【正文】 D是計算 1000以內所有素數并顯示最后結果程序 。 程序 B：采用堆排序算法，在屏幕的中 1/3處開設一個窗口顯示其排序過程。 解答： ? 就緒 —運行 : 不一定（系統中僅一個進程） 轉換條件：被調度程序選中 ? 運行 —就緒 : 一定（討論就緒隊列的長度） 轉換條件：時間片到時 ,或有更高優(yōu)先級 的進程出現 ? 運行 —等待 : 不一定（考慮死鎖） 轉換條件：等待某事件發(fā)生 ? 等待 —就緒 : 不一定 轉換條件：考慮就緒隊列的長度 第二章 進 程 管 理 例 1： 設有 3個排序程序 。 第二章 進 程 管 理 3) 阻塞狀態(tài) （ Wait/Block]) 正在執(zhí)行的進程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，這種暫停狀態(tài)稱為阻塞狀態(tài)（等待狀態(tài)或封鎖狀態(tài)）。 2) 執(zhí)行狀態(tài) (Running） 進程已獲得 CPU，其程序正在執(zhí)行。 第二章 進 程 管 理 2. 進程的三種基本狀態(tài) 1) 就緒狀態(tài) (Ready) 當進程已分配到 除 CPU以外的所有必要資源后，只要再獲得 CPU，便可立即執(zhí)行，進程這時的狀態(tài)稱為就緒狀態(tài)。 ? 系統進程在管態(tài)下活動 ， 而用戶進程則在用戶態(tài) （ 目態(tài) ） 下活動 。 第二章 進 程 管 理 ?系統進程與用戶進程的區(qū)別 ? 系統進程被分配一個初始的資源集合 ， 這些資源可以為它獨占 ， 也能以最高優(yōu)先權的資格使用 。 或者：執(zhí)行操作系統核心代碼的進程 。 一個程序可以作為多個進程的運行程序 ， 一個進程也可以運行多個程序 。 而程序則不是 。 進程是有生命周期的 。 進程是程序在處理機上的一次執(zhí)行的過程 ， 是動態(tài)的概念 。 教材上給出的進程的定義： 進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位。 (2) 進程是一個程序及其數據在處理機上順序執(zhí)行時所發(fā)生的 活動 。 ?不可再現性： 程序經過多次執(zhí)行后，雖然它們執(zhí)行時的環(huán)境和初始條件相同，但得到的結果卻各不相同。 N值分別為 n， n+1， 0。N:=N+1。值分別為 n， 0， 1。N:=0。N值分別為 n+1， n+1， 0。Print(N)。這樣，可能出現下述三種情況 (假定某時刻變量 N的值為 n)。 A： while(1) B:while(1) N： N+1。 對于具有下述四條語句的程序段： S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+b S1S2S3S4第二章 進 程 管 理 2． 程序并發(fā)執(zhí)行時的特征 1) 間斷性： 2) 失去封閉性： 資源狀態(tài)有多個程序改變 3) 不可再現性 例如，有兩個循環(huán)程序 A和 B，它們共享一個變量 N。 第二章 進 程 管 理 程序的并發(fā)執(zhí)行及其特征 1． 程序的并發(fā)執(zhí)行 在圖 21中存在 Ii→C i→P i前趨關系，以至對一個作業(yè)的輸入、計算和打印三個操作，必須順序執(zhí)行，但并不存在Pi→I i+1的關系，因而在對一批程序進行處理時，可使它們并發(fā)執(zhí)行。 第二章 進 程 管 理 程序的并發(fā)執(zhí)行及其特征 1． 程序的并發(fā)執(zhí)行 若干個程序段同時在系統中運行，這些程序段的執(zhí)行在時間上是 重疊 的，一個程序段的執(zhí)行尚未結束，另一個程序段的執(zhí)行已經開始，即使這種重疊是很小的一部分，也稱這幾個程序段是 并發(fā)執(zhí)行 的。 此外，每個結點還具有一個重量 (Weight)，用于表示該結點所含有的程序量或結點的執(zhí)行時間。 自反、反對稱、傳遞 第二章 進 程 管 理 → ={(Pi， Pj)|Pi must plete before Pj may start}，如果 (Pi， Pj)∈→ ，可寫成 Pi→P j，稱 Pi是 Pj的直接前趨，而稱 Pj是 Pi的直接后繼。 程序的順序執(zhí)行及其特征 第二章 進 程 管 理 前趨圖 前趨圖 (Precedence Graph)是一個有向無循環(huán)圖，記為DAG(Directed Acyclic Graph)，用于 描述進程之間執(zhí)行的前后關系。 (3) 可再現性 ： 只要程序執(zhí)行時的環(huán)境和初始條件相同 ，當程序重復執(zhí)行時 ， 都將獲得相同的結果 。 (2) 封閉性 ： 程序是在封閉的環(huán)境下執(zhí)行的 ， 即程序運行時獨占全機資源 ， 資源的狀態(tài) (除初始狀態(tài)外 )只有本程序才能改變它 。 第二章 進 程 管 理 進程的基本概念 程序的順序執(zhí)行及其特征 1. 程序的順序執(zhí)行 一個程序由若干個程序段組成，而這些程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式就稱為 程序的順序執(zhí)行 。顯然，在操作系統中，進程是一個極其重要的概念。第二章 進 程 管 理 第二章 進 程 管 理 進程的基本概念 進程控制 進程同步 經典進程的同步問題 進程通信 線程 第二章 進 程 管 理 ?教學目的： ? 掌握操作系統的順序進程和并發(fā)進程的各自特點 ? 掌握進程基本概念，進程的狀態(tài)及轉換 ? 掌握操作系統進程同步的概念 ? 掌握信號量機制 ? 了解操作系統進程同步的經典問題 ? 掌握利用信號量機制解決進程同步問題的方法 ?教學難重點： ? 進程基本概念，進程的狀態(tài)及轉換 ? 利用信號量機制解決進程同步問題的方法 第二章 進 程 管 理 新課導入 ? 在傳統的操作系統中，程序并不能獨立運行，作為資源分配和獨立運行的基本單位都是進程。操作系統所具有的四大特征也都是基于進程而形成的，并可從進程的觀點來研究操作系統。因此，在這章中我們來學習進程。例如對多個作業(yè) : I：輸入 C：計算 P：打印 第二章 進 程 管 理 S1: a:=x+y； S2: b:=a5； S3: c:=b+1； 程序的順序執(zhí)行及其特征 1. 程序的順序執(zhí)行 S1 S2 S3 例如對一個程序的多條語句 : 圖 21（ b） 程序的順序執(zhí)行 第二章 進 程 管 理 2. 程序順序執(zhí)行時的特征 (1) 順序性 ： 處理機的操作嚴格按照程序所規(guī)定的順序執(zhí)行 ， 即每一操作必須在上一個操作結束之后開始 。 程序一旦開始執(zhí)行 ， 其執(zhí)行結果不受外界因素影響 。 ?優(yōu)點：程 序的編制 、 調試方便 ， ?缺點：計算機系統效率不高 。 結點： 可用于描述一個程序段或進程，乃至一條語句； 結點間的 有向邊 ：則用于表示兩個結點之間存在的 偏序(Partial Order，亦稱 偏序關系 )或前趨關系 (Precedence Relation)“→ ”。在前趨圖中，把沒有前趨的結點稱為 初始結點 (Initial Node)，把沒有后繼的結點稱為終止結點 (Final Node)。在圖 21(a)和 21(b)中分別存在著這樣的前趨關系： Ii→ Ci→ Pi S1→ S2→ S3 和 第二章 進 程 管 理 圖 22 前趨圖 P1P3P8P9P4P2P5P6P7S1S2S3( a ) 具有九個結點的前趨圖 ( b ) 具有循環(huán)的圖第二章 進 程 管 理 對于圖 22(a)所示的前趨圖，存在下述前趨關系： 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 或表示為： P={P1， P2， P3， P4， P5， P6， P7， P8， P9} →={(P 1， P2)， (P1， P3)， (P1， P4)， (P2， P5)， (P3， P5)， (P4，P6)， (P4， P7)， (P5， P8)， (P6， P8)， (P7， P9)， (P8， P9)} 前趨圖中 必須不存在循環(huán) ，但在圖 22(b)中卻有著下述的前趨關系： S2→ S3， S3→ S2 這種前驅關系是不可能滿足的。 P Q R 例：三個并發(fā)執(zhí)行的程序段 。 i1 p1 i p o o1 i2 p2 o2 i3 p3 o3 t1 t2 t3 進程 時間 第二章 進 程 管 理 在該例中存在下述前趨關系： Ii→ Ci， Ii→ Ii+1， Ci→ Pi， Ci→ Ci+1， Pi→ Pi+1 而 Ii+1和 Ci及 Pi1是重迭 的 ， 亦即在 Pi1和 Ci以及 Ii+1之間 ，可以并發(fā)執(zhí)行 。 ? 程序 A每執(zhí)行一次時，都要做 N:=N+1操作； ? 程序 B每執(zhí)行一次時，都要執(zhí)行 Print(N)操作，然后再將 N置成 “ 0”。 { Pint(N): N:=0 } ? 程序 A和 B以不同的速度運行。 第二章 進 程 管 理 求解：已知一個求值公式 (A A＋ 3B)/(B+5A) 若 A和 B已經賦值，試畫出該公式求解的前驅圖 第二章 進 程 管 理 (1)N:=N+1。N:=0。 (2)Print(N)。N:=N+1。 (3)Print(N)。N:=0。 上述情況說明，程序在并發(fā)執(zhí)行時，由于失去了封閉性，其計算結果已與并發(fā)程序的執(zhí)行速度有關，從而使程序的執(zhí)行 失去了可再現性。 第二章 進 程 管 理 進程的特征與狀態(tài) 1. 進程的特征和定義 ? 特征： 1) 結構特征 ： PCB 2) 動態(tài)性 ：生命期 3) 并發(fā)性 ：重要特征 4) 獨立性： 5) 異步性： 間斷性 第二章 進 程 管 理 ? 進程的定義 較典型的進程定義有： (1) 進程是程序的一次 執(zhí)行 。 (3) 進程是程序在一個數據集合上運行的 過程 ，它是系統進行資源分配和調度的一個獨立單位。 第二章 進 程 管 理 What is a process? ? One program which has an independent function works on certain data set dynamically and allocate resources dynamically ? 一個具有一定獨立功能的程序對某個數據集合上的一次動態(tài)執(zhí)行過程和資源分配過程 第二章 進 程 管 理 ? 進程與程序的區(qū)別與聯系 程序是指令的集合 ， 是靜態(tài)的概念 。 程序可以作為軟件資料長期保存 。 進程是一個獨立的運行單位 ， 能與其它進程并行（ 并發(fā) ） 活動 。 進程是競爭計算機系統有限資源的基本單位 ， 也是進行處理機調度的基本單位 。 進程三要素：程序、數據、 CPU 第二章 進 程 管 理 編譯程序上的兩個進程 源程序 f C 語言編譯程序 源程序 f p2 p1 B A 第二章 進 程 管 理 ? 進程的類型 在系統中同時有多個進程存在 ， 但歸納起來有兩大類： （ 1） 系統進程 系統進程起著資源管理和控制的作用 。 （ 2） 用戶進程 執(zhí)行用戶程序的進程 。 用戶進程通過系統服務請求的手段競爭使用系統資源； ? 用戶進程不能直接做 I/O操作 ， 而系統進程可以做顯式的 、 直接的 I/O操作 。 另一種分類：計算進程 ， I/O進程等 注意：在 UNIX系統中沒有這樣對進程進行分類 。 在一個系統中處于就緒狀態(tài)的進程可能有多個，通常將它們排成一個隊列，稱為 就緒隊列。 在單處理機系統中，只有一個進程處于執(zhí)行狀態(tài)；在多處理機系統中，則有多個進程處于執(zhí)行狀態(tài)。 第二章 進 程 管 理 問題：如果系統中有 N個進程， ?運行進程最多幾個，最少幾個？ ?就緒進程最多幾個，最少幾個？ ?等待進程最多幾個，最少幾個？ 解答： 運行進程最多 1個，最少 0個； 就緒進程最多 N1個，最少