Interviewer: man, how much do you know about the read-write lock of go language?

Preface

hello , Hello everyone , I am a asong.

In the last article ： interviewer ： Brother Go To what extent has the language mutex been understood ？ We studied together Go How to implement mutex in language , In this article, we will study together Go How to design the read-write lock in language , Mutexes can ensure that multiple threads will not compete when accessing the same piece of memory to ensure concurrency safety , Because the mutex locks the critical area of the code , Therefore, when the concurrency is high, lock competition will intensify , The execution efficiency will be worse and worse ; Therefore, more fine-grained locks are derived ： Read-write lock , It is suitable for the situation of reading more and writing less , Next, let's take a detailed look at read-write locks .

Golang edition ：1.18

Introduction to read write lock

We all know that mutexes lock critical areas of code , When you have one goroutine After obtaining the mutex , whatever goroutine You can't get a mutex , Can only wait for this goroutine Release the mutex , No matter reading or writing, a big lock will be added , In the scenario of reading more and writing less, the efficiency will be very low , So the big guys designed a read-write lock , As the name suggests, a read-write lock is a lock divided into two parts ： Read lock and write lock , Read lock allows multiple threads to obtain at the same time , Because the read operation itself is thread safe , Write locks are mutually exclusive , Multiple threads are not allowed to obtain write locks at the same time , And write and read operations are mutually exclusive , In conclusion ： Reading is not mutually exclusive , Reading and writing are mutually exclusive , Writing mutually exclusive ;

Why is there a read lock

Some friends may have doubts , Why is there a read lock , The read operation does not modify the data , It is safe for multiple threads to read the same resource at the same time , Why add a read lock ？

Let me give you an example , stay Golang The assignment of variables in is not concurrency safe , For example, to a int Type variable execution count++ operation , Execution under concurrency will produce unexpected results , because count++ The operation is divided into three parts ： Read count Value 、 take count The value of the add 1, Then assign the result to count, This is not an atomic operation , When unlocked, execute on this variable in multiple threads at the same time count++ Operation will cause data inconsistency , This problem can be solved by adding a write lock , But what will happen if we don't apply read lock when reading ？ Write an example to see , Write lock only , No read lock ：

package main

import "sync"

const maxValue = 3

type test struct {
 rw sync.RWMutex
 index int
}

func (t *test) Get() int {
 return t.index
}

func (t *test)Set() {
 t.rw.Lock()
 t.index++
 if t.index >= maxValue{
  t.index =0
 }
 t.rw.Unlock()
}

func main()  {
 t := test{}
 sw := sync.WaitGroup{}
 for i:=0; i < 100000; i++{
  sw.Add(2)
  go func() {
   t.Set()
   sw.Done()
  }()
  go func() {
   val := t.Get()
   if val >= maxValue{
    print("get value error| value=", val, "\n")
   }
   sw.Done()
  }()
 }
 sw.Wait()
}

Running results ：

get value error| value=3
get value error| value=3
get value error| value=3
get value error| value=3
get value error| value=3
.....

The result of each run is not fixed , Because we didn't add read lock , If both reading and writing are allowed , The data read may be in the intermediate state , So we can conclude that it is necessary to read locks , Read lock can prevent reading the value in the middle of writing .

Queue jumping strategy of read-write lock

It is also thread safe when multiple read operations are performed at the same time , After a thread obtains a read lock , Another thread can also acquire a read lock , Because read locks are shared , If there are always threads with read locks , If a thread adds a write lock later, it will not get the lock all the time, causing blocking , At this time, some strategies are needed to ensure the fairness of the lock , Avoid lock hunger , that Go What queue jumping strategy does the read-write lock in the language use to avoid hunger ？

Here we use an example to illustrate Go Language queue jumping strategy ：

Suppose there are now 5 individual goroutine Namely G1、G2、G3、G4、G5, Now? G1、G2 Acquire read lock successfully , The read lock has not been released ,G3 To perform a write operation , Failure to acquire the write lock will block the wait , Read lock that currently blocks write lock goroutine The number of 2：

follow-up G4 Come in to get the read lock , At this time, she will judge if there is currently a write lock goroutine Blocking waiting , In order to avoid writing lock hunger , So this one G4 It will also enter the blocking waiting , follow-up G5 Come in and want to get the write lock , because G3 Occupying mutex , therefore G5 Will enter spin / Sleep Block waiting ;

Now? G1、G2 The read lock has been released , When the read lock is released, it is judged if the write lock is blocked goroutine Read lock goroutine The number of 0 If there is a write lock waiting, the blocking waiting write lock will wake up G3,G3 Wake up ：

G3 After processing the write operation, the write lock will be released , This step will wake up the waiting read lock at the same time / Write the lock goroutine, as for G4、G5 Who can get the lock first depends on who is faster , It's like robbing a daughter-in-law , First come, first served .

The realization of read-write lock

Next, let's go deep into the source code analysis , Have a look first RWMutex What are the structures ：

type RWMutex struct {
 w           Mutex  // held if there are pending writers
 writerSem   uint32 // semaphore for writers to wait for completing readers
 readerSem   uint32 // semaphore for readers to wait for completing writers
 readerCount int32  // number of pending readers
 readerWait  int32  // number of departing readers
}

• w： Reuse the capabilities provided by mutexes ;
• writerSem： Write operations goroutine Blocking wait semaphore , When blocking read operations for write operations goroutine When the read lock is released , This semaphore notifies blocked write operations goroutine;
• readerSem： Read operations goroutine Blocking wait semaphore , When writing goroutine When the write lock is released , This semaphore notifies blocked read operations goroutine;
• redaerCount： Currently executing read operation goroutine Number ;
• readerWait： Read operation waiting when write operation is blocked goroutine Number ;

Read the lock

The corresponding method of reading lock is as follows ：

func (rw *RWMutex) RLock() {
  //  Atomic manipulation readerCount  As long as the value is not negative, it means that the lock reading is successful 
 if atomic.AddInt32(&rw.readerCount, 1) < 0 {
  //  There is a write lock waiting , In order to avoid hunger, the reader lock coming in after blocking and waiting 
  runtime_SemacquireMutex(&rw.readerSem, false, 0)
 }
}

The method of race detection is simplified , There are only two lines of code for the lock reading method , The logic is as follows ：

Update with atomic operations readerCount, take readercount It's worth adding 1, As long as the value after atomic operation is not negative, it means that the read lock is successful , If the value is negative, it means that there has been a write lock to obtain the mutex successfully , Write lock goroutine Waiting or running , So in order to avoid hunger, the reader lock coming in behind should be blocked and waited , call runtime_SemacquireMutex Block waiting .

Non blocking read lock

Go Language in 1.18 A non blocking read lock method is introduced in ：

func (rw *RWMutex) TryRLock() bool {
 for {
    //  Read readerCount Value can know whether there is currently a write lock waiting for blocking , If the value is negative , Then the back read lock will be blocked 
  c := atomic.LoadInt32(&rw.readerCount)
  if c < 0 {
   if race.Enabled {
    race.Enable()
   }
   return false
  }
    //  Try to get a read lock ,for Try again and again 
  if atomic.CompareAndSwapInt32(&rw.readerCount, c, c+1) {
   if race.Enabled {
    race.Enable()
    race.Acquire(unsafe.Pointer(&rw.readerSem))
   }
   return true
  }
 }
}

Because read locks are shared , When there is no write lock blocking wait, multiple threads can acquire at the same time , So atomic operations may fail , Here the for Loop to increase the number of attempts , It's very clever .

Release read lock

The code for releasing read lock is mainly divided into two parts , The first part ：

func (rw *RWMutex) RUnlock() {
  //  take readerCount The value of the reduction 1, If the value is equal to 0 Just exit ; Otherwise enter rUnlockSlow Handle 
 if r := atomic.AddInt32(&rw.readerCount, -1); r < 0 {
  // Outlined slow-path to allow the fast-path to be inlined
  rw.rUnlockSlow(r)
 }
}

We all know readerCount The value of represents the currently executing read operation goroutine Number , The value after decrement is greater than or equal to 0 Indicates that there is no abnormal scenario or write lock blocking waiting , So just exit , Otherwise, you need to deal with these two logics ：

rUnlockSlow The logic is as follows ：

func (rw *RWMutex) rUnlockSlow(r int32) {
  // r+1 be equal to 0 It means to release the read lock without adding the read lock , Exception scenarios should throw exceptions 
  // r+1 == -rwmutexMaxReaders  It also means that if a read lock is not added, the read lock is released 
  //  Because when the write lock is successfully locked, it will readerCout The value of minus rwmutexMaxReaders
 if r+1 == 0 || r+1 == -rwmutexMaxReaders {
  race.Enable()
  throw("sync: RUnlock of unlocked RWMutex")
 }
 //  If there is a write lock waiting to be read, it will be updated readerWait Value , So step by step rw.readerWait value 
  //  If readerWait The value after atomic operation is equal to 0 It indicates that the read locks that currently block the write lock have been released , Need to wake up the waiting write lock 
 if atomic.AddInt32(&rw.readerWait, -1) == 0 {
  // The last reader unblocks the writer.
  runtime_Semrelease(&rw.writerSem, false, 1)
 }
}

Read this code ：

• r+1 be equal to 0 Show the current goroutine Release the read lock without adding the read lock , It's illegal
• r+1 == -rwmutexMaxReaders It means that writing lock and locking successfully will readerCount Subtraction of rwmutexMaxReaders Become negative , If there is no read lock before , Then directly releasing the read lock will cause this equation to hold , It also belongs to the operation of releasing the read lock without adding a read lock , It's illegal ;
• readerWait Represents the read operation when the write operation is blocked goroutine Number , If there is a write lock waiting, it will be updated readerWait Value , Required when reading lock and releasing lock readerWait Go down , If decreasing equals 0 It indicates that the read locks that currently block the write lock have been released , Need to wake up the waiting write lock .（ See the code of writing lock below to echo ）

Write lock

The corresponding method of writing lock is as follows ：

const rwmutexMaxReaders = 1 << 30
func (rw *RWMutex) Lock() {
 // First, resolve competition with other writers.
  //  Write lock is also called mutex lock , The ability to reuse mutexes to solve the competition with other write locks 
  //  If the write lock has been acquired , other goroutine It will enter spin or sleep when acquiring write lock 
 rw.w.Lock()
 //  take readerCount Set to negative , Tell the read lock that there is now a write lock waiting to run （ Get mutex successfully ）
 r := atomic.AddInt32(&rw.readerCount, -rwmutexMaxReaders) + rwmutexMaxReaders
 //  Success in obtaining the mutex does not mean goroutine Get write lock successfully , By default, we have 2^30 Number of read operations , Subtract this maximum number 
  //  Still not for 0 It means there is a read lock in front , You need to wait for the read lock to be released and update the read operation waiting when the write operation is blocked goroutine Number ;
 if r != 0 && atomic.AddInt32(&rw.readerWait, r) != 0 {
  runtime_SemacquireMutex(&rw.writerSem, false, 0)
 }
}

The amount of code is not very large , But it's a little complicated to understand , I try to analyze it in words , It is mainly divided into two parts ：

• Get mutex , Write lock is also called mutex lock , Here we reuse mutexes mutex Locking ability , When the mutex lock is successfully locked , Other write locks goroutine When you try to acquire the lock again, you will enter spin sleep and wait ;
• Judge whether the acquisition of write lock is successful , Here's a variable rwmutexMaxReaders = 1 << 30 Indicates maximum support for 2^30 Concurrent reads , After locking the mutex successfully , hypothesis 2^30 All the read operations have released the read lock , By atomic operation readerCount Set to a negative number plus 2^30, If at this time r Still not for 0 There are also read operations in progress , Then write the lock and wait , At the same time, update through atomic operation readerWait Field , That is, the read operation waiting when the update write operation is blocked goroutine Number ; readerWait Judge when reading and releasing the lock above , Go down , At present readerWait Descending to 0 It will wake up the write lock .

Non blocking write lock

Go Language stay 1.18 A non blocking locking method is introduced in ：

func (rw *RWMutex) TryLock() bool {
  //  First judge whether the mutex is obtained successfully , If not, return directly false
 if !rw.w.TryLock() {
  if race.Enabled {
   race.Enable()
  }
  return false
 }
  //  The mutex was successfully obtained , Next, judge whether there is a read lock blocking the write lock , If there is no direct update readerCount by 
  //  Negative number obtains write lock successfully ;
 if !atomic.CompareAndSwapInt32(&rw.readerCount, 0, -rwmutexMaxReaders) {
  rw.w.Unlock()
  if race.Enabled {
   race.Enable()
  }
  return false
 }
 return true
}

Release the write lock

func (rw *RWMutex) Unlock() {
 // Announce to readers there is no active writer.
  //  take readerCount The recovery of is positive , That is to remove the mutual exclusion of the read lock 
 r := atomic.AddInt32(&rw.readerCount, rwmutexMaxReaders)
 if r >= rwmutexMaxReaders {
  race.Enable()
  throw("sync: Unlock of unlocked RWMutex")
 }
 //  If there are read operations later goroutine You need to wake them up 
 for i := 0; i < int(r); i++ {
  runtime_Semrelease(&rw.readerSem, false, 0)
 }
 //  Release the mutex , Write operated goroutine And read operation goroutine Simultaneous competition 
 rw.w.Unlock()
}

The logic to release the write lock is relatively simple , Releasing the write lock will cause the read and write operations to meet goroutine All wake up , Then they are competing ;

summary

Because we have shared the implementation of mutex above , Look at the read-write lock again, it's much easier , At the end of the article, let's summarize the read-write lock ：

• The read-write lock provides four operations ： Read lock , Read unlock , Write lock , Write unlock ; The locking rule is read sharing , Writing mutually exclusive , Reading and writing are mutually exclusive , Writing and reading are mutually exclusive ;
• Read lock in read-write lock must exist , Its purpose is also to avoid the problem of atomicity , Only a write lock without a read lock will cause us to read the intermediate value ;
• Go The design of the read-write lock of the language also avoids the hunger of the write lock , Through fields readerCount、 readerWait Control , When writing lock goroutine When is blocked , Come in later to get the read lock goroutine Will also be blocked , When the write lock is released , The following read operations goroutine、 Write operated goroutine All wake up , Let them compete for the rest ;
• Read lock acquire lock process ：
• When the lock is idle , Read lock can be obtained immediately
• If a write lock is currently blocking , Then those who want to get the read lock goroutine Will be dormant
• Release the lock reading process ：
• Currently, there is no exception scenario or write lock blocking waiting , Then the read lock is directly released successfully
• If the read lock is released without adding a read lock, an exception is thrown ;
• In the scenario where the write lock is blocked and waiting by the read lock , Will readerWait Decrement the value of , readerWait Indicates blocking write operations goroutine Read operation goroutine Number , When readerWait Reduced to 0 Can wake up blocked write operations goroutine 了 ;
• Write lock acquire lock process
• Write lock reuse mutex The ability of mutex , First try to get the mutex , If you fail to acquire the mutex, you will enter the spin / Sleep ;
• Success in obtaining mutexes does not mean success in writing and locking , At this time, if there are people who occupy the read lock goroutine, Then it will block , Otherwise, the write lock will be added successfully
• Release the write lock process
• Releasing the write lock will result in a negative readerCount Become positive , Release the mutex of the read lock
• Wake up all currently blocked read locks
• Release the mutex

The amount of code for reading and writing locks is not much , Because it reuses the design of mutex , More work has been done on the function of read-write lock , It is much easier to understand than mutex , Have you learned ？ baby ～.

All right. , This is the end of the article , I am a asong, See you next time .

Created a reader exchange group , Welcome to join the group , Learn and communicate together . Entry mode ： Official account acquisition . More information on study, please go to the official account .