This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact.

Mutex is the main means of controlling access to shared resources of concurrent programs. The use of mutex has been described in the previous section on concurrency: concurrency control, synchronization primitive sync package

Mutex is very convenient to use, but its internal implementation is very complicated, today we will introduce its internal implementation principle.

Mutex data structure

In the source package SRC /sync/mutex.go: mutex defines a mutex 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 code
  • State: indicates the status of the mutex, for example, whether it is locked
  • Sema: Represents the semaphore. The coroutine blocks and waits for the semaphore. The unlocked coroutine releases the semaphore and wakes up the coroutine waiting for the semaphore.

State is a 32-bit integer variable that is internally divided into four parts to record the four states of Mutex. Internal layout of Mutex:

  • Waiter: indicates the number of blocked coroutines to determine whether the semaphore needs to be released when the coroutine is unlocked.
  • ‘Starving’ : indicates whether the Mutex processes hunger. 0: no hunger. 1: starvation.
  • Woken: indicates whether any coroutine has been Woken up. 0: no coroutine has been Woken up. 1: coroutine has been Woken up and is being locked.
  • Locked: indicates whether the Mutex is Locked. 0: no Mutex is Locked. 1: The Mutex is Locked.

Locking between coroutines actually deprives Locked of the right to assign values to Locked. Locking succeeds if the Locked field is set to 1. If not, block and wait for the mutex. sema semaphore. Once the coroutine holding the lock is unlocked, the waiting coroutines will wake up in turn.

Mutex method

  • Lock() : Lock method
  • Unlock(): Unlock method
  1. A mutex that allows only one coroutine to execute a program at a time, while the other coroutines wait for the coroutine to finish executing before executing it in sequence.
  2. A mutex has only two methods: Lock and Unlock. When a coroutine locks a resource, other coroutines can be locked again only after the coroutine is unlocked.
  3. Lock and Unlock come in pairs, and to prevent forgetting to release the Lock, we can use the defer statement to release the Lock.

Add/unlock process

Simple locking

Assuming that only one coroutine is currently locking and there is no interference from other coroutines, the process is shown as follows:

When the lock is added, the system checks whether the Locked flag is 0. If the Locked flag is 0, the system changes it to 1.

The lock is blocked

Assume that the lock is already occupied by other coroutines, and the process is as follows:

When the B coroutine re-locks an occupied lock, the Waiter counter is increased by 1, and the B coroutine will block and not be awakened until the Locked value reaches 0.

Simple unlock

Assuming that no other coroutines block when unlocking, the process is shown as follows:

Since there are no other coroutines blocking for locking, you only need to change the Locked bit to 0 to unlock the device without releasing the semaphore.

Unlocks and wakes up coroutines

Assume that one or more coroutines are blocked when unlocking, and the process is shown as follows:

A coroutine is unlocked in two steps: first, the Locked position 0 is unlocked; second, if the Waiter>0 is observed, A semaphore is released to wake up A blocked coroutine; the woken coroutine B changes the Locked bit to 1, and the coroutine B acquires the lock.

Spin process

  • If the Locked bit is 1, the lock is currently held by another coroutine. The coroutine attempting to lock does not immediately block, but continuously checks to see if the Locked bit is 0, a spin process.

  • The spin time is short, but if the lock is found to have been released during the spin, the coroutine can acquire the lock immediately. Even if a coroutine is awakened, the lock cannot be acquired and can only be blocked again.

  • The advantage of spin is that if a lock fails, instead of immediately going into blocking, there is a chance that the lock will be acquired, thus avoiding coroutine switching.

Conditions for spin

When locking, the program automatically determines whether it can spin, but unlimited spin puts a lot of pressure on the CPU, so it is important to determine whether it can spin.

The spin must satisfy all of the following conditions:

  • The number of spins should be small enough, usually 4, that is, at most 4 spins
  • The number of CPU cores must be greater than 1, otherwise the spin is meaningless because no other coroutine can release the lock
  • The number of processes in the coroutine scheduling mechanism should be greater than 1, such as setting the processor to 1 with GOMAXPROCS() without enabling spin
  • Runnable queues in the coroutine scheduling mechanism must be empty, otherwise coroutine scheduling will be delayed

Spin advantage and problems

Spin has the advantage of making better use of the CPU and avoiding coroutine switching as much as possible.

If a lock is acquired during spin, the previously blocked coroutine will not be able to acquire the lock. If a particularly large number of coroutines are locked each time they are acquired by spin, the previously blocked process will have a hard time acquiring the lock and will go hungry.

To avoid coroutines being unable to acquire locks for long periods of time, a state has been added since version 1.8, namely the Medicine state of Mutex. There is no spin in this state. Once a coroutine releases the lock, a coroutine must wake up and lock successfully.

Mutex mode

Each Mutex has two modes, Normal and medicine.

  1. Normal

By default, Mutex’s mode is normal. In this mode, if the coroutine fails to lock, it will not immediately switch to blocking queuing. Instead, it will judge whether the conditions of spin are met. If so, it will start the spin process and attempt to snatch the lock.

  1. starvation

If a coroutine is found to be blocking and waiting, a semaphore will be released to wake up a waiting coroutine. The awakened coroutine will start running after getting the CPU. At this time, it finds that the lock has been preempted and it has to block again. However, before blocking, Mutex will determine how much time has passed since the last block. If more than 1ms has passed, Mutex will be marked as “hungry” and blocked again. In starvation mode, the spin process does not start, that is, once a coroutine has released the lock, it must wake up. The awakened coroutine will successfully acquire the lock, and the wait count will be reduced by one.

Woken state

The Woken state is used to communicate the locking and unlocking process. For example, at the same time, two coroutines, one is locking and the other is unlocking, and the locked coroutine may be in the spin process. In this case, Woken is marked as 1 to inform the unlocking coroutine that it does not need to release the semaphore.

Repeating the solution will panic

Unlock consists of changing Locked to 0 and determining Waiter:

  • If the value is greater than 0, the semaphore is released.
  • If Unlock() is unlocked multiple times, one semaphore may be released each time, which wakes up multiple coroutines, which then continue to Lock in the logic of Lock(), increasing the complexity of Lock() implementation and causing unnecessary coroutine switching.