Classic Coordination Problems Flashcards
User Defined Box Sizing
– One process reads a number from keyboard and places inside an object of class BoxDimension
– Separate process extracts the number from BoxDimension object, and draws a box of corresponding size
Coordination Problem
- Getter must extract only dimensions that Putter has placed
- Getter must not extract any dimension more than once
- Putter must not place a new dimension until the Getter has extracted the one the
Putter placed earlier - Putter=Producer; put=produce
- Getter=Consumer; extract=consume
- Placing values in a unit buffer (buffer of size 1)
Producer-Consumer (Bounded Buffer) Problem
Producer-Consumer (Bounded Buffer) Problem
Outline of solution
- Uses two semaphores produce and consume
- How to ensure that consumer does not consume before producer produces?
- What should the initial values of the semaphores be?
Java Implementation of Producer-Consumer Unit Buffer
class Consumer implements Runnable {
Semaphore produce, consume;
StringBuffer buf;
public Consumer(Semaphore produce, Semaphore consume, StringBuffer buf) {this.produce = produce;
this.consume = consume;
this.buf = buf;
}
public void run() {
while(true) {
consume.acquire();
System.out.println(buf);
produce.release();
}
}
}
Producer-Consumer in General (Several producers, consumers, and bounded length buffers)
Conditions
- A Consumer must extract only values that a Producer has placed
- No value should be extracted more than once
- A Producer may place a value only in free buffer locations
- Initially all buffer locations are free
- Any location that contains a value that has been extracted is free
- No other location is free
Generalized Producer-Consumer in Java
class Consumer implements Runnable {
Semaphore produce,Semaphore consume;
Buffer buf;
public Consumer(Semaphore produce, Semaphore consume, Buffer buf){this.produce = produce; this.consume = consume; this.buf = buf;}
public void run() {
while(true) {
consume.acquire();
System.out.println(“Got:” + buf.get());
produce.release();
}
}
}
class Buffer
String[] values; boolean[] availableWrite;
public Buffer(int bufSize)
values = new String[bufSize];
availableWrite = new boolean[bufSize];
for(int i = 0; i<bufSize;i++)
availableWrite[i] = true;
synchronized void put(String s)
for(int i = 0; i < availableWrite.length; i++)
if(availableWrite[i] == true)
values[i] = s;
availableWrite[i] = false;
break;
synchronized String get()
for(int i = 0; i < availableWrite.length; i++)
if(availableWrite[i] == false)
availableWrite[i] = true;
return values[i];
Readers-Writers Problem
- A buffer (“file”) that several threads are accessing simultaneously
- Buffer holds a single value (the file)
- Writers write values to the buffer (they may also read the buffer)
- Readers may only read from the buffer
- Ensure that any buffer value read by a thread is a value written by some writer!
- Unlike Producer-Consumer, a value may be overwritten by a Writer without ever having been read by a Reader
- Unlike Producer-Consumer, the same value can be read by many Readers and more than once by a Reader
Readers-Writers Problems
Constraints that Follow from the Requirement
- Writer must have exclusive access to the buffer
- Any number of readers may be concurrent
Readers-Writers Problems
Solution Outline
- Two semaphores, write and read, initialized to 1
- A count of the number of Readers numReaders, initialized to 0
Readers-Writers
Firing up the Threads
Writer run() function
Reader run() function
Code does not meet Requirement as we stated it
- (As stated earlier) Ensure that any buffer value read by a thread is a value written by some writer!
- (Should Be) Ensure that any buffer value read by a thread is either the initial value or a value written by some writer!
- 2 is normally requirement for Readers-Writers
- Illustrates the subtlety of implementing multithreaded programs
- How would you modify code so that 1 is met?
