移动云

?找回密码
?立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz

[原创]Linux内核里的同步机制(1)—— 原子操作

2012-9-18 16:33| 发布者: admin| 查看: 3566| 评论: 0|原作者: platero

摘要: Linux内核里的同步机制(1)—— 原子操作 原子操作 –单一的不可中断的操作。 首先看一个counter++的例子(Sch)。 在汇编层次,这一条语句会变成3个指令, 1.将counter值从内存中拷贝到CPU寄存器R0。 2.寄存器R ...
[原创]Linux内核里的同步机制(1)—— 原子操作

原子操作 –单一的不可中断的操作。

首先看一个counter++的例子(Sch[94])
counter.png


    在汇编层次,这一条语句会变成3个指令,
    1.counter值从内存中拷贝到CPU寄存器R0
    2.寄存器R0中的值加1
    3.将寄存器的值拷回到内存。


    如果此时有两个CPU同时执行counter++,那么假设counter初始值为0,两次加1所得出来的结果就不是2,而是1Bug由此而生。
    这是一个SMP的例子。类似的,对于UP来说,如果两个任务“同时”执行counter++,那么同样会出现此问题。“同时”上面加了引号,那是因为UP永远不会真的同时,不过如果在1->2或者2->3之间切换到了另一个任务或者被中断,而此任务或中断例程也执行counter++,就有可能产生这个BUG


    如何避免上面这个问题?首先我们必须保证了1->2->3是一个单一步骤,不被“打断”(这里的打断只是逻辑意义上的,而不是特指我们通常说的中断,后文可以看到在ARMV6以上的平台,原子操作中间也是可以发生中断的)。而对于SMP,还需要保证对临界内存的访问是互斥的。


    Linux内核为原子操作提供了类型atomic_t和一组内核API,使用起来非常简单。原子版的counter++如下:

    atomic_t counter =ATOMIC_INIT(0);

    atomic_inc&counter);


    atomic_t相关的原子操作由平台代码负责实现,不同的处理器会采用不同的方式,目的都是为了上面说的两个保证。

    Linux内核如何保证这组API的原子性呢?
    1.保证不能被打断。

    从字面上理解,就是要禁止上下文切换,禁止中断发生。这个很容易实现,只要保证在这个原子操作的时候不发生中断就可以了。所以通过关本地中断就可以实现。简单粗暴而又有效。

    2.保证对共享内存的访问是互斥的。
    这一点和具体平台紧密相连。一般来说,可以通过Bus锁或者其他的对内存访问的互斥机制实现。Linux理应交给平台代码去实现。

    ARM为例,分析一下代码。以下代码均来自2.6.35.11
    在代码中,发现共有两种实现,分别为ARMV6之前,ARMV6之后。


    ARMV6之前的实现如下,

    #ifdef CONFIG_SMP

    #error SMP not supported onpre-ARMv6 CPUs

    #endif

    static inline intatomic_add_return(int i, atomic_t *v)

    {

    ? ?? ???unsignedlong flags;
    ? ?? ???intval;

    ? ?? ???raw_local_irq_save(flags);
    ? ?? ???val= v->counter;
    ? ?? ???v->counter= val += i;
    ? ?? ???raw_local_irq_restore(flags);

    ? ?? ???returnval;

    }

    #define atomic_add(i, v)? ?? ? (void) atomic_add_return(i, v)


    ARMV6之前不支持SMP,所以只要在具体实现里关中断就可以了。轻松实现两个保证。

    再看ARMV6以后,

    /*

    * ARMv6UP and SMP safe atomic ops.??We use load exclusive and
    * storeexclusive to ensure that these are atomic.??We may loop
    * toensure that the update happens.
    */

    static inline void atomic_add(inti, atomic_t *v)

    {

    ? ?? ???unsignedlong tmp;
    ? ?? ???intresult;

    ? ?? ???__asm____volatile__("@ atomic_add\n"

    "1:? ???ldrex? ?%0, [%3]\n"

    "? ?? ? add? ???%0, %0,%4\n"

    "? ?? ? strex? ?%1, %0,[%3]\n"

    "? ?? ? teq? ???%1, #0\n"

    "? ?? ? bne? ???1b"

    ? ?? ???:"=&r" (result), "=&r" (tmp), "+Qo"(v->counter)
    ? ?? ???:"r" (&v->counter), "Ir" (i)
    ? ?? ???:"cc");

    }


    这里出现了几个问题,首先,在实现上没有区分UPSMP。其次,也没有关中断及加总线锁的动作。那么这个函数如何保证原子性呢?上面有段注释很有价值。说是采用了loadexclusivestoreexclusive确保其原子性。读一下汇编发现最后一行的意思是当strex的返回值不为0(%1,tmp),会跳转到1重新执行一遍。所以最后一行注释说“Wemay loop to ensure that the update happens.”。那么strex又是什么?

    查了一下ARM用户手册[AARM],终于在A2.9找到了上面所有问题的答案。
    ldrex和和strexAMRV6引入的新的同步机制,取代了过去的SWPSWPB指令。ldrex就是Load-Exclusive的缩写,而strex就是Store-Exclusive的缩写。这两个指令与addressmonitor协同工作,为内存的访问提供了一个状态机。对于SMPUP来说,这种机制稍有不同。简单地讲,对于非共享内存的情况(UP),只需要维护一个monitor就可以了。而对于共享内存的情况(SMP),需要为每一个CPU维护一个monitor,状态机就复杂一些。但是这些区别在指令的层次上是体现不出来的。所以,使用了ldrexstrex,就不需要为UPSMP单独实现一套原子操作。

    ARM到底是如何实现这种新的同步机制的?道理上很简单。简单地说,指令ldrex会为执行处理器做一个标记(tag),说当前对该物理地址已经有一个CPU访问了,但是还没有访问完毕。当strex指令执行时,就会检查是否存在这个标记。如果存在,那么将完成这次store的过程,并且返回0,然后清除该标记。如果没有这个标记,不会完成store,返回1。这样就能够在不关闭中断,没有执行任何buslock的情况下,保证操作的原子性。详细过程请参阅ARM用户手册[AARM]

    根据Linux内核里面atomic_add的实现,分析一个UP上的并发情景。(SMP上会复杂一点,但是大体意思相同)

    • 首先会执行指令ldrex,添加一个标记(Tag),说明执行CPU标记了一个物理地址,但访问尚未完毕。
    • 假设此时发生了中断,在中断处理或者切换了上下文后需要对该值进行原子加一。

    • 在新上下文中执行指令ldrexstrex。由于此时有标记,strex会成功执行,而后更新内存,清除标记。
    • 假设此时中断返回,被中断的任务继续进行。当执行strex时,会发现标记已被清除,此时strex就不会更新内存,并且返回1
    • 跳转到1(bne? ?? ???1b),重新执行。

    上面只是一个理论过程,但是查资料的时候发现一个patch[LKM],说有一些互斥机制使用了LDREX/STREXEQ的组合,当使用这些机制的代码并发时,就可能出现LDREXSTREXEQ执行不成对的情况(STREXEQ是条件执行,未必每次都能得到执行),这样就无法保证原子性了。为了解决这个问题,就在exceptionhandler推出时,显式的调用一下clrex或者strex,这样就相当于在每次中断结束后,手动清理一下标记。也就是说,在原子操作时,只要发生了中断,标记都会被清除。

    总之,使用这种Load-exclusiveStore-exclusive机制,避免了关中断和总线锁,能够显着提高效率。

    参考资料:

    [Sch94] Curt Schimmel: UNIX Systems for Modern Architectures: Symmetric

    Multiprocessingand Caching for Kernel Programmers. Addison Wesley, 1994

    [LKM]http://lists.infradead.org/pipermail/linux-arm-kernel/2009-September/000665.html

    [AARM]ARM Architecture Reference Manual


    转载请注明原帖出处:http://bbs.t268.com/forum.php?mod=viewthread&tid=828&extra=





相关分类

小黑屋|管理员QQ:44994224|邮箱(t268studio@gmail.com)|Archiver|MCLOUDER

GMT+8, 2019-9-24 13:09 , Processed in 0.144318 second(s), 19 queries .

Powered by Discuz! X3.4

? 2001-2017 Comsenz Inc.

返回顶部