Date: Tue, 05 Nov 1996 20:57:02 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Thu, 31 Oct 1996 21:38:53 GMT Content-length: 42275
Tanenbaum mixes a presentation of the features of processes of interest
to programmers creating concurrent programs with discussion of techniques
for implementing them. The result is (at least to me) confusing.
I will attempt to first present processes and associated features from the
user's point of view with as little concern as possible for questions about
how they are implemented, and then turn to the question of implementing
processes.
Using Processes
What is a Process?
A process is a ``little bug'' that crawls around on the program executing
the instructions it sees there.
Normally (in so-called sequential programs) there is exactly one
process per program, but in concurrent programs, there may be
several processes executing the same program.
The details of what constitutes a ``process'' differ from system to system.
The main difference is the amount of private state associated with
each process.
Each process has its own program counter, the register
that tells it where it is in the program.
It also needs a place to store the return address when it calls a subroutine,
so that two processes executing the same subroutine called from different
places can return to the correct calling points.
Since subroutines can call other subroutines, each process needs its own
stack of return addresses.
Processes with very little private memory are called threads or light-weight processes. At a minimum, each thread needs a program counter and a place to store a stack of return addreses; all other values could be stored in memory shared by all threads. At the other extreme, each process could have its own private memory space, sharing only the read-only program text with other processes. This essentially the way a Unix process works. Other points along the spectrum are possible. One common approach is to put the local variables of procedures on the same private stack as the return addresses, but let all global variables be shared between processes. A stack frame holds all the local variables of a procedure, together with an indication of where to return to when the procedure returns, and an indication of where the calling procedure's stack frame is stored. Java follows this approach. It has no global variables, but threads all share the same heap. The heap is the region of memory used to allocate objects in response to new. In short, variables declared in procedures are local to threads, but objects are all shared. Of course, a thread can only ``see'' an object if it can reach that object from its ``base'' object (the one containing its run method, or from one of its local variables.
class Foo implements Runnable { Object obj1, obj2; Foo(Object a) { obj1 = a; } public void run() { Object obj3 = new Object(); obj2 = new Object(); for(int i = 0; i < 1000; i++) // do something } } class Bar { static public void main(String args[]) { Object obj4 = new Object(); Runnable foo1 = new Foo(obj4); Thread t1 = new Thread(foo1); Runnable foo2 = new Foo(obj4); Thread t2 = new Thread(foo2); t1.start(); t2.start(); // so something here } }There are three treads in this program, the main thread and two child threads created by it. Each child thread has its own stack frame for Foo.run(), with space for obj3 and i. Thus there are two copies of the variable obj3, each of which points to a different instance of Object. Those objects are in the shared heap, but since one thread has no way of getting to the object created by the other thread, these objects are effectively private. Similary, the objects pointed to by obj2 are effectively private. But both copies of obj1 and the copy of obj4 in the main thread all point to the same (shared) object.
Other names sometimes used for processes are job or task.
It is possible to combine threads with processes in the same system.
For example, when you run Java under Unix, each Java program is run in
a separate Unix process.
Unix processes share very little with each other, but the Java threads
in one Unix process share everything but their private stacks.
Why Use Processes
Processes are basically just a programming convenience, but in some settings they are such a great convenience, it would be nearly impossible to write the program without them. A process allows you to write a single thread of code to get some task done, without worrying about the possibilty that it may have to wait for something to happen along the way. Examples:
When a new process is created, it needs to know where to start executing. In Java, a thread is given an object when it is created. When it is started, it starts execution at the beginning of the run method of that object. In Unix, a new process is started with the fork() command. It starts execution at the statement immediately following the fork() call. After the call, both the parent (the process that called fork()) and the child are both executing at the same point in the program. The child is given its own memory space, which is initialized with an exactly copy of the memory space (globals, stack, heap objects) of the parent. Thus the child looks like an exact clone of the parent, and indeed, it's hard to tell them apart. The only difference is that fork() returns 0 in the child, but a non-zero value in the parent.
char *str; main() { int j; str = "the main program "; j = f(); cout << str << j << endl; } void f() { int k; k = fork(); if (k == 0) { str = "the child has value "; return 10; } else { str = "the parent has value "; return 39; } }This program starts with one process executing main(). This process calls f(), and inside f() it calls fork(). Two processes appear to return from fork(), a parent and a child process. Each has its own copy of the global global variable str and its own copy of the stack, which contains a frame for main with variable j and a frame for f with variable k. After the return from fork the parent sets its copy of k to a non-zero value, while the child sets its copy of k to zero. Each process then assigns a different string to its copy of the global str and returns a different value, which is assigned to the process' own copy of j. Two lines are printed:
the parent has value 39 the child has value 10(actually, the lines might be intermingled).
void deposit(int amount) { balance += amount; }(where we assume that balance is a shared variable. If two processes try to call deposit concurrently, something very bad can happen. The single statment balance += amount is really implmented, on most computers, buy a sequence of instructions such as
Load Reg, balance Add Reg, amount Store Reg, balanceSuppose process P1 calls deposit(10) and process P2 calls deposit(20). If one completes before the other starts, the combined effect is to add 30 to the balance, as desired. However, suppose the calls happen at exactly the same time, and the executions are interleaved. Suppose the initial balance is 100, and the two processes run on different CPUs. One possible result is
P1 loads 100 into its register P2 loads 100 into its register P1 adds 10 to its register, giving 110 P2 adds 20 to its register, giving 120 P1 stores 110 in balance P2 stores 120 in balanceand the net effect is to add only 20 tot he balance!
This kind of bug, which only occurs under certain timing conditions, is
called a race condition.
It is an extremely difficult kind of bug to track down (since it
may disappear when you try to debug it) and may be nearly
impossible to detect from testing (since it may occur only extremely rarely).
The only way to deal with race conditions is through very careful
coding.
To avoid these kinds of problems, systems that support processes always
contain constructs called
synchronization primatives.
Semaphores
One of the earliest and simplest synchronization primitives is the semaphore. We will consider later how semaphores are implemented, but for now we can treat them like a Java object that hides an integer value and only allows three operations: initialization to a specified value, increment, or decrement.1
class Semaphore { private int value; public Semaphore(int v) { value = v; } public void up() { /* ... */ } public void down() { /* ... */ }; }There is no operation to read the current value! There two bits of ``magic'' that make this seemingly useless class extremely useful:
shared Semaphore mutex = new Semaphore(1); void deposit(int amount) { mutex.down(); balance += amount; mutex.up(); }We assume there is one semaphore, which we call mutex (for ``mutual exclusion'') shared by all processes. The keyword shared (which is not Java) will be omitted if it is clear which variables are shared and which are private (have a separate copy for each process). Semaphores are useless unless they are shared, so we will omit shared before Semaphore. Also we will abreviate the declaration and initialization as
Semaphore mutex = 1;Let's see how this works. If only one process wants to make a deposit, it does mutex.down(), decreasing the value of mutex to zero, adds its amount to the balance, and returns the value of mutex to one. If two processes try to call deposit at about the same time, one of them will get to do the down operation first (because down is atomic!). The other will find that mutex is already zero and be forced to wait. When the first process finishes adding to the balance, it does mutex.up(), returning the value to one and allowing the other process to complete its down operation. If there were three processes trying at the same time, one of them would do the down first, as before, and the other two would be forced to wait. When the first process did up, one of the other two would be allowed to complete its down operation, but then mutex would be zero again, and the third process would continue to wait.
shared Buffer b; Semaphore mutex = 1, empty = N, full = 0; class Producer implements Runnable { public void run() { Object item; for (;;) { item = produce(); empty.down(); mutex.down(); b.enter_item(item); mutex.up(); full.up(); } } } class Consumer implements Runnable { public void run() { Object item; for (;;) { full.down(); mutex.down(); item = b.remove_item(); mutex.up(); empty.up(); } } }As before, we surround operations on the shared Buffer data structure with mutex.down() and mutex.up() to prevent interleaved changes by two processes (which may screw up the data structure). The semaphore full counts the number of objectx in the buffer, while the semphore empty counts the number of free slots. The operation full.down() in Consumer atomically waits until there is something in the buffer and then ``lays claim'' to it by decrementing the semaphore. Suppose it was replaced by
while (b.count == 0) { /* do nothing */ } mutex.down(); /* as before */It would be possible for one process to see that the buffer was non-empty, and then have another process remove the last item before it got a chance to grab the mutex semapore.
There is one more fine point to notice here: Suppose we revesed the down operations in the consumer
mutex.down(); full.down();and a consumer tries to do these operation when the buffer is empty. It first grabs the mutex semaphore and then blocks on the full semaphore. It will be blocked forever because no other process can grab the mutex semaphore to add an item to the buffer (and thus call full.up()). This situation is called deadlock. We will study it in length later.
class Philosopher implements Runnable { int i; // which philosopher public void run() { for (;;) { think(); take_forks(i); eat(); put_forks(i) } } }A first attempt to solve this problem represents each fork as a semaphore:
Semaphore fork[5] = 1; void take_forks(int i) { fork[i].down(); fork[i+1].down(); } void put_forks(int i) { fork[i].up(); fork[i+1].up(); }The problem with this solution is that it can lead to deadlock. Each philosopher picks up his right fork before he tried to pick up his left fork. What happends if the timing works out such that all the philosophers get hungry at the same time, and they all pick up their right forks before any of them gets a chance to try for his left fork? Then each philosopher i will be holding fork i and waiting for fork i+1, and they will all wait forever.
There's a very simple solution: Instead of trying for the right fork first, try for the lower numbered fork first. We will show later that this solution cannot lead to deadlock. You will be implementing a generalization of this technique in project 2.
This solution, while deadlock-free, is still not as good as it could be. Consider again the situation in which all philosophers get hungry at the same time and pick up their lower-numbered fork. Both philosopher 0 and philosopher 4 try to grab fork 0 first. Suppose philosopher 0 wins. Since philosopher 4 is stuck waiting for fork 0, philosopher 3 will be able to grab both is forks and start eating.
Dijkstra suggests a better solution. He shows how to derive the solution by thinking about two goals of any synchronization problem:
With this observation, the solution almost writes itself (See also Figure 2-20 on page 59 of Tanenbaum.)
Semaphore mayEat[5] = { 0, 0, 0, 0, 0}; Semaphore mutex = 1; int state[5] = { THINKING, THINKING, THINKING, THINKING, THINKING }; void take_forks(int i) { mutex.down(); state[i] = HUNGRY; test(i); mutex.up(); mayEat[i].down(); } void put_forks(int i) { mutex.down(); state[i] = THINKING; test(i-1); test(i+1); mutex.up(); } void test() { if (state[i]==HUNGRY && state[i-1]!=EATING && state[i+1] != EATING) { state[i] = EATING; mayEat[i].up(); } }The method test() checks for a violation of liveness at position i. Such a violation can only occur when philosopher i gets hungry or one of his neighbors finishes eating.
Although semaphores are all you need to solve lots of synchronization problems, they are rather ``low level'' and error-prone. As we saw before, a slight error in placement of semaphores (such as switching the order of the two down operations in the Bounded Buffer problem) can lead to big problems. It is also easy to forget to protect shared variables (such as the bank balance or the buffer object) with a mutex semaphore. A better (higher-level) solution is provided by the monitor (also invented by Dijkstra).
If you look at the example uses of semaphores above, you see that they are used in two rather different ways: One is simple mutual exclusion. A semephore (always called mutex in our examples) is associated with a shared variable or variables. Any piece of code that touches these variables is preceded by mutex.down() and followed by mutex.up(). Since it's hard for a programmer to remember to do this, but easy for a compiler, why not let the compiler do the work? 2
monitor class BankAccount { private int balance; public void deposit(int amount) { balance += amount; } // etc }The keyword monitor tells the compiler to add a field
Semaphore mutex = 1;to the class, add a call of mutex.down() to the beginning of each method, and put a call of mutex.up() at each return point in each method.
The other way semaphores are used is to block a process when it cannot proceed until another process does something. For example, a consumer, on discovering that the buffer is empty, has to wait for a producer; a philosopher, on getting hungry, may have to wait for a neighbor to finish eating. To provide this facility, monitors can have a special kind of variable called a condition variable.
class Condition { public void signal(); public void wait(); }A condition variable is like a semaphore, with two differences:
monitor BoundedBuffer { Buffer b; Condition nonfull, nonempty; public void enter_item(Object item) { if (b.isFull()) nonfull.wait(); b.enter_item(item); nonempty.signal(); } public Object remove_item() { if (b.isEmpty()) nonempty.wait(); item result = b.remove_item(); nonfull.signal(); return result; } }In general, each condition variable is associated with some logical condition on the state of the monitor (some expression that may be either true or false). If a process discovers, part-way through a method, that some logical condition it needs is not satisfied, it waits on the corresponding condition variable. Whenever a process makes one of these condtions true, it signals the corresponding condition variable. When the waiter wakes up, he knows that the problem that caused him to go to sleep has been fixed, and he may immediately proceed. For this kind of reasoning to be valid, it is important that nobody else sneak in between the time that the signaller does the signal and the waiter wakes up. Thus, calling signal blocks the signaller on yet another queue and immediately wakes up the waiter (if there are multiple processes blocked on the same condition variable, the one waiting the longest wakes up). When a process leaves the monitor (returns from one of its methods), a sleeping signaller, if any, is allowed to continue. Otherwise, the monitor mutex is released, allowing a new process to enter the monitor. In summary, waiters are give precedence over signallers.
This strategy, while nice for avoiding certain kinds of errors, is very inefficient. As we will see when we consider implemenation, it is expensive to swith processes. Consider what happens when a consumer is blocked on the nonempty condition variable and a producer calls enter_item.
To avoid this inefficiency, all recent implementations of monitors replace signal with notify. The notify operation is like signal in that it awakens a process waiting on the condition variable if there is one and otherwise does nothing. But as the name implies, a notify is a ``hint'' that the associated logical condition might be true, rather than a guarantee that it is true. The process that called notify is allowed to continue. Only when it leaves the monitor is the awakened waiter allowed to continue. Since the logical condition might not be true anymore, the waiter needs to recheck it when it wakes up. For example the Bounded Buffer monitor should be rewritten to replace
if (b.isFull()) nonfull.wait();with
while (b.isFull()) nonfull.wait();
Java has built into it something like this, but with two key differences. First, instead of marking a whole class as monitor, you have to remember to mark each method as synchronized. Every object is potentially a monitor. Second, there are no explicit condition variables. In effect, every monitor has exactly one anonymous condition variable. Instead of writing c.wait() or c.notify(), where c is a condition variable, you simply write wait() or notify(). A solution to the Bounded Buffer problem in Java might look like this:
class BoundedBuffer { Buffer b; synchronized public void enter_item(Object item) { while (b.isFull()) wait(); b.enter_item(item); notifyAll(); } synchronized public Object remove_item() { while (b.isEmpty()) wait(); item result = b.remove_item(); notifyAll(); return result; } }Instead of waiting on a specific condition variable corresponding to the condition you want (buffer non-empty or buffer non-full), you simply wait, and whenever you make either of these conditions true, you simply notifyAll. The operation notifyAll is similar to notify, but it wakes up all the processes that are waiting rather than just the one that has been waiting the longest. In general, a process has to use notifyAll rather than notify, since the process that has been waiting the longest may not necessarily be waiting for the condition that the notifier just made true. In this particular case, you can get away with notify because there cannot be both producers and consumers waiting at the same time.
Since shared variables are such a source of errors, why not get rid of them altogether? In this section, we assume there is no shared memory between processes. That raises a new problem. Instead of worrying about how to keep processes from interferring with each other, we have to figure out how to let them cooperate. Systems without shared memory provide message-passing facilities that look something like this:
send(destination, message); receive(source, messsage_buffer);The details vary substantially from system to system.
Message-based communication between processes is particularly attractive in distributed systems (such as computer networks) where processes are on different computers and it would be difficult or impossible to allow them to share memory. But it is also used in situations where processes could share memory but the operating system designer chose not allow sharing. One reason is to avoid the bugs that can occur with sharing. Another is to build a wall of protection between processes that don't trust each other. Some systems even combine message passing with shared memory. A message may include a pointer to a region of (shared) memory. The message is used as a way of transferring ``ownership'' of the region. There might be a convention that a process that wants to access some shared memory had to request permission from its current owner (by sending a message). The second algorithm of project 2 has this flavor.
Unix is a message-based system (at the user level). Processes do not share memory but communicate through pipes.3 A pipe looks like an output stream connected to an input stream by a chunk of memory used to make a queue of bytes. One process sends data to the output stream the same way it would write data to a file, and another reads from it the way it would read from a file. In the terms outlined above, naming is indirect (with the pipe acting as a mailbox or message queue), send (called write in Unix) is non-blocking, while recieve (called read) is blocking, and there is buffering in the operating system. At first glance it would appear that the message size is unbounded, but it would actually be more accurate to say each ``message'' is one byte. The amount of data sent in a write or recieved in a read is unbounded, but the boundaries between writes are erased in the pipe: If the sender does three writes of 60 bytes each and the receive does two reads asking for 100 bytes, it will get back the first 100 bytes the first time and the remaining 80 bytes the second time.
2Monitors are not available in this form in Java. We are using Java as a vehicle for illustrating various ideas present in other languages. See below for a similar feature that is available in Java.
3There are so many versions of Unix that just about any blanket statement about it is sure to be a lie. Some versions of Unix allow memory to be shared between processes, and some have other ways for processes to communicate other than pipes.