HomeDigital EditionSys-Con RadioSearch Java Cd
Advanced Java AWT Book Reviews/Excerpts Client Server Corba Editorials Embedded Java Enterprise Java IDE's Industry Watch Integration Interviews Java Applet Java & Databases Java & Web Services Java Fundamentals Java Native Interface Java Servlets Java Beans J2ME Libraries .NET Object Orientation Observations/IMHO Product Reviews Scalability & Performance Security Server Side Source Code Straight Talking Swing Threads Using Java with others Wireless XML
 

Java was designed to have all of the best features of existing languages. However, Java has no concept of asynchronous behavior. This is the main reason the threading mechanism is so important and that concurrent programming techniques are evolving quickly to the point where known patterns, whose behaviors are well understood, will become an integral part of the common Java environment.

In the first part (JDJ, Vol. 2, Iss. 4) of our series, we discussed some basic patterns: Waiter and Early Reply Threads. Using inner classes, a sample Waiter pattern, called Operation, was implemented. In this article, I continue with an in-depth look at synchronization and its extensibility. The relationships between Inheritance and Synchronization will be studied in the context of the Inheritance Anomaly. A new model, called Active Object, will be introduced as a possible alternative in solving the inheritance anomaly.

Relationships between a Generic Object and a Thread Object
An object has a state, behavior and identity. What types of objects exist in the multithreaded environment? I like to classify objects from the point of view of their participation as:

  1. Passive Unaware Object: The object is a simple repository for data manipulated by its methods and designed without multithreaded concerns.
  2. Passive Aware Object: The object whose sensitive methods are synchronized.
  3. Runnable Object: The object whose willingness to participate in a multithreaded environment is marked by implementation of the Runnable interface.
  4. Threaded Object: The object is an instance of at least a Thread Class.
  5. Active Object: An object whose behavior is exhibited from its creation.

Imagine for a moment a virtual machine with as many processors as you want. Thus, every thread your program creates could find a place to live. Think of a thread as having only one purpose in its existence: to execute code, knowing that as soon as it cannot find something to devour, it dies. It is obvious that our objects are exposed to a ferocious fight - the fight for thread survival. How could an object maintain its integrity and where is the authority to establish an order in this chaos? An object protects its sensitive part using a simple lock mechanism implemented in Java with the form

synchronized (object) { //atomic code of object }

called synchronized block. There is a form of protection at the method level:

public synchronized void method() { ... }

Let us define the term "synchronized code": the part of the code (block/method) which is atomic with respect to an object, meaning that once a thread begins the execution of the code, no other thread can interrupt it. Think of an object lock as an access door for the thread to object code. While the object invites all interested threads, the object imposes a condition: only one at a time. When the thread finishes, the door is opened (the lock is released) and another thread may come in. The interval of time the door is locked is called scope of the lock (see Figure 1).

Figure 1
Figure 1:

Why do we need two synchronization levels: block and method? Sometimes the method scope is too large and holds a lock for a section of code which is not necessarily atomic. On the other hand, there is an overhead in grabbing and releasing the lock too many times during the execution of a method. The Java mechanism is very flexible, allowing us to choose whatever form is suitable in designing our objects.

What happens when a thread needs certain conditions to exist? What are the mechanisms for threads communication? The Java mechanism is simple. Besides having a lock, each object maintains a wait set', which is a set of threads waiting for the object to be in an appropriate state. In contrast with the lock mechanism implemented using synchronized keyword, the wait set' is implemented using method invocation. The methods are: wait(), notify() and notifyAll(). By invoking the wait() method on the object, the thread enters the wait set' and prior to waiting, the object lock is released. The mechanism has the form:

synchronized(this) {
while (!condition) {try { wait();}
catch(...) {}
}

When does a thread exit the blocked state and become released from the object wait set'? When one or the other of notify() or notifyAll() method is invoked. The object reacquires the lock prior to returning from wait() method.

synchronized(this) {
condition = true;
notify(); //notifyAll();
}

What method should be invoked: notify() or notifyAll()? When a single object is used as an implicit condition, as shown above, you need to use notifyAll() because a subclass may introduce a new condition and notify() may wake the thread for the alternative condition, obtaining what is called the lost notification. On the other hand, it is very inefficient to wake up all the threads.

One solution consists of grouping objects in containers, targeting a specific thread on a specific type of condition [3]. As you know, Java does not treat synchronization as part of the class contract with respect to inheritance. To override a method you must have knowledge of the semantics of the superclass method. A synchronized method could or could not be declared synchronized in the overridden method [4]. Are synchronized mechanisms strong enough to avoid an inheritance anomaly?

Inheritance Anomaly
First, let's define the meaning of inheritance anomaly. The term was introduced by S. Matsuoka [2] to describe the conflict between inheritance and concurrency in object-oriented languages. Basically, it says that in some circumstances the synchronized code cannot be effectively inherited without non-trivial class re-definition. There are two main reasons the phenomenon could occur: the insufficient language support and/or the poor class hierarchy design. The classical example to illustrate the inheritance anomaly is the Bounded Buffer. The base class has two synchronized methods, put() and get(), with obvious restrictions that putting to a full buffer or getting from an empty buffer must wait. The natural assumption, that a subclass tries to inherit and use as many parent methods as possible, is made. To emphasize the anomaly, three subclasses were defined. The first subclass extends the parent by adding a method, get2(), which removes the two oldest items from the buffer simultaneously. The second subclass adds a method called gget(), which is almost identical with get() except that it can only be accepted immediately after a get() method. Finally, the third subclass tries to implement the lock state. Many questions arise: Is there a real crisis in the concurrent object-oriented languages: inheritance and polymorphism cannot coexist with concurrency mechanism? Is Java at the semantic level powerful enough to provide a mechanism for solving the anomaly inheritance?

First of all, let us analyze how a class can be extended in Java. Could we isolate the sensitive inheritance constructs? Java allows a subclass to define new methods (N) to override methods of the superclass (O) and to use in the subclass methods the superclass public/protected methods (U). I would like to consider the triplet (N, O, U) and the values 0/1 to express the existence of the specific relationship between a superclass and its subclass. From the eight combinations, the cases (0,0,0), (0, 0, 1) are trivial and the subclass is semantically identical with its superclass. The situations depicted as (0,1,1) and (1,0,1) are more subtle with respect to synchronization constraints. If we consider the case (1,1,1) as being actually an extension of previous two, why do the cases (0, 1, 1) and (1, 0, 1) deserve special attention? Because the subclass implementing new methods or overriding methods uses the superclass methods at the same time with a synchronization mechanism that could not be suitable for the extensions of the subclass behavior.

As an exercise, let's try to apply one of Matsuoka's examples to Java. Listing 1 shows an abstract class definition called BoundedContainer. Depending on the type of structure we use to express a limited storage container, the store() and retrieve() methods are irrelevant to our discussion, being implementation details of the store/retrieve operations for that specific container (array, etc.). Let us extend our base class by adding an operation called gget(), with the only restriction that its invocation must immediately follow a get() invocation as required in Matsuoka's theory. The class ExtBoundedContainer (Listing 2) is a simple example to illustrate what is called the history state problem in the inheritance anomaly. The problem could be solved by defining in the subclass a variable that records the invocation of get() method. Thus, the sole purpose of overridden get() is to record its invocation, the actual operation of getting the object from the container being accomplished by calling super.get(). Would you recognize the sensitive case here? First the subclass uses the superclass get(), implements a new method gget() and overrides get() for implementing the required behavior. So the case in our analysis is of type (1, 1, 1).

Is there an error in our simple implementation? Consider an empty container with a get() and gget() waiting. If a put() is invoked and the gget() thread is woken, it goes back to waiting, because the last operation was not a get(), the notification being lost. There is even a worse scenario in which all threads using the buffer will be in a deadlock state if put() is called many times until the buffer is full. Would the impasse have arisen had we used notifyAll() instead of notify()? Of course not, but now in order to reuse code from our simple hierarchy we have to redefine methods of the base class. Is this a type of inheritance anomaly or just a poor class design? It is indeed a real problem, especially in big class hierarchies, no matter how you wish to classify it.

How could we avoid such an simpasse? First of all, trying to identify the sensitive cases with respect to synchronization constrains the case of type (0, 1, 1), ( 1, 0, 1), as explained in the above analysis. Second, regardless of optimization criteria, using the notifyAll() methods in base class as well is explained in [1]. In our attempt, we relied on Java support for the nested locks: Once a thread acquires the object lock, it can move freely through synchronized methods of the object. From this point of view, Java has all the mechanisms in place for helping us to solve the inheritance anomaly, except that access to superclass methods implementation is sometimes found only at documentation level when the source code is not available. This could lead to inheritance deficiencies, especially when the hierarchy has a poor architecture design, with synchronized code not well contained. Is there another approach, a new model that could avoid the inheritance anomaly? The answer might be found in studying a new type of model.

The Active Object Model
Until now, every object exposed its behavior only at the client's request through method invocation. How could we implement an object whose behavior is exhibited once the object is created, without any request from a client? It is obvious that the object must delegate its entire activity to a thread member and the thread must be started once the object is created. So the implementation of an active object should conform to the form:

class ActiveObject implements Runnable { private Thread activity;
public ActiveObject() {
activity = new Thread(this);
activity.start();
}
public void run() { ... }
}

Once the object is constructed, its run() method is executed without any exterior intervention. The run() method for such an object is the core of its existence and a private/protected access control modifier would be more suitable. On the other hand, run() must be public, being declared in the Runnable interface. How could we prevent a client from invoking the run() method directly? The answer is easy using the thread identification idiom:

public void run() {
if (activity == Thread.currentThread())
{ ... }
}

Thus, only the thread constructed by the active object, can execute the run() method implemented by the active object. If you define a subclass of ActiveObject class, the constructor of the subclass will invoke the constructor of superclass, which will create and start a new thread. The subclass thread will execute the run() method of its superclass unless you override the run() method, in which case the overridden run() method is executed. As you know, the C++ virtual mechanism governs the method invocation in Java. For instance, let Y be a class that extends class X and let f() be a non-private method of X overridden in Y. If x is an object obtained by a construct of the form: X x = new Y(), the invocation x.f() executes the method f() of class Y. How would the superclass thread use its run() method, when the subclass overrides it? You may have guessed the answer: We apply the thread identification idiom in the subclass. The overridden run() method would look like:

public void run ()
if (thread == Thread.currentThread()) {
//execute subclass activity
} else super.run();

Although defining an active object, as shown above, gives us total flexibility with regard to the execution of the run() methods, the question remains: Would an active object eliminate the inheritance anomaly? Trying to control the execution of synchronized code from within a centralized point is a step in the right direction. Are we missing something in our attempt to empower the active object with the total control? For instance, could our object schedule processing requests and replies in a self-contained way? It could, if we define the adequate notions and implement them correctly.

The state of the object should be the starting point. Let us abstract the state an object could be in, not only at the level of the values of the object's instance variable, but also at the level of execution of the object's threads. An abstract state for an object would be what an interface is for a class. The concrete state should be, in this case, a simple mapping from the abstract state to the value true/false. How could an object be self-aware of its state? If we define an inner object called object's manager, every activity of the active object will be supervised by it. In addition, every invocation would come only at the level of the object manager, who will change the concrete state of the active object accordingly. Figure 2 is a conceptual view of the active object model. What we obtain is a separation of the protocol from functionality in class definition as a way to overcome the inheritance anomaly. Modular design is achieved by restricting inheritance in a way that ensures that subclass refines superclass. Object consistency can thus be verified at an abstract level, ignoring unnecessary implementation details.

Figure 2
Figure 2:

Conclusion
I can already hear some readers arguing: "What you advocate here is a procedural design in object-oriented fashion!" You may remember what happened when structured programming was introduced many years ago! Many programmers believed that jumping freely through instructions using 'goto' statements was essential to the art of programming. If today's problems come from yesterday's solutions, the inheritance anomaly proves that the way we design our object today could lead to tomorrow's problem. Is the Active Object Model a viable alternative? I believe so, and the next part of our series will analyze how this new Architectural Design brings order into a chaos of uncontrolled object interaction.

References

  1. Doug Lea, "Concurrent Programming in Java Design Principles and Patterns", Addison-Wesley, 1997.
  2. Satoshi Matsuoka, "Synchronization Constraints With Inheritance", University of Tokyo, 1990.
  3. Scott Oaks, Henry Wong, "Java Threads", O'Reilly & Associates, Inc., 1997.
  4. J. Gosling, B. Joy, G. Steele, "The Java Language Specification", Addison-Wesley, 1996.
About the Author
Jordan Anastasiade holds a BS in Architecture and MS in Mathematics. He works for Hummingbird Communications Ltd., focusing on design patterns using object-oriented techniques in Java. Jordan can be reached at [email protected]

	

Listing 1

/** Interface for a Generic Container */
interface Container {
   public final static int SIZE = 100;
   public abstract void store(Object o);
   public abstract Object retrieve();
}

/** Base class defines: put and get methods */
public abstract class BoundedContainer 
                                implements Container {

   protected int currentSize = 0;
   /** put adds an object to container */
   public synchronized void put(Object o) {
      while (currentSize == SIZE) {
         try {
           wait();
         }
         catch (Exception e) { }
      }
      store(o);
      currentSize++;
      if (currentSize == 1)
         notify(); 
   }
   /** get removes an object from container */
   public synchronized Object get() {
      while (currentSize == 0) {
         try {
           wait();
         }
         catch (Exception e) { }
      }
      Object o = retrieve();
      currentSize--;
      if (currentSize == SIZE - 1)
         notify(); 
      return o;
   }
   /** isEmpty defines the state */
   public synchronized boolean isEmpty() {
      return (currentSize == 0); 
   }
}

Listing 2

/** Extended class adds a new method: gget */
public abstract class ExtBoundedContainer 
                        extends BoundedContainer {

   protected boolean lastGet = false;
   /** put records the use of get method
       and uses the superclass method */
   public synchronized void put(Object o) {
      super.put(o);
      lastGet = false;
   }
   /** get records its invocation 
       and uses the superclass method */
   public synchronized Object get() {
      Object o = super.get();
      lastGet = true;
      return o;
   }
   /** gget implements the fuctionality required 
         in Matsuoka's problem [2] */
   public synchronized Object gget() {
      while (currentSize == 0 || lastGet == false) {
         try {
           wait();
         }
         catch (Exception e) { }
      }
      return get();
   }
}


 

All Rights Reserved
Copyright ©  2004 SYS-CON Media, Inc.
  E-mail: [email protected]

Java and Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. SYS-CON Publications, Inc. is independent of Sun Microsystems, Inc.