1、7.5 同 步 通常是運用硬件提供的有關同步指令，經過用戶級軟件例程建立的。 7.5.1 根本硬件原語 在多處置器同步中，主要功能是一組能自動讀出后并進展寫存儲單元的硬件原語。它們可以自動讀修正單元。通常情況下，用戶不直接運用根本的硬件原語，原語主要供系統程序員用來編制同步庫函數。 第章 多處置機 功能：將一個存儲單元的值和一個存放器的值 進展交換。建立一個鎖，鎖值為“0表示開鎖， 為“1表示上鎖。 處置器加鎖時，將對應于該鎖的存儲單元的值 交換為某個存放器的值“1。假設前往值為“0， 存儲單元的值此時已置換為“1，防止了別的進 程競爭該鎖。 實現同步的關鍵: 操作的原子性1. 典型操作:原子

2、交換atomic exchange7.5 同 步2. 測試并置定test_and_set 先測試一個值，假設符合條件那么修正其值。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 同 步例實現對由例實現對由R1R1指出的存儲單元進展原子交換操作指出的存儲單元進展原子交換操作 try try：m

3、ov 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 ；存失敗轉移；存失敗轉移 mov R4,R2 mov R4,R2 ；將取的值送往；將取的值送往R4R4 最終最終R4R4和由和由R1R1指向的單元值進展原子交換，在指向的單元值進展原子交換，在llll和和scsc之間如有別的處置器插入并修正了存儲單元的值，之間如有別的處置器插

4、入并修正了存儲單元的值，scsc將前往將前往“0 0并存入并存入R3R3中，從而使指令序列再重新循環。中，從而使指令序列再重新循環。7.5 同 步 llsc機制的一個優點：可用來構造別的同步原語 例如：原子的fetch-and-increment try： ll R2,0(R1) ；load linked addi R2,R2,1 ；添加 sc R2,0(R1) ；store conditional beqz R2,try ；存失敗轉移 指令對的實現必需跟蹤地址 由ll指令指定一個存放器，該存放器存放著一個 單元地址，這個存放器常稱為銜接存放器。7.5 同 步7.5.2 用一致性實現鎖 采用多

5、處置機的一致性機制來實現旋轉鎖。 旋轉鎖 處置器環繞一個鎖不停地旋轉而懇求獲得該鎖。1. 無Cache一致性機制 在存儲器中保管鎖變量，處置器可以不斷地通 過一個原子操作懇求加鎖，比如先交換，再測試返 回值從而知道鎖的情況。釋放鎖的時候，處置器可 簡單地將鎖置為“0 。 7.5 同 步 li R2 li R2，1 1lockitlockit： exch R2,0(R1) exch R2,0(R1) ；原子交；原子交換換 bnez R2bnez R2，lockit lockit ；能否已；能否已加鎖加鎖? ?2. 機器支持Cache一致性 將鎖緩沖進入Cache，并經過一致性機制使鎖值保 持一致

6、。 7.5 同 步 優點q 可使可使“環繞的進程對本地環繞的進程對本地CacheCache塊進展操作；塊進展操作；q 可利用鎖訪問的部分性，即處置器最近運用過可利用鎖訪問的部分性，即處置器最近運用過 q 的鎖不久又會運用。的鎖不久又會運用。 改良旋轉鎖(獲得第一條益處) 使其環繞過程僅對本地Cache中鎖的拷貝進展讀， 直到它前往“0確認鎖可用，然后再進展加鎖交換操 作。運用鎖終了后新競爭又開場進展。7.5 同 步 lockit：lw R2，0(R1) ；取鎖值 bnez R2，lockit ；鎖不可用 li R2，1 ；存入鎖值 exch R2，0(R1) ；交換 bnez R2，locki

7、t ;如鎖不為0轉移 上面給出了對于三個處置器競爭鎖的操作。一旦處置器存入“0釋放鎖，一切別的Cache對應塊均被作廢，必需取新的值來更新它們鎖的拷貝。 一個處置器Cache會先獲得未加鎖值并執行交換操作，當別的Cache失效處置完后，它們會發現已被加鎖，所以又必需不停地測試環繞。7.5 同 步表表7.5 7.5 三個處置機對鎖的運用三個處置機對鎖的運用步驟步驟 處置器處置器P0處置器處置器P1處置器處置器P2鎖形狀鎖形狀總線總線/目錄操作目錄操作1占有鎖占有鎖環繞測試環繞測試lock=0環繞測試環繞測試lock=0Shared無無2將鎖置為將鎖置為0收到作廢命令收到作廢命令(收到作廢命令收到

8、作廢命令)ExclusiveP0發鎖變量作廢音訊發鎖變量作廢音訊3 Cache失效失效Cache失效失效Shared總線總線/目錄處置目錄處置P2 Cache失效失效,鎖從鎖從P0寫回寫回4 總線總線/目錄忙那么目錄忙那么等待等待Lock=0SharedP2 Cache失效處置失效處置5 Lock=0執行交換，導執行交換，導致致 Cache失效失效SharedP1Cache失效處置失效處置6 執行交換，導致執行交換，導致 Cache失效失效 交換終了，前交換終了，前往往0置置lock=1Exclusive總線總線/目錄處置目錄處置P2 Cache失效失效,發作廢音訊發作廢音訊7 交換終了，前往

9、交換終了，前往1進入關鍵處置進入關鍵處置段段Shared總線總線/目錄處置目錄處置P2 Cache失效，寫回失效，寫回8 環繞測試環繞測試lock=0 無無7.5 同 步 llsc原語的另一個形狀：讀寫操作明顯分開。 Ll不產生總線數據傳送，這使下面代碼與運用經 過優化交換的代碼具有一樣的特點： lockit： ll R2，0(R1) ；load-linked bnez R2，lockit ；鎖無效 li R2,，1 ；加鎖值 sc R2，0(R1) ；存 beqz R2，lockit ；如存失敗轉移 第一個分支構成環繞的循環體，第二個分支處理了兩個同時懇求鎖的處置器競爭問題。雖然旋轉鎖機制簡

10、單并且具有強迫性，但難以將它擴展四處置器數量很多的情況。7.5 同 步7.5.3 同步性能問題 簡單旋轉鎖不能很好地順應可伸縮性。大規模機器 中一切的處置器會產生出大量的競爭問題。 例7.3：設總線上有10個處置器同時預備對同一變量加鎖。假設每個總線事務處置(讀失效或寫失效)是100個時鐘周期，忽略實踐的Cache塊鎖的讀寫時間以及加鎖的時間，求10個處置器懇求加鎖所需的總線事務數目。設時間為0時鎖已釋放并且一切處置器在旋轉，求處置這10個懇求時間為多長?假設總線在新的懇求到達之前已效力完掛起的一切懇求，并且處置器速度一樣。7.5 同 步解解 當當i i個處置器競爭鎖的時候，他們完成以下操個處

11、置器競爭鎖的時候，他們完成以下操作序列，每一個操作產生一個總線事務：作序列，每一個操作產生一個總線事務： 訪問該鎖的訪問該鎖的i i個個LLLL指令操作；指令操作； 試圖鎖住該鎖的試圖鎖住該鎖的i i個個SCSC指令操作；指令操作； 1 1個釋放鎖的存操作指令。個釋放鎖的存操作指令。因此對因此對n n個處置器，總線事務的總和為：個處置器，總線事務的總和為： n n (2i+1)=n(n+1)+n=n2+2n (2i+1)=n(n+1)+n=n2+2n i=1 i=1對于對于1010個處置器有個處置器有120120個總線事務，需求個總線事務，需求1200012000個時個時鐘周期。鐘周期。 7.

12、5 同 步 本例中問題的根源是鎖的競爭、存儲器中本例中問題的根源是鎖的競爭、存儲器中鎖訪問的串行性以及總線訪問的延遲。鎖訪問的串行性以及總線訪問的延遲。 旋轉鎖的主要優點旋轉鎖的主要優點: : 對于總線或網絡對于總線或網絡開銷較低開銷較低7.5 同 步q 并行循環的程序中另一個常用的同步操作: 柵欄q 柵欄強迫一切到達的進程進展等待，直到全部的q 進程到達柵欄，然后釋放全部的進程，從而構成同步。 柵欄的典型實現柵欄的典型實現 用兩個旋轉鎖用兩個旋轉鎖 (1) (1) 用來記錄到達柵欄的進程數用來記錄到達柵欄的進程數 (2) (2) 用來封鎖進程直至最后一個進程到達柵欄用來封鎖進程直至最后一個進

13、程到達柵欄 柵欄的實現要不停地探測指定的變量，柵欄的實現要不停地探測指定的變量， 直到它滿足規定的條件。直到它滿足規定的條件。 一種典型的實現，其中一種典型的實現，其中locklock和和unlockunlock提供根本的提供根本的 旋轉鎖，旋轉鎖，totaltotal是要到達柵欄的進程總數。是要到達柵欄的進程總數。7.5 同 步Lock(counterlock)Lock(counterlock)； * *確保更新的原子性確保更新的原子性* *if(count=0) release=0if(count=0) release=0； * *第一個進程那么重置第一個進程那么重置releaserele

14、ase* *count=count+1count=count+1； * *到達進程記數到達進程記數* *unlock(counterlock)unlock(counterlock)； * *釋放鎖釋放鎖* *if(count=total) if(count=total) * *進程全部到達進程全部到達* * count=0count=0； * *重置計數器重置計數器* * release=1release=1； * *釋放進程釋放進程* * else else * *還有進程未到達還有進程未到達* * spin(release=1)spin(release=1)； * *等待別的進程到達等待別

15、的進程到達* * 7.5 同 步 對counterlock加鎖保證增量操作的原子性，變 量 count記錄著已到達柵欄的進程數，變量 release用來封鎖進程直到最后一個進程到達柵欄。 實踐情況中會出現的問題 能夠反復運用一個柵欄，柵欄釋放的進程運轉 一段后又會再次前往柵欄，這樣有能夠出現某個進 程永遠離不開柵欄的情況(它停在旋轉操作上)。7.5 同 步 例如：例如：OSOS調度進程，能夠一個進程速度較快，調度進程，能夠一個進程速度較快，當它第二次到達柵欄時，第一次的進程還掛在柵欄當它第二次到達柵欄時，第一次的進程還掛在柵欄中未能分開。這樣一切的進程在這個柵欄的第二次中未能分開。這樣一切的進

16、程在這個柵欄的第二次運用中都處于無限等待形狀，由于進程的數目永達運用中都處于無限等待形狀，由于進程的數目永達不到不到totaltotal。7.5 同 步q 一種處理方法一種處理方法q 當進程分開柵欄時進展計數，在上次柵欄運用中當進程分開柵欄時進展計數，在上次柵欄運用中q 的一切進程分開之前不允許任何進程重用并初始化本的一切進程分開之前不允許任何進程重用并初始化本q 柵欄。柵欄。q 另一種處理方法另一種處理方法q sense_reversingsense_reversing柵欄，每個進程均運用一個私柵欄，每個進程均運用一個私q 有變量有變量local_senselocal_sense，初始化為，

17、初始化為1 1。7.5 同 步Local_sense=! Local_senseLocal_sense=! Local_sense； * *local-senselocal-sense取反取反* *lock(counterlock)lock(counterlock)； * *確保添加的原子確保添加的原子性性* *count+count+； * *記算到達進程數記算到達進程數* *unlock(counterlock)unlock(counterlock)； * *解鎖解鎖* *if(count=total) if(count=total) * *進程全部到達進程全部到達* * count=0c

18、ount=0； * *重置計數器重置計數器* * release=local_senserelease=local_sense； * *釋放進程釋放進程* * else else * *還有進程未到達還有進程未到達* * spin(release=local_sense)spin(release=local_sense)； * *等待信等待信號號* * 7.5 同 步例例7.4 7.4 假設總線上假設總線上1010個處置器同時執行一個柵欄，設個處置器同時執行一個柵欄，設每個總線事務需每個總線事務需100100個時鐘周期，忽略個時鐘周期，忽略CacheCache塊中鎖的塊中鎖的讀、寫實踐破費的時

19、間，以及柵欄實現中非同步操作讀、寫實踐破費的時間，以及柵欄實現中非同步操作的時間，計算的時間，計算1010個處置器全部到達柵欄，被釋放及分個處置器全部到達柵欄，被釋放及分開柵欄所需的總線事務數。設總線完全公平，整個過開柵欄所需的總線事務數。設總線完全公平，整個過程需多長時間程需多長時間? ?答：下表給出一個處置器經過柵欄發出的事件序列，答：下表給出一個處置器經過柵欄發出的事件序列，設第一個獲得總線的進程并未擁有鎖。設第一個獲得總線的進程并未擁有鎖。7.5 同 步 表表7.6 第第i個處置器經過柵欄產生的事件序列個處置器經過柵欄產生的事件序列 事件事件 數量數量 對應源代碼對應源代碼 闡明闡明L

20、L i Lock(counterlock)； 一切處置器搶鎖一切處置器搶鎖SC i Lock(counterlock)； 一切處置器搶鎖一切處置器搶鎖LD 1 count=count+1； 一個勝利一個勝利LL i-1 Lock(counterlock)； 不勝利的處置器再次搶不勝利的處置器再次搶鎖鎖SD 1 count=count+1； 獲得專有訪問產生的失效獲得專有訪問產生的失效SD 1 unlock(counterlock)； 獲得鎖產生的失效獲得鎖產生的失效LD 2 spin(release=local_sense)；讀釋放：初次和最后；讀釋放：初次和最后寫產寫產 生的失效生的失效7.

21、5 同 步q 當競爭不猛烈且同步操作較少時，我們主要關懷的q 是一個同步原語操作的延遲。q 根本的旋轉鎖操作可在兩個總線周期內完成：q 一個讀鎖，一個寫鎖。我們可用多種方法改良構成q 在一個單周期內完成操作。q 同步操作最嚴重的問題：進程的串行性q 當出現競爭時，就會出現串行性問題。它極大q 地添加了同步操作的時間。q 總線的運用是這個問題關鍵所在。q 在基于目錄的Cache一致性機器中，串行性問題也q 同樣嚴重。7.5 同 步7.5.4 大規模機器的同步所希望的同步機制：在無競爭的條件下延遲較小 在競爭猛烈時串行性小1. 軟件實現 旋轉鎖 (1) 旋轉鎖實現的主要問題 當多個進程檢測并競爭鎖

22、時引起的延遲 (2) 一種處理方法: 當加鎖失敗時就人為地推遲 這些進程的等待時間。 (3) 具有指數延遲的旋轉鎖代碼7.5 同 步 li R3，1 ；R3初始延遲值；lockit： ll R2，0(R1) ；load linked bnez R2，lockit ；無效 addi R2，R2，1 ；取到加鎖值 sc R2，0(R1) ；store conditional bnez R2，gotit ；存勝利轉移 sll R3，R3，1 ；將延遲時間增至2倍 pause R3 ；延遲R3中時間值 j lockitgotit： 運用加鎖維護的數據 當sc失敗時，進程推遲R3個時間單位。7.5 同

23、步 先討論采用數組進展的軟件實現。為此我們給出一種更好的柵欄實現代碼。 前面柵欄機制實現中，一切的進程必需讀取 release標志，構成沖突。 經過組合樹來減小沖突 組合樹是多個懇求在部分結合起來構成樹的一 種分級構造。 降低沖突的緣由：將大沖突化解成為并行的多 個小沖突。 鎖實現的另一種技術是排隊鎖7.5 同 步q 組合樹采用預定義的組合樹采用預定義的n n叉樹構造叉樹構造q 用變量用變量k k表示扇入數目，實踐中表示扇入數目，實踐中k=4k=4效果較效果較q 好。當好。當k k個進程都到達樹的某個結點時，那么個進程都到達樹的某個結點時，那么發發q 信號進入樹的上一層。信號進入樹的上一層。q

24、 當全部進程到達的信號聚集在根結點時，釋放當全部進程到達的信號聚集在根結點時，釋放q 一切的進程。一切的進程。q 采用采用sense_reversingsense_reversing技術來給出下面的基于技術來給出下面的基于q 組合樹的柵欄代碼。組合樹的柵欄代碼。7.5 同 步struct node struct node * *組合樹中一個結點組合樹中一個結點* * int counterlockint counterlock；int count int count ；int parentint parent； struct node tree struct node tree 0.p-10.

25、p-1； * *樹中各結點樹中各結點* * int local_senseint local_sense；int releaseint release； barrier(int mynode) barrier(int mynode) lock(treemynode.counterlock)lock(treemynode.counterlock)；* *維護計數器維護計數器* * count+count+； * *計數的累加計數的累加* * unlock(treemynode.conterlock)unlock(treemynode.conterlock)；* *解鎖解鎖* * if(treem

26、ynode.count=k)if(treemynode.count=k) * *本結點全部到達本結點全部到達* * if(treemynode.parent)=0if(treemynode.parent)=0 barrier(treemynodebarrier(treemynode.parent).parent)； elseelserelease=local_senserelease=local_sense； treemynode.counttreemynode.count0 0； * *為下次重用初始化為下次重用初始化* * else else spin(release=local_sens

27、e)spin(release=local_sense)； local_sense= ! local_senselocal_sense= ! local_sense；barrier (mynode)barrier (mynode)；7.5 同 步2. 硬件原語支持 引見兩種硬件同步原語：(1) 排隊鎖 可以排隊記錄等待的進程，當鎖釋放時送 出一個已確定的等待進程。 第一個針對鎖 第二個針對柵欄和要求進展計數或提供明確索 引的某些用戶級操作7.5 同 步q 硬件實現q 在基于目錄的機器上，經過硬件向量等方式q 來進展排隊和同步控制。q 在基于總線的機器中要將鎖從一個進程顯式q 地傳給另一個進程，軟

28、件實現會更好一些。q 在第一次取鎖變量失效時，失效被送入同步控在第一次取鎖變量失效時，失效被送入同步控q 制器。同步控制器可集成在存儲控制器中制器。同步控制器可集成在存儲控制器中( (基基 q 于總線的系統于總線的系統) )或集成在目錄控制器中。或集成在目錄控制器中。q 排隊鎖的任務過程7.5 同 步q 假設鎖空閑，將其交給該處置器；假設鎖忙，控制假設鎖空閑，將其交給該處置器；假設鎖忙，控制q 器產生一個結點懇求記錄，并將鎖忙的標志前往器產生一個結點懇求記錄，并將鎖忙的標志前往給給q 處置器，然后該處置器不停地進展檢測。處置器，然后該處置器不停地進展檢測。q 當該鎖被釋放時，控制器從等待的進程

29、排隊中選出當該鎖被釋放時，控制器從等待的進程排隊中選出q 一個運用鎖，這可以經過更新所選進程一個運用鎖，這可以經過更新所選進程CacheCache中的中的q 鎖變量來完成。鎖變量來完成。7.5 同 步例例7.5 7.5 假設在排隊鎖的運用中，失效時進展鎖更新，假設在排隊鎖的運用中，失效時進展鎖更新，求求1010個處置器完成個處置器完成locklock和和unlockunlock所需的時間和總線事所需的時間和總線事務數。假設條件與前面例子一樣。務數。假設條件與前面例子一樣。解解 對對n n個處置器，每個處置器都初始加鎖產生個處置器，每個處置器都初始加鎖產生1 1個總個總線事務，其中線事務，其中1

30、 1個勝利獲得鎖并在運用后釋放鎖，第個勝利獲得鎖并在運用后釋放鎖，第1 1個處置器將有個處置器將有n+1n+1個總線事務。每一個后續的處置器需個總線事務。每一個后續的處置器需求求2 2個總線事務：個總線事務：1 1個獲得鎖個獲得鎖 ，另，另1 1個釋放鎖。因此總個釋放鎖。因此總線事務的總數為線事務的總數為(n+1)+2(n-1)=3n-1(n+1)+2(n-1)=3n-1。留意這里的總線。留意這里的總線事務總數隨處置器數量成線性增長，而不是前面旋轉事務總數隨處置器數量成線性增長，而不是前面旋轉鎖那樣成二次方增長。對鎖那樣成二次方增長。對10 10 個處置器，共需求個處置器，共需求2929個總個

31、總線事務或線事務或29002900個時鐘周期。個時鐘周期。7.5 同 步q 首先，需求識別出對鎖進展初次訪問的進程，首先，需求識別出對鎖進展初次訪問的進程，q 從而對其進展排隊操作。從而對其進展排隊操作。q 第二，等待進程隊列可經過多種機制實現，在第二，等待進程隊列可經過多種機制實現，在q 基于目錄的機器中，隊列為共享集合，需用類基于目錄的機器中，隊列為共享集合，需用類 q 似目錄向量的硬件來實現排隊鎖的操作。似目錄向量的硬件來實現排隊鎖的操作。q 最后，必需有硬件來回收鎖，由于懇求加鎖的最后，必需有硬件來回收鎖，由于懇求加鎖的q 進程能夠被切換時切出，并且有能夠在同一處進程能夠被切換時切出，并且有能夠在同一處q 理器上不再被調度切入。理器上不再被調度切入。 q 排隊鎖功能實現中有一些要思索的關鍵問題7.5 同 步 為減少柵欄記數時所需的時間，從而減小瓶頸為減少柵欄記數時所需的時間，從而減小瓶頸的串行度，引進一種原語的串行度