1、2022-4-71操作系統操作系統2022-4-72內容概述內容概述2.1 2.1 進程的基本概念進程的基本概念 2.2 2.2 進程控制進程控制 2.3 2.3 進程同步進程同步 2.4 2.4 經典進程的同步問題經典進程的同步問題 2.5 2.5 管程機制管程機制 2.6 2.6 進程通信進程通信 2.7 2.7 線程線程 進程管理的進程管理的主要功能主要功能是把處理機分配給進程是把處理機分配給進程,并對處理器運并對處理器運行進行有效地控制和管理行進行有效地控制和管理,以及協調各個進程之間的相互關系。以及協調各個進程之間的相互關系。2022-4-732.1.1 2.1.1 程序的順序執行及

2、其特征程序的順序執行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發執行及其特征程序的并發執行及其特征2.1.4 2.1.4 進程的特征與狀態進程的特征與狀態2.1.5 2.1.5 進程控制塊進程控制塊2022-4-742.1.2 2.1.2 前趨圖前趨圖(Precedence Graph) (Precedence Graph) 前趨圖前趨圖是一個有向是一個有向無循環無循環圖圖,記為記為DAG(Directed Acyclic Graph),用于描述進程之間執行的前后關系用于描述進程之間執行的前后關系。圖中的每個。圖中的每個結點結點可用于描可用于描述一個述一個程序

3、段程序段或或進程進程,乃至乃至一條語句一條語句;結點間的結點間的有向邊有向邊則用于表示則用于表示兩個結點之間存在的兩個結點之間存在的偏序偏序(Partial Order)或或前趨關系前趨關系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果如果(Pi, Pj),可寫成可寫成PiPj,稱稱Pi是是Pj的直接前趨的直接前趨,而稱而稱Pj是是Pi的直接后的直接后繼。在前趨圖中繼。在前趨圖中,把沒有前趨的結點稱為把沒有前趨的結點稱為初始結點初始結點(Initial Node),把沒有后繼的結點稱為把沒有

4、后繼的結點稱為終止結點終止結點(Final Node)。2022-4-75 每個結點還具有一個每個結點還具有一個重量重量(Weight),用于表示該結點所用于表示該結點所含有的含有的程序量程序量或結點的或結點的執行時間執行時間。 圖圖2-2 2-2 前趨圖前趨圖 2022-4-76對于圖對于圖 2-2(a)所示的前趨圖所示的前趨圖,存在下述前趨關系存在下述前趨關系P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示為或表示為: P=P1, P2, P3, P4, P5, P6, P7, P8, P9=(P1, P

5、2),(P1, P3),(P1, P4),(P2, P5),(P3, P5),(P4, P6),(P4, P7),(P5, P8),(P6, P8),(P7, P9),(P8, P9) 應當注意應當注意,前趨圖中必須前趨圖中必須不存在不存在循環循環,但在圖但在圖2-2(b)中卻有著下中卻有著下述的前趨關系述的前趨關系: S2S3, S3S2 2022-4-772.1.1 2.1.1 程序的順序執行及其特征程序的順序執行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發執行及其特征程序的并發執行及其特征2.1.4 2.1.4 進程的特征與狀態進程的特征與狀態2.1.5

6、 2.1.5 進程控制塊進程控制塊2022-4-78程序的執行有兩種方式程序的執行有兩種方式:順序執行順序執行和和并發執行并發執行。順序執行順序執行是是單道單道批處理系統的執行方式批處理系統的執行方式,也用于也用于簡單的單簡單的單片機片機系統系統;現在的操作系統多為現在的操作系統多為并發執行并發執行,具有許多新的特征。引入具有許多新的特征。引入并發執行的目的是為了提高并發執行的目的是為了提高資源利用率。資源利用率。2022-4-79圖圖2-1 2-1 程序的順序執行程序的順序執行 1.程序的順序執行程序的順序執行 這是最自然、也是最初的設計。這是最自然、也是最初的設計。僅當前一操作僅當前一操作

7、(程序段程序段)執行完后執行完后,才能執行后繼操作。才能執行后繼操作。例如例如,在進行計算時在進行計算時,總須先輸總須先輸入用戶的程序和數據入用戶的程序和數據,然后進行計算然后進行計算,最后才能打印計算結果。最后才能打印計算結果。 S1: a:=x+y; S2: b:=a-5; S3: c:=b+1;2.1.1 2.1.1 程序的順序執行及其特征程序的順序執行及其特征2022-4-7102.2.程序順序執行時的特征程序順序執行時的特征(1)(1)順序性順序性: :處理機的操作嚴格按照程序所規定的順序執處理機的操作嚴格按照程序所規定的順序執行行, ,只有當上一個操作完成后只有當上一個操作完成后,

8、 ,下一個操作才能執行。下一個操作才能執行。(2)(2)封閉性封閉性: :程序運行在一個封閉的環境中程序運行在一個封閉的環境中, ,即程序運行時即程序運行時獨占系統的全部資源獨占系統的全部資源, ,這些資源的狀態只能因程序的執行這些資源的狀態只能因程序的執行而改變而改變, ,不受任何外界因素的影響。不受任何外界因素的影響。(3)(3)可再現性可再現性: :由于程序順序執行的封閉性由于程序順序執行的封閉性, ,只要程序順序只要程序順序執行的執行的初始條件和環境相同初始條件和環境相同, ,則不論何時執行則不論何時執行, ,也不論程也不論程序執行期間是否存在停頓序執行期間是否存在停頓, ,程序所得的

9、程序所得的結果結果也也相同相同。結論結論: :正由于程序順序執行的特點正由于程序順序執行的特點, ,程序員可以檢測和重程序員可以檢測和重現程序的錯誤現程序的錯誤, ,可以調試和校正程序。可以調試和校正程序。2022-4-7112.1.1 2.1.1 程序的順序執行及其特征程序的順序執行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發執行及其特征程序的并發執行及其特征2.1.4 2.1.4 進程的特征與狀態進程的特征與狀態2.1.5 2.1.5 進程控制塊進程控制塊2022-4-7122.1.3 2.1.3 程序的并發執行及其特征程序的并發執行及其特征 1.1.程序

10、的并發執行程序的并發執行 圖圖2-3 2-3 并發執行時的前趨圖并發執行時的前趨圖 2022-4-713在該例中存在下述前趨關系在該例中存在下述前趨關系: IiCi,IiIi+1, CiPi, CiCi+1,PiPi+1而而Ii+1和和Ci及及Pi-1是重迭的是重迭的,亦即在亦即在Pi-1和和Ci以及以及Ii+1之間之間,可以并可以并發執行。對于具有下述四條語句的程序段發執行。對于具有下述四條語句的程序段: S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6 圖圖2-4 2-4 四條語句的前趨關系四條語句的前趨關系S1S2S3S42022-4-7142.2.

11、程序并發執行時的特征程序并發執行時的特征 (1)(1)間斷性間斷性 走走停停走走停停,一個程序可能走到中途停下來一個程序可能走到中途停下來, ,失去失去原有的時序關系原有的時序關系; ;(2)(2)失去封閉性失去封閉性 程序并發執行時程序并發執行時,系統中多道程序系統中多道程序共享共享資源資源,資源的資源的狀態不是唯一地取決于某一個程序狀態不是唯一地取決于某一個程序,因此因此,必然失去了程必然失去了程序的封閉性序的封閉性,而程序的執行結果因依賴于外部環境也失而程序的執行結果因依賴于外部環境也失去了可再現性。去了可再現性。(3)(3)不可再現性不可再現性 失去封閉性失去封閉性 失去可再現性失去可

12、再現性; ;外界環境在程序的外界環境在程序的兩次執行期間發生變化兩次執行期間發生變化, ,失去原有的可重復特征。失去原有的可重復特征。2022-4-715例如例如, ,有兩個程序有兩個程序A A和和B,B,它們共享一個變量它們共享一個變量N(N(初始值為初始值為x)x)。 A:A:N:=N+1N:=N+1 B: B:Print(N);Print(N);N:=0; N:=0; 程序程序A A和和B B并發執行并發執行, ,以不可預知的速度運行以不可預知的速度運行, ,可出現以可出現以下下三種三種情況情況: : (1)N:=N+1 (1)N:=N+1在在Print(N)Print(N)和和N:=0

13、N:=0之之前前, ,此時得到的此時得到的N N值分別為值分別為x+1, x+1, 0 x+1, x+1, 0。 (2)N:=N+1(2)N:=N+1在在Print(N)Print(N)和和N:=0N:=0之之后后, ,此時得到的此時得到的N N值分別為值分別為x, 0, 1x, 0, 1。 (3)N:=N+1(3)N:=N+1在在Print(N)Print(N)和和N:=0N:=0之之間間, ,此時得到的此時得到的N N值分別為值分別為x, x+1, 0 x, x+1, 0。 2022-4-716補充補充: :并發執行失去封閉性的原因是共享資源的影響并發執行失去封閉性的原因是共享資源的影響,

14、 ,去掉這去掉這種影響就行了。種影響就行了。19661966年年, ,由由BernsteinBernstein( (波恩斯坦波恩斯坦) )給出給出并發并發執行的條件執行的條件。若兩個程序。若兩個程序P P1 1和和P P2 2滿足下述條件滿足下述條件, ,便能并發便能并發執行且有執行且有可再現性可再現性: :(R(P(R(P1 1) ) W(PW(P2 2) ( (R(PR(P2 2) ) W(PW(P1 1) ) ) ( (W(PW(P1 1) ) W(PW(P2 2)=)=解釋解釋: :運算的運算的讀集讀集R(PR(Pi i) )是指在運算執行期間參考的所有變量是指在運算執行期間參考的所有

15、變量的集合的集合; ;運算的運算的寫集寫集W(PW(Pi i) )是指在運算執行期間要改變的所有變是指在運算執行期間要改變的所有變量的集合。量的集合。存在的存在的問題問題是這個條件不好檢查是這個條件不好檢查2022-4-717S S1 1: a:=x+y: a:=x+yR(SR(S1 1)=x,y)=x,yW(SW(S1 1)=a)=aS S2 2: b:=z+1: b:=z+1R(SR(S2 2)=z)=zW(SW(S2 2)=b)=bS S3 3: c:=a-b: c:=a-bR(SR(S3 3)=a,b)=a,bW(SW(S3 3)=c)=cS S4 4: d:=c+1: d:=c+1R

16、(SR(S4 4)=c)=cW(SW(S4 4)=d)=d可見可見: :語句語句S S1 1和和S S2 2可以并發執行嗎？可以并發執行嗎？語句語句S S1 1和和S S3 3可以并發執行嗎？可以并發執行嗎？語句語句S S2 2和和S S3 3可以并發執行嗎？可以并發執行嗎？語句語句S S3 3和和S S4 4可以并發執行嗎？可以并發執行嗎？語句語句S S2 2和和S S4 4可以并發執行嗎？可以并發執行嗎？(R(S1) W(S2) (R(S2) W(S1) (W(S1) W(S2)=可以可以不可以不可以,因為因為: R(S3) W(S1)=a 不可以不可以,因為因為: R(S3) W(S2)

17、=b 不可以不可以,因為因為: R(S4) W(S3)=c 可以可以2022-4-7182.1.1 2.1.1 程序的順序執行及其特征程序的順序執行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發執行及其特征程序的并發執行及其特征2.1.4 2.1.4 進程的特征與狀態進程的特征與狀態2.1.5 2.1.5 進程控制塊進程控制塊2022-4-719進程實體由三部分構成進程實體由三部分構成: :(1)(1)程序程序( (段段) ): :進程要進行的操作。進程要進行的操作。(2)(2)數據段數據段: :包括操作的數據和程序自己的變量。包括操作的數據和程序自己的變量。(

18、3)(3)進程控制塊進程控制塊PCB(Process Control Block)PCB(Process Control Block): :存放進程標識存放進程標識符、進程運行的當前狀態、程序和數據的地址、程序運行符、進程運行的當前狀態、程序和數據的地址、程序運行時的時的CPUCPU環境等。環境等。2022-4-7202.1.4 2.1.4 進程的特征與狀態進程的特征與狀態 1.1.進程的特征和定義進程的特征和定義 動態性動態性: :進程是一個動態的概念進程是一個動態的概念, ,實質上是程序的一次實質上是程序的一次執行過程。進程具有生命期執行過程。進程具有生命期: :它因它因“創建創建”而產生

19、而產生, ,因因“調度調度”而執行而執行, ,執行時還走走停停執行時還走走停停, ,因因“撤消撤消”而滅而滅亡。亡。 并發性并發性: :多個進程實體同存于內存中多個進程實體同存于內存中, ,且能在一段時間且能在一段時間內同時運行內同時運行, ,共享系統資源共享系統資源; ;引入進程實體的目的就是引入進程實體的目的就是并發執行并發執行; ; 獨立性獨立性: :進程是一個能進程是一個能獨立運行獨立運行的基本單位的基本單位, ,也是系統也是系統進行資源分配和調度的基本單位進行資源分配和調度的基本單位; ; 異步性異步性: :各進程按各自獨立的、不可預知的速度向前各進程按各自獨立的、不可預知的速度向前

20、推進推進; ; 結構特征結構特征: :程序段程序段、數據段數據段和和PCBPCB; ;程序文件中通常也程序文件中通常也劃分了代碼段和數據段劃分了代碼段和數據段, ,進程的創建與撤消就是進程的創建與撤消就是PCBPCB的的創建與撤消。創建與撤消。2022-4-721較典型的較典型的進程定義進程定義有有: :(1)(1)進程是程序的一次執行。進程是程序的一次執行。(2)(2)進程是一個程序及其數據在處理機上順序執行時所發進程是一個程序及其數據在處理機上順序執行時所發生的活動。生的活動。(3)(3)進程是程序在一個數據集合上運行的過程進程是程序在一個數據集合上運行的過程, ,它是系統進它是系統進行資

21、源分配和調度的一個獨立單位。行資源分配和調度的一個獨立單位。 在引入了進程實體的概念后在引入了進程實體的概念后, ,我們可以把傳統我們可以把傳統OSOS中的中的進程定義為進程定義為: :“進程是進程實體的運行過程進程是進程實體的運行過程, ,是系統進行資是系統進行資源分配和調度的一個獨立單位源分配和調度的一個獨立單位”。 2022-4-722進程是動態的進程是動態的, ,程序是靜態的程序是靜態的: :程序是有序代碼的集合程序是有序代碼的集合, ,它可它可以復制以復制; ;進程是程序在數據集上的一次執行。進程是程序在數據集上的一次執行。進程是暫時的進程是暫時的, ,程序是永久的程序是永久的: :

22、進程是一個狀態變化的過程進程是一個狀態變化的過程, ,有它的撤銷有它的撤銷, ,程序可長久保存。程序可長久保存。進程具有結構特征進程具有結構特征, ,由程序段、數據段和進程控制塊三者組由程序段、數據段和進程控制塊三者組成成, ,而程序僅是指令的有序集合而程序僅是指令的有序集合, ,是進程的組成部分之一。是進程的組成部分之一。進程與程序的對應關系進程與程序的對應關系: :通過多次執行通過多次執行, ,一個程序可對應多一個程序可對應多個進程個進程; ;2022-4-7232.2.進程的三種基本狀態進程的三種基本狀態 (1)(1)就緒就緒(Ready)(Ready)狀態狀態 進程已獲得除進程已獲得除

23、處理機處理機外的所需資源外的所需資源, ,等待分配處理機資源等待分配處理機資源; ;只要分配只要分配CPUCPU就可執行。就可執行。一個系統中多個處于就緒狀態的進程排成一個系統中多個處于就緒狀態的進程排成就緒隊列。就緒隊列。(2)(2)執行執行(Running)(Running)狀態狀態處于就緒狀態的進程一旦獲得了處于就緒狀態的進程一旦獲得了處理機處理機, ,就可以運行就可以運行, ,進程進程狀態也就處于執行狀態。狀態也就處于執行狀態。處于此狀態的進程的數目處于此狀態的進程的數目小于等于小于等于CPUCPU的數目。的數目。(3)(3)阻塞阻塞(Blocked)(Blocked)狀態狀態( (“

24、等待等待”或或“睡眠睡眠”) ) 由于進程等待某種事件由于進程等待某種事件( (如如I/OI/O操作或進程同步操作或進程同步),),在事件發在事件發生之前無法繼續執行。該事件發生前即使把處理機分配給生之前無法繼續執行。該事件發生前即使把處理機分配給該進程該進程, ,也無法運行。如也無法運行。如: :請求請求I/OI/O操作操作, ,申請緩沖空間等申請緩沖空間等通常阻塞進程也排成通常阻塞進程也排成若干隊列若干隊列。2022-4-724圖圖2-5 2-5 進程的三種基本狀態及其轉換進程的三種基本狀態及其轉換 進程的三種基本狀態及其轉換進程的三種基本狀態及其轉換1.1.時間片用光時間片用光2.2.有

25、優先級高的進程到來有優先級高的進程到來2022-4-725新新( (創建創建) )狀態狀態 當一個新進程剛剛建立當一個新進程剛剛建立, ,還還未未將其放入就緒隊將其放入就緒隊列時的狀態列時的狀態, ,稱為新狀態。稱為新狀態。 終止狀態終止狀態 當一個進程已經當一個進程已經正常結束正常結束或或異常結束異常結束, ,操作系操作系統已將其從系統隊列中移出統已將其從系統隊列中移出, ,但但尚未撤消尚未撤消, ,這時稱為這時稱為終止狀態。終止狀態。 2022-4-726圖圖2-52-5 進程的五種基本狀態及其轉換進程的五種基本狀態及其轉換 進程的五種基本狀態及其轉換進程的五種基本狀態及其轉換2022-4

26、-7271.1.引入掛起狀態的原因引入掛起狀態的原因 (1)(1)終端用戶的請求終端用戶的請求當終端用戶在自己的程序運行期間發現有當終端用戶在自己的程序運行期間發現有可疑問可疑問題題時時, ,希望暫時將自己的程序靜止下來。希望暫時將自己的程序靜止下來。(2)(2)父進程請求父進程請求父進程需要考查和修改子進程。父進程需要考查和修改子進程。(3)(3)操作系統的需要操作系統的需要如檢查運行中的資源使用情況。如檢查運行中的資源使用情況。(4)(4)對換的需要對換的需要緩和內存緊張緩和內存緊張, ,將將阻塞進程阻塞進程換到外存上換到外存上, ,有別于阻有別于阻塞狀態。塞狀態。(5)(5)負荷調節的需

27、要負荷調節的需要在在實時系統實時系統中為了調整工作負荷可將不重要的進中為了調整工作負荷可將不重要的進程掛起。程掛起。3.3.掛起狀態掛起狀態2022-4-728圖圖2-6 2-6 具有掛起狀態的進程狀態圖具有掛起狀態的進程狀態圖 活動就緒靜止就緒執行掛起激活釋放掛起活動阻塞靜止阻塞掛起激活釋放請求I/O2.2.進程狀態的轉換進程狀態的轉換 2022-4-7292.1.1 2.1.1 程序的順序執行及其特征程序的順序執行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發執行及其特征程序的并發執行及其特征2.1.4 2.1.4 進程的特征與狀態進程的特征與狀態2.1.5

28、 2.1.5 進程控制塊進程控制塊2022-4-7302.1.5 2.1.5 進程控制塊進程控制塊 1.1.進程控制塊的作用進程控制塊的作用 進程控制塊的進程控制塊的作用作用是使一個在多道程序環境下不能是使一個在多道程序環境下不能獨立運行的程序獨立運行的程序( (含數據含數據),),成為一個能獨立運行的基本單成為一個能獨立運行的基本單位位, ,一個能與其它進程并發執行的進程。或者說一個能與其它進程并發執行的進程。或者說,OS,OS是根是根據據PCBPCB來對并發執行的進程進行控制和管理的。來對并發執行的進程進行控制和管理的。 記錄了操作系統所需的記錄了操作系統所需的, ,用于描述進程情況及控制

29、進用于描述進程情況及控制進程運行所需的程運行所需的全部信息全部信息。 PCBPCB是進程存在的唯一標志。是進程存在的唯一標志。2022-4-7312.2.進程控制塊中的信息進程控制塊中的信息 1) 1)進程標識符進程標識符 進程標識符用于惟一地標識一個進程。進程標識符用于惟一地標識一個進程。一個進程通常一個進程通常有有兩種兩種標識符標識符: : (1) (1)內部標識符內部標識符。在所有的操作系統中。在所有的操作系統中, ,都為每一個進都為每一個進程賦予一個惟一的程賦予一個惟一的數字標識符數字標識符, ,它通常是一個進程的序號。它通常是一個進程的序號。設置內部標識符主要是為了方便系統使用。設置

30、內部標識符主要是為了方便系統使用。 (2)(2)外部標識符外部標識符。它由創建者提供。它由創建者提供, ,通常是由字母、數通常是由字母、數字組成字組成, ,往往是由用戶往往是由用戶( (進程進程) )在訪問該進程時使用。為了在訪問該進程時使用。為了描述進程的家族關系描述進程的家族關系, ,還應設置父進程標識及子進程標識。還應設置父進程標識及子進程標識。此外此外, ,還可設置用戶標識還可設置用戶標識, ,以指示擁有該進程的用戶。以指示擁有該進程的用戶。2022-4-7322)2)處理機狀態處理機狀態 處理機狀態信息主要是由處理機的各種處理機狀態信息主要是由處理機的各種寄存器寄存器中的內中的內容組

31、成的。容組成的。通用寄存器通用寄存器, ,又稱為用戶可視寄存器又稱為用戶可視寄存器, ,它們是用戶程序可以它們是用戶程序可以訪問的訪問的, ,用于暫存信息用于暫存信息, ,在大多數處理機中在大多數處理機中, ,有有8 8 32 32 個通用個通用寄存器寄存器, ,在在RISCRISC結構的計算機中可超過結構的計算機中可超過100100個個; ;指令計數器指令計數器PCPC, ,其中存放了要訪問的下一條指令的地址其中存放了要訪問的下一條指令的地址; ;程序狀態字程序狀態字PSWPSW, ,其中含有狀態信息其中含有狀態信息, ,如條件碼、執行方式、如條件碼、執行方式、中斷屏蔽標志等中斷屏蔽標志等;

32、 ;用戶棧指針用戶棧指針, ,指每個用戶進程都有一個或若干個與之相關指每個用戶進程都有一個或若干個與之相關的系統棧的系統棧, ,用于存放過程和系統調用參數及調用地址。棧用于存放過程和系統調用參數及調用地址。棧指針指向該棧的棧頂。指針指向該棧的棧頂。2022-4-7333)3)進程調度信息進程調度信息 在在PCBPCB中還存放一些與進程調度和進程對換有關的中還存放一些與進程調度和進程對換有關的信息信息, ,包括包括: : 進程狀態進程狀態, ,指明進程的當前狀態指明進程的當前狀態, ,作為進程調度和對換時作為進程調度和對換時的依據的依據; ;進程優先級進程優先級, ,用于描述進程使用處理機的優先

33、級別的一用于描述進程使用處理機的優先級別的一個整數個整數, ,優先級高的進程應優先獲得處理機優先級高的進程應優先獲得處理機; ; 進程調度所需的其它信息進程調度所需的其它信息, ,它們與所采用的進程調度算它們與所采用的進程調度算法有關法有關, ,比如比如, ,進程已等待進程已等待CPUCPU的的時間總和時間總和、進程已執行、進程已執行的的時間總和時間總和等等; ;事件事件, ,是指進程由執行狀態轉變為阻塞狀態所等待發生是指進程由執行狀態轉變為阻塞狀態所等待發生的事件的事件, ,即即阻塞原因阻塞原因。 2022-4-7344)4)進程控制信息進程控制信息 進程控制信息包括進程控制信息包括: :程

34、序和數據的地址程序和數據的地址, ,是指進程的程序和數據所在的內存是指進程的程序和數據所在的內存或外存地或外存地( (首首) )址址, ,以便再調度到該進程執行時以便再調度到該進程執行時, ,能從能從PCBPCB中找到其程序和數據中找到其程序和數據; ;進程同步和通信機制進程同步和通信機制, ,指實現進程同步和進程通信時必指實現進程同步和進程通信時必需的機制需的機制, , 如消息隊列指針、如消息隊列指針、信號量信號量等等, ,它們可能全部它們可能全部或部分地放在或部分地放在PCBPCB中中; ;資源清單資源清單, ,是一張列出了除是一張列出了除CPUCPU以外的、進程所需的全部以外的、進程所需

35、的全部資源及已經分配到該進程的資源的清單資源及已經分配到該進程的資源的清單; ;鏈接指針鏈接指針, ,它給出了本進程它給出了本進程(PCB)(PCB)所在隊列中的所在隊列中的下一個下一個進進程的程的PCBPCB的首地址。的首地址。 2022-4-735圖圖2-7 PCB2-7 PCB鏈接隊列示意圖鏈接隊列示意圖 3.3.進程控制塊的組織方式進程控制塊的組織方式(1)(1)鏈接方式鏈接方式 把具有同一狀態的把具有同一狀態的PCBPCB用其中的鏈接字鏈接用其中的鏈接字鏈接成一個隊列成一個隊列, ,可以形成可以形成就緒隊列就緒隊列、若干個、若干個阻塞隊列阻塞隊列和和空空閑隊列閑隊列(2). .(2)

36、. .2022-4-736圖圖2-8 2-8 按索引方式組織按索引方式組織PCB PCB 3.3.進程控制塊的組織方式進程控制塊的組織方式(1). .(1). .(2)(2)索引方式索引方式 系統根據所有進程的狀態建立幾張系統根據所有進程的狀態建立幾張索引表索引表, ,如如就緒索引表就緒索引表、阻塞索引表阻塞索引表等等, ,并把各索引表在內存的并把各索引表在內存的首地址記錄在專用單元中。索引表中記錄的是首地址記錄在專用單元中。索引表中記錄的是PCBPCB在在PCBPCB表中的地地址。表中的地地址。2022-4-7372.1 2.1 進程的基本概念進程的基本概念 2.2 2.2 進程控制進程控制

37、 2.3 2.3 進程同步進程同步 2.4 2.4 經典進程的同步問題經典進程的同步問題 2.5 2.5 管程機制管程機制 2.6 2.6 進程通信進程通信 2.7 2.7 線程線程 2022-4-738處理機的執行狀態分處理機的執行狀態分系統態系統態和和用戶態用戶態兩種兩種: : (1) (1)系統態系統態( (管態管態、核心態核心態):):有較有較高高特權特權, ,能執能執行行一切一切指令指令, ,訪問訪問所有所有寄存器和存儲區。寄存器和存儲區。 (2)(2)用戶態用戶態( (目態目態):):有較有較低低特權特權, ,能執行能執行規定規定指指令令, ,訪問訪問指定指定寄存器和存儲區。寄存器

38、和存儲區。用戶用戶程序運行在程序運行在用戶態用戶態, ,不能執行不能執行OSOS指令及區域。指令及區域。OSOS內核運行在內核運行在系統態系統態, ,進程控制進程控制是由是由OSOS內核實現內核實現的。的。2022-4-739進程控制是進程管理中進程控制是進程管理中最基本最基本的功能的功能, ,主要包括以下幾個方面主要包括以下幾個方面 創建創建新進程新進程 終止終止已結束進程已結束進程 終止終止由于某事件而無法運行下去的進程由于某事件而無法運行下去的進程 負責進程的狀態負責進程的狀態轉換轉換原語原語(primitive)(primitive) 由若干條指令構成的由若干條指令構成的“原子操作原子

39、操作(atomic operation)(atomic operation)”過程過程, ,在執行期間在執行期間不可中斷不可中斷, ,以保證其正確性。作為一個整體而不以保證其正確性。作為一個整體而不可分割。許多系統調用就是原語。可分割。許多系統調用就是原語。 系統調用系統調用并不都是并不都是原語。進程原語。進程A A調用調用read(),read(),因無數據而阻因無數據而阻塞塞, ,在在read()read()里未返回。然后進程里未返回。然后進程B B調用調用read(),read(),此時此時read()read()被重入。系統調用不一定一次執行完并返回該進程被重入。系統調用不一定一次執行

40、完并返回該進程, ,有可能有可能在特定的點暫停在特定的點暫停, ,而轉入到其他進程。而轉入到其他進程。1.創建原語創建原語2.撤消原語撤消原語3.阻塞原語阻塞原語4.喚醒原語喚醒原語5.掛起原語掛起原語6.激活原語激活原語2022-4-7402.2.1 2.2.1 進程的創建進程的創建2.2.2 2.2.2 進程的終止進程的終止2.2.3 2.2.3 進程的阻塞與喚醒進程的阻塞與喚醒2.2.4 2.2.4 進程的掛起與激活進程的掛起與激活2022-4-7412.2.1 2.2.1 進程的創建進程的創建圖圖2-9 2-9 進程樹進程樹 1.1.進程圖進程圖(Process Graph)(Proc

41、ess Graph)進程圖進程圖是用于描述一個進程的家族是用于描述一個進程的家族關系關系的的有向樹有向樹, ,樹中的樹中的結點結點表示表示進程進程在進程在進程A A創建了進程創建了進程B B之后稱之后稱A A是是B B的的父進程父進程(Parent Process)(Parent Process),B,B是是A A的的子子進程進程(Progeny Process)(Progeny Process)。創建父進。創建父進程的進程稱為祖先進程程的進程稱為祖先進程, ,把樹的把樹的根根結結點稱為進程家族的點稱為進程家族的祖先進程祖先進程(Ancestor)(Ancestor)子進程可以子進程可以繼承繼

42、承(Inherit)(Inherit)父進程的父進程的資源。資源。撤消父進程時必須撤消父進程時必須同時同時撤消子進程撤消子進程2022-4-7422.2.引起創建進程的事件引起創建進程的事件 在在多道程序多道程序環境中環境中, ,只有只有進程進程才能在系統中運行。才能在系統中運行。因此因此, ,為使程序運行為使程序運行, ,必須創建進程必須創建進程, ,創建進程事件包創建進程事件包括括: :(1)(1)用戶登錄用戶登錄 在在分時系統分時系統中中, ,用戶在終端登錄后用戶在終端登錄后, ,如是合法用戶如是合法用戶, ,系統將為用戶創建一個進程系統將為用戶創建一個進程, ,并插入并插入就緒隊列就緒

43、隊列。(2)(2)作業調度作業調度 在批處理系統中在批處理系統中, ,當作業調度程序調度到某作業當作業調度程序調度到某作業時時, ,將該作業裝入內存將該作業裝入內存, ,為它分配資源并創建進程。為它分配資源并創建進程。(3)(3)提供服務提供服務 當運行中的用戶進程提出某種請求后當運行中的用戶進程提出某種請求后, ,系統系統將專將專門創建一個進程來提供服務門創建一個進程來提供服務, ,如打印。如打印。(4)(4)應用請求應用請求 由應用進程為由應用進程為自己自己創建進程創建進程, ,以便能并發執行以便能并發執行, ,如如輸入、計算、輸出程序。輸入、計算、輸出程序。2022-4-7433.3.進

44、程的創建進程的創建步驟步驟(Creation of Progress) (Creation of Progress) (1)(1)申請空白申請空白PCB PCB 為新進程申請惟一的數字為新進程申請惟一的數字標識符標識符, ,并從并從PCBPCB集合中索取集合中索取一個空白一個空白PCBPCB(2)(2)為新進程分配資源為新進程分配資源 為新進程的程序和數據為新進程的程序和數據分配內存分配內存。對于。對于批處理批處理型作業型作業, ,可以在可以在用戶用戶提出創建進程時要求提供所需內存大小。提出創建進程時要求提供所需內存大小。對于對于交互型交互型作業可以由作業可以由系統系統來分配一定的空間來分配一

45、定的空間(3)(3)初始化進程控制塊初始化進程控制塊 初始化標識信息初始化標識信息將系統標識信息寫入新將系統標識信息寫入新PCBPCB初始化處理機狀態信息初始化處理機狀態信息使使程序計數器程序計數器指向程序的入指向程序的入口地址口地址, ,棧指針指向棧頂棧指針指向棧頂初始化處理機控制信息初始化處理機控制信息將進程的狀態設為將進程的狀態設為就緒狀態就緒狀態或或靜止就緒狀態靜止就緒狀態(4)(4)將新進程插入就緒隊列將新進程插入就緒隊列如果進程就緒隊列能夠接納新進程如果進程就緒隊列能夠接納新進程, ,便將新進程插入就便將新進程插入就緒隊列緒隊列2022-4-7442.2.1 2.2.1 進程的創建

46、進程的創建2.2.2 2.2.2 進程的終止進程的終止2.2.3 2.2.3 進程的阻塞與喚醒進程的阻塞與喚醒2.2.4 2.2.4 進程的掛起與激活進程的掛起與激活2022-4-7451.1.引起進程終止引起進程終止(Termination of Process)(Termination of Process)的事件的事件 1)1)正常結束正常結束 在任何計算機系統中在任何計算機系統中, ,都應有一個用于表示進程已經都應有一個用于表示進程已經運行完成的指示。例如運行完成的指示。例如, ,在批處理系統中在批處理系統中, ,通常在程序的最通常在程序的最后安排一條后安排一條HaltHalt指令或終

47、止的系統調用。當程序運行到指令或終止的系統調用。當程序運行到HaltHalt指令時指令時, ,將產生一個中斷將產生一個中斷, ,去通知去通知OSOS本進程已經完成。本進程已經完成。 在分時系統中在分時系統中, ,用戶可利用用戶可利用Logs offLogs off去表示進程運行完畢去表示進程運行完畢, , 此時同樣可產生一個中斷此時同樣可產生一個中斷, ,去通知去通知OSOS進程已運行完畢。進程已運行完畢。 2022-4-746 2) 2)異常結束異常結束 在進程運行期間在進程運行期間, ,由于出現某些錯誤和故障而迫使進程由于出現某些錯誤和故障而迫使進程終止。這類異常事件很多終止。這類異常事件

48、很多, ,常見的有常見的有: :越界錯誤。這是指程序所訪問的存儲區越界錯誤。這是指程序所訪問的存儲區, ,已已越出越出該進程的區該進程的區域域; ; 保護錯。進程試圖去訪問一個保護錯。進程試圖去訪問一個不允許訪問不允許訪問的資源或文件的資源或文件, ,或或者以不適當的方式進行訪問者以不適當的方式進行訪問, ,例如例如, ,進程試圖去寫一個進程試圖去寫一個只讀只讀文件文件; ;非法指令。程序試圖去執行一條非法指令。程序試圖去執行一條不存在不存在的的指令指令。出現該錯。出現該錯誤的原因誤的原因, ,可能是程序錯誤地轉移到數據區可能是程序錯誤地轉移到數據區, ,把數據當成了把數據當成了指令指令; ;

49、特權指令錯。用戶進程試圖去執行一條只允許特權指令錯。用戶進程試圖去執行一條只允許OSOS執行的指執行的指令令; ;運行超時。進程的執行時間超過了指定的最大值運行超時。進程的執行時間超過了指定的最大值; ;等待超時。進程等待某事件的時間等待超時。進程等待某事件的時間, ,超過了規定的最大值超過了規定的最大值; ;算術運算錯。進程試圖去執行一個被禁止的運算算術運算錯。進程試圖去執行一個被禁止的運算, ,例如例如, ,被被0 0除除; ;I/OI/O故障。這是指在故障。這是指在I/OI/O過程中發生了錯誤等。過程中發生了錯誤等。2022-4-747 3) 3)外界干預外界干預 外界干預并外界干預并非

50、非指在本進程運行中出現了指在本進程運行中出現了異常事件異常事件, ,而而是指進程應外界的請求而終止運行。這些干預有是指進程應外界的請求而終止運行。這些干預有: :操作員操作員或或操作系統操作系統干預。由于某種原因干預。由于某種原因, ,例如例如, ,發生了發生了死鎖死鎖, ,由操作員或操作系統終止該進程由操作員或操作系統終止該進程; ;父進程請求父進程請求。由于父進程具有終止自己的任何子孫進。由于父進程具有終止自己的任何子孫進程的權利程的權利, ,因而當父進程提出請求時因而當父進程提出請求時, ,系統將終止該進程系統將終止該進程; ; 父進程終止父進程終止。當父進程終止時。當父進程終止時,OS

51、,OS也將他的所有子孫進也將他的所有子孫進程終止。程終止。 2022-4-7482.2.進程的終止過程進程的終止過程 (1)(1)根據被終止進程的標識符根據被終止進程的標識符, ,從從PCBPCB集合中檢索出該進集合中檢索出該進程的程的PCB,PCB,從中讀出該進程的狀態。從中讀出該進程的狀態。 (2)(2)若被終止進程正處于若被終止進程正處于執行狀態執行狀態, ,應立即終止該進程應立即終止該進程的執行的執行, ,并置并置調度標志調度標志為為真真, ,用于指示該進程被終止后應重用于指示該進程被終止后應重新進行調度。新進行調度。 (3)(3)若該進程還有若該進程還有子孫進程子孫進程, ,還應將其

52、所有子孫進程予還應將其所有子孫進程予以以終止終止, ,以防他們成為不可控的進程。以防他們成為不可控的進程。 (4)(4)將被終止進程所擁有的將被終止進程所擁有的全部資源全部資源, ,或者歸還給其父或者歸還給其父進程進程, , 或者歸還給系統。或者歸還給系統。 (5)(5)將被終止進程將被終止進程( (它的它的PCBPCB) )從所在隊列從所在隊列( (或鏈表或鏈表) )中中移移出出, ,等待其他程序來搜集信息。等待其他程序來搜集信息。 2022-4-7492.2.1 2.2.1 進程的創建進程的創建2.2.2 2.2.2 進程的終止進程的終止2.2.3 2.2.3 進程的阻塞與喚醒進程的阻塞與

53、喚醒2.2.4 2.2.4 進程的掛起與激活進程的掛起與激活2022-4-7501.1.引起進程阻塞和喚醒的事件引起進程阻塞和喚醒的事件 (1)(1)請求系統服務請求系統服務 如請求如請求打印機打印機時時, ,若已被其他進程若已被其他進程占用占用, ,此時只能此時只能阻塞阻塞, ,等其他進程釋放后再將請求進程喚醒。等其他進程釋放后再將請求進程喚醒。(2)(2)啟動某種操作啟動某種操作 當進程啟動某種操作后當進程啟動某種操作后, ,如果該進程必須在該操如果該進程必須在該操作完成后才能繼續執行作完成后才能繼續執行, ,則必須先使進程阻塞則必須先使進程阻塞, ,以等待以等待該該操作完成操作完成。如啟

54、動。如啟動I/OI/O設備。設備。(3)(3)新數據尚未到達新數據尚未到達 對于相互合作的進程對于相互合作的進程, ,如果一個進程需要另一合如果一個進程需要另一合作進程提供的數據作進程提供的數據, ,則在數據到達之前只能阻塞。則在數據到達之前只能阻塞。(4)(4)無新工作可做無新工作可做 系統中的一些特殊功能進程系統中的一些特殊功能進程, ,在完成了任務之后在完成了任務之后, ,等待新任務到來。如系統中的發送進程。等待新任務到來。如系統中的發送進程。2022-4-7512.2.進程阻塞過程進程阻塞過程 正在執行的進程正在執行的進程, ,當發現上述某事件時當發現上述某事件時, ,由于無法繼續由于

55、無法繼續執行執行, ,于是進程便通過調用阻塞原語于是進程便通過調用阻塞原語block()block()把自己阻把自己阻塞。可見塞。可見, ,進程的阻塞是進程自身的一種主動行為進程的阻塞是進程自身的一種主動行為 進入進入blockblock過程后過程后, ,由于此時該進程還處于由于此時該進程還處于執行狀態執行狀態, ,所以應先立即所以應先立即停止執行停止執行, ,把進程控制塊中的現行狀態把進程控制塊中的現行狀態由由“執行執行”改為改為阻塞阻塞, ,并將并將PCBPCB插入插入阻塞隊列阻塞隊列 如果系統中設置了因不同事件而阻塞的多個如果系統中設置了因不同事件而阻塞的多個阻塞隊列阻塞隊列, ,則應將

56、本進程則應將本進程插入插入到具有相同事件的阻塞到具有相同事件的阻塞( (等待等待) )隊列隊列 調度程序進行調度程序進行重新調度重新調度, ,將處理機分配給另一就緒進將處理機分配給另一就緒進程程, ,并進行切換并進行切換, ,亦即亦即, ,保留被阻塞進程的處理機狀態保留被阻塞進程的處理機狀態( (在在PCBPCB中中),),再按新進程的再按新進程的PCBPCB中的處理機狀態設置中的處理機狀態設置CPUCPU的環境的環境2022-4-7523.3.進程喚醒過程進程喚醒過程 當被阻塞進程所期待的事件出現時當被阻塞進程所期待的事件出現時, ,如如I/OI/O完成或其所完成或其所期待的數據已經到達期待

57、的數據已經到達, ,則由有關進程則由有關進程( (比如比如, ,用完并釋用完并釋放了該放了該I/OI/O設備的進程設備的進程) )調用喚醒原語調用喚醒原語wakeup( )wakeup( ), ,將等將等待該事件的進程喚醒待該事件的進程喚醒 喚醒原語執行的過程是喚醒原語執行的過程是 把被阻塞的進程從等待該事件的阻塞隊列中把被阻塞的進程從等待該事件的阻塞隊列中移出移出 將其將其PCBPCB中的現行狀態由中的現行狀態由阻塞阻塞改為改為就緒就緒 將該將該PCBPCB插入到插入到就緒隊列就緒隊列中中2022-4-7532.2.1 2.2.1 進程的創建進程的創建2.2.2 2.2.2 進程的終止進程的

58、終止2.2.3 2.2.3 進程的阻塞與喚醒進程的阻塞與喚醒2.2.4 2.2.4 進程的掛起與激活進程的掛起與激活2022-4-7541.1.進程的掛起進程的掛起 當出現了引起進程掛起的事件時當出現了引起進程掛起的事件時, ,比如比如, ,用戶進程請求用戶進程請求將自己掛起將自己掛起, ,或父進程請求將自己的某個子進程掛起或父進程請求將自己的某個子進程掛起, , 系統將利用掛起原語系統將利用掛起原語suspend( )suspend( )將指定進程或處于阻將指定進程或處于阻塞狀態的進程掛起。塞狀態的進程掛起。 suspend()suspend()原語的執行過程原語的執行過程 首先檢查被掛起進

59、程的狀態首先檢查被掛起進程的狀態, ,若處于若處于活動就緒活動就緒狀態狀態, ,便將其改為便將其改為靜止就緒靜止就緒; ;對于對于活動阻塞活動阻塞狀態的進程狀態的進程, ,則將之改為則將之改為靜止阻塞。靜止阻塞。 為了方便用戶或父進程考查該進程的運行情況而為了方便用戶或父進程考查該進程的運行情況而把該進程的把該進程的PCBPCB復制復制到某指定的到某指定的內存區域內存區域。 若被掛起的進程若被掛起的進程正在執行正在執行, ,則轉向調度程序則轉向調度程序重新調重新調度。度。2022-4-7552.2.進程的激活過程進程的激活過程 當發生激活進程的事件時當發生激活進程的事件時, ,例如例如, ,父

60、進程或用戶進程請父進程或用戶進程請求激活指定進程求激活指定進程, ,若該進程駐留在外存而內存中已有若該進程駐留在外存而內存中已有足夠的空間時足夠的空間時, ,則可將在外存上處于靜止就緒狀態的則可將在外存上處于靜止就緒狀態的進程換入內存。這時進程換入內存。這時, ,系統將利用激活原語系統將利用激活原語active( )active( )將指定進程激活。將指定進程激活。 active()active()原語執行過程原語執行過程 激活原語先將進程從外存激活原語先將進程從外存調入內存調入內存, ,檢查該進程的檢查該進程的現行狀態現行狀態, ,若是若是靜止就緒靜止就緒, ,便將之改為便將之改為活動就緒活