# Background

共享的資料同時被不同 Process /threads 存取時可能導致 data 的不一致性 (inconsistency)。為了維持 data 的一致性，需要有機制去確保合作的 process 的執行的順序

# Consumer & Producer Problem

之前使用 in, out position ，現在使用 count value

# Concurrent Operations on counter

除了 Buffer 之外 Counter 也是 share variable
instruction level 其實有三道指令
- counter++ 要先將 counter 從記憶體中移到 register，加上 1 之後，再存回記憶體
  counter++ in machine language
  1
  2
  3
  move ax, counter
  add ax, 1
  move counter, ax
- counter-- in machine language
  1
  2
  3
  move bx, counter
  sub bx, 1
  move counter, bx

# Instruction Interleaving

Context switch, Preemptive scheduling 等因素可能不是一次執行完成，導致執行結果不符合預期

問題：這樣的穿插情形 counter 可能 4、5、6，但實際上要是 5
解：如果把 cpu burst 做完，就不會有這種情況

# Race Condition

有多個 process 在同時競爭（相同）的資源，結果與存取資源的順序性有關連時 race condition 就會發生

通常將每一個 Process 存取 shared data 的 code segment 稱作 Critical Section
shared data 的值會由最後一個執行的 process 所決定
single-processor machine 要達成同步可透過 disable interrupt 或 Non-preemptive scheduling，但在 User Program 中不可能使用，會影響整個系統的運作
解法：同步化 concurrent processes

# Critical Section

-	-	著重於	-
高階 (位於函式庫中)	Monitor	同步問題之解決	-
中階 (通常於 System call)	Semaphore	同步問題之解決	-
基礎建設 (作業系統核心製作)	Software solutions、Hardware instrustions support	C.S. 設計的正確與否	Disable interrupt 也在基礎建設

# Critical-Section Problem

目的：建立 Processes 之間合作的 protocol
Problem description
- N 個 Processes 競爭使用 shared data
- 每個 process 有一個 code segment 稱為 critical section，也是 shared data 被存取的區域
- 需要確保 mutually exclusive
一般常見 critical section 的架構如下

# Critical Section Requirements

Mutually exclusive：任一時間點，只允許一個 process 進入他自已的 critical section 內活動
Progress：必須同時滿足（tips: 有空位時讓「想進的人」「馬上」進入）
- 不想進入 critical section 的 process 不能擋其它 process 進入，即不可參與進入 critical section 的決策過程
- 必須在有限的時間從想進入 critical section 的 process 中，挑選其中一個 process 進入，隱含 No Deadlock
Bounded Waiting：自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。即若有 n 個 processes 想進入，則任一 process 至多等待 n-1 次即可進入，隱含 No starvation

# Critical-Section Solution & Synchronization

# Algorithm for Two Processes

Shared variables
- int turn
- turn = i (Pi 可進入 critical section)
Requirement
- mutual exclusive - YES
  
  因為 turn 值只會為 0 或 1 之其中一個值，所以只有一個可進入 C.S.
- progress - NO
  
  假設目前 P0 在 R.S. (且 P0 不想進入 C.S.)，而目前的 turn = 0 且 P1 欲進入 C.S.，但是因為 P0 仍在 R.S. 無法交付 turn ，所以被 P0 阻礙進入
- bounded wait - YES
  證明 P0 無法連續兩次進入 C.S 之中：
  1. 假設目前 turn = 0，且 P0 已先早於 P1 進入 C.S. 使 P1 開始等待
  2. 若 P0 離開後又想立刻想再次進入，但因為 P0 離開時會將 turn = 1，使得 P0 無法再度比 P1 早進入 C.S.
  3. 這一次 P1 必定先進入之，所以 P1 最多等一次後即可進入

以上的程式碼其實並不完美，這個程式要能順利運作的前提是兩個 Process 必須輪流執行，但 while loop 不保證執行順序

# Peterson’s Solution for Two Processes

為了解決上述 Progress 的問題，我們引入另一個變數 flag ，用來表示 Process 是否想要進入 critical section 中

do{
 flag[i] = TRUE; //代表 Pi 已經準備好要進入 critical section
 turn = j; //代表把 key 交給別人，禮讓的概念

 while ( flag[j] && turn == j); //檢查其他 Process 是否可進入 critical section，確認沒有其他 Process 要進入 critical section 後自己再進入 critical section

 [CRITICAL SECTION]

 flag[i] = FALSE;

 [REMAINDER SECTION]

} while (TRUE);

Shared variables
- int turn = 0 (initially)
- turn = i ⇒ Pi can enter its critical section (key)
- boolean flag[2] (initially flag [0] = flag [1] = false)
- flag [i] = true ⇒ Pi ready to enter its critical section
Requirement
- mutual exclusive - YES
  
  兩個 process 都要等對方的 flag 變 false 才能進入 CS
- progress - YES
  - 當一個 process 不想進入 CS 時，另一個 process 可以直接進入 CS
  - 當兩個 process 都想進入 CS 時，會看 turn 的值決定誰先進入 CS
- bounded wait - YES
  
  當一個 process 想要進入 CS 時，最多只需要等另一個 process 一次就可以進入 CS

# Bakery Algorithm (n processes)

每個行程進入 C.S. 之前，會抽號碼牌
產生號碼的方法會產生 non-decreasing order 的序列
有最小號碼的行程先執行他的 C.S.
號碼牌的比較方式：
1. 比較號碼大小，號碼小的先進入 C.S.
2. 號碼相同時，比較行程編號，編號小的先進入 C.S.

# Hardware Support

Critical Section Problem 的發生是因為 shared variable 的修正可能被打斷，若某些指令我們可以一行完成就可以避免 race condition 的問題
前面都是在說軟體上的支援，若硬體可以將指令變成 atomic instructions ，就沒有同步的問題

atomic : 無法中斷執行的最小單元
hardware solution 缺點 (特指 TAS 和 SWAP)
- 只有 kernel mode 能用
- need time
- 多處理機上會失效，單處理機上不好 (busy waiting)
- starvation
例如 : TestAndSet (var), Swap (a,b)

# Atomic Test And Set()

檢查並設置是一種不可中斷的基本 (原子) 運算 (atomically)，它會寫值到某個記憶體位置並傳回其舊值

boolean TestAndSet (bool &lock) {
    bool value = lock ;
    lock = TRUE ;
    return value ;
}

Requirement
- Mutual exclusion - Yes
- Progress - Yes
- Bounded-Wait - No

# Atomic Swap()

想法：a, b 兩值互換
多個 procress 也行得通
key 可表示是否想進去
搶到 lock 的人才能進去
Requirement
- Mutual exclusion - Yes
- Progress - Yes
- Bounded-Wait - No

# Synchronization Tools

# Semaphores

Semaphore 是一個同步物件，用於保持在 0 至指定最大值之間的一個計數值。(Semaphore do not require busy waiting, using waiting queue)

記錄一個特定的資源有多少 unit 是 available
- #record = 1 –-> binary semaphore, mutex lock
- #record > 1 –-> counting semaphore
利用兩個 atomic operations wait & signal 來存取 (注意與 critical section 的 wait & signal 不同)

# Non-busy waiting Implementation

想法：當 Process 因為同步事件 (Synchronization event) 被長時間卡住，則可以使用 Block system call 將該 Process 送入 Blocked state，所以不會與其他 Process 競爭 CPU ，直到該事件觸動了，才會喚醒 (Wake up system call) 該 Process 移至 Ready state
優點：等待中的 Process 不會與其他 Process 不會浪費 CPU time
缺點：需額外付出「Context switching time」

system call 要考慮 context switch、re-scheduing 的影響，成本比 while 來得高。一般來說，等待時間很短的會用 busy waiting，反之則使用 non-busy waiting

# Cooperation Synchronization

解決：有些情況我們關心不同 Process 間的執行順序，考慮兩個 thread P1 & P2 分別執行 S1 & S2，S2 必須在 S1 完成後才可執行

# Monitors

Monitors 是一個用來解決同步問題的高階資料結構 (物件導向)(Semaphore and monitor have the same power in solving synchronization problem.)

Monitors 的組成
- 共享變數宣告區
- 一組程序
- 初始區
特色：
- 宣告在 monitor 的變數只有 monitor 的 procedure 可以存取 (類似 class 中的 private 區)
- monitor 中有 condition 型態的變數，提供 programmer 設計同步問題之用 (for sync policy)
- monitor 直接保障 monitor 中變數和程序的互斥性質 (mutex, not sync policy)，不可有多個 process 呼叫 monitor 的某個程序 (在 semaphore 中要多加許多 mutex 保護變數)

# Monitor Condition Variables

為了允許行程在 monitor 做等待，需要一個 condition
Condition variable 只能被 wait () and signal () 使用
Operations on condition variables
- x.wait();
  - process invoking this operation 被中斷直到另一個 process 調用完
- x.signal();
  - 繼續一個先前被中斷的行程
  - 如果沒有行程被中斷，則 signal operation 沒有影響
  - 相反的，signal 不斷改變 semaphore 的 state
- 單純就是 linked list 的 queue
  - wait –-> enqueue
  - signal –-> dequeue
  - 是 queue 不是 counter

# Classical Problems of Synchronization

常見的問題如下：

Bounded-Buffer (Producer-Consumer) Problem
Reader-Writers Problem
Dining-Philosopher Problem

# Bounded-Buffer (Producer-Consumer) Problem

背景：N 個 buffers，Producer 製造項目，Consumer 消耗項目
Shared variables
- N Buffer initial mutex = 1 ：互斥鎖，避免同時複寫
- initial full = 0：producer signal，consumer wait
- initial empty = N：producer wait，consumer signal
Producer
- 取一個空的 buffer
- 放置一個 item 進 buffer
- 如果沒有空的 buffer，則等待
Consumer
- 取一個 buffer 並拿出 item
- 將 buffer 放到 free pool
- 如果所有的 buffers 都空的，則等待

# Reader-Writers Problem

問題：如何設計一個同步機制，使得多個 process 可以同時讀取資料庫，但在寫入資料庫時，必須確保沒有其他 process 在讀取或寫入資料庫
A group of processes
- reader：只會讀取
- writer：可讀可寫
- writer 對 shared object 有獨佔權
種類
- First readers-writers problem：不會讓 reader 等待，可能導致 writer 飢餓
- Second readers-writers problem：不會讓 writer 等待，可能導致 reader 飢餓

# Dining-Philosopher Problem

介紹：五個哲學家圍著一張圓桌坐著，他們的生活方式是思考和吃飯。桌子中央有一碗米飯，旁邊有五根筷子。每個哲學家在吃飯時需要使用他們左邊和右邊的筷子
問題：是如何設計一個同步機制，使得哲學家們能夠在不發生死鎖或飢餓的情況下進行思考和吃飯
每個哲學家有 3 種狀態：
- thinking — 不想吃飯，思考中。
- hungry — 想吃飯。
- eating — 取得左右筷子，可吃飯。
Shared variables：
- data set
- chopstick[0…4] of semaphore

# Thread Programming

# Pthread Lock/Mutex Routines

#include “pthread.h”
pthread_mutex mutex;
pthread_mutex_init(&mutex, NULL);
pthread_mutex_lock(&mutex);// enter critical section
    Critical Section;
pthread_mutex_unlock(&mutex);// leave critical section
pthread_mutex_destory(&mutex);

use mutex

declare：pthread_mutex_t
initialize：pthread_mutex_init()
destroy：pthread_mutex_destory()
CS be protected：pthread_mutex_lock() and pthread_mutex_unlock()

# Condition Variables (CV)

CV 代表一些條件讓 thread 可以

等待直到條件發生
通知其他正在等待的 thread，條件已經發生了
operations on condition variables
- wait()
  Block 直到另一個 thread calls signal () or broadcast () on the CV
- signal()
  Wake up one thread waiting on the CV
- broadcast()
  Wake up all threads waiting on the CV
Pthread
Example：所有的 condition variable operation MUST be performed while a mutex is locked

# ThreadPool Implementation

很多個 thread 去 queue 中搶 task，queue 空了之後，等到有東西之後繼續搶。是 critical section 保護 dequeue 的動作

# Synchronized Tools in JAVA

Synchronized Methods (Monitor)
Synchronized Statement (Mutex Lock)

# Atomic Transactions

# System Model

Transaction
- 執行一個單一邏輯 function 的一個指令集合
Atomic Transaction
- 執行一個單一邏輯 function，要馬全部執行，要不就全部不執行（all or nothing）
- Atomic transaction 在 database system 是個重要的議題（讀寫）

# File I/O Example

Transaction 是一連串的讀寫 operations

透過 commit 以及 abort 來確認動作完成
- transaction 成功 : commit –> terminated
- transaction 失敗 : abort –> roll back
abort 的 transaction 必須回溯，取消所有做過的改變，這個性質的確保為 system 的責任

# Log-Based Recovery

紀錄所有 transaction 的步驟及做過的改變

Write-ahead logging : 基本上 log 紀錄需包含以下資訊
- Transaction name
- Data item name
- Old & new values
- Special events: (Ti starts), (Ti commits)
Log 用來重建被改動資料的原始狀態
- 利用 undo (Ti) 及 redo (Ti) 來復原資料

# Checkpoints

問題：Logging 沒有時間觀念，從系統打開到系統崩潰為止一直紀錄，因此需要 checkpoint 留存系統還原點
例如：強制關機時 word 沒有存檔，重開後系統會問你是否要還原至關機瞬間的狀態
當 failure 發生時，必須查看 log 來確認哪些 transactions 要重新執行
- 搜尋 process 很花時間
- 並非所有 transactions 都需要重新執行
checkpoints 減少上述 overhead 達到 stable storage
- 輸出所有 log 紀錄
- 輸出所有被更動的資料
- 輸出紀錄 checkpoint 的 log

# Ref Notes

Kipper’s Note
Chang-Chia-Chi’s Note
陳品媛的筆記
Mr. Opengate. OS - Ch6
Sheng-Hao Liao