进程同步经典问题

生产者-消费者问题

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

因为缓冲区属于临界资源，因此需要使用一个互斥量 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);
	}
}

读者-写者问题

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

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

读者优先：

当读者进行读取时，如果后面一直有读者进入，那么写者就会阻塞，直到所有读者完成之后，写者才可以进入。

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void writer(){
    while(TRUE){
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

void reader(){
    while(TRUE){
        down(&count_mutex);
        if(count==0)
            down(&data_mutex);//如果是第一个读者，阻塞写者
        count++;
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count==0)
            up(&data_mutex);//最后一个读者出来，释放写者
        up(&count_mutex);
    }
}

写者优先：

置一个WriterMutex信号量来实现优先读。我们可以看到，当有写者进入时，通过P(WriterMutex)阻塞了读者

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
semaphore write_mutex = 1;//实现写者优先
int count = 0;

void writer(){
    while(TRUE){
        down(&write_mutex);
        down(&data_mutex);
        write();
        up(&data_mutex);
        up(&write_mutex);
    }
}

void reader(){
    while(TRUE){
        down(&write_mutex);//无写者进入时
        down(&count_mutex);
        if(count==0)
            down(&data_mutex);//如果是第一个读者，阻塞写者
        count++;
        up(&write_mutex);//恢复对共享资源的访问
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count==0)
            up(&data_mutex);//最后一个读者出来，释放写者
        up(&count_mutex);
    }
}

哲学家进餐问题

五个哲学家（A~E）围着一张圆桌就餐，他们每个人面前都有一盘通心粉。由于通心粉很滑，所以需要两只筷子才能夹住，但每两个盘子之间只放着一只筷子，如下图。
哲学家只有两个动作：要么就餐，要么思考。而且他们之间从不交谈。
当一个哲学家饿了的时候，就拿起盘子左右两边的筷子开始就餐（不能同时拿起两只筷子）。就餐完以后，就把筷子放回盘子左右，继续思考。
由于他们之间互不交谈，所以很容易出现“死锁”：假如每个人都拿着左边的筷子，则所有人都在等右边的筷子，谁都吃不了。
在这里插入图片描述
为了防止死锁的发生，可以设置两个条件：

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

#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://blog.csdn.net/Sunflowerfiona/article/details/52756819）