現代作業系統之多處理機系統（上）

多處理機

共享存儲器多處理機是有兩個或更多的CPU全部共享通路的一個公用的RAM，運作在任何一個COu上的程式都看到一個普通的（通常是分頁）的虛拟位址空間。這個系統唯一特别的性質是，CPU可對存儲器字寫入某個值，然後讀會這個字，得到一個不同的值（因為另一個CPU改寫了它）。

最重要的部分，多處理機作業系統至少普通的作業系統。不過在某些領域它們有一些特殊的性質

多處理機硬體

所有多處理機都具有可通路全部存儲器的性質，而有些多處理機仍有一些其它的性質，即讀出每個存儲器字的速度是一樣快的。這種及其稱為UMA（統一存儲器通路）多處理機，而另一種則稱為NUMA（肺移植存儲器通路）多處理機。

基于總線的UMA多處理機體系結構

通過給每個CPU添加一個高速緩存（cache），這個高速緩存可以位于CPU晶片内部，CPU附近，處理器闆上或所有三種方式的組合。因為許多讀操作可以在高速緩存中得到滿足，總線流量被大大減少了，這樣系統就能支援更多的CPU。

每一個高速緩存塊或者被标記為隻讀（此時可以存在與多個告訴緩存中），或者被标記為讀寫（不能出現在多個高速緩存）。如果CPU試圖在一個或多個遠端高速緩存中寫入一個字，總線硬體檢測到寫，并把一個信号放到總線上通知所有其它的高速緩存。 如果某些其它高速緩存中有“髒”副本，它必須在處理寫之前把資料寫回存儲器或者它通過總線直接傳送到寫者上。高速緩存這一套規則被稱為高速緩存一緻性協定。

使用交叉開關的UMA多處理機

即使擁有最好的高速緩存，單個總線的使用還是把UMA多處理機的數量限制在16個到32個CPu，連接配接n個CPU到k個存儲器的最多簡單的電路是交叉開關。

交叉開關最好的一個特性是它是一個非阻塞網絡，即不會因有些交叉點或連線已經被占據而拒絕連接配接。

交叉開關最差的一個特性是，交叉點數量以n的平方速度上漲。無論如何對于中等規模的系統而言，交叉開關的設計是可用的。

使用多級交換的UMA多處理機

需要log2 n級，沒幾n／2個開關，總數為n/2 * log 2 你個開關。Omega網絡稱為全混洗，因為每一級信号的混合就像把一副牌分成兩半。

在消息通過交換網絡後，子產品号左端的值就不再需要了。它們可以用作應答消息找回傳回路徑。

若發生沖突，則其中一個必須等待。Mnerga網絡是一種阻塞網絡。

可以在多個莫垮肩均勻地分散對存儲器的引用。一種常用的奇數是把地位作為子產品好。然後連續的字會放在連續的子產品中。而連續字被放在不同子產品裡的存儲器系統稱作交叉存儲器系統。

NUMA多處理機

這種機器為所有CPu提供一個統一的位址空間，但是通路本地存儲器子產品快于通路遠端存儲器子產品。是以，在NUMA機器傻姑娘運作的所有UMA程式無須做任何改變，但是相同的時鐘速率下其性能不如UMA機器傻姑娘的性能。

在對于遠端存儲器的通路時間不被隐藏時（因為沒有高速緩存），系統被稱為NC-NUMA（無高速緩存NUMA）。在有一緻性高速緩存時，系統被稱為CC-NUMA（高速緩存一緻NUMA）

目前構造大小CC-NUMA多處理機最常見的方法是基于目錄的多處理機。其基本思想是，維護一個資料庫來記錄高速緩存行的位置機器狀态，當一個高速緩存被引用時，查詢資料庫找出高速緩存行的位置以及他是否感覺。必須配有專門的硬體來提速。

即使在一個所謂的“”共享存儲器多處理機，在下層仍然有大量的消息傳遞。

該設計有一個明顯的限制，級一行隻能被一個節點高速緩存。要想允許一行能夠在多個節點上被高速緩存，我們需要某種對所有行定位的方法。

多核晶片

雖然CPU可能共享或不共享高速緩存，但是它們必然共享記憶體。考慮到每個記憶體總是有唯一的值，這些記憶體是一緻的。特殊的硬體電路可以確定一個字同時出現在兩個或都給高速緩存中的情況下，當其中某個CPU修改來該字，所有其它高速緩存中的該字都會被自動地并且原子性删除以保證一緻，這個過程稱為窺探。

這樣設計的結果是多核晶片就相當于小的多處理機。實際上，多核晶片時常被稱為片級多處理機（CMP）

CPM跟更大的多處理機之間的一個差異是容錯。CPM的一個共享子產品失效可能導緻許多CPU同時出錯，而這樣的情況在傳統多處理機上是很少出現的。

除了所有核都是對等的對稱多核晶片，還有一類多核晶片被稱為片上系統。這些晶片含有一個或者多個主CPU，但同時海包含若幹個專用核，例如視訊和音頻解碼器，加密晶片或者網絡接口。這些和共同構成來完整的片上計算機系統。

多處理機作業系統類型

每個CPU有自己的作業系統

靜态地把存儲器劃分成和CPU一樣多的各個部分，為每個CPU提供其素有存儲器以及作業系統的各自私有副本。這樣的明顯優點是，允許所有CPu共享作業系統的代碼，而且隻需要提供資料的私有副本。

這樣要比有n個分離的計算機好得多，因為它允許所有機器共享一套磁盤和其它的IO裝置，他還允許靈活的共享存儲器。 程序之間可以高效通信，而且從作業系統的角度上看，每個CPu都有自己的作業系統非常自然。

該設計涉及4個方面（P302）

這個模型已經很少使用了

主從多處理機

在這種模型下，作業系統的一個副本機器資料表都在一個CPU上，所有的系統調用都重定向到CPU1上。如果有剩餘的CPu時間，還可以在CPU1上運作使用者程序。這種模型稱為主從模型。

當某個CPU空閑下來時，它向CPU1上的作業系統請求一個程序運作，并被配置設定一個程序。

這個模型的問題是，如果有很多CPU，那麼出CPU會稱為瓶頸。

對稱多處理機

在存儲器中有作業系統的一個副本，但任何CPU都可以運作它。在有系統調用時，進行系統調用但CPU陷入核心并處理系統調用。

當一個COU要運作作業系統時，它必須首先獲得互斥信号量。如果互斥信号量被鎖住。就得等待。按照這種方式，任何CPu都可以運作作業系統，但任意時刻隻有一個CPU可運作曹旭哦系統。

這樣就需要把作業系統分割成互不影響但臨界區。每個臨界區由其互斥信号量保護，是以一次隻能有一個CPU運作它。

大多數但現代多處理機都采用這種安排。為這類機器編寫作業系統但苦難不在于實際代碼，而在于如何将其劃分成可以由不同但CPU冰箱指向但臨界區而互不幹擾。

更進一步，要盡量避免死鎖。

理論上，所有但表都可以被賦予整數值，而且其所有但臨界區都應該以升序但方式獲得表。

多處理機同步

在多處理機中，禁止中斷的操作隻影響到完成禁止中斷操作的這個CPU，其它的CPU繼續運作并且可以通路鄰接表。是以需要合适和互斥協定。

任何實用的胡吃遍了核心都是一條特殊治療，該指令允許檢測一個存儲器字并以一種不可見的操作設定。

TSL指令必須首先鎖住總線，阻止其它CPU通路他，然後進行存儲器的讀寫通路，再解鎖總線。對總線枷鎖的典型做法是，先使用通風的總線協定請求總線，然後申明已擁有某些特定的總線線路，直到兩個周期全部完成。隻要始終保持擁有這一特性的總線線路，那麼其他CPu就不會得到總線的通路權。這個指令隻有在擁有必要的線路和使用它們的協定上才能實作。

如果正确的實作和使用TSL，就能保證互斥機制正常工作。但是這種互斥方法使用了自旋鎖。因為請求的CPU隻是在原地盡可能快得對鎖進行循環測試。

當兩者同時看到鎖是空閑的，于是同時也哦那個TSL指令去獲得他。隻有一個會成功，是以這裡沒有競争條件，因為真正的擷取是由TSL指令進行的，這條指令是原子性的。即使看到了鎖空閑，然後曆史用TSL指令試圖獲得它，也不能保證真正得到它。

另一個減少總線流量的方式是泗洪柱面的以太網二進制指數補償算法。不采用輪詢，而将一個延遲插入輪詢之間，每次延遲時間加倍。

一個更好的思想是，讓每個打算獲得互斥信号量的CPU都擁有歌詞用于測試的私有鎖變量。 給一個未能活動的鎖的CPu配置設定一個鎖變量并且把它負載等待該鎖的CPU連結清單的末端。在目前鎖的持有者退出臨界區時，它釋放連結清單中的首個CPU正在測試的似有所，然後在CPU進入臨界區

自旋和切換

有時對于提出請求的CPU而言，隻有等待，不存在其他等待的辦法。 然而，在另外一些情形中，卻存在着别的選擇。

自旋直接浪費了CPU周期，重複地測試鎖并不是搞笑的工作。不過，切換也浪費了CPU周期，因為必須儲存目前線程的狀态，必須獲得保護就緒連結清單的鎖，還必須選擇一個線程，必須裝入其狀态，并且使其開始運作。

通過事後算法可以對可行算法進行政策的基準評測标準，

一個未能獲得互斥信号量的線程先自旋一段時間，若時間超過某個阙值，則切換。

多處理器排程

線程是核心線程還是使用者線程是至關重要的，如果線程是由使用者空間庫維護，而對核心不肯叫。那麼核心不能排程線程。

而對核心線程，是核心選擇線程作為排程機關，線程叢書的程序對于排程算法隻有很少（乃至于沒有）的影響。

在多處理機上，排程是二維的，排程程式必須決定哪一個程序運作以及在哪一個CPU上運作。

另一個造成複雜性的因素是，在與嘔血系統中所有的線程是不相關的，而在另外一些系統中它們是承租的，同屬于一個應用并且協同曹旭哦，

分時

處理獨立線程的最低暗淡算法是，為就緒線程維護一個系統級的資料結構，它可能隻是一個連結清單，但更多但情況下可能是對應不同優先級但一個連結清單集合。

由所有CPU‘使用但單個排程資料結構分時共享這些CPU，就像還在一個但處理機系統中一樣。不過有量缺點——意識随着CPU數量增加引起但對排程資料結構對潛在競争，而是線程由于IO阻塞而因為對上下文切換對開銷。當線程時間片用完時，也可能會發生上下文切換。

為了避免這種情況，一些系統采用智能排程算法。獲得自旋鎖的程序設定一個程序範圍的标志表示它目前擁有自旋鎖，當釋放時，就清除該标志。這樣排程程式就不會停止擁有自旋鎖的線程，相反，還會給更多的時間。

有些多處理機使用了親和排程。其基本思想是，盡量使一個線程在前一次運作過的同一個CPU上運作。建立這種請合理的一個途徑是采用一種兩級排程算法。 通過試圖讓一個線程在其生命周期在同一個CPU上運作，高速緩存的親和力得到最大化。不過，如果某一個CPU沒有線程運作，就選擇另一個線程運作而不是空轉。

兩級排程算法有三個優點——将負載大緻平均的配置設定在可用的CPU傻姑娘；盡可能發揮了高速緩存親和力的有時；為每個CPU提供一個私有的就緒線程連結清單，使得對就緒線程連結清單的競争見到最小，因為試圖使用另一個CPU就緒線程連結清單的機會相對較小

空間共享

在多處理機系統中國年的一個算法是選擇需要CPU周期數最少的線程運作，次小的為候選線程。

在這個簡單的分區模型中國年，一個線程請求一定數量的CPu，然後全部得到或者等待全部等到。另一種方法是主動管理線程的并行度，關系并行度的一種途徑是使用一個中心伺服器，用它跟蹤哪些線程正在運作，哪些線程希望運作以及所需CPU的最小數量和最大數量

群排程

空間共享的一個明顯優點是消除多道程式設計，進而消除了上下文切換的開銷。但是統一的一個缺點是當CPU被阻塞或無事可做時時間被良妃了 。

而一個解決方法是群排程，它是協同排程發展的産物。

1. 把一組相關線程作為一個機關，級一個群，一起排程
2. 一個群中國年的所有成員在不同的分時CPU上同時運作
3. 群中的所有成員共同開始和結束其時間片

使群排程正确工作的關鍵是同步排程所有CPu，這一位這把時間劃分為離散的時間片。在每一個新的時間片開始時，所有CPU都重新排程，在每個CPU上都開始一個新的線程。在後續時間片開始是，另一個排程時間發生。在這之間，沒有排程行為。如果某個線程被阻塞，則保持CPU空轉，直到對應的時間片結束為止。

群排程的思想是，讓一個程序的所有線程一起運作，這樣，如果其中一個線程想另一個線程發送請求，接收方幾乎會立即得到消息，并且幾乎能偶立即應答