第三章处理机调度和死锁

第三章处理机调度与死锁主要内容处理机调度的层次调度队列模型和调度准则调度算法实时调度多处理机系统中的调度产生死锁的原因和必要条件死锁的预防死锁的检测与解除处理机调度（CPU调度）要解决的问题WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）3.1处理机调度的基本概念高级调度中级调度低级调度按OS的类型分：批处理调度分时调度和实时调度多处理机调度等按调度层次分：处理机调度的基本类型：3.1.1高级调度（长程调度、作业调度）HighLevelScheduling决定允许哪些作业竞争系统资源。也就是说，高级调度用于决定把外存上处于后备状态的作业按照一定的算法，选取出若干个作业，当内存空间满足其要求时，为它们分配存储空间，调入内存，创建该作业的进程，再分配它们所需的I/0设备及其它资源，再将新进程排在就绪队列上，新进程具有了获得处理机的资格。1、作业的基本概念2、作业调度外存后备状态作业调入内存，分配资源创建进程就绪队列在执行作业调度时，要做以下两步：接纳多少个作业接纳哪些作业取决于多道程序度取决于调度算法在分时系统和实时系统中有没有作业调度？3.1.2低级调度（LowLevelScheduling）也称进程调度（短程调度），它决定在就绪队列中哪一个进程将分配到处理机，并由分派程序把处理机实际分配给这个进程。最基本的调度三种操作系统都有1、低级调度功能：（1）保存处理器的现场信息。（2）按某种算法选取进程。（3）把处理器分配给进程。2、进程调度中的三个基本机制排队器：分派器(分派程序)：用来将CPU的控制交给由进程调度所选择的进程。其功能包括：（1）切换上下文（2）切换到用户模式（3）跳转到用户程序的合适位置以重新启动这个程序。上下文切换机制第一对上下文切换：保存当前进程的上下文，装入分派程序的上下文。第二对上下文切换：移出分派程序的上下文，装入新选进程的上下文。进程调度的时机进程调度的时机与引起进程调度的原因以及进程调度的方式有关。引起进程调度的原因（1）正在执行的进程执行完毕。（2）执行中的进程提出I/O请求后被阻塞。（3）执行某种原语操作，比如wait(s)，block原语，wakeup原语。（4）分时系统中，由于分配给该进程的时间片已经用完。（5）执行中进程自己调用阻塞原语将自己阻塞起来。（6）执行完系统程序后返回用户进程时，可看作系统进程执行完毕，从而可以调度选择一个新的用户进程执行。以上是在不可剥夺方式下的引起进程调度的原因，在CPU执行方式是可剥夺时，还有一个原因。（7）一个比正在运行进程的优先数更高的进程进入就绪队列，从而引起调度。在以上所列的几种原因之一发生的情况下，OS进行进程调度。在UNIXSystemⅤ中，在以下情况之一发生时，进行进程调度。（1）当前进程自己调用sleep，wait等进入睡眠状态。（2）当前进程执行系统调用结束后返回用户态时，该进程的优先级低于其它就绪状态进程或调度标志被置位。（3）当前进程完成中断和陷入处理后返回用户状态时，该进程的优先级低于其它就绪状态进程或调度标志被置位。（4）时间片用完，并且当前进程的优先级低于其它就绪进程。（5）当前进程调用exit自我终止时。进程调度可采用下述两种方式：非抢占方式抢占方式抢占原则：（1）时间片原则（2）优先权原则（3）短作业优先原则3.进程调度方式3.1.3中级调度(中程调度)（IntermediateLevelScheduling）目的：是为了提高内存的利用率和系统吞吐量。中级调度涉及进程在内外存间的交换。实现存储器管理中的对换功能中级调度新建态挂起就绪态挂起等待态高级调度低级调度运行态就绪态等待态终止态问题批处理系统作业要获得处理机，需要什么调度？分时操作系统，作业获得处理机，需要什么调度？3.2进程调度队列模型和调度准则3.2.1进程调度队列模型1、仅有进程调度的调度队列模型2、具有高级和低级调度的调度队列模型3、同时具有三级调度的调度队列模型进程完成cpu进程调度时间片完阻塞队列就绪队列事件出现交互用户等待事件仅有进程调度的调度队列模型具有高、低两级调度的调度队列模型processor进程调度作业调度超时就绪队列等待事件2事件2出现后备作业队列事件n出现事件1出现等待事件n等待事件1………完成中级调度processor进程调度作业调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度具有三级调度时的调度队列模型事件出现3.2.2选择调度方式和调度算法的若干准则1、面向用户的准则（1）周转时间短（2）响应时间快（3）截止时间的保证（4）优先权准则2、面向系统的准则（1）系统吞吐量高。（2）处理机利用率好。（3）各类资源的平衡利用。§3.3调度算法在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。3.3.1先来先服务和短作业优先调度算法1、先来先服务调度算法(FCFS)作业调度：每次调度是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。进程调度：每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投入运行，该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。既可用于进程调度，也可用于作业调度进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D3100进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B1100C21D3100进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B11001101100100/100=1C21D3100进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B11001101100100/100=1C21101102102-2=100100/1=100D3100进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B11001101100100/100=1C21101102102-2=100100/1=100D3100102202199199/100=1.99平均周转时间（1+100+100+199）/4=100平均带权周转时间（1+1+100+1.99）/4=25.9975进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B11001101100100/100=1C21101102102-2=100100/1=100D3100102202199199/100=1.99FCFS调度算法有利于CPU繁忙型的作业，FCFS调度算法不利于I/0繁忙型作业。为什么？FCFS在一定意义上是公平合理的。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。先来先服务不能保证良好的响应时间，在处理交互用户时很少用这种方法。FCFS适不适合分时系统？FCFS的特点FCFS属于非剥夺调度，不适用在合理的响应时间应得到保证的分时环境中。FCFS属于非剥夺调度，还是可剥夺调度？2.短作业（进程）优先调度算法（ShortestJobFirst）SJF短作业（进程）优先调度算法SJ(P)F，是指对短作业或进程优先调度的算法。它们可分别用于作业调度(SJF)和进程调度(SPF)。实例作业调度情况算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间实例作业调度情况算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间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完成时间周转时间带权周转时间采用SJF哪个作业第一个执行？实例作业调度情况算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间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完成时间4周转时间4带权周转时间1实例作业调度情况算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间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完成时间44+2=6周转时间46-3=3带权周转时间13÷2=1.5实例作业调度情况算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间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=94+2=6周转时间486-3=3带权周转时间18÷3=2.673÷2=1.5实例作业调度情况算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间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=94+2=69+4=13周转时间486-3=313-4=9带权周转时间18÷3=2.673÷2=1.59÷4=2.25实例作业调度情况算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间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.5SJF完成时间46+3=913+5=184+2=69+4=13周转时间4818-2=166-3=313-4=9带权周转时间18÷3=2.6716÷5=3.13÷2=1.59÷4=2.25实例作业调度情况算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间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.1FCFS:只考虑等待时间，而不考虑运行时间。SPJ、SJF：根据作业（进程）占用处理机时间长短而定，注重了作业运行时间。SJF调度算法能有效地降低作业的平均等待时间和提高系统的吞吐量。FCFS与SPJ(SJF)比较SJ(P)F调度算法的缺点：（1）该算法对长作业非常不利。（2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会得到及时处理；（3）由于作业（进程）的长短只是根据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。3.3.2优先权（级）调度算法该算法的核心是确定作业或进程的优先权。一、优先权调度算法的类型当用于进程