操作系统第6讲课件

操作系统概念

第六讲 CPU调度(1)OperatingSystemConceptionDavidfu上章回顾1、产生死锁的四个必要条件？如何预防？OperatingSystemConceptionDavidfu本课总体纲要基本概念调度术语作业调度进程调度进程调度功能进程调度的时机进程上下文切换进程调度的性能评价调度算法先到先服务调度最短作业优先调度优先权调度轮转法调度OperatingSystemConceptionDavidfu基本概念CPU区间时间直方图OperatingSystemConceptionDavidfuCPU调度当CPU变为空闲时，操作系统就必须从就绪的队列中选择一个进程来执行。系统调度分为4级：作业调度交换调度进程调度线程调度OperatingSystemConceptionDavidfu本课总体纲要基本概念调度术语作业调度进程调度进程调度功能进程调度的时机进程上下文切换进程调度的性能评价调度算法先到先服务调度最短作业优先调度优先权调度轮转法调度OperatingSystemConceptionDavidfuCPU作业调度作业调度功能：记录系统中作业的状况从后备作业队列中挑选一批作业进入执行状态被选中的作业分配资源建立进程作业执行结束后释放所占用的资源作业调度目标：对所有作业应该公平合理较高的利用率每天执行尽可能多的作业响应时间快OperatingSystemConceptionDavidfu本课总体纲要基本概念调度术语作业调度进程调度进程调度功能进程调度的时机进程上下文切换进程调度的性能评价调度算法先到先服务调度最短作业优先调度优先权调度轮转法调度OperatingSystemConceptionDavidfu进程调度功能功能包括：记录系统中所有进程的执行情况选择占有处理机的进程进行进程上下文切换OperatingSystemConceptionDavidfu进程上下文切换进程上下文切换包括四个步骤：决定是否做上下文切换保存当前执行的进程上下文采用合理的调度算法，选择一个处于就绪状态进程恢复所选进程的上下文，将控制权交给所选进程OperatingSystemConceptionDavidfu进程调度性能评价进程调度性能的衡量是操作系统设计的一个重要指标定性：调度的可靠性、简洁性定量：CPU利用率，进程的等待/执行率方法：对进程调度的解析是十分困难的，一般采用模拟或测试系统响应时间的方法OperatingSystemConceptionDavidfu本课总体纲要基本概念调度术语作业调度进程调度进程调度功能进程调度的时机进程上下文切换进程调度的性能评价调度算法先到先服务调度最短作业优先调度优先权调度轮转法调度OperatingSystemConceptionDavidfu最短作业优先调度最短作业优先调度（SJF）将每个进程与其下一个CUP区间段相关联，当CPU可用时，它会赋给具有最短后续CPU区间的进程两种方法非抢占性－一旦一个进程开始执行就需完成该次任务抢占性－如果新来的进程CPU区间段比当前进程的时间段小，则优先选择新进程。称为SRTF(ShorestRemainingTimeFirst)SJF算法是最优的。OperatingSystemConceptionDavidfu最短作业优先调度进程到达时间

区间时间

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(非抢占性)SJF平均等待时间=(0+(7-4)+(8-2)+(12-5))/4=4msFCFS平均等待时间＝（0＋(7-2)＋(11-4)＋(12-5))/4=4.75msP1P3P273160P4812OperatingSystemConceptionDavidfu最短作业优先调度

Process ArrivalTime

BurstTime

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(抢占性)P1P3P242110P457P2P116平均等待时间=(9+1+0+2)/4=3OperatingSystemConceptionDavidfu最短作业优先调度=0n+1=nRecenthistorydoesnotcount=1n+1=tn实际最后一个CPU区间记数。n+1=tn+(1-)tn

-1

+…

+(1-)j

tn

-j

+…

+(1-)n+10

因为and(1-)小于或等于1,所以后面项的权比前面项权要小。OperatingSystemConceptionDavidfu最短作业优先调度OperatingSystemConceptionDavidfu优先权调度每个进程都有优先权具有最高优先权的进程分配给CPUSJF算法作为优先权算法的特例。优先权为下一个CPU区间的倒数。CPU区间越大，优先权越小导致的问题：饥饿（starvation)－低优先权的进程可能永远也不会运行。（无穷阻塞）解决方案：老化(aging)－逐渐增加在系统中等待很长时间的进程的优先权。OperatingSystemConceptionDavidfu轮转法调度Process

BurstTime P1 53

P2 17

P3 68

P4 24甘特图为（时间片q＝20ms):

特点：平均等待时间较高，但响应较好P1P2P3P4P1P3