- Atomic operation. One or more statements that cannot be interrupted.
- Critical section. Area of code that accesses a resource such that no other executing unit (EU) can be allowed to access that resource at the same time.
- deadlock. Situation where multiple EUs get stuck because they are all waiting for each other.
- livelock. Similar to deadlock, but the EUs keep running, they just never get past some place.
- Mutual exclusion. The thing that makes EUs not step on each other's critical sections.
- race condition. Multiple EUs accessing the same resource at the same time result in indeterminate output depending on who gets run first.
- Situation where an EU is not stuck, but might have to theoretically wait forever because other EUs keep hoggin the resource.
- Multiple EUs operating on same variables:
out = getchar(); putchar(out);
depends on who runs when.
- Simple solution- single access. only one EU can access at a time. Others must wait.
- Also want to avoid deadlock and starvation. Want to always let EU use resource if no one else is.
- Assume use is always finite.
- Disable interrupts? A bit drastic and only works on uniprocessors.
- Special instructions. Compare&Swap, exchange
- Why does that have to be atomic?
- Supports many EUs and many sections.
- easy to verify.
- Busy wait wasteful
- starvation
while(true) {
semWait(s);
/*critical section*/
semPost(s);
}
- One or more "producers" are adding data to a buffer.
- One or more "consumers" are removing from the buffer.
- Obvious example: network buffer.
- Producers stop when the buffer is full.
- Consumers stop when the buffer is empty.
- Only one EU can be actually reading or writing to the buffer at a time.
- Assume functions produce(), to produce an item, append() to add item to buffer, take() to remove item, and consume() to consume.
- We will start with a simplified version: 1 P, 1 C and an infinite buffer
- With an infinite buffer, producer never needs to block, so we need to just protect the critical section and have the consumer wait on empty.
- Why is this broken?
void consumer() { if (n==0) sem_wait(empty); sem_wait(s); take(); n--; sem_post(s); consume(); } void producer() { while(1) { produce(); sem_wait(s); append(); n++; if (n==1) sem_post(empty); sem_post(s); } }This works better:
void consumer() { sem_wait(n); sem_wait(s); take(); sem_post(s); consume(); } void producer() { while(1) { produce(); sem_wait(s); append(); sem_post(s); sem_post(n); } }
e = sizeofbuffer; n = 0;
void consumer() {
sem_wait(n);
sem_wait(s);
take();
sem_post(s);
sem_post(e);
consume();
}
void producer() {
while(1) {
produce();
sem_wait(e)
sem_wait(s);
append();
sem_post(s);
sem_post(n);
}
}
- There are other ways to do this. One common one (often seen in Java) is monitors.
- Monitors are software modules that organize code, exactly
like classes, but with the following properties:
- Data in the monitor is only accessed from within the monitor
- An EU "enters" monitor by calling a monitor function.
- Only 1 process can be "in" a monitor at a time.
- Monitors also contain mechanizms for synchronization.
- There are the special variables called condition variables that live in the monitor.
- wait(c)- causes the EU to block until that condition is true. Exits monitor.
- signal(c)- unblock the next thread on the condition queue for that condition.
- basic solution to producer/consumer - put both take and append in monitor. Signal and wait for over/underflow:
void append(x) { if (count == n) wait(full); buffer[next]= x; next = (next+1)%N; count++; signal(empty); } void take(x) { if (count == 0) wait(empty); x = buffer[next]; next = (next-1)%N; count--; signal(full); } void producer() { while (1) { produce(x); append(x); } void consumer() { while (1) { take(x); consume(x); } - In Java, every object has a monitor associated with it automatically, but a method is not part of the monitor unless you use the word synchronized.
- When processes interact with one another, two fundamental requirements must be satisfied: synchronization and communication.
- Message Passing is one solution to the second requirement
- send(dest,message), recv(source,message)
- must send before you receive. Synchronization!
- Blocking on send and receive creates tight synchronization, rendezvous.
- non-blocking, more flexible, now requires other synch.
- How do we address the message?
- Direct- PID, etc.
- Indirect, Mailbox.
- Mutex using messages- use a blocking receive at start, a send at end.
- How to solve the producer/consumer problem with a sahred buffer and messages? Don't, just send the data in the messages!
- A data area is shared among many processes
- Some processes only read the data area, some only write to the area
- Multiple readers may read the file at once.
- Only one writer at a time may write.
- If a writer is writing to the file, no reader may read it.
- Subtly different from a Producer/Consumer problem.
- Here wsem is used to keep out all other processes when there is a writer going.
- The basic plan for readers is: if there's already a reader in the CS, I can just go right in. If I'm the first reader to come along, I better check to make sure there isn't alreader a writer in there. To see if I'm the first, we keep track of how many are there with readcount.
- x is just a critical section wrapper around readcount.
- In this version a reader waits if a writer is writing, but otherwise readers rule the day. If readers keep coming in, writers starve.
- This is bad because in most cases, there can be lots of
readers.
- We still use wsem, readcount and x, but we need more.
- The writers will keep track of how many they are, so we need a writecount variable, and a mutex semephore y.
- When a writer shows up, it checks to see if it's first. If it is, there still might be a reader, so it will need to check and possibly block. Instead of using wsem to control all access, we'll use wsem to keep out other writers, and rsem to keep out the the readers when the writer is writing, and to keep out the writer when it .
- Let's see it in action.
Process Step rsem wsem x y z readcount writecount comment none n/a 1 1 1 1 1 0 0 r1 semWait(z) 1 1 1 1 0 0 0 r1 semWait(rsem) 0 1 1 1 0 0 0 r1 emWait(x) 0 1 0 1 0 0 0 r1 readcount++ 0 1 0 1 0 1 0 r1 semWait(wsem) 0 0 0 1 0 1 0 lock out writers r1 semSignal(x) 0 0 1 1 0 1 0 r1 semSignal(rsem) 1 0 1 1 0 1 0 r1 semSignal(z) 1 0 1 1 1 1 0 swap r2 semWait(z) 1 0 1 1 0 1 0 r2 semWait(rsem) 0 0 1 1 0 1 0 r2 semWait(x) 0 0 0 1 0 1 0 r2 readcount++ 0 0 0 1 0 2 0 r2 semSignal(x) 0 0 1 1 0 2 0 r2 semSignal(rsem) 1 0 1 1 0 2 0 r2 semSignal(z) 1 0 1 1 1 2 0 swap r3 semWait(z) 1 0 1 1 0 2 0 r3 semWait(rsem) 0 0 1 1 0 2 0 r3 semWait(x) 0 0 0 1 0 2 0 r3 readcount++ 0 0 0 1 0 3 0 r3 semSignal(x) 0 0 1 1 0 3 0 r3 semSignal(rsem) 1 0 1 1 0 3 0 r3 semSignal(z) 1 0 1 1 1 3 0 swap We now have 3 readers reading w1 semWait(y) 1 0 1 0 1 3 0 w1 writecount++ 1 0 1 0 1 3 1 w1 semWait(rsem) 0 0 1 0 1 3 1 Am I first? Lock out new readers. w1 semSignal(y) 0 0 1 1 1 3 1 w1 semwait(wsem) 0 -1 1 1 1 3 1 block readers have locked us out w2 semwait(y) 0 -1 1 0 1 3 1 w2 writecount++ 0 -1 1 0 1 3 2 w2 semSignal(y) 0 -1 1 1 1 3 2 w2 semWait(wsem) 0 -2 1 1 1 3 2 block 2 writers waiting on the readers. r4 semWait(z) 0 -2 1 1 0 3 2 Oh no! will new readers starve our writers? r4 semWait(rsem) -1 -2 1 1 0 3 2 block See how we're blocked before releasing z? r5 semWait(z) -1 -2 1 1 -1 3 2 block Any new readers will block on z. r1 semWait(x) -1 -2 0 1 -1 3 2 The early ones finish r1 readcount-- -1 -2 0 1 -1 2 2 r1 semSignal(x) -1 -2 1 1 -1 2 2 done Still readers in there. r2 semWait(x) -1 -2 0 1 -1 2 2 r2 readcount-- -1 -2 0 1 -1 1 2 r2 semSignal(x) -1 -2 1 1 -1 1 2 done One left. r3 semWait(x) -1 -2 0 1 -1 1 2 r3 readcount-- -1 -2 0 1 -1 0 2 r3 semSignal(wsem) -1 -1 0 1 -1 0 2 Last one out, wake up the writers r3 semSignal(x) -1 -1 1 1 -1 0 2 done Writers ready to go. w3 semWait(y) -1 -1 1 0 -1 0 2 new writer, what order will they run? w3 writecount++ -1 -1 1 0 -1 0 3 w3 semSignal(y) -1 -1 1 1 -1 0 3 w3 semWait(wsem) -1 -2 1 1 -1 0 3 block w1 semSignal(wsem) -1 -1 1 1 -1 0 3 Writer completes, wakes next writer w1 semWait(y) -1 -1 1 0 -1 0 3 w1 writecount-- -1 -1 1 0 -1 0 2 w1 semSignal(y) -1 -1 1 1 -1 0 2 done w2 semSignal(wsem) -1 0 1 1 -1 0 2 w2 semWait(y) -1 0 1 0 -1 0 2 w2 writecount-- -1 0 1 0 -1 0 1 w2 semSignal(y) -1 0 1 1 -1 0 1 done Readers still blocked. w3 semSignal(wsem) -1 1 1 1 -1 0 1 w3 semWait(y) -1 1 1 0 -1 0 1 w3 writecount-- -1 1 1 0 -1 0 0 w3 semSignal(rsem) 0 1 1 0 -1 0 0 Last writer out, wake the readers w3 semSignal(y) 0 1 1 1 -1 0 0 done Remaining readers go. r4 semWait(x) 0 1 0 1 -1 0 0 r4 readcount++ 0 1 0 1 -1 1 0 r4 semWait(wsem) 0 0 0 1 -1 1 0 r4 semSignal(x) 0 0 1 1 -1 1 0 r4 semSignal(rsem) 1 0 1 1 -1 1 0 r4 semSignal(z) 1 0 1 1 0 1 0 Waking other reader r4 semWait(x) 1 0 0 1 0 1 0 r4 readcount-- 1 0 0 1 0 0 0 r4 semSignal(wsem) 1 1 0 1 0 0 0 r4 semSignal(x) 1 1 1 1 0 0 0 done Last one. r4 semWait(rsem) 0 1 1 1 0 0 0 r4 semWait(x) 0 1 0 1 0 0 0 r4 readcount++ 0 1 0 1 0 1 0 r4 semWait(wsem) 0 0 0 1 0 1 0 r4 semSignal(x) 0 0 1 1 0 1 0 r4 semSignal(rsem) 1 0 1 1 0 1 0 r4 semSignal(z) 1 0 1 1 1 1 0 r4 semWait(x) 1 0 0 1 1 1 0 r4 readcount-- 1 0 0 1 1 0 0 r4 semSignal(wsem) 1 1 0 1 1 0 0 r4 semSignal(x) 1 1 1 1 1 0 0 done and done.