第5章 同步(Synchronization)

Presentation on theme: "第5章 同步(Synchronization)"— Presentation transcript:

1 第5章 同步(Synchronization)

2 基本觀念 賽跑的時候會要求跑者起跑的時間一致，有人偷跑就要重新來過，同時起跑就是一種同步(synchronization)的概念
使用PDA的人有時候需要把PDA跟電腦連接在一起，從電腦下載資料到PDA上、或是從PDA將資料上傳到電腦上，讓PDA與電腦上的資料能夠同步 電腦作業系統探討的同步概念跟這些觀念很像

3 處理元與執行緒(thread)的管理 多工(multiprogramming) 多處理器(multiprocessing)
分散式的處理(distributed processing)

4 應用程式運用並行(concurrency) 的困難
並沒有普及的平行程式語言(parallel programming language)可用，Ada支援同時性卻不普及，常用的C/C++不支援同時性。 系統軟體的技術並未在同時性程式(concurrent program)的支援上有一致的發展。 由於同時性的解決方法分歧，作業系統只提供極少的同時性支援功能。

5 並行演算法(concurrent algorithm)發展上不利的因素
要設計一組可同時並合作執行的程式是很複雜的問題，原因是實作的方法太多了，另一個原因則是處理元間的交互作用(interaction)與相依性(dependencies)不易處理。 在網路與平行處理的架構下，交互作用的處理更複雜。 在設計具有同時執行能力的軟體時，常會衍生出其他的同步問題。

6 同步(synchronization) 同步的觀念不太容易理解，而且同步不是作業系統領域獨有的問題，其他的領域也有類似的問題
同步是指多個處理元同時在執行，輪流使用CPU 為什麼電腦系統會同時有多個處理元在執行呢 ? 多工的作業系統本來就容許多個處理元同時執行 在結構化的應用系統中，則是有多個處理元個別執行，即使作業系統本身也有結構化的現象，由數個處理元合作完成複雜的系統功能，這都會造成多個處理元同時執行

7 作業系統中處理元同步的問題 作業系統在同步問題上的考量 處理元之間的互動(process interaction)

8 臨界區域(critical section)
當兩個處理元共用一個變數(variable)，我們說各處理元使用共用變數時進入了所謂的臨界區域 在沒有做任何控制的情況下，當這兩個處理元同時執行時，所得到的結果不是確定的(non-determinate)，也就是說，同樣的程式每次執行時得到的結果可能都不一樣 我們希望避免這樣的狀況，基本的解決方式是要求任一處理元進入臨界區域時，另外一個處理元就不能同時進入其臨界區域

9 支援互斥的方法應該滿足的要求 同樣的資源或共享的物件由多個處理元在互斥的情況下使用，則一次只有一個處理元能進入其臨界區域。
處理元在臨界區域以外暫停時，不能因而干擾其他處理元。 要求進入臨界區域的處理元不應該被無限期地拖延。 沒有處理元在臨界區域的時候，任何要求進入臨界區域的處理元都應該被允許進入。 不需要對處理器的數目或是處理元的執行時間有任何假設。 處理元在臨界區域中只停留有限的時間。

10 同時更改餘額的問題

11 交錯執行的狀況

12 錯誤發生的原因

13 使用共同變數的解法

14 處理元執行的情形

15 典型的互斥機制

16 透過軟體方法來達到互斥(mutual exclusion)
軟體解決同步的方法可以運用於單處理器的環境，假如要使用於多單處理器的環境，必須有共享的主記憶體 這些方法都假設記憶體層次的存取(memory access level)有基本的互斥機制，也就是說，對同一個記憶體位置的讀(read)與寫(write)的動作會序列化，依序進行

17 第1種解決辦法 (參考資料: (Stallings 2001))

18 第2種解決辦法 (參考資料: (Stallings 2001))

19 第3種解決辦法 (參考資料: (Stallings 2001))

20 第4種解決辦法 (參考資料: (Stallings 2001))

21 同步問題解決方法的整理 典型的互斥機制 透過軟體方法來達到互斥(mutual exclusion) Dekker’s演算法
Peterson的演算法

22 處理元之間的協調

23 號誌(semaphore) 號誌是一種作業系統提供的抽象資料型式(abstract data type) ，執行的功能有點像enter與exit 的系統呼叫，簡單地說，semaphore包括兩個主要的操作 : V(s) : [ s = s+1 ] P(s) : [ while (s==0) {wait}; s = s - 1] semaphore本身只是一個正整數值，其值的改變得經由上述的兩種操作。方括弧內的操作必須是單元化的(atomic) ，V(s)是不能被中斷的，P(s)在執行wait時可以被中斷

24 semaphore解決同步的方法

25 常見的同步問題 基本的臨界區域問題 基本的同步問題 生產者-消費者問題(producer-consumer problem)
讀取與寫入的問題(readers-writers problem) 哲學家用餐問題(The Dining-Philosophers Problem) 理髮店的問題(Barbershop problem)

26 基本的臨界區域問題

27 基本的同步問題

28 生產者-消費者問題(producer-consumer problem)

29 讀取與寫入的問題(readers-writers problem)

30 哲學家用餐問題(The Dining-Philosophers Problem)

31 理髮店的問題(Barbershop problem)