生产者消费者模型

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者 进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）

生产者、消费者共享一个初始为空、大小为n的缓冲区。

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。（同步关系）

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。（同步关系）

缓冲区是临界资源，各进程必须互斥地访问。（互斥关系）

请用代码实现上述模型。

题目中存在2个同步关系和1个互斥关系，因此需要3个信号量实现：

semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量，表示空闲缓冲单位的数量
semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲单位的数量

producer(){
    while(1){
        生产1个产品;
        P(empty);    // 消耗一个空闲缓冲单位
        P(mutex);	  // 访问缓冲区
        把产品放入缓冲区;
        V(mutex);
        V(full);	// 增加一个产品
    }


consumer(){
    while(1){
        P(full);    // 消耗一个缓存区中的产品
        P(mutex);	  // 访问缓冲区
        从缓冲区取出产品;
        V(mutex);
        V(empty);	// 增加一个可用缓冲区单位
        使用产品;
    }
}

 

问题1：producer()中能否改变 P(empty) 和 P(mutex)的顺序？

答：不可以，会发生死锁。

若此时缓冲区内已经放满产品，则 empty=0，full=n。

则生产者进程执行① 使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。

由于生产者阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，即生产者还没 释放对临界资源的“锁”，因此消费者也被阻塞。

这就造成了生产者等待消费者消费以腾出空闲单元，而消费者又等待生产者释放临界区，生 产者和消费者循环等待被对方唤醒，出现“死锁”。

因此，实现互斥的P（wait）操作一定要在实现同步的P（wait）操作之后。

 

问题2：producer()中能否改变V(full) 和 V(mutex)的顺序？

答：V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

 

问题3：能否把 “使用产品;” 放到PV操作之间？

答：可以是可以，但是会使临界区代码增多，临界区是只允许串行的代码区，因此会导致并发度降低，建议极可能将无需互斥访问的代码放到临界区之外。

 

 

多生产者-多消费者模型

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放 橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才 可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。

用PV操作实现上述过程。

1、首先4个人，是4个进程；

2、父母只能在盘子有空间的时候放水果，否则阻塞。需要同步信号量plate表示盘子是否为空来同步父母的放水果操作，对应的V(plate)操作放在子女进程中取完水果后执行，唤醒父母。

3、子女需要两个同步信号量apple和orange表示是否有苹果和橘子来同步子女的拿水果操作。对应的V操作在父母放完水果后执行，唤醒子女。

4、互斥访问盘子资源需要一对PV操作。

 

代码如下：

orange = 0;	// 盘子中的橘子数	
apple = 0;		// 盘子中的苹果数
empty = 1;		// 盘子是否为空
mutex = 1;

father(){
    while(1){
        生产苹果;
        P(empty);	// 如果盘子不为空则阻塞，为空则将empty置为非空
        P(mutex);
        苹果放入盘子;
        V(mutex);
        V(apple);	// 通知女儿有苹果了
    }
}

mother(){
    while(1){
        生产橘子;
        P(empty);
        P(mutex);
        橘子放入盘子;
        V(mutex);
        V(orange);
    }
}

son(){
    while(1){
        P(orange)	// 检查盘子中是否有橘子，并减少盘子中的一个橘子。没有则阻塞
        P(mutex);
        从盘子拿走橘子;
        V(mutex);
        V(empty);
    }
}

daughter(){
    while(1){
        P(apple)
        P(mutex);
        从盘子拿走苹果;
        V(mutex);
        V(empty);		// 通知爸爸盘子空了，可以继续放苹果
    }
}

问题1：可不可以不用互斥信号量mutex？

答：在本例中可以，因为缓冲区大小为1，在任何时刻，apple、orange和empty这三个同步信号量最多只有一个是1，因此任意时刻最多只有一个进程的P操作不会被阻塞，其他进程都会被阻塞，也就相当于是串行操作了。

如果缓冲区大小为2，则必须要用互斥信号量，否则父母可能同时访问临界资源导致数据混乱。

 

 

读者-写者问题

情景如下：

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致 数据不一致的错误。

因此要求：①读读可并发；②写写互斥；③读写互斥；④写读互斥。

读者-写者问题和生产者-消费者问题的区别在于，前者的读读是可以并发的，读是不会改变容器内的数据的，后者的消费者不能并发消费容器内的产品，因为消费会修改容器内的产品（即产品-1）。

 

分析：本题目是一个纯互斥的问题，不涉及同步（因为没有必须先读后写，或者先写后读的要求）。

其实 后面3个要求比较容易解决，直接用一个互斥量锁住读操作和写操作的临界区即可，如何解决读读并发是难点。

读者-写者问题可以使用一个互斥信号量，一个计数器实现。

可以用一个计数器count记录当前执行读操作的读进程有多少个，只有第一个读进程才需要读前加锁，count > 0 时，说明有其他读进程在读，本读进程就不上锁了。

这就相当于，所有读进程可以共同持有一把锁，而写进程不能共享一把锁，只能单独使用这把锁。

 

代码实现：

rw_lock = 1;	// 互斥量，保证读写数据是串行的
count = 0; 	// 当前执行读操作的读进程有多少个
count_lock = 1;		// 互斥量，保证count变量的访问是串行的

reader(){
    while(1){
        P(count_lock)
        if(count==0){
            P(rw_lock)    // 没有读进程上锁，则本读进程上锁
        }
        count++
        V(count_lock)
        
        读数据;
        
        P(count_lock)
        count--
        if(count==0){
            V(rw_lock)    // 如果本进程是最后一个持有锁的读进程，则解锁
        }
        V(count_lock) 
    }
}

writer(){
    while(1){
        P(rw_lock);	// 申请锁，上锁
        写数据;
        V(rw_lock);	// 释放锁，解锁
    }
}

需要注意：count的检查和修改是原子性的。否则，读进程1执行完 if(count==0)后对文件上锁，没来得及执行 count++就切换到了读进程2，那么读进程2也会上锁，于是读读互斥。

 

解决写饥饿问题

问题：按照上述代码的逻辑，如果有足够多的读进程，他们执行while循环不停地进行读操作，那么 rw_lock 会一直被读进程们持有，导致写进程一直等待，无法写入数据。如何解决写进程饥饿问题？

比如，有3个进程并发执行，开始执行的顺序是读进程1->写进程1->读进程2。之所以写进程1会饥饿是因为写进程1被P(rw_lock)阻塞住了，读进程1在执行count--之前，读进程2就执行了count++，导致读进程1无法释放 rw_lock。

如果能按进程先来后到的顺序公平的获得rw_lock就可以破解饥饿，例如写进程1比读进程2先来，写进程1就优先获得rw_lock的权利，因此写进程1可以先预订读进程1正在持有的rw_lock，即用一个互斥量w锁住rw_lock，只有进程拿到rw_lock锁之后才能释放w。可以将 P(w)理解为进程在申请获取rw_lock锁的权利。

。

如下所示：

rw_lock = 1;	// 互斥量，保证读写数据是串行的
count = 0; 	// 当前执行读操作的读进程有多少个
count_lock = 1;		// 互斥量，保证count变量的访问是串行的
w = 1;    // 互斥量，用来锁住rw_lock

reader(){
    while(1){
        P(w);   // 申请持有rw_lock锁的权利
        P(count_lock)
        if(count==0){
            P(rw_lock)    // 没有读进程上锁，则本读进程上锁
        }
        
        count++
        V(w);    // 拿到rw_lock锁之后才释放w，必须放在count++之后，因为对于读进程而言，count++才算让读进程拿到了rw_lock锁
        V(count_lock)
        
        读数据;
        
        P(count_lock)
        count--
        if(count==0){
            V(rw_lock)    // 如果本进程是最后一个持有锁的读进程，则解锁
        }
        V(count_lock) 
    }
}

writer(){
    while(1){
        P(w);       // 申请持有rw_lock锁的权利
        P(rw_lock);	// 申请锁，上锁
        V(w);       // 拿到rw_lock锁之后才释放w
        写数据;
        V(rw_lock);	// 释放锁，解锁
    }
}

 

下图为官方答案