|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 470-471 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 470
SEC. 6.2
INTRODUCTION TO DEADLOCKS
439
typedef int semaphore;
semaphore resource
1;
semaphore resource
1;
semaphore resource
2;
semaphore resource
2;
void process
A(void) {
void process
A(void) {
down(&resource
1);
down(&resource
1);
down(&resource
2);
down(&resource
2);
use
both
resources( );
use
both
resources( );
up(&resource
2);
up(&resource
2);
up(&resource
1);
up(&resource
1);
}
}
void process
B(void) {
void process
B(void) {
down(&resource
1);
down(&resource
2);
down(&resource
2);
down(&resource
1);
use
both
resources( );
use
both
resources( );
up(&resource
2);
up(&resource
1);
up(&resource
1);
up(&resource
2);
}
}
(a)
(b)
Figure 6-2.
(a) Deadlock-free code. (b) Code with a potential deadlock.
6.2 INTRODUCTION TO DEADLOCKS
Deadlock can be defined formally as follows:
A set of processes is deadlocked if each process in the set is waiting for an
event that only another process in the set can cause.
Because all the processes are waiting, none of them will ever cause any event that
could wake up any of the other members of the set, and all the processes continue
to wait forever. For this model, we assume that processes are single threaded and
that no interrupts are possible to wake up a blocked process.
The no-interrupts
condition is needed to prevent an otherwise deadlocked process from being awak-
ened by an alarm, and then causing events that release other processes in the set.
In most cases, the event that each process is waiting for is the release of some
resource currently possessed by another member of the set.
In other words, each
member of the set of deadlocked processes is waiting for a resource that is owned
by a deadlocked process.
None of the processes can run, none of them can release
any resources, and none of them can be awakened. The number of processes and
the number and kind of resources possessed and requested are unimportant.
This
result holds for any kind of resource, including both hardware and software. This
kind of deadlock is called a
resource deadlock
.
It is probably the most common
kind, but it is not the only kind.
We first study resource deadlocks in detail and
then at the end of the chapter return briefly to other kinds of deadlocks.
Page 471
440
DEADLOCKS
CHAP. 6
6.2.1 Conditions for Resource Deadlocks
Coffman et al. (1971) showed that four conditions must hold for there to be a
(resource) deadlock:
1.
Mutual exclusion condition.
Each resource is either currently assign-
ed to exactly one process or is available.
2. Hold-and-wait condition.
Processes currently holding resources that
were granted earlier can request new resources.
3. No-preemption condition. Resources previously granted cannot be
forcibly taken away from a process.
They must be explicitly released
by the process holding them.
4.
Circular wait condition.
There must be a circular list of two or more
processes, each of which is waiting for a resource held by the next
member of the chain.
All four of these conditions must be present for a resource deadlock to occur.
If
one of them is absent, no resource deadlock is possible.
It is worth noting that each condition relates to a policy that a system can have
or not have.
Can a given resource be assigned to more than one process at once?
Can a process hold a resource and ask for another?
Can resources be preempted?
Can circular waits exist? Later on we will see how deadlocks can be attacked by
trying to negate some of these conditions.
6.2.2 Deadlock Modeling
Holt (1972) showed how these four conditions can be modeled using directed
graphs. The graphs have two kinds of nodes: processes, shown as circles, and re-
sources, shown as squares.
A directed arc from a resource node (square) to a proc-
ess node (circle) means that the resource has previously been requested by, granted
to, and is currently held by that process.
In Fig. 6-3(a), resource
R
is currently as-
signed to process
A
.
A directed arc from a process to a resource means that the process is currently
blocked waiting for that resource.
In Fig. 6-3(b), process
B
is waiting for resource
S
.
In Fig. 6-3(c) we see a deadlock: process
C
is waiting for resource
T
, which is
currently held by process
D
. Process
D
is not about to release resource
T
because
it is waiting for resource
U
, held by
C
.
Both processes will wait forever. A cycle
in the graph means that there is a deadlock involving the processes and resources in
the cycle (assuming that there is one resource of each kind).
In this example, the
cycle is
C
−
T
−
D
−
U
−
C
.
Now let us look at an example of how resource graphs can be used.
Imagine
that we have three processes,
A
,
B
, and
C
, and three resources,
R
,
S
, and
T
. The
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
