When implementing locks, it is necessary to ensure the memory order semantics of the lock: generally, an acquire memory order is required when acquiring the lock, and a release memory order is required when releasing the lock. This acquire-release semantics guarantees that memory read and write operations in the critical section do not get reordered before acquiring the lock and after releasing the lock, thus ensuring the happen-before relationship of acquiring the lock -> shared variable read/write operations -> releasing the lock. Additionally, it guarantees the happen-before relationship between releasing the lock and acquiring the lock across threads.
Sequential consistency memory order can ensure the above semantics. Therefore, in the previous article, the read-write spinlock scheme with a preference for write locks was introduced, where the memory order of atomic operations, except for local spinning which used memory_order_relaxed, the other memory orders used are the default implementation, which is the safest sequential consistency: memory_order_seq_cst. However, it is not necessary to use seq_cst everywhere; a more relaxed memory order can be chosen based on the scenario to improve performance. This article will briefly introduce the selection of memory orders in this scheme.
The following are the implementations of various read-write lock functions mentioned above:
1. Requesting and acquiring a read lock
Function to acquire a read lock:
void rw_spin_lock::lock_reader() noexcept { while (true) { // Position A, local spin waiting for write lock to be released while (write_flag.load(memory_order_relaxed)) { pause_cpu(); } // Position B, write lock has been released, increment reader counter read_counter.fetch_add(1); // Position C, check if the write lock has been acquired again if (write_flag.load()) { // Position D, roll back the read lock counter to its original state read_counter.fetch_sub(1); } else { break; } }Function to release a read lock:
void rw_spin_lock::unlock_reader() noexcept { // Position E read_counter.fetch_sub(1);}First, since the shared variables protected by the read lock are all read operations, multiple readers can hold the read lock simultaneously. Therefore, there is no need for a happen-before relationship between the release and acquisition of the read lock. However, the acquisition and release of the read lock still require acquire and release memory orders to ensure that memory read operations in the critical section cannot be reordered before acquiring the lock and after releasing the lock. Thus, acquiring the lock must ensure that memory read operations after write_flag.load() at Position C cannot be reordered before it, so acquire memory order can be used. Releasing the lock must ensure that memory read operations before read_counter.fetch_sub() at Position E cannot be reordered after it, so release memory order can be used.
Secondly, after a reader acquires the read lock and accesses memory variables, it must ensure that it can see the results of memory write operations before the write lock is released. The write_flag is a synchronization variable between the read lock and the write lock. When the write lock is released, the write_flag.store() write operation can use release memory order, thus establishing a happen-before relationship between the thread releasing the lock and the thread acquiring the lock at Position C.
Finally, let’s look at the memory order between the two atomic variables write_flag and read_counter.
The write_flag.load() operation at Position A is just local spinning and does not participate in synchronization operations, so it does not require memory order, thus using the best performance relaxed memory order.
At Position B, the read_counter.fetch_add() read-modify-write operation can be reordered to execute before the write_flag.load() read operation at Position A, meaning that the write lock may still be held by the writer or is in the process of being requested when the reader optimistically attempts to acquire the lock. Since whether the read lock can be successfully obtained must be determined at Position C, and since it has been reordered to execute before Position A, it cannot be reordered to execute after Position C, this reordering execution is acceptable.
However, this read_counter.fetch_add() operation cannot be reordered to execute after the write_flag.load() read operation at Position C (or in other words, the write_flag read operation cannot be reordered to execute before read_counter). Otherwise, if both the reader and writer attempt to acquire the lock simultaneously, it may lead to both obtaining the read lock and the write lock. The table below lists a possible erroneous execution order if the two are reordered.
Assumption: write_flag==false, read_counter==0, meaning both the write lock and read lock have been released.
| Order | Reader calls lock_reader() | Writer calls lock_writer() | Description |
| 1 | r1=write_flag | Reader reads write_flag out of order, its value false is read into register r1 | |
| 2 | write_flag.compare_exchange_strong(false, true) | Writer requests the lock, write_flag successfully changes from false to true | |
| 3 | r2=read_counter | Writer reads the value of read_counter 0 into register r2 | |
| 4 | read_counter.fetch_add(1) | read_counter increment operation is reordered to execute after write_flag | |
| 5 | r2 == 0 ? | Since r2==0, the writer believes all read locks have been released, and it successfully obtains the write lock | |
| 6 | r1 == false? | Since r1==false, the reader believes the writer has released it, and it successfully obtains the read lock |
To ensure that the two do not get reordered, either acquire memory order must be used above read_counter.fetch_add(), or release memory order must be used above write_flag.load(). However, since write_flag.load() is a read operation, it cannot use release memory order, so only acquire memory order can be used above read_counter.fetch_add().
The read_counter.fetch_sub() operation at line D is due to the operation when the request for the read lock fails, and since it goes back to loop after failure, it does not need to guarantee memory access order, and it also uses relaxed memory order.
Therefore, the memory order related to the read lock can be optimized as follows:
void rw_spin_lock::lock_reader() noexcept { while (true) { while (write_flag.load(memory_order_relaxed)); read_counter.fetch_add(1, memory_order_acquire); if (write_flag.load(memory_order_acquire)) { read_counter.fetch_sub(1, memory_order_relaxed); } else { break; } }And
void rw_spin_lock::unlock_reader() noexcept { // E read_counter.fetch_sub(1, memory_order_release);}2. Requesting and releasing a write lock
Function to request the lock:
void rw_spin_lock::lock_writer() noexcept { bool expect; do { // Position F wait for write lock to be released while (write_flag.load(memory_order_relaxed)) { pause_cpu(); } expect = false; // Position G, if another writer has set this flag, continue spinning } while (!write_flag.compare_exchange_strong(expect, true)); // Position H wait for all readers to release the read lock while (read_counter.load() != 0) { pause_cpu(); }}Function to release the lock:
void rw_spin_lock::unlock_writer() noexcept { // Position I write_flag = false;}In the write lock, write_flag and read_counter are both synchronization variables. The write_flag is used between acquiring and releasing the write lock, while read_counter is used between releasing the write lock and acquiring the read lock. Therefore, they need to ensure memory order, and there must also be memory order between them.
First, let’s look at the memory order between them.
The write_flag.compare_exchange_strong() at Position G and read_counter.load() at Position H cannot be reordered; otherwise, it may happen that the reader preemptively acquires the read lock before the write lock has been successfully requested, leading to the error of both the read lock and write lock being occupied simultaneously. The table below lists a possible erroneous execution order if both the write lock and read lock are requested simultaneously and if they are reordered.
Assumption: write_flag==false, read_counter==0, meaning both the write lock and read lock have been released.
| Order | Writer calls lock_writer() | Reader calls lock_reader() | Description |
| 1 | r1=read_counter | Writer reads the operation of read_counter out of order, its value 0 is read into register r1 | |
| 2 | read_counter.fetch_add(1) | Reader optimistically attempts to acquire the lock, read_counter becomes 1 | |
| 3 | r2=write_flag | Reader reads the value of write_flag false into register r2 | |
| 4 | write_flag.compare_exchange_strong(false, true) | Writer requests the lock, write_flag successfully changes from false to true | |
| 5 | r1 == 0 ? | Since r1==0, the writer believes all read locks have been released, and it successfully obtains the write lock | |
| 6 | r2 == false? | Since r2==false, the reader believes the writer has released it, and it successfully obtains the read lock |
To ensure that the two do not get reordered, either acquire memory order must be used above write_flag.compare_exchange_strong(), or release memory order must be used above read_counter.load(). However, since read_counter.load() is a read operation, it cannot use release memory order, so only acquire memory order can be used when the write_flag.compare_exchange_strong() operation is successful.
Acquiring the write lock and releasing the read lock must form acquire-release memory order semantics to ensure the happen-before relationship between threads. Therefore, read_counter.load() at Position H must use acquire memory order, which can be guaranteed by the release memory order when releasing the read lock.
Additionally, acquiring the write lock and releasing the write lock must also form acquire-release memory order semantics. Therefore, the write_flag.compare_exchange_strong() operation can use acquire memory order when successful, ensuring that the read_counter.load() does not get reordered, as the latter has already used acquire memory order, ensuring that subsequent memory read and write operations in the critical section do not get reordered before read_counter.load(). The write lock release function unlock_writer() can use release memory order, thus ensuring that acquiring and releasing the write lock also guarantees acquire-release memory order semantics.
Therefore, the memory order for the atomic variables in the write lock can be optimized as follows:
Function to request the lock:
void rw_spin_lock::lock_writer() noexcept { bool expect; do { while (write_flag.load(memory_order_relaxed)) { pause_cpu(); } expect = false; } while (!write_flag.compare_exchange_strong(expect, true, memory_order_acquire, memory_order_relaxed)); while (read_counter.load(memory_order_acquire) != 0) { pause_cpu(); }}Function to release the lock:
void rw_spin_lock::unlock_writer() noexcept { write_flag.store(false, memory_order_release);}3. Acquiring the write lock and acquiring the read lock
Another scenario to consider is the memory order between acquiring the write lock and acquiring the read lock, where the synchronization variables involved are write_flag and read_counter.
Let’s look at the core code when write_flag=false and read_counter=0, and the reader and writer are competing for the lock:
Acquiring the read lock:
while (true) { read_counter.fetch_add(1, memory_order_acquire); if (write_flag.load(memory_order_acquire)) { read_counter.fetch_sub(1, memory_order_relaxed); }}First, use fetch_add() to update the atomic variable read_counter, referred to as “write C”, and then read the atomic variable write_flag, referred to as “read F”. According to their memory orders, the two cannot be reordered, i.e., the execution order must be “write C -> read W”.
Acquiring the write lock:
bool expect;do { expect = false;} while (!write_flag.compare_exchange_strong(expect, true, memory_order_acquire, memory_order_relaxed)); while (read_counter.load(memory_order_acquire) != 0) { pause_cpu();}First, use compare_exchange_strong() to update the atomic variable write_flag, referred to as “write F”, and then read the atomic variable read_counter, referred to as “read C”. According to their memory orders, when the CAS operation is successful, the two cannot be reordered, i.e., the execution order must be “write F -> read C”.
When the reader thread and writer thread simultaneously attempt to acquire the read lock and write lock, intuitively analyzing these atomic operations’ execution can lead to the following six scenarios (the numbers indicate the execution order):
| 1 | 2 | 3 | 4 | Requested Lock |
|
write C=1 |
read F=false |
write F=true |
read C=1 |
Read Lock |
|
write C=1 |
write F=true | read F=true | read C=1 | Write Lock |
|
write C=1 |
write F=true | read C=1 | read F=true | Write Lock |
| write F=true | read C=0 | write C=1 | read F=true | Write Lock |
| write F=true | write C=1 | read C=1 | read F=true | Write Lock |
| write F=true | write C=1 | read F=true | read C=1 | Write Lock |
However, the reader thread’s “read F -> write C” operation and the writer thread’s “write F -> read C” operation do not have sequential consistency, and cannot guarantee the order between threads. For instance, in the first scenario in the table, when the writer thread reads C in step 4, it may see C=0, at which point the writer can successfully acquire the lock. Similarly, in the fifth scenario, when the reader thread reads F in step 4, it may see F=false, allowing the reader to successfully acquire the lock. Other scenarios are similar, leading to the possibility of both the reader and writer obtaining the lock simultaneously.
In summary, under the current applied memory orders, assuming the reader thread operates as “write C -> read F” and the writer thread operates as “write F -> read C”, the memory order that the reader may see is “write C -> read F -> write F -> read C”, while the memory order that the writer sees may be “write F -> read C -> write C -> read F”, allowing both the reader and writer to successfully acquire their respective locks.
The reason is that the write W and write C operations are independent, and there is no single global order, preventing all CPUs from seeing the results of these memory write operations in a consistent order. Therefore, the memory order semantics of these two atomic operations are too weak and should be strengthened to sequential consistency, i.e., memory_order_seq_cst, ensuring that the six scenarios in the table can be guaranteed.
4. Final Memory Order
Function to acquire the read lock:
void rw_spin_lock::lock_reader() noexcept { while (true) { while (write_flag.load(memory_order_relaxed)); read_counter.fetch_add(1, memory_order_seq_cst); if (write_flag.load(memory_order_acquire)) { read_counter.fetch_sub(1, memory_order_relaxed); } else { break; } }Using memory_order_seq_cst at line 4 ensures that it will not be reordered forward or backward.
Function to attempt to acquire the read lock:
bool rw_spin_lock::try_lock_reader() noexcept { if (write_flag.load(memory_order_relaxed)) { return false; } read_counter.fetch_add(1, memory_order_seq_cst); if (write_flag.load(memory_order_acquire)) { read_counter.fetch_sub(1, memory_order_relaxed); return false; } else { return true; }}Function to release the read lock:
void rw_spin_lock::unlock_reader() noexcept { read_counter.fetch_sub(1, memory_order_release);}Function to acquire the write lock:
void rw_spin_lock::lock_writer() noexcept { bool expect; do { while (write_flag.load(memory_order_relaxed)) { pause_cpu(); } expect = false; } while (!write_flag.compare_exchange_strong(expect, true, memory_order_seq_cst, memory_order_relaxed)); while (read_counter.load(memory_order_acquire) != 0) { pause_cpu(); }}Function to attempt to acquire the write lock:
bool rw_spin_lock::try_lock_writer() noexcept { if (write_flag.load(memory_order_relaxed)) { return false; } bool expect = false; if (!write_flag.compare_exchange_strong(expect, true, memory_order_seq_cst, memory_order_relaxed)) return false; if (read_counter.load(memory_order_acquire) == 0) return true; else { write_flag.store(false, memory_order_relaxed); return false; }}Function to release the write lock:
void rw_spin_lock::unlock_writer() noexcept { write_flag.store(false, memory_order_release);}