進程互斥與同步

1.引言：多道程序設計存在的問題？

采用多道程序設計技術的操作系統(tǒng)，允許多個進程同時駐留內存并發(fā)執(zhí)行。思考： A.如何協(xié)調多個進程對系統(tǒng)資源，如內存空間、外部設備等的競爭和共享？ B.如何解決多個進程因為競爭資源而出現(xiàn)執(zhí)行結果異常，甚至導致系統(tǒng)不穩(wěn)定、失效等問題？ 例如，多個進程同時申請文件打印，如何有效分配打印機？?

1.1 臨界資源訪問實例1：

銀行的聯(lián)網(wǎng)儲蓄業(yè)務允許儲戶同時用儲蓄卡和存折對同一帳戶進行存取款操作，如果某儲戶同時（在ATM機和營業(yè)柜臺）辦理兩筆存款業(yè)務（假設分別為1000和2000元），思考：余額是如何進行修改的？
從系統(tǒng)的角度看，有兩個進程【服務器上感知到的】將同時對儲戶余額等數(shù)據(jù)進行修改【銀行數(shù)據(jù)管理中心-計算中心數(shù)據(jù)庫】。如果兩個進程同時讀出原余額（假設為5000元），兩個進程分別將最新余額修改為6000 （5000+1000） 和7000 （5000+2000），顯然都不正確。
原因：兩個進程同時修改同一數(shù)據(jù)，而沒有進行有效控制。
正確的方法：如果有多個進程需要同時修改某一數(shù)據(jù)，系統(tǒng)必須控制，一次僅允許一個進程完成讀數(shù)據(jù)，并修改數(shù)據(jù)兩件事以后，才允許別的進程對同一數(shù)據(jù)的讀和修改操作。【互斥：A進程先修改，B進程阻塞；同步：A進程完成任務后，負責喚醒B進程】

1.2 臨界資源訪問實例2：

假設1：系統(tǒng)中有3個進程P1、P2、P3，其中P1和P2是計算進程，P3是打印進程，每當P1或P2計算出一個結果以后，將計算結果送到緩存區(qū)中，以便P3進程從中取出數(shù)據(jù)打印。
假設2：緩沖區(qū)被劃分為0、1、2...n-1共n個單元。
有兩個指針:in指針用于計算進程存放數(shù)據(jù)，指向緩沖區(qū)中下一個空閑的單元，out指針用于打印進程取數(shù)據(jù)，指向緩沖區(qū)中下一個將取走數(shù)據(jù)的單元。
解答： 假設某時刻，0到3號單元空閑，4到6號單元被占用，這時候P1、P2進程都準備將數(shù)據(jù)送入緩沖區(qū) ，如圖所示：
可能發(fā)生的情況： 1.?進程P1需要向緩沖區(qū)存儲數(shù)據(jù)，并知道in指針當前指向7號空閑緩沖單元。若這時進程P1的時間片用完，被中斷，調度程序調度進程P2執(zhí)行。 2.?P2正好也需要向緩沖區(qū)存放數(shù)據(jù)，首先獲取in指針位置，同樣也是7，于是，P2將數(shù)據(jù)送入7號單元，并將in指針移動一格，指向8號單元，然后繼續(xù)執(zhí)行其他操作。? 3.當進程P1再次被調度執(zhí)行時，將從上次的斷點繼續(xù)執(zhí)行，即將數(shù)據(jù)送入7號單元（覆蓋進程P2的數(shù)據(jù)），并移動in指針指向8號單元，然后繼續(xù)執(zhí)行其他操作。 4.進程P3不會發(fā)現(xiàn)上述錯誤【打印進程無法發(fā)覺數(shù)據(jù)覆蓋錯誤】，繼續(xù)從緩沖區(qū)取數(shù)據(jù)，進行打印。顯然，進程P2的相應計算結果不會被打印輸出。?
問題分析： 由于進程P1和P2共享緩沖區(qū)和位置指針，而未對這種共享進行有效控制，導致打印數(shù)據(jù)的丟失。如果控制進程P1、P2互斥地訪問緩沖區(qū)和修改位置指針，將避免這種因為并發(fā)執(zhí)行而導致的程序執(zhí)行結果的不確定性。

結論： 通過上述兩個例子可見，采用多道程序并發(fā)設計技術的操作系統(tǒng)對諸進程的并發(fā)控制是非常重要和必需的。?

2.并發(fā)控制

2.1 競爭資源

當并發(fā)進程競爭使用同一資源時，它們之間就會發(fā)生沖突。如果操作系統(tǒng)將資源分配給其中的某一個進程使用，另一個進程就必須等待，直到申請的資源可用時，由操作系統(tǒng)分配給它。如果競爭某資源的進程太多，這些進程還必須等待在一個隊列中，如就緒隊列，阻塞隊列等。一種極端的情況是，被阻塞進程永久得不到申請的資源，而死鎖【多個進程之間的僵持現(xiàn)象】。?
進程競爭資源首先必須解決“互斥”問題。某些資源必須互斥使用，如打印機、共享變量、表格、文件等。這類資源又稱為臨界資源【一次僅允許一個進程使用的資源】，訪問臨界資源的那段代碼稱為臨界區(qū)。任何時刻，只允許一個進程進入臨界區(qū)，以此實現(xiàn)進程對臨界資源的互斥訪問。


當進程需要使用臨界資源時，通過獲得臨界區(qū)的使用權實現(xiàn)的。
首先，在“進入?yún)^(qū)”判斷是否可以進入臨界區(qū)，如果可以進入，則必須設置臨界區(qū)使用標志，阻止其它后來的進程進入臨界區(qū)。后來的進程通過查看臨界區(qū)使用標志，知道自己不能進入臨界區(qū)，就進入阻塞隊列，將自己阻塞。
當臨界區(qū)內的進程使用完畢，退出臨界區(qū)時，即在“退出區(qū)”修改臨界區(qū)使用標志，并負責喚醒阻塞隊列中的一個進程，讓其進入臨界區(qū)。

2.2 如何保證互斥地訪問？

由于同一個臨界資源在多個共享它的進程中將對應多個臨界區(qū)，怎樣才能保證諸進程間互斥地執(zhí)行臨界區(qū)呢？
這就必須保證“臨界區(qū)使用標志”是可被系統(tǒng)中所有進程共享的全局變量，而且諸進程對該標志的修改操作必須互斥進行。?

2.3 臨界區(qū)使用條件（互斥條件）

1. 每次只允許一個進程處于 臨界區(qū)（忙則等待）；
2. 進程只能在臨界區(qū)內逗留有限時間，不得使其它進程在臨界外無限期等待（有限等待）
3. 如果臨界區(qū)空閑，則只要有進程申請就立即讓其進入（空閑讓進）；
4. 進入臨界區(qū)的進程，不能在臨界區(qū)內長時間阻塞等待某事件，必須在一定期限內退出臨界區(qū)（讓權等待）
5. 不能限制進程的執(zhí)行進度及處理機的數(shù)量

2.4 共同協(xié)作

多個進程常常需要共同修改某些共享變量、表格、文件數(shù)據(jù)庫等，協(xié)作完成一些功能。
必須確保它們對共享變量的修改是正確的，保證數(shù)據(jù)的完整性。
共享協(xié)作同樣涉及到互斥、死鎖和饑餓問題，但更強調對數(shù)據(jù)的寫操作必須互斥地進行。?只有該進程退出臨界區(qū)以后，才允許別的進程進入臨界區(qū)進行數(shù)據(jù)修改，以保證數(shù)據(jù)的一致性。

2.5 通信協(xié)作

當進程進行通信合作時，各個進程之間需要建立連接，進程通信需要同步和協(xié)調。進程通信的方式很多，包括消息傳遞、管道、共享存儲區(qū)等。通過消息傳遞實現(xiàn)進程通信時，由于沒有共享資源，故無須互斥，但仍可能出現(xiàn)死鎖和饑餓。
例如：3個進程P1、P2、P3，其中P1不斷嘗試與P2或P3通信，P2和P3又不斷嘗試與P1通信，如果P1與P2總能成功建立連接進行通信，而P3一直阻塞等待P1，這樣P3被長時間饑餓。?

3.競爭資源引起的死鎖與饑餓現(xiàn)象

2.1 競爭引起的死鎖

例如，兩個進程P1、P2，競爭資源R1、R2。
假設 ，現(xiàn)在P1已經(jīng)占用了R1，且P2占用了R2，如果此時P1申請R2，且P2申請R1。會怎么樣呢？
結果是P1、P2雙方都占用對方申請的資源而阻塞，誰也不讓步地永久等待，這就是死鎖，如圖所示：

2.2 競爭引起的饑餓

假設有3個進程P1、P2、P3，每個進程都需要周期性的使用資源R。如果當前P1正在使用臨界資源R，P2和P3因為等待R而阻塞。
Case：當P1退出臨界區(qū)時，P2立即進入臨界區(qū)執(zhí)行，若P2還未退出臨界區(qū)時，P1又申請使用臨界資源R。
:假設P2退出臨界區(qū)后，系統(tǒng)將R分給了P1，然后，當R空閑時，又將其分給P2，如此反復。【此時，P3就處于饑餓狀態(tài)】【該情況對P3是不公平的，應該避免】

總結

以上是生活随笔為你收集整理的[OS复习]进程互斥与同步1的全部內容，希望文章能夠幫你解決所遇到的問題。

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