7강 연습문제

7.1 Consider the traffic deadlock depicted in Figure 7.9

 

a. Show that the four neccessary conditions for deadlock indeed hold in this example.

Deadlock이 성립하기 위해서는

1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait

를 모두 만족해야 한다.

1. Mutual Exclusion : 각 교차로에서는 한번에 하나의 차량만 지나갈 수 있다.
2. Hold and Wait : 다른 차들이 지나가기 전까지 기다려야 한다.
3. No Preemption : 도로위에 있는 차가 지나가기 전에는 대체되거나 사라질 수 없다.
4. Cicular Wait : 4개의 도로에 꼬리가 물려있어 어느 차도 지나가지 못하는 네모 형태의 순환이 생겼다.

b. State a simple rule for avoiding deadlocks in this system.

도로별 우선순위를 정하여 한 도로의 차가 우선적으로 지나갈 수 있도록 한다. 우선순위가 낮은 도로의 차는 우선순위가 높은 도로의 차가 지나갈 때 까지 기다리도록 한다.

7.5 Consider a system consisting of m resources of the same type being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock free if the following two conditions hold:

Explanation:

The system will be deadlock free if the below two conditions holds :

Proof below:

Suppose N = Summation of all Need(i), A = Addition of all Allocation(i), M = Addition of all Max(i). Use contradiction to prove.

Suppose this system isn't deadlock free. If a deadlock state exists, then A = m due to the fact that there's only one kind of resource and resources can be requested and released only one at a time.

Condition B, N + A equals M < m + n. Equals N + m < m + n. And we get N < n. It means that at least one process i that Need(i) = 0.

Condition A, Pi can let out at least 1 resource. So there will be n-1 processes sharing m resources now, Condition a and b still hold. In respect to the argument, No process will wait forever or permanently, so there's no deadlock.

a. The maximum need of each process is between 1 and m resources.

b. The sum of all maximum needs is less than m + n.

7.8 Consider the following snapshot of a system:

 

Answer the following questions using the banker's algorithm:

a. What is the content of the matrix Need?

Need = Max - Allocation

b. Is the system in a safe state?

p0→p3→p1→p2→p4 순서대로 프로세스에 자원을 할당해주게 되면 safe state에 있다.

c. If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately?

1. P1이 요청한 (0,4,2,0)이 Max(1,7,5,0) 보다 낮다.
2. p1이 요청한 (0,4,2,0)이 현재 갖고있는 Available(1,5,2,0)보다 낮다.

그러므로 Safe state에 있는지 확인한 뒤 자원을 할당해줄 수 있다.

p0→p2→p3→p4→p1 순서대로 프로세스에 자원을 할당해주게 되면 safe state에 있으므로 P1이 요청한 자원은 즉시 할당될 수 있다.