`
totoxian
  • 浏览: 1071215 次
  • 性别: Icon_minigender_2
  • 来自: 西安
文章分类
社区版块
存档分类
最新评论

RCU锁在linux内核的演变

 
阅读更多

2.6内核引入了RCU锁,这种锁十分高效,总的说来就是读时加锁,写时拷贝,读后更新。具体的流程可以参照 rcu的相关文档。本文主要谈一下rcu在linux2.6内核的演变过程,它分别经历了三个阶段,分别是传统rcu锁,可抢占rcu锁以及2.6.29 中将要引入的树形分层rcu锁。
linux中最早引入的rcu锁十分的粗糙,实现原理也是非常简单,毕竟linux中不管多复杂的机制一开始的时候都是十分简单的,这一点可以看看 linux0.01到linux2.6.28的演变。传统的rcu锁就是在有读者读数据的时候加上rcu锁,注意这里的“加锁”仅仅是逻辑意义上的加锁, 至于真正实现可以很灵活,实际上linux的实现就没有用到所谓的锁,而是简单的禁用抢占。为何可以这么实现呢?因为在一个cpu上禁用了抢占也就禁用了 这个cpu上的进程切换,该cpu上的当前进程将一直运行,除非重新使能抢占,那么什么时候使能抢占呢?当然是在读者释放rcu锁的时候了,而linux 中传统rcu实现规定在进程切换的时候才会运行更新回调函数,这就是本质。每当一个cpu经历进程上下文切换时,rcu就说此cpu经过了一个 quiescent state,而所有的cpu都经过一个quiescent state的时间称为一个grace period,在这个grace period点之后,该grace period的更新回调函数就可以被安全的执行了,因为此时,系统已经确定所有的读者都不再持有rcu锁了。我们再次理一下这是为什么,读者释放锁就是使 能抢占,也就是可以切换进程,而且换进程的时候rcu就认为经过了一个quiescent state,所有的cpu都经过了一个quiescent state意味着所有的cpu都可以进程切换了,就是意味着所有的cpu上的读者都不再持有rcu锁了。就是这么简单,但是我们看一下这个实现会存在什么 问题,只要读者加锁,就意味着禁用抢占,就是禁止切换,这会很大地减低系统的交互性能,当然也会降低实时任务的性能,这一切都不是想要的,单独一个rcu 把大家都拖下水实在不应该,难道要为了保护读者保护的数据而冻住整个系统不让切换进程吗?传统的rcu不允许占有rcu的进程睡眠,睡眠了进程又不允许切 换,系统就相当于死掉了。于是下一个版本的rcu就要出来了,它试图将rcu对系统的影响减小到最小,也就是说将rcu单独做成一个可以自洽自治的模块, 它本身就可以处理好数据的保护而不再需要通过系统其它的机制来确保rcu读者数据在允许更新前被保护,这就是preemptible-RCU锁。其实 linux最开始引入的所谓传统的rcu锁是一个很失败的实现,操作系统的任务就是管理各种复杂的模块以模拟真实世界,优秀的操作系统可以做到模块化的管 理各种机制,比如进程,内存,设备,以及各种锁和并发机制等等,在管理它们的时候各个模块低耦合地通信而不至于互相依赖互相影响性能,如果说要想不出问 题,最简单也是最失败的方式就是只让一个进程跑,没有切换没有共享当然也就没有了竞争,没有竞争也就意味着没有竞态,也就意味着没有了并发问题,这很简 单,但是很不灵活,也让人感觉到这不是一个优秀的操作系统,就好像人不能说怕淋雨就不出门,正确的解决方案就是发明出雨伞和雨衣。linux第一代rcu 就是这种很差劲的实现。
既然第二代rcu是preemptible的rcu,那么就是说在持有rcu锁期间不再需要禁用抢占了,这个实现看到这里就知道它是一个很优秀的实现,因 为它不再需要抢占机制帮忙来实现数据保护,rcu的内部机制已经可以实现数据保护了。那么它是怎么实现的呢?如果你不想用别的机制实现rcu数据保护,那 么就要自己实现,当然代价就是引入新的数据结构和逻辑控制机制,在preemptible-rcu中,一个grace period被分解为了两个阶段而不是所有cpu完成quiescent state了所有的数据保护机制都是在这两个阶段大做文章而实现的。这两个阶段通过一系列的软件计数器来实现了rcu,之所以分为两个阶段是因为rcu有 lock和unlock两个动作,我们能不能像实现传统rcu一样,不用真正的锁就实现逻辑上的rcu锁呢?当然可以了,引入一个每cpu变量:
#define GP_STAGES 2
struct rcu_data {
spinlock_t lock; //保护此结构中字段的自旋锁
long completed; //总的阶段计数器
int waitlistcount;
struct rcu_head *nextlist; //一些链表,记录更新回调函数
struct rcu_head **nexttail;
struct rcu_head *waitlist[GP_STAGES];
struct rcu_head **waittail[GP_STAGES];
struct rcu_head *donelist;
struct rcu_head **donetail;
long rcu_flipctr[2]; //这个很重要
struct rcu_head *nextschedlist;
struct rcu_head **nextschedtail;
struct rcu_head *waitschedlist;
struct rcu_head **waitschedtail;
int rcu_sched_sleeping;
};
rcu_flipctr 这个字段十分重要,它是一个数组,每个元素其实就是一个计数器,第一个元素记录的是在本阶段中的本cpu的rcu锁持有者数量,而第二个元素表示上个阶段 的还没有释放的本cpu的rcu锁数量,注意,只有unlock操作可以递减第二个元素,lock操作只能递增第一个元素,另外unlock操作也可以递 减第一个元素,一旦所有cpu的第二个元素的和变为0了,那么就可以向前推进一个阶段了,在下一个阶段中,第一个元素成了只有unlock才能递减的元 素,而第二个元素lock和unlock都可触及,记录着当前阶段的新rcu锁数量,往下依次类推。每个阶段都要等待所有cpu的rcu_flipctr 的同一个元素的和成为0,然后进入下一个阶段,进入下一个阶段同时交换rcu_flipctr的两个元素的意义。系统维持一个状态机,为rcu设置了好几 种状态,其中包括一个等待所有cpu的前一个阶段的rcu计数器降到0的状态,这一个状态过去以后,rcu状态机就可以向前推进一个阶段了,注意,可抢占 的rcu锁机制的重点执行点不再是grace period,而是一个grace period的两个阶段,可抢占的rcu锁也是以阶段为基准的,也就是说,在每一个阶段结束时都会有一个计数器的和降为0,这时同步将这个计数器对应的回 调函数链表推进到最前面,然后就可以安全地执行这些更新回调函数了,这里执行回调函数链表的时间是每个阶段结束,而不必等到一个grace period的第二个阶段结束时。原先的传统rcu的实现在机进程切换时更新quiescent state状态然后判断是否过了一个grace period,现在的可抢占的rcu中,仅在时钟中断里面执行rcu状态机,状态机根据其前一个状态和当前的rcu状态采取不同的措施以维持状态机继续运 转,这么看来可抢占的rcu就和抢占没有关系了,cpu可以随便被抢占而不会破坏rcu读者保护的数据,于是就说rcu模块和抢占模块解耦合了,各自可以 通过各自的方式进行设计,调试,优化以提高性能而不用像原来那样互相依赖杂糅在一起。
我们看一下lock和unlock函数:
void __rcu_read_lock(void)
{
...
} else {
unsigned long flags;
local_irq_save(flags);
idx = ACCESS_ONCE(rcu_ctrlblk.completed) & 0x1;
ACCESS_ONCE(RCU_DATA_ME()->rcu_flipctr[idx])++;
ACCESS_ONCE(t->rcu_read_lock_nesting) = nesting + 1;
ACCESS_ONCE(t->rcu_flipctr_idx) = idx;
local_irq_restore(flags);
}
}
void __rcu_read_unlock(void)
{
...
} else {
unsigned long flags;
local_irq_save(flags);
idx = ACCESS_ONCE(t->rcu_flipctr_idx);
ACCESS_ONCE(t->rcu_read_lock_nesting) = nesting - 1;
ACCESS_ONCE(RCU_DATA_ME()->rcu_flipctr[idx])--;
local_irq_restore(flags);
}
}
然后看一幅图:
clip_image002
另外linux绝对不会放过任何可以优化的空间的,只要能节省一条指令的执行,那么linux内核就会认为这么做就是值得的,比如在可抢占的rcu中,有两个函数:
void rcu_irq_enter(void)
{
int cpu = smp_processor_id();
struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
if (per_cpu(rcu_update_flag, cpu))
per_cpu(rcu_update_flag, cpu)++;
if (!in_interrupt() && (rdssp->dynticks & 0x1) == 0) {
rdssp->dynticks++;
smp_mb();
per_cpu(rcu_update_flag, cpu)++;
}
}
void rcu_irq_exit(void)
{
int cpu = smp_processor_id();
struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
if (per_cpu(rcu_update_flag, cpu)) {
if (--per_cpu(rcu_update_flag, cpu))
return;
WARN_ON(in_interrupt());
smp_mb();
rdssp->dynticks++;
WARN_ON(rdssp->dynticks & 0x1);
}
}
注 意有一个dynticks,它在进入irq和出去irq的时候都会递增,它被初始化为1,但是更要注意,这种递增是有条件的,比如在 rcu_irq_enter中,这个dynticks递增的条件就是中断非嵌套并且dynticks为偶数,显然第一次进入中断时dynticks不可能 为偶数,这就是说dynticks应该第一次在rcu_irq_exit中被增加,其实这个小算法的意义就是在进入nohz的时候或者停掉时钟节拍的时 候,当事cpu就没有必要按照常规的更新自己-通知他人-等待他人的方式维持状态机了,而是直接忽略当事cpu,按照应该的方式直接将该cpu向前推进, 这样的话就免去了很多操作,在实现这个小算法的时候,巧妙地利用了奇数偶数的方式,判断上减少了很多条指令,具体不多说,最后看一眼下面的利用 dynticks的函数:
static inline int rcu_try_flip_waitack_needed(int cpu)
{
long curr;
long snap;
struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
curr = rdssp->dynticks;
snap = rdssp->dynticks_snap;
smp_mb();
if ((curr == snap) && ((curr & 0x1) == 0))
return 0;
if ((curr - snap) > 2 || (curr & 0x1) == 0)
return 0;
return 1;
}
以上就是第二代的可抢占的rcu的思想和框架,那么第三代的rcu在那些方面有所创新呢?虽然第三代的rcu还没有被合进2.6.28内核,准备合入 2.6.29内核,但是Changelog中已经描述地很清晰了,它的主体思想就是:One effective way to reduce lock contention is to create a hierarchy.这句话真的要仔细推敲,这涉及到一个设计思想问题。分布式的对等结构是趋势吗?这么看来这句话就是大错特错了,但是分级管理确实可以 省很多事,这样分级正确的话,对等结构岂不是错误的结构吗?因此这个问题很有意义。国家机器应该是何种结构呢?金字塔式的等级政府合理吗?第三代的rcu 称为树形rcu,它采用了树结构,将锁定定义为一个分层分级的操作。这就类似于百米赛跑选拔过程,如果一共有50个人参加,那么有两种方式可以进行选拔, 一个是50个人同时上场,这样的话消耗巨大,另外就是分批分组选拔,这样的话消耗很小,分批分组其实就是分级选拔,将50个人分为25组,每组2人,这样 的话同时只有2人比赛,而且25组不必在一个场地上。树形的rcu就是这么干的,把所有的cpu分组,每组2个或多于2个,这样同时竞争rcu锁的cpu 就会减少很多,低级组的赢家竞争更高一级的rcu,然后赢家继续类似的竞争。见下面的几幅图:
clip_image004
在上面的图中,6个cpu分为3组,每两个同时竞争,之后赢了的3个再竞争,避免了6个同时竞争。

clip_image006
上面的图就不多说了。在存在大量cpu的机器上,难道要把cpu们分为很多组,必须两个一组吗?没有必要,两个一组当然可以,但是那是教条,实际上文档上讲64个cpu同时竞争锁的情形下所测试得到的性能是很不错的,因此上面的图示所示的两两分组的方式实属为了说明问题而设,树形rcu的真正用武之地不是少量cpu的机器而是大量,也就是成千cpu的巨猛机器,这些是我接触不到的,因此我只谈思想而没有任何实战经验。如果为了运用树形rcu而在拥有少量cpu的机器上实施的话,那么势必会因为树形复杂的结构而占用大量的内存空间,所得到的益处不能补偿其带来的弊端,因此一味追求新技术是不对的,必须了解这种新技术最适合的场合再作考虑,考虑好是用时间换空间还是用空间换时间,自己的系统是空间重要还是时间重要。
另外树形的rcu也实现了节能机制,同样利用可抢占rcu的奇数偶数小算法技巧实现,这样持有偶数计数器的cpu就不必被唤醒以维持状态机,因为持有偶数计数器的cpu处的状态是时钟节拍停止(nohz),或者挂起状态,这样就减少了不必要的能源消耗,可谓不错。
其实,树形的分层结构不但可以实现rcu,任何锁都可以用树形结构实现,树形锁的关键在于它可以减少同时竞争锁的cpu的数量,从而避免过多的竞态。.第 一代rcu在linux上实现表明了linux可以实现这个古老的锁机制;第二代的可抢占的rcu说明了一个优秀的机制可以作为一个模块脱离别的机制独立 存在,并且活得很好;第三代的树形rcu表明在实施上,分布式的对等结构是不错的,在管理上有时分层的等级结构是必要的,毕竟实施的时候实体很多很不确 定,分布式对等结构可以增加系统的对称性提高效率,但是管理的时候实体很确定,工作很明确,分层的等级结构带来的是更有条理,管理更有效.

分享到:
评论

相关推荐

    内核的rcu锁移植到就应用层的实现

    内核的RCU(Read-Copy Update)锁是一种在Linux内核中广泛使用的并发控制机制,主要用于处理读多写少的场景。RCU锁的设计理念是优化读取操作,允许多个读者并行执行,同时确保在写者修改数据时,所有还在使用旧数据...

    Linux 内核RCU机制的使用

    RCU(Read-Copy-Update)是一种专门针对读多写少场景优化的同步机制,在Linux内核2.5版本开发期间引入。尽管其核心概念相对简单,但理解和掌握这一机制却需要一定的过程。RCU的核心思想是在读取数据时避免锁定操作,...

    rcu_linux_rcu_linuxmemory_

    在Linux内核中,RCU是核心的同步原语之一,它允许对共享数据结构进行无锁更新,同时最大化读取性能。以下是对RCU技术及其在Linux内核中的应用的详细阐述: **1. RCU的基本原理** RCU的核心思想是,当一个数据结构被...

    史上最全linux内核配置详解

    史上最全linux内核配置详解。对于每一个配置选项,用户可以回答"y"、"m"或"n"。其中"y"表示将相应特性的支持或设备驱动程序编译进内核;"m"表示将相应特性的支持或设备驱动程序编译成可加载模块,在需要时,可由系统...

    linux 内核RCU机制分析

    Read-Copy-Update(简称RCU)是一种在Linux内核中广泛使用的并发控制技术。它主要用于处理读取密集型场景下的数据一致性问题,通过允许读操作不受写操作的影响,从而提高了系统的并发性能。 #### 二、RCU机制 ####...

    Linux内核数据同步经典方法

    在Linux内核中,有几种经典的数据同步方法,主要包括互斥锁(Mutex)、读写锁(Read-Write Lock)、顺序锁(Seqlock)、信号量(Semaphore)、自旋锁(Spinlock)和RCU(Read-Copy Update)等。 1. 互斥锁(Mutex)...

    Linux 内核分析

    通过分析RCU在Linux内核中的演变过程,我们可以了解到Linux内核对新引入技术的影响,以及这些技术如何适应Linux内核中多样化的负载和平台需求。 #### 引言 Linux内核被广泛应用于从手机到超级计算机的各种平台上,...

    Linux内核之list_head

    在Linux内核中,链表数据结构的实现主要集中在`include/linux/list.h`文件中。尽管本节以2.6内核为例,但2.4内核中的链表结构与其基本一致,仅有一些扩展,如链表的读拷贝更新(RCU)和HASH链表(hlist)等。 **基本...

    LINUX RCU 经典教程

    通过学习这个LINUX RCU经典教程,你可以深入理解RCU如何在Linux内核中实现无锁编程,以及如何在自己的代码中有效地利用RCU来提升系统性能。同时,掌握RCU的使用技巧和优化策略,对于开发高效、可靠的多线程应用程序...

    linux内核链表介绍与了解

    在Linux内核2.6版本中,引入了两种扩展的链表数据结构:读拷贝更新(Read-Copy Update, RCU)链表和HASH链表(hlist)。RCU是一种优化技术,允许在读多写少的场景下,即使在数据结构正在被修改的情况下,也能安全地...

    LINUX内核编程---相当经典

    在IT领域,Linux内核编程是一项高级且至关重要的技能,对于理解操作系统的工作原理以及开发高效、低级系统软件至关重要。"LINUX内核编程---相当经典"这一教程很可能提供了深入的见解,帮助学习者掌握这一复杂的主题...

    linux 内核源码情景分析.rar

    《Linux内核源码情景分析》是一本深入探讨Linux内核源码的权威书籍,它为读者提供了一条理解这个复杂而精妙的操作系统内核的路径。这本书以丰富的实例和详细的情景分析,帮助读者逐步揭示Linux内核的运作机制,是IT...

    Linux2.6内核标准教程(共计8-- 第1个)

    最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU这两种新的 同步机制。 《Linux2.6内核标准教程》适合Linux内核爱好者、Linux驱动开发人员、Linux系统工程师参考使用,也可以作为计算机及相关...

    rcu_example:linux内核的rcu示例。 标签

    **RCU(Read-Copy Update)技术是Linux内核中的一种并发原语,主要用于处理多处理器环境下的数据结构更新问题。RCU的核心理念是允许多个读者并行访问数据,同时仅在一个单独的写者更新数据时短暂地阻止读者。在Linux...

    Linux内核编程与调试.pdf

    根据提供的文件信息,我们可以深入探讨Linux内核编程中的一些关键概念和技术细节,特别是关于原子操作、自旋锁、信号量、“读者-写者锁”、读-拷贝-更新(RCU)机制以及互斥体(mutex)和完成变量(completion)等...

    linux 2.6内核标准教程

    最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU这两种新的同步机制。 本书适合Linux内核爱好者、Linux驱动开发人员、Linux系统工程师参考使用,也可以作为计算机及相关专业学生深入学习操作系统...

    深入分析Linux内核链表(超详细)

    在Linux内核中,链表的实现方式和传统意义上的链表有所不同,它采用了更优化的设计以适应内核操作的高效性要求。 首先,Linux内核链表的核心数据结构是一个名为`list_head`的结构体,它包含了两个指针,`next`和`...

    linux锁机制分析

    除了基本的自旋锁和信号量外,Linux内核还支持读写锁,如 `rwlock_t` 和 `rw_semaphore`。这些锁支持多读者共享,但只允许一个写者独占,非常适合读多写少的场景。 #### 六、替代方案:RCU与原子变量 - **RCU**...

Global site tag (gtag.js) - Google Analytics