银行柜员并发问题：互斥锁与信号量实战解析

简介一份面向操作系统课程学习者的进程同步互斥实验报告以银行柜员服务问题为场景完整展示基于PV操作和信号量机制解决多线程同步与互斥问题的思路。内容涵盖实验题目、设计伪码、顾客与柜员线程实现、数据结构及测试输出要求适合正在学习进程管理、准备课程实验或复习操作系统的本科生参考。压缩包内为1个PDF文件大小370KB集中呈现报告正文阅读轻量、便于对照练习。该资源目前已吸引1872人浏览学习适合作为理解经典同步问题的补充材料。通过这份报告读者可以掌握互斥锁、信号量在等待队列管理中的具体用法看懂从问题建模、线程划分到输出验证的完整流程并迁移到其他并发编程场景中。1. 为什么银行柜员问题值得亲手实现一遍取号机跳号背后的并发真相某开发者给某银行网点写叫号程序3个窗口同时服务结果第一天就翻了车两个柜员几乎同时按下叫号键系统把同一个号码叫给了两个窗口两位客户差点走到同一个窗口前。更离谱的是午高峰取号机上一下子跳了三个号。这类问题并不是“多线程写得不对”而是多个执行流同时读写共享号码、共享队列时读写顺序完全不可控。标题里的银行柜员服务问题正是操作系统课程中经典的进程线程间同步互斥案例本质上是生产者—消费者模型的业务化表达客户不断“生产”取号需求柜员不断“消费”叫号任务中间那台取号机和那条等待队列就是要用锁和信号量保护起来的临界资源。读完下面的实践你能拿到一份可编译的多柜员服务程序知道每个参数为什么这么设并避开并发实现里最容易翻车的五个坑。2. 柜员模型拆解临界资源、两类同步关系与机制选型2.1 临界资源与竞态条件取号机、等待队列凭什么必须加锁先定义问题。银行柜员服务场景里有三个共享对象取号机上的当前号码 ticket、等待队列 queue、队列头尾指针 head 和 tail。多个客户线程同时执行 ticket 时CPU 实际会拆成 load、add、store 三步线程 A 读到 10线程 B 也读到 10各自加 1 再存回去结果两个客户拿到的都是 10。这跟你现实中两台机器同时按取号键却只出一个号是同一回事。同样的客户入队和柜员出队如果交错执行head 和 tail 就可能被写乱出现队列覆盖或空读。所以这些对象是临界资源所有访问路径必须互斥。同步需求则来自数量关系队列空时柜员必须等待客户队列满时客户必须等待空位多个窗口同时服务时还要保证叫号不重。互斥解决“同一时刻只能一个人动共享数据”同步解决“什么时候可以动”。需要特别说明的是这里说的“进程间同步互斥”在实际练习里通常先用线程实现因为同一套互斥锁、信号量原语在线程和进程之间逻辑完全一致先在线程上把并发问题看清楚再迁移到进程版会轻松得多。线程模型下共享的是进程地址空间里的全局变量进程模型下共享的是映射到各进程地址空间的共享内存。两者的临界区保护思路是一样的。2.2 互斥锁、信号量、条件变量各自卡在哪个环节常见做法是用三种原语组合各自管不同的事。互斥锁管临界区互斥对应取号机号码、队列指针的并发访问信号量管资源数量对应队列空位、排队客户数、空闲窗口数条件变量管事件通知对应柜员在没客户时休息、来客户时被唤醒。一个直觉化的比喻互斥锁是门卫信号量是计数器条件变量是广播喇叭。原语管什么银行场景对应典型误用互斥锁 mutex临界区互斥取号机号码、队列头尾指针的并发访问把整个服务过程也锁住导致多窗口退化成单窗口信号量 semaphore资源数量管理队列空位/排队客户数、空闲窗口数初值设错导致死锁或放行过多线程条件变量 cond事件通知柜员等待客户到来时被唤醒用 if 判断条件虚假唤醒后重复叫号为什么银行柜员问题的基础版通常只需要互斥锁加信号量就能跑通因为队列的“满”和“空”是典型的计数问题信号量的 P/V 操作天然对应“申请一个空位”和“释放一个空位”。互斥锁保护的是取号和入队这个短暂操作。条件变量要等引入“客户等自己的号被叫到”这一层通知逻辑时才需要属于进阶扩展。还有一点值得提很多初学者喜欢用“全局标志位 sleep”来模拟同步这是最危险的做法。标志位的读写本身不具备原子性sleep 只是把竞态出现的时间推迟了并没有消除竞态。同步互斥问题必须用操作系统提供的原语而不是靠业务代码里的延时来“碰运气”。2.3 最小可运行骨架先跑通再谈完整不急着上完整代码先理解执行顺序。我一般会先画一遍流程再动手写。客户线程生产者的执行顺序是先 P(empty)也就是队列有空位才继续否则阻塞然后加锁取号 ticket把号码写入队尾解锁最后 V(full)告诉柜员“有客户排队了”。柜员线程消费者的顺序是先 P(full)有客户才继续否则阻塞等待然后加锁从队头取出一个号码解锁接着 V(empty)腾出一个排队空位最后打印服务信息模拟业务耗时。这段骨架的核心是empty 和 full 两个信号量完成有界缓冲区的容量控制mutex 保证号码和队列的操作原子。把上面的 P/V 换成代码就是下一章的完整程序。信号量语义有个检查方法谁做 P谁做 V初值是多少必须能对上。empty 的初值是队列容量 MAX_QUEUE客户入队时 P(empty)柜员出队后 V(empty)full 的初值是 0客户入队后 V(full)柜员服务前 P(full)。两个信号量任何时刻的值加起来恒等于 MAX_QUEUE。这个守恒关系如果被破坏说明某处多了一次 P 或少了一次 V死锁基本就在那附近。3. 用互斥锁信号量实现可运行的柜员服务程序3.1 完整代码3个柜员窗口 最多排队10人这一份代码是我调试过的常见写法用 pthread 搭配两个信号量实现 3 个柜员窗口、最多 10 人排队、20 位客户依次取号的小型模拟程序。重点看信号量与锁的配合顺序。#include stdio.h #include stdlib.h #include unistd.h #include time.h #include pthread.h #include semaphore.h #define WINDOWS 3 /* 柜员窗口数 */ #define MAX_QUEUE 10 /* 最多排队人数 */ #define CUSTOMER_NUM 20 /* 模拟客户总数 */ pthread_mutex_t lock PTHREAD_MUTEX_INITIALIZER; sem_t empty; /* 队列空位数初值 MAX_QUEUE */ sem_t full; /* 队列内客户数初值 0 */ int ticket 1; /* 取号机当前号码 */ int queue[MAX_QUEUE]; /* 等待队列环形数组 */ int head 0, tail 0; void enqueue(int v) { queue[tail] v; tail (tail 1) % MAX_QUEUE; } int dequeue(void) { int v queue[head]; head (head 1) % MAX_QUEUE; return v; } void *customer_entry(void *arg) { long id (long)arg 1; sem_wait(empty); /* 队列满时等待空位 */ pthread_mutex_lock(lock); /* 取号机是临界区必须加锁 */ int my_ticket ticket; enqueue(my_ticket); pthread_mutex_unlock(lock); sem_post(full); /* 通知柜员有新客户可服务 */ printf(客户 %2ld 取号 %d进入等待队列\n, id, my_ticket); return NULL; } void *clerk_entry(void *arg) { long id (long)arg 1; while (1) { sem_wait(full); /* 队列空时休眠等待 */ pthread_mutex_lock(lock); /* 出队同样需要互斥 */ int cur dequeue(); pthread_mutex_unlock(lock); sem_post(empty); /* 腾出一个排队空位 */ printf(柜员 %ld 叫号 %d客户开始办理业务\n, id, cur); usleep(80000 rand() % 120000); /* 模拟业务处理耗时 */ } return NULL; } int main(void) { pthread_t clerks[WINDOWS], customers[CUSTOMER_NUM]; long i; srand((unsigned)time(NULL)); sem_init(empty, 0, MAX_QUEUE); sem_init(full, 0, 0); for (i 0; i WINDOWS; i) pthread_create(clerks[i], NULL, clerk_entry, (void *)(i 1)); for (i 0; i CUSTOMER_NUM; i) { pthread_create(customers[i], NULL, customer_entry, (void *)(i 1)); usleep(30000); /* 模拟客户到达间隔 */ } for (i 0; i CUSTOMER_NUM; i) pthread_join(customers[i], NULL); sleep(1); /* 留时间让最后几个服务日志打印完 */ printf(全部客户完成取号程序结束\n); return 0; }编译命令gcc -o bank bank.c -lpthread -Wall代码里的顺序是有讲究的。客户线程必须先 sem_wait(empty) 再加锁如果反过来先加锁再等空位队列满时客户会持锁阻塞柜员线程无法出队释放空位程序直接死锁。柜员线程同理先 sem_wait(full) 再加锁保证没有客户时不会占着锁不放。这是一个很容易被忽略的锁顺序问题。3.2 代码拆解与三个必调参数先看两个信号量的分工。empty 初值等于 MAX_QUEUE表示队列空位数full 初值等于 0表示当前排队人数。客户入队消耗一个空位、增加一个排队数柜员出队增加一个空位、消耗一个排队数。两个信号量值之和守恒这是排查死锁的第一抓手。再看不变量。mutex 只包围了 ticket、enqueue、dequeue 这几条内存操作usleep 业务耗时在锁外。这是刻意为之锁的粒度越小并发度越高。如果把 usleep 放进临界区3 个柜员线程会被同一把锁串行化吞吐量直接掉回单窗口水平。三个必调参数如下。WINDOWS 是柜员窗口数也是消费者线程数决定同时服务几个客户MAX_QUEUE 是等待队列容量决定排队上限usleep 的两个时间值决定业务耗时分布和客户到达间隔。教学验证时我习惯用 WINDOWS3、MAX_QUEUE10、客户到达间隔 30ms、服务耗时 80~200ms日志节奏刚好能看清。压测时则把所有延时调成 0让竞态尽可能暴露。参数含义调大影响调小影响WINDOWS柜员线程数并发服务能力增强但线程切换开销上升窗口过少队列积压明显MAX_QUEUE等待队列上限容纳更多排队客户积压时延变大队列容易满客户到达被阻塞usleep 耗时模拟业务/到达节奏更接近真实业务竞态容易被掩盖竞态暴露更充分适合压测三个参数相互牵制在业务耗时不变的前提下窗口数越多、到达间隔越短队列越容易积压。合理经验是把 MAX_QUEUE 设成“窗口数 × 平均服务耗时 ÷ 平均到达间隔”再乘 1.5~2 的应急系数。比如窗口 3、平均服务 150ms、到达间隔 100ms乘积是 4.5取 8~10。这样高峰时客户能排队但不至于无限堆积。3.3 线程版跑通之后进程版要怎么改标题里写的是进程间同步互斥但上面这份代码是线程版。常见做法是先在线程上验证同步逻辑再迁移到进程版。迁移有五处明显改动把 ticket、queue、head、tail 放进共享内存信号量改用具名信号量 sem_open 或 System V 信号量互斥锁设置进程共享属性线程创建改成 fork日志打印加上进程号和时间戳。共享内存里放一个结构体是常见做法第一个成员放锁struct Shared { pthread_mutex_t lock; int ticket; int queue[MAX_QUEUE]; int head; int tail; }; pthread_mutexattr_t attr; pthread_mutexattr_init(attr); pthread_mutexattr_setpshared(attr, PTHREAD_PROCESS_SHARED); pthread_mutex_init(shared-lock, attr);用 mmap 分配共享内存后 fork子进程访问同一个 shared 指针。注意锁必须在共享内存里初始化不能在某一个进程的栈上初始化后再让其他进程用否则锁的状态只在当前进程地址空间内有效其他进程拿到的锁是非法的。4. 银行柜员并发实现避坑5条血泪经验4.1 用sleep模拟业务耗时掩盖了真正的竞态现象程序跑起来一切正常反复跑十几次也抓不到错一上真实业务就偶发号码重复。原因usleep 或 sleep 放错了位置。最常见的是把业务耗时写进了临界区让两次取号操作之间天然隔开ticket 背后的 load-add-store 竞态被“延时”掩盖了。同步互斥问题最怕这种假象程序不是没问题只是问题还没露头。解决把所有延时调到 0到达间隔为 0、服务耗时为 0让大量线程背靠背抢同一把锁。如果在极限情况下出现重复号码说明锁的位置或粒度有问题。我每次改完并发代码都会先做三轮这种极限测试再跑正常参数下的日志。提示判断竞态是否被掩盖的方法很简单——把延时全部置 0 再跑能复现问题就说明锁没锁对地方而不是业务代码的问题。4.2 信号量初始化顺序不对程序直接死锁现象程序一启动就卡住柜员线程全部睡死没有任何打印输出。原因empty 初值被设成 0客户线程全部阻塞在 sem_wait(empty)柜员线程等 full而 full 不会有新值因为没有客户能入队。两个信号量互相等形成死锁。另外还有一种情况使用已存在的信号量时没有重新初始化残留了上一次运行的值。解决用守恒关系检查初值。empty full 必须恒等于 MAX_QUEUE初值分别是 MAX_QUEUE 和 0。换到进程版时如果信号量是持久化的运行前要显式设置初值不能假设它一定是干净的。4.3 锁粒度过大多窗口退化成单窗口现象3 个柜员窗口吞吐量却和 1 个柜员一样慢运行时间几乎没缩短。原因把 usleep 业务耗时放进了 pthread_mutex_lock 和 unlock 之间。锁被正在办理业务的客户线程占着其他客户线程和柜员线程全部排队等锁所谓 3 个窗口实际上变成了一扇门进出。解决临界区只保护 ticket、enqueue、dequeue 这几条语句。业务耗时、打印、文件写入、网络请求一律放到解锁之后。验证方法统计同等客户数下的总耗时如果增加窗口数后总耗时几乎不变锁粒度八成有问题。4.4 在临界区里调用阻塞函数后续任务全部卡住现象程序运行中突然所有线程全部停住没有崩溃信息过一阵又恢复或者永久卡死。原因在临界区内调用了 sem_wait、条件变量等待、文件读取这类阻塞操作。这意味着线程持锁等待某个事件而该事件的产生可能需要进入同一把锁于是形成“持锁等待”的死锁闭环。比 4.3 更隐蔽的是它不一定每次复现。解决临死区里只做内存级的普通赋值不调用任何可能阻塞的系统调用。如果必须在等待时释放锁就用条件变量配合 pthread_cond_wait它会在等待时自动释放互斥锁。4.5 条件变量判断条件用if虚假唤醒后客户被重复叫号现象加了条件变量扩展“客户等叫号”逻辑后两个柜员同时叫到同一个客户或者一个客户被唤醒后条件已经不满足仍然继续执行。原因pthread_cond_wait 可能被虚假唤醒也就是没有对应事件发生也会返回。返回后必须重新检查条件是否满足if 只检查一次做不到这一点。解决用 while 循环包裹等待这是 POSIX 线程编程的标准写法while (queue_count 0) pthread_cond_wait(cond, lock);5. 窗口数、队列上限、客户到达速率把柜员服务从能跑到能上线5.1 三个参数的三角关系窗口数不是越大越好。窗口数决定同时服务多少个客户但每个柜员线程都要占用一个 CPU 执行上下文线程太多时切换开销会抵消并发收益。队列上限决定缓冲能力太小客户到达时没有空位取号直接被阻塞太大高峰积压时客户等待时间飙升体感很差。客户到达速率则取决于业务真实节奏模拟时用客户线程的创建间隔来控制。常见做法是用“服务时间 / 到达间隔”估算稳态排队长度再留出余量。教学场景下我一般直接用 WINDOWS3、MAX_QUEUE10 这种便于观察日志的组合。高并发场景下窗口数先按 CPU 核数或核数 ×2 起步再通过压测调整。注意一个容易被忽略的点队列用 FIFO 顺序出队可以保证先到的客户先被叫号如果改成 LIFO 或者按优先级出队低优先级客户可能一直等不到服务这就是饥饿问题。5.2 用平均等待时延和吞吐量验证并发效果参数调完怎么知道有没有变好我一般记录两个指标平均等待时延即客户取号到柜员叫号之间的时间差吞吐量即单位时间内完成服务的客户数。做法是在代码里加两个时间数组取号时记录 t1叫号时记录 t2结束时统一计算。跑测试时有个原则每组参数跑三次取中位数不要看单次结果。先固定 WINDOWS把 MAX_QUEUE 从 5 调到 20观察吞吐量的拐点再固定队列调窗口数。如果窗口数翻倍而吞吐量没有明显上升说明瓶颈不在窗口数而在锁竞争或 CPU 核心数。5.3 真实系统里更常见的做法线程池 任务队列裸 pthread 加信号量适合理解原理真实服务里我一般不会手写这种结构而是用线程池加任务队列。线程池负责管理固定数量的工作线程任务队列用条件变量实现“有任务就唤醒没任务就休眠”上层只需要提交任务。取号机场景中ticket 这种单变量计数可以直接用原子操作替代互斥锁比如 GCC 的 __sync_fetch_and_add 或 C11 的 atomic_fetch_add进一步减少锁竞争。但原子操作有边界它只适合单个计数变量。队列的 head、tail 还是需要锁或专门的无锁队列实现。信号量在需要“资源数量上限”时仍然合适但涉及超时、取消任务、优先级调度时条件变量配合超时参数 pthread_cond_timedwait 更灵活。真实系统中还会引入队列长度告警、超时直接返回“业务繁忙”而不是让客户无限阻塞等待。6. 验证并发正确性的一个实用习惯日志序号连续性检查最后分享一个我每次写完并发代码都会做的验证——不只看“能不能跑”而是看日志里的号码序列是否连续完整。这个习惯能快速暴露三类问题重复取号说明锁失效叫号重复说明条件变量或出队逻辑有误号码缺失说明入队失败或队列覆盖。做法分三步。第一步在客户取号处打印取到的号码在柜员叫号处打印叫出的号码。第二步跑完一轮后用脚本提取所有取号记录和所有叫号记录分别检查号码序列。第三步把两份记录做对比确认每个号码都被叫到且没有号码被叫两次。检查脚本的核心逻辑很简单。用下面的命令检查取号序列是否完整grep 取号 bank.log | awk {print $4} | sort -n taken.txt seq 1 20 expect.txt diff expect.txt taken.txt echo 取号序列完整再检查叫号是否有重复grep 叫号 bank.log | awk {print $4} | sort -n | uniq -c | awk $1 ! 1注意awk 的字段序号取决于你的打印格式我这里把号码放在第四个字段如果你的日志里位置不同改成对应的列就行。我习惯把号码固定在固定列这样日志解析脚本写一次就能长期复用。我自己的习惯是并发代码写完后先做三轮极限测试也就是到达间隔为 0、服务耗时为 0把竞态逼出来再跑一轮正常参数日志最后用序号连续性检查收尾。这套流程帮我避开了不少看似玄学的偶发问题——它们其实大多不是玄学只是竞态还没被抓住。希望帮到你。本文还有配套的精品资源点击获取