一、哲学家问题

• 哲学家要进餐，须同时具备左边和右边的筷子

• 一支筷子在一个时刻只允许一位使用

• 用完之后返回原处

Semaphore Chopstick[n]={1,1,1,1,1}; // 定义n个共享资源

while(1)
{
    P(Chopstick[i]); // 第i个人拿起他左边的筷子
    P(Chopstick[(i+1)%n]); // 拿起他右边的筷子
    Eating...
    V(Chopstick[(i+1)%n]);
    V(Chopstick[i]);
    Thinking or Computing...;
}

该算法存在的问题：

可以保证不会有两个相邻的哲学家同时进餐，但却可能引起死锁的情况。

假如五位哲学家同时饥饿而都拿起的左边的筷子，就会使五个信号量chopstick都为0，当他们试图去拿右手边的筷子时，都将无筷子而陷入无限期的等待。

改进策略：

1. 至多只允许四个哲学家同时进餐

2. 仅当哲学家的左右两支筷子都可用时，才允许他拿起筷子进餐

3. 规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号的哲学家则先拿起他右边的筷子，然后再去拿他左边的筷子

二、吃水果问题

桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。

Semaphore Mutex=1; // 盘子临界资源
Semaphore Empty=1,So=0,Sa=0; // 盘子空吗，有桔子或苹果吗

Father()
{
    while(1)
    {
        P(Empty);
        P(Mutex);
        Put fruit;
        if(Orange) V(So);
        else V(Sa);
        V(Mutex);
    }
}

Son()
{
    while(1)
    {
        P(So);
        P(Mutex);
        Fetch Orange;
        V(Empty);
        V(Mutex);
        Eating;
    }
}

Daughter()
{
    while(1)
    {
        P(Sa);
        P(Mutex);
        Fetch Apple;
        V(Mutex);
        V(Empty);
        Eating;
    }
}

三、理发师问题

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子

• 如果没有顾客，理发师便在理发椅上睡觉

• 一个顾客到来时，首先看理发师在干什么，如果在睡觉，则叫醒理发师并坐到理发椅上开始理发；若理发师正在理发，则查看是否有空位可以坐下，如果有，则坐下等待，如果没有则离开。

• 理发师为一位顾客理完发后，查看是否有人等待，如果有则唤醒一位为其理发，没有则在理发椅上睡觉

int seat=n;
int waiting=0;
Semaphore barber=0;
Semaphore customer=0;
Semaphore Mutex=1;

void barber()
{
    while(1)
    {
        P(customer); // 没有顾客睡觉
        P(mutex);
        waiting--;
        V(barber); // 理发师去理发
        V(mutex);
        理发;
    }
}

void customer()
{
    while(1)
    {
        P(mutex);
        if(waiting<n){
            waiting++;
            V(customer); // 唤醒理发师
            V(mutex);
            P(barber); // 没有理发师时，顾客坐着
            坐下等待理发;
        } else{
            V(mutex); // 人太多了走了
        }
    }
}

四、关于P、V操作

解决P、V操作问题的关键

• 理解临界资源与临界区的概念!

• 准确理解问题的同步互斥过程与要求!

  • 同步：多个进程在执行次序上的协调，相互等待消息
  • 互斥：对临界资源的使用

• 建立信号量，准确定义信号量的意义和初始值!

  • 信号量的定义根据同步和互斥要求来定