[发明专利]无锁先入先出

摘要

本发明的一个实施例阐述了允许多生产者和/或消费者使用“无锁”机制来访问先入先出子系统（FIFO）的技术。当两个或两个以上生产者尝试同时推入数据到FIFO上时，仅一个生产者成功。类似地，当两个或两个以上消费者尝试同时从FIFO取出数据时，仅一个消费者成功。然而，每个生产者和消费者被提供以其各自的访问是否成功的指示。可在接下来的时钟周期中重试不成功的访问，以便将同时的访问序列化。

主权项

一种访问无锁先入先出（FIFO）子系统的方法，所述方法包括：接收从所述无锁FIFO取出FIFO头节点的取出请求；从无锁FIFO数据结构读取FIFO头指针值；读取包括在所述FIFO头节点中并且识别在所述无锁FIFO中的第二FIFO节点的next值；实施原子的比较和交换操作以将所述FIFO头指针值与存储在所述无锁FIFO数据结构中的当前FIFO头指针值加以比较；以及如果对于所述原子的比较和交换操作所述FIFO头指针值等于所述当前FIFO头指针值，那么将所述next值与在所述无锁FIFO数据结构中的所述当前FIFO头指针值进行互换以更新所述FIFO头指针值，或者如果对于所述原子的比较和交换操作所述FIFO头指针值不等于所述当前FIFO头指针值，那么重复所述FIFO头指针值的读取、所述next值的读取以及所述原子的比较和交换操作的实施。