OS调与死锁.pptx

1第三章调度与死锁n3.1 处理机调度n3.2 调度算法n3.3 死锁n3.4 死锁的预防n3.5 死锁的避免和银行家算法n3.6 死锁的检测与解除 n3.7 Windows2003处理器n3.8 本章小结23.1 处理器调度3.1.1调度的层次3.1.2进程调度3.1.3调度队列模型3调度的层次n高级调度：也称作业调度n中级调度：即交换调度n低级调度：也称进程调度4processerprocesserRAMmemory高级调度中级调度低级调度5n高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天n中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问n低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效6处理机的三级调度7作业调度与进程调度8处理机调度与进程状态转换9进程调度n进程调度的功能记录系统中所有进程的状态、优先数和资源需求确定调度算法分配处理器给进程 10n进程调度的时机：正在执行的进程执行完毕执行进程调用阻塞原语将自己阻塞起来变为阻塞状态执行进程调用P操作，因资源不足而被阻塞；或调用V操作激活了等待资源的进程队列。执行进程提出I/O请求，被阻塞分时系统中时间片用完执行系统调用完毕，由系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。11调度队列模型具有一级调度的调度队列模型 12两级调度简化队列图 13具有高、低两级调度的调度队列模型 14具有三级调度的调度队列模型 153.2 调度算法3.2.1算法的衡量3.2.2先来先服务调度算法3.2.3短者优先调度算法3.2.4最短剩余时间优先调度算法3.2.5最高响应比优先调度算法3.2.6时间片轮转法3.2.7优先级调度算法3.2.8多级反馈队列调度算法16n确定调度策略时应考虑的主要因素：所用算法应保证实现系统的设计目标公平性原则均衡使用资源兼顾响应时间和资源利用率基于相对优先级，但避免无限延期系统开销不应大大17算法的衡量n常用的评价准则包括：CPU利用率 吞吐量 周转时间 就绪等待时间 响应时间18nCPU利用率：CPU利用率CPU有效工作时间CPU总运行时间CPU总运行时间CPU有效工作时间CPU空闲时间19n吞吐量：单位时间内CPU完成作业的数量20n周转时间：Tit ci t si其中，t si表示作业i的提交时间，即作业i到达系统的时间；t ci表示作业i的完成时刻n平均周转时间：21n就绪等待时间：作业在就绪队列中的等待时间22n响应时间：从提交第一个请求到产生第一个响应所用的时间 23先来先服务调度算法n实现思想：“排队买票”，即按照作业到达系统或是进程进入就绪队列的先后次序作为选择 依据就绪队列（后备队列）按照进入的先后次序为序，选择时选取队列的队首进程（作业）24【例3-1】假设一个系统有5个进程P1、P2、P3、P4、P5，已知它们的到达时间和运行时间，用FCFS算法进行调度。2526周转时间/服务时间27nFCFS的优点：简单、容易实现 有利于长进程（作业），不利于短进程（作业）有利于CPU型作业，不利于I/O型作业 n FCFS的缺点：属于不可抢占策略，表面上对于所有的作业和进程都是公平的，但系统吞吐量不大，效率较低28短者优先调度算法n实现思想：从就绪队列中挑选所需的运行时间（估计时间）最短的进程（作业）运行 n就绪队列（后备队列）按照进程（作业）的运行为序，选择时选取队列的队首进程（作业）即为最短者，新来的进程（作业）依据运行时间的长短插入到队列的合适位置。29【例3-2】设系统中有5个进程中A，B，C，D，E，它们到来的时间依次为0，1，2，3，4，运行时间依次为4，3，5，2，4，试用FCFC算法和短者优先调度算法调度。FCFS：进程的执行顺序依次为ABCDE SJF：进程的执行顺序依次为ADBEC。3031nSJF（SPF）的优点：简单、容易实现 有利于短进程（作业），不利于长进程（作业）有利于保障系统吞吐量 n SJF（SPF）的缺点：对于长进程（作业）是不公平的32最短剩余时间优先调度算法n实现思想：让运行到进程完成时所需运行时间最短的进程优先得到处理，其中包括新进入系统的进程。n就绪队列（后备队列）按照进程（作业）的剩余运行时间的长短为序，选择时选取队列的队首进程（作业）即为最短者，新入队的进程（作业）依据剩余运行时间的长短插入到队列的合适位置。33n优点：可以用于分时系统，保证及时响应用户要求 属于可抢占策略，使短进程一进入系统就能立即得到服务，从而降低作业的平均等待时间n缺点：系统开销增加n需要保存进程的运行情况记录，以比较其剩余时间大小n抢占本身消耗处理器时间 34最高响应比优先调度算法n实现思想：综合FCFS和短者优先算法的特点 n就绪队列（后备队列）按照进程（作业）到来的先后次序为序，选择时计算队列全部进程的响应比，选择最高响应比的进程（作业）运行。35【例3-3】假设一个系统有4个进程P1、P2、P3、P4，已知它们的到达时间和运行时间，试用最高响应比优先算法进行调度。363738nHRF的优点：短进程（作业）由于计算响应比的分 母大而可以得到大的响应比，优先执行，长进程（作业）的响应比会随着等待时间的加长越来越大，得到执行机会。39时间片轮转法n实现思想：从就绪队列中的每个运行指定的时间片，时间片到，无论是否运行完毕都执行下一个进程。n就绪队列（后备队列）按照进程（作业）到来的先后为序，选择时选取队列的队首进程（作业）运行一个时间片。40【例3-4】设系统中有四个进程P1，P2，P3，P4依次进入系统，但彼此相差时间很小，可以近似看作“同时”到达。四个进程分别需要运行12，5，3和6个时间单位，时间片分别为1和4时系统运行的情形：4142n时间片的大小是关键过大：时间片轮转法退化成先来先服务算法过小：处理器在进程间的转接工作过于频繁，开销变大，而处理器真正用于运行用户程序的时间将会减少 43优先级调度算法n实现思想：按照进程（作业）的优先级大小来调度，使高优先级进程（作业）得到优先处理 n就绪队列（后备队列）按照进程（作业）的优先级从高到低，选择时选取队列的队首进程（作业）即为优先级最高的，新进程据其优先级大小入就绪队列相应位置44n进程调度策略：非抢占优先级调度抢占优先级调度n优先级的确定：静态优先级动态优先级45【例3-5】假设一个系统有5个进程P1、P2、P3、P4、P5，已知它们的到达时间、运行时间和优先数如表3-7所示，试用静态优先级调度算法进行调度。464748多级反馈队列调度算法493.3 死锁3.3.1死锁的定义3.3.2产生死锁的必要条件3.3.3对死锁采取的对策50交通死锁 51死锁的定义n死锁，是指两个或两个以上的进程，因竞争系统共享资源而产生的无止境地相互等待的状态，此时计算机系统所处的状态即处于死锁状态。n陷入死锁状态的进程称之为死锁进程 52例：现有两个进程PA和PB，各自按以下顺序使用PV操作并行运行，其中S1和S2分别代表系统中一台打印机和一台扫描仪的信号量，初值均为1进程PA：P(S1)；P(S2)；V(S1)；V(S2)；进程PB：P(S2)；P(S1)；V(S2)；V(S1)；53n产生死锁的根本原因：资源有限进程推进的顺序不合理54产生死锁的必要条件n互斥条件：进程访问的临界资源是互斥的n不可抢占条件：一个资源仅能被占有它的进程主动释放，不能被其他进程强行抢占。n占有且申请：进程在申请新资源的同时，保持对已有资源的占有。n环路等待条件：存在一个进程资源的环形链55对死锁采取的对策n置之不理驼鸟策略n运行前预防死锁的预防。n运行中避免死锁的避免。n运行中解除死锁的检测与恢复。563.4 死锁的预防n设法破坏产生死锁的四个必要条件之一，从而保证系统不发生死锁破坏互斥条件破坏不可抢占条件破坏占有且申请条件破坏环路等待条件n此方法较容易实现，但由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。57n“资源一性分配策略”算法规定任一进程必须预先申请所需要的全部资源，而且当且仅当该进程的全部要求都能得到满足时，系统才一次性分配，然后启动该进程运行。58n“资源有序分配策略”算法把资源事先分类编号，按序分配，使进程在申请、占用资源时不会形成环路。593.5 死锁的避免和银行家算法3.5.1系统安全状态3.5.2银行家算法3.5.3银行家算法的例子60系统安全状态n安全状态是指系统中的所有进程能按某种顺序（P1，P2，Pn）分配其所需的资源，直到的有进程都可以运行完毕。n此进程序列（P1，P2，Pn）称为安全序列n若存在这样一个安全序列，则系统是安全的；否则，如果在系统中无法找到这样一个安全序列，则称系统处于不安全状态。61死锁与不安全状态的关系62银行家算法n基本思想：当一个新的进程进入系统时，其所需要每种资源的最大数目，不能超过系统中资源的总数。当用户申请资源时，系统判断此资源分配是否使系统仍处于安全状态，若是则分配，否则该进程等待，直到其他进程释放足够的资源。63n使用的数据结构：（系统中有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类资源数目为Kn显然Needi,j=Maxi,j-Allocationi,j。64银行家算法n设Requesti是进程Pi提出的资源申请向量n当进程Pi提出资源申请Requesti K时，按照银行家算法，系统将执行下列步骤：1）若RequestiNeedi，转2），否则错误返回。2）若RequestiAvailable，转3），否则资源不足，进程Pi需要等待。653）假设系统满足Pi的请求为其分配资源，则：AvailableAvailable Requesti；AllocationiAllocationiRequesti；NeediNeediRequest i；4）执行安全性算法，若系统新状态是安全的，则分配完成；如果系统处于不安全状态，那么进程Pi等待Requesti，并且恢复到系统原来的状态。66安全性算法 1）Work=Available；Finishi=False，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，则该系统处于安全状态。否则处于不安全状态。67n银行家算法的优点：采用死锁动态策略，系统资源利用率提高了n银行家算法的缺点：要求被分配每类资源数量、客户数固定不变，这在多道程序系统中是难以做到的。算法保证客户请求在有限的时间内得到满足，但无法满足实时客户的快速响应要求。寻找安全序列，增加了系统的开销。68银行家算法的例子【例3-6】假设系统中有五个进程P0，P1，P2，P3，P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7,在T0时刻系统的资源分配情况如表：69A，B，C=10，5，7T0时刻的资源分配表 资源情况进程MAXAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P443300243170（1）T0时刻的安全性：利用安全性算法有：Work=Available（3，3，2）；Finishi=False，i=1，2，3，4，5。1）有Finish1=False，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=False，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安全性算法的计算可简化为下表：T0时刻的安全序列WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1332122200532TrueP3532011211743TrueP4743431002745TrueP27456003021047TrueP010477430101057True72（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，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 P1申请资源时的资源分配表 MAXAllocationNeedAvailableABCABCABCABCP0753010743 230(332)P1322302(2 00)020(122)P2902302600P3222211011P443300243174执行安全性算法，检测新状态是否安全P1申请资源时的安全性检查存在安全序列P1，P3，P4，P0，P2，因此，系统在将资源分配给P1后是安全的，故可以立即将P1所申请的资源分配给它。WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532TrueP3532011211743TrueP4743431002745TrueP0745743010755TrueP27556003021057True75（3）P4请求资源Request4（3，3，0）对于P4的请求，按照银行家算法有：1）Request4（3，3，0）Need4（4，3，1）。2）Request4（3，3，0）Available（2，3，0），故让P4等待。76（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 P0申请资源时的资源分配表 MAXAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P4433002431784）利用安全性算法，检测此时系统是否安全。从表中可以看出：可用资源Available（2，1，0）已经不能满足任何进程的需要，故系统进入不安全状态。因此，系统不能满足进程P0申请资源的请求，为其分配资源。79【练习3-1】1）该状态是否安全？2）如果进程P2提出Request2（1，2，2，2）后，系统能否将资源分配给它？为什么？AllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656803.6 死锁的检测与解除3.6.1死锁的检测3.6.2死锁检测的时机3.6.3死锁的恢复81死锁检测与恢复：是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。82死锁的检测检测死锁实质上是确定是否存在环路等待，一旦发现这种环路便认定死锁存在，并识别出该环路所涉及的有关进程，以供系统采用适当的措施来解除死锁。83资源分配图 84n死锁定理：如果资源分配图中不存在环路，则系统不存在死锁；反之，如果资源分配图中存在环路，则系统中可能存在死锁，也可能不存在死锁。85图中存在着两个环路：P1R1P2R3P3R2P1P2R3P3R2P2分析后可知系统处于死锁状态，进程P1、P2和P3参与了死锁。86图中也有一个环路：P1R1P3R2P1但并不存在死锁状态，因为资源类R2中有一个资源被进程P4占有，如果进程P4释放这一资源，该资源可能会被分配给进程P3，从而断开环路。87可以用对资源分配图简化的方法，来检测当前系统状态是否为死锁状态。死锁定理：当前系统状态S为死锁状态的充分条件是，当且仅当S状态的资源分配图是不可完全简化的。88死锁检测的时机n进程等待时检测n定时检测n资源利用率降低时检测89死锁的恢复n重新启动n终止进程一次性撤销所有参与死锁的进程逐一参与死锁的进程n剥夺资源逐步剥夺一次剥夺n进程回退90课堂练习n1.操作系统中的作业管理是一种（）。A）宏观的高级管理B）宏观的低级管理C）系统开始加电D）初始化引导完成n2.定义：进程的周转时间进程完成时间进程到达时间。现有三个进程同时到达，每个进程的计算时间均为1小时，它们在一台处理器上按单道方式运行，则平均周转时间为（）。A）1小时B）2小时C）3小时D）6小时 n3.设系统中有两个进程共享3个同类资源，为使系统不会发生死锁，每个进程最多可以申请（）资源。A）0个B）1个C）2个D）3个91n4.在下列进程调度算法中，（）算法会对优先权进行调整。A）先来先服务B）短进程优先C）高响应比优先D）时间片轮转n5.进程P1使用资源情况：申请资源r1，申请资源r2，释放资源r1；进程P2使用资源情况：申请资源r2，申请资源r1，释放资源r2。系统并发执行进程P1、P2，则系统将（）。A）不会发生死锁B）可能发生死锁C）必定产生死锁D）不能给出答案n6.资源的按序分配策略可以破坏（）条件。A）互斥使用资源B）占有且等待资源C）非抢占资源D）环路等待 92n7.银行家算法是一种（）算法。A）死锁解除B）死锁避免C）死锁预防D）死锁检测n8.在下列解决死锁的方法中，属于死锁预防策略的是（）。A）银行家算法B）资源有序分配C）死锁检测D）资源分配图化简法