# Chp 6 Synchronization Tools
###### tags: `作業系統`
# P.4

Process 之間如果有 dependency或涉及shared data，就會有consistency的問題

# P.7 Race condition (Race hazard)

* <font color='#ff0000'>考</font> 定義:Several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.



>[color=#FF00FF] (補充)有人問i\++跟\++i的區別
>以c來說i\++跟\++i最主要的差異在i\++會先將原本的i保存起來，而\++i則不會，對早期的編譯器來說\++i是會比較有效率的，不過以現在來說絕大多數的編譯器都會針對這兩個操作做最佳化，所以對一個for迴圈語句for(;;i\++ or \++i)其實是沒有效率差別的。
>如果沒有特殊需求的話，建議還是使用\++i為主，雖然沒有強大的理由要這麼做，但哪天你用的tool chain沒有幫你最佳化的話程式依然不會受影響。
>
>事情到了c\++就不太一樣了，如果是內建的整數型態的話跟C語言並無二致，但是如果你是針對某些型態覆寫了原本的\++ operator，那麼編譯器自然沒辦法針對這種操作最佳化，i\++跟\++i的差異就會出現。
>[name=Neko]

# P.8 Critical Section

* critical section是指程式碼中會存取到共享資源的區段，共享資源有很多種，像是共用裝置或是共用記憶體，最重要的是這個共享資源有**無法被多人同時存取**的特性。

在entry section的時候process會發出request，後面會介紹如何解決critical section problem

# P.11
To make sure that an implementation of critical sections works properly, there are three conditions that must be satisfied.

1. **Mutual Exclusion**
- 任一時間點，只允許一個 process 進入他自已的 critical section 內活動。
2. **Progress**
- 選擇進入critical section的程序不能永久被推遲
- 必須在有限的時間從想進入 critical section 的 process 中，挑選其中一個 process 進入 critical section，隱含**No Deadlock**。
>[color=#FF00FF]這邊是說只有那些已經說要進入critical section或是將來可能馬上要進入critical section的process可以參與selection，而且這個selection要在一個limit time之前完成，也就是說要馬上決定誰可以使用共享資源，這個目的是要避免deadlock或是livelock的情況發生。
>[Reference](https://stackoverflow.com/questions/33143779/what-is-progress-and-bounded-waiting-in-critical-section)
>[name=Neko]
3. **Bounded Waiting**
- 自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。
- 若有 n 個 processes 想進入，則任一 process 至多等待 n-1 次即可進入
- **避免starvation**
>[color=#0000FF]中文的解釋大多來自這篇，否則講義寫的英文太難記了
>[參考](https://mropengate.blogspot.com/2015/01/operating-system-ch6-synchronization.html)
>[name=Conan]
>
# P.12
- Peemptive
- Non-preemptive
- interrupt disabled
- Non-preemptive可避免race condition的問題
# P.13 Peterson’s Solution
(有機會會考)
- 只適合兩個process時


* turn 不是i就是j，不能同時等於

* <font color='#ff0000'>考</font> Any solution to solve a critical section problem must satisfy three requirements. Please explain the three requirements.(%) Explain how does Peterson solution satisfy the three requirements.



# P.16 Synchronization Hardware

## Using Lock

* test_and_set

boolean test_and_set (boolean *target)
          {
               boolean rv = *target;
               *target = TRUE;
               return rv:
          }


do {
    while (test_and_set(&lock)) ; /* do nothing */ 
            //只有當lock是false時才能進入critical section
             
                 /* critical section */ 
          lock = false; 
                 /* remainder section */ 
       } while (true); 

* compare_and_swap

int compare_and_swap(int *value, int expected, int new_value) { 
         int temp = *value; 

         if (*value == expected) 
            *value = new_value; 
      return temp; 
     } 


do {
    while (compare_and_swap(&lock, 0, 1) != 0) ; /* do nothing */ 
            //只有當lock是0時才能進入critical section
            
          /* critical section */ 
       lock = 0; 
          /* remainder section */ 
      } while (true); 

>[color=#FF00FF]上面兩個function是假設atomic的前提，實際上這種寫法並不保證是atomic就是了。
>要保證的話可以使用編譯器支援的atomic function，這樣可以確保編譯器產生的組語是不可分割的操作。
>當然，前提是ISA有支援囉，像是test and set的instruction BTS在x86裡本身就有支援。
>[name=Neko]
>

>[color=#00a000]
>
>看了[這篇](https://stackoverflow.com/questions/3659336/compare-and-swap-vs-test-and-set)還是不太清楚上面2個function的差異，
>就結果來說好像一模一樣
>[name=Omnom]
* **Atomic = non-interruptible**
# Mutex Lock

>[color=#000000] 推薦[這篇](https://dev.to/rinsama77/process-synchronization-with-busy-waiting-4gho)，寫得很好笑。
>[name=Peter Peter]
* Calls to **acquire()** and **release()** must be atomic
* Require busy waiting (c.f. Semaphore doesn't need busy waiting)

<font color='#ff0000'>考</font>

Q : What is the main disadvantage of Mutex Locks? Simply describe it.
A :  Requires busy waiting
     lock therefore called a spinlock.

* <font color='#ff0000'>考</font> **busy waiting**: A process repeatedly checks to see if a condition is true.

<font color='#ff0000'>考</font>

acquire() {
    while (!available) 
          ; /* busy wait */ 
       available = false;
    } 
release() { 
       available = true; 
    }
    
   do { 
    acquire()
       critical section
    release() 
       remainder section 
 } while (true); 

<font color='#ff0000'>考</font>

Which of the following statements are true? If false, why? (15%)
(A) Hardware support synchronization implements lock 
mechanism with atomic instructions which are interruptible.
(B) There is only one process can be active within a monitor.
(C) Mutex lock can be implemented with binary semaphore.
(D) Semaphore can be implemented without busy waiting.
(E) Monitor handles synchronization issues with condition variables containing two operations: 
wait and signal, which are also used in semaphore.

B C D

(A) Atomic instructions are not interruptible.
(E) Wait and signal in semaphore act as lock with resource counter, which are not related to condition variables at all.

# Semaphore

* **wait()** and **signal()**

* Implementing with no busy waiting
* Two operations:
- **block** – **place the process** invoking the operation on the appropriate **waiting queue**
- **wakeup** – remove one of processes in the waiting queue and **place it in the ready queue**

typedef struct{ 
   int value; 
   struct process *list; 
   } semaphore; 


wait(semaphore *S) { 
   S->value--; 
   if (S->value < 0) {      add this process to S->list; 
      block(); 
   } 
}

signal(semaphore *S) { 
   S->value++; 
   if (S->value <= 0) {      remove a process P from S->list; 
      wakeup(P); 
   } 
} 

>[color=#000000] Semaphore 發明者 Dijkstra 是荷蘭人，所以 P(), V() 意思就是英文的 wait(), signal()。[參考](https://mropengate.blogspot.com/2015/01/operating-system-ch6-synchronization.html)
>[name=Peter Peter]
# Deadlock and Starvation
<font color='#ff0000'>考</font>
* **Deadlock** – two or more processes are **waiting indefinitely for an event** that can be caused by only one of the waiting processes

* **Starvation** – 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**

# Monitors

* A high-level abstraction that provides a convenient and effective mechanism for process synchronization
* Only one process may be active within the monitor at a time