os-第3章处理机调度和死锁

南昌大学信息管理系

NanChangUniversityDepartmentofinformationmanager操作系统OperatingSystem第二部分B处理机调度与死锁南昌大学信息管理系

NanChangUniversityDepartmentofinformationmanager3.1处理机调度的基本概念

高级调度低级调度中级调度按OS的类型分：批处理调度分时调度和实时调度多处理机调度等按调度层次分：处理机调度的基本类型：

一个作业从提交给计算机系统到执行结束退出系统，一般都要经历4个状态：提交、后备（收容）、执行和完成。1）提交状态：通过终端设备向计算机的磁盘输入作业信息时所处的状态。2）后备状态：作业的全部信息已输入到磁盘的一个专用区(输入井)中等待作业调度时所处的状态。3）执行状态：在后备作业队列中的作业一旦被作业调度程序选中，为它分配了必要的资源，并且建立了进程,开始处理时所处的状态。4）完成状态：作业完成其全部任务后，进程撤消,做善后处理时的作业状态称为完成状态。作业的状态一、作业的状态及其转换

作业的状态及其转换执行进程调度

内存

线程调度运行等待就绪外存

就绪等待提交后备完成作业输入作业调度

交换调度

作业调度

执行一、高级调度（作业调度）

HighLevelScheduling

决定允许哪些作业竞争系统资源。也就是说，高级调度用于决定把外存上处于后备状态的作业按照一定的算法，选取出一个作业，当内存空间满足其要求时，为它分配存储空间，调入内存，创建该作业的进程，再分配它所需的I/0设备及其它资源，再将新进程排在就绪队列上，新进程具有了获得处理机的资格。

外存后备状态作业调入内存，分配资源创建进程就绪队列在执行作业调度时，要做以下两步：接纳多少个作业接纳哪些作业二、低级调度（LowLevelScheduling）就绪队列进程获得处理机

也称进程调度，它决定在就绪队列中哪一个进程将分配到处理机，并由分派程序把处理机实际分配给这个进程。进程调度可采用下述两种方式：非抢占方式抢占方式

抢占原则： （1）时间片原则 （2）优先权原则 （3）短作业优先原则三、中级调度（IntermediateLevelScheduling）

目的：是为了提高内存的利用率和系统吞吐量。四、三级调度的关系3.1.2进程调度队列模型1、仅有进程调度的调度队列模型2、具有高级和低级调度的调度队列模型3、同时具有三级调度的调度队列模型进程完成CPU进程调度时间片完阻塞队列就绪队列事件出现交互用户等待事件仅有进程调度的调度队列模型CPU进程调度作业调度超时就绪队列等待事件2事件2出现后备作业队列具有高,低两级调度的调度队列模型事件n出现事件1出现等待事件n等待事件1………完成中级调度CPU进程调度作业调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度具有三级调度时的调度队列模型3.1.3选择调度方式和调度算法的若干准则1、面向用户的准则（1）周转时间短（2）响应时间快（3）截止时间的保证（4）优先权准则1、平均周转时间周转时间：由等待时间、执行时间等组成

平均周转时间：Ti=1/n∑Ti n>=1，n为作业或进程个数。2、带权周转时间

带权周转时间：Wi=Ti/Tr

周转时间与执行时间之比。

平均带权周转时间：W=1/n∑Wi

n为作业或进程个数。3、响应时间

响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应位置的时间说直到或在屏幕上显示出结果为止的一段时间间隔。包括： （1）从键盘输入的请求信息传送到处理机的时间； （2）处理机对请求信息进行处理的时间； （3）将所形成的响应回送到终端显示器的时间。2、面向系统的准则（1）系统吞吐量高。（2）处理机利用率好。（3）各类资源的平衡利用。选择调度方式和调度算法的若干准则（续）进程调度

进程调度的任务就是按照一定的策略负责把处理机分配给某一就绪进程。由进程调度程序具体实现处理机在进程之间的转换。进程调度程序的功能具体功能包括： （1）记录系统中所有进程的执行情况。 （2）进行进程上下文切换

进程上下文实际上是进程执行活动全过程的静态描述，进程上下文包括计算机系统中与执行进程有关的各种寄存器的值，程序段在经过编译之后形成的机器指令代码集（正文段）、数据集及各种堆栈值和PBC结构。进程调度的时机

进程调度的时机与引起进程调度的原因以及进程调度的方式有关。 一、引起进程调度的原因 （1）正在执行的进程执行完毕。 （2）执行中的进程提出I/O请求后被阻塞。（3）执行某种原语操作，比如wait(s)，block原语，wakeup原语。

（4）分时系统中，由于分配给该进程的时间片已经用完。 （5）执行中进程自己调用阻塞原语将自己阻塞起来。 （6）执行完系统程序后返回用户进程时，可看作系统进程执行完毕，从而可以调度选择一个新的用户进程执行。 以上是在不可剥夺方式下的引起进程调度的原因，在CPU执行方式是可剥夺时，还有一个原因。

（7）一个比正在运行进程的优先数更高的进程进入就绪队列，从而引起调度。 在以上所列的几种原因之一发生的情况下，OS进行进程调度。进程上下文切换

进程上下文由正文段、数据段、硬件积存器的内容以及有关数据结构等组成。在发生进程调度时系统要做进程上下文切换。进程上下文切换包括四个步骤：

（1）决定是否做上下文切换以及是否允许做上下文切换。在OS中不是每进每刻上下文切换进程都在检查和分析是否可做上下文切换。在可剥夺方式中，是采用优先级高的进程发生信号中断正在执行的优先级低的进程，从而进行上下文切换；在不可剥夺方式中可采用时间片方式，也可采用原语调用，调用上下文切换程序。

（2）保存当前执行进程的上下文

当前执行进程是指调用上下文切换程序之前的执行进程。上下文切换程序不能破坏“老”进程的上下文结构。

（3）采用进程调度算法，从就绪队列中选择一个进程。 （4）恢复或装配所选进程的上下文，把处理机分配给所选进程。§3.2调度算法

在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。3.2.1先来先服务和短作业优先调度算法

1、先来先服务调度算法 先来先服务FCFS调度算法是一种最简单的调度算法。 作业调度中采用该算法时，每次调度是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。既可用于进程调度，也可用于作业调度

在进程调度中，采用FCFS时每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投入运行，该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。

进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B11001101100100/100=1C21101102102-2=100100/1=100D3100102202199199/100=1.99

可见，FCFS调度算法有利于CPU繁忙型的作业，

FCFS调度算法不利于I/0繁忙型作业。

FCFS在一定意义上是公平合理的。

FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。先来先服务不能保证良好的响应时间，在处理交互用户时很少用这种方法。2.短作业（进程）优先调度算法（ShortestJobFirst）SJF

短作业（进程）优先调度算法SJ(P)F，是指对短作业或进程优先调度的算法。它们可分别用于作业调度(SJF)和进程调度(SPF)。

二、实例

作业调度情况算法进程名ABCDE平均到达时间01234

服务时间43524

FCFS完成时间47121418

周转时间47-1=612-2=1014-3=1118-4=144+6+10+11+14/5=9带权周转时间16÷3=210÷5=211÷2=5.514÷4=3.51+2+2+5.5+3.5/5=2.8SJF完成时间46+3=913+5=184+2=69+4=13

周转时间4818-2=166-3=313-4=94+8+16+3+9/5=8

带权周转时间18÷3=2.6716÷5=3.13÷2=1.59÷4=2.251+2.67+3.1+1.5+2.25/5=2.1

FCFS:只考虑等待时间，而不考虑运行时间。

SPJ、SJF：根据作业（进程）占用处理机时间长短而定，注重了作业运行时间。

SJF调度算法能有效地降低作业的平均等待时间和提高系统的吞吐量。

SJ(P)F调度算法的缺点：（1）该算法对长作业非常不利。（2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会得到及时处理；（3）由于作业（进程）的长短只是根据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。

FCFS与SJF都属于非剥夺调度，不适用在合理的响应时间应得到保证的分时环境中。FCFS与SJF属于非剥夺调度，还是可剥夺调度？3.2.2

优先权（级）调度算法

该算法的核心是确定作业或进程的优先权。一、优先权调度算法的类型

当用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，这时又可进一步把该算法分成两种方式：

1.非抢占式优先权算法

2.抢占式优先权调度算法二、优先权类型

设计优先权的主要原则是充分地利用处理机，使用户进程尽可能地并行运行。优先权可分为静态优先权和动态优先权。

确定作业的静态优先权可根据以下原则：

（1）由用户自己根据作业的紧急程度输入一个适当的优先权。（2）由系统或操作员根据作业类型指定优先权。作业类型可由用户约定，也可以由操作员指定。（3）作业使用资源。1).静态优先权进程的静态优先权确定原则：（1）进程类型。（2）进程对资源的要求。（3）根据用户的要求。（4）将作业的静态优先权作为它所属进程的优先级。

静态优先权法简单易行，系统开销小，但不够精确，很可能出现优先权低的作业或进程，长期没有被调度的情况，而且静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。因此，仅在要求不太高的系统中才使用静态优先权。2).动态优先权

动态优先权把作业或进程的静态特性和动态特性结合起来确定作业或进程的优先权，随着作业或进程的执行过程，其优先权不断变化。

动态优先权的确定原则：（1）根据进程占有CPU时间的长短来决定。（2）根据就绪进程等待CPU的时间长短来决定。3高响应比优先调度算法

(HighResponse-ratioNext)

BrichHansen发展的最高响应比优先调度策略修正了最短作业优先调度的某些弱点，特别是后者忽视长作业，优待新的短作业的弱点。HRN是一种非剥夺调度优先权的变化可描述为：

响应比要求服务时间响应时间要求服务时间要求服务时间等待时间优先权==+=R

该算法既照顾了短作业，又考虑了作业到达的先后次序，也不会使长作业长期得不到服务，是介于FCFS与SJF之间的一种算法，由于每次调用前，都要先进行响应比的计算，这会增加系统的开销。

3.2.3基于时间片的轮转调度算法

（RoundRobin）一、基本原理

系统将所有的就绪进程按先来先服务原则，排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片，当执行的时间片用完时，由计时器发出时钟中断，调度程序根据这个信号来停止该进程的执行，把它放到就绪队列的末尾，等待下一次执行；然后再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就保证就绪队列中的所有进程，在一个给定的时间内，均能获得一时间片的处理机执行时间。

轮转法只能调度分配可抢占的资源，而作业调度是对除了CPU之外的所有系统硬件资源的分配，其中包含有不可抢占资源，比如说打印机，所以作业调度不使用轮转法,也就是说轮转法只适用于进程调度。

轮转法能否用于作业调度?二、时间片大小的确定

1、系统对响应时间的要求响应时间T与用户进程N和时间片q成正比，T=Nq。当进程数目一定时，时间片量值与系统响应时间成正比。

轮转法的性能几乎完全取决于时间片2、就绪队列中进程的数目T=Nq3、系统的处理能力

系统的处理能力是必须保证用户键入的常用命令能在一个时间片内处理完毕，否则将无法保证得到满意的响应时间，而且会使平均周转时间及带权周转时间都很长。

在时间片轮转法中，就绪进程按照先来先服务的原则排队，每个进程轮流地运行大小相等的时间片，对短作业和I/O操作较高的作业是不利的。如果有紧急进程进入就绪队列，并不能得到及时响应。2多级反馈队列调度算法

多级反馈队列调度算法，事先不必知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而是目前公认的较好的调度算法。优先权高一级

二级

n级

就绪队列1

就绪队列2就绪队列n

（先来先服务）（先来先服务）（轮转）

剥夺

S1至CPUS1至CPU至CPU低时间片短时间片S1<S2<S3长

在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下：

3、多级反馈队列调度算法的性能1、终端型作业用户2、对于中短批处理型作业3、长批处理作业用户（不会长期得不到处理）

Windows2000/XP调度策略线程时间配额：是一个线程从进入运行状态到Windows2000/XP检查是否有其他优先级相同的线程需要开始运行之间的时间总合。１.时间配额的计算缺省时，windows2000专业版线程时间配额为6,windows2000服务器版为36。每次时钟中断，时钟中断服务例程从线程的时间配额中减少３，如果没有剩余的时间配额，系统将触发时间配额用完处理，选择另外一个线程进入运行状态。时间配额的控制在系统注册表中的一个注册项“HKEY_LOCAL_MACHINE\SYSTEM\CurrentConctrolSet\Control\PriorityControl\Win32PrioritySeparation”,允许用户指定线程时间配额的相对长度（长或短）和前台进程的时间配额是否加长。

6４２０时间配额长度前后台变化前台进程时间配额提升注册表Win32PrioritySeparation的定义时间配额长度：１—长时间，２—短时间，0,３—缺省前后台变化：１—改变前台进程时间配额，２—前后台进程时间配额相同，0,３—缺省前台进程时间配额提升:该字段是一个时间配额表索引，用于设置前后台进程的时间配额，前台为第一项，后台为第二项。在任务管理器中修改进程优先级类型的方法是：在“进程”栏中用鼠标右击下拉菜单中的“设置优先级”。通过注册表来设置时间配额时，用户可对３个字段中的内容进行任意组合。通过“控制面板”来设置时间配额时，用户只有２种选择。设置方法：从“控制面板”中的“系统”或“我的电脑”中的“属性”找到“性能”设置窗口。优化应用的性能：短时间配额和改变前台进程的时间配额优化后台服务的性能：长时间配额和前后台进程的时间配额相同一.单处理器系统中的线程调度1.主动切换线程可能因为进入等待状态而主动放弃处理器的使用，等待的对象可能是事件，互斥信号量，资源信号量，I/O操作，进程，线程，窗口消息等。２.抢先可能出现抢先的情况：１)高优先级线程的等待完成，即一个线程等待的事件出现。２）一个线程的优先级被增加或减少。当线程被抢先时，它被放到相应优先级的就绪队列的队首。处于实时优先级的线程在抢先时，时间配额被重置为一个完整的时间片；而处于动态优先级的线程在被抢先时，时间配额不变，重新得到处理器使用权后将运行到剩余的时间配额用完。被抢先的线程是排在就绪队列的队首，而不是队尾。3.时间配额用完是否要降低该线程的优先级，是否要调度另一个线程线程进入运行状态。４.结束调用ExitThread,TerminateThread来终止。线程优先级提升：1）I/O操作完成。2）信号量或事件等待结束。3）前台进程中的现程完成一个等待操作。4）由于窗口活动而唤醒图形用户接口线程。5）线程处于就绪状态超过一定时间，但没能进入运行状态（处理器饥饿）优先级提升的目的：改进系统吞吐量、响应时间等整体特性，解决线程调度策略中潜在的不公正性。3.5产生死锁的原因和必要条件3.5.1产生死锁的原因(Continued)所谓死锁,是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程将永远不能再向前推进.产生死锁的原因资源不足导致的资源竞争进程推进顺序不合理1竞争资源引起进程死锁系统中的资源分为两类：可剥夺资源：某进程在获得这类资源后，该资源可以被其他进程或系统剥夺。例子：cpu和主存不可剥夺资源：系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放。例子：磁带，打印机2竞争非剥夺性资源资源分配图涉及非剥夺性资源死锁的例子3临时竞争性资源由一个进程产生，被另一进程使用一短暂时间便无使用的资源。例子：中断,信号,消息,I/O缓冲区中的信息涉及临时竞争资源死锁的例子P1: … receive(P2); … send(P2,M1); …P2: … receive(P1); … send(P1,M2); …2.进程推进顺序不当引起死锁2.进程推进顺序不当引起死锁(续）关于死锁的一些结论：参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。3.5.2产生死锁的必要条件互斥条件指进程对所分配到的资源进行排他性使用,即在一段时间内某资源只由一个进程占有.如果此时还有其它进程要求该资源,要求者只能阻塞,直至占有该资源的进程用毕释放.请求和保持条件进程已经保持了至少一个资源,但又提出了新的资源要求,而该资源又已被其它进程占有,此时请求进程阻塞,但又对已经获得的其它资源保持不放.死锁的必要条件(Continued)不剥夺条件进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放.环路等待条件在发生死锁时,必然存在一个进程-资源的环形链.即进程集合{P0,P1,P2,…,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源.3.5.3处理死锁的基本方法预防死锁：破坏产生死锁的必要条件避免死锁:在资源动态分配的过程中，防止系统进入不安全状态检测死锁：检测死锁，并清除死锁解除死锁：将进程从死锁状态中解脱出来。3.6预防死锁的方法通过破坏产生死锁的四个必要条件中的一个或多个条件,保证不会发生死锁互斥条件由设备的固有特性所决定,应加以保证1.摒弃“请求和保持”系统要求所有进程要一次性地申请在整个运行过程需的全部资源优点:简单、易于实现、安全缺点:资源严重浪费,进程延迟运行3.6.1预防死锁2.摒弃“非剥夺”条件方法:一个已经保持了某些资源的进程,当它再提出新的资源请求而不能立即得到满足时,必须释放它已经保持的所有资源,待以后需要时再重新申请OS可以剥夺一个进程占有的资源,分配给其他进程适用条件资源的状态可以很容易地保存和恢复缺点实现复杂、代价大,反复申请/释放资源,系统开销大,降低系统吞吐量3.摒弃“环路等待”方法系统把所有资源按类型进行线性排队;所有进程对资源的请求必须严格按资源序号递增的顺序提出,从而保证任何时刻的资源分配图不出现环路问题:此方法要求资源类型序号相对稳定,不便于添加新类型的设备.易造成资源浪费,类型序号的安排只能考虑一般作业的情况,限制用户简单、自主地编程3.6.2系统安全状态不需事先采取限制措施破坏产生死锁的必要条件;在资源的动态分配过程中,采用某种策略防止系统进入不安全状态,从而避免发生死锁如果一个新的进程的资源请求会导致死锁,则拒绝启动这个进程如果满足一个进程新提出的一项资源请求会导致死锁,则拒绝分配资源给这个进程

拒绝启动进程策略在启动一个新的进程时,首先检查它的资源请求,仅当

当前所有进程的最大资源请求量+

新进程的请求量<=

系统资源量

时才启动新进程.考虑所有进程的最大请求,条件过于严格.系统的安全状态安全状态:系统能按某种顺序,如<P1,P2,…,Pn>,为每个进程分配所需资源,直到最大需求,使每个进程都可顺序完成,称系统处于安全状态.安全序列:上述的资源分配顺序,如<P1,P2,…,Pn>.安全序列可以不唯一!不安全状态:系统中不存在安全序列.不安全状态不一定是死锁状态.只要系统处于安全状态,必定不会进入死锁状态.避免死锁的实质:如何使系统不进入不安全状态.银行贷款问题的描述银行有一笔数目有限的现金可供借贷,以及一批借贷客户.每个客户有各自的借款限额(最大借款额).客户可在借款限额范围内一次借贷一部分现金,且不保证在获得最大贷款额之前做出任何偿付.如果在满足一个客户的一次借贷请求之后,银行可能没有足够的资金以保证所有客户最终偿还所有贷款,那么银行可以拒绝这项请求.例:某银行共有资金100万元和三个借贷客户甲、乙、丙,他们的最大借款额分别为100,80,70(万元).他们已借得的金额分别为10,20,50(万元).银行还有资金多少?各客户还需多少资金?按目前状况,银行可能收回全部贷款吗?如果乙提出借10万,可以满足吗?如果丙提出借10万,可以满足吗?银行家算法中的数据结构

设系统中有m种不同资源,n个进程Resource向量:系统中每种资源的总量Resource[j]:资源j的总量Available向量:系统中尚未分配的每种资源的总量Available[j]:尚未分配的资源j的数量Max矩阵:各个进程对每种资源的最大需求量(进程事先声明)Max[i,j]:进程i对资源j的最大需求量Allocation矩阵:当前资源分配状况Allocation[i,j]:进程i获得的资源j的数量Need矩阵:每个进程尚需的各类资源数量Need[i,j]:进程i尚需的资源j的数量各数据间的关系对所有的i,j(i=1,2,…,n;j=1,2,…,m),有:Resource[j]=Available[j]+(Allocation[1,j]+Allocation[2,j]+…+Allocation[n,j])Max[i,j]<=Resource[j]Allocation[i,j]<=Max[i,j]Allocation[i,j]+Need[i,j]=Max[i,j]二银行家算法设Requesti是进程Pi的请求向量，如果Requesti[j]=k,表示进程Pi需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：（1）如果Requesti<=Needi,则转向步骤(2)，否则，认为出错，因为它所申请的资源已超过它所宣布的最大值；（2）如果Requesti<=Availablei,则转向步骤(3)，否则，表示系统中尚无足够的资源，Pi必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面的数据结构中的数值：

Available=Available-Requesti;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才是将资源分配给进程Pi,以完成此次分配；否则，将试探分配作废，恢复原来的资源分配状态，让Pi等待。三安全性算法系统所执行的安全性算法可描述如下：（1）设置两个向量工作向量Work：它表示系统可提供给进程继续运行的各类资源数目，它包含有m个元素，执行安全算法时，Work=Available

进程是否完成标志finish:开始时先令finish[i]=false;当有足够的资源分配给进程时，令finish[i]=true(2)从进程集合中找到一个能满足下述条件的进程

finish[i]=falseneed[i]<=work

如果找到，执行步骤（3），否则执行步骤（4）（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源：Work=work+Allocation[i]finish[i]=true

转向（2）（4）如果所有进程的finish[i]=true,则表示系统处于安全状态，否则，系统处于不安全状态。一个安全性计算的实例死锁避免小结优点比死锁预防限制少无死锁检测中的资源剥夺,进程重启缺点必须事先声明每个进程请求的最大资源考虑的进程必须是无关的,也就是说,它们执行的顺序没有任何同步要求的限制资源数目必须是固定的在占有资源时,进程不能退出3.7死锁的检测与解除3.7.1死锁的检测系统必须:保存有关资源的请求和分配信息提供一种算法,以利用这些信息来检测系统是否已进入死锁状态1.资源分配图资源类（资源的不同类型）:用方框表示资源实例（存在于每个资源中）:用方框中的黑圆点表示进程:用圆圈中加进程名表示分配边：资源实例进程的一条有向边申请边：进程资源类的一条有向边有环有死锁有环无死锁2.死锁定理

如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件资源分配图化简方法如下:1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边3)进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立的结点，则该图是可完全简化。否则该图是不可完全简化的。3.死锁检测中的数据结构(1)可利用资源向量Available(2)把不占用资源的进程(向量Allocation:=0)记入L表中,即LiUL.(3)从进程集合中找到一个Requesti<=Work的进程,做如下处理:将其资源分配图简化,释放资源,增加工作向量work:=work+Allocationi将它记入L表中(4)若不能把所有进程都记入L表中,该系统状态将发生死锁.Work:=Available;L:={Li|Allocationi=0∩Requesti=0}ForallLi不属于LdoBeginforallRequesti<=workdobeginwork:=work+AllocationiLiUL;EndEndDeadlock:=¬(L={p1,p2,…pn});

3.7.2死锁的解除方法:取消所有的死锁进程把每个死锁进程备份到前面定义的某些检查点,并且重新启动所有进程连续取消死锁进程直到不再存在死锁连续剥夺资源直到不再存在死锁选择取消死锁进程或剥夺资源时要考虑代价问题进程和线程函数（一）CreateProcess**CreateThread****ExitProcess**ExitThread***GetCurrentProcess*GetCurrentProcessId*GetCurrentThread****GetCurrentThreadId****进程和线程函数(二)GetExitCodeProcess*GetExitCodeThread*GetThreadPriority****OpenProcess*ResumeThread***SetThreadPriority***Sleep*CloseHandle****进程和线程函数(三)SuspendThread***TerminateProcess**TerminateThread***ThreadProc****同步函数(一)临界段Critical_Section类型InitializeCriticalSection*DeleteCriticalSection*EnterCriticalSection*LeaveCriticalSection*TryEnterCriticalSection*同步函数(二)互斥体(Mutex)和信号量(Semaphore)：类型是HANDLECreateMutex****ReleaseMutex****CreateSemaphore****ReleaseSemaphore****CloseHandle****同步函数(三)Wait函数WaitForMultipleObjects****WaitForMultipleObjectsEx**WaitForSingleObject****WaitForSingleObjectEx**相关头文件:#include<winbase.h>库文件：kernel32.lib调试函数GetLastError()TRACE宏printf()coutsprintf()2）交换调度（中级调度）（均衡调度）：按照给定的原则实现进程在主存和外存交换区之间的换进换出，以解决内存紧张问题，特别是具有虚拟存储器的系统中。3）进程调度（低级调度）：按照某种策略从进程就绪队列中选择一个就绪进程，使其占有处理机运行。处理机调度可以分为3级：1）作业调度（高级调度）：按一定原则选择若干个后备作业调入主存，分配资源，并建立相应的进程，投入运行。当该作业执行完毕时，还负责回收资源。二、作业调度的功能

作业调度的主要任务：完成作业从后备状态到运行状态和从运行状态到完成状态的转变。1）记录系统中各作业的状况。

作业调度程序应包括以下功能：

作业调度程序为了挑选一个作业投入运行，并且在运行中对它实施管理，它必须掌握该作业进入系统时的有关情况并随时记录该作业在各运行阶段的变化。为此，系统为每一个已进入系统的作业分配一个作业控制块JCB(JobContrlblock)。每个作业的JCB在该作业进入后备状态时由系统建立．在该作业退出系统时由系统撤消。每个作业在各阶段的情况(包括分配的资源和作业状态等)都记录在它的JCB中。2)按一定的调度算法，从后备作业中挑选出一个或几个作业运行。系统中处于后备状态的作业较多，几十个甚至几百个，处于运行状态的作业只是有限的几个如最多不超过4个或8个。作业调度程序的一个重要职能就是在适当的时候按一定的调度原则从后备作业中挑选出若干个作业投入运行。3)为被选中的作业做好执行前的准备工作。为该作业建立相应的进程，并且为这些进程提供所需的资源，如内存和外部设备等。4)在作业执行结束时做善后处理工作。

输出如运行时间、作业执行情况等必要信息，回收该作业所占用的全部资源，撤消与该作业有关的全部进程和该作业的作业控制块。注：1）处理机的分配工作由进程调度程序完成。内存的分配和释放工作由存贮管理程序完成。外部设备的分配和释放工作由设备管理程序完成。三、作业控制块2）作业调度程序只保证被选中的作业获得使用处理机的资格，把一个作业的内存、外设要求转给相应的管理程序。

作业控制块JCB是作业存在的标志，记录与该作业有关的信息。作业调度算法

按作业来到的先后次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。优点：容易实现；缺点：没有考虑各个作业运行特征和资源要求的差异，系统效率较低。1.先来先服务调度算法（FCFS）

例：先来先服务调度算法（单位：小时，并以十进制计）作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周转时间T＝1.725平均带权周转时间W＝6.8752.短作业优先调度算法（SJF）

此算法总是优先调度要求运行时间最短的作业。优点：易于实现，效率比较高。缺点：只照顾短作业而不考虑长作业的利益。如果系统不断地接受新的短作业。则有可能较长作业长时间等待而不能运行。例：短作业优先调度算法（单位：小时，并以十进制计）作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.3010.802.304.639.000.1010.0010.101.101149.500.2010.1010.300.804平均周转时间T＝1.55平均带权周转时间W＝5.153.响应比高者优先调度算法

响应比是指作业的响应时间与作业估计运行时间的比值。

选择原则是优先选取响应比值最大的作业。即兼顾等待时间长和运行时间短的作业，它是FCFS和SJF算法的结合。响应比＝1＋作业等待时间/执行时间

作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.1010.602.104.239.000.1010.0010.101.101149.500.2010.6010.801.306.5例：响应比高者优先调度算法（单位：小时，并以十进制计)平均周转时间T＝1.625，平均带权周转时间W＝5.675

响应比＝1＋作业等待时间/执行时间例如：当作业3结束时，Rp2=1＋作业等待时间/可执行时间=1+(10.10-8.50)/0.5=1+3.2Rp4=1＋作业等待时间/可执行时间=1+(10.10-9.50)/0.2=1+3

这种算法是根据确定的优先数来选取作业，每次总是选择优先级最高的作业。4.最高优先级优先调度算法规定用户作业优先数的方法:1）由用户自己提出作业的优先数。有的用户为了自己的作业尽快被系统选中就设法提高自己作业的优先数，这时系统可以规定优先数越高则需付出的计算机使用费就越多，以作限制。2）由系统综合有关因素来确定用户作业的优先数。

例如，根据作业的缓急程度、作业计算时间的长短、等待时间的多少、资源申请情况等来确定优先数。确定优先数时，各因素的比例应根据系统设计目标来分析这些因素在系统中的地位而决定。3.3进程调度进程调度：就是系统按照某种算法把CPU动态地分配给某一就绪进程。进程调度工作是通过进程调度程序来完成的。一、调度/分派结构调度程序：将进程插入就绪队列，按一定原则保持队列结构；分派程序：将进程从就绪队列中移出，建立它执行的机器状态。进程切换：把一个进程让出处理机，由另一个进程占用处理机的调度过程称为“进程切换”。

分派程序首先将正在执行的进程的CPU现场信息保存在该进程PCB的现场保护区中，再从被调度选中的进程PCB的现场保护区中取出它的CPU现场信息恢复。CPU现场信息由程序状态寄存器、程序计数器以及若干通用寄存器的内容组成。1.记录系统中所有进程的执行情况。

二、进程调度功能

记录系统中所有进程的有关情况，对进程控制块PCB的内容作相应的登记、修改，记录进程的状态特征。2.按照一定调度策略选择一个占有处理机的就绪进程。

在处理机空闲时根据一定的原则选择一个进程去运行，同时确定获得处理机的时间。3.实施处理机的分配和回收(进行进程上下文切换)。回收:正在运行的进程由于某种原因让出处理机，该进程的状态改为“阻塞”，插入到相应队列中，保留该进程的CPU现场。分配:根据调度原则选择进程去运行，把选中进程从就绪队列中移出,改状态为“运行”，把CPU控制权交给被选中的进程，将选中进程的有关PCB现场信息，分别送到相应的寄存器中。三、进程调度时机

1）正在执行的进程完成其任务而运行完毕。2）执行中的进程由于请求某个事件的发生，比如I/O请求，等待所需要的信号、信件的到来等而自己调用阻塞原语将自己阻塞起来，进入相应的等待队列。3）在分时系统中，当进程使用完规定的时间片。4）在采用可抢占调度方式的系统中，当具有更高优先级的进程要求使用处理机。四、进程调度方式

1.非抢先调度方式这种方式是当有重要或紧迫的进程进入就绪队列时，仍然让正在执行的进程继续执行，直到该进程完成任务终止运行或发生某种等待事件而进入阻塞状态时，才主动放弃占有的处理机，把处理机分配给重要或紧迫的就绪进程，以使其运行。2.可抢先调度方式这种方式则是重要或紧迫的进程一到，便把正在执行的进程占有的处理机强行剥夺下来，并转给这个优先级比它更高的重要或紧迫的就绪进程，使其运行。五、进程调度算法

采用最高优先级优先调度算法时，系统对每个进程确定一个优先数，进程的优先数用于表示进程的重要性及运行的优先性。调度时，系统把处理机分配给优先级最高的就绪进程。如果就绪进程具有相同的优先数，则再按先来先服务的次序分配处理机。

先来先服务调度算法是按照进程进入就绪队列的先后次序来选择进程分配处理机。（一）最高优先级优先调度算法系统确定优先数的方法：

1.静态优先数法：静态优先数是在创建进程时系统为其确定的，并且在进程的生命期内不再改变。确定静态优先数的原则：1）按进程类型。系统进程的优先级高于用户进程的优先级。2）按进程使用的资源。进程所使用的资源越多，进程的优先级越低；反之，则进程的优先级越高。3）按进程的估计运行时间。进程的估计运行时间越长，进程的优先级越低；反之，则进程的优先级越高。4）由用户指定。有些系统可以按收费标准不同，设置不同的优先级别，可以由用户指定。静态优先级法实现起来比较简单，但不能反映系统以及进程在运行过程中的动态变化情况，系统管理效果显然不佳。2.动态优先数法。动态优先数是指在系统创建进程时，根据系统资源的使用情况和进程的当前特点确定一个优先数，然后，在进程运行过程中再根据情况的变化动态调整进程的优先数。调整进程优先数的原则：

1）进程占有处理机的时间越长，则进程的优先级越低；进程的等待时间越长，则进程的优先级越高。2）根据进程所执行的程序的轻重缓急程度，调整进程的优先数。（二）时间片轮转调度算法

在分时系统中，为了满足系统对响应时间的要求，通常采用时间片轮转调度算法。1.简单轮转法(固定时间片轮转法）

在这种调度算法中，系统把所有就绪进程按到达的先后顺序形成一个就绪队列，就绪队列中的所有进程按时间片依次轮流获得处理机。

时间片的大小应根据进程要求系统给出应答的时间和进入系统的进程数来决定。可以表示为：其中，q是时间片的大小，T是系统的响应时间，N是进入系统的进程数。

简单轮转法的优点是简单、方便，但由于采用固定时间片的方式，调度欠灵活，服务质量不够理想。可以通过以下两个方面加以改进：1）将固定时间片方式改为可变时间片方式；2）将单就绪队列改为多就绪队列。2.可变时间片轮转法

时间片可变会给系统带来好处。如果要求系统快速应答，则时间片小一些，这样可使轮转一遍的总时间减少而可对进程尽快应答。如果进程数少，则时间片可以大一些，这样可减少进程调度的次数，提高系统效率。可变时间片轮转法中，可采取如下措施调整时间片：1)固定周期轮转法。在这种方法中，每一轮调度中所得的时间片q＇值的大小仅在这一轮调度中有效。系统的响应时间T固定，在每一轮调度中，根据当前就绪队列中的进程数n计算这一轮调度的时间片：q＇＝T/n，然后进行轮转，每个进程可获得这一轮的一个时间片q＇。在此期间所到达的进程暂不进入就绪队列，等此次轮转完毕再一并进入。系统根据此时就绪队列的进程数重新计算时间片q＇，然后开始下一轮循环。2)时间片的大小取决于优先级的高低，优先级高的进程分得的时间片较大，优先级低的进程分得的时间片较小。3)短作业的时间片较小，长作业的时间片较大。3.多级反馈轮转法（多重时间片轮转调度算法）

调度算法的实施过程如下：1.设置多个就绪队列，并为各个就绪队列赋予不同的优先级。第一个就绪队列的优先级最高，第二个就绪队列的优先级次之，其余各个就绪队列的优先级逐个降低。2.赋予各个就绪队列中进程的时间片也各不相同，优先级越高的就绪队列中的进程的时间片越小，反之，优先级越低的就绪队列中的进程的时间片越大。3.当一个新被创建的进程进入就绪队列后，首先将它加入第一个就绪队列的队尾，按先来先服务的原则排队等待调度。

当轮到该进程执行时，如能在该时间片内完成，则该进程将被撤消；如果在一个时间片结束时该进程尚未完成，调度程序则将该进程转入第二个就绪队列的队尾，按先来先服务的原则排队等待调度；如果它在第二个就绪队列中运行一个时间片后仍未完成，再以同样的方法将它转入第三个就绪队列的队尾，如此下去。4.仅当第一个就绪队列空闲时，调度程序才调度第二个就绪队列中的进程运行；仅当第1至第i–1个就绪队列均为空时，才会调度第i个就绪队列中的进程运行。如果处理机正在第i个就绪队列中为某进程服务时，又有新进程进入优先级较高的就绪队列时，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i个就绪队列的队尾，然后将处理机重新分配给新进程。§3.4死锁

一、死锁的概念死锁：各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成系统中一些进程处于无休止的等待状态，在无外力作用的情况下，这些进程永远也不能继续前进。我们称这种现象为死锁。例：系统中只有一台输入机R1和一台打印机R2可供进程P1和P2共享。进程P1进程P2┇┇请求资源R1请求资源R2┇┇

请求资源R2请求资源R1┇┇

释放资源R1释放资源R2┇┇释放资源R2释放资源R1

┇┇

R1R2

两个进程死锁的典型情况

进程在同步和通信的过程当中也会产生死锁。

例如，在生产者—消费者问题中，若把生产者进程中两个P操作的顺序颠倒如下图所示：生产者进程Pi

生产一个产品

产品送入缓冲区P(avail)

P(mutex)V(mutex)

V(full)

在这种情况下，当缓冲区都已放满了产品时，生产者仍可执行P(mutex)操作，于是该生产者掌握了对缓冲区的存取控制权，当它继续执行P(avail)操作时，由于没有空缓冲区，该生产者被阻塞，并在avail上等待。若此时有一个消费者到达，尽管缓冲区中有产品，消费者在执行P(full)操作时通过，但紧接着执行P(mutex)操作时，将因缓冲区已被阻塞的生产者所占有，而使消费者无法获得缓冲区的存取控制权而被阻塞。此时，出现了生产者和消费者之间僵死的局面，亦即发生了死锁。二、产生死锁的原因

产生的根本原因是系统能够提供的资源数少于需要该资源的进程数(系统资源不足)。1）对资源的分配策略（请求顺序）不当

；2）进程推进顺序非法。

死锁起因是并发进程的资源竞争。但资源竞争并不一定产生死锁。例如，在前一个例子中，进程P1和P2的不同进展情况将产生不同的结果。

P1和P2都占用R1

P1和P2都占用R2

P2的进展

P1的进展

占用R1占用R2释放R1释放R2请求R1请求R2请求R1

请求R2释放R1

释放R2

占用R1123占用R2下面用图示来说明进程P1和P2的三种可能的进展情况：产生死锁的必要条件1）互斥条件。进程对其所要求的资源进行排它性控制，即一次只有一个进程可以使用一个资源。2）不剥夺条件。进程所获得的资源在未被释放之前，不能被其它进程强行剥夺。3）占有且等待条件。进程每次申请它所需要的一部分资源，在进程等待分配其它资源的同时，可以占有已分配的资源。P1P2R1R2被占有

被占有

请求请求4）环路条件。在发生死锁时，必然存在一个进程资源的循环等待链，三、解决死锁问题的方法（一）死锁的防止(预防)1．破坏互斥条件为了破坏资源使用的互斥条件，就要允许多个进程同时访问共享资源。但是这种方法受到资源本身固有特性的限制，对某些资源是行不通的。例如打印机，就不允许多个进程在其运行期间交替打印数据，打印机只能互斥使用。而文件，可能允许多个进程对其进行读访问，但只允许互斥地写访问。因此，互斥条件难以破坏。

死锁的防止是通过设置某些严格的限制条件，以破坏产生死锁的必要条件来防止死锁的发生。

2．破坏不剥夺条件该策略规定，一个已保持了某些资源的进程，若新的资源要求不能立即得到满足，它必须释放已保持的所有资源。以后再需要时重新申请。这意味着，一个进程已占有的资源，在运行过程中可能暂时地释放，或说被剥夺。问题：1）这种防止死锁的策略实现起来比较复杂；2）一个资源在使用一段时间后被释放，可能会造成前阶段工作的失效，即使采取某些防范措施，也还会使前后两次运行的信息不连续。3）该策略还可能由于反复地申请和释放资源，使进程的执行无限推迟。这不仅延长了进程的周转时间，还增加了系统开销，又降低了系统吞吐量。3．破坏占有且等待条件----资源的静态分配策略系统要求所有进程一次性地申请其所需的全部资源。若系统有足够的资源分配给该进程时，便一次把所有其所需的资源分配给该进程。这样，该进程在整个运行期间，便不会再提出任何资源要求，从而使请求条件不成立。但在分配时只要有一种资源要求不能满足，则已有的其它资源也全部不分配给该进程，该进程只能等待。由于等待期间的进程不占有任何资源，因此，破坏了必要条件之3，防止了死锁发生。优点：简单、易于实现，且很安全。缺点：1）资源严重浪费。一个进程一次获得其所需的全部资源且独占，其中可能有些资源很少使用，甚至在整个运行期间都未使用，这就严重地恶化了系统资源利用率：2）进程延迟运行。仅当进程获得其所需全部资源后，方能开始运行，但可能有许多资源长期被其它进程占用，致使进程推迟运行，这往往要经过很长的时延。4.破坏环路条件----有序资源分配策略对系统中的全部资源按类型进行编号，编号的原则是较为紧缺的资源给以一个较大的序号。并且要求每一个进程在申请资源时应按照编号递增的顺序请求资源。也就是说，只要进程提出请求资源Ri（i为系统资源编号），则在以后的请求中，只能请求排在Ri后面的资源，不能在申请编号低于Ri的那些资源。

对资源申请作了这样的限制之后，在进程资源分配图中不可能再出现环路的情况。这种防止死锁的策略较之前两种策略，不论是资源利用率还是系统吞吐量，都有显著的改善。问题：1）为系统中各种资源类型分配的序号．必须相对稳定，这就限制了新设备类型的增加；2）尽管在为资源类型分配序号时，已考虑到大多数作