OS:Synchronization

Hello!

最近想開始複習一些零零碎碎的東西，上研究所後修完一些課，發覺自己的基礎還是有很多不足的地方，希望可以一邊寫筆記一邊把不懂的東西複習起來。

找到錯誤的話，可以提醒我一下< _ _ >。而最後也會整理出我看完之後，還是搞不懂的問題，有興趣的也可以一起討論～

Why we need synchronization?

為什麼我們需要進行”同步”(synchronization)呢？因為現在越來越多multicore的系統，不論是正在執行兩個不同的process，或是兩個thread，可能”同時”跑在“不同”的cpu上。當兩個cpu想要共享一塊memory的時候，就會發生一些問題。

下面來舉一個例子，一個producer不斷生產一個東西，一個consumer不斷取用東西。而共享的記憶體是一個counter，以及一個array。counter用來計算現在還有多少資源可以取用，而array就是producer以及consumer所生產以及取用的東西，陣列最大可以容納BUFFER_SIZE個元素。每當producer生產一個東西的時候就會上counter++，每當consumer取用一個東西的時候，counter- -。

(producer跟consumer的關係可以類比為compiler->assembler…等等)

例子是取自Reference[1]

而假設上面的程式編譯成組合語言後會變成下面的樣子。（當然不確定組語會編成什麼樣子，要看compiler怎麼做，這裡就當個理想的例子看吧～）

並且producer跟consumer“同時”跑在“不同”的cpu上，並且讓producer跟consumer各生產跟拿取一個物件。原本的counter是5，理想上，當我生產一個物件（counter++），且拿取一個物件（counter — — ），最後的counter應該要是5才對。

但最後的結果卻是4，可以知道一定是某個地方出問題了。

想要counter是5（正確答案）的話，那instruction的執行順序要照一定的順序走，但是當兩個cpu同時執行的時候，就沒辦法確保這個順序，於是發生了”race condition”。

為了避免發生這個問題，所以我們需要進行同步“synchronization”。

The Critical-Section problem

為了解決“同步”相關的問題，我們可以開始來思考一個問題。

也就是The Critical-Section problem.

想像一個系統裡，同時有n個processes，每個process都有一段被稱為critical section的程式碼，這段程式碼可能會更改一個全域變數，一張表，寫入一個檔案…等等（就像上面那個produecer-consumer例子裡的變數counter）。在這個系統裡，一次只能有一個process能進入critical section。

想要解決critical-section問題的話，需要符合三個需求。

1. mutual exclusion
   假如某個process正在執行critical section，其他process就不能執行他們的critical section。
2. Progress
   假如沒有process正在執行critical section，則只有那些沒有在執行remainder section的process可以當進入critical section的候選人。此外，這個選擇“誰可以進入critical section”的過程所導致的延遲，必須要是很明確的。
3. Bounded waiting
   某個process等待要進入critical section的時間必須要是有限的（不然就會發生starvation了）。

通常來說，在OS裡有兩種處理critical section的辦法。

preemptive kernels:更容易有所回應，不用怕有一個process會執行任意長的時間，適合拿來寫real-time programming。

nonpreemptive kernels:本質上就避免了race condition，因為一次只有一個process在執行kernel code。

Q:恐龍書讀到這裡我很疑惑，那假如在多核心的情況下，雖然沒有preemptive，不也會出現上面那個race condition的例子嗎？或是書上的意思是在nonpreemptive kernel，進入critical section的process不會被中斷，所以不會有race condition？這裡暫且保留。

Peterson’s Solution

這裡提出一個經典的軟體解法，雖然在現在的電腦架構下不一定可行，但是這個解法給了我們一些解決The critical-section problem的演算法描述。

簡單描述一下程式碼的意思，這裡假設只有兩個process，Pi跟Pj。

flag[i] = true;表示Pi想要進入critical section。

turn = j;表示現在實際上輪到Pj進入critical section。

雖然某些時候，turn會短時間內是i或是j，但是最後進入critical section的，一定會是其中一個，而不是同時進去。

所有解決The critical-section problem的解法都需要符合Mutual exclusion, Progress, 以及Bounded-waiting，下面來驗證這個解法有沒有符合這三個需求。可以往上複習一下這三個需求分別是什麼。

1. 驗證是否符合 “Mutual Exclusion”
   turn一定會是i或是j，不可能同時都是。
2. 驗證是否符合”Progress”
   Pi只有在entry section的時候，才會把flag[i]設為true（表示想成為候選人）。
3. 驗證是否符合"bounded-waiting"
   假如Pi跟Pj同時都想要進入critical section（flag[i], flag[j]都為true），而Pi成功進入critical section，而Pj在while迴圈裡等待。Pj最多就等到Pi執行完critical section，不會無限制地等待。

Synchronization Hardware

現在來談談硬體上可以怎麼解決The critical-section problem。有了硬體的支援，軟體上就可以更簡單的實作出各式各樣的同步機制了。這些解法都用到了 — — 鎖(Lock)，用來保護critical section。

現在的硬體為了能夠支援同步，所以推出了可以atomically（不會被中斷或打擾）比較一個word，或是兩個word各自交換內容的指令(instructions)。

這裡介紹兩個指令，test_and_set()、compare_and_swap()，並附上虛擬碼來描述這兩個指令的內容。

可以很清楚的感覺到，這兩個指令其實很像。但這兩個例子並不符合synchronization三個要求中的bounded-waiting，可能會讓一個process或thread等資源等到天荒地老。所以可以稍微改進一下，下面來一個符合bounded-waiting的實作。

因為多了一個在cyclic queue中尋找下一個候選人的動作，所以最多就等n-1個候選人離開critical section，就會輪到自己了，所以也解決了bounded-waiting的需求。

Start to Lock Something

接下來會介紹各式各樣的鎖，為了能夠實際試試看各種鎖是怎麼在程式碼上運用的，所以我隨意寫了一個可能發生race condition的範例程式。

順帶一提，我的系統是ubuntu 18.04，gcc 7.4.0

簡單來說，就是建立一個shared memory，然後fork出三個process，各對shared memory裡的一個int變數加一，每個process各加100000次，看最後的結果是不是300000，不是的話就是發生race condition了。

我輸出的結果是在100000~200000之間，幾乎沒有出現正確答案300000，所以我假設是出現race condition了。

接下來看看加上鎖之後有沒有什麼變化吧。

Mutex Locks

先來一個簡單的Mutex Locks例子。

Mutex Lock的概念很簡單，就是用一個boolean變數當作鎖，當沒有鎖上的時候（available == true），就可以進入critical section，並且把鎖鎖上。當鎖原本就已經鎖上（available == false）的時候，就開始等待這個資源。

這邊的虛擬碼實作的方式有個問題，就是使用了busy waiting的方式（當等待鎖時放的時候，是不停地執行空迴圈，直到鎖釋放後才會脫離空迴圈，進入critical section），而busy waiting會浪費cpu cycles去執行空迴圈。

mutex 使用這樣“實作”的方式也叫做spin lock。

上面提到了spin lock的缺點，而spin lock也有優點，就是process（或thread）在等待一個鎖的時候，不需要進行context switch，所以假如critical section夠短的話，這樣反而有利。

（這是我的猜測：在進行context switch的時候，kernel也需要執行一段程式。所以critical section的instruction數假如小於執行context switch的instruction數，選spin lock的方式比較有利。或是用兩邊的cpu cycles去算會比較好。）

Q：mutex lock要怎樣不使用spin lock方式實作呢？

虛擬碼看了心裡總是不踏實，還是想要在自己的系統上試試看使用mutex lock。那現在我們寫一個小程式來解決剛剛的race condition吧。

在這裡，我把鎖跟變數都放在shared memory裡，接下來試著跑跑看。加上鎖之後，輸出的結果確實是300000了！

read-write lock

想解決的問題：The readers-writers Problem

（待補完）

Semaphores

semaphore S是一個有號整數，擁有兩種操作：wait(S)以及signal(S)。

wait(S) : 
while(S) {
  while(S <= 0)
    ;
  S--;
}
signal(S) :
signal(S) {
  S++;
}

binary semaphore ： S的值只能是0或1，其實作用跟mutex一模一樣。
counting semaphore ：S的值是一個範圍，代表有限資源的數量。

semaphore也有其他有趣的玩法，例如想要S2一定要在S1執行結束後才開始執行的話，可以將S初始化為0，並且

S1;
signal(S);
-----
wait(S);
S2;

Condition variable

假設這時候有process( or thread)A, B。A這時要等待一個變數condi成為true才能繼續執行下去，但是這個變數condi是由B來改變的。

這時後有兩個解法。

1. 第一個是process( or thread)A去輪詢變數condi，假如condi還是false，就繼續sleep。當condi為true時，就能繼續執行下去。
2. 第二個方法就是使用condition variable，當A想要等待變數condi，而condi為false的時候，就使用condition variable(假設此變數的名稱為c)，就c.wait()，並開始sleep。B將變數condi設為true的時候，呼叫c.signal()，將A喚醒，並使A繼續執行下去。
   小總結：
   A call c.wait(), and go to sleep.
   B call c.signal(), and wake A up.

第一個解法，輪詢很吃cpu，而sleep時間過長又會導致回應時間不那麼即時。所以condition variable就是為了解決這個問題而產生的。

barrier

（待補完）

monitor

Monitor有一些性質：

1. 在monitor結構裡的變數，只有monitor裡的function能取用跟改變。
2. 一次只能有一個process進入monitor，如此一來，就天然地形成了mutual exclusion，不需要程式設計師再去加鎖解鎖，可以減少人為的錯誤。

monitor 示意圖

initialization code :當建立monitor物件時，會需要對一些變數進行初始化。
shared data :一些process ( or thread)想要共享的資源。
entry queue :一些想要進入monitor的process ( or thread)
operation : 對shared data進行的操作，或是只能在monitor裡進行的操作。

有人已經證明monitor跟semaphore是等價的，只是monitor不需要程式設計師戰戰兢兢的需要自己上鎖跟解鎖。

但光是使用 monitor 可能會有一個問題，假設有一對 process ( or thread)A, B。 A, B 都想要進入 monitor。當 A 進入 monitor 的時候，B 就需要進入等待。但是A剛好需要B正在使用的資源才能退出 monitor ，於是陷入A與B互相等待的情況，也就是發生死結( dead lock)。

為了避免這種情況，另外要服用上面已經介紹過的，”condition variable”這種機制。

加上condition variable的monitor示意圖

延續上面提到的例子，假如A需要B的資源的話，A可以呼叫condition variable x的x.wait()，此時A進入睡眠，並丟到x的queue（不一定需要first in first out，關於排程可以自己另外設計）。

因為A進入睡眠了，這時候等同於退出monitor，這樣B就可以進來執行，並且釋放資源，B可以呼叫x.signal()，讓A可以有繼續執行的權利。(在這裡我們先假設x的queue裡只有A)，於是就避免掉了dead lock的問題。

這時後有兩種想法出現：

1. Signal and wait:
   B在x.signal()之後就進入等待，讓A進入monitor執行。
2. Signal and continue:
   B在x.signal()之後繼續執行，執行完之後再讓A進入monitor。

接下來簡單介紹monitor要怎麼解決Dining-Philosophers Problem。
（等一下會對Dining-Philosophers Problem進行簡單的介紹。）

這裡所使用的解法是等等會提到的第二個：只準哲學家一次拿兩隻筷子（拿兩隻筷子這件事需要變成critical section）。

但是這個解法還是”有問題”，那就是有可能會有哲學家一直沒有機會拿起筷子，導致starve to death。

Q: 可以思考看看，要怎麼才能再避免starve to death呢？

接下來試著使用semaphore來實做monitor。

想簡單了解每個變數的話，可以實際用一個例子走過一遍（我是這麼做的）。假設現在有兩個process ( or thread)A與B，A需要等一個變數condi為true才能夠繼續往下執行，而condi是由B所控制。

1. A 進入 monitor。
   mutex = 1→ mutex = 0//wait(mutex)
2. A 因為condi為false，於是呼叫x.wait()開始等待x_sem，並退出monitor。雖然說是退出，但A其實還在”body of F”裡，只是可以讓process ( or thread)可以有進入monitor的權限。
   x_count = 0 → x_count = 1//x_count ++
   mutex = 0 → mutex = 1 //signal(mutex)
   //wait(x_sem)
3. B進入monitor
   mutex = 1 → mutex = 0 // wait(mutex)
4. B呼叫x.signal()，開始等待next，退出monitor。
   next_count = 0 →next_count = 1 //next_count ++
   x_sem = 0 → x_sem = 1 // signal(x_sem)
   //wait(next)
5. A進入monitor
   x_sem = 1 → x_sem = 0 // wait(x_sem)
   x_count = 1 → x_count = 0 //x_count- -
6. A徹底離開monitor
   next = 0 → next = 1 //signal(next)
7. 讓B可以進入monitor
   next = 1 → next = 0 //wait(next)
   next_count = 1 → next_count = 0 //next_count- -
8. B徹底離開monitor
   mutex = 0 → mutex = 1 // signal(mutex)

接下來思考一下monitor與排程。

當有 process ( or thread) 使用 x.wait() 去等待某個變數的時候，就需要其他 process ( or thread) 呼叫 x.signal() 來喚醒某個在 condition variable 的等待池裡的 process ( or thread) 。這時候要選哪一個 process ( or thread) 來喚醒呢？可以用最簡單的first in, first out，也可以在x.wait()的時候下某些權重來當作參考。

假設現在我們希望等待時間最少的優先取用，就可以實做類似

x.wait(time)

的機制，把一個權重（這裡是時間）當做參數傳入，並利用權重進行排序。在這裡就是時間越少的排在越前面。

想要有更多的理解的話，可以參考看看Reference[4]。

Priority Inversion

假若現在有三個process，L, M, H。而他們的權重由低到高為L < M < H。並且現在H跟L都想要共用一個資源R，而現在R是被L給把持住，所以H等待L。因為L的權重比M還要小，於是M有權力搶佔L的資源。而這時候H的等待時間被M給影響了，在這種情況，H的權重感覺上其實比M還要小，但實際上應該是要H先執行才對。

有一個簡單的解法就是priority-inheritance，當L使用資源R時，可以繼承所有需要資源R的process中權重最高的那個權重，使用完資源R後，L的權重再回復成原本的樣子。

這樣子M就暫時不能搶佔L了，也就不會阻擋到H的執行。

classic problem of synchronization

一開始我們遇到了race condition，所以我們提出了使用“鎖”來解決，但是鎖的使用上又會再度遭遇其他問題，所以大概可以這樣整理出目前所遇到的困難：

發現問題（The critical-section problem）->解決問題（Lock）->在這個解法中發現問題（DeadLock & Starvation）->解決問題->……以此類推，當解決一個問題後，就會衍生出其他問題需要解決。

這邊再介紹三個同步問題：

1.The Bounded-Buffer problem

這個例子在一開始有提過，就是producer會生產物件，然後consumer會消耗物件，並且最多能生產的物件有一個數量上的限制。
假設這個限制是n。
於是consumer與producer可以共享三個資訊：

並且可以用虛擬碼大概表示一下producer跟consumer相互溝通的方式。

2.The Readers-Writers Problem

當一塊被分享的記憶體被許多process(thread)共享時，只要大家都只是對它同時進行讀取（read）則不會發生任何問題。但是當有人想要對這塊記憶體進行寫入的時候，就可能會發生問題了。

a. first readers-writers problem

當目前沒有任何reader的時候，才可以進行寫入。

目前沒有writer在進行的話，reader彼此間不需要等待。

當writer獲得修改權限並開始進行寫入的時候，reader要等待寫入完成。

寫一個簡單的虛擬碼實作的話，會像下面這樣：

然而這個方式會導致writer的starvation，因為reader可能會源源不絕的增加，這樣子write會一直在等待的狀態。

b. second readers-writers problem

當一個writer在等待，想寫入共享資源的時候，不能有新的reader開始讀取共享資源。

所以會變成reader可能會starvation，假如有許許多多witer在等待的話，就會一直不能有新的reader進行讀取了。

first v.s. second
first readers-writers problem : 有一個writer在等待的時候，還是可以不斷有新的reader進行讀取。

second readers-writers problem : 有一個writer在等待的時候，就不能有新的reader進行讀取了。

Q:starvation free solution？

readers-writers lock適合用在容易區分“讀操作”跟“寫操作”的應用上。另外也很適合用在”同時讀取“的情況多於“同時寫入”的情況。因為readers-writers lock允許多個process進行同時讀取，效率較高。

3.The Dining-Philosophers Problem

現在假想有五個哲學家圍著一個圓桌坐著，他們花盡他們的一生用來思考與吃東西。圓桌的中央有米飯，並且有五隻筷子擺在圓桌上。當一個哲學家在思考的時候，不會跟兩旁的人進行溝通。而思考到肚子餓的時候呢，就會想要拿起靠近他的兩隻筷子去夾米飯來吃。

哲學家一次只能拿起一隻筷子，並且很明顯的，假如有一隻筷子已經被其他哲學家拿走了，這個哲學家就必須另外一個哲學家用完筷子放回桌上後，才能使用這隻筷子。

當一個哲學家拿起兩隻筷子後，在吃飯的過程中都不會把筷子給釋放掉，直到吃到不再餓肚子。

簡易解法，就是每一隻筷子都上一個semaphore，虛擬碼如下：

但這個解法有個問題，就是當所有哲學家同時肚子餓，同時拿起自己右手邊的筷子的時候，就會出現deadlock了。

於是Reference[1]再推出其他三個解法：

1. 一次只能有四個哲學家坐在餐桌上（筷子仍舊保持5隻）
2. 只準哲學家一次拿兩隻筷子（拿兩隻筷子這件事需要變成critical section）。
3. 依照順序為每個在餐桌上的哲學家進行編號。單數的哲學家一定只能先拿自己左手邊的筷子，再拿右手邊的筷子；雙數的哲學家一定只能先拿自己右手邊的筷子，再拿左手邊的筷子。

要注意，能夠避免deadlock的解法，不一定也同時能避免starvation，所以當解決類似的問題的時候，要確保其中一個哲學家不會因為一直要不到資源而餓死（starve to death）。

synchronization examples

Windows

（待補完）

Linux

（待補完）

Solaris

（待補完）

Pthreads Synchronization

（待補完）

other features for synchronixation

Transaction Memory

（待補完）

OpenMP

（待補完）

Functional Programming Language

（待補完）

Bye Bye!

讀完這一章，覺的CS的東西有很多概念其實是通用的，了解其中一邊後，可能可以實做在其他地方，像是cpu scheduling跟monitor的x.wait(time)感覺有異曲同工的點。

感謝你的閱讀< _ _ >。

Reference

[1]Operating system concepts:ch5 process synchronization

[2]advanced programming in the UNIX environment:ch11 Threads

[3]OS 同步問題 https://mropengate.blogspot.com/2015/01/operating-system-ch6-synchronization.html

[4]監視器(monitor) https://zh.wikipedia.org/wiki/%E7%9B%A3%E8%A6%96%E5%99%A8_(%E7%A8%8B%E5%BA%8F%E5%90%8C%E6%AD%A5%E5%8C%96)

[5]condition variable 詳解 http://www.wuzesheng.com/?p=1668

Question

[1]nonpreemptive在本質上的就避免掉了race condition嗎？假如在多核心的情況下呢？

[2]mutex lock該怎麼用不是spin lock的方式實作？

[3]starvation free solution for readers-writers problem

[4]上面介紹monitor的時候，利用monitor+condition variable解決了Dining-Philosopher的dead lock，但沒有解決starve to death的問題。可以思考看看，要怎麼才能再避免starve to death呢？

進度

開始寫使用semaphore實做monitor的解說

semaphore筆記

barrier