IS CS-2020S1-02

题目来源：Problem 2 日期：2024-08-07 题目主题：CS-操作系统-并发与同步

解题思路

此题是经典的哲学家进餐问题，涉及到多线程的同步和死锁问题。我们需要分析如何使用二元信号量来实现 pickup 和 putdown 函数，避免死锁并确保至少一个线程能够持续执行 eat 和 think 函数。第一问涉及的是一个可能导致死锁的情况，第二问要求我们重新定义 pickup 和 putdown 函数以避免死锁，而第三问则需要讨论饥饿问题。

Solution

Q1: Deadlock Occurrence

In the given pickup and putdown functions, a deadlock may occur due to the circular wait condition. Here’s the explanation:

1. Circular Wait Condition:
   • Each philosopher tries to pick up their left fork first by executing wait(R[i]).
   • After picking up the left fork, each philosopher tries to pick up the right fork with wait(R[(i + 1) % 5]).
2. Deadlock Scenario:
   • Suppose all philosophers pick up their left forks simultaneously, i.e., Philosopher 0 picks up fork 0, Philosopher 1 picks up fork 1, and so on.
   • Then, each philosopher tries to pick up their right fork, which is already held by the next philosopher. For example, Philosopher 0 waits for fork 1 (held by Philosopher 1), Philosopher 1 waits for fork 2 (held by Philosopher 2), and so on.
   • As a result, all philosophers are stuck waiting for a fork that will never become available, causing a deadlock.

Q2: Redefinition of test Function

To avoid deadlock, we redefine the pickup and putdown functions using a different synchronization mechanism. The test function is called to check if a philosopher can start eating.

void test(int i) {
  if (state[i] == waiting &&
      state[(i + 4) % 5] != eating &&
      state[(i + 1) % 5] != eating) {
    state[i] = eating;
    signal(S[i]);
  }
}

Explanation:

• The test function checks if the philosopher i is in the waiting state and both neighbors are not eating.
• If both conditions are met, the philosopher can proceed to eat by setting state[i] to eating and signaling the semaphore S[i] so that the philosopher can continue past wait(S[i]) in the pickup function.

Q3: Starvation Analysis

No, starvation cannot occur under the provided solution. Here’s why:

• The solution ensures that if a philosopher wants to eat and their neighbors are not eating, they will eventually be allowed to eat. The mutex ensures that only one philosopher can change the state at a time, preventing race conditions. Since any philosopher can only start eating if both neighbors are not eating, there will always be at least one philosopher able to eat if others are not eating.
• Additionally, since all philosophers can continuously cycle between eating and thinking, each philosopher will eventually get a chance to eat when they are hungry. This is because once a philosopher finishes eating, they will release the forks (signal semaphores) and set their state to thinking, allowing the next waiting philosopher to eat.

知识点

并发控制死锁信号量哲学家进餐问题操作系统

难点思路

死锁的分析和避免是本题的难点之一。在分析死锁时，要考虑资源的分配和等待的顺序，并且必须设计机制来打破循环等待条件。

Note: 为什么 (2) 的 pickup 中会出现先 V(S[i]) 再 P(S[i]) 的情况？

1. 快速通过的情况：

   • 如果哲学家进入 pickup 函数时，恰好他的两个邻居都没有在吃饭，那么 test(i) 函数会立即调用 signal(S[i])。
   • 这样，当执行到 wait(S[i]) 时，它会立即通过，哲学家可以开始吃饭。
   • 这种情况下，哲学家几乎没有等待就获得了开始吃饭的许可。

2. 等待的情况：

   • 如果有邻居正在吃饭，test(i) 函数不会调用 signal(S[i])。
   • 这时，哲学家会在 wait(S[i]) 处阻塞。
   • 当邻居吃完饭执行 putdown 时，会调用 test 函数检查等待的哲学家。
   • 如果条件满足（比如这个等待的哲学家的另一个邻居也没在吃饭），then signal(S[i]) 会被调用，唤醒等待的哲学家。

这个机制的巧妙之处在于：

1. 它允许哲学家在条件满足时快速获取资源（叉子）。
2. 当条件不满足时，它能让哲学家有效地等待，而不会占用 mutex 锁。
3. 它保证了系统的活性（liveness），因为每次有哲学家放下叉子时，都会检查是否可以唤醒等待的邻居。

这种设计体现了并发编程中的一个重要原则：尽可能减少持有锁的时间，以提高并发性。通过将 ” 等待条件满足 ” 的操作（wait(S[i])）放在释放 mutex 之后，系统允许其他哲学家在这期间改变他们的状态。

解题技巧和信息

1. 避免死锁: 要避免死锁，可以打破循环等待、占有且等待、不可剥夺条件中的至少一个。通过规定一个哲学家先尝试获取编号小的叉子，再获取编号大的叉子，或者使用信号量控制最多只有四个哲学家可以同时拿起叉子来避免死锁。
2. 信号量使用: 使用二元信号量来保证临界区的互斥访问，以及实现条件同步。

重点词汇

1. Semaphore (信号量): A synchronization primitive used to control access to a common resource.
2. Deadlock (死锁): A situation where a set of processes are blocked because each process is holding a resource and waiting for another resource.
3. Starvation (饥饿): A situation where a process is perpetually denied necessary resources to proceed.

参考资料

1. A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts, 9th Edition, Chapter 7: “Deadlocks”.