3
经典并发问题: 大型理发店
source link: https://colobu.com/2022/03/06/hilzers-barbershop-problem/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
经典并发问题: 大型理发店
二月二理发店太火了，家家都爆满，这次我们来到Hilzer的理发店，这是一家比较大的理发店。
这家理发店有三位有经验的理发师，每个理发师都有自己独立的理发椅。等待区有一个四座的沙发，等待区还有站一些人等待。还有一个收银台。
- 依照新冠疫情防控的要求，最多允许20个顾客进入。
- 如果有顾客，理发师优先从沙发上叫起等待最久的顾客开始理发；如果没有顾客，理发师则在自己的理发椅上睡觉
- 顾客来到后
- 如果已经有20个顾客，则此顾客离开去其它理发店
- 如果理发师在睡觉，则叫起一位理发师开始理发
- 如果没有空闲的理发师，则选择沙发坐下
- 如果沙发已经坐满，则在休息去站着等待
- 理完发后顾客去收银台去缴费，交完费后理发师把发票交给顾客。顾客就离开，而理发师则准备服务下一位顾客
这一次理发店的问题比上一个理发店问题要复杂很多:
- 等待区分为了站立区和沙发区
- 新增加了收银台，理发师和顾客需要付款和发票的相互等待
- 三位理发师
这类问题使用信号量并发原语比较好，因为理发师、沙发等都是一定数量的资源。理发师和顾客之间缴费和发票之间的同步按理说使用channel比较合适，但是收银台只有一位收银员，还需要处理理发师、顾客和收银员之间的并发，所以我们可以把收银、开发票看成计数器是1的资源。
首先我们还是定义信号量和辅助方法:
// Semaphore定义
type Semaphore chan struct{}
func (s Semaphore) Acquire() {
s <- struct{}{}
func (s Semaphore) Release() {
<-s
func randomPause(max int) {
time.Sleep(time.Millisecond * time.Duration(rand.Intn(max)))
接下来我们定义所需的并发原语。
我们使用customerMutex这个排他锁来控制理发店的顾客数量。
使用sofaSema控制站立用户坐到沙发上以及理发师叫起等待的顾客。
paySema用来让顾客去缴费，而receiptSema让理发师把发票送给顾客，顾客离开。
// 控制顾客的总数
customerMutex sync.Mutex
customerMaxCount = 20
customerCount = 0
// 沙发的容量
sofaSema Semaphore = make(chan struct{}, 4)
// 理发师
// 三位理发师
barberSema Semaphore = make(chan struct{}, 3)
// 收银台
// 同时只有一对理发师和顾客结账
paySema Semaphore = make(chan struct{}, 1)
// 顾客拿到发票才会离开，控制开票
receiptSema Semaphore = make(chan struct{}, 1)
接下来我们实现理发师的逻辑:
// 理发师工作
func barber(name string) {
// 等待一个用户
log.Println(name + "老师尝试请求一个顾客")
sofaSema.Release() // 等待沙发上等待最久的一位顾客
log.Println(name + "老师找到一位顾客，开始理发")
randomPause(2000)
log.Println(name + "老师理完发，等待顾客付款")
paySema.Acquire() // 等待用户缴费
log.Println(name + "老师给付完款的顾客发票")
receiptSema.Release() // 通知顾客发票开好
log.Println(name + "老师服务完一位顾客")
接下来实现顾客的逻辑, 注意customerCount操作需要使用Mutex保护:
// 模拟顾客陆陆续续的过来
func customers() {
randomPause(500)
go customer()
func customer() {
customerMutex.Lock()
if customerCount == customerMaxCount {
log.Println("没有空闲座位了，一位顾客离开了")
customerMutex.Unlock()
return
customerCount++
customerMutex.Unlock()
log.Println("一位顾客开始等沙发坐下")
sofaSema.Acquire()
log.Println("一位顾客找到空闲沙发坐下,直到被理发师叫起理发")
paySema.Release()
log.Println("一位顾客已付完钱")
receiptSema.Acquire()
log.Println("一位顾客拿到发票，离开")
customerMutex.Lock()
customerCount--
customerMutex.Unlock()
最后把所有的逻辑串起来：
func main() {
// 托尼、凯文、艾伦理发师三巨头
go barber("Tony")
go barber("Kevin")
go barber("Allen")
go customers()
sigs := make(chan os.Signal, 1)
signal.Notify(sigs, syscall.SIGINT, syscall.SIGTERM)
<-sigs
运行这个程序观察并发的执行。
通过这个问题，我们可以好好的练习Semaphore的使用，以及两个goroutine之间信号的传递，控制并发程序的协作执行。
下一章你想了解什么样的经典并发问题呢？
历史并发问题
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK