处理机调度与死锁-(3)

《处理机调度与死锁-(3)》由会员分享，可在线阅读，更多相关《处理机调度与死锁-(3)（69页珍藏版）》请在金锄头文库上搜索。

1、第3章 处理机调度与死锁,3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测和解除,开 始,本章学习目标,处理机调度的基本概念 处理机调度算法 实时调度和多处理机调度 死锁问题及解决对策,返回本章首页,3.1 处理机调度的基本概念,3.1.1 高级、中级和低级调度 3.1.2 调度队列模型 3.1.3 选择调度方式和算法的准则,返回本章首页,3.1.1 调度的类型,一、调度的职能 (1) 记录系统中所有进程的有关情况 (2) 确定分配处理机的原则 (3) 分配处理机给进程

2、(4) 从进程收回处理机,返回本节目录,二、高级、中级和低级调度,1. 高级调度作业调度 (1) 接纳多少作业 (2) 接纳哪些作业取决于调度算法,返回本节目录,2. 低级调度进程调度,(1) 非抢占方式CPU不能被动剥夺 引起调度的因素： * 进程执行完毕，或发生某事件进程不能继续运行 * 进程因I/O请求而停止 * 进程通信或同步过程中执行了某种原语,返回本节目录,(2) 抢占方式(Preemptive Mode),抢占的原则： * 优先权原则 * 短作业优先原则 * 时间片原则,返回本节目录,3. 中级调度对换暂时不能运行的进程,中级调度的任务是挂起暂时不能运行的进程，以提高内存的利用率

3、和系统的吞吐量。,返回本节目录,3.1.2 调度队列模型,一、仅有进程调度的调度队列模型,返回本节目录,二、具有高级和低级调度的调度队列模型,1. 调度队列模型,2. 与进程调度队列模型的区别,(1) 就绪队列的形式 * 优先权队列 * 无序链表 (2) 设置多个阻塞队列,三、同时具有三级调度的调度队列模型,3.1.3 选择调度方式和算法的准则,一、面向用户的准则 1. 周转时间短 作业周转时间=外存等待时间+就绪队列等待时间+CPU执行时间+I/O操作时间 平均周转时间= 平均带权周转时间 2. 响应时间快提交请求开始到首次响应止 3. 截止时间的保证任务必须开始执行的最迟时间 4. 优先权

4、准则紧急任务优先执行,返回本节目录,二、面向系统的准则,1. 系统吞吐率高单位时间内完成的作业多 2. 处理机利用高40%90% 3. 各类资源平衡利用,3.2 调度算法,3.2.1 先来先服务和短作业优先调度算法 3.2.2 优先权调度算法 3.2.3 基于时间片的调度算法,下一页,3.2.1 先来先服务和短作业优先调度算法,一、先来先服务调度算法FCFS 按照进程进入就绪队列的先后顺序调度进程，到达得越早，其优先数越高。未遇到其他情况时，获得处理机的进程就一直运行下去。,二、(运行时间)短作业优先调度算法,1. 基本原理 2. 算法的缺点 (1) 对长作业不利 (2) 未考虑作业的紧迫性

5、(3) 时间是估计的，不一定真的最短,3.2.2 优先权调度算法,一、优先权调度算法的类型 1. 非抢占式优先权算法 最高优先级的就绪进程获得处理机之后，就一直运行下去(除非因自身的原因被阻塞，如要求I/O操作)，直至运行结束。 2.抢占式优先权算法 就绪队列中优先级高的进程可以随时取代正在运行的进程，投入运行。,二、优先权的类型,1. 静态优先权进程创建时确定 (1) 进程的类型(I/O进程、对换进程等) (2) 进程的资源需求(内存、执行时间等) (3) 用户要求(紧迫程度、支付费用等) 2. 动态优先权进程创建时确定,三、高响应比优先调度算法,1. 优先权的定义 2. 响应比 3. 算法

6、特点 (1) 对短作业有利 (2) 服务时间相同，等待时间越长，优先权越高 (3) 随着时间增加，长作业得到照顾,3.2.3 基于时间片的调度算法,一、时间片轮转法 所有就绪进程按先后次序排队，处理机总是优先分配给就绪队列中的第一个进程，并分配它一个固定的时间片（如100毫秒）。时间片时间到，同时未遇到任何阻塞时，进程就回到就绪队列的尾部。,二、多级反馈队列调度算法,根据进程的优先级设置多个就绪队列，第一个队列的优先级最高，队列之间的优先级依次降低。高优先级队列中的进程执行时间片短 当一个进程进入内存时，首先把它放到第一个队列的末尾，按FCFS原则等待调度。若在时间片内未执行完，将被放到第二个

7、队列的末尾；然后依次类推 仅当前面的队列为空时，才调度后面队列中的进程。,三、多级反馈队列调度算法的性能,1. 终端型作业 此类作业较短，只要在第一队列的时间片内完成，即可获得较好的满意度 2. 短批处理作业 用较短的时间即可完成 3. 长批处理作业 将依次在不同的队列中运行，不必担心长期得不到处理,3.3 实时调度,3.3.1 实现实时调度的基本条件 3.3.2 实时调度算法的分类 3.3.3 常用的几种实时调度算法,3.3.1 实现实时调度的基本条件,一、提供必要的调度信息 1. 就绪时间 2. 开始截止时间和完成截止时间 3. 处理时间 4. 资源要求 5. 优先级,二、系统的处理能力强

8、,二、系统的处理能力强 1. 单机系统 m个周期性任务，Pi为周期时间，Ci为执行时间 2. 多处理机系统(处理机数为N) 三、采用抢占式调度机制 四、具有快速切换机制 1. 对外部中断的快速响应能力 2. 快速的任务切换能力,3.3.2 实时调度算法的分类,一、非抢占式调度算法 1. 非抢占式轮转调度算法 响应时间：几秒几十秒 2. 非抢占式优先调度算法 响应时间：几百毫秒,二、抢占式调度算法(响应时间几十毫秒以下),1. 基于时钟中断的抢占式优先权调度算法 优先级高于当前任务的实时任务到达，但是在发生时钟中断时才剥夺当前任务的执行 2. 立即抢占的优先权调度算法 一旦出现外部中断，只要当前

9、任务未处于临界区，就立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务,3.3.3 常用的几种实时调度算法,一、最早截止时间优先算法EDF(Earliest Deadline First)算法 该算法根据任务的开始截止时间确定任务的优先级。截止时间越早，优先级越高。 系统中保持一个就绪队列，队列中的各任务按截止时间的早晚排序。 该算法既可用于抢占式调度，也可用于非抢占式调度。,二、最低松弛度优先调度算法,1. 基本原理 该算法根据任务的紧急(或松弛)程度确定任务的优先级。任务的紧急程度越高，优先级也就越高 系统中保持一个就绪队列，队列中的各任务按松弛度排序，松弛度最低的任务排在队列的最前

10、面。 该算法既主要应用于抢占式调度。,2. 松弛度的计算,松弛度的定义 松弛度的计算 任务A要求每20ms执行一次，执行时间10ms 任务B要求每50ms执行一次，执行时间25ms 图P84,3.4 多处理机系统中的调度,3.4.1 多处理器系统的类型 3.4.2 进程分配方式 3.4.3 进程(线程)调度方式,3.4.1 多处理器系统(MPS)的类型,MPSMultiProcessor System 一、紧密耦合MPS和松弛耦合MPS 1. 紧密耦合MPS 通过高速总线或高速交叉开关连接多个处理器，多个CPU共享主存储器和I/O设备，系统中的所有资源和进程由操作系统统一控制和管理 2. 松弛

11、耦合MPS 通过通道或通信线路连接多个计算机，每个计算机都有自己的存储器和I/O设备，都有自己的操作系统控制和管理本地资源和进程的运行(计算机网络),二、对称MPS和非对称MPS,根据处理器是否相同来划分。 1. 对称MPSSMPS 系统中的处理器在结构和功能上都相同 2. 非对称MPS 系统中有多种类型的处理器，它们的结构和功能各不相同。其中一个是主处理器，其余都是从处理器,3.4.2 进程分配方式,一、对称多处理器系统中的进程分配方式 1. 静态分配方式 进程从开始执行到执行结束，都被固定地分配到一个处理器。每个处理器有一个专用的就绪队列，被阻塞的进程再次就绪时，仍回到该队列的末尾。 2.

12、 动态分配方式 系统中可以只设置一个公共的就绪队列，其中的进程可以分配到系统中的任何一个处理器。,二、非对称MPS中的进程分配方式,此类系统一般采用主从式操作系统，即OS的核心驻留于主处理器中，而用户程序则在从处理器上，进程调度由主处理器执行。每当从处理器空闲时，就小向主处理器发送一个索求进程的信号，主处理器从公用就绪队列中进行进程调度,3.4.3 进程(线程)调度方式,一、自调度方式 1. 自调度机制 在系统中设置一个公共的进程(线程)就绪队列，所有的处理器空闲时，都可以自己到该队列中取得一个进程(线程)投入运行 (1) FCFS算法 (2) 最小优先数优先算法 (3) 抢占式最小优先数优先

13、算法,2. 自调度方式的特点,有任务的情况下处理机不会空闲 分布式调度 可以沿用单处理机环境下的就绪队列组方式织和进程调度方法 多处理机互斥共享单就绪队列引起的瓶颈 重新调度时线程迁移引起的低效性 线程切换频繁,二、成组调度,1. 基本原理 把一个进程中的一组线程分配到一组处理机上执行。其优点是： (1) 若一组线(进)程可以并行执行，就可以减少阻塞情况的发生，减少了切换频率，提高 了性能 (2) 一次调度为一组线程分配处理机，减少了调度频率，减少了系统开销,2. 为应用程序分配处理机时间的方法,1) 为所有的应用程序平均分配处理机时间 2) 为所有的线程平均分配处理机时间,三、专用处理器分配

14、,1. 基本原理 为一个应用程序的每个线程分配一个处理器，直到该应用程序执行完毕，才释放为该应用程序所分配的所有处理器。,2. 采用专用处理器分配方法的理由,1) 专用处理器分配方式的缺点 部分处理器的利用率可能不高 2) 仍然采用专用处理器分配方式的原因 (1) 在大规模(甚至几百个处理器)高度并行的系统中，单个处理器的利用率不那么重要 (2) 避免了线程切换，加速了程序运行,3.5 产生死锁的原因和必要条件,死锁(Deadlock)多个进程因竞争资源或进程推进顺序不当而造成的进程无法继续运行的现象(Deadly-Embrace) 3.5.1 产生死锁的原因 3.5.2 产生死锁的必要条件

15、3.5.3 处理死锁的基本方法,返回本章首页,3.5.1 产生死锁的原因,一、资源的类型 1. 剥夺性资源 2. 非剥夺性资源 二、竞争资源引起死锁 1. 竞争非剥夺性资源 2. 竞争临时性资源 临时资源是指由一个进程产生，被另一进程使用短暂时间后就不再有用的资源，这种资源也叫做消耗性资源。,临时资源使用实例,正确的进程推进顺序 P1: Release(S1); Request(S3); P2: Release(S2); Request(S1); P3: Release(S3); Request(S2); 死锁的进程推进顺序 P1: Request(S3); Release(S1); P2:

16、Request(S1); Release(S2); P3: Request(S2); Release(S3);,三、进程推进顺序不当引起死锁,进程推进顺合法 进程推进顺序非法,3.5.2 产生死锁的必要条件,同时具备下列四个必要条件，就会产生产生死锁： 1. 互斥条件 2. 不剥夺条件 3. 请求和保持条件 4. 环路等待条件,3.5.3 处理死锁的基本方法,一、预防死锁消除产生死锁的必要条件 二、避免死锁分配资源时防止进入不安全状态 三、检测死锁不预防死锁，出现死锁就解除 四、解除死锁与检测死锁配合使用,3.6 预防死锁的方法,3.6.1 预防死锁 3.6.2 系统安全状态 3.6.3 利用银行家算法避免死锁,返回本章首页,3.6.1 预防死锁,一、破坏“请求和保持”条件 进程运行之前必须提出要使用的全部资源，在该进程需要的资源末得到满足之前，不让它们投入运行；并且当资源一旦分配给某进程之后，就在该进程整个运行期间一直占有该资源。,二、破坏“不剥夺”条件,