【正文】 第二章 進(jìn)程管理 2022/2/6 太湖學(xué)院信機系 2 程序的順序執(zhí)行及特征 一、程序執(zhí)行有固定的時序。（ P34,圖 21） 二、特征： ? 順序性、封閉性、可再現(xiàn)性 I1 C1 P1 I2 C2 P2 程序段的順序執(zhí)行 2022/2/6 太湖學(xué)院信機系 3 程序段中語句的順序執(zhí)行 ? S1:a:=x+y。 ? S2:b:=a5。 ? S3:c:=b+1。 S1 S2 S3 2022/2/6 太湖學(xué)院信機系 4 ? 有向 無循環(huán)圖 ? 表示方式： ? （ 1） p1 p2 ? （ 2） ={(p1,p2)| p1 必須在 p2開始前完成 }，前趨關(guān)系 （圖 22 P35） ? 節(jié)點表示：一條語句，一個程序段，一個進(jìn)程。 P1 P2 P3 P4 S1 S2 S3 2022/2/6 太湖學(xué)院信機系 5 ? 試畫出下面幾條語句的前趨圖 : S1: a=5x。 S2: b=a*x。 S3: c=4*x。 S4: d=b+c。 S5: e=d+3。 2022/2/6 太湖學(xué)院信機系 6 程序的并發(fā)執(zhí)行 一 、 多個程序的并發(fā)執(zhí)行 （ 可行性分析 ） I1 I2 I3 I4 C1 C2 C3 C4 P1 P2 P3 P4 t 思考： ① 哪些程序段的執(zhí)行必須是順序的？為什么？ ② 哪些程序段的執(zhí)行是可并行的？為什么？ 2022/2/6 太湖學(xué)院信機系 7 程序的并發(fā)執(zhí)行 (2) ? 二、特征 ? 間斷性 ? 失去封閉性：主要由共享資源引起 ? 不可再現(xiàn)性： P37例 ， 設(shè) N的初值為 n。 有 2個循環(huán)程序 A和 B，它們共享一個變量 N，程序 A每執(zhí)行一次時，都要做 N:=N+1。 B則每次要執(zhí)行 Print(N), 然后再做 N:=0. 若程序 A,B以不同的速度運行有以下三種不同的結(jié)果 : N:=N+1在 print(N)和 N:=0之前 ， 則 N值分別為 n+1,n+1,0. N:=N+1在 print(N)和 N:=0之后，則 N值分別為 n,0,1. N:=N+1在 print(N)和 N:=0之間，則 N值分別為 n,n+1,0. 2022/2/6 太湖學(xué)院信機系 8 1. 進(jìn)程的特征和定義 一、定義： ? 1978年，全國操作系統(tǒng)會議：進(jìn)程是一個具有一定獨立功能的程序（關(guān)于某個數(shù)據(jù)集合的一次運行活動）對某個數(shù)據(jù)集在處理機上的執(zhí)行過程和分配資源的基本單位。 ? 進(jìn)程 是進(jìn)程實體的運行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。（ P38） ? 系統(tǒng)中能獨立運行并作為資源分配和調(diào)度的基本單位。(P15) *程序是指一組操作序列 *數(shù)據(jù)集則是指接受程序規(guī)定操作的一組存儲單元的內(nèi)容 2022/2/6 太湖學(xué)院信機系 9 (2) 二、特征 : ? 進(jìn)程：由程序段、數(shù)據(jù)段及 進(jìn)程控制塊 三部分構(gòu)成，總稱 “ 進(jìn)程映像 ” 。 ? 由 “ 創(chuàng)建 ” 而產(chǎn)生，由 “ 調(diào)度 ” 而執(zhí)行；由得不到資源而 阻塞（或等待） ；由撤消而消亡。（而程序是靜態(tài)的）。 ? 只有建立了進(jìn)程，才能并發(fā)執(zhí)行。 ? 獨立運行，獨立獲得資源 ,獨立接受調(diào)度 （斷斷續(xù)續(xù)向前推進(jìn)） 2022/2/6 太湖學(xué)院信機系 10 進(jìn)程與程序的區(qū)別 進(jìn)程 程序 動態(tài) 靜態(tài) 暫時 永久 并發(fā) 串行 PCB 多個 一個 一個 多個 2022/2/6 太湖學(xué)院信機系 11 例題： 設(shè)有 2個程序，程序 P打印工資報表的程序，程序 C是計算 1000以內(nèi)所有素數(shù)并顯示最后結(jié)果的程序。 （ 1）在不支持進(jìn)程運行環(huán)境的操作系統(tǒng)下運行。 （ 2）在支持進(jìn)程運行的操作系統(tǒng)環(huán)境下運行。 運行過程如下： ①在不支持進(jìn)程運行的環(huán)境下： 依次運行程序 P、程序 C?？梢钥吹较仁谴蛴C不停地打印工資報表，打完后，接著運行程序 C，不停地計算，最后顯示計算結(jié)果。 ②在支持進(jìn)程運行的環(huán)境下： 創(chuàng)建進(jìn)程 P和 C，由于兩個進(jìn)程分別是 I/O量較大和計算量較大的進(jìn)程，故在系統(tǒng)進(jìn)程調(diào)度的控制下，兩個進(jìn)程并發(fā)執(zhí)行?？梢钥吹酱蛴C不斷地打印工資報表，而處理機不停地計算，最后屏幕顯示計算的結(jié)果。 2022/2/6 太湖學(xué)院信機系 12 (3) 為了描述和控制進(jìn)程的運行，系統(tǒng)為每一個進(jìn)程定義了一個數(shù)據(jù)結(jié)構(gòu)，即進(jìn)程控制塊 PCB（ Process Control Block） ,系統(tǒng)根據(jù) PCB，感知該進(jìn)程的存在，故稱 PCB是進(jìn)程存在的標(biāo)志。 通常在一個實際系統(tǒng)中， PCB的總數(shù)時固定的，該數(shù)目規(guī)定了系統(tǒng)所允許擁有的進(jìn)程數(shù)目，同時將所有的 PCB形成一個結(jié)構(gòu)數(shù)組（或稱 PCB表），存放在系統(tǒng)的數(shù)據(jù)區(qū)里。 一個進(jìn)程的 PCB機構(gòu)全部或部分常駐內(nèi)存。 進(jìn)程的靜態(tài)描述由三部分組成： PCB，有關(guān)程序段，數(shù)據(jù)集。 2022/2/6 太湖學(xué)院信機系 13 (3) 2. 進(jìn)程的三種基本狀態(tài) 就緒狀態(tài)、執(zhí)行狀態(tài)、阻塞（等待）狀態(tài) ? 就緒態(tài)：等待系統(tǒng)分配處理機以便運行。即獲得了處理機以外的所有資源，一旦由調(diào)度選中得到處理機可以立即執(zhí)行的狀態(tài)。 ? 運行態(tài)：占有處理機正在執(zhí)行。在單處理機的情況下，該狀態(tài)的進(jìn)程只有一個。 ? 等待態(tài)：等待某個事件的完成。進(jìn)程因等待某事件而放棄處理機進(jìn)入等待該事件的狀態(tài)。 2022/2/6 太湖學(xué)院信機系 14 就緒 阻塞 運行 時間片完 (剝奪處理機 ) 進(jìn)程調(diào)度 發(fā)生等待事件 等待事件結(jié)束 圖 2－ 5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 創(chuàng)建 2022/2/6 太湖學(xué)院信機系 15 2 1 4 3 執(zhí)行態(tài) 就緒態(tài) 等待態(tài) 某系統(tǒng)的進(jìn)程狀態(tài)轉(zhuǎn)換圖如上圖所示，請回答： （ 1）引起各種狀態(tài)轉(zhuǎn)換的典型事件有哪些？ （ 2）當(dāng)我們觀察系統(tǒng)中某些進(jìn)程時，能夠看到某一進(jìn)程產(chǎn)生的一次狀態(tài)轉(zhuǎn)換能引起另一個進(jìn)程作一次狀態(tài)轉(zhuǎn)換。在什么情況下，當(dāng)一個進(jìn)程發(fā)生轉(zhuǎn)換 3時，能立即引起另一進(jìn)程發(fā)生轉(zhuǎn)換 1？試說明是否會發(fā)生這些因果轉(zhuǎn)換： 2→1 ； 3→2 ； 4→1 。 2022/2/6 太湖學(xué)院信機系 16 (4) 3. 掛起狀態(tài) （ 被換出內(nèi)存的狀態(tài) ， 它所要解決的問題就是某些進(jìn)程不參與資源競爭 ， 掛起就是靜止 ） ? 引入原因： ? 終端用戶請求 ? 父進(jìn)程請求（考察、修改、 協(xié)調(diào)子進(jìn)程） ? 負(fù)荷調(diào)節(jié)需要（符合過重，把暫時不要的進(jìn)程掛起） ? 操作系統(tǒng)需要（檢查資源使用情況） ? 進(jìn)程狀態(tài)的轉(zhuǎn)換 ? 活動就緒 ? 靜止就緒 ? 活動阻塞 ? 靜止阻塞 ? 靜止就緒 ? 活動就緒 ? 靜止阻塞 ? 活動阻塞 2022/2/6 太湖學(xué)院信機系 17 圖 2－ 6 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 運行 活動 就緒 靜止 就緒 活動 阻塞 靜止 阻塞 激活 掛起 激活 掛起 喚醒 喚醒 掛起 請求 I/O 2022/2/6 太湖學(xué)院信機系 18 ? 是進(jìn)程存在的唯一標(biāo)志； ? 記錄進(jìn)程的信息 PCB (process control block)常駐內(nèi)存 ? 標(biāo)識（描述信息）、處理機狀態(tài)（ CPU現(xiàn)場保護(hù)）、進(jìn)程調(diào)度信息、進(jìn)程控制信息 進(jìn)程標(biāo)識符 進(jìn)程狀態(tài) 現(xiàn)場 優(yōu)先級 阻塞原因 程序地址 同步機制 資源清單 家族關(guān)系 鏈接指針 2022/2/6 太湖學(xué)院信機系 19 ⑴ 描述信息（標(biāo)識） ? 進(jìn)程名或進(jìn)程標(biāo)識符 ? 用戶名或用戶標(biāo)識符（指示擁有該進(jìn)程的用戶） ? 家族關(guān)系（父進(jìn)程和子進(jìn)程的標(biāo)識符） ⑵調(diào)度信息 ? 進(jìn)程的當(dāng)前狀態(tài) ? 優(yōu)先級 ? 調(diào)度所需的其他信息 ? 事件（執(zhí)行 等待） 2022/2/6 太湖學(xué)院信機系 20 ⑶ 控制信息 ? 程序和數(shù)據(jù)的地址 ? 進(jìn)程同步和通信機制 ? 資源清單 ? 鏈接指針（同一隊列的下一個 PCB的首地址） ⑷處理機狀態(tài)（ CPU現(xiàn)場保護(hù)） ? 通用 R ? PC指令計數(shù)器 ? 程序狀態(tài)字 PSW ? 用戶棧指針 2022/2/6 太湖學(xué)院信機系 21 CPU現(xiàn)場保護(hù)信息（進(jìn)程上下文） 當(dāng)處理機被中斷時，各種 Register的內(nèi)容都必須保存在被中斷進(jìn)程的 PCB中，以便在改進(jìn)程重新執(zhí)行時，能從斷點繼續(xù)執(zhí)行。 (1)通用 R（用戶可視寄存器） 832個 (在 RISC結(jié)構(gòu)中，可超過 100） (2)PC（ next） (3)PSW：含狀態(tài)信息（條件碼的執(zhí)行方式，中斷屏蔽標(biāo)志） (4)用戶棧指針：每個用戶進(jìn)程有一個或若干個與之相關(guān)的系統(tǒng)棧，用戶存放過程和系統(tǒng)調(diào)用參數(shù)和調(diào)用地址。 由于 PCB中包含較多的信息（占幾百 幾千 Byte），在有的系統(tǒng)中只含最常用部分（標(biāo)識、進(jìn)程狀態(tài)信息、用于調(diào)度的信息）常駐內(nèi)存，其它部分則存在于外存之中，待該進(jìn)程將要執(zhí)行時，與其它數(shù)據(jù)一起裝入內(nèi)存。 2022/2/6 太湖學(xué)院信機系 22 進(jìn)程上下文 進(jìn)程上下文實際上是進(jìn)程執(zhí)行活動全過程的 靜態(tài)描述 。進(jìn)程的上下文是其相應(yīng)的程序地址空間的內(nèi)容，硬件 R的內(nèi)容以及與該進(jìn)程有關(guān)的核心數(shù)據(jù)結(jié)構(gòu)組成的。 具體包括：計算機系統(tǒng)中與該進(jìn)程有關(guān)的各種 R值，程序段經(jīng)過編譯，連接后形成的機器指令代碼段（ text）數(shù)據(jù)段及各種堆棧的值和 PCB塊。 2022/2/6 太湖學(xué)院信機系 23 在一個系統(tǒng)中，通常可擁有數(shù)十個、數(shù)百個，乃至數(shù)千個 PCB：為能對它們進(jìn)行有效的管理，應(yīng)當(dāng)用適當(dāng)?shù)姆绞綄⑺鼈兘M織起來。 ? 目前常用的組織方式有兩種： 鏈接方式，索引方式 。 ? 系統(tǒng)中進(jìn)程隊列分類：就緒隊列、等待隊列、運行隊列。 就緒隊列：整個系統(tǒng)一個。 等待隊列：每個等待事件一個。 運行隊列：單機系統(tǒng)中整個系統(tǒng)一個。 2022/2/6 太湖學(xué)院信機系 24 (2) ? 鏈接方式 把具有相同狀態(tài)的 PCB，用其中的鏈接字，鏈接成一個隊列。 執(zhí)行指針 就緒隊列指針 阻塞隊列指針 空閑隊列指針 PCB1 4 PCB2 3 PCB3 0 PCB4 8 PCB5 PCB6 7 PCB7 9 PCB8 0 PCB9 11 多個 2022/2/6 太湖學(xué)院信機系 25 (3) ? 索引方式 系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)，建立幾張索引表，例如，就緒索引表，阻塞索引表等，并把各索引表在內(nèi)存的 首地址 記錄于內(nèi)存中的一些 專用庫文件 中，在內(nèi)存索引表的表目中，記錄具有相應(yīng)狀態(tài)的 PCB在 PCB表中的地址。 2022/2/6 太湖學(xué)院信機系 26 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 執(zhí)行指針 就緒表指針 阻塞表指針 就緒索引表 阻塞索引表 202