3590 字
18 分钟
Peterson 算法笔记

Peterson 算法笔记#

1. 问题背景:临界区(Critical Section)#

多个进程/线程同时访问共享数据时,会产生竞态条件(Race Condition)。

例如:

int count = 0;
// 进程A
count++;
// 进程B
count++;

count++实际上不是一步:

读取count
+
1
+
写回count

如果两个进程交错执行:

A读 count=0
B读 count=0
A写 count=1
B写 count=1

最终:

count=1

而不是:

count=2

因此需要保证:

同一时间只能有一个进程进入修改共享数据的代码区域。

这个区域称为:

临界区(Critical Section)


2. 临界区问题的三个要求#

一个正确的同步算法需要满足:


(1) 互斥 Mutual Exclusion#

任何时刻:

最多只有一个进程在临界区。

例如:

P0进入临界区
P1必须等待

(2) 进展 Progress#

如果:

  • 当前没有人在临界区
  • 有进程想进入

那么:

不能无限等待,必须决定谁进入。


(3) 有限等待 Bounded Waiting#

一个进程请求进入后:

不能永远被其他进程插队。

防止:

P0进去
P0出来
P0又进去
P0又出来
P1永远等待

3. Peterson算法简介#

Peterson算法:

一个只使用共享变量的软件算法,用于解决两个进程之间的临界区互斥问题。

特点:

  • 只支持两个进程
  • 不需要硬件锁指令
  • 通过共享变量实现同步

假设:

两个进程:
P0
P1

4. Peterson算法核心变量#

两个共享变量:

bool flag[2];
int turn;

(1) flag数组#

表示:

某个进程是否想进入临界区。

例如:

flag[0]=true;

表示:

P0想进入临界区
flag[1]=true;

表示:

P1想进入临界区

(2) turn变量#

表示:

如果两个进程同时想进入,让谁优先。

例如:

turn=1;

表示:

如果发生冲突,让P1先进入

5. Peterson算法代码#

对于进程 Pi:

do {
flag[i] = true;
turn = j;
while(flag[j] && turn == j)
;
// critical section
flag[i] = false;
// remainder section
} while(true);

其中:

i = 当前进程编号
j = 另一个进程编号

例如:

P0:

i=0
j=1

P1:

i=1
j=0

6. 代码含义#

第一步:表示想进入#

flag[i]=true;

含义:

我要进入临界区

第二步:主动让对方优先#

turn=j;

含义:

如果我们同时想进入,
让对方先

为什么?

因为两个进程都会执行:

turn=对方

最后写入 turn 的进程会让出机会。


第三步:等待#

while(flag[j] && turn==j);

翻译:

如果:
对方也想进入
并且
现在轮到对方
那么我等待

第四步:进入临界区#

// critical section

此时:

只有一个进程执行。


第五步:退出#

flag[i]=false;

表示:

我已经退出,可以让别人进入。

7. 关键情况分析:两个进程同时进入#

假设:

P0、P1同时想进入。

初始:

flag[0]=false
flag[1]=false

P0执行:

flag[0]=true;
turn=1;

表示:

P0想进入
冲突时让P1

P1执行:

flag[1]=true;
turn=0;

表示:

P1想进入
冲突时让P0

最终:

flag[0]=true
flag[1]=true
turn=0

P0检查:

while(flag[1] && turn==1)

代入:

true && false

结果:

false

P0进入。


P1检查:

while(flag[0] && turn==0)

代入:

true && true

等待。


结果:

P0进入临界区
P1等待

保证互斥。


8. 为什么一定不会同时进入?#

假设:

P0和P1同时进入。

因为:

flag[0]=true
flag[1]=true

所以:

两个进程都不能依靠 flag 放行。

只能依靠:

turn

但是:

turn只能等于0或者1

不可能:

turn=0
同时
turn=1

因此:

两个进程不可能同时满足进入条件。


9. Peterson算法的问题#

(1) 只能两个进程#

不能直接扩展到:

P0
P1
P2
...
Pn

(2) 忙等待(Busy Waiting)#

等待代码:

while(...)
;

CPU一直执行循环。

例如:

CPU:
检查
检查
检查
检查

浪费CPU资源。


(3) 依赖内存访问顺序#

现代CPU可能:

  • 指令乱序执行
  • 缓存不一致

实际系统需要:

  • 原子指令
  • 内存屏障(Memory Barrier)

10. Peterson算法在OS中的意义#

Peterson算法现在很少直接使用。

但是它展示了:

仅靠共享变量,也可以构造进程同步机制。

发展路线:

Peterson算法
|
↓
硬件原子指令
|
↓
自旋锁 Spinlock
|
↓
互斥锁 Mutex
|
↓
信号量 Semaphore

11. 一句话总结#

Peterson算法:

两个进程通过 flag[] 表示“我想进入”,通过 turn 表示“冲突时谁优先”,利用二者组合保证任意时刻只有一个进程进入临界区。

核心:

flag[i]=true; // 我要进入
turn=j; // 让对方优先
while(flag[j] && turn==j);
// 等待
// 临界区
flag[i]=false; // 退出

记忆:

flag = 意愿
turn = 谦让
有意愿 + 有优先级
=> 保证互斥

你已经理解 Peterson 算法了。现在来看:

  • 自旋锁(Spinlock)
  • 互斥锁(Mutex)

它们其实都是为了解决同一个问题:

两个人不能同时使用同一个东西。

比如:

一个厕所 🚻
小明想进去
小红也想进去
怎么办?

一、自旋锁(Spinlock)#

1. 最简单理解#

自旋锁就是:

门口放一个锁,进不去的人一直站在那里看门有没有开。

比如:

厕所:

🚻

门上有一个状态:

0 = 没人
1 = 有人

小明来了:

发现:

锁=0

于是:

锁=1

进去。


小红来了:

发现:

锁=1

说明:

有人正在里面

怎么办?

她不走。

她一直:

看
看
看
看

直到:

锁=0

然后进去。

这就是:

自旋(spin)


2. 代码长什么样?#

非常像 Peterson:

while(lock == 1)
{
// 什么也不干,一直等
}
lock = 1;
// 临界区
lock = 0;

重点:

while()

里面一直循环。


3. 为什么叫自旋?#

因为CPU像这样:

检查锁
↓
没开
↓
再检查
↓
没开
↓
再检查

像原地转圈:

spin spin spin

所以叫:

Spin Lock(自旋锁)


4. 自旋锁的问题#

假设:

小明进去厕所:

10秒

小红:

门口等10秒

她一直:

看门
看门
看门

CPU也一样:

while(lock)

CPU:

100%
100%
100%

但是啥也没干。

浪费。


5. 那什么时候用自旋锁?#

如果等待时间非常短:

例如:

等1微秒

那睡觉反而更麻烦。

因为睡眠需要:

保存状态
↓
切换进程
↓
唤醒

这个过程可能比等待还慢。

所以:

短等待:

自旋锁

二、互斥锁(Mutex)#

Mutex:

全称:

Mutual Exclusion Lock

意思:

互斥锁。


1. 小学生版本#

还是厕所。

小红来了:

发现:

有人

她不会站在那里一直看。

她:

去旁边休息

等有人通知:

厕所空了

再回来。

这就是互斥锁。


2. 和自旋锁区别#

自旋锁:#

等待的人:
站门口
一直看

图:

小明 🚻
小红 👀👀👀

互斥锁:#

小明 🚻
小红 😴
等待通知

3. 操作系统里面发生什么?#

假设:

进程A拿锁:

lock()

成功:

进入临界区

进程B:

也:

lock()

发现:

锁已经有人拿了

怎么办?

不是循环。

而是:

操作系统:

把B挂起

也就是:

阻塞(Block)

CPU:

原来:

A运行
B运行

变成:

A运行
B睡觉

等A:

unlock()

释放锁。

系统:

唤醒B

B继续。


4. Mutex大概实现#

伪代码:

lock(){
if(lock_free)
{
获取锁;
}
else
{
睡眠等待;
}
}
unlock(){
释放锁;
唤醒等待者;
}

三、自旋锁 vs 互斥锁#

看这个表:

自旋锁 互斥锁
等待方式 一直循环 睡眠等待
CPU占用 高 低
切换进程 不需要 需要
适合 短等待 长等待
实现难度 简单 复杂
常用于 内核 用户程序

四、举个实际例子#

假设:

情况1#

锁只需要等:

100纳秒

例如:

修改一个内核变量。

如果用mutex:

睡眠
唤醒

花:

几微秒

反而更慢。

所以:

使用:

自旋锁

情况2#

锁可能等:

5秒

例如:

下载文件。

如果自旋:

CPU:

100%

5秒。

太浪费。

使用:

mutex

让线程睡觉。


五、它们和Peterson算法关系#

你刚学的:

Peterson:

软件方法

↓

自旋锁:

硬件支持的简单锁

↓

mutex:

操作系统管理的锁

发展:

Peterson算法
↓
spinlock
(一直等)
↓
mutex
(睡眠等待)
↓
semaphore
(多个资源)

六、为什么需要硬件?#

这里有一个关键问题:

如果:

lock=0;
if(lock==0)
lock=1;

两个CPU同时执行:

CPU1:

看到0

CPU2:

看到0

然后:

CPU1:

lock=1

CPU2:

lock=1

两个都进去了。

失败。

所以现代锁需要:

原子操作#

例如:

test_and_set()

意思:

检查并修改必须一步完成。

CPU保证:

别人不能插进来。

最后记忆版#

自旋锁#

一句话:

抢不到锁的人一直在那里等。

特点:

while(lock)
;

优点:

  • 快
  • 没有线程切换

缺点:

  • 浪费CPU

互斥锁#

一句话:

抢不到锁的人睡觉,等别人叫醒。

特点:

lock失败
↓
阻塞
↓
等待唤醒

优点:

  • 节省CPU

缺点:

  • 有上下文切换开销

最核心区别:

自旋锁:
等待 = 消耗CPU
互斥锁:
等待 = 让出CPU

你后面学 Linux 内核时会看到一个很有意思的设计:

Linux 内核里面大量使用 spinlock,而普通应用程序大量使用 mutex。

原因就是:内核不能随便睡眠,而用户程序更关心CPU利用率。

条件变量中的 while + wait 机制笔记#

1. 背景:为什么需要条件变量?#

在并发程序中,线程经常需要等待某个条件成立。

例如生产者消费者:

消费者:
如果没有数据
等待
有数据
消费

最简单的想法:

while(data == 0)
{
}

但是这是:

忙等待(Busy Waiting)#

线程一直占用 CPU:

检查
检查
检查
检查
...

导致:

  • 浪费 CPU
  • 占用时间片
  • 无法充分利用处理器

因此需要:

当条件不满足时,让线程睡眠;条件满足后,再唤醒线程。

这就是条件变量(Condition Variable)。


2. 条件变量核心接口#

典型使用:

std::unique_lock<std::mutex> lock(mtx);
while(!condition)
{
cv.wait(lock);
}

其中:

  • mutex:保护共享数据
  • condition:判断是否满足条件
  • wait:等待条件成立

3. wait() 的真正作用#

很多初学者误解:

while(!ready)
{
cv.wait(lock);
}

认为:

while会不断检查ready。

实际上错误。

真正流程:

while判断一次
↓
条件不满足
↓
进入wait()
↓
线程睡眠
↓
等待唤醒
↓
重新判断

4. wait()内部发生了什么?#

执行:

cv.wait(lock);

实际上包含三个关键步骤。

第一步:释放mutex#

假设:

消费者:

lock();
while(buffer.empty())
{
wait();
}

如果wait不释放锁:

消费者睡眠,但是还拿着锁。

生产者:

lock();
buffer.push();

无法获得锁。

结果:

生产者无法生产。

消费者无法醒来。

因此:

wait必须:

释放锁

第二步:线程进入阻塞状态#

操作系统:

修改线程状态:

RUNNING
↓
BLOCKED

然后:

调度器:

不再选择该线程运行

CPU去运行其他线程。

此时:

线程:

  • 不占CPU
  • 不执行while
  • 不检查条件

第三步:等待唤醒#

其他线程:

cv.notify_one();

或者:

cv.notify_all();

操作系统:

等待队列
↓
就绪队列

线程重新等待调度。

注意:

唤醒 ≠ 立即执行。

线程只是:

READY

状态。

什么时候运行:

由调度器决定。


5. 为什么需要 while,而不是 if?#

错误:

if(!ready)
{
cv.wait(lock);
}
使用资源;

正确:

while(!ready)
{
cv.wait(lock);
}
使用资源;

原因:

原因1:虚假唤醒(Spurious Wakeup)#

条件变量允许:

没有收到通知,也可能醒来。

例如:

线程睡眠
↓
突然醒
↓
检查条件
↓
ready=false

如果使用if:

直接继续执行。

产生错误。

while:

醒来
↓
检查
↓
条件不满足
↓
重新睡眠

原因2:多个线程竞争资源#

例如:

两个消费者:

C1
C2

生产者:

生产一个资源:

resource=1

调用:

notify_all()

两个消费者醒来。

但是:

只有一个能拿到资源。

流程:

C1获得锁
检查:
resource=1
消费
释放锁
C2获得锁
检查:
resource=0
重新wait

如果使用if:

C2会错误执行。


6. while + wait 和忙等待区别#

忙等待#

代码:

while(!ready)
{
}

执行:

CPU运行
检查ready
检查ready
检查ready

状态:

RUNNING

CPU占用:

高。


条件变量#

代码:

while(!ready)
{
wait();
}

执行:

检查一次
↓
睡眠
↓
等待通知
↓
醒来检查

状态:

BLOCKED

CPU占用:

接近0。


7. notify_one 和 notify_all#

notify_one#

唤醒一个等待线程:

cv.notify_one();

适合:

只有一个线程能够继续工作的情况。

例如:

生产一个商品:

消费者1
消费者2
消费者3

只需要叫醒一个。


notify_all#

唤醒所有线程:

cv.notify_all();

例如:

系统状态发生变化:

所有等待者都需要重新检查。


8. notify_all 会不会导致CPU空转?#

不会。

错误理解:

notify_all
↓
所有线程同时运行
↓
CPU爆炸

实际:

notify_all
↓
所有线程进入READY
↓
竞争mutex
↓
只有一个获得锁
↓
其他线程继续阻塞

过程:

线程A:
获得锁
检查条件
线程B:
等待锁
线程C:
等待锁

没有大量循环。


但是:

会产生:

惊群效应(Thundering Herd)#

例如:

1000个线程等待:

notify_all()

全部醒来:

1000个线程竞争锁

最后:

只有一个成功。

造成:

  • 调度开销增加
  • 缓存失效

因此:

能使用:

notify_one()

就不要:

notify_all()

9. 条件变量完整模型#

条件变量由:

共享状态#

例如:

int count;

Mutex#

保护状态:

mutex

Condition Variable#

等待通知:

condition_variable

关系:

共享数据
|
|
mutex保护
|
|
------------------
|
condition variable
|
wait / notify

10. 生产者消费者模型#

消费者#

lock();
while(buffer.empty())
{
wait();
}
取数据;
unlock();

含义:

没有数据
↓
睡觉
↓
有数据
↓
消费

生产者#

lock();
生产数据;
notify();
unlock();

含义:

产生数据
↓
通知消费者

11. 与操作系统调度联系#

条件变量本质是:

线程状态转换。

wait()#

线程:

Running
↓
Blocked

notify()#

线程:

Blocked
↓
Ready

调度器#

决定:

Ready
↓
Running

所以:

条件变量依赖:

  • 线程状态管理
  • 调度器
  • 阻塞队列
  • 唤醒机制

12. 核心总结#

wait()#

作用:

让线程等待条件成立。

内部:

释放锁
↓
进入阻塞队列
↓
睡眠
↓
被唤醒
↓
重新获得锁
↓
返回

while#

作用:

保证醒来后重新检查条件。

不是轮询。

执行次数:

约等于:

唤醒次数

不是:

CPU循环次数

忙等待 vs 条件等待#

忙等待 条件变量
代码 while空循环 while + wait
线程状态 Running Blocked
CPU 持续占用 释放
效率 低 高
用途 极短等待 事件等待

一句话记忆#

wait负责让线程睡觉,while负责保证正确;while + wait不是轮询,而是“醒一次检查一次,不满足继续睡”。

这也是 Linux/POSIX 线程同步中最重要的设计模式之一。

Peterson 算法笔记
https://sanzenin.top/posts/obsidian/并发/
作者
Sanzenin 凪
发布于
2026-08-25
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取