一、進程同步的概念

在多道程序環(huán)境下，進程是并發(fā)執(zhí)行的，不同進程之間存在著不同的相互制約的關(guān)系。為了協(xié)調(diào)進程之間的相互制約的關(guān)系，引入進程同步的概念。

1.臨界資源

雖然多個進程可以共享系統(tǒng)中的各種資源，但其中許多資源依次只能為一個進程所使用，這類資源稱為臨界資源。許多物理設(shè)備都屬于臨界資源，例如打印機、磁帶機。此外，全局變量，靜態(tài)變量、數(shù)據(jù)等都可以被若干進程共享，也屬于臨界資源。

對臨界資源的訪問，必須互斥地進行。在每個進程中，訪問臨界資源的那段代碼稱為臨界區(qū)。為了保證臨界資源的正確使用，可以把臨界資源的訪問分成四個部分。

do{
    entry section;//進入?yún)^(qū)
    critical section;//臨界區(qū)
    exit section;//退出區(qū)
    remainder section;//剩余區(qū)
} while (true);

• 進入?yún)^(qū)
  為了進入臨界區(qū)使用臨界資源，在進入?yún)^(qū)要檢查可否進入臨界區(qū)，如果可以進入，則應(yīng)該設(shè)置在訪問臨界區(qū)的標志，以阻止其他進程同時進入臨界區(qū)。
• 臨界區(qū)
  進程中訪問臨界資源的代碼段，又稱為臨界段
• 退出區(qū)
  將正在訪問臨界區(qū)的標志清除
• 剩余區(qū)
  進程代碼中其余部分

2.同步

同步亦稱為直接制約關(guān)系，它是指為完成某種任務(wù)而建立的兩個或多個進程，這些進程因為需要在某些位置上協(xié)調(diào)他們的工作次序而等待、傳遞信息所產(chǎn)生的制約關(guān)系。進程間的直接制約關(guān)系源于它們之間相互的合作。

例如，輸入進程A通過單緩沖向進程B提供數(shù)據(jù)。當該緩沖區(qū)空時，進程B不能獲得所需數(shù)據(jù)而阻塞，一旦進程A將數(shù)據(jù)送入緩沖區(qū)，進程B被喚醒。反之，當緩沖區(qū)滿時，進程A被阻塞，僅當進程B取走緩沖數(shù)據(jù)時，才喚醒進程A。

可以用下圖簡單表示：

3.互斥

互斥亦稱為間接制約關(guān)系。當一個進程進入臨界區(qū)使用臨界資源時，另一個進程必須等待，當占用臨界資源的進程退出臨界區(qū)后，另一個進程才允許區(qū)訪問此臨界資源。

例如，在僅有一臺打印機的系統(tǒng)中，有兩個進程A和進程B，如果進程A需要打印時, 系統(tǒng)已將打印機分配給進程B,則進程A必須阻塞。一旦進程B將打印機釋放，系統(tǒng)便將進程A喚醒，并將其由阻塞狀態(tài)變?yōu)榫途w狀態(tài)。

為禁止兩個進程同時進入臨界區(qū)，同步機制應(yīng)遵序以下準則：

• 空閑則讓
  臨界區(qū)空閑時，可以允許一個請求進入空閑區(qū)的進程立即進入臨界區(qū)
• 忙則等待
  當已有進程進入臨界區(qū)時，其他試圖進入臨界區(qū)的進程必須等待
• 有限等待
  對請求訪問的進程，應(yīng)保證能在優(yōu)先時間內(nèi)進入臨界區(qū)
• 讓權(quán)等待
  當進程能進入臨界區(qū)，應(yīng)立即釋放處理器，防著進程忙等待

二、臨界區(qū)的實現(xiàn)

1.軟件實現(xiàn)方法

在進入?yún)^(qū)設(shè)置和檢查一些標志來標明是否有進程在臨界區(qū)中，如果已有進程在臨界區(qū)，則在進入?yún)^(qū)通過循環(huán)檢查進行等待，進程離開臨界區(qū)后則在退出區(qū)修改標志。

接下來介紹兩種軟件解決方案：Peterson算法與Dekker算法。

• Dekker算法

bool flag[2];
int turn;//訪問權(quán)限
void P0(){
    while (true){
        flag[0] = true;//P0想使用關(guān)鍵區(qū)。
        while (flag[1]){//檢查P1是不是也想用？
            if (turn == 1){//如果P1想用，則查看P1是否具有訪問權(quán)限？
                flag[0] = false;//如果有，則P0放棄
                while (turn == 1);//檢查turn是否屬于P1。
                flag[0] = true;//P0想使用。
            }
        }
        do_something();//訪問critical section
        turn = 1; //訪問完成，將權(quán)限給P1。
        flag[0] = false;//P0結(jié)束使用。
    }
}
void P1(){
    while (true){
        flag[1] = true; //P1想使用關(guān)鍵區(qū)
        while (flag[0]){ //檢查P0是不是也想用？
            if (turn == 0){ //如果P0想用，則查看P0是否具有訪問權(quán)限？
                flag[1] = false; //如果有，則P1放棄
                while (turn == 0); //檢查turn是否屬于P1
                flag[1] = true; // P1想使用。
            }
        }
        do_something();//訪問critical section
        turn = 0; //訪問完成，將權(quán)限給P0
        flag[1] = false; //P1結(jié)束使用
    }
}

• Peterson算法

bool flag[2];//訪問請求
int turn;//訪問權(quán)
void* procedure0(void *){
    while (true){
        flag[0] = true;
        turn = 1;
        while (flag[1] && turn == 1){
            //P1需要訪問且擁有訪問權(quán)時，P0等待
            //當P1不想訪問或者不具備權(quán)限時推出
            Sleep(1);
            printf("procedure0 is waiting!\n");
        }
        do_something();//訪問critical section
        flag[0] = false;
    }
}
void* procedure1(void *){
    while (true){
        flag[1] = true;
        turn = 0;
        while (flag[0] && turn == 0){
            //P0需要訪問且擁有訪問權(quán)時，P1等待
            //當P0不想訪問或者不具備權(quán)限時推出
            Sleep(1);
            printf("procedure1 is waiting!\n");
        }
        do_something();//訪問critical section
        flag[1] = false;
    }
}

2.硬件實現(xiàn)方法

計算機提供了特殊的硬件指令，允許對一個字中的內(nèi)容進行檢測和修正，或者是對兩個字的內(nèi)容進行交換等。通過硬件支持臨界區(qū)訪問的方法或稱為元方法。

硬件實現(xiàn)方法主要有兩種：中斷屏蔽方法和硬件指令方法。

• 中斷屏蔽方法
  當某進程正在執(zhí)行其臨界區(qū)代碼時，為防止其他進程再進入其臨界區(qū)訪問的最簡單方法是禁止一切中斷發(fā)生，稱之為屏蔽中斷或關(guān)中斷。由于CPU只在發(fā)生中斷時引起進程切換，中斷的屏蔽便可保證當前進程順利執(zhí)行完臨界區(qū)代碼，進而保證互斥。其典型模式為：
  …
  關(guān)中斷;
  臨界區(qū);
  開中斷;
  …
  中斷屏蔽的實現(xiàn)方式代價很高。如果臨界區(qū)比較大的話會限制并發(fā)能力，不適用與多處理器，適用于操作系統(tǒng)本身，不適用與用戶進程

• 硬件指令方法
  1）TSL（TestAndSetLock）指令
  這條指令是原子操作，即執(zhí)行該代碼時不允許被中斷。其功能是讀出指定標志后把該標志設(shè)置為真。指令的功能描述如下：

enter_region:
    TSL REGISTER, LOCK
    CMP REGISTER, #0
    JINE enter_region
    RET
leave_region
    MOVE LOCK, #0
    RET

2）XCHG（EXCHANGE）指令
該指令的功能是交換兩個字節(jié)的內(nèi)容。其功能描述如下：

enter_region:
    MOVE REGISTER, #1
    XCHG REGISTER, LOCK
    CMP REGISTER, #0
    JINE enter_region
    RET
leave_region
    MOVE LOCK, #0
    RET