《操作系统第6讲》由会员分享，可在线阅读，更多相关《操作系统第6讲（28页珍藏版）》请在金锄头文库上搜索。
1、操作系统概念第六讲 CPU调度(1)Operating System ConceptionDavidfu上章回顾1、产生死锁的四个必要条件？如何预防？Operating System ConceptionDavidfu本课总体纲要基本概念基本概念调度术语调度术语作业调度作业调度进程调度进程调度进程调度功能进程调度功能进程调度的时机进程调度的时机进程上下文切换进程上下文切换进程调度的性能评价进程调度的性能评价调度算法调度算法先到先服务调度先到先服务调度最短作业优先调度最短作业优先调度优先权调度优先权调度轮转法调度轮转法调度Operating System ConceptionDavidfu基本概
2、念CPU调度：调度：进程调度程序按照一定的策略，动态的将进程调度程序按照一定的策略，动态的将CPU分配给某个进程，并使之执行。分配给某个进程，并使之执行。目的：以使目的：以使CPU资源利用率最高。资源利用率最高。进程执行由进程执行由CPU执行与执行与IO等待周期组成。等待周期组成。Operating System ConceptionDavidfu基本概念 CPU区间时间直方图Operating System ConceptionDavidfuCPU调度当CPU变为空闲时，操作系统就必须从就绪的队列中选择一个进程来执行。系统调度分为4级：作业调度交换调度进程调度线程调度Operating Sy
3、stem ConceptionDavidfu本课总体纲要基本概念基本概念调度术语调度术语作业调度作业调度进程调度进程调度进程调度功能进程调度功能进程调度的时机进程调度的时机进程上下文切换进程上下文切换进程调度的性能评价进程调度的性能评价调度算法调度算法先到先服务调度先到先服务调度最短作业优先调度最短作业优先调度优先权调度优先权调度轮转法调度轮转法调度Operating System ConceptionDavidfu调度术语调度术语CPU利用率：使利用率：使CPU尽可能忙，实现高效。尽可能忙，实现高效。吞吐量：吞吐量：(throughput)单位时间中完成的进程单位时间中完成的进程周转时间：运
4、行该进程所花费的时间周转时间：运行该进程所花费的时间等待时间：在就绪队列中等待所花费的时间等待时间：在就绪队列中等待所花费的时间响应时间：从提交请求到产生第一个响应的时响应时间：从提交请求到产生第一个响应的时间间Operating System ConceptionDavidfuCPU作业调度作业调度功能：作业调度功能：记录系统中作业的状况记录系统中作业的状况从后备作业队列中挑选一批作业进入执行状从后备作业队列中挑选一批作业进入执行状态态被选中的作业分配资源建立进程被选中的作业分配资源建立进程作业执行结束后释放所占用的资源作业执行结束后释放所占用的资源作业调度目标：作业调度目标：对所有作业应该
5、公平合理对所有作业应该公平合理较高的利用率较高的利用率每天执行尽可能多的作业每天执行尽可能多的作业响应时间快响应时间快Operating System ConceptionDavidfu本课总体纲要基本概念基本概念调度术语调度术语作业调度作业调度进程调度进程调度进程调度功能进程调度功能进程调度的时机进程调度的时机进程上下文切换进程上下文切换进程调度的性能评价进程调度的性能评价调度算法调度算法先到先服务调度先到先服务调度最短作业优先调度最短作业优先调度优先权调度优先权调度轮转法调度轮转法调度Operating System ConceptionDavidfu进程调度功能功能包括：记录系统中所有进
6、程的执行情况选择占有处理机的进程进行进程上下文切换Operating System ConceptionDavidfu进程调度时机进程执行完毕进入睡眠等待状态执行进程中调用了P,V原语执行中进程提出I/O请求分时系统中时间片已经用完系统进程执行完毕，调度用户进程就绪队列中某进程优先权高于当前执行的进程Operating System ConceptionDavidfu进程上下文切换进程上下文切换包括四个步骤：决定是否做上下文切换保存当前执行的进程上下文采用合理的调度算法，选择一个处于就绪状态进程恢复所选进程的上下文，将控制权交给所选进程 Operating System ConceptionD
7、avidfu进程调度性能评价进程调度性能的衡量是操作系统设计的一个重要指标定性：调度的可靠性、简洁性定量：CPU利用率，进程的等待/执行率方法：对进程调度的解析是十分困难的，一般采用模拟或测试系统响应时间的方法Operating System ConceptionDavidfu本课总体纲要基本概念基本概念调度术语调度术语作业调度作业调度进程调度进程调度进程调度功能进程调度功能进程调度的时机进程调度的时机进程上下文切换进程上下文切换进程调度的性能评价进程调度的性能评价调度算法调度算法先到先服务调度先到先服务调度最短作业优先调度最短作业优先调度优先权调度优先权调度轮转法调度轮转法调度Operati
8、ng System ConceptionDavidfu调度算法调度算法先到先服务调度（FCFS）先请求CPU的进程被首先分配到CPU当进程之间的处理时间相差较大时，采用FCFS策略的平均等待时间较长。Process Burst TimeP1 24P2 3P3 3 P1P2P32427300P1P3P263300Operating System ConceptionDavidfu最短作业优先调度最短作业优先调度最短作业优先调度（SJF）将每个进程与其下一个CUP区间段相关联，当CPU可用时，它会赋给具有最短后续CPU区间的进程两种方法非抢占性一旦一个进程开始执行就需完成该次任务抢占性如果新来的进
9、程CPU区间段比当前进程的时间段小，则优先选择新进程。称为SRTF(Shorest Remaining Time First)SJF算法是最优的。Operating System ConceptionDavidfu最短作业优先调度最短作业优先调度 进程 到达时间区间时间P10.07P22.04P34.01P45.04SJF (非抢占性)SJF平均等待时间 = (0 + (7-4)+(8-2) +(12-5)/4 =4msFCFSFCFS平均等待时间（平均等待时间（0 0(7-2)(7-2)(11-4)(11-4)(12-(12-5)/5)/4=4.75ms4=4.75msP1P3P273160
10、P4812Operating System ConceptionDavidfu最短作业优先调度最短作业优先调度 Process Arrival TimeBurst TimeP10.07P22.04P34.01P45.04SJF (抢占性)P1P3P242110P457P2P116平均等待时间 = (9 + 1 + 0 +2)/4 = 3Operating System ConceptionDavidfu最短作业优先调度最短作业优先调度如何决定下一个CPU区间的长度用前一个CPU区间的长度估计下一个CPU区间的长度Operating System ConceptionDavidfu最短作业优先调
11、度最短作业优先调度 =0n+1 = nRecent history does not count =1 n+1 = tn实际最后一个CPU区间记数。n+1 = tn+(1 - ) tn -1 + +(1 - )j tn -j + +(1 - )n +1 0因为 and (1 - ) 小于或等于 1,所以后面项的权比前面项权要小。Operating System ConceptionDavidfu最短作业优先调度最短作业优先调度Operating System ConceptionDavidfu优先权调度优先权调度每个进程都有优先权具有最高优先权的进程分配给CPUSJF算法作为优先权算法的特例。
12、优先权为下一个CPU区间的倒数。CPU区间越大，优先权越小导致的问题：饥饿（starvation)低优先权的进程可能永远也不会运行。（无穷阻塞）解决方案：老化(aging)逐渐增加在系统中等待很长时间的进程的优先权。Operating System ConceptionDavidfu轮转法调度（轮转法调度（Round-Robin)轮转法调度：专门为分时系统设计的。每个进程得到一个较小的时间单元时间片（time quantum），时间片通常（10ms100ms)。系统给每个进程分配若干个时间片，被调度的进程运行完时间片后，系统就发生调度。如果有n个进程，q个时间片，那么每个进程会得到1/n的CP
13、U时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过（n-1）q个时间单元，直到下一个时间片为止。两种情况：CPU区间小于时间片CPU区间大于时间片Operating System ConceptionDavidfu轮转法调度轮转法调度ProcessBurst TimeP153P2 17P368P4 24甘特图为（时间片q20ms): 特点：平均等待时间较高，但响应较好P1P2P3P4P1P3P4P1P3P302037577797117121 134154 162Operating System ConceptionDavidfu轮转法调度轮转法调度时间片与上下文时间的关系O
14、perating System ConceptionDavidfu轮转法调度轮转法调度不同时间片的平均等待时间统计轮转法性能Q若较大FIFOQ若较小=q的长度要比上下文切换时间长，否则造成浪费。80的CPU区间应该小于时间片Operating System ConceptionDavidfu总结基本概念基本概念调度术语调度术语作业调度作业调度进程调度进程调度进程调度功能进程调度功能进程调度的时机进程调度的时机进程上下文切换进程上下文切换进程调度的性能评价进程调度的性能评价调度算法调度算法先到先服务调度先到先服务调度最短作业优先调度最短作业优先调度优先权调度优先权调度轮转法调度轮转法调度Operating System ConceptionDavidfu
