TU Computing and System Sciences
Bill Toll
Explanation of ABCs Concurrency Example

The example code uses a semaphore class and two classes extended from it (BinarySempahore and CountingSemaphore) to implement three threads printing the letters A, B, anc C according to the following rules:

  1. A B must be output before any Cs can be output.
  2. Bs anc Cs must alternate in the output string, that is after the first B is output, another B cannot be output until a C is output. Similarly, once a C is output, another C cannot be output until a B is output
  3. The total number of Bs and Cs that have been output at any given point in the output string cannot exceed the number of As output at that point in the string.

ABCs

The ABCs class extends MyObject and includes a main method to be executed as an application. The main method creates a thread of class Pa, a thread of Pb, and a thread of class Pc. The semaphores B, C, and sum are used to coordinate these concurrent threads. The classes Pa, Pb, and Pc are extended from ABCs with run methods that use the appropriate semaphores to guarantee proper operation according to the rules stated above.

MyObject

This class is included in the Utilities package. It extends Object and implements the Serializable interface. This class provides the following methods:

Semaphore

This class uses Java concurrency structures (synchronized, wait, release) to implement traditional semaphores and associated P and V methods.

BinarySemaphore

This class extends Semaphore to create a BinarySemaphore.

CountingSemaphore

This class extends Semaphore to create a CountingSemaphore.

WouldBlockException

This class implements a simple exception class used by Semaphore.



NOTES

A semaphore in an object-oriented paradigm such as Java is an object created from a class that has a private integer data field and two public access methods, P and V. If the integer value of a semaphore S is positive, a thread invoking P(S) decrements S in an atomic action; otherwise the thread waits. If a thread invokes V(S) and no thread is waiting at a P(S) call, then the value os S is incremented atomically; otherwise one waiting thread (chosen non-deterministically) is released and allowed to continue past its P(S). In Java, synchronized methods are used to implement P and V. The Java wait() and notify() methods are used to provide blocking releasing functionality.

The Serializable interface implemented by MyObject simply means that the object can be written to an output stream because it can be serialized - transformed into a stream of bytes.

The threads used in the example follow the standard practice of inheriting from another class and implementing the Runnable interface rather than inheriting from the Thread class. The interface is implemented by providing a run method.

In class ABCs, the semaphores are declared static meaning that they may be accessed by other executing classes that are extended from ABCs. In this example, the class Pa, Pb, and Pc provide the Runnable interface for threads created to print 'A', 'B', or 'C'. Objects of these classes may use the Semaphores B, C, and sum created in ABCs.

The rules for printing an 'A' are implemented by allowing an 'A' to be printed at any time. In order to support the other rules, V(sum) is executed to indicate that an additional 'A' has been printed.

The rules for printing a 'B' are implemented by waiting for a 'C' to be printed by using the C binary semaphore. The C semaphore is initialized to 1 so that a 'B' is printed first. The sum semaphore must be available before the letter may be printed to satisfy the rule that the total number of 'A's printed must be at least as many as the total of the 'B's and 'C's. After the 'B' is printed, this fact is signaled by V(B) allowing a 'C' to print.

The rules for printing a 'C' are handled in a similar manner except that the B semaphore is initialized to 0 so that a 'C' cannot be printed until after a 'B'.