> For the complete documentation index, see [llms.txt](https://lewiszlw.gitbook.io/notebooks/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lewiszlw.gitbook.io/notebooks/blogs/history/chu-li-ji-tiao-du.md).

# 处理机调度

处理机调度的核心是对CPU资源进行合理的分配使用。

## 分级调度

### 调度层次

* 作业调度（宏观调度、高级调度）
  * 按一定原则选择外存后备队列中的作业，为其分配内存等资源，并建立进程，使其获得竞争处理机的资格，进入就绪队列。此外，在作业执行完毕时，回收系统资源。
* 交换调度（中级调度：内外存交换）
  * 按给定策略，将外存中处于就绪状态或等待状态的进程调入内存，或将内存中暂时不能运行的进程调至外存，以提高内存利用率和系统吞吐量。
* 进程调度（微观调度、低级调度）
  * 决定就绪队列中的哪个进程应获得处理机，为其进行进程上下文切换以建立相应的执行环境（即由处理机调度程序将处理机分配给某就绪进程，处理机调度程序常驻内存）
* 线程调度：进程中相关堆栈和控制表等的调度
  * 可有OS内核完成，也可由用户程序进行

### 作业的状态及转换

作业从提交给系统，直到完成任务退出系统前，在整个活动过程中它会处于不同的状态

* 提交状态：一个作业处于从输入设备进入外部存储设备的过程时所处的状态
* 后备状态：作业的全部信息都已通过输入设备输入到外存输入井中，等待进入内存
* 执行状态：作业一旦被作业调度程序选中，则为其分配所需的资源，并创建进程，送入内存中投入运行
* 完成状态：作业运行完毕，准备退出系统时的状态（所占用的资源尚未全部被系统回收）

![处理机调度1](http://ofolh8dcq.bkt.clouddn.com/%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A61.PNG)

### 作业和进程的关系

作业是用户向计算机提交任务的任务实体。

进程是计算机为了完成用户任务实体而设置的执行实体。

计算机要完成一个任务实体，必须要有一个以上的执行实体，即一个作业是由一个以上的进程组成。 **系统必须为一个作业创建一个根进程，然后再根据任务要求创建相应的子进程**

### 调度性能的衡量

面向用户的性能衡量

* 周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待等
  * 平均周转时间T
  * 平均带权周转时间W（综合考虑周转时间和执行时间）
* 响应时间：用户发出命令（如击键，输入一个请求）到系统响应给出执行结果（如屏幕显示）所经历的时间

面向系统的性能衡量

* 吞吐量：给定时间内所完成的作业总数。跟作业本身特性和调度算法都有关系
* 设备（处理机）利用率
* 设备的均衡利用：如CPU繁忙的作业和I/O繁忙的作业搭配
* 公平性：避免某些作业的等待时间过长
* 优先级

调度算法本身的性能衡量

* 易于实现
* 执行开销比

## 作业调度

### 作业控制块

系统为每个作业设置了一个作业控制块（JCB），记录已进入系统的各作业的情况，以便于管理和调度作业。 JCB的主要内容 ![处理机调度2](http://ofolh8dcq.bkt.clouddn.com/%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A62.PNG)

### 作业调度及功能

作业调度的任务：完成作业从后备状态到执行状态的转变，以及从执行态到完成态的转变。

* 作业从后备状态到执行状态 ![处理机调度3](http://ofolh8dcq.bkt.clouddn.com/%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A63.PNG)
* 作业从执行状态到完成状态 ![处理机调度4](http://ofolh8dcq.bkt.clouddn.com/%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A64.PNG)

作业调度的具体功能

* 记录系统中各个作业的情况；（记录情况）
* 按照某种调度算法从后备作业队列中选取作业；（挑选作业）
* 为被选取的作业分配内存、外设等需要的资源；（分配资源）
* 为选中的作业建立相应的进程。（建立进程）
* 在作业运行完毕或运行过程中因某种原因需要撤离时，进行善后处理工作，回收所占用的全部资源，撤消相关的进程及JCB。（善后处理）

### 作业调度目标与性能衡量

调度目标：

* 尽量公平合理
* 尽可能高的设备利用率
* 执行尽可能多的作业
* 尽快的响应时间

调度算法性能的衡量

* 平均周转时间（假定某作业i的提交时间为Tsi，完成时间为Tei）
  * 作业的周转时间为：$T\_i=T\_{ei}-T\_{si}$
  * 作业的平均周转时间为：$T=\frac1n\sum\_{i=1}^nT\_i$。（其中，n为作业流中的作业数）
* 平均带权周转时间
  * 作业的带权周转时间为：$W\_i=\frac{T\_i}{r\_i}$
  * 作业的平均带权周转时间为：$W=\frac1n\sum\_{i=1}^n\frac{T\_i}{r\_i}$
* 平均响应时间（分时、实时系统）

## 进程调度

### 进程调度的功能

进程调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选择一个进程，并把CPU的使用权交给被选中的进程。

进程调度的功能：

1. 记录所有进程的执行状况（静态和动态）
2. 按一定策略，选择一个就绪进程
3. 完成进程上下文切换

进程（上下文）切换的步骤：

1. 检查是否可以进行进程切换（如:原语执行时不可）
2. 保存被切换进程的现场（如：程序计数器、寄存器），并移至合适的（就绪、阻塞）队列
3. 选取一个新进程
4. 恢复被选中进程的现场：装配该进程的正文，使其获得CPU控制权

### 进程调度的时机

进程调度的时机与引起进程调度的原因及进程调度方式有关。

引起进程调度的原因有（原因之一发生时引发）：

* 正在执行的进程运行完毕，或由于某种错误而终止运行
* 执行中的进程自己调用阻塞原语，将自己阻塞起来进入等待状态
* 执行中的进程执行了P原语操作，因资源不足而被阻塞，或执行了V原语操作激活了等待资源的进程队列
* 执行中的进程提出I/O请求后被阻塞
* 执行完系统调用，在系统程序返回用户进程时，可调度选择一新的用户进程执行
* 分时系统中时间片到
* 当有一个优先级更高的进程就绪（可抢占式）

### 进程调度的方式

* 非抢占式 Non-preemptive（非剥夺式） 某一进程被调度执行后，将一直执行直到完成或发生某事件被阻塞，即是由于自身的原因而让出CPU。
* 抢占式 Preemptive（可剥夺式） 由于优先权、短作业优先或时间片到等因素，系统强行剥夺正在执行进程的CPU。

### 进程调度性能衡量

* 定性衡量
  * 公平性
  * 可靠性（避免因调度引起的破坏,对调度时机的选择和CPU现场的保护要十分谨慎）
  * 简洁性（避免调度程序消耗较大的系统开销）
* 定量评价
  * CPU利用率
  * 响应时间（交互式系统）
  * 吞吐量（批处理系统）

## 调度算法

### 先来先服务算法

FCFS法（First Come First Serve）基本思想：按照作业提交/进程变为就绪状态的先后次序，调入系统或分派CPU，换句话说，调度程序每次选择的作业/进程是等待时间最久的，而不管其运行时间的长短。

FCFS算法既可用于作业调度，也可用于进程调度。

特点

* 系统开销小，实现简单
* 比较有利于长作业和CPU繁忙的作业，而不利于短作业和I/O繁忙的作业。

### 短作业优先法

SJF法（Shortest Job First）基本思想：对预计执行时间短的作业（进程）优先处理。通常后来的短作业不抢先正在执行的作业。

SJF算法既可用于作业调度，也可用于进程调度。

优点：

* 缩短作业的等待时间
* 提高系统的吞吐量
* 比FCFS平均周转时间和平均带权周转时间短

缺点：

* 对长作业非常不利，可能长时间得不到执行
* 未能依据作业的紧迫程度来划分执行的优先级
* 难以准确估计作业（进程）的执行时间，从而影响调度性能

### 最高响应比优先法

HRN法（Highest Response\_Ratio Next）基本思想：响应比高者优先调度算法是介于先来先服务和短作业优先这两种算法之间的一种拆衷的算法，同时考虑每个作业的等待时间和估计需要的运行时间，从中选出响应比最高的作业投入运行。

既可用于作业调度，也可用于进程调度。

### 时间片轮转法

RR法（Round Robin）基本思想：（使等待时间与享受服务的时间成正比）

* 将系统中所有的就绪进程按照FCFS原则，排成一个队列。
* 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
* 在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
* 进程可以未使用完一个时间片，就提前调度（如完成/阻塞）

可用于进程调度，但不能用于作业调度。

时间片长度的影响

* 过长： 退化为FCFS算法，进程在一个时间片内可以都执行完。
* 过短： 一个进程需要多个时间片才能处理完，上下文切换频繁，开销增加。

对时间片长度的要求：q (时间片长度) = R(要求的响应时间) / N (最大进程数)

时间片长度的影响因素：

* 系统的响应时间：时间片越大，响应时间越长（当进程数一定时）
* 就绪进程的数目：数目越多，时间片越小（当响应时间一定时）
* CPU运行速度：CPU运行速度快，则时间片可以短些；反之，则取长些。

### 多级队列算法

根据作业或进程的性质或类型的不同，将后备或就绪队列再分为若干个子队列。各队列有不同的调度算法。

既可用于作业调度，也可用于进程调度。

### 优先级法

本算法是对优先级高的作业/进程优先处理。可分成抢先式和非抢先式。

既可用于作业调度，也可用于进程调度。

1. 静态优先级 根据作业/进程的静态特性，优先级在作业/进程开始执行前就确定，直到终止都不改变。通常是一个整数。（静态优先级可由用户/系统/操作员确定） 确定静态优先级的依据：

* 作业/进程类型（如：系统进程优先级较高）
* 用户要求（紧迫程度和付费多少：系统对高优先级用户收取较高的费用）
* 对资源的需求（对CPU和内存需求较少的进程，优先级较高）

1. 动态优先级 创建时赋予的优先级，在运行过程中可以不断改变，以便获得更好的调度性能。
2. 线性优先级调度算法——SRR法（Selfish Round Robin）

* 基本思想 就绪进程队列分成两个：
  * 新创建进程队列：按FCFS方式排队；进程优先级按速率a增加；
  * 享受服务进程队列：已得到过时间片服务的进程也按FCFS方式排队；进程优先级按速率b增加；（a>b>0）
* 新创建进程队列中的队首进程转入享受服务队列的条件：
  * 当新创建进程队列中的头一个进程的优先级与享受服务进程队列中最后一个进程的优先级相同时
  * 当享受服务队列为空时

### 多级反馈轮转法

多级反馈轮转法是时间片轮转法和优先级法的综合和发展。

多级反馈轮转法的基本思想

* 设置多个就绪队列，分别赋予不同的优先级，如：
  * 优先级逐级降低，队列1的优先级最高。
  * 每个队列执行时间片的长度也不同，规定优先级越低，则时间片越长，如逐级加倍
* 每个队列按FCFS原则排队。
* 同一队列内优先级相同。
* 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。
* 新进程进入内存后，先投入队列1的末尾；若按队列1的一个时间片未能执行完，则降低投入到队列2的末尾；如此下去，直到最后一个队列（最低级）。
* 最后一个队列（最低级）中的进程采用时间片轮转的方式进行调度。

多级反馈轮转法的优点：

* 不必估计进程的执行时间，动态调节
* 能较好地满足各种要求，提高系统吞吐量、缩短响应时间和平均周转时间
  * 短进程：能在较高优先级队列上的时间片内完成
  * 长进程：不必担心长期得不到处理
* 系统开销小

***

> 《计算机操作系统教程（第3版）》张尧学 史美林 张高 著