【正文】 產(chǎn)品； V(m)； V(a)。 消費產(chǎn)品； 由以上分析，設公用信號量 mutex保證生產(chǎn)者進程和消費者進程之間的互斥，設信號量 avail為生產(chǎn)者進程的私用信號量，信號量 full為消費者進程的私用信號量。信號量 avail表示有界緩沖區(qū)中的空單元數(shù)，初值為 n；信號量 full表示有界緩沖區(qū)中非空單元數(shù)，初值為 0。信號量 mutex表示可用有界緩沖區(qū)的個數(shù)，初值為 1。從而有： deposit(data): begin Ｐ（ avail） Ｐ（ mutex） 送數(shù)據(jù)入緩沖區(qū)某單元 Ｖ（ full） Ｖ（ mutex） end remove(data): begin Ｐ（ full） Ｐ（ mutex） 取緩沖區(qū)中某單元數(shù)據(jù) Ｖ（ avail） Ｖ（ mutex） end 在上例中，由于一個過程中包含有幾個公用、私用信號量，因此，Ｐ、Ｖ原語的操作次序要非常小心。一般說來，由于Ｖ原語是釋放資源的，所以可以以任意次序出現(xiàn)。但Ｐ原語則不然，如果次序混亂，將會造成進程之間的死鎖。關(guān)于死鎖，將在 中介紹。 進 程 通 信 本節(jié)介紹進程間互相傳遞信息的方法和原理。通信（ munication）意味著在進程間傳送數(shù)據(jù)。操作系統(tǒng)可以被看作是各種進程組成的。這些進程都具有各自的獨立功能，且大多數(shù)被外部需要而啟動執(zhí)行。一般來說，進程間的通信根據(jù)通信內(nèi)容可以劃分為二種：即控制信息的傳送與大批量數(shù)據(jù)傳送。有時，也把進程間控制信息的交換稱為低級通信，而把進程間大批量數(shù)據(jù)的交換稱為高級通信。上面幾節(jié)中所介紹的進程間同步或互斥，也是使用鎖或信號量進行通信來實現(xiàn)的。低級通信一般只傳送一個或幾個字節(jié)的信息，以達到控制進程執(zhí)行速度的作用。高級通信要傳送大量數(shù)據(jù)。高級通信的目的不是為了控制進程的執(zhí)行速度，而是為了交換信息。 進程的通信方式 在單機系統(tǒng)中，進程間通信可分為 4種形式： (1) 主從式； (2) 會話式； (3) 消息或郵箱機制； (4) 共享存儲區(qū)方式。 主從式通信系統(tǒng)的主要特點是： ① 主進程可自由地使用從進程的資源或數(shù)據(jù)； ② 從進程的動作受主進程的控制； ③ 主進程和從進程的關(guān)系是固定的。 主從式通信系統(tǒng)的典型例子是終端控制進程和終端進程。 會話方式中，通信進程雙方可分別稱為使用進程和服務進程。其中，使用進程調(diào)用服務進程提供的服務。它們具有如下特點： ① 使用進程在使用服務進程所提供的服務之前，必須得到服務進程的許可； ② 服務進程根據(jù)使用進程的要求提供服務，但對所提供服務的控制由服務進程自身完成。 ③ 使用進程和服務進程在通信時有固定連接關(guān)系。 用戶進程與磁盤管理進程之間的通信是會話系統(tǒng)的一個例子。各用戶進程向磁盤管理進程提出使用要求并得到許可之后，才可以使用相應的存儲區(qū)。而且，由磁盤管理進程自身完成對磁盤存儲區(qū)的管理和控制。另外，用戶進程與磁盤管理進程之間，只有在用戶進程要求使用磁盤存儲區(qū)時才有通信關(guān)系。 消息或郵箱機制則無論接收進程是否已準備好接收消息，發(fā)送進程都將把所要發(fā)送的消息送入緩沖區(qū)或郵箱。消息的一般形式為４個部分組成。即：發(fā)送進程名、接收進程名、數(shù)據(jù)和有關(guān)數(shù)據(jù)的操作。 消息或郵箱機制的特點是： ① 只要存在空緩沖區(qū)或郵箱，發(fā)送進程就可以發(fā)送消息。 ② 與會話系統(tǒng)不同，發(fā)送進程和接收進程之間無直接連接關(guān)系，接收進程可能在收到某個發(fā)送進程發(fā)來的消息之后，又轉(zhuǎn)去接收另一個發(fā)送進程發(fā)來的消息。 消息的組成圖 緩沖區(qū)或郵箱通信結(jié)構(gòu)圖 ③ 發(fā)送進程和接收進程之間存在緩沖區(qū)或郵箱用來存放被傳送消息。 與前面三種方式不同，共享存儲區(qū)方式不要求數(shù)據(jù)移動。兩個需要互相交換信息的進程通過對同一共享數(shù)據(jù)區(qū)（ shared memory）的操作來達到互相通信的目的。這個共享數(shù)據(jù)區(qū)是每個互相通信進程的一個組成部分。 以上幾種通信方式都可用于大量數(shù)據(jù)傳送，而且，由于其通信方式不同，需要使用不同的控制方式來達到通信進程之間同步或互斥的目的。 下面，首先介紹進程通信中較為常用的消息與郵箱機制，然后再介紹幾個實際例子。 消息緩沖機制 發(fā)送進程和接收進程采用消息緩沖機制進行數(shù)據(jù)傳送時，發(fā)送進程在發(fā)送消息前，先在自己的內(nèi)存空間設置一個發(fā)送區(qū)，把欲發(fā)送的消息填入其中，然后再用發(fā)送過程將其發(fā)送出去。接收進程則在接收消息之前，在自己的內(nèi)存空間內(nèi)設置相應的接收區(qū)，然后用接收過程接收消息。由于消息緩沖機制中所使用的緩沖區(qū)為公用緩沖區(qū)，使用消息緩沖機制傳送數(shù)據(jù)時，兩通信進程必須滿足如下條件： ① 在發(fā)送進程把消息寫入緩沖區(qū)和把緩沖區(qū)掛入消息隊列時，應禁止其他進程對該緩沖區(qū)消息隊列的訪問。否則，將引起消息隊列的混亂。同理，當接收進程正從消息隊列中取消息緩沖時，也應禁止其他進程對該隊列的訪問。 ② 當緩沖區(qū)中無消息存在時，接收進程不能接收到任何消息。 至于發(fā)送進程是否可以發(fā)送消息，則由發(fā)送進程是否申請到緩沖區(qū)決定。 設公用信號量 mutex 為控制對緩沖區(qū)訪問的互斥信號量，其初值為 1 。設 SM為接收進程的私用信號量，表示等待接收的消息個數(shù)，其初值為 0 。設發(fā)送進程調(diào)用過程 send(m)將消息 m 送往緩沖區(qū)，接收進程調(diào)用過程 Receive(m)將消息 m從緩沖區(qū)讀往自己的數(shù)據(jù)區(qū)，則 Send(m)和 Receive(n)可分別描述為： Send(m): begin 向系統(tǒng)申請一個消息緩沖區(qū) Ｐ（ mutex） 將發(fā)送區(qū)消息 m送入新申請的消息緩沖區(qū) 把消息緩沖區(qū)掛入接收進程的消息隊列 Ｖ（ mutex） Ｖ（ SM） end Receive(n): begin Ｐ（ SM） Ｐ（ mutex） 摘下消息隊列中的消息 n 將消息 n從緩沖區(qū)復制到接收區(qū) 釋放緩沖區(qū) Ｖ（ mutex） end 一般來說，盡管系統(tǒng)中可利用的緩沖區(qū)總數(shù)是已知的，但由于消息隊列是按接收進程排列，因而，在同一時間內(nèi)，系統(tǒng)中存在著多個消息隊列；且這些隊列的長度是不固定的。因此，發(fā)送進程無法在Send過程用Ｐ操作判斷信號量 SM。 郵箱通信 郵箱通信就是由發(fā)送進程申請建立一與接收進程鏈接的郵箱。發(fā)送進程把消息送往郵箱，接收進程從郵箱中取出消息，從而完成進程間信息交換。設置郵箱的最大好處就是發(fā)送進程和接收進程之間沒有處理時間上的限制。一個郵箱可考慮成發(fā)送進程與接收進程之間的大小固定的私有數(shù)據(jù)結(jié)構(gòu)，它不像緩沖區(qū)那樣被系統(tǒng)內(nèi)所有進程共享。郵箱由郵箱頭和郵箱體組成。其中郵箱頭描述郵箱名稱、郵箱大小、郵箱方向以及擁有該郵箱的進程名等。郵箱體主要用來存放消息。 郵箱通信結(jié)構(gòu)圖 對于只有一發(fā)送進程和一接收進程使用的郵箱，則進程間通信應滿足如下條件： ① 發(fā)送進程發(fā)送消息時，郵箱中至少要有一個空格能存放該消息。 ② 接收進程接收消息時，郵箱中至少要有一個消息存在。 設發(fā)送進程調(diào)用過程 deposit(m)將消息發(fā)送到郵箱，接收進程調(diào)用過程 remove(m)將消息 m 從郵箱中取出。另外，為了記錄郵箱中空格個數(shù)和消息個數(shù)，信號量 fromnum 為發(fā)送進程的私用信號量，信號量 mesnum為接收進程的私用信號量。 fromnum 的初值為信箱的空格數(shù) n， mesnum 的初值為 0。則 deposit(m)和 remove(m)可描述如下： deposit(m): begin local x Ｐ（ fromnum） 選擇空格 x 將消息 m放入空格 x中 置格 x的標志為滿 Ｖ（ mesnum） end remove(m): begin local x Ｐ（ mesnum） 選擇滿格 x 把滿格 x中的消息取出放 m中 置格 x標志為空 Ｖ（ fromnum） end 顯然，調(diào)用過程 deposit(m)的進程與調(diào)用過程remove(m)的進程之間存在著同步制約關(guān)系而不是互斥制約關(guān)系。 另外，在許多時侯，存在著多個發(fā)送進程和多個接收進程共享郵箱的情況。這時需要對過程deposit(m)和 remove(m)作相應的改動。 死 鎖 問 題 死鎖的概念 1. 死鎖的定義 各進程在使用系統(tǒng)資源時，應注意系統(tǒng)產(chǎn)生死鎖問題。所謂死鎖，是指各并發(fā)進程彼此互相等待對方所擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進程不能繼續(xù)向前推進的狀態(tài)。圖示是兩個進程發(fā)生死鎖時的例子。 下面以生產(chǎn)者 /消費者問題為例來進一步看看死鎖的概念。設生產(chǎn)者進程已獲得對緩沖區(qū)隊列的操作權(quán)，生產(chǎn)者進程進一步要求對緩沖區(qū)內(nèi)的某一空緩沖區(qū)進行置入消息操作。然而，設此時緩沖隊列內(nèi)所有緩沖區(qū)都是滿的，即只有消費者進程才能對它們進行取消息操作。因此，生產(chǎn)者進程進入等待狀態(tài)。反過來，消費者進程擁有對各緩沖區(qū)操作的操作權(quán)，為了對各緩沖區(qū)進行操作，它又要申請對緩沖隊列操作的操作權(quán)。由于對緩沖隊列的操作權(quán)被生產(chǎn)者進程掌握，且生產(chǎn)者進程不會自動釋放它，從而消費者進程也只能進入等待狀態(tài)而陷入死鎖。 一般地，可以把死鎖描述為：有并發(fā)進程 P1，P2， … ， Pn，它們共享資源 R1， R2， … ， Rm（ n0， m0， n=m）。其中，每個 Pi（ 1≤i≤n）擁有資源 Rj（ 1 ≤j ≤m），直到不再有剩余資源。同時，各 Pi又在不釋放 Rj 的前提下要求得到 Rk（ k≠j， 1 ≤k≤m），從而造成資源的互相占有和互相等待。在沒有外力驅(qū)動的情況下，該組并發(fā)進程停止往前推進，陷入永久等待狀態(tài)。 2. 死鎖的起因 死鎖的起因是并發(fā)進程的資源競爭。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的資源個數(shù)少于并發(fā)進程所要求的該類資源數(shù)。顯然，由于資源的有限性，不可能為所有要求資源的進程無限制地提供資源。但是，可以采用適當?shù)馁Y源分配算法，以達到消除死鎖的目的。為此，先看看產(chǎn)生死鎖的必要條件。 3. 產(chǎn)生死鎖的必要條件 (1) 互斥條件。并發(fā)進程所要求和占有的資源是不能同時被兩個以上進程使用或操作的，進程對它所需要的資源進行排他性控制。 (2) 不剝奪條件。進程所獲得的資源在未使用完畢之前，不能被其他進程強行剝奪，而只能由獲得該資源的進程自己釋放。 (3) 部分分配。進程每次申請它所需要的一部分資源，在等待新資源的同時繼續(xù)占用已分配到的資源。 (4) 環(huán)路條件。存在一種進程循環(huán)鏈，鏈中每一個進程已獲得的資源同時被下一個進程所請求。 顯然，只要使上述 4個必要條件中的某一個不滿足，則死鎖就可以排除。 死鎖的排除方法 解決死鎖的方法一般可分為預防、避免、檢測與恢復等三種。預防是采用某種策略，限制并發(fā)進程對資源的請求，從而使得死鎖的必要條件在系統(tǒng)執(zhí)行的任何時間都不滿足。避免是指系統(tǒng)在分配資源時，根據(jù)資源的使用情況提前做出預測，從而避免死鎖的發(fā)生。死鎖檢測與恢復是指系統(tǒng)設有專門的機構(gòu)，當死鎖發(fā)生時，該機構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進程從死鎖狀態(tài)中恢復出來。 通過預防和避免的手段達到排除死鎖的目的是一件十分困難的事。死鎖的檢測和恢復則不必花費多少執(zhí)行時間就能發(fā)現(xiàn)死鎖和從死鎖中恢復出來。因此，在實際操作系統(tǒng)中大都使用檢測與恢復法排除死鎖。 1. 死鎖預防 一種方法是打破資源的互斥和不可剝奪這兩個條件，例如允許進程同時訪問某些資源等。這種方法不能解決訪問那些不允許被同時訪問的資源時所帶來的死鎖問題。另一種方法則是打破資源的部分分配這個死鎖產(chǎn)生的必要條件。即預先分配各并發(fā)進程所需要的全部資源。如某個進程的資源得不到滿足時，則安排一定的等待次序讓其他進程釋放資源。但是，這種方法也有如下缺點： (1) 在許多情況下，一個進程在執(zhí)行之前不可能提出它所需要的全部資源。 (2) 無論所需資源何時用到，一個進程只有在所有要求資源都得到滿足之后才開始執(zhí)行。 (3) 對于那些不經(jīng)常使用的資源，進程在生存過程期間一直占用它們是一種極大的浪費。 (4) 降低了進程的并發(fā)性。 另外一種死鎖的預防方法是打破死鎖的環(huán)路條件。即把資源分類按順序排列，使進程在申請、保持資源時不形成環(huán)路。如有 m種資源，則列出 R1＜ R2＜ … ＜ Rm。若進程 Pi保持了資源 Ri，則它只能申請比 Ri級別更高的資源 Rj（ Ri ＜ Rj ）。釋放資源時必須是 Rj先于 Ri被釋放，從而避免環(huán)路的產(chǎn)生。這種方法的缺點是限制了進程對資源的請求，而且對資源的分類編序也耗去一定的系統(tǒng)開銷。 2 死鎖的避免 Avoidance 在分配資源時判斷是否會出現(xiàn)死鎖，如不會死鎖，