操作系统第三章-处理机调度及死锁课件

第三章处理机调度与死锁.第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除.3.1处理机调度的层次处理机调度如何分配处理机资源处理机调度的层次高级调度(HighLevelScheduling)中级调度(Intermediate-LevelScheduling)低级调度(LowLevelScheduling).3.1处理机调度的层次高级调度(HighLevelScheduling)也称为作业调度或长程调度根据某种算法，把外存上处于后备队列中的作业调入内存仅用于批处理系统作业程序数据作业说明书（包含作业步）.3.1处理机调度的层次低级调度(LowLevelScheduling)也称为进程调度或短程调度用于决定就绪队列中哪个进程应获得处理机低级调度的功能保存CPU现场按某种算法选取进程把CPU分派给进程进程调度的方式非抢占方式(nonpreemptivemode)抢占方式(preemptivemode).3.1处理机调度的层次非抢占式调度(nonpreemptivemode)进程获得CPU之后，可以一直运行下去，直至进程完成或因等待某些事件而阻塞引起调度的原因进程执行完毕等待某些事件而阻塞通信或同步过程中执行了某些原语适用于批处理系统，不适用于实时系统.3.1处理机调度的层次抢占式调度(preemptivemode)允许调度程序根据某种原则暂停正在执行的进程，将CPU分配给另一个进程原则：优先权原则短作业优先原则时间片原则.3.1处理机调度的层次中级调度(Intermediate-LevelScheduling)也称为中程调度用于决定将哪些进程调出外存或调入内存即如何选择挂起和激活的进程.3.1处理机调度的层次调度的层次事件发生运行就绪时间片到调度阻塞完成终止静止阻塞静止就绪内存空间挂起激活事件发生收容接纳挂起激活等待事件进程调度中级调度作业调度中级调度.3.2调度队列模型和调度准则面向用户的调度准则周转时间短周转时间：从作业被提交系统开始，到作业完成为止的这段时间用于评价批处理系统性能平均周转时间平均带权周转时间.3.2调度队列模型和调度准则面向用户的调度准则响应时间快响应时间：从用户通过键盘提交一个请求开始，直到系统首次产生响应时间为止用于评价分时系统性能截止时间的保证截止时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间用于评价实时系统性能优先权高的任务优先处理用于评价批处理、分时、实时等系统.3.2调度队列模型和调度准则面向系统的调度准则系统吞吐量高处理机利用率好各类资源的平衡利用.3.3调度算法先来先服务调度算法(FCFS)FirstComeFirstServe作业调度从后备作业队列中选择最先进入的一个或几个作业，调入内存，创建进程，放入就绪队列进程调度就绪队列中选择一个最先进入就绪队列的进程，将CPU分配于它.3.3调度算法先来先服务调度算法(FCFS)有利于长作业（进程），不利于短作业(进程)作业到达时间Tin服务时间Tr开始时间TS结束时间Tc周转时间T带权周转时间WA01B1100C21D31000110110211011022021100100199111001.99.3.3调度算法短作业(进程)优先调度算法(SJF/SPF)ShortestJobFirst/ShortestProcessFirst作业调度从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行进程调度从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它.短作业(进程)优先调度算法(SJF/SPF)能有效降低作业（进程）的平均等待时间3.3调度算法调度算法进程名ABE平均到达时间01234服务时间43524FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间441441762982.671210218163.114115.5631.518143.51392.2592.882.1DC.3.3调度算法短作业(进程)优先调度算法(SJF/SPF)对长作业（进程）不利没有考虑作业（进程）的紧迫程度需要事先知道或至少需要估计每个作业（进程）所需的处理时间.3.3调度算法高优先权优先调度算法（HPF）HighestPriorityFirst按作业或进程的优先级顺序进行调度，优先调度优先级高的作业或进程非抢占式优先权算法用于批处理系统抢占式优先权算法用于实时系统.3.3调度算法高优先权优先调度算法（HPF）如何确定进程或作业的优先级静态优先权进程类型进程对资源的需求用户要求动态优先权就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高.3.3调度算法高响应比优先调度算法（HRF）HighestResponseratioFirst响应比优先调度响应比高的进程FCFS强调等待时间，SJF强调要求服务时间，HRF是两者的折中.3.3调度算法时间片轮转法（RR）RoundRobin将CPU的处理时间分成固定大小的时间片用于分时系统.时间片轮转法（RR）3.3调度算法调度算法进程名ABCDE平均到达时间01234服务时间43524RR(q=1)完成时间周转时间带权周转时间12123109318163.2118417133.2511.63.29AAAABCBBCCCCDDEEEE调度序列：311271042516141891161381517就绪队列：AAAABCBBCCCCDDEEEE.3.3调度算法时间片轮转法（RR）时间片的确定R是系统对响应时间的要求Nmax是就绪队列中所允许的最大进程数.3.3调度算法多级反馈队列调度算法（MFQ）MultilevelFeedbackQueue多个就绪队列进程时间片结束时尚未完成则到下一就绪队列排队就绪队列1（8ms）就绪队列2（16ms）就绪队列3（32ms）就绪队列n（FCFS）处理机┇.3.4实时调度实现实时调度的基本条件系统必须提供必要的信息就绪时间开始截止时间和完成截止时间处理时间资源要求优先级.3.4实时调度实现实时调度的基本条件系统处理能力的要求单处理机系统多处理机系统Ci表示处理时间Pi

表示周期时间.3.4实时调度实现实时调度的基本条件采用抢占式调度机制具有快速切换机制.3.4实时调度实时调度算法最早截止时间优先（EDF）EarliestDeadlineFirst最低松弛度优先（LLF）LeastLaxityFirst.3.4实时调度最早截止时间优先（EDF）开始截止时间越早，优先级越高任务1任务执行→任务到达→任务1t任务3任务4任务2任务2任务3任务4任务1任务3

任务4

任务2

开始截止时间：.3.4实时调度最低松弛度优先（LLF）根据任务紧急(或松弛)的程度，来确定任务的优先级松弛度=必须完成的时间点-本身所需运行时间-当前时间.3.4实时调度最低松弛度优先（LLF）假如一个实时系统中有两个周期性实时任务，A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间25ms。0102030405060708090100t●●A1A2A3A4A5B1B2.3.4实时调度最低松弛度优先（LLF）A1(10)B1(20)0102030405060708090100tA2(10)A3(10)A4(10)B1(5)B2(15)B2(10)●●0102030405060708090100t●●A1A2A3A4A5B1B2.死锁(Deadlock)指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进wait(mutexN);wait(mutexM);M=10;N=M;print(N);signal(mutexM);signal(mutexN);ProcessAwait(mutexM);wait(mutexN);N=0;M=0;print(N);signal(mutexM);signal(mutexN);ProcessB3.5产生死锁的原因和必要条件.3.5产生死锁的原因和必要条件死锁产生的原因竞争非剥夺性资源.wait(mutexN);wait(mutexM);M=10;N=M;print(N);signal(mutexM);signal(mutexN);ProcessAwait(mutexM);wait(mutexN);N=0;M=0;print(N);signal(mutexM);signal(mutexN);ProcessB3.5产生死锁的原因和必要条件死锁产生的原因进程推进顺序不当.3.5产生死锁的原因和必要条件产生死锁的必要条件互斥条件请求和保持条件不剥夺条件环路等待条件.3.5产生死锁的原因和必要条件处理死锁的基本方法预防死锁施加限制条件破坏四个必要条件中的一个或几个避免死锁根据资源的使用情况提前做出预测，避免死锁发生检测死锁解除死锁.3.6预防死锁的方法摒弃“请求和保持”条件在进程运行之前，为其分配所需的全部资源缺点：资源浪费严重进程等待时间长互斥条件请求和保持条件不剥夺条件环路等待条件四个必要条件互斥条件请求和保持条件不剥夺条件环路等待条件四个必要条件互斥条件请求和保持条件不剥夺条件环路等待条件四个必要条件.3.6预防死锁的方法摒弃“不剥夺”条件当进程提出新的资源请求而得不到满足时，必须释放它所占用的资源某些资源（如打印机）不适用互斥条件请求和保持条件不剥夺条件环路等待条件四个必要条件.3.6预防死锁的方法摒弃“环路等待”条件把系统中所有资源编号，进程在申请资源时必须按资源编号的递增次序进行例如：资源编号－1，2，3，…，10P1：申请1申请3申请9…P2：申请1申请2申请5P3……P10互斥条件请求和保持条件不剥夺条件环路等待条件四个必要条件申请9.3.6避免死锁——银行家算法思想系统运行过程中，允许进程动态地申请资源但系统在进行资源分配之前，应先计算此次资源分配的安全性（是否会产生死锁）若此次分配是安全的（不会产生死锁），则将资源分配给进程；否则，令进程等待.3.6避免死锁——银行家算法安全状态如果系统能按某种顺序（如P4，P1，…,Pn）为每个进程分配其所需的资源，直至每个进程都能顺利地完成，称系统处于安全状态。否则处于不安全状态安全序列能安全分配的顺序称为安全序列安全状态一定没有死锁发生.3.6避免死锁——银行家算法安全状态举例有三个进程p1,p2,p3，有12台磁带机。需求及已分配如下：经分析，此刻系统是安全的。因为存在一个安全序列p2、p1、p3进程最大需求已分配可用P1P2P310495232510①②③3.3.6避免死锁——银行家算法不安全状态举例P3要求1台磁带机经分析，此刻系统是不安全的。因为不存在安全序列进程最大需求已分配可用P1P2P31049523232.3.6避免死锁——银行家算法银行家算法中的数据结构可利用资源向量Available含有m个元素的数组每个元素代表一类当前系统可利用资源的数目如：Available=（5，2，3）R1R2R3523.3.6避免死锁——银行家算法银行家算法中的数据结构最大需求矩阵Maxn*m矩阵表示n个进程的每一个对m类资源的最大需求R1R2R3P1562P2331P3425P4332.3.6避免死锁——银行家算法银行家算法中的数据结构已分配矩阵Allocationn*m矩阵表示每个进程已分配的资源数R1R2R3P1212P2121P3222P4132.3.6避免死锁——银行家算法银行家算法中的数据结构需求矩阵Needn*m矩阵表示每个进程还需要各类资源数Need=Max-AllocationR1R2R3P1352P2211P3223P4232.3.6避免死锁——银行家算法银行家算法进程pi提出资源申请Request=(a,b,c)if(Request<=Need[i]){if(Request<=Available){Available=Available–Request;Allocation[i]=Allocation[i]+Request[i];Need[i]=Need[i]–Request;if(SafetyTest)

进行分配；else

恢复试分配前状态；}else出错：无足够资源分配}else出错：申请的资源大于需求值试分配.3.6避免死锁——银行家算法安全性算法中的数据结构工作向量Work表示系统可用的各类资源数目初始时Work=Available布尔向量Finish记录系统是否有足够资源分配给各进程也可以记录某进程是否已进入安全序列.3.6避免死锁——银行家算法安全性算法(SafetyTest)Work=Available;所有Finish[i]=false;while(还有未放入安全序列的进程){if(找到满足Finish[i]==false&&Need[i]≤Work的进程i){

Work=Work+Allocation[i];Finish[i]=true;}if(遍历一遍，找不到满足条件的进程)break;}if(所有Finish[i]==true)

返回“安全”；else

返回“不安全”；.3.6避免死锁——银行家算法银行家算法举例设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图：

资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010P1322200P2902302P3222211P4433002011122743600431332532000743000745000①⑤④②③.3.6避免死锁——银行家算法银行家算法举例设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图：

资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010P1322200P2902302P3222211P4433002T0时刻可以找到一个安全序列{p1,p3,p4,p0,p2},系统是安全的011122743600431332①⑤④②③.3.6避免死锁——银行家算法银行家算法举例P1发出请求Request(1,0,2)Request<=Need[i]&&Request<=Available

资源情况进程MaxABCAllocationABCNeedABCAvail