Operating System 简明教程

Operating System Scheduling algorithms

进程调度程序根据特定调度算法将不同的进程调度到 CPU。本章将讨论六种流行的进程调度算法 −

  1. First-Come, First-Served (FCFS) Scheduling

  2. Shortest-Job-Next (SJN) Scheduling

  3. Priority Scheduling

  4. Shortest Remaining Time

  5. Round Robin(RR) Scheduling

  6. Multiple-Level Queues Scheduling

这些算法要么是 non-preemptive or preemptive 。非抢占式算法设计为，一旦进程进入运行状态，它就无法在完成规定时间之前被抢占，而抢占式调度基于优先级，其中调度程序可以在高优先级进程进入就绪状态的任何时候抢占低优先级正在运行的进程。

First Come First Serve (FCFS)

  1. 作业按先到先服务的基础执行。

  2. 这是一种非抢占式、抢占式调度算法。

  3. 易于理解和实现。

  4. 其实现基于 FIFO 队列。

  5. 性能较差，因为平均等待时间较长。

fcfs

每个进程的 Wait time 如下 −

Process

等待时间：服务时间 - 到达时间

P0

0 - 0 = 0

P1

5 - 1 = 4

P2

8 - 2 = 6

P3

16 - 3 = 13

平均等待时间：(0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

  1. 这也被称为 shortest job first 或 SJF

  2. 这是一种不抢占式、抢占式调度算法。

  3. 最大程度减少等待时间的最佳方法。

  4. 易于在要求的 CPU 时间已知的批处理系统中实现。

  5. 不可能在要求的 CPU 时间未知的交互系统中实现。

  6. 处理器应预先知道进程将占用多少时间。

给定：进程表及其到达时间、执行时间

Process

Arrival Time

Execution Time

Service Time

P0

0

5

0

P1

1

3

5

P2

2

8

14

P3

3

6

8
shortest job next

每个进程的 Waiting time 如下：-

Process

Waiting Time

P0

0 - 0 = 0

P1

5 - 1 = 4

P2

14 - 2 = 12

P3

8 - 3 = 5

平均等待时间：(0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling

  1. 优先级调度是一种非抢占式算法，也是批处理系统中最常见的调度算法之一。

  2. 每个进程都会被分配一个优先级。优先级最高的进程将首先执行，以此类推。

  3. 优先级相同的进程按照先到先服务原则执行。

  4. 优先级可以根据内存需求、时间需求或任何其他资源需求来决定。

给定：进程表及其到达时间、执行时间和优先级。在这里，我们认为 1 是最低优先级。

Process

Arrival Time

Execution Time

Priority

Service Time

P0

0

5

1

0

P1

1

3

2

11

P2

2

8

1

14

P3

3

6

3

5
priority based sceduling

每个进程的 Waiting time 如下：-

Process

Waiting Time

P0

0 - 0 = 0

P1

11 - 1 = 10

P2

14 - 2 = 12

P3

5 - 3 = 2

平均等待时间：(0 + 10 + 12 + 2)/4 = 24/4 = 6

Shortest Remaining Time

  1. 最短剩余时间 (SRT) 是 SJN 算法的抢占版。

  2. 将处理器分配给最接近完成的任务，但它会被一个新生的就绪任务抢占，该任务完成时间更短。

  3. 不可能在要求的 CPU 时间未知的交互系统中实现。

  4. 它通常用于调度短任务优先的批处理环境。

Round Robin Scheduling

  1. 循环调度是一种抢占进程调度算法。

  2. 向每个进程提供固定时间执行，这被称为 quantum 。

  3. 一个进程执行一段时间后，它被抢占，其他进程执行一段时间。

  4. 上下文切换用于保存被抢占进程的状态。

round robin

每个进程的 Wait time 如下 −

Process

等待时间：服务时间 - 到达时间

P0

(0 - 0) + (12 - 3) = 9

P1

(3 - 1) = 2

P2

(6 - 2) + (14 - 9) + (20 - 17) = 12

P3

(9 - 3) + (17 - 12) = 11

平均等待时间：(9 + 2 + 12 + 11)/4 = 8.5

Multiple-Level Queues Scheduling

多级队列并不是一个独立的调度算法。它们利用其他现有算法对具有共同特征的任务进行分组和调度。

  1. 为具有共同特征的进程维护多个队列。

  2. 每个队列可以有自己的调度算法。

  3. 为每个队列分配优先级。

例如，CPU 绑定任务可以在一个队列中调度，所有 I/O 绑定任务在另一个队列中调度。然后进程调度器交替从每个队列中选择任务，并根据分配给该队列的算法将它们分配给 CPU。