【转】进程同步之信号量机制（pv操作）及三个经典同步问题 上篇博客中（），我们对临界区，临界资源，锁机制详细解读了下，留下了⼀个问题，就是锁机制只能判断临界资源是否被占⽤，所以他解决了互斥问题，但是他不能确定前⾯的进程是否完成，所以他不能⽤于同步问题中。下⾯就为你讲解信号量机制是如何解决这⼀问题的。 1.信号量机制
信号量机制即利⽤pv操作来对信号量进⾏处理。
什么是信号量？信号量（semaphore）的数据结构为⼀个值和⼀个指针，指针指向等待该信号量的下⼀个进程。信号量的值与相应资源的使⽤情况有关。
当它的值⼤于0时，表⽰当前可⽤资源的数量；
当它的值⼩于0时，其绝对值表⽰等待使⽤该资源的进程个数。
注意，信号量的值仅能由PV操作来改变。
⼀般来说，信号量S³0时，S表⽰可⽤资源的数量。执⾏⼀次P操作意味着请求分配⼀个单位资源，因此S
的值减1；当S<0时，表⽰已经没有可⽤资源，请求者必须等待别的进程释放该类资源，它才能运⾏下去。⽽执⾏⼀个V操作意味着释放⼀个单位资源，因此S的值加1；若S£0，表⽰有某些进程正在等待该资源，因此要唤醒⼀个等待状态的进程，使之运⾏下去。
2.PV操作
可控硅散热器
什么是PV操作？
p操作（wait）：申请⼀个单位资源，进程进⼊
经典伪代码
wait(S){
while(s<=0)<span > </span>//如果没有资源则会循环等待；
;
S-- ;
}
v操作（signal）：释放⼀个单位资源，进程出来
signal(S){
S++ ;
}
p操作（wait）：申请⼀个单位资源，进程进⼊
v操作（signal）：释放⼀个单位资源，进程出来
PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进⾏操作，具体定义如下：
P（S）：①将信号量S的值减1，即S=S-1；
②如果S<=0，则该进程继续执⾏；否则该进程置为等待状态，排⼊等待队列。
V（S）：①将信号量S的值加1，即S=S+1；
②如果S>0，则该进程继续执⾏；否则释放队列中第⼀个等待信号量的进程。
PV操作的意义：我们⽤信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。
使⽤PV操作实现进程互斥时应该注意的是：
（1）每个程序中⽤户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分⽀，要认真检查其成对性。
（2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
（3）互斥信号量的初值⼀般为1。
3.三个经典同步问题
前⾯我们讲到信号量机制，下⾯我们讲解利⽤信号量及PV操作解决⼏个经典同步问题。
a.⽣产者-消费者（缓冲区问题）
⽣产者⼀消费者问题(producer-consumerproblem)是指若⼲进程通过有限的共享缓冲区交换数据时的缓冲区资源使⽤问题。假设“⽣产者”进程不断向共享缓冲区写⼈数据(即⽣产数据)，⽽“消费者”进程不断从共享缓冲区读出数据(即消费数据)；共享缓冲区共有n个；任何时刻只能有⼀个进程可对共享缓冲区进⾏操作。所有⽣产者和消费者之间要协调，以完成对共享缓冲区的操作。
⽣产者进程结构：
do{
wait(empty) ;
wait(mutex) ;
add nextp to buffer
signal(mutex) ;
signal(full) ;
}while(1) ;
消费者进程结构：
do{
wait(full) ;
wait(mutex) ;
remove an item from buffer to nextp
signal(mutex) ;
signal(empty) ;
}while(1) ;
彩印业务我们可把共享缓冲区中的n个缓冲块视为共享资源，⽣产者写⼈数据的缓冲块成为消费者可⽤资源，⽽消费者读出数据后的缓冲块成为⽣产者的可⽤资源。为此，可设置三个信号量：full、empty和mutex。其中：full表⽰有数据的缓冲块数⽬，初值是0；empty表⽰空的缓冲块数初值是n；mutex⽤于访问缓冲区时的互斥，初值是1。实际上，full和empty间存在如下关系：full + empty = N
注意：这⾥每个进程中各个P操作的次序是重要的。各进程必须先检查⾃⼰对应的资源数在确信有可⽤资源后再申请对整个缓冲区的互斥操作；否则，先申请对整个缓冲区的互斥操后申请⾃⼰对应的缓冲块资源，就可能死锁。出现死锁的条件是，申请到对整个缓冲区的互斥操作后，才发现⾃⼰对应的缓冲块资源，这时已不可能放弃对整个缓冲区的占⽤。如果采⽤AND信号量集，相应的进⼊区和退出区都很简单。如⽣产者的进⼊区为Swait(empty，mutex)，退出区为Ssignal(full，mutex)。
b.作者读者问题
读者⼀写者问题(readers-writersproblem)是指多个进程对⼀个共享资源进⾏读写操作的问题。
假设“读者”进程可对共享资源进⾏读操作，“写者”进程可对共享资源进⾏写操作；任⼀时刻“写者”最多只允许⼀个，⽽“读者”则允许多个。即对共享资源的读写操作限制关系包括：“读—写，互斥、“写⼀写”互斥和“读—读”允许。
我们可认为写者之间、写者与第⼀个读者之间要对共享资源进⾏互斥访问，⽽后续读者不需要互斥访问。为此，可设置两个信号量Wmutex、Rmutex和⼀个公共变量Rcount。其中：Wmutex表⽰“允许写”，初值是1；公共变量Rcount表⽰“正在读”的进程数，初值是0；Rmutex表⽰对Rcount的互斥操作，初值是1。
在这个例⼦中，我们可见到临界资源访问过程的嵌套使⽤。在读者算法中，进⼊区和退出区⼜分别嵌套了⼀个临界资源访问过程。
对读者⼀写者问题，也可采⽤⼀般“信号量集”机制来实现。如果我们在前⾯的读写操作限制上再加⼀个限制条件：同时读的“读者”最多R个。这时，可设置两个信号量Wmutex和Rcount。其中：Wmutex表⽰“允许写”，初值是¨Rcount表⽰“允许读者数⽬”，初值为R。为采⽤⼀般“信号量集”机制来实现的读者⼀写者算法。
(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=4;
void 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 ;
semaphore chopstick[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 =1;
semaphore s[N]; /*每个哲学家⼀个信号量，初始值为0*/
void test(int i)
{
if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING && state[RIGHT(i)] != EATING )
{
state[i] = EATING;
V(s[i]);
}
}
void get_forks(int i)
{
P(mutex);
state[i] = HUNGRY;
test(i); /*试图得到两⽀筷⼦*/
V(mutex);
P(s[i]); /*得不到筷⼦则阻塞*/
}
void put_forks(int i)
{
P(mutex);
state[i]= THINKING;
test(LEFT(i)); /*看左邻是否进餐*/
test(RIGHT(i)); /*看右邻是否进餐*/
V(mutex);
}
}
哲学家进程如下：
void philosopher(int process)
{
while(true)
{
think();
get_forks(process);
eat();
put_forks(process);
}
}
看完上⾯想必⼤家有点转晕了，来⼏道题，熟悉下。
【例1】⽣产者-消费者问题
在多道程序环境下，进程同步是⼀个⼗分重要⼜令⼈感兴趣的问题，⽽⽣产者-消费者问题是其中⼀个有代表性的进程同步问题。下⾯我们给出了各种情况下的⽣产者-消费者问题，深⼊地分析和透彻地理解这个例⼦，对于全⾯解决操作系统内的同步、互斥问题将有很⼤帮助。
（1）⼀个⽣产者，⼀个消费者，公⽤⼀个缓冲区。
定义两个同步信号量：
empty——表⽰缓冲区是否为空，初值为1。
full——表⽰缓冲区中是否为满，初值为0。
⽣产者进程
while(TRUE){
⽣产⼀个产品;
P(empty);
产品送往Buffer;
V(full);
}
消费者进程
while(True){
P(full);
从Buffer取出⼀个产品;
V(empty);
消费该产品;
}
（2）⼀个⽣产者，⼀个消费者，公⽤n个环形缓冲区。
定义两个同步信号量：
empty——表⽰缓冲区是否为空，初值为n。
full——表⽰缓冲区中是否为满，初值为0。
设缓冲区的编号为1～n-1，定义两个指针in和out，分别是⽣产者进程和消费者进程使⽤的指
，指向下⼀个可⽤的缓冲区。
⽣产者进程
while(TRUE){
电极扁钢⽣产⼀个产品;
P(empty);
产品送往buffer（in）；
in=(in+1)mod n；
V(full);
}
消费者进程
while(TRUE){
P(full);
从buffer（out）中取出产品；
out=(out+1)mod n；
V(empty);
消费该产品;
}
（3）⼀组⽣产者，⼀组消费者，公⽤n个环形缓冲区
