【文章內(nèi)容簡(jiǎn)介】 件組成 組成： 獲取方法、等待算法、釋放方法。 等待算法： 忙等待、阻塞。 應(yīng)用 忙等待適合等待周期較短的場(chǎng)合，阻塞適合等待周期較長(zhǎng)的場(chǎng)合。 優(yōu)化 — 先采用忙等待，超過(guò)某時(shí)間閥值后轉(zhuǎn)為阻塞。 同步事件的實(shí)現(xiàn)： 在基本硬件原語(yǔ)的基礎(chǔ)上，用軟件實(shí)現(xiàn)同步算法。 說(shuō)明：本節(jié)的討論均基于忙等待進(jìn)行。 45 二、互斥 硬件鎖 在總線上用一組鎖線路實(shí)現(xiàn)，每一條線代表一把鎖。 該方法不靈活，所數(shù)量有限，基本不采用。 簡(jiǎn)單軟件鎖算法 方法： 鎖代碼放在 OS中、鎖代碼前后用硬件鎖、 增加原子性讀 修改 寫指令 。 可選方案： （原子性指令） 測(cè)試并設(shè)置指令、交換指令、取并操作指令、比較交換指令。 46 測(cè)試并設(shè)置指令（ Testamp。Set） 測(cè)試并設(shè)置鎖特點(diǎn)： 等待期間每次測(cè)試產(chǎn)生一次寫的總線事務(wù)。 等待期間的總線流量與參與的處理器數(shù)量成正比。 優(yōu)化設(shè)計(jì)： 帶回退的測(cè)試并設(shè)置鎖 — 減少等待期間指令發(fā)出的頻率， 操作失敗后插入的延遲時(shí)間可變（ t=k ci）； 測(cè)試 測(cè)試并設(shè)置鎖（ Test and Testamp。Set） — 減少等待期間的總線流量， 占有方 — I態(tài) → E態(tài) → M態(tài) → S態(tài) →M 態(tài) → I態(tài) 等待方 —— I態(tài) →S 態(tài) →I 態(tài) → E態(tài) → M態(tài) → — I態(tài) →S 態(tài) → I態(tài) → 47 鎖性能指標(biāo)： 低時(shí)延、低流量、可擴(kuò)展性、低存儲(chǔ)代價(jià)、公平性。 時(shí)延 流量 可擴(kuò)展性 存儲(chǔ)代價(jià) 公平性 測(cè)試并設(shè)置鎖 小 大 差 好 不保證 帶回退測(cè)試并設(shè)置鎖 小 中 中 好 不保證 測(cè)試 測(cè)試并設(shè)置鎖 略大 小 好 好 不保證 流量（ p每個(gè) PE各獲得一次） 測(cè)試并設(shè)置鎖 O(p m), m=∑k ci 帶回退測(cè)試并設(shè)置鎖 O(p i ) 測(cè)試 測(cè)試并設(shè)置鎖 O(p2) 結(jié)論：理所當(dāng)然用測(cè)試 測(cè)試并設(shè)置鎖代替測(cè)試并設(shè)置鎖。 48 優(yōu)化的硬件原語(yǔ)： LLSC 用非原子性的 LoadLocked和 StoreConditional指令對(duì)實(shí)現(xiàn)變量的原子訪問(wèn)。 look: ll reg1, location //取鎖變量到 reg1 bnz reg1, lock //如果變量已加鎖，轉(zhuǎn) look sc location, reg2 //LL后沒(méi)有其他 PE對(duì)變量的寫操作， //且第一個(gè)將 sc指令送到總線的 PE將成功操作 beqz look //如果失敗，轉(zhuǎn) look ret LLSC與 Test and Testamp。Set比較： 獲得鎖的嘗試失敗不產(chǎn)生作廢，總線流量少； 不用讀 改 寫原子總線事務(wù)實(shí)現(xiàn)原子訪問(wèn)。 LLSC原語(yǔ)應(yīng)用： 可合成多種原子操作，如取并加 1。 49 高級(jí)的鎖算法 目標(biāo)： 鎖被釋放時(shí)，只有一個(gè) PE去嘗試獲得鎖； 鎖被釋放時(shí)，只有一個(gè)進(jìn)程發(fā)生讀撲空。 加號(hào)鎖： （實(shí)現(xiàn)了第一個(gè)目標(biāo)） 進(jìn)程取某單元值并加一，進(jìn)程讀另一單元（正在服務(wù)）值，去和讀的值相等時(shí)獲得鎖； 釋放時(shí)將正在服務(wù)單元值加一。 取并加一實(shí)現(xiàn)： 可用 LLSC實(shí)現(xiàn)。 服務(wù)單元加一實(shí)現(xiàn)： 普通寫操作。 算法優(yōu)化： 采用帶回退的方法減少等待期間總線流量，回退值與進(jìn)程取的值成正比。 50 基于數(shù)組的鎖： （實(shí)現(xiàn)了兩個(gè)目標(biāo)） 進(jìn)程取得存儲(chǔ)單元（內(nèi)容為下一個(gè)進(jìn)程取得的存儲(chǔ)單元地址和本進(jìn)程狀態(tài)），進(jìn)程讀取該單元上狀態(tài)，不忙時(shí)獲得鎖； 釋放時(shí)向該單元中對(duì)應(yīng)的下一個(gè)進(jìn)程的單元寫不忙值。 時(shí)延 流量 可擴(kuò)展性 存儲(chǔ)代價(jià) 公平性 測(cè)試 測(cè)試并設(shè)置鎖 小 中 線性 好 不保證 LLSC 小 較小 線性 好 不保證 加號(hào)鎖 小 小 線性 較好 保證 基于數(shù)組的鎖 小 最小 常數(shù) 差 保證 結(jié)論： 帶回退的 LLSC鎖具有最好的性能； 基于數(shù)組的鎖具有最好的可擴(kuò)展性； 帶有比例回退的加號(hào)鎖和數(shù)組鎖具有較好的公平性。 設(shè)計(jì)：根據(jù)系統(tǒng)的應(yīng)用特性及性能 /價(jià)格要求進(jìn)行選擇。 51 二、點(diǎn)對(duì)點(diǎn)事件同步 軟件算法 用普通變量作為標(biāo)記，通報(bào)同步事件的出現(xiàn)。 硬件支持 — 滿 空位 使每個(gè)存儲(chǔ)字均和滿 空位狀態(tài)相聯(lián)，寫后滿，讀后空。 缺點(diǎn)： 功能限制 (不能寫后寫和讀后讀 )和硬件代價(jià)大。 P1 P2 a=f(x)。 /*set a*/ while (flag is 0 ) do nothing。 flag=1。 b=g(a)。 /*use a*/ P1 P2 a=f(x)。 /*set a*/ b=g(a)。 /*use a*/ 結(jié)論：用普通變量作為標(biāo)記，在標(biāo)記上用忙等待或阻塞實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)同步。 52 三、全局（柵障）事件同步 集中式軟件柵障 實(shí)現(xiàn)： 一把鎖、一個(gè)計(jì)數(shù)器、一個(gè)標(biāo)記位。 常規(guī)柵障： BARRIER(bar_name, p) { LOCK()。 if ( == 0 ) = 0。 mycount = ++。 UNLOCK()。 if ( mycount == p ) { = 0。 = 1。 } else while ( == 0 ) ()。 } 帶感應(yīng)逆轉(zhuǎn)的柵障： BARRIER(bar_name, p) { local_sense = !(local_sense)。 LOCK()。 mycount = ++。 if ( mycount == p ) { UNLOCK()。 = 0。 = local_sense。 } else { UNLOCK()。 while ( == 0 ) ()。 } } 53 硬件原語(yǔ) 取決于鎖算法原語(yǔ)： 柵障采用鎖和普通讀 /寫實(shí)現(xiàn)； 優(yōu)化的總線原語(yǔ)： PE在發(fā)出讀撲空時(shí) /后，看到對(duì)同一單元的讀撲空的總線信號(hào)后，將自己的讀撲空在到達(dá)總線前取消，簡(jiǎn)單地從總線上取得所需數(shù)據(jù)。 優(yōu)化的總線原語(yǔ)同樣適用于互斥中獲得鎖的等待期間的高度總線爭(zhēng)用。 硬件柵障 總線上用多條 “ 線與 ” 線路實(shí)現(xiàn)多個(gè)硬件柵障。 優(yōu)點(diǎn)： 在柵障頻率較高的機(jī)器中較有用； 缺點(diǎn)： OS不易管理進(jìn)程在 PE間遷移，同一 PE多個(gè)進(jìn)程問(wèn)題。 結(jié)論：采用硬件原語(yǔ)支持的鎖和共享變量構(gòu)造軟件柵障。 54 第四節(jié) 基于監(jiān)聽(tīng)的 Cache一致性實(shí)現(xiàn) 影響 Cache一致性協(xié)議性能的因素： 總線設(shè)計(jì)、 Cache設(shè)計(jì)、存儲(chǔ)系統(tǒng)整合。 Cache一致性協(xié)議實(shí)現(xiàn)的目標(biāo)： 正確性 — 相對(duì)于抽象的狀態(tài)轉(zhuǎn)換圖，在硬件層的動(dòng)作不一定是原子性的時(shí)候保持正確性； 高性能 — 存取操作應(yīng)流水化，非串行執(zhí)行； 最少的額外硬件 — 優(yōu)化設(shè)計(jì)，減少硬件復(fù)雜性和成本。 55 一、正確性需求 滿足一致性需求 滿足 Cache一致性需求，保持存儲(chǔ)一致性模型的語(yǔ)義。 避免死鎖 死鎖處理：避免資源的依賴環(huán)，發(fā)生死鎖時(shí)能夠處理。 活鎖處理：通過(guò)優(yōu)先級(jí)來(lái)解決。 挨餓處理：使用總線仲裁設(shè)備和先進(jìn)先出隊(duì)列訪問(wèn)資源。 異常處理 能夠正確地處理各種異常。 56 二、采用原子總線的單級(jí) Cache設(shè)計(jì) Cache控制器和塊標(biāo)記 Cache 存儲(chǔ)陣列 比較器 控制器 處理器 目錄表 Data Cmd Addr System Bus 單處理機(jī) Cache： 塊狀態(tài) I、 V、 M； 控制器 有限狀態(tài)機(jī)； 總線操作步驟 請(qǐng)求、獲得、地址和命令、響應(yīng)、數(shù)據(jù)。 問(wèn)題 1： Cache如何實(shí)現(xiàn) R/W/WB操作的？ 問(wèn)題 2： 為什么總線 R/W時(shí)，主設(shè)備會(huì)發(fā)出等待周期？ 返回下頁(yè) 57 多處理機(jī) Cache： 要求： 能夠同時(shí)響應(yīng)總線端和處理器端兩方面的操作。 控制器 — 分為總線端控制器、處理器端控制器兩部分。 處理器端控制器： 與單處理機(jī) Cache控制器類似； 總線端控制器： 控制和響應(yīng)來(lái)自總線的事務(wù)。 狀態(tài) — M、 E、 S、 I。 要求： 支持總線端、處理器端控制器的同時(shí)訪問(wèn)； 實(shí)現(xiàn)： 雙端口存儲(chǔ)器組成的目錄表、 相互拷貝的兩個(gè)目錄表 (改寫與其他操作互斥 )。 轉(zhuǎn)上頁(yè) 58 監(jiān)聽(tīng)結(jié)果報(bào)告的設(shè)計(jì) 提交監(jiān)聽(tīng)結(jié)果的時(shí)間設(shè)計(jì)： ： 主存設(shè)計(jì)不受影響，監(jiān)聽(tīng)時(shí)延較大 √ ： 握手方法 Cache監(jiān)聽(tīng)并可以提供數(shù)據(jù)，同時(shí)主存提取數(shù)據(jù)，等待Cache的監(jiān)聽(tīng)結(jié)果并響應(yīng)（ Cache有響應(yīng)時(shí)，主存結(jié)果作廢） ： 主存每個(gè)塊有一個(gè)是否在 Cache中的標(biāo)志，來(lái)指示主存是否響應(yīng)總線操作請(qǐng)求。 59 監(jiān)聽(tīng)結(jié)果的格式設(shè)計(jì)： 總線增加三根信號(hào)線 監(jiān)聽(tīng)命中信號(hào)： 指示有否該塊的拷貝； 修改狀態(tài)信號(hào)： 指示命中的塊是否處于修改狀態(tài)； 監(jiān)聽(tīng)完成信號(hào)： 指示監(jiān)聽(tīng)是否完成。 各 Cache對(duì)監(jiān)聽(tīng)結(jié)果的相應(yīng)處理： 監(jiān)聽(tīng)結(jié)果 總線事務(wù) 完成 命中 修改 BusRd BusRdX BusWB 0 X X 主存提供數(shù)據(jù)，請(qǐng)求方 I→E ，無(wú)命中方 主存提供數(shù)據(jù)，請(qǐng)求方I→M ，無(wú)命中方 無(wú)請(qǐng)求方 1 1 0 主存 /Cache提供數(shù)據(jù)， 請(qǐng)求方 I→S 主存 /Cache提供數(shù)據(jù)，請(qǐng)求方 I→M ，命中方 E/S→I 無(wú)請(qǐng)求方 1 1 1 Cache提供數(shù)據(jù)，請(qǐng)求方 I→S ，命中方M→S Cache提供數(shù)據(jù)，主存接收數(shù)據(jù)，請(qǐng)求方 I→M ，命中方 M/S→I 主存接收數(shù)據(jù)，請(qǐng)求方 M→I ，無(wú)命中方 返回下二頁(yè) 60 對(duì)寫回的處理 為隱藏寫回時(shí)延，常采用推遲寫回、先處理讀撲空的方法。 推遲回寫實(shí)現(xiàn)： Cache中增加寫回緩沖區(qū)（ WBBuff），將推遲寫回的塊放入 WBBuff，總線端控制器對(duì) WBBuff進(jìn)行管理。 地址 塊數(shù)據(jù)緩沖區(qū) 寫回緩沖區(qū)管理： 總線空閑時(shí)，總線端控制器發(fā)出 BusWB操作，將 WBBuff內(nèi)容寫回主存，清除緩沖區(qū)中相應(yīng)項(xiàng)； 總線不空閑且總線事務(wù)（包括本地的操作）與 WBBuff地址相同時(shí)，發(fā)出監(jiān)聽(tīng)結(jié)果信號(hào) (111)，從 WBBuff中提取數(shù)據(jù)，清除緩沖區(qū)中相應(yīng)項(xiàng)。 返回下頁(yè) 61 基于監(jiān)聽(tīng)的 Cache結(jié)構(gòu)設(shè)計(jì) 采用 MESI一致性協(xié)議，兩個(gè)控制器、兩個(gè)同步目錄表、一個(gè)數(shù)據(jù)緩沖區(qū)、一個(gè)寫回緩沖區(qū)。 Cache 存儲(chǔ)陣列 比較器 處理器端 控制器 處理器 目錄表 Data Cmd