1. Basic concepts of locks

1.1 CAS and Polling

1.1.1 Cas Locks

CAS is more and more used in the realization of the lock. The CAS instruction of the processor is used to exchange the value of a given variable to obtain the lock

1.1.2 polling lock

In the case of concurrent multi-threading, it is likely that some thread CAS will fail, and it is usually used in conjunction with the for loop to try to retrieve the lock by polling

1.2 Fairness of locks

In terms of fairness, locks are usually divided into fair locks and unfair locks. It mainly depends on whether the thread that obtains the lock first obtains the lock before the subsequent thread in the process of acquiring the lock. If so, it is a fair lock: multiple threads acquire the lock in the sequence of acquiring the lock; otherwise, it is unfair

1.3 Hunger and Queuing

1.3.1 lock hunger

Lock hunger refers to the fact that because a large number of threads are trying to acquire locks at the same time, some threads may fail to obtain locks during the CAS process and thus fail to obtain locks for a long time

1.3.2 Queuing mechanism

As mentioned above, CAS and polling lock are used to acquire locks. It can be found that if a thread has already acquired the lock, but when the current thread fails to obtain the lock in multiple polling, there is no need to waste system resources by repeated attempts. A queuing mechanism is usually used to queue and wait

1.4 a count

Most programming languages use a 32-bit integer to store the state of a CAS-based lock

2. The mutex

2.1 Member variables and patterns

2.1.1 Member Variables

In GO mutex, there are only two core member variables, state and SEMA, which count locks through state and queue through SEMA

type Mutex struct {
    state int32
    sema  uint32
}Copy the code

2.1.2 lock mode

There are two main types of locking modes


 describe fairness
Normal mode In normal mode, all goroutine locks are acquired in FIFO order. The lock is acquired simultaneously by the awakened Goroutine and the newly requested goroutine. In general, the newly requested goroutine is easier to obtain the lock no
Starvation mode In hunger mode, all goroutines that attempt to acquire locks are queued. New goroutines that request locks are not queued, but join the end of the queue to acquire locks is

Above you can see it in normal mode, the performance of the lock is actually the highest if multiple lock goroutine to obtain immediately after release can avoid multiple threads lined up to consume the same after the switch to starvation mode, when get the lock, if meet the certain conditions will switch back to the normal mode, so as to ensure the high performance of the lock

2.2 the lock count

2.2.1 lock state

In mutex, the lock has three flag bits, among which the binary bits are 001(mutexLocked), 010(mutexWoken) and 100(mutexStarving). Note that these three are not mutually exclusive. For example, the state of a lock may be locked starvation mode and has been woken up

    mutexLocked = 1 << iota // mutex is locked
    mutexWoken
    mutexStarvingCopy the code

2.2.2 Wait Count

Mutex stores the three states of the current MUtex through the lower three bits, and the remaining 29 bits are all used to store the number of goroutines trying to acquire locks

    mutexWaiterShift = iota // 3Copy the code

2.3 Wake Up Mechanism

2.3.1 Wake up flag

The wake up flag is used to indicate whether or not a goroutine is currently in the wake state. Remember that in fair mode, the goroutine currently running on the CPU may acquire the lock first

2.3.2 Wake up process

If a goroutine is currently in the wake state when the lock is released, change the lock state to unlock, and the goroutine in woken state can directly acquire the lock. Otherwise, you need to wake up a Goroutine and wait for the goroutine to change its state to mutexWoken before exiting

2.4 Lock process

2.3.1 Fast Mode

If there is no Goroutine lock and the CAS succeeds, the lock succeeds

        // Fast path: grab unlocked mutex.
    if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
        if race.Enabled {
            race.Acquire(unsafe.Pointer(m))
        }
        return
    }Copy the code

2.3.2 Spin and wake up

// Notice that there are actually two pieces of information here. One is if the current state is already locked, then allow the spin iter to basically count the number of spins and actually only allow 4 spins. Will immediately try to the following the logic of acquiring a lock if old & (mutexLocked | mutexStarving) = = mutexLocked && runtime_canSpin (iter) {/ /! Awoke if the current thread is not in a awoke state // old&mutexWoken == 0 If there are no other awoke nodes currently, put the current one in a awoke state // old>>mutexWaiterShift! = 0: three moves to the right, if not a 0, suggests that the current has a waiting goroutine pareAndSwapInt32 / / atomic.Com (& Margaret spellings Tate, old, old | mutexWoken) sets the current status to awaken the if condition! awoke && old&mutexWoken == 0 && old>>mutexWaiterShift ! = 0 && atomic.Com pareAndSwapInt32 (& Margaret spellings Tate, old, old | mutexWoken) {awoke = true} / / try to spin, Runtime_doSpin () // spin count iter++ // new state old = m.state continue}Copy the code

2.3.3 Changing the Lock Status

There are two possibilities: 1. The lock state is not locked. 2. Spin is no longer allowed when the specified number of spins is exceeded

New := old if old&mutexmedicine == 0 {// The locks here can actually try to obtain the | = in fact, the lock of the bit is set to 1 lock state new | = mutexLocked} if old & (mutexLocked | mutexStarving)! New += 1 << mutexWaiterShift} if medicine && old&mutexLocked! = 0 {/ / if the current has been hungry, and the current lock or occupied, then try to starvation mode switch new | = mutexStarving} if awoke {if new&mutexWoken = = 0 {throw (" sync: Inconsistent mutex state")} // a awoke state of mutexWoken was successful when the current thread spun above // Why eliminate the awoke flag? // It is possible that the thread will be suspended and will wait for another goroutine to wake it up. The thread can no longer wake up and lock new &^= mutexWoken}Copy the code

2.3.3 Lock queuing and State Transition

Only one goroutine locks successfully, and the rest of the threads need to reacquire the state, recalculate the spin and wake states, and repeat the CAS

if atomic.CompareAndSwapInt32(&m.state, old, {if old & new) (mutexLocked | mutexStarving) = = 0 {/ / if the original state is equal to 0 indicates the current has released the lock and no starvation mode / / actual binary bits that may be 1111000, the three are all zero, If waitStatrTime is not set to 0, the current thread is queued again. If waitStatrTime is not set to 0, the current thread is queued again. QueueLifo := waitStartTime! QueueLifo := waitStartTime! WaitStartTime == 0 {waitStartTime = runtime_nanotime()} runtime_SemacquireMutex(&m.sema, QueueLifo) queueLifo: starving=true Is starving to false / / will trigger the state switching starving = starving | | runtime_nanotime () - waitStartTime > starvationThresholdNs / / retrieves state  old = m.state if old&mutexStarving ! = 0 {/ / if it is found that the current paradigm is hunger, pay attention to awaken the mode of hunger is the first goroutine / / current all goroutine standing in line waiting for / / consistency check, if old & (mutexLocked | mutexWoken)! = 0 || old>>mutexWaiterShift == 0 { throw("sync: Inconsistent MUtex state")} delta := int32(mutexLocked - 1<<mutexWaiterShift) if! Starving | | old > > mutexWaiterShift = = 1 {/ / if the current goroutine is not hungry, Delta -= mutexmedicine} // Final cas operation // a ~ of work // awoke = true iter = 0} else {old = m.state}Copy the code

2.5 Releasing lock Logic

2.5.1 Releasing the lock Code

Func (m *Mutex) Unlock() {if race.enabled {_ = m.state race.release (unsafe.pointer (m))} // Directly perform cas operations new := atomic.AddInt32(&m.state, -mutexLocked) if (new+mutexLocked)&mutexLocked == 0 { throw("sync: Unlocked of unlocked mutex")} if new&mutexmedicine == 0 {// Old := new for {if old>>mutexWaiterShift == 0  || old&(mutexLocked|mutexWoken|mutexStarving) ! = 0 {// If there is already a wait and it has been woken up, return} // subtract a wait count, And then switch to the current mode mutexWoken new = (old - 1 < < mutexWaiterShift) | mutexWoken if atomic.Com pareAndSwapInt32 (& Margaret spellings Tate, old, New) {// Wake up a Goroutine runtime_Semrelease(&m.sema, False) return} old = m.state}} else {// Wake up the waiting thread runtime_Semrelease(&m.sema, true)}}Copy the code

This article is published by OpenWrite!