如果你用Linux perf tool的top命令做热点纠察时,你会发现,前10名嫌疑犯里面肯定有好几个都是锁!
在进行并行多处理时,不可 避免地会遇到锁的问题,这是不可避免的,因为这一直以来也许是保护共享数据的唯一方式,被保护的区域就是临界区。而我们知道,锁的开销是巨大的,因为它不 可避免地要么等待,要么让别人等待,然而这并不是开销的本质,开销的本质在于很多锁都采用了“原子操作”这么一个技术,如此一个原子操作会对总线或者 cache一致性造成很大的影响,比如要对一个变量进行原子加1,不要认为它很简单,其实背后会有很多不希望的操作,在某架构的处理器上,首先要LOCK 总线,这意味着LOCK不解除期间,其它处理器不能访存(起码是内存的某些区域),可能还要涉及到刷cache,或者触发cache一致性操作...这还 不算最猛的打击,在某些架构上,存在内存栅栏,它会刷掉CPU的流水线,刷掉cache,几乎所有的为优化而设计的方案全部失效,当然,这是代价,收益就 是你保护了临界区。
你要保护临界区,你要付出代价,这个代价如果用复杂的锁来支付的话,未免有点大。非要这样子吗?也许是你的数据结构设计地不好,也许是你的代码流设计地不 好,比如多个线程同时读共享数据,两个线程一个读一个写,能否采用环形缓冲区来减轻竞争呢?事实上很多诸如网卡,硬盘等共享外设驱动程序都是这么玩的,代 码只要保证读指针和写指针不相互超越即可,这样可以最小化锁的使用,当然这只是一个非常简单的例子。
设计好的数据结构和代码流程是一方面,但是这个层次不够抽象,更好的方式就是设计一种更加优化的锁。读写锁这种不对称的锁应对读者多写者少的情景是一种优 化的锁,它对读者的优待就是无需等待,只要没有写者就可以直接读,否则才等待。而对于写者,它需要等待所有读者的完成。这种读写的实现可以依赖于另一种叫 做自旋锁的机制实现,我的一个实现如下所示:
typedef struct { spinlock_t *spinlock; atomic_t readers; }rwlock_t; static inline void rdlock(rwlock_t *lock) { spinlock_t *lck = lock->spinlock; if (likely(!lock->readers++)) spin_lock(lck); } static inline void rdunlock(rwlock_t *lock) { spinlock_t *lck = lock->spinlock; if (likely(!--lock->readers)) spin_unlock(lck); } static inline void wrlock(rwlock_t *lock) { spin_lock(lock->spinlock); } static inline void wrunlock(rwlock_t *lock) { spin_unlock(lock->spinlock); }
很OK,不是吗?但是最好的方案就是彻底抛弃锁,彻底不用锁。
我曾经在设计我的转发表的时候,为了降低lock开销,我为每个CPU复制了一个局部的本地转发表,这些转发表是一致的,由路由表生成,心想这就可以避免 竞争,然而,这些转发表总要面临更新问题,如何更新它们??我最初采用的方式是采用IPI(处理器间中断),在处理函数中,停掉处理线程,然后更新数据, 最后开启线程,这样可以在处理期间避免lock。十分合理,不是吗?可是我想复杂了。
仔细看看读写锁的写锁,它鲁莽地进行了标准锁定操作,而读锁也是在第一个读者进来的时候采用了锁定动作。这些锁定操作导致的等待可以避免吗?看看我原始的 IPI方案,停掉线程是为了防止读者读到错误的数据,实际上是将主动将执行流让位给了写者,写者先来,然后再看看读写锁中的写者,发现有读者存在时,没有 主动地让位,而只是被动地等待,这种等待很无聊!
能否将我的方式和读写锁的方式结合呢?
怎么结合?按照刚刚的思路,无非就是为写者是被动等待还是抢先读者做一个决策!但是它还有一个别的选择,那就是先按照自己的流程写数据,不是写原始数据, 而是写原始数据的一份拷贝(伟大的写时拷贝),然后将这件事挂在一个未竟事务链表上直接走人,等待系统发现所有的读者都完成时用链表上的数据逐个覆盖原始 数据。这是个多么好的结合,这就是伟大的RCU锁。读者的代价就是简单地标示一下有人读即可,而写者也无需等待持锁,直接写副本,写完走人,后来的事就交 给系统了....