|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 477 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 477
446
DEADLOCKS
CHAP. 6
any cycles. If this property holds for all nodes, the entire graph is cycle free, so the
system is not deadlocked.
To see how the algorithm works in practice, let us use it on the graph of
Fig. 6-5(a).
The order of processing the nodes is arbitrary, so let us just inspect
them from left to right, top to bottom, first running the algorithm starting at
R
, then
successively
A
,
B
,
C
,
S
,
D
,
T
,
E
,
F
, and so forth.
If we hit a cycle, the algorithm
stops.
We start at
R
and initialize
L
to the empty list.
Then we add
R
to the list and
move to the only possibility,
A
, and add it to
L
, giving
L
=[
R
,
A
]. From
A
we go
to
S
, giving
L
=[
R
,
A
,
S
].
S
has no outgoing arcs, so it is a dead end, forcing us to
backtrack to
A
. Since
A
has no unmarked outgoing arcs, we backtrack to
R
, com-
pleting our inspection of
R
.
Now we restart the algorithm starting at
A
, resetting
L
to the empty list.
This
search, too, quickly stops, so we start again at
B
. From
B
we continue to follow
outgoing arcs until we get to
D
, at which time
L
=[
B
,
T
,
E
,
V
,
G
,
U
,
D
]. Now we
must make a (random) choice.
If we pick
S
we come to a dead end and backtrack
to
D
.
The second time we pick
T
and update
L
to be [
B
,
T
,
E
,
V
,
G
,
U
,
D
,
T
], at
which point we discover the cycle and stop the algorithm.
This algorithm is far from optimal.
For a better one, see Even (1979).
Never-
theless, it demonstrates that an algorithm for deadlock detection exists.
6.4.2 Deadlock Detection with Multiple Resources of Each Type
When multiple copies of some of the resources exist, a different approach is
needed to detect deadlocks.
We will now present a matrix-based algorithm for de-
tecting deadlock among
n
processes,
P
1
through
P
n
.
Let the number of resource
classes be
m
, with
E
1
resources of class 1,
E
2
resources of class 2, and generally,
E
i
resources of class
i
(1
≤
i
≤
m
).
E
is the
existing resource vector
. It gives the
total number of instances of each resource in existence. For example, if class 1 is
tape drives, then
E
1
=
2 means the system has two tape drives.
At any instant, some of the resources are assigned and are not available. Let
A
be the
available resource vector
, with
A
i
giving the number of instances of re-
source
i
that are currently available (i.e., unassigned).
If both of our two tape
drives are assigned,
A
1
will be 0.
Now we need two arrays,
C
, the
current allocation matrix
, and
R
, the
request
matrix
. The
i
th row of
C
tells how many instances of each resource class
P
i
cur-
rently holds.
Thus,
C
ij
is the number of instances of resource
j
that are held by
process
i
. Similarly,
R
ij
is the number of instances of resource
j
that
P
i
wants.
These four data structures are shown in Fig. 6-6.
An important invariant holds for these four data structures.
In particular, every
resource is either allocated or is available. This observation means that
n
i
=
1
Σ
C
ij
+
A
j
=
E
j
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
