The Deadlock Problems
final exam 会出一题
A set of blocked processes each holding a resource and wating to acquire a resource held by another process in the set
Circular wait: there exists a set {P0, P1, …, Pn} of wating processes such that P0 is wating for a resource that is held by P1, P1 is wating for a resource that is held by P2, …, Pn-1 is wating for a resource that is held by Pn, and Pn is wating for a resource that is held by P0.
Example of Banker’s Algorithm
- allocation and max is givin in final exam
- find out the
need matricx(max - allocation) - if
availableis not given, we cannnot find out the safe sequence, just go finding resource type
Example 1
Available A B C
3 3 2
Allocation Max Need Matrix
---------- --- -----------
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3 P0: Finish: F
P1 2 0 0 3 2 2 1 2 2 P1: Finish: T | W: 5 3 2
P2 3 0 2 9 0 2 6 0 0 P2: Finish: F
P3 2 1 1 2 2 2 0 1 1 P3: Finish: T | W: 7 4 2
P4 0 0 2 4 3 3 4 3 1 P4: Finish: T | W: 7 4 5
-- -- -- P0: Finish: T | W: 7 5 5
7 2 5 <--total P2: Finish: T | W: 10 5 7 <--same as resource type means ok
10 5 7 <--resource type
(ii) Conclusion: Yes! the system is in the safe state
(iii) Safe sequence <P1, P3, P4, P0, P2>
Example 2
Available = (2, 1, 0)
Processes Allocation Max Need Matrix
A B C A B C A B C
-------------------------------------------
P0 1 1 2 4 3 3 3 2 1 P0: Finish[0]; F
P1 2 1 2 3 2 2 1 1 0 P1: Finish[1]; T | W: 4 2 2
P2 4 0 1 9 0 2 5 0 1 P2: Finish[2]; F
P3 0 2 0 7 5 3 7 3 3 P3: Finish[3]; F
P4 1 1 2 1 1 2 0 0 0 P4: Finish[4]; T | W: 5 3 4
-- -- -- P0: Finish[0]; T | W: 6 4 6
8 5 7 P2: Finish[2]; T | W: 10 4 7
10 6 7 P3: Finish[3]; T | W: 10 6 7
Yes, the system is in Safe state
Safe sequence <P1, P4, P0, P2, P3>
Example 3
Consider the following data structures in the Banker’s algorithm, with resources A, B, C, and D, and process P0 o P4.
Available Resource - 1 5 2 0
Allocation Max
---------- ---
A B C D A B C D
P0 0 0 1 2 0 0 1 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
i) Calculate the Need Matrix. (5 marks)
Need Matrix
-----------
A B C D
P0 0 0 0 0
P1 0 7 5 0
P2 1 0 0 2
P3 0 0 2 0
P4 0 6 4 2
ii) Is the system in a safe state? Give the safe sequence. (10 marks)
P0: Finish[0]; T | W: 1 5 3 2
P1: Finish[1]; F
P2: Finish[2]; T | W: 2 8 8 6
P3: Finish[3]; T | W: 2 14 11 8
P4: Finish[4]; T | W: 2 14 12 12
P1: Finish[1]; T | W: 3 14 12 12
quick checking answer:
A B C D
total of Allocation: 2 9 10 12
Available Resources: + 1 5 2 0
------------
3 14 12 12 -->answer is same :)
Yes, the system is in a safe state.
Safe sequence <P0, P2, P3, P4, P1>