You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
MCS锁的名字来源于他的两个发明者Mellor-Crummey和Scott,他俩在1991年创造MCS发表在期刊上面。就算是FIFO自旋锁也存在一个比较大的问题,就是slock值是共享的。如果在单核系统里面没有任何的问题,但是在SMP和NUMA多核系统里面,多核共同修改一个share属性的slock值就会因为cache颠簸的问题,导致性能下降。这是由于MESI缓存一致性协议参与多核之间的cache一致性问题引入的。锁在多核使用的过程中,使得snooping control unit多次参与CPU数据和cache的多次失效。MCS锁的引入就是解决这个问题,原理是在本地CPU上面各自建立锁的副本(PerCPU变量3),只对本地操作,再进行多核的同步。这样就可以避免snooping control unit参与cache的一致性维护。这个锁被称为Queued SpinLock, QSpinLock。
0x33_LinuxKernel_同步管理_原子操作_内存屏障_锁机制等
当一个资源被多个使用者竞争的时候,必然要去做一些保护措施。这个竞争者可能是中断、也可能是另一个core。Linux在用户空间给我们提供了很多同步手段,这些手段在system-v和poxis标准里面有所体现,system-v更面向于随内核持续的资源,而poxis更面向于随进程持续的资源。这些用户空间的同步手段,最终还是调用内核的low-level同步函数,而且内核中的资源保护,也指向了这些low-level的同步函数。本文主要就是来描述,内核的low-level的同步函数是如何实现的,他们的设计思想和理念是什么。对于之前的知识,请复习:
LDXR
STXR
。1. 同步操作论述
首先引入一个内核控制路径(kernel control path) 简称:内核路径的概念1,内核执行路径可以是中断处理程序、内核线程等。我们可以简单的引用文献2中的内容来解释内核路径中比较重要的事情参考附录X:内核抢占。
早起不支持SMP的Linux内核中,导致并发访问的因素是中断服务程序,只有在中断发生的时候,或者内核代码路径显式要求重新调度并且执行另一个进程时候,才有可能发生并发访问。而在支持SMP的Linux内核中,并发运行在不同的CPU中的内核线程完全有可能同一时刻访问共享数据。尤其是现在内核支持内核抢占。
内核中产生并发访问的并发源主要有四种:
若在single-core系统中:
若在SMP系统中:
处理一下情况应该十分小心:
锁和同步工具的使用并不难,而真正的难点在于如何发现内核代码存在并发访问。理论上,多个内核代码路径可能访问的资源都要去保护(需要我们设计者在设计之初就要trace执行路径,把控中断、进程切换点、使用的内核延迟机制);还要注意,我们保护的是资源,而不是代码,这些资源是:全局变量、共享的数据结构、缓存、链表、红黑树等隐形的数据结构。要考虑:
Linux提供了丰富的工具,包含:原子操作、自旋锁、信号量、互斥锁、读写锁、RCU等,我们来看看具体如何实现的。
2. 原子操作与内存屏障
2.1 原子操作论述
先说一下一个问题,如下代码,两个线程同时对i进行++,(执行完之后)最后i的值是多少?
这个数可能是2,也可能是1,为什么呢?这是由于ARM的流水线乱序执行导致的,我们的C语言虽然只有一条指令,但是转为汇编伪代码,大概意思是:
如果流水线执行顺序是这样呢:
此时乱序执行thread_b最后把A的计算结果覆盖,最后得到的不是1,而是2。问题就出在了,thread_b加载数据的值的时机有问题,thread_b应该等thread_a回写完数据之后再去load数据。
讲到这里,可能有人就考虑使用内存屏障了(如下代码),我们在操作前加上mb()强制要求处理器执行完毕之后才可以执行后面的指令。
还有一种方法是加锁,的确可以达到效果,但是对于一个变量而言,这个代价未免有点大。对于一个变量,实际上我们可以使用原子操作类型的函数来处理:
这种就可以实现保证没有上面的操作了,因为ATOMIC操作,把上面三个指令“合并”成了一条:"读-修改-回写"变成了一条组合指令。
我们来复习一下底层的ARM知识,原子操作在架构层级提供了什么帮助,引用06_ARMv8_指令集_一些重要的指令 包含原子操作的ARM机制-独占监视器(Exclusive monitor),及使用它的指令
LDXR
STXR
。2.2 Linux基本原子操作函数
Linux内核提供了最基本的原子操作的函数包括:
2.2.1 不带返回值的
atomic_read(atomic_t *v)
:该函数对原子类型的变量进行原子读操作,它返回原子类型的变量v的值。atomic_set(atomic_t *v,int i)
:该函数设置原子类型的变量v的值为i。atomic_add(int i, atomic_t *v)
:该函数给原子类型变量v增加i。atomic_sub(int i, atomic_t *v)
:该函数给原子类型变量v减去i。atomic_sub_and_test(int i, atomic_t *v)
:该函数从原子类型的变量v中减去i,并判断结果是否是0,如果为0,返回真,否则返回假。atomic_inc(atomic_t *v)
:该函数对原子变量v原子的增加1。atomic_dec(atomic_t *v)
:该函数对原子变量v原子的减少1。atomic_dec_and_test(atomic_t *v)
:该函数对原子类型的变量v原子的减少1,并判断结果是否是0,如果是0,返回真,否则返回假。atomic_inc_and_test(atomic_t *v)
:该函数对原子类型的变量v原子增加1,并判断结果是否是0,如果是0,返回真,否则返回假。atomic_add_negative(int i, atomic_t *v)
:该函数对原子类型的变量v原子的增加I,并判断结果是否是负数,如果是,返回真,否则返回假。atomic_add_return(int i, atomic_t *v)
:该函数对原子类型的变量v原子的增加i,并且返回指向v的指针。atomic_sub_return(int i, atomic_t *v)
:该函数对原子累心的变量v中减去i,并且返回指向v的指针。2.2.2 带返回值的
除了这些之外,还有一些带返回值的原子操作函数格式为
atomic_fetch_{add,sub,or,xor}
返回原子变量的值。2.2.3 原子交换函数
Linux内核提供了一些原子交换函数:
atomic_cmpxchg(ptr, old, new)
:原子比较ptr和值是否和old相等,若相等,把new的值放在ptr地址中,返回old。atomic_xchg(ptr, new)
:原子地把new的值放在ptr地址中并返回ptr的原值。atomic_try_cmpxchg(ptr, old, new)
:与atomic_cmpxchg函数类似,但是返回值发生变换,返回一个bool值,以判断是否相等。2.2.4 处理引用计数的原子操作
在内核代码中很多地方使用了引用计数机制,比如page的
_ref_count
和_map_count
。atomic_add_unless(atomic_t *v, int a, int u)
:比较v的值是否等于u;atomic_inc_not_zero(v)
:比较v的值是否等于0;atomic_inc_and_test(v)
:原子地给v加1,然后判断v的新值是否等于0;atomic_dec_and_test(v)
:原子地给v减1,然后判断v的新值是否等于0;2.2.5 内嵌memory barrier的原子操作函数
{}_relaxed
:不内嵌内存屏障原语的原子操作;{}_acquire
:内置了load-store
内存屏障原语的操作;{}_release
:内置了store-release
内存屏障源于的操作;2.4 原子操作底层实现示例
我们以atomic_add为例子,了解一下在Linux上面底层原子操作什么样子的。
使用了内嵌汇编的方式实现,主要使用了ldxr和stxr独占访问内存的指令。除此之外,对于独占比较交换,还使用了
cas
等。3. 内存屏障
ARM架构有3类内存屏障指令:
Linux内核在底层则使用这些指令完成自己的接口:
在内核代码中这些函数实现很简单:
4. 自旋锁
上一节我们说了原子操作的应用范围,临界区小到了一个变量,而当我们操作链表时候,或者临界区内是有函数调用的时候,这时候就该考虑锁机制了。谈起用户空间的自旋锁,pthread在用户空间提供了pthread_spinlock这类的函数,我们闭着眼睛就能说出spinlock的特性:
4.1 经典自旋锁
spinlock和CPU架构息息相关。早起的自旋锁十分简单,描述自旋锁的机构提就是用一个变量表示,但这个方法性能十分低下,因为在激烈竞争锁的时候出现锁的持有者释放后会再次拿到锁,对于多线程的执行分给各个线程的时间片就非常不公平。自从Linux2.6.25内核之后,自旋锁实现了一套基于FIFO的排队机制。
4.1.1 spinlock的FIFO机制
定义slock分为next和owner,这个机制就类似于去饭店吃饭。假设饭店开张只有一个位置,初始的next和owner都是0:
大概就是以上的意思。
4.1.2 spinlock
Linux中的经典自旋锁定义如下:
spinlock结构体考虑了不同架构体系的支持,所以这里使用arch_spinlock定义。在ARM64的spinlock实现如下:
这个实现就是按照我们上面说的原理,实现了next和owner之间的增加操作。而且在spinlock实现中,依然大量的使用独占内存访问的。
4.1.2.1 raw_spin_lock
在内核代码里面经常看见
raw_spin_lock
的身影,甚至有些代码spinlock
直接调用raw_spin_lock
。这里面有个小故事,Linux有一些分支需要打RT-patch,这个RT-patch就是为了让Linux能够支持一些实时操作系统的特性。因此,就有个需求,允许自旋锁在临界区被抢占,在临界区内允许自旋锁睡眠。注意哈,普通的自旋锁这个两个完全不允许的,但是实时操作系统是必须要支持的。但是RT-patch如果主意的修改自旋锁调用位置,且一一甄别,那工作量十分巨大了,不过需要抢占的地方工程师们筛查出来仅仅只有一百多处,因此把这部分的自旋锁改为raw_spin_lock
。所以,对于实时Linux,
raw_spin_lock
和spin_lock
是有区别的,raw能够支持在临界区抢占,能够支持在临界区睡眠;但是对于没有实时补丁的Linux而言,raw_spinlock和spinlock完全等价。4.1.2.2 spin_lock_irq
在需要依赖中断处理器的设备驱动开发,常常遇到这样的问题,驱动某一个链表中有很多设备需要访问和更新,例如open\ioctl等等。操作链表时候通常会把操作链表划为一个临界区,需要用自旋锁来保护。当处于临界区的时候,系统将暂停当前进程去执行中断。假如恰巧中断程序也要处理这个链表,链表被主进程锁住了,中断永远拿不到这把锁,这就是死锁。所以linux提供了spin_lock_irq来对这个问题进行解决,在加锁之前直接
preempt_disable()
关闭内核抢占,local_irq_disable()
关闭中断和抢占。注意,
preempt_disable
关闭了内核抢占,内核就不会去主动抢占。但编程者需要小心自己抢占自己,这种情况经常非常隐晦的发生在调用函数中。例如kmalloc()函数放在了临界区,此时有可能因为内存不足而在函数内部进行了睡眠,但kmalloc被我们编程者放在了临界区内,这就发生了死锁现象,除非显式地给定kmalloc(GFP_ATOMIC)指定kmalloc为一个原子操作。(这个例子我觉得非常好)。另外,还有
spin_lock_irqsave
这个函数,他比lock_irq多了一个功能就是保存当前中断状态,内部调用了local_irq_store
,会把CPU的状态寄存器保存起来(例如ARM的CPSR寄存器),这样的目的是防止中断状态被破坏。自旋锁还有个变种就是spin_lock_bh()
用于处理进程和延迟处理机制导致的并发访问的互斥问题。4.2 MCS锁
MCS锁的名字来源于他的两个发明者Mellor-Crummey和Scott,他俩在1991年创造MCS发表在期刊上面。就算是FIFO自旋锁也存在一个比较大的问题,就是slock值是共享的。如果在单核系统里面没有任何的问题,但是在SMP和NUMA多核系统里面,多核共同修改一个share属性的slock值就会因为cache颠簸的问题,导致性能下降。这是由于MESI缓存一致性协议参与多核之间的cache一致性问题引入的。锁在多核使用的过程中,使得snooping control unit多次参与CPU数据和cache的多次失效。MCS锁的引入就是解决这个问题,原理是在本地CPU上面各自建立锁的副本(PerCPU变量3),只对本地操作,再进行多核的同步。这样就可以避免snooping control unit参与cache的一致性维护。这个锁被称为Queued SpinLock, QSpinLock。
这里暂时不展开了。后面有时间用到之后,再去理解如何设计的!
5. 信号量和互斥锁
我们在用户空间知道信号量和互斥锁有着相似的特性,但是也有一些差别。它们在等待锁的释放的时候都是进入睡眠等待的,它们是支持调度的;而区别是,信号量是同步的机制,是存在同步深度的(“洗手间理论”,信号量相当于一个N人的洗手间),而互斥量是一个布尔型的互斥锁。在功能上,信号量的一级深度可以实现和互斥锁一模一样的功能。但是需要注意,信号量内部实现数据结构比互斥锁复杂,注定是比互斥锁低效的,速度快是互斥锁的广泛使用的原因,并且互斥锁的一些特性也用到了信号量身上,比如“乐观自旋”(Optimistic spinning)。
总得来说,互斥锁比信号量高效的多,体现在:
spinlock和(信号量+互斥锁)的应用场景我们可以拿这个例子举例:最典型的消费者和生产者线程。例如,我们去餐厅吃饭,可能没有位置了,但看着人数也不多,就整个人坐在餐厅门口等着有位置空闲,这个场景可以用spinlock解释,一种让我们整个人都等在那里的,短时间能够忍受的;而互斥锁和信号量更像是网络预订,我们去4S店预订汽车,发现汽车没有了,需要联系厂家制造,你会和4S店的店员讲,我先排队,等着到货的时候给我打电话,然后你离开4S店正常生活吃饭,等着有一天店员给你打电话之后你再去买车。这两个生活场景可以解释spinlock和mutex(sem)的应用场景。没有人会在4s店门口拿个板凳等着车到了是吧。因此**,spinlock用于那种短时的值的你去等的场景,而mutex和信号量常常配合完成变量等通知再去取资源**。
5.1 信号量
在Linux定义的信号量的数据结构如下:
操作信号量的接口:
down
down_interruptible
down_trylock
down_timeout
相应的还有
up_{ , interruptible, trylock, timeout}
函数。5.2 互斥锁
在Linux定义的互斥锁的数据结构如下:
CONFIG_MUTEX_SPIN_ON_OWNER
选项才会有owner,用于指示锁持有着的PCB;因为互斥锁的简洁性和高效性,所以使用互斥锁要更严格,需要注意以下条件:
在工程中spinlock和mutex选择原则如下:
另外,除了满足不了上面互斥锁的约束条件,否则都优先使用互斥锁。
6. RCU
我们这里简要介绍一些RCU的功能,不再详细描述。RCU(Read-Copy Update),是Linux内核的一种同步机制。无论是自旋锁、互斥锁、信号量,其内部都直接或者间接的使用原子操作,而在架构上原子操作的monitor机制会过多的访问内存,导致性能下降。而且信号量还有一个缺点,只允许多个读者存在,不允许读者和写者同时存在。RCU机制的目标就是为了降低同步开销,让读操作没有任何负担,不需要使用原子操作和内存屏障指令。
RCU可以参考文献4,也可以在内核代码/documents/RCU/wahtisRCU.txt路径找到,这里就不做过多的介绍了。
X. 附录
内核抢占
Ref
Footnotes
内核控制路径,内核同步,中断,异常--x86 ↩
深入理解 Linux 内核—内核同步 ↩
PERCPU变量实现 ↩
What is RCU, Fundamentally? ↩
The text was updated successfully, but these errors were encountered: