|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 482-483 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 482
SEC. 6.5
DEADLOCK AVOIDANCE
451
In Fig. 6-8 we see a model for dealing with two processes and two resources,
for example, a printer and a plotter.
The horizontal axis represents the number of
instructions executed by process
A
.
The vertical axis represents the number of in-
structions executed by process
B
. At
I
1
A
requests a printer; at
I
2
it needs a plotter.
The printer and plotter are released at
I
3
and
I
4
, respectively. Process
B
needs the
plotter from
I
5
to
I
7
and the printer from
I
6
to
I
8
.
Plotter
Printer
Printer
Plotter
B
A
u (Both processes
finished)
p
q
r
s
t
I
8
I
7
I
6
I
5
I
4
I
3
I
2
I
1
Figure 6-8.
Two process resource trajectories.
Every point in the diagram represents a joint state of the two processes. Ini-
tially, the state is at
p
, with neither process having executed any instructions. If the
scheduler chooses to run
A
first, we get to the point
q
, in which
A
has executed
some number of instructions, but
B
has executed none.
At point
q
the trajectory
becomes vertical, indicating that the scheduler has chosen to run
B
.
With a single
processor, all paths must be horizontal or vertical, never diagonal. Furthermore,
motion is always to the north or east, never to the south or west (because processes
cannot run backward in time, of course).
When
A
crosses the
I
1
line on the path from
r
to
s
, it requests and is granted
the printer.
When
B
reaches point
t
, it requests the plotter.
The regions that are shaded are especially interesting.
The region with lines
slanting from southwest to northeast represents both processes having the printer.
The mutual exclusion rule makes it impossible to enter this region. Similarly, the
region shaded the other way represents both processes having the plotter and is
equally impossible.
If the system ever enters the box bounded by
I
1
and
I
2
on the sides and
I
5
and
I
6
top and bottom, it will eventually deadlock when it gets to the intersection of
I
2
and
I
6
.
At this point,
A
is requesting the plotter and
B
is requesting the printer, and
both are already assigned.
The entire box is unsafe and must not be entered.
At
Page 483
452
DEADLOCKS
CHAP. 6
point
t
the only safe thing to do is run process
A
until it gets to
I
4
.
Beyond that,
any trajectory to
u
will do.
The important thing to see here is that at point
t
,
B
is requesting a resource.
The system must decide whether to grant it or not.
If the grant is made, the system
will enter an unsafe region and eventually deadlock.
To avoid the deadlock,
B
should be suspended until
A
has requested and released the plotter.
6.5.2 Safe and Unsafe States
The deadlock avoidance algorithms that we will study use the information of
Fig. 6-6.
At any instant of time, there is a current state consisting of
E
,
A
,
C
, and
R
.
A state is said to be
safe
if there is some scheduling order in which every proc-
ess can run to completion even if all of them suddenly request their maximum
number of resources immediately.
It is easiest to illustrate this concept by an ex-
ample using one resource.
In Fig. 6-9(a) we have a state in which
A
has three
instances of the resource but may need as many as nine eventually.
B
currently has
two and may need four altogether, later.
Similarly,
C
also has two but may need an
additional five.
A total of 10 instances of the resource exist, so with seven re-
sources already allocated, three there are still free.
A
B
C
3
2
2
9
4
7
Free: 3
(a)
A
B
C
3
4
2
9
4
7
Free: 1
(b)
A
B
C
3
0
–
–
2
9
7
Free: 5
(c)
A
B
C
3
0
7
9
7
Free: 0
(d)
–
A
B
C
3
0
0
9
–
Free: 7
(e)
Has
Max
Has
Max
Has
Max
Has
Max
Has
Max
Figure 6-9.
Demonstration that the state in (a) is safe.
The state of Fig. 6-9(a) is safe because there exists a sequence of allocations
that allows all processes to complete.
Namely, the scheduler can simply run
B
exclusively, until it asks for and gets two more instances of the resource, leading to
the state of Fig. 6-9(b). When
B
completes, we get the state of Fig. 6-9(c). Then
the scheduler can run
C
, leading eventually to Fig. 6-9(d). When
C
completes, we
get Fig. 6-9(e). Now
A
can get the six instances of the resource it needs and also
complete. Thus, the state of Fig. 6-9(a) is safe because the system, by careful
scheduling, can avoid deadlock.
Now suppose we have the initial state shown in Fig. 6-10(a), but this time
A
requests and gets another resource, giving Fig. 6-10(b). Can we find a sequence
that is guaranteed to work? Let us try.
The scheduler could run
B
until it asked for
all its resources, as shown in Fig. 6-10(c).
Eventually,
B
completes and we get the state of Fig. 6-10(d). At this point we
are stuck.
We only have four instances of the resource free, and each of the active
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
