In Go’s Great Mutex Design, we went into detail on how mutex is implemented. A mutex avoids a race condition by allowing only one thread to enter the critical section of the code, which reduces the efficiency of the program. At the same time, we know that only when multiple threads have write operations in the shared resource, will race problem occur. As long as the resource has not changed, it is safe for multiple threads to read the same resource. Therefore, we have developed a more fine-grained lock: read-write locks.

What is a read-write lock

A read-write lock is a multiple-read single-write lock. Multiple threads can add a read-write lock at the same time. However, a read-write lock is mutually exclusive with a read-write lock and with a read-write lock.

The read-write lock handles critical sections as shown in the figure above. At time T1, thread 1 has a write lock, and thread 2 is mutex waiting for the release of the write lock. At t2, thread 2 has read the lock, and thread 3 can continue to read the lock and enter the critical section. At t3, thread 3 has a read lock and thread 4 is mutex waiting for the read lock to be released.

hunger

Based on the nature of the read/write lock, the reader should guess that the read/write lock is suitable for read-write scenarios. According to the priority, it can be classified into read priority lock and write priority lock. Read priority locking allows maximum concurrency, but the writer thread may starve to death. Similarly, a write priority lock preferentially serves the writer thread so that the reader thread can starve to death.

Write lock hunger is a relatively prominent problem. Since read locks are shared, if the current critical section has a read lock, it is ok for subsequent threads to add a read lock. However, if the thread that has a read lock is locked, the thread that is trying to add a write lock will not be able to acquire the lock. In this way, the thread that is trying to add a write lock will be blocked, resulting in write lock starvation.

At the same time, since multiple read locks are shared, readers may ask: why not just remove the read lock and only add the write lock when the write operation thread comes in? If the current critical section has a write lock, a new write thread will enter before the lock is unlocked. When the lock is released, the new write thread will be locked again. If this happens continuously, the entire program can only execute the write thread and the read thread will starve to death.

Therefore, in order to avoid the hunger problem, the general practice is to achieve fair read and write lock, it will request the thread of the lock queue, to ensure that the first in first out (FIFO) principle of locking, so that it can effectively avoid the thread hunger problem.

How does Go’s read-write lock deal with hunger?

Go read and write lock design

The code version for this article is Go 1.15.2. As shown below, the sync.RWMutex structure contains five fields.

type RWMutex struct {
	w           Mutex  
	writerSem   uint32 
	readerSem   uint32 
	readerCount int32  
	readerWait  int32  
}
Copy the code
  • wThe mutexsync.MutexFor mutually exclusive write operations.
  • writerSemThe write operation Goroutine blocks waiting for the semaphore. When the last blocking read goroutine releases the read lock, the blocking write lock goroutine is notified.
  • readerSemThe read operation Goroutine blocks waiting for the semaphore. When the write lock goroutine releases the write lock, it notifys the blocking read lock Goroutine.
  • readerCountNumber of Read goroutine operations.
  • readerWaitNumber of Read Goroutines that block write goroutines.

In this case, you may not be able to understand some of the fields in the mutex, but after you read the four method interfaces provided by Sync.rwmutex, you will understand.

  • RLock(): read lock
  • RUnlock()Interpretation: lock
  • Lock(): write locks
  • Unlock(): write locks

Now, let’s analyze them in turn.

Add read lock

It should be noted here that all of the code blocks in this article have removed the logical part of race detection, namely the if race.enabled {} method block, for better understanding of the code logic.

func (rw *RWMutex) RLock(a) {
	if atomic.AddInt32(&rw.readerCount, 1) < 0 {
		runtime_SemacquireMutex(&rw.readerSem, false.0)}}Copy the code

Atomic.AddInt32 is an atomic operation that is encapsulated underneath by the hardware instruction LOCK (see “Building blocks of synchronization Primitors” for more details). ReaderCount represents the number of read goroutine operations. If the number is +1 and less than 0, block until the write lock is released through the sleep primitive runtime_SemacquireMutex used for the synchronization library.

Simply put, if a goroutine has already been written, the new goroutine will be queued and blocked. However, readers must find the criteria strange. Why is rw.readerCount negative? Don’t worry, the answer will be found below.

Of course, if there is no write lock, then simply increase the rw.readerCount by 1 and exit.

Interpretation of the lock

func (rw *RWMutex) RUnlock(a) {
	if r := atomic.AddInt32(&rw.readerCount, - 1); r < 0 {
		rw.rUnlockSlow(r)
	}
}
Copy the code

If the number of goroutine is greater than or equal to 0, then the lock is read successfully. Otherwise, enter the following rUnlockSlow logic with the number r currently in negative value

func (rw *RWMutex) rUnlockSlow(r int32) {
	if r+1= =0 || r+1 == -rwmutexMaxReaders {
		race.Enable()
		throw("sync: RUnlock of unlocked RWMutex")}if atomic.AddInt32(&rw.readerWait, - 1) = =0 {
		runtime_Semrelease(&rw.writerSem, false.1)}}Copy the code

If r+1==0, then we show that the lock was not read; RwmutexMaxReaders = 1 << 30, which represents the maximum number of goroutine read operations that the read/write lock can receive. R +1 == -rwmutexmaxReaders (r+1 == -rwmutexmaxReaders) Reading a lock on a lock without a read lock will throw an exception and cause a panic.

ReaderWait indicates the number of goroutine read operations when a write operation is blocked. If the value is 1, indicating that the current goroutine is the last blocking write, the blocking goroutine is awakened by the runtime_Semrelease wakeup primitive for the synchronization library.

At this point, the reader only reads the code that adds and unreads the lock, it will be difficult to understand, do not worry, let’s continue to look at the logic that adds and unwrites the lock.

Add write lock

func (rw *RWMutex) Lock(a) {
	rw.w.Lock()
	r := atomic.AddInt32(&rw.readerCount, -rwmutexMaxReaders) + rwmutexMaxReaders
	ifr ! =0&& atomic.AddInt32(&rw.readerWait, r) ! =0 {
		runtime_SemacquireMutex(&rw.writerSem, false.0)}}Copy the code

When a write lock is applied, the mutex lock is applied first, which ensures that only one write lock will be applied successfully. When the mutex locks successfully, we can see how the write prevents the read, and how the read is aware of the write.

We already know that readerCount is the number of goroutine read operations. If there is no write operation, this value will be +1 for each read lock and -1 for each read lock. ReaderCount = [0,rwmutexMaxReaders]; the maximum number of concurrent reads is 2^30; the minimum number is 0.

However, after the current goroutine is added with a mutex, the atomic operation atomic.addint32 subtracts the readerCount by 2^30. At this point, the readerCount becomes a negative value. If any subsequent goroutine is added with a lock, This value can be used to know that there is a write lock and block the wait. This also explains the issues left in the reading locks and reading locks sections. Finally, to hold the true number of goroutine reads, add back 2^30.

It is important to note that success in mutex locking does not mean success in write locking. We need to know how a read prevents a write and how a write is aware of a read.

r ! = 0 indicates that the current goroutine is not zero, which means that the write lock is applied until the previous read is finished. ReaderCount is copied to rw.readerWait using atomic.AddInt32 to mark the number of read Goroutines that precede write goroutines. Blocking waits for these reads to finish through the sleep primitive runtime_SemacquireMutex used for the synchronization library. ReaderWait (rw. ReaderWait (rw. ReaderWait (rW. ReaderWait (rW.

Solutions of the write lock

func (rw *RWMutex) Unlock(a) {
	r := atomic.AddInt32(&rw.readerCount, rwmutexMaxReaders)
	if r >= rwmutexMaxReaders {
		race.Enable()
		throw("sync: Unlock of unlocked RWMutex")}for i := 0; i < int(r); i++ {
		runtime_Semrelease(&rw.readerSem, false.0)
	}
	rw.w.Unlock()
}
Copy the code

When unlocking a write lock, change the rw.readerCount from a negative value to a positive value, release the mutex for the read lock, and wake up r goroutine that are blocked because of the write lock. Finally, the write lock is unexclusive by calling the Unlock method of the mutex.

At this point, we can illustrate how Go solves the problem of hunger.

Suppose G1, G2, and G3 are goroutines that are being read, and the value of rw.readerCount is 3. At this point the write operation G4 comes in, turns the rw.readerCount value negative, and finds that rw.readerCount is not zero, so it blocks and waits. But while G4 is waiting, new read operations G5, G6 and write operations G7 come in. ReaderCount (rw. ReaderCount) is negative, so G5 and G6 cannot add the lock successfully and will be blocked. G7 is also stuck waiting because G4 has a mutex. G3 wakes up G4 when the last read operation preceding the write operation G4 is finished. When G4 ends, it wakes up G5, G6, and G7. But G7 needs to wait for G5 and G6 to exit (because it will find that readerCount is not zero when it attempts to add a write lock) before it can successfully add a write lock. This is repeated to ensure that the read-write lock is relatively fair, to avoid one side starving.

conclusion

Read/write locks are based on mutex locks and provide more granular control. They are suitable for read-write scenarios where there are more read operations than write operations. In the scenario of more read and less write, using read/write lock instead of mutex lock can effectively improve the efficiency of the program.

Read sharing, read-write mutual exclusion, and write mutual exclusion. In terms of priority, there are several ways to favor read or write locks.

  • The lock is idle, and it is perfectly fair that whoever comes in first can lock it.
  • If there is no read, it is all write, and the read/write lock will degenerate into a mutex, which is only fair if the mutex is in starvation mode.
  • If there is no write, it is all read, and all reads can come in, and the read/write lock degrades to a lock-free design (which is not really lock-free, since both add and unlock have atomic operations)atomic.AddInt32Statistics on read operation Goroutine).
  • When a read lock is added, incoming write operations are blocked. While a write operation is blocking, if a read operation attempts to come in, they will also be blocked. When the last read that blocks a write reads the lock, it only wakes up the blocked write, and subsequent reads need to be woken up after the write has completed. These awakened reads get the lock before new writes (which can be new or blocked by the mutex), and wait until those reads complete before new writes get the lock.

Because read-write locks are designed on top of mutex locks, there is inevitably some extra work to be done. Therefore, it is not necessarily true that the benefits of using read-write locks are higher than mutex locks. When choosing which lock to use, consider the ratio of read and write operations and the time spent in critical section code. The content of performance comparison is not discussed in this article, the reader can test.