CHAPTER 02 · 2.1 程序的并发执行 3 个程序 · 可调 CPU / I/O 时长 · 可切换顺序与并发 ← 章节首页

并发之后,
程序不再是全部

顺序执行时,程序独占整台机器,结果只由代码和输入决定。一旦多个程序同时进入内存, 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。 预设只载入数值,点“应用”才生效。应用同时会停止并重置前趋图与共享计数器,避免旧动画继续推进。表格可直接逐格修改,手机上与桌面同样完整显示。

实验一 · 顺序 vs 并发SEQUENTIAL / CONCURRENT

T = 0 s

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。 三种程序固定,只切换执行方式,观察总耗时与两条资源轨道的差别。

← 左右滑动查看完整时间轴 →

  • CPU 段
  • I/O 段
  • 播放头
先播放一遍,再对比两种模式下 CPU 与 I/O 的忙闲。

I/O 利用率按“单一 I/O 设备”计算:多个程序的 I/O 段重叠时只计一次占用。 顺序执行中,一个程序做 I/O,CPU 只能空闲等待;并发执行把这段空闲交给别的程序。

实验二 · 前趋图调度PRECEDENCE GRAPH

点击节点尝试执行

边表示“必须先完成”。S1 是唯一入口,S4 要等 S2、S3 都完成;S5 与 S6 互不依赖,谁先执行都合法。

S1 入口 S2 分支 A S3 分支 B S4 汇合 S5 出口 A S6 出口 B

手机上以前趋图节点列表呈现:每行显示状态与直接前驱,点任意行即可执行(前驱全部完成后才可执行)。

自动序列:S1 → S3 → S2 → S4 → S6 → S5

前趋图只规定偏序:S2 与 S3 谁先、S5 与 S6 谁先,都不影响正确性。合法执行序列因此不唯一, 这也是“并发程序的结果依赖推进顺序”的根源。窄屏下可在图框内左右滑动查看 S4–S6。

实验三 · 共享计数器LOST UPDATE

第 0 / 12 步

P1、P2 执行同一段代码:把共享变量 N 加 1,各做两次,N 初值 0,正确答案是 4。 每一步拆成“读 → 加 1 → 写回”,推进顺序不同,结果就会不同。

进程 P1 N = N + 1,做 2 次

    SHARED MEMORY · N
    0共享变量 N
    P1 寄存器 R1—
    P2 寄存器 R2—
    正确结果应为 4,现在还没开始。

    进程 P2 N = N + 1,做 2 次

      当前为预设交错:先让两个进程都读到旧值,再分别写回。
      逐步执行日志PRESET

        把“为什么需要进程”讲清楚

        并发执行带来三个新问题:顺序被打断、资源被共享、结果不可再现。进程正是为收拾这三件事而设计的抽象。

        2.1 / 核心
        01 / 前趋图

        偏序,而不是一条固定路线

        前趋图(precedence graph)是一个有向无环图:结点表示程序段、语句或进程,有向边 Pi → Pj 表示 Pi 必须在 Pj 开始前完成。

        • 若存在边 Pi → Pj,Pi 是 Pj 的直接前趋,Pj 是 Pi 的直接后继
        • 沿边可到达的都算前趋,其中直接的才叫“直接前趋”
        • 没有任何前趋的结点可以立即开始;入边全部完成的结点才变成可选

        本页的 S2 与 S3 之间没有边,说明二者可以任意先后——前趋图给出的是偏序,合法的拓扑序列不止一条。

        02 / 顺序执行

        三条性质,都建立在“独占”上

        程序顺序执行时,处理机一次只为一个程序服务,于是有三条性质:

        • 顺序性:严格按程序规定的次序执行,前一操作结束才做后一操作
        • 封闭性:程序独占全机资源,运行时资源状态只由本程序改变,结果不受外界影响
        • 可再现性:初始条件和执行环境相同,重复执行必然得到相同结果

        可再现性让“跑一遍就能验证程序”成立;调试、复现缺陷都依赖它。并发执行打破的正是这个前提。

        03 / 并发执行

        间断、失封闭、不可再现

        多个程序同时进入内存、交替占用 CPU 后,顺序执行的三条性质变成并发执行的三条特征:

        • 间断性:程序因等待 I/O 或竞争资源而“走走停停”,不再一气呵成
        • 失去封闭性:资源被多个程序共享,一个程序可能改变另一个程序的状态
        • 不可再现性:推进速度与交错顺序不同,同一组输入可能得到不同结果

        并发是单处理机上多个程序交替执行,宏观同时、微观串行;并行是多处理机上真正同时执行。本页实验一演示的是并发。

        04 / Bernstein

        什么时候两个程序“互不干扰”

        设 R(Pi)、W(Pi) 分别是 Pi 的读集与写集。若下面三条同时成立,P1 与 P2 并发执行的结果与某种顺序执行相同:

        R(P1) ∩ W(P2) = ∅
        W(P1) ∩ R(P2) = ∅
        W(P1) ∩ W(P2) = ∅

        即不存在“读—写”“写—读”“写—写”冲突;只读—只读可以随意重叠。它只保证结果等价,不负责调度:谁先谁后、优先级、公平性都不在条件里。

        而且读写集在运行时才完全确定(取决于分支、参数、地址),所以它不能直接当作调度依据。

        05 / 一句话

        进程,是并发执行程序的抽象

        程序是静态的指令集合,本身不会“跑”;并发执行需要记录执行到哪、占有哪些资源、处于什么状态、和谁共享什么。把这些现场信息连同程序与数据一起管理起来,就得到进程。

        所以“为什么有了程序还需要进程”的答案是:程序描述做什么,进程描述这一次执行。下一节会用 PCB 说明内核如何保存这份现场。

        06 / 误区

        四个常见误判

        • “并发就是同时运行”:单 CPU 上是交替,任意时刻只有一个程序占用处理机
        • “并发一定更快”:只有能重叠 I/O 或使用多处理机时才更快;纯 CPU 程序并发反而多出切换开销
        • “不可再现就是程序写错了”:更准确地说,是共享数据缺少同步,属于竞态;加上互斥后可恢复可再现(见 2.5)
        • “Bernstein 条件可以拿来排调度”:它是正确性判据,不是调度算法,读写集也无法在调度前廉价获得

        课堂追问

        为什么并发执行会失去可再现性?

        因为正确性依赖多个程序对共享数据的读写交错顺序,而顺序由时间片、I/O 完成时刻和中断时机决定。实验三中两个进程都先读出 0,再各自加 1 写回,后写的一次覆盖前一次,两次“加 1”只留下一次效果。程序与输入都没变,只是推进速度不同,结果就成了 2、3 或 4。要恢复可再现性,必须用同步把“读—改—写”变成不可分割的临界区。

        前趋图能不能有环?如果画出了环意味着什么?

        不能。前趋图的边表示“必须先于”,若存在环 S1 → S2 → S3 → S1,就会推出 S1 必须先于自己完成,没有任何结点可以首先开始,拓扑排序不存在,执行会永久等待。因此前趋图必须是有向无环图(DAG)。真实系统里如果出现循环等待,说明资源分配或同步设计有错,需要打破环:调整执行顺序、合并结点,或引入资源有序分配等策略。

        Bernstein 条件能不能直接作为实际调度的依据?

        不能。它要求事先知道读集与写集,而读写集依赖运行时才确定的参数、分支与地址,静态分析既不精确也不现实;内核不可能在每次调度前算集合交集。更重要的是,这三条只回答“并发是否改变结果”,不回答“该让谁先跑”:优先级、截止时间、公平性都不在条件内。它是正确性判据,不是调度算法。

        既然并发会带来这么多问题,为什么还要并发?

        因为程序并不总占着 CPU:实验一里 25 s 中有 11 s 是 I/O。顺序执行让 CPU 空转,并发把等待时间交给另一个程序,总耗时降到 14 s,CPU 利用率从 56% 升到 100%。并发还能让多用户共享一台机器、让交互程序等待输入时不妨碍后台任务。代价是保存现场、切换上下文并处理共享数据冲突,这正是进程与同步要解决的问题。

        ← PREV · 第 2 章章节首页:进程管理知识地图