|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 478-479 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 478
SEC. 6.4
DEADLOCK DETECTION AND RECOVERY
447
Resources in existence
(E
1
, E
2
, E
3
, …, E
m
)
Current allocation matrix
C
11
C
21
C
n1
C
12
C
22
C
n2
C
13
C
23
C
n3
C
1m
C
2m
C
nm
Row n is current allocation
to process n
Resources available
(A
1
, A
2
, A
3
, …, A
m
)
Request matrix
R
11
R
21
R
n1
R
12
R
22
R
n2
R
13
R
23
R
n3
R
1m
R
2m
R
nm
Row 2 is what process 2 needs
Figure 6-6.
The four data structures needed by the deadlock detection algorithm.
In other words, if we add up all the instances of the resource
j
that have been allo-
cated and to this add all the instances that are available, the result is the number of
instances of that resource class that exist.
The deadlock detection algorithm is based on comparing vectors. Let us
define the relation
A
≤
B
on two vectors
A
and
B
to mean that each element of
A
is
less than or equal to the corresponding element of
B
. Mathematically,
A
≤
B
holds
if and only if
A
i
≤
B
i
for 1
≤
i
≤
m
.
Each process is initially said to be unmarked. As the algorithm progresses,
processes will be marked, indicating that they are able to complete and are thus not
deadlocked. When the algorithm terminates, any unmarked processes are known
to be deadlocked. This algorithm assumes a worst-case scenario: all processes
keep all acquired resources until they exit.
The deadlock detection algorithm can now be given as follows.
1. Look for an unmarked process,
P
i
, for which the
i
th row of
R
is less
than or equal to
A
.
2.
If such a process is found, add the
i
th row of
C
to
A
, mark the process,
and go back to step 1.
3.
If no such process exists, the algorithm terminates.
When the algorithm finishes, all the unmarked processes, if any, are deadlocked.
What the algorithm is doing in step 1 is looking for a process that can be run to
completion. Such a process is characterized as having resource demands that can
be met by the currently available resources.
The selected process is then run until
it finishes, at which time it returns the resources it is holding to the pool of avail-
able resources.
It is then marked as completed.
If all the processes are ultimately
able to run to completion, none of them are deadlocked. If some of them can never
Page 479
448
DEADLOCKS
CHAP. 6
finish, they are deadlocked. Although the algorithm is nondeterministic (because it
may run the processes in any feasible order), the result is always the same.
As an example of how the deadlock detection algorithm works, see Fig. 6-7.
Here we have three processes and four resource classes, which we have arbitrarily
labeled tape drives, plotters, scanners, and Blu-ray drives. Process 1 has one scan-
ner.
Process 2 has two tape drives and a Blu-ray drive.
Process 3 has a plotter and
two scanners. Each process needs additional resources, as shown by the
R
matrix.
Blu-rays
Tape drives
Tape drives
Plotters
Plotters
Scanners
Scanners
Blu-rays
E = ( 4
2
3
1 )
Current allocation matrix
Request matrix
A = ( 2
1
0
0 )
C =
0
0
1
0
2
0
0
1
0
1
2
0
R =
2
0
0
1
1
0
1
0
2
1
0
0
Figure 6-7.
An example for the deadlock detection algorithm.
To run the deadlock detection algorithm, we look for a process whose resource
request can be satisfied. The first one cannot be satisfied because there is no Blu-
ray drive available. The second cannot be satisfied either, because there is no scan-
ner free.
Fortunately, the third one can be satisfied, so process 3 runs and eventual-
ly returns all its resources, giving
A
=
(2 2 2 0)
At this point process 2 can run and return its resources, giving
A
=
(4 2 2 1)
Now the remaining process can run.
There is no deadlock in the system.
Now consider a minor variation of the situation of Fig. 6-7. Suppose that proc-
ess 3 needs a Blu-ray drive as well as the two tape drives and the plotter.
None of
the requests can be satisfied, so the entire system will eventually be deadlocked.
Even if we give process 3 its two tape drives and one plotter, the system deadlocks
when it requests the Blu-ray drive.
Now that we know how to detect deadlocks (at least with static resource re-
quests known in advance), the question of when to look for them comes up.
One
possibility is to check every time a resource request is made.
This is certain to
detect them as early as possible, but it is potentially expensive in terms of CPU
time. An alternative strategy is to check every
k
minutes, or perhaps only when the
CPU utilization has dropped below some threshold.
The reason for considering the
CPU utilization is that if enough processes are deadlocked, there will be few run-
nable processes, and the CPU will often be idle.
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
