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.

A simple example of a concurrent program can be found here.

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();
  }
}

Four concurrent implementations of a stack can be found here.

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