浙江工商大學(xué)計(jì)算機(jī)體系結(jié)構(gòu)多處理器和線程級(jí)并行

第4章多處理器和線程級(jí)并行對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)對(duì)稱式共享存儲(chǔ)器多處理器的性能分布式共享存儲(chǔ)器同步存儲(chǔ)器連貫性模型

4.1簡(jiǎn)介問題引出盡管單處理器仍在進(jìn)展，但多處理器自20世紀(jì)末開頭顯得越來越重要，由于開發(fā)ILP的空間正在削減，單處理器的進(jìn)展速度正在逐步變慢，使得多處理器唱主角的時(shí)代到來。

對(duì)多處理器的依靠還體現(xiàn)在以下方面：

對(duì)服務(wù)器及其性能的關(guān)注不斷增加、以數(shù)據(jù)為中心的應(yīng)用不斷增多、工業(yè)制造中批量復(fù)制比專門生產(chǎn)的方法更有優(yōu)勢(shì)，而多處理器正好有此優(yōu)勢(shì)4.1簡(jiǎn)介并行系統(tǒng)結(jié)構(gòu)分類依據(jù)數(shù)據(jù)流和指令流的并行度，將計(jì)算機(jī)分為四類

1、單指令流單數(shù)據(jù)流（SISD）:單處理器2、單指令流多數(shù)據(jù)流（SIMD）

同一條指令被多個(gè)使用不同數(shù)據(jù)流的多處理器執(zhí)行。通過將相同的操作以并行的方式應(yīng)用于數(shù)據(jù)的各個(gè)項(xiàng)來實(shí)現(xiàn)數(shù)據(jù)級(jí)的并行，每個(gè)處理器有自己的數(shù)據(jù)存儲(chǔ)器，但系統(tǒng)中有唯一的指令存儲(chǔ)器和掌握處理器，用來獵取和安排指令。4.1簡(jiǎn)介并行系統(tǒng)結(jié)構(gòu)分類依據(jù)數(shù)據(jù)流和指令流的并行度，將計(jì)算機(jī)分為四類

3、多指令流單數(shù)據(jù)流（MISD）

至今無(wú)此類型的商用機(jī)4、多指令流多數(shù)據(jù)流（MIMD）

每個(gè)處理器取自己的指令并對(duì)自己的數(shù)據(jù)進(jìn)行操作，多個(gè)線程按并行操作，計(jì)算機(jī)實(shí)現(xiàn)線程級(jí)并行，這種線程級(jí)并行比數(shù)據(jù)級(jí)并行更加靈敏，用途也更為廣泛。4.1簡(jiǎn)介并行系統(tǒng)結(jié)構(gòu)分類

MIMD的優(yōu)勢(shì)1、靈敏性強(qiáng)

在必要的軟件和硬件支持下，MIMD既能作為單用戶多處理器為單一應(yīng)用程序供應(yīng)高性能，又可作為同時(shí)運(yùn)行多個(gè)任務(wù)的多道程序多處理器系統(tǒng)使用，還可以供應(yīng)結(jié)合這兩種任務(wù)的應(yīng)用。2、能夠充分利用現(xiàn)有處理器的性價(jià)比優(yōu)勢(shì)

多核芯片通過復(fù)制方式可降低單處理器設(shè)計(jì)成本4.1簡(jiǎn)介幾個(gè)概念

多核：又稱為片內(nèi)多處理器或單芯片多處理器，在一個(gè)單獨(dú)的晶片上設(shè)計(jì)多個(gè)處理器，多個(gè)內(nèi)核共享一些資源如二級(jí)緩存、存儲(chǔ)器和I/O總線

進(jìn)程：是可以獨(dú)立運(yùn)行的一段代碼，進(jìn)程的狀態(tài)包含了處理器運(yùn)行這個(gè)進(jìn)程的全部必要信息。

線程：指運(yùn)行在不同處理器上的多個(gè)執(zhí)行過程，允許不同的地址空間上多個(gè)進(jìn)程同時(shí)執(zhí)行，也允許共享的地址空間上多個(gè)線程同時(shí)執(zhí)行。4.1簡(jiǎn)介MIMD分類依據(jù)處理器個(gè)數(shù)分為兩類，這兩類機(jī)器的存儲(chǔ)器組織方式和互聯(lián)測(cè)量不相同，依據(jù)存儲(chǔ)器組織方式而不是處理器構(gòu)成方式區(qū)分多處理器種類。1、集中式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)（圖4.1）

最多擁有幾十個(gè)處理器，但隨著處理器數(shù)目的增多，共享單個(gè)集中式存儲(chǔ)器方案前景不被看好.存儲(chǔ)器對(duì)每個(gè)處理器都是對(duì)等的，顧也稱為對(duì)稱多處理器系統(tǒng)，該系統(tǒng)是目前最流行的系統(tǒng)結(jié)構(gòu).4.1簡(jiǎn)介MIMD分類2、分布式存儲(chǔ)器系統(tǒng)結(jié)構(gòu)（圖4.2）

支持更多的處理器，存儲(chǔ)器依據(jù)分布式組織。系統(tǒng)基本結(jié)構(gòu)由多個(gè)獨(dú)立節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)包含處理器、存儲(chǔ)器、輸入輸出和互連網(wǎng)絡(luò)接口，各個(gè)節(jié)點(diǎn)通過互連網(wǎng)絡(luò)連接在一起。

分布式存儲(chǔ)器結(jié)構(gòu)優(yōu)點(diǎn)是縮短了本地存儲(chǔ)器訪問的時(shí)延，缺點(diǎn)是處理器間的數(shù)據(jù)通信變得更加簡(jiǎn)潔且時(shí)延也更大。4.1簡(jiǎn)介通信和存儲(chǔ)器系統(tǒng)結(jié)構(gòu)模型

依據(jù)處理器間傳遞數(shù)據(jù)的方法，有兩種不同的系統(tǒng)結(jié)構(gòu)：1、通過共享的地址空間進(jìn)行通信

共享存儲(chǔ)器指的是共享尋址空間，物理上分開的存儲(chǔ)器能夠作為規(guī)律上共享的地址空間進(jìn)行尋址，只要有正確的訪問權(quán)限，任何一個(gè)節(jié)點(diǎn)都能夠通過引用地址的方式訪問任意節(jié)點(diǎn)上的存儲(chǔ)器。4.1簡(jiǎn)介通信和存儲(chǔ)器系統(tǒng)結(jié)構(gòu)模型

依據(jù)處理器間傳遞數(shù)據(jù)的方法，有兩種不同的系統(tǒng)結(jié)構(gòu)：

2、通過私有的地址空間進(jìn)行通信

私有的地址空間在規(guī)律上是分散的，不能被遠(yuǎn)程的處理器尋址，每個(gè)處理器-存儲(chǔ)器模塊本質(zhì)上是一臺(tái)獨(dú)立的計(jì)算機(jī)。4.1簡(jiǎn)介并行處理遇到的挑戰(zhàn)

有兩個(gè)障礙使得并行處理遇到了挑戰(zhàn)，第一個(gè)障礙是程序可獲得的并行度是有限的；其次個(gè)障礙來自于通信相對(duì)較高的開銷。

這兩個(gè)障礙使得并行處理器難以得到較高的性價(jià)比（見P138-139頁(yè)例子）

并行度低和遠(yuǎn)程通信時(shí)延太長(zhǎng)是多處理器的最大挑戰(zhàn)，后面集中商量削減通信時(shí)延技術(shù)4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)

對(duì)稱式共享存儲(chǔ)器系統(tǒng)支持共享和私有數(shù)據(jù)的緩存，私有數(shù)據(jù)被單個(gè)處理器使用，共享數(shù)據(jù)被多個(gè)處理器使用，基本上是通過讀寫共享數(shù)據(jù)完成處理器之間的通信。

把私有數(shù)據(jù)緩存后，對(duì)該數(shù)據(jù)的訪問可以在Cache中進(jìn)行，共享數(shù)據(jù)可以在Cache中形成多個(gè)副本，這樣可以削減訪問時(shí)延和降低對(duì)存儲(chǔ)器帶寬的要求，但會(huì)產(chǎn)生Cache全都性問題。4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)處理器的Cache全都性

緩存共享帶來了新的問題，如果沒有其他的防范措施，會(huì)導(dǎo)致兩個(gè)處理器得到兩個(gè)不同的值（見圖4.3）.

如果在一個(gè)存儲(chǔ)器系統(tǒng)中讀取任何一個(gè)數(shù)據(jù)項(xiàng)的返回結(jié)果總是最近寫入的數(shù)值，那么就認(rèn)為該存儲(chǔ)器具有全都性。該定義包含了全都性和連貫性兩個(gè)方面，全都性定義了讀操作可以返回什么樣的數(shù)值，連貫性定義了寫入的數(shù)值什么時(shí)候才能被都操作返回4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)存儲(chǔ)器全都性滿意的條件1、處理器P對(duì)地址X的寫操作后面緊跟著P對(duì)X的讀操作，而且這次讀操作和寫操作之間沒有其他處理器對(duì)X的寫操作，讀操作總是返回P寫入的數(shù)值。

2、在其他處理器對(duì)X的寫操作后，處理器P對(duì)X進(jìn)行讀操作，這兩個(gè)操作之間有足夠的間隔而且沒有其他處理器對(duì)X進(jìn)行寫操作，讀操作返回的是寫入的數(shù)值。3、對(duì)同一個(gè)地址的寫操作是串行執(zhí)行的。4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)存儲(chǔ)器全都性滿意的條件

雖然上面三共性質(zhì)可以保證全都性，但寫入的數(shù)據(jù)什么時(shí)候可以讀取也是至關(guān)重要的。如果某個(gè)處理器對(duì)X的寫操作只領(lǐng)先其他處理器對(duì)X的讀操作很小一段時(shí)間，那么就無(wú)法保證該讀操作能返回寫入的數(shù)值，由于這一刻寫入的數(shù)據(jù)甚至可能還沒有被處理器發(fā)送出去。存儲(chǔ)器連貫性模型定義了寫入的數(shù)值在什么時(shí)候才可以被讀操作讀出的問題，此問題后面商量。4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)存儲(chǔ)器全都性和連貫性

全都性和連貫性是互補(bǔ)的，全都性定義了對(duì)同一個(gè)存儲(chǔ)器地址進(jìn)行的讀寫操作行為，而連貫性定義了關(guān)于訪問其他存儲(chǔ)器地址的讀寫操作。有兩個(gè)假設(shè)：一是直到全部處理器都看到了寫操作的結(jié)果后一個(gè)寫操作才算完成，并且后續(xù)的寫操作才可以開頭；二是處理器不會(huì)由于其他存儲(chǔ)器操作而轉(zhuǎn)變寫操作的挨次。4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)實(shí)施全都性的基本方案Cache在本地為那些被同時(shí)讀取的共享數(shù)據(jù)做了備份，全都性的Cache要為這些數(shù)據(jù)供應(yīng)副本，副本可以削減訪問時(shí)延。為了維護(hù)Cache全都性，小規(guī)模多處理器是通過在硬件上引入一個(gè)協(xié)議解決的

這個(gè)協(xié)議稱為Cache全都性協(xié)議，實(shí)現(xiàn)該協(xié)議的關(guān)鍵在于跟蹤全部數(shù)據(jù)塊的狀態(tài)，目前廣泛采納的有兩類協(xié)議，名目式和監(jiān)聽式。4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)實(shí)施全都性的基本方案

名目式：把物理存儲(chǔ)器的共享狀態(tài)存放在一個(gè)地點(diǎn)，稱之為名目。名目式全都性比監(jiān)聽式的實(shí)現(xiàn)開銷略高，但是可以用來擴(kuò)展更多的處理器。

監(jiān)聽式：每個(gè)含有物理存儲(chǔ)器中數(shù)據(jù)塊副本的Cache還要保留該數(shù)據(jù)塊共享狀態(tài)的副本，但是并不集中地保存狀態(tài)。Cache通常通過廣播的方式訪問，全部的Cache掌握器對(duì)總線進(jìn)行監(jiān)聽，來確定它們是否含有總線上懇求的數(shù)據(jù)塊的副本。4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)監(jiān)聽協(xié)議

寫無(wú)效協(xié)議：在處理器寫數(shù)據(jù)項(xiàng)之前保證該處理器能獨(dú)占地訪問數(shù)據(jù)項(xiàng)，在執(zhí)行寫操作時(shí)要使其他副本無(wú)效，該協(xié)議是目前在監(jiān)聽和名目方案中最常用的協(xié)議。

寫廣播協(xié)議：寫入數(shù)據(jù)項(xiàng)時(shí)更新該數(shù)據(jù)項(xiàng)全部的副本，該協(xié)議必須將全部的寫操作廣播給共享Cache，需要更大的帶寬。4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)基本實(shí)現(xiàn)技術(shù)

寫無(wú)效的基本思路

小規(guī)模多處理器中實(shí)現(xiàn)寫無(wú)效協(xié)議可使用總線或廣播的方式來完成無(wú)效操作。要實(shí)現(xiàn)無(wú)效操作，處理器只要取得總線掌握權(quán)然后在總線上廣播無(wú)效數(shù)據(jù)地址即可。全部的處理器都要不斷地監(jiān)聽總線來監(jiān)測(cè)地址。處理器要檢查各自的Cache中是否有總線上廣播的地址，如果有，則Cache中相應(yīng)的數(shù)據(jù)要置為無(wú)效。4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)基本實(shí)現(xiàn)技術(shù)

共享塊的操作

當(dāng)向一個(gè)共享塊執(zhí)行寫操作時(shí)，寫處理器必須獲得對(duì)總線的訪問權(quán)才能廣播無(wú)效性操作。若兩個(gè)處理器同時(shí)對(duì)一個(gè)共享塊執(zhí)行寫操作，其廣播無(wú)效的懇求會(huì)通過總線的仲裁實(shí)現(xiàn)串行化。全部的全都性方案都要求通過某種方式來實(shí)現(xiàn)對(duì)同一Cache塊的串行化訪問，包括對(duì)通信媒介的訪問和對(duì)其他共享結(jié)構(gòu)的訪問。

4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)基本實(shí)現(xiàn)技術(shù)Cache塊中的標(biāo)識(shí)位

利用Cache塊中的標(biāo)識(shí)位可以實(shí)現(xiàn)監(jiān)聽過程，其中數(shù)據(jù)塊的有效位使得實(shí)現(xiàn)無(wú)效操作更加容易。任何讀操作缺失都可以通過監(jiān)聽總線來直接解決；對(duì)于寫操作，需要知道其他Cache中是否存有該數(shù)據(jù)塊的副本，如果沒有其他副本，則不用將寫操作放到總線上，不發(fā)送寫操作能夠節(jié)省時(shí)間和帶寬。

4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)基本實(shí)現(xiàn)技術(shù)Cache塊中的標(biāo)識(shí)位

要跟蹤一個(gè)Cache數(shù)據(jù)塊是否能被共享，需要為每一個(gè)數(shù)據(jù)塊增加一個(gè)狀態(tài)位。增加數(shù)據(jù)塊是否被共享的狀態(tài)位之后，執(zhí)行寫操作時(shí)就可以據(jù)此來判定是否需要發(fā)送無(wú)效操作。當(dāng)對(duì)共享數(shù)據(jù)執(zhí)行寫操作時(shí)，Cache會(huì)在總線上發(fā)送一個(gè)無(wú)效操作并把該塊標(biāo)記為私有。擁有Cache塊唯一一個(gè)副本的處理器稱為該塊的全部者。

4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)基本實(shí)現(xiàn)技術(shù)Cache塊中的標(biāo)識(shí)位

當(dāng)發(fā)送無(wú)效操作時(shí)，全部者的Cache塊從共享狀態(tài)變成獨(dú)占狀態(tài)。稍后如果其他處理器懇求這個(gè)Cache塊，那么它會(huì)再次變成共享狀態(tài)。由于Cache對(duì)總線的監(jiān)聽同樣可以觀測(cè)到缺失的現(xiàn)象，所以它能夠發(fā)現(xiàn)其他處理器懇求獨(dú)占Cache塊的情況，并且會(huì)把狀態(tài)設(shè)置成共享。

4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)監(jiān)聽協(xié)議的局限性

隨著處理器數(shù)目的增加或是對(duì)存儲(chǔ)器要求的增加，系統(tǒng)集中式資源會(huì)變成瓶頸。在最簡(jiǎn)潔的基于總線的多處理器中，總線必須同時(shí)支持全都性通信和由于Cache導(dǎo)致的存儲(chǔ)器通信。同樣，對(duì)于只有一個(gè)存儲(chǔ)器部件，就必須處理全部的處理器懇求。隨著處理器的飛速進(jìn)展，單獨(dú)一條總線或單獨(dú)一個(gè)物理存儲(chǔ)器所能支持的處理器數(shù)量正在下降。

4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)監(jiān)聽協(xié)議的局限性

為了增加處理器和存儲(chǔ)器之間的通信帶寬，設(shè)計(jì)者使用多種總線以及各種互聯(lián)網(wǎng)絡(luò)，像交叉開關(guān)或小型點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)。在這樣的設(shè)計(jì)中，存儲(chǔ)器系統(tǒng)可以被配置成多個(gè)物理組，以便在保持均勻存儲(chǔ)器訪問時(shí)間的情況下增加存儲(chǔ)器有效帶寬，參照?qǐng)D4.8，它是共享式存儲(chǔ)器和分布式存儲(chǔ)器的結(jié)合。

4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)實(shí)現(xiàn)監(jiān)聽Cache全都性

實(shí)現(xiàn)監(jiān)聽全都性協(xié)議的主要簡(jiǎn)潔性是在任何最新的多處理器中，寫缺失或更新缺失都不是原子操作。監(jiān)測(cè)寫缺失或更新缺失、與其他處理器和存儲(chǔ)器的通信、對(duì)于寫缺失得到的最新值、保證每個(gè)無(wú)效操作都被處理以及更新Cache，這些步驟均無(wú)法在一個(gè)單循環(huán)中完成。

4.2對(duì)稱式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)實(shí)現(xiàn)監(jiān)聽Cache全都性

在簡(jiǎn)潔單總線系統(tǒng)中，可以通過首先競(jìng)爭(zhēng)總線和直到操作完成才釋放總線的方式將這些步驟變成有效的原子操作。

在沒有總線的系統(tǒng)中，必須找到發(fā)生缺失時(shí)將這些步驟變成原子操作的其他方法。在監(jiān)聽系統(tǒng)中，保證競(jìng)爭(zhēng)只有一個(gè)成功者的方法是對(duì)全部的缺失使用廣播來實(shí)現(xiàn)，簡(jiǎn)略可參照附錄H中的細(xì)節(jié)。

4.3對(duì)稱共享存儲(chǔ)器多處理器性能Cache缺失的影響因素

Cache的總體性能由單處理器的Cache缺失通信和由通信造成的數(shù)據(jù)傳輸共同決定，后者會(huì)造成無(wú)效的和隨之而來的Cache缺失。轉(zhuǎn)變處理器個(gè)數(shù)、Cache大小、塊大小都會(huì)以不同方式影響缺失率。

4.3對(duì)稱共享存儲(chǔ)器多處理器性能幾個(gè)概念由處理器間通信引起的缺失，稱為全都性缺失，分為兩種：1、真共享缺失

由Cache全都性機(jī)制下的數(shù)據(jù)通信產(chǎn)生。處理器對(duì)共享Cache塊的第一次寫操作引發(fā)無(wú)效大事，從而獲得該塊的獨(dú)占權(quán)。除此之外，另一個(gè)處理器試圖從該Cache塊中讀一個(gè)已修改的字時(shí)，會(huì)產(chǎn)生一個(gè)缺失，該缺失由處理器間共享數(shù)據(jù)引起，稱為真共享缺失。

4.3對(duì)稱共享存儲(chǔ)器多處理器性能幾個(gè)概念

2、假共享

是由于使用基于無(wú)效的全都性算法引起的。該算法利用了數(shù)據(jù)塊的有效位，而這個(gè)有效位每個(gè)數(shù)據(jù)塊只有一個(gè)。對(duì)數(shù)據(jù)塊的某些字執(zhí)行寫操作而導(dǎo)致該數(shù)據(jù)塊被置為無(wú)效后，再對(duì)該塊中的另一些字執(zhí)行寫操作時(shí)，就會(huì)發(fā)生假共享現(xiàn)象。在假共享缺失中，共享的是數(shù)據(jù)塊，并沒有共享單個(gè)值。

4.3對(duì)稱共享存儲(chǔ)器多處理器性能幾個(gè)概念

2、假共享

如果在寫操作中將其他處理器中的數(shù)據(jù)副本置為無(wú)效之后，這些處理器再次使用已經(jīng)寫入的數(shù)據(jù)，那么該調(diào)用是一個(gè)真共享調(diào)用并會(huì)導(dǎo)致缺失，而缺失與塊的大小或字的位置無(wú)關(guān)。然而，如果寫入的值和讀取的字不相同，那么無(wú)效并不會(huì)引發(fā)傳輸新數(shù)值的操作，而只是導(dǎo)致多余的Cache缺失，該缺失為假共享缺失。

4.3對(duì)稱共享存儲(chǔ)器多處理器性能例子：假如字x1和x2處于同一塊Cache中，這個(gè)Cache塊在CacheP1和P2中均為共享狀態(tài)。P1和P2兩個(gè)Cache在這之前已經(jīng)讀入了x1和x2。假如有如下大事序列，請(qǐng)區(qū)分每個(gè)缺失畢竟是真共享Cache還是假共享Cache，或是命中。如果數(shù)據(jù)塊大小是一個(gè)字，任何能夠發(fā)生的缺失就都是真共享缺失了。4.3對(duì)稱共享存儲(chǔ)器多處理器性能

-------------------------------

時(shí)序P1P21寫x12讀x23寫x14寫x25讀x2

-------------------------------答案：1真

2假3假4假5真4.3對(duì)稱共享存儲(chǔ)器多處理器性能多道程序和操作系統(tǒng)負(fù)載負(fù)載分為3個(gè)不同階段：編譯基本測(cè)試程序，包括子計(jì)算活動(dòng)；在庫(kù)里建立對(duì)象文件；移除對(duì)象文件。最后一個(gè)階段完全由I/O掌握而且只有兩個(gè)活動(dòng)的進(jìn)程，每個(gè)負(fù)責(zé)一個(gè)運(yùn)行。在中間階段，主要是依靠I/O，處理器大部分時(shí)間是空閑的。

多道程序負(fù)載至少對(duì)于操作系統(tǒng)來講有明顯的指令Cache性能損失。不論Cache的大小是多少，用戶級(jí)指令Cache缺失大約為操作系統(tǒng)速率的1/6。4.3對(duì)稱共享存儲(chǔ)器多處理器性能多道程序和操作系統(tǒng)負(fù)載的性能轉(zhuǎn)變Cache容量和塊大小對(duì)多道程序工作負(fù)載的Cache性能產(chǎn)生影響。

操作系統(tǒng)的行為比用戶進(jìn)程會(huì)導(dǎo)致更多的Cache缺失，除了操作系統(tǒng)有更大的代碼容量和局限性缺失緣由外，還有兩個(gè)緣由：第一，內(nèi)核把頁(yè)安排給用戶之前首先要初始化全部頁(yè)，這極大地增加了內(nèi)核的強(qiáng)制性缺失率；其次，內(nèi)核實(shí)際上共享數(shù)據(jù)，因此不能忽視全都性缺失率。用戶進(jìn)程只有被調(diào)度到另一個(gè)處理器上才會(huì)引起缺失，這部分比例小。4.3對(duì)稱共享存儲(chǔ)器多處理器性能多道程序和操作系統(tǒng)負(fù)載的性能

圖4.16給出了數(shù)據(jù)缺失率與數(shù)據(jù)Cache大小的比率。增加數(shù)據(jù)Cache的大小對(duì)用戶缺失率的影響比內(nèi)核缺失率的影響要大。增加數(shù)據(jù)塊的大小對(duì)缺失率有好的效果，由于大部分缺失屬于容量缺失，這種缺失可以通過增大數(shù)據(jù)塊大小得到改進(jìn)。4.3對(duì)稱共享存儲(chǔ)器多處理器性能多道程序和操作系統(tǒng)負(fù)載的性能對(duì)于多道程序工作負(fù)載，操作系統(tǒng)對(duì)存儲(chǔ)器系統(tǒng)的要求是格外苛刻的。如果工作負(fù)載中包含了更多的操作系統(tǒng)或類操作系統(tǒng)活動(dòng)，那么要想構(gòu)建一個(gè)能力足夠大的存儲(chǔ)器系統(tǒng)是格外困難的。要改善性能也許可以通過更好的編程環(huán)境或編程幫助，使得操作系統(tǒng)更加關(guān)注Cache的活動(dòng)。例如，對(duì)于來自不同系統(tǒng)調(diào)用發(fā)出的懇求，操作系統(tǒng)會(huì)重用存儲(chǔ)器，這和過程調(diào)用中的堆棧位置重用情況類似。4.4分布式存儲(chǔ)器

通過安排存儲(chǔ)器的方式可以增加存儲(chǔ)器帶寬和互連帶寬，這種方式可以將本地存儲(chǔ)器通信和遠(yuǎn)程存儲(chǔ)器通信飛快分開，這就削減了對(duì)存儲(chǔ)器系統(tǒng)和互連網(wǎng)絡(luò)的帶寬要求。4.4分布式存儲(chǔ)器名目協(xié)議

名目協(xié)議是基于監(jiān)聽全都性協(xié)議的一種替代方式，該協(xié)議保存每個(gè)Cache數(shù)據(jù)塊的狀態(tài)。名目中的信息包括哪個(gè)Cache擁有該塊的副本，是否處于臟狀態(tài)等等，名目協(xié)議同樣可以用于集中式共享存儲(chǔ)器中削減帶寬要求。4.4分布式存儲(chǔ)器名目協(xié)議

最簡(jiǎn)潔的名目協(xié)議的實(shí)現(xiàn)機(jī)制是在名目中給每個(gè)存儲(chǔ)器數(shù)據(jù)塊安排一個(gè)條目，在這樣的設(shè)計(jì)中，信息個(gè)數(shù)與存儲(chǔ)器中塊的個(gè)數(shù)和處理器個(gè)數(shù)的乘積成正比。這對(duì)于處理器數(shù)目小于200的處理器系統(tǒng)來說不成問題，由于名目的開銷還可以接受。4.4分布式存儲(chǔ)器名目協(xié)議

為了防止名目成為瓶頸，需要使名目隨存儲(chǔ)器分布，這樣訪問不同的名目就要到不同的地點(diǎn)，正如要在不同的存儲(chǔ)器上執(zhí)行不同的存儲(chǔ)器懇求一樣。分布名目使得數(shù)據(jù)塊的共享狀態(tài)總是位于一個(gè)已知的地點(diǎn)，正是這個(gè)特性避開了全都性協(xié)議中的廣播。圖4.19給出了每個(gè)節(jié)點(diǎn)上帶聞名目的分布式存儲(chǔ)器多處理器系統(tǒng)。4.4分布式存儲(chǔ)器基于名目的Cache全都性協(xié)議名目協(xié)議必須實(shí)現(xiàn)兩個(gè)基本操作：處理讀缺失和處理共享未修改Cache塊的寫操作。為了實(shí)現(xiàn)這些操作，名目必須跟蹤每個(gè)Cache塊的狀態(tài)，可能消滅的狀態(tài)如下：

共享：一個(gè)或多個(gè)處理器擁有Cache數(shù)據(jù)塊，并且存儲(chǔ)器中的數(shù)值也是最新的。

未緩存：沒有任何一個(gè)處理器含有該數(shù)據(jù)塊副本

修改：只有一個(gè)處理器擁有該Cache塊的副本并且對(duì)該塊執(zhí)行寫操作，存儲(chǔ)器中的副本是無(wú)效的。4.4分布式存儲(chǔ)器基于名目的Cache全都性協(xié)議除了跟蹤C(jī)ache中每個(gè)塊的狀態(tài)外，還必須跟蹤擁有共享數(shù)據(jù)塊副本的處理器，由于執(zhí)行寫操作后這些處理器中的副本要設(shè)置成無(wú)效狀態(tài)。實(shí)現(xiàn)這一功能最簡(jiǎn)潔的方法是為每個(gè)存儲(chǔ)器保留一個(gè)位向量。當(dāng)塊處于共享狀態(tài)時(shí)，向量的每一位表示所對(duì)應(yīng)的處理器是否擁有該塊的副本。當(dāng)塊處于獨(dú)占狀態(tài)時(shí)，可以利用位向量來跟蹤塊的全部者。4.4分布式存儲(chǔ)器基于名目的Cache全都性協(xié)議

每個(gè)Cache上的狀態(tài)及轉(zhuǎn)換與監(jiān)聽協(xié)議中的相同，只是轉(zhuǎn)換中執(zhí)行的動(dòng)作稍有不同。數(shù)據(jù)項(xiàng)的獨(dú)占副本的無(wú)效化和定位過程是不同的，由于兩者都包括懇求節(jié)點(diǎn)和名目間以及名目和一個(gè)或多個(gè)遠(yuǎn)程節(jié)點(diǎn)間的通信。在監(jiān)聽協(xié)議中，這兩步是通過向全部節(jié)點(diǎn)廣播的方式結(jié)合在一起的。4.4分布式存儲(chǔ)器基于名目的Cache全都性協(xié)議幾個(gè)概念：本地節(jié)點(diǎn)、主節(jié)點(diǎn)和遠(yuǎn)程節(jié)點(diǎn)

本地節(jié)點(diǎn)：是指產(chǎn)生懇求的節(jié)點(diǎn)

主節(jié)點(diǎn)：是指存儲(chǔ)地址和名目條目所在的節(jié)點(diǎn)

遠(yuǎn)程節(jié)點(diǎn)：是指擁有Cahce塊副本的節(jié)點(diǎn)，該副本可能處于共享狀態(tài)，也可能處于獨(dú)占狀態(tài)（這時(shí)是唯一的副本），遠(yuǎn)程節(jié)點(diǎn)可以和本地節(jié)點(diǎn)或主節(jié)點(diǎn)相同。4.4分布式存儲(chǔ)器基于名目的Cache全都性協(xié)議

實(shí)際多處理器中使用的名目協(xié)議需要優(yōu)化，發(fā)生對(duì)獨(dú)占狀態(tài)數(shù)據(jù)塊的讀缺失或?qū)懭笔r(shí)，該塊首先被送到主節(jié)點(diǎn)的名目，在那里存入主存儲(chǔ)器中并被送到發(fā)出懇求的節(jié)點(diǎn)上，商用處理器系統(tǒng)中使用的很多協(xié)議把數(shù)據(jù)從全部者節(jié)點(diǎn)直接送到懇求節(jié)點(diǎn)上，這增加了協(xié)議的簡(jiǎn)潔性，更多內(nèi)容參照附錄H。4.5同步概述

同步是通過用戶層的軟件例程來構(gòu)造的，這些例程要使用硬件供應(yīng)的同步指令，關(guān)鍵是要在硬件上支持一條不行中斷的指令或指令序列，該指令或序列能以原子操作的方式取回?cái)?shù)據(jù)并修改其值。本節(jié)關(guān)注鎖和解鎖同步操作的實(shí)現(xiàn)，鎖和解鎖可以被直接用來實(shí)現(xiàn)互斥機(jī)制，以及實(shí)現(xiàn)更加簡(jiǎn)潔的同步機(jī)制4.5同步基本硬件原語(yǔ)

原子互換：是一個(gè)典型的構(gòu)建同步原語(yǔ)的操作，它將一個(gè)寄存器中的值和一個(gè)存儲(chǔ)器中的值進(jìn)行互換，互換是不行割裂的，且兩個(gè)同時(shí)進(jìn)行的互換將由寫串行機(jī)制進(jìn)行排序，這種方式使得兩個(gè)試圖設(shè)置同步變量的處理器不行能同時(shí)完成設(shè)置。4.5同步基本硬件原語(yǔ)

構(gòu)造同步操作可以先構(gòu)造一個(gè)簡(jiǎn)潔的鎖，其中0表示該鎖可以占用，1表示不能占用。如果處理器想占用該鎖，可以通過將寄存器中的1與該鎖在存儲(chǔ)器中的值互換來實(shí)現(xiàn)。如果有其他處理器占用了該鎖，返回結(jié)果為1，否則為0。如果返回結(jié)果為0，鎖的值被設(shè)置成1，在處理器將鎖釋放之前，其他處理器無(wú)法占用這個(gè)鎖。4.5同步基本硬件原語(yǔ)其他一些原子性原語(yǔ)也可實(shí)現(xiàn)同步

測(cè)試并置位：首先對(duì)值進(jìn)行檢測(cè)，如果該值通過了檢測(cè)則執(zhí)行設(shè)置，例如可以定義一個(gè)測(cè)試0和設(shè)置1的操作，其使用方法與原子互換類似。

取并增加：返回存儲(chǔ)器中的值，并以原子操作的方式使存儲(chǔ)器中的值加1，如果用0表示同步變量未被使用，就可以像使用互換一樣使用取并增加操作4.5同步用全都性實(shí)現(xiàn)鎖

有了原子操作就可以利用多處理器的全都性機(jī)制來實(shí)現(xiàn)自旋鎖（即處理器通過循環(huán)來不停嘗試獲得鎖，直到成功為止）。有兩種情況會(huì)用到自旋鎖，1、程序員要求占用鎖的時(shí)間很短；2、程序員要求鎖在可用時(shí)，鎖定過程的時(shí)延較低。自旋鎖的代價(jià)是要堵塞處理器并始終循環(huán)等待鎖被釋放。4.5同步用全都性實(shí)現(xiàn)鎖

若不存在Cache全都性問題，可用簡(jiǎn)潔方法在存儲(chǔ)器中保存鎖變量。處理器可以不停地使用原子操作嘗試占用鎖，或者說互換，以及檢測(cè)鎖是否可用。要釋放鎖，處理器只要將0值存儲(chǔ)到鎖中即可。

若多處理器支持Cache全都性，就可以利用全都性協(xié)議把鎖放入Cache來保證其全都性。4.6存儲(chǔ)器連貫性模型

存儲(chǔ)器連貫性是指一個(gè)被處理器修改過的值，在何時(shí)可以被另一個(gè)處理器訪問，或者說一個(gè)處理器應(yīng)該以何種次序來查看被別的處理器寫過的數(shù)據(jù)值，才能保證連貫性。由于查看的方式是讀操作，所以上述問題變?yōu)椋涸诓煌幚砥鲗?duì)不同單元進(jìn)行讀操作和寫操作時(shí)，應(yīng)加上何種屬性才能確保連貫性。4.6存儲(chǔ)器連貫性模型挨次連貫性模型

該模型是存儲(chǔ)器連貫性最直接的模型，它要求程序每次執(zhí)行的結(jié)果都是一樣的。實(shí)現(xiàn)挨次連貫性最簡(jiǎn)潔的