Transcript Chapter 5 Concurrency: Mutual Exclusion and Synchronization

Chapter 5
Concurrency: Mutual Exclusion and
Synchronization
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
1
Multiple Processes
• Central to the design of modern Operating
Systems is managing multiple processes
– Multiprogramming
– Multiprocessing
– Distributed Processing
• Big Issue is Concurrency
– Managing the interaction of all of these
processes
2
Interleaving and
Overlapping Processes
• Earlier (Ch2) we saw that processes may
be interleaved on uniprocessors
3
Interleaving and
Overlapping Processes
• And not only interleaved but overlapped on
multi-processors
• Both interleaving and overlapping present the
same problems in concurrent processing
4
One Difficulty of
Concurrency
• Sharing of global resources can be
problematic
5
A Simple Example
Suppose echo is a shared procedure
and P1 echoes ‘x’ and P2 echoes ‘y’
void echo()
{ // send a keyboard-input character to display
chin = getchar();
What would happen if P1 is
interrupted here by P2?
chout = chin;
putchar(chout);
}
What would happen if only one process is
permitted at a time to be in the procedure?
6
A Simple Example:
On a Multiprocessor
Process P1
.
chin = getchar();
.
chout = chin;
putchar(chout);
.
.
Process P2
.
.
chin = getchar();
chout = chin;
.
putchar(chout);
.
7
Enforce Single Access
• If we enforce a rule that only one process may
enter the function at a time then:
– P1 & P2 run on separate processors
– P1 enters echo first,
• P2 tries to enter but is blocked
– P1 completes execution
• P2 resumes and executes echo
Solution: Control access
to shared resource
8
Competition among
Processes for Resources
Three main control problems:
• Need for Mutual Exclusion
– Only one program at a time be allowed in its
critical section.
– Critical resource: nonsharable resource,
e.g., printer
– Critical section: portion of the program that
uses a critical resource
• Deadlock
• Starvation
9
Requirements for
Mutual Exclusion
• Only one process at a time is allowed in
the critical section for a resource
• A process that halts in its noncritical
section must do so without interfering with
other processes
• No deadlock or starvation
10
Requirements for
Mutual Exclusion
• A process must not be delayed access to
a critical section when there is no other
process using it
• No assumptions are made about relative
process speeds or number of processes
• A process remains inside its critical section
for a finite time only
11
Roadmap
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
12
Disabling Interrupts
• Uniprocessors only allow interleaving
• Interrupt Disabling
– A process runs until it invokes an operating
system service or until it is interrupted
– Disabling interrupts guarantees mutual
exclusion because the critical section cannot
be interrupted
13
Pseudo-Code
while (true) {
/*
/*
/*
/*
disable interrupts */;
critical section */;
enable interrupts */;
remainder */;
}
–  Reduced interleaving
–  Will not work in multiprocessor architecture
14
Special Machine
Instructions
• Use of atomic action: instruction is treated
as a single step that cannot be interrupted
– Compare&Swap Instruction
int compare_and_swap (int *word,
int testval, int newval)
{ /* checks a memory location (*word) against a test value (testval) */
int oldval;
oldval = *word;
if (oldval == testval) *word = newval;
return oldval;
}
15
Mutual Exclusion (fig 5.2)
• The only process
that may enter its
critical section is
one that finds bolt
equal to 0
• All other
processes go into
a busy waiting
mode
16
Hardware Mutual
Exclusion: Advantages
• Applicable to any number of processes on
either a single processor or multiple
processors sharing main memory
• It is simple and therefore easy to verify
• It can be used to support multiple critical
sections
17
Hardware Mutual
Exclusion: Disadvantages
• Busy-waiting consumes processor time
• Starvation is possible when a process leaves a
critical section and more than one process is
waiting
– Some process could indefinitely be denied access
because selection of a waiting process is arbitrary
• Deadlock is possible
– Example: P1 enters its critical section and is then
preempted by higher priority P2 which will go into a
busy waiting loop
18
Roadmap
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
19
Semaphore
• Fundamental principle: Processes can
cooperate by means of simple signal such
that a process can be forced to stop at a
specified place until it has received a
specific signal.
20
Semaphore
• Semaphore:
– An integer value used for signalling among
processes
• Only three operations may be performed
on a semaphore, all of which are atomic:
– initialize (to a nonnegative integer value)
– decrement (semWait), to receive a signal
– increment (semSignal), to transmit a signal
21
Semaphore Primitives
22
Binary Semaphore
Primitives
23
Strong/Weak
Semaphore
• A queue is used to hold processes waiting
on the semaphore
– In what order are processes removed from
the queue?
• Strong Semaphores use FIFO
• Weak Semaphores don’t specify the
order of removal from the queue
24
Mutual Exclusion Using
Semaphores
1. The first process that executes a
semWait will be able to enter the
critical section immediately,
setting the value of s to 0
2. Any other processes attempting
to enter the critical section will
find it busy and will be blocked
25
Processes Accessing
Shared Data Using
Semaphore
Three processes
(A,B,C) access a
shared resource
protected by the
semaphore lock.
26
Mutual Exclusion Using
Semaphores
• The semaphore can be initialized to a
specified value to allow more than one
process in its critical section at a time
– s.count  0: the number of processes that can
execute semWait(s) without suspension
– s.count < 0: the magnitude is the number
processes suspended in s.queue
27
Producer/Consumer
Problem
• General Situation:
– One or more producers are generating data and
placing these in a buffer
– A single consumer is taking items out of the buffer
one at time
– Only one producer or consumer may access the
buffer at any one time
• The Problem:
– Ensure that the Producer can’t add data into full buffer
and consumer can’t remove data from empty buffer
28
Functions
• Assume an infinite buffer b with a linear array of
elements
Producer
while (true) {
/* produce item v */
b[in] = v;
in++;
}
Consumer
while (true) {
while (in <= out)
/*do nothing */;
w = b[out];
out++;
/* consume item w */
}
29
Buffer
The consumer must
make sure that the
producer has
advanced beyond it
(in > out) before
proceeding
The producer can
generate items and
store them in the buffer
at its own pace. Each
time, in is incremented
30
Semaphores
n is equal to the number of items
in the buffer
Prevent the consumer and any
other producer from accessing
the buffer during the append
operation
The consumer must wait on both
semaphores before proceeding
31
Bounded Buffer
The buffer is treated as a circular
storage; pointer values are expressed
modulo the size of the buffer
32
Functions in a
Bounded Buffer
in and out are initialized to 0 and n is the size of the buffer
Producer
while (true) {
/* produce item v */
while ((in + 1) % n == out)
/* do nothing */;
b[in] = v;
in = (in + 1) % n
}
Consumer
while (true) {
while (in == out)
/* do nothing */;
w = b[out];
out = (out + 1) % n;
/* consume item w */
}
33
Semaphores
e keeps track of the number
of empty spaces
34
Roadmap
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
35
Readers/Writers Problem
• A data area (e.g., a file) is shared among
many processes
– Some processes (readers) only read the data
area, some (writers) only write to the area
• Conditions to satisfy:
1.Multiple readers may simultaneously read the file
2.Only one writer at a time may write
3.If a writer is writing to the file, no reader may
read it
36
Readers have Priority
readcount keeps track of the
number of readers
x is used to assure that
readcount is updated properly
the first reader that attempts
to read should wait on wsem
wsem is used to enforce
mutual exclusion: as long as
one writer is accessing the
shared data area, no other
writers and no readers may
access it
37
Readers/Writers Problem
• Once a single reader has begun to access
the data area, it is possible for readers to
retain control of the data area as long as
there is at least one reader reading.
– Therefore, writers are subject to starvation
• An alternative solution: no new readers
are allowed access to the data area once
at least one writer wants to write
38
Writers have Priority
y controls the updating of
writecount
writecount controls the setting
of rsem
rsem inhibits all readers while
there is at least one writer
desiring access to the data area
39
Writers have Priority
only one reader is allowed to
queue on rsem, with any
additional readers queuing on z
40
Writers have Priority
41
Key Terms
42