同步問題 Synchronization

# 同步問題 Synchronization :::spoiler [TOC] ::: ## 一、同步問題簡介 :::success The Critical Section Problem：提供對共享變數之存取的互斥控制，確保資料的正確性。 ::: :::danger - `entry` section - `Critical` section - `exit` section - `remainder` section ::: ![](https://i.imgur.com/WBSeLjx.png) :::danger **建立 critical section** ::: ![](https://i.imgur.com/kp52krg.png) :::warning ### Solution to ==Critical-Section Problem== : ::: :::success - Mutual exclusion：任一時間點，只允許一個 process 進入他自已的 `critical section` 內活動。 ::: :::info - Progress：必須同時滿足下面2個要件： - 不想進入 critical section 的 process 不可以阻礙其它 process 進入 critical section，即不可參與進入 critical section 的決策過程。 - 必須在有限的時間從想進入 critical section 的 process 中，挑選其中一個 process 進入 critical section，隱含No Deadlock。 - ==tips: 有空位時讓「想進的人」「馬上」進入。== - Bound waiting：自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。即若有 n 個 processes 想進入，則任一 process 至多等待 n-1 次即可進入，隱含 No starvation。 ::: ## 二、Peterson's solution —software solution :::info - Two process solution. Assume that the `LOAD` and `STORE` instructions are automic; that is, cannot be interrupted. ::: :::warning - Share variables : - turn：整數，存放的値為 i 或 j，誰擁有此值誰就有資格進入。 - flag[i]：布林陣列，表示 i 想不想進去。 ::: ``` c= do{ flag[i] = TRUE; turn = j; //禮讓的概念 while ( flag[j] && turn == j); //想進去且輪到他進去 CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION } while (TRUE); ``` ### 1. Mutual exclusion :::success - 若 Pi 與 Pj 皆想進入自已的 C.S.，代表 flag[i] = flag[j] = true，而且會分別執行到 turn = i 及 turn = j 之設定，只是先後次序不同，turn 的值僅會是 i 或 j，絶不會兩者皆是。 ::: ### 2. Progressive :::success - 若 Pi 不想進入 C.S.，則表示flag[i] = false。此時若 Pj 想進入自已的 C.S.，必可通過 while(flag[i] and turn = i) do no-op 這個空迴圈而進入其 C.S.，不會被 Pi 阻礙。 - 若 Pi 與 Pj 皆想進入自已的 C.S.，則在有限的時間內，Pi 與 Pj 會分別執行到 turn = i 及 turn = j 之設定 (只是先後次序不同)，turn 値必為 i 或是 j。因此 Pi (或 Pj) 會在有限的時間內進入自已的 C.S. (No Deadlock)。 ::: ### 3. Bounded-waiting :::success - Pi 離開 C.S. 後又企圖立刻進入自已的 C.S.，此時 Pi 一定會執行 turn = j，使得 Pi 無法再搶先於 Pj 進入自已的 C.S.。所以 Pj 至多等待一次即可進入 C.S.。 ::: ### 4. Failed Algorithm 1 : Only Turn ``` c= repeat while(turn!=i)do no-op C.S. turn = j; R.S. until False ``` :::danger - **違反 Progress (違反條件1)**：  假設目前 turn 值為 i ，但 Pi 不想進入 critical section。若此時 Pj 想進critical section Pj 卻無法進入被 Pi 阻礙，因為只有 Pi 才有資格將 turn 值改為 j (想進入無法馬上進入)。 ::: ### 5. Failed Algorithm 2 : Only Flag ``` c= repeat flag[i] = True while( flag[j] ) do no-op; C.S. flag[i] = False R.S. until False ``` :::danger **Progress違反(違反條件2)**：如 Pi,Pj 依下列順序執行，則 Pi,Pj 皆無法進入 critical section 形成 Deadlock 。 ::: ```c= lag[i] = True; lag[j] = True; while( flag[j] ); while( flag[i] ); // 太有禮貌，大家都想進都進不了 ``` ## 三、Disable interrupt — hardware instructions support :::success 1. TestAndSet：檢查並設置是一種不可中斷的基本 (原子) 運算 (atomically)，它會寫值到某個記憶體位置並傳回其舊值。 2. Swap： a, b 兩值互換。 ::: :::info - hardware solution 缺點 (特指 TAS 和 SWAP) - 只有kernel mode 能用 - need time - 多處理機上會失效，單處理機上不好(busy waiting) - starvation ::: :::danger **[感覺] ++簡易解法違反++ bounded waiting：未規範`order`使得次序以亂數決定。** ::: ``` c= /* Test_and_Set C.S. example */ repeat while(Test_and_Set(Lock)) do no-op; //entry C.S. Lock = False; //exit R.S. until false /* SWAP C.S. example */ Repeat key = true; repeat SWAP(Lock, key); until key = False; C.S. Lock = False; R.S. Until false ``` :::danger **[用心去感覺] `Software` & `Hardware solution` 整理** ::: :::success **Uniprocessor** ::: :::info - Interrupt disabling - Only available in kernel space - Increase interrupt latency - Spin lock (test and set, swap) - Waste CPU cycles ::: :::success **Multiprocessor** ::: :::info - Interrupt disabling - Too costly to broadcast interrupt disabling - Does not work if two involved processes run on different processors - Spin lock - Waste CPU cycle, but seem to be the only choice ::: ## 四、Semaphore :::success - **Semaphore** - 是一個同步物件，用於保持在 0 至指定最大值之間的一個計數值。(Semaphore do not require busy waiting, using waiting queue) - 當執行緒完成一次對該 semaphore 物件等待 (wait(S) / P(S)) 時，該計數值 S-1； - 當執行緒完成一次對semaphore 物件釋放 (signal(S) / V(S)) 時，計數值 S+1。 - 當計數值為 0，則執行緒等待該 semaphore 物件直至該 semaphore 物件變成 signaled (>0)狀態。 ::: :::info - 用途設置： - Sequencing (event) : value = 0 - Mutex : value = 1 - Capacity control : value = n_capacity ::: :::danger **[感覺] Semaphore 發明者 Dijkstra 是荷蘭人，所以 P(), V() 意思就是英文的 wait(), signal()。** ::: :::warning 1. 例題 : Sequencing - **傑克和羅絲相約去看電影，兩人約在電影院門口見面，如果有人先到的話要等另一人到了才可以進入電影院。** ::: ``` c= R=0;J=0; jack(){ signal(J); //自己到了，一定要先 signal 再 wait 不然會有 deadlock。 wait(R); //等 // see the movie } ross() { signal(R); wait(J); // see the movie } ``` :::warning 2. 例題 : Mutex 和 Capacity control A `DMA` controller offers 4 `DMA` channels for simultaneous data transfers. ::: ``` c= S=4; T=1; c[4]={F,F,F,F}; proc() { wait(S); //容量控制(一個房間最多4人) wait(T); //保護c[4]避免複寫(一次只有一個人找位子坐) // pick one unused channel among c[0],c[1],c[2],c[3] // setup DMA transfer signal(T); // wait for DMA completion signal(S); } ``` ## 五、Classical Problem of Synchronization ### 1. Bounded-Buffer Problem :::success N 個 buffers，Producer 製造項目，Consumer 消耗項目。 ::: :::info - Shared data： - N Buffer initial mutex = 1 ：互斥鎖，避免同時複寫 - initial full = 0：producer signal，consumer wait - initial empty = N：producer wait，consumer signal ::: :::danger **[感覺1] consumer「製造空白」** ::: :::danger **[感覺2] 如果 mutex 在 full, empty semaphore scope 之外，則當全空或全滿時會形成 deadlock。** ::: ``` c= /* P1 : producer */ do{ wait(empty); // producer 吃掉 "empty" wait(mutex); // add a item to the buffer signal(mutex); signal(full); //producer 排出 "full" }while(1); /* P2 : comsumer */ do{ wait(full); // comsumer 吃掉 "full" wait(mutex); // remove an item from buffer signal(mutex); signal(empty); //comsumer 排出 "empty" }while(1); ``` ### 2. Readers-Writers Problem :::success Allow multiple readers to read at the same time. ++Only one single writer can access the shared data at the same time.++ ::: :::warning **Readers** – only read the data set; they do not perform any updates **Writers**– can both read and write. ::: :::info - Shared Data : - data set - int readcount = 0 - Semaphore mutex = 1 (in order to protect readcount) - Semaphore wrt = 1 ::: ``` c= /* writer */ do{ wait(wrt); // writing is performed signal(wrt); }while(true); /* reader */ do{ wait(mutex); readcount++; if(readercount == 1) wait(wrt); signal(mutex) // reading is performed wait(mutex); readcount--; if(readcount == 0) signal(wrt); signal(mutex); }while(true) ``` :::danger **[感覺] 這個排程對 reader 有利** ::: :::info - reader 一直來 writer 會 starvation. (眾 reader 相當於是一個很愛佔位的 writer) - No readers will wait until the writer locked the shared object. - Readers need not to sync with each other. ::: - ![](https://i.imgur.com/px7S7Ov.png) ### 3. Philosophers Problem :::info 每個哲學家有 3 種狀態： - thinking — 不想吃飯，思考中。 - hungry — 想吃飯。 - eating — 取得左右筷子，可吃飯。 ::: :::warning Shared variables： - data set - chopstick[0...4] of semaphor ::: ```c= repeat wait(chopstick[i]); wait(chopstick[i+1] mod 5); //eating signal(chopstick[i]); signal(chopstick[i+1] mod 5); until False; ``` :::info - Alternatives : - One person get the left stick first, the rest get the right stick first (avoid circular waiting) - Allow up to 2 people having sticks (more semaphore) - Two sticks are picked simultaneously (low concurrency) ::: ### 4. Sleeping Barber Problem :::info - 有兩種process ： - Barber — 沒有客人則等待，否則一個一個剪。 - Customer — 若有椅子可坐，則坐下等待，否則離開店內。 ::: :::info - Shared variables : - initial Semaphore custReady = 0：event，表示有無等待的 customer。 - initial Semaphore barberReady = 0：event，表示 barber 是否準備就緒。 - initial int accessWRSeats = N：店內有幾張椅子 ::: ```python= # The first two are mutexes (only 0 or 1 possible) Semaphore barberReady = 0 Semaphore accessWRSeats = 1 # if 1, the number of seats in the waiting room can be incremented or decremented Semaphore custReady = 0 # the number of customers currently in the waiting room, ready to be served int numberOfFreeWRSeats = N # total number of seats in the waiting room def Barber(): while true: # Run in an infinite loop. wait(custReady) # Try to acquire a customer - if none is available, go to sleep. wait(accessWRSeats) # Awake - try to get access to modify # of available seats, otherwise sleep. numberOfFreeWRSeats += 1 # One waiting room chair becomes free. signal(barberReady) # I am ready to cut. signal(accessWRSeats) # Don't need the lock on the chairs anymore. # (Cut hair here.) def Customer(): wait(accessWRSeats) # Try to get access to the waiting room chairs. if numberOfFreeWRSeats > 0: # If there are any free seats: numberOfFreeWRSeats -= 1 # sit down in a chair signal(custReady) # notify the barber, who's waiting until there is a customer signal(accessWRSeats) # don't need to lock the chairs anymore wait(barberReady) # wait until the barber is ready # (Have hair cut here.) else: # otherwise, there are no free seats; tough luck -- signal(accessWRSeats) # but don't forget to release the lock on the seats! # (Leave without a haircut.) # may lead to starvation of a customer ``` ## 六、Monitors :::success Monitors 是一個用來解決同步問題的高階資料結構(物件導向)。(Semaphore and monitor have the same power in solving synchronization problem.) ::: :::info Monitors 的組成 : 1. 共享變數宣告區 2. 一組程序 3. 初始區 ::: :::info **特色 :** - 宣告在 monitor 的變數只有 monitor 的 procedure 可以存取 (類似class中的private區)。 - monitor 中有 condition 型態的變數，提供 programmer 設計同步問題之用(for sync policy)。 - monitor 直接保障 monitor 中變數和程序的互斥性質(mutex, not sync policy)，不可有多個 process 呼叫 - -- monitor 的某個程序 (在 semaphore 中要多加許多 mutex 保護變數)。 ``` =python monitor name{ // share variable declarations pro1(){...} pro2(){...} init code(){...} } ``` ![](https://i.imgur.com/6oBUJRF.png) ::: ## Synchronization in Solaris :::success • ==Solaris controls== access to critical sections using five tools: **semaphores**, condition **variables**, adaptive **mutexes**, reader-writer **locks**, and **turnstiles**. The first two are as described above, and the other three are described here: ::: ### Adaptive Mutexes :::success • Adaptive mutexes are basically **binary semaphores** that are implemented differently depending upon the conditions: ::: *single processor* :::info **semaphore sleeps** **until the block is released**. ::: *multi-processor* :::info - **same processor as the thread that is blocked**, - **if not running at all**, **then the blocked thread sleeps like a single processor** ::: :::warning - blocking **thread is currently running**on a **different processor**: - **blocked thread does a spinlock**, **under the assumption** **block willsoon be released**. ::: :::info **only used for protecting short critical sections**, - **benefit** - **not doing context switching** - worth - a short bit of spinlocking. Otherwise **traditional semaphores and condition variables are used** ::: ### Reader-Writer Locks :::info • protecting longer sections - accessed frequently (but **changed infrequently**). ::: ### Turnstiles :::success - turnstile is a queue of threads waiting on a lock. - Each synchronized **threads** blocked **waiting for access** to it needs a **separate turnstile**. ::: :::warning - efficiency: associated with the thread **currently** holding the object, **rather than the object itself**. ::: :::info - **prevent priority** thread holding a lock **will temporarily acquire the highest priority** of any **process in** **the turnstile waiting** for the blocked object. - **priority-inheritance protocol**. ::: :::danger - User threads same as for kernel threads, - **except** **priority-inheritance protocol** :::

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.