第三章進程管理

1、 進程是操作系統(tǒng)中極為重要的概念，通過這一概念的引入，可以更準確地把握OS對資源的管理功能和對用戶的服務(wù)功能,同時更能從本質(zhì)上了解OS中關(guān)于用戶作業(yè)和程序的處理過程以及OS對死鎖、同步、互斥、通信等內(nèi)容的展開。一、程序的并發(fā)執(zhí)行 1、在單道程序系統(tǒng)中程序的執(zhí)行特點： （1）順序性：即不同程序之間是順序執(zhí)行的， 一個程序的執(zhí)行必須在他的前一個程序的 執(zhí)行完畢。 （2）封閉性：指用戶程序在其運行期間所使用 的系統(tǒng)是專用的，資源的狀態(tài)只有該程序 能改變，而不受外界因素的影響。 （3）無關(guān)性：指程序的運行結(jié)果與他的執(zhí)行速 度無關(guān)。 （4）再現(xiàn)性：如果一個程序在不同的時間執(zhí)行，只要初 始條件相同，該程序

2、的執(zhí)行軌跡和最終結(jié)果亦必相 同。 2、多道程序系統(tǒng)中程序執(zhí)行的特點： （1）異步性：每個程序均以各自獨立的速度向前推進， 沒有時間上的規(guī)律性，程序的啟動與執(zhí)行時間是不 確定的， 而且程序的執(zhí)行一般是非連續(xù)的，且呈走 走停停的狀態(tài)。 （2）競爭性： （3）相互制約性 （4）與速度有關(guān) a.舉例 b.與時間相關(guān)的錯誤現(xiàn)象 (5)獨立性 (6)隨機性 (7)資源共享 3、程序的并發(fā)執(zhí)行（P38） （1）什么是程序的并發(fā)執(zhí)行？ 并發(fā)：指在計算機系統(tǒng)中同時存在多個程序，宏觀 上看，這些程序是同時向前推進的，表現(xiàn)在以 下兩個方面：第一、用戶程序之間并發(fā)執(zhí)行； 第二、用戶程序與OS程序之間并發(fā)執(zhí)行。 并行：

3、程序并行要求微觀上的同時，即在絕對的同一 時刻有多個程序同時向前推進，所以程序并行 只能在多處理機上才能實現(xiàn)。 兩相鄰語句S1,S2可以并發(fā)的條件（P39） （3）程序的并發(fā)執(zhí)行所帶來的影響： 由于資源共享和競爭，程序的執(zhí)行結(jié)果將不 可避免地失去封閉性和可再現(xiàn)性二、進程的定義 1、進程：是一個具有獨立功能的程序?qū)δ硞€數(shù)據(jù)集在 處理機上的執(zhí)行過程，是分配資源的基本單位。 2、進程與程序的區(qū)別： （1）進程是一個動態(tài)的概念，而程序則是一個靜態(tài)的 概念。程序是指令的有序集合，沒有任何執(zhí)行的 含義。而進程則強調(diào)執(zhí)行過程，他動態(tài)地被創(chuàng)建， 并被執(zhí)行后消亡。 （2）進程具有并行特征，而程序沒有。有進程的定

4、義 可知，進程具有特征的兩個方面，即獨立性和異 步性。也就是說，在不考慮資源共享的情況下， 各進程的執(zhí)行是獨立的，執(zhí)行速度是異步的。顯 然，由于程序不反映執(zhí)行過程，所以不具有并行 特征。 （3）進程是競爭計算機系統(tǒng)資源的基本單位，從而其 并行性受到系統(tǒng)自己的制約。這里，制約就是對 進程獨立性和異步性的限制。 （4）不同的進程可以包含同一個程序，只要該程序?qū)?應(yīng)的數(shù)據(jù)集不同。三、進程和作業(yè)的關(guān)系： （1)作業(yè)是用戶向計算機提交任務(wù)的任務(wù)實體。而進程 是完成用戶任務(wù)的執(zhí)行實體，是向系統(tǒng)申請分配資 源的基本單位。 （2）一個作業(yè)可由多個進程組成。 且必須至少有一個 進程組成，但反過來不成立。 （3）

5、作業(yè)的概念主要用在批處理系統(tǒng)中。像UNIX這樣 的分時系統(tǒng)中，則沒有作業(yè)概念。而進程的概念則 用在幾乎所有的多道系統(tǒng)中。 從靜態(tài)看，進程由三部分組成：進程控制塊、有關(guān)程序段、數(shù)據(jù)結(jié)構(gòu)集。 （1）PCB：包含了有關(guān)進程的描述信息、 控制信息及資源信息，是進程動態(tài) 特征的集中反映，OS根據(jù)PCB感知 進程的存在和通過PCB中所含的各項 變量的變化，掌握進程的狀態(tài)已達 到控制進程活動的目的。 （2）進程的程序部分：描述進程所要完 成的功能。 （3）數(shù)據(jù)結(jié)構(gòu)集：是程序執(zhí)行時必不可 少的工作區(qū)和操作對象。一、進程控制塊PCB （1）PCB集中反映一個進程的動態(tài)特征。 （2）創(chuàng)建進程時，就由操作系統(tǒng)為其建

6、立PCB，然后 根據(jù)PCB中的信息對進程進行控制。 （3）當(dāng)一個進程完成時，系統(tǒng)釋放PCB，進城也隨之 消亡。 1、PCB內(nèi)容：OS不同，PCB內(nèi)容也有差異，但所有PCB 均有以下內(nèi)容： （1）描述信息 a、進程名或進程標志號 b、用戶名或用戶標志號 c、家族關(guān)系 （2）控制信息 a、進程當(dāng)前狀態(tài) b、進程優(yōu)先級 c、程序開始地址 d、各種計時信息 e、通信信息 （3）資源管理信息 a、占用內(nèi)存大小及其管理用數(shù)據(jù)結(jié)構(gòu)指針 b、在某些復(fù)雜系統(tǒng)中，還有對換或覆蓋用的有關(guān) 信息，如對換程序長度，對換外存地址等。 c、共享程序段大小及起始地址。 d、輸入輸出設(shè)備的設(shè)備號，所要傳送的數(shù)據(jù)長度、 緩沖區(qū)地

7、址、緩沖區(qū)長度及所用設(shè)備的有關(guān)數(shù)據(jù) 結(jié)構(gòu)指針等。 e、指向文件系統(tǒng)的指針及有關(guān)標志等。 （4）CPU現(xiàn)場保護結(jié)構(gòu) 當(dāng)前進程因等待某個事件而進入等待狀態(tài)或 因某種事件的發(fā)生被中止在處理機上的執(zhí)行時，為 了以后該進程能在被打斷處恢復(fù)執(zhí)行，需要保護當(dāng) 前進程的CPU現(xiàn)場（或稱進程上下文）。PCB中設(shè) 有專門的CPU現(xiàn)場保護結(jié)構(gòu)，以存儲退出執(zhí)行時的 進程現(xiàn)場數(shù)據(jù)。 2、PCB的物理表示 或二、進程上下文（P44） 1、概念：是進程執(zhí)行活動全過程的靜態(tài)描述，包括計 算機中與執(zhí)行進程有關(guān)的各種寄存器的值，程序段 PCB程序程序數(shù)據(jù) PCB程序數(shù)據(jù) 在經(jīng)過編譯后形成的機器指令代碼集（正文段）、 數(shù)據(jù)集及各種

8、堆棧值及PCB結(jié)構(gòu)。 2、進程上下文動態(tài)部分：指在進入和退出不同的上下 文時，系統(tǒng)為各層上下文中相關(guān)聯(lián)的寄存器值所保 存和恢復(fù)的記錄。 3、進程上下文靜態(tài)部分：包括PCB結(jié)構(gòu)、將進程虛地 址空間映射到物理空間用的有關(guān)表格和核心棧。三、進程空間（P45） 1、進程空間：任一進程均有一個自己的地址空間，把該 空間稱為進程控間或虛空間。進程空間大小只與處理 機位數(shù)有關(guān)。 2、進程空間的劃分： 分為用戶空間和系統(tǒng)空間。 （1）用戶模式（用戶態(tài)）：用戶程序的執(zhí)行方式，只 能在用戶空間進行，不能訪問系統(tǒng)空間。 （2）系統(tǒng)模式（系統(tǒng)態(tài)）：系統(tǒng)程序執(zhí)行方式，能對 系統(tǒng)空間和用戶空間訪問。一、進程狀態(tài) 1、執(zhí)行

9、態(tài)：進程獲得了CPU，正在CPU上運行它的程序。在單CPU的系統(tǒng)中，任一時刻系統(tǒng)中只能有一個處于執(zhí)行狀態(tài)的進程。 2、就緒狀態(tài)：進程獲得了除CPU之外的一切當(dāng)前需要的資源，準備占用CPU。一個進程一旦被建立就處于就緒狀態(tài)。 3、等待狀態(tài)：進程正在等待某一事件的發(fā)生或受到某種制約而暫時停止運行。 4、停止狀態(tài)：進程運行終止，等待被系統(tǒng)撤銷。 5、死鎖狀態(tài)：進程在無限地等待一件永遠不會發(fā)生的事 件，這是一種進程運行故障。二、進程狀態(tài)轉(zhuǎn)換 1、轉(zhuǎn)換圖 1 3 5 撤銷 建立 2 6 4 7 2、圖中各種轉(zhuǎn)換的條件 （1）變換1：處于就緒狀態(tài)的進程獲得了CPU而變成執(zhí) 行態(tài)。 就緒執(zhí)行等待停止死鎖 （

10、2）變換2：正在運行的進程因等待某種原因（如時間 片用完）而被迫放棄CPU。 （3）變換3：表示正在運行的進程因等待某時間的發(fā)生 而處于等待。 （4）變換4：表示進程所等待的事件發(fā)生了，而變成就 緒態(tài)。 （5）變換5：表示當(dāng)前進程運行完畢，進入停止態(tài)，等 待被撤銷。 （6）變換6：表示若干進程無休止地等待陷入死鎖。 （7）變換7：在解除死鎖的有的方案中，可以將死鎖態(tài) 進程逐一恢復(fù)。1、進程控制：系統(tǒng)使用一些具有特定功能的程序段（原語）來創(chuàng)建、撤銷進程以及完成進程個狀態(tài)間的轉(zhuǎn)換，從而達到多進程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實現(xiàn)資源共享的目的。2、原語：在系統(tǒng)態(tài)下執(zhí)行的具有特定功能的程序段，原語分為指令級

11、原語和功能級原語。 （1）指令級原語：執(zhí)行期間不允許中斷，是不 可分割的單位。 （2）功能級原語：執(zhí)行期間不允許并發(fā)的程序 段。 原語的特點： a、具有獨立的系統(tǒng)功能； b、在系統(tǒng)態(tài)運行； c、不允許中斷或不允許并發(fā)。一、進程創(chuàng)建與撤銷 1、進程創(chuàng)建 （1）創(chuàng)建方式： a、由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建，各進程關(guān)系平等； b、由父進程創(chuàng)建 進程之間存在隸屬關(guān)系，形成家族關(guān)系； 屬于某家族的一個進程可以繼承父進程的資源。 （2）創(chuàng)建過程描述： 入口查PCB鏈表有無空PCB創(chuàng)建失敗取空PCB（i）將有關(guān)參數(shù)填入PCB(i)相應(yīng)項PCB(i)入就緒隊列PCB(i)入進程家族或進程鏈返回 2、進程撤銷： （1

12、）引起進程撤銷的原因： a、該進程已完成所要求的功能而正常終止； b、由于某種錯誤而導(dǎo)致非正常終止； c、祖先進程要求撤銷某個子進程。 （2）撤銷的任務(wù)： a、釋放所占有的所有資源； b、釋放相應(yīng)的PCB或子進程相應(yīng)的PCB。 （3）撤銷原語流程圖 （P48）二、進程的阻塞和喚醒 1、進程的阻塞（執(zhí)行態(tài) 等待態(tài)） 處于執(zhí)行狀態(tài)的進程由于需等待外部事件的發(fā)生 而調(diào)用block原語將自己從執(zhí)行態(tài)變?yōu)榈却龖B(tài)。在實 現(xiàn)阻塞時，block應(yīng)先中斷處理機并保存CPU現(xiàn)場。 流程圖（P49） 2、喚醒 當(dāng)?shù)却犃兄械倪M程所等待的事件發(fā)生時，待事 件的所有進程都將被喚醒，即從等待態(tài)變?yōu)榫途w態(tài)。 喚醒方法有：

13、a、由系統(tǒng)進程喚醒 系統(tǒng)進程統(tǒng)一控制事件的發(fā)生 并將“事件發(fā)生”這一消息通知等待進程，從而使 進程從等待態(tài)變?yōu)榫途w態(tài)； b、由事件發(fā)生進程喚醒 這種情況下，事件發(fā)生進 程和被喚醒進程之間是合作關(guān)系。 流程圖（P49）一、資源共享引起的制約 1、與時間相關(guān)的錯誤 由于兵法進程是隨機發(fā)生的，如果參與并發(fā)的進程相互間直接或間接聯(lián)系非常緊密，如共享變量或某些資源，可能產(chǎn)生與進程推進速度有關(guān)的錯誤，也稱與時間相關(guān)的錯誤。 例子（略） 2、進程互斥：指兩個或兩個以上的進程不能同時進入關(guān)于同一組共享變量的臨界區(qū)域，否則會發(fā)生與時間相關(guān)的錯誤。 互斥是進程間所發(fā)生的間接性相互排斥現(xiàn)象，根本 原因在于不同進程對

14、共享變量或資源的訪問。 3、進程同步：指一組相互合作的并發(fā)進程，為協(xié)同起推 進速度，需要相互等待與相互喚醒，進程間的這種直接 相互作用叫同步。 4、共享資源： 指兩個或兩個以上的進程要訪問使用的 資源，包括硬件、軟件資源，如打印機、數(shù)據(jù)等。 5、臨界資源： 并發(fā)進程可以共享系統(tǒng)中的各種資源， 但其中某些資源一次只允許一個進程訪問，這樣的資源 叫臨界資源，如打印機、磁帶等。 6、臨界區(qū)域： 進程中涉及對臨界資源訪問的那一部分 操作即程序段叫做關(guān)于該臨界資源的臨界區(qū)域。 7、間接制約： 由于共享某一共有資源而引起的在臨界 區(qū)內(nèi)不允許并發(fā)進程交叉執(zhí)行的現(xiàn)象稱為由共享資源而 造成的對并發(fā)進程執(zhí)行速度的

15、間接制約，簡稱間接制約。 8、互斥概念的含義： （1）不允許多個進程同時進入關(guān)于同一組共享變量的 相同的臨界區(qū)。 （2）不允許多個進程同時進入關(guān)于同一組共享變量的 不同的臨界區(qū)。 9、解決臨界區(qū)互斥問題應(yīng)遵循的準則： （1）有空讓進 （2）無空等待 （3）多中擇一 （4）有限等待 （5）讓權(quán)等待 10、實現(xiàn)互斥的基本要求： （1）互斥性要求：任一時刻最多只能有一個進程處于 關(guān)于同一組共享變量的臨界區(qū)域中； （2）公平性要求：不能讓一個進程無限地等待進入關(guān) 于任一組共享資源的臨界區(qū)。二、互斥的加鎖實現(xiàn)（P52） 1、加鎖原語LOCK與開鎖原語UNLOCK 思想： （1）設(shè)變量X，它取值為0或1，

16、把X作為一把所配 置給臨界資源，若X=0，表示資源未加鎖，X=1，表示 資源已加鎖。 （2）互斥的進程在進入臨界資源前先對X進行測 試，若X=0表示進程可以進入臨界區(qū)，進入后立即加鎖， 不允許其他進程進入；當(dāng)該進程退出臨界區(qū)時應(yīng)立即 開鎖，以便其他進程進入。 （3）加鎖原語LOCK定義為： a、檢查x的值； b、若x=0，則表示臨界資源可用，允許一個進程進入 臨界區(qū)，并立即加鎖：x=1； c、若x=1，表示資源已被占用，返回第一步繼續(xù)測試。 2、例：設(shè)進程A負責(zé)分配打印機，進程B釋放打印機， 用LOCK 和UNLOCK解決對打印機的互斥。 解：用流程圖描述如下： 3、特點：效率不高，因只有一個

17、進程正在臨界區(qū)內(nèi)執(zhí)行， 返 回 ， 繼 續(xù) 測試X =1上鎖，置X=1分配打印機退出，開鎖X=0返回，繼續(xù)測試X=1上鎖，置X=1釋放打印機退出，開鎖X=0 其他試圖進入臨界區(qū)的進程只有通過反復(fù)測試，等待 進入臨界區(qū)，從而浪費了CPU時間。三、信號量和P、V原語（P53） 1、信號量（Sem） 是一個整數(shù)，在Sem大于等于0時表示可供并發(fā) 進程是用的資源實體數(shù)，Sem小于0則表示正在等待 使用資源的進程數(shù)。 2、P操作: (1)Sem減1; (2)若Sem減1后仍大于或等于0,則進程執(zhí)行； （3）若Sem減1后小于0，則該進程被阻塞后進入與該信 號相對應(yīng)的隊列中，然后轉(zhuǎn)進程調(diào)度。 3、V操作：

18、 （1）Sem加1； （2）若Sem加1后小于或等于0，則從與該信號量的等 待隊列中喚醒一進程，然后再返回原進程繼續(xù)執(zhí) 行或轉(zhuǎn)進程調(diào)度。四、用P、V原語實現(xiàn)互斥： 方法：令Sem=1，把臨界區(qū)置于P(Sem)和V(Sem)之間。 描述： PA: P(SEM) V(SEM) PB: P(SEM) V(SEM) 一、進程同步 指兩個或兩個以上的具有合作關(guān)系的進程，為協(xié)調(diào)其推進速度，需要互相等待和互相喚醒，進程間的這種直接相互作用關(guān)系叫進程同步。 例：計算進程Pc與打印進程Pp間的關(guān)系 1、并發(fā)進程間的直接制約： 一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制個進程的執(zhí)行速度

19、的過程稱為進程間的直接制約。 2、解決方法之一：直接制約的進程互相給對方發(fā)送執(zhí)行 條件已具備的信號。 （1）合作進程：指具有同步關(guān)系的一組并發(fā)進程。 消息：合作進程間互相發(fā)送的信號。 （2）Wait和Signal過程 Wait(消息名)：表示進程等待合作進程發(fā)來的消息。 Signal(消息名)：表示向合作進程發(fā)送消息。 （3）用Wait和Signal過程實現(xiàn)進程同步的方法：P58 a、設(shè)消息名Bufempty表示buf為空，消息名buffull表 示buf中裝滿了數(shù)據(jù)。 b、初始化bufempty=true，buffull=false； c、描述： pc: a: wait(bufempty)

20、計算 bul 計算結(jié)果 bufempty false signal(buffull) goto a Pp: b: wait(buffull) 打印buf 中的數(shù)據(jù) 清除buf中的數(shù)據(jù) buffull falsesignal(bufempty) goto b二、私用信號量： 各并發(fā)進程發(fā)送的消息作為信號量對待，與互斥中 不同的是：這里的信號量只與制約進程和被制約進程有 關(guān)而不是與整組并發(fā)進程有關(guān)，因此把同步中的信號量 稱為私用信號量。 相反，互斥中的信號量稱為公用信號量。三、用P、V原語實現(xiàn)同步： 1、用P、V原語實現(xiàn)同步的步驟： （1）為各并發(fā)進程設(shè)置私用信號量； （2）為私用信號量賦初值；

21、（3）用私用信號量和P、V原語規(guī)定各進程的執(zhí)行順序 2、例：進程Pa和Pb通過緩沖區(qū)隊列傳遞數(shù)據(jù)。Pa為發(fā)送 數(shù)據(jù)的進程，Pb為接收進程。Pa發(fā)送數(shù)據(jù)時調(diào)用過程 deposit(data)，Pb接收數(shù)據(jù)時調(diào)用過程remove(data)，且 發(fā)送與接收滿足條件： （1）在Pa至少送一塊數(shù)據(jù)如一個緩沖區(qū)前，Pb不可能 從緩沖區(qū)取出數(shù)據(jù)； （2）Pa往緩沖區(qū)隊列發(fā)送數(shù)據(jù)時，至少有一個緩沖區(qū) 是空的； （3）由Pa發(fā)送的數(shù)據(jù)塊在緩沖區(qū)隊列中按先進先出方 式排列。 解：略 （P59-60）四、生產(chǎn)者-消費者問題 1、概念： 資源的消費者：系統(tǒng)中使用某一類資源的進程。 資源的生產(chǎn)者：釋放同類資源的進程。

22、 例如：計算進程為生產(chǎn)者，打印進程為消費者。 2、生產(chǎn)者、消費者問題屬于同步問題，因為它們之間滿 足條件： （1）消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個 單元是滿的； （2）生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個 單元是空的。（即生產(chǎn)者與消費者之間各自的執(zhí)行 結(jié)果互為對方的條件，屬于同步問題） 3、生產(chǎn)者消費者之間對有界緩沖區(qū)的使用必須互斥，印 有界緩沖區(qū)是臨界資源。 4、生產(chǎn)者、消費者之間同步、互斥的描述： P61 解：設(shè)公用信號量nutex保證上纏著消費者進程之間的 互斥，設(shè)信號量avail為生產(chǎn)者進程的私用信號量， full 為消費者進程的私用信號量。Avail表示有界緩 沖區(qū)中

23、的空單元數(shù)，初值為n；full表示有界緩沖區(qū) 中非空單元數(shù)，初值為0。信號量mutex表示可用有 界緩沖區(qū)的個數(shù)，初值為1。 deposit(data): begin p(avail); p(mutex); 送數(shù)據(jù)進入緩沖區(qū)某單元 v(full); v(mutex); end remove(data): bein p(full); p(mutex); 取緩沖區(qū)中某單元數(shù)據(jù) v(avail); v(mutex) end五、讀者與寫者關(guān)系： 1 1、 問題描述： reader/writer 設(shè)有一組共享數(shù)據(jù)和兩組并發(fā)進程，一組進程只 能對這組數(shù)據(jù)進行讀操作，另一組進程可能對這組數(shù) 據(jù)進行讀操作和寫

24、操作。前者稱為讀進程，后者稱為 寫進程，二者進行數(shù)據(jù)共享要求： a、多個讀者可同時訪問這組共享數(shù)據(jù)并發(fā) b、多個者不可同時訪問這組共享數(shù)據(jù)互斥 c、讀者與寫者不可同時訪問這組共享數(shù)據(jù)互斥l解：用變量r w w實現(xiàn)讀者與寫者的互斥及寫者之間的互斥。 變量readcount用于記錄讀者數(shù)目。 變量mutex用來保證讀者對于變量readcount訪問的互斥。 Program read_and_writer(input,output); type semaphore=record value:integer; queue:pointer to pcb end; var r_w_w,mutex:sema

25、phore; readcount:integer; procedure readers; begin p(mutex); readcount:=readcount+1; if readcount=1 then p(r_w_w); v(mutex); reading; p(mutex); readcount:=readcount-1; if readcount=0 then v(r_w_w) v(mutex) end; procedure writers; begin p(r_w_w); writing; v(r_w_w) end; begin of main r_w_w:=1; mutex:=

26、1; readcount:=0; cobegin r1:readers; rm:readers; w1: writers; wn: writers coend end. 所謂進程通信，是指進程間進行信息交換，根據(jù)進程間傳送數(shù)據(jù)的多少及性質(zhì)，將進程通信分成低級通信和高級通信。 低級通信：進程間控制信息的交換。一般只傳送一個或幾個字節(jié)信息，目的是控制進程執(zhí)行速度。 高級通信：進程向大批量數(shù)據(jù)的交換，目的是為了交換信息。 一、進程的通信方式： （一） 進程間通信方式種類：1 1、主從式 2、會話式 3、消息或郵箱機制 4、共享存貯區(qū)方式 （二）四種通信方式的基本情況： 1、 主從式通信特點： a、主

27、進程可自由地使用從進程的資源或數(shù)據(jù) b、從進程的動作受主進程的控制 c、主進程和從進程的關(guān)系是固定的 2、會話方式： 通信雙方稱為使用進程和服務(wù)進程，其中，使用 進程調(diào)用服務(wù)進程提供的服務(wù)。二者具有以下特點： a、使用進程在使用服務(wù)進程所提供的服務(wù)之前， 必須得到服務(wù)進程的許可。 b、服務(wù)進程根據(jù)使用進程的要求提供服務(wù)，但對 所提供服務(wù)的控制由服務(wù)進程自身完成。 c、使用進程和服務(wù)進程在進行通信時有固定的連 接關(guān)系。 例：1、用戶進程與磁盤管理進程采取會話方式。 2、用戶進程與打印機管理進程之間采用會話方式。 （三）消息或郵箱機制： 1、方法：無論接收進程是否已準備好接收消息，發(fā) 送進程都將把

28、所要發(fā)送的消息送入緩沖區(qū)或郵箱。、 消息：進程向傳遞的大量數(shù)據(jù)。 2、消息的組成 （1）發(fā)送進程名 （2）接收進程名 （3）數(shù)據(jù) （4）有關(guān)數(shù)據(jù)的操作3、消息或郵箱機制的特點：（1）只要存在空緩沖區(qū)或郵箱，發(fā)送進程就可以 發(fā)送消息。 （2）與會話系統(tǒng)不同，發(fā)送進程與接收進程之間 無直接連接關(guān)系，接收進程可能在接收到某個 發(fā)送進程發(fā)來的消息后，又轉(zhuǎn)去接收另一個發(fā) 送進程送來的消息。 （3）發(fā)送進程和接收進程之間存在緩沖區(qū)或郵箱 用來存放被傳消息。（四）共享存貯區(qū)方式： 方法：不要求數(shù)據(jù)移動，兩個需要相互交換信息的 進程通過對同一共享數(shù)據(jù)的操作來達到互相通 信的目的。這個共享數(shù)據(jù)區(qū)是每個互相通信進

29、 程的一個組成部分。二、消息緩沖區(qū)機制： 1、方法： （1）發(fā)送進程和接收進程采用消息緩沖機制進行數(shù)據(jù) 傳送時，發(fā)送進程在發(fā)送消息前，先在自己的內(nèi)存 空間設(shè)置一個發(fā)送區(qū)，把欲發(fā)送的消息填入其中， 然后再用發(fā)送過程將其發(fā)送出去。 （2）接收進程則在接收消息之前，在自己的內(nèi)存空間 內(nèi)設(shè)置相應(yīng)的接收區(qū)，然后用接收過程收消息。 2、發(fā)送進程與接收進程通信的條件： （1）在發(fā)送進程把消息寫入緩沖區(qū)和把緩沖區(qū)掛入消 息隊列時，應(yīng)禁止其它進程 對該緩沖區(qū)消息隊列的 訪問，否則將引起消息隊列的混動，同理，當(dāng)接 收進程上從消息隊列中取消息緩沖時，也應(yīng)禁止 其他進程對該隊列的訪問。（互斥） （2）當(dāng)緩沖區(qū)中無消息

30、存在時，接收進程不能接收 到任何消息。解：設(shè)公用信息量mutrx作為控制緩沖區(qū)的互斥信 息量，初值為1。設(shè)sm為接收進程的私用信息量， 表示等待接收的消息個數(shù)，初值為0。 令發(fā)送進程調(diào)用過程send(m)將消息m送入緩沖 區(qū)，接收進程調(diào)用過程Receive(m)把渻m從緩沖區(qū) 讀往自己的數(shù)據(jù)區(qū)。 Send(m)和receive(m)的描述Send(m): Begin 向系統(tǒng)申請一個消息緩沖區(qū) P（mutex） 將發(fā)送區(qū)消息m送入新申請的消息緩沖區(qū) 把消息緩沖區(qū)掛入接收進程的消息隊列 V(mutex) V(sm) EndReceive(m):Begin End; 三、郵箱通信 1、方法： (1)

31、郵箱通信就是由發(fā)送進程申請建立一個與接收進程鏈 接的郵箱。 (2)發(fā)送進程把消息送往郵箱，接收進程從郵箱中取出信 息，從而完成進程間信息交換。 (3)郵箱由郵箱頭和郵箱體組成，其中郵箱頭描述郵箱名 稱、郵箱大小、郵箱方向以及擁有該郵箱的進程名等。 2、條件：對于只有一個發(fā)送進程和一個接收進程使用的 郵箱，進程間的通信應(yīng)滿足如下條件： （1）發(fā)送進程發(fā)送消息時，郵箱中至少有一個空格能 存放消息。 （2）接收進程接收消息時，郵箱中至少要有一個消息 存在。 3、控制描述： （1）設(shè)發(fā)送進程調(diào)用過程deposit(m)將消息發(fā)送到郵 箱，接收進程調(diào)用過程remove(m)將消息m從郵箱中 取出。 （2

32、）為了記錄郵箱中空格和消息個數(shù)，信息量fromnum 為發(fā)送進程的私用信息量，mesnum為接收進程的私 用信息量fromnum的初值為信箱的空格數(shù)n,mesnum的 初值為0。 （3）同步描述： deposit(m) begin local(x) p(fromnum) 選擇空格x 將消息m放入空格x中 置空格x的標志為滿 v(mesnum) end; remove(m) begin local x; p(mesnum) 選擇滿格x 把滿格x中消息取出放入m中 置x標志為空 v(fromnum) end （4）思考： 郵箱機制為何不存在互斥？四、進程通信的實例和控制后的通信 1、控制臺終端：由

33、鍵盤和顯示器組成，它同主機之間按 全雙工模式發(fā)送和接收數(shù)據(jù)，由系統(tǒng)操作員使用。 2、所需進程 （1）鍵盤控制進程Kcp （2）顯示控制進程Dcp （3）會話控制進程Ccp-管理用戶進程和控制臺終 端的通信。 3、緩沖區(qū)： Inbuf：控制臺終端的輸入置于其中，Ccp可以從Inbuf 中取出消息從而得到來自控制臺的指示。 Outbut：Ccp所提出問題以消息形式放入控制臺的輸出 緩沖隊列，且Dcp從Output中取出消息送至顯示器， 以供操作員判斷。 （1）Kcp與Dcp的動作 P66 略 在多道程序系統(tǒng)中，多進程并發(fā)執(zhí)行，共享系統(tǒng)資源，從而提高了資源利用率，但如果對資源的管理不當(dāng)，則可能產(chǎn)生一

34、種隨機故障死鎖。一、死鎖定義： 1、定義：指各并發(fā)進程彼此互相等待對方擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己擁有的資源，從而造成大家都想得到資源而又都得不到資源，各并發(fā)進程不能繼續(xù)向前推進的狀態(tài)。 2、例：設(shè)p1,p2,p3為3個并發(fā)進程，r1,r2,r3 為三種不同類資源，p1擁有r1,申請r2，p2擁有r2，申 請r3,p3擁有r3,申請r1,則此時，p1,p2,p3陷入死鎖狀態(tài)。 圖示如下： 產(chǎn)生死鎖的原因：系統(tǒng)提供的資源個數(shù)少于并發(fā)進程要 求的該類資源數(shù)。 3、死鎖不生的必要條件： （無之必不然，有這未必然） (1)互斥條件：進程訪問的資源是臨界資源，即一個資源一次

35、 只能被一個進程使用。 （2）請求和保持：也稱占有申請、部分分配。即一個進程在 P1R1P2R2P3R3 申請新的資源的同時，保持對某些資源的占有。 （3）不剝奪條件：即一個資源僅能被占有它的進程釋放， 而不能被其他進程剝奪。 （4）環(huán)路等待條件：存在一個進程環(huán)路，環(huán)路中每一進 程占有某個（些）資源，又申請環(huán)路中其它進程所占 有資源。 4、 關(guān)于死鎖的有關(guān)結(jié)論： （1）參與死鎖的進程個數(shù)至少為2。 （2）參與死鎖的所有進程均正在等待資源。 （3）參與死鎖的進程至少有兩個已經(jīng)占有資源。 （4）參與死鎖的進程是系統(tǒng)中當(dāng)前正在運行進程構(gòu)成 的集合的子集。 5、資源分配圖定義： 一個資源分配圖稱為RA

36、G,RAG定義為一個二元組 (N,E)，其中N是節(jié)點的集合，E為邊集；N又包含2個子集P,R，即N=(P,R),P=P1,P2,PM,是進程集合，每個元素P i 表 示 一 個 進 程 ， 在 圖 中 用 矩 形 框 表 示 ， 子 集R=R1,R2,Rk,是資源集合，每個元素Rj表示一類資源，在圖中用園圈表示，每類資源可能有多個分配單位，這在圖中用園圈中的小園圈表示； 邊集E中的每一元素是 Ri Rj或Rj Ri ，這可用序偶表示，即或。若Ri Rj E，則在圖中存在一條從節(jié)點Pi指向節(jié)點Rj 的有向邊，稱為請求邊，它表示進程Pi請求分配資源 或Rj中的一個單位；若Rj Pi，則在圖中存在一

37、條從節(jié)點Rj指向Pi的有向邊，稱為分配邊，表示資源Rj或Rj中的一個單位已分配給進程Pi，當(dāng)進程Pi請求分配資源Rj中的一個單位時，一條請求邊被加入RAG中，只要這個請求是可滿足的，則該請求邊立即轉(zhuǎn)換成分配邊，當(dāng)進程Pi釋放了某個資源Rj時，則刪除RAG中相應(yīng)的分配邊。 例：設(shè)集合P,R,E分別為: (1)P=P1,P2,P3,R=R1,R2,R3,R4,且 R1 =1, R2 =2, R3 =1, R4 =3, E=P1-R1,P2-R3,R1-P2,R2-P1, R2-P2,R3-P3 (2)進程狀態(tài)為： 進程P已占有R2中一個單位，正在等待在獲得 R1類資源，進程P2已占有R1類資源和R

38、2中的一個單 位，正在等待R3類資源，進程P3已占有R3資源。 (3)圖示如下:P1P3P2R2R3R1R4 6、死鎖判定定理： 假定某時刻系統(tǒng)中有一組進程使用一組資源的 狀態(tài)為s，RAG是狀態(tài)s對應(yīng)的圖，則 （1）若RAG中未出現(xiàn)環(huán)路，則s為非死鎖狀態(tài)，或 為安全態(tài)。 （2）若RAG中出現(xiàn)了環(huán)路，且該環(huán)路中的各資源均為 單單位資源（只有一個分配單位），則s為死鎖狀態(tài)。 換言之，由若干單單位資源構(gòu)成的環(huán)路，是s為死鎖狀 態(tài)的充分必要條件。 （3）若RAG中出現(xiàn)了環(huán)路，但該環(huán)路中的各資源不 全為單單位資源，則s不一定是死鎖狀態(tài)，換言之， 由若干不全為單單位資源構(gòu)成的環(huán)路，是s為死鎖狀態(tài) 的必要條

39、件但不充分。 7、對RAG圖的簡化： （1）從RAG中找一個只有分配邊的，或雖有請求邊但該 請求邊能立即轉(zhuǎn)化為分配邊的非孤立點Pi，然后消 去Pi的全部有向邊，即釋放進程Pi所占有的全部資 源，使之成為孤立點； （2）假定Rk是進程節(jié)點Pi釋放的某個資源節(jié)點，則另 一節(jié)點Pj關(guān)于Rk的請求邊Pi-Rj就可以轉(zhuǎn)化為分配 邊RK-Pj，即進程Pi釋放的資源Rk可分配給進程Pj 所使用；如果經(jīng)一系列的轉(zhuǎn)化后Pj只有分配邊，則 進程Pj稱為孤立點； （3）在實施一系列簡化后，若可消去RAG中全部有向邊， 使全部進程節(jié)點均成為孤立點，則稱該圖是可完全 化簡的，否則稱該圖是不可完全簡化的。（死鎖） 例1：

40、對下圖化簡：P1P3P2R2R3R1R4P1P3P2R2R3R1R4 例1：化簡上圖，判斷是否發(fā)生死鎖。二、死鎖的排除方法： 1、預(yù)防死鎖：只要去掉產(chǎn)生死鎖的四個必要條件之一， 就可達到預(yù)防死鎖的目的，但由于互斥條件是資源本 身性質(zhì)決定的，因此可以有以下三種預(yù)防措施。 （1）防止“請求和保持”條件的出現(xiàn)： a、思想：系統(tǒng)要求任一進程必須預(yù)先申請它所需要 的全部資源，而且僅當(dāng)該進程全部資源要求 都滿足時，系統(tǒng)才一次性給予分配，然后啟 動該進程運行，進程在整個生存期間，不再 請求新的資源。 b、實現(xiàn)特點： 資源按靜態(tài)分配策略，簡單安全 資源利用率低，浪費嚴重。 （2）防止“不剝奪”條件的出現(xiàn)： a

41、、思想：在允許進程動態(tài)申請資源前提下，規(guī)定 一個進程在請求新資源不能立即得到滿足 而變成等待狀態(tài)前，它必須釋放已占有的 全部資源；若需要，再重新申請新資源和 已釋放的資源。 b、特點：實現(xiàn)困難。 （3）防止“環(huán)路”條件： a、思想：把系統(tǒng)中所有資源按類型線性排隊，并 按遞增規(guī)則賦予每類資源以唯一編號，進程 申請資源時，必須嚴格按資源編號的遞增順 序進行，否則系統(tǒng)不予分配，由于在任何時 刻，總有一個進程占有較高編號的資源，它 繼續(xù)申請資源的要求必然可滿足，因此一定 不會出現(xiàn)環(huán)路等待條件。 b、特點： 由于資源申請和分配是逐步的，因此提高了 資源的利用率。 由于進程使用資源順序與系統(tǒng)規(guī)定不一致，

42、因此低級別的資源必須先申請，這樣也影響了 資源利用率。 由于嚴格地限制了使用資源的順序性，給程 序設(shè)計帶來了不便。 2、避免死鎖： （1）預(yù)防死鎖是設(shè)法至少破壞產(chǎn)生死鎖的必要條件之 一，嚴格地防止死鎖的出現(xiàn)，而避免死鎖不嚴格地 限制死鎖產(chǎn)生的必要條件。是一種動態(tài)監(jiān)測技術(shù)。 A、系統(tǒng)資源分配狀態(tài)： a、系統(tǒng)資源分配狀態(tài)s(t)定義： 系統(tǒng)中可用資源數(shù)和已分配資源數(shù)以及各 進程對資源的最大需求量的當(dāng)前情況。 b、安全狀態(tài)： 對于某時刻的系統(tǒng)資源分配狀態(tài)s（t），如 果系統(tǒng)能夠按照某種次序為進程分配它們所需 資源，并滿足各進程的最大需求而不會造成死 鎖，那么稱狀態(tài)s(t)是安全的。 形式化定義： 系

43、統(tǒng)狀態(tài)s（t）是安全的，僅當(dāng)存在一個安 全的進程序列p1,p2,pn，對于每一進程Pi， 其資源剩余需求數(shù)均可由系統(tǒng)當(dāng)前的可用資源 數(shù)與所有其他進程Pj(JNi，則有(Rri+Ui)Mi，即進程Pi請求的資源 類Rj的單位數(shù)大于它申請的最大需求數(shù)，故請求無 效并作出錯處理，否則進入下一步驟。 (j)若RriAi，即系統(tǒng)不能滿足當(dāng)前請求，則進程Pi等待； 否則繼續(xù)下一步驟。 (k)系統(tǒng)進行假分配，即對資源分配狀態(tài)作如下修改： A=A-Rri Ui=Ui+Rri Ni=Ni-Rri (l)調(diào)用安全算法檢查修改后的現(xiàn)行狀態(tài)是否安全，若 不安全，則告訴系統(tǒng)，否則進入下一步。 (m)系統(tǒng)實施真分配。 d

44、、例：設(shè)有五個進程P1,P2,P3,P4,P5，共享三類資源 R1,R2,R3，且有 R1 =10， R2 =5, R3 =7,若在時刻T0 關(guān)于它們的狀態(tài)S(T0)如下： (略，見備課本) 例（略，見備課本） 五、檢測和排除死鎖 預(yù)防死鎖與避免死鎖都不讓系統(tǒng)發(fā)生死鎖，這是 對資源使用設(shè)置了一些限制和增加了額外的CPU開銷為 代價的，降低了CPU利用率，也給用戶帶來了不方便。 在有的系統(tǒng)中，為提高資源利用率以及方便用戶，用 檢測與解除方案，即允許系統(tǒng)中存在死鎖，但在適當(dāng) 時刻進行死鎖檢測，一旦發(fā)現(xiàn)死鎖便立即設(shè)法解除死 鎖。 （一）檢測死鎖 1、 檢測依據(jù)： 確定是否存在環(huán)路等待現(xiàn)象，一旦發(fā)現(xiàn)這種現(xiàn)象 便認定死鎖存在，并識別出該環(huán)路所涉及的有關(guān)進程， 以供系統(tǒng)