操作系统与chap3复习 .ppt

第三章 处理机调度和死锁 作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历下述三级调度。 1. 高级调度/ 作业调度(job scheduling) 2. 低级调度/进程调度(process scheduling) 1）非抢占方式(Non-Preemptive Mode) 2）抢占方式(Preemptive Mode) 3. 中级调度(Intermediate-Level Scheduling) 存储器的对换功能 一、 调度的类型和层次 二、调度算法 1. 先来先服务（FCFS）调度算法(作业调度、进程调度) 2. 短作业（进程）优先(SJF/SPF)调度算法（作业调度、进程调度） 3. 高优先权调度（HPF）算法（作业调度、进程调度） 4. 高响应比优先(HRRF)调度算法(作业调度) 5. 时间片轮转（RR）算法（进程调度） 6. 多级反馈队列(MFQ)调度算法（进程调度） 几种常见调度算法比较见下表所示： FCFS RR SJ(P)F HPF HRRF MFQ 选择依据 Max[w] 常量 Min[s] 优先数 Max[w＋s/s] 调度方式 非抢占 抢占 非抢占 抢占 非抢占 抢占 非抢占 抢占 应用系统 批处理 分时系统 批处理 批处理/分时 批处理/分时 分时 吞吐量 不突出 时间片小，可能变低 高 不强调 高 不突出 响应时间 不突出 好 短进程响应时间好 较好 较好 较好 开销 最小 较小 较高 较高 较高 较高 对进程作用 不利于短作业 公平对待 不利于长作业(进程) 良好的均衡 良好的均衡 可能偏爱I/o繁忙型作业 “饥饿” 无 无 可能 可能 无 可能 几种常见调度算法的比较 三、常用的几种实时调度算法 根据确定实时任务优先权方法的不同，可形成以下两种常用的实时调度算法： 1. 最早截止时间（EDF）优先算法。EDF算法如何确定任务的优先权？或者说它是如何保证满足各任务对截止时间的要求的。 2. 最低松弛度优先（LLF）算法。LLF算法如何确定任务的优先权？在什么情况下，一个进程应抢占被另一个进程占用的CPU。 四、死锁的基本概念 1. 死锁的定义：多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。 2. 产生死锁的原因 （1）竞争资源 （2）进程推进顺序非法 3. 产生死锁的必要条件 (1) 互斥条件(Mutual Exclusion condition) (2) 请求和保持条件(Request and hold condition) (3) 不剥夺条件(Non preemptive condition) (4) 环路等待条件(Loop waiting condition) 五、处理死锁的基本方法 1. 预防死锁 摒弃“请求和保持”条件 摒弃“不剥夺”条件 摒弃“环路等待”条件 2. 避免死锁 银行家算法避免死锁 3. 死锁的检测与解除 当系统资源都为单体资源类时，若图中出现环路，则必存在死锁。 在系统资源为多体资源类时，图中出现环路，系统不一定死锁。 系统存在死锁，则资源分配图中一定出现环路。 4.鸵鸟策略 利用资源分配图，死锁定理进行死锁判定。 资源分配策略 死锁预防 死锁避免 死锁检测和解除 很保守；对资源不做调配使用 介于预防和检测间，安全状态 非常开放；申请资源就分配，但定期检测 采用的方式 一次性分配所有资源 抢占式资源分配 资源编号，按序分配 至少找一个安全序列 定期调用检测算法，是否出现死锁 主要优点 适用单一突发进程 无需抢占 最容易实现 适用资源状态便于保存和恢复的情况 适用于编译时强行检查 运行无需计算 无需抢占 从来不延误进程的开始执行，便于联机处理 主要缺点 设备利用率低，效率低 延误进程开始时间 抢占动作比实际需要次数多 占用没有太多用处的资源 不允许增加对资源的申请 须知道以后对资源申请情况，实现困难 进程可能被阻塞很长时间 丧失固有的抢占性。 执行检测算法需要一定的CPU开销。 几种处理死锁方法的比较 典型问题分析 1. n个进程共享m 个同类资源，若每个进程都需要用该资源，而且每个进程对该类资源的最大需求量之和小于m+n。说明该系统不会因竞争该类资源而阻塞。 2. 当前运行的进程（ ），将引发系统进行进程调度。 A. 执行了一条转移指令 B.要求增加主存空间，经系统调用银行家算法进行测算认为是安全的 C.执行了一条I/O指令 D.执行程序期间发生了