LINUX操作系统教程课件第四章.pptVIP

基于Linux 的操作系统教程 Operating System Course based on Linux 第四章 调度与死锁 章节目标： 1：掌握调度的类型及模型； 2：掌握几种调度算法； 3：掌握死锁、死锁产生的原因和必要条件以及死锁预防、避免的原理； 4：掌握死锁检测、死锁解除的方法； 5：掌握Linux的调度和死锁技术。 4.1 调度的类型和模型 调度的类型 调度队列模型 调度的类型 高级调度：作业调度。被用来从后备队列中按照某种规则或算法选择若干个作业，把它们装入内存，并为之建立进程，分配必要的资源。 低级调度：进程调度。被用来从就绪队列中选择一个进程，让其占有CPU执行。有非剥夺式和剥夺式两种调度方式。 中级调度：中级调度一般存在于规模较大的综合性OS中，它的引入主要时为了提高内存的利用率和系统吞吐量。 调度队列模型 在各级调度中，等候选择的进程一般存在于相应的调度队列中。图中是一个同时具有三级调度的调度队列模型。 4.2 调度算法 调度算法的选择 各种调度算法 调度算法的选择 选择调度算法的准则： （1）系统吞吐量高； （2）周转时间短； （3）响应时间短； （4）优先权准则； （5）CPU的利用率高； （6）各种资源的均衡利用。 各种调度算法（一） 先来先服务算法（FCFS）：按照进程就绪的先后次序来调度进程。 短进程优先算法（SPF）：对短进程（其CPU周期短）优先的调度算法。 时间片轮转算法（RR） ：轮流调度就绪队列中的进程，每个进程执行一个时间片。 各种调度算法（二） 优先权算法（HPF） ：系统中的每个进程被赋予一个优先权 ，选择就绪队列中优先权最高的进程占有CPU执行。 多级反馈队列算法 ：一种综合了FCFS、RR、HPF的调度算法，它可以满足各类进程的需要。下图是一个多级反馈队列模型。 4.3 死锁及其预防和避免 死锁 死锁的预防 死锁的避免 死锁（一） 死锁的概念：在多任务OS中，多个并发进程因竞争资源而形成的一种僵持局面，若无外力作用，这些进程将永远不能再向前推进。 产生死锁的原因：1、竞争资源；2、进程推进顺序不当。 产生死锁的四个必要条件： 1、互斥条件 2、请求和保持条件 3、不可剥夺条件 4、环路等待条件 死锁（二） 死锁的处理方案： 1、死锁的预防 2、死锁的避免 3、死锁的检测 4、死锁的解除 死锁的预防 破坏“请求和保持”条件 破坏“不剥夺”条件 破坏“环路等待”条件 死锁的避免 基本思想：一般情况下它对进程的资源申请不加限制，只是在即将进入不安全状态时才加以限制。采取一种动态策略。 死锁避免算法：银行家算法 4.4 死锁的检测和解除 死锁的检测 死锁的解除 死锁的检测 资源分配图（RAG） 死锁定理：S为死锁状态，当且仅当S状态的资源分配图是不可完全化简的。 死锁检测算法 死锁的解除 死锁解除方案： 撤消进程 剥夺资源 进程回退 4.5 Linux中的调度和死锁技术 Linux中的调度 Linux中死锁技术 Linux中的调度（一） Linux没有作业调度的概念，只有进程调度。 Linux中的进程调度由内核函数schedule()实现。 Linux的进程调度在以下时机进行： （1）进程状态转换时； （2）向就绪队列(run queue)中加入一个进程时； （3）当前进程的时间片用完时； （4）在系统调用之后进程从系统态返回用户态时； （5）内核完成中断处理，进程返回到用户态时。 Linux中的调度（二） task_struct中与调度有关的域： need_resched counter priority rt_priority policy Linux中的调度（三） 调度策略：综合FIFO、RR、多级反馈轮转调度三种调度策略。 调度实现：遍历就绪队列，调用函数goodness()计算每个进程的goodness值，schedule()选择goodness值最大的进程。 Linux中的调度（四） 进程切换：由宏switch_to()来完成 。 Linux中的死锁技术 Linux只在使用信号量时有死锁的概念。 对于其他情况的死锁，交给程序员自己去解决。 4.6 本章小结 本章介绍了进程调度及各种进程调度算法。 本章介绍了死锁的概念、产生死锁的原因以及发生死锁的四个必要条件。死锁处理的主要方案有：预防死锁、避免死锁、检测和解除死锁。 Linux的进程调度在sche