|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 199-200 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 199
168
PROCESSES AND THREADS
CHAP. 2
primitive is by showing how elegantly it solves the dining philosophers problem.
The problem can be stated quite simply as follows. Five philosophers are seated
around a circular table. Each philosopher has a plate of spaghetti.
The spaghetti is
so slippery that a philosopher needs two forks to eat it. Between each pair of plates
is one fork.
The layout of the table is illustrated in Fig. 2-45.
Figure 2-45.
Lunch time in the Philosophy Department.
The life of a philosopher consists of alternating periods of eating and thinking.
(This is something of an abstraction, even for philosophers, but the other activities
are irrelevant here.)
When a philosopher gets sufficiently hungry, she tries to ac-
quire her left and right forks, one at a time, in either order.
If successful in acquir-
ing two forks, she eats for a while, then puts down the forks, and continues to
think. The key question is: Can you write a program for each philosopher that does
what it is supposed to do and never gets stuck?
(It has been pointed out that the
two-fork requirement is somewhat artificial; perhaps we should switch from Italian
food to Chinese food, substituting rice for spaghetti and chopsticks for forks.)
Figure 2-46 shows the obvious solution. The procedure
take
fork
waits until
the specified fork is available and then seizes it. Unfortunately, the obvious solu-
tion is wrong.
Suppose that all five philosophers take their left forks simultan-
eously. None will be able to take their right forks, and there will be a deadlock.
We could easily modify the program so that after taking the left fork, the pro-
gram checks to see if the right fork is available. If it is not, the philosopher puts
down the left one, waits for some time, and then repeats the whole process. This
proposal too, fails, although for a different reason.
With a little bit of bad luck, all
the philosophers could start the algorithm simultaneously, picking up their left
forks, seeing that their right forks were not available, putting down their left forks,
Page 200
SEC. 2.5
CLASSICAL IPC PROBLEMS
169
#define N 5
/
*
number of philosophers
*
/
void philosopher(int i)
/
*
i: philosopher number, from 0 to 4
*
/
{
while (TRUE) {
think( );
/
*
philosopher is thinking
*
/
take
fork(i);
/
*
take left fork
*
/
take
fork((i+1) % N);
/
*
take right fork; % is modulo operator
*
/
eat( );
/
*
yum-yum, spaghetti
*
/
put
fork(i);
/
*
put left fork back on the table
*
/
put
fork((i+1) % N);
/
*
put right fork back on the table
*
/
}
}
Figure 2-46.
A nonsolution to the dining philosophers problem.
waiting, picking up their left forks again simultaneously, and so on, forever. A
situation like this, in which all the programs continue to run indefinitely but fail to
make any progress, is called
starvation
.
(It is called starvation even when the
problem does not occur in an Italian or a Chinese restaurant.)
Now you might think that if the philosophers would just wait a random time
instead of the same time after failing to acquire the right-hand fork, the chance that
everything would continue in lockstep for even an hour is very small.
This obser-
vation is true, and in nearly all applications trying again later is not a problem. For
example, in the popular Ethernet local area network, if two computers send a pack-
et at the same time, each one waits a random time and tries again; in practice this
solution works fine. However, in a few applications one would prefer a solution
that always works and cannot fail due to an unlikely series of random numbers.
Think about safety control in a nuclear power plant.
One improvement to Fig. 2-46 that has no deadlock and no starvation is to pro-
tect the five statements following the call to
think
by a binary semaphore. Before
starting to acquire forks, a philosopher would do a
down
on
mutex
.
After replacing
the forks, she would do an
up
on
mutex
.
From a theoretical viewpoint, this solu-
tion is adequate. From a practical one, it has a performance bug: only one philoso-
pher can be eating at any instant. With five forks available, we should be able to
allow two philosophers to eat at the same time.
The solution presented in Fig. 2-47 is deadlock-free and allows the maximum
parallelism for an arbitrary number of philosophers.
It uses an array,
state
, to keep
track of whether a philosopher is eating, thinking, or hungry (trying to acquire
forks). A philosopher may move into eating state only if neither neighbor is eat-
ing. Philosopher
i
’s neighbors are defined by the macros
LEFT
and
RIGHT
.
In
other words, if
i
is 2,
LEFT
is 1 and
RIGHT
is 3.
The program uses an array of semaphores, one per philosopher, so hungry
philosophers can block if the needed forks are busy. Note that each process runs
the procedure
philosopher
as its main code, but the other procedures,
take
forks
,
put
forks
, and
test
, are ordinary procedures and not separate processes.
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
