同步问题

同步问题案例

读者-写者问题

问题描述：

有两组并发进程：读者和写者，共享一个文件F，要求:
（1）允许多个读者同时执行读操作
（2）任一写者在完成写操作之前不允许其它读者或写者工作
（3）写者执行写操作前，应让已有的写者和读者全部退出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
semapore rw = 1;   //控制读者和写者同时操作文件,当有写者时加锁，当有第一个读者时加锁（之后只允许读者访问）
semapore mutex = 1;  //控制多个写者控制文件
int reader_count = 0;  //记录当前的读者数量
Reader{
    P(mutex);
    if(reader_count++ == 0)   //如果这是第一个读者，就加锁
    {
        P(rw);
    }
    V(mutex);
    //执行读操作

    P(mutex);
    if(reader_count-- == 0)
    {
        V(rw);
    }
    V(mutex);
}
Writer{
    P(rw);
    //写数据
    V(rw);
}

当写者加锁成功其余写者与读者均不能加锁，当读者加锁成功，其他读者可以继续执行，但写者无法加锁

理发师问题

  • 理发店有一位理发师、一把理发椅和N把供等候理发的顾客坐的椅子
  • 如果没有顾客，理发师便在理发椅上睡觉
  • 一个顾客到来时，他必须叫醒理发师
  • 如界理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开
  • 使用PV操作求解该问题

初始条件，没有顾客，理发师在休息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
semapore customer = 0;
semapore barber = 1;
semapore mutex = 1;
int waiting = 0;  //等待的人数
chair_count = max;
Barber{
    P(customer);
    P(mutex); waiting--; V(mutex);
    //执行理发
    V(barber);

}

customer{
    P(mutex);
    if(waiting <= max) 
    {
        waiting++;
        V(mutex);
        P(barber);   //等待理发师   
        V(customer);  
        //被理发
    }
    else
    {
        V(mutex);
        //leaving,椅子已经坐满了
    }
}

哲学家就餐问题

有 5 个哲学家，他们面前都有一双筷子，即左手有一根筷子，右手有一根筷子。当然，这个问题有多个版本的描述，可以说是筷子，也可以说是一刀一叉，因为吃牛排的时候，需要刀和叉，缺一不可，也有说是用两把叉子来吃意大利面。这里具体是刀叉还是筷子并不重要，重要的是必须要同时持有左右两边的两个才行，也就是说，哲学家左手要拿到一根筷子，右手也要拿到一根筷子，在这种情况下哲学家才能吃饭。为了方便理解，我们选取和我国传统最贴近的筷子来说明这个问题。

我们来看一下哲学家就餐的主流程。哲学家如果想吃饭，他会先尝试拿起左手的筷子，然后再尝试拿起右手的筷子，如果某一根筷子被别人使用了，他就得等待他人用完，用完之后他人自然会把筷子放回原位，接着他把筷子拿起来就可以吃了（不考虑卫生问题）。这就是哲学家就餐的最主要流程。

1
2
3
4
5
6
7
8
9
semaghore chopstick[5] = {1};  //初始状态均为空闲状态
philospher_i{
    //Thinking
    P(choptick[i]);
    P((chopstick[i+1)%5])
    //eating
    V(choptick[i]);
    V((chopstick[i+1)%5])
}

这实际上有问题的，当每个哲学家都拿到其左边的筷子，这样死锁就产生了，具体将在下一节给出死锁的解决方案

参考：https://www.bilibili.com/video/BV1bf4y147PZ/?p=18