Classic IPC problem

Classic IPC problem

1. The Dining Philosophers Problem

There are two alternate periods of activity in the life of a philosopher: eating and thinking. When a philosopher feels hungry, he tries to take two forks on his left and right, one at a time, but in no particular order. If you successfully get two forks, start eating, and after eating, put down your forks and continue thinking. The key question is: Can every philosopher write a
program describing his behavior, and it will never deadlock?

Insert picture description here
#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)		//哲学家编号:从0到N-1
{
    while(true){	//无限循环
        
    }
}

void take_forks(int i)		//哲学家编号,从0到N-1
{
    //下面的这组down up操作是对test进行保护的
    down(&mutex);
    state[i] = HUNGRY;
    test(i);
    up(&mutex);
    down(&s[i]);		//如果得不到需要的叉子,那么阻塞
}

void put_forks(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]);
    }
}

2.The Readers and Writers Problem

Simultaneous reading by multiple readers: acceptable

One writer is writing, readers want to read, other writers want to write: none is allowed

typedef int semaphore;
semaphore mutex = 1;	//控制对rc的访问
semaphore db = 1;		//控制对数据库的访问
int rc = 0;

void reader(void)
{
    while(TRUE){
        down(&mutex);	//获得对rc的互斥访问
        rc = rc + 1;	//读者数+1
        if(rc == 1)down(&db);	//如果是第一个读者,那么进入写,获得了数据库的访问,那么写者将不再能进入数据库写数据
        //如果此时已经有写者在写了,第一个读者将会阻塞在这里,后续的读者将会阻塞在第9行
        up(&mutex);			//其他的读者就可以进入的
        
        read_data_base();		//访问数据
        
        down(&mutex);			//读者读完再次进入关键区,获得rc的访问权
        rc = rc - 1;			//读者读完,读者数-1
        if(rc == 0)up(&db);		//如果这是最后一个读者,那么唤醒可能阻塞的写者
        up(&mutex);			    //离开对rc的互斥访问
        use_data_read();		//非临界区
    }
}

void writer(void)
{
    while(true){
        think_up_data();	//非临界区
        down(&db);			//写者写的时候任何线程都不能进入
        write_data_base();		//在关键区内进行写操作
        up(&db);			//写完,释放互斥访问
    }
}

​ The rc and database access here are both key areas, and mutually exclusive access is required, so once these two resources are to be modified, the corresponding down and up operations must be performed. So use a mutex to achieve mutually exclusive access to rc, and use db to achieve mutually exclusive access to data_base. In particular, when there is no writer, access to data_base between readers does not need to be mutually exclusive.

​ The mutually exclusive access of rc is relatively simple. Here is a detailed description if(rc == 1)down(&db);of the role of line 11 : here is not only for the first reader to enter, but subsequent writers cannot enter the key area again, but the second and third one will be learned later. This is not affected because rc==1 is not satisfied; more importantly, this code realizes that when the writer accesses the key area, the reader will no longer be able to access the key area-if there are readers later, the first reader will Is blocked on line 11 down(&db), and the second reader, the third reader will be up(&mutex)blocked on line 9 because the first reader cannot proceed down(&mutex). So 11 lines of code are the key to understanding this problem.

​ In the above program, multiple readers are allowed to access the database together. At the same time, the above writing method is also the priority of readers. As long as there are readers in the database, even if a writer is waiting in front of the subsequent readers, then the subsequent readers can access the database, but the writer cannot. There are readers in the database, and the writer has no chance to write. If the reader’s time to read> the arrival time, for example, it takes 5 seconds for the reader to finish reading, and the next reader arrives at a frequency of one every 2s, then the waiting writer will be There is never a chance to write.