第四章处理机调度2

1、复习n一个作业从提交给计算机系统到执行结束退出系统，一般要经历几个状态？n处理机调度可分为哪四级？n在哪些系统中不存在作业调度？n作业与进程的关系如何？第四章 处理机调度作业调度进程调度作业调度n作业调度（宏观调度、高级调度）：n主要任务：按一定原则对外存中大量后备作业进行选择，给选出的作业分配资源，建立相应的进程，作业完毕时还要回收资源n主要完成：作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变作业调度功能1）记录系统中各作业的状况。系统为每个作业建立一个JCB记录这些信息。nJCB的内容：作业调度功能2）从后备作业中挑选出一部分作业投入运行n一般地，系统中处于后备状态的作业较

2、多，但处于执行状态的作业一般只有有限的几个。n作业调度程序根据选定的调度算法（FCFS,优先级,SJF等），从后备作业队列中挑选出若干作业投入运行作业调度功能3）为被选中的作业做好执行前的准备工作。n为选中的作业建立相应的进程，并为这些进程分配它们所需要的系统资源，如内存、外存、外设等作业调度功能4）作业执行结束时做善后处理工作。n输出作业管理信息，如执行时间等n回收该作业所占用的资源n撤消与该作业有关的全部进程和该作业的JCB作业从后备状态到执行状态后备作业队列空？出口是按调度算法从后备作业中选出一作业否调用存储、设备管理程序，审核资源要求资源要求能满足？是分配资源调用进程管理程序建立进程放

3、弃该作业进程调度否作业从执行状态到完成状态调用存储、设备管理回收分配给该作业的全部资源计算该作业的执行费用撤消该作业的所有进程及作业的JCB调度下一个作业作业调度的目标n1）对所有作业应该时公平合理n2）应该使设备有高的利用率（I/O设备的使用情况）n3）使系统有高的吞吐率（单位时间内完成的作业数）n4）有快的响应时间（从用户向计算机发出命令到计算机吧响应执行结果返回给用户所需的时间）作业调度的目标n注意：上述目标是相互冲突的，所以任一调度算法想要同时满足是不可能的。n如：要提高吞吐率，就应选择SJF，但这样对那些长作业不公平n如果考虑因素过多，调度算法会变得非常复杂，这将导致系统开销增加，资

4、源利用率下降，因此在实际中根据用户需求，采用兼顾某些目标的简单调度算法衡量作业调度算法的指标n对于批处理系统：平均周转时间、平均带权周转时间n（批处理系统主要用于计算，对作业的周转时间要求较高）衡量作业调度算法的指标n周转时间：将一个作业提交给计算机系统后到该作业的结果返回给用户所需的时间n1）Ti=TeiTsin其中Tei为作业完成时刻， Tsi为作业提交时刻n2）Ti=Twi+Trin其中Twi为作业从后备状态到执行状态的等待时间， Tri为作业的执行时间n平均周转时间：T=1/nTi衡量作业调度算法的指标n带权周转时间：作业周转时间与作业执行时间的比nWi=Ti/Tri=(Twi+Tri

5、)/Tri=1+Twi/Trin平均带权周转时间：nW=1/n Wi 衡量作业调度算法的指标n例：有5个作业ABCDE几乎同时到达一个计算中心，估计的运行时间分别为2，4，6，8，10分钟，根据以下情况分别计算作业的平均周转时间。n1）执行顺序为CDBEAn2）执行顺序为EDCBAn3）执行顺序为ABCDE衡量作业调度算法的指标n解：1）执行顺序为CDBEAnC周转时间Tc=6-0=6， 带权周转时间Wc=6/6=1nD周转时间Td=14-0=14,带权周转时间Wd=14/8=1.75nB周转时间Tb=18-0=18,带权周转时间Wb=18/4=4.5nE周转时间Te=28-0=28,带权周转

6、时间We=28/10=2.8nA周转时间Ta=30-0=30,带权周转时间Wa=30/2=15n平均周转时间T=1/5Ti=19.2n平均带权周转时间W=1/5Wi=5.0106141828 30CDBEAt衡量作业调度算法的指标n2）执行顺序为EDCBAnE周转时间Te=10-0=10,带权周转时间We=10/10=1nD周转时间Td=18-0=18,带权周转时间Wd=18/8=2.25nC周转时间Tc=24-0=24,带权周转时间Wc=24/6=4nB周转时间Tb=28-0=28,带权周转时间Wb=28/4=7nA周转时间Ta=30-0=30,带权周转时间Wa=30/2=15n平均周转时间

7、T=1/5 Ti=22n平均带权周转时间W=1/5Wi=5.85010241828 30CDBEAt衡量作业调度算法的指标n3）执行顺序为ABCDEnA周转时间为Ta=2-0=2, 带权周转时间Wa=2/2=1nB周转时间为Tb=6-0=6, 带权周转时间Wb=6/4=1.5nC周转时间为Tc=12-0=12,带权周转时间Wc=12/6=2nD周转时间为Td=20-0=20,带权周转时间Wd=20/8=2.5nE周转时间为Te=30-0=30,带权周转时间We=30/10=3n平均周转时间T=1/5 Ti=14n平均带权周转时间W=1/5Wi=2061220230CDBEAt处理机调度进程调度

8、进程调度n进程调度：（微观调度、低级调度）：n主要任务：按照某中策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程之后，系统进行进程上下文切换。进程调度的功能1）记录系统中所有进程的执行情况n进程管理模块将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。n进程调度模块通过PCB变化来掌握系统中所有进程的执行情况和状态特征，在适当的时机从就绪队列中选择一个进程占有处理机。进程调度的功能2）选择占有处理机的进程n按照一定的策略选择一个处于就绪状态的进程，使其执行n例如：如果要求系统有高的吞吐率，则选择SPF调度算法；如果要求系统对不同等级的进程分别处理，则选择优先级

9、调度算法进程调度的功能3）进行进程上下文切换n进程上下文：进程执行活动全过程的静态描述n一个进程的上下文包括进程的状态、有关变量和数据结构的值、硬件寄存器的值等n当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，来让另一个进程得以执行。进程调度的时机n进程调度的时机与引起进程调度的原因有关：n（1）CPU非剥夺方式n即使在就绪队列中有优先级高于当前执行进程优先级的进程存在，当前进程仍继续执行，直到它因调用原语操作或等待I/O而进入等待态，或者因时间片用完而回到就绪态n（2）CPU可剥夺方式n若在就绪队列中一旦有优先级高于当前执行进程优先级的进程存在时，立刻发生进程调度，转让处

10、理机CPU非剥夺方式n1）正在执行的进程执行完毕n2）执行中进程自己调用阻塞原语将自己阻塞起来，进入等待态n3）执行中进程调用了P原语，因资源不足而被阻塞（sem0）;或调用了V原语唤醒了等待资源的进程队列（sem=0）n4）执行中进程提出I/O请求后被阻塞n5）在分时系统中时间片用完，该进程从执行态回到就绪态n6）在执行完系统调用，系统程序返回用户进程CPU可剥夺方式n7）在CPU执行方式时可剥夺方式时，满足可剥夺条件即可发生进程调度n（可剥夺条件：若在就绪队列中一旦有优先级高于当前执行进程优先级的进程存在时，立刻发生进程调度，转让处理机）进程上下文切换n在发生进程调度时，系统要做进程上下文

11、切换。n进程上下文切换包括4个步骤：n1）决定是否做以及是否允许做上下文切换n2）保存当前执行进程的上下文n3）使用某种调度算法，选择一个处于就绪状态的进程n4）恢复或装配所选进程的上下文，将CPU控制权交给它进程上下文切换n1）决定是否做以及是否允许做上下文切换n对进程调度原因的检查分析，对当前执行进程的资格的检查，对CPU执行方式的检查等n例如：在CPU可剥夺方式中，可采用高优先级进程中断正在执行的低优先级进程；在CPU非剥夺方式中，可采用时间片轮转的方法进程上下文切换n2）保存当前执行进程的上下文n当前执行进程指的是调用上下文切换程序之前的执行进程n上下文切换程序为了不破坏这个“老”进程上下文，系统就必须保存当前执行进程的上下文进程上下文切换n3）使用某种调度算法，选择一个处于就绪状态的进程n先来先服务（FCFS）n轮转法（RR）n优先级n最短进程优先（SPF）进程上下文切换n4）恢复或装配所选进程的上下文，将CPU控制权交给它n恢复：进程已经被调度过，但没有执行完毕，由于某种原因以前进行过上下文切换，现在再切换回来n装配：进程没有被调度过进程调度性能评价n1）定性衡量方法：n调度的可靠性：