经典同步互斥问题
描述
生产者消费者问题
生产者消费者应当是最最基本的同步互斥问题了。生产者生产了之后消费者才消费，消费者消费之后，通知生产者再去生产，而生产者和消费者互斥的访问缓冲区。不难看出我们要设置的一个互斥变量mutex=1，empty=n，full=0；
具体问题描述如下：
该问题描述如下：有一个生产者在生产产品，这些产品将提供给若干个消费者去消费，为了使生产者和消费者能并发执行，在两者之间设置一个具有多个缓冲区的缓冲池，生产者将它生产的产品放入一个缓冲区中，消费者可以从缓冲区中取走产品进行消费，显然生产者和消费者之间必须保持同步，即不允许消费者到一个空的缓冲区中取产品，也不允许生产者向一个已经放入产品的缓冲区中再次投放产品。
mutex=1，empty=n，full=0；
Pp:生产者
Pp（empty）
Pp（mutex）
produce
Pp（mutex）
V(full)
Pc:消费者
P(full）
P(mutex）
consume
P(mutex）
V(empty)
哲学家就餐问题
哲学家就餐问题的三种解决方式：
1.互斥吃饭的动作
2.仅允许部分人(四个人)去抢筷子
3.按照一定规则去抢筷子（奇数编号的的哲学家先拿左边的筷子，再拿右边筷子，偶数编号则相反）
第一种：==互斥吃饭的动作==
mutex=1
P(mutex)
get the right chopsticks
get the left chopsticks
eating
P(mutex)
这样的缺点就是资源利用不充分；
下面见第二种:仅允许==部分人==(四个人)去抢筷子
Pi
chopsticks[5]=[1,1,1,1,1] ，count=4
P(count)
P(chopsticks[i])
P(chopsticks[i+1])
eating
V(chopsticks[i])
V(chopsticks[i])
V(count)
另外一种解决方案就是，按照一定==规则==去抢筷子
chopsticks[5]=[1,1,1,1,1]
if（i%2==0）{ //判断哲学家的编号的奇偶
p(chopsticks[i])
p(chopsticks[i+1])
eating
V(chopsticks[i])
V(chopsticks[i+1])
thinking
}
else {
p(chopsticks[i+1])
p(chopsticks[i])
eating
V(chopsticks[i+1])
V(chopsticks[i])
thinking
}
读者与写者问题
这个问题又可以分为三个个小问题，读者优先，写者优先和公平竞争。我们一个一个来看，先看读者优先。
==读者优先==
Reader process
mutex=1，count=0，mc=1；
P(mc）
V(mc)
if(count==1){
V(mutex)
}
reading
P(mc)
count--;
V(mc)
if(count==0){
V(mutex)
}
writer process
P(mutex)
writing;
V(mutex)
==写者优先==
==读写公平==
wmutex=1;
mutex=1;
cmutex=1;
int count=0; //读者个数
Reader
p(wmutex) //判断是否有写者进入
p(cmutex)
if(count==0){
p(mutex)
}
count++;
v(cmutex)
reading
v(wmutex)
p(cmutex)
count--
if(count==0){
v(mutex)
}
v(cmutex)
writer
p(wmutex)
p(mutex)
writing
v(mutex)
v(wmutex)
吃水果问题
问题描述：
吃水果问题：桌子有一只盘子，只允许放一个水果，父亲专向盘子放苹果，母亲专向盘子放桔子 儿子专等吃盘子的桔子，女儿专等吃盘子的苹果。只要盘子为空，父亲或母亲就可以向盘子放水果， 仅当盘子有自己需要的水果时，儿子和女儿可从盘子取出。
问题分析：一个互斥的资源，盘子。两个同步的关系，父亲放好了苹果通知女儿，女儿拿苹果通知父母有了空盘子。母亲这是放好了桔子通知儿子，儿子拿走了桔子去通知父母有了空盘子；需要一个信号量互斥盘子是否可用，两个同步信号量；
mutex =1，apple=0，orange=0；
Father
p(mutex)
put a orange; //父亲放橘子
v(orange)
Daughter
p(orange)
get a orange; //女儿拿橘子
v(mutex)
Mother
p(mutex)
put a apple; //母亲放苹果
v(apple)
Son
p(apple)
get a apple; //儿子放苹果
v(mutex)
理发师问题
问题描述：
假设有一个理发店只有一个理发师，一张理发时坐的沙发，若干张普通椅子顾客供等候时坐。没有顾客时，理发师就坐在理发的椅子上睡觉。顾客一到，他不是叫醒理发师，就是离开。如果理发师没有睡觉，而在为别人理发，他就会坐下来等候。如果所有的椅子都坐满了人，最后来的顾客就会离开。
问题分析：可以把沙发，座椅，顾客用同一个信号量表示
mutex=1；
ready=0；
chair=n+1；沙发和座椅总共的个数
finsh=1；//理发师初始位置空闲
customer
p(mutex）
if(chair>0){
chair--；
v(mutex)
v(ready)
p(finsh) //进入等待理发的队列
}
else{
v(mutex)
}
barber
p(ready)
hair-cut
p(mutex)
chair++;
v(mutex)
v(finsh)
吸烟者问题
抽烟者问题。假设一个系统中有三个抽烟者进程，每个抽烟者不断地卷烟并抽烟。抽烟者卷起并抽掉一颗烟需要有三种材料：烟草、纸和胶水。一个抽烟者有烟草，一个有纸，另一个有胶水。系统中还有两个供应者进程，它们无限地供应所有三种材料，但每次仅轮流提供三种材料中的两种。得到缺失的两种材料的抽烟者在卷起并抽掉一颗烟后会发信号通知供应者，让它继续提供另外的两种材料。
ps=1；
pa=0； //通知有烟草的人
pb=0； //通知有纸的人
pc=0； //同志有胶水的人
supplier
p(ps)
num=random%3;
if(num==0){
v(pa)
}
else if(num==1){
v(pb)
}
else {
v(pc)
}
process a
p(pa)
get paper and glue
smoking
v(ps)
process b
p(pb)
get tobacco and glue
smoking
v(ps)
process c
p(pc)
get tobacco and paper
smoking
v(ps)
猴子过桥问题
问题概述：
在两个相对的悬崖间，有一根绳子。悬崖两边有许多猴子，分别要到对面去。其中有一些属性，比如不能让不同方向的猴子同时处于绳上，同一方向的猴子必须依次通过等等。假设绳子两端的方向是南北。问，如何使用同步原语解决这个问题？
mutex=1； 用来互斥桥的使用
int count1=0； 计算绳子上猴子个数（从南到北）
int count2=0； 计算绳子上猴子个数（从北到南）
c1mutex=1； 用来互斥count1修改
c2mutex=1; 用来互斥count1修改
从南到北
p(c1mutex)
count1++ // 统计从南到北方向上猴子的个数
v(c1mutex)
if(count1==1){ //若为第一个猴子则去争夺，桥的使用权
p(mutex)
}
jump off the bridge
p(c1mutex)
count1--
v(c1mutex)
if（count1==0){ //若为最后一个猴子，则释放出桥的使用权
v(mutex)
}
从北到南
p(c2mutex)
count2++
v(c2mutex)
if(count2==1){
p(mutex)
}
jump off the bridge
p(c2mutex)
count2--
v(c2mutex)
if（count2==0){
v(mutex)
}
参考资料：2019年王道操作系统
下载地址：2019年王道操作系统
