Information Technology Reference
In-Depth Information
may need as many as 4, 5, and 5 pages to complete, respectively.
If they take turns requesting one page each, and the system grants requests
in order, the system deadlocks, reaching a state where each process is stuck
until some other process releases memory:
Process
Allocation
A
0
1
1
1
2
2
2
3
3
3
wait
wait
B
0
0
1
1
1
2
2
2
3
3
3
wait
C
0
0
0
1
1
1
2
2
2
wait
wait
wait
Total
0
1
2
3
4
5
6
7
8
8
8
8
On the other hand, if the system follows the Banker's algorithm, then it can
delay some processes and guarantee that all processes eventually complete.
E.g.,
Process
Allocation
A
0
1
1
1
2
2
2
3
3
3
4
0
0
0
0
0
0
0
0
B
0
0
1
1
1
2
2
2
wait
wait
wait
wait
3
4
4
5
0
0
0
C
0
0
0
1
1
1
2
2
2
wait
wait
wait
3
3
wait
wait
4
5
0
Total
0
1
2
3
4
5
6
7
7
8
4
6
7
7
8
4
4
5
0
By delaying B and C in the nineth through twelfth steps, the algorithm allows A
to complete and release its resources. Then, by delaying C in the fifteenth and
sixteen steps, the algorithm allows B to complete and release its resources.
Though not terribly complex in absolute terms, the Banker's Algorithm
is noticably more involved than the other approaches discussed above. It is
rarely used in its full generality, but understanding the distinction between safe,
unsafe, and deadlock states and understanding how manifestations of deadlock
depend on request ordering are both important for understanding deadlock.
Additionally, an understanding of the Banker's Algorithm can help one de-
sign simple solutions for specic problems. For example, if we apply the Banker's
Algorithm to the variation of the Dining Philosopher's problem where we place
the chopsticks in the middle of the table, then a philosopher taking a chopstick
would wait if it would be the last chopstick and no philsopher would have two
chopsticks; otherwise, the philosopher would take the chopstick.
6.2.4
Detecting and breaking deadlock
Rather than preventing deadlocks, some systems allow deadlocks to occur and
break them when they arise.
Why allow deadlocks to occur at all? Sometimes, it is dicult or expensive
to enforce sucient structure on the system's data and workloads to prevent
deadlock. For example, this approach is often used in databases, which provide
a general interface that applications can use to access shared data via multi-
step transactions that can acquire and release locks covering different subsets
of data. Because the database is meant as a general tool, there is seldom any
way to prevent users from issuing requests that could cause deadlock. Also,
because a database is often shared by multiple users, it can not allow bugs
