进程管理(三) 同步与互斥(详解四大经典问题：生产消费者|哲学家进餐|理发师问题|读者写者问题)

（三）同步与互斥

        间接相互制约关系（互斥）：若某一进程要求使用某种资源，而该资源正在被另一个进程占用，并且该资源不允许两个资源同时占用，那么只能等占用资源的进程释放资源后再使用，这种制约关系为互斥关系，因其制约形式是“进程——资源——进程”，故称为间接相互制约关系。

        直接相互制约关系（同步）：某一进程若收不到另一个进程给他提供的必要信息就不能继续下去，这种情况表明了两个进程要在某些点上交换信息，相互交流的情况。这种制约形式是“进程——进程”，也因此称为直接相互制约关系（同步）。

        Statement：同类进程即为互斥关系，不同类进程为同步关系。例如：生产者和生产者是互斥关系，生产者和消费者是同步关系。

1、临界资源与临界区

临界资源：同时仅允许一个进程使用或访问的资源称为临界资源，需要不同进程互斥访问。

临界区：进程中用于访问临界资源的一段代码，是属于对应的进程的。

2、信号量及同步原语

        信号量是一个确定的二元组（s， q），其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。整型变量s表示系统中某类资源的数目，当其值大于0时，表示系统中存在的可用资源数目，当其小于0时，表示系统中因请求该资源而被阻塞的进程的数目。除信号量的初值外，信号量的操作只能通过P操作和V操作来改变，操作系统利用它的状态对进程和资源进行管理。

        P操作：P(s):  s = s – 1 若s >= 0则继续，否则阻塞该进程，并将该进程挂在等待队列中。

struct semaphore{    int count;    queue q};P(s){    s.count--    if(s.count < 0){ 该进程阻塞 将该进程插入阻塞队列s.q    }}

        V操作：V(s) : 若s > 0则继续，否则，从该进程等待队列中移出第一个进程，使其变为就绪状态，插入就绪队列当中，然后继续执行。

V(s){    s.count++    if(s.count <= 0){ 在s.q中取出第一个进程p 将p插入就绪队列    }}

注意：

        P和V均为不可分割的原子操作，若执行P/V操作，必须执行完毕。

        P和V在系统中一定是成对实现的但未必在同一个进程中。

实现进程同步：

考虑同步关系：并发进程P1和P2，P1中有一条语句S1，P2中有一条语句S2，则通过信号量实现进程同步如下：

semaphore N = 0P1(){    ...    S1    V(N)    ...}P2(){    ...    P(N)    S2    ...}

实现进程互斥：

考虑互斥问题：P1和P2共享资源S，且S只能同时供一个进程使用或访问，则通过信号量实现进程互斥过程如下：

semaphore  N = 1P1(){    ...    P(N)    访问S    V(N)    ...}P2(){    ...    P(N)    访问S    V(N)    ...}

3、经典同步问题

        生产者-消费者问题

        问题描述：一组生产者向一组消费者提供产品，他们共享一个有界的缓冲区，生产者向其中投入产品，消费者取走产品，循环往复，以至无穷......

semaphore full = 0semaphore empty= nsemaphore mutex = 1Producer(){    while(1){ produce an item P(empty)     //获取空位置 P(mutex)     //获取缓冲区访问权限，与上一行不可调换顺序，否则可能死锁 将产品放入缓冲池 V(mutex)     //释放缓冲区访问权限 V(full)      //占位    }}Consumer(){    while(1){ P(full)      //获取产品位置 P(mutex)     //获取缓冲区访问权限，与上一行不可调换顺序，否则可能死锁 取出产品 V(mutex)     //释放缓冲区访问权限 V(empty)     //空出一个位置    }}

注意：

P(full)/P(empty)与P(mutex)顺序不能变换，否则可能出现死锁。例如，某一时刻缓冲区已经满，而生产者先P(mutex)成功，这时，由于empty = 0，故P(empty)会被挂起，生产操作不能进行，而消费者因为不能申请到对缓存区的访问也不能取走一个产品，故生产者和消费者会陷入相互等待，形成死锁。因此P操作必须后对互斥信号量进行操作。

mutex不能省略！例如，在生产者和消费者不唯一的情况下，两个生产者同时进行了P(empty)操作，第一个生产者执行了buffer(in) = nextp操作，这时，该生产者还未来得及执行in= (in + 1) % n 的操作，而第二个生产者以及执行了buffer(in) = nextp操作，这样就将两个新产品放在了同一个位置上，因此在多生产者和多消费者的情况下，一定要设置mutex互斥信号量，以保证对缓冲池的互斥访问。简而言之，互斥信号量就是为了同类进程互斥准备的。

        哲学家进餐问题

        问题定义：5个哲学家围桌而坐，每两个哲学家之间放一支筷子，哲学家们在思考和干饭之间切换状态，当他们想干饭时，他们拿起左右的筷子进餐。也就是每支筷子会被 其左右两个哲学家使用......

        分析：该问题筷子是临界资源，不能同时被两个哲学家使用，首先可以通过如下信号量来控制互斥过程。

semaphore Fork[5] = {1, 1, 1, 1, 1}philosopher(int i){    while(1){ think(); P(Fork[i % 5])// 申请使用第1根筷子 P(Fork[(i + 1) % 5]) // 申请使用第2根筷子 ganfan() V(Fork[i % 5]) V(Fork[(i + 1) % 5])    }}

注意，这种算法存在问题，就是五个哲学家同时拿起左手边的筷子时，五个哲学家都不能拿起右手边的筷子，因此陷入交替等待的死锁状态。解决办法：同时只允许四个哲学家同时进餐，或者规定奇数号的哲学家每次先拿起左手边的筷子，偶数号的哲学家每次先拿起右手边的筷子。

每次只允许4个哲学家同时进餐

semaphore Fork[5] = {1, 1, 1, 1, 1}flag = 4philosopher(int i){    while(1){ think(); P(flag) P(Fork[i % 5])// 申请使用第1根筷子 P(Fork[(i + 1) % 5]) // 申请使用第2根筷子 ganfan() V(flag) V(Fork[i % 5]) V(Fork[(i + 1) % 5])    }}

奇数号哲学家先拿左边筷子

semaphore Fork[5] = {1, 1, 1, 1, 1}philosopher(int i){    while(1){ if(i % 2 == 0){     think();     P(Fork[i % 5])// 申请使用左手边筷子     P(Fork[(i + 1) % 5]) // 申请使用右手边筷子     ganfan()     V(Fork[i % 5])     V(Fork[(i + 1) % 5]) }else{     think();     P(Fork[(i + 1) % 5]) // 申请使用右手边筷子     P(Fork[i % 5])// 申请使用左手边筷子     ganfan()     V(Fork[i % 5])     V(Fork[(i + 1) % 5]) }    }}

        理发师问题

        问题描述：理发店里有一位理发师、一把理发椅和若干供顾客等待的椅子(n个)，若没有顾客理发，则理发师坐在理发椅上睡觉；当一个顾客到来时，他会唤醒理发师，若理发师正在给顾客理发，如果有空凳子，则顾客等待；否则顾客离开。要为理发师和顾客设计一段程序来描述其活动。

int chairs = n + 1;semaphore ready = 0;semaphore finish= 1;semaphore mutex = 1;barber(){    while(1){ P(ready); //看看有没有顾客，如果没有就阻塞 理发();    P(mutex); //理发结束，对chairs进行操作 chairs++; V(mutex); V(finish) //理发师空闲    }}customer(){    P(mutex)  //申请更改chair    if(chairs > 0){ chairs--;    //找个凳子 V(mutex);    //释放mutex V(ready);    //多了个准备好的顾客 P(finish);   //等待空闲的理发师来给理发    }else{ V(mutex);    //释放mutex    }}

        读者-写者问题

        问题定义：读者和写者共同访问一个共享文档，访问需遵循如下规律：

        多个读者可以同时读文件

        一次只能有一个写者写文件

        写者写文件时不能有读者正在读文件

 情况一：读者优先算法：

int readernumber = 0;semaphore rmutex = 1;    //读者需互斥访问readernumber对其进行修改semaphore mutex = 1;     //保证对数据区的写互斥writer(){    while(1){ P(mutex) write() V(mutex)    }}reader(){    while(1){ P(rmutex)  // 申请修改readernumber  if(readernumber == 0){    /* 如果此时readernumber为0，说明第一个读者刚要访问该共享文件，因此要禁止后面到来的写者进入，而若此前已有读者正在访问过程中，那么写者已经被阻塞      同时，如果已有写者进入，那么读者会被阻塞*/     P(mutex) } readernumber++    // 读者数量加1 V(rmutex)  // 释放readernumber权限，允许其他读者访问之 read()     // 进行读操作 P(rmutex)  // 再次申请readernumber修改权限 readernumber--    // 读者数-1 if(readernumber == 0){     /** 如果是最后一个读者退出文件，释放mutex，允许后续写者进入   */     V(mutex) } V(rmutex)  // 释放readernumber权限，允许其他读者访问之    }}

        这种情况是利于读者访问的，因为如果当前有两个读者进程在读文档，一个写者进程被阻塞，此时再来一个读者进程，那么这个读者进程将被允许读文档，而阻塞的写者进程只能在所有读者都退出进程才能被访问。

情况二：写者优先算法

semaphore rmutex = wmutex = r = w = 1int readercount = 1int writercount= 1reader(){    while(1){ P(r) P(rmutex) if(readercount == 0){     P(w) } readercount++ V(rmutex) V(r) read() P(rmutex) if(readercount == 1){     V(w) } readercount-- V(rmutex)    }}writer(){    while(1){ P(wmutex) if(writercount == 0){     P(r) } writercount++ V(wmutex) P(w) write() V(w) P(wmutex) writercount-- if(writercount == 0){     V(r) } V(wmutex)    }}

在本例中信号量来控制写者进程的进入，若有写着存在则占用该信号量，阻止后续读者进如临界区，而w信号量代表对临界区进行写操作的权力，当有读者占用临界区时，占用信号量w以阻止写者进行写操作。本解法的rmutex和wmutex信号量表示对读者、写者计数器互斥操作控制的信号量。

情况三：读者写者公平

semaphore mutex = rmutex = wmutex = 1int readercount = 0reader(){    while(1){ P(wmutex) //检测是否有写者 P(rmutex) if(readercount == 0){     P(mutex) } readercount++ V(rmutex) //恢复rmutex V(wmutex) //恢复wmutex read() P(rmutex) //申请readercount使用 readercount-- if(readercount == 0){     V(mutex)     //释放数据区，允许写者进入 } V(rmutex)    }}writer(){    while(1){ P(wmutex) //检测是否有其他写者存在，无写者时进入 P(mutex)  //申请数据区访问 write()   //进行写操作 V(mutex)  //释放数据区，允许其他进程写 V(wmutex) //恢复wmutex    }}