《同步與死結(jié)》ppt課件

1、第六章第六章 同步與死結(jié)同步與死結(jié)行程同步 臨界區(qū)號誌 同步的經(jīng)典問題 有限緩衝區(qū)問題 讀取者與寫入者問題 哲學(xué)家晚餐問題 臨界區(qū)域與監(jiān)督程式 死結(jié)簡介 死結(jié)預(yù)防 死結(jié)防止 摘要 同步的經(jīng)典問題同步的經(jīng)典問題牽涉到了大型並行控制的領(lǐng)域。經(jīng)常拿來測試新的同步機制的正確性。 這些問題的解法當(dāng)中都運用了號誌作為同步的工具。 有限緩衝區(qū)問題有限緩衝區(qū)問題 (The Bounded Buffer Problem) 用號誌來實作可簡單解決許多問題。 假設(shè)緩衝區(qū)中有 n 個欄位，每個欄位可以存放一個項目。運用 mutex 號誌確保管取緩衝區(qū)時的互斥條件成立，並初始化為 1。empty 和 full 兩個號誌

2、則分別用來計算緩衝區(qū)中空的與運用過的欄位數(shù)目。empty 號誌初始化為 n。full 號誌初始化為 0。 有限緩衝區(qū)問題有限緩衝區(qū)問題 ( (續(xù)續(xù)) )生產(chǎn)者和耗費者的程式碼如下： do do 產(chǎn)生一個新的項目放在產(chǎn)生一個新的項目放在 nextp nextp wait(empty); wait(empty); wait(mutex); wait(mutex); 將將 nextp nextp 參與到緩衝區(qū)中參與到緩衝區(qū)中 signal(mutex); signal(mutex); signal(full); signal(full); while(1); while(1); do do wait

3、(full); wait(full); wait(mutex); wait(mutex); 將一個項目由緩衝區(qū)中將一個項目由緩衝區(qū)中 移到移到 nextc nextc signal(mutex); signal(mutex); signal(empty); signal(empty); 耗費放在耗費放在 nextc nextc 中的項目中的項目 while(1); while(1); 生 產(chǎn) 者消 耗 者讀取者與寫入者問題讀取者與寫入者問題 (The Readers and Writers Problem) 一個系統(tǒng)中經(jīng)常會有數(shù)個行程共同分享同一份資料物件只讀取這份分享資料的行程稱為讀取者。

4、只更新分享資料的行程稱為寫入者。假設(shè)一個讀取者和一個寫入者同時存取所共享的資料，可以會發(fā)生錯誤。 這種同步的問題稱為讀取者與寫入者問題。以整數(shù) readcount 記錄正在讀取資料的讀取者數(shù)目，初始值為 0。利用初始化為 1 的 mutex 和 wrt 兩個號誌構(gòu)成兩種臨界區(qū)。 讀取者與寫入者問題讀取者與寫入者問題 ( (續(xù)續(xù)) )讀取者和寫入者問題的解法如下： wait(mutex);wait(mutex);readcount+;readcount+;if (readcount = 1)if (readcount = 1) wait(wrt); wait(wrt);signal(mutex)

5、;signal(mutex); 進行讀取進行讀取 wait(mutex); wait(mutex);readcount-;readcount-;if (readcount = 0)if (readcount = 0) signal(wrt); signal(wrt);signal(mutex); signal(mutex); wait(wrt);wait(wrt); 進行寫入進行寫入 signal(wrt); signal(wrt); 讀 取 者 寫 入 者哲學(xué)家晚餐問題哲學(xué)家晚餐問題 (1)(1)哲學(xué)家們圍坐在一張圓桌一同共進晚餐。桌上筷子數(shù)目與哲學(xué)家相等，每兩個哲學(xué)家之間共用一支筷子。哲學(xué)

6、家們會坐在餐桌上思索哲學(xué)問題。當(dāng)哲學(xué)家們想吃東西時會拿起左右各一支筷子進餐，拿齊兩支筷子的哲學(xué)家們可同時進餐，但不能搶奪別人手上的筷子。當(dāng)食物吃完後，哲學(xué)家會將兩支筷子都放下，並繼續(xù)思索哲學(xué)問題，其他哲學(xué)家可繼續(xù)用放下的筷子。 哲學(xué)家晚餐問題表示圖哲學(xué)家晚餐問題表示圖 哲學(xué)家晚餐問題哲學(xué)家晚餐問題 (2)(2)第 i 位哲學(xué)家的程式可寫成： do do wait(chopsticki); wait(chopsticki); wait(chopstick(i + 1) % 5; wait(chopstick(i + 1) % 5; 進餐進餐 signal(chopsticki); signal(

7、chopsticki); signal(chopstick(i + 1) % 5; signal(chopstick(i + 1) % 5; 思索思索 while(1); while(1); 哲學(xué)家晚餐問題哲學(xué)家晚餐問題 (2)(2)上述作法可以會導(dǎo)致死結(jié)的發(fā)生。假設(shè)每位哲學(xué)家都拿起了一支筷子而等待另一支筷子，則不會有任何一位哲學(xué)家可以拿到兩支筷子，一切的哲學(xué)家將會進入死結(jié)狀態(tài)。 以下作法可以防止哲學(xué)家晚餐問題發(fā)生死結(jié)： 在圓桌上放置 n+1 支筷子或限制最多只需 n-1 位哲學(xué)家可以同時進餐。規(guī)定哲學(xué)家們必須要同時拿起左右兩支筷子。規(guī)定奇數(shù)座位的哲學(xué)家要先拿起左方的筷子再拿起右方的筷子；而偶

8、數(shù)座位的哲學(xué)家則先拿起右方的筷子再拿起左方的筷子。第六章第六章 同步與死結(jié)同步與死結(jié)行程同步 臨界區(qū)號誌 同步的經(jīng)典問題 臨界區(qū)域與監(jiān)督程式 臨界區(qū)域 監(jiān)督程式死結(jié)簡介 死結(jié)預(yù)防死結(jié)防止摘要 臨界區(qū)域與監(jiān)督程式臨界區(qū)域與監(jiān)督程式 號誌是個非常方便而且有效率的同步工具。然而不正確地運用號誌，很容易產(chǎn)生行程之間同步上的錯誤。這類錯誤並不一定每次程式執(zhí)行時都會發(fā)生，所以很難除錯。 臨界區(qū)域(Critical Region)與監(jiān)督程式(Monitor)是另外兩種較高階的常用同步工具。運用起來較為方便，而且不容易出錯。 每個行程會有一些私有的部分變數(shù)，以及一些行程間的共享變數(shù)。行程不能夠直接存取其他行程

9、的部分變數(shù)。 臨界區(qū)域臨界區(qū)域 臨界區(qū)域的運用非常方便。 以下宣告一個具有共享變數(shù) v 的臨界區(qū)域，在 B 條件式成立下，假設(shè)沒有其他行程在此臨界區(qū)域中執(zhí)行，就會執(zhí)行 S 敘述：利用臨界區(qū)域來實作，程式設(shè)計師不用煩惱同步的問題，只需正確地把問題描畫在臨界區(qū)域內(nèi)。 有限緩衝區(qū)問題可以用臨界區(qū)域來簡單地解決同步的問題。region v when B do S; region v when B do S; 臨界區(qū)解決有限緩衝區(qū)的問題臨界區(qū)解決有限緩衝區(qū)的問題 共享的資料:struct buffer item pooln;int count, in, out;生產(chǎn)者構(gòu)成將 nextp 放共享的緩衝區(qū)r

10、egion buffer when( count 0) nextc = poolout;out = (out+1) % n;count-;臨界區(qū)域臨界區(qū)域 ( (續(xù)續(xù)) )臨界區(qū)域 region v when B do S 可利用 mutex、first_delay 及 second_delay 三個號誌實作。 mutex 號誌是用來確保臨界區(qū)的互斥條件成立。 假設(shè)行程因為 B 為 FALSE 而無法進入臨界區(qū)，該行程將會在號誌 first_delay 等待。 在號誌 first_delay 等待的行程重新檢查 B 值之前，會離開號誌 first_delay，而在號誌 second_delay

11、 等待。 分成first_delay 與 second_delay兩段式等待的緣由，是為了要防止行程持續(xù)忙碌地檢查 B 值。 當(dāng)一個行程離開了臨界區(qū)之後，可以因為執(zhí)行了敘述 S 而改變了 B 的值，所以需求重新檢查。監(jiān)督程式監(jiān)督程式 監(jiān)督程式是另外一種高階的同步工具。 對較複雜的同步問題提供了更普通性的實作工具。 由一些變數(shù)宣告及函式所組成，變數(shù)的值定義了監(jiān)督程式的狀態(tài)。 保證只需一個行程在監(jiān)督程式中執(zhí)行所定義的函式。 在監(jiān)督程式中，程式設(shè)計師不需求撰寫有關(guān)同步的程式碼，但是可以利用條件變數(shù)來定義本人的同步機制。 哲學(xué)家晚餐問題可以利用監(jiān)督程式來實作。Solution to Dining So

12、lution to Dining PhilosophersPhilosophersmonitor dp enum thinking, hungry, eating state5;condition self5;void pickup(int i) / following slidesvoid putdown(int i) / following slidesvoid test(int i) / following slidesvoid init() for (int i = 0; i 5; i+)statei = thinking;pickUp() ProcedurepickUp() Proc

13、edurevoid pickup(int i) statei = hungry;testi;if (statei != eating)selfi.wait();void putdown(int i) statei = thinking;/ test left and right neighborstest(i+4) % 5);test(i+1) % 5);test() Proceduretest() Procedurevoid test(int i) if ( (state(i + 4) % 5 != eating) & (statei = hungry) & (state(i

14、 + 1) % 5 != eating) statei = eating;selfi.signal();Solution to Dining Solution to Dining PhilosophersPhilosophersPhilosopher i must invoke the operations pickup and putdown in the following sequence:dp.pickUp(i);.eat.dp.putDown(i);This solution ensures that no two neighbors are eating simultaneousl

15、y, and no deadlocks will occur.However, it is possible for a philosopher to starve to death. 第六章第六章 同步與死結(jié)同步與死結(jié)行程同步 臨界區(qū)號誌 同步的經(jīng)典問題 臨界區(qū)域與監(jiān)督程式 死結(jié)簡介 死結(jié)特性 死結(jié)偵測 死結(jié)解除 死結(jié)預(yù)防 死結(jié)防止 摘要 死結(jié)簡介死結(jié)簡介 許多行程會共同競爭系統(tǒng)中有限的資源。 當(dāng)行程所要求的資源正被其他的行程所運用時，該行程就必須要等待。 等待的行程可以會因為所要求的資源也被其他正在等待的行程所持有，而無限期地等待，這種情形稱為死結(jié)。 死結(jié)特性死結(jié)特性 (1)(1)系統(tǒng)中行

16、程共同競爭的有限資源可以分為幾種不同的類型，而每種類型又會有不同數(shù)目的資源。 一個行程可以對一個資源進行要求、運用、釋放等 3 種動作。 行程不能要求比系統(tǒng)擁有數(shù)目更多的資源。 當(dāng)行程要求了某種資源時，作業(yè)系統(tǒng)會先檢查系統(tǒng)的資源配置表，假設(shè)該種資源都正被其他行程所運用，作業(yè)系統(tǒng)會將目前要求的這個行程參與所等待資源的等待串列中。 死結(jié)特性死結(jié)特性 (2)(2)死結(jié)的定義如下，系統(tǒng)中的每一個行程都在等待著某些資源，而這些資源卻已經(jīng)配置給其他正在等待的行程，因此一切的行程都進入無限期地等待而無法完成義務(wù)。 死結(jié)只需在以下 4 種條件都同時成立下才會發(fā)生： 互斥 佔用與等待 制止搶先 循環(huán)等待 死結(jié)特

17、性死結(jié)特性 (3)(3)我們可以運用系統(tǒng)資源配置圖來描畫系統(tǒng)中行程與資源間的狀態(tài)。 圓代表系統(tǒng)中的一個行程，圓中寫著行程的名稱。 方塊代表系統(tǒng)中的一種資源，方塊中黑點的數(shù)量表示該種資源的數(shù)目。 箭號所代表的意義有兩種。 由資源指向行程的箭號表示該資源目前被該行程所持有。 由行程指向資源的箭號則代表該行程目前正在等待該項資源。 資源配置圖資源配置圖 P1P2P3 R2 R1死結(jié)偵測死結(jié)偵測 假設(shè)系統(tǒng)中一切類型的資源都只需一項的話，我們可以利用資源配置圖來偵測死結(jié)。 利用偵測迴圈的演算法來檢查資源配置圖中能否有迴圈存在，就能知道目前系統(tǒng)中能否有死結(jié)發(fā)生。 運用這種方法的系統(tǒng)必須要持續(xù)地更新資源配置

18、圖，並且要定期地執(zhí)行偵測迴圈的演算法以偵測死結(jié)。 假設(shè)系統(tǒng)中各類型資源的數(shù)目不只一項的話，可以運用死結(jié)偵測演算法來偵測死結(jié)。 死結(jié)解除死結(jié)解除 當(dāng)偵測到死結(jié)發(fā)生，有兩種方法可以解除死結(jié)。 終止一些行程，使循環(huán)等待的條件不成立。 由發(fā)生死結(jié)的行程中回收一些資源給其他行程，使制止搶先的條件不成立。終止行程的作法中，可以選擇終止一切行程或是一次只終止一個行程，直到死結(jié)的狀態(tài)解除。 終止一切行程的作法雖然比較簡單，但是行程的義務(wù)必須重新或是部分執(zhí)行，會浪費較多的 CPU 時間。 一次終止一個行程所浪費的 CPU 時間較少，但是每終止一個行程之後都必須要執(zhí)行一次偵測死結(jié)的動作來斷定死結(jié)能否已經(jīng)解除。 死

19、結(jié)解除死結(jié)解除 ( (續(xù)續(xù)) )用回收資源的作法來解除死結(jié)，必須持續(xù)地由一些行程回收資源，並將回收的資源配置給其他的行程，直到死結(jié)的狀態(tài)解除。這個作法有幾點需求留意： 選定行程的方法回溯 飢餓現(xiàn)象 第六章第六章 同步與死結(jié)同步與死結(jié)行程同步 臨界區(qū)號誌同步的經(jīng)典問題臨界區(qū)域與監(jiān)督程式 死結(jié)簡介 死結(jié)預(yù)防 互斥 佔用與等待 制止搶先 循環(huán)等待 死結(jié)防止 摘要 死結(jié)預(yù)防死結(jié)預(yù)防 死結(jié)的發(fā)生要 4 個條件同時成立。 互斥 佔用與等待 制止搶先 循環(huán)等待只需廢除死結(jié)的任一個條件就可以預(yù)防死結(jié)的發(fā)生。 互斥互斥 互斥的條件只存在於不能共享的資源上。 如印表機不能同時列印兩份不同的文件。 可以共享的資源能

20、夠允許多個行程同時運用，因此可以共享的資源不可以呵斥死結(jié)的發(fā)生。 但是，我們無法讓不可共享的資源變成可共享，因此無法利用資源的互斥條件來預(yù)防死結(jié)的發(fā)生。 佔用與等待佔用與等待 不讓佔用與等待的情形在系統(tǒng)中發(fā)生，必須要讓一切的行程在獲得某項資源時不得先持有任何其他的資源。 行程在執(zhí)行前必須要一次獲得一切需求的資源，但是這個作法比較沒有效率。 或是行程在獲得任何資源之前必須要釋放一切持有的資源。 可以呵斥資源運用率降低或是發(fā)生飢餓現(xiàn)象。 制止搶先制止搶先 制止搶先是指資源一旦配置給行程，就必須等到行程運用完，資源才會被釋放，要解除制止搶先可以運用以下作法： 當(dāng)行程持有某些資源並要求新的資源，假設(shè)所

21、要求的資源正被運用而必須等待，該行程必須釋放一切持有的資源。 當(dāng)行程 A 要求某些資源，假設(shè)所要求的資源可以運用，就立刻配置；但是假設(shè)所要求的資源已經(jīng)配置給其他的行程 B，檢查 B 能否正在等待其他的資源，假設(shè)是的話便將 A 所要求的資源由 B 回收並配置給 A。 循環(huán)等待循環(huán)等待 要使循環(huán)等待的條件不會發(fā)生，我們可以將系統(tǒng)中的一切資源類型都事先編號。 規(guī)定一切行程必須按照編號順序如由小而大獲得資源。 行程必須要先釋放所持有編號較大的資源，才干要求編號較小的資源。 會有資源運用率降低的問題。 第六章第六章 同步與死結(jié)同步與死結(jié)行程同步 臨界區(qū)號誌同步的經(jīng)典問題臨界區(qū)域與監(jiān)督程式 死結(jié)簡介 死結(jié)

22、預(yù)防 死結(jié)防止 平安狀態(tài) 資源配置圖演算法 銀行家演算法 摘要 死結(jié)防止死結(jié)防止 預(yù)防死結(jié)的方法大多會降低資源的運用率，而導(dǎo)致系統(tǒng)的效能降低。 死結(jié)防止雖然不完全排除死結(jié)發(fā)生的條件，但能有效地偵測系統(tǒng)可以發(fā)生死結(jié)的狀態(tài)，進而防止死結(jié)的發(fā)生。 需求系統(tǒng)提供行程額外的資訊。 當(dāng)有行程要求資源，系統(tǒng)會利用這些資訊判斷能否要將資源配置給行程或者是讓行程等待以防止死結(jié)的發(fā)生。 平安狀態(tài)平安狀態(tài) 平安狀態(tài)是指存在某種順序，可以讓系統(tǒng)按照該順序?qū)①Y源配置給所需求的行程，而不會發(fā)生死結(jié)。 系統(tǒng)正處於平安狀態(tài)，存在一組平安序列。 假設(shè)系統(tǒng)不存在一組平安序列，則表示系統(tǒng)正處於不平安狀態(tài)中，即系統(tǒng)可以會發(fā)生死結(jié)。

23、不平安狀態(tài)不一定就會發(fā)生死結(jié)，但是處於平安狀態(tài)絕對不會發(fā)生死結(jié)，這是因為系統(tǒng)運用資源的真正時間是無法確定的。 資源配置圖演算法資源配置圖演算法 資源配置圖演算法在系統(tǒng)配置某項資源給行程之前 先將配置圖中的箭號反向。然後運用偵測迴圈的演算法檢查新的配置圖中能否會出現(xiàn)迴圈。假設(shè)不會，則代表配置該資源後系統(tǒng)仍處於平安狀態(tài)，所以不會發(fā)生死結(jié)。反之，則代表配置該資源後，系統(tǒng)會進入不平安狀態(tài)而可以發(fā)生死結(jié)，因此系統(tǒng)不應(yīng)該配置該項資源給該行程。 不適用於有多項同種資源的系統(tǒng)之中。( (不不) )平安狀態(tài)的資源配置平安狀態(tài)的資源配置 R1R2P1P2R1R2P1P2R1R2P1P2R1R2P1P2銀行家演算法

24、銀行家演算法 每一個新進入到系統(tǒng)的行程必須要先註冊所需求的各種資源的最大數(shù)量。 當(dāng)行程要求某些資源時，系統(tǒng)便判斷這樣的配置能否會導(dǎo)致系統(tǒng)進入不平安狀態(tài)。 運用平安演算法來測試系統(tǒng)能否處在平安狀態(tài)。運用資源要求演算法來決定能否允許資源的要求。平安演算法平安演算法Safety Algorithmn宣告兩個長度分別為 m 與 n 的陣列 Work 與 Finish，並將 Work 初始化為 Available，F(xiàn)inish 陣列中一切元素初始為 FALSE。n尋找 i 使得 Finishi = FALSE 而且 NEEDi WORKi，假設(shè)找不到這樣的 i，執(zhí)行步驟 4。nWorki = Worki

25、 + Allocationi;n Finishi = TRUE;n 執(zhí)行步驟 2。n假設(shè) Finish 陣列中一切元素都為 TRUE，則系統(tǒng)目前處於平安狀態(tài)中。nn資源要求演算法資源要求演算法Resource Request Algorithmn宣告 n m 的 Request 陣列存放行程所要求各項資源的數(shù)量，如 Requesti, j = 3 表示行程 Pi 要求 3 項資源 Rj。n假設(shè) Requesti Needi，執(zhí)行步驟 3；否則因為行程要求過多的資源而發(fā)生錯誤。n假設(shè) Requesti Availablei，則執(zhí)行步驟 4；否則因為目前系統(tǒng)中尚未配置的資源缺乏，行程 Pi 必須等待。n作以下