《第3章处理机调度和死锁剖析》由会员分享，可在线阅读，更多相关《第3章处理机调度和死锁剖析（98页珍藏版）》请在金锄头文库上搜索。
1、2019/10/16,阜阳师范学院计算机与信息学院,1,第3章 处理机调度与死锁,3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 产生死锁的原因和必要条件 3.5 预防死锁的方法 3.6 死锁的检测与解除,2019/10/16,阜阳师范学院计算机与信息学院,2,3.1 处理机调度的基本概念,3.1.1 高级调度、中级调度、低级调度 3.1.2 调度队列模型 3.1.3 选择调度方式和调度算法的若干准则,2019/10/16,阜阳师范学院计算机与信息学院,3,2019/10/16,阜阳师范学院计算机与信息学院,4,3.1.1 高级、中级和低级调度,经历下述三级调度: 高
2、级调度（High Scheduling） 中级调度（Intermediate-Level Scheduling） 低级调度（Low Level Scheduling）,2019/10/16,阜阳师范学院计算机与信息学院,5,1. 高级调度,又称为作业调度、宏观调度或长程调度。用于决定把后备队列中的哪些作业调入内存，为他们分配必要的资源，并创建进程。,批处理系统 ： 分时系统 ： 实时系统 ：,需要作业调度,不需作业调度,不需作业调度,2019/10/16,阜阳师范学院计算机与信息学院,6,1. 高级调度,执行作业调度时，必须作出两个决定： 接纳多少作业每次接纳多少作业进入内存，取决于多道程序度
3、，即允许多少个作业同时在内存中运行。 接纳哪些作业应接纳哪些作业从外存调入内存，取决于所采用的调度算法。,2019/10/16,阜阳师范学院计算机与信息学院,7,2. 低级调度,通常也称为进程调度、微观调度或短程调度。进程调度是最基本的一种调度，在三种OS中都有。用于决定就绪队列中哪个进程应先获得处理机，并将处理机分配给选中的进程。,为实现进程调度，应具有如下三个基本机制： 排队器 分派器 上下文切换,2019/10/16,阜阳师范学院计算机与信息学院,8,2. 低级调度,进程调度可采用下述两种调度方式： 非抢占方式 抢占方式 抢占的原则有： （1）优先权原则 （2）短作业（进程）优先原则 （
4、3）时间片原则,2019/10/16,阜阳师范学院计算机与信息学院,9,3. 中级调度,中级调度又称为交换调度、中程调度或内存调度。 它按一定的算法将外存中已具备运行条件的进程换入内存，而将内存中处于阻塞状态的某些进程换出至外存。,运行,就绪,阻塞,挂起阻塞,挂起就绪,创建,退出,进程调度,中级调度,作业调度,调度的层次,2019/10/16,阜阳师范学院计算机与信息学院,11,3.1.2 调度队列模型,仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列模型,2019/10/16,阜阳师范学院计算机与信息学院,12,1. 仅有进程调度的调度队列模型,在分时
5、系统中就绪进程组织成FIFO队列形式，按时间片轮转方式运行。,2019/10/16,阜阳师范学院计算机与信息学院,13,2. 具有高级和低级调度的调度队列模型,2019/10/16,阜阳师范学院计算机与信息学院,14,3. 同时具有三级调度的调度队列模型,2019/10/16,阜阳师范学院计算机与信息学院,15,3.1.3 选择调度方式和调度算法的若干准则,面向用户的准则 周转时间短 平均周转时间T 平均带权周转时间 （W= T(周转)/Ts(CPU执行) 响应时间快 截止时间的保证 优先权准则,面向系统的准则 系统吞吐量高 处理机利用率好 各类资源的平衡利用,练习1,设有4个作业同时到达，每
6、个作业执行时间均为2h，它们在一台处理器上按单道方式运行，则平均周转时间为（ ） A. 1h B. 5h C. 2.5h D.8h,B,2019/10/16,阜阳师范学院计算机与信息学院,17,3.2 调度算法,3.2.1 FCFS与SJF/SPF调度算法 3.2.2 高优先权优先调度算法 3.2.3 基于时间片的轮转调度算法,2019/10/16,阜阳师范学院计算机与信息学院,18,3.2.1 FCFS与SJF/SPF调度算法,1. 先来先服务调度算法(FCFS) 按进程申请CPU（就绪）的次序,0 27 30 35,2019/10/16,阜阳师范学院计算机与信息学院,19,FCFS实例 下
7、表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，计算出各自的周转时间和带权周转时间。,FCFS（First Come First Serve),2019/10/16,阜阳师范学院计算机与信息学院,20,FCFS（First Come First Serve),0,1,1,1,1,101,100,1,101,102,100,100,102,202,199,1.99,2019/10/16,阜阳师范学院计算机与信息学院,21,FCFS的特点: FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业（进程） 比较有利于长作业，而不利于短作
8、业,FCFS（First Come First Serve),2019/10/16,阜阳师范学院计算机与信息学院,22,2. 短作业（进程）优先调度算法,4,4,1,7,6,2,12,10,2,14,11,5.5,18,14,3.5,9,2.8,4,4,1,9,8,2.67,18,16,3.2,6,3,1.5,13,9,2.25,8,2.1,2019/10/16,阜阳师范学院计算机与信息学院,23,2 . 短作业（进程）优先调度算法,SJF调度算法的优缺点： 优点： 有效降低作业的平均等待时间，提高系统吞吐量 缺点： (1) 对长作业不利 (2) 不能保证紧迫性作业（进程）的及时处理 (3)
9、不一定能真正做到短作业优先,2019/10/16,阜阳师范学院计算机与信息学院,24,3.2.2 高优先权优先调度算法,1. 优先权调度算法的类型 为照顾紧迫性作业，使之在进入系统后便获得优先处理，引入了最高优先权优先（HPF）调度算法。它分为两种： 非抢占式优先权算法 抢占式优先权调度算法,2019/10/16,阜阳师范学院计算机与信息学院,25,3.2.2 高优先权优先调度算法,2. 优先权的类型 静态优先权：在创建进程时确定的，在进程的整个运行期间保持不变,又称优先数。 动态优先权：在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变。,2019/10/16,阜阳师范学院
10、计算机与信息学院,26,3. 高响应比优先调度算法(HRRN),为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则可解决问题。见下式： 优先权=(等待时间+要求服务时间)/要求服务时间 响应时间/要求服务时间,3.2.2 高优先权优先调度算法,练习2,一个作业8：00到达系统，估计运行时间为1h。若10:00开始执行该作业，其响应比是（ ） A. 2 B.1 C.3 D.0.5,C,例题1,设有4个作业J1、J2、J3、J4，它们的到达时间和计算时间如表所示。若这4个作业在一台处理器上按单道方式运行，采用高响应比优先调度算法，试写出各作业的执行顺序、各作业的周转时间
11、及平均周转时间,解析：,优先权（响应比）=(等待时间+要求服务时间)/要求 服务时间响应时间/要求服务时间,例题2,在一个批处理系统中，有两个作业进程。有一个作业序列，其到达时间及估计运行时间如表所示。系统作业采用最高响应比优先调度算法，进程的调度采用短进程优先的抢占式调度算法,例题2,（1）列出各作业的执行时间（即列出每个作业运行的时间片段，如作业i的运行时间序列为10：00-10：40） （2）计算这批作业的平均周转时间。,2019/10/16,阜阳师范学院计算机与信息工程学院,32,J1,10:00,J4:20m,10:10 J2到达,J2,10:35 J1完成 J4进内存,分析：,J3
12、,J4,J5,10:55 J4完成 J3进内存,J1:10m,J1:25m,11:25 J2完成 J5进内存,J2:30m,J5:30m,11:55 J5完成,12:40 J3完成,J3:45m,例题3,有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用抢占式优先级调度算法，作业的运行情况如表所示，其中作业的优先数即为进程的优先数，优先数越小，优先级越高。,2019/10/16,阜阳师范学院计算机与信息学院,33,（1）列出所有作业进入内存的时间及结束的时间 （2）计算平均周转时间,2019/10/16,阜阳师范学院计算机与信息工程学院,34,J1,8:00,J1:2
13、0m,8:20 J2到达,J2,8:30,分析：,J3,J4,8:50 J2完成 J4进入,J1:20m,J2:10m,9:10 J1完成 J3进内存,J3:50m,J4:20m,10:00 J3完成,10:20 J4完成,J2:20m,2019/10/16,阜阳师范学院计算机与信息学院,35,3.2.3 基于时间片的轮转调度算法(RR),在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片的轮转式进程调度算法。在早期，分时系统中采用的是简单的时间片轮转法，进入90年代后，广泛采用多级反馈队列调度算法。,2019/10/16,阜阳师范学院计算机与信息学院,36,将系统中所有的就绪进程按
14、照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。 在一个时间片结束时，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。,一、时间片轮转算法,1. 基本原理,2019/10/16,阜阳师范学院计算机与信息学院,37,2. 时间片长度的确定,时间片长度变化的影响 过长退化为FCFS算法。 过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。 对响应时间的要求： T(响应时间)=N(进程数目)*q(时间片),一、时间片轮转算法,2019/10/16,阜阳师范学院计算机与信息学院,38,2019/10/16,阜阳师范学院计算机与信息学院,3
15、9,二、多级反馈队列调度算法,实施过程如下： （1） 应设置多个队列并为各个队列赋予不同的优先级。第一个最高，依次降低。该算法赋予各个队列中进程执行时间片的大小也不相同，优先权越高，时间片越短。,1. 调度算法,2019/10/16,阜阳师范学院计算机与信息学院,40,多级反馈队列调度算法,2019/10/16,阜阳师范学院计算机与信息学院,41,二、多级反馈队列调度算法,(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。如它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾。 (3）仅当第1（i-1）队列空闲时，才会调度第i队列中的进程运行
16、。,2019/10/16,阜阳师范学院计算机与信息学院,42,2. 多级反馈队列调度算法的性能,终端型作业用户 短作业优先 短批处理作业用户 周转时间较短 长批处理作业用户,二、多级反馈队列调度算法,2019/10/16,阜阳师范学院计算机与信息学院,43,补充作业,假如有四道作业，它们的进入时间和运行时间由下表给出，在单道程序环境下，分别填写先来先服务、短作业优先和RR（3）算法的完成时间、周转时间、带权周转时间、平均周转时间和带权平均周转时间。,2019/10/16,阜阳师范学院计算机与信息学院,44,2019/10/16,阜阳师范学院计算机与信息学院,45,第3章 处理机调度与死锁,3.3 实时调度 3.4 产生死锁的原因和必要条件 3.5 预防死锁的方法 3.6 死锁的检测与解除,2019/10/16,阜阳师范
