第3章处理机调度与死锁祥解.ppt

一、进程调度方式: 1、 非抢占方式:分配给它则一直拥有直到放弃（主动/被动） 特点: 优—实现简单,系统开销小→适用于批处理系统. 缺—不满足紧急任务要求(立即执行)→不适于实时系统. 2、抢占方式：现行进程的CPU可以被另一进程剥夺(符合原则) 抢占原则:时间片原则,优先权原则,短作业(进程)优先原则等 资源分配图的化简 3.死锁检测的实现：（自学） DS 算法 二、 死锁的解除 1．剥夺资源： 非死进程之资源?死锁进程。 2．撤消死锁进程（全部/逐个）： 寻求最小进程数/最小撤消代价方法。 3．挂起死锁进程： 负荷减轻，资源富余再解挂。 图 3-21 付出代价最小的死锁解除方法 采取增量方式讲解 采取增量方式讲解 采取增量方式讲解 采取增量方式讲解 采取增量方式讲解 采取增量方式讲解 五．进程调度的实现： 调度因素，算法，就绪队列的组织 1. 确定引起进程调度的因素 。执行完毕或因故不能继续运行 。I/O请求而暂停执行 。因原语操作而阻塞如：Ｐ、BLOCK、WAKEUP、SUSPEND等 。可剥夺方式中，进程进入就绪队列 。分时系统，时间片用完 2. 调度队列：就绪队列 　　　组成：树，链表～算法 3. 分派程序：CPU-进程（选择进程为调度之功能） 保存现场（前P）　布置现场（新调P） 注意：有些OS 将CPU分派功能合并于调度程序中。 3.4 实 时 调 度 3.4.1 实现实时调度的基本条件 1. 提供必要的信息 就绪时间。 (2) 截止时间：开始、完成。 (3) 处理时间。 (4) 资源要求。 (5) 优先级：绝对，相对 。 2. 系统处理能力强 单机系统： eg.周期=50ms, 6个时实任务，处理时间各为10ms 多机系统： 3、采用抢占式调度机制=硬实时任务 4、具有快速切换机制 对外部中断的快速响应能力 快速的任务分派能力 3.3.2 实时调度算法的分类 1. 非抢占式调度算法 非抢占式轮转调度算法：群控 (2) 非抢占式优先调度算法：较紧急—高优 2. 抢占式调度算法 基于时钟中断的抢占式优先权调度算法。 (2) 立即抢占的优先权调度算法。 3.3.3 常用的几种实时调度算法 1. 最早截止时间优先即EDF(Earliest Deadline First)算法 (1)非抢占调度方式----非周期实时任务,开始截止时间 (2)抢占调度方式----周期实时任务,完成截止时间 图 3-8 A和B任务每次必须完成的时间 松弛度=必须完成时间-本身运行时间-当前时间 2. 最低松弛度优先算法 (LLF---- Least Laxity First) 完成截止时间 图 3-9 利用ELLF算法进行调度的情况 指多个进程在运行过程中因争夺资源而造成的一种僵局（互阻-等待永不发生的事情）。 若无外力作用，死锁中的进程都无法向前推进 死 锁 产生 解决 预防 避免 解除 死锁 原因 必要条件 3.5 产生死锁的原因和必要条件 3.5.1 产生死锁的原因 竞争资源 (2) 进程间推进顺序非法 1. 竞争资源引起进程死锁 可剥夺 资源分类 非剥夺性资源 永久性资源 临时性资源 死锁 * 2. 进程推进顺序不当引起死锁 1) 进程推进顺序合法 2) 进程推进顺序非法 3.5.2 产生死锁的必要条件 互斥条件 (2) 请求和保持条件 (3) 不剥夺条件 (4) 环路等待条件 3.5.3 处理死锁的基本方法 预防死锁 (2) 避免死锁 (安全性检查) (4) 解除死锁 (检测死锁) 3.6 死锁的预防 3.6.1 预防死锁 分析四个必要条件： (1)互斥条件 (2) 请求和保持条件 (3) 不剥夺条件 (4) 环路等待条件 不可破且要保证 三种预防方法 出发点：通过破坏四个必要条件之一。 1. 摒弃“请求和保持”条件 目标：请求时不保持；保持时不请求。 （1）静态分配-?完全分配：所需资源一次申请完。