简介面向操作系统课程实验的银行柜员服务问题完整实验报告聚焦进程间同步与互斥这一核心难点适合计算机专业本科生、考研复习者及需要巩固 P/V 操作与信号量机制的自学者参考。压缩包内仅含 1 个 PDF 文件约 370KB篇幅精炼但结构完整从问题描述与五项实现要求出发给出互斥对象、同步对象及等待队列的抽象分析并附伪码算法、Customer 与 Counter 结构体定义、基于 pthread 互斥锁与信号量的顾客/柜员线程源码剖析最后说明测试数据格式与输出要求。读者可据此理清 Ubuntu 环境下 C/C 多线程建模的完整思路掌握号码唯一、柜员不重复叫号、双向等待等约束的实现与排错方法。目前已有 1874 人学习。1. 银行柜员服务问题为什么两个信号量就能撑起整个同步互斥模型第一次接触进程间同步互斥的人看到银行柜员服务问题直觉上会觉得起码要四五个信号量顾客一个、柜员一个、等待队列一个、输出流一个。可真正把代码写出来会发现同步只用了两个信号量互斥只用了一把锁剩下的全是队列和结构体在干活。这个反差恰恰值得琢磨——信号量的值从来不是“资源还剩几个”这么简单的计数器它在一头数着“有多少人在等”在另一头数着“有多少窗口刚刚空出来”。这两条计数为什么必须反向增长、唤醒动作为什么必须落在锁内、模拟服务的睡眠为什么必须落在锁外把这三件事想通P、V 操作的设计骨架也就摸到了。2. 信号量的语义customers 与 counters 为什么必须反着数2.1 sem_wait 与 sem_post 在内核里究竟做了什么P、V 原语是两个荷兰语词的首字母V 表示释放P 表示申请。落到 Linux 的 POSIX 接口上就是sem_wait和sem_post这一对。它们的实现并不神秘sem_t内部维护一个整型计数和一个等待队列sem_wait原子地把计数减一如果减完小于零调用线程就被挂到该信号量的等待队列上睡眠sem_post把计数加一并检查等待队列若有线程在睡就唤醒其中一个让它重新去尝试减一。关键在于“原子地减一并判断”这一步普通变量做不到。你在用户态写if (count 0) count--;两条线程可能同时通过判断然后同时减结果是计数变成负数、两个线程都进了临界区。信号量的价值就在于把“判断加修改”压成一条不可分割的原语并且顺手把“减不动怎么办”这件事也包办了——睡眠而不是空转。// 用普通变量手工模拟 P 操作这是错误示范 if (count 0) { // 线程 A 和 B 可能同时看到 count 1 count--; // 两个线程都减count 变成 -1 /* 进入临界区 */ // 互斥被破坏 }上面这段代码里检查和修改之间存在窗口期任何抢占都可能导致两个线程同时认为自己拿到了资源。真实的sem_wait内部要么依赖处理器的原子指令要么依赖内核的 futex 机制把一个大概率失败的操作路径压缩到极短。这也是为什么“信号量控制分布在整个程序中、正确性难以保证”这句评价会出现——原语本身是可靠的不可靠的是调用者放它的位置。还有一个容易被忽略的性质互斥锁是有所有者的谁加锁谁解锁跨线程解锁属于未定义行为信号量没有所有者概念A 线程sem_post、B 线程sem_wait是完全合法的。银行柜员问题恰恰吃到了这个红利——柜员线程负责post顾客线程负责wait两条线程通过一个计数器完成交接不需要知道对方是谁。2.2 两条信号量的方向一条数人一条数空闲窗口先把程序里的两条信号量摆出来。customer_sem初值为 0顾客入队后sem_post一次counter_sem初值也为 0柜员叫号后sem_post一次。注意两条都是从零起步方向完全对称但语义并不相同。customer_sem数的是“等待队列里还有多少张没被叫的号”。顾客每post一次就相当于往柜台上放了一张号票柜员每wait一次就取走一张。这是标准的“生产者—消费者”里表示“满”的那条信号量计数为正说明有活儿可干柜员不会白等。counter_sem数的是“有多少次叫号还没有被对应的顾客认领”。柜员叫完号立刻post顾客wait到之后才知道轮到自己了。这条不是资源计数而是事件通知——它传递的不是“有几个窗口空着”而是“刚才有人叫了号你去看看是不是你”。这里有个设计上的取舍值得说清楚。另一种常见写法是把柜员当成资源counters初值设为柜员数 n顾客进来先wait(counters)占一个窗口柜员post(counters)归还。听起来更符合直觉但它有个致命短板顾客占到了窗口却不知道自己被哪个柜员服务。要补齐这个信息还得再加一条通道把柜员编号传过去等于凭空多出一层同步。原方案绕开了这个问题。柜员在出队的同时就把自己的编号写进了Customer结构体的counter_id字段顾客醒来后直接读结构体即可。信号量只负责“通知你去看”不负责“告诉你是谁”信息载体和同步机制被拆成了两件事。这种“用共享数据传值、用信号量传时机”的分工是多线程编程里非常经典的一招理解了它很多看起来复杂的同步场景都能简化。提示只要共享数据是在锁内写入、在信号量post之后才被对端读取读取方就不需要再加锁去读那个字段。信号量的post/wait本身建立了先后关系写在前、读在后内存可见性由原语保证。2.3 互斥锁保护数据结构信号量协调执行顺序这两者的边界必须划清楚否则很容易写成“用锁去等、用信号量去护”的四不像。互斥锁管的是数据完整性。等待队列queueCustomer*是个链表push和pop都会改指针两条线程同时动它必然崩。输出流也是同理cout的多次之间如果被另一条线程插进来一行日志就会被劈成两半。所有这类“读了会坏、写了会坏”的地方都要套锁。信号量管的是推进节奏。柜员不能在没有顾客的时候叫号顾客不能在没有柜员空闲的时候接受服务这两条约束描述的是“事件发生的先后”不是“数据被谁改”。用锁去实现这种等待只能靠轮询检查条件变量CPU 空转而且很容易写出优先级反转。原文把这两件事分得很干净customer_waiting、customer_list、counter_list以及所有cout统统在mutex里顾客与柜员之间的“我来了”“我空了”统统走信号量。混用的后果下一章会具体看到同一把锁既当互斥又当同步稍不注意就会在持锁状态下睡眠把整个系统串行化。3. 顾客线程与柜员线程一次叫号握手里藏着几次上下文切换3.1 顾客线程睡眠模拟到达入队后立刻交出控制权顾客线程的职责非常线性睡到自己的到达时刻进队列通知柜员然后原地等叫号被服务完就退出。整条路径上没有循环也没有重试写完就结束。// 顾客线程从到达到离开全程只有一次等待 void *customer_thread(void *arg) { Customer customer *(Customer *)arg; // 用 sleep 模拟顾客在 arrive_time 时刻到达银行 sleep(customer.arrive_time); // 取号入队 通知柜员这两步必须原子完成 pthread_mutex_lock(mutex); cout [CUSTOMER] id customer.id arrive at time(NULL) - program_start_time endl; customer_waiting.push(customer); // 存入的是指针指向 vector 中的元素 sem_post(customer_sem); // 队列长度 1唤醒一个柜员 pthread_mutex_unlock(mutex); // 等叫号阻塞在这里直到某个柜员 post(counter_sem) sem_wait(counter_sem); // 此时 counter_id 和 service_start 已被柜员写好直接读 pthread_mutex_lock(mutex); cout [CUSTOMER] id customer.id served by customer.counter_id at customer.service_start endl; pthread_mutex_unlock(mutex); // 模拟接受服务所耗的时间 sleep(customer.service_duration); return NULL; }入队和sem_post被放在同一个临界区里这个细节不能省。假如先解锁再post中间那一瞬间柜员可能已经wait到了旧的计数、去队列里front()而此时顾客的元素还没挂上链表取到的就是空队列或者上一个顾客——一次典型的“信号量抢跑”。把两步绑在锁内保证柜员被唤醒时队列里一定已经有货。第二处pthread_mutex_lock只包住了输出语句。有人会问读counter_id要不要加锁答案是不需要因为柜员是在sem_post(counter_sem)之前、持锁状态下写这两个字段的顾客sem_wait返回时写入早已完成同步原语已经保证了顺序。加锁只是为了不让自己的cout和别人的cout交错。3.2 柜员线程while(true) 里的一次完整服务周期柜员线程和顾客线程最大的区别是它不退出。只要还有顾客没服务完它就要一直转所以主体是个死循环靠外部的取消信号终止。// 柜员线程循环取号、服务直到被主线程取消 void *counter_thread(void *arg) { Counter counter *(Counter *)arg; while (true) { // 没有顾客就睡在这里不消耗 CPU sem_wait(customer_sem); // 进入工作状态后禁止取消避免服务到一半被强杀 pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, NULL); // 叫号出队 记录服务信息 通知顾客一个临界区做完 pthread_mutex_lock(mutex); Customer customer *customer_waiting.front(); customer.counter_id counter.id; // 传值 customer.service_start time(NULL) - program_start_time; cout [COUNTER] id counter.id serve customer customer.id endl; customer_waiting.pop(); sem_post(counter_sem); // 传时机 pthread_mutex_unlock(mutex); // 模拟服务过程注意这一步必须在锁外 sleep(customer.service_duration); pthread_mutex_lock(mutex); cout [COUNTER] id counter.id finish customer customer.id endl; pthread_mutex_unlock(mutex); // 服务结束恢复可取消状态并检查一次取消请求 pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, NULL); pthread_testcancel(); } }front()和pop()必须在同一个临界区内完成这是整段代码里最容易写错的地方。如果先解锁、再pop另一个柜员可能在这中间也执行了front()两个柜员叫到同一个号——恰好违反题目里“不能有多于一个柜员叫同一个号”的要求。这类 bug 在低并发下几乎测不出来一旦柜员数上去就原形毕露。3.3 锁内锁外的边界post 在锁内sleep 在锁外现在可以回答第 1 章留下的问题了。sem_post(counter_sem)放在锁内是为了让“写counter_id”和“通知顾客”成为一个不可分割的动作。若先解锁再post顾客被唤醒后去读counter_id时理论上可能读到还没写完的值虽然实际执行顺序大概率没事但语言层面没有保证。把它压在锁内写和通知之间就没有任何缝隙顾客醒来看到的一定是完整数据。sleep(service_duration)放在锁外理由更直白锁是全局唯一的一把谁持有它谁就独占整个数据结构。柜员模拟服务要睡好几秒如果抱着锁睡其他柜员既不能叫号、顾客也不能入队、连日志都打不出来整个程序退化成单线程串行。更糟的是顾客线程醒来后第一件事也是抢这把锁双方便僵在原地互相等形成一种“持锁睡眠导致的伪死锁”。这条边界可以总结成一句经验临界区里只做内存操作任何可能阻塞的调用——sleep、文件 I/O、网络请求、甚至长时间的字符串拼接——都要挪到锁外面去。至于sem_wait它本身就会阻塞更不能放在锁里否则就是经典的“拿着锁去等信号”柜员永远等不到下一个顾客因为顾客连入队都进不来。把 7 个顾客、2 个柜员的测试样例跑一遍可以对照出时序。输入是到达时刻和服务时长两个维度比如 1 号顾客 1 时刻到、要 11 秒2 号顾客 1 时刻到、要 4 秒3 号顾客 1 时刻到、要 7 秒。时刻事件等待队列customer_semcounter_sem1顾客 1、2、3 同时到达并入队[1,2,3]301柜员 1 取 1 号柜员 2 取 2 号[3]12→15柜员 2 服务完 2 号取 3 号[]01→08柜员 2 服务完 3 号队列空睡眠[]0012柜员 1 服务完 1 号两柜员均空闲[]00表里counter_sem那一列会出现“2”这种值意思是两个柜员几乎同时叫了号、两次通知叠在一起顾客会依次wait掉。这正是信号量作为计数器而非条件变量的好处——通知不会丢失早到的通知会被记账晚到的顾客照样能取到属于自己的那一张。4. 线程取消与收尾柜员线程凭什么能被安全终止4.1 pthread_cancel 的默认行为与取消点柜员线程是死循环不能靠返回值自然结束只能由主线程在“所有顾客都服务完”之后发取消请求。pthread_cancel的语义常被误解成“立刻杀死线程”实际它只是设置一个挂起标志线程运行到下一个取消点时才会真正退出。取消点包括sleep、read、write、sem_wait、pthread_testcancel这类可能阻塞的调用。这个延迟退出机制在银行场景里救了命。设想柜员正在服务中途——已经出队、已经写好counter_id、正sleep模拟服务——此时若被强杀这位顾客的线程会永远卡在sem_wait(counter_sem)上因为再没人会替他post。程序不会崩而是安静地挂住这种“看起来在跑其实已经死了”的故障最难排查。所以柜员线程在取到号之后、开始服务之前先把自己的取消状态设为禁用服务完、日志打完再恢复成允许并主动调用一次pthread_testcancel。这一对开关把“工作区间”保护了起来取消只能发生在循环开头等待下一个顾客的间隙。注意pthread_setcancelstate的作用范围是当前线程不需要加锁但一定要成对出现。中间若有return或break提前跳出记得补上恢复语句否则线程带着禁用状态进入下一轮之后再也不会响应取消。4.2 主线程的收尾顺序先等顾客再取消柜员主线程的逻辑是按依赖关系倒着写的先读文件建结构体再创建全部线程然后等所有顾客线程结束最后取消柜员线程并做资源回收。等顾客用pthread_join因为顾客线程有明确终点join会阻塞到它return为止。柜员不能用join——它永远不返回join会把自己也挂死。这是两类线程收尾方式不同的根本原因不是风格选择。回收顺序同样有讲究必须先join完所有顾客再发取消再join柜员确认真的退出了最后才sem_destroy和pthread_mutex_destroy。如果提前销毁信号量那些还阻塞在sem_wait上的柜员线程会操作一块已经失效的内存行为未定义如果销毁了锁但还有线程在排队同样会踩到已释放的内存。销毁类接口的调用时机本质上就是在赌“确认没有别人还持有或等待它”。// 主线程收尾的关键顺序不能调换 for (auto c : customer_list) pthread_join(c.pID, NULL); // 1. 等顾客走完 for (auto c : counter_list) pthread_cancel(c.pID); // 2. 通知柜员退出 for (auto c : counter_list) pthread_join(c.pID, NULL); // 3. 确认真的退出了 pthread_mutex_destroy(mutex); // 4. 销毁锁 sem_destroy(customer_sem); // 5. 销毁信号量 sem_destroy(counter_sem);第 3 步的join经常被省略理由是“都cancel了还等什么”。可cancel只是请求线程可能还卡在sleep里没醒。不等它就直接destroy等于是把地基抽了还留着人在上面走。4.3 结构体与容器的内存布局指针存进队列的隐患程序里customer_list是vectorCustomer存的是对象本体等待队列是queueCustomer*存的是指向 vector 元素的指针。这个组合有一个隐蔽前提vector 在全部push_back完成后不能再扩容。vector扩容时会重新申请一块更大的内存、把旧元素搬过去、释放旧内存。原来那些指针指向的地址就全部悬空了队列里的元素变成了野指针运行时表现为段错误或读到一堆垃圾数据。原程序在初始化阶段一次性读完输入、建完所有顾客之后不再push_back所以侥幸安全。但如果改成“顾客线程运行中动态加入新顾客”这个隐患立刻变成真 bug。常见的做法有两种一是在读完输入后立刻reserve一个足够大的容量明确表达“不打算再扩”二是干脆把队列改成queueint存下标或者用deque这种插入不失效的容器。第一种简单第二种更稳。我在写这类“对象池 指针队列”的结构时习惯在池子建完的那一刻加一行注释写明“此后不再扩容”免得下次改需求时忘了这个约定。还有一处值得提的细节Customer结构体里的线程 id 字段初始化为 0创建线程时再回填。这意味着customer_list里的元素在线程启动前是“半成品”如果此时有别的线程去遍历这个 vector读到的就是无效 id。所有对结构体的写入都应该在线程启动前完成或者在锁内进行——初始化阶段的单线程执行天然满足这个条件但把它写进注释里会更保险。5. 排查清单这类同步程序最容易翻车的五个地方5.1 两个顾客拿到同一个柜员号现象输出文件里两条记录的服务柜员号相同、开始服务时刻也相同等待队列里少了一个人。原因几乎总是front()和pop()之间出现了空隙——先取队首、解锁、再出队另一个柜员挤进来取了同一个队首。解决办法是把判断、取用、出队三步压进同一个临界区中间不释放锁。这类 bug 在 2 个柜员时可能几十次才复现一次把柜员数调到 8 个、顾客调到 50 个几乎必现。5.2 柜员线程在 sem_wait 处被取消顾客永久挂起现象程序不退出也不报错进程 CPU 占用接近零像睡着了一样。原因是主线程发出取消请求时某个柜员正阻塞在sem_wait(customer_sem)上而sem_wait本身是取消点线程当场退出可它已经取走的那张号票对应的顾客没人管了。解决思路是调整禁用取消的位置不要等wait返回后才禁用而是在进入循环前就禁用、wait成功后再考虑恢复或者给sem_wait挂一个取消清理函数在退出时把票还回去。5.3 日志行被劈成两半现象终端上出现[COUNTER] id 1 serve cus[CUSTOMER] id 3 arrive这样的拼接。原因是cout a b c在底层是多次独立的函数调用不是一次原子写两条线程的输出可以任意穿插。解决方式是先把整行拼成一个std::string在一次里输出或者干脆所有输出都放进互斥锁内。前者粒度更细后者更省事看你对日志实时性的要求。5.4 总耗时远大于理论值现象两个柜员、七个顾客理论十几秒跑完实际跑了三十多秒。检查服务时长和总时间的关系若呈现明显的串行特征多半是sleep被写进了临界区。持锁睡眠会让所有线程排队等着锁等于把多线程退化成单线程。排查方法很简单在加锁和解锁之间打时间戳若某段临界区耗时接近服务时长就是它了。5.5 信号量初值写错导致启动即卡死现象程序刚起来就再也不动一个日志都没有。原因可能是把customer_sem的初值设成了柜员数而不是 0。柜员一启动就wait成功、去队列里front()而队列此时是空的front()对空容器是未定义行为可能直接崩也可能取到垃圾指针后卡在别处。还有一种是counter_sem初值设成大于 0顾客还没入队就以为自己被叫到了直接跳过等待去读counter_id读到的是初始值 0。信号量的初值必须严格对应“初始时刻系统里有几张票”这个数字要靠推演而不是猜。6. 从信号量到管程什么时候该换掉 P、V把银行柜员问题写通之后回头看那串“实现互斥的方法”的比较会有完全不同的体感。禁止中断、轮转法、Peterson 算法、硬件指令这些方案在单核时代是主流共同点是忙等待——进程在等的时候仍在烧 CPU且轮转法还要求进程严格交替进入一旦有人中途退出就全乱。信号量把等待变成了睡眠是效率上的一次跃迁代价是把同步逻辑散落到调用者的代码里post少写一个就死锁多写一个就破坏互斥而且这些错误在编译期完全看不出来。这正是管程被发明出来的动机。管程把“共享数据 操作这些数据的过程 一把隐式锁”打包成一个语言层面的单元进入管程自动加锁、离开自动解锁程序员不再需要手写lock/unlock的配对也就不存在“忘了解锁”这种错误。Java 的synchronized、C 的条件变量加互斥锁封装本质上都是管程思想的不同形态。它的效率与信号量同级可读性和可维护性却高一个档次。那是不是就该彻底抛弃 P、V也不必。管程需要语言或库的支持在纯 C 加 pthread 的环境里你能用的还是互斥锁加条件变量这一套而条件变量本身就是信号量的近亲。更实际的选择标准是看同步关系的形状如果关系是“一方通知另一方某件事发生了”一条信号量就够了简单直接如果关系是“多个操作必须基于同一个不变量整体成立”比如队列非空且元素有效、账户余额与流水一致那就该用锁把整段操作圈起来信号量反而会把不变量撕成两半。验证这类程序我一般会做三件事。第一件是不变量检查在每次出队后断言队列长度不小于零、每个顾客的counter_id只被赋值一次、服务开始时刻不早于到达时刻。第二件是压力测试把柜员数从 1 调到 16、顾客数从 10 调到 500跑上一百轮看有没有偶发的重复服务或超时。第三件是时序核对拿输出的 (到达, 开始服务, 离开) 三元组和手工推演的甘特图对比重点看“同时到达”的边界情况那里最容易暴露竞争。这三件事都不难写难的是每次都写。我头一回写这个题时把sleep留在了锁里跑出来三十多秒还以为是机器慢盯着top看了半天才发现只有一个核在动。从那以后我每次写多线程都强制在临界区首尾各打一个时间戳跑完先扫一遍最长的那段临界区有多久超过一毫秒就逐个检查里面有没有阻塞调用。这个习惯后来帮我抓到过不少隐藏的串行化问题比事后对着日志猜要省力得多。希望帮到你。本文还有配套的精品资源点击获取
