第3章处理机调度与死锁(计12级课堂最新)

1、1北华大学北华大学.计算机科学技术学院计算机科学技术学院操作系统原理操作系统原理 课程课程 处理机调度与死锁处理机调度与死锁 第第3章章操作系统原理操作系统原理 课程 第2张本章目标本章目标掌握作业调度和进程调度的功能；理解作业调度与进程掌握作业调度和进程调度的功能；理解作业调度与进程调度的关系；理解作业的四种状态：提交、后备、执行调度的关系；理解作业的四种状态：提交、后备、执行和完成。和完成。掌握常用调度算法的评价指标：吞吐量、周转时间、平掌握常用调度算法的评价指标：吞吐量、周转时间、平均周转时间、带权周转时间和平均带权周转时间均周转时间、带权周转时间和平均带权周转时间。掌握基本调度算法的实

2、现思想，并能进行评价指标的计掌握基本调度算法的实现思想，并能进行评价指标的计算算 。掌握进程死锁的概念、产生的必要条件及解决死锁的方掌握进程死锁的概念、产生的必要条件及解决死锁的方法。法。掌握银行家算法的思想，能应用银行家算法解决资源分掌握银行家算法的思想，能应用银行家算法解决资源分配问题。配问题。操作系统原理操作系统原理 课程 第3张处理机调度处理机调度与死锁与死锁 调对队列模型和调度准则调对队列模型和调度准则处理机调度的基本概念处理机调度的基本概念 调度算法调度算法 死锁的检测与解除死锁的检测与解除 预防死锁的方法预防死锁的方法 产生死锁的原因和必要条件产生死锁的原因和必要条件 处理机调度

3、处理机调度死锁死锁 实时调度实时调度 本章结构本章结构操作系统原理操作系统原理 课程 第4张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 作业的状态及其转换作业的状态及其转换1.作业作业(Job) 用户在一次计算过程中，或者一次事务处理过程中，要求计算用户在一次计算过程中，或者一次事务处理过程中，要求计算机系统所做工作的总称。机系统所做工作的总称。2.作业步作业步(Job Step) 一般情况下，一个作业可划分成若干个部分，每个部分称为一一般情况下，一个作业可划分成若干个部分，每个部分称为一个作业步。个作业步。在作业运行期间，各作业步之间存在着相互联系，往往上一个作业步的结果作

4、为下一个作业步的输入。操作系统原理操作系统原理 课程 第5张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 作业的状态及其转换作业的状态及其转换3.作业流作业流一次有一批作业进入系统，并在操作系统控制下，一个接一个地一次有一批作业进入系统，并在操作系统控制下，一个接一个地进行处理。进行处理。4.作业的组成作业的组成作业由作业由程序程序、数据数据、作业说明书作业说明书组成。组成。其中程序和数据完成用户所要求的业务处理工作；作业说明书则体现用户的控制意图，主要包含三方面的内容：作业的基本描述作业的基本描述、作业的控制描述作业的控制描述和和资源要求描述资源要求描述，它是用作业控制语言书

5、写的 。操作系统原理操作系统原理 课程 第6张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 作业的状态及其转换作业的状态及其转换5.作业控制块（作业控制块（Job Control Block-JCB）作业存在的唯一标志，是系统为管理作业所设置的一个数据结构，作业存在的唯一标志，是系统为管理作业所设置的一个数据结构，存放了管理和控制作业所必需的信息。存放了管理和控制作业所必需的信息。6. 状态转换状态转换一个作业从提交给计算机系统到执行结束退出系统，一般都要经一个作业从提交给计算机系统到执行结束退出系统，一般都要经历历提交（输入提交（输入）、）、收容（后备收容（后备）、）、执行执

6、行和和完成完成等等4个状态。个状态。（图示图示）操作系统原理操作系统原理 课程 第7张作业的状态转换图作业的状态转换图 内存内存就绪就绪执行执行等待等待 外存外存就绪就绪等待等待完成完成状态状态收容收容状态状态提交提交状态状态交换调度交换调度进（线）程调度进（线）程调度作业调度作业调度作业调度作业调度输入管理系统输入管理系统操作系统原理操作系统原理 课程 第8张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.2 调度的层次调度的层次1. 高级调度高级调度 (High Level Scheduling)： 又称又称“作业调度作业调度”、“长程调度长程调度”、“接纳调度接纳调度”。 1）

7、主要任务）主要任务：按一定的原则对外存输入井上的大量后备作业进行选择，给选按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、出的作业分配内存、I/O设备等必要的资源，并建立相应的进程排设备等必要的资源，并建立相应的进程排在就绪队列中，以使该作业的进程获得竞争处理机的权利。在就绪队列中，以使该作业的进程获得竞争处理机的权利。当该作业当该作业执行完毕执行完毕时，还负责回收系统资源。时，还负责回收系统资源。注意注意：分时系统、实时系统：分时系统、实时系统没有没有作业调度作业调度操作系统原理操作系统原理 课程 第9张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.2 调

8、度的层次调度的层次1. 高级调度高级调度 (High Level Scheduling)：2）两个决定两个决定：每次选择多少个作业：取决于每次选择多少个作业：取决于“多道程序度多道程序度”选择哪些作业：取决于选择哪些作业：取决于“调度算法调度算法”操作系统原理操作系统原理 课程 第10张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.2 调度的层次调度的层次2. 中级调度中级调度（Intermediate Level Scheduling）：）： 又称又称“交换调度交换调度”、“中程调度中程调度”。主要任务主要任务： 为提高内存利用率和系统吞吐量，按照给定的原则和策略，为提高内存利用

9、率和系统吞吐量，按照给定的原则和策略，将处于将处于外存外存交换区中的就绪状态或等待状态的进程交换区中的就绪状态或等待状态的进程调入内存调入内存，或把处于或把处于内存内存就绪状态或等待状态的进程就绪状态或等待状态的进程交换到外存交换到外存交换区。交换区。“挂起与解挂挂起与解挂”操作系统原理操作系统原理 课程 第11张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.2 调度的层次调度的层次3. 低级调度低级调度（Low Level Scheduling）：）： 又称又称”进程调度进程调度”或或“短程调度短程调度”。 1）主要任务）主要任务：按照某种策略和方法按照某种策略和方法选取一个处于

10、就绪状态的进程占用处理机选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程之后，系统要切换进程的上下文以建在确定了占用处理机的进程之后，系统要切换进程的上下文以建立与占用处理机进程相适应的执行环境。立与占用处理机进程相适应的执行环境。2）3个基本机制个基本机制：排队器、分派器、上下文切换机制：排队器、分派器、上下文切换机制操作系统原理操作系统原理 课程 第12张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.2 调度的层次调度的层次3）两种调度方式两种调度方式：不可抢占方式不可抢占方式：进程在处理机上执行时，除非执行完、阻塞、：进程在处理机上执行时，除非执行完、阻塞、 等

11、待同步信号或消息，才会重新调度新的进程。等待同步信号或消息，才会重新调度新的进程。 评价：评价：简单，系统开销小，貌似公正，但却可能导致系统性能恶化（紧 急任务、后到短作业）抢占方式抢占方式：优先权原则、短进程优先原则、时间片原则：优先权原则、短进程优先原则、时间片原则3. 低级调度低级调度（Low Level Scheduling）：）：操作系统原理操作系统原理 课程 第13张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.3 有关于有关于优先权优先权1. 静态优先权静态优先权 在创建进程时指定，进程运行期间不变。常用整数表示在创建进程时指定，进程运行期间不变。常用整数表示“优先优

12、先数数”。优先数与优先权正比？反比？视系统规定而定。优先数与优先权正比？反比？视系统规定而定。 进程类型：系统进程类型：系统用户用户 进程对资源的需求：小者优先进程对资源的需求：小者优先 用户的申请：用户的申请：“外部优先权外部优先权”，需，需“高额付费高额付费”。确定优先权的依据？确定优先权的依据？操作系统原理操作系统原理 课程 第14张3.1 处理机调度的基本概念处理机调度的基本概念 3.1.3 有关于有关于优先权优先权2. 动态优先权动态优先权 在进程创建时创立一个优先数，但在其生命周期内优先数可以动在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。态变化。相对公平相对公平

13、系统开销大（需计算优先级）系统开销大（需计算优先级）评价：评价：操作系统原理操作系统原理 课程 第15张3. 2 调度队列模型调度队列模型 1. 仅有仅有进程进程调度的调度队列模型调度的调度队列模型 就 绪队 列阻 塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完操作系统原理操作系统原理 课程 第16张2. 具有具有高级高级和和低级低级调度的调度队列模型调度的调度队列模型 就 绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现等待事件n事件n出现后备 队列3. 2 调度队列模型调度队列模型 操作系统原理操作系统原理 课程 第17张3. 同时具有同时

14、具有三级调度三级调度的调度队列模型的调度队列模型 就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3. 2 调度队列模型调度队列模型 操作系统原理操作系统原理 课程 第18张1. 任务在当前时间片执行完后，任务在当前时间片执行完后，若能全部完成，则变为若能全部完成，则变为“完成完成”状态状态，再也不参与竞争处理机。，再也不参与竞争处理机。2. 任务在当前时间片执行完后，若尚未完成，则任务在当前时间片执行完后，若尚未完成，则排在就绪队列排在就绪队列末尾末尾。（。（注意在应用计算时，可能会出现同一时间也

15、有新进程进入就绪队列注意在应用计算时，可能会出现同一时间也有新进程进入就绪队列的情况，一般的情况，一般先排新进程先排新进程）3.在执行期间，若进程被阻塞，则将其在执行期间，若进程被阻塞，则将其置入相应阻塞队列置入相应阻塞队列。强调强调：进程执行时出现的三种情况进程执行时出现的三种情况操作系统原理操作系统原理 课程 第19张3.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1. 面向用户面向用户的准则的准则 (1) 周转时间短。周转时间短。 niSiiTTnW11作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权带权周转时间周转时间，而平均带权周转

16、时间平均带权周转时间则可表示为: 作业的周转时间为：作业的周转时间为：TsiTeiTi Ti ：作业：作业i的的周转周转时间时间 T完成完成i：作业：作业i的的完成完成时间时间 T提交提交i： 作业作业i的的提交提交时间时间 可把平均周转时间平均周转时间描述为： iiiTnT11nTi=T完成完成i-T提交提交i操作系统原理操作系统原理 课程 第20张(2) 响应时间快。响应时间快。 (3) 截止时间的保证。截止时间的保证。 (4) 优先权准则。优先权准则。 3.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1. 面向用户面向用户的准则的准则 操作系统原理操作系统原理

17、课程 第21张2. 面向系统面向系统的准则的准则 (1) 系统吞吐量高。系统吞吐量高。(2) 处理机利用率好。处理机利用率好。 (3) 各类资源的平衡利用。各类资源的平衡利用。 3.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 操作系统原理操作系统原理 课程课程高级高级调度调度低级低级调度调度中级中级调度调度作业从提交开始到结束可能经历作业从提交开始到结束可能经历三级三级调度调度:作业作业调度调度交换交换调度调度进程进程调度调度选择选择=调度调度操作系统原理操作系统原理 课程课程生活中随处可见的生活中随处可见的排队排队现象。现象。讲个讲个“先来后到先来后到”操作系统原理

18、操作系统原理 课程 第24张3.2 调调 度度 算算 法法 一、一、 先来先服务先来先服务算法算法 1.原则：原则：发生调度时发生调度时，按照作业（或进程）提交（或就绪），按照作业（或进程）提交（或就绪）的的先后次序先后次序来调度。来调度。First Come First Serve -FCFS 4.评价：评价： 优优:实现简单实现简单 缺缺:没考虑优先级没考虑优先级 3.实例分析：实例分析：“非剥夺式非剥夺式”2.同时适用于同时适用于高级高级和和低级低级调度。调度。操作系统原理操作系统原理 课程课程银行窗口取钱的银行窗口取钱的苦恼苦恼。站错队了！站错队了！操作系统原理操作系统原理 课程 第2

19、6张3.2 调调 度度 算算 法法 二、二、 短作业短作业(进程进程)优先优先算法算法 1.原则：原则：发生调度时发生调度时，选择要求服务时间即，选择要求服务时间即运行时间最短运行时间最短的的作业（或进程）来调度。作业（或进程）来调度。4.评价：评价： 优优:系统吞吐量高系统吞吐量高 缺缺:不利于长作业，甚至会不利于长作业，甚至会“饿死饿死”； 完全未考虑作业的紧迫程度；完全未考虑作业的紧迫程度； 运行时间的估计也有问题运行时间的估计也有问题3.实例分析：实例分析：“非剥夺式非剥夺式”Short Job(Process)First-SJ(P)F2同时适用于同时适用于高级高级和和低级低级调度。调

20、度。操作系统原理操作系统原理 课程课程视系统的视系统的目标目标和和需求需求而定而定1.都既都既适用于作业调度适用于作业调度（高级），又（高级），又适用于进程调度适用于进程调度（低级）。（低级）。2.都属于都属于非抢占式非抢占式调调度算法。度算法。不能及时响应用户的请求不能及时响应用户的请求操作系统原理操作系统原理 课程课程幼儿园小班幼儿园小班阿姨喂饭阿姨喂饭。操作系统原理操作系统原理 课程课程 把把CPU的处理时间划分成的处理时间划分成若干时间片若干时间片,初始时按初始时按FCFS顺序顺序赋赋给就绪队列中的每一个进程，进程给就绪队列中的每一个进程，进程轮流轮流占有占有CPU，当时间片用，当时间

21、片用完时，即使进程未执行完毕，系统也完时，即使进程未执行完毕，系统也剥夺剥夺该进程的该进程的CPU，将该，将该进程排在进程排在就绪队列末尾就绪队列末尾，同时系统选择另一个进程运行。，同时系统选择另一个进程运行。 只适用于只适用于低级低级调度（进程），调度（进程），分时系统分时系统中常常使用。中常常使用。Round Robin 轮叫轮叫调度调度三、时间片轮转三、时间片轮转调度算法调度算法-RRRR3.2 调调 度度 算算 法法 操作系统原理操作系统原理 课程课程就 绪队 列阻 塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完1.1.任务在当前时间片执行完后，任务在当前时间片执行完后，

22、若能全部完成，则变为若能全部完成，则变为“完成完成”状态状态，再也，再也不参与竞争处理机。不参与竞争处理机。2.2.任务在当前时间片执行完后，若尚未完成，则任务在当前时间片执行完后，若尚未完成，则排在就绪队列末尾排在就绪队列末尾。（注意在应用计算时，可能会出现同一时间也有新进程进入就绪队列的情况，一般注意在应用计算时，可能会出现同一时间也有新进程进入就绪队列的情况，一般先先排新进程排新进程）3.3.在执行期间，若进程被阻塞，则将其在执行期间，若进程被阻塞，则将其置入相应阻塞队列置入相应阻塞队列。三、时间片轮转三、时间片轮转调度算法调度算法-RRRR3.2 调调 度度 算算 法法 操作系统原理操

23、作系统原理 课程课程（1 1）与时间片大小有关的因素）与时间片大小有关的因素: :（2 2）时间片种类）时间片种类: : 固定固定时间片时间片 可变可变时间片时间片 系统响应时间系统响应时间 就绪进程个数就绪进程个数 CPU能力能力 三、时间片轮转三、时间片轮转调度算法调度算法-RRRR3.2 调调 度度 算算 法法 q= R / Nmax就绪队列就绪队列模拟模拟（ ms 时）时）例例：考虑：考虑4个进程个进程P1P2P3P4信息如下，请分析按照信息如下，请分析按照时间片轮转时间片轮转（RR）调度算调度算法时各进程执行过程法时各进程执行过程（时间片为时间片为2ms），），并计算并计算 每个进程

24、的周转时间每个进程的周转时间（假设忽略（假设忽略进程的调度时间）。进程的调度时间）。进程进程创建时刻创建时刻运行时间运行时间msP102P224P342P464P1解解：执行过程如下：执行过程如下P20 24P3420进程进程时间时间P1P2P3P42ms时时P1完成完成P2就绪队列就绪队列模拟模拟（ ms 时）时）例例：考虑：考虑4个进程个进程P1P2P3P4信息如下，请分析按照信息如下，请分析按照时间片轮转时间片轮转（RR）调度算）调度算法时各进程执行过程法时各进程执行过程（时间片为时间片为2ms），），并计算并计算 每个进程的周转时间每个进程的周转时间（假设忽略（假设忽略进程的调度时间）

25、。进程的调度时间）。进程进程创建时刻创建时刻运行时间运行时间msP102P224P342P464解解：执行过程如下：执行过程如下P20 24P3420进程进程时间时间P1P2P3P46P46ms时时P3完成完成6888ms时时P2完成完成1010就绪队列就绪队列模拟模拟（ ms 时）时）例例：考虑：考虑4个进程个进程P1P2P3P4信息如下，请分析按照信息如下，请分析按照时间片轮转时间片轮转（RR）调度算）调度算法时各进程执行过程法时各进程执行过程（时间片为时间片为2ms），），并计算并计算 每个进程的周转时间每个进程的周转时间（假设忽略（假设忽略进程的调度时间）。进程的调度时间）。进程进程创

26、建时刻创建时刻运行时间运行时间msP102P224P342P464解解：执行过程如下：执行过程如下420进程进程时间时间P1P2P3P46P4812ms时时P4完成完成1010 1212Ti=T完成完成i-T创建创建iT12-02T28-26T36-42T412-66操作系统原理操作系统原理 课程 第35张3.2 调调 度度 算算 法法 四、四、 高优先权优先高优先权优先算法算法 1.原则：原则：发生调度时发生调度时，优先选择就绪队列中，优先选择就绪队列中优先级最高优先级最高的进程的进程投入运行。投入运行。3.实例分析：实例分析：Highest Priority First - HPF2. 优

27、先权调度算法的类型优先权调度算法的类型 1) 非抢占式非抢占式优先权算法优先权算法2) 抢占式抢占式优先权算法优先权算法静态优先权静态优先权操作系统原理操作系统原理 课程 第36张3.2 调调 度度 算算 法法 3.2.5 高响应比优先高响应比优先算法算法 1.引入：引入：先来先服务和短作业优先算法都有其先来先服务和短作业优先算法都有其片面性片面性，先来先服务调度算法，先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间；短作业优先算只考虑作业的等待时间，而忽视了作业的运行时间；短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。法则相反，只考虑了作业的运行时间，而

28、忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间的一种响应比高者优先调度算法是介于这两种算法之间的一种拆衷拆衷的算法。的算法。 2.响应比响应比R定义定义:一种静态优先权一种静态优先权要求服务时间要求服务时间等待时间优先权响应比响应比R= TWTTWR/1/ )(操作系统原理操作系统原理 课程 第37张 (1) 如果作业的等待时间相同，则要求服务的时间愈短，如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有其优先权愈高，因而该算法有利于短作业利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定于其当要求服务的时间相同时，作业的优先权决定于其等待时

29、间，等待时间愈长，其优先权愈高，因而它实现的是等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务先来先服务。 (3) 对于对于长作业长作业，作业的优先级可以随等待时间的增加，作业的优先级可以随等待时间的增加而提高，而提高，当其等待时间足够长时当其等待时间足够长时，其优先级便可升到很高其优先级便可升到很高， 从而也可获得处理机。从而也可获得处理机。 扩展算法扩展算法3.分析：分析：TWTTWR/1/ )(操作系统原理操作系统原理 课程 第38张非抢占式非抢占式优先权算法优先权算法 此方式下，系统一旦把处理机分配给就绪队列中优先权最此方式下，系统一旦把处理机分配给就绪队列中优先权最高的

30、进程后，该进程便高的进程后，该进程便一直执行下去，直至完成一直执行下去，直至完成；或因发生；或因发生某事件使该某事件使该进程放弃处理机进程放弃处理机时，系统方可再将处理机重新分时，系统方可再将处理机重新分配给另一优先权最高的进程。配给另一优先权最高的进程。 这种调度算法主要用于这种调度算法主要用于批处理系统批处理系统中；也可用于某些对中；也可用于某些对实实时性要求不严时性要求不严的实时系统中。的实时系统中。 操作系统原理操作系统原理 课程 第39张 此方式下，系统同样是把处理机分配给优先权最高的进程，使之此方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。执行。但在其执行期间，只要又

31、出现了另一个其优先权更高的进程，但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程进程调度程序就立即停止当前进程(原优先权最高的进程原优先权最高的进程)的执行，重的执行，重新将处理机分配给新到的优先权最高的进程。新将处理机分配给新到的优先权最高的进程。 因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果PiPj，原进程Pj便继续执行；但如果是PiPj, 则立即停止Pj的执行，做进程切换，使i进程投入执行。 显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的显然，这种抢占式的优先权

32、调度算法，能更好地满足紧迫作业的要求，故而常用于要求，故而常用于要求比较严格的实时系统要求比较严格的实时系统中，中， 以及以及对性能要求较对性能要求较高的批处理和分时系统高的批处理和分时系统中。中。 抢占式抢占式优先权调度算法优先权调度算法例例1 1：4 4个进程个进程ABCDABCD的提交时间和要求系统的服务时间如表，请分的提交时间和要求系统的服务时间如表，请分析按照析按照FCFSFCFS算法进行调度时的执行过程，并填写下表算法进行调度时的执行过程，并填写下表( (时间单位时间单位ms)ms)。进程名进程名提交时间提交时间服务时间服务时间开始执行时间开始执行时间完成时间完成时间周转时间周转时

33、间Ti带权周转时间带权周转时间WiA010111B110011011001C21001012011991.99D31201202199199解解：执行过程如下执行过程如下ABCD0进程进程时间时间1101201 202Wi=Ti / TSTi=T完成完成i-T提交提交i系统的系统的平均带权周转时间平均带权周转时间 W=（1+1+1.99+199）4=50.75例例2 2：4 4个进程个进程ABCDABCD的提交时间和要求系统的服务时间如表，请分的提交时间和要求系统的服务时间如表，请分析按照析按照SPFSPF算法进行调度时的执行过程，并填写下表算法进行调度时的执行过程，并填写下表( (时间单位时

34、间单位ms)ms)。进程名进程名提交时间提交时间服务时间服务时间开始执行时间开始执行时间完成时间完成时间周转时间周转时间Ti带权周转时间带权周转时间WiA010111B110011011001C21001022022002D311011029999解解：执行过程如下执行过程如下ABCD0进程进程时间时间1101 102202Wi=Ti / TSTi=T完成完成i-T提交提交i系统的系统的平均带权周转时间平均带权周转时间 W=（1+1+2+99）4=25.75操作系统原理操作系统原理 课程 第42张例例2：考虑：考虑5个进程个进程P1P2P3P4P5如下表，规定进程的优先数越小优先级越高，如下表

35、，规定进程的优先数越小优先级越高，请分析按照请分析按照非非剥夺式优先级调度剥夺式优先级调度算法时各进程执行过程，并计算采用每算法时各进程执行过程，并计算采用每算法时的平均周转时间（假设忽略进程的调度时间）。算法时的平均周转时间（假设忽略进程的调度时间）。解：解：1.非剥夺式非剥夺式HPF过程如下过程如下391318进程进程创建时刻创建时刻运行时间运行时间ms优先数优先数P1033P2265P3441P4652P58240进程进程时间时间P1P2P3P4P520T13-03T29-27T313-49T418-612T520-812T（3+7+9+12+12）58.60Ti=T完成完成i-T提交提

36、交i操作系统原理操作系统原理 课程 第43张例例2：考虑：考虑5个进程个进程P1P2P3P4P5如下表，规定进程的优先数越小优先级越高，如下表，规定进程的优先数越小优先级越高，请分析按照请分析按照非非剥夺式优先级调度剥夺式优先级调度算法时各进程执行过程，并计算采用每算法时各进程执行过程，并计算采用每算法时的平均周转时间（假设忽略进程的调度时间）。算法时的平均周转时间（假设忽略进程的调度时间）。解：解：2.剥夺式剥夺式HPF过程如下过程如下34813进程进程创建时刻创建时刻运行时间运行时间ms优先数优先数P1033P2265P3441P4652P58240进程进程时间时间P1P2P3P4P515

37、T13-03T220-218T38-44T413-67T515-87T（3+18+4+7+7）57.8020Ti=T完成完成i-T提交提交i2操作系统原理操作系统原理 课程 第44张扩展扩展-调度算法调度算法 原则原则1：操作系统原理操作系统原理 课程 第45张多级反馈队列调度算法示意图就绪队列 1就绪队列 2就绪队列 3就绪队列 nS1S2S3至CPU至CPU至CPU至CPU(时间片： S1 S2 S3)操作系统原理操作系统原理 课程 第46张-调度算法调度算法 原则原则2：操作系统原理操作系统原理 课程 第47张原则原则3：扩展扩展-调度算法调度算法 操作系统原理操作系统原理 课程 第48

38、张(1) 终端型作业用户。终端型作业用户。 (2) 短批处理作业用户。短批处理作业用户。 (3) 长批处理作业用户。长批处理作业用户。扩展：扩展：多级反馈队列调度算法多级反馈队列调度算法 操作系统原理操作系统原理 课程 第49张3.3 实实 时时 调调 度度 3.3.1 实现实时调度的实现实时调度的基本条件基本条件 (1) 就绪时间就绪时间(2) 开始截止时间和完成截止时间开始截止时间和完成截止时间 (3) 处理时间处理时间 (4) 资源要求资源要求 (5) 优先级优先级 操作系统原理操作系统原理 课程 第50张 在实时系统中，通常都有着多个实时任务。若处理机的在实时系统中，通常都有着多个实时

39、任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，任务不能得到及时处理， 从而导致发生难以预料的后果。从而导致发生难以预料的后果。假定系统中有假定系统中有m个周期性的硬实时任务，它们的个周期性的硬实时任务，它们的处理时间处理时间可可表示为表示为Ci，周期时间周期时间表示为表示为Pi，则在单处理机情况下，必须，则在单处理机情况下，必须满足下面的限制条件，满足下面的限制条件， 系统才是可调度的。系统才是可调度的。miiiPC113.3.1 实现实时调度的实现实时调度的基本条件基本条件 操作系统原理操作系统原

40、理 课程 第51张miiiNPC1操作系统原理操作系统原理 课程 第52张3. 采用抢占式调度机制采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务当一个优先权更高的任务到达时，允许将当前任务暂时挂暂时挂起起，而令高优先权任务立即投入运行，这样便可满足该硬实时，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。任务对截止时间的要求。但这种调度机制比较复杂。 3.3.1 实现实时调度的实现实时调度的基本条件基本条件 操作系统原理操作系统原理 课程 第53张4. 具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：该机制应具有

41、如下两方面的能力： (1) 对外部中断的快速响应能力对外部中断的快速响应能力。为使在紧迫的外部。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，中断机构，还应使禁止中断的时间间隔尽量短， 以免耽以免耽误时机误时机(其它紧迫任务其它紧迫任务)。 (2) 快速的任务分派能力快速的任务分派能力。在完成任务调度后，便应。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，进行任务切换。为了提高分派程序进行任务切换时的速度， 应使系统中的每个运行功能单位适当的小，以减少任务

42、切应使系统中的每个运行功能单位适当的小，以减少任务切换的时换的时间开销。间开销。 3.3.1 实现实时调度的实现实时调度的基本条件基本条件 操作系统原理操作系统原理 课程 第54张3.3.2 常用的几种实时调度算法常用的几种实时调度算法 1. 最早截止时间优先算法最早截止时间优先算法 EDF(Earliest Deadline First) 根据任务的根据任务的开始截止时间开始截止时间来确定任务的优先级。该算法要来确定任务的优先级。该算法要求在系统中保持一个按截止时间早晚排成的实时任务就绪队求在系统中保持一个按截止时间早晚排成的实时任务就绪队列，可用于列，可用于抢占非抢占抢占非抢占调度方式中。

43、调度方式中。 2. 最低松弛度优先算法最低松弛度优先算法 LLF(Least Laxity First)根据任务根据任务紧急紧急( (或松弛或松弛) )的程度的程度，来确定任务的优先级。任务，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，的紧急程度愈高，为该任务所赋予的优先级就愈高， 以使之以使之优先执行。该算法要求系统中有一个按松弛度排序的实时任优先执行。该算法要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，该算法主务就绪队列，松弛度最低的任务排在队列最前面，该算法主要用于要用于可抢占可抢占调度方式中。调度方式中。松弛度松弛度必须完成时

44、间本身运行时间当前时间必须完成时间本身运行时间当前时间操作系统原理操作系统原理 课程 第55张本次课总结本次课总结几种典型调度算法几种典型调度算法掌握掌握 先来先服务调度先来先服务调度 （适用于作业、进程调度）（适用于作业、进程调度） 短优先调度短优先调度 （适用于作业、进程调度）（适用于作业、进程调度） 高优先权优先调度高优先权优先调度 （适用于作业、进程调度）（适用于作业、进程调度） 时间片轮转调度时间片轮转调度 （只适用于进程调度）（只适用于进程调度） 高响应比优先调度高响应比优先调度 多级反馈队列调度多级反馈队列调度实时调度实时调度 了解了解 基本条件基本条件 算法分类算法分类 最早截

45、止时间优先最早截止时间优先 最低松弛度优先最低松弛度优先操作系统原理操作系统原理 课程 第56张本次课作业：补充题本次课作业：补充题有有5个作业（个作业（A,B,C,D,E）几乎同时到达一个计算中心）几乎同时到达一个计算中心,到达顺到达顺序按序按C,D,B,E,A处理处理,估计运行时间分别为估计运行时间分别为2、4、6、8、10分分钟，优先数分别为钟，优先数分别为1、2、3、4、5，系统规定进程的优先数越，系统规定进程的优先数越大，优先级越高。大，优先级越高。试描述在采用下述几种调度算法时试描述在采用下述几种调度算法时调度思想调度思想和和各进程运行过各进程运行过程程，并计算采用每种算法时的，并

46、计算采用每种算法时的系统平均周转时间系统平均周转时间和和平均带权平均带权周转时间周转时间。 1.最高优先级优先最高优先级优先2.时间片轮转时间片轮转（时间片为（时间片为2分钟）分钟）3.先来先服务先来先服务（）（）4.短作业优先短作业优先 操作系统原理操作系统原理 课程课程生产者生产者-消费者中消费者中P操作的顺序操作的顺序。 僵持僵持（DeadlyEmbrace）proceducer: wait(empty); wait(mutex); signal(mutex); signal(full);consumer: wait(full); wait(mutex); signal(mutex);

47、signal(empty); wait(mutex); wait(empty);操作系统原理操作系统原理 课程课程哲学家吃面哲学家吃面问题问题.0#1#2#3#4# 僵持僵持（DeadlyEmbrace）0#1#2#3#4#0#1#2#3#4#“各执各执1筷筷”操作系统原理操作系统原理 课程课程 交通中交通中的的死锁死锁现象。现象。 僵持僵持（DeadlyEmbrace）操作系统原理操作系统原理 课程 第60张3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 一、一、 死锁的死锁的定义定义 R1R2P1P2理解理解： 死锁就是两个或两个以上的进程等候着一个死锁就是两个或两个以上的进程等

48、候着一个永远不会发永远不会发生生的事件时所取的一种系统状态。的事件时所取的一种系统状态。操作系统原理操作系统原理 课程 第61张3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件一、一、 死锁的死锁的定义定义 教材中定义教材中定义：所谓死锁死锁，是指以上并发进程，且，且。从而造成大家都想得到资源而又都得不到资源，各并发进程的状态。 引申引申：关于死锁的一些结论：关于死锁的一些结论：参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与

49、死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集参与死锁的进程是当前系统中所有进程的子集操作系统原理操作系统原理 课程 第62张3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件二、二、 产生产生死锁的死锁的原因原因 1. 并发进程的资源竞争并发进程的资源竞争。 产生死锁的产生死锁的根本原因根本原因在于系统提供的资源个数在于系统提供的资源个数少于少于并发进程所并发进程所要求的该类资源数。要求的该类资源数。 资源的分类：资源的分类： 可抢占资源：可抢占资源：不可抢占资源不可抢占资源 共享资源共享资源独占资源独占资源 永久性资源永久性资源临时资源临时资源当多个进程竞争当多个

50、进程竞争不可抢占资源不可抢占资源、独占资源独占资源或或消耗性的临时资源消耗性的临时资源，且资源数量不，且资源数量不足时，可能会产生死锁。足时，可能会产生死锁。操作系统原理操作系统原理 课程 第63张2. 进程推进顺序不当引起死锁进程推进顺序不当引起死锁 1) 进程推进顺序进程推进顺序合法合法 P1P2R1R2二、二、 产生产生死锁的死锁的原因原因 正正常常运运行行 操作系统原理操作系统原理 课程 第64张 2) 进程推进顺序进程推进顺序非法非法二、二、 产生产生死锁的死锁的原因原因 2. 进程推进顺序不当引起死锁进程推进顺序不当引起死锁 死死锁锁R1R2P1P2操作系统原理操作系统原理 课程

51、第65张三、三、 产生死锁的产生死锁的必要条件必要条件 互斥互斥请求和保持请求和保持不剥夺不剥夺环路等待环路等待竞争的资源竞争的资源一一次只能被一个次只能被一个进程使用进程使用。当一个进程占当一个进程占有一些资源，有一些资源，同时又申请新同时又申请新的资源，若新的资源，若新资源申请失败，资源申请失败，进程将进程将占有着占有着资源阻塞等待资源阻塞等待。进程获得的资进程获得的资源，在未使用源，在未使用完之前，完之前，不能不能被其他进程被其他进程强强行剥夺行剥夺。发生死锁时，发生死锁时，必然存在着必然存在着“进程进程-资源资源”的环形请求链的环形请求链。操作系统原理操作系统原理 课程课程预预 防防设

52、置某些限设置某些限制条件，制条件，破破坏坏死锁产生死锁产生的的必要条件必要条件。避免避免也叫也叫“动态预防动态预防”，在资源的动态分配在资源的动态分配过程中，用某种方过程中，用某种方法去防止系统进入法去防止系统进入不安全状态不安全状态，从而，从而避免死锁。避免死锁。检测并解除检测并解除允许发生死锁，但允许发生死锁，但可可及时检测及时检测出来，出来，并精确指明相关进并精确指明相关进程和资源，同时配程和资源，同时配合适当措施合适当措施消除消除死死锁。锁。四、四、 处理处理死锁的死锁的方法方法操作系统原理操作系统原理 课程 第67张3.6 预防死锁预防死锁 一、一、 预防预防死锁死锁 -静态静态预防

53、预防0.摒弃摒弃“互斥互斥”条件条件 1. 摒弃摒弃“请求和保持请求和保持”条件条件 2. 摒弃摒弃“不剥夺不剥夺”条件条件 3. 摒弃摒弃“环路等待环路等待”条件条件 受设备的受设备的固有使用特性固有使用特性的制约，不便强行破坏的制约，不便强行破坏 预防是采用某种策略，限制并发进程对资源的请求，从而预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。使得死锁的必要条件在系统执行的任何时间都不满足。 为了不发生死锁，必须设法为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一破坏产生死锁的四个必要条件之一。3.6 预防死锁预防死锁 要求每个进程在

54、运行前必须要求每个进程在运行前必须一次性一次性申请它所要求的所有资源，申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。且仅当该进程所要资源均可满足时才给予一次性分配。：简单，易于实现，安全：简单，易于实现，安全 资源严重浪费资源严重浪费 可以使进程运行被延迟可以使进程运行被延迟返回返回“资源预先资源预先（静态静态）分配法分配法”-摒弃摒弃“请求和保持请求和保持”条件条件3.6 预防死锁预防死锁 -摒弃摒弃“不剥夺不剥夺”条件条件 在允许进程动态申请资源前提下规定，一个进程在申请新在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，

55、必须释放的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请已占有的全部资源，若需要再重新申请 ：增加资源在进程间转移的机时：增加资源在进程间转移的机时 降低资源利用率降低资源利用率返回返回3.6 预防死锁预防死锁 -摒弃摒弃“环路等待环路等待”条件条件 把系统中所有资源把系统中所有资源编号编号，进程在申请资源时必须严格按资，进程在申请资源时必须严格按资源编号的源编号的递增次序递增次序进行，否则操作系统不予分配。进行，否则操作系统不予分配。：序号不宜经常改动，增加新设备不便：序号不宜经常改动，增加新设备不便 对不能匹配正常使用顺序的进程不利。对不能匹配正常使用顺

56、序的进程不利。返回返回“资源有序分配法资源有序分配法”操作系统原理操作系统原理 课程课程破坏破坏互斥互斥 破坏破坏请求和保持请求和保持 破坏破坏不剥夺不剥夺 破坏破坏环路等待环路等待限于资源限于资源固有固有属性属性二、二、如何预防如何预防死锁？死锁？资源静态资源静态分配法分配法申请资源未得申请资源未得时，需时，需释放拥释放拥有资源有资源并阻塞并阻塞资源有序资源有序分配法分配法操作系统原理操作系统原理 课程 第72张3.7 死锁的死锁的避免避免-态态预防预防 一、安全状态一、安全状态 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分在避免死锁的方法中，允许进程动态地申请资源，但系统

57、在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；安全状态，则将资源分配给进程； 否则，令进程等待。否则，令进程等待。 ，是指系统能按某种进程顺序，是指系统能按某种进程顺序(P1, P2, ，Pn)(称称P1, P2, , Pn序列为序列为安全序列安全序列)，来为每个进程，来为每个进程Pi分配其分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个可顺利地完成。如果系统无

58、法找到这样一个安全序列，则称系统安全序列，则称系统处于处于。 操作系统原理操作系统原理 课程 第73张有一个慈善的银行家共有人民币有一个慈善的银行家共有人民币10万元，要贷款给万元，要贷款给A、B、C3个客户。个客户。.银行家算法引例银行家算法引例. 前提条件前提条件：客户要事先提出需要贷款的总额，若不超过银行家的总钱数，银行家即可贷：客户要事先提出需要贷款的总额，若不超过银行家的总钱数，银行家即可贷 款给他。款给他。 若每个客户得到了他要求借的全部金额，他可以完成生意，并将钱立即归还。若每个客户得到了他要求借的全部金额，他可以完成生意，并将钱立即归还。B2(3)C2(4)剩余剩余3万万A3(

59、2)T时刻时刻分配给分配给A 2万万B2(3)C2(4)剩余剩余6万万分配给分配给B 3万万分配给分配给C 4万万C2(4)剩余剩余8万万剩余剩余10万万即按即按A(2)-B(3)-C(4)的顺序进行分配，可完成借贷，故的顺序进行分配，可完成借贷，故T时刻是时刻是安全安全的。的。操作系统原理操作系统原理 课程 第74张B2(3)C2(4)剩余剩余3万万A3(2)T时刻分配给分配给A 1万万B2(3)C2(4)剩余剩余2万万A4(1)分配给分配给B 1万万分配给分配给C 1万万B3(2)C2(4)剩余剩余1万万A4(1)B3(2)C3(3)剩余剩余0万万A4(1)若按若按A(1)-B(1)-C(

60、1)的顺序进行分配，便会死锁，故的顺序进行分配，便会死锁，故安全状态是可以向安全状态是可以向不安全状态转换不安全状态转换的。的。.银行家算法引例银行家算法引例. 操作系统原理操作系统原理 课程 第75张二、避免死锁典型算法二、避免死锁典型算法-1. 银行家算法中的银行家算法中的数据结构数据结构 (1) Available。 这是一个含有这是一个含有m个元素的个元素的数组数组，其中的，其中的每一个元素代表一类每一个元素代表一类可利用的资源数目可利用的资源数目，其初始值是系统中所配置的该类全部可用资，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。源的数目