While it is not too difficult to check if a thread already owns a lock before grabbing it, is it possible to prevent deadlock of any kind? Before we try to answer this question, let’s look further into just what deadlock is. Simplistically, deadlock is when two or more threads are waiting for two or more locks to be freed and the circumstances in the program are such that the locks will never be freed. We saw this occur earlier, when we made the getBusyFlag() method synchronized. The fact that the freeBusyFlag() method was also synchronized made it impossible for the busyflag to be freed until the getBusyFlag() method returned. Since the getBusyFlag() method was waiting for the busyflag to be freed, it would wait forever.

That deadlock was caused by an object lock grabbed by the Java synchronization primitive and our own implementation of a lock mechanism, the BusyFlag class. Can this deadlock situation also be caused only with Java’s synchronization primitives? The answer to this question is yes; furthermore, it may be difficult to predict deadlock or to detect deadlock when it occurs. Code that runs correctly every time during testing may contain potential deadlocks that occur only under certain conditions or on certain implementations of the Java virtual machine. To better illustrate this problem, let’s examine some possible methods that may exist in any database system:

public void removeUseless(Folder file) {
     synchronized (file) {
          if (file.isUseless()) {
               Cabinet directory = file.getCabinet();
               synchronized (directory) {
                    directory.remove(file);
               }
          }
     }
}

Suppose, in some database class, we have a method called removeUseless(). This method is called during the period when the program needs to clean up the database system. It is passed a folder object; this object represents some folder we have in our database system. There is some indication of uselessness that is calculated by the isUseless() method of the folder object. In order for us to act on the folder, we must make sure that we have the object lock of the folder. If we find that the folder is useless, we can simply remove the folder from the cabinet. The cabinet can be found by the getCabinet() method, and the folder can be deleted with the remove() method. Just as with the folder object, before we can act on the cabinet object, we must obtain its object lock. Now, let’s also suppose that we have another method, called updateFolders():

public void updateFolders(Cabinet dir) {
     synchronized (dir) {
          for (Folder f = dir.first(); f != null; f = dir.next(f)) {
               synchronized (f) {
                    f.update();
               }
          }
     }
}

This method is passed a cabinet object that represents a cabinet in our database system. In order for us to act on this cabinet, we must first obtain its object lock. Let’s suppose that the act of updating the cabinet is done by cycling through all the folders in the cabinet and calling the update() method on the folders. Again, in order for us to update the folders, we must also grab the folder lock.

None of these methods is extraordinary; they could exist in one form or another in any database system. However, let’s look at a possible run of this implementation as outlined in Figure 3.4. Assume the updateFolders() method is called from thread 1. The method locks the cabinet (L1). Now assume the removeUseless() method is called by thread 2. The removeUseless() method locks the folder (L2), determines that it is indeed useless, and proceeds to lock the cabinet (L1) in order to remove the folder. At this point, thread 2 blocks and waits until the cabinet object lock is freed.

Figure 3-4. Deadlock in a database system

But what happens if the folder on which the removeUseless() method is working is now accessed by the updateFolders() method? When the updateFolders() method reaches this folder, it tries to grab the object lock for the folder (L2). At this point, the removeUseless() method has the folder lock and is waiting for the cabinet lock to be freed; the updateFolders() method holds the cabinet lock and is waiting for the folder lock to be freed. This is the classic deadlock situation, and it illustrates the problem that deadlock can be easy to program and hard to detect: both methods involved use a simple, straightforward algorithm, and there are no obvious signs in the code that deadlock can occur. Consider this problem in the light of a large system, where the code may have been developed by two engineers with no knowledge of each other’s work; even the best program design would not guarantee deadlock prevention.

Can the system somehow resolve this deadlock, just as it was able to avoid the potential deadlock when a thread tries to grab the same lock again? Unfortunately, this problem is different. Unlike the case of the nested locks, where a single thread is trying to grab a single lock twice, this case involves two separate threads trying to grab two different locks. Since a thread owns one of the locks involved, it may have made changes that make it impossible for it to free the lock. To be able to fix this problem, we can either redesign the program so that it doesn’t run into this deadlock condition, or provide a way for this deadlock to be avoided programmatically. In either case, it involves some sort of redesign. Given the complexity of the original design, this may involve a major overhaul of the database system.

How could you expect the Java system to resolve this deadlock automatically when even the developer may not be able to do so without overhauling the design? The answer is that you can’t, and it doesn’t. We will look at the design issues related to deadlock prevention in Chapter 8.