Peterson 算法笔记
1. 问题背景:临界区(Critical Section)
多个进程/线程同时访问共享数据时,会产生竞态条件(Race Condition)。
例如:
int count = 0;
// 进程Acount++;
// 进程Bcount++;count++实际上不是一步:
读取count+1+写回count如果两个进程交错执行:
A读 count=0B读 count=0
A写 count=1B写 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算法:
一个只使用共享变量的软件算法,用于解决两个进程之间的临界区互斥问题。
特点:
- 只支持两个进程
- 不需要硬件锁指令
- 通过共享变量实现同步
假设:
两个进程:
P0P14. 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=0j=1P1:
i=1j=06. 代码含义
第一步:表示想进入
flag[i]=true;含义:
我要进入临界区第二步:主动让对方优先
turn=j;含义:
如果我们同时想进入,让对方先为什么?
因为两个进程都会执行:
turn=对方最后写入 turn 的进程会让出机会。
第三步:等待
while(flag[j] && turn==j);翻译:
如果:
对方也想进入并且
现在轮到对方
那么我等待第四步:进入临界区
// critical section此时:
只有一个进程执行。
第五步:退出
flag[i]=false;表示:
我已经退出,可以让别人进入。7. 关键情况分析:两个进程同时进入
假设:
P0、P1同时想进入。
初始:
flag[0]=falseflag[1]=falseP0执行:
flag[0]=true;turn=1;表示:
P0想进入冲突时让P1P1执行:
flag[1]=true;turn=0;表示:
P1想进入冲突时让P0最终:
flag[0]=trueflag[1]=true
turn=0P0检查:
while(flag[1] && turn==1)代入:
true && false结果:
falseP0进入。
P1检查:
while(flag[0] && turn==0)代入:
true && true等待。
结果:
P0进入临界区P1等待保证互斥。
8. 为什么一定不会同时进入?
假设:
P0和P1同时进入。
因为:
flag[0]=trueflag[1]=true所以:
两个进程都不能依靠 flag 放行。
只能依靠:
turn但是:
turn只能等于0或者1不可能:
turn=0同时turn=1因此:
两个进程不可能同时满足进入条件。
9. Peterson算法的问题
(1) 只能两个进程
不能直接扩展到:
P0P1P2...Pn(2) 忙等待(Busy Waiting)
等待代码:
while(...) ;CPU一直执行循环。
例如:
CPU:
检查检查检查检查浪费CPU资源。
(3) 依赖内存访问顺序
现代CPU可能:
- 指令乱序执行
- 缓存不一致
实际系统需要:
- 原子指令
- 内存屏障(Memory Barrier)
10. Peterson算法在OS中的意义
Peterson算法现在很少直接使用。
但是它展示了:
仅靠共享变量,也可以构造进程同步机制。
发展路线:
Peterson算法 | ↓硬件原子指令 | ↓自旋锁 Spinlock | ↓互斥锁 Mutex | ↓信号量 Semaphore11. 一句话总结
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()释放锁。
系统:
唤醒BB继续。
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:
看到0CPU2:
看到0然后:
CPU1:
lock=1CPU2:
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:多个线程竞争资源
例如:
两个消费者:
C1C2生产者:
生产一个资源:
resource=1调用:
notify_all()两个消费者醒来。
但是:
只有一个能拿到资源。
流程:
C1获得锁
检查:
resource=1
消费
释放锁
C2获得锁
检查:
resource=0
重新wait如果使用if:
C2会错误执行。
6. while + wait 和忙等待区别
忙等待
代码:
while(!ready){
}执行:
CPU运行
检查ready
检查ready
检查ready状态:
RUNNINGCPU占用:
高。
条件变量
代码:
while(!ready){ wait();}执行:
检查一次
↓
睡眠
↓
等待通知
↓
醒来检查状态:
BLOCKEDCPU占用:
接近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
保护状态:
mutexCondition Variable
等待通知:
condition_variable关系:
共享数据 | | mutex保护 | | ------------------ | condition variable | wait / notify10. 生产者消费者模型
消费者
lock();
while(buffer.empty()){ wait();}
取数据;
unlock();含义:
没有数据
↓
睡觉
↓
有数据
↓
消费生产者
lock();
生产数据;
notify();
unlock();含义:
产生数据
↓
通知消费者11. 与操作系统调度联系
条件变量本质是:
线程状态转换。
wait()
线程:
Running
↓
Blockednotify()
线程:
Blocked
↓
Ready调度器
决定:
Ready
↓
Running所以:
条件变量依赖:
- 线程状态管理
- 调度器
- 阻塞队列
- 唤醒机制
12. 核心总结
wait()
作用:
让线程等待条件成立。
内部:
释放锁
↓
进入阻塞队列
↓
睡眠
↓
被唤醒
↓
重新获得锁
↓
返回while
作用:
保证醒来后重新检查条件。
不是轮询。
执行次数:
约等于:
唤醒次数不是:
CPU循环次数忙等待 vs 条件等待
| 忙等待 | 条件变量 | |
|---|---|---|
| 代码 | while空循环 | while + wait |
| 线程状态 | Running | Blocked |
| CPU | 持续占用 | 释放 |
| 效率 | 低 | 高 |
| 用途 | 极短等待 | 事件等待 |
一句话记忆
wait负责让线程睡觉,while负责保证正确;while + wait不是轮询,而是“醒一次检查一次,不满足继续睡”。
这也是 Linux/POSIX 线程同步中最重要的设计模式之一。
分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 83 天
部分内容可能已过时