操作系统原理第4章

14.1分级调度4.2作业调度4.3进程调度4.4调度算法4.5算法评价4.6实时系统调度方法第4章处理机调度24.1分级调度4.1.1作业的状态及其转换4.1.2调度的层次(1)作业调度——宏观调度或高级调度(2)交换调度——中级调度(3)进程调度——微观调度或低级调度(4)线程调度4.1.3作业与进程的关系第4章处理机调度3

进程状态及其转换第4章处理机调度RunningTerminateReadyBlockedReadySuspendedBlockedSuspendedEventWaitEventOccursCreateResumeSuspendResumeSuspendDispatchEventOccursTimeout4作业状态及其转换第4章处理机调度运行就绪等待完成收容提交用户作业录入作业调度作业调度执行54.2作业调度4.2.1作业调度功能4.2.2作业调度目标与性能衡量调度目标：(1)对所有的作业应该是公平合理的；(2)应使设备有高的利用率；(3)执行尽可能多的作业（吞吐量大）；(4)有快的响应时间。性能衡量：1.周转时间Ti=TeiTsi或Ti=Twi+Tri(Tsi—作业的提交时间，Tei—作业的完成时间)2.带权周转时间Wi=Ti/Tri第4章处理机调度6第4章处理机调度4.3进程调度4.3.1进程调度的功能4.3.2进程调度的时机4.3.3进程上下文切换4.3.4进程调度性能评价7第4章处理机调度4.4调度算法1.先来先服务FCFS——FirstComeFirstServe2.轮转法RR——RoundRobin3.多级反馈轮转法——RoundRobinwithmultiplefeedback4.优先级法——静态法和动态法[例]线性优先级调度策略图4.5线性优先级调度CPU完成新创建进程队列享受服务进程队列8第4章处理机调度新创建进程队列中进程的优先级P=a*t(a>0)

享受服务进程队列中进程的优先级P=b*t(a>b>0)

P(t)=a*(tt1) 进程在时刻t1被创建

P(t)=a*(t1't1)+b*(t

t1') 进程在时刻t1'转入享受服务队列若b>a>0，则为FCFS；若a>b=0，则为RR法。线性优先级调度策略介于FCFS和RR法之间。图4.6优先级变化曲线t1t1'

t2t2'tP(t)b(t

t1')a(tt1)9第4章处理机调度4.4调度算法5.最短作业优先法SJF——ShortestJobFirst6.最高响应比优先法HRN——HighestResponse-ratioNext响应比=等待时间/运行时间[例]9:30开始调度：作业A的响应比=40/90，作业B的响应比=30/24，作业C的响应比=0/60。9:54调度：作业A的响应比=64/90，作业C的响应比=24/60。调度次序：B、A、C。作业到输入井时间执行时间A8:501.5小时B9:000.4小时C9:301小时10第4章处理机调度常用的作业调度算法(1)先来先服务(FCFS——FirstComeFirstServe)(2)短作业优先(SJF——ShortestJobFirst)(3)响应比高者优先(HRN——HighestResponse-ratioNext) 响应比=等待时间/运行时间(4)优先级调度(5)均衡调度算法(资源调度算法)11第4章处理机调度试题6（90）从供选择的答案中，选出应填入下列叙述中__n__内的正确答案，把编号写在答卷的对应栏内。假设某多道程序设计系统有供用户使用的主存空间100K，磁带机2台，打印机1台，系统采用可变分区方式管理主存，对磁带机和打印机采用静态分配，并假设输入输出操作的时间忽略不计。现有一作业序列如下：作业号进输入井时间要求计算时间要求主存量申请磁带机数申请打印机数18:0025分钟15K1台1台28:2010分钟30K0台1台38:2020分钟60K1台0台48:3020分钟20K1台0台58:3515分钟10K1台1台12第4章处理机调度假设作业调度采用先来先服务算法，优先分配主存的低地址区域且不准移动已在主存中的作业，在主存中的作业平分CPU时间，则作业调度选中作业的次序是__A__，如果把一个作业从进入输入井到得到计算结果的时间定义为周转时间，则在忽略系统工作时间的情况下，最大的作业周转时间是__B__，最小的作业周转时间是__C__，作业的平均周转时间是__D__，作业全部执行结束的时间是__E__。供选择的答案A：①(1,3,2,4,5) ②(1,2,3,4,5) ③(1,3,4,2,5) ④(1,