 学习笔记：并发控制与信号量，哲学家就餐的死锁危机)
写在前面这是本系列的第十六篇。在上一讲中我们发现互斥锁 (mutex) 只能保证代码原子性地执行却无法控制并发线程的先后次序。为了实现Happens-before的顺序关系我们学习了万能的“条件变量”机制。本讲内容我们将学习由计算机科学巨擘 E. W. Dijkstra 发明的另一种共享内存同步神器信号量 (Semaphore)。并在最经典的“哲学家就餐问题”中直面并发编程的死锁梦魇。同步实现 Happens-before同步的核心就是实现“条件达成前等待” $ \rightarrow $ “条件达成后继续”。23:59:59 大活门口不见不散。存在一个确定的状态两人同时到达且都未进行下一步动作。生产 (对象创建) $ \rightarrow $ 消费 (对象释放)。存在一个状态对象已经创建但还未被释放。线程结束 $ \rightarrow $join返回。存在一个状态线程全部结束且后续代码还未开始。条件变量的终极万能模板等待条件满足while (!cond) wait(cv, lk);条件可能满足时唤醒broadcast(cv);互斥锁也能实现 Happens-before (Release - Acquire)其实哪怕不用条件变量单靠互斥锁也能强行造出同步。voidlock(){std::unique_lockstd::mutexlk(mtx);cv.wait(lk,[]{return!lock_held;});lock_heldtrue;}voidunlock(){std::lock_guardstd::mutexlk(mtx);lock_heldfalse;cv.notify_one();// 或 cv.notify_all()}在纯互斥的场景下例如自己写malloc分配器直接用底层的mutex_lock效率更高。信号量 (Semaphore)凭票入场的艺术有没有想过一个奇妙的 Hack 技巧主进程创建一把互斥锁L并立即lock(L)获取它。主进程再次调用lock(L)由于锁已经被占主进程被挂起等待。此时派出一个子进程在子进程里调用unlock(L)主进程瞬间被唤醒lock(L)成功返回继续执行。_(注在 Cstd::mutex中这是一个 Undefined Behavior互斥锁通常要求在同一个线程解铃还须系铃人。但这给我们提供了一种绝妙的*_同步思路)*这种机制的本质Release as Synchronization这种“一个线程上锁另一个线程解锁”的思想实现了完美的Happens-beforeAcquire (获取):等待信号。Release (释放):发出信号。信号量的现实隐喻“资源许可”与“凭票入场”不要把信号量想得很神秘它就是现实生活中的“门票”游泳馆储物柜只有 100 个手环。有手环就能进Acquire没有就排队。出来时交还手环Release。餐厅只有 20 张桌子。有空桌直接进没有就取号等待。停车场只有 50 个车位。有空位抬杆进场没空位在门口死等。用条件变量模拟“停车场” (信号量的推导)在发明信号量之前如果我们用条件变量来写停车场的逻辑voidenter_parking(){mutex_lock(lk);// 进入 parking lot 的判断如果车位满了就睡觉等待while(!(in_parkingcapacity)){cond_wait(cv,lk);}in_parking;// 这个时候我已经拿到车位“进入”了mutex_unlock(lk);}voidleave_parking(){mutex_lock(lk);in_parking--;// 腾出车位cond_broadcast(cv);// 大吼一声有车位了唤醒外面排队的车mutex_unlock(lk);}发现了吗“空位” 和 “占用” 其实是相对的停车 “吃掉”一个车位资源。离开 “创造”一个车位资源。于是Dijkstra 发明了“信号量”如果把上面的代码封装一下把车位数量抽象成count我们就得到了大名鼎鼎的P / V 操作voidP(sem_t*sem){// Prolaag (荷兰语尝试降低) - wait / acquire / downmutex_lock(sem-lk);while(!(sem-count0)){cond_wait(sem-cv,sem-lk);}sem-count--;// 消耗一个信号 (吃掉一个车位/手环)mutex_unlock(sem-lk);}voidV(sem_t*sem){// Verhoog (荷兰语增加) - signal / release / upmutex_lock(sem-lk);sem-count;// 凭空创造一个信号 (还回一个车位/手环)cond_broadcast(sem-cv);mutex_unlock(sem-lk);}极客提示把信号量当互斥锁用如果我们把信号量的初始资源设为1sem_t sem SEM_INIT(1);那么P(sem)就是lockV(sem)就是unlock。因此“信号量本质上是互斥锁的一种数学推广”信号量的实战应用1. 实现一次临时的 Happens-before ($ A \rightarrow B $)线程 1 执行完 $ A $ 后调用V(s)。线程 2 在执行 $ B $ 之前调用P(s)。这样就强行锁死了 $ A $ 必然在 $ B $ 之前执行2. 优雅实现生产者-消费者模型告别复杂的条件变量while循环用信号量写生产者-消费者简直是艺术// 固定大小的缓冲区sem_temptySEM_INIT(depth);// 初始时有 depth 个空位sem_tfillSEM_INIT(0);// 初始时有 0 个数据voidT_produce(){P(empty);// 消耗一个空位袋子如果没有空位就死等printf(();// 生产数据放入V(fill);// 创造一个有数据的袋子叫醒消费者}voidT_consume(){P(fill);// 消耗一个有数据的袋子如果没有数据就死等printf());// 取出数据消费V(empty);// 创造一个空位袋子叫醒生产者}难度暴增哲学家就餐问题 (Dining Philosophers)信号量非常优雅但当多个资源交织在一起时致命的危机就潜伏在代码中。哲学家吃饭问题 (E. W. Dijkstra, 1960)5 个哲学家围坐在一张圆桌旁平时思考饿了就吃饭。桌上只有 5 把叉子。规则吃饭必须同时拿到左手和右手两把叉子。灾难发生死锁 (Deadlock)我们顺理成章地用信号量来实现把每把叉子看作初始值为 1 的信号量。哲学家饿了就依次P左手再P右手。#includethread.h#includethread-sync.h#defineN5sem_tavail[N];// 5把叉子voidTphilosopher(intid){intlhs(idN-1)%N;// 左手叉子编号intrhsid%N;// 右手叉子编号while(1){P(avail[lhs]);// 拿起左手叉子printf( %d by T%d\n,lhs,id);P(avail[rhs]);// 拿起右手叉子printf( %d by T%d\n,rhs,id);// 吃饭 (Eat)printf(- %d by T%d\n,lhs,id);printf(- %d by T%d\n,rhs,id);V(avail[lhs]);// 放下左手V(avail[rhs]);// 放下右手}}运行结果代码卡死了......3by T4 4by T4 -3by T4 -4by T4 2by T3 4by T5 3by T4 1by T2 ^C# 程序彻底挂起无响应被迫强制中断发生了什么想象一个极端的并发情况5 个哲学家同时饿了同时举起了左手的叉子此时桌上 5 把叉子全被拿光了。然后他们每个人都在等待右手的叉子但右手的叉子都在旁边那个人的左手上没有人愿意放下左手的叉子。死锁诞生。破解死锁的 Workaround解法 1从桌子上赶走一个人 (引入门卫)在桌子外加一个容量为 4 的信号量餐厅只发 4 张进场就餐卡。拿到卡的人才能上桌。这样桌上最多只有 4 个人必然有 1 个人能同时拿到左右两把叉子吃完后释放资源打破死锁循环。解法 2Lock Ordering (全局锁排序)给叉子强行编号0 到 4。强行规定所有哲学家必须先拿编号小的叉子再拿编号大的叉子。这样坐在 0 号和 4 号之间的哲学家会去抢 0 号叉子而不是像其他人一样先拿左手。这就破坏了死锁形成的“环形等待”条件信号量 vs 条件变量谁才是王者信号量干净、优雅完美解决了类似于生产者-消费者这种“资源计数型”问题。局限性但如果同步条件变成了“二选一”比如鱼序列_只要匹配任意一边的鱼头鱼尾即可单纯的资源加减就显得极其无力。信号量很难表达复杂的逻辑决策。条件变量万能适用于任何同步条件。配合while(!cond)模板只要你能用 C 语言写出来的条件它都能同步。缺点是代码显得臃肿有循环空转的味道。终极魔法挑战用信号量实现条件变量 (Spicy ️)既然两者都是同步原语能不能用信号量把条件变量给手搓出来来自 2003 年的技术报告Implementing condition variables out of a simple primitive like semaphores is surprisingly tricky.voidwait(cond_t*cv,mutex_t*mutex){atomic_inc(cv-nwait);// 原子增加等待线程计数mutex_unlock(mutex);// ⚠️ 释放互斥锁允许其他线程进入临界区// ⛔ 致命漏洞窗口这里可能会发生线程切换恰好另一个线程执行了 broadcastP(cv-sleep);// 挂起自己mutex_lock(mutex);// 醒来后重新抢锁}voidbroadcast(cond_t*cv){mutex_lock(cv-lock);for(inti0;icv-nwait;i)V(cv-sleep);// 唤醒所有等待的线程cv-nwait0;mutex_unlock(cv-lock);}实现困难的本质原因唤醒丢失 (Lost Wakeup)在wait函数中当你mutex_unlock(mutex)释放锁的一瞬间到你真正执行P(cv-sleep)睡下去之前存在一个极小的时间差。如果此时另一个线程飞速冲进来发现条件满足执行了broadcast连续执行了 $ n $ 次V但此时你还没开始睡等你磨磨蹭蹭执行P的时候之前那个V信号要么被别人抢走要么早已错过。你将面临永久睡眠那怎么办必须在底层将Release(释放锁) 和Wait(进入睡眠) 实现为“不可分割的绝对原子操作”。软件层面根本解决不了这个问题最后必须求助于操作系统内核实际靠的是futex系统调用。总结Take-away messages:信号量可以看作是互斥锁的一个伟大“推广”。我们可以把信号量具象化地理解成游泳馆的手环、停车场的车位、或者袋子里的球。通过计数的方式它极具美感地实现了线程间的先后顺序控制Happens-before。在处理同质化资源共享时信号量能带来极其优雅的代码。但信号量绝不是万能的。在复杂的资源依赖图如哲学家就餐中滥用信号量极易招致死锁在面对复杂的逻辑条件时老老实实回到“条件变量”的模板才是 System 程序员最安稳的归宿。
南京大学 操作系统 (JYY) 学习笔记：并发控制与信号量，哲学家就餐的死锁危机
发布时间：2026/7/31 11:34:24
写在前面这是本系列的第十六篇。在上一讲中我们发现互斥锁 (mutex) 只能保证代码原子性地执行却无法控制并发线程的先后次序。为了实现Happens-before的顺序关系我们学习了万能的“条件变量”机制。本讲内容我们将学习由计算机科学巨擘 E. W. Dijkstra 发明的另一种共享内存同步神器信号量 (Semaphore)。并在最经典的“哲学家就餐问题”中直面并发编程的死锁梦魇。同步实现 Happens-before同步的核心就是实现“条件达成前等待” $ \rightarrow $ “条件达成后继续”。23:59:59 大活门口不见不散。存在一个确定的状态两人同时到达且都未进行下一步动作。生产 (对象创建) $ \rightarrow $ 消费 (对象释放)。存在一个状态对象已经创建但还未被释放。线程结束 $ \rightarrow $join返回。存在一个状态线程全部结束且后续代码还未开始。条件变量的终极万能模板等待条件满足while (!cond) wait(cv, lk);条件可能满足时唤醒broadcast(cv);互斥锁也能实现 Happens-before (Release - Acquire)其实哪怕不用条件变量单靠互斥锁也能强行造出同步。voidlock(){std::unique_lockstd::mutexlk(mtx);cv.wait(lk,[]{return!lock_held;});lock_heldtrue;}voidunlock(){std::lock_guardstd::mutexlk(mtx);lock_heldfalse;cv.notify_one();// 或 cv.notify_all()}在纯互斥的场景下例如自己写malloc分配器直接用底层的mutex_lock效率更高。信号量 (Semaphore)凭票入场的艺术有没有想过一个奇妙的 Hack 技巧主进程创建一把互斥锁L并立即lock(L)获取它。主进程再次调用lock(L)由于锁已经被占主进程被挂起等待。此时派出一个子进程在子进程里调用unlock(L)主进程瞬间被唤醒lock(L)成功返回继续执行。_(注在 Cstd::mutex中这是一个 Undefined Behavior互斥锁通常要求在同一个线程解铃还须系铃人。但这给我们提供了一种绝妙的*_同步思路)*这种机制的本质Release as Synchronization这种“一个线程上锁另一个线程解锁”的思想实现了完美的Happens-beforeAcquire (获取):等待信号。Release (释放):发出信号。信号量的现实隐喻“资源许可”与“凭票入场”不要把信号量想得很神秘它就是现实生活中的“门票”游泳馆储物柜只有 100 个手环。有手环就能进Acquire没有就排队。出来时交还手环Release。餐厅只有 20 张桌子。有空桌直接进没有就取号等待。停车场只有 50 个车位。有空位抬杆进场没空位在门口死等。用条件变量模拟“停车场” (信号量的推导)在发明信号量之前如果我们用条件变量来写停车场的逻辑voidenter_parking(){mutex_lock(lk);// 进入 parking lot 的判断如果车位满了就睡觉等待while(!(in_parkingcapacity)){cond_wait(cv,lk);}in_parking;// 这个时候我已经拿到车位“进入”了mutex_unlock(lk);}voidleave_parking(){mutex_lock(lk);in_parking--;// 腾出车位cond_broadcast(cv);// 大吼一声有车位了唤醒外面排队的车mutex_unlock(lk);}发现了吗“空位” 和 “占用” 其实是相对的停车 “吃掉”一个车位资源。离开 “创造”一个车位资源。于是Dijkstra 发明了“信号量”如果把上面的代码封装一下把车位数量抽象成count我们就得到了大名鼎鼎的P / V 操作voidP(sem_t*sem){// Prolaag (荷兰语尝试降低) - wait / acquire / downmutex_lock(sem-lk);while(!(sem-count0)){cond_wait(sem-cv,sem-lk);}sem-count--;// 消耗一个信号 (吃掉一个车位/手环)mutex_unlock(sem-lk);}voidV(sem_t*sem){// Verhoog (荷兰语增加) - signal / release / upmutex_lock(sem-lk);sem-count;// 凭空创造一个信号 (还回一个车位/手环)cond_broadcast(sem-cv);mutex_unlock(sem-lk);}极客提示把信号量当互斥锁用如果我们把信号量的初始资源设为1sem_t sem SEM_INIT(1);那么P(sem)就是lockV(sem)就是unlock。因此“信号量本质上是互斥锁的一种数学推广”信号量的实战应用1. 实现一次临时的 Happens-before ($ A \rightarrow B $)线程 1 执行完 $ A $ 后调用V(s)。线程 2 在执行 $ B $ 之前调用P(s)。这样就强行锁死了 $ A $ 必然在 $ B $ 之前执行2. 优雅实现生产者-消费者模型告别复杂的条件变量while循环用信号量写生产者-消费者简直是艺术// 固定大小的缓冲区sem_temptySEM_INIT(depth);// 初始时有 depth 个空位sem_tfillSEM_INIT(0);// 初始时有 0 个数据voidT_produce(){P(empty);// 消耗一个空位袋子如果没有空位就死等printf(();// 生产数据放入V(fill);// 创造一个有数据的袋子叫醒消费者}voidT_consume(){P(fill);// 消耗一个有数据的袋子如果没有数据就死等printf());// 取出数据消费V(empty);// 创造一个空位袋子叫醒生产者}难度暴增哲学家就餐问题 (Dining Philosophers)信号量非常优雅但当多个资源交织在一起时致命的危机就潜伏在代码中。哲学家吃饭问题 (E. W. Dijkstra, 1960)5 个哲学家围坐在一张圆桌旁平时思考饿了就吃饭。桌上只有 5 把叉子。规则吃饭必须同时拿到左手和右手两把叉子。灾难发生死锁 (Deadlock)我们顺理成章地用信号量来实现把每把叉子看作初始值为 1 的信号量。哲学家饿了就依次P左手再P右手。#includethread.h#includethread-sync.h#defineN5sem_tavail[N];// 5把叉子voidTphilosopher(intid){intlhs(idN-1)%N;// 左手叉子编号intrhsid%N;// 右手叉子编号while(1){P(avail[lhs]);// 拿起左手叉子printf( %d by T%d\n,lhs,id);P(avail[rhs]);// 拿起右手叉子printf( %d by T%d\n,rhs,id);// 吃饭 (Eat)printf(- %d by T%d\n,lhs,id);printf(- %d by T%d\n,rhs,id);V(avail[lhs]);// 放下左手V(avail[rhs]);// 放下右手}}运行结果代码卡死了......3by T4 4by T4 -3by T4 -4by T4 2by T3 4by T5 3by T4 1by T2 ^C# 程序彻底挂起无响应被迫强制中断发生了什么想象一个极端的并发情况5 个哲学家同时饿了同时举起了左手的叉子此时桌上 5 把叉子全被拿光了。然后他们每个人都在等待右手的叉子但右手的叉子都在旁边那个人的左手上没有人愿意放下左手的叉子。死锁诞生。破解死锁的 Workaround解法 1从桌子上赶走一个人 (引入门卫)在桌子外加一个容量为 4 的信号量餐厅只发 4 张进场就餐卡。拿到卡的人才能上桌。这样桌上最多只有 4 个人必然有 1 个人能同时拿到左右两把叉子吃完后释放资源打破死锁循环。解法 2Lock Ordering (全局锁排序)给叉子强行编号0 到 4。强行规定所有哲学家必须先拿编号小的叉子再拿编号大的叉子。这样坐在 0 号和 4 号之间的哲学家会去抢 0 号叉子而不是像其他人一样先拿左手。这就破坏了死锁形成的“环形等待”条件信号量 vs 条件变量谁才是王者信号量干净、优雅完美解决了类似于生产者-消费者这种“资源计数型”问题。局限性但如果同步条件变成了“二选一”比如鱼序列_只要匹配任意一边的鱼头鱼尾即可单纯的资源加减就显得极其无力。信号量很难表达复杂的逻辑决策。条件变量万能适用于任何同步条件。配合while(!cond)模板只要你能用 C 语言写出来的条件它都能同步。缺点是代码显得臃肿有循环空转的味道。终极魔法挑战用信号量实现条件变量 (Spicy ️)既然两者都是同步原语能不能用信号量把条件变量给手搓出来来自 2003 年的技术报告Implementing condition variables out of a simple primitive like semaphores is surprisingly tricky.voidwait(cond_t*cv,mutex_t*mutex){atomic_inc(cv-nwait);// 原子增加等待线程计数mutex_unlock(mutex);// ⚠️ 释放互斥锁允许其他线程进入临界区// ⛔ 致命漏洞窗口这里可能会发生线程切换恰好另一个线程执行了 broadcastP(cv-sleep);// 挂起自己mutex_lock(mutex);// 醒来后重新抢锁}voidbroadcast(cond_t*cv){mutex_lock(cv-lock);for(inti0;icv-nwait;i)V(cv-sleep);// 唤醒所有等待的线程cv-nwait0;mutex_unlock(cv-lock);}实现困难的本质原因唤醒丢失 (Lost Wakeup)在wait函数中当你mutex_unlock(mutex)释放锁的一瞬间到你真正执行P(cv-sleep)睡下去之前存在一个极小的时间差。如果此时另一个线程飞速冲进来发现条件满足执行了broadcast连续执行了 $ n $ 次V但此时你还没开始睡等你磨磨蹭蹭执行P的时候之前那个V信号要么被别人抢走要么早已错过。你将面临永久睡眠那怎么办必须在底层将Release(释放锁) 和Wait(进入睡眠) 实现为“不可分割的绝对原子操作”。软件层面根本解决不了这个问题最后必须求助于操作系统内核实际靠的是futex系统调用。总结Take-away messages:信号量可以看作是互斥锁的一个伟大“推广”。我们可以把信号量具象化地理解成游泳馆的手环、停车场的车位、或者袋子里的球。通过计数的方式它极具美感地实现了线程间的先后顺序控制Happens-before。在处理同质化资源共享时信号量能带来极其优雅的代码。但信号量绝不是万能的。在复杂的资源依赖图如哲学家就餐中滥用信号量极易招致死锁在面对复杂的逻辑条件时老老实实回到“条件变量”的模板才是 System 程序员最安稳的归宿。
 学习笔记：并发控制与同步的魔法 (Synchronization))
