Package org.HdrHistogram

Class WriterReaderPhaser

java.lang.Object

org.HdrHistogram.WriterReaderPhaser

public class WriterReaderPhaser
extends Object

WriterReaderPhaser provides an asymmetric means for synchronizing the execution of wait-free "writer" critical sections against a "reader phase flip" that needs to make sure no writer critical sections that were active at the beginning of the flip are still active after the flip is done. Multiple writers and multiple readers are supported.

Using a WriterReaderPhaser for coordination, writers can continously perform wait-free/lock-free updates to common data structures, while readers can get hold of atomic and inactive snapshots without stalling writers.

While a WriterReaderPhaser can be useful in multiple scenarios, a specific and common use case is that of safely managing "double buffered" data stream access in which writers can proceed without being blocked, while readers gain access to stable and unchanging buffer samples. WriterReaderPhaser "writers" are wait free (on architectures that support wait free atomic increment operations), "readers" block for other "readers", and "readers" are only blocked by "writers" whose critical section was entered before the reader's flipPhase() attempt.

Assumptions and Guarantees

When used to protect an actively recording data structure, the assumptions on how readers and writers act are:

1. There are two sets of data structures ("active" and "inactive")
2. Writing is done to the perceived active version (as perceived by the writer), and only within critical sections delineated by writerCriticalSectionEnter() and writerCriticalSectionExit().
3. Only readers switch the perceived roles of the active and inactive data structures. They do so only while under readerLock() protection and only before calling flipPhase().
4. Writers do not remain in their critical sections indefinitely.
5. Only writers perform writerCriticalSectionEnter() and writerCriticalSectionExit().
6. Readers do not hold onto readerLock indefinitely.
7. Only readers perform readerLock() and readerUnlock().
8. Only readers perform flipPhase() operations, and only while holding the readerLock.

When the above assumptions are met, WriterReaderPhaser guarantees that the inactive data structures are not being modified by any writers while being read while under readerLock() protection after a flipPhase()() operation.

The following progress guarantees are provided to writers and readers that adhere to the above stated assumptions:

1. Writers operations (writerCriticalSectionEnter and writerCriticalSectionExit) are wait free on architectures that support wait-free atomic increment operations (they remain lock-free [but not wait-free] on architectures that do not support wait-free atomic increment operations)
2. flipPhase() operations are guaranteed to make forward progress, and will only be blocked by writers whose critical sections were entered prior to the start of the reader's flipPhase operation, and have not yet exited their critical sections.
3. readerLock() only blocks for other readers that are holding the readerLock.

Example use

Imagine a simple use case where a histogram (which is basically a large set of rapidly updated counters) is being modified by writers, and a reader needs to gain access to stable interval samples of the histogram for reporting or other analysis purposes.

         final WriterReaderPhaser recordingPhaser = new WriterReaderPhaser();

         volatile Histogram activeHistogram;
         Histogram inactiveHistogram;
         ...
 

A writer may record values the histogram:

         // Wait-free recording:
         long criticalValueAtEnter = recordingPhaser.writerCriticalSectionEnter();
         try {
             activeHistogram.recordValue(value);
         } finally {
             recordingPhaser.writerCriticalSectionExit(criticalValueAtEnter);
         }
 

A reader gains access to a stable histogram of values recorded during an interval, and reports on it:

         try {
             recordingPhaser.readerLock();

             inactiveHistogram.reset();

             // Swap active and inactive histograms:
             final Histogram tempHistogram = inactiveHistogram;
             inactiveHistogram = activeHistogram;
             activeHistogram = tempHistogram;

             recordingPhaser.flipPhase();
             // At this point, inactiveHistogram content is guaranteed to be stable

             logHistogram(inactiveHistogram);

         } finally {
             recordingPhaser.readerUnlock();
         }
 

Constructor Summary

Constructors

Constructor	Description
WriterReaderPhaser()

Method Summary

Modifier and Type	Method	Description
void	flipPhase()	Flip a phase in the WriterReaderPhaser instance, flipPhase() can only be called while holding the readerLock.
void	flipPhase(long yieldTimeNsec)	Flip a phase in the WriterReaderPhaser instance, flipPhase() can only be called while holding the readerLock.
void	readerLock()	Enter to a critical section containing a read operation (mutually excludes against other readerLock calls).
void	readerUnlock()	Exit from a critical section containing a read operation (relinquishes mutual exclusion against other readerLock calls).
long	writerCriticalSectionEnter()	Indicate entry to a critical section containing a write operation.
void	writerCriticalSectionExit(long criticalValueAtEnter)	Indicate exit from a critical section containing a write operation.

Methods inherited from class java.lang.Object

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

Constructor Detail

WriterReaderPhaser

public WriterReaderPhaser()

Method Detail

writerCriticalSectionEnter

public long writerCriticalSectionEnter()

Indicate entry to a critical section containing a write operation.

This call is wait-free on architectures that support wait free atomic increment operations, and is lock-free on architectures that do not.

writerCriticalSectionEnter() must be matched with a subsequent writerCriticalSectionExit(long) in order for CriticalSectionPhaser synchronization to function properly.

Returns:

an (opaque) value associated with the critical section entry, which MUST be provided to the matching writerCriticalSectionExit(long) call.

writerCriticalSectionExit

public void writerCriticalSectionExit(long criticalValueAtEnter)

Indicate exit from a critical section containing a write operation.

This call is wait-free on architectures that support wait free atomic increment operations, and is lock-free on architectures that do not.

writerCriticalSectionExit(long) must be matched with a preceding writerCriticalSectionEnter() call, and must be provided with the matching writerCriticalSectionEnter() call's return value, in order for CriticalSectionPhaser synchronization to function properly.

Parameters:

criticalValueAtEnter - the (opaque) value returned from the matching writerCriticalSectionEnter() call.

readerLock

public void readerLock()

Enter to a critical section containing a read operation (mutually excludes against other readerLock calls).

readerLock DOES NOT provide synchronization against writerCriticalSectionEnter() calls. Use flipPhase() to synchronize reads against writers.

readerUnlock

public void readerUnlock()

Exit from a critical section containing a read operation (relinquishes mutual exclusion against other readerLock calls).

flipPhase

public void flipPhase(long yieldTimeNsec)

Flip a phase in the WriterReaderPhaser instance, flipPhase() can only be called while holding the readerLock. flipPhase() will return only after all writer critical sections (protected by writerCriticalSectionEnter and writerCriticalSectionEnter) that may have been in flight when the flipPhase() call were made had completed.

No actual writer critical section activity is required for flipPhase() to succeed.

However, flipPhase() is lock-free with respect to calls to writerCriticalSectionEnter() and writerCriticalSectionExit(). It may spin-wait or for active writer critical section code to complete.

Parameters:

yieldTimeNsec - The amount of time (in nanoseconds) to sleep in each yield if yield loop is needed.

flipPhase

public void flipPhase()

Flip a phase in the WriterReaderPhaser instance, flipPhase() can only be called while holding the readerLock. flipPhase() will return only after all writer critical sections (protected by writerCriticalSectionEnter and writerCriticalSectionEnter) that may have been in flight when the flipPhase() call were made had completed.

No actual writer critical section activity is required for flipPhase() to succeed.

However, flipPhase() is lock-free with respect to calls to writerCriticalSectionEnter() and writerCriticalSectionExit(). It may spin-wait or for active writer critical section code to complete.