|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 484 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 484
SEC. 6.5
DEADLOCK AVOIDANCE
453
A
B
C
3
2
2
9
4
7
Free: 3
(a)
A
B
C
4
2
2
9
4
7
Free: 2
(b)
A
B
C
4
4
—
4
2
9
7
Free: 0
(c)
A
B
C
4
—
2
9
7
Free: 4
(d)
Has Max
Has Max
Has Max
Has Max
Figure 6-10.
Demonstration that the state in (b) is not safe.
processes needs five.
There is no sequence that guarantees completion.
Thus, the
allocation decision that moved the system from Fig. 6-10(a) to Fig. 6-10(b) went
from a safe to an unsafe state.
Running
A
or
C
next starting at Fig. 6-10(b) does
not work either.
In retrospect,
A
’s request should not have been granted.
It is worth noting that an unsafe state is not a deadlocked state.
Starting at
Fig. 6-10(b), the system can run for a while.
In fact, one process can even com-
plete. Furthermore, it is possible that
A
might release a resource before asking for
any more, allowing
C
to complete and avoiding deadlock altogether.
Thus, the dif-
ference between a safe state and an unsafe state is that from a safe state the system
can
guarantee
that all processes will finish; from an unsafe state, no such guaran-
tee can be given.
6.5.3 The Banker’s Algorithm for a Single Resource
A scheduling algorithm that can avoid deadlocks is due to Dijkstra (1965); it is
known as the
banker’s algorithm
and is an extension of the deadlock detection al-
gorithm given in Sec. 3.4.1.
It is modeled on the way a small-town banker might
deal with a group of customers to whom he has granted lines of credit. (Years ago,
banks did not lend money unless they knew they could be repaid.)
What the algo-
rithm does is check to see if granting the request leads to an unsafe state.
If so, the
request is denied.
If granting the request leads to a safe state, it is carried out.
In
Fig. 6-11(a) we see four customers,
A
,
B
,
C
, and
D
, each of whom has been granted
a certain number of credit units (e.g., 1 unit is 1K dollars).
The banker knows that
not all customers will need their maximum credit immediately, so he has reserved
only 10 units rather than 22 to service them.
(In this analogy, customers are proc-
esses, units are, say, tape drives, and the banker is the operating system.)
The customers go about their respective businesses, making loan requests from
time to time (i.e., asking for resources).
At a certain moment, the situation is as
shown in Fig. 6-11(b). This state is safe because with two units left, the banker can
delay any requests except
C
’s, thus letting
C
finish and release all four of his re-
sources. With four units in hand, the banker can let either
D
or
B
have the neces-
sary units, and so on.
Consider what would happen if a request from
B
for one more unit were grant-
ed in Fig. 6-11(b). We would have situation Fig. 6-11(c), which is unsafe.
If all
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
