华南农业大学——第六章 并发,死锁与饥饿

1、死锁一组相互竞争系统资源或进行通信的进程间的“永久”阻塞涉及两个或多个进程之间对资源需求的冲突无有效解决方法 常见：交通死锁 可重用资源可重用资源+可消耗资源可消耗资源可重用资源可重用资源一次只能供一个进程安全地使用，不会耗尽可剥夺资源：包括CPU、虚存、磁盘不可剥夺资源：打印机、文件、数据库和信号量竞争不可剥夺资源，就会发生死锁死锁两进程竞争可重用资源可重用资源的例子p0p1q0q1p2q2策略：给系统设计施加关于资源请求顺序的约束资源请求顺序的约束可重用资源死锁的另一个例子：内存请求可分配空间200kb第二个请求时发生死锁 解决：使用虚拟存储消除死锁可能性使用虚拟存储消除死锁可能性P1.

2、. . . .Request 80 Kbytes;Request 60 Kbytes;P2. . . . .Request 70 Kbytes;Request 80 Kbytes;可消耗资源可消耗资源可以被创建（生产）和销毁（消耗） 的资源一个无阻塞的生产进程可以创建任意数目的这类资源例子：中断、信号、消息和I/O缓冲区中的信息接收信息信息被阻塞（receive阻塞），出现死锁-难以发现接收受阻，死锁出现P1. . . . .Receive(P2);Send(P2, M1);P2. . . . .Receive(P1);Send(P1, M2);一个有向图表示，描述资源和进程状态进程：P，圆形

3、表示某类资源：R，方形表示具体资源：原点表示请求：Pi Rj分配：Rj PiP1P2R2 R1 互斥一次只有一个进程可以使用一个资源，其他进程不能访问占有且等待当一个进程等待其他进程时，继续占有已有资源不可抢占不能强行抢占进程已占有资源循环等待前三个条件的潜在结果存在一个封闭的进程链，使每个进程至少占有此链中下一个进程所需要的一个资源 必必要要条条件件充充分分条条件件预防死锁预防死锁：消除某一个条件的出现避免死锁避免死锁：不破坏条件，允许进程资源动态分配，检查状态，保证不出现死锁 检测死锁检测死锁：试图检测到死锁的存在并恢复撤销死锁进程剥夺资源互斥不可能禁止占有且等待要求进程一次性地请求所有需

4、要的资源低效的进程阻塞很长时间，以等待所有资源一个资源可能被占有很长时间，而不被使用并不知道自己所需的所有资源 不可抢占一个进程申请新资源被拒绝时，必须释放之前占有的资源操作系统抢占某个进程，要求它释放已占有的资源（不同优先级）循环等待定义资源类型的线性顺序A：Ri-Rj（ij) 死锁预防-约束资源请求,至少破坏一个条件防止前三个条件，间接完成防止第四个条件，直接完成导致低效的资源利用和低效的进程执行死锁避免允许三个必要条件明智选择，确保永不会到达死锁点，允许更多的并发需要知道将来的进程资源请求的情况，以判断该请求是否可能导致死锁两种方法进程启动拒绝进程启动拒绝：如果一个进程的请求会导致死锁，

5、不启动进程资源分配拒绝资源分配拒绝：如果一个进程增加的资源请求会导致死锁，则不允许分配Resource=(R1,R2,Rm): 系统中每种资源的总量Available=V=（V1,V2,Vm):未分配给进程的每种资源的总量Claim=C= :每个进程对每种资源的最大需求Allocation=A= :显示每个进程当前的资源分配情况1. Rj=Vj+A.j 所有资源或者可用，或者已经被分配2. Cij=Ri 任何一个进程对任一种资源的请求都不能超过系统中该种资源的总量3. Aij=C(n+1)j+C.j 才启动新进程Pn+1银行家算法银行家算法安全状态：至少有一个资源分配序列不会导致死锁, 即 C

6、ij-Aij=Vj不安全状态: 不存在任何安全序列RequestiCi-AiF退出TRequesti=ViT预分配资源Ai=Ai+ RequestiV=V- Requesti测试 分配资源FPi等待 不安全Pi等待，恢复原来值安全初始状态初始状态P2 运行运行P1 运行运行P3 运行运行51P 2请求1个R1和1个R3，是否安全？P1请求1个R1和1个R3，是否安全？全局数据结构资源分配算法测试安全算法（银行家算法）必需事先声明必需事先声明每个进程请求的最大资源；所讨论的进程必须是无关的，不存在同步不存在同步分配资源数目必须是固定的固定的占有资源时，进程不能退出不限制资源访问或约束进程行为，只

7、要有可能，被请求的资源就被分配给进程OS周期性地执行一个算法检测充分条件：循环等待循环等待好处：可以尽早发现死锁缺点：耗费相当多的处理器时间死锁检测算法死锁检测算法标记所有不会产生死锁的进程当且仅达算法结束仍有进程未标记，则存在死锁不能保证防止死锁，只能确定当前是否存在死锁00011Available 步骤：步骤：1、标记A矩阵中全为0的一行；2、初始化临时向量W=V；3、查找未标记的进程i，其在请求矩阵Q中小于等于W，若无，终止 ；4、找到，标记进程i，并把A中相应的第i行加到W中，并返回3。P4P3恢复（复杂度递增）取消取消所有的死锁进程所有的死锁进程把每个死锁进程回滚到前面定义的某些检查

8、点，重新启动所有进程连续取消死锁进程直到不再存在死锁连续抢占资源直到不再存在死锁选择原则：选择原则：消耗的CPU时间最少产生的输出最少剩下的时间最少分配的资源总量最少优先级最低（防止饥饿） 把资源分成几组不同的资源类预防资源类之间由于循环等待产生死锁，可使用全面定义的线性排序策略在一个资源类中，使用该类资源最适合的算法对于每一类资源的策略可交换空间可交换空间：即外存，通过要求一次性分配所有请求的资源来预防死锁，如果知道最大存储需求，此策略合理进程资源进程资源：如文件等，死锁避免很有效，或资源排序进行预防内存内存：基于抢占的预防最适合。内部资源内部资源：如I/O通道，可以使用基于资源排序的预防策

9、略至多允许四人同时拿刀叉Semaphore fork5=1Semaphore room=4奇号人先拿左叉偶号人先拿右叉管道消息共享内存信号量信号管道环形缓冲区，允许进程以生产者/消费者的模型进行通信先进先出队列创建时获得一个固定大小的字节数，OS强制实施互斥命名管道和匿名管道消息有类型的一段文本OS提供msgsnd和msgrcv系统调用每个进程都有一个消息队列，信箱发送者指定每个消息的类型，接收者可以用作选择依据内存共享Unix提供进程通信的速度最快的一种方式多个进程共享一个公共内存块每个进程都有读写权限 互斥约束，不属于此机制，但由各个进程提供信号量是semWait 和semSignal 的

10、扩展可同时进行多个操作，且增量减量可大于1信号信号是用于向一个进程通知发生异步事件的机制类似于硬件中断，但没有优先级死锁原理资源类型和资源分配图死锁条件处理死锁方法死锁预防死锁避免：银行家算法死锁检测：检测算法复习题：3，7习题：5，6，151、写出信号量定义，semWait和semSignal原语，以及用信号量实现互斥的伪代码。P. 151-图图5.3 ： semWait和和semSignal原语原语P. 153-图图5.6：信号量实现互斥：信号量实现互斥2、假设一个阅览室有100个座位，没有座位时读者在阅览室外等待；每个读者进入阅览室时都必须在阅览室门口的一个登记本上登记座位号和姓名，然后

11、阅览，离开阅览室时要去掉登记项。每次只允许一个人登记或去掉登记。用信号量操作描述读者的行为读者的行为。设两个信号量：设两个信号量： const int n=/*读者数*/count 空位数，初值=100； mutex 用于登记本的互斥使用，mutex=1。 void reader(int i)semWait(count);semWait(mutex); 登记； semSignal(mutex)； 阅览； semWait(mutex); 去掉登记； semSignal(mutex)； semSignal(count)； 离开； void main() Parbegin(reader(1)， re

12、ader(2),reader(n); 3、设公共汽车上，司机和售票员活动如下： 1）司机：启动汽车，正常行车，到站停车； 2）售票员：关车门，售票，开门上下客。用信号量操作描述司机和售票员的同步。设信号量：S1表示是否允许司机启动汽车（初值0）、S2表示是否允许售票员开车门（初值0）。Void Driver()while T semWait(S1); 启动汽车； 正常行车； 到站停车； semSignal(S2); Void Conductor() while T 关车门； semSignal(S1); 售票； semWait(S2); 开门上下客； Void main() parbegin(

13、Driver(), Conductor(); 4、(选做)独木桥问题：东、西向汽车过独木桥。桥上无车时允许一方汽车过桥，待全部过完后才允许另一方汽车过桥。用信号量操作写出同步算法。(提示：参考读者优先的解法)设信号量pass表示可以上桥，初值1。东车和西车计数的整型变量count1和count2，初值均为0。保护count1和count2互斥访问的两个信号量mutex1和mutex2，初值均为1。P1：东车 semWait(mutex1); count1+; if (count1=1) semWait(pass); semSignal(mutex1); 过独木桥; semWait(mutex1); count1-; if (