成都信息工程学院：操作系统原理：os-4

1 操 作 系 统 | 调 度 与 死 锁 1 CUIT 徐虹 第四章调度与死锁 ?不同的OS，处理机管理的策略不同 ?衡量调度策略的指标 ?周转时间 ?吞吐率 ?响应时间 ?设备利用率 ?调度算法 ?死锁的概念和解决方案 操 作 系 统 | 调 度 与 死 锁 2 CUIT 徐虹 4．1调度的类型和模型 ?调度类型 ?高级调度 ?作业的状态及其转换 作业从输入到完成要经历提交，收容， 执行，完成四个阶段。 ?作业调度（宏观调度或高级调度） 2 操 作 系 统 | 调 度 与 死 锁 3 CUIT 徐虹 ?进程调度(微观调度或低级调度) ?进程调度程序 ?记录进程中所有进程的执行情况：状 态，优先级，所用资源情况等。 ?选择占用处理机的进程。 ?进行进程上，下文切换，分配处理机 给进程。 操 作 系 统 | 调 度 与 死 锁 4 CUIT 徐虹 ?进程调度的时机 ?正在执行的进程执行完毕。 ?运行中的进程提出I/O 请求。 ?执行某原语操作。 ?在可剥夺调度方式中，一个具有 更高优先数的进程进入就绪队列。 ?在分时系统中，分配给该进程的 时间片已用完 3 操 作 系 统 | 调 度 与 死 锁 5 CUIT 徐虹 ?进程调度方式 ?非剥夺方式 ?剥夺方式 ?选择性剥夺调度 为每个进程设置特征位Up 和Vp Up=1：本进程可剥夺其它进程 Up=0：本进程不能剥夺其它进程 Vp=1：可被剥夺 Vp=0：不能被剥夺 操 作 系 统 | 调 度 与 死 锁 6 CUIT 徐虹 ?交换调度（中级调度） 按照给定的原则和策略，将处于外存交 换区中的就绪状态或等待状态的进程调入 内存，或把处于内存就绪状态或内存等待 状态的进程交换到外存交换区中。 4 操 作 系 统 | 调 度 与 死 锁 7 CUIT 徐虹 调度和进程状态转换 操 作 系 统 | 调 度 与 死 锁 8 CUIT 徐虹 调度的层次 5 操 作 系 统 | 调 度 与 死 锁 9 CUIT 徐虹 ?调度队列模型 ?进程调度队列模型 ?作业和进程调度队列模型 ?三级调度队列模型 操 作 系 统 | 调 度 与 死 锁 10 CUIT 徐虹 6 操 作 系 统 | 调 度 与 死 锁 11 CUIT 徐虹 ?调度准则和算法评价 ?调度准则 ?面向用户 ?周转时间 ?响应时间 ?最后期限 ?可预测性 ?面向系统 ?吞吐量 ?处理机利用率 ?公平 ?平衡资源 ?强制优先级 操 作 系 统 | 调 度 与 死 锁 12 CUIT 徐虹 ?设计调度算法时考虑的因素 ?应与系统的整个设计目标一致。 ?系统资源的均衡使用。 ?平衡系统和用户要求。 大多数系统都根据用户的需要而采用兼 顾某些目标的简单调度算法。 7 操 作 系 统 | 调 度 与 死 锁 13 CUIT 徐虹 ?调度性能的衡量 批处理系统：平均周转时间或平均带权周 转时间 分时或实时系统：平均响应时间 ?周转时间： 作业i. Ti = Tei – Tbi = Twi + Tsi Tei: 完成时间Tbi:提交时间 Twi：等待时间Tsi：执行时间 有n个作业的作业流，其平均周转时间： T = 1/n [T1 + T2 + ……+Tn] 操 作 系 统 | 调 度 与 死 锁 14 CUIT 徐虹 ?带权周转时间 比较某种调度算法对不同作业流的调度性能。 Wi=Ti/Tsi 平均带权周转时间： W = 1/n [W1 + w2 + …… +Wn] 一般，总是T或W小的作业被选中，因为这样 资源利用率较高，用户也满意。 ?响应时间 ?截止完成时间 8 操 作 系 统 | 调 度 与 死 锁 15 CUIT 徐虹 例：假定有四个作业，它们的提交，运行，完成情况如下： 作业Tbi Tsi 开始完成Ti Wi 1 8：00 2. 00 8：00 10：00 2. 00 1. 00 2 8：30 0. 50 10：00 10：30 2. 00 4. 00 3 9：00 0. 10 10：30 10：36 1. 6 16. 00 4 9：30 0. 20 10：36 10：48 1. 3 6. 5 平均周转时间T=1.725(小时) 平均带权周转时间W=6.875 操 作 系 统 | 调 度 与 死 锁 16 CUIT 徐虹 4．2调度算法 ?先来先服务调度算法 ?原理 ?作业 ?进程 ?特点 利于长作业，利于CPU 繁忙型的作业。 9 操 作 系 统 | 调 度 与 死 锁 17 CUIT 徐虹 0 5 10 15 20 1 2 3 4 5 操 作 系 统 | 调 度 与 死 锁 18 CUIT 徐虹 ?最短作业（进程）优先法（SJF） ?原理：估计运行时间。 ?优点：SJF能有效地降低作业的平均等待 时间和提高系统吞吐量。 ?缺点： ?对长作业不利； ?不能保证紧迫性作业或进程会得到及时处理； ?不一定能真正做到短作业优先。 10 操 作 系 统 | 调 度 与 死 锁 19 CUIT 徐虹 0 5 10 15 20 1 2 3 4 5 操 作 系 统 | 调 度 与 死 锁 20 CUIT 徐虹 0 5 10 15 20 1 2 3 4 5 最 短 剩 余 时 间 （ S R T） 11 操 作 系 统 | 调 度 与 死 锁 21 CUIT 徐虹 ?最高响应比优先法（HRN） HRN是对FCFS和SJF方式的一种综合平衡。 响应比：R=（W+T）/T = 1+W/T T：估计执行时间 W：等待时间 W+T：响应时间 每当要进行调度时，系统计算每个作业的 响应比，选择其中R最大者投入执行。 操 作 系 统 | 调 度 与 死 锁 22 CUIT 徐虹 1 2 3 4 5 0 5 10 15 20 12 操 作 系 统 | 调 度 与 死 锁 23 CUIT 徐虹 ?时间片轮转法 ?原理 将CPU 的处理时间分成固定大小的 时间片，系统将所有就绪进程按先来先 服务的原则排成队列。每次调度时，把 CPU 分配给队首进程，令其执行一个时 间片，时间片用完后，若进程未结束， 则重新排入就绪队列尾部。 ?时间片的划分 时间片Q=R / Nmax R：响应时间Nmax：最大进程数 操 作 系 统 | 调 度 与 死 锁 24 CUIT 徐虹 13 操 作 系 统 | 调 度 与 死 锁 25 CUIT 徐虹 操 作 系 统 | 调 度 与 死 锁 26 CUIT 徐虹 0 5 10 15 20 1 2 3 4 5 14 操 作 系 统 | 调 度 与 死 锁 27 CUIT 徐虹 0 5 10 15 20 1 2 3 4 5 操 作 系 统 | 调 度 与 死 锁 28 CUIT 徐虹 虚时间片轮转法 15 操 作 系 统 | 调 度 与 死 锁 29 CUIT 徐虹 ?优先级法 ?静态优先级 ?作业的优先级确定原则： ?作业的紧急程度 ?作业类型 ?作业要求资源情况 操 作 系 统 | 调 度 与 死 锁 30 CUIT 徐虹 ?进程的优先级确定原则： ?按进程的类型赋予不同的优先级 ?用户进程类型：I/O 忙，CPU忙，I/O与 CPU 均衡 ?系统进程类型：调度进程，I/O 进程，中 断处理，存储各类等。 ?将作业的静态优先级作为它所属进程 的优先级。 ?特点：简单易行，系统开销小；不够 精确，可能出现优先级低的作业或进程， 长期得不到调度。 16 操 作 系 统 | 调 度 与 死 锁 31 CUIT 徐虹 ?动态优先级 把作业或进程的静态特性和动态特性 结合起来确定作业或进程的优先级，在 执行过程中，优先级不断变化。 ?确定进程动态优先级的原则： ?根据其占有CPU 时间的长短； ?根据就绪进程等待CPU 的时间长短 操 作 系 统 | 调 度 与 死 锁 32 CUIT 徐虹 ?改变进程优先级的方式： ?线形优先级调度策略 新创建的进程按FCFS方式排成就绪队列，优先级以 a 的速率增加，正在执行的进程优先级以b 的速率改变。 P（t）=a*（t1’- t1）+b*（t – t1’） ?非线形改变优先级规则 t1’ t a b t1 17 操 作 系 统 | 调 度 与 死 锁 33 CUIT 徐虹 ?多队列调度法 ?原理 多队列调度是根据作业的性质或类型 不同，将就绪进程队列再分为若干子队列， 各作业固定地分属于一队列，每个队列采 用一种算法。 操 作 系 统 | 调 度 与 死 锁 34 CUIT 徐虹 18 操 作 系 统 | 调 度 与 死 锁 35 CUIT 徐虹 ?实现方式 ?规定队列的优先级，优先级高的先获调 度。 例：按规定时间片运行前台作业，运行 完成或阻塞时，才转去调度后台作业。 ?为各队列分配一定的占用CPU时间比例。 例：前台：80%后台：20% 或：前台运行N个时间片，后台运行一个时间 片。 操 作 系 统 | 调 度 与 死 锁 36 CUIT 徐虹 ?多级反馈轮转法 ?设置多个就绪队列,每个队列赋予不同地 优先级。队列按FCFS原则排列。 ?各队列时间片不同。 ?当一个新进程进入内存后，首先放在第 一队列尾，按FCFS原则调度；如果该时 间片内未结束，转入第二队列尾；直到 最后的第N队列，在第N队列中便采取按 时间片轮转的方式执行。 ?仅当第i队列空闲时，才调度第i+1队列。 如有新进程进入优先级较高的队列，则 剥夺CPU执行新进程，旧进程放入原队 列尾 19 操 作 系 统 | 调 度 与 死 锁 37 CUIT 徐虹 操 作 系 统 | 调 度 与 死 锁 38 CUIT 徐虹 ?q=1 和q=2 i 20 操 作 系 统 | 调 度 与 死 锁 39 CUIT 徐虹 ?算法性能 ?终端型用户：在第一队列中完成，作 业短，交互型。 ?短批处理用户：周转时间较短，通常 三个队列即可完成。 ?长批处理作业用户：依次在前N-1个 队列中执行，在第N个队列中按轮转 方式运行。 操 作 系 统 | 调 度 与 死 锁 40 CUIT 徐虹 ?公平共享调度 ?用户的应用程序由一组进程（线程）构 成； ?用户关心的是应用程序的执行； ?需要基于进程组的调度方法。 21 操 作 系 统 | 调 度 与 死 锁 41 CUIT 徐虹 操 作 系 统 | 调 度 与 死 锁 42 CUIT 徐虹 ?各种调度算法性能比较 22 操 作 系 统 | 调 度 与 死 锁 43 CUIT 徐虹 操 作 系 统 | 调 度 与 死 锁 44 CUIT 徐虹 4．3 实时系统中的调度 ?对实时系统的要求 ?调度信息 ?就绪时间 ?开始截止时间和完成截止时间 ?处理时间 ?资源要求 ?优先级 23 操 作 系 统 | 调 度 与 死 锁 45 CUIT 徐虹 ?调度方式 ?抢占调度方式 ?非剥夺调度方式 ?具有快速响应外部中断的能力 ?快速任务分派 操 作 系 统 | 调 度 与 死 锁 46 CUIT 徐虹 ?实时调度算法 ?时间片轮转调度算法 24 操 作 系 统 | 调 度 与 死 锁 47 CUIT 徐虹 ?非抢占优先权调度算法 操 作 系 统 | 调 度 与 死 锁 48 CUIT 徐虹 ?基于时钟中断抢占的优先权调度算法 25 操 作 系 统 | 调 度 与 死 锁 49 CUIT 徐虹 ?立即抢占的优先权调度 操 作 系 统 | 调 度 与 死 锁 50 CUIT 徐虹 ?实时调度实例 ?具有开始截止时间的非周期实时任 务的调度 26 操 作 系 统 | 调 度 与 死 锁 51 CUIT 徐虹 操 作 系 统 | 调 度 与 死 锁 52 CUIT 徐虹 ?具有完成截止时间的周期性实时 任务的调度 27 操 作 系 统 | 调 度 与 死 锁 53 CUIT 徐虹 操 作 系 统 | 调 度 与 死 锁 54 CUIT 徐虹 4．4多处理机调度 ?多处理机系统（multiprocessor system） ?广义多处理机系统 ?狭义多CPU 系统 ?多处理机的OS系统 ?进程可在CPU间进行透明迁移。 ?并行地执行用户的几个程序（进程）。 ?提供系统结构重组能力，支持系统的降 级使用。 28 操 作 系 统 | 调 度 与 死 锁 55 CUIT 徐虹 ?多处理机系统的调度策略 ?进程调度 ?同构型多处理机系统 ?静态分配（Static Assignment） ?动态分配（Dynamic Assignment） ?自调度（Self-Scheduling） ?异构型多处理机系统 操 作 系 统 | 调 度 与 死 锁 56 CUIT 徐虹 ?自调度 系统中有一个公共的线程或进程的就 绪队列，当某个处理机空闲时，从队列 中摘取一个进程或线程运行。 ?自调度算法 ?FCFS ?最小优先数优先算法 ?抢占式最小优先数优先算法 ?自调度算法的缺陷 ?改进：设置局部就绪队列。 29 操 作 系 统 | 调 度 与 死 锁 57 CUIT 徐虹 ?成组调度（Group　Scheduling）或 协同调度 将同一进程的一组线程调度到几个 CPU 上同时执行。减少进程（线程）的 切换，使系统性能改善；减少调度频率， 从而减少了调度开销。 ?面向所有的应用程序平均分配处理机时间 ?面向所有的线程平均分配处理机时间 操 作 系 统 | 调 度 与 死 锁 58 CUIT 徐虹 30 操 作 系 统 | 调 度 与 死 锁 59 CUIT 徐虹 ?专用处理机分配 ?在应用程序执行期间，专为该程序的 每个线程分配一个处理机。 ?整机效率较高；完全避免进程或线程 间的切换。 操 作 系 统 | 调 度 与 死 锁 60 CUIT 徐虹 4．5死锁 ?死锁的概念 31 操 作 系 统 | 调 度 与 死 锁 61 CUIT 徐虹 操 作 系 统 | 调 度 与 死 锁 62 CUIT 徐虹 ?定义 当某进程提出资源申请后，使得系统 中一些进程处于无休止的阻塞状态，在无 外力作用下，永远不能再继续前进。 进程——资源图 32 操 作 系 统 | 调 度 与 死 锁 63 CUIT 徐虹 ?死锁的起因 例：有两个进程P、Q，系统仅有一台磁带机和打印机。 Pr1：P进程申请打印机A Qr1：Q进程申请磁带机B Pr2：P进程申请磁带机B Qr2：Q进程申请打印机A Pr3：P进程释放打印机A Qr3：Q进程释放磁带机B Pr4：P进程释放磁带机B Qr4：Q进程释放打印机A 操 作 系 统 | 调 度 与 死 锁 64 CUIT 徐虹 33 操 作 系 统 | 调 度 与 死 锁 65 CUIT 徐虹 操 作 系 统 | 调 度 与 死 锁 66 CUIT 徐虹 P1 . . . Request 80K bytes; Request 60K bytes; P2 Request 70K bytes; Request 80K bytes; . . . . . . . . . 可供分配的空间为200K 当两个进程都执行第二个请求时发生死锁 34 操 作 系 统 | 调 度 与 死 锁 67 CUIT 徐虹 ?产生死锁的原因： ?系统资源不足：为多道程序所共享 的资源不足； ?进程推进顺序非法。 操 作 系 统 | 调 度 与 死 锁 68 CUIT 徐虹 ?产生死锁的必要条件 ?互斥条件：某段时间内某资源只能由 一个进程使用。 ?请求和保持：进程因请求资源而阻塞 时，对已分配给它的资源保持不放。 ?不剥夺条件：资源在未使用完前，不 能被剥夺，由使用进程释放。 ?环路条件：发生死锁时，有向图必构 成一环路。 35 操 作 系 统 | 调 度 与 死 锁 69 CUIT 徐虹 ?处理死锁的方法 ?预防死锁 预防策略：破坏死锁产生的四个必要条 件，向进程施加适当的限制，使死锁在结 构上不可能发生。 ?避免死锁 避免策略：精心地分配资源，动态地回 避死锁。 ?检测死锁与恢复 检测与恢复：一旦发生死锁，系统不但能 及时检测出，还能采取积极措施加以解决。 操 作 系 统 | 调 度 与 死 锁 70 CUIT 徐虹 4．6死锁的预防和避免 ?死锁的预防 ?资源静态分配法 ?采用剥夺控制 ?破坏互斥性 ?资源顺序分配法 对系统的全部资源编号，并规定进程 申请资源时只能按升序进行。 36 操 作 系 统 | 调 度 与 死 锁 71 CUIT 徐虹 ?系统的安全状态 ?安全状态 系统能按某种顺序为每个进程分配其 所需的资源，使每个进程执行完毕。 安全序列：进程安全执行完的顺序。 操 作 系 统 | 调 度 与 死 锁 72 CUIT 徐虹 ?由安全状态向不安全状态的转换 例：系统中有10台磁带机，由A、B、C三进程共享， 运行一段时间后，情况如下： 进程名已分配数尚需申请数最大需求数 A2 2 4 B3 3 6 C 3 5 8 此时已分配8台，安全序列：A，B，C 如B申请一台，则不满足；如A申请一台就满足， 进行分配。 37 操 作 系 统 | 调 度 与 死 锁 73 CUIT 徐虹 例. 多项资源的安全序列 操 作 系 统 | 调 度 与 死 锁 74 CUIT 徐虹 38 操 作 系 统 | 调 度 与 死 锁 75 CUIT 徐虹 进入不安全状态 操 作 系 统 | 调 度 与 死 锁 76 CUIT 徐虹 ?银行家算法（Banker’s Algorithm） ?算法描述： public class state { int [] resource = new int[m]; int [] available = new int[m]; int [][] claim = new int[n][m]; int [][] alloc = new int[n][m]; } (a) global data structures 39 操 作 系 统 | 调 度 与 死 锁 77 CUIT 徐虹 if (alloc [i,*] + request [*] > claim [i,*]) { < error >; // --total request > claim } else if (request [*] > available [*]) { < suspend process >; } else { // --simulate alloc < define newstate by: alloc [i,*] = alloc [i,*] + request [*]; available [*] = available [*] - request [*] >; } 操 作 系 统 | 调 度 与 死 锁 78 CUIT 徐虹 if (safe (newstate)) { < carry out alloc >; } else { < restore original state >; < suspend process >; } (b) resource alloc algorithm 40 操 作 系 统 | 调 度 与 死 锁 79 CUIT 徐虹 public boolean safe (state S) { int [] currentavail = new int [m]; process [] rest = new process[<number of processes>]; currentavail = available; rest = {all processes}; possible = true; 操 作 系 统 | 调 度 与 死 锁 80 CUIT 徐虹 while (possible) { find a Pk in rest such that claim [k,*] - alloc [k,*] <= currentavail; if (found) { // simulate execution of P currentavail = currentavail + alloc [k,*]; rest = rest - {Pk}; } else possible = false; } return (rest == null); } (c) test for safety algorithm (banker's algorithm) 41 操 作 系 统 | 调 度 与 死 锁 81 CUIT 徐虹 ?优点： 资源利用率比静态资源分配法高， 又避免死锁。 ?缺点： 对资源分配过于保守；计算太多， 并且需知道对资源的最大需求量，不太 实际。 操 作 系 统 | 调 度 与 死 锁 82 CUIT 徐虹 4．7死锁的检测和解除 ?死锁的检测 ?进程资源图 在图中找一既非阻塞又非孤立的进 程节点Pi，如对某资源的请求能满足， 把请求边改为分配边，当Pi只有分配边 时，消去所有分配边，并释放占有的资 源。再选下一进程节点Pj，…，若能消 去所有边，那么该图是可完全简化的。 否则称为不可简化。 42 操 作 系 统 | 调 度 与 死 锁 83 CUIT 徐虹 ?死锁定理 ?引理：一个给定的进程——资源图的 全部化简序列导致同一不可简化图。 ?死锁定理：S是死锁状态，当且仅当 S的资源——进程图不是可完全化简 图。 ?死锁检测算法 操 作 系 统 | 调 度 与 死 锁 84 CUIT 徐虹 43 操 作 系 统 | 调 度 与 死 锁 85 CUIT 徐虹 ?死锁的恢复 ?删除法 ?删除策略：为解除死锁状态所需删除的进 程数最少，以及删除那些代价最小的进程。 ?衡量进程删除代价的依据：作业或进程的 优先级、作业类的预定代价、运行代价。 ?剥夺法 从一些进程那里剥夺出足够数量的资源，分 给死锁进程，使其解除死锁。被剥夺资源的进程 以请求资源的方式保留它们，以便于以后恢复运 行。 操 作 系 统 | 调 度 与 死 锁 86 CUIT 徐虹 ?本章重点 ?三级调度； ?调度算法； ?实时调度和多处理机调度； ?死锁的概念； ?银行家算法； ?死锁的检测和恢复。