1、第第3 3章章 處理機管理處理機管理本章學習目標本章學習目標在多道程序環境下，程序不能獨立運行。作為資源分配和在多道程序環境下，程序不能獨立運行。作為資源分配和獨立運行的基本單位是進程。操作系統所有的特征都是基獨立運行的基本單位是進程。操作系統所有的特征都是基于進程而體現的。所以，本章的主要問題是：于進程而體現的。所以，本章的主要問題是： 進程的概念進程的概念進程的實體、狀態及狀態的演變進程的實體、狀態及狀態的演變進程的控制與調度進程的控制與調度進程之間的關系進程之間的關系進程的通信進程的通信線程線程死鎖問題及解決死鎖問題及解決返回本章首頁返回本章首頁第第3章章 處理機管理處理機管理第第3 3

2、章章 處理機管理處理機管理3.1 進程的定義和特征進程的定義和特征 3.1.1 3.1.1 進程的引入進程的引入3.1.2 3.1.2 進程的定義進程的定義3.1.3 3.1.3 進程的進程的特征特征返回本章首頁返回本章首頁第第3 3章章 處理機管理處理機管理3.1.1 進程的引入進程的引入 在多道程序系統中，程序并不能獨立運行。獨立在多道程序系統中，程序并不能獨立運行。獨立運行和資源分配的基本單位是進程。用進程的觀點運行和資源分配的基本單位是進程。用進程的觀點來研究操作系統，可深入地了解和把握系統內部的來研究操作系統，可深入地了解和把握系統內部的動態活動，這就是所謂研究操作系統進程的觀點。動

3、態活動，這就是所謂研究操作系統進程的觀點。 進程也是對操作系統進行設計的一個重要概念。進程也是對操作系統進行設計的一個重要概念。 下一頁下一頁第第3 3章章 處理機管理處理機管理3.1.1 進程的引入進程的引入1程序的順序執行及其特性程序的順序執行及其特性2程序的并發執行和資源共享程序的并發執行和資源共享3程序的并發執行特性程序的并發執行特性 下一頁下一頁第第3 3章章 處理機管理處理機管理 一個程序由若干個程序段組成，而這些程序段的一個程序由若干個程序段組成，而這些程序段的執行必須是順序的，這種程序執行的方式就稱為程序執行必須是順序的，這種程序執行的方式就稱為程序的順序執行。的順序執行。 例

4、如：例如： 下一頁下一頁I1P1O1I2P2O21程序的順序執行及其特性程序的順序執行及其特性第第3 3章章 處理機管理處理機管理1.1.順序性順序性 處理機嚴格按照程序所規定的順序執行，即每個操處理機嚴格按照程序所規定的順序執行，即每個操作必須在下一個操作開始之前結束。作必須在下一個操作開始之前結束。2. 2. 資源獨占資源獨占 程序在執行過程中獨占全機資源，資源狀態的改變程序在執行過程中獨占全機資源，資源狀態的改變只與本程序有關而與外界環境無關。只與本程序有關而與外界環境無關。3. 3. 結果無關性結果無關性 程序執行的結果與初始條件有關，而與執行速度無程序執行的結果與初始條件有關，而與執

5、行速度無關。即只要程序的初始條件相同，它的執行結果是相關。即只要程序的初始條件相同，它的執行結果是相同的，不論它在什么時間執行，也不管計算機的運行同的，不論它在什么時間執行，也不管計算機的運行速度。速度。第第3 3章章 處理機管理處理機管理 順序程序以上的執行特性可歸結為順序程序以上的執行特性可歸結為封閉性封閉性和和可再現性可再現性。 所謂所謂封閉性封閉性就是指程序一旦運行，就不受外就是指程序一旦運行，就不受外界環境的影響，其運行結果與環境以外的事情界環境的影響，其運行結果與環境以外的事情無關；無關； 所謂所謂可再現性可再現性就是指程序重復運行時，只要就是指程序重復運行時，只要初始條件相同，必

6、將獲得相同的結果。初始條件相同，必將獲得相同的結果。第第3 3章章 處理機管理處理機管理圖3.2 程序的并發執行有向圖 下一頁下一頁P3I11I2I3 3I4 4P1 1P2P4 4o1 o2 2o3 3o4 42程序的并發執行和資源共享程序的并發執行和資源共享第第3 3章章 處理機管理處理機管理3程序的并發執行特性程序的并發執行特性 無論是操作系統自身的程序還是用戶程序，通常無論是操作系統自身的程序還是用戶程序，通常總是存在一些相對獨立、但又能并發執行的程序總是存在一些相對獨立、但又能并發執行的程序段。由于這些程序段可以被多個用戶作業調用，段。由于這些程序段可以被多個用戶作業調用，因此可在同

7、一時間間隔內發生。這樣一來，某個因此可在同一時間間隔內發生。這樣一來，某個程序段可能對應多個程序段可能對應多個“計算計算”，于是程序與，于是程序與“計計算算”已不具有一一對應關系了。這些已不具有一一對應關系了。這些“并發程序并發程序”就構成了一個就構成了一個“并發環境并發環境”。下一頁下一頁第第3 3章章 處理機管理處理機管理程序并發執行特征：程序并發執行特征：（1 1）失去封閉性）失去封閉性 例：觀察者例：觀察者/ /報告者報告者 (2) (2) 程序和機器執行程序的活動不再一一程序和機器執行程序的活動不再一一 對應對應 (3) 并發程序間的相互制約并發程序間的相互制約 第第3 3章章 處理

8、機管理處理機管理觀察者：觀察者： 報告者：報告者：begin beginbegin begin repeat repeat repeat repeat wait a car go through deley a time wait a car go through deley a time N=N+1N=N+1； Print N Print N ； N=0 N=0 ； until until until untilend endend end初始初始N=nN=n時不同執行序列：時不同執行序列： N=N+1N=N+1； Print N Print N； Print N Print N ； Pri

9、nt N Print N ； N=0 N=0 ； N=N+1 N=N+1 ； N=0 N=0 ； N=N+1 N=N+1 ； N=0 N=0 ；結果各不相同結果各不相同: : 打印打印n+1n+1，N=0N=0； 打印打印n n，N=1N=1； 打印打印n n，N=0N=0；第第3 3章章 處理機管理處理機管理 資源共享是現代操作系統的另一基本特性。所謂資源共享是資源共享是現代操作系統的另一基本特性。所謂資源共享是指系統中的硬件資源和軟件資源不再為單個用戶程序所獨占，指系統中的硬件資源和軟件資源不再為單個用戶程序所獨占，而由幾道用戶程序共同使用。這樣，這些資源的狀態不再取決而由幾道用戶程序共同

10、使用。這樣，這些資源的狀態不再取決于一道程序，而是由多道程序的活動所決定。這就從根本上打于一道程序，而是由多道程序的活動所決定。這就從根本上打破了一道程序封閉于一個系統中執行的局面。破了一道程序封閉于一個系統中執行的局面。 程序并發執行和資源共享之間互為依存條件。一方面，資程序并發執行和資源共享之間互為依存條件。一方面，資源共享是以程序并發執行為條件的，因為若系統不允許程序并源共享是以程序并發執行為條件的，因為若系統不允許程序并發，也就不存在資源共享問題；另一方面，若系統不能對共享發，也就不存在資源共享問題；另一方面，若系統不能對共享資源進行有效管理，也就降低了程序并發執行的效果。資源進行有效

11、管理，也就降低了程序并發執行的效果。 第第3 3章章 處理機管理處理機管理程序的制約方式有如下兩種程序的制約方式有如下兩種 ：（1）間接制約方式。）間接制約方式。這是由于競爭相同資源而引起的，得到資源的程序段可以投這是由于競爭相同資源而引起的，得到資源的程序段可以投入運行，而得不到資源的程序段就是暫時等待，直至獲得可入運行，而得不到資源的程序段就是暫時等待，直至獲得可用資源時再繼續運行用資源時再繼續運行 。（2）直接制約方式。）直接制約方式。這通常是在那些邏輯上相關的程序段之間發生的。一般是由這通常是在那些邏輯上相關的程序段之間發生的。一般是由于各種程序段要求共享信息引起的于各種程序段要求共享

12、信息引起的 。如。如, ,進程之間的合作進程之間的合作第第3 3章章 處理機管理處理機管理由于程序在并發執行時，各次執行的結果不同，所以用由于程序在并發執行時，各次執行的結果不同，所以用“程序程序”這個概念已無法描述程序的并發執行，所以必須這個概念已無法描述程序的并發執行，所以必須引入新的概念引入新的概念進程來描述程序的并發執行。進程這一進程來描述程序的并發執行。進程這一術語最早由麻省理工學院著名的操作系統術語最早由麻省理工學院著名的操作系統MULTICSMULTICS中提出。中提出。 進程定義：進程定義：“可并發執行的程序在一個數據集合上的運可并發執行的程序在一個數據集合上的運行過程行過程”

13、。(1) (1) 進程是程序的一次執行。進程是程序的一次執行。(2) (2) 進程是可以和別的計算并發執行的計算。進程是可以和別的計算并發執行的計算。(3) (3) 進程是一個具有一定獨立功能的程序在某個數據集上進程是一個具有一定獨立功能的程序在某個數據集上的一次執行活動，它可以和同樣的其它程序共行。的一次執行活動，它可以和同樣的其它程序共行。(4) (4) 進程是一個程序及數據在處理機上順序執行時所發生進程是一個程序及數據在處理機上順序執行時所發生的活動。的活動。(5) (5) 進程是程序在一個數據集上的運行過程，是系統可調進程是程序在一個數據集上的運行過程，是系統可調度的實體。度的實體。第

14、第3 3章章 處理機管理處理機管理3.1.3 3.1.3 進程的特征進程的特征 進程的特征進程的特征: :動態性：動態性：動態性是進程的最基本特征，它是程序執行過動態性是進程的最基本特征，它是程序執行過程，它是有一定的生命期。它由創建而產生、由調度而程，它是有一定的生命期。它由創建而產生、由調度而執行，因得不到資源而暫仃，并由撤消而死亡。而程序執行，因得不到資源而暫仃，并由撤消而死亡。而程序是靜態的，它是存放在介質上一組有序指令的集合，無是靜態的，它是存放在介質上一組有序指令的集合，無運動的含義。運動的含義。第第3 3章章 處理機管理處理機管理并發性：并發性：并發性是進程的重要特征，同時也是并

15、發性是進程的重要特征，同時也是OSOS的重要特的重要特征。并發性指多個進程實體同存于內存中，能在一段時間征。并發性指多個進程實體同存于內存中，能在一段時間內同時運行。而程序是不能并發執行。內同時運行。而程序是不能并發執行。獨立性：獨立性：進程是一個能獨立運行的基本單位，即是一個獨進程是一個能獨立運行的基本單位，即是一個獨立獲得資源和獨立調度的單位，而程序不作為獨立單位參立獲得資源和獨立調度的單位，而程序不作為獨立單位參加運行。加運行。異步性：異步性：進程按各自獨立的不可預知的速度向前推進，即進程按各自獨立的不可預知的速度向前推進，即進程按異步方式進行，正是這一特征，將導致程序執行的進程按異步方

16、式進行，正是這一特征，將導致程序執行的不可再現性，因此不可再現性，因此OSOS必須采用某種措施來限制各進程推進必須采用某種措施來限制各進程推進序列以保證各程序間正常協調運行。序列以保證各程序間正常協調運行。結構特征：結構特征：從結構上，進程實體由程序段、數據段和進程從結構上，進程實體由程序段、數據段和進程控制塊三部分組成，控制塊三部分組成，UNIXUNIX中稱為中稱為“進程映象進程映象”。第第3 3章章 處理機管理處理機管理3.2 進程的描述進程的描述 返回本章首頁返回本章首頁3.2.1 3.2.1 進程的表示進程的表示3.2.2 3.2.2 進程的基本調度狀態及其轉換進程的基本調度狀態及其轉

17、換 第第3 3章章 處理機管理處理機管理 進程組成：進程組成： 程序程序 + + 數據數據 + + PCBPCB 進程控制塊進程控制塊 （PCBPCBProcess Control BlockProcess Control Block） 進程與進程與PCBPCB是一一對應的是一一對應的 為了刻畫進程的動態變化，通常把進程表示為由程序為了刻畫進程的動態變化，通常把進程表示為由程序段、私有數據塊和進程控制塊組成。程序部分描述進程本段、私有數據塊和進程控制塊組成。程序部分描述進程本身所要完成的功能，而身所要完成的功能，而“私有數據塊私有數據塊”是接受程序規定操是接受程序規定操作的一組存儲單元的內容，

18、是操作的對象。進程控制塊是作的一組存儲單元的內容，是操作的對象。進程控制塊是在進程創建時產生的，當進程存在于系統時（運行），進在進程創建時產生的，當進程存在于系統時（運行），進程控制塊就標識了這個進程程控制塊就標識了這個進程 下一頁下一頁3.2.1 3.2.1 進程的表示進程的表示第第3 3章章 處理機管理處理機管理在進程控制塊中，主要包含下列在進程控制塊中，主要包含下列4 4方面的信息。方面的信息。1) 1) 進程標識符進程標識符這是用來唯一標識一個進程的信息。通常有以下兩種標識符。這是用來唯一標識一個進程的信息。通常有以下兩種標識符。(1) (1) 外部標識符。這由進程創建者提供，通常由字

19、母、數字組成。外部標識符。這由進程創建者提供，通常由字母、數字組成。外部標識符便于記憶，如計算進程、打印進程等，以便用戶外部標識符便于記憶，如計算進程、打印進程等，以便用戶( (進程進程) )訪問該進程時使用。訪問該進程時使用。(2) (2) 內部標識符。在所有操作系統中都為每一進程賦予一個唯一內部標識符。在所有操作系統中都為每一進程賦予一個唯一的整數，作為進程的內部標識符。的整數，作為進程的內部標識符。2) 2) 處理機狀態信息處理機狀態信息這是指一個原在執行的進程，因某種原因而被暫停執行瞬間的處這是指一個原在執行的進程，因某種原因而被暫停執行瞬間的處理機映象。其中包括：理機映象。其中包括：

20、(1) 通用寄存器信息。通用寄存器信息。 （2） 指令計數器信息指令計數器信息(3) (3) 程序狀態字程序狀態字PSW PSW (4) (4) 用戶棧指針。用戶棧指針。第第3 3章章 處理機管理處理機管理3) 3) 進程的調度信息進程的調度信息這主要是指與進程調度和進程對換有關的信息，包括以下這主要是指與進程調度和進程對換有關的信息，包括以下4 4點。點。(1) (1) 進程狀態。指明進程當前所處的狀態，如就緒、阻塞等。這進程狀態。指明進程當前所處的狀態，如就緒、阻塞等。這是調度進程或進程對換的依據。是調度進程或進程對換的依據。(2) (2) 進程優先級。用于描述進程使用處理機的優先級別，一

21、般用進程優先級。用于描述進程使用處理機的優先級別，一般用優先數來表示。優先級高的進程可優先獲得處理機。優先數來表示。優先級高的進程可優先獲得處理機。(3) (3) 其它調度信息。如進程已等待其它調度信息。如進程已等待CPUCPU的時間總和、進程已執行的時間總和、進程已執行的時間總和等，這與所采用的進程調度算法有關。的時間總和等，這與所采用的進程調度算法有關。(4) (4) 事件。這是指進程由執行狀態轉變為阻塞狀態所等待發生的事件。這是指進程由執行狀態轉變為阻塞狀態所等待發生的事件，也就是阻塞的原因。事件，也就是阻塞的原因。第第3 3章章 處理機管理處理機管理4) 4) 進程控制信息進程控制信息

22、(1) (1) 程序和數據集的地址。它是指該進程實體中程序和數據集所程序和數據集的地址。它是指該進程實體中程序和數據集所在的存儲地址在的存儲地址( (內存或外存內存或外存) )，以便當調度到該進程時，能定位到，以便當調度到該進程時，能定位到其程序和數據。其程序和數據。(2) (2) 同步和通信機制。它是指實現進程同步和進程通信時所必須同步和通信機制。它是指實現進程同步和進程通信時所必須的機制，如消息隊列指針、信號量等，這些信息可能全部或部分的機制，如消息隊列指針、信號量等，這些信息可能全部或部分存放于存放于PCBPCB中。中。(3) (3) 鏈接指針。為了有效地管理所有進程，在系統中要組成各種

23、鏈接指針。為了有效地管理所有進程，在系統中要組成各種進程隊列，以及在有些操作系統中，采用樹結構方式來管理進程，進程隊列，以及在有些操作系統中，采用樹結構方式來管理進程，這都需要有相應的鏈接指針。這都需要有相應的鏈接指針。(4) (4) 資源清單。這是一張列出除資源清單。這是一張列出除CPUCPU以外的，進程所需的全部資以外的，進程所需的全部資源及已經分配到資源的清單。源及已經分配到資源的清單。第第3 3章章 處理機管理處理機管理下一頁下一頁第第3 3章章 處理機管理處理機管理 進程控制塊是進程存在的標志，當系統或父進進程控制塊是進程存在的標志，當系統或父進程創建一個進程時，實際上就是為其建立一

24、個進程創建一個進程時，實際上就是為其建立一個進程控制塊。程控制塊。 進程控制塊既能標識進程的存在，又能刻畫出進程控制塊既能標識進程的存在，又能刻畫出進程的動態特征，它是一個進程僅有的被系統真進程的動態特征，它是一個進程僅有的被系統真正感知的部分。正感知的部分。進程控制塊的作用：進程控制塊的作用：返回本節目錄返回本節目錄第第3 3章章 處理機管理處理機管理PCBPCB的組織形式的組織形式PCBPCB組織的目標：便于調度和管理進程組織的目標：便于調度和管理進程 方法有三：方法有三： （1 1）線性表：簡單，但進程多時查找速度慢！）線性表：簡單，但進程多時查找速度慢！ （2 2）索引表：相同狀態的進

25、程）索引表：相同狀態的進程PCBPCB組織在同一張表格中，組織在同一張表格中，如就緒進程索引表，阻塞進程索引表如就緒進程索引表，阻塞進程索引表 （3 3）鏈接表：相同狀態的進程）鏈接表：相同狀態的進程PCBPCB按優先數排成一個或多按優先數排成一個或多個隊列，如就緒隊列，不同事件的阻塞隊列個隊列，如就緒隊列，不同事件的阻塞隊列第第3 3章章 處理機管理處理機管理 PCB1 ReadyPCB1 Ready就緒表就緒表 PCB2 BlockedPCB2 Blocked就緒表起始地址就緒表起始地址 PCB3 RunningPCB3 Running PCB4 BlockedPCB4 Blocked某阻

26、塞表某阻塞表 PCB5 ReadyPCB5 Ready某阻塞表起始地址某阻塞表起始地址 PCB6 ReadyPCB6 Ready第第3 3章章 處理機管理處理機管理第第3 3章章 處理機管理處理機管理3.2.2 進程的基本調度狀態及其轉換進程的基本調度狀態及其轉換 （1）運行狀態：進程正在處理機上運行的狀態，該進程）運行狀態：進程正在處理機上運行的狀態，該進程已獲得必要的資源，也獲得了處理機，用戶程序正在處理已獲得必要的資源，也獲得了處理機，用戶程序正在處理機上運行。機上運行。（2）阻塞狀態：進程等待某種事件完成（例如，等待輸）阻塞狀態：進程等待某種事件完成（例如，等待輸入入/輸出操作的完成）

27、而暫時不能運行的狀態，處于該狀輸出操作的完成）而暫時不能運行的狀態，處于該狀態的進程不能參加競爭處理機，此時，即使分配給它處理態的進程不能參加競爭處理機，此時，即使分配給它處理機，它也不能運行。機，它也不能運行。（3）就緒狀態：該進程運行所需的一切條件都得到滿足，）就緒狀態：該進程運行所需的一切條件都得到滿足，但因處理機資源個數少于進程個數，所以該進程不能運行，但因處理機資源個數少于進程個數，所以該進程不能運行，而必須等待分配處理機資源，一旦獲得處理機就立即投入而必須等待分配處理機資源，一旦獲得處理機就立即投入運行。運行。下一頁下一頁第第3 3章章 處理機管理處理機管理下一頁下一頁 第第3 3

28、章章 處理機管理處理機管理三個基本狀態之間可能轉換和轉換原因如下：三個基本狀態之間可能轉換和轉換原因如下： 就緒態就緒態運行態：當處理機空閑時，進程調度程序必將運行態：當處理機空閑時，進程調度程序必將處理機分配給一個處于就緒態的進程處理機分配給一個處于就緒態的進程 ，該進程便由就緒態轉換，該進程便由就緒態轉換為運行態。為運行態。 運行態運行態阻塞態：處于運行態進程在運行過程中需要等阻塞態：處于運行態進程在運行過程中需要等待某一事件發生后（例如因待某一事件發生后（例如因I IO O請求等待請求等待I IO O完成后），才能完成后），才能繼續運行，則該進程放棄處理機，從運行態轉換為阻塞態。繼續運行

29、，則該進程放棄處理機，從運行態轉換為阻塞態。 阻塞態阻塞態就緒態：處于阻塞態的進程，若其等待的事件就緒態：處于阻塞態的進程，若其等待的事件已經發生，于是進程由阻塞態轉換為就緒態。已經發生，于是進程由阻塞態轉換為就緒態。 運行態運行態就緒態：處于運行狀態的進程在其運行過程中，就緒態：處于運行狀態的進程在其運行過程中，因分給它的處理機時間片已用完，而不得不讓出（被搶占）處因分給它的處理機時間片已用完，而不得不讓出（被搶占）處理機，于是進程由運行態轉換為就緒態。理機，于是進程由運行態轉換為就緒態。而阻塞態而阻塞態運行態和就緒態運行態和就緒態阻塞態這二種狀態轉換阻塞態這二種狀態轉換不可能發生。不可能發

30、生。返回本節目錄返回本節目錄第第3 3章章 處理機管理處理機管理在一個多道程序設計的系統中，各進程狀態轉換會互相影在一個多道程序設計的系統中，各進程狀態轉換會互相影響。例如系統中一個運行態的進程響。例如系統中一個運行態的進程A A發生發生I/OI/O請求后要等待請求后要等待I/OI/O完成，它的狀態也由運行態轉換為阻塞態，此時進程完成，它的狀態也由運行態轉換為阻塞態，此時進程調度程序就會按照一定的算法，在就緒隊列中選一個進程調度程序就會按照一定的算法，在就緒隊列中選一個進程B B，將處理機分給它，該將處理機分給它，該B B進程的狀態也由就緒態轉換為運進程的狀態也由就緒態轉換為運行態。如一個進程

31、行態。如一個進程C C等待的事件完成，則它的狀態由阻塞等待的事件完成，則它的狀態由阻塞態轉換為就緒態，它也從阻塞隊列中抽出插入就緒隊列中。態轉換為就緒態，它也從阻塞隊列中抽出插入就緒隊列中。如進程如進程 C C從阻塞態轉換為就緒態時，有一個進程從阻塞態轉換為就緒態時，有一個進程D D在在CPUCPU上上運行。而系統采用搶占式調度算法，進程運行。而系統采用搶占式調度算法，進程C C的優先級又高的優先級又高于正在于正在CPUCPU上運行的進程上運行的進程D D的優先級，則要發行搶占調度。的優先級，則要發行搶占調度。即接下去的操作時由進程調度程序將正在運行的進程即接下去的操作時由進程調度程序將正在運

32、行的進程D D由由運行態轉換為就緒態，插入就緒隊列。運行態轉換為就緒態，插入就緒隊列。第第3 3章章 處理機管理處理機管理處于運行態進程處于運行態進程: :如系統有一個處理機，則在任何一時刻，如系統有一個處理機，則在任何一時刻，最多只有一個進程處于運行態。最多只有一個進程處于運行態。處于就緒態進程處于就緒態進程: :一般處于就緒態的進程按照一定的算法一般處于就緒態的進程按照一定的算法（如先來的進程排在前面，或采用優先權高的進程排在前（如先來的進程排在前面，或采用優先權高的進程排在前面）排成一個就緒隊列。面）排成一個就緒隊列。處于阻塞態進程處于阻塞態進程: :處于阻塞態的進程排在阻塞隊列中。由處

33、于阻塞態的進程排在阻塞隊列中。由于等待事件原因不同，阻塞隊列也按事件分成幾個隊列。于等待事件原因不同，阻塞隊列也按事件分成幾個隊列。第第3 3章章 處理機管理處理機管理例：一個只有一個處理機的系統中，例：一個只有一個處理機的系統中，OSOS的進程有運行、就緒、阻塞三的進程有運行、就緒、阻塞三個基本狀態。假如某時刻該系統中有個基本狀態。假如某時刻該系統中有1010個進程并發執行，在略去調度個進程并發執行，在略去調度程序所占用時間情況下試問：程序所占用時間情況下試問：這時刻系統中處于運行態的進程數最多有幾個？最少這時刻系統中處于運行態的進程數最多有幾個？最少有幾個？有幾個？這時刻系統中處于就緒態的

34、進程數最多有幾個？最少這時刻系統中處于就緒態的進程數最多有幾個？最少有幾個？有幾個？這時刻系統中處于阻塞態的進程數最多有幾個？最少這時刻系統中處于阻塞態的進程數最多有幾個？最少有幾個？有幾個？解：因為系統中只有一個處理機，所以某時刻處于運行態的進程數最解：因為系統中只有一個處理機，所以某時刻處于運行態的進程數最多只有一個。而最少可能為多只有一個。而最少可能為0 0，此時其它，此時其它1010個進程一定全部排在各阻個進程一定全部排在各阻塞隊列中，在就緒隊列中沒有進程。而某時刻處于就緒態的進程數最塞隊列中，在就緒隊列中沒有進程。而某時刻處于就緒態的進程數最多只有多只有9 9個，不可能出現個，不可能

35、出現1010個情況，因為一旦個情況，因為一旦CPUCPU有空，調度程序馬上有空，調度程序馬上調度，當然這是在略去調度程序調度時間時考慮。處于阻塞態的進程調度，當然這是在略去調度程序調度時間時考慮。處于阻塞態的進程數最少是數最少是0 0個。個。第第3 3章章 處理機管理處理機管理3.3 進程控制進程控制 3.3.1 原語原語 3.3.2 進程控制原語進程控制原語 返回本章首頁返回本章首頁第第3 3章章 處理機管理處理機管理3.4.1 原語原語 在操作系統中，某些被進程調用的操作，例如隊列操作、在操作系統中，某些被進程調用的操作，例如隊列操作、對信號量的操作、檢查啟動外設等操作，一旦開始執行就不對

36、信號量的操作、檢查啟動外設等操作，一旦開始執行就不能被中斷，否則就會出現操作錯誤，造成系統混亂。原語就能被中斷，否則就會出現操作錯誤，造成系統混亂。原語就是為實現這些操作而設置的。是為實現這些操作而設置的。 原語（原語（Primitive)Primitive)是由若干條指令組成，用來實現某個是由若干條指令組成，用來實現某個特定的操作，通過一段不可分割的或不可中斷的程序實現其特定的操作，通過一段不可分割的或不可中斷的程序實現其功能。功能。具有原子性：要么執行，要么不執行具有原子性：要么執行，要么不執行進程通過調用原語實現進程管理！進程通過調用原語實現進程管理！下一頁下一頁第第3 3章章 處理機管

37、理處理機管理3.3.2 進程控制原語進程控制原語1 1創建原語創建原語2 2撤消原語撤消原語3 3阻塞原語阻塞原語4 4喚醒原語喚醒原語 5. 掛起原語掛起原語 6. 激活原語激活原語返回本節目錄返回本節目錄新建完成第第3 3章章 處理機管理處理機管理Create:Create:為被建進程建立一個為被建進程建立一個PCBPCB，并初始化并初始化Procedure Create(n,S0,k0,M0,R0) Create(n,S0,k0,M0,R0)begini:= Get Internal Name(n); /n: i:= Get Internal Name(n); /n: 進程外部名進程外部

38、名Id(i) := n;Id(i) := n; /i: PCB /i: PCB內部標示號內部標示號Priority(i) := k0;Priority(i) := k0; /k0: /k0:進程優先數進程優先數Cpustate(i) := S0;Cpustate(i) := S0; /S0:CPU /S0:CPU初始狀態初始狀態Main Store(i) := M0;Main Store(i) := M0; / /主存初始占有情況主存初始占有情況Resources(i) := R0;Resources(i) := R0; / /其它資源初始占有其它資源初始占有情況情況Status(i) :=

39、Readys;Status(i) := Readys; / /進程初始狀態置為掛進程初始狀態置為掛起就緒起就緒Parent(i) := CALLER;Parent(i) := CALLER; / /父進程名父進程名Insert(RL,i);Insert(RL,i); / /把把i i插入就緒隊列插入就緒隊列end第第3 3章章 處理機管理處理機管理Destroy(n):Destroy(n):撤消指定標識符的進撤消指定標識符的進程及其所有子進程程及其所有子進程Procedure Destroy(n)Procedure Destroy(n)beginbeginSched := false;Sche

40、d := false;i:= Search Internal Name(n);i:= Search Internal Name(n); KILL(i);KILL(i);if Sched = true if Sched = true then SCHEDULER; then SCHEDULER; end end 注：注：SchedSched 標志是否需要調用處理機調度程序。標志是否需要調用處理機調度程序。第第3 3章章 處理機管理處理機管理KILL(i):KILL(i):殺死所有屬于殺死所有屬于i i的子進程并釋的子進程并釋放所有資源放所有資源 Procedure KILL(i) KILL(i)

41、 begin if Status(i) = Running Status(i) = Running then begin STOP(i); Sched := STOP(i); Sched := true end REMOVE(Queue(i),i); / REMOVE(Queue(i),i); /從進程從進程i i所在的隊列中移走進程所在的隊列中移走進程i i for all P all P progeny(i) progeny(i) do KILL(P);/ KILL(P);/殺死所有屬于殺死所有屬于i i的子進程的子進程 for all r all r progeny(i) progeny

42、(i) do /釋放進程釋放進程i i占用的所有資源占用的所有資源 RELEASE(r);RELEASE(r); RELEASE(PCB(i);RELEASE(PCB(i);end第第3 3章章 處理機管理處理機管理Suspend(n):Suspend(n):掛起外部名為掛起外部名為n n的進程的進程 Procedure Suspend(n) Suspend(n) begini:= Search Internal Name(n);i:= Search Internal Name(n);CASE Status(i)CASE Status(i)Blockeda:Status(i) := Block

43、eds;Blockeda:Status(i) := Blockeds;Readya: Status(i) := Readys; Readya: Status(i) := Readys; Running: Begin Running: Begin STOP(i); / STOP(i); /停止該進程停止該進程i i的運行的運行 SCHEDULER; /CPUSCHEDULER; /CPU調度程序調度程序 endendend第第3 3章章 處理機管理處理機管理Resume(n):Resume(n):激活外部名為激活外部名為n n的已的已掛起進程掛起進程Procedure Resume(n) Res

44、ume(n)begini:= Search Internal Name(n);i:= Search Internal Name(n);if Status(i) = Readys Status(i) = Readys then begin Status(i) = Readya; Status(i) = Readya; SCHEDULER; SCHEDULER; end else Status(i) = Blockeda; Status(i) = Blockeda;end第第3 3章章 處理機管理處理機管理3.4 進程調度進程調度 3.4.1 進程調度的基本概念進程調度的基本概念 3.4.2進程調

45、度進程調度所用的數據結構所用的數據結構3.4.3 進程調度方式進程調度方式 3.4.4進程調度算法進程調度算法 返回本章首頁返回本章首頁第第3 3章章 處理機管理處理機管理3.4.1 進程調度的基本概念進程調度的基本概念 進程調度程序的職能：進程調度程序的職能：（1）記錄系統中所有進程的有關情況。）記錄系統中所有進程的有關情況。 （2）確定分配處理機的原則。）確定分配處理機的原則。 （3）分配處理機給進程。）分配處理機給進程。 （4）從進程收回處理機。）從進程收回處理機。 返回本節目錄返回本節目錄3.4.2 進程調度所用的主要數據結構進程調度所用的主要數據結構 第第3 3章章 處理機管理處理機

46、管理剝奪式剝奪式/ /搶占方式（搶占方式（Preemptive modePreemptive mode） 剝奪式調度是指當系統按照某種原則發現一個比剝奪式調度是指當系統按照某種原則發現一個比正在運行的進程更合適、更應該占用正在運行的進程更合適、更應該占用CPUCPU的進程時，的進程時，系統將強迫處于運行狀態的進程將系統將強迫處于運行狀態的進程將CPUCPU的使用權交的使用權交給這個更適合的進程。常見的剝奪原則有給這個更適合的進程。常見的剝奪原則有優先權優先權原則、短進程優先原則和時間片原則原則、短進程優先原則和時間片原則。采用剝奪。采用剝奪式調度的系統能夠及時處理緊急事件，它反映出式調度的系統

47、能夠及時處理緊急事件，它反映出了進程的優先級特征，但這勢必會帶來較大的系了進程的優先級特征，但這勢必會帶來較大的系統開銷，調度算法也會相對復雜一些。統開銷，調度算法也會相對復雜一些。3.4.3 進程調度的方式進程調度的方式第第3 3章章 處理機管理處理機管理非剝奪式非剝奪式/ /非搶占方式非搶占方式 采用這種調度方式時，一旦把處理機分配給某采用這種調度方式時，一旦把處理機分配給某進程后，便讓進程一直執行，直到該進程完成或發進程后，便讓進程一直執行，直到該進程完成或發生某事件而被阻塞時，才把處理機分配給其它進程，生某事件而被阻塞時，才把處理機分配給其它進程，決不允許某進程搶占已經分配出去的處理機

48、。決不允許某進程搶占已經分配出去的處理機。 這種調度方式算法簡單，系統開銷也較小，但它這種調度方式算法簡單，系統開銷也較小，但它不能反映出進程的優先級特征。不能反映出進程的優先級特征。 第第3 3章章 處理機管理處理機管理 3.4.4 進程調度算法進程調度算法1先來先服務先來先服務First-Come-First-ServedFirst-Come-First-Served （FCFS） 這種調度算法按照進程進入就緒隊列的先后順序這種調度算法按照進程進入就緒隊列的先后順序來調度進程，到達得越早，其優先數越高。獲得來調度進程，到達得越早，其優先數越高。獲得處理機的進程，未遇到其他情況時，一直運行下

49、處理機的進程，未遇到其他情況時，一直運行下去，系統只需具備一個先進先出的隊列，在管理去，系統只需具備一個先進先出的隊列，在管理優先數的就緒隊列時，這種方法是一種最常見策優先數的就緒隊列時，這種方法是一種最常見策略，并且在沒有其他信息時，也是一種最合理的略，并且在沒有其他信息時，也是一種最合理的策略。策略。下一頁下一頁第第3 3章章 處理機管理處理機管理2輪轉調度輪轉調度 先來先服務的一個重要變形，就是輪轉規則。輪轉調先來先服務的一個重要變形，就是輪轉規則。輪轉調度算法是系統把所有就緒進程按先后次序排隊，處理機總度算法是系統把所有就緒進程按先后次序排隊，處理機總是優先分配給就緒隊列中的第一個就緒

50、進程，并分配它一是優先分配給就緒隊列中的第一個就緒進程，并分配它一個固定的時間片（如個固定的時間片（如100毫秒）。當該運行進程用完規定毫秒）。當該運行進程用完規定的時間片時，被迫釋放處理機給下一個處于就緒隊列中的的時間片時，被迫釋放處理機給下一個處于就緒隊列中的第一個進程，分給這個進程相同的時間片，每個運行完時第一個進程，分給這個進程相同的時間片，每個運行完時間片的進程，當未遇到任何阻塞時，就回到就緒隊列的尾間片的進程，當未遇到任何阻塞時，就回到就緒隊列的尾部，并等待下次轉到它時再投入運行。于是，只要是處于部，并等待下次轉到它時再投入運行。于是，只要是處于就緒隊列中的進程，按此種算法遲早總可

51、以分得處理機投就緒隊列中的進程，按此種算法遲早總可以分得處理機投入運行。入運行。下一頁下一頁第第3 3章章 處理機管理處理機管理3分級輪轉法分級輪轉法 所謂分級輪轉法就是將先前的一個就緒隊列，所謂分級輪轉法就是將先前的一個就緒隊列，根據進程的優先數不同劃分兩個或兩個以上的就緒根據進程的優先數不同劃分兩個或兩個以上的就緒隊列，并賦給每個隊列不同的優先數。以兩個就緒隊列，并賦給每個隊列不同的優先數。以兩個就緒隊列為例，一個具有較高優先數，另一個具有較低隊列為例，一個具有較高優先數，另一個具有較低優先數，前者稱為前臺隊列，后者稱為后臺隊列。優先數，前者稱為前臺隊列，后者稱為后臺隊列。 下一頁下一頁第

52、第3 3章章 處理機管理處理機管理 例如前后臺系統可以建立兩個就緒隊列，批處理作業所例如前后臺系統可以建立兩個就緒隊列，批處理作業所建立進程進入后臺就緒隊列；交互型作業所建立的進程進入建立進程進入后臺就緒隊列；交互型作業所建立的進程進入前臺就緒隊列。前臺采用時間片輪轉算法，進程按前臺就緒隊列。前臺采用時間片輪轉算法，進程按FCFSFCFS等策等策略排序，后臺采用優先權高優先的調度算法或者短作業優先略排序，后臺采用優先權高優先的調度算法或者短作業優先的調度算法。的調度算法。 對多級就緒隊列調度策略有兩種，一種是各就緒隊列按對多級就緒隊列調度策略有兩種，一種是各就緒隊列按進程性質賦予不同的優先權，

53、優先權高的就緒隊列的進程優進程性質賦予不同的優先權，優先權高的就緒隊列的進程優先被調度，例如上例中前臺就緒隊列的優先權比后臺就緒隊先被調度，例如上例中前臺就緒隊列的優先權比后臺就緒隊列的優先權高，所以前臺隊列中的進程優先被調度。而只有列的優先權高，所以前臺隊列中的進程優先被調度。而只有當優先權高的就緒隊列空時，方才調度優先權其次的就緒隊當優先權高的就緒隊列空時，方才調度優先權其次的就緒隊列進程，在上例中只有前臺隊列空時，才調度后臺就緒隊列。列進程，在上例中只有前臺隊列空時，才調度后臺就緒隊列。這樣，只有較高優先權的就緒隊列都空時才調度最低優先權這樣，只有較高優先權的就緒隊列都空時才調度最低優先

54、權就緒隊列的進程。就緒隊列的進程。第第3 3章章 處理機管理處理機管理4優先數法優先數法 根據已占有處理根據已占有處理 機的進程是否可被剝奪而分為優先占機的進程是否可被剝奪而分為優先占有法和優先剝奪法兩種有法和優先剝奪法兩種 。優先占有法的原理優先占有法的原理是：一旦某個最高優先數的就緒進程分是：一旦某個最高優先數的就緒進程分得處理機之后，只要不是其自身的原因被阻塞（如要求得處理機之后，只要不是其自身的原因被阻塞（如要求I/O操作）而不能繼續運行時，就一直運行下去，直至運操作）而不能繼續運行時，就一直運行下去，直至運行結束。行結束。優先剝奪法的原理優先剝奪法的原理是：當一個正在運行的進程即使其

55、時間是：當一個正在運行的進程即使其時間片未用完，無論什么時候，只要就緒隊列中有一個比它的片未用完，無論什么時候，只要就緒隊列中有一個比它的優先數高的進程，優先數高的進程就可以取代以前正在運優先數高的進程，優先數高的進程就可以取代以前正在運行的進程，投入運行行的進程，投入運行 。下一頁下一頁第第3 3章章 處理機管理處理機管理確定進程的優先數通常應考慮如下確定進程的優先數通常應考慮如下幾個因素：幾個因素： （1）進程類型。）進程類型。 （2）運行時間。）運行時間。 （3）作業的優先數。）作業的優先數。 （4）動態優先數。）動態優先數。 返回本節目錄返回本節目錄第第3 3章章 處理機管理處理機管理

56、 在多道程序的環境中，系統中的多個進程可以并發在多道程序的環境中，系統中的多個進程可以并發執行，同時它們又要共享系統中的資源，這些資源有執行，同時它們又要共享系統中的資源，這些資源有些是可共享使用的，如磁盤，有些是以獨占方式使用些是可共享使用的，如磁盤，有些是以獨占方式使用的，如打印機。由此將會引起一系列的矛盾，產生錯的，如打印機。由此將會引起一系列的矛盾，產生錯綜復雜的相互制約的關系。綜復雜的相互制約的關系。 產生這種錯綜復雜的相互制約關系的原因有二：產生這種錯綜復雜的相互制約關系的原因有二： 資源共享資源共享間接制約關系間接制約關系 進程合作進程合作直接制約關系直接制約關系3.5 進程間的

57、同步和互斥進程間的同步和互斥 第第3 3章章 處理機管理處理機管理1.1. 進程間的同步進程間的同步 2. 進程間的互斥進程間的互斥 3.5.1 進程間的同步和互斥進程間的同步和互斥 第第3 3章章 處理機管理處理機管理臨界資源臨界資源：某段時間僅允許一個進程使用的資源稱為臨界：某段時間僅允許一個進程使用的資源稱為臨界資源。資源。宿舍電話宿舍電話打印機打印機 電話和打印機都屬于臨界資源。除此之外，還有內存變電話和打印機都屬于臨界資源。除此之外，還有內存變量、指針、數組等等也是臨界資源。量、指針、數組等等也是臨界資源。 幾個進程若共享同一臨界資源，它們必須以幾個進程若共享同一臨界資源，它們必須以

58、互斥互斥的方式的方式使用這個臨界資源，即當一個進程正在使用臨界資源且尚使用這個臨界資源，即當一個進程正在使用臨界資源且尚未使用完畢時，則其他進程必須推遲對該資源的進一步操未使用完畢時，則其他進程必須推遲對該資源的進一步操作，作，3.5.1 進程間的同步和互斥進程間的同步和互斥 第第3 3章章 處理機管理處理機管理臨界區臨界區( (critical section) ) 每個進程中訪問臨界資源的那段程序段稱為每個進程中訪問臨界資源的那段程序段稱為相對于臨界資源的臨界區。相對于臨界資源的臨界區。訪問臨界資源的進程互斥訪問臨界資源的進程互斥的進入各自的臨界區。的進入各自的臨界區。第第3 3章章 處理

59、機管理處理機管理a := a -1 print (a)a := a +1 print (a)P1互斥互斥P2互斥互斥If a 0then a := a +1else a:= a-1P3互斥互斥第第3 3章章 處理機管理處理機管理程 序 段1程 序 段2程 序 段n共 享 變 量第第3 3章章 處理機管理處理機管理 這種方法使用了一個物理實體，稱為鎖，用這種方法使用了一個物理實體，稱為鎖，用 W 來表示，鎖有來表示，鎖有兩種狀態，兩種狀態，W=0 表示鎖已打開；表示鎖已打開；W=1表示鎖被關閉。表示鎖被關閉。加鎖原語用加鎖原語用LOCK(W)表示，其操作為：表示，其操作為：測試測試W，若若W=1

60、，表示資源正在使用，繼續反復測試；若表示資源正在使用，繼續反復測試；若W=0，置置W=1(加鎖加鎖)。加鎖原語用加鎖原語用LOCK(W)可描述為可描述為L：if W=1 then go to L else W：=1；開鎖原語用開鎖原語用UNLOCK(W)表示，可描述為表示，可描述為 W：=0； 3. 實現臨界區互斥的鎖操作法實現臨界區互斥的鎖操作法 第第3 3章章 處理機管理處理機管理兩個進程兩個進程P1P1、P2P2使用如下程序實施進程的互斥：使用如下程序實施進程的互斥： 進程進程P1 P1 進程進程P2P2 LOCK(W) LOCK(W) LOCK(W) LOCK(W) S S1/1/進入