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

1

StartReadyQueueEventQueueEventExitTimeSliceCPU2

StartReadyQueueEventQueueEventExitTimeSliceCPU3

StartReadyQueueEventQueueEventExitTimeSliceCPU4

StartReadyQueueEventQueueEventExitTimeSliceCPU5

StartReadyQueueEventQueueEventExitTimeSliceCPU6

StartReadyQueueEventQueueEventExitTimeSliceCPU7

StartReadyQueueEventQueueEventExitTimeSliceCPU8

StartReadyQueueEventQueueEventExitTimeSliceCPU9

StartReadyQueueEventQueueEventExitTimeSliceCPU10

StartReadyQueueEventQueueEventExitTimeSliceCPU11

StartReadyQueueEventQueueEventExitTimeSliceCPU12

StartReadyQueueEventQueueEventExitTimeSliceCPU13

StartReadyQueueEventQueueEventExitTimeSliceCPU14

StartReadyQueueEventQueueEventExitTimeSliceCPU進程控制塊ProcessControlBlock

進程控制塊PCB是操作系統(tǒng)為了管理和控制進程的運行而為每一個進程定義的一個數(shù)據(jù)結(jié)構(gòu)，它記錄了系統(tǒng)管理進程所需的全部信息。系統(tǒng)根據(jù)PCB而感知進程的存在，PCB是進程存在的唯一標志。例：Linux中的PCB1、進程控制塊PCB的作用是OS對并發(fā)執(zhí)行的進程進行控制和管理的根據(jù)。也是系統(tǒng)用來感知進程存在的根據(jù)，即PCB是進程存在的唯一標志。

2、進程控制塊PCB中的信息（1）

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

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

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

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

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

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

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

3、進程控制塊PCB的組織方式

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

圖示

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

圖示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

至PCB，再按新進程PCB中的狀

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

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

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

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

…P1P2…PmC1C2…Ck2、臨界資源、臨界區(qū)（3）生產(chǎ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)者消費者進程可分別描述為：producer:repeat

……produceaniteminnextp;

……whilecounter=ndono-op;buf