Analysis of mutex principle in golang

Mutex structure

type Mutex struct {
    
	state int32
	sema  uint32
}

state Indicates the status of the mutex .

sema Indicates the semaphore , The coroutine block waits for the semaphore , The unlocked coroutine releases the semaphore to wake up the coroutine waiting for the semaphore .

state yes 32 Bit integer variable , In the internal implementation, the variable is divided into four parts , Used to record Mutex Four states .

• Locked:： It means that we should Mutex Whether it has been locked ,0- It's not locked ,1- Locked .
• Woken:： Indicates whether a collaboration has been awakened ,0- There's no synergy ,1- There is a process to wake up , In the process of locking .
• Starving： It means that we should Mutex Whether you are hungry , 0- No hunger ,1- Starvation , It indicates that there is a process blocking more than 1ms.
• Waiter:： Indicates the number of coprocesses blocking waiting locks , When the co process is unlocked, judge whether to release the semaphore according to this value .

The lock grabbing between processes is actually grabbing for Locked Right of assignment , Can give Locked Domain setting 1, It means that the lock grabbing is successful . If you can't grab it, block and wait Mutex.sema Semaphore , Once the co process holding the lock is unlocked , The waiting process will be awakened in turn .

Woken and Starving It is mainly used to control the lock grabbing process between processes , We'll find out later .

When reading the source code , You will find that all kinds of bit operations and logical operations are really not easy to read , Why not use four independent fields , In fact, this is for atomic operation , Just imagine , How can we update these four fields while ensuring atomicity ？ therefore , Combine them into a field and match atomic We can solve this problem .

Mutex Methods

Mutext Provide two methods for external ：

Lock() Lock method
Unlock() Unlocking method

Let's analyze the process of locking and unlocking , Locking can be divided into success and failure , If successful, get the lock directly , After failure, the current collaboration is blocked , Again , When unlocking, there are also two kinds of processing according to whether there is a blocking process .

Simple locking

Suppose there is only one coroutine locking at present , No other co process interference , Then the process is shown in the figure below ：

The locking process will judge Locked Whether the flag bit is 0, If it is 0 Then put Locked Location 1, It represents the success of locking . As can be seen from the above figure , After locking successfully , It's just Locked Location 1, Other status bits have not changed .

Locking is blocked

Assume that when locking , The lock has been occupied by other processes , At this time, the locking process is shown in the figure below ：

As you can see from the picture above , When the process B When locking an occupied lock again ,Waiter The counter is incremented 1, At this point, the process B Will be blocked , until Locked Value to 0 Before you wake up .

Simply unlock

It is assumed that when unlocking , There are no other processes blocking , The unlocking process is shown in the figure below ：

Wait for locking because there are no other processes blocking , So when unlocking at this time, you only need to put Locked The position is 0 that will do , There is no need to release semaphores .

Unlock and wake up the process

It is assumed that when unlocking , Yes 1 One or more processes are blocked , The unlocking process is shown in the figure below ：

coroutines A The unlocking process is divided into two steps , One is to put the Locked Location 0, The second is to view Waiter>0, So release a semaphore , Wake up a blocked process , Awakened synergy B hold Locked Location 1, So Xie Cheng B Gets the lock .

Spin process

When locking , If at present Locked Position as 1, This indicates that the lock is currently held by other processes , The process of trying to lock does not immediately turn into blocking , It will continue to detect Locked Whether the bit changes to 0, This process is called spin process spin.

Spin time is very short , But if the lock is found to have been released during spin , Then the coroutine can get the lock immediately . At this time, even if a process is awakened, the lock cannot be obtained , Can only block again .

Spin operation , Would call procyield function , This function is also implemented in assembly language . Function internal loop call PAUSE Instructions .PAUSE Command to do nothing , But it will consume CPU Time , So I won't give up CPU.

The advantage of spin is , When locking fails, it is not necessary to immediately turn to blocking , Have a chance to get the lock , This can avoid context switching of the collaboration .

Spin condition

When locking, the program will automatically judge whether it can spin , Unlimited spin will give CPU It brings a lot of pressure , So it's important to judge whether you can spin .

Spin must meet all of the following conditions ：

• Spin times should be small enough , Usually it is 4, That is, spin most 4 Time .
• CPU The number of cores should be greater than 1, Otherwise spin doesn't make sense , Because it is impossible for other processes to release the lock at this time .
• In the cooperative scheduling mechanism Process The quantity should be greater than 1, For example, use GOMAXPROCS() Set the processor to 1 You can't turn on spin .
• The runnable queue in the co process scheduling mechanism must be empty , Otherwise, the co process scheduling will be delayed .
• so , Spin conditions are very harsh , In short, spin is only enabled when you are not busy .

The advantage of spin

The advantage of spin is to make full use of CPU, Try to avoid co process switching . Because the current application for locking has CPU, If you spin for a short time, you can get a lock , The current collaboration can continue to run , You don't have to go into a blocking state .

Spin problem

If a lock is obtained during spin , Then the previously blocked coroutine will not be able to obtain the lock , If there are many locking processes , Every time you get a lock by spinning , Then it will be difficult for previously blocked processes to obtain locks , To enter a state of hunger .

In order to avoid that the cooperation process cannot obtain the lock for a long time , since 1.8 A status has been added since version , namely Mutex Of Starving state . It doesn't spin in this state , Once there is a process release lock , Then it will wake up a cooperative process and lock it successfully .

Mutex Pattern

The previous analysis of locking and unlocking only focused on Waiter and Locked The change of the position , Now let's take a look at Starving The role of bit .

Every Mutex There are two modes , be called Normal and Starving. The two modes are described below .

normal Pattern

By default ,Mutex Model for normal.

In this mode , If the process fails to lock, it will not immediately turn into the blocking queue , But to determine whether the spin condition is satisfied , If satisfied, the spin process will start , Try to grab the lock .

starvation Pattern

You can grab the lock during spin , It must mean that a coroutine releases the lock at the same time , We know that if a blocking waiting process is found when releasing the lock , It also releases a semaphore to wake up a waiting process , The awakened synergy gets CPU And then start running , At this time, it is found that the lock has been preempted , I had to block again , However, before blocking, we will judge how long it has taken since the last blocking to this blocking , If exceeded 1ms Words , Will Mutex Marked as " hunger " Pattern , Then block .

In hunger mode , The spin process will not start , That is, once a process releases the lock , Then it will awaken the synergy , The awakened coroutine will successfully acquire the lock , It also reduces the wait count 1.

Woken state

Woken Status is used for communication during locking and unlocking , for instance , At the same time , One of the two coroutines is locking , One is unlocking , The locked coprocess may be in the spin process , At this time Woken Marked as 1, It is used to inform the unlocking process that it is not necessary to release the semaphore , It's like saying ： Just unlock it , You don't have to release the semaphore , I'll get the lock right away .

Why do I need to unlock repeatedly panic

Maybe you think , Why? Go Can't be more robust , Multiple execution Unlock() No more panic？

Think carefully Unlock The logic can be understood , It's actually hard to do .Unlock The process is divided into Locked Set as 0, And then determine Waiter value , If value >0, Then release the semaphore .

If you do it many times Unlock(), Then you may release a semaphore every time , This will wake up multiple processes , After multiple processes wake up, they will continue in Lock() Grab the lock in your logic , It's bound to increase Lock() The complexity of implementation , It will also cause unnecessary co process switching .

To sum up

The source code looks very difficult to read , Bit operation logic operation , Mainly for the realization of atomic operation ,Mutex The core logic is actually semaphore PV operation , and state The four states of are for optimization .

stay m.lockSlow() and m.unlockSlow() There was a state modification operation before , This is to prevent the repeated release of semaphores , Because the release semaphore will not be blocked , The repeated release of semaphores will destroy mutex The logic of . You can refer to https://www.cnblogs.com/niniwzw/p/3153955.html

In the source code , With the help of atomic operation atomic To achieve Mutex, That's because atomic Is supported by hardware （CPU Instructions ）, Smaller particle size , Higher performance , The semaphore is provided by the operating system .

About semaphores

We know Semaphore , It's provided by the operating system , Used to realize mutual exclusion and thread synchronization , Granularity is thread level , and golang Of Mutex It's at the collaborative level , Obviously, it is impossible to directly use the semaphore of the operating system , Therefore, cooperation is needed golang Co scheduling model GMP To further understand .