How does Go implement reentrant locking?

preface

Hello, everyone, I’m Asong. A few days ago, a reader asked me how to implement reentrant locks using Go. It occurred to me that the concept of reentrant locks does not exist in Go and is not used in business development. Reentrant locks have been used in Java, but not in Go. This article will take you to decrypt ~

What is a reentrant lock

For those of you who have written Java before, a reentrant lock, also known as a recursive lock, means that when the same thread acquires the lock in the outer method, it automatically acquires the lock in the inner method of the thread. It will not block because the lock has been acquired before and has not been released. An example of a reentrant lock is given in an article on locks by meituan technical team:

Suppose now have multiple villagers in queuing for water well, the administrator is guarding the Wells, the villagers in the water, the administrator allows the lock and the same multiple binding bucket, the person with multiple buckets to draw water, and lock the first bucket binding and follow up with water, after the second lock may also directly bring a bucket and binding and began to draw water, The lock will be returned to the keeper after all the buckets are filled. All of this person’s water fetching process can be successfully executed, and the subsequent waiting people can also fetch water. This is the reentrant lock.

Below is an excerpt from the article shared by Meituan’s technical team:

If the lock is not reentrant, the administrator will only allow the lock to be bound to one bucket of the same person. The first bucket and lock will not release the lock after it finishes watering, so the second bucket will not be able to bind to the lock or draw water. The current thread is deadlocked and all threads in the entire wait queue cannot be woken up.

The picture below is taken from the article shared by meituan’s technical team:

withGoImplement reentrant locking

ReentrantLock ReentrantLock ReentrantLock ReentrantLock ReentrantLock ReentrantLock ReentrantLock ReentrantLock

ReentrantLock inherits its parent class AQS, which maintains a synchronization status to count the reentrant times. The initial value of status is 0. When a thread tries to acquire the lock, the ReentrantLock can first try to acquire and update the status value. If status == 0 means that no other thread is executing the synchronization code, set status to 1 and the current thread starts executing. If the status! If = 0, the current thread is determined to be the thread that acquired the lock. If so, status+1 is executed and the current thread can acquire the lock again. When the lock is released, the reentrant lock also obtains the value of the current status, provided that the current thread is the thread holding the lock. If status-1 == 0, it indicates that all repeated lock acquisition operations of the current thread have been completed before the thread actually releases the lock.

To summarize, implementing a reentrant lock requires two things:

  • Remember the thread that holds the lock
  • Count the number of reentries

It’s easy to count the number of reentrants, so let’s think about how to do that. Remember the thread holding the lock?

Goroutine is the most basic execution unit in Go. Every Go program has at least one Goroutine. The main program is also a Goroutine, called the main Goroutine, which will be created automatically when the program starts. Each Goroutine also has its own unique number, which can only be seen in panic scenarios, but Go deliberately does not provide an interface to obtain this number. The official reason is to avoid abuse. The runtime.Stack function outputs the current Stack frame information, and then parses the string to obtain the Goroutine ID. For details, see the open-source project – GoID.

Because the Goroutine in Go has a Goroutine ID, we can use this to remember the current thread, and use this to determine whether the lock is held, so we can define the following structure:

type ReentrantLock struct {
	lock *sync.Mutex
	cond *sync.Cond
	recursion int32
	host     int64
}
Copy the code

The host field records the id of the current goroutine holding the lock. The recursion field records the number of times the current Goroutine reenters. The purpose of using Cond is to coordinate multiple coroutines using the same reentrant lock. If another coroutine is holding the lock, the current coroutine blocks until the other coroutine calls release the lock. Sync. Cond (conditional variable implementation mechanism) sync.Cond (conditional variable implementation mechanism)

  • The constructor

func NewReentrantLock(a)  sync.Locker{
	res := &ReentrantLock{
		lock: new(sync.Mutex),
		recursion: 0,
		host: 0,
	}
	res.cond = sync.NewCond(res.lock)
	return res
}
Copy the code
  • Lock
func (rt *ReentrantLock) Lock(a)  {
	id := GetGoroutineID()
	rt.lock.Lock()
	defer rt.lock.Unlock()

	if rt.host == id{
		rt.recursion++
		return
	}

	forrt.recursion ! =0{
		rt.cond.Wait()
	}
	rt.host = id
	rt.recursion = 1
}
Copy the code

Here is a simple logic, roughly explained:

First we get the ID of the current Goroutine, and then we add a mutex to lock the current block to ensure concurrency safety. If the current Goroutine is holding the lock, we increase the value of resutsion to record the number of locks held by the current thread, and then return. If the current Goroutine does not occupy the lock, it determines whether the current reentrant lock is occupied by another Goroutine. If another Goroutine is occupying the reentrant lock, the cond.wait method is called to block until other coroutines release the lock.

  • Unlock
func (rt *ReentrantLock) Unlock(a)  {
	rt.lock.Lock()
	defer rt.lock.Unlock()

	if rt.recursion == 0|| rt.host ! = GetGoroutineID() {panic(fmt.Sprintf("the wrong call host: (%d); current_id: %d; recursion: %d", rt.host,GetGoroutineID(),rt.recursion))
	}

	rt.recursion--
	if rt.recursion == 0{
		rt.cond.Signal()
	}
}
Copy the code

The explanation is as follows:

First, we add a mutex to lock the current code block to ensure concurrency safety. When releasing the reentrant lock, if the Goroutine that does not hold the lock releases the lock, panic will occur in the program, which is usually caused by user usage errors. If the current Goroutine releases the lock, call cond.Signal to wake up the other coroutines.

Test cases are not posted here, code uploaded github:github.com/asong2020/G…

whyGoThere are no reentrant locks in the language

The answer, I’m: stackoverflow.com/questions/1…

For example, suppose we have a piece of code that looks like this:

func F(a) {
	mu.Lock()
	/ /... do some stuff ...
	G()
	/ /... do some more stuff ...
	mu.Unlock()
}

func G(a) {
	mu.Lock()
	/ /... do some stuff ...
	mu.Unlock()
}
Copy the code

Functions F() and G() use the same mutex, and both use locks inside their respective functions. This can cause deadlocks. Using reentrant locks can solve this problem, but a better way is to change the structure of our code.


func call(a){
  F()
  G()
}

func F(a) {
      mu.Lock()
      ... do some stuff
      mu.Unlock()
}

func g(a){... do some stuff ... }func G(a) {
     mu.Lock()
     g()
     mu.Unlock()
}
Copy the code

This not only avoids deadlocks, but also decouples the code. Such code is layered by scope, like a pyramid, with functions at the top calling those at the bottom, and scope increasing as you go up; Each layer has its own lock.

Conclusion: There is no need to use reentrant lock in Go language, if we find our code to use reentrant lock, it must be something wrong, please check the code structure, modify it!!

conclusion

In this article, we learned what a reentrant lock is, and implemented it in Go. You just need to know the concept, not the actual development. Finally, I recommend you to think about your code structure. Good code is well thought out, and I hope you can write beautiful code.

Well, that’s the end of this article, the quality three (share, like, look) are the author to continue to create more quality content motivation! I am aasongAnd we’ll see you next time.

We have created a Golang learning and communication group. Welcome to join the group and we will learn and communicate together. Way to join the group: follow the public account [Golang Dreamworks] to obtain. For more learning materials, please go to the official number.

Recommended previous articles:

  • Unsafe package
  • Which of the Go languages do you use to allocate memory, new or make?
  • Source analysis panic and recover, do not understand you hit me!
  • The scene of large face blows caused by empty structures
  • Leaf-segment Distributed ID Generation System (Golang implementation version)
  • Interviewer: What is the result of two nil comparisons?
  • Interviewer: Can you use Go to write some code to determine how the current system is stored?
  • How to smoothly toggle online Elasticsearch index