《第三章处理机调度与死锁G讲义资料》由会员分享，可在线阅读，更多相关《第三章处理机调度与死锁G讲义资料（58页珍藏版）》请在金锄头文库上搜索。
1、第三章 处理机调度与死锁,主要内容： 处理机的两级调度 作业调度 进程调度 死锁 什么是死锁 预防死锁。 避免死锁。 检测死锁。,第一部分 处理机调度,主要内容：两级调度：作业调度和进程调度的调度算法。 作业调度：从磁盘的众多的作业中选择作业进入 内存。 进程调度：进入系统中若干进程如何争夺cpu的控制权。 1. cpu的调度层级 作业调度：宏观调度（用户的观点） 进程调度：微观调度（系统的观点） 一，作业调度和进程调度的任务 1.作业调度的任务 (1) 从磁盘的后备作业中按一定的算法选择作业进入内存; (2) 建立相应的进程于就绪状态,使它们有资格获得cpu的 控制权; (3) 当作业执行完
2、成后,作善后处理工作,如:撤销JCB,回收资源等。,2.进程调度的任务 （1）按一定的算法将CPU分配某一就绪状态的进程，规定占用CPU的时间，或测试优先级； （2）当CPU被进程占用时，建立相应的运行环境，如：保护现场等。 二，两级调度的关系,作业录入：sploonig系统,作业调度,作业调度,进程调度,二. 作业调度的功能 记录进入系统的各作业的情况。 建立作业控制块jcb (job control block)。作业控制块记录了每个作业类型、状态、资源请求及分配情况 。 按调度算法从后备作业中挑选出若干作业投入运行。 为选中的作业分配主存和外设资源。 为选中的作业分配所需要的系统资源。
3、作业结束后作善后处理工作。 收回该作业所占用的全部资源，撤消作业控制块以及与该作业有关的全部进程。,作业控制块(JCB),每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，主要信息见右图。,调度性能的衡量 1. 调度算法设计时考虑的因素 与整体目标一致 批量系统:尽量增加系统作业的平均吞吐量,提高系统的效率. 分时系统:保证用户能忍受时间. 实时系统:保证及时响应和处理. 资源负载均匀 ,作业应能运行,特殊要求等。 考虑的调度原则 公平性:对用户要公平和满意,不能无故地拖延作业的运行. 平衡资源的使用:将I/O繁忙
4、的作业和CPU繁忙的作业搭配起来,尽量使资源都处于忙碌. 较大的流量:单位时间内,尽可多的为多个作业服务.保证系统的吞吐能力.,2. 调度性能的衡量 通常采用平均周转时间和平均带权周转时间衡量. (1)周转时间和平均周转时间 作业的周转时间ti：一个作业在系统中停留的时间. ti = tci-tsi tci:作业完成时间 tsi:作业进入输入井时间 n个作业的平均周转时间t: t越小调度性能越好; 系统吞吐量大, 资源利用率越高. (2)带权周转时间和平均带权周转时间 带权周转时间wi:周转时间/运行时间 作业在系统中相对等待时间,注：平均周转时间：用来衡量不同的调度算法对同一作业流的调度性能
5、。 平均带权周转时间：用来衡量某种调度算法对不同作业流的调度性能。,五. 作业调度算法 先来先服务调度算法 短作业优先调度算法 响应比高者优先调度算法 优先数调度算法 均衡调度算法 1.先来先服务调度算法（FCFS） 按作业到达输入井的先后次序，且满足资源要求挑选作业进行的调度。,例子 在一个多道程序系统中，有作业A,B,C,D,E；用户使用的空间100KB。各作业进入输入井的时间和要求运行的时间如下表： 根据达到输入井的先后次序和满足资源要求条件,4个作业的调度次序：AB D C E,先来先服务算法（0.1小时6分钟）,平均周转时间 t = (0.7+1+1.6+1.1+1.6)/5=1.2
6、(小时) 平均带权周转时间 w = (1+2+4+2.75+8)/5=3.55(小时),算法的优缺点： 优点：实现简单；算法具有一定的公平性。 缺点：当计算时间长的作业先达到而被选中时，可能使计算时间短的作业长期等待， 则周转时间长，平均周转时间增大，降低了系统的吞吐能力。,入内存时间（小时）,2.短作业优先调度算法 每次总是选择满足资源要求的作业优先调入内存，然后挑选要求运行时间最短的作业投入运行。 上例：短作业优先调度的次序：AB D E C,入输入井时间(小时),平均周转时间 t = (0.7+1+1.8+1.1+1.2)/5=1.16(小时) 平均带权周转时间 w = (1+2+4.5
7、+1.75+6)/5=3.25(小时),比先来先服务算法调度,t,w都下降了.,短作业优先调度算法的优缺点： 优点:提高了系统的吞吐能力. 缺点：不断地接受计算时间短的作业,会使计算时间长的作业长期等待,长作业用户不满意. 3.响应比高者优先调度算法 每一次计算每个作业的响应比,从满足资源的作业中挑选响应比高者优先调度. 注:该算法是先来先服务调度算法和短作业优先调度算法的折衷方案. 响应比=,等待时间,计算时间,例子:单道程序系统中,三个作业A,B,C达到输入井的时间及要求的运行时间,如下表:,从达到的时间9:30开始,计算A,B,C的响应比: A,B,C等待的时间分别:40分(9:30-8
8、:50),30分(9:30-9:00),0分: 第一遍 A的响应比=40/90分=4/9 B的响应比=30/24分=5/4 C的响应比=0/60分=0 应该调度B:周转时间 t=(9:30-9:00=30分=0.5小时)+0.4=0.9(小时) 带权周转时间w=0.9/0.4=2.25(小时) 第二遍:B结束.开始时间:9:54小时(9:30+24分(0.4*6=24分) A的响应比=64/90分=32/45 (9:54-8:50=64分) C的响应比=24/60分=2/5(9:54-9:30=24分) 应该调度A:周转时间 t=(9:54-8:50)+1.5=2.54(小时) 带权周转时间w
9、=2.54/1.5=1.69(小时),最后调度C:开始时间11:24小时(9:54+1.5小时) 周转时间 t=(11:24-9:30=1.54小时)+1=2.9(小时) 带权周转时间w=2.9/1=2.9(小时) 平均周转时间:T=(0.9+2.54+2.9)/3=2.11(小时) 平均带权周转时间:w=(2.25+1.69+2.9)/3=2.26(小时) 优缺点: 优点:既照顾了作业到来的先后次序,又考虑了要求系统服务时间的长短. 缺点:计算复杂,每调度一次,都要计算每个作业的响应比. 4.优先数调度算法 算法综合考虑的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设
10、置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。 优先数确定:,用户规定 系统规定,优先数=(等待时间)-要求运行的时间-16输出量。 输出量以行计. 算法优缺点: 优点:保证优先照顾运行时间短的作业;但也不会使运行时间长的长作业等待太久,而得不到运行的机会. 缺点:算法实现的困难,如何综合考虑各种因素之间的关系确定优先数。 5.均衡调度算法 依据作业对资源的要求分类,作业调度轮流地从不同类的作业中去挑选作业,尽可能地使得使用不同资源的作业同时执行. 优点:减少作业等待同类资源的时间,加快作业的执行. 缺点:算法实现复杂.,2,3 进程调度 一,进程调度的功能和
11、时机 1.进程调度的功能 记录和保持系统中所有进程有关情况和状态特征。 决定分配策略。 实施处理机的分配和回收。 2.进程调度时机 调度时机有如下几种情况: 正常终止 系统服务请求：如：请求I/O等； 异常终止：程序出错； 时间片到 可剥夺方式下，高优先级进程进入就绪队列,3.进程调度方式 非剥夺方式 让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把处理机分配给“重要而紧迫”的进程。 剥夺方式 当“重要而紧迫”的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。 三.调度用的进程状态变迁图,例:有一个分时系统进程状态变迁图如下:,运行,
12、等待,高优先就绪,低优先就绪,超时间片,其次选择500ms,请求I/O,I/O完成,首先选择100ms,1,2,3,4,5,要求分析:进程的可能状态，状态间的变迁的原因，调度策略和调度效果。,问：(1) 说明发生变迁3，2，4的原因是什么？ (2) 下列因果关系是否会发生？如果会发生，在什么情况下发生？ a. 21 b. 3 5 c. 4 2 d. 3 1 (3) 依据该系统的状态变迁图，叙述该系统的调度策略和调度效果。 解： (1) 发生变迁3的原因：一个运行的进程要请求 系统服务。 发生变迁2的原因：一个运行的进程用完了此轮 的时间片，但任务还未完成。 或者：系统采用剥夺式调度，一个更高优
13、先级 的进程进入就绪队列要求执行。,发生变迁4的原因：I/o完成的消息到来，等待队列中的一个进程获得该I/o设备，则它由等待状态变为就绪状态。 (2) a. 21 :是因果变迁关系。条件：当时间片到时， 高优先就绪队列为空。 b. 3 5 ：是因果变迁关系。条件：高优先就绪 队列为非空。 c. 4 2 :不是因果变迁关系。 d. 3 1 :是因果变迁关系。条件：高优先就绪队 列为空,低优先就绪队列为非空。 (3)调度策略:优先照顾I/O量大的进程,也适当的照顾了 计算量大的进程. 调度效果:平衡系统的负荷,将I/O繁忙的进程和计算繁忙的进程搭配使用不同的资源,使CPU和I/O设备并行性更合理一
14、些.资源的利用率更高.,四. 进程调度算法 先来先服务调度算法 优先级调度算法 时间片轮转调度算法 分级的调度算法 1.先来先服务调度算法 按进程进入就绪队列的先后次序选择进程占用CPU.直至它运行完毕,或因等待某一事件让出CPU为止. 优点:算法实现简单. 缺点:不考虑进程的其它要求.,2.优先级调度算法 预先确定各进程的优先级,系统把CPU分给就绪队列中优先级别高的进程. 关键是优先级的确定:静态优先级和动态优先级. (1) 静态优先级的确定 在进程创建时确定,确定后,在整个运行期间不能改变. 确定情况: a.直接取作业的优先级. b.根据进程要求的资源和程序运行的估计时间综合确定. 如:
15、进程要求资源越多,运算的时间愈长,优先级就低. c.基于进程的类型确定 系统进程的优先级高于用户进程的优先级. I/O繁忙的进程优先级高于CPU繁忙的进程优先级.保证CPU与I/O并行. 在分时OS中,前台进程的优先级高于后台进程的优先级.,优点:算法容易实现,系统开销小. 缺点:死板.不能精确地调度进程,可能导致低优先级的进程长期等待. (2) 动态优先级的确定 进程优先级在运行时可以调整. 确定: 进程优先级随占用CPU时间的延长而下降,随等待CPU时间的延长而上升. 当等待一外设的进程较多时,可提高使用该外设进程的优先级,使它尽快运行,以释放该外设,满足其它进程的服务. 优点:调度效果比较好. 缺点:算法实现困难.,例：已知p1，p2，p3，p4四个进程依次进入就绪队列，它们所需的CPU的时间和优先数如下表：,写出采用非抢占式的优先数调度算法选中的进程执行的次序；计算它们在就绪队列中的等待时间和平均等待时间。,执行次序：p3p2 p4p1 等待时间：p1：251237（秒） p2：01010 （秒） p3：0 （秒） p4：1
