形象点解释： 画一个圆，三条直径平分为6块 。6快体积相当与6碗面，6条半径相当6条筷子。
【Linux多线程】三个经典同步问题标签： 多线程同步生产者与消费者写者与读者
目录(?)[+]
在了解了《同步与互斥的区别 》之后，我们来看看几个经典的线程同步的例子。相信通过具体场景可以让我们学会分析和解决这类线程同步的问题，以便以后应用在实际的项目中。
一、生产者-消费者问题
问题描述：
一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。
分析：
关系分析：生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。
整理思路：这里比较简单，只有生产者和消费者两个进程，且这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步的PV *** 作的位置。
信号量设置：信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，初值为1；信号量full用于记录当前缓冲池中“满”缓冲区数，初值为 0；信号量empty用于记录当前缓冲池中“空”缓冲区数，初值为n。
代码示例：（semaphore类的封装见下文）
#include<iostream>
#include<unistd.h> // sleep
#include<pthread.h>
#include"semaphore.h"
using namespace std
#define N 5
semaphore mutex("/", 1) // 临界区互斥信号量
semaphore empty("/home", N) // 记录空缓冲区数，初值为N
semaphore full("/home/songlee",0)// 记录满缓冲区数，初值为0
int buffer[N]// 缓冲区，大小为N
int i=0
int j=0
void* producer(void* arg)
{
empty.P()// empty减1
mutex.P()
buffer[i] = 10 + rand() % 90
printf("Producer %d write Buffer[%d]: %d\n",arg,i+1,buffer[i])
i = (i+1) % N
mutex.V()
full.V() // full加1
}
void* consumer(void* arg)
{
full.P() // full减1
mutex.P()
printf(" \033[131m")
printf("Consumer %d read Buffer[%d]: %d\n",arg,j+1,buffer[j])
printf("\033[0m")
j = (j+1) % N
mutex.V()
empty.V()// empty加1
}
int main()
{
pthread_t id[10]
// 开10个生产者线程，10个消费者线程
for(int k=0k<10++k)
pthread_create(&id[k], NULL, producer, (void*)(k+1))
for(int k=0k<10++k)
pthread_create(&id[k], NULL, consumer, (void*)(k+1))
sleep(1)
return 0
}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455561234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
编译运行输出结果：
Producer 1 write Buffer[1]: 83
Producer 2 write Buffer[2]: 26
Producer 3 write Buffer[3]: 37
Producer 5 write Buffer[4]: 35
Producer 4 write Buffer[5]: 33
Consumer 1 read Buffer[1]: 83
Producer 6 write Buffer[1]: 35
Consumer 2 read Buffer[2]: 26
Consumer 3 read Buffer[3]: 37
Consumer 4 read Buffer[4]: 35
Consumer 5 read Buffer[5]: 33
Consumer 6 read Buffer[1]: 35
Producer 7 write Buffer[2]: 56
Producer 8 write Buffer[3]: 22
Producer 10 write Buffer[4]: 79
Consumer 9 read Buffer[2]: 56
Consumer 10 read Buffer[3]: 22
Producer 9 write Buffer[5]: 11
Consumer 7 read Buffer[4]: 79
Consumer 8 read Buffer[5]: 1112345678910111213141516171819201234567891011121314151617181920
二、读者-写者问题
问题描述：
有读者和写者两组并发线程，共享一个文件，当两个或以上的读线程同时访问共享数据时不会产生副作用，但若某个写线程和其他线程（读线程或写线程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：
允许多个读者可以同时对文件执行读 *** 作；
只允许一个写者往文件中写信息；
任一写者在完成写 *** 作之前不允许其他读者或写者工作；
写者执行写 *** 作前，应让已有的读者和写者全部退出。
分析：
关系分析：由题目分析可知，读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题。
整理思路：写者是比较简单的，它与任何线程互斥，用互斥信号量的 PV *** 作即可解决。读者的问题比较复杂，它必须实现与写者的互斥，多个读者还可以同时读。所以，在这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者的时候写者是无法写文件的，此时读者会一直占用文件，当没有读者的时候写者才可以写文件。同时，不同的读者对计数器的访问也应该是互斥的。
信号量设置：首先设置一个计数器count，用来记录当前的读者数量，初值为0；设置互斥信号量mutex，用于保护更新 count 变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问。
代码示例：
#include<iostream>
#include<unistd.h> // sleep
#include<pthread.h>
#include"semaphore.h"
using namespace std
int count = 0 // 记录当前的读者数量
semaphore mutex("/",1) // 用于保护更新count变量时的互斥
semaphore rw("/home",1)// 用于保证读者和写者的互斥
void* writer(void* arg)
{
rw.P() // 互斥访问共享文件
printf(" Writer %d start writing...\n", arg)
sleep(1)
printf(" Writer %d finish writing...\n", arg)
rw.V() // 释放共享文件
}
void* reader(void* arg)
{
mutex.P() // 互斥访问count变量
if(count == 0) // 当第一个读线程读文件时
rw.P() // 阻止写线程写
++count// 读者计数器加1
mutex.V() // 释放count变量
printf("Reader %d start reading...\n", arg)
sleep(1)
printf("Reader %d finish reading...\n", arg)
mutex.P() // 互斥访问count变量
--count// 读者计数器减1
if(count == 0) // 当最后一个读线程读完文件
rw.V() // 允许写线程写
mutex.V() // 释放count变量
}
int main()
{
pthread_t id[8]// 开6个读线程，2个写线程
pthread_create(&id[0], NULL, reader, (void*)1)
pthread_create(&id[1], NULL, reader, (void*)2)
pthread_create(&id[2], NULL, writer, (void*)1)
pthread_create(&id[3], NULL, writer, (void*)2)
pthread_create(&id[4], NULL, reader, (void*)3)
pthread_create(&id[5], NULL ,reader, (void*)4)
sleep(2)
pthread_create(&id[6], NULL, reader, (void*)5)
pthread_create(&id[7], NULL ,reader, (void*)6)
sleep(4)
return 0
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
编译运行的结果如下：
Reader 2 start reading...
Reader 1 start reading...
Reader 3 start reading...
Reader 4 start reading...
Reader 1 finish reading...
Reader 2 finish reading...
Reader 3 finish reading...
Reader 4 finish reading...
Writer 1 start writing...
Writer 1 finish writing...
Writer 2 start writing...
Writer 2 finish writing...
Reader 5 start reading...
Reader 6 start reading...
Reader 5 finish reading...
Reader 6 finish reading...1234567891011121314151612345678910111213141516
三、哲学家进餐问题
问题描述：
一张圆桌上坐着 5 名哲学家，桌子上每两个哲学家之间摆了一根筷子，桌子的中间是一碗米饭，如图所示：
哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、右两根筷子（一根一根拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
分析：
关系分析：5名哲学家与左右邻居对其中间筷子的访问是互斥关系。
整理思路：显然这里有 5 个线程，那么要如何让一个哲学家拿到左右两个筷子而不造成死锁或饥饿现象？解决方法有两个，一个是让他们同时拿两个筷子；二是对每个哲学家的动作制定规则，避免饥饿或死锁现象的发生。
信号量设置：定义互斥信号量数组chopstick[5] = {1,1,1,1,1}用于对 5 根筷子的互斥访问。
示例代码：
1．哲学家进餐问题：(1) 在什么情况下5 个哲学家全部吃不上饭考虑两种实现的方式，如下：
A. 算法描述： void philosopher(int i) /*i：哲学家编号，从0 到4*/ {while (TRUE) { think( )/*哲学家正在思考*/ take_fork(i)/*取左侧的筷子*/ take_fork((i+1) % N)/*取左侧筷子；％为取模运算*/eat( )/*吃饭*/put_fork(i)/*把左侧筷子放回桌子*/ put_fork((i+1) % N)/*把右侧筷子放回桌子*/ } } 分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。
B．算法描述：规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，等一段时间再重复整个过程。分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。
(2) 描述一种没有人饿死（永远拿不到筷子）算法。考虑了四种实现的方式（A、B、C、D）：
A．原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。
伪码： semaphore chopstick[5]={1，1，1，1，1}semaphore room=4void philosopher(int i) { while(true) {think()wait(room)//请求进入房间进餐 wait(chopstick[i])//请求左手边的筷子 wait(chopstick[(i+1)%5])//请求右手边的筷子 eat()signal(chopstick[(i+1)%5])//释放右手边的筷子 signal(chopstick[i])//释放左手边的筷子 signal(room)//退出房间释放信号量room } }
B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。
方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程由于等待队列的存在，使得对资源的请求满足FIFO 的要求，因此不会出现饥饿的情形。
伪码： semaphore chopstick[5]={1，1，1，1，1}void philosopher(int I) { while(true) { think()Swait(chopstick[(I+1)]%5,chopstick[I])eat()Ssignal(chopstick[(I+1)]%5,chopstick[I])} } 方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷子的 *** 作进行保护，使之成为一个原子 *** 作，这样可以防止死锁的出现。伪码： semaphore mutex = 1 semaphorechopstick[5]={1，1，1，1，1}void philosopher(int I) { while(true) { think()wait(mutex)wait(chopstick[(I+1)]%5)wait(chopstick[I])signal(mutex)eat()signal(chopstick[(I+1)]%5)signal(chopstick[I])} }
C．原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。
伪码： semaphore chopstick[5]={1，1，1，1，1}void philosopher(int i) { while(true) { think()if(i%2== 0) //偶数哲学家，先右后左。 { wait (chopstick[ i + 1 ] mod 5) wait (chopstick[ i]) eat()signal (chopstick[ i + 1 ] mod 5) signal (chopstick[ i]) } Else //奇数哲学家，先左后右。 { wait (chopstick[ i]) wait (chopstick[ i +1 ] mod 5) eat()signal (chopstick[ i]) signal (chopstick[ i + 1 ] mod 5)} }
D．利用管程机制实现（最终该实现是失败的，见以下分析）：原理：不是对每只筷子设置信号量，而是对每个哲学家设置信号量。test()函数有以下作用：
a. 如果当前处理的哲学家处于饥饿状态且两侧哲学家不在吃饭状态，则当前哲学家通过 test()函数试图进入吃饭状态。
b. 如果通过test()进入吃饭状态不成功，那么当前哲学家就在该信号量阻塞等待，直到其他的哲学家进程通过test()将该哲学家的状态设置为EATING。
c. 当一个哲学家进程调用put_forks()放下筷子的时候，会通过test()测试它的邻居，如果邻居处于饥饿状态，且该邻居的邻居不在吃饭状态，则该邻居进入吃饭状态。由上所述,该算法不会出现死锁，因为一个哲学家只有在两个邻座都不在进餐时，才允许转换到进餐状态。该算法会出现某个哲学家适终无法吃饭的情况，即当该哲学家的左右两个哲学家交替处在吃饭的状态的时候，则该哲学家始终无法进入吃饭的状态，因此不满足题目的要求。但是该算法能够实现对于任意多位哲学家的情况都能获得最大的并行度，因此具有重要的意义。
伪码：#define N 5 /* 哲学家人数*/#define LEFT (i-1+N)%N /* i的左邻号码 */ #define RIGHT (i+1)%N /* i的右邻号码 */ typedef enum { THINKING, HUNGRY, EATING } phil_state/*哲学家状态*/ monitor dp /*管程*/ { phil_state state[N]semaphore mutex =1semaphore s[N]/*每个哲学家一个信号量，初始值为0*/void test(int i) { if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING&&state[RIGHT(i)] != EATING ) { state[i] = EATINGV(s[i])} } void get_forks(inti) { P(mutex)state[i] = HUNGRYtest(i)/*试图得到两支筷子*/ V(mutex)P(s[i])/*得不到筷子则阻塞*/ } void put_forks(int i) { P(mutex)state[i]= THINKINGtest(LEFT(i))/*看左邻是否进餐*/ test(RIGHT(i))/*看右邻是否进餐*/ V(mutex)} } 哲学家进程如下： void philosopher(int process) { while(true) { think()get_forks(process)eat()put_forks(process)} }
2.理发师问题：一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。理发师可从事理发、收银和休息三种活动。
理发店的活动满足下列条件：
1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；
2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；
3）理发时间长短由理发师决定；
4）在站席区等待时间最长的顾客可坐到空闲的理发上；
5）任何时刻最多只能有一个理发师在收银。试用信号量机制或管程机制实现理发师进程和顾客进程。
原理：
(1) customer 进程：首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入理发店。在站席区等待沙发的空位（信号量sofa），如果沙发已满，则进入阻塞等待队列，直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity）。坐到沙发上，等待理发椅(barber_chair)，如果理发椅已满，则进入阻塞等待队列，直到出现空位，在沙发上等待时间最长的顾客离开沙发（释放信号量sofa）。坐到理发椅上，释放准备好的信号（customer_ready），获得该理发师的编号（0~1 的数字）。等待理发师理发结束（finished[barber_number]）。在离开理发椅之前付款（payment），等待收据 (receipt)，离开理发椅（leave_barberchair）。最后离开理发店。
这里需要注意几点：
a) 首先是几个需要进行互斥处理的地方，主要包括:进入站席区、进入沙发、进入理发椅和付款几个地方。
b) 通过barber_chair保证一个理发椅上最多只有一名顾客。但这也不够，因为单凭 baber_chair 无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上，因此增加信号量leave_barberchair，让顾客离开理发椅后，释放该信号，而理发师接收到该信号后才释放barber_chair 等待下一位顾客。
c) 在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的，这样，当该编号的理发师释放对应的finished[i]信号的时候，该顾客才理发完毕。
d) 理发师是通过mutex 信号量保证他们每个人同时只进行一项 *** 作（理发或者收款）。
e) 为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理发完毕后马上到收银台进入收款 *** 作而不是给下一位顾客服务。在伪码中由以下机制实现：即顾客在释放离开理发椅的信号前，发出付款的信号。这样该理发师得不到顾客的离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款 *** 作。直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该理发椅的信号，让下一位等待的顾客坐到理发椅上。
(2)barber 进程首先将该理发师的编号压入队列，供顾客提取。等待顾客坐到理发椅坐好(信号量 customer_ready)，开始理发，理发结束后释放结束信号（finished[i]）。等待顾客离开理发椅（leave_barberchair）（期间去收银台进行收款活动），释放理发椅空闲信号(barber_chair)，等待下一位顾客坐上来。
(3)cash（收银台）进程等待顾客付款(payment),执行收款 *** 作，收款 *** 作结束，给付收据（receipt）。信号量总表：信号量 waitsignal stand_capacity 顾客等待进入理发店顾客离开站席区 sofa 顾客等待坐到沙发顾客离开沙发 barber_chair 顾客等待空理发椅理发师释放空理发椅 customer_ready 理发师等待，直到一个顾客坐到理发椅顾客坐到理发椅上，给理发师发出信号 mutex 等待理发师空闲，执行理发或收款 *** 作理发师执行理发或收款结束，进入空闲状态 mutex1执行入队或出队等待入队或出队结束，释放信号 finished[i] 顾客等待对应编号理发师理发结束理发师理发结束，释放信号 leave_barberchair 理发师等待顾客离开理发椅顾客付款完毕得到收据，离开理发椅释放信号 payment 收银员等待顾客付款顾客付款，发出信号 receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据，释放信号
伪码： semaphore stand_capacity=5semaphore sofa=4semaphorebarber_chair=3semaphore customer_ready=0semaphore mutex=3semaphoremutex1=1semaphore finished[3]={0,0,0}semaphore leave_barberchair=0semaphore payment=0semaphore receipt=0void customer() { int barber_numberwait(stand_capacity)//等待进入理发店 enter_room()//进入理发店 wait(sofa)//等待沙发 leave_stand_section()//离开站席区 signal(stand_capacity)sit_on_sofa()//坐在沙发上 wait(barber_chair)//等待理发椅 get_up_sofa()//离开沙发 signal(sofa)wait(mutex1)sit_on_barberchair()//坐到理发椅上 signal(customer_ready)barber_number=dequeue()//得到理发师编号 signal(mutex1)wait(finished[barber_number])//等待理发结束 pay()//付款 signal(payment)//付款 wait(receipt)//等待收据 get_up_barberchair()//离开理发椅 signal(leave_barberchair)//发出离开理发椅信号 exit_shop()//了离开理发店 } void barber(int i) { while(true) { wait(mutex1)enqueue(i)//将该理发师的编号加入队列 signal(mutex1)wait(customer_ready)//等待顾客准备好 wait(mutex)cut_hair()//理发 signal(mutex)signal(finished[i])//理发结束 wait(leave_barberchair)//等待顾客离开理发椅信号 signal(barber_chair)//释放barber_chair 信号 } } void cash() //收银 { while(true) { wait(payment)//等待顾客付款 wait(mutex)//原子 *** 作 get_pay()//接受付款 give_receipt()//给顾客收据 signal(mutex)signal(receipt)//收银完毕，释放信号 } }
分析：在分析该问题过程中，出现若干问题，是参阅相关资料后才认识到这些问题的隐蔽性和严重性的,主要包括：
（1）在顾客进程，如果是在释放leave_barberchair 信号之后进行付款动作的话，很容易造成没有收银员为其收款的情形，原因是：为该顾客理发的理发师收到 leave_barberchair 信号后，释放barber_chair 信号，另外一名顾客坐到理发椅上，该理发师有可能为这另外一名顾客理发，而没有为刚理完发的顾客收款。为解决这个问题，就是采取在释放leave_barberchair 信号之前，完成付款 *** 作。这样该理发师无法进入下一轮循环为另外顾客服务，只能到收银台收款。
（2）本算法是通过给理发师编号的方式，当顾客坐到某理发椅上也同时获得理发师的编号，如此，当该理发师理发结束，释放信号，顾客只有接收到为其理发的理发师的理发结束信号才会进行付款等 *** 作。这样实现，是为避免这样的错误，即：如果仅用一个finished 信号量的话，很容易出现别的理发师理发完毕释放了finished 信号，把正在理发的这位顾客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编号，让理发师获取他理发的顾客的编号，但这样就会限制顾客的数量，因为finished[] 数组不能是无限的。而为理发师编号，则只需要三个元素即可。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）