Transcript Hardware solutions

Semaphores
Operating System
support for
concurrency
Motivation
• Goal is to eliminate busy waiting
– See Sec. 2.3.4, p. 108
• Consider a simplified version of the semaphore
first:
– Sleep – block if waiting to get into critical section
– Wake-up – unblock, or move from blocked to ready
• A little too simple
– Vulnerable to race conditions…
Sleep and Wakeup
Producer-consumer problem with fatal race condition
Semaphores
• A semaphore S is an integer variable that,
apart from initialization, is accessed only
through two standard atomic operations
wait (down) and signal (up) .
– Atomic
– S may be
• binary – used to enforce mutual exclusion (mutex)
or synchronize processes;
• counting – used to synchronize processes
About semaphores...
• Invented by Edsgar Dijkstra in 1965
– He was a famous Dutch computer scientist who
passed away in 2004…
• Generalized locking mechanisms
– They count the number of saved wake-ups
– May be implemented in hardware or software
• Got milk? example :
wait(S) [or down(S)]
if no milk then buy milk
signal(S) [or up(S)]
wait & signal operations
wait (S):
while S <= 0 do no-op;
S = S - 1;
as soon as S > 0
signal (S): S = S + 1;
• S is initialized to a value >= 1 why not 0? when >0?
• wait & signal are executed atomically
– if one process is modifying the semaphore, no other
process can do so.
– in the wait, the testing of the semaphore and the
modification is un-interruptible.
Semaphores are data structures
• They have the following basic operations
associated with them:
– initialize
– wait
– signal
Recall the n-process
Critical Section problem
• We can use a semaphore to guarantee
simple mutual exclusion. S is initialized to
1, and the code for each process is as
follows:
repeat
wait (S)
critical section
signal (S)
remainder section
until false;
Easier
than the
bakery
algorithm!
BACI implementation of
semaphores
• semaphore S; declares S to be type semaphore
• initialsem(S, value) initializes semaphore S to
a given value
• signal(S)
• wait(S)
Synchronizing processes
• Suppose p1 contains statement s1 and p2
contains statement s2
– s2 can execute only after s1 has completed
– it’s a synchronization issue
• Use semaphore sync, initialized to 0:
in p1: s1
in p2: wait (sync)
signal (sync)
s2
Aren’t we still busy waiting?
• All solutions we’ve seen so far spend a lot
of time doing nothing: while ..... do no-op;
– This wastes CPU cycles that would otherwise
be available for other processes
• We address the problem of busy waiting by
modifying the semaphore so that wait &
signal enable a process to block itself rather
than spin its wheels.
Recall process states
READY
RUNNING
BLOCKED
We will complicate this model slightly
The block operation
• Puts the process (thread) in a semaphore’s queue.
• Process state changes from running to blocked.
– It’s blocked waiting on the semaphore
• Now another process or thread can execute.
• The blocked process will become ready when
some other process executes a signal operation on
the same semaphore.
– Then, the process is placed in the ready queue.
How this is implemented
• Define semaphore as a class object or struct:
value
List of waiting processes
• When a process must wait on a semaphore, it
is added to its list of blocked processes. A
signal operation removes one process from
the list and wakes it up.
Operations wait & signal
are now more complex
wait(S)
S.value := S.value - 1;
if S.value < 0 then
{
add this process to S.list;
block;
}
signal(S)
S.value := S.value + 1;
if S.value <= 0 then
{
remove a process
from S.list;
wakeup(process);
}
block & wakeup are provided by the OS (system calls)
Some observations
• The order in which processes are awakened depends
on the CPU scheduling algorithm (not always FCFS)
• Always remember that wait & signal are executed
atomically.
– So, no two processes can execute wait or signal operations
on the same semaphore at the same time.
• If we have only one processor, we can inhibit
interrupts during the time the wait and signal
operations are executing. This will not work in a
multiprocessing environment.
Some more observations
• Semaphore values in this later definition
can actually become negative.
– What would a negative value signify?
• Busy waiting has not actually been
eliminated, just mitigated
– it’s been moved to the wait & signal operations
– why is this preferable?
Deadlock
• When we use a semaphore with a waiting
queue, we may create a situation in which
two or more processes are waiting for an
event (a signal operation) that can be
caused only by one of the waiting
processes. When such a state is reached,
these processes are said to be deadlocked.
• Formal def of deadlock in Chapter 3
Starvation
• Another related problem is indefinite
postponement or starvation. This happens
when processes must wait indefinitely and
may occur if we add processes to (and
remove them from) the semaphore list in
LIFO order.
Some Classical Synchronization
Problems (Sec. 2.4)
• These scenarios are used to test synchronization
schemes:
–
–
–
–
Bounded Buffer
Readers Writers
Dining Philosophers
Sleeping Barber
• Solutions here rely on semaphores, but next time
we’ll see another approach.
Examples of producer-consumer
processes
Producer
• Output process stores
characters in a buffer
• Assembler process
produces object code
Consumer
• Printer driver reads
characters from buffer
• Linker/loader
process forms object
code into a run unit
Bounded Buffer (ProducerConsumer) Problem
• Assume a buffer of size N.
• mutex (initialized to 1)
– Provides mutual exclusion.
• empty and full (both semaphores) count the
number of buffers that are empty and full
resp. Empty initialized to N and full to 0
– Used for synchronizing the processes
Producer Consumer problem
Readers and Writers
• If two (or more) readers access the shared file at
the same time, there is no problem.
• However, we cannot allow a writer to access the
shared file at the same time as another process
(either a reader or writer). Why?
• So we give the writers exclusive access to the file.
• BUT, no reader will be kept waiting unless a writer
has already gained access to the file
• So, readers have a certain degree of priority over
writers...
The solution
• Initialize an integer variable rc to 0
– rc is used to count the number of readers
– Mutual exclusion is required for any reader
process to update rc
• Initialize two semaphores, mutex (mutual
exclusion while updating rc) and db (mutual
exclusion for the writers), both to 1.
The Readers and Writers Problem
The Dining Philosophers
Models allocating
several resources
among several
processes.
Correct solutions are
free of both deadlock
and starvation.
The problem
• We have 5 (or more) philosophers who eat &
think all day. They all sit around a circular table
that contains 5 plates and 5 single chopsticks,
placed one between each plate.
• In order to eat, a philosopher needs 2 chopsticks,
the one to the left of her plate and the one to the
right.
• When she finishes eating she puts down both
chopsticks.
A simple but flawed solution
• Initialize all elements of semaphore array
chopstick to 1. (chopstick[0]...chopstick[4])
repeat
wait (chopstick[i]);
wait (chopstick[(i+1) % 5]);
eat
signal (chopstick[i]);
signal (chopstick[(i+1) % 5]);
think;
until false;
What can we do to fix this?
• Allow at most 4 philosophers to sit at the
table set for five the same time
• Allow a philosopher to pick up her
chopsticks only if both are available.
• Use an asymmetric solution i.e., an odd
philosopher picks up the left and then the
right, an even philosopher picks up the right
and then the left.
Dining Philosophers solution
Part 1
Dining Philosophers solution
Part 2
The Sleeping Barber Problem
The Sleeping Barber solution