1、1第二章 進程(jnchng)管理重點理解進程的概念、狀態變化理解和掌握(zhngw)同步的概念及經典進程同步問題 ，是本課程的重點之一難點會寫進程同步問題的算法知識點進程、線程、進程的特征、PCB、進程控制、進程狀態轉換、 進程同步、進程通信7/19/2022共七十三頁第二章 進程(jnchng)管理進程的基本概念 進程控制(kngzh) 進程同步 經典進程的同步問題 管程機制 進程通信 線程 7/19/2022共七十三頁進程(jnchng)的基本概念程序的順序執行及其特征前趨圖程序的并發(bngf)執行及其特征進程的特征與狀態進程控制塊7/19/2022共七十三頁程序(chngx)的順序執

2、行及其特征兩種方式順序執行：是單道批處理系統的執行方式，也用于簡單的單片機系統并發執行：現在的操作系統，具有許多新的特征。引入并發執行的目的是為了提高資源利用率順序執行的特征順序性：按照程序結構所指定的次序（可能(knng)有分支或循環）封閉性：獨占全部資源，計算機的狀態只由于該程序的控制邏輯所決定可再現性：初始條件相同則結果相同。如：可通過空指令控制時間關系7/19/2022共七十三頁程序的順序(shnx)執行及其特征僅當前一操作(程序段)執行完后，才能執行后繼操作。例如(lr)，在進行計算時，總須先輸入用戶的程序和數據，然后進行計算，最后才能打印計算結果。語句s1,s2,s3必須按順序執行

3、 S1: a=x+y; S2: b=a-5; S3: c=b+1;7/19/2022共七十三頁程序的順序(shnx)執行及其特征 IiCiPi和S1S2S3程序的順序(shnx)執行 (a) 程序的順序執行I1C1P1I2C2P2(b) 三條語句的順序執行S1S2S37/19/2022共七十三頁進程(jnchng)的基本概念程序(chngx)的順序執行及其特征前趨圖程序的并發執行及其特征進程的特征與狀態進程控制塊7/19/2022共七十三頁前趨圖前趨圖(Precedence Graph)是一個有向無循環圖，記為DAG(Directed Acyclic Graph)，用于描述進程之間執行的前后關

4、系。圖中的每個結點可用于描述一個程序段或進程，乃至一條語句；結點間的有向邊則用于表示兩個(lin )結點之間存在的偏序(Partial Order)或前趨關系(Precedence Relation)“” =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結點稱為初始結點(Initial Node)，把沒有后繼的結點稱為終止結點(Final Node)7/19/2022共七十三頁前趨圖每個結點還具有一個重量(Weight, 權值)，用于表

5、示(biosh)該結點所含有的程序量或結點的執行時間P1P3P8P9P4P2P5P6P7(a) 具有九個結點的前趨圖S1S2S3(b) 具有循環的前趨圖7/19/2022共七十三頁前趨圖對于圖(a)所示的前趨圖， 存在下述前趨關系P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示為： P=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

6、), (P6, P8), (P7, P9), (P8, P9) 應當注意(zh y)，前趨圖中必須不存在循環，但在圖(b)中卻有著下述的前趨關系：S2S3, S3S2 7/19/2022共七十三頁進程(jnchng)的基本概念程序的順序執行及其特征前趨圖程序的并發執行及其特征進程的特征與狀態(zhungti)進程控制塊7/19/2022共七十三頁程序(chngx)的并發執行及其特征并發(bngf)執行時的前趨圖7/19/2022共七十三頁程序的并發(bngf)執行及其特征在該例中存在下述前趨關系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是時間

7、上重迭的，亦即在Pi-1和Ci以及Ii+1，可以并發(bngf)執行。7/19/2022共七十三頁程序的并發(bngf)執行及其特征對于具有(jyu)下述四條語句的程序段 S1: a=x+2 S2: b=y+4 S3: c=a+b S4: d=c+b S1S2S3S47/19/2022共七十三頁程序的并發執行(zhxng)及其特征例如有兩個循環程序A和B，它們共享一個變量(binling)N程序A和B以不同的速度運行(失去封閉性，導致不可再現性）N=N+1在Print(N)和N=0之前，此時得到的N值分別為n+1, n+1, 0 N=N+1在Print(N)和N=0之后，此時得到的N值分別為n

8、, 0, 1N=N+1在Print(N)和N=0之間，此時得到的N值分別為n, n+1, 0程序A：N=N+1; 程序B： Print(N); N=0 ; 7/19/2022共七十三頁程序的并發(bngf)執行及其特征N：n程序(chngx)A：N=N+1; /N = n+1程序B： Print(N); /N=n+1 N=0 ; /N=0程序切換N：n程序B：Print(N); /N=n N=0 ; /N=0程序A：N=N+1; /N = 1程序切換N：n程序B： Print(N); /N=n程序切換程序A：N=N+1; /N = n+1程序切換程序B：N=0; /N = 0注意：A、B程序得

9、到的共享變量結果不同，失去封閉性、不可再現性；要得到良好的控制，系統必須要進行管理進程控制管理7/19/2022共七十三頁程序(chngx)的并發執行及其特征并發執行的特征間斷(異步)性走走停停，一個程序可能(knng)走到中途停下來，失去原有的時序關系；失去封閉性共享資源，受其他程序的控制邏輯的影響。如：一個程序寫到存儲器中的數據可能被另一個程序修改，失去原有的不變特征。失去可再現性失去封閉性 失去可再現性；外界環境在程序的兩次執行期間發生變化，失去原有的可重復特征7/19/2022共七十三頁程序(chngx)的并發執行及其特征并發執行失去封閉性的原因是共享資源的影響，去掉這種影響就行了。1

10、966年，由Bernstein給出并發執行的條件。（這里沒有考慮執行速度的影響。）程序 P(i) 針對共享變量的讀集和寫集 R(i)和W(i)條件：任意兩個程序P(i)和P(j)，有：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;前兩條保證一個程序的兩次讀之間數據不變化；最后一條(y tio)保證寫的結果不丟掉現在的問題是這個條件不好檢查7/19/2022共七十三頁程序并發執行的條件(tiojin)（1966年由Bernstein提出）若兩個程序P1和P2滿足下述條件，便能并發執行且有可再現性：R(P1)W(P2)R(P2)W(P1)W(P1)W(P2) = “讀集” R ( P

11、i ) 為程序 Pi 在執行期間所需參考的所有變量的集合(jh)?！皩懠?W ( Pi )為程序 Pi 在執行期間所需改變的所有變量的集合。例如：S1: a := x + y S2: b := z + 1S3: c := a - bS4: d := c + 17/19/2022共七十三頁程序并發(bngf)執行的條件（1966年由Bernstein提出）S1: a := x + yR(S1)=W(S1)=S2: b := z + 1R(S2)=W(S2)=S3: c := a - bR(S3)=W(S3)=S4: d := c + 1R(S4)=W(S4)=語句(yj)S1、S2_并發，因為

12、_。語句S1、S3_并發，因為_。語句S2、S3_并發，因為_。語句S3、S4_并發，因為_。語句S2、S4_并發，因為_。x, yazba, bccd可以R(P1)W(P2)R(P2)W(P1)W(P1)W(P2) = 不能R(S3)W(S1)=a 不能不能可以R(S3)W(S2)=b R(S4)W(S3)=c 7/19/2022共七十三頁進程(jnchng)的基本概念程序的順序執行及其特征前趨圖程序的并發執行及其特征進程概念進程的特征與狀態(zhungti)進程控制塊7/19/2022共七十三頁進程(jnchng)概念何謂進程（Process）如何理解進程概念(ginin)？進程與程序有何

13、差別？描述性定義：計算機中的所有程序（軟件），按照某種順序運行，這種運行的過程稱之為進程。7/19/2022共七十三頁進程(jnchng)概念閱讀(yud)菜譜準備原料烹制菜肴飯菜閱讀洗衣機手冊準備衣服、洗衣粉設定參數，洗衣服干凈衣服程序輸入運行輸出程序輸入運行輸出分時切換洗衣進程做飯進程7/19/2022共七十三頁進程(jnchng)概念進程(jnchng)的核心思想進程是某種類型的一個活動，它有程序、輸入、輸出和狀態。在分時操作系統中，單個CPU被若干進程共享，它使用某種調度算法決定何時停止一個進程的運行，轉而為其他進程提供服務。7/19/2022共七十三頁進程(jnchng)概念較典型的

14、進程定義有：進程是程序的一次執行進程是一個程序及其數據在處理機上順序執行時所發生的活動進程是程序在一個數據集合上運行的過程，它是系統(xtng)進行資源分配和調度的一個獨立單位7/19/2022共七十三頁進程(jnchng)的基本概念程序的順序(shnx)執行及其特征前趨圖程序的并發執行及其特征進程概念進程的特征與狀態進程控制塊7/19/2022共七十三頁進程的特征(tzhng)與狀態動態性：進程具有動態的地址空間（數量和內容），地址空間上包括(boku)：代碼（指令執行和CPU狀態的改變）數據（變量的生成和賦值）系統控制信息（進程控制塊的建立和系統收回）獨立性：各進程的地址空間相互獨立，除非

15、采用進程間通信手段；并發性：多個進程實體同存于內存中，且能在一段時間內同時運行；引入進程實體的目的就是并發執行異步性：各進程按各自獨立的、不可預知的速度向前推進結構性：程序段、數據段和PCB；程序文件中通常也劃分了代碼段和數據段，進程的創建與撤消就是PCB的創建與撤消7/19/2022共七十三頁2.1.4 進程(jnchng)的特征與狀態 1. 進程(jnchng)的特征和定義 通常的程序是不能并發執行的。應為之配置進程控制塊，即PCB；而由程序段、相關的數據段和PCB三部分便構成了進程實體。在許多情況下所說的進程，實際上是指進程實體。所謂創建進程，實質上是創建進程實體中的PCB；而撤銷進程，

16、實質上是撤銷進程的PCB。 7/19/2022共七十三頁進程(jnchng)概念較典型的進程定義有：進程是程序的一次執行進程是一個程序及其數據在處理機上順序執行時所發生的活動進程是程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的一個獨立(dl)單位在引入了進程實體的概念后，我們可以把傳統OS中的進程定義為：“進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位”7/19/2022共七十三頁進程(jnchng)與程序的區別進程是動態的，程序是靜態的：程序是有序代碼的集合；進程是程序的執行。通常進程不可在計算機之間遷移；而程序通常對應著文件、靜態和可以復制進程是暫時的，程序是永久(yngji)的：進程是一個狀態變化的過程，程序可長久保存進程與程序的組成不同：進程的組成包括程序、數據和進程控制塊（即進程狀態信息）進程與程序的對應關系：通過多次執行，一個程序可對應多個進程；通過調用關系，一個進程可包括多個程序7/19/2022共七十三頁進程的特征與狀態進程的三種(sn zhn)基本狀態就緒(Ready)狀態 可運行，已獲得除CPU外的所需資源，等待分配CPU一個系統中多個處于就緒狀態的進程(jnchng)排成就緒隊列執行(Running)狀態 占用CPU運行；處于此狀態的進程的