檢視原始碼 延遲釋放
問題
在多執行緒環境中處理記憶體配置的一種簡單方法，是使用全域鎖保護記憶體配置器，執行記憶體配置或釋放的執行緒必須在整個操作過程中持有該鎖。當然，這種解決方案由於鎖的嚴重競爭，擴展性非常差。此方案的一個改進解決方案是使用多個執行緒特定的配置器實例。也就是說，每個執行緒在其自己的配置器實例中進行配置，該實例由鎖保護。在一般情況下，記憶體參考需要在執行緒之間傳遞。在需要釋放來自另一個執行緒配置器實例的記憶體的執行緒情況下，可能會發生鎖衝突。在像 Erlang VM 這樣記憶體配置/釋放頻繁且記憶體參考也在執行緒之間傳遞的系統中，此解決方案也會因鎖競爭而擴展性不佳。
用於解決此問題的功能
為了減少由於鎖定配置器實例而引起的競爭，我們引入了與每個排程器執行緒綁定的完全無鎖實例，以及一個用於其他執行緒的額外鎖定實例。系統中的排程器執行緒預期會執行大部分工作。可能仍然需要其他執行緒，但不應執行任何主要和/或時間關鍵的工作。鎖定配置器實例上出現的有限競爭或多或少可以忽略不計。
由於我們仍然需要在排程器執行緒之間傳遞記憶體參考，我們需要某種方式來管理它。屬於一個排程器執行緒的配置器實例只允許由該排程器執行緒操作。當其他執行緒需要釋放來自外部配置器實例的記憶體時，它們只會將記憶體區塊傳遞給一個「訊息箱」，其中包含附加到原始配置器實例的釋放工作。當排程器執行緒偵測到此類釋放工作時，它會執行實際的釋放。
「訊息箱」是使用透過要釋放的記憶體區塊的無鎖單向連結列表實作的。此列表中元素的順序並不重要。新的空閒區塊將被插入到列表末尾附近的某個位置。要求新區塊必須插入到末尾，會在多個執行緒同時插入大量記憶體區塊時，導致不必要的競爭。
引用此單向連結列表的資料結構涵蓋兩個快取行。一個快取行包含有關列表頭部的資訊，另一個快取行包含有關列表尾部的資訊。這是為了減少此資料結構的快取行乒乓效應。列表頭部僅由擁有配置器實例的執行緒操作，而尾部則由其他插入釋放工作的執行緒操作。
尾部
在資料結構的尾部，我們找到一個指向列表最後一個元素的指標，或者至少是指向列表末尾附近的某個指標。在沒有競爭的情況下，它將指向列表的末尾，但是當同時執行插入操作時，它將指向列表末尾附近的某個位置。
插入元素時，會嘗試將指向新元素的指標寫入最後一個指標所指向的元素的下一個指標。這是使用原子比較和交換完成的，它期望下一個指標為 NULL。如果成功，執行此操作的執行緒會將最後一個指標移動到指向新插入的元素。
如果上述原子比較和交換失敗，則最後一個指標並未指向最後一個元素。在這種情況下，我們需要將新元素插入到最後一個指標所指向的元素和實際最後一個元素之間的某個位置。如果我們這樣做，當執行緒停止添加新元素時，最後一個指標最終會指向最後一個元素。當嘗試在末尾附近插入但未能成功時，插入執行緒有時會移動到下一個元素，有時會再次嘗試使用相同的元素。這是為了在發生嚴重競爭時分散插入的元素。也就是說，我們嘗試將記憶體的修改分散到不同的位置，而不是讓所有執行緒繼續嘗試修改記憶體中的相同位置。
頭部
頭部包含指向列表開頭 (head.first) 的指標，以及指向其他執行緒可能引用的第一個區塊 (head.unref_end) 的指標。這些指標之間的區塊僅由資料結構的頭部引用，該頭部僅由擁有配置器實例的執行緒使用。當這兩個指標不相等時，擁有配置器實例的執行緒會逐個釋放區塊，直到 head.first 到達 head.unref_end。
當然，我們需要定期將 head.unref_end 移近末尾，以便能夠繼續釋放記憶體區塊。由於在連結列表中插入新元素的所有執行緒都將使用最後一個指標進入列表，因此我們可以使用此知識。如果我們呼叫 erts_thr_progress_later() 並等待直到我們達到該執行緒進度，我們就知道在我們呼叫 erts_thr_progress_later() 時，沒有受管理的執行緒可以引用直到最後一個指標所指向的元素。這是因為所有受管理的執行緒都必須至少離開一次實現此功能的程式碼，並且它們始終通過最後一個指標進入列表。tail.next 欄位包含有關下一個 head.unref_end 指標和執行緒進度的資訊，必須先達到該進度，我們才能移動 head.unref_end。
不幸的是，不僅由執行緒進度功能管理的執行緒可能會插入記憶體區塊。也需要處理其他執行緒。其他執行緒將不像受管理的執行緒那樣頻繁地使用此功能，因此對它們使用效率較低的方案並不是一個大問題。為了處理未受管理的執行緒，我們使用兩個參考計數器。當未受管理的執行緒進入此實作時，它會增加當前使用的參考計數器，當它離開此實作時，它會減少相同的參考計數器。當消費者執行緒呼叫 erts_thr_progress_later() 以確定何時可以安全移動 head.unref_end 時，它也會交換未受管理執行緒的參考計數器。先前當前表示從此時到此時間點的未完成參考。新的當前表示此點之後的未來參考。當消費者執行緒偵測到我們既已達到所需的執行緒進度，又達到先前的當前參考計數器為零時，就可以安全移動 head.unref_end。
使用兩個參考計數器的原因是，我們需要知道參考計數器最終將達到零。如果我們只使用一個參考計數器，則不同的未受管理執行緒可能會將其保持在零以上。
空列表
如果沒有新的記憶體區塊插入到列表中，它最終應該被清空。但是，指向列表的所有指標都期望始終指向某個東西。這可以通過插入一個空的「標記」元素來解決，該元素的存在目的僅僅是在沒有其他元素的情況下存在。也就是說，當列表為空時，它僅包含此「標記」元素。
競爭
當由不擁有配置器實例的執行緒持續插入元素時，擁有配置器實例的執行緒將能夠在列表的頭部端或多或少不受其他執行緒干擾地工作。在尾部，大量同時插入可能會導致競爭，但是我們通過在末尾附近分散插入新元素，而不是要求將所有新元素都插入到末尾，來減少這種競爭。
排程器和鎖定的配置器實例
此外，供非排程器執行緒使用的鎖定配置器實例也具有用於釋放工作的訊息箱，就像所有其他配置器實例一樣。這樣做的原因是，其他執行緒可能會配置記憶體並將其傳遞給需要釋放記憶體的排程器。我們不希望排程器等待此鎖定實例上的鎖。由於鎖定實例也有用於釋放工作的訊息箱，因此排程器可以只插入工作並避免鎖定。
基準測試結果
執行 ehb 基準測試時，會在排程器之間傳遞大量訊息。所有訊息傳遞都會以某種方式導致記憶體配置和釋放。由於訊息在不同的排程器之間傳遞，因此我們將在配置訊息的配置器實例上產生競爭。通過引入延遲釋放功能，當在配備超執行緒的 Intel i7 四核心處理器的新機器上使用 8 個排程器執行時，我們獲得了 25-45% 的加速，具體取決於基準測試的配置。