Lock-Free Algorithms

Sometimes, you can recast your algorithms to avoid the need for locking altogether. A number of reader/writer situations—if there is only one writer—can often work in this manner. If the writer takes care that the view of the data structure, as seen by the reader, is always consistent, it may be possible to create a lock-free data structure.

 

       有时，你可以重新指定你的法则来避免完整的锁定操作。对于许多读写情况——如果只有一个写入者——就常常以该方式工作。如果写入者获得的数据结构与读取者看到的一样，通常是一致的，它也许就会创建一个免锁的数据结构。

 

 

A data structure that can often be useful for lockless producer/consumer tasks is the circular buffer . This algorithm involves a producer placing data into one end of an array, while the consumer removes data from the other. When the end of the array is reached, the producer wraps back around to the beginning. So a circular buffer requires an array and two index values to track where the next new value goes and which value should be removed from the buffer next.

 

       一个常被用于无锁的生产者/消费者任务的数据结构是一个循环缓冲区。其操作法则是一个生产者将数据放进一个数组的末尾，而消费者则从另一端移除数据。当到达数组末尾时，生产者将会绕到开始位置。所以一个循环区域需要一个数组和两个索引值来确定下一个值的位置以及应该从缓冲区中移除哪个值。

 

 

When carefully implemented, a circular buffer requires no locking in the absence of multiple producers or consumers. The producer is the only thread that is allowed to modify the write index and the array location it points to. As long as the writer stores a new value into the buffer before updating the write index, the reader will always see a consistent view. The reader, in turn, is the only thread that can access the read index and the value it points to. With a bit of care to ensure that the two pointers do not overrun each other, the producer and the consumer can access the buffer concurrently with no race conditions.

 

       当小心执行时，一个循环缓冲区在缺乏多个生产者或消费者时不需要锁定。生产者是一个唯一的，能够修改写入索引值及其指向的数组位置的线程。只要写入者在更新写入索引之前向缓冲区中存入了一个新值，读取者将会始终看到一致的数组内容。读取者是线程则轮流访问读取索引值及其指向的数组值。这里要注意的一点就是这两个指针不会相互溢出，生产者和消费者能够并发访问目标缓冲区而不会引起竞态条件。

 

 

Figure 5-1 shows circular buffer in several states of fill. This buffer has been defined such that an empty condition is indicated by the read and write pointers being equal, while a full condition happens whenever the write pointer is immediately behind the read pointer (being careful to account for a wrap!). When carefully programmed, this buffer can be used without locks.

 

   图5-1展示了循环缓冲区的许多填充情况。该缓冲区被定义为空时读写指针的值相等，只要一个完整的条件发生，写入指针就会立即跳到读取指针的后面(小心计算偏移！)。当你谨慎地编写程序时，该缓冲区完全可以脱离锁使用。

Circular buffers show up reasonably often in device drivers. Networking adaptors, in particular, often use circular buffers to exchange data (packets) with the processor. Note that, as of 2.6.10, there is a generic circular buffer implementation available in the kernel; see for information on how to use it.

 

       循环缓冲区经常用于设备驱动程序中。特别是网络适配器，经常使用循环缓冲区来与处理器交换数据(包)。注意，从2.6.10版本开始，内核提供了一个通用的循环缓冲区函数；它的使用方法可以查看文件。