# 3.1 调度的基本概念

## 一、调度的层次

### 1.1 高级调度（作业调度）

**定义**：从外存的后备队列中选择作业调入内存，并为其创建进程。

**调度对象**：作业

**发生频率**：最低，几分钟或更长时间一次

**主要功能**：
- 选择作业进入内存
- 为作业分配资源
- 创建进程
- 作业完成后回收资源

**在多道批处理系统中的重要性**：
- 决定哪些作业能进入系统
- 影响系统的吞吐量和资源利用率

### 1.2 中级调度（内存调度）

**定义**：将内存中的进程换出到外存，或将外存中的进程换入内存。

**调度对象**：进程

**发生频率**：中等

**主要功能**：
- 实现虚拟存储
- 提高内存利用率
- 系统负荷调节

**换出条件**：
- 进程长时间不运行
- 系统内存不足
- 进程优先级低

**换入条件**：
- 系统内存充足
- 进程需要运行
- 进程优先级高

### 1.3 低级调度（进程调度）

**定义**：从就绪队列中选择进程，将CPU分配给该进程。

**调度对象**：进程

**发生频率**：最高，几毫秒一次

**主要功能**：
- 选择就绪进程
- 分配CPU
- 实现进程切换

**调度方式**：
- **非抢占式**：一旦分配CPU，直到进程完成或阻塞才释放
- **抢占式**：可以强制收回CPU，分配给其他进程

### 1.4 三层调度的比较

| 特性 | 高级调度 | 中级调度 | 低级调度 |
|-----|---------|---------|---------|
| 调度对象 | 作业 | 进程 | 进程 |
| 发生频率 | 低 | 中 | 高 |
| 调度时机 | 作业进入系统 | 内存不足或充足 | 每次进程切换 |
| 主要功能 | 选择作业进入内存 | 内存管理 | 分配CPU |
| 是否必需 | 批处理系统必需 | 有交换功能的系统 | 所有系统必需 |

---

## 二、调度的目标

### 2.1 共同目标

#### 资源利用率

**CPU利用率**：
$$CPU利用率 = \frac{CPU有效工作时间}{CPU总的运行时间}$$

**目标**：使CPU尽可能忙碌

#### 公平性

**定义**：每个进程获得合理的CPU时间

**注意**：公平不等于平均，要考虑进程优先级

#### 平衡性

**定义**：系统各个部分都忙碌

**例子**：
- CPU繁忙时，I/O设备也应工作
- 避免CPU或I/O设备空闲

### 2.2 批处理系统的目标

#### 平均周转时间短

**周转时间**：从作业提交到作业完成的时间间隔。

$$周转时间 = 作业完成时间 - 作业提交时间$$

**平均周转时间**：
$$平均周转时间 = \frac{1}{n}\sum_{i=1}^{n}周转时间_i$$

#### 带权周转时间短

**带权周转时间**：
$$带权周转时间 = \frac{周转时间}{实际运行时间}$$

**平均带权周转时间**：
$$平均带权周转时间 = \frac{1}{n}\sum_{i=1}^{n}带权周转时间_i$$

**意义**：反映作业的等待时间相对于执行时间的比例

#### 系统吞吐量高

**吞吐量**：单位时间内完成的作业数。

**目标**：在单位时间内完成尽可能多的作业

### 2.3 分时系统的目标

#### 响应时间快

**响应时间**：从用户提交请求到系统首次产生响应的时间。

$$响应时间 = 首次响应时间 - 请求提交时间$$

**目标**：使响应时间尽可能短，提高用户体验

### 2.4 实时系统的目标

#### 截止时间的保证

**截止时间**：任务必须开始或完成的最迟时间。

**目标**：
- 硬实时系统：必须满足截止时间
- 软实时系统：尽量满足截止时间

#### 可预测性

**目标**：系统行为可预测，便于分析和验证

---

## 三、调度算法评价指标

### 3.1 CPU利用率

$$CPU利用率 = \frac{CPU忙碌时间}{总时间}$$

### 3.2 吞吐量

$$吞吐量 = \frac{完成作业数}{总时间}$$

### 3.3 周转时间

$$周转时间 = 完成时间 - 到达时间$$

### 3.4 等待时间

$$等待时间 = 周转时间 - 实际运行时间$$

### 3.5 响应时间

$$响应时间 = 首次响应时间 - 请求提交时间$$

### 3.6 带权周转时间

$$带权周转时间 = \frac{周转时间}{实际运行时间}$$

---

## 四、调度时机

### 4.1 需要进程调度的时机

1. **进程终止**：运行进程完成或异常终止
2. **进程阻塞**：运行进程需要等待某事件
3. **进程创建**：新进程创建后
4. **中断发生**：I/O中断、时钟中断等
5. **时间片用完**：抢占式调度中，进程时间片用完

### 4.2 不能调度的时机

1. **处理中断时**：中断处理需要快速完成
2. **进程在操作系统内核临界区**：防止系统不稳定
3. **其他需要屏蔽中断的原子操作期间**

---

## 五、调度方式

### 5.1 非抢占式调度

**定义**：一旦将CPU分配给某进程，直到该进程完成或阻塞，才将CPU分配给其他进程。

**优点**：
- 实现简单
- 系统开销小
- 适合批处理系统

**缺点**：
- 响应时间长
- 不适合分时系统和实时系统
- 可能导致优先级反转

### 5.2 抢占式调度

**定义**：允许调度程序根据某种策略，强制收回正在运行进程的CPU，分配给其他进程。

**抢占原则**：
1. **优先权原则**：高优先级进程到达，抢占低优先级进程的CPU
2. **短进程优先原则**：短进程到达，抢占长进程的CPU
3. **时间片原则**：进程时间片用完，被抢占

**优点**：
- 响应时间快
- 适合分时系统和实时系统
- 可以防止一个进程长时间占用CPU

**缺点**：
- 实现复杂
- 系统开销大
- 需要保存和恢复进程现场

---

## 六、考研重点

1. **调度的三个层次**：高级、中级、低级调度的功能和区别
2. **调度的目标**：资源利用率、公平性、周转时间、响应时间
3. **评价指标**：CPU利用率、吞吐量、周转时间、等待时间、响应时间
4. **调度时机**：什么时候需要调度，什么时候不能调度
5. **调度方式**：抢占式和非抢占式的优缺点

---

*下一节：3.2 调度时机、切换与过程*