操作系统--处理机调度

在计算机系统中，可能同时有数百个批处理作业存放在磁盘的作业队列中，或者有数百个终端与主机相连接。如何从这些作业中挑选作业进入主存运行、如何在进程之间分配处理器时间，无疑是操作系统资源管理中的一个重要问题。这一涉及处理机分配的问题，称之为处理机调度。

1、处理机调度的层次

处理机调度分为三个级别：

• 高级调度：又称为作业调度，他按照系统的预定调度策略决定把后背队列作业中的那些作业调入主存，并为之创建进程、启动他们运行，它发生在新进程的创建过程中，决定了一个进程能否被创建，或者创建后是否被指为就绪状态。
• 中级调度：又称为平衡负载调度，它决定了主存储器中所能够容纳的进程数，这些进程允许参与竞争处理器资源。而暂时不能运行的进程，则被调出主存，挂起；它根据当前系统的负荷情况决定停留在主内存中进程数。

• 低级调度：又称为进程调度，按照某种原则决定就绪队列中的那些进程可以获得处理器，并将处理机让出给它进行工作；

  
  image.png

2、调度算法

2.1、选取原则

• 资源利用率--使得CPU或者其他资源的利用率尽可能的高且能够并行工作
• 响应时间--使交互式用户的响应时间尽可能的小，或者尽快处理实时任务
• 周转时间---批处理用户从作业提交给系统开始到作业完成获得结果为止的这段时间间隔称作业周转时间，应该使作业周转时间或作业平均周转时间尽可能短。
• 吞吐量---使得单位时间处理的作业数尽可能多。
• 公平性---确保每个用户每个进程获得合理的 CPU份额或其他资源份额。

批处理系统的调度性能主要用作业周转时间和作业带权周转时间来衡量。如果作业i提交给系统的时刻是ts，完成时刻是tf，则其周转时间为：
ti=tf-ts
即作业在系统中的等待时间和运行时间之和

从操作系统来说，为提高系统的性能，让若干用户的平均作业周转时间和平均带权周转时间最小：
平均作业周转时间 T=（Σti）/n

如果作业 i 的周转时间为 ti，所需运行时间为 tk，则称 wi=ti/tk 为该作业的带权周转时间。因为，ti 是等待时间与运行时间之和，故带权周转时间总大于 1。
平均作业带权周转时间 W = (Σwi) / n

通常，用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们呈现的调度性能；用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算法时，它们呈现的调度性能。这两个数值均越小越好。

3、批处理作业的管理与调度

多道批处理操作系统采用脱机控制方式，它具体独立的作业管理模块，为了有效管理作业，为每一个作业建立作业控制块。每个作业的生命周期内都顺序的处于以下四个状态：

1. 输入状态：此时作业的信息正在从输入设备上预输入
2. 后备状态：此时作业预输入结束但尚未被选中执行
3. 执行状态：作业已经被选中并构成进程去，竞争处理器资源以获取运行
4. 完成状态：作业以及运行结束，正在等待缓输出

多道批处理操作系统的处理机调度，至少包括作业调度和进程调度。

image.png

3.1、 批处理作业的调度方法

对成批进入系统的用户作业，按一定的策略选取若干个作业使它们可以去获得处理器运行，这项工作称为作业调度。

3.1.1、 先来先服务算法（FCFS ） ：

此种方法，按照作业进入系统的先后顺序来挑选作业，考虑了作业等待时间，而未考虑作业要求服务时间的长短。此种不利于短作业而优化了长作业。
例如：下面三个作业同时到达系统并立即进入调度：

          作业名    所需 CPU 时间
          作业1        28
          作业2        9
          作业3        3                           

假设系统中没有其他作业，现采用 FCFS 算法进行:

   平均作业周转时间： T=(28+(28+9)+(28+9+3))/3=35
  

3.1.2、 最短作业优先算法（SJF） ：

此种方法已进入系统的作业所提出运算的计算时间为标准，选取估计计算时间最短的作业投入运行。它忽略了作业等待时间，且估算作业时间并不容易；

例如：下面四个作业同时到达系统并立即进入调度：

          作业名    所需 CPU 时间
          作业1        9
          作业2        4
          作业3        10  
          作业4        8                             

假设系统中没有其他作业，现采用 SJF 算法进行: 此时作业调度顺序为： 2--4--1--3

   平均作业周转时间： T=(4+(4+8)+(4+8+9)+(4+8+9+10))/4=17
   平均带权作业周转时间：W=（4/4+（4+8）/8+（4+8+9）/9+（4+8+9+10）/10）/4=1.98

而采用FCFS调度算法：

   平均作业周转时间： T=(9+13+23+31)/4=19
   平均带权作业周转时间：W=（9/9+13/4+23/10+31/8）/4=2.51

对比可以看出，SJF算法较FCFS调度算法，性能较好；

3.1.3、 响应比最高者有限算法（HRN） ：

前面两者的调度算法都比较片面，而HRN算法使两者的折衷算法。
响应比=已等待时间/估计计算时间
限显然，计算时间短的作业容易得到较高的响应比，此算法优待短作业

例如：下面四个作业同时到达系统并立即进入调度：

          作业名    所需 CPU 时间       到达时间
          作业1        20                0
          作业2        15                5
          作业3        5                 10
          作业4        10                15             

假设系统中没有别的作业，现对实施SJF调度算法，此时作业调度顺序为：1--3--4--2

   平均作业周转时间： T=(20+15+20+45)/4=25
   平均带权作业周转时间：W=(20/20+15/5+25/10+45/15)/4=2.25

如果对它们施行 FCFS 调度算法，

   平均作业周转时间 T = (20+30+30+35)/4 = 38.75
   平均带权作业周转时间 W = (20/20+30/15+30/5+35/10)/4 = 3.13 

采用HRN算法：

• 开始只有作业1，作业1被选中，执行时间20
• 作业1执行完毕后，响应比依次为15/15，10/5，5/10,作业3被选中，执行时间为5
• 作业 3 执行完毕后，响应比依次为 20/15、10/10，作业 2 被选中，执行时间 15；
• 作业 2 执行完毕后，作业 4 被选中，执行时间 10；

   平均作业周转时间 T = (20+15+35+35)/4 = 26.25
   平均带权作业周转时间 W = (20/20+15/5+35/15+35/10)/4 = 2.42 

3.1.4、 优先数法 ：

根据确定的优先数来选取作业，每次总选择优先级高的作业。

3.1.5、分类调度算法

分类调度算法按照一定的原则将作业划分为若干类，以达到均衡使用操作系统的资源和兼顾大小作业的目的。分类原则包括作业计算时间、对内存的需求、对外围设备的需求等。作业调度时还可以为每类作业设置优先级，从而照顾到同类作业中的轻
重缓急。

4、进程调度

进程调度又称为低级调度，其负责将处理器分配给进程 。

• 记录进程的状态
• 记录某个进程什么时候获取处理器，以及占用多长时间
• 把处理器分配给进程
• 收回处理器

4.1、进程调度算法

1. 先来先服务算法

2. 时间片轮转算法：又称为时间片调度。具体做法是调度程序每次把 CPU 分配给就绪队列首进程使用一个时间片，例100ms，就绪队列中的每个进程轮流地运行一个这样的时间片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。实现这种调度要使用一个间隔时钟，例如，当一个进程开始运行时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，就表明该进程连续运行的时间已超过一个规定的时间片。此时，中断处理程序就通知处理器调度进行处理器的转换工作。这种调度策略可以防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备。

3. 优先权调度，每个进程给出一个优先数，调度每次选择就绪进程中优先数最大者，让它占用处理器运行。

4. 多级反馈队列调度，又称之为反馈循环队列。其主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度每次先从高级的就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取 image.png

5. 保证调度算法，一种完全不同的调度算法是向用户做出明确的性能保证，然后去实现它。为了实现所作的保证，系统必须跟踪各个进程自创建以来已经使用了多少 CPU 时间。然后它计算各个进程应获得的 CPU 时间，即自创建以来的时间除以 n。由于各个进程实际获得的 CPU 时间已知，所以很容易计算出实际获得的 CPU 时间和应获得的CPU 时间之比，于是调度将转向比率最低的进程。

6. 彩票调度算法，为进程发放针对系统各种资源（如 CPU 时间）的彩票。当调度程序需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。对于 CPU调度，系统可能每秒钟抽 50 次彩票，每次中奖者可以获得 20ms 的运行时间。

4.2、 分时调度

实时系统是那些时间因素非常关键的系统。通常分为硬实时系统和软实时系统。前这意味着存在必须满足的时间限制，后则意味着偶尔超过时间限制可以容忍的。

5、多处理器的调度算法

大量的实验数据证明，随着处理器数目的增多，复杂进程调度算法的有效性却逐步下降。因此在大多数采取动态分配策略的多处理器系统中，进程调度算法往往采用最简单的先来先服务算法或优先数算法，就绪进程组成一个队列或多个按照优先数排列的队列。
多处理器调度算法主要研究线程调度算法

5.1、均分负载调度算法

均分负载（load sharing）调度算法的基本思想是：进程并不分配给一个处理器，系统维护一个就绪线程队列，当一个处理器空闲时，就选择一个就绪线程占有处理器运行。这一算法有如下优点：

• 把负载均分到所有的可用处理器上，保证了处理器效率的提高。
• 不需要一个集中的调度程序，一旦一个处理器空闲，操作系统的调度程序就可以运行在该处理器上以选择下一个运行的线程。
• 运行线程的选择可以采用各种可行的策略（雷同与前面介绍的各种进程调度算法）。

这一算法也有一些不足：

• 就绪线程队列必须被互斥访问，当系统包括很多处理器，并且同时有多个处理器同时挑选运行线程时，它将成为性能的瓶颈。
• 被抢占的线程很难在同一个处理器上恢复运行，因此当处理器带有高速缓存时，恢复高速缓存的信息会带来性能的下降。
• 如果所有的线程都被放在一个公共的线程池中的话，所有的线程获得处理器的机会是相同的。如果一个程序的线程希望获得较高的优先级，进程切换将导致性能的折衷。

5.2、群调度

群调度（gang scheduling）算法的基本思想是：把一组相关的线程在同一时间一次性调度到一组处理器上运行