进程同步之信号量机制（pv操作）及三个经典同步问题

信号量机制即利用pv操作来对信号量进行处理。

什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。

当它的值大于0时，表示当前可用资源的数量；

当它的值小于0时，其绝对值表示等待使用该资源的进程个数。

注意，信号量的值仅能由PV操作来改变。

     一般来说，信号量S³0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S 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);               吃苹果;             ｝ ｝   思考题：

四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：     （1）应定义的信号量及初值：                    。     （2）在下列的程序中填上适当的P、V操作，以保证它们能正确并发工作：      A()                B()                  C()                 D()       {                 {                    {                  {       [1];                [3];                  [5];                 [7];       read F;             read F;                read F;              read F;      [2];                [4];                  [6];                 [8];       }                  }                    }                  } 

    思考题解答： （1）定义二个信号量S1、S2，初值均为1，即：S1=1，S2=1。其中进程A和C使用信号量S1，进程B和D使用信号量S2。 （2）从[1]到[8]分别为：P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)

1、测量控制系统中的数据采集任务把所采集的数据送一单缓冲区；计算任务则 从该缓冲区中取出数据并进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。

       Var Sempty，Sfull: semaphore:= 1,0

Begin

              Parbegin

              Collection:begin

              repeat

                     采集一个数据；

                     wait(Sempty);

                     数据放入缓冲区；

                     signal(Sfull);

              untill false;

              end;

              Compute:begin

              repeat

                     wait(Sfull);

                     从缓冲区取出数据;

                     signal(Sempty);

                     计算;

`                    until false;

                     end;

              Parend

       End

2、有一阅览室，共有100个座位。读者进入时必须先在一种登记表上登记，该表为每一座位列一个表目，包括座号和读者姓名。读者离开时要注销掉登记内容。试用wait和signal原语描述读者进程的同步问题。

       var mutex, readcount :semaphore := 1,100;

Begin

              Parbegin

              Process Reader:begin

              repeat

              wait(readcount);

              wait(mutex);

              ；

              signal(mutex);

              wait(mutex)

              signal(mutex);

              signal(readcount);

              until false;

              end;

              parend;

       End;

1）、桌上有一空盘，只允许放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子；女儿专吃盘中的苹果，儿子专吃盘中的桔子；试用wait和signal原语实现爸爸、妈妈、女儿、儿子之间的同步问题。

var Sempty, Sapple, Sorange,: semaphore:= 1,0,0;

 begin

       parbegin

              Father: begin

                            repeat

                                   wait(Sempty);                                ;

                                   signal(Sapple);                         until false;

                       end;

              Mother: begin

                            repeat

                                   wait(Sempty);                                ;

                                   signal(Sorange);                       until false;

                        end;

              Son: begin

                            repeat

                                   wait(Sorange);

                                   ;

                                   signal(Sempty);

                            until false;

                      end;

              Daughter: begin

                            repeat

                                   wait(Sapple);

                                   ;

                                   signal(Sempty);                       until false;

                       end;

              parend;

end;

1、在4×100米接力赛中，4个运动员之间存在如下关系，运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交给运动员3，运动员3也只有在接到运动员2传来的棒后才能跑，他跑完100米后交给运动员4，运动员4接到棒后跑完全程。请试用信号量机制对其上过程进行分析。

       var s1,s2,s3:semaphpre:=0,0,0;

       begin

              parbegin

                     Athlete1: begin

                                   Run100m;

                                   signal(s1);

                                end;

                     Athlete2: begin

                                   wait(s1);

                                   Run100m;

                                   signal(s2);

                                end;

                     Athlete3: begin

                                   wait(s2);

                                   Run100m;

                                   signal(s3);

                                end;

                     Athlete4: begin

                                   wait(s3);

                                   Run100m;

                                end;

              parend;

       end

2、在公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开、关车门；当售票员关好车门后驾驶员才能开车行驶。试用wait和signal操作实现司机和售票员的同步。

var s1,s2:semaphore:=0,0;

begin

       parbegin

              Process Driver

              begin

              repeat

                     ;

                     ;

                     signal(s2);

                     wait(s1);

              until false;

              end;

              Process BookingClerk;

              begin

              repeat

                     ;

                     wait(s2);

                     ;

                     ;

                     signal(s1);

              until false

              end;

       parend;

end;

1、假设有3个并发进程P，Q，R，其中P负责从输入设备上读入信息，并传送给Q,Q将信息加工后传送给R，R负责打印输出。进程P，Q共享一个有m个缓冲区组成的缓冲池；进程Q，R共享一个有n个缓冲区组成的缓冲池（假设缓冲池足够大，进程间每次传输信息的单位均小于等于缓冲区长度），请写出满足上述条件的并发程序。（12分）

var mutex1,mutex2,Sip,Siq,Soq,Sor:semaphore:=1,1,m,0,n,0;

begin

       parbegin

              Process P

              begin

              repeat

                     wait(Sip);

                     wait(mutex1);

                     signal(mutex1);

                     signal(Siq);

              until false

              end;

              Process Q

              begin

              repeat

                     wait(Siq);

                     wait(mutex1);

                     signal(mutex1);

                     signal(Sip);