Announcements

Classic Sync Problems

Monitors

Synchronization Problems Producer-Consumer Problem

• Producer-Consumer Problem • Unbounded buffer
• Readers-Writers Problem • Producer process writes data to buffer
• Dining-Philosophers Problem – Writes to In and moves rightwards
• Consumer process reads data from buffer
– Reads from Out and moves rightwards
– Should not try to consume if there is no data

Out In

Need an infinite buffer

Producer-Consumer Problem Producer-Consumer Problem

• Bounded buffer: size ‘N’ • A number of applications:
• Producer process writes data to buffer – Compiler’s output consumed by assembler
– Should not write more than ‘N’ items – Assembler’s output consumed by loader
– Web server produces data consumed by client’s web browser
• Consumer process reads data from buffer
– Should not try to consume if there is no data • Example: pipe ( | ) in Unix
– > cat file | more
– > prog | sort … what happens here?

In Out

1
 Producer-Consumer Problem Producer-Consumer Problem
Shared: Semaphores mutex, empty, full;
First attempt to solve: Shared: int counter;
any_t buffer[N]; Init: mutex = 1; /* for mutual exclusion*/
Producer empty = N; /* number empty bufs */
Init: counter = 0; full = 0; /* number full bufs */
while (true) { Producer Consumer
/* produce an item in nextProduced*/
while (counter == N) do { do {
; /* do nothing */ ... P(full);
buffer[in] = nextProduced; Consumer // produce an item in nextp P(mutex);
in = (in + 1) % N; ... ...
counter++; while (true) { P(empty); // remove item to nextc
} while (counter == 0) P(mutex); ...
; /* do nothing */ ... V(mutex);
nextConsumed = buffer[out]; // add nextp to buffer V(empty);
out = (out + 1) % N; ... ...
counter--; V(mutex); // consume item in nextc
/* consume an item in nextConsumed*/ V(full); ...
} } while (true); } while (true);

Readers-Writers Problem Readers-Writers Problem

• Courtois et al 1971 • Many processes share a database
• Models access to a database • Some processes write to the database
• Example: airline reservation • Only one writer can be active at a time
• Any number of readers can be active simultaneously
• This problem is non-preemptive
– Wait for process in critical section to exit
• First Readers-Writers Problem:
– Readers get higher priority, and do not wait for a writer
• Second Readers-Writers Problem:
– Writers get higher priority over Readers waiting to read
• Courtois et al.

First Readers-Writers Readers-Writers Notes

Shared variables: Semaphore mutex, wrl;
integer rcount; Reader • If there is a writer
do { – First reader blocks on wrl
Init: mutex = 1, wrl = 1, rcount = 0; P(mutex);
rcount++; – Other readers block on mutex
if (rcount == 1) • Once a writer exists, all readers get to go through
P(wrl);
Writer V(mutex); – Which reader gets in first?
do { ... • The last reader to exit signals a writer
/*reading is performed*/
P(wrl); ...
– If no writer, then readers can continue
...
/*writing is performed*/
P(mutex); • If readers and writers waiting on wrl, and writer exits
rcount--;
... – Who gets to go in first?
if (rcount == 0)
V(wrl); V(wrl); • Why doesn’t a writer need to use mutex?
V(mutex);
}while(TRUE); }while(TRUE);

2
 Dining Philosopher’s Problem A non-solution
# define N 5
• Dijkstra

• Philosophers eat/think Philosopher i (0, 1, .. 4)

• Eating needs two forks
do {
• Pick one fork at a time
think();
• How to avoid deadlock? take_fork(i);
take_fork((i+1)%N);
eat(); /* yummy */
put_fork(i);
put_fork((i+1)%N);
Example: multiple processes competing for limited resources } while (true);

Will this work? Dining Philosophers Solutions

Shared: semaphore fork[5];
Init: fork[i] = 1 for all i=0 .. 4
• Allow only 4 philosophers to sit simultaneously
Philosopher i • Asymmetric solution
– Odd philosopher picks left fork followed by right
do { – Even philosopher does vice versa
P(fork[i]);
P(fork[i+1]); • Pass a token
• Allow philosopher to pick fork only if both available
/* eat */

V(fork[i]);
V(fork[i+1]);

/* think */
} while(true);

One possible solution

Shared: int state[5], semaphore s[5], semaphore mutex;
Init: mutex = 1; s[i] = 0 for all i=0 .. 4

Philosopher i
take_fork(i) {
P(mutex);
Language Support for
do {
state[i] = hungry;
test(i);
test(i) {
if(state[i] == hungry
Concurrency
take_fork(i); V(mutex);
&& state[(i+1)%N] != eating
/* eat */ P(s[i]);
&& state[(i-1+N)%N != eating)
put_fork(i); }
{
/* think */ state[i] = eating;
} while(true); put_fork(i) {
V(s[i]);
P(mutex);
}
state[i] = thinking;
test((i+1)%N);
test((i-1+N)%N);
V(mutex);
}

3
 Common programming errors What’s wrong?
Shared: Semaphores mutex, empty, full;

Init: mutex = 1; /* for mutual exclusion*/

empty = N; /* number empty bufs */
full = 0; /* number full bufs */
Producer Consumer
Process i Process j Process k
do { do {
... P(full);
P(S) V(S) P(S) // produce an item in nextp P(mutex);
CS CS CS ... ...
P(S) V(S) P(mutex); // remove item to nextc
P(empty); ...
... V(mutex);
// add nextp to buffer V(empty);
... ...
V(mutex); // consume item in nextc
V(full); ...
} while (true); } while (true);

What’s wrong? Revisiting semaphores!

Shared: Semaphores mutex, empty, full;
• Semaphores are still low-level
Init: mutex = 1; /* for mutual exclusion*/
– Users could easily make small errors
empty = N; /* number empty bufs */
full = 0; /* number full bufs */ – Similar to programming in assembly language
Producer Consumer • Small error brings system to grinding halt
– Very difficult to debug
do { do {
... P(full);
// produce an item in nextp P(mutex); • Simplification: Provide concurrency support in compiler
... ... – Monitors
P(mutex); What if buffer is full? // remove item to nextc
P(empty); ...
... V(mutex);
// add nextp to buffer V(empty);
... ...
V(mutex); // consume item in nextc
V(full); ...
} while (true); } while (true);

Monitors Monitor Semantics

• Hoare 1974 • Monitors guarantee mutual exclusion
• Abstract Data Type for handling/defining shared resources – Only one thread can execute monitor procedure at any time
• “in the monitor”
• Comprises:
– If second thread invokes monitor procedure at that time
– Shared Private Data • It will block and wait for entry to the monitor
• The resource ⇒ Need for a wait queue
• Cannot be accessed from outside – If thread within a monitor blocks, another can enter
– Procedures that operate on the data • Effect on parallelism?
• Gateway to the resource
• Can only act on data local to the monitor
– Synchronization primitives
• Among threads that access the procedures

4
 Structure of a Monitor
Monitor monitor_name
Synchronization Using Monitors
{ For example:
// shared variable declarations • Defines Condition Variables:
Monitor stack
procedure P1(. . . .) { {
– condition x;
.... int top; – Provides a mechanism to wait for events
} void push(any_t *) { • Resources available, any writers
.... • 3 atomic operations on Condition Variables
procedure P2(. . . .) {
}
.... – x.wait(): release monitor lock, sleep until woken up
} any_t * pop() { ⇒ condition variables have waiting queues too
. ....
. – x.notify(): wake one process waiting on condition (if there is one)
}
procedure PN(. . . .) { • No history associated with signal
.... initialization_code() { – x.broadcast(): wake all processes waiting on condition
} .... • Useful for resource manager
}
initialization_code(. . . .) {
}
• Condition variables are not Boolean
.... – If(x) then { } does not make sense
} only one instance of stack can
} be modified at a time

Producer Consumer using Monitors Compare with Semaphore Solution

Monitor Producer_Consumer { Monitor Producer_Consumer { Init: mutex = 1; empty = N; full = 0;
any_t buf[N]; any_t buf[N];
int n = 0, tail = 0, head = 0; int n = 0, tail = 0, head = 0; Producer
condition not_empty, not_full; condition not_empty, not_full; do {
void put(char ch) { void put(char ch) { // produce an item in nextp
if(n == N) if(n == N) P(empty);
wait(not_full);
What if no thread is waiting wait(not_full); P(mutex);
buf[head%N] = ch; buf[head%N] = ch; // add nextp to buffer
head++;
when signal is called? head++; V(mutex);
n++; n++;
V(full);
signal(not_empty); signal(not_empty);
} } } while (true);
char get() { char get() { Consumer
if(n == 0) if(n == 0) do {
wait(not_empty); wait(not_empty); P(full);
ch = buf[tail%N]; ch = buf[tail%N]; P(mutex);
tail++; tail++;
// remove item to nextc
n--; n--;
signal(not_full); signal(not_full); V(mutex);
return ch; return ch; V(empty);
} } // consume item in nextc
} } } while (true);

Producer Consumer using Monitors Types of Monitors

Monitor Producer_Consumer
What happens on notify():
{
condition not_full; • Hoare: signaler immediately gives lock to waiter (theory)
/* other vars */ – Condition definitely holds when waiter returns
condition not_empty; – Easy to reason about the program
void put(char ch) { • Mesa: signaler keeps lock and processor (practice)
wait(not_full); – Condition might not hold when waiter returns
... – Fewer context switches, easy to support broadcast
signal(not_empty); • Brinch Hansen: signaller must immediately exit monitor
} – So, notify should be last statement of monitor procedure
char get() {
...
}
}

5
 Mesa-style monitor subtleties Mesa-style subtleties
char buf[N]; // producer/consumer with monitors
char buf[N]; // producer/consumer with monitors int n = 0, tail = 0, head = 0;
int n = 0, tail = 0, head = 0; condition not_empty, not_full;
condition not_empty, not_full; Consider the following time line: void put(char ch)
void put(char ch)
0. initial condition: n = 0 while(n == N)
if(n == N)
wait(not_full);
1. c0 tries to take char, blocks wait(not_full);
buf[head] = ch;
When can we replace
buf[head%N] = ch; on not_empty (releasing monitor
lock) head = (head+1)%N; “while” with “if”?
head++;
n++; 2. p0 puts a char (n = 1), signals n++;
signal(not_empty); not_empty signal(not_full);
char get() 3. c0 is put on run queue char get()
if(n == 0) 4. Before c0 runs, another while(n == 0)
wait(not_empty); consumer thread c1 enters wait(not_empty);
ch = buf[tail%N]; ch = buf[tail];
and takes character (n = 0)
tail++; tail = (tail+1) % N;
n--;
5. c0 runs.
n--;
signal(not_full); signal(not_full);
return ch; Possible fixes? return ch;

Condition Variables & Semaphores Hoare Monitors using Semaphores

Condition Var Wait: x.wait:
• Condition Variables != semaphores
x_count++;
• Access to monitor is controlled by a lock For each procedure F: if(next_count > 0)
– Wait: blocks on thread and gives up the lock V(next);
• To call wait, thread has to be in monitor, hence the lock P(mutex); else
• Semaphore P() blocks thread only if value less than 0 V(mutex);
– Signal: causes waiting thread to wake up /* body of F */ P(x_sem);
• If there is no waiting thread, the signal is lost x.count--;
• V() increments value, so future threads need not wait on P()
if(next_count > 0)
V(next); Condition Var Notify: x.notify:
• Condition variables have no history
else If(x_count > 0) {
• However they can be used to implement each other V(mutex); next_count++;
V(x_sem);
P(next);
next_count--;
}

Language Support Eliminating Locking Overhead

• Can be embedded in programming language: • Remove locks by duplicating state
– Synchronization code added by compiler, enforced at runtime – Each instance only has one writer
– Mesa/Cedar from Xerox PARC – Assumption: assignment is atomic
– Java: synchronized, wait, notify, notifyall • Non-blocking/Wait free Synchronization
– C#: lock, wait (with timeouts) , pulse, pulseall – Do not use locks
– Optimistically do the transaction
• Monitors easier and safer than semaphores
– If commit fails, then retry
– Compiler can check, lock implicit (cannot be forgotten)
• Why not put everything in the monitor?

6
 Optimistic Concurrency Control
• Example: hits = hits + 1;
A) Read hits into register R1
B) Add 1 to R1 and store it in R2
C) Atomically store R2 in hits only if hits==R1 (i.e. CAS)
• If store didn’t write goto A
• Can be extended to any data structure:
A) Make copy of data structure, modify copy.
B) Use atomic word compare-and-swap to update pointer.
C) Goto A if some other thread beat you to the update.
Less overhead, deals with failures better
Lots of retrying under heavy load