第4章并發(fā)處理

主要內(nèi)容:1．

進(jìn)程的引入2．

進(jìn)程的概念3．

進(jìn)程控制4．

進(jìn)程的相互制約關(guān)系5．

進(jìn)程互斥6．

信號燈和P、V操作7．

進(jìn)程同步8．

進(jìn)程通信9.UNIX系統(tǒng)的進(jìn)程管理第4章并發(fā)處理主要內(nèi)容:6．

信號燈和P、V操作4.1并發(fā)活動——進(jìn)程的引入

4.1.1程序的順序執(zhí)行

（一）數(shù)據(jù)、操作對某一有限數(shù)據(jù)的集合所施行的、目的在于解決某一問題的一組有限的操作的集合，稱為一個計算。（二）順序程序一個程序由若干個程序段組成，而這些程序段的執(zhí)行必須是順序的，這個程序被稱為順序程序。4.1并發(fā)活動——進(jìn)程的引入4.1.1程序的順序執(zhí)行（三）順序程序的特點1.順序性：處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行2.封閉性：程序執(zhí)行的結(jié)果不受外界因素的影響，即一個程序執(zhí)行時所用的變量、指針值、各資源的狀態(tài)不能被外界改變。3.可再現(xiàn)性：程序執(zhí)行的結(jié)果與它的執(zhí)行速度無關(guān)（即與時間無關(guān)），只與初始條件有關(guān)。（三）順序程序的特點4.1.2程序的并發(fā)執(zhí)行

所謂程序的并發(fā)執(zhí)行是指：若干個程序同時在系統(tǒng)中運行，這些程序的執(zhí)行在時間上是重迭的，一個程序的執(zhí)行尚未結(jié)束，另一個程序的執(zhí)行已經(jīng)開始，即使這種重迭是很小的一部分，那么這兩個程序是并發(fā)執(zhí)行的。

4.1.2程序的并發(fā)執(zhí)行操作系統(tǒng)原理-第4章-并發(fā)處理ppt課件程序的并發(fā)執(zhí)行的表示方法：

1.圖示方法

程序的并發(fā)執(zhí)行的表示方法：操作系統(tǒng)原理-第4章-并發(fā)處理ppt課件2．語句方法（荷蘭科學(xué)家E.W.Dijkstra方法）

S0；

cobeginS1；S2；．．．；Sn；

coendSn+1；

2．語句方法（荷蘭科學(xué)家E.W.Dijkstra方法）4.1.3并發(fā)執(zhí)行實例—譽抄

(一)一個循環(huán)程序的譽抄方案

假設(shè)f表示輸入序列，g表示輸出序列。main(){while(f不空){input;/*讀入f中的數(shù)據(jù)；*/output;/*輸出讀入的數(shù)據(jù)；*/}}卡片輸入機(jī)打印機(jī)4.1.3并發(fā)執(zhí)行實例—譽抄卡片輸入機(jī)打印機(jī)（二）

兩個并發(fā)程序的譽抄方案假設(shè)f表示輸入序列，g表示輸出序列,譽抄過程利用一個緩沖區(qū)A。（二）

兩個并發(fā)程序的譽抄方案main(){

cobeginwhile(f不空){input;/*讀入f中的數(shù)據(jù)；*/send;/*將讀入的數(shù)據(jù)送到A；*/}while(謄抄未完成){receive;/*從A中取的數(shù)據(jù)；*/output;/*輸出取出的數(shù)據(jù)；*/}coend}

fAgmain()fAg三個并發(fā)程序的譽抄方案main(){if(f不空){get(s,f);while(謄抄未完成){t=s;/*COPY*/cobeginput(t,g);get(s,f);coend}}}

fstg三個并發(fā)程序的譽抄方案fstg4.1.4與時間有關(guān)的錯誤結(jié)論：并發(fā)程序如共享某些公共變量時，并發(fā)程序執(zhí)行時會出現(xiàn)與時間有關(guān)的錯誤。如

4.1.4與時間有關(guān)的錯誤main(){if(f不空){get(s,f);while(謄抄未完成){

/*t=s;*//*COPY*/cobegint=s;/*COPY*/put(t,g);get(s,f);coend}}}main()4.1.5并發(fā)程序的特點（一）失去程序的封閉性和再現(xiàn)性（二）程序與計算不再一一對應(yīng)

(三)程序并發(fā)執(zhí)行的相互制約

4.1.5并發(fā)程序的特點4.2進(jìn)程概念

4.2.1進(jìn)程的定義到目前為止，進(jìn)程有多種定義，如：（1）

進(jìn)程是程序的執(zhí)行；（2）

并行程序稱為進(jìn)程；（3）

進(jìn)程是可以和別的計算并發(fā)的計算；（4）

進(jìn)程是一個數(shù)據(jù)結(jié)構(gòu)及在其上進(jìn)行操作的程序。4.2進(jìn)程概念4.2.1進(jìn)程的定義這些定義都從不同的側(cè)面描述了進(jìn)程的特征，都一定的道理，但我們認(rèn)為下面的定義更全面和更準(zhǔn)確：進(jìn)程是一個具有一定獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。此定義包含有如下的含義：這些定義都從不同的側(cè)面描述了進(jìn)程的特征，都一定的道理，但我們（1）

進(jìn)程是一個動態(tài)的概念，而程序是一個靜態(tài)的概念；（2）

進(jìn)程包含了一個數(shù)據(jù)集合和運行其上的程序；（3）

同一程序運行于若干不同的數(shù)據(jù)集合上時，它將屬于若干個不同的進(jìn)程，或者說，兩個不同的進(jìn)程可包含相同的程序；（4）

系統(tǒng)分配資源是以進(jìn)程為單位的，所以只有進(jìn)程才可能在不同的時刻處于幾種不同的狀態(tài)，即等待、就緒、運行。（5）

從微觀上看，進(jìn)程是輪換地占有處理機(jī)而運行的，從宏觀上看，進(jìn)程是并發(fā)地運行的。（1）進(jìn)程是一個動態(tài)的概念，而程序是一個靜態(tài)的概念；進(jìn)程和程序是即有聯(lián)系又有區(qū)別的兩個概念，它們的區(qū)別和關(guān)系如下：（1）程序是指令的有序集合，其本身沒有任何運行的含義，它是一個靜態(tài)概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，它是一動態(tài)概念。程序可以作為一種軟件資料長期保存，而進(jìn)程是有一定生命周期的，它能夠動態(tài)地產(chǎn)生和消亡。即進(jìn)程可由“創(chuàng)新”而產(chǎn)生，由調(diào)度而執(zhí)行，因得不到資源而暫停，以致最后由“撤消”而消亡。進(jìn)程和程序是即有聯(lián)系又有區(qū)別的兩個概念，它們的區(qū)別和關(guān)系如下（2）進(jìn)程是一個能獨立運行的單位，能與其它進(jìn)程并行地活動。（3）進(jìn)程是競爭計算機(jī)系統(tǒng)有限資源的基本單位，也是進(jìn)行處理機(jī)調(diào)度的基本單位。(4)同一程序同時運行于若干不同的數(shù)據(jù)集合上，它將屬于若干個不同的進(jìn)程?；蛘哒f，若干個不同的進(jìn)程可以包含相同的程序。這句話的意思是：用同一程序?qū)Σ煌臄?shù)據(jù)先后或同時加以處理，就對應(yīng)與好幾個進(jìn)程。例如，系統(tǒng)具有一個輸入子程序，當(dāng)它輸入不同的作業(yè)時就形成了輸入進(jìn)程I1、I2、I3……In。（2）進(jìn)程是一個能獨立運行的單位，能與其它進(jìn)程并行地活動。進(jìn)程的構(gòu)成進(jìn)程=PCB+程序+數(shù)據(jù)進(jìn)程的構(gòu)成4.2.2進(jìn)程的類型1．系統(tǒng)進(jìn)程2．用戶進(jìn)程3．系統(tǒng)進(jìn)程與用戶進(jìn)程的區(qū)別：（1）

系統(tǒng)進(jìn)程被分配一個初始的資源集合，這些資源可以獨占，也可以最高優(yōu)先權(quán)資格優(yōu)先使用。用戶進(jìn)程通過系統(tǒng)服務(wù)請求的手段競爭系統(tǒng)資源。（2）

系統(tǒng)進(jìn)程可以進(jìn)行顯示的、直接的I/O操作。用戶進(jìn)程不進(jìn)行直接的I/O操作。(3)系統(tǒng)進(jìn)程在管態(tài)下活動。用戶進(jìn)程在目態(tài)下活動。

4.2.2進(jìn)程的類型4.2.3進(jìn)程的狀態(tài)（一）進(jìn)程的基本狀態(tài)

（1）就緒狀態(tài)：存在于處理機(jī)調(diào)度隊列中的那些進(jìn)程，它們已經(jīng)準(zhǔn)備就緒，一旦得到CPU就立即可以運行，這些進(jìn)程所處的狀態(tài)為就緒狀態(tài)。（2）運行狀態(tài)：當(dāng)進(jìn)程由調(diào)度/分派模塊分派后，得到中央處理機(jī)控制權(quán)，它的程序正在運行，該進(jìn)程所處的狀態(tài)為運行狀態(tài)。（3）

等待狀態(tài)：若一進(jìn)程正在等待著某一事件發(fā)生（如等待輸入輸出操作的完成）而暫時停止執(zhí)行，這時，即使給它CPU時間，它也無法執(zhí)行，則稱該進(jìn)程處于等待狀態(tài)。又可稱為阻塞狀態(tài)或掛起狀態(tài)。

4.2.3進(jìn)程的狀態(tài)（二）進(jìn)程狀態(tài)變遷圖在進(jìn)程狀態(tài)變遷圖中，以結(jié)點表示進(jìn)程的狀態(tài)，以箭頭表示狀態(tài)的變化。

請求可以滿足開始時間片到進(jìn)程調(diào)度請求無法滿足完成等待就緒執(zhí)行圖4.8進(jìn)程狀態(tài)變遷圖（二）進(jìn)程狀態(tài)變遷圖請求可以滿足時間片到請求無法滿足等待就緒（三）引起進(jìn)程狀態(tài)轉(zhuǎn)換的4原因（1）CPU調(diào)度（低級調(diào)度）：CPU調(diào)度按某種原則從就緒隊列中調(diào)度一個進(jìn)程到CPU上運行，該進(jìn)程就從就緒狀態(tài)變?yōu)檫\行狀態(tài)；與此同時，原運行進(jìn)程從運行狀態(tài)變?yōu)榫途w狀態(tài)。因此，這兩種狀態(tài)變化是同時發(fā)生的。（2）進(jìn)程在運行過程中需要等待某一事件，例如，等待分配某一資源，等待I/O操作完成等。一個進(jìn)程在需要等待某一事件時主動退出CPU，并使自己處于阻塞狀態(tài)，引起狀態(tài)變化。（三）引起進(jìn)程狀態(tài)轉(zhuǎn)換的4原因（3）如果進(jìn)程所等待的事件發(fā)生了變化，例如，一次I/O完成了，于是進(jìn)程便被解除阻塞狀態(tài)，變?yōu)榫途w狀態(tài)。(4)一個具體的進(jìn)程在任何一個指定的時刻必須而且只能處于一種狀態(tài)。（3）如果進(jìn)程所等待的事件發(fā)生了變化，例如，一次I/O完成了（四）進(jìn)程狀態(tài)轉(zhuǎn)換的說明（1）

進(jìn)程之間的狀態(tài)轉(zhuǎn)換并非都是可逆的進(jìn)程既不能從等待變?yōu)檫\行，也不能從就緒變?yōu)榈却?。?）進(jìn)程之間的狀態(tài)轉(zhuǎn)換并非都是主動的，在很多情況下都是“它動的”事實上，只有運行到等待的轉(zhuǎn)換是進(jìn)程的主動行為（主動調(diào)用調(diào)度管理程序），其它都是它動的，例如，從執(zhí)行到就緒，通常是時鐘中斷引起的，從等待到就緒，是一個進(jìn)程把另一個進(jìn)程喚醒。

（四）進(jìn)程狀態(tài)轉(zhuǎn)換的說明4.2.4進(jìn)程的描述-----進(jìn)程控制塊進(jìn)程控制塊（processcontrolblock,PCB）是進(jìn)程的重要組成部分，是操作系統(tǒng)能“感知”進(jìn)程存在的唯一標(biāo)志，它和進(jìn)程是一一對應(yīng)的，操作系統(tǒng)正是通過管理PCB來管理進(jìn)程的。為了描述一個進(jìn)程和其它進(jìn)程相聯(lián)系的數(shù)據(jù)塊，稱為進(jìn)程控制塊pcb(processcontrolblock)或稱為進(jìn)程描述器（processdescriptor）。包含下面的內(nèi)容：4.2.4進(jìn)程的描述-----進(jìn)程控制塊（1）

進(jìn)程標(biāo)識符name（2）

進(jìn)程當(dāng)前狀態(tài)status（3）

當(dāng)前隊列指針next（4）

總鏈指針all-q–next（5）

進(jìn)程開始地址start-addr（6）

進(jìn)程優(yōu)先級priority（7）

CPU現(xiàn)場保護(hù)區(qū)cpustatus（8）

通信信息communication-information（9）

家族聯(lián)系process-family（10）

占用資源清單own-resource（1）

進(jìn)程標(biāo)識符name4.3進(jìn)程控制

4.3.1進(jìn)程控制的概念進(jìn)程控制的職責(zé)是對系統(tǒng)中的全部進(jìn)程實施有效的管理，它是處理機(jī)管理的一部分，當(dāng)系統(tǒng)允許多進(jìn)程并發(fā)執(zhí)行是，為了實現(xiàn)共享、協(xié)調(diào)并發(fā)進(jìn)程的關(guān)系，處理機(jī)管理機(jī)就提供對進(jìn)程實行有效的功能。用于進(jìn)程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等4.3進(jìn)程控制4.3.1進(jìn)程控制的概念原語

一般，我們把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段成為原語，原語可是機(jī)器指令級的擴(kuò)充，其特點是執(zhí)行期間不允許中斷、它是一個不可分割的基本單位。它們都在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個系統(tǒng)管理所需要的功能和被高層軟件調(diào)用。原語一般，我們把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序4.3.2進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建的方式有兩種：（a）由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建。例如在批處理系統(tǒng)中，由操作系統(tǒng)的作業(yè)調(diào)度程序為用戶進(jìn)程創(chuàng)建相應(yīng)的進(jìn)程以完成用戶作業(yè)所要求的功能。（b）由父進(jìn)程創(chuàng)建。例如在UNIX操作系統(tǒng)中，父進(jìn)程創(chuàng)建子進(jìn)程以完成并行工作。

4.3.2進(jìn)程創(chuàng)建create(name,priority,start_add){在總鏈隊列上查找有無同名的進(jìn)程；if(有同名的進(jìn)程)return(錯誤碼)；從pcb資源池申請一個空閑的pcb結(jié)構(gòu)；if(無空pcb結(jié)構(gòu))return(錯誤碼)；用入口參數(shù)設(shè)置pcb內(nèi)容；置進(jìn)程為“就緒”狀態(tài)；將新進(jìn)程的pcb插入就緒隊列；將新進(jìn)程的pcb插入總鏈隊列；return(新進(jìn)程的pid)；}create(name,priority,start_add4.3.3進(jìn)程撤消進(jìn)程撤消的原因：1）

該進(jìn)程已完成所要求的功能而正常終止。2）

由于某種錯誤導(dǎo)致非正常終止。4.3.3進(jìn)程撤消Kill(){由運行指針得到當(dāng)前進(jìn)程的pid；釋放本進(jìn)程所占資源給父進(jìn)程；將該進(jìn)程從總鏈隊列中摘除；釋放該進(jìn)程的pcb；轉(zhuǎn)進(jìn)程調(diào)度程序；}Kill()4.3.4進(jìn)程等待（阻塞）阻塞原語在一個進(jìn)程期待某一事件發(fā)生但發(fā)生條件尚不具備時，被該進(jìn)程自己調(diào)用來阻塞自己。阻塞原語在阻塞一個進(jìn)程時，由于該進(jìn)程正處于執(zhí)行狀態(tài)，故應(yīng)先中斷處理機(jī)和保存該進(jìn)程的處理機(jī)現(xiàn)場，然后被阻塞進(jìn)程置阻塞狀態(tài)后插入等待隊列中，再轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運行。

4.3.4進(jìn)程等待（阻塞）susp(chan)//*入口參數(shù)chan，進(jìn)程等待的原因*//{保護(hù)現(xiàn)行進(jìn)程的CPU現(xiàn)場到pcb結(jié)構(gòu)中；置進(jìn)程為“等待”狀態(tài)；將該進(jìn)程的pcb插入到等待chan的等待隊列中；轉(zhuǎn)進(jìn)程調(diào)度；}susp(chan)4.3.5進(jìn)程喚醒進(jìn)程喚醒的兩種方法1）

由系統(tǒng)進(jìn)程喚醒系統(tǒng)統(tǒng)一控制事件的發(fā)生并將“事件發(fā)生”這一消息通知等待進(jìn)程。2）

由事件發(fā)生進(jìn)程喚醒4.3.5進(jìn)程喚醒wakeup(chan)/*輸入：chan等待的事件（阻塞原因）

輸出：無*/{找到該等待chan的隊列指針；for(等待該事件的進(jìn)程){將進(jìn)程移出此等待隊列；置進(jìn)程為“就緒”狀態(tài)；將進(jìn)程pcb入就緒隊列；}}wakeup(chan)4.3.6進(jìn)程延遲

delay(seconds)/*seconds為所需延遲秒數(shù)*/{保護(hù)調(diào)用進(jìn)程的CUP現(xiàn)場；clock_ticks=secondsX(clock_rate)；/*需延遲的機(jī)內(nèi)時間，clock_rate為時鐘速率*/封鎖延遲隊列；以clock_ticks值查找延遲隊列；找到合適位置插入；/*延遲隊列按延遲時間升序排隊*/解除延遲隊列；置進(jìn)程為延遲狀態(tài)；轉(zhuǎn)進(jìn)程調(diào)度；}4.3.6進(jìn)程延遲4.4進(jìn)程的相互制約關(guān)系

資源共享是當(dāng)代計算機(jī)系統(tǒng)的一個重要特征。而資源共享導(dǎo)致進(jìn)程之間存在相互制約關(guān)系。

4.4進(jìn)程的相互制約關(guān)系資源共享是當(dāng)代計算機(jī)系統(tǒng)的一資源共享的方式（兩種）1.由系統(tǒng)進(jìn)行統(tǒng)一分配凡需要使用共享資源的進(jìn)程，先向系統(tǒng)申請，然后由系統(tǒng)根據(jù)資源情況，按一定的策略進(jìn)行分配。如，進(jìn)程對處理機(jī)的共享，靠操作系統(tǒng)的進(jìn)程調(diào)度程序來協(xié)調(diào)；內(nèi)存的共享，靠操作系統(tǒng)的內(nèi)存管理程序來協(xié)調(diào)。

資源共享的方式（兩種）2.由程序自行使用系統(tǒng)中的某些資源無需系統(tǒng)分配，而由進(jìn)程自行使用，如數(shù)據(jù)集、變量、隊列等。共享這些資源時，靠操作系統(tǒng)提供的同步機(jī)構(gòu)來協(xié)調(diào)

2.由程序自行使用進(jìn)程合作進(jìn)程合作時，必定會出現(xiàn)數(shù)據(jù)的共享，如消息的傳遞等。

進(jìn)程合作4.4.2進(jìn)程互斥與同步同步:所謂進(jìn)程同步就是對于進(jìn)程操作的時間順序所加的某種限制。也可以說進(jìn)程同步是進(jìn)程間共同完成一項任務(wù)是直接發(fā)生相互作用的關(guān)系，也就是說，這些具有伙伴關(guān)系的進(jìn)程在執(zhí)行時間次序上必須遵循確定的規(guī)律。4.4.2進(jìn)程互斥與同步同步:互斥:在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問某一存儲區(qū)域時，就不允許其它進(jìn)程來讀出或者修改存儲區(qū)的內(nèi)容，否則就會發(fā)生后果無法估計的錯誤。我們把進(jìn)程之間的這種相互制約關(guān)系稱為互斥。也可以說，進(jìn)程的互斥是因為對同一物理資源的競爭而產(chǎn)生的相互制約關(guān)系。

互斥:同步與互斥的特點比較

同步與互斥的特點比較臨界資源和臨界區(qū)我們把一次只允許一個進(jìn)程使用的資源稱為臨界資源，而把在每個進(jìn)程中訪問臨界資源的程序段稱為臨界區(qū)。要進(jìn)入臨界區(qū)的若干個進(jìn)程必須滿足如下關(guān)系：（1）

一次只允許一個進(jìn)程進(jìn)入臨界區(qū)。（2)任何時候，處于臨界區(qū)的進(jìn)程不得多于一個。（3）進(jìn)入臨界區(qū)的進(jìn)程要在有限的時間內(nèi)退出。(4)如果不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出處理機(jī)資源。

臨界資源和臨界區(qū)4.5.同步機(jī)構(gòu)4.5.1鎖和上鎖、開鎖操作對應(yīng)于每一共享數(shù)據(jù)塊或設(shè)備都要有一個單獨的鎖位。按慣例，常用鎖位w值為“0”表示資源可用，而用“1”表示資源已經(jīng)被占用。這樣，進(jìn)程使用某一共享資源之前就必須完成下列動作（即關(guān)鎖操作）：（1）考察鎖位的值（是0還是1）；（2）如果原來的值為0，將鎖位置1（表示占用資源）；（3）如果原來的值為1（即資源已被占用），則返回第一步再考察。當(dāng)前進(jìn)程使用完資源后，它將鎖位置成“0”，稱為開鎖操作。

4.5.同步機(jī)構(gòu)局限性：只要有一個進(jìn)程由于執(zhí)行關(guān)鎖操作而進(jìn)入臨界區(qū)，則其它進(jìn)程在檢查鎖狀態(tài)時都將反復(fù)執(zhí)行關(guān)鎖操作，從而導(dǎo)致處理機(jī)繁忙。

現(xiàn)在一般采用硬件指令來解決互斥進(jìn)入臨界區(qū)問題。

局限性：只要有一個進(jìn)程由于執(zhí)行關(guān)鎖操作而進(jìn)入臨界區(qū)，則其它進(jìn)lock(w){while(w==1){保護(hù)現(xiàn)行進(jìn)程的CPU現(xiàn)場；現(xiàn)行進(jìn)程入等W的隊列；將該進(jìn)程登記為“等待”狀態(tài)；轉(zhuǎn)到進(jìn)程調(diào)度；}w=1;/*上鎖*/}unlock(w){if(等W的隊列不空){

移出等W的隊列的首元素；將該進(jìn)程入就緒隊列；將該進(jìn)程登記為“就緒”狀態(tài)；}w=0;/*開鎖*/}lock(w)unlock(w)4.5.2信號燈和P、V操作1.信號燈的概念P、V操作是荷蘭科學(xué)家E.W.Dijkstra在1965年提出的一種解決同步、互斥問題的更通用的方法，并在THE操作系統(tǒng)中得以實現(xiàn)。P是荷蘭語發(fā)信號的開頭字母，V是等待的開頭字母。信號燈是一個確定的二元組（s,q），s為信號燈的值,是整型變量；q是指向PCB的隊列。4.5.2信號燈和P、V操作1.信號燈的概念信號量的值s與相應(yīng)資源的使用狀態(tài)有關(guān)。（1）當(dāng)它的值>0時，它表示可用資源的數(shù)量；（2）當(dāng)它的值<0時，其絕對值表示等待使用該資源的進(jìn)程個數(shù)，即在該信號量隊列上排隊的PCB的個數(shù)。（3）當(dāng)它的值＝0時，無可用資源，同時也無等待使用該資源的進(jìn)程信號量的一般數(shù)據(jù)結(jié)構(gòu)及PCB隊列如圖

數(shù)值（-3）指針PCB1PCB2PCB3信號量的值s與相應(yīng)資源的使用狀態(tài)有關(guān)。數(shù)值（-3）PCB1信號燈的值只能通過p、v操作來改變。其可能的取值范圍是，負(fù)數(shù)值、零、正數(shù)值。信號燈的是操作系統(tǒng)中實現(xiàn)進(jìn)程見同步和通信的一種常用工具。

信號燈的值只能通過p、v操作來改變。其可能的取值范圍是，負(fù)數(shù)2.p、v操作

設(shè)信號量為S，對S的P操作記為P(S)，對它的V操作記為V(S)。P、V操作的含義是：

P(S)操作順序執(zhí)行下述動作：1）

S=S-12）

S>=0說明當(dāng)前進(jìn)程q有資源可執(zhí)行；

3)S<0說明無資源，則當(dāng)前進(jìn)程掛起或封鎖，將該進(jìn)程插入排隊到該信號量等待隊列的隊尾，并放棄處理機(jī)，進(jìn)行等待（直到其它進(jìn)程在S上執(zhí)行V操作，把資源釋放出來為止）。

2.p、v操作設(shè)信號量為S，對S的P操作記為P(S)V(S)操作順序執(zhí)行下述動作：1）S=S+1；2）如果S>0，則該進(jìn)程繼續(xù)運行；3)

如果S<=0，則釋放信號隊列上的第一個PCB（即信號量指針?biāo)赶虻腜CB）所對應(yīng)的進(jìn)程（把阻塞態(tài)改為就緒態(tài)），執(zhí)行V操作的進(jìn)程繼續(xù)運行。V(S)操作順序執(zhí)行下述動作：4.6進(jìn)程互斥與同步的實現(xiàn)4.6.1用上鎖原語和開鎖原語實現(xiàn)進(jìn)程互斥

上鎖原語進(jìn)入臨界區(qū)csa開鎖原語上鎖原語進(jìn)入臨界區(qū)csb開鎖原語4.6進(jìn)程互斥與同步的實現(xiàn)上鎖原語進(jìn)入臨界區(qū)csa開鎖原語main(){intw=0;cobeginppa();ppb();coend}

ppa(){……lock(w);csa;/*臨界區(qū)*/unlock(w);……}

ppb(){……lock(w);csa;/*臨界區(qū)*/unlock(w);……}main()ppb()4.6.2用信號燈實現(xiàn)進(jìn)程互斥

main(){intmutex=1;/*互斥作用*/cobeginpa();pb();coend}pa(){……;p(mutex)；

csa；/*臨界段*/v(mutex)；

……;}pb(){……;p(mutex)；

csb；/*臨界段*/v(mutex)；

……;

}4.6.2用信號燈實現(xiàn)進(jìn)程互斥main()pb4.6.3進(jìn)程同步的實現(xiàn)

同步的概念所謂同步，就是并發(fā)進(jìn)程在一些關(guān)鍵點上可能需要互相等待與互通消息，這種相互制約的等待與互通消息稱為進(jìn)程同步。

4.6.3進(jìn)程同步的實現(xiàn)同步的概念同步的例子SPOOLing系統(tǒng)中的輸入功能可以由兩個進(jìn)程A和B完成，進(jìn)程A負(fù)責(zé)從讀卡機(jī)上把卡片上的信息讀到一個緩沖區(qū)中，進(jìn)程B負(fù)責(zé)把該緩沖區(qū)中的信息進(jìn)行加工并寫到外存輸入井中。要實現(xiàn)兩者的協(xié)同工作，兩個進(jìn)程必須滿足如下的制約關(guān)系：同步的例子SPOOLing系統(tǒng)中的輸入功能可以由兩個進(jìn)程A只有當(dāng)緩沖區(qū)的內(nèi)容取空時，進(jìn)程A才能向其中寫入新信息；只有當(dāng)緩沖區(qū)寫滿時，進(jìn)程B才能從中取出內(nèi)容作進(jìn)一步加工和轉(zhuǎn)送工作?？梢?，在緩沖區(qū)內(nèi)容區(qū)空時，進(jìn)程B不應(yīng)該繼續(xù)運行，需要等待進(jìn)程A向其中送入新的信息；反之，當(dāng)緩沖區(qū)中的信息尚未取走時，進(jìn)程A應(yīng)等待，防止把原有的信息沖掉，造成丟失信息的結(jié)果。進(jìn)程A和進(jìn)程B就是一種同步關(guān)系。只有當(dāng)緩沖區(qū)的內(nèi)容取空時，進(jìn)程A才能向其中寫入新信息；只有當(dāng)用信號燈實現(xiàn)進(jìn)程同步信號燈可以解決進(jìn)程的同步問題。一般同步問題可以分為兩類：一類是保證一組合作進(jìn)程按邏輯需要所確定的執(zhí)行次序；另一類是保證共享緩沖區(qū)（或共享數(shù)據(jù)）的合作進(jìn)程的同步。

用信號燈實現(xiàn)進(jìn)程同步main(){ints1=0;/*表示有無化驗單*/ ints2=0;/*表示有無化驗結(jié)果*/cobeginlabora();diagnosis();coend}

labora(){while(化驗工作未完成){p(s1);/*詢問有無化驗單，若無則等*/

化驗工作；

v(s2);/*送出化驗結(jié)果*/}}diagnosis(){while(看病工作未完成){

看??；

v(s1);/*送出化驗單*/p(s2);/*等化驗結(jié)果*/diagnosis;/*診斷*/}}main()化驗工作；（一）合作進(jìn)程的執(zhí)行次序main(){intsb=0；/*表示Pb進(jìn)程能否開始執(zhí)行*/intsc=0；/*表示Pc進(jìn)程能否開始執(zhí)行*/cobeginpa()；

pb()；

pc()；

coend}pa(){……;v(sb);v(sc);}pb(){p(sb)；

……;}pc(){p(sc)；

……;}sfpbpcpa（一）合作進(jìn)程的執(zhí)行次序main()pa()sfpb（二）

共享緩沖區(qū)的合作進(jìn)程的同步

main(){intsa=0;/*表示buf中有無信息*/intsb=1;/*表示buf中有無空位置*/cobegincp();iop();coend}cp(){while(計算未完成){

得到一個計算結(jié)果；

p(sb)；將數(shù)送到緩沖區(qū)中；

v(sa)；

}}iop(){while(打印工作未完成)；

{p(sa);

從緩沖區(qū)中取一數(shù)；

v(sb);

從打印機(jī)上輸出；｝

}cpiopbuf（二）共享緩沖區(qū)的合作進(jìn)程的同步main()p(s4.6.4生產(chǎn)者-消費者問題

（producer-consumerproblem）生產(chǎn)者--消費者問題表述如下：有n個生產(chǎn)者和m個消費者，連接在一個有k個單位緩沖區(qū)的有界緩沖上，故又叫有界緩沖問題。其中，pi和cj都是并發(fā)進(jìn)程，只要緩沖區(qū)未滿，生產(chǎn)者pi生產(chǎn)的產(chǎn)品就可投入緩沖區(qū)；類似地，只要緩沖區(qū)不空，消費者進(jìn)程cj就可從緩沖區(qū)取走并消耗產(chǎn)品。4.6.4生產(chǎn)者-消費者問題

（producer-consu可以用程序把生產(chǎn)者-消費者問題的算法描述如下：p1p2…pnc1c2…cmK個可以用程序把生產(chǎn)者-消費者問題的算法描述如下：p1c1K個main(){intfull=0;/*滿緩沖區(qū)的數(shù)目*/intempty=n;/*空緩沖區(qū)的數(shù)目*/intmutex=1;/*互斥作用*/cobeginproducer();consumer();coend}producer(){while(生產(chǎn)未完成){

……;

生產(chǎn)一個產(chǎn)品；

p(empty)；

p(mutex)；送一個產(chǎn)品到有界緩沖區(qū)中；

v(mutex)v(full)；

}}consumer(){while(還要繼續(xù)消費)；

{p(full);p(mutex)；從有界緩沖區(qū)中取產(chǎn)品；

v(mutex)；

v(empty);

消費一個產(chǎn)品；

……;

｝

}main()p(empty)；哲學(xué)家吃通心面問題下面再來討論使用信號量和P、V操作解決操作系統(tǒng)經(jīng)典的五個哲學(xué)家吃通心面問題（Dijkstra，1965）。有五個哲學(xué)家圍坐在一圓桌旁，桌子中央有一盤通心面，每人面前有一只空盤子，每兩人之間放一把叉子。每個哲學(xué)家思考、饑餓、然后，欲吃通心面。為了吃面，每個哲學(xué)家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。哲學(xué)家吃通心面問題下面再來討論使用信號量和P、V操作解決操五個哲學(xué)家吃通心面問題五個哲學(xué)家吃通心面問題在這道經(jīng)典題目中，每一把叉子都是必須互斥使用的，因此，應(yīng)為每把叉子設(shè)置一個互斥信號量Si(i=0,1,2,3,4)，初值均為1。當(dāng)一個哲學(xué)家吃通心面之前必須獲得自己左邊和右邊的兩把叉子，即執(zhí)行兩個P操作，吃完通心面后必須放下叉子，即執(zhí)行兩個V操作。程序如下：在這道經(jīng)典題目中，每一把叉子都是必須互斥使用的，因此，應(yīng)為每main(){intfork[0...4]={1,1,1,1,1,1};cobeginp1;p2;p3;p4;p5;coend}processPi/*i=0,1,2,3,4{while(){

思考;P(fork[i]);P(fork[i+1]mod5);

吃通心面;V(fork[i]);V(fork[i+1]mod5);}}main()processPi/*i=0,1,2,3,4上述解法中，如果五個哲學(xué)家先執(zhí)行P(fork[i])，再執(zhí)行P(fork[i+1]mod5)的話，就有可能出現(xiàn)每個哲學(xué)家舉起左邊一把叉子，卻又在永遠(yuǎn)等待相鄰哲學(xué)家手中的叉子的情況。有若干種辦法可避免這類死鎖：(1)至多允許四個哲學(xué)家同時吃。(2)奇數(shù)號先取左手邊的叉子，然后再取右手邊的叉子；偶數(shù)號先取右手邊的叉子，然后，再取左手邊的叉子。(3)每個哲學(xué)家取到手邊的兩把叉子才吃，否則，一把叉子也不取。上述解法中，如果五個哲學(xué)家先執(zhí)行P(fork[i])，再執(zhí)行讀者與寫者問題

（reader-writerproblem）讀者與寫者問題（Courtois，1971）也是一個經(jīng)典的并發(fā)程序設(shè)計問題。有兩組并發(fā)進(jìn)程：讀者和寫者，共享一個文件F，要求：（1）允許多個讀者可同時對文件執(zhí)行讀操作；（2）只允許一個寫者往文件中寫信息；（3）任一寫者在完成寫操作之前不允許其他讀者或?qū)懻吖ぷ鳎唬?）寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出。讀者與寫者問題

（reader-writerproblemReader_i(){P(mutex);rc=rc+1;ifrc=1thenP(W)；

V(mutex);

讀文件；

P(mutex);rc=rc-1;ifrc=0thenV(W)；V(mutex);}Writer_j(){P(W);寫文件;V(W);}其中：i=1,2,…,n;j=1,2,…,m;Reader_i()Writer_j()其中：main(){intW=1，mutex=1;intrc=0;/*讀進(jìn)程計數(shù)*/cobeginReader_i;Writer_j;coend}main()4.7進(jìn)程通信

４.7.１進(jìn)程通信的概念

并發(fā)進(jìn)程之間的交互必須滿足兩個基本要求：同步和通信。進(jìn)程競爭資源時要實施互斥，互斥是一種特殊的同步，實質(zhì)上需要解決好進(jìn)程同步問題，進(jìn)程同步是一種進(jìn)程通信，通過修改信號量，進(jìn)程之間可建立起聯(lián)系，相互協(xié)調(diào)運行和協(xié)同工作。但是信號量與PV操作只能傳遞信號，沒有傳遞數(shù)據(jù)的能力。

4.7進(jìn)程通信４.7.１進(jìn)程通信的概念有些情況下進(jìn)程之間交換的信息量雖很少，例如，僅僅交換某個狀態(tài)信息，但很多情況下進(jìn)程之間需要交換大批數(shù)據(jù)，例如，傳送一批信息或整個文件，這可以通過一種新的通信機(jī)制來完成，進(jìn)程之間互相交換信息的工作稱之為進(jìn)程通信IPC（InterProcessCommunication）。有些情況下進(jìn)程之間交換的信息量雖很少，例如，僅僅交換某個狀態(tài)進(jìn)程通信是指進(jìn)程之間可直接以較高的效率傳達(dá)較多數(shù)據(jù)的信息交換方式。這種方式中采用的是通信機(jī)構(gòu)，如消息發(fā)送和接收、郵箱結(jié)構(gòu)等，在進(jìn)程通信時往往以消息形式傳遞信息。消息是指進(jìn)程之間相互傳送的賴以發(fā)生交互作用的有結(jié)構(gòu)的數(shù)據(jù)。操作系統(tǒng)原理-第4章-并發(fā)處理ppt課件進(jìn)程間通信的方式很多，大致分為四類：1、信號（signal）通信機(jī)制；2、信號量及其原語操作（PV、讀寫鎖、管程）控制的共享存儲區(qū)（sharedmemory）通信機(jī)制；3、管道（pipeline）提供的共享文件（sharedfile）通信機(jī)制；4、信箱和發(fā)信/收信原語的消息傳遞（messagepassing）通信機(jī)制。進(jìn)程間通信的方式很多，大致分為四類：其中前兩種通信方式由于交換的信息量少且效率低下，故稱為低級通信機(jī)制，相應(yīng)地可把發(fā)信號/收信號及PV之類操作稱為低級通信原語，僅適用于集中式操作系統(tǒng)。消息傳遞機(jī)制屬于高級通信機(jī)制，共享文件通信機(jī)制是消息傳遞機(jī)制的變種，這兩種通信機(jī)制，既適用于集中式操作系統(tǒng)，又適用于分布式操作系統(tǒng)。其中前兩種通信方式由于交換的信息量少且效率低下，故稱為低級通信號通信機(jī)制信號（signal）機(jī)制又稱軟中斷，是一種進(jìn)程之間進(jìn)行通信的簡單通信機(jī)制，通過發(fā)送一個指定信號來通知進(jìn)程某個異常事件發(fā)生，并進(jìn)行適當(dāng)處理。進(jìn)程運行時不時地檢查有無軟中斷信號到達(dá)，如果有，則中斷原來正在執(zhí)行的程序，轉(zhuǎn)向該信號的處理程序?qū)υ撌录M(jìn)行處理，處理結(jié)束后便可返回原程序的斷點執(zhí)行。信號通信機(jī)制信號（signal）機(jī)制又稱軟中斷，是一種進(jìn)程之一般地可以分成OS標(biāo)準(zhǔn)信號和用戶進(jìn)程自定義信號，這種機(jī)制類似硬件中斷，不分優(yōu)先級，簡單有效，但不能傳送數(shù)據(jù)。信號不但能從內(nèi)核發(fā)給一個進(jìn)程，也能由一個進(jìn)程發(fā)給同組的另一個進(jìn)程或多個進(jìn)程。一般地可以分成OS標(biāo)準(zhǔn)信號和用戶進(jìn)程自定義信號，這種機(jī)制類舉例：當(dāng)系統(tǒng)正在運行一個耗時的前臺程序，如若已發(fā)現(xiàn)有錯誤，并斷定該程序要失敗，為了節(jié)省時間，用戶可以按軟中斷鍵（一般為ctrl+alt+del）停止程序的執(zhí)行，這一過程中就用到了信號（signal）。系統(tǒng)具體的操作為：響應(yīng)鍵盤輸入的中斷處理程序向發(fā)來中斷信號的終端進(jìn)程發(fā)一個信號，進(jìn)程收到信號后，完成相關(guān)處理，然后執(zhí)行終止。舉例：當(dāng)系統(tǒng)正在運行一個耗時的前臺程序，如若已發(fā)現(xiàn)有錯誤，并共享文件通信機(jī)制管道（pipeline）是連接讀寫進(jìn)程的一個特殊文件，允許進(jìn)程按先進(jìn)先出方式傳送數(shù)據(jù)，也能使進(jìn)程同步執(zhí)行操作。如圖所示，發(fā)送進(jìn)程視管道文件為輸出文件，以字符流形式把大量數(shù)據(jù)送入管道；接收進(jìn)程將管道文件視為輸入文件，從管道中接收數(shù)據(jù)，所以，也叫管道通信。由于方便有效，能在進(jìn)程間作大量信息的通信，目前已被引入到許多操作系統(tǒng)中。共享文件通信機(jī)制管道和消息隊列的主要區(qū)別在于：管道中的消息是無界的，它存于外存；消息隊列是位于內(nèi)存。共享文件ProcessA寫ProcessB

讀管道和消息隊列的主要區(qū)別在于：管道中的消息是無界的，它存于外４.7.２消息緩沖通信消息傳遞方式分為直接通信方式和間接通訊方式兩種，而直接通訊方式的消息緩沖為基本的進(jìn)程通訊方式。發(fā)送進(jìn)程直接將消息掛在接收進(jìn)程的消息緩沖隊列上，接收進(jìn)程從消息緩沖隊列中得到消息?；镜挠邪l(fā)送（send）消息和讀取（re