信号量及PV操作
信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为”P操作”和”V操作”
如何理解信号量及PV操作（我印象中iOS的互斥锁就是基于PV操作实现的，在面试中也会经常考察到这部分）
首先我们假定有一个只有三个停车位的停车场（停车位代表临界资源，车代表访问资源的代码），因为有时候会出现停车场停满的现象，这个时候来的车就要在一个队列里面等着。
我们来模拟一下有五辆车先后进入，之后又按进入时间依次离开（非必须）的情况。
最开始的时候S=3，代表有三个空的停车位。
1号车进入，S=2;
2号车进入，S=1;
3号车进入，S=0;
4号车进入，P，S=-1(代表有1辆车在等待);
5号车进入，P，S=-2;
1号车离开，V，S=-1，4号车进入;
2号车离开，V，S=0，5号车进入;
3号车离开，V，S=1;
4号车离开，V，S=2；
5号车离开，V，S=3;
用什么数据结构实现PV操作呢？分两种信号量
1.整型信号量
wait(S){
while(S<=0);
S = S-1;
}
signal(S){
S = S+1;
}
在wait里面，只要信号量S<=0，就会不断的循环，违背让权等待规则。
2.记录型信号量
用一个value代表资源数目，增加一个进程链表(我觉得队列也OK)，用于链接所有正在等待的进程。当执行P操作后，自我阻塞，将正在等待的进程放入进程链表中;当执行V操作后，取出链表中的一个元素，将其唤醒，放入临界区。
typedef struct{
int value;
struct process *L;
} semaphore
void wait(semaphore S){
S.value--;
if(S.value < 0){
add this process to S.L;
block(S.L);
}
}
void signal(semaphore S){
S.value++;
if(S.value<=0){
remove a process P from S.L;
wakeup(P);
}
}
用信号量实现同步的互斥的基本模型
同步(公共信号量初始化为0)
semaphore S=0;
P1(){ P2(){
... ...
x; P(S); //准备执行y了
V(S); //通知P2，x已完成 y;
... ...
} }
互斥(公共信号量初始化为1)
semaphore S=1;
P1(){ P2(){
... ...
P(S); V(S);
进程P1的临界区; 进程P2的临界区;
V(S); P(S);
... ...
} }
用信号量可以实现前驱关系，实现方法如下
假设一个有向图G，满足G=(V,E),V={S1,S2,S3,S4,S5,S6},E={,,,,,,}
实现算法如下
semaphore a1=a2=b1=b2=c=d=e=0;
//在这里，我让=a1,=a2,=b1,=b2,=d,=e,=c
S1(){
...;
V(a1);
V(a2);//表示S1已经运行完成
}
S2(){
P(a1);
...;
V(b1);
V(b2);
}
以此类推，就不赘述了。
接下来重点将一个几个经典的同步问题（考研重点，面试从来没人问过）
1.生产者消费者问题
问题描述：一组生产者进程和一组消费者进程共享一个初始化为空、大小为n的缓冲区。只有缓冲区没满时，生产者才能把生产出来的东西放入缓冲区，否则必须等待；只有缓冲区不为空时消费者才能从中取出东西，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入，一个消费者取出。
解答思路：首先根据最后一句话，缓冲区是临界资源，我们可以得出需要互斥的进去这个缓冲区。所以我们设置一个互斥变量（mutex=1），每当需要进入缓冲区的时候记得互斥一下。
之后我们根据题目要求，生产者生产的前提条件是缓冲区不满，也就是有闲的缓冲区（empty=n）;消费者消费的前提条件是缓冲区不空，也就是有满的缓冲区（full=0）。
完整代码：
semaphor mutex=1;
semaphore empty=n;
semaphore full=0;
pruduct(){
while(1){
生产...;
P(empty);//也就是要使用一个空的缓冲区
P(mutex);//互斥
把生产出来的东西放进缓冲区;
V(mutex);//互斥
V(full);//空的缓冲区少了一个，取而代之的是生产了一个满缓冲区
}
}
consumer(){
while(1){
P(full);//也就是要使用一个满的缓冲区
P(mutex);//互斥
消费掉生产出来的东西;
V(mutex);//互斥
V(empty);//满的缓冲区少了一个，取而代之的是生产了一个空的缓冲区
}
}
2、吃水果问题
问题描述：桌上有一只盘子，每次只能向其中一个放入水果。爸爸专门向盘子中放苹果，妈妈专门向盘子里放橘子，儿子专门等吃盘子重的句子，女儿专门等吃盘子中的苹果。只有盘子为空时，爸爸妈妈就可以向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿就可以从盘子中取出水果吃掉。
解答思路：因为在这里，所放的水果有两种，而且只能放一个水果，所以和之前的生产者消费者问题有了很大的不同。首先我们放水果吃水果都应该是一个互斥的过程，所以设置一个用于表示只有一个盘子的变量（plate=1）。
之后每次爸爸生产出来的是苹果，女儿消费的也是苹果，所以设置一个表示苹果的变量（apple=0）。同理，设置表示橘子的变量（orange=0）。
完整代码：
semaphore plate =1,apple=0,orange=0;
dad(){
while(1){
准备苹果;
P(plate);//互斥的向盘中取、放水果
向盘子里放苹果;
V(apple);//盘子中的苹果++,也可以理解为叫女儿过来吃苹果
}
}
daughter(){
while(1){
P(apple);//收到了爸爸的放苹果信息，准备来吃了，苹果--
拿走苹果;
V(plate);//拿走了苹果，盘子中的东西--，也可以理解为叫爸爸妈妈再放
}
}
妈妈和儿子同理，这里就不赘述了。
在这里我提出一个问题，如果盘子里可以放两个水果，拿代码需要做怎样的修改？
我的想法是，单纯的把plant的数量修改为2就可以，但是这样的话，放水果和吃水果就不是一个互斥的行为了，如果题目没要求互斥，就没问题了，如果题目要求必须是互斥的，则需要再加一个额外的互斥变量，保证放和吃的互斥（同理，放不互斥或吃不互斥，只要单独修改就好了，加上互斥变量就是互斥，不加就不互斥）
3、读者写者问题
问题描述：有读者和写者两组并发进程，共享一个文件，当两个和两个以上的读进程同时访问数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问就会导致数据的不一致。
所以我们要求，1.允许多个读者同时访问文件2.只允许一个写者往文件中写信息3.任一写者完成操作前不允许其他读者或写者工作4.写者在执行写操做前，应确保没有其他读者写者正在访问文件。
解答思路：首先读者的数量count，它的增加或者减少都不能让任何人唤醒或等待，所以count不是信号量，count应该是一个计数器。
读者和写者要互斥访问，所以我们要设置一个变量（rw=1）。
如果这样子就结束了，我们让读者执行：判断读者数量（若为0则P(rw)） -> count++ -> 读-> count-- ->判断读者数量（若count为0则V(rw)）
就会产生一个问题，假如两个读者同时达到，此时count=1，这样两个人同时执行count++，之后count有可能会=2，但是实际上这个时候已经有三个读者进去了。
所以我们在进行count++,count--操作时，应该加一个互斥锁（mutex=1），这样就可以避免这种情况了。
完整代码：
int count=0;
semaphore mutex=1;
semaphore rw=1;
writer(){
while(1){
P(rw);
writing;
V(rw);
}
}
reader(){
while(1){
P(mutex);//互斥访问count变量
if(count==0)//如果count==0，也就是第一个进来的读者
P(rw);//如果有写者在里面，就会等待，没有，就会让以后写者进不来
count++;
V(mutex);
读吧...;
P(mutex);//互斥访问count
count--
if(count==0)//如果这个是最后一个读者，这样的话把外面等着的写者叫起来吧
V(rw);
V(mutex);
}
}
这样子的话是一个读者优先，有时候有其他变形。
我们按照到达顺序和执行顺序可以把执行方式分为三类
到达顺序：RRWRRWWWRRR
执行顺序1：RRRRRRRWWWW (读者优先)
执行顺序2：RRWRRWWWRRR (顺序优先)
执行顺序3：RRWWWWRRRRR (写者优先)
顺序优先
解答思路：顺序优先要给双方加限制，当写者到的时候，P一下，后面到的读者都要等待。当读者到的时候，P一下（其实主要是为了确保前面没有写者），如果有写者就等待，如果没写者就进去（先执行修改count拿一系列操作），记得要在读之前V一下，保证下一个读者能顺利进入。
简单可以理解为，双方进之前都要进行P操作，但是写者只有在写完了才V，读者要在读之前V。
完整代码：
int count=0;
semaphore mutex=1;
semaphore rw=1;
semaphore w=1;
writer(){
while(1){
P(w);
P(rw);
writing;
V(rw);
V(w);
}
}
reader(){
while(1){
P(w);
P(mutex);//互斥访问count变量
if(count==0)//如果count==0，也就是第一个进来的读者
P(rw);//如果有写者在里面，就会等待，没有，就会让以后写者进不来
count++;
V(mutex);
V(w);
读吧...;
P(mutex);//互斥访问count
count--
if(count==0)//如果这个是最后一个读者，这样的话把外面等着的写者叫起来吧
V(rw);
V(mutex);
}
}
写者优先：
实现方法较为复杂，先放上代码
写者优先只要保证WRW形式的进入方式是WWR就可以了，也就是当第一个W进入的时候，把wfirst按住，这样R就进不来。接下来下一个W就会跳过if语句。但是因为不可以两个写者同时写，所以停在wmutex外面，当W读完之后，直接放下一个W进来，直到所有W都写完了，才会放R进来。
完整代码
semaphoRe rmutex=1,mutex=1,wfirst=1,writemutex=1;
int readcount=0.writecount=0;
reader(){
while(1){
P(wfirst);
if(readcount==0)
P(wmutex);
readcount++;
V(rmutex);
读吧...;
V(wfirst);
P(rmutex);
readcount--;
if(readcount==0)
V(wmutex);
V(rmutex);
}
}
writer(){
while(1){
P(writemutex)
if(writecount==0)
P(wfirst);
writecount++;
V(writemutex);
P(wmutex);
写吧...;
V(wmutex);
P(writemutex);
if(writecount==0)
V(wfirst);
writecount--;
V(writemutex);
}
}
4、哲学家进餐问题
问题描述：一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆着一根筷子，桌子的中间是一碗米饭。
哲学家只进行吃饭和思考，当哲学家饥饿的时候，拿起左右筷子（一根一根的拿起）。如果筷子在别人手上，则需要等待。只有同时拿到了两根筷子哲学家才可以进餐。
解答思路：
定义互斥信号量数组chopstick[5]={1,1,1,1,1}
哲学家按顺序从0~4编号，哲学家i左边筷子编号为i，右边筷子编号为(i+1)%5
第一种做法、
把取左筷子和取右筷子作为一个原子操作，加上锁进行，就可以了(放回去就不用加锁了)。
具体代码
Pi(){
while(1){
P(mutex);
P(chopstick[i]);
P(chopstick[(i+1)%5]);
V(mutex);
eat;
V(chopstick[i]);
V(chopstick[(i+1)%5]);
think;
}
}
用AMD信号量机制可以非常简洁的写完代码
Pi(){
while(1){
Swait(chopstick[(i+1)mod 5),chopstick[i]);
eat;
Signal(chopstick[(i+1)mod 5),chopstick[i]);
}
}
第二种做法、
用奇偶数的方法，让奇数哲学家先拿它左边的筷子，然后在去拿右边的筷子，偶数哲学家相反。
这样，1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子，最后无论如何都能有哲学家吃到饭。
具体代码
Pi(){
If(i%2==0){//偶数哲学家，先右后左
P(chopstick[i+1]%5);
P(chopstick[i]);
Eating();
V(chopstick[i+1]%5);
V(chopstick[i]);
}
else{//奇数哲学家，先左后右
P(chopstick[i]);
P(chopstick[i+1]%5);
Eating();
V(chopstick[i]);
V(chopstick[i+1]%5);
}
}
第三种做法、
至多只允许4位哲学家同时去取左边的筷子，最终能保证至少有一位哲学家能够进餐
具体代码
semaphore eating=4;
Pi(){
while(1){
P(eating);
P(chopstick[i]);
P(chopstick[(i+1)%5]);
eating();
V(chopstick[i]);
V(chopstick[(i+1)%5]);
V(eating);
}
}
5、吸烟者问题
问题描述：假设一个系统有三个抽烟者和一个供应者。每个抽烟者不停地卷烟并抽掉，抽烟者需要三种材料：烟草、纸、胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸、第三个拥有胶水。供应者无限的供应三种材料，供应者每次将两种材料放到桌子上，拥有剩下的那两种材料的男人卷一根烟抽到，并给供应者一个信号告诉完成了，供应者就会再放两种材料在桌子上。
直接上代码吧
Int random;//存储随机数
Semaphore offer1=0;//烟草和纸
Semaphore offer2=0;//烟草和胶水
Semaphore offer3=0;//纸和胶水
Semaphore finish=0;//是否完成
P1(){
Random =任意一个整数;
Random = random%3；
If(random==0)
V(offer1);
If(random==1)
V(offer2);
If(random==2)
V(offer3);
P(finish);
}
}
P2(){
While(1){
P(offer3);
拿出纸和胶水，抽掉;
V(finish);
}
}
我觉得这个直接把题目改成，爸爸往盘子里放苹果、桃子、梨。老大只吃苹果，老二只吃桃子，老三只吃梨，每次盘子里只能放一个水果，吃完之后再让爸爸放。
这样的话这个题目叫好理解很多了。
网友评论