華東理工815操作系統(tǒng)第4講

1

StartReadyQueueEventQueueEventExitTimeSliceCPU2

StartReadyQueueEventQueueEventExitTimeSliceCPU3

StartReadyQueueEventQueueEventExitTimeSliceCPU4

StartReadyQueueEventQueueEventExitTimeSliceCPU5

StartReadyQueueEventQueueEventExitTimeSliceCPU6

StartReadyQueueEventQueueEventExitTimeSliceCPU7

StartReadyQueueEventQueueEventExitTimeSliceCPU8

StartReadyQueueEventQueueEventExitTimeSliceCPU9

StartReadyQueueEventQueueEventExitTimeSliceCPU10

StartReadyQueueEventQueueEventExitTimeSliceCPU11

StartReadyQueueEventQueueEventExitTimeSliceCPU12

StartReadyQueueEventQueueEventExitTimeSliceCPU13

StartReadyQueueEventQueueEventExitTimeSliceCPU14

StartReadyQueueEventQueueEventExitTimeSliceCPU進(jìn)程控制塊ProcessControlBlock

進(jìn)程控制塊PCB是操作系統(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)志。例：Linux中的PCB1、進(jìn)程控制塊PCB的作用是OS對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的根據(jù)。也是系統(tǒng)用來(lái)感知進(jìn)程存在的根據(jù)，即PCB是進(jìn)程存在的唯一標(biāo)志。

2、進(jìn)程控制塊PCB中的信息（1）

根據(jù)操作系統(tǒng)的要求不同，PCB所包含信息有些不同，但通常包含以下信息：進(jìn)程標(biāo)識(shí)符：

內(nèi)部標(biāo)識(shí)符（由系統(tǒng)創(chuàng)建進(jìn)程時(shí)分配給進(jìn)程的唯一標(biāo)識(shí)號(hào)，通常為一整數(shù)，稱(chēng)為進(jìn)程號(hào)，用于區(qū)分不同的進(jìn)程）

外部標(biāo)識(shí)符（由字母、數(shù)字組成，由用戶(hù)訪問(wèn)該進(jìn)程時(shí)使用）。

2、進(jìn)程控制塊PCB中的信息（2）處理機(jī)狀態(tài)（斷點(diǎn)信息）：

即處理機(jī)中各種寄存器（通用寄存器、PC、PSW等）的內(nèi)容進(jìn)程調(diào)度：

記錄了進(jìn)程調(diào)度的相關(guān)信息（狀態(tài)、優(yōu)先級(jí)、事件等）。進(jìn)程控制：

記錄了系統(tǒng)對(duì)進(jìn)程控制的信息（程序和數(shù)據(jù)的地址、同步機(jī)制、資源清單、鏈接指針）

3、進(jìn)程控制塊PCB的組織方式

在一個(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)程組織在一個(gè)索引表中，索引表的表項(xiàng)指向相應(yīng)的PCB，不同狀態(tài)對(duì)應(yīng)不同的索引表。0PCB90PCB89PCB77PCB6

PCB58PCB40PCB33PCB24PCB1執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針按鏈接方式組織PCB按索引方式組織PCBPCB9PCB8PCB7PCB6

PCB5PCB4PCB3PCB2PCB1執(zhí)行指針就緒表指針阻塞表指針就緒索引表阻塞索引表2.2進(jìn)程的控制進(jìn)程控制是進(jìn)程管理中最基本的功能，即對(duì)系統(tǒng)中所有的進(jìn)程實(shí)施有效的管理，其功能包括

進(jìn)程的創(chuàng)建進(jìn)程的撤消進(jìn)程的阻塞與喚醒等，這些功能一般是由操作系統(tǒng)的內(nèi)核來(lái)完成。OS內(nèi)核：

在現(xiàn)代OS中，常把一些功能模塊（與硬件緊密相關(guān)的、常用設(shè)備的驅(qū)動(dòng)程序及運(yùn)行頻率較高的）放在緊靠硬件的軟件層次中，加以特殊保護(hù)，同時(shí)把它們常駐內(nèi)存，以提高OS的運(yùn)行效率，這部分功能模塊就稱(chēng)OS的內(nèi)核。內(nèi)核是基于硬件的第一層軟件擴(kuò)充，它為系統(tǒng)控制和管理進(jìn)程提供了良好的環(huán)境。

為了防止OS及其關(guān)鍵數(shù)據(jù)（如PCB等）不被用戶(hù)有意或無(wú)意破壞,通常將處理機(jī)的執(zhí)行狀態(tài)分為兩種：處理機(jī)狀態(tài)特權(quán)(執(zhí)行指令,訪問(wèn)）程序系統(tǒng)態(tài)(核心態(tài)、管態(tài))

用戶(hù)態(tài)（目態(tài)）補(bǔ)充：處理機(jī)的執(zhí)行狀態(tài)較高(一切指令,所有寄存器及存儲(chǔ)區(qū))OS內(nèi)核較低(規(guī)定指令,指定寄存器及存儲(chǔ)區(qū))用戶(hù)程序或系統(tǒng)外層的應(yī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、進(jìn)程圖：又稱(chēng)為進(jìn)程樹(shù)或進(jìn)程家族樹(shù)，是描述進(jìn)程家族關(guān)系的一棵有向樹(shù)。ABDECF父進(jìn)程祖先進(jìn)程子進(jìn)程2、引起進(jìn)程創(chuàng)建的事件（1）

在多道程序環(huán)境中，只有進(jìn)程才可以在系統(tǒng)中運(yùn)行。為了使一個(gè)程序能運(yùn)行，必須為它創(chuàng)建進(jìn)程。導(dǎo)致進(jìn)程創(chuàng)建的事件有：用戶(hù)登錄：

在分時(shí)OS中，用戶(hù)在終端鍵入登錄命令后，如是合法用戶(hù)，則系統(tǒng)為該終端創(chuàng)建一進(jìn)程，并插入就緒隊(duì)列。2、引起進(jìn)程創(chuàng)建的事件（2）作業(yè)調(diào)度：在批處理OS中，當(dāng)按某算法調(diào)度一作業(yè)進(jìn)內(nèi)存，系統(tǒng)為之分配必要資源，同時(shí)為該作業(yè)創(chuàng)建一進(jìn)程，并插入就緒隊(duì)列。

提供服務(wù)：在程序運(yùn)行中，若用戶(hù)需某種服務(wù)，則系統(tǒng)創(chuàng)建一進(jìn)程為用戶(hù)提供服務(wù)，并插入就緒隊(duì)列。應(yīng)用請(qǐng)求：在運(yùn)行中，由于應(yīng)用進(jìn)程本身的需求，自己創(chuàng)建一進(jìn)程，并插入就緒隊(duì)列。3、進(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è)空閑的PCB為新進(jìn)程分配資源對(duì)PCB初始化將PCB插入就緒隊(duì)列返回一個(gè)進(jìn)程標(biāo)識(shí)號(hào)

一個(gè)進(jìn)程在完成其任務(wù)后，應(yīng)加以撤消，以便及時(shí)釋放其占有的各類(lèi)資源。1、導(dǎo)致進(jìn)程撤消的事件進(jìn)程正常結(jié)束進(jìn)程異常結(jié)束外界干預(yù)

如果系統(tǒng)中發(fā)生了要求撤消進(jìn)程的事件，OS便調(diào)用撤消原語(yǔ)去撤消進(jìn)程。2、撤消原語(yǔ)可采用2種撤消策略只撤消指定的進(jìn)程撤消指定進(jìn)程及其所有的子孫進(jìn)程二、進(jìn)程的撤消

3、進(jìn)程撤消的過(guò)程在運(yùn)行？NYNY由標(biāo)識(shí)符在PCB集中找PCB并讀狀態(tài)歸還占有資源從所在隊(duì)列(索引表)撤消PCB中止運(yùn)行重置調(diào)度標(biāo)志終止所有子孫進(jìn)程有子孫進(jìn)程？

當(dāng)一個(gè)進(jìn)程期待的事件還沒(méi)有出現(xiàn)時(shí)，該進(jìn)程調(diào)用阻塞原語(yǔ)block()將自己阻塞起來(lái)；

block()功能：將進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)。對(duì)于處于阻塞狀態(tài)的進(jìn)程，當(dāng)該進(jìn)程期待的事件出現(xiàn)時(shí)，由其它相關(guān)進(jìn)程調(diào)用喚醒原語(yǔ)wakeup()將阻塞的進(jìn)程喚醒，使其進(jìn)入就緒狀態(tài)；

wakeup()功能：將進(jìn)程由阻塞狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。三、進(jìn)程的阻塞與喚醒

1、引起進(jìn)程阻塞和喚醒的事件請(qǐng)求系統(tǒng)服務(wù)啟動(dòng)某種操作新數(shù)據(jù)尚未到達(dá)無(wú)新工作可做三、進(jìn)程的阻塞與喚醒停止執(zhí)行修改PCB中的狀態(tài)（執(zhí)行→阻塞）插入到相應(yīng)的阻塞隊(duì)列另調(diào)度一就緒進(jìn)程，切換CPU（保留阻塞進(jìn)程的CPU狀態(tài)信息

至PCB，再按新進(jìn)程PCB中的狀

態(tài)設(shè)置CPU環(huán)境）將阻塞進(jìn)程移出阻塞隊(duì)列插入到就緒隊(duì)列如需要，則另調(diào)度

一就緒進(jìn)程，切換CPU修改PCB中的狀態(tài)（阻塞→就緒）2、進(jìn)程的阻塞過(guò)程3、進(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)程的掛起與激活2、進(jìn)程的掛起過(guò)程3、進(jìn)程的激活過(guò)程N(yùn)Y將掛起進(jìn)程從外存調(diào)入內(nèi)存決定是否需重新調(diào)度修改PCB中的狀態(tài)*（靜止→活動(dòng)）活動(dòng)就緒？檢查該進(jìn)程狀態(tài)修改PCB中的狀態(tài)*（活動(dòng)→靜止）復(fù)制PCB至指定內(nèi)存區(qū)域運(yùn)行？另調(diào)度一

就緒進(jìn)程YN進(jìn)程間CPU的切換/上下文切換2.3進(jìn)程同步（1）進(jìn)程同步：指對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)；同步的任務(wù)：使系統(tǒng)中各進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性；系統(tǒng)中各進(jìn)程之間在邏輯上的相互制約的關(guān)系：直接關(guān)系—同步間接關(guān)系—互斥2.3進(jìn)程同步（2）用來(lái)實(shí)現(xiàn)同步的機(jī)制稱(chēng)為同步機(jī)制。如：軟件和硬件的方法；信號(hào)量機(jī)制；管程機(jī)制2.3進(jìn)程同步（3）進(jìn)程同步的基本概念兩種形式的制約關(guān)系臨界資源、臨界區(qū)同步機(jī)制應(yīng)遵循的規(guī)則信號(hào)量機(jī)制整型信號(hào)量記錄型信號(hào)量AND型信號(hào)量集、一般信號(hào)量集信號(hào)量的應(yīng)用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥信號(hào)量描述進(jìn)程間的前趨關(guān)系管程機(jī)制一、進(jìn)程同步的基本概念1、進(jìn)程之間兩種形式的制約關(guān)系系統(tǒng)中各進(jìn)程之間在邏輯上存在著兩種制約關(guān)系：直接相互制約關(guān)系/相互合作關(guān)系（進(jìn)程同步）：即為完成同一個(gè)任務(wù)的各進(jìn)程之間，因需要協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的直接制約關(guān)系。

間接相互制約關(guān)系/資源共享關(guān)系（進(jìn)程互斥）：是進(jìn)程共享獨(dú)占型資源而必須互斥執(zhí)行的間接制約關(guān)系。同步與互斥比較同步（直接制約）互斥（間接制約）進(jìn)程-進(jìn)程進(jìn)程-資源-進(jìn)程時(shí)間次序上受到某種限制競(jìng)爭(zhēng)不到某一物理資源時(shí)不允許進(jìn)程工作相互清楚對(duì)方的存在及作用，交換信息不一定清楚其它進(jìn)程的情況往往指有幾個(gè)進(jìn)程共同完成一個(gè)任務(wù)往往指多個(gè)任務(wù)多個(gè)進(jìn)程間通訊制約例：生產(chǎn)與消費(fèi)之間，發(fā)送與接收之間，寫(xiě)者與讀者之間例：交通十字路口，單軌火車(chē)的撥道岔2、臨界資源、臨界區(qū)（1）一次只允許一個(gè)進(jìn)程使用的共享資源稱(chēng)為臨界資源，如打印機(jī)，繪圖機(jī)，變量，數(shù)據(jù)等，各進(jìn)程間采取互斥方式實(shí)現(xiàn)對(duì)這種臨界資源的共享，從而實(shí)現(xiàn)并發(fā)進(jìn)程的封閉性。例：生產(chǎn)者-消費(fèi)者問(wèn)題一組生產(chǎn)者向一組消費(fèi)者提供產(chǎn)品，它們共享一個(gè)緩沖池，生產(chǎn)者向其中投放產(chǎn)品，消費(fèi)者從中取得產(chǎn)品。它是許多相互合作進(jìn)程的抽象，如輸入進(jìn)程與計(jì)算進(jìn)程；計(jì)算進(jìn)程與打印進(jìn)程等。2、臨界資源、臨界區(qū)（2）設(shè)緩沖池的長(zhǎng)度為n（n>0），一群生產(chǎn)者進(jìn)程P1,P2,…，Pm，一群消費(fèi)者進(jìn)程C1,C2,…，Ck，如圖所示。假定生產(chǎn)者和消費(fèi)者是相互等效，只要緩沖池未滿(mǎn)，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，類(lèi)似地，只要緩沖池未空，消費(fèi)者便可以從緩沖區(qū)取走產(chǎn)品并消耗它。生產(chǎn)者和消費(fèi)者進(jìn)程是以異步方式運(yùn)行的，但必須保持同步關(guān)系，即禁止生產(chǎn)者向滿(mǎn)的緩沖池輸送產(chǎn)品，也禁止消費(fèi)者從空的緩沖池提取產(chǎn)品。

…P1P2…PmC1C2…Ck2、臨界資源、臨界區(qū)（3）生產(chǎn)者消費(fèi)者進(jìn)程共享如下變量：TYPEitem=…;VARn:integer;buffer:array[0..n-1]ofitem;in,out:0..n-1;counter:0..n;

注：n為緩沖池中緩沖區(qū)的個(gè)數(shù)；buffer為具有n個(gè)緩沖區(qū)的緩沖池；in和out為指針，分別指向下一個(gè)可投放產(chǎn)品的緩沖區(qū)和下一個(gè)可獲取產(chǎn)品的緩沖區(qū)2、臨界資源、臨界區(qū)（4）生產(chǎn)者消費(fèi)者進(jìn)程可分別描述為：producer:repeat

……produceaniteminnextp;

……whilecounter=ndono-op;buf