IS CS-2016S1-04

题目来源：Problem 4 日期：2024-08-11 题目主题：CS-操作系统-死锁

解题思路

本题主要考察的是操作系统中进程管理与死锁预防的相关概念。我们需要理解死锁产生的条件，以及如何通过资源分配策略来避免死锁的发生。

死锁发生的必要条件是：互斥、占有并等待、不剥夺以及循环等待。本题中涉及到的资源是不可抢占的，因此若满足其他条件，系统可能会进入死锁状态。

Solution

Question 1

Given $M=2$, $N=2$, and $n_1=n_2=2$, let’s describe a deadlock scenario.

Example of Deadlock

• Assume we have two processes, ${\mathbf{p}}_1$ and ${\mathbf{p}}_2$, and two resources, ${\mathbf{r}}_1$ and ${\mathbf{r}}_2$.
• Process ${\mathbf{p}}_1$ requests resource ${\mathbf{r}}_1$ and is granted it.
• Process ${\mathbf{p}}_2$ requests resource ${\mathbf{r}}_2$ and is granted it.
• Now, ${\mathbf{p}}_1$ requests resource ${\mathbf{r}}_2$ (which is already held by ${\mathbf{p}}_2$) and must wait.
• Simultaneously, ${\mathbf{p}}_2$ requests resource ${\mathbf{r}}_1$ (which is already held by ${\mathbf{p}}_1$) and must wait.

At this point, both processes are waiting for each other to release the resource they need to proceed, leading to a deadlock. Neither process can continue, as both are waiting indefinitely for a resource held by the other.

Timing of Assignment and Release

• Step 1: ${\mathbf{p}}_1$ requests and acquires ${\mathbf{r}}_1$.
• Step 2: ${\mathbf{p}}_2$ requests and acquires ${\mathbf{r}}_2$.
• Step 3: ${\mathbf{p}}_1$ requests ${\mathbf{r}}_2$ and gets blocked.
• Step 4: ${\mathbf{p}}_2$ requests ${\mathbf{r}}_1$ and gets blocked.
• Result: Deadlock occurs.

Question 2

Example of a Technique to Prevent Deadlock

One common technique to prevent deadlock is resource allocation ordering.

Resource Allocation Ordering

• Assign a global ordering to all resources. For example, let ${\mathbf{r}}_1$ have a lower order than ${\mathbf{r}}_2$.
• Enforce that each process requests resources in the order of this global numbering. For instance, processes must always request ${\mathbf{r}}_1$ before ${\mathbf{r}}_2$.

Application

• ${\mathbf{p}}_1$ must first request ${\mathbf{r}}_1$ and then ${\mathbf{r}}_2$.
• ${\mathbf{p}}_2$ must also request ${\mathbf{r}}_1$ before ${\mathbf{r}}_2$.

By ensuring that all processes request resources in the same order, we eliminate the possibility of circular waiting, thereby preventing deadlock.

Restrictions and Disadvantages

• Rigidity: Processes may not be able to request resources dynamically based on real-time needs.
• Underutilization: If processes have to request resources in a predefined order, it could lead to inefficient resource utilization, as some processes may hold onto resources longer than necessary.

Question 3

Given $M=3$, $N=4$, and $n_1=n_2=n_3=2$, we need to determine if deadlock is possible.

Analysis

• There are 3 processes, each requiring 2 out of the 4 available resources.
• Suppose ${\mathbf{p}}_1$ holds ${\mathbf{r}}_1$ and ${\mathbf{r}}_2$, ${\mathbf{p}}_2$ holds ${\mathbf{r}}_3$ and ${\mathbf{r}}_4$.
• Now, ${\mathbf{p}}_3$ cannot acquire any two resources without waiting. But since ${\mathbf{p}}_1$ and ${\mathbf{p}}_2$ are already holding 4 resources collectively, ${\mathbf{p}}_3$ is blocked.

However, as the total number of resources is greater than the number required for two processes combined, no process is left waiting indefinitely in a circular wait. Therefore, deadlock cannot occur.

Conclusion

• In this specific setup, deadlock does not occur because the system can always complete at least one process and release resources for others.

Question 4

Given arbitrary integers $M$ and $N$ (both at least 1) and assuming $1\le n_i\le N$ for each $i\in [1,M]$, we need to find the maximum value of $n=n_1+n_2+\cdots +n_M$ such that the system is guaranteed not to exhibit deadlock.

Solution

• The system is guaranteed not to have a deadlock if, at all times, there is at least one process that can obtain all the resources it needs to complete and release those resources.

• A necessary and sufficient condition to avoid deadlock is:

  $$n\le N+(M-1)$$

  This inequality ensures that after $M-1$ processes have taken up to $n_i$ resources each, there will still be enough resources left for the $M$-th process to complete, avoiding circular wait and hence deadlock.

Explanation

• $M-1$ Processes: Assume the worst-case scenario where $M-1$ processes have already acquired the maximum number of resources they each need (up to $N-1$).
• Remaining Resources: To avoid deadlock, at least one process must be able to acquire all the remaining resources it needs (at least 1 resource).

Therefore, the maximum value of $n$ to avoid deadlock is $N+(M-1)$.

知识点

操作系统死锁

解题技巧和信息

1. 理解死锁的四个必要条件

在分析死锁问题时，首先要确认是否满足以下四个必要条件：

• 互斥 (Mutual Exclusion): 资源无法被多个进程同时使用。
• 占有并等待 (Hold and Wait): 进程已经占有了资源，并且还在等待其他资源。
• 不剥夺 (No Preemption): 资源不能被强制剥夺，只能由占有它的进程自行释放。
• 循环等待 (Circular Wait): 存在一个进程环，环中的每个进程都在等待被下一个进程占有的资源。

如果四个条件同时满足，那么系统可能会陷入死锁。因此，在设计和分析系统时，要通过打破这些条件中的至少一个来预防死锁。

2. 使用资源分配图 (Resource Allocation Graph)

在分析进程和资源之间的关系时，资源分配图是一个非常有效的工具。通过绘制图表，可以直观地看出系统中是否存在可能导致死锁的循环等待链路。如果图中存在环路，系统可能处于死锁状态。

3. 死锁预防的常见策略

以下是几种常见的死锁预防策略：

• 静态资源分配顺序 (Resource Allocation Ordering): 对资源编号，并要求进程按照编号顺序请求资源，避免循环等待的形成。
• 资源请求时全占用 (Resource Allocation upon Request): 要求进程在开始执行时一次性请求所需的所有资源。如果不能获得所有资源，则进程必须释放已经获得的资源，并重新尝试。
• 避免饥饿 (Starvation Prevention): 为了避免进程一直无法获得资源而导致死锁或饥饿，通常使用优先级机制或资源抢占策略来动态调整资源分配。

4. 确定系统的最大资源需求

在设计系统时，计算系统中每个进程的最大资源需求是至关重要的。通过分析最坏情况下的资源需求，可以确保系统配置的资源足够满足每个进程的需求，从而避免死锁。

5. 运用安全状态 (Safe State) 的概念

为了避免死锁，确保系统始终处于安全状态。如果系统可以保证即使在最坏情况下，仍然可以完成某个进程而不导致其他进程进入死锁，那么系统就是安全的。使用银行家算法可以动态判断系统是否处于安全状态，并调整资源分配策略。

总结

• 在解答涉及死锁的问题时，首先要明确系统的资源配置和进程需求。
• 使用死锁的四个必要条件来判断系统是否可能发生死锁。
• 采用图论工具如资源分配图来帮助识别潜在的死锁风险。
• 了解并应用死锁预防策略，如资源分配顺序、全占用请求等，以确保系统设计中不会出现死锁。

这些技巧和信息可以帮助你更好地理解和解决操作系统中与死锁相关的问题，并在考试中提供有力的支持。

重点词汇

1. Deadlock 死锁
2. Resource allocation 资源分配
3. Circular wait 循环等待
4. Mutual exclusion 互斥

参考资料

1. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts (10th ed.). John Wiley & Sons, Inc. Chapter 7: Deadlocks.
2. Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th ed.). Pearson. Chapter 6: Deadlocks.