操作系統(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)程同步問(wèn)題§2.8進(jìn)程的通信§2.9處理機(jī)調(diào)度§2.10死鎖第二章進(jìn)程及處理機(jī)管理第二章進(jìn)程及處理機(jī)管理——§2.1進(jìn)程的提出一、程序的執(zhí)行1前趨圖前趨圖指的是有向無(wú)循環(huán)圖。在這里，我們用前趨圖表示系統(tǒng)在某個(gè)時(shí)間完成工作的流程。在圖中，結(jié)點(diǎn)表示一條語(yǔ)句、一個(gè)程序段落或一個(gè)程序。有向邊表示結(jié)點(diǎn)之間的偏序或前趨關(guān)系。前趨圖是無(wú)循環(huán)的圖。必然有一個(gè)結(jié)點(diǎn)沒(méi)有前趨，一個(gè)結(jié)點(diǎn)沒(méi)有后繼

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

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

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

（不正確的一個(gè)意思，但可以作為一種今后學(xué)習(xí)上的參考解釋?zhuān)┑诙逻M(jìn)程及處理機(jī)管理——

§2.2進(jìn)程的定義和特征二、進(jìn)程的特征1動(dòng)態(tài)性：指的是程序的一次執(zhí)行過(guò)程，是一個(gè)動(dòng)態(tài)的概念，而程序只是指的指令序列的集合，沒(méi)有運(yùn)行（運(yùn)動(dòng)）的含義。因此，程序是靜態(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)形式，簡(jiǎn)單地說(shuō)進(jìn)程是由程序+數(shù)據(jù)+進(jìn)程控制塊組成的，而進(jìn)程控制塊是使計(jì)算機(jī)系統(tǒng)識(shí)別該進(jìn)程、運(yùn)行該進(jìn)程的一個(gè)唯一標(biāo)志，這在后面我們將要提到。第二章進(jìn)程及處理機(jī)管理——

§2.2進(jìn)程的定義和特征進(jìn)程樹(shù)在這里，我們還應(yīng)該注意到，進(jìn)程是一個(gè)程序的運(yùn)行過(guò)程，這其中會(huì)包含兩種情況：一是該進(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)程樹(shù)來(lái)表示。第二章進(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í)無(wú)法執(zhí)行時(shí)，而放棄處理進(jìn)入暫停狀態(tài)。（3）就緒狀態(tài)已經(jīng)完成暫停，在沒(méi)有得到CPU前所處的狀態(tài)2擴(kuò)充狀態(tài)（1）執(zhí)行狀態(tài)（2）活動(dòng)阻塞狀態(tài)（3）靜止阻塞狀態(tài)（4）活動(dòng)就緒狀態(tài)（5）靜止就緒狀態(tài)第二章進(jìn)程及處理機(jī)管理——

§2.3進(jìn)程的狀態(tài)和進(jìn)程控制塊二、進(jìn)程控制塊1進(jìn)程控制塊進(jìn)程控制塊其英文名稱(chēng)為ProcessControlBlock，簡(jiǎn)稱(chēng)PCB。是使計(jì)算機(jī)系統(tǒng)感知進(jìn)程存在的唯一依據(jù)，是描述和控制進(jìn)程的執(zhí)行過(guò)程的一個(gè)數(shù)據(jù)結(jié)構(gòu)。2進(jìn)程控制塊的結(jié)構(gòu)（1）．進(jìn)程標(biāo)識(shí)符（進(jìn)程內(nèi)部名稱(chēng)）（2）．現(xiàn)行狀態(tài)（3）．現(xiàn)場(chǎng)保留區(qū)（4）．程序和數(shù)據(jù)地址（5）．互斥與同步結(jié)構(gòu)：（6）．進(jìn)程通信機(jī)制：（7）．優(yōu)先級(jí)（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)行過(guò)程中，資源需要被處理進(jìn)程整體的過(guò)程可以由調(diào)度、控制、資源處理等組成分離后，將調(diào)度單獨(dú)完成二、線程的概念線程是進(jìn)程中的一個(gè)實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。三、線程與進(jìn)程（見(jiàn)書(shū)P53頁(yè)）1調(diào)度

2并發(fā)性

3擁有資源

4系統(tǒng)開(kāi)銷(xiāo)

第二章進(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)程集合。是由原語(yǔ)設(shè)計(jì)的原語(yǔ)（Primitive）是指機(jī)器指令的延伸，是由若干條機(jī)器指令構(gòu)成的，不可中斷的程序代碼。實(shí)現(xiàn)對(duì)進(jìn)程的控制在多數(shù)系統(tǒng)中都提供了六個(gè)原語(yǔ)實(shí)現(xiàn)的。第二章進(jìn)程及處理機(jī)管理——

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§2.6進(jìn)程同步一、基本概念1臨界資源（CriticalResource）臨界資源指的是計(jì)算機(jī)系統(tǒng)中每次只允許一個(gè)進(jìn)程訪問(wèn)的資源。計(jì)算機(jī)系統(tǒng)中大部分資源屬于臨界資源。顯示器？鍵盤(pán)？2臨界區(qū)（Criticalsection）臨界區(qū)指的是在一個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼。3對(duì)于臨界資源的使用兩個(gè)或兩個(gè)以上進(jìn)程不能同時(shí)進(jìn)入自己的臨界區(qū)，訪問(wèn)臨界資源。這就要求有一個(gè)同步機(jī)制來(lái)制約各個(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ī)制信號(hào)量機(jī)制管程第二章進(jìn)程及處理機(jī)管理——

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

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

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

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

§2.6進(jìn)程同步（互斥）信號(hào)量機(jī)制2記錄型信號(hào)量機(jī)制（1）信號(hào)量（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)程同步（互斥）信號(hào)量機(jī)制3信號(hào)量集機(jī)制（1）提出的原因（2）解決方案強(qiáng)制資源訪問(wèn)順序一次性申請(qǐng)（信號(hào)量集機(jī)制）第二章進(jìn)程及處理機(jī)管理——

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

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

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

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

§2.7幾個(gè)經(jīng)典的進(jìn)程同步問(wèn)題一、生產(chǎn)者與消費(fèi)者問(wèn)題其主要思想是一組生產(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)者問(wèn)題生產(chǎn)者與消費(fèi)者存在的問(wèn)題第二章進(jìn)程及處理機(jī)管理——

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

§2.7幾個(gè)經(jīng)典的進(jìn)程同步問(wèn)題三、哲學(xué)家進(jìn)餐的問(wèn)題有五個(gè)哲學(xué)家，他們的生活方式是交替的進(jìn)行思考和進(jìn)餐，哲學(xué)家們共用一張圓桌，周?chē)盼鍙堃巫?，每人坐一張。在圓桌上有五個(gè)碗和五只筷子，當(dāng)一個(gè)哲學(xué)家思考時(shí)，他不與同事交談，饑餓時(shí)便試圖取其左右最靠近他的筷子，但有可能一支都拿不到，只有在他拿到兩支筷子才能進(jìn)餐。餐畢，放下筷子又繼續(xù)思考。哲學(xué)家進(jìn)餐問(wèn)題解決方案1、用一個(gè)信號(hào)量表示一只筷子，共有五個(gè)信號(hào)量構(gòu)成信號(hào)量數(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)程同步問(wèn)題四、司機(jī)和售票員問(wèn)題司機(jī)負(fù)責(zé)汽車(chē)的啟動(dòng)、運(yùn)行和停止；售票員負(fù)責(zé)車(chē)門(mén)的打開(kāi)和關(guān)閉。當(dāng)司機(jī)在汽車(chē)啟動(dòng)工作中，售票員是不允許打開(kāi)車(chē)門(mén)的；當(dāng)汽車(chē)停止的時(shí)候，售票員可以把車(chē)門(mén)打開(kāi)；當(dāng)售票員把車(chē)門(mén)關(guān)閉后，司機(jī)可以啟動(dòng)汽車(chē)。第二章進(jìn)程及處理機(jī)管理——

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

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

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

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

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

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

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

一、進(jìn)程調(diào)度的功能和方式1進(jìn)程調(diào)度的功能：i.記住進(jìn)程的狀態(tài)ii.決定某個(gè)進(jìn)程什么時(shí)候得到處理機(jī)，占用多長(zhǎng)時(shí)間iii.執(zhí)行把處理機(jī)分配進(jìn)程iv.讓出處理機(jī)2進(jìn)程調(diào)度方式：指的是當(dāng)一進(jìn)程正在處理機(jī)上運(yùn)行時(shí)，若有某個(gè)更為重要的或緊迫的進(jìn)程到來(lái)時(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)先級(jí)動(dòng)態(tài)優(yōu)先級(jí)4輪轉(zhuǎn)法簡(jiǎn)單輪轉(zhuǎn)法多級(jí)隊(duì)列輪轉(zhuǎn)法多級(jí)反饋隊(duì)列輪轉(zhuǎn)法第二章進(jìn)程及處理機(jī)管理——§2.10死鎖死鎖指的是當(dāng)某個(gè)進(jìn)程提出資源申請(qǐng)后，使得若干進(jìn)程在無(wú)外力作用下永遠(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)程占有。請(qǐng)求與保持條件：即進(jìn)程一旦擁有某一共享資源，就不會(huì)在使用過(guò)程中自動(dòng)釋放，即使在被阻塞時(shí)也不釋放。不剝奪條件：即進(jìn)程已獲得某一資源，在未使用完之前不能被剝奪。環(huán)路條件：在發(fā)生死鎖時(shí)，必然會(huì)出現(xiàn)進(jìn)程——資源的環(huán)形鏈。注意：環(huán)路條件既是必要條件，又是充分條件。

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

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

銀行家算法——舉例假定系統(tǒng)中有五個(gè)進(jìn)程{p0,p1,p2,p3,p4}和三類(lèi)資源{a,b,c},各類(lèi)資源總數(shù)量分別為10，5，7。在t0時(shí)刻的資源分配情況如下MaxAllocationNeedavailableABCABCABCABcP0753010743332P1322200122P2902302600P3222211011p44330024311t0時(shí)刻是否安全？2P1發(fā)出請(qǐng)求向量request(p1)={1,0,2}，是否進(jìn)行分配？3P4發(fā)出請(qǐng)求向量request(p4)={3,3,0}，是否進(jìn)行分配？4P0發(fā)出請(qǐng)求向量request(p0)={0,2,0}，是否進(jìn)行分配？5P0發(fā)出請(qǐng)求向量request(p0)={0,1,0}，是否進(jìn)行分配？第二章進(jìn)程及處理機(jī)管理——§2.10死鎖四、檢測(cè)死鎖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）對(duì)于邊e∈E，都連接著Ｐ中的一個(gè)