亚马逊面试题：
问题陈述非常简单。
假设我们有 N 个资源（全部相互独立），那么可以同时运行的最大进程数是多少，使用至少一个资源，这样就不会出现死锁？
下面提供了一个示例示例，显示使用两个资源的两个进程可能处于死锁状态。（来源：ucla.edu）
有人请给我详细的答案。
问问题
723 次
2 回答
0
问题不完整。该问题未指定进程完成其执行所需的最大资源数。
让我重新表述一下这个问题：
假设我们有N个资源（都是相互独立的），那么可以同时运行的最大进程数是多少，至少使用其中一个资源，每个进程最多M个资源，这样就不会有僵局？
回答：
设可用资源数=N，一个进程可以同时持有的最大资源数=M，进程数=P。
如果满足以下条件，则系统处于安全模式。
N >= P ( M - 1 ) + 1
最大进程数，
P <= ( N - 1) / ( M - 1)
例如，如果可用资源数为 6（N=6），每个进程最多使用 2（M=2）个资源来完成执行，则最大进程数为 5。系统仍然是安全的。
Let, illustrate another scenario. the number of available resources is 6 (N=6) and each process uses at most 3 (M=3) resources to finish execution
Now, we have 6 processes in the system. All possible resources allocations are:
P1 | P2 | P3 | P4 | P5 | P6 | Available | Safe | Comment
| | | | | | resources | |
--------|-------|-------|-------|-------|-------|---------------|-----------|-----------------------------------------------------------
1 | 1 | 1 | 1 | 1 | 1 | 0 | No |each process requires at least 2 resources to finish
| | | | | | | |But no resource is available
Now, we have 5 processes in the system. All possible resources allocations are:
P1 | P2 | P3 | P4 | P5 | Available | Safe | Comment
| | | | | resources | |
--------|-------|-------|-------|-------|---------------|-----------|-----------------------------------------------------------
1 | 1 | 1 | 1 | 1 | 1 | No |each process requires at least 2 resources to finish
| | | | | | | |But only one resource is available
--------|-------|-------|-------|-------|---------------|-----------|-----------------------------------------------------------
2 | 1 | 1 | 1 | 1 | 0 | No |P1 requires at least 1 resource to finish
| | | | | | | |But no resource is available
Now, we have 4 processes in the system. All possible resources allocations are:
P1 | P2 | P3 | P4 | Available | Safe | Comment
| | | | resources | |
--------|-------|-------|-------|---------------|-----------|-----------------------------------------------------------
1 | 1 | 1 | 1 | 2 | Yes |
--------|-------|-------|-------|---------------|-----------|-----------------------------------------------------------
2 | 1 | 1 | 1 | 1 | Yes |P1 requires at least 1 resources to finish
| | | | | |and 1 resource is available. So the system is safe for this allocation.
--------|-------|-------|-------|---------------|-----------|-----------------------------------------------------------
2 | 2 | 1 | 1 | 0 | No |
Now, we have 3 processes in the system. All possible resources allocations are:
P1 | P2 | P3 | Available | Safe | Comment
| | | resources | |
--------|-------|-------|---------------|-----------|-----------------------------------------------------------
1 | 1 | 1 | 3 | Yes |
2 | 1 | 1 | 2 | Yes |
2 | 2 | 1 | 1 | Yes |
2 | 2 | 2 | 0 | No |
Now, we have 2 processes in the system. All possible resources allocations are:
P1 | P2 | Available | Safe | Comment
| | resources | |
--------|-------|---------------|-----------|-----------------------------------------------------------
1 | 1 | 4 | Yes |
2 | 1 | 3 | Yes |
2 | 2 | 2 | Yes |
If the maximum no of processes is 2, the system will be safe whatever the resources allocations are.
So using the given formula above,
For, the number of available resources, N = 6
And the maximum number of resources required by each process, M = 3
The maximum number processes, P <= (6-1) / (3-1) = 2.5 = 2 (apx.)
于 2021-03-03T22:00:45.300 回答
0
问题不完整。只有当系统中同时满足以下所有条件时，才会发生死锁（检查https://en.wikipedia.org/wiki/Deadlock）：
- 互斥：至少一个资源必须以不可共享的方式持有。在任何给定时刻，只有一个进程可以使用该资源。
- 持有并等待或资源持有：一个进程当前持有至少一个资源并请求其他进程持有的额外资源。
- 无抢占：资源只能由持有它的进程自愿释放。
- 循环等待：一个进程必须等待另一个进程持有的资源，而另一个进程又在等待第一个进程释放资源。一般来说，有一组等待进程，P = {P1, P2, ..., PN}，这样 P1 正在等待 P2 持有的资源，P2 正在等待 P3 持有的资源，依此类推，直到 PN等待 P1 持有的资源。
所以，这里有不同的假设和相应的答案：
案例1：资源是非独占的或者可以被抢占或者有任何其他机制来避免死锁（明显的答案）
然后，可以运行任意数量的处理器。附带说明：当然，根据具体情况，您可能希望限制进程数以避免/减少争用。
案例2：没有上述条件
然后，如果没有任何避免死锁的逻辑，如果要避免死锁，一次只能运行一个进程。一旦您向系统添加另一个进程，您就会遇到示例中描述的情况（P1 有 Ra 并且想要 Rb，P2 有 Rb 并且想要 Ra）。
PS：我相信这更多是为了看到您对概念的理解而不是获得确切答案的问题。
于 2016-03-06T23:24:22.860 回答