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 thread synchronization primitives are based on object instances. Multithreaded access to a shared resource requires a unique object instance that all threads accessing the resource can synchronize upon.

This is especially challenging for resources that may have multiple views. For instance, multiple threads can independently open a given file and will have separate instances of the java.io.File object, each corresponding to the same file. The different object instances that correspond to multiple views of the same resources don't allow synchronized multithreaded access to these resources.

This article illustrates the problem and examines approaches to solving it with an emphasis on their synchronization and concurrency trade-offs. It presents a few use-case examples where this problem manifests itself, followed by a simple and elegant solution with the complete Java source code. Java programmers who work with remote resources, including file, URL, LDAP, JNDI, and relational databases, are likely to find this article helpful in recognizing areas of code that are vulnerable to suboptimal synchronization.

How Java Thread Synchronization Works
Each Java object has a "monitor" that can be used as a semaphore to synchronize multithreaded access to shared resources. Typical resources that are shared in a Java program include shared memory spaces such as tables, queues, and lists. Various Java classes such as java.util.Vector and java.util.Hashtable have most of their methods synchronized on the object instance. As you may already know, any Java object may be used as the semaphore for synchronizing multithreaded access to itself or other object(s), as long as each thread uses the same instance of the object to synchronize upon.

The Challenge with Multiview Resources
Shared system and network resources, such as files, database tables, network connections, URLs, and LDAP directory entries, are also represented by one or more Java objects, and often the same underlying resource is represented by more than one object. Each object that represents a resource presents a view of that resource. While it's sometimes possible and desirable to use a unique object instance that corresponds to a given underlying resource, in many cases it's either undesirable or impossible to do so. Figure 1 illustrates the synchronization and concurrency challenges posed by multiple views of a given resource.

Figure 1
Figure  1:

Consider an application that needs to write some data to one of several hundred files in a given file system. The file is selected based on the request parameters. Assume that a multithreaded request dispatcher handles each incoming request, parses the request to map it to a unique file in the file system, and then edits the file as per the request parameters. Given the possibility that multiple simultaneous requests can map to the same file, the application must ensure that access to a given file is synchronized across multiple threads.

The implementation in Listing 1 is clearly incorrect, since the synchronization is based on a local object instance. Two threads processing independent requests that return the same file name will create two separate java.io.File objects. Therefore no synchronization will be achieved. Making the entire method synchronized introduces more problems than it solves. First, it significantly reduces concurrency by synchronizing access across independent files. Second, it doesn't help if the request can be dispatched to one of many methods, each of which may need to access the requested file. Synchronizing every method that may need to access any file is clearly unacceptable, as it severely reduces concurrency.

First Cut at the Solution
Our first attempt at solving this problem is to make use of a shared table that keeps track of the files in use and returns the same instance of a File object to every request that corresponds to a given file. As a request is made for a file, the table is checked to see if a File object corresponding to the requested file already exists. If so, the existing File object is returned and the use count for the File object is incremented by one. Otherwise, a new File object is created for the file and added to the table with the use count set to one.

Once the requester is done with the file, it must explicitly call a method that decrements the use count by one and removes the File object from the shared table if the use count is reduced to zero. Listing 2 provides the modified code based on this solution. The method acquireFile(String) is used to request the object instance for a file and increment the use count; the method releaseFile (File) is used to decrement the use count and release the File object if it's no longer in use.

Critical Analysis
Note: The try-finally block becomes necessary to ensure that the file use count is decremented even if the method throws an undeclared throwable in the synchronized block. A missed finally block can cause undesirable side effects such as memory leaks, making this approach unattractive. This approach is also unacceptable if the File object is to maintain a state that is specific to each thread requesting access to the file. The limitation is easy to get around once we realize that there are two distinct requirements here:

  1. To obtain a reference to a File object corresponding to the requested filename
  2. To obtain a unique object to synchronize the file access on
In the solution in Listing 2 we returned the same object for both purposes, whereas we could just as well return a different object for synchronization.

Second Attempt at the Solution
We modify the solution (see Listing 3) to create a local instance of the File object and seek a unique object instance for synchronization purposes only. The method acquireSemaphore(File) checks if the given File instance is equal to any other File that exists in its tables. If so, it returns the unique object stored against the existing File entry and increments the use count. Otherwise, it stores the current File instance in its tables along with a new java.lang.Object instance created to act as the semaphore and sets the use count to one. The method releaseSemaphore(File) decrements the use count for the File that's equal to the given File, and clears the entry if the use count goes to zero. Using a java .util.Hashtable (or java.util.HashMap) makes the equality comparison easy and efficient as long as the hashCode returned is also the same for objects that are equal (though not necessarily the same instance).

A Few Use Cases
Before looking at further improvements to the solution developed thus far, let's discuss a couple more use cases so that we can arrive at a clear definition of the problem.

First, consider a directory-based application that uses LDAP or JNDI APIs to access the directory. For optimal concurrency it may be desirable to synchronize thread access at the level of a directory entry. A directory entry can be uniquely identified using a canonical string representation of its "DN" or distinguished name. Using the solution developed above, an application fragment may be written as illustrated in Listing 4 to allow for maximum concurrency while remaining thread-safe.

Next, we have a server application that caters to authenticated users and needs to limit access to certain resources to one concurrent request per user. The solution outlined in Listing 4 can be applied to all such resources by using the unique identity of the authenticated user to obtain a semaphore for synchronization.

Formal Definition of the Problem
As you may notice, for the acquireSemaphore method to work correctly in these examples, the argument must uniquely represent the shared resource and must also be equal to other argument instances that represent other views of the same resource. The problem can therefore be described as a requirement to synchronize across n objects that are not equal by reference, but are equal by value. In other words, these n objects are different views of the same resource.

To avoid confusion, in the following description I'll use the term equal to imply reference equality, and equivalent to imply equality by value. Thus equal objects are always equivalent, though not the other way round. Therefore, these n objects are equivalent but not equal to each other. Expressed in Java, it implies that the following is true for any given n objects obj[0] through obj[n-1] that we need to synchronize across:

obj[i] != obj[j]
// for all i != j, 0 <= i < n, 0 <= j < n
* obj[i].equals(obj[j])
* (obj[i].hashCode() ==
obj[j].hashCode())
// for all i, j, 0 <= i < n, 0 <= j < n

The solution is simple and elegant and is illustrated in its entirety in Listing 5. Listing 6 presents Listing 3, rewritten using the solution.

How Does the Solution Work?
Start with any object that satisfies the synchronization requirements listed above. Instead of synchronizing on the object itself, obtain a semaphore for the object using a single instance of the monitor that's accessible to all concerned packages. The monitor maintains weak references to all objects with semaphores in a hash map for faster lookup. The weak reference allows the objects to be garbage collected if there are no other strong references to the object, obviating the need for maintaining use counts using try-finally blocks.

When you request a semaphore for an object, the monitor looks for an object in its hash table that's equivalent to the given object (has the same hash code and satisfies the equals method). If an equivalent object is found, the same is returned. Otherwise, the given object is added to the hash table, wrapped in a weak reference so that the garbage collector automatically removes it when it's no longer in use.

This approach always keeps one element of every equivalence set in the hash table until no element in that equivalence set is in use, at which point it's eligible to be removed until the next time it's required. Therefore, it's best to obtain a semaphore for a lightweight object that's a simple canonical representation of the resource.

Unlike the example in Listing 2, the semaphore (which is really the first object in its equivalence set to look for a semaphore) is used only for synchronization, not for any other access, thereby allowing context-specific settings to be different among different objects in the same equivalence set. Wrapping the semaphore in a weak reference eliminates the need for maintaining use counts and makes the usage more natural. Figure 2 demonstrates the solution.

Figure 2
Figure  2:

The Nuts and Bolts
To conclude, let's take a closer look at the code in the monitor. The following statement in the monitor may also return a null in the case when ref is non-null.

Object monitor = ((ref == null) ? null : ((WeakReference)ref).get());

This is possible in the case of an unlikely race condition in which the object is cleared from the weak reference after the super.get(key) statement, at which point it may still be in the hash table. Checking for monitor == null again guards against a rare race condition. The get and put methods of the underlying HashMap (a WeakHashMap) are not synchronized; this is good since we don't expose them directly but through the single synchronized get method in the monitor. Synchronizing the get method of the monitor is essential, as it involves modification of a shared data structure.

While a single instance of the monitor may be functionally sufficient for the entire application, for higher concurrency a different instance of monitor should be used for independent modules or packages that require semaphores for objects of different classes. The monitor tremendously simplifies the writing of multithreaded code with just the right amount of synchronization - not more, not less.

Author Bio
Vishal Goenka is a senior software engineer for Campus Pipeline Inc., where his group is responsible for the infrastructure components of the Campus Pipeline Web Platform. He focuses on security architecture and implementation. Vishal holds a BS in computer science from the Indian Institute of Technology Kanpur (India). [email protected]

	


Listing 1

public void process (Request req) {
    File file = new File(req.getFileName());
    synchronized (file)  {
       // ... open/modify/close file as per the request parameters...
    }
}


Listing 2

public void process (Request req) {
    File file =  acquireFile( req.getFileName() );
    try {
       synchronized (file) {
          // ... open/modify/close file as per the request parameters...
       }
    }
    finally {
       releaseFile( file );
    }
}


Listing 3

public void process (Request req) {
    File file =  new File( req.getFileName() );
    Object semaphore = acquireSemaphore ( file );
    try {
       synchronized (semaphore) {
          // ... open/modify/close file as per the request parameters...
       }
    }
    finally {
       releaseSemaphore( file );
    }
}


Listing 4

public void methodA(LDAPObject obj) {
    String dn = obj.getDN();
    Object semaphore = acquireSemaphore ( dn );
    try {
       synchronized ( semaphore ) {
          // read/modify/delete object
       }
    }
    finally {
       releaseSemaphore ( dn );
    }
}


Listing 5

public class Monitor {
    private WeakHashMap map = new WeakHashMap() {
       public final Object get(Object key) {
          Object ref = super.get(key);
          Object monitor = ((ref == null) ? null : ((WeakReference)ref).get());
          if (monitor == null) {
             monitor = key;
             put (monitor, new WeakReference(monitor));
          }
          return monitor;
       }
    };
    public synchronized Object get(Object key) {
       return map.get(key);
    }
}


Listing 6

static final Monitor monitor = new Monitor();

public void process (Request req) {
    File file =  new File( req.getFileName() );
    synchronized (monitor.get(file)) {
          // ... open/modify/close file as per the request parameters...
    }
}

  
 

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.