1024個CPU的內核調度

Question

Azul Systems擁有一個支持數千個緩存一致性CPU的設備。我很想知道爲了安排數千個同時運行的線程而需要對操作系統進行哪些更改。

Answer 1

您要求對操作系統進行可能的更改，所以我認爲這項工作背後有一個重要的工程團隊。

也有clarififying信息，這將有助於確定問題的參數幾塊：

多少IPC（進程間通信），你需要什麼？
他們是否真的必須是線程，還是他們可以是進程？
如果他們是進程，如果必須通過套接字彼此對話，而不是使用共享內存，那麼是否可以？
什麼是內存架構？你是直接使用1024核心的SMP，還是有其他一些NUMA（非統一內存架構）或MMP在這裏？你的頁面表是什麼樣的？

只知道有關Azul系統的最小信息，我猜你的IPC很少，而且一個簡單的「每個內核運行一個內核」模型實際上可能工作得很好。如果進程需要彼此交談，那麼他們可以創建套接字並以這種方式傳輸數據。你的硬件是否支持這種模式？ （你可能最終需要每個內核一個IP地址，並且在1024個IP地址上，這可能很麻煩，儘管它們都可能是NAT的，也可能不是那麼重要）。如果當然，這種模式會導致一些效率低下的情況，比如額外的頁表，以及相當一部分內存開銷，甚至可能不會被硬件系統支持。

即使「每個核心1個內核」不起作用，您可能會運行1024/8個內核，並且會很好，讓每個內核控制8個物理CPU。這就是說，如果你想在一個傳統的SMP機器上運行1個線程，每個內核只有1024個內核（並且只有少數幾個物理CPU），那麼我認爲舊式的O（1）調度器就是你想要的想。很有可能你的CPU [0]在內核中會以近100％的速度結束並進行中斷處理，但對於這種用例來說，這很好，除非你需要超過1個內核來處理你的工作負載。

Answer 2

調度成千上萬的線程並不是什麼大不了的事情，但是在數百個CPU上調度它們是。首先您需要的是非常細緻的鎖定，或者更好的是，無鎖數據結構和算法。當一個CPU執行關鍵部分時，您不能讓200個CPU等待。

Answer 3

我沒有受過教育的猜測是，當處理器空閒時，每個處理器有一個運行隊列和一個工作竊取算法。我可以看到這在M：N模型中工作，每個cpu和輕量級進程都有一個進程作爲工作項目。然後，這會和盜取工作的線程池類似，比如Java-7的fork-join庫中的線程池。

如果你真的想知道，可以選擇Solaris內核或深入Solaris內核代碼。我仍然在讀設計& FreeBSD的Impl，Solaris Internals是我名單上的下一個，所以我所能做的就是做一個瘋狂的猜測atm。

Answer 4

我很確定我們在工作中使用的SGI Altix（ccNUMA）使用特殊的硬件來實現緩存一致性。

有一個巨大的開銷連接到每個核心相干持有4MB緩存。這不太可能發生在軟件上。

在一個256 cpu的數組中，您需要768mb RAM來保存緩存無效位。 12MB緩存/每個緩存行128字節* 256個核心。

Answer 5

修改操作系統是一回事，但使用不變的應用程序代碼會浪費硬件。當遇到一些限制（取決於硬件）時，爲了執行通用代碼而保持一致性和同步的努力實在太多了。你可以做到這一點，但它會非常昂貴。 從操作系統方面來說，您需要複雜的關聯模型，即不要因爲您的CPU繁忙而跳CPU。基於硬件拓撲調度線程 - 在「關閉」的CPU上協作線程以最小化處罰。簡單的工作竊取並不是一個好的解決方案，你必須考慮拓撲結構。一種解決方案是分層偷竊 - 按距離竊取工作，將拓撲劃分到扇區，並嘗試從最近的第一個盜取。 觸摸有點鎖問題;你仍然會使用自旋鎖，但使用完全不同的實現。這可能是CS目前最具專利的領域。 但是，您需要專門針對如此大規模的程序進行編程。或者你會簡單地使用它。沒有自動的「並行器」會爲你做。

Answer 6

制定Linux規模一直是一個長期和正在進行的項目。第一個具有多處理器能力的Linux內核具有保護整個內核的單個鎖（Big Kernel Lock，BKL），這很簡單，但是可擴展性有限。隨後，鎖定變得更加細緻，即有許多鎖（數千個），每個鎖只覆蓋一小部分數據。但是，可以採取多大程度的限制，因爲細粒度鎖定會變得複雜，並且鎖定開銷會削弱性能優勢，特別是考慮到大多數多CPU Linux系統的CPU數量相對較少。

另一件事是，內核儘可能使用per-cpu數據結構。這非常重要，因爲它避免了共享數據的緩存一致性問題，當然也沒有鎖定開銷。例如。每個CPU都運行自己的進程調度程序，只需要偶爾的全局同步。

此外，有些算法是考慮到可擴展性而選擇的。例如。一些主要讀取數據受Read-Copy-Update（RCU）保護，而不是傳統的互斥鎖;這允許讀者在併發更新期間繼續。

至於內存，Linux會盡力從運行進程的同一個NUMA節點分配內存。這爲應用程序提供了更好的內存帶寬和延遲。

Answer 7

最簡單的方法是將每個進程/線程綁定到幾個CPUS，然後只有那些CPU必須爭奪該線程上的鎖。很明顯，需要一些方法來移動線程以平衡負載，但在NUMA體系結構中，您必須儘可能地減少這種情況。

Answer 8

即使在雙核英特爾系統上，我也確信Linux已經可以使用本地posix線程處理「數千個」線程。 （Glibc和內核都需要配置來支持這個，但是，我相信現在大多數系統現在默認都是這樣的）。