《操作系统原理--课件、实验安排第3章处理机调度与死锁》由会员分享，可在线阅读，更多相关《操作系统原理--课件、实验安排第3章处理机调度与死锁（56页珍藏版）》请在金锄头文库上搜索。
1、第三章 处理机调度与死锁,3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 死锁问题的解决方法,低级调度,中 级 调 度,高级调度,高级调度,提交,收容,就绪,阻塞,就绪,执行,阻塞,内存,3.1 处理机调度的基本概念,高/中/低级调度 调度队列模型 调度方式和算法的选择准则,3.1.1 处理机调度的层次,1、高级调度（作业调度 / 长程调度 / 接纳调度） 多用于批处理系统，决定外存上处于后备队列中的哪些作业调入内存。 每次调度时要考虑： (1)接纳多少作业：取决于多道程序度 (2)接纳哪些作业：取决于调
2、度算法 作业调度运行频率低，几分钟一次,2、低级调度（进程调度/ 短程调度） 用来决定就绪队列中哪个进程应获得处理机，然后再由分派程序(Dispatcher)执行处理机分配操作。 进程状态：Ready Running 引起进程调度的原因有： 进程正常终止或异常终止 正在执行的进程因某种原因而阻塞（I/O请求） 分时系统中时间片用尽 当有一个优先级更高的进程就绪（可抢占式） 在进程通信中，执行中的进程执行了某种原语操作。如：wait/signal操作、Block原语、wakeup原语等 运行频率高，几十毫秒一次，算法不能太复杂，以免占用太多的CPU时间。,进程调度采用两种方式： 非抢占方式： 一
3、旦分配处理机，进程就一直执行，直至完成或发生某事件而被阻塞，不允许其它进程抢占处理机。 优点：简单、系统开销小，适合大多数批处理系统 缺点：无法满足紧急任务的需要，不适合实时系统 抢占方式： 允许调度程序根据某原则，暂停正在执行的进程，将处理机重新分配。 抢占原则：优先权原则 、短作业(进程)优先原则、时间片原则,3、中级调度（中程调度） 目的：为了缓解内存紧张问题，将那些暂时不能运行的进程调到外存上去等待。 当进程运行条件具备、且内存又空闲时，中级调度程序决定将外存上的哪些进程重新调入内存。 进程状态：Ready Ready suspend, Blocked Blocked suspend
4、运行频率介于高级调度和低级调度之间。,3.1.2 调度队列模型,3.1.3 调度方式和算法的选择准则,面向用户的准则 周转时间短评价批处理系统 响应时间快评价实时，分时系统 截止时间保证评价实时系统 优先权准则三种系统中皆适用,面向系统的准则 系统吞吐量高评价批处理系统 处理机利用率好针对大中型系统 各类资源的平衡利用对大中型系统,周转时间 (通常作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一)： 是指从作业被提交系统开始，到作业完成为止的这段时间间隔。 包括四部分： 等待作业调度时间(高级调度) 等待进程调度时间(低级调度) 执行时间 进程等待I/O操作完成时间,平均周转时间
5、：,ti: 作业周转时间，tci：作业完成时间，tsi: 作业提交（到达）时间,ti = tci-tsi,带权周转时间：,平均带权周转时间：,tr: 作业实际运行时间,响应时间(用来评价分时系统的性能，选择分时系统中进程调度算法的重要准侧之一)： 从用户通过键盘提交一个请求开始直至系统首次产生响应为止的时间。,响应时间包括三部分时间：从键盘输入的请求信息传送到处理机的时间、处理时间、响应信息回送终端的时间。,3.2 调度算法,先来先服务 短作业（进程）优先 高优先权先调度 时间片轮转 多级反馈队列,1、 先来先服务（FCFS）,可用于作业调度和进程调度,周转时间 = 完成时间 到达时间 带权周
6、转时间 = 周转时间 / 服务（运行）时间,0,1,1,101,101,102,102,202,1,100,100,199,1,1,100,1.99,优缺点：实现简单 有利于长作业（进程），不利于短作业（进程）。 有利于CPU繁忙型作业，不利于I/O繁忙型作业。,2、短作业 / 进程优先（SJF/SPF）,短作业优先（SJF） 从后备队列中选择估计运行时间最短的作业，调入内存运行。 短进程优先（SPF） 从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。 直到运行完成，或发生某事件而被阻塞，进程才会让出处理机非抢占式。 优点： 有效地降低了作业的平均等待时间，提高系统的吞
7、吐量。 缺点： 对长作业不利，有可能长期不被调度。 完全没考虑作业的紧迫程度（某些特殊的）。 用户做出的估计时间带有很大的主观性。,2.25,9,13,3.5,14,18,4,4,E,3.2,16,18,2,10,12,5,2,C,2.67,8,9,2,6,7,3,1,B,1.5,3,6,5.5,11,14,2,3,D,2.1,1,带权周转时间,8,4,周转时间,4,完成时间,SJF,2.8,1,带权周转时间,9,4,周转时间,4,完成时间,FCFS,4,服务时间,0,到达时间,平均,A,进程名,作 调 业 度 情 算 况 法,3、高优先权优先调度算法（HPF）,作业调度：从后备队列中选择若干
8、个优先权最高的作业装入内存。 进程调度：把处理机分配给就绪队列中优先权最高的进程 非抢占式优先权算法： 一旦分配处理机给优先权最高的进程，进程便一直执行直至完成，或发生某事件而被阻塞。 主要用于批处理系统和实时性要求不严的实时系统。 抢占式优先权算法： 一旦系统中出现一个新的就绪进程Pi，就将其优先权与正在执行的进程Pj进行比较，如果Pi Pj ，那么就做进程切换，使Pi投入运行。 常用于要求严的实时系统，以及对性能要求高的批处理和分时系统中。,关键：优先权的确定 优先权类型一：静态优先权 在进程创建时确定的，在进程整个运行期间保持不变。 通常根据进程类型、进程对资源的要求、用户要求来确定进程
9、优先权 简单易行，但不够精确，可能出现优先权低的进程长期得不到执行的情况。,优先权类型二：动态优先权 在进程创建时创立的优先权，可随进程的推进或等待时间的增加而改变。如等待时间长，优先权升高。,高响应比优先调度算法（FCFS和SJF的折中） 为每个进程引入动态优先权，随着等待时间增加优先权提高。,T作业估计运行时间（要求服务时间） W作业在后备队列中的等待时间,作业等待时间相同，则作业要求的服务时间愈短，优先权愈高，因而有利于短作业。 当要求的服务时间相同，则等待时间愈长，优先权愈高，因而实现了先来先服务。 长作业也能保证得到执行。,例2：下表说明了采用响应比高者(HRN)优先调度算法时上述作
10、业组合运行的情况。 表中单位：小时，并以十进制计,平均周转时间t=1.625 平均带权周转时间w=5.675,8.00,10.00,10.00,10.10,10.10,10.60,10.60,10.80,2.00,2.10,1.10,1.30,1,4.2,11,6.5,采用HRN算法时，这四个作业的执行次序为：J1，J3，J2，J4。之所以会是这样的次序，是因为该算法在一个作业运行完时要计算剩下的所有作业的响应比，然后选响应比高者去运行。例如，当J1结束时，J2、J3、J4的响应比计算如下： rp2 =1+作业等待时间执行时间 =1+(10.00-8.50)0.5 =1+3 rp3 =1+作业
11、等待时间执行时间 =1+(10.00-9.00)0.10 =1+10 rp4 =1+作业等待时间执行时间 =1+(10.00-9.50)0.20 =1+2.5,从计算结果可看出，J3的响应比最高，所以让J3先运行。当J3运行结束以及以后选中的作业运行结束时，都用上述方法计算出当时各作业的响应比，然后选出响应比高的去运行。,4、时间片轮转,特别适用于分时系统的抢占方式调度算法。 系统将所有的就绪进程按FIFO原则排成一个队列，将CPU分配给队首进程，执行一个时间片。在时间片内进程未完，则插入就绪队列未尾，CPU交给下一个进程。 时间片选择问题：固定时间片、可变时间片 与时间片大小有关的因素： 系
12、统响应时间、就绪进程个数、CPU能力,5、多级反馈队列,多级反馈队列调度算法的思想： 设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；在优先权愈高的队列中，为每个进程设置的执行时间片就愈小。 新创建的进程，首先被挂到第一优先级的队列，然后按 FCFS 原则排队等待调度。当轮到其执行时，如它能在设定时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列的末尾，最后一级队列采用时间片轮转法； 仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推；如果有优先权高的新进程到来，那么将抢占低级进程的处理机。,时间片 小 大,优先级 高 低,多级反馈队列调度算法的性能
13、 多级反馈队列调度算法不必事先知道各种进程所需的执行时间，能较好地满足各种类型用户(进程)的需要，是目前公认的一种较好的进程调度算法。 终端（交互）型作业用户 短批处理作业用户 长批处理作业用户,3.5 产生死锁的原因和必要条件,产生死锁的原因 产生死锁的必要条件,1、产生死锁的原因,死锁（Deadlock）： 是指两个或两个以上的进程在运行过程中，因争夺资源而造成的一种互相等待（谁也无法再继续推进）的现象，若无外力作用，它们都将无法推进下去。,例如，系统有5台打印机，进程A需要4台，进程B需要4台，进程AB并发执行，A已经占3台，B已经占2台，此时陷入死锁。,产生死锁的原因： 竞争资源 进程
14、间推进顺序非法,1、竞争资源引起进程死锁： 可剥夺性资源：CPU、RAM等； 非剥夺性资源：打印机、磁带机等； 竞争非剥夺性资源： 系统中配备的非剥夺性资源的数量不能满足诸进程运行的需要时，会使进程因争夺资源而陷入僵局。,永久性资源：打印机 临时性资源：进程通信中的消息、数据等 竞争临时性资源：,P1 Request (s3); Release(s1);,P2 Request (s1); Release(s2);,P3 Request (s2); Release(s3);,s1,P1,s2,P2,P3,s3,P1 Release(s1); Request (s3);,P2 Release(s2
15、); Request (s1);,P3 Release(s3); Request (s2);,2、进程间推进顺序不当引起死锁 进程推进顺序合法不会导致死锁 进程推进顺序非法可能会导致死锁,顺序合法,s1,P1,s2,P2,P3,s3,顺序非法,s1,P1,s2,P2,P3,s3,请求R2,请求R1,请求R1,请求R2,释放R1,释放R2,释放R2,释放R1,t,t,P1进程,P2进程,不 安全区,2、产生死锁的必要条件,互斥条件 一个资源一次只能被一个进程使用。 请求和保持条件（部分分配） 保留已经得到的资源，还要求其它的资源。 不可剥夺条件（不可抢占） 资源只能被占有者释放，不能被其它进程强
16、行抢占。 环路等待条件（循环等待） 系统中的进程形成了环形的资源请求链。,3.6 死锁问题的解决方法,预防死锁 避免死锁 检测与解除死锁,1、预防死锁,预防： 通过设置某些限制条件，破坏导致死锁的四个必要条件之一。 “互斥条件”由资源的性质决定。 摒弃“请求和保持”条件-一次性预分配法 在开始运行前（创建时），一次性分配给进程它所需的“全部”资源。 简单易实现，安全性高；资源浪费。,摒弃“不可剥夺”条件-先释放后申请分配法 当进程有新的资源请求时，如果得不到满足，要先释放原先占有的资源，待以后重新申请。 等价于此进程“被剥夺”了已经占有的资源。 实现比较复杂，系统代价很高。 摒弃“循环等待”条件-资源顺序分配法 把系统资源按类型排序，进程要
