No43.进程间的同步与互斥---哲学家问题

2019-12-22  本文已影响0人  赫尔特

文章目录

\color{orange}{1.水果问题}
\color{red}{2.公交车问题}
\color{green}{3.哲学家问题}
\color{pink}{4.读者写者问题}
\color{purple}{5.总结}

1.水果问题

semaphore empty=1;  //判断盘子是否为空的信号量
semaphore apple=0,banana=0;   //是否有苹果，香蕉的信号量

Father:
    P(empty)
    向盘子里放苹果;
    V(apple);
Mother:
    P(empty)
    向盘子里放香蕉;
    V(banana);
Daughter:
    P(apple)
    取盘子里的苹果;
    V(empty);
Son:
    P(banana)
    取盘子里的香蕉;
    V(empty);

用一个信号量对盘子里的水果个数进行计数，用另一个信号量用来控制对盘子的互斥访问（因为每次只能放和取出一个水果），还有苹果和香蕉的信号量

semaphore empty=2;  //对盘子里的水果个数进行计数
semaphore mutex=1;  //控制对盘子的互斥访问
semaphore apple=0,banana=0;   //是否有苹果，香蕉的信号量

Father:
    P(empty);
    P(mutex);
    向盘子里放苹果;
    V(mutex);
    v(apple);
Mother:
    P(empty);
    P(mutex);
    向盘子里放香蕉;
    V(mutex);
    v(banana);
Daughter i(i=1,2):
    P(apple);
    P(mutex);
    取盘子里的苹果;
    V(mutex);
    v(empty);
Son i(i=1,2):
    P(banana);
    P(mutex);
    取盘子里的香蕉;
    V(mutex);
    v(empty);

2.公交车问题

graph LR
A[司机] --> B[启动车辆]
B --> C[正常行驶]
C--> D[到站停车]

E[售票员] --> F[关车门]
F --> G[售票]
G--> H[开车门]

规定：只有当售票员关车门后司机才能启动车辆，只有当司机停车门后售票员才能开车门。用P、V操作实现两人正确活动的程序。

semaphore start=0;    //可以开车的信号量
semaphore open=0;     //可以开门的信号量

司机:
P(start);
启动车辆;
正常行驶;
到站停车;
V(open);

售票员:
关车门;
V(start);   //因为只有关车门后才能启动车辆
售票;
P(open);
开车门;

3.哲学家问题

下面这个代码就会产生五个人都没得吃的情况：

take_fork()和put_fork()函数内部都有P,V操作，也就是说同一个叉子不能被两个人同时拿起

#define N 5

void philosopher(int i)   //第i个哲学家
{
while(true){
think();    //我要思考问题！
take_fork();    //准备要吃饭了，拿起第i个叉子，
//假设哲学家被编好号，这个i就是哲学家的编号，
//它对应的是抓起左边的叉子
take_fork((i+1)%N);    //抓起右边的叉子
eat();    //我开动了
put_fork(i);    //放下左边的叉子
put_fork((i+1)%N);  //放下右边的叉子
}
}

解决办法有很多，比如下面四种都可行：
1.同一时间只允许四个哲学家同时拿起叉子
2.规定拿起第一个叉子时，编号为奇数的哲学家先拿起自己左边的叉子，而编号为偶数的哲学家先拿起自己右边的叉子
3.更暴力一些，把上面代码think()后面的五句保护起来，设置mutex，规定一次只允许一个哲学家吃饭。
4.规定：当且仅当旁边的两个叉子都可以用时，才允许哲学家拿叉子，否则就一直等待。

下面代码是对第4种方法的实现：

#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是哲学家编号
{
    while(true)
    {
        think();
        take_forks(i);
        eat();
        put_forks(i);
    }
}

void take_forks(int i)
{
down(&mutex);
state[i]=HUNGRY;
test(i);     //尝试一下能不能同时拿起左右两只叉子
up(&mutex);
down(&s[i]);    //如果在之前的test里不能拿起两个叉子，那么会在这条语句被锁住
}

void put_forks(int i)
{
down(&mutex);
state[i]=THINKING;
test(LEFT);    //看看左边的哲学家有没有食欲
test(RIGHT);   //看看右边的哲学家有没有食欲
up(&mutex);
}

void test(int i)
{
    if(state[i[==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING)
    {
        state[i]=EATING;
        up(&s[i]);
    }
}

4.读者写者问题

读者和写者都可以访问一个数据库，读者只能读，写者只能写，规定如下：
1.允许任意多个读者同时读数据
2.同一时间只允许一个写者修改数据
3.写者和读者不能同时访问数据

用P、V操作实现的思路：
（把这个数据库想象成图书馆，方便陈述理解）
1.偏向读者型：
（1）当读者到来时，只要有读者在读数据，或者没有人访问数据，这个新的读者都可以读数据
（2）当写者到来时，只有没人访问数据时才能对数据进行写

2.偏向写者型：
（1）当读者到来时，如果前面有写者在等待进入图书馆，读者就不能进去，当然里面有写者也不能进入
（2）当写者到来时，里面有读者依然不能进入，只有里面没人时才能进。

typedef int semaphore;
semaphore mutex=1;    //控制对读者的数量进行加减的信号量
semaphore db=1;       //图书馆的信号量,database
int rc=0;             //图书馆里读者的数量

void reader()
{
    while(true)
    {
    //进入
        down(&mutex);
        rc++;
        if(rc==1)
        down(&db);
        up(&mutex);
        
        read_db();   //读取数据

    //离开
        down(&mutex);
        rc--;
        if(rc==0)
        up(&db);
        up(&mutex);
    }
}

void writer()
{
    while(true)
    {
        down(&db);
        write_db();
        up(&db);
    }
}

5.总结

上一篇下一篇

猜你喜欢

热点阅读