|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 160-161 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 160
SEC. 2.3
INTERPROCESS COMMUNICATION
129
#define N 100
/
*
number of slots in the buffer
*
/
int count = 0;
/
*
number of items in the buffer
*
/
void producer(void)
{
int item;
while (TRUE) {
/
*
repeat forever
*
/
item = produce
item( );
/
*
generate next item
*
/
if (count == N) sleep( );
/
*
if buffer is full, go to sleep
*
/
insert
item(item);
/
*
put item in buffer
*
/
count = count + 1;
/
*
increment count of items in buffer
*
/
if (count == 1) wakeup(consumer);
/
*
was buffer empty?
*
/
}
}
void consumer(void)
{
int item;
while (TRUE) {
/
*
repeat forever
*
/
if (count == 0) sleep( );
/
*
if buffer is empty, got to sleep
*
/
item = remove
item( );
/
*
take item out of buffer
*
/
count = count
−
1;
/
*
decrement count of items in buffer
*
/
if (count == N
−
1) wakeup(producer);
/
*
was buffer full?
*
/
consume
item(item);
/
*
print item
*
/
}
}
Figure 2-27.
The producer-consumer problem with a fatal race condition.
instant, the scheduler decides to stop running the consumer temporarily and start
running the producer. The producer inserts an item in the buffer, increments
count
,
and notices that it is now 1.
Reasoning that
count
was just 0, and thus the consu-
mer must be sleeping, the producer calls
wakeup
to wake the consumer up.
Unfortunately, the consumer is not yet logically asleep, so the wakeup signal is
lost. When the consumer next runs, it will test the value of
count
it previously read,
find it to be 0, and go to sleep. Sooner or later the producer will fill up the buffer
and also go to sleep.
Both will sleep forever.
The essence of the problem here is that a wakeup sent to a process that is not
(yet) sleeping is lost.
If it were not lost, everything would work. A quick fix is to
modify the rules to add a
wakeup waiting bit
to the picture. When a wakeup is
sent to a process that is still awake, this bit is set.
Later, when the process tries to
go to sleep, if the wakeup waiting bit is on, it will be turned off, but the process
will stay awake. The wakeup waiting bit is a piggy bank for storing wakeup sig-
nals. The consumer clears the wakeup waiting bit in every iteration of the loop.
Page 161
130
PROCESSES AND THREADS
CHAP. 2
While the wakeup waiting bit saves the day in this simple example, it is easy to
construct examples with three or more processes in which one wakeup waiting bit
is insufficient. We could make another patch and add a second wakeup waiting bit,
or maybe 8 or 32 of them, but in principle the problem is still there.
2.3.5 Semaphores
This was the situation in 1965, when E. W. Dijkstra (1965) suggested using an
integer variable to count the number of wakeups saved for future use.
In his pro-
posal, a new variable type, which he called a
semaphore
, was introduced.
A sem-
aphore could have the value 0, indicating that no wakeups were saved, or some
positive value if one or more wakeups were pending.
Dijkstra proposed having two operations on semaphores, now usually called
down
and
up
(generalizations of
sleep
and
wakeup
, respectively). The
down
oper-
ation on a semaphore checks to see if the value is greater than 0.
If so, it decre-
ments the value (i.e., uses up one stored wakeup) and just continues.
If the value is
0, the process is put to sleep without completing the
down
for the moment. Check-
ing the value, changing it, and possibly going to sleep, are all done as a single,
indivisible
atomic action
.
It is guaranteed that once a semaphore operation has
started, no other process can access the semaphore until the operation has com-
pleted or blocked. This atomicity is absolutely essential to solving synchronization
problems and avoiding race conditions. Atomic actions, in which a group of related
operations are either all performed without interruption or not performed at all, are
extremely important in many other areas of computer science as well.
The
up
operation increments the value of the semaphore addressed.
If one or
more processes were sleeping on that semaphore, unable to complete an earlier
down
operation, one of them is chosen by the system (e.g., at random) and is al-
lowed to complete its
down
.
Thus, after an
up
on a semaphore with processes
sleeping on it, the semaphore will still be 0, but there will be one fewer process
sleeping on it. The operation of incrementing the semaphore and waking up one
process is also indivisible. No process ever blocks doing an
up
, just as no process
ever blocks doing a
wakeup
in the earlier model.
As an aside, in Dijkstra’s original paper, he used the names
P
and
V
instead of
down
and
up
, respectively.
Since these have no mnemonic significance to people
who do not speak Dutch and only marginal significance to those who do—
Proberen
(try) and
Verhogen
(raise, make higher)—we will use the terms
down
and
up
instead. These were first introduced in the Algol 68 programming language.
Solving the Producer-Consumer Problem Using Semaphores
Semaphores solve the lost-wakeup problem, as shown in Fig. 2-28. To make
them work correctly, it is essential that they be implemented in an indivisible way.
The normal way is to implement
up
and
down
as system calls, with the operating
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
