操作系统--第三章调度与死锁 2016-10

1、第三章 进程调度的核心是调度算法。进程调度的核心是调度算法。 3.1 调度的基本概念调度的基本概念 (一）一） 作业从进入系统到完成作业从进入系统到完成，可能要经历三级调度过程：可能要经历三级调度过程： 1、高级调度、高级调度 又称为又称为作业调度作业调度，它决定将哪些在外存上处于，它决定将哪些在外存上处于 后备状态的作业调入主机内存，准备执行。因此，有时把它后备状态的作业调入主机内存，准备执行。因此，有时把它 称为接纳调度。称为接纳调度。 2 2、低级调度、低级调度 又称为又称为进程调度进程调度，它决定就绪队列中哪个进程，它决定就绪队列中哪个进程 将获得处理机，并实际执行将处理机分配给进程的

2、操作。执将获得处理机，并实际执行将处理机分配给进程的操作。执 行分配处理机的程序称为行分配处理机的程序称为分派程序分派程序。 3、中级调度、中级调度 中级调度的主要作用是在内存和外存之间进行中级调度的主要作用是在内存和外存之间进行 进程交换，以解决内存紧张的问题。如它将内存中处于等待进程交换，以解决内存紧张的问题。如它将内存中处于等待 状态的某些进程调至外存对换区，以腾出内存空间，而将外状态的某些进程调至外存对换区，以腾出内存空间，而将外 存对换区上已具备运行条件的进程重新调入内存，准备运行存对换区上已具备运行条件的进程重新调入内存，准备运行 。故又称为。故又称为交换调度交换调度。 阻塞阻塞

3、状态状态 就绪就绪 状态状态 执行执行 状态状态 调度调度 I/O请求请求 进程进程 释放释放 时间时间 片到片到 后备作业队列后备作业队列 CPU 就绪队列就绪队列 内存内存外存外存 阻塞队列阻塞队列 作业调度作业调度 等待事件等待事件 中级中级调度调度 即交换调度即交换调度 交换文件交换文件 就绪队列就绪队列 阻塞队列阻塞队列 三级调度的模型三级调度的模型 调度队列模型调度队列模型 1. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 图图 3 - 1 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 就 绪队 列 阻 塞队列 进程调度 CPU 进程完成 等待事件 交互用户

4、事 件 出 现 时间片完 2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 图图 3-2 具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型 就 绪队列 进程调度 CPU 进程完成 等待事件1 作业 调度 事件1出现 时间片完 等待事件2 事件2出现 等待事件n 事件n出现 后备 队列 就绪队列的形式。就绪队列的形式。 (2) 设置多个阻塞队列。设置多个阻塞队列。 图图 3-2 示出了具有高、低两级调度的调度队列模型。该模型与上一模示出了具有高、低两级调度的调度队列模型。该模型与上一模 型的主要区别在于如下两个方面。型的主要区别在于如下两个方面。 3. 同时

5、具有三级调度的调度队列模型同时具有三级调度的调度队列模型 图图 3-3 具有三级调度时的调度队列模型具有三级调度时的调度队列模型 就绪队列 进程调度 CPU 就绪，挂起队列 中级调度 阻塞，挂起队列 阻塞队列 等待事件 进程完成 时间片完作业调度 交互型作业 后备队列 批量作业 挂起 事件出现 事 件 出 现 3.1 调度的基本概念调度的基本概念 (三）三） 作业调度是确定作业调度是确定哪些作业哪些作业可以被可以被调入内存调入内存。 进程调度是确定进程调度是确定哪哪个个进程进程可以可以占有占有CPUCPU并执行。并执行。 作业调度是进程调度的基础，作业被作业调度是进程调度的基础，作业被调入内存

6、调入内存后，后， 是以是以进程的形式执行进程的形式执行的。的。 在一个在一个OSOS中进程调度与作业调度的算法是一致的。中进程调度与作业调度的算法是一致的。 ？问题？问题？ 1 1。进程调度与。进程调度与 作业调度之间（功能、调度算法）有作业调度之间（功能、调度算法）有 何区别和联系？何区别和联系？ 2 2。三级调度中，最核心的是那一级调度？为什么。三级调度中，最核心的是那一级调度？为什么？ 各级调度间的关系各级调度间的关系 3.1 调度的基本概念调度的基本概念 (四）四） 作业步作业步 将一个作业划分为若干个顺序处理的步骤，作将一个作业划分为若干个顺序处理的步骤，作 业步相互独立又相互关联。

7、业步相互独立又相互关联。 作业作业 是用户请求计算机系统执行的一次独立的上机任是用户请求计算机系统执行的一次独立的上机任 务，是能够共享公共资源区域的一族有关进程（家族）。务，是能够共享公共资源区域的一族有关进程（家族）。 从静态观点看，作业由从静态观点看，作业由 控制命令系列、程序集、数据控制命令系列、程序集、数据 集三部分构成。集三部分构成。 补充：关于作业的概念补充：关于作业的概念 作业控制块作业控制块 JCB（Job Control Block）用于描述作业。）用于描述作业。 定义为记录类型（作业名、优先级、建立时间、状态外定义为记录类型（作业名、优先级、建立时间、状态外 存地址、大小

8、等）。存地址、大小等）。 作业状态作业状态 作业在其生命期中，共有四种状态：作业在其生命期中，共有四种状态： 关于作业的状态关于作业的状态 作业状态作业状态 作业在其生命期中，共有四种状态：作业在其生命期中，共有四种状态： 完成完成 执行执行 就绪就绪阻塞阻塞进入进入后备后备 内存内存 运行运行 提交提交 作业作业 调度调度 完成完成 问题：引起进程调度的问题：引起进程调度的原因有哪些？原因有哪些？ 3.1 调度的基本概念调度的基本概念 (五）五） 非抢占式（非剥夺式）非抢占式（非剥夺式） 进程进程 一旦被调度一旦被调度 ，就一直占有，就一直占有CPUCPU，直到完成或，直到完成或 因发生某事

9、件而被阻塞（因发生某事件而被阻塞（I/OI/O请求）。请求）。 抢占式（剥夺式）抢占式（剥夺式） 进程未执行完，可由调度程序剥夺其进程未执行完，可由调度程序剥夺其CPUCPU，另分配，另分配 给别的进程。给别的进程。 抢占的原因有：优先级、时间片、短进程等。抢占的原因有：优先级、时间片、短进程等。 在在OSOS中，进程调度的方式分为两类。中，进程调度的方式分为两类。 3.1 调度的基本概念调度的基本概念 (六）六） 记录系统中所有进程的执行情况记录系统中所有进程的执行情况 确定分配处理机的原则（调度算法）确定分配处理机的原则（调度算法） 分配处理机给进程分配处理机给进程 回收处理机、进行进程上

10、下文切换回收处理机、进行进程上下文切换 显然，进程调度的核心问题是调度算法。显然，进程调度的核心问题是调度算法。 3.1 调度的基本概念调度的基本概念 (七）七） 1。周转时间短。周转时间短 周转时间周转时间TT（Tumaround Time） 对作业对作业从作业提交到完成。从作业提交到完成。 对进程对进程第一次进入就绪队列到运行结束。第一次进入就绪队列到运行结束。 平均周转时间平均周转时间ATT（Average Tumaround Time） ATT= Ti 带权带权平均平均 W= 其中：其中： Ti 各进程的各进程的TT TT T Tr ri i 实际执行时间实际执行时间 2. 2. 响应

11、时间快响应时间快 响应时间响应时间RTRT（Response TimeResponse Time）输入键盘命令到屏幕输入键盘命令到屏幕 显示结果。显示结果。 四四. 调度算法准则调度算法准则 1 n i=1 n Ti Tri i=1 n 1 n (2) 响应时间快。响应时间快。 (3) 截止时间的保证。截止时间的保证。 (4) 优先权准则。优先权准则。 1. 面向用户的准则面向用户的准则 (1) 周转时间短。周转时间短。 2. 面向系统的准则面向系统的准则 系统吞吐量高。系统吞吐量高。 (2) 处理机利用率好。处理机利用率好。 (3) 各类资源的平衡利用。各类资源的平衡利用。 四四. 调度算法

12、准则调度算法准则 3.23.2 调度算法调度算法 （一）（一） 先来先服务（先来先服务（FCFSFCFS）算法）算法 最短最短CPUCPU运行期优先（运行期优先（SCBFSCBF）算法）算法 最高优先权（最高优先权（HPFHPF）算法）算法 时间片轮转（时间片轮转（RRRR）算法）算法 多级反馈队列算法多级反馈队列算法 思考题思考题 1、各种调度算法的特点、性能如何？适宜于各种调度算法的特点、性能如何？适宜于 哪类哪类 OS？ 2。最高优先权算法中，动态优先权有何实际意义？。最高优先权算法中，动态优先权有何实际意义？ 常用调度算法常用调度算法 3.23.2 调度算法调度算法 （二）（二） 一一

13、. .、先来先服务（、先来先服务（FCFSFCFS）算法）算法 FCFS（First Come First Server ）法，又称为先）法，又称为先 进先出（进先出（FIFO）算法，就绪进程按照进入的先后次序排）算法，就绪进程按照进入的先后次序排 列，调度程序总是选择队首的进程执行。列，调度程序总是选择队首的进程执行。 这是一种非剥夺式的这是一种非剥夺式的调度算法，简单、易实现。调度算法，简单、易实现。 对短进程易出现等待时间长，服务质量差。对短进程易出现等待时间长，服务质量差。 该算法有利于该算法有利于CPUCPU繁忙型的进程，不利于繁忙型的进程，不利于I/OI/O繁忙型的进繁忙型的进 程

14、。程。 1n 该算法只能用于辅助算法。该算法只能用于辅助算法。 先来先服务调度算法先来先服务调度算法 图图 3-4 FCFS和和SJF调度算法的性能调度算法的性能 3.23.2 调度算法调度算法 （二）（二） 二、二、 最短最短CPUCPU运行期优先（运行期优先（SCBFSCBF）算法）算法 n+1 nn t 该算法优于该算法优于FCFS，但长进程等待时间长，估算误差较大。，但长进程等待时间长，估算误差较大。 SCBF（Shortest CPU Burst First） ，即调度程序总，即调度程序总 是选择是选择CPU运行时间最短的进程执行。运行时间最短的进程执行。 其中其中 为估计的第为估计

15、的第n个个CPU 周期。周期。tn 为实际值。为实际值。 为控制值，为控制值，0 1，常取常取 0.5 n 对对最短最短CPUCPU运行期的估算，依赖于系统的下一个运行期的估算，依赖于系统的下一个CPUCPU周周 期中，实现较困难。进程的期中，实现较困难。进程的CPU时间时间 的估算公式：的估算公式： n+1 3.23.2 调度算法调度算法 （三）（三） 三、三、 最高优先权（最高优先权（HPFHPF）算法）算法 调度程序每次都将调度程序每次都将CPU分配给就绪队列中具有最高优先分配给就绪队列中具有最高优先 级（级（Highest Priority）的进程。该）的进程。该算法的核心是算法的核心

16、是优先级的优先级的 确定。确定。 调度方式分为调度方式分为剥夺式剥夺式和和非剥夺式非剥夺式。 静态优先级静态优先级 在创建进程时根据进程的特性或者用户要求赋予，在进在创建进程时根据进程的特性或者用户要求赋予，在进 程的整个生命期中程的整个生命期中不能改变不能改变。 简单、易实现，但是调度性能不高，优先级低的进程可简单、易实现，但是调度性能不高，优先级低的进程可 能长期等待。能长期等待。 动态优先级动态优先级 在创建进程时为进程赋予一个在创建进程时为进程赋予一个基本优先级基本优先级，在进程的执，在进程的执 行过程中可随进程的特性行过程中可随进程的特性动态改变动态改变。 引起优先级改变的原因：引起

17、优先级改变的原因： 进程等待进程等待CPU时间长短，执行所需时间长短，执行所需CPU时间长短等。时间长短等。 分两类优先级：分两类优先级： 3.23.2 调度算法调度算法 （四）（四） 三、最高优先权（三、最高优先权（HPFHPF）算法）算法 确定进程优先级的一般原则：确定进程优先级的一般原则： 1. 进程的类型进程的类型 例如：例如： 系统进程高于用户进程；系统进程高于用户进程； 前台进程高于后台进程；前台进程高于后台进程； 实时进程高于一般进程。实时进程高于一般进程。 2. 对资源的需求量及类型对资源的需求量及类型 占用占用CPU时间少的，使用内存资源少的进程优时间少的，使用内存资源少的进

18、程优 先级高。先级高。 3. 按作业到达系统的时间顺序按作业到达系统的时间顺序 4. 按用户类型和要求按用户类型和要求 3.23.2 调度算法调度算法 （五）（五） 四、四、 时间片轮转（时间片轮转（RRRR）算法）算法 该该算法主要用于分时系统，按照公平服务的原则，算法主要用于分时系统，按照公平服务的原则， 为进程分配为进程分配CPUCPU时间片。是一种剥夺式的算法。时间片。是一种剥夺式的算法。 轮转法的关键是时间片的选取：轮转法的关键是时间片的选取： 时间片太大，则轮转法蜕化为时间片太大，则轮转法蜕化为FCFSFCFS法。法。 时间片太小，则增加时间片太小，则增加CPUCPU的额外开销。的

19、额外开销。 影响时间片设置的主要因素：影响时间片设置的主要因素： 系统响应时间系统响应时间R R、就绪进程数、就绪进程数N N、计算机处理能力等。、计算机处理能力等。 时间片长度：时间片长度： q = R / N max 3.23.2 调度算法调度算法 （六）（六） 五、高响应比优先调度算法（五、高响应比优先调度算法（HRNHRN） HRN（Highest Response ratio Next）算法将短进算法将短进 程优先与动态优先级相结合。程优先与动态优先级相结合。 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故 该优先权又相当于响应比RP 随着进程等待时间的增加，优先权动态增

20、加。随着进程等待时间的增加，优先权动态增加。 对等待相同时间的短进程比长进程优先权增加得多。对等待相同时间的短进程比长进程优先权增加得多。 长进程随着等待时间增加也会被调度。长进程随着等待时间增加也会被调度。 要求服务时间 响应时间 要求服务时间 要求服务时间等待时间 优先权 3.23.2 调度算法调度算法 （七）（七） 六、多级队列调度六、多级队列调度 根据作业性质不同分为若干个就绪队列，根据作业性质不同分为若干个就绪队列， 如：系统进程队列，交互进程队列，批处理队如：系统进程队列，交互进程队列，批处理队 列等。对各队列采用不同的调度算法。列等。对各队列采用不同的调度算法。 3.23.2 调

21、度算法调度算法 （八）（八） 亦称多级反馈轮转法（亦称多级反馈轮转法（Round Robin with Multiple FeedbackRound Robin with Multiple Feedback） 实现基本思想：实现基本思想： 1 1。按优先级分别设置。按优先级分别设置N N个就绪队列个就绪队列，优先级愈高的队列分配，优先级愈高的队列分配 的时间片愈小。的时间片愈小。 2 2。系统总是。系统总是先调度当前优先级最高的先调度当前优先级最高的队列中的进程，只有当队列中的进程，只有当 最高优先级队列为空时，才去调度低一优先级队列中的进最高优先级队列为空时，才去调度低一优先级队列中的进 程

22、。程。 3 3。进程被调度后，若未执行完时间片到，则。进程被调度后，若未执行完时间片到，则优先级降低优先级降低，进，进 程排入相应优先级队列的程排入相应优先级队列的队尾队尾。 4 4。同一优先级队列，按照。同一优先级队列，按照FCFSFCFS算法调度算法调度。 多级反馈队列是一种多级反馈队列是一种综合调度算法综合调度算法，对进程就绪队列进，对进程就绪队列进 行动态调度和管理。行动态调度和管理。 七、多级反馈队列七、多级反馈队列 3.23.2 调度算法调度算法 （九）（九） 七、多级反馈队列七、多级反馈队列 时间片：时间片：S1S2S3 多级反馈队列调度算法的性能多级反馈队列调度算法的性能 终端

23、型作业用户。终端型作业用户。 (2) 短批处理作业用户。短批处理作业用户。 (3) 长批处理作业用户。长批处理作业用户。 3.3 实实 时时 调调 度度 3.3.1 实现实时调度的基本条件实现实时调度的基本条件 1. 提供必要的信息提供必要的信息 就绪时间。就绪时间。 (2) 开始截止时间和完成截止时间。开始截止时间和完成截止时间。 (3) 处理时间。处理时间。 (4) 资源要求。资源要求。 (5) 优先级。优先级。 2. 系统处理能力强系统处理能力强 假定系统中有假定系统中有m个周期性的硬实时任务，它们的处理时间可表示个周期性的硬实时任务，它们的处理时间可表示 为为Ci，周期时间表示为，周期

24、时间表示为Pi，则在单处理机情况下，必须满足下面的限制，则在单处理机情况下，必须满足下面的限制 条件：条件： m i i i P C 1 1 假如系统中有假如系统中有6个硬实时任务，它们的周期时间都是个硬实时任务，它们的周期时间都是 50 ms，而每次的处，而每次的处 理时间为理时间为 10 ms，则不难算出，此时是不能满足上式的，因而系统是不可，则不难算出，此时是不能满足上式的，因而系统是不可 调度的。调度的。 解决的方法是提高系统的处理能力解决的方法是提高系统的处理能力 途径一途径一: 仍是采用单处理机系统，仍是采用单处理机系统， 但须增强其处理能力，但须增强其处理能力， 以显著地减少对每

25、一以显著地减少对每一 个任务的处理时间；个任务的处理时间； 途径二途径二: 采用多处理机系统。采用多处理机系统。 假定系统中的处理机数为假定系统中的处理机数为N，则应将上述的限制条件改为：，则应将上述的限制条件改为： m i i i N P C 1 3. 采用抢占式调度机制采用抢占式调度机制 4. 具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：该机制应具有如下两方面的能力： (1) 对外部中断的快速响应能力。对外部中断的快速响应能力。 要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短， 以以 免耽误时机

26、免耽误时机(其它紧迫任务其它紧迫任务)。 (2) 快速的任务分派能力。快速的任务分派能力。 3.3.2 实时调度算法的分类实时调度算法的分类 1. 非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法。非抢占式轮转调度算法。 (2) 非抢占式优先调度算法。非抢占式优先调度算法。 基于时钟中断的抢占式优先权调度算法。基于时钟中断的抢占式优先权调度算法。 (2) 立即抢占立即抢占(Immediate Preemption)的优先权调度算法。的优先权调度算法。 2. 抢占式调度算法抢占式调度算法 (a) 非抢占轮转调度 当前进程实时进程 实时进程请求调度 实时进程枪占当前 进程，并立即执行 (d)

27、 立即抢占的优先权调度 调度时间 进程 1进程 2 实时进程要求调度 进程 n实时进程 调度实时进程运行 (b) 非抢占优先权调度 当前进程实时进程 实时进程请求调度当前进程运行完成 调度时间 当前进程 实时进程请求调度时钟中断到来时 调度时间 (c) 基于时钟中断抢占的优先权抢占调度 调度时间 实时进程 图图 3-6 实时进程调度实时进程调度 3.3.3 常用的几种实时调度算法常用的几种实时调度算法 1. 最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)算法算法 图图 3-7 EDF算法用于非抢占调度方式算法用于非抢占调度方式 1342 开始截止时

28、间 任务执行 任务到达 12 34 1342 t 2. 最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 该算法是根据任务紧急该算法是根据任务紧急(或松弛或松弛)的程度，来确定任务的优先级。任务的程度，来确定任务的优先级。任务 的紧急程度愈高，为该任务所赋予的优先级就愈高，的紧急程度愈高，为该任务所赋予的优先级就愈高， 以使之优先执行。以使之优先执行。 例如例如: 一个任务在一个任务在200ms时必须完成，而它本身所需的运行时间就有时必须完成，而它本身所需的运行时间就有100ms， 因此，调度程序必须在因此，调度程序必须在100 ms之前调度执行，该任务的

29、紧急程度之前调度执行，该任务的紧急程度(松弛程度松弛程度) 为为100 ms。又如，另一任务在。又如，另一任务在400 ms时必须完成，它本身需要运行时必须完成，它本身需要运行 150 ms ，则其松弛程度为，则其松弛程度为 250 ms。 在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列， 松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首 任务执行。任务执行。 该算法主要用于可抢占调度方式中。该算法主要用于可抢占调度方式中。 图图 3-8

30、A和和B任务每次必须完成的时间任务每次必须完成的时间 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 20406080100120140160 B1B2B3 t 0 假如在一个实时系统中，有两个周期性实时任务假如在一个实时系统中，有两个周期性实时任务A和和B，任务，任务A要求每要求每 20 ms执行一次，执行一次， 执行时间为执行时间为 10 ms；任务；任务B只要求每只要求每50 ms执行一次，执行时间为执行一次，执行时间为 25 ms。 在刚开始时在刚开始时(t1=0)， A1必须在必须在20ms时完成，而它本身运行又需时完成，而它本身运行又需 10 ms，可算出，可算出A

31、1的松弛度为的松弛度为10ms； B1必须在必须在50ms时完成，时完成， 而它本身运行就需而它本身运行就需25 ms，可算出，可算出B1的松弛度为的松弛度为25 ms， 故调度程序应先调度故调度程序应先调度A1执行。在执行。在t2=10 ms时，时，A2的松弛度可按下式算出：的松弛度可按下式算出： A2的松弛度的松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间 =40 ms-10 ms-10 ms=20 ms 图图 3-9 利用利用ELLF算法进行调度的情况算法进行调度的情况 t1 A 1(10) 10203040506080 t 0 t1 0 B 1(2

32、0) t2t3 70 A 2(10) A 3(10) A 4(10) t4t5t6t7t8 B 1(5) B 2(15) B 2(10) 第三章 处理机调度与死锁 3.4 多处理机系统中的调度多处理机系统中的调度 3.4.1 多处理器系统的类型多处理器系统的类型 (1) 紧密耦合(Tightly Coupted)MPS。 这通常是通过高速总线或高速交叉开关，来实现多个 处理器之间的互连的。它们共享主存储器系统和I/O设备， 并要求将主存储器划分为若干个能独立访问的存储器模块， 以便多个处理机能同时对主存进行访问。系统中的所有资 源和进程，都由操作系统实施统一的控制和管理。 第三章 处理机调度与

33、死锁 (2) 松散耦合(Loosely Coupled)MPS。 在松散耦合MPS中，通常是通过通道或通信线路，来 实现多台计算机之间的互连。每台计算机都有自己的存储 器和I/O设备，并配置了OS来管理本地资源和在本地运行 的进程。因此，每一台计算机都能独立地工作， 必要时可 通过通信线路与其它计算机交换信息，以及协调它们之间 的工作。 第三章 处理机调度与死锁 2. 对称多处理器系统和非对称多处理器系统对称多处理器系统和非对称多处理器系统 (1) 对称多处理器系统SMPS(Symmetric MultiProcessor System)。 在系统中所包含的各处理器单元，在功能和结构 上都是相

34、同的， 当前的绝大多数MPS都属于SMP系统。例 如，IBM公司的SR/6000 Model F50, 便是利用4片Power PC 处理器构成的。 (2) 非对称多处理器系统。在系统中有多种类型的处理 单元， 它们的功能和结构各不相同，其中只有一个主处理 器，有多个从处理器。 第三章 处理机调度与死锁 3.4.2 进程分配方式进程分配方式 1. 对称多处理器系统中的进程分配方式对称多处理器系统中的进程分配方式 在SMP系统中，所有的处理器都是相同的，因而可把所 有的处理器作为一个处理器池(Processor pool)，由调度程序 或基于处理器的请求， 将任何一个进程分配给池中的任何一 个处

35、理器去处理。在进行进程分配时，可采用以下两种方式 之一。 1) 静态分配(Static Assigenment)方式 2) 动态分配(Dynamic Assgement)方式 第三章 处理机调度与死锁 2. 非对称非对称MPS中的进程分配方式中的进程分配方式 对于非对称MPS， 其OS大多采用主从(Master-Slave) 式OS， 即OS的核心部分驻留在一台主机上(Master)， 而从 机(Slave)上只是用户程序， 进程调度只由主机执行。 每当 从机空闲时， 便向主机发送一索求进程的信号， 然后， 便 等待主机为它分配进程。 在主机中保持有一个就绪队列， 只要就绪队列不空， 主机便从

36、其队首摘下一进程分配给请 求的从机。从机接收到分配的进程后便运行该进程， 该进 程结束后从机又向主机发出请求。 第三章 处理机调度与死锁 3.4.3 进程进程(线程线程)调度方式调度方式 1. 自调度自调度(Self-Scheduling)方式方式 1) 自调度机制 在多处理器系统中，自调度方式是最简单的一种调度方 式。它是直接由单处理机环境下的调度方式演变而来的。 在系统中设置有一个公共的进程或线程就绪队列， 所有的 处理器在空闲时，都可自己到该队列中取得一进程(或线程) 来运行。在自调度方式中，可采用在单处理机环境下所用的 调度算法，如先来先服务(FCFS)调度算法、最高优先权优先 (FP

37、F)调度算法和抢占式最高优先权优先调度算法等。 第三章 处理机调度与死锁 2) 自调度方式的优点 自调度方式的主要优点表现为：首先，系统中的公共 就绪队列可按照单处理机系统中所采用的各种方式加以组 织； 其调度算法也可沿用单处理机系统所用的算法，亦即， 很容易将单处理机环境下的调度机制移植到多处理机系统 中， 故它仍然是当前多处理机系统中较常用的调度方式。 其次， 只要系统中有任务，或者说只要公共就绪队列不空， 就不会出现处理机空闲的情况，也不会发生处理器忙闲不 均的现象，因而有利于提高处理器的利用率。 第三章 处理机调度与死锁 3) 自调度方式的缺点 瓶颈问题。 (2) 低效性。 (3) 线

38、程切换频繁。 第三章 处理机调度与死锁 2. 成组调度成组调度(Gang Scheduling)方式方式 在成组调度时，如何为应用程序分配处理器时间， 1) 面向所有应用程序平均分配处理器时间 2) 面向所有线程平均分配处理器时间 图 3 - 10 两种分配处理器时间的方法 第三章 处理机调度与死锁 3. 专用处理器分配专用处理器分配(Dedicated Processor Assigement)方式方式 图 3-11 线程数对加速比的影响 123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 加速比 线程数

39、矩阵相乘 FFT 0 3.3 3.3 进程调度实例进程调度实例 ( (一）一） 一。一。VMSVMS进程调度进程调度 综合调度算法：综合调度算法：以优先级为基础的多级反馈队列。以优先级为基础的多级反馈队列。 VMS中的优先级：中的优先级： 1。硬件优先级（。硬件优先级（IPL）中断优先级，存储在硬件中断优先级，存储在硬件PCB中。中。 2。软件优先级。软件优先级 （0 31级）存储在软件级）存储在软件PCB中。中。 1631 实时优先级实时优先级（静态优先级静态优先级），用于实时进程。），用于实时进程。 不受时间片影响，进程一旦被调度，一直执行不受时间片影响，进程一旦被调度，一直执行 到到 结

40、束。结束。 0 15 正常正常优先级优先级 （动态优先级动态优先级），用于非实时进程，），用于非实时进程， 为每个为每个优先级队列设置不同的优先级队列设置不同的 时间片。时间片。优先级优先级 愈高，愈高，时间片愈短。时间片愈短。 系统中的进程按照系统中的进程按照优先级优先级排成排成32个就绪个就绪队列队列，系统总是按，系统总是按 FCFS算法算法先先调度调度当前当前优先级最高的优先级最高的队列中的进程。对实时队列中的进程。对实时 进程和正常进程采用不同的调度策略。进程和正常进程采用不同的调度策略。 3.3 3.3 进程调度实例进程调度实例 ( (二）二） 正常正常优先级进程（优先级进程（0 1

41、5）在创建时，系统为其分配了）在创建时，系统为其分配了 基本优先级基本优先级： 交互进程为交互进程为4，批处理进程为，批处理进程为3。 优先级提升优先级提升幅度的原则：幅度的原则： 随着进程等待时间增加，优先级提升幅度增加。随着进程等待时间增加，优先级提升幅度增加。 因进程类型而定；因进程类型而定；受受 I/O 限制的进程限制的进程提升幅度大于受提升幅度大于受 计算限制的进程。计算限制的进程。 VMSVMS中进程优先级的动态提升中进程优先级的动态提升 在进程运行过程中，优先级会有不同幅度（在进程运行过程中，优先级会有不同幅度（0 6）的提）的提 升，使进程获得调度的可能性。升，使进程获得调度的

42、可能性。 进程进程优先级下降优先级下降 ：当进程因为时间片到或者等待某事：当进程因为时间片到或者等待某事 件发生而释放件发生而释放CPU时，优先级下降。时，优先级下降。 优先级改变后的进程排到相应队列的队尾优先级改变后的进程排到相应队列的队尾 。 优先级队列优先级队列 31 30 15 16 14 0 静态优先级静态优先级动态优先级动态优先级 CPU 等等 待待 队队 列列 优优 先先 级级 下下 降降 进程按照进程按照优先级优先级排成排成32个就绪个就绪队列。队列。 每个每个就绪就绪队列按照队列按照FCFS算法排队。算法排队。 优先级越高时间片越小。优先级越高时间片越小。 3.3 3.3 进

43、程调度实例进程调度实例 ( (三）三） 进程的优先权分进程的优先权分31级（级（1 - 31），为动态优先级：在基），为动态优先级：在基 本优先级的基础上波动本优先级的基础上波动 + 2级。级。 基本优先权设置（基本优先权设置（4组）组） 优先权等级优先权等级 优先权范围优先权范围 Idle Idle （闲置闲置） 1 1 6 6 Normal Normal （标准）标准） 6 6 10 10 High High （高级）高级） 11 11 15 15 Realtime Realtime（实时）实时） 16 16 31 31 进程调度过程中优先权的动态提升有何实际意义？进程调度过程中优先权的动

44、态提升有何实际意义？ WINDOWS NT 的进程优先级的进程优先级 问问 题题 3.7 3.7 死锁的基本概念（一）死锁的基本概念（一） 死锁（死锁（deadlock） 是是OS的一种随机故障，的一种随机故障，是指两个或是指两个或 两个以上的进程都无限制的地等待永远不会出现的两个以上的进程都无限制的地等待永远不会出现的 事件而发生的状态。事件而发生的状态。 1、争夺资源引起死锁争夺资源引起死锁 例例1：P1，P2两个进程争夺打印机和读卡机。两个进程争夺打印机和读卡机。 一、死锁的原因死锁的原因 P1 P2 打印机读卡机 P1P1已经申请到打印机，已经申请到打印机， 又申请读卡机。又申请读卡机

45、。 P2P2已经申请到读卡机，已经申请到读卡机， 又申请打印机。又申请打印机。 打印机和读卡机为打印机和读卡机为 非剥夺性资源。非剥夺性资源。 例例3 3、 P1P1，P2P2，P3 P3 三个进程之间通信：三个进程之间通信： P1P1产生消息产生消息S1S1，接收，接收P3P3产生的消息产生的消息S3S3； P2P2产生消息产生消息S2S2，接收，接收P1P1产生的消息产生的消息S1S1； P3P3产生消息产生消息S3S3，接收，接收P2P2产生的消息产生的消息S2S2； 按以下次序运行：按以下次序运行： P1：Request（S3）；）；Release（S1） P2：Request（S1）

46、；）；Release（S2） P3：Request（S2）；）；Release（S3） 3.7 死锁的基本概念死锁的基本概念（二）（二） 2 2、进程推动顺序不当引起的死锁、进程推动顺序不当引起的死锁 P1 P3 P2 S2 S3 S1 P1 P2 P3 按照以上的顺序执行会产生死锁吗？按照以上的顺序执行会产生死锁吗？ ？问题？ 例例2 2、 在生产者在生产者消费者问题中如果交换两个消费者问题中如果交换两个P P操作操作 的次序，可能引起死锁。的次序，可能引起死锁。 S Si i临时性资源临时性资源 3.7 死锁的基本概念死锁的基本概念（三）（三） 生产者进程：生产者进程： 生产一个产品生产一

47、个产品 m ； . . . P（empty）；）； P（mutex）；）； 将产品将产品 m放入缓冲区；放入缓冲区； in ：=（in +1） mod n ； V （mutex）；）； V（ full）；）； 消费者进程：消费者进程： P （ full）；）； P （ mutex ）；）； 从缓冲区取产品从缓冲区取产品m； out ：=（out+1） mod n ； V （mutex）；）； V （empty）；）； 生产者生产者消费者问题算法：消费者问题算法： 3.7 死锁的基本概念死锁的基本概念（四）（四） 由于由于 产生死锁的根本原因是争夺共享资源，从而得产生死锁的根本原因是争夺共享资源

48、，从而得 到产生到产生死锁的必要条件是死锁的必要条件是： 二。二。死锁的必要条件死锁的必要条件 互斥条件互斥条件 进程互斥使用临界资源。进程互斥使用临界资源。 不剥夺条件不剥夺条件 资源只能由占有它的进程释放，不能资源只能由占有它的进程释放，不能 被其它进程剥夺。被其它进程剥夺。 非剥夺资源非剥夺资源 部分分配条件部分分配条件 进程在申请新资源的同时，保持对某进程在申请新资源的同时，保持对某 些资源的占有。些资源的占有。 环路等待条件环路等待条件 存在循环等待链，在链中每个进程都存在循环等待链，在链中每个进程都 在等待它的前一进程所持有的资源。在等待它的前一进程所持有的资源。 3.7 死锁的基

49、本概念死锁的基本概念（五）（五） 显然，如果出现死锁将对操作系统造成极大的危害，显然，如果出现死锁将对操作系统造成极大的危害， 甚至使系统瘫痪，如何解决死锁是操作系统设计的重要甚至使系统瘫痪，如何解决死锁是操作系统设计的重要 问题。问题。 限制并发进程对于资源的限制并发进程对于资源的 需求，破坏产生死需求，破坏产生死 锁的必锁的必 要条件。严格限制死锁的要条件。严格限制死锁的 发生。发生。 三。解决死锁的方法。解决死锁的方法 预防死锁预防死锁 避免死锁避免死锁 在资源的在资源的动态分配动态分配过程中，过程中， 采用某种算法防止系统进采用某种算法防止系统进 入不安全状态，避免死锁入不安全状态，避

50、免死锁 发生。发生。 检测与解除死锁检测与解除死锁 对资源的分配不加限制，系统定时运行对资源的分配不加限制，系统定时运行“死锁死锁 检测检测” 程序，如检测到死锁，设法加以解除。程序，如检测到死锁，设法加以解除。 3.7 死锁的基本概念死锁的基本概念（六）（六） 采用资源的静态分配策略，破坏采用资源的静态分配策略，破坏“部分分配部分分配”条件条件。 即只有当进程所需要的全部资源满足时，系统予以即只有当进程所需要的全部资源满足时，系统予以 一次分配。一次分配。 允许进程剥夺使用其他进程占有的资源，破坏允许进程剥夺使用其他进程占有的资源，破坏“不不 剥夺条件剥夺条件”。 进程动态申请资源，当进程申

51、请不到新资源时，应立进程动态申请资源，当进程申请不到新资源时，应立 即释放已占有的即释放已占有的 所有资源。所有资源。 采用资源顺序分配法，破坏采用资源顺序分配法，破坏“环路等待环路等待”条件。条件。 将系统中的所有资源按类型线性排队，并赋予唯将系统中的所有资源按类型线性排队，并赋予唯 一编号，进程申请资源时，严格按编号递增顺序分配。一编号，进程申请资源时，严格按编号递增顺序分配。 预防死锁预防死锁 3.7 死锁的基本概念死锁的基本概念（七）（七） 1）系统的安全状态）系统的安全状态 在分配资源时，分析计算系统的在分配资源时，分析计算系统的安全性安全性，避免系统，避免系统 进入不安全状态，则可

52、避免死锁。进入不安全状态，则可避免死锁。 系统状态安全系统状态安全 存在一个进程序列存在一个进程序列 P1，P2，。，。Pn ，如果系统按此，如果系统按此 顺序为每个进程分配它们所需的最大资源，而不造成顺序为每个进程分配它们所需的最大资源，而不造成 死锁，则称系统状态死锁，则称系统状态S（t）安全。）安全。 2 2）银行家算法）银行家算法 银行家算法是著名的银行家算法是著名的避免死锁的避免死锁的算法。其基本思算法。其基本思 想是：想是： O SO S 银行家银行家 进程进程 借贷的客户借贷的客户 资源资源 可周转的借贷资金可周转的借贷资金 避免死锁避免死锁 解除死锁解除死锁 一旦检测到死锁，应

53、立即消除，常用的方法有：一旦检测到死锁，应立即消除，常用的方法有： 1、撤消进程法、撤消进程法 逐个撤消所有死锁进程，直到解除死锁为止。逐个撤消所有死锁进程，直到解除死锁为止。 撤消进程的策略：撤消进程的策略： 按优先级；按优先级； 最小代价原则最小代价原则撤消进程数最少、撤消路径最短。撤消进程数最少、撤消路径最短。 2、挂起进程法挂起进程法 使用挂起使用挂起/ /激活机构挂起一些进程，剥夺它们所占有的激活机构挂起一些进程，剥夺它们所占有的 资源以解除死锁。资源以解除死锁。 问题问题 在解决死锁的几种方法中，你认为哪种方法既能够在解决死锁的几种方法中，你认为哪种方法既能够 解决死锁问题，对系统

54、效率牺牲也不大？解决死锁问题，对系统效率牺牲也不大？ 3.6.2 系统安全状态系统安全状态 1. 安全状态安全状态 称称P1, P2, , Pn序列为安全序列，序列为安全序列， 指系统能按某种进指系统能按某种进 程顺序程顺序(P1, P2, ，Pn)(来为每个进程来为每个进程Pi分配其所需资源，直至分配其所需资源，直至 满足每个进程对资源的最大需求，使每个进程都可顺利地完满足每个进程对资源的最大需求，使每个进程都可顺利地完 成。成。 如果系统无法找到这样一个安全序列，则称系统处于不安如果系统无法找到这样一个安全序列，则称系统处于不安 全状态。全状态。 2. 安全状态之例安全状态之例 我们通过一

55、个例子来说明安全性。假定系统中有三个进程我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和和P3， 共有共有12台磁带机。台磁带机。 进程进程P1总共要求总共要求10台磁带机，台磁带机，P2和和P3分别要求分别要求4台和台和9台。台。 假设在假设在T0时刻，进程时刻，进程P1、P2和和P3已分别获得已分别获得5台、台、2台和台和2台磁带机，台磁带机， 尚有尚有3台空闲未分配，如下表所示：台空闲未分配，如下表所示： 进 程 最 大 需 求 已 分 配 可 用 P1 P2 P3 10 4 9 5 2 2 3 3. 由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安

56、全序列分配资源，则系统可能会由安全状态进入不如果不按照安全序列分配资源，则系统可能会由安全状态进入不 安全状态。安全状态。 例如，在例如，在T0时刻以后，时刻以后，P3又请求又请求1台磁带机，若此时系统把剩余台磁带机，若此时系统把剩余3台台 中的中的1台分配给台分配给P3，则系统便进入不安全状态。，则系统便进入不安全状态。 因为，此时也无法再因为，此时也无法再 找到一个安全序列找到一个安全序列; 例如，把其余的例如，把其余的2台分配给台分配给P2，这样，在，这样，在P2完成后只能释放出完成后只能释放出4台，台， 既不能满足既不能满足P1尚需尚需5台的要求，也不能满足台的要求，也不能满足P3尚需

57、尚需6台的要求，致使它台的要求，致使它 们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结 果导致死锁。果导致死锁。 3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁 1. 银行家算法中的数据结构银行家算法中的数据结构 (1) 可利用资源向量可利用资源向量Available 这是一个含有这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源个元素的数组，其中的每一个元素代表一类可利用的资源 数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资数目，其初始值是系统中所配置的该类全部可用资源的数

58、目，其数值随该类资 源的分配和回收而动态地改变。源的分配和回收而动态地改变。 如果如果Availablej=K，则表示系统中现有，则表示系统中现有Rj类资源类资源K个。个。 (2) 最大需求矩阵最大需求矩阵Max 这是一个这是一个nm的矩阵，它定义了系统中的矩阵，它定义了系统中n个进程中的每一个进程对个进程中的每一个进程对 m类资源的最大需求。如果类资源的最大需求。如果Maxi,j=K，则表示进程，则表示进程i需要需要Rj类资源的最类资源的最 大数目为大数目为K。 (3) 分配矩阵分配矩阵Allocation 这也是一个这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配的矩阵，它定义了系

59、统中每一类资源当前已分配 给每一进程的资源数。如果给每一进程的资源数。如果Allocationi,j=K，则表示进程，则表示进程i当前已分得当前已分得 Rj类资源的数目为类资源的数目为K。 (4) 需求矩阵需求矩阵Need 这也是一个这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。的矩阵，用以表示每一个进程尚需的各类资源数。 如果如果Needi,j=K，则表示进程，则表示进程i还需要还需要Rj类资源类资源K个，方能完成其任务。个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j 2. 银行家算法银行家算法 设设Requesti是进程是进程Pi的请求向量，如果

60、的请求向量，如果Requestij=K，表示进程，表示进程Pi需要需要 K个个Rj类型的资源。当类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：发出资源请求后，系统按下述步骤进行检查： (1) 如果如果RequestijNeedi,j，便转向步骤，便转向步骤2；否则认为出错，因为；否则认为出错，因为 它所需要的资源数已超过它所宣布的最大值。它所需要的资源数已超过它所宣布的最大值。 (2) 如果如果RequestijAvailablej，便转向步骤，便转向步骤(3)；否则，；否则， 表示尚无表示尚无 足够资源，足够资源，Pi须等待。须等待。 (3) 系统试探着把资源分配给进程系统试探着