| Overview Of Thread Continue... |
There are two variants of condition variables: Hoare
condition variables and Mesa condition variables. For Hoare
condition variables, when one thread performs a
Signal, the very next thread to run is the waiting
thread.
For Mesa condition variables, there are no
guarantees when the signalled thread will run. Other
threads that acquire the lock can execute between
the signaller and the waiter. The
example above will work with Hoare condition variables but
not with Mesa condition variables.
What is the problem with Mesa condition variables?
Consider the following scenario: Three threads,
thread 1 one producing data, threads 2 and 3 consuming data.
- Thread 2 calls consumer, and suspends.
- Thread 1 calls producer, and signals thread 2.
- Instead of thread 2 running next, thread 3 runs next,
calls consumer, and consumes the element. (Note: with
Hoare monitors, thread 2 would always run next, so this
would not happen.)
- Thread 2 runs, and tries to consume an item that is not
there. Depending on the data structure used to store produced
items, may get some kind of illegal access error.
How can we fix this problem?
Replace the if with a while.
void consumer(int dummy) {
while (1) {
l->Acquire();
while (avail == 0) {
c->Wait(l);
}
consume the next unit of data
avail--;
l->Release();
}
}
In general, this is a crucial point. Always put while's around your
condition variable code. If you don't, you can get really
obscure bugs that show up very infrequently.
In this example, what is the data that the lock and
condition variable are associated with? The
avail variable.
People have developed a programming abstraction that
automatically associates locks and condition variables with
data. This abstraction is called a monitor. A monitor is a
data structure plus a set of operations (sort of like an
abstract data type). The monitor also has a lock and, optionally,
one or more condition variables. See notes for Lecture 14.
The compiler for the monitor language automatically inserts
a lock operation at the beginning of each routine and an unlock
operation at the end of the routine. So, programmer does not have
to put in the lock operations.
Monitor languages were popular in the middle 80's - they are in some
sense safer because they eliminate one possible programming error.
But more recent languages have tended not to support monitors explicitly,
and expose the locking operations to the programmer. So the programmer
has to insert the lock and unlock operations by hand.
Java takes a middle ground - it supports monitors, but also allows
programmers to exert finer grain control over the locked sections
by supporting synchronized blocks within methods. But synchronized
blocks still present a structured model of synchronization, so it
is not possible to mismatch the lock acquire and release.
Laundromat Example: A local laudromat has switched to a
computerized machine allocation scheme. There are N machines,
numbered 1 to N. By the front door there are P allocation stations. When
you want to wash your clothes, you go to an allocation station
and put in your coins. The allocation station gives you a number,
and you use that machine. There are also P deallocation stations.
When your clothes finish, you give the number back to one
of the deallocation stations, and someone else can use the machine.
Here is the alpha release of the machine allocation software:
allocate(int dummy) {
while (1) {
wait for coins from user
n = get();
give number n to user
}
}
deallocate(int dummy) {
while (1) {
wait for number n from user
put(i);
}
}
main() {
for (i = 0; i < P; i++) {
t = new Thread("allocate");
t->Fork(allocate, 0);
t = new Thread("deallocate");
t->Fork(deallocate, 0);
}
}
The key parts of the scheduling are done in the two routines
get and put, which use an array data
structure a to keep track of which machines are
in use and which are free.
int a[N];
int get() {
for (i = 0; i < N; i++) {
if (a[i] == 0) {
a[i] = 1;
return(i+1);
}
}
}
void put(int i) {
a[i-1] = 0;
}
|
