【正文】 每個程序的執(zhí)行過程均為： 首先 輸入程序和數(shù)據(jù) 然后 進行計算 最后 打印計算結果 形式化的表示為： I： 輸入操作 C： 計算操作 P： 輸出操作 ★ 118 P2 C2 I2 P1 C1 I1 即：嚴格地說，程序的順序執(zhí)行是指： 不僅 一個計算內的各個操作 是順序執(zhí)行的 而且 多個計算之間的執(zhí)行 也是順序的 不滿足上述的任何一條 就 不是 程序的順序執(zhí)行 (稱為 并發(fā)執(zhí)行 ) ★ 那么在 單道 環(huán)境下，一批作業(yè)的 所有操作 會形成一個什么樣的 執(zhí)行序列 呢？ 119 3. 順序程序的特點 (1) 順序性 處理機的操作，嚴格按程序所 規(guī)定的順序 執(zhí)行 (傳統(tǒng)的程序 都具有此特點 ) (2) 封閉性 程序的執(zhí)行，不受外界因素的影響。 為什么 ? (3) 可再現(xiàn)性 (由封閉性保證 ) 即：初始條件相同，得到的結果就相同 也稱為 與時間無關性 即：程序執(zhí)行的結果 只與初始條件有關，而與執(zhí)行的速度無關 (結果唯一 、 可預期的 ) ★ 120 1. 什么是程序的并發(fā)執(zhí)行 多個程序 (或程序段 )，同時在系統(tǒng)中運行 若它們執(zhí)行的 起始時間段有重疊 的部分 (一個的執(zhí)行尚未結束，另一個的執(zhí)行已開始 ) 則稱這幾個程序段是并發(fā)執(zhí)行的 P Q R 例：三個并發(fā)執(zhí)行的程序段 多個程序段的并發(fā)執(zhí)行，應如何來表示呢？ ★ 二、程序的 并發(fā)執(zhí)行 121 問題： 從并發(fā)的形式化描述中 ， 能看出程序的執(zhí)行次序嗎 ？ 2. 并發(fā)執(zhí)行的表示 (1) 用并發(fā)語句表示 cobegin S1； S2； ．．． Sn coend S0 并發(fā)執(zhí)行的一般性含義： 指多個程序 、 或程序段的執(zhí)行 ， 沒有任何次序的限制 S4 S2 S1 S3 (2) 用次序圖表示 探討的問題： 在一個 實際 的并發(fā)環(huán)境中 ， 多個程序段的并發(fā)執(zhí)行 是否完全沒有 次序的限制 ? 會不會帶來 意外的問題呢 ？ ★ 122 思考： 它們的并發(fā)執(zhí)行，會得到什么樣的 結果 呢？ 打印出的 n值？ n的終值？ 四、 與時間有關 的錯誤 例：兩個程序共享一個初值為 0 的公共變量 n 程序 A執(zhí)行時：完成 n 加 1 的操作 程序 B執(zhí)行時：先打印 n的值，再將 n置為 0 與時間有關的錯誤 是指： 多個程序并發(fā)執(zhí)行時，可能會有多個不同的結果。除一個結果正確外，其余的都 認為 是錯誤的。 稱其為與時間有關的錯誤。 123 程序 A的 n :=n+1 ，與 程序 B的 兩語句 之間的 執(zhí)行 次序 ： 之前 1 0 之后 0 1 中間 0 0 打印的結果 : n的終值 : 程序 A ．．． n := n+1 ．．． 程序 B ．．． print(n) n := 0 ．．． 將上述錯誤稱為與時間有關的錯誤。 什么問題？ 124 (1) 失去程序的 封閉性 和可 再現(xiàn)性 如果程序 A的執(zhí)行，可以 改變程序 B的環(huán)境 ( 即程序 B失去了封閉性 ) 五、并發(fā)程序的特點 思考： 如果程序 B本身是封閉的呢 ? ★ 則：程序 B的運行 結果 就與二個程序之間，執(zhí)行的 相對速度 有關 (即 失去了可再現(xiàn)性 ) 125 編譯 1 C編譯 程序 編譯 2 …. 編譯 n (2) 程序與計算 不再一一對應 一個程序可以對應多個計算。如： (3) 程序的并發(fā)執(zhí)行也存在著相互制約 ? 直接的 相互制約： 由程序的邏輯決定 ? 間接的 相互制約： 由共享資源而引起 歸納： 產生了新的問題 ， 有待解決 ★ 六、并發(fā)程序執(zhí)行中應解決的問題 (1) 由于失去了可再現(xiàn)性，而帶來 與時間有關的錯誤 (與 占有 CPU的 次序 有關 ) (2) 由于程序與計算不再一一對應 資源分配給誰 ? 因此，操作系統(tǒng)必須解決： (1) 如何描述每個程序，在內存的 執(zhí)行過程 ？ (何時占有 CPU、何時沒有，怎么表示 ) (2) 資源分配的對象 是什么？ 已獲得的資源記錄在何處？ ★ 127 4. 2 進程的概念 一 . 進程定義 程序并發(fā)執(zhí)行時，占有 CPU的活動規(guī)律為： 執(zhí)行 暫停 執(zhí)行 ．．． 因此必須用一個 數(shù)據(jù)結構 ，描述 程序 執(zhí)行時的 活動規(guī)律 、以及對 資源的使用情況 將其 描述的對象稱為： Processing 1. 什么是 Processing (進程 ) 所謂進程，就是一個 程序 在給定活動空間和初始環(huán)境下，在一個處理機上 的執(zhí)行過程 ★ 128 (1) 運行狀態(tài) (running) 該進程已獲得運行所必需的一切資源 它的程序 正在處理機上執(zhí)行 二 . 進程的狀態(tài)、及狀態(tài)變遷 1. 進程的基本狀態(tài) 思考： 沒有運行的進程 根據(jù)其 原因 ，能否再作進一步的區(qū)分呢 ? ★ 129 (3) 等待狀態(tài) (wait) 進程正 等待 著某一 事件的發(fā)生 即使將 CPU的控制權給它，也 無法執(zhí)行 問題： 各種狀態(tài)是如何進行轉換的呢？ ★ (2) 就緒狀態(tài) (ready) 進程已獲得除 CPU之外，運行所必需的一切資源 一旦得到 CPU的控制權 ，立即可以執(zhí)行 130 2. 進程狀態(tài)的變遷 進程的狀態(tài)，是隨著進程自身的推進和外界條件的變化，而發(fā)生變化的。 運 行 等 待 就 緒 服務請求 / 等待一個 事件的發(fā)生 服務完成 / 事件已發(fā)生 進程調度 時間片到 ★ 131 三 . 進程的描述 多個進程并發(fā)執(zhí)行時，就產生了 動態(tài)的特征 由于進程對資源的不斷占有和釋放 從而造成了一個不斷 變化的外部環(huán)境 而且，進程間還存在 相互制約 因此對 每個進程 ，必須至少用一個數(shù)據(jù)結構 對其運行的過程進行描述 ★ 132 1. 進程控制塊 描述一個進程的數(shù)據(jù)結構，稱為 進程控制塊 (Process Control Block PCB)，它描述了進程： 當前所處的 狀態(tài) 對 資源的使用情況 以及 與其他進程的關系 用途： 操作系統(tǒng)是通過 PCB 而 感知 到進程的存在 并對進程進行 控制 ★ 133 3. PCB的主要內容 進程標識符 進程當前狀態(tài) 當前隊列指針 總鏈隊列指針 程序開始地址 進程優(yōu)先級 CPU現(xiàn)場保護區(qū) 通信信息 家族聯(lián)系 占有資源清單 (1) 進程標識符： 進程符號名、或內部 id號 (2) 進程當前狀態(tài)： 本進程目前處于何種狀態(tài) (運行、就緒、等待 ) (3) 當前隊列指針 next： 同一狀態(tài)的 下一個進程的 PCB 地址 ★ 134 (4) 總鏈隊列指針 all_q_next ： 用于將系統(tǒng)中，所有的進程的連為一個整體 (5) 程序開始地址： 該進程的程序將從此地址開始執(zhí)行。 (6) 進程優(yōu)先級： 反映了進程要求 CPU的緊迫程度 (7) CPU現(xiàn)場保護區(qū) ： 當進程由于某種原因釋放處理機時， CPU現(xiàn)場信息被保存在 pcb的該區(qū)域中 ★ 135 (8) 通信信息： 進程間進行通信時，所記錄的有關信息。 (9) 家族聯(lián)系： 進程與家族的聯(lián)系，通常為 指向父進程的指針 (10) 占有資源清單 為了對系統(tǒng)中的 所有的進程 進行管理 系統(tǒng)中還需要哪些 其他的數(shù)據(jù)結構呢？ ★ 136 ready_start ? pcb1 pcb2 pcb9 就緒隊列 next wait_start pcb3 pcb7 ? next 打印機等待隊列 其他的就緒隊列 ．．．．．．．． 其他的等待隊列 ．．．．．．．． ★ 137 ? all_start pcb1 pcb2 pcbn 總鏈隊列 next running pcb4 ? next 運行指針 ★ @Unix系統(tǒng)中的進程 (映像 ) 一 . 進程控制的概念 1. 什么是進程控制 指由 一組系統(tǒng)功能調用子例程 ，對系統(tǒng)中的全部進程實施有效管理，并負責其狀態(tài)的改變 完成的功能包括進程的： 無 有 消亡 @Unix中的進程樹 ★ 4. 3 進程控制 創(chuàng)建 撤消 139 就緒 運行 運行 等待 等待 就緒 調度 喚醒 等待 由于這些 子例程 在執(zhí)行時不能被中斷 (至少在邏輯上 )，因此被稱之為 原語 ★ 140 二 . 進程創(chuàng)建 1. 進程創(chuàng)建原語的 一般形式 create (name， priority， start_addr ) 進程的創(chuàng)建，通常會涉及到 3個主要的參數(shù) ? name ：新進程的符號名 (或 進程標識符 ) ? priority：進程的優(yōu)先級 ? start_addr：程序的開始地址 ★ 2. 常用的進程控制原語 創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等 141 2. 進程創(chuàng)建原語的 一般 功能 建立新進程的 PCB結構 創(chuàng)建一個具有指定標識符的進程： (1) 從 PCB池分配一個空 PCB結構 a b 1 … PCB池 (2) 填寫 PCB的內容 (如：狀態(tài)為 就緒 、 …. ) (3) 將 PCB插入就緒隊列 調用者： 作業(yè)調度程序 、 終端進程 、 執(zhí)行程序 (父進程