【正文】 執(zhí)行 輸入： 計算： 輸出： t0 t1 t2 t3 t4 t5 t6 Δ t t I1 圖 三個程序并發(fā)執(zhí)行的前驅(qū)圖 I2 I3 C1 C2 C3 P1 P2 P3 時間 :5個 Δt 并行 并行 并行 下一步 下一步下一步前驅(qū)關系 執(zhí)行順序 174。 NOTE BOOK Operating System 第 3 章 15 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ?多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化 如前圖 多道的執(zhí)行環(huán)境具有如下 3 個特點： ?獨立性 ——每道程序都是邏輯上獨立的 ?隨機性 ——多道程序下，特別多用戶環(huán)境下，程序和數(shù)據(jù)輸入與執(zhí)行開始時間都是隨機的 ?資源共享 —— 導致程序執(zhí)行速度受制約（ 3點） ? 外設有限將導致這些設備被共享 ? 內(nèi)存有限將導致內(nèi)存被共享等 ? CPU有限將導致輪流占用 對單 CPU系統(tǒng)更是如此 174。 NOTE BOOK Operating System 第 3 章 13 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 考慮時間上關系，可有下面圖 （為簡單，假定任意的 Ii、 Ci、 Pi 都為一個 Δt 時間） t 輸入： 計算： 輸出： I1 C1 P1 I2 C2 P2 I3 C3 P3 t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 圖 三個程序間順序執(zhí)行 Δ t 程序 1： I1 C1 P1 程序 2： 程序 3： I2 C2 P2 I3 C3 P3 9個 Δt 下一步 174。其執(zhí)行過程可以描述為： 顯然， 程序的順序性與硬件順序性是一致的 Repeat： IR ← M[pc] pc ← pc+1 執(zhí)行 IR 中指令 Until CPU halt 174。 NOTE BOOK Operating System 第 3 章 10 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ?前驅(qū)圖的定義（ Procedence Graph） 反映和研究系統(tǒng)內(nèi)所發(fā)生事件之間的一種關系 → ＝ { (pi， pj) | pi必須在 pj開始之前完成 } 圖 存在下面一些前驅(qū)關系： P1 → P2 ， P1 → P3 ， ┅ ， P4 → P6 ， P6 → P7 1 2 3 4 7 5 6 圖 具有 7個結點的前驅(qū)圖 174。 NOTE BOOK Operating System 第 3 章 8 2022年 4月 17日星期日 進程的概念 3點問題： ?如何協(xié)調(diào)各程序并發(fā)運行、資源共享 ?如何刻畫可以運行的系統(tǒng)環(huán)境，需要一種機制 ?如圖 A,…,D，怎樣體現(xiàn) “走走停?！? 活動 ，這需要反映程序一種動態(tài)性 *要動態(tài) 的反映兩個基本問題： ? 程序的執(zhí)行，包括可以運行的、等待的 ? 確定資源分配的基本單位 (整體 / 獨立模塊 ) 這兩個基本點充分刻畫操作系統(tǒng) 并發(fā)、資源共享及異步等 特點，而反映 這些概念的機制就是進程 174。 問題是內(nèi)存程序數(shù)量是否越多越好呢？ (3點 否定 ) ? 內(nèi)存的容量限制了系統(tǒng)可同時處理程序的數(shù)目 ? 設備數(shù)量有限也是一個制約條件；多個程序競爭 ? 程序道數(shù)過多處理機競爭更激烈，兩個不利后果： ?影響系統(tǒng)的響應速度 ?產(chǎn)生過多系統(tǒng)開銷（系統(tǒng)本身時空耗費） *結論： 多道帶來了 系統(tǒng)資源競爭。顯然不僅使內(nèi)存充分利用，還帶來處理機利用率的提高，使整個系統(tǒng)效率得以提高 下一步下一步174。見圖 吞吐率 = 作業(yè)道數(shù) 全部處理時間 174。 NOTE BOOK Operating System 第 3 章 4 2022年 4月 17日星期日 Why Process is Described ？ ? On a multiprogramming uniprocessor, the execution of multiple processes can be interleaved in time. ? On a multiprocessor, not only may process execution be interleaved, but also multiple processes can execute simultaneously. ? Both interleaved and simultaneous execution are types of concurrency and lead to a host of difficult problems, both for the application programmer and the operating system. ? 174。 NOTE BOOK Operating System 第 3 章 2 2022年 4月 17日星期日 第 3章 進程 /CPU管理 多道程序設計 進程的概念 進程控制塊和狀態(tài)轉(zhuǎn)換 進程控制 線程 Linux 進程管理 有關進程和線程的研究 174。? 169。TSINGHUA UNIVERSITY PRESS 169。? 169。 第 3章 進程 /CPU管理 Process Management 174。 NOTE BOOK Operating System 第 3 章 3 2022年 4月 17日星期日 Why process is described ？ ? The fundamental task of any modern operating system is process management. The operating system must allocate resources to processes, enable processes to share and exchange information, protect the resources of each process from other processes, and enable synchronization among processes. ? To meet these requirements, the operating system must maintain a data structure for each process that describes the state and resource ownership of that process and that enables the operating system to exert process control. ? 174。 NOTE BOOK Operating System 第 3 章 5 2022年 4月 17日星期日 多道程序設計 ?衡量一個系統(tǒng)效率的一個指標就是吞吐率 ；即 系統(tǒng)效率與系統(tǒng)資源利用率密切相關，主要涉及： 處理機、存儲器、設備 這樣一些硬件資源的利用率問題。 NOTE BOOK Operating System 第 3 章 6 2022年 4月 17日星期日 多道程序設計 t A A Δ t 等待 I/O的時間（ 6個 Δ t） （ a） 單道情況 11 0 7 8 B B t A A Δ t （ b） 兩道情況 11 0 7 1 8 9 t Δ t （ c） 四道情況 11 0 7 1 8 9 B B A A C D C D 2 3 10 圖 單道 、 兩道和四道情況 1 4 2 1/8Δt = /Δt 2/9Δt = /Δt AI/O AI/O BI/O 4/11Δt = /Δt 下一步 A,B,C,D為程序，忽略外設；假定 4個程序都需運行 2個Δ t時間，在期間有 6個 Δ t時間的 I/O操作； 吞吐率分別為： 1/8 = 2/9 = 4/11 = 4道程序情況比單道提高了近 3 倍。 NOTE BOOK Operating System 第 3 章 7 2022年 4月 17日星期日 多道程序設計 *討論： 由圖 內(nèi)存和處理機利用率得到顯著提高。 需要解決處理機、存儲器及設備資源管理等問題 利用什么理論和機制？ 174。 NOTE BOOK Operating System 第 3 章 9 2022年 4月 17日星期日 進程的概念 前驅(qū)圖和程序執(zhí)行 進程的描述 174。 NOTE BOOK Operating System 第 3 章 11 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ? 程序的順序執(zhí)行 程序是指令（或語句）的集合，指令之間是順序關系，是一個靜態(tài)的概念。 NOTE BOOK Operating System 第 3 章 12 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 假定用 I、 C和 P分別表示輸入、計算和輸出操作（也可以為語句），可以有圖 的前驅(qū)圖 I1 C1 P1 I2 C2 P2 （ a） 兩個程序的前驅(qū)圖 （ 單道情況 ） 圖 程序的前驅(qū)圖 S1 S3 S2 （ b） 三個語句表示的前驅(qū)圖 S1： a=10； S2： b=a+8； S3： Print (b)； 174。 NOTE BOOK Operating System 第 3 章 14 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ? 程序的順序執(zhí)行 程序順序執(zhí)行具有如下 3 個特點： ?順序性 ——嚴格按程序規(guī)定的狀態(tài)轉(zhuǎn)移 ?封閉性 ——最終結果由給定的初始條件決定， 不受外界因素的影響 ?可再現(xiàn)性 ——只要初始條件相同，無論何時重復執(zhí)行該程序都會得到相同的結果 檢測查找錯誤很方便 174。 NOTE BOOK Operating System 第 3 章 16 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 注意 2點： ?對任意程序，存在著 I→C→P 這樣的前驅(qū)關系，這三個操作必須順序執(zhí)行 ?但在多道環(huán)境下，并不存在，或不要求 Pi→I i+1 關系，即 Ii、 Cj 和 Pk（ i≠j≠k）之間并不存在前驅(qū)關系，因而在對一批程序處理時，可使它們 并發(fā)執(zhí)行 ，即產(chǎn)生了并發(fā)操作，見圖 所示 174。 NOTE BOOK Operating System 第 3 章 18 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ?多道系統(tǒng)中程序執(zhí)行的變化（ 3個方面） ?程序內(nèi)保持 Ii→C i→P i邏輯順序性 ?存在 Ii→I i+1； Ci→C i+1。 ?系統(tǒng)資源競爭 Ii+ Ci+1 和 Pi沒有前驅(qū)關系，可以 并發(fā) 執(zhí)行 I1 I2 I3 C1 C2 C3 P1 P2 P3 提高 (95)/9x100% = 44% 174。關于程序并行性挖掘?qū)儆诓⑿醒芯空n題 S0 S2 S1 圖 四條語句的前驅(qū)圖 S0： x = a+10； S1： y = b a； S2： z = x+y10； S3： print（ z）； （ b） （ a） S3 174。程序的并發(fā)執(zhí)行可分為兩種： ?多道程序并發(fā)執(zhí)行在 宏觀上是同時 進行的，但在微觀上仍是順序 執(zhí)行的 ?并發(fā)執(zhí)行在某道程序幾個程序段中，包含著一部分可以同時執(zhí)行或順序顛倒執(zhí)行的代碼 174。如圖 所示 A B C t t0 t1 t2 t3 t4 t5 圖 三個程序 （ 段 ） 在執(zhí)行時間上的重疊 A B A C B C 174。 NO