Herb Sutter and James Larus. Software and the Concurrency Revolution. Queue, 3(7):54-62, September 2005.

Celeste Biever. Chip revolution poses problems for programmers. New Scientist, 2594:26-27, March 2007.

Bryan Cantrill and Jeff Bonwick. Real-world concurrency. Communcations of the ACM, 51(11):34-39, November 2008.

/**
 * An Assignment thread continuously assigns its private value to
 * a shared value.
 */
public class Assignment extends Thread
{
    /** The value shared by all Assignment objects */
    public static long sharedValue;
 
    /** The private value of this Assignment object */
    private long privateValue;
 
    /**
     * Creates an Assignment object with the given private value.
     *
     * @param privateValue the private value of the created Assignment object.
     */
    public Assignment(long privateValue)
    {
        this.privateValue = privateValue;
    }
 
    /**
     * Continuously assigns the private value of this Assignment object
     * to the shared value of all Assignment objects.
     */
    public void run()
    {
        while (true)
        {
            Assignment.sharedValue = this.privateValue;
        }
    }
}

/**
 * A Print thread continuously prints the value of the value shared
 * by all Assignment objects.
 */
public class Print extends Thread
{
    /**
     * Continuously prints the value of the value shared
     * by all Assignment objects.
     */
    public void run()
    {
        while (true)
        {
            System.out.println(Assignment.sharedValue);
        }
    }
}

public class Client
{
    public static void main(String[] args)
    {
        Assignment zero = new Assignment(0);
        Assignment max = new Assignment(Long.MAX_VALUE);
        Print print = new Print();
        zero.start();
        max.start();
        print.start();
    }
}

A guest lecture by librarian John Dupuis will take place in the Steacie Building, room 021. Ask at the library reference desk for room 021 if you cannot find it.

Leah Graham and Panagiotis Takis Metaxas. Of course it's true; I saw it on the Internet! Communications of the ACM, 46(5):70-75, May 2003.

Neil L. Waters. Why you can't cite Wikipedia in my class. Communications of the ACM, 50(9):15-17, September 2007.

Some information about literature search can be found here.

Chapter 1 of

Mordechai Ben-Ari. Principles of Concurrent and Distributed Programming. Second edition. Addison-Wesley, Harlow, UK, 2006.

P.J. Courtois, F. Heymans and D.L. Parnas. Concurrent control with "readers" and "writers". Communications of the ACM, 14(10): 667-668, October 1971.

Edsger W. Dijkstra. Two starvation-free solutions of a general exclusion problem. EWD 625.

An alternative solution to the dining philosophers can be found here.

C.A.R. Hoare. Monitors: an operating system structuring concept. Communications of the ACM, 17(10):549–557, October 1974.

Corrigenda

• Add count := count - 1 to the first remove procedure on page 553.
• Replace + with - in the release procedure on page 554.

A few examples can be found here.

C.A.R. Hoare. Communicating Sequential Processes. Communications of the ACM, 21(8):666-677, August 1978.

Some sources (in alphabetical order) where you can find information about concurrent programming in Java:

• Mordechai Ben-Ari. Principles of Concurrent and Distributed Programming. Second edition. Addison-Wesley, Harlow, UK, 2006.
• Mary Campione, Kathy Walrath and Alison Huml. The Java Tutorial. Lesson: Threads: Doing Two or More Tasks At Once.
• James Gosling, Bill Joy, Guy L. Steele Jr. and Gilad Bracha. The Java Language Specification. Third edition.
• Charles W. Kann. Creating components: object oriented, concurrent, and distributed computing in Java. Auerbach, Boca Raton, FL, USA, 2004.
• Douglas Lea. Concurrent programming in Java : design principles and patterns. Second edition. Addison-Wesley, Reading, MA, USA, 2000.

If you come across another source that may be useful, please email it to the instructor.

/**
 * A printer prints its name 1000 times.
 *
 * @author Franck van Breugel
 */
public class Printer extends Thread
{
  /**
   * Initializes this printer with the given name.
   *
   * @param name the name of this printer.
   * @pre. name != null
   */
  public Printer(String name)
  {
    super(name);
  }
 
  /**
   * Prints the name of this printer 1000 times.
   */
  public void run()
  {
    final int NUMBER = 1000;
    for (int i = 0; i < NUMBER; i++)
    {
      System.out.print(this.getName());
    }
  }
}

public class PrinterTest
{
  public static void main(String[] args)
  {
    new Printer("1").start();
    new Printer("2").start();
  }
}

/**
 * A printer prints its name 1000 times.
 *
 * @author Franck van Breugel
 */
public class Printer implements Runnable
{
  public void run()
  {
    final int NUMBER = 1000;
    for (int i = 0; i < NUMBER; i++)
    {
      System.out.print(Thread.currentThread().getName());
    }
  }
}

public class PrinterTest
{
  public static void main(String[] args)
  {
    Printer printer = new Printer();
    new Thread(printer, "1").start();
    new Thread(printer, "2").start();
  }
}

A solution to the readers-writers problem using semaphores in Java. First, a Reader.

package semaphore;
 
import java.util.Random;
import java.util.concurrent.Semaphore;
 
/**
 * A reader.
 *
 * @author Franck van Breugel
 */
public class Reader extends Thread
{
  private static int readers = 0;
  private static final Semaphore mutex = new Semaphore(1);
 
  /**
   * Initializes this reader.
   */
  public Reader()
  {
    super();
  }
 
  /**
   * Reads.
   */
  public void run()
  {
    try
    {
      Reader.mutex.acquire();
      Reader.readers++;
      if (Reader.readers == 1)
      {
        Writer.writer.acquire();
      }
      Reader.mutex.release();
      // read
      Reader.mutex.acquire();
      Reader.readers--;
      if (Reader.readers == 0)
      {
        Writer.writer.release();
      }
      Reader.mutex.release();
    }
    catch (InterruptedException e) {}
  }
}

Then, a Writer.

package semaphore;
 
import java.util.Random;
import java.util.concurrent.Semaphore;
 
/**
 * A writer.
 *
 * @author Franck van Breugel
 */
public class Writer extends Thread
{
  public static final Semaphore writer = new Semaphore(1, true);
 
  /**
   * Initializes this writer.
   */
  public Writer()
  {
    super();
  }
 
  /**
   * Writes.
   */
  public void run()
  {
    try
    {
      Writer.writer.acquire();
      // write
      Writer.writer.release();
    }
    catch (InterruptedException e) {}
  }
}

And finally an app.

package semaphore;
 
/**
 * This app creates a number of readers and writers.
 *
 * @author Franck van Breugel
 */
public class ReadersWriters
{
  /**
   * @param args[0] numbers of readers.
   * @param args[1] number of writers.
   */
  public static void main(String[] args)
  {
    try
    {
      int readers = Integer.parseInt(args[0]);
      int writers = Integer.parseInt(args[1]);
      for (int i = 0; i < writers; i++)
      {
        new Writer().start();
      }
      for (int i = 0; i < readers; i++)
      {
        new Reader().start();
      }
    }
    catch (Exception e)
    {
      System.out.println("Usage: java ReadersWriters < number of readers> <number of writers>");
    }
  }
}

Below, we present another solution to the readers-writers problem.

/**
 * This class represents a database.  There are many 
 * competing threads wishing to read and write.  It is 
 * acceptable to have multiple processes reading at the 
 * same time, but if one thread is writing then no other 
 * process may either read or write.
 */
public class Database
{
  private int readers; // number of active readers
 
  /**
   * Initializes this database.
   */
  public Database()
  {
    this.readers = 0;
  }
 
  /**
   * Read from this database.
   */
  public void read(int number)
  {
    synchronized(this)
    {
      this.readers++;
    }
    // read
    synchronized(this)
    {
      this.readers--;
      if (this.readers == 0)
      {
        this.notifyAll();
      }
    }
  }
 
  /**
   * Writes to this database.
   */
  public synchronized void write(int number)
  {
    while (this.readers != 0)
    {
      try
      {
        this.wait();
      }
      catch (InterruptedException e) {}
    }
    // write
    this.notifyAll();
  }
}

Presentations in CSEB 3033.

Presentations

A guest lecture by Susan Visser (Publishing Program Manager, IBM) in CSEB 3033.

Some information about writing can be found here.

Communicating Sequential Processes for Java

public class Process implements CSProcess
{
  private ChannelOutput verhoog;
  private ChannelOutput prolaag;
 
  public Process(ChannelOutput verhoog, ChannelOutput prolaag)
  {
    super();
    this.verhoog = verhoog;
    this.prolaag = prolaag;
  }
 
  public void run()
  {
    this.prolaag.write(null);
    // critical section
    this.verhoog.write(null);
  }
} 

public class Semaphore implements CSProcess
{
  private int value;
  private AltingChannelInput verhoog;
  private AltingChannelInput prolaag;
 
  public Semaphore(int value, AltingChannelInput verhoog, AltingChannelInput prolaag)
  {
    super();
    this.value = value;
    this.verhoog = verhoog;
    this.prolaag = prolaag;
  }
 
  public void run()
  {
    final int ALTERNATIVES = 2;
    final int V = 0;
    final int P = 1;
    final Guard[] guard = new Guard[ALTERNATIVES];
    guard[V] = this.verhoog;
    guard[P] = this.prolaag;
    final boolean[] precondition = new boolean[ALTERNATIVES];
    precondition[V] = true;
    final Alternative alternative = new Alternative(guard);
    while (true)
    {
      precondition[P] = this.value > 0;
      switch (alternative.select(precondition))
      {
        case V:
          this.verhoog.read(); 
          this.value++;
          break;
        case P:
          this.prolaag.read(); 
          this.value--;
          break;
      }
    }
  }
}

public class Main
{
  public static void main(String[] args)
  {
    Any2OneChannel verhoog = Channel.any2one();
    Any2OneChannel prolaag = Channel.any2one();
    Semaphore semaphore = new Semaphore(1, verhoog.in(), prolaag.in());
    Process one = new Process(verhoog.out(), prolaag.out());
    Process two = new Process(verhoog.out(), prolaag.out());
    CSProcess[] process = { semaphore, one, two };
    Parallel parallel = new Parallel(process);
    parallel.run();
  }
}

Concurrent implementations of the following interface.

/**
 * A Stack.
 */
public interface Stack<T>
{
  /**
   * Removes the top element from this stack and returns it.
   *
   * @return the top element of this stack.
   * @throw Exception if this stack is empty.
   */
  public T pop() throws Exception;
 
  /**
   * Pushes the given element onto this stack.
   *
   * @param the element to be pushed onto this stack.
   */
  public void push(T element);
}

In each implementation of the above interface we will exploit the class Node.

/**
 * A node of a linked list.
 */
public class Node<T>
{
  private T element;
  private Node<T> next;
 
  /**
   * Initializes this node with the given element and next node.
   *
   * @param element the element stored in the node.
   * @pre. element != null
   * @param next the next node in the list.
   */
  public Node(T element, Node<T> next)
  {
    this.element = element;
    this.next = next;
  }
 
  /**
   * Returns the element of this node.
   *
   * @return the element of this node.
   */
  public T getElement()
  {
    return this.element;
  }
 
  /**
   * Returns the next node.
   *
   * @return the next node.
   */
  public Node<T> getNext()
  {
    return this.next;
  }
 
  /**
   * Sets the next node to the given node.
   *
   * @param node the new next node.
   */
  public void setNext(Node<T> next)
  {
    this.next = next;
  }
}

In the first implementation, we simply lock the whole stack when we pop or push an element.

public class First<T> implements Stack<T>
{
  private Node<T> top;
 
  public First()
  {
    this.top = null;
  }
 
  public synchronized T pop() throws Exception
  {
    if (this.top == null)
    {
      throw new Exception();
    }
    else
    {
      T element = this.top.getElement();
      this.top = this.top.getNext();
      return element;
    }
  }
 
  public synchronized void push(T element)
  {
    this.top = new Node<T>(element, this.top);
  }
}

In the second implementation, we lock the top node when we pop or push an element.

public class Second<T> implements Stack<T>
{
  private Node<T> top;
 
  public Second()
  {
    this.top = null;
  }
 
  public T pop() throws Exception
  {
    Node<T> node;
    synchronized (this.top)
    {
      if (this.top == null)
      {
        throw new Exception();
      }
      else
      {
        node = this.top;
        this.top = this.top.getNext();
      }
    }
    return node.getElement();
  }
 
  public void push(T element)
  {
    Node<T> node = new Node<T>(element, null);
    synchronized (this.top)
    {
       node.setNext(this.top);
       this.top = node;
    }
  }
}

The third implementation does not use any locking. We exploit the class AtomicReference.

import java.util.concurrent.atomic.*;
 
public class Third<T> implements Stack<T>
{
  private volatile AtomicReference<Node<T>> top;
 
  public Third()
  {
    this.top = new AtomicReference<Node<T>>();
  }
 
  public T pop() throws Exception
  {
    Node<T> node;
    do
    {
      node = this.top.get();
      if (node == null)
      {
        throw new Exception();
      }
    }
    while (!this.top.compareAndSet(node, node.getNext()));
    return node.getElement();
  }
 
  public void push(T element)
  {
    Node<T> node = new Node<T>(element, null);
    do
    {
      node.setNext(this.top.get());
    }
    while (!this.top.compareAndSet(node.getNext(), node));
  }
}

Also the fourth implementation does not use any locking. This time we exploit the class AtomicReferenceFieldUpdater.

import java.util.concurrent.atomic.*;
 
public class Fourth<T> implements Stack<T>
{
  private volatile Node<T> top;
 
  private static final AtomicReferenceFieldUpdater<Fourth<T>, Node<T>> topUpdater
    = AtomicReferenceFieldUpdater.newUpdater(Fourth.class, Node.class, "top");
 
  public Fourth()
  {
    this.top = null;
  }
 
  public T pop() throws Exception
  {
    Node<T> node;
    do
    {
      node = this.top;
      if (node == null)
      {
        throw new Exception();
      }
    }
    while (Fourth.topUpdater.compareAndSet(this, node, node.getNext()));
    return node.getElement();
  }
 
  public void push(T element)
  {
    Node node = new Node<T>(element, null);
    do
    {
        node.setNext(this.top);
    }
    while (Fourth.topUpdater.compareAndSet(this, node.getNext(), node));
  }
}

Brian Goetz. Testing Concurrent Programs. September 2006.

Presentations in CSEB 3033

Presentations

Edmund M. Clarke and Jeannette M. Wing. Formal methods: state of the art and future directions. ACM Computing Surveys, 28(4):626-643, December 1996.

Mats P.E. Heimdahl and Constance L. Heitmeyer. Formal methods for developing high assurance computer systems: working group report. In Proceedings of the 2nd IEEE Workshop Industrial Strength Formal Specification Techniques, pages 60-64, Boca Raton, FL , USA, October 1998. IEEE.

An answer to the question Why do we need software verification tools? can be found here.

Willem Visser, Klaus Havelund, Guillaume Brat, SeungJoon Park and Flavio Lerda. Model Checking Programs. Automated Software Engineering, 10(2): 203-232, April 2003.

More information about Java PathFinder can be found here.

Presentations

Presentations in CSEB 3033