Since the appearance of multi-processor computers and multi-tasking operating systems, programmers have been interested in concurrent programming-- doing several tasks in parallel, then putting the pieces together at the end to produce a final answer. Even on single-processor computers concurrent programs offer advantages, because much of the scheduling and control information that would be needed in a traditional program is managed by the underlying operating system, instead; so programmers only need to concentrate on describing the independent sub-tasks that must be performed.

There are problems with concurrency, however. The biggest problem is that if each task is to be performed by a separate program, all running on the same single-processor computer, then we will have to add the time it takes the operating system to switch the processor from one program to another to the overall processing time. This time can be considerable, because when control of the CPU is switched from program A to program B, then some or all of B's data and control information may need to be restored from spacious, low-speed memories to cramped, high-speed memories, while some or all of A's data and control information may need to be saved from the high-speed memories back to the low-speed memories.

Many operating systems solve this problem for us. Instead of implementing a concurrent algorithm as a loose collection of collaborating programs, programmers can implement it as a single master program that "fathers" several "child programs" that perform the various sub-tasks in parallel, then report their results back to the master. These child programs are called threads, or light-weight processes.

What makes this idea an improvement is that a thread isn't a full fledged program with its own data and control information. Instead, the thread simply uses the data and control information of its parent program (or most of it, anyway). This means switching the CPU from one thread to another is relatively efficient.

An object-oriented operating system might represent each thread as an object that "controls" other objects representing system resources such as memory, processors, or I/O devices. In fact processes, the objects that represent ordinary programs, are simply threads that control additional resources:

In a simplified operating system, a thread is always in one of at least four states: Ready (waiting for the CPU), Running (using the CPU), Blocked (waiting for input), or Terminated. We can represent these states, the transitions between them, and the actions that cause transition to occur using a state diagram:

It is the job of an operating system component called the scheduler to perform the switch and preempt actions. Switching means switching control of the processor from the thread that currently controls the processor to the next thread in the ready queue. All threads in the ready queue are in the Ready state, because they are ready to use the processor. A thread that controls a processor is in the Running state, because it uses its processor to run.

What makes a running thread give up control of a processor? When the task performed by a thread is complete, then the thread stops. Also, the operating system will require a running thread to release its processor and enter a Blocked state while it waits for input to arrive. Some operating systems will even preempt a thread that attempts to starve its siblings by consuming large slices of processor time without releasing it to the others. Finally, cooperative threads voluntarily release processor control on occasion, either by auto-transitioning back to their Ready state, or by auto-transitioning to their Blocked state for a specific amount of time (sleeping).

Naturally, the more interesting concurrent programs are the ones where the threads collaborate in interesting ways. Obviously, meaningful collaboration requires communication. But how can threads communicate? Broadly speaking, there are two techniques: message passing and shared memory.

In some cases a parent thread might provide message brokering services for its children. Essentially, the parent thread acts like a post office: a child thread gives the parent a message, which the parent eventually forwards to the recipient child thread. Of course this is very similar to the job of the message pump of a Windows application.

While using the parent as a message broker promotes decoupling among the child threads, it introduces two inefficiencies. First, all messages must pass through a middle man-the broker. Second, there will have to be some limit on the amount of information that can be sent in a single message.

All child threads can easily access their parent thread's global data structures. This means they can communicate directly through these data structures: if thread A changes the engine design on a global CAD/CAM model of a car, then thread B will be able to see this change, and therefore will take it into account as it estimates the total cost of the car. This is the basic idea behind shared memory communication. In effect, global data structures act like abstract mailboxes. Thread A places a "message" for thread B in mailbox M. Later, thread B removes the message and reads it. No middle man is required, and messages can hold as much information as we like. But the downside is this: what happens if thread B checks mailbox M before thread A posts the message? In this case B may not get the message, which may result in an error.

Sometimes it's difficult for programmers to cope with problems like this, because they are accustomed to being able to predict the execution order of a sequence of instructions. While the execution order of instructions being executed by a single thread is predictable, the execution order of instructions being executed by different threads isn't.

Once again the operating system comes to our rescue, this time by supplying synchronization mechanisms: objects that work like latches and locks. If we equip mailbox M with a locked latch, L, then if Thread B doesn't have a "key", it must wait next to the mailbox for the latch to be unlocked. Of course this will only happen after thread A, which does have a key, puts its message inside M.

Combining multi-threading and object-orientation produces the powerful idea of an active object: an object that "owns" a thread of control. Until now, all of the objects we have dealt with have been passive. A passive object does nothing unless a client calls one of its member functions. When the member function terminates, the passive object goes back to doing nothing. But an active object doesn't need to wait for a client to call one of its member functions. Instead, it can use its thread to execute a control loop that perpetually searches for work to be done:

In effect, an object-oriented concurrent program can be seen as a society of active objects, each behaving like a tiny virtual machine that drives the application toward a goal. Of course there may be many active objects, each with its own goal. In some cases these goals may even conflict with each other, but the overall effect is that the application is collectively driven toward some larger goal.

Active objects are particularly useful in simulations of systems containing autonomous, active elements.

Designing a program as a society of active objects can lead to chaos. To avoid this fate, most multithreaded applications instantiate some variant of the Master-Slave design pattern:

Assume threads are represented as instances of a Thread class. Then an active object is an instance of a class derived from or associated with the Thread class:

In the Master-Slave pattern active master object creates many active slave objects. Each slave object retains a pointer back to its master:

Each slave performs some task, then reports its result back to the master. The master accumulates results and produces a final result.

Java's Thread class makes multithreading of the underlying host operating system available to programmers. We extend the Java Thread class like any other class, except we usually redefine the inherited run() method:

Threads can be launched using the start() method, which calls the run() method:

Sometimes it makes more sense to extend another class. Since Java doesn't support multiple inheritance (like C++), we must implement the Runnable interface. This requires defining a run() method as before, as well as creating a thread to run:

At any moment a thread can be in any one of the eight states shown in below. Most of the transitions are thread methods discussed below:

Java multithreading is implemented using the multithreading system provided by the host platform. On single-processor computers there are two types of multithreading systems: preemptive and nonpreemptive. In a non-preemptive system all runnable threads wait in a ready queue for the currently running thread to release the CPU. This either happens because it terminates, requests I/O, or calls suspend(), wait(), sleep(t), yield(), or stop().

In a preemptive system the CPU is allocated to a thread for a fixed time slice (e.g. one second). If a thread doesn't release the CPU before its time slice expires, it will be interrupted, sent back to the ready queue, and the CPU will be allocated to the "next" thread in the ready queue.

The Java ready queue is a priority queue. This means threads are inserted according to their priority. The maximum priority of a Java thread is 10, the minimum priority is 1, and the normal priority is 5. If a thread has priority n, it will be inserted into the queue behind all threads with priority ≥ n, but ahead of all threads with priority < n. The Thread.getPriority() and Thread.setPriority() methods can be used to learn and modify a thread's priority. When a thread calls yield() or is preempted, it rejoins the ready queue, but if all other threads in the ready queue have lower priority, then the same thread immediately regains control of the CPU.

Most multithreading systems are preemptive, but some are not (e.g. Solaris' "green threads"). This means multithreaded Java programs can exhibit platform-dependent behavior. One way to mitigate this problem is to write cooperative threads. A thread is cooperative if it occasionally releases the CPU specifically so other threads can run. There are two ways to do this: by calling the yield() method, or the sleep(t) method where t is an integer. We already mentioned that yield() doesn't guarantee a different thread will be allocated the CPU. The sleep(t) call forces the thread to suspend itself for t milliseconds.

In the bouncing ball applet each ball is animated by its own slave thread. New balls are created by mouse clicks. Keyboard inputs stop, suspend, and resume the balls:

If you have a JDK 1.1 enabled browser, the applet is located at:

Bounce is a fairly simple example of a multi-threaded application, because the bouncing ball threads don't need to communicate with each other. In more complicated problems threads do need to communicate with each other.

Threads can communicate with each other by message passing, but this isn't very efficient; the message must be dispatched to a handler function by the receiver thread, and only small amounts of information can be packed into the message.

A more efficient method of communication is through shared memory. This is particularly easy to set up in the Master-Slave architecture because all slaves share their master's heap and static memory segments. In this case thread A simply makes a modification to some global data structure. For example, the data structure might represent a mailbox where messages can be stored. Later, thread B simply examines the global data structure to see what thread A has done. For example, thread B might remove the message from the mailbox and read it.

But there is a problem. Suppose thread B checks the mailbox before thread A has had a chance to put the message inside? While we can predict the execution order of instructions within a single thread, there is no way in general to predict the execution order for instructions executed by different threads. If thread B misses the message, this could change the behavior of the entire application. This may even result in an error!

This type of problem is particularly difficult for programmers who feel the need to control every aspect of their program's behavior. To solve problems like these programmers use synchronization mechanisms provided by the operating system. A synchronization mechanism allows one thread to lock the global data structure until it is finished. Other threads must wait for the data structure to be unlocked before they can access it.

Producer-Consumer problems are a family of similar problems that are traditionally used to demonstrate synchronization problems and solutions. Generally speaking, a master thread creates a global buffer and two slave threads. One slave is called the producer. The producer perpetually creates imaginary objects called widgets and places them in the global buffer. The other slave is called the consumer. The consumer repeatedly removes widgets from the buffer and consumes them:

Producer-Consumer presents several synchronization problems. For example, if the slaves aren't clever, the consumer slave may consume the last widget in the buffer and suspend itself, waiting for the producer to produce more widgets. At the same time, the producer slave adds a second widget to the buffer, failing to realize that the first widget is in the process of being consumed. If the producer only notifies the consumer when it adds a widget to the empty buffer, no notification is sent. The producer proceeds to fill the buffer with widgets. When the buffer is full, the producer suspends itself, waiting for the consumer to consume some widgets to make more room in the buffer. Of course at this point both the producer and consumer are suspended!

A joint checking account is a simple example of a producer-consumer problem. Our simulation will run as a console application. Consumer and producer worker threads will be equipped with pointers to a shared checking account (the buffer). The producer repeatedly deposits money in the joint account, while the consumer repeatedly withdraws money. (We won't name names.)

The account plays the role of the shared buffer. Widgets are dollars:

A producer deposits $10 into a shared account five times:

A consumer withdraws $5 from the shared account 5 times:

The master creates an account with $100, a producer slave, and a consumer slave:

Here's the output produced:

But wait, something is wrong. The "insufficient funds" message never appears, so the consumer withdrew $5 five times; a total of $25. Of course the producer deposits $10 five times for a total of $50. There was $100 in the account initially, so the closing balance should have been $100 + $50 - $25 = $125, not $150. What happened?

Things went wrong at the very start of the run:

The consumer starts to withdraw $5. In the middle of the transaction, the producer interrupts and begins a $10 deposit. Now the consumer interrupts the producer to complete its transaction, leaving a balance of $95 in the shared account. But it's too late. The producer has already copied the $100 balance into a local variable and incremented it to $110. When it regains control of the CPU, it copies its local variable back into the balance member variable of the shared account, over writing the $95 balance. The bank has just lost $5! (Which perhaps isn't so tragic, but it could just as easily been the customer!)

We can represent this situation using a sequence diagram:

Readers might think that the root of the problem is the leisurely pace of the Account's deposit() and withdraw() methods. Perhaps if we reduced these functions to single lines we could have avoided the interruption problem:

This idea appears to work until we set the producer and consumer cycle counters to a large value, say 30,000, then, eventually, the problem reappears. The real problem is that while an assembly language instruction may be indivisible-i.e., the CPU will complete execution of an assembly language instruction without interruption-- the same is not true for a C++ or Java instruction. Even the simple Java instruction:

may translate into several assembly language instructions:

Eventually this sequence will be interrupted by the consumer thread sometime after the first instruction but before the last. When that happens, the amount withdrawn will be lost.

Any object that can control the number of threads that can call its methods is called a monitor. We can make a Java object a monitor by writing "synchronized" in front of any methods that access important member variables.

Notice that the producer and consumer no longer interrupt each other:

Lets try another experiment. Suppose the master created a joint account with an initial balance of $0. Here's the output produced:

In this case the producer deposited $10 five times for a total of $50, while the consumer withdrew $5 four times for a total of $20, leaving a closing balance of $30. This is as it should be, but a supply-side economist would frown. There's no greater sin than to turn away eager consumers because lazy producers are slacking off.

When a thread calls wait() inside a monitor, the thread is blocked placed in the associated queue. It can only be unblocked if another thread calls notifyAll() inside the same monitor. This allows us to achieve more sophisticated forms of synchronization.

Now the consumer is never turned away hungry:

If objects A and B are separated by a machine boundary, then they must communicate with each other by sending messages across a network. The simplest method is to equip A and B with connected sockets. A socket is basically a transceiver. A transceiver combines a transmitter (an object that can be used to send or transmit messages) with a receiver (an object that can receive messages). Telephones, CB radios, and mailboxes are examples of transceivers. Of course a transceiver is only useful if it is connected to another transceiver in such a way that messages sent by one are received by the other and vice versa.

Most standard Internet servers- ftp servers, telnet servers, web servers, etc.- perpetually listen for clients at well known port numbers below 100. For example, most computers are equipped with a date server that listens for clients at port 13. When a connection is made, the date server sends the local date and time to the client.

Constructor

Listener

Constructor

Run Loop

Processing Commands

In some sense we are using the term "direct communication" to mean just the opposite. Instead of normal, "face-to-face conversation", two objects separated by a process boundary must communicate with each other through sockets. To make matters worse, using sockets requires some awareness of network protocols and addressing formats. Also, transmitting anything other than a string through a socket is difficult.

In the context of C++ objects, "face-to-face conversation" means invoking member functions. No special transceiver device is required, parameters and return values can be arbitrary objects, and objects can be located using ordinary pointers rather than protocol-dependent network addresses.

Remote method invocation (RMI) combines the best of both worlds by allowing distributed objects to communicate by ordinary member function invocations. This illusion is created by introducing proxies- local representatives of remote objects- into the address space of each object. Instead of direct communication, distributed objects communicate indirectly through proxies, which hide the details of direct communication.

Suppose we want to add features to a server. The obvious way to do this would be to create a derived class with the added features:

Of course this doesn't add features to the original server. Instead, we must create new servers that instantiate the derived class.

Another approach uses the idea of the Decorator pattern introduced in Chapter 4. Instead of creating a server object that instantiates a derived class, we place a decorator-like object called a proxy between the client and the server. The proxy intercepts client requests, performs the additional services, then forwards these requests to the server. The server sends any results back to clients through the proxy.

The proxy implements the same interface as the server, so from the client's point of view the proxy appears to be the actual server. Of course the proxy has no way of knowing if the server it delegates to is the actual server or just another proxy in a long chain, and of course the server has no way of knowing if the object it provides service to is an actual client or a proxy. The idea is formalized by the Proxy design pattern:

To simplify creation of proxies, a Proxy base class can be introduced that facilitates the creation of delegation chains:

The class diagram suggests that process or machine boundaries may exist between proxies. Proxies that run in the same process or on the same machine as the client are called client-side proxies, while proxies that run in the same process or on the same machine as the server are called server-side proxies.

As in the decorator pattern, proxies can be chained together. The client, and each proxy, believes it is delegating messages to the real server:

A firewall proxy is essentially a filter that runs on the bridge that connects a company network to the Internet. It filters out client requests and server results that may be inconsistent with company policies. For example, a firewall may deny a local web browser's request to download web pages from sites considered to host non work-related material such as today's Dilbert cartoon.

A cache proxy is a client-side proxy that searches a local cache containing recently received results. If the search is successful, the result is returned to the client without the need of establishing a connection to a remote server. Otherwise, the client request is delegated to the server or another proxy. For example, most web browsers transparently submit requests for web pages to a cache proxy, which attempts to fetch the page from a local cache of recently downloaded web pages.

Virtual proxies provide a partial result to a client while waiting for the real result to arrive from the server. For example, a web browser might display the text of a web page before the images have arrived, or a word processor might display empty rectangles where embedded objects occur.

Protection proxies can be used to control access to servers. For example, a protection proxy might be inserted between the CIA's web server and the Internet. It demands user identifications and passwords before it forwards client requests to the web server.

A synchronization proxy uses techniques similar to the locks discussed earlier to control the number of clients that simultaneously access a server. For example, a file server may use a synchronization proxy to insure that two clients don't attempt to write to the same file at the same time.

High-volume servers run on multiple machines called server farms. A load balancing proxy is a server-side proxy that keeps track of the load on each server in a farm and delegates client requests to the least busy server.

Counting proxies are server-side proxies that maintain usage statistics such as hit counters.

Communicating with remote objects through sockets is awkward. It is entirely different from communicating with local objects, where we can simply invoke a member function and wait for a return value. The socket adds an unwanted layer of indirection, it restricts us to sending and receiving strings, it exposes the underlying communication protocol, and it requires us to know the IP address or DNS name of the remote object.

A remote proxy encapsulates the details of communicating with a remote object. This creates the illusion that no process boundary separates clients and servers. Clients communicate with servers by invoking the methods of a client-side remote proxy. Servers communicate with clients by returning values to server-side remote proxies. This is called Remote Method Invocation or RMI.

For example, a client simply invokes the member functions of a local implementation of the server interface:

Internally, the client's constructor creates a client-side remote proxy, which is commonly called a stub:

Stubs use IPC mechanisms such as sockets to forward client requests to server-side remote proxies, which are commonly called skeletons. A Java skeleton customizes a Java version of our server framework and implements the server interface by delegating to a real server:

The real server simply returns computed results to its local caller, the skeleton. Therefore, the server doesn't need to depend on any special inter-process communication mechanism:

The skeleton slave handles the communication with the client's stub and invokes the appropriate methods of its master, the skeleton:

Remote proxies can be quite complex. In our example, the message sent from the stub to the skeleton includes the name of the requested service, "serviceA," and the parameters: x, y, and z. Of course x, y, and z need not be strings. They might be C++ numbers (in which case the stub will need to converted them into strings by inserting them into string streams) or they might be arbitrary C++ objects (in which case the stub will need to serialize them using the techniques of Chapter 5). This process is called marshalling.

The problem is even more complicated in our example because the server implementation is apparently a Java object, not a C++ object. Thus, after the skeleton deserializes x, y, and z, it will have to translate them into Java data. For example, an ASCII string representing a C++ number will have to be converted into a Java Unicode sting, probably using Java character streams, then the Java string must be converted into a Java number. This process is called de-marshalling.

Of course the skeleton must marshal the result before sending it back to the stub, and the stub must de-marshal the result before returning it to the client.

Finally, the reader may well ask how the skeleton knows a received request is a string containing C++ parameters and therefore C++ to Java translation should be performed, or how does the stub know a received result is a string containing Java data and therefore Java to C++ translation should be performed? Remember, clients and servers are often developed independently.

One way to solve this problem is for all programmers to agree on a common object oriented language, let's call it COOL. Marshalling must include translating data from the implementation language into COOL, and de-marshalling must include translating data from COOL into the implementation language.

Of course getting programmers to agree on what COOL should be is difficult. The Object Management Group (OMG), is promoting a standard called the Interface Description Language, IDL. An IDL description of ServerIntf looks an awful lot like a C++ header file. Compilers are available that will automatically translate IDL interfaces into stubs and clients in most object oriented languages, including Java and C++. Microsoft is promoting a standard called the Component Object Model (COM). COM interfaces are objects that can be discovered by clients at runtime through a COM meta interface.

In the following scenario we enhance a real server by adding four proxies between it and a client. On the client side we have a cache proxy and a stub. On the server side we have a skeleton and a synchronization proxy. The stub and skeleton perform parameter marshalling and de-marshalling.

All server interfaces must extend the java.rmi.Remote interface. All methods must throw the java.rmi.RemoteException:

All servers must extend some concrete extension of the RemoteServer class. The java.rmi.server package supplies UnicastRemoteObject:

Our implementation:

Executing the line:

registers the server with the local naming service.

The Control Loop

execute()

main()

The line:

prevents a rogue stub from doing something nasty.

The line:

returns a Table stub.

The rmi compiler generates TableServer_stub.class. In jdk 1.1 it also generated TableServer_skel.class, but this is no longer needed.

The name server is similar to our table server. It maintains a table containing associations between server names and references to server implementations.

or

We start a table server.

or

This calls main(), which calls:

To allow clients to connect to the naming server, you need to create a security policy that allows clients to connect with sockets with large port numbers:

When we start the client we specify the security policy:

And later another client produces the output:

Of course we need to change main() in the table client so that it gets a stub for "animals2" instead of "animals".

Messages are carried across networks using prescribed formatting and addressing protocols. The Socket API partially hides these details from programmers. We can complete the cover up by abstracting the network into an object called a message broker. A message broker is like a virtual network. It provides a name resolution service to hide network-dependent addresses, and it provides functions for sending and receiving messages.

There are many kinds of brokers that allow us to create interesting types of network services. A call back broker is similar to a publisher. It allows subscribers to register functions that should be called when a certain type of message for the subscriber is received by the broker. This is similar to the event manager discussed in the problem section of Chapter 2. Recall that an event manager is a notification mechanism that calls a registered subscriber function when a certain type of event occurs.

Technically, a dispatcher isn't really a broker, it is simply a name server similar to the table server implemented earlier, only it stores associations between names of servers and their current locations. A location might be a pointer, OID, IP address, port number, or URL. A dispatcher is comparable to the white pages in a telephone directory- a client that knows the name of a server, but not its location, so it asks a dispatcher to look up the location. After that, it's up to the client to establish a connection to the server. Port mapper daemons and domain name servers are examples of dispatchers.

If a dispatcher is analogous to the white pages of a telephone directory, then a trader system is analogous to the yellow pages. A client knows the name of the service it wants performed, so it contacts a trader system to get the location of a convenient server that currently provides this service. "Convenient" might mean "nearby" or "not busy".

Here is the basic Broker design pattern:

An in-process broker is used to pass messages between local objects:

For example, every MFC program is driven by a controller called theApp:

This controller is essentially an active message broker (see Problem 7.11). It perpetually monitors a message queue. When a message arrives, theApp extracts it and forwards it to its target. This design is useful for communication between threads. It also promotes looser coupling between objects.

An out-of-process broker might use remote proxies to create the illusion that each correspondent has an in-process broker implemented in the correspondent's language:

ORB architectures such as CORBA and Java RMI combine brokers with remote server proxies:

Brokers may also use the Chain of Command design pattern to forward messages to other brokers. For example, each computer on a network may have a broker that knows about all servers running on its machine. Requests for other servers are forwarded to a broker running on another machine according to some routing algorithm. (See Problem 7.13.)

We began this chapter with a discussion of threads, locks, and the Master-Slave design pattern. This was the architecture we subsequently used for our server framework, which we subsequently specialized into the command server framework.

Our clients and servers communicated through awkward, transceiver-like devices called sockets. We were able to hide sockets inside remote proxies on both the server side (skeletons) and the client side (stubs). Remote proxies created the illusion that clients and servers were communicating using ordinary method call and return mechanisms. By introducing brokers we were able to further decouple clients from servers. Now clients only needed to know the name of a server, not its location.

Remote method invocation completes the merger of object-oriented programming with client-server programming, the two great programming paradigms of the 1990s. By adding a sophisticated persistence mechanism such as an object-oriented database, the location of an object (local, remote, or in storage) becomes irrelevant.