Guarded Suspension and Balking Patterns

Introduction

By Mark Grand

This is the second of a series of articles on design patterns related to concurrency. The focus of these articles is design-level solutions to problems that occur when a program is doing more than one thing at a time.

Sometimes a thread or process is prevented from completing what it is doing. If it is acceptable to wait until the thread or process can continue, you might find the Guarded Suspension pattern useful. If waiting is not acceptable, then you might find the Balking pattern useful.


Guarded Suspension

I will begin this explanation of the Guarded Suspension design pattern with a simple example of a problem it can be used to solve.

Suppose that you have to create a class that implements a queue data structure. A queue is a first-in/first-out data structure. Objects are removed from a queue in the same order they are added. Figure 1 shows a Queue class.

Figure 1. Queue Class.
Figure 1. Queue Class.

A queue class has two methods that are of particular interest:

  • The push method adds objects to a queue.
  • The pull method removes objects from the queue.


The environment you are developing for has a Queue class. However, the behavior of that class is perhaps not what you need. If you try to remove an object from an instance of the existing Queue class when it does not contain any objects, it throws an exception.

The desired behavior is that when a Queue object's pull method is called when the queue is empty, it does not return until there is an object in the queue for it to return. An object can be added to the queue while the pull method is waiting to return if another thread calls the push method. Both push and pull are guarded to allow multiple threads to safely make concurrent calls.

Guarded is a UML term that means only one thread at a time can execute a method. In Java*, guarded methods are usually implemented as synchronized methods. In C#*, guarded methods are implemented by wrapping the body of the methods in a lock statement like this.

void foo()


{


  lock (this)


  {


    …


  }


}

 

Figure 1 shows that the push and pull methods of the Queue class are both guarded. This creates a problem when there is a call to a Queue object's pull method and the queue is empty. The pull method waits for a call to the push method to provide it with an object to return. However, because they are both guarded, calls to the push method cannot execute until the pull method returns and the pull method will never return until a call to the push method executes.

A solution to the problem is to add a precondition to the pull method so that it does not execute when the queue is empty. Consider the collaboration diagram in Figure 2.

Figure 2. Queue Collaboration.

Figure 2. Queue Collaboration.

The diagram shows concurrent calls to a Queue object's push and pull methods. If the pull method is called when the Queue object's isEmpty method returns true, then the thread waits until isEmpty returns false before executing the pull method. Since it does not actually execute the pull method while the queue is empty, there is no problem with a call to the push method being able to add objects to an empty queue.


General Purpose Solution for Guarded Suspension

Before discussing the implementation of Guarded Suspension, I will restate the problem and its solution in more general terms.

Figure 3 shows a class named Widget. It has two guarded methods named foo and bar. There is an exceptional state that Widget objects can enter. While a Widget object is in the exceptional state, its isOK method returns false; otherwise, it returns true. When a Widget object is in the exceptional state, a call to its bar method may take it out of that state. There is no way to take it out of the exceptional state other than a call to bar. Taking a Widget object out of its exceptional state is a side effect of the bar method's main purpose, so it is not acceptable to call the bar method just to take a widget object out of its exceptional state.

Figure 3. Widget Class.
Figure 3. Widget Class.

A call to a Widget object's foo method cannot complete if the Widget object is in its exceptional state. If this happens, because the foo and bar methods are guarded, subsequent calls to the Widget ob ject's foo and bar methods will not execute until the pending call to foo returns. The call to foo will not return until a call to bar takes the Widget object out of its exceptional state.

The purpose of the Guarded Suspension pattern is to avoid the deadlock situation that can occur when a thread is about to execute an object's guarded method and the state of the object prevents the method from completing. If a method call occurs when an object is in a state that prevents the method from executing to completion, the Guarded Suspension pattern suspends the thread until the object is in a state that allows the method to complete. This is illustrated in the collaboration diagram in Figure 4.

Figure 4. Guarded Suspension Collaboration.
Figure 4. Guarded Suspension Collaboration.

Notice that Figure 4 indicates a precondition that must be satisfied before a call to a Widget object's foo method executes. If a thread tries to call a Widget object's foo method when the Widget object's isOK method returns false, the thread is forced to wait until isOK returns true before it is able to execute the foo method. While the thread is waiting for isOK to return true, other threads are free to call the bar method.

Implementations of the Guarded Suspension pattern in Java and C# are similar.

In Java, a method such as foo must satisfy preconditions before it actually begins executing. The first thing such a method does is test its preconditions in a while loop. While the preconditions are false, it calls the wait method of an appropriate object.

Every Java class inherits the wait method from the Object class. When a thread calls an object's wait method, the wait method causes the thread to release the synchronization lock it holds on the object. The method then waits until it is notified that it may return. Then, as soon as the thread is able to recapture the lock, the wait method returns.

When the wait method returns, control returns to the top of the while loop, which tests the preconditions again. The reason for testing the preconditions in a loop is that between the time that the thread first tries to recapture the synchronization lock and the time that it does capture it, another thread may have made the preconditions false.

The call to the wait method is notified that it should return when another method, such as bar, calls the object's notify method. Such methods call the notify method after they have changed the state of the object in a way that may satisfy a method's preconditions. All classes inherit the notify method from the Object class. The notify method notifies a waiting thread that it shoul d return.

The C# version is similar to the Java version. The C# equivalent of notify is Pulse. However C# classes do not inherit Wait and Pulse methods from Object. Instead, they are static methods of the System.Threading.Monitor class.

If more than one thread is waiting, the notify or Pulse method chooses one to notify arbitrarily. Arbitrary selection works well in most situations. It does not work well for objects that have methods with different preconditions.

Consider a situation in which multiple method calls are waiting to have their different preconditions satisfied. With arbitrary selection, the preconditions of one method call can be satisfied but the thread that gets notified or pulsed is waiting to execute a method with different preconditions that are not yet satisfied. In this situation, it is possible for a method call to never complete because the method is never notified when its preconditions are satisfied.

There is an alternative for classes where arbitrary selection is not a good way to decide which thread to notify or pulse. Their methods can call the notifyAll or PulseAll method. Rather than choosing one thread to notify or pulse, the notifyAll or PulseAll method notifies all waiting threads. This achieves notifying the right thread, but it may result in wasted machine cycles as a result of waking up the wrong threads.

Here are some code examples that implement the designs in the queue example:

Java: Queue.java (.zip)
C#: Queue.cs (.zip)  


Balking

The Guarded Suspension pattern is useful in situations where is acceptable to handle the inability to execute a method by waiting. If waiting is not acceptable, the Balking pattern may be useful. Once again, I will explain this by way of an example.

Suppose you are writing a program to control an electronic toilet flusher. Such devices are intended for use in public bathrooms. They have a light sensor on the front of the flusher. When the light sensor detects an increased light level, it assumes that a person has left the toilet and triggers a flush. Electronic toilet flushers also have a button to manually trigger a flush. Figure 5 is a class diagram showing classes to model this behavior.

Figure 5. Flusher Classes.
Figure 5. Flusher Classes.

When a LightSensor object or a FlushButton object decides that there should be a flush, it requests the Flusher object to start a flush by calling its flush method. The flush method starts a flush and then returns once the flush is started. This arrangement raises some concurrency issues.

What happens when the flush method is called while a flush is already in progress? What happens when both the LightSensor object and the FlushButton object call the Flusher object's flush method at the same time?

These are the three most obvious choices for how to handle a call to the flush method while there is a flush in progress:

  • Start a new flush immediately. Starting a new flush while a flush is already in progress has the same effect as making the flush in progress last longer than a normal flush. The optimal length of a normal flush has been determined through experience. A longer flush will waste water, so this is not a good option.
  • Wait until the current flush finishes and immediately start another flush. This option effectively doubles the length of a flush. It is a bigger waste of water than the first option.
  • Do nothing. This option wastes no water, so it is the best choice.


When there are two concurrent calls to the flush method, allowing one to execute and ignoring the other is also a good strategy.

Suppose a call is made to an object's method when the object is not in a state to properly execute the method. If the method handles the situation by returning without performing its normal function, we say that the method balked. UML does not have a standard way of indicating a method call with balking behavior. Figure 6 represent a balking method call with an arrow that curves back on itself.

Figure 6. Flusher Collaboration with Balking Behavior.
Figure 6. Flusher Collaboration with Balking Behavior.


General-Purpose Solution for Balking

Figure 7 is a collaboration diagram that shows the general case for the Balking pattern.

Figure 7. Balking Collaboration.
Figure 7. Balking Collaboration.

In Figure 7, a client object calls the doIt method of a Service object. The bent-back arrow indicates that the call may balk. If the Service object's doIt method is called when the Service object is in a state inappropriate for executing a call to its doIt method, then the method returns without having performed its usual functions.

The doIt method returns a result, indicated in the diagram as didIt. The result is either true or false, indicating whether the method performed its normal functions or balked.

Here are some code examples that implement the designs in the flusher example:

Java: Flusher.java (.zip)
C#: Flusher.cs (.zip)


Wrapping Up

In this article, we took a brief look at patterns that address the most basic of issues related to concurrent use of shared resources. In my next article, we will look at two other patterns:

  • Guarded Suspension
    What to do when you get exclusive access to a resource and then find that you need an unavailable resource to complete the operation.
  • Balking
    What to do when you can't wait to get exclusive access to an object.


The patterns in these articles are drawn from my book, Patterns in Java , Volume 1. The C# version of the book, Patterns in C# will be out in early 2003.


About the Author

Mark Grand is a consultant with over 23 years of experience who specializes in Distributed Systems, Object Oriented Design, Java and C#. He was the architect of the first commercial business-to-business e-Commerce product for the Internet. He is currently working on an open source framework for gluing components and programs into an application.

Mark Grand is most widely known for his best selling Patterns in Java books. His current book projects are titled Patterns in C# and Patterns in VB.NET. Mark has taught for U.C. Berkeley, Sun, and other organizations.

Prior to his involvement with Java and C#, Mark spent over 11 years as a designer and implementer of 4GLs. His most recent role in that vein was as the architect and project manager for an electronic data interchange product. Mark has worked with a number of MIS organizations in capacities such as Software Architect, Database Architect, and Network Designer.

Mark in based in the Atlanta area. He has been involved with object oriented programming and design since 1982.

You can find more information about Mark Grand at http://mgrand.home.mindspring.com*.

The information, opinions, and recommendations in this column are provided by the Author, Mark Grand. Intel and its subsidiaries do not necessarily endorse or represent the accuracy of the Author's information opinions or recommendations and any reliance upon the Author's statements is solely at your own risk.


Categories:
For more complete information about compiler optimizations, see our Optimization Notice.