O第3章处理机调度

2020-03-01 145浏览

1.操作系统原理 Principle of Operating System 精品课程第 3 章处理机调度 3.1 概述 3.2 作业调度 3.3 进程调度 3.4 实时调度 3.5 多处理机调度本章主要内 3.6 实例： Windows 调度容
2.2019年5月14日操作系统原理 Principle of Operating System 精品课程处理机调度（ CPU scheduling ）是指 CPU 资源在可运行实体间的分配。在多道程序系统中，通常会有多个进程或线程同时竞争 CPU 。如果只有一个 CPU 可用，就必须选择下一个可用的进程或线程。在操作系统中，完成选择工作的这一部分称为调度程序（ scheduling ），该程序使用的算法称为调度算法（ scheduling algorithm ）。
3.兰州理工大学计算机与通信学院操作系统原理 2019年5月14日 Principle of Operating System 3.1.1 调度层次 3.1.2 调度准则精品课程
4.2019年5月14日
5.2019年5月14日操作系统原理 Principle of Operating System 3.1.1 调度层次 3.1.2 调度准则精品课程
6.2019年5月14日为了比较 CPU 调度算法，人们提出了很多调度准则（也称为评价准则），用来进行比较特征对确定最佳算法时产生的影响。常用的准则如下： CPU 利用率 吞吐量 周转时间 就绪等待时间 响应时间
7.操作系统原理 Principle of Operating System 第 3 章处理机调度 3.1 概述 3.2 作业调度 3.3 进程调度 3.4 实时调度 3.5 多处理机调度精品课程
8.2019年5月14日操作系统原理 Principle of Operating System 精品课程作业（ Job ）是用户提交给操作系统计算的一个独立任务。在批处理系统中，作业进入系统后先驻留在外存上，因此，需要由作业调度来将它们分批地装入内存。因此作业调度是适用于批处理系统的一种调度方式。
9.兰州理工大学计算机与通信学院操作系统原理 2019年5月14日 Principle of Operating System 3.2.1 作业控制快 3.2.2 作业状态 3.2.3 作业调度功能 3.2.4 作业调度时机 3.2.5 作业调度算法精品课程
10.2019年5月14日操作系统原理 Principle of Operating System 精品课程在多道批处理系统中通常有上百个作业被放在输入井（外存）中。为了管理和调度作业，系统为每个作业设置了一个作业控制块（ JCB ），它记录该作业的有关信息。不同系统的 JCB 的组成内容有所区别，主要包括：作业名、资源要求、资源使用情况、类型级别、状态等。 JCB 是作业在系统中存在的唯一标志。作业进入系统时由 spooling 系统为每个作业建立一个 JCB ；当作业退出系统时，其 JCB 也一起被撤销。
11.2019年5月14日操作系统原理 Principle of Operating System 3.2.1 作业控制快 3.2.2 作业状态 3.2.3 作业调度功能 3.2.4 作业调度时机 3.2.5 作业调度算法精品课程
12.2019年5月14日操作系统原理 Principle of Operating System 精品课程
13.2019年5月14日操作系统原理 Principle of Operating System 3.2.1 作业控制快 3.2.2 作业状态 3.2.3 作业调度功能 3.2.4 作业调度时机 3.2.5 作业调度算法精品课程
14.兰州理工大学计算机与通信学院操作系统原理 2019年5月14日 Principle of Operating System 精品课程  记录系统中各个作业的情况  按照某种调度算法从后备作业队列中选取一个或多个作业  为被选中的作业分配主存和外设资源  为作业开始运行做好一切准备工作  在作业运行完成或由于某种原因需要撤离系统时，作业调度程序还要完成作业的善后处理工作
15.2019年5月14日操作系统原理 Principle of Operating System 3.2.1 作业控制快 3.2.2 作业状态 3.2.3 作业调度功能 3.2.4 作业调度时机 3.2.5 作业调度算法精品课程
16.2019年5月14日操作系统原理 Principle of Operating System  作业完成后  有新作业提交  处理机利用率较低精品课程
17.兰州理工大学计算机与通信学院操作系统原理 2019年5月14日 Principle of Operating System 3.2.1 作业控制快 3.2.2 作业状态 3.2.3 作业调度功能 3.2.4 作业调度时机 3.2.5 作业调度算法精品课程
18.2019年5月14日操作系统原理 Principle of Operating System 精品课程  先来先服务（ FCFS ）算法  最短作业优先（ SJF ）算法（抢占式 SJF-SRTF ）例 1 ：有三个作业同时到达系统，它们投入运行时所需 CPU 时间分别为： 20ms 、 5ms 、 2ms 。例 2 ：四个作业到达系统时间 / 所需 CPU 时间：
19.2019年5月14日操作系统原理作业情况调度算法 FCFS (a) SJF (b) 精品课程 Principle of Operating System 进程名 A B C D E 到达时间 0 1 2 3 4 服务时间 4 3 5 2 4 完成时间周转时间带权周转时间完成时间周转时间带权周转时间 4 4 1 4 4 1 7 6 2 9 8 2.67 12 10 2 18 16 3.1 14 11 5.5 6 3 1.5 18 14 3.5 13 9 2.25 平均 9 2.8 8 2.1
20.2019年5月14日操作系统原理 Principle of Operating System 最高响应比优先（ HRF ）算法响应比＝ 1+ 已等待时间 / 估计运行时间精品课程
21.操作系统原理 Principle of Operating System 第 3 章处理机调度 3.1 概述 3.2 作业调度 3.3 进程调度 3.4 实时调度 3.5 多处理机调度精品课程
22.2019年5月14日进程调度是任何一种操作系统都必须具有的功能，它在很大程度上决定了系统的性能。因此，如何把处理机有效地分配给进程、如何在多个请求进程中选择某个进程运行，都是进程调度需要解决的问题。
23.兰州理工大学计算机与通信学院操作系统原理 2019年5月14日 Principle of Operating System 3.3.1 进程调度功能 3.3.2 进程调度时机 3.3.3 进程调度方式 3.3.4 进程调度算法 3.3.5 进程调度过程 3.3.6 线程调度精品课程
24.兰州理工大学计算机与通信学院操作系统原理  2019年5月14日 Principle of Operating System 精品课程记录和保持系统中所有进程的有关情况和状态特征  决定分配策略  实施处理机的分配和回收
25.2019年5月14日操作系统原理 Principle of Operating System 3.3.1 进程调度功能 3.3.2 进程调度时机 3.3.3 进程调度方式 3.3.4 进程调度算法 3.3.5 进程调度过程 3.3.6 线程调度精品课程
26.2019年5月14日操作系统原理  Principle of Operating System 精品课程在创建一个新进程后，需要决定是运行父进程还是运行子进程  在一个进程退出时必须作出调度  当一个运行进程阻塞在 I/O 或信号量上或由于其它原因阻塞时，必须选择另一个进程运行  在一个 I/O 中断发生时，必须作出调度  在分时系统中，现行进程的时间片用完的情况下，需要重新选择新进程在处理机上运行
27.2019年5月14日操作系统原理 Principle of Operating System 3.3.1 进程调度功能 3.3.2 进程调度时机 3.3.3 进程调度方式 3.3.4 进程调度算法 3.3.5 进程调度过程 3.3.6 线程调度精品课程
28.2019年5月14日操作系统原理  Principle of Operating System 精品课程抢占式调度：又称为剥夺调度方式，指当一个进程正在处理机上执行时，系统可以根据规定的原则剥夺分配给它的 CPU 并分配给其它进程使用。  非抢占式调度：又称为非剥夺调度方式，指挑选一个进程或线程运行后，该进程或线程一直占有 CPU ，直至被阻塞，或者直到该进程或线程自动释放 CPU 为止。
29.2019年5月14日操作系统原理 Principle of Operating System 3.3.1 进程调度功能 3.3.2 进程调度时机 3.3.3 进程调度方式 3.3.4 进程调度算法 3.3.5 进程调度过程 3.3.6 线程调度精品课程
30.2019年5月14日操作系统原理 Principle of Operating System 精品课程进程调度算法要解决两个问题，其一是选择哪个进程，其二是选中它以后，如何给它分配处理机，以及该进程能占用处理机多久。第一个问题是选择方式，第二个问题是调度方式。
31.2019年5月14日 1 ．先来先服务（ FCFS ）算法 FCFS 算法就是每次从就绪队列中选择一个最先进入该队列的进程调度，把 CPU 分给它，令其投入运行。该进程一直运行下去，直至完成或者由于某些原因而被阻塞才放弃 CPU 。这样，当一个进程就绪队列时，它的 PCB 就链入就绪队列的末尾。每次进程调度时就把队头进程从该队列中摘下，分给它 CPU ，使它运行。
32.2019年5月14日 2 ．时间片轮转（ TRR ）算法主要用于分时系统中的进程调度。每当执行进程调度时，调度程序总是选出就绪队列的队首进程，让它在 CPU 上运行一个时间片的时间。时间片是一个小的时间单位，通常为 10 至 100ms 数量级。当进程用完分给它的时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，并把它放入就绪队列的末尾；然后，再把 CPU 分给就绪队列的队首进程，同样也让它运行一个时间片。
33.2019年5月14日例：有四个进程 A ， B ， C 和 D 。设它们依次进入就绪队列，但彼此相差时间很少，可以近似地认为“同时”到达。四个进程分别需要运行 12 、 5 、 3 和 6 个时间单位。试表示出时间片 q 等于 1 和 q 等于 4 时的运行情况。
34.2019年5月14日 3 ．高优先级优先调度算法利用优先级调度算法时，给每一个进程确定一个优先级，在进行进程调度时，从就绪队列中选出优先级最高的进程，把 CPU 分配给它使用。 非抢占式优先级法。 抢占式优先级法。
35.2019年5月14日两种确定进程优先级的方式： 静态方式：是在创建进程时就确定下来，而且在进程的整个运行期间保持不变 动态方式：是随着进程的推进而不断改变的。
36.2019年5月14日 4 ．多级反馈队列调度算法
37.2019年5月14日操作系统原理精品课程 Principle of Operating System 低级就绪队列低级就绪队列度一策个略三级反馈队列调超过时间片超过时间片等待其等待其他外设他外设启动其他启动其他外设外设运行运行选中选中,,时间片时间片 500ms 500ms 启动磁盘启动磁盘磁带磁带等待磁等待磁盘磁带盘磁带选中选中,,时间片时间片 100ms 100ms 选中选中,,时间片时间片 200ms 200ms 高级就绪队列高级就绪队列中级就绪队列中级就绪队列
38.2019年5月14日 5 ．保证调度一种实际并容易实现的保证是：若系统工作时有 n 个用户登录，则每个用户将获得 CPU 处理能力的 1/n 。类似地，在一个有 n 个进程的单用户系统中，若所有的进程都是平等的，则每个进程也将获得 CPU 处理能力的 1/n 。
39.兰州理工大学计算机与通信学院 2019年5月14日 6 ．彩票调度算法基本思想是为进程发放针对系统各种资源的彩票。当调度算法需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。对于 CPU 调度，系统可能每秒钟抽多次（如 50 次）彩票，每次获奖者可以获得一个时间片（如 20ms ）的运行时间。
40.兰州理工大学计算机与通信学院 2019年5月14日 7 ．公平分享调度体现对用户的公平性，每个用户得到的 CPU 时间都差不多，而调度程序需要一种强制的方式选择进程。
41.2019年5月14日操作系统原理 Principle of Operating System 3.3.1 进程调度功能 3.3.2 进程调度时机 3.3.3 进程调度方式 3.3.4 进程调度算法 3.3.5 进程调度过程 3.3.6 线程调度精品课程
42.兰州理工大学计算机与通信学院操作系统原理  2019年5月14日 Principle of Operating System 保存“下降”进程现场系统初启时无“下降”进程，“下降”进程为终止进程时，这一步不执行；  选择将要运行的进程——“上升”进程若此时就绪队列为空，则选择系统中一个特殊的死循环进程——闲置进程。  恢复“上升”进程的现场精品课程
43.2019年5月14日操作系统原理 Principle of Operating System 3.3.1 进程调度功能 3.3.2 进程调度时机 3.3.3 进程调度方式 3.3.4 进程调度算法 3.3.5 进程调度过程 3.3.6 线程调度精品课程
44.2019年5月14日线程调度的主要功能是选择一个适当的线程到处理机上去执行并进行描述表的切换。对于用户级线程，内核并不知道线程的存在，所以内核还是和以前一样工作，即采用前面所介绍的方法进行进程调度。对于内核级线程，是由内核选择一个特定的线程运行，它不用考虑该线程属于哪个进程。
45.兰州理工大学计算机与通信学院操作系统原理 Principle of Operating System 第 3 章处理机调度 3.1 3.2 3.3 3.4 3.5 概述作业调度进程调度实时调度多处理机调度精品课程
46.2019年5月14日操作系统原理 Principle of Operating System 精品课程实时系统是一种时间起着主导作用的系统。也就是说，在实时系统中，总是存在着若干带有某种程度紧迫性的实时进程，因此，对实时系统中的调度也就提出了某些特殊的要求。
47.2019年5月14日操作系统原理 3.4.1 Principle of Operating System 实时调度的要求 3.4.2 实时任务的分类 3.4.3 实时调度算法精品课程
48.2019年5月14日操作系统原理 Principle of Operating System 精品课程实时系统通常可以分为硬实时和软实时两种，前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。在实时系统中，为保证系统能够正常工作，实时调度必须能满足对于截止时间的限制，于是，对实时系统提出了以下几方面的要求：
49.2019年5月14日操作系统原理  Principle of Operating System 精品课程提供必要的调度信息：就绪时间；开始截止时间和完成截止时间；处理时间；资源需求；优先级。  调度方式：在实时系统中，广泛采用抢占式调度方式，特别是对那些要求严格的实时系统；对于一些小的实时系统，如果能预知任务的开始截止时间，则实时任务的调度也可采用非剥夺式调度。  具有快速响应中断的能力：系统具有快速硬件中断机构，使禁止中断的时间间隔尽量短以免耽误其他紧迫任务的处理时间。  快速的任务分配能力：系统中的每个运行单位比较小，减少人物切换的时间开销。
50.2019年5月14日操作系统原理 3.4.1 Principle of Operating System 实时调度的要求 3.4.2 实时任务的分类 3.4.3 实时调度算法精品课程
51.2019年5月14日操作系统原理 Principle of Operating System 1 ．根据任务到达时刻的规律分类：  周期任务  间发任务  非周期任务 2 ．根据对截止时间的要求分为类：  硬实时任务  软实时任务精品课程
52.2019年5月14日操作系统原理 3.4.1 Principle of Operating System 实时调度的要求 3.4.2 实时任务的分类 3.4.3 实时调度算法精品课程
53.2019年5月14日操作系统原理 Principle of Operating System 精品课程根据实时任务的特性可以将实时调度方法分为两大类：静态任务调度、动态任务调度。
54.2019年5月14日 1 ．静态调度算法常用的是静态优先级调度算法，此算法给系统中能够运行的所有任务都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期、用户优先级或者其它预先确定的策略。典型的静态调度算法有固定优先级调度算法、时钟驱动调度算法和单调速率（ RM ）算法。
55.2019年5月14日 ⑴ 固定优先级调度算法。广泛应用于实时系统和内核中，每个任务在运行之前都已经分配好固定的静态优先级。 ⑵ 时钟驱动调度方法。时钟驱动调度是指在系统开始执行之前，选择一些特定的时刻，在这些时刻决定哪一个作业在何时执行。 ⑶ 单调速率（ RM ）调度算法。它根据任务执行周期的长短来决定调度优先级，执行周期小的任务具有较高的优先级。
56.2019年5月14日 2 ．动态调度算法根据任务的资源需求来动态地分配任务的优先级。这类算法是在运行期间根据目前已处于就绪态的各个任务的相关属性来决定当前的调度序列。典型的动态调度算法有最小松弛度算法、最早截止时间优先算法等。
57.2019年5月14日 ⑴ 最小松弛度算法一个任务 A 的第 i 次执行的松弛度 FA(i) 的计算公式是 FA(i)=i×TA﹣Tsi﹣T 其中， TA 为任务 A 的周期长度； Tsi 为任务 A 的执行时间； T 为系统的当前时间。松弛度越小，说明任务的截止时间离当前时间越近。不过，当任务 Ai 的松弛度大于一个周期长度时，系统认为 Ai 当前无权被调度。
58.2019年5月14日例 3-8 有两个任务 A 和 B 。任务 A 的执行时间为 10ms/ 次，周期长度为 50ms 。任务 B 的执行时间为 20ms/ 次，周期长度为 80ms 。图 a 给出了任务 A 的调度需求。图 b 是任务 B 的调度需求。
59.2019年5月14日 ⑵ 最早截止时间优先算法 ① 抢占式EDF 调度算法它是一个动态优先级驱动的调度算法，其中分配给每个任务的优先级根据它们当前对最终期限的要求而定。当前请求的最终期限最近的任务具有最高的优先级，而请求最终期限最远的任务被分配最低优先级。对于含有 n 个任务的任务集，算法的可调度条件是处理机利用率满足下面公式： Ci 1  i 1 T i n 其中， Ci 为任务的最坏情况执行时间， Ti 为任务的周期。
60.2019年5月14日例 3-9 设任务集中含有三个任务，如下表所示：截止期 Di 任务周期 Ti 最坏情况所需的处理机时间 Ci 利用率任务 1 50 50 20 0.4 任务 2 40 40 10 0.25 任务 3 30 30 10 0.33 分析：上面任务集包含了三个任务，它们的处理机利用率为 0.98 ，小于 1 ，因此这个任务集能满足截止期要求进行调度。
61.2019年5月14日 ② 非抢抢占式抢 EDF 调度算法适用于周期性和非周期性任务，其中非周期性任务可以在任何时间被唤醒，但需指定它们连续两次被抢醒之抢抢抢抢的抢抢抢抢隔，一个任抢抢抢抢抢抢一旦抢抢抢行就要等到抢抢抢抢执行完成。调度程序只是在一个任务执行完成后才决定下一个要执行的任务。
62.兰州理工大学计算机与通信学院 2019年5月14日 3 ．各种类型实时任务的混合调度下面是几种典型的混合调度方法： 后台处理（ Background Processing ）法 基于服务器（ Serve Based ）的方法：又称为带宽预留算法。可以归结为固定优先级服务器算法与动态优先级服务器算法。 基于空闲时间的方法：主要包括空闲时间偷取法、时间片移位法与双重优先级法。
63.操作系统原理 Principle of Operating System 第 3 章处理机调度 3.1 3.2 3.3 3.4 3.5 概述作业调度进程调度实时调度多处理机调度精品课程
64.2019年5月14日操作系统原理 Principle of Operating System 精品课程当系统中有多台处理机时，进程调度是二维的，即调度程序要解决的问题不仅是决定哪一个进程运行，同时还要决定在哪一个 CPU 上运行。有些系统中的进程是不相关即独立的，而有些系统中的进程是成组的。
65.2019年5月14日操作系统原理 Principle of Operating System 3.5.1 不相关进程的调度 3.5.2 相关进程的调度 3.5.3 群调度精品课程
66.2019年5月14日操作系统原理 Principle of Operating System 精品课程操作系统处理不相关进程最简单且常用的方法是采用负载共享调度算法。如果有多个 CPU 同时处于空闲状态，则必须互斥访问就绪队列，此时就绪队列成为影响系统性能的瓶颈资源。
67.2019年5月14日
68.2019年5月14日操作系统原理 Principle of Operating System 精品课程利用这种调度策略，有下面的缺点，一是随着 CPU 数量的增加会引起对系统级就绪队列的潜在竞争；二是当进程由于 I/O 阻塞时引起的进程切换代价较高，比如分时系统中当时间片到时，就要发生进程切换；另外假设某个进程持有自旋锁，那么直到该进程再次被调度并且释放该锁之前，其它等待这个自旋锁的 CPU 只是浪费其轮转时间片。
69.2019年5月14日操作系统原理 Principle of Operating System 精品课程为了避免这种情况，可以采用“灵巧调度”的方法。即抢抢得自旋抢抢抢抢的抢抢程抢抢置一个抢抢抢抢程抢抢志表示它目前有抢抢抢抢抢抢一个自旋锁，当它释放该自旋锁时，就清除该标志。这样调度程序就不用停止持有自旋锁的进程，相反，调度程序会给予稍多一些的时间让该进程完成临界区的工作并能够释放自旋锁。 “ 亲和调度”的方法，其基本思想是进行一系列严格的努力使一个进程在它前一次运行过的 CPU 上运行。
70.2019年5月14日操作系统原理 Principle of Operating System 3.5.1 不相关进程的调度 3.5.2 相关进程的调度 3.5.3 群调度精品课程
71.2019年5月14日操作系统原理 Principle of Operating System 精品课程一个含有多个相关进程的作业或者包含多个线程的进程，基本上采用相同的处理方法。在多个 CPU 上同时调度多个进程或线程称为空间共享。最简单的空间共享算法是：假设一次创建了一组相关的进程或线程，在其创建时，调度程序检查是否有相同数量的空闲 CPU 存在，如果有，每个进程或线程都获得 CPU （即非多道程序处理）开
72.2019年5月14日操作系统原理 Principle of Operating System 精品课程始运行；如果没有足够的 CPU ，就没有进程或线程开始运行，直到有足够的 CPU 时为止。每个进程或线程拥有其 CPU 直到其运行结束，然后该 CPU 被送回可用 CPU 池中。如果有一个进程或线程被阻塞（如 I/O ）后，它继续占有 CPU ，该 CPU 一直空闲直到该进程或线程被唤醒。在下一批相关进程或线程出现时，应用相同的算法。在任何一个时刻，全部 CPU 被静态地划分成若干个分区，每个分区只运行一个进程或线程。
73.2019年5月14日
74.2019年5月14日操作系统原理 Principle of Operating System 3.5.1 不相关进程的调度 3.5.2 相关进程的调度 3.5.3 群调度精品课程
75.2019年5月14日操作系统原理 Principle of Operating System 精品课程群调度的基本思想是：把一组进程（或一个进程的所有线程）在同一时间一次性调度到一组处理机上运行。具体描述为： 1 ．把一组相关进程作为一个单位，即一个群一起调度； 2 ．一个群中的所有成员在不同分时处理的 CPU 上同时运行； 3 ．群中的所有成员一起开始和结束其时间片。
76.2019年5月14日操作系统原理 Principle of Operating System 精品课程群调度的关键是同步调度所有的 CPU ，也就是抢，在把抢抢抢 CPU 抢抢划抢抢分抢抢离散的抢抢抢抢抢片后，抢每一个新的时间片开始时，所有的 CPU 都重新调度，在每个 CPU 上都开始一个新的进程或线程。在后续的时间片开始时，另一个调度事件发生。在两个时间片中间没有调度行为。即使某个线程被阻塞，它的 CPU 也保持空闲，直到对应的时间片结束为止。
77.兰州理工大学计算机与通信学院 2019年5月14日谢谢 !