當前位置：首頁 > 运维知识 > windows >内容正文

windows

操作系统原理第六章：进程同步

發布時間：2025/6/17 windows 35 豆豆

生活随笔收集整理的這篇文章主要介紹了操作系统原理第六章：进程同步小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1 進程同步背景

對于之前所提到的生產者消費者問題，采用共享內存解決生產者消費者問題時，N個緩沖區最多只能用N-1個，那么為什么有一個是用不了的呢？這是因為在判斷緩沖區空或滿時，用取余計算實現的，之所以犧牲一個位置是為了讓緩沖區空和緩沖區滿兩種狀態有兩種不同的表達式，若是換一種方法，設置一個計數變量 count ，count 的值表示當前緩沖區已經使用的容量，count=0表示緩沖區空，count=BUFFER_SIZE表示緩沖區滿（BUFFER_SIZE為緩沖區大小），這樣就解決了犧牲一個緩沖區容量的問題，如下圖：

下面是實現生產者添加商品的偽代碼，若不能理解該過程可以查閱數據結構中循環隊列的內容：

// 生產者調用的方法 public void enter(Object item) {// 緩沖區已經滿無法繼續添加while (count == BUFFER_SIZE) ; // 添加一個商品到緩沖區buffer[in] = item;in = (in + 1) % BUFFER_SIZE;count++; // 計數加一 }

下面是實現消費者消費商品的偽代碼：

// 消費者調動的方法 public Object remove() {Object item;// 當前緩沖區沒有商品，無法消費while (count == 0) ; // 從緩沖區移除一個商品item = buffer[out];out = (out + 1) % BUFFER_SIZE;count--; // 商品總數減一return item; }

上述思想看起來是沒有問題的，但是在實現過程中會出現問題，問題就出在 count 的自增和自減操作，由于count++和count--屬于高級指令，所以在機器執行過程中是分為三個步驟的，中間還有一步轉交給寄存器的操作，如下圖：

所以當一條指令分解成三個指令時，多個程序并發時就會出現問題，現假設count=5，若生產一個商品，再消費一個商品，最后count的值還是等于5，可在并發執行時就不一定會這樣，見下面的例子（注：以下例子只是情況的一種，在并發執行時會有非常多的不確定性），最終count的值等于4：

由以上的例子可知，對共享數據的并發訪問可能導致數據的不一致性，要保持數據的一致性，就需要一種保證并發進程的正確執行順序的機制，解決有界緩沖區問題的共享內存方法在類數據count 上存在競爭條件。

競爭條件：

若干個并發的進程(線程)都可以訪問和操縱同一個共享數據，從而執行結果就取決于并發進程對這個數據的訪問次序；
為了保證數據的一致性，需要有同步機制來保證多個進程對共享數據的互斥訪問。

進程的類型分為兩種，一種是獨立進程，它獨立執行，不受其他進程的影響；另一種就是協作進程，如剛剛所講的生產者和消費者問題，這兩個進程就屬于協作進程。進程間資源訪問沖突也分為兩種，一種是共享變量的修改沖突，如上面的count值，另一種則是操作順序沖突，比如某個作業A，需要作業B提供數據進行計算，若B提供數據，那么A會受到影響。

進程間的制約關系分為如下兩種：

間接制約：有些資源需要互斥使用，因此各進程進行競爭，獨占分配到的部分或全部共享資源，進程的這種關系為進程的互斥；
直接制約：進行協作，具體說，一個進程運行到某一點時要求另一伙伴進程為它提供消息，在未獲得消息之前，該進程處于等待狀態，獲得消息后被喚醒進入就緒態.進程的這種關系為進程的同步。

由于多個進程相互競爭資源，若各個進程互不相讓，此時就會發生死鎖想象。

2 臨界區

臨界資源即共享資源，對于臨界資源，多個進程必須互斥的對它進行訪問，在進程中某些代碼會訪問到臨界資源，這段代碼就叫做臨界區 (critical section)，即進程中訪問臨界資源的一段代碼，實現進程對臨界資源的互斥訪問就是讓各進程互斥的進入自己的臨界區，也就是說當某個進程在臨界區中執行時，其他進程都不能訪問自己臨界區，這樣就保證了某個時間內只有一個進程在臨界區內使用臨界資源，這樣就實現了臨界資源的互斥訪問。

臨界區的執行在時間上是互斥的，進程必須請求允許進入臨界區，也就是說當某個進程想進入臨界區時，比如進行某種操作來判斷當前臨界區是否有進程在執行，在具體實現時也是利用代碼來判斷的，整個進程的訪問過程分為以下三個區：

進入區 (entry section)：在進入臨界區之前，檢查可否進入臨界區的一段代碼。如果可以進入臨界區，通常設置相應“正在訪問臨界區”標志；
退出區 (exit section)：用于將"正在訪問臨界區"標志清除；
剩余區 (remainder section)：代碼中的其余部分。

臨界區互斥問題的解決方案要滿足如下三個要求：

互斥：假定進程 Pi 在其臨界區內執行，其他任何進程將被排斥在自己的臨界區之外；
有空讓進：臨界區雖沒有進程執行，但有些進程需要進入臨界區，不能無限期地延長下一個要進入臨界區進程的等待時間；
有限等待：在一個進程提出進入臨界區的請求和該請求得到答復的時間內，其他進程進入臨界區的次數必須是有限的。

2.1 進程的互斥

如何實現進程間的互斥？這里舉一個現實中游樂園的滑滑梯例子，滑滑梯一次只能進一個小朋友，當有很多小朋友想要玩的時候，那么一個解決辦法是讓他們輪流來玩，另一個解決辦法是提出想玩滑滑梯申請。在解決進程間的互斥問題時，也是借助了這兩個思想，這里介紹兩種算法。

算法1：設立一個兩進程公用的整型變量 turn ，用來描述允許進入臨界區的進程標識有兩個進程Pi，Pj ，如果 turn==i，那么進程 Pi允許在其臨界區執行，即采用輪流的方式，用turn表示當前運行哪個進程進入臨界區。

Pi進入臨界區的偽代碼如下：

while (turn != i); // 判斷是否輪到 Pi critical section; // 執行臨界區 turn = j; // 執行完臨界區就輪到下一個 Pjremainder section; // 執行剩余區

Pj進入臨界區的偽代碼如下：

while (turn != j); // 判斷是否輪到 Pjcritical section; // 執行臨界區 turn = i; // 執行完臨界區就輪到下一個 Piremainder section; // 執行剩余區

對于之前提到的臨界區互斥問題的三個要求，該算法顯然是滿足第一個互斥要求的，實際上該算法是強制輪流進入臨界區，沒有考慮進程的實際需要，若 Pi 執行完臨界區，turn也轉交給了Pj，但此時Pj不需要使用臨界區，這時臨界區處于空閑狀態，但turn這時不屬于Pi，所以Pi依然無法執行臨界區，容易造成資源利用不充分，所以不滿足第二個要求有空讓進，也不滿足第三個要求有限等待。

算法2：由于算法1 只記住了哪個進程能進入臨界區，沒有保存進程的狀態，設立一個標志數組 flag[]，用來描述進程是否準備進入臨界區，初值均為 FALSE，先申請后檢查。可防止兩個進程同時進入臨界區。

Pi進入臨界區的偽代碼如下：

flag[i] = TURE; // Pi 申請執行臨界區 while (flag[j]); // 判斷 Pj 是不是在執行臨界區或它也想執行臨界區critical section; flag[i] = FALSE; // Pi 執行完臨界區，撤銷之前的申請remainder section;

Pj進入臨界區的偽代碼如下：

flag[j] = TURE; // Pj 申請執行臨界區 while (flag[i]); // 判斷 Pi 是不是在執行臨界區或它也想執行臨界區critical section; flag[j] = FALSE; // Pj 執行完臨界區，撤銷之前的申請remainder section;

該算法顯然滿足互斥要求，因為每次執行臨界區前都會判斷對方是否在執行臨界區或是否也想進入臨界區；設想某個時刻 Pi 和 Pj 都申請執行臨界區，這樣會導致雙方誰也不能執行臨界區，所以不滿足有空讓進的要求，算法2對比算法1的優點是不用交替進入，可連續使用，不用等待對方，缺點就是兩進程可能都進入不了臨界區。

算法3：在算法2的基礎上進一步改進，同樣是要先申請執行臨界區，但要把turn改為對方，然后再進行檢查若當前對方在執行臨界區或對方想要執行臨界區且turn也是對方，那么就要等待對方執行完。

Pi進入臨界區的偽代碼如下：

flag[i] = TURE; // Pi 申請執行臨界區 turn = j; // 讓 Pj 下次執行 while (flag[j] && turn = j); // 判斷 Pj 是不是在執行臨界區或它也想執行臨界區且當且turn為它critical section; flag[i] = FALSE; // Pi 執行完臨界區，撤銷之前的申請remainder section;

Pj進入臨界區的偽代碼如下：

flag[j] = TURE; // Pj 申請執行臨界區 turn = i; // 讓 Pi 下次執行 while (flag[i] && turn = i); // 判斷 Pi 是不是在執行臨界區或它也想執行臨界區且當且turn為它critical section; flag[j] = FALSE; // Pj 執行完臨界區，撤銷之前的申請remainder section;

算法3解決了算法1和算法2的缺點，同時算法3具有先到先入，后到等待的特點。

3 信號量

可以用臨界區解決互斥問題，它們是平等進程間的一種協商機制，之前所提到的輪流和申請都是基于兩個進程的臨界區模型所提出來的，當進程數目過多的時候，顯然要引入新的機制來解決互斥問題，操作系統可從進程管理者的角度來處理互斥的問題，信號量 (Semaphore) 就是操作系統提供的管理公有資源的有效手段。

信號量是在1965年，由荷蘭學者Dijkstra提出（所以P、V分別是荷蘭語的test (proberen)、increment (verhogen)），是一種卓有成效的進程同步機制。用于保證多個進程在執行次序上的協調關系的相應機制稱為進程同步機制。

信號量是一個整型變量，代表信號量代表可用資源實體的數量。除了初始化之外，僅能通過兩個不可分割的原子操作訪問，即P(S)和V(S)，簡稱為P，V操作。

原子操作：指的是操作系統內最小的操作單位，它的執行時不可中斷的。

由于S代表當前可用資源的數量，當 S <= 0時，會一直等待資源，所以存在忙等現象，又稱自旋鎖，此時CPU的利用率是不高的，偽代碼如下：

P(S); // 申請資源while (S <= 0); // 當前沒有可用資源就要一直等待 S--; // 若有資源，就要總資源數減一 V(S); // 使用完資源要釋放資源 S++; // 釋放資源

為了解決忙等現象，引入了一種不需要忙等的方案，它將 S-- 操作提前了，先減再判斷 S 的值，若判斷的 S < 0，就讓進程進入阻塞狀態（通常是設置一個阻塞進程隊列），在釋放資源時，若 S >= 0，則要喚醒阻塞的進程，偽代碼如下：

P(S); // 申請資源S--; // 總資源數減一if (S < 0) {block; // 若當前無可用資源，則將該進程阻塞} V(S); // 使用完資源要釋放資源S++; // 釋放資源if (S >= 0) {wakeup; // 若當前有可用資源，則將之前阻塞的進程喚醒}

S是與臨界區內所使用的公用資源有關的信號量：

P(S)：表示申請一個資源；
V(S)：表示釋放一個資源。

一般來說初始化指定一個非負整數值，表示空閑資源總數，在信號量經典定義下，信號量S的值不可能為負，后面的定義下可能為負，因為后面的定義是先做 S--：

S≥0 表示可供并發進程使用的資源數；
S<0 其絕對值就是正在等待進入臨界區的進程數。

在用信號量解決問題的時候，首先要分清楚這個問題是個同步問題，還是一個互斥問題，若是一個互斥問題，那么就要找到互斥的臨界資源是什么，并把臨界資源抽象成信號量，然后給信號量賦初值并給出正確的P，V操作。

4 哲學家問題

問題描述：（由Dijkstra首先提出并解決）5個哲學家圍繞一張圓桌而坐，桌子上放著5支筷子（注意是5支而不是5雙），每兩個哲學家之間放一支；哲學家的動作包括思考和進餐，進餐時需要同時拿起他左邊和右邊的兩支筷子，思考時則同時將兩支筷子放回原處。如何保證哲學家們的動作有序進行？如：不出現相鄰者同時進餐，問題模型如下圖：

先考慮該問題是一個同步問題還是一個互斥問題，顯然它是一個互斥問題，那么它的臨界資源就是筷子，把臨界資源抽象成信號量為 Semaphore chopStick[] = new Semaphore[5];，即一個容量為5的數組。

哲學家思考和進餐的過程如下面的偽代碼：

Repeat思考；取chopStick[i]; // 一根筷子取chopStick[(i+1) mod 5]； // 取旁邊一根筷子進餐；放chopStick[i]; // 放回筷子放chopStick[(i+1) mod 5]； // 放回筷子 Until false;

用信號量表示的偽代碼如下：

while (true) {// 取左邊的筷子chopStick[i].P();// 取右邊的筷子chopStick[(i + 1) % 5].P();// 進餐// 放回左邊的筷子chopStick[i].V();// 放回右邊的筷子chopStick[(i + 1) % 5].V();// 思考 }

用信號量實現保證了互斥，但是這種實現下可能會出現死鎖，當五個哲學家每人拿起了他左邊的筷子，則桌子上筷子全部被拿完了，而沒有一個哲學家湊齊了兩支筷子，解決這個死鎖的方法有如下幾種：

最多允許四個哲學家同時就坐，此時至少有一個哲學家能夠同時拿起兩支筷子；
同時拿起兩根筷子，若某個哲學家要進餐時，要求他同時拿起一雙，若不能同時拿起兩支，就不能進餐；
非對稱解決，處于奇數位置的哲學家限制他只能拿左邊的筷子，處于偶數位置的哲學家限制他只能拿右邊的筷子，這樣無論如何都會有一個哲學家能同時拿起兩支筷子。

5 生產者消費者問題

問題描述：若干進程通過有限的共享緩沖區交換數據。其中，"生產者"進程不斷寫入，而"消費者"進程不斷讀出；共享緩沖區共有N個；任何時刻只能有一個進程可對共享緩沖區進行操作，問題模型如下圖：

由于進程之間是共享了臨界資源，所以他們之間肯定是互斥關系，所以要設置臨界區保證進程間互斥訪問，由于生產者生產商品給消費者使用，他們之間也存在著同步關系。

緩沖區的大小是固定為N，當緩沖區滿的時候，生產者是不能再生產商品的，當緩沖區為空的時候消費者是不能消費商品的，我們可以抽象以下變量：

full：表示緩沖區滿的數量，也就是可用商品的個數，它的初值為 0；
empty：表示緩沖區空的數量，也就是還可以生產多少商品的個數，它的初值為 N；
mutex：用于訪問緩沖區的互斥，初值是 1。

每生產一個商品就要進行 full++ 操作，每消費一個商品就要進行 empty++ 操作，full 和 empty 滿足關系式 full + empty = N。對于生產者來說它一開始要生產商品放到緩沖區里面，而緩沖區是互斥的，生產的時候還要看緩沖區里面是否還有空位，有空位才能夠生產，所以對應的有兩對P，V操作，一對是關于互斥信號量 mutex的操作，一對是關于資源信號量 empty 的操作。在實現的時候要注意每個進程中各個P操作的次序是非常重要的。應先檢查資源數目，再檢查是否互斥，否則可能出現死鎖。

對于生產者操作的偽代碼如下；

P(empty); // 申請空位 empty-- P(mutex); // 申請占用緩沖區// 生產一個商品放入緩沖區 V(mutex); // 釋放占用的緩沖區 V(full); // 添加商品 full++

對于消費者操作的偽代碼如下：

P(full); // 申請消費一個商品 full-- P(mutex); // 申請占用緩沖區// 消費緩沖區中的一個商品 V(mutex); // 釋放占用的緩沖區 V(empty); // 增加一個空位 empty++

用信號量表示生產者的偽代碼如下：

public void enter(Object item) {empty.P(); // 申請緩沖區中的一個空位mutex.P(); // 申請占用緩沖區// 添加一個商品到緩沖區buffer[in] = item;in = (in + 1) % BUFFER_SIZE;mutex.V(); // 釋放占用緩沖區full.V(); // 增加一個商品 }

用信號量表示消費者的偽代碼如下：

public Object remove() {full.P(); // 申請消費一個商品mutex.P(); // 申請占用緩沖區// 從緩沖區消費一個商品Object item = buffer[out];out = (out + 1) % BUFFER_SIZE;mutex.V(); // 釋放占用的緩沖區empty.V(); // 增加一個空位return item; }

6 讀寫問題

問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個。

讀寫問題存在以下三種關系：

讀者和寫者：互斥關系，寫者在寫的時候讀者不可以讀，讀者在讀的時候寫者不可以寫；
寫者和寫者：互斥關系，同一時刻只能有一個寫者進行寫操作；
讀者和讀者：沒有限制，多個讀者可以同時讀。

那么可以從兩個方面來考慮這個問題，即有讀者來會怎么樣和有寫者來會怎么樣，當有讀者來的時候：

如果當前系統中沒有讀者也沒用寫者，那么新來的讀者可以直接讀，一旦這個讀者開始讀的時候，后面來的讀者都可以讀，但是后來的寫者是不可以寫的；
當一個讀者到來的時候，發現有一個寫者正在等待，因為之前已經到來了讀者并且現在在讀，那么這個時候來的讀者便可以直接讀；
當一個讀者到來的時候，發現有一個寫者正在寫，那么該讀者就不能讀，并且后面來的讀者都要等待，除非這個寫者寫完。

當寫者到來時：

若當前沒有讀者，寫者可以直接寫；
若當前有讀者，寫者便要等待讀者讀完；
若當前正有寫者在寫，那么該寫者要等待。

總結來說寫者是更任何人互斥的，讀讀是允許的，并且可以發現只有第一個和最后一個讀者是會影響寫者的，那么如何知道哪個讀者是第一個來的，哪個讀者是最后一個走的呢？我們的解決方法是設置一個變量來統計讀者的個數，初值可以設為 0，來一個讀者就加一，走一個讀者就減一，這里引入一個共享變量必然會成為臨界資源，對于這個臨界資源時肯定要對它進行保護的，采用的采用信號量機制如下：

信號量Wmutex表示"允許寫"，初值是1；
公共變量Rcount表示“正在讀”的進程數，初值是0；
信號量Rmutex為了保護臨界資源Rcount，它表示對Rcount的互斥操作，初值是1。

寫者的操作偽代碼如下：

P(Wmutex); // 申請寫信號量write; // 寫 V(Wmutex); // 釋放寫信號量

讀者的操作相對復雜，其偽代碼如下：

P(Rmutex); // 申請對 Rcount 的使用if (Rcount == 0) {// 當前讀者是第一個讀者// 若允許他讀，則要不允許后來的讀者寫// 要將寫操作的信號量做 P 操作P(Wmutex);}++Rcount; // 讀者數加一，上下對 Rmutex 的P，V操作實際上是為了保護 Rcount V(Rmutex);…read; // 讀… P(Rmutex);--Rcount; // 讀完之后讀者數減一，上下對 Rmutex 的P，V操作實際上是為了保護 Rcountif (Rcount == 0) {// 當前讀者是最后一個離開的讀者// 此時應該釋放寫操作，對寫操作做 V 操作V(Wmutex);} V(Rmutex);

7 P，V操作總結

信號量S為一個整型的變量，它描述的是當前可用資源的數目，當 S > 0 時表示有S個資源可用，當 S = 0 時表示無資源可用，當 S < 0 則 $∣ S ∣$ 表示 S 等待隊列中的進程個數，P(S) 表示申請一個資源，V(S) 表示釋放一個資源，信號量的初值應該大于等于0。

P，V操作必須成對出現，有一個P操作就一定有一個V操作，且有以下規律：

當為互斥操作時：它們處于同一進程；
當為同步操作時：它們不在同一進程中出現。

對于前后相連的兩個P(S1)和P(S2) ，順序是至關重要的，同步P操作應該放在互斥P操作前。

總結

以上是生活随笔為你收集整理的操作系统原理第六章：进程同步的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

windows

操作系统原理第六章：进程同步

目錄

1 進程同步背景

2 臨界區

2.1 進程的互斥

3 信號量

4 哲學家問題

5 生產者消費者問題

6 讀寫問題

7 P，V操作總結

總結