A pattern for managing concurrency—written in Java!
Allan is chief technical officer for Rogue Wave Software. He can be contacted at [email protected].
Synchronous functions communicate with their callers by returning an object. The IOU design pattern I present here generalizes this to the asynchronous case--instead of a function returning an object, it returns an object IOU. The IOU is an agreement from a supplier (the function you called) that it will eventually close the IOU by providing the promised object. Once the IOU is closed, you can redeem the IOU for the object that the supplier provided. In the meantime, your code can continue to do useful things.
Two things make the IOU concept useful. First, it's simple. Calling a function that returns an IOU is just like calling any other function. Second, it is completely independent of the asynchronous mechanism (if any) used by the supplier. For example, code using IOUs looks exactly the same regardless of whether the supplier closes the IOU by launching a separate thread, talking to another process, making a remote procedure call, or waiting for a human to type a response into a dialog box.
All code in this article was written in Java. You can see it in action by pointing a Java-enabled browser at http://www.roguewave.com/~alv/iou. Of course, if the code was written in a different language, it would look a little different. For example, in C++, you would probably make IOU a template class, IOU<T>, so that it could be redeemed for a strongly typed object.
Using the IOU Class
The IOU class has four basic operations. The closed() function returns True if the IOU can be immediately redeemed. The standBy() function waits until the IOU is redeemable. The redeem() function returns the owed object. If the IOU is not closed, redeem() waits until the IOU is closed. Finally, the addCallback(f) function arranges for the function f to be called when the IOU is closed. The function has signature f(obj), where obj is the object referred to by the IOU.
The simplest way to demonstrate IOUs is with an example. Example 1 sends four Messenger objects to fetch four Dossier objects, then computes the size of all the dossiers put together.
Each call to getDossier() doesn't start until the previous one has completed, so the code takes about four times as long as fetching a single message. Since fetching a dossier takes a few seconds (the messenger might have to go across town), this is not good.
Example 2 shows how you could program this using IOUs. This time, all four messengers go out at once. The program takes only as long as the slowest messenger.
Adding Callbacks
Often, you'll want to do something as soon as an IOU is redeemable. For example, you might want to display the cover of the dossier as soon as it's available. Example 3 shows how to do this without IOUs.
The simplest way to do this with IOUs would be to get all of them and then redeem each one, displaying the image right after calling redeem. The problem is that while you're waiting to redeem John's IOU, Ringo's may become redeemable. Since you are still waiting for John, Ringo's image won't be put up as soon as possible.
IOU callbacks provide a way around this problem. Each IOU has an associated list of callbacks that will be executed as soon as the IOU is redeemable. Example 4 displays the covers as soon as the IOU can be redeemed. Listing One defines the interface for IOU callback objects.
Supplying IOUs
Figure 1 shows the key classes in the IOU pattern. The key abstraction from the IOU client's point of view is the IOU class shown in Listing Two. The IOU is simply a lightweight handle to the supplier's key abstraction--the Escrow object. It manages the object promised by the IOU, manages the supplier's synchronization policy and serves as the interface between the supplier and the client. The Escrow class shown in Listing Three is abstract: The synchronization policy is determined by how the particular subclass you instantiate implements the abstract functions standBy and redeem.
A SynchEscrow manages the synchronization by providing no synchronization. You must close escrow, by supplying the promised object, before building an IOU that refers to the escrow. The IOU is immediately redeemable. This escrow synchronization strategy is useful mainly as a placeholder for synchronous code that you may want to make asynchronous later. It is also useful for debugging.
When you construct a ThreadEscrow, you pass it a handle to the supplier code (in C++, this could be a pointer to a function; in Java, it is an object that satisfies a particular interface). The ThreadEscrow starts a new thread and runs the supplier code in the new thread. While the supplier code is running, you build an IOU that refers to the escrow and returns the main thread of control to the client. Once the supplier code finishes executing, the result of the computation is stored in the escrow, the escrow is closed, and the thread's execution is complete. The thread will be joined back to the main thread when standBy or redeem are called. ThreadEscrow is given in Listings Four and Five.
When a DialogEscrow is used, the asynchronous behavior is provided by a human filling in a dialog box. The escrow is associated at construction time with a nonmodal dialog. Once the escrow is created, IOUs can be generated, and the flow of control can be returned to the IOU client. Pressing OK on the dialog generates an event which, using the standard GUI mechanisms, returns control to the escrow. The escrow is then closed, and any outstanding IOUs can be redeemed.
IOU Groups
Sometimes you'll want to deal with many IOUs (with an IOU group) at once instead of one IOU at a time. Using an IOU group, you can wait for all IOUs in the group to be enabled, or wait for some number of IOUs in the group to be enabled.
A key design constraint for the IOU pattern was that IOU groups could be built using only the public IOU interface--an IOU group should not need to know which type of Escrow the IOUs in the group are using. This was the initial motivation for the callback functionality in IOU. By using callbacks, the IOU group can arrange to be signaled when there is a change in any of the IOUs in the group.
Streaming Models
You can either redeem an IOU in total, or it is not yet ready; there is no middle ground. In some asynchronous applications, this is not a valid assumption. For example, when receiving images you may be able to do useful things to the image before it has been completely received. In this case the IOU pattern does not apply. Instead, a streaming pattern (such as that described by Gabe B. Beged-Dov et al., in an OOPSLA '95 workshop paper entitled "The Pipeline Design Pattern") might be more appropriate.
Summary
The IOU pattern is a simple, intuitive way to add asynchronous behavior to applications. By adding interfaces that deliver IOUs, instead of simply supplying objects, you can achieve concurrency without explicitly dealing with concurrency primitives. Since the IOU pattern is designed independent of any particular concurrency mechanisms, it is applicable to many different concurrency methods, from event-driven systems to distributed systems to threaded systems.
Figure 1: Classes in the IOU pattern.
Example 1: Fetching dossiers synchronously.
// john, paul, george, ringo are Messenger objects Dossier d1 = john.getDossier(); Dossier d2 = paul. getDossier(); Dossier d3 = george. getDossier(); Dossier d4 = ringo. getDossier(); int l = d1.length()+d2.length()+d3.length()+d4.length();
Example 2: Fetching dossiers using IOUs.
IOU iou1 = john. getDossierIOU(); // First get IOUs IOU iou2 = paul. getDossierIOU(); IOU iou3 = george. getDossierIOU(); IOU iou4 = ringo. getDossierIOU(); Dossier d1 = (Dossier)iou1.redeem(); // Redeem the IOUs Dossier d2 = (Dossier)iou2.redeem(); Dossier d3 = (Dossier)iou3.redeem(); Dossier d4 = (Dossier)iou4.redeem(); int l = d1.length()+d2.length()+d3.length()+d4.length();
Example 3: Showing the covers without IOUs.
// display1 et al are screen display panels Dossier d1 = john.getDossier(); display1.show(d1.cover); Dossier d2 = paul. getDossier(); display2.show(d2.cover); Dossier d3 = george. getDossier(); display3.show(d3.cover); Dossier d4 = ringo. getDossier(); display4.show(d4.cover)
Example 4: Using callbacks to redeem IOUs.
// display1 et al satisfy IOUCallback interface, // so display1.run(dossier) draws the Dossier on // the screen IOU iou1 = john.getDossierIOU(); iou1.addCallback(display1); IOU iou2 = paul. getDossierIOU(); iou2.addCallback(display2); IOU iou3 = george. getDossierIOU(); iou3.addCallback(display3); IOU iou4 = ringo. getDossierIOU(); iou4.addCallback(display4);
Listing One
/* File: IOUCallback.java */
/**
* An object to be run when an IOU is closed. Each Escrow has a list
* of these objects. They get fired when the IOU's escrow is closed.
* @see IOU, Escrow
* @author: alvis, 1/26/96
*/
package iou;
public interface IOUCallback {
public void run(Object o);
};
Listing Two
/* File: IOU.java */
package iou;
/**
* An IOU is a token that you can later redeem for an actual object.
* IOUs are typically returned from functions that build their results
* asynchronously.
* An IOU refers to an Escrow object. The Escrow is responsible for
* obtaining and holding on to the object referred to by the IOU.
* @author Alvis, 2/7/96
*/
public class IOU extends Object {
private Escrow escrow_;
/**
* Check if the IOU can be immediately redeemed. If this returns
* true, then none of IOUs member functions will block. If it
* returns false then standBy and redeem will likely block.
*/
public boolean closed() {return escrow_.closed();}
/**
* Wait until the object is ready. This will cause this thread of
* execution to block.
* @exception InterruptedException When the thread is interupted before
* the IOU is enabled.
*/
public void standBy() throws InterruptedException {escrow_.standBy();}
/**
* Get the object promised by the IOU.
* This will block if the IOU has not been enabled yet.
* @exception InterruptedException When the thread is interupted before
* the IOU is enabled.
*/
public Object redeem() throws InterruptedException {return escrow_.redeem();}
/**
* The run(Object) object interface in the IOUCallback
* will be invoked when the IOU is enabled. The object passed
* as a parameter to the callback is the IOU's value.
* The callback is normally run in the same thread in which the
* escrow is enabled.
* If the IOU is already enabled, then it will be run immediately.
*/
public void addCallback(IOUCallback callback)
{
escrow_.addCallback(callback);
}
/**
* Remove a callback that was previously added. If the callback
* is not on the callback list it is ignored.
*/
public void removeCallback(IOUCallback callback)
{
escrow_.removeCallback(callback);
}
/**
* Normally, you receive IOUs as return values from functions, you
* don't build them yourself. If you are giving out IOUs, you should
* obtain them from Escrow.iou.
*/
public IOU(Escrow e) {escrow_ = e;}
}
Listing Three
/* File: Escrow.java */
package iou;
/**
* Escrow mediates the transaction between someone with an IOU, and
* the party that gave out the IOU. Before you can give out an
* IOU, you must create an Escrow. The IOU will refer to the Escrow
* for all of its functionality. You must (eventually) enable the
* Escrow before any IOU which refer to this Escrow can be redeemed.
* This is an abstract base class. The mechanism used to wait until
* the Escrow is enabled is implemented by overriding the function
* block(). The default mechanism for holding the object is to
* keep a copy in a variable in the Escrow. It is expected that
* some subclasses will override enabled(), value(), enable(), and
* block() to change this policy.
* @see IOU
* @author Alvis, 1/25/96 and 3/19/96
*/
public abstract class Escrow extends Object {
private boolean closed_; //can IOUs be redeemed without blocking?
private java.util.Vector callbackList;//fire when ready
/**
* Constructor.
*/
public Escrow()
{
closed_ = false;
callbackList = new java.util.Vector();
}
/**
* Return an IOU which refers to this Escrow.
* The normal method of using an Escrow is to create the Escrow, and
* then use this method to give out IOUs.
*/
public IOU iou() {return new IOU(this);}
/**
* Close the IOU. Once this is called, then redeem() and standBy()
* must return without blocking.
* Closing the IOU will run any callbacks which have been queued up.
* Closing escrow more than once has no effect.
* There can only be one first time.
*/
synchronized protected void close()
{
closed_ = true;
Object value = redeemAfterClose();
// Fire the callbacks in the order they were provided.
// The callback list has no elements if we have already closed escrow.
for(int i=0; i
Listing Four
/* File: ThreadEscrow.java */
package iou;
/**
* A framework for building IOUs by putting the supplier in its own thread.
* A ThreadEscrow computes its value in a thread that it controls.
* You pass the escrow an ObjectMaker when you construct it.
* ObjectMaker is a simple interface; it requires a run function which
* builds up the object.
* The Escrow builds a thread and runs the ObjectMaker in that thread.
* When the ObjectMaker returns, its value is put in Escrow and the
* thread exits.
* The thread uses a ThreadEscrowWorker class as its Runnable object.
* The ThreadEscrowWorker knows about the Escrow, and can therefore
* stuff the object produced by the ObjectMaker into the Escrow.
* The standBy() function needs to wait for the thread that was launched
* in the constructor. This should be possible using Thread.join(),
* but unfortunately Netscape has a bug where Thread.join() blocks
* forever (it has been reported, see
* http://www.roguewave.com/~alv/javaThreadBug.html for an example).
* To get around this, the ThreadEscrowWorker has a waitForRunToFinish()
* function.
* @author: Alvis, 1/26/96
*/
public class ThreadEscrow extends Escrow {
private Thread thread_; // started in the constructor
private ThreadEscrowWorker worker_; // the Runnable action in the thread
Object value_; // at closing, the value is set here
/**
* Start up a new thread to supply the object. Once the
* object is supplied, the new thread will set value_ and
* close escrow.
*/
public ThreadEscrow(ObjectMaker maker)
{
worker_ = new ThreadEscrowWorker(this,maker);
thread_ = new Thread(worker_);
thread_.start();
}
/**
* Waits until the worker thread has completed. When the thread
* has completed it will set value_.
*/
public void standBy() throws InterruptedException
{
// thread_.join(); - doesn't work due to Netscape bug - see top of file
worker_.waitForRunToFinish();
if (!worker_.isFinished()) {
throw new InterruptedException();
}
}
/**
* Redeem the object. If necessary, this will wait for the thread to
* finish computing the object.
*/
public Object redeem() throws InterruptedException
{
standBy(); // if value_ is already set, this comes back fast
return value_;
}
}
/**
* Do the work of supplying an object to a ThreadEscrow.
* This class manages a thread which runs the function which supplies
* the object to the ThreadEscrow. It should only be created by
* a ThreadEscrow.
*/
class ThreadEscrowWorker extends Thread {
ThreadEscrow escrow_; // my creator
ObjectMaker maker_; // what I'm supposed to do
boolean runFinished_; // has run finished executing?
ThreadEscrowWorker(ThreadEscrow e, ObjectMaker m)
{
maker_ = m;
escrow_ = e;
runFinished_ = false;
}
public boolean isFinished() {return runFinished_;}
public synchronized void run()
{
Object value = maker_.run();
escrow_.value_ = value;
runFinished_ = true;
escrow_.close();
notify(); // threads may be waiting in waitForRunToFinish()
}
synchronized void waitForRunToFinish()
{
while (isFinished()==false) {
try {
wait(); // run() will call notify
}
catch(InterruptedException e) {}
}
notify(); // There may be other threads waiting in waitForRunToFinish()
}
}
Listing Five
/* File: ObjectMaker.java */
/**
* A simple interface for objects that produce an object.
* @author: Alvis, 1/26/96
*/
package iou;
public interface ObjectMaker {
public Object run();
}
