|
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.
| 
