iT邦幫忙

0

【小黑馬作業系統教室】(15) (Ch6)什麼是「同步化」議題的超完整解說

嗨嗨,大家好,我是心原一馬,
今天來給大家講講OS的另一個重要的章節,「同步化」。

上一篇: 【小黑馬作業系統教室】(14) (Ch5) 程式排程問題,以古代皇上見大臣做為比喻

其實小馬一直有個困惑,
若你有在追我的系列文的話,
到此篇,應該會知道其實程式本來就不會同時執行,
【小黑馬作業系統教室】(6) (Ch3)程式生命週期的程式生命週期圖來說,
一次只會有一支程式在running state執行,
其餘程式在ready state等候scheduler選擇它進入running state。
平時你在電腦上感覺程式可以同時執行(比如說一邊打你的word報告、一邊上網跟朋友聊天),
只不過是程式快速交替換到running state的結果。
所以說,既然程式本來就不會「同時」執行,
那麼「同步化」問題從何而來?

以提款卡同時存錢做為比喻

為了能夠深刻的理解程式間「同步化」的議題,
我們首先以生活化的例子想起,
假設A, B兩人有一張共用的提款卡,
帳戶餘額本來有10000元,
現在他們兩人「同時」對帳戶存款,
A想要在帳戶存2000元,
B想要在帳戶存3000元。

那麼,你會覺得不論A, B誰先存款,
帳戶餘額都要變為10000+2000+3000=15000元才合理,對吧?
等等,乍看簡單的存款,其實可以細分三個步驟:

  1. 讀取存在銀行資料庫的帳戶餘額資料到計算機
  2. 計算機裡完成帳戶餘額的計算
  3. 將更新後的帳戶餘額存回銀行資料庫中。

如果A,B是「同時」對帳戶存款的話,
那麼也就無法保證A先存款完才換B存款了,
而是這些步驟可能會交替進行。
假設步驟依序執行的是: A1->A2->B1->B2->A3->B3,
那麼就會發生這些事:
(A1) A讀取帳戶餘額資料到計算機中 (money=10000)
(A2) A做存入3000元的計算 (money=13000)
(B1) B讀取帳戶餘額資料到計算機中 (money=10000)
(B2) B做存入2000元的計算 (money=12000)
(A3) A將更新後的帳戶餘額存回銀行資料庫 (此時銀行資料庫顯示有13000元)
(B3) B將更新後的帳戶餘額存回銀行資料庫 (此時銀行資料庫顯示有12000元)

哇,經過這一連串的操作,
銀行資料庫的帳戶餘額竟然變成12000元(僅增加B存入的2000元),
而不是預期的15000元。

race conditon

在剛剛的例子中,若A3比B3更晚執行一些,
那麼銀行資料庫的帳戶餘額就會變成13000元。(僅增加A存入的3000元)

race conditon指的便是程式共用的變數,
它的值會取決於最後一個執行完畢的程式。

critical section

很顯然的,你會發現在存款的過程中,
如果能夠保證其中一人先存款完成,另一人再去存款的話,
那麼銀行資料庫的帳戶餘額就一定是正確的。
也就是上述步驟1,2,3應該一氣呵成的做完,不應該中途可以被打斷。

對程式來說,
不該中途被打斷的一段程式碼稱為「critical section」,
也就是若程式在執行「critical section」,
其它程式都不該進入它們的「critical section」。

「存款問題」對應到程式語言的同步化問題

假設我們有process A, B,它們共用變數money,
process A 做的事是 「money= money+3000」(A存入3000元)
process B 做的事是 「money= money+2000」(B存入2000元)
從程式碼來看你會以為只有一個步驟,
但簡單的「money= money+3000」這個指令翻譯成組合語言時卻有三個步驟。
(註: 若你沒學過計算機結構,這邊給個簡單的概念,
人類看的懂的語言是「程式碼」,
電腦看的懂的語言是「0101」,
組合語言」則是介於兩者間的橋樑)

(程式A做的指令)
move ax money (將記憶體中變數money的值,讀進register ax)
add ax 3000 (將ax的值加3000,存放在register ax裡) 
move money ax (將ax的值寫回記憶體中的變數money) 

(程式B做的指令)
move bx money (將記憶體中變數money的值,讀進register bx)
add bx 2000 (將bx的值加3000,存放在register bx裡) 
move money bx (將bx的值寫回記憶體中的變數money) 

(若你不知道register是什麼,可簡單想成是CPU對變數進行加減乘除後,暫存數字的地方)
也就是說,如果這些指令中途被其它程式打斷的話,
那麼便會發生上述描述的「race conditon」的問題了。
因此,解決的方法便是將修改程式間共同變數之間的指令,
視為「critical section」,
若程式在執行「critical section」,
其它程式都不該進入它們的「critical section」。

critical section requirement

一般來說,要解決「critical section」(以下簡稱CS)問題應滿足三個條件為理想:

  • mutual exclusion: 若程式在執行「critical section」,
    其它程式都不該進入它們的「critical section」。
    (並不是其它程式不能進入CPU哦,那是不可搶先的概念)
  • progress: 若沒有程式在執行CS,並且有程式想要執行CS,則必須有程式去執行CS
  • bounded waiting: 若一支程式想執行CS,等待的process數量必須是有限的,不能無限被插隊

生活比喻: 上廁所

若死背「critical section problem」應滿足的三個條件總是不好記,
小馬給個生活化的例子幫助大家記憶,
若將「critical section problem」比做「上廁所」,而廁所只有一間,則

  • mutual exclusion: 一次只能有一個人上廁所
  • progress: 若廁所沒人使用而有人想上廁所,則應該有人去上廁所,不可將廁所門反鎖
  • bounded waiting: 若一個人想排隊上廁所,總有一天需要輪到他上

先整理到這邊吧,
期望生活化的比喻解說能幫助大家學習。

參考資料

  1. 作業系統共筆- 同步 (Synchronization)

1 則留言

0
一級屠豬士
iT邦高手 1 級 ‧ 2019-12-30 12:18:32

別光在這邊貼讀書心得,也要回答問題,搭配起來,學習效果更佳.

https://ithelp.ithome.com.tw/questions/10196735

這裡有個案例.

感謝建議,有機會試試看~ 不過目前應該先以整理課程內容為重

我要留言

立即登入留言