操作系統(tǒng)教程(第二章)

第二章進(jìn)程及處理機(jī)管理§2.1進(jìn)程的提出§2.2進(jìn)程的定義和特征§2.3進(jìn)程狀態(tài)和進(jìn)程控制塊§2.4線程的基本概念§2.5進(jìn)程控制§2.6進(jìn)程同步§2.7經(jīng)典進(jìn)程同步問題§2.8進(jìn)程的通信§2.9處理機(jī)調(diào)度§2.10死鎖第二章進(jìn)程及處理機(jī)管理第二章進(jìn)程及處理機(jī)管理——§2.1進(jìn)程的提出一、程序的執(zhí)行1前趨圖前趨圖指的是有向無循環(huán)圖。在這里，我們用前趨圖表示系統(tǒng)在某個(gè)時(shí)間完成工作的流程。在圖中，結(jié)點(diǎn)表示一條語句、一個(gè)程序段落或一個(gè)程序。有向邊表示結(jié)點(diǎn)之間的偏序或前趨關(guān)系。前趨圖是無循環(huán)的圖。必然有一個(gè)結(jié)點(diǎn)沒有前趨，一個(gè)結(jié)點(diǎn)沒有后繼

第二章進(jìn)程及處理機(jī)管理——§2.1進(jìn)程的提出一、程序的執(zhí)行2程序順序執(zhí)行（1）順序性：（2）封閉型（3）程序的執(zhí)行結(jié)果與速度和時(shí)間沒有關(guān)系。（4）可再現(xiàn)性3程序并發(fā)執(zhí)行（1）間斷性（2）失去封閉性（3）不可再現(xiàn)性（4）．通信性

（5）．程序與執(zhí)行過程不再一一對應(yīng)二、進(jìn)程的引入資源分配的單位不再是程序程序與執(zhí)行過程不再是一一對應(yīng)一個(gè)程序的多個(gè)運(yùn)行過程中資源分配第二章進(jìn)程及處理機(jī)管理——

§2.2進(jìn)程的定義和特征一、進(jìn)程的定義1進(jìn)程是指程序的一次執(zhí)行過程。2進(jìn)程定義為一個(gè)數(shù)據(jù)結(jié)構(gòu)和能在其上進(jìn)行操作。3進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程。4進(jìn)程是系統(tǒng)資源進(jìn)行分配和調(diào)度的一個(gè)獨(dú)立單位。5指可并發(fā)執(zhí)行的程序，在一個(gè)數(shù)據(jù)集合上運(yùn)行過程。進(jìn)程是一個(gè)正在執(zhí)行中的程序

（不正確的一個(gè)意思，但可以作為一種今后學(xué)習(xí)上的參考解釋）第二章進(jìn)程及處理機(jī)管理——

§2.2進(jìn)程的定義和特征二、進(jìn)程的特征1動態(tài)性：指的是程序的一次執(zhí)行過程，是一個(gè)動態(tài)的概念，而程序只是指的指令序列的集合，沒有運(yùn)行（運(yùn)動）的含義。因此，程序是靜態(tài)的。2并發(fā)性：指進(jìn)程之間是可以并發(fā)執(zhí)行的。3獨(dú)立性：指進(jìn)程是一個(gè)獨(dú)立運(yùn)行的、獨(dú)立分配資源的單位。4異步性：進(jìn)程之間按各自的、不可預(yù)知的速度向前推進(jìn)。5結(jié)構(gòu)特征：進(jìn)程是有一定的組成成分，而且有一定的結(jié)構(gòu)形式，簡單地說進(jìn)程是由程序+數(shù)據(jù)+進(jìn)程控制塊組成的，而進(jìn)程控制塊是使計(jì)算機(jī)系統(tǒng)識別該進(jìn)程、運(yùn)行該進(jìn)程的一個(gè)唯一標(biāo)志，這在后面我們將要提到。第二章進(jìn)程及處理機(jī)管理——

§2.2進(jìn)程的定義和特征進(jìn)程樹在這里，我們還應(yīng)該注意到，進(jìn)程是一個(gè)程序的運(yùn)行過程，這其中會包含兩種情況：一是該進(jìn)程是系統(tǒng)要求執(zhí)行的。另一個(gè)是該進(jìn)程所包含的程序是另一個(gè)程序的子程序，該進(jìn)程的執(zhí)行是另一個(gè)程序要求執(zhí)行的。所以，在系統(tǒng)中，進(jìn)程和進(jìn)程之間是有一定關(guān)聯(lián)的。這種關(guān)聯(lián)的形式我們可以用進(jìn)程樹來表示。第二章進(jìn)程及處理機(jī)管理——

§2.3進(jìn)程的狀態(tài)和進(jìn)程控制塊一、進(jìn)程的狀態(tài)1基本狀態(tài)（1）執(zhí)行狀態(tài)進(jìn)程已經(jīng)獲得了處理機(jī)（CPU），其程序正在運(yùn)行。（2）阻塞狀態(tài)（等待狀態(tài)）正在執(zhí)行的進(jìn)程，由于發(fā)生某事件而暫時(shí)無法執(zhí)行時(shí)，而放棄處理進(jìn)入暫停狀態(tài)。（3）就緒狀態(tài)已經(jīng)完成暫停，在沒有得到CPU前所處的狀態(tài)2擴(kuò)充狀態(tài)（1）執(zhí)行狀態(tài)（2）活動阻塞狀態(tài)（3）靜止阻塞狀態(tài)（4）活動就緒狀態(tài)（5）靜止就緒狀態(tài)第二章進(jìn)程及處理機(jī)管理——

§2.3進(jìn)程的狀態(tài)和進(jìn)程控制塊二、進(jìn)程控制塊1進(jìn)程控制塊進(jìn)程控制塊其英文名稱為ProcessControlBlock，簡稱PCB。是使計(jì)算機(jī)系統(tǒng)感知進(jìn)程存在的唯一依據(jù)，是描述和控制進(jìn)程的執(zhí)行過程的一個(gè)數(shù)據(jù)結(jié)構(gòu)。2進(jìn)程控制塊的結(jié)構(gòu)（1）．進(jìn)程標(biāo)識符（進(jìn)程內(nèi)部名稱）（2）．現(xiàn)行狀態(tài)（3）．現(xiàn)場保留區(qū)（4）．程序和數(shù)據(jù)地址（5）．互斥與同步結(jié)構(gòu)：（6）．進(jìn)程通信機(jī)制：（7）．優(yōu)先級（8）．資源清單（9）．鏈接字（隊(duì)列指針）（10）．家族聯(lián)系第二章進(jìn)程及處理機(jī)管理——

§2.3進(jìn)程的狀態(tài)和進(jìn)程控制塊三、進(jìn)程控制塊組織結(jié)構(gòu)1鏈接方式2索引方式第二章進(jìn)程及處理機(jī)管理——§2.4線程一、線程的引入進(jìn)程擁有資源在進(jìn)程運(yùn)行過程中，資源需要被處理進(jìn)程整體的過程可以由調(diào)度、控制、資源處理等組成分離后，將調(diào)度單獨(dú)完成二、線程的概念線程是進(jìn)程中的一個(gè)實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。三、線程與進(jìn)程（見書P53頁）1調(diào)度

2并發(fā)性

3擁有資源

4系統(tǒng)開銷

第二章進(jìn)程及處理機(jī)管理——

§2.5進(jìn)程控制進(jìn)程的控制指的是進(jìn)程的創(chuàng)建和撤消，以及實(shí)現(xiàn)進(jìn)程的狀態(tài)轉(zhuǎn)換。進(jìn)程控制一般是由操作系統(tǒng)的內(nèi)核完成。內(nèi)核（Kernel）是指基于硬件的第一層軟件，完成操作系統(tǒng)的基本功能的進(jìn)程集合。是由原語設(shè)計(jì)的原語（Primitive）是指機(jī)器指令的延伸，是由若干條機(jī)器指令構(gòu)成的，不可中斷的程序代碼。實(shí)現(xiàn)對進(jìn)程的控制在多數(shù)系統(tǒng)中都提供了六個(gè)原語實(shí)現(xiàn)的。第二章進(jìn)程及處理機(jī)管理——

§2.5進(jìn)程控制創(chuàng)建、撤銷、激活、阻塞、喚醒、掛起第二章進(jìn)程及處理機(jī)管理——

§2.5進(jìn)程控制一、進(jìn)程的創(chuàng)建原語（CreatePrimitive） 1調(diào)用創(chuàng)建原語的情況用戶登錄程序執(zhí)行用戶提出請求而為之提供的服務(wù)應(yīng)用請求 2創(chuàng)建原語描述第二章進(jìn)程及處理機(jī)管理——

§2.5進(jìn)程控制二、進(jìn)程的撤消原語（Destroy

Primitive） 1引起進(jìn)程撤消的情況正常結(jié)束異常結(jié)束外界干擾 2撤消原語描述第二章進(jìn)程及處理機(jī)管理——

§2.5進(jìn)程控制三、進(jìn)程的阻塞原語（Block

Primitive） 1引起進(jìn)程阻塞的原因

（1）請求系統(tǒng)服務(wù)，但沒有得到及時(shí)的響應(yīng)（2）啟動某種Ｉ／Ｏ （3）新數(shù)據(jù)還沒有到來（4）沒有新的工作

2阻塞原語描述第二章進(jìn)程及處理機(jī)管理——

§2.5進(jìn)程控制四、進(jìn)程的喚醒原語（Wakeup

Primitive） 1、某進(jìn)程所請求的事件完成，從阻塞狀態(tài)到就緒狀態(tài)

2、喚醒原語描述第二章進(jìn)程及處理機(jī)管理——

§2.5進(jìn)程控制五、進(jìn)程的掛起原語（Suspend

Primitive） 1當(dāng)需要對正在運(yùn)行的程序進(jìn)行調(diào)試時(shí)，通過掛起原語使其變成靜止的某一種狀態(tài)

2掛起原語描述第二章進(jìn)程及處理機(jī)管理——

§2.5進(jìn)程控制六、進(jìn)程的激活原語（Active

Primitive） 1當(dāng)進(jìn)程調(diào)試完成后，通過激活原語將其投入?yún)⑴c運(yùn)行

2激活原語描述第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步進(jìn)程同步是由于進(jìn)程之間的并發(fā)執(zhí)行造成的一種相互制約、相互協(xié)調(diào)，按一定次序進(jìn)行的現(xiàn)象根據(jù)相互制約的不同形式，可以分為兩種形式的同步：互斥同步和依賴同步。簡稱互斥和同步第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步一、基本概念1臨界資源（CriticalResource）臨界資源指的是計(jì)算機(jī)系統(tǒng)中每次只允許一個(gè)進(jìn)程訪問的資源。計(jì)算機(jī)系統(tǒng)中大部分資源屬于臨界資源。顯示器？鍵盤？2臨界區(qū)（Criticalsection）臨界區(qū)指的是在一個(gè)進(jìn)程中訪問臨界資源的那段代碼。3對于臨界資源的使用兩個(gè)或兩個(gè)以上進(jìn)程不能同時(shí)進(jìn)入自己的臨界區(qū)，訪問臨界資源。這就要求有一個(gè)同步機(jī)制來制約各個(gè)進(jìn)程的執(zhí)行，這個(gè)同步機(jī)制應(yīng)該遵循以下四條準(zhǔn)則：空閑讓進(jìn)。②忙則等待，③有限等待。④讓權(quán)等待。第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步二、互斥同步定義指的是兩個(gè)或兩個(gè)以上的進(jìn)程在共享某一臨界資源時(shí)，所采取的一種協(xié)調(diào)制約形式，即互相排斥地使用臨界資源。實(shí)現(xiàn)方法：硬件機(jī)制信號量機(jī)制管程第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步（互斥）硬件機(jī)制利用計(jì)算機(jī)系統(tǒng)中提供的硬件操作指令來實(shí)現(xiàn)。主要有TS指令和Swap指令1TS指令2Swap指令第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步（互斥）信號量機(jī)制1經(jīng)典信號量機(jī)制（1）信號量（Semaphore）表示資源的物理實(shí)體。定義為一個(gè)整形變量，它的值除初值外只能由P-V操作完成?？梢钥醋魇欠从迟Y源的數(shù)目。也可以看作反映資源可被共享的次數(shù)。

（2）P-V操作P-V操作是兩個(gè)原子操作（Atomicoperation）P（S）和V（S）。利用對信號量S的操作來實(shí)現(xiàn)互斥。

（3）實(shí)現(xiàn)互斥（4）缺陷當(dāng)S<=0時(shí)執(zhí)行P操作，必將使進(jìn)程處于“忙等”狀態(tài)。所謂“忙等”指的是該進(jìn)程無法向下進(jìn)行.但還占用CPU時(shí)間。第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步（互斥）信號量機(jī)制2記錄型信號量機(jī)制（1）信號量（2）P-V操作（3）實(shí)現(xiàn)（4）特點(diǎn)：改進(jìn)了系統(tǒng)運(yùn)行的效率，在進(jìn)程被阻塞的時(shí)候，可以使處理機(jī)繼續(xù)完成其它的任務(wù)，而不是等待第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步（互斥）信號量機(jī)制3信號量集機(jī)制（1）提出的原因（2）解決方案強(qiáng)制資源訪問順序一次性申請（信號量集機(jī)制）第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步三、依賴同步（同步）1概念指的是兩個(gè)合作進(jìn)程，當(dāng)某一進(jìn)程未得到另一個(gè)進(jìn)程發(fā)出來的消息之前處于等待，直到另一個(gè)進(jìn)程發(fā)出來消息后，該進(jìn)程繼續(xù)向下執(zhí)行。2舉例3實(shí)現(xiàn)P-V操作和信號量機(jī)制第二章進(jìn)程及處理機(jī)管理——

§2.6進(jìn)程同步四、說明1進(jìn)程同步是進(jìn)程低級通信的一種形式。

2P-V操作實(shí)質(zhì)和信號量的物理意義

信號量的物理意義是：信號量S表示資源的數(shù)目。當(dāng)S>0時(shí)，S的數(shù)值表示可用資源的個(gè)數(shù)當(dāng)S=0時(shí)，表示當(dāng)前系統(tǒng)已經(jīng)沒有可用資源當(dāng)S<0時(shí)，S的數(shù)值表示當(dāng)前系統(tǒng)缺少的資源個(gè)數(shù)，也可以表示當(dāng)前因?yàn)闆]有申請到資源而被阻塞的進(jìn)程個(gè)數(shù)。P-V操作的實(shí)質(zhì)：在互斥中，P操作表示請求分配一個(gè)資源，V操作表示請求釋放一個(gè)資源在同步中，P操作表示檢測消息是否到來，V操作表示發(fā)送消息。經(jīng)典信號量機(jī)制實(shí)現(xiàn)互斥可以為臨界資源先設(shè)置一個(gè)互斥信號量S，其初始值為該臨界資源的數(shù)目。在進(jìn)程對這個(gè)臨界資源進(jìn)行訪問之前，先執(zhí)行P操作；在退出臨界區(qū)之后執(zhí)行V操做。記錄型信號量機(jī)制實(shí)現(xiàn)互斥記錄型信號量機(jī)制存在的問題信號量集機(jī)制第二章進(jìn)程及處理機(jī)管理——

§2.7幾個(gè)經(jīng)典的進(jìn)程同步問題一、生產(chǎn)者與消費(fèi)者問題其主要思想是一組生產(chǎn)者向一組消費(fèi)者提供信息。他們之間共用同一個(gè)有界緩沖區(qū)

1、有一個(gè)緩沖池，一次只能讓一個(gè)進(jìn)入，不論是生產(chǎn)者還是消費(fèi)者。2、在一個(gè)緩沖池中有多個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)一次也只能由一個(gè)使用3、生產(chǎn)者可以把它的產(chǎn)品放在任何一個(gè)空的緩沖區(qū)中4、消費(fèi)者可以到任何一個(gè)已有產(chǎn)品的緩沖區(qū)中取產(chǎn)品5、生產(chǎn)者只有等到緩沖區(qū)有空的時(shí)候才可以放產(chǎn)品，消費(fèi)者只有當(dāng)緩沖區(qū)有產(chǎn)品的時(shí)候才可以把產(chǎn)品取走生產(chǎn)者與消費(fèi)者問題生產(chǎn)者與消費(fèi)者存在的問題第二章進(jìn)程及處理機(jī)管理——

§2.7幾個(gè)經(jīng)典的進(jìn)程同步問題二、讀者-寫者問題一個(gè)數(shù)據(jù)文件或記錄（統(tǒng)稱為數(shù)據(jù)對象），可被多個(gè)進(jìn)程共享。其中有些進(jìn)程要求讀，而另一些進(jìn)程要求寫或修改。我們把只要求讀的進(jìn)程稱為“讀者”。其他進(jìn)程稱為“寫者”。允許多個(gè)讀者可同時(shí)訪問一個(gè)共享對象，而不允許一個(gè)寫者和其他進(jìn)程（可能是讀者，也可能是寫者）同時(shí)訪問同一個(gè)共享對象。1、讀者之間可以共享使用這個(gè)文件對象2、寫者之間只能有一個(gè)使用這個(gè)文件對象3、當(dāng)一個(gè)寫者在使用的時(shí)候，讀者也不能使用這個(gè)文件讀者-寫者問題解決方案第二章進(jìn)程及處理機(jī)管理——

§2.7幾個(gè)經(jīng)典的進(jìn)程同步問題三、哲學(xué)家進(jìn)餐的問題有五個(gè)哲學(xué)家，他們的生活方式是交替的進(jìn)行思考和進(jìn)餐，哲學(xué)家們共用一張圓桌，周圍放五張椅子，每人坐一張。在圓桌上有五個(gè)碗和五只筷子，當(dāng)一個(gè)哲學(xué)家思考時(shí)，他不與同事交談，饑餓時(shí)便試圖取其左右最靠近他的筷子，但有可能一支都拿不到，只有在他拿到兩支筷子才能進(jìn)餐。餐畢，放下筷子又繼續(xù)思考。哲學(xué)家進(jìn)餐問題解決方案1、用一個(gè)信號量表示一只筷子，共有五個(gè)信號量構(gòu)成信號量數(shù)組2、需要加上一些限制條件，否則容易出現(xiàn)錯(cuò)誤。3、限制條件比如是：至多允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐；僅當(dāng)哲學(xué)家左右兩支筷子都可以用時(shí)，才能拿起進(jìn)餐第二章進(jìn)程及處理機(jī)管理——

§2.7幾個(gè)經(jīng)典的進(jìn)程同步問題四、司機(jī)和售票員問題司機(jī)負(fù)責(zé)汽車的啟動、運(yùn)行和停止；售票員負(fù)責(zé)車門的打開和關(guān)閉。當(dāng)司機(jī)在汽車啟動工作中，售票員是不允許打開車門的；當(dāng)汽車停止的時(shí)候，售票員可以把車門打開；當(dāng)售票員把車門關(guān)閉后，司機(jī)可以啟動汽車。第二章進(jìn)程及處理機(jī)管理——

§2.7幾個(gè)經(jīng)典的進(jìn)程同步問題五、讀、計(jì)算和打印三個(gè)進(jìn)程問題司機(jī)和售票員問題第二章進(jìn)程及處理機(jī)管理——

§2.7幾個(gè)經(jīng)典的進(jìn)程同步問題六、十字路口問題1、東西和南北走向要分開2、在中心有共享區(qū)3、如果有左轉(zhuǎn)問題，解決方案比較復(fù)雜第二章進(jìn)程及處理機(jī)管理——

§2.8進(jìn)程通信在前面我們所介紹的進(jìn)程同步中，不論是互斥還是同步，都可以理解為雙方相互之間的信息傳遞，但傳遞的信息只是一個(gè)消息，沒有數(shù)據(jù)信息的概念，為此，我們把這樣的消息傳遞稱為“低級通信”一、進(jìn)程通信方式1共享存儲的系統(tǒng)（sharedmemorysystem）在這種方式中，相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式基于共享存儲區(qū)的通信方式

第二章進(jìn)程及處理機(jī)管理——

§2.8進(jìn)程通信一、進(jìn)程通信方式2信息系統(tǒng)（Messagesystem）

在這種方式中，進(jìn)程之間通過消息或報(bào)只交換信息，并提供相應(yīng)一組通信命令來實(shí)現(xiàn)通信直接通信方式指發(fā)送進(jìn)程通過系統(tǒng)原語，直接將消息發(fā)送給接收進(jìn)程。通常使用的系統(tǒng)原語是：send（receiver，message）和receive（sender，message）。間接通信方式指進(jìn)程之間的通信，需要借助一個(gè)數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。3利用共享文件的通信方式

間接通信中的數(shù)據(jù)結(jié)構(gòu)——信箱信箱頭包含信箱的名稱、大小、安全等信息；信箱體是用來存放通信數(shù)據(jù)的。信箱通信是根據(jù)系統(tǒng)提供的一些控制原語來完成。這些控制原語包括創(chuàng)建和撤消信箱、發(fā)送和接收消息等。例如：send（mailbox，message）、receive（mailbox，message）。信箱分為：私有信箱、公用信箱、共享信箱。根據(jù)信箱通信的方式，通信進(jìn)程之間存在有：一對一關(guān)系、多對一關(guān)系、一對多關(guān)系和多對多關(guān)系實(shí)際例子1、每個(gè)接收者都有一個(gè)以自己ID為標(biāo)識的信箱2、每個(gè)發(fā)送者都可以把信件放在接收者的信箱中3、與其它共享存儲區(qū)不同的是信箱是統(tǒng)一管理的，發(fā)送者和接收者都不需要考慮對信箱的管理問題第二章進(jìn)程及處理機(jī)管理——

§2.8進(jìn)程通信二、進(jìn)程通信實(shí)例-消息緩沖隊(duì)列通信機(jī)制

第二章進(jìn)程及處理機(jī)管理——

§2.9處理機(jī)調(diào)度處理機(jī)調(diào)度是進(jìn)程及處理機(jī)管理功能中的最后一個(gè)。由于在計(jì)算機(jī)系統(tǒng)中處于就緒狀態(tài)的進(jìn)程很多，如何調(diào)度它們使之運(yùn)行，并且還能充分提高處理機(jī)的利用率和改善系統(tǒng)性能，成為現(xiàn)代操作系統(tǒng)中的一個(gè)中心問題。

一、進(jìn)程調(diào)度的功能和方式1進(jìn)程調(diào)度的功能：i.記住進(jìn)程的狀態(tài)ii.決定某個(gè)進(jìn)程什么時(shí)候得到處理機(jī)，占用多長時(shí)間iii.執(zhí)行把處理機(jī)分配進(jìn)程iv.讓出處理機(jī)2進(jìn)程調(diào)度方式：指的是當(dāng)一進(jìn)程正在處理機(jī)上運(yùn)行時(shí)，若有某個(gè)更為重要的或緊迫的進(jìn)程到來時(shí)，該如何分配處理機(jī)通常有兩種調(diào)度方式：i.非剝奪方式ii.

剝奪方式第二章進(jìn)程及處理機(jī)管理——

§2.9處理機(jī)調(diào)度二、調(diào)度算法1先進(jìn)先出（FIFO）算法2最短cup運(yùn)行期優(yōu)先調(diào)度算法（SCBF）3最高優(yōu)先權(quán)（FPF）優(yōu)先調(diào)度算法靜態(tài)優(yōu)先級動態(tài)優(yōu)先級4輪轉(zhuǎn)法簡單輪轉(zhuǎn)法多級隊(duì)列輪轉(zhuǎn)法多級反饋隊(duì)列輪轉(zhuǎn)法第二章進(jìn)程及處理機(jī)管理——§2.10死鎖死鎖指的是當(dāng)某個(gè)進(jìn)程提出資源申請后，使得若干進(jìn)程在無外力作用下永遠(yuǎn)不能繼續(xù)執(zhí)行。產(chǎn)生死鎖的原因和條件如何解除和預(yù)防避免出現(xiàn)死鎖。

第二章進(jìn)程及處理機(jī)管理——§2.10死鎖一、產(chǎn)生死鎖的原因和必要條件1產(chǎn)生死鎖的原因：資源引起死鎖：由于共享資源數(shù)目不夠。進(jìn)程推進(jìn)順序不當(dāng)引起死鎖2產(chǎn)生死鎖的必要條件：互斥條件：即共享資源一次只能為一個(gè)進(jìn)程占有。請求與保持條件：即進(jìn)程一旦擁有某一共享資源，就不會在使用過程中自動釋放，即使在被阻塞時(shí)也不釋放。不剝奪條件：即進(jìn)程已獲得某一資源，在未使用完之前不能被剝奪。環(huán)路條件：在發(fā)生死鎖時(shí)，必然會出現(xiàn)進(jìn)程——資源的環(huán)形鏈。注意：環(huán)路條件既是必要條件，又是充分條件。

第二章進(jìn)程及處理機(jī)管理——§2.10死鎖二、預(yù)防死鎖1屏棄‘請求和保持’條件：采取系統(tǒng)要求進(jìn)程一次性的申請所需的所有資源。2屏棄‘不剝奪’條件：采取進(jìn)程得不到新請求的資源，則將已請求到的資源釋放。3屏棄‘環(huán)路條件’采取系統(tǒng)中所有資源排隊(duì)排號，進(jìn)程在請求資源時(shí)要嚴(yán)格按照資源序號遞增的順序。第二章進(jìn)程及處理機(jī)管理——§2.10死鎖三、避免死鎖1安全狀態(tài)：指系統(tǒng)能按某種進(jìn)程順序如（P1，P2，P3．．．Pn），來為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可順序完成。這時(shí)（P1，P2，P3．．．Pn）序列我們稱為安全序列。2不安全狀態(tài)：若系統(tǒng)中不存在一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。銀行家算法1數(shù)據(jù)結(jié)構(gòu)2銀行家算法描述設(shè)request(j)是進(jìn)程P(i)的請求向量。如果request[j]=k，表示進(jìn)程P(i)需要k個(gè)R(j)類資源。

3安全性算法設(shè)置兩個(gè)向量Work和FinishWork表示可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素。其初始值work=available。finish表示是否有足夠的資源分配給進(jìn)程。其初始值finish[i]=false.

銀行家算法——舉例假定系統(tǒng)中有五個(gè)進(jìn)程{p0,p1,p2,p3,p4}和三類資源{a,b,c},各類資源總數(shù)量分別為10，5，7。在t0時(shí)刻的資源分配情況如下MaxAllocationNeedavailableABCABCABCABcP0753010743332P1322200122P2902302600P3222211011p44330024311t0時(shí)刻是否安全？2P1發(fā)出請求向量request(p1)={1,0,2}，是否進(jìn)行分配？3P4發(fā)出請求向量request(p4)={3,3,0}，是否進(jìn)行分配？4P0發(fā)出請求向量request(p0)={0,2,0}，是否進(jìn)行分配？5P0發(fā)出請求向量request(p0)={0,1,0}，是否進(jìn)行分配？第二章進(jìn)程及處理機(jī)管理——§2.10死鎖四、檢測死鎖1資源狀態(tài)圖該圖n各結(jié)點(diǎn)和f組邊構(gòu)成，G(N,E)具有如下定義：n被分成兩個(gè)獨(dú)立的子集，一組為進(jìn)程結(jié)點(diǎn)Ｐ＝（p1，p2，p3．．．Pn)，一組為資源結(jié)點(diǎn)Ｒ＝（r1，r2，r3．．．rn）對于邊e∈E，都連接著Ｐ中的一個(gè)