By Chuck Mcmanis, JavaWorld |

Using threads with collections, Part 2

New design issues arise when making collections larger

Previous 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.

This story, "Using threads with collections, Part 2" was originally published by JavaWorld.

Next read this:

Previous 1 2 Page 2

Page 2 of 2