OS重要知识点摘录（考研用）——第二章：进程管理

男娘i 2023-10-06 15:36 11阅读 0赞

## OS重要知识点摘录（考研用）——第二章：进程管理 ##

本文参考于《2021年操作系统考研复习指导》（王道考研），《计算机操作系统教程》

PCB是进程存在的唯一标志

（3）一个进程可以执行一个或几个程序，一个程序也可构成多个进程。程序的每次运行都构成不同的进程，通过多次执行，一个程序可对应多个进程，通过调用关系，一个进程可包括多个程序。

在OS中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建。

进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得CPU），才可能将其转为阻塞态。

Block原语和Wakeup原语是一对作用刚好相反的原语，必须成对使用。Block原语是由被阻塞进程自我调用实现的，而Wakeup原语则是由一个与被唤醒进程合作或被其他相关的进程调用实现的

进程创建时，OS为它新建一个PCB，该结构之后常驻内存， 任意时刻都可以存取，并在进程结束时删除。PCB是进程实体的一部分，是进程存在的唯一标志。

线程的实现可以分为两类：用户级线程（User-Level Thread,ULT）和内核级线程（Kernel-Level Thread,KLT）。 内核级线程又称内核支持的线程  
  在用户级线程中，有关线程管理（线程的创建、撤销和切换等）的所有工作都由应用程序完成，内核意识不到线程的存在。 应用程序可以通过使用线程库设计成多线程程序。 通常，应用程序从单线程开始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。  
  在内核级线程中，线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口。 内核为进程及其内部的每个线程维护上下文信息，调度也在内核基于线程架构的基础上完成。

######   5.多线程模型 ######

有些系统同时支持用户线程和内核线程，由此产生了不同的多线程模型，即实现用户级线程和内核级线程的连接方式。  
  （1）多对一模型  
  将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。 此模式中，用户级线程对OS不可见（即透明）  
  优点：线程管理在用户空间进行，效率较高  
  缺点：一个线程在使用内核服务时被阻塞，整个进程都会被阻塞；多个线程不能并行地运行在多处理机上。  
  （2）一对一模型  
  将每个用户级线程映射到一个内核级线程  
  优点：当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。  
  缺点：每创建一个用户级线程就需要创建一个内核级线程与其对应，这样创建线程的开销比较大，会影响到应用程序的性能。  
  （3）多对多模型  
  将n个用户级线程映射到m个内核级线程上，要求m<=n  
  特点：多对多模型是多对一模型和一对一模型的折中，既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外，还拥有多对一模型和一对一模型各自的优点，可谓集两者之所长

######   2.调度的层次 ######

一个作业从提交开始直到完成，往往要经历以下3级调度：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center]

（1）作业调度  
  又称高级调度，其主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个（或多个）作业，给它（们）分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使它（们）获得竞争处理机的权利。 简言之，作业调度就是内存与辅存之间的调度。对于每个作业只调入一次、调出一次。  
  多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。 作业调度的执行频率较低，通常为几分钟一次  
  （2）中级调度  
  又称内存调度，其作用是提高内存利用率和系统吞吐量。为此，应将那些暂时不能运行的进程调至外存等待，把此时的进程状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程，再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。  
  （3）进程调度  
  又称低级调度，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。 进程调度是OS中最基本的一种调度，在一般的OS中都必须配置进程调度。进程调度的频率很高，一般几十ms一次

现代OS中，不能进行进程的调度与切换的情况有以下几种：  
  （1）在处理中断的过程中  
  中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源  
  （2）进程在OS内核程序临界区中  
  进入临界区后，需要独占式地访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放  
  （3）其他需要完全屏蔽中断的原子操作过程中  
  如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换  
  若在上述过程中发生了引起调度的条件，则不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换  
  应该进行进程调度与切换的情况如下：  
  （1）发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。若OS只在这种情况下进行进程调度，则是非剥夺调度  
  （2）中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。若OS支持这种情况下的运行调度程序，则实现了剥夺方式的调度。  
  进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。 现场切换时，OS内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

#####  2.2.4 调度的基本准则 #####

为了比较处理机调度算法的性能，人们提出了很多评价准则：  
  （1）CPU利用率  
  （2）系统吞吐量  
  表示单位时间内CPU完成作业的数量。 长作业需要消耗较长的处理机时间，因此会降低系统的吞吐量。而对于短作业，它们所需要消耗的处理机时间较短，因此能提高系统的吞吐量。调度算法和方式的不同，也会对系统的吞吐量造成较大的影响。  
  （3）周转时间  
  周转时间是指从作业提交到作业完成所经历的时间， 是作业等待、在就绪队列中排队、在处理机上运行及进行输入/输出操作所花费时间的总和。  
  周转时间=作业完成时间-作业提交时间  
  平均周转时间是指多个作业周转时间的平均值：  
  平均周转时间=（作业1的周转时间+…+作业n的周转时间）/n  
  带权周转时间是指作业周转时间与作业实际运行时间的比值：  
  带权周转时间=作业周转时间/作业实际运行时间  
  平均带权周转时间是指多个作业带权周转时间的平均值：  
  平均带权周转时间=（作业1的带权周转时间+…+作业n的带权周转时间）/n  
  （4）等待时间  
  等待时间指进程处于等处理机状态的时间之和，。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。 因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间  
  （5）响应时间  
  响应时间指从用户提交请求到系统首次产生响应所用的时间。 在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。

#####  2.2.5 典型的调度算法 #####

OS中存在多种调度算法，有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。

######   1.先来先服务（FCFS）调度算法 ######

FCFS调度算法既可以用于作业调度，又可以用于进程调度。在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列  
  在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放处理机  
  假设系统中有4个作业，它们的提交时间分别是8,8.4,8.8,9,运行时间依次是2,1,0.5,0.2,系统采用FCFS调度算法，这组作业的平均等待时间、平均周转时间和平均带权周转时间如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 1]  
  FCFS调度算法属于不可剥夺算法。 从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面的许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度算法中使用。 例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS原则处理  
  FCFS调度算法的特点是算法简单，但效率低；对长作业比较有利，但对短作业不利（相对于SJF和高响应比）； 有利于CPU繁忙型作业，不利于I/O繁忙型作业

######   2.短作业优先（SJF）调度算法 ######

短作业（进程）优先调度算法是指对短作业（进程）优先调度的算法。短作业优先（SJF）调度算法从后备队列中选择一个或若干估计运行时间最短的作业，将它们调入内存运行；短进程优先（SPF）调度算法从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。  
  假设系统中有4个作业，它们的提交时间分别是8,8.4,8.8,9,运行时间依次是2,1,0.5,0.2,系统采用SJF调度算法，这组作业的平均等待时间、平均周转时间和平均带权周转时间如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 2]  
  SJF调度算法的缺点有：  
  （1）算法对长作业不利；SJF调度算法中长作业的周转时间会增加。更严重的是，若有一长作业进入系统的后备队列，由于调度程序总是优先调度那些（即使是后进来的）短作业，将导致长作业长期不被调度（饥饿现象，饥饿与死锁不同，前者是调度策略问题，后者是系统环形等待）  
  （2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理  
  （3）由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度

SJF调度算法的平均等待时间、平均周转时间最少

######   3.优先级调度算法 ######

优先级调度算法（优先权调度算法）既可用于作业调度，又可用于进程调度。该算法中的优先级用于描述作业运行的紧迫程度  
  在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行  
  根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为如下两种：  
  （1）非剥夺式优先级调度算法  
  当一个进程正在处理机上运行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在运行的进程继续运行，直到由于其自身的原因而主动让出处理机时（任务完成或等待事件），才把处理机分配给更为重要或紧迫的进程。  
  （2）剥夺式优先级调度算法  
  当一个进程正在处理机上运行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给更重要或紧迫的进程

根据进程创建后其优先级是否可以改变，可以将进程优先级分为以下两种：  
  （1）静态优先级：  
  优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。 确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求  
  （2）动态优先级  
  在进程运行过程中，根据进程情况的变化动态调整优先级。 动态调整优先级的主要依据有进程占用CPU时间的长短、就绪进程等待CPU时间的长短

一般来说，进程优先级的设置可以参照以下原则：  
  （1）系统进程>用户进程  
  （2）交互性进程>非交互性进程（或前台进程>后台进程）  
  （3）I/O型进程>计算型进程  
  所谓I/O型进程，是指那些会频繁使用I/O设备的进程，而计算型进程是那些频繁使用CPU的进程（很少使用I/O设备）。若将I/O型进程的优先级设置得更高，就更有可能让I/O设备尽早开始工作，进而提高系统的整体效率

优先级调度算法按照任务的优先级进行调度，对于更紧急的任务给予更高的优先级，适合实时操作系统

######   4.高响应比优先调度算法 ######

高响应比优先调度算法主要用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。 在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。  
![在这里插入图片描述][20200905184405433.png_pic_center]

（1）作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业  
  （2）要求服务时间相同时，作业的响应比由其等待时间确定，等待时间越长，其响应比越高，因而它实现的是先来先服务  
  （3）对于长作业，作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。因此，克服了饥饿状态， 兼顾了长作业

######   5.时间片轮转调度算法 ######

时间片轮转调度算法主要适用于分时系统。 在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务的原则，但仅能运行一个时间片，如100ms。在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出（被剥夺）处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。  
  在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。若时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法。 若时间片很小，则处理机将在进程间过于频繁地切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。因此，时间片的大小应选择适当。  
  时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力

######   6.多级反馈队列调度算法（融合了前几种算法的优点） ######

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 3]  
  通过动态调整进程优先级和时间片大小， 多级反馈队列调度算法可以兼顾多方面的系统目标。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；同时，也不必事先估计进程的执行时间  
  多级反馈队列调度算法的实现思想如下：  
  （1）设置多个就绪队列，并为各个队列赋予不同的优先级， 第1级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低  
  （2）赋予各个队列中进程执行的时间片大小各不相同。在优先级越高的队列中，每个进程的运行时间片越小。 例如，第2级队列的时间片要比第1级队列的时间片长1倍… …第i+1级队列的时间片要比第i级队列的时间片长1倍  
  （3）一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；若它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样按FCFS原则等待调度执行；若它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列… … 如此下去，当一个长进程从第1级队列依次降到第n级队列后，在第n级队列中便采用时间片轮转的方式运行。  
  （4）仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行；仅当第1~（i-1）级队列均为空时，才会调度第i级队列中的进程运行。 若处理机正在执行第i级队列中的某进程，这时又有新进程进入优先级较高的队列（ 第1~i-1中的任何一个队列 ），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回第i级队列的末尾，把处理机分配给新到的更高优先级的进程。

多级反馈队列的优势有以下几点：  
  （1）终端型作业用户：短作业优先  
  （2）短批处理作业用户：周转时间较短  
  （3）长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理

--------------------

高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法都能保证每个任务在一定时间内分配到时间片，并轮流占用CPU，适合分时操作系统

--------------------

同步亦称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。 进程间的直接制约关系源于它们之间的相互合作。

（4）算法四：Peterson’s Algorithm

Pi进程：							Pj进程：
    flag[i]=TRUE;						flag[j]=TRUE;
    turn=j;								turn=i;
    while(flag[j]&&turn==j);			while( flag[i]&&turn==i );		
    critical section;					critical section;
    flag[i]=FALSE;						flag[j]=FALSE;
    remainder section;					remainder section;

为了防止两个进程为进入临界区而无限期等待，又设置了变量turn，每个进程在先设置自己的标志后再设置turn标志。这时，再同时检测另一个进程状态标志和不允许进入标志，以便保证两个进程同时要求进入临界区时，只允许一个进程进入临界区。  
  具体如下：考虑进程Pi，一旦设置flag\[i\]=true，就表示它想要进入临界区，同时turn=j，此时若进程Pj已在临界区中，符合进程Pi中的while循环条件，则Pi不能进入临界区。若Pj不想要进入临界区，即flag\[j\]=false，循环条件不符合，则Pi可以顺利进入，反之亦然。 利用flag解决临界资源的互斥访问，而利用turn解决饥饿现象 （若两个进程几乎同时都想进入临界区，最后turn的值要么是i，要么是j，而两个flag都为TRUE，此时总有一个进程可以执行，而另一个进程不能执行，克服了饥饿现象）

--------------------

Peterson’s Algorithm可类比为两个人进门，每个人进门前都会和对方客套一句“你先走”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两个人同时进门，就互相请先，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大地进门

--------------------

######   3.利用信号量实现同步 ######

信号量机制能用于解决进程间的各种同步问题。设S为实现进程P1，P2同步的公共信号量，初值为0。进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成之后语句y才可以执行。

semaphore S=0;			//初始化信号量
    P1()
    {
        
    	x;					//语句x
    	V(S);				//告诉进程P2，语句x已经完成
    	...
    }
    P2()
    {
        
    	...
    	P(S);				//检查语句x是否运行完成
    	y;					//检查无误，运行y语句
    	...
    }

若P2先执行到P（S）时，S为0，执行P操作会把进程P2阻塞，并放入阻塞队列；当进程P1中的x执行完后，执行V操作，把P2从阻塞队列中放回就绪队列，当P2得到处理机时，就得以继续执行

######   4.利用信号量实现进程互斥 ######

设S为实现进程P1，P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应该为1（即可用资源数为1）。 只需把临界区置于P（S）和V（S）之间，即可实现两个进程对临界资源的互斥访问。

semaphore S=1;				//初始化信号量
    P1()						
    {
        
    	...
    	P( S );					//准备开始访问临界资源，加锁
    	进程P1的临界区；			
    	V( S );					//访问结束，解锁
    	...
    }
    P2()
    {
        
    	...
    	P( S );					//准备开始访问临界资源，加锁
    	进程P2的临界区；			
    	V( S );					//访问结束，解锁
    	...
    }

当没有进程在临界区时，任意一个进程要进入临界区，就要执行P操作，把S的值减为0，然后进入临界区；当有进程存在于临界区时，S的值为0，再有进程要进入临界区，执行P操作时将会被阻塞，直至在临界区中的进程退出，这样便实现了临界区的互斥。  
  互斥是不同进程对同一信号量进行P,V操作实现的，一个进程成功对信号量进行了P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作，表示当前没有进程进入临界区，可以让其他进程进入。

同步互斥中的P,V操作：在同步问题中，若某个行为要用到某种资源，则在这个行为前面P这种资源一下；若某个行为会提供某种资源，则在这个行为后面V这种资源一下。在互斥问题中，P,V操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码。

######   5.利用信号量实现前驱关系 ######

信号量也可用来描述程序之间或语句之间的前驱关系。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 4]  
  S1,S2,S3,…,S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干初始值为0的信号量。为保证S1——>S2,S1——>S3的前驱关系，应分别设置信号量a1,a2，为保证S2——>S4,S2——>S5,S3——>S6,S4——>S6,S5——>S6,应设置信号量b1,b2,c,d,e

semaphore a1=a2=b1=b2=c=d=e=0;		//初始化信号量
    S1()
    {
        
    	...;
    	V(a1);							//S1已经运行完成
    	V(a2);
    }
    S2()
    {
        
    	P(a1);							//检查S1是否运行完成
    	...;
    	V(b1);							//S2已经运行完成
    	V(b2);
    }
    S3()
    {
        
    	P(a2);							//检查S1是否运行完成
    	...;
    	V(c);							//S3已运行完成
    }
    S4()
    {
        
    	P(b1);							//检查S2是否已经运行完成
    	...;
    	V(d);							//S4已经运行完成
    }
    S5()
    {
        	
    	P(b2);							//检查S2是否已经运行完成
    	...;
    	V(e);							//S5已经运行完成
    }
    S6()
    {
        
    	P(c);							//检查S3是否已经运行完成
    	P(d);							//检查S4是否已经运行完成
    	P(e);							//检查S5是否已经运行完成
    	...;
    }

#####  2.3.5 经典同步问题 #####

######   1.生产者-消费者问题 ######

问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。 由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。  
  问题分析：  
  （1）关系分析：  
  生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。  
  （2）整理思路：  
  需要解决互斥和同步PV操作的位置  
  （3）信号量设置：  
  信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1；信号量full用于记录当前缓冲池中的满缓冲区数，初值为0；信号量empty用于记录当前缓冲池中的空缓冲区数，初值为n

semaphore mutex=1;			//临界区互斥信号量
    semaphore empty=n;			//空闲缓冲区
    semaphore full=0;			//缓冲区初始化为空
    producer()					//生产者进程
    {
        
    	while( 1 )
    	{
        
    		produce an item in nextp;		//生产数据
    		P(empty);   （要用什么，P一下）  //获取空缓冲区单元
    		P(mutex);    （互斥夹紧）		//进入临界区
    		add nextp to buffer;  （行为）   //将数据放入缓冲区
    		V(mutex);	  （互斥夹紧）		//离开临界区，释放互斥信号量
    		V(full);	（提供什么，V一下）	//满缓冲区数加1
    	}
    }
    consumer()					//消费者进程
    {
        
    	while(1)
    	{
        
    		P(full);			//获取满缓冲区单元
    		P(mutex);			//进入临界区
    		remove an item from buffer;		//从缓冲区中取出数据
    		V(mutex);			//离开临界区，释放互斥信号量
    		V(empty);			//空缓冲区数加1
    		consume the item;	//消费数据
    	}
    }

该类问题要注意对缓冲区大小为n的处理，当缓冲区中有空时，便可对empty变量执行P操作，一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对mutex的P操作之前

--------------------

若生产者进程先执行P(mutex)，然后执行P(empty)，消费者进程执行P(mutex)，然后执行P(full)，可不可以？  
  不可。若生产者进程已将缓冲区放满，消费者进程并没有取产品，即empty=0，当下次仍然是生产者进程运行时，它先执行P(mutex)封锁信号量，再执行P(empty)时将被阻塞，希望消费者取出产品后将其唤醒。轮到消费者进程运行时，它先执行P(mutex)，然而由于生产者进程已经封锁mutex信号量，消费者进程也会被阻塞，这样一来生产者、消费者进程都被阻塞，都指望对方唤醒自己，因此陷入了无休止的等待。同理，若消费者已将缓冲区取空，即full=0，下次若还是消费者先运行，也会出现类似的死锁。不过生产者释放信号量时，mutex,full先释放哪一个无所谓，消费者先释放mutex或empty都可以。

--------------------

另一个稍复杂的生产者-消费者问题：  
  问题描述：  
  桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果  
  （1）关系分析：  
  由每次只能向其中放入一个水果可知，爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有同步和互斥关系，因为他们是选择条件执行，不可能并发  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 5]  
  （2）整理思路：  
  这里有4个进程，实际上可抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。  
  （3）信号量设置  
  首先将信号量plate设置为互斥信号量，表示是否允许向盘子中放入水果，初值为1表示允许放入，且只允许放入一个。信号量apple表示盘子中是否有苹果，初值为0表示盘子为空，不许取，apple=1表示可以取。信号量orange表示盘子中是否有橘子，初值为0表示盘子为空，不许取，orange=1表示可以取

semaphore plate=1,apple=0,orange=0;
    dad()				//父亲进程
    {
        
    	while(1)
    	{
        
    		prepare an apple;
    		P(plate);	//互斥向盘中取、放水果
    		put the apple on the plate;		//向盘中放苹果
    		V(apple);	//允许取苹果
    	}
    }
    mom()				//母亲进程
    {
        
    	while(1)
    	{
        
    		prepare an orange;
    		P(plate);	//互斥向盘中取、放水果
    		put the orange on the plate;	//向盘中放橘子
    		V(orange);	//允许取橘子
    	}
    }
    son()				//儿子进程
    {
        
    	while(1)
    	{
        
    		P(orange);			//互斥向盘中取橘子
    		take an orange from the plate;
    		V(plate);			//允许向盘中取、放水果
    		eat the orange;
    	}
    }
    daughter()			//女儿进程
    {
        
    	while(1)
    	{
        
    		P(apple);			//互斥向盘中取苹果
    		take an apple from the plate;
    		V(plate);			//允许向盘中取、放水果
    		eat the apple;
    	}
    }

dad()和daughter()、mom()和son()必须连续执行，正因为如此，也只能在女儿拿走苹果后或儿子拿走橘子后才能释放盘子，即V(plate)操作

######   2.读者-写者问题 ######

问题描述：  
  有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：（1）允许多个读者可以同时对文件执行读操作； （2）只允许一个写者往文件中写信息； （3）任一写者在完成写操作之前不允许其他读者或写者工作 （4）写者执行写操作前，应让已有的读者和写者全部退出  
  问题分析：  
  （1）关系分析：  
  读者和写者互斥，写者和写者互斥，读者和读者不互斥  
  （2）整理思路：  
  两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的PV操作即可解决。读者较复杂，它必须在实现与写者互斥的同时，实现与其他读者的同步， 因此简单的一对PV操作是无法解决问题的。这里用到了一个计数器，用它来判断当前是否有读者读文件。 当有读者时，写者是无法写文件的，此时读者会一直占用文件，当没有读者时，写者才可以写文件。同时，这里不同读者对计数器的访问也应该是互斥的。  
  （3）信号量设置：  
  首先设置信号量count为计数器，用于记录当前读者的数量，初值为0；设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw,用于保证读者和写者的互斥访问

int count=0;		//用于记录当前的读者数量
    semaphore mutex=1;	//用于保护更新count变量时的互斥
    semaphore rw=1;		//用于保证读者和写者互斥地访问文件
    writer()			//写者进程
    {
        
    	while(1)
    	{
        
    		P(rw);		//互斥访问共享文件
    		writing;	//写入
    		V(rw);		//释放共享文件
    	}
    }
    reader()			//读者进程
    {
        
    	while(1)
    	{
        
    		P(mutex);	//互斥访问count变量
    		if( count==0 )		//当第一个读进程读共享文件时
    			P(rw);			//阻止写进程写
    		count++;			//读者计数器加1
    		V(mutex);	//释放互斥变量count
    		reading;	//读取
    		P(mutex);	//互斥访问count变量
    		count--;			//读者计数器减1
    		if( count==0 )		//当最后一个读进程读完共享文件
    			V(rw);			//允许写进程写
    		V(mutex);	//释放互斥变量count
    	}
    }

在上述算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。 这样的方式会导致写进程可能长时间等待，且存在写进程饿死的情况。

若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的writer()和reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序：

int count=0;		//用于记录当前的读者数量
    semaphore mutex=1;	//用于保护更新count变量时的互斥
    semaphore rw=1;		//用于保证读者和写者互斥地访问文件
    semaphore w=1;		//用于实现写优先
    writer()			//写者进程
    {
        
    	while(1)
    	{
        
    		P(w);		//在无写进程请求时进入
    		P(rw);		//互斥访问共享文件
    		writing;	//写入
    		V(rw);		//释放共享文件
    		V(w);		//恢复对共享文件的访问
    	}
    }
    reader()			//读者进程
    {
        
    	while(1)
    	{
        	
    		P(w);		//在无写进程请求时进入
    		P(mutex);	//互斥访问count变量
    		if( count==0 )		//当第一个读进程读共享文件时
    			P(rw);			//阻止写进程写
    		count++;			//读者计数器加1
    		V(mutex);	//释放互斥变量count
    		V(w);		//恢复对共享文件的访问
    		reading;	//读取
    		P(mutex);	//互斥访问count变量
    		count--;			//读者计数器减1
    		if( count==0 )		//当最后一个读进程读完共享文件
    			V(rw);			//允许写进程写
    		V(mutex);	//释放互斥变量count
    	}
    }

这里的写进程优先是相对而言的，有的书上把这个算法称为读写公平法， 即读写进程具有一样的优先级。当一个写进程访问文件时，若先有一些读进程要求访问文件，后有另一个写进程要求访问文件，则当前访问文件的进程结束对文件的写操作时，会是一个读进程而不是一个写进程占用文件（在信号量w的阻塞队列上，因为读进程先来，因此排在阻塞队列队首，而V操作唤醒进程时唤醒的是队首进程），所以说这里的写优先是相对的。  
  读者-写者问题有一个关键的特征，即有一个互斥访问的计数器count，因此遇到一个不太好解决的同步互斥问题时，要想一想用互斥访问的计数器count能否解决问题

######   3.哲学家进餐问题 ######

问题描述：  
  一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 6]  
  问题分析：  
  （1）关系分析  
  5名哲学家与左右邻居对其中间筷子的访问是互斥关系  
  （2）整理思路  
  解决方法有两个：一是让他们同时拿两根筷子；二是对每名哲学家的动作制定规则，避免饥饿或死锁现象发生  
  （3）信号量设置  
  定义互斥信号量数组chopstick\[5\]=\{1,1,1,1,1\}，用于对5个筷子的互斥访问。哲学家按顺序编号为0~4，哲学家i左边筷子的编号为i，哲学家右边筷子的编号为(i+1)%5。

错误算法：

semaphore chopstick[5]={
        1,1,1,1,1};
    Pi()
    {
        
    	do
    	{
        
    		P( chopstick[i] );
    		P( chopstick[(i+1)%5] );
    		eat;
    		V( chopstick[i] );
    		V( chopstick[(i+1)%5] );
    		thick;
    	}
    	while(1);
    }

当5名哲学家都想要进餐并分别拿起左边的筷子时（都恰好执行完wait(chopstick\[i\]) ），筷子已被拿光，等到他们再想拿右边的筷子时（执行wait(chopstick\[(i+1)%5\]) ），就全被阻塞，因此出现了死锁。

为防止死锁产生，可对哲学家进程施加一些限制条件，比如：  
  （1）至多允许四名哲学家同时进餐  
  至多只允许四名哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐。

semaphore r=4;
    P(r);
    P( chopstick[i] );
    P( chopstick[(i+1)%5] );
    eat;
    V( chopstick[i] );
    V( chopstick[(i+1)%5] );
    V(r);

（2）对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家则刚好相反

（3）仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子  
  即每次都使一个哲学家同时拿到两根筷子

semaphore chopstick[5]={
        1,1,1,1,1};		//初始化信号量
    semaphore mutex=1;						//设置取筷子的信号量
    Pi()									//i号哲学家的进程
    {
        
    	do
    	{
        
    		P(mutex);		//在取筷子前获得互斥量
    		P( chopstick[i] );			//取左边筷子
    		P( chopstick[(i+1)%5] );	//取右边筷子
    		V(mutex);		//释放取筷子的信号量
    		eat;			//进餐
    		V( chopstick[i] );			//放回左边筷子
    		V( chopstick[(i+1)%5] );	//放回右边筷子
    		think;			//思考
    	}while(1);
    }

哲学家进餐问题的思想其实和贪心算法的思想截然相反。 贪心算法强调争取眼前认为最好的，而不考虑后续会有什么后果。在哲学家进餐问题中，若只要眼前有筷子就拿起，就会出现死锁。然而，若不仅考虑眼前的一步，而且考虑下一步，即不因为有筷子能拿起就拿起，而是考虑能不能一次拿起两根筷子才做决定的话，就会避免死锁问题。

######   4.吸烟者问题 ######

问题描述：  
  假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷起一根烟并抽掉它，并给供应者一个信号表示已完成，此时供应者会将另外两种材料放到桌上，如此重复（让三个抽烟者轮流地抽烟）  
  问题分析：  
  （1）关系分析  
  供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上的抽烟者，三个抽烟者对抽烟这个动作互斥（或由三个抽烟者轮流抽烟得知）  
  （2）整理思路  
  有四个进程，供应者作为生产者向三个抽烟者提供材料  
  （3）信号量设置  
  信号量offer1,offer2,offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。

int random;			//存储随机数
    semaphore offer1=0;		//定义信号量对应烟草和纸组合的资源
    semaphore offer2=0;		//定义信号量对应烟草和胶水组合的资源
    semaphore offer3=0;		//定义信号量对应纸和胶水组合的资源
    semaphore finish=0;		//定义信号量表示抽烟是否完成
    process P1()			//供应者
    {
        
    	while(1)
    	{
        
    		random=任意一个整数随机数;
    		random=random%3;
    		if( random==0 )
    			V(offer1);		//提供烟草和纸
    		else if( random==1 )
    			V(offer2);		//提供烟草和胶水
    		else
    			V(offer3);		//提供纸和胶水
    		任意两种材料放在桌子上;
    		P(finish);
    	}
    }
    process P2()			//拥有烟草者
    {
        
    	while(1)
    	{
        
    		P(offer3);
    		拿纸和胶水，卷烟，抽掉;
    		V(finish);
    	}
    }
    process P3()			//拥有纸者
    {
        
    	while(1)
    	{
        
    		P( offer2 );
    		拿烟草和胶水，卷烟，抽掉;
    		V(finish);
    	}
    }
    process P4()			//拥有胶水者
    {
        
    	while(1)
    	{
        
    		P( offer1 );
    		拿烟草和纸，卷烟，抽掉;
    		V(finish);
    	}
    }

（3）死锁产生的必要条件  
  产生死锁必须同时满足以下4个条件，只要其中任意一个条件不成立，死锁就不会发生。  
  互斥条件：进程要求对所分配的资源（如打印机）进行排它性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待  
  不剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放）  
  请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。  
  循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待态的进程集合\{P1，P2，…，Pn\}，其中Pi等待的资源被Pi+1（i=0,1,…,n-1）占有，Pn等待的资源被P0占有  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 7]  
  循环等待条件和死锁的定义有区别。按死锁定义构成的等待环所要求的条件更严，它要求Pi等待的资源必须由Pi+1来满足，而循环等待条件则无此限制。例如，系统中有两台输出设备，P0占有一台，PK占有一台，且K不属于集合\{0,1,…,n\}。Pn等待一台输出设备，它可以从P0获得，也可能从PK获得。因此，虽然Pn,P0和其他一些进程形成了循环等待圈，但PK不在圈内，若PK释放了输出设备，则可打破循环等待。因此循环等待只是死锁的必要条件。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 8]  
  资源分配图含圈而系统又不一定有死锁的原因是，同类资源数大于1。但若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。

#####  2.4.2 死锁的处理策略 #####

为使系统不发生死锁，必须设法破坏产生死锁的4个必要条件之一，或允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复

######   1.死锁预防 ######

设置某些限制条件，破坏产生死锁的4个必要条件中的一个或几个，以防止发生死锁

######   2.避免死锁 ######

在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁

######   3.死锁的检测及解除 ######

无须采取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁

预防死锁和避免死锁都属于事先预防策略，预防死锁的限制条件比较严格， 实现起来较为简单，但往往导致系统的效率低，资源利用率低；避免死锁的限制条件相对宽松， 资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。  
  死锁的几种处理策略的比较如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 9]

#####  2.4.3 死锁预防 #####

防止死锁的发生只需破坏死锁产生的4个必要条件之一即可

######   1.破坏互斥条件 ######

若允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行， 而且在有的场合应该保护这种互斥性。

######   2.破坏不剥夺条件 ######

当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺，或从而破坏了不剥夺条件。  
  该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。

######   3.破坏请求并保持条件 ######

采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行，这些资源就一直归它所有，不再提出其他资源请求，这样就可以保证系统不会发生死锁。  
  使用这种方式，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致饥饿现象，由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。

######   4.破坏循环等待条件 ######

为了破坏循环等待条件，可采用顺序资源分配法。 首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中就只能申请编号大于Ri的资源  
  这种方法的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦

#####  2.4.4 死锁避免 #####

避免死锁同样属于事先预防策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。 这种方法所施加的限制条件较弱，可以获得较好的系统性能

######   1.系统安全状态 ######

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待。  
  所谓安全状态，是指系统能按某种进程推进顺序（P1，P2，…，Pn）为每个进程Pi分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称P1,P2,…，Pn为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。  
  假设系统中有三个进程P1,P2和P3，共有12台磁带机。进程P1共需要10台磁带机，P2和P3分别需要4台和9台。假设在T0时刻，进程P1，P2和P3已分别获得5台、2台和2台，尚有3台未分配，见下表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 10]  
  在T0时刻是安全的，因为存在一个安全序列P2,P1,P3，只要系统按此进程序列分配资源，那么每个进程都能顺利完成。也就是说，当前可用磁带机为3台，先把3台磁带机分配给P2以满足最大需求，P2结束并归还资源后，系统有5台磁带机可用；接下来给P1分配5台磁带机以满足其最大需求，P1结束并归还资源后，剩余10台磁带机可用；最后分配7台磁带机给P3，这样P3也能顺利完成  
  若在T0时刻后，系统分配1台磁带机给P3，系统剩余可用资源数为2，此时系统进入不安全状态，因为此时已无法再找到一个安全序列。当系统进入不安全状态后，便可能导致死锁。例如，把剩下的2台磁带机分配给P2，这样，P2完成后只能释放4台磁带机，既不能满足P1又不能满足P3，致使它们都无法推进到完成，彼此都在等待对方释放资源，陷入僵局，导致死锁。

并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。

######   2.银行家算法 ######

银行家算法的思想是：把OS视为银行家，OS管理的资源相当于银行家管理的资金，进程向OS请求分配资源相当于用户向银行家贷款。OS按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。  
  （1）数据结构描述  
  可利用资源向量Available：  
  含有m个元素的数组，其中每个元素代表一类可用的资源数目。Available\[j\]=K表示系统中现有Rj类资源K个  
  最大需求矩阵Max：  
  nxm矩阵，定义系统中n个进程中的每个进程对m类资源的最大需求。简单来说，一行代表一个进程，一列代表一类资源。Max\[i,j\]=K表示进程i需要Rj类资源的最大数目为K  
  分配矩阵Allocation：  
  nxm矩阵，定义系统中每类资源当前已分配给每个进程的资源数。Allocation\[i,j\]=K表示进程i当前已分得Rj类资源的数目为K。  
  需求矩阵Need：  
  nxm矩阵，表示每个进程接下来最多还需多少资源。Need\[i,j\]=K表示进程i还需Rj类资源的数目为K

上述三个矩阵间存在下列关系：  
  Need=Max-Allocation

（2）银行家算法描述  
  设Requesti是进程Pi的请求向量，Requesti\[j\]=K表示进程Pi需要j类资源K个。当Pi发出资源请求后，系统按下列步骤进行检查：  
  a.若Requesti\[j\]<=Need\[i,j\]，则转向步骤b；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值  
  b.若Requesti\[j\]<=Available\[j\]，则转向步骤c;否则，表示尚无足够资源，Pi须等待  
  c.系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：  
  Available=Available-Requesti  
  Allocation\[i,j\]=Allocation\[i,j\]+Requesti\[j\]  
  Need\[i,j\]=Need\[i,j\]-Requesti\[j\]  
  d.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

（3）安全性算法  
  设置工作向量Work，有m个元素，表示系统中的剩余可用资源数目。在执行安全性算法开始时，Work=Available。  
  a.初始时安全序列为空  
  b.从Need矩阵中找出符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于Work向量，找到后，把对应的进程加入安全序列;若找不到，则执行步骤d  
  c.进程Pi进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，因此应执行Work=Work+Allocation\[i\]，其中Allocation\[i\]表示进程Pi代表的在Allocation矩阵中对应的行，返回步骤b  
  d.若此时安全序列中已有所有进程， 则系统处于安全状态，否则系统处于不安全状态

#####  2.4.5 死锁检测和解除 #####

前面介绍的死锁预防和避免算法，都是在为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何措施，则应该提供死锁检测和解除的手段

######   1.资源分配图 ######

系统死锁可利用资源分配图来描述。用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，因此用框中的一个圆代表一类资源中的一个资源。 从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 11]  
  在上图所示的资源分配图中，进程P1已经分得了两个R1资源，并又请求一个R2资源；进程P2分得了一个R1资源和一个R2资源，并又请求一个R1资源

######   2.死锁定理 ######

简化资源分配图可检测系统状态S是否为死锁状态。 简化方法如下：  
  （1）在资源分配图中，找出既不阻塞又不孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有的空闲资源数量，若所有连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。  
  判断某种资源是否有空闲，应用它的资源数量减去它在资源分配图中的出度。  
  （2）进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。根据（1）中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可以完全简化的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 12]  
  S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。

######   3.死锁解除 ######

一旦检测出死锁，就应采取相应的措施来解除死锁。死锁解除的主要方法有：  
  （1）资源剥夺法  
  挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态  
  （2）撤销进程法  
  强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行  
  （3）进程回退法  
  让一（或多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息，设置还原点

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200904200204233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200905171130277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2020090517232062.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[20200905184405433.png_pic_center]: https://img-blog.csdnimg.cn/20200905184405433.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200905185920972.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200907210119149.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20200908194252757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20200908203508899.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20200911144901994.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20200911145517763.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20200911150940993.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/2020091115442482.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20200911170131548.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20200911171345820.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70#pic_center