Semaphores do much more than mutual exclusion. They can also be
used to synchronize producer/consumer programs. The idea is that
the producer is generating data and the consumer is consuming data.
So a Unix pipe has a producer and a consumer. You can also think
of a person typing at a keyboard as a producer and the shell
program reading the characters as a consumer.
Here is the synchronization problem: make sure that the
consumer does not get ahead of the producer. But, we would like
the producer to be able to produce without waiting for the
consumer to consume. Can use semaphores
to do this. Here is how it works:
Semaphore *s;
void consumer(int dummy) {
while (1) {
s->P();
consume the next unit of data
}
}
void producer(int dummy) {
while (1) {
produce the next unit of data
s->V();
}
}
void main() {
s = new Semaphore("s", 0);
Thread *t = new Thread("consumer");
t->Fork(consumer, 1);
t = new Thread("producer");
t->Fork(producer, 1);
}
In some sense the semaphore is an abstraction of the collection of data.
In the real world, pragmatics intrude. If we let the producer
run forever and never run the consumer, we have to store all of the
produced data somewhere. But no machine has an infinite amount of
storage. So, we want to let the producer to get ahead of the consumer
if it can, but only a given amount ahead. We need to implement
a bounded buffer which can hold only N items. If the bounded
buffer is full, the producer must wait before it can put any
more data in.
Semaphore *full;
Semaphore *empty;
void consumer(int dummy) {
while (1) {
full->P();
consume the next unit of data
empty->V();
}
}
void producer(int dummy) {
while (1) {
empty->P();
produce the next unit of data
full->V();
}
}
void main() {
empty = new Semaphore("empty", N);
full = new Semaphore("full", 0);
Thread *t = new Thread("consumer");
t->Fork(consumer, 1);
t = new Thread("producer");
t->Fork(producer, 1);
}
An example of where you might use a producer and consumer
in an operating system is the console (a device that reads and
writes characters from and to
the system console). You would probably use semaphores to
make sure you don't try to read a character before it is typed.
Semaphores are one synchronization abstraction. There is
another called locks and condition variables.
Locks are an abstraction specifically for mutual exclusion
only. Here is the Nachos
lock interface:
class Lock {
public:
Lock(char* debugName);
// initialize lock to be FREE
~Lock();
// deallocate lock
void Acquire();
// these are the only operations on a lock
void Release();
// they are both *atomic*
}