在 2.6 内核中，开发者还引入了一种新的无锁机制 -RCU(Read-Copy-Update)，允许多个读者和写者并发执行。RCU 技术的核心是写操作分为写和更新两步，允许读操作在任何时候无阻碍的运行，换句话说，就是通过延迟写来提高同步性能。RCU 主要应用于 WRRM 场景，但它对可保护的数据结构做了一些限定：RCU 只保护被动态分配并通过指针引用的数据结构，同时读写控制路径不能有睡眠。以下数组动态增长代码摘自 2.4.34 内核：

清单 7. 2.4.34 RCU 实现代码

其中 ipc_lock 是读者，grow_ary 是写者，不论是读或者写，都需要加 spin lock 对被保护的数据结构进行访问。改变数组大小是小概率事件，而读取是大概率事件，同时被保护的数据结构是指针，满足 RCU 运用场景。以下代码摘自 2.6.10 内核：

清单 8. 2.6.10 RCU 实现代码

#define rcu_read_lock() preempt_disable()

#define rcu_read_unlock() preempt_enable()

#define rcu_assign_pointer(p, v) ({ \

smp_wmb(); \

(p) = (v); \

})

struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id)

{

……

rcu_read_lock();

entries = rcu_dereference(ids->entries);

if(lid >= entries->size) {

rcu_read_unlock();

return NULL;

}

out = entries->p[lid];

if(out == NULL) {

rcu_read_unlock();

return NULL;

}

……

return out;

}

static int grow_ary(struct ipc_ids* ids, int newsize)

{

struct ipc_id_ary* new;

struct ipc_id_ary* old;

……

new = ipc_rcu_alloc(sizeof(struct kern_ipc_perm *)*newsize +

sizeof(struct ipc_id_ary));

if(new == NULL)

return size;

new->size = newsize;

memcpy(new->p, ids->entries->p, sizeof(struct kern_ipc_perm *)*size

+sizeof(struct ipc_id_ary));

for(i=size;i<newsize;i++) {

new->p[i] = NULL;

}

old = ids->entries;

rcu_assign_pointer(ids->entries, new);

ipc_rcu_putref(old);

return newsize;

}

纵观整个流程，写者除内核屏障外，几乎没有一把锁。当写者需要更新数据结构时，首先复制该数据结构，申请new 内存，然后对副本进行修改，调用 memcpy 将原数组的内容拷贝到 new 中，同时对扩大的那部分赋新值，修改完毕后，写者调用 rcu_assign_pointer 修改相关数据结构的指针，使之指向被修改后的新副本，整个写操作一气呵成，其中修改指针值的操作属于原子操作。在数据结构被写者修改后，需要调用内存屏障smp_wmb，让其他 CPU 知晓已更新的指针值，否则会导致 SMP 环境下的 bug。当所有潜在的读者都执行完成后，调用 call_rcu 释放旧副本。同 Spin lock 一样，RCU 同步技术主要适用于 SMP 环境。

内核无锁第四层级 — 免锁

环形缓冲区是生产者和消费者模型中常用的数据结构。生产者将数据放入数组的尾端，而消费者从数组的另一端移走数据，当达到数组的尾部时，生产者绕回到数组的头部。

如果只有一个生产者和一个消费者，那么就可以做到免锁访问环形缓冲区（Ring Buffer）。写入索引只允许生产者访问并修改，只要写入者在更新索引之前将新的值保存到缓冲区中，则读者将始终看到一致的数据结构。同理，读取索引也只允许消费者访问并修改。

图 2. 环形缓冲区实现原理图

如图所示，当读者和写者指针相等时，表明缓冲区是空的，而只要写入指针在读取指针后面时，表明缓冲区已满。

清单 9. 2.6.10 环形缓冲区实现代码

unsigned int __kfifo_put(struct kfifo *fifo,

unsigned char *buffer, unsigned int len)

{

unsigned int l;

len = min(len, fifo->size - fifo->in + fifo->out);

l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));

memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);

memcpy(fifo->buffer, buffer + l, len - l);

fifo->in += len;

return len;

}

unsigned int __kfifo_get(struct kfifo *fifo,

unsigned char *buffer, unsigned int len)

{

unsigned int l;

len = min(len, fifo->in - fifo->out);

l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));

memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);

memcpy(buffer + l, fifo->buffer, len - l);

fifo->out += len;

return len;

}

以上代码摘自 2.6.10 内核，通过代码的注释（斜体部分）可以看出，当只有一个消费者和一个生产者时，可以不用添加任何额外的锁，就能达到对共享数据的访问。

回页首

总结

通过对比 2.4 和 2.6 内核代码，不得不佩服内核开发者的智慧，为了提高内核性能，一直不断的进行各种优化，并将业界最新的 lock-free 理念运用到内核中。

在实际开发过程中，进行无锁设计时，首先进行场景分析，因为每种无锁方案都有特定的应用场景，接着根据场景分析进行数据结构的初步设计，然后根据先前的分析结果进行并发模型建模，最后在调整数据结构的设计，以便达到最优。

参考资料

Andrei Alexandrescu. 《 Lock-Free Data Structures--- Keeping threads moving while avoiding deadlock》，《 Dr. Dobb's Journal 》， October 01, 2004。
《 Non-blocking synchronization 》， http://en.wikipedia.org/wiki/Non-blocking_synchronization
Shameem Akhter and Jason Roberts. 李宝峰，富弘毅，李韬译 . 《多核程序设计技术》，电子工业出版社，2007。
Rebert Love，《 Linux Kernel Development，2rd Edition 》，机械工业出版社，2006。
Daniel P. Bovet，Marco Cesati，《 Understanding the Linux Kernel，3rd Edition 》，东南大学出版社，2006。
Jonatban Corbet 等，魏永明等译，《 Linux 设备驱动程序》，中国电力出版社，2006。
Gordon Fischer 等，《 The Linux Kernel Prime 》，机械工业出版社，2006。
在 developerWorks Linux 专区寻找为 Linux 开发人员（包括 Linux 新手入门）准备的更多参考资料，查阅我们最受欢迎的文章和教程。
在 developerWorks 上查阅所有 Linux 技巧和 Linux 教程。