【正文】 Buf← Buf UntilBuf=空 計(jì)算 得到計(jì)算結(jié)果 Buf ← 計(jì)算結(jié)果 Goto A PB: ： : B: local Pri Repeat Pri ← Buf UntilPri ≠ 空 打印 Buf中的數(shù)據(jù) 清除 Buf中的數(shù)據(jù) Goto B 這里，如果假定進(jìn)程 PC和 PP對公用緩沖區(qū) Buf 已采取了互斥措施。 這里異步環(huán)境主要指各并發(fā)進(jìn)程的執(zhí)行起始時間的隨機(jī)性和執(zhí)行速度的獨(dú)立性。 (2) 初始化 Bufempty=true， Buffull=false 。與私用信號量相對應(yīng)，稱互斥時使用的信號量為公用信號量。 PA為發(fā)送進(jìn)程， PB為接收進(jìn)程。把系統(tǒng)中使用某一類資源的進(jìn)程稱為該資源的消費(fèi)者，而把釋放同類資源的進(jìn)程稱為該資源的生產(chǎn)者。 消費(fèi)者進(jìn)程： P(b)； 從滿格取出產(chǎn)品； 消費(fèi)產(chǎn)品； V(a)。 消費(fèi)產(chǎn)品； 由以上分析，設(shè)公用信號量 mutex保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥，設(shè)信號量 avail為生產(chǎn)者進(jìn)程的私用信號量，信號量 full為消費(fèi)者進(jìn)程的私用信號量。通信（ munication）意味著在進(jìn)程間傳送數(shù)據(jù)。高級通信的目的不是為了控制進(jìn)程的執(zhí)行速度，而是為了交換信息。 用戶進(jìn)程與磁盤管理進(jìn)程之間的通信是會話系統(tǒng)的一個例子。 ② 與會話系統(tǒng)不同，發(fā)送進(jìn)程和接收進(jìn)程之間無直接連接關(guān)系，接收進(jìn)程可能在收到某個發(fā)送進(jìn)程發(fā)來的消息之后，又轉(zhuǎn)去接收另一個發(fā)送進(jìn)程發(fā)來的消息。接收進(jìn)程則在接收消息之前，在自己的內(nèi)存空間內(nèi)設(shè)置相應(yīng)的接收區(qū)，然后用接收過程接收消息。設(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ū) Ｐ（ mutex） 將發(fā)送區(qū)消息 m送入新申請的消息緩沖區(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)程排列，因而，在同一時間內(nèi)，系統(tǒng)中存在著多個消息隊(duì)列；且這些隊(duì)列的長度是不固定的。郵箱體主要用來存放消息。這時需要對過程deposit(m)和 remove(m)作相應(yīng)的改動。因此，生產(chǎn)者進(jìn)程進(jìn)入等待狀態(tài)。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的資源個數(shù)少于并發(fā)進(jìn)程所要求的該類資源數(shù)。 (3) 部分分配。死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時，該機(jī)構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來。如某個進(jìn)程的資源得不到滿足時，則安排一定的等待次序讓其他進(jìn)程釋放資源。若進(jìn)程 Pi保持了資源 Ri，則它只能申請比 Ri級別更高的資源 Rj（ Ri ＜ Rj ）。即把資源分類按順序排列，使進(jìn)程在申請、保持資源時不形成環(huán)路。另一種方法則是打破資源的部分分配這個死鎖產(chǎn)生的必要條件。預(yù)防是采用某種策略，限制并發(fā)進(jìn)程對資源的請求，從而使得死鎖的必要條件在系統(tǒng)執(zhí)行的任何時間都不滿足。 (2) 不剝奪條件。在沒有外力驅(qū)動的情況下，該組并發(fā)進(jìn)程停止往前推進(jìn)，陷入永久等待狀態(tài)。設(shè)生產(chǎn)者進(jìn)程已獲得對緩沖區(qū)隊(duì)列的操作權(quán)，生產(chǎn)者進(jìn)程進(jìn)一步要求對緩沖區(qū)內(nèi)的某一空緩沖區(qū)進(jìn)行置入消息操作。則 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è)公用信號量 mutex 為控制對緩沖區(qū)訪問的互斥信號量，其初值為 1 。 下面，首先介紹進(jìn)程通信中較為常用的消息與郵箱機(jī)制，然后再介紹幾個實(shí)際例子。即：發(fā)送進(jìn)程名、接收進(jìn)程名、數(shù)據(jù)和有關(guān)數(shù)據(jù)的操作。它們具有如下特點(diǎn)： ① 使用進(jìn)程在使用服務(wù)進(jìn)程所提供的服務(wù)之前，必須得到服務(wù)進(jìn)程的許可； ② 服務(wù)進(jìn)程根據(jù)使用進(jìn)程的要求提供服務(wù)，但對所提供服務(wù)的控制由服務(wù)進(jìn)程自身完成。低級通信一般只傳送一個或幾個字節(jié)的信息，以達(dá)到控制進(jìn)程執(zhí)行速度的作用。關(guān)于死鎖，將在 中介紹。 M=1；表示互斥空格區(qū)； 生產(chǎn)者進(jìn)程： 生產(chǎn)產(chǎn)品； P(a)； P(m)； 放入空的格； V(m)； V(b)。 生產(chǎn)者 消費(fèi)者問題圖 第一種實(shí)現(xiàn)： 設(shè) a=n表示空的產(chǎn)品格數(shù)； b=0表示滿的產(chǎn)品格數(shù)。 生產(chǎn)者 消費(fèi)者問題（ producerconsumer problems） 把并發(fā)進(jìn)程的同步和互斥問題一般化，可以得到一個抽象的一般模型，即生產(chǎn)者 消費(fèi)者問題。 PB: L: P(b) 計(jì)算； BUF 打印 V(a) Goto L。因此，稱該信號量為私用信號量（ Private Semaphvre）。如果對一個消息或事件賦以唯一的消息名，則可用過程 wait(消息名） 表示進(jìn)程等待合作進(jìn)程發(fā)來的消息，而用過程 signal（消息名） 表示向合作進(jìn)程發(fā)送消息。這與上節(jié)中講述的進(jìn)程互斥是不同的，進(jìn)程互斥時它們的執(zhí)行順序可以是任意的。 計(jì)算進(jìn)程和打印進(jìn)程共同使用同一緩沖區(qū) Buf。在一個進(jìn)程完成對臨界區(qū)的操作之后，它必須執(zhí)行Ｖ原語操作以釋放它所占用的臨界區(qū)。否則，如果多個進(jìn)程同時調(diào)用Ｐ操作或Ｖ操作的話，則有可能在Ｐ操作剛把sem1而未把對應(yīng)進(jìn)程送入等待隊(duì)列時，Ｖ操作開始執(zhí)行。一次Ｐ原語操作使得信號量 sem減 1，而一次Ｖ原語操作將使得信號量 sem加 1。 信號量的概念和下面所述的Ｐ、Ｖ原語是荷蘭科學(xué)家 。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。然而遺憾的是，這種可能性是非常小的。例如，循環(huán)測試鎖定位將損耗較多的 CPU計(jì)算時間。加鎖后的臨界區(qū)程序描述如下： lock(key ［Ｓ］ ) 〈 臨 界 區(qū) 〉 unlock(key ［Ｓ］ ) 設(shè) key ［Ｓ］ =1時表示類名為Ｓ的臨界區(qū)可用， key ［Ｓ］ =0時表示類名為Ｓ的臨界區(qū)不可用。因?yàn)檫@要求該組并發(fā)進(jìn)程中的每個進(jìn)程事先知道其他并發(fā)進(jìn)程與系統(tǒng)的動作，由用戶程序執(zhí)行開始的隨機(jī)性可知，這是不可能的。否則，由于某個并發(fā)進(jìn)程長期占有臨界區(qū)，其他進(jìn)程則因?yàn)椴荒苓M(jìn)入臨界區(qū)而進(jìn)入互相等待狀態(tài)。把一個過程作成純過程可便于多個進(jìn)程共享，但由于編制純過程必須對有關(guān)變量和工作區(qū)作相應(yīng)的處理，從而其執(zhí)行效率往往會受到一定的影響。 3. 什么是互斥 可以把互斥定義為：一組并發(fā)進(jìn)程中的一個或多個程序段，因共享某一公有資源而導(dǎo)致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行。上例中，以公用數(shù)據(jù)棧Ｓ劃分的臨界區(qū)集合是 {getspace,release}。然而，由下面的描述可以看到，在進(jìn)程并發(fā)執(zhí)行時，getspace或 release(ad)將有可能完不成所要求的功能。這里數(shù)據(jù)區(qū)被劃分大小相等的塊，每個塊中既可能放有數(shù)據(jù)，也有可能未放有數(shù)據(jù)。一般說來，即使在程序中所描述的一條語句，也是由多條執(zhí)行指令構(gòu)成的。由事件發(fā)生進(jìn)程喚醒時，事件發(fā)生進(jìn)程和被喚醒進(jìn)程之間是合作關(guān)系。然后將被阻塞進(jìn)程置“阻塞”狀態(tài)后插入等待隊(duì)列中，再轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行。 撤消原語首先檢查 PCB進(jìn)程鏈或進(jìn)程家族，尋找所要撤消的進(jìn)程是否存在。屬于某個家族的一個進(jìn)程可以繼承其父進(jìn)程所擁有的資源。然而，如果不加控制和管理地讓這些控制進(jìn)程狀態(tài)轉(zhuǎn)換及創(chuàng)建和撤消進(jìn)程的程序段并發(fā)執(zhí)行，則會使得其執(zhí)行結(jié)果失去封閉性和可再現(xiàn)性，從而達(dá)不到進(jìn)程控制的目的。 進(jìn)程狀態(tài)轉(zhuǎn)換圖 進(jìn) 程 控 制 進(jìn)程和處理機(jī)管理的一個重要任務(wù)是進(jìn)程控制。這樣做的好處是系統(tǒng)控制簡單，發(fā)現(xiàn)和喚醒相應(yīng)的進(jìn)程較為容易。 在單 CPU系統(tǒng)中，任一時刻處于執(zhí)行狀態(tài)的進(jìn)程只能有一個。 進(jìn)程狀態(tài)及其轉(zhuǎn)換 進(jìn)程狀態(tài) 一個進(jìn)程的生命期可以劃分為一組狀態(tài)，這些狀態(tài)刻劃了整個進(jìn)程。進(jìn)程上下文的層次概念也主要體現(xiàn)在動態(tài)部分中，即系統(tǒng)級上下文的動態(tài)部分可看成是一些數(shù)量變化的層次組成。用戶級上下文由進(jìn)程的用戶程序段部分編譯而成的用戶正文段、用戶數(shù)據(jù)、用戶棧等組成。具體地說，進(jìn)程上下文包括計(jì)算機(jī)系統(tǒng)中與執(zhí)行該進(jìn)程有關(guān)的各種寄存器的值、程序段在經(jīng)過編譯之后形成的機(jī)器指令代碼集（或稱正文段）、數(shù)據(jù)集及各種堆棧值和 PCB結(jié)構(gòu) (圖 )。通過對 PCB 的操作，給進(jìn)程分配資源、調(diào)度進(jìn)程執(zhí)行、釋放進(jìn)程所占有的各種資源；而完成進(jìn)程所要求功能的程序段的有關(guān)地址，以及程序段在進(jìn)程過程中因某種原因被停止執(zhí)行后的現(xiàn)場信息也都在 PCB 中。 ③ 共享程序段大小及起始地址。 根據(jù)操作系統(tǒng)的要求不同， PCB的內(nèi)容會有所不同。而數(shù)據(jù)結(jié)構(gòu)集是程序在執(zhí)行時必不可少的工作區(qū)和操作對象。 (3) 作業(yè)的概念主要用在批處理系統(tǒng)中。 作業(yè)和進(jìn)程的關(guān)系 作業(yè)是用戶需要計(jì)算機(jī)完成某項(xiàng)任務(wù)時要求計(jì)算機(jī)所作工作的集合。而進(jìn)程則強(qiáng)調(diào)執(zhí)行過程，它動態(tài)地被創(chuàng)建，并被調(diào)度執(zhí)行后消亡。 從上述討論可以看出，由于程序的順序性、靜態(tài)性以及孤立性，用程序段作為描述其執(zhí)行過程和共享資源的基本單位既增加操作系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的復(fù)雜性，也無法反映操作系統(tǒng)所應(yīng)該具有的程序段執(zhí)行的并發(fā)性、用戶隨機(jī)性，以及資源共享等特征。 s[top] ? blk。用getaddr(top) 從棧頂取出相應(yīng)的內(nèi)存塊的地址。 C P U 利用率＝ 3t／ 5t＝ 3／ 5＝ 60％ 輸入設(shè)備利用率＝ 3t／ 5t＝ 3／ 5＝ 60％ 輸出設(shè)備利用率＝ 3t／ 5t＝ 3／ 5＝ 60％ CPU時間片 進(jìn) 程 A 進(jìn) 程 B 進(jìn) 程 C t Ai Ac Ao Bi Bc Bo Ci Cc Co t t t t 輸入設(shè)備 輸出設(shè)備 CPU (2) 程序的并發(fā)執(zhí)行所帶來的影響 程序的并發(fā)執(zhí)行充分地利用了系統(tǒng)資源，從而提高了系統(tǒng)的處理能力，這是并發(fā)執(zhí)行好的一方面。程序的并行執(zhí)行是指一組程序按獨(dú)立的、異步的速度執(zhí)行。程序的并發(fā)執(zhí)行可進(jìn)一步分為兩種：第一種 是多道程序系統(tǒng)的程序執(zhí)行環(huán)境變化所引起的多道程序的并發(fā)執(zhí)行。 程序的順序執(zhí)行具有如下特點(diǎn)： (1) 順序性 程序順序執(zhí)行時，其執(zhí)行過程可看作一系列嚴(yán)格按程序規(guī)定的狀態(tài)轉(zhuǎn)移過程。 2. 多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化 多道程序執(zhí)行的系統(tǒng)環(huán)境具有下述三個特點(diǎn)： (1) 獨(dú)立性 每道程序都是邏輯上獨(dú)立的，它們之間不存在邏輯上的制約關(guān)系。例如語句： read (a) ； read (b) ； 它們既可以同時執(zhí)行，也可顛倒次序執(zhí)行。 P1， 2， … ，Pn也可以由同一程序段中的不同語句組成。但在一般情況下，系統(tǒng)要判定并發(fā)執(zhí)行的各程序段是否滿足 Bernstein 條件是相當(dāng)困難的。 r ? s[top]。一般情況下，并發(fā)執(zhí)行的各程序段如果共享軟、硬件資源，都會造成其執(zhí)行結(jié)果受執(zhí)行速度影響的局面。這個基本單位被稱為進(jìn)程（或任務(wù)）。也就是說，在不考慮資源共享的情況下，各進(jìn)程的執(zhí)行是獨(dú)立的，執(zhí)行速度是異步的。在用戶向計(jì)算機(jī)提交作業(yè)之后，系統(tǒng)將它放入外存中的作業(yè)等待隊(duì)列中等待執(zhí)行。進(jìn)程的靜態(tài)描述由三部分組成：進(jìn)程控制塊PCB，有關(guān)程序段和該程序段對其進(jìn)行操作的數(shù)據(jù)結(jié)構(gòu)集。下面分別介紹進(jìn)程的 PCB結(jié)構(gòu)、程序與數(shù)據(jù)結(jié)構(gòu)集。 ② 進(jìn)程優(yōu)先級 進(jìn)程優(yōu)先級是選取進(jìn)程占有處理機(jī)的重要依據(jù)。 ⑤ 指向文件系統(tǒng)的指針及有關(guān)標(biāo)識等。 PCB 結(jié)構(gòu)中的其他部分則存放于外存之中，待該進(jìn)程將要執(zhí)行時與其他數(shù)據(jù)一起裝入內(nèi)存。從 CPU是活動的觀點(diǎn)來靜態(tài)地看一個進(jìn)程時，必須把有關(guān)寄存器和棧區(qū)的內(nèi)容也包括在其中。 進(jìn)程的系統(tǒng)級上下文又分為靜態(tài)部分與動態(tài)部分。 圖 UNIX System Ⅴ 進(jìn)程