无锁环形缓冲区设计

版权所有 2009 Red Hat Inc.

作者:

Steven Rostedt <srostedt@redhat.com>

许可:

GNU 自由文档许可证,版本 1.2 (在 GPL v2 下双重许可)

审核人:

Mathieu Desnoyers, Huang Ying, Hidetoshi Seto, and Frederic Weisbecker.

编写于: 2.6.31

本文档中使用的术语

尾 (tail)
  • 环形缓冲区中发生新写入的位置。

头 (head)
  • 环形缓冲区中发生新读取的位置。

生产者 (producer)
  • 写入环形缓冲区的任务 (与写入者相同)

写入者 (writer)
  • 与生产者相同

消费者 (consumer)
  • 从缓冲区读取的任务 (与读取者相同)

读取者 (reader)
  • 与消费者相同。

reader_page
  • 环形缓冲区外部的页面,主要 (大部分情况下) 由读取者使用。

head_page
  • 指向读取者将要使用的下一个页面的指针

tail_page
  • 指向将要写入的下一个页面的指针

commit_page
  • 指向具有上次完成的非嵌套写入的页面的指针。

cmpxchg
  • 硬件辅助原子事务,执行以下操作

    A = B if previous A == C
    
    R = cmpxchg(A, C, B) is saying that we replace A with B if and only
        if current A is equal to C, and we put the old (current)
        A into R
    
    R gets the previous A regardless if A is updated with B or not.
    

    要查看更新是否成功,可以使用 R == C 的比较。

通用环形缓冲区

环形缓冲区可以在覆盖模式或生产者/消费者模式下使用。

生产者/消费者模式是指,如果生产者在消费者释放任何内容之前填满了缓冲区,则生产者将停止写入缓冲区。这将丢失最近的事件。

覆盖模式是指,如果生产者在消费者释放任何内容之前填满了缓冲区,则生产者将覆盖较旧的数据。这将丢失最旧的事件。

没有两个写入者可以同时写入 (在同一个 per-cpu 缓冲区上),但是一个写入者可以中断另一个写入者,但是它必须在先前的写入者可以继续之前完成写入。这对算法非常重要。写入者的行为就像一个“堆栈”。中断的工作方式强制执行这种行为

writer1 start
   <preempted> writer2 start
       <preempted> writer3 start
                   writer3 finishes
               writer2 finishes
writer1 finishes

这非常类似于一个写入者被中断抢占,并且中断也执行写入。

读取者可以在任何时候发生。但是没有两个读取者可以同时运行,也不能一个读取者抢占/中断另一个读取者。读取者不能抢占/中断写入者,但是它可以与写入者同时读取/使用缓冲区,但是读取者必须在另一个处理器上才能这样做。读取者可以在自己的处理器上读取,并且可以被写入者抢占。

写入者可以抢占读取者,但是读取者不能抢占写入者。但是读取者可以与写入者同时 (在另一个处理器上) 读取缓冲区。

环形缓冲区由一个链表链接在一起的页面列表组成。

在初始化时,为不属于环形缓冲区的读取者分配一个读取者页面。

head_page,tail_page 和 commit_page 都被初始化为指向同一个页面。

读取者页面被初始化为使其 next 指针指向 head 页面,并且其 previous 指针指向 head 页面之前的页面。

读取者有自己的页面可以使用。在启动时,会分配此页面,但不附加到列表。当读取者想要从缓冲区读取时,如果它的页面为空 (就像在启动时一样),它将把它的页面与 head_page 交换。旧的读取者页面将成为环形缓冲区的一部分,并且 head_page 将被删除。插入的页面 (旧的 reader_page) 之后的页面将成为新的 head 页面。

一旦将新页面提供给读取者,只要写入者离开了该页面,读取者就可以对它做任何想做的事情。

读取者页面如何交换的示例:注意,这不显示缓冲区中的 head 页面,它仅用于演示交换。

+------+
|reader|          RING BUFFER
|page  |
+------+
                +---+   +---+   +---+
                |   |-->|   |-->|   |
                |   |<--|   |<--|   |
                +---+   +---+   +---+
                 ^ |             ^ |
                 | +-------------+ |
                 +-----------------+


+------+
|reader|          RING BUFFER
|page  |-------------------+
+------+                   v
  |             +---+   +---+   +---+
  |             |   |-->|   |-->|   |
  |             |   |<--|   |<--|   |<-+
  |             +---+   +---+   +---+  |
  |              ^ |             ^ |   |
  |              | +-------------+ |   |
  |              +-----------------+   |
  +------------------------------------+

+------+
|reader|          RING BUFFER
|page  |-------------------+
+------+ <---------------+ v
  |  ^          +---+   +---+   +---+
  |  |          |   |-->|   |-->|   |
  |  |          |   |   |   |<--|   |<-+
  |  |          +---+   +---+   +---+  |
  |  |             |             ^ |   |
  |  |             +-------------+ |   |
  |  +-----------------------------+   |
  +------------------------------------+

+------+
|buffer|          RING BUFFER
|page  |-------------------+
+------+ <---------------+ v
  |  ^          +---+   +---+   +---+
  |  |          |   |   |   |-->|   |
  |  |  New     |   |   |   |<--|   |<-+
  |  | Reader   +---+   +---+   +---+  |
  |  |  page ----^                 |   |
  |  |                             |   |
  |  +-----------------------------+   |
  +------------------------------------+

如果环形缓冲区中的内容小于缓冲区页面中保存的内容,则交换的页面可能是 commit 页面和 tail 页面。

          reader page    commit page   tail page
              |              |             |
              v              |             |
             +---+           |             |
             |   |<----------+             |
             |   |<------------------------+
             |   |------+
             +---+      |
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

这种情况对于此算法仍然有效。当写入者离开页面时,它只是进入环形缓冲区,因为读取者页面仍然指向环形缓冲区中的下一个位置。

主要指针

读取者页面
  • 仅由读取者使用且不属于环形缓冲区的页面 (可能会交换进来)

头部页面
  • 环形缓冲区中的下一个页面,将与读取者页面交换。

尾部页面
  • 下一个写入将发生的页面。

提交页面
  • 上次完成写入的页面。

提交页面仅由写入者堆栈中最外层的写入者更新。抢占另一个写入者的写入者不会移动提交页面。

当数据写入环形缓冲区时,会在环形缓冲区中保留一个位置并传递回写入者。当写入者完成将数据写入该位置时,它会提交写入。

在此事务期间,可以在任何时候发生另一个写入 (或读取)。如果发生另一个写入,则必须在继续上一次写入之前完成。

写入保留

 Buffer page
+---------+
|written  |
+---------+  <--- given back to writer (current commit)
|reserved |
+---------+ <--- tail pointer
| empty   |
+---------+

写入提交

 Buffer page
+---------+
|written  |
+---------+
|written  |
+---------+  <--- next position for write (current commit)
| empty   |
+---------+

如果在第一次保留后发生写入

     Buffer page
    +---------+
    |written  |
    +---------+  <-- current commit
    |reserved |
    +---------+  <--- given back to second writer
    |reserved |
    +---------+ <--- tail pointer

After second writer commits::


     Buffer page
    +---------+
    |written  |
    +---------+  <--(last full commit)
    |reserved |
    +---------+
    |pending  |
    |commit   |
    +---------+ <--- tail pointer

When the first writer commits::

     Buffer page
    +---------+
    |written  |
    +---------+
    |written  |
    +---------+
    |written  |
    +---------+  <--(last full commit and tail pointer)

commit 指针指向上次在没有抢占另一个写入的情况下提交的写入位置。当提交抢占另一个写入的写入时,它仅成为挂起的提交,并且在所有写入都已提交之前不会成为完全提交。

commit 页面指向具有上次完全提交的页面。tail 页面指向具有上次写入的页面 (在提交之前)。

tail 页面始终等于或晚于 commit 页面。它可能会提前几个页面。如果 tail 页面赶上 commit 页面,则无论环形缓冲区的模式如何 (覆盖和生产者/消费者),都不能再进行写入。

页面的顺序是

head page
commit page
tail page

可能的场景

                             tail page
  head page         commit page  |
      |                 |        |
      v                 v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

有一种特殊情况,即头部页面在 commit 页面之后,并且可能在尾部页面之后。这是当 commit (和 tail) 页面已与读取者页面交换时。这是因为头部页面始终是环形缓冲区的一部分,但读取者页面不是。只要在环形缓冲区内提交的页面少于一个完整页面,并且读取者交换出一个页面,它将交换出 commit 页面。

          reader page    commit page   tail page
              |              |             |
              v              |             |
             +---+           |             |
             |   |<----------+             |
             |   |<------------------------+
             |   |------+
             +---+      |
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+
                        ^
                        |
                    head page

在这种情况下,当 tail 和 commit 移回环形缓冲区时,头部页面不会移动。

如果 commit 页面仍在页面上,则读取者无法将页面交换到环形缓冲区中。如果读取与上次提交 (真实提交,而不是挂起或保留) 相遇,则没有更多要读取的内容。缓冲区被认为是空的,直到另一个完全提交完成。

当 tail 与头部页面相遇时,如果缓冲区处于覆盖模式,则头部页面将向前推一个。如果缓冲区处于生产者/消费者模式,则写入将失败。

覆盖模式

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+
                        ^
                        |
                    head page


            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+
                                 ^
                                 |
                             head page


                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+
                                 ^
                                 |
                             head page

请注意,读取者页面仍将指向先前的头部页面。但是,当发生交换时,它将使用最新的头部页面。

使环形缓冲区无锁:

无锁算法背后的主要思想是将 head_page 指针的移动与页面与读取者的交换相结合。状态标志放置在指向页面的指针内。为此,每个页面必须在内存中按 4 字节对齐。这将允许地址的 2 个最低有效位用作标志,因为对于地址它们将始终为零。要获取地址,只需屏蔽标志

MASK = ~3

address & MASK

这两个位将保留两个标志

HEADER
  • 指向的页面是一个头部页面

UPDATE
  • 指向的页面正在被写入者更新,并且曾经或即将成为一个头部页面。

          reader page
              |
              v
            +---+
            |   |------+
            +---+      |
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-H->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

上面的指针“-H->”将设置 HEADER 标志。也就是说,下一个页面是要被读取者交换出的下一个页面。此指针表示下一个页面是头部页面。

当尾部页面与头部指针相遇时,它将使用 cmpxchg 将指针更改为 UPDATE 状态

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-H->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

“-U->”表示 UPDATE 状态下的指针。

对读取者的任何访问都需要采取某种锁来序列化读取者。但是写入者永远不会采取锁来写入环形缓冲区。这意味着我们只需要担心单个读取者,并且写入仅以“堆栈”形式抢占。

当读取者尝试将页面与环形缓冲区交换时,它也将使用 cmpxchg。如果指向头部页面的指针中的标志位没有设置 HEADER 标志,则比较将失败,并且读取者需要查找新的头部页面并重试。请注意,标志 UPDATE 和 HEADER 永远不会同时设置。

读取者按如下方式交换读取者页面

+------+
|reader|          RING BUFFER
|page  |
+------+
                +---+    +---+    +---+
                |   |--->|   |--->|   |
                |   |<---|   |<---|   |
                +---+    +---+    +---+
                 ^ |               ^ |
                 | +---------------+ |
                 +-----H-------------+

读取者将读取者页面的下一个指针设置为 HEADER 到头部页面之后的页面

+------+
|reader|          RING BUFFER
|page  |-------H-----------+
+------+                   v
  |             +---+    +---+    +---+
  |             |   |--->|   |--->|   |
  |             |   |<---|   |<---|   |<-+
  |             +---+    +---+    +---+  |
  |              ^ |               ^ |   |
  |              | +---------------+ |   |
  |              +-----H-------------+   |
  +--------------------------------------+

它对指向先前头部页面的指针执行 cmpxchg,以使其指向读取者页面。请注意,新指针没有设置 HEADER 标志。此操作原子地将头部页面向前移动

+------+
|reader|          RING BUFFER
|page  |-------H-----------+
+------+                   v
  |  ^          +---+   +---+   +---+
  |  |          |   |-->|   |-->|   |
  |  |          |   |<--|   |<--|   |<-+
  |  |          +---+   +---+   +---+  |
  |  |             |             ^ |   |
  |  |             +-------------+ |   |
  |  +-----------------------------+   |
  +------------------------------------+

在设置新的头部页面后,头部页面的先前指针会更新为读取者页面

+------+
|reader|          RING BUFFER
|page  |-------H-----------+
+------+ <---------------+ v
  |  ^          +---+   +---+   +---+
  |  |          |   |-->|   |-->|   |
  |  |          |   |   |   |<--|   |<-+
  |  |          +---+   +---+   +---+  |
  |  |             |             ^ |   |
  |  |             +-------------+ |   |
  |  +-----------------------------+   |
  +------------------------------------+

+------+
|buffer|          RING BUFFER
|page  |-------H-----------+  <--- New head page
+------+ <---------------+ v
  |  ^          +---+   +---+   +---+
  |  |          |   |   |   |-->|   |
  |  |  New     |   |   |   |<--|   |<-+
  |  | Reader   +---+   +---+   +---+  |
  |  |  page ----^                 |   |
  |  |                             |   |
  |  +-----------------------------+   |
  +------------------------------------+

另一个重点:读取者页面通过其先前指针指向的页面 (现在指向新的头部页面的页面) 永远不会指向读取者页面。那是因为读取者页面不属于环形缓冲区。通过 next 指针遍历环形缓冲区将始终停留在环形缓冲区中。通过 prev 指针遍历环形缓冲区可能不会。

请注意,确定读取者页面的方法很简单,只需检查页面的先前指针即可。如果先前页面的 next 指针没有指向原始页面,则原始页面是一个读取者页面

 +--------+
 | reader |  next   +----+
 |  page  |-------->|    |<====== (buffer page)
 +--------+         +----+
     |                | ^
     |                v | next
prev |              +----+
     +------------->|    |
                    +----+

头部页面向前移动的方式

当尾部页面与头部页面相遇,并且缓冲区处于覆盖模式并且发生更多写入时,必须在写入者可以移动尾部页面之前将头部页面向前移动。执行此操作的方式是写入者执行 cmpxchg 以将指向头部页面的指针从 HEADER 标志转换为设置 UPDATE 标志。完成此操作后,读取者将无法从缓冲区交换头部页面,也无法移动头部页面,直到写入者完成移动。

这消除了读取者可能对写入者造成的任何竞争。读取者必须旋转,这就是为什么读取者不能抢占写入者

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-H->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

以下页面将成为新的头部页面

           tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

在设置新的头部页面后,我们可以将旧的头部页面指针设置回 NORMAL

           tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

在头部页面移动后,尾部页面现在可以向前移动

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

以上是简单的更新。现在来看更复杂的场景。

如前所述,如果足够的写入抢占了第一个写入,则尾部页面可能会一直绕缓冲区转,并与 commit 页面相遇。此时,我们必须开始丢弃写入 (通常会向用户发出某种警告)。但是,如果 commit 仍然在读取者页面上会发生什么?commit 页面不属于环形缓冲区。尾部页面必须考虑到这一点

          reader page    commit page
              |              |
              v              |
             +---+           |
             |   |<----------+
             |   |
             |   |------+
             +---+      |
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-H->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+
               ^
               |
           tail page

如果尾部页面只是简单地将头部页面向前推,则离开读取者页面时的 commit 将不会指向正确的页面。

对此的解决方案是在推动头部页面之前测试 commit 页面是否在读取者页面上。如果是,则可以假定尾部页面已包装缓冲区,并且我们必须丢弃新的写入。

这不是竞争条件,因为 commit 页面只能由最外层的写入者 (被抢占的写入者) 移动。这意味着当写入者移动尾部页面时,commit 不会移动。如果读取者页面也用作 commit 页面,则读取者无法交换读取者页面。读取者可以简单地检查 commit 是否已离开读取者页面。一旦 commit 页面离开读取者页面,除非读取者与也作为 commit 页面的缓冲区页面再次进行交换,否则它将永远不会回到它上面。

嵌套写入

在向前推动尾部页面时,如果头部页面是下一个页面,我们必须首先向前推动头部页面。如果头部页面不是下一个页面,则只需使用 cmpxchg 更新尾部页面。

只有写入者才能移动尾部页面。必须原子地完成此操作以防止嵌套写入

temp_page = tail_page
next_page = temp_page->next
cmpxchg(tail_page, temp_page, next_page)

如果尾部页面仍指向预期页面,则以上将更新尾部页面。如果这失败了,则嵌套写入将其向前推动,当前写入不需要推动它

           temp page
               |
               v
            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

嵌套写入进入并将尾部页面向前移动

                    tail page (moved by nested writer)
            temp page   |
               |        |
               v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

以上将使 cmpxchg 失败,但是由于尾部页面已经向前移动,因此写入者将再次尝试在新尾部页面上保留存储。

但是移动头部页面有点复杂

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-H->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

写入将头部页面指针转换为 UPDATE

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

但是,如果嵌套写入者在此处抢占,它将看到下一个页面是一个头部页面,但它也是嵌套的。它将检测到它是嵌套的,并将保存该信息。检测是它看到 UPDATE 标志而不是 HEADER 或 NORMAL 指针的事实。

嵌套写入者将设置新的头部页面指针

           tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

但它不会将更新重置为 normal。只有将指针从 HEAD 转换为 UPDATE 的写入者才会将其转换回 NORMAL

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

在嵌套写入者完成后,最外层的写入者会将 UPDATE 指针转换为 NORMAL

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

如果几个嵌套写入进入并将尾部页面向前移动几个页面,则它会变得更加复杂

(first writer)

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-H->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

写入将头部页面指针转换为 UPDATE

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

下一个写入者进入,并看到更新并设置新的头部页面

(second writer)

           tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

嵌套写入者将尾部页面向前移动。但不会将旧的更新页面设置为 NORMAL,因为它不是最外层的写入者

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

另一个写入者抢占并看到尾部页面之后的页面是一个头部页面。它将其从 HEAD 更改为 UPDATE

(third writer)

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-U->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

写入者将向前移动头部页面

(third writer)

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-U->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

但是现在第三个写入者确实将 HEAD 标志更改为 UPDATE,它将将其转换为 normal

(third writer)

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

然后它将移动尾部页面,然后返回到第二个写入者

(second writer)

                             tail page
                                 |
                                 v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

第二个写入者将无法移动尾部页面,因为它已经被移动,因此它将再次尝试并将其数据添加到新的尾部页面。它将返回到第一个写入者

(first writer)

                             tail page
                                 |
                                 v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

第一个写入者无法原子地知道尾部页面是否在更新 HEAD 页面时移动。然后,它将更新头部页面,以它认为的新头部页面

(first writer)

                             tail page
                                 |
                                 v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

由于 cmpxchg 返回指针的旧值,因此第一个写入者将看到它成功地将指针从 NORMAL 更新为 HEAD。但是正如我们所看到的,这还不够好。它还必须检查尾部页面是否在它过去的位置或在下一个页面上

(first writer)

               A        B    tail page
               |        |        |
               v        v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

如果 tail 页面 != A 并且 tail 页面 != B,则它必须将指针重置回 NORMAL。它只需要担心嵌套写入者这一事实意味着它只需要在设置 HEAD 页面后检查此项

(first writer)

               A        B    tail page
               |        |        |
               v        v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

现在,写入者可以更新头部页面。这也是头部页面必须保持 UPDATE 状态并且只能由最外层的写入者重置的原因。这可以防止读取者看到不正确的头部页面

(first writer)

               A        B    tail page
               |        |        |
               v        v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+