第04章 进程调度与死锁.pptVIP

软件学院软件基础教研室 计算机组成和操作系统 第四章 进程调度与死锁 进程调度类型和准则 进程调度算法 死锁的基本概念 死锁的预防与避免 死锁的检测与解除 1 进程调度 1.1 为什么需要进程调度 在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。 这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。 分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。 1 进程调度 1.2 进程调度要解决的问题 Rule：按什么原则分配CPU —进程调度算法 When：何时分配CPU —进程调度的时机 1.3 处理机调度 处理机是计算机系统中的重要资源，处理机调度可分成三个层次： 高级调度 中级调度 低级调度 1.3.1 高级调度 高级调度也称为作业调度或宏观调度，将外存作业调入内存，创建PCB等，插入就绪队列。 1.3.2 中级调度 为提高系统吞吐量和内存利用率而引入的内- 外存对换功能（换出时，进程为挂起或就绪驻外状 态）。 1.3.3 低级调度(进程调度) 选择就绪进程或线程进入运行状态，低级调度 的时间尺度通常是毫秒级的。 1.4 进程调度的目的 控制和协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。 1.5 进程调度的方式 非剥夺方式(非抢占方式) 一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。 剥夺方式(抢占方式)： 当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程 剥夺原则有：优先权原则、短进程优先原则、时间片原则等。 1.6 进程调度性能衡量的指标 响应时间 周转时间 处理机的利用率 截止时间（实时系统） 系统吞吐量 公平（避免“饿死”） 各类资源的平衡利用率 …… 1.7 进程调度的时机 进程退出 进程阻塞 时钟中断 高优先级进程抢占处理器 在进程通信中，执行中的进程执行了某种原语操作，例如：P操作。 1.8 进程调度算法 调度算法实际上是一个资源分配的问题。 先来先服务(FCFS)算法 短作业（进程）优先调度算法 最高优先权优先调度算法 时间片轮转法 多级反馈队列 2 死锁的基本概念 2.1 死锁的定义 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，出现相互的永久“阻塞”,如无外力作用，这组进程将永远不能继续运行。 2.2 死锁产生的原因 系统的资源数量不足 进程调用的顺序不当 现实生活中的死锁现象 计算机系统中的死锁实例 进程P1 进程P2 申请打印机 申请扫描仪 申请扫描仪 申请打印机 使用 使用 …… …… …… …… 2.3 死锁产生的必要条件 如果以下四个条件同时满足，则会引起死锁 互斥 资源只能被进程互斥的访问，即资源为临界资源。 请求和保持 占有资源的进程可以请求新的资源。 不可剥夺 进程已经获得了资源，在它使用完毕前，不能被剥夺，只能使用完毕后自己释放。 循环等待 至少有2个或以上进程构成循环链，每个进程都在等待由循环链中下一个成员占有的资源。 2.4 处理死锁的基本策略 忽略该问题 例如：鸵鸟算法 算法思想：对死锁视而不见 理由：死锁极少发生，预防死锁的代价太高 UNIX和Windows采用这种方法 这是方便性与正确性的平衡 检测并恢复 让死锁发生，然后检测它们，再采取行动。 通过仔细地分配资源动态地避免 通过破坏死锁的四个必要条件之一来预防 3 死锁的预防 出现死锁有四个必要条件，只要确保至少一个必要条件不成立，就能预防死锁发生。 3.1 破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。 缺点：资源利用率可能比较低。 3 死锁的预防 3.2