操作系統教程(第二章)

第二章進程及處理機管理§2.1進程的提出§2.2進程的定義和特征§2.3進程狀態(tài)和進程控制塊§2.4線程的基本概念§2.5進程控制§2.6進程同步§2.7經典進程同步問題§2.8進程的通信§2.9處理機調度§2.10死鎖第二章進程及處理機管理第二章進程及處理機管理——§2.1進程的提出一、程序的執(zhí)行1前趨圖前趨圖指的是有向無循環(huán)圖。在這里，我們用前趨圖表示系統在某個時間完成工作的流程。在圖中，結點表示一條語句、一個程序段落或一個程序。有向邊表示結點之間的偏序或前趨關系。前趨圖是無循環(huán)的圖。必然有一個結點沒有前趨，一個結點沒有后繼

第二章進程及處理機管理——§2.1進程的提出一、程序的執(zhí)行2程序順序執(zhí)行（1）順序性：（2）封閉型（3）程序的執(zhí)行結果與速度和時間沒有關系。（4）可再現性3程序并發(fā)執(zhí)行（1）間斷性（2）失去封閉性（3）不可再現性（4）．通信性

（5）．程序與執(zhí)行過程不再一一對應二、進程的引入資源分配的單位不再是程序程序與執(zhí)行過程不再是一一對應一個程序的多個運行過程中資源分配第二章進程及處理機管理——

§2.2進程的定義和特征一、進程的定義1進程是指程序的一次執(zhí)行過程。2進程定義為一個數據結構和能在其上進行操作。3進程是程序在一個數據集合上運行的過程。4進程是系統資源進行分配和調度的一個獨立單位。5指可并發(fā)執(zhí)行的程序，在一個數據集合上運行過程。進程是一個正在執(zhí)行中的程序

（不正確的一個意思，但可以作為一種今后學習上的參考解釋）第二章進程及處理機管理——

§2.2進程的定義和特征二、進程的特征1動態(tài)性：指的是程序的一次執(zhí)行過程，是一個動態(tài)的概念，而程序只是指的指令序列的集合，沒有運行（運動）的含義。因此，程序是靜態(tài)的。2并發(fā)性：指進程之間是可以并發(fā)執(zhí)行的。3獨立性：指進程是一個獨立運行的、獨立分配資源的單位。4異步性：進程之間按各自的、不可預知的速度向前推進。5結構特征：進程是有一定的組成成分，而且有一定的結構形式，簡單地說進程是由程序+數據+進程控制塊組成的，而進程控制塊是使計算機系統識別該進程、運行該進程的一個唯一標志，這在后面我們將要提到。第二章進程及處理機管理——

§2.2進程的定義和特征進程樹在這里，我們還應該注意到，進程是一個程序的運行過程，這其中會包含兩種情況：一是該進程是系統要求執(zhí)行的。另一個是該進程所包含的程序是另一個程序的子程序，該進程的執(zhí)行是另一個程序要求執(zhí)行的。所以，在系統中，進程和進程之間是有一定關聯的。這種關聯的形式我們可以用進程樹來表示。第二章進程及處理機管理——

§2.3進程的狀態(tài)和進程控制塊一、進程的狀態(tài)1基本狀態(tài)（1）執(zhí)行狀態(tài)進程已經獲得了處理機（CPU），其程序正在運行。（2）阻塞狀態(tài)（等待狀態(tài)）正在執(zhí)行的進程，由于發(fā)生某事件而暫時無法執(zhí)行時，而放棄處理進入暫停狀態(tài)。（3）就緒狀態(tài)已經完成暫停，在沒有得到CPU前所處的狀態(tài)2擴充狀態(tài)（1）執(zhí)行狀態(tài)（2）活動阻塞狀態(tài)（3）靜止阻塞狀態(tài)（4）活動就緒狀態(tài)（5）靜止就緒狀態(tài)第二章進程及處理機管理——

§2.3進程的狀態(tài)和進程控制塊二、進程控制塊1進程控制塊進程控制塊其英文名稱為ProcessControlBlock，簡稱PCB。是使計算機系統感知進程存在的唯一依據，是描述和控制進程的執(zhí)行過程的一個數據結構。2進程控制塊的結構（1）．進程標識符（進程內部名稱）（2）．現行狀態(tài)（3）．現場保留區(qū)（4）．程序和數據地址（5）．互斥與同步結構：（6）．進程通信機制：（7）．優(yōu)先級（8）．資源清單（9）．鏈接字（隊列指針）（10）．家族聯系第二章進程及處理機管理——

§2.3進程的狀態(tài)和進程控制塊三、進程控制塊組織結構1鏈接方式2索引方式第二章進程及處理機管理——§2.4線程一、線程的引入進程擁有資源在進程運行過程中，資源需要被處理進程整體的過程可以由調度、控制、資源處理等組成分離后，將調度單獨完成二、線程的概念線程是進程中的一個實體，是被系統獨立調度和分派的基本單位。三、線程與進程（見書P53頁）1調度

2并發(fā)性

3擁有資源

4系統開銷

第二章進程及處理機管理——

§2.5進程控制進程的控制指的是進程的創(chuàng)建和撤消，以及實現進程的狀態(tài)轉換。進程控制一般是由操作系統的內核完成。內核（Kernel）是指基于硬件的第一層軟件，完成操作系統的基本功能的進程集合。是由原語設計的原語（Primitive）是指機器指令的延伸，是由若干條機器指令構成的，不可中斷的程序代碼。實現對進程的控制在多數系統中都提供了六個原語實現的。第二章進程及處理機管理——

§2.5進程控制創(chuàng)建、撤銷、激活、阻塞、喚醒、掛起第二章進程及處理機管理——

§2.5進程控制一、進程的創(chuàng)建原語（CreatePrimitive） 1調用創(chuàng)建原語的情況用戶登錄程序執(zhí)行用戶提出請求而為之提供的服務應用請求 2創(chuàng)建原語描述第二章進程及處理機管理——

§2.5進程控制二、進程的撤消原語（Destroy

Primitive） 1引起進程撤消的情況正常結束異常結束外界干擾 2撤消原語描述第二章進程及處理機管理——

§2.5進程控制三、進程的阻塞原語（Block

Primitive） 1引起進程阻塞的原因

（1）請求系統服務，但沒有得到及時的響應（2）啟動某種Ｉ／Ｏ （3）新數據還沒有到來（4）沒有新的工作

2阻塞原語描述第二章進程及處理機管理——

§2.5進程控制四、進程的喚醒原語（Wakeup

Primitive） 1、某進程所請求的事件完成，從阻塞狀態(tài)到就緒狀態(tài)

2、喚醒原語描述第二章進程及處理機管理——

§2.5進程控制五、進程的掛起原語（Suspend

Primitive） 1當需要對正在運行的程序進行調試時，通過掛起原語使其變成靜止的某一種狀態(tài)

2掛起原語描述第二章進程及處理機管理——

§2.5進程控制六、進程的激活原語（Active

Primitive） 1當進程調試完成后，通過激活原語將其投入參與運行

2激活原語描述第二章進程及處理機管理——

§2.6進程同步進程同步是由于進程之間的并發(fā)執(zhí)行造成的一種相互制約、相互協調，按一定次序進行的現象根據相互制約的不同形式，可以分為兩種形式的同步：互斥同步和依賴同步。簡稱互斥和同步第二章進程及處理機管理——

§2.6進程同步一、基本概念1臨界資源（CriticalResource）臨界資源指的是計算機系統中每次只允許一個進程訪問的資源。計算機系統中大部分資源屬于臨界資源。顯示器？鍵盤？2臨界區(qū)（Criticalsection）臨界區(qū)指的是在一個進程中訪問臨界資源的那段代碼。3對于臨界資源的使用兩個或兩個以上進程不能同時進入自己的臨界區(qū)，訪問臨界資源。這就要求有一個同步機制來制約各個進程的執(zhí)行，這個同步機制應該遵循以下四條準則：空閑讓進。②忙則等待，③有限等待。④讓權等待。第二章進程及處理機管理——

§2.6進程同步二、互斥同步定義指的是兩個或兩個以上的進程在共享某一臨界資源時，所采取的一種協調制約形式，即互相排斥地使用臨界資源。實現方法：硬件機制信號量機制管程第二章進程及處理機管理——

§2.6進程同步（互斥）硬件機制利用計算機系統中提供的硬件操作指令來實現。主要有TS指令和Swap指令1TS指令2Swap指令第二章進程及處理機管理——

§2.6進程同步（互斥）信號量機制1經典信號量機制（1）信號量（Semaphore）表示資源的物理實體。定義為一個整形變量，它的值除初值外只能由P-V操作完成?？梢钥醋魇欠从迟Y源的數目。也可以看作反映資源可被共享的次數。

（2）P-V操作P-V操作是兩個原子操作（Atomicoperation）P（S）和V（S）。利用對信號量S的操作來實現互斥。

（3）實現互斥（4）缺陷當S<=0時執(zhí)行P操作，必將使進程處于“忙等”狀態(tài)。所謂“忙等”指的是該進程無法向下進行.但還占用CPU時間。第二章進程及處理機管理——

§2.6進程同步（互斥）信號量機制2記錄型信號量機制（1）信號量（2）P-V操作（3）實現（4）特點：改進了系統運行的效率，在進程被阻塞的時候，可以使處理機繼續(xù)完成其它的任務，而不是等待第二章進程及處理機管理——

§2.6進程同步（互斥）信號量機制3信號量集機制（1）提出的原因（2）解決方案強制資源訪問順序一次性申請（信號量集機制）第二章進程及處理機管理——

§2.6進程同步三、依賴同步（同步）1概念指的是兩個合作進程，當某一進程未得到另一個進程發(fā)出來的消息之前處于等待，直到另一個進程發(fā)出來消息后，該進程繼續(xù)向下執(zhí)行。2舉例3實現P-V操作和信號量機制第二章進程及處理機管理——

§2.6進程同步四、說明1進程同步是進程低級通信的一種形式。

2P-V操作實質和信號量的物理意義

信號量的物理意義是：信號量S表示資源的數目。當S>0時，S的數值表示可用資源的個數當S=0時，表示當前系統已經沒有可用資源當S<0時，S的數值表示當前系統缺少的資源個數，也可以表示當前因為沒有申請到資源而被阻塞的進程個數。P-V操作的實質：在互斥中，P操作表示請求分配一個資源，V操作表示請求釋放一個資源在同步中，P操作表示檢測消息是否到來，V操作表示發(fā)送消息。經典信號量機制實現互斥可以為臨界資源先設置一個互斥信號量S，其初始值為該臨界資源的數目。在進程對這個臨界資源進行訪問之前，先執(zhí)行P操作；在退出臨界區(qū)之后執(zhí)行V操做。記錄型信號量機制實現互斥記錄型信號量機制存在的問題信號量集機制第二章進程及處理機管理——

§2.7幾個經典的進程同步問題一、生產者與消費者問題其主要思想是一組生產者向一組消費者提供信息。他們之間共用同一個有界緩沖區(qū)

1、有一個緩沖池，一次只能讓一個進入，不論是生產者還是消費者。2、在一個緩沖池中有多個緩沖區(qū)，每個緩沖區(qū)一次也只能由一個使用3、生產者可以把它的產品放在任何一個空的緩沖區(qū)中4、消費者可以到任何一個已有產品的緩沖區(qū)中取產品5、生產者只有等到緩沖區(qū)有空的時候才可以放產品，消費者只有當緩沖區(qū)有產品的時候才可以把產品取走生產者與消費者問題生產者與消費者存在的問題第二章進程及處理機管理——

§2.7幾個經典的進程同步問題二、讀者-寫者問題一個數據文件或記錄（統稱為數據對象），可被多個進程共享。其中有些進程要求讀，而另一些進程要求寫或修改。我們把只要求讀的進程稱為“讀者”。其他進程稱為“寫者”。允許多個讀者可同時訪問一個共享對象，而不允許一個寫者和其他進程（可能是讀者，也可能是寫者）同時訪問同一個共享對象。1、讀者之間可以共享使用這個文件對象2、寫者之間只能有一個使用這個文件對象3、當一個寫者在使用的時候，讀者也不能使用這個文件讀者-寫者問題解決方案第二章進程及處理機管理——

§2.7幾個經典的進程同步問題三、哲學家進餐的問題有五個哲學家，他們的生活方式是交替的進行思考和進餐，哲學家們共用一張圓桌，周圍放五張椅子，每人坐一張。在圓桌上有五個碗和五只筷子，當一個哲學家思考時，他不與同事交談，饑餓時便試圖取其左右最靠近他的筷子，但有可能一支都拿不到，只有在他拿到兩支筷子才能進餐。餐畢，放下筷子又繼續(xù)思考。哲學家進餐問題解決方案1、用一個信號量表示一只筷子，共有五個信號量構成信號量數組2、需要加上一些限制條件，否則容易出現錯誤。3、限制條件比如是：至多允許四個哲學家同時進餐；僅當哲學家左右兩支筷子都可以用時，才能拿起進餐第二章進程及處理機管理——

§2.7幾個經典的進程同步問題四、司機和售票員問題司機負責汽車的啟動、運行和停止；售票員負責車門的打開和關閉。當司機在汽車啟動工作中，售票員是不允許打開車門的；當汽車停止的時候，售票員可以把車門打開；當售票員把車門關閉后，司機可以啟動汽車。第二章進程及處理機管理——

§2.7幾個經典的進程同步問題五、讀、計算和打印三個進程問題司機和售票員問題第二章進程及處理機管理——

§2.7幾個經典的進程同步問題六、十字路口問題1、東西和南北走向要分開2、在中心有共享區(qū)3、如果有左轉問題，解決方案比較復雜第二章進程及處理機管理——

§2.8進程通信在前面我們所介紹的進程同步中，不論是互斥還是同步，都可以理解為雙方相互之間的信息傳遞，但傳遞的信息只是一個消息，沒有數據信息的概念，為此，我們把這樣的消息傳遞稱為“低級通信”一、進程通信方式1共享存儲的系統（sharedmemorysystem）在這種方式中，相互通信的進程共享某些數據結構或共享存儲區(qū)基于共享數據結構的通信方式基于共享存儲區(qū)的通信方式

第二章進程及處理機管理——

§2.8進程通信一、進程通信方式2信息系統（Messagesystem）

在這種方式中，進程之間通過消息或報只交換信息，并提供相應一組通信命令來實現通信直接通信方式指發(fā)送進程通過系統原語，直接將消息發(fā)送給接收進程。通常使用的系統原語是：send（receiver，message）和receive（sender，message）。間接通信方式指進程之間的通信，需要借助一個數據結構來實現。3利用共享文件的通信方式

間接通信中的數據結構——信箱信箱頭包含信箱的名稱、大小、安全等信息；信箱體是用來存放通信數據的。信箱通信是根據系統提供的一些控制原語來完成。這些控制原語包括創(chuàng)建和撤消信箱、發(fā)送和接收消息等。例如：send（mailbox，message）、receive（mailbox，message）。信箱分為：私有信箱、公用信箱、共享信箱。根據信箱通信的方式，通信進程之間存在有：一對一關系、多對一關系、一對多關系和多對多關系實際例子1、每個接收者都有一個以自己ID為標識的信箱2、每個發(fā)送者都可以把信件放在接收者的信箱中3、與其它共享存儲區(qū)不同的是信箱是統一管理的，發(fā)送者和接收者都不需要考慮對信箱的管理問題第二章進程及處理機管理——

§2.8進程通信二、進程通信實例-消息緩沖隊列通信機制

第二章進程及處理機管理——

§2.9處理機調度處理機調度是進程及處理機管理功能中的最后一個。由于在計算機系統中處于就緒狀態(tài)的進程很多，如何調度它們使之運行，并且還能充分提高處理機的利用率和改善系統性能，成為現代操作系統中的一個中心問題。

一、進程調度的功能和方式1進程調度的功能：i.記住進程的狀態(tài)ii.決定某個進程什么時候得到處理機，占用多長時間iii.執(zhí)行把處理機分配進程iv.讓出處理機2進程調度方式：指的是當一進程正在處理機上運行時，若有某個更為重要的或緊迫的進程到來時，該如何分配處理機通常有兩種調度方式：i.非剝奪方式ii.

剝奪方式第二章進程及處理機管理——

§2.9處理機調度二、調度算法1先進先出（FIFO）算法2最短cup運行期優(yōu)先調度算法（SCBF）3最高優(yōu)先權（FPF）優(yōu)先調度算法靜態(tài)優(yōu)先級動態(tài)優(yōu)先級4輪轉法簡單輪轉法多級隊列輪轉法多級反饋隊列輪轉法第二章進程及處理機管理——§2.10死鎖死鎖指的是當某個進程提出資源申請后，使得若干進程在無外力作用下永遠不能繼續(xù)執(zhí)行。產生死鎖的原因和條件如何解除和預防避免出現死鎖。

第二章進程及處理機管理——§2.10死鎖一、產生死鎖的原因和必要條件1產生死鎖的原因：資源引起死鎖：由于共享資源數目不夠。進程推進順序不當引起死鎖2產生死鎖的必要條件：互斥條件：即共享資源一次只能為一個進程占有。請求與保持條件：即進程一旦擁有某一共享資源，就不會在使用過程中自動釋放，即使在被阻塞時也不釋放。不剝奪條件：即進程已獲得某一資源，在未使用完之前不能被剝奪。環(huán)路條件：在發(fā)生死鎖時，必然會出現進程——資源的環(huán)形鏈。注意：環(huán)路條件既是必要條件，又是充分條件。

第二章進程及處理機管理——§2.10死鎖二、預防死鎖1屏棄‘請求和保持’條件：采取系統要求進程一次性的申請所需的所有資源。2屏棄‘不剝奪’條件：采取進程得不到新請求的資源，則將已請求到的資源釋放。3屏棄‘環(huán)路條件’采取系統中所有資源排隊排號，進程在請求資源時要嚴格按照資源序號遞增的順序。第二章進程及處理機管理——§2.10死鎖三、避免死鎖1安全狀態(tài)：指系統能按某種進程順序如（P1，P2，P3．．．Pn），來為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。這時（P1，P2，P3．．．Pn）序列我們稱為安全序列。2不安全狀態(tài)：若系統中不存在一個安全序列，則稱系統處于不安全狀態(tài)。銀行家算法1數據結構2銀行家算法描述設request(j)是進程P(i)的請求向量。如果request[j]=k，表示進程P(i)需要k個R(j)類資源。

3安全性算法設置兩個向量Work和FinishWork表示可提供給進程繼續(xù)運行所需的各類資源數目，它含有m個元素。其初始值work=available。finish表示是否有足夠的資源分配給進程。其初始值finish[i]=false.

銀行家算法——舉例假定系統中有五個進程{p0,p1,p2,p3,p4}和三類資源{a,b,c},各類資源總數量分別為10，5，7。在t0時刻的資源分配情況如下MaxAllocationNeedavailableABCABCABCABcP0753010743332P1322200122P2902302600P3222211011p44330024311t0時刻是否安全？2P1發(fā)出請求向量request(p1)={1,0,2}，是否進行分配？3P4發(fā)出請求向量request(p4)={3,3,0}，是否進行分配？4P0發(fā)出請求向量request(p0)={0,2,0}，是否進行分配？5P0發(fā)出請求向量request(p0)={0,1,0}，是否進行分配？第二章進程及處理機管理——§2.10死鎖四、檢測死鎖1資源狀態(tài)圖該圖n各結點和f組邊構成，G(N,E)具有如下定義：n被分成兩個獨立的子集，一組為進程結點Ｐ＝（p1，p2，p3．．．Pn)，一組為資源結點Ｒ＝（r1，r2，r3．．．rn）對于邊e∈E，都連接著Ｐ中的一個