iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
自我挑戰組

杰哥的考研紀錄系列 第 26

Day-26 Process Synchronization

Process Synchronization

tags: IT鐵人

由於電腦同時會執行許多程式,不同程式可能會共用其中幾個變數。
舉例來說,一個停車場要標示裡面還剩多少位置時,如果二樓有一台車走了,一樓也有一台車走了,理論上要多出兩個空位,但如果同步的問題沒有處理好,可能導致二樓跟一樓取走原本剩餘的車位數量,減去一之後丟回去告訴中控,這時候中控就會只有收到減去一的結果,導致外面公告的數字跟停車場內的實際數字不一樣。

Process Communication

不同的Process溝通的方式主要有兩種,分別為Shared Memory及Message Passing,以下分別介紹。

Shared Memory

Process之間向OS申請一個shared memory space,可以在這之間宣告一些shared variables,Process可藉由write, read這些shared variables,達到溝通的目的。

有點像是在冰箱上貼便利貼,規定這個冰箱給某兩個process溝通,像是有些家庭會在冰箱上貼一些"晚餐在裡面,自己微波"或是通知隔天的行程之類的。

這種做法OS不用特別支援,只要提供shared memory就好,所以主要責任在programming身上,比如說不同的process(家人)不可以同時搶memory(便條紙),發生的話稱為Race condition,需要額外寫避免發生的程式碼。

適用於大量資訊溝通,而且這種溝通方式速度快(不用kernel介入),不適合分散式系統。

Message Passing

兩個Process要溝通時要建立Communication link,並且此link要能互相傳輸,溝通完即釋放。

就像是講電話,撥通電話號碼後交給電信業者處理,溝通完掛電話連接就斷了。

這種方式就需要OS提供支援,如果兩個Process同時請求溝通,OS要能處理。像是Line通話會在兩人同時撥電話的時候接不到對方來電,OS就要想辦法避免這種狀況發生。

因為需要kernel介入,所以溝通速度慢並且適用於少量的Message,適合用在分散式系統。

Race Condition

這邊簡單介紹Race Condition以及解決方法,前面用停車場的例子簡單介紹了一下,我們底下用程式的例子來解釋:

假設有一個變數"x"初始值為5,會被兩個process使用到,P1會執行x=x+1,P2會執行x=x-1,這時候根據不同的執行順序會有4,5,6三種結果,以下分別舉一個例子說明:

x=4 x=5 x=6
P1,P2同時取得x的初始值x=5 P1先取得x的數值且計算並存入x=6 P1,P2同時取得x的初始值x=5
P1,P2對取得的值進行計算x1=6, x2=4 P2取得x的數值且計算並存入x=5 P1,P2對取得的值進行計算x1=6, x2=4
P2在P1之後存回x, x=5 => 6 => 4 P1在P2之後存回x, x=5 => 6 => 4

由於我們不知道Process之間如何交錯,所以要避免這種情況發生。

Race Condition 解決方法

解決方法有兩種主要做法,第一種是Disable Interrupt,第二種是Critical Section Design。

Disable Interrupt

這個做法是在處理共享變數時Disable Interrupt,完成存取後才Enable Interrupt,如此一來在這期間CPU不會被Preempted交給其他Process。

這個做法非常簡單暴力,就像是圍起封鎖線不准進入一樣,在單核心的情況下適合使用這種作法。如果是多核心的情況,禁止某個CPU Preempted以後,可能會被其他的CPU Preempted,如果禁止所有CPU Preempted,則Performance會變得非常差。

並且如果讓User任意Disable Interrupt,萬一User遲遲沒有Enable Interrupt,則CPU永遠不會交給其他Process使用。

Critical Section Design

Critical Section的作用代表這塊很重要,一次只能有一個Process待在Critical Section中,Critical Section Design的想法是由Programmer在Critical Section的前後寫控制碼,分為Entry Section以及Exit Section。

Critical Section Design必須滿足三點,分別為Mutual Exclusion、Progress、Bounded Waiting,以下詳細介紹這三個要素。

要素 內容
Mutual Exclusion 任何時間點最多只允許一個Process在自己的C.S.活動。
Progress 不想進入C.S.的Process不可阻礙其他想進入C.S.的Process進入C.S.。多個Process想進入C.S.時必須在有限時間內決定誰可進入,不可讓所有Process卡住。
Bounded Waiting No Starvation。Process在提出進入C.S.的申請後,最多等n-1次(n個Process)即可進入C.S.。

至於實際的設計方式,經過多次的改良之後解釋起來會有點小複雜,有興趣的同學就去查查吧~
底下提供其中一個範例,還有其他更難理解的Algorithm。

這篇就到這邊了!Race Condition是在多核心的時候會發生的問題,科技的進展同時會產生更多問題需要解決,那我們下篇見囉~

上一篇 下一篇
Deadlock Memory Management

上一篇
Day-25 Deadlock
下一篇
Day-27 Memory Management
系列文
杰哥的考研紀錄30

尚未有邦友留言

立即登入留言