第4章-进程同步与死锁

1、 进程同步和互斥，临界资源及临界区进程同步和互斥，临界资源及临界区的概念的概念 实现进程互斥的方法实现进程互斥的方法 信号量机制与信号量机制与P、V操作操作 一些经典的进程同步问题一些经典的进程同步问题 利用管程实现进程同步利用管程实现进程同步 进程的死锁及处理机制进程的死锁及处理机制 Linux系统的进程同步及死锁系统的进程同步及死锁2 并发性并发性 操作系统基本特征，改善系统资源的利用率，操作系统基本特征，改善系统资源的利用率，提高系统的吞吐量提高系统的吞吐量 指一组进程执行在时间点上相互交替，在时指一组进程执行在时间点上相互交替，在时间段上重叠间段上重叠 与时间有关的错误与时间有关的错误

2、 多进程并发情况下，进程共享某些变量或硬多进程并发情况下，进程共享某些变量或硬件资源，进程的执行具有不确定性，如果不件资源，进程的执行具有不确定性，如果不对进程的执行加以制约，执行结果是错误的对进程的执行加以制约，执行结果是错误的3 进程的同步进程的同步 指当进程运行到某一点时，若其他进程已完成某种指当进程运行到某一点时，若其他进程已完成某种操作，使进程满足了继续运行的条件，进程才能够操作，使进程满足了继续运行的条件，进程才能够继续运行，否则必须停下来等待继续运行，否则必须停下来等待 相互协作的进程间经常存在数据或变量等共享资源，相互协作的进程间经常存在数据或变量等共享资源，进程受到特定条件的

3、限制，各进程需要严格按照固进程受到特定条件的限制，各进程需要严格按照固定的顺序执行，否则将导致程序的执行错误定的顺序执行，否则将导致程序的执行错误 进程的互斥进程的互斥 互斥共享资源是指在某段时间内，只能有一个进程互斥共享资源是指在某段时间内，只能有一个进程对该资源进行访问，其他进程若想访问该资源则必对该资源进行访问，其他进程若想访问该资源则必须停下来等待，直到该共享资源被前一进程释放须停下来等待，直到该共享资源被前一进程释放4 临界资源临界资源 只允许一个进程访问的共享资源只允许一个进程访问的共享资源 物理设备：打印机、绘图仪物理设备：打印机、绘图仪 变量、数据、文件、内存区变量、数据、文件

4、、内存区 临界区临界区 程序中对临界资源访问的代码程序中对临界资源访问的代码 临界资源程序：入口区、临界区、退出区、其余代临界资源程序：入口区、临界区、退出区、其余代码区码区 临界区访问准则：临界区访问准则：p 空闲让进空闲让进p 忙则等待忙则等待p 有限等待有限等待p 让权等待让权等待5 管理临界区管理临界区入口入口标志两个操作标志两个操作 查看标志以判断临界资源是否已被占用；查看标志以判断临界资源是否已被占用； 修改标志阻止其他进程进入临界区；修改标志阻止其他进程进入临界区； 并发进程交错执行时，可能会出现进程只执行一个操作并发进程交错执行时，可能会出现进程只执行一个操作就被另一个进程打断

5、的情况，从而造成临界资源访问发就被另一个进程打断的情况，从而造成临界资源访问发生错误；生错误； 主要思想主要思想 用一条指令来完成标志的检查和修改两个操作，保用一条指令来完成标志的检查和修改两个操作，保证两个操作不被打断；证两个操作不被打断； 通过禁止中断的方式来保证检查和修改作为一个整通过禁止中断的方式来保证检查和修改作为一个整体来执行；体来执行；6 禁止中断禁止中断 进程使用禁止中断的方法构成临界区的入口区，使进程使用禁止中断的方法构成临界区的入口区，使用打开中断的方法构成临界区退出区用打开中断的方法构成临界区退出区 不足：不足：u如果临界区访问时间过长，关中断时间过长，限如果临界区访问时

6、间过长，关中断时间过长，限制处理器交叉执行程序的能力，影响系统效率；制处理器交叉执行程序的能力，影响系统效率；u将关中断的权利交给用户进程，可能会引起计算将关中断的权利交给用户进程，可能会引起计算机响应不及时，使重要的中断程序不能及时处理；机响应不及时，使重要的中断程序不能及时处理；u在多处理器系统，通过关中断阻止进程在临界区在多处理器系统，通过关中断阻止进程在临界区执行不被中断没有意义；执行不被中断没有意义；7 专用机器指令：专门硬件指令，用一条指令完成检查和专用机器指令：专门硬件指令，用一条指令完成检查和改写两个操作改写两个操作 TS（Test-and-Set）指令：检查指定标志后把该）指

7、令：检查指定标志后把该标志置位标志置位TS(key)while(!TS(key);临界区；临界区；if(key = 1)key = 0；return 0;else key = 1;return 1;8 专用机器指令：专门硬件指令，用一条指令完成检查和专用机器指令：专门硬件指令，用一条指令完成检查和改写两个操作改写两个操作 Swap指令：交换两个字节的内容指令：交换两个字节的内容Swap(a,b)x = 1;while(x != 0)temp = a;swap(&key, &x);a = b;临界区；临界区；b = temp;key = 0;9 优点：优点： 适用范围广，可用于多

8、个并发进程及单处理器或多处理器环适用范围广，可用于多个并发进程及单处理器或多处理器环境；境； 方法简单，只需要硬件指令即可实现；方法简单，只需要硬件指令即可实现； 支持多个临界区，可为每个临界区设置单独标志，在支持的支持多个临界区，可为每个临界区设置单独标志，在支持的临界区的个数上没有限制；临界区的个数上没有限制； 缺点：缺点： 易出现忙等待，在进程无法进入临界区时会对标志进行循环易出现忙等待，在进程无法进入临界区时会对标志进行循环测试，耗费大量处理器资源；测试，耗费大量处理器资源； 可能产生进程饥饿现象，某个进程释放临界资源后，下一个可能产生进程饥饿现象，某个进程释放临界资源后，下一个进入临

9、界区的进程不确定，从而可能会产生有的进程长期无进入临界区的进程不确定，从而可能会产生有的进程长期无法进入临界区的情况；法进入临界区的情况；10 20世纪世纪60年代开始利用软件方法解决临界区互斥访问问年代开始利用软件方法解决临界区互斥访问问题研究；题研究； 方法主要基于内存级别的访问互斥，通过内存中的标志方法主要基于内存级别的访问互斥，通过内存中的标志位实现并发进程对临界资源的顺序访问；位实现并发进程对临界资源的顺序访问； 算法算法1：利用共享的标志位来表示哪个并发进程可以进：利用共享的标志位来表示哪个并发进程可以进入临界区：设置标志变量，变量为入临界区：设置标志变量，变量为0允许进程允许进程

10、A进入，变进入，变量为量为1允许进程允许进程B进入；进入；int turn = 0;进程进程A:进程进程B:while(turn != 0);while(turn != 1);临界区临界区;临界区临界区;turn = 1;turn = 0; 违反违反“空闲让进空闲让进”原则原则11算法算法2：利用双标志法判断进程是否进入临界区：使用数组表示进：利用双标志法判断进程是否进入临界区：使用数组表示进程是否希望进入临界区，真正进入临界区之前先查看一下对方标志，程是否希望进入临界区，真正进入临界区之前先查看一下对方标志，如果对方正在进入临界区则进行等待，还需要通过一个变量避免两如果对方正在进入临界区则进

11、行等待，还需要通过一个变量避免两个进程都无法进入临界区个进程都无法进入临界区int flag2 = 0,0;进程进程A:进程进程B:flag0 = 1;flag1 = 1;turn = 1;turn = 0;while(flag1&turn = 1);while(flag0&turn = 0);临界区临界区;临界区临界区;flag0 = 0;flag1 = 0;12信号量信号量 荷兰科学家荷兰科学家Dijkstra在在1965年提出，进程同步机制；年提出，进程同步机制； 概念上类似交通信号灯，通过信号量的状态来决定并发概念上类似交通信号灯，通过信号量的状态来决定并发进程对临界资

12、源的访问顺序；进程对临界资源的访问顺序； 多进程间传递简单信号，使进程在某位置阻塞，直到收多进程间传递简单信号，使进程在某位置阻塞，直到收到特定信号后继续运行，达到多进程相互协作的目的；到特定信号后继续运行，达到多进程相互协作的目的； 包含包含“检测检测”和和“归还归还”两个操作：检测操作称为两个操作：检测操作称为P操操作，查看是否可访问临界资源，若检测通过，则开始访作，查看是否可访问临界资源，若检测通过，则开始访问临界资源，若检测不通过，则进行等待，直到临界资问临界资源，若检测不通过，则进行等待，直到临界资源被归还后才能进入临界区访问；归还操作称为源被归还后才能进入临界区访问；归还操作称为V

13、操作，操作，通知等待进程临界资源已经被释放；通知等待进程临界资源已经被释放； P操作与操作与V操作都是原子操作，每个步骤不可分割，操作都是原子操作，每个步骤不可分割，“要要么都做，要么都不做么都做，要么都不做”；13信号量（续）信号量（续） 实现进程互斥访问临界资源的模型：实现进程互斥访问临界资源的模型：进程进程1：进程进程2：进程进程3：P(mutex);P(mutex);P(mutex);临界区临界区;临界区临界区;临界区临界区;V(mutex);V(mutex);V(mutex); 实现进程间同步的模型：实现进程间同步的模型：进程进程1：进程进程2：读入数据读入数据;P(mutex);V

14、(mutex);处理数据处理数据;14整型信号量机制整型信号量机制 最简单的一种信号量，通常是一个需要初最简单的一种信号量，通常是一个需要初始化值的正整型量；始化值的正整型量； 操作原语如下：操作原语如下：P操作：操作：V操作：操作：P(x)V(x)while(x = 0);x = x + 1;x = x - 1;15记录型信号量机制记录型信号量机制 整型信号量在整型信号量在P操作不成功时需要进行循环等待，没有操作不成功时需要进行循环等待，没有放弃放弃CPU资源，违背让权等待原则，造成系统资源浪费；资源，违背让权等待原则，造成系统资源浪费； 记录型信号量在整型信号量基础上进行改进，包含整型记录

15、型信号量在整型信号量基础上进行改进，包含整型值外，还包含一个阻塞队列；值外，还包含一个阻塞队列； 操作原语如下：操作原语如下：P操作：操作：V操作：操作：P(x)V(x) x.value=x.value -1; x.value=x.value + 1; if(x.value 0) if(x.value =0&x2=0&.xn=0)for(i=0;in;+i)xi=xi-1;else在队列中阻塞在队列中阻塞;18AND型信号量机制（续型信号量机制（续2）SV(x1,x2,.,xn)for(i=0;in;+i)xi=xi+1;唤醒队列中进程唤醒队列中进程;19生产者生产者-消费者问

16、题消费者问题 最著名进程同步问题，一组生产者进程向一组消费者进最著名进程同步问题，一组生产者进程向一组消费者进程提供产品，共享一个环形缓冲池；程提供产品，共享一个环形缓冲池； 缓冲池每个缓冲区存放一个产品，生产者进程不断生产缓冲池每个缓冲区存放一个产品，生产者进程不断生产产品并放入缓冲池，消费者进程不断从缓冲池取出产品产品并放入缓冲池，消费者进程不断从缓冲池取出产品并消费；并消费； 进程满足同步条件：进程满足同步条件： 任一时刻所有生产者存放产品的单元数不能超过缓冲池的总任一时刻所有生产者存放产品的单元数不能超过缓冲池的总容量容量N； 所有消费者取出产品的总量不能超过所有生产者当前生产产所有消

17、费者取出产品的总量不能超过所有生产者当前生产产品的总量；品的总量；20生产者生产者-消费者问题（续消费者问题（续1） 同步关系：同步关系：当缓冲池满时生产者进程需等待；当缓冲池满时生产者进程需等待；当缓冲池空时消费者进程需等待；当缓冲池空时消费者进程需等待；各个进程应互斥使用缓冲池；各个进程应互斥使用缓冲池； 使用信号量解决问题。假设缓冲区编号使用信号量解决问题。假设缓冲区编号0（N-1），用），用in和和out作为生产者和消费者进程使用的指针，指向可用作为生产者和消费者进程使用的指针，指向可用的缓冲区，初值都是的缓冲区，初值都是0。设置。设置3个信号量：个信号量：full，表示放有产品的缓冲

18、区数，初值为，表示放有产品的缓冲区数，初值为0；empty，表示可供使用的缓冲区数，初值为，表示可供使用的缓冲区数，初值为N；mutex，互斥信号量，初值为，互斥信号量，初值为1，使各进程互斥进入临界区，保证任何时候，使各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区；只有一个进程使用缓冲区；21生产者生产者-消费者问题（续消费者问题（续2）算法描述：算法描述：/生产者进程生产者进程 /消费者进程消费者进程while(1) while(1) P(empty); P(full); P(mutex); P(mutex); 产品送往产品送往buffer(in); 从从buffer(out)取

19、出产品取出产品; in=(in+1)%N; out=(out+1)%N; V(mutex); V(mutex); V(full); V(empty); 生产者进程利用信号量生产者进程利用信号量empty保证在具有空闲的缓冲区时才将产品保证在具有空闲的缓冲区时才将产品放入缓冲池，消费者进程利用信号量放入缓冲池，消费者进程利用信号量full保证只有在缓冲区存在产保证只有在缓冲区存在产品时才会取出，信号量品时才会取出，信号量mutex保证生产者及消费者进程对缓冲池的保证生产者及消费者进程对缓冲池的互斥访问。互斥访问。22读者读者-写者问题写者问题 一个数据对象（如文件或记录）可以被多个并发进程共一个

20、数据对象（如文件或记录）可以被多个并发进程共享，有些进程只要求读取数据对象的内容，另一些进程享，有些进程只要求读取数据对象的内容，另一些进程则要求修改数据对象的内容；则要求修改数据对象的内容； 允许多个读进程同时访问数据对象，但写进程不能与其允许多个读进程同时访问数据对象，但写进程不能与其他进程同时访问数据对象；他进程同时访问数据对象； 举例，大型数据库系统；举例，大型数据库系统； 根据写者到来后是否仍允许新读者进入分类：根据写者到来后是否仍允许新读者进入分类： 读者优先：当写者提出存取共享对象的需求后，仍允许新读读者优先：当写者提出存取共享对象的需求后，仍允许新读者进入；者进入； 写者优先：

21、当写者提出存取共享对象的需求后，不允许新读写者优先：当写者提出存取共享对象的需求后，不允许新读者进入；者进入；23读者读者-写者问题（续写者问题（续1） 使用信号量解决问题。需要设置两个信号量和一个共享使用信号量解决问题。需要设置两个信号量和一个共享变量：变量：读互斥信号量读互斥信号量rmutex，用于使读进程互斥访问共享变量，用于使读进程互斥访问共享变量readcount，其初，其初值为值为1；读写互斥信号量读写互斥信号量mutex，用于实现写进程与读进程的互斥以及写进程与写，用于实现写进程与读进程的互斥以及写进程与写进程的互斥，其初值为进程的互斥，其初值为1；读共享变量读共享变量readc

22、ount，用于记录当前的读进程数目，初值为，用于记录当前的读进程数目，初值为0；24读者读者-写者问题（续写者问题（续2）算法描述：（读者优先）算法描述：（读者优先）/读者进程读者进程 /写者进程写者进程while(1) while(1) P(rmutex); P(mutex); readcount=readcount+1; 执行写操作执行写操作; if(readcount=1) V(mutex); P(mutex); V(rmutex); 执行读操作执行读操作; P(rmutex); readcount=readcount-1; if(readcount=0) V(mutex); V(rmu

23、tex); 使用读取的数据使用读取的数据;25读者读者-写者问题（续写者问题（续3） 上述算法基础上，增加上述算法基础上，增加3个信号量和一个共享变量解决个信号量和一个共享变量解决写者优先的读者写者优先的读者-写者问题：写者问题：写互斥信号量写互斥信号量wmutex，用于使写进程互斥访问共享变量，用于使写进程互斥访问共享变量writecount，其初，其初值为值为1；读写阻塞信号量读写阻塞信号量rblock，用来在写者到来后阻塞读者，其初值为，用来在写者到来后阻塞读者，其初值为1；写阻塞信号量写阻塞信号量wblock，当有读者被写者阻塞时，阻塞其他新到来的读者，当有读者被写者阻塞时，阻塞其他新

24、到来的读者，其初值为其初值为1； 写共享变量写共享变量writecountwritecount，用来记录当前写进程的数目，初值为，用来记录当前写进程的数目，初值为0 0；26读者读者-写者问题（续写者问题（续4）算法描述：（写者优先）算法描述：（写者优先）/读者进程读者进程 /写者进程写者进程while(1) while(1) P(wblock); P(wmutex); P(rblock); writecount=writecount+1; P(rmutex); if(writecount=1) readcount=readcount+1; P(rblock); if(readcount=1)

25、 V(wmutex); P(mutex); P(mutex); V(rmutex); 执行写操作执行写操作; V(rblock); V(mutex); V(wblock); P(wmutex); 执行读操作执行读操作; writecount=writecount-1; P(rmutex); if(writecount=0) readcount=readcount-1; V(rblock); if(readcount=0) V(wmutex); V(mutex); V(rmutex);27哲学家进餐问题哲学家进餐问题 问题描述：有问题描述：有5个哲学家，生活方式就是交替地进行思个哲学家，生活方式

26、就是交替地进行思考和进餐，公用一张圆桌，分别坐在周围的考和进餐，公用一张圆桌，分别坐在周围的5张椅子上，张椅子上，在圆桌上有在圆桌上有5个碗和个碗和5支筷子，平时哲学家进行思考，饥支筷子，平时哲学家进行思考，饥饿时便试图取其左右最靠近他的筷子，只有在拿到两支饿时便试图取其左右最靠近他的筷子，只有在拿到两支筷子时才能进餐，进餐完毕，放下筷子又继续思考；筷子时才能进餐，进餐完毕，放下筷子又继续思考； 3种状态：种状态： THINKING：思考状态，处于该状态的哲学家正在思考；：思考状态，处于该状态的哲学家正在思考； HUNGRY：饥饿状态，处于该状态的哲学家已经停止思考，：饥饿状态，处于该状态的哲

27、学家已经停止思考，正在试图取得身边的两根筷子；正在试图取得身边的两根筷子； EATING：就餐状态，处于该状态的哲学家取得身边的两根：就餐状态，处于该状态的哲学家取得身边的两根筷子，正在就餐；筷子，正在就餐； 设定哲学家编号依次为设定哲学家编号依次为0到到4，数组，数组State表明哲学家所表明哲学家所处状态；处状态； 定义信号量数组定义信号量数组s，对应每个哲学家，初值为，对应每个哲学家，初值为0，在哲学，在哲学家得不到筷子时阻塞。定义信号量家得不到筷子时阻塞。定义信号量mutex，初值为，初值为1；28哲学家进餐问题（续）哲学家进餐问题（续）算法描述：算法描述：/哲学家进程哲学家进程i v

28、oid philosopher(int i) void test(int i) while(1) if(statei=HUNGRY & 思考问题思考问题; stateLEFT(i)!=EATING & take_chopstick(i); stateRIGHT(i)!=EATING) 就餐就餐; put_chopstick(i); statei=EATING; V(si); void take_chopstick(int i) void put_chopstick(int i) P(mutex); P(mutex); statei=HUNGRY; statei=THINKING

29、; test(i); test(LEFT(i); V(mutex); test(RIGHT(i); P(si); V(mutex); 29打瞌睡理发师问题打瞌睡理发师问题 问题描述：理发店有一位理发师、一把理发椅和问题描述：理发店有一位理发师、一把理发椅和5把供把供等候理发的顾客坐的座椅，如果没有顾客，理发师便在等候理发的顾客坐的座椅，如果没有顾客，理发师便在理发椅上睡觉。一个顾客到来时，必须叫醒理发师，如理发椅上睡觉。一个顾客到来时，必须叫醒理发师，如果理发师正在理发而且有空椅子可坐，就坐下来等待，果理发师正在理发而且有空椅子可坐，就坐下来等待，否则就离开；否则就离开； 设置变量设置变量wa

30、iting表示等待理发的顾客的数量，初值为表示等待理发的顾客的数量，初值为0。定义定义3个信号量：个信号量： customers：正待等待的顾客的数量，数值上与：正待等待的顾客的数量，数值上与waiting相同，初值相同，初值为为0； barbers：理发师的状态，初值为：理发师的状态，初值为1； mutex：用于互斥访问变量：用于互斥访问变量waiting，初值为，初值为1；30打瞌睡理发师问题（续）打瞌睡理发师问题（续）算法描述：算法描述：#define CHAIRS 5void barber(void) void customer(void) while(1) P(mutex); P(c

31、ustomers); if(waitingCHAIRS) P(mutex); waiting+; waiting-; V(customers); V(barbers); V(mutex); V(mutex); P(barbers); 给顾客理发给顾客理发; 理发理发; else V(mutex); 离开离开; 31使用信号的管程使用信号的管程Brinch Hansen和和Hoare提出，高级同步机制，管程提出，高级同步机制，管程Monitor；基本思想：利用数据抽象地表示系统中的共享资源，而把对该数据基本思想：利用数据抽象地表示系统中的共享资源，而把对该数据实施的操作定义为一组过程。代表共享资

32、源的数据，以及由对该共实施的操作定义为一组过程。代表共享资源的数据，以及由对该共享资源实施操作的一组过程所组成的资源管理程序，共同构成了一享资源实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块个操作系统的资源管理模块-管程；管程；Hansen定义：一个管程定义了一个数据结构和能为并发进程在其定义：一个管程定义了一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据；上执行的一组操作，这组操作能使进程同步和改变管程中的数据；四部分组成：四部分组成：管程名称；管程名称；局部于管程的数据的说明；局部于管程的数据的说明；对数据进行操作的一组过

33、程；对数据进行操作的一组过程；对局部于管程内部的共享数据赋初值的语句；对局部于管程内部的共享数据赋初值的语句；32使用信号的管程（续）使用信号的管程（续）进程要想进入管程，必须调用管程中的过程；面向对象中对象的特进程要想进入管程，必须调用管程中的过程；面向对象中对象的特点；点；管程的过程体可以有局部数据；过程有两种：由管程的过程体可以有局部数据；过程有两种：由define定义的过程定义的过程可以被其他模块引用，而未定义的则仅在管程内部使用；管程要引可以被其他模块引用，而未定义的则仅在管程内部使用；管程要引用模块外定义的过程，则必须用用模块外定义的过程，则必须用use说明；说明；编译器采用与其他

34、过程调用不同的方法来处理对管程的调用；典型编译器采用与其他过程调用不同的方法来处理对管程的调用；典型处理方法：当一个进程调用管程过程时，该过程的前几条指令将检处理方法：当一个进程调用管程过程时，该过程的前几条指令将检查在管程中是否有其他活跃进程；查在管程中是否有其他活跃进程；进入管程时的互斥由编译器负责，使用二值型信号量；进入管程时的互斥由编译器负责，使用二值型信号量；条件变量和操作原语：条件变量和操作原语：wait，signal；生产者生产者-消费者问题使用管程的一种解决方案（消费者问题使用管程的一种解决方案（P96）；）；自动实现对临界区的互斥，比信号量更容易保证程序的正确性；自动实现对临

35、界区的互斥，比信号量更容易保证程序的正确性；缺点：程序设计语言概念，编译器必须识别管程并用某种方式实现缺点：程序设计语言概念，编译器必须识别管程并用某种方式实现互斥；互斥；33使用通知和广播的管程使用通知和广播的管程 Lampson和和Redell开发另一种管程方案，解决开发另一种管程方案，解决singal处理处理问题，并支持许多有用扩展；问题，并支持许多有用扩展； singal原语被原语被notify取代；取代； notify含义：当一个正在管程中的进程执行含义：当一个正在管程中的进程执行notify（x）时，时，x条件队列得到通知，但发信号的进程继续执行；条件队列得到通知，但发信号的进程继

36、续执行；通知的结果使得位于条件队列头的进程在将来方便时、通知的结果使得位于条件队列头的进程在将来方便时、当处理器可用时被恢复；不能保证之前没有其他进程进当处理器可用时被恢复；不能保证之前没有其他进程进入管程，等待进程必须重新检查条件；入管程，等待进程必须重新检查条件； 增加增加broadcast广播原语，使所有在该条件上等待的进广播原语，使所有在该条件上等待的进程都被置于就绪状态；当不知道有多少别的进程将被激程都被置于就绪状态；当不知道有多少别的进程将被激活时或难以准确断定将激活哪个进程时，可使用广播；活时或难以准确断定将激活哪个进程时，可使用广播； 使用通知和广播的管程有助于程序结构中采用更

37、模块化使用通知和广播的管程有助于程序结构中采用更模块化的方法；的方法；34死锁的概念死锁的概念 现实生活现象：两人过独木桥；现实生活现象：两人过独木桥； 进程死锁问题描述：资源进程死锁问题描述：资源R1和和R2是独占性资源，进程是独占性资源，进程A占有资源占有资源R1，进程，进程B占有资源占有资源R2，进程，进程A等待占有资源等待占有资源R2，进程等待占有资源，进程等待占有资源R1；结果两个进程都处于阻塞状；结果两个进程都处于阻塞状态，若不采取其他措施，这种循环等待状况无限期持续。态，若不采取其他措施，这种循环等待状况无限期持续。 信号量是共享资源，如果信号量是共享资源，如果P、V操作使用不当

38、，也会产生操作使用不当，也会产生死锁；死锁； 系统中资源分配不当也可引起死锁；系统中资源分配不当也可引起死锁； 死锁：多个进程循环等待他方占有的独占性资源而无限死锁：多个进程循环等待他方占有的独占性资源而无限期地僵持下去的局面。如果没有外力作用，那么死锁涉期地僵持下去的局面。如果没有外力作用，那么死锁涉及的各个进程都将永远处于阻塞状态；及的各个进程都将永远处于阻塞状态；35死锁的概念（续）死锁的概念（续） 同时具备如下同时具备如下4个必要条件时，发生死锁：个必要条件时，发生死锁： 互斥条件：每个资源每次只能分配给一个进程使用，某个进互斥条件：每个资源每次只能分配给一个进程使用，某个进程一旦获得

39、资源，就不准其他进程使用；程一旦获得资源，就不准其他进程使用； 部分分配（占有且等待）条件：进程由于申请不到所需要的部分分配（占有且等待）条件：进程由于申请不到所需要的资源而等待时，仍然占据着已经分配到的资源；资源而等待时，仍然占据着已经分配到的资源； 不可抢占（非剥夺）条件：任一个进程不能从另一个进程那不可抢占（非剥夺）条件：任一个进程不能从另一个进程那里抢占资源，即已被占有的资源，只能由占用进程自己来释里抢占资源，即已被占有的资源，只能由占用进程自己来释放；放； 循环等待条件：存在一个循环的等待序列，从而形成一个进循环等待条件：存在一个循环的等待序列，从而形成一个进程循环等待环；程循环等待

40、环； 资源分配图示例（资源分配图示例（P99）；）；36死锁的处理策略死锁的处理策略 产生死锁的因素：系统拥有的资源数量、资源分配策略、产生死锁的因素：系统拥有的资源数量、资源分配策略、进程对资源的使用要求、并发进程的速率；进程对资源的使用要求、并发进程的速率； 策略：策略： 预防死锁：通过破坏预防死锁：通过破坏4个必要条件之一，可以使系统不具备个必要条件之一，可以使系统不具备产生死锁的条件；产生死锁的条件； 避免死锁：在为申请者分配资源前先测试系统状态，若把资避免死锁：在为申请者分配资源前先测试系统状态，若把资源分配给申请者会产生死锁，拒绝分配，否则接受申请，为源分配给申请者会产生死锁，拒绝

41、分配，否则接受申请，为它分配资源；它分配资源； 检测死锁并恢复：允许系统出现死锁，在死锁发生后，通过检测死锁并恢复：允许系统出现死锁，在死锁发生后，通过一定方法加以恢复，并尽可能地减少损失；一定方法加以恢复，并尽可能地减少损失； 忽略死锁：任凭死锁的出现；当系统中出现死锁时，将系统忽略死锁：任凭死锁的出现；当系统中出现死锁时，将系统重新启动；重新启动；37死锁的预防死锁的预防 死锁预防是排除死锁的静态策略，对进程申请资源的活死锁预防是排除死锁的静态策略，对进程申请资源的活动加以限制，从而使产生死锁的动加以限制，从而使产生死锁的4个必要条件不能同时个必要条件不能同时具备，以保证死锁不会发生；具备

42、，以保证死锁不会发生； 策略：策略： 破坏互斥条件：由于资源独占特征引起；一般来说，不采用该方法；破坏互斥条件：由于资源独占特征引起；一般来说，不采用该方法； 破坏部分分配（占有而且等待）条件：破坏部分分配（占有而且等待）条件： 采用预分配策略，进程执行前申请，静态分配，申请资源系统调用采用预分配策略，进程执行前申请，静态分配，申请资源系统调用先于其他系统调用；先于其他系统调用； 仅当进程没有占用资源时才允许它去申请资源，已经占用再申请资仅当进程没有占用资源时才允许它去申请资源，已经占用再申请资源，应先释放所占资源；源，应先释放所占资源； 减低资源利用率，执行前不知道所需全部资源；减低资源利用

43、率，执行前不知道所需全部资源；38死锁的预防（续）死锁的预防（续） 策略：策略： 破坏不可抢占（非剥夺）条件：破坏不可抢占（非剥夺）条件： 允许在一些情况下，抢占其他进程占有的资源；允许在一些情况下，抢占其他进程占有的资源； 常用于资源状态易于保留和恢复的环境，如常用于资源状态易于保留和恢复的环境，如CPU寄存器和内存；寄存器和内存； 破坏循环条件：破坏循环条件： 实行资源按序（层次）分配策略，把全部资源事先分成多个层次，实行资源按序（层次）分配策略，把全部资源事先分成多个层次，排上序号，然后依次序分配；排上序号，然后依次序分配； 先释放大，再申请小；先释放大，再申请小； 证明（证明（P100

44、）；）； 资源利用率提高；进程使用资源次序和系统规定资源次序不同时，资源利用率提高；进程使用资源次序和系统规定资源次序不同时，提高不明显；系统中所有资源合理排序号是难事，增加系统开销；提高不明显；系统中所有资源合理排序号是难事，增加系统开销；39死锁的避免死锁的避免 动态策略，在为申请者分配资源前先测试系统装他，若动态策略，在为申请者分配资源前先测试系统装他，若把资源分配给申请者会产生死锁，拒绝分配，否则接受把资源分配给申请者会产生死锁，拒绝分配，否则接受申请，为它分配资源；申请，为它分配资源； Dijkstra，1965年，经典避免死锁的算法年，经典避免死锁的算法-银行家算法；银行家算法；模

45、型基于一个小城镇的银行家，向一群客户分别承诺了模型基于一个小城镇的银行家，向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。银行家算法就是对每一个客户的请求进最大的贷款额。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态；如果行检查，检查如果满足它是否会引起不安全状态；如果是，则不满足该请求；否，则满足请求；是，则不满足该请求；否，则满足请求； 系统安全，指系统中的所有进程能够按照某一种次序分系统安全，指系统中的所有进程能够按照某一种次序分配资源，并且依次运行完毕，这种进程序列就是安全序

46、配资源，并且依次运行完毕，这种进程序列就是安全序列；如果存在这样一个安全序列，则系统是安全的；如列；如果存在这样一个安全序列，则系统是安全的；如果系统不存在这个一个安全序列，则系统是不安全的；果系统不存在这个一个安全序列，则系统是不安全的；40死锁的避免（续死锁的避免（续1） 银行家算法：系统给进程分配资源时，先检查状态是否银行家算法：系统给进程分配资源时，先检查状态是否安全，方法是看它是否有足够的剩余资源满足一个距最安全，方法是看它是否有足够的剩余资源满足一个距最大需求最近的进程；如果有，那么分配资源给该进程，大需求最近的进程；如果有，那么分配资源给该进程，然后接着检查下一个距最大需求最近的

47、进程，如此反复然后接着检查下一个距最大需求最近的进程，如此反复下去。如果所有进程都能获得所需资源，那么该状态是下去。如果所有进程都能获得所需资源，那么该状态是安全的，最初的进程申请资源可以分配；安全的，最初的进程申请资源可以分配； 数据结构：向量数据结构：向量Availablej=k，表示，表示 类资源可用数类资源可用数量是量是k；矩阵；矩阵Claimi,j=x，表示进程，表示进程 最大需求最大需求 类类资源资源x个；矩阵个；矩阵Allocationi,j=y，表示进程，表示进程 此时占此时占有有y个个 类资源；矩阵类资源；矩阵Needi,j=z，表示进程，表示进程 还总还总共需要共需要z个个

48、 类资源才能完成任务；类资源才能完成任务； Needi,j=Claimi,j-Allocationi,j；41jriPjriPjriPjr死锁的避免（续死锁的避免（续2） 算法描述：设算法描述：设Request 是进程是进程P 的申请向量，如果的申请向量，如果Request j=m，表示，表示P 这次申请这次申请m个个r 类资源；当类资源；当P 发发出申请后，系统按下述步骤进行检查：出申请后，系统按下述步骤进行检查：if (Request =Need ) goto ;else error(进程对资源的申请量大于它说明的最大值进程对资源的申请量大于它说明的最大值);if (Request =Av

49、ailable ) goto ;else wait();系统试探性地把资源分配给系统试探性地把资源分配给P （类似回溯算法），并根据分配修改下（类似回溯算法），并根据分配修改下面数据结构中的值：面数据结构中的值：Available := Available - Request ;Allocation := Allocation + Request ;Need := Need - Request ;系统执行安全性检查，检查此次资源分配后，系统是否处于安全状态；系统执行安全性检查，检查此次资源分配后，系统是否处于安全状态；若安全，才正式将资源分配给进程以完成此次分配；若不安全，试探若安全，才正式将

50、资源分配给进程以完成此次分配；若不安全，试探性分配作废，恢复原资源分配表，让进程性分配作废，恢复原资源分配表，让进程P 等待；等待；42iiiiijiiiiiiiiiiii死锁的避免（续死锁的避免（续3）安全性检查算法描述：设置两个向量安全性检查算法描述：设置两个向量Free、Finish；向量；向量Free表示表示系统可分配给进程的各类资源数组，含有元素个数等于资源数，执系统可分配给进程的各类资源数组，含有元素个数等于资源数，执行安全算法开始时，行安全算法开始时，Free := Available；标记向量；标记向量Finish表示进程表示进程在此次检查中是否被满足，初始值表示当前未满足进程

51、申请，即在此次检查中是否被满足，初始值表示当前未满足进程申请，即Finishi=false；当有足够资源分配给进程（；当有足够资源分配给进程（Need =Free）时，）时，Finishi=true，P 完成并释放资源；完成并释放资源；从进程集合中找一个能满足下述条件的进程从进程集合中找一个能满足下述条件的进程P ; Finishi=false，表示资源未分配给进程；，表示资源未分配给进程； Need =Free，表示资源够分配给进程；，表示资源够分配给进程；当当P 获得资源后，认为获得资源后，认为P 完成，释放资源；完成，释放资源；Free := Free + Allocation;Fini

52、shi ：=true；goto step1如此试探分配，若可以达到如此试探分配，若可以达到Finish0,.,n=true成立，则表示系统处于安全成立，则表示系统处于安全状态；否则系统处于不安全状态；状态；否则系统处于不安全状态；43iiiiiii44 资源资源进程进程AllocationClaimNeedAvailableR1R2R3R4R1R2R3R4R1R2R3R4R1R2R3R4P13011411111001020P2010002120112P3111042103100P4110111210020P5000021102110 资资源源进程进程FreeNeedAllocationFree

53、+AllocationFinishR1R2R3R4R1R2R3R4R1R2R3R4R1R2R3R4死锁的检测与恢复死锁的检测与恢复 对资源的分配加以限制可以预防和避免死锁的发生，但对资源的分配加以限制可以预防和避免死锁的发生，但不利于各进程对系统资源的充分共享；不利于各进程对系统资源的充分共享； 死锁检测方法，对资源的分配不加以限制，系统周期性死锁检测方法，对资源的分配不加以限制，系统周期性地运行一个地运行一个“死锁检测死锁检测”程序，判断系统内是否存在死程序，判断系统内是否存在死锁，若检测到，则设法加以解除；锁，若检测到，则设法加以解除； 检测频率取决于发生死锁的可能性，申请资源时检测可检测

54、频率取决于发生死锁的可能性，申请资源时检测可以使算法相对比较简单，但频繁的检测消耗相当多的系以使算法相对比较简单，但频繁的检测消耗相当多的系统资源；统资源；45死锁的检测与恢复（续死锁的检测与恢复（续1） 检测常见算法：使用检测常见算法：使用Available向量、向量、Allocation矩阵、矩阵、Request矩阵；算法只调查尚待完成的各个进程所有可矩阵；算法只调查尚待完成的各个进程所有可能的分配序列；初始化临时向量能的分配序列；初始化临时向量Free:=Available；如；如果果Allocation 0(i=1,2,.,n)，则，则Finishi=false；否；否则则Finish

55、=true； 算法描述：算法描述： 从进程集合中找一个能满足下述条件的进程从进程集合中找一个能满足下述条件的进程P ； Finishi=false，表示资源未分配给进程；，表示资源未分配给进程； Request =Free，表示资源够分配给进程；，表示资源够分配给进程； 当当P 获得资源后，认为获得资源后，认为P 完成，释放资源；完成，释放资源；Free := Free + Allocation;Finishi := true;goto step1; 存在某些存在某些i，使得，使得Finishi=false，则系统处于死锁状态，进，则系统处于死锁状态，进程程P 处于死锁之中；处于死锁之中；46

56、iiiiii死锁的检测与恢复（续死锁的检测与恢复（续2） 按照检测算法，序列按照检测算法，序列P1，P3，P2，P4，对于所有，对于所有i都都有有Finishi=true，因此，在，因此，在T0时刻没有死锁；时刻没有死锁；47 资源资源进程进程AllocationRequestAvailableR1R2R3R1R2R3R1R2R3P1110000000P2200202P3313000P4212102死锁的检测与恢复（续死锁的检测与恢复（续3） 进程进程P3申请一个申请一个R3资源，进程资源，进程P3等待；等待； 对于对于i=1,2,3,4，Allocation 0，则，则Finishi=False； P1 Request1=Free，标记，标记Finish1=true，释放资源，释放资源，Free=（1,1,0），此时不能满足其余进程中任何一个需），此时不能满足其余进程中任何一个需要，要，Finishi=false，出现死锁，出现死锁48 资源资源进程进程AllocationRequestAvailableR1R2R3R1R2R3R1R2R3P1110000000P2200202P3313001P42