第3章chapter3
進程同步1.1微型計算機簡介操作系統引入進程后,雖然改善了資源的利用率,提高了系統的吞吐量,但是系統中的多個進程由于競爭使用系統資源,導致它們之間存在一定的相互依賴、相互制約的關系。為了有效地協調各個并發進程間的關系,系統必須采用同步機制,確保進程之間能正確地競爭資源,并相互協調、相互合作。
3.1基本概念[4/5]3.1.1進程的制約關系多道程序環境下,系統中存在著多個并發進程。這些并發進程之間可能相互獨立,即一個進程的執行不影響其他進程的執行,此時系統無須對這些并發進程進行特別控制;并發進程之間也可能彼此相關、相互影響,即一個進程的執行可能影響其他進程的執行結果,此時,系統就需要合理地控制和協調這些進程的執行。根據共享資源性質的不同,并發進程之間的關系可以分為間接制約關系和直接制約關系。
（1）間接制約關系:也稱“競爭關系”,指系統中多個進程訪問相同的資源,其中一個進程訪問資源時,其他需訪問此資源的進程必須等待,只有當該進程釋放該資源后,其他進程才能訪問。進程的競爭關系可通過進程互斥方式來解決。
（2）直接制約關系:也稱“合作關系”,指系統中多個進程需要相互合作才能完成同一任務。例如,假設輸入進程和計算進程共同使用一個單緩沖區,那么當輸入進程將數據寫入緩沖區后,計算進程才能開始計算;當計算進程將緩沖區中的數據取走后,輸入進程才可以再次向緩沖區中寫入數據。進程的合作關系可通過進程同步機制來實現。
3.1.2進程互斥與同步[2]1.臨界資源及臨界區為了便于控制和管理競爭資源,系統引入了臨界資源和臨界區的概念:
（1）臨界資源:指一次只允許一個進程訪問的資源。臨界資源在任何時刻都不允許兩個及以上并發進程同時訪問。系統中有許多獨占性硬件資源（如卡片輸入機和打印機等）和軟件資源（如變量、表格、隊列、棧和文件等）均屬于臨界資源。
（2）臨界區:指進程訪問臨界資源的那段程序代碼。
系統若能保證進程互斥地進入各自的臨界區,便可實現臨界資源的互斥訪問。
2.進程互斥
進程互斥是指當一個進程進入臨界區使用臨界資源時,其他進程必須等待。當占用臨界資源的進程退出臨界區后,另外一個進程才被允許使用臨界資源。
◆計算機操作系統原理第◆3章進程同步若要實現各進程對臨界資源的互斥訪問,則需要保證各進程互斥地進入自己的臨界區。進程在進入臨界區之前,應先對臨界資源進行檢查,確認該資源是否正在被訪問。若臨界資源正被其他進程訪問,則該進程不能進入臨界區;若臨界資源空閑,該進程便可以進入臨界區對臨界資源進行訪問,并將該資源的標志設置為正在被訪問。因此,進程訪問臨界資源前,應增加一段用于進行上述檢查的代碼,這段代碼稱為進入臨界區;臨界資源訪問結束后,也要增加一段用于將臨界資源標志恢復為未被訪問的代碼,這段代碼稱為退出臨界區。臨界區的框架如下:do{
進入臨界區
訪問臨界資源
退出臨界區
其余代碼
}while(1);3.進程同步
進程同步是指多個進程為了合作完成同一個任務,在執行次序上相互協調、相互合作,在一些關鍵點上還需要相互等待或相互通信。
進程同步的例子在現實生活中隨處可見,如司機與售票員的關系。公共汽車的司機負責開車和到站停車,售票員負責售票和開關車門,他們之間是相互合作、相互配合的。例如車門關閉后才能啟動,到站停車后才能打開車門,即“啟動汽車”在“關閉車門”之后,而“打開車門”在“到站停車”之后。司機和售票員之間的活動關系如圖31所示。
圖31司機與售票員的關系
若進程P1和P2分別表示司機和售票員,當它們并發向前推進時,則需滿足以下要求:
（1）若P1推進到①,但P2未到達②時,則P1應等待,直到P2到達②為止。
（2）若P2推進到④,但P1未到達③時,則P2應等待,直到P1到達③為止。
（3）若P1在①處等待,則當P2到達②處時,應通知（喚醒）P1。
（4）若P2在④處等待,則當P1到達③處時,應通知（喚醒）P2。
由此可知,為了協調進程推進次序,相互合作的并發進程有時需要互相等待與互相喚醒。
4.同步與互斥的關系
同步與互斥是并發進程之間兩種重要關系,其中互斥反映了進程間的競爭關系,而同步則反映了進程間的合作關系。
進程互斥是進程同步的一種特殊情況。例如,某個進程進入臨界區時,其他進程不允許進入臨界區。當進程完成任務離開臨界區,并歸還臨界資源后,喚醒其等待進入臨界區的進程。這說明互斥的進程也存在特殊的合作關系。因此,互斥是一種特殊的同步關系。
互斥所涉及的并發進程之間只是競爭獲得共享資源的使用權,這種競爭沒有固定的、必然的聯系,誰競爭到資源,誰就擁有資源的使用權,直到不需要時才歸還;而同步所涉及的并發進程之間有一種必然的聯系,在進程同步過程中,即使沒有進程使用共享資源,尚未得到同步消息的進程也不能去使用共享資源。
5.臨界區的管理準則
為了實現進程的同步與互斥,可以利用軟件方法或在系統中設置專門的同步機制,協調各個并發進程。同步機制必須遵循以下4條準則:
（1）閑則讓進:當臨界資源處于空閑狀態時,系統應允許一個請求訪問該臨界資源的進程進入自己的臨界區,訪問該臨界資源。
（2）忙則等待:當臨界資源正在被訪問時,其他試圖進入臨界區訪問該臨界資源的進程必須等待,以保證臨界資源的互斥訪問。
（3）有限等待:對于等待訪問臨界資源的進程,系統應保證這些等待進程在有限時間內能進入臨界區,訪問臨界資源,以避免陷入“死等”狀態。
（4）讓權等待:當進程不能進入臨界區訪問臨界資源時,應立即釋放CPU,以免該進程陷入“忙等”（即等待時占有CPU）狀態。
3.2同步機制
進程同步機制的基本目標是在功能上保證進程能夠正確地互斥執行各自的臨界區,其具體的實現方法包括軟件方法、硬件方法、信號量方法和管程這四大類。
3.2.1軟件方法
軟件方法是指通過編寫程序代碼方式進入臨界區,以訪問臨界資源。此方法既適用于單CPU環境,也適用于多CPU環境,只需這些CPU共享一個存儲區,且各個進程對該存儲區串行訪問即可。
下面通過程序偽代碼方式說明實現進程之間互斥訪問臨界資源的軟件方法。
1.算法1
該算法的基本思想:若一個進程申請使用臨界資源,應先查看該資源當前是否被一個進程訪問。若資源正在被訪問,則該進程只能等待,否則進入自己的臨界區執行。下面是進程P1和P2的程序偽代碼,其中inside1和inside2為布爾型變量,且初值均false,表示P1和P2均不在其臨界區內。booleaninside1,inside2;
inside1=false;//P1不在其臨界區內
inside2=false;//P2不在其臨界區內
cobegin
processP1(){
while(inside2);
inside1=ture;
訪問臨界資源;
inside1=false;
}
processP2(){
while(inside1);
inside2=ture;
訪問臨界資源;
inside2=false;
}
coend該算法雖然實現了進程互斥管理的“閑則讓進”準則,保證了每次只允許一個進程進入臨界區,但違背了“忙則等待”準則。例如,假設P1和P2先后執行“while（inside2）;”和“while（inside1）;”,發現對方均不在臨界區內,則它們執行“inside1=true;”和“inside2=true;”,并進入了各自臨界區內,同時訪問該臨界資源。
2.算法2
算法1違背了“忙則等待”準則,沒有實現對臨界區的互斥訪問。算法2對其進行了改進,即進程若想進入臨界區,必須搶先將自己的標志設置為true,以防止對方再進入臨界區。
算法2的程序偽代碼如下:booleaninside1,inside2;
inside1=false;//P1不在其臨界區內
inside2=false;//P2不在其臨界區內
cobegin
processP1(){
inside1=ture;
while(inside2);
訪問臨界資源;
inside1=false;
}
processP2(){
inside2=ture;
while(inside1);
訪問臨界資源;
inside2=false;
}
coend算法2雖然解決了“忙則等待”問題,但存在著“有限等待”問題。例如,當P1和P2都判斷對方不在臨界區時,P1執行“inside1=true;”,此時P2同樣也執行“inside2=true;”,然后P1和P2分別執行“while(inside2);”和“while(inside1);”時,均因為條件不滿足,而無法往下執行,導致P1和P2將陷入無限等待狀態。
3.Peterson算法
Peterson采用了原語形式,提出了一種表述簡單的算法,很好地解決了臨界區互斥的問題,能滿足臨界區訪問的四個條件。Peterson算法的基本思想:當一個進程需要進入臨界區,需先調用enter_section()函數,判斷是否可以安全進入臨界區,若不能則等待;當從臨界區退出后,調用leave_section()函數,允許其他進程進入臨界區。Peterson算法流程如下:#defineFALSE0
#defineTRUE1
#defineN2//競爭資源的進程數目
intobserver;//輪到哪個進程觀察要進入臨界區的情況
intwanted_in(N);//各進程希望進入臨界區的標志
enter_section(process)//進入臨界區的互斥控制函數
intprocess;//進程編號,0或1
{
intother;//對方進程號
other=1-process;
wanted_in\[process\]=TRUE;//本進程要進入臨界區
observer=process;//觀察進入臨界區的情況,設置標志位
while(observer==process&&wanted_in\[other\]);//等待,什么都不做
}
leaver_section(process)//退出臨界區函數
intprocess;
{
wanted_in\[process\]=FALSE;//離開了臨界區
}3.2.2硬件方法
軟件方法相對復雜且容易出錯,因而現在系統較少采用。目前常用的是通過硬件方法實現同步互斥操作。
1.開關中斷法
開關中斷法采用中斷方式,借助硬件中斷機構實現臨界區的管理。當進程進入臨界區后,關閉系統中斷;離開臨界區時,重新開啟系統中斷。由于進程切換是由時鐘或其他中斷導致,因而當中斷被屏蔽后,其他進程無法獲得CPU調度,導致無法運行,從而實現了臨界區的互斥訪問。進程進入臨界區后,只要不自行掛起,就會連續地執行,直至退出臨界區,并在執行開中斷指令后,才可能重新調度,允許其他進程進入臨界區。do{
開中斷
訪問臨界資源
關中斷
其余代碼
}while(1);開關中斷方法具有效率高、簡單易行,且系統不會出現忙等現象;但其缺點也較明顯,如只適用于單CPU系統和系統效率較低,進而影響系統處理緊迫事件的能力。多CPU系統中,禁止中斷只會影響當前CPU,而其他CPU上并行執行的進程仍然能不受阻礙地進入臨界區。
2.測試與設置方法
測試和設置（TestandSet,TS）方法利用指令讀取內存中某個變量的值后,重新給它賦一個新值。TS指令定義如下:intTS(inttarget){
inttemp;
temp=target;
target=1;
return(temp);
}TS指令首先讀取當前變量的值,作為參數返回,同時將其值置為1。由于該指令是原子操作,因此,它在執行期間不允許被打斷,即所有語句要么全執行,要么都不執行。
TS指令可用來實現進程互斥操作。具體地,設置一個共享變量（如lock）,置其初值為0,表示臨界區內沒有進程。每個進程在進入臨界區之前,先使用TS指令測試該共享變量。若其值為0,則進入臨界區,并將其值置為1;若其值為1,則表明其他進程已進入臨界區,此時該進程需等待。進程離開臨界區時,需將共享變量的值置為0。使用TS指令的互斥算法如下:while(1){
while(TS(lock));
訪問臨界資源;
lock=0;
}盡管上面算法可以實現進程互斥操作,但仍然存在“忙碌等待”,浪費了CPU寶貴的資源,因而實際情況中較少使用。
3.swap指令
Swap指令也稱交換指令,其功能是交換兩個變量的值,具體實現如下:voidswap(inta,b){
inttemp;
temp=a;a=b;b=temp;
}Swap指令是原子操作,執行期間是不可分割的。使用swap指令實現進程互斥時,需對臨界區（可表示為一組共享變量）定義一個全局變量（如lock）,并對每個進程定義一個局部變量（如key）。利用swap指令實現的進程互斥算法具體實現如下:key=1;
do{
swap(&lock,&key);
whlie(key==1);
訪問臨界資源;
lock=0;
其余代碼;
}while(1);進程在進入臨界區前,利用swap指令交換lock和key的值,檢查key的狀態,判斷是否有進程已進入臨界區。若其他進程已進入,則該進程不斷重復交換和檢查過程,直到其他進程退出臨界區。
3.3信號量方法
由于硬件方法采用原語或指令形式,將修改和檢查作為一個不可分割的整體,因而比軟件方法具有明顯的優勢。然而,進入臨界區的進程是隨機選擇的,使得部分進程可能一直未被選擇,從而導致“饑餓”現象。為此,實際系統中常采用信號量機制和PV操作進程互斥。
信號量機制是指兩個或多個進程利用彼此之間收發的簡單信號來實現并發執行,其中進程若未收到指定的信號,則停留在特定的地方,直至收到了信號后才能繼續往下執行。信號量機制目前是一種卓有成效的進程同步機制,已被廣泛應用于各種系統。
3.3.1信號量機制[2]1.信號量的概念信號量（Semaphore）是一種特殊變量,它用來表示系統中資源的使用情況,其值與臨界區內所使用的臨界資源的狀態有關。如果信號量S是一個整型變量,則其值表示系統中某類資源的數目。S必須且只能設置一次初值,并大于或等于0。當其值大于0時,表示系統中對應可用資源的數目;當其值小于0時,其絕對值表示等待該類資源的進程的數目;當其值等于0時,表示系統中對應資源已用完,且沒有進程等待該類資源。
2.信號量的操作
信號量機制中,信號量的值僅能通過兩個標準的原語操作來改變,它們分別是P操作和V操作。信號量S的P、V操作表示為:P(S)和V(S),也稱為wait和signal。由于P、V操作是原語,因此,它們在執行的過程中不可中斷。
利用信號量和P、V操作既可以解決并發進程對資源的競爭問題,又可以解決并發進程的合作問題。進程在互斥訪問臨界資源、進入臨界區前,先執行P操作,退出臨界區后應執行V操作。
3.3.2信號量的分類
信號量機制自提出以來得到了很大發展,已從最初的單信號量機制發展到多信號量機制。
1.單信號量機制
單信號量機制是指信號量所涉及的變量只有一個。根據變量的類型,單信號量機制包括互斥型信號量、整型信號量和記錄型信號量等,其中互斥型信號量最簡單,而記錄型信號量表達能力最強。
（1）互斥型信號量
互斥型信號量也稱0/1信號量,它的值為0、1或FALSE、TRUE,表示當前信號量所代表的臨界資源是否可用,其中1或TRUE表示臨界資源可用,而0或FALSE表示臨界資源當前已被占用。
互斥型信號量定義為:booleanS;//互斥信號量的定義互斥型信號量的P、V操作描述如下:voidP(booleanS){
while(!S);//若信號量為FALSE,表示資源不可用,繼續測試
S=FALSE;//表示可以進入臨界區,同時不允許其他進程進入
}
voidV(booleanS){
S=TRUE;//允許其他進程進入臨界區
}（2）整型信號量
互斥型信號量雖然能保證進程互斥地訪問臨界資源,但不能反映臨界資源的數量。針對這個問題,提出了整型信號量,即信號量的類型為整型。整型信號量S的初始值應大于等于0,其值不僅能表示臨界資源是否空閑,還具有如下物理意義:
①S>0:表示當前有S個資源可用;
②S=0:表示當前沒有資源可用,且沒有等待該資源的進程;
③S<0:表示當前有|S|個進程正在等待此資源。
整型信號量定義為:intS;//整型信號量定義整型信號量的P、V操作描述如下:voidP(intS){
S--;//表示申請一個資源
while(S<0);//若信號量為0,表示無資源可用,反復測試
}……
新書資訊