[原创]Linux内核里的同步机制(1)—— 原子操作 原子操作 –单一的不可中断的操作。 首先看一个counter++的例子(Sch[94])。 在汇编层次,这一条语句会变成3个指令, 1.将counter值从内存中拷贝到CPU寄存器R0。 2.寄存器R0中的值加1。 3.将寄存器的值拷回到内存。 如果此时有两个CPU同时执行counter++,那么假设counter初始值为0,两次加1所得出来的结果就不是2,而是1,Bug由此而生。 这是一个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"); } 这里出现了几个问题,首先,在实现上没有区分UP和SMP。其次,也没有关中断及加总线锁的动作。那么这个函数如何保证原子性呢?上面有段注释很有价值。说是采用了loadexclusive和storeexclusive确保其原子性。读一下汇编发现最后一行的意思是当strex的返回值不为0时(%1,即tmp),会跳转到1重新执行一遍。所以最后一行注释说“Wemay loop to ensure that the update happens.”。那么strex又是什么? 查了一下ARM用户手册[AARM],终于在A2.9找到了上面所有问题的答案。 ldrex和和strex是AMRV6引入的新的同步机制,取代了过去的SWP和SWPB指令。ldrex就是Load-Exclusive的缩写,而strex就是Store-Exclusive的缩写。这两个指令与addressmonitor协同工作,为内存的访问提供了一个状态机。对于SMP和UP来说,这种机制稍有不同。简单地讲,对于非共享内存的情况(UP),只需要维护一个monitor就可以了。而对于共享内存的情况(SMP),需要为每一个CPU维护一个monitor,状态机就复杂一些。但是这些区别在指令的层次上是体现不出来的。所以,使用了ldrex和strex,就不需要为UP和SMP单独实现一套原子操作。 ARM到底是如何实现这种新的同步机制的?道理上很简单。简单地说,指令ldrex会为执行处理器做一个标记(tag),说当前对该物理地址已经有一个CPU访问了,但是还没有访问完毕。当strex指令执行时,就会检查是否存在这个标记。如果存在,那么将完成这次store的过程,并且返回0,然后清除该标记。如果没有这个标记,不会完成store,返回1。这样就能够在不关闭中断,没有执行任何buslock的情况下,保证操作的原子性。详细过程请参阅ARM用户手册[AARM]。 根据Linux内核里面atomic_add的实现,分析一个UP上的并发情景。(SMP上会复杂一点,但是大体意思相同) 上面只是一个理论过程,但是查资料的时候发现一个patch[LKM],说有一些互斥机制使用了LDREX/STREXEQ的组合,当使用这些机制的代码并发时,就可能出现LDREX和STREXEQ执行不成对的情况(STREXEQ是条件执行,未必每次都能得到执行),这样就无法保证原子性了。为了解决这个问题,就在exceptionhandler推出时,显式的调用一下clrex或者strex,这样就相当于在每次中断结束后,手动清理一下标记。也就是说,在原子操作时,只要发生了中断,标记都会被清除。 总之,使用这种Load-exclusive和Store-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, 2024-5-4 15:06 , Processed in 0.035379 second(s), 19 queries .
Powered by Discuz! X3.4
© 2001-2017 Comsenz Inc.