OS3處理機(jī)管理.ppt

1、操作系統(tǒng)Operating System,第3章 處理機(jī)管理,本章重點(diǎn),進(jìn)程的概念、特征 進(jìn)程控制、進(jìn)程調(diào)度、進(jìn)程同步與互斥 死鎖問題,主要內(nèi)容,3.1 進(jìn)程的定義和特征 3.2 進(jìn)程的描述 3.3 進(jìn) 程 控 制 3.4 進(jìn)程調(diào)度 3.5 進(jìn)程的同步與互斥 3.6 線 程 3.7 死 鎖 問 題,處理器(CPU)是程序的執(zhí)行機(jī)構(gòu)，用戶要求計(jì)算機(jī)完成一項(xiàng)作業(yè)，首先必須將作業(yè)程序調(diào)入內(nèi)存，再由處理器逐條執(zhí)行程序指令 處理器管理就是要解決用戶提交的作業(yè)何時(shí)調(diào)入內(nèi)存，在調(diào)入內(nèi)存的各個(gè)作業(yè)程序間如何分配處理器，以達(dá)到各道程序能協(xié)調(diào)一致運(yùn)行，而系統(tǒng)資源又能得到最大程度的利用.,3.1 進(jìn)程的定義和特征,

2、3.3.1. 進(jìn)程的引入 1）多道程序系統(tǒng)中允許多道程序存放在內(nèi)存中，并在系統(tǒng)中同時(shí)處于運(yùn)行狀態(tài)。這些并行執(zhí)行的程序之間存在著相互依賴、相互制約的關(guān)系。 另外，不論是系統(tǒng)程序還是用戶程序，由于它們并行地在著系統(tǒng)中運(yùn)行，并且有著各種復(fù)雜的制約關(guān)系，所以它們?cè)谙到y(tǒng)內(nèi)部所處的狀態(tài)不斷發(fā)生變化，時(shí)而在CPU上執(zhí)行，時(shí)而因某種原因被暫停執(zhí)行。由于在這樣一個(gè)多道程序系統(tǒng)所帶來的復(fù)雜環(huán)境中，使程序具有了并行、制約和動(dòng)態(tài)的特性，使得原來的程序難以刻劃和反映系統(tǒng)中的每一瞬間的狀況。因此，需要引進(jìn)一個(gè)新的概念進(jìn)程。,2）程序和機(jī)器執(zhí)行程序的活動(dòng)是兩個(gè)概念。程序是指令的有序集合，是靜態(tài)的概念，而機(jī)器執(zhí)行程序的活動(dòng)是

3、指指令序列在處理機(jī)上的執(zhí)行過程，或處理機(jī)按照程序執(zhí)行指令序列的過程。而且由于競爭資源等其他因素，程序執(zhí)行時(shí)走走停停，具有“執(zhí)行暫停執(zhí)行”的活動(dòng)規(guī)律。所以就無法用“程序”這個(gè)靜態(tài)的概念來描述程序運(yùn)行的過程，為此，引入了一個(gè)新的一個(gè)動(dòng)態(tài)的概念“進(jìn)程”,2進(jìn)程的定義 (1) 進(jìn)程是程序的一次執(zhí)行。 (2) 進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算。 (3) 進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序在某個(gè)數(shù)據(jù)集上的一次執(zhí)行活動(dòng)，它可以和同樣的其它程序共行。 (4) 進(jìn)程是一個(gè)程序及數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。 (5) 進(jìn)程是程序在一個(gè)數(shù)據(jù)集上的運(yùn)行過程，是系統(tǒng)可調(diào)度的實(shí)體。 據(jù)此，我們可把“進(jìn)程”定義為“

4、可與其它程序并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集上的執(zhí)行過程”。,3進(jìn)程的特征 (1) 動(dòng)態(tài)性 進(jìn)程是進(jìn)程實(shí)體的執(zhí)行過程，因此，動(dòng)態(tài)性是進(jìn)程的最基本特征。動(dòng)態(tài)性還表現(xiàn)為進(jìn)程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，因得不到資源而暫停，因撤消而消亡?？梢?，進(jìn)程是有生命期的。而程序只是存放在某種介質(zhì)上的一組有序指令的集合，本身并無運(yùn)動(dòng)的含意，程序只是個(gè)靜態(tài)實(shí)體。 (2) 并發(fā)性 這是指多個(gè)進(jìn)程實(shí)體同時(shí)存在于系統(tǒng)中，并能在一段時(shí)間內(nèi)同時(shí)執(zhí)行，并發(fā)性是進(jìn)程最重要的特征，同時(shí)也是操作系統(tǒng)的重要特征。,(3) 獨(dú)立性 這是指進(jìn)程實(shí)體是一個(gè)能夠獨(dú)立運(yùn)行的基本單位，同時(shí)也是系統(tǒng)中獨(dú)立獲得資源和獨(dú)立調(diào)度的基本單位。 (4) 異步性 這

5、是指進(jìn)程按各自獨(dú)立的不可預(yù)知的速度向前推進(jìn)，或者說，進(jìn)程按異步方式運(yùn)行。這是由于進(jìn)程間共享資源和協(xié)同合作時(shí)帶來了相互間制約的關(guān)系，造成進(jìn)程執(zhí)行的間斷性。 (5)結(jié)構(gòu)特性 從結(jié)構(gòu)上看，進(jìn)程實(shí)體是由程序段、數(shù)據(jù)段及進(jìn)程控制塊3部分組成，也可把這3部分稱為“進(jìn)程映象”。,返回本節(jié),進(jìn)程與程序的區(qū)別與聯(lián)系,進(jìn)程是程序的一次執(zhí)行，是一個(gè)動(dòng)態(tài)的概念，程序是完成某個(gè)特定功能的指令的有序序列，是一個(gè)靜態(tài)的概念 進(jìn)程和程序不再是一一對(duì)應(yīng)關(guān)系。 進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位，程序則不是 程序可以作為一種軟件資源長期保存，而進(jìn)程是程序的一次執(zhí)行過程，它是臨時(shí)的，有生命期的 進(jìn)程是具有結(jié)構(gòu)的,3.2 進(jìn)

6、程的描述,3.2.1. 進(jìn)程的表示 (1) 進(jìn)程實(shí)體的組成 (2) 進(jìn)程控制塊(PCB) 為描述進(jìn)程的動(dòng)態(tài)變化， 便于系統(tǒng)對(duì)進(jìn)程進(jìn)行有 效地控制和管理，系統(tǒng) 中為每一進(jìn)程設(shè)置了一個(gè)進(jìn)程控制塊。進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志。創(chuàng)建一個(gè)進(jìn)程就是為其建立一個(gè)PCB，當(dāng)進(jìn)程被撤消時(shí)，系統(tǒng)就回收它的PCB。,內(nèi)容回顧,進(jìn)程的引入 程序的并發(fā)執(zhí)行使得程序之間相互制約，程序的執(zhí)行并不是一氣呵成，而是以一種“執(zhí)行-暫停-執(zhí)行”的狀態(tài)執(zhí)行。對(duì)于這種動(dòng)態(tài)的執(zhí)行狀態(tài)，用已不能用程序這一靜態(tài)的概念來描述其具體執(zhí)行過程，因此引入新的概念進(jìn)程。 進(jìn)程的定義 可與其它程序并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集上的執(zhí)行過程 進(jìn)程的特點(diǎn)：

7、 動(dòng)態(tài)、并發(fā)、獨(dú)立、異步、結(jié)構(gòu)特征,(1) 進(jìn)程的基本調(diào)度狀態(tài) 進(jìn)程有3種基本調(diào)度狀態(tài)，具體說明如下。 執(zhí)行狀態(tài)(executing)。進(jìn)程已獲得必要的資源，并已占有處理機(jī)，在其上執(zhí)行該進(jìn)程的程序。 就緒狀態(tài)(ready)。進(jìn)程本身已具備了執(zhí)行條件，即已獲得除CPU之外其它所必需的資源，而正在等待分配處理機(jī)。有時(shí)也稱此狀態(tài)為可執(zhí)行狀態(tài)。 阻塞狀態(tài)(blocked)。進(jìn)程因等待資源或等待某一事件(如某一I/O操作完成)而處于不可執(zhí)行的狀態(tài)，也可以說，進(jìn)程本身的執(zhí)行條件不滿足，即使為它分配CPU也不能在其上執(zhí)行。,3.2.2. 進(jìn)程的基本調(diào)度狀態(tài)及其轉(zhuǎn)換,(2) 進(jìn)程狀態(tài)間的轉(zhuǎn)換,圖3.5 進(jìn)程狀

8、態(tài)的轉(zhuǎn)換,返回本節(jié),進(jìn)程調(diào)度狀態(tài)轉(zhuǎn)換,就緒,運(yùn)行,阻塞,作業(yè)管理,進(jìn)程調(diào)度,I/O要求,I/O完成,時(shí)間到,完成,在單處理器系統(tǒng)中，任何時(shí)刻只有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)，其他進(jìn)程分別處于就緒或阻塞狀態(tài) 為了調(diào)度方便，通常將處于就緒進(jìn)程的PCB（進(jìn)程控制塊）構(gòu)成一就緒隊(duì)列 按各種阻塞原因的PCB構(gòu)成多個(gè)阻塞隊(duì)列,三個(gè)基本狀態(tài)之間可能轉(zhuǎn)換和轉(zhuǎn)換原因如下： 就緒態(tài)執(zhí)行態(tài)：當(dāng)處理機(jī)空閑時(shí)，進(jìn)程調(diào)度程序必將處理機(jī)分配給一個(gè)處于就緒態(tài)的進(jìn)程 ，該進(jìn)程便由就緒態(tài)轉(zhuǎn)換為執(zhí)行態(tài)。 執(zhí)行態(tài)阻塞態(tài)：處于執(zhí)行態(tài)的進(jìn)程在運(yùn)行過程中需要等待某一事件發(fā)生后（例如因IO請(qǐng)求等待IO完成后），才能繼續(xù)運(yùn)行，則該進(jìn)程放棄處理機(jī)，從執(zhí)

9、行態(tài)轉(zhuǎn)換為阻塞態(tài)。,返回本節(jié)目錄,阻塞態(tài)就緒態(tài)：處于阻塞態(tài)的進(jìn)程，若其等待的事件已經(jīng)發(fā)生，于是進(jìn)程由阻塞態(tài)轉(zhuǎn)換為就緒態(tài)。 執(zhí)行態(tài)就緒態(tài)：處于執(zhí)行狀態(tài)的進(jìn)程在其運(yùn)行過程中，因分給它的處理機(jī)時(shí)間片已用完，而不得不讓出（被搶占）處理機(jī)，于是進(jìn)程由執(zhí)行態(tài)轉(zhuǎn)換為就緒態(tài)。 而阻塞態(tài)執(zhí)行態(tài)和就緒態(tài)阻塞態(tài)這二種狀態(tài)轉(zhuǎn)換不可能發(fā)生。,處于執(zhí)行態(tài)進(jìn)程:如系統(tǒng)有一個(gè)處理機(jī)，則在任何一時(shí)刻，最多只有一個(gè)進(jìn)程處于執(zhí)行態(tài)。 處于就緒態(tài)進(jìn)程:一般處于就緒態(tài)的進(jìn)程按照一定的算法（如先來的進(jìn)程排在前面，或采用優(yōu)先權(quán)高的進(jìn)程排在前面）排成一個(gè)就緒隊(duì)列。 處于阻塞態(tài)進(jìn)程:處于阻塞態(tài)的進(jìn)程排在阻塞隊(duì)列中。由于等待事件原因不同，阻塞隊(duì)

10、列也按事件分成幾個(gè)隊(duì)列。,例：一個(gè)只有一個(gè)處理機(jī)的系統(tǒng)中，OS的進(jìn)程有執(zhí)行、就緒、阻塞三個(gè)基本狀態(tài)。假如某時(shí)刻該系統(tǒng)中有10個(gè)進(jìn)程并發(fā)執(zhí)行，在略去調(diào)度程序所占用時(shí)間情況下試問： 這時(shí)刻系統(tǒng)中處于執(zhí)行態(tài)的進(jìn)程數(shù)最多有幾個(gè)？最少有幾個(gè)？ 這時(shí)刻系統(tǒng)中處于就緒態(tài)的進(jìn)程數(shù)最多有幾個(gè)？最少有幾個(gè)？ 這時(shí)刻系統(tǒng)中處于阻塞態(tài)的進(jìn)程數(shù)最多有幾個(gè)？最少有幾個(gè)？,解：因?yàn)橄到y(tǒng)中只有一個(gè)處理機(jī)，所以某時(shí)刻處于執(zhí)行態(tài)的進(jìn)程數(shù)最多只有一個(gè)。而最少可能為0，此時(shí)其它10個(gè)進(jìn)程一定全部排在各阻塞隊(duì)列中，在就緒隊(duì)列中沒有進(jìn)程。而某時(shí)刻處于就緒態(tài)的進(jìn)程數(shù)最多只有9個(gè)，不可能出現(xiàn)10個(gè)情況，因?yàn)橐坏〤PU有空，調(diào)度程序馬上調(diào)度，

11、當(dāng)然這是在略去調(diào)度程序調(diào)度時(shí)間時(shí)考慮。處于阻塞態(tài)的進(jìn)程數(shù)最少是0個(gè)。,3.3 進(jìn) 程 控 制,進(jìn)程控制的作用是對(duì)系統(tǒng)中的全部進(jìn)程實(shí)行有效的管理，主要表現(xiàn)在對(duì)一個(gè)進(jìn)程進(jìn)行創(chuàng)建、撤消以及在某些進(jìn)程狀態(tài)間的轉(zhuǎn)換控制。,返回本章首頁,通常允許一個(gè)進(jìn)程創(chuàng)建和控制另一個(gè)進(jìn)程，前者稱為父進(jìn)程，后者稱為子進(jìn)程。創(chuàng)建父進(jìn)程的進(jìn)程稱為祖父進(jìn)程。子進(jìn)程又可創(chuàng)建孫進(jìn)程，從而形成一個(gè)樹型結(jié)構(gòu)的進(jìn)程家族，如圖3.7所示。,圖3.7 進(jìn)程家族示例,在操作系統(tǒng)中，進(jìn)程之間的控制就是通過進(jìn)程控制原語來實(shí)現(xiàn)的。 原語：原語通常由若干條指令所組成，用來實(shí)現(xiàn)某個(gè)特定的操作。通過一段不可分割的或不可中斷的程序?qū)崿F(xiàn)其功能。,進(jìn)程控制原語

12、(了解),1創(chuàng)建原語 按 調(diào)用者提供的參數(shù)，構(gòu)成該進(jìn)程的PCB 2阻塞原語 中斷該進(jìn)程的運(yùn)行，把PCB中的轉(zhuǎn)態(tài)改為阻塞狀態(tài)。 3激活原語 把某阻塞進(jìn)程置為就緒狀態(tài)，等待分配CPU。 4。撤消原語 停止該進(jìn)程的運(yùn)行，釋放它所占有的所有資源，刪除該進(jìn)程的PCB,內(nèi)容回顧,進(jìn)程的基本狀態(tài) 進(jìn)程狀態(tài)之間的轉(zhuǎn)換 原語:若干條指令所組成，用來實(shí)現(xiàn)某個(gè)特定的操作。,搶占,習(xí)題,1. 在操作系統(tǒng)中進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序在某個(gè)數(shù)據(jù)集合上的一次A，進(jìn)程是一個(gè)B概念，而程序是一個(gè)C的概念。在一單處理機(jī)中，若有5個(gè)用戶進(jìn)程，在某一時(shí)刻，處于就緒狀態(tài)的用戶進(jìn)程最多有D個(gè)，最少有E個(gè)。 A：(1)并發(fā)活動(dòng)；(2

13、)運(yùn)行活動(dòng)；(3)單獨(dú)操作；(4)關(guān)聯(lián)操作。 B，C：(1)組合態(tài)；(2)關(guān)聯(lián)態(tài)；(3)運(yùn)行態(tài)；(4)等待態(tài)；(5)靜態(tài)；(6)動(dòng)態(tài)。 D，E：(1)1；(2)2；(3)3；(4)4；(5)5；(6)0。,習(xí)題-2,2.從靜態(tài)角度看，進(jìn)程由A、B和C三部分組成，用戶可通過D建立和撤消進(jìn)程，通常用戶進(jìn)程被建立后，變處于E狀態(tài)。 A：(1)JCB；(2)DCB；(3)PCB；(4)PMT。 B: (1)程序段；(2)文件體；(3)I/O；(4)子程序。 C：(1)文件描述塊；(2)數(shù)據(jù)；(3)EOF；(4)I/O緩沖區(qū)。 D：(1) 函數(shù)調(diào)用；(2)宏指令；(3)原語；(4)過程調(diào)用。 E: (1

14、)運(yùn)行狀態(tài)(2)就緒狀態(tài)(3)阻塞狀態(tài),3.4 進(jìn)程調(diào)度,3.4.1進(jìn)程調(diào)度的基本概念 進(jìn)程調(diào)度也可被稱為處理機(jī)調(diào)度，它協(xié)調(diào)和控制各進(jìn)程對(duì)CPU的使用。相應(yīng)的進(jìn)程調(diào)度程序叫分派程序或低級(jí)調(diào)度程序。一旦作業(yè)調(diào)度程序選擇了一個(gè)作業(yè)集合來運(yùn)行，系統(tǒng)就要為作業(yè)建立起一組進(jìn)程，這組進(jìn)程協(xié)同運(yùn)行，以便共同完成該作業(yè)的計(jì)算任務(wù)。這樣，在系統(tǒng)中就存在許多進(jìn)程，而這些進(jìn)程具有獲得使用處理機(jī)的可能性，它們同時(shí)在等待獲得處理機(jī)的執(zhí)行時(shí)間，進(jìn)程調(diào)度的職能就是動(dòng)態(tài)且合理地把處理機(jī)分配給就緒隊(duì)列中的某一進(jìn)程，并使該進(jìn)程投入運(yùn)行。,進(jìn)程調(diào)度程序的職能： （1）記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況。 （2）確定分配處理機(jī)的原則。 （

15、3）分配處理機(jī)給進(jìn)程。 （4）從進(jìn)程收回處理機(jī)。,返回本節(jié)目錄,PCB的組織形式 方法有三： （1）線性表：簡單，但進(jìn)程多時(shí)查找速度慢！ （2）鏈接表：相同狀態(tài)的進(jìn)程PCB按優(yōu)先數(shù)排成一個(gè)或多個(gè)隊(duì)列，如就緒隊(duì)列，不同事件的阻塞隊(duì)列,3.4.2 進(jìn)程調(diào)度所用的主要數(shù)據(jù)結(jié)構(gòu),鏈接表組織方式,3.4.3進(jìn)程調(diào)度的方式,調(diào)度類型： 1.高級(jí)調(diào)度（作業(yè)調(diào)度） 2.低級(jí)調(diào)度（進(jìn)程調(diào)度） 進(jìn)程調(diào)度的方式： 剝奪式調(diào)度：當(dāng)系統(tǒng)按照某種原則發(fā)現(xiàn)一個(gè)比現(xiàn)運(yùn)行 進(jìn)程更合適、更應(yīng)該占有CPU的進(jìn)程時(shí)，系統(tǒng)將強(qiáng)迫處于運(yùn)行狀態(tài)的進(jìn)程將CPU的使用權(quán)交給這個(gè)更適合的進(jìn)程。 非剝奪式調(diào)度：一旦某個(gè)進(jìn)程占用了CPU，除非是由于

16、它自身原因自動(dòng)放棄CPU，否則它將一直運(yùn)行下去直到完成,1先來先服務(wù)First-Come-First-Served （FCFS） 這種調(diào)度算法按照進(jìn)程進(jìn)入就緒隊(duì)列的先后順序來調(diào)度進(jìn)程，到達(dá)得越早，其優(yōu)先數(shù)越高。獲得處理機(jī)的進(jìn)程，未遇到其他情況時(shí)，一直運(yùn)行下去，系統(tǒng)只需具備一個(gè)先進(jìn)先出的隊(duì)列，在管理優(yōu)先數(shù)的就緒隊(duì)列時(shí)，這種方法是一種最常見策略，并且在沒有其他信息時(shí)，也是一種最合理的策略。,下一頁,3.4.4 進(jìn)程調(diào)度算法,2輪轉(zhuǎn)調(diào)度 先來先服務(wù)的一個(gè)重要變形，就是輪轉(zhuǎn)規(guī)則。輪轉(zhuǎn)調(diào)度算法是系統(tǒng)把所有就緒進(jìn)程按先后次序排隊(duì)，處理機(jī)總是優(yōu)先分配給就緒隊(duì)列中的第一個(gè)就緒進(jìn)程，并分配它一個(gè)固定的時(shí)間片（如

17、100毫秒）。當(dāng)該運(yùn)行進(jìn)程用完規(guī)定的時(shí)間片時(shí)，被迫釋放處理機(jī)給下一個(gè)處于就緒隊(duì)列中的第一個(gè)進(jìn)程，分給這個(gè)進(jìn)程相同的時(shí)間片，每個(gè)運(yùn)行完時(shí)間片的進(jìn)程，當(dāng)未遇到任何阻塞時(shí)，就回到就緒隊(duì)列的尾部，并等待下次轉(zhuǎn)到它時(shí)再投入運(yùn)行。于是，只要是處于就緒隊(duì)列中的進(jìn)程，按此種算法遲早總可以分得處理機(jī)投入運(yùn)行。,下一頁,3分級(jí)輪轉(zhuǎn)法 所謂分級(jí)輪轉(zhuǎn)法就是將先前的一個(gè)就緒隊(duì)列，根據(jù)進(jìn)程的優(yōu)先數(shù)不同劃分兩個(gè)或兩個(gè)以上的就緒隊(duì)列，并賦給每個(gè)隊(duì)列不同的優(yōu)先數(shù)。以兩個(gè)就緒隊(duì)列為例，一個(gè)具有較高優(yōu)先數(shù)，另一個(gè)具有較低優(yōu)先數(shù)，前者稱為前臺(tái)隊(duì)列，后者稱為后臺(tái)隊(duì)列。,下一頁,在多道程序的環(huán)境中，系統(tǒng)中的多個(gè)進(jìn)程可以并發(fā)執(zhí)行，同時(shí)它們

18、又要共享系統(tǒng)中的資源，這些資源有些是可共享使用的，如磁盤，有些是以獨(dú)占方式使用的，如打印機(jī)。由此將會(huì)引起一系列的矛盾，產(chǎn)生錯(cuò)綜復(fù)雜的相互制約的關(guān)系。 產(chǎn)生這種錯(cuò)綜復(fù)雜的相互制約關(guān)系的原因有二： 資源共享間接制約關(guān)系 進(jìn)程合作直接制約關(guān)系,3.5 進(jìn)程間的同步和互斥,一個(gè)進(jìn)程到達(dá)了某點(diǎn)后，除非另一進(jìn)程已完成某些操作，否則就不得不停下來等待這些操作的結(jié)束。這就是進(jìn)程間的同步。,進(jìn)程間的同步,汽車司機(jī)和售票員之間的同步關(guān)系,進(jìn)程P1和P2之間的同步,在各協(xié)同工作的進(jìn)程之間存在著同步關(guān)系，但進(jìn)程之間更為一般的關(guān)系卻是互斥關(guān)系。這是由于進(jìn)程在運(yùn)行過程中因爭奪資源所引起的。 例如，有兩個(gè)進(jìn)程P1、P2，它

19、們都要使用打印機(jī)，如果讓它們隨意使用，那么就有可能出現(xiàn)P1打印幾行P2再打印幾行的結(jié)果導(dǎo)致打印出來的內(nèi)容混在一起，很難區(qū)分，即使能夠區(qū)分，也要將各自輸出的結(jié)果從打印紙上剪下來，再用漿糊粘接起來。 解決這一問題的辦法是，不允許一臺(tái)打印機(jī)讓兩個(gè)進(jìn)程同時(shí)使用，應(yīng)在一個(gè)進(jìn)程用完后再讓另一進(jìn)程使用。由此可見，系統(tǒng)中存在許多進(jìn)程，它們共享各種資源。然而有很多資源一次只能供一個(gè)進(jìn)程使用。,2. 進(jìn)程間的互斥,臨界資源：某段時(shí)間僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。 宿舍電話 打印機(jī) 電話和打印機(jī)都屬于臨界資源。除此之外，還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源。 兩個(gè)或兩個(gè)以上的進(jìn)程不能同時(shí)使用同一臨界資源

20、，只能一個(gè)進(jìn)程使用完畢后，另一進(jìn)程才能使用，這種現(xiàn)象稱為進(jìn)程互斥。,幾個(gè)進(jìn)程若共享同一臨界資源，它們必須以互斥的方式使用這個(gè)臨界資源，即當(dāng)一個(gè)進(jìn)程正在使用臨界資源且尚未使用完畢時(shí)，則其他進(jìn)程必須推遲對(duì)該資源的進(jìn)一步操作，,進(jìn)程互斥,P1：R1:=COUNT; R1:=R1+1； COUNT:=R1; 其中R1，R2屬于兩個(gè)通用寄存器。 并發(fā)執(zhí)行的兩程序可能是以下執(zhí)行順序： P1： R1:=COUNT; P2：R2:=COUNT; P1: R1:=R1+1； COUNT:=R1; P2： R2:=R2+1；COUNT:=R2;,P2：R2:=COUNT; R2:=R2+1； COUNT:=R2;

21、,臨界區(qū)(critical section) 每個(gè)進(jìn)程中訪問臨界資源的那段程序段稱為相對(duì)于臨界資源的臨界區(qū)。,因?yàn)楦鬟M(jìn)程對(duì)臨界資源的使用是采用互斥方式的，所以訪問臨界資源的進(jìn)程必須互斥的進(jìn)入各自的臨界區(qū)。,這種方法使用了一個(gè)物理實(shí)體，稱為鎖，用W來表示，鎖有兩種狀態(tài)，W=0表示鎖已打開；W=1表示鎖被關(guān)閉。 加鎖原語用LOCK(W)表示，其操作為： 測(cè)試W，若W=1，表示資源正在使用，繼續(xù)反復(fù)測(cè)試；若W=0，置W=1(加鎖)。 加鎖原語用LOCK(W)可描述為 L：if W=1 then go to L else W：=1； 開鎖原語用UNLOCK(W)表示，可描述為 W：=0；,3. 實(shí)現(xiàn)臨

22、界區(qū)互斥的鎖操作法,兩個(gè)進(jìn)程P1、P2使用如下程序?qū)嵤┻M(jìn)程的互斥： 進(jìn)程P1 進(jìn)程P2 LOCK(W) LOCK(W) S1/進(jìn)入臨界區(qū) S2 /進(jìn)入臨界區(qū) UNLOCK(W) UNLOCK(W) 其中S1和S2分別為進(jìn)程P1和P2的臨界區(qū)。,知識(shí)回顧,進(jìn)程的關(guān)系：同步和互斥 臨界資源 臨界區(qū) 因?yàn)楦鬟M(jìn)程對(duì)臨界資源的使用是采用互斥方式的，所以訪問臨界資源的進(jìn)程必須互斥的進(jìn)入各自的臨界區(qū)。,1965年，荷蘭學(xué)者Dijkstra提出的信號(hào)量機(jī)制是一種卓有成效的進(jìn)程同步工具，在長期廣泛的應(yīng)用中，信號(hào)量機(jī)制又得到了很大的發(fā)展，它從整型信號(hào)量機(jī)制發(fā)展到記錄型信號(hào)量機(jī)制，進(jìn)而發(fā)展為“信號(hào)集”機(jī)制?，F(xiàn)在信號(hào)

23、量機(jī)制已廣泛應(yīng)用于OS中。 信號(hào)燈的使用,3.5.2 信號(hào)量和P、V操作 1. 信號(hào)量及P、V操作,信號(hào)量按聯(lián)系進(jìn)程的關(guān)系分成二類： 公用信號(hào)量（互斥信號(hào)量）：它為一組需互斥共享臨界資源的并發(fā)進(jìn)程而設(shè)置，代表共享的臨界資源，每個(gè)進(jìn)程均可對(duì)它施加P、V操作，即都可申請(qǐng)和釋放該臨界資源，其初始值置為1。 信號(hào)量s取值意義如下： s 1 ；表示資源空閑，可供使用。 s 0 ；表示資源已被占用，無其它進(jìn)程等待。 s -n ；表示資源已被占用，還有n個(gè)進(jìn)程因等待資源而阻塞。 私用信號(hào)量（同步信號(hào)量）：它為一組需同步協(xié)作完成任務(wù)的并發(fā)進(jìn)程而設(shè)置，只有擁有該資源的進(jìn)程才能對(duì)它施加P操作（即可申請(qǐng)資源），而由

24、其合作進(jìn)程對(duì)它施加V操作（即釋放資源）。初值為0或?yàn)槟硞€(gè)整數(shù)n,點(diǎn)我,P、V操作（原語）是定義在信號(hào)量S上的兩個(gè)操作，其定義分別如下： P(S)： S：=S-1 若S0，則調(diào)用P(S)的進(jìn)程繼續(xù)運(yùn)行； 若S0，則調(diào)用P(S)的進(jìn)程被阻塞，并把它插入到等待信號(hào)量S的阻塞隊(duì)列中。,V(S) S：=S+1； 若S0，則調(diào)用V(S)的進(jìn)程繼續(xù)運(yùn)行； 若S0，從等待信號(hào)量S的阻塞隊(duì)列中喚醒頭一個(gè)進(jìn)程，然后調(diào)用V(S)的進(jìn)程繼續(xù)運(yùn)行。,P、V操作可表示為如下兩個(gè)過程： P(S) Procedure P(Var S:Semaphore) Begin S:=S-1; /表示申請(qǐng)一個(gè)資源; If s0 /表示沒

25、有空閑資源; then W(S) / *將該進(jìn)程置成等待S的阻塞狀態(tài); End;,V(S) Procedure V(Var s:semaphore) Begin S:=S+1; /表示釋放一個(gè)資源； If S0 /表示有進(jìn)程處于阻塞狀態(tài)； then R(S)/ *喚醒等待S阻塞隊(duì)列的第一個(gè)進(jìn)程; End; 其中W(S)表示將調(diào)用該過程的進(jìn)程置成等待信號(hào)量S的阻塞狀態(tài)，并插入相應(yīng)的阻塞隊(duì)列中。R(S)表示要喚醒等待信號(hào)S阻塞隊(duì)列中的頭一個(gè)進(jìn)程。,P、V操作可表示為如下兩個(gè)過程： Procedure P(Var S:Semaphore) Begin S:=S-1; Ifs0 thenW(S) /*

26、將該進(jìn)程置成等待S的阻塞狀態(tài) End; P Procedure V(Var s:semaphore) Begin S:=S+1; If S0 then R(S) /*喚醒等待S阻塞隊(duì)列的第一個(gè)進(jìn)程 End; V 分析如何通過對(duì)信號(hào)量的P、V操作來實(shí)現(xiàn)進(jìn)程互斥的,例如進(jìn)程P1和進(jìn)程P2按如下安排，即可實(shí)現(xiàn)互斥。 設(shè)S為兩進(jìn)程互斥的公用信號(hào)量，初值賦予1，表明該臨界資源未被占用。 進(jìn)程P1 進(jìn)程P2 P(s) P(s) S1 S2 V(S) V(S) 其中的S1，S2是兩個(gè)互斥的程序段，即P1、P2的臨界區(qū)。,小結(jié)： 信號(hào)量S0時(shí)的數(shù)值表示某類可用資源的數(shù)量。 執(zhí)行P操作意味著申請(qǐng)分配一個(gè)單位的資

27、源。因此可描述為S：=S-1。當(dāng)S0表示已無資源可用，此時(shí)S的絕對(duì)值表示信號(hào)量S的阻塞隊(duì)列中的進(jìn)程數(shù)， 執(zhí)行一次V操作意味著釋放一個(gè)單位的資源，描述為S：=S+1，若此時(shí)S0表明信號(hào)量的阻塞隊(duì)列中仍有被阻塞的進(jìn)程，因此在執(zhí)行V操作時(shí)應(yīng)喚醒該隊(duì)列的第一個(gè)進(jìn)程。,注意： 必須成對(duì)使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進(jìn)程）； P、V原語不能次序錯(cuò)誤、重復(fù)或遺漏,【例3.1】 例子中的公用變量COUNT，是一個(gè)臨界資源。兩個(gè)并發(fā)進(jìn)程對(duì)COUNT的操作必須互斥地執(zhí)行。對(duì)此，可寫出如下程序： begin COUNT:integer; S:s

28、emaphore; COUNT:=0; S:=1;,使用信號(hào)量實(shí)現(xiàn)互斥,process p1 R1:register; begin P(S); R1:=COUNT; R1:=R1+1; COUNT:=R1; V(S) end;,process p2 R2:register; begin P(S); R2:=COUNT; R2:=R2+1; COUNT:=R2; V(s) end;,所以為使多個(gè)進(jìn)程能互斥地訪問某臨界資源，只需為該資源設(shè)置一個(gè)互斥信號(hào)量mutex,并設(shè)其初值為1，然后將各進(jìn)程的臨界區(qū)CS置于P（mutex）和V(mutex)操作之間即可。,進(jìn)程間的互斥： P(s) CS V(S)

29、,內(nèi)容回顧,信號(hào)量的分類 P操作代表申請(qǐng)資源 V操作代表釋放資源 P操作中心語句： S:=S-1; If then W(S) V操作中心語句： S:=S+1; If then R(S),s0,S0,互斥信號(hào)量的值： mutex=1： mutex=0： mutex=-n:,表示資源空閑，可供使用,表示資源已被占用，無其它進(jìn)程等待。,表示資源已被占用，還有n個(gè)進(jìn)程 因等待資源而阻塞。,小結(jié)： 信號(hào)量S0時(shí)的數(shù)值表示某類可用資源的數(shù)量。 執(zhí)行P操作意味著申請(qǐng)分配一個(gè)單位的資源。因此可描述為S：=S-1。當(dāng)S0表示已無資源可用，此時(shí)S的絕對(duì)值表示信號(hào)量S的阻塞隊(duì)列中的進(jìn)程數(shù)， 執(zhí)行一次V操作意味著釋放

30、一個(gè)單位的資源，描述為S：=S+1，若此時(shí)S0表明信號(hào)量的阻塞隊(duì)列中仍有被阻塞的進(jìn)程，因此在執(zhí)行V操作時(shí)應(yīng)喚醒該隊(duì)列的第一個(gè)進(jìn)程。,3. 利用信號(hào)量實(shí)現(xiàn)進(jìn)程間的同步,一般來說，信號(hào)量初值為0，兩個(gè)進(jìn)程之間的同步模型如下： 進(jìn)程P1 進(jìn)程P2 L1：P(S) L2：V(S) 設(shè)進(jìn)程P1先到達(dá)L1點(diǎn)，當(dāng)它執(zhí)行P(S)，使S=1，于是P1進(jìn)入阻塞狀態(tài)并進(jìn)入信號(hào)量S的阻塞隊(duì)列；然后進(jìn)程P2到達(dá)L2點(diǎn)，當(dāng)它執(zhí)行V(S)時(shí)，將S值變?yōu)?，于是喚醒P1，使其轉(zhuǎn)變?yōu)榫途w狀態(tài)，當(dāng)再調(diào)度到進(jìn)程P1時(shí)，則P1可在L1點(diǎn)后繼續(xù)運(yùn)行下去。由些可見，當(dāng)進(jìn)程P1到達(dá)L1點(diǎn)必須與進(jìn)程P2同步。,【例2】 用信號(hào)量實(shí)現(xiàn)司機(jī)和售

31、票員的同步。 設(shè)S1和S2分別為司機(jī)和售票員的私用信號(hào)量，初值均為0，則司機(jī)和售票員的同步過程描述如下： 司機(jī)進(jìn)程 售票員進(jìn)程 正常行車 售票 到站停車 P(S2) V(S2) 開車門 P(S1) 關(guān)車門 離站開車 V(S1),3.6 線 程,3.6.1. 線程的引入 進(jìn)程的兩個(gè)基本屬性： 進(jìn)程是一個(gè)可擁有資源的獨(dú)立單位； 進(jìn)程是一個(gè)可以獨(dú)立調(diào)度和分派的基本單位。 （1）創(chuàng)建進(jìn)程。系統(tǒng)在創(chuàng)建進(jìn)程時(shí)，必須為之分配其所必需的、除處理機(jī)以外的所有資源。如內(nèi)存空間、I/O設(shè)備以及建立相應(yīng)的PCB結(jié)構(gòu)。 （2）撤消進(jìn)程。系統(tǒng)在撤消進(jìn)程時(shí)，又必須先對(duì)這些資源進(jìn)行回收操作，然后再撤消PCB結(jié)構(gòu)。 （3）進(jìn)程

32、切換。在對(duì)進(jìn)程進(jìn)行切換時(shí)，由于要保留當(dāng)前進(jìn)程的CPU環(huán)境和設(shè)置新選中進(jìn)程的CPU環(huán)境，為此需花費(fèi)不少處理機(jī)時(shí)間。,3.6.2. 線程的基本概念 線程可定義：進(jìn)程中的一個(gè)執(zhí)行活動(dòng)；進(jìn)程中的可調(diào)度實(shí)體；一個(gè)獨(dú)立的程序計(jì)數(shù)器。 如果把進(jìn)程理解為在邏輯上是操作系統(tǒng)的一個(gè)任務(wù)，那么線程表示完成該任務(wù)的許多可并發(fā)(并行)執(zhí)行的子任務(wù)。,3.6.3 線程與進(jìn)程的關(guān)系,1調(diào)度：在傳統(tǒng)的操作系統(tǒng)中，擁有資源的基本單位和獨(dú)立調(diào)度、分派的基本單位都是進(jìn)程。引入線程以后，把線程作為調(diào)度和分派的基本單位，而把進(jìn)程作為資源擁有的基本單位。 2并發(fā)性：在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個(gè)進(jìn)程中的多個(gè)

33、線程之間亦可并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。,3擁有資源：不論是傳統(tǒng)的操作系統(tǒng)，還是設(shè)有線程的操作系統(tǒng)，進(jìn)程都是擁有資源的一個(gè)獨(dú)立單位，它可以擁有自己的資源。一般的說，線程自己不擁有系統(tǒng)資源（也有一點(diǎn)必不可少的資源），但它可以訪問其隸屬進(jìn)程的資源。 4系統(tǒng)開銷：由于在創(chuàng)建或撤消進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O設(shè)備等。因此，操作系統(tǒng)所付出的開銷將明顯地大于在創(chuàng)建或撤消線程時(shí)的開銷。,返回本節(jié),3.7 死鎖問題,3.7.1 死鎖產(chǎn)生的原因 3.7.2死鎖舉例 3.7.3 產(chǎn)生死鎖的必要條件和預(yù)防死鎖,返回本章首頁,所謂死鎖

34、，是指多個(gè)進(jìn)程因競爭資源而造成的彼此無休止地互相等待，在無外力作用下永遠(yuǎn)不能擺脫的僵局，這種僵局使參與的進(jìn)程永遠(yuǎn)不能向前推進(jìn)。,下一頁,P1、P2是兩個(gè)并行進(jìn)程，R1、R2是系統(tǒng)中可共享的獨(dú)占資源。當(dāng)兩個(gè)進(jìn)程以如下順序推進(jìn)時(shí)： P1分配占有R1 ；P1申請(qǐng)R2； P2分配占有R2； P2申請(qǐng)R1。 申請(qǐng) 占有 申請(qǐng) 占有 圖3.16 兩個(gè)進(jìn)程的死鎖,3.7.1 死鎖產(chǎn)生的原因,所以產(chǎn)生死鎖的原因可歸納為以下兩點(diǎn)。 (1) 系統(tǒng)資源的不足。這必定會(huì)引起進(jìn)程間資源競爭，資源競爭是產(chǎn)生死鎖的原因之一。 (2) 進(jìn)程推進(jìn)順序非法。任何系統(tǒng)資源不足是一定的，但是只有當(dāng)進(jìn)程執(zhí)行過程中，請(qǐng)求和釋放資源的順序

35、不當(dāng)時(shí)，如圖3.16所示，才會(huì)導(dǎo)致死鎖，所以，進(jìn)程推進(jìn)順序不當(dāng)是產(chǎn)生死鎖的第二個(gè)原因。,下一頁,下一頁,內(nèi)容回顧,死鎖的概念 死鎖產(chǎn)生的原因,1、 產(chǎn)生死鎖有四個(gè)必要條件,互斥條件：一個(gè)資源一次只能被一個(gè)進(jìn)程所使用，即是排它性使用。 不可剝奪/搶占條件：一個(gè)資源僅能被占有它的進(jìn)程所釋放，而不能被別的進(jìn)程搶占。 請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源要求，而該資源又已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)已經(jīng)獲得的其它資源保持不放。,返回本節(jié)目錄,2、解決死鎖的方法 ： (1) 預(yù)防死鎖。通過設(shè)置某種限制條件，去破壞產(chǎn)生死鎖必要條件中的一個(gè)或幾個(gè)，來防止死鎖出現(xiàn)。這一方法較易實(shí)現(xiàn)，但往往由于所施加的限制條件太嚴(yán)格，導(dǎo)致系統(tǒng)資源利用率下降。 (2) 避免死鎖。事先不施加預(yù)防死鎖的某種強(qiáng)制條件，而在資源動(dòng)態(tài)分配過程中，采用某種方法避免系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。在這種方法中，只是事先施加一些弱的限制條件，以使資源的利用率不致降低很多。,(3) 檢測(cè)死鎖。這種方法事先不采取任何措施，系統(tǒng)發(fā)生死鎖時(shí)，只是通過系統(tǒng)設(shè)置的檢測(cè)機(jī)構(gòu)，及時(shí)