hilinux是什么系统,你们好,明天给你们分享并行程序设计中最重要的锁-RCU锁,RCU锁本质是用空间换时间,是对读写锁的一种优化强化,但不仅仅是这样简单,RCU彰显下来的垃圾回收思想,也是值得我们学习和借鉴,各个语言C,C++,Java,go等标准库都有RCU锁实现,同时内核精致的实现也是学习代码设计好素材,深入理解RCU分为两个部份,第一部份主要是讲核心原理,理解其核心设计思想,对RCU会有个宏观的理解;后续第二部份会剖析源码实现,希望你们喜欢。
并行程序设计演化
怎样正确有效的保护共享数据是编撰并行程序必须面临的一个困局,一般的手段就是同步。同步可分为阻塞型同步(BlockingSynchronization)和非阻塞型同步(Non-blockingSynchronization)。
阻塞型同步是指当一个线程抵达临界区时,因另外一个线程早已持有访问该共享数据的锁,因而不能获取锁资源而阻塞(睡眠),直至另外一个线程释放锁。常见的同步子句有mutex、semaphore等。假如同步方案采用不当,才会导致死锁(deadlock),活锁(livelock)和优先级反转(priorityinversion),以及效率低下等现象。
为了增加风险程度和增强程序运行效率,业界提出了不采用锁的同步方案,根据这些设计思路设计的算法称为非阻塞型同步,其本质就是停止一个线程的执行不会妨碍系统中其他执行实体的运行。
先有阻塞型同步
互斥锁(英語:Mutualexclusion,简写Mutex)是一种用于多线程编程中,避免两条线程同时对同一公共资源进行读写的机制。该目的通过将代码切块成一个一个的临界区域(criticalsection)达成。临界区域指的是一块对公共资源进行存取的代码。
讯号量(Semaphore),是在多线程环境下使用的一种设施,是可以拿来保证两个或多个关键代码段不被并发调用,可以觉得mutex是0-1讯号量;
读写锁是计算机程序的并发控制的一种同步机制,它把对共享资源的访问者界定成读者和写者,读者只对共享资源进行读访问,写者则须要对共享资源进行写操作,读操作可并发重入,写操作是互斥的。
再有非阻塞型同步
现今比较流行的非阻塞型同步实现方案有三种:
Wait-free(无等待)
Wait-free是指任意线程的任何操作都可以在有限步之内结束,而不用关心其它线程的执行速率。Wait-free是基于per-thread的,可以觉得是starvation-free的。十分遗憾的是实际情况并非这么,采用Wait-free的程序并不能保证starvation-free,同时显存消耗也随线程数目而线性下降。目前只有极少数的非阻塞算法实现了这一点。
简单理解:任意时刻所有的线程都在干活;Lock-free(无锁)
Lock-Free是指才能确保执行它的所有线程中起码有一个才能继续往下执行。因为每位线程不是starvation-free的,即有些线程可能会被任意地延后,但是在每一步都起码有一个线程才能往下执行,因而系统作为一个整体是在持续执行的,可以觉得是system-wide的。所有Wait-free的算法都是Lock-Free的。
简单理解:任意时刻起码一个线程在干活;Obstruction-free(无障碍)
Obstruction-free是指在任何时间点,一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争,线程就可以持续运行。一旦共享数据被更改linux内核设计和实现,Obstruction-free要求终止早已完成的部份操作,并进行回滚。所有Lock-Free的算法都是Obstruction-free的。
简单理解:只要数据有更改,才会重新获取,而且把早已完成操作回滚重来;
综上所述,不难得出Obstruction-free是Non-blockingsynchronization中性能最差的,而Wait-free性能是最好的,但实现难度也是最大的,因而Lock-free算法开始被注重,并广泛运用于各类程序设计中,这儿主要介绍Lock_free算法。
lock-free(无锁)常常可以提供更好的性能和伸缩性保证,但实际上其优点不止于此。初期这种概念首先是在操作系统上应用的,由于一个不依赖于锁的算法,可以应用于各类场景下,而无需考虑各类错误,故障,失败等情形。诸如死锁,中断,甚至CPU失效。
主流无锁技术
Atomicoperation(原子操作),在单一、不间断的步骤中读取和修改数据的操作。须要处理器指令支持原子操作:
●test-and-set(TSR)
●compare-and-swap(CAS)
●load-link/store-conditional(ll/sc)
SpinLock(载流子锁)是一种轻量级的同步方式,一种非阻塞锁。当lock操作被阻塞时,并不是把自己挂到一个等待队列,而是死循环CPU空转等待其他线程释放锁。
Seqlock(次序锁)是Linux2.6内核中引入一种新型锁,它与spinlock读写锁十分相像,只是它为写者赋于了较高的优先级。也就是说,虽然读者正在读的时侯也容许写者继续运行,读者会检测数据是否有更新,假如数据有更新都会重试,由于seqlock对写者更有利,只要没有其他写者,写锁总能获取成功。
RCU(Read-CopyUpdate),顾名思义就是读-拷贝更改,它是基于其原理命名的。对于被RCU保护的共享数据结构,读者不须要获得任何锁就可以访问它,但写者在访问它时首先拷贝一个副本,之后对副本进行更改,最后使用一个反弹(callback)机制在适当的时机把指向原先数据的表针替换为新的被更改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的访问。
本文主要讲解RCU的核心原理。
历史背景
高性能并行程序中,数据一致性访问是一个十分重要的部份,通常都是采用锁机制(semaphore、spinlock、rwlock等)进行保护共享数据,根本的思想就是在访问临界资源时,首先访问一个全局的变量(锁),通过全局变量的状态来控制线程对临界资源的访问。并且,这些思想是须要硬件支持的,硬件须要配合实现全局变量(锁)的读-更改-写,现代CPU还会提供这样的原子化指令。
采用锁机制实现数据访问的一致性存在如下两个问题:
原始的RCU思想
在多线程场景下,常常我们须要并发访问一个数据结构,为了保证线程安全我们会考虑使用互斥设施来进行同步,更进一步我们会依据对这个数据结构的读写比列而选用读写锁进行优化。并且读写锁不是惟一的方法,我们可以利用于COW技术来做到写操作不须要加锁,也就是在读的时侯正常读linux vps,写的时侯,先加锁拷贝一份,之后进行写,写完就原子的更新回来,使用COW实现防止了频繁加读写锁本身的性能开支。
异同点
因为RCU致力最小化读取端开支,因而仅在以更高速率使用同步逻辑进行读取操作时才使用它。假如更新操作超过10%linux内核设计和实现,性能反倒会变差,所以应当选择另一种同步方法而不是RCU。
缺点适用场景
资料直通车:Linux内核源码技术学习路线+视频教程内核源码
学习直通车:Linux内核源码显存调优文件系统进程管理设备驱动/网路合同栈
核心原理理论基础-QSBR算法
(QuiescentState-BasedReclamation)
这个算法的核心思想就是辨识出线程的不活动(quiescent)状态,这么哪些时侯才算是不活动的状态呢?这个状态和临界区状态是相对的,线程离开临界区就是不活动的状态了。辨识出不活动状态了,还须要把状态通知出去,让其他线程晓得,这整个过程可以用下边的图来描述:
里面有四个线程,线程1执行完更新操作后添加了释放显存的callback,此时线程2,3,4都读取的是之前的内容,等她们执行完成后分别回来调用onQuiescentState来表明自己早已不不活动了,等到最后一个线程调用onQuiescentState的时侯就可以去调用注册的callback了。要实现前面这个过程其要点就是选择适宜的位置执行onQuiescentState,还有就是怎样晓得谁是最后一个执行onQuiescentState的线程。
批量回收,假如更新的次数比较多的话,而且每次只反弹一个callback,释放一次显存都会造成显存释放跟不上回收的速率,因此须要进行批量回收,每次更新还会注册新的callback,当第一次所有的线程都步入不活动状态的时侯就把当前的所有callback保存上去,等待下一次所有线程步入不活动的状态的时侯就反弹前一次所有的callback。
基本构架
Linux内核RCU参考QSBR算法设计一套无锁同步机制。
RCU模型
三个重要概念
静止状态QS(QuiescentState):CPU发生了上下文切换称为经历一个quiescentstate;
宽责令GP(GracePeriod):graceperiod就是所有CPU都经历一次quiescentstate所须要的等待的时间,也即系统中所有的读者完成对共享临界区的访问;
GP原理
读侧临界部份RCS(Read-SideCriticalSection):保护严禁其他CPU更改的代码区域,但允许多个CPU同时读;
三个主要的角色
读者reader:
写者updater:
回收者reclaimer: