計(jì)算機(jī)操作系統(tǒng)

1、計(jì)算機(jī)操作系統(tǒng)主講教師：曹建秋 賀清碧課程主要內(nèi)容課程主要內(nèi)容操作系統(tǒng)引論（1章）進(jìn)程管理（2-3章）存儲(chǔ)管理（4章）設(shè)備管理（5章）文件管理（6章）操作系統(tǒng)接口（7章）系統(tǒng)安全性（9章）*分布式操作系統(tǒng)從進(jìn)程的觀點(diǎn)研究操作系統(tǒng)n把OS看作是由若干個(gè)可獨(dú)立運(yùn)行的程序和一個(gè)可對(duì)這些程序進(jìn)行協(xié)調(diào)控制的核心（內(nèi)核）組成。這些運(yùn)行的程序稱為進(jìn)程，它是資源分配和獨(dú)立運(yùn)行的基本單位，每一進(jìn)程都完成某一特定任務(wù)，而OS的內(nèi)核則必須要控制和協(xié)調(diào)這些進(jìn)程的運(yùn)行，解決進(jìn)程之間的通信，并從系統(tǒng)可并發(fā)工作為出發(fā)點(diǎn)，實(shí)現(xiàn)并發(fā)進(jìn)程間通信，并解決由此帶來(lái)的共享資源的競(jìng)爭(zhēng)問(wèn)題。Process Management Proce

2、ss Management 進(jìn)程管理進(jìn)程管理-第第2 2章章n進(jìn)程的基本概念與控制n進(jìn)程的基本概念n進(jìn)程控制n線程的基本概念nUNIX中進(jìn)程的描述與控制n進(jìn)程同步與通信n進(jìn)程同步n經(jīng)典進(jìn)程的同步問(wèn)題n管程機(jī)制n進(jìn)程通信nUNIX中進(jìn)程的同步與通信n調(diào)度與死鎖（第3章）本章作業(yè)本章作業(yè)2.1 進(jìn)程的基本概念n前趨圖n程序順序執(zhí)行n程序并發(fā)執(zhí)行n進(jìn)程的描述進(jìn)程的定義、特征進(jìn)程的狀態(tài)（狀態(tài)、狀態(tài)轉(zhuǎn)換 及掛起狀態(tài)）進(jìn)程控制塊PCBProcess Management進(jìn)程管理-processes 進(jìn)程 返回目錄一、前趨圖的定義3有向無(wú)循環(huán)圖,記DAG124567結(jié)點(diǎn)，可表一語(yǔ)句、程序段或進(jìn)程前趨關(guān)系初始

3、結(jié)點(diǎn)終止結(jié)點(diǎn)前趨關(guān)系： P1 P2 ， P2 P5 ， P5 P7 P1 P3 ， P3 P5 P1 P4 ， P6 P7直接前趨直接后繼Eg1： 以下三條語(yǔ)句的前趨圖為： s1: a:=x+y s2: b:=a-5 s3: c:=b+1 Eg2: S1： a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6 s1s2s3s1s2s3s4返回二、程序順序執(zhí)行二、程序順序執(zhí)行n程序執(zhí)行時(shí)，必須按照某種先后次序逐個(gè)執(zhí)行程序執(zhí)行時(shí)，必須按照某種先后次序逐個(gè)執(zhí)行nEg s1: a:=x+y s2: b:=a-5 s3: c:=b+1n程序順序執(zhí)行時(shí)有如下特征：n順序性n封閉性

4、n可再現(xiàn)性s1s2s3返回三、程序并發(fā)執(zhí)行在處理一批作業(yè)時(shí)，有的程序可實(shí)現(xiàn)并發(fā)執(zhí)行在處理一批作業(yè)時(shí)，有的程序可實(shí)現(xiàn)并發(fā)執(zhí)行n n S1： a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6I1I2I3I4C1C2C3C4P1P2P3P4s1s2s3s4三、程序并發(fā)執(zhí)行三、程序并發(fā)執(zhí)行n程序并發(fā)執(zhí)行時(shí)的特征n間斷性n失去封閉性n不可再現(xiàn)性n（補(bǔ)充）（補(bǔ)充）程序并發(fā)執(zhí)行的條件（Bernstein)()()()()()(211221 pWpWpWpRpWpR程序并發(fā)執(zhí)行條件例題程序并發(fā)執(zhí)行條件例題nEg S1： a:=x+2 S3: c:=a-b S2: b:=z+4 S

5、4: w:=c+1試?yán)肂ernstein條件證明： （1）s1與s2并發(fā)執(zhí)行；（2） s1與s3,s2與s3,s3與s4不能。解：各語(yǔ)句的讀、寫(xiě)集分別為： R(S1)=x, W(S1)=a, R(S2)=z, W(S2)=b, R(S3)=a,b, W(S3)=c, R(S4)=c, W(S4)=w, 因?yàn)?R(S1) W(S2)=,R(S2) W(S1) = 且W(S1) W(S2) =所以由Bernstein條件，s1與s2并發(fā)執(zhí)行。 同理可證s1與s3,s2與s3,s3與s4不能（略）。 返回一、進(jìn)程的定義、特征一、進(jìn)程的定義、特征1、進(jìn)程進(jìn)程process的定義的定義 1）進(jìn)程是程序

6、的一次執(zhí)行。 2）進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。 3）進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。注：進(jìn)程與程序的主要區(qū)別注：進(jìn)程與程序的主要區(qū)別Process Management進(jìn)程管理-processes 進(jìn)程 進(jìn)程與程序的主要區(qū)別進(jìn)程與程序的主要區(qū)別1）程序是指令的有序集合，其本身沒(méi)有任何運(yùn)行的含義，它是一個(gè)靜態(tài)靜態(tài)的概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過(guò)程，它是一個(gè)動(dòng)態(tài)動(dòng)態(tài)概念。2）程序的存在是永久存在是永久的。而進(jìn)程則是有生命期進(jìn)程則是有生命期的，它因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因得不到資源而暫停，因撤消而消亡。3）程序

7、僅是指令的有序集合指令的有序集合。而進(jìn)程則由程序段、相關(guān)數(shù)據(jù)段程序段、相關(guān)數(shù)據(jù)段進(jìn)程控制塊（進(jìn)程控制塊（PCB）組成。4）進(jìn)程與程序之間不是一一對(duì)應(yīng)進(jìn)程與程序之間不是一一對(duì)應(yīng)。進(jìn)程與程序的主要區(qū)別進(jìn)程與程序的主要區(qū)別2、進(jìn)程、進(jìn)程process的基本特征的基本特征 （1）結(jié)構(gòu)特征結(jié)構(gòu)特征 為了描述和記錄進(jìn)程的運(yùn)動(dòng)變化過(guò)程，并使之能正確運(yùn)行，每個(gè)進(jìn)程都應(yīng)配置了一個(gè)進(jìn)程PCB。所以，從結(jié)構(gòu)上看，每個(gè)進(jìn)程（進(jìn)程實(shí)體）都是由程序段、相關(guān)數(shù)據(jù)段及進(jìn)程控制塊（程序段、相關(guān)數(shù)據(jù)段及進(jìn)程控制塊（PCB）組成。注：1.在早期UNIX版本中稱進(jìn)程的三個(gè)組成部分為“進(jìn)程映像” 2.區(qū)別進(jìn)程實(shí)體和進(jìn)程 （2）動(dòng)態(tài)性動(dòng)

8、態(tài)性 進(jìn)程的實(shí)質(zhì)是程序在處理機(jī)上的一次執(zhí)行過(guò)程程序在處理機(jī)上的一次執(zhí)行過(guò)程，因此是動(dòng)態(tài)性的。所以動(dòng)態(tài)性是進(jìn)程的最基本的特征。同時(shí)動(dòng)態(tài)性還表現(xiàn)在 進(jìn)程則是有生命期進(jìn)程則是有生命期的，它因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因得不到資源而暫停，因撤消而消亡。Process Management進(jìn)程管理-processes 進(jìn)程 一、進(jìn)程的定義、特征一、進(jìn)程的定義、特征（3）并發(fā)性并發(fā)性 指多個(gè)進(jìn)程實(shí)體同時(shí)存在于內(nèi)存中，能在一段時(shí)間內(nèi)同時(shí)運(yùn)行。 引入進(jìn)程的目的就是為了使進(jìn)程能并發(fā)執(zhí)行，以提高資源利用率，所以并發(fā)性是進(jìn)程的重要特征，也是OS的重要特征。（4）獨(dú)立性獨(dú)立性 指進(jìn)程是一個(gè)能獨(dú)立運(yùn)行的基本單位，也是系

9、統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位。（5）異步性異步性 指進(jìn)程以各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。返回二、二、 進(jìn)程狀態(tài)進(jìn)程狀態(tài) 為了刻畫(huà)了整個(gè)進(jìn)程，可以將一個(gè)進(jìn)程的生命周期劃分為一組狀態(tài)：1、進(jìn)程的5種狀態(tài)（三種基本狀態(tài)三種基本狀態(tài)）nnew新建/創(chuàng)建:進(jìn)程正在創(chuàng)建中的狀態(tài)nready就緒就緒: 進(jìn)程已獲得了除處理機(jī)以外的所有資源，等待分配處理機(jī)執(zhí)行的等待狀態(tài)。nrunning運(yùn)行/執(zhí)行執(zhí)行: 當(dāng)一個(gè)進(jìn)程獲得必要的資源并正在處理機(jī)上執(zhí)行的狀態(tài)。nwaiting等待/阻塞阻塞: 正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時(shí)無(wú)法執(zhí)行下去，此時(shí)進(jìn)程所處的狀態(tài)。nterminated終止/撤消/退出：進(jìn)程執(zhí)行完

10、畢，釋放所占資源的狀態(tài)。Process Management進(jìn)程管理-processes 進(jìn)程 進(jìn)程在運(yùn)行期間并非固定處于某個(gè)狀態(tài)，而是不斷從一個(gè)狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)。n2 2、進(jìn)程狀態(tài)轉(zhuǎn)換、進(jìn)程狀態(tài)轉(zhuǎn)換3 3、進(jìn)程的掛起狀態(tài)、進(jìn)程的掛起狀態(tài) 在某些系統(tǒng)中，為了更好地管理和調(diào)度進(jìn)程，引入了掛起狀態(tài)：n掛起狀態(tài)掛起狀態(tài)/靜止?fàn)顟B(tài)：靜止?fàn)顟B(tài)： 程序在運(yùn)行期間，由于某種需要，往往要將進(jìn)程程序在運(yùn)行期間，由于某種需要，往往要將進(jìn)程暫停執(zhí)行，使其靜止下來(lái)，以滿足其需要。這種靜止?fàn)顣和?zhí)行，使其靜止下來(lái)，以滿足其需要。這種靜止?fàn)顟B(tài)就稱為進(jìn)程的掛起狀態(tài)。態(tài)就稱為進(jìn)程的掛起狀態(tài)。引起掛起狀態(tài)的原因引起掛起狀態(tài)

11、的原因 終端用戶的需要終端用戶的需要：終端用戶在自己程序運(yùn)行中發(fā)現(xiàn)問(wèn)題要求使正在 執(zhí)行的進(jìn)程暫停執(zhí)行而使進(jìn)程處于掛起狀態(tài)。父進(jìn)程的需要：父進(jìn)程的需要：父進(jìn)程為了考查和修改某個(gè)子進(jìn)程，或者協(xié)調(diào)各子進(jìn) 程間的活動(dòng)，需要將該子進(jìn)程掛起。操作系統(tǒng)的需要：操作系統(tǒng)的需要：操作系統(tǒng)為了檢查運(yùn)行中的資源使用情況或進(jìn)行記 帳，而將某些進(jìn)程掛起。對(duì)換的需要：對(duì)換的需要：為了提高內(nèi)存的利用率，而將內(nèi)存中某些進(jìn)程掛起，以 調(diào)進(jìn)其它程序運(yùn)行。負(fù)荷調(diào)節(jié)的需要：負(fù)荷調(diào)節(jié)的需要：由于工作負(fù)荷較重，而將一些不重要的進(jìn)程掛起， 以保證系統(tǒng)能正常運(yùn)行（實(shí)時(shí)操作系統(tǒng)） 返回控制進(jìn)程的掛起與激活具有掛起狀態(tài)的進(jìn)程狀態(tài)具有掛起狀態(tài)的進(jìn)

12、程狀態(tài) 在引入掛起狀態(tài)后，就增加了掛起狀態(tài)（靜止?fàn)顟B(tài)）與非掛起狀態(tài)（活動(dòng)狀態(tài)）間的轉(zhuǎn)換，如圖所示：活動(dòng)就緒掛起就緒活動(dòng)阻塞掛起阻塞執(zhí)行進(jìn)程調(diào)度時(shí)間片用完掛起激活掛起掛起事件發(fā)生事件發(fā)生等待事件激活返回三、進(jìn)程控制塊三、進(jìn)程控制塊Process Control Block (PCB)Process Control Block (PCB)進(jìn)程控制塊進(jìn)程控制塊PCBPCB 是操作系統(tǒng)為了管理和控制進(jìn)程的運(yùn)行而為每一個(gè)進(jìn)程定義的一個(gè)數(shù)據(jù)結(jié)構(gòu)，它記錄了系統(tǒng)管理進(jìn)程所需的全部信息。系統(tǒng)根據(jù)PCB而感知進(jìn)程的存在，PCB是進(jìn)程存在的唯一標(biāo)志。1 1、進(jìn)程控制塊、進(jìn)程控制塊PCBPCB的作用的作用是OS對(duì)并發(fā)

13、執(zhí)行的進(jìn)程進(jìn)行控制和管理的根據(jù)。也是系統(tǒng)用來(lái)感知進(jìn)程存在的根據(jù)，即PCB是進(jìn)程存在的唯一標(biāo)志。Process Management進(jìn)程管理-processes 進(jìn)程 1、進(jìn)程控制塊PCB的作用2、進(jìn)程控制塊PCB中的信息3、進(jìn)程控制塊PCB的組織方式2 2、進(jìn)程控制塊、進(jìn)程控制塊PCBPCB中的信息中的信息 根據(jù)操作系統(tǒng)的要求不同，PCB所包含信息有些不同，但通常包含以下信息：進(jìn)程標(biāo)志符進(jìn)程標(biāo)志符：由系統(tǒng)創(chuàng)建進(jìn)程時(shí)分配給進(jìn)程的唯一標(biāo)識(shí)號(hào)，通常為一整數(shù)，稱為進(jìn)程號(hào)，用于區(qū)分不同的進(jìn)程。其所屬用戶通常也為一整數(shù)，稱為用戶號(hào)。處理機(jī)狀態(tài)（斷點(diǎn)信息）處理機(jī)狀態(tài)（斷點(diǎn)信息）：即處理機(jī)中各種寄存器（通用寄

14、存器、PC、PSW等）的內(nèi)容進(jìn)程調(diào)度進(jìn)程調(diào)度：記錄了進(jìn)程調(diào)度的相關(guān)信息（狀態(tài)、優(yōu)先級(jí)、事件等）。進(jìn)程控制進(jìn)程控制：記錄了系統(tǒng)對(duì)進(jìn)程控制的信息（程序和數(shù)據(jù)的地址、同步機(jī)制、資源清單、鏈接指針）Process Management進(jìn)程管理-processes 進(jìn)程 3 3、進(jìn)程控制塊、進(jìn)程控制塊PCBPCB的組織方式的組織方式 在一個(gè)系統(tǒng)中，通常存在著許多進(jìn)程，它們所處的狀態(tài)不同，為了方便進(jìn)程的調(diào)度和管理，需要將各進(jìn)程的PCB用適當(dāng)方法組織起來(lái)。目前常用的組織方式有：鏈接方式鏈接方式 圖示 把同一狀態(tài)的PCB鏈接成一個(gè)隊(duì)列，這樣就形成了就緒隊(duì)列、阻塞隊(duì)列等。索引方式索引方式 圖示 將同一狀態(tài)的進(jìn)程

15、組織在一個(gè)索引表中，索引表的表項(xiàng)指向相應(yīng)的PCB ，不同狀態(tài)對(duì)應(yīng)不同的索引表。 Process Management進(jìn)程管理-processes 進(jìn)程 返回1PCB90PCB89PCB77PCB6 PCB58PCB40PCB33PCB24PCB1執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針按鏈接方式組織PCB按索引方式組織PCB1PCB90PCB89PCB77PCB6 PCB58PCB40PCB33PCB24PCB1執(zhí)行指針就緒表指針阻塞表指針就緒索引表阻塞索引表2.3 2.3 進(jìn)程的控制進(jìn)程的控制 進(jìn)程控制是進(jìn)程管理中最基本的功能，即對(duì)系統(tǒng)中所有的進(jìn)程實(shí)施有效的管理，其功能包括進(jìn)程的創(chuàng)建、撤

16、消、阻塞與喚醒等，這些功能一般是由操作系統(tǒng)的內(nèi)核來(lái)完成。補(bǔ)充：補(bǔ)充：OS OS 內(nèi)核：內(nèi)核：在現(xiàn)代OS中，常把一些功能模塊（與硬件緊密相關(guān)的、常用設(shè)備的驅(qū)動(dòng)程序及運(yùn)行頻率較高的）放在緊靠硬件的軟件層次中，加以特殊保護(hù)，同時(shí)把它們常駐內(nèi)存，以提高OS的運(yùn)行效率，這部分功能模塊就稱OS的內(nèi)核。內(nèi)核是基于硬件的第一層軟件擴(kuò)充，它為系統(tǒng)控制和管理進(jìn)程提供了良好的環(huán)境。Process Management進(jìn)程管理-processes 進(jìn)程 補(bǔ)充：處理機(jī)的執(zhí)行狀態(tài)處理機(jī)的執(zhí)行狀態(tài) 為防止OS及其關(guān)鍵數(shù)據(jù)（如PCB等)不被用戶有意或無(wú)意破壞,通常將處理機(jī)的執(zhí)行狀態(tài)分為兩種Process Management

17、進(jìn)程管理-processes 進(jìn)程 一、進(jìn)程創(chuàng)建一、進(jìn)程創(chuàng)建 一個(gè)進(jìn)程可以創(chuàng)建若干個(gè)新進(jìn)程，新創(chuàng)建的進(jìn)程又可以創(chuàng)建子進(jìn)程，為了描述進(jìn)程之間的創(chuàng)建關(guān)系，引入了進(jìn)程圖（如下圖所示：） 1 1、進(jìn)程圖、進(jìn)程圖：又稱為進(jìn)程樹(shù)或進(jìn)程家族樹(shù)，是描述進(jìn)程家族關(guān)系的一棵有向樹(shù)。Process Management進(jìn)程管理-processes 進(jìn)程 ABDECF父進(jìn)程祖先進(jìn)程子進(jìn)程2 2、引起進(jìn)程創(chuàng)建的事件、引起進(jìn)程創(chuàng)建的事件 在多道程序環(huán)境中，只有進(jìn)程才可以在系統(tǒng)中運(yùn)行。為了使一個(gè)程序能運(yùn)行，必須為它創(chuàng)建進(jìn)程。導(dǎo)致進(jìn)程創(chuàng)建的事件有： 用戶登錄：用戶登錄：在分時(shí)OS中，用戶在終端鍵入登錄命令后，如是合法用戶，則

18、系統(tǒng)為該終端創(chuàng)建一進(jìn)程，并插入就緒隊(duì)列。 作業(yè)調(diào)度作業(yè)調(diào)度：在批處理OS中，當(dāng)按某算法調(diào)度一作業(yè)進(jìn)內(nèi)存，系統(tǒng)為之分配必要資源，同時(shí)為該作業(yè)創(chuàng)建一進(jìn)程，并插入就緒隊(duì)列。 提供服務(wù)：提供服務(wù)：在程序運(yùn)行中，若用戶需某種服務(wù)，則系統(tǒng)創(chuàng)建一進(jìn)程為用戶提供服務(wù)，并插入就緒隊(duì)列。 應(yīng)用請(qǐng)求應(yīng)用請(qǐng)求：在運(yùn)行中，由于應(yīng)用進(jìn)程本身的需求，自己創(chuàng)建一進(jìn)程，并插入就緒隊(duì)列。3 3、進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建 操作系統(tǒng)一旦發(fā)現(xiàn)了要求創(chuàng)建進(jìn)程的事件后，便調(diào)用進(jìn)程創(chuàng)建原語(yǔ)create()按以下過(guò)程創(chuàng)建一新進(jìn)程：申請(qǐng)一個(gè)空閑的申請(qǐng)一個(gè)空閑的PCBPCB為新進(jìn)程分配資源為新進(jìn)程分配資源對(duì)對(duì)PCBPCB初始化初始化將將PCBPCB插

19、入就緒隊(duì)列插入就緒隊(duì)列返回一個(gè)進(jìn)程標(biāo)識(shí)號(hào)返回一個(gè)進(jìn)程標(biāo)識(shí)號(hào) 一個(gè)進(jìn)程在完成其任務(wù)后，應(yīng)加以撤消，以便及時(shí)釋放其占有的各類資源。1 1、導(dǎo)致進(jìn)程撤消的事件、導(dǎo)致進(jìn)程撤消的事件u進(jìn)程正常結(jié)束進(jìn)程正常結(jié)束u進(jìn)程異常結(jié)束進(jìn)程異常結(jié)束u外界干預(yù)外界干預(yù) 如果系統(tǒng)中發(fā)生了要求撤消進(jìn)程的事件，OS便調(diào)用撤消原語(yǔ)去撤消進(jìn)程。2 2、撤消原語(yǔ)可采用、撤消原語(yǔ)可采用2 2種撤消策略：種撤消策略：u只撤消指定的進(jìn)程只撤消指定的進(jìn)程u撤消指定進(jìn)程及其所有的子孫進(jìn)程撤消指定進(jìn)程及其所有的子孫進(jìn)程 二、二、進(jìn)程的撤消進(jìn)程的撤消Process Management進(jìn)程管理-processes 進(jìn)程 3 3、進(jìn)程撤消的過(guò)程、

20、進(jìn)程撤消的過(guò)程Process Management進(jìn)程管理-processes 進(jìn)程 在運(yùn)行？在運(yùn)行？NYNY由標(biāo)識(shí)符在由標(biāo)識(shí)符在PCBPCB集中找集中找PCBPCB并讀狀態(tài)并讀狀態(tài)歸還占有資源歸還占有資源從所在隊(duì)列從所在隊(duì)列( (索引表索引表) )撤消撤消PCBPCB中止運(yùn)行重置調(diào)度標(biāo)志中止運(yùn)行重置調(diào)度標(biāo)志終止所有子孫進(jìn)程終止所有子孫進(jìn)程有子孫進(jìn)程？有子孫進(jìn)程？ 當(dāng)一個(gè)進(jìn)程期待的事件尙未出現(xiàn)時(shí)，該進(jìn)程調(diào)用阻塞原語(yǔ)block()（功能：將進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)為阻塞狀態(tài)）將自己阻塞起來(lái)。對(duì)于處于阻塞狀態(tài)的進(jìn)程，當(dāng)該進(jìn)程期待的事件出現(xiàn)時(shí)，由其它相關(guān)進(jìn)程調(diào)用喚醒原語(yǔ)wakeup()（功能：將進(jìn)程由阻塞狀

21、態(tài)變?yōu)榫途w狀態(tài)）將阻塞的進(jìn)程喚醒，使其進(jìn)入就緒狀態(tài)。1、引起進(jìn)程阻塞和喚醒的事件、引起進(jìn)程阻塞和喚醒的事件請(qǐng)求系統(tǒng)服務(wù)請(qǐng)求系統(tǒng)服務(wù)啟動(dòng)某種操作啟動(dòng)某種操作新數(shù)據(jù)尚未到達(dá)新數(shù)據(jù)尚未到達(dá)無(wú)新工作可做無(wú)新工作可做三、進(jìn)程的阻塞與喚醒三、進(jìn)程的阻塞與喚醒Process Management進(jìn)程管理-processes 進(jìn)程 停止執(zhí)行停止執(zhí)行修改修改PCBPCB中的狀態(tài)中的狀態(tài)（執(zhí)行（執(zhí)行- -阻塞）阻塞）插入到相應(yīng)的阻塞隊(duì)列插入到相應(yīng)的阻塞隊(duì)列另調(diào)度一就緒進(jìn)程，切換另調(diào)度一就緒進(jìn)程，切換CPUCPU（保留阻塞進(jìn)程的（保留阻塞進(jìn)程的CPUCPU狀態(tài)）狀態(tài)）將阻塞進(jìn)程移出阻塞隊(duì)列將阻塞進(jìn)程移出阻塞隊(duì)列插入

22、到就緒隊(duì)列插入到就緒隊(duì)列另調(diào)度一就緒進(jìn)程，切換另調(diào)度一就緒進(jìn)程，切換CPUCPU（保留阻塞進(jìn)程的（保留阻塞進(jìn)程的CPUCPU狀態(tài)）狀態(tài)）修改修改PCBPCB中的狀態(tài)中的狀態(tài)（阻塞（阻塞- -就緒）就緒）2、進(jìn)程的阻塞過(guò)程、進(jìn)程的阻塞過(guò)程3、進(jìn)程的喚醒過(guò)程、進(jìn)程的喚醒過(guò)程 當(dāng)引起進(jìn)程掛起的事件發(fā)生時(shí)，系統(tǒng)就將利用掛起原語(yǔ)suspend()將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。當(dāng)發(fā)生激活進(jìn)程的事件時(shí)，系統(tǒng)就將利用激活原語(yǔ)active()將指定進(jìn)程激活。1、引起進(jìn)程的掛起與激活的事件引起進(jìn)程的掛起與激活的事件四、進(jìn)程的掛起與激活四、進(jìn)程的掛起與激活Process Management進(jìn)程管理-proc

23、esses 進(jìn)程 2、進(jìn)程的掛起過(guò)程、進(jìn)程的掛起過(guò)程檢查該進(jìn)程狀態(tài)檢查該進(jìn)程狀態(tài)修改修改PCBPCB中的狀態(tài)中的狀態(tài)* *（活動(dòng)（活動(dòng)- -靜止）靜止）復(fù)制復(fù)制PCBPCB至指定內(nèi)存區(qū)域至指定內(nèi)存區(qū)域運(yùn)行？運(yùn)行？另調(diào)度另調(diào)度一就緒進(jìn)程一就緒進(jìn)程3、進(jìn)程的激活過(guò)程、進(jìn)程的激活過(guò)程N(yùn)Y將掛起進(jìn)程從外存調(diào)入內(nèi)存將掛起進(jìn)程從外存調(diào)入內(nèi)存決定是否需重新調(diào)度決定是否需重新調(diào)度修改修改PCBPCB中的狀態(tài)中的狀態(tài)* *（靜止（靜止- -活動(dòng)）活動(dòng)）活動(dòng)就緒？活動(dòng)就緒？返回目錄* *2.7 2.7 線程線程 線程是近年來(lái)操作系統(tǒng)領(lǐng)域出現(xiàn)的一個(gè)非常重要的技術(shù)，其引入進(jìn)一步提高了程序并發(fā)執(zhí)行的程度，從而進(jìn)一步提高

24、了資源的利用率和系統(tǒng)的吞吐量。 線程的基本概念 線程間的同步和通信 內(nèi)核支持線程和用戶級(jí)線程 線程控制Process Management進(jìn)程管理-processes 進(jìn)程 一、線程的基本概念一、線程的基本概念進(jìn)程間CPU的切換/上下文切換Process Management進(jìn)程管理-processes 進(jìn)程 Process Management進(jìn)程管理-threads 線程 二、線程的分類二、線程的分類三、三、Solaris OS 中的線程中的線程qSolaris 2：是UNIX的一種版本,92年以前僅支持傳統(tǒng)的單線程的重型進(jìn)程,現(xiàn)在已發(fā)展為可支持用戶級(jí)、內(nèi)核/核心級(jí)線程,對(duì)稱多處理器和實(shí)時(shí)

25、調(diào)度的OS。用戶級(jí)線程用戶級(jí)線程輕型進(jìn)程輕型進(jìn)程內(nèi)核級(jí)線程內(nèi)核級(jí)線程進(jìn)程進(jìn)程內(nèi)核內(nèi)核返回目錄* *2.8 UNIX2.8 UNIX中進(jìn)程的描述與控制中進(jìn)程的描述與控制P323P323n進(jìn)程的描述進(jìn)程的描述n進(jìn)程的數(shù)據(jù)結(jié)構(gòu)進(jìn)程的數(shù)據(jù)結(jié)構(gòu)n進(jìn)程的狀態(tài)及其轉(zhuǎn)換進(jìn)程的狀態(tài)及其轉(zhuǎn)換n進(jìn)程映像進(jìn)程映像進(jìn)程的數(shù)據(jù)結(jié)構(gòu)進(jìn)程的數(shù)據(jù)結(jié)構(gòu) UNIX系統(tǒng)V中，一個(gè)進(jìn)程由程序區(qū)、數(shù)據(jù)區(qū)、棧區(qū)、共享存儲(chǔ)區(qū)等若干區(qū)組成，同時(shí)設(shè)置PCB，PCB分為以下四部分：n進(jìn)程表進(jìn)程表：記錄了進(jìn)程的狀態(tài)及有關(guān)控制信息等。nU U區(qū)：區(qū)：存放進(jìn)程表項(xiàng)的一些擴(kuò)充信息n進(jìn)程區(qū)表進(jìn)程區(qū)表：記錄了進(jìn)程每個(gè)區(qū)的起始虛地址及指向系統(tǒng)區(qū)表中對(duì)應(yīng)區(qū)表項(xiàng)的

26、指針。n系統(tǒng)區(qū)表：系統(tǒng)區(qū)表：記錄了各區(qū)的類型、狀態(tài)及在物理存儲(chǔ)器中的地址信息等，以實(shí)現(xiàn)對(duì)區(qū)的管理。U區(qū)進(jìn)程表a b c本進(jìn)程區(qū)表系統(tǒng)區(qū)表abc進(jìn)程的數(shù)據(jù)結(jié)構(gòu)進(jìn)程的狀態(tài)及轉(zhuǎn)換進(jìn)程的狀態(tài)及轉(zhuǎn)換 UNIX系統(tǒng)中，進(jìn)程的狀態(tài)(9種)及轉(zhuǎn)換如圖圖10-410-4所示所示。n進(jìn)程的九種狀態(tài)進(jìn)程的九種狀態(tài)n核心態(tài)執(zhí)行核心態(tài)執(zhí)行n用戶態(tài)執(zhí)行用戶態(tài)執(zhí)行n內(nèi)存中就緒內(nèi)存中就緒n被剝奪狀態(tài)被剝奪狀態(tài)n就緒且換出就緒且換出n內(nèi)存中睡眠內(nèi)存中睡眠n睡眠且換出睡眠且換出n創(chuàng)建狀態(tài)創(chuàng)建狀態(tài)n僵死狀態(tài)僵死狀態(tài)85系統(tǒng)調(diào)用中斷返回用戶態(tài)執(zhí)行返回用戶態(tài)4962137搶占核心態(tài)執(zhí)行僵死睡眠內(nèi)存中睡眠睡眠且換出換出喚醒內(nèi)存中就緒調(diào)度

27、換出 換入喚醒就緒且換出內(nèi)存不足內(nèi)存足創(chuàng)建fork被搶占進(jìn)程的映像進(jìn)程的映像 UNIX系統(tǒng)中，進(jìn)程是進(jìn)程映像的執(zhí)行過(guò)程，進(jìn)程映像由三部分組成:n用戶級(jí)上、下文用戶級(jí)上、下文 主要是用戶程序，在系統(tǒng)中分為正文區(qū)、數(shù)據(jù)區(qū)、棧區(qū)和主要是用戶程序，在系統(tǒng)中分為正文區(qū)、數(shù)據(jù)區(qū)、棧區(qū)和共享數(shù)據(jù)區(qū)。共享數(shù)據(jù)區(qū)。n寄存器上、下文寄存器上、下文 由由CPUCPU中一些寄存器的內(nèi)容所構(gòu)成。中一些寄存器的內(nèi)容所構(gòu)成。n系統(tǒng)級(jí)上、下文系統(tǒng)級(jí)上、下文 分靜態(tài)（只有一個(gè)，大小不變）和動(dòng)態(tài)兩部分（大小可分靜態(tài)（只有一個(gè)，大小不變）和動(dòng)態(tài)兩部分（大小可變）。變）。進(jìn)程的控制進(jìn)程的控制系統(tǒng)調(diào)用系統(tǒng)調(diào)用 unix系統(tǒng)向用戶提供了

28、一組系統(tǒng)調(diào)用，用戶可利用這些系統(tǒng)調(diào)用來(lái)實(shí)現(xiàn)對(duì)進(jìn)程的控制。nfork()fork()創(chuàng)建一新進(jìn)程（創(chuàng)建一新進(jìn)程（0 0進(jìn)程由系統(tǒng)引導(dǎo)時(shí)建）進(jìn)程由系統(tǒng)引導(dǎo)時(shí)建）nExec()Exec()改變進(jìn)程的原有代碼改變進(jìn)程的原有代碼nExit()Exit()實(shí)現(xiàn)進(jìn)程的自我終止實(shí)現(xiàn)進(jìn)程的自我終止nWait()Wait()掛起進(jìn)程，等待子進(jìn)程終止掛起進(jìn)程，等待子進(jìn)程終止nGetpid()Getpid()獲取進(jìn)程標(biāo)識(shí)符獲取進(jìn)程標(biāo)識(shí)符nNice()Nice()改變進(jìn)程的優(yōu)先級(jí)改變進(jìn)程的優(yōu)先級(jí)返回目錄 2.3 2.3 進(jìn)程同步進(jìn)程同步n進(jìn)程同步進(jìn)程同步是指對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，它的目的是使系統(tǒng)中諸進(jìn)程之

29、間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性；或系統(tǒng)中諸進(jìn)程之間在邏輯上的相互制約的關(guān)系（直接的-同步；間接的互斥）。n用來(lái)實(shí)現(xiàn)同步的機(jī)制稱為同步機(jī)制。如：信號(hào)量機(jī)制；管程機(jī)制。 2.3 2.3 進(jìn)程同步進(jìn)程同步進(jìn)程同步的基本概念進(jìn)程同步的基本概念 兩種形式的制約關(guān)系兩種形式的制約關(guān)系 臨界資源、臨界區(qū)臨界資源、臨界區(qū) 同步機(jī)制應(yīng)遵循的規(guī)則同步機(jī)制應(yīng)遵循的規(guī)則信號(hào)量機(jī)制信號(hào)量機(jī)制 整型信號(hào)量整型信號(hào)量 記錄型信號(hào)量記錄型信號(hào)量 ANDAND型信號(hào)量集、一般信號(hào)量集型信號(hào)量集、一般信號(hào)量集信號(hào)量的應(yīng)用信號(hào)量的應(yīng)用 信號(hào)量實(shí)現(xiàn)進(jìn)程互斥信號(hào)量實(shí)現(xiàn)進(jìn)程互斥 信號(hào)量描述進(jìn)程間的前趨關(guān)系信號(hào)

30、量描述進(jìn)程間的前趨關(guān)系返回目錄一、進(jìn)程同步的基本概念一、進(jìn)程同步的基本概念1 1、兩種形式的制約關(guān)系、兩種形式的制約關(guān)系系統(tǒng)中諸進(jìn)程之間在邏輯上存在著兩種制約關(guān)系：n直接制約關(guān)系（進(jìn)程同步）直接制約關(guān)系（進(jìn)程同步）：即為完成同一個(gè)任務(wù)的諸進(jìn)程間，因需要協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的直接制約關(guān)系。 n間接制約關(guān)系（進(jìn)程互斥）間接制約關(guān)系（進(jìn)程互斥） ：是進(jìn)程共享獨(dú)占型資源而必須互斥執(zhí)行的間接制約關(guān)系。n同步與互斥比較同步與互斥比較2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū)n一次只允許一個(gè)進(jìn)程使用的資源稱為臨界資源一次只允許一個(gè)進(jìn)程使用的資源稱為臨界資源，如打印機(jī)，繪圖機(jī)；變量，數(shù)

31、據(jù)等，諸進(jìn)程間采取互斥方式式實(shí)現(xiàn)對(duì)這種臨界資源的共享，從而實(shí)現(xiàn)并行程序的封閉性。例例：有兩個(gè)進(jìn)程A和B，它們共享一個(gè)變量x，且兩個(gè)進(jìn)程按以下方式對(duì)變量X進(jìn)行訪問(wèn)和修改: 其中R1和R2為處理機(jī)中的兩個(gè)寄存器。A與B均對(duì)X+1，即X+2。若按另一順序?qū)ψ兞窟M(jìn)行修改：結(jié)果x只加了1.A: R1=X;B: R2=X;A: R1=R1+1; X=R1;B: R2=R2+1; X=R2;A: R1=X; R1=R1+1; X=R1;B: R2=X; R2=R2+1; X=R2;（1 1）變量）變量X X必必需按臨界資源需按臨界資源處理。處理。（2 2）每個(gè)進(jìn)程）每個(gè)進(jìn)程中訪問(wèn)臨界資中訪問(wèn)臨界資源的那段代

32、碼源的那段代碼稱為臨界區(qū)稱為臨界區(qū)2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū) 為了保證臨界資源的正確使用，可以把臨界資源的訪問(wèn)過(guò)程臨界資源的訪問(wèn)過(guò)程分成以下幾部分： 進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)v進(jìn)入?yún)^(qū)增加在臨界區(qū)前面的一段代碼，用于檢查欲訪問(wèn)的臨界資源此刻是否被訪問(wèn)。v退出區(qū)增加在臨界區(qū)后面的一段代碼，用于將臨界資源的訪問(wèn)標(biāo)志恢復(fù)為未被訪問(wèn)標(biāo)志。v剩余區(qū)進(jìn)程中除了進(jìn)入?yún)^(qū)、臨界區(qū)及退出區(qū)之外的其余代碼。2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū) 要進(jìn)入臨界區(qū)的若干進(jìn)程必須滿足要進(jìn)入臨界區(qū)的若干進(jìn)程必須滿足：（1）一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)（2）任何時(shí)候，處于臨界區(qū)的進(jìn)程不得多于一個(gè)（3）進(jìn)入臨界

33、區(qū)的進(jìn)程要在有限的時(shí)間內(nèi)退出（4）如果不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出處理機(jī)資源解決臨界區(qū)（互斥）問(wèn)題的幾類方法：解決臨界區(qū)（互斥）問(wèn)題的幾類方法：（1）軟件方法（2）硬件方法（3）P-V操作進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)同步機(jī)制3 3、同步機(jī)制應(yīng)遵循的規(guī)則、同步機(jī)制應(yīng)遵循的規(guī)則q 有空讓進(jìn)有空讓進(jìn)( (空閑讓進(jìn)）空閑讓進(jìn)）: :當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。q 互斥（忙則等待）互斥（忙則等待）: :當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪問(wèn)，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問(wèn)

34、q 有限等待有限等待: :對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死等”狀態(tài).q 讓權(quán)等待讓權(quán)等待: :當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”。返回二、信號(hào)量機(jī)制解決臨界區(qū)（互斥）問(wèn)題的幾類方法解決臨界區(qū)（互斥）問(wèn)題的幾類方法n* *軟件方法軟件方法RepeatRepeat flagi:=true;turn:=j;flagi:=true;turn:=j; while(flagi and turn=j) while(flagi and turn=j) do no_op; do no_op; critical section crit

35、ical section flagi:=false;flagi:=false; remainder section remainder sectionUntil falseUntil false遵循遵循“忙則等待忙則等待”；“有空讓進(jìn)有空讓進(jìn)”，但難但難度和局限性較大。度和局限性較大。u硬件方法硬件方法 用硬件方法來(lái)解決臨界區(qū)問(wèn)題，用硬件方法來(lái)解決臨界區(qū)問(wèn)題，即定義一些特殊指令，如即定義一些特殊指令，如TEST TEST 、SETSET、SWAPSWAP等指令，有效地實(shí)現(xiàn)了等指令，有效地實(shí)現(xiàn)了進(jìn)程互斥，但不滿足進(jìn)程互斥，但不滿足“讓權(quán)等待讓權(quán)等待”。有效解決同步問(wèn)題的方法有效解決同步問(wèn)題的方法

36、信號(hào)機(jī)制信號(hào)機(jī)制為臨界資源加鎖的方法二、信號(hào)量機(jī)制n信號(hào)量機(jī)制是荷蘭科學(xué)家E.W.Dijkstra在1965年提出的一種同步機(jī)制，也稱為P、V操作。由最初的整型信號(hào)量發(fā)展為記錄型信號(hào)量，進(jìn)而發(fā)展為信號(hào)量集。n整型信號(hào)量整型信號(hào)量n記錄型信號(hào)量記錄型信號(hào)量n信號(hào)量集（信號(hào)量集（AND信號(hào)量集、一般信號(hào)量集）信號(hào)量集、一般信號(hào)量集）1 1、整型信號(hào)量、整型信號(hào)量n整型信號(hào)量整型信號(hào)量非負(fù)整數(shù)，除了初始化外，只能通過(guò)兩個(gè)原子操作waitwait和signalsignal（P P，V V）來(lái)訪問(wèn)。nwaitwait和和signalsignal操作描述操作描述： wait(S)wait(S)： whil

37、e Swhile S 0 do no-op0 do no-op 測(cè)試有無(wú)可用資源 S:=S-1; S:=S-1; 可用資源數(shù)減一個(gè)單位 signal(S): S:=S+1;signal(S): S:=S+1; 主要問(wèn)題主要問(wèn)題：只要S S 0 0， waitwait操作就不斷地測(cè)試（盲等），因而，未做到“讓權(quán)等待”。 2 2、記錄型信號(hào)量、記錄型信號(hào)量n基本思想基本思想 1、設(shè)置一個(gè)代表資源數(shù)目的整型變量valuevalue（資源信號(hào)量） 2、設(shè)置一鏈表L L用于鏈接所有等待的進(jìn)程記錄型信號(hào)量的數(shù)據(jù)結(jié)構(gòu)記錄型信號(hào)量的數(shù)據(jù)結(jié)構(gòu) Type semaphore=record value:intege

38、r; L: list of process; endwaitwait和和signalsignal操作描述操作描述： wait(S)wait(S)： S.value:=S.value-1; S.value:=S.value-1; if S.value0 then block(S.L);if S.value0），一群生產(chǎn)者進(jìn)程），一群生產(chǎn)者進(jìn)程p1,p2,，pm，一群消費(fèi)者進(jìn)程，一群消費(fèi)者進(jìn)程c1,c2,，cm，如圖所示。假定生產(chǎn)者和消費(fèi)，如圖所示。假定生產(chǎn)者和消費(fèi)者是相互等效，只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，者是相互等效，只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，類似地，只要緩

39、沖區(qū)未空，消費(fèi)者便可以從緩沖區(qū)取走產(chǎn)品并消耗它。類似地，只要緩沖區(qū)未空，消費(fèi)者便可以從緩沖區(qū)取走產(chǎn)品并消耗它。生產(chǎn)者和消費(fèi)者的同步關(guān)系將禁止生產(chǎn)者向滿的緩沖區(qū)輸送產(chǎn)品，也生產(chǎn)者和消費(fèi)者的同步關(guān)系將禁止生產(chǎn)者向滿的緩沖區(qū)輸送產(chǎn)品，也禁止消費(fèi)者從空的緩沖區(qū)提取產(chǎn)品。禁止消費(fèi)者從空的緩沖區(qū)提取產(chǎn)品。 P1P2pmc1c2cmn設(shè)置兩個(gè)同步信號(hào)量及一互斥信號(hào)量設(shè)置兩個(gè)同步信號(hào)量及一互斥信號(hào)量empty：說(shuō)明空緩沖單元的數(shù)目，其初值為有界緩沖區(qū)的大小說(shuō)明空緩沖單元的數(shù)目，其初值為有界緩沖區(qū)的大小n n。Full： 說(shuō)明滿緩沖單元的數(shù)目（即產(chǎn)品數(shù)目），其初值為說(shuō)明滿緩沖單元的數(shù)目（即產(chǎn)品數(shù)目），其初值為0

40、.0.Mutex: 說(shuō)明該有界緩沖區(qū)是一臨界資源，必須互斥使用，說(shuō)明該有界緩沖區(qū)是一臨界資源，必須互斥使用， 其初值為其初值為1 1。 “ “生產(chǎn)者生產(chǎn)者消費(fèi)者消費(fèi)者”問(wèn)題的解決問(wèn)題的解決n“生產(chǎn)者生產(chǎn)者消費(fèi)者消費(fèi)者”問(wèn)題的同步算法描述問(wèn)題的同步算法描述 semaphore full=0; /*表示滿緩沖區(qū)的數(shù)目表示滿緩沖區(qū)的數(shù)目*/ semaphore empty=n; /*表示空緩沖區(qū)的數(shù)目表示空緩沖區(qū)的數(shù)目*/ semaphore mutex=1; /*表示對(duì)緩沖區(qū)進(jìn)程操作的互斥信號(hào)量表示對(duì)緩沖區(qū)進(jìn)程操作的互斥信號(hào)量*/Main() cobegin producer(); consume

41、r(); coend “ “生產(chǎn)者生產(chǎn)者消費(fèi)者消費(fèi)者”問(wèn)題的解決問(wèn)題的解決 while(true) while(true) 生產(chǎn)一個(gè)產(chǎn)品生產(chǎn)一個(gè)產(chǎn)品; ; p(empty); p(empty); P(mutex); P(mutex); 將一個(gè)產(chǎn)品送入緩沖區(qū)；將一個(gè)產(chǎn)品送入緩沖區(qū)； V(mutex);V(mutex); V(full); V(full); Producer() while(true) while(true) p(full); p(full); P(mutex); P(mutex); 從緩沖區(qū)取走一個(gè)產(chǎn)品從緩沖區(qū)取走一個(gè)產(chǎn)品; ; V(mutex); V(mutex); V(emp

42、ty); V(empty); 消費(fèi)一個(gè)產(chǎn)品；消費(fèi)一個(gè)產(chǎn)品； consumer()“生產(chǎn)者生產(chǎn)者- -消費(fèi)者消費(fèi)者”問(wèn)題中應(yīng)注意問(wèn)題中應(yīng)注意1. 互斥信號(hào)量的P,V操作在每一程序中必須成對(duì)出現(xiàn).2. 資源信號(hào)量(full,empty)也必須成對(duì)出現(xiàn),但可分別處于不同的程序中.3. 多個(gè)P操作順序不能顛倒.4. 先執(zhí)行資源信號(hào)量的P操作,再執(zhí)行互斥信號(hào)量的P操作,否則可能引起進(jìn)程死鎖.5. 它是一個(gè)同步問(wèn)題： （1）消費(fèi)者想要取產(chǎn)品，有界緩沖區(qū)中至少有一個(gè)單元是滿的。 （2）生產(chǎn)者想要放產(chǎn)品，有界緩沖區(qū)中至少有一個(gè)是空的。6. 它是一互斥問(wèn)題 有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程

43、必須互斥執(zhí)行。返回2 2、“哲學(xué)家進(jìn)餐哲學(xué)家進(jìn)餐”問(wèn)題問(wèn)題n問(wèn)題描述：?jiǎn)栴}描述： 有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。他們共用一張圓桌，分別坐在五張椅子上。在圓桌上有五個(gè)碗和五支筷子，平時(shí)一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐畢，放下筷子又繼續(xù)思考。n哲學(xué)家進(jìn)餐問(wèn)題可看作是并發(fā)進(jìn)程并發(fā)執(zhí)行時(shí)，處理共享資源的一個(gè)有代表性的問(wèn)題。n semaphore stick5=1,1,1,1,1; /*分別表示分別表示5支筷子支筷子*/ Main() cobegin philosopher(0); philosopher(1); ph

44、ilosopher(2); philosopher(3); philosopher(4); coend 哲學(xué)家進(jìn)餐問(wèn)題的解決哲學(xué)家進(jìn)餐問(wèn)題的解決 while(true) while(true) 思考思考; ; p(sticki); p(sticki); P(stick(i+1)%5); P(stick(i+1)%5); 進(jìn)餐；進(jìn)餐； V(sticki);V(sticki); V(stick(i+1)%5); V(stick(i+1)%5); 第第i個(gè)哲學(xué)家的活動(dòng)算法個(gè)哲學(xué)家的活動(dòng)算法philosopher(int i)返回說(shuō)明：說(shuō)明：1、此算法可以保證不會(huì)有相保證不會(huì)有相鄰的兩位哲學(xué)家同時(shí)進(jìn)餐

45、鄰的兩位哲學(xué)家同時(shí)進(jìn)餐。2、若五位哲學(xué)家同時(shí)饑餓而各自拿起了左邊的筷子，這使五個(gè)信號(hào)量stick均為0，當(dāng)他們?cè)噲D去拿起右邊的筷子時(shí)，都將因無(wú)筷子而無(wú)限期地等待下去，即可能會(huì)引起死鎖可能會(huì)引起死鎖。3 3、“讀者讀者寫(xiě)者寫(xiě)者”問(wèn)題問(wèn)題n問(wèn)題描述：?jiǎn)栴}描述： 一個(gè)數(shù)據(jù)對(duì)象（數(shù)據(jù)文件或記錄）可被多個(gè)進(jìn)程共享。其中，reader進(jìn)程要求讀，writer 進(jìn)程要求寫(xiě)或修改。允許多個(gè)reader進(jìn)程同時(shí)讀共享數(shù)據(jù)，但絕不允許一個(gè)writer進(jìn)程與其它的reader進(jìn)程或writer進(jìn)程同時(shí)訪問(wèn)，即writer進(jìn)程必須與其它進(jìn)程互斥訪問(wèn)共享對(duì)象。n“讀者讀者寫(xiě)者寫(xiě)者”問(wèn)題的同步算法描述問(wèn)題的同步算法描述

46、設(shè)置一個(gè)共享變量和兩個(gè)信號(hào)量：設(shè)置一個(gè)共享變量和兩個(gè)信號(hào)量：共享變量Readcount：記錄當(dāng)前正在讀數(shù)據(jù)集的讀進(jìn)程數(shù)目， 初值為0。讀互斥信號(hào)量Rmutex ：表示讀進(jìn)程互斥地訪問(wèn)共享變量 readcount，初值為1.寫(xiě)互斥信號(hào)量wmutex：表示寫(xiě)進(jìn)程與其它進(jìn)程（讀、寫(xiě)） 互斥地訪問(wèn)數(shù)據(jù)集，初值為1. “ “讀者讀者寫(xiě)者寫(xiě)者”問(wèn)題的解決問(wèn)題的解決n“讀者讀者寫(xiě)者寫(xiě)者”問(wèn)題的同步算法描述問(wèn)題的同步算法描述 semaphore rmutex=1; semaphore wmutex=1; int readcount=0; Main() cobegin reader(); writer(); c

47、oend “ “讀者讀者寫(xiě)者寫(xiě)者”問(wèn)題的解決問(wèn)題的解決 while(true) while(true) p(rmutex); p(rmutex); if(readcount= =0) p(wmutex); if(readcount= =0) p(wmutex);/ /* *第一位讀者阻止寫(xiě)者第一位讀者阻止寫(xiě)者* */ / readcount+; readcount+; V(rmutex); V(rmutex); 讀數(shù)據(jù)集；讀數(shù)據(jù)集； p(rmutex); p(rmutex); readcount-; readcount-; if(readcount= =0) v(wmutex); if(rea

48、dcount= =0) v(wmutex);/ /* *第末位讀者允許寫(xiě)者進(jìn)第末位讀者允許寫(xiě)者進(jìn)* */ / V(rmutex); V(rmutex); reader()修改修改readcount修改修改readcount while(true) p(wmutex); /*阻止其它進(jìn)程（讀、寫(xiě)）進(jìn)阻止其它進(jìn)程（讀、寫(xiě)）進(jìn)/ 寫(xiě)數(shù)據(jù)集；寫(xiě)數(shù)據(jù)集； V(wmutex); /*允許其它進(jìn)程（讀、寫(xiě)）進(jìn)允許其它進(jìn)程（讀、寫(xiě)）進(jìn)/writer()返回2.5 管程機(jī)制n信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程同步的問(wèn)題信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程同步的問(wèn)題 用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程間的同步和互斥，即方便又有效。但存在以下兩個(gè)問(wèn)題：v 每個(gè)訪

49、問(wèn)臨界資源每個(gè)訪問(wèn)臨界資源的進(jìn)程都必須自備同步操作（的進(jìn)程都必須自備同步操作（P P、V V操作）操作），這使大量的同步操作分散在各個(gè)進(jìn)程中，給系統(tǒng)的管理帶來(lái)麻煩。給系統(tǒng)的管理帶來(lái)麻煩。v會(huì)因同步操作使用不當(dāng)而導(dǎo)致系統(tǒng)死鎖會(huì)因同步操作使用不當(dāng)而導(dǎo)致系統(tǒng)死鎖。n解決方法解決方法-管程（管程（Monitors)Monitors) Dijkstra于1971年提出，為每個(gè)共享資源設(shè)立一個(gè)“秘書(shū)”來(lái)管理對(duì)它的訪問(wèn)。一切來(lái)訪者都要通過(guò)秘書(shū)，而秘書(shū)每次僅允許一個(gè)來(lái)訪者（進(jìn)程）來(lái)訪問(wèn)共享資源。這樣既便于系統(tǒng)管理共享資源，又能保證進(jìn)程的互斥訪問(wèn)和同步。1973年，Hanson和Hoare又把“秘書(shū)”概念發(fā)展為

50、管程概念。 一、管程的基本概念基本思想基本思想 把訪問(wèn)某種臨界資源的所有進(jìn)程的同步操作都集中起來(lái)，構(gòu)成一個(gè)所謂的“秘書(shū)秘書(shū)”進(jìn)程（管程）進(jìn)程（管程），凡是訪問(wèn)臨界資源的進(jìn)程，都需要報(bào)告 “秘書(shū)”，由秘書(shū)來(lái)實(shí)現(xiàn)諸進(jìn)程的同步。管程的定義管程的定義 一個(gè)數(shù)據(jù)結(jié)構(gòu)一個(gè)數(shù)據(jù)結(jié)構(gòu)和在該數(shù)據(jù)結(jié)構(gòu)上能被并發(fā)進(jìn)程所執(zhí)行的一組操作一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。如下圖所示。一、管程的基本概念條件變量條件變量 在管程機(jī)制中，當(dāng)某進(jìn)程通過(guò)管程請(qǐng)求臨界資源未能滿足時(shí)，管程便調(diào)用wait原語(yǔ)使該進(jìn)程等待，但等待的原因可能有多個(gè)，為了加以區(qū)別，在P，V操作前，引入條件變量加以說(shuō)明。 （1 1）條件變量的定義

51、格式）條件變量的定義格式 Var x,y: condition （2 2）對(duì)條件變量執(zhí)行的兩種操作）對(duì)條件變量執(zhí)行的兩種操作nWait操作 如x.wait用來(lái)將執(zhí)行進(jìn)程掛到與條件變量x相應(yīng)的 等待隊(duì)列上。nSignal操作 如x.signal用來(lái)喚醒與條件變量x相應(yīng)的等待隊(duì)列 上的一個(gè)進(jìn)程。 二、用管程機(jī)制解決生產(chǎn)者二、用管程機(jī)制解決生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題1、建立Producer-consumer(PC)管程 Type producer-consumer=monitor var in,out,count:integer; buffer:array0,n-1 of item; notfull

52、,notempty:condition; put(item); get(item); begin in:=out:=0; /* 初始化代碼*/ count:=0; end管程中的兩個(gè)條件變量：管程中的兩個(gè)條件變量： (1) notfull 當(dāng)緩沖區(qū)中不全滿，該變量為真。 (2)notempty 當(dāng)緩沖區(qū)中不全空，該變量為真。二、用管程機(jī)制解決生產(chǎn)者二、用管程機(jī)制解決生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題1、建立Producer-consumer(PC)管程n put(item)過(guò)程 生產(chǎn)者利用此過(guò)程將自已的消息放到緩沖池中，若發(fā)現(xiàn)緩沖已滿（count n),則等待。nGet(item)過(guò)程 消費(fèi)者利用此過(guò)

53、程將緩沖池中的消息取走，若發(fā)現(xiàn)緩沖已空（count 0),則等待。 put(item) put(item)Procedure entry put(item) begin if count n then full.wait; buffer(in):=nextp; in:=(in+1) mod n; count:=count+1; if empty.queue then empty.signal; end get(item) get(item)Procedure entry get(item) begin if count 0 then empty.wait; nextc:=buffer(out)

54、; out:=(out+1) mod n; count:=count-1; if full.queue then full.signal; end2 2、生產(chǎn)者、生產(chǎn)者消費(fèi)者問(wèn)題的解決消費(fèi)者問(wèn)題的解決Producer:begin repeat produce an item in nextp; PC.put(item); until false endConsumer:begin repeat PC.get(item); consume the item in nextc; until false end返回目錄 2.6 進(jìn)程通信高級(jí)通信一、進(jìn)程通信的類型一、進(jìn)程通信的類型 進(jìn)程通信是指進(jìn)程之間的信息交換。根據(jù)所交換的信息量的多少分為： v低級(jí)通信低級(jí)通信 進(jìn)程之間交換的信息量較少且效率低。如進(jìn)程同步和互斥。v高級(jí)通信高級(jí)通信 進(jìn)程之間交換的信息量較多且效率高。又分：共享存儲(chǔ)器系統(tǒng)共享存儲(chǔ)器系統(tǒng) 指進(jìn)程之間通過(guò)對(duì)共享存儲(chǔ)區(qū)讀寫(xiě)來(lái)交換數(shù)據(jù)。消息傳遞系統(tǒng)消息傳遞系統(tǒng) 指進(jìn)程間的通信以消息為單位，程序員可通過(guò)通信原語(yǔ) 實(shí)現(xiàn)通信，按其實(shí)現(xiàn)方式不同可分為：直接通信方式直接通信方式 發(fā)送進(jìn)程直接把消息發(fā)送給接收進(jìn)程。間接通信方式間接通信方式 發(fā)送進(jìn)程把消息發(fā)送到某個(gè)中間實(shí)體（信箱），接收進(jìn) 程從中取得消息。管道通信系統(tǒng)管道通信系統(tǒng) 發(fā)送進(jìn)程（寫(xiě)進(jìn)程）以字符流形式將大量數(shù)據(jù)送入管道（管道：