进程调度算法

需要了解的 6 类调度算法【先来先服务调度算法、短进程优先调度算法、优先权调度算法、时间片轮转调度算法、多级队列调度、多级反馈队列调度】。

选择调用方式和算法的若干准则

1.周转时间短

是指从作业提交给系统开始，到作业完成为止的这段时间的间隔。

• 作业在外存后备队列上等待调度时间。

• 进程在就绪队列上等待进程调度时间。

• 进程在 CPU 上执行时间。

• 进程等待 I/O 操场完成时间。

衡量系统时间性能

• 平均周转时间

平均周转时间 T 等于 n 个作业的周转时间之和除以 n。

• 带权平均周转时间

作业的周转时间 T 与系统为它提供服务时间 Ts 之比为 W，W = T / Ts 。被称为带权平均周转时间。

2.响应时间快

响应时间是指从用户提交一个请求开始直至系统首次产生响应时间为止的一段时间。

• 从输入设备输入请求信息传送到处理机的时间。

• 处理机对请求信息的进程处理的时间。

• 所形成的响应信息回送到终端显示的时间。

3.截止时间的保证

某个任务必须开始执行的最迟时间，或必须完成的最迟时间。截止时间是评价实时系统的重要指标。

4.系统吞吐量高

单位时间内完成的作业数量。系统的吞吐量是评价系统性能的重要标准之一。调度算法影响系统的吞吐量

5.处理机利用率好

CPU 是计算机系统中影响时间性能的最重要的硬件资源。在多任务系统，进程调度算法对 CPU 的利用率有很大影响。因此，在选择和设计进程调度算法时应该考虑使 CPU 利用率尽可能高。

调度算法

1.先来先服务调度算法（FCFS）

1.1.调度算法

FCFS 就是从就绪队列中的队首选择最先到达就绪队列的进程，为该进程分配 CPU。

1.2.性能分析

• FCFS 适合长进程，不利于短进程，短进程等待时间相对于运行时间而言太长。

• FCFS 使短进程的周转时间过程，系统的平均周转时间也比较长。

• FCFS 有利于 CPU 繁忙型进程（科学计算），不利于 I/O 繁忙型进程（如多数的事务处理）。

2.短进程优先调度算法（SPF）Shortest-Process-First

2.1.调度算法

SPF 的调度算法是从就绪队列中选择估计运行实时间最短的进程，将 CPU 分配给它，使它立即执行并一只执行完成，或发生某事件而被阻塞放弃执行时间。

2.2.算法优点

与 FCFS 相比，短进程优先的算法有效降低来进程的平均等待时间。提高了系统的吞吐量。

2.3.算法缺陷

• 对长进程不利。如果系统中不断有短进程进入，长进程可能很长时间得不到执行。

• 不能保证急迫进程的及时处理，因此该算法不考虑进程的进程程度。

• 进程的长度根据用户评估而定，不一定能做到到真正的短进程优先。

2.4.性能分析

短进程优先的调度算法与先来先服务的调度算法相比，降低了系统的平均周转时间和带权平均周转时间。

3.优先权调度算法（Priority-Scheduling Lgorithm）

3.1.调度算法

在使用优先权调度的系统中，每一个进程都有一个与之关联的优先权。优先权的值通常采用固定的区间的数字标示。

3.2.优先权可以通过内部或外部方式来定义

内部定义

优先权可以通过使用一些可测量数据以计算进程的优先权值。如：时间极限，内存要求，打开文件数量，平均 i/o 服务时间，平均 CPU 服务时间等。

外部定义

通过操作系统之外的准则来设置。如：进程的重要性，用于支付使用计算的费用和数量。

3.3.优先权调度算法的类型

非抢占式优先权调度算法

高优先权的进程到来如果有别的进程正在运行，高优先权的进程真能先进入就绪队列。系统不能剥夺当前进程的 CPU 使用权。在对截止时间有严格要求的实时系统中，非抢占式调度难以保证高优先级的进程及时调度

抢占式优先权调度算法

在支持抢占式调度的系统中，如果新到的进程优先权高于当前正在运行的进程，那么系统会抢占 CPU，把它分配给最新到的高优先权的进程，而当前执行的较低优先权的进程暂停。

3.4.优先权的类型

静态优先权

在创建的时候确定，在进程运行期间保持不变。

动态优先权

进程创建时被赋予的优先权，随着进程的推进或等待时间的增加而改变。

优先权调度算法存在问题和解决方案

问题：无穷阻塞，或者饥饿问题。

解决方案：老化（Aging）技术。逐渐增加在系统中等待时间很长的进程优先权。

4.时间片轮转调度算法

4.1.调度算法

在早期的时间时间片轮转算法中，系统将所有就绪进程按照先来先服务的原则，排查一个队列，每次调度时把 cpu 分配给队首进程，并令其执行一个时间片。当时间片用完时，调度程序终止当下进程的执行，并将其送到就绪队列的队尾。

4.2.时间片大小的确定（相关因素）

系统对响应时间的要求。

系统响应时间为 T，进程数目为 N，时间片为 q T = Nq。

就绪队列中的进程数目。

系统的处理能力。

4.3.性能评价

算法的性能很大程度上依赖时间片的大小。在极端情况下，如果时间片很大，那么时间片轮转调度算法和先来先服务算法一样。如果时间片很小，进程需要多次上下文切换和进程调度。会大大增加 cpu 用于进程切换和进程调度的开销。

5.多级队列调度（Muti level Queue-Scheduling Algorithm）

5.1.调度算法

就绪队列分成多个独立队列，根据进程的某些属性，如需要占用内存的大小，进程优先权或进程类型，进程会被永久的分配到一个队列中。每一个队列有自己的调度算法。不同的队列的优先级不同算法也不同。

6.多级反馈队列调度

6.1.调度算法

建立多个优先权不同的就绪队列，为每个队列赋予大小不同的时间片。有一种反馈策略可以规定：独立的优先权高，时间片越短，时间片通常成倍增长。

6.2.调度流程

新进程被创建后，先插入优先权最高的队列。仅当高优先队列为空时，才调度优先权次之的队列。同一队列中，采用时间片轮转调度算法。使用 cpu 时间过多的进程会被移动到优先权较低的队列中，在优先权较低的队列中等待时间过长的进程将会被转移到较高优先权的队列中。

6.3.设计考虑的问题

• 就绪队列的数量。

• 根据进程优先权确定进程应该进入那个就绪队列的算法。

• 用于确认进程何时转移到较高优先权的算法。

• 用于确认进程何时转入到较低优先权的算法。

• 用于确认进程子需要服务时候应该进入那个队列的算法。

典型案例 Linux 2.6.11 内核的进程调度算法。

周转时间计算

例如：有 3 个进程分别为 P1，P2，P3，他们的服务时间为 24 ，3，3 。

1.先来先服务算法

执行顺序： P1 -> P2 -> P3；

开始运行时间 = 上一个进程周转时间 + 上一个进程进入系统时间

等待时间 = 开始运行时间 - 进入进入系统时间

周转时间 = 服务时间 + 等待时间

平均周转时间计算结果：（24+26+28）/ 3 = 26

带权平均周转时间计算结果：（24/24 + 26/3 + 28/3）/ 3 -> (1 + 8.6666 + 9.3333) / 3 约等于 6.3

2.短进程优先算法

执行顺序： P3 -> P2 -> P1；

平均周转时间计算结果：（28+5+3）/ 3 = 12

带权平均周转时间计算结果：（3/3 + 5/3 + 28/24）/ 3 -> (1 + 1.6666 + 1.1666) / 3 约等于 1.2

欢迎大家的留言讨论。按惯例最后分享一首诗给大家。

要和你心灵的主人一起，

时时检查你内心的状态。

黄铜不知道它是铜，

直到它，变成黄金。