第3章_进程调度(免费阅读)课件

1、第3章 处理机调度与死锁 调度目的：处理机调度的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。3.1 处理机调度基本概念3.1.1 调度类型 1）低级（短期）调度：确定选择哪个就绪的进程占有CPU，所以也称为处理机调度，进程调度2）高级（长期、作业）调度：确定哪些作业从外存调入内存作业：（用户）利用计算机进行一次运行所需工作的集合（比如，编辑、编译，运行等）。要执行一个程序，用户必须先提交一个作业。通过批输入设备（卡片、纸带、磁带）批处理作业。通过终端启动的作业交互式作业。提交作业方式 ： 注： 用户进程在运行过程中，也可能会产生由系统管理的后台作业

2、，比如打印作业。这些作业在条件满足时，由系统调度执行。3）中级（中期）调度：为提高效率，加快进程运行，调节系统的负荷，有时需要在选择内存中阻塞或就绪的进程暂时放到外存（一般是硬盘），即所谓的挂起。这种内外存的数据交换称为对换。中级调度解决：在阻塞或就绪的进程中选择哪个（些）进程挂起在条件允许下，在外存挂起的进程集合中如何选进程激活并调回内存外存对换作业输入 spooling输入程序 spooling 作业调度就绪阻塞就绪运行完成阻塞后备作业输出4）三种调度之间的关系如图低级调度中级调度3.1.2 调度队列模型 一、仅有进程调度的调度队列模型 特点：单就绪、单阻塞队列就队列绪CPU进程调度进程完

3、成时间片完阻队列塞交互用户等待事件事件出现二、具有高级和低级的调度队列模型特点 ：1)具有进程调度、作业调度 2)根据阻塞原因设置了多个阻塞队列后队列备1阻队列塞作业调度就队列绪CPU进程调度进程完成时间片完等待事件1事件1出现2阻队列塞n阻队列塞等待事件2等待事件n事件2出现事件n出现三、同时具有三级调度的调度队列模型作业调度就队列绪CPU进程调度进程完成时间片完事件出现阻塞列、起队挂阻队列塞等待事件就绪、挂起队列事件出现挂起中级调度后队列备交互型作业批量作业挂起选择哪种模型应根据系统的规模及目标制定3.1.3 选择调度方式和调度算法的若干标准1、调度目标：1)公平确保每个进程获得合理的CP

4、U份额2)效率是百分之百地忙碌3)响应时间使交互用户的响应时间尽可能短4)周转时间使批处理用户等待输出的时间尽可能短5)吞吐量使每小时处理的作业数量多以上调度目标有矛盾之处，不可能满足所有情况，取决于系统设计目标2、有关术语及衡量标准周转时间T：批处理系统的一个重要指标。指作业从提交到完成（得到结果）所经历的时间。 包括：1）在外存后备队列中等待时间；2）CPU上执行时间；3）就绪队列和阻塞队列中等待时间；4）结果输出等待时间。周转时间常用以下参数衡量 （原则上越小越好）平均周转时间: 带权周转时间 ： 其中:Ti/Tsi为第i个作业的带权周转时间，Tsi系统为第i个作业提供的实际服务时间响应

5、时间：分时系统的一个重要指标。用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间。包括：1）从终端的键盘输入的一个请求信息传送到处理机的时间；2）处理机对请求的处理时间；3）处理结果送到终端显示器的时间。吞吐量：批处理系统的一个重要指标。单位时间内所完成的作业数。处理机利用率：大中型主机多用户系统的性能指标，因为系统价格昂贵，所以非常重视其CPU利用率。PC一般不考虑这个指标。各种设备的均衡利用：大中型主机多用户系统性能指标。如CPU繁忙的作业和I/O繁忙的作业搭配。对PC及实时系统该指标并不重要。 3. 调度准则面向用户准则周转时间短；响应时间快；截止时间保证；优先权准则面向系

6、统的准则系统吞吐量处理机利用率各类资源的平衡利用3.2 调度算法 一、调度的时机 调度的时机是与调度方式有关，一般在以下情况下会发生进程调度：（1）正在执行的进程正常结束或由于某种错误而终止运行；（2）执行中的进程提出I/O请求，在等待I/O完成前，进程阻塞，转进程调度；（3）在分时系统中，按照时间片轮转，分给进程的时间片用完时； （4）按照优先级调度，有更高优先级进程变为就绪时；（5）在进程通讯中，执行中的进程执行了某种原语操作，如P操作、阻塞原语和唤醒原语时，都可能引起进程调度。二、常用的调度方法1. 先来先服务（FCFS算法） 按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作

7、业或进程占用CPU，直到执行完或阻塞，才主动地出让CPU。特点：非常简单，易于实现；但对短作业而言，带权周转时间可能太大。按FCFS原则的进程调度进程名到达时间服务时间开始时间完成时间周转时间带权周转时间A03B26C44D65E823913182037912121.001.172.252.406.000391318特点：比FCFS改善了平均周转时间和平均带权周转时间，缩短作业的等待时间，提高了系统的吞吐量；对长作业非常不利，可能长时间得不到执行；难以准确估计作业（进程）的执行时间，从而影响调度性能2.短作业（进程）优先 对执行时间短的作业（进程）优先分派处理机。什么是短作业？以前没有执行过！

8、按什么标准：时间？程序长度？while(1);特点：比FCFS改善了平均周转时间和平均带权周转时间，缩短作业的等待时间，提高了系统的吞吐量；对长作业非常不利，可能长时间得不到执行；难以准确估计作业（进程）的执行时间，从而影响调度性能2.短作业（进程）优先 对执行时间短的作业（进程）优先分派处理机。什么是短作业？ 由用户自己利用作业控制语言说明程序预计执行时间。按非抢占式SJF原则的进程调度进程名到达时间服务时间开始时间完成时间周转时间带权周转时间A03B26C44D65E82031115939152011361114316/311/414/53/2按抢占式SJF原则的进程调度进程名到达时间服务

9、时间开始时间完成时间周转时间带权周转时间A03B26C44D65E823. 时间片轮转 主要用于低级调度，是一种最古老、最简单、最公平且使用最广泛的方法。 将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾。（进程可以由于阻塞或已运行结束，在未用完一个时间片时，主动放弃CPU）。 主要问题：如何确定时间片的长短cpu效率=时间片长度/(时间片长度+调度切换时间) 对一个系统，调度切换时间可近似看成定数。我们可以调整时间片长度改变cpu效率。短：比如调

10、度时间需50ms,时间片50ms。效率=50%。 用户的一次请求需要多个时间片才能处理完，切换次数增加。长：时间片到500ms，效率=99%。 若有10个进程，这十个用户若几乎同时按下键盘，从第1个响应到他再次轮到运行要等 9*0.5=4.5秒远远超出能容忍的时间。 等待时间一般不要超出1秒，因此应该有： (时间片长度+调度切换时间)*进程数=1000ms所以：时间片长度=1000/进程数-调度切换时间 1000/进程数 对一个分时系统，联机的用户数是变化的。随进程数变化调整时间片长度是合理的。但由于进程数的变化几乎是连续不断的，所以没有必要随着实时的变化，这样系统开销也大。折衷的办法是：进程

11、数在一个区间范围内用一个时间片，在另一个区间范围内，用另一个时间片。系统可以每间隔一段时间，检测当前进程数，确定有无必要调整时间片长度。按时间片轮转的进程调度（时间片长为1）进程名到达时间服务时间开始时间完成时间周转时间带权周转时间A03B26C44D65E824、优先权调度 前者简单，在实时性要求不高或时间片不很长时可考虑；后者适合于实时要求高的场合，但时刻要监视有否更高优先权的进程产生。1）优先权调度分为： 非抢占式：除系统一旦把处理机分配给就绪队列中优先权最高的进城后，该进程便一直执行下去，直至完成；或者因发生某件事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最高的进

12、程。 抢占方式：系统同样是吧处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要有另外一个优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的最高优先权进程。抢占方式在实际的操作系统设计中也会有细分：内核部分可抢占：用户态时可以随时被抢占CPU，但当进程在核心态时则大部分时间都不可以抢用CPU，而只在某些时刻（称为可抢占点，Preemption Point），可以抢用CPU。例： UNIX SVR 4。 内核完全不可抢占：用户态时可以随时被抢占CPU，但当进程在核心态时，则完全不可以被抢用CPU。例：UNIX（SVR 3和4.3BSD UNIX及其以前的版本

13、）、WINDOWS NT。这些OS通常在系统调用或中断处理时屏蔽大部分中断，系统调用返回或中断返回时再开放大部分中断。 完全可抢占或内核完全可抢占：无论处于用户态还是核心态，都可以随时被抢占CPU 。例：SUN公司的Solaris 、Windows 2000 / XP。实际上，Solaris和Windows 2000 / XP并不是100%完全可抢占，只是将内核中不可抢占的代码段尽量减少而已。任何OS都不可能是100%的完全可抢占的。2）优先权的类型静态优先级 创建进程时就确定，直到进程终止前都不改变。通常是一个整数。 进程类型（系统进程优先级较高） 依据 对资源的需求（对CPU和内存需求较少

14、的进程，优 先级较高） 用户要求（紧迫程度和付费多少）动态优先级 创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能（UNIX中采用）。动态优先级的改变原则： A） 在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级得到提高； B） 进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。5、高响应比优先调度响应比：R = (等待时间 + 要求执行时间) / 要求执行时间是FCFS（先来先服务）和SJF的折衷：作业等待时间相同，服务时间越短，优先权越高-SJF；要求服务时间相同，等待时间越长，优先

15、权越高-FCFS；长作业随着等待时间的增加，优先权增加。 6、多级队列调度 使用多个就绪队列，各队列的区别对待，达到综合的调度目标。 方法： 根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列（如前、后台进程，系统、用户进程等）。 每个作业归入一个队列。不同队列可有不同的优先级、时间片长度、调度策略等；在运行过程中还可改变进程所在队列。 7、多级反馈队列调度 时间片轮转和优先级的综合及发展。就绪队列1S1至CPU就绪队列2S2至CPU就绪队列3S3至CPU就绪队列nSn至CPU时间片：s1s2sn 多个就绪队列，赋予不同的优先级。队列1的优先级最高。每个队列执行时间片的长度也不同，

16、规定优先级越低则时间片越长。 新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若一个时间片未完，投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列。 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。8、公平分享调度策略 1986年Bach提出：按进程组（用户）分配CPU。以前的做法，按进程分配CPU： A用户：1个进程 B用户：6个进程 C用户：3个进程 ，10%的CPU分额 ，60%的CPU分额 ，30%的CPU分额现在 ：每个用户都按1/3的比例分配C

17、PU A用户的每个进程，1/3的CPU分额 B用户的每个进程，1/18的CPU分额 C用户的每个进程，1/9的CPU分额 定义：假如在一个进程集合中的每个进程都在等待只能由该集合中的其它一个进程才能引发的事件，这种状态被看成死锁。3.5 死锁的原因和必要条件1、产生死锁的原因 A）竞争不可剥夺资源 典型的打印机，磁带机等。3.5.1 死锁产生的原因p2rel(r1)p2rel(r2)p2req(r2)p2req(r1) p1req(r1) p1req(r2) p1rel (r1) p1rel (r2)死锁区p1p2tt当进程推进到死锁区，进程必死可通过增加资源来解决死锁，比如有两个r1和两个r

18、2资源就不会发生死锁,但现实中是不可取的。资源不够一定死锁吗？ p1req(r1) p1req(r2) p1rel (r1) p1rel (r2)p1p2p2rel(r1)p2rel(r2)p2req(r2)p2req(r1)进程没有推进到死锁区，不会发生死锁tt 定义：假如在一个进程集合中的每个进程都在等待只能由该集合中的其它一个进程才能引发的事件，这种状态被看成死锁。产生死锁的原因： A）竞争不可剥夺资源 典型的打印机，磁带机等。B)进程推进顺序不当3.5.2 产生死锁的必要条件 Coffman等人在1971年总结了4个死锁的必要条件只有4个条件都满足时，才会出现死锁。(1)互斥：一个资源

19、要么分配给一个进程，要么空闲； (2)请求和保持：进程可请求其余资源，但不主动释放已 经占用的资源（部分分配）(3)不剥夺：进程已经占用的资源，不会被强制剥夺(4)环路等待：系统一定有两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待相邻进程正占用的资源。3.5.3 死锁的解决方法一、鸵鸟策略（置之不理） 解决死锁的最简单方法就是鸵鸟算法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。 当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。 以UNIX系统为例，它潜在地存在死锁，但它并不花功夫

20、去检测和解除死锁，而是忽略不去理它。 如果死锁不花什么代价就能解决，那么什么问题也没有。但实际是代价很大，常会给进程带来很多不便的限制。所以，需要在方便性和正确性之间进行折衷，要充分考虑哪一个更重要，对象是谁，一般很难发现一般性的解决办法。二、预防死锁 预防死锁是一种简单直观的方法，通过预先设置某些限制条件，去破坏产生死锁的四个必要条件之一或几个条件，来预防死锁的发生。由于施加的条件过于严格，会导致系统资源利用率和系统吞吐量降低。三、避免死锁 避免死锁指的是在资源动态分配过程中，采用某种方法去防止系统进入不安全的状态，从而避免发生死锁。需要事先加以较弱的限制条件。目的地危险要想过去，必须保证在

21、通过的整个过程中肯定不会发生危险！保守主义者！目的地危险要想过去，那么小心一点，时刻探测下一步是不是会遇到危险！积极者！目的地只要想过去，就过去，不管有没有危险，碰到危险就完蛋！蛮干者！过？彻底完蛋！过！四、检测死锁 检测死锁的功能是利用系统所设置的检测机制，及时的检测出死锁的发生，并精确地确定与死锁有关的进程和资源。五、解除死锁 解除死锁：当检测到系统已经发生了死锁时，必须将进城从死锁状态中解脱出来。通常会牺牲部分系统利用率，甚至会牺牲部分进程。3.6 死锁的预防 预防：是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。 1）预先静态分配： 预先分配所需全部所

22、需资源，这样可保证不等待资源；降低了对资源的利用率（资源分配了可能不用）预先要知道所需资源；2）资源强制变为“可剥夺”的 在申请资源得不到时，占用资源也释放。实用中可行吗？3）破坏“环路等待”条件 有序资源使用法：每个独享资源都给一个唯一序号，使用只能按序号申请资源，三、利用银行家算法避免死锁1、银行家算法思想 避免死锁的算法是Dijkstra在1965年提出的，被称为银行家算法。 这个算法是用来模拟一个小城镇的银行家为一批顾客贷款的问题。 例： 有四个顾客：A，B，C，D，每个顾客提出的最大贷款数量分别为6、5、4、7。银行家知道不是所有顾客都马上需要其全部贷款（6+5+4+7=22）。因此

23、，他只保留10个单位数量(而不是全部22个单位)为这些顾客服务。银行家拥有量:10当前剩余量: 2当B请求1个时，当前剩余量:1 当前剩余量:1 现在银行家要破产了，剩余的资金贷给谁都不够，因此项目不能完成，银行家不能收回贷款。破产了错误发生在最后贷款给B的1个亿上当前剩余量: 2B请求：不贷款C请求2个亿：可以贷款 C完成项目后，还出4，这个4银行家下次可贷给B，也可贷给D其中的3，不管如何处理，B或D都能完成归还5或归还7；最后贷给A所需资金5。 最终，A、B、C、D都完成了项目，银行家得到了贷款利润。 存在的安全序列是：C、B、D、A或C、D、B、A赚钱了2. 银行家算法假定顾客分成若干

24、次借款；并在第一次借款时，能说明他的最大借款额。具体算法：顾客的借款操作依次顺序进行，直到全部操作完成；银行家对当前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）；安全时，贷款；否则，暂不贷款。 银行家算法可陈述如下： 当一个进程提出资源请求时，假定分配给它，并检查系统因此是否仍处于安全状态。如果安全，则满足它的请求。否则，推迟它的请求。 为了检查状态是否安全，银行家要检查他是否还有足够资源满足某一个顾客。如果能满足，这个顾客就能很快将贷款归还。重复这一检查过程。如果所有顾客的贷款都能满足，系统的这个状态是安全的。可实施实际的分配。如果不安全，则让其阻塞等待。 上述算

25、法可简单归纳如下：当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成序列，说明系统是安全的，可进行实际分配；否则，让申请者等待。3、算法描述： 设有n个客户，max i:第i个客户的资金总需求数 alloc i:第i个客户已得到的资金数，初值为0 needi:第i个客户还需要的资金数，初值为maxi (1=i=n)av:银行家目前可以贷出的资金,开始为总资本三者关系： maxi=alloci+needirequesti:第i个客户当前需要的资金数（必需有：requesti=needi)if(requesti=av & requesti=needi) av-=requesti;

26、 alloci+=requesti; needi-=requesti; if(check() )资金分配处理；else 拒绝分配，恢复av,needi,alloci的值;check:安全性检查:work=av;finishi=False; i=1,2,nwhile(1) flag=1; for(k=1;k=n;k+) if(finishk=False & needk avi i=1,2,.m代表第i个银行家当前能提供的资金原来的一维数组扩充为二维(n*m)，如：alloci(i=1,2,.n) :代表第i个客户已得到的资金- alloci,j (i=1,2, n；j=1,2,.m): 代表第i

27、个客户在第j个银行家处已得到的资金 其它类推。 5、存在的问题：要求事先说明最大资源要求，在现实中很困难系统中有5个进程（p0,P1,P2,P3,P4）和三类资源(A,B,C)，各种资源的数量分别为10，5，7，在T0时刻资源分配的情况如下表。Max(最多)A B CALLOC(已分配)A B CNEED(还需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 33 3 2P13 2 2P2P3p42 0 01 2 29 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 1T0时刻是否安全？找到一个能够把所有进程执行完成的序列即可说明其安全性

28、。Max(最多)A B CALLOC(已分配)A B CNEED(还需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 33 3 2P13 2 2P2P3p42 0 01 2 29 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 1现在P1进程发出请求Request（1，0，2）Max(最多)A B CALLOC(已分配)A B CNEED(还需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 33 3 2P13 2 2P2P3p42 0 01 2 29 0 23 0 26 0 00 1 12 1 12 2 24 3

29、30 0 24 3 12 3 03 0 20 2 0如果P1请求得到满足，那么系统的安全性怎么样？再次发生进程请求资源：P4进程发出请求Request（3，3，0）Max(最多)A B CALLOC(已分配)A B CNEED(还需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 3P13 2 2P2P3p49 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 12 3 03 0 20 2 0（3，3，0）大于(2 ,3, 0)所以P4必须等待再次发生进程请求资源：P0进程发出请求Request（0，2，0）Max(最多)A B CALLO

30、C(已分配)A B CNEED(还需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 3P13 2 2P2P3p49 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 12 3 03 0 20 2 00 3 07 2 32 1 0剩余的资源(2,1,0)不能使得任何一个进程得到全部满足，导致找不到任何安全序列，所以此次分配是不安全的！4.8 死锁的检测和解除一、死锁的检测 1、死锁模型 Holt1972年指出，用有向图可以建立死锁四个必要条件模型。图中用圆形结点表示进程，方形结点代表资源。从资源结点到进程结点的弧表示该资源已分配给该进程，从

31、进程到资源结点的弧表示进程请求资源。p1p2删除出度为0的进程结点的所有弧（包括出度与入度）。 （含义是：该结点对应进程不处于阻塞态），该点变为孤立点。重复上述过程，若最后所有进程结点是孤立点，则称该资源图是完全可简化的，否则是不可完全简化的。不可完全简化的资源分配图存在死锁，其中的有边进程为死锁进程。2、资源分配图的化简（类似于数据结构的拓扑排序）3、死锁定理 状态S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。本质是数据结构的拓扑排序4、死锁检测 1）数据结构：类似于银行家算法中所使用的 （A）av 代表所有不同类资源的当前可用资源数（一维数组） （B）alloci i = 1,2,. (n为进程数）， alloci 代表第i个进程的目前已得到的不同种类资源的资源