临界资源与临界区:一次只许一个
临界资源是一次仅允许一个进程使用的资源,如打印机、共享变量、共享缓冲区。访问它的那段代码叫临界区,结构上分成四段:
- 进入区:检查是否可进,并设置“正在访问”标志;检查和上锁必须原子
- 临界区:真正读写共享变量
- 退出区:清除标志,允许其他进程进入
- 剩余区:临界区之外、不访问共享资源的代码
N++ 在高级语言里是一条语句,在机器里却是“读—改—写”三条指令。两条执行流只要在中间交错一次, 两次自增就只剩一次效果。下面先亲手制造这种丢失,再用临界区修好它;然后把信号量拆成 P/V 两个原子动作, 看清楚 负值到底在记录什么。
应用后会重建竞态时间轴、进程卡片与指标,并重置 P/V 实验和信号量值。P/V 的语义不变:P 先减再判,小于 0 就阻塞;V 先加再判,小于等于 0 就唤醒队首。加锁只影响竞态实验,不会改写 P/V 的阻塞逻辑。
共享变量 N 初值 0,A、B 各执行 3 次自增。每次自增被拆成 tmp = N → tmp++ → N = tmp。若没有交错,正确结果是 6。
← 左右滑动查看完整竞态时间轴 →
时间轴以 tick 为单位:每次微步骤占 1 格。加锁模式下,一次自增的读 / 改 / 写必须整体在临界区内完成;若锁被占用,另一个进程会在进入区等待,日志会记录这次失败的进入尝试。
记录型信号量 S:P(S) 先减 1,若结果小于 0 就阻塞并入等待队列;V(S) 先加 1,若结果小于等于 0 就唤醒队首。负值的绝对值,正好是等待进程数。
当前操作进程:P1 · 就绪 · 持有 0 个资源
V 操作在本实验里允许由任意选中进程执行:若它没有持有资源,可理解为替一次设备完成中断或上游进程完成释放。真实代码中 V 通常由使用完资源的进程调用,漏掉 V 会造成等待者永久阻塞。
互斥解决“不能同时”,同步解决“必须按顺序”,信号量把两者统一成一对原子操作。
临界资源是一次仅允许一个进程使用的资源,如打印机、共享变量、共享缓冲区。访问它的那段代码叫临界区,结构上分成四段:
同步是直接制约:两个进程为完成同一任务而协作,次序由逻辑决定。例如生产者必须等消费者腾出空位,消费者必须等生产者放入数据。互斥是间接制约:多个进程争用同一临界资源,谁先谁后并不重要,只要不重叠。
empty/full 管同步,mutex 管互斥空闲让进:临界区空闲时应立即放行一个请求者,不能因为线程间互相谦让而空转。忙则等待:已有进程在临界区,其他进程必须等待。有限等待:任何进程都应在有限时间内获准进入,不能被无限推迟。让权等待:进不去时应当释放 CPU,不能占着处理器空转。
单标志法用一个 turn 强制轮流,一方不进另一方也进不去,违反空闲让进。双标志先检查先看对方标志再置位,检查和置位之间可被切换,双方可能同时进入。双标志后检查先置位再检查,又可能双方都谦让而都进不去。Peterson 算法加一个 turn 打破僵局,同时满足互斥与空闲让进。
整型信号量的 P 操作写成 while (S <= 0); S--;,进程在 CPU 上空转,违反让权等待。记录型信号量增加一个等待队列,把“等”变成阻塞:
P 可能让调用者阻塞,V 可能唤醒一个完全不同的进程;V 也不一定由“加锁者”执行。把 P/V 当成成对的加解锁,是后续死锁与漏唤醒的根源。
因为检查和置位是两条指令,中间可以被中断或调度。A 先读到 flag[B] = false,还没来得及执行 flag[A] = true,CPU 切到 B;B 也读到 flag[A] = false,于是两者都通过检查、都进入临界区。把置位提前(后检查)能避免同时进入,却可能双方都置位后互相谦让,谁都不进。Peterson 算法再加入 turn,指定其中一方先等,才同时解决互斥与进展。
表示当前没有可用资源,且有 3 个进程阻塞在 S 的等待队列中。记录型信号量的 P 先把值减 1 再判断,减到负数说明资源已被透支;每执行一次 V,值加 1,若结果仍 ≤ 0 就唤醒队首。因此从 -3 变到 -2,意味着一个等待者被唤醒,队列里还剩 2 个。绝对值就是等待进程数,不是错误码。
忙等的进程仍处于运行态、占着 CPU,反复执行 while (S <= 0) 测试,时间片被白白烧掉;阻塞的进程把自己挂到等待队列并让出 CPU,由调度器选别人运行,等 V 操作或中断把它唤醒。前者实现简单,但浪费处理器,还可能因优先级反转拖垮高优先级任务;后者符合让权等待,代价是需要维护队列与唤醒路径。整型信号量的缺陷正是忙等。
互斥信号量代表“一把锁”,同一时刻只允许一个进程进入临界区,所以初值设为 1;第一个 P 把它减到 0 并获得锁,第二个 P 减到 -1 就阻塞。同步信号量代表“某个事件是否已经发生”,初值 0 表示还没发生:消费者先 P(full) 会阻塞,等生产者放入数据后 V(full),值从 -1 回到 0 并唤醒消费者。若同步信号量初值为 1,消费者可能在数据产生前就通过,同步就失效了。