計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)-多處理機(jī)課件

1、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)多處理機(jī)課件計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)多處理機(jī)課件提 示本章內(nèi)容2 之 2 因?yàn)槎嗵幚頇C(jī)系統(tǒng)結(jié)構(gòu)是一個(gè)巨大而多樣的領(lǐng)域，其中很多領(lǐng)域仍處于不成熟的階段，所以本課程集中于多處理機(jī)設(shè)計(jì)的主流進(jìn)行討論：由少量到中等數(shù)量的處理機(jī)（128）組成的機(jī)器。提 示本章內(nèi)容2 之 2 因?yàn)槎嗵幚頇C(jī)系統(tǒng)結(jié)構(gòu)多處理機(jī)結(jié)構(gòu)本章內(nèi)容 根據(jù)存儲(chǔ)器的組織形式，多處理機(jī)有兩種基本結(jié)構(gòu)：集中式共享存儲(chǔ)器結(jié)構(gòu)分布式共享存儲(chǔ)器結(jié)構(gòu)多處理機(jī)結(jié)構(gòu)本章內(nèi)容 根據(jù)存儲(chǔ)器的組織形式，多處集中式共享存儲(chǔ)器結(jié)構(gòu)多處理機(jī)本章內(nèi)容多處理機(jī)結(jié)構(gòu) 存儲(chǔ)器是一個(gè)獨(dú)立的子系統(tǒng)，通過互連網(wǎng)絡(luò)（交叉開關(guān)/總線）為所有的處理機(jī)共享，任何兩臺(tái)處理機(jī)都可以通過訪問

2、共享的存儲(chǔ)器單元實(shí)現(xiàn)通信。 由于共享存儲(chǔ)器對(duì)每個(gè)處理機(jī)都是對(duì)稱關(guān)系，而且所有處理機(jī)對(duì)共享存儲(chǔ)器的訪問時(shí)間都相同，這種結(jié)構(gòu)的多處理機(jī)也稱為對(duì)稱多處理機(jī)（SMP）和均勻存儲(chǔ)器存取（UMA）。2 之 1集中式共享存儲(chǔ)器結(jié)構(gòu)多處理機(jī)本章內(nèi)容多處理機(jī)結(jié)構(gòu) 圖 示本章內(nèi)容多處理機(jī)結(jié)構(gòu)2 之 2處理機(jī)1級(jí)/多級(jí)Cache存儲(chǔ)器處理機(jī)1級(jí)/多級(jí)Cache處理機(jī)1級(jí)/多級(jí)Cache處理機(jī)1級(jí)/多級(jí)CacheI/O系統(tǒng)圖 示本章內(nèi)容多處理機(jī)結(jié)構(gòu)2 之 2處理機(jī)1級(jí)/多級(jí)存分布式共享存儲(chǔ)器結(jié)構(gòu)(DSM)多處理機(jī)本章內(nèi)容多處理機(jī)結(jié)構(gòu) 存儲(chǔ)器分布在各處理機(jī)中，但這些存儲(chǔ)器在邏輯上統(tǒng)一編址，形成一個(gè)為所有處理機(jī)共享的虛擬

3、共享存儲(chǔ)器。處理機(jī)之間信息交換的物理實(shí)現(xiàn)仍然是通過點(diǎn)-點(diǎn)的通信。 由于任何一個(gè)處理機(jī)訪問本地存儲(chǔ)器都較快，但是訪問分布在其他處理機(jī)的遠(yuǎn)程存儲(chǔ)器則較慢，這種結(jié)構(gòu)的多處理機(jī)也稱為非均勻存儲(chǔ)器存?。∟UMA）。3 之 1分布式共享存儲(chǔ)器結(jié)構(gòu)(DSM)多處理機(jī)本章內(nèi)容多處理機(jī)結(jié)圖 示本章內(nèi)容多處理機(jī)結(jié)構(gòu)3 之 2處理機(jī)+Cache存儲(chǔ)器互 連 網(wǎng) 絡(luò)I/O處理機(jī)+Cache存儲(chǔ)器I/O處理機(jī)+Cache存儲(chǔ)器I/O處理機(jī)+Cache存儲(chǔ)器I/O處理機(jī)+Cache存儲(chǔ)器I/O處理機(jī)+Cache存儲(chǔ)器I/O圖 示本章內(nèi)容多處理機(jī)結(jié)構(gòu)3 之 2處理機(jī)存儲(chǔ)器互 連比 較本章內(nèi)容多處理機(jī)結(jié)構(gòu)3 之 3集中共享分

4、布共享處理機(jī)數(shù)301000限制結(jié)點(diǎn)間間距和延遲數(shù)據(jù)局部性比 較本章內(nèi)容多處理機(jī)結(jié)構(gòu)3 之 3集中共享分布共享處一致性問題本章內(nèi)容Cache一致性存儲(chǔ)一致性一致性問題本章內(nèi)容Cache一致性Cache一致性本章內(nèi)容一致性問題問題現(xiàn)象原因分析解決方法Cache一致性本章內(nèi)容一致性問題問題現(xiàn)象問題現(xiàn)象本章內(nèi)容一致性問題Cache一致性 Cache一致性是指私有Cache中共享數(shù)據(jù)的副本和共享存儲(chǔ)器中共享數(shù)據(jù)之間的一致性。u:7u:?P1C u:5主存 CCP2P3特征 多處理器對(duì)相同存儲(chǔ)單元的操作引起的一致性。u:5u:5u:7問題現(xiàn)象本章內(nèi)容一致性問題Cache一致性 原因分析本章內(nèi)容一致性問題C

5、ache一致性共享可寫數(shù)據(jù)引起的不一致性進(jìn)程遷移引起的數(shù)據(jù)不一致性I/O傳輸造成的數(shù)據(jù)不一致性原因分析本章內(nèi)容一致性問題Cache一致性共享可寫數(shù)共享可寫數(shù)據(jù)引起的不一致性 不同處理器對(duì)相同單元在各自Cache的拷貝的異步寫操作。本章內(nèi)容一致性問題Cache一致性原因分析P1XXP2X處理機(jī)Cache共享存儲(chǔ)器更新之前P1XXP2X更新之后（寫通過）P1XXP2X更新之后（寫回）共享可寫數(shù)據(jù)引起的不一致性 不同處理器對(duì)相同單元進(jìn)程遷移引起的數(shù)據(jù)不一致性本章內(nèi)容一致性問題Cache一致性原因分析 多處理器中的進(jìn)程遷移，而又不互相通報(bào)。P1XXP2X處理機(jī)Cache共享存儲(chǔ)器初始狀態(tài)P1XXP2X

6、遷移之前（寫通過）進(jìn)程P1XXP2X遷移之后（寫通過）進(jìn)程進(jìn)程進(jìn)程遷移引起的數(shù)據(jù)不一致性本章內(nèi)容一致性問題CachI/O傳輸造成的數(shù)據(jù)不一致性本章內(nèi)容一致性問題Cache一致性原因分析繞過Cache拷貝擁有者的I/O操作。P1XX處理機(jī)Cache共享存儲(chǔ)器I/O前P2XI/OP1XXI/O后XP2XP1XXI/O后（寫回）XP2X共享存儲(chǔ)器輸入共享存儲(chǔ)器輸出I/O傳輸造成的數(shù)據(jù)不一致性本章內(nèi)容一致性問題Cac解決方法前兩種原因監(jiān)聽法目錄法第三種原因禁止法刷新法本章內(nèi)容一致性問題Cache一致性解決方法前兩種原因第三種原因本章內(nèi)容一致性問題Cac監(jiān)聽協(xié)議基本原理具體實(shí)現(xiàn)采用寫通過策略的Cache

7、采用寫回策略的Cache寫一次（Write-Once）協(xié)議本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議基本原理本章內(nèi)容一致性問題Cache一致性基本原理本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議4 之 1 本方法只適用于采用基于總線互連結(jié)構(gòu)的系統(tǒng)中，由于系統(tǒng)中每個(gè)處理機(jī)都能覺察到存儲(chǔ)器系統(tǒng)正在進(jìn)行的活動(dòng)，在某個(gè)活動(dòng)破壞了Cache的一致性時(shí)， Cache控制器將采取相應(yīng)的動(dòng)作使有關(guān)的拷貝無效或更新?；驹肀菊聝?nèi)容一致性問題Cache一致性解決方寫無效/寫更新本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議4 之 2 使用監(jiān)聽協(xié)議來保持Cache一致性有兩種方法：方法一：寫無效

8、（Write Invalidate）策略 在本地Cache的數(shù)據(jù)塊修改時(shí)使遠(yuǎn)程數(shù)據(jù)塊都無效。方法二：寫更新（Write Update）策略 在本地Cache數(shù)據(jù)塊修改時(shí)通過總線把新的數(shù)據(jù)塊廣播給含該塊的所有其他Cache。提示：采用寫無效或?qū)懜虏呗耘cCache采用寫回還是寫通過方式無關(guān)。寫無效/寫更新本章內(nèi)容一致性問題Cache一致性圖 示本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議4 之 3P1XXP2X處理機(jī)Cache共享存儲(chǔ)器更新之前P1XIP2X更新之后(Write-Invalidate)P1XXP2X更新之后(Write-Update)圖 示本章內(nèi)容一致性問題Cache一致性

9、解決方應(yīng)用情況本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議4 之 4 由于寫更新法在本地Cache修改時(shí)需要通過總線把修改過的數(shù)據(jù)塊的內(nèi)容廣播給所有含該數(shù)據(jù)塊的其他Cache，增加了總線的負(fù)擔(dān)，所以在一般的應(yīng)用系統(tǒng)中，極少使用寫更新法。 本方法實(shí)現(xiàn)簡(jiǎn)單，但只適用于總線式互連的多處理機(jī)，而且寫無效法和寫更新法都要占用總線不少時(shí)間，因此只能用于機(jī)數(shù)少的多處理機(jī)中。應(yīng)用情況本章內(nèi)容一致性問題Cache一致性解決方采用寫通過策略的Cache本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議 Cache數(shù)據(jù)塊有兩種狀態(tài): 有效和無效，有效狀態(tài)表示該數(shù)據(jù)塊內(nèi)容正確，無效狀態(tài)表示該數(shù)據(jù)塊內(nèi)容已“過時(shí)”

10、或不在Cache中。RL、WL表示本地處理機(jī)對(duì)Cache的讀和寫操作，RR、WR表示遠(yuǎn)程處理機(jī)對(duì)Cache中相同內(nèi)容數(shù)據(jù)的讀和寫操作。采用寫通過策略的Cache本章內(nèi)容一致性問題Cach采用寫回策略的Cache本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議2 之 1采用寫回策略的Cache本章內(nèi)容一致性問題Cache采用寫回策略的Cache Cache數(shù)據(jù)塊有三種狀態(tài): 只讀、讀寫和無效。只讀狀態(tài)表示整個(gè)系統(tǒng)中有多個(gè)數(shù)據(jù)塊拷貝是正確的；讀寫狀態(tài)表示數(shù)據(jù)塊至少被修改過一次，存儲(chǔ)器中相應(yīng)數(shù)據(jù)塊還沒有修改，在整個(gè)系統(tǒng)中只有一個(gè)數(shù)據(jù)塊拷貝是正確的；無效狀態(tài)表示該數(shù)據(jù)塊內(nèi)容已“過時(shí)”或不在Cache

11、中。 RL、WL表示本地處理機(jī)對(duì)Cache的讀和寫操作，RR、WR表示遠(yuǎn)程處理機(jī)對(duì)Cache中相同內(nèi)容數(shù)據(jù)的讀和寫操作。本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議2 之 2采用寫回策略的Cache Cache數(shù)據(jù)塊有三種狀態(tài)寫一次協(xié)議本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議4 之 1 本方法為了降低總線流量，結(jié)合了寫回和寫通過策略的優(yōu)點(diǎn)。在第一次寫Cache采用寫通過策略，以后寫Cache采用寫回策略，此時(shí)整個(gè)系統(tǒng)中只有一份正確的拷貝。寫一次協(xié)議本章內(nèi)容一致性問題Cache一致性解決寫一次協(xié)議本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議4 之 2RR寫一次協(xié)議本章內(nèi)容一

12、致性問題Cache一致性解決寫一次協(xié)議本章內(nèi)容一致性問題Cache一致性解決方法監(jiān)聽協(xié)議4 之 3 Cache數(shù)據(jù)塊有四種狀態(tài): 有效、保留、重寫和無效。有效狀態(tài)表示整個(gè)系統(tǒng)中有多個(gè)數(shù)據(jù)塊拷貝是正確的；保留狀態(tài)表示數(shù)據(jù)從存儲(chǔ)器讀入Cache后只被寫過一次，Cache和存儲(chǔ)器中拷貝都正確；重寫狀態(tài)表示Cache中的數(shù)據(jù)塊被寫過多次，而且是唯一正確的數(shù)據(jù)塊；無效狀態(tài)表示該數(shù)據(jù)塊內(nèi)容已“過時(shí)”或不在Cache中。 RL、WL表示本地處理機(jī)對(duì)Cache的讀和寫操作，RR、WR表示遠(yuǎn)程處理機(jī)對(duì)Cache中相同內(nèi)容數(shù)據(jù)的讀和寫操作。寫一次協(xié)議本章內(nèi)容一致性問題Cache一致性解決寫一次協(xié)議本章內(nèi)容一致性問

13、題Cache一致性解決方法監(jiān)聽協(xié)議4 之 4 主要優(yōu)點(diǎn)： 減少大量的無效操作，提高了總線效率。 主要缺點(diǎn)： 當(dāng)主存儲(chǔ)器的內(nèi)容無效時(shí),讀缺失引起的總線讀操作必須禁止主存儲(chǔ)器的操作（以免造成總線沖突），而大多數(shù)總線不支持這種操作。IEEE Futurebus+總線支持該操作。寫一次協(xié)議本章內(nèi)容一致性問題Cache一致性解決目錄協(xié)議基本原理具體實(shí)現(xiàn)全映射目錄協(xié)議有限目錄協(xié)議鏈?zhǔn)侥夸泤f(xié)議本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議基本原理本章內(nèi)容一致性問題Cache一致性基本原理本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議 監(jiān)聽協(xié)議涉及大量廣播通信及收集狀態(tài)信息的任務(wù)，即使是總線型網(wǎng)絡(luò)也會(huì)

14、使總線流量大大增加。 如果使無效信息只發(fā)給有關(guān)的數(shù)據(jù)塊，可以避免廣播，這需要有一套管理數(shù)據(jù)塊的結(jié)構(gòu)，這就是Cache一致性目錄協(xié)議方案。3 之 1基本原理本章內(nèi)容一致性問題Cache一致性解決方基本原理 建立目錄表 為Cache在共享存儲(chǔ)器建立一個(gè)目錄表，用于保存每個(gè)數(shù)據(jù)塊的狀態(tài)：包括用幾個(gè)標(biāo)志位分別指示這個(gè)信息塊的副本在其他幾個(gè)處理機(jī)的Cache中是否有，另外再設(shè)置一個(gè)標(biāo)志位（重寫位）用以指明是否有一個(gè)Cache允許將有關(guān)數(shù)據(jù)寫入。本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議3 之 2 目錄協(xié)議用在實(shí)現(xiàn)廣播功能比較困難的網(wǎng)絡(luò)。主要思想為：基本原理 建立目錄表本章內(nèi)容一致性問題Cache

15、一基本原理 使用目錄表 在CPU對(duì)Cache進(jìn)行寫操作時(shí)，系統(tǒng)根據(jù)目錄表中的信息將所有其它存有相同內(nèi)容的Cache拷貝無效，并置重寫位。在CPU對(duì)Cache進(jìn)行讀操作時(shí)，如果重寫未置位，則說明該內(nèi)容未經(jīng)重寫，此時(shí)若Cache讀缺失，則從主存儲(chǔ)器中或擁有正確內(nèi)容的Cache中讀入塊并修改目錄即可；如果讀命中，則直接讀即可。本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議3 之 3基本原理 使用目錄表本章內(nèi)容一致性問題Cache一全映射目錄協(xié)議本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議5 之 1目錄項(xiàng)： 重寫位 存在位 數(shù)據(jù)塊C101X共享存儲(chǔ)器CacheP2VCacheP1VXCach

16、eP3VXV-有效位：0-無效；1-有效C-重寫位：0-不許；1-允許存在位：0-不存在；1-存在 位數(shù)等于處理機(jī)數(shù)全映射目錄協(xié)議本章內(nèi)容一致性問題Cache一致性舉 例本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議5 之 2目錄項(xiàng)： 重寫位 存在位 數(shù)據(jù)塊0000X共享存儲(chǔ)器CacheP20CacheP10CacheP30 所有Cache都沒有塊X的拷貝有效位有效位有效位舉 例本章內(nèi)容一致性問題Cache一致性解決方舉 例本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議5 之 3目錄項(xiàng)： 重寫位 存在位 數(shù)據(jù)塊0111X共享存儲(chǔ)器CacheP21XCacheP11XCacheP31X

17、三個(gè)處理機(jī)都讀過塊X后有效位有效位有效位舉 例本章內(nèi)容一致性問題Cache一致性解決方舉 例本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議5 之 4目錄項(xiàng)： 重寫位 存在位 數(shù)據(jù)塊1001X共享存儲(chǔ)器CacheP20CacheP10CacheP31X P3獲得寫塊X權(quán)力后有效位有效位有效位舉 例本章內(nèi)容一致性問題Cache一致性解決方特 點(diǎn) 全映射目錄協(xié)議的效率比較高，但是其目錄開銷比較大，與處理器數(shù)平方成正比（因?yàn)槟夸涰?xiàng)的多少與處理器數(shù)成正比，而且每個(gè)目錄項(xiàng)的大小也與處理器數(shù)成正比），不具有可擴(kuò)展性。本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議5 之 5特 點(diǎn) 全映射目錄協(xié)議的效率

18、比較高，但是其目錄有限目錄協(xié)議本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議4 之 1目錄項(xiàng)： 重寫位 存在位 數(shù)據(jù)塊C11X共享存儲(chǔ)器CacheP2VCacheP1VXCacheP3VXV-有效位：0-無效；1-有效C-重寫位：0-不許；1-允許存在位： 0-不存在；1-存在 位數(shù) 等于 log2處理機(jī)數(shù)有限目錄協(xié)議本章內(nèi)容一致性問題Cache一致性解舉 例本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議4 之 2目錄項(xiàng)： 重寫位 存在位 數(shù)據(jù)塊011X共享存儲(chǔ)器CacheP20CacheP11XCacheP31X 當(dāng)P1、P3的Cache中都有塊X的拷貝時(shí)舉 例本章內(nèi)容一致性問題Ca

19、che一致性解決方舉 例本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議4 之 3目錄項(xiàng)： 重寫位 存在位 數(shù)據(jù)塊011X共享存儲(chǔ)器CacheP21XCacheP10CacheP31X P2請(qǐng)求塊X的拷貝（存在驅(qū)逐問題）舉 例本章內(nèi)容一致性問題Cache一致性解決方特 點(diǎn) 有限目錄協(xié)議解決了目錄過大的問題，其目錄開銷與Nlog2N成正比，N為處理器數(shù)（因?yàn)槟夸涰?xiàng)的多少與處理器數(shù)成正比，而且每個(gè)目錄項(xiàng)的大小與log2N成正比），但效率有所下降。本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議4 之 4特 點(diǎn) 有限目錄協(xié)議解決了目錄過大的問題，其目鏈?zhǔn)侥夸泤f(xié)議本章內(nèi)容一致性問題Cache一致性

20、解決方法目錄協(xié)議2 之 1目錄項(xiàng)：重寫位指針 數(shù)據(jù)塊CX共享存儲(chǔ)器CacheP2CacheP1VXCacheP3V-有效位：0-無效；1-有效C-重寫位：0-不許；1-允許VXVXCT鏈?zhǔn)侥夸泤f(xié)議本章內(nèi)容一致性問題Cache一致性解特 點(diǎn) 鏈?zhǔn)侥夸泤f(xié)議的復(fù)雜程度超過前兩種目錄協(xié)議，但它具有前兩種目錄協(xié)議所沒有的重要特性：可擴(kuò)展性。其指針的大小以處理機(jī)數(shù)目的對(duì)數(shù)關(guān)系增長(zhǎng)，Cache的每個(gè)數(shù)據(jù)塊的指針數(shù)目與處理機(jī)數(shù)目無關(guān)。本章內(nèi)容一致性問題Cache一致性解決方法目錄協(xié)議2 之 2特 點(diǎn) 鏈?zhǔn)侥夸泤f(xié)議的復(fù)雜程度超過前兩種目錄協(xié)I/O與Cache的一致性本章內(nèi)容一致性問題Cache一致性解決方法 禁

21、止法 存儲(chǔ)空間中的某些段不允許進(jìn)入Cache。 刷新法 操作系統(tǒng)在I/O操作前，將有關(guān)的段先從Cache刷新過來，然后再進(jìn)行I/O操作。I/O與Cache的一致性本章內(nèi)容一致性問題Cach存儲(chǔ)一致性本章內(nèi)容一致性問題問題現(xiàn)象解決方法存儲(chǔ)一致性本章內(nèi)容一致性問題問題現(xiàn)象問題現(xiàn)象本章內(nèi)容一致性問題存儲(chǔ)一致性 存儲(chǔ)一致性是指多個(gè)處理機(jī)程序的執(zhí)行次序與共享存儲(chǔ)器中共享數(shù)據(jù)存取次序之間的一致性。特征 不同處理機(jī)對(duì)不同存儲(chǔ)單元的操作引起的一致性。a. A :=1b. print B,Cc. B :=1d. print A,Ce. C :=1f. print A,BA、B、C 為共享變量(初始狀態(tài)均為0)處

22、理機(jī)1處理機(jī)2處理機(jī)3共享存儲(chǔ)器問題現(xiàn)象本章內(nèi)容一致性問題存儲(chǔ)一致性 存解決方法本章內(nèi)容一致性問題存儲(chǔ)一致性 順序一致性（SC） 任何執(zhí)行結(jié)果認(rèn)為是在多線程順序機(jī)器上各操作交錯(cuò)執(zhí)行的結(jié)果。 處理機(jī)一致性（PC） 每臺(tái)處理機(jī)發(fā)出的寫操作順序不會(huì)亂，但兩臺(tái)處理機(jī)發(fā)出的寫操作順序可能會(huì)不一樣。 弱一致性（WC） 程序員利用同步操作確保順序一致性。 釋放一致性（RC） 具有獲得和釋放兩類同步操作的弱一致性，每類操作保證處理機(jī)一致性。解決方法本章內(nèi)容一致性問題存儲(chǔ)一致性 順序一致性（同 步本章內(nèi)容為什么要同步？ 在多處理機(jī)中，進(jìn)程之間可以通過使用共享變量來實(shí)現(xiàn)信息交流，共享變量每次只能被一個(gè)進(jìn)程訪問，因

23、此當(dāng)兩個(gè)或兩個(gè)以上的進(jìn)程同時(shí)訪問某個(gè)共享變量時(shí)，必須采用同步措施來協(xié)調(diào)并行執(zhí)行的進(jìn)程。如何實(shí)現(xiàn)同步？ 一般來說，同步機(jī)制是通過用戶級(jí)的軟件例程來構(gòu)造的，而這些例程要使用硬件提供的同步指令。2 之 1同 步本章內(nèi)容為什么要同步？2 之 1同 步本章內(nèi)容基本硬件原語用戶級(jí)的同步操作2 之 2同 步本章內(nèi)容基本硬件原語2 之 2基本硬件原語本章內(nèi)容同步在多處理機(jī)中實(shí)現(xiàn)同步，所需的主要功能是：一組能以原子操作的方式讀出并修改存儲(chǔ)單元的硬件原語。它們能夠自動(dòng)讀修改單元。通常情況下，用戶不直接使用基本的硬件原語，原語主要供系統(tǒng)程序員用來編制同步庫函數(shù)。7 之 1基本硬件原語本章內(nèi)容同步在多處理機(jī)中實(shí)現(xiàn)同步

24、，所需的主要原子交換（atomic exchange）本章內(nèi)容同步功能 將一個(gè)存儲(chǔ)單元的值和一個(gè)寄存器的值進(jìn)行交換。例子 可以利用它構(gòu)建一個(gè)簡(jiǎn)單的鎖：0表示該鎖未被占用，1表示該鎖已被占用。如果某處理機(jī)想占用該鎖，將對(duì)應(yīng)于該鎖的存儲(chǔ)單元的值與存放在某個(gè)寄存器中的1進(jìn)行交換，返回結(jié)果為0則占用成功，為1則未占用成功。實(shí)現(xiàn)同步的關(guān)鍵 操作的原子性（交換操作是不可再細(xì)分的）。7 之 2原子交換（atomic exchange）本章內(nèi)容同步測(cè)試并置定（test_and_set）本章內(nèi)容同步功能 先測(cè)試一個(gè)存儲(chǔ)單元的值，如果符合條件則修改其值。例子 可以定義一個(gè)測(cè)試0和設(shè)置1的操作，該操作的使用方法與原

25、子交換類似。7 之 3測(cè)試并置定（test_and_set）本章內(nèi)容同步功能讀取并加1（fetch_and_increment）本章內(nèi)容同步功能 返回存儲(chǔ)器中的值并以原子操作的方式使存儲(chǔ)器中的值增1。例子 如果用0表示同步變量未被占用，就可以象使用原子交換一樣使用“取并增1”操作。7 之 4讀取并加1（fetch_and_increment）本章內(nèi)容使用指令對(duì):LL/SC本章內(nèi)容同步LL(load linked或load locked)：特殊的取指令SC(store conditional)：特殊的存指令指令對(duì)功能：如果由LL指明的存儲(chǔ)單元的內(nèi)容在SC對(duì)其進(jìn)行寫之前已被其他指令改寫過，則第二條

26、指令SC執(zhí)行失敗。如果在兩條指令間進(jìn)行切換也會(huì)導(dǎo)致SC執(zhí)行失敗。SC將返回一個(gè)值來指出該指令操作是否成功：“1”表示成功，“0”表示不成功LL則返回該存儲(chǔ)單元初始值。 7 之 5使用指令對(duì):LL/SC本章內(nèi)容同步LL(load linLL/SC指令對(duì)舉例本章內(nèi)容同步利用LL和SC指令實(shí)現(xiàn)“原子交換”操作 實(shí)現(xiàn)R4和由R1指出的存儲(chǔ)單元進(jìn)行原子交換操作。try：ORR3, R4, R0 LLR2, 0(R1) SCR3, 0(R1) BEQZR3, try MOVR4, R27 之 6LL/SC指令對(duì)舉例本章內(nèi)容同步利用LL和SC指令實(shí)現(xiàn)“LL/SC指令對(duì)舉例本章內(nèi)容同步利用LL和SC指令實(shí)現(xiàn)“

27、取并增1”操作 LL/SC機(jī)制的一個(gè)優(yōu)點(diǎn)：用來構(gòu)造別的同步原語。try： LLR2, 0(R1) DADDIUR2, R2, #1 SCR2, 0(R1) BEQZR2, try7 之 7LL/SC指令對(duì)舉例本章內(nèi)容同步利用LL和SC指令實(shí)現(xiàn)“用戶級(jí)的同步操作本章內(nèi)容同步旋轉(zhuǎn)鎖柵欄用戶級(jí)的同步操作本章內(nèi)容同步旋轉(zhuǎn)鎖旋轉(zhuǎn)鎖本章內(nèi)容同步用戶級(jí)的同步操作思想 處理機(jī)環(huán)繞一個(gè)鎖不停地旋轉(zhuǎn)而請(qǐng)求獲得該鎖。即：處理機(jī)圍繞該鎖反復(fù)地執(zhí)行循環(huán)程序，直至獲得該鎖。適合場(chǎng)合 鎖被占用的時(shí)間很少，在獲得鎖后加鎖過程延遲很小，因?yàn)樘幚頇C(jī)一直在循環(huán)等待獲得鎖。11 之 1旋轉(zhuǎn)鎖本章內(nèi)容同步用戶級(jí)的同步操作思想11 之

28、1旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作無Cache一致性機(jī)制 在存儲(chǔ)器中保存鎖變量，處理機(jī)可以不斷地通過一個(gè)原子交換請(qǐng)求使用權(quán)。占用鎖 DADDIUR2, R0, #1 lockit： EXCH R2, 0(R1) /原子交換 BNEZR2, lockit釋放鎖 處理機(jī)只需將0放入鎖中即可。11 之 2旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作無Cache旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作無Cache一致性機(jī)制 在存儲(chǔ)器中保存鎖變量，處理機(jī)可以不斷地通過一個(gè)原子交換請(qǐng)求使用權(quán)。缺點(diǎn) 每次交換（EXCH指令）都產(chǎn)生一次寫操作，如果多個(gè)處理機(jī)試圖占用一個(gè)鎖時(shí)，則大多數(shù)寫操作都會(huì)導(dǎo)致寫無效，

29、因?yàn)槊總€(gè)處理機(jī)都想以獨(dú)占的方式獲得鎖變量。11 之 3旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作無Cache旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作支持Cache一致性將鎖變量調(diào)入Cache，并通過一致性機(jī)制使鎖值保持一致。優(yōu)點(diǎn)：每次嘗試占用鎖都可以在本地Cache中進(jìn)行，而不需進(jìn)行全局存儲(chǔ)訪問；大多數(shù)對(duì)鎖的訪問有局限性，這樣做可以大大減少獲取鎖所需的時(shí)間。11 之 4旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作支持Cach旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作支持Cache一致性采用“原子交換”原語實(shí)現(xiàn)（改進(jìn)）：只對(duì)本地Cache中鎖的副本進(jìn)行讀取和檢測(cè)，直到發(fā)現(xiàn)該鎖已經(jīng)被釋放。然后，該程序立即

30、進(jìn)行交換操作，去跟在其他處理器上的進(jìn)程爭(zhēng)用該鎖變量。 lockit： LD R2, 0(R1) BNEZ R2, lockit DADDIU R2, R0, #1 EXCH R2, 0(R1) /原子交換 BNEZ R2, lockit11 之 5旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作支持Cach步驟 處理機(jī)P0 處理機(jī)P1 處理機(jī)P2 鎖的狀態(tài) 總線/目錄操作 1占有鎖 環(huán)繞測(cè)試是否lock=0？環(huán)繞測(cè)試是否lock=0？ 共享 無 2將鎖置為0 （收到作廢命令） （收到作廢命令）專有(P0) P0發(fā)出對(duì)鎖變量的作廢消息 3Cache失效 Cache失效 共享總線/目錄收到P2 Cache

31、失效；鎖從P0寫回 4（因總線/目錄忙而等待）lock=0共享P2 Cache失效被處理 5Lock=0 執(zhí)行交換，導(dǎo)致Cache失效共享P1 Cache失效被處理 6執(zhí)行交換，導(dǎo)致Cache失效 交換完畢：返回0并置lock=1 專有(P2) 總線/目錄收到P2 Cache失效；發(fā)作廢消息 7交換完畢：返回1 進(jìn)入關(guān)鍵程序段 專有(P1)總線/目錄處理P1 Cache失效；寫回 8環(huán)繞測(cè)試是否lock=0？ 無3個(gè)處理機(jī)利用原子交換爭(zhēng)用旋轉(zhuǎn)鎖所進(jìn)行的操作 11 之 6步驟 處理機(jī)P0 處理機(jī)P1 處理機(jī)P2 鎖的狀態(tài) 總線/目旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作支持Cache一致性采用L

32、L/SC原語實(shí)現(xiàn)：讀/寫操作明顯分開，而且LL原語不產(chǎn)生總線數(shù)據(jù)傳送，這使下面代碼與前面方法具有相同的特點(diǎn)。 lockit：LL R2, 0(R1) BNEZ R2, lockit DADDIU R2, R0, #1 SC R2, 0(R1) BEQZ R2, lockit11 之 7旋轉(zhuǎn)鎖的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作支持Cach同步性能問題本章內(nèi)容同步用戶級(jí)的同步操作 簡(jiǎn)單旋轉(zhuǎn)鎖不能很好地適應(yīng)可擴(kuò)縮性。大規(guī)模多處理機(jī)中，若所有的處理器都同時(shí)爭(zhēng)用同一個(gè)鎖，則會(huì)導(dǎo)致大量的爭(zhēng)用和通信開銷。11 之 8同步性能問題本章內(nèi)容同步用戶級(jí)的同步操作 定量分析本章內(nèi)容同步用戶級(jí)的同步操作例：假設(shè)某條總

33、線上有10個(gè)處理機(jī)同時(shí)準(zhǔn)備對(duì)同一變量加鎖。如果每個(gè)總線事務(wù)處理（讀失效或?qū)懯В┑臅r(shí)間是100個(gè)時(shí)鐘周期，而且忽略對(duì)已調(diào)入Cache中的鎖進(jìn)行讀寫的時(shí)間以及占用該鎖的時(shí)間。(1) 假設(shè)該鎖在時(shí)間為0時(shí)被釋放，并且所有處理機(jī)都在旋轉(zhuǎn)等待該鎖。問：所有10個(gè)處理機(jī)都獲得該鎖所需的總線事務(wù)數(shù)目是多少？(2) 假設(shè)總線是非常公平的，在處理新請(qǐng)求之前，要先全部處理好已有的請(qǐng)求。并且各處理機(jī)的速度相同。問：處理10個(gè)請(qǐng)求大概需要多少時(shí)間？11 之 9定量分析本章內(nèi)容同步用戶級(jí)的同步操作例：假設(shè)某條總線定量分析本章內(nèi)容同步用戶級(jí)的同步操作解：當(dāng)i個(gè)處理器爭(zhēng)用鎖的時(shí)候，它們都各自完成以下操作序列，每一個(gè)操作產(chǎn)

34、生一個(gè)總線事務(wù)：訪問該鎖的i個(gè)LL指令操作試圖占用該鎖（并上鎖）的i個(gè)SC指令操作1個(gè)釋放鎖的存操作指令 因此對(duì)于i個(gè)處理器來說，一個(gè)處理器獲得該鎖所要進(jìn)行的總線事務(wù)的個(gè)數(shù)為2i+1。 由此可知，對(duì)n個(gè)處理器，總的總線事務(wù)個(gè)數(shù)為： 對(duì)于10個(gè)處理器來說，其總線事務(wù)數(shù)為120個(gè)，需要12000個(gè)時(shí)鐘周期。11 之 10定量分析本章內(nèi)容同步用戶級(jí)的同步操作解：當(dāng)i個(gè)處理器問題分析本章內(nèi)容同步用戶級(jí)的同步操作本例中問題的根源：鎖的爭(zhēng)用、對(duì)鎖進(jìn)行訪問的串行性以及總線訪問的延遲。旋轉(zhuǎn)鎖的主要優(yōu)點(diǎn)：總線開銷或網(wǎng)絡(luò)開銷比較低，而且當(dāng)一個(gè)鎖被同一個(gè)處理器重用時(shí)具有很好的性能。旋轉(zhuǎn)鎖的兩個(gè)主要優(yōu)點(diǎn)在本例中都沒有得到體現(xiàn)11 之 11問題分析本章內(nèi)容同步用戶級(jí)的同步操作本例中問題的根源柵 欄本章內(nèi)容同步用戶級(jí)的同步操作柵欄思想 柵欄強(qiáng)制所有到達(dá)該柵欄的進(jìn)程進(jìn)行等待，直到全部的進(jìn)程到達(dá)柵欄，然后釋放全部的進(jìn)程，從而形成同步。典型實(shí)現(xiàn) 用兩個(gè)旋轉(zhuǎn)鎖：一個(gè)用來保護(hù)一個(gè)計(jì)數(shù)器，它記錄已到達(dá)該柵欄的進(jìn)程數(shù)；另一個(gè)用來封鎖進(jìn)程直至最后一個(gè)進(jìn)程到達(dá)該柵欄。 6 之 1柵 欄本章內(nèi)容同步用戶級(jí)的同步操作柵欄思想6 之 一種典型的實(shí)現(xiàn)本章內(nèi)容同步用戶級(jí)的同步操作lock（counterlock）