The previous article introduced a read-write lock implementation scheme where writers are not starved by readers who come later, ensuring fairness for writers competing for the lock with readers. This article introduces a special type of read-write spinlock that guarantees the highest priority for write operations. Specifically, when there is only one writer, meaning there are no other writers competing with it, the writer can perform write operations at any time, greatly ensuring the timeliness of data updates.
We know that when readers and writers simultaneously perform read and write operations on data, they are mutually exclusive. However, in this special read-write lock, there is no mutual exclusion between read and write operations using locks. Write operations are unaffected by read operations and will ignore the presence of readers, proceeding directly with the write operation. However, read operations are affected by write operations; if a write operation updates the data during a read operation, the read operation becomes invalid. The mechanism works as follows: after completing a read operation, the reader checks whether the data has been modified during the read operation. If it has been modified, the reader discards the data it has read and re-reads the data. In other words, the reader always assumes that the data it reads is correct before reading, and verifies the correctness of the data afterward. This is an optimistic read lock, while the read-write lock implementations in the previous two articles were based on pessimistic locks.
Implementation Principle
A counter is used to accumulate the number of write operations. Write or read operations are only allowed when the value of this counter is even, meaning that readers and one writer can operate simultaneously. The initial value of the counter must be even, typically initialized to 0.
When a writer performs a write operation, it first increments this counter by 1, changing its value to odd, indicating that a writer is modifying the data (i.e., holding the write lock). After the writer completes the write operation, it increments the counter again, returning it to even, indicating that the writer has completed the write operation (i.e., releasing the write lock).
Before a reader performs a read operation, if the value of the counter is odd, it indicates that a writer is currently writing, and the reader must wait. If it is even, the reader saves the value of the counter, and after reading the data, it compares the current value of the counter with the original value. If they are the same, it indicates that the data has not been updated during the read operation, and the data has been successfully read; otherwise, it indicates that dirty data has been read, and the reader should discard the data and start reading again.
In summary, writers compete for write operations when the counter is even, while readers ensure that the counter remains even during their read operations and that it has not changed, thus guaranteeing that they read correct data. Because this read-write lock is based on the accumulation order of the counter and implements functionality based on the odd/even nature of the sequence number, it is commonly referred to as a sequential lock.
Implementation Code
Below is the class definition for the sequential lock:
#include <atomic>
class seq_lock final {
public:
int read_entry() noexcept;
bool read_validate(int seq) noexcept;
void write_lock() noexcept;
void write_unlock() noexcept;
seq_lock() = default;
seq_lock(const seq_lock &) = delete;
seq_lock &operator=(const seq_lock &) = delete;
private:
atomic<int> counter{0};
};The data member counter represents the counter, which is of type atomic<int> with an initial value of 0, and can only be modified by writers. When a writer is ready to perform a write operation, it first increments it by 1, changing it to odd. After finishing writing, it increments it again, returning it to even. Thus, when it is odd, it indicates that a writer is performing a write operation, and when it is even, it indicates that no write operation is currently in progress. Although the counter can continue to increment indefinitely, there is no need to worry about overflow. As shown in the implementation code below, the counter does not compare sizes but only checks odd/even status and equality, which is unrelated to whether it is positive or negative. Even if it overflows and changes from positive to negative, it will still function correctly.
1. Entering Read Operation
int seq_lock::read_entry() noexcept {
// Optimistic read
while (true) {
int seq = counter.load(std::memory_order_acquire);
if ((seq & 1) == 0) { // Odd, spin wait
// Wait until it is even, indicating the write operation has ended
return seq; // Return the counter value, to be used for validating the read result later
}
}
}This function allows readers to check if they can perform a read operation. It first checks the value of the counter; if it is odd, it indicates that a writer is currently updating the data, making it unsafe to read, as the state may not be fully updated. In this case, the reader should not perform a read operation but should continue to spin wait. When the counter value is even, it indicates that no writer is currently performing a write operation, and the data is consistent, allowing the reader to exit the spin and use the counter value as the return value. Although the reader spins, it is not actually acquiring or releasing a lock; it is merely checking the odd/even value of the counter, which does not affect the writer’s operations.
Finally, the acquire memory order ensures that subsequent data read operations do not occur out of order relative to the counter.load() read operation, guaranteeing that the data read is correct. This forms an acquire-release memory order semantics with the release memory order used in seqLock::write_unlock(), ensuring the happen-before relationship between threads.
However, when the counter is even, it only indicates that there is no writer modifying the data at that moment. The shared data may be successfully read, but it is also possible to read dirty data, so further checks are needed using the function below.
2. Checking for Dirty Reads
bool seq_lock::read_validate(int seq) noexcept {
std::atomic_thread_fence(std::memory_order_acquire);
// If seq is the original value, it indicates that the shared data has not been updated
return counter.load(std::memory_order_relaxed) == seq;
}This function is very simple; it checks whether the sequence number seq obtained from seqLock::read_entry() is equal to the current value of the counter. If they are equal, it indicates that no writer has updated the data during the read operation, and the data read is correct. If they are not equal, it indicates that a new write operation is either ongoing or has just completed, and the data may have been modified, meaning the reader has read dirty data and should discard the data and start reading again. Clearly, when they are not equal, if the current value of the counter is odd, it indicates that a writer is modifying the data. If it is still even, it indicates that during the read operation, a writer has completed one or more updates.
Of course, this method can also lead to false positives. If the data has already been read, and a writer starts a write operation immediately after, the reader may call counter.load() just as a writer is preparing to write, incrementing the counter to odd without having started modifying the data. In this case, the reader may read valid data but still mistakenly believe it is dirty data, forcing it to roll back and start over until the current write operation is complete. Although it misjudges valid data as dirty data, wasting a valid read, it only delays the successful reading of data and does not cause errors. Moreover, it has a positive aspect: even though valid data has been read, new data is being updated, so it is better to discard the current data and wait for the writer to finish updating before reading the updated data.
Let’s look at the memory order of atomic variable operations:
When used, it is in the form of read_entry():
int seq=0;
do {
seq = seqlock.read_entry();
...... // Shared variable read operation
} while (!seqlock.read_validate(seq));Thus, read_entry() and read_validate() form a critical section for reading shared data. The read operations on shared data must be executed within this critical section; otherwise, the data read may be the data that the writer has already modified, which is unsafe. To ensure safety, a common solution is to use acquire memory order at the entrance of the critical section to ensure that subsequent memory read and write operations do not cross it, and to use release memory order at the exit of the critical section to ensure that preceding memory read and write operations do not cross it.
In read_entry(), acquire memory order is used on the counter, so should release memory order be used here? However, since read_validate() involves a read operation on the counter, release memory order cannot be used during atomic variable read operations, and there are no other atomic variables available. Therefore, a memory barrier must be used to specify the memory order. Can atomic_thread_fence(memory_order_release) be used? No! Because release memory order semantics only guarantee that memory read and write operations before the barrier do not cross the release barrier, but read operations after the barrier can cross it, meaning that the subsequent counter.load() read operation can cross the release barrier, potentially leading to out-of-order execution with previous shared variable read operations. Therefore, atomic_thread_fence(memory_order_release) cannot be used; instead, atomic_thread_fence(memory_order_acquire) must be used. This ensures that subsequent memory read and write operations do not cross this acquire barrier, and that previous memory read operations do not cross this acquire barrier either.
3. Requesting a Write Lock
void seq_lock::write_lock() noexcept {
while (true) {
int seq = counter.load(std::memory_order_relaxed);
if ((seq & 1) == 1) {
// If odd, another writer holds the lock, spin wait again
continue;
}
// If even, increment the counter to odd, indicating the writer holds the lock
if (counter.compare_exchange_strong(
seq, seq + 1, std::memory_order_acquire,
std::memory_order_relaxed)) {
break;
}
}
}The write lock is a spinlock, and write operations are only allowed when the counter is even. If it is odd, it indicates that another writer is currently performing a write operation, and the writer must spin wait until the counter becomes even again. Before the write operation modifies the data, the counter is incremented by 1, changing it to odd, indicating that a writer is modifying the data. If another writer wants to perform a write operation, it must wait for the counter to become even again, and the data read by readers must be considered invalid.
Write operations are mutually exclusive, and before performing a write operation, the writer must call this interface to request a write lock. After returning, it can perform the write operation.
Here, the CAS operation on the counter uses acquire memory order semantics, ensuring that memory read and write operations following the counter.compare_exchange_strong() operation do not cross it.
4. Releasing the Write Lock
void seq_lock::write_unlock() noexcept {
counter.fetch_add(1, std::memory_order_release);
}Releasing the write lock is very simple; it increments the counter by 1. We know that after a writer acquires the lock, the counter value becomes odd. After incrementing it, it becomes even again, indicating that the write operation is complete, allowing other readers to read the data or other writers to request the lock.
Here, release memory order semantics are used on the counter, ensuring that memory read and write operations before counter.fetch_add() do not cross it.
Looking again at the read_entry() function, it uses acquire memory order semantics on counter.load(), ensuring that subsequent memory read and write operations do not cross this load read operation. When the writer modifies the shared memory variable, it will not cross counter.fetch_add(), and the increment operation of counter.fetch_add() makes the counter even. The reader’s counter.load() is waiting for an even value, so read_entry() at counter.load() is a synchronization point. The release and acquire memory orders ensure that the data read by the reader is the data that the writer has already updated. Thus, as long as the reader reads the counter as even, its subsequent read operations are guaranteed to be those that the writer has already completed.
Similarly, write_lock() at counter.load() is also a synchronization point, providing the same memory order guarantee as read_entry(), thus forming an acquire-release memory order semantics to protect the critical section.
5. Simplified Implementation
If readers can generally read correct data and the cost of reading data is low, even if they frequently roll back when reading dirty data, the reader’s operations can use a simpler scheme:
When entering the read operation, read_entry() directly returns the value of the counter:
int seq_lock::read_entry() noexcept {
// Optimistic read
return counter.load(std::memory_order_acquire);
}When validating after reading, read_validate() must check not only if seq has not changed but also if it is even:
bool seq_lock::read_validate(int seq_old) noexcept {
std::atomic_thread_fence(std::memory_order_acquire);
int seq_new = counter.load(std::memory_order_relaxed);
// If equal and even, it indicates successful reading of data
return (seq_old == seq_new) && ((seq_new & 1) == 0);
}This checks the counter values before and after reading; if they are equal and even, the read operation is considered successful.
If there is only one writing thread, meaning there is no competition for the write lock, the implementation for requesting a write lock is simpler:
void seq_lock::write_lock() noexcept {
counter.fetch_add(1, std::memory_order_acquire);
}Both acquiring and releasing the write lock involve incrementing the counter, but they use different memory orders.
Usage Instructions
The sequential lock only has a write lock and does not have a read lock. Its application method differs from the previously introduced read-write locks, so it is necessary to clarify the steps and precautions for using it:
1. Reader Thread Code Template
Since there is no read lock, when seq_lock::read_entry() returns, it only indicates that there is no ongoing write operation, allowing the reader to read the data. After reading the data, it must use seq_lock::read_validate() to determine whether the read operation was successful. If not, it must roll back and re-read until successful. Therefore, this process is a loop structure:
int seq=0;
do {
seq = seqlock.read_entry();
... // Perform read operation
} while (!seqlock.read_validate(seq));Thus, the read operation process is to roll back and retry if the read fails, which is an optimistic read, somewhat similar to the CAS algorithm. Compared to the CAS algorithm, the sequential lock focuses on read operations, always assuming that the read operation will succeed, and only checks afterward whether any write operations occurred during the read. If so, the data read is dirty, and it rolls back and retries; whereas the CAS algorithm focuses on write operations, always assuming that the write operation will succeed, attempting to write, and rolling back if another write operation occurs during the write.
However, what needs to be done inside the while loop is to save the data to a data copy and then validate the data’s validity. Thus, when dirty data is detected, this data copy can simply be overwritten. In the critical section, the only operations allowed are copying the data (i.e., copy on read); do not directly use the data for any business processing. First, business processing may take too long, during which time the writer may modify the data, increasing the probability of retries. Secondly, if dirty data is detected, the processing result is also invalid, and if the processing is not idempotent, it may not be possible to roll back directly, complicating error recovery logic.
If further business processing is needed with this data, the already read data copy can be used, executed outside the while loop, at which point the data has been validated and is accurate and consistent.
2. Writer Thread Code Template
Write operations are mutually exclusive, so when performing write operations, a write lock must be requested, and the lock must be released after writing. In programming practice, a lock_guard related operation can be provided for the sequential lock according to the RAII convention to implement automatic lock release functionality.
seqlock.write_lock();
...... // Perform write operation
seqlock.write_unlock();Characteristics
1. Read operations do not hold locks, so reading does not affect writing. During read operations, write operations can proceed simultaneously. Read-read operations are not mutually exclusive, and read-write operations are also not mutually exclusive; only write-write operations are mutually exclusive.
2. Because there are no locks between reads and writes, unlike traditional read-write locks, read operations do not have lock and unlock interfaces. Instead, they first obtain a sequence number and validate it after reading.
3. Although it uses a method similar to the CAS algorithm, there is no ABA problem because when a writer acquires the lock, the sequence number is incremented by 1, and when releasing the lock, the sequence number is also incremented by 1, preventing the scenario where it increments and then decrements. Although the counter can overflow and return to 0, starting the cycle again, this is a lengthy process. During a single read operation, if the counter overflows, and during read_validate, the counter wraps back to the value read in read_entry(), the read operation must take a sufficiently long time, meaning that the time for a single read operation must exceed the time for 2^31 (i.e., 2 billion) write operations to encounter the ABA problem. If running in a 64-bit environment, where the counter is defined as atomic<uint64_t>, the time for a single read operation would need to exceed the time for 2^63 write operations to encounter the ABA problem.
4. It is suitable for scenarios where write operations have high priority and data types are simple, especially in real-time updating scenarios. For example, the clock’s periodic updates require the clock driver to write data strictly according to time intervals; it cannot delay writing due to not obtaining a lock, as that would lead to inaccurate time, as seen in the usage scenarios of sequential locks in the Linux kernel.
5. It is suitable for scenarios with many writes and few reads, as write operations do not compete with read operations, and read operations must first copy data, sometimes rolling back and re-reading, which is clearly more favorable for writers.
Example
Below is an example:
Assuming there is a 100Mb bandwidth network card on a 32-bit CPU processor receiving and sending Ethernet packets (frame length 1536 bytes), we want to count the number of packets received by the network card since booting. Since the bit count of the counter is 32 bits, it is treated as an unsigned integer with a maximum of 2^32-1. Given the 100Mb bandwidth, the number of packets received can overflow the 32-bit counter in about 6 days. Clearly, using a 32-bit counter is not feasible, as a 32-bit system cannot provide a higher precision counter, such as a 64-bit counter. We can consider using a combination of two 32-bit counters: one for the low 32 bits and another for the high 32 bits, requiring atomic operations for reading and writing them. The network card driver acts as the writer, updating the statistics (immediate), while the application acts as the reader, querying when needed (random).
Typically, since atomic operations are required for both variables, locks must be used for protection. If mutexes or general read-write locks are used, they can meet the requirements, but the read and write operations are mutually exclusive, causing the writer to compete for the lock with the reader, which is not suitable in this scenario. The network card driver may be in a waiting state while the reader holds the lock, and the waiting time is uncertain (since the reader is a user thread, it may be preempted and perform time-consuming operations). Clearly, if network packets arrive at this time, the driver cannot receive them in time, leading to the network card buffer filling up and packets being discarded. Therefore, the writer must not be allowed to wait.
The sequential lock perfectly meets this requirement, making it a very suitable solution. The network card driver, as the writer, can update these two statistical counters at any time. For readers, since the statistical counters are two variables, they must read them in a complete update, ensuring that the low 32 bits are from this update and the high 32 bits are from the previous update. Clearly, the read operation of the sequential lock can also meet this requirement.
Below is a simulated example code snippet:
// Packet statistics structure
struct pkt_counter {
uint32_t low;
uint32_t high;
};
// Initialize statistical variables, which are shared variables
static pkt_counter s_counter{0, 0};
void test() {
seq_lock seqlock;
srand(time(nullptr));
// Writer periodically updates the counter
thread writer([&seqlock]() {
for (int i=0; i<10; i++) {
seqlock.write_lock();
uint32_t old = s_counter.low;
s_counter.low += rand()%10000;
if (old > s_counter.low) { // Low 32 bits overflow, high 32 bits increment
s_counter.high++;
}
seqlock.write_unlock();
this_thread::sleep_for(chrono::milliseconds(500));
}
});
writer.detach();
// Reader, randomly obtaining statistical information
for (int i=0; i<10; i++) {
pkt_counter counter; // Copy
int seq;
do {
seq = seqlock.read_entry();
counter.low = s_counter.low;
counter.high = s_counter.high;
} while (!seqlock.read_validate(seq));
string counter64 = ::to_string(counter.high) + ::to_string(counter.low);
cout << "read:" << counter64 << endl;
this_thread::sleep_for(chrono::milliseconds(rand()%500+i*50));
}
}In this example, assuming the data read needs to be represented as a string, the two high and low 32-bit numbers are combined into a single 64-bit number represented as a string, stored in counter64. When reading data, it uses a temporary object counter to receive the data, which incurs very low overhead, only involving two integer assignment operations. After the while loop ends, the merging and conversion processing is performed.