Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

JavaWorld.com

Programming Java threads in the real world, Part 6

The Observer pattern and mysteries of the AWTEventMulticaster

By Allen Holub, JavaWorld.com, 03/01/99

  • Print
  • Feedback

Page 6 of 6

Listing 7 (Synchronized_list_publisher.java): Locking on a synchronized LinkedList 


01  
02  
03  
04  
05  
06  
07  
08  
09  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  

import java.util.*;
import com.holub.tools.Subscriber;
public class Synchronized_list_publisher
{   Collection subscription_list
                   = Collections.synchronizedList( new LinkedList() );

   public void subscribe( Subscriber subscriber )
    {   subscription_list.add( subscriber );
    }
   public void cancel_subscription( Subscriber subscriber )
    {   subscription_list.remove( subscriber );
    }
   public void publish( )
    {   
        Object[] copy;       copy = subscription_list.toArray();
        for( int i = 0; i < copy.length; ++i )
            ((Subscriber) copy[i]).receive("Hello world");
    }
   public void publish_blocking( )
    {      synchronized( subscription_list )
        {
            for(Iterator i = subscription_list.iterator(); i.hasNext();)
                ((Subscriber) i.next()).receive("Hello world");       }
    }
}


Now let's address the problem of the amount of time required to do the notifications, and the fact that the thread that calls either publish() or publish_blocking() is effectively blocked until all the subscriber's receive() methods have been called. (Don't confuse locking with blocking. A thread can be blocked by attempting to enter a synchronized method that's in use by another thread. Acquiring a lock doesn't cause you to block unless there's contention. A thread is also effectively blocked -- in the sense that it can't do anything else -- while it's executing a lengthy method, whether or not that method is locked.)

The time problem is easily solved by wrapping threads around the publication code in Listing 7. I've done this in Listing 8. Now, the publish() method (Listing 8, line 16) creates a new Thread that notifies the subscribers. The complementary publish_sequentially() method (Listing 8, line 32) keeps the list locked while notifications are in progress, so if N threads publish simultaneously, you'll effectively go through the list N times, one after the other, instead of having N notification threads running in parallel.

Other, more complex solutions are also possible. It really isn't necessary for publish_sequentially() to create multiple threads when it's called while notifications are in progress. The publish_sequentially() method could just ignore any requests that come in while notifications are in progress, for example, or it could remember the fact that the request was made and run through the list a second time when it finished the first traversal.

Listing 8 (Background_publisher.java): Publishing from a thread 


01  
02  
03  
04  
05  
06  
07  
08  
09  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  

import java.util.*;
import com.holub.tools.Subscriber;
public class Background_publisher
{
    Collection subscription_list = Collections.synchronizedList( new LinkedList() );
   public void subscribe( Subscriber subscriber )
    {   subscription_list.add( subscriber );
    }
   public void cancel_subscription( Subscriber subscriber )
    {   subscription_list.remove( subscriber );
    }   
   public void publish()
    {       new Thread()
       {   public void run()
            {
                Object[] copy;
                synchronized( subscription_list )
                {   copy = subscription_list.toArray();
                }
                for( int i = 0; i < copy.length; ++i )
                    ((Subscriber)copy[i]).receive("Hello world");           }
        }.start();
    }
   public void publish_sequentially()
    {       new Thread()
        {   public void run()
            {
                synchronized( subscription_list )
                {   for(Iterator i = subscription_list.iterator(); i.hasNext();)
                        ((Subscriber) i.next()).receive("Hello world");
                }           }
        }.start();
    }
}


Mysteries of the AWTEventMulticaster

Though the various blocking-publication functions I've just presented do solve the notification-after-removal problem, they aren't a general solution to the notification problem since any threads that modify the subscriber list are effectively blocked until no notifications are in progress (which could be a long time). The notify-from-the-copy strategy is perfectly viable when this blocking is unacceptable. The only down side is the amount of time that it takes not only to lock the subscription_list but also to actually make the copy. Fortunately, Sun's John Rose and Amy Fowler came up with an elegant solution to the problem: the AWTEventMulticaster. The AWTEventMulticaster class implements all of the AWT/Swing listener interfaces, so you can literally pass an object of this class any message that can be sent to any listener.

Figure 1 shows how an AWTEventMulticaster is used to construct a list of listeners. A static factory_method (add()) is used to create individual multicaster instances -- you can't create them with new. As you can see in Figure 1, this factory method is passed the current head-of-list reference and the listener to add. If either of these is null, it just returns the other, effectively creating a one-element list. If neither argument is null, then an AWTEventMulticaster object, essentially a binary-tree node, is created and initialized so that one child points to the existing list and the other points to the newly added listener. It continues in this way, building a binary tree whose interior nodes are all AWTEventMulticasters and whose leaf notes are standard AWT or Swing listener objects.



Figure 1. Building a subscription list with a multicaster



Notification is done with a simple, recursive tree-traversal. (Which can be a problem. You'll note in Figure 1 that the tree will most likely degrade into a linked list, and recursive traversal of a linked list can use up a lot of runtime stack.) As I mentioned earlier, the AWTEventMulticaster implements all of the standard listener interfaces (actionPerformed(), mouseClicked(), and so on). The multicaster overrides do nothing but pass the message to their children, using instanceof in the case of the leaf nodes to ensure that the message can be received by the actual object.

Immutable objects and blank finals
The most important feature of the AWTEventMulticaster is not actually evident in the diagram. The multicaster is an immutable object: all of its fields are declared static final, but are initialized in the constructor rather than the declaration; like this:



Since everything's final, the object's state can't change once it's created. A Java String is immutable, for example. Immutable objects have a significant advantage over normal objects in multithreaded environments: you never have to synchronize access to them, because they can't change state. Consequently, replacing the Collection in the earlier listings with a multicaster eliminates the synchronization overhead entirely.

A final field that is initialized in the constructor rather than the declaration is called a blank final. You should use them whenever you can, which is unfortunately not as often as you'd like. An oft-reported bug that's been around since the early beta versions of the JDK 1.1 compiler is still there in the Java 2 compiler: The compiler sometimes incorrectly spits out the hard-error "Blank final may not have been initialized," even when the field in question has been initialized. This bug tends to manifest only when you use a lot of inner classes. Because I don't want to corrupt the global or package-level name space with class names that the user could care less about, I usually prefer removing the final to moving the inner class out to the global level.

Using the multicaster
The multicaster exhibits a lot of very desirable behavior. For example, you can safely add listeners to the list while traversals are in progress because the tree is constructed from the bottom up. The new listeners will not be notified by any of the in-progress notification threads, but adding a listener will not damage the list either.

Listener removal elicits the following question: How do you remove nodes from a tree whose nodes can't be modified? The flip answer is that you build another tree. Figure 2 shows the easy scenario. To effectively delete node C, you create a new root node and make its child pointers reference node D and node C's right subtree. If you overwrite subscribers with new_list -- the normal case -- there will be no more references to the gray-colored nodes, and they will eventually be garbage collected.



Figure 2. Deleting a node from a multicaster: the easy case



Figure 3 shows the more difficult process of deleting a node that's further down in the tree (C again). Here, you have to build a second tree that looks exactly like that part of the original tree that's above the deleted node. As before, the gray colored nodes are subject to garbage collection once subscribers is overwritten (and any traversals positioned in that part of the tree complete).



Figure 3. Deleting a node from a multicaster: the hard case



The first time I looked at the AWTEventMulticaster source, I thought the code was weird and unnecessarily complex. On reflection, though, I realized that there's a lot of neat stuff here. The more I looked at it, the more I liked it. Multiple threads can happily add and remove nodes without conflicting either with each other or with threads that are traversing the tree, and multiple threads can traverse the tree simultaneously. Moreover, absolutely no synchronization is required to do any of this. The data structure that's used is no larger than the doubly linked list that I used earlier, and the overhead of copying part of the tree when you do deletions is a lot less than the overhead of copying the entire subscriber list every time you publish an event.

So, not being one to look a gift algorithm in the mouth, I wrote up my own general-purpose version of the multicaster, based on the AWTEventMulticaster. It's in Listing 9. It's remarkable how little code there is here. (Ahh, the miracle of recursion!) All the complexity, in fact, is in the removal. (I'll leave it as an exercise to the reader to puzzle through how it works -- opacity is the down side of most recursive algorithms.) This implementation is very general purpose in that it can publish any Object to any class that implements the generic Subscriber interface (from Listing 2).

Listing 9 (/src/com/holub/tools/Multicaster.java): A roll-your-own multicaster 


001  
002  
003  
004  
005  

package com.holub.tools;
import java.util.EventObject;
import com.holub.tools.Subscriber;

/**
  |      The multicaster (modeled after the AWTEventMulticaster) provides an efficient way to manage relatively-short lists of subscribers. Each Multicaster object can reference two Subscriber objects, one or both of which can be another multicaster. The top-level multicaster is passed a publish message, which it broadcasts (recursively) to both of the subscribers that it references.

The multicaster is an immutable object, so you can't modify it. The add() method, for example, is passed two multicasters and returns a third one that effectively references all the subscribers referenced by the original two. Any notifications that are in progress when the add() is executed will not be affected by the operation, however. It's perfectly acceptable for notifications to be performed on one thread while a second thread is adding or removing members from the Multicaster. The order in which Subscribers are notified is undefined. (It is not necessarily the order of insertion.)
@see java.awt.AWTEventMulticaster
@see Subscriber

 
 */

006  
007  
008  
009  
010  
011  
012  
013  
014  
015  

    /******************************************************************
      |      Ask the subscribers of this multicaster to receive the publication. This is the publish operation, as seen from the perspective of a subscriber. Remember, a multicaster is a list of subscribers. Note that the order of traversal should generally be considered undefined. However, if you really need to notify listeners in a known order, and you consistently add nodes as follows: 
subscription_list = Multicaster.add( subscription_list, new_node );
(Where subscription_list is the head-of-list reference and new_node is the node you're adding), subscribers will be notified in the order they were added. Removing nodes does not affect the order of notification. If you transpose the two arguments in the foregoing code: 
subscription_list = Multicaster.add( new_node, subscription_list );
subscribers will be notified in reverse order. 
     */

016  
017  
018  
019  
020  
021  

  public void receive( Object publication )
    {   a.receive( publication );
        b.receive( publication );
    }

    /******************************************************************
      |      Add a new subscriber to the list. The way that this call is used can impact the order in which subscribers are notified. (See receive().)
@param a Typically the head-of-list pointer.
@param b Typically the Subscriber you're adding to the list. 
     */

022  
023  
024  
025  
026  

  public static Subscriber add(Subscriber a, Subscriber b)
    {   return  (a == null)  ? b :
                (b == null)  ? a : new Multicaster(a, b);
    }

    /******************************************************************
      |      Remove the indicated subscriber from the list 
     */

027  
028  
029  
030  
031  
032  
033  
034  
035  
036  
037  
038  
039  
040  
041  
042  
043  
044  
045  
046  
047  
048  
049  
050  
051  
052  
053  
054  
055  
056  
057  
058  
059  
060  
061  
062  
063  
064  
065  
066  
067  
068  
069  
070  
071  
072  
073  
074  
075  
076  
077  
078  
079  
080  
081  
082  
083  
084  
085  
086  
087  
088  
089  
090  
091  
092  
093  
094  
095  
096  
097  
098  
099  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  

public static Subscriber remove(Subscriber list, Subscriber remove_me)
    {
        if( list == remove_me || list == null  )
            return null;
        else if( !(list instanceof Multicaster) )
            return list;
        else
            return ((Multicaster)list).remove( remove_me );
    }
    private Subscriber remove(Subscriber remove_me)
    {
        if (remove_me == a)  return b;
        if (remove_me == b)  return a;
        Subscriber a2 = remove( a, remove_me );
        Subscriber b2 = remove( b, remove_me );
        return (a2 == a && b2 == b ) // it's not here
                ? this
                : add(a2, b2)
                ;
    }
    //================================================================
   public static class Test
   {   private static class Leaf implements Subscriber
        {   String s;
           public Leaf(String s){ this.s = s; }
           public void receive( Object publication )   
            {   System.out.print(s);
            }
        }
       public static void main( String[] args )
        {   Leaf a = new Leaf("A");
            Leaf b = new Leaf("B");
            Leaf c = new Leaf("C");
            Leaf d = new Leaf("D");
            Leaf e = new Leaf("E");
            Subscriber subscription_list = null;
            subscription_list = Multicaster.add( subscription_list, a );
            subscription_list = Multicaster.add( subscription_list, b );
            subscription_list = Multicaster.add( subscription_list, c );
            subscription_list = Multicaster.add( subscription_list, d );
            subscription_list = Multicaster.add( subscription_list, e );
            System.out.print("List is: ");
            subscription_list.receive( null );
            System.out.print("\nRemoving c: ");
            subscription_list = Multicaster.remove( subscription_list, c );
            subscription_list.receive( null );
            System.out.print("\nRemoving a: ");
            subscription_list = Multicaster.remove( subscription_list, a );
            subscription_list.receive( null );
            System.out.print("\nRemoving d: ");
            subscription_list = Multicaster.remove( subscription_list, d );
            subscription_list.receive( null );
            System.out.print("\nRemoving b: ");
            subscription_list = Multicaster.remove( subscription_list, b );
            subscription_list.receive( null );
            System.out.print("\nRemoving e: ");
            subscription_list = Multicaster.remove( subscription_list, e );
            if( subscription_list != null )
                System.out.println("Couldn't remove last node");
            subscription_list = Multicaster.add( a, subscription_list );
            subscription_list = Multicaster.add( b, subscription_list );
            subscription_list = Multicaster.add( c, subscription_list );
            subscription_list = Multicaster.add( d, subscription_list );
            subscription_list = Multicaster.add( e, subscription_list );
            System.out.print("\nShould be: EDCBA: " );
            subscription_list.receive( null );
            System.out.println();
        }
    }
}


The final task, is to modify our publisher to use the multicaster. I've done that in Listing 10 (for this month's final entry in the worlds-most-complicated-way-to-print-"hello world" contest). This version is built on the one-thread-per-publication model discussed earlier.

Listing 10 (Multicast_publisher.java): Using the multicaster in a publisher 


01  
02  
03  
04  
05  
06  
07  
08  
09  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  

import java.util.*;
import com.holub.tools.Subscriber;
import com.holub.tools.Multicaster;
public class Multicast_publisher
{
    Subscriber subscription_list; // = null
   public void subscribe( Subscriber subscriber )
    {   subscription_list =
                        Multicaster.add( subscription_list, subscriber);
    }
   public void cancel_subscription( Subscriber subscriber )
    {   subscription_list =
                    Multicaster.remove( subscription_list, subscriber );
    }
   public void publish()
    {   
        new Thread()
       {   public void run()
            {   if( subscription_list != null ) 
                    subscription_list.receive( "Hello world" );
            }
        }.start();
    }
   public void publish_sequentially()
    {
        new Thread()
        {   public void run()
            {   synchronized( subscription_list )
                {   if( subscription_list != null ) 
                        subscription_list.receive( "Hello world" );
                }
            }
        }.start();
    }
    //==================================================================
   public static class Test
    {   
       static private Multicast_publisher publisher  =
                                                new Multicast_publisher();
       static private Subscriber subscriber = 
                                new Subscriber()
                               {   public void receive(Object p)
                                    {   System.out.println( (String) p );
                                    }
                                };
       static public void main( String[] args )
        {   publisher.subscribe( subscriber );
            publisher.publish();            // Publish "Hello world" events
        }
    }
}


Wrapping up

So that's it for this month. The Observer pattern is enormously useful when you need to write code that can be used in any context. Since the publisher knows nothing about the subscribers (except that they implement the Subscriber interface), the publisher is truly reusable in the technical OO sense. AWT/Swing obviously leverages Observer in its event model, but I use this design pattern heavily in non-UI situations as well.

Next month I'll present the last of the class-related solutions to multithreading problems: a reader-writer lock that lets you control access to a shared global resource. I'll also discuss Critical Sections and Singletons. Subsequent columns will look at a few architectural solutions to threading problems such as Synchronous Dispatchers and Active Objects.

  • Print
  • Feedback

Resources