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

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

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

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

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

（不正確的一個意思，但可以作為一種今后學習上的參考解釋）第二章進程及處理機管理——

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

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

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

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

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

2并發(fā)性

3擁有資源

4系統(tǒng)開銷

第二章進程及處理機管理——

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

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

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

§2.5進程控制二、進程的撤消原語（Destroy

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

§2.5進程控制三、進程的阻塞原語（Block

Primitive） 1引起進程阻塞的原因

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

2阻塞原語描述第二章進程及處理機管理——

§2.5進程控制四、進程的喚醒原語（Wakeup

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

2、喚醒原語描述第二章進程及處理機管理——

§2.5進程控制五、進程的掛起原語（Suspend

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

2掛起原語描述第二章進程及處理機管理——

§2.5進程控制六、進程的激活原語（Active

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

2激活原語描述第二章進程及處理機管理——

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第二章進程及處理機管理——

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

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

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

§2.8進程通信二、進程通信實例-消息緩沖隊列通信機制

第二章進程及處理機管理——

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

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

剝奪方式第二章進程及處理機管理——

§2.9處理機調(diào)度二、調(diào)度算法1先進先出（FIFO）算法2最短cup運行期優(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)法多級隊列輪轉(zhuǎn)法多級反饋隊列輪轉(zhuǎn)法第二章進程及處理機管理——§2.10死鎖死鎖指的是當某個進程提出資源申請后，使得若干進程在無外力作用下永遠不能繼續(xù)執(zhí)行。產(chǎn)生死鎖的原因和條件如何解除和預(yù)防避免出現(xiàn)死鎖。

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

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

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

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