操作系统原理第4章

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

2、程状态及其转换第第4 4章章 处理机调度处理机调度RunningTerminateReadyBlockedReadySuspendedBlockedSuspendedEvent WaitEvent OccursCreateResumeSuspendResumeSuspendDispatchEvent OccursTimeout4n 作业状态及其转换作业状态及其转换第第4 4章章 处理机调度处理机调度运行运行就绪就绪等待等待完成完成收容收容提交提交用户用户作业录入作业录入作业调度作业调度作业调度作业调度执行执行54.2 作业调度作业调度4.2.1 作业调度功能作业调度功能4.2.2 作业调度目标

3、与性能衡量作业调度目标与性能衡量n 调度目标：调度目标： (1) 对所有的作业应该是公平合理的；对所有的作业应该是公平合理的； (2) 应使设备有高的利用率；应使设备有高的利用率； (3) 执行尽可能多的作业（吞吐量大）；执行尽可能多的作业（吞吐量大）； (4) 有快的响应时间。有快的响应时间。n 性能衡量：性能衡量： 1. 周转时间周转时间Ti=Tei Tsi或或Ti=Twi+Tri (Tsi作业的提交时间，作业的提交时间，Tei作业的完成时间作业的完成时间) 2. 带权周转时间带权周转时间Wi=Ti/Tri第第4 4章章 处理机调度处理机调度6第第4 4章章 处理机调度处理机调度4.3 进

4、程调度进程调度4.3.1 进程调度的功能进程调度的功能4.3.2 进程调度的时机进程调度的时机4.3.3 进程上下文切换进程上下文切换4.3.4 进程调度性能评价进程调度性能评价7第第4 4章章 处理机调度处理机调度4.4 调度算法调度算法 1. 先来先服务先来先服务FCFSFirst Come First Serve 2. 轮转法轮转法RRRound Robin 3. 多级反馈轮转法多级反馈轮转法Round Robin with multiple feedback 4. 优先级法优先级法静态法和动态法静态法和动态法 例例 线性优先级调度策略线性优先级调度策略图图 4.5 线性优先级调度线性优

5、先级调度CPU完成完成新创建进程队列新创建进程队列享受服务进程队列享受服务进程队列8第第4 4章章 处理机调度处理机调度l 新创建进程队列中进程的优先级新创建进程队列中进程的优先级P=a*t (a0)l 享受服务进程享受服务进程队列中进程的优先级队列中进程的优先级P=b*t (ab0) P(t)=a*(t t1)进程在时刻进程在时刻t1被创建被创建 P(t)=a*(t1 t1)+b*(t t1)进程在时刻进程在时刻t1转入转入享受服务享受服务队列队列 若若ba0，则为，则为FCFS； 若若ab=0，则为，则为RR法。法。 线性优先级调度策略介于线性优先级调度策略介于FCFS和和RR法之间。法之

6、间。图图 4.6 优先级变化曲线优先级变化曲线t1 t1 t2 t2 t P(t)b(t t1)a(t t1)9第第4 4章章 处理机调度处理机调度4.4 调度算法调度算法 5. 最短作业优先法最短作业优先法SJFShortest Job First 6. 最高响应比优先法最高响应比优先法HRNHighest Response-ratio Next 响应比响应比=等待时间等待时间/运行时间运行时间 例例9:30开始调度：作业开始调度：作业A的响应比的响应比=40/90，作业，作业B的响应比的响应比=30/24，作业，作业C的响应比的响应比=0/60。9:54调度：作业调度：作业A的响应比的响应

7、比=64/90，作业，作业C的响应比的响应比=24/60。调度次序：调度次序：B、A、C。作业作业到输入井时间到输入井时间执行时间执行时间A8:501.5小时小时B9:000.4小时小时C9:301小时小时10第第4 4章章 处理机调度处理机调度n 常用的作业调度算法常用的作业调度算法 (1) 先来先服务先来先服务(FCFSFirst Come First Serve) (2) 短作业优先短作业优先(SJFShortest Job First) (3) 响应比高者优先响应比高者优先(HRNHighest Response-ratio Next)响应比响应比=等待时间等待时间/运行时间运行时间

8、(4) 优先级调度优先级调度 (5) 均衡调度算法均衡调度算法(资源调度算法资源调度算法)11第第4 4章章 处理机调度处理机调度试题试题6 （90） 从供选择的答案中，选出应填入下列叙述中从供选择的答案中，选出应填入下列叙述中_n_内的正确答案，把编号内的正确答案，把编号写在答卷的对应栏内。写在答卷的对应栏内。 假设某多道程序设计系统有供用户使用的主存空间假设某多道程序设计系统有供用户使用的主存空间100K，磁带机，磁带机2台，台，打印机打印机1台，系统采用可变分区方式管理主存，对磁带机和打印机采用静态分台，系统采用可变分区方式管理主存，对磁带机和打印机采用静态分配，并假设输入输出操作的时间

9、忽略不计。现有一作业序列如下：配，并假设输入输出操作的时间忽略不计。现有一作业序列如下：作业号作业号进输入井时间进输入井时间要求计算时间要求计算时间要求主存量要求主存量申请磁带机数申请磁带机数申请打印机数申请打印机数18:0025分钟分钟15K1台台1台台28:2010分钟分钟30K0台台1台台38:2020分钟分钟60K1台台0台台48:3020分钟分钟20K1台台0台台58:3515分钟分钟10K1台台1台台12第第4 4章章 处理机调度处理机调度 假设作业调度采用先来先服务算法，优先分配主存的低地址区域且假设作业调度采用先来先服务算法，优先分配主存的低地址区域且不准移动已在主存中的作业，

10、在主存中的作业平分不准移动已在主存中的作业，在主存中的作业平分CPU时间，则作业调时间，则作业调度选中作业的次序是度选中作业的次序是_A_，如果把一个作业从进入输入井到得到计算，如果把一个作业从进入输入井到得到计算结果的时间定义为周转时间，则在忽略系统工作时间的情况下，最大的结果的时间定义为周转时间，则在忽略系统工作时间的情况下，最大的作业周转时间是作业周转时间是_B_，最小的作业周转时间是，最小的作业周转时间是_C_，作业的平均周转，作业的平均周转时间是时间是_D_，作业全部执行结束的时间是，作业全部执行结束的时间是_E_。供选择的答案供选择的答案 A： (1, 3, 2, 4, 5) (1

11、, 2, 3, 4, 5) (1, 3, 4, 2, 5) (1, 2, 4, 3, 5) BD： 30分钟分钟 36分钟分钟 40分钟分钟 44分钟分钟 55分钟分钟 64分钟分钟 E： 9:20 9:30 9:40 9:50A： B： C： D： E：13第第4 4章章 处理机调度处理机调度内存分配图内存分配图J115K空闲空闲85KJ115KJ360K空闲空闲25K空闲空闲15KJ360KJ420K空闲空闲5KJ230KJ420K空闲空闲5K空闲空闲45KJ230K空闲空闲70KJ510K空闲空闲90K8:00 8:20 8:30 9:00 9:10 9:1514第第4 4章章 处理机调

12、度处理机调度 8:00 8:20 8:30 8:35 9:00 9:10 9:15 9:30 J1J2J3J4J55分钟分钟15分钟分钟20分钟分钟15分钟分钟5分钟分钟周转时间：周转时间：J1(30分钟分钟)、 J2(55分钟分钟)、 J3(40分钟分钟)、 J4(40分钟分钟)、 J5(55分钟分钟)5分钟分钟5分钟分钟5分钟分钟15分钟分钟15第第4 4章章 处理机调度处理机调度4.6 实时系统调度方法实时系统调度方法4.6.1 实时系统的特点实时系统的特点 (1) 有限等待时间有限等待时间 (2) 有限响应时间有限响应时间 (3) 用户控制用户控制 (4) 可靠性高可靠性高 (5) 系

13、统出错处理能力强系统出错处理能力强4.6.2 实时调度算法的分类实时调度算法的分类 (1) 静态表格驱动类静态表格驱动类 (2) 静态优先级驱动抢先式调度算法类静态优先级驱动抢先式调度算法类 (3) 动态计划调度算法类动态计划调度算法类 (4) 尽力而为调度算法类尽力而为调度算法类16第第4 4章章 处理机调度处理机调度4.6.3 时限调度算法与频率单调调度算法时限调度算法与频率单调调度算法 开始时限开始时限starting deadline 结束时限结束时限ending deadline 时限调度算法所需要的相关输入信息：时限调度算法所需要的相关输入信息： (1) 任务就绪时间或事件到达时间

14、任务就绪时间或事件到达时间 (2) 开始时限开始时限 (3) 完成时限完成时限 (4) 处理时间处理时间 (5) 资源需求资源需求 (6) 优先级优先级17第第4 4章章 处理机调度处理机调度例例 设实时系统从两个不同的数据源设实时系统从两个不同的数据源DA和和DB周期性地收集数据并进周期性地收集数据并进行处理，其中行处理，其中DA的时限要求以的时限要求以30ms为周期，为周期， DB的时限要求以的时限要求以75ms为为周期。设周期。设DA所需处理时限为所需处理时限为15ms， DB所需处理时限为所需处理时限为38ms，则与，则与DA和和DB有关进程的事件发生时限（就绪时限）、执行时限以及结束

15、有关进程的事件发生时限（就绪时限）、执行时限以及结束时限如下图所示。时限如下图所示。进进 程程事件发生时限事件发生时限执行时限执行时限结束时限结束时限DA(1)01530DA(2)301560DA(3)601590DB(1)03875DB(2)7538150DB(3)1503822518第第4 4章章 处理机调度处理机调度 频率单调调度算法是一种被广泛用于多周期性实时处理频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。的调度算法。 频率单调调度算法的基本原理是频率越低（周期越长）频率单调调度算法的基本原理是频率越低（周期越长）的任务的优先级越低。的任务的优先级越低。 设任务周期为设

16、任务周期为T，任务的执行时间为，任务的执行时间为C，则使用频率单，则使用频率单调调度算法的必要条件是调调度算法的必要条件是CT。图图 4.12 时限调度算法的调度顺序时限调度算法的调度顺序15 30 45 60 75 90 105 130 tDA(1) DB(1) DA(2) DB(1) DB(1) DA(3) DA(4) DB(2) 19第第4 4章章 处理机调度处理机调度 设有设有A、B、C三个作业，执行情况如下表所示。请三个作业，执行情况如下表所示。请填写周转时间栏，并回答下列问题：填写周转时间栏，并回答下列问题： (1) 作业的平均周转时间是多少？作业的平均周转时间是多少？ (2) 采

17、用了什么作业调度算法？采用了什么作业调度算法？ 作业名作业名到达时间到达时间开始执行时间开始执行时间执行结束时间执行结束时间周转时间周转时间(小时小时)A10:0010:0012:00B10:1012:2513:25C10:2512:0012:2520第第4 4章章 处理机调度处理机调度(1) 作业的平均周转时间是作业的平均周转时间是2.42小时。小时。(2) 采用的作业调度算法是采用的作业调度算法是SJF。作业名作业名到达时间到达时间开始执行时间开始执行时间执行结束时间执行结束时间周转时间周转时间(小时小时)A10:0010:0012:002.00B10:1012:2513:253.25C1

18、0:2512:0012:252.0021 k个进程共享某种资源个进程共享某种资源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(k)+(U(1)+U(2)+U(k)m+k 因为已发生死锁，所以资源