偏序,而不是一条固定路线
前趋图(precedence graph)是一个有向无环图:结点表示程序段、语句或进程,有向边 Pi → Pj 表示 Pi 必须在 Pj 开始前完成。
- 若存在边
Pi → Pj,Pi 是 Pj 的直接前趋,Pj 是 Pi 的直接后继 - 沿边可到达的都算前趋,其中直接的才叫“直接前趋”
- 没有任何前趋的结点可以立即开始;入边全部完成的结点才变成可选
本页的 S2 与 S3 之间没有边,说明二者可以任意先后——前趋图给出的是偏序,合法的拓扑序列不止一条。
顺序执行时,程序独占整台机器,结果只由代码和输入决定。一旦多个程序同时进入内存, CPU 与 I/O 会重叠,执行顺序由调度决定,顺序性、封闭性、可再现性随之丢失。 这一节用三条时间线,把“为什么需要进程”变成可以看见的事故。
| 程序 | CPU1(s) | I/O(s) | CPU2(s) | 合计 |
|---|---|---|---|---|
| 程序 A | 9 s | |||
| 程序 B | 9 s | |||
| 程序 C | 7 s |
时长范围 1–10 秒,全部为整数。应用后:重建顺序 / 并发两条时间轴与汇总,重算总耗时、CPU 与 I/O 利用率、各程序完成时间,并停止播放回到 T = 0。 预设只载入数值,点“应用”才生效。应用同时会停止并重置前趋图与共享计数器,避免旧动画继续推进。表格可直接逐格修改,手机上与桌面同样完整显示。
A:CPU 3 s → I/O 4 s → CPU 2 s · B:CPU 2 s → I/O 5 s → CPU 2 s · C:CPU 4 s → I/O 2 s → CPU 1 s。 三种程序固定,只切换执行方式,观察总耗时与两条资源轨道的差别。
← 左右滑动查看完整时间轴 →
I/O 利用率按“单一 I/O 设备”计算:多个程序的 I/O 段重叠时只计一次占用。 顺序执行中,一个程序做 I/O,CPU 只能空闲等待;并发执行把这段空闲交给别的程序。
边表示“必须先完成”。S1 是唯一入口,S4 要等 S2、S3 都完成;S5 与 S6 互不依赖,谁先执行都合法。
手机上以前趋图节点列表呈现:每行显示状态与直接前驱,点任意行即可执行(前驱全部完成后才可执行)。
前趋图只规定偏序:S2 与 S3 谁先、S5 与 S6 谁先,都不影响正确性。合法执行序列因此不唯一, 这也是“并发程序的结果依赖推进顺序”的根源。窄屏下可在图框内左右滑动查看 S4–S6。
P1、P2 执行同一段代码:把共享变量 N 加 1,各做两次,N 初值 0,正确答案是 4。 每一步拆成“读 → 加 1 → 写回”,推进顺序不同,结果就会不同。
并发执行带来三个新问题:顺序被打断、资源被共享、结果不可再现。进程正是为收拾这三件事而设计的抽象。
前趋图(precedence graph)是一个有向无环图:结点表示程序段、语句或进程,有向边 Pi → Pj 表示 Pi 必须在 Pj 开始前完成。
Pi → Pj,Pi 是 Pj 的直接前趋,Pj 是 Pi 的直接后继本页的 S2 与 S3 之间没有边,说明二者可以任意先后——前趋图给出的是偏序,合法的拓扑序列不止一条。
程序顺序执行时,处理机一次只为一个程序服务,于是有三条性质:
可再现性让“跑一遍就能验证程序”成立;调试、复现缺陷都依赖它。并发执行打破的正是这个前提。
多个程序同时进入内存、交替占用 CPU 后,顺序执行的三条性质变成并发执行的三条特征:
并发是单处理机上多个程序交替执行,宏观同时、微观串行;并行是多处理机上真正同时执行。本页实验一演示的是并发。
设 R(Pi)、W(Pi) 分别是 Pi 的读集与写集。若下面三条同时成立,P1 与 P2 并发执行的结果与某种顺序执行相同:
即不存在“读—写”“写—读”“写—写”冲突;只读—只读可以随意重叠。它只保证结果等价,不负责调度:谁先谁后、优先级、公平性都不在条件里。
而且读写集在运行时才完全确定(取决于分支、参数、地址),所以它不能直接当作调度依据。
程序是静态的指令集合,本身不会“跑”;并发执行需要记录执行到哪、占有哪些资源、处于什么状态、和谁共享什么。把这些现场信息连同程序与数据一起管理起来,就得到进程。
所以“为什么有了程序还需要进程”的答案是:程序描述做什么,进程描述这一次执行。下一节会用 PCB 说明内核如何保存这份现场。
因为正确性依赖多个程序对共享数据的读写交错顺序,而顺序由时间片、I/O 完成时刻和中断时机决定。实验三中两个进程都先读出 0,再各自加 1 写回,后写的一次覆盖前一次,两次“加 1”只留下一次效果。程序与输入都没变,只是推进速度不同,结果就成了 2、3 或 4。要恢复可再现性,必须用同步把“读—改—写”变成不可分割的临界区。
不能。前趋图的边表示“必须先于”,若存在环 S1 → S2 → S3 → S1,就会推出 S1 必须先于自己完成,没有任何结点可以首先开始,拓扑排序不存在,执行会永久等待。因此前趋图必须是有向无环图(DAG)。真实系统里如果出现循环等待,说明资源分配或同步设计有错,需要打破环:调整执行顺序、合并结点,或引入资源有序分配等策略。
不能。它要求事先知道读集与写集,而读写集依赖运行时才确定的参数、分支与地址,静态分析既不精确也不现实;内核不可能在每次调度前算集合交集。更重要的是,这三条只回答“并发是否改变结果”,不回答“该让谁先跑”:优先级、截止时间、公平性都不在条件内。它是正确性判据,不是调度算法。
因为程序并不总占着 CPU:实验一里 25 s 中有 11 s 是 I/O。顺序执行让 CPU 空转,并发把等待时间交给另一个程序,总耗时降到 14 s,CPU 利用率从 56% 升到 100%。并发还能让多用户共享一台机器、让交互程序等待输入时不妨碍后台任务。代价是保存现场、切换上下文并处理共享数据冲突,这正是进程与同步要解决的问题。