万字图解| 深入揭秘Golang锁结构:Mutex(上)

大家好,我是「云舒编程」,今天我们来聊聊Golang锁结构:Mutex。

文章首发于微信公众号:云舒编程

关注公众号获取:
1、大厂项目分享
2、各种技术原理分享
3、部门内推

一、前言

   Golang的Mutex算是在日常开发中最常见的组件了,并且关于锁的知识也是面试官最喜欢问的。
   曾经在一次腾讯面试中,被面试官问得体无完肤。
   虽然Golang Mutex只有短短的200多行,但是已经是一个极其丰富、精炼的组件,有极其复杂的状态控制。我已经看过很多次Mutex的源码,但是总是过段时间就会又处于懵逼状态,不得其道。分析下来,猜测是缺少“历史背景”,一上来就看到的是已经经过好几轮优化的代码,但是不清楚这么优化的背景,同时也缺少一些场景,就会导致无法理解一些设计。
   其实如果我们去追溯 Mutex 的演进历史,会发现,Mutex最开始是一个非常简单的实现,简单到难以置信的地步,是Go开发者们经过了好几轮的优化才变成了现在这么一个非常复杂的数据结构,这是一个逐步完善的过程。
   于是我想如果我们是设计者,我们会怎么去设计去优化一个锁的实现呢?
   下面我将结合我曾经的腾讯面试经历 加上 代入“设计者”的角度出发,结合Mutex 的演进历史,去分析如何设计一个功能完备的锁。希望经过本文的分析,你也可以从零设计出属于你的「Mutex」。
   友情提醒:文章很长,但是绝对值得一读。

二、面试中遇到Mutex

   这里大致还原下之前的面试流程,由于当初并没有答上来,所以会加入一些下来学习后的思考,从而让剧情可以顺利开展。
   面试官:对Mutex熟悉吗?
   :熟悉,Mutex是Golang 中的锁,主要是控制并发访问资源,保护共享资源。
   面试官:那如果让你去实现Mutex,你会怎么设计?
   :简单,定义一个int变量,0代表没有加锁,1代表加锁了,初始状态为0。然后使用一个For循环去尝试加锁,加锁时使用Atomic的CAS尝试将值从0改为1,如果成功了就获取锁,如果没有成功就继续For循环也就是自旋尝试获取锁,直到成功为止。拿到锁的线程想解锁的话也是通过Atomic的CAS尝试将值从1改为0。

type Mutex struct {
	key  int32
}

func (m *Mutex) Lock() {
	for {
		if atomic.CompareAndSwapInt32(&m.key, 0, 1) {
			return
		}
	}
}

func (m *Mutex) Unlock() {
	atomic.CompareAndSwapInt32(&m.key, 1, 0)
}

   面试官:那你觉得你的这个设计有没有问题?
   :性能会比较差,由于加锁是通过自旋实现的,如果有很多Goroutine在竞争锁的话,会导致CPU资源被打满,同时也是浪费资源。
   面试官:那怎么优化呢?
   :可以利用信号量去实现Goroutine的睡眠和唤醒,避免自旋浪费CPU。

type Mutex struct {
	key  int32
	sema uint32
}

func (m *Mutex) Lock() {
	if atomic.AddInt32(&m.key, 1) ==  1 {  //值从0变为1,则证明加锁成功
		return
	}
	runtime.Semacquire(&m.sema) //等待信号量
}

func (m *Mutex) Unlock() {
	if atomic.AddInt32(&m.key, -1) == 0 { //值-1后,变为0证明没有协程等待锁了,可以直接返回
		return
	}
	runtime.Semrelease(&m.sema) //唤起信号量上的协程
}

   面试官:回答不错,那你觉得这版的实现还有其他问题吗?
   :首先这版的实现解决了自旋的性能问题,其次由于信号量有一个先进先出的等待队列,所以也可以保证竞争锁的Goroutine是先到先得的,保证了公平。但是这样的公平其实在调度层面又是效率不高的。
   面试官:这里的「效率不高」从何说起?
   :假设有三个协程分别是G1,G2,G3。G1首先加锁成功了,然后执行业务逻辑。期间G2想加锁发现加不上,就进入了信号量的等待队列,这个时候G2可能已经被调度器从M上调走了。然后G1解锁,这个时候G3想加锁发现由于G2在他前面进行了等待,所以导致G3加不上。这种情况由于G2没有获得CPU时间片,但是G3已经获得了CPU时间片,所以直接把锁给G3从整体上来说,效率会更加高些。
   面试官:非常好,那应该怎么实现呢?
   :这里的本质是想给处于运行态的Goroutine 直接获得锁的机会,将上面的代码修改为:
这样新来的Goroutine可以有一次直接获取锁的机会

type Mutex struct {
	key  int32
	sema uint32
}

func (m *Mutex) Lock() {
	if atomic.CompareAndSwapInt32(&m.key, 0, 1) {
		return
	}
	for {
		if atomic.CompareAndSwapInt32(&m.key, 0, 1) {
			return
		}
		runtime.Semacquire(&m.sema)
	}
}

func (m *Mutex) Unlock() {
	if atomic.CompareAndSwapInt32(&m.key, 1, 0) {
		runtime.Semrelease(&m.sema)
	}
}

   面试官:这样写,有一个明显的问题,你知道「惊群效应」吗?
   :哦对,假设先有三个协程G1,G2,G3。G1加锁成功,G2,G3进入了信号量的等待队列。然后G1解锁,G2被唤醒,这个时候来了个新协程G4,G2和G4一起竞争锁,G4竞争成功。然后G4很快执行完进行解锁,然后G3就被唤醒了,这个时候就存在G2,G3一起竞争锁的场景。如果在高并发场景,这样的唤醒竞争还会更加激烈。同时也违背了G2,G3在信号量上先来先得的设计。
   面试官:对,那应该怎么解决呢?
   :可以考虑增加一个标识,如果发现已经有协程被唤醒了,后来的协程就只是解锁,但是不唤醒协程。
   面试官:还有一个问题,如果是最后一个协程,那他解锁的时候还需要进行runtime.Semrelease(&m.sema)吗?
   :哦对,这里也需要考虑。总结下我们的锁还需要以下额外能力:
         1、信号量:阻塞唤醒协程
         2、知道当前有多少协程阻塞在信号量上
         3、避免「惊群效应」
   面试官:嗯,差不多了。说说你的设计思路吧
   :按照一般的设计我们需要使用三个变量控制,类似下面这样

type Mutex struct {
	key  int32  //控制是否加锁成功,1:加锁 0:未加锁
    woken bool  //是否已经有协程被唤醒了
    waiter int32 //记录当前有多少协程阻塞在信号量上
	sema uint32 //信号量
}

   面试官:可以这样设计,不过可以优化下吗?很多框架组件设计都会充分利用变量的高位低位,你这里可以这样设计吗?
   :哦对,我再优化下,定义int32的变量state将其分为三部分:

type Mutex struct {
	state int32
	sema  uint32
}

image.png
那么加锁逻辑就变为:

const (
	mutexLocked      = 1 // mutex is locked
	mutexWoken       = 2 
	mutexWaiterShift = 2
)

type Mutex struct {
	state int32
	sema  uint32
}

func (m *Mutex) Lock() {
	//给新来的协程直接加锁的机会
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
		return
	}

	//上面没有加锁成功,尝试在接下来的唤醒中去竞争锁
	awoke := false //表示当前协程是不是被唤醒的
	for {
		old := m.state
		new := old | mutexLocked // 设置锁标志位为1
		if old&mutexLocked != 0 {
			new = old + 1<<mutexWaiterShift //锁没有释放,当前协程可能会阻塞在信号量上,先将waiter+1
		}
		if awoke { //尝试清除唤醒标志
			new &^= mutexWoken
		}

		//这里尝试将state从old设置为new。如果代码能够执行到这步,代表了可能发生以下几种情况的一种或者多种
		//1、当前协程尝试加锁
		//2、waiter+1
		//3、清除唤醒标志
		if atomic.CompareAndSwapInt32(&m.state, old, new) {
			if old & mutexLocked == 0{
				//成功获取到锁了,返回
				break
			}
			
			//没有获取到锁,阻塞在信号量上
			runtime.Semacquire(&m.sema)
			awoke = true //执行到这步,证明是被信号量唤醒的,设置唤醒标志
		}
	}
}

对上面的一些运算进行解释:
1、new := old | mutexLocked 将state的最低位设置为1,即代表想加锁;
2、new = old + 1<<mutexWaiterShift,首先会执行1<<mutexWaiterShift,即将1左移两位,移位后的值在加上old。1左移两位即避开了mutexLocked和mutexWoken,然后再跟old相加,就可以实现waiter+1。
3、new &^= mutexWoken,&^ 是一个位清除运算符(bit clear operator,它的作用是将第一个操作数(左操作数)中的位与第二个操作数(右操作数)相对应的位进行比较。如果右操作数的位为 1,则将左操作数的相应位清零(设置为 0)。如果右操作数的位为 0,则左操作数的相应位保持不变。

   面试官:写的不错,解锁的部分呢?

   :别急,马上补上

func (m *Mutex) Unlock() {
	new := atomic.AddInt32(&m.state, -mutexLocked)
	if (new+mutexLocked)&mutexLocked == 0 {
		panic("sync: unlock of unlocked mutex")
	}
	
	old := new
	for{
		//以下情况都直接结束,不继续往下:
		//1、如果没有人阻塞在信号量上了
		//2、其他人加锁了
		//3、已经有人唤醒协程了
		if old>>mutexWaiterShift == 0 || old & (mutexLocked|mutexWoken) != 0{
			return
		}
		
		new = (old - 1<<mutexWaiterShift) | mutexWoken //waiter-1 并且将唤醒标志置为1
		if atomic.CompareAndSwapInt32(&m.state,old,new){
			//如果cas执行成功就唤醒一个协程
			runtime.Semacquire(&m.sema)
			return
		}
		old = m.state
	}
}

   面试官:不错,你的这个设计就是 2011年 Russ Cox 的第二版的Mutex实现逻辑。

三、golang 原版 Mutex

上面的分析过程就是golang Mutex的演进历史,给大家看下golang 原版 Mutex代码。
V1版本极其简单:github地址

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package sync

package func cas(val *int32, old, new int32) bool

export type Mutex struct {
	key int32;
	sema int32;
}

func xadd(val *int32, delta int32) (new int32) {
	for {
		v := *val;
		if cas(val, v, v+delta) {
			return v+delta;
		}
	}
	panic("unreached")
}

func (m *Mutex) Lock() {
	if xadd(&m.key, 1) == 1 {
		// changed from 0 to 1; we hold lock
		return;
	}
	sys.semacquire(&m.sema);
}

func (m *Mutex) Unlock() {
	if xadd(&m.key, -1) == 0 {
		// changed from 1 to 0; no contention
		return;
	}
	sys.semrelease(&m.sema);
}

V2版本增加了点细节:github地址

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package sync provides basic synchronization primitives such as mutual
// exclusion locks.  Other than the Once and WaitGroup types, most are intended
// for use by low-level library routines.  Higher-level synchronization is
// better done via channels and communication.
//
// Values containing the types defined in this package should not be copied.
package sync

import "sync/atomic"

// A Mutex is a mutual exclusion lock.
// Mutexes can be created as part of other structures;
// the zero value for a Mutex is an unlocked mutex.
type Mutex struct {
	state int32
	sema  uint32
}

// A Locker represents an object that can be locked and unlocked.
type Locker interface {
	Lock()
	Unlock()
}

const (
	mutexLocked = 1 << iota // mutex is locked
	mutexWoken
	mutexWaiterShift = iota
)

// Lock locks m.
// If the lock is already in use, the calling goroutine
// blocks until the mutex is available.
func (m *Mutex) Lock() {
	// Fast path: grab unlocked mutex.
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
		return
	}

	awoke := false
	for {
		old := m.state
		new := old | mutexLocked
		if old&mutexLocked != 0 {
			new = old + 1<<mutexWaiterShift
		}
		if awoke {
			// The goroutine has been woken from sleep,
			// so we need to reset the flag in either case.
			new &^= mutexWoken
		}
		if atomic.CompareAndSwapInt32(&m.state, old, new) {
			if old&mutexLocked == 0 {
				break
			}
			runtime_Semacquire(&m.sema)
			awoke = true
		}
	}
}

// Unlock unlocks m.
// It is a run-time error if m is not locked on entry to 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() {
	// Fast path: drop lock bit.
	new := atomic.AddInt32(&m.state, -mutexLocked)
	if (new+mutexLocked)&mutexLocked == 0 {
		panic("sync: unlock of unlocked mutex")
	}

	old := new
	for {
		// If there are no waiters or a goroutine has already
		// been woken or grabbed the lock, no need to wake anyone.
		if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken) != 0 {
			return
		}
		// Grab the right to wake someone.
		new = (old - 1<<mutexWaiterShift) | mutexWoken
		if atomic.CompareAndSwapInt32(&m.state, old, new) {
			runtime_Semrelease(&m.sema)
			return
		}
		old = m.state
	}
}

四、结尾

Golang Mutex一共优化了四版,我们上面已经分析了V1和V2版,后续会继续分析为什么还需要V3,V4版,他们又分别解决了什么问题。
最后我想出几个问题,知道答案的兄弟们可以在评论区回复:
1、为什么不用old = atomic.LoadInt32(&m.state),而直接使用old := m.state,在并发情况下不会出现不一致吗?
2、Unlock中,为啥不直接这么判断

if m.state != mutexLocked {
    panic("sync: unlock of unlocked mutex")
}

反而要这么判断:

new := atomic.AddInt32(&m.state, -mutexLocked)
	if (new+mutexLocked)&mutexLocked == 0 {
		panic("sync: unlock of unlocked mutex")
}

3、如果G1 通过Lock获取了锁, 在持有锁的期间,G2 调用Unlock释放这个锁, 会出现什么现象?

推荐阅读

1、原来阿里字节员工简历长这样

2、一条SQL差点引发离职

3、MySQL并发插入导致死锁


如果你也觉得我的分享有价值,记得点赞或者收藏哦!你的鼓励与支持,会让我更有动力写出更好的文章哦!
更多精彩内容,请关注公众号「云舒编程」

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/363164.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Redis核心技术与实战【学习笔记】 - 14.Redis 旁路缓存的工作原理及如何选择应用系统的缓存类型

概述 我们知道&#xff0c;Redis 提供了高性能的数据存取功能&#xff0c;广泛应用在缓存场景中&#xff0c;既可以提升业务的响应速度&#xff0c;又可以避免把高并发的请求发送到数据库。 如果 Redis 做缓存时出现了问题&#xff0c;比如说缓存失效&#xff0c;那么&#x…

轴承故障诊断 (12)基于交叉注意力特征融合的VMD+CNN-BiLSTM-CrossAttention故障识别模型

目录 往期精彩内容&#xff1a; 前言 模型整体结构 1 变分模态分解VMD的Python示例 第一步&#xff0c;Python 中 VMD包的下载安装&#xff1a; 第二步&#xff0c;导入相关包进行分解 2 轴承故障数据的预处理 2.1 导入数据 2.2 故障VMD分解可视化 第一步&#xff0c…

【issue-YOLO】自定义数据集训练YOLO-v7 Segmentation

1. 拉取代码创建环境 执行nvidia-smi验证cuda环境是否可用&#xff1b;拉取官方代码&#xff1b; clone官方代码仓库 git clone https://github.com/WongKinYiu/yolov7&#xff1b;从main分支切换到u7分支 cd yolov7 && git checkout 44f30af0daccb1a3baecc5d80eae229…

关于Spring框架的 @Configuration 与@Service 加载顺序哪个先后(某些环境加载是随机的)

很多资料都说Configuration 优先加载&#xff0c;Service后加载&#xff0c;如下图&#xff1a; 本来也是以为 Configuration 优先加载于 Service &#xff0c;那参数处理放在Configuration注入完后&#xff0c;service构建时就可以拿来用的&#xff0c;在我在IDEA的调试时下断…

C语言数据结构之二叉树

少年恃险若平地 独倚长剑凌清秋 &#x1f3a5;烟雨长虹&#xff0c;孤鹜齐飞的个人主页 &#x1f525;个人专栏 &#x1f3a5;前期回顾-栈和队列 期待小伙伴们的支持与关注&#xff01;&#xff01;&#xff01; 目录 树的定义与判定 树的定义 树的判定 树的相关概念 树的运用…

字符串转换const char* , char*,QByteArray,QString,string相互转换,支持中文

文章目录 1.char * 与 const char * 的转换2.QByteArray 与 char* 的转换3.QString 与 QByteArray 的转换4.QString 与 string 的转换5.QString与const string 的转换6.QString 与 char* 的转换 在开发中&#xff0c;经常会遇到需要将数据类型进行转换的情况&#xff0c;下面依…

❤ 做一个自己的AI智能机器人吧

❤ 做一个自己的AI智能机器人 看了扣子&#xff08;coze&#xff09;的模型&#xff0c;字节基于chatgpt搭建的一个辅助生成AI的网站&#xff0c;感觉蛮有意思&#xff0c;看了掘金以后&#xff0c;于是动手自己也实现了一个。 官网 https://www.coze.cn/ 进入的网站 1、 创…

如何在Windows系统使用Plex部署影音服务与公网访问本地资源【内网穿透】

文章目录 1.前言2. Plex网站搭建2.1 Plex下载和安装2.2 Plex网页测试2.3 cpolar的安装和注册 3. 本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4. 公网访问测试5. 结语 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通…

如何发布自己的npm包:

1.创建一个打包组件或者库&#xff1a; 安装weback&#xff1a; 打开项目&#xff1a; 创建webpack.config.js,创建src目录 打包好了后发现两个js文件都被压缩了&#xff0c;我们想开发使用未压缩&#xff0c;生产使用压缩文件。 erserPlugin&#xff1a;&#xff08;推荐使用…

什么是信创业态支持?支持信创的数据库防水坝哪家好?

随着国产化信创化的崛起&#xff0c;出现了很多新名词&#xff0c;例如信创业态支持、国产信创化等等。今天我们就来聊聊什么是信创业态支持&#xff1f;支持信创的数据库防水坝哪家好&#xff1f; 什么是信创业态支持&#xff1f; 大范围而言&#xff0c;信创业态支持可以理解…

多线程编程4——线程安全问题

一、线程之间是并发执行的&#xff0c;是抢占式随机调度的。 多个线程之间是并发执行的&#xff0c;是随机调度的。我们只能确保同一个线程中代码是按顺序从上到下执行的&#xff0c;无法知道不同线程中的代码谁先执行谁后执行。 比如下面这两个代码&#xff1a; 代码一&…

自定义一个线程安全的生产者-消费者模型(大厂java面试题)

生产者-消费者模型的核心思想是通过阻塞队列和线程的等待和通知机制实现生产者和消费者之间的协作&#xff0c;确保生产者不会向满队列中添加消息&#xff0c;消费者不会从空队列中获取消息&#xff0c;从而有效地解决了多线程间的同步问题。 需要实现两个方法。方法1向队列中…

Aigtek高压功率放大器主要功能是什么

高压功率放大器是一种用于将低电压信号放大到高电压水平的电子设备。它在许多领域中发挥着重要的作用&#xff0c;具有以下主要功能&#xff1a; 信号放大&#xff1a;高压功率放大器的主要功能之一是将低电压信号放大到高电压水平。它能够以较高的增益放大输入信号&#xff0c…

【云原生之kubernetes系列】--污点与容忍

污点与容忍 污点&#xff08;taints)&#xff1a;用于node节点排斥Pod调度&#xff0c;与亲和效果相反&#xff0c;即taint的node排斥Pod的创建容忍&#xff08;toleration)&#xff1a;用于Pod容忍Node节点的污点信息&#xff0c;即node节点有污点&#xff0c;也将新的pod创建…

​亚马逊测评礼品卡撸C采退如何搬砖?

亚马逊测评礼品卡搬砖、撸C是什么&#xff1f; 拿亚马逊礼品卡搬砖来讲&#xff0c;除了汇率差还有佣金。因为盈利的是美刀&#xff0c;因此比我们国内礼品卡的利润更多。比如亚马逊礼品卡&#xff0c;它的折损率比较低&#xff0c;很容易出手&#xff0c;所以是硬通货的存在。…

SD-WAN与MPLS没有取代之说,合适的才最重要

随着企业网络需求的不断增长和变化&#xff0c;SD-WAN&#xff08;软件定义广域网&#xff09;和MPLS&#xff08;多协议标签交换&#xff09;成为企业网络架构中备受关注的两种技术。然而&#xff0c;值得注意的是&#xff0c;并不存在SD-WAN完全取代MPLS或相反的情况。本文将…

SpringMVC实现对网页的访问,在请求控制器中创建处理请求的方法

目录 测试HelloWorld RequestMapping注解 RequestMapping注解的位置 RequestMapping注解的value属性 RequestMapping注解的method属性 SpringMVC支持路径中的占位符&#xff08;重点&#xff09; SpringMVC获取请求参数 1、通过ServletAPI获取 2、通过控制器方法的形参…

Git系列---标签管理

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.理解标签2.创建标签…

ThreadX_note:创建线程

ThreadX 创建线程 ThreadX 是一款实时操作系统 (RTOS)&#xff0c;它提供了一套全面的 API&#xff0c;可以用于创建和管理线程。 创建线程 在 ThreadX 中&#xff0c;我们可以使用 tx_thread_create 函数来创建线程。 exam&#xff1a; #include "tx_api.h"/*…

Ansible自动化运维实战

一、abstract简介 ansible是新出现的自动化运维工具&#xff0c;基于Python开发&#xff0c;集合了众多运维工具(puppet、cfengine、chef、func、fabric) 的优点&#xff0c;实现了批量系统配置、批量程序部署、批量运行命令等功能.无客户端。我们要学一些Ansible的安装和一些基…