经典同步问题Go语言实现

经典同步问题Go语言实现

引言

并发编程中各个并发实例有许多的制约关系，为了协调各个实例的制约关系，引入了同步的概念。
下面了解几个经典的同步问题：

1. 生产者消费者问题
2. 读写者问题
3. 哲学家就餐问题
4. 吸烟者问题
   许多的同步问题都可以简化为这三类问题。

基本概念

解决这些问题只需要了解互斥这个概念就可以做到，下面来了解一些基本概念。

临界资源： 系统中的某些资源一次只能有一个并发实例使用，多个实例使用时是未定义的。
临界区：并发实例中访问临界资源的那段代码。
同步：多个并发实例为了协调工作次序而形成的相互制约关系。
互斥：当一个并发实例进入临界时，其它并发实例会被阻塞。
阻塞： 并发实例因为不能获得某些资源而等待的行为。
互斥锁： 一般是由硬件系统和操作系统共同提供的接口，来帮助用户实现互斥的工具。
死锁： 多个并发实例占有一个临界资源，但是又需要被别的实例占有的某个资源。互相期望对方的资源。导致程序不能执行下去。
饥饿： 只一个实例长期得不到临界资源的现象。
原子操作: 又被叫做原语,只操作过程中连续的,不可被中断的一组程序。

特别的：
互斥锁一般由原子操作来实现。
硬件系统直接提供了swap指令来直接支持，因为该指令要占用总线吗，所以在多核CPU中也有效。

go语言在 sync 包 提供了 sync.Mutex 互斥锁。
c语言提供了 <pthread.h> 头文件中提供了 pthread_mutex_t 互斥锁。

import "sync"mutx := sync.Mutex{}  // 创建互斥锁
mutx.Lock()           // 锁住临界区
// do something
mutx.Unlock()         // 释放临界区

可以了解一下在C语言的中的实现,往往会用到😂。

// c语言相关(可以忽略)// 环境是在linux中 // 如果使用gcc请注意安装时的线程实现方式选项选POSIX#include <pthread.h>pthread_mutex_t mutx;           // 创建互斥锁
pthread_mutex_init(&mutex,NULL) // 初始化互斥锁
pthread_mutex_lock(&mutx);      // 锁住临界区
// do something
phtread_mutex_unlock(&mutex);   // 释放临界区// 注意 不使用后销毁
pthread_mutex_destroy(mutx);

生产者-消费者问题

最常见的，最典型的问题。

问题描述：一组生产者，一组消费者共享一个初始为空，大小为n的缓冲区。
生产者：缓冲区未满时向缓冲区填写消息，否则阻塞，直到缓冲区有空闲。
消费者：缓冲区未空时向缓冲区取消息，否则阻塞，直到有消息。

互斥锁解法

var n int = 10 // 缓冲区大小
var mutex sync.Mutex = sync.Mutex{} // 全局变量
var buf []int // 缓冲区func init() {buf = make([]int,n)buf = buf[:0]
}// 生产者
func productor(data int) {for {mutex.Lock()         // 获得锁 进入临界区for len(buf) == 10 { // 判断条件 缓冲区是否满了mutex.Unlock()          // 满的缓冲区 要将锁释放出来time.Sleep(time.Second) // 等一会儿mutex.Lock()            // 重新获取锁}buf = append(buf, data) // 将生产的数据写入缓冲区mutex.Unlock() // 释放锁}
}// 消费者
func consumer() {for {mutex.Lock()        // 获得锁 进入临界区for len(buf) == 0 { // 判断条件 缓冲区是否为空mutex.Unlock()          // 空的缓冲区 要将锁释放出来time.Sleep(time.Second) // 等一会儿mutex.Lock()            // 重新获取锁}data := buf[len(buf)-1] // 从缓冲区获取数据buf = buf[:len(buf)-1]fmt.Println(data) // 打印到标准输出mutex.Unlock() // 释放锁}
}

思考：

1. 想一想，如何验证正确性。
2. 我们用的是全局变量来当作缓冲区，如果传入[]int切片会造成何种情况。
3. 更好的办法是使用条件变量，试着使用条件变量写一个。

在go语言中，go提供了更加方便的组件chan来帮助我们编写并发程序，来试一下。

var ch chan int = make(chan int, 10)func consumer() {for {num := <-chfmt.Println(num)}
}func productor(num int) {for {ch <- num}
}

怎么样，是不是超级简单。

更复杂的生产者消费者问题

问题描述：
盘子：只能放一个水果。
爸爸：向盘子放苹果。
妈妈：向盘子放橘子。
女儿：向盘子拿苹果。
儿子：向盘子拿橘子。

var (plateVal string     = ""           // 盘子plate    sync.Mutex = sync.Mutex{} // 盘子互斥锁apple    sync.Mutex = sync.Mutex{} // 苹果orange   sync.Mutex = sync.Mutex{} // 橘子
)func init() {apple.Lock()orange.Lock()
}func dad() { // 父亲for {plate.Lock()       // 获取盘子互斥锁plateVal = "apple" // 像盘子中放苹果apple.Unlock()     // 允许取苹果}
}func mom() { // 母亲for {plate.Lock()        // 获取盘子互斥锁plateVal = "orange" // 向瓶子中放橘子orange.Unlock()     // 允许取橘子}
}func son() { // 儿子for {orange.Lock()   // 互斥的取橘子get := plateVal // 从盘子中取橘子plateVal = ""plate.Unlock()              // 允许向盘子放东西fmt.Println("son eat", get) // 吃}
}func daughter() {for {apple.Lock()    // 互斥的取苹果get := plateVal // 从盘子中取苹果plateVal = ""plate.Unlock()                   // 允许向盘子放东西fmt.Println("daughter eat", get) // 吃}
}

读者-写者问题

读写锁的实现原理。
一般情况下，互斥锁的效率普遍都要比读写锁高（就算是在多读少写的情况下）。
特别是读写锁在维护时容易出意想不到的bug。
陈硕在《linux多线程编程》就中建议尽量不要使用读写锁。

问题描述
有一组读者和一组写者共享一个文件。
读者：多个读者可以同时读一个文件。
写者：写者写文件时，不允许有另外的读者或写者读写文件。只能有一个写者独占文件。

一般解法（读优先）

var (count int        = 0            // 记录当前进入临界区的读者数量mutex sync.Mutex = sync.Mutex{} // 保护更新count的互斥量rw    sync.Mutex = sync.Mutex{} // 保证读者写者互斥的访问文件file  int        = 0            // 代表共享的文件
)// 写者
func writer() {for {rw.Lock()   // 互斥访问file++      // 写入rw.Unlock() // 释放共享文件}
}// 读者
func reader() {for {mutex.Lock()    //  访问count变量if count == 0 { // 当第一个读者访问共享文件时rw.Lock() // 阻止写进程}count++        // 读者计数器加1mutex.Unlock() // 释放互斥变量fmt.Println(file) // 读取mutex.Lock()    // 访问countcount--         // 读者计数器减1if count == 0 { // 最后一个读者退出rw.Unlock() // 允许写者写}mutex.Unlock() // 释放互斥变量count}
}

这个解法是读者优先的,在读者特别多的情况下会造成写者的饥饿。
造成写者永远不能进入临界区。
下面我们来看看读写公平的实现。

读写平等

上述的方案造成读优先的原因是因为：一个读进程获取访问权限后，其它的所有读者都可以直接访问文件。
那么我们加上对写者请求的关联，就可以构造出读写公平的访问。
增加一个互斥锁 w 。规定读者和写者都要先访问这个锁，使得写者占有该锁后，后续的读者不能直接访问，必须等待写者访问后才能访问。
而写者获取 w 后还必须等待之前的 reader 释放 rw 锁，才能独占文件并继续执行。

var (count int        = 0            // 当前读者数量mutex sync.Mutex = sync.Mutex{} //用于保护count的互斥rw    sync.Mutex = sync.Mutex{} // 读者写者互斥访问w     sync.Mutex = sync.Mutex{} // 读写平等file  int        = 0            // 表示要访问的文件
)func write() {for {w.Lock()    // 请求访问rw.Lock()   // 互斥访问 获取文件访问权file++      // 写操作rw.Unlock() // 释放共享文件w.Unlock()  // 恢复对共享文件的访问}
}func reader() {for {w.Lock()        // 请求访问 如果有写者请求 这里就会阻塞mutex.Lock()    // 访问countif count == 0 { // 第一个读rw.Lock() // 获取文件访问权}count++        // 读者计数器加一mutex.Unlock() // 退出count访问w.Unlock()     // 请求访问结束 此时可以有其它的读者写者申请访问fmt.Println(file) // 读mutex.Lock()    // 访问countcount--         // 读者计数器减一if count == 0 { // 如果是最一个rw.Unlock() // 释放对文件的占有}mutex.Unlock() // 退出访问count}
}

思考：

1. 如何验证正确性。
2. 根据上面的原理，试着自己构建一个读写锁。
3. 使用go test验证一下你自己构造的读写锁的性能和sync.Mutex以及sync.RWMutex的性能。

哲学家就餐问题

一般，在日常学习或工作中不会碰到这个问题。
如果出现这种问题一般是设计有问题,要好好反思一下有没有更好的设计。

问题描述：
一张圆桌上有5个哲学家，每名哲学家之间都有一根筷子，共计5根筷子；
哲学家有两种状态，进餐或思考。
进餐： 哲学家需要左右两根筷子才能进餐，否则等待。
思考： 不需要筷子。

出现死锁的情况

注意:下面的写法会导致死锁

var chopstick []sync.Mutex = make([]sync.Mutex, 5)func ph(no int) { // 哲学家 no为哲学家的编号for {chopstick[no].Lock()       // 取左边的筷子chopstick[(no+1)%5].Lock() // 取右边的筷子fmt.Printf("%d eatingn", no) // 吃饭chopstick[(no+1)%5].Unlock()  // 放回右边的筷子chopstick[no].Unlock() // 放回左边的筷子time.Sleep(time.Second) // 思考}
}

常规解法-限制同时就餐的数量

限制只能有四个人有获得筷子的权利。
此处循环等待失效，不会造成死锁。

var (count     int          = 0 // 就餐的和等待就餐的个数mutex     sync.Mutex   = sync.Mutex{}chopstick []sync.Mutex = make([]sync.Mutex, 5)
)func ph(no int) {for {mutex.Lock()count++for count == 5 { // 如果已经有四个进入了就等待mutex.Unlock()time.Sleep(time.Millisecond)mutex.Lock()}mutex.Unlock()// 和上一个例子相同 不多做解释chopstick[no].Lock()chopstick[(no+1)%5].Lock()fmt.Printf("%d eatingn", no)chopstick[(no+1)%5].Unlock()chopstick[no].Unlock()// 计数器减一mutex.Lock()count--mutex.Unlock()time.Sleep(time.Second) // 思考}
}

常规解法-同时获取两根筷子

哲学家尝试拿起两根筷子，在他尝试时候，其他人只能放下筷子，不能拿起筷子。
破坏了死锁条件的持有并等待。
注意：虽然筷子是一根根拿起的，但是我们用互斥锁保护了临界区，所以在外界看来是同时拿起的。

var (chopstick []sync.Mutex = make([]sync.Mutex, 5)mutex     sync.Mutex   = sync.Mutex{}
)func ph(no int) {for {mutex.Lock() // 一次性申请两个资源chopstick[no].Lock()chopstick[(no+1)%5].Lock()mutex.Unlock()fmt.Printf("%d eatingn", no)chopstick[(no+1)%5].Unlock()chopstick[no].Unlock()time.Sleep(time.Second)}
}

常规解法-奇偶编号

自己思考后试着写一下。

简化为生产者消费者问题

安排一个管理者,所有哲学家吃饭时要想管理者申请。
如果管理者发现资源不够，就让他等待。
其实就是上面的同时取根筷子（同时分配所有资源）。

吸烟者问题

问题描述：
一根烟需要烟草、烟纸和胶水才能制作成。
吸烟者1： 有烟草，需要胶水和烟纸
吸烟者2： 有烟纸，需要烟草和胶水
吸烟者3： 有胶水，需要烟草和烟纸
供应者： 每次随机提供三种材料中的两种，只允许同时取走所提供的两种材料。等取走了材料的人抽完了才放下一组材料。

比较简单，不需要分析，直接看代码。

var (offer1 sync.Mutex = sync.Mutex{} // 第一类资源，拥有烟草和纸offer2 sync.Mutex = sync.Mutex{} // 第二类资源offer3 sync.Mutex = sync.Mutex{} // 第三类资源finish sync.Mutex = sync.Mutex{} // 抽烟动作完成
)func init() {offer1.Lock() // 初始化offer2.Lock()offer3.Lock()
}func supplier() {for {rand := rand.Intn(3) // 生成一个随机数来模拟switch rand {case 0:offer1.Unlock() // 提供胶水和烟纸case 1:offer2.Unlock() // 提供烟草和胶水case 2:offer3.Unlock() // 提供烟草和烟纸default:}finish.Lock() // 等待抽烟者抽完烟}
}func smoker1() { // 吸烟者1for {offer1.Lock()fmt.Println("smoker1")finish.Unlock()}
}func smoker2() { // 吸烟者2for {offer2.Lock()fmt.Println("smoker2")finish.Unlock()}
}func smoker3() { // 吸烟者3for {offer3.Lock()fmt.Println("smoker3")finish.Unlock()}
}

解决同步问题的常规方法

一般，解决同步问题只需要掌握互斥锁和条件变量（同样的简单）就可以了。
但是如果在代码中大量的使用mutex和cond无疑是用小刀砍大树。
正确的做法是使用更高级的组件。看到这里，读者可以自己写一个线程安全的消息队列。

参考

[1] 王道论坛. 2021年·操作系统考研复习指导. 电子工业出版社
[2] 陈硕. Linux多线程编程. 电子工业出版社
[3] 宋劲杉. Linux C编程一站式学习