《同步与死结》PPT课件.ppt

第六章第六章 同步與死結同步與死結行程同步 臨界區號誌 同步的經典問題 有限緩衝區問題 讀取者與寫入者問題 哲學家晚餐問題 臨界區域與監督程式 死結簡介 死結預防 死結避免 摘要 1同步的經典問題同步的經典問題牽涉到了大型並行控制的領域經常拿來測試新的同步機制的正確性 這些問題的解法當中都使用了號誌作為同步的工具 2有限緩衝區問題有限緩衝區問題 (The Bounded Buffer Problem) 用號誌來實作可簡單解決許多問題 假設緩衝區中有 n 個欄位，每個欄位可以存放一個項目使用 mutex 號誌確保存取緩衝區時的互斥條件成立，並初始化為 1empty 和 full 兩個號誌則分別用來計算緩衝區中空的與使用過的欄位數目empty 號誌初始化為 nfull 號誌初始化為 0 3有限緩衝區問題有限緩衝區問題 ( (續續) )生產者和消耗者的程式碼如下： dodo 產生一個新的項目放在 nextp waitwait(empty); waitwait(mutex); 將 nextp 加入到緩衝區中 signalsignal(mutex); signalsignal(full); whilewhile(1); dodo waitwait(full); waitwait(mutex); 將一個項目由緩衝區中 移到 nextc signalsignal(mutex); signalsignal(empty); 消耗放在 nextc 中的項目 whilewhile(1); 生 產 者消 耗 者4讀取者與寫入者問題讀取者與寫入者問題 (The Readers and Writers Problem) 一個系統中經常會有數個行程共同分享同一份資料物件只讀取這份分享資料的行程稱為讀取者。

只更新分享資料的行程稱為寫入者如果一個讀取者和一個寫入者同時存取所共享的資料，可能會發生錯誤 這種同步的問題稱為讀取者與寫入者問題以整數 readcount 記錄正在讀取資料的讀取者數目，初始值為 0利用初始化為 1 的 mutex 和 wrt 兩個號誌形成兩種臨界區 5讀取者與寫入者問題讀取者與寫入者問題 ( (續續) )讀取者和寫入者問題的解法如下： waitwait(mutex);readcount+;ifif (readcount = 1) waitwait(wrt);signalsignal(mutex); 進行讀取 waitwait(mutex);readcount-;ifif (readcount = 0) signalsignal(wrt);signalsignal(mutex); waitwait(wrt); 進行寫入 signalsignal(wrt); 讀 取 者 寫 入 者6哲學家晚餐問題哲學家晚餐問題 (1) (1)哲學家們圍坐在一張圓桌一起共進晚餐桌上筷子數目與哲學家相等，每兩個哲學家之間共用一支筷子哲學家們會坐在餐桌上思考哲學問題當哲學家們想吃東西時會拿起左右各一支筷子進餐，拿齊兩支筷子的哲學家們可同時進餐，但不能搶奪別人手上的筷子。

當食物吃完後，哲學家會將兩支筷子都放下，並繼續思考哲學問題，其他哲學家可繼續用放下的筷子 7哲學家晚餐問題示意圖哲學家晚餐問題示意圖 8哲學家晚餐問題哲學家晚餐問題 (2) (2)第 i 位哲學家的程式可寫成： dodo waitwait(chopsticki); waitwait(chopstick(i + 1) % 5; 進餐 signalsignal(chopsticki); signalsignal(chopstick(i + 1) % 5; 思考 whilewhile(1); 9哲學家晚餐問題哲學家晚餐問題 (2) (2)上述作法可能會導致死結的發生假如每位哲學家都拿起了一支筷子而等待另一支筷子，則不會有任何一位哲學家可以拿到兩支筷子，所有的哲學家將會進入死結狀態 下列作法可以避免哲學家晚餐問題發生死結： 在圓桌上放置 n+1 支筷子或限制最多只有 n-1 位哲學家可以同時進餐規定哲學家們必須要同時拿起左右兩支筷子規定奇數座位的哲學家要先拿起左方的筷子再拿起右方的筷子；而偶數座位的哲學家則先拿起右方的筷子再拿起左方的筷子10第六章第六章 同步與死結同步與死結行程同步 臨界區號誌 同步的經典問題 臨界區域與監督程式 臨界區域 監督程式死結簡介 死結預防死結避免摘要 11臨界區域與監督程式臨界區域與監督程式 號誌是個非常方便而且有效率的同步工具。

然而不正確地使用號誌，很容易產生行程之間同步上的錯誤這類錯誤並不一定每次程式執行時都會發生，所以很難除錯 臨界區域(Critical Region)與監督程式(Monitor)是另外兩種較高階的常用同步工具使用起來較為方便，而且不容易出錯 每個行程會有一些私有的局部變數，以及一些行程間的共享變數行程不能夠直接存取其他行程的局部變數 12臨界區域臨界區域 臨界區域的使用非常方便 以下宣告一個具有共享變數 v 的臨界區域，在 B 條件式成立下，如果沒有其他行程在此臨界區域中執行，就會執行 S 敘述：利用臨界區域來實作，程式設計師不用煩惱同步的問題，只要正確地把問題描述在臨界區域內 有限緩衝區問題可以用臨界區域來簡單地解決同步的問題regionregion v whenwhen B dodo S; 13臨界區解決有限緩衝區的問題臨界區解決有限緩衝區的問題 共享的資料:struct buffer item pooln;int count, in, out;生產者形成將 nextp 放共享的緩衝區region buffer when( count 0) nextc = poolout;out = (out+1) % n;count-;15臨界區域臨界區域 ( (續續) )臨界區域 region v when B do S 可利用 mutex、first_delay 及 second_delay 三個號誌實作。

mutex 號誌是用來確保臨界區的互斥條件成立 如果行程因為 B 為 FALSE 而無法進入臨界區，該行程將會在號誌 first_delay 等待 在號誌 first_delay 等待的行程重新檢查 B 值之前，會離開號誌 first_delay，而在號誌 second_delay 等待 分成first_delay 與 second_delay兩段式等待的原因，是為了要避免行程持續忙碌地檢查 B 值 當一個行程離開了臨界區之後，可能因為執行了敘述 S 而改變了 B 的值，所以需要重新檢查16監督程式監督程式 監督程式是另外一種高階的同步工具 對較複雜的同步問題提供了更一般性的實作工具 由一些變數宣告及函式所組成，變數的值定義了監督程式的狀態 保證只有一個行程在監督程式中執行所定義的函式 在監督程式中，程式設計師不需要撰寫有關同步的程式碼，但是可以利用條件變數來定義自己的同步機制 哲學家晚餐問題可以利用監督程式來實作17Solution to Dining Solution 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;18pickUp() ProcedurepickUp() Procedurevoid 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);19test() Proceduretest() Procedurevoid test(int i) if ( (state(i + 4) % 5 != eating) & (statei = hungry) & (state(i + 1) % 5 != eating) statei = eating;selfi.signal();20Solution 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 simultaneously, and no deadlocks will occur.However, it is possible for a philosopher to starve to death. 21第六章第六章 同步與死結同步與死結行程同步 臨界區號誌 同步的經典問題 臨界區域與監督程式 死結簡介 死結特性 死結偵測 死結解除 死結預防 死結避免 摘要 22死結簡介死結簡介 許多行程會共同競爭系統中有限的資源。

當行程所要求的資源正被其他的行程所使用時，該行程就必須要等待 等待的行程可能會因為所要求的資源也被其他正在等待的行程所持有，而無限期地等待，這種情形稱為死結 23死結特性死結特性 (1) (1)系統中行程共同競爭的有限資源可以分為幾種不同的類型，而每種類型又會有不同數目的資源 一個行程可以對一個資源進行要求、使用、釋放等 3 種動作 行程不能要求比系統擁有數目更多的資源 當行程要求了某種資源時，作業系統會先檢查系統的資源配置表，如果該種資源都正被其他行程所使用，作業系統會將目前要求的這個行程加入所等待資源的等待串列中 24死結特性死結特性 (2) (2)死結的定義如下，系統中的每一個行程都在等待著某些資源，而這些資源卻已經配置給其他正在等待的行程，因而所有的行程都進入無限期地等待而無法完成工作 死結只有在下列 4 種條件都同時成立下才會發生： 互斥 佔用與等待 禁止搶先 循環等待 25死結特性死結特性 (3) (3)我們可以使用系統資源配置圖來描述系統中行程與資源間的狀態 圓代表系統中的一個行程，圓中寫著行程的名稱 方塊代表系統中的一種資源，方塊中黑點的數量表示該種資源的數目 箭號所代表的意義有兩種。

由資源指向行程的箭號表示該資源目前被該行程所持有 由行程指向資源的箭號則代表該行程目前正在等待該項資源 26資源配置圖資源配置圖 P1P2P3 R2 R127死結偵測死結偵測 如果系統中所有類型的資源都只有一項的話，我們可以利用資源配置圖來偵測死結 利用偵測迴圈的演算法來檢查資源配置圖中是否有迴圈存在，就能知道目前系統中是否有死結發生 使用這種方法的系統必須要持續地更新資源配置圖，並且要定期地執行偵測迴圈的演算法以偵測死結 如果系統中各類型資源的數目不只一項的話，可以使用死結偵測演算法來偵測死結 28死結解除死結解除 當偵測到死結發生，有兩種方法可以解除死結 終止一些行程，使循環等待的條件不成立 由發生死結的行程中回收一些資源給其他行程，使禁止搶先的條件不成立終止行程的作法中，可以選擇終止所有行程或是一次只終止一個行程，直到死結的狀態解除 終止所有行程的作法雖然比較簡單，但是行程的工作必須重新或是。