Implementation of golang spin lock
- 2020-06-23 00:36:44
- OfStack
CAS Algorithm (compare and swap)
CAS algorithm is a famous lock-free algorithm. Lock-free programming is the synchronization of variables between multiple threads without the use of locks. In other words, the synchronization of variables without threads being blocked is also called non-blocking synchronization (ES9en-ES10en Synchronization). The CAS algorithm involves three operands
The memory value V that needs to be read and written Compare the value A The new value B to writeIf and only if the value of V is equal to A, CAS updates the value of V atomically with the new value of B, otherwise nothing is done (the comparison and replacement is 1 atomic operation). 1 in the general case is 1 spin operation, that is, repeated retries.
spinlocks
A spin lock is when a thread acquires a lock. If the lock has already been acquired by another thread, the thread will loop and wait until the lock has been acquired.
The thread 1 that gets the lock is active but is not performing any valid tasks, and using this lock results in ES30en-ES31en.
It is a lock mechanism for protecting Shared resources. In fact, spinlocks are similar to mutexes in that they are used to resolve the exclusive use of a resource. Either a mutex or a spin lock, at most one holder at any one time, that is, at most one execution unit at any one time can acquire a lock. But the scheduling mechanism is slightly different. For a mutex, the resource applicant can only go to sleep if the resource is already occupied. But a spin lock does not cause the caller to sleep. If the spin lock has been held by another execution unit, the caller loops around to see if the holder of the spin lock has released the lock, hence the name "spin".
golang implements spin locks
type spinLock uint32
func (sl *spinLock) Lock() {
for !atomic.CompareAndSwapUint32((*uint32)(sl), 0, 1) {
runtime.Gosched()
}
}
func (sl *spinLock) Unlock() {
atomic.StoreUint32((*uint32)(sl), 0)
}
func NewSpinLock() sync.Locker {
var lock spinLock
return &lock
}
Reentrant spin locks and non-reentrant spin locks
The code at the beginning of this article can be seen from a careful analysis of 1 that it is non-supported reentrant, that is, when a thread has acquired the lock on the first time and re-acquired the lock on the second time before the lock is released, it cannot be successfully acquired on the second time. Since CAS is not satisfied, the second fetch will go into the while loop and wait, and if it is reentrant, the second fetch should be successful.
Moreover, even if the second lock is successfully obtained, the second lock will be released when the first lock is released, which is unreasonable.
To implement a reentrant lock, we need to introduce a counter that records the number of threads that acquired the lock
type spinLock struct {
owner int
count int
}
func (sl *spinLock) Lock() {
me := GetGoroutineId()
if spinLock .owner == me { // If the current thread has already acquired the lock, the number of threads increases 1 And then go back
sl.count++
return
}
// If no lock is obtained, pass CAS The spin
for !atomic.CompareAndSwapUint32((*uint32)(sl), 0, 1) {
runtime.Gosched()
}
}
func (sl *spinLock) Unlock() {
if rl.owner != GetGoroutineId() {
panic("illegalMonitorStateError")
}
if sl.count >0 { // If more than 0 , indicates that the current thread has acquired the lock multiple times, and the lock is released through count Reduction of 1 To simulate the
sl.count--
}else { // if count==0 , the lock can be released, so that the number of times the lock can be obtained and the number of times the lock can be released is 1 To the.
atomic.StoreUint32((*uint32)(sl), 0)
}
}
func GetGoroutineId() int {
defer func() {
if err := recover(); err != nil {
fmt.Println("panic recover:panic info:%v", err) }
}()
var buf [64]byte
n := runtime.Stack(buf[:], false)
idField := strings.Fields(strings.TrimPrefix(string(buf[:n]), "goroutine "))[0]
id, err := strconv.Atoi(idField)
if err != nil {
panic(fmt.Sprintf("cannot get goroutine id: %v", err))
}
return id
}
func NewSpinLock() sync.Locker {
var lock spinLock
return &lock
}
Other variations of the spin lock
1. TicketLock
TicketLock mainly addresses the issue of fairness.
Idea: every time a thread when acquiring the lock, give the thread a incremental id, we call queue number, at the same time, the lock corresponding to one service, every time a thread lock is released, the service will increase, at this time if the service number with a thread queue number 1, then the thread lock, because the line number is increasing, so to ensure that the first request of acquiring a lock threads can be the first to get to the lock, to realize the fairness.
Can imagine the bank to handle the business end of the line, line up every one customer on behalf of a need to lock the thread, and the bank service window lock, whenever there is a window service completed service number plus 1, as at this point in the line up all of the customers, only their line number and service number 1 can get service.
2. CLHLock
CLH lock is an extensible, high-performance, fair spin lock based on a linked list. The application thread spins only on local variables. It continuously polls the state of the precursor.
3. MCSLock
MCSLock loops through the nodes of local variables.
4. CLHLock and MCSLock
Both are based on linked lists. The difference is that CLHLock is based on implicit linked lists and does not have real attributes of subsequent nodes. MCSLock is a display linked list with one attribute pointing to subsequent nodes.
The problem of TicketLock multi-processor cache synchronization is solved by saving the thread state of the lock via a node (node), each thread having a separate node.
Spinlocks and mutexes
Conclusion: