《OS调度与死锁》PPT课件

1、第 3 章 调度与死锁操作系统原理与Windows 2003实践教程1精选PPT第三章调度与死锁3.1 处理机调度3.2 调度算法3.3 死锁3.4 死锁的预防3.5 死锁的避免和银行家算法3.6 死锁的检测与解除 3.7 Windows2003处理器3.8 本章小结2精选PPT3.1 处理器调度3.1.1调度的层次3.1.2进程调度3.1.3调度队列模型3精选PPT调度的层次高级调度：也称作业调度中级调度：即交换调度低级调度：也称进程调度4精选PPTprocesserprocesserRAMmemory高级调度中级调度低级调度5精选PPT高级调度也称为作业调度或宏观调度 高级调度的时间尺度通

2、常是分钟、小时或天中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效6精选PPT处理机的三级调度7精选PPT作业调度与进程调度8精选PPT处理机调度与进程状态转换9精选PPT进程调度进程调度的功能记录系统中所有进程的状态、优先数和资源需求确定调度算法分配处理器给进程

3、 10精选PPT进程调度的时机：正在执行的进程执行完毕执行进程调用阻塞原语将自己阻塞起来变为阻塞状态执行进程调用P操作，因资源不足而被阻塞；或调用V操作激活了等待资源的进程队列。执行进程提出I/O请求，被阻塞分时系统中时间片用完执行系统调用完毕，由系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。11精选PPT调度队列模型具有一级调度的调度队列模型 12精选PPT两级调度简化队列图 13精选PPT具有高、低两级调度的调度队列模型 14精选PPT具有三级调度的调度队列模型 15精选PPT3.2 调度算法3.2.1算法的衡量3.2.2先来先服务调度算法3.2.3短者

4、优先调度算法3.2.4最短剩余时间优先调度算法3.2.5最高响应比优先调度算法3.2.6时间片轮转法3.2.7优先级调度算法3.2.8多级反馈队列调度算法16精选PPT确定调度策略时应考虑的主要因素：所用算法应保证实现系统的设计目标公平性原则均衡使用资源兼顾响应时间和资源利用率基于相对优先级，但避免无限延期系统开销不应大大17精选PPT算法的衡量常用的评价准则包括： CPU利用率 吞吐量 周转时间 就绪等待时间 响应时间18精选PPTCPU利用率： CPU利用率CPU有效工作时间CPU总运行时间CPU总运行时间CPU有效工作时间CPU空闲时间19精选PPT吞吐量： 单位时间内CPU完成作业的数

5、量20精选PPT周转时间： Tit ci t si其中，t si表示作业i的提交时间，即作业i到达系统的时间；t ci表示作业i的完成时刻平均周转时间：21精选PPT就绪等待时间 ： 作业在就绪队列中的等待时间22精选PPT响应时间： 从提交第一个请求到产生第一个响应所用的时间 23精选PPT先来先服务调度算法实现思想：“排队买票”，即按照作业到达系统或是进程进入就绪队列的先后次序作为选择 依据就绪队列（后备队列）按照进入的先后次序为序，选择时选取队列的队首进程（作业）24精选PPT【例3-1】假设一个系统有5个进程P1、P2、P3、P4、P5，已知它们的到达时间和运行时间，用FCFS算法进行

6、调度。 25精选PPT26精选PPT周转时间/服务时间27精选PPTFCFS的优点：简单、容易实现 有利于长进程（作业），不利于短进程（作业）有利于CPU型作业，不利于I/O型作业 FCFS的缺点：属于不可抢占策略，表面上对于所有的作业和进程都是公平的 ，但系统吞吐量不大，效率较低28精选PPT短者优先调度算法实现思想：从就绪队列中挑选所需的运行时间（估计时间）最短的进程（作业）运行 就绪队列（后备队列）按照进程（作业）的运行为序，选择时选取队列的队首进程（作业）即为最短者，新来的进程（作业）依据运行时间的长短插入到队列的合适位置。29精选PPT【例3-2】设系统中有5个进程中A，B，C，D，

7、E，它们到来的时间依次为0，1，2，3，4，运行时间依次为4，3，5，2，4，试用FCFC算法和短者优先调度算法调度。FCFS：进程的执行顺序依次为ABCDE SJF：进程的执行顺序依次为ADBEC。 30精选PPT31精选PPTSJF（SPF）的优点：简单、容易实现 有利于短进程（作业），不利于长进程（作业）有利于保障系统吞吐量 SJF（SPF）的缺点：对于长进程（作业）是不公平的32精选PPT最短剩余时间优先调度算法实现思想：让运行到进程完成时所需运行时间最短的进程优先得到处理，其中包括新进入系统的进程 。就绪队列（后备队列）按照进程（作业）的剩余运行时间的长短为序，选择时选取队列的队首进

8、程（作业）即为最短者，新入队的进程（作业）依据剩余运行时间的长短插入到队列的合适位置。33精选PPT优点：可以用于分时系统，保证及时响应用户要求 属于可抢占策略，使短进程一进入系统就能立即得到服务，从而降低作业的平均等待时间缺点：系统开销增加需要保存进程的运行情况记录，以比较其剩余时间大小抢占本身消耗处理器时间 34精选PPT最高响应比优先调度算法实现思想：综合FCFS和短者优先算法的特点 就绪队列（后备队列）按照进程（作业）到来的先后次序为序，选择时计算队列全部进程的响应比，选择最高响应比的进程（作业）运行。35精选PPT【例3-3】假设一个系统有4个进程P1、P2、P3、P4，已知它们的到

9、达时间和运行时间，试用最高响应比优先算法进行调度。 36精选PPT37精选PPT38精选PPTHRF的优点：短进程（作业）由于计算响应比的分 母大而可以得到大的响应比，优先执行，长进程（作业）的响应比会随着等待时间的加长越来越大，得到执行机会。39精选PPT时间片轮转法实现思想：从就绪队列中的每个运行指定的时间片，时间片到，无论是否运行完毕都执行下一个进程。就绪队列（后备队列）按照进程（作业）到来的先后为序，选择时选取队列的队首进程（作业）运行一个时间片。40精选PPT【例3-4】设系统中有四个进程P1，P2，P3，P4依次进入系统，但彼此相差时间很小，可以近似看作“同时”到达。四个进程分别需

10、要运行12，5，3和6个时间单位，时间片分别为1和4时系统运行的情形： 41精选PPT42精选PPT时间片的大小是关键过大：时间片轮转法退化成先来先服务算法过小：处理器在进程间的转接工作过于频繁，开销变大，而处理器真正用于运行用户程序的时间将会减少 43精选PPT优先级调度算法实现思想：按照进程（作业）的优先级大小来调度，使高优先级进程（作业）得到优先处理 就绪队列（后备队列）按照进程（作业）的优先级从高到低，选择时选取队列的队首进程（作业）即为优先级最高的，新进程据其优先级大小入就绪队列相应位置44精选PPT进程调度策略：非抢占优先级调度抢占优先级调度优先级的确定：静态优先级动态优先级45精

11、选PPT【例3-5】假设一个系统有5个进程P1、P2、P3、P4、P5，已知它们的到达时间、运行时间和优先数如表3-7所示，试用静态优先级调度算法进行调度。 46精选PPT47精选PPT48精选PPT多级反馈队列调度算法49精选PPT3.3 死锁3.3.1死锁的定义3.3.2产生死锁的必要条件3.3.3对死锁采取的对策50精选PPT交通死锁 51精选PPT死锁的定义死锁，是指两个或两个以上的进程，因竞争系统共享资源而产生的无止境地相互等待的状态，此时计算机系统所处的状态即处于死锁状态。陷入死锁状态的进程称之为死锁进程 52精选PPT例：现有两个进程PA和PB，各自按以下顺序使用PV操作并行运行

12、，其中S1和S2分别代表系统中一台打印机和一台扫描仪的信号量，初值均为1进程PA：P(S1)；P(S2)；V(S1)；V(S2)； 进程PB：P(S2)；P(S1)；V(S2)；V(S1)； 53精选PPT产生死锁的根本原因：资源有限进程推进的顺序不合理54精选PPT产生死锁的必要条件互斥条件：进程访问的临界资源是互斥的不可抢占条件：一个资源仅能被占有它的进程主动释放，不能被其他进程强行抢占。占有且申请：进程在申请新资源的同时，保持对已有资源的占有。环路等待条件：存在一个进程资源的环形链55精选PPT对死锁采取的对策置之不理驼鸟策略运行前预防死锁的预防。运行中避免死锁的避免。运行中解除死锁的检

13、测与恢复。 56精选PPT3.4 死锁的预防设法破坏产生死锁的四个必要条件之一，从而保证系统不发生死锁破坏互斥条件破坏不可抢占条件破坏占有且申请条件破坏环路等待条件此方法较容易实现，但由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。57精选PPT“资源一性分配策略”算法规定任一进程必须预先申请所需要的全部资源，而且当且仅当该进程的全部要求都能得到满足时，系统才一次性分配，然后启动该进程运行 。58精选PPT“资源有序分配策略”算法把资源事先分类编号，按序分配，使进程在申请、占用资源时不会形成环路。 59精选PPT3.5 死锁的避免和银行家算法3.5.1系统安全状态3.5.

14、2银行家算法3.5.3银行家算法的例子60精选PPT系统安全状态安全状态是指系统中的所有进程能按某种顺序（P1，P2，Pn）分配其所需的资源，直到的有进程都可以运行完毕。此进程序列（P1，P2，Pn）称为安全序列若存在这样一个安全序列，则系统是安全的；否则，如果在系统中无法找到这样一个安全序列，则称系统处于不安全状态。61精选PPT死锁与不安全状态的关系62精选PPT银行家算法基本思想：当一个新的进程进入系统时，其所需要每种资源的最大数目，不能超过系统中资源的总数。当用户申请资源时，系统判断此资源分配是否使系统仍处于安全状态，若是则分配，否则该进程等待，直到其他进程释放足够的资源。 63精选P

15、PT使用的数据结构：（系统中有n个进程，m类资源）Available：长度为m的向量Availablej为系统中资源类Rj的当前可用数（j=1,2,m)Max：nm阶矩阵Mi,j=K表示进程Pi需要Rj类资源最大数目为K。Allocation：nm阶矩阵Allocationi,j=K，表示进程Pi当前已分得Rj类资源数为K。Need：nm阶矩阵Needi,j=K，表示进程Pi还需要Rj类资源数目为K显然Needi,j=Maxi,j-Allocationi,j。64精选PPT银行家算法设Requesti是进程Pi提出的资源申请向量当进程Pi提出资源申请Requesti K时，按照银行家算法，系统

16、将执行下列步骤：1）若RequestiNeedi，转2），否则错误返回。2）若RequestiAvailable，转3），否则资源不足，进程Pi需要等待。65精选PPT3）假设系统满足Pi的请求为其分配资源，则：AvailableAvailable Requesti；AllocationiAllocationiRequesti；NeediNeediRequest i；4）执行安全性算法，若系统新状态是安全的，则分配完成；如果系统处于不安全状态，那么进程Pi等待Requesti，并且恢复到系统原来的状态。66精选PPT安全性算法 1） Work=Available； Finishi=False，

17、i=1,2,n 2）存在Pi满足：Finishi=False, NeediWork, 执行3)；否则执行4）。3）修改：Work=Work+Allocationi；Finishi=True；转向2）。4）若所有：Finishi=True，i=1，2，n，则该系统处于安全状态。否则处于不安全状态。67精选PPT银行家算法的优点：采用死锁动态策略，系统资源利用率提高了银行家算法的缺点：要求被分配每类资源数量、客户数固定不变，这在多道程序系统中是难以做到的。算法保证客户请求在有限的时间内得到满足，但无法满足实时客户的快速响应要求。寻找安全序列，增加了系统的开销。68精选PPT银行家算法的例子 【例3

18、-6】假设系统中有五个进程P0，P1，P2，P3，P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7,在T0时刻系统的资源分配情况如表：69精选PPTA，B，C=10，5，7T0时刻的资源分配表 资源情况进程MAXAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P443300243170精选PPT（1）T0时刻的安全性：利用安全性算法有：Work=Available（3，3，2）；Finishi=False，i=1，2，3，4，5。1）有Finish1=False

19、，Need1Work，即（1，2，2）（3，3，2），所以Work=Work+Allocation（3，3，2）+（2，0，0）（5，3，2）；Finish1=True。2）有Finish3=False，Need3Work，即（0，1，1）（5，3，2），所以Work=Work+Allocation（5，3，2）+（2，1，1）（7，4，3）；Finish3=True。3）有Finish4=False，Need4Work，即（4，3，1）（7，4，3），所以Work=Work+Allocation（7，4，3）+（0，0，2）（7，4，5）；Finish4=True。4）有Finish2=Fa

20、lse，Need2Work，即（6，0，0）（7，4，5），所以Work=Work+Allocation（7，4，5）+（3，0，2）（10，4，7）；Finish2=True。5）有Finish0=False，Need0Work，即（7，4，3）（10，4，7），所以Work=Work+Allocation（10，4，7）+（0，1，0）（10，5，7）；Finish0=True。 所以，有安全序列P1，P3，P4，P2，P0，使得对i=1，2，3，4，5，均有Finishi=True，则T0时刻该系统处于安全状态。 71精选PPT安全性算法的计算可简化为下表：T0时刻的安全序列WorkNe

21、edAllocationWork+AllocationFinishABCABCABCABCP1332122200532TrueP3532011211743TrueP4743431002745TrueP27456003021047TrueP010477430101057True72精选PPT（2）P1请求资源Request1（1，0，2） 对于P1的请求，按照银行家算法有：1）Request1（1，0，2）Need1（1，2，2）。2）Request1（1，0，2）Available（3，3，2）。3）假设满足P1的请求为其分配资源，则：AvailableAvailable Request1（3

22、，3，2）（1，0，2）（2，3，0）；AllocationiAllocationiRequesti（2，0，0）+（1，0，2）（3，0，2）；NeediNeediRequest i（1，2，2）（1，0，2）（0，2，0）；由此形成的系统资源分配情况表。73精选PPT P1申请资源时的资源分配表 MAXAllocationNeedAvailableABCABCABCABCP0753010743 230( 332)P1322302(2 00)020(122)P2902302600P3222211011P443300243174精选PPT执行安全性算法，检测新状态是否安全P1申请资源时的安全性

23、检查存在安全序列P1，P3，P4，P0，P2，因此，系统在将资源分配给P1后是安全的，故可以立即将P1所申请的资源分配给它。WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532TrueP3532011211743TrueP4743431002745TrueP0745743010755TrueP27556003021057True75精选PPT（3）P4请求资源Request4（3，3，0） 对于P4的请求，按照银行家算法有：1）Request4（3，3，0）Need4（4，3，1）。2）Request4（3，3，0）

24、Available（2，3，0），故让P4等待。 76精选PPT（4）P0请求资源Request0（0，2，0），按照银行家算法有：1）Request0（0，2，0）Need0（7，4，3）。2）Request0（0，2，0）Available（2，3，0）。3）假设满足P0的请求，则：AvailableAvailable Request0（2，3，0）（0，2，0）（2，1，0）；Allocation0Allocation0Request0（0，1，0）+（0，2，0）（0，3，0）；Need0Need0Request 0（7，4，3）（0，2，0）（7，2，3）；77精选PPT P0申请资

25、源时的资源分配表 MAXAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P443300243178精选PPT4）利用安全性算法，检测此时系统是否安全。从表中可以看出：可用资源Available（2，1，0）已经不能满足任何进程的需要，故系统进入不安全状态。因此，系统不能满足进程P0申请资源的请求，为其分配资源。 79精选PPT【练习3-1】1）该状态是否安全？2）如果进程P2提出Request2（1，2，2，2）后，系统能否将资源分配给它？为什么？AllocationNeedAv

26、ailableP0003200121622P110001750P213542356P303320652P40014065680精选PPT3.6 死锁的检测与解除3.6.1死锁的检测3.6.2死锁检测的时机3.6.3死锁的恢复81精选PPT死锁检测与恢复：是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。 82精选PPT死锁的检测检测死锁实质上是确定是否存在环路等待，一旦发现这种环路便认定死锁存在，并识别出该环路所涉及的有关进程，以供系统采用适当的措施来解除死锁。83精选PPT资源分配图 84精选PPT死锁定理：如果资源分配图中不存在环路，则系统不存在死锁；反之，如果资源分配图中存在环路，则系统中可能存在死锁，也可能不存在死锁。 85精选PPT图中存在着两个环路：P1R1P2R3P3R2P1P2R3P3R2P2分析