调度策略与算法：广东工业大学操作系统实验深入理解


参考资源链接：[广东工业大学 操作系统四个实验（报告+代码）](https://wenku.csdn.net/doc/6412b6b0be7fbd1778d47a07?spm=1055.2635.3001.10343)
# 1. 调度策略与算法的基础知识

在现代操作系统中，高效的任务调度是确保系统资源得到充分利用和提供快速响应服务的关键技术。本章节将介绍调度策略与算法的基础知识，包括其定义、目标和分类，以及它们在操作系统中的重要性。

## 1.1 调度的基本概念

调度，简单来说，就是操作系统中对CPU以及其他资源进行合理分配的过程。它决定了哪个进程或线程在何时获得对CPU的控制权，进而执行其任务。这一过程的核心在于提高资源利用率和系统的吞吐量，同时减少进程的等待时间和响应时间。

## 1.2 调度的目标和评价标准

调度的目标主要是提高资源的利用率，保障系统的公平性，并确保系统服务的响应性与高效性。在评价调度算法时，通常使用以下几个标准：

- **CPU利用率**：CPU工作时间与总时间的比例，应尽可能高。
- **吞吐量**：单位时间内完成进程的数量。
- **周转时间**：从作业提交到作业完成的时间间隔。
- **等待时间**：进程在就绪队列中等待分配CPU时间的总时间。
- **响应时间**：从作业提交到首次响应的时间。

在后续章节中，我们将探讨不同类型的进程调度算法，并分析它们是如何在各种操作系统中实现和优化的。理解基础概念将帮助我们更深入地掌握调度策略的复杂性和多样性。

# 2. ```
# 第二章：进程调度理论与实践

## 2.1 进程调度的基本概念

### 2.1.1 进程状态与转换

进程是操作系统中的一个核心概念，它表示了一个正在执行的程序的实例。进程的生命周期中，会经历不同的状态，包括就绪态、运行态和阻塞态等。进程状态的转换是操作系统调度过程中的重要部分，它直接影响到系统的性能和资源的有效利用。

- **就绪态（Ready）**：进程已经具备运行条件，但由于没有获得CPU的分配而不能运行。
- **运行态（Running）**：进程获得CPU时间片，正在运行。
- **阻塞态（Blocked/Waiting）**：进程因等待某个事件发生而暂时停止运行，如等待输入/输出操作完成。

转换关系如下：

- **就绪 -> 运行**：就绪队列中的进程被调度程序选中，分配CPU资源，进入运行状态。
- **运行 -> 阻塞**：运行中的进程因等待外部事件（如I/O操作）或系统资源而暂时无法继续执行，转为阻塞状态。
- **阻塞 -> 就绪**：当阻塞事件发生（如I/O完成），进程变为就绪状态。
- **运行 -> 就绪**：运行时间片到或者更高优先级的进程到来时，当前进程被抢占，转为就绪状态。

进程状态转换可以用以下图示进行描述：

### 2.1.2 调度算法的目标和评价标准

调度算法的设计目标是为了合理地分配CPU时间，提高系统吞吐量，缩短平均响应时间，保证公平性和系统的稳定性。不同的调度策略会侧重于不同的目标。

- **系统吞吐量**：单位时间内完成进程的数量。
- **平均响应时间**：从提交进程到系统开始执行进程的时间。
- **CPU利用率**：CPU工作时间与总时间的比值。
- **周转时间**：从进程提交到进程完成的时间间隔。
- **等待时间**：进程在就绪队列中等待的时间总和。
- **公平性**：确保每个进程都能获得CPU资源，防止饥饿现象。

## 2.2 典型的进程调度算法

### 2.2.1 先来先服务（FCFS）

先来先服务（FCFS）是最简单的调度算法，按照进程到达的先后顺序进行调度。FCFS算法简单、易于实现，但它可能存在"饥饿"问题，即某些进程可能因为等待时间过长而延迟执行。

在FCFS中，一个进程一旦获得了CPU，就会一直运行直到完成，或者被阻塞，无法立即获得CPU资源的进程则需要等待。

### 2.2.2 短作业优先（SJF）

短作业优先（SJF）算法选择当前可运行的、执行时间最短的进程进行调度。这种策略可以有效地减少平均等待时间，从而减少总体的平均周转时间。

然而，SJF算法可能会造成长作业的饥饿问题，因为系统可能会持续选择较短的作业进行执行，而忽略时间较长的作业。

### 2.2.3 优先级调度算法

优先级调度算法根据进程的优先级进行调度。每个进程都有一个优先级，CPU总是选择优先级最高的进程进行执行。优先级可以是静态的，也可以是动态调整的。

- **静态优先级**：进程的优先级在创建时确定，之后不变。
- **动态优先级**：进程的优先级随着等待时间的增加或其他因素变化。

优先级调度算法的一个重要问题是优先级反转问题，即高优先级进程可能被低优先级进程阻塞。

## 2.3 实际操作系统的进程调度实现

### 2.3.1 Linux进程调度概述

Linux操作系统采用了多层次、多策略的调度框架。从2.6版本开始，Linux引入了完全公平调度器（CFQ），它是一种基于虚拟运行时间的调度器，旨在为每个进程提供公平的CPU时间。

CFQ调度器使用红黑树来管理就绪队列，根据进程的权重公平地分配时间片。Linux调度器还引入了实时调度策略，支持软实时和硬实时进程。

### 2.3.2 Windows进程调度机制

Windows操作系统中，进程调度主要由调度器（Scheduler）完成，它为每个进程分配优先级和处理器时间。Windows调度器支持多优先级策略，并且能够动态调整进程优先级。

Windows调度器还利用了优先级提升（Priority Boosting）技术，以防止低优先级进程饥饿。同时，Windows系统也提供了实时调度能力，支持实时和近实时任务。

在接下来的章节中，我们将深入探讨CPU调度的高级策略，内存管理与调度的关联，以及I/O调度策略及其优化。这将帮助读者更好地理解操作系统内部工作原理，并提升实际的系统管理能力。

# 3. CPU调度的高级策略

## 3.1 多级队列调度算法

### 3.1.1 多级队列的设计与实现

多级队列调度算法（MLQ）是一种用于处理多类进程调度的算法，它根据进程的不同特性将它们分配到不同的队列中，并为每个队列设置不同的调度策略。在多级队列模型中，每个队列拥有其独立的调度器，且这些调度器可以使用不同的算法，如轮转（Round Robin, RR）、先来先服务（FCFS）或优先级调度（Priority Scheduling）。当一个进程进入系统时，它会根据其属性和分类规则被分配到相应的队列中。

设计多级队列调度算法时，需要考虑的关键因素包括：

- **队列的数量与类型**：根据进程的特性，如优先级、IO密集型或CPU密集型，确定队列数量和类型。
- **调度策略**：为每个队列选择合适的调度策略。例如，高优先级队列可以采用FCFS，而低优先级队列可以采用RR策略以防止饥饿。
- **进程的分类和迁移规则**：定义进程分类的标准和进程在不同队列间迁移的规则。

graph LR
A[开始] --> B[接收新进程]
B --> C{进程分类}
C -->|CPU密集型| D[CPU队列]
C -->|IO密集型| E[IO队列]
C -->|优先级高| F[高优先级队列]
D --> G[应用FCFS或RR]
E --> H[应用RR]
F --> I[应用FCFS]
G --> J[完成调度]
H --> J
I --> J

### 3.1.2 实例：多级反馈队列调度

多级反馈队列调度（MFQ）是多级队列调度算法的一个实际应用示例。它不仅将进程分配到不同的队列，而且允许进程在不同的队列间迁移。这个算法的主要优势是它能够动态地响应进程的行为变化。

在MFQ算法中，进程首先被放入最高优先级队列，并给定一个较小的时间片。如果进程在规定时间内未能完成，它会被移到下一个低优先级队列。如果进程完成了任务或等待I/O操作，则可以被提升到一个高优先级队列。这种策略确保了I/O密集型和交互式进程能够得到快速响应，同时保证了CPU密集型进程也能得到足够的CPU时间。

flowchart LR
A[进程提交] --> B{放入最高优先级队列}
B --> C{时间片内完成?}
C -- 是 --> D[任务完成]
C -- 否 --> E{移动到下一队列?}
E -- 是 --> B
E --