檢視原始碼 程序和埠表
問題
程序表是從程序識別碼到程序結構指標的映射。程序結構包含關於程序的各種資訊，例如指向其堆積、訊息佇列等的指標。當執行時期系統需要操作程序時，它會使用程序識別碼在程序表中查找程序結構。一個例子是將訊息傳遞給程序。
程序表長期以來只是一個指向程序結構的指標陣列。由於執行時期系統內部的程序識別碼是 28 位元的整數，因此很容易將程序識別碼映射到陣列的索引。這 28 個位元被分為兩組。最不重要的位元組被用作陣列的索引。最重要的位元組僅用於區分映射到陣列中相同索引的多個識別碼。只要使用二的冪次的程序表大小，我們就有 2^28 個唯一的程序識別碼。
當第一個 SMP 支援實作時，表格仍然保持大致相同的方式，但受到兩種鎖的保護。一個鎖保護整個表格免於修改，另一個鎖陣列保護表格的不同部分。先前使用的確切鎖定策略並不重要。重要的是，它遭受了嚴重的鎖競爭，尤其是在進行大量修改時，但即使僅執行查找時也是如此。
為了能夠偵測何時可以安全地釋放先前使用的程序結構，使用了結構的參考計數。這也是有問題的，因為同時查找需要修改參考計數器，這也會導致參考計數器所在的快取行上的競爭。這是因為所有修改都需要在所有相關處理器之間傳遞。
埠表與程序表非常相似。至少在概念上，主要的差異在於它從埠識別碼到埠結構的映射。它有一個類似的實作，但有一些差異。它不是一個指標陣列，而是一個結構陣列，並且它不是由兩種鎖保護，而是僅由一個全域鎖保護。這個表格在各種情況下也遭受了鎖競爭。
解決方案
程序表是要解決的主要問題，因為程序的使用頻率遠高於埠。第一個實作僅針對程序實作了此功能，但是由於埠表非常相似，並且埠表上也會出現非常類似的問題，因此後來對程序表實作進行了概括，以便也可以用於實作埠表。為簡單起見，以下文字中我將僅討論程序表，但除非另有說明，否則同樣適用於埠表。
如果我們忽略鎖定問題，則原始解決方案非常吸引人。從程序識別碼到陣列索引的映射非常快，我們希望保留此屬性。這些表格上的絕大多數操作都是查找，因此針對查找進行最佳化是我們要做的。
查找
使用程序識別碼中的一組位元作為陣列索引似乎很難被超越。通過將指標陣列替換為我們的指標大小的原子資料類型陣列，查找將包含以下內容：
將 28 位元整數映射到陣列的索引。
稍後將詳細介紹此映射。
使用原子記憶體操作在陣列中的已確定索引處讀取指標。
在我們提供原子記憶體操作的所有平台上，這只是一個
volatile讀取，防止編譯器使用暫存器中的值，強制從記憶體讀取。根據用途，發出適當的記憶體屏障。
常用的屏障是具有取得語義的屏障。在 x86/x86_64 上，這會映射到防止編譯器重新排序指令的編譯器屏障，但在其他硬體上，通常還需要某種輕量級硬體記憶體屏障。
與鎖定方法相比，在大多數（如果不是全部）硬體架構（包括 x86/x86_64）上鎖定鎖時，至少會發出一個重量級記憶體屏障，並且在解除鎖定時，通常會發出某種輕量級記憶體屏障。
當查看這個開銷很小的非常簡單的解決方案時，您可能會想知道為什麼我們從一開始就沒有以這種方式實作它。這一切都歸結為指標的讀取操作。我們需要某種方法來知道存取指向的記憶體是安全的。一種方法是在程序結構中放置參考計數器。查找時參考計數器的遞增需要與查找以原子方式完成。鎖通常可以為我們提供此服務，這就是我們先前使用的方法。另一種方法可能是將參考計數器與表格中的指標並置。這種方法的主要問題是參考計數器的修改。這是因為這些修改必須在所有相關處理器之間傳遞，導致包含參考計數器的快取行上的競爭。上面新的查找方法是可能的，因為我們可以利用「執行緒進度」功能來確定何時可以安全地釋放程序結構。我們將在描述表格中的刪除時回到這一點。
使用這種新的查找方法，我們根本不會修改任何記憶體，這很重要。從概念上講，查找僅讀取記憶體，現在這在實作中也是如此，這從可擴展性的角度來看很重要。先前的實作修改了包含參考計數器的快取行兩次，並在每次查找時修改了包含相應鎖的快取行兩次。
表格的修改
表格中的輕量級查找是最重要的功能，但我們也希望改進表格的修改。當產生新程序時（即將新指標插入表格）以及當程序終止時（即從表格中刪除指標）會修改程序表。
假設我們產生的程序少於系統中唯一程序識別碼的最大數量，則始終可以通過比較程序識別碼來確定程序建立的順序。如果 PidX 大於 PidY，則假設兩個識別碼都來自同一個節點，則 PidX 是在 PidY 之後建立的。但是，由於我們今天擁有的唯一識別碼數量非常有限 (2^28)，如果我們建立大量的程序，則不能依賴此屬性。但儘管如此，這一直是系統所擁有的屬性。
如果我們有大量的可用唯一識別碼，則很可能放棄或修改如上所述的此排序屬性。例如，排序屬性可以基於執行產生操作的排程器。可以為每個排程器執行緒保留大量的識別碼範圍，這些識別碼範圍可用於最大程度地減少分配識別碼時的通訊需求。但是，我們今天使用的識別碼數量甚至不足以採用這種方法。
由於我們擁有的唯一識別碼數量有限，因此我們需要謹慎，不要浪費它們。如果過快重複使用先前使用的識別碼，則來自已終止程序的識別碼將引用新建立的程序，並且會發生混淆。先前使用的方法非常擅長不浪費識別碼。使用修改後的相同方法版本還可以使我們保持一直擁有的排序屬性。
插入
原始方法或多或少是在陣列中搜尋下一個空閒索引或插槽。搜尋從最後分配的插槽開始。如果我們到達陣列的末尾，我們會增加一個「包裝計數器」，然後繼續搜尋。程序識別碼的構造方法是將索引寫入最不重要的位元組，並將「包裝計數器」寫入最重要的位元組。每組位元中的位元數是在啟動時決定的，因此最大索引將恰好適合最不重要的位元組。
在修改後的無鎖版本的方法中，我們或多或少以相同的方式執行，但是進行了一些重要的修改，試圖避免多個排程器同時建立程序時的不必要競爭。由於多個執行緒可能同時從同一起點嘗試搜尋下一個空閒插槽，因此我們希望後續插槽位於不同的快取行中。因此，多個排程器同時將新指標寫入表格很可能會寫入相鄰的插槽。如果相鄰插槽位於同一快取行中，則需要將此快取行的所有修改在所有相關處理器之間傳遞，這將非常昂貴且規模非常差。通過將相鄰插槽放在不同的快取行中，只有真正的衝突才會觸發相關處理器之間的通訊，即避免虛假共享。
快取行大於指標，通常大 8 或 16 倍，因此為每個僅包含一個指標的插槽使用一個快取行將是浪費空間。每個快取行將能夠容納固定數量的插槽。表格的第一個插槽將是第一個快取行的第一個插槽，表格的第二個插槽將是第二個快取行的第一個插槽，直到我們到達陣列的末尾。之後的下一個插槽將是第一個快取行的第二個插槽，依此類推，每次換行時向前移動一個快取行內部插槽。這樣，我們將能夠將相同數量的指標放入相同大小的陣列中，同時始終將相鄰的插槽保持在不同的快取行中。
從識別符到陣列中的槽位或索引的映射，比以前稍微複雜。我們不再使用shift和位元and運算，而是使用兩個shift、兩個位元and，和一個add運算（請參閱erl_ptab.h中的erts_ptab_data2pix()實作）。然而，透過儲存經過查找優化的資訊，我們在 32 位元平台上只需要一個shift和一個位元and運算。在 64 位元平台上，我們在最低有效半字中有足夠的空間容納 28 位元的識別符，而在最高有效半字則儲存索引，換句話說，我們只需要讀取最高有效半字即可取得索引。也就是說，此操作與之前一樣快，甚至更快。缺點是，在 32 位元平台上，當列印或排序來自同一節點的識別符時，我們需要將此資訊轉換為 28 位元的識別符號碼。然而，與查找相比，這些操作極為不頻繁。
當我們在表格中插入新元素時，我們會執行以下操作
首先，我們透過原子性地遞增表格中程序的計數器來預留表格中的空間。如果我們的遞增使計數器超過表格的最大大小，則操作失敗並引發
system_limit例外。表格包含一個 64 位元的原子變數，用於記錄最後使用的識別符。實際建立識別符時，只會使用最低有效位元。此識別符是搜尋的起點。
我們遞增最後使用的識別符值。為了判斷對應於此識別符的槽位，我們呼叫
erts_ptab_data2pix()，該函數會將識別符映射到槽位。我們讀取槽位的內容。如果該槽位是空的，我們會嘗試使用原子比較和交換寫入保留標記。如果此操作失敗，我們會重複此步驟直到成功為止。變更最後使用的識別符的表格變數。由於可能會同時發生多次寫入，因此該值可能已被更改為大於我們取得的識別符。在這種情況下，我們可以繼續；否則，我們需要將其更改為我們取得的識別符。
現在，我們會對程序結構進行一些初始化，這些初始化在我們知道程序識別符之前無法完成，並且必須在我們將該結構發佈到表格之前完成。例如，這包括將識別符儲存在程序結構中。
現在，我們可以透過將指向程序結構的指標寫入先前在步驟 3 中保留的槽位，將該結構發佈到表格中。
使用此方法，我們保持了識別符排序和識別符重用的特性，同時提高了效能和可擴展性。不過，它有一個缺點。無法保證操作會終止。不過，這可以很容易地修復，並且將在下一個版本中修復。我們將在下面回到這一點。
刪除
當程序終止時，我們會在程序結構中將程序標記為已終止，表格中程序數量的計數器會遞減，並且透過將 NULL 指標寫入對應的槽位來移除對程序結構的參照。執行此操作的排程器執行緒隨後會排程一個執行緒進度稍後工作，該工作將執行最終清理並釋放程序結構。執行緒進度功能將確保此工作不會執行，直到確定所有受管理的執行緒都已捨棄對程序結構的所有參照為止。
BIF 迭代表格
erlang:processes/0 和 erlang:ports/0 BIF 會迭代表格並傳回對應的識別符。這些 BIF 應在 BIF 執行期間的某個時間傳回表格內容的一致快照。為了實作此功能，我們以一種奇怪的方式使用鎖定。我們使用「反向讀寫鎖」。
在表格中執行查找時，我們根本不需要擔心鎖定，但在修改表格時，我們會讀取鎖定保護表格的讀寫鎖，這允許在正常操作期間有多個寫入者。當迭代表格的 BIF 需要存取表格時，它會寫入鎖定讀寫鎖並讀取表格的內容。BIF 不會一次讀取整個表格，而是一次只讀取小塊，並且只在讀取時寫入鎖定。BIF 的實際實作超出本文檔的範圍。
現成的讀寫鎖通常會在包含讀寫鎖狀態的單個快取行上遇到競爭，即使在我們僅讀取鎖定的情況下也是如此。我們沒有使用此類讀寫鎖，而是擁有自己的讀取器優化讀寫鎖實作，該實作會在單獨的執行緒特定快取行中追蹤讀取器執行緒。這是為了避免在單個快取行上發生競爭。只要我們只執行讀取鎖定操作，執行緒就只需要讀取全域快取行並修改自己的快取行，並且藉此最大限度地減少涉及的處理器之間的通訊。迭代 BIF 通常非常不頻繁地使用，因此在正常情況下，我們只會在表格全域讀寫鎖上執行讀取鎖定操作。
未來改進
第一個改進是修復保證，以便保證插入操作會終止。當操作開始時，我們會驗證是否真的存在我們可以使用的空閒槽位。問題在於我們可能找不到它，因為當多個執行緒同時修改表格時，它可能會移動，而我們正在嘗試尋找該槽位。簡單的解決方法是在有限次操作中找不到空槽位時中止操作，然後在寫入鎖定下重新啟動操作。這將在下一個版本中實作，但應該進一步努力尋找更好的解決方案。
當表格幾乎已滿時，此實作和先前的實作都無法正常工作。我們將獲得較長的空閒槽位搜尋時間，並且由於我們在搜尋過程中更頻繁地環繞，因此我們將更頻繁地重複使用識別符。當表格遠大於同時存在的程序數量時，這些表格效果最佳。一個簡單的改進方法是，始終為比我們允許的更多程序保留空間。這也將在下一個版本中實作，但可能也應該進一步努力尋找更好的解決方案。
最好也能完全擺脫讀寫鎖。使用讀取器優化的讀寫鎖可確保我們在鎖上沒有任何競爭，但會由於鎖而發出不必要的記憶體屏障。這裡的主要問題是修改迭代 BIF，以便它們在讀取一系列槽位時不需要獨佔存取表格。原則上這應該很容易，程式碼可以處理可變大小的序列，因此將槽位的序列大小縮小為一個即可解決問題。但是，這需要對非瑣碎的程式碼進行一些調整和修改，但這是將來應該研究的事情。
透過增加識別符的大小（至少在 64 位元機器上，這不像最初看起來那麼容易），我們還有進一步改進的空間。除了顯而易見的不像我們目前那樣快速重複使用識別符的改進之外，還可以進一步避免在表格中插入元素時發生競爭。至少如果我們放棄這種排序特性，它無論如何都沒有那麼有用。
一些基準測試結果
為了測試程序表格的修改，我們執行了一些基準測試，其中同時產生和終止大量程序，並獲得了 150-200% 的加速。執行類似的基準測試，但使用連接埠，我們獲得了約 130% 的加速。
BIF erlang:is_process_alive/1 是您最接近程序表格查找的方法。BIF 會查找對應於作為引數傳遞的程序識別符的程序，然後檢查它是否還活著。透過執行多個程序循環執行此 BIF 檢查同一個程序，我們獲得了 20000-23000% 的加速。從概念上講，此操作僅涉及讀取操作。在 R16B 中使用的實作中，也僅執行讀取操作，而先前的實作需要鎖定結構才能讀取資料，從而導致鎖定競爭以及由於修改鎖定內部資料結構使用的快取行和正在查找的程序的參考計數器而導致的競爭。
基準測試是在具有 Intel i7 四核心處理器（具有超執行緒）的相對較新的機器上使用 8 個排程器執行的。在具有更多通訊開銷和/或更多邏輯處理器的機器上，預計加速效果會更大。