操作系统原理第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*(tt1') 进程在时刻t1'转入享受服务队列若b>a>0，则为FCFS；若a>b=0，则为RR法。线性优先级调度策略介于FCFS和RR法之间。图4.6优先级变化曲线t1t1'

t2t2'tP(t)b(tt1')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,2,4,3,5)B~D：①30分钟 ②36分钟 ③40分钟 ④44分钟 ⑤55分钟 ⑥64分钟E：①9:20 ②9:30 ③9:40 ④9:50A：③B：⑤C：①D：④E：②13第4章处理机调度内存分配图J1—15K空闲85KJ1—15KJ3—60K空闲25K空闲15KJ3—60KJ4—20K空闲5KJ2—30KJ4—20K空闲5K空闲45KJ2—30K空闲70KJ5—10K空闲90K8:008:208:309:009:109:1514第4章处理机调度8:008:208:308:359:009:109:159:30J1J2J3J4J55分钟15分钟20分钟15分钟5分钟周转时间：J1(30分钟)、J2(55分钟)、J3(40分钟)、J4(40分钟)、J5(55分钟)5分钟5分钟5分钟15分钟15第4章处理机调度4.6实时系统调度方法4.6.1实时系统的特点(1)有限等待时间(2)有限响应时间(3)用户控制(4)可靠性高(5)系统出错处理能力强4.6.2实时调度算法的分类(1)静态表格驱动类(2)静态优先级驱动抢先式调度算法类(3)动态计划调度算法类(4)尽力而为调度算法类16第4章处理机调度4.6.3时限调度算法与频率单调调度算法开始时限——startingdeadline结束时限——endingdeadline时限调度算法所需要的相关输入信息：(1)任务就绪时间或事件到达时间(2)开始时限(3)完成时限(4)处理时间(5)资源需求(6)优先级17第4章处理机调度[例]设实时系统从两个不同的数据源DA和DB周期性地收集数据并进行处理，其中DA的时限要求以30ms为周期，DB的时限要求以75ms为周期。设DA所需处理时限为15ms，DB所需处理时限为38ms，则与DA和DB有关进程的事件发生时限（就绪时限）、执行时限以及结束时限如下图所示。进程事件发生时限执行时限结束时限DA(1)01530DA(2)301560DA(3)601590…………DB(1)03875DB(2)7538150DB(3)15038225…………18第4章处理机调度频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。频率单调调度算法的基本原理是频率越低（周期越长）的任务的优先级越低。设任务周期为T，任务的执行时间为C，则使用频率单调调度算法的必要条件是C≤T。图4.12时限调度算法的调度顺序153045607590105130tDA(1)DB(1)DA(2)DB(1)DB(1)DA(3)DA(4)DB(2)…19第4章处理机调度设有A、B、C三个作业，执行情况如下表所示。请填写周转时间栏，并回答下列问题：(1)作业的平均周转时间是多少？(2)采用了什么作业调度算法？

作业名到达时间开始执行时间执行结束时间周转时间(小时)A10:0010:0012:00B10:1012:2513:25C10:2512:0012:2520第4章处理机调度(1)作业的平均周转时间是2.42小时。(2)采用的作业调度算法是SJF。作业名到达时间开始执行时间执行结束时间周转时间(小时)A10:0010:0012:002.00B10:1012:2513:253.25C10:2512:0012:252.0021k个进程共享某种资源r，该资源共有m个可分配单位，每个进程一次申请和释放资源单位一个。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m+k，试证明这个系统中不可能产生死锁。反证法：假设系统已发生死锁M(i)——第i个进程的最大资源需求量N(i)——第i个进程还需要的资源量U(i)——第i个进程已分配的资源量M(1)+M(2)+…+M(k)=(N(1)+N(2)+…+N(