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
Difficulties of
Concurrency
• Sharing of global resources
– consider two processes perform reads and
writes on the same global variable
• Optimally managing the allocation of
resources is difficult
• Difficult to locate programming errors as
results are not deterministic and
reproducible.
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
Race Condition
• A race condition occurs when
– Multiple processes or threads read and write
data items
– They do so in a way where the final result
depends on the order of execution of the
processes
• The output depends on who finishes the
race last (the loser)
• However, the processes and outputs must
be independent of the processing speed
9
Process Interaction
Example: multiprogramming of
multiple independent processes
Example: processes share access to
some object, such as an I/O buffer
Example: Processes designed to
work jointly on some activity
10
Competition among
Processes for Resources
Three main control problems:
• Need for Mutual Exclusion
– Critical resource: nonsharable resource, e.g.,
printer
– Critical section: portion of the program that
uses a critical resource
• Deadlock
• Starvation
11
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
12
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
13
Roadmap
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
14
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
15
Pseudo-Code
while (true) {
/*
/*
/*
/*
disable interrupts */;
critical section */;
enable interrupts */;
remainder */;
}
–  Reduced interleaving
–  Will not work in multiprocessor architecture
16
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;
}
17
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
18
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
19
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
20
Roadmap
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
21
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)
– increment (semSignal)
22
Semaphore Primitives
23
Binary Semaphore
Primitives
24
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
25
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
26
Processes Accessing
Shared Data Using
Semaphore
Three processes
(A,B,C) access a
shared resource
protected by the
semaphore lock.
27
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
28
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
Producer/Consumer Animation
29
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 */
}
30
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
31
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
32
Bounded Buffer
The buffer is treated as a circular
storage; pointer values are expressed
modulo the size of the buffer
33
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 */
}
34
Semaphores
e keeps track of the number
of empty spaces
35
Demonstration
Animations
• Producer/Consumer
– Illustrates the operation of a producer-consumer
buffer.
• Bounded-Buffer Problem Using Semaphores
– Demonstrates the bounded-buffer consumer/producer
problem using semaphores.
36
Roadmap
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
37
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
interaction of readers and
writers.
38
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
39
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
40
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
41
Writers have Priority
only one reader is allowed to
queue on rsem, with any
additional readers queuing on z
42
Writers have Priority
43
Key Terms
44