2020-计算机操作系统-Lecture6-并发程序设计

Lecture6-并发程序设计

1. 并发进程

1.1. 顺序程序设计

1.1.1. 程序与顺序性

1. 程序是实现算法的操作(指令)序列
2. 程序顺序执行是指其在处理器上执行是严格有序的，前一个操作被执行完后，才能开始后继操作，被称为程序执行的内部顺序性
3. 把一个具体问题的求解过程设计成一个程序或者若严格顺序执行的程序序列，这称为程序执行的外部顺序性

1.1.2. 顺序程序设计的特性

1. 程序执行的顺序性：程序指令执行是严格按序的，每个操作必须在下一个操作开始前结束。
2. 计算环境的封闭性：程序运行时如同独占受操作系统保护的资源，资源状态只能由程序本身决定和改变，不受外界因素改变。
3. 计算结果的确定性：程序执行结果与执行速度和执行时段无关
4. 计算过程的可再见性：程序对相同数据集的执行轨迹是确定的

1.1.3. 顺序程序执行程序例子

1. 循环地(从输入机读78秒再计算52秒再向磁带机输出20秒)按照顺序程序设计方法，设计成如下一个程序：

2. 处理器利用率:$\frac{52}{78 + 52 + 20} \approx 34.7\%$

1.2. 无关与交往的并发进程

1. 无关的并发进程：一组并发进程分别在不同的变量集合上运行，一个进程的执行与其他并发进程的进展无关
2. 交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果

1.3. 并发程序设计

1.3.1. 程序并发执行

1. 程序并发执行是指一组程序的执行在时间上是重叠的，所谓重叠的是指一个程序执行第一条指令是在另一个程序执行完最后一条指令之前开始的。
   1. 宏观上，并发性反应了一个时间段内有几个程序都处于运行但运行尚未结束的状态。
   2. 微观上，任一时刻都只有一个程序在运行。
2. 并发实质是处理器在几个程序之间的多路复用，对有限物力资源强制行使多用户共享，消除计算机部件之间的互等现象，提高资源利用率。
3. 并发使得程序失去了封闭性、顺序性、确定性和可再现性。
4. 并发程序设计指一个程序被设计成可以与其他程序并发执行。

1.3.2. 并发程序设计例子

换一种设计思路，设计3个独立运行的程序，让它们同时进入多道程序系统去并发执行

while(1) { input，send }
while(1) { receive，process，send }
while(1) { receive，output }

1. 处理器利用率$=\frac{52 * n}{78 * n + 52 + 20}$
2. 计算一定是在接收结束之后的，$\lim\limits_{n\rightarrow \infty}\frac{52 * n}{78 * n + 52 + 20} \approx 66.7\%$后，利用率会大大提高。

1.3.3. 并发程序设计的特性

1. 并行性：多个进程在多道程序系统中并发执行或者在多处理器系统中并行执行，提高了计算效率
2. 共享性：多个进程共享软件资源
3. 交往性：多个进程并发执行时存在制约，增加了程序设计的难度

1.3.4. 进程的无关性

进程的无关性是进程的执行与时间无关的一个充分条件

1.3.4.1. Bernstein条件

$R(P_i)={a_{i1},a_{i2},..., a_{in}}，程序P_i在执行期间引用的变量集\\ W(P_i)={b_{i1},b_{i2},...,b_{im}}，程序P_i在执行期间改变的变量集$

若两个进程的程序$P_1$和$P_2$能满足Bernstein条件，即满足：$R(P_1)\cap W(P_2) \cup R(P_2) \cap W(P_1) \cup W(P_1) \cap W(P_2) = \emptyset$则并发进程的执行与时间无关，保持封闭性和可再现性。

1. $R(P_1)\cap W(P_2) \cup R(P_2) \cap W(P_1)$，表明一个程序在两次读操作之间存储单元的数据不会被改变。
2. $W(P_1) \cap W(P_2)$：表明程序的写操作结果不会丢失。

1.3.4.2. Bernstein条件例子

1. 例如，有如下分属四个进程中的四条语句：

S1: a := x + y
S2: b := z + 1
S3: c := a – b
S4: w := c + 1

1. 于是有:
   1. $R(S1)=\{x,y\} , R(S2)=\{z\}, R(S3)=\{a,b\}, R(S4)=\{c\}$
   2. $W(S1)=\{a\}, W(S2)=\{b\} , W(S3)=\{c\} , W(S4)=\{w\}$
2. $S_1$和$S_2$可并发执行，满足Bernstein条件
3. 其他语句并发执行可能会产生与时间有关的错误

1.3.5. 并发程序设计的优点

1. 单处理器系统：有效利用资源，让处理器和设备、设备和设备同时工作，充分发挥硬件设备的并行工作能力。
2. 多处理器系统：让进城在不同处理器上物理地并行工作，加快计算速度。
3. 简化程序设计：编写并发执行的小程序进度较快，更容易保证正确性。

1.4. 顺序程序设计与并发程序设计

1.5. 与时间有关的错误

1. 对于一组交往的并发进程，执行的相对速度无法相互控制
2. 如果程序设计不当，可能出现各种"与时间有关的"错误
   1. 表现一：结果不唯一，不同的执行序列有不同的结果。
   2. 表现二：永远等待

1.5.1. 结果错误：机票问题

1. 每两条机器指令之间都存在着一定的时间缝隙，导致时间片轮转可能导致的抢占问题。
2. 时间片轮转调度，如果并发数足够高，那么可能导致一张票被非常多的人抢到。
3. 此时出现把同一张票卖给两个旅客的情况，两个旅客可能各自都买到一张同天同次航班的机票，可是，Aj的值实际上只减去1，造成余票数不正确。特别是，当某次航班只有一张余票时，可能把一张票同时售给两位旅客。

1.5.2. 永远等待：内存管理问题

1. 由于borrow和return共享代表主存物理资源的临界变量X，对并发执行不加限制会导致错误。
2. 例如
   1. 一个进程调用borrow申请主存，在执行比较B和X大小的指令后，发现B>X，但在执行{进程进入等待主存资源队列}前
   2. 另一个进程调用return抢先执行，归还所借全部主存资源
   3. 这时，由于前一个进程还未成为等待者，return中的{释放等主存资源进程}相当于空操作，以后当调用borrow的应用进程被置成{等主存资源}时，可能己经没有其他进程再来归还主存，从而，申请资源的进程处于永远等待状态

1.6. 进程的交互：竞争(互斥)和协作(同步)

1. 因此，交互的并发进程在执行时必须进行制约，才能保证得到合理的结果

1.6.1. 进程互斥(竞争)

1. 并发进程之间因相互争夺独占性资源而产生的竞争制约关系
2. 一个进程的执行可能影响到同其竞争资源的其他进程，如果两个进程要访问同一资源，那么，一个进程通过操作系统分配得到该资源，另一个将不得不等待。
3. 进程互斥是解决进程间竞争关系(间接制约关系)的手段。
4. 进程互斥指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源

1.6.1.1. 竞争带来的问题

1. 资源竞争的两个控制问题：
   1. 一个是死锁(Deadlock)问题: 一组进程如果都获得了部分资源，还想要得到其他进程所占有的资源，最终所有的进程将陷入死锁。
   2. 一个是饥饿(Starvation)问题: 一个进程由于其他进程总是优先于它而被无限期拖延，可以使用FCFS来解决饥饿问题。
2. 操作系统需要保证诸进程能互斥地访问临界资源，既要解决饥饿问题，又要解决死锁问题

1.6.1.2. 竞争关系:死锁

1. 临界资源：互斥使用的资源
2. 死锁: 一组进程因争夺资源陷入永远等待的状态
3. P0和P1两个进程，均需要使用S和Q两类资源，每类资源数为1
   1. P0：申请(S) -> 申请(Q) -> 释放(S) -> 释放(Q)
   2. P1：申请(Q) -> 申请(S) -> 释放(Q) -> 释放(S)
   3. 以上两个进程互相持有对方的资源的锁，导致无法继续进行。

1.6.2. 进程同步(协作)

1. 并发进程之间为完成共同任务基于某个条件来协调执行先后关系而产生的协作制约关系
2. 某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协调各自的工作。当合作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后方被唤醒并继续执行
3. 是解决进程间协作关系(直接制约关系)的手段。
4. 进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于另一个协作进程的消息或信号，当一个进程没有得到来自于另一个进程的消息或信号时则需等待，直到消息或信号到达才被唤醒
5. 同步和异步
   1. 同步：等待/阻塞
   2. 异步：不等/平行
6. 进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调

1.6.3. 并发进程之间的关系

1.6.4. "忙式等待"方法解决临界区调度的缺点

1. 临界区管理的简单方法
   1. 关中断
   2. 测试并建立指令
   3. 对换指令
   4. Peterson算法
2. 存在问题
   1. 对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间
   2. 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重用户编程负担
3. 通用的解决方法：信号量与PV操作

1.6.5. 并发进程设计控制

2. 临界区

2.1. 互斥与临界区

1. 临界资源：互斥共享变量所代表的资源，即一次只能被一个进程使用的资源
   1. 举例: 火车上的卫生间就是一种互斥使用的共享资源
   2. 使用共享变量代表共享资源
2. 临界区(critical section)：并发进程中与互斥共享变量相关的程序段，与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预见
3. 多个并发进程访问临界资源时，存在竞争制约关系，如果两个进程同时停留在相关的临界区内，就会出现与时间相关的错误
4. 竞争条件(race condition)
5. 调度原则：
   1. 互斥使用，有空让进
   2. 忙则要等，有限等待
   3. 择一而入，算法可行(避开饥饿)

2.2. 临界区的描述

1. 确定临界资源：shared <variable>
2. 确定临界区：region <variable> do < statement_list>
3. 两个进程的临界区有相同的临界资源，就是相关的临界区，必须互斥进入
4. 两个临界区不相关，进入就没有限制

2.3. 临界区管理的三个要求(Dijkstra, 1965)

1. 一次至多一个进程能够进入临界区内执行：在某些特殊情况下可能会突破
2. 如果已有进程在临界区，其他试图进入的进程应等待
3. 进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入

2.4. 临界区的使用

2.5. 临界区的嵌套使用

2.6. 临界区管理实现的尝试

2.6.1. 临界区管理：尝试一，进程均可进入

1. 存在的问题: 两个进程可能都进去
2. 进程P1测试inside2与随后置insidel之间(由于时间片轮转等诸多原因)，P2可能发现inside1有值false，于是它将置inside2为true，并且与进程P1同时进入临界区，而对于P2而言也是同理的

2.6.2. 临界区管理：尝试二，进程均不可进入

1. 优先表示自己在临界区内，存在的问题: 两个进程都进不去
2. 延迟进程P2对inside2的测试，先置inside1为true，用以封锁P2，但是有可能每个进程都把自己的标志置成true，从而出现死循环，这时没有进程能在有限时间内进入临界区，造成永远等待。

2.6.3. 解决思路

1. 问题：框内的(测试锁、建立锁)两条指令执行过程不能中断

2.6.4. 解决算法：peterson算法

1. 通用性和效率比较差

// 公共的变量声明部分
bool inside[2];      // 存储是否进入的情况
inside[0] = false;
inside[1] = false;
enum{0, 1} turn;     // 指示器turn来指示可以由哪个进程进入

上图中的绿色箭头可以理解为激活和唤醒
下图中展示了一种修改方案：这种修改是不可行的。

1. P0中执行了turn=1, 暂时进不去
2. 等P1中执行turn=0, P0可以进去
3. P0使用完临界区，退出临界区的时候，将turn=0(好像是多余的)，此时P1还是进不去，要等p0执行turn=1，使得P1有机会进入临界区
4. 之后，P1退出临界区的时候，turn=1，P0暂时进不去，等在P1中执行turn=0，P0可以再次进入临界区
5. 因此，P0和P1使用临界区的次序变成了完全一比一的交替方式，这只能是临界区互斥使用的一个特例，不能满足临界区互斥使用的完全随机性。

3. 临界区管理实现的硬件方式

3.1. 关中断

1. 实现互斥的最简单方法：进程进入临界区时关中断，进程退出临界区时开中断。
2. 关中断后，时钟中断也会被屏蔽，进程上下文切换完全由中断事件引起。
3. Linux关中断:cli()，开中断:sti()
4. 关中断适用场合

3.1.1. 关中断方法优点

简单、有效，队操作系统自身很有用。

3.1.2. 关中断方法的缺点

1. 关中断时间过长影响性能和系统效率
2. 不适用于多处理器系统

3.2. 测试并建立指令

TS(Test and Set)指令的处理过程：返回条件码

bool TS(bool &x) {
   if(x) {
      x = false;
      return true;
   }
   else
      return false;
}
//TS指令实现进程互斥
bool lock=true;
cobegin
process Pi() {          //i=1,2,...,n
   while(!TS(lock));    //上锁
   {/*临界区*/};
   lock=true;           //开锁
}
coend

3.3. 对换指令

对换质量是交换两个字的值

void SWAP(bool &a, bool &b) {
   bool temp=a;
   a=b;
   b=temp;
}
//对换指令实现进程互斥
bool lock=false;
cobegin
Process Pi(){           //i=1,2,...,n
   bool keyi=true;
   do{
      SWAP(keyi,lock);
   }while(keyi);        //上锁
   /*临界区*/
   SWAP(keyi,lock);     //开锁
}
coend

3.4. 实现临界区管理的硬件设施

1. TS和swap指令均是忙式等待，效率低
2. 简单的解决办法是在进出临界区时开关中断，这样临界区执行就不会中断了，执行就有原子性
   1. 关中断
   2. 临界区
   3. 开中断
3. 操作系统原语就采用这种实现思路
4. 但是，临界区的指令长度应该短小精悍，这样才能保证系统效率
5. 不建议用户程序使用，滥用是可怕的！

4. 信号量

4.1. 问题的提出

1. TS或swap指令管理临界区，采用忙式轮询，效率低
2. 关开中断管理临界区，不便交给用户程序使用
3. 参考：操作系统访问硬件资源时采用"请求-等待-中断恢复"方式

4.2. 同步和同步机制

1. 著名的生产者-消费者问题是典型的进程同步问题。
2. 为什么count的值是不确定的，因为我们并没有对count进行封锁(同步)
3. 课本134页

4.3. 信号量与PV操作的数据结构与原语操作

1. 信号量：一种可动态定义的软件资源。
2. 信号量是一种变量类型，有两个分量，一个是信号量的值，另一个是信号量队列指针。
3. 信号量分类
   1. 按照用途：
      1. 公用信号量：联系一组并发进程，相关进程均可在此信号量上执行PV操作，初值为1，实现进程互斥。
      2. 私有信号量：联系一组并发进程，仅允许此信号量所拥有的进程执行P操作，其他相关进程可以在其上执行V操作，初值为0或正整数，多用于进程同步
   2. 按照取值
      1. 二值信号量：值为0或1，用于解决互斥问题。
      2. 一般信号量(计数信号量)，允许大于1的整数值，主要解决进程同步。

4.3.1. 一般信号量数据结构定义

1. 设s为一个记录型数据结构，一个分量为整型量value，另一个为信号量队列queue, P和V操作原语定义：
   1. P(s)：
      1. 将信号量s减去1，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态
      2. 负数的绝对值就是等待的进程的个数
   2. V(s)：将信号量s加1，若结果不大于0，则释放(唤醒)一个等待信号量s的进程，使其转换为就绪态
   3. 原语：CPU处于内核态，在关中断环境下执行的一段指令序列
2. 原子性：不被中断，确保安全且完整执行这段指令序列

3. 强调：对于信号量，只允许使用P和V原语操作访问信号量，不能直接对信号量的整型值做读写操作，也不能直接对信号量的队列做任何其他操作

4.3.2. PV原语操作含义及其伪代码

// 基本数据结构定义
typedef struct semaphore {
   int value;           /*信号量值，正值表示资源可复用次数，0值表示无资源且无进程等待，负数的绝对*/
   struct pcb* list;    /*信号量队列指针，等待队列*/
};
// P操作原语
void P(semahore s) {
   s.value--;           /* 信号量值减1 */
   if(s.value < 0)
      sleep(s.list);
   /* 若信号量值小于0,执行P操作的进程调用sleep(s.list)阻塞自己，被置成等待信号量s状态并移人s信号量队列,转向进程调度程序*/
}
// V操作原语
void V ( semaphore s) {
   s.value++;           /* 信号量值加 1*/
   if(s.value <=0)
      wakeup(s.list) ;
   /*若信号量值小于等于0,则调用wakeup(s. list) 从信号量s队列中释放一-个等待信号量s的进程并转换成就绪态,进程则继续执行*/  
}
// PV操作解决进程互斥问题框架
semaphore s;
s = 1;
cobegin
   process Pi {
      ……
      P(s);
      临界区;
      V(s);
      ……
   }
coend;

4.3.3. 补充：二值信号量数据结构定义

1. 设s为一个记录型数据结构，一个分量为整型量value，仅能取值0或1，另一个为信号量队列queue, P和V操作原语定义：

typedef struct binary_semaphore{
   int value;           // 取值为0或1
   struct pcb * list;   // 等待队列
};
void BP(binary_semaphore s){
   if(s.value == 1){
      s.value = 0;
   }else{
      sleep(s.list);
   }
}
void BV(binary_sempahore s){
   if(s.list is empty()){
      s.value = 1;
   }else{
      wakeup(s.list);
   }
}

4.3.4. 信号量与PV操作管理临界资源的的举例(火车上的卫生间)

4.4. 信号量与进程状态转化模型及其队列模型

4.4.1. 信号量与进程状态转换模型

4.4.2. 信号量与进程状态转换模型(队列模型)

4.5. 信号量与PV操作的推论

1. 推论1：若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作次数、亦等于s所代表的实际还可以使用的物理资源数
2. 推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数
3. 推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源；在一定条件下，P操作代表阻塞进程操作，而V操作代表唤醒被阻塞进程的操作

4.6. 信号量的应用

4.6.1. 信号量程序设计的一般结构

semaphore s=1;
cobegin
Process Pi /* i=1,…,n */
{
   …
   P(s); // 申请进入临界区
   /* critical region 临界区 */
   V(s); // 申请退出临界区
   …
};
coend

1. 说明: 在表达纯粹互斥关系时信号量初值为1，且同一个信号量的P操作和V操作处于同一个进程之中。
2. 但是这种情形不适用于同步关系。
3. 假设有n个进程，则s的取值范围为[1-n, 1]

4.6.2. 信号量与PV操作控制并发进程之间的临界资源

4.7. 求解互斥问题

4.7.1. 飞机票问题

Var A : ARRAY[1..m] of integer;
   mutex : semaphore;
   mutex:= 1;
cobegin
process Pi
   var Xi:integer;
begin
   L1:
      按旅客订票要求找到A[j];
      P(mutex);
      Xi := A[j];
      if Xi>=1 then
         begin
            // 如果售票成功，在if内释放信号量
            Xi:=Xi-1;
            A[j]:=Xi;
            V(mutex);
            {输出一张票};
         end;
      else
         begin
            // 如果票不足，则跳出后释放信号量
            V(mutex);
            {输出"票已售完"};
         end;
      goto L1;
   end;
coend

1. P操作和V操作在执行路径上一一匹配。
2. 只有相同航班的票数才是相关的临界资源，所以用一个信号量处理全部机票会影响进程并发度。
3. 下面的例子是将不同航班的信号量分开：

Var A : ARRAY[1..m] of integer;
   s : ARRAY[1..m] of semaphore;
   s[j] := 1;
cobegin
process Pi
   var Xi:integer;
begin
   L1:
      按旅客定票要求找到A[j];
      P(s[j]);
      Xi := A[j];
   if Xi>=1 then
      begin
         Xi:=Xi-1;A[j]:=Xi;
         V(s[j]); {输出一张票};
      end;
   else
      begin
         V(s[j]); {输出"票已售完"};
      end;
   goto L1;
end;
coend

4.7.2. 哲学家就餐问题

1. 问题描述：有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子
2. Dijkstra最早设计了哲学家就餐问题，哲学家顺时针编号

// 存在死锁的哲学家就餐问题
semaphore fork[5];
for (int i=0;i<5;i++)
   fork[i]=1;
cobegin
   process philosopher_i( ) { //i= 0,1,2,3,4
      while(true) {
         think();
         P(fork[i]); //先取右手的叉子
         P(fork[(i+1)%5]); //再取左手的叉子
         eat();
         V(fork[i]);
         V(fork[(i+1)%5]);
      }
   }
coend

1. 上面的代码存在死锁的问题：特殊的执行轨迹比如每一个哲学家都拿到了一侧的叉子
2. 上述解法可能出现永远等待，有若干种办法可避免死锁
   1. 至多允许四个哲学家同时取叉子 (C. A. R. Hoare方案)
   2. 奇数号先取左手边的叉子，偶数号先取右手边的叉子

4.7.2.1. 至多允许四位哲学家同时取叉子

// 设置侍者，添加房间信号量来控制同时取叉子的哲学家个数。
semaphore fork[5];
   for (int i=0;i<5;i++)
      fork[i]= 1;
      semaphore room=4; //增加一个侍者，设想有两个房间1号房间是会议室，2号房间是餐厅
cobegin
process philosopher_i(){/*i=0,1,2,3, 4 */
      while(true) {
         think();
         P(room); //控制最多允许4位哲学家进入2号房间餐厅取叉子
         P(fork[i]);
         P(fork[(i+1)%5] ) ;
         eat();
         V(fork[i]);
         V(fork[(i+1) % 5];
         V(room);
      }
   }
coend

4.7.2.2. 限制奇数哲学家优先取左手，偶数哲学家优先取右手

// 限制奇数哲学家优先取左手，偶数哲学家优先取右手
void philosopher (int i){
   if i mod 2 == 0 then{
      P(fork[i]);             //偶数哲学家先右手
      P(fork[(i+1) mod 5]);   //后左手
      eat();
      V(fork[i]);
      V (fork[(i+1) mod 5]);
   }
   else{
      P (fork[(i+1) mod 5]);  //奇数哲学家，先左手
      P (fork[i]);            //后右手
      eat();
      V(fork[(i+1) mod 5]);
      V(fork[i]);
   }
}

4.8. 求解同步问题

1. 进程同步：并发进程为完成共同任务基于某个条件来协调执行先后关系而产生的协作制约关系
2. 一个进程的执行等待来自于其他进程的消息
3. 解决的基本思路
   1. 定义一个信号量：其数值代表可用消息数
   2. 等待消息进程：执行P，无消息则等待
   3. 发出消息进程：执行V，有等待进程则释放

4.8.1. 生产者与消费者

1. 问题描述：有$n$个生产者和$m$个消费者，连接在一个有$k$个单位缓冲区的有界缓冲区上。其中，生产者进程$Producer_i$和消费者进程$Consumer_j$都是并发进程
   1. 只要缓冲区未满，生产者$Producer_i$生产的产品就可投入缓冲区
   2. 只要缓冲区不空，消费者进程$Consumer_j$就可从缓冲区取走并消耗产品可能情形:
      1. $n=1, m=1, k=1$
      2. $n=1, m=1, k>1$
      3. $n>1, m>1, k>1$

4.8.1.1. 一个生产者、一个消费者、一个缓冲单元

1. 生产者和消费者共享缓冲区
   1. 缓冲区有空位时，生产者可放入产品，否则等待
   2. 缓冲区有产品时，消费者可取出产品，否则等待

2. 解决思路
   1. 同步关系1：消费者一开始在等待产品到来，考虑设置一个信号量(等待产品)；一开始无产品，初值为0
   2. 同步关系2：消费者则在等待缓冲区中有空位，也可设置一个信号量(等待缓冲区)；一开始缓冲区有空位，初值为1
3. 核心是缓冲区只允许放一个产品

B: integer;          /* 共享缓冲区 */
sput: semaphore;     /* 可以使用的空缓冲区数 */
sget: semaphore;     /* 缓冲区可以使用的产品数 */
sput:=1;             /* 缓冲区内允许放入一件产品 */
sget:=0;             /* 缓冲区内没有产品 */

4.8.1.2. 一个生产者、一个消费者、多个缓冲单元

P操作的次序是重要的可能导致死锁的

B : ARRAY[0..k-1] of integer;
sput: semaphore；       /* 可以使用的空缓冲区数 */
sget: semaphore;        /* 缓冲区内可以使用的产品数 */
sput := k;              /* 缓冲区内允许放入k件产品 */
sget := 0;              /* 缓冲区内没有产品 */
putptr, getptr : integer; putptr:=0; getptr:=0;

4.8.1.3. 多个生产者、多个消费者、多个缓冲单元

如果没有$S_1$、$S_2$的话，在多个生产者和消费者时，对于生产者和消费者序列本身需要用$S_1$、$S_2$控制。

B : ARRAY[0..k-1] OF integer;
sput: semaphore；          /* 可以使用的空缓冲区数 */
sget: semaphore;           /* 缓冲区内可以使用的产品数 */
sput := k;                 /* 缓冲区内允许放入k件产品 */
sget := 0;                 /* 缓冲区内没有产品 */
putptr, getptr : integer;
putptr := 0; getptr := 0;
s: semaphore;              /* 互斥使用putptr, getptr */
s1:= 1; s2:= 1;

4.8.2. 苹果-桔子问题

plate : integer;
sp:semaphore；    /* 盘子里可以放几个水果 */
sg1:semaphore;    /* 盘子里有桔子 */
sg2:semaphore;    /* 盘子里有苹果 */
sp := 1;          /* 盘子里允许放入一个水果*/
sg1 := 0;         /* 盘子里没有桔子 */
sg2 := 0;         /* 盘子里没有苹果*/

4.9. 小结

1965年Dijkstra发明的同步控制的编程方法

5. 并发程序设计习题讲解

5.1. 信号量-前驱关系

Semaphore s1=0; /*表示进程P1是否已经执行完成*/
Semaphore s2=0; /*表示进程P2是否已经执行完成*/
Semaphore s3=0; /*表示进程P3是否已经执行完成*/
Semaphore s4=0; /*表示进程P4是否已经执行完成*/
Semaphore s5=0; /*表示进程P5是否已经执行完成*/
main () {
   cobegin
      P1();
      P2();
      P3();
      P4();
      P5();
      p6();
   coend
}

5.2. 读者/写者问题

1. 读者与写者问题(reader-writer problem) (Courtois, 1971)也是一个经典的并发程序设计问题。有两组并发进程：读者和写者，共享一个文件F，要求：
   1. 允许多个读者可同时对文件执行读操作
   2. 只允许一个写者往文件中写信息
   3. 任意写者在完成写操作之前不允许其他读者或写者工作
   4. 写者执行写操作前，应让已有的写者和读者全部退出
   5. 使用PV操作求解该问题

5.2.1. 读者优先

5.2.2. 信号量解决读者写者问题，写者优先

5.2.3. 写者优先

5.3. 睡眠的理发师问题

1. 理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子
2. 如果没有顾客，理发师便在理发椅上睡觉
3. 一个顾客到来时，它必须叫醒理发师
4. 如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开
5. 使用PV操作求解该问题

int waiting=0;                   //等候理发顾客坐的椅子数
int CHAIRS=N;                    //为顾客准备的椅子数
semaphore customers,barbers,mutex;
customers=0;
// 如果没有顾客，理发师便在理发椅上睡觉 需要叫醒
barbers=0;
mutex=1;

5.4. 农夫猎人问题

1. 有一个铁笼子，每次只能放入一个动物。猎手向笼中放入老虎，农夫向笼中放入羊；动物园等待取笼中的老虎，饭店等待取笼中的羊。请用P、V操作原语写出同步执行的程序
2. 和苹果-桔子问题没有本质区别。

semaphore Scage=1;
semaphore Stiger=0;
semaphore Ssheep=0;

5.5. 银行业务问题

1. 某大型银行办理人民币储蓄业务，由n个储蓄员负责。每个顾客进入银行后先至取号机取一个号，并且在等待区找到空沙发坐下等着叫号。取号机给出的号码依次递增，并假定有足够多的空沙发容纳顾客。当一个储蓄员空闲下来，就叫下一个号。请用信号量和P，V操作正确编写储蓄员进程和顾客进程的程序
2. 类似苹果-桔子

var customer_count, server_count, mutex: semaphore;
customer_count:=0;
server_count:=n;
mutex:=1;

5.6. 缓冲区管理

1. 有n个进程将字符逐个读入到一个容量为80的缓冲区中(n>1)，当缓冲区满后，由输出进程Q负责一次性取走这80个字符。这种过程循环往复，请用信号量和P、V操作写出n个读入进程(P1， P2，…Pn)和输出进程Q能正确工作的动作序列
2. 生产者消费者问题

var mutex,empty,full:semaphore;
count,in:integer
buffer:array[0..79] of char;
mutex=1;empty=80;full=0;
count=0;in=0;

一次性V 80次

5.7. 售票问题

1. 汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好门应通知司机开车，然后售票员进行售票。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应该通知售票员。假定某辆公共汽车上有一名司机与两名售票员，汽车当前正在始发站停车上客，试用信号量与P、V操作写出他们的同步算法

5.8. 吸烟者问题

1. 一个经典同步问题：吸烟者问题(patil，1971)。
2. 三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。试用信号量和P、V操作求解该问题

5.9. 独木桥问题

5.9.1. 独木桥问题1

1. 东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待一方的车全部过完后，另一方的车才允许过桥。请用信号量和PV操作写出过独木桥问题的同步算法。

var wait,mutex1,mutex2:semaphore; 
mutex1:=mutex2:=1;wait:=1; 
count1,count2:integer;
count1:=count2:=0;

5.9.2. 独木桥问题2

1. 在独木桥问题1中，限制桥面上最多可以有k辆汽车通过。试用信号量和P，V操作写出过独木桥问题的同步算法

semaphore wait,mutex1,mutex2,bridge;
mutex1=mutex2=1;
bridge=k;wait=1;
int count1,count2;
count1=0;count2=0;

5.9.3. 独木桥问题3

1. 在独木桥问题1中，以3辆汽车为一组，要求保证东方和西方以组为单位交替通过汽车。试用信号量和P，V操作写出汽车过独木桥问题的同步算法

semaphore wait,mutex1,mutex2;
mutex1=mutex2=1;wait=1;
int counter1,counter2; counteru1=0; countd1=0; counteru2=0; counterd2=0;
semaphore S1,S2;S1=3;S2=0;

5.9.4. 独木桥问题4

1. 在独木桥问题1中，要求各方向的汽车串行过桥，但当另一方提出过桥时，应能阻止对方未上桥的后继车辆，待桥面上的汽车过完桥后，另一方的汽车开始过桥。试用信号量和P，V操作写出过独木桥问题的同步算法

semaphore stop,wait,mutex1,mutex2;
stop=mutex1=mutex2=1;
wait=1;  
int count1,count2;
count1=0;count2=0;

6. 管程

6.1. 管程和条件变量

1. 管程试图抽象相关并发进程对共享变量访问，以提供一个友善的并发程序设计开发环境。
2. 管程是由若干公共(共享)变量及其说明和所有访问这些变量的过程所组成。
   1. 管程的局部变量只能由该管程的过程读取。
   2. 把分散在各进程中的临界区集中起来进行管理
3. 防止进程有意或无意的违法同步操作，进程只能互斥地调用管程中的过程。
4. 便于用高级语言来书写程序

6.2. 管程定义和属性

1. 管程的定义：管程是由局部于自己的若干公共(共享)变量及其说明和所有访问这些公共变量的过程所组成的软件模块
2. 管程的属性
   1. 共享性：管程中的移出过程可被所有调用管程的过程的进程所共享
   2. 安全性：管程的局部变量只能由此管程内部分访问，不允许进程或其他管程直接访问。
   3. 互斥性：任一时刻，共享资源的进程可以访问管程中的管理此资源的过程，但最多只有一个调用者能够真正进入管程，其他调用者必须等待直到管程可用。

6.3. 管程的形式

type 管程名=monitor {
   局部变量说明；
   条件变量说明；
   初始化语句；
   define 管程内定义的，管程外可调用的过程或函数名列表；
   use 管程外定义的，管程内将调用的过程或函数名列表；
   过程名/函数名(形式参数表) {
      <过程/函数体>;
      }
   
   过程名/函数名(形式参数表) {
      <过程/函数体>;
   }
}

6.4. 管程的结构

1. wait操作请求资源
2. signal操作唤醒条件变量

6.5. 管程的条件变量

1. 当资源不足导致进程阻塞时，同时开放冠层，让挡在管程外的一个进程进入管程。
2. 条件变量：是出现在管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过两个原语操作来控制它，用于阻塞进程的信号量。
   1. wait()：当一个管程过程发现无法继续时(如发现没有可用资源时)，它在某些条件变量上执行wait，这个动作引起调用进程阻塞，直到另一个进程在该条件变量上执行signal()
   2. signal()
      1. 如果存在其他进程由于对条件变量执行wait()而被阻塞，便释放之
      2. 如果没有进程在等待，那么信号不被保存，并不是立即退出管程等待队列，而是进入next信号量，以保证多个进程都可以正常退出。
   3. 条件变量仅仅维护阻塞队列的作用，如果没有等待时发生signal()操作，相当于空操作。
3. 使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：
   1. 执行signal的进程等待，直到被释放进程退出管程或等待另一个条件
   2. 被释放进程等待，直到执行signal的进程退出管程或等待另一个条件
4. 霍尔(Hoare, 1974)采用第一种办法
5. 汉森(Hansen)选择两者的折衷，规定管程中的过程所执行的signal操作是过程体的最后一个操作

6.6. 管程和进程对比

1. 管程定义公用数据结构，进程定义私有数据结构
2. 管程将共享变量上的同步操作集中统一管理，临界区分散在每个金层中。
3. 管程为了解决进程共享资源的互斥，进程为了占有系统资源和实现系统并发。
4. 管程被想要使用共享资源的所有进程调用，管程和调用它的进程不能并行工作；进程间可以并行工作。

6.7. 管程的实现(Hoare方法)

1. 霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理
2. 不要求signal操作是过程体的最后一个操作，且wait和signal操作可被设计成可以中断的过程
3. 使用signal释放一个等待进程时，霍尔管程让执行signal的进程等待，直到被释放进程退出管程或等待另一个条件
4. 霍尔管程基于PV操作原语实现
   1. Wait和signal可以是程序过程
   2. 可以用语言机制实现霍尔管程

6.7.1. Hoare管程的数据结构

6.7.1.1. 互斥信号量mutex

1. 对每个管程，使用用于管程中过程互斥调用的信号量mutex(初值为1)
2. 进程调用管程中的任何过程时，应执行P(mutex)；进程退出管程时，需要判断是否有进程在next信号量等待，如果有(即next_count>0)，则通过V(next)唤醒一个发出signal的进程，否则应执行V(mutex)开放管程，以便让其他调用者进入
3. 为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源

6.7.1.2. 进程的信号量next和计数器next-count

1. 对每个管程，引入信号量next(初值为0)，凡发出signal操作的进程应该用P(next)阻塞自己，直到被释放进程退出管程或产生其他等待条件
2. 进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。next-count(初值为0)，用来记录在next上等待的进程个数

6.7.1.3. 挂起等待资源的进程的信号量x-sem和计数器x-count

1. 引入信号量x-sem(初值为0)，申请资源得不到满足时，执行P(x-sem)阻塞。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器x-count(初值为0)记录等待资源的进程数
2. 执行signal操作时，应让等待资源的进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现

//每个管程定义如下数据结构 ：
typedef struct InterfaceModule { //InterfaceModule是结构体名字
   semaphore mutex;              //进程调用管程过程前使用的互斥信号量
   semaphore next;               //发出signal的进程阻塞自己的信号量
   int next_count;               //在next上等待的进程数
};
mutex=1;
next=0;
next_count=0; //初始化语句

6.7.2. Hoare管程的enter()和leave()操作

void enter(InterfaceModule &IM) {
   P(IM.mutex);         //判有否发出过signal的进程?
}

void leave(InterfaceModule &IM) {
   if (IM.next_count>0)
      V(IM.next);       //有就释放一个发出过signal的进程
   else
      V(IM.mutex);      //否则开放管程
}

6.7.3. Hoare管程的wait()操作

x_sem: semaphore;       // 与资源相关的信号量
x_count: integer;       // 在x_sem上等待的进程数
void wait(semaphore &x_sem,int
      x_count,InterfaceModule &IM) {
   x_count++;           //等资源进程个数加1，x_count初始化为0
   if (IM.next_count>0) //判断是否有发出过signal的进程
      V(IM.next);       //有就释放一个
   else
      V(IM.mutex);      //否则开放管程
   P(x_sem);            //等资源进程阻塞自己，x_sem初始化为0
}

6.7.4. Hoare管程的signal()操作

void signal(semaphore &x_sem,int
      &x_count,InterfaceModule &IM) {
   if(x_count>0) {      //判断是否有等待资源的进程
      IM.next_count++;  //发出signal进程个数加1
      V(x_sem);         //释放一个等资源的进程
      P(IM.next);       //发出signal进程阻塞自己
      x_count--;        //发出signal进程个数减1
   }
}

6.7.5. 合并汇总

typedef struct InterfaceModule { //InterfaceModule是结构体的名字
   semaphore mutex;              //进程调用管程过程前使用的互斥信号量
   semaphore next;               //发出signal的进程挂起自己的信号量
   int next_count; 
};                               //在next上等待的进程数
//初始化语句
mutex=1;
next=0;
next_count=0;

void enter(InterfaceModule &IM) {
   P(IM.mutex); //判有否发出过signal的进程?
}

void leave(InterfaceModule &IM) {
   if (IM.next_count>0)
      V(IM.next);       //有就释放一个发出过signal的进程
   //否则开放管程
}

void wait(semaphore &x_sem, int &x_count,InterfaceModule &IM) {
   x_count++;           //等资源进程个数加1，
   if (IM.next_count>0) //判断是否有发出过signal的进程
      V(IM.next);       //有就释放一个
   else
      V(IM.mutex);      //否则开放管程
   P(x_sem);            //等资源进程阻塞自己，x_sem初始化为0
} 

void signal(semaphore &x_sem,int &x_count,InterfaceModule &IM){
   if(x_count>0) {      //判断等待进程
      IM.next_count++;  //发出signal进程个数加1
      V(x_sem);         //释放一个等资源的进程
      P(IM.next);       //发出signal进程阻塞自己
      IM.next_count--;  //发出signal进程个数减1
   }
}

6.8. 管程求解进程同步与互斥问题

1. 互斥问题
   1. 读者写者问题
   2. 哲学家就餐问题
2. 同步问题
   1. 生产者-消费者问题
   2. 苹果-桔子问题

6.8.1. 霍尔管程求解读者/写者问题-写者优先

6.8.2. 霍尔管程求解哲学家就餐问题

Cobegin
   process philosopher_i() {
      L:thinking();
         dining_philosopers.pickup(i);
         eating();
         dining_philosophers.putdown(i);
      goto L;
   }
coend

6.8.3. AND 型信号量(课本 188-189 第53题)

1. 求解可以使用AND型信号量SP和SV操作
   1. SP(fork[i], fork[(i+1)%5])
   2. SV(fork[i], fork[(i+1)%5])

6.8.4. 霍尔管程解决生产者消费者问题

6.8.5. 霍尔管程求解苹果桔子问题

1. 桌上有一只盘子，每次只能放入一只水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。使用Hoare管程求解该问题
2. SP：盘子
3. SS：桔子
4. SD：苹果

7. 进程通信(信息传递)

7.1. 进程通信的概念

1. 交往进程通过信号量操作实现进程互斥和同步，这是一种低级通信方式
2. 进程有时还需要交换更多的信息(如把数据传送给另一个进程)，可以引进高级通信方式：进程通信机制，实现进程间用信件来交换信息，进程通信扩充了并发进程的数据共享
3. 通信方式包括很多种
   1. 信号通信机制：只能发送单个信号
   2. 管道通信机制
   3. 消息传递机制
   4. 信号量通信机制
   5. 共享内存通信机制。
4. 当进程互相交互时，必须满足两个基本要求：同步和通信
   1. 为实施互斥，进程间需要同步
   2. 为了协作，进程间需要交换信息
5. 消息传递提供了这些功能，最典型的消息传递原语
   1. send：发送消息的原语
   2. receive：接收消息的原语

7.2. 信号通信机制

7.2.1. 软中断(P152页)

1. 信号是一种软中断，用于内核或进程对某个进程发出中断，向进程通知某个特定事件的发生或迫使进程执行信号处理程序。
2. 中断和信号
   1. 相同：
      1. 概念上一致
      2. 异步过程
      3. 均采用向量表
      4. 均有屏蔽设施
   2. 不同：
      1. 中断由硬件和软件结合实现，信号完全依靠软件实现。
      2. 中断向量和中断处理程序均位于系统空间；信号向量表位于用系统空间，但信号处理程序由应用程序提供，在用户空间处理。

7.3. 信号通信机制

1. 用户、内核和进程都可以生成和发送信号。
2. 由进程执行指令而产生的信号称为同步信号，如除以0；
3. 像击键之类的进程之外的事件所引起的信号叫做异步信号。

7.4. 消息格式

7.5. 进程直接通信

1. 发送或接收信件的进程指出信件发给谁或从谁那里接收信件
   1. send(P, 信件)：把信件发送给进程P
   2. receive(Q, 信件)：从进程Q接收信件
2. 对称直接寻址，发送进程和接收进程必须命名对方以便通信，原语send() 和 receive()定义如下：
   1. send(P, messsage) 发送消息到进程P
   2. receive(Q, message) 接收来自进程Q的消息
3. 非对称直接寻址，只要发送者命名接收者，而接收者不需要命名发送者，send()和 receive()定义如下：
   1. send(P, messsage) 发送消息到进程P
   2. receive(id, message) 接收来自任何进程的消息，变量id置成与其通信的进程名称

7.6. 进程间接通信

1. 发送或者接收信件通过一个信箱来进行，该信箱有唯一标识符
2. 消息不是直接从发送者发送到接收者，而是发送到由临时保存这些消息的队列组成的一个共享数据结构，这些队列通常成为信箱(mailbox)
3. 一个进程给合适的信箱发送消息，另一进程从信箱中获得消息。
4. 信箱为操作系统所有是指由操作系统统一设置信箱，归系统所有，供相互通信的进程共享，消息缓冲机制就是一个著名的例子。
5. 一个进程为其他进程提供服务，此时信箱又叫做端口(port)
6. 间接通信的send()和 receive()定义如下：
   1. send(A,message)：把一封信件(消息)传送到信箱A，本身执行包含两种情况
      1. 同步的(阻塞型)，等待进程回答消息才继续。
      2. 异步的(非阻塞型)，不等待进程回答，先继续执行，之后再回来处理。
   2. receive(A,message)：从信箱A接收一封信件(消息)
      1. 同步的(阻塞型)，没有信息则挂起，知道有信息进入，如果有消息立即返回
      2. 异步的(非阻塞型)，查询信箱后，进程立即返还控制权，如果有消息则返回消息，否则返回标志码。
7. 一般我们选择非阻塞式send和阻塞式receive：发送可以一直发送信息直到满，接受通常是服务器进程，知道有信息才被唤醒。
8. "发送"和"接收"两条原语的功能为：
   1. 发送信件：如果指定的信箱未满，则将信件送入信箱中由指针所指示的位置，并释放等待该信箱中信件的等待者；否则，发送信件者被置成等待信箱状态
   2. 接收信件：如果指定信箱中有信，则取出一封信件，并释放等待信箱的等待者，否则，接收信件者被置成等待信箱中信件的状态
9. send和receive的代码实现

7.6.1. 间接通信的信箱

1. 信箱是存放信件的存储区域，每个信箱可以分成信箱特征和信箱体两部分
   1. 信箱头指出信箱容量、信件格式、存放信件位置的指针等
   2. 信箱体用来存放信件，信箱体分成若干个区，每个区可容纳一封信

7.6.2. 发送信件原语的处理流程

1. 若指定的信箱未满
2. 则把信件送入信箱中指针所指示的位置，释放等待该信箱中信件的等待者
3. 否则，发送信件者被置成等待信箱的状态

7.6.3. 接收信件原语的处理流程

1. 若指定信箱中有信件
2. 则取出一封信件，释放等待信箱的等待者
3. 否则，接收信件者被置成等待信箱中信件的状态

7.7. 管道和套接字

1. 管道(pipeline)是Unix和C的传统通信方式
   1. 进程通过管道读写数据时，另一个进程需要等待
   2. 发送者和接收者必须都知道对方存在
   3. 发送者和接受者之间要实现正确的同步关系

2. 套接字(socket)起源于Unix BSD版本，目前已经被Unix和Windows操作系统广泛采用，并支持TCP/IP协议，即支持本机的进程间通信，也支持网络级的进程间通信
3. 管道和套接字都是基于信箱的消息传递方式的一种变体，它们与传统的信箱方式等价，区别在于没有预先设定消息的边界。换言之，如果一个进程发送10条100字节的消息，而另一个进程接收1000个字节，那么接收者将一次获得10条消息

8. 消息传递通信机制

1. 消息传递的复杂性在于地址空间隔离，发送进程无法将信息直接复制到接收空间 的地址空间中，需要由操作系统完成。
2. 消息缓冲是在1973年由P.B.Hansan提出的一种进程间高级通信设施，并在RC4000系统中实现
3. 消息缓冲通信的基本思想是：由操作系统统一管理一组用于通信的消息缓冲存储区，每一个消息缓冲存储区可存放一个消息(信件)。当一个进程要发送消息时，先在自己的消息发送区里生成待发送的消息，包括：接收进程名、消息长度、消息正文等。然后，向系统申请一个消息缓冲区，把消息从发送区复制到消息缓冲区中，注意在复制过程中系统会将接收进程名换成发送进程名，以便接收者识别。随后该消息缓冲区被挂到接收消息的进程的消息队列上，供接收者在需要时从消息队列中摘下并复制到消息接收区去使用，同时释放消息缓冲区。

8.1. 消息缓冲通信

1. 消息缓冲通信涉及的数据结构：
   1. sender：发送消息的进程名或标识符
   2. size：发送的消息长度
   3. text：发送的消息正文
   4. next-ptr：指向下一个消息缓冲区的指针
2. 在进程的PCB中涉及通信的数据结构：
   1. mptr：消息队列队首指针
   2. mutex：消息队列互斥信号量，初值为1
   3. sm：表示接收进程消息队列上消息的个数，初值为0，是控制收发进程同步的信号量
3. 发送原语和接收原语的实现如下：
   1. 发送原语Send：申请一个消息缓冲区，把发送区内容复制到这个缓冲区中；找到接收进程的PCB，执行互斥操作P(mutex)；把缓冲区挂到接收进程消息队列的尾部，执行V(sm)、即消息数加1；执行V(mutex)
   2. 接收原语Receive：执行P(sm)查看有否信件；执行互斥操作P(mutex)，从消息队列中摘下第一个消息，执行V(mutex)；把消息缓冲区内容复制到接收区，释放消息缓冲区

8.2. 消息传递机制解决进程互斥和同步问题

8.2.1. 解决进程互斥问题

create_mailbox(box);
send (box，null)；
void Pi() { /*i = l,2,...，n*/
   message msg；
   while (true){
      receive(box，msg)；
      /* 临界区 */ ;
      send( box,msg)；
   }
}
cobegin
   Pi();
coend

1. 阻塞式receive()原语和非阻塞式send()原语。
2. 消息可以看做是传递的令牌

8.3. 消息传递求解生产者消费者问题

int capacity;                    /* 缓冲区最多个数 */
void producer(void){             /* 生产者进程 */
   int item;
   message m;                    /* 消息缓冲区 */
   while(true){
      item = produce_item();     /* 生产消息 */
      receive(consumer, &m);     /* 等待消费者发送空缓冲区 */
      build_message( &m，item);  /* 构造一条发送的消息 */
      send(consumer, &m);        /*发送消息给消费者*/
   }
}
void consumer(void){             /*消费者进程*/
   int item,i ;
   message m;
   for(i = 0; i < capacity ; i++)
      send (producer，&m);       /*给消费者发送空缓冲区*/
   while(true){
      receive( producer,&m);     /*接收含有item的消息*/
      item = extract_item(&m);   /*从item取消息*/
      send(producer,&m);        /*回送空缓冲区给生产者*/
      consume_item(item);        /*使用消息*/
   }
}

1. consumer发送capacity条空消息，生产者对信息加工后给消费者。
2. 通过上面方式，整体信息数不变。

9. 高级进程通信机制

9.1. 基于流的进程通信

1. 多个进程使用一个共享的消息缓冲区(可称为管道、多路转接器、套接字)
2. 一些进程往消息缓冲区中写入字符流(send/write)
3. 一些进程从消息缓冲区中读出字符流(receive/read)
4. 信息交换单位基于字符流，长度任意

9.2. 基于字符流的进程通信规约

9.3. 远程过程调用RPC(Remote Procedure Call)

1. 采用客户/服务器计算模式
2. 服务器进程提供一系列过程/服务，供客户进程调用
3. 客户进程通过调用服务器进程提供的过程/服务获得服务
4. 考虑到客户计算机和服务器计算机的硬件异构型，外部数据表示XDR被引入来转换每台计算机的特殊数据格式为标准数据格式

9.4. RPC执行步骤

1. 客户进程以普通方式调用客户存根
2. 客户存根组织RPC消息并执行Send，激活内核程序
3. 内核把消息通过网络发送到远地内核
4. 远地内核把消息送到服务器存根
5. 服务器存根取出消息中参数后调用服务器过程
6. 服务器过程执行完后把结果返回至服务器存根
7. 服务器存根进程将它打包并激活内核程序
8. 服务器内核把消息通过网络发送至客户机内核
9. 客户内核把消息交给客户存根
10. 客户存根从消息中取出结果返回给客户进程
11. 客户进程获得控制权并得到了过程调用的结果

9.5. 基于RPC/XDR的高级通信规约

10. 死锁的产生

10.1. 死锁的产生

1. 允许多个进程并发执行共享系统资源时，系统必须提供同步机制和进程通信机制
2. 然而，对这种机制使用不当的话，可能会出现进程永远被阻塞的现象
3. 例如，两个进程分别等待对方占有的一个资源，于是两者都不能执行而处于永远等待，这种现象称为"死锁"

10.1.1. 例1 进程推进顺序不当产生死锁

1. 设系统有打印机、绘图仪各一台，被进程Q1和Q2共享。两个进程并发执行，按下列次序请求和释放资源：

2. 进程资源轨迹图

10.1.2. 例2 PV操作使用不当产生死锁

10.1.3. 例3 资源分配不当引起死锁

若系统中有m个资源被n个进程共享，每个进程都要求Ｋ个资源，而m < n·K时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁

10.1.4. 例4 对临时性资源使用不加限制引起死锁

1. 进程通信使用的信件是一种临时性资源，如果对信件的发送和接收不加限制，可能引起死锁。
2. 进程P1等待进程P3的信件S3来到后再向进程P2发送信件S1；P2又要等待P1的信件S1来到后再向P3发送信件S2；而P3也要等待P2的信件S2来到后才能发出信件S3。这种情况下形成了循环等待，产生死锁。

10.1.5. 独木桥(例)

只能在一个方向行车，可能发生死锁，也可能发生饥饿

10.2. 死锁的定义

1. 一组进程处于死锁状态是指：每一个进程都在等待被另一个进程所占有的、不能抢占的资源。例如，
   1. 存在n个进程P1, P2, …, Pn
   2. 进程Pi因为申请不到资源Ri而处于等待状态
   3. 而Ri又被Pi+1占有，Rn被P1占有
   4. 显然，这n个进程的等待状态永远不能结束，
   5. 这n个进程就处于死锁状态
2. 操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁。
3. 例如，n个进程P1，P2，…，Pn，Pi因为申请不到资源Rj而处于等待状态，而Rj又被Pi+1占有，Pn欲申请的资源被P1占有，此时这n个进程的等待状态永远不能结束，则说这n个进程处于死锁状态。

10.3. 死锁问题的解决方法

1. 死锁防止
2. 死锁避免
3. 死锁检测和恢复

10.4. 产生死锁因素

1. 不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关

10.4.1. 死锁的产生(例1)

1. 例1 竞争资源产生死锁。设系统有打印机、读卡机各一台，它们被进程P和Q共享。两个进程并发执行，它们按下列次序请求和释放资源：

10.4.2. 死锁的产生(例2)

10.4.3. 死锁的产生(例3)

1. 例3 同类资源分配不当引起死锁
2. 若系统中有m个资源被n个进程共享，当每个进程都要求Ｋ个资源，而m < n·(K-1)+1时，如果分配不得当就可能引起死锁
3. 例如，m=5，n=5，k=2，采用的分配策略是为每个进程轮流分配。首先，为每个进程轮流分配一个资源，这时，系统中的资源都已分配完了；于是第二轮分配时，各进程都处于等待状态，导致了死锁

10.4.4. 死锁的产生(例4)

1. 例4 对临时性资源使用不加限制引起死锁
2. 在进程通信时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁
3. 比如，进程P1等待进程P3的信件S3来到后再向进程P2发送信件S1；P2又要等待P1的信件S1来到后再向P3发送信件S2；而P3也要等待P2的信件S2来到后才能发出信件S3。在这种情况下就形成了循环等待，永远结束不了，产生死锁

10.5. 解决死锁问题的三个方法

1. 综合上面的例子，产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关
2. 可从三个方面来解决死锁问题:
   1. 死锁防止
   2. 死锁避免
   3. 死锁检测和恢复

10.6. 死锁的防止

10.7. 死锁产生的四个必要条件

1. 互斥条件: 进程应互斥使用资源，任一时刻一个资源仅为一个进程独占
2. 占有和等待条件: 一个进程请求资源得不到满足而等待时，不释放已占有的资源
3. 不剥夺条件: 任一进程不能从另一进程那里抢夺资源
4. 循环等待条件: 存在一个循环等待链，每一个进程分别等待它前一个进程所持有的资源
5. 前三个是死锁存在的必要条件，但不是充分条件，第四个条件是前三个条件同时存在时所产生的结果。

10.7.1. 死锁的防止

1. 破坏四个必要条件之一，死锁就可防止
2. 破坏第一个条件，把独占型资源改造成共享性资源，使资源可同时访问而不是互斥使用。这是一个简单的办法，但对许多资源往往是不能做到的
3. 采用剥夺式调度方法可以破坏第三个条件，但剥夺式调度方法目前只适用于对主存资源和处理器资源的分配，而不适用于所有资源

10.7.1.1. 破坏第一个条件

1. 使资源可同时访问而不是互斥使用，
2. 可再入程序、只读数据文件、时钟、磁盘等软硬件资源均可用这种办法管理，但有许多资源如可写文件、磁带机等由于特殊性质决定只能互斥占有，而不能被同时访问，所以这种做法许多场合行不通。
3. 有些资源具有天生的互斥性

10.7.1.2. 破坏第二个条件

1. 静态分配是指进程在执行中不再申请资源，就不会出现占有某些资源再等待另一些资源的情况。
2. 所有并发执行的进程要求的资源总和不超过系统拥有的资源数
3. 实现简单，被许多操作系统采用，但会严重地降低资源利用率，因为在每个进程占有的资源中，有些资源在运行后期使用，甚至有些资源在例外情况下才被使用，可能造成进程占有一些几乎不用的资源，而使其他想用这些资源的进程产生等待。

10.7.1.3. 破坏第三个条件

1. 采用剥夺式调度方法，适用于内存和处理器资源。
2. 方法
   1. 如果要申请新的资源，必须主动释放已占用资源(剥夺式)，若仍需要占用次资源，则需要重新发起申请。
   2. 资源管理程序为进程分配新资源时，若有资源则分配，否则将剥夺进程已占有的全部资源，并让进程进入等待资源状态，资源充足后再唤醒它重新申请所有需要的资源。

10.7.1.4. 破坏第四个条件

1. 上述死锁防止办法造成资源利用率和吞吐率低。介绍两种比较实用的死锁防止方法
2. 采用层次分配策略
   1. 在层次分配策略下，资源被分成多个层
      1. 一个进程得到某一层的一个资源后，它只能再申请在较高层的资源
      2. 当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源
      3. 当一个进程获得了某一层的一个资源后，它想再申请该层中的另一个资源，那么，必须先释放该层中的已占资源
   2. 层次策略的变种按序分配策略
      1. 把系统的所有资源排一个顺序，例如，系统若共有n个进程，共有m个资源，用$r_i$表示第i个资源，于是这m个资源是：$r_1,r_2,...,r_m$
      2. 规定如果进程不得在占用资源$r_i(1\leq i \leq m)$后再申请$r_j(j<i)$。不难证明，按这种策略分配资源时系统不会发生死锁。

10.8. 死锁的避免

10.8.1. 死锁的避免

1. 当不能防止死锁的产生时，如果能掌握并发进程中与每个进程有关的资源申请情况，仍然可以避免死锁的发生
2. 只需在为申请者分配资源前先测试系统状态，若把资源分配给申请者会产生死锁的话，则拒绝分配，否则接收申请，为它分配资源

10.8.2. 银行家算法(资源分配拒绝法)

1. 银行家算法：
   1. 银行家拥有一笔周转资金，借钱给有偿还能力的客户
   2. 客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款
   3. 银行家应谨慎的贷款，防止出现坏帐
2. 用银行家算法避免死锁
   1. 操作系统(银行家)
   2. 操作系统管理的资源(周转资金)
   3. 进程(要求贷款的客户)
3. 银行家算法允许前三个必要条件存在，通过核实的资源分配算法确保不会出现进程循环等待链，从而避免死锁。
4. 系统首先检查申请者对资源的最大需求量
   1. 如果现存的资源可以满足它的最大需求量时，就满足当前的申请
   2. 如果不能则拒绝启动该进程。
5. 换言之，仅仅在申请者可能无条件地归还它所申请的全部资源时，才分配资源给它
6. 为了进一步说明这种算法，考虑下面的例子。假设系统有三个进程P, Q, R，系统只有一类资源共10个，目前分配情况如下：

10.8.2.1. 银行家算法的数据结构

1. 一个系统有$n$个进程和$m$种不同类型的资源,定义包含以下向量和矩阵的数据结构
2. 系统中每类资源总数向量：$Resource=(R_1,R_2,...,R_m)$
3. 系统中每类资源当前可用数向量：$Available=(V_1,V_2,...,V_m)$
4. 每个进程对各类资源的最大需求矩阵：$Claim[i,j]$，如果$Claim[i,j]=k$表示进程$P_i$需要$R_j$类资源的最大数目为$k$个。
5. 每个进程已占有各类资源数量矩阵：$Allocation[i,j]$，若$Allocation[i,j] = k$表示进程$P_i$占有$R_j$类资源$k$个，初始值为0。
6. 每个进程尚需要各类资源数量矩阵$Need[i,j]$，若$Need[i,j] = k$表示进程$P_i$还需要$R_j$类资源$k$个。$Need[i,j] = Claim[i,j] - Allocation[i,j]$
7. 每个进程从当前申请各类资源数量矩阵$Request[i,j]$，若$Request[i, j] = k$，表示进程$P_i$当前申请$R_j$类资源$k$个。

10.8.2.2. 银行家算法中下列关系式确保成立

1. 系统要启动一个新进程工作，对于资源$Resource[i]$即$R_i$的需求满足不等式：

$R_i \geq Claim[(n+1), i] + \sum\limits_{k=1}\limits^nClaim[k, i]$

1. 也就是应当满足当前系统中所有进程对资源$R_i$的最大需求数，加上启动的新进程的资源最大需求数，不超过系统拥有的最大资源数时才启动该进程(进程拒绝启动法)
2. $R_i=V_i+\sum A_{ki}$ 对$i=1,..,m,k=1,..,n$表示所有资源要么被分配、要么尚可分配
3. $C_{ki} \leq R_i$对$i=1,..,m, k=1,..,n$表示进程申请资源数不能超过系统拥有的资源总数
4. $A_{ki} \leq C_{ki}$对$i=1,..,m,k=1,..,n$表示进程申请任何类资源数不能超过声明的最大资源需求数

10.8.3. 系统安全性定义

1. 系统安全性定义：在时刻$T_0$系统是安全的,仅当存在一个进程序列$P_1,..,P_n$,对进程$P_k$满足公式：

$Need[k, i] \leq Available[i](V_i) + \sum\limits_{j=1}\limits^{k-1}Allocation[j, i] \\ i = 1,...,m;k = 1,...,n;\\$

10.8.4. 银行家算法的基本思想

1. 系统中的所有进程进入进程集合
2. 在安全状态下系统收到进程的资源请求后，先把资源试探性分配给它。
3. 系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程，从而，保证这个进程运行完毕并归还全部资源。
4. 把这个进程从集合中去掉，系统的剩余资源更多了，反复执行上述步骤。(进程退出系统，资源回收)
5. 最后，检查进程集合，若为空表明本次申请可行，系统处于安全状态，可实施本次分配;否则，有进程执行不完，系统处于不安全状态，本次资源分配暂不实施，让申请进程等待。
6. 注：安全序列是不唯一的,2019年有考察

10.8.5. 银行家算法的程序及实现

typedef struct state {//全局数据结构
   int resource[m];
   int available[m];
   int claim[n][m];
   int allocation[n][m];
};
void resource_allocation( ) { //资源分配算法
   if(allocation[i,*]+request[*]>claim[i,*])
      {error}; //申请量超过最大需求值
   else {
      if(request[*]>available[*])
         {suspend process.};
      else { //尝试分配，define newstate by:
         allocation[i,*]=allocation[i,*]+request[*];
         available[*]=available[*]-request[*];
      }
   }
   if(safe(newstate))
      {carry out allocation};
   else {
      {restore original state};
      {suspend process};
   }
}
bool safe(state s) { //安全性测试算法
   int currentavail[m];
   set <process> rest;
   currentavail[*]=available[*];
   rest={all process};
   possible=true;
   while(possible){ //rest中找一个Pk，满足以下条件
      claim[k,*]-allocation[k,*]<=currentavail[*]
      if(found){
         currentavail[*]=currentavail[*]+allocation[k,*];
         rest=rest–{Pk};
      }else{
         possible=false;
      }
   }
   return(rest=null);
}

10.8.6. 银行家算法例子

10.8.6.1. 银行家算法例1

P或者R再申请资源时，不能分配，因为现在只剩下2个资源，不能满足它们的最大需求

10.8.6.2. 实例说明系统所处的安全或不安全状态(1)

1. 如果系统中共有五个进程和A、B、C三类资源
2. A类资源共有10个,B类资源共有5个,C类资源共有7个
3. 在时刻$T_0$,系统目前资源分配情况如下：

1. 可以断言目前系统处于安全状态，因为序列$\{P_1,P_3,P_4,P_2,P_0\}$能满足安全性条件

2. 假设$P_1$又请求1个A类资源和2个c类资源，得到新的状态如下图所示：
   1. $Request1(1, 0, 2) \leq Need(1, 2, 2)$
   2. $Request1(1, 0, 2) \leq Available(3, 3, 2)$

3. 判定新状态是否安全?可执行安全性测试算法，找到一个进程序列$\{P_1,P_3,P_4,P_0,P_2\}$能满足安全性条件，所以可正式把资源分配给进程P1；

4. 假设$P_4$发起资源请求，按照银行家算法检查，资源不足不予以分配
   1. $Request4(3, 3, 0) \leq Need(4, 3, 1)$
   2. $Request4(3, 3, 0) > Available(2, 3, 0)$
5. 假设$P_0$发起资源请求，按照银行加算法检查，得到中间结果如下
   1. $Request0(0, 2, 0) \leq Need(7, 3, 1)$
   2. $Request0(0, 2, 0) \leq Available(2, 3, 0)$

10.9. 死锁的检测

10.9.1. 死锁的检测

1. 解决死锁问题的另一条途径是死锁检测方法
2. 这种方法对资源的分配不加限制，但系统定时运行一个"死锁检测"程序，判断系统内是否已出现死锁，若检测到死锁则设法加以解除
3. 检测的一种方法：可设置两张表格来记录进程使用资源的情况
   1. 等待资源表记录每个被阻塞进程等待的资源
   2. 占用资源表记录每个进程占有的资源
4. 进程申请资源时，先查该资源是否为其它进程所占用
   1. 若资源空闲，则把该资源分配给申请者且登入占用资源表
   2. 否则，则登入进程等待资源表

1. 死锁检测程序定时检测这两张表，若有进程$P_i$等待资源$r_k$，且$r_k$被进程$P_j$占用，则说$P_i$和$P_j$具有"等待占用关系"，记为$W(P_i, P_j)$
2. 死锁检测程序反复检测这两张表，可以列出所有的"等待占用关系"
3. 如果出现$W(P_i, P_j)，W(P_j, P_k)，...，W(P_m,P_n)，W(P_n, P_i)$时，显然，系统中存在一组循环等待资源的进程：$P_i，P_j，P_k，...，P_m，P_n$，也就是说出现了死锁

10.9.2. 资源分配图与死锁定理

1. 资源分配图的图例
   1. 每个资源用一个方框表示
   2. 方框中的黑圆点表示此资源类中的各个资源
   3. 每个进程用一个圆圈表示
   4. 有向边表示进程申请资源和资源被分配情况
2. 约定$P_i\rightarrow R_j$为请求边，表示进程$P_i$申请资源类$R_j$中的一个资源得不到满足而处于等待$R_j$类资源的状态，该有向边从进程开始指到方框的边缘，表示进程$P_i$申请$R_j$类中的一个资源。
3. $Rj\rightarrow Pi$为分配边，表示$R_j$类中的一个资源已被进程$P_i$占用，由于已把一个具体的资源分给了进程Pi，故该有向边从方框内的某个黑圆点出发指向进程。

1. 图3.6中存在环路，经过分析是存在死锁的
2. 图3.7中存在环路，但是经过分析是不存在死锁的，因为$R_1$和$R_2$资源都不只一个，$P_2$和$P_4$进程归还后是可以避免的。
3. 我们可以用矩阵和向量来求解，手机图片

10.9.2.1. 死锁检测算法

1. 如果进程-资源分配图中无环路，此时系统没有发生死锁。
2. 如果进程-资源分配图中有环路，且每个资源都只有一个资源则发生死锁。
3. 如果进程-资源分配图中有环路，且所涉及资源有多个资源，则未必发生死锁，需要具体问题具体分析：可以通过消去法来判断，消去即不阻塞其他进程又与其他进程相关的进程的所有请求边和分配边，得到一个孤立点。接着将等待资源的进程分配后再次消去，如果最后所有的进程都成为孤立点则是无死锁的，图是可完全简化的，否则图是不可以完全简化的。

10.9.2.2. 死锁定理

系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理

10.9.3. 死锁检测的数据结构

1. 把两张表格中记录的进程使用和等待资源的情况用一个矩阵A来表示

10.9.4. 死锁检测程序可用Warshall的传递闭包算法

1. 检测是否有死锁发生，即对矩阵$A$构造传递闭包$A^*[bij]$
2. $A^*[bij]$中的每个$bij$是对$A[bij]$执行如下算法

for k:=1 to n do
   for i:=1 to n do 
      for j:=1 to do
         bij:= bij 并 (bik 并 bkj)

10.10. 死锁检测和恢复

1. 死锁被检测到后可以通过各种方法来解除系统死锁以恢复到可运行状态，方法有资源剥夺法、进程回退法、进程撤销法和系统重启法。
   1. 资源剥夺法：剥夺陷于死锁的进程所占用的资源，但并不撤销此进程，直至死锁解除。可仿照撤销陷于死锁的进程那样来选择剥夺资源的进程。
   2. 进程回退法：根据系统保存的检查点让所有进程回退，直到足以解除死锁，这种措施要求系统建立保存检査点、回退及重启机制。
   3. 进程撤销法：
      1. 撤销陷于死锁的所有进程，解除死锁，继续运行。
      2. 逐个撤销陷于死锁的进程，回收其资源并重新分派，直至死锁解除。但是究竟先撤销哪个死锁进程呢？可选择符合下面条件之一的进程先撤销： PU消耗时间最少者、产生的输出量最少者、预计剩余执行时间最长者、分得的资源数量最少者或优先级最低者。
   4. 系统重启法：结束所有进程的执行并重新启动操作系统。这种方法很简单，但先前的工作全部作废，损失很大。
2. 检测死锁是否出现和发现死锁后实现恢复的代价大于防止和避免死锁花费的代价，但是这样的代价是值得的，因为死锁不是经常出现的。
   1. 检测策略的代价依赖于死锁出现的频率
   2. 恢复的代价是指处理器时间的损失。