第3章 处理机调度7.ppt

《第3章 处理机调度7.ppt》由会员分享，可在线阅读，更多相关《第3章 处理机调度7.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统原理操作系统原理Principle of Operating System 精品课程精品课程第第3 3章章 处理机调度处理机调度 3.1 3.1 概述概述 3.2 3.2 作业调度作业调度 3.3 3.3 进程调度进程调度 3.4 3.4 实时调度实时调度 3.5 3.5 多处理机调度多处理机调度 3.6 3.6 实例：实例：WindowsWindows调度调度本章主要内本章主要内容容兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 处理机调度（处理机调度（CPU schedul

2、ing）是指）是指CPU资源在资源在可运行实体间的分配。在多道程序系统中，通常可运行实体间的分配。在多道程序系统中，通常会有多个进程或线程同时竞争会有多个进程或线程同时竞争CPU。如果只有一。如果只有一个个CPU可用，就必须选择下一个可用的进程或线可用，就必须选择下一个可用的进程或线程。在操作系统中，完成选择工作的这一部分称程。在操作系统中，完成选择工作的这一部分称为调度程序（为调度程序（scheduling），该程序使用的算法称），该程序使用的算法称为调度算法（为调度算法（scheduling algorithm）。）。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作

3、系统原理Principle of Operating System 精品课程精品课程3.1 3.1 概述概述3.1.1 3.1.1 调度层次调度层次 3.1.2 3.1.2 调度准则调度准则 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.1 3.1 概述概述 3.1.1 3.1.1 调度层次调度层次 3.1.2 3.1.2 调度

4、准则调度准则 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 为为了了比比较较CPU调调度度算算法法，人人们们提提出出了了很很多多调调度度准准则则（也也称称为为评评价价准准则则），用用来来进进行行比比较较特特征征对对确确定定最佳算法时产生的影响。常用的准则如下：最佳算法时产生的影响。常用的准则如下：CPU利用率 吞吐量 周转时间 就绪等待时间 响应时间 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating Syst

5、em 精品课程精品课程第第3 3章章 处理机调度处理机调度 3.1 3.1 概述概述 3.2 3.2 作业调度作业调度 3.3 3.3 进程调度进程调度 3.4 3.4 实时调度实时调度 3.5 3.5 多处理机调度多处理机调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 作业（作业（Job）是用户提交给操作系统计算）是用户提交给操作系统计算的一个独立任务。在批处理系统中，作业的一个独立任务。在批处理系统中，作业进入系统后先驻留在外存上，因此，需要进入系统后先驻留在外存上，因此，需

6、要由作业调度来将它们分批地装入内存。因由作业调度来将它们分批地装入内存。因此作业调度是适用于批处理系统的一种调此作业调度是适用于批处理系统的一种调度方式。度方式。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.2 3.2 作业调度作业调度3.2.1 3.2.1 作业控制快作业控制快 3.2.2 3.2.2 作业状态作业状态 3.2.3 3.2.3 作业调度功能作业调度功能 3.2.4 3.2.4 作业调度时机作业调度时机 3.2.5 3.2.5 作业调度算法作业调度算法 兰州理工大学

7、计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 在多道批处理系统中通常有上百个作业被放在输入井（外存）中。为了管理和调度作业，系统为每个作业设置了一个作业控制块（JCB），它记录该作业的有关信息。不同系统的JCB的组成内容有所区别，主要包括：作业名、资源要求、资源使用情况、类型级别、状态等。JCB是作业在系统中存在的唯一标志。作业进入系统时由spooling系统为每个作业建立一个JCB；当作业退出系统时，其JCB也一起被撤销。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作

8、系统原理Principle of Operating System 精品课程精品课程3.2 3.2 作业调度作业调度3.2.1 3.2.1 作业控制快作业控制快 3.2.2 3.2.2 作业状态作业状态 3.2.3 3.2.3 作业调度功能作业调度功能 3.2.4 3.2.4 作业调度时机作业调度时机 3.2.5 3.2.5 作业调度算法作业调度算法 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Princ

9、iple of Operating System 精品课程精品课程3.2 3.2 作业调度作业调度3.2.1 3.2.1 作业控制快作业控制快 3.2.2 3.2.2 作业状态作业状态 3.2.3 3.2.3 作业调度功能作业调度功能 3.2.4 3.2.4 作业调度时机作业调度时机 3.2.5 3.2.5 作业调度算法作业调度算法 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程作业调度的主要功能作业调度的主要功能:记录系统中各个作业的情况按照某种调度算法从后备作业队列中选取一个或多个

10、作业 为被选中的作业分配主存和外设资源 为作业开始运行做好一切准备工作在作业运行完成或由于某种原因需要撤离系统时，作业调度程序还要完成作业的善后处理工作 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.2 3.2 作业调度作业调度3.2.1 3.2.1 作业控制快作业控制快 3.2.2 3.2.2 作业状态作业状态 3.2.3 3.2.3 作业调度功能作业调度功能 3.2.4 3.2.4 作业调度时机作业调度时机 3.2.5 3.2.5 作业调度算法作业调度算法 兰州理工大学计算机与

11、通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程调度一个作业的时机有三种：调度一个作业的时机有三种：作业完成后有新作业提交 处理机利用率较低 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.2 3.2 作业调度作业调度3.2.1 3.2.1 作业控制快作业控制快 3.2.2 3.2.2 作业状态作业状态 3.2.3 3.2.3 作业调度功能作业调度功能 3.2.4 3.2.4 作业调度时机作业调度

12、时机 3.2.5 3.2.5 作业调度算法作业调度算法 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 所谓调度算法是指系统依照某种原则或策略所谓调度算法是指系统依照某种原则或策略从后备作业队列中选取作业的方法。以单道批从后备作业队列中选取作业的方法。以单道批处理系统为例，常采用的作业调度算法有：处理系统为例，常采用的作业调度算法有：先来先服务（FCFS）算法最短作业优先（SJF）算法（抢占式SJF-SRTF）例例1：有三个作业同时到达系统，它们投入运行时所需CPU时间分别为：20ms

13、、5ms、2ms。例例2：四个作业到达系统时间/所需CPU时间：作业1-0/7，作业2-1/3，作业3-2/4，作业4-3/5。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 例例3:3:四个作业到达系统时间/所需CPU时间:作业1-0/8，作业2-2/6，作业3-4/2，作业4-6/4。分别用FCFS、SJF和HRF算法进行调度时的调度顺序是什么？平均周转时间为多少？最高响应比优先（HRF）算法 响应比 1+已等待时间/估计运行时间均衡调度算法 兰州理工大学计算机与通信学院兰州理工大

14、学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程第第3 3章章 处理机调度处理机调度 3.1 3.1 概述概述 3.2 3.2 作业调度作业调度 3.3 3.3 进程调度进程调度 3.4 3.4 实时调度实时调度 3.5 3.5 多处理机调度多处理机调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 进程调度是任何一种操作系统都必须具有的进程调度是任何一种操作系统都必须具有的功能，它在很大程度上决定了系统的性能。因

15、此，功能，它在很大程度上决定了系统的性能。因此，如何把处理机有效地分配给进程、如何在多个请如何把处理机有效地分配给进程、如何在多个请求进程中选择某个进程运行，都是进程调度需要求进程中选择某个进程运行，都是进程调度需要解决的问题。解决的问题。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.3 3.3 进程调度进程调度3.3.1 3.3.1 进程调度功能进程调度功能 3.3.2 3.3.2 进程调度时机进程调度时机 3.3.3 3.3.3 进程调度方式进程调度方式 3.3.4 3.3.4

16、 进程调度算法进程调度算法 3.3.5 3.3.5 进程调度过程进程调度过程 3.3.6 3.3.6 线程调度线程调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 进程调度根据进程调度根据PCB描述的信息进行调度，其描述的信息进行调度，其主要功能如下：主要功能如下：记录和保持系统中所有进程的有关情况和状态特征 决定分配策略 实施处理机的分配和回收兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System

17、 精品课程精品课程3.3 3.3 进程调度进程调度3.3.1 3.3.1 进程调度功能进程调度功能 3.3.2 3.3.2 进程调度时机进程调度时机 3.3.3 3.3.3 进程调度方式进程调度方式 3.3.4 3.3.4 进程调度算法进程调度算法 3.3.5 3.3.5 进程调度过程进程调度过程 3.3.6 3.3.6 线程调度线程调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 在什么情况下，现行进程放弃处理机，而重新引起处理机的调度。主要有以下几种情况：在创建一个新进程后，需

18、要决定是运行父进程还是运行子进程 在一个进程退出时必须作出调度 当一个运行进程阻塞在I/O或信号量上或由于其它原因阻塞时，必须选择另一个进程运行 在一个I/O中断发生时，必须作出调度 在分时系统中，现行进程的时间片用完的情况下，需要重新选择新进程在处理机上运行 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.3 3.3 进程调度进程调度3.3.1 3.3.1 进程调度功能进程调度功能 3.3.2 3.3.2 进程调度时机进程调度时机 3.3.3 3.3.3 进程调度方式进程调度方式

19、3.3.4 3.3.4 进程调度算法进程调度算法 3.3.5 3.3.5 进程调度过程进程调度过程 3.3.6 3.3.6 线程调度线程调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程从调度方式上看，进程调度有两种类型：从调度方式上看，进程调度有两种类型：抢占式调度：又称为剥夺调度方式，指当一个进程正在处理机上执行时，系统可以根据规定的原则剥夺分配给它的CPU并分配给其它进程使用。非抢占式调度：又称为非剥夺调度方式，指挑选一个进程或线程运行后，该进程或线程一直占有CPU，直至被阻塞

20、，或者直到该进程或线程自动释放CPU为止。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.3 3.3 进程调度进程调度3.3.1 3.3.1 进程调度功能进程调度功能 3.3.2 3.3.2 进程调度时机进程调度时机 3.3.3 3.3.3 进程调度方式进程调度方式 3.3.4 3.3.4 进程调度算法进程调度算法 3.3.5 3.3.5 进程调度过程进程调度过程 3.3.6 3.3.6 线程调度线程调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原

21、理Principle of Operating System 精品课程精品课程 进程调度算法要解决两个问题，其一是进程调度算法要解决两个问题，其一是选择哪个进程，其二是选中它以后，如何选择哪个进程，其二是选中它以后，如何给它分配处理机，以及该进程能占用处理给它分配处理机，以及该进程能占用处理机多久。第一个问题是选择方式，第二个机多久。第一个问题是选择方式，第二个问题是调度方式。问题是调度方式。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程1 1先来先服务（先来先服务（FCFSFCFS）

22、算法）算法 FCFS算法就是每次从就绪队列中选择一个最先进入该队列的进程调度，把CPU分给它，令其投入运行。该进程一直运行下去，直至完成或者由于某些原因而被阻塞才放弃CPU。这样，当一个进程就绪队列时，它的PCB就链入就绪队列的末尾。每次进程调度时就把队头进程从该队列中摘下，分给它CPU，使它运行。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程2 2时间片轮转（时间片轮转（TRRTRR）算法）算法 主要用于分时系统中的进程调度。每当执行进程调度时，调度程序总是选出就绪队列的队首进程，让

23、它在CPU上运行一个时间片的时间。时间片是一个小的时间单位，通常为10至100ms数量级。当进程用完分给它的时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，并把它放入就绪队列的末尾；然后，再把CPU分给就绪队列的队首进程，同样也让它运行一个时间片。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程例例：有四个进程A，B，C和D。设它们依次进入就绪队列，但彼此相差时间很少，可以近似地认为“同时”到达。四个进程分别需要运行12、5、3和6个时间单位。试表示出时间片q等于1和q等

24、于4时的运行情况。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3 3高优先级优先调度算法高优先级优先调度算法 利用优先级调度算法时，给每一个进程确定一个优先级，在进行进程调度时，从就绪队列中选出优先级最高的进程，把CPU分配给它使用。非抢占式优先级法。抢占式优先级法。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 两种确定进程优先级的方式：静态方式：是在创建进程时就确定下来，

25、而且在进程的整个运行期间保持不变 动态方式：是随着进程的推进而不断改变的。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 例例：有5个进程P1、P2、P3、P4、P5，它们同时依次进入就绪队列，它们的优先数和需要的处理机的时间分别为：P1-20/6，P2-2/2，P3-4/6，P4-2/8，P5-10/4，忽略进程调度所花的时间，要求：试分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序。分别计算各进程在就绪队列中的周转时间和平均周转时间。兰州理工大学计算机与通信学院兰

26、州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程4 4多级反馈队列调度算法多级反馈队列调度算法 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程5 5保证调度保证调度 一种实际并容易实现的保证是：若系统工作时有n个用户登录，则每个用户将获得CPU处理能力的1/n。类似地，在一个有n个进程的单用户系统中，若所有的进程都是平等的，则每个进程也将获得CPU处理能力的1/n。兰州理工大学计算机与通信学院兰州理工大学计算

27、机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程6 6彩票调度算法彩票调度算法 基本思想是为进程发放针对系统各种资源的彩票。当调度算法需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。对于CPU调度，系统可能每秒钟抽多次（如50次）彩票，每次获奖者可以获得一个时间片（如20ms）的运行时间。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程7 7公平分享调度公平分享调度 体现对用户的公平性，每个用户得到的CPU

28、时间都差不多，而调度程序需要一种强制的方式选择进程。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.3 3.3 进程调度进程调度3.3.1 3.3.1 进程调度功能进程调度功能 3.3.2 3.3.2 进程调度时机进程调度时机 3.3.3 3.3.3 进程调度方式进程调度方式 3.3.4 3.3.4 进程调度算法进程调度算法 3.3.5 3.3.5 进程调度过程进程调度过程 3.3.6 3.3.6 线程调度线程调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理

29、操作系统原理Principle of Operating System 精品课程精品课程 在进程调度时，处理机调度需要经历以下三在进程调度时，处理机调度需要经历以下三个主要步骤：个主要步骤：保存“下降”进程现场选择将要运行的进程“上升”进程 恢复“上升”进程的现场兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.3 3.3 进程调度进程调度3.3.1 3.3.1 进程调度功能进程调度功能 3.3.2 3.3.2 进程调度时机进程调度时机 3.3.3 3.3.3 进程调度方式进程调度方式

30、 3.3.4 3.3.4 进程调度算法进程调度算法 3.3.5 3.3.5 进程调度过程进程调度过程 3.3.6 3.3.6 线程调度线程调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 线程调度的主要功能是选择一个适当的线程到处理机上去执行并进行描述表的切换。对于用户级线程，内核并不知道线程的存在，所以内核还是和以前一样工作，即采用前面所介绍的方法进行进程调度。对于内核级线程，是由内核选择一个特定的线程运行，它不用考虑该线程属于哪个进程，不过，如果有必要考虑的话，内核也可以考虑

31、兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程第第3 3章章 处理机调度处理机调度 3.1 3.1 概述概述 3.2 3.2 作业调度作业调度 3.3 3.3 进程调度进程调度 3.4 3.4 实时调度实时调度 3.5 3.5 多处理机调度多处理机调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 实时系统是一种时间起着主导作用的系统。实时系统是一种时间起着主导作用的系统。也

32、就是说，在实时系统中，总是存在着若干也就是说，在实时系统中，总是存在着若干带有某种程度紧迫性的实时进程，因此，对带有某种程度紧迫性的实时进程，因此，对实时系统中的调度也就提出了某些特殊的要实时系统中的调度也就提出了某些特殊的要求。求。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.4 3.4 实时调度实时调度3.4.1 3.4.1 实时调度的要求实时调度的要求 3.4.2 3.4.2 实时任务的分类实时任务的分类 3.4.3 3.4.3 实时调度算法实时调度算法 兰州理工大学计算机与

33、通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 实时系统通常可以分为硬实时和软实时两实时系统通常可以分为硬实时和软实时两种，前者的含义是必须满足绝对的截止时间，种，前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。在实时系统中，为保证系统能但是可以容忍。在实时系统中，为保证系统能够正常工作，实时调度必须能满足对于截止时够正常工作，实时调度必须能满足对于截止时间的限制，于是，对实时系统提出了以下几方间的限制，于是，对实时系统提出

34、了以下几方面的要求：面的要求：兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程提供必要的调度信息：就绪时间；开始截止时间和完成截止时间；处理时间；资源需求；优先级。调度方式：在实时系统中，广泛采用抢占式调度方式，特别是对那些要求严格的实时系统；对于一些小的实时系统，如果能预知任务的开始截止时间，则实时任务的调度也可采用非剥夺式调度。具有快速响应中断的能力 快速的任务分配能力兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Opera

35、ting System 精品课程精品课程3.4 3.4 实时调度实时调度3.4.1 3.4.1 实时调度的要求实时调度的要求 3.4.2 3.4.2 实时任务的分类实时任务的分类 3.4.3 3.4.3 实时调度算法实时调度算法 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程1根据任务到达时刻的规律分类：周期任务间发任务非周期任务2 根据对截止时间的要求分为类：硬实时任务软实时任务兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of

36、Operating System 精品课程精品课程3.4 3.4 实时调度实时调度3.4.1 3.4.1 实时调度的要求实时调度的要求 3.4.2 3.4.2 实时任务的分类实时任务的分类 3.4.3 3.4.3 实时调度算法实时调度算法 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 根据实时任务的特性可以将实时调度方法分为根据实时任务的特性可以将实时调度方法分为两大类：静态任务调度、动态任务调度。两大类：静态任务调度、动态任务调度。兰州理工大学计算机与通信学院兰州理工大学计算机与通

37、信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程1 1静态调度算法静态调度算法 常用的是静态优先级调度算法，此算法给系统中能够运行的所有任务都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期、用户优先级或者其它预先确定的策略。典型的静态调度算法有固定优先级调度算法、时钟驱动调度算法和单调速率（RM）算法。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 固定优先级调度算法。广泛应用于实时系统和内核中，

38、每个任务在运行之前都已经分配好固定的静态优先级。时钟驱动调度方法。时钟驱动调度是指在系统开始执行之前，选择一些特定的时刻，在这些时刻决定哪一个作业在何时执行。单调速率（RM）调度算法。它根据任务执行周期的长短来决定调度优先级，执行周期小的任务具有较高的优先级。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程2 2动态调度算法动态调度算法 根据任务的资源需求来动态地分配任务的优先级。这类算法是在运行期间根据目前已处于就绪态的各个任务的相关属性来决定当前的调度序列。典型的动态调度算法有最小松

39、弛度算法、最早截止时间优先算法等。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 最小松弛度算法一个任务A的第i次执行的松弛度FA(i)的计算公式是FA(i)=iTA-Tsi-T松弛度越小，说明任务的截止时间离当前时间越近。系统可以按照最小松弛度优先原则进行调度，相应的算法称为最小剩余时间SRT调度算法。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 最早截止时间优先算法抢占式

40、EDF调度算法 它是一个动态优先级驱动的调度算法，其中分配给每个任务的优先级根据它们当前对最终期限的要求而定。当前请求的最终期限最近的任务具有最高的优先级，而请求最终期限最远的任务被分配最低优先级。对于含有n个任务的任务集，算法的可调度条件是处理机利用率满足下面公式：兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程非抢占式EDF调度算法 适用于周期性和非周期性任务，其中非周期性任务可以在任何时间被唤醒，但需指定它们连续两次被唤醒之间的时间间隔，一个任务一旦执行就要等到执行完成。调度程序只

41、是在一个任务执行完成后才决定下一个要执行的任务。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3 3各种类型实时任务的混合调度各种类型实时任务的混合调度 下面是几种典型的混合调度方法：后台处理（Background Processing）法 基于服务器（Serve Based）的方法：又称为带宽预留算法。可以归结为固定优先级服务器算法与动态优先级服务器算法。基于空闲时间的方法：主要包括空闲时间偷取法、时间片移位法与双重优先级法。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操

42、作系统原理操作系统原理Principle of Operating System 精品课程精品课程第第3 3章章 处理机调度处理机调度 3.1 3.1 概述概述 3.2 3.2 作业调度作业调度 3.3 3.3 进程调度进程调度 3.4 3.4 实时调度实时调度 3.5 3.5 多处理机调度多处理机调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 当系统中有多台处理机时，进程调度是二维的，当系统中有多台处理机时，进程调度是二维的，即调度程序要解决的问题不仅是决定哪一个进即调度程序要

43、解决的问题不仅是决定哪一个进程运行，同时还要决定在哪一个程运行，同时还要决定在哪一个CPU上运行。上运行。有些系统中的进程是不相关即独立的，而有些有些系统中的进程是不相关即独立的，而有些系统中的进程是成组的。系统中的进程是成组的。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.5 3.5 多处理机调度多处理机调度3.5.1 3.5.1 不相关进程的调度不相关进程的调度 3.5.2 3.5.2 相关进程的调度相关进程的调度 3.5.3 3.5.3 群调度群调度 兰州理工大学计算机与通信

44、学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 操作系统处理不相关进程最简单且常用的方法是采用负载共享调度算法。如果有多个CPU同时处于空闲状态，则必须互斥访问就绪队列，此时就绪队列成为影响系统性能的瓶颈资源。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 利用这种调度策略，有下面的缺点，一是随着CPU数量的增加会引起对系统级就绪队列的潜在竞争；二是当进程由于I/O阻塞时引起的进程切换代价较高，比如分

45、时系统中当时间片到时，就要发生进程切换；另外假设某个进程持有自旋锁，那么直到该进程再次被调度并且释放该锁之前，其它等待这个自旋锁的CPU只是浪费其轮转时间片。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 为了避免这种情况，可以采用“灵巧调度”的方法。即获得自旋锁的进程设置一个进程标志表示它目前有一个自旋锁，当它释放该自旋锁时，就清除该标志。这样调度程序就不用停止持有自旋锁的进程，相反，调度程序会给予稍多一些的时间让该进程完成临界区的工作并能够释放自旋锁。“亲和调度”的方法，其基本思想

46、是进行一系列严格的努力使一个进程在它前一次运行过的CPU上运行。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.5 3.5 多处理机调度多处理机调度3.5.1 3.5.1 不相关进程的调度不相关进程的调度 3.5.2 3.5.2 相关进程的调度相关进程的调度 3.5.3 3.5.3 群调度群调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 一个含有多个相关进程的作业或者包

47、含多个线程的进一个含有多个相关进程的作业或者包含多个线程的进程，基本上采用相同的处理方法。在多个程，基本上采用相同的处理方法。在多个CPU上同时上同时调度多个进程或线程称为空间共享。调度多个进程或线程称为空间共享。最简单的空间共享算法是：假设一次创建了一组相关的进程或线程，在其创建时，调度程序检查是否有相同数量的空闲CPU存在，如果有，每个进程或线程都获得CPU（即非多道程序处理）开兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 始运行；如果没有足够的CPU，就没有进程或线程开始运行，

48、直到有足够的CPU时为止。每个进程或线程拥有其CPU直到其运行结束，然后该CPU被送回可用CPU池中。如果有一个进程或线程被阻塞（如I/O）后，它继续占有CPU，该CPU一直空闲直到该进程或线程被唤醒。在下一批相关进程或线程出现时，应用相同的算法。在任何一个时刻，全部CPU被静态地划分成若干个分区，每个分区只运行一个进程或线程。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程3.5 3.5 多处理机调度多处理机调度3.5.1 3.5.1 不相关进程的调度不相关进程的调度 3.5.2 3.

49、5.2 相关进程的调度相关进程的调度 3.5.3 3.5.3 群调度群调度 兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 群调度的基本思想是：把一组进程（或一个进群调度的基本思想是：把一组进程（或一个进程的所有线程）在同一时间一次性调度到一组程的所有线程）在同一时间一次性调度到一组处理机上运行。具体描述为：处理机上运行。具体描述为：1把一组相关进程作为一个单位，即一个群一起调度；2一个群中的所有成员在不同分时处理的CPU上同时运行；3群中的所有成员一起开始和结束其时间片。兰州理工大学

50、计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精品课程精品课程 群调度的关键是同步调度所有的CPU，也就是说，在把CPU时间划分为离散的时间片后，在每一个新的时间片开始时，所有的CPU都重新调度，在每个CPU上都开始一个新的进程或线程。在后续的时间片开始时，另一个调度事件发生。在两个时间片中间没有调度行为。即使某个线程被阻塞，它的CPU也保持空闲，直到对应的时间片结束为止。兰州理工大学计算机与通信学院兰州理工大学计算机与通信学院操作系统原理操作系统原理Principle of Operating System 精