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 i=0, j=1 flag[0]=True; turn=1; while(flag[1] && turn==1); P0 P1 P1 i=1, j=0 flag[1]=True; turn=0; while(flag[0] && turn==0); 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 用途(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 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. Indefinite blocking may occur if we remove processes from the list associated with a semaphore in LIFO (Last-in, First out) order. 9

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。 Priority Inversion - Scheduling problem when lower-priority process holds a lock needed by higher-priority process

Priority inversion is a situation where in lower priority tasks will run blocking higher priority tasks waiting for resource (mutex).  priority: A(High) B(Medium) C(Low) C was ready to run. So C starts running. locks mutex A is ready to run. Bcz of A is higher priority than C, A  gets the CPU (otherwords C relinguishes CPU).  While executing "A" task, it's need of resource(mutex) but it locked by lower priority task "C". so task "A" going to  be waiting state(priority inversion) B is ready to run. Bcz B is Higher priority than C, B get the CPU frm C.  For task "B", its no need of any resource(mutex). so it wont be waiting for any task to get resource. it will be finished first. Then, Task "C" gets CPU from task "B" and finished its task, and reliese the resource(mutex). Task C (waiting task for resource)then gets mutex finish execution.. Here:  B(M) task finished exe first C(L) task finished exe second A(H) task finished exe last even its have higher priority  than both B and C

6.6 典型的同步問題(Classic Problem of Synchronization) 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. Empty 5 Full 0 Mutex 1 Buffer[0] Buffer[1] Buffer[2] Buffer[3] Buffer[4]

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

6.6.3 哲學家進餐的問題(Dining-Philosophers Problem) Shared data Bowl of rice (data set) Semaphore chopstick [5] initialized to 1 至多允許四位哲學家上座 只有左右二支筷子可取用時，才允許哲學家拾取 座次為奇數號取其左邊筷子、為偶數號取其右邊筷子

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

condition x, y; x.wait(); : x.signal(); 可以確保同一時間只有一個Process 在monitor內執行。

6.7.2 使用監督程式哲學家進餐的解(Dining-Philosophers Solution Using Monitors) 只有左右二支筷子可取用時，才允許哲學家拾取 不會發生deadlock但可能有Starvation

6.7.3 使用號誌製作監督程式(Implementing a Monitor Using Semaphores) 對每一個監督程式提一個號誌mutex(初始值為 1)。每一個行程在進 入監督程式之前，都必須先執行wait (mutex) 的動作，並在離開監 督程式之後，執行signal (mutex) 的動作。 semaphore next: 控制通知等候process next_count紀錄等候next號誌地˙process數 x_sem=1; x.count=0; mutex=1; next=0; F: external procedure x.wait() x.signal()

6.7.4 監督程式內的恢復行程(Resuming Processes within a Monitor) R.acquire(t) … access the resource; R.release(); 把單一資源分配給相互競爭的process 每一process須告知使用資源之最大使用使間 Monitor將資源分配給使用時間最短之process 一個行程(Process)可能在沒有先取得某項資源的存取允許權之前就先使用該資源。 一個行程在獲得某項資源的存取權之後，就佔住不放。 一個行程可能會試圖存取一項從未取得過的資源。 一個行程可能會對相同的資源提出兩次要求(沒有先釋放出該資源)。

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

6.8.1 系統模型(System Model) A collection of operations that performs a single logical function is called a transaction(交易). 成功完成一交易就執行committed，確認之前交易活動資料。失敗則中止 (aborted)，恢復之前交易資料狀態(稱為為rolled back撤回)。 為了確保不可分割的性質，首先需要識別用來儲存被交易存取各項資料 之裝量的特性。不同型態的儲存媒體是由它們的速度(Speed)、容量 (Capacity)、和失效彈性(Resilience to failure)來區分。 揮發性儲存體 (volatile storage)：儲存在揮發性儲存體的資訊在系統當掉時通常不存在。這種儲存體的例子有主記憶體和快取記憶體。對揮發性儲存體的存取非常快，這是因為記憶體存取本身的速度，和因為可以直接在揮發性儲存體 存取任何資料項。 非揮發性儲存體 (nonvolatile storage)：儲存在非揮發性儲存體的資訊在系統當掉之後通常還存在。這種儲存體的例子有磁碟和磁帶。目前非 揮發性儲存體的速度比揮發性儲存體的速度慢好幾個級次。因為磁碟和磁帶裝置是電子機械式，並且需要實體移動以存取資料。 穩定儲存體 (stable storage)：在穩定儲存體的資訊絕不會遺失。為了製作近似這種的儲存體，我們需要複製資訊到數個非揮發性的儲存體快取 (通常是磁碟)，每一個有各自的失效模式，並且以控制的方式更新資訊 。

6.8.2 以記載簿為基礎的復原(Log-based Recovery) 預先記錄所有對各項資料所做修改之交易資訊，稱為預寫式記載簿 (write-ahead logging)。 為每一筆記載簿登錄下列各欄寫入交易資訊： 1. 交易名稱 (transaction)：執行 write 操作交易的唯一名稱。 2. 資料項名稱 (data item name)：寫入資料項的唯一名稱。 3. 舊值 (old value)：寫入動作前的資料項數值。 4. 新值 (new value)：寫入後的資料項數值。 undo(Ti) redo(Ti) 缺點：需做二次write

6.8.3 檢查點(Checkpoints) 一旦系統failure，以記載簿為基礎的復原方式，必須搜尋整個紀錄簿，搜尋過程耗時，影響效能。 1. 將所有記錄簿中目前在揮發性儲存體(通常是主記憶體)的記錄 輸出到穩定儲存體。 2. 將所有在揮發性儲存體的已修改資料輸出到穩定儲存體。 3. 輸出一筆記錄簿記錄(checkpoint)到穩定儲存體。

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

6.8.4.1 可串列化(Serializability) Conflicting operation Non-Conflicting operation 將non-serial schedule轉換成 Serial schedule 交換 T0的read(B)操作和T1的write(A)。

6.8.4.2 上鎖協定(Locking Protocol) 每一資料項給予一鎖，每一筆交易需遵循上鎖協定，以管理如何取得和釋放鎖。 資料有下列二種模式被上鎖： Two-phase locking protocol可確保conflict serializable， 但還是會發生deadlock。(習題)

6.8.4.3 時間戳記為基礎的協定(Timestamp-based Protocols) 使用系統時鐘的數值做為時間戳記:換言之，一筆交易的時間戳記等於此交易進入系統時的時鐘數值。這種方法對於發生在分隔系統間的交易，或沒有共用同一時鐘的處理器之交易無效。 使用邏輯計數器做為時間戳記:換言之，交易的時間戳記等於此交易 進入系統時的計數器數值。當設定一個新的時間戳記之後，計數器就 加 1。 TS(Ti) < TS(Tj)：表示交易Ti發生在交易Tj前的串列排班。 每一資料項 Q 配上二個Timestamp值：