CHAPTER 02 · 2.5 进程同步与互斥 丢失更新复现 · 记录型信号量 P/V 单步 ← 上一节:进程控制

两个进程,
一个计数器

N++ 在高级语言里是一条语句,在机器里却是“读—改—写”三条指令。两条执行流只要在中间交错一次, 两次自增就只剩一次效果。下面先亲手制造这种丢失,再用临界区修好它;然后把信号量拆成 P/V 两个原子动作, 看清楚 负值到底在记录什么。

自定义实验参数 自增次数 · 进程数 · 默认加锁 · 信号量初值 展开 ▾
预设

应用后会重建竞态时间轴、进程卡片与指标,并重置 P/V 实验和信号量值。P/V 的语义不变:P 先减再判,小于 0 就阻塞;V 先加再判,小于等于 0 就唤醒队首。加锁只影响竞态实验,不会改写 P/V 的阻塞逻辑。

竞态条件复现实验台RACE CONDITION

共享变量 N 初值 0,A、B 各执行 3 次自增。每次自增被拆成 tmp = N → tmp++ → N = tmp。若没有交错,正确结果是 6。

并发执行 N = 0 选择 A 或 B 推进一步,制造一次交错。 T+0
临界区:无锁— 任意两条指令之间都可能被抢占
锁

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

  • 读 N(tmp ← N)
  • 改(tmp++)
  • 写回(N ← tmp)
  • 临界区 / 锁占用

时间轴以 tick 为单位:每次微步骤占 1 格。加锁模式下,一次自增的读 / 改 / 写必须整体在临界区内完成;若锁被占用,另一个进程会在进入区等待,日志会记录这次失败的进入尝试。

P/V 操作单步实验台SEMAPHORE PV

S.value = 1

记录型信号量 S:P(S) 先减 1,若结果小于 0 就阻塞并入等待队列;V(S) 先加 1,若结果小于等于 0 就唤醒队首。负值的绝对值,正好是等待进程数。

SEMAPHORE · S
1S.value
S.value = 1 → 有 1 个资源可用,没有进程等待。
改动初值会重置实验
等待队列 · 阻塞在 S 上0
就绪 / 可执行3

当前操作进程:P1 · 就绪 · 持有 0 个资源

V 操作在本实验里允许由任意选中进程执行:若它没有持有资源,可理解为替一次设备完成中断或上游进程完成释放。真实代码中 V 通常由使用完资源的进程调用,漏掉 V 会造成等待者永久阻塞。

把“同步”讲清楚

互斥解决“不能同时”,同步解决“必须按顺序”,信号量把两者统一成一对原子操作。

2.5 / 核心
01 / 临界区

临界资源与临界区:一次只许一个

临界资源是一次仅允许一个进程使用的资源,如打印机、共享变量、共享缓冲区。访问它的那段代码叫临界区,结构上分成四段:

  • 进入区:检查是否可进,并设置“正在访问”标志;检查和上锁必须原子
  • 临界区:真正读写共享变量
  • 退出区:清除标志,允许其他进程进入
  • 剩余区:临界区之外、不访问共享资源的代码
02 / 同步与互斥

直接制约与间接制约

同步是直接制约:两个进程为完成同一任务而协作,次序由逻辑决定。例如生产者必须等消费者腾出空位,消费者必须等生产者放入数据。互斥是间接制约:多个进程争用同一临界资源,谁先谁后并不重要,只要不重叠。

  • 互斥信号量初值通常为 1,同步信号量初值通常为 0
  • 生产者-消费者问题里两者同时出现:empty/full 管同步,mutex 管互斥
  • 同步约束的是“先后”,互斥约束的是“排他”
03 / 四条准则

空闲让进、忙则等待、有限等待、让权等待

空闲让进:临界区空闲时应立即放行一个请求者,不能因为线程间互相谦让而空转。忙则等待:已有进程在临界区,其他进程必须等待。有限等待:任何进程都应在有限时间内获准进入,不能被无限推迟。让权等待:进不去时应当释放 CPU,不能占着处理器空转。

  • “有限等待”管的是多久能进,防止饥饿
  • “让权等待”管的是等待时占不占 CPU,防止忙等
  • 软件双标志法容易违反空闲让进;整型信号量违反让权等待
04 / 实现方法

软件方案靠算法,硬件方案靠原子指令

单标志法用一个 turn 强制轮流,一方不进另一方也进不去,违反空闲让进。双标志先检查先看对方标志再置位,检查和置位之间可被切换,双方可能同时进入。双标志后检查先置位再检查,又可能双方都谦让而都进不去。Peterson 算法加一个 turn 打破僵局,同时满足互斥与空闲让进。

  • 硬件:TestAndSet 原子地读出旧值并置 true;Swap 原子交换标志
  • 硬件方法实现简单、适合多处理机,但通常仍是忙等
  • 软件算法依赖内存序假设,现代 CPU 上需配合屏障才可靠
05 / 记录型信号量

P/V:值可以为负,负号就是队列长度

整型信号量的 P 操作写成 while (S <= 0); S--;,进程在 CPU 上空转,违反让权等待。记录型信号量增加一个等待队列,把“等”变成阻塞:

P(S): S.value--; if (S.value < 0) block(self), insert(等待队列, self)
V(S): S.value++; if (S.value <= 0) wake(等待队列队首)
  • 值 ≥ 0:可用资源数;值为负:绝对值 = 等待进程数,可用资源为 0
  • AND 型信号量要求一次申请多个资源,全部满足才分配,否则一个都不占,可避免部分分配导致的死锁
  • 信号量集进一步为每类资源规定下限与需求量,适用于一次申请多种资源
06 / 常见误区

P/V 不是 lock/unlock 的同义词

P 可能让调用者阻塞,V 可能唤醒一个完全不同的进程;V 也不一定由“加锁者”执行。把 P/V 当成成对的加解锁,是后续死锁与漏唤醒的根源。

  • 初值决定语义:互斥用 1,同步用 0;把同步信号量初值设成 1,等待方会在数据就绪前通过
  • 顺序不能反:生产者-消费者中若先 P(mutex) 再 P(empty),缓冲区满时生产者抱着锁睡眠,消费者永远进不来(2.6 详述)
  • 只 P 不 V 会耗尽资源;只 V 不 P 会破坏互斥;值为负不是错误,而是等待队列的编码
  • 信号量只保证互斥,不保证“谁先进入”;需要严格次序时得再加同步信号量

课堂追问

为什么“先检查后上锁”仍然可能让两个进程都进入临界区?

因为检查和置位是两条指令,中间可以被中断或调度。A 先读到 flag[B] = false,还没来得及执行 flag[A] = true,CPU 切到 B;B 也读到 flag[A] = false,于是两者都通过检查、都进入临界区。把置位提前(后检查)能避免同时进入,却可能双方都置位后互相谦让,谁都不进。Peterson 算法再加入 turn,指定其中一方先等,才同时解决互斥与进展。

信号量 S.value = -3 表示什么?

表示当前没有可用资源,且有 3 个进程阻塞在 S 的等待队列中。记录型信号量的 P 先把值减 1 再判断,减到负数说明资源已被透支;每执行一次 V,值加 1,若结果仍 ≤ 0 就唤醒队首。因此从 -3 变到 -2,意味着一个等待者被唤醒,队列里还剩 2 个。绝对值就是等待进程数,不是错误码。

忙等与阻塞的本质区别是什么?

忙等的进程仍处于运行态、占着 CPU,反复执行 while (S <= 0) 测试,时间片被白白烧掉;阻塞的进程把自己挂到等待队列并让出 CPU,由调度器选别人运行,等 V 操作或中断把它唤醒。前者实现简单,但浪费处理器,还可能因优先级反转拖垮高优先级任务;后者符合让权等待,代价是需要维护队列与唤醒路径。整型信号量的缺陷正是忙等。

为什么互斥信号量初值取 1,而同步信号量常取 0?

互斥信号量代表“一把锁”,同一时刻只允许一个进程进入临界区,所以初值设为 1;第一个 P 把它减到 0 并获得锁,第二个 P 减到 -1 就阻塞。同步信号量代表“某个事件是否已经发生”,初值 0 表示还没发生:消费者先 P(full) 会阻塞,等生产者放入数据后 V(full),值从 -1 回到 0 并唤醒消费者。若同步信号量初值为 1,消费者可能在数据产生前就通过,同步就失效了。

← PREV · 2.4进程控制与上下文切换