《System处理机调度课件》由会员分享，可在线阅读，更多相关《System处理机调度课件（35页珍藏版）》请在金锄头文库上搜索。
1、第四章: 处理机调度（CPU Scheduling）,4.1 基本概念 4.2 调度准则 4.3 调度算法 4.4 多CPU进程调度 4.5 实时系统调度 4.6 评估算法,4.1 基本概念,让CPU充分利用，在多道程序中提高CPU的利用率 CPU 调度是操作系统设计的核心 CPUI/O 中断周期 进程执行包括CPU执行周期和I/O等待周期,CPU和I/O中断的连续交换,I/O-bound program and CPU-bound program,CPU中断时间的矩形图,CPU burst时间长度在0-8微秒的是大多数,CPU调度,短期调度 ，也称低级调度。 功能：在存储器中准备执行的多个进
2、程中选择，将CPU分配给多个进程中的一个。 执行时机： CPU 调度可能发生在一个进程: 1. 从运行状态转换到等待状态（如等待I/O） 2. 从运行状态转换到就绪状态 （如中断发生） 3.从等待状态转换到就绪状态 （如I/O结束） 4.终止状态 其中1和4是非抢占，其他的都是抢占。 在非抢占的调度中, 一个处于运行状态的进程一直占有CPU，直到这个进程终止或它从运行状态转换到等待状态才会释放CPU。,调度员,调度模型 gives control of the CPU to the process selected by the short-term scheduler; this invol
3、ves: 上下文切换 处理机状态变为User,而以前是Kernel. 跳转到执行程序的适当位置重新执行此程序。 反应时间 指调度员从终止一个进程到开始另一个进程的时间。,42调度准则,CPU利用率 让CPU越忙越好 吞吐率 在单位时间内执行完的进程数量 周转时间 一个进程从存在到结束的时间间隔 等待时间 一个进程在等待队列中等待的时间 响应时间 从请求发出到系统第一次响应的时间,最优准则,CPU利用率最大 吞吐率最大的 周转时间最短 等待时间最短 响应时间最短,4.3 调度算法,先来先服务First-Come, First-Served (FCFS) 短作业优先Shortest-Job-Fir
4、st (SJF) 优先级调度Priority Scheduling 轮转调度Round Robin (RR) 多级队列调度Multilevel Queue 多级反馈队列调度Multilevel Feedback Queue,先来先服务调度,示例:ProcessBurst Time P124 P2 3 P3 3 如果以上进程到达的顺序为: P1 , P2 , P3 ，那么调度的图示如下： 等待时间 P1 = 0; P2 = 24; P3 = 27 平均等待时间: (0 + 24 + 27)/3 = 17,先来先服务调度 （续1）,如果进程到达的顺序为 : P2 , P3 , P1 . 调度的图示
5、为 : 等待时间 P1 = 6; P2 = 0; P3 = 3 平均等待时间 : (6 + 0 + 3)/3 = 3 比前一种好,P1,P3,P2,6,3,30,0,有利于长进程，实现简单，对系统性能会有影响， 可用于作业调度和进程调度,短作业优先调度,关系到每一个进程下一个CPU中断时间的长度. 时间最短的先执行 两种方案: 非抢占 once CPU given to the process, it cannot be preempted until completes its CPU burst(进程自愿放弃CPU) 抢占 if a new process arrives with CPU
6、 burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF） 短作业优先的特点 偏向短作业，平均周转时间短。,ProcessArrival TimeBurst Time P10.07 P22.04 P34.01 P45.04 SJF (non-preemptive) 平均等待时间 = (0 + 6 + 3 + 7)/4 = 4,非抢占短优先调度示例,P1,P3,P2,7,3,
7、16,0,P4,8,12,抢占短作业优先调度示例,ProcessArrival TimeBurst Time P10.07 P22.04 P34.01 P45.04 SJF (preemptive) 平均等待时间 = (9 + 1 + 0 +2)/4 = 3,P1,P3,P2,4,2,11,0,P4,5,7,P2,P1,16,下一个CPU中断长度的确定,只能做长度的估计 将前一个的CPU中断时间长度作为指数,SJF有短的平均等待时间，有利于短作业，可能会饿死长作业， 实现较复杂。通常用于作业调度,优先级调度,每个进程都具有优先度 (integer) 优先级最高的先被执行（数字越小表示优先级越高
8、） 抢占 非抢占 短作业优先是优先级调度的一种，优先级的设定是根据下一个CPU中断的时间长短。 问题：饥饿 优先级低的进程可能永远不会被执行 解决方法 ：老化 优先级随着等待时间的加长而提高,优先数法考虑进程的质而不是量，有动态和静态两种。优先 数的计算公式可决定调度算法。可用于作业调度和进程调度， 实时系统应采用可抢先的优先数法,优先数法例,UNIX system v p_pri = P_cpu / 2 + PUSER + P_nice + NZERO Windows 2000/xp 基于优先级的抢先式多处理器调度算法 优先级分为： 实时优先级:（16-31，静态，超级用户可设置） 可变优先
9、级:（1-15，普通用户用）,轮转式调度 (RR),将CPU的处理时间分成固定大小的时间片，通常10-100 milliseconds.如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU，而排到就绪队列的末尾，等待下一次调度。 如果在等待队列里有n 个进程，时间片为 q,那么在q*n时间单元中每个进程获得CPU时间为 1/n. 没有进程等待时间超过 (n-1)q 性能 q large FIFO q small q must be large with respect to context switch, otherwise overhead
10、is too high.,示例: RR （时间片为20）,ProcessBurst Time P153 P2 17 P368 P4 24 图示: 实现简单，平均周转时间SJF，但响应时间比它短。,0,20,37,57,77,97,117,121,134,154,162,时间片短上下文切换次数增加,Turnaround Time Varies With The Time Quantum,RR实现简单，有较好的响应时间，用于分时系统的进程调度,多级队列调度,Ready queue is partitioned into separate queues: - foreground (interact
11、ive) - background (batch) Each queue has its own scheduling algorithm - foreground RR - background FCFS Scheduling must be done between the queues. Fixed priority scheduling; i.e., serve all from foreground then from background. Possibility of starvation. Time slice each queue gets a certain amount
12、of CPU time which it can schedule amongst its processes; e.g.,80% to foreground in RR,20% to background in FCFS.,多级队列调度（例）,1-20,21-99,100-199,200-255,256-1024,Time slice,100,200,300,400,500,多级反馈队列调度,A process can move between the various queues; aging can be implemented this way 考虑因素：Multilevel-feed
13、back-queue scheduler defined by the following parameters: number of queues scheduling algorithms for each queue method used to determine when to upgrade a process（向上迁移标准） method used to determine when to demote a process（向下迁移标准） method used to determine which queue a process will enter when the proc
14、ess is created,多级反馈队列调度,多级反馈队列调度示例,三个队列: Q0 time quantum 8 milliseconds Q1 time quantum 16 milliseconds Q2 FCFS Scheduling A new job enters queue Q0. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1 At Q1 job receives 16 additional mil
15、liseconds. If it still does not complete, it is preempted and moved to queue Q2,多级反馈队列实现复杂，比较合理，用于通用系统中的进程 调度。一般都是用动态优先数法实现的,4.4 多进程调度,使用CPU越多，CPU调度算法越复杂。 Homogeneous processors within a multiprocessor （最简单情况，进程可在任何处理机中运行） Load sharing（多个就绪队列 ，还是一个就绪队列（有同步）) Symmetric Multiprocessing (SMP-对称多处理) eac
16、h processor makes its own scheduling decisions.（自调度,实现复杂） Asymmetric multiprocessing（非对称多处理） only one processor accesses the system data structures, alleviating the need for data sharing.（master-slaver，实现简单),4.5 实时调度,硬实时控制 采用专用系统，硬件和软件。应用程序常驻内存，事件激发，实时控制，比通用系统功能少。不用二级存储，虚存 软实时控制 采用可抢先的优先数法.通用系统中，实时进程优先级必须是最高的，切换开销必须小，允许系统调用是可抢先的。如：多媒体处理，实时信息处理 。可能产生饥饿 要求： 具有最优的调度算法 潜伏的可能性必须很小，这要求系统调用允许被抢占。,潜伏,System call is preemption Ins
