Today’s Topics

‹ Semaphores
COS 318: Operating Systems ‹ Monitors
‹ Mesa-style monitors
Semaphores, Monitors and ‹ Programming idiom
Condition Variables

Kai Li
Computer Science Department
Princeton University

(http://www.cs.princeton.edu/courses/cos318/)

Semaphores (Dijkstra, 1965) Bounded Buffer with Semaphores

‹ Initialization producer() { consumer() {
z Initialize a value atomically while (1) { while (1) {
‹ P (or Down or Wait) definition produce an item P(fullCount);
P(emptyCount);
z Atomic operation
P(mutex);
z Wait for semaphore to become positive and then decrement P(mutex); take an item from buffer
P(s){ put the item in buffer V(mutex);
while (s <= 0) V(mutex);
; V(emptyCount);
s--; V(fullCount); consume the item
} } }
‹ V (or Up or Signal) definition } }
z Atomic operation
z Increment semaphore by 1
‹ Initialization: emptyCount = N; fullCount = 0
V(s){ ‹ Are P(mutex)and V(mutex) necessary?
s++;
}

3
Implementation Motivation

P(sem) { V(sem) { ‹ A shared queue has Enqueue and Dequeue:

while (!TAS(sem.guard)) while (!TAS(sem.guard))
; ; Enqueue(q, item) Dequeue(q)
sem.value--; sem.value++; { {
if (sem.value < 0) { if (sem.value <= 0) Acquire(mutex); Acquire(mutex);
enqueue self to sem.q; dequeue sem.q; put item into q; take an item from q;
schedule & sem.guard = 0; make thread ready; Release(mutex); Release(mutex);
}; }; } return item;
sem.guard = 0; sem.guard = 0; }
} }

‹ It is a consumer and producer problem

z Dequeue(q) blocks until q is not empty
‹ Would this work?
‹ Semaphores are difficult to use: orders are important

Monitor: Hide Mutual Exclusion Condition Variables in A Monitor

Queues
‹ Brinch-Hansen (73), Hoare (74) ‹ Wait( condition )
associated
‹ Procedures are mutual exclusive z Block on “condition” with x, y
‹ Signal( condition ) conditions
Shared z Wakeup a blocked process x
y
data on “condition”
Queue of waiting processes ‹ Conditions are not “sticky” Shared
trying to enter the monitor data
...

procedures ...
Entry queue
procedures
Producer-Consumer with Monitors Options of the Signaler
‹ Run the signaled thread immediately and suspend the
monitor ProdCons
condition full, empty;
current one (Hoare)
procedure Producer
begin
z If the signaler has other work to do, life is complex
procedure Enter;
begin
while true do z It is difficult to make sure there is nothing to do, because the
begin
if (buffer is full)
produce an item
signal implementation is not aware of how it is used
wait(full);
put item into buffer;
ProdCons.Enter(); z It is easy to prove things
end;
if (only one item)
signal(empty);
end; ‹ Exit the monitor (Hansen)
end;
procedure Consumer
z Signal must be the last statement of a monitor procedure
procedure Remove;
begin
while true do
‹ Continues its execution (Mesa)
begin
if (buffer is empty)
begin z Easy to implement
ProdCons.Remove();
wait(empty);
consume an item; z But, the condition may not be true when the awaken process
remove an item;
if (buffer was full)
end; actually gets a chance to run
end;
signal(full);
end;
10

Mesa Style “Monitor” (Birrell’s Paper) Consumer-Producer with Mesa-Style Monitor

‹ Associate a condition variable with a mutex static count = 0;
‹ Wait( mutex, condition ) static Cond full, empty;
z Atomically unlock the mutex and enqueued on the condition static Mutex lock;
variable (block the thread)
z Re-lock the lock when it is awaken Enter(Item item) { Remove(Item item) {
Acquire(lock); Acquire(lock);
‹ Signal( condition ) if (count==N) if (!count)
z No-op if there is no thread blocked on the condition variable Wait(lock, full); Wait(lock, empty);
z Wake up at least one if there are threads blocked insert item into buffer remove item from buffer
count++; count--;
‹ Broadcast( condition ) if (count==1) if (count==N-1)
z Wake up all waiting threads Signal(empty); Signal(full);
‹ Original Mesa paper Release(lock); Release(lock);
z B. Lampson and D. Redell. Experience with processes and } }
monitors in Mesa. Comm. ACM 23, 2 (feb 1980), pp 106-117.
Any issues with this?
12
Consumer-Producer with Mesa-Style Monitor The Programming Idiom
‹ Waiting for a resource ‹ Make a resource available
static count = 0;
static Cond full, empty;
Acquire( mutex ); Acquire( mutex );
static Mutex lock;
while ( no resource ) ...
Enter(Item item) { Remove(Item item) { wait( mutex, cond ); (make resource available)
Acquire(lock); Acquire(lock); ... ...
while (count==N) while (!count) (use the resource) Signal( cond );
Wait(lock, full); Wait(lock, empty); ... /* or Broadcast( cond );
insert item into buffer remove item from buffer Release( mutex); Release( mutex);
count++; count--;
if (count==1) if (count==N-1)
Signal(empty); Signal(full);
Release(lock); Release(lock);
} }

13 14

Revisit the Motivation Example Condition Variables Primitives

‹ Wait( mutex, cond ) ‹ Signal( cond )
Enqueue(Queue q, Item GetItem(Queue q) {
Item item) { Item item; z Enter the critical section z Enter the critical section
(min busy wait) (min busy wait)
Acquire(lock); Acquire( lock ); z Release mutex z Wake up a TCB in cond’s
while ( q is empty )
z Put my TCB to cond’s queue
insert an item to q; Wait( lock, Empty);
queue z Exit the critical section
Signal(Empty); remove an item; z Call scheduler
Release(lock);
} Release( lock ); z Exit the critical section
return item; . . . (blocked)
}

z Waking up:
• Acquire mutex
‹ Can this be further improved?
• Resume

16
More on Mesa-Style Monitor Evolution of Monitors
‹ Signaler continues execution ‹ Brinch-Hansen (73) and Hoare Monitor (74)
z Concept, but no implementation
‹ Waiter simply put on ready queue, with no special z Requires Signal to be the last statement (Hansen)
priority z Requires relinquishing CPU to signaler (Hoare)
z Must then spin and reevaluate the condition ‹ Mesa Language (77)
z Monitor in language, but signaler keeps mutex and CPU
‹ No constraints on when the waiting thread/process must z Waiter simply put on ready queue, with no special priority
run after a “signal” ‹ Modula-2+ (84) and Modula-3 (88)
‹ Simple to introduce a broadcast: wake up all z Explicit LOCK primitive
z Mesa-style monitor
‹ No need to make signal sticky ‹ Pthreads (95)
‹ No constrains on signaler z Started standard effort around 1989
z Defined by ANSI/IEEE POSIX 1003.1 Runtime library
z Can execute after signal call (Hansen’s cannot)
‹ Java threads
z Do not need to relinquish control to awaken thread/process z James Gosling in early 1990s without threads
z Use most of the Pthreads primitives

Example: A Simple Barrier Using Semaphores as A Barrier

‹ Thread A and Thread B ‹ Use two semaphores
want to meet at a Thread A Thread B init(s1, 0);
particular point and then init(s2, 0);
go on
Thread A Thread B
‹ How would you program … …
V(s1); V(s2);
this with monitor?
P(s2); P(s1);
… …

19 20
Example: Interrupt Handler Use Semaphore to Signal
‹ A device thread works with an interrupt handler
‹ What to do with shared data? Init(s,0);
‹ What if “m” is held by another thread or by itself?
Device thread Interrupted Thread
while (1) {
Device thread Interrupt handler P(s); …
Acquire(m); Interrupt handler
... ... ... ... Interrupt
Acquire(); Acquire(); deal with interrupt V(s); …
...

Release();
...
? ...

Release();
...
}
...
Release(m);
...

21 22

Equivalence Summary
‹ Semaphores ‹ Semaphores
z Good for signaling ‹ Monitors
z Not good for mutex because it is easy to introduce a bug z Hoare’s
‹ Monitors z Mesa-style and its idiom
z Good for scheduling and mutex ‹ Examples
z Maybe costly for a simple signaling z Use cases for semaphores

23 24