第三章進(jìn)程管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、操作。前者稱為讀進(jìn)程，后者稱為 寫(xiě)進(jìn)程，二者進(jìn)行數(shù)據(jù)共享要求： a、多個(gè)讀者可同時(shí)訪問(wèn)這組共享數(shù)據(jù)并發(fā) b、多個(gè)者不可同時(shí)訪問(wèn)這組共享數(shù)據(jù)互斥 c、讀者與寫(xiě)者不可同時(shí)訪問(wèn)這組共享數(shù)據(jù)互斥l解：用變量r w w實(shí)現(xiàn)讀者與寫(xiě)者的互斥及寫(xiě)者之間的互斥。 變量readcount用于記錄讀者數(shù)目。 變量mutex用來(lái)保證讀者對(duì)于變量readcount訪問(wèn)的互斥。 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ìn)程通信，是指進(jìn)程間進(jìn)行信息交換，根據(jù)進(jìn)程間傳送數(shù)據(jù)的多少及性質(zhì)，將進(jìn)程通信分成低級(jí)通信和高級(jí)通信。 低級(jí)通信：進(jìn)程間控制信息的交換。一般只傳送一個(gè)或幾個(gè)字節(jié)信息，目的是控制進(jìn)程執(zhí)行速度。 高級(jí)通信：進(jìn)程向大批量數(shù)據(jù)的交換，目的是為了交換信息。 一、進(jìn)程的通信方式： （一） 進(jìn)程間通信方式種類：1 1、主從式 2、會(huì)話式 3、消息或郵箱機(jī)制 4、共享存貯區(qū)方式 （二）四種通信方式的基本情況： 1、 主從式通信特點(diǎn)： a、主

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

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

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

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

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

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

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

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

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

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

37、條從節(jié)點(diǎn)Rj指向Pi的有向邊，稱為分配邊，表示資源Rj或Rj中的一個(gè)單位已分配給進(jìn)程Pi，當(dāng)進(jìn)程Pi請(qǐng)求分配資源Rj中的一個(gè)單位時(shí)，一條請(qǐng)求邊被加入RAG中，只要這個(gè)請(qǐng)求是可滿足的，則該請(qǐng)求邊立即轉(zhuǎn)換成分配邊，當(dāng)進(jìn)程Pi釋放了某個(gè)資源Rj時(shí)，則刪除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)進(jìn)程狀態(tài)為： 進(jìn)程P已占有R2中一個(gè)單位，正在等待在獲得 R1類資源，進(jìn)程P2已占有R1類資源和R

38、2中的一個(gè)單 位，正在等待R3類資源，進(jìn)程P3已占有R3資源。 (3)圖示如下:P1P3P2R2R3R1R4 6、死鎖判定定理： 假定某時(shí)刻系統(tǒng)中有一組進(jìn)程使用一組資源的 狀態(tài)為s，RAG是狀態(tài)s對(duì)應(yīng)的圖，則 （1）若RAG中未出現(xiàn)環(huán)路，則s為非死鎖狀態(tài)，或 為安全態(tài)。 （2）若RAG中出現(xiàn)了環(huán)路，且該環(huán)路中的各資源均為 單單位資源（只有一個(gè)分配單位），則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、對(duì)RAG圖的簡(jiǎn)化： （1）從RAG中找一個(gè)只有分配邊的，或雖有請(qǐng)求邊但該 請(qǐng)求邊能立即轉(zhuǎn)化為分配邊的非孤立點(diǎn)Pi，然后消 去Pi的全部有向邊，即釋放進(jìn)程Pi所占有的全部資 源，使之成為孤立點(diǎn)； （2）假定Rk是進(jìn)程節(jié)點(diǎn)Pi釋放的某個(gè)資源節(jié)點(diǎn)，則另 一節(jié)點(diǎn)Pj關(guān)于Rk的請(qǐng)求邊Pi-Rj就可以轉(zhuǎn)化為分配 邊RK-Pj，即進(jìn)程Pi釋放的資源Rk可分配給進(jìn)程Pj 所使用；如果經(jīng)一系列的轉(zhuǎn)化后Pj只有分配邊，則 進(jìn)程Pj稱為孤立點(diǎn)； （3）在實(shí)施一系列簡(jiǎn)化后，若可消去RAG中全部有向邊， 使全部進(jìn)程節(jié)點(diǎn)均成為孤立點(diǎn)，則稱該圖是可完全 化簡(jiǎn)的，否則稱該圖是不可完全簡(jiǎn)化的。（死鎖） 例1：

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

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

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

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

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