Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 6: Synchronization Tools (The Critical-Section Problem (process內容…
Chapter 6:
Synchronization Tools
背景
有多個procee或thread同時存取共同資料 => 資料不一致 (因為程式會reordering)
Race Condition
:star::star::star: : 若未對共享變數的存取提供同步機制，會造成執行結果會因process之間的交錯執行順序不同而有不同結果，稱之
Process synchronization
:star::star::star: : 一次只有一個process可以存取共享data
The Critical-Section Problem
critical section
(臨界區間):star: : 有動到共享資料的地方
設計方法 : 一個critical section一次只允許一個process進入
process內容
entry section
:star:
exit section,
:star:
critical dection
remainder section
:star:
c.s須滿足的三大條件
Mutual Exclusion
:star: : 只要有一個prcoess在c.s裡面，另一就不能進去
Progress
:star: : 當有prcoess離開了c.s，一定要再讓別人進去
Bounded Waiting
:star: : 有人想等，遲早要讓他進去
OS handling
Preemptive
(現今)
Non-preemptive
(早期) : 一次只能有一人進kernel mode，可解決race condition但效能不好
Peterson’s Solution
說明
經典軟體解法
但現今CPU會將程式碼reordering，因此不保證結果正確
:fire::fire::fire:p.9程式碼
硬體解決同步問題
許多系統的硬體支援c.s之實作
disable interrupts
定義 : 在對共享資料進行存取前，把中斷關掉，等到存取完成後才打開，此段時間內CPU不會被插隊
優點 : 簡單、易實作、適用於Uniprocessors(e.g. CLI in Intel IA-32)
缺點 : 不適用於multiprocessor，會大幅降低performance
三種硬體支援的同步問題解法
Memory barriers (memory fence)
:star::star::star:
定義 : 由系統所提供的機器指令。讓你改了一個記憶體，就馬上廣播給大家知道
Memory models
Strongly ordered
: 改一個記憶體，
馬上
通知所有相關的人
Weakly ordered
: 修改某塊記憶體，不會馬上通知其他人
Hardware instructions
TestAndSet
定義 : 修改共享資料時，將lock設為true。則其他process必須等到它做完把lock放掉後，才可以進行資料操作。
CompareAndSwap
說明 : 把lock改成int expected，比TestAndSet更有彈性
Atomic variables
說明
一種data type，compiler看到atomic，就自動幫你做保護
但沒有完全解決race condition
atomic可確保變數執正確 (atomic變數在update過程中，是不會被中斷的)
Mutex Locks
mutexlock
(最簡單)
作法 : 用acquire()、 release()來控制lock，以保護c.s
Busy waiting (soinlock)
:star::star::star:
定義 : 透過使用loop相關敘述，達到讓process暫時等待之效果
Semaphores
定義
架構在integer type
僅能夠過兩個atomic operation存取
wait()
signal()
用途
Counting semaphore
:star: : value的值是一個範圍
Binary semaphore
:star: : value僅能為0或1 (等同
mutex
:star:)
實作with no busy waiting
2個operations
block
:star: : 把process丟進waiting queue
wakeup
:star: : 把process從waiting queue抓進ready queue
Condition Variables
定義
condition型別是用於semaphore中，提供給programmer解同步問題用的
operation
wait() : process暫停直到signal()
signal : 恢復正在wait的process
Monitors
定義 : 一種高階的abstract data type。程式語言自動幫你加lock、unlock
Liveness
Evaluation