檢視原始碼 載體遷移
簡介
ERTS 記憶體配置器管理兩種原始記憶體區塊中的記憶體塊。我們將這些原始記憶體區塊稱為載體。單區塊載體僅包含一個大型區塊，而多區塊載體則包含多個區塊。載體通常在 Unix 系統上使用 mmap() 建立。但是，載體的建立方式並不重要。配置器實例通常管理單區塊和多區塊載體的混合。
問題
當載體為空時，即僅包含一個大型可用區塊時，會被釋放。由於多區塊載體可以同時包含已分配的區塊和可用區塊，因此如果記憶體負載降低，配置器實例可能會被大量利用率不佳的載體卡住。在記憶體使用量達到高峰之後，預期並非所有記憶體都能被歸還，因為仍然分配的區塊很可能會分散在多個載體中。如果記憶體負載再次增加，這些利用率不佳的載體通常可以重複使用。但是，由於每個排程器執行緒管理其自己的一組配置器實例，並且記憶體負載不一定與 CPU 負載相關，我們可能會遇到這樣的情況：某些配置器實例上有大量利用率不佳的多區塊載體，而我們需要在其他配置器實例上分配新的多區塊載體。在這種情況下，系統中對多區塊載體的需求可能會在系統中的實際記憶體需求降低的同時增加，這對於最終使用者來說既不希望發生，也相當出乎意料。
解決方案
為了防止這種情況發生，我們實作了支援在配置器實例之間遷移多區塊載體的功能。
可用區塊的管理
為了能夠從一個配置器實例中移除載體並將其添加到另一個實例，我們需要在配置器實例之間移動對載體可用區塊的參考。配置器實例特定的資料結構，引用其管理的可用區塊，通常會從多個位置引用同一個載體。例如，當使用位址順序最佳擬合策略時，此資料結構是跨越配置器實例管理的所有載體的二元搜尋樹。一個特定載體中的可用區塊可能會被管理的其他每個載體引用，並且此類引用的數量可能很大。也就是說，從搜尋樹中移除此類載體的可用區塊的工作量將會很大。一種解決方案可能是不遷移包含大量可用區塊的載體，但這會阻止我們遷移可能需要遷移的載體，以解決我們著手解決的問題。
藉由在每個載體中使用一個可用區塊資料結構，以及一個配置器實例範圍的資料結構來管理由配置器實例管理的載體，可以將移除和新增載體所需的工作量降至最低。當在特定配置器類型上啟用載體遷移時，我們要求使用具有此類實作的配置策略。目前，我們已針對三種不同的配置策略實作了此功能。所有這些策略都使用載體的搜尋樹進行排序，以便我們可以找到可以滿足要求的位址最低的載體。在載體內部，我們使用另一個搜尋樹，該樹實作位址順序首次擬合、位址順序最佳擬合或最佳擬合。用於這些不同配置策略的縮寫是 aoff、 aoffcaobf 和 aoffcbf。
載體池
為了在配置器實例之間遷移載體，我們將它們透過載體池進行移動。為了完成載體遷移，一個排程器需要將載體移入池中，而另一個排程器需要將載體從池中取出。
該池實作為一個無鎖、循環、雙向連結的清單。該清單包含一個哨兵，該哨兵用作插入或從池中擷取的起點。池中的載體是此清單中的元素。
該清單可以由所有排程器執行緒同時修改。在修改過程中，允許雙向連結清單稍微「變形」。例如，追蹤指向下一個元素的 next 指標，然後追蹤 prev 指標，並不總是將您帶回您開始的位置。但是，以下情況始終為真
- 重複追蹤
next指標最終會將您帶到哨兵。 - 重複追蹤
prev指標最終會將您帶到哨兵。 - 追蹤
next或prev指標會將您帶到池中的元素，或曾經在池中的元素。
當插入新元素時，我們只追蹤 next 指標來搜尋插入元素的位置，並且我們總是從跳過遇到的第一個元素開始。當嘗試擷取元素時，我們會做相同的事情，但只追蹤 prev 指標。
透過在插入和擷取時朝不同的方向移動，我們盡可能避免插入執行緒和擷取執行緒之間的爭用。透過在開始搜尋時跳過一個元素，我們盡可能保持哨兵不被修改。這是很有利的，因為所有搜尋操作都需要讀取哨兵的內容。如果我們要修改哨兵，包含哨兵的快取行將不必要地在處理器之間跳動。
清單元素中的 prev 和 next 欄位包含指標值、修改標記和刪除標記。對這些欄位的記憶體操作是使用原子記憶體操作完成的。當執行緒在欄位中設定修改標記時，除了設定標記的執行緒之外，不允許任何人修改該欄位。如果需要設定多個修改標記，我們總是從 next 欄位開始，然後按照實際指標順序進行 prev 欄位。這保證不會發生死鎖。
當從池中移除載體時，我們將其標記為一個執行緒進度值，在允許修改 next 和 prev 欄位之前需要達到該值。也就是說，在達到此執行緒進度之前，我們不允許再次將載體插入池中，也不允許釋放載體。這確保了檢查池的執行緒始終能夠遍歷池並到達有效元素。一旦我們達到載體標記的執行緒進度值，我們就知道沒有執行緒可能透過池引用它。
遷移
每個配置器實例都會追蹤其多區塊載體的目前利用率。當總利用率低於「放棄載體利用率限制」時，它會在進行釋放時開始檢查目前載體的利用率。如果載體的利用率也低於「放棄載體利用率限制」，它會將載體從其可用區塊的資料結構中取消連結，並將載體插入池中。
由於載體已從可用區塊的資料結構中取消連結，因此不會在載體中進行更多配置。
建立載體的配置器實例稱為其擁有者。所有權永遠不會改變。
負責在載體中執行釋放的配置器實例稱為其僱用者。如果載體不在池中，僱用者也可以執行配置。當從池中擷取或插入載體時，僱用關係可能會變更。
當載體保留在池中時，在載體中的釋放始終由擁有者執行。也就是說，所有池化載體都由其擁有者僱用。
每個載體都有一個原子字，其中包含指向僱用配置器實例的指標和三個位元旗標：IN_POOL、BUSY 和 HOMECOMING。
當從池中擷取載體時，僱用關係可能會變更，並且載體中的進一步釋放將使用延遲釋放功能重新導向到新的僱用者。
當外部配置器實例將載體放棄回池中時，它也會使用延遲釋放佇列將其傳回給其擁有者。執行此操作時，它會設定 HOMECOMING 位元旗標，將其標記為「已排入佇列」。擁有者稍後會在載體從佇列中移除時清除 HOMECOMING 位元。此機制可防止載體在從佇列中移除之前再次排入佇列。
當載體變為空時，將會被釋放。載體釋放始終由分配載體的擁有者完成。透過這樣做，配置和釋放載體的底層功能可以保持簡單，而不必擔心多個執行緒。在 NUMA 系統中，我們也不會混合來自多個 NUMA 節點的載體。
如果池中的載體變為空，它將從池中取出，並由已經僱用它的擁有者釋放。
如果由外部配置器僱用的載體變為空，它將使用延遲釋放功能傳回給擁有者以進行釋放。
簡而言之
- 建立載體的配置器實例擁有它。
- 空載體始終由其擁有者釋放。
- 所有權永遠不會改變。
- 使用載體的配置器實例僱用它。
- 僱用者可以將載體放棄到池中。
- 不會從池化載體中配置。
- 池化載體始終由其擁有者僱用。
- 所有權 只有在從資源池中提取載體時，才能從 擁有者 變更為外部配置器。
搜尋資源池
當配置器實例需要更多載體空間時，它會檢查資源池。如果無法從資源池中提取任何載體，它將配置一個新的載體。無論配置器實例從哪裡取得載體，它都會將載體連結到其可用區塊的資料結構中。
為了保有即時特性，對資源池的搜尋是有限制的。我們只會檢查有限數量的載體。如果這些載體中沒有任何一個具有足夠大的可用區塊來滿足配置請求，則搜尋將會失敗。如果另一個執行緒目前正在對載體進行區塊釋放工作，則資源池中的載體也可能處於忙碌狀態。處於忙碌狀態的載體也會被搜尋跳過，因為它無法滿足請求。資源池是無鎖的，我們不希望阻塞等待其他執行緒完成。
不良叢集問題
在 OTP-17.4 之前，搜尋演算法存在一個問題，因為搜尋始終從資源池中的相同位置（即哨兵）開始。這可能導致並發搜尋程序之間的競爭。但更糟的是，當搜尋以高失敗率導致配置新的載體時，可能會導致「不良」狀態。這些新的載體稍後可能會由於不良的利用率而被插入到資源池中。如果插入到資源池中的頻率高於從資源池成功提取的頻率，記憶體最終將會耗盡。
這種「不良」狀態是由位於資源池中哨兵處的一組小型和/或高度碎片化的載體組成的。這種「不良」載體中最大的可用區塊相當小，使其無法滿足大多數配置請求。由於搜尋始終從哨兵開始，因此任何留在資源池中的此類「不良」載體最終都會聚集在哨兵處。所有搜尋首先必須跳過這組「不良」載體才能到達「良好」的載體。當叢集的大小與搜尋限制相同時，所有搜尋基本上都會失敗。
為了應對「不良叢集」問題並減輕競爭，搜尋現在將始終首先檢視配置器自己的載體。也就是說，最初由配置器本身建立，後來被遺棄到資源池中的載體。如果我們自己被遺棄的載體中沒有任何一個可以滿足要求，那麼搜尋將像以前一樣繼續進入資源池，尋找由其他配置器建立的載體。但是，如果我們至少有一個自己被遺棄但無法滿足請求的載體，我們可以將其用作進入資源池的入口點。
結果是我們優先使用執行緒本身建立的載體，這對於 NUMA 效能是有益的。並且當搜尋資源池時，我們會獲得更多的入口點，這將減輕競爭和叢集。
我們自己的資源池樹
為了在自己的載體中進行第一次搜尋，每個配置器實例都有一個載體的 pooled_tree。這個樹只能由配置器本身存取，並且只能包含自己的載體。當載體被遺棄並放入資源池時，它也會被插入到 pooled_tree 中。如果該載體已經被其擁有者使用，則直接完成此操作；或者先透過延遲釋放佇列將其傳遞回擁有者。
當我們搜尋 pooled_tree 並發現不再在資源池中的載體時，我們會從 pooled_tree 中移除該載體，並將其標記為 TRAITOR（叛徒），因為它現在已被外部配置器使用。我們不會在 pooled_tree 中發現任何被其他執行緒標記為 BUSY 的載體。
如果 pooled_tree 中沒有任何載體具有足夠大的可用區塊，我們會再次搜尋它，以尋找任何可以作為進入所有資源池載體共享列表的入口點的載體。這樣做的目的是為了盡可能避免從哨兵開始，從而緩解「不良叢集」問題。
此外，對計劃釋放的自有載體的搜尋是作為最後一個搜尋選項完成的。這樣做的想法是，重複使用一個利用率較低的載體比復活一個即將被釋放回作業系統的空載體要好。
結果
這種遺棄利用率不佳的載體並在對載體需求增加的配置器實例中重複使用它們的策略非常有效，並且完全消除了在 CPU 負載下降而記憶體負載沒有下降時有時會發生的問題。
當使用 aoffcaobf 或 aoff 策略與 gf 或 bf 相比時，由於我們在可用區塊的資料結構中進行了更多修改，因此會損失一些效能。然而，使用 aoffcbf 策略可以減少這種效能損失。然而，記憶體消耗和效能之間的權衡是不可避免的，這取決於使用者決定什麼是最重要的。