1

StartReadyQueueEventQueueEventExitTimeSliceCPU2

StartReadyQueueEventQueueEventExitTimeSliceCPU3

StartReadyQueueEventQueueEventExitTimeSliceCPU4

StartReadyQueueEventQueueEventExitTimeSliceCPU5

StartReadyQueueEventQueueEventExitTimeSliceCPU6

StartReadyQueueEventQueueEventExitTimeSliceCPU7

StartReadyQueueEventQueueEventExitTimeSliceCPU8

StartReadyQueueEventQueueEventExitTimeSliceCPU9

StartReadyQueueEventQueueEventExitTimeSliceCPU10

StartReadyQueueEventQueueEventExitTimeSliceCPU11

StartReadyQueueEventQueueEventExitTimeSliceCPU12

StartReadyQueueEventQueueEventExitTimeSliceCPU13

StartReadyQueueEventQueueEventExitTimeSliceCPU14

StartReadyQueueEventQueueEventExitTimeSliceCPU進程控制塊ProcessControlBlock

進程控制塊PCB是操作系統為了管理和控制進程的運行而為每一個進程定義的一個數據結構，它記錄了系統管理進程所需的全部信息。系統根據PCB而感知進程的存在，PCB是進程存在的唯一標志。例：Linux中的PCB1、進程控制塊PCB的作用是OS對并發執行的進程進行控制和管理的根據。也是系統用來感知進程存在的根據，即PCB是進程存在的唯一標志。

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

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

內部標識符（由系統創建進程時分配給進程的唯一標識號，通常為一整數，稱為進程號，用于區分不同的進程）

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

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

即處理機中各種寄存器（通用寄存器、PC、PSW等）的內容進程調度：

記錄了進程調度的相關信息（狀態、優先級、事件等）。進程控制：

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

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

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

圖示

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

圖示

將同一狀態的進程組織在一個索引表中，索引表的表項指向相應的PCB，不同狀態對應不同的索引表。0PCB90PCB89PCB77PCB6

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

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

進程的創建進程的撤消進程的阻塞與喚醒等，這些功能一般是由操作系統的內核來完成。OS內核：

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

為了防止OS及其關鍵數據（如PCB等）不被用戶有意或無意破壞,通常將處理機的執行狀態分為兩種：處理機狀態特權(執行指令,訪問）程序系統態(核心態、管態)

用戶態（目態）補充：處理機的執行狀態較高(一切指令,所有寄存器及存儲區)OS內核較低(規定指令,指定寄存器及存儲區)用戶程序或系統外層的應用程序一、進程創建

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

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

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

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

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

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

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

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

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

block()功能：將進程由執行狀態轉變為阻塞狀態。對于處于阻塞狀態的進程，當該進程期待的事件出現時，由其它相關進程調用喚醒原語wakeup()將阻塞的進程喚醒，使其進入就緒狀態；

wakeup()功能：將進程由阻塞狀態轉變為就緒狀態。三、進程的阻塞與喚醒

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

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

態設置CPU環境）將阻塞進程移出阻塞隊列插入到就緒隊列如需要，則另調度

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

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

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

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

注：n為緩沖池中緩沖區的個數；buffer為具有n個緩沖區的緩沖池；in和out為指針，分別指向下一個可投放產品的緩沖區和下一個可獲取產品的緩沖區2、臨界資源、臨界區（4）生產者消費者進程可分別描述為：producer:repeat

……produceaniteminnextp;

……whilecounter=ndono-op;buf