public abstract class Striped<L>
extends java.lang.Object
Lock/Semaphore/ReadWriteLock
. This offers the underlying lock striping similar
to that of ConcurrentHashMap
in a reusable form, and extends it for semaphores and
read-write locks. Conceptually, lock striping is the technique of dividing a lock into many
stripes, increasing the granularity of a single lock and allowing independent operations
to lock different stripes and proceed concurrently, instead of creating contention for a single
lock.
The guarantee provided by this class is that equal keys lead to the same lock (or semaphore),
i.e. if (key1.equals(key2))
then striped.get(key1) == striped.get(key2)
(assuming
Object.hashCode()
is correctly implemented for the keys). Note that if key1
is
not equal to key2
, it is not guaranteed that striped.get(key1) != striped.get(key2)
; the elements might nevertheless be mapped to the same
lock. The lower the number of stripes, the higher the probability of this happening.
There are three flavors of this class: Striped<Lock>
, Striped<Semaphore>
, and
Striped<ReadWriteLock>
. For each type, two implementations are offered: strong and weak Striped<Lock>
, strong and weak Striped<Semaphore>
, and strong and weak Striped<ReadWriteLock>
. Strong means that all
stripes (locks/semaphores) are initialized eagerly, and are not reclaimed unless Striped
itself is reclaimable. Weak means that locks/semaphores are created lazily, and they are
allowed to be reclaimed if nobody is holding on to them. This is useful, for example, if one
wants to create a Striped<Lock>
of many locks, but worries that in most cases only a
small portion of these would be in use.
Prior to this class, one might be tempted to use Map<K, Lock>
, where K
represents the task. This maximizes concurrency by having each unique key mapped to a unique
lock, but also maximizes memory footprint. On the other extreme, one could use a single lock for
all tasks, which minimizes memory footprint but also minimizes concurrency. Instead of choosing
either of these extremes, Striped
allows the user to trade between required concurrency
and memory footprint. For example, if a set of tasks are CPU-bound, one could easily create a
very compact Striped<Lock>
of availableProcessors() * 4
stripes, instead of
possibly thousands of locks which could be created in a Map<K, Lock>
structure.
Modifier and Type | Class and Description |
---|---|
private static class |
Striped.CompactStriped<L>
Implementation of Striped where 2^k stripes are represented as an array of the same length,
eagerly initialized.
|
(package private) static class |
Striped.LargeLazyStriped<L>
Implementation of Striped where up to 2^k stripes can be represented, using a ConcurrentMap
where the key domain is [0..2^k).
|
private static class |
Striped.PaddedLock |
private static class |
Striped.PaddedSemaphore |
private static class |
Striped.PowerOfTwoStriped<L> |
(package private) static class |
Striped.SmallLazyStriped<L>
Implementation of Striped where up to 2^k stripes can be represented, using an
AtomicReferenceArray of size 2^k.
|
private static class |
Striped.WeakSafeCondition
Condition object that ensures a strong reference is retained to a specified object.
|
private static class |
Striped.WeakSafeLock
Lock object that ensures a strong reference is retained to a specified object.
|
private static class |
Striped.WeakSafeReadWriteLock
ReadWriteLock implementation whose read and write locks retain a reference back to this lock.
|
Modifier and Type | Field and Description |
---|---|
private static int |
ALL_SET
A bit mask were all bits are set.
|
private static int |
LARGE_LAZY_CUTOFF
If there are at least this many stripes, we assume the memory usage of a ConcurrentMap will be
smaller than a large array.
|
private static Supplier<java.util.concurrent.locks.ReadWriteLock> |
READ_WRITE_LOCK_SUPPLIER |
private static Supplier<java.util.concurrent.locks.ReadWriteLock> |
WEAK_SAFE_READ_WRITE_LOCK_SUPPLIER |
Modifier | Constructor and Description |
---|---|
private |
Striped() |
Modifier and Type | Method and Description |
---|---|
java.lang.Iterable<L> |
bulkGet(java.lang.Iterable<?> keys)
Returns the stripes that correspond to the passed objects, in ascending (as per
getAt(int) ) order. |
private static int |
ceilToPowerOfTwo(int x) |
(package private) static <L> Striped<L> |
custom(int stripes,
Supplier<L> supplier)
Creates a
Striped<L> with eagerly initialized, strongly referenced locks. |
abstract L |
get(java.lang.Object key)
Returns the stripe that corresponds to the passed key.
|
abstract L |
getAt(int index)
Returns the stripe at the specified index.
|
(package private) abstract int |
indexFor(java.lang.Object key)
Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key).
|
private static <L> Striped<L> |
lazy(int stripes,
Supplier<L> supplier) |
static Striped<java.util.concurrent.locks.Lock> |
lazyWeakLock(int stripes)
Creates a
Striped<Lock> with lazily initialized, weakly referenced locks. |
static Striped<java.util.concurrent.locks.ReadWriteLock> |
lazyWeakReadWriteLock(int stripes)
Creates a
Striped<ReadWriteLock> with lazily initialized, weakly referenced read-write
locks. |
static Striped<java.util.concurrent.Semaphore> |
lazyWeakSemaphore(int stripes,
int permits)
Creates a
Striped<Semaphore> with lazily initialized, weakly referenced semaphores,
with the specified number of permits. |
static Striped<java.util.concurrent.locks.Lock> |
lock(int stripes)
Creates a
Striped<Lock> with eagerly initialized, strongly referenced locks. |
static Striped<java.util.concurrent.locks.ReadWriteLock> |
readWriteLock(int stripes)
Creates a
Striped<ReadWriteLock> with eagerly initialized, strongly referenced
read-write locks. |
static Striped<java.util.concurrent.Semaphore> |
semaphore(int stripes,
int permits)
Creates a
Striped<Semaphore> with eagerly initialized, strongly referenced semaphores,
with the specified number of permits. |
abstract int |
size()
Returns the total number of stripes in this instance.
|
private static int |
smear(int hashCode) |
private static final int LARGE_LAZY_CUTOFF
private static final Supplier<java.util.concurrent.locks.ReadWriteLock> READ_WRITE_LOCK_SUPPLIER
private static final Supplier<java.util.concurrent.locks.ReadWriteLock> WEAK_SAFE_READ_WRITE_LOCK_SUPPLIER
private static final int ALL_SET
public abstract L get(java.lang.Object key)
key1.equals(key2)
, then get(key1) == get(key2)
.key
- an arbitrary, non-null keypublic abstract L getAt(int index)
size()
,
exclusively.index
- the index of the stripe to return; must be in [0...size())
abstract int indexFor(java.lang.Object key)
public abstract int size()
public java.lang.Iterable<L> bulkGet(java.lang.Iterable<?> keys)
getAt(int)
) order. Thus, threads that use the stripes in the order returned by this method
are guaranteed to not deadlock each other.
It should be noted that using a Striped<L>
with relatively few stripes, and bulkGet(keys)
with a relative large number of keys can cause an excessive number of shared
stripes (much like the birthday paradox, where much fewer than anticipated birthdays are needed
for a pair of them to match). Please consider carefully the implications of the number of
stripes, the intended concurrency level, and the typical number of keys used in a bulkGet(keys)
operation. See Balls in
Bins model for mathematical formulas that can be used to estimate the probability of
collisions.
keys
- arbitrary non-null keysget(Object)
; may contain duplicates), in an increasing index order.static <L> Striped<L> custom(int stripes, Supplier<L> supplier)
Striped<L>
with eagerly initialized, strongly referenced locks. Every lock is
obtained from the passed supplier.stripes
- the minimum number of stripes (locks) requiredsupplier
- a Supplier<L>
object to obtain locks fromStriped<L>
public static Striped<java.util.concurrent.locks.Lock> lock(int stripes)
Striped<Lock>
with eagerly initialized, strongly referenced locks. Every lock
is reentrant.stripes
- the minimum number of stripes (locks) requiredStriped<Lock>
public static Striped<java.util.concurrent.locks.Lock> lazyWeakLock(int stripes)
Striped<Lock>
with lazily initialized, weakly referenced locks. Every lock is
reentrant.stripes
- the minimum number of stripes (locks) requiredStriped<Lock>
public static Striped<java.util.concurrent.Semaphore> semaphore(int stripes, int permits)
Striped<Semaphore>
with eagerly initialized, strongly referenced semaphores,
with the specified number of permits.stripes
- the minimum number of stripes (semaphores) requiredpermits
- the number of permits in each semaphoreStriped<Semaphore>
public static Striped<java.util.concurrent.Semaphore> lazyWeakSemaphore(int stripes, int permits)
Striped<Semaphore>
with lazily initialized, weakly referenced semaphores,
with the specified number of permits.stripes
- the minimum number of stripes (semaphores) requiredpermits
- the number of permits in each semaphoreStriped<Semaphore>
public static Striped<java.util.concurrent.locks.ReadWriteLock> readWriteLock(int stripes)
Striped<ReadWriteLock>
with eagerly initialized, strongly referenced
read-write locks. Every lock is reentrant.stripes
- the minimum number of stripes (locks) requiredStriped<ReadWriteLock>
public static Striped<java.util.concurrent.locks.ReadWriteLock> lazyWeakReadWriteLock(int stripes)
Striped<ReadWriteLock>
with lazily initialized, weakly referenced read-write
locks. Every lock is reentrant.stripes
- the minimum number of stripes (locks) requiredStriped<ReadWriteLock>
private static int ceilToPowerOfTwo(int x)
private static int smear(int hashCode)