# OS-Chap6 - Synchonization
###### tags: `作業系統 Operating System note`, `110-1`, `2021`
# Contents
[TOC]

---

## Critical-Section（CS）

### Background
- data inconsistency(資料不一致)：
- 在程式的許多地方同時處理同一塊的共享資源(shared memory)。
-

### Race Condition
- happened : 兩個以上的 process 同時存取、修改一個 shared memory (global variables)
- result : 將導致電腦只會存最後放入的 data。
> - 對 shared memory 不同步訪問產生的問題
用 Consumer & Producer 來解釋 race condition

- 上圖中的 counter ++; 與 counter --; 編譯成 machine code 時，會變成像下面的圖的樣子
- counter ++;
- counter --;

## The Critical-Section Problem
- entry CS
- CS
- exit CS
- reminder Section(RS)

### Requirement of CS solution :white_check_mark: < 三個 > :white_check_mark:
1. **Mutual Exclusion**
- 確保在同一時間，只有一個 process 再 CS 中被執行。
> - 否則將導致上方 race condition 的情況發生。
2. **Progress**
- 若沒有 process 在執行 CS，而有其他 process 需要執行時，不能讓 process 無限制等待。
> - 為避免兩個 process 都想進入 kernal 執行，但卻又因為偵測到對方想執行，而互相禮讓導致雙方都無法進入的情況發生。
3. **Bounded Waiting**
- 要有等待上限的概念。
- ex. 若有一 process 的 priority 較低，則該 process 可能永遠無法被執行。

- 在需要critical section的前面跟後面加入 entry section 和 exit section

## Solution of CS-problem

### Software
- 用軟體的方式解決該問題。

#### Method of Two processes __ Algorithm
>:exclamation: only for two processes :exclamation:


// in P0
do{
    while( turn != 0 ) ; // 如果還沒輪到我，我就在這行一直執行死迴圈，不往下做
      --  InCirticalSection
    turn = 1; // 做完就把使用權讓給對方執行
      --  Reminder Section // 剩下的 code
}while(1)

- Why 不符合 Progress 條件？
- progress 是指說「我想要執行而且裡面沒有人的時候，就可以執行」
- 假設現在 Pi 想進 CS ，但 Pj 不想。
可是 turn 一直 = j，而一定要等 Pj 進去 CS ，等他出來後才會更動到 turn 的值 (turn = i)
- 這樣子 Pj 就參與到決定 turn 的過程，所以違反 progress 的條件。
- 改良方法 :
- 即便不想進 CS，也要先把控制權禮讓給對方(ex. Pi->turn = j) ((做之前先把控制權交出來就對ㄌ。 ，
#### :heavy_exclamation_mark: 重要觀念 :heavy_exclamation_mark:
#### process 若想執行 CS 的程式碼，須符合以下條件
#### 1. 我舉手(interrupt?) ➞ 我想進入(執行)
#### 2. 輪到我進入 ➞ 使用權輪到我 ...turn = "me"

- ### Peterson's Solution

---

### Hardware support
> ### -> disable interrpt == LOCK.
>>>>>>>>>>>>>>>>>>>>>> ---
- #### :star: **先備觀念** :star:
1. lock = 保護 CS。
2. atomic = non-interrupt (不可被中斷)
3. atomic hardware instruction 是什麼?
- - TestAndSet(TAS) 和 CompareAndSwap(CAS)
4. spinlock 是什麼?
- 透過 hardware instruction(atomic) 指令執行 acquire() 和 release()
- 但這的方法需要用到 busy waiting (polling)，一直不斷的發出消息，然後問問問問問問問問。
===> 所以這個方法就會叫做 spinlock

>>>>>>>>>>>>>>>>>>>>>>> ---

- Uni-processor(單一處理器)
- disable interrupt ((= Lock
- enable interrupt ((= unlock
> - 開關 interrupt 對於 multi-processor systems 太沒效率 (要全部 processor 都把 interrupt 關掉才行(?))

:star: 總體來說，把 CS 用 locking 鎖住，然後在 uniprocessor 時，將 interrupt 給禁止掉，就不會發生任何 preemption 的情況。
:heavy_exclamation_mark: 但這是一個非常不好的方法(沒有效率)，所以需要用到 atomic 方法:heavy_exclamation_mark:
> :heavy_exclamation_mark: lock 和 enable/disable interrupt 的差異在**lock 利用 global variable 的方式」**，讓多個 processor(?) 可以同時知道這塊區域是 CS，所以被鎖起來就是不能用，但 disable interrupt，只會關掉一個 processor，若要讓其他 processor 也不能進入 CS，就要一個一個關，極度沒有效率。:heavy_exclamation_mark:

- atomic hardware instructions. ( 硬體指令)
- Atomic = non-interruptible(不可中斷指令)
- TestAndSet(TAS) : test 記憶體的 word + set value(lock/unlock = 1/0)
- CompareAndSwap(CAS) :
> - 但兩者都沒辦法做到 bound waiting, WHY?
> - 未規範 order 使得次序以亂數(隨機/誰跑到就誰get key)決定。
> - 導致 Pi 做完之後，可能可以馬上繼續使用 CS，其他 processes 永遠無法使用 CS。
> - 兩者的缺點:
> - 只有 kernel mode 能用
> - need time
> - multi-processor 會失效，單處理機上不好(busy waiting)
> - starvation (No bounded waiting)

>>>>>>>>>>>>>>>>>>>> ---

- ## mutex lock
- 用一個boolean變數當作鎖
- 沒有鎖上的時候（available == true），就可以進入critical section，並把 lock 鎖上。
- 當鎖原本就已經鎖上（available == false）的時候，就開始 waiting 這個資源(死迴圈)。
> - 死迴圈 -> busy waiting -> spinlock 的一種。

### Semaphone

- Semaphore S是一個有號整數變數(integer variable)。
- 可透過兩個方法執行(two operation)：
1. wait()
2. signal()
==> 為不可被中斷(non-preemptive)的方法。
- 是個Synchronization tool，提供更複雜、尖端的方法給process去同步活動。
- 不同的 semaphone
- binary semaphore：S 的值只能是 **0 或 1** ，其實作用跟mutex一模一樣。
- counting semaphore：S 的值是一個**範圍**，代表**有限資源的數量**。

>>>>>>>>>>>>>>>>>>>>>> ---

:star2: Software & Hardware solution 整理 :star2:
- single processor
- disable interrupt
- Only available in kernel space
- Increase interrupt latency
- Spin lock (test and set, swap)
- Waste CPU cycles

- Multiprocessor
- 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

> ## 以下提供工具去 slove
## Classical Synchronization problem
### Q1. Producer & Consumer problem

### Q2. Dining-Pilosophers problem
- Deadlock problem
- 當兩位哲學家在 eating，而有一位哲學家只拿到一隻筷子時
- 

- solve:
1. By Deadlock Avoidence
> 動態配置的方式去偵測會不會進入 unsafe state，有的話就把不進入 unsafe state(unsafe 只是有機會發生 deadlock，不是一定發生 deadlock)
- 
2.+ 3.+ 4.
- 

### Read & Write problem
:-1: 待補待補 :-1: 解決方法都差不多啦
把 Critical Section 的 shared memory() 用 **lock(mutex)鎖起來 **
===> **wait(mutex)** 丟進 queue 裡面 sleep
等 lock 沒人要用的時候 ((-->表示可以拿到鎖ㄌ!
**就叫醒在 sleep 的第一個 process**
===> **signal(mutex)**

### Monitor
- Monitor 有一些性質：
1. 在 monitor 結構裡的變數，只有 monitor 裡的 function 能取用跟改變。
2. 一次只能有一個 process 進入monitor，就自然地形成 mutual exclusion，不需要 programmer 再去 lock/unlock，可以減少人為的錯誤。

- ### Condition variable
- Q : 假設有 process( or thread) A, B。A 這時要等待一個變數 condi 成為 true 才能繼續執行下去，但是這個變數 condi 是由 B 來改變。
- A :
1. process(or thread) A 去 polling 變數 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繼續執行下去。

:heavy_exclamation_mark: 小總結 :heavy_exclamation_mark: :star::star::star:
1. A call c.wait(), and go to sleep.
2. B call c.signal(), and wake A up.
> 第一個解法，polling 很吃 cpu，而 sleep 時間過長，又會導致回應時間不即時。所以 condition variable (塞入queue 中 waiting，等有空閒時再 wakeup 他)就是為了解決這個問題而產生的。

## HomeWork
> 6.1, 6.2, 6.3, 6.4, 6.5, 6.8, 6.9, 6.14
### 6.1
- 


### 6.2
- 
- 


### 6.3
- 
- 


### 6.4
- 

### 6.5
- 

### 6.8
- 

### 6.9
- 

### 6.14
-