[Operating System Cheat sheat] — Mutex and Semaphore

Leon .

4 min readApr 4, 2021

Mutex lock

(其實為Binary Semaphore)

是OS提供的software tool(sys call)之一，給Application Programmer來解決同步問題。

Mutex Lock提供一個共享變數型態

eg：boolean available=false，並在此變數available上提供2個
"atomically operation"

acquire()
release()

Semaphore

令S為 Semaphore Type 變數，架構在 Integer Type上

S提供 2 個”Atomic” Operations :

wait(S) : // P()
while(s≤0) do no-op;
s=s-1;
signal(S) : // V()
s=s+1;

Note: 因為Atomic，所以 s 不會有 Race Condition
p.s. if wait(s)、signal(s)不為Atomic ，會違反 Mutex exclusion :
假設value=1，有兩個wait(s)同時執行，但不為Atomic，則兩者都會通過while，使得 s同時有兩個process對其modify違反互斥。

Semaphore Crical Section design

Critical Section Design
Easy Problem solve by Semaphore
Classic problem solve —
(a.) Producer-Consumer Problem
(b.) Reader-Writer Problem
(c.) The Sleeping Barbers Problem
(d.) The Dining Philosophers Problem

Critical Section Design

Easy Problem

這邊舉幾個Semaphore能做到的應用問題 :

但是Semaphore的「誤用」也會造成 Mutex Exclusion以及Deadlock的產生 :

Producer-Consumer Problem

Producer: 此Process專門產生訊息，供別人使用。
Consumer:此 Process專門消耗別人產生的成果。

分為2種 :

Bounded Buffer
<同步條件>
(1)當Buffer滿，則Producer被迫等待。
(2)當Buffer空，則Consumer被迫等待。
Unbounded Buffer
(1) Producer無需等待
(2)當 Buffer空，則Consumer被迫等待

No using semaphore to Producer-Consumer Problem

Algorthm — 1

以下演算法只能利用到 n-1格的Buffer。

in , out =0
Buffer[1…n]: 存data

Algorthm — 2

以下演算法能利用到n格的Buffer。

in , out =0
Buffer[1…n]: 存data
Count = 0 …新增的欄位

Using semaphore to solve Producer-Consumer Problem

empty: (semaphore type) = n
代表 Buffer內空格數。若空格為0，表示buffer滿了
full: (semaphore type) =0
代表 Buffer中填入item之格數。若為0，表Buffer 空
mutex: (semaphore type)=1
對 Buffer, in, out, Count 作互斥控制防止 Race Condition

Tips:

滿足同步條件之方法變數
(empty=卡生產者、full=卡消費者)
互斥控制防止 Race Condition 之號誌變數
(mutex=Count之互斥控制)

Note . 先測試同步(empty or full)，再測互斥(mutex)。

Reader-Writer Problem

Allow multiple readers to read at the same time. Only one single writer can access the shared data at the same time.

Readers — only read the data set; they do not perform any updates
Writers — can both read and write.

描述 :

Reader、Writer必須要互斥。
Writer、Writer必須要互斥。

除此之外，Read/Writer problem可以再細分為 :

First Read/Writer problem
— 對Reader 有利、對Writer不利；Writer有可能會Starvation。
Second Read/Writer problem
— 對Writer有利、對Reader不利；Reader有可能會Starvation。

First Read/Writer problem

對Reader 有利、對Writer不利；Writer有可能會Starvation。

wrt : (semaphore type) =1
提供R/W、W/W互斥控制，(兼作對Writer不利之控制)
readcnt : int = 0
統計目前Reader個數。
Reader到達則readcnt+1 ; reader離開，則readcunt-1。
mutex : (semaphore type) = 1
對 readcnt 作互斥控制，防止Race Condition。

Example

若目前W1已在寫入，則
(1.) R1到達、R1會被卡在__?、此時readcnt=__?
(2.) R2到達、R2會被卡在__?、此時readcnt=__?
(3.) R3到達、R3會被卡在__?、此時readcnt=__?

ANS
1. wrt 、1
2. mutex、1
3. mutex、1

Second Read/Writer problem

對Writer有利、對Reader不利；Reader有可能會Starvation。

readcnt: int=0;
統計 Reader 個數。
wrtcnt: int=0
統計 Writer 個數。
x: semaphore=1
作 readcnt的互斥控制，防止Race Condition。
y作 wrtcnt 的互斥控制，防止Race Condition
z作為對Reader之入口控制(卡多一些關卡,讓 5. Z:semaphore=1;
Reader slower)
rsem: semaphore=1;//作為對 Reader不利之控制
wsem: semaphore=1;//提供 R/W、W/W互斥控制

Sleeping barber problem

Semaphore types

依照Semoaphore值域作為區分
binary semaphore v.s counting semaphore
是否將用Busy-Waiting(spinlock)來定義 semaphore
Spinlock semaphore v.s Non-Busy-Waiting semaphore