2 进程与线程

2.1 进程与线程

2.1.1 概念和特征

概念

进程：在多道程序环境下，并发执行的多个程序失去封闭性，具有间断性和不可再现性，因此引入进程来更好描述和控制程序的并发执行，实现操作系统的并发和共享。
进程控制块（Precess Control Block， PCB）描述进程的基本情况和运行状态的数据结构，进而控制和管理进程。
进程映像（进程实体）：程序段、数据段、PCB构成。

创建进程的实质是创建一个进程控制块。
vice versa，撤销进程的实质是撤销进程的PCB。即，PCB是进程存在的唯一标志。
进程映像是静态的，进程是动态的
进程可以有如下几种定义：
- 程序的一次执行过程
- 程序及其数据在处理器顺序执行发生的活动
- 具有独立功能的程序在数据集合上运行的过程，是系统机型资源分配和调度的独立单位。
- 进程实体的运行过程，系统进行资源分配和调度的一个独立单位

特征

动态性：最基本特征。进程有创建、活动、暂停、终止等过程，具有生命周期，是动态产生、变化和消亡的；
并发性：多个进程实体可以在内存中同时存在并并发执行
独立性：进程实体是一个能独立运行、独立获得资源和接受调度的基本单位
异步性：不同进程相互制约，使其具有运行时的间断性，各自独立，运行时间未定。
结构性：进程实体由程序段、数据段、PCB共同组成。

2.1.2 进程的状态和转换

五种状态，其中包括三种基本状态。

运行状态
就绪状态
阻塞状态（等待状态）
创建状态
结束状态

就绪和等待的区别：就绪状态获得处理器资源立即执行；等待状态则还需要额外等待其他进程结束。

状态的转换：

就绪状态 → 运行状态：获得时间片，立即转换
运行状态 → 就绪状态：用完时间片，让出资源
运行状态 → 等待状态：进程请求其他资源，如系统调用时
等待状态 → 就绪状态：进程等待的事件到来时，可以继续

只有就绪和运行两个状态可以双向。从等待状态出来只能是就绪状态。只有运行中才能再处于等待状态（就绪状态本就未在运行，无从等待）

2.1.3 进程控制

对系统中所有进程实施有效的管理，具有创建新进程、撤销已有进程、实现进程状态转换等功能。进程控制程序是原语（原子化、不允许中断）。

当一个进程创建另一个，则创建者为父进程，被创建者为子进程。子进程可继承父进程资源，撤销时也需要归还资源。撤销父进程必须撤销所有子进程。

进程的创建

分配PID，申请一个空白的PCB（PCB有限），申请失败则创建失败
分配资源（如数据、程序、用户栈所需内存空间），如失败会进入等待状态
初始化PCB，包括初始化标志信息、处理器状态信息、处理器控制信息、优先级
如果进程就绪队列可容纳该新进程则进入就绪队列等待调度执行。

进程的终止

正常结束：完成并自行结束运行
异常结束：发生存储区越界、非法指令、特权指令错、IO故障等情况

终止进程会运行一系列撤销原语：

根据进程标识符检索PCB，读取进程状态
若该进程处于执行状态，则立即终止，将处理器资源分配给其他进程
若该进程还有子进程，则全部终止
将该进程的全部资源归还父进程或操作系统
将该PCB从所在队列（PCB）中删除

进程的阻塞和唤醒

若进程期待的某些事件未发生（请求资源失败、等待其他操作完成），则系统主动执行阻塞原语（Block）

找到将要被阻塞进程的标识对应的PCB
若该进程为运行状态则保护现场，改为阻塞状态并停止运行
将该PCB插入当相应事件的等待队列中。

而反之，唤醒原语（Wakeup）的执行顺序为：

在事件的等待队列中寻找相应PCB
将其从等待队列中移除，设置为就绪状态
将此PCB插入就绪队列中，等待调度。

Block和Wakeup原语作用恰好相反，因此需要成对使用。

Block原语是由被阻塞进程自我调用实现的
Wakeup原语是有一个与被唤醒进程相关的进程调用实现的。

进程切换

进程切换与前三项一样都是通过内核实现的。具体步骤如下：

保存处理器上下文，包括程序计数器和其他寄存器内容
更新PCB信息
将进程PCB移入相应队列，如就绪、阻塞等。
选择另一个进程执行，并更新其PCB
更新内存管理的数据结构
恢复处理器上下文

进程切换不同于处理器模式切换。

模式切换时处理器逻辑上可能还在同一个进程中运行，如果进程进入核心态运行后回到用户态，操作系统只需要恢复进入内核前保存的现场，当前进程的环境信息不必改变。
切换进程时，由于发生了进程的改变，当前进程的环境信息需要改变。

2.1.4 进程的组织

进程时操作系统的资源分配和独立运行的基本单位，一般有以下三个部分组成：进程控制块、程序段和资源。

PCB

创建进程时就会新建一个空白PCB，之后就会常驻内存并可在任意时间进行存取，并在程序结束后删除。PCB是进程实体的一部分，是进程存在的唯一标志。

操作系统通过PCB表来管理和控制进程。

进程描述信息
- PID、UID
进程控制和管理信息
- 当前状态、优先级、代码入口地址、程序外存地址、进入内存时间、占用时间、信号量使用
资源分配清单
- 代码段指针、数据段指针、堆栈段指针、文件描述符、IO设备
处理器相关信息
- 通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值、程序状态字

程序段

程序段就是能被进程调度程序调度到CPU执行的程序代码段。程序段可以被多个程序共享：多个进程可以运行同一个程序。

数据段

进程对应的程序处理的原始数据或中间和最终结果。

2.1.5 进程的通信

1. 共享存储

进程间存在一块可以直接访问的共享空间，荣国这篇共享空间进行信息交换，在对共享空间进行读写操作时，需要使用同步互斥工具（P操作、V操作）进行控制。

用户进程空间一般是独立的，进程运行期间一般不能访问其他进程的空间，除非使用特殊的系统调用。而进程内的线程可以共享进程空间。

P操作：
- ① 将信号量S的值减1，即S=S-1；
- ② 如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。
V操作：
- ①将信号量S的值加1，即S=S+1；
- ②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

2.消息传递

消息传递系统中，进程间数据交换是以格式化的消息为单位的。通过发送原语和接受原语进行数据交换

直接通信方式：发送进程直接将消息发送给接受进程，并将其挂在接收进程的消息缓冲队列熵，接收进程从该队列取得消息。
间接通信方式：发送进程将消息发送到某个中间实体（一般称为信箱），接收进程从该中间实体取得消息。（计算机网络中称为电子邮件系统）

3.管道通信

“管道”就是用于链接一个读进程和一个写进程来实现其通信的一个共享文件，又名Pipe文件。相关到提供输入的发送进程以字符流形式将数据送入写管道，接受管道输出端的接收进程则从中读取数据。为协调双方通信，管道机制必须提供以下三方面的协调能力：

互斥
同步
确定对方存在

无名管道：半双工，只能用于亲缘关系的进程之间
有名管道：半双工，允许无亲缘关系的进程之间。

其他

套接字（Socket）通信：可用于不同进程的通信
信号量（Semaphore）：主要用于实现进程间互斥和同步

2.1.6 线程概念、多线程模型

线程的概念

线程的组成：线程ID、程序计数器、寄存器集合、堆栈
线程的状态：就绪、运行、阻塞
线程的概念：线程是进程中的一个实体，是被系统独立调度和分配的基本单位，其自身不拥有系统资源，但可以与同一个进程之间的线程共享资源。线程之间互相制约，可并发运行，可相互撤销

线程和进程

调度：线程是独立调度的基本单位，进程是拥有资源的基本单位。
拥有资源：线程不拥有系统资源，但具有维持运行的一些资源，但可以通过访问其他线程的资源。
并发性：都可以并发运行。
系统开销：线程在创建和撤销时需要分配或回收资源，且切换时也需要大量开销保存现场。而线程切换时只需要保存少量寄存器内容，开销较小。
地址空间和其他资源：进程的地址空间和其他资源之间相互独立，而一个进程之间多个线程之间可以共享以上内容。

线程的属性

轻型实体，不拥有系统资源，但都应具备标识符和线程控制块TCB
不同线程可以执行相同程序
容易进程的不同线程共享资源
线程是处理器独立调度的最小单位，多个线程可以并发执行。
线程同样在创建后开始生命周期，具有就绪、运行、阻塞态。

线程的实现方式

用户级线程（ULT，User-level thread），应用程序执行线程管理
内核级线程（KLT，Kernel-level thread），内核执行线程管理
组合方式，二者兼有

多线程模型

多对一：多个用户级线程映射到一个内核级线程，在用户空间进行管理
- 效率较高，但内核中有一个线程阻塞则全部进程阻塞，多线程不能并行运行在多处理器上
一对一：每个用户级线程映射到一个内核级线程
- 一个线程被阻塞后可以继续其他线程执行，并发能力较强。线程但创建开销较大
多对多：n个用户及线程映射到m个内核级线程，m<=n
- 二者折中。

2.2 处理器调度

2.2.1 调度的概念

基本概念

进程之间往往会存在资源竞争，因此，从就绪队列中，按照一定算法选择继承并分配处理器给其运行来实现进程的并发执行就是处理器调度。
处理器调度是多道程序操作系统的基础，是操作系统设计的核心。

调度的层次

作业从提交到完成需要三级调度：

作业调度：又称高级调度，按一定原则从外存上出狱后被状态的作业中挑选一个或多个，给其分配内存、IO设备等，并建立相应进程，使其获得竞争处理器的权利：内存与外存之间的调度。对于每个作业，只调入一次、调出一次。
内存调度：又称中级调度，将暂时不运行的进程放入外存等待，此时的进程为挂起状态。再将外存其他具备条件的就绪进程调入内存，挂在就绪队列上等待。是为了提高内存利用率和系统吞吐量
进程调度：又称低级调度，按照算法从就绪队列选取进程并分配处理器。是操作系统中被基本的一种调度，在操作系统中都必须具备。频率很高，几十毫秒一次。

三级调度的联系

作业调度为进程活动做准备，进程调度使进程正常活动，中级调度将暂时不用的进程挂起。
越低级的调度频率越高
进程调度在操作系统中不可或缺

2.2.2 调度的时机、切换、过程

不会进行进程调度和切换的情况：

处理中断：并不发生进程切换，因此不应被剥夺处理器资源
进程处于内核程序的临界区：进入临界段需要独占访问数据，需要加锁来防止其他并行程序进入。
其他屏蔽中断的原子操作（加锁、解锁、现场保护和恢复）同样不能中断，因而不会发生进程的切换。

应该进行进程调度和切换的情况：

发生引起调度的条件且当前进程无法继续运行下去
中断处理结束或自陷处理结束返回执行现场前，可以马上进行调度和切换（剥夺方式的调度）

2.2.3 进程调度方式

非剥夺调度：非抢占方式。当前进程完成或等待时才进入其他进程，实现简单且开销小
剥夺调度：抢占方式，一个进程执行时若有另一个更重要的需要使用处理器则立即暂停当前进程。提高了系统吞吐率和效率，用在实时操作系统中。

2.2.4 调度的基本准则

选择调度算法的准则：

CPU利用率
系统吞吐量：单位时间CPU完成作业量
周转时间：作业从提交到完成的时间，带权周转时间：周转时间/实际运行时间
等待时间：进程处于等待状态时间之和
响应时间：从提交请求到首次产生响应的时间

2.2.5 典型调度算法

1. 先来先服务（FCFS，First come first service）

非剥夺算法。简单但效率低

2. 短作业优先（SJF，Short job first）

对长作业不利：饥饿现象（Starvation）
非剥夺算法。最短的平均等待时间和平均周转时间

3. 优先级调度

可用于作业调度、进程调度。

按是否抢占分为：

非剥夺优先级调度
剥夺优先级调度

按优先级是否可以改变分为：

静态优先级
动态优先级

4. 高响应比优先级调度算法

主要用于作业调度。通过响应比平衡了FCFS和SJF调度算法
响应比 = (等待时间+要求服务时间)/要求服务时间
长作业的等待时间长，从而获得高响应比避免饥饿；
等待时间相同，则要求服务时间短的响应比高，实现短作业优先；
要求服务时间相同，则等待时间长的响应比高，实现先来先服务。

5. 时间片轮转调度算法

主要用于分时系统，将所有就绪进程按到达先后排为队列，总是选择第一个执行（FCFS），但在一个时间片后必须被剥夺而处理下一个就绪的进程。被剥夺的进程则被放到队列末尾。
时间片过长，则退化为FCFS；过短则进程切换开销过大。由系统响应时间、就绪队列中的进程数和系统处理能力确定。

6. 多级反馈队列调度算法

时间片轮转和优先级调度算法的综合和发展。

设置多个就绪队列，给这些队列赋予不同优先级，1级最高
赋予各队列进程的时间片大小各不相同
每当存在新进程，进入队列1，若在一个时间片中未完成，则放入队列2，以此类推，最终在队列n按时间片轮转调度
仅前面所有队列为空，才调度下一级队列的进程，

2.3 进程同步

2.3.1 基本概念

进程之间存在相互制约的关系。为了协调制约关系，需要进行进程同步。

1.临界资源

临界资源是一次仅允许一个进程使用的资源。如物理设备、某些变量和数据。
临界资源必须互斥访问。访问临界资源的代码段称为临界区或临界段

临界资源的访问过程：

进入区：检查是否可以进入临界区
临界区：进程中访问临界资源的代码
退出区：将正在访问临界区的标志清除
剩余区：代码中的剩余部分

while(true){
    entry section;
    critical section;
    exit section;
    remainder section;
}

2.同步

同步又称直接制约关系，是指未完成某种任务而建立的两个或多个进程由于需要在某些位置上协调工作秩序而等待、传递信息所产生的制约关系。

例如：进程A通过单缓冲，向进程B提供数据。当该缓冲区空时，B取不到则阻塞；反之，缓冲区满时，A写不入则阻塞。

3. 互斥

互斥又称间接制约关系：一个进程进入临界段时，另一个进程必须等待直至使用临界资源的进程退出临界区，才能访问临界资源。、

例如：仅有一台打印机的系统中，A在打印时B只能先阻塞直到打印机释放。

为禁止两个进程同时进入临界区，同步机制的准侧有：

空闲让进：临界区空闲时，允许任意请求
忙则等待：已有临界区进程时，其他等待
有限等待：保证请求访问的进程在有限时间内进入临界区
让权等待：不能进入临界区时立即释放处理器，防止忙等待（反复检查）

2.3.2 实现临界区互斥的基本方法

1.软件实现方法

单标志法：设置一个公用整形变量turn用于指示被用于进入临界区的进程编号。仅仅在进入区进行检查而不锁定。但是必须多个进程交替进入临界区，否则会卡住（违背空闲让进原则）：如P0执行完毕后turn改为1，但P1并无进入临界区的打算，则此时turn一直不变，其他进程一直等待。
```
//Process0:
    while(turn != 0){}  //进入
    ciritical section;  //临界
    turn = 1;           //退出
    remainder section;  //剩余

//Process1:
    while(turn != 1){}
    critical section;
    turn = 0;
    remainder section;
```
双标志先检查：在每个进程访问临界区资源之前，查看临界资源是否正被访问。数据flag[i]为true表示第i个进程进入临界区，否则未进入。解决了单标志法必须教体进入的问题，但是由于检查和修改不能同时进行，在检查对方flag和改变自己flag之间会出现两个进程同时进入临界区的情况，违背了忙则等待。
```
//Process i:
    while(flag[j]){}   //进入
    flag[i] = true;
    critical section;  //临界
    flag[i] = false;   //退出
    remainder section; //剩余

//Process j:
    while(flag[i]){} 
    flag[j] = true;
    critical section;
    flag[j] = false;
    remainder section;
```
双标志后检查：在进入区先设置自己的状态，再判断对方的状态，即将先检查的进入区代码交换。容易在同时运行第一行后使得二者flag都为True，造成饥饿状态。违背了有限等待和空则让进即：先检查则抢入，后检查则谦让。
```
//Process i:
    flag[i] = true;    //进入
    while(flag[j]){} 
    critical section;  //临界
    flag[i] = false;   //退出
    remainder section; //剩余

//Process j:
    flag[j] = true;
    while(flag[i]){} 
    critical section;
    flag[j] = false;
    remainder section;
```
Peterson's Algorithm：防止双标志先检查的同时进入临界区和后检查的饥饿现象，该算法设置了变量turn，每个进程在先设置自己的标志后再设置turn标志，再同时检测另一个进程的状态标志和不允许进入标志，保证只有一个进入临界区。flag表示是否想进，可以有多个true，而turn表示唯一进入的。表示自己想进后将进入让给另一个，如果另一个不想进则直接进，如果另一个也想进则进，当前这个进入检查循环。
```
//Process i:
    flag[i] = true;  //进入区
    turn = j;
    while(flag[j] && turn == j); //缺一则直接往下
    critical section;   //临界区
    flag[i] = false;    //退出区
    remainder section;  //剩余区

//Process j:
    flag[j] = true;
    turn = i;
    while(flag[i] && turn == i);
    critical section;
    flag[j] = false;
    remainder section;
```

2.硬件实现方法

中断屏蔽：在有进程访问临界段时，禁止一切中断的发生。由于限制了处理器交替执行程序的能力，会降低程序执行效率。
```
...
关中断
临界区
开中断
...
```
硬件指令方法
- TestAndSet指令：是一个原子操作，执行该代码时不允许被中断。功能是读出指定标志后将其设置为真。
```
bool TestAndSet(bool* lock){
    bool old = *lock;
    *lock = true;
    return old;
}
```
  可以为每个临界资源设置共享的变量lock来表示是否被占用。每当进程在访问临界资源之前都需要运行TestAndSet检查和修改标志lock，若有进程正在占用则重复检查直至解除占用，该部分代码为：
```
while(TestAndSet(&lock));
critical section;
lock = false;
```
- Swap指令：交换两个字或字节的内容。
```
void swap(bool* a, bool* b){
    bool temp = *a;
    *a = *b;
    *b = temp;
}
```
  为每个临界资源设置共享布尔变量lock，初值为false，再设置一个局部变量key用于和lock交换信息，当进入临界区前首先使用swap交换lock和key的内容并检查key的状态，当进程在临界区时重复交换和检查直至不再占用。利用swap实现进程互斥的算法如下：
```
key = true;
while(key == false){
    swap(&lock, &key);
}
critical section;
lcok = false;
```
硬件方法的优点：适用于任意数目的进程，支持多个临界区或一到多个处理器，仅需为每个临界区设置一个布尔变量；简单且容易验证。
硬件方法的缺点：等待进入临界区需要耗费处理器时间，不能实现让权等待。从等待进程中随机选择进入临界区，可能造成饥饿现象。

2.3.3 信号量Semaphore

信号量可以解决互斥和同步的问题，只能被两个标准的原语wait(s)以及signal(S)访问，记作P操作和V操作。

1.整型信号量

整型信号量用于表示资源数目，wait和signal操作可描述为：

wait(S){
    while(s<=0);
    S = S-1;
}

signal(S){
    S = S+1;
}

只要信号量小于等于0则不断测试，因此不遵循“让权等待”，而是出于“忙等”状态。

2.记录型信号量

除了整数变量value外再增加一个进程链表L来链接所有等待该资源的进程。

//信号量实现方式
typedef struct{
    int value;
    struct process *L;
} semaphore;

//P和V操作
void wait(semaphore S){
    --S.value;
    if(S.value<0){
        /* add this process to S.L; */
        block(S.L);
    }
}

void signal(semaphore S){
    ++S.value;
    if(S.value<=0){
        /* remove process P from S.L; */
        wakeup(P);
    }
}

wait中减少value表示进程请求一个此类资源，value小于0则表示该类资源分配完毕，应该调用block原语进行阻塞，放弃处理器并将该进程插入到等待队列S.L中，实现了“让权等待”。

signal表示释放资源，使系统中可供分配的该类资源数目+1，若增加后仍然非正，则表示还有等待该资源的进程在S.L中，因此需要调用wakeup原语将链表中第一个的进程P唤醒。

3.利用信号量实现同步

设信号量初值为0

P操作为Passeren，即通过；V操作为vrijgeven，即释放。二者成对出现，与wait-signal等价。P减V加，wait减signal加。

semaphore S = 0;

//单纯P2等待P1的情况

P1(){
    ...
    x;
    V(S);   //用信号量表示x已经运行完毕
    ...
}

P2{
    ...
    P(S);   //检查P1是否运行完x，未完成则P2处于阻塞队列，否则移入就绪队列
    y;
    ...
}

4.利用信号量实现进程互斥

设信号量初始值为1（可用资源数为1）

semaphore S = 1;
P1(){
    ...
    P(S);
    ciritical section of P1;
    V(S);
    ...
}

P2(){
    ...
    P(S);
    critical section of P2;
    V(S);
    ...
}

信号量与同步互斥的总结

同步问题中，若某个行为需要使用资源，则在那个行为之前先P一下；若某个行为会提供某个资源，则在那个行为之后V一下
互斥问题中，需要将临界段加入P和V之间，中间不能有冗余代码。

5.利用信号量实现前驱关系

为保证按照某个图的执行顺序进行程序执行，可以将信号量设为0，并按照同步的方法，前一个V->后一个P逐个向后。

注意：有几个两两之间的进程传递关系则创建几个信号量，且P和V需要成对出现。

semaphore s12=s13=s24=s25=s36=s46=s56=0;

S1(){
    ...
    V(s12);  //V通S2
    V(s13);  //V通S3
}

S2(){
    P(s12);  //P检查S1
    ...
    V(s24);
    V(s25);
}

S3(){
    P(s13);
    ...
    V(s36);
}

S4(){
    P(s24);
    ...
    V(s46);
}

S5(){
    P(s25);
    ...
    V(s56);
}

S6(){
    P(s36);
    P(s46);
    P(s56);
    ...
}

6.分析进程同步和互斥问题的方法步骤

关系分析：进程数、同步和互斥关系
整理
设置信号量

2.3.4 管程monitor

1. 管程定义

系统中的硬软件资源都可以使用数据结构抽象描述而忽略实现细节。管程则是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块：这组操作初始化并改变管程中的数据和同步进程。

2. 管程组成

局部于管程的共享结构数据说明
对该数据结构进行操作的一组过程
对局部与管程的共享数据设置初始值的语句

管程实质上是一个抽象类，其中有多个成员变量，系统中任何设备都可以通过这几个成员变量区分和描述；管程中还有对这些成员变量操作的一组成员函数。

2.3.5 经典同步问题

1.生产者-消费者问题

生产者和消费者进程共享一个初值为空、大小为n的缓冲区。

只有缓冲区未满时，生产者将消息放入缓冲区，否则等待；
只有缓冲区非空时，消费者才能从中取出消息，否则等待。

semaphore muted = 1;   //临界区互斥量
semaphore empty = n;   //空闲缓冲区
semaphore full = 0;    //缓冲区初始化为空

producer(){
    while(1){
        produce an item in nextp;
        P(empty);  //P一下empty，获取空缓冲单元
        P(mutex);  //进入临界区
        add nextp to buffer;  //数据入缓冲区
        V(mutex);  //离开临界区，释放互斥量
        V(full);   //满缓冲区信号量+1
    }
}

consumer(){
    while(1){
        P(full);   //获取满缓冲区单元
        P(mutex);  //进入临界区
        remove an item from buffer;  //取走数据
        V(mutex);  //离开临界区，释放互斥量
        V(empty);  //空缓冲区信号量+1
        consume the item；  //消费数据
    }
}

empty为n，表示如果多次运行producer，在P了n次empty之后保证进入等待。

full为0，表示一开始运行consumer一定会处于等待，直到运行producer直到V到了这个full。

mutex为1，即标准的互斥信号量，保证只有一个程序进入临界段。

示例：父母子女，苹果橘子
该问题的特点：盘子只有一个，则写入不必独占，因此不必加入进入临界的互斥量。

semaphore plate=1, apple=0, orange=0;
dad(){
    while(1){
        prepare an apple;
        P(plate);
        put apple in plate;
        V(apple);
    }
}

mom(){
    while(1){
        prepare an orange;
        P(plate);
        put orange in plate;
        V(orange);
    }
}

son(){
    while(1){
        P(apple);
        pick apple from plate;
        V(plate);
        eat apple;
    }
}

daughter(){
    while(1){
        P(orange);
        pick orange form plate;
        V(plate);
        eat orange;
    }
}

2. 读者-写者问题

读者和写者共享一个文件，允许两个以上的读进程访问共享数据，但不允许某个写进程和其它任何进程同时访问共享数据，也就是独占写、共享读。

int count = 0;       //记录读者量
semaphore mutex = 1; //保护更新count时处于互斥
semaphore rw = 1;    //保证读者和写者互斥

writer(){
    while(1){
        P(rw);        //阻止读
        writing;
        V(rw);        //允许读
    }
}

reader(){
    while(1){
        P(mutex);       //保证独占写count
        if(count == 0)  //当第一个读进程开始读就要
            P(rw);      //阻止写
        ++count; 
        V(mutex);       //释放count
        
        reading;

        P(mutex);       //独占count
        --count;        //读完后读者数-1
        if(count == 0)  //确保想读的全部读完才让写
            V(rw);      //允许写
        V(mutex);       //释放count
    }
}

mutex保证读者和读者之间的count被独占修改（写者只对是否写入负责），因此count的变动和检查都需要P一下mutex，完成后V。

只要有一个读进程运行，写进程则一直处于循环等待状态，因此只要有一个读，就不能写，容易导致写进程饿死。

一种改进是写进程优先：只要有写进程运行就让给写进程，则需要在甲一组信号量w用于实现。

int count=0;
semaphore mutex=1;
semaphore rw=1;
semaphore w=1;

writer(){
    while(1){
        P(w);
        P(rw);
        writing;
        V(rw);
        V(w);
    }
}

reader(){
    while(1){
        P(w);  //其他读进程在写时等待
        P(mutex);
        if(count == 0)
            P(rw);
        ++count;

        V(mutex);
        V(w);  //一个读进程开始时立即释放，保证写进程可以进入

        reading;

        P(mutex);
        --count;
        if(count==0)
            V(rw);
        V(mutex);
    }
}

写进程并非完全优先，因此更准确称为读写公平法。

3. 哲学家进餐问题

两个哲学家之间放着一个筷子，当需要进餐时，需要拿起左右两根才能开始，否则等待。

假设问题中有五个哲学家：

semaphore chopstick[5] = {1,1,1,1,1}; //互斥量
process(){
    do{
        P(chopstick[i]);       //取左边
        P(chopstick[(i+1)%5]); //取右边
        eat;
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        think;
    }whilel(1);
}

问题在于，如果同时发生取左边筷子的情况，则所有人都只拿到左边而不放回，产生死锁，因此一种解决方式为：

对哲学家也进行编号，奇数哲学家拿走左边筷子，偶数哲学家拿走右边筷子。

或者：直接将拿走两个筷子的行为设为独占，每次只允许一个哲学家同时拿走左边和右边两个筷子：

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1; //互斥为1，保证独占拿走

process(){
    while(1){
        P(mutex);
        P(chopstick[i]);
        P(chopsitck[(i+1)%5]);
        V(mutex);
        eat;
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        think;
    }
}

不同于贪心算法，解决该类问题必须考虑下一步更下一步的后果。

4. 吸烟者问题

供应者不断提供抽烟者所需的三种材料，三个抽烟者分别拥有其中的一种材料。每个吸烟者需要同时获得三种才能吸烟；但供应者每次只放两种材料在桌上。当拥有某种材料的吸烟者完成抽烟给供应者一个信号，则供应者提供给另外两个吸烟者的材料搭配。

int random;
semaphore offerBC = 0;  //组合B&C，供A抽烟
semaphore offerAC = 0;  //组合A&C，供B抽烟
semaphore offerAB = 0;  //组合A&B，供C抽烟

process Producer(){
    while(1){
        random = rand()%3;
        if(random==0)
            V(offerBC);
        else if(random==1)
            V(offerAC);
        else
            V(offerAB);
        P(finish);    //等待抽烟完成
    }
}

process PA(){
    while(1){
        P(offerBC);
        smoke;
        V(finish);
    }
}

process PB(){
    while(1){
        P(offerAC);
        smoke;
        V(finish);
    }
}

process PC(){
    while(1){
        P(offerAB);
        smoke;
        V(finish);
    }
}

2.4 死锁

2.4.1 概念

1. 定义

多个进程因竞争资源而造成的互相等待，若无外力作用则这些进程都无法向前推进。

2. 产生原因

系统资源的竞争（不可剥夺的资源的竞争）
进程推进顺序非法（循环等待）
四个必要条件：
- 互斥：一段时间内某资源仅被一个进程占有
- 非剥夺：进程未完成时，资源不会被其他进程夺走（只能主动释放）
- 请求和保持：进程已经请求并保持到了一个资源，但需要继续请求其他被占有的资源
- 循环等待：存在循环等待链

2.4.2 死锁处理

死锁预防：限制某些限制条件破坏四个必要条件之一。
死锁避免：分配资源时防止系统进入不安全状态。
死锁检测和解除：允许发生死锁，但是可以检测到并解除之。

对比

2.4.3 死锁预防

破坏互斥条件：由于大多数资源只能独占访问，破坏互斥不太可行。
破坏不剥夺条件：使已经保持了某个资源的进程在无法取得新的资源时释放已有的资源。实现比较复杂，系统开销大，适用于易保存和恢复的资源，如CPU寄存器、内存资源
破坏请求和保持条件：预先采用静态分配方法，在运行前一次申请所有所需资源，未成功则等待，取得后一直独占且不提出其他请求。实现简单，但浪费系统资源，易导致其他进程饥饿。
破坏循环等待条件：采用顺序资源分配法，为资源编号，规定每个进程必须按照编号顺序请求资源且一次申请完同类资源。（申请Ri后只能申请标号大于i的其他资源）。要求编号稳定，因而限制了新设备的增加开销。

2.4.4 死锁避免

死锁避免也是事先预防，但不会实现采取限制，而是在资源动态分配时防止系统进入不安全状态。限制条件比死锁预防弱。

1.安全状态

安全状态指系统可以按某种顺序推进程序，为每个进程分配所需资源直到满足每个进程的最大需求，每个进程都可以按顺序完成。此时称进程序列P1，P2...Pn为安全序列。如没有安全序列，则系统不安全。（不安全未必死锁，但安全一定不死锁）

2.银行家算法

把操作系统看作银行家，资源为所管理的资金，请求资源相当于贷款。每次请求资源需要测试想最大需求量，若现存资源可以满足则分配，否则推迟分配。

数据结构：（假设m类资源，n个进程）
- 可利用资源矢量Available：含有m个元素的数组，Available[k]代表资源k的可用数目
- 最大矩阵需求Max：nxm矩阵，定义了系统中每类资源分配给各进程对m类资源的最大需求，Max[i,j]代表进程i对资源j的最大需求。
- 分配矩阵Allocation：和Max同型，用来表示当前分配给各进程的各类资源数目。
- 需求矩阵Need：和Max同型，用来表示各进程还需要的各类资源需求数目。易得Need=Max-Allocation
算法描述
- 每个进程都可以发送请求矢量Request_i，表示对每类资源的需求量。如Request_i[j] = K
- Request_i[j] <= Need[i, j]：进入下一步，否则错误：需求超过应需求量。
- Request_i[j] <= Available[j]：进入下一步，否则等待：系统没有足够资源。
- 系统尝试分配资源给进程P_i，并更新以下数值：
```
Avaliable = Available - Request_i;
Allocation[i, j] = Allocation[i, j] + Request_i[j];
Need[i, j] = Need[i, j] - Request_i[j];
```
- 系统执行安全性算法，检测系统在该次分配后是否出于安全状态，否则将本次尝试作废，并让Pi等待。
安全性算法
- ① 初始状态：安全序列为空
- ② 从Need中找出对应进程不在安全序列 && 该行小于等于Available的行，并将该行对应进程Pi加入安全序列，找不到则进入④
- ③ Pi进入安全序列后就可以执行直到完成，并释放出所分配的资源，执行：Available = Available + Allocation[i];返回②
- ④ 如果安全序列中有所有进程，则系统处于安全状态，否则不安全。

2.4.5 死锁检测和解除

该算法最为宽松，在分配资源时不采取任何措施，但可以在运行时检测并解除死锁。

1.资源分配图

系统死锁可以使用资源分配图描述。圆圈代表一个进程，框代表一类资源，框中的一个点表示一类中的一个资源，从资源到进程的边称为分配边，表示该资源已经有一个资源被分配给了此进程。

2.死锁定理

在资源分配图中，找出既不阻塞又不是孤点的进程Pi（有一条有向边与其相连，且该有向边对应的资源申请数小于等于已有的空闲资源），若所有连接该进程的边都满足上述条件，则该进程可以运行直到完成释放资源。此时可以消去该进程的所有有向边，使其孤立。
注意：判断资源是否有空间，应该用资源总数减去资源分配图中的“出度”
消去某个进程的边后，如果可以循环该过程消去所有进程的边，则称该图是完全可简化的。

死锁定理：当且仅当资源分配图不可完全简化。

3.死锁解除

资源剥夺法：挂起死锁进程并抢占资源，将这些资源分配给其他进程，但应防止被挂起进程饿死
撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源，撤销的原则可以按进程优先级和撤销进程的代价高低进行。
进程回退法：让一个或多个进程回退到回避死锁的地步（资源释放资源而不是被剥夺），要求系统可以设置还原点。