进程与调度 · 操作系统

为什么需要它

直觉理解

定义

进程 Process

A running program: its code, its own memory, open files and a state (running, ready, blocked). Identified by a PID.

正在运行的程序：它的代码、独立的内存、打开的文件，以及一个状态（运行、就绪、阻塞）。用 PID 标识。

上下文切换

Saving one process's CPU state and loading another's so it can continue. Necessary for sharing, but pure overhead.

保存一个进程的 CPU 状态、载入另一个进程的状态，让它继续运行。共享 CPU 必须这样做，但它本身是纯开销。

示例

1
2
3
4
5
6
7
8
9
10
11
12

from collections import deque

ready = deque([("A", 5), ("B", 2), ("C", 3)])
quantum, clock = 2, 0
while ready:
    name, left = ready.popleft()
    run = min(quantum, left)
    clock += run
    if left - run > 0:
        ready.append((name, left - run))
    else:
        print(name, "done at", clock)

常见错误

小测验

1
2
3
4
5

jobs = [("A", 3), ("B", 1), ("C", 2)]
clock = 0
for name, need in sorted(jobs, key=lambda j: j[1]):
    clock += need
    print(name, clock)

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

1. 预测输出跟踪调度器

   准确写出这段程序的输出。

2. 改需求用上时间片

   finish_times(jobs, quantum) 应该模拟轮转调度，返回每个任务完成时刻的字典。现在它让每个任务一口气跑完（先来先服务）。改成每轮最多运行 quantum 个单位，没做完的排到队尾。

3. 从零写平均等待时间

   所有任务都在时刻 0 到达，按给定顺序一个接一个运行。一个任务的等待时间是它开始之前等了多久。写函数 avg_wait(bursts)，返回平均等待时间（浮点数）。然后在编辑器里用同样的任务、两种顺序试一试，看看为什么短作业优先有好处。

本课术语