com.persistit.util

Class ThreadSequencer

java.lang.Object

com.persistit.util.ThreadSequencer

All Implemented Interfaces:

SequencerConstants

public class ThreadSequencer
extends Object
implements SequencerConstants

Internal utility that allows tests to define execution sequences to confirm specific concurrent execution patterns. Subject code incorporates calls to the static method sequence(int). Each usage in the application code should follow this pattern:

• In the SequencerConstants interface, add a static variable with a name denoting the place in code where sequencing will occur as follows:

   
     final static int SOME_LOCATION = ThreadSequence.allocate("SOME_LOCATION");
   
   

• In the class being tested, add a static import to ThreadSequence.* and then call itself:

   
        sequence(SOME_LOCATION);
   
   

The allocate(String) method simply allocates a unique integer and stores an associated location name. Currently the maximum number of allocated locations is 64.

The sequence(int) method blocks on a Semaphore until a condition for release is recognized. The condition is determined by a schedule that the test class must define.

The entire ThreadSequence mechanism must be enabled via enableSequencer(boolean). By default all calls to sequence(int) invoke an empty method in the NullSequencer subclass, which is fast.

In conjunction with enabling the sequencer, a test must also add one or more sequencing schedules. Each schedule denotes two sets: the "join set" and the "release set". When a thread calls sequence(x), the thread adds location x to a list of blocked locations. It then determines whether that set covers any join set, and if so, it releases all threads in the associated release set. For example, suppose there are three location A, B and C. Consider two sections of code executed by two different threads:

   sequence(A)
   // do this before B
   sequence(C)
 

and

   sequence(B)
   // do this after A
 

A suitable schedule might include the pairs (A, B)->(A) and (B, C)->(B, C). In this example one thread blocks until both sequence(A) and sequence(B) have been called. Then the schedule (A, B)->(A) releases the call to sequence(A) so that the first thread runs. When the first thread calls sequence(C), the schedule (B,C)->(B,C) runs, releasing the second thread's call to sequence(B) and allowing the first thread to continue without blocking.

Follow existing usage in SequencerConstants for defining schedules. Test classes should invoke the static method addSchedules(int[][]) to add schedules defined in SequencerConstants.

Note: a malformed schedule can cause threads blocked within the sequence method to remain blocked forever.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ThreadSequencer.Condition

Field Summary

Fields inherited from interface com.persistit.util.SequencerConstants

ACCUMULATOR_CHECKPOINT_A, ACCUMULATOR_CHECKPOINT_B, ACCUMULATOR_CHECKPOINT_C, ACCUMULATOR_CHECKPOINT_SCHEDULED, COMMIT_FLUSH_A, COMMIT_FLUSH_B, COMMIT_FLUSH_C, COMMIT_FLUSH_SCHEDULE, DEALLOCATE_CHAIN_A, DEALLOCATE_CHAIN_B, DEALLOCATE_CHAIN_C, DEALLOCATE_CHAIN_SCHEDULED, LONG_RECORD_ALLOCATE_A, LONG_RECORD_ALLOCATE_B, LONG_RECORD_ALLOCATE_SCHEDULED, PAGE_MAP_READ_INVALIDATE_A, PAGE_MAP_READ_INVALIDATE_B, PAGE_MAP_READ_INVALIDATE_C, PAGE_MAP_READ_INVALIDATE_SCHEDULE, RECOVERY_PRUNING_A, RECOVERY_PRUNING_B, RECOVERY_PRUNING_SCHEDULE, WRITE_WRITE_STORE_A, WRITE_WRITE_STORE_B, WRITE_WRITE_STORE_C, WRITE_WRITE_STORE_SCHEDULE

Constructor Summary

Constructors

Constructor and Description
ThreadSequencer()

Method Summary

Modifier and Type	Method and Description
static void	addSchedule(int[] awaitLocations, int[] releaseLocations)
static void	addSchedules(int[][] pairs)
static int	allocate(String locationName)
static void	appendHistoryElement(StringBuilder sb, int location)
static int[]	array(int... args)
static String	describeHistory(int[] history)
static String	describePartialOrdering(int[]... args)
static void	disableSequencer() Disable sequencer debugging.
static void	enableSequencer(boolean history) Enable sequencer debugging.
static boolean	historyMeetsPartialOrdering(int[] history, int[]... partialOrderings) Compare a particular sequence history to a collection of required subsets.
static int	out(int location)
static int[]	rawSequenceHistoryCopy()
static void	sequence(int location) Possibly block (only when ThreadSequencer is enabled for tests) until a scheduling condition is met.
static String	sequencerHistory()
static void	setCondition(int location, ThreadSequencer.Condition condition)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ThreadSequencer

public ThreadSequencer()

Method Detail

allocate

public static int allocate(String locationName)

sequence

public static void sequence(int location)

Possibly block (only when ThreadSequencer is enabled for tests) until a scheduling condition is met. This method is called from strategically selected places in the main code to enable concurrency tests. See above for details.

Parameters:

location - integer uniquely identifying a location in code

enableSequencer

public static void enableSequencer(boolean history)

Enable sequencer debugging.

Parameters:

history - indicates whether to maintain a schedule history

disableSequencer

public static void disableSequencer()

Disable sequencer debugging.

addSchedule

public static void addSchedule(int[] awaitLocations,
                               int[] releaseLocations)

addSchedules

public static void addSchedules(int[][] pairs)

setCondition

public static void setCondition(int location,
                                ThreadSequencer.Condition condition)

sequencerHistory

public static String sequencerHistory()

rawSequenceHistoryCopy

public static int[] rawSequenceHistoryCopy()

appendHistoryElement

public static void appendHistoryElement(StringBuilder sb,
                                        int location)

describeHistory

public static String describeHistory(int[] history)

describePartialOrdering

public static String describePartialOrdering(int[]... args)

historyMeetsPartialOrdering

public static boolean historyMeetsPartialOrdering(int[] history,
                                                  int[]... partialOrderings)

Compare a particular sequence history to a collection of required subsets. That is, compare the total ordering of the history as specified by the given ranges where the elements within a given range can be in any order.

For example, a partialOrderings of:

•  { { A_IN, B_IN }, { OUT_B }, { IN_C } }
   

Could be satisfied by either of these history:

•  { A_IN, B_IN, OUT_B, IN_C }
   

•  { B_IN, A_IN, OUT_B, IN_C }
   

But not by any that contains IN_C before OUT_B.

Note: Both parameters will be modified by sorting.

Parameters:

history - An ordered history, e.g. from rawSequenceHistoryCopy().

partialOrderings - Total ordering specification of unordered subsets

Returns:

true if the history fulfilled the required orderings.

array

public static int[] array(int... args)

out

public static int out(int location)