華東理工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)行而為每一個進(jìn)程定義的一個數(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對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的根據(jù)。也是系統(tǒng)用來感知進(jìn)程存在的根據(jù)，即PCB是進(jìn)程存在的唯一標(biāo)志。

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

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

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

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

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

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

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

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

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

在一個系統(tǒng)中，通常存在著許多進(jìn)程，它們所處的狀態(tài)不同，為了方便進(jìn)程的調(diào)度和管理，需要將各進(jìn)程的PCB用適當(dāng)方法組織起來。目前常用的組織方式有：鏈接方式

圖示

把同一狀態(tài)的PCB鏈接成一個隊列，這樣就形成了就緒隊列、阻塞隊列等。索引方式

圖示

將同一狀態(tài)的進(jìn)程組織在一個索引表中，索引表的表項指向相應(yīng)的PCB，不同狀態(tài)對應(yīng)不同的索引表。0PCB90PCB89PCB77PCB6

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

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

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

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

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

用戶態(tài)（目態(tài)）補(bǔ)充：處理機(jī)的執(zhí)行狀態(tài)較高(一切指令,所有寄存器及存儲區(qū))OS內(nèi)核較低(規(guī)定指令,指定寄存器及存儲區(qū))用戶程序或系統(tǒng)外層的應(yīng)用程序一、進(jìn)程創(chuàng)建

一個進(jìn)程可以創(chuàng)建若干個新進(jìn)程，新創(chuàng)建的進(jìn)程又可以創(chuàng)建子進(jìn)程，為了描述進(jìn)程之間的創(chuàng)建關(guān)系，引入了進(jìn)程圖（如下圖所示：）

1、進(jìn)程圖：又稱為進(jìn)程樹或進(jìn)程家族樹，是描述進(jìn)程家族關(guān)系的一棵有向樹。ABDECF父進(jìn)程祖先進(jìn)程子進(jìn)程2、引起進(jìn)程創(chuàng)建的事件（1）

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

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

提供服務(wù)：在程序運(yùn)行中，若用戶需某種服務(wù)，則系統(tǒng)創(chuàng)建一進(jìn)程為用戶提供服務(wù)，并插入就緒隊列。應(yīng)用請求：在運(yùn)行中，由于應(yīng)用進(jìn)程本身的需求，自己創(chuàng)建一進(jìn)程，并插入就緒隊列。3、進(jìn)程的創(chuàng)建操作系統(tǒng)一旦發(fā)現(xiàn)了要求創(chuàng)建進(jìn)程的事件后，便調(diào)用進(jìn)程創(chuàng)建原語create()按以下過程創(chuàng)建一新進(jìn)程：申請一個空閑的PCB為新進(jìn)程分配資源對PCB初始化將PCB插入就緒隊列返回一個進(jìn)程標(biāo)識號

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

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

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

當(dāng)一個進(jìn)程期待的事件還沒有出現(xiàn)時，該進(jìn)程調(diào)用阻塞原語block()將自己阻塞起來；

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

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

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

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

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

一就緒進(jìn)程，切換CPU修改PCB中的狀態(tài)（阻塞→就緒）2、進(jìn)程的阻塞過程3、進(jìn)程的喚醒過程當(dāng)引起進(jìn)程掛起的事件發(fā)生時，系統(tǒng)就將利用掛起原語suspend()將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。當(dāng)發(fā)生激活進(jìn)程的事件時，系統(tǒng)就將利用激活原語active()將指定進(jìn)程激活。1、引起進(jìn)程的掛起與激活的事件四、進(jìn)程的掛起與激活2、進(jìn)程的掛起過程3、進(jìn)程的激活過程N(yùn)Y將掛起進(jìn)程從外存調(diào)入內(nèi)存決定是否需重新調(diào)度修改PCB中的狀態(tài)*（靜止→活動）活動就緒？檢查該進(jìn)程狀態(tài)修改PCB中的狀態(tài)*（活動→靜止）復(fù)制PCB至指定內(nèi)存區(qū)域運(yùn)行？另調(diào)度一

就緒進(jìn)程YN進(jìn)程間CPU的切換/上下文切換2.3進(jìn)程同步（1）進(jìn)程同步：指對多個相關(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）用來實現(xiàn)同步的機(jī)制稱為同步機(jī)制。如：軟件和硬件的方法；信號量機(jī)制；管程機(jī)制2.3進(jìn)程同步（3）進(jìn)程同步的基本概念兩種形式的制約關(guān)系臨界資源、臨界區(qū)同步機(jī)制應(yīng)遵循的規(guī)則信號量機(jī)制整型信號量記錄型信號量AND型信號量集、一般信號量集信號量的應(yīng)用信號量實現(xiàn)進(jìn)程互斥信號量描述進(jìn)程間的前趨關(guān)系管程機(jī)制一、進(jìn)程同步的基本概念1、進(jìn)程之間兩種形式的制約關(guān)系系統(tǒng)中各進(jìn)程之間在邏輯上存在著兩種制約關(guān)系：直接相互制約關(guān)系/相互合作關(guān)系（進(jìn)程同步）：即為完成同一個任務(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)程時間次序上受到某種限制競爭不到某一物理資源時不允許進(jìn)程工作相互清楚對方的存在及作用，交換信息不一定清楚其它進(jìn)程的情況往往指有幾個進(jìn)程共同完成一個任務(wù)往往指多個任務(wù)多個進(jìn)程間通訊制約例：生產(chǎn)與消費(fèi)之間，發(fā)送與接收之間，寫者與讀者之間例：交通十字路口，單軌火車的撥道岔2、臨界資源、臨界區(qū)（1）一次只允許一個進(jìn)程使用的共享資源稱為臨界資源，如打印機(jī)，繪圖機(jī)，變量，數(shù)據(jù)等，各進(jìn)程間采取互斥方式實現(xiàn)對這種臨界資源的共享，從而實現(xiàn)并發(fā)進(jìn)程的封閉性。例：生產(chǎn)者-消費(fèi)者問題一組生產(chǎn)者向一組消費(fèi)者提供產(chǎn)品，它們共享一個緩沖池，生產(chǎn)者向其中投放產(chǎn)品，消費(fèi)者從中取得產(chǎn)品。它是許多相互合作進(jìn)程的抽象，如輸入進(jìn)程與計算進(jìn)程；計算進(jìn)程與打印進(jìn)程等。2、臨界資源、臨界區(qū)（2）設(shè)緩沖池的長度為n（n>0），一群生產(chǎn)者進(jìn)程P1,P2,…，Pm，一群消費(fèi)者進(jìn)程C1,C2,…，Ck，如圖所示。假定生產(chǎn)者和消費(fèi)者是相互等效，只要緩沖池未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，類似地，只要緩沖池未空，消費(fèi)者便可以從緩沖區(qū)取走產(chǎn)品并消耗它。生產(chǎn)者和消費(fèi)者進(jìn)程是以異步方式運(yùn)行的，但必須保持同步關(guān)系，即禁止生產(chǎ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ū)的個數(shù)；buffer為具有n個緩沖區(qū)的緩沖池；in和out為指針，分別指向下一個可投放產(chǎn)品的緩沖區(qū)和下一個可獲取產(chǎn)品的緩沖區(qū)2、臨界資源、臨界區(qū)（4）生產(chǎn)者消費(fèi)者進(jìn)程可分別描述為：producer:repeat

……produceaniteminnextp;

……whilecounter=ndono-op;buf