OS——经典进程同步问题

OS——经典进程同步问题

在之前的章节我们介绍过，实现进程的同步与互斥可以有两种方法，即硬件同步机制与信号量机制，其中信号量机制又有整型信号量机制以及记录型信号量机制，而我们今天要介绍的两个问题，就是采用信号量机制的方法最终实现了进程间的同步与互斥。

生产者 - 消费者问题

问题描述

大概就是生产者生产的产品供消费者使用，为了让生产和消费并发的执行，就设置了一个有n个缓冲区的缓冲池，生产者生产的产品扔进去，消费者从缓冲池中取出来用。

但是我们注意到，缓冲池内只有n个缓冲区，也就是有限的，所以我们就可以得出来4个约束条件

约束条件

• 有空生产者就可以放
• 没空生产者就不能放，要等消费者取走一个腾出空间才能放
• 有东西消费者就可以取
• 没东西消费者就不能取，要等生产者放进去一个才能取

各进程间的关系

知道了场景以及约束条件，我们就可以来盘一盘每个进程之间的关系了，经过我们细心盘完之后，发现了以下三点

• 互斥：每个进程互斥的访问缓冲池
• 同步
  • 缓冲池满后：生产者要等消费者取走再放
  • 缓冲区空时：消费者要等生产者放完再取

对于第一点互斥，在生产进程时：如果两个生产进程同时对一片缓冲池进行生产，那么第二次生产结果就会覆盖第一次生产的结果。在消费进程时：如果两个消费进程对一片缓冲区消费，则第二个消费进程将会取不到产品。

如何设置信号量

知道了进程间的互斥或同步的关系，我们就可以来设置信号量实现这些关系。

互斥实现

在之前我们讲过，对于实现互斥我们可以一个信号量mutex，初值为1，使用缓冲区前执行P操作，使用完后执行V操作即可

同步实现

同样在之前讲过，对于实现进程间的同步，我们可以通过设置信号量后，在前操作执行后执行V操作，在后操作执行前执行P操作。因为这里涉及到两个同步关系，所以我们设置两个信号量：

• 设置信号量full ，初值为0，表示当前缓冲池中有产品的缓冲区个数。
• 设置信号量empty，初值为n，表示当前缓冲池无产品的缓冲区个数

生产进程

• 在进程执行前，执行P(empty)，消耗一个空闲缓冲区，若empty<0，就表示没有空闲资源了，此时生产进程就会阻塞自己。
• 在进程执行后，执行V(full)，增加一个产品

消费进程：

• 在进程执行前，执行P(full)，消耗一个产品，如果full<0，就表示没有产品消耗了，此时消费进程就会阻塞自己，直到生产进程执行一个V(full)操作才被唤醒
• 在消费执行后，执行V(empty)，增加一个产品

代码表示

smaphore empty = n;
smaphore full = 0;
smaphore mutex = 1;

producer(){
    while(1){
        生产一个产品;
        P(empty);
        P(mutex);
        把产品放进去;
        V(mutex);
        V(full);
    }
}

consumer(){
    while(1){
        P(full);
        P(mutex);
        取走一个产品;
        V(mutex);
        V(empty);
        使用产品;
    }
}

我们同时可以发现：实现互斥是同一进程中执行PV操作，实现同步是其中一个进程执行P，另一个进程执行V

思考问题

能否将生产进程中的P(mutex)放在P(empty)的前面，将消费进程中的(mutex)放在P(full)的前面

首先这是不能的，再来说说为什么：如果生产者先使用P(mutex)操作占用了缓冲区，如果此时缓冲区满了，你就会阻塞自己，一直等消费者取走东西，但此时的消费进程，会执行P(mutex)一直失败，因为你生产者一直占着呢。这样就会两者互相等待，即死锁

能否将生产进程中的“生产一个产品”和消费进程中的“消费产品”放入缓冲区内完成？

也就是说生产者先占用缓存区，在生产，再放进去。在功能实现上，也并不会造成错误，但我们应该**减少使用缓冲区的时间，把一些不必要的操作放在外部执行，以提高并发度。

读者 - 写者问题

问题描述

有一个数据区被多个用户共享，用户大概可以分为读者和写者，我们规定：读者只读，且允许多个读者同时读，写者只写，但只允许一个写者写，且写者在写的时候，读者不能读。6

约束条件

在读完问题后，约束条件大概就出来了

• 多个读者可以同时读
• 一个时刻只能一个写者写
• 如果写者正在写，读者就不能读

进程间的关系

有了约束条件，我们就可以来盘进程之间的关系。

• 互斥
  • 写和写之间是互斥的，一次只能一个人写
  • 写和者之间是互斥的，写者在写时读者不能读
  • 读进程之间不存在互斥，因为允许多个人同时读

信号量的设置及代码表示

• 设置信号量rw，初值为1，实现对数据区的互斥访问。那么我们可以脑侧到，在写操作中，因为各写进程是互斥的，所以会在进程中依次执行PV操作，在读操作中，因为读操作和写操作也是互斥的，所以读操作中也会依次执行PV操作。那么问题就来了：读进程之前不互斥呀，在第一个读进程中执行P操作后，执行V操作前，我第二个读进程怎么读？，那就要引入下一个变量了。
• 设置整型变量count = 0，来记录当前有几个在读，那么在读进程中，我们只需要在第一个读进程开始前执行P，最后一个读进程结束后执行V，问题就解决了。

smaphore rw = 1;

write(){
    while(1){
        P(rw);
        写进去;
        V(rw);
    }
}
read(){
    while(1){
       if(count==0)
           P(rw);//第一个读进程加锁
        count++;
        读一读;
        count--;//一个进程读完之后，使count-1，表示读进程数-1
        if(count==0)
            V(rw);//最后一个读进程解锁
    }
}

在进行了上面的操作后，看似非常合理，但还有个问题：如果两个读进程并发执行，在第一个读进程执行P(rw)后，第二个进程执行P(rw)可能被阻塞，原因就在于count变量的检查和更改不能一气呵成。那么，我们就想办法让count的检查以及更改过程中不被打扰

• 设置信号量mutex = 1，表示对count的互斥访问。把count的检查以及修改操作放入PV里面，即：

read(){
    while(1){
       P(mutex);
       if(count==0)
           P(rw);
        count++;
        V(mutex);
        读一读;
        P(mutex);
        count--; 
        if(count==0)
            V(rw); 
        V(mutex);
    }
}

在进行完上面的操作之后，我们已经满足了问题的要求，但现在又出现了一个问题：如果一直有新的读进程源源不断的读数据，写操作啥时候才能执行啊？就出现了写者饥饿的情况。所以为了解决这个问题，我们推出了写优先方法，上面的实现也称之为读优先方法。

写优先方法

目的：在读进程执行时有写操作想执行，则先执行完本个读进程，再去执行写进程，不管有多少个读进程去读这个数据，在执行完本个读进程后，就转去执行写进程。

解决方法：设置新的信号量w = 1,加在以下位置：

smaphore empty = n;
smaphore full = 0;
smaphore mutex = 1;
smaphore w = 1;

write(){
    while(1){
        P(w)//
        P(rw);
        写进去;
        V(rw);
        V(w);//
    }
}

read(){
    while(1){
       P(w);//
       P(mutex);
       if(count==0)
           P(rw);
        count++;
        V(mutex);
        V(w)//
        读一读;
        P(mutex);
        count--; 
        if(count==0)
            V(rw); 
        V(mutex);
    }
}

• 这样对于写者与写者之间，以及读者与读者之间：和之前无差别，只是执行时多了一个上锁以及解锁的过程。
• 对于 写者1->读者1，写者在写之前执行P(w)，在执行V(w)前，读者的读操作都会一直被阻塞。写者写完后执行V操作，读者就开始读，也就是说读者和写者之间的互斥也没有受到影响。
• 对于读者1->写者1->读者2：也就是我们刚刚提到的写者可能饥饿的情况。步骤为：读者1先执行P(w)操作，如果期间写者1想执行写操作，就会在读者1读完之后执行V(w)后就可以执行了，不必再等读者2读完，这也就是实现了写优先。
• 对于写者1->读者1->写者2：步骤为：写1在执行P(w)操作后，读1想读，被阻塞，待写1写完之后执行V(w)后，会优先执行读进程，在读进程的执行过程中，如果写进程2想执行写操作，需等待读进程1读完。也就是说，写优先并不是绝对的写优先，而是相对公平的先来先服务 原则。

哲学家就餐问题

问题描述：

一个桌子上坐着5个哲学家，每个哲学家两侧都有一个筷子，桌子中间放着饭菜。哲学家的行为描述为：思考-饥饿-吃饭-思考。饥饿时需要拿起两个筷子才能进餐，如果筷子在别人手上，就需要等别人吃完放下筷子。这里直接偷王道的一张图了：

约束条件

通过描述我们可以知道，哲学家在思考时互不影响他人，在进餐时每个人和旁边的两个人都存在互斥关系，因为每个人要拿起两个筷子才能吃饭。我们把筷子作为临界资源，也就是每个人需要同时持有两个临界资源才能开吃

信号量设置

我们定义互斥信号量数组chopstick[0,1,2,3,4]，用于表示对5个筷子的互斥访问，哲学家标号为0,1,2,3,4，其中哲学家i左边的筷子为i，右边的筷子为(i+1)%5。设置完后我们可以如下表示：

semaphore chopstick[5]={0,1,2,3,4};
pi(){//哲学家i的进程
    while(1){
        P(chopstick[i]);
        P(chopstick[i+1]%5);
        吃饭;
        V(hopstick[i]);
        V(hopstick[i+1]%5);
        思考；
    }
}

但这样设置有个问题：若5个哲学家同时想吃饭，每位哲学家都拿起自己左边的筷子，再去拿右边的筷子时发现已经被拿了，就需要一直等待，就成了：每个哲学家都等自己右边的哲学家放下筷子，形成死锁。下面就来讲解如何解决死锁？

• 法一：奇数号哲学家先拿左边，再拿右边，偶数号哲学家相反

semaphore chopstick[5]={0,1,2,3,4};
pi(){
    while(1){
        if(i%2==0){
            P(chopstick[i+1]%5);
            P(chopstick[i]);
        }
        else{
            P(chopstick[i]);
            P(chopstick[i+1]%5);
        }
        吃饭;
         V(chopstick[i]);
         V(chopstick[i+1]%5);
    }
}

• 法二：最多允许4个人同时拿筷子

原理就是5个人同时拿筷子会死锁，那就让最多4个人拿，这样一次总会有一个哲学家能吃到饭。

smaphore count == 4;控制吃饭人数
semaphore chopstick[5]={0,1,2,3,4};
pi(){
	while(1){
        P(count);
        P(chopstick[i]);
        P(chopstick[i+1]%5);
        吃饭;
        V(hopstick[i]);
        V(hopstick[i+1]%5);
        V(count);
        思考；
        
    }
}

• 法三：设置mutex=1，使哲学家拿筷子这件事互斥的进行。

semaphore mutex = 1;
semaphore chopstick[5]={0,1,2,3,4};
pi(){
    while(1){
        P(mutex);
		P(chopstick[i]);
        P(chopstick[i+1]%5);
        V(mutex);
        吃饭;
        V(chopstick[i]);
        V(chopstick[i+1]%5);
        思考;
    }
}

这样就保证了一个人拿筷子拿到一半时被阻塞，在一个人拿筷子时，不会有别人拿筷子。原理就是既然可能出现同时拿筷子而导致的死锁，那就将拿筷子这个动作从头到尾用一个信号量锁起来即可。