【正文】 第二章 進程管理 進程的基本概念 進程控制 進程同步 經(jīng)典進程的同步問題 進程通信 線程 進程的基本概念 ? 進程的概念是操作系統(tǒng)中最基本、最重要的概念。它是在多道程序系統(tǒng)出現(xiàn)后，為了刻劃系統(tǒng)內(nèi)部出現(xiàn)的情況，描述系統(tǒng)內(nèi)部各作業(yè)的活動規(guī)律而引進的一個新的概念 ? ? 一個復(fù)雜的程序一般均含 若干個程序段 ，并按 一定先后順序執(zhí)行 ，每個操作必須在下一個操作開始之前結(jié)束。也即僅當(dāng)前一個操作結(jié)束之后，后繼操作才開始執(zhí)行，此即 程序的順序執(zhí)行性。 ? ? 例如一般程序包括輸入 (I)、計算 (C)、輸出 (P)三部分，而 計算 須在 輸入 完成后方可開始，而輸出須在計算完成后才能進行。 I1 C1 P1 I2 C2 P2 對一個程序段中的多條語句來說 ， 也有一個執(zhí)行順序問題 ， 例如對于下述三條語句的程序段 : S1： a:=x+y S2： b:=a5 S3： c:=b+1 如下圖 ， 語句 S2必須在 a被賦值后才能執(zhí)行；S3也只能在 b被賦值后才能執(zhí)行 。 S1 S2 S3 ? 順序性： 一個程序的各個部分的執(zhí)行 ，嚴格地按照某種先后次序執(zhí)行； ? 封閉性： 程序一旦開始執(zhí)行 ， 其執(zhí)行結(jié)果不受外界因素影響 。 ? 可再現(xiàn)性： 只要程序執(zhí)行時的環(huán)境和初始條件相同 ， 當(dāng)程序重復(fù)執(zhí)行時 ，將獲得相同的結(jié)果 。 ? 前趨圖： 用于描述一個程序的各部分（程序段或語句）間的執(zhí)行順序關(guān)系，或者是一個大的計算的各個子任務(wù)間的因果關(guān)系。 ? 是一個 有向無循環(huán)圖 ，每個結(jié)點用于表示一條語句、一個程序段或一個進程；結(jié)點間的有向邊表示兩個結(jié)點之間存在的 偏序或前趨關(guān)系 “ → ” 。 ? 結(jié)點間的有向邊表示兩個結(jié)點之間存在的偏序 (Partial_Order)或前趨關(guān)系(Precedence_Relation) ? ―→ ‖＝ {(Pi,Pj)|在 Pj開始前 Pi必須完成 }，如果 (Pi,Pj)∈→ ，可寫成 Pi→Pj ，Pi是 Pj的直接前趨， Pj是 Pi的直接后繼。 每個結(jié)點還具有一個重量。 P1P3P8P9P4P2P5P6P7S1S2S3( a ) 具有九個結(jié)點的前趨圖 ( b ) 具有循環(huán)的圖 ? 該前趨圖 ， 存在下面的前趨關(guān)系： P1→P 2， P1→P 3， P1→P 4， P2→P 5，P3→P 5， P4→P 6， P4→P 7， P5→P 8，P6→P 8， P7→P 9， P8→P 9； ? 或表示為： ? Ｐ ={P1,P2,P3,P4,P5,P6,P7,P8,P9} → ={(P1,P2),(P1,P3),(P1,P4), (P2,P5),(P3,P5),(P4,P6), (P4,P7),(P5,P8),(P6,P8), (P7,P9),(P8,P9)} 例：下述幾條語句的程序段畫出前趨圖 P1 → P2， P1 → P3， P1 → P4， P2 → P5， P3 → P5， P3 → P6， P4 → P6， 程序并發(fā)執(zhí)行及特征 并發(fā)環(huán)境： 在一定時間內(nèi)物理機器上有兩個或兩個以上的程序同處于開始運行但尚未結(jié)束的狀態(tài)，并且次序不是事先確定的， 就稱這幾個程序是并發(fā)執(zhí)行的。 1. 程序的并發(fā)執(zhí)行 ? 在對一批程序進行處理時 ， 可以并發(fā)執(zhí)行 。 ? 例如 ， 輸入 、 計算 、 打印三個程序?qū)σ慌鳂I(yè)進行處理時前趨關(guān)系圖如下： P1P2P3P4I1I2I3I4C1C2C3C4 Ii→C i， Ii→I i+1, Ci→P i, Ci→C i+1， Pi→P i+1 在 Pi1和 Ci以及 Ii+1之間 ， 可以并發(fā)執(zhí)行 。 1. 程序的并發(fā)執(zhí)行 ? ? S1: a∶ =x+2 ? S2: b∶ =y+4 ? S3: c∶ =a+b ? S4: d∶ =c+b 1. 程序的并發(fā)執(zhí)行 ? 假設(shè)有一個程序由 ? S0～ Sn+1個語句， ? 其中 S1～ Sn語句是并發(fā)執(zhí)行的，程序如下： ? S0。 ? cobegin ? S1。S2。S3。...。SN ? coend。 ? Sn+1。 三個并發(fā)執(zhí)行程序的謄抄 ? get程序負責(zé)從輸入序列 f中讀取字符 ? 并送到緩沖區(qū) s中 。 ? copy程序把緩沖區(qū) s中的數(shù)據(jù)復(fù)制到緩沖區(qū) t中去 。 ? put程序從緩沖區(qū) t中取出數(shù)據(jù)打印。 ? 假設(shè)有兩個緩沖區(qū) ， 每個緩沖區(qū)只存放一個字符 ， get程序負責(zé)從輸入序列 f中讀一個字符 ， 然后 ， 送到緩沖區(qū) s中 ， copy程序負責(zé)將 s中的字符復(fù)制到 t中 ， put負責(zé)從 t中提取字符打印 。 這個算法是正確的 。 輸入 f 輸出 g { If (f不為空） { Get(s,f) while (謄寫未完成） { t=s cobegin put(t,g) Get(s,f) coend } } } c p c g p c g p g 并行環(huán)境下程序間的制約關(guān)系 與時間有關(guān)的錯誤 ? 假定 f系列中有記錄 ? f=(R1,R2,...,Rn) ? g=() ? 在謄抄完成后： ? f=() ? g=(R1,R2,...,Rn) ? 算法中的： ? copy≡t=s put ≡ put(t,g) get ≡ get(s,f) 與時間有關(guān)的錯誤 ? 若程序錯寫成： ? while(謄抄未完成 ）{ ? cobegin ? copy。 ? put。 ? get。 ? coend ? } ? 初始狀態(tài)： ? f=(R1,R2,...,Rn) ? s=() t=() g=() ? 首先執(zhí)行了 get(s,f) ? f=(R1,R2,...,Rn) ? s=R1,t=(),g=() ? copy,put,get三個程序段并發(fā)執(zhí)行 ， 就有六種組合： ? copy。put。get 導(dǎo)致結(jié)果： g=(R1,R2) ? ? copy。get。put 導(dǎo)致結(jié)果： g=(R1,R2) ? ? put。copy。get 導(dǎo)致結(jié)果： g=(R1,R1) ? ? put。get。copy 導(dǎo)致結(jié)果： g=(R1,R1) ? ? get。copy。put 導(dǎo)致結(jié)果： g=(R1,R3) ? ? get。put。copy 導(dǎo)致結(jié)果： g=(R1,R1) ? ? 這就是與時間有關(guān)的錯誤 。 與時間有關(guān)的錯誤 ? 1) 間斷性 :程序在并發(fā)執(zhí)行時，由于它們 共享資源 或為完成某一項任務(wù)而合作，致使 在并發(fā)程序之間存在相互制約 的關(guān)系。 ? 2) 失去封閉性 :程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源，因而 這些資源的狀態(tài) 將由 多個程序來改變 ，致使程序的運行失去了封閉性。 ? 3) 不可再現(xiàn)性 : 程序在并發(fā)執(zhí)行時，由于失去了封閉性，也導(dǎo)致失去了可再現(xiàn)性。 ? 并發(fā)程序 A和 B，共享變量 n，程序 A做 n=n+1操作；程序 B執(zhí)行 print（ n）操作。 ? 兩種情況：（假設(shè)當(dāng)前變量 n的值為 100） ? 執(zhí)行方式 1： ? A： n=n+1； ? B： print（ n）；結(jié)果： B打印 n的值為 101。 ? 執(zhí)行方式 2： ? B： print（ n）； ? A： n=n+1； 結(jié)果： B打印 n的值為 100。 進程的特征與狀態(tài) ? 在 多道程序 環(huán)境下， 程序具有了并行、制約和動態(tài)的特征 ， 程序概念 已刻劃不清系統(tǒng)的這種并行情況， 反映不了它們的活動規(guī)律和狀態(tài)變化 。為了動態(tài)地看待操作系統(tǒng)，則以進程作為資源分配和獨立運行的基本單位， 從進程觀點來研究操作系統(tǒng) ，操作系統(tǒng)所具有的所有特征也都是基于進程而形成的。 1. 進程的特征和定義 進程 ： 是指在系統(tǒng)中能 獨立運行 并作為 資源分配的基本單位 ， 是一個活動實體 。 也可以說，進程是 程序 在 數(shù)據(jù)集合 上的 一次運行過程 ，是系統(tǒng)進行 資源分配和調(diào)度的 基本單位。 進程是一個 動態(tài)的概念， 是一個運行過程。它不同于程序，但又 依賴于程序 。對不同的數(shù)據(jù)集合，依照一定的程序運行處理的每一個過程是每個不同的進程。 ? 在系統(tǒng)中同時有多個進程存在 ， 但歸納起來有兩大類： ? 系統(tǒng)進程 ? 系統(tǒng)進程起著資源管理和控制的作用 。 ? 或者：執(zhí)行操作系統(tǒng)核心代碼的進程 。 ? 用戶進程 ? 執(zhí)行用戶程序的進程 。 ? 一般來講 ， 在管態(tài)下執(zhí)行的進程稱為系統(tǒng)進程；在目態(tài)下執(zhí)行的進程稱為用戶進程 。 進程的特征 ? 結(jié)構(gòu)特征： 為了控制和管理進程 ， 系統(tǒng)為每個進程設(shè)立一個進程控制塊－ PCB。 ? 動態(tài)性： 進程的實質(zhì)是程序的一次執(zhí)行過程 ， 進程是動態(tài)產(chǎn)生，動態(tài)消亡的，進程在其生命周期內(nèi)，在三種基本狀態(tài)之間轉(zhuǎn)換 ? 并發(fā)性： 任何進程都可以同其他進程一起向前推進 ? 獨立性： 進程是一個能獨立運行的基本單位 ， 同時也是系統(tǒng)分配資源和調(diào)度的獨立單位； ? 異步性： 由于進程間的相互制約 ， 使進程具有執(zhí)行的 間斷性 ， 即進程按各自獨立的 、 不可預(yù)知的速度向前推進 進程與程序的區(qū)別 ? 程序是 靜態(tài) 的，進程是 動態(tài) 的 。 ? 進程更能真實地描述 并發(fā) ,而程序不能 。 ? 一 個程序可對應(yīng) 多 個進程，反之亦然 。 ? 程序可作為軟件資源 長期保存 ， 進程只是一次執(zhí)行過程 ， 是 暫時 的； ? 進程是系統(tǒng) 分配調(diào)度 的獨立單位 ， 能與其他進程并發(fā)執(zhí)行 。 ? 進程是由 程序 、 數(shù)據(jù) 和 進程控制塊 組成 ? 進程具有創(chuàng)建其他進程的功能，而程序沒有 2. 進程的三種基本狀態(tài) ? 在進程運行過程中，由于系統(tǒng)中多個進程的并發(fā)運行及相互制約的結(jié)果，使得進程的狀態(tài)不斷發(fā)生變化。 進程在系統(tǒng)中的活動規(guī)律是： ? 執(zhí)行 暫停 執(zhí)行 ? 進程的三種基本狀態(tài)： ? 運行狀態(tài) ? 就緒狀態(tài) ? 阻塞狀態(tài) 2. 進程的三種基本狀態(tài) ? 1)就緒 (Ready)狀態(tài) ? 當(dāng)進程 已經(jīng)分配 到 除 CPU以外 的 所有必要的資源 后，只要能 獲得處理機 ，就可以 立即執(zhí)行 。這時的進程的狀態(tài)稱為就緒狀態(tài) ? 2)執(zhí)行狀態(tài) (Running)（運行狀態(tài)） ? 指進程 已獲得處理機 ，其程序正在執(zhí)行。在 單處理機 系統(tǒng)中， 只能有一個進程 處于執(zhí)行狀態(tài)。（在多處理機中，可能有多個進程處于執(zhí)行狀態(tài)） 2. 進程的三種基本狀態(tài) ? 3)阻塞狀態(tài) (Block) ? 進程 因發(fā)生某個事件 而 暫停執(zhí)行 時的狀態(tài)（如：請求 I/O、申請緩沖空間等），也就是說， 進程受到阻塞 ，所以稱這種暫停狀態(tài)為 阻塞狀態(tài) ，有時也稱“ 等待 ” 狀態(tài) 或 “ 睡眠 ” 狀態(tài)。 進程的狀態(tài)及其轉(zhuǎn)換 運行 就緒 等待 ? ? ? ? 2. 進程的三種基本狀態(tài) 進程 狀態(tài) 轉(zhuǎn)換條件 在進程運行過程中，由于自身進展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換： ? 就緒 運行 – 調(diào)度程序選擇一個新的進程運行 ? 運行 就緒 – 運行進程用完了時間片 – 運行進程被中斷，因為一高優(yōu)先級進程處于就緒狀態(tài) 進程狀態(tài) 轉(zhuǎn)換條件 ? 運行 阻塞 – 當(dāng)一進程必須等待時 ?OS尚未完成服務(wù) ?對一資源的訪問尚不能進行 ?初始化 I/O 且必須等待結(jié)果 ?等待某一進程提供輸入 (IPC) ? 等待 就緒 – 當(dāng)所等待的事件發(fā)生時 3. 掛起狀態(tài) ? 在某些系統(tǒng)中，為了更好地管理和調(diào)度進程及適應(yīng)系統(tǒng)的功能目標，引入了掛起狀態(tài)。 ? 1) 引入掛起狀態(tài)的原因 – (1)終端用戶的需要 – (2) 父進程請求。 – (3) 負荷調(diào)