CroftSoft / Library / Tutorials

Concurrent Java Simulations
Using
Three Phase Update

David Wallace Croft

2009 Jul 04 Sat


Abstract

Computer games and simulations have a main loop which is divided into phases such as user input controller processing, updating model state, and rendering the view. Since the states of multiple simulated objects are determined by their interactions, each object must have the opportunity to access the current state of every other object during the update phase. To ensure that the next states of objects are independent of the order in which they are updated, all of these accesses must occur before the state of any one object mutates into its next state. This can be accomplished by dividing the update into two sub-phases, access and mutate, in which no object can mutate its state until every other object has completed accessing shared state. Beyond update order independence, this has an additional benefit in that this can increase the performance of multi-threaded concurrent applications because synchronization is not required to ensure the integrity of shared state. A further increase in performance for concurrent simulations can be had by the introduction of a third sub-phase, digest, in which processing is performed on data copied during the preceding access sub-phase but modifying shared state is delayed until the following mutate sub-phase. This tutorial demonstrates the use of the three sub-phases pattern, Three Phase Update (TPU), using example code in the Java programming language including classes from the Java concurrency library.

Loop Phases

The Model-View-Controller (MVC) pattern organizes objects as being related to maintaining the current state of the program (the model), the rendering of the current state to the user onscreen (the view), and the processing of user inputs from the keyboard and mouse to modify state (the controller). Many programs are event-driven in that no processing occurs until a user input event triggers the controller to update the model which then forces a refresh of the view.

Simulations and animated computer games differ in that they are constantly running whether there are user input events or not. For simulations, the states of multiple interacting simulated objects are updated from one state to the next, generally as fast as the computer will allow. Animated computer games also have simulated objects which must be updated but there is usually a pause after each update since there is no point to animating state onscreen faster than the monitor refresh rate.

These continuously updating programs run in a main loop which is divided into phases paralleling the MVC objects. The first phase polls the controller for user input events. The second phase updates the model, including the state of simulated objects, based on the user input events and the rules of the simulation. The third phase renders the new state of the model to the screen to create the illusion of animation. After an optional pause in which the main loop thread is suspended, the loop then starts again, iterating indefinitely.

Order Independence

One issue that faces the programmer of games and simulations is that updates to the states of simulated objects during the update phase of the main loop must often be independent of the order in which they are processed. For physics-based simulations in which state updates are based on the amount of simulated time passed since the last update iteration, the time delta, this effect can be minimized by choosing a sufficiently small time delta such as one millisecond. The idea here is that small time deltas result in small changes in state from one iteration to the next so that the current and next states are approximately the same. From the viewpoint of other interacting simulated objects which depend on the current state of the observed object to determine their next states, small changes from one update to the next minimize the effects of update order dependence. This of course depends on the time delta and the rate of change so relying upon this is problematic.

Some simulations are not based on a time delta and so update order dependence is always an issue. An example of this is Conway's Game of Life in which the next state of a simulated object, a cell, is dependent on the current state of its adjacent neighboring cells in a grid of cells. For this type of simulation, the time delta is always "1", as in one iteration of the loop. If a programmer knew how simulated objects depended on each other, the updates might be deliberately ordered such that state of objects were always updated before other objects that depended on them for their own state. For simulations like the Game of Life in which there are bi-directional dependencies, there is no order in which this would work.

One solution is to guarantee update order independence by dividing the update phase into two sub-phases, access (read) and mutate (write). During the access sub-phase, all simulated objects access and copy the state of other objects that they need to update their own states. After every simulated object has done so, the access sub-phase ends and the mutate sub-phase begins in which objects use the state copied during the access phase to update their own states. No mutations of shared state are permitted during the access sub-phase and no accesses of shared state are permitted during the following mutate sub-phase.

Thus update order independence is guaranteed. During the update phase, the simulated objects can be updated in random order without adverse effects so long as all accesses are performed before all mutates. The following two Java code samples demonstrate the incorrect and the correct methods of updating state, respectively.

      // Update order dependent (incorrect)

      for ( final Cell  cell : cells )
      {
        cell.access ( );

        cell.mutate ( );
      }
      // Update order independent (correct)

      for ( final Cell  cell : cells )
      {
        cell.access ( );
      }

      for ( final Cell  cell : cells )
      {
        cell.mutate ( );
      }

Concurrent Access and Mutate

I personally avoid multi-threaded concurrent programming in my game programming as much as possible because it can cause significant problems that are difficult to debug. It is often simpler and more productive to run everything in a single thread, especially if the computer the program is running on only has a single central processing unit (CPU). For tasks that take too long to run within the normal timeframe of the main loop such as file or network access, a separate thread can be spawned and the results merged back into the main thread later but this should be the exception, not the rule.

Unlike game programming, I am more inclined to use multiple threads in simulation programming. In game programming, your program must have good performance on a variety of computers, whether single CPU or multi-core. In simulation programming, it is permissible for performance to vary dramatically depending on the hardware since real-time animation is not the goal. The other difference is that games usually have many less simulated objects to update compared to simulations. For example, a small 30 by 30 grid of cells in the Game of Life requires 900 cells to be updated with each game loop. A biologically realistic neuronal network simulation is usually limited in the number of objects it can simulate due to processing time constraints. On a computer with two processing cores, being able to update half of the simulated objects on one core and the other half on the other can nearly double your performance.

Usually with multi-threaded concurrent programming you have to synchronize access to shared state so that it is not being accessed (read) by one thread at the same time as it is being mutated (written) by another thread. Not doing so can mean that the accessing thread might retrieve inconsistent state such as a point in space in which the X coordinate is at the next state location but the Y coordinate is still at the current state location. In Java, this means marking both the accessor (getter) and mutator (setter) methods of an object as synchronized. Synchronization can be a performance hit as it blocks one thread from proceeding while it waits on the other so it should be avoided if convenient.

Fortunately dividing the update phase into separate access and mutate sub-phases means that there is no possibility for data to be retrieved in an inconsistent state because simultaneous accesses and mutations are not allowed even without synchronization. If two threads are running, each processes the access sub-phase simultaneously. The first thread to finish blocks and waits until the other thread is finished with the access sub-phase and then they both proceed with the mutate phase.

In Java, this means that accessor and mutator methods do not need to be synchronized. Non-final instance variables do need to be marked volatile so that they are accessible to other threads in the heap instead of tucked away in registers but this is an improvement over mandatory synchronization. The only blocking required is at the end of a sub-phase where the faster threads must wait on the slowest thread to finish before proceeding. This blocking can be accomplished with the use of two instances of the Java class CountDownLatch from the package java.util.concurrent.

The first CountDownLatch is used to signal the transition from the access sub-phase to the mutate sub-phase. A second CountDownLatch is used to signal when the mutate sub-phase is completed at which point the main loop thread can then continue with all operations as single threaded again. One way to structure a simulation which minimizes complexity but gain the benefits of multi-core processing is to have all of the phases of the main loop running within a single thread except for the update phase which rejoins the main loop thread upon completion.

Another Java class from package java.util.concurrent that can be used in this situation is ExecutorService. If you simply divide up the simulated objects between the two threads evenly, one thread might take much longer to finish than the other because by chance it was assigned the simulated objects that take longer to process. You then have the much faster thread blocking while it waits on the much slower thread to finish a sub-phase. If you instead put all of the simulated objects in a queue and have threads process them as ready, you can balance out differences in processing time for each simulated object. As an exaggerated example, imagine that one simulated object takes as much time to process as the 899 others. While one thread is stuck on the one object, another thread can process all of the others in about the same time. The ExecutorService class can assign threads from a thread pool to process the simulated objects as the threads become available.

Concurrent Digest

A further performance increase can be reached by introducing an intermediate sub-phase, digest, which comes between the access and mutate sub-phases. In the digest sub-phase, neither shared state access nor shared state mutate is permitted. Since shared state is not involved in any way, the digest sub-phase of one thread can partially overlap the access and mutate sub-phases of other threads without adverse effect.

With all three sub-phases of the Three Phase Update pattern described, access, digest, and mutate, I can now introduce a Java interface to be implemented by simulated objects:

    /***********************************************************************
    * Three phase update.
    *
    * @since
    *   2009-05-10
    * @author
    *   David Wallace Croft
    ***********************************************************************/

    public interface  ThreePhaseUpdate
    ////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////
    {

    void  access ( );

    void  digest ( );

    void  mutate ( );

    ////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////
    }

In a single threaded application, using three sub-phases is equivalent to using just two since the content of the digest() method can be included in either access() or mutate() methods without impacting update order independence. In fact, in a single-threaded application, the following code samples demonstrating different methods of processing the update phase are all equivalently correct:

    public static void  update1 ( )
    ////////////////////////////////////////////////////////////////////////
    {
      [...]

      for ( final ThreePhaseUpdate  threePhaseUpdate : threePhaseUpdates )
      {
        threePhaseUpdate.access ( );
      }

      for ( final ThreePhaseUpdate  threePhaseUpdate : threePhaseUpdates )
      {
        threePhaseUpdate.digest ( );
      }

      for ( final ThreePhaseUpdate  threePhaseUpdate : threePhaseUpdates )
      {
        threePhaseUpdate.mutate ( );
      }
    }

    public static void  update2 ( )
    ////////////////////////////////////////////////////////////////////////
    {
      [...]

      for ( final ThreePhaseUpdate  threePhaseUpdate : threePhaseUpdates )
      {
        threePhaseUpdate.access ( );

        threePhaseUpdate.digest ( );
      }

      for ( final ThreePhaseUpdate  threePhaseUpdate : threePhaseUpdates )
      {
        threePhaseUpdate.mutate ( );
      }
    }

    public static void  update3 ( )
    ////////////////////////////////////////////////////////////////////////
    {
      [...]

      for ( final ThreePhaseUpdate  threePhaseUpdate : threePhaseUpdates )
      {
        threePhaseUpdate.access ( );
      }

      for ( final ThreePhaseUpdate  threePhaseUpdate : threePhaseUpdates )
      {
        threePhaseUpdate.digest ( );

        threePhaseUpdate.mutate ( );
      }
    }

In multi-threaded concurrent applications, however, breaking out the digest sub-phase distinct from the other two sub-phases can make a difference in performance. When faster threads finish their access sub-phase, they can proceed to the digest sub-phase and perform some work instead of simply blocking while they wait on the slowest thread to finish the access sub-phase. The slowest thread can signal to the other threads they can proceed to the mutate sub-phase when the slowest thread enters the digest sub-phase instead of making the other threads block until the slowest thread has performed both access and digest processing.

To reiterate, this works because the digest sub-phase of one thread is permitted to overlap the access or mutate sub-phases of other threads since digest does not require any access of or mutation to shared state. In no circumstance, though, can one thread be in the access sub-phase while another is in the mutate-subphase and vice versa. Either digest overlaps access or mutate but not both. Again, this is because no thread may enter the mutate sub-phase until all threads have completed the access sub-phase.

Demonstration Code

This demonstration code shows how to use Three Phase Update in a concurrent Java simulation. The code is described in more detail after being initially presented in its entirety.

    package com.croftsoft.apps.tpu;

    import java.util.*;
    import java.util.concurrent.*;

    /***********************************************************************
    * Demonstration of using ThreePhaseUpdate multi-threaded.
    *
    * @since
    *   2009-06-05
    * @author
    *   David Wallace Croft
    ***********************************************************************/

    public final class  ThreePhaseUpdateDemo2
    ////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////
    {

    private static final int
      GRID_WIDTH  = 2,
      GRID_HEIGHT = 2;

    ////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////

    public static void  main ( final String [ ]  args )
      throws Exception
    ////////////////////////////////////////////////////////////////////////
    {
      final Random  random = new Random ( );

      final ThreePhaseUpdateGrid  grid
        = new ThreePhaseUpdateGrid ( random, GRID_WIDTH, GRID_HEIGHT );

      final ThreePhaseUpdate [ ]  threePhaseUpdates = grid.getCells ( );

      System.out.println ( "runnerCount = " + threePhaseUpdates.length );

      final int  threadCount
        = Runtime.getRuntime ( ).availableProcessors ( );

      System.out.println ( "threadCount = " + threadCount );

      final ExecutorService  executorService
        = Executors.newFixedThreadPool ( threadCount );

      final BlockingQueue<Runnable>  runnableBlockingQueue
        = new LinkedBlockingQueue<Runnable> ( );

      final long  startTime = System.currentTimeMillis ( );

      for ( int  i = 0; i < 3; i++ )
      {
        update (
          threePhaseUpdates,
          executorService,
          runnableBlockingQueue );

        System.out.println ( "update complete" );
      }

      System.out.println (
        "elapsed time:  " + ( System.currentTimeMillis ( ) - startTime ) );

      executorService.shutdown ( );
    }

    public static void  update (
      final ThreePhaseUpdate [ ]     threePhaseUpdates,
      final ExecutorService          executorService,
      final BlockingQueue<Runnable>  runnableBlockingQueue )
      throws Exception
    ////////////////////////////////////////////////////////////////////////
    {
      final int  runnerCount = threePhaseUpdates.length;

      final CountDownLatch
        countDownLatch1 = new CountDownLatch ( runnerCount ),
        countDownLatch2 = new CountDownLatch ( runnerCount );

      for ( int  i = 0; i < runnerCount; i++ )
      {
        final ThreePhaseUpdate  threePhaseUpdate = threePhaseUpdates [ i ];

        executorService.execute (
          new Runnable ( )
          {
            @Override
            public void  run ( )
            {
              try
              {
                threePhaseUpdate.access ( );
              }
              finally
              {
                countDownLatch1.countDown ( );

                try
                {
                  threePhaseUpdate.digest ( );
                }
                finally
                {
                  runnableBlockingQueue.add (
                    new Runnable ( )
                    {
                      @Override
                      public void  run ( )
                      {
                        try
                        {
                          threePhaseUpdate.mutate ( );
                        }
                        finally
                        {
                          countDownLatch2.countDown ( );
                        }
                      }
                    } );
                }
              }
            }
          } );
      }

      countDownLatch1.await ( );

      int  mutateCount = 0;

      while ( mutateCount < runnerCount )
      {
        executorService.execute ( runnableBlockingQueue.take ( ) );

        mutateCount++;
      }

      countDownLatch2.await ( );
    }

    ////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////
    }

The following is a breakdown of the preceding code.

    private static final int
      GRID_WIDTH  = 2,
      GRID_HEIGHT = 2;

This demonstration runs a Game of Life simulation. To make demonstrating its operation simpler, I only used a 2 by 2 grid of cells for a total of four simulated objects.

      final Random  random = new Random ( );

      final ThreePhaseUpdateGrid  grid
        = new ThreePhaseUpdateGrid ( random, GRID_WIDTH, GRID_HEIGHT );

      final ThreePhaseUpdate [ ]  threePhaseUpdates = grid.getCells ( );

The grid contains four simulated objects, each of which implements interface ThreePhaseUpdate which was introduced previously. The random number generator is used to insert random delay times when the access(), digest(), and mutate() methods are called on the simulated objects in order to demonstrate correct behavior in all circumstances of timing.

      System.out.println ( "runnerCount = " + threePhaseUpdates.length );

      final int  threadCount
        = Runtime.getRuntime ( ).availableProcessors ( );

      System.out.println ( "threadCount = " + threadCount );

      final ExecutorService  executorService
        = Executors.newFixedThreadPool ( threadCount );

      final BlockingQueue<Runnable>  runnableBlockingQueue
        = new LinkedBlockingQueue<Runnable> ( );

Since each simulated object will be wrapped in a Runnable which will be passed to an ExecutorService to process, the runnerCount shows how many tasks are to be processed as distinguished from the number of threads available to process them. In this case, I set the number of threads equal to the number of processors available on the computer. A BlockingQueue is created here so that it can be reused each time the update() method is called.

      final long  startTime = System.currentTimeMillis ( );

      for ( int  i = 0; i < 3; i++ )
      {
        update (
          threePhaseUpdates,
          executorService,
          runnableBlockingQueue );

        System.out.println ( "update complete" );
      }

      System.out.println (
        "elapsed time:  " + ( System.currentTimeMillis ( ) - startTime ) );

      executorService.shutdown ( );

The update() method is called three times as an example of calling it repeatedly as part of the update phase within the main loop of a simulation. The time it takes to complete these 3 loops is measured so that performance can be compared between multi-threaded operation on a multi-core computer to single-threaded operation. When the main loop exits, the ExecutorService must be shutdown for the program to complete.

    public static void  update (
      final ThreePhaseUpdate [ ]     threePhaseUpdates,
      final ExecutorService          executorService,
      final BlockingQueue<Runnable>  runnableBlockingQueue )
      throws Exception
    ////////////////////////////////////////////////////////////////////////
    {

The update() method is static to show how it could be included within a reusable static method library.

      final int  runnerCount = threePhaseUpdates.length;

      final CountDownLatch
        countDownLatch1 = new CountDownLatch ( runnerCount ),
        countDownLatch2 = new CountDownLatch ( runnerCount );

The first CountDownLatch is used to signal when the access sub-phase is completed. The second CountDownLatch signals when the mutate sub-phase is completed. They count how many simulated objects have been processed in each phase, the runnerCount.

      for ( int  i = 0; i < runnerCount; i++ )
      {
        final ThreePhaseUpdate  threePhaseUpdate = threePhaseUpdates [ i ];

        executorService.execute (
          new Runnable ( )
          {

For each simulated object that implements interface ThreePhaseUpdate, the ExecutorService is passed a new Runnable to process the simulated object.

            @Override
            public void  run ( )
            {
              try
              {
                threePhaseUpdate.access ( );
              }
              finally
              {
                countDownLatch1.countDown ( );

When processed, the Runnable will first call the access() method of the simulated object. Regardless of whether it completes successfully or throws an Exception, it will then decrement the first CountDownLatch. The first CountDownLatch is used to signal when the access sub-phase is completed.

                try
                {
                  threePhaseUpdate.digest ( );
                }
                finally
                {
                  runnableBlockingQueue.add (
                    new Runnable ( )
                    {

Without waiting, it then proceeds to call the digest() method of the simulated object. Regardless of whether it completes successfully or throws an Exception, it will then create a new Runnable add it to a BlockingQueue to be processed later.

                      @Override
                      public void  run ( )
                      {
                        try
                        {
                          threePhaseUpdate.mutate ( );
                        }
                        finally
                        {
                          countDownLatch2.countDown ( );
                        }
                      }
                    } );
                }
              }
            }
          } );
      }

This new Runnable will call the mutate() method of the simulated object and then decrement the second CountDownLatch. The second CountDownLatch is used to signal when the mutate sub-phase is completed.

Note that the access() and digest() methods are processed as part of one Runnable and the mutate() method is processed in another Runnable, possibly by a different thread. For this reason, all of your non-final instance variables in your simulated objects should be marked volatile even if they are not accessible to other objects via an accessor (getter) method.

      countDownLatch1.await ( );

      int  mutateCount = 0;

      while ( mutateCount < runnerCount )
      {
        executorService.execute ( runnableBlockingQueue.take ( ) );

        mutateCount++;
      }

      countDownLatch2.await ( );
    }

After each simulated object has been wrapped in a Runnable and passed to the ExecutorService, the main thread then waits until the access sub-phase is completed as indicated by the first CountDownLatch. The main thread then enters the mutate sub-phase by pulling simulated objects that are ready to have their mutate() methods called off of the BlockingQueue and passing them back to the ExecutorService. Not all of the simulated objects will become available immediately as some will still be in the digest sub-phase. Eventually all of the simulated objects will be in the mutate sub-phase and the main thread will wait on the second CountDownLatch for the end of the mutate sub-phase. This is also the end of the update phase and the update() method returns.

The following is example code for a simulated object. It is not described in detail but notice that it adheres to the following rules:

  • The class implements interface ThreePhaseUpdate.

  • All non-final instance variables are marked volatile.

  • None of the methods are synchronized.

  • The access() method does not mutate shared state.

  • The mutate() method does not access shared state.

  • The digest() method does not access or mutate shared state.

    package com.croftsoft.apps.tpu;

    import java.util.*;
    import java.util.concurrent.*;

    /***********************************************************************
    * Three phase update demo implementation.
    *
    * @since
    *   2009-05-10
    * @author
    *   David Wallace Croft
    ***********************************************************************/

    public final class  ThreePhaseUpdateCell
      implements ThreePhaseUpdate
    ////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////
    {

    private final String  id;

    private final Random  random;

    // All non-final instance variables must be volatile.

    /** Set after construction and referenced during access(). */
    private volatile ThreePhaseUpdateCell [ ]  adjacentCells;

    /** The current state. */
    private volatile boolean  alive;

    /** Calculated during access() and used in digest(). */
    private volatile int  adjacentCellsAliveCount;

    /** This is the next state which is set when mutate() is called. */
    private volatile boolean  nextAlive;

    ////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////

    public  ThreePhaseUpdateCell (
      final String  id,
      final Random  random )
    ////////////////////////////////////////////////////////////////////////
    {
      this.id     = id;

      this.random = random;
    }

    ////////////////////////////////////////////////////////////////////////
    // accessor methods
    ////////////////////////////////////////////////////////////////////////

    public String   getId   ( ) { return id;    }

    public boolean  isAlive ( ) { return alive; }

    ////////////////////////////////////////////////////////////////////////
    // mutator methods
    ////////////////////////////////////////////////////////////////////////

    public void  setAlive ( final boolean  alive )
    ////////////////////////////////////////////////////////////////////////
    {
      this.alive = alive;
    }

    public void  setAdjacentCells (
      final ThreePhaseUpdateCell [ ]  adjacentCells )
    ////////////////////////////////////////////////////////////////////////
    {
      this.adjacentCells = adjacentCells;
    }

    ////////////////////////////////////////////////////////////////////////
    // interface ThreePhaseUpdate methods
    ////////////////////////////////////////////////////////////////////////

    @Override
    public void  access ( )
    ////////////////////////////////////////////////////////////////////////
    {
      System.out.println (
        id + ":  access begin " + Thread.currentThread ( ) );

      adjacentCellsAliveCount = 0;

      for ( final ThreePhaseUpdateCell  adjacentCell : adjacentCells )
      {
        if ( adjacentCell.isAlive ( ) )
        {
          adjacentCellsAliveCount++;
        }
      }

      randomDelay ( 1 );

      System.out.println (
        id + ":  access done  " + Thread.currentThread ( ) );
    }

    @Override
    public void  digest ( )
    ////////////////////////////////////////////////////////////////////////
    {
      System.out.println (
        id + ":  digest begin " + Thread.currentThread ( ) );

      nextAlive = alive;

      if ( alive )
      {
        if ( ( adjacentCellsAliveCount < 2 )
          || ( adjacentCellsAliveCount > 3 ) )
        {
          nextAlive = false;
        }
      }
      else
      {
        if ( adjacentCellsAliveCount == 3 )
        {
          nextAlive = true;
        }
      }

      randomDelay ( 1000 );

      System.out.println (
        id + ":  digest done  " + Thread.currentThread ( ) );
    }

    @Override
    public void  mutate ( )
    ////////////////////////////////////////////////////////////////////////
    {
      System.out.println (
        id + ":  mutate begin " + Thread.currentThread ( ) );

      alive = nextAlive;

      randomDelay ( 1 );

      System.out.println (
        id + ":  mutate done  " + Thread.currentThread ( ) );
    }

    ////////////////////////////////////////////////////////////////////////
    // private methods
    ////////////////////////////////////////////////////////////////////////

    private void  randomDelay ( final int  maxDelay )
    ////////////////////////////////////////////////////////////////////////
    {
      try
      {
        TimeUnit.MILLISECONDS.sleep ( random.nextInt ( maxDelay ) );
      }
      catch ( final InterruptedException  ie )
      {
        // ignore
      }
    }

    ////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////
    }

The following is sample output from the simulation. Each of the simulated objects is assigned a unique identifier, 0 to 3, so that you can see when each entered and exited its access(), digest(), and mutate() methods. The thread name follows so you can see what thread was processing it at that moment. The "update complete" indicates one iteration of the three times that the update() method was called as part of the main loop.

The time for each simulated object to complete its digest() method has been deliberately randomized using a randomly generated delay but the maximum possible delay has been set to a large value of up to one second to demonstrate how the sub-phases overlap. In the sample output, note how the first mutate() method is never called until after the last access() method is done but how the first mutate() method can begin before the last digest() method completes.

runnerCount = 4
threadCount = 2
0:  access begin Thread[pool-1-thread-1,5,main]
0:  access done  Thread[pool-1-thread-1,5,main]
0:  digest begin Thread[pool-1-thread-1,5,main]
1:  access begin Thread[pool-1-thread-2,5,main]
1:  access done  Thread[pool-1-thread-2,5,main]
1:  digest begin Thread[pool-1-thread-2,5,main]
0:  digest done  Thread[pool-1-thread-1,5,main]
2:  access begin Thread[pool-1-thread-1,5,main]
2:  access done  Thread[pool-1-thread-1,5,main]
2:  digest begin Thread[pool-1-thread-1,5,main]
2:  digest done  Thread[pool-1-thread-1,5,main]
3:  access begin Thread[pool-1-thread-1,5,main]
3:  access done  Thread[pool-1-thread-1,5,main]
3:  digest begin Thread[pool-1-thread-1,5,main]
1:  digest done  Thread[pool-1-thread-2,5,main]
0:  mutate begin Thread[pool-1-thread-2,5,main]
0:  mutate done  Thread[pool-1-thread-2,5,main]
2:  mutate begin Thread[pool-1-thread-2,5,main]
2:  mutate done  Thread[pool-1-thread-2,5,main]
1:  mutate begin Thread[pool-1-thread-2,5,main]
1:  mutate done  Thread[pool-1-thread-2,5,main]
3:  digest done  Thread[pool-1-thread-1,5,main]
3:  mutate begin Thread[pool-1-thread-2,5,main]
3:  mutate done  Thread[pool-1-thread-2,5,main]
update complete
0:  access begin Thread[pool-1-thread-1,5,main]
1:  access begin Thread[pool-1-thread-2,5,main]
0:  access done  Thread[pool-1-thread-1,5,main]
1:  access done  Thread[pool-1-thread-2,5,main]
0:  digest begin Thread[pool-1-thread-1,5,main]
1:  digest begin Thread[pool-1-thread-2,5,main]
0:  digest done  Thread[pool-1-thread-1,5,main]
2:  access begin Thread[pool-1-thread-1,5,main]
2:  access done  Thread[pool-1-thread-1,5,main]
2:  digest begin Thread[pool-1-thread-1,5,main]
1:  digest done  Thread[pool-1-thread-2,5,main]
3:  access begin Thread[pool-1-thread-2,5,main]
3:  access done  Thread[pool-1-thread-2,5,main]
3:  digest begin Thread[pool-1-thread-2,5,main]
2:  digest done  Thread[pool-1-thread-1,5,main]
0:  mutate begin Thread[pool-1-thread-1,5,main]
0:  mutate done  Thread[pool-1-thread-1,5,main]
1:  mutate begin Thread[pool-1-thread-1,5,main]
1:  mutate done  Thread[pool-1-thread-1,5,main]
2:  mutate begin Thread[pool-1-thread-1,5,main]
2:  mutate done  Thread[pool-1-thread-1,5,main]
3:  digest done  Thread[pool-1-thread-2,5,main]
3:  mutate begin Thread[pool-1-thread-1,5,main]
3:  mutate done  Thread[pool-1-thread-1,5,main]
update complete
0:  access begin Thread[pool-1-thread-2,5,main]
1:  access begin Thread[pool-1-thread-1,5,main]
0:  access done  Thread[pool-1-thread-2,5,main]
1:  access done  Thread[pool-1-thread-1,5,main]
0:  digest begin Thread[pool-1-thread-2,5,main]
1:  digest begin Thread[pool-1-thread-1,5,main]
0:  digest done  Thread[pool-1-thread-2,5,main]
2:  access begin Thread[pool-1-thread-2,5,main]
2:  access done  Thread[pool-1-thread-2,5,main]
2:  digest begin Thread[pool-1-thread-2,5,main]
2:  digest done  Thread[pool-1-thread-2,5,main]
3:  access begin Thread[pool-1-thread-2,5,main]
3:  access done  Thread[pool-1-thread-2,5,main]
3:  digest begin Thread[pool-1-thread-2,5,main]
1:  digest done  Thread[pool-1-thread-1,5,main]
0:  mutate begin Thread[pool-1-thread-1,5,main]
0:  mutate done  Thread[pool-1-thread-1,5,main]
2:  mutate begin Thread[pool-1-thread-1,5,main]
2:  mutate done  Thread[pool-1-thread-1,5,main]
1:  mutate begin Thread[pool-1-thread-1,5,main]
1:  mutate done  Thread[pool-1-thread-1,5,main]
3:  digest done  Thread[pool-1-thread-2,5,main]
3:  mutate begin Thread[pool-1-thread-1,5,main]
3:  mutate done  Thread[pool-1-thread-1,5,main]
update complete
elapsed time:  3599

The elapsed time for this particular run is 3.599 seconds on a computer with two cores. If I force the thread count to one and run it again so that it runs as a single-threaded application, I get 6.601 seconds. There will some variation due to the randomly generated delays but on average I expect single-threaded operation to take almost twice as long as multi-threaded, two-core operation.

Source Code

You can download the source code used in this demonstration as a zip file: croftsoft-tpu.zip. You may reuse this source code under the terms of the Open Source GNU Lesser General Public License version 3.0 (LGPLv3). If you modify the code for reuse, please link back to this tutorial by including the URL for this webpage in your javadoc comments.

Recommended Book

The Three Phase Update (TPU) pattern is something that I came up with on my own as part of my doctoral studies in Computational Neuroethology but I learned how to use the Java concurrency classes from one particular book. I highly recommend that you read Java Concurrency in Practice by Goetz, et al. before you begin writing multi-threaded Java applications. By explaining Java concurrency, it can help you understand the advantages of the TPU pattern in more detail. I plan to re-read it the next time I write a multi-threaded application.

 
 
 
CroftSoft
 
 
About
Library
-Books
-Code
-Courses
-Links
-Media
-Software
-Tutorials
People
Portfolio
Update
 
 
Google
CroftSoft Web

 

Creative Commons License
© 2009 CroftSoft Inc.
You may copy this webpage under the terms of the
Creative Commons Attribution License.