1、2006年2月秦杰 鄭麗萍 張慶輝7.5 同 步 通常是運用硬件提供的有關(guān)同步指令，經(jīng)過用戶級軟件例程建立的。 7.5.1 根本硬件原語 在多處置器同步中，主要功能是一組能自動讀出后并進展寫存儲單元的硬件原語。它們可以自動讀修正單元。通常情況下，用戶不直接運用根本的硬件原語，原語主要供系統(tǒng)程序員用來編制同步庫函數(shù)。 第章 多處置機2006年2月秦杰 鄭麗萍 張慶輝 功能：將一個存儲單元的值和一個存放器的值 進展交換。建立一個鎖，鎖值為“0表示開鎖， 為“1表示上鎖。 處置器加鎖時，將對應(yīng)于該鎖的存儲單元的值 交換為某個存放器的值“1。假設(shè)前往值為“0， 存儲單元的值此時已置換為“1，防止了別的

2、進 程競爭該鎖。 實現(xiàn)同步的關(guān)鍵: 操作的原子性1. 典型操作:原子交換atomic exchange7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝2. 測試并置定test_and_set 先測試一個值，假設(shè)符合條件那么修正其值。3. 讀取并加1fetch_and_increment 它前往存儲單元的值并自動添加該值。4. 運用指令對q LL(load linked LL(load linked或或load locked)load locked)的取指令的取指令q SC(store conditional)SC(store conditional)的特殊存指令的特殊存指令7.5 同 步200

3、6年2月秦杰 鄭麗萍 張慶輝例實現(xiàn)對由例實現(xiàn)對由R1R1指出的存儲單元進展原子交換操作指出的存儲單元進展原子交換操作 try try：mov R3,R4 mov R3,R4 ；送交換值；送交換值 ll R2,0(R1) ll R2,0(R1) ；load linkedload linked sc R3,0(R1) sc R3,0(R1) ；store conditionalstore conditional beqz R3,try beqz R3,try ；存失敗轉(zhuǎn)移；存失敗轉(zhuǎn)移 mov R4,R2 mov R4,R2 ；將取的值送往；將取的值送往R4R4 最終最終R4R4和由和由R1R1指向

4、的單元值進展原子交換，在指向的單元值進展原子交換，在llll和和scsc之間如有別的處置器插入并修正了存儲單元的值，之間如有別的處置器插入并修正了存儲單元的值，scsc將前往將前往“0 0并存入并存入R3R3中，從而使指令序列再重新循環(huán)。中，從而使指令序列再重新循環(huán)。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 llsc機制的一個優(yōu)點：可用來構(gòu)造別的同步原語 例如：原子的fetch-and-increment try： ll R2,0(R1) ；load linked addi R2,R2,1 ；添加 sc R2,0(R1) ；store conditional beqz R2,try ；

5、存失敗轉(zhuǎn)移 指令對的實現(xiàn)必需跟蹤地址 由ll指令指定一個存放器，該存放器存放著一個 單元地址，這個存放器常稱為銜接存放器。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝7.5.2 用一致性實現(xiàn)鎖 采用多處置機的一致性機制來實現(xiàn)旋轉(zhuǎn)鎖。 旋轉(zhuǎn)鎖 處置器環(huán)繞一個鎖不停地旋轉(zhuǎn)而懇求獲得該鎖。1. 無Cache一致性機制 在存儲器中保管鎖變量，處置器可以不斷地通 過一個原子操作懇求加鎖，比如先交換，再測試返 回值從而知道鎖的情況。釋放鎖的時候，處置器可 簡單地將鎖置為“0 。 7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 li R2 li R2，1 1lockitlockit： exch R2,

6、0(R1) exch R2,0(R1) ；原子交；原子交換換 bnez R2bnez R2，lockit lockit ；能否已；能否已加鎖加鎖? ?2. 機器支持Cache一致性 將鎖緩沖進入Cache，并經(jīng)過一致性機制使鎖值保 持一致。 7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 優(yōu)點q 可使可使“環(huán)繞的進程對本地環(huán)繞的進程對本地CacheCache塊進展操作；塊進展操作；q 可利用鎖訪問的部分性，即處置器最近運用過可利用鎖訪問的部分性，即處置器最近運用過 q 的鎖不久又會運用。的鎖不久又會運用。 改良旋轉(zhuǎn)鎖(獲得第一條益處) 使其環(huán)繞過程僅對本地Cache中鎖的拷貝進展讀， 直到它

7、前往“0確認鎖可用，然后再進展加鎖交換操 作。運用鎖終了后新競爭又開場進展。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 lockit：lw R2，0(R1) ；取鎖值 bnez R2，lockit ；鎖不可用 li R2，1 ；存入鎖值 exch R2，0(R1) ；交換 bnez R2，lockit ;如鎖不為0轉(zhuǎn)移 上面給出了對于三個處置器競爭鎖的操作。一旦處置器存入“0釋放鎖，一切別的Cache對應(yīng)塊均被作廢，必需取新的值來更新它們鎖的拷貝。 一個處置器Cache會先獲得未加鎖值并執(zhí)行交換操作，當(dāng)別的Cache失效處置完后，它們會發(fā)現(xiàn)已被加鎖，所以又必需不停地測試環(huán)繞。7.5 同

8、步2006年2月秦杰 鄭麗萍 張慶輝表表7.5 7.5 三個處置機對鎖的運用三個處置機對鎖的運用步驟步驟 處置器處置器P0處置器處置器P1處置器處置器P2鎖形狀鎖形狀總線總線/目錄操作目錄操作1占有鎖占有鎖環(huán)繞測試環(huán)繞測試lock=0環(huán)繞測試環(huán)繞測試lock=0Shared無無2將鎖置為將鎖置為0收到作廢命令收到作廢命令(收到作廢命令收到作廢命令)ExclusiveP0發(fā)鎖變量作廢音訊發(fā)鎖變量作廢音訊3 Cache失效失效Cache失效失效Shared總線總線/目錄處置目錄處置P2 Cache失效失效,鎖從鎖從P0寫回寫回4 總線總線/目錄忙那么目錄忙那么等待等待Lock=0SharedP2

9、Cache失效處置失效處置5 Lock=0執(zhí)行交換，導(dǎo)執(zhí)行交換，導(dǎo)致致 Cache失效失效SharedP1Cache失效處置失效處置6 執(zhí)行交換，導(dǎo)致執(zhí)行交換，導(dǎo)致 Cache失效失效 交換終了，前交換終了，前往往0置置lock=1Exclusive總線總線/目錄處置目錄處置P2 Cache失效失效,發(fā)作廢音訊發(fā)作廢音訊7 交換終了，前往交換終了，前往1進入關(guān)鍵處置進入關(guān)鍵處置段段Shared總線總線/目錄處置目錄處置P2 Cache失效，寫回失效，寫回8 環(huán)繞測試環(huán)繞測試lock=0 無無7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 llsc原語的另一個形狀：讀寫操作明顯分開。 Ll不產(chǎn)

10、生總線數(shù)據(jù)傳送，這使下面代碼與運用經(jīng) 過優(yōu)化交換的代碼具有一樣的特點： lockit： ll R2，0(R1) ；load-linked bnez R2，lockit ；鎖無效 li R2,，1 ；加鎖值 sc R2，0(R1) ；存 beqz R2，lockit ；如存失敗轉(zhuǎn)移 第一個分支構(gòu)成環(huán)繞的循環(huán)體，第二個分支處理了兩個同時懇求鎖的處置器競爭問題。雖然旋轉(zhuǎn)鎖機制簡單并且具有強迫性，但難以將它擴展四處置器數(shù)量很多的情況。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝7.5.3 同步性能問題 簡單旋轉(zhuǎn)鎖不能很好地順應(yīng)可伸縮性。大規(guī)模機器 中一切的處置器會產(chǎn)生出大量的競爭問題。 例7.3：

11、設(shè)總線上有10個處置器同時預(yù)備對同一變量加鎖。假設(shè)每個總線事務(wù)處置(讀失效或?qū)懯?是100個時鐘周期，忽略實踐的Cache塊鎖的讀寫時間以及加鎖的時間，求10個處置器懇求加鎖所需的總線事務(wù)數(shù)目。設(shè)時間為0時鎖已釋放并且一切處置器在旋轉(zhuǎn)，求處置這10個懇求時間為多長?假設(shè)總線在新的懇求到達之前已效力完掛起的一切懇求，并且處置器速度一樣。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝解解 當(dāng)當(dāng)i i個處置器競爭鎖的時候，他們完成以下操個處置器競爭鎖的時候，他們完成以下操作序列，每一個操作產(chǎn)生一個總線事務(wù)：作序列，每一個操作產(chǎn)生一個總線事務(wù)： 訪問該鎖的訪問該鎖的i i個個LLLL指令操作；指令

12、操作； 試圖鎖住該鎖的試圖鎖住該鎖的i i個個SCSC指令操作；指令操作； 1 1個釋放鎖的存操作指令。個釋放鎖的存操作指令。因此對因此對n n個處置器，總線事務(wù)的總和為：個處置器，總線事務(wù)的總和為： n n (2i+1)=n(n+1)+n=n2+2n (2i+1)=n(n+1)+n=n2+2n i=1 i=1對于對于1010個處置器有個處置器有120120個總線事務(wù)，需求個總線事務(wù)，需求1200012000個時個時鐘周期。鐘周期。 7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 本例中問題的根源是鎖的競爭、存儲器中本例中問題的根源是鎖的競爭、存儲器中鎖訪問的串行性以及總線訪問的延遲。鎖訪問

13、的串行性以及總線訪問的延遲。 旋轉(zhuǎn)鎖的主要優(yōu)點旋轉(zhuǎn)鎖的主要優(yōu)點: : 對于總線或網(wǎng)絡(luò)對于總線或網(wǎng)絡(luò)開銷較低開銷較低7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝q 并行循環(huán)的程序中另一個常用的同步操作: 柵欄q 柵欄強迫一切到達的進程進展等待，直到全部的q 進程到達柵欄，然后釋放全部的進程，從而構(gòu)成同步。 柵欄的典型實現(xiàn)柵欄的典型實現(xiàn) 用兩個旋轉(zhuǎn)鎖用兩個旋轉(zhuǎn)鎖 (1) (1) 用來記錄到達柵欄的進程數(shù)用來記錄到達柵欄的進程數(shù) (2) (2) 用來封鎖進程直至最后一個進程到達柵欄用來封鎖進程直至最后一個進程到達柵欄 柵欄的實現(xiàn)要不停地探測指定的變量，柵欄的實現(xiàn)要不停地探測指定的變量， 直到它滿

14、足規(guī)定的條件。直到它滿足規(guī)定的條件。 一種典型的實現(xiàn)，其中一種典型的實現(xiàn)，其中l(wèi)ocklock和和unlockunlock提供根本的提供根本的 旋轉(zhuǎn)鎖，旋轉(zhuǎn)鎖，totaltotal是要到達柵欄的進程總數(shù)。是要到達柵欄的進程總數(shù)。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝Lock(counterlock)Lock(counterlock)； * *確保更新的原子性確保更新的原子性* *if(count=0) release=0if(count=0) release=0； * *第一個進程那么重置第一個進程那么重置releaserelease* *count=count+1count=cou

15、nt+1； * *到達進程記數(shù)到達進程記數(shù)* *unlock(counterlock)unlock(counterlock)； * *釋放鎖釋放鎖* *if(count=total) if(count=total) * *進程全部到達進程全部到達* * count=0count=0； * *重置計數(shù)器重置計數(shù)器* * release=1release=1； * *釋放進程釋放進程* * else else * *還有進程未到達還有進程未到達* * spin(release=1)spin(release=1)； * *等待別的進程到達等待別的進程到達* * 7.5 同 步2006年2月秦杰 鄭麗

16、萍 張慶輝 對counterlock加鎖保證增量操作的原子性，變 量 count記錄著已到達柵欄的進程數(shù)，變量 release用來封鎖進程直到最后一個進程到達柵欄。 實踐情況中會出現(xiàn)的問題 能夠反復(fù)運用一個柵欄，柵欄釋放的進程運轉(zhuǎn) 一段后又會再次前往柵欄，這樣有能夠出現(xiàn)某個進 程永遠離不開柵欄的情況(它停在旋轉(zhuǎn)操作上)。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 例如：例如：OSOS調(diào)度進程，能夠一個進程速度較快，調(diào)度進程，能夠一個進程速度較快，當(dāng)它第二次到達柵欄時，第一次的進程還掛在柵欄當(dāng)它第二次到達柵欄時，第一次的進程還掛在柵欄中未能分開。這樣一切的進程在這個柵欄的第二次中未能分開。

17、這樣一切的進程在這個柵欄的第二次運用中都處于無限等待形狀，由于進程的數(shù)目永達運用中都處于無限等待形狀，由于進程的數(shù)目永達不到不到totaltotal。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝q 一種處理方法一種處理方法q 當(dāng)進程分開柵欄時進展計數(shù)，在上次柵欄運用中當(dāng)進程分開柵欄時進展計數(shù)，在上次柵欄運用中q 的一切進程分開之前不允許任何進程重用并初始化本的一切進程分開之前不允許任何進程重用并初始化本q 柵欄。柵欄。q 另一種處理方法另一種處理方法q sense_reversingsense_reversing柵欄，每個進程均運用一個私柵欄，每個進程均運用一個私q 有變量有變量local

18、_senselocal_sense，初始化為，初始化為1 1。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝Local_sense=! Local_senseLocal_sense=! Local_sense； * *local-senselocal-sense取反取反* *lock(counterlock)lock(counterlock)； * *確保添加的原子確保添加的原子性性* *count+count+； * *記算到達進程數(shù)記算到達進程數(shù)* *unlock(counterlock)unlock(counterlock)； * *解鎖解鎖* *if(count=total) if(

19、count=total) * *進程全部到達進程全部到達* * count=0count=0； * *重置計數(shù)器重置計數(shù)器* * release=local_senserelease=local_sense； * *釋放進程釋放進程* * else else * *還有進程未到達還有進程未到達* * spin(release=local_sense)spin(release=local_sense)； * *等待信等待信號號* * 7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝例例7.4 7.4 假設(shè)總線上假設(shè)總線上1010個處置器同時執(zhí)行一個柵欄，設(shè)個處置器同時執(zhí)行一個柵欄，設(shè)每個總線事務(wù)

20、需每個總線事務(wù)需100100個時鐘周期，忽略個時鐘周期，忽略CacheCache塊中鎖的塊中鎖的讀、寫實踐破費的時間，以及柵欄實現(xiàn)中非同步操作讀、寫實踐破費的時間，以及柵欄實現(xiàn)中非同步操作的時間，計算的時間，計算1010個處置器全部到達柵欄，被釋放及分個處置器全部到達柵欄，被釋放及分開柵欄所需的總線事務(wù)數(shù)。設(shè)總線完全公平，整個過開柵欄所需的總線事務(wù)數(shù)。設(shè)總線完全公平，整個過程需多長時間程需多長時間? ?答：下表給出一個處置器經(jīng)過柵欄發(fā)出的事件序列，答：下表給出一個處置器經(jīng)過柵欄發(fā)出的事件序列，設(shè)第一個獲得總線的進程并未擁有鎖。設(shè)第一個獲得總線的進程并未擁有鎖。7.5 同 步2006年2月秦杰

21、鄭麗萍 張慶輝 表表7.6 第第i個處置器經(jīng)過柵欄產(chǎn)生的事件序列個處置器經(jīng)過柵欄產(chǎn)生的事件序列 事件事件 數(shù)量數(shù)量 對應(yīng)源代碼對應(yīng)源代碼 闡明闡明LL i Lock(counterlock)； 一切處置器搶鎖一切處置器搶鎖SC i Lock(counterlock)； 一切處置器搶鎖一切處置器搶鎖LD 1 count=count+1； 一個勝利一個勝利LL i-1 Lock(counterlock)； 不勝利的處置器再次搶不勝利的處置器再次搶鎖鎖SD 1 count=count+1； 獲得專有訪問產(chǎn)生的失效獲得專有訪問產(chǎn)生的失效SD 1 unlock(counterlock)； 獲得鎖產(chǎn)生的失

22、效獲得鎖產(chǎn)生的失效LD 2 spin(release=local_sense)；讀釋放：初次和最后；讀釋放：初次和最后寫產(chǎn)寫產(chǎn) 生的失效生的失效7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝q 當(dāng)競爭不猛烈且同步操作較少時，我們主要關(guān)懷的q 是一個同步原語操作的延遲。q 根本的旋轉(zhuǎn)鎖操作可在兩個總線周期內(nèi)完成：q 一個讀鎖，一個寫鎖。我們可用多種方法改良構(gòu)成q 在一個單周期內(nèi)完成操作。q 同步操作最嚴重的問題：進程的串行性q 當(dāng)出現(xiàn)競爭時，就會出現(xiàn)串行性問題。它極大q 地添加了同步操作的時間。q 總線的運用是這個問題關(guān)鍵所在。q 在基于目錄的Cache一致性機器中，串行性問題也q 同樣嚴重。

23、7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝7.5.4 大規(guī)模機器的同步所希望的同步機制：在無競爭的條件下延遲較小 在競爭猛烈時串行性小1. 軟件實現(xiàn) 旋轉(zhuǎn)鎖 (1) 旋轉(zhuǎn)鎖實現(xiàn)的主要問題 當(dāng)多個進程檢測并競爭鎖時引起的延遲 (2) 一種處理方法: 當(dāng)加鎖失敗時就人為地推遲 這些進程的等待時間。 (3) 具有指數(shù)延遲的旋轉(zhuǎn)鎖代碼7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 li R3，1 ；R3初始延遲值；lockit： ll R2，0(R1) ；load linked bnez R2，lockit ；無效 addi R2，R2，1 ；取到加鎖值 sc R2，0(R1) ；store

24、conditional bnez R2，gotit ；存勝利轉(zhuǎn)移 sll R3，R3，1 ；將延遲時間增至2倍 pause R3 ；延遲R3中時間值 j lockitgotit： 運用加鎖維護的數(shù)據(jù) 當(dāng)sc失敗時，進程推遲R3個時間單位。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 先討論采用數(shù)組進展的軟件實現(xiàn)。為此我們給出一種更好的柵欄實現(xiàn)代碼。 前面柵欄機制實現(xiàn)中，一切的進程必需讀取 release標志，構(gòu)成沖突。 經(jīng)過組合樹來減小沖突 組合樹是多個懇求在部分結(jié)合起來構(gòu)成樹的一 種分級構(gòu)造。 降低沖突的緣由：將大沖突化解成為并行的多 個小沖突。 鎖實現(xiàn)的另一種技術(shù)是排隊鎖7.5 同 步

25、2006年2月秦杰 鄭麗萍 張慶輝q 組合樹采用預(yù)定義的組合樹采用預(yù)定義的n n叉樹構(gòu)造叉樹構(gòu)造q 用變量用變量k k表示扇入數(shù)目，實踐中表示扇入數(shù)目，實踐中k=4k=4效果較效果較q 好。當(dāng)好。當(dāng)k k個進程都到達樹的某個結(jié)點時，那么個進程都到達樹的某個結(jié)點時，那么發(fā)發(fā)q 信號進入樹的上一層。信號進入樹的上一層。q 當(dāng)全部進程到達的信號聚集在根結(jié)點時，釋放當(dāng)全部進程到達的信號聚集在根結(jié)點時，釋放q 一切的進程。一切的進程。q 采用采用sense_reversingsense_reversing技術(shù)來給出下面的基于技術(shù)來給出下面的基于q 組合樹的柵欄代碼。組合樹的柵欄代碼。7.5 同 步200

26、6年2月秦杰 鄭麗萍 張慶輝struct node struct node * *組合樹中一個結(jié)點組合樹中一個結(jié)點* * int counterlockint counterlock；int count int count ；int parentint parent； struct node tree struct node tree 0.p-10.p-1； * *樹中各結(jié)點樹中各結(jié)點* * int local_senseint local_sense；int releaseint release； barrier(int mynode) barrier(int mynode) lock(tr

27、eemynode.counterlock)lock(treemynode.counterlock)；* *維護計數(shù)器維護計數(shù)器* * count+count+； * *計數(shù)的累加計數(shù)的累加* * unlock(treemynode.conterlock)unlock(treemynode.conterlock)；* *解鎖解鎖* * if(treemynode.count=k)if(treemynode.count=k) * *本結(jié)點全部到達本結(jié)點全部到達* * if(treemynode.parent)=0if(treemynode.parent)=0 barrier(treemynodeb

28、arrier(treemynode.parent).parent)； elseelserelease=local_senserelease=local_sense； treemynode.counttreemynode.count0 0； * *為下次重用初始化為下次重用初始化* * else else spin(release=local_sense)spin(release=local_sense)； local_sense= ! local_senselocal_sense= ! local_sense；barrier (mynode)barrier (mynode)；7.5 同 步20

29、06年2月秦杰 鄭麗萍 張慶輝2. 硬件原語支持 引見兩種硬件同步原語：(1) 排隊鎖 可以排隊記錄等待的進程，當(dāng)鎖釋放時送 出一個已確定的等待進程。 第一個針對鎖 第二個針對柵欄和要求進展計數(shù)或提供明確索 引的某些用戶級操作7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝q 硬件實現(xiàn)q 在基于目錄的機器上，經(jīng)過硬件向量等方式q 來進展排隊和同步控制。q 在基于總線的機器中要將鎖從一個進程顯式q 地傳給另一個進程，軟件實現(xiàn)會更好一些。q 在第一次取鎖變量失效時，失效被送入同步控在第一次取鎖變量失效時，失效被送入同步控q 制器。同步控制器可集成在存儲控制器中制器。同步控制器可集成在存儲控制器中(

30、 (基基 q 于總線的系統(tǒng)于總線的系統(tǒng)) )或集成在目錄控制器中?；蚣稍谀夸浛刂破髦小 排隊鎖的任務(wù)過程7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝q 假設(shè)鎖空閑，將其交給該處置器；假設(shè)鎖忙，控制假設(shè)鎖空閑，將其交給該處置器；假設(shè)鎖忙，控制q 器產(chǎn)生一個結(jié)點懇求記錄，并將鎖忙的標志前往器產(chǎn)生一個結(jié)點懇求記錄，并將鎖忙的標志前往給給q 處置器，然后該處置器不停地進展檢測。處置器，然后該處置器不停地進展檢測。q 當(dāng)該鎖被釋放時，控制器從等待的進程排隊中選出當(dāng)該鎖被釋放時，控制器從等待的進程排隊中選出q 一個運用鎖，這可以經(jīng)過更新所選進程一個運用鎖，這可以經(jīng)過更新所選進程CacheCache

31、中的中的q 鎖變量來完成。鎖變量來完成。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝例例7.5 7.5 假設(shè)在排隊鎖的運用中，失效時進展鎖更新，假設(shè)在排隊鎖的運用中，失效時進展鎖更新，求求1010個處置器完成個處置器完成locklock和和unlockunlock所需的時間和總線事所需的時間和總線事務(wù)數(shù)。假設(shè)條件與前面例子一樣。務(wù)數(shù)。假設(shè)條件與前面例子一樣。解解 對對n n個處置器，每個處置器都初始加鎖產(chǎn)生個處置器，每個處置器都初始加鎖產(chǎn)生1 1個總個總線事務(wù)，其中線事務(wù)，其中1 1個勝利獲得鎖并在運用后釋放鎖，第個勝利獲得鎖并在運用后釋放鎖，第1 1個處置器將有個處置器將有n+1n+1個

32、總線事務(wù)。每一個后續(xù)的處置器需個總線事務(wù)。每一個后續(xù)的處置器需求求2 2個總線事務(wù)：個總線事務(wù)：1 1個獲得鎖個獲得鎖 ，另，另1 1個釋放鎖。因此總個釋放鎖。因此總線事務(wù)的總數(shù)為線事務(wù)的總數(shù)為(n+1)+2(n-1)=3n-1(n+1)+2(n-1)=3n-1。留意這里的總線。留意這里的總線事務(wù)總數(shù)隨處置器數(shù)量成線性增長，而不是前面旋轉(zhuǎn)事務(wù)總數(shù)隨處置器數(shù)量成線性增長，而不是前面旋轉(zhuǎn)鎖那樣成二次方增長。對鎖那樣成二次方增長。對10 10 個處置器，共需求個處置器，共需求2929個總個總線事務(wù)或線事務(wù)或29002900個時鐘周期。個時鐘周期。7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝q 首

33、先，需求識別出對鎖進展初次訪問的進程，首先，需求識別出對鎖進展初次訪問的進程，q 從而對其進展排隊操作。從而對其進展排隊操作。q 第二，等待進程隊列可經(jīng)過多種機制實現(xiàn)，在第二，等待進程隊列可經(jīng)過多種機制實現(xiàn)，在q 基于目錄的機器中，隊列為共享集合，需用類基于目錄的機器中，隊列為共享集合，需用類 q 似目錄向量的硬件來實現(xiàn)排隊鎖的操作。似目錄向量的硬件來實現(xiàn)排隊鎖的操作。q 最后，必需有硬件來回收鎖，由于懇求加鎖的最后，必需有硬件來回收鎖，由于懇求加鎖的q 進程能夠被切換時切出，并且有能夠在同一處進程能夠被切換時切出，并且有能夠在同一處q 理器上不再被調(diào)度切入。理器上不再被調(diào)度切入。 q 排隊鎖功能實現(xiàn)中有一些要思索的關(guān)鍵問題7.5 同 步2006年2月秦杰 鄭麗萍 張慶輝 為減少柵欄記數(shù)時所需的時間，從而減小瓶頸為減少柵欄記數(shù)時