Synchronization and locking

 

Overview

When two or more threads share the same resource, nasty things can happen. The problem is similar to what can occur when two people, say Pat and Chris, share a joint checking account. Consider this scenario:

  1. At an ATM, Pat does a balance inquiry and learns the current account balance is $100.

  2. At about the same time and on the other side of town, Chris does a balance inquiry and learns the same thing.

  3. Pat writes a check for $60 and believes the account balance is now $40.

  4. Chris writes a check for $80 and believes the account balance is now $20.

  5. Later that day, they learn of each other's action and realize they have overdrawn the account by $40.

One way to prevent this problem is to permit only one task at a time to control the resource. This is called a resource "lock". In other words, Pat and Chris should have only one checkbook. This would make it impossible for them to write two checks at the same time because only one would have the checkbook.

While locking solves the problem of simultaneous modification of a shared resource, it can lead to another problem known as "deadlock". This occurs when each of two tasks has locked a resource that the other task needs to continue processing. Unless or until one task gives up its locked resource, neither task can go on. For example, Pat and Chris may each want to write a check. If Pat has the checkbook and Chris has the only pen available to write a check, no one can proceed until one gives up their locked resource.

Fortunately, Java provides a mechanism for locking resources and synchronizing thread processing so such problems can be avoided.

 

A program with a problem

The following program launches two threads that share a single StringBuffer object with the intention of loading it with characters to complete the string "abcdefghijklmnopqrstuvwxyz". The threads do not lock the StringBuffer and frequently yield control of the CPU. This permits the other thread to add a character (or two) when they aren't looking.

public class App {

  // Inner class for a thread to load the remaining characters of the
  // alphabet into a StringBuffer.

  public static class LoadCharacters extends Thread {

    // Object reference for the StringBuffer.

    StringBuffer buffer;

    // This constructor receives and saves a reference to the
    // StringBuffer.

    public LoadCharacters(StringBuffer theBuffer) {
      buffer = theBuffer;
    }

    // This method defines thread processing.

    public void run() {

      // Local variables for the last character in the StringBuffer
      // and the next character to be added to the StringBuffer.

      char lastChar;
      char nextChar;

      // Loop to add remaining characters through the letter 'z'.

      do {

        // Determine the last character in the StringBuffer.

        lastChar = buffer.charAt(buffer.length() - 1);

        // If the last character is less than 'z', determine the
        // next character in the collating sequence and append that
        // character to the end of the StringBuffer.
        //
        // NOTES: (1) The call to Thread.yield() simulates extensive
        // processing activity, I/O, etc. and forces an error when
        // multiple, unsynchronized threads are executed. (2) As each
        // character is appended to the StringBuffer, it is displayed
        // along with the thread's internal name to trace processing.

        if (lastChar < 'z') {
          nextChar = (char) (lastChar + 1);
          Thread.yield();
          buffer.append(nextChar);
          System.out.println(getName() + ": " + nextChar);
        }
      } while (lastChar < 'z');
    }
  }

  // This method is the application's starting point.

  public static void main(String[] args) {

    // This StringBuffer will be shared by multiple threads.

    StringBuffer myBuffer = new StringBuffer("abc");

    // Create and start two threads to load the shared StringBuffer
    // with the remaining characters of the alphabet.

    Thread t1 = new Thread(new LoadCharacters(myBuffer));
    t1.start();
    Thread t2 = new Thread(new LoadCharacters(myBuffer));
    t2.start();

    // Loop while either thread is alive. This forces the application
    // thread to pause until the subthreads are done.

    while (t1.isAlive() || t2.isAlive()) {
    }

    // Display the final contents of the StringBuffer.

    System.out.println("Result: " + myBuffer.toString());
  }
}

Notes:

  1. Run this program several times. You may get different erroneous results each time.

  2. The statement that calls Thread.yield() in the inner LoadCharacters class simulates extensive processing or I/O activity that might realistically occur within a thread. Because thread processing is interleaved by the JVM, simultaneous updating of the StringBuffer will result. See what happens when you remove or comment-out the statement (one thread will do all the work because our task is so trivial).

 

The synchronized keyword

Thread 1 Thread 1
\

---------->

    /
Thread 2  -->

synchronized code

 --> Thread 2
/     \
Thread 3 Thread 3

Code that is synchronized is said to be "single-threaded".

public synchronized boolean updateBalance(double amount) {
   single-threaded code goes here...
}

For a static (class) method, the locked resource is the Class object. For an instance method, the locked resource is the current (this) object.

To synchronize a statement block, use the synchronized statement as shown by

synchronized (someObject) {
   single-threaded code goes here...
}

where someObject is the object (resource) to be locked. Every object in Java may be locked because the Object class, the root of the class hierarchy, contains a lock variable which can only be seen and manipulated by the Java Virtual Machine.

public class App {

  // Inner class for a thread to load the remaining characters of the
  // alphabet into a StringBuffer.

  public static class LoadCharacters extends Thread {

    // Object reference for the StringBuffer.

    StringBuffer buffer;

    // This constructor receives and saves a reference to the
    // StringBuffer.

    public LoadCharacters(StringBuffer theBuffer) {
      buffer = theBuffer;
    }

    // This method defines thread processing.

    public void run() {

      // Local variables for the last character in the StringBuffer
      // and the next character to be added to the StringBuffer.

      char lastChar;
      char nextChar;

      // Loop to add remaining characters through the letter 'z'.

      do {

        // Lock the StringBuffer to prevent simultaneous processing
        // by multiple threads.

        synchronized (buffer) {

          // Determine the last character in the StringBuffer.

          lastChar = buffer.charAt(buffer.length() - 1);

          // If the last character is less than 'z', determine the
          // next character in the collating sequence and append that
          // character to the end of the StringBuffer.
          //
          // NOTES: (1) The call to Thread.yield() simulates extensive
          // processing activity, I/O, etc. and forces an error when
          // multiple, unsynchronized threads are executed. (2) As each
          // character is appended to the StringBuffer, it is displayed
          // along with the thread's internal name to trace processing.

          if (lastChar < 'z') {
            nextChar = (char) (lastChar + 1);
            Thread.yield();
            buffer.append(nextChar);
            System.out.println(getName() + ": " + nextChar);
          }
        }
      } while (lastChar < 'z');
    }
  }

  // This method is the application's starting point.

  public static void main(String[] args) {

    // This StringBuffer will be shared by multiple threads.

    StringBuffer myBuffer = new StringBuffer("abc");

    // Create and start two threads to load the shared StringBuffer
    // with the remaining characters of the alphabet.

    Thread t1 = new Thread(new LoadCharacters(myBuffer));
    t1.start();
    Thread t2 = new Thread(new LoadCharacters(myBuffer));
    t2.start();

    // Loop while either thread is alive. This forces the application
    // thread to pause until the subthreads are done.

    while (t1.isAlive() || t2.isAlive()) {
    }

    // Display the final contents of the StringBuffer.

    System.out.println("Result: " + myBuffer.toString());
  }
}

 

Monitor objects

When an object's wait() method is called, the executing thread releases its resource lock and is placed in a "waiting pool" of threads that are waiting for a chance to reacquire the object's lock in order to resume processing.

When an object's notify() method is called, one of the threads from the waiting pool will be given the opportunity to reacquire the object's resource lock. When notifyAll() is called, all of the threads in the waiting pool will be given the opportunity to reacquire the object's resource lock. In either case, only one thread will be successful and there is no way to predict which thread it will be (it could even be the thread that was just suspended). Once the lock is obtained, the lucky thread is ready to resume processing.

Monitor Object

Waiting Pool

lock variable

 

wait()

notify()

notifyAll()

 

suspended thread

------->

  

resuming thread

<-------

Thread 1

Thread 2

Thread 3

Thread 4

:

Thread n

public class App {

  // This class defines a "mailbox" which can hold only one message
  // at a time.

  public static class MailBox {

    // Instance variables for the message to be stored and to indicate
    // if the box is empty.

    String message;
    boolean empty = true;

    // This method can be called to store a message. If the box has
    // an unread message, it waits until that message has been read
    // before storing the new one. After storing a message, it
    // notifies a task that may be waiting to read the new message.

    public synchronized void setMessage(String theMessage) {
      while (!empty) {
        try {
          wait();
        }
        catch (InterruptedException err) {
        }
      }
      message = theMessage;
      empty = false;
      notify();
    }

    // This method can be called to read a message. If the box has
    // no message, it waits until a message has been stored. When a
    // message is read, it notifies a task that may be waiting to
    // store a new message.

    public synchronized String getMessage() {
      while (empty) {
        try {
          wait();
        }
        catch (InterruptedException err) {
        }
      }
      empty = true;
      notify();
      return message;
    }
  }

  // This class defines a thread to send random messages to a MailBox
  // at random intervals of 1 to 3 seconds. When a message is sent, it
  // is also logged to the console.

  public static class SendMessage extends Thread {
    boolean isAlive;
    MailBox box;
    public SendMessage(MailBox theBox) {
      box = theBox;
      isAlive = true;
    }
    public void run() {
      while (isAlive) {
        try {
          Thread.sleep((int)(1000*(((Math.random()*1000)%3)+1)));
        }
        catch (InterruptedException err) {
        }
        String message = new String("Message " + Math.random());
        box.setMessage(message);
        System.out.println("Sent: " + message);
      }
    }
    public void destroy() {
      isAlive = false;
    }
  }

  // This class defines a thread to read messages from a MailBox
  // at random intervals of 1 to 3 seconds. When a message is read,
  // its contents are displayed on the console.

  public static class ReadMessage extends Thread {
    boolean isAlive;
    MailBox box;
    public ReadMessage(MailBox theBox) {
      box = theBox;
      isAlive = true;
    }
    public void run() {
      while (isAlive) {
        try {
          Thread.sleep((int)(1000*(((Math.random()*1000)%3)+1)));
        }
        catch (InterruptedException err) {
        }
        String message = box.getMessage();
        System.out.println("Read: " + message);
      }
    }
    public void destroy() {
      isAlive = false;
    }
  }

  // This method is the application's starting point.

  public static void main(String[] args) {

    // This mailbox will be shared by threads that send and read
    // messages.

    MailBox b = new MailBox();

    // Create and launch threads to send and read messages.

    SendMessage send = new SendMessage(b);
    send.start();
    ReadMessage receive = new ReadMessage(b);
    receive.start();

    // Sleep for 20 seconds while the subthreads process.

    try {
      Thread.sleep(20000);
    }
    catch (InterruptedException err) {
    }

    // Destroy the subthreads.

    send.destroy();
    receive.destroy();

    // Loop until the subthreads are dead then display a termination
    // message.

    while (send.isAlive() || receive.isAlive()) {
    }
    System.out.println("DONE");
  }
}

Note that this is a smart MailBox object. It monitors and controls its threads by calling the inherited wait() and notify() methods.

 

Lab exercise for Ferris students

E-mail your answers to this assignment no later than the due date listed in the class schedule.

 

Review questions

  1. Which of the following are non-static, instance methods of the Object class?  (choose three)

  1. sleep()

  2. wait()

  3. notify()

  4. equals()

  5. run()

  1. Assume all unseen code is correct and shouldWait is a boolean variable with a value of true. What will happen when an attempt is made to compile and execute this method? The line numbers are for reference purposes only.

1
2
3
4
5
6
public synchronized void mayWait() {
  if (shouldWait)
    wait();
  else
    System.out.println("Continue");
}
  1. a compile error will occur at line 1

  2. a compile error will occur at line 3

  3. the code will compile but a runtime exception will occur 

  4. the code will compile and execute to display "Continue"

  5. the code will compile and execute but nothing will be displayed

  1. Which of the following statements are true?  (choose two)

  1. In order to call notify() a thread must have a lock on the object involved

  2. A monitor object must either extend Thread or implement Runnable

  3. An object can have only one thread in the waiting pool at a time 

  4. The notify() method allows for the specification of the thread to be notified

  5. Only an object can be locked

  1. True or False: If t1 and t2 are Thread objects that share the same monitor object, the following statement could be coded within t1

t2.yield();

  1. True

  2. False