深入理解操作系统原理之进程管理（二）

「爱情、让人受尽委屈。」 2022-06-13 04:48 541阅读 0赞

## 一、进程通信 ##

在多道程序设计的系统中并发执行的进程是异步的、独立地向前推进。并发执行的进程间有的需共享有关临界资源，有的需要协同完成一个任务，在进程间不但需要同步还需要通信，即交换一定数量的信息。进程间通信时所交换的信息量可多可少，少者仅是一些数据和状态的变换，多者可交换成千上百个数据。前面讨论的利用信号量机制实现进程的同步问题，也是一种通信方式。例如生产者和消费者问题中，生产者通过缓冲池将所生产的消息传送给消费者。  
虽然信号量机制作为同步工具是卓有成效，但作为通信工具不够理想。主要是由于效率低，生产者或消费者每次都只能放入或取出一个消息；其次是通信对用户不透明，这对程序设计带来很大的不便，P、V操作设计不当会造成某些执行序列出现死锁。高级通信要求能高效地传送大量数据，同时通信过程对用户透明，以简化程序设计的复杂性。  
高级通信机制可归结为三大类：  
1、共享存储器系统：

*  基于共享数据结构的通信方式
 *  基于共享存储区的通信方式

2、消息传送系统

*  直接通信方式
 *  间接通信方式

3、管道通信系统

### 1、基于共享数据结构的通信方式 ###

在这种通信方式中，要求诸进程公用某个数据结构，进程通过它们交换信息。如在生产者-消费者问题中，就是把缓冲池（有界缓冲区）这种数据结构用来作通信的。这种通信方式是低效的，只适用传送少量的数据。

### 2、基于共享存储区的通信方式 ###

共享存储区是UNIX系统中通信速度最高的一种通信机制，它包含在进程通信软件包IPC中。该方法为了传送大量数据，在存储区中划出一块存储区，供多个进程共享，共享进程通过对这一共享存储区中的数据进行读或写来实现通信。  
当进程A要利用共享存储区进行通信时，应先利用系统调用shmget建立一个共享存储区。执行该系统调用时，核心首先检查共享存储区表，该表是系统范围的数据结构，每个共享存储区在该表中占一表项。如末找到，则分配一系统空闲区作为共享区的页表区，分配相应的内存块，有关参数填入页表中。返回共享存储器的描述符shmid。  
进程B要利用共享存储区与进程A通信时，也要先利用系统调用shmget，此时核心检查共享存储区表找到了指定的表项，则返回该表项的描述符shmid。  
进程A和B在建立了一个共享存储区并获得了其描述符后，还需分别利用系统调用shmat将共享存储区附接到各自进程的虚地址空间上。此后共享存储区便成为进程虚地址空间的一部分，进程可采取与其它虚地址空间一样的存取方法来存取它。

### 3、消息传递系统 ###

分为直接通信方式和间接通信方式两种。

*  直接通信方式  
    这是指发送进程利用OS提供的发送命令直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收进程利用OS提供的接收命令直接从消息缓冲队列中取得消息。此时要求发送进程和接收进程都以显示的方式提供对方的标识符，通常系统提供下述两条通信原语： `Send(Receiver ,message) ； Receive(Sender ,message) ；或(Receive(message)) ；`  
    直接通信的实例-消息缓冲队列通信机制。消息缓冲队列通信机制的原理是：由系统管理一组缓冲区，其中每个缓冲区可以存放一个消息。当发送进程要发送消息时先要向系统申请一个缓冲区，然后把消息写进去，接着把该缓冲区连接到接收进程的消息缓冲队列中。接收进程可以在适当的时候从消息缓冲队列中摘下消息缓冲区，读取消息，并释放该缓冲区。
 *  间接通信方式  
    在间接通信情况，消息不直接从发送者发送到接收者，而是发送到暂存消息的共享数据结构组成的队列，这个实体称为信箱（mailbox）.因此二个进程通信情况，一个进程发送一个消息到某个信箱，而另一个进程从信箱中摘取消息。  
    间接通信的使用好处是增加了使用消息的灵活性。发送者和接收者的关系可能是一对一、多对一，一对多或多对多。一对一的关系允许一个专用通信链路用于二个进程间的交互，它能使俩进程间交互不受其它进程错误干予的影响，多对一的关系对客户／服务器交互特别有用，一个进程对多个其它进程（用户）提供服务。在这种情况信箱经常称作为端口(port)。一对多关系允许一个发送进程和多个接收进程交互，这可用来将消息广播(broadcast)给一组进程。

### 3、管道通信 ###

UNIX系统在OS的发展上最重要的贡献之一便是该系统首创了管道（pipes）。管道是指用于连接一个读进程和一个写进程，以实现它们之间通信的一个打开的共享文件，又称为pipe文件。向管道（共享文件）提供输入的发送进程（即写进程），以字符形式将大量的数据送入管道，而接收管道输出的接收进程（即读进程）可从管道中接收数据。管道通信是基于文件系统形式的一种通信方式。  
为了协调双方的通信，管道机制必须提供以下三方面的协调能力：① 互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。 ② 同步，指当写(输入)进程把一定数量(如4 KB)的数据写入pipe，便去睡眠等待， 直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。③ 确定对方是否存在，只有确定了对方已存在时，才能进行通信。 与一般文件不同是管道数据的先进先出（FIFO）处理方式和管道文件数据不可再现性，即被读取的数据在管道中不能再利用。

## 二、调度 (Scheduling) ##

### 1、作业的状态和处理机三级调度 ###

作业从进入到运行结束，一般需要经历“提交”、“后备”、“运行”和“完成”四个阶段。  
(1)提交状态  
一个作业被提交给机房后正在通过SPOOLing系统进行输入或用户通过终端向计算机中键入其作业时所处于的状态为提交状态。  
(2)后备状态  
作业已经过SPOOLing系统输入到磁盘输入井，等待调入内存运行，此时作业处于后备状态。为了管理和调度作业，为每个作业设置一个作业控制块（JCB）。作业控制块记录了作业类型和资源要求等有关信息。作业控制块按作业类型组成一个或多个后备作业队列。  
(3)运行状态  
一个在后备作业队列的作业被作业调度程序选中后，分配必要的资源，建立一组相应的进程后，调入内存，该作业就进入运行状态。进程各状态（进程运行态、内存进程就绪态、内存阻塞态、外存进程就绪态、外存进程阻塞态等）都对应作业运行状态。  
(4)完成状态  
当进程正常运行结束或因发生错误而终止时，作业进入完成状态。终止作业程序将负责善后处理。  
![这里写图片描述][20170627194204992]

### 2、处理机三级调度 ###

(1)低级(Short-term)调度：进程调度  
进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。调度的运行频率很高，在分时系统中通常是几十毫秒就要运行一次。进程调度是最基本的调度，任何操作系统都有进程调度。  
(2)中级(Medium-term)调度：对换  
引入中级调度的目的是为了提高主存利用率和系统吞吐量。由于在进程并发执行过程中，因对主存资源或I/O资源提出新的要求得不到满足，或因等待协作进程同步操作完成造成阻塞，而无法运行下去。为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存。有时内存中进程数目过多也需将处于就绪态的进程从内存调到盘交换区，当然在盘交换区等待时间过长的就绪态的进程也要调入内存。  
在UNIX系统中中级调度就是存储管理中的对换，即进程的图象在磁盘的交换区和内存间的对换。采用虚拟存储技术的分时系统往往设立中级调度。  
(3)高级(Long-term)调度：作业调度  
作业调度高级调度又称作业调度。作业调度用于决定把外存输入井上处于作业后备队列上的哪些作业调入内存，并为它们分配必要的资源，创建进程，设置该进程状态为就绪态，然后再将新创建的进程排在就绪队列上，参加CPU争夺。在批处理系统中，作业进入系统后，是先驻留在外存的输入井上的，因此需要有作业调度，以便将它们分批装入内存。然而在分时系统中，为了能及时响应，用户通过键盘输入的命令和数据，都是直接进入内存，因而无需配置作业调度，类似地在实时系统中通常也无需作业调度。  
作业调度还包括终止作业操作。当进程正常运行结束或因发生错误终止时，作业调度调用终止作业程序，它负责将输出文件缓冲输出到输出井，并调用SPOOLing系统输出进程将作业输出文件在打印机输出。同时回收作业所使用内、外存、I/O设备等各种资源，最后调用记帐程序结清作业费用。

### 3、调度队列模型 ###

（1）、仅有进程调度的调度队列模型  
![这里写图片描述][20170627195901863]  
（2）、具有高级和低级调度的调度队列模型  
![这里写图片描述][20170627200004646]  
（3）、同时具有三级调度的调度队列模型  
![这里写图片描述][20170627200103181]

### 4、进程调度 ###

1、进程调度的方式

*  非抢占（非剥夺）方式  
    采用这种调度方式时，一旦把处理机分配给某进程后，便让进程一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统环境。缺点是难以满足紧急任务的要求，不适用于实时、分时系统要求。
 *  抢占（剥夺）方式（Preemptive mode）  
    这种调度方式，允许进程调度程序根据某个原则，去停止某个正在执行的进程，将已分配给进程的处理机，重新分配给另一个进程。抢占的原则有：  
    （1）时间片原则。各进程按时间片运行，当一个时间片用完后，便仃止该进程的执行而重新进行调度。这个原则适用于分时系统。  
    （2）优先权原则。通常是对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，例如由阻塞态转换为就绪态，或从静止就绪态转为活动就绪态时，或新创建进入就绪态的进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便仃止正在执行的进程，将处理机分配给优先权高的进程，使之执行。

2.调度的时机  
在UNIX系统中，为了减少操作系统设计的复杂性和提高系统执行效率，对操作系统程序采用了伪异步执行方式。也就是说，设计人员认为在系统程序执行期间不会发生调度或发生调度的时间是可预知的，然而，由于调度程序swtch又是进程0的一部分，也就是说是系统程序，这又要求调度必须在核心态下完成。怎样把这二者统一起来呢？显然，采用系统调用的方式向用户开放进程调度是不可取的，这一是导致系统无法控制，二是可能造成系统瘫痪和很多意想不到的问题出现。UNIX的设计者们采用了当处理机在执行完核心程序之后向用户态转换之前的瞬间，检查各就绪进程的优先级进行调度的方法。由用户态转而执行核心程序的可能性很多,例如中断处理和陷阱处理，系统调用等。

3、调度方式和算法的选择准则和评价  
1.面向用户(User-oriented)的准则和评价  
(1)周转时间(Turnaround Time)短:  
它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。  
(2)响应时间(Response Time)快  
响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。  
(3)截止时间(Deadline)的保证  
它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。  
(4)优先权(Enforcing Priorities)准则  
在选择批处理、分时和实时系统的调度算法时，都可引用优先权准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到及时的处理。

### 5、调度算法 ###

1、先来先服务First-Come-First-Served （FCFS）（作业／进程）调度算法  
FCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。FCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。FCFS算法易于实现，表面上很公平。 FCFS算法有利于长作业，对短作业不利；有利于CPU繁忙型作业，对I/O繁忙型作业不利。 FCFS算法的缺点是平均周转时间长。

2、短作业／进程优先(SJF/Shortest Process Next)调度算法  
这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。这一算法有利于短作业，对长作业不利。采用SJF有利于系统减少平均周转时间和平均带权周转时间。  
SJ(P)F调度算法也存在不容忽视的缺点：  
(1) 该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。  
(2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。  
(3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

3、高优先权优先调度算法  
（1）、非抢占式优先权算法  
在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成； 或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。  
（2）、 抢占式优先权调度算法  
在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi＞Pj, 则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中。

4、基于时间片的轮转调度算法  
（1）、时间片轮转法  
在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。  
（2）、多级反馈队列调度算法  
![这里写图片描述][20170627202749549]

*  应设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。
 *  当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。
 *  仅当第一队列空闲时，调度程序才调度第二队列中的进程运行； 仅当第1~(i-1) 队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

## 三、进程死锁 ##

在多道程序系统中，通过多个进程并发执行可改善系统的资源利用率和提高系统的处理能力，但也带来一种危险，即死锁现象发生。所谓死锁是指计算机系统和进程所处的一种状态。在系统中，两个或多个进程无限期地等待永远不会发生的条件，此时称此系统处于死锁状态。

### 1、产生死锁的原因 ###

*  竞争资源引起死锁  
    在多道程序系统，多个进程共享系统的资源。系统资源分为二类，一类是不可抢占的资源，如打印机、磁带机等。当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。另一类是可抢占的资源，如CPU、内存等。由于系统拥有的不可抢占的资源有限，多个进程共享竞争不可抢占的资源就可能引起死锁。  
    例如系统只有一台打印机R1和一台磁带机R2，可供进程P1和P2共享。假如P1已占用了打印机R1，而P2占用了磁带机R2。此时若P2继续要求打印机，P2将阻塞；P1若又要求使用磁带机，P1也将阻塞。于是P1与P2之间便形成了僵局，而两个进程都在等待对方释放出自己所需要的资源，但它们又都因不能获得所需的资源而不能继续推进，从而也不能释放出自己占有的资源，以致进入死锁状态。
 *  进程推进顺序不当引起死锁  
    在多道程序系统中，并发执行的进程推进序列不可预测，有些推进顺序，进程可以顺利完成，这些推进顺序是合法的；而有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。

### 2、产生死锁的必要条件（ Conditions for Deadlock ） ###

*  互斥（ Mutual exclusion ）条件：一个资源一次只能被一个进程所使用，即是排它性使用。
 *  不可抢占（ No preemption ）条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占。
 *  请求和保持（ Hold-and-wait ）条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。
 *  环路等待（ Circular wait ）条件：当每类资源只有一个时，在发生死锁时，必然存在一个进程-资源的环形链。如P1正在等待一个P2占用的资源R2，P2正在等待一个P1占用的资源R1。

产生死锁这四个条件仅是必要条件而不是充分条件，即只要发生死锁则这四个条件一定同时成立，但反之则不然。

### 3、处理死锁的基本方法 ###

*  死锁的预防  
    静态的方法：在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。
 *  死锁的避免  
    动态的方法：在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。
 *  死锁的检测和解除  
    这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生，如检测到死锁，则采用撤消进程等死锁解除方法使系统恢复正常工作。
 *  驼鸟算法(The Ostrich Algorithm)  
    自称没有死锁问题，理由是死锁极少发生和预防的成本太高。如发生死锁采用重启动和人工恢复方法。这是方便和正确的折中方法。大部分的操作系统包括UNIX and Windows 采用这种方法。

### 4、死锁的预防(Deadlock Prevention) ###

预防死锁的方法是破坏四个产生死锁的必要条件之一。

*  破坏互斥条件  
    互斥使用是资源本身特征所决定的。使用硬软件结合可改变资源本身特性，例如采用SPOOLing技术可将“独享” 打印机改变为“共享”的打印机。
 *  破坏不可抢占条件  
    抢占式调度法主要用于处理机和存贮器资源调度，它们的状态容易保存和恢复。但此法对外部设备和私存数据不宜使用。
 *  破坏请求和保持条件  
    系统可采用资源静态予先全分配方式来破坏请求保持条件。系统要求所有进程一次性地申请在整个运行过程中全部资源，若系统有足够资源满足给进程，则在运行前，一次性将其所需要的所有资源分配给该进程。这样该进程在整个运行期间，便不再提出资源要求，从而摒弃了请求条件。这种预防死锁的方法，优点是简单、易予实现且很安全，但其资源利用率很低，进程也延迟运行。
 *  破坏循环等待条件  
    有序资源使用法：该方法将所有的资源按类型进行线性排队，并赋予不同的序号。例如令输入机的序号为1，打印机序号为2，磁盘机序号为3等。所有进程对资源的请求必须严格按资源序号递增的次序提出。这样在所形成的资源分配图中不可能再出现环路，因而摒弃了“环路等待”条件。系统要求申请进程： （1）对它所必须使用的而且属于同一类的所有资源，必须一次申请完； （2）在申请不同类资源时，必须按各类设备的编号依次申请。  
    例如：进程PA，使用资源的顺序是R1，R2； 进程PB，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。  
    采用有序资源分配法：R1的编号为1，R2的编号为2； PA：申请次序应是：R1，R2 ，PB：申请次序也应是：R1，R2  
    这样就破坏了环路条件，避免了死锁的发生。

### 5、死锁的避免(Deadlock Avoidance) ###

*  根据系统的安全状态避免死锁  
    在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。所谓安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
 *  利用银行家算法避免死锁  
    1、银行家算法中的数据结构  
    (1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。  
    (2) 最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。  
    (3) 分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。  
    (4) 需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Need［i,j］=Max［i,j］-Allocation［i,j］  
    2、银行家算法  
    设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：  
    (1) 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。  
    (2) 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。  
    (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：  
    Available［j］∶=Available［j］-Requesti［j］;  
    Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;  
    Need［i,j］∶=Need［i,j］-Requesti［j］;  
    (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。  
    3、安全性算法  
    安全性算法执行步骤如下：  
    (1)初始化设置工作向量Work\[m\]表示系统可提供的各类资源数目，用以保护原数据结构有关值。Work = Available，设置完成标志向量 Finish\[n\]。Finish\[i\] = false 表示i进程尚末完成，如值为true则表示进程i已完成。  
    (2)从进程集合n中找到一个能满足下述二个条件: Finish\[i\] = false和Need\[i\]≤Work\[i\]，如找到则执行步骤3，如找不到同时满足以上二条件的进程则执行步骤4。  
    (3)当进程i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：  
    work = work+Allocationi ； Finish\[i\]=true ；转执行步骤2。  
    (4)如果所有的Finish\[i\]＝ture，则表示系统处于安全状态，否则系统处于不安全状态。  
    4、银行家算法之例  
    假定系统中有五个进程｛P0, P1, P2, P3, P4｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。  
    ![这里写图片描述][20170627211523107]  
    (1)T0时刻的安全性：  
    ![这里写图片描述][20170627213608118]  
    (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：  
    ① Request1(1, 0, 2)≤Need1(1, 2, 2)  
    ② Request1(1, 0, 2)≤Available1(3, 3, 2)  
    ③ 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成资源变化。  
    ④ 再利用安全性算法检查此时系统是否安全。  
    ![这里写图片描述][20170627213633876]  
    (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：  
    ① Request4(3, 3, 0)≤Need4(4, 3, 1);  
    ② Request4(3, 3, 0) < Available(2, 3, 0)，让P4等待  
    (4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：  
    ① Request0(0, 2, 0)≤Need0(7, 4, 3);  
    ② Request0(0, 2, 0)≤Available(2, 3, 0);  
    ③ 系统暂时先假定可为P0分配资源，并修改有关数据，如图所示。  
    ![这里写图片描述][20170627213715090]

### 6、死锁的检测(Deadlock Detection) ###

死锁的避免算法增加了系统的开销，死锁的检测采用资源分配图的简化判断是否发生了不安全状态。如发现系统处于不安全状态时，即执行死锁解除的策略，采用此法开销相对减少。  
1、资源分配图的简化：  
系统处于某S状态时可用资源分配图表示，可用资源分配图简化来判断系统是否处于死锁状态。资源分配图简化的方法如下：在资源分配图中找一个既不阻塞又非孤立的进程结点PI（如某进程既无已分配的资源也不需申请资源，即既无分配边又无申请边，则该进程结点是孤立结点），让它获得所需资源而继续运行直至完毕，再释放它拥有的所有的资源，这相当于取消PI的分配边和请求边，使它成为孤立结点。经过以上简化，如所有的进程结点都是孤立结点则称资源分配图是可完全简化的。若不能通过任何过程使该图完全简化，则该图是不可完全简化的。  
2、死锁定理：  
系统状态S为死锁状态的充分条件，当且仅当S状态的资源分配图是不可完全简化时，该充分条件称为死锁定理。在不可完全简化的资源分配中不能简化为孤立结点的进程是死锁进程。反之若状态S的对应资源分配图是可化简的，则状态S是安全的。

### 7、死锁的解除 ###

当检测死锁的软件判别死锁存在时，就要解除死锁，使系统从死锁中恢复。当前系统中所使用的死锁恢复办法是强制性地从系统中撤消一个或多个死锁进程以断开循环等待链，并收回分配给终止进程的全部资源供剩下的进程使用。借助于撤消进程来解除死锁可以使用两种方法。一种是撤消全部的死锁进程，这显然会断开死锁环路，但代价太大。另一种方法是逐个撤消死锁的进程直至死锁环路消除。这里存在一个按照什么原则进行逐个撤消进程的问题。目前较实用而又简便的方法是撤消那些代价最小的进程。所谓影响一个进程的撤消代价因素有该进程的优先权，该进程运行到今的运行代价（包括CPU时间，使用资源的种类和时间等）、与相关的作业类型和外部代价等。

[20170627194204992]: /images/20220613/6b350b9aa62a45a685f5bd0a3d5dbd93.png
[20170627195901863]: /images/20220613/29e12d240c4948a981064c808e94a902.png
[20170627200004646]: /images/20220613/a331880ea9c54c53aeb3c19117c576ee.png
[20170627200103181]: /images/20220613/a4c7168a0b7c4c3c94a7a75e2a5545ed.png
[20170627202749549]: /images/20220613/4ebab831a0ad4c5ebb1bdef248362e27.png
[20170627211523107]: /images/20220613/bcd41eb8b2124d1f9415d63a7a311293.png
[20170627213608118]: /images/20220613/bcfd1df483ac4c6b8c89d3c336d369d2.png
[20170627213633876]: /images/20220613/a84fa4afa8914a4eac294918fef029af.png
[20170627213715090]: /images/20220613/d43973bb42c043a9b9232e3821255549.png