4.1. Semaphores

Processes often need to coordinate access to a set of shared resources. A semaphore is a synchronization construct that was first used to solve concurrency problems in operating systems back in the 1960s. Today, they are commonly found in multithreaded programming languages, but are more difficult to achieve in distributed systems.

The conventional definition of a semaphore is an integer counter that represents the count of available resources at any given time. A semaphore is controlled by two operations:

• down: checks to see if the counter is greater than zero, and if so, decrements its value by one. If the counter is zero, then the calling process blocks until the value is greater than zero. This operation is atomic: by calling down, a process tests and decrements the counter in an indivisible operation.

• up: increments the counter value. If one or more processes are waiting in the down operation, then one is chosen at random to proceed.

Semaphores are used as follows: A semaphore is initially created with its counter set to the total number of resources available. Whenever a process wants to access a resource, it must down the semaphore before using it. When it's done using a resource, the process calls up on the semaphore and releases it for use by others. The semaphore counter value will go up and down, depending how many processes are currently using the resources, and how many remain free. When a semaphore's count goes to zero, any process that tries to access a resource will block when calling down on the semaphore until a resource becomes available.

Semaphores are typically implemented as an integer counter that requires special language or hardware support to ensure the atomic properties of the up and down operations. Using spaces we could easily implement a semaphore as a shared variable that holds an integer counter. However we are going to take a distributed data structure approach to semaphores and implement a more scalable solution. Our implementation strategy is as follows: Instead of maintaining an integer counter, we'll make use of the bag distributed data structure and put one entry into the bag for each available resource. In effect we will have a bag of resources. When a process wants to down a semaphore, it must take an entry out of the bag first. When it's finished with the resource, to up the semaphore it must write a semaphore entry back to the space.

You can think of the semaphore entries as a pool of available resources: If n entries exist in the space at a given time, that means n resources are currently unused and available. That is, in our space-based implementation we are replacing an integer counter (that has a maximum value of n), with a pool of entries (that at any time contains at most n entries). Note that a “semaphore entry” is not a semaphore; it takes an entire bag of semaphore entries to make up a semaphore.

4.1.1. Implementing a Semaphore

To implement a space-based semaphore we first need to define an entry that will represent one resource in the pool:

public class SemaphoreEntry implements Entry {
  public String resource;

  public SemaphoreEntry() {
  }

  public SemaphoreEntry(String resource) {
    this.resource = resource;
  }
}

The single field, resource, is a string that uniquely identifies the resource. We can have many semaphores in the space as long as each group of SemaphoreEntry entries is identified by a unique resource name. We can also add more fields to describe properties of the specific resource this entry represents (such as the address of a specific printer).

Now that we have an entry to work with, we can implement the semaphore itself. To implement the distributed semaphore we are going to define a class DistributedSemaphore. Here is the code:

public class DistributedSemaphore {
  private JavaSpace space;
  private String resource;

  public DistributedSemaphore(JavaSpace space, String resource) {
    this.space = space;
    this.resource = resource;
  }

  public void create(int num) {
    for (int i = 0; i < num; i++) {
       SemaphoreEntry semaphoreEntry =
         new SemaphoreEntry(resource);
        try {
           space.write(semaphoreEntry, null, Lease.FOREVER);
        } catch (Exception e) {
           e.printStackTrace();
        }
    }
  }

  public void down() {
    SemaphoreEntry template = new SemaphoreEntry(resource);
    try {
       space.take(template, null, Long.MAX_VALUE);
    } catch (Exception e) {
     e.printStackTrace();
    }
  }

  public void up() {
    SemaphoreEntry semaphoreEntry =
      new SemaphoreEntry(resource);
    try {
       space.write(semaphoreEntry, null, Lease.FOREVER);
    } catch (Exception e) {
      e.printStackTrace();
    }
  }
}

Here we provide a constructor that takes a space and a resource name. The combination of these two uniquely identifies a specific semaphore. The constructor assigns these values to the private fields space and resource, respectively.

Once a semaphore object has been instantiated, you can call three methods: create, down, and up. The create method is called by one process to allocate a certain number of resources. Processes that need to obtain the resources never call create. The create method takes an integer num, which specifies the number of resources to create in the semaphore, and writes num entries into the space. For instance, specifying the number five would result in five SemaphoreEntry entries being added to the space.

The down method creates a SemaphoreEntry template with its resource field set to the resource name of the DistributedSemaphore object—and calls take to remove a SemaphoreEntry for the resource from the space. If no such entries are available, then no such resources are available and take will wait indefinitely until one shows up. Once a SemaphoreEntry is taken from the space, the down method returns to the calling process, which can proceed knowing it has the resource.

The up method creates a new SemaphoreEntry and writes it into the space. Once it is returned, the resource can be used by other processes; in fact, some may already be waiting.

Now that we've implemented a distributed semaphore, let's put it to use in an example application: a license manager for a networked software product.

4.1.2. Implementing a License Manager

Networked software products are commonly sold with a license for a fixed number of simultaneous users. Using our distributed semaphore we are going to implement a license manager library that ensures only a limited number of clients can run at the same time. Our library isn't designed to be bulletproof, but it does demonstrate how we can implement a license service using semaphores.

The library consists of two distinct parts: a trivial installer component that is used when installing the product, and a runtime component that is embedded in a client application to ensure that a license resource is available before the application runs. Let's see how the components work.

4.1.3. The License Manager Installer

Our installer is a simple application that takes a product name and number of seats as command line parameters. For instance, a command line to execute the installer looks something like this:

java jsbook.chapter4.license.LicenseInstall JSGame 3

In this example, the application parameters specify that the software product is called “JSGame” and comes with a three-seat license that restricts its use to just three simultaneous users. This isn't very safe—anyone installing the product could change the parameters—but our goal here is to demonstrate semaphores, not build a secure installer.

Here's the LicenseInstall code:

public class LicenseInstall {
  public static void main(String[] args) {
    JavaSpace space = SpaceAccessor.getSpace();

    String product = args[0];
    int seats =  Integer.parseInt(args[1]);

    DistributedSemaphore license =
      new DistributedSemaphore(space, product);
    license.create(seats);
    System.out.println("License created for " + seats +
      " seats");
  }
}

When the LicenseInstall application starts, its main method is called, which first obtains access to the space. The application then processes the command-line parameters to obtain the product name and number of seats. Next, the application creates a DistributedSemaphore initialized with the current space and product name (in this case “JSGame”). Then the create method is called to create a semaphore with the specified number of seats (in this case three). Once the LicenseInstall execution is complete, the license is installed and clients can make use of it.

4.1.4. The License Manager Client Library

The license manager is implemented as a simple object that the client-side application instantiates as the application starts up. To obtain a license to run a product the application calls the license manager's getLicense method. Before the application terminates it calls the license manager's returnLicense method.

Here is the code for the LicenseManager:

public class LicenseManager {
  private DistributedSemaphore semaphore;

  public LicenseManager(JavaSpace space, String product) {
    semaphore = new DistributedSemaphore(space, product);
  }

  public void getLicense() {
    System.out.println("getting key");
    semaphore.down();
  }

  public void returnLicense() {
    System.out.println("returning key");
    semaphore.up();
  }
}

Here the constructor takes a space and a product name and uses them to instantiate a private DistributedSemaphore object. The getLicense method simply calls a down on the distributed semaphore, which has the effect of obtaining a license; while the returnLicense method calls up, which has the effect of releasing the license.

Now any class can make use of this license manager by adding a small code fragment to its startup code; here is an example:

LicenseManager licenseMgr = new LicenseManager(space, product);
licenseMgr.getLicense();

// application's main loop here

licenseMgr.returnLicense();

Assuming that space and product variables have been initialized, we instantiate a LicenseManager and call getLicense. If a license is available, then the call returns immediately and we can use the application, otherwise we wait until one is available. When we are finished with the application we return the license.

The semaphore technique for controlling access to licensed software works equally well no matter how many seats the license allows, and no matter whether we have two users sharing access to the software or hundreds. If all the license resources are taken, other users will wait until a license becomes available before they can start running the software. Of course, it makes sense for the number of seats to comfortably accommodate usage demands. If there are 100 users who want to use the application frequently, the three-seat license of our example will severely limit users' access to the software.

As we mentioned at the outset, this isn't an industrial-strength license manager quite yet. For one thing, we've sidestepped the issue of partial failure for the time being. If a process takes a license semaphore entry from the space and then crashes before writing it back, the entry is lost for good and our resource pool is reduced by one. For our semaphore code to work in the presence of failure, we will have to introduce transactions; we'll return to the topic of transactions in Chapter 9. The second drawback of our license manager is that it is very easy to forge license resources and override the semaphore: a piece of code could take a license from the space and then write it back not just once, but as many times as it pleases.