無鎖環形緩衝區設計¶
版權所有 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->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+