操作系统第三章PPT.

《操作系统第三章PPT.》由会员分享，可在线阅读，更多相关《操作系统第三章PPT.（63页珍藏版）》请在金锄头文库上搜索。

1、* 1 第三章第三章 处理机调度和死锁处理机调度和死锁 * 2 处理机调度的层次处理机调度的层次 n 处理机调度 系统中有多道程序和多个进程时，系统按某 种算法，动态地把处理机分配个某个就绪队 列中的进程的过程 n 调度的三个层次 高级调度 中级调度 低级调度 * 3 高级调度高级调度 n 又称作业调度、长程调度、接纳调度 n 作业和作业步 作业job包含程序、数据和作业说明书 系统根据作业说明书对程序的运行进行控制 作业步job step：作业的加工处理步骤 一个作业包含托干个作业步。 如编译、连接、运行等 * 4 作业调度作业调度 n 作业调度的主要任务是完成作业从后备状态到执 行状态和从

2、执行状态到完成状态的转变。 n 作业调度功能 记录已进入系统的各作业的情况（JCB， Job Control Block）； 按一定的调度算法，从后备作业中选择一 个或几个作业进入系统内存； 为被选中的作业创建进程，并且为其申请 系统资源； 作业加束后作善后处理工作。 * 5 作业控制快作业控制快JCBJCB n 为管理和调度作业，为每个作业设置的控制块 n 是存放作业控制和管理信息的数据结构 * 6 高级调度特性高级调度特性 n 接纳作业数 内存驻留数 太多，周转时间T长 太少，系统效率低 n 接纳策略 决定接纳哪些作业 即采用何种调度算法 FCFS、短作业优先等 * 7 低级调度低级调度

3、n 又称进程调度，短程调度 n 调度对象是进程 n 主要是由分派程序（Dispatcher）分配处理机 n 进程调度功能 保护现场 入就绪队列算法实现 处理机分派 恢复现场 * 8 进程调度的三个基本机制进程调度的三个基本机制 n 排队器 负责将就绪进程某种策略排队 n 分派程序 按照进程调度策略，从就绪进程中取出进程 ，进行上下文切换，分配处理机给进程 n 上下文切换机制 当调度新的进程执行时，保存当前执行进程 的上下文，装入即将运行进程的上下文 * 9 调度分派结构调度分派结构 pcb1 scheduler suspwakeupreceive pcb2pcb3pcb4 dispatcher

4、 cpu Ready-q pcb5 * 10 pcb2 scheduler suspwakeupreceive pcb5pcb3pcb4 dispatcher cpu Ready-q pcb1 * 11 进程调度方式进程调度方式 n 非抢占方式 一旦处理机分配后，直到进程完成或自愿放 弃处理机 简单，实时性差 (如win31) n 抢占方式 时间片原则 优先权原则 短作业优先原则 * 12 中级调度中级调度 n 又称中程调度 为提高系统吞吐量和内存利用率 引入进程的内/外存对换功能 换出时，进程为挂起或就绪驻外状态 由中程调度决定调度哪些就绪进程入内存 * 13 调度队列模型调度队列模型 n

5、仅有进程调度的队列模型 就绪队列CPU 阻塞队列 交互用户 时间片完 进程调度 进程完成 等待事件 事件出现 * 14 调度队列模型调度队列模型 n 具有高/低级模型 就绪队列 CPU 阻塞队列 时间片完 进程调度 进程完成 等待事件1 事件1出现 后备队列 阻塞队列 等待事件2 事件2出现 作业调度 * 15 具有三级调度具有三级调度 就绪队列CPU 就绪、挂起队列 时间片完 进程调度 进程完成 后备队列 阻塞、挂起队列 事件出现 作业调度 阻塞队列 等待事件 挂起 事件出现 中级调度 交互型作业 * 16 选择调度方式和算法的准则选择调度方式和算法的准则 n 面向用户的准则 n 面向系统的

6、准则 * 17 面向用户的准则面向用户的准则 n 周转时间短，常用于批处理系统 作业从提交 完成的时间.分为： 驻外存等待调度时间 驻内存等待调度时间 执行时间 阻塞时间 平均周转时间 Ti i进程的周转时间 平均带权周转时间 Ts 系统的服务时间 * 18 面向用户的准则面向用户的准则 n 响应时间快（交互性作业） 键盘提交请求到首次响应时间 输入传送时间 处理时间 响应传送时间 n 截止时间的保证（实时系统） n 优先权准则 即需要抢占调度 * 19 面向系统的准则面向系统的准则 n 吞吐量高 对于批处理：单位时间完成作业数 n 处理机利用率好 特别于大中型多用户系统 n 各类资源的平衡利

7、用 内存、外存、I/O设备等 * 20 调度算法调度算法 n 是一个资源分配问题 n 根据系统的资源分配策略所规定资源分配算法 n 典型算法 先来先服务 短作业优先 高优先权优先调度 时间片轮转调度 * 21 先来先服务先来先服务FCFSFCFS n 简单，有利于长作业 即CPU繁忙性作业 注意作业C的带权周转时间 进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间 A010111 B110011011001 C21101102100100 D31001022021991.99 * 22 短作业优先调度算法短作业优先调度算法 n 短作业进程优先SJ(P)F 提高了平均周转时间和平均

8、带权周转时间， 从而提高了系统吞吐量 对长作业不利，有可能得不到服务 不易确定作业完成时间 * 23 FCFSFCFS和和SJFSJF比较比较 进程名 A B C D E平均 到达时间 0 1 2 3 4 服务时间 4 3 5 2 4 FCFS完成时间 4 7 12 14 18 周转时间 4 6 10 11 149 带权周转时间 1 2 2 5.5 3.52.8 SJF完成时间 4 9 18 6 13 周转时间 4 8 16 3 98 带权周转时间 1 2.67 3.1 1.5 2.252.1 * 24 高优先权优先调度算法高优先权优先调度算法 n 优先权调度算法类型 非抢占式优先权算法 当前

9、运行进程不可被抢占 当要调度新的进程时按优先权调度 抢占式优先权算法，实时性更好 如果出现优先权更高的进程，则中止当前进程， 并将处理机分配给优先权高的进程 * 25 优先权类型优先权类型 n 静态优先权 进程优先权在整个运行期不变 确定优先权依据 进程类型、进程对资源的需求、用户需求。 简单，但低优先权作业可能长期不被调度 n 动态优先权 如：优先权随执行时间而下降，随等待时间 而升高 可用响应比Rp作为优先权 Rp =（等待时间服务时间）/服务时间 即：Rp=（tw+ts）/ts 优点：长短兼顾 缺点：需计算Rp * 26 高响应比优先算法高响应比优先算法 响应比Rp=（tw+ts）/ts

10、 短作业Rp大 ts（要求服务时间）相同的进程间相当于FCFS。 长作业等待一段时间仍能得到服务。 * 27 基于时间片的轮转调度算法基于时间片的轮转调度算法 n 多运用于分时系统中 n 两种策略 时间片轮转 多级反馈队列调度 * 28 时间片轮转时间片轮转 n 系统根据按时间片轮流调度进程 n 时间片大小的确定 太大：退化为FCFS 太小：系统开销过大 n 系统对进程的响应时间 T=nq； q为时间片,n为就绪队列中进程的数 目； n 系统的处理能力 应保证一个时间片处理完常用命令 * 29 多级反馈队列调度多级反馈队列调度 n 设置多个就绪队列，为每个队列设定不同的优先 级 第一个队列优先

11、级最高，其他依次递减 优先级越高的队列、每个时间片越短 第 i+1个队列的时间片长是第i个队列的2倍 n 新进程进入内存后，首先加入第一队列队尾，按 FCFS等待调度 第一轮结束后，若进程未结束，则加入第二 队列，依此类推 n 仅当第一队列空闲时，才会调度第二队列进程运 行，依此类推 * 30 就绪队列1 至CPU S1 就绪队列2 S2 至CPU 就绪队列3 S3 至CPU 就绪队列n Sn 至CPU 时间片：S1S2S3 多级队列反馈调度算法多级队列反馈调度算法 * 31 多级队列反馈调度算法特点多级队列反馈调度算法特点 n 长、短作业兼顾，有较好的响应时间 n 短作业一次完成； n 中型

12、作业周转时间不长； n 大型作业不会长期不处理 * 32 实时调度实时调度 n 实现实时调度的基本条件 提供必要的调度信息 就绪时间、开始/完成截止时间、处理时间、资源 要求、优先级； 系统处理能力强 满足限制条件 m:周期性实时任务 Ci:处理时间 Pi:周期时间 N:处理器数目 * 33 实现实时调度的基本条件实现实时调度的基本条件 n 采用抢占调度方式 剥夺方式 非剥夺方式 实现简单 一般实时任务较小，以及时放弃CPU n 具有快速切换机制 具有快速响应外部中断能力。 快速任务分派 * 34 实时调度算法的分类实时调度算法的分类 n 非抢占式调度算法 时间片轮转 秒级 非抢占优先权（协同

13、） 秒毫秒级 n 抢占式调度算法 时钟中断抢占优先权 毫秒级 基于抢占点抢占 立即抢占毫秒微秒级 只要不在临界区即抢占（中断引发） * 35 进程1进程2进程n实时进程 调度时间 实时进程要求调度调度实时进程运行 a 非抢占轮转调度 当前进程实时进程 实时进程要求调度当前进程运行完成 b 非抢占优先权调度 调度时间 * 36 c 基于时钟中断抢占的优先权抢占调度 当前进程实时进程 实时进程要求调度 抢占时刻（其它中断） b 立即抢占优先权调度 当前进程实时进程 实时进程要求调度时钟中断到达时 调度时间 调度时间 * 37 常用的几种实时调度算法常用的几种实时调度算法 n 最早截止时间优先EDF

14、（earliest deadline first)算法 根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高 可以是抢占式或非抢占式 * 38 最早截止时间优先最早截止时间优先EDFEDF例例 1342 134 2 1234 t 开始截止时间 任务到达 任务执行 EDF算法用于非抢占调度方式 * 39 最低松弛度优先最低松弛度优先LLFLLF算法算法 n 松弛度 若A进程需在200ms时完成，其本身运行需要100ms，当 前时刻是10ms，则A的松弛度为：2001001090 主要用于可抢占的调度方式中 例：A的执行周期为20ms,执行时间10ms B的执行周期为50ms,执行时间2

15、5ms A1A2A3A4 A5 A6A7A8 B1B2B3 0 20 406080100120140160 t 图311 A/B任务每次必须完成的时间 * 40 最低松弛度优先最低松弛度优先LLFLLF算法算法 A1(10) A2(10)A3(10)A4(10) t 01020304050607080 t1=0 B1(20)B1(5) B2(15) B2(10) t1t2t3t4t5t6t7t8 * 41 进程死锁进程死锁 n 系统中的进程无法进一步推进 * 42 产生死锁的原因和必要条件产生死锁的原因和必要条件 n 产生死锁的原因 竞争资源引起死锁 进程推进顺序不当引起死锁 * 43 竞争资源引起死锁竞争资源引起死锁 n 可剥夺（CPU、内存，）和非剥夺性（打印机， 磁带机）资源 n 竞争非剥夺性资源可造成死锁 n 竞争临时性资源 由一个进程产生