Transcript Document
6.5 Semaphore
Less complicated than the hardware-based solutions
Semaphore S – integer variable accessed only through two
standard atomic operations: wait() and signal()
Originally called P() and V()
wait (S) {
while S <= 0
; // no-op
S--;
}
signal (S) {
S++;
}
In wait(S), the testing of S (S <= 0) and S-- must be executed
without interruption
Operating System Principles
6.1
Silberschatz, Galvin and Gagne ©2005
Semaphore Usage
Counting semaphore – integer value can range over an
unrestricted domain
Binary semaphore – integer value can range only between 0 and
1; can be simpler to implement
Also known as mutex locks
Can implement a counting semaphore S by a binary semaphore
Provides mutual exclusion
semaphore mutex;
// initialized to 1
do {
wait (mutex);
// critical section
signal (mutex);
// remainder section
} while (TRUE);
Operating System Principles
6.2
Silberschatz, Galvin and Gagne ©2005
Semaphore Usage
Used in synchronization
If two concurrent processes P1 and P2 must be synchronized
such that S2 in P2 must be executed only after S1 of P1
semaphore synch; // initialized to 0
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
Operating System Principles
6.3
Silberschatz, Galvin and Gagne ©2005
Semaphore Implementation
Must guarantee that no two processes can execute wait
() and signal () on the same semaphore at the same
time
Thus, implementation becomes the critical section
problem where the wait and signal code are placed in
the critical section.
Could have busy waiting (called spinlock) in critical section
implementation
But implementation code is short
Little busy waiting if critical section rarely occupied
Note that applications may spend lots of time in critical sections
and therefore this is not a good solution.
Operating System Principles
6.4
Silberschatz, Galvin and Gagne ©2005
Semaphore Implementation with no Busy waiting
With each semaphore there is an associated waiting
queue. Each entry in a waiting queue has two data items:
value (of type integer): if value is negative, its magnitude is the
number of processes waiting on this semaphore
pointer to a process list: could be implemented as a queue to
ensure bounded waiting
typeof struct {
int value;
struct process *list;
} semaphore;
Two operations:
block – place the process invoking the operation on the appropriate
waiting queue.
wakeup – remove one of processes in the waiting queue and place it
in the ready queue.
Operating System Principles
6.5
Silberschatz, Galvin and Gagne ©2005
Semaphore Implementation with no Busy waiting (Cont.)
Implementation of wait:
wait (semaphore *S){
S->value- -;
if (S->value < 0) {
add this process to S’s waiting list
block( );
}
}
Implementation of signal:
signal (semaphore *S){
S->value++;
if (S->value <= 0) {
remove a process P from S’s waiting list
wakeup(P);
}
}
Operating System Principles
6.6
Silberschatz, Galvin and Gagne ©2005
Deadlock and Starvation
Deadlock – two or more processes are waiting
indefinitely for an event that can be caused by only one
of the waiting processes
Let S and Q be two semaphores initialized to 1
P0
P1
wait (S);
wait (Q);
wait (Q);
.
.
signal (S);
signal (Q);
wait (S);
.
.
signal (Q);
signal (S);
Starvation – indefinite blocking. A process may never
be removed from the semaphore queue in which it is
suspended.
Operating System Principles
6.7
Silberschatz, Galvin and Gagne ©2005
6.6 Classical Problems of Synchronization
Use semaphores for synchronization
Bounded-Buffer Problem
Readers and Writers Problem
Dining-Philosophers Problem
Operating System Principles
6.8
Silberschatz, Galvin and Gagne ©2005
Bounded-Buffer Problem
N buffers, each can hold one item
Semaphore mutex (for mutual exclusion) initialized to
the value 1
Semaphore full (counter for filled buffers) initialized to
the value 0
Semaphore empty (counter for empty buffers)
initialized to the value N
Operating System Principles
6.9
Silberschatz, Galvin and Gagne ©2005
Bounded Buffer Problem (Cont.)
The structure of the consumer
The structure of the producer
process
process
while (TRUE) {
while (TRUE) {
wait (full);
// produce an item
wait (mutex);
wait (empty);
wait (mutex);
// remove an item from buffer
signal (mutex);
// add the item to the buffer
signal (empty);
signal (mutex);
signal (full);
// consume the removed item
}
Operating System Principles
}
6.10
Silberschatz, Galvin and Gagne ©2005
Readers-Writers Problem
A data set is shared among a number of concurrent
processes
Readers – only read the data set; they do not perform any
updates
Writers – can both read and write.
Problem – allow multiple readers to read at the same
time. Only one single writer can access the shared data
at the same time. Writers must have exclusive access.
Variation problems
1.
No reader should be kept waiting unless a writer has obtained
permission to use the shared object
2.
Once a write is ready, that writer performs its write as soon as
possible
Operating System Principles
6.11
Silberschatz, Galvin and Gagne ©2005
Solution to Readers-Writers Problem
In the first problem, writers may starve; in the
second problem, reader may starve
Solution to the first problem
Shared Data
Data object
Semaphore mutex initialized to 1. It is to ensure mutual
exclusion when the variable readcount is updated.
Semaphore wrt initialized to 1. It is used as a mutual exclusion
semaphore for the writers. It is also used by the first or last
reader that enters or exits the critical section.
Integer readcount initialized to 0. It keeps track of how many
processes are currently reading the object.
Operating System Principles
6.12
Silberschatz, Galvin and Gagne ©2005
Readers-Writers Problem (Cont.)
The structure of a writer process
while (true) {
wait (wrt) ;
//
The structure of a reader process
while (true) {
wait (mutex) ;
readcount ++ ;
if (readercount == 1) wait (wrt) ;
signal (mutex)
writing is performed
// reading is performed
signal (wrt) ;
wait (mutex)
readcount - - ;
if (redacount == 0) signal (wrt) ;
signal (mutex) ;
}
}
Operating System Principles
6.13
Silberschatz, Galvin and Gagne ©2005
Readers-Writers Problem (Cont.)
If a writer is in the critical section, and n readers are waiting,
then one reader is queued on wrt, and n-1 readers are
queued on mutex
When a writer executes signal(wrt), we may resume the
execution of either the waiting readers or a single waiting
writer. The selection is made by the scheduler of the OS.
The readers-writers problem and its solution has been
generalized to provide reader-writer locks. Reader-writer
locks are useful in
Applications where it is easy to identify which processes only read
shared data and which only writes shared data
Applications that have more readers than writers, where the overhead
for setting up a reader-writer lock is compensated by the increased
concurrency of allowing multiple readers
Operating System Principles
6.14
Silberschatz, Galvin and Gagne ©2005
Dining-Philosophers Problem
A representation of the need to
allocate several resources among
several processes in a dead-lock
free and starvation-free manner.
Shared data
Bowl of rice (data set)
Semaphore chopstick [5] initialized to 1
Operating System Principles
6.15
Silberschatz, Galvin and Gagne ©2005
Dining-Philosophers Problem (Cont.)
The structure of Philosopher i:
while (true) {
wait ( chopstick[i] );
wait ( chopstick[ (i + 1) % 5] );
// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
}
Operating System Principles
6.16
Silberschatz, Galvin and Gagne ©2005
Dining-Philosophers Problem (Cont.)
The above solution could create a deadlock
How to prevent deadlock
Allow at most four philosophers to sit simultaneous in the
table
Allow a philosopher to pick up her chopsticks only if both
chopsticks are available (pick up in a critical section)
Use an asymmetric solution: an odd philosopher pick up
first her left chopstick and then her right chopstick;
whereas an even philosopher pick up first her right
chopstick and then her left chopstick
Note that a deadlock free solution does not
eliminate the possibility of starvation
Operating System Principles
6.17
Silberschatz, Galvin and Gagne ©2005
6.7 Problems with Semaphores
Correct use of semaphore operations:
wait(mutex) … signal(mutex)
Incorrect use of semaphore operations:
signal (mutex) …. wait (mutex): mutual exclusion violation
wait (mutex) … wait (mutex): deadlock
Omitting of wait (mutex) or signal (mutex) (or both): mutual
exclusion violation or deadlock
SKIP 6.7.1-6.7.4 Monitors
Operating System Principles
6.18
Silberschatz, Galvin and Gagne ©2005
6.8 Synchronization Examples
Windows XP Synchronization
Uses interrupt masks to protect access to global resources on
uniprocessor systems
Uses spinlocks on multiprocessor systems. The kernel uses
spinlocks only to protect short code segments. A thread will
never be preempted while holding a spinlock.
Also provides dispatcher objects which may act as either
mutexes and semaphores
Dispatcher objects may also provide events
An event acts much like a condition variable in monitor
Dispatcher objects may also provide timers, to notify a thread
that a specified amount of time has expired
SKIP 6.8.1 Solaris
SKIP 6.8.2 第 3 段之後
SKIP 6.8.4 Pthreads
Operating System Principles
6.19
Silberschatz, Galvin and Gagne ©2005
Linux Synchronization
Linux:
disables interrupts to implement short critical sections
Linux provides:
Semaphores (reader/writer version)
Spinlocks (reader/writer version) only for multiprocessors
For single processors, use enable/disable kernel
preemption
If a kernel is holding a lock, it is not preemptible
Operating System Principles
Each task in the system has a thread-info structure
containing a preempt_count counter to indicate the number
of locks held by the task
6.20
Silberschatz, Galvin and Gagne ©2005