操作系统：经典IPC问题

本文将介绍两个经典的同步问题：读者/写者问题和哲学家就餐问题。

读者/写者问题

读者/写者问题是一类在共享数据访问中产生的问题。在这个问题中，我们有两种类型使用者。一类是只需要读取数据的读者，一类是需要读取和修改数据的写者。对于这个问题，可以有读者优先和写者优先的解决办法。下面我们给出一种读者优先的解决办法：

typedef int semaphore;
semaphore mutex = 1; //锁, 控制对rc的访问
semaphore db = 0; // 控制对数据库的访问
int rc  = 0; //正在读或者即将读的进程数目

void reader(){

while(TRUE){
down(&mutex); //上锁，获得对rc的互斥访问权.
rc = rc+1; // 新读者
if(rc == 1) down(&db); //如果这是第一个读者，获取数据库访问权
up(&mutex);//解锁.
read_data_base(); //读者执行读操作
down(&mutex);
rc = rc - 1;
if(rc == 0) up(&db);//如果这是最后一个读者，允许写者写。
up(&mutex);
use_data_read();//临界区外的读
}
}

void writer(){
while(TRUE){
think_up_data();//临界区外写。
down(&db);//获取互斥访问
write_data_base();//更新数据
up(&db);
}
}

通过在读者进程中对写者信号量的限制，只有当没有读者需要访问数据库的时候，写者才能对数据库进行写操作。如果读者连绵不断，那写者将永远没有机会进行更新。

哲学家就餐问题

1965年，Dijkstra提出并解决了哲学家就餐问题。问题中，五个哲学家围坐在一张圆桌边，每个哲学家面前有一盘面条，吃面条需要两把叉子，每个哲学家的左手边和右手边各有一把叉子。哲学家有两种活动：吃饭和思考。哲学家饿了的时候，他就要拿两把叉子开始吃饭，吃完了继续思考。但如果哲学家没得到叉子，他会一直等待。问题在于，如何为每个哲学家编写一段描述其行为的程序，且绝不会死锁？

下面是一种解决方法：

#define N 5 //哲学家的数量
#define LEFT (i+N-1)%N //i的左邻居编号
#define RIGHT (i+1)%N //i的右邻居编号
#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){ //i为哲学家编号，范围从0到N-1.
while(TRUE);
}

void take_folks(int i){
down (&mutex);
state[i] = HUNGRY; //记录此哲学家的饥饿状态
test(i); //试图获取两把叉子
up(&mutex);
down(s[i]); //如果得不到需要的叉子，阻塞。
}

void put_folks(int 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){
//哲学家i饥饿，且哲学家i的左右邻居没有在进食
state[i] = EATING; //哲学家i的状态置为进食
up(&s[i]);//哲学家i进食
}

这种方法的思路是，哲学家进食之前先检测左右邻居是不是在进食，如果左右邻居没有在进食，就可以进行一个互斥的进食过程。如果左右邻居已经在进食了，那该进程自我阻塞，直到左右邻居进食完毕将其唤醒。