2018/5/18 15:03:15当前位置推荐好文程序员浏览文章

信号量及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);

}

}

我觉得这个直接把题目改成,爸爸往盘子里放苹果、桃子、梨。老大只吃苹果,老二只吃桃子,老三只吃梨,每次盘子里只可以放一个水果,吃完之后再让爸爸放。

这样的话这个题目叫好了解很多了。

网友评论