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