數學與計算機學院2023/2/6操作系統第三章進程管理一數學與計算機學院

硬件教研室曾新數學與計算機學院2023/2/6本章學習目標進程的概念進程的實體、狀態及狀態的演變進程的控制與調度進程之間的關系協調進程的通信死鎖問題及解決數學與計算機學院2023/2/6一、引言：進程的初步引入現代操作系統的特點：程序的并發執行、系統所擁有的資源被共享、系統的用戶隨機地使用。操作系統的重要任務之一是使用戶充分、有效地利用系統資源。采用一個什么樣的概念，來描述計算機程序的執行過程和作為資源分配的基本單位，才能充分反映操作系統的執行并發、資源共享及用戶隨機的特點呢？這個概念就是進程。數學與計算機學院2023/2/6一、引言：處理機管理處理機管理是操作系統的基本管理功能之一，它所關心的是處理機的分配問題。也就是說把CPU（中央處理機）的使用權分給某個程序，通常把這個正準備進入內存的程序稱為作業，當這個作業進入內存后我們把它稱為進程。處理機管理分為作業管理和進程管理兩個階段來實現。數學與計算機學院2023/2/6一、引言：進程管理的功能。進程管理的主要功能是把處理機分配給進程以及協調各個進程之間的相互關系。它是由進程調度程序和進程控制（控制進程狀態轉換）程序這兩部分內容組成的。進程是操作系統的五大功能之一。1、高級（宏）處理機管理即作業調度，確定系統中哪些作業將獲得CPU；2、低級（微）處理機管理即進程調度，確定系統中哪個作業中的哪個進程將獲得CPU。

數學與計算機學院2023/2/6二、進程的引入：程序引入進程的關鍵是資源共享，高效管理共享資源是操作系統的重要內容。1、程序的順序執行及其特性程序是一個在時間上按嚴格次序前后相繼的操作序列，是一個靜態的概念。程序體現了編程人員要求計算機完成所要求功能時所應該采取的順序步驟。數學與計算機學院2023/2/6二、進程的引入：串行執行上圖表示每次只能調度一個作業進行操作的情況。輸入、計算、打印輸出工作只能串行執行，因而可以把程序的執行看做一系列狀態轉換的過程，即每執行一個操作，系統就會從一個狀態轉換成另外一個狀態。數學與計算機學院2023/2/6二、進程的引入：程序順序執行程序的順序執行：一個具有獨立功能的程序獨占處理機直至最終結束的過程。從上例可以看出，程序的順序執行有一下特點：

1、順序性2、資源獨占性3、結果的無關性4、可再現性數學與計算機學院2023/2/6二、進程的引入：多道程序系統在許多情況下，需要計算機能夠同時處理多個具有獨立功能的程序。批處理系統、分時系統、實時系統以及網絡與分布式系統等都是這樣的系統。那么多道程序系統中程序執行的特點如下：1、獨立性2、隨機性3、資源共享數學與計算機學院2023/2/6二、進程的引入：單道和多道數學與計算機學院2023/2/6二、進程的引入：資源的共享操作系統是用來實現對計算機資源進行管理的一個大型系統程序，其基本特征之一就是資源共享。所謂資源共享，就是指計算機中并發執行的多個程序交替使用計算機硬件和軟件資源。資源共享將導致對進程執行速度的制約。數學與計算機學院2023/2/6二、進程的引入：程序并發及其特性所謂并發執行，是為了增強計算機系統的處理能力和提高資源利用率所采取的一種同時操作技術。程序的并發執行可進一步分為兩種：第一種是多道程序系統的程序執行環境變化所引起的多道程序的并發執行；第二種并發執行是在某道程序的幾個程序段中（例如幾個程序），包含著一部分可以同時執行或順序顛倒執行的代碼。數學與計算機學院2023/2/6二、進程的引入：多道程序并發由于資源的有限性，多道程序的并發執行總是伴隨著資源的共享與競爭。從而制約各道程序的執行速度。而無法作到在微觀上，也就是在指令級上的同時執行。因此，盡管多道程序的并發執行在宏觀上是同時進行的，但在微觀上仍是順序執行的。數學與計算機學院2023/2/6二、進程的引入：某道程序的多個程序段并發在某道程序的幾個程序段中（例如幾個程序），包含著一部分可以同時執行或順序顛倒執行的代碼。例如語句：

read(a)；

read(b)；它們既可以同時執行，也可顛倒次序執行。對于這樣的語句，同時執行不會改變順序程序所具有的邏輯性質。因此，可以采用并發執行來充分利用系統資源以提高計算機的處理能力。數學與計算機學院2023/2/6二、進程的引入：并發執行總結程序的并發執行可總結為：一組在邏輯上互相獨立的程序或程序段在執行過程中，其執行時間在客觀上互相重疊，即一個程序段的執行尚未結束，另一個程序段的執行已經開始的一種執行方式。程序的并發執行不同于程序的并行執行。程序的并行執行是指一組程序按獨立的、異步的速度執行。并行執行不等于時間上的重疊。數學與計算機學院2023/2/6二、進程的引入：并發執行的條件并發執行過程描述為：S0 Cobegin P1；P2；...Pn CoendSn 1966年Bernstein提出了兩相鄰語句S1，S2可以并發執行的條件： 將程序中任一語句Si劃分為兩個變量的集合R(Si)和W(Si)。R(Si)={a1a2…am}，aj(j=1，…，m) 是語句Si在執行期間必須對其進行讀寫的變量；W(Si)={b1b2…bn}，bj(j=1，…，n)

是語句Si在執行期間必須對其進行修改、訪問的變量；數學與計算機學院2023/2/6二、進程的引入：并發執行的條件如果對于語句S1和S2，有 ①R(S1)∩W(S2)={∮}， ②W(S1)∩R(S2)={∮}， ③W(S1)∩W(S2)={∮}

同時成立，則語句S1和S2是可以并發執行的。如果并發執行的各程序段中語句或指令滿足上述Bernstein的三個條件，則認為并發執行不會對執行結果的封閉性和可再現性產生影響。數學與計算機學院2023/2/6二、進程的引入：例題分析如果并發執行的程序段不按照特定的規則和方法進行資源共享和競爭，則其執行結果將不可避免地失去封閉性和可再現性。數學與計算機學院2023/2/6二、進程的引入：例題分析proceduregetaddr(top)beginlocalrr←(top)top←top-1return(r)endprocedurereladdr(blk)begintop←top+1(top)←blkendgetaddr(top)從給定的top所指棧中取出相應的內存數據塊地址，而reladdr(blk)則將內存數據塊地址blk放入堆棧S中數學與計算機學院2023/2/6二、進程的引入上例中的程序段并發執行出現錯誤結果是由于兩程序段共享資源堆棧S，從而使得執行結果受執行速度影響。一般情況下，并發執行的各程序段如果共享軟、硬件資源，都會造成其執行結果受執行速度影響的局面。

為了控制和協調各程序段執行過程中的軟、硬件資源的共享和競爭，顯然，必須應該有一個描述各程序段執行過程和共享資源的基本單位。數學與計算機學院2023/2/6二、進程的引入現代操作系統的重要特點是程序的并發執行，由于程序的順序性、靜態性以及孤立性，用程序段作為描述其執行過程和共享資源的基本單位既增加操作系統設計和實現的復雜性，也無法反映操作系統所應該具有的程序段執行的并發性、用戶隨機性，以及資源共享等特征。因而需要有一個能描述程序的執行過程且能用來共享資源的基本單位。這個基本單位被稱為進程（或任務）。數學與計算機學院2023/2/6二、進程的引入：多道程序并發為了合理利用系統資源，更好地發揮各種資源的效益，使各種物理設備之間的時間性限制條件減少到最低限度，最大限度地提高系統的效率，因而引出了多道程序方法。其實質是減少程序的順序性，提高系統的并行性。多道程序并發執行的特點：1、資源分配的動態性2、程序執行的間斷性3、程序間的通訊4、程序間的同步和互斥數學與計算機學院2023/2/6二、進程的引入：順序與并發的比較順序執行并發執行程序順序執行間斷執行，多個程序各自在“走走停停”中進行程序具有封閉性程序失去封閉性獨占資源共享資源可再現性失去可再現性有直接和間接的相互制約數學與計算機學院2023/2/6二、進程的引入：進程的定義進程是現代操作系統的一個基本概念，是并發程序出現后出現的一個重要概念，它是指程序在一個數據集合上運行的過程，是系統進行資源分配和調度運行的一個獨立單位，有時也稱為活動、路徑或任務。數學與計算機學院2023/2/6二、進程的引入：進程的定義一個具有獨立功能的程序對某個數據集在處理機上的執行過程和分配資源的基本單位。主要注重進程是一個動態的執行過程這一概念。在傳統的操作系統設計中，進程既是基本的分配單元，也是基本的執行單元。這里，程序指一組操作序列，而數據集則是接受程序規定操作的一組存儲單元的內容。數學與計算機學院2023/2/6二、進程的引入：進程與程序的聯系和區別1、進程是一個動態概念，而程序則是一個靜態概念。程序是指令的有序集合，沒有任何執行的含義。而進程則強調執行過程，它動態地被創建，并被調度執行后消亡。2、進程具有并行特征，而程序沒有。由進程的定義可知，進程具有并行特征的兩個方面，即獨立性和異步性。也就是說，在不考慮資源共享的情況下，各進程的執行是獨立的，執行速度是異步的。顯然，由于程序不反映執行過程，所以不具有并行特征。數學與計算機學院2023/2/6二、進程的引入：進程與程序的聯系和區別3、進程是競爭計算機系統資源的基本單位，從而其并行性受到系統自己的制約，只有進程才可能在不同的時刻處于幾種不同的狀態，即等待、就緒、運行。

4、不同的進程可以包含同一程序，只要該程序所對應的數據集不同。同一程序運行于若干不同的數據集合上時，它將屬于若干個不同的進程，或者說，兩個不同的進程可包含相同的程序；

5、從微觀上看，進程是輪換地占有處理機而運行的，從宏觀上看，進程是并發地運行的。數學與計算機學院2023/2/6二、進程的引入：作業與進程的聯系和區別作業是用戶需要計算機完成某項任務時要求計算機所作工作的集合。進程是已提交完畢程序的執行過程的描述，是資源分配的基本單位。作業是用戶向計算機提交任務的任務實體。在用戶向計算機提交作業之后，系統將它放入外存中的作業等待隊列中等待執行。而進程則是完成用戶任務的執行實體，是向系統申請分配資源的基本單位。任一進程，只要它被創建，總有相應的部分存在于內存中。

一個作業可由多個進程組成。且必須至少由一個進程組成，但反過來不成立。作業的概念主要用在批處理系統中。而進程的概念則用在幾乎所有的多道系統中。數學與計算機學院2023/2/6二、進程的引入：進程的5個基本特征1、動態性：進程是程序在并發系統的一次執行，一個進程有一個從產生到消失的生命期；2、并發性：正是為了描述程序在并發系統內執行的動態特征才引入了進程，沒有并發就沒有進程；3、獨立性：每個進程的程序都是相對獨立的順序程序，可以按自己的方向和速度獨立地向前推進；4、制約性：進程之間的相互制約，主要表現在互斥地使用資源和相關進程之間必要的同步和通訊；5、結構性：進程=PCB（進程控制塊）+程序+數據集合。數學與計算機學院2023/2/6二、進程的引入引入進程的目的是為了描述程序動態執行時的活動規律和狀態變化。進程和程序是既有聯系又有區別的兩個概念，它們的主要區別如下：1、程序是指令的有序集合，是一個靜態的概念，而進程是程序在CPU上的一次執行過程，它是一個動態概念。2、程序的存在是永久的。而進程則是有生命期的，它因創建而產生，因調度而執行，因得不到資源而暫停，因撤銷而消亡。3、程序僅是指令的有序集合，而進程則由程序、數據和進程控制塊組成。4、進程和程序無一一對應關系，即同一個程序同時運行于若干不同的數據集合上，它將屬于若干個不同的進程。而一個進程可以執行多個程序。5、進程可以生成其他進程，而程序不能生成新的程序。數學與計算機學院2023/2/6二、進程的引入：進程的分類及區別進程通常分為兩類，一類是系統進程，另一類是用戶進程。它們的區別是：1、系統進程是操作系統用來管理系統資源并行活動的并發軟件。2、系統進程之間的關系由操作系統自己負責。3、系統進程直接管理有關的軟、硬設備的活動。4、在進程調度中，系統進程的優先級高于用戶進程。數學與計算機學院2023/2/6二、進程的引入：進程狀態圖在進程的生命期內，一個進程至少具有三種基本狀態，它們是：執行狀態、等待狀態和就緒狀態。數學與計算機學院2023/2/6二、進程的引入：進程狀態的解釋1、運行狀態：進程正在處理機上運行的狀態，該進程已獲得必要的資源，也獲得了處理機，用戶程序正在處理機上運行。2、等待狀態：進程等待某種事件完成（例如，等待輸入/輸出操作的完成）而暫時不能運行的狀態，處于該狀態的進程不能參加競爭處理機，此時，即使分配給它處理機，它也不能運行。3、就緒狀態：該進程運行所需的一切條件都得到滿足，但因處理機資源個數少于進程個數，所以該進程不能運行，而必須等待分配處理機資源，一旦獲得處理機就立即投入運行。數學與計算機學院2023/2/6二、進程的引入：進程狀態的轉換1、CPU調度（低級調度）：一個進程到CPU上運行，該進程就從就緒狀態變為運行狀態；與此同時，原運行進程從運行狀態變為就緒狀態。因此，這兩種狀態變化是同時發生的。2、進程在運行過程中需要等待某一事件，例如，等待分配某一資源，等待I/O操作完成等。一個進程在需要等待某一事件時主動退出CPU，并使自己處于阻塞狀態（等待狀態），引起狀態變化。3、如果進程所等待的事件發生了變化，例如，一次I/O完成了，于是進程便被解除阻塞狀態，變為就緒狀態。一個具體的進程在任何一個指定的時刻必須而且只能處于一種狀態。

數學與計算機學院2023/2/61、進程之間的狀態轉換并非都是可逆的，進程既不能從等待變為運行，也不能從就緒變為等待。2、進程之間的狀態轉換并非都是主動的，在很多情況下都是“它動的”。事實上，只有運行到等待的轉換是進程的主動行為（主動調用調度管理程序），其它都是它動的，例如，從執行到就緒，通常是時鐘中斷引起的，從等待到就緒，是一個進程把另一個進程喚醒。就緒狀態變化到運行狀態。運行狀態變化到就緒狀態。運行狀態變化到等待狀態。等待狀態變化到就緒狀態。二、進程的引入：進程狀態的轉換數學與計算機學院2023/2/6二、進程的引入：掛起與激活在具有掛起和激活的系統中，又增加了兩種基本的進程狀態：靜止就緒和靜止阻塞。靜止就緒：它是活動就緒進程由其自身或其他進程調用掛起原語而進入的一種狀態。處于靜止就緒狀態的進程沒有資格爭用CPU，只有其他進程調用激活原語將其激活才行。靜止阻塞：它是活動等待進程由其自身或其他進程調用掛起原語而進入的一種狀態。處于靜止阻塞狀態的進程，在其掛起期間并不影響其等待事件的發生。數學與計算機學院2023/2/6二、進程的引入：掛起與激活示意圖數學與計算機學院2023/2/6二、進程的引入：進程的描述及PCB進程的靜態描述由三部分組成：進程控制塊PCB，有關程序段和該程序段對其進行操作的數據結構集。進程控制塊（pcb）包含了有關進程的描述信息、控制信息以及資源信息，是進程動態特征的集中反映。系統根據PCB感知進程的存在和通過PCB中所包含的各項變量的變化，掌握進程所處的狀態以達到控制進程活動的目的。由于進程的PCB是系統感知進程的唯一實體，因此，在幾乎所有的多道操作系統中，一個進程的PCB結構都是全部或部分常駐內存的。數學與計算機學院2023/2/6二、進程的引入：進程的描述及PCB進程的程序部分描述進程所要完成的功能。而數據結構集是程序在執行時必不可少的工作區和操作對象。這兩部分是進程完成所需功能的物質基礎。由于進程的這兩部分內容與控制進程的執行及完成進程功能直接有關，因而，在大部分多道操作系統中，這兩部分內容放在外存中，直到該進程執行時再調入內存。數學與計算機學院2023/2/6二、進程的引入：進程的結構進程名當前狀態優先數現場保留區指示處于同一狀態進程的鏈指針資源清單進程起始地址家族關系其他PCB程序段私有數