操作系统第6讲

1、操作系统概念第六讲 CPU调度(1)上章回顾1、产生死锁的四个必要条件？如何预防？本课总体纲要基本概念调度术语作业调度进程调度进程调度功能进程调度的时机进程上下文切换进程调度的性能评价调度算法先到先服务调度最短作业优先调度优先权调度轮转法调度基本概念CPU调度：进程调度程序按照一定的策略，动态的将CPU分配给某个进程，并使之执行。目的：以使CPU资源利用率最高。进程执行由CPU执行与IO等待周期组成。基本概念 CPU区间时间直方图CPU调度当CPU变为空闲时，操作系统就必须从就绪的队列中选择一个进程来执行。系统调度分为4级：作业调度交换调度进程调度线程调度本课总体纲要基本概念调度术语作业调度进

2、程调度进程调度功能进程调度的时机进程上下文切换进程调度的性能评价调度算法先到先服务调度最短作业优先调度优先权调度轮转法调度调度术语CPU利用率：使CPU尽可能忙，实现高效。吞吐量：(throughput)单位时间中完成的进程周转时间：运行该进程所花费的时间等待时间：在就绪队列中等待所花费的时间响应时间：从提交请求到产生第一个响应的时间CPU作业调度作业调度功能：记录系统中作业的状况从后备作业队列中挑选一批作业进入执行状态被选中的作业分配资源建立进程作业执行结束后释放所占用的资源作业调度目标：对所有作业应该公平合理较高的利用率每天执行尽可能多的作业响应时间快本课总体纲要基本概念调度术语作业调度进

3、程调度进程调度功能进程调度的时机进程上下文切换进程调度的性能评价调度算法先到先服务调度最短作业优先调度优先权调度轮转法调度进程调度功能功能包括：记录系统中所有进程的执行情况选择占有处理机的进程进行进程上下文切换进程调度时机进程执行完毕进入睡眠等待状态执行进程中调用了P,V原语执行中进程提出I/O请求分时系统中时间片已经用完系统进程执行完毕，调度用户进程就绪队列中某进程优先权高于当前执行的进程进程上下文切换进程上下文切换包括四个步骤：决定是否做上下文切换保存当前执行的进程上下文采用合理的调度算法，选择一个处于就绪状态进程恢复所选进程的上下文，将控制权交给所选进程 进程调度性能评价进程调度性能的衡

4、量是操作系统设计的一个重要指标定性：调度的可靠性、简洁性定量：CPU利用率，进程的等待/执行率方法：对进程调度的解析是十分困难的，一般采用模拟或测试系统响应时间的方法本课总体纲要基本概念调度术语作业调度进程调度进程调度功能进程调度的时机进程上下文切换进程调度的性能评价调度算法先到先服务调度最短作业优先调度优先权调度轮转法调度调度算法先到先服务调度（FCFS）先请求CPU的进程被首先分配到CPU当进程之间的处理时间相差较大时，采用FCFS策略的平均等待时间较长。Process Burst TimeP1 24P2 3P3 3 P1P2P32427300P1P3P263300最短作业优先调度最短作业

5、优先调度（SJF）将每个进程与其下一个CUP区间段相关联，当CPU可用时，它会赋给具有最短后续CPU区间的进程两种方法非抢占性一旦一个进程开始执行就需完成该次任务抢占性如果新来的进程CPU区间段比当前进程的时间段小，则优先选择新进程。称为SRTF(Shorest Remaining Time First)SJF算法是最优的。最短作业优先调度 进程 到达时间区间时间P10.07P22.04P34.01P45.04SJF (非抢占性)SJF平均等待时间 = (0 + (7-4)+(8-2) +(12-5)/4 =4msFCFS平均等待时间（0(7-2)(11-4)(12-5)/4=4.75msP1

6、P3P273160P4812最短作业优先调度 ProcessArrival TimeBurst TimeP10.07P22.04P34.01P45.04SJF (抢占性)P1P3P242110P457P2P116平均等待时间 = (9 + 1 + 0 +2)/4 = 3最短作业优先调度如何决定下一个CPU区间的长度用前一个CPU区间的长度估计下一个CPU区间的长度最短作业优先调度 =0n+1 = nRecent history does not count =1 n+1 = tn实际最后一个CPU区间记数。n+1 = tn+(1 - ) tn -1 + +(1 - )j tn -j + +(1

7、 - )n +1 0因为 and (1 - ) 小于或等于 1,所以后面项的权比前面项权要小。最短作业优先调度优先权调度每个进程都有优先权具有最高优先权的进程分配给CPUSJF算法作为优先权算法的特例。优先权为下一个CPU区间的倒数。CPU区间越大，优先权越小导致的问题：饥饿（starvation)低优先权的进程可能永远也不会运行。（无穷阻塞）解决方案：老化(aging)逐渐增加在系统中等待很长时间的进程的优先权。轮转法调度（Round-Robin)轮转法调度：专门为分时系统设计的。每个进程得到一个较小的时间单元时间片（time quantum），时间片通常（10ms100ms)。系统给每个进

8、程分配若干个时间片，被调度的进程运行完时间片后，系统就发生调度。如果有n个进程，q个时间片，那么每个进程会得到1/n的CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过（n-1）q个时间单元，直到下一个时间片为止。两种情况：CPU区间小于时间片CPU区间大于时间片轮转法调度ProcessBurst TimeP153P2 17P368P4 24甘特图为（时间片q20ms): 特点：平均等待时间较高，但响应较好P1P2P3P4P1P3P4P1P3P302037577797117121134154162轮转法调度时间片与上下文时间的关系轮转法调度不同时间片的平均等待时间统计轮转法性能