进程同步和互斥机制

进程同步的几种机制  转自：http://www.cnblogs.com/sonic4x/archive/2011/07/05/2098036.html

多进程的系统中避免不了进程间的相互关系。本讲将介绍进程间的两种主要关系——同步与互斥，然后着重讲解解决进程同步的几种机制。
      进程互斥是进程之间发生的一种间接性作用，一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将发生能够问共享变量的程序段称为临界区。两个进程不能同时进入临界区，否则就会导致数据的不一致，产生与时间有关的错误。解决互斥问题应该满足互斥和公平两个原则，即任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。互斥问题可以用硬件方法解决，我们不作展开；也可以用软件方法，这将会在本讲详细介绍。
      进程同步是进程之间直接的相互作用，是合作进程间有意识的行为，典型的例子是公共汽车上司机与售票员的合作。只有当售票员关门之后司机才能启动车辆，只有司机停车之后售票员才能开车门。司机和售票员的行动需要一定的协调。同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次序。
本讲主要介绍以下四种同步和互斥机制：信号量、管程、会合、分布式系统。

一，信号量

参考自http://blog.csdn.net/leves1989/article/details/3305609

理解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操作属于进程的低级通信。

什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。
     一般来说，信号量S?0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S?0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

利用信号量和PV操作实现进程互斥的一般模型是：
进程P1              进程P2           ……          进程Pn
……                  ……                           ……
P（S）；              P（S）；                         P（S）；
临界区；             临界区；                        临界区；
V（S）；              V（S）；                        V（S）；
……                  ……            ……           ……

    其中信号量S用于互斥，初值为1。
    使用PV操作实现进程互斥时应该注意的是：
    （1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。
    （2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
   （3）互斥信号量的初值一般为1。

利用信号量和PV操作实现进程同步
PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。
    使用PV操作实现进程同步时应该注意的是：

    （1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。
    （2）信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。
    （3）同一信号量的P、V操作要成对出现，但它们分别在不同的进程代码中。

【例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);
              吃苹果;
            ｝
｝
 
思考题：

四个进程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)

 

 

二，管程：参考自http://hi.baidu.com/zucenaa/blog/item/e63d22277c9d9c09918f9de2.html

信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难。因此后来又提出了一种集中式同步进程——管程。其基本思想是将共享变量和对它们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰，便于维护和修改，易于保证正确性。

管程作为一个模块，它的类型定义如下：
monitor_name = MoNITOR;
共享变量说明;
define 本管程内部定义、外部可调用的函数名表;
use 本管程外部定义、内部可调用的函数名表;
内部定义的函数说明和函数体
{
共享变量初始化语句;
}

 

从语言的角度看，管程主要有以下特性：
（1）模块化。管程是一个基本程序单位，可以单独编译;
（2）抽象数据类型。管程是中不仅有数据，而且有对数据的操作;
（3）信息掩蔽。管程外可以调用管程内部定义的一些函数，但函数的具体实现外部不可见;
对于管程中定义的共享变量的所有操作都局限在管程中，外部只能通过调用管程的某些函数来间接访问这些变量。因此管程有很好的封装性。
为了保证共享变量的数据一致性，管程应互斥使用。 管程通常是用于管理资源的，因此管程中有进程等待队列和相应的等待和唤醒操作。在管程入口有一个等待队列，称为入口等待队列。当一个已进入管程的进程等待时，就释放管程的互斥使用权；当已进入管程的一个进程唤醒另一个进程时，两者必须有一个退出或停止使用管程。在管程内部，由于执行唤醒操作，可能存在多个等待进程（等待使用管程），称为紧急等待队列，它的优先级高于入口等待队列。
因此，一个进程进入管程之前要先申请，一般由管程提供一个enter过程；离开时释放使用权，如果紧急等待队列不空，则唤醒第一个等待者，一般也由管程提供外部过程leave。
管程内部有自己的等待机制。管程可以说明一种特殊的条件型变量：var c:condition；实际上是一个指针，指向一个等待该条件的PCB队列。对条件型变量可执行wait和signal操作：（联系P和V； take和give）
wait(c):若紧急等待队列不空，唤醒第一个等待者，否则释放管程使用权。执行本操作的进程进入C队列尾部；
signal(c):若C队列为空，继续原进程，否则唤醒队列第一个等待者，自己进入紧急等待队列尾部。

 

【示例】

生产者-消费者问题（有buffer）

问题描述：(一个仓库可以存放K件物品。生产者每生产一件产品，将产品放入仓库，仓库满了就停止生产。消费者每次从仓库中去一件物品，然后进行消费，仓库空时就停止消费。
解答：
管程：buffer=MODULE;
（假设已实现一基本管程monitor，提供enter,leave,signal,wait等操作）

  notfull,notempty:condition; // notfull控制缓冲区不满,notempty控制缓冲区不空；
count,in,out: integer; 　　  // count记录共有几件物品，in记录第一个空缓冲区，out记录第一个不空的缓冲区
buf:array [0..k-1] of item_type;
define deposit,fetch;
use monitor.enter,monitor.leave,monitor.wait,monitor.signal;

procedure deposit(item);
{
　　if(count=k) monitor.wait(notfull);
　　buf[in]=item;
　　in:=(in+1) mod k;
　　count++;
　　monitor.signal(notempty);
}
procedure fetch:Item_type;
{
　　if(count=0) monitor.wait(notempty);
　　item=buf[out];
　　in:=(in+1) mod k;
　　count--;
　　monitor.signal(notfull);
　　return(item);
}
{
count=0;
in=0;
out=0;
}
进程：producer,consumer;
producer（生产者进程）：
Item_Type item;
{
　　while (true)
　　{
　　　　produce(&item);
　　　　buffer.enter();
　　　　buffer.deposit(item);
　　　　buffer.leave();
　　}
}
consumer（消费者进程）：
Item_Type item;
{
　　while (true)
　　{
　　　　buffer.enter();
　　　　item=buffer.fetch();
　　　　buffer.leave();
　　　　consume(&item);
　　}
}

【附】有关wait和signal的语言表示

信号量结构使用C语言表示如下：

typedef struct {
    int value;//记录了这个信号量的值 
    struct process *list;//储存正在等待这个信号量的进程 
} semaphore;

wait()信号量部分代码如下：

wait(semaphore *S) {
    S->value--;
    if(S->value < 0) {
        add this process to S->list;
        block();
    }
}

signal()信号量部分代码如下：

signal(semaphore *S) {
    S->value++;
    if(S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}

一、The Bounded-Buffer Problem：

full初始化为0，empty初始化为n，mutex为1

do{
    wait(full);
    wait(mutex);
    ...
    //remove an item from buffer to nextc
    ...
    signal(mutex);
    signal(empty);
    ...
    //consume the item in nextc
    ...
} while(TRUE);

二、The Readers-Writers Problem：

wrt初始化为1，readcount初始化为0，mutex为1

写者操作： 

 

do{
    wait(wrt);
    ...
    //writing is performed 
    ...
    signal(wrt);
} while(TRUE);

 

读者操作：

do{
    wait(mutex);//确保与signal(mutex)之间的操作不会被其他读者打断
    readcount++;
    if(readcount == 1)
        wait(wrt);
    signal(mutex);
    ...
    //reading is performed
    ...
    wait(mutex);
    readcount--;
    if(readcount == 0)
        signal(wrt);
    signal(mutex);
} while(TRUE);

三、The Dining-Philosophers Problem：

所有的chopstick[5]全部初始化为1

do{
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    ...
    //eating
    ...
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    ...
    //thinking
    ...
} while(TRUE);

但是这个解决方案的最大问题在于它会出现死锁。所以我认为应该增加一个信号量mutex，并初始化为1：

do{
    wait(mutex);
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    signal(mutex);
    ...
    //eating  
    ...
    wait(mutex);
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    signal(mutex);
    ...
    //thinking  
    ...
} while(TRUE);

这样由于确保了一位哲学家在拿起两只筷子的时间内其他哲学家不可以拿起任何一支筷子，从而破坏了死锁出现需要的四个特征中的Hold And Wait特征，从而避免了死锁的发生。