Classical Problems of Synchronization

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

**Bounded-Buffer Problem

• 有n個buffers，且每個都可以放一個item。

1. Semaphore mutex的初始值設為1。
2. Semaphore full的初始值設為0。
3. Semaphore empty的初始值設為n。

• 在producer與consumer的process架構中，因為producer是wait(empty)、wait(mutex)，然後signal(mutes)、signal(full)，與consumer的wait(full)、wait(mutex)跟signal(mutex)、signal(empty)並不一樣，而且在wait()方面需要取得lock或spinlock才可以進入CS操作，這就是容易產生問題的所在。

Readers-Writers Problem

• 多個process可以同時共享data：

1. Readers：只能read the data，並不能執行任何更新。
2. Writers：可以read也可以write。

• Problem：只允許多個reader在同一時間進行read。

1. 只有單一writer可以在一個時間內存取共享的data。

• 共享data：

1. Data set
2. Semaphore rw_mutex的初始值為1。
3. Semaphore mutex的初始值為1。
4. Semaphore read_count的初始值為0。

Readers-Writers Problem Variations

• First variation：除非有witer去使用共享object，否則不能有reader在一直等待。
• Second variation：只要writer準備就緒，就會執行寫作ASAP。
• 以上兩種都有可能會產生「Starvation」的情況，導致更多的變化出現。
• 由kernel提供reader-writer locks，才能使某些系統得以解決problem。

Dining-Philosophers Problem

• 哲學家們終其一生在進行thinking與eating。
• 他們不會和坐在隔壁的鄰居互動，如果想要拿到桌上的筷子進行吃飯的話，就要等到兩邊的筷子可以拿取使用才行。
• 在一個案件裡面有5個哲學家，圍在一張圓桌上吃飯：
• 共享data：

1. 碗裡的飯(data set)
2. Semaphore chopstick[5]的初始值為1。

Dining-Philosophers Problem Algorithm

• Deadlock的發生：一開始大家都拿右方的筷子並沒有問題，但當大家要拿取左方的筷子時，會因為已經被坐在自己左邊的人給取走了，所以就會形成一個「Deadlock」的problem狀態。
• Deadlock的處理：

1. 只允許在一個圓桌上有4個人而已。
2. 要檢查左右是否都已經available，可以的話便能eating。
3. 使用asymmetric方法解決：也就是說，坐在奇位數位置的人先拿取左邊再拿取右邊的筷子；坐在雙數位置的人先拿取右邊再拿取左邊的筷子，方能解決問題。

Problems with Semaphores

• semaphore 的不正確操作：

1. signal (mutex).......wait(mutex)
2. wait(mutex)........wait(mutex)
3. 會遺漏wait(mutex)或是signal(mutex)，亦或是兩個一起遺漏掉。

• 因為這只是個機制，所以不會保證不會發生deadlock跟starvation。

Monitors

• 提供方便且有效率的機制給process synchronization使用。
• 有些系統不支持。
• 一次只能有一個process可以在monitor內執行。
• 不能解決所有的synchronization問題，但這已經是較為複雜的方法。

Condition Variables

• condition x, y;
• 有兩種operations允許condition variables：

1. x.wait()：一個process要invoke一個operation時，要一直等到x.singal()可以使用，不然就是suspended。
2. x.signal()：如果任何的x.wait()被invoked的話，其中一個process就會重新開始。
   1-但如果沒有任何x.wait()的話，對variable就不會有任何影響。

Condition Variables Choices

• 如果process P invokes x.wait()且process Q在x.wait()內暫停的話：

1. Ｐ和Ｑ不可以同時平行執行。如果Ｑ重新開始的話，Ｐ就必須要等待。

• operation 包含：

1. Signal and wait：Ｐ必須等待Ｑ，直到Ｑ離開monitor或是等待其他condition。
2. Signal and continue：Ｑ必須等待Ｐ，直到Ｐ離開monitor或是等待其他的condition。
3. Both have pros and cons：執行者可以自行決定要使用哪種語言。

• Monitors在Concurrent Pascal compromise內執行：

1. 當Ｐ執行signal後立刻離開monitor，然後Ｑ恢復重新開始。

Solution to Dining Philosophers

• 每個philosopher i invoke兩個operations pickup()以及putdown()在sequence中。
• 因為一次一個進入，所以並不會產生dealock，但因為動作慢所以可能會產生starvation的情況。

Resuming Process within a Monitor

• 如果多個process在condition x中排隊，然後x.signal()執行，那一個該被恢復呢？
• 如果依照FCFS執行的話，是不足夠的。
• x.wait(x)的conditional-wait構造：

1. 哪裡的c 是優先權數字
2. 如果process是高優先權的話，將會是被排程的下一個。

Synchronization Examples

• Solaris
• Windows
• Linux
• Pthreads

Solaris Synchronization

• 執行有多種不同的locks去支持multitasking,multithreading(包含real-time threads),multiprocessing。
• 從短的code segments中保護data的話，為了效率所以使用adaptive mutexes。

1. 類似於標準的semaphore spin-lock開始。
2. 如果保持lock，以及被thread執行在其他的CPU,spins。
3. 如果lock被不在執行狀態的thread給block和sleep，等待單一的lock被釋放。

• 使用condition variables
• 使用reader-writers locks，當code需要longer section去存取data。
• 使用turnstiles去命令在互相等待的threads，將其整理成一個list，等待mutex或是reader-writer解決，並以資料結構的方式處理。
• 將priority-inheritance一個turnstile給正在執行thread最高優先全的threads在這個turnstile。

Windows Synchronization

• 使用interrupt去保護global resources在uniprocessor systems存取。
• 使用spinlock在multiprocessor system。

1. Spinlocking-threads 將永不會被中斷。

• 也提供dispatcher objects user-land，或許哪個會act mutex,semaphores,events,and timers。

1. Events：會類似於condition variable一樣執行。

• 當時間到了，timer會通知一個或多個thread。
• Dispatcher objects是signaled-state(object available)或是non-signaled state(thread will block)。

Linux Synchronization

• Linux:

1. Version 2.6禁止使用interrupt去執行CS，但回應速度較慢。
2. Version 2.6之後使用fully preemptive，所以回應速度較佳。

• Linux提供：

1. Semaphores
2. atomic integers
3. spinlocks
4. reader-writer versions of both

• 在單一CPU系統時，spinlock可被可用或不可用的kernel preemption所取代。

Pthreads Synchronization

• Pthreads API是OS-independent。
• 提供了：

1. mutex locks
2. condition variable

• Non-portable 延期包含：

1. read-writer locks
2. spinlocks

Alternative Approaches

• Transactional Memory
• OpenMP
• Functional Programming Languages

Transactional Memory

• 一個memory transaction是很多的read-write operations序列，不會被中斷。

OpenMP

• OpenMP是一組由compiler指令與API所組成的，它們支持平行程式執行。
• 在程式碼中有#pragma omp critical 的指令，就像對待CS一樣是個atomic，不會中斷。

Functional Programming Languages

• 在不能維持的狀態中，比procedural languages提供更多不同的範例。
• 一旦variables被分配value，就不能被改變的。
• 增加有趣的functional languages，像是Erlang跟Scala，都是種方法去處理data race condition。