第二章

进程与线程¶

进程的概念和特征以及进程的组成¶

进程和程序的区别：进程就是程序执行的一次过程，是动态的，而程序是静态的是放在内存或外存里的指令集合。
一个进程实体（进程映像）由PCB，程序段，数据段组成。ps:进程实体是静态的，可以理解成进程一瞬间的快照。
进程本身不直接参与CPU调度，线程才是CPU调度的最小单位，进程是资源分配的最小单位。

思维导图：

进程的状态与转换¶

进程控制¶

作业：就是放在外存的程序

总结：

进程通信¶

进程的通信¶

进程间通信（IPC，Inter-Process Communication）：指的是两个进程之间产生数据交互。
消息头包括：发送进程ID、接受进程ID、消息长度等格式化的信息（概要）。
管道中同一时间段内数据的流向一定是单向的，这就是半双工通信。
管道中是先进先出的（FIFO），这也是管道通信和共享存储的区别。ps:就是（循环）队列嘛
如果多个读进程对一个管道进行读时可能会错乱，所以关于管道的读写有两种观点：

（1） 一个管道允许多个写进程，一个读进程。（408官方答案）

（2）一个管道允许多个写进程和读进程，但系统会轮流让各个读进程从管道中读取数据。（Linux）

两个观点都没有错，但是考试时认准（1）

管道非空就可以读，管道没满就可以写。

总结：

信号¶

信号与信号量：信号量（Semaphore）用以实现进程间的同步、互斥；而信号（Signal）用以实现进程间通信。
进程之间能发送的信号类型是有限制的。
各个进程自定义的处理程序只在该进程内生效。

总结：

线程和多线程模型¶

线程的概念与特点¶

线程是程序执行流的最小单位。
资源是直接分配给进程的，而非线程。

总结：

线程的实现方式和多线程模型¶

内核级线程进行切换时需要变态，用户级线程不需要。
内核级线程一个线程阻塞后不影响其他线程，用户级线程影响。
因为操作系统只看得见内核级线程，因此内核级线程是处理机的分配单位。

总结：

线程的状态和转换¶

线程的PCB叫做TCB（Thread Control Block），同样的多个TCB组织成一张线程表。

节末习题笔记¶

进程的生命周期是不连续的，因为可能发生阻塞或抢占。
在单处理器系统中，任何时刻都只有一个进程处于运行态，这个说法是错误的，因为可能发生死锁，这时没有一个进程处于运行态。
操作系统是根据PCB来对并发执行的进程进行控制和管理的。
并发进程失去封闭性指的是，并发执行的进程，其执行结果不再仅仅由自身的代码逻辑和初始输入决定，还会受到其他并发进程的干扰或影响，打破了 “进程执行环境独立、结果可预测” 的封闭特性。
父进程和子进程是相互独立的，可以并发执行。
C语言编写的程序在使用内存时一般分为三个阶段：正文段（代码和赋值数据段）、数据堆段和数据栈段。数据堆段放的是动态分配的存储区，比如malloc或者vector，这里注意vector的数据是放在堆段的，但是对象定义在哪就存在哪，数据栈段放的就是局部变量和实参传递。
原语在内核态下执行，常驻内存。
速度最快的进程通信方式是共享存储，不需要进行数据的拷贝。
引入线程后，处理器依旧可以进行进程的切换。
同一进程中的线程间通信不一定需要使用系统调用函数，这是因为他们可以共享存储区。
线程的引入减少了程序执行时的时空开销。
用户级线程的调度单位仍旧是进程这是因为内核“看不见”用户级线程，因此只能分配给他们的进程。
跨进程的线程切换需要内核参与。
内核态中存在的是进程，而进程下是线程，但是进行调度时线程是最小单位。
内核级线程的程序实体可以在内核态运行。
内核级线程同一进程内的线程切换需要从用户态转到内核态，系统开销大。
用户级线程中同一个进程内的多个线程并不可以同时调度到多个处理器上，这是因为内核只能看到进程，所以不能利用多处理器的并行性。
涉及内核态的事件都不会导致用户级线程切换，但会导致内核级线程切换。
线程同步是指多个线程之间协调执行顺序的机制，如互斥锁、信号量、条件变量等。当一个线程在等待同步条件时，应用程序可以选择切换到另一个就绪的用户级线程。
线程库中线程的切换不会导致进程的切换。
用户级线程除了涉及 I/O 的操作、阻塞类系统调用、进程级资源申请、线程的终止（触发进程退出）外，都是在用户态下实现的。
创建进程的主要原因有：用户登录；高级调度；系统处理用户程序的请求；用户程序的应用请求。
线程库是在本进程下，也就是说线程库管理的只是本进程下的所有用户级线程。
父进程和子进程之间不会共享虚拟地址空间，但是在创建子进程时会为子进程分配资源，如虚拟地址空间等。
有些操作系统在终止父进程时并不一定会终止子进程。
共享内存区和共享文件并非一回事，前者是内存级、高速、非持久化的共享；后者是磁盘级、低速、持久化的共享。
多任务和多线程：前者是相对于操作系统的，代表操作系统可以同时执行的程序个数；后者是针对一个程序而言，代表一个程序可以同时执行的线程个数，而每个线程可以完成不同的任务。

CPU调度¶

调度的概念、层次¶

挂起：内存不够时，暂时把某些进程的数据调到外存，这次这种状态称为挂起态，等内存空闲或进程需要处理时再通过中级调度调回内存。
阻塞与挂起的区别：两种都是暂时不能获得CPU的服务，前者的进程映像还在内存中，后者的不在。
就绪挂起：满足运行条件，等待调入内存。
阻塞挂起：等待事件，且在外存。

总结：

进程调度的时机+切换与过程调度方式¶

临界区和内核临界区：前者就是访问临界资源的那段代码；后者一般是用来访问某种内核数据结构的，比如进程的就绪队列。
进程在操作系统内核临界区时中不能进行调度与切换（为了尽快释放临界资源，不然可能影响到操作系统内核的其他管理工作）。
进程处于临界区时可以进行处理机调度（这是因为某些临界资源太慢，不切换的话占用CPU，要保证CPU不空闲）。
调度器/调度程序（scheduler）：决定“让谁运行”、”运行多长时间”。
闲逛进程：调度程序的备胎，没有其他就绪进程时，就运行闲逛进程（就像人无聊没事干抖腿一样）。
闲逛进程的特性：优先级最低、可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）、能耗低。

总结：

调度算法的评价指标¶

系统吞吐量就是单位时间完成了多少道作业。

总结：

调度算法¶

先来先服务（First Come First Serve, FCFS）
最短作业优先（Short Job First， SJF）
最高相应比优先（Highest Response Ratio Next, HRRN）:响应比=(等待时间 + 要求服务时间) / 要求服务时间
时间片轮转（Round-Robin, RR）
优先级调度算法
多级反馈队列调度算法 ：
多级队列调度算法（与6不同）：系统中按照进程类型设置多个队列，并且每个队列可采用不同的调度策略，各队列优先级各不相同，时间片可不同可相同，一般时不可抢占的。

总结：

多处理机调度¶

多处理机比单处理机要多考虑的就是让这个进程/线程上哪个处理机。

总结：

节末习题笔记¶

进程上下文：当一个进程被执行时，CPU的所有寄存器中的值（进程现场信息）、进程的状态和控制信息以及堆栈中的内容。
当进程切换时，操作系统需要保存当前线程的PC的值，并恢复新线程的PC。
在多线程条件下，每个线程拥有各自独立的栈。
同一个进程中的线程共享进程的虚拟地址空间，因此线程切换时不需要更新页基址寄存器的值；但是进程切换时需要。
CPU繁忙型作业：需要占用很长的CPU时间，而很少请求I/O操作的作业，类似于长作业，适合FCFS；而FCFS为什么适合长作业而不适合短作业是因为它非抢占，短作业等待时间长。
I/O繁忙型作业：需要频繁请求I/O操作，即可能频繁放弃CPU，所以占用CPU的时间不会太长，一旦放弃CPU，则必须重新排队等待调度，适合SJF。
静态优先级在进程创建时确定，之后不再更改。
RR是抢占式的。
RR在实际运行中也按先后顺序使用时间片，所以时间片过大时，可以认为其大于进程需要时间，即FCFS。
降低进程优先级的合理时机时进程时间片用完。
当只有两个进程先后到达时，FCFS 调度算法的总完成时间和平均等待时间，是所有非抢占式调度算法中最优的。
当进程数量 ≥ 3 时，FCFS 不再是 “时间最少” 的方案，此时 SJF（短作业优先） 能显著降低平均等待时间和总完成时间。
考虑到系统资源利用率，对于优先级调度算法，一般来说，I/O型作业的优先权高于计算型作业的优先权，这是因为I/O操作需要及时完成，它没办法长时间地保存所要输入/输出的数据，所以要选择I/O繁忙型作业有更高的优先级。
进程每进行一次切换需要一次调度（选谁）+一次切换。

同步与互斥¶

同步与互斥的基本概念¶

临界资源：一个时间段内只允许一个进程使用的资源。
临界区也称临界段

总结：

进程互斥的实现方法¶

进程互斥的软件实现方法¶

单标志法因为进程A总是退出临界区后把进入临界区的权限让给进程B，所以如果B进程一直不进入临界区的话，这时进程A想进也进不去，这就违反了空闲让进。

// 全局共享变量
int turn = 0; // turn 表示当前允许进入临界区的进程号

// P0 进程代码
while (turn != 0);     // ① 进入区：等待轮到自己
critical section;      // ② 临界区：访问共享资源的代码段
turn = 1;              // ③ 退出区：将使用权交给 P1
remainder section;     // ④ 剩余区：其他代码

// P1 进程代码
while (turn != 1);     // ⑤ 进入区：等待轮到自己
critical section;      // ⑥ 临界区：访问共享资源的代码段
turn = 0;              // ⑦ 退出区：将使用权交给 P0
remainder section;     // ⑧ 剩余区：其他代码

双标志先检查因为如果并发执行的进程A和进程B同时都想进临界区，并且由于进入区的“检查”和“上锁”并非一步完成，可能会发生进程切换，所以这时有可能会发生他们都进入了临界区的情况，这就违反了忙则等待。

// 全局共享变量
bool flag[2]; // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 刚开始设置为两个进程都不想进入临界区

// P0 进程代码
while (flag[1]);       // ① 检查 P1 是否想进入
flag[0] = true;        // ② 标记自己想进入
critical section;      // ③ 临界区
flag[0] = false;       // ④ 标记自己不想进入了
remainder section;     // ⑤ 剩余区

// P1 进程代码
while (flag[0]);       // ① 检查 P0 是否想进入
flag[1] = true;        // ② 标记自己想进入
critical section;      // ③ 临界区
flag[1] = false;       // ④ 标记自己不想进入了
remainder section;     // ⑤ 剩余区

双标志后检查虽然解决了忙则等待，但是却引发了新问题，当进程A、进程B同时都想要进入临界区时，都会卡在进入区，会产生”饥饿”，这就违反了空闲让进和有限等待。

// 全局共享变量
bool flag[2]; // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 初始时两个进程都不想进入临界区

// P0 进程代码
flag[0] = true;        // ① 表达自己想进入临界区的意愿
while (flag[1]);       // ② 检查 P1 是否也想进入，若想则等待
critical section;      // ③ 临界区：访问共享资源
flag[0] = false;       // ④ 退出临界区，重置意愿
remainder section;     // ⑤ 剩余区：其他代码

// P1 进程代码
flag[1] = true;        // ⑤ 表达自己想进入临界区的意愿
while (flag[0]);       // ⑥ 检查 P0 是否也想进入，若想则等待
critical section;      // ⑦ 临界区：访问共享资源
flag[1] = false;       // ⑧ 退出临界区，重置意愿
remainder section;     // ⑨ 剩余区：其他代码

Peterson算法解决了空闲让进、忙则等待、有限等待，但是却没有解决让权等待，因为它进入不了临界区时，仍在执行while循环中的空语句，这会占用CPU资源。

// 全局共享变量
bool flag[2]; // 表示进入临界区意愿的数组，初始值都是 false
int turn = 0; // turn 表示优先让哪个进程进入临界区

// P0 进程代码
flag[0] = true;                // ① 表达自己想进入临界区的意愿
turn = 1;                     // ② 礼让，让 P1 优先进入
while (flag[1] && turn == 1); // ③ 若 P1 也想进且轮到它，就等待
critical section;              // ④ 临界区
flag[0] = false;               // ⑤ 退出，重置意愿
remainder section;             // ⑥ 剩余区

// P1 进程代码
flag[1] = true;                // ⑥ 表达自己想进入临界区的意愿
turn = 0;                     // ⑦ 礼让，让 P0 优先进入
while (flag[0] && turn == 0); // ⑧ 若 P0 也想进且轮到它，就等待
critical section;              // ⑨ 临界区
flag[1] = false;               // ⑩ 退出，重置意愿
remainder section;             // ⑪ 剩余区

总结：

进程互斥的硬件实现方法¶

中断屏蔽方法只适用于操作系统内核进程是因为，开/关中断指令只能运行在内核态，这组指令如果让用户随意使用会很危险。
TSL:TestAndSetLock

// 布尔型共享变量 lock 表示当前临界区是否被加锁
// true 表示已加锁，false 表示未加锁
bool TestAndSet(bool *lock) {
    bool old;
    old = *lock;        // old 用来存放 lock 原来的值
    *lock = true;       // 无论之前是否已加锁，都将 lock 设为 true
    return old;         // 返回 lock 原来的值
}

// 使用 TSL 指令实现互斥的算法逻辑
while (TestAndSet(&lock)); // “上锁”并“检查”，若返回 true 说明锁已被占用，循环等待
临界区代码段...
lock = false;              // “解锁”
剩余区代码段...

Swap指令也称Exchange指令，或简称XCHG。

// Swap 指令的作用是交换两个变量的值
Swap(bool *a, bool *b) {
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 以下是用 Swap 指令实现互斥的算法逻辑
// lock 表示当前临界区是否被加锁
bool old = true;
while (old == true)
    Swap(&lock, &old);
临界区代码段...
lock = false;
剩余区代码段...

注意，3.2.2代码旨在模拟TSL和Swap，二者本质为硬件实现

TSL和Swap不满足让权等待和Peterson算法类似，因为进不了进临界区了所以在忙等。

总结：

互斥锁¶

解决临界区最简单的方法就是互斥锁（mutex lock）。一个进程在进入临界区时获得锁，退出临界区时释放锁。函数acquire()获得锁，release()释放锁。

acquire(){
    while(!avaliable);  //忙等待
    avaliable = false;  //获得锁
}
release(){
    avaliable = true;   //释放锁
}c

同样违反让权等待。
因为忙等时得不断while检查，所以又称自旋锁（spin lock），如TSL、Swap、单标志法。
忙等不会一直占用处理机，时间片没了也会下处理机。
优点：等待期间不需要切换进程上下文，多处理机系统中，若上锁时间很短，则等待代价很低。
常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区。
不太适合单处理器系统，因为忙等的过程中不可能解锁。

信号量¶

信号量机制¶

wait()原语、signal()原语分别对应P操作（荷兰语：proberen，尝试，可理解为申请和V操作（荷兰语：verhogen，增加，可理解为释放）。

//整型信号量
// 初始化整型信号量 S，表示当前系统中可用的打印机资源数
int S = 1;

// wait 原语，相当于“进入区”
void wait(int S) {
    // 如果资源数不够，就一直循环等待
    while (S <= 0);
    // 如果资源数够，则占用一个资源
    S = S - 1;
}

// signal 原语，相当于“退出区”
void signal(int S) {
    // 使用完资源后，在退出区释放资源
    S = S + 1;
}

//记录型信号量
// 记录型信号量的定义
typedef struct {
    int value;               // 剩余资源数
    struct process *L;       // 等待队列
} semaphore;

// 某进程需要使用资源时，通过 wait 原语申请
void wait(semaphore S) {
    S.value--;
    if (S.value < 0) {
        block(S.L);          // 若资源不足，将进程阻塞并放入等待队列
    }
}

// 进程使用完资源后，通过 signal 原语释放
void signal(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        wakeup(S.L);  // 若等待队列中有进程，唤醒其中一个
    }
}

对于wait()原语中是否会卡在while循环一问题有如下解释：

2.1 对于整型信号量

2.1.1 对于单核：不会，因为时间片会到

       2.1.2 对于多核：可能会，因为带着锁的进程因为各个核的时间片各自独立。

2.2 对于记录型信号量：不会，因为直接阻塞了，会把CPU让给其他进程，这是真正的pv操作，不会自旋等待。

通常来说，S.value < 0时，S.value的绝对值就是此时在等待队列里的进程数量。

总结：

用信号量实现进程互斥、同步、前驱关系¶

所谓的进程同步并非真正意义上的同步，而是有序进行。

总结：

经典进程同步互斥问题¶

实现互斥的P操作一定要在实现同步的P操作之后，如果颠倒位置可能会发生死锁；V操作的顺序则无所谓。

生产者-消费者¶

此处把“生产一个产品”和“使用产品”放在临界区外是因为要尽可能地让临界区小。

多生产者-多消费者¶

读者-写者¶

若想真正实现写者优先，可以统计一下写者数量，只要不为0，那就不让读者进临界区

哲学家进餐问题¶

解决方案：

最多只允许四个哲学家同时拿筷子。

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 4;
Pi(){
    while(1){
        P(mutex);
        P(chopstick[i]);
        P(chopstick[(i + 1) % 5]);
        吃饭...
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
        V(mutex);
        思考...
    }
}

偶数序号的哲学家拿左手的筷子，奇数序号的哲学家拿右手的筷子。

semaphore chopstick[5] = {1, 1, 1, 1, 1};
Pi(){
    while(1){
        if(i % 2 == 0) {
            P(chopstick[i]);
            P(chopstick[(i + 1) % 5]);
        }else{
            P(chopstick[(i + 1) % 5]);
            P(chopstick[i]);
        } 
        吃饭...
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
        思考...
    }
}

各哲学家拿筷子必须保证互斥。

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
Pi(){
    while(1){
        P(mutex);
        P(chopstick[i]);
        P(chopstick[(i + 1) % 5]);
        V(mutex);
        吃饭...
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
        思考...
    }
}

管程¶

管程就像是类。

总结：

节末习题笔记¶

临界资源和共享资源的区别：区别就在于在一段时间内能否允许被多个进程并发使用，前者不可以，后者可以。
PV原语是一种低级的进程通信原语，是不能被中断的。
可重入编码是 “同一代码能被多个执行流安全复用”。
互斥锁可用于多进程或多线程之间，但是只有对它加锁的线程或进程才能解锁它。
若线程1先对互斥锁A加锁，然后尝试对互斥锁B加锁；同时，线程2先对B加锁，然后尝试对A加锁，两个线程都在等待对方释放资源，从而形成死锁。
管程是被进程调用的，管程是语法范围，无法创建和撤销。
管程中的signal操作的作用和信号量机制中V操作不同，前者是针对某个变量条件的，若不存在因该条件而阻塞的进程，则signal不会产生任何影响，而后者则是一定会改变信号量的值S = S + 1。
有n个进程，阻塞队列中进程的个数最多有n个。（死锁）
生产者-消费者用于解决多个进程之间的同步和互斥问题。
TSL实现进程互斥时并没有阻塞态进程（因为是硬件实现），并且等待进入临界区的进程一直停留在执行while(TSL(&lock))的循环中，不会主动放弃CPU（时间片到了属于主动放弃）。
管程的wait()不是直接 “检查条件”，而是线程先自行检查条件，若不满足则调用wait()主动放弃 CPU 并进入阻塞态——wait()本身是 “阻塞操作”，而非 “条件检查操作”，条件检查是调用wait()的前提；signal()不保证条件一定满足，也不直接让被唤醒线程执行，也不分配CPU，只是 “解除阻塞”，把线程从 “等待队列” 移到 “就绪队列”。
简单来说，条件变量是一个 “线程等待队列 + 唤醒 / 阻塞接口” 的组合，它的唯一作用是：让线程在 “条件不满足时主动阻塞，条件满足时被唤醒”，解决管程中 “互斥之外的同步问题”。

死锁¶

死锁的概念¶

如果同类资源数大于1，则即使有循环等待，也未必发生死锁；但是如果系统中每类资源都只有一个，那么循环等待就是死锁的成分必要条件了。

总结：

预防死锁¶

资源静态分配策略就是运行前分配好所有需要的资源，之后一直保持。

总结：

避免死锁¶

安全序列：如果系统按照这种序列分配资源，则每个进程都能顺利完成。当然，安全序列可能有多个。
安全状态：只要能找出一个安全序列，系统就是安全状态。

总结：

检测和解除¶

如何对哪个进程“动手”优先考虑：进程优先级低的，以执行时间短的，批处理式的，离完成远的，已经使用了很多资源了的。

“动手”在这里指的是“撤销、挂起”，对于后两个来说是用系统开销换取解锁效率，并非最小损失策略。

资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。
撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。

总结：

节末习题笔记¶

若本题不加任何条件限制，那么例子中最坏的资源分配情况就是A分配a - 1, B分配b - 1，C分配c - 1, 这时若m > a + b + c - 3那就一定不会发生死锁，若m <= a + b + c - 3有可能会发生死锁；而本题要求使用银行家算法，若此时每个进程都分配了k - 1个资源，那么总的已分配资源量为n * (k - 1),剩下的资源数就是m - n * (k - 1)，那么如果要保证安全，剩下的资源数一定要大于等一，即m - n * (k - 1) >= 1,变形可得n * k <= m + n - 1，也就是所有进程所需资源数要小于等于m + n - 1,即小于m + b。

或者简单想想，让他们平均分，每个进程都取m / n + 1个资源的时候刚好死锁，n个进程所需的总共的资源数就是n(m / n + 1) = m + n

对死锁的四种方法：忽略、检测与恢复、避免和预防，系统并发性由大到小。
为什么会发生死锁：竞争资源、进程推进顺序非法。
银行家算法也算分配策略，算是动态分配规则，而静态分配和按序分配则是静态。