2021-11-10
成都创新互联公司专注为客户提供全方位的互联网综合服务,包含不限于成都网站建设、网站制作、沁水网络推广、成都微信小程序、沁水网络营销、沁水企业策划、沁水品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;成都创新互联公司为所有大学生创业者提供沁水建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com
列表是一种非连续的存储容器,有多个节点组成,节点通过一些变量记录彼此之间的关系
单链表和双链表就是列表的两种方法。
原理:A、B、C三个人,B懂A的电话,C懂B的电话只是单方知道号码,这样就形成了一个单链表结构。
如果C把自己的号码给B,B把自己的号码给A,因为是双方都知道对方的号码,这样就形成了一个双链表结构
如果B换号码了,他需要通知AC,把自己的号码删了,这个过程就是列表的删除操作。
在Go语言中,列表使用 container/list 包来实现,内部的实现原理是双链表,列表能够高效地进行任意位置的元素插入和删除操作。
列表初始化的两种办法
列表没有给出具体的元素类型的限制,所以列表的元素可以是任意类型的,
例如给列表中放入了一个 interface{} 类型的值,取出值后,如果要将 interface{} 转换为其他类型将会发生宕机。
双链表支持从队列前方或后方插入元素,分别对应的方法是 PushFront 和 PushBack。
列表插入函数的返回值会提供一个 *list.Element 结构,这个结构记录着列表元素的值以及与其他节点之间的关系等信息,从列表中删除元素时,需要用到这个结构进行快速删除。
遍历完也能看到最后的结果
学习地址:
map 是Go语言中基础的数据结构,在日常的使用中经常被用到。但是它底层是如何实现的呢?
总体来说golang的map是hashmap,是使用数组+链表的形式实现的,使用拉链法消除hash冲突。
golang的map由两种重要的结构,hmap和bmap(下文中都有解释),主要就是hmap中包含一个指向bmap数组的指针,key经过hash函数之后得到一个数,这个数低位用于选择bmap(当作bmap数组指针的下表),高位用于放在bmap的[8]uint8数组中,用于快速试错。然后一个bmap可以指向下一个bmap(拉链)。
Golang中map的底层实现是一个散列表,因此实现map的过程实际上就是实现散表的过程。在这个散列表中,主要出现的结构体有两个,一个叫 hmap (a header for a go map),一个叫 bmap (a bucket for a Go map,通常叫其bucket)。这两种结构的样子分别如下所示:
hmap :
图中有很多字段,但是便于理解map的架构,你只需要关心的只有一个,就是标红的字段: buckets数组 。Golang的map中用于存储的结构是bucket数组。而bucket(即bmap)的结构是怎样的呢?
bucket :
相比于hmap,bucket的结构显得简单一些,标红的字段依然是“核心”,我们使用的map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”,稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针,使得bucket会形成一个链表结构。例如下图:
由此看出hmap和bucket的关系是这样的:
而bucket又是一个链表,所以,整体的结构应该是这样的:
哈希表的特点是会有一个哈希函数,对你传来的key进行哈希运算,得到唯一的值,一般情况下都是一个数值。Golang的map中也有这么一个哈希函数,也会算出唯一的值,对于这个值的使用,Golang也是很有意思。
Golang把求得的值按照用途一分为二:高位和低位。
如图所示,蓝色为高位,红色为低位。 然后低位用于寻找当前key属于hmap中的哪个bucket,而高位用于寻找bucket中的哪个key。上文中提到:bucket中有个属性字段是“高位哈希值”数组,这里存的就是蓝色的高位值,用来声明当前bucket中有哪些“key”,便于搜索查找。 需要特别指出的一点是:我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:
并不是key0/value0/key1/value1的形式,这样做的好处是:在key和value的长度不同的时候,可 以消除padding(内存对齐)带来的空间浪费 。
现在,我们可以得到Go语言map的整个的结构图了:(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中,高位用于key的快速预览,用于快速试错)
map的扩容
当以上的哈希表增长的时候,Go语言会将bucket数组的数量扩充一倍,产生一个新的bucket数组,并将旧数组的数据迁移至新数组。
加载因子
判断扩充的条件,就是哈希表中的加载因子(即loadFactor)。
加载因子是一个阈值,一般表示为:散列包含的元素数 除以 位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中:加载因子越小,说明空间空置率高,空间使用率小,但是加载因子越大,说明空间利用率上去了,但是“产生冲突机会”高了。
每种哈希表的都会有一个加载因子,数值超过加载因子就会为哈希表扩容。
Golang的map的加载因子的公式是:map长度 / 2^B(这是代表bmap数组的长度,B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。
当Go的map长度增长到大于加载因子所需的map长度时,Go语言就会将产生一个新的bucket数组,然后把旧的bucket数组移到一个属性字段oldbucket中。注意:并不是立刻把旧的数组中的元素转义到新的bucket当中,而是,只有当访问到具体的某个bucket的时候,会把bucket中的数据转移到新的bucket中。
如下图所示:当扩容的时候,Go的map结构体中,会保存旧的数据,和新生成的数组
上面部分代表旧的有数据的bucket,下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket,橘黄色代表空的bucket。
扩容时map并不会立即把新数据做迁移,而是当访问原来旧bucket的数据的时候,才把旧数据做迁移,如下图:
注意:这里并不会直接删除旧的bucket,而是把原来的引用去掉,利用GC清除内存。
map中数据的删除
如果理解了map的整体结构,那么查找、更新、删除的基本步骤应该都很清楚了。这里不再赘述。
值得注意的是,找到了map中的数据之后,针对key和value分别做如下操作:
1
2
3
4
1、如果``key``是一个指针类型的,则直接将其置为空,等待GC清除;
2、如果是值类型的,则清除相关内存。
3、同理,对``value``做相同的操作。
4、最后把key对应的高位值对应的数组index置为空。
Goroutine调度是一个很复杂的机制,下面尝试用简单的语言描述一下Goroutine调度机制,想要对其有更深入的了解可以去研读一下源码。
首先介绍一下GMP什么意思:
G ----------- goroutine: 即Go协程,每个go关键字都会创建一个协程。
M ---------- thread内核级线程,所有的G都要放在M上才能运行。
P ----------- processor处理器,调度G到M上,其维护了一个队列,存储了所有需要它来调度的G。
Goroutine 调度器P和 OS 调度器是通过 M 结合起来的,每个 M 都代表了 1 个内核线程,OS 调度器负责把内核线程分配到 CPU 的核上执行
模型图:
避免频繁的创建、销毁线程,而是对线程的复用。
1)work stealing机制
当本线程无可运行的G时,尝试从其他线程绑定的P偷取G,而不是销毁线程。
2)hand off机制
当本线程M0因为G0进行系统调用阻塞时,线程释放绑定的P,把P转移给其他空闲的线程执行。进而某个空闲的M1获取P,继续执行P队列中剩下的G。而M0由于陷入系统调用而进被阻塞,M1接替M0的工作,只要P不空闲,就可以保证充分利用CPU。M1的来源有可能是M的缓存池,也可能是新建的。当G0系统调用结束后,根据M0是否能获取到P,将会将G0做不同的处理:
如果有空闲的P,则获取一个P,继续执行G0。
如果没有空闲的P,则将G0放入全局队列,等待被其他的P调度。然后M0将进入缓存池睡眠。
如下图
GOMAXPROCS设置P的数量,最多有GOMAXPROCS个线程分布在多个CPU上同时运行
在Go中一个goroutine最多占用CPU 10ms,防止其他goroutine被饿死。
具体可以去看另一篇文章
【Golang详解】go语言调度机制 抢占式调度
当创建一个新的G之后优先加入本地队列,如果本地队列满了,会将本地队列的G移动到全局队列里面,当M执行work stealing从其他P偷不到G时,它可以从全局G队列获取G。
协程经历过程
我们创建一个协程 go func()经历过程如下图:
说明:
这里有两个存储G的队列,一个是局部调度器P的本地队列、一个是全局G队列。新创建的G会先保存在P的本地队列中,如果P的本地队列已经满了就会保存在全局的队列中;处理器本地队列是一个使用数组构成的环形链表,它最多可以存储 256 个待执行任务。
G只能运行在M中,一个M必须持有一个P,M与P是1:1的关系。M会从P的本地队列弹出一个可执行状态的G来执行,如果P的本地队列为空,就会想其他的MP组合偷取一个可执行的G来执行;
一个M调度G执行的过程是一个循环机制;会一直从本地队列或全局队列中获取G
上面说到P的个数默认等于CPU核数,每个M必须持有一个P才可以执行G,一般情况下M的个数会略大于P的个数,这多出来的M将会在G产生系统调用时发挥作用。类似线程池,Go也提供一个M的池子,需要时从池子中获取,用完放回池子,不够用时就再创建一个。
work-stealing调度算法:当M执行完了当前P的本地队列队列里的所有G后,P也不会就这么在那躺尸啥都不干,它会先尝试从全局队列队列寻找G来执行,如果全局队列为空,它会随机挑选另外一个P,从它的队列里中拿走一半的G到自己的队列中执行。
如果一切正常,调度器会以上述的那种方式顺畅地运行,但这个世界没这么美好,总有意外发生,以下分析goroutine在两种例外情况下的行为。
Go runtime会在下面的goroutine被阻塞的情况下运行另外一个goroutine:
用户态阻塞/唤醒
当goroutine因为channel操作或者network I/O而阻塞时(实际上golang已经用netpoller实现了goroutine网络I/O阻塞不会导致M被阻塞,仅阻塞G,这里仅仅是举个栗子),对应的G会被放置到某个wait队列(如channel的waitq),该G的状态由_Gruning变为_Gwaitting,而M会跳过该G尝试获取并执行下一个G,如果此时没有可运行的G供M运行,那么M将解绑P,并进入sleep状态;当阻塞的G被另一端的G2唤醒时(比如channel的可读/写通知),G被标记为,尝试加入G2所在P的runnext(runnext是线程下一个需要执行的 Goroutine。), 然后再是P的本地队列和全局队列。
系统调用阻塞
当M执行某一个G时候如果发生了阻塞操作,M会阻塞,如果当前有一些G在执行,调度器会把这个线程M从P中摘除,然后再创建一个新的操作系统的线程(如果有空闲的线程可用就复用空闲线程)来服务于这个P。当M系统调用结束时候,这个G会尝试获取一个空闲的P执行,并放入到这个P的本地队列。如果获取不到P,那么这个线程M变成休眠状态, 加入到空闲线程中,然后这个G会被放入全局队列中。
队列轮转
可见每个P维护着一个包含G的队列,不考虑G进入系统调用或IO操作的情况下,P周期性的将G调度到M中执行,执行一小段时间,将上下文保存下来,然后将G放到队列尾部,然后从队列中重新取出一个G进行调度。
除了每个P维护的G队列以外,还有一个全局的队列,每个P会周期性地查看全局队列中是否有G待运行并将其调度到M中执行,全局队列中G的来源,主要有从系统调用中恢复的G。之所以P会周期性地查看全局队列,也是为了防止全局队列中的G被饿死。
除了每个P维护的G队列以外,还有一个全局的队列,每个P会周期性地查看全局队列中是否有G待运行并将其调度到M中执行,全局队列中G的来源,主要有从系统调用中恢复的G。之所以P会周期性地查看全局队列,也是为了防止全局队列中的G被饿死。
M0
M0是启动程序后的编号为0的主线程,这个M对应的实例会在全局变量rutime.m0中,不需要在heap上分配,M0负责执行初始化操作和启动第一个G,在之后M0就和其他的M一样了
G0
G0是每次启动一个M都会第一个创建的goroutine,G0仅用于负责调度G,G0不指向任何可执行的函数,每个M都会有一个自己的G0,在调度或系统调用时会使用G0的栈空间,全局变量的G0是M0的G0
一个G由于调度被中断,此后如何恢复?
中断的时候将寄存器里的栈信息,保存到自己的G对象里面。当再次轮到自己执行时,将自己保存的栈信息复制到寄存器里面,这样就接着上次之后运行了。
我这里只是根据自己的理解进行了简单的介绍,想要详细了解有关GMP的底层原理可以去看Go调度器 G-P-M 模型的设计者的文档或直接看源码
参考: ()
()
当前文章:go语言链表是什么 go语言实现单链表反转
网站路径:https://www.cdcxhl.com/article30/ddcciso.html
成都网站建设公司_创新互联,为您提供服务器托管、、全网营销推广、关键词优化、定制网站、网站制作
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联