Operating System Concepts 作業系統原理 Chapter 6 同步 (Synchronization)

CHAPTER 6 同步 6.1 背景 6.2 臨界區間問題 6.3 Peterson’s解決方案 6.4 同步之硬體 6.5 號誌 6.1 背景 6.2 臨界區間問題 6.3 Peterson’s解決方案 6.4 同步之硬體 6.5 號誌 6.6 典型的同步問題 6.7 監督程式 6.8 不可分割的交易

6.1 背景 這個不正確的狀態是因為允許兩個行程並行處理這個 counter變數。像這種數個行程同時存取和處理相同資料的情況，而且執行的結果取決於存取時的特殊順序，就叫兢爭情況 (race condition)。

6.2 臨界區間問題(Critical-Section Problem) 互斥(Mutual Exclusion):如果行程Pi正在臨界區間內執行，則其它的行程不能在其臨界區間內執行。 進行(Progress):如果沒有行程在臨界區間內執行，同時某一行程想要進入其臨界區間，那麼只有那些不在剩餘區間執行的行程才能加入決定誰將在下一次進入臨界區間，並且這個選擇不得無限期地延遲下去。 有限制的等待(Bound Waiting):一個行程已要求進入其臨界區間，在此要求尚未被答應前，允許其它的行程進入其臨界區間的次數要有限制。

6.3 Peterson’s解決方案 要證明 互斥性存在， 進行的要求能被滿足， 有限制的等待要求亦能符合。 P0 P1 i=0, 1

6.4 同步之硬體 硬體上的特殊性質可以使寫程式的工作變得比較容易，並且增進系統的效率。 6.4 同步之硬體 lock=FALSE 硬體上的特殊性質可以使寫程式的工作變得比較容易，並且增進系統的效率。 電腦系統都提供了一些特殊的硬體指令，允許我們可以在同一記憶體週期內去測試修改一個字組的內容，或交換兩個字組的內容。 回傳*target, 並設定*target為True lock=FALSE 設定lock為True *a & *b內容對換

waiting[i]=FALSE; lock=FALSE lock=FALSE TestAndSet及Swap由硬體製作(不可分方式執行)

6.5 號誌 (Semaphore) 6.5.1 用途 計數號誌 (counting semaphore)的值可以不受限制。二元號誌 (binary semaphore)的數值可以是0或 1。在某些系統，二元號誌稱為互斥鎖 (mutex locks)，當它們是鎖而且互斥。 mutex=1 wait(mutex);

6.5.2 製作 號誌定義都有一個主要的缺點，那就是它們都需要忙碌等待 (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);

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 waiting processes Let S and Q be two semaphores initialized to 1 P0 P1 wait (S); wait (Q); wait (Q); wait (S); . . signal (S); signal (Q); signal (Q); signal (S); Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended Priority Inversion - Scheduling problem when lower-priority process holds a lock needed by higher-priority process 10

6.5.4 優先權倒置(Priority Inversion) 假設有三個行程L、M、H，其優先權順序是L < M < H。假設行程H要求正被行程L存取的資源R。通常行程H會等待L完成使用資源R。然而，現在因為行程M變成可執行的，因此可搶先行程L。間接地一個有較低優先權的行程(行程M)已經影響到行程H。這個問題被稱為優先權倒置。 優先權繼承協定必須允許行程L暫時地繼承行程H的優先權，因此才能阻止行程M搶先它的執行。當行程L已經完成使用資源R時，它將放棄它從H所繼承的優先權並假設其最初的優先權。因為資源R是可用的，接下來讓行程H使用，而不是M。

6.6 典型的同步問題 6.6.1 有限緩衝區問題(Bounded-Buffer Problem) 6.6 典型的同步問題 6.6.1 有限緩衝區問題(Bounded-Buffer Problem) N buffers, each can hold one item Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0 Semaphore empty initialized to the value N.

6.6.2 讀取者-寫入者問題(Readers and Writers Problem) Allow multiple readers to read at the same time. Only one single writer can access the shared data at the same time. 除非有一Writer已獲得允許使用共用資料，否則Reader不需保持等候狀態 (Reader不用等候其他Reader結束，但Writer需要等候)。Writer可能有Starvation 若有一Writer已在等候存取共用資料，則不能有新Reader去讀取資料。Reader可能 有Starvation Semaphore mutex initialized to 1 Semaphore wrt initialized to 1 Integer readcount initialized to 0

Shared data 6.6.3 哲學家進餐的問題(Dining-Philosophers Problem) Bowl of rice (data set) Semaphore chopstick [5] initialized to 1

6.7 監督程式 (monitor) 6.7.1 用途 一種抽象的資料型態使用公用的方法封裝私人的資料以對或函數之實體。 此資料進行操作。監督程式之型式為該程式是由一組程式設計者定義之運算元所組成。 此監督程式之形式之表示是由變數宣告所組成，該變數之值定義了形式範例的狀態，以及形式運作之程序。

6.7.2 使用監督程式哲學家進餐的解

6.7.3 使用號誌製作監督程式 對每一個監督程式提一個號誌mutex(初始值為 1)。每一個行程在進入監督程式之前，都必須先執行wait (mutex) 的動作，並在離開監督程式之後，執行signal (mutex) 的動作。

6.7.4 監督程式內的恢復行程 一個行程可能在沒有先取得某項資源的存取允許權之前就先使用該資源。 6.7.4 監督程式內的恢復行程 一個行程可能在沒有先取得某項資源的存取允許權之前就先使用該資源。 一個行程在獲得某項資源的存取權之後，就佔住不放。 一個行程可能會試圖桿放一項從未取得過的資源。 一個行程可能會對相同的資源提出兩次要求(沒有先釋放出該資源)。

6.8 不可分割的交易 臨界區間的互斥性保證了臨界區間的執行之不可分割。換言之，如果兩個臨界區間並行地執行，結果相當於它們以某種未知的順序循序地執行。雖然這項性質在許多應用領域很有用，依然有許多情況下我們希望工作是完整的執行完，或完全不執行。 資料的一致性 (連同資料的儲藏和取回)，時常與資料庫系統 (Database systems)有關。最近，與起應用資料庫系統的技術在作業系統的與趣。作業系統可以視為資料的處理者:因此，可以從資料庫研究的進階技術和模型得到一些幫助。

6.8.1 系統模型 為了決定系統該如何確保不可分割的性質，我們首先需要誠別用來儲存被交易存取各項資料之裝量的特性。不同型態的儲存媒體是由它們的速度、容量和失效彈性來區分。 揮發性儲存體 (volatile storage):儲存在揮發性儲存體的資訊在系統當掉時通 常不存在。這種儲存體的例子有主記憶體和快取記憶體。對揮發性儲存體的存取非常快，這是因為記憶體存取本身的速度，和因為可以直接在揮發性儲存體 存取任何資料項。 非揮發性儲存體 (nonvolatile storage):儲存在非揮發性儲存體的資訊在系統當掉之後通常還存在。這種儲存體的例子有磁碟和磁帶。目前非 揮發性儲存體的速度比揮發性儲存體的速度慢好幾個級次。因為磁碟和磁帶裝 置是電子機械式，並且需要實體移動以存取資料。 穩定儲存體 (stable storage):在穩定儲存體的資訊絕不會遺失 。為了製作近似這種的儲存體，我們需要複製資訊到數個非揮發性的儲 存體快取 (通常是磁碟)，每一個有各自的失效模式，並且以控制的方式更新 資訊 。

6.8.2 以記載簿為基礎的復原 每一筆登錄記載著一筆寫入交易的操作，並有以下各欄: 6.8.2 以記載簿為基礎的復原 每一筆登錄記載著一筆寫入交易的操作，並有以下各欄: 交易名稱 (transaction):執行 write操作之交易的唯一名稱。 資料項名稱 (data item name):寫入資料項的唯一名稱。 舊值 (old value):寫入動作前的資料項數值。 新值 (new value):寫入後的資料項數值。

6.8.3 檢查點(checkpoint) 1. 將所有記錄簿中目前在揮發性儲存體(通常是主記憶體)的記錄輸出到穩定儲存體。 2. 將所有在揮發性儲存體的已修改資料輸出到穩定儲存體。 3. 輸出一筆記錄簿記錄(checkpoint)到穩定儲存體。

6.8.4 並行的不可分割交易 每一筆交易都是不可分割，交易的並行執行就相當於以某種任意順序依序地執行這些交易。這項性質 [叫做可串列化，serialization)可以藉著在一個臨界區間只執行一項交易來維持。 所有的交易都共享一個共用號誌 mutex，此號誌被設定成 1的初值。當一項交易開始執行時，它的第一個動作時執行wait (mutex)。在此交易交付或中止時，它就執行 signal (mutex)。

6.8.4.1 可串列化

6.8.4.2 上鎖協定

6.8.4.3 時間戳記為基礎的協定 使用系統時鐘的數值做為時間戳記:換言之，一筆交易的時間戳記等於此交易 進入系統時的時鐘數值。這種方法對於發生在分隔系統間的交易，或沒有共用 同一時鐘的處理器之交易無效。 使用邏輯計數器做為時間戳記:換言之，交易的時間戳記等於此交易進入系統時的計數器數值。當設定一個新的時間戳記之後，計數器就加 1。