Using threads with collections, Part 2

New design issues arise when making collections larger

1 2 Page 2
Page 2 of 2

Changing the SynchroList class

Functionally, there are two changes to the SynchroList class. The first change is to maintain a set of bits that are associated with the LinkEnumerator objects that have been created by invoking the elements method. The second is to update the before, add, and remove methods to note when the Link object that will be modified by the method is currently part of an enumeration.

The first change is trivial and consists of adding a private variable named players of type ChuckBitSet to the class to note which player IDs are in use. The second is a private method newPlayerID that is used to return the next available ID. In this design the ID is the index of a bit in the players bit set. The code is shown below.

/* return a new player ID from the list */
private int newPlayerID() {
    int i = 0;
    while (players.get(i)) i++;
    players.set(i);
    return i;
}

As you can see the code above uses a very simple linear search from zero to find the next index. This works well for a small number of threads but should be revisited if more than a few dozen threads are to be accessing a list at the same time. The newPlayerID method does not need to be synchronized as it is only called from within the LinkEnumerator constructors which are called in the synchronized elements methods of SynchroList.

The changes to the linked list manipulation methods before, after, and remove are slightly more complicated but not terribly so. Consider the code below. This is the original before method, which inserts a new Link object into the link list.

private void before(Object o, Link p) {
    new Link(o, p.prev(), p);
}

To update this method, the class needs to ascertain whether or not the Link object identified by p is currently part of an enumeration. The updated code is as follows:

private void before(Object o, Link p) {
    synchronized (p) {
        while (p.inPlay()) {
            try { p.wait(); }
            catch (InterruptedException e) { break; }
        }
        new Link(o, p.prev(), p);
    }
}

The method above is now synchronized using the object p. This ensures that if the thread does block, it will be notified as soon as p is released. The loop while (p.inplay()) { ... } guards against multiple threads manipulating the object at once. When a Link object's release method is invoked, all threads waiting on it are notified. As the link in question may be participating in several enumerations, however, the waiting thread must hang on until inPlay returns false before manipulating the object's link references. The after and remove methods are changed in exactly the same way, synchronizing on their object first before changing the structure of the linked list on which the object appears. The complete source for this version of the SynchroList is also available in the Resources section below.

Reviewing the path

Now, with the SynchroList class and its inner classes modified, the external interface to clients has remained the same. However, the class is now able to support multiple threads concurrently enumerating various portions of the linked list that the class maintains. Further, the class supports multiple threads updating the list without interfering with other thread readers, as long as the element to be updated is not currently being used by a different reader thread. I have not been able to eliminate the synchronization cost associated with creating the enumerations. I don't believe it's possible with the current JVM technology. There is, however, a large boost in efficiency over the original Java collections.

Conclusion

With the previous column and this one, I've explored some of the issues that arise when classes that implement collections of objects are used in multithreaded applications. It is important to note that techniques that make a class threadsafe, such as synchronized methods, can have adverse effects on performance when the classes are used in larger applications. These two columns have walked through the problem of multithreaded collections from conception, to prototype. These techniques are applicable to a wide variety of design problems involving threads.

Chuck McManis currently is a distinguished engineer at FreeGate Corp., a venture-funded start-up that is exploring opportunities in the Internet marketplace. Before joining FreeGate, Chuck was a member of the Java Group. He joined the Java Group just after the formation of FirstPerson Inc. and was a member of the portable OS group (the group responsible for the OS portion of Java). Later, when FirstPerson was dissolved, he stayed with the group through the development of the alpha and beta versions of the Java platform. He created the first "all Java" home page on the Internet when he did the programming for the Java version of the Sun home page in May 1995. He also developed a cryptographic library for Java and versions of the Java class loader that could screen classes based on digital signatures. Before joining FirstPerson, Chuck worked in the operating systems area of SunSoft, developing networking applications, where he did the initial design of NIS+. Check out his home page.

Learn more about this topic

  • Comparator interface http://www.javaworld.com/jw-06-1998/indepth/Comparator.java
  • The example comparator for integers http://www.javaworld.com/jw-06-1998/indepth/IntCompare.java
  • The test program for the SynchroList class http://www.javaworld.com/jw-06-1998/indepth/SynchroTest.java
  • Subsetted version http://www.javaworld.com/jw-06-1998/indepth/SynchroList.java
  • Subsetted and threaded version with some methods to support the applet http://www.javaworld.com/jw-06-1998/indepth/SynchroList.java
  • Applet base class http://www.javaworld.com/jw-06-1998/indepth/Synchro.java
  • Helper class for the applet http://www.javaworld.com/jw-06-1998/indepth/State.java
  • Here are the sources, in ZIP format, for collections that support subsets http://www.javaworld.com/jw-06-1998/indepth/indepth1.java
  • Here are the sources in ZIP format, for adding threads to the picture http://www.javaworld.com/jw-06-1998/indepth/indepth2.java
  • "Using threads with collections, Part 1"
    Threads add a new degree of complexity to otherwise straightforward design issues. http://www.javaworld.com/javaworld/jw-03-1998/jw-03-indepth.html
  • "An in-depth look at Java's character type"
    Eight (bits) is not enough -- Java's character type adds another eight. http://www.javaworld.com/javaworld/jw-01-1998/jw-01-indepth.html
  • "A first look at Borland's JBuilder IDE" http://www.javaworld.com/jw-11-1997/jw-11-indepth.html
  • "A look at inner classes"
    Reduce class clutter in your Java designsUse inner classes. http://www.javaworld.com/javaworld/jw-10-1997/jw-10-indepth.html
  • "Take an in-depth look at the Java Reflection API"
    Learn about the new Java 1.1 tools for finding out information about classes. http://www.javaworld.com/javaworld/jw-09-1997/jw-09-indepth.html
  • "Take a look inside Java classes"
    Learn to deduce properties of a Java class from inside a Java program. http://www.javaworld.com/javaworld/jw-08-1997/jw-08-indepth.html
  • "Build an interpreter in Java -- Implement the execution engine"
    Here's how to take the interpreter classes and run with them. http://www.javaworld.com/javaworld/jw-07-1997/jw-07-indepth.html
  • "How to build an interpreter in Java, Part 2The structure"
    The trick to assembling the foundation classes for a simple interpreter. http://www.javaworld.com/javaworld/jw-06-1997/jw-06-indepth.html
  • "How to build an interpreter in Java, Part 1The BASICs"
    For complex applications requiring a scripting language, Java can be used to implement the interpreter, adding scripting abilities to any Java app. http://www.javaworld.com/javaworld/jw-05-1997/jw-05-indepth.html
  • "Lexical analysis, Part 2Build an application"
    How to use the StreamTokenizer object to implement an interactive calculator. http://www.javaworld.com/javaworld/jw-02-1997/jw-02-indepth.html
  • "Lexical analysis and JavaPart 1"
    Learn how to convert human-readable text into machine-readable data using the StringTokenizer and StreamTokenizer classes. http://www.javaworld.com/javaworld/jw-01-1997/jw-01-indepth.html
  • "Code reuse and object-oriented systems"
    Use a helper class to enforce dynamic behavior. http://www.javaworld.com/javaworld/jw-12-1996/jw-12-indepth.html
  • "Container support for objects in Java 1.0.2"
    Organizing objects is easy when you put them into containers. This article walks you through the design and implementation of a container. http://www.javaworld.com/javaworld/jw-11-1996/jw-11-indepth.html
  • "The basics of Java class loaders"
    The fundamentals of this key component of the Java architecture. http://www.javaworld.com/javaworld/jw-10-1996/jw-10-indepth.html
  • "Not using garbage collection"
    Minimize heap thrashing in your Java programs. http://www.javaworld.com/javaworld/jw-09-1996/jw-09-indepth.html
  • "Threads and applets and visual controls"
    This final part of the series explores reading multiple data channels. http://www.javaworld.com/javaworld/jw-07-1996/jw-07-mcmanis.html
  • "Using communication channels in applets, Part 3"
    Develop Visual Basic-style techniques to applet design -- and convert temperatures in the process. http://www.javaworld.com/javaworld/jw-06-1996/jw-06-mcmanis.html
  • "Synchronizing threads in Java, Part 2"
    Learn how to write a data channel class, and then create a simple example application that illustrates a real-world implementation of the class. http://www.javaworld.com/javaworld/jw-05-1996/jw-05-mcmanis.html
  • "Synchronizing threads in Java"
    Former Java team developer Chuck McManis walks you through a simple example illustrating how to synchronize threads to assure reliable and predictable applet behavior. http://www.javaworld.com/javaworld/jw-04-1996/jw-04-synch.html

1 2 Page 2
Page 2 of 2