Operating Systems
Semaphores II
Lecture: 18
Producer/Consumer Problem
• Consumer must wait for producer to fill buffers,
if none full
– (scheduling constraint)
• Producer must wait for consumer to empty
buffers, if all full
– (scheduling constraint)
• Only one thread can manipulate buffer queue
at a time
– (mutual exclusion)
Use a separate semaphore for each constraint
int BUFFER_SIZE = 100; int count = 0; P() is a
void producer(void) { int item; Generalization
while(TRUE) {
of Sleep()
produce_item(&item);
Mutual Exclusion
if(count == BUFFER_SIZE)
sleep ();
enter_item(item);
count++;
if(count == 1)
wakeup(consumer);
}} Scheduling
Scheduling
void consumer(void) { int item; Constraint 2
while(TRUE) { Constraint 1
if(count == 0)
sleep (); V() is a
remove_item(&item); Generalization of
count--; Wakeup()
if(count == BUFFER_SIZE - 1)
wakeup(producer);
consume_item(&item); }}
int BUFFER_SIZE = 100; int count = 0; P() is a
void producer(void) { int item; Generalization
while(TRUE) {
of Sleep()
produce_item(&item);
Mutual Exclusion
if(count == BUFFER_SIZE)
Sleep if buffer full
sleep ();
Get Exclusive Access of Queue
enter_item(item);
Leaveif(count
Exclusive ==
Access
1) of Queue
Wake up if first item in buffer
wakeup(consumer);
}} Scheduling
Scheduling
void consumer(void) { int item; Constraint 2
while(TRUE) { Constraint 1
if(count == 0)
Sleep if buffer empty
sleep (); V() is a
Get Exclusive Access of Queue Generalization of
remove_item(&item); Wakeup()
Leaveif(count
Exclusive ==
Access of Queue - 1)
BUFFER_SIZE
Wake up if space in buffer
wakeup(producer);
consume_item(&item); }}
int BUFFER_SIZE = 100; int count = 0; Semaphore
Empty(BUFFER_SIZE);
void producer(void) { int item; Semaphore full(0);
while(TRUE) { Semaphore CountMutex(1);
produce_item(&item);
Mutual Exclusion
empty->P();
Sleep if buffer full Pr
CountMutex->P(); od
Get Exclusive Access of Queue uso
enter_item(item); l v cer
ed / C
LeaveCountMutex->V();
Exclusive Access of Queue w on
Wake up if first item in buffer ith su
full->V();
Se me
}}
Scheduling
m rP
Scheduling
ap r
void consumer(void) { int item; Constraint 2 ho ob
while(TRUE) { re le1m
Constraint
s
full->P();
Sleep if buffer empty
CountMutex->P();
Get Exclusive Access of Queue
remove_item(&item);
LeaveCountMutex->V();
Exclusive Access of Queue
Wake up if space in buffer
empty->V();
consume_item(&item); }}
Semaphore API
• #include <semaphore.h>
• How to declare semaphore?
• sem_t S;
• Initialization… Max Value
• sem_init(&S,0,1);
• Decrement ( P())
• sem_wait(&S);
• Increment ( V() )
• sem_post(&S);
Example - Ping Pong…
• Suppose we have two threads A and B
• A and B are to repeatedly print out ping and pong,
respectively
• We want to execute them in an alternating order
• An alternating execution would force A and B to
print out in the order of
– ping pong ping pong ping pong
• Write the pseudocode of the thread A and B
• How can this be solved with and without
semaphores
Example - Threads
• A Thread creates 5 Threads. Thread 1 is created first,
Thread 2 is created second, Thread 3 is created third
and so on. Assume FIFO to be the scheduling policy.
Each thread prints the sequence number of its
creation. Write the code that will print exactly the
following:
• I am Thread 5, I was created at number 5
• I am Thread 3, I was created at number 3
• I am Thread 4, I was created at number 4
• I am Thread 1, I was created at number 1
• I am Thread 2, I was created at number 2
Example …
• A thread may delay its execution by calling a
function
• Void Delay(int second)
• The thread itself is blocked (no busy waiting by
this thread)
• Wakesup roughly after second
• Hint I: A new thread is spawned whenever delay
is called
• Hint II: Loops for delay?
int BUFFER_SIZE = 100; int count = 0; Semaphore
void producer(void) { int item; Empty(BUFFER_SIZE);
Semaphore full(0);
while(TRUE) { Semaphore CountMutex(1);
produce_item(&item);
empty->P();
CountMutex->P();
Wh
at w
enter_item(item); ill h
a ppe
CountMutex->V(); n if
full->V(); Cou emp we sw
ntM t a
}} ute y->P( p
void consumer(void) { int item; x-> );
P()
while(TRUE) { ;
full->P();
CountMutex->P();
remove_item(&item);
CountMutex->V();
empty->V();
consume_item(&item);
}}
int BUFFER_SIZE = 100; int count = 0; Semaphore
void producer(void) { int item; Empty(BUFFER_SIZE);
Semaphore full(0);
while(TRUE) { Semaphore CountMutex(1);
produce_item(&item);
CountMutex->P();
empty->P();
enter_item(item); Suppose the buffer is full
CountMutex->V(); Where is the producer???
full->V();
}}
Where is the consumer???
void consumer(void) { int item;
while(TRUE) {
full->P();
DEADLOCK
DEADLOCK
CountMutex->P();
remove_item(&item);
CountMutex->V();
empty->V();
consume_item(&item);
}}
Solution
• One has to be really careful while working with the
Semaphores
• Problem with semaphores:
– Used for both mutex
– and scheduling constraints.
• This makes the code hard to read, and hard to get
right.
• Monitor: A higher level synchronization primitive
• Separate these 2 concepts:
– use locks for mutual exclusion
– condition variables for scheduling constraints.
Monitor
• A Monitor consists of
– A lock
– Zero or more condition variables
• For managing concurrent access to shared
data
• Only one process can be active in the
monitor at a time
• Acquire the lock on entry and Release the lock before
returning.
• With condition variables, the module methods may
wait and signal on multiple independent conditions.
Locks: A simple example
AddToQueue() {
[Link](); // lock before using shared data
put item on queue; // ok to access shared data
[Link](); // unlock after done with shared data
}
RemoveFromQueue() {
[Link](); // lock before using shared data
if something on queue // ok to access shared data
remove it;
[Link](); // unlock after done with shared data
return item;
}
• “Roughly Equivalent” to a semaphore with value 1
– Restriction that the thread that “locks” must be the one that
unlocks it.
A simple example
• How do we change
RemoveFromQueue() to wait until
something is on the queue?
• Logically, want to go to sleep inside of
critical section
• But if hold lock when go to sleep?
– other threads won't be able to get in to add
things to the queue
– And then wake up the sleeping thread
Condition Variables:
• Sleep inside critical section, by atomically
releasing lock at same time we go to sleep
• Condition variable:
– A queue of threads
– Waiting for something inside a critical section.
Condition Variables: Support three
operations
• Wait()
– release lock, go to sleep, re-acquire lock
• Releasing lock and going to sleep is atomic
• Signal()
– wake up a waiter, if any
• Broadcast()
– wake up all waiters
• Rule: must hold lock when doing condition
variable operations.
A simple example
AddToQueue() {
[Link](); // lock before using shared
// data
put item on queue; // ok to access shared data
[Link]();
[Link](); // unlock after done with
// shared data
}
RemoveFromQueue() {
[Link]();
while nothing on queue
[Link](&lock);// release lock; go
// to sleep;
// re-acquire lock
remove item from queue;
[Link]();
return item;}
How is a conditional variable
different from Semaphore?
• What if thread calls V() and no one is waiting?
– Increment – Wakeup is saved.
• What if thread later does calls P()?
– Decrement and continue – Wakeup is used.
• P + V are commutative
– Result is the same no matter what order they occur.
• What if thread signals and no one is waiting?
– Nothing Happens – No Wakeups are saved.
• What if thread later waits?
– Thread waits.
How is a conditional variable
different from Semaphore?
• Conditional Variables are not counters
• Just unblock a thread if one is blocked on the
conditional variable
• No counter incremented/decremented
• Just like Sleep/Wakeup except that this is atomic
• That's why they must be accessed in a critical
section
• Before waiting, must check the state variables.
Producer/Consumer Problem with
Monitor
• Constraints
– 1. Producers can produce if buffer not full
• Condition: okToProduce
– 2. Consumers can consume if buffer not
empty
• Condition: okToConsume
– 3. Only one thread manipulates state
variables at a time.
int empty = BUFFER_SIZE;
void producer(void) { int item;
while(TRUE) {
produce_item(&item);
mutex->lock();
if(empty < = 0)
okToProduce->Wait(&mutex);
enter_item(item);
empty--;
okToConsume->Signal();
mutex->unlock();}}
void consumer(void) { int item;
while(TRUE) {
mutex->lock();
if(empty >= BUFFER_SIZE)
okToConsume->Wait(&mutex);
remove_item(&item);
empty++;
okToProduce->Signal();
mutex->unlock();
consume_item(&item);}}
