像这种数个行程同时存取和处理相同资料的情况-Min-ShiangHwang.ppt

* * Modified by Min-Shiang Hwang (亞大黃明祥) ?2013 Modified by Min-Shiang Hwang (亞大黃明祥) ?2013 Chapter 6 同步  (Synchronization) * 6.1 背景 6.2 臨界區間問題 6.3 Peterson’s解決方案 6.4 同步之硬體 6.5 號誌 6.6 典型的同步問題 6.7 監督程式 6.8 不可分割的交易 6.1 背景(Background) 這個不正確的狀態是因為允許兩個行程並行處理這個 counter變數。像這種數個行程同時存取和處理相同資料的情況，而且執行的結果取決於存取時的特殊順序，就叫兢爭情況 (race condition)。 * T0 = T1 = T4 = T2 = T3 = T5 = 6.2 臨界區間問題(Critical-Section Problem) 互斥(Mutual Exclusion):如果行程Pi正在臨界區間內執行，則其它的行程不能在其臨界區間內執行。 進行(Progress):如果沒有行程在臨界區間內執行，同時某一行程想要進入其臨界區間，那麼只有那些不在剩餘區間執行的行程才能加入決定誰將在下一次進入臨界區間，並且這個選擇不得無限期地延遲下去。 有限制的等待(Bound Waiting):一個行程已要求進入其臨界區間，在此要求尚未被答應前，允許其它的行程進入其臨界區間的次數要有限制。 * 6.3 Peterson’s解決方案(Perterson’s Solution) 要證明 互斥性存在 進行(Progress)的要求能被滿足 有限制的等待要求亦能符合。 P0 P1 i=0, 1 * flag[0]=True; turn=1; while(flag[1] turn==1); flag[1]=True; turn=0; while(flag[0] turn==0); P0 P1 i=0, j=1 i=1, j=0 6.4 同步之硬體 硬體上的特殊性質可以使寫程式的工作變得比較容易，並且增進系統的效率。 電腦系統都提供了一些特殊的硬體指令，允許我們可以在同一記憶體週期內去測試修改一個字組的內容，或交換兩個字組的內容。 lock=FALSE 回傳*target, 並設定*target為True *a *b內容對換 設定lock為True lock=FALSE * lock=FALSE waiting[i]=FALSE; lock=FALSE TestAndSet及Swap由硬體製作(一時間週期完成；不可分步驟方式執行) * 6.5 號誌 (Semaphore) 6.5.1 用途(Usage) 計數號誌 (counting semaphore)的值可以不受限制。二元號誌 (binary semaphore)的數值可以是0或 1。在某些系統，二元號誌稱為互斥鎖 (mutex locks)，當它們是鎖而且互斥。 mutex=1 wait(mutex); * 6.5.2 製作(Implementation) 號誌定義都有一個主要的缺點，那就是它們都需要忙碌等待 (busy waiting)。意即當一個行程置於其臨界區間時，其它欲進入它們的臨界區間之行程必定在入口的程式碼形成循環迴路。 Implementation of wait: wait(semaphore *S) { S-value--; if (S-value 0) { add this process to S-list; block(); } } Implementation of signal: signal(semaphore *S) { S-value++; if (S-value = 0) { remove a process P from S-list; wakeup(P); } } * typedef struct{ int value; struct process *list; } semaphore 6.5.3 死結和飢餓(Deadlock and Starvation) Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waitin