|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 158-159 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 158
SEC. 2.3
INTERPROCESS COMMUNICATION
127
enter
region:
TSL REGISTER,LOCK
| copy lock to register and set lock to 1
CMP REGISTER,#0
| was lock zero?
JNE enter
region
| if it was not zero, lock was set, so loop
RET
| return to caller; critical region entered
leave
region:
MOVE LOCK,#0
| store a 0 in lock
RET
| return to caller
Figure 2-25.
Entering and leaving a critical region using the
TSL
instruction.
An alternative instruction to
TSL
is
XCHG
, which exchanges the contents of two
locations atomically, for example, a register and a memory word. The code is
shown in Fig. 2-26, and, as can be seen, is essentially the same as the solution with
TSL
.
All Intel x86 CPUs use
XCHG
instruction for low-level synchronization.
enter
region:
MOVE REGISTER,#1
| put a 1 in the register
XCHG REGISTER,LOCK
| swap the contents of the register and lock variable
CMP REGISTER,#0
| was lock zero?
JNE enter
region
| if it was non zero, lock was set, so loop
RET
| return to caller; critical region entered
leave
region:
MOVE LOCK,#0
| store a 0 in lock
RET
| return to caller
Figure 2-26.
Entering and leaving a critical region using the
XCHG
instruction.
2.3.4 Sleep and Wakeup
Both Peterson’s solution and the solutions using
TSL
or
XCHG
are correct, but
both have the defect of requiring busy waiting. In essence, what these solutions do
is this: when a process wants to enter its critical region, it checks to see if the entry
is allowed. If it is not, the process just sits in a tight loop waiting until it is.
Not only does this approach waste CPU time, but it can also have unexpected
effects. Consider a computer with two processes,
H
, with high priority, and
L
, with
low priority. The scheduling rules are such that
H
is run whenever it is in ready
state. At a certain moment, with
L
in its critical region,
H
becomes ready to run
(e.g., an I/O operation completes).
H
now begins busy waiting, but since
L
is never
Page 159
128
PROCESSES AND THREADS
CHAP. 2
scheduled while
H
is running,
L
never gets the chance to leave its critical region, so
H
loops forever. This situation is sometimes referred to as the
priority inversion
problem
.
Now let us look at some interprocess communication primitives that block in-
stead of wasting CPU time when they are not allowed to enter their critical regions.
One of the simplest is the pair
sleep
and
wakeup
.
Sleep
is a system call that
causes the caller to block, that is, be suspended until another process wakes it up.
The
wakeup
call has one parameter, the process to be awakened. Alternatively,
both
sleep
and
wakeup
each have one parameter, a memory address used to match
up
sleep
s with
wakeup
s.
The Producer-Consumer Problem
As an example of how these primitives can be used, let us consider the
pro-
ducer-consumer
problem (also known as the
bounded-buffer
problem). Two
processes share a common, fixed-size buffer. One of them, the producer, puts infor-
mation into the buffer, and the other one, the consumer, takes it out.
(It is also pos-
sible to generalize the problem to have
m
producers and
n
consumers, but we will
consider only the case of one producer and one consumer because this assumption
simplifies the solutions.)
Trouble arises when the producer wants to put a new item in the buffer, but it is
already full. The solution is for the producer to go to sleep, to be awakened when
the consumer has removed one or more items. Similarly, if the consumer wants to
remove an item from the buffer and sees that the buffer is empty, it goes to sleep
until the producer puts something in the buffer and wakes it up.
This approach sounds simple enough, but it leads to the same kinds of race
conditions we saw earlier with the spooler directory.
To keep track of the number
of items in the buffer, we will need a variable,
count
.
If the maximum number of
items the buffer can hold is
N
, the producer’s code will first test to see if
count
is
N
.
If it is, the producer will go to sleep; if it is not, the producer will add an item and
increment
count
.
The consumer’s code is similar: first test
count
to see if it is 0.
If it is, go to
sleep; if it is nonzero, remove an item and decrement the counter. Each of the proc-
esses also tests to see if the other should be awakened, and if so, wakes it up. The
code for both producer and consumer is shown in Fig. 2-27.
To express system calls such as
sleep
and
wakeup
in C, we will show them as
calls to library routines. They are not part of the standard C library but presumably
would be made available on any system that actually had these system calls. The
procedures
insert
item
and
remove
item
, which are not shown, handle the
bookkeeping of putting items into the buffer and taking items out of the buffer.
Now let us get back to the race condition.
It can occur because access to
count
is unconstrained. As a consequence, the following situation could possibly occur.
The buffer is empty and the consumer has just read
count
to see if it is 0.
At that
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
