进程同步与互斥

1、1进程的互斥进程的互斥 你要，我也要 多道程序设计带来的问题多道程序设计带来的问题 ： 并发执行的多个进程可能产生互斥或同步的相互制约并发执行的多个进程可能产生互斥或同步的相互制约关系，不采取措施，可能导致结果的不可再现性。影响系关系，不采取措施，可能导致结果的不可再现性。影响系统效率，而且还可以导致系统崩溃。统效率，而且还可以导致系统崩溃。 为此为此，现代操作系统都在内核中设有进程的互斥同步，现代操作系统都在内核中设有进程的互斥同步机制，以控制并发执行的诸进程能有效的共享资源和相互机制，以控制并发执行的诸进程能有效的共享资源和相互合作，同时使并发程序的执行仍具有可再现性。合作，同时使并发程序

2、的执行仍具有可再现性。2一、一、 互斥的定义互斥的定义 所谓所谓，指的是对某个系统资源，一个进，指的是对某个系统资源，一个进程正在使用它，另外一个想用它的进程就必须等程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用待，而不能同时使用 。 进程互斥是多道程序系统中进程间存在的一种源进程互斥是多道程序系统中进程间存在的一种源于资源共享的制约关系，也称于资源共享的制约关系，也称间接制约关系间接制约关系，主，主要是由被共享资源的使用性质所决定的。要是由被共享资源的使用性质所决定的。计科系姜云杰3 这种限定进程只能互斥地访问它的资源叫这种限定进程只能互斥地访问它的资源叫临界资源（临界资源（指

3、一次仅允许一个进程使用的资源 ）。 临界资源限定了使用者只能互斥地使用它。临界资源限定了使用者只能互斥地使用它。 操作系统也不能中途从抢先者手中把临界资源抢来给其他操作系统也不能中途从抢先者手中把临界资源抢来给其他进程用。进程用。 因此，临界资源也是不可剥夺性资源。因此，临界资源也是不可剥夺性资源。例：打印机、共享例：打印机、共享变量变量等。等。计算机系统中可剥夺性使用的资源主要有计算机系统中可剥夺性使用的资源主要有CPU、内存内存和和磁磁盘盘等。等。4程 序 段1程 序 段2程 序 段n共 享 变量5：进程中访问临界资源的那段程序代码称为临界：进程中访问临界资源的那段程序代码称为临界区或临界

4、段。区或临界段。使用同一临界资源的不同进程中的临界区称为使用同一临界资源的不同进程中的临界区称为区区或或。为实现对临界资源的互斥访问，应保证诸进程为实现对临界资源的互斥访问，应保证诸进程地进地进入各自的临界区。入各自的临界区。 但无论采用何种方法，都应但无论采用何种方法，都应遵循临界区的使用原则遵循临界区的使用原则，即，即“空则让进，忙则等待，等则有限，等则让权空则让进，忙则等待，等则有限，等则让权”。 6二、上锁和开锁原语二、上锁和开锁原语 现代操作系统用来实现进程的互斥、同步的工现代操作系统用来实现进程的互斥、同步的工具有多种，如上锁与开锁原语、信号灯机制、具有多种，如上锁与开锁原语、信号

5、灯机制、管程机制等。管程机制等。 上锁与开锁是一种最简单的进程互斥方法，它上锁与开锁是一种最简单的进程互斥方法，它使用一个锁变量使用一个锁变量W来表示某种临界资源的状态，来表示某种临界资源的状态， 71 1上锁原语：上锁原语：LOCKLOCK（W W） L1L1：如果：如果 W=1W=1那那 么转向么转向L1;L1;否则否则W=1 返回返回void lock(void lock(锁变量锁变量w) w) test: if (w test: if (w 为为1 1) ) goto test goto test else else w=1; / w=1; /* *上锁上锁* */ / / /* *

6、lock(w) lock(w) * */ / 1.考察锁位的值；考察锁位的值；2.如果原来的值为如果原来的值为0，将锁位，将锁位置置1；3.如果为如果为1，则返回第一步再，则返回第一步再次考察次考察82 2开锁原语：开锁原语：UNLOCKUNLOCK（W W） W=0;W=0;返回返回void unlock(锁变量锁变量w) w=0; /* 开锁开锁 */ /* unlock(w) */ v当进程使用完资当进程使用完资源后，它必须将锁源后，它必须将锁位置成位置成“0”，称为，称为开锁操作。开锁操作。9三、用上锁和开锁原语可以解决并三、用上锁和开锁原语可以解决并发进程的互斥发进程的互斥 任何欲进

7、入临界区的进程，必须先执行上锁原语。若任何欲进入临界区的进程，必须先执行上锁原语。若上锁原语上锁原语顺利顺利通过，则进程可通过，则进程可进入临界区进入临界区；当完成对临界区资源的访问后再执行；当完成对临界区资源的访问后再执行开开锁原语锁原语，以释放该临界资源。，以释放该临界资源。 即在相关进程的程序里由上锁和开锁原语紧夹着临界区，就能保证这些进程互斥地进入各自的临界区。 10例如，甲、乙两进程要访问同一类临界资源例如，甲、乙两进程要访问同一类临界资源 甲进程：甲进程： 其他代码；其他代码； LOCKLOCK（W W）；）； 甲进程的临界区；甲进程的临界区； UNLOCKUNLOCK（W W）；

8、）； 其他代码；其他代码； 乙进程乙进程： 其他代码；其他代码； LOCKLOCK（W W）；）； 乙进程的临界区；乙进程的临界区； UNLOCKUNLOCK（W W）；）； 其他代码；其他代码；v用上锁用上锁用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理机效率不高，因为上锁原语中的条件测试操作可能引起机效率不高，因为上锁原语中的条件测试操作可能引起CPU“忙等忙等”。 11信号量机制信号量机制 荷兰著名科学家，后来的计算机图灵奖获得者，荷兰著名科学家，后来的计算机图灵奖获得者，E.W.Dijkstra于于1965年提出了用作进程同

9、步年提出了用作进程同步工具的工具的信号量信号量（semaphore）机制机制，这是一，这是一种卓有成效的进程互斥同步工具，已被广泛应种卓有成效的进程互斥同步工具，已被广泛应用于现代计算机系统中。用于现代计算机系统中。 计科系姜云杰12进程的同步进程的同步(synchronism)(synchronism)： 你等我，我也等你你等我，我也等你 v多道程序系统中，许多进程之间可能存在以下多道程序系统中，许多进程之间可能存在以下两种制约关系：两种制约关系： v1.1.源于源于资源共享的资源共享的间接间接制约关系制约关系（互斥）（互斥） v2.2.源于源于合作相互的合作相互的直接直接制约关系制约关系（

10、同步）（同步）v后者即一种合作进程在独自并发执行过程中的某些确定的后者即一种合作进程在独自并发执行过程中的某些确定的时序点上时序点上“你等我，我也等你你等我，我也等你”的同步约束，前者可视为后的同步约束，前者可视为后者的特例（前面已经介绍）。者的特例（前面已经介绍）。计科系姜云杰13 1.1.资源共享关系资源共享关系 很多进程之间彼此无关，它们并不知道其它进程的存在。例如在分时系统中，系统分别为每个用户（终端）建立一个进程。但这些进程既然同处于一个系统中，也就必然存在着资源共享的关系，如共享CPU和I/O设备等。此时，进程的主要任务，是保证各个进程能互斥地访问临界资源。所以，系统中的资源应该不

11、允许用户进程直接使用，而应该由系统同一分配。例如：在仅有一台打印机的系统中，两个进程提出打印请求2.2.相互合作关系相互合作关系 例如输入进程、计算进程、打印进程合作完成一批数据的输入、计算和打印时的关系；中断响应过程；生活中下棋、看病时等化验结果等等。 计科系姜云杰14一、一、 同步的定义同步的定义 进程同步：进程同步：指的是两个或多个进程为了合作完成同一个任指的是两个或多个进程为了合作完成同一个任务，在执行速度或某些个确定的时序点上必须相互协调，务，在执行速度或某些个确定的时序点上必须相互协调，即一个进程的执行依赖于另一个进程即一个进程的执行依赖于另一个进程其合作伙伴的消其合作伙伴的消息，

12、当一个进程到达了某一确定点而没有得到合作伙伴发息，当一个进程到达了某一确定点而没有得到合作伙伴发来的来的“已完成某些操作已完成某些操作”的消息时必须等待，直到该消息的消息时必须等待，直到该消息到达被唤醒后，才能继续向前推进。到达被唤醒后，才能继续向前推进。v进程同步是多道程序系统中进程之间存在的一种主要进程同步是多道程序系统中进程之间存在的一种主要源于源于进程间合作的进程间合作的制约关系，也称制约关系，也称直接制约关系。直接制约关系。 计科系姜云杰15父子进程就是典型的合作进程父子进程就是典型的合作进程 ： 它们之间的同步关系有时也被形象地称为它们之间的同步关系有时也被形象地称为“生产者与生产

13、者与消费者消费者”之间的关系，之间的关系，“产品产品”（即生产者进程的输出，（即生产者进程的输出，亦即消费者进程的输入）是它们的纽带，它们在执行过程亦即消费者进程的输入）是它们的纽带，它们在执行过程中的某个或某些确定的时序点上有着固定的前趋后继的同中的某个或某些确定的时序点上有着固定的前趋后继的同步约束，即先步约束，即先“生产生产”后后“消费消费”，这是一种，这是一种“你等我你等我”的关系。的关系。 而在稍微复杂一点的进程同步问题里，合作进程间的而在稍微复杂一点的进程同步问题里，合作进程间的“生产者与消费者生产者与消费者”的关系或身份是可以经常转换的，因的关系或身份是可以经常转换的，因此，这些

14、合作进程在执行过程中就会出现时而你等我，时此，这些合作进程在执行过程中就会出现时而你等我，时而我等你的现象。而我等你的现象。 计科系姜云杰16进程同步和互斥间的关系：进程同步和互斥间的关系：相似处：相似处：进程的互斥实际上是进程同步的一种特殊进程的互斥实际上是进程同步的一种特殊 情况；情况； 进程的互斥和同步统称为进程同步。进程的互斥和同步统称为进程同步。差别：差别：是进程间共享资源的使用权是进程间共享资源的使用权 ，这种竞争没有，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时再归还；而直到不需要使用时再

15、归还；而则涉及共享资源的并则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。去使用这个资源。17信号量机制的基本原理是：信号量机制的基本原理是： v两个或多个进程可以利用彼此间收发的简单的信两个或多个进程可以利用彼此间收发的简单的信号来实现号来实现“正确的正确的”并发执行，一个进程在收到并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要一个指定信号前，会被迫在一个确定的或者需要的地方停下来

16、，从而保持同步或互斥。的地方停下来，从而保持同步或互斥。v经典的整型信号量经典的整型信号量经记录型信号量经记录型信号量信号量集机制信号量集机制CPU忙等忙等造成死锁造成死锁不易死锁，可不易死锁，可能导致资源利能导致资源利用率低用率低18一、一、 信号量的概念信号量的概念 信号量信号量，也叫信号灯信号灯，一般是由两个成员组成的数据结构，是一个确定的二元组（S，Q）S是个具有非负初值的整型变量整型变量，表示该信号量的值，且S的值只能由定义在信号量上的P操作原语和V操作原语来改变；Q是个初始状态为空的队列队列。 19另一定义：另一定义：v信号量类型是个复合类型，其一个分量是个整型分量信号量类型是个复

17、合类型，其一个分量是个整型分量S，另，另一个分量是个等待队列指针一个分量是个等待队列指针Q （一个是指向（一个是指向PCB的指针，的指针，当多个进程都等待同一信号量时，它们就排成一个队列，当多个进程都等待同一信号量时，它们就排成一个队列，由信号量的指针项指出该队列的头。）由信号量的指针项指出该队列的头。） v信号量通常可以简单反映出相应资源的使用情况，它与信号量通常可以简单反映出相应资源的使用情况，它与P，V操作原语一起使用可实现进程的同步和互斥。操作原语一起使用可实现进程的同步和互斥。 20信号量的定义：信号量的定义： Type semaphore=RECORD value: integer

18、; L: PCB pointer; END; VAR s: semaphore;21信号灯变量信号灯变量S.valueS. LS.valueS.LPCBPCBPCBVar S:semaphore;FIFO22* * *信号量的整型分量信号量的整型分量S S的值的物理含义：的值的物理含义： v当当S0S0时，表示某类可用资源的数目，或者说表时，表示某类可用资源的数目，或者说表示可以执行示可以执行P P操作而不会被阻塞的进程的数目；操作而不会被阻塞的进程的数目；v当当S S0 0时，其绝对值表示信号量时，其绝对值表示信号量S S的阻塞队列中的的阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进

19、进程数，即系统中因请求该类资源而被阻塞的进程的数目，亦即被信号灯挡住的进程数目，这些程的数目，亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。进程需要别的进程发出相应的信号灯来唤醒。 v另外，另外，S S的值只能由的值只能由P P、V V操作来改变。操作来改变。 二、二、P P（wait)wait)、V(singal)V(singal)操作原语操作原语 P P代表荷兰语的代表荷兰语的proberenproberen，意为，意为“测试测试”；V V代表荷兰语的代表荷兰语的verhogenverhogen，意为，意为“增加增加”。 现在很多国外的文献都使用现在很多国外的文献

20、都使用waitwait和和signalsignal操作（或者操作（或者downdown和和upup操作）代替操作）代替P P、V V操作。操作。 计科系姜云杰241定义在信号量定义在信号量S上的上的P（S）原语操作的算法描）原语操作的算法描述为：述为： （1 1）S S减减1 1；（2 2）若）若S S0 0，则调用，则调用P P（S S）的进程返回，继续）的进程返回，继续执行；执行；（3）若若SSS0 Block(Q) 返回YN26P(wait)操作原语操作原语Procedure wait(var s:semaphore)begin s.value:=s.value-1; If s.valu

21、e0 S0 ，则调用，则调用V V（S S）的进程继）的进程继续执行，续执行， 返回；返回；（3 3）若）若S0 SS S0 Wakeup(s.L) 返回YN29V(singal)操作原语操作原语Procedure V(var s:semaphore)Procedure V(var s:semaphore)beginbegin s.value:=s.value+1; s.value:=s.value+1; If s.value=0 Then If s.value=0; 只能执行只能执行P操作和操作和V操作，所有其它操作非法。操作，所有其它操作非法。 几个有用的结论几个有用的结论： 当当s.va

22、lue=0时，时，s.queue为空；为空； 当当s.value共享存储器系统共享存储器系统包括包括共享内存变量共享内存变量（如信号（如信号量机制）和量机制）和共享内存区共享内存区两种通信方式。两种通信方式。 =消息传递系统消息传递系统包括包括消息缓冲消息缓冲和和信箱信箱两种通信两种通信方式。方式。 =管道通信方式管道通信方式 共享存储器系统共享存储器系统计科系姜云杰75P1 P2OS提供：提供：（1）公共内存）公共内存（2）互斥同步机制）互斥同步机制消息传递系统消息传递系统计科系姜云杰76P1P2Msendreceive直接：进程直接：进程-进程进程间接：进程间接：进程-信箱信箱-进程进程直

23、接方式 对称形式(sender and receiver name each other) send(R,message) receive(S,message)Send(R,M).Receive(S,N).S:R:直接方式receive(pid,N).send(R,M1).send(R,M2). 非对称形式(only sender names receiver) send(R,message) receive(pid,message)C/S modelR:S1:S2:计科系姜云杰79发送原语（发送原语（send（接收者进程名，发送区首地址）（接收者进程名，发送区首地址）接收原语（接收原语（re

24、ceive（接收区首地址）（接收区首地址） send：当要进行消息传递时执行：当要进行消息传递时执行send receive：当接收者要接收消息时执行：当接收者要接收消息时执行receive 这是系统提供给用户实现进程通信的最基本的原这是系统提供给用户实现进程通信的最基本的原语，也是构成一种具体的通信系统的主要内容，用户语，也是构成一种具体的通信系统的主要内容，用户直接使用这些通信原语一次就能发送成千上万字节的直接使用这些通信原语一次就能发送成千上万字节的信息。信息。 计科系姜云杰80 消息（消息（message）：在计算机网络）：在计算机网络中又叫报文，指进程之间相互传递的赖以中又叫报文，指

25、进程之间相互传递的赖以发生相互作用的有结构的数据。发生相互作用的有结构的数据。 有缓冲途径PCBsend(R,M)size text .PCBreceive(pid,N) .M:N:msgmsgmsg.发送者发送者S:接收者接收者R:Message passing, direct,non-symmetric, bufferingSizetextsenderlink载有消息的缓冲：载有消息的缓冲：进程消息队列管理：进程消息队列管理： Var Sm:semaphore; (0) 收取消息前：收取消息前：P（Sm）; 消息入队后：消息入队后：V（Sm);消息队列互斥：消息队列互斥： Var m_mu

26、tex:semaphore;(1) P(m_mutex); 取取(放放)动作动作; V（m_mutex);间接方式MailboxSend_mb(mb,m)Receive_mb(mb,n).multi-sender - multi-receiver;multi-sender - one receiver计科系姜云杰84 所谓信箱通信方式是指连接两进程之间所谓信箱通信方式是指连接两进程之间的一个打开的共享文件，以文件作为缓冲的一个打开的共享文件，以文件作为缓冲传输介质，一个进程向其写入消息，另一传输介质，一个进程向其写入消息，另一个进程从中读取消息，好象是一个管道，个进程从中读取消息，好象是一个管

27、道，消息从一头流进，从另一头流出的通信方消息从一头流进，从另一头流出的通信方式。式。计科系姜云杰85 2.8 *死锁问题死锁问题* 你不让，我也不让你不让，我也不让 在多道程序系统中，多个进程并发运行，共享资源，从在多道程序系统中，多个进程并发运行，共享资源，从而提高了资源的利用率。但是若对资源的管理和使用不当，而提高了资源的利用率。但是若对资源的管理和使用不当，在一定条件下会导致系统发生一种随机性故障在一定条件下会导致系统发生一种随机性故障死锁。死锁。在一些系统中，比如实时控制系统，系统一旦发生死锁将在一些系统中，比如实时控制系统，系统一旦发生死锁将导致灾难性的后果。导致灾难性的后果。 死锁

28、问题是死锁问题是E.W.Dijkstra在在1965年研究银行家算法时年研究银行家算法时首次提出的，以后又由首次提出的，以后又由Havender、Lyach等人研究并发展。等人研究并发展。计科系姜云杰862.8.1.死锁的定义死锁的定义 死锁（死锁（Deadlock）：是指两个或两个以上的进是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。称此时系统象，若无外力作用，它们都将无法推进下去。称此时系统处于处于或或。 称这些永远在互相等待的进程为称这些永远在互相等待的进程为。 所占用的资

29、源或者需要它们进行某种合作的其它进程就会所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。相继陷入死锁，最终可能导致整个系统处于瘫痪状态。 计算机系统中，如果系统的资源分配策略不当，或者更计算机系统中，如果系统的资源分配策略不当，或者更常见的是程序员写的程序有错误等，则会导致进程因竞争常见的是程序员写的程序有错误等，则会导致进程因竞争资源不当（往往与进程的推进速度有关）而产生死锁的现资源不当（往往与进程的推进速度有关）而产生死锁的现象。象。 在计算机系统中有很多独占性的资源，在任一时刻，在计算机系统中有很多独占性的资源，在任一时刻，它们都只能被一

30、个进程使用。常见的有打印机、磁带驱动它们都只能被一个进程使用。常见的有打印机、磁带驱动器等。例如：两个进程同时打印会引起打印混乱。器等。例如：两个进程同时打印会引起打印混乱。 鉴于此，操作系统全都具有授权一进程（临时）独占鉴于此，操作系统全都具有授权一进程（临时）独占地访问某一种资源的能力。地访问某一种资源的能力。 计科系姜云杰88 例如例如:将一个大文件由磁带拷贝至打印机，进程需要将一个大文件由磁带拷贝至打印机，进程需要同时访问磁带驱动器和打印机，并且不允许其他进程这时同时访问磁带驱动器和打印机，并且不允许其他进程这时访问它们。在只有一个进程的系统中，该进程可以要求任访问它们。在只有一个进程

31、的系统中，该进程可以要求任何它所需要的资源，然后进行工作。但是，在一个多道程何它所需要的资源，然后进行工作。但是，在一个多道程序系统中，就有可能出现严重的问题。序系统中，就有可能出现严重的问题。 计科系姜云杰89A、B两个进程准备打印一个大的磁带文件两个进程准备打印一个大的磁带文件ABR1R2打印机打印机磁带机磁带机计科系姜云杰90以哲学家就餐问题为例来说明一下死锁： 该问题的描述如下：有该问题的描述如下：有5个哲学家，围坐在圆桌旁，个哲学家，围坐在圆桌旁，他们的生活方式是交替地进行思考和进餐；圆桌上他们的生活方式是交替地进行思考和进餐；圆桌上间隔地摆放着间隔地摆放着5把叉子和把叉子和5个装有

32、通心粉的盘子，个装有通心粉的盘子，规定第规定第i号哲学家固定坐在第号哲学家固定坐在第i把椅子上把椅子上（i=0,1,2,3,4），且每个哲学家必须两手分别拿），且每个哲学家必须两手分别拿起他左右两旁的那两把叉子，才能吃通心粉；假定起他左右两旁的那两把叉子，才能吃通心粉；假定通心粉的数量足够通心粉的数量足够5个哲学家用的。个哲学家用的。 假设这假设这5把叉子与椅子相应也按逆时针方向把叉子与椅子相应也按逆时针方向从从0开始连续编号，即第开始连续编号，即第i号哲学家左边摆着第号哲学家左边摆着第i号号叉子，右边摆着第叉子，右边摆着第(i+1)mod 5)号叉子，这里的号叉子，这里的mod代表模运算，即

33、整除取余。代表模运算，即整除取余。 显然，在这个问题中叉子是哲学家进餐竞争显然，在这个问题中叉子是哲学家进餐竞争的临界资源，的临界资源，5把叉子应分别用一个初值为把叉子应分别用一个初值为1的信的信号量表示，这号量表示，这5个信号量构成一个信号量数组个信号量构成一个信号量数组S.则第则第i号哲学家的进餐过程可以描述如下：号哲学家的进餐过程可以描述如下： 哲学家（哲学家（I0，1，2，3，4）思考；思考；P(Si);拿起左边的叉子；拿起左边的叉子；P(Si1mod5)；拿起右边的叉子；拿起右边的叉子；吃通心粉；吃通心粉；放下左边的叉子；放下左边的叉子；V(Si);放下右边的叉子；放下右边的叉子；V

34、(Si1mod5)； 这种算法将这种算法将产生死锁产生死锁下面就是一个不会出现死锁的哲学家进餐过程的算法描述。下面就是一个不会出现死锁的哲学家进餐过程的算法描述。 哲学家（哲学家（I0，1，2，3，4）思考；思考；P(mutex);P(Si);拿起左边的叉子；拿起左边的叉子；P(Si1mod5)；拿起右边的叉子；拿起右边的叉子；吃通心粉；吃通心粉；放下左边的叉子；放下左边的叉子；V(Si);放下右边的叉子；放下右边的叉子；V(Si1mod5)；V(mutex) （1）竞争临界资源竞争临界资源 当系统中供多个进程共享的临界资源（如打印机、公当系统中供多个进程共享的临界资源（如打印机、公用队列等）

35、的数目不能满足诸进程的需要时，会引起诸进程用队列等）的数目不能满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。这个问题在多道程序系统中是无对资源的竞争而产生死锁。这个问题在多道程序系统中是无法解决的。法解决的。 （2）进程推进顺序不当进程推进顺序不当 进程在运行过程中，请求和释放资源的顺序不当，也同进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁的产生。这个问题在多道程序系统中是可以解样会导致死锁的产生。这个问题在多道程序系统中是可以解决的。决的。 计科系姜云杰95一、竞争资源引起死锁一、竞争资源引起死锁 1资源的分类：可剥夺和非剥夺性资源资源的分类：可剥夺和非剥夺性资源：

36、 CPU和主存和主存 例如：优先权高的程可以剥夺低优先权进程的处理机。又如：内存例如：优先权高的程可以剥夺低优先权进程的处理机。又如：内存区可由存储器管理程序把进城从一个存储区移至另外一个存储区，即剥区可由存储器管理程序把进城从一个存储区移至另外一个存储区，即剥夺了该进城原来占有的存储区，甚至可以将一进程从内存调出到外存上。夺了该进城原来占有的存储区，甚至可以将一进程从内存调出到外存上。：磁带机、打印机等：磁带机、打印机等 当系统把这类资源分配给某进程后，再不能强行收回，只能在进当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。程用完后自动释放。 2竞争非剥夺性资源竞争

37、非剥夺性资源 两个进程分别准备打印一个非常大的磁带文件（两个进程分别准备打印一个非常大的磁带文件（双方都拥双方都拥有部分资源，同时在请求对方已占有的资源。）有部分资源，同时在请求对方已占有的资源。）3竞争临时性资源竞争临时性资源永久性资源永久性资源：打印机资源输入可顺序重复使用的资源。：打印机资源输入可顺序重复使用的资源。临时性资源临时性资源：由一个进程产生，被另一个进程使用一短暂时：由一个进程产生，被另一个进程使用一短暂时间后便无用的资源。间后便无用的资源。 打印机R1磁带机R2P1P2计科系姜云杰97二、进程推进顺序不当引起死锁二、进程推进顺序不当引起死锁 资源资源少也未必一定产生死锁。就

38、如同两个人过独木桥，少也未必一定产生死锁。就如同两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了。那么问题就解决了。 所以，如果程序设计得不合理，造成进程推进的顺序不所以，如果程序设计得不合理，造成进程推进的顺序不当，也会出现死锁。当，也会出现死锁。 计科系姜云杰98 1互斥条件：互斥条件： 每一资源被分配给每

39、一资源被分配给一个进程一个进程，或者空闲。，或者空闲。 2占有并请求条件：占有并请求条件： 已分配到了一些资源的进程可以申请新的资源。已分配到了一些资源的进程可以申请新的资源。 3不可剥夺条件：不可剥夺条件： 进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。 4循环等待条件：循环等待条件： 链中的每一个进程都在等待相邻进程所占用的资源。链中的每一个进程都在等待相邻进程所占用的资源。2.8.3 2.8.3 产生死锁

40、的必要条件产生死锁的必要条件 计科系姜云杰992.8.4 2.8.4 死锁的解决办法：死锁的解决办法： 死锁的预防；死锁的预防； 死锁的避免；死锁的避免； 死锁的检测和恢复；死锁的检测和恢复； 鸵鸟算法鸵鸟算法 当死锁在计算机中很少出现时，比如说每五年或更当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。决它，而是采用类似鸵鸟一样的办法忽略它。计科系姜云杰100v这种办法是在系统运行之前就采取措施，即在系统设这种办法是在系统运行之前就采取措施，即在系统设计时确定资源

41、分配算法，消除发生死锁的任何可能性。计时确定资源分配算法，消除发生死锁的任何可能性。v该方法虽然比较保守、资源利用率低，但因简单明了该方法虽然比较保守、资源利用率低，但因简单明了并且安全可靠，仍被广泛采用。并且安全可靠，仍被广泛采用。v产生死锁的四个必要条件中，互斥条件由设备的固有产生死锁的四个必要条件中，互斥条件由设备的固有特性所决定的，不仅不能改变，相反还应加以保证，因特性所决定的，不仅不能改变，相反还应加以保证，因此实际上只有三种方法。此实际上只有三种方法。一、死锁的防止一、死锁的防止 计科系姜云杰1011静态资源分配法（摒弃静态资源分配法（摒弃“占有并请求条件占有并请求条件”） v系统

42、规定每一个进程在开始运行前，都必须一系统规定每一个进程在开始运行前，都必须一次性地申请其在整个运行过程所需的全部资源。次性地申请其在整个运行过程所需的全部资源。此时，若系统有足够的资源，便把进程想要的此时，若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。这进程的资源请求，则一个资源也不分给它。这样，进程在运行过程中就不会再提出资源请求，样，进程在运行过程中就不会再提出资源请求，从而破坏了占有与请求条件。从而破坏了占有与请求条件。 计科系姜云杰102静态资源分配法的优缺点：静态资源分配法的优缺

43、点： 优点：简单、安全、易实现。优点：简单、安全、易实现。缺点：缺点： （1）资源被严重浪费）资源被严重浪费（因为一个进程一次获得其所需因为一个进程一次获得其所需的全部资源并且独占，其中有可能有些资源很少使用，的全部资源并且独占，其中有可能有些资源很少使用，严重恶化了资源利用率严重恶化了资源利用率）。）。 （2）进程延迟运行。）进程延迟运行。（当且仅当进程获得其所需的全当且仅当进程获得其所需的全部资源后，才能开始运行，但有可能有些资源长期被其部资源后，才能开始运行，但有可能有些资源长期被其他进程占用，致使需要该资源的进程迟迟不能运行他进程占用，致使需要该资源的进程迟迟不能运行） 计科系姜云杰1

44、032摒弃摒弃“不可剥夺条件不可剥夺条件” 进程在需要资源时才提出请求。即：一个已经保持了某些进程在需要资源时才提出请求。即：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后再需要时足时，必须释放它已经保持的所有资源，待以后再需要时再重新申请。再重新申请。 实现起来比较复杂，且要付出很大的代价。实现起来比较复杂，且要付出很大的代价。 进程的周转时间较长，系统开销大。进程的周转时间较长，系统开销大。 计科系姜云杰1043有序资源使用法（摒弃有序资源使用法（摒弃“循环等待条件循环等待条件

45、”） v系统中的所有资源按类都被赋予一个唯一的编号，每个进系统中的所有资源按类都被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。即对同一个进程而言，它程只能按编号的升序申请资源。即对同一个进程而言，它一旦申请了一个编号为一旦申请了一个编号为i的资源，就不允许再申请编号比的资源，就不允许再申请编号比i小的资源了，因此，破坏了循环等待条件。小的资源了，因此，破坏了循环等待条件。v优点：安全且资源利用率比静态资源分配法有所提高，因优点：安全且资源利用率比静态资源分配法有所提高，因为它实际是一种半动态的资源分配法。为它实际是一种半动态的资源分配法。v缺点：实现较困难，因为难给出合适的资源编号，

46、不便于缺点：实现较困难，因为难给出合适的资源编号，不便于系统增添新设备，不便于用户编程，且仍有一定的资源浪系统增添新设备，不便于用户编程，且仍有一定的资源浪费现象费现象计科系姜云杰105二、二、 死锁的避免死锁的避免 死锁的避免是这样一种对付死锁的办法：系统在运行死锁的避免是这样一种对付死锁的办法：系统在运行过程中采取动态的资源分配策略，保证系统不进入可能导过程中采取动态的资源分配策略，保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态，以避免死锁发生。致系统陷入死锁状态的所谓不安全状态，以避免死锁发生。 死锁的避免与死锁防止策略不同，它不对进程申请资死锁的避免与死锁防止策略不同，它不对进

47、程申请资源加任何限制，而是对进程提出的每一次资源请求进行动源加任何限制，而是对进程提出的每一次资源请求进行动态检查，并根据检查结果决定是否分配资源以满足进程的态检查，并根据检查结果决定是否分配资源以满足进程的请求。由于采用了动态的资源分配策略，所以资源利用率请求。由于采用了动态的资源分配策略，所以资源利用率比死锁的防止办法高。比死锁的防止办法高。 计科系姜云杰106(一一)系统的状态系统的状态 若在某一时刻，系统中存在某种进程序列，如若在某一时刻，系统中存在某种进程序列，如，如果系统按此序列为每个进程分配其所需，如果系统按此序列为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成。

48、则称此的资源，直至最大需求，使每个进程均可顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列时系统的状态为安全状态，称这样的一个进程序列为安全序列。为安全序列。 安全序列的实质是：序列中的每一个进程安全序列的实质是：序列中的每一个进程Pi（i=1,2,n）到以后运行完成尚需要的资源量不超过系统）到以后运行完成尚需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。占有的资源量之和。 计科系姜云杰107 若在某一时刻，系统中不存在一个安全序列，若在某一时刻，系统中不存在一个安全序列，则称系统处于不

49、安全状态。则称系统处于不安全状态。 安全状态的例子安全状态的例子例：假定系统有三个进程例：假定系统有三个进程P1、P2、P3，共有，共有12台磁带机。台磁带机。进程进程P1总共要求总共要求10台磁带机，台磁带机，P2和和P3分别要求分别要求4台和台和九台。设在九台。设在T0时刻，进程时刻，进程P1、P2和和P3已经获得已经获得5台、台、2台和台和2台，还有台，还有3台空闲没有分配台空闲没有分配。进程最大需求已分配可用P11053P2P34229T0时刻系统时安全的。这时存在一个安全序列计科系姜云杰109注意：注意： （1）系统在某一时刻的安全状态可能不唯一，但这不）系统在某一时刻的安全状态可能

50、不唯一，但这不影响对系统安全性的判断。影响对系统安全性的判断。（2）安全状态是非死锁状态，而不安全状态并不一定）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅可能进入死锁状态。而系统处于不安全状态则仅仅可能进入死锁状态。 安全状态安全状态不安全状态不安全状态死锁状态死锁状态计科系姜云杰110银行家算法银行家算法银行家算法是最有代表性的避免死锁算法，是银行家算法是最有代表性的避免死锁算法，是Dijkstra提出的。提出的。其模型基于一个小城镇的银行家，他向一群客其模型基于一个小城

51、镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。在这里，我们可将客户比户同时都需要最大的贷款额。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是对每一作进程，银行家比作操作系统。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不个客户的请求进行检查，检查如果满足它是否会引起不安全状态。假如是，那么不满足该请求；否，那么便满安全状态。假如是，那么不满足该请求；否，那么便满足。足。计科系姜云杰111银行家算法的实质就是 : 要设法保证系统动态分配资源后不进入不要设法保证

52、系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。安全状态，以避免可能产生的死锁。 即：每当进程提出资源请求且系统的资源即：每当进程提出资源请求且系统的资源能够满足该请求时，系统将判断如果满足能够满足该请求时，系统将判断如果满足此次资源请求系统状态是否安全，如果判此次资源请求系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。则不分配资源，申请资源的进程将阻塞。 v银行家算法的执行有个前提条件，即要求进程预银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并且假设系统拥有先提出自己的最大资

53、源请求，并且假设系统拥有固定的资源总量。固定的资源总量。v银行家算法中所用的主要的数据结构如下：银行家算法中所用的主要的数据结构如下： v(1)可利用资源向量Available （剩余或可用资源量），记录系统中各类资源的当前可利用数目。如果Availablej=k， 表示系统中现有Rj类资源k个。 (2) 最大需求矩阵最大需求矩阵Max 每个进程对各类资源的最大需求量每个进程对各类资源的最大需求量 (3)Allocation 已为每个进程分配的数量或者说每个进程对各类已为每个进程分配的数量或者说每个进程对各类资源当前的占有量。资源当前的占有量。 (4)需求矩阵需求矩阵Need 某某进程对各类资

54、源尚需要的数目。进程对各类资源尚需要的数目。 Need=MaxAllocation (5)请求向量请求向量Request 它记录某个进程当前对各类资源的申请量，是银行家它记录某个进程当前对各类资源的申请量，是银行家算法的入口参数。算法的入口参数。 当当Pi发出资源请求后，系统按下述步骤进行检查：发出资源请求后，系统按下述步骤进行检查：1.如果如果Requesti Needi,则出错。则出错。2.如果如果Requesti Available,则则Pi 阻塞阻塞； 3.系统试探把要求的资源分配给进程系统试探把要求的资源分配给进程Pi，并修改下面数据结，并修改下面数据结构中的数值：构中的数值：Ava

55、ilablei=Availablei-Requesti; Allocationi=Allocationi+Requesti; Needi = Needi- Requesti;4. 系统执行安全性算法，检查此次资源分配后，系统是否处系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程于安全状态。若安全，正式将资源分配给进程Pi，以完成，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程状态，让进程Pi等待。等待。 1.1.设置两个向量设置两个向量 工作向量工作向量Work.Work. 表示系

56、统可提供给进程继续运行所需要的各类资源的数表示系统可提供给进程继续运行所需要的各类资源的数目，开始时，目，开始时，Work:=AvailableWork:=Available。 Finish.Finish. 它表示系统是否有足够的资源分配给进程，使之运行完它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做成。开始时先做Finishi:=falseFinishi:=false；当有足够的资源分配；当有足够的资源分配给进程时，令给进程时，令Finishi:=true.Finishi:=true.2.2.执行过程的描述：执行过程的描述：(1)初始化：初始化：work=work=avail

57、ableavailable；finish=falsefinish=false；(2)若按进行编号顺序找到了一个可加入安全序列的进程若按进行编号顺序找到了一个可加入安全序列的进程 即：满足条件即：满足条件finishfinishi i=false=false且且 needneedi iworkwork的进程的进程P Pi i 则假设该进程不久将完成任务归还资源，置则假设该进程不久将完成任务归还资源，置 重复执行这一步重复执行这一步；(3)若所有进程的可完成标志若所有进程的可完成标志finishfinish为真，则返回逻辑真值为真，则返回逻辑真值 （表示系统处于安全状态）；（表示系统处于安全状态）

58、；(4)否则，返回逻辑假值（表示不安全）；否则，返回逻辑假值（表示不安全）； 计科系姜云杰117可以看出：可以看出： 银行家算法从避免死锁的角度上说是非常有效的，但银行家算法从避免死锁的角度上说是非常有效的，但是，从某种意义上说，它缺乏实用价值，因为很少有是，从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能

59、坏掉）。因此，在实际中，成不可用（如磁带机可能坏掉）。因此，在实际中，如果有，也只有极少的系统使用银行家算法来避免死如果有，也只有极少的系统使用银行家算法来避免死锁。锁。 计科系姜云杰118银行家算法之例银行家算法之例 假定系统中有四个进程假定系统中有四个进程P1、P2、P3、P4和三种类型的和三种类型的资源资源R1，R2，R3，资源的数量分别为，资源的数量分别为9、3、6，在，在T0时刻的资源分配情况如图时刻的资源分配情况如图:资源情况资源情况进程进程MaxR1 R2 R3AllocationR1 R2 R3NeedR1 R2 R3AvailableR1 R2 R3 P1 3 2 2 1 0

60、 0 2 2 2 1 1 2 P2 6 1 3 5 1 1 1 0 2 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0T0时刻时刻是否安是否安全？全？资源情况资源情况进程进程MaxR1 R2 R3AllocationR1 R2 R3NeedR1 R2 R3AvailableR1 R2 R3 P1 3 2 2 1 0 0 2 2 2 1 1 2 P2 6 1 3 5 1 1 1 0 2 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0资源情况资源情况进程进程WorkR1 R2 R3NeedR1 R2 R3AllocaR1 R2