檢視原始碼 執行緒進度
問題
了解執行緒何時完成對資料結構的存取
當多個執行緒存取相同的資料結構時，您通常需要知道所有執行緒何時完成其存取。例如，為了知道何時可以安全地釋放資料結構。實現此目的的一種簡單方法是對資料結構的所有存取進行參考計數。此方法的問題在於，參考計數器所在的快取行需要在所有相關處理器之間進行傳遞。如果頻繁存取參考計數器，則這種傳遞可能會變得非常昂貴，並且會難以擴展。也就是說，我們希望使用參考計數以外的其他方法來追蹤執行緒。
了解記憶體的修改是否被一致地觀察到
不同的硬體架構有不同的記憶體模型。某些架構允許非常激進地重新排序記憶體存取，而其他架構只會重新排序少數特定情況。然而，所有現代硬體都有一個共同點，即會發生某種類型的重新排序。當使用鎖來保護多個執行緒進行的所有記憶體存取時，此類重新排序將不可見。鎖定原語將確保記憶體存取將被排序。但是，當使用無鎖演算法時，必須考慮到硬體所做的此類重新排序。
硬體記憶體屏障或記憶體柵欄是可用於強制執行記憶體存取順序的指令。不同的硬體架構提供不同的記憶體屏障。無鎖演算法需要使用記憶體屏障，以確保記憶體存取不會以導致演算法崩潰的方式重新排序。記憶體屏障也是昂貴的指令，因此您通常希望盡量減少使用這些指令。
用於解決這些問題的功能
Erlang VM 中的「執行緒進度」功能用於解決這些問題。「執行緒進度」這個名稱的選擇是因為我們希望使用它來確定一組執行緒中的所有執行緒何時已取得進展，以便它們的所有兩個特定事件都已發生。
我們感興趣的執行緒組稱為受管理執行緒。受管理執行緒是我們唯一能取得任何資訊的執行緒。這些執行緒必須頻繁地報告進度。系統中並非所有執行緒都能頻繁地報告進度。此類執行緒不能允許在受管理執行緒組中，並稱為非受管理執行緒。非受管理執行緒的一個例子是非同步執行緒池中的執行緒。非同步執行緒可能會被阻塞很長時間，因此無法頻繁地報告進度。目前，只有排程器執行緒和其他少數幾個執行緒是受管理執行緒。
執行緒進度事件
系統中的任何執行緒都可以使用執行緒進度功能來確定以下事件何時在所有受管理執行緒中至少發生一次
- 執行緒已從其他程式碼返回到執行緒進度功能中的已知狀態，該狀態獨立於任何其他程式碼。
- 執行緒已執行完整的記憶體屏障。
當然，這些事件需要按順序發生到其他記憶體操作。確定此操作的過程從啟動執行緒進度操作開始。啟動執行緒進度操作的執行緒在此之後輪詢操作的完成情況。這兩個事件必須在啟動執行緒進度操作之後至少發生一次，並且在每個受管理執行緒中，在操作完成之前至少發生一次。這是透過記憶體中的通訊來排序的，這使得可以在執行緒進度操作完成後得出關於記憶體狀態的結論。讓我們將從啟動到完成所取得的進度稱為「執行緒進度」。
假設執行緒進度功能是高效的，則許多演算法可以簡化並比使用首先想到的方法更有效。以下是一些範例。
透過能夠確定上述第一個事件何時發生，我們可以輕鬆知道所有受管理執行緒何時完成對資料結構的存取。可以透過以下方式確定這一點。我們使用資料結構 D 實作某個功能 F。在存取 D 之前，總是會查閱對 D 的參考，並且在我們離開實作 F 的程式碼之前，總是會捨棄對 D 的參考。如果我們移除查閱 D 的可能性，然後等到第一個事件在所有受管理執行緒中發生，則沒有受管理執行緒可以擁有對資料結構 D 的任何參考。例如，這可以透過使用參考計數來實現，但在這種情況下，包含參考計數器的快取行會在每次存取時在存取 D 的所有處理器之間來回傳遞。
透過能夠確定第二個事件何時發生，可以很容易地對記憶體進行複雜的修改，而無需訴諸鎖定，而這些修改需要由其他執行緒一致地看到。透過進行修改，然後發出完整的記憶體屏障，然後等到第二個事件在所有受管理執行緒中發生，然後發佈修改，我們知道讀取此記憶體的所有受管理執行緒都會獲得一致的修改檢視。讀取此記憶體的受管理執行緒完全不必發出任何額外的記憶體屏障。
執行緒進度功能的實作
實作上的要求
為了能夠確定所有受管理執行緒何時達到我們感興趣的狀態，我們需要在所有相關執行緒之間進行通訊。當然，我們希望將此通訊最小化。
我們還希望執行緒能夠相對快速地確定執行緒進度何時已取得。也就是說，我們需要在通訊開銷和完成操作的時間之間取得一些平衡。
API
我將在此僅呈現 API 中最重要的功能。
-
ErtsThrPrgrVal erts_thr_progress_later(void)- 操作的啟動。傳回的執行緒進度值可用於測試操作是否完成。 -
int erts_thr_progress_has_reached(ErtsThrPrgrVal val)- 當我們達到作為引數傳遞的執行緒進度值時，傳回非零值。也就是說，當傳回非零值時，操作已完成。
當執行緒呼叫 my_val = erts_thr_progress_later() 並等待 erts_thr_progress_has_reached(my_val) 傳回非零值時，它知道已取得執行緒進度。
在等待 erts_thr_progress_has_reached() 傳回非零值的同時，我們通常不希望阻塞等待，而是希望繼續處理其他事項。如果我們沒有其他事情可處理，我們通常確實希望阻塞等待，直到我們達到我們正在等待的執行緒進度值。為了能夠做到這一點，我們提供了在達到特定執行緒進度值時喚醒執行緒的功能
-
void erts_thr_progress_wakeup(ErtsSchedulerData *esdp, ErtsThrPrgrVal val)- 要求喚醒。當執行緒進度達到 val 時，將喚醒呼叫執行緒。
受管理執行緒需要透過呼叫以下函數來頻繁地更新其執行緒進度
-
int erts_thr_progress_update(ErtsSchedulerData *esdp)- 更新執行緒進度。如果傳回非零值，則必須在不持有任何鎖定的情況下呼叫erts_thr_progress_leader_update()。 -
int erts_thr_progress_leader_update(ErtsSchedulerData *esdp)- 主要執行緒更新執行緒進度。
非受管理執行緒可能會延遲執行緒進度的進展
-
ErtsThrPrgrDelayHandle erts_thr_progress_unmanaged_delay(void)- 延遲執行緒進度。 -
void erts_thr_progress_unmanaged_continue(ErtsThrPrgrDelayHandle handle)- 讓執行緒進度繼續。
當執行緒進度已取得時，排程器執行緒可以排程由排程器本身執行的操作
void erts_schedule_thr_prgr_later_op(void (*funcp)(void *), void *argp, ErtsThrPrgrLaterOp *memp)- 排程對funcp的呼叫。自對erts_schedule_thr_prgr_later_op()的呼叫以來，當執行緒進度已取得時，將執行呼叫(*funcp)(argp)。
實作
為了確定事件何時發生，我們使用全域計數器，當所有受管理執行緒呼叫 erts_thr_progress_update()（或 erts_thr_progress_leader_update()）時，該計數器會遞增。這可以天真地使用「執行緒已確認」計數器來實作。但是，這會導致通訊激增，其中所有相關的處理器都需要在每次更新時彼此通訊。
每個執行緒都在自己的快取行中確認它接受全域計數器的遞增，而不是在全域位置確認。這些確認快取行按順序位於陣列中，並且每個確認快取行將僅由一個執行緒寫入。受管理執行緒之一始終具有主要執行緒的職責。此職責可能會在執行緒之間跳轉，但只要系統中有一些活動，其中一個執行緒將始終具有主要執行緒的職責。具有主要執行緒職責的執行緒將呼叫 erts_thr_progress_leader_update()，這將檢查所有其他執行緒是否已確認全域計數器的遞增，然後再執行全域計數器的遞增。主要執行緒是唯一讀取確認快取行的執行緒。
透過這種方式，我們將得到一種資訊傳遞模式，資訊從領導執行緒傳遞到所有其他受管理執行緒，然後再從其他執行緒傳遞回領導執行緒。這是因為只有領導執行緒會寫入全域計數器，而所有其他執行緒只會讀取它，而且每個確認快取行都只會由一個特定的執行緒寫入，並且只會由領導執行緒讀取。當每個受管理執行緒分佈在不同的處理器上時，處理器之間的通訊將反映執行緒之間這種通訊模式。
erts_thr_progress_later() 傳回的值等於此執行緒所確認的最新值加二。全域值可能是最新確認的值，也可能是最新確認的值減一。為了確保所有其他受管理執行緒實際上會在我們達到 erts_thr_progress_later() 傳回的值之前至少呼叫一次 erts_thr_progress_update()，單純全域計數器加一是不夠的。這是因為在我們呼叫 erts_thr_progress_later() 時，所有其他執行緒可能已經確認了當前全域值加一。但是，它們保證在這個時候還沒有確認全域值加二。
上述實作或多或少地將我們遞增全域計數器之前所需的通訊量降到最低。然而，由於執行緒進度功能而在系統中產生的通訊量，也取決於受管理執行緒呼叫 erts_thr_progress_update() 的頻率。現在，每個排程器執行緒大約在每次 Erlang 程序排程出去時都會呼叫 erts_thr_progress_update()。進一步減少因執行緒進度功能而產生通訊量的一種方法是，僅在每次 Erlang 程序排程出去的第二、三次呼叫 erts_thr_progress_update()，甚至更低的頻率。然而，透過降低執行緒進度的更新頻率，所有依賴執行緒進度功能的操作也會需要更長的時間。
非管理執行緒延遲執行緒進度
為了實作非管理執行緒對執行緒進度的延遲，我們使用兩個參考計數器。一個是 current，另一個是 waiting。當非管理執行緒想要延遲執行緒進度時，它會遞增 current 並取得遞增參考計數器的回傳處理序。之後當它想要啟用執行緒進度的繼續時，它會使用該處理序來遞減先前遞增的參考計數器。
當領導執行緒即將遞增全域執行緒進度計數器時，它會先驗證 waiting 計數器是否為零。如果不是零，則不允許領導者遞增全域計數器，並且需要等待才能執行此操作。當它為零時，它會在增加全域計數器之前交換 waiting 和 current 計數器。從現在開始，新的 waiting 計數器將會遞減，以便它最終將達到零，使其有可能在下次遞增全域計數器。如果我們只使用一個參考計數器，不同非管理執行緒可能會使其永遠保持在零以上。
當非管理執行緒遞增 current 計數器時，它不會阻止下次遞增全域計數器，而是阻止之後的遞增。這就足夠了，因為全域計數器需要遞增兩次才能完成執行緒進度。也不希望阻止第一次遞增，因為在全域計數器被延遲遞增之前，撤回延遲的可能性會增加。也就是說，該操作將導致盡可能少的干擾。
然而，非管理執行緒延遲執行緒進度的此功能最好盡可能少用，因為大量使用會導致參考計數器快取行的爭用。但是，此功能在通常僅在受管理執行緒中執行的程式碼中非常有用，但在某些不常見的情況下可能會在其他執行緒中執行。
額外負擔
無論功能的使用次數如何，使用相同數量的排程器，執行緒進度功能所造成的額外負擔或多或少是固定的。現在已經有很多功能使用它，我們計劃更多地使用它。當重寫 ERTS 內部功能的舊實作以使用執行緒進度功能時，這意味著刪除舊實作中的通訊。否則，重寫舊實作以使用執行緒進度功能就沒有意義了。由於執行緒進度額外負擔或多或少是固定的，因此重寫將會減少系統中的總體通訊量。
一個範例
ETS 表格的主要結構最初是使用參考計數來管理的。很久以前我們就已經取代了這種策略，因為參考計數器在每次存取表格時都會引起爭用。使用的解決方案是在每個排程器上排程「確認刪除」作業，以便知道何時可以安全地解除分配已移除表格的表格結構。這些確認刪除作業需要分配。也就是說，我們必須分配和解除分配與排程器數量一樣多的區塊，才能解除分配一個區塊。這當然是一個相當昂貴的操作，但我們只需要在移除表格時執行一次。更重要的是擺脫表格上每次操作都存在的參考計數器的爭用。
當引入執行緒進度功能時，我們可以移除實作「確認刪除」作業的程式碼，然後僅排程稍後的執行緒進度操作來解除分配該結構。除了大大簡化程式碼之外，在四核心機器上執行 mnesia tpcb 基準測試時，每秒處理的交易次數增加了 10% 以上。