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) ;  //如果没有资源则会循环等待； 

    S--; 

} 

---

wait(S){

    while(s<=0)  ;  //如果没有资源则会循环等待；

    S-- ;

}

v操作（signal）：释放一个单位资源，进程出来

---

signal(S){ 

    S++ ; 

} 

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) ;

消费者进程结构：

[html] view plain copy

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。为采用一般“信号量集”机制来实现的读者一写者算法。

c.哲学家进餐问题

(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) ;

        }

    }

}

【例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个环形缓冲区

    在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。

定义四个信号量：

empty——表示缓冲区是否为空，初值为n。

full——表示缓冲区中是否为满，初值为0。

mutex1——生产者之间的互斥信号量，初值为1。

mutex2——消费者之间的互斥信号量，初值为1。

    设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。

生产者进程

while(TRUE){

    生产一个产品;

    P(empty);

    P(mutex1)；

    产品送往buffer（in）；

    in=(in+1)mod n；

    V(mutex1);

    V(full);

}

消费者进程

while(TRUE){

P(full)

  P(mutex2)；

  从buffer（out）中取出产品；

  out=(out+1)mod n；

  V（mutex2）；

  V(empty);

  消费该产品;

  }

  需要注意的是无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。应先执行同步信号量的P操作，然后再执行互斥信号量的P操作，否则可能造成进程死锁。

【例2】桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

分析在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

    解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：

int S＝1;

int Sa＝0;

int So＝0;

      main()

      {

        cobegin

            father();      /*父亲进程*/

            son();        /*儿子进程*/

            daughter();    /*女儿进程*/

        coend

    ｝

    father()

    {

        while(1)

          {

            P(S);

            将水果放入盘中;

            if（放入的是桔子）V(So);

            else  V(Sa);

          }

    }

    son()

    {

        while(1)

          {

            P(So);

            从盘中取出桔子;

            V(S);

            吃桔子;

            ｝

    }

    daughter()

    {

        while(1)

            {

              P(Sa);

              从盘中取出苹果;

              V(S);

              吃苹果;

            ｝

｝