檢視原始碼 程序管理優化
問題
早期版本的執行時期系統 SMP 支援完全依賴鎖定來保護多個執行緒的資料存取。在某些情況下，這並不是那麼有問題，但在某些情況下，確實是個問題。它使程式碼複雜化，確保所有需要的鎖定實際上都被持有，並確保所有鎖定都以不會發生死鎖的順序取得。以正確的順序取得鎖定通常還涉及釋放持有的鎖定，迫使執行緒重新讀取已讀取的資料。這是一個創造錯誤的好方法。嘗試使用更細粒度的鎖定以增加系統中可能的並行性，會使複雜性情況變得更糟。在執行操作時，必須取得一堆鎖定也常常導致嚴重的鎖定競爭，從而導致不良的可擴展性。
執行時期系統內部程序的管理也受到這些問題的影響。當更改程序的狀態時，例如從 等待中 到 可執行，需要在程序上鎖定。當將程序插入到執行佇列中時，也必須鎖定保護執行佇列的鎖定。當將程序從一個執行佇列遷移到另一個執行佇列時，必須鎖定兩個執行佇列和程序的鎖定。
最後一個例子在正常操作中是一個非常常見的情況。例如，當排程器執行緒耗盡工作時，它會嘗試從另一個排程器執行緒的執行佇列中竊取工作。當搜尋要竊取的受害者時，涉及大量執行佇列鎖定的操作，並且在實際竊取時，必須鎖定兩個執行佇列和程序。當一個排程器耗盡工作時，通常其他排程器也會耗盡，導致大量的鎖定競爭。
解決方案
程序
為了避免這些情況，我們希望能夠在大多數情況下，對程序執行基本操作，而無需取得程序的鎖定。一些基本操作的例子包括：在執行佇列之間移動程序、偵測是否需要將其插入到執行佇列中，以及偵測其是否存活。
程序結構中這些操作所需的所有資訊都受程序的 status 鎖定保護，但這些資訊分佈在多個欄位中。使用的欄位通常是狀態欄位，其中可能包含少量不同的狀態。透過稍微重新排列這些資訊，我們可以輕鬆地將這些資訊放入一個 32 位元的位元標誌欄位（只需要 12 個標誌）。透過移動這些資訊，我們可以從程序結構中刪除五個 32 位元的欄位和一個指標欄位！此移動還使我們能夠使用原子記憶體操作輕鬆讀取和更改狀態。
執行佇列
與程序一樣，我們希望能夠在大多數情況下，執行基本操作而無需取得鎖定。最重要的操作是能夠判斷是否應該將程序加入到特定的執行佇列中。這涉及能夠讀取實際負載和負載平衡資訊。
負載平衡功能會在重複的固定間隔觸發。負載平衡或多或少地致力於使整個系統的執行佇列長度平均化。當觸發平衡時，會收集有關每個執行佇列的資訊，並設定遷移路徑和執行佇列長度限制。遷移路徑和限制在下次平衡完成之前是固定的。關於每個執行佇列最重要的資訊是自上次平衡以來的最大執行佇列長度。所有這些資訊以前都儲存在執行佇列本身中。
當一個程序變成可執行狀態時，例如由於接收到訊息，我們需要確定要將其加入哪個執行佇列。先前，這至少涉及鎖定程序目前所分配到的執行佇列，同時持有程序的狀態鎖定。根據負載情況，我們有時還必須取得另一個執行佇列的鎖定，才能判斷是否應該將其遷移到該執行佇列。
為了能夠在不鎖定任何執行佇列的情況下決定要使用哪個執行佇列，我們將所有固定的平衡資訊從執行佇列中移出到全域記憶體區塊中。也就是說，遷移路徑和執行佇列限制。需要頻繁更新的資訊（例如最大執行佇列長度）保留在執行佇列中，但我們不再在鎖定下操作這些資訊，而是在存取這些資訊時使用原子記憶體操作。這樣，我們可以先在不鎖定任何執行佇列的情況下確定要使用哪個執行佇列，當決定好時，鎖定選定的執行佇列並插入程序。
固定的平衡資訊
當決定要選擇哪個執行佇列時，我們需要讀取從執行佇列中移出的固定平衡資訊。此資訊是全域的，在負載平衡操作之間為唯讀，但在負載平衡期間將會被更改。我們不希望引入在存取此資訊時需要取得的全域鎖定。讀取器優化的 rwlock 可以避免一些額外負擔，因為資料最常被讀取，但這將不可避免地在負載平衡期間造成中斷，因為此資訊的讀取頻率非常高。由於這種情況導致重大中斷的可能性也會隨著排程器的數量增加而增加。
我們沒有使用全域鎖定來保護此資訊的修改，而是在每次負載平衡時寫入一個全新的版本。新版本寫入到與先前版本不同的記憶體區塊中，並透過發出寫入記憶體屏障，然後使用原子寫入操作將指向新記憶體區塊的指標儲存在全域變數中來發布。
當排程器需要讀取此資訊時，它們會使用原子讀取操作讀取目前使用的資訊的指標，然後發出資料相依性讀取屏障，這在大多數架構上是無操作。也就是說，取得此資訊的額外負擔非常少。
我們沒有為不同版本的平衡資訊分配和釋放記憶體區塊，而是保留舊的記憶體區塊，並在安全時重複使用它們。為了能夠判斷何時可以安全地重複使用區塊，我們使用執行緒進度功能，確保在我們重複使用記憶體區塊時，沒有執行緒對其有任何引用。
減少積極性
我們實作了一個使用無鎖定執行佇列的測試版本。但是，這個實作的效能不如每個執行佇列使用一個鎖定的版本。沒有充分研究這樣做的原因。由於鎖定版本的效能更好，所以我們保留了它，至少目前是這樣。但是，無鎖定版本迫使我們使用其他解決方案，我們保留了其中的一些解決方案。
先前，當執行佇列中的程序暫停時，我們會立即將其從佇列中移除。這涉及鎖定程序、鎖定執行佇列，然後從實作佇列的雙向連結串列中取消連結它。從無鎖定佇列中移除程序變得非常複雜。因此，我們沒有將其從佇列中移除，而是將其保留在佇列中並標記為暫停。當稍後選擇執行時，我們會檢查程序是否已暫停，如果是，則將其捨棄。在佇列中，它也可能再次恢復執行，如果是，則在選取執行時執行它。
透過在回復到鎖定實作時保留這個部分，我們可以移除每個程序結構中的指標欄位，並避免在程序和佇列上進行可能導致競爭的不必要操作。
組合修改
透過組合程序狀態管理和執行佇列管理的修改，我們可以在管理有關排程和遷移的程序時，在完全沒有鎖定的情況下完成大部分工作。在這種情況下，我們以前必須鎖定多個鎖定。當然，這導致執行時期系統的許多部分進行了大量的重寫，但是重寫既簡化了程式碼，又消除了許多地方的鎖定。主要好處當然是減少了競爭。
基準測試結果
在執行 chameneosredux 基準測試時，排程器經常耗盡工作，並嘗試互相竊取工作。也就是說，要么成功遷移，要么嘗試遷移程序，這是我們想要優化的情境。透過引入這些改進，當在配備 Intel i7 四核心處理器和超執行緒的相對較新的機器上使用 8 個排程器執行此基準測試時，我們獲得了 25-35% 的加速。