Operating System 简明教程

Operating System Scheduling algorithms

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

A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms. There are six popular process scheduling algorithms which we are going to discuss in this chapter −

  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 。非抢占式算法设计为，一旦进程进入运行状态，它就无法在完成规定时间之前被抢占，而抢占式调度基于优先级，其中调度程序可以在高优先级进程进入就绪状态的任何时候抢占低优先级正在运行的进程。

These algorithms are either non-preemptive or preemptive. Non-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time, whereas the preemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state.

First Come First Serve (FCFS)

  1. Jobs are executed on first come, first serve basis.

  2. It is a non-preemptive, pre-emptive scheduling algorithm.

  3. Easy to understand and implement.

  4. Its implementation is based on FIFO queue.

  5. Poor in performance as average wait time is high.

fcfs

每个进程的 Wait time 如下 −

Wait time of each process is as follows −

Process

Wait Time : Service Time - Arrival Time

P0

0 - 0 = 0

P1

5 - 1 = 4

P2

8 - 2 = 6

P3

16 - 3 = 13

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

Average Wait Time: (0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

  1. This is also known as shortest job first, or SJF

  2. This is a non-preemptive, pre-emptive scheduling algorithm.

  3. Best approach to minimize waiting time.

  4. Easy to implement in Batch systems where required CPU time is known in advance.

  5. Impossible to implement in interactive systems where required CPU time is not known.

  6. The processer should know in advance how much time process will take.

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

Given: Table of processes, and their Arrival time, Execution time

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 如下：-

Waiting time of each process is as follows −

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

Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling

  1. Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems.

  2. Each process is assigned a priority. Process with highest priority is to be executed first and so on.

  3. Processes with same priority are executed on first come first served basis.

  4. Priority can be decided based on memory requirements, time requirements or any other resource requirement.

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

Given: Table of processes, and their Arrival time, Execution time, and priority. Here we are considering 1 is the lowest priority.

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 如下：-

Waiting time of each process is as follows −

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

Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Shortest Remaining Time

  1. Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.

  2. The processor is allocated to the job closest to completion but it can be preempted by a newer ready job with shorter time to completion.

  3. Impossible to implement in interactive systems where required CPU time is not known.

  4. It is often used in batch environments where short jobs need to give preference.

Round Robin Scheduling

  1. Round Robin is the preemptive process scheduling algorithm.

  2. Each process is provided a fix time to execute, it is called a quantum.

  3. Once a process is executed for a given time period, it is preempted and other process executes for a given time period.

  4. Context switching is used to save states of preempted processes.

round robin

每个进程的 Wait time 如下 −

Wait time of each process is as follows −

Process

Wait Time : Service Time - Arrival Time

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

Average Wait Time: (9+2+12+11) / 4 = 8.5

Multiple-Level Queues Scheduling

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

Multiple-level queues are not an independent scheduling algorithm. They make use of other existing algorithms to group and schedule jobs with common characteristics.

  1. Multiple queues are maintained for processes with common characteristics.

  2. Each queue can have its own scheduling algorithms.

  3. Priorities are assigned to each queue.

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

For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs in another queue. The Process Scheduler then alternately selects jobs from each queue and assigns them to the CPU based on the algorithm assigned to the queue.