计算机操作系统教程(第三版)张尧学 第8讲-处理机调度

第四章处理机调度4.1分级调度4.2

作业调度4.3

进程调度4.4

调度算法14.3进程调度进程调度的功能进程调度的时机进程调度性能评价234.3.1进程调度的功能记录系统中所有进程的执行情况将各进程的执行情况和状态特征记录在各进程的PCB中进程在活动期间状态是变化的，例如由运行状态到等待，等待到就绪，就绪到运行根据各进程的状态特征和资源需求，将各进程的PCB表排成相应的队列选择占有处理机的进程在处理机空闲时，根据一定的原则选择一个就绪状态的进程来运行选择策略多种多样，他们决定了调度的性能44.3.1进程调度的功能切换进程上下文进程上下文有正文段、数据段、硬件寄存器（指令计数器、处理机状态字寄存器、过程调用时传递参数的通用寄存器等）的内容以及有关的数据结构（PCB表）组成。首先检查是否可以做切换（执行不允许中断的原语时不可切换）然后保留被切换进程的上下文，以便以后切换回该进程时顺利恢复执行由调度程序选择一个进程，装载该进程的上下文。控制转向该进程，从刚恢复的程序计数器所指示的指令地址开始执行54.3.2进程调度的时机一个进程完成其任务时。执行中的进程自己调用阻塞原语，进入等待状态。执行了一次P操作，资源不满足；执行V操作激活了等待队列的进程。执行的进程提出I/O请求后被阻塞。在分时系统中，当进程完规定的时间片，时钟中断使该进程让出处理机时。执行完系统调用，系统返回用户态之前，由于系统进程结束，需要调度新的进程。在采用可剥夺调度方式的系统中，当具有更高优先级的进程要求处理机时。6可剥夺方式与非剥夺方式就绪队列中只要有优先级更高的进程就停止现运行进程而让高优先级的进程运行。这种方式叫做可剥夺式。即使就绪队列存在高优先级的进程，仍然让现进程继续运行，直到该进程时间片用完或因发生某事件而进入等待状态。这时才将处理机分派给优先级更高的进程，这种方式叫做非剥夺方式。74.3.3进程调度性能评价进程调度策略的好坏直接影响作业调度的性能。作业周转时间和平均周转时间在某种程度上反映了进程调度的性能。定性评价可靠性简洁性定量评价CPU利用率进程在就绪队列里的等待时间与执行时间之比84.4调度算法先来先服务FCFS法——作业和进程最短作业优先SJF法最高响应比优先法优先级法轮转法多级反馈轮转法94.4.1先来先服务(FCFS)法先来先服务算法是按作业来到的次序进行调度的。这种算法优先考虑在系统中等待时间最长的作业或进程，而不管它要求运行时间的长短。这种算法简单，容易实现，但效率较低。因为它没有考虑作业的运行特性和对资源的要求，所以影响了系统效率的发挥。10例子下面是4个作业在系统中从提交、运行、完成的各个信息。作业提交时间运行时间开始时间完成时间周转时间带权周转时间1828102128.50.51010.524390.110.510.61.61649.50.2010.610.81.36.5平均周转时间：T=1.725平均带权周转时间W=6.875114.4.2最短作业优先(SJF)法比较作业缓冲区中的作业预计的运行时间，选择预计时间最短的作业进入运行状态。这种算法简单，并且效率相对较高。主要问题是对长作业不利，如果系统不断地接受短作业，就会使长作业长时间等待。12例子作业提交时间运行时间开始时间完成时间周转时间带权周转时间1828102128.50.510.310.82.34.6390.11010.11.11149.50.2010.110.30.84平均周转时间：T=1.55平均带权周转时间W=5.15134.4.3最高响应比优先法响应比=(W+T)/T=1+W/TW:作业在后备状态队列中的等待时间

T:该作业估计需要的执行时间每调度一个作业后，就计算作业缓冲区中作业的响应比，下一次选择响应比高的作业运行。预计运行时间短的作业，其响应比较高，所以它的总的执行时间较短。而长作业如果在系统中等待的时间较长，其响应比随着等待时间的增加而提高，所以它的等待时间也不会太长。这种算法既照顾了短作业、也考虑到了长作业。14例子作业提交时间运行时间开始时间完成时间周转时间带权周转时间1828102128.50.510.110.62.14.2390.11010.11.11149.50.2010.6010.81.36．5平均周转时间：T=1.625W=5.675154.4.4优先级法系统或用户按照某种原则为作业或进程指定一个优先级来表示所享有的优先权。系统将处理机的使用权交给就绪队列中优先数最高的进程。确定优先级的方法静态法:开始执行之前就确定，执行开始之后不可改变动态法：随着执行过程不断变化优先级作业静态优先级用户指定，高优先级高费用根据作业类型指定优先级根据作业要求资源情况指定优先级164.4.4优先级法进程静态优先级根据进程的类型系统进程调度进程I/O进程中断处理进程存储管理进程I/O繁忙CPU繁忙I/O与CPU均衡将作业的静态优先级作为它所属进程的优先级174.4.4优先级法进程动态优先级根据进程占用CPU时间的长短占用处理机时间越长，阻塞之后再次获得调度的优先级越低根据就绪进程等待CPU的时间长短等待时间越长，获得调度选中的优先级越高动态进程优先级需要系统付出一定的开销184.4.5轮转法将CPU的处理时间分成固定大小的时间片如果一个进程用完了时间片，但没有完成任务，则释放CPU而排到就绪队列的末尾，等待下一次调度轮转法只能用来调度分配可以抢占的资源作业调度包括有不可抢占硬件资源的分配，所以不使用轮转法时间片的长度为系统要求的响应时间/就绪队列允许的最大进程数194.4.5轮转法就绪队列中的进程均匀获得时间片。如果时间片太大，则每个进程等待的时间就会较长，用户会感觉到明显的等待，如果时间片太小，则系统的开销就显得较大。所以时间片的选择是非常重要的。一般为100或几百毫秒。每个进程获得的时间片是固定的，并且只有一个就绪队列。改进的方向：将固定时间片为可变时间片、将一个就绪队列该为多个就绪队列。204.4.5轮转法在固定时间片的方法中，如果有Q=T/Nmax关系，当用户允许的响应时间为3秒，最大进程数为30时，每个进程占用处理机的时间时0.1秒。如果在某个时刻，系统中的进程数为6个，因为每个进程占用处理机的时间是固定的，所以这时响应时间变短。但实际上，用户已经满意了3秒的响应时间，没有必要缩短响应时间，而使每个进程多占用一些处理机时间对提高系统效率有好处。这时就可以使用可变时间片算法：每当一轮开始时，系统便根据就绪队列中的进程数计算一次时间片，然后按新的时间片运行，在此期间到达的进程都不入就绪队列，而等到这轮完成后，参加新的时间片计算。214.4.6多级反馈轮转法轮转法中，加入就