信号量和银行家算法.ppt

1,第3章 同步、通信与死锁,主要内容 临界区管理 信号量与PV操作 进程通信 死锁 转向,2,3.1.3 进程的交互：竞争与协作(1) 第一种是竞争关系,系统中的多个进程之间彼此无关 系统中的多个进程之间彼此相关 资源竞争的两个控制问题： 一个是死锁(Deadlock)问题， 一个是饥饿(Starvation) 问题 既要解决饥饿问题，又要解决死锁问题。 进程互斥是指若干个进程因相互争夺独占型资源时所产生的竞争制约关系。,3,进程的交往：竞争与协作(2) 第二种是协作关系,某些进程为完成同一任务需要分工协作。 进程同步指为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。 进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。 进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。,4,3.2 临界区管理,3.2.1 互斥与临界区 3.2.2 实现临界区管理的几种尝试 3.2.3 实现临界区管理的软件方法 3.2.4 实现临界区管理的硬件设施,5,3.2.1 互斥与临界区(1),临界资源：一次仅允许一个进程使用的共享资源，如打印机，表格，磁带机。 临界区：在每个进程中方位临界资源的那段程序。 与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。 如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。,6,互斥与临界区(2),访问领界区的循环描述repeat,until false,检查临界资源是否能访问,将临界资源设为未访问,7,互斥与临界区(3),临界区调度原则： 一次至多一个进程能够进入临界区内执行； 如果已有进程在临界区，其他试图进入的进程应等待； 进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入。 临界区调度原则总结： 互斥使用、有空让进； 忙则等待、有限等待； 择一而入，算法可行。,8,3.3 信号量与PV操作,3.3.1 同步与同步机制 3.3.2 信号量与PV操作 3.3.3 信号量实现互斥 3.3.4 信号量解决五个哲学家吃通心面问题 3.3.5 信号量解决生产者-消费者问题 3.3.6 记录型信号量解决读者-写者问题 3.3.7 记录型信号量解决理发师问题 转向,9,信号量机制,如何协调进程间的同步互斥？ 1965年E.W.Dijkstra提出了新的同步工具-信号量 和P、V操作。,信号灯,10,信号量与PV操作,信号量：一种软件资源 一种数据结构 信号量的值与相应资源的使用情况有关 信号量的值仅有P，V操作改变。 原语：内核中执行时不可被中断的过程 P操作原语和V操作原语 一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。,11,信号量与PV操作,那么信号量如何实现？,12,整型信号量,整型数 P操作（Wait）原语 V操作（Singal）,S,13,整型信号量,Wait（s）： while s = 0 do no option s:=s-1; Signal（s）： s:=s+1;,14,Wait (s)和Signal（s）是原子操作 注意：只要信号量=0就不断测试，不满足让权等待。,15,记录型信号量,记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。,16,记录型信号量,记录型结构， 包含两个数据项 Type semaphore = record value：interger； L：list of process end：,Value,L,PCB链表,S,17,记录型信号量,S.value 为资源信号量其初值；某类资源的数目 Wait操作：申请一个单位资源 Procedure Wait(s) var s: semaphore; begin s.value=s.value-1; if s.value0 then Block(s,l) End,18,记录型信号量,Singal 操作：释放一个单位资源 Procedure Signal(s) Var S:Semaphore begin S.value:=S.value+1; if S.value=0 then Wakeup(s,L) S.value,19,记录型信号量,S.value 大于等于0 表示系统中可用的资源数量 S.value 小于0 表示其绝对值表示申请该资源的阻塞的进程数量 S.value等于1：只允许一个进程访问临界资源，是互斥信号量。 死锁可能产生！举例！,20,记录型信号量,Pa： Pb Wait（Demutex） Wait（Emutex） Wait（Emutex） Wait（Dmutex） 可能会造成僵持的状态！,21,用信号量实现互斥,Var mutex：semaphore=1 Begin Parbegin process 1：begin repeat wait（mutex）； critical section signal（mutex）； reminder section until false； end,22,用信号量实现互斥,Process2：begin repeat wait（mutex）； crital section singal（mutex）； reminder section until false； end； parend,23,3.3.3 信号量实现互斥,semaphore mutex; mutex=1; cobegin process Pi( ) /i=1,n P(mutex); 临界区; V(mutex); coend,24,在实现互斥时应注意 Wait（mutex）和signal（mutex）必须成对的出现。 缺 Wait（mutex）将会引起系统混乱，不能保证对临界资源的互斥访问 缺 Signal（mutex）将会使该临界资源不能释放,25,经典的同步问题,哲学家进餐问题 生产者-消费者问题 读者-写者问题,26,五个哲学家吃通心面问题,有五个哲学家，他们的生活方式是交替的进行思考和进餐。哲学家围坐在一圆桌旁，桌中央有一盘通心面，在园桌上有五个碗和五只筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。,27,五个哲学家吃通心面问题,28,哲学家吃通心面问题,分析 筷子是临界资源，在一段时间内只允许一个哲学家使用 用一个信号量表示一支筷子，由这五个信号量构成信号量组 var chopstick： array04of semaphore 所以信号量初始化为1,29,问题,加入五个哲学家同时饥饿，同时拿起左边的筷子，五个信号量为0，当他们再试图拿起右面的筷子时，都将无限期的等待，导致僵持的状态。,30,semaphore fork5; for (int i=0;i5;i+) forki=1; cobegin process philosopher_i( ) /i= 0,1,2,3,4 while(true) think( ); P(forki); P(fork(i+1)%5); eat( ); V(forki); V(fork(i+1)%5); coend,可能死锁！,哲学家吃通心面问题,31,解决方法,上述解法可能出现永远等待，有若干种办法可避免死锁： 至多允许四个哲学家同时吃；保证至少一人能够吃饭，从而保证将来释放筷子使更多人进餐。 奇数号先取左手边的叉子，偶数号先取右手边的叉子； 每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,32,哲学家吃通心面问题的一种正确解,semaphore fork5; for (int i=0;i5;i+) forki= 1; cobegin process philosopher_i( )/*i=0,1,2,3 */ repeat think( )； P(forki）； /*i=4,P(fork4)*/ P(fork(i+1)%5 )；/*i=4,P(fork0)*/ eat( )； V(forki)； V(fork(i+ 1%5)； until false coend,33,课堂练习,为保证这两个进程能正确地打印各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。,34,生产者-消费者问题,著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。 在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。 解决好生产者-消费者问题就解决好了一类并发进程的同步问题。,35,生产者-消费者问题,有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。,36,生产者消费者问题,一个生产者、一个消费者共享一个缓冲区 一个生产者、一个消费者共享多个缓冲区 多个生产者、多个消费者共享多个缓冲区,37,一个生产者、一个消费者共享一个缓冲区的解,int B; semaphore empty; /可以使用的空缓冲区数 semaphore full; /缓冲区内可以使用的产品数 empty=1; /缓冲区内允许放入一件产品 full=0; /缓冲区内没有产品,38,cobegin process producer() process consumer() while(true) while(true) produce( ); P(full); P(empty); take( ) from B; append( ) to B; V(empty); V(full); consume( ); coend,39,多个生产者/消费者、共享多个缓冲区的解,item Bk; semaphore empty; empty=k; /可以使用的空缓冲区数 semaphore full; full=0; /缓冲区内可以使用的产品数 semaphore mutex; mutex=1; /互斥信号量 int in=0; /放入缓冲区指针 int out=0; /取出缓冲区指针,40,cobegin process producer_i ( ) process consumer_j ( ) while(true) while(true) produce( ); P(full); P(empty); P(mutex); P(mutex); take( ) from Bout; append to Bin; out=(out+1)%k; in=(in+1)%k; V(mutex); V(mutex); V(empty); V(full); consume( ); coend,跳转,41,1、信号量小结,一个信号量可用于n个进程的同步互斥；且只能由P、V操作修改。 用于互斥时，S初值为1，取值为1 - (n-1) （相当于临界区的通行证，实际上也是资源个数） S=1：临界区可用 S=0：已有一进程进入临界区 S=0 S=0:表示可用资源个数 S0: 表示该资源的等待队列长度,42,2、P、V操作小结,P(S)：请求分配一个资源。 V(S)：释放一个资源。 P、V操作必须成对出现。 用于互斥时，位于同一进程内； 用于同步时，交错出现于两个合作进程内。 多个P操作的次序不能颠倒，否则可能导致死锁。 多个V操作的次序可任意。,43,课堂练习：,44,答案,45,答案,46,答案,47,3.6 死锁,3.6.1 死锁产生 3.6.2 死锁防止 3.6.3 死锁避免 3.6.4 死锁检测和解除,48,3.6.1 死锁产生 若干死锁的例子,例进程推进顺序不当产生死锁 设系统有打印机、读卡机各一台，被进程和共享。两个进程并发执行，按下列次序请求和释放资源： 进程 进程 请求读卡机 请求打印机 请求打印机 请求读卡机 释放读卡机 释放读卡机 释放打印机 释放打印机,49,出现死锁！,50,例 PV操作使用不当产生死锁,进程Q1 进程Q2 P(S1); P(s2); P(s2); P(s1); 使用r1和r2; 使用r1和r2 V(S1); V(s2); V(S2); V(S1);,51,出现死锁！,52,例资源分配不当引起死锁,若系统中有m个资源被n个进程共享，每个进程都要求个资源，而m nK时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。,53,死锁定义,操作系统中的死锁：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁。 例如，n个进程P1、P2，Pn，Pi因为申请不到资源Rj而处于等待状态，而Rj又被Pi+1占有，Pn欲申请的资源被P1占有，此时这n个进程的等待状态永远不能结束，则说这n个进程处于死锁状态。,54,产生死锁因素,不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关。,55,3.6.2 死锁防止(1),系统形成死锁的四个必要条件 互斥条件：进程互斥使用资源 部分分配条件：申请新资源时不释放已占有资源 不剥夺条件：一个进程不能抢夺其他进程占有的资源 环路条件：存在一组进程循环等待资源的,56,死锁防止(2),破坏第一个条件 使资源可同时访问而不是互斥使用， 破坏第三个条件 采用剥夺式调度方法， 当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后才去等待。 破坏第二个条件或第四个条件 上述死锁防止办法造成资源利用率和吞吐率低。介绍两种比较实用的死锁防止方法。,57,死锁的防止(3),采用层次分配策略（破坏条件2和4） 资源被分成多个层次 当进程得到某一层的一个资源后，它只能再申请较高层次的资源 当进程要释放某层的一个资源时，必须先释放占有的较高层次的资源 当进程得到某一层的一个资源后，它想申请该层的另一个资源时，必须先释放该层中的已占资源,58,死锁防止(4),层次策略的变种按序分配策略 把系统的所有资源排一个顺序，例如，系统若共有n个进程,共有m个资源，用ri表示第i个资源，于是这m个资源是： r1,r2,rm 规定如果进程不得在占用资源ri(1im)后再申请rj(ji)。不难证明，按这种策略分配资源时系统不会发生死锁。,59,3.6.3 死锁避免,主要思想：动态的检测资源分配状态以确保循环等待条件不可能成立。 银行家算法 银行家拥有一笔周转资金 客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款 银行家应谨慎的贷款，防止出现坏帐 用银行家算法避免死锁 操作系统（银行家） 操作系统管理的资源(周转资金) 进程（要求贷款的客户）,60,1、安全状态,最大需求 当前占有 P0 10 5 P1 4 2 P2 9 2,说明：某系统有12台磁带驱动器 P0：最多要求10台 P1：最多要求4台 P2：最多要求9台,P1 分配2；用完释放4；则系统剩余5 P0 分配5；用完释放10；则系统剩余10 P2 分配7；用完释放9；则系统剩余12,若存在一个安全序列，则系统处于安全状态 例,61,死锁,不安全,安全,安全、不安全和死锁状态空间,结论： 安全状态不是死锁状态 死锁状态是不安全状态 不是所有不安全状态都是死锁状态,62,2、银行家算法,数据结构 Available：Availablej=k 资源类型Rj 现有k个实例 Max：Maxi,j=k 进程Pi最多可申请k个Rj的实例 Allocation：Allocationi,j=k 进程Pi现在已经分配了k个Rj的实例 Need：Needi,j=k 进程Pi还可能申请k个Rj的实例 Needi,j = Maxi,j - Allocationi,j,63,符号说明 X=Y （X和Y是长度为n的向量），当且仅当对所有i=1,2,n，Xi=Yi Allocationi 表示分配给进程Pi的资源（将Allocation每行作为向量） Need同Allocation,64,安全性算法,用于确定计算机系统是否处于安全状态 设Work和Finish分别是长度为m和n的向量，初始化Work:=Available，Finishi=false(i=1,2,n) 查找 i 使其满足 Finishi = false Needi =Work 若没有这样的 i 存在，转到4）。 Work := Work + Allocationi Finishi := true 返回到2） 如果对所有 i，Finishi = true，则系统处于安全状态,65,资源请求算法,设Requesti 为进程Pi的请求向量 如果Requesti = Needi ，那么转到第2）步。否则，产生出错条件，因为进程已超过了其请求。 如果Requesti =Available，那么转到第3）步。否则， Pi等待，因为没有可用资源。 假定系统可以分配给进程Pi 所请求的资源，并按如下方式修改状态： Available:= Available Requesti ; Allocationi := Allocationi + Requesti ; Needi := Needi Requesti ; 调用安全性算法确定新状态是否安全 安全操作完成且进程Pi分配到其所需要的资源 不安全进程Pi必须等待，并将数据结构恢复到原状态（即 3）的逆操作）,66,银行家算法举例,说明： 5个进程P0P4， 3种资源类型A、B、C，且实例个数分别为10、5、7 T0时刻状态如图所示,Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3,67,问题： T