進程與進程管理 | 進程同步機制

05-08

進程同步概念

概念：並發進程在一些關鍵點上可能需要互相等待或互通消息，這種相互制約的等待或互通消息稱為進程同步。
同步機制應遵循的準則

空閑讓進：其他進程均不處於臨界區；
忙則等待：已有進程處於其臨界區；
有限等待：等待進入臨界區的進程不能"死等"；
讓權等待：不能進入臨界區的進程，應釋放CPU（如轉換到等待狀態）

使用軟體演算法實現互斥

演算法1：兩個進程P0, P1共享某臨界資源

演算法一：設立一個公用整型變數 turn，描述允許進入臨界區的進程標識，假設初始化turn=0，表示首先輪到P0訪問臨界資源

該演算法，初始化是設置的等待 P0 對進程進行訪問，但是如果 P1 先申請訪問就不能執行，違背了空閑讓進的準則。
當 turn 值為1時，如果 P0 進程想要訪問臨界資源，會在 while 語句中執行空循環等待，知道 turn 變為 0。所以當 P0 不能拿到訪問權時，並沒有放棄等待，而是一直占著 CPU 在做空循環等待，違背了讓權等待的準則。

演算法二：設立一個標誌數組flag[2]：描述進程是否已在臨界區，初值均為0(FALSE)，表示進程都不在臨界區。

在這個演算法中，當 flag[1] = 0 的時候，我們可以進入 P0 進程，當 P0 進程剛執行完第一條 while 語句的時候，它的時間片到了，中斷 P0 進程的執行，進而執行 P1 的時候，又會因為 flag[0] = 0，認為臨界資源可以訪問，這樣 P0 和 P1 都會同時訪問臨界資源。違背了忙則等待的原則
當 flag[1] 為 1 的時候，P0 進程的 while 語句會執行空循環等待，所以也違背了讓權等待的原則。

使用鎖機制實現互斥

鎖的定義：用變數w代表某種資源的狀態，w稱為「鎖」。
上鎖操作和開鎖操作

上鎖操作（臨界資源的申請操作）：

檢測w的值 (是0還是1)；
如果w的值為1，繼續檢測；
如果w的值為0，將鎖位置1 (表示佔用資源)，進入臨界區執行

開鎖操作（臨界資源的釋放操作）：

臨界資源使用完畢，將鎖位置0

上鎖原語和開鎖原語

上鎖原語

lock（）{ test: if (w為1) goto test； ∕* 測試鎖位的值*∕ else w=1；} ∕*上鎖*∕

開鎖原語

unlock（）{ w=0；} ∕*開鎖*∕

操作方法

加鎖操作 -》執行臨界區程序 -》開鎖操作

信號量機制

信號量數據結構的定義

typedef struct{ int value; /*信號量的值*/ PCB * L; /*進程等待隊列隊首指針*/} semaphore ;

value：初始化為一個非負整數值，表示空閑資源總數－－若為非負值表示當前的空閑資源數，若為負值其絕對值表示當前等待臨界資源的進程個數。
L：初值為空

信號量的P、V操作： semaphore *S;

P 操作（臨界資源申請操作）

P(S){ S->value--; if(S->value<0) sleep(S->L); // 由於進程在不能申請到臨界資源時是主動釋放CPU並且阻塞到L鏈表上 // 所以信號量實現了讓權等待的機制}

V 操作（臨界資源釋放操作）

V(S){ S->value++; // 歸還一個臨界資源給系統 if(S->value<=0) wakeup(S->L); // 喚醒進程}

利用信號量機制實現進程互斥與同步

實現互斥

為臨界資源設置一個互斥信號量 mutex ，其初值為 1：

semaphore mutex=1

在每個進程中將臨界區代碼置於P(mutex)和V(mutex)原語之間：

演算法描述如下：

給出一個例子：兩個進程共享一台印表機

在執行 Pa 進程的過程中，P 操作先對 mutex 減一，得到 0。不是負數，可以直接執行。 Pb 進程如果在這個時候進行申請，此時執行 P 操作，mutex 得到 -1，會阻塞 Pb 進程。
當執行 Pa 進程的 V 操作時， mutex 值為 -1，加 1 得到 0。小於等於 0，喚醒等待進程 Pb。
當 Pb 進程執行到 V 操作時， mutex 加 1 得到 1，此時印表機空閑。

實現同步：進程間合作的前驅後繼關係

為一個同步關係設置一個同步信號量S，其初值為0：

semaphore S=0 // 表示令牌

前驅進程完成操作後執行V(S)：表示釋放令牌；後繼進程開始操作前執行P(S)：表示申請令牌
演算法描述：Pa -> Pb

舉個例子： I -> C -> P

再舉一個例子：對給出的前驅圖編寫同步信號量程序：

a,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0cobegin s1: { s1; v(a); v(b);} s2: { p(a); s2; v(c); v(d);} s3: { p(b); s3; v(e); } s4: { p(c); s4; v(f); } s5: { p(d); s5; v(g); } s6: { p(e); p(f); p(g); s6; }coend

最後，再給出一個司機和售票員的例子，司機和售票員的工作進程如下：

我們，首先需要尋找這兩個進程之間的同步關係，得到同步關係如下：

售票員關閉車門→ 司機啟動車輛
司機到站停車→ 售票員打開車門

對於這連個同步關係，我們設置相應的同步信號量如下：

semaphore drive_sem={0,NULL};
semaphore conductor_sem={0,NULL};

最後，我們根據這些信號量的設置，寫出相應的演算法如下：

使用信號量解決進程同步問題的步驟

確定進程：

包括進程的數量、進程的工作內容。

確定進程同步互斥關係：

根據進程間是競爭臨界資源還是相互合作處理上的前後關系，來確定進程間是互斥還是同步。

確定信號量：

根據進程間的同步互斥關係確定信號量個數、含義、初始值，各進程需要對信號量進行的PV操作。

用類程序語言描述演算法。