1 definition
1.1 Basic Concepts
A Mutual exclusion (Mutex) is a mechanism used in multithreaded programming to prevent two threads from simultaneously reading and writing to the same common resource (such as global variables). This is done by slicing the code into critical sections. A critical region is a piece of code that accesses a common resource, not a mechanism or algorithm. A program, process, or thread can have multiple critical regions, but mutex does not necessarily apply.
That’s the wikipedia definition of mutex, and Golang’s sync.mutex is a mutex implementation.
1.2 golang sync. Mutex
Efficiency gives priority to equity
Mutex in Golang is a fair lock, as explained in the source code:
// Mutex fairness.
//
// Mutex can be in 2 modes of operations: normal and starvation.
// In normal mode waiters are queued in FIFO order, but a woken up waiter
// does not own the mutex and competes with new arriving goroutines over
// the ownership. New arriving goroutines have an advantage -- they are
// already running on CPU and there can be lots of them, so a woken up
// waiter has good chances of losing. In such case it is queued at front
// of the wait queue. If a waiter fails to acquire the mutex for more than 1ms,
// it switches mutex to the starvation mode.
//
// In starvation mode ownership of the mutex is directly handed off from
// the unlocking goroutine to the waiter at the front of the queue.
// New arriving goroutines don't try to acquire the mutex even if it appears
// to be unlocked, and don't try to spin. Instead they queue themselves at
// the tail of the wait queue.
//
// If a waiter receives ownership of the mutex and sees that either
// (1) it is the last waiter in the queue, or (2) it waited for less than 1 ms,
// it switches mutex back to normal operation mode.
//
// Normal mode has considerably better performance as a goroutine can acquire
// a mutex several times in a row even if there are blocked waiters.
// Starvation mode is important to prevent pathological cases of tail latency.
Copy the codeThis explanation is the core of mutex. This is the whole idea of mutex. The translation is roughly as follows
// Fairness of mutex.
//
// Mutex operates in two modes: normal mode and hungry mode.
// In normal mode, goroutines requesting a lock are queued in FIFO(first in, first out) order, but awakened goroutines do not acquire the lock directly. Instead, they compete with new goroutines for ownership of the lock.
// But this is unfair, because new goroutines have an advantage: they are running on the CPU and there are likely to be a lot of them, so newly awakened Goroutines have a hard time acquiring the lock. In this case, if the goroutine fails to be fetched, it is inserted directly into the head of the queue.
// If a waiting goroutine is more than 1ms, the lock will be put into starvation mode.
//
// In hungry mode, mutex ownership is transferred directly from the unlocked Goroutine to the leading goroutine.
// And newly arrived goroutines do not attempt to acquire locks and are inserted directly at the end of the queue.
//
// If a waiting goroutine takes ownership of the lock, and one of the following two conditions is met:
// (1) It is the last goroutine in the queue
// (2) it waits less than 1 millisecond
// It switches the mutex back to normal mode.
//
// The common mode has better performance, because even if there are many blocking goroutines waiting for locks, one Goroutine can attempt to request more than one lock.
// The hungry mode avoids the bad case of tail delay.
Copy the code2 Memory Model
The code in the example is Golang 1.16.3, portal
2.1 Data Structure
// A Mutex is a mutual exclusion lock.
// The zero value for a Mutex is an unlocked mutex.
//
// A Mutex must not be copied after first use.
type Mutex struct {
state int32
sema uint32
}
Copy the codeSync. mutex has a very simple data structure, just two fields,
- The state field is the state of the mutex. The lower three bits of the binary correspond to the state of the lock. Shifting state to the right by three bits represents the number of mutex.
- The sema is used to wake up the goroutine.
These two comments are important
- The zero value guarantees that sync.mutex conforms to golang’s zero value semantics, i.e. the zero value of sync.mutex is an open mutex.
- Mutex data structures are not allowed to be copied. The result of copying mutex is undefined.
Key constants
Const (mutexLocked = 1 << iota // mutex is in locked state and corresponds to 0b001 mutexWoken 0b010 mutexWaiterShift = iota; // Shift the number of waiter to shift; State >> mutexWaiterShift to get the number of waiter messages. StarvationThresholdNs = 1e6//Copy the codeAs you can see, the source code uses iota to initialize various constants. (Ps: iota is a ridiculous thing to do in language design, especially when it is const.
2.2 interface
// A Locker represents an object that can be locked and unlocked.
type Locker interface {
Lock()
Unlock()
}
Copy the codeSync. Mutex implements this interface (sync.locker), and it’s worth mentioning that sync.rwmutex, which will be discussed later, also implements this interface.
Sync. Mutex also has its own private (lower-case) in-package functions, which are discussed in more detail below.
func (m *Mutex) lockSlow() {}
func (m *Mutex) unlockSlow(new int32) {}
Copy the codeMutex also has runtime calls. The actual implementations of these functions are the following functions.
// Determine whether the current goroutine can spin (since spin is very CPU consuming, Func runtime_canSpin(I int) bool // Perform the spin operation func runtime_doSpin() // Get the current milliseconds timestamp func runtime_nanotime() Int64 // Implementation of the semaphore, corresponding to the semaphore P primitive operation, the value of s represents the semaphore, contains a FIFO wait queue, if lifo is true, then placed at the head of the queue. Skipframes are valid only when tracing is started. Func runtime_SemacquireMutex(s *uint32, lifo bool, skipframes int) Goroutine func runtime_Semrelease(s *uint32 handoff bool, skipframes int) For now, you just need to know what the function does, and we'll have a separate section on that laterCopy the code3 source details analysis
3.1 the lock
First rob again
// Lock locks m.
// If the lock is already in use, the calling goroutine
// blocks until the mutex is available.
func (m *Mutex) Lock(a) {
// Fast path: if the value of state is 0(the current lock is open and there are no waiters), then the lock can be added directly
if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
if race.Enabled {
race.Acquire(unsafe.Pointer(m)) // Load happens-before guarantee
}
return
}
// Slow path: Performs various operations, and this is where the core of mutex locking is
m.lockSlow()
}
Copy the codefunc (m *Mutex) lockSlow(a) {
// The current goroutine wait time
var waitStartTime int64
// Whether the current goroutine is hungry
starving := false
// Whether the current goroutine has been awakened
awoke := false
// The number of spins of the current goroutine
iter := 0
// The current status of the lock
old := m.state
for {
// If the lock is hungry, there is no need to spin, and the lock can be transferred directly to the team leader's goroutine
// If means if the state of the lock is locked &&
// In non-hunger mode &&
// The current goroutine can be spun.
// Spin the current goroutine
if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
/ / if
// The current state of the goroutine is unwoke &&
// The state of mutex is not awake &&
// The waiter number is not equal to 0
// Set its own state to wake and the lock state to wake, so that blocked Goroutines do not need to be woken when unlocked
if! awoke && old&mutexWoken ==0&& old>>mutexWaiterShift ! =0 &&
atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
awoke = true
}
runtime_doSpin()
iter++
old = m.state
continue
}
// There are three ways to get there:
// 1. The mutex is not locked
// 2. Mutex is in starvation mode
// 3. The current goroutine cannot spin (iter has a number limit)
new := old
// Start setting the desired state, where new is the desired new state (fetch the lock). Finally, the CAS operation ensures that only one goroutine can operate on state
// If the lock is not in the hungry state, change the expected state to lock, because if the lock is in the hungry state, no attempt should be made to lock, and it needs to be queued directly
if old&mutexStarving == 0 {
new |= mutexLocked
}
// If the state of the lock is already locked or the state of the lock is hungry, then the current goroutine should be queued with the waiter number +1
ifold&(mutexLocked|mutexStarving) ! =0 {
new+ =1 << mutexWaiterShift
}
// If the current goroutine is hungry and the mutex is locked, the mutex is expected to be hungry.
// If the lock is idle, there is no need to switch to starvation mode. The Unlock operation expects a hungry Mutex to have a waiter, which is not the case in this case.
// The current goroutine switches mutex to starvation mode.
// But if the mutex is currently unlocked, don't do the switch.
// Unlock expects that starving mutex has waiters, which will not be true in this case.
ifstarving && old&mutexLocked ! =0 {
new |= mutexStarving
}
// If the state of the goroutine is awake, you need to reset the state, because the current state of the goroutine must change to sleep or the lock has been acquired.
if awoke {
// The goroutine has been woken from sleep,
// so we need to reset the flag in either case.
if new&mutexWoken == 0 {
throw("sync: inconsistent mutex state")}new &^= mutexWoken // Press position 0
}
// Start the CAS, and restart the loop if the CAS fails
if atomic.CompareAndSwapInt32(&m.state, old, new) {
if old&(mutexLocked|mutexStarving) == 0 {
break // locked the mutex with CAS
}
// If the wait time is not 0, the current goroutine has been awakened, and the current goroutine needs to be placed at the head of the queuequeueLifo := waitStartTime ! =0
// Set the initial timestamp
if waitStartTime == 0 {
waitStartTime = runtime_nanotime()
}
// Here the goroutine enters sleep, using the semaphore to acquire the lock
runtime_SemacquireMutex(&m.sema, queueLifo, 1)
// The current goroutine is awakened
// If the waiting time of the current goroutine exceeds 1ms, the current Goroutine is marked as hungry
starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
old = m.state
// If the current lock is in starvation mode, the state of the lock is unlocked, and the current goroutine is awakened by directly moving mutex from the previous gorountine. Otherwise, the current state of the goroutine is marked as awake to compete with other unqueued Goroutines for the lock
ifold&mutexStarving ! =0 {
// If this goroutine was woken and mutex is in starvation mode,
// ownership was handed off to us but mutex is in somewhat
// inconsistent state: mutexLocked is not set and we are still
// accounted as waiter. Fix that.
ifold&(mutexLocked|mutexWoken) ! =0 || old>>mutexWaiterShift == 0 {
throw("sync: inconsistent mutex state")}// A lock has been obtained in the current routine. Change the waiter number to -1 to change the status to lock
delta := int32(mutexLocked - 1<<mutexWaiterShift)
// mutexLocked + (-1<<mutexWaiterShift)
// If the waiting time of the current Goroutine is less than 1ms(non-hungry state) or the current Goroutine is the last one in the queue, then the lock mode needs to be switched to the regular mode
if! starving || old>>mutexWaiterShift ==1 {
delta -= mutexStarving
// mutexLocked - mutexStarving + (-1<<mutexWaiterShift)
}
// Add the lock, decrease the count, and reduce the hunger if not hunger
atomic.AddInt32(&m.state, delta)
break
}
awoke = true
iter = 0 // The spin count is zero
} else {
old = m.state
}
}
if race.Enabled {
race.Acquire(unsafe.Pointer(m))
}
}
Copy the code3.2 unlock
// A locked Mutex is not associated with a particular goroutine.
// It is allowed for one goroutine to lock a Mutex and then
// arrange for another goroutine to unlock it.
func (m *Mutex) Unlock(a) {
if race.Enabled {
_ = m.state
race.Release(unsafe.Pointer(m))
}
// This is similar to locking. If the lock mode is normal and there is no waiter waiter, the lock will be unlocked directly.
new := atomic.AddInt32(&m.state, -mutexLocked)
if new! =0 {
// Outlined slow path to allow inlining the fast path.
// To hide unlockSlow during tracing we skip one extra frame when tracing GoUnblock.
m.unlockSlow(new)}}Copy the code//new identifies the new state of the lock, subtracting 1 from the original state
func (m *Mutex) unlockSlow(new int32) {
Attempting to release a mutex that is not locked causes the process to crash directly.
// In order to avoid concurrent UnLock problems, the lock is subtracted and the UnLock is added.
if (new+mutexLocked)&mutexLocked == 0 {
throw("sync: unlock of unlocked mutex")}// If mutex is in normal mode
if new&mutexStarving == 0 {
old := new
for {
// If there are no waiters or a goroutine has already
// been woken or grabbed the lock, no need to wake anyone.
// In starvation mode ownership is directly handed off from unlocking
// goroutine to the next waiter. We are not part of this chain,
// since we did not observe mutexStarving when we unlocked the mutex above.
// So get off the way.
// If no waiter is waiting for mutex
// Or the mutex has been acquired by another goroutine,
// Or there is a goroutine in the awake state (trying to acquire the lock)
// Or the lock is in starvation mode (mutex ownership is transferred directly to the next waiter, and the current Goroutine is not in the queue, because the lock is in normal mode when released)
// In the above four cases, return directly
if old>>mutexWaiterShift == 0|| old&(mutexLocked|mutexWoken|mutexStarving) ! =0 {
return
}
// Grab the right to wake someone.
// At this point, the state of the lock is idle, no lock has been awakened, and the lock is in normal mode
// Then the desired state is the waiter number -1 and the lock state is set to wake
new = (old - 1<<mutexWaiterShift) | mutexWoken
if atomic.CompareAndSwapInt32(&m.state, old, new) {
// Wake the waiter of the party leader to try to acquire the lock
runtime_Semrelease(&m.sema, false.1)
return
}
old = m.state
}
} else {
// If mutex is in hungry mode, transfer ownership of Mutex directly to the head of the queue
// Starving mode: handoff mutex ownership to the next waiter, and yield
// our time slice so that the next waiter can start to run immediately.
// Note: mutexLocked is not set, the waiter will set it after wakeup.
// But mutex is still considered locked if mutexStarving is set,
// so new coming goroutines won't acquire it.
runtime_Semrelease(&m.sema, true.1)}}Copy the code4 common pit points
- Sync. mutex is not reentrant
- For example, if lock is called twice in a row, a deadlock will be triggered and goroutine will panic directly.
package main
import "sync"
func main(a) {
m := sync.Mutex{}
m.Lock()
m.Lock()
}
//fatal error: all goroutines are asleep - deadlock!
Copy the code- If A acquires A+B and B acquires B+A, A deadlock is triggered
var lockA = &sync.Mutex{}
var lockB = &sync.Mutex{}
func TestA(a) {
lockA.Lock()
defer lockA.Unlock()
time.Sleep(1 * time.Second)
lockB.Lock()
defer lockB.Unlock()
}
func TestB(a) {
lockB.Lock()
defer lockB.Unlock()
time.Sleep(1 * time.Second)
lockA.Lock()
defer lockA.Unlock()
}
func main(a) {
go TestA()
TestB()
}
//fatal error: all goroutines are asleep - deadlock!
Copy the code- A deadlock is not a sufficient condition to trigger a panic
package main
import (
"sync"
"time"
)
var lockA = &sync.Mutex{}
var lockB = &sync.Mutex{}
func TestA(a) {
lockA.Lock()
defer lockA.Unlock()
time.Sleep(1 * time.Second)
lockB.Lock()
defer lockB.Unlock()
}
func TestB(a) {
lockB.Lock()
defer lockB.Unlock()
time.Sleep(1 * time.Second)
lockA.Lock()
defer lockA.Unlock()
}
func main(a) {
go TestA()
go TestB()
time.Sleep(3 * time.Second)
}
/ / return normally
Copy the code- Sync. mutex: Trying to unlock an idle mutex causes panic.
package main
import (
"fmt"
"sync"
"time"
)
func main(a) {
m := sync.Mutex{}
m.UnLock()
}
// fatal error: sync: unlock of unlocked mutex
Copy the code- Sync. mutex is not bound to a goroutine and can be acquired by a goroutine and released by b Goroutine.
package main
import (
"fmt"
"sync"
"time"
)
func main(a) {
m := sync.Mutex{}
m.Lock()
fmt.Println("a lock")
go func(a) {
m.Unlock()
fmt.Println("b unlock")
}()
time.Sleep(time.Second)
}
//a lock
//b unlock
Copy the code- Do not copy sync.Mutex. When Mutex is used as a function argument, use a pointer to pass the argument.
5 Reference Documents
- Github.com/golang/go/b…
- www.purewhite.io/2019/03/28/…