StampedLock
Introduction to the
We introduced ReentrantReadWriteLock, but JDK1.8 introduced StampedLock, which I’d like to call the best.
A capability-based lock with three modes for controlling read/write access.
StampedLock status consists of version and mode.
The lock acquisition method returns an imprint that represents and controls access to the lock state; The “try” versions of these methods may return a special value of zero to indicate that access failed.
The lock release and transition method takes stamps as arguments and fails if they do not match the state of the lock.
Three models
The three models are:
(1) write
The writeLock() method may block waiting for exclusive access and return stamps that can be used in the unlockWrite(long) method to release the lock.
The untimed and timed versions of tryWriteLock also provide that a read lock cannot be obtained while the lock remains in write mode, and all optimistic read validations will fail.
(2) read
The method readLock() may prevent waiting for non-exclusive access and return a stamp that can be used for the method unlockRead(long) to release the lock.
Untimed and timed versions of tryReadLock are also available.
(3) Optimistic reading
The tryOptimisticRead() method returns a non-zero flag only if the lock is not currently in write mode.
The validate(long) method returns true if a lock has not been obtained in write mode by the time the given stamps are obtained.
This mode can be thought of as a very weak version of the read lock, which can be broken by writer at any time.
Using optimistic mode for simple read-only code snippets usually reduces contention and improves throughput.
However, its use is inherently fragile. The optimistic reading section can only read fields and save them in local variables for later validation.
Fields read in optimistic mode can be very inconsistent, so use cases are only applicable if you are familiar with the data representation to check for consistency and/or call the method validate() repeatedly.
For example, such a step is usually required when reading an object or array reference for the first time and then accessing one of its fields, elements, or methods.
core idea
StampedLock not only prevents multiple reads from blocking each other, but also prevents simultaneous reads from blocking writes.
- Why is StampedLock so amazing?
The idea behind this is that if a write occurs while reading, the new value should be obtained by retry rather than blocking the write.
This pattern is the classic idea of lockless programming, as is the idea of CAS spin.
This operation makes StampedLock very useful in scenarios where there are many readers and few writers, while avoiding write starvation.
Use case
public class Point {
private double x, y;
private final StampedLock stampedLock = new StampedLock();
// Write lock usage
void move(double deltaX, double deltaY){
long stamp = stampedLock.writeLock(); // Get the write lock
try {
x += deltaX;
y += deltaY;
} finally {
stampedLock.unlockWrite(stamp); // Release the write lock}}// Optimistic read lock usage
double distanceFromOrigin(a) {
long stamp = stampedLock.tryOptimisticRead(); // Get an optimistic read lock
double currentX = x;
double currentY = y;
if(! stampedLock.validate(stamp)) {// Check if any other write locks have occurred after optimistic read locks, return false if so
stamp = stampedLock.readLock(); // Get a pessimistic read lock
try {
currentX = x;
} finally {
stampedLock.unlockRead(stamp); // Release the pessimistic read lock}}return Math.sqrt(currentX*currentX + currentY*currentY);
}
// Pessimistic read lock and read lock upgrade write lock use
void moveIfAtOrigin(double newX,double newY) {
long stamp = stampedLock.readLock(); // Pessimistic read lock
try {
while (x == 0.0 && y == 0.0) {
long ws = stampedLock.tryConvertToWriteLock(stamp); // Read locks are converted to write locks
if(ws ! =0L) { // The conversion succeeded
stamp = ws; // Note update
x = newX;
y = newY;
break;
} else {
stampedLock.unlockRead(stamp); // The read lock was released when the conversion failed
stamp = stampedLock.writeLock(); // Force a write lock}}}finally {
stampedLock.unlock(stamp); // Release all locks}}}Copy the codeIf you look at the first method, you can see that it is the same as ReentrantReadWriteLock write lock.
Note that a stamp of type LONG is returned when the write lock is acquired and passed in when the write lock is released.
What is this stamp used for? What happens if we change this value in the middle? Here is a temporary explanation, after the analysis of the source will answer this question.
The second method, distanceFromOrigin, is more specific and calls tryOptimisticRead, which by its name is an optimistic read lock. First of all, what is optimism lock? Optimistic locking means that it is assumed that the shared variable will not change during optimistic lock acquisition, and since it is assumed that the shared variable will not change, there is no need to lock it. After obtaining the optimistic read lock, we perform some operations and then call the validate method, which verifies that any write operations have been performed since tryOptimisticRead. If so, we acquire a read lock. The read lock is similar to the read lock in ReentrantReadWriteLock and is assumed to be a shared lock.
The third method, moveIfAtOrigin, does a lock upgrade by calling tryConvertToWriteLock to try to convert a read lock to a write lock. If the conversion succeeds, the write lock is acquired. If the conversion fails, the write lock is occupied. This is done by calling writeLock to acquire the writeLock.
Having looked at the three methods above, you probably have a general idea of how StampedLock works.
Here is a step by step analysis of StampedLock source code to understand how it is behind the lock hunger problem.
Source code analysis
The class definition
/* * @author Doug Lea */
public class StampedLock implements java.io.Serializable {}
Copy the codeThis lock is li Dagou implementation, let’s learn the source code together.
Algorithm of notes
There’s a core algorithm that’s not in the documentation.
Our translation is as follows:
The design uses elements of sequence locking (used in the Linux kernel; Please refer to Lameter www.lameter.com/gelato2005…. And elsewhere;
Please refer to Boehm www.hpl.hp.com/techreports… Dl.acm.org/citation.cf…
Conceptually, the primary state of a lock consists of a serial number that is odd when the lock is written, and even odd in other cases.
However, when a read is locked, the reader count is offset by a non-zero value.
The read count is ignored when validating the “optimistic” SEqLock-reader style tag.
Because we have to use a small number of bits for readers (currently 7), supplementary reader overflow words are used when the number of readers exceeds the count field.
To do this, we treat the maximum reader count (RBITS) as a spin lock to protect overflow updates.
Waiting for use in AbstractQueuedSynchronizer for use in a modified form of CLH lock (for the full account, please refer to the internal document), in which each node is marked (field) to a reader or writer.
The collection of wait readers is grouped (linked) under a common node (field cowait), so it acts as a single node compared to most CLH mechanisms.
Because of the queue structure, wait nodes don’t actually need to carry serial numbers. We know that each one is bigger than its predecessor.
This simplifies the scheduling policy to a major FIFO scheme that contains elements of phase-fair locking (see Brandenburg&Anderson, especially www.cs.unc.edu/~bbb/diss/)…
In particular, we use the fair rebuttal rule:
If an incoming reader arrives while holding a read lock, but there are queued writers, the incoming reader is queued.
(This rule takes care of some of the complexity of the method acquireRead, but without it, the lock becomes very unfair.)
Method release does not (and sometimes does not) wake up the wait by itself.
This is done by the main thread, but with the help of any other thread, there is nothing better to do in the acquireRead and acquireWrite methods.
These rules apply to actual queued threads.
Regardless of the preference rule, all tryLock forms attempt to acquire the lock and thus may “insert” their way.
Random rotation is used in the fetch method to reduce (increasingly expensive) context switches, while also avoiding constant memory jitter between many threads.
We limit rotation to the beginning of the queue.
Threads wait up to a maximum of SPINS (decreasing the spin count 50% of the time per iteration) before blocking.
If it fails to get locked after waking up and is still (or becomes) the first waiting thread (indicating that some other threads are locked and get locked), it will upgrade its spin (up to MAX_HEAD_SPINS), The goal is to reduce the likelihood of continually losing to barging threads.
Almost all of these mechanisms are implemented in the methods acquireWrite and acquireRead, which are typical examples of this type of code because actions and retries depend on a consistent set of locally cached reads, so they spread out.
As described in Boehm’s paper (above), sequence validation (primarily the method validate()) requires a stricter collation than that applied to ordinary volatile reads (” states “).
To enforce the read order before validation and the validation itself if it has not already been enforced, we use unsafe.loadfence.
The memory layout keeps the lock state and the queue pointer together (usually on the same cache line). This generally applies to most read loads.
In most other cases, the natural tendency for adaptive rotating CLH locks to reduce memory contention reduces the incentive to further scatter competing places, but may be improved in the future.
Ps: As you can see here, this design is actually derived from sequential locking, which is also used in the Linux kernel.
www.hpl.hp.com/techreports… The paper addresses
Effective Synchronization on Linux/NUMA Systems
Ps: I also translated these two books once, but the content is too boring (limited level, boring translation), and the content is too much, I will not do the expansion here.
Some constant definitions
/** Number of processors, for spin control */
private static final int NCPU = Runtime.getRuntime().availableProcessors();
/** Maximum number of retries before enqueuing on acquisition */
private static final int SPINS = (NCPU > 1)?1 << 6 : 0;
/** Maximum number of retries before blocking at head on acquisition */
private static final int HEAD_SPINS = (NCPU > 1)?1 << 10 : 0;
/** Maximum number of retries before re-blocking */
private static final int MAX_HEAD_SPINS = (NCPU > 1)?1 << 16 : 0;
/** The period for yielding when waiting for overflow spinlock */
private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
/** The number of bits to use for reader count before overflowing */
private static final int LG_READERS = 7;
Copy the codeThe amount of state that a read/write lock shares
As you can see from the example above, StampedLock provides an optimistic read lock acquisition and release method similar to ReentrantReadWriteLock.
So how do these three ways interact?
According to AQS experience, StampedLock should also use a state quantity to mark the lock state.
This can be proved by the following source code:
// Use the state operation to obtain the value of stamp
private static final int LG_READERS = 7;
private static final long RUNIT = 1L; / / 0000 0000 0001
private static final long WBIT = 1L << LG_READERS; / / 0000 1000 0000
private static final long RBITS = WBIT - 1L; / / 0000 0111 1111
private static final long RFULL = RBITS - 1L; / / 0000 0111 1110
private static final long ABITS = RBITS | WBIT; / / 0000 1111 1111
private static final long SBITS = ~RBITS; / / 1111 1000 0000
// The value of state at initialization
private static final long ORIGIN = WBIT << 1; / / 0001 0000 0000
// Lock the shared variable state
private transient volatile long state;
// Read locks are used to store extra toxins when they overflow
private transient int readerOverflow;
Copy the codeIn addition to defining the state variable, the above source code also provides a series of variables to manipulate state, which is used to represent the various states of read and write locks.
For ease of understanding, I’ve represented them all as binary values of limited length, with the lower 12 bits representing the 64 longs and the higher ones automatically filled in with zeros.
To understand the role of these states, we need to analyze how the three lock operations are represented by the state variable. First, we will look at acquiring and releasing write locks.
Other constants
// Initial value for lock state; avoid failure value zero
// The initial value of the lock state; Avoid a failure value of zero
private static final long ORIGIN = WBIT << 1;
// Special value from cancelled acquire methods so caller can throw IE
// Remove the special value in the get method so that the caller can throw an interrupt exception
private static final long INTERRUPTED = 1L;
// Values for node status; order matters
// Node status; Order is important
private static final int WAITING = -1;
private static final int CANCELLED = 1;
// Modes for nodes (int not boolean to allow arithmetic)
// The mode of the node (not Boolean to allow arithmetic)
private static final int RMODE = 0;
private static final int WMODE = 1;
Copy the codeWait node definition
The node definition here should be intended for later use in bidirectional lists.
All values are volatile to ensure volatility and inter-thread variability.
Mode uses the final modifier and is immutable once created, so it is thread-safe.
/** Wait nodes */
static final class WNode {
volatile WNode prev;
volatile WNode next;
volatile WNode cowait; // list of linked readers
volatile Thread thread; // non-null while possibly parked
volatile int status; // 0, WAITING, or CANCELLED
final int mode; // RMODE or WMODE
WNode(intm, WNode p) { mode = m; prev = p; }}/** Head of CLH queue */
private transient volatile WNode whead;
/** Tail (last) of CLH queue */
private transient volatile WNode wtail;
Copy the codeview
This also introduces the concept of views, which may or may not be related to the common views in our database.
// views
transient ReadLockView readLockView;
transient WriteLockView writeLockView;
transient ReadWriteLockView readWriteLockView;
Copy the codeReadLockView definition
This is a simple implementation of the Lock interface.
The methods called in the view will be described later.
final class ReadLockView implements Lock {
public void lock(a) { readLock(); }
public void lockInterruptibly(a) throws InterruptedException {
readLockInterruptibly();
}
public boolean tryLock(a) { returntryReadLock() ! =0L; }
public boolean tryLock(long time, TimeUnit unit)
throws InterruptedException {
returntryReadLock(time, unit) ! =0L;
}
public void unlock(a) { unstampedUnlockRead(); }
public Condition newCondition(a) {
throw newUnsupportedOperationException(); }}Copy the codeWrite lock view
Also for the Lock interface implementation, the corresponding implementation is write Lock.
final class WriteLockView implements Lock {
public void lock(a) { writeLock(); }
public void lockInterruptibly(a) throws InterruptedException {
writeLockInterruptibly();
}
public boolean tryLock(a) { returntryWriteLock() ! =0L; }
public boolean tryLock(long time, TimeUnit unit)
throws InterruptedException {
returntryWriteLock(time, unit) ! =0L;
}
public void unlock(a) { unstampedUnlockWrite(); }
public Condition newCondition(a) {
throw newUnsupportedOperationException(); }}Copy the codeRead/write lock view
final class ReadWriteLockView implements ReadWriteLock {
public Lock readLock(a) { return asReadLock(); }
public Lock writeLock(a) { returnasWriteLock(); }}Copy the codeThe main conversion here is to return the read-write lock implementation.
Read lock implementation
If there is a read lock view, return it directly. If there is no read lock view, create an instance.
public Lock asReadLock(a) {
ReadLockView v;
return((v = readLockView) ! =null ? v :
(readLockView = new ReadLockView()));
}
Copy the codeWrite lock implementation
Similarly returns the write lock view.
public Lock asWriteLock(a) {
WriteLockView v;
return((v = writeLockView) ! =null ? v :
(writeLockView = new WriteLockView()));
}
Copy the codeThree types of lock acquisition and release
The follow-up content has been sorted out very well, so I put it directly in the text for you to learn.
Java Concurrency (8) – The king of performance in read/write locks: StampedLock
Write lock release and acquisition
The source code
public StampedLock(a) {
state = ORIGIN; // Initialize state to 0001 0000 0000
}
public long writeLock(a) {
long s, next;
return ((((s = state) & ABITS) == 0L && // No read/write lock
U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ? // The CAS operation attempted to obtain a write lock
next : acquireWrite(false.0L)); // Return to next if the command is successfully obtained. If the command fails, subsequent processing is performed
}
public void unlockWrite(long stamp) {
WNode h;
if(state ! = stamp || (stamp & WBIT) ==0L) // Stamp value is modified, or write lock has been released, throw an error
throw new IllegalMonitorStateException();
state = (stamp += WBIT) == 0L ? ORIGIN : stamp; // add 0000 1000 0000 to record the write lock change and change the write lock state
if((h = whead) ! =null&& h.status ! =0)
release(h);
}
Copy the codeRead locks are represented by the first 7 bits, and each read lock is incremented by 1.
A write lock is represented by dividing the first seven bits and adding 1000 000 for each write lock acquired, both of which can be proved later in the source code.
Set the state variable to 0001 0000 0000 during initialization.
The write lock acquires when the (s = state) & ABITS operation is equal to 0.
Write lock acquisition
There are three types of write lock acquisition:
(1) State is 0001 0000 0000 when there is no read or write lock
0001 0000 0000 &0000 1111 1111 = 0000 0000 0000Copy the code(2) When there is a read lock, state is 0001 0000 0001
0001 0000 0001 & 0000 1111 1111 = 0000 0000 0001 // Does not equal 0LCopy the code(3) There is a write lock with state 0001 1000 0000
0001 1000 0000 &0000 1111 1111 = 0000 1000 0000 // Does not equal 0LCopy the codeWhen acquiring a write lock, set S + WBIT to state, that is, each time acquiring a write lock, add 0000 1000 0000.
Also returns the value of s + WBIT
0001 0000 0000 + 0000 1000 0000 = 0001 1000 0000
Copy the codeWrite lock release
State = (stamp += WBIT) == 0L; state = (stamp += WBIT) == 0L ORIGIN: stamp to release the write lock, the bit operation is expressed as follows: stamp += WBIT
0010 0000 0000 = 0001 1000 0000 + 0000 1000 0000
Copy the codeThis step is the key!!
Instead of +1 and -1 like ReentrantReadWriteLock, the write lock is released by adding 0000, 1000, 0000 again to make the high level change each time.
Just subtract 0000, 1000, 0000.
This is to pave the way for the optimistic lock, so that every time the lock is written, it leaves a trace.
You can imagine A scenario where the letter A changes to B and you can see the change. If you change from A to B and then to A over A period of time, A will be displayed in memory, but you can’t record the change. This is the ABA problem in CAS.
StampedLock is used to record the write lock operation by adding 0000 1000 0000 to the high value each time.
Acquire write lock for the first time:
0001 0000 0000 + 0000 1000 0000 = 0001 1000 0000
Copy the codeRelease write lock for first time:
0001 1000 0000 + 0000 1000 0000 = 0010 0000 0000
Copy the codeObtain write lock for second time:
0010 0000 0000 + 0000 1000 0000 = 0010 1000 0000
Copy the codeSecond release write lock:
0010 1000 0000 + 0000 1000 0000 = 0011 0000 0000
Copy the codeObtain write lock for NTH time:
1110 0000 0000 + 0000 1000 0000 = 1110 1000 0000
Copy the codeRelease write lock for NTH time:
1110 1000 0000 + 0000 1000 0000 = 1111 0000 0000
Copy the codeAs you can see, bit 8 is used to indicate the write lock status, the first 7 bits are used to indicate the read lock status, and the number of times the write lock was acquired after bit 8. This effectively solves the ABA problem, leaving a record of each lock write and providing a basis for optimistic lock checking changes later.
The acquireWrite method is a complex one. If you are interested in this method, you can search it online.
Here is just a brief summary of this method. This method is divided into two steps to queue the thread. First, it tries to obtain the lock by spinning for several times through random detection, and then initializes the node for insertion after a certain number of spins fail.
Pessimistic read lock release and acquisition
The source code
public long readLock(a) {
long s = state, next;
return ((whead == wtail && (s & ABITS) < RFULL && // Queue is empty, no write lock, and the read lock is not overflowed, try to obtain the read lock
U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ? // CAS attempts to obtain read lock +1
next : acquireRead(false.0L)); // Obtain the lock successfully, return s + RUNIT, failure to enter the subsequent processing, similar to acquireWrite
}
public void unlockRead(long stamp) {
long s, m; WNode h;
for (;;) {
if(((s = state) & SBITS) ! = (stamp & SBITS) || (stamp & ABITS) ==0L || (m = s & ABITS) == 0L || m == WBIT)
throw new IllegalMonitorStateException();
if (m < RFULL) { // Less than the maximum record value (if 127 is exceeded, put it in the readerOverflow variable)
if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { // CAS attempts to release read lock 1
if(m == RUNIT && (h = whead) ! =null&& h.status ! =0)
release(h);
break; }}else if(tryDecReaderOverflow(s) ! =0L) //readerOverflow - 1
break; }}Copy the codeThe pessimistic read lock is similar to ReentrantReadWriteLock except that StampedLock’s read lock is easy to overflow. The maximum value of StampedLock’s read lock is 127. After that, StampedLock’s read lock is stored by an additional variable readerOverflow. Because write locks are increasing.
Lock acquisition
Pessimistic read lock acquisition can be divided into the following four cases:
When there is no read or write lock, the state is 0001 0000 0000
< 0000 0111 1110, you can try to obtain read lock 0001 0000 0000 & 0000 1111 1111 = 0000 0000 0000Copy the codeWhen there is a read lock, state is 0001 0000 0001
0000 0000 0001&0000 1111 1111 = 0000 0000 0001Copy the codeThere is a write lock with state 0001 1000 0000
// Read lock 0001 1000 0000&0000 1111 1111 = 0000 1000 0000 cannot be obtained if the value is greater than 0000 0111 1110Copy the codeRead lock overflows. The state is 0001 0111 1110
0001 0111 1110&0000 1111 1111 = 0000 0111 1110Copy the codeRelease the lock
The read lock is released by the s-runit operation (-1) without an overflow, and the readerOverflow variable -1 is released when an overflow occurs.
Optimistic read lock acquisition and validation
Optimistic read locks do not actually acquire locks, so there is no lock release process, just after the operation through verification checks and changes before the acquisition.
The source code
The source code is as follows:
// Try to get optimistic lock
public long tryOptimisticRead(a) {
long s;
return (((s = state) & WBIT) == 0L)? (s & SBITS) :0L;
}
// Verify that there is no write operation after optimistic lock acquisition
public boolean validate(long stamp) {
StoreFence () and fullFence();
U.loadFence();
return (stamp & SBITS) == (state & SBITS); // Compare whether there is a write operation
}
Copy the codeThe basic principle of optimistic locking is to record the write state of the state when the lock is acquired, and then check whether the write state has changed after the operation is completed, because the write state will be recorded at a high level each time, so as to avoid the accurate data after the write lock is acquired and released.
Lock acquisition
There are three ways to obtain write lock records:
(1) State is 0001 0000 0000 when there is no read or write lock
//((s = state) & WBIT) == 0L) true
0001 0000 0000 & 0000 1000 0000 = 0000 0000 0000
//(s & SBITS)
0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
Copy the code(2) When there is a read lock, state is 0001 0000 0001
//((s = state) & WBIT) == 0L) true
0001 0000 0001 & 0000 1000 0000 = 0000 0000 0000
//(s & SBITS)
0001 0000 0001 & 1111 1000 0000 = 0001 0000 0000
Copy the code(3) There is a write lock with state 0001 1000 0000
//((s = state) & WBIT) == 0L) false
0001 1000 0000 & 0000 1000 0000 = 0000 1000 0000
//0L
0000 0000 0000
Copy the codeVerify that there is a write operation
Check whether there is a write operation during the process, divided into four cases
(1) Once
0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
0010 0000 0000 & 1111 1000 0000 = 0010 0000 0000 //false
Copy the code(2) I haven’t written about it, but I have read it
0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
0001 0000 1111 & 1111 1000 0000 = 0001 0000 0000 //true
Copy the code(3) I’m writing
0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
0001 1000 0000 & 1111 1000 0000 = 0001 1000 0000 //false
Copy the code(4) Writing before, whether finished or not will not be 0L
0000 0000 0000 & 1111 1000 0000 = 0000 0000 0000 //false
Copy the codesummary
We look at the whole history of concurrent locking, actually the history of an idea
(1) Synchronized most commonly used pessimistic lock, easy to use, but not fair lock.
(2) ReentrantLock ReentrantLock provides fair lock and other rich features.
(3) The ReentrantReadWriteLock readwrite lock supports read/write separation and performs well in multiple read scenarios.
(4) Reading this article does not block writing, is a more excellent idea. There are CopyOnWriteList implementations of similar ideas.
Hope you found this article helpful, and if you have any other ideas, please share them in the comments section.
All geeks’ likes, favorites and forwarding are the biggest motivation for Lao Ma to write!
