操作系统：经典进程同步问题之生产者-消费者问题、读者-写者问题、哲学家进餐问题

柔光的暖阳◎ 2022-03-29 02:14 582阅读 0赞

在进程同步中，经典的同步问题有：生产者-消费者问题、读者-写者问题、哲学家进餐问题。

### 一、生产者与消费者问题： ###

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

**1、使用信号量实现生产者-消费者问题：**

> **down** : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
> 
> **up** ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

#define N 100
    typedef int semaphore;
    semaphore mutex = 1;
    semaphore empty = N;
    semaphore full = 0;
    
    void producer() {
        while(TRUE) {
            int item = produce_item();
            down(&empty);
            down(&mutex);
            insert_item(item);
            up(&mutex);
            up(&full);
        }
    }
    
    void consumer() {
        while(TRUE) {
            down(&full);
            down(&mutex);
            int item = remove_item();
            consume_item(item);
            up(&mutex);
            up(&empty);
        }
    }

**2、使用管程实现生产者-消费者问题：**

>  // 管程  
>  monitor ProducerConsumer  
>     condition full, empty;  
>     integer count := 0;  
>     condition c;
> 
>     procedure insert(item: integer);  
>     begin  
>         if count = N then wait(full);  
>         insert\_item(item);  
>         count := count + 1;  
>         if count = 1 then signal(empty);  
>     end;
> 
>     function remove: integer;  
>     begin  
>         if count = 0 then wait(empty);  
>         remove = remove\_item;  
>         count := count - 1;  
>         if count = N -1 then signal(full);  
>     end;  
> end monitor;
> 
> // 生产者客户端  
> procedure producer  
> begin  
>     while true do  
>     begin  
>         item = produce\_item;  
>         ProducerConsumer.insert(item);  
>     end  
> end;
> 
> // 消费者客户端  
> procedure consumer  
> begin  
>     while true do  
>     begin  
>         item = ProducerConsumer.remove;  
>         consume\_item(item);  
>     end  
> end;

### 二、读者-写者问题： ###

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count\_mutex 用于对 count 加锁，一个互斥量 data\_mutex 用于对读写的数据加锁。

typedef int semaphore;
    semaphore count_mutex = 1;
    semaphore data_mutex = 1;
    int count = 0;
    
    void reader() {
        while(TRUE) {
            down(&count_mutex);
            count++;
            if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
            up(&count_mutex);
            read();
            down(&count_mutex);
            count--;
            if(count == 0) up(&data_mutex);
            up(&count_mutex);
        }
    }
    
    void writer() {
        while(TRUE) {
            down(&data_mutex);
            write();
            up(&data_mutex);
        }
    }

### 三、哲学家进餐问题： ###

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

![a9077f06-7584-4f2b-8c20-3a8e46928820.jpg][]

下面是一种错误的解法，考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。

#define N 5
    
    void philosopher(int i) {
        while(TRUE) {
            think();
            take(i);       // 拿起左边的筷子
            take((i+1)%N); // 拿起右边的筷子
            eat();
            put(i);
            put((i+1)%N);
        }
    }

为了防止死锁的发生，可以设置两个条件：

*  必须同时拿起左右两根筷子；
 *  只有在两个邻居都没有进餐的情况下才允许进餐。

#define N 5
    #define LEFT (i + N - 1) % N // 左邻居
    #define RIGHT (i + 1) % N    // 右邻居
    #define THINKING 0
    #define HUNGRY   1
    #define EATING   2
    typedef int semaphore;
    int state[N];                // 跟踪每个哲学家的状态
    semaphore mutex = 1;         // 临界区的互斥
    semaphore s[N];              // 每个哲学家一个信号量
    
    void philosopher(int i) {
        while(TRUE) {
            think();
            take_two(i);
            eat();
            put_two(i);
        }
    }
    
    void take_two(int i) {
        down(&mutex);
        state[i] = HUNGRY;
        test(i);
        up(&mutex);
        down(&s[i]);
    }
    
    void put_two(i) {
        down(&mutex);
        state[i] = THINKING;
        test(LEFT);
        test(RIGHT);
        up(&mutex);
    }
    
    void test(i) {         // 尝试拿起两把筷子
        if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
            state[i] = EATING;
            up(&s[i]);
        }
    }

文章转自：[https://github.com/CyC2018/CS-Notes/blob/master/docs/notes/%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F.md\#%E7%B3%BB%E7%BB%9F%E8%B0%83%E7%94%A8][https_github.com_CyC2018_CS-Notes_blob_master_docs_notes_E8_AE_A1_E7_AE_97_E6_9C_BA_E6_93_8D_E4_BD_9C_E7_B3_BB_E7_BB_9F.md_E7_B3_BB_E7_BB_9F_E8_B0_83_E7_94_A8]

[a9077f06-7584-4f2b-8c20-3a8e46928820.jpg]: https://github.com/CyC2018/CS-Notes/raw/master/docs/notes/pics/a9077f06-7584-4f2b-8c20-3a8e46928820.jpg
[https_github.com_CyC2018_CS-Notes_blob_master_docs_notes_E8_AE_A1_E7_AE_97_E6_9C_BA_E6_93_8D_E4_BD_9C_E7_B3_BB_E7_BB_9F.md_E7_B3_BB_E7_BB_9F_E8_B0_83_E7_94_A8]: https://github.com/CyC2018/CS-Notes/blob/master/docs/notes/%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F.md#%E7%B3%BB%E7%BB%9F%E8%B0%83%E7%94%A8