計(jì)算機(jī)操作系統(tǒng)第3章-資料下載頁

　　

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