ClarkCheung
ClarkCheung

I'm writing something about Computer Science, especially some basic knowledges.

操作系统:经典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进食
}

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

CC BY-NC-ND 2.0 版权声明

喜欢我的文章吗?
别忘了给点支持与赞赏,让我知道创作的路上有你陪伴。

加载中…

发布评论