OS第6章

1(一)处理机的多级调度(二)作业调度(三)进程调度第六章处理机调度2(一)处理机的多级调度一.处理机调度的功能确定数据结构制订调度策略(调度原则)给出调度算法具体的实施处理机分派不同类型的操作系统往往采用不同的处理机分配方法。3二.批处理系统中的处理机调度处理机调度分为两级：作业调度和进程调度。1.作业调度作业调度又称为宏观调度。任务——对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行。2.进程调度进程调度又称为微观调度。任务——对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。4三.多任务操作系统中的处理机调度在分时系统或支持多任务并发执行个人计算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。进程调度的任务是：当处理机空闲时，以某种策略选择一个就绪进程去运行，并分配处理机的时间。5四.多线程操作系统中的处理机调度在支持多线程运行的系统中，一个进程可以创建一个线程，也可以创建多个线程。系统为进程分配它所需要的资源，而处理机的分配单位则为线程。系统提供线程调度程序，其功能是当处理机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间。6(二)作业调度一.作业的状态作业在整个活动期间一共有四种状态，提交状态：用户将自己的程序和数据提交给系统，等待后备状态：作业已存放在磁盘上，等待调度。执行状态：作业进入主存开始运行。完成状态：作业计算完成开始，退出系统。7运行就绪完成等待后备提交作业调度作业调度作业录入执行8二.作业调度的功能1.确定数据结构建立作业控制块jcb(jobcontrolblock)。作业控制块记录了每个作业类型、状态、资源请求及分配情况。2.确定调度策略与调度算法3.分配资源为选中的作业分配所需要的系统资源。4.善后处理收回该作业所占用的全部资源，撤消作业控制块以及与该作业有关的全部进程。9三.作业控制块作业控制块jcb存在于系统的整个过程中，jcb是一个作业存在的标志。jcb的主要内容如下：作业名资源要求资源使用情况估计执行时间进入系统时间最迟完成时间开始执行时间要求的主存量已执行时间要求外设的类型及台数主存地址要求文件量和输出量外设台号类型优先级控制方式状态作业类型10四.作业调度算法性能的衡量采用平均周转时间和平均带权周转时间来衡量作业调度算法性能的好坏。1.周转时间一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间。(1)定义ti=tci-tsiti—作业i的周转时间tsi—作业i的提交时间，tci—作业i的完成时间。(2)意义说明作业I在系统中停留时间的长短。(3)平均周转时间t=niti1n1112.带权周转时间(1)定义一个作业的周转时间与其运行时间的比值。wi=(2)意义说明作业i在系统中相对等待时间。(3)平均带权周转时间t=tritiniwi1n112五.作业调度算法1.先来先服务调度算法(FCFS)(1)策略：按作业来到的先后次序进行调度。(2)特点：简单，易实现。(3)讨论在先来先服调度算法下的周转时间与带权周转时间作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.0028.500.5039.000.1049.500.208.0010.002.00110.0010.502.00410.5010.601.601610.6010.801.306.5平均周转时间t=平均带权周转时间w=1.7256.87513五.作业调度算法2.短作业优先调度算法(1)策略：按作业按作业请求运行的时间长短进行调度。(2)特点：易实现，系统吞吐量高；只照顾短作业，而没有考虑长作业的利益易实现。(3)讨论短作业优先调度算法下的周转时间与带权周转时间作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.0028.500.5039.000.1049.500.20平均周转时间t=平均带权周转时间w=1.555.158.0010.002.00110.3010.802.304.610.0010.101.101110.1010.300.80414(三)进程调度一.调度/分派结构1.调度在众多处于就绪状态的进程中，按一定的原则选择一个进程。2.分派当处理机空闲时，是移出就绪队列中第一个进程，并赋予它使用处理机的权利。153.调度∕分派结构图ready_qschedulersuspwakeupreceiveLpcb6Lpcb4pcb3pcb2pcb1dispatcherCPU16二.进程调度的功能1.记录进程的有关情况和状态特征2.决定调度策略优先调度原则——进程就绪队列按进程优先级高低排序先来先服务原则——进程就绪队列按进程来到的先后次序排序3.实施处理机的分配和回收17三.进程调度方式1.什么是调度方式当一进程正在处理机上执行时，若有某个更为“重要而紧迫”的进程需要进行运行，系统如何分配处理机。2.非剥夺方式一种是让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把处理机分配给“重要而紧迫”的进程。3.剥夺方式当“重要而紧迫”的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。18四.进程调度算法1.进程优先数调度算法(1)什么是进程优先数调度算法预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权(优先数和一定的优先级相对应)的就绪进程。(2)优先数的分类及确定静态优先数——*在进程被创建时确定，且一经确定后在整个进程运行期间不再改变。19*静态优先数的确定优先数基于进程的类型动态优先数——*进程优先数在进程运行期间可以改变。*动态优先数的确定——进程使用CPU超过一定数值时，降低优先数；进程进行I/O操作后，增加优先数进程等待时间超过一定数值时，提高优先数202.循环轮转调度算法(1)什么是循环轮转调度算法当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。该队列排序的原则是什么？pcb1pcb2pcbnCPU完成21(2)简单循环轮转调度就绪队列中的所有进程以等速度向前进展q=t/nt为响应时间，n为进入系统的进程数目。q值如何确定?(3)循环轮转调度算法的发展可变时间片轮转调度、多重时间片循环调度22五.调度用的进程调度变迁图运行500ms100ms因I∕O而等待高优先就绪低优先就绪进程调度进程调度时间片到请求I/OI/O完成231.队列结构I/O等待队列——一个进程如果请求I/O，进入I/O等待队列低优先就绪队列——一个进程如果在运行中超过了它的时间量，进入低优先就绪队列高优先就绪队列——当进程从等待状态变为就绪状态时，进入高优先就绪队列2.进程调度算法优先调度与时间片调度相结合的调度策略24(1)当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms(2)当CPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms3.调度效果优先照顾了I∕O量大的进程；适当照顾了计算量大的进程。25第六章小结一.处理机的两级调度二.作业调度1.作业的四种状态2.作业控制块3.周转时间、带权周转时间：定义物理意义4.常用的作业调度算法先来先服务短作业优先对一批作业，若采用两中不同的调度算法，能分析、计算调度性能的好坏。26三.进程调度1.调度方式非剥夺方式剥夺方式2.常用的进程调度算法优先数调度循环轮转调度3.调度用的进程状态变迁图通过调度用的进程状态变迁图，能分析系统采用的调度策略，调度性能的好坏。能分析因果变迁及条件。