操作系統(tǒng)課件第三章一

數(shù)學與計算機學院2023/2/6操作系統(tǒng)第三章進程管理一數(shù)學與計算機學院

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

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

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

read(a)；

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

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

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

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

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

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

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

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