CS444 Class 13
2 handouts
Midterm Exam next Monday,
Oct. 29
Next time: Midterm Review
Think of MacDonald’s as a
burger pipeline: cook making burgers, putting them in the bin. But if
the bin fills up, the cook has to stop for a while. The consumers come to
buy burgers, and take them from the bin, but if the bin is empty, they have to
wait a while. The bin has a certain capacity. Similarly, memory
buffers have a certain size, the "bounded buffer" idea.
How can we solve similar
problems with data pipelines? Spinning? No, wastes CPU.
Instead, we want to block the waiter.
Solution: semaphores:
they can block for more than just mutex. Think how they work: if sem’s
count is 3, then down, down, down and sleep. If we can arrange a count
that goes to 0 at the point we need a thread to sleep, semaphores will do the
job.
Here we are considering a
data pipeline with a buffer of a fixed number of slots, a “bounded
buffer.” Although buffers can be enlarged dynamically, that isn’t such a
great idea in many cases, as a faster producer could use up a huge amount of
memory and the job isn’t being finished faster.
So it’s often best to live with a fixed-size buffer as is done in this classic problem.
<producer thread>
| producer adds items to buffer
v
[………..]
shared buffer of a certain fixed size
|
v consumer removes items from buffer
< consumer thread>
The data consumer can be
controlled by a semaphore whose count tracks the number of objects in the data
buffer. Buffer empty, consumer waits. The data producer can be
controlled by a semaphore whose count tracks the number of spaces in the
buffer, i.e., the number of empty slots in the buffer. Buffer full, no
empties, producer waits.
In Tanenbaum, pg. 130, we
have some magic C code (perhaps a preprocessor.) We could use the
portable POSIX semaphore API instead, with sem_init(), sem_wait(), sem_post(),
sem_destroy(). You can “man sem_init” for example, for more details.
But since Java 5, Java has
had a nice Semaphore class, so we’ll use that to turn pg. 130 into real code.
See handout “Producer
Consumer Ptogram Using Java Semaphores” for code and some introduction.
Think about how this will
run. First the producer will run and produce N items, and during this
time, the consumer will start and consume some.
Either way, it works fine,
and if the producer and consumer vary in speed, the system keeps them in
balance.
Semaphore and mutex system calls
Since semaphores and mutex
mechanisms used in user code involve blocking, they must enter the kernel and
thus involve system calls.
POSIX (portable across UNIX
variants) with sem_init, etc. other has sema_init(), etc. See man pages.
Win32: CreateSemaphore,
WaitForSingleObject, ReleaseSemaphore
CreateMutex, WaitForSingleObject, ReleaseMutex
Note on Tan., p 131.
Note this discussion is about user-level threads, not kernel-supported
threads. User-level threads cannot use simple spin locks because they
have no preemption capability, unlike kernel-supported threads. To fix
this, a call to the user-level thread scheduler is added to the spin-lock code
to prevent the waiter from just spinning forever. If you want, just ignore user-level threads, so this whole
page. You can drop the “call thread_yield” in Fig. 2-25 and get
workable mutex for kernel-supported threads, but usually better to use
semaphores and use blocking instead of spin waits.
Monitors (from English word monitor, meaning a kind of
guard person, like a lunch monitor in grade school)
Think of a picture of
stick-figure guard attached to piece of code with a stop sign, one thread
inside, others waiting their turn outside.
A monitor is a language
construct (dating from 1974) that sets up mutex protection for its encapsulated
code, and also helps with necessary blocking actions. Just skip the
pidgin Pascal coverage and let’s cover the Java case. Java supplies a built-in mutex, usually not
in active use, in each object. We can
use the synchronized keyword on methods of the class and then the mutex will
start being used to ensure that only one of the methods is currently being
executed at each point in time, i.e.., turn the class into a monitor.
From the handout “Example of
Monitor in Java”
private
static int N = 10;
// How to set up a Queue in Java—Queue
interface, LinkedList concrete class
private
Queue<Integer> buffer = new
LinkedList<Integer>();
// or use buffer =
Collections.synchronizedList(new LinkedList(...));
public
synchronized boolean insert(int val) {
if (buffer.size() == N)
return
false; // fail if full
buffer.add(val); // add to end, i.e. enqueue
return true;
}
// return positive number, or -1 if nothing
is there
public
synchronized int remove() {
int val;
if (buffer.size() == 0)
return
-1; // fail if empty
val = buffer.remove(); // remove from
front, i.e., dequeue
return val;
}
}
With this implementation, two
concurrent inserts or removes or both can’t happen, so the queue data
structure (a LinkedList) should stay
unbroken in spite of multithreaded execution. Note that LinkedList is not
itself synchronized, so concurrent access to it can break it.
With the Monitor0
implementation above, two concurrent inserts or removes or both can’t happen,
so the queue data structure should stay unbroken in spite of multithreaded
execution. Providing simple mutex is the crux of synchronized
methods. Each object with synchronized methods has a hidden mutex
variable ensuring that only one thread is executing any of its synchronized
methods at once.
But the caller only gets an
error return for a full or empty buffer. What are they supposed to do,
spin?? Clearly they want to block so as not to waste CPU—that’s the full
program of the second handout.
We just saw how to use Java
synchronized methods to provide mutex for a data structure accessed by
multiple threads. It's really easy, since all you have to do is add the
keyword "synchronized" to the method declaration, and Java sets up a
mutex variable in the object for you and uses it appropriately at each thread
entrance into these methods, and exit from them.
Easy mutex is great, but we need more for full producer consumer: we need to
block the producer when the buffer is full, and the consumer when the buffer is
empty.
It’s possible to build
that blocking into OurMonitor, using the Java wait and notify methods.
Note that mutex alone is not powerful enough to block on any given condition—it’s
specialized to block only the second and subsequent threads after one is
allowed to run in the critical region. This approach leads to Tanenbaum’s
code on pg. 141. But we can do it in a much more comprehensible way by just
using Semaphores again. We can use empty and full as done in the first handout,
but replace the mutex Semaphore with the mutex in Monitor0.
Note that a Semaphore is
itself implemented as a monitor. You can implement semaphores from wait
and notify—Google “Java semaphores wait notify” for several implementations.
BTW, on pg. 141 we see simple
calls wait() and notify(). Where’s the class or object? What class
has these methods? Answer: Object, and any Java object ISA Object, so by
inheritance these are methods of the current class.
However, I strongly caution
against coding with wait and notify—it’s very tricky and usually not
needed. Use semaphores instead—see
handout. In fact, the code on pg. 141
looks a lot like the code on pg. 127, labeled as having a fatal race condition. Shows how hard it is to make this right.
Tanenbaum’s sleep/wakeup
example, pg. 127, has a fatal race condition. How does this code avoid
it? What was this fatal race condition?
Answer: Lost wakeup
problem. (Not to be confused with the lost update problem, both race
conditions.)
Scenario
from pg. 127: lost wakeup problem
--consumer
reads count = 0
<thread
switch>
--producer
inserts an item into the buffer, incs count, calls wakeup
--but
consumer isn’t waiting yet, so wakeup wakes up nothing
<thread
switch>
consumer
acts on its knowledge of count = 0, calls sleep, sleeps forever
This can’t happen with the
synchronized methods of pg. 141 because the consumer “has the monitor” i.e. the
mutex at the thread switch, and so the producer can’t run inside the synch.
methods. There can be a thread switch, but the producer quickly blocks on
the mutex, and the consumer runs again and finishes the full action, going to
sleep. Then the producer inserts the item and calls wakeup, waking up the
sleeping consumer. No lost wakeup.
What about our
producer-consumer code with semaphores?
Consumer
tries to get something from empty queue: blocks in sem
Producer
inserts an item into queue, OK, consumer already waiting
Producer
does release: wakeup, wakes up consumer, no problem.
Bottom line: no lost wakeup
problem because the semaphore deals with the underlying count, causing blocking
along with recognition of needed blocking.