Java concurrency with thread gates

Manage concurrent thread execution in complex business applications

The thread gate pattern is an effective tool for controlling thread concurrency, but many developers are unfamiliar with it. Just as a traffic light can regulate the behavior of automobiles at an intersection, thread gates can block or allow thread progress based on given factors. Obi Ezechukwu introduces the concept of thread gates, then shows you how to implement them in a multithreaded prime-number generator. Level: Intermediate

Multithreading and code concurrency were once the preserve of elite programmers, but the combination of multicore processing power, complex requirements, and the readily available javax.util.concurrent package has changed that. Today, enterprise application developers are expected to be knowledgeable about the various synchronization mechanisms and constructs available in the Java language. The level of expectation is even higher where the problems being solved require non-textbook and highly innovative concurrency constructs. It isn't enough in those situations to understand the Java language's concurrency mechanisms and those included in the standard SDK; you also must be able to use these tools as building blocks for custom-made concurrency controls.

In this article, we'll explore a concurrency pattern that isn't widely discussed, generally called thread gates. Like its real-world counterpart, a gate instance opens or closes, thus allowing or preventing thread progress. It does so based on the truth value of some predicate.

I'll start with an overview of thread gates based on the traffic-flow model, then explain how to set up your development environment for the example application, a multithreaded prime-number generator. The remainder of the article will be hands-on, as you learn about the thread gate pattern by implementing it.

Thread gates: An overview

A good metaphor for thread gates is the traffic light system that operates on many public roads. When the signal is red, cars have to wait at the stop line until the signal changes. On the other hand, cars are free to run past the signal when it is green. There is no limit to the number of times that the signal can go from green to red, given a statistically significant observation timeframe. Traffic lights are designed to enable crossflow of traffic, and are redundant where crossflow does not exist. In a programmer's terms, you can imagine the light as a control that lets bidirectional traffic share a small section of road that might otherwise cause the paths of traffic to intersect in an unsafe manner.

In the same way, thread gates are generally best used for scenarios where one set of threads has to be prevented from proceeding beyond a determined point, whilst another set of threads is active. To put it another way, the competing sets of threads are dependent on the value of some truth predicate, where each distinct value of the predicate strictly triggers one (and only one) set of threads, forcing the others to remain suspended. Note that the emphasis here is on sets or groups of threads rather than individual threads. In essence, the focus is on scenarios where multiple threads share access to an underlying resource, and the threads can be partitioned into sets depending on the actions that they perform in relation to that resource.

A good example of this is in producer-consumer flows, where some threads are responsible for producing data that is consumed by another group of threads; the shared resource is most likely the handoff mechanism (data bus) used by the disparate thread groups; and the truth predicate that determines thread progress is the quantity of data in the handoff mechanism. An in-memory request queue can sometimes fit such a pattern if the data is enqueued as part of a process that is analogous to a production process, and the data is dequeued or consumed by a separate process.

The producer-consumer analogy is a good one for formulating a problem that explores the concept of thread gates. An example problem should be easily recognizable to the vast majority of programmers. In this case, the problem should also be one that lends itself easily to task splitting and parallelization, as the emphasis is on creating a multithreaded solution to it. This article's sample application will fulfill all of these criteria and more.

The multithreaded prime-number generator

This article's example application will tackle the age-old problem of finding all the probable prime numbers within a given bound (between one and a million, say). Specifically, the task is to implement a software component that exposes a method for retrieving all the probable prime numbers in a given range (with an upper and lower bound given). Assume that the component's client mandates that the method return a thread-safe handle for accessing the results as soon as it is invoked, and then performs the actual task of finding the prime numbers in the background or asynchronously. Assume also that the handle must provide a blocking method that allows primes to be accessed and returned as soon as possible, such that the client does not have to wait for the search to complete before accessing results. To simplify the task, no restrictions are placed on the order in which the handle returns the results.

Before reading further you should download the code archive that accompanies this article and create a development project within your favorite IDE. The archive contains ten source files, which are organized as follows:

-src\
  -main\
    -java\
       -com\
          -javaworld\
             -primefinder\
                  PrimeNumberSearcher.java
                  PrimeNumberSource.java
                  PrimeUtil.java
                  ThreadGate.java
                  PrimeSearchThread.java
                  PartitionInfo.java
                  PrimeNumberReader.java
                  GatedPrimeNumberSearcher.java
                  ConcurrentPrimeNumberSource.java                                    
-src\
 -test\
    -java\
       -com\
          -javaworld\
             -primefinder\
                  PrimeFinderTest.java

PrimeFinderTest.java is a JUnit 4 test case; you will need to use JUnit in order to test out the sample code. In keeping with Maven 2 naming conventions, the application's source files are in src/main/java, and the JUnit 4 test case that demonstrates the solution is in src/test/java. The key contents of these folders will be covered in the listings shown in the following sections.

Finding those primes

The interface com.javaworld.primefinder.PrimeNumberSearcher defines the contract to which the component must conform. The signature of this contract is given by the method findPrimeNumbers(), which is shown in Listing 1.

Listing 1. The search contract

PrimeNumberSource  findPrimeNumbers(BigInteger lowerBound,
                                    BigInteger upperBound);

Observe that com.javaworld.primefinder.PrimeNumberSource is the interface to which the result handle must conform. It defines a single method, BigInteger nextPrime(), which, when invoked, should return the next element in the search results buffer. If the results buffer has been exhausted, the implementation must return null to indicate that no further results are available. As already mentioned, the implementation of this method must be thread-safe.

Note that the emphasis of this task is on finding the probable primes within the search range; this makes it possible to use the nextProbablePrime() method from the java.math.BigInteger class. You can wrap the call to this method in a static method of the utility class com.javaworld.primefinder.PrimeUtil, an excerpt of which is shown in Listing 2.

Listing 2. A utility method for finding the first prime number within a given range

public static BigInteger findFirstPrime(long lowerBound, long upperBound) 
{
    BigInteger result;
    BigInteger startPos = BigInteger.valueOf(lowerBound);    
    BigInteger nextProbablePrime;
   
    if (startPos.isProbablePrime(.....)) // some reasonable accuracy
        nextProbablePrime = startPos;
    else nextProbablePrime = startPos.nextProbablePrime();
       
    if (nextProbablePrime.longValue() >= upperBound)
        result = null;
    else result = nextProbablePrime;
       
        return result;
   }

Having defined the public interfaces and utilities on which the solution is to be built, you can now move onto the task of detailing it. You'll begin by defining the thread gate implementation, which provides the means of controlling access to the results buffer.

A thread gate implementation

The objective of the thread gate is to ensure that multiple readers can access the prime numbers buffer without preventing the search threads from adding results to it.

A reader thread should be able to pick up any available results from the handle without waiting; but if there are no results, it must queue until at least one is made available. The sample application employs a fair scheme so that results are handed out more or less in the order in which the threads arrive. And yes, I mean it when I say "more or less." The emphasis is not on dispensing results in strict queuing order; rather, threads that request primes around a given interval will all receive their data roughly at the same time -- before the arrival of the next batch of threads.

A real-world analogy that illustrates this scheme is that of the modern coffee shop. The inoffensive way in which coffee orders are "batched" during busy periods is interesting. The attendants at the till take the customer orders and shout them down the line to the baristas manning the espresso machines, who in turn prepare several cups of coffee from the same espresso batch and dispense them to the waiting customers at roughly the same time. Then, of course, they return to the task of making the next batch of coffee for the next batch of customers, and the cycle repeats ad infinitum. By this strange internal scheme, people who arrive at the queue within a given interval tend to get their coffees around the same time -- although not exactly in the order in which the requests were made. Presumably the espresso machines can only prepare so many cups of coffee at any point in time, and it would simply be inefficient or slow to prepare the cups individually.

Returning to the more mundane task of generating and buffering prime numbers, the simple application controls access to the results buffer by a gate that functions in a manner similar to a binary latch: when the gate is open, threads can pass, and when it is closed, threads must queue until it is re-opened. It is more clever than a latch in the sense that it batches waiting threads into generations, which ensures that threads in the same generation all pass through the gate at the same time; threads in an older generation always take priority over those in younger generations. The gate implementation also has an innovative feature that ensures that results can always be written to the results buffer regardless of how many waiting threads there are. If a generic thread gate is like a traffic light, then this would be more akin to a railway crossing in the sense that the train always gets priority -- and for good reason, too.

The gate implementation is contained in the compilation unit com.javaworld.primefinder.ThreadGate, and is detailed in Listing 3.

Listing 3. The gate implementation

package com.javaworld.primefinder;

class ThreadGate
{
    private int waitPosition;
    private int generationSize;
    private int openAttempts;
    private int activeSearchThreads;
    private boolean open;
    
    public ThreadGate(int searchThreadsCount)
        
    public synchronized void await() throws InterruptedException

    public synchronized void close() throws InterruptedException
    
    public synchronized void open()
    
}

To deconstruct this class, begin by taking a look at the class-level fields, of which there are five:

1 2 Page
Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more