Skip to main content

Java Tech: The ABCs of Synchronization, Part 1

August 2, 2004

{cs.r.title}










Contents
Monitors and Locks
   Synchronized Methods and Synchronized Statements
Deadlock
Conclusion
Answers
to Previous Homework

Threads may execute in a manner where their paths of execution are completely
independent of each other. Neither thread depends upon the other for
assistance. For example, one thread might execute a print job, while a second
thread repaints a window. And then there are threads that require
synchronization, the act of serializing access to critical sections of
code, at various moments during their executions. For example, say that two threads
need to send data packets over a single network connection. Each thread must
be able to send its entire data packet before the other thread starts sending
its data packet; otherwise, the data is scrambled. This scenario requires each
thread to synchronize its access to the code that does the actual data-packet
sending.

Correctly synchronizing threads is one of the more challenging thread-related
skills for Java developers to master. This article begins a two-part series
that attempts to meet that challenge by exploring the fundamentals of Java's
synchronization capabilities. It begins by introducing you to the concepts of
monitors and locks. You next will learn how synchronized methods and synchronized
statements implement those concepts at the language level. Finally, you will learn
about deadlock, a nasty problem that often occurs when synchronizing threads.

Note: This series assumes that you have a basic understanding of threads and
the java.lang.Thread class, such as how to start a thread. Also,
keep in mind that the idea of multiple threads simultaneously executing code
has slightly different meanings on uniprocessor and multiprocessor machines.
On a uniprocessor machine, threads don't actually run at the same time. The
thread scheduler gives the illusion that this is the case. In contrast, where
enough processors exist to run all eligible threads, a multiprocessor machine
is capable of actually running threads simultaneously.

Monitors and Locks

Sun's Java virtual machine specification states that synchronization is based
on monitors. This point is reinforced at the Java VM level by the presence of
monitorenter and monitorexit instructions.

First suggested by E. W. Dijkstra in 1971, conceptualized by P. Brinch Hansen
in 1972-1973, and refined by C. A. R. Hoare in 1974, a monitor is a
concurrency construct that encapsulates data and functionality for allocating
and releasing shared resources (such as network connections, memory buffers,
printers, and so on). To accomplish resource allocation or release, a thread
calls a monitor entry (a special function or procedure that serves as
an entry point into a monitor). If there is no other thread executing code
within the monitor, the calling thread is allowed to enter the monitor and
execute the monitor entry's code. But if a thread is already inside of the
monitor, the monitor makes the calling thread wait outside of the monitor until
the other thread leaves the monitor. The monitor then allows the waiting
thread to enter. Because synchronization is guaranteed, problems such as data
being lost or scrambled are avoided. To learn more about monitors,
study Hoare's landmark paper,
""Monitors: An Operating System Structuring Concept,"
first published by the Communications of the Association for Computing
Machinery Inc. in 1974.

The Java virtual machine specification goes on to state that monitor behavior
can be explained in terms of locks. Think of a lock as a token that a
thread must acquire before a monitor allows that thread to execute inside of a
monitor entry. That token is automatically released when the thread exits the
monitor, to give another thread an opportunity to get the token and enter the monitor.

Java associates locks with objects: each object is assigned its own lock, and
each lock is assigned to one object. A thread acquires an object's lock prior
to entering the lock-controlled monitor entry, which Java represents at the
source code level as either a synchronized method or a synchronized statement.

Note: Java 1.5 introduces the java.util.concurrent.locks package.
This package includes a Lock interface for implementing locking
operations that are more extensive than those offered by synchronized methods
and synchronized statements.

Synchronized Methods and Synchronized Statements

A synchronized method is a method that serves as a monitor entry. That
method's signature is prefixed with keyword synchronized and the
entire method's code is a critical section (a section of code that can
be executed by only one thread at a time, to prevent data loss or corruption).
The code fragment below presents a class with two instance-based synchronized
methods and one class-based synchronized method:

public class SyncMethods
{
   public synchronized void instanceMethod1 ()
   {
      // Appropriate method-related code.
   }

   public synchronized void instanceMethod2 ()
   {
      // Appropriate method-related code.
   }

   public static synchronized void classMethod ()
   {
      // Appropriate method-related code.
   }
}

A SyncMethods object reference is needed to invoke either of the
two synchronized instance methods. For example:

SyncMethods sm = new SyncMethods ();
sm.instanceMethod1 ();

The thread that executes sm.instanceMethod1() needs to acquire the
lock associated with the SyncMethods object that sm
references before it can enter that monitor entry. If some other thread has
that lock, because it is executing code inside of instanceMethod1()
or inside of instanceMethod2(), the invoking thread is made to wait
until the other thread leaves its instance method.

Because the static classMethod() does not require an object reference prior
to its invocation, which lock does a thread acquire before it can enter that
method? The answer is simple. When a classloader loads a class, the
classloader creates a java.lang.Class object that describes the
loaded class. A thread acquires the lock from that Class object.
For example, in SyncMethods.classMethod ();, the thread acquires
the lock from the SyncMethods Class object.

The lock assigned to a SyncMethods object and the lock assigned
to the SyncMethods Class object are two different
locks. As a result, one thread may execute inside of either instance method,
while a second thread simultaneously executes inside of the class method.

In contrast to the synchronized method, a synchronized statement is a
monitor entry with a (usually) smaller critical section. The statement begins
with the keyword synchronized, continues with an object identifier
placed between a pair of round bracket characters, and concludes with a block
of statements that serves as a critical section. The following code fragment
illustrates the synchronized statement:

public class SyncStatements
{
   public void instanceMethod1 ()
   {
      // Setup code.

      synchronized (this)
      {
         // Update file.
      }

      // Cleanup code.
   }

   public void instanceMethod2 ()
   {
      // Setup code.

      synchronized (this)
      {
         // Read from file.
      }

      // Cleanup code.
   }
}

Let's assume instanceMethod1() is invoked by a thread that must
periodically update a file and instanceMethod2() is invoked by a
different thread whenever it needs to read from that file. In addition to the
actual file I/O code, each method contains extensive setup and cleanup code,
which we'll assume is completely independent of the other method's setup and
cleanup code. Assume also that there are no interdependencies.

Because the setup and cleanup code is independent, the simultaneous execution
of both methods' setup codes or both methods' cleanup codes does not cause
data corruption, and synchronization isn't required. Since at least part of
each method doesn't need to be synchronized, there is no point in
synchronizing the entire method. But threads cannot simultaneously update a
file and read from that same file. Therefore, each method's appropriate file
I/O code is placed within a synchronized statement. When one thread tries to
invoke instanceMethod1()'s update file code, it must first
acquire the lock that associates with the current object (that keyword
this signifies). Similarly, when the other thread tries invoking
instanceMethod2()'s read file code, that thread must acquire the
same lock. Only one thread will succeed (if both threads simultaneously try
acquiring the lock) and the file will be updated or read from, depending on
which thread obtains the lock.

Sometimes, it is convenient to use both synchronized methods and synchronized
statements in the same code. For example, consider a (not necessarily
graphical) component's event registration and listener notification logic, as
presented by the following code fragment:

// This code fragment has been shortened for
// clarity.

Vector clients = new Vector ();

public synchronized void addClientsListener
                         (ClientsListener cl)
{
   clients.add (cl);
}

public synchronized void removeClientsListener
                         (ClientsListener cl)
{
   clients.remove (cl);
}

private void notifyClients ()
{
   // ... Preamble.

   Vector copy;

   synchronized (this)
   {
      copy = (Vector) clients.clone ();
   }

   for (int i = 0; i < copy.size (); i++)
        // Retrieve listener object from copy
        // Vector at index i and fire an event
        // object to that listener, by invoking
        // a specific listener method with the
        // event object as an argument to that
        // method.
}

The code fragment above presents a clients data structure, two
synchronized methods for registering and de-registering listener objects (via
that data structure), and a private method that incorporates a synchronized
statement to assist in notifying those listeners when something interesting
happens. Both synchronized methods and the synchronized statement obtain the
same lock from the current (this) object. The result: only one
thread may execute, at any moment in time, inside of one of the three critical
sections.

Why is a synchronized statement used to make a copy of the data structure? To
understand the need for that statement, assume the thread that invokes either
of the synchronized methods, to register or de-register a client's interest in
receiving event notifications, is separate from the thread that invokes
notifyClients(). This is often the case in practice. Also,
assume that notifyClients()'s synchronized statement was not
present and that its for loop worked with clients directly. In that situation,
suppose a listener's thread removes the listener from the clients
data structure, while the for loop is iterating. At that point, the number of
objects in the Vector is less than the number of iterations that
the for loop must complete (based on initially evaluating expression
i < clients.size ()). The result: a runtime exception (caused by
an illegal array index) is thrown.







Deadlock

Large multithreaded programs that involve synchronization can be challenging
to write. In addition to making certain that threads don't acquire different
locks before entering the same critical section, or related critical sections,
the developer must guard against deadlock, a situation where locks are
acquired by multiple threads, neither thread holds its own lock but holds the
lock needed by some other thread, and neither thread can enter and later exit
its critical section to release its held lock because some other thread holds
the lock to that critical section. The following code fragment demonstrates
this pathological scenario for two threads:

public class Deadlock
{
   private Object lock1 = new Object ();
   private Object lock2 = new Object ();

   public void instanceMethod1 ()
   {
      synchronized (lock1)
      {
         synchronized (lock2)
         {
            // critical section guarded first by
            // lock1 and then by lock2
         }
      }
   }

   public void instanceMethod2 ()
   {
      synchronized (lock2)
      {
         synchronized (lock1)
         {
            // critical section guarded first by
            // lock2 and then by lock1
         }
      }
   }
}

Let's assume that thread A invokes instanceMethod1() at different
times and thread B invokes instanceMethod2() in the same random
fashion. Consider the following execution sequence:

  1. Thread A invokes instanceMethod1(), obtains the lock assigned to
    the lock1-referenced object, and enters its outer critical
    section (but has not yet acquired the lock assigned to the lock2-
    referenced object).

  2. Thread B invokes instanceMethod2(), obtains the lock assigned to
    the lock2-referenced object, and enters its outer critical
    section (but has not yet acquired the lock assigned to the lock1-
    referenced object).

  3. Thread A attempts to acquire the lock associated with lock2. The
    monitor forces that thread to wait outside of the inner critical section because
    thread B holds that lock.

  4. Thread B attempts to acquire the lock associated with lock1. The
    monitor forces that thread to wait outside of the inner critical section because
    thread A holds that lock.

  5. Neither thread can proceed because the other thread holds the needed lock. We
    have a deadlock situation and the program (at least in the context of the two
    threads) freezes up.

Although the previous code fragment clearly identifies a deadlock state, it's
often not that easy to detect deadlock. For example, your code may contain a
circular relationship among various classes (in several source files), where
class A's synchronized method invokes class B's synchronized method, which
invokes class C's synchronized method, and so on. Eventually, class Z's
synchronized method calls class A's synchronized method. If thread A invokes
class A's synchronized method and, while thread A is still inside of that method,
thread B invokes class Z's synchronized method, thread B will block when it
attempts to invoke class A's synchronized method. Thread A will continue to
execute until it invokes class Z's synchronized method, and then block.
Deadlock results. This scenario also happens with synchronized statements or
a collection of synchronized methods and synchronized statements.

Neither the Java language nor the Java VM provides a way to prevent deadlock.
Therefore, deadlock prevention is up to the developer. The simplest way to
prevent deadlock from happening: avoid having either a synchronized method or
a synchronized statement invoke another synchronized method/statement.
Although that advice prevents deadlock from happening, it's both impractical
(because one of your synchronized methods/statements may need to invoke a
synchronized method in a Java API -- see the various synchronized methods
in the java.util.Hashtable class for examples), and overkill
(because the synchronized method/statement being invoked might not invoke any
other synchronized method/statement, so deadlock wouldn't occur).

Note: The ACM has published
an interesting paper
on extending Java to support deadlock detection.

Conclusion

Synchronization is one of the more challenging thread-related skills that the
successful Java developer must acquire. A solid understanding of monitors and
locks, synchronized methods and synchronized statements, and deadlock is your
starting point for meeting that challenge.

I have some homework for you to accomplish:

  • If a thread holds a lock, what happens when the thread needs to enter another
    critical section controlled by the same lock?

  • Construct an example that illustrates a lack of synchronization due to a pair
    of threads acquiring different locks. Use the keyword this and the
    synchronized statement in the example.

  • In the earlier example of a component's event registration and listener logic,
    I presented two synchronized methods and a synchronized statement. You might
    be tempted to remove the synchronized statement from
    notifyClients() and make the entire method synchronized. What is
    wrong with that idea?

Next month's Java Tech completes this series by exploring Java's waiting and
notification mechanism, a thread communication example, volatile variables,
and Java 1.5's high-level synchronization tools.

Answers to Previous Homework

The previous Java Tech article presented you with some challenging homework on
console-based and GUI-based versions of the Nim computer game. Let's revisit
that homework and investigate solutions.

  1. Modify ConNim, so that it uses the Scanner class to
    handle input from the user.

    Consult the ConNim.java source code in this article's attached
    code.zip file.

  2. GuiNim's onscreen match drag-and-drop logic reveals a quirk.
    You've selected 1, 2, or 3 onscreen matches while pressing the Shift key,
    released that key after releasing the mouse button, and noticed that all
    selected onscreen matches still appear cyan (meaning they are selected). You
    can deal with the quirk by moving the mouse pointer to a blank area of the
    screen and then clicking the mouse button, or by releasing the Shift key
    before releasing the mouse button. Can you think of some better way to handle
    this quirk?

    The quirk described above occurs when you drag one or more of the selected
    matches to the human player's pile of matches and then release the mouse
    button before releasing the Shift key. This quirk can be handled in a better
    way by attaching a key listener, which implements the keyReleased
    method to invoke the mouse listener's mouseReleased method when
    the Shift key is released, to the GamePanel component in its
    constructor. The following steps accomplish that task:

    1. Modify GuiNim's constructor so that the GamePanel
      component requests focus. If this is not done, that component cannot detect
      key-release events. The following code fragment shows the needed modification:

      GamePanel gp = new GamePanel (this);
      getContentPane ().add (gp);
      pack ();
      gp.requestFocus (); // This call must come last.
    2. Change MouseAdapter ma; to final MouseAdapter ma; in
      GamePanel's constructor. This variable must be marked final so it
      can be accessed from within keyPressed.

    3. Add the following code fragment after the addMouseListener (ma);
      method call:

      KeyAdapter ka = new KeyAdapter ()
      {
         public void keyReleased (KeyEvent e)
         {
            if (e.getKeyCode () == KeyEvent.VK_SHIFT)
           
            {
                MouseEvent me;
                me = new MouseEvent (GamePanel.this,
                                     MouseEvent.MOUSE_RELEASED,
                                     0,
                                     0,
                                     0,
                                     0,
                                     0,
                                     false);

                ma.mouseReleased (me);         
            }
         }
      };
      addKeyListener (ka);

      When the code fragment detects that Shift has been released, it creates an
      object from MouseEvent and calls the mouse listener's
      mouseReleased method with that object as the method's argument.
      In turn, mouseReleased determines if any selected matches locate
      over the human player's match pile. If so, the matches are dropped. Otherwise,
      the matches remain selected.

    Make the appropriate changes above to GuiNim.java (and also to
    GuiNim2.java, if desired). Then compile the source code, and run
    the application. Try dragging matches to the human player's pile with the
    Shift key held down. Release that key once the matches are over the pile, and
    you should see them immediately disappear.

Jeff Friesen is a freelance software developer and educator specializing in Java technology. Check out his site at javajeff.mb.ca.
Related Topics >> Programming   |