同步通常是使用硬件提供的有關(guān)同步指令通過用戶級軟.ppt

1、7.5 同 步 通常是使用硬件提供的有關(guān)同步指令，通過用戶級軟件例程建立的。 7.5.1 基本硬件原語 在多處理器同步中，主要功能是一組能自動(dòng)讀出后并進(jìn)行寫存儲單元的硬件原語。它們能夠自動(dòng)讀修改單元。通常情況下，用戶不直接使用基本的硬件原語，原語主要供系統(tǒng)程序員用來編制同步庫函數(shù)。,第章 多處理機(jī),功能：將一個(gè)存儲單元的值和一個(gè)寄存器的值 進(jìn)行交換。建立一個(gè)鎖，鎖值為“0”表示開鎖， 為“1”表示上鎖。 處理器加鎖時(shí)，將對應(yīng)于該鎖的存儲單元的值 交換為某個(gè)寄存器的值“1”。如果返回值為“0”， 存儲單元的值此時(shí)已置換為“1”，防止了別的進(jìn) 程競爭該鎖。 實(shí)現(xiàn)同步的關(guān)鍵: 操作的原子性,1. 典

2、型操作:原子交換（atomic exchange）,7.5 同 步,2. 測試并置定（test_and_set） 先測試一個(gè)值，如果符合條件則修改其值。 3. 讀取并加1（fetch_and_increment） 它返回存儲單元的值并自動(dòng)增加該值。 4. 使用指令對,LL(load linked或load locked)的取指令 SC(store conditional)的特殊存指令,7.5 同 步,例實(shí)現(xiàn)對由R1指出的存儲單元進(jìn)行原子交換操作 try：mov R3,R4 ；送交換值 ll R2,0(R1) ；load linked sc R3,0(R1) ；store conditional

3、 beqz R3,try ；存失敗轉(zhuǎn)移 mov R4,R2 ；將取的值送往R4 最終R4和由R1指向的單元值進(jìn)行原子交換，在ll和sc之間如有別的處理器插入并修改了存儲單元的值，sc將返回“0”并存入R3中，從而使指令序列再重新循環(huán)。,7.5 同 步,llsc機(jī)制的一個(gè)優(yōu)點(diǎn)：可用來構(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 ；存失敗轉(zhuǎn)移 指令對的實(shí)現(xiàn)必須跟蹤地址 由ll指令指定一個(gè)寄存器，該

4、寄存器存放著一個(gè) 單元地址，這個(gè)寄存器常稱為連接寄存器。,7.5 同 步,7.5.2 用一致性實(shí)現(xiàn)鎖,采用多處理機(jī)的一致性機(jī)制來實(shí)現(xiàn)旋轉(zhuǎn)鎖。 旋轉(zhuǎn)鎖 處理器環(huán)繞一個(gè)鎖不停地旋轉(zhuǎn)而請求獲得該鎖。,1. 無Cache一致性機(jī)制 在存儲器中保存鎖變量，處理器可以不斷地通 過一個(gè)原子操作請求加鎖，比如先交換，再測試返 回值從而知道鎖的狀況。釋放鎖的時(shí)候，處理器可 簡單地將鎖置為“0” 。,7.5 同 步,li R2，1 lockit： exch R2,0(R1) ；原子交換 bnez R2，lockit ；是否已加鎖?,2. 機(jī)器支持Cache一致性 將鎖緩沖進(jìn)入Cache，并通過一致性機(jī)制使鎖值保

5、持一致。,7.5 同 步,優(yōu)點(diǎn),可使“環(huán)繞”的進(jìn)程對本地Cache塊進(jìn)行操作； 可利用鎖訪問的局部性，即處理器最近使用過 的鎖不久又會(huì)使用。,改進(jìn)旋轉(zhuǎn)鎖(獲得第一條好處) 使其環(huán)繞過程僅對本地Cache中鎖的拷貝進(jìn)行讀， 直到它返回“0”確認(rèn)鎖可用，然后再進(jìn)行加鎖交換操 作。使用鎖完畢后新競爭又開始進(jìn)行。,7.5 同 步,lockit：lw R2，0(R1) ；取鎖值 bnez R2，lockit ；鎖不可用 li R2，1 ；存入鎖值 exch R2，0(R1) ；交換 bnez R2，lockit ;如鎖不為0轉(zhuǎn)移 上面給出了對于三個(gè)處理器競爭鎖的操作。一旦處理器存入“0”釋放鎖，所有別的

6、Cache對應(yīng)塊均被作廢，必須取新的值來更新它們鎖的拷貝。 一個(gè)處理器Cache會(huì)先獲得未加鎖值并執(zhí)行交換操作，當(dāng)別的Cache失效處理完后，它們會(huì)發(fā)現(xiàn)已被加鎖，所以又必須不停地測試環(huán)繞。,7.5 同 步,表7.5 三個(gè)處理機(jī)對鎖的使用,7.5 同 步,llsc原語的另一個(gè)狀態(tài)：讀寫操作明顯分開。 Ll不產(chǎn)生總線數(shù)據(jù)傳送，這使下面代碼與使用經(jīng) 過優(yōu)化交換的代碼具有相同的特點(diǎn)： lockit： ll R2，0(R1) ；load-linked bnez R2，lockit ；鎖無效 li R2,，1 ；加鎖值 sc R2，0(R1) ；存 beqz R2，lockit ；如存失敗轉(zhuǎn)移 第一個(gè)分支

7、形成環(huán)繞的循環(huán)體，第二個(gè)分支解決了兩個(gè)同時(shí)請求鎖的處理器競爭問題。盡管旋轉(zhuǎn)鎖機(jī)制簡單并且具有強(qiáng)制性，但難以將它擴(kuò)展到處理器數(shù)量很多的情況。,7.5 同 步,7.5.3 同步性能問題 簡單旋轉(zhuǎn)鎖不能很好地適應(yīng)可伸縮性。大規(guī)模機(jī)器 中所有的處理器會(huì)產(chǎn)生出大量的競爭問題。 例7.3：設(shè)總線上有10個(gè)處理器同時(shí)準(zhǔn)備對同一變量加鎖。假設(shè)每個(gè)總線事務(wù)處理(讀失效或?qū)懯?是100個(gè)時(shí)鐘周期，忽略實(shí)際的Cache塊鎖的讀寫時(shí)間以及加鎖的時(shí)間，求10個(gè)處理器請求加鎖所需的總線事務(wù)數(shù)目。設(shè)時(shí)間為0時(shí)鎖已釋放并且所有處理器在旋轉(zhuǎn)，求處理這10個(gè)請求時(shí)間為多長?假設(shè)總線在新的請求到達(dá)之前已服務(wù)完掛起的所有請求，并且

8、處理器速度相同。,7.5 同 步,解 當(dāng)i個(gè)處理器競爭鎖的時(shí)候，他們完成下列操作序列，每一個(gè)操作產(chǎn)生一個(gè)總線事務(wù)： 訪問該鎖的i個(gè)LL指令操作； 試圖鎖住該鎖的i個(gè)SC指令操作； 1個(gè)釋放鎖的存操作指令。 因此對n個(gè)處理器，總線事務(wù)的總和為： n (2i+1)=n(n+1)+n=n2+2n i=1 對于10個(gè)處理器有120個(gè)總線事務(wù)，需要12000個(gè)時(shí)鐘周期。,7.5 同 步, 本例中問題的根源是鎖的競爭、存儲器中鎖訪問的串行性以及總線訪問的延遲。 旋轉(zhuǎn)鎖的主要優(yōu)點(diǎn): 對于總線或網(wǎng)絡(luò)開銷較低,7.5 同 步,并行循環(huán)的程序中另一個(gè)常用的同步操作: 柵欄 柵欄強(qiáng)制所有到達(dá)的進(jìn)程進(jìn)行等待，直到全部

9、的 進(jìn)程到達(dá)柵欄，然后釋放全部的進(jìn)程，從而形成同步。,柵欄的典型實(shí)現(xiàn) 用兩個(gè)旋轉(zhuǎn)鎖 (1) 用來記錄到達(dá)柵欄的進(jìn)程數(shù) (2) 用來封鎖進(jìn)程直至最后一個(gè)進(jìn)程到達(dá)柵欄 柵欄的實(shí)現(xiàn)要不停地探測指定的變量， 直到它滿足規(guī)定的條件。 一種典型的實(shí)現(xiàn)，其中l(wèi)ock和unlock提供基本的 旋轉(zhuǎn)鎖，total是要到達(dá)柵欄的進(jìn)程總數(shù)。,7.5 同 步,Lock(counterlock)； *確保更新的原子性* if(count=0) release=0； *第一個(gè)進(jìn)程則重置release* count=count+1； *到達(dá)進(jìn)程記數(shù)* unlock(counterlock)； *釋放鎖* if(count=

10、total) *進(jìn)程全部到達(dá)* count=0； *重置計(jì)數(shù)器* release=1； *釋放進(jìn)程* else *還有進(jìn)程未到達(dá)* spin(release=1)； *等待別的進(jìn)程到達(dá)* ,7.5 同 步,對counterlock加鎖保證增量操作的原子性，變 量 count記錄著已到達(dá)柵欄的進(jìn)程數(shù)，變量 release用來封鎖進(jìn)程直到最后一個(gè)進(jìn)程到達(dá)柵欄。 實(shí)際情況中會(huì)出現(xiàn)的問題 可能反復(fù)使用一個(gè)柵欄，柵欄釋放的進(jìn)程運(yùn)行 一段后又會(huì)再次返回柵欄，這樣有可能出現(xiàn)某個(gè)進(jìn) 程永遠(yuǎn)離不開柵欄的狀況(它停在旋轉(zhuǎn)操作上)。,7.5 同 步,例如：OS調(diào)度進(jìn)程，可能一個(gè)進(jìn)程速度較快，當(dāng)它第二次到達(dá)柵欄時(shí)，第

11、一次的進(jìn)程還掛在柵欄中未能離開。這樣所有的進(jìn)程在這個(gè)柵欄的第二次使用中都處于無限等待狀態(tài)，因?yàn)檫M(jìn)程的數(shù)目永達(dá)不到total。,7.5 同 步,一種解決方法 當(dāng)進(jìn)程離開柵欄時(shí)進(jìn)行計(jì)數(shù)，在上次柵欄使用中 的所有進(jìn)程離開之前不允許任何進(jìn)程重用并初始化本 柵欄。 另一種解決辦法 sense_reversing柵欄，每個(gè)進(jìn)程均使用一個(gè)私 有變量local_sense，初始化為1。,7.5 同 步,Local_sense=! Local_sense； *local-sense取反* lock(counterlock)； *確保增加的原子性* count+； *記算到達(dá)進(jìn)程數(shù)* unlock(counter

12、lock)； *解鎖* if(count=total) *進(jìn)程全部到達(dá)* count=0； *重置計(jì)數(shù)器* release=local_sense； *釋放進(jìn)程* else *還有進(jìn)程未到達(dá)* spin(release=local_sense)； *等待信號* ,7.5 同 步,例7.4 假設(shè)總線上10個(gè)處理器同時(shí)執(zhí)行一個(gè)柵欄，設(shè)每個(gè)總線事務(wù)需100個(gè)時(shí)鐘周期，忽略Cache塊中鎖的讀、寫實(shí)際花費(fèi)的時(shí)間，以及柵欄實(shí)現(xiàn)中非同步操作的時(shí)間，計(jì)算10個(gè)處理器全部到達(dá)柵欄，被釋放及離開柵欄所需的總線事務(wù)數(shù)。設(shè)總線完全公平，整個(gè)過程需多長時(shí)間? 答：下表給出一個(gè)處理器通過柵欄發(fā)出的事件序列，設(shè)第一個(gè)獲得

13、總線的進(jìn)程并未擁有鎖。 ,7.5 同 步,表7.6 第i個(gè)處理器通過柵欄產(chǎn)生的事件序列 事件 數(shù)量 對應(yīng)源代碼 說明 LL i Lock(counterlock)； 所有處理器搶鎖 SC i Lock(counterlock)； 所有處理器搶鎖 LD 1 count=count+1； 一個(gè)成功 LL i-1 Lock(counterlock)； 不成功的處理器再次搶鎖 SD 1 count=count+1； 獲得專有訪問產(chǎn)生的失效 SD 1 unlock(counterlock)； 獲得鎖產(chǎn)生的失效 LD 2 spin(release=local_sense)；讀釋放：初次和最后寫產(chǎn) 生的失效

14、,7.5 同 步,當(dāng)競爭不激烈且同步操作較少時(shí)，我們主要關(guān)心的 是一個(gè)同步原語操作的延遲。 基本的旋轉(zhuǎn)鎖操作可在兩個(gè)總線周期內(nèi)完成： 一個(gè)讀鎖，一個(gè)寫鎖。我們可用多種方法改進(jìn)形成 在一個(gè)單周期內(nèi)完成操作。 同步操作最嚴(yán)重的問題：進(jìn)程的串行性 當(dāng)出現(xiàn)競爭時(shí)，就會(huì)出現(xiàn)串行性問題。它極大 地增加了同步操作的時(shí)間。 總線的使用是這個(gè)問題關(guān)鍵所在。 在基于目錄的Cache一致性機(jī)器中，串行性問題也 同樣嚴(yán)重。,7.5 同 步,7.5.4 大規(guī)模機(jī)器的同步 所希望的同步機(jī)制：在無競爭的條件下延遲較小 在競爭激烈時(shí)串行性小 1. 軟件實(shí)現(xiàn) 旋轉(zhuǎn)鎖 (1) 旋轉(zhuǎn)鎖實(shí)現(xiàn)的主要問題 當(dāng)多個(gè)進(jìn)程檢測并競爭鎖時(shí)引起的

15、延遲 (2) 一種解決辦法: 當(dāng)加鎖失敗時(shí)就人為地推延 這些進(jìn)程的等待時(shí)間。 (3) 具有指數(shù)延遲的旋轉(zhuǎn)鎖代碼,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 ；存成功轉(zhuǎn)移 sll R3，R3，1 ；將延遲時(shí)間增至2倍 pause R3 ；延遲R3中時(shí)間值 j lockit gotit： 使用加鎖保護(hù)的數(shù)據(jù) 當(dāng)sc失敗時(shí)，進(jìn)程推延R3個(gè)時(shí)間單位。,7.5 同

16、步,先討論采用數(shù)組進(jìn)行的軟件實(shí)現(xiàn)。為此我們給出一種更好的柵欄實(shí)現(xiàn)代碼。 前面柵欄機(jī)制實(shí)現(xiàn)中，所有的進(jìn)程必須讀取 release標(biāo)志，形成沖突。 通過組合樹來減小沖突 組合樹是多個(gè)請求在局部結(jié)合起來形成樹的一 種分級結(jié)構(gòu)。 降低沖突的原因：將大沖突化解成為并行的多 個(gè)小沖突。,鎖實(shí)現(xiàn)的另一種技術(shù)是排隊(duì)鎖,7.5 同 步,組合樹采用預(yù)定義的n叉樹結(jié)構(gòu) 用變量k表示扇入數(shù)目，實(shí)際中k=4效果較 好。當(dāng)k個(gè)進(jìn)程都到達(dá)樹的某個(gè)結(jié)點(diǎn)時(shí)，則發(fā) 信號進(jìn)入樹的上一層。 當(dāng)全部進(jìn)程到達(dá)的信號匯集在根結(jié)點(diǎn)時(shí)，釋放 所有的進(jìn)程。 采用sense_reversing技術(shù)來給出下面的基于 組合樹的柵欄代碼。,7.5 同

17、步,struct node *組合樹中一個(gè)結(jié)點(diǎn)* int counterlock；int count ；int parent； struct node tree 0.p-1； *樹中各結(jié)點(diǎn)* int local_sense；int release； barrier(int mynode) lock(treemynode.counterlock)；*保護(hù)計(jì)數(shù)器* count+； *計(jì)數(shù)的累加* unlock(treemynode.conterlock)；*解鎖* if(treemynode.count=k) *本結(jié)點(diǎn)全部到達(dá)* if(treemynode.parent)=0 barrier(tr

18、eemynode.parent)； elserelease=local_sense； treemynode.count0； *為下次重用初始化* else spin(release=local_sense)； local_sense= ! local_sense；barrier (mynode)；,7.5 同 步,2. 硬件原語支持 介紹兩種硬件同步原語：,(1) 排隊(duì)鎖 可以排隊(duì)記錄等待的進(jìn)程，當(dāng)鎖釋放時(shí)送 出一個(gè)已確定的等待進(jìn)程。,第一個(gè)針對鎖 第二個(gè)針對柵欄和要求進(jìn)行計(jì)數(shù)或提供明確索 引的某些用戶級操作,7.5 同 步,硬件實(shí)現(xiàn),在基于目錄的機(jī)器上，通過硬件向量等方式 來進(jìn)行排隊(duì)和同步控

19、制。 在基于總線的機(jī)器中要將鎖從一個(gè)進(jìn)程顯式 地傳給另一個(gè)進(jìn)程，軟件實(shí)現(xiàn)會(huì)更好一些。,在第一次取鎖變量失效時(shí)，失效被送入同步控 制器。同步控制器可集成在存儲控制器中(基 于總線的系統(tǒng))或集成在目錄控制器中。,排隊(duì)鎖的工作過程,7.5 同 步,如果鎖空閑，將其交給該處理器；如果鎖忙，控制 器產(chǎn)生一個(gè)結(jié)點(diǎn)請求記錄，并將鎖忙的標(biāo)志返回給 處理器，然后該處理器不停地進(jìn)行檢測。 當(dāng)該鎖被釋放時(shí)，控制器從等待的進(jìn)程排隊(duì)中選出 一個(gè)使用鎖，這可以通過更新所選進(jìn)程Cache中的 鎖變量來完成。,7.5 同 步,例7.5 如果在排隊(duì)鎖的使用中，失效時(shí)進(jìn)行鎖更新，求10個(gè)處理器完成lock和unlock所需的時(shí)間

20、和總線事務(wù)數(shù)。假設(shè)條件與前面例子相同。 解 對n個(gè)處理器，每個(gè)處理器都初始加鎖產(chǎn)生1個(gè)總線事務(wù)，其中1個(gè)成功獲得鎖并在使用后釋放鎖，第1個(gè)處理器將有n+1個(gè)總線事務(wù)。每一個(gè)后續(xù)的處理器需要2個(gè)總線事務(wù)：1個(gè)獲得鎖 ，另1個(gè)釋放鎖。因此總線事務(wù)的總數(shù)為(n+1)+2(n-1)=3n-1。注意這里的總線事務(wù)總數(shù)隨處理器數(shù)量成線性增長，而不是前面旋轉(zhuǎn)鎖那樣成二次方增長。對10 個(gè)處理器，共需要29個(gè)總線事務(wù)或2900個(gè)時(shí)鐘周期。,7.5 同 步,首先，需要識別出對鎖進(jìn)行初次訪問的進(jìn)程， 從而對其進(jìn)行排隊(duì)操作。 第二，等待進(jìn)程隊(duì)列可通過多種機(jī)制實(shí)現(xiàn)，在 基于目錄的機(jī)器中，隊(duì)列為共享集合，需用類 似目錄向量的硬件來實(shí)現(xiàn)排隊(duì)鎖的操作。 最后，必須有硬件來回收鎖，因?yàn)檎埱蠹渔i的 進(jìn)程可能被切換時(shí)切出，并且有可能在同一處 理器上不再被調(diào)度切入。,排