Enforcing ordering constraints between instructions of different threads/processes is called syncronization. Mutual exclusion of critical sections is just one kind of syncronization. Many common synchronization patterns have been identified, including:
| Thread A | Thread B |
Code chunk A1
← rendvous point
Code chunk A2
|
Code chunk B1
← rendvous point
Code chunk B2
|
double cos(double x);
is the interface to the cosine function in math.h. As
programmers, we only care about that interface, not the
implementation. In OOP the interface for a class is its
public member functions. These are the operations we as
outside programmers can use. All the private data data and
member functions ... those don't matter to use outsiders. In
data structures, which you'll have next semester, this gets
taken much farther still. Finally, all these system calls
that we've been learning about: they are our (as programmers)
interface to the kernel. Prototypes and man page
documentation tell us what these functions
accomplish, but how they are implemented is a
completely different story --- a story that we don't really
have to know to be able to use them.
Finding the right interface is very important, and often quite difficult. Ideally, you want to provide a few simple operations that are easy to understand, but can be combined to accomplish a wide variety of complex tasks. A small set of operations like this is often called a set of primitive operations. We will study semaphores, which provide a small set of primitive operations for synchronizing threads or processes that can be combined to provide many different synchronization patterns, including the four listed above.
Semaphores are probably the best known synchronization primitive. Mutexes are nothing more than a semaphore with initial value one, with every process doing a wait immediately prior to a critical seciton and a post immediately after.
Of course we have mutex's for mutual exclusion, but a mutex
is no different than a semaphore with initial value 1. So
we'll use a semaphore named mu, initialized to
1, to ensure mutual exclusion. We'll have another semaphore
named items whose value is the number of items
currently stored in the buffer. Thus, every time the
producer produces, items should be
incremented. Every time the consumer consumes,
items should be decremented, and since the
consumre can't consume unless items > 0,
the consumer will "wait" on items.
Shared semaphores
mu initialized to 1, and
items initialized to 0.
|
|
| Producer | Consumer |
while(1)
{
get/compute data
wait(mu);
write data item to buffer
post(items);
post(mu);
}
|
while(1)
{
wait(items);
wait(mu);
read data item form buffer
post(mu);
process data
}
|
Hopefully you can convince yourself that this works properly.
spaces, initialized
to the capacity of the buffer, that keeps track of the number
of empty slots in the buffer. Thus, BUFFERSIZE = #items +
#spaces at all times.
Shared semaphores
mu initialized to 1, and
items initialized to 0, and
spaces inialized to BUFFERSIZE.
|
|
| Producer | Consumer |
while(1)
{
get/compute data
wait(spaces);
wait(mu);
write data item to buffer
post(items);
post(mu);
}
|
while(1)
{
wait(items);
wait(mu);
read data item form buffer
post(spaces);
post(mu);
process data
}
|
Hopefully you can convince yourself that this works properly as well.