第２章進程和處理機管理要求學生掌握順序程序和并發程序；進程的定義、特點及狀態變遷；進程管理；進程間的同步與互斥；進程通信；死鎖產生的原因與解除方法。第２章進程和處理機管理

2.1進程及其有關概念

2.2進程管理

2.3進程的同步與互斥

2.4進程通信

2.5死鎖

2.6小結2.1.1順序程序

1.順序程序：程序中若干操作必須按照某種先后次序來執行，并且每次操作前和操作后的狀態之間都有一定的關系。2.1進程及其有關概念2.順序程序的基本特征

(1)程序執行的順序性(2)資源利用的獨占性，又叫程序執行的封閉性(3)執行結果的確定性2.1.2并發程序

1.并發執行：如果有多個程序段同時在系統中運行且執行時間是重疊的，即使重疊很小，我們也稱這幾個程序段是并發執行的。

2.要求：兩個或兩個程序處于運行狀態2.1進程及其有關概念圖2-1三個并發程序段示意圖2.1.2并發程序

3.用語句形式描述并發程序（執行如圖2-2）

s0;cobegins1;s2;…sn;coend sn+1; 2.1進程及其有關概念圖2-2并發程序執行的優先圖2.1.2并發程序

4.并發執行和并行執行的區別：

前者是在一段時間內，從宏觀上看好象它們是在同時執行，而實際上CPU是按照一定的策略在輪流執行它們，在任一時刻，實際上只有一個程序段在執行。而并行執行需要多CPU的支持，在任一時刻，可以實現多個程序段的真正同時執行。5.引入并發程序的目的：主要是為了提高資源利用率，從而提高系統效率2.1進程及其有關概念6.比較順序程序和并發執行

舉例：假設有A和B兩個程序段，它們各自的執行過程如圖2.3所示。2.1進程及其有關概念圖2-3順序程序舉例如果這兩個程序段是順序執行，則CPU利用率=40/80=50%DEV1利用率=15/80=18.75%DEV2利用率=25/80=31.25%6.比較順序程序和并發執行2.1進程及其有關概念圖2-4并發程序舉例如果這兩個程序段按照如圖2-4的順序并發執行，那么CPU利用率=40/45=89%DEV1利用率=15/45=33%DEV2利用率=25/45=56%2.1.2并發程序

7.并發執行的特征：(1)并發性(2)程序結果的不可再現性（見下頁例子）(3)在并發環境下程序的執行是間斷性的，即程序“執行---暫停---執行”(4)開放性⑸獨立性⑹制約性：分為間接制約和直接制約(7)程序和計算不在一一對應2.1進程及其有關概念例如，A向某帳號存錢，B從某帳號取錢。程序如右：①先執行A，后執行B，即先存錢，后取錢，其結果為s=900。②t1時刻：執行A中的n=s;n=n+100;t2時刻：執行B中的m=s;m=m-200;s=m;t3時刻：執行A中的s=n;則結果為s=1100。程序結果的不可再現性舉例main(){ints=1000；//最初余額cobeginwhile(A未完成){n=s;n=n+100;s=n;}while{m=s;m=m-200;s=m;}coend}2.1.3進程的定義及其特征

1.進程定義最能反映進程實質的定義有：1）進程是程序的一次執行2）進程是可以和別的計算并發執行的計算3）進程可定義為一個數據結構及能在其上進行操作的一個程序。4）進程是一個程序及其數據在處理機上順序執行所發生的活動。2.1進程及其有關概念5）進程是程序在一個數據集合上的運行過程，是系統進行資源分配和調度的一個獨立單位。進程的一個正式的定義是：：進程是在自身的虛擬地址空間運行的一個單獨的程序，是系統進行資源分配和調度的一個獨立單位

這個定義包含的含義是：1）進程一個動態的概念，而程序是一個靜態的概念。

3.1進程的基本概念2）進程包含了一個數據集合和運行其上的程序。3）同一程序運行于若干個不同的數據集合上時，它將屬于若干個不同的進程，或者說，兩個不同的進程可包含相同的程序。4）系統分配資源是以進程為單位的，所以只有進程才可能在不同的時刻處于幾種不同的狀態，例如，等待，就緒，運行。5）從微觀上看，進程是輪換地占有處理機而運行的；從宏觀上看，進程是并發運行的2.1進程及其有關概念2.1.3進程的定義及其特征

2.進程和程序的區別:

⑴進程是程序的一次運行，屬于動態概念；程序是指令的集合，是靜態概念。⑵進程包含數據和運行其上的程序，這樣靜態地觀察進程與程序含義相近。⑶同一程序運行于若干個不同的集合上時，它將屬于若干個不同的進程。或者說，兩個不同的進程可以包含相同的程序。2.1進程及其有關概念2.1.3進程的定義及其特征

2.進程和程序的區別:

⑷進程能逼真的描述并發活動，而程序不明顯。⑸微觀上，進程是輪流搶占處理機而運行的，宏觀上，進程是并發運行的。⑹程序存儲需要介質，進程執行要處理。⑺進程是由程序和數據兩部分組成的。⑻進程可以創建其他進程，可以處于等待、就緒、運行等幾種不同的狀態。2.1進程及其有關概念2.1.3進程的定義及其特征

3.進程和作業的區別:一個正在執行的進程稱為一個作業，而且作業可以包含一個或多個進程，尤其是當使用了管道和重定向命令時。4.進程的特征⑴動態⑵并發⑶獨立⑷交互⑸異步

2.1進程及其有關概念2.1.4進程的類型1、系統進程和用戶進程，兩者的區別:⑴系統進程被分配一個初始資源集，這些資源可以獨占，也可被擁有更高優先權的系統進程優先使用。用戶進程要通過系統服務請求手段競爭系統資源。⑵用戶進程不能直接做I／O操作，而系統進程可以直接進行。⑶系統進程在管態下活動，用戶進程在目態下活動。2.1進程及其有關概念2.1.4進程的類型2、父進程和子進程系統或用戶首先創建的進程稱父進程；在父進程下面的進程稱子進程。進程圖如圖2-5所示：進程圖：是一棵包含一個根結點有向樹，Pi到結點Pj的一條邊表示進程Pj是由進程Pi創建的2.1進程及其有關概念圖2.5進程圖2.1.4進程的類型2、父進程和子進程進程圖反映了進程間的父子關系：創建與被創建、控制與被控制關系，體現了進程間的層次關系。

父子進程間的關系主要為：⑴進程控制：父創建或刪除子⑵運行方式：同時運行或最后運行⑶資源共享：全部或部分共享資源2.1進程及其有關概念2.2.1進程的狀態及其轉換1、進程的三個基本狀態⑴運行狀態⑵就緒狀態

⑶等待狀態。也叫阻塞狀態、掛起狀態、封鎖狀態、凍結狀態、睡眠狀態。2、引起進程狀態轉換的原因大致如下：⑴CPU調度；⑵進程在運行過程中需要等待某一事件；⑶如果進程所等待的事件發生變化；⑷一個具體的進程在任何一個指定的時刻必須而且只能處于一種狀態。2.2進程管理2.2進程管理圖2-6進程狀態變遷圖2.2.2進程的組成1、進程的組成

進程由三部分組成：程序、數據集合和進程控制塊(ProcessControlBlok，PCB)前兩者稱為進程的實體，用PCB描述實體的存在和變化。2.2進程管理PCB數據程序圖2-7進程的組成2.2.2進程的組成2、進程控制塊PCB1)PCB的作用：標識進程存在的唯一實體2）進程控制塊PCB常用的信息如表2-13）PCB中的內容主要分為如下3大部分：進程標識符、處理器狀態信息、進程控制信息

2.2進程管理進程標識符進程當前狀態當前隊列指針總鏈指針程序開始地址進程優先級CPU現場保護區進程通信家族聯系占有資源清單表2-1PCB的一般結構2.2.2進程的組成3、PCB表的兩種組織方式

1）線性表；2）鏈接表。如圖2-8所示

2.2進程管理(a)PCB的線性表Next0Next1Next2

∧PCB1PCB2PCBnReady-head高低(b)按優先級排列的就緒隊列鏈接表priority2.2.2進程的組成3、PCB表的兩種組織方式

2.2進程管理Next0Next1Next2

∧PCB1PCB2PCBnReady-head先后(c)按先來先服務排列的就緒隊列鏈接表FCFS圖2-8PCB表的組織方式4、進程的狀態轉換用PCB隊列來表示

2.2進程管理圖2.9狀態轉換2.2.3進程控制

原語：程序、我們把系統態下執行的某些具有特定功能的程序段。原語可以是機器指令集的擴充，其特點是執行期間不允許中斷，它是一個不可分割的基本單位。用于進程控制的原語有：創建原語、撤消原語、阻塞原語、喚醒原語等2.2進程管理2.2.3進程控制

1、創建進程創建進程原語，操作系統主要完成以下幾項工作：1)創建一個PCB。2)賦予一個統一的進程標識符。3)為進程映象分配空間。4)初始化進程控制塊。5)設置相應的鏈接,如把新進程加到就緒隊列的鏈表中。2.2進程管理假設我們用n表示進程名（外部標識符），CPU的初始狀態為S，優先數為K，內存始址為M，資源清單為R，申請的PCB的內部標識符為i，則創建進程原語可描述為：創建原語Create(n,S,K,M,R,acc){i=getnewinternalname(n)；∥為n申請一個PCB，標號送入iid[i]=n；∥進程外部標識符登記第i個PCB相應域

priority[i]=K；∥置優先數

cpustate[i]=S；∥置CPU狀態

mainstore[i]=M；∥置內存始址

resourcesp[i]=R；∥置資源表

status[i]=“readys”；∥置該進程為就緒狀態

sdata[i]=RL；∥指向就緒隊列

parent[i]=*；∥置創建它的父進程名insert(progeny(*),i)；∥插入進程簇中

setaccountingdata；∥建立記帳信息

insert(RL,i)∥將PCB插入就緒隊列}2、刪除進程又稱撤消進程刪除進程的3種情形：1）正常終止；2）由于錯誤非正常終止；3）祖先進程要求撤銷

刪除進程通常需要完成以下工作：1）定位欲刪除的進程PCB；2）回收進程所占的全部資源；3）遞歸地刪除其所有“子孫”進程；4）刪除PCB，處理記賬信息；5）若刪除的是正在運行的進程，則請求重新調度，否則返回。2.2進程管理刪除進程原語Kill操作如下：Delete(n){Sched=false;//置調度標志為假I=getinternatname(n);//找內部進程號Kill(i);//調刪除進程過程If(sched)Scheduler;//若i為運行態，則重新調度}

kill(i){If(status[i]==”Executing”)//若i為運行態{stop(i);//停止i的執行，保存CPU信息sched=true;//置重新調度標志}remove(sdata[i],i);//從隊列中刪去i進程for(alls∈progency(i))kill(s)//刪除i的所有子進程for(allr∈(mainstore(i)∪resoure(i)))ifowned[r]then//如果是i的祖先的資源，則全部歸還insert(avail(semaphore(r)),data(r));//給它的祖先for(allR∈creaeresources(i))removeresourcesdescriptot[R];//創建時申請的資源全部歸還給系統removepch[i];//釋放PCB}2.2.3進程控制

3、掛起進程

進程掛起方式：自身掛起；掛起指定標識符的進程；進程全部或部分子孫進程掛起

在掛起進程控制中主要完成以下工作：1）定位欲掛起的進程PCB；2）將其運行的有關現場信息放至調用者指定的區域；3）將進程變為掛起狀態；4）如果進程從運行狀態變為掛起狀態，則請求重新調度。2.2進程管理假設掛起指定標識符為n的進程，調用者指定區域為a，則掛起進程原語可描述為：2.2進程管理Suspend(n,a){i=get-internal-name(n);//根據指定標識符n獲取進程內部號S=status[i];//把狀態賦給sIf(s==”Executing”)Stop(i);//若進程為執行態，則中斷ＣＰＵA=copy-PCB[i];//保存ＰＣＢ狀態到指定區域Status(i)=(s=”Blockeda”?”Blockeds”:”Ready”);//若狀態為活動阻塞，則掛起進程為靜止阻塞，否則為就緒狀態

If(s=”Executing”)Scheduler;//若為執行態，則重新調度}2.2.3進程控制

4、喚醒進程

進程喚醒方法：1）有系統進程喚醒；2）有事件發生進程喚醒

喚醒進程原語完成的主要工作如下：1）定位被喚醒的進程PCB；2）將其改變為就緒狀態，插入就緒隊列；3）請求重新調度。2.2進程管理假設喚醒指定標識符為n的進程，則喚醒進程原語可描述為：2.2進程管理

Wakeup(n){i=get-internal-name(n);/／找到喚醒進程nRemove(WL[r],i);/／從等待隊列中出隊Status[i]=”ready”;／/將其變為就緒隊列Insert(RL,i);/／插入就緒隊列Scheduler;/／重新調度}在以上算法中，WL為等待隊列，RL為就緒隊列。2.2.4進度調度進程調度（也稱CPU調度）:按照某種調度算法從就緒隊列中選取進程分配CPU，也叫低調

衡量各種調度算法性能優劣的指標:

1）CPU利用率——主要目標CPU利用率=CPU利用的時間/開機運行的總時間

2）等待時間3）響應時間4）I/O設備的利用率5）“時空”代價2.2進程管理2.2.4進度調度進程調度方式：剝奪調度和非剝奪調度下面介紹幾種常見的進程調度方法1.先來先服務（Firstcomefirstservice,FCFS）2.輪轉法（RR，RoundRobin）將CPU的處理時間分成固定大小的時間片，進程時間片內輪轉執行

關鍵問題：如何確定時間片的大小

時間片q=RT/Nmax2.2進程管理將考慮下面3個進程，它們按1，2，3的順序處于就緒隊列中：進程下一個CPU周期

P124P23P33

2.2進程管理圖2-10執行過程1圖2-11執行過程2FCFS調度算法其他調度算法2.輪轉法設有如下4個就緒進程：進程下一個CPU周期

P16P23P31P47

則如圖2-12所示2.2進程管理01234567qATT圖2-12平均周轉時間ATT與時間片q之間的關系2.2.4進度調度3.多級反饋輪轉法思想：不同級別的就緒隊列分配給不同時間片，優先級高的為第一級隊列，時間片最小，隨著隊列級別降低，時間片加大

例如：考慮由3個隊列組成的多級隊列調度3個隊列的編號分別為0,1,2，如下圖2.2進程管理2.2.4進度調度4.優先數法（Priority）思想：按進程的優先級確定調度優先權優先級確定方法：（1）靜態法：可按進程類型、資源的要求、用戶要求指定（2）動態法：原則是合理地分配CPU時間、緊急的程序優先2.2進程管理實例解釋：假設就緒狀態有4個進程，每個進程所需運行時間如下所示。進程 所需運行時間

1 62 33147進程到達次序為1，2，3，4。試分別按先來先服務調度算法、短進程優先調度算法和時間片輪轉法(時間片分1，3，5，6)給出進程調度順序，并計算平均等待時間。2.2進程管理解：（1）先來先服務調度算法進程調度順序為：

平均等待時間：T=1／4×(0+6+9+10)=6.25（2）短進程優先調度算法進程調度順序為：平均等待時間：T=1／4×(4+1+0+10)=3.75（3）時間片輪轉法

2.2進程管理解：·時間片為1，進程調度順序如下：

平均等待時間：T=1/4×((0+3+2+2+1+1)+(1+3+2)+2+(3+2+2+1+1+1)=1／4×(9+6+2+10)=6.75·時間片為3，進程調度順序如下：平均等待時間：T=1／4×((0+7)+3+6+(7+3))=1／4×(7+3+6+10)=6.52.2進程管理解：·時間片為5，進程調度順序如下：平均等待時間：T=1／4×((0+9)+5+8+(9+1))=1／4×(9+5+8+10)=8·時間片為6，相當于先來先服務調度算法。其進程調度順序和平均等待時間與先來先服務調度算法相同。總結：短進程優先調度算法使進程平均等待時間最小。對于時間片輪轉法，進程平均等待時間與時間片的大小有關。

2.2進程管理進程間的兩種主要關系：

1、互斥關系，也稱間接制約關系：各進程間競爭、互斥使用共享資源

2、同步關系，也稱直接制約關系：指多個進程發生的事件存在某種時序關系，需要相互合作，共同完成一項任務。譬如公共汽車上司機與售票員的合作就是一種同步關系。2.3進程的同步與互斥同步與互斥的特點比較如表2-1所示。2.3進程的同步與互斥同

步互

斥進程—進程時間次序上受到某種限制相互清楚對方的存在及其作用，交換信息往往指有幾個進程共同完成一個任務舉例：生產與消費之間，發送與接受之間，作者與讀者之間，供者與用者之間進程—資源—進程競爭到某一物理資源時不允許進程工作不一定清楚其它進程情況往往指多個任務多個進程間通訊制約舉例：交通十字路口，單軌火車的撥道岔表2-1同步與互斥的比較2.3.1臨界區

臨界資源：一次只允許一個進程使用的資源

臨界區：在進程中涉及到臨界資源的程序段

使用臨界區、解決互斥問題應遵守以下原則：

1）有空讓進2）等待3）多中擇一4）有限等待5）讓權等待2.3進程的同步與互斥2.3.1臨界區

我們先看一下幾個問題：問題1：設進程P1，P2，共享一臺打印機問題2：生產者／消費者問題(Producer／Consumer)這里，生產者和消費者進程因為共享使用著一個軟件資源――產品系列，若按不恰當的執行順序，則隊列操作就會出現混亂。2.3進程的同步與互斥小結：從以上二個例子可以看到，進程之間若共享互斥資源(共享外設—打印機，共享隊列等)，則會出現互斥問題，即存在臨界區問題。2.3.2互斥

進程互斥進入方法：

1、用禁止中斷實現互斥

2、用鎖操作原語實現互斥為共享資源設置一把鎖。鎖用變量W表示：W=0表示共享資源可用。W=1表示共享資源不可用，已有進程訪問

有關鎖的基本操作如下：

2.3進程的同步與互斥加鎖原語LOCK（W）{while(W);W=1;}開鎖原語UNLOCK（W）{W=0;}2.3.2互斥

3、信號量及P、V操作原語實現互斥

信號量(Semaphore)是表示資源的物理實體，是一個與隊列有關的整型變量。信號量是一個數據結構,一般定義如下：

strucsemaphore{intvalue; pointer_PCBqueue;}2.3進程的同步與互斥信號量說明：

semaphores;3、信號量及P、V操作原語實現互斥P、V操作是指在信號量上定義的兩個操作。設信號量為s，對s的P操作記為P(s)，對它的操作記為V(s)。2.3進程的同步與互斥P操作對應的過程如下：P(s){s.value――;if(s.value<0){該進程狀態置為等待狀態;

將該進程的PCB插入相應的等待隊列末尾s.queue;}}V操作對應的過程如下：V(s){s.value++;if(s.value<=0){喚醒相應等待隊列s.queue中等待的一個進程;改變其狀態為就緒態;并將其插入就緒隊列;

}}3、信號量及P、V操作原語實現互斥P(s)表示申請一個資源，V(s)表示釋放一個資源。P.V操作必須成對出現2.3進程的同步與互斥P1P2…………P(s);P(s);使用打印機;使用打印機；V(s);V(s);…………下面通過幾個例子進一步說明。例1用PV操作解決打印機共享的問題（如右）s的初值為1，表示打印機是可用的。例2生產者／消費者問題（自行閱讀）例3用P、V操作實現如圖2-17所示的優先圖2.3.3進程同步

1、同步類別：

(1)對系統資源的共享。(2)諸進程合作完成某工作的邏輯順序。

2、利用信號量機制解決進程同步問題舉例設有若干個生產者進程P1，P2，….Pn，若干個消費者進程C1，C2，…Cm，它們通過一個有界緩沖池聯系起來。其同步問題是：P進程不能往“滿”緩沖區中放產品，C進程不能從“空”緩沖區中取產品。可以采用P.V操作解決。設各生產者使用的信號量為S1，消費者使用的信號量為S2。2.3進程的同步與互斥例1：設只有一個生產者、一個消費者且緩沖區的大小為1。S1初值為1、S2為0。S1=1表示最初有一個緩沖區空間可用，S2=0表示最初沒有產品可消費。2.3進程的同步與互斥P：while(true){

生產一個產品;P(s1);

送產品到緩沖區;V(s2);};C：while(true){P(s2);

從緩沖區取產品;V(s1);

消費產品;};例4再看第二種情況：只有一個生產者、一個消費者且緩沖區的大小為n。設S1初值為n，S2初值為0。S1=n表示最初有n個緩沖區空間可用，S2=0表示最初沒有產品可消費。2.3進程的同步與互斥P：i=0;while(true){

生產產品;P(S1);

往Buffer[i]放產品;V(S2);i=(i+1)%n;};

C：j=0;while(true){P(S2);

從Buffer[j]取產品;V(S1);

消費產品;j=(j+1)%n;};例5再看第三種情況：有m一個生產者、k個消費者且緩沖區的大小為n。設S1初值為n，S2初值為0，mutex的初值為1（默認值）。2.3進程的同步與互斥P：i=0;while(true){

生產產品;P(S1);P(mutex);

往Buffer[i]放產品;V(mutex);V(S2);i=(i+1)%n;};C：j=0;while(true){P(S2);P(mutex);

從Buffer[j]取產品;V(mutex);V(S1);

消費產品;j=(j+1)%n;};2.4.1進程通信的概念

1、進程通信：是指進程之間的信息交換。2、進程通信類型1)

共享存儲器系統2)消息系統進程間的信息交換以消息或者報文為單位消息系統有兩種通信方式：a）直接通信方式

原語：send(接收者ID，消息)和receive(發送者ID，消息)2.4進程通信b）間接通信方式如右圖，進程間有中間實體（信箱）2.4進程通信發送進程接收進程信箱頭信箱1信箱2

間接通信方式3)

利用共享文件（管道）的通信方式

發送進程接收進程圖3-12利用共享文件（管道）通信2.4.2消息通信

通信鏈：是指進程之間進行通信存在的鏈路連接，通信鏈有物理通信鏈和邏輯通信鏈之分。

通信方式主要有：直接或間接通信；對稱或非對稱通信。

1、直接通信

直接通信的一個基本原則是：發送/接收消息的每一個進程，通信時都必須明顯地指明接收/發送方的名字。2.4進程通信2.4.2消息通信

1、直接通信直接通信通信鏈的屬性主要包括以下方面：1）參加通信的雙方；2）每條通信鏈嚴格地對應兩個進程；3）任意一對進行通信的進程，均嚴格地存在一條通信鏈；4）通信鏈是雙向的，可雙向傳輸

其中，send和receive原語定義為：

Send(P,message):發送message給進程P；

Receive(Q,message):接收來自進程Q的message2.4進程通信生產者/消費者問題采用直接通信方式的進程間的通信進程：2.4進程通信typedefitem=…；itemnextp,nextc;cobegin;producer{do{…produceaniteminnextp;…send(consumer,nextp);}while(true);}

consumer{do{receive(producer,nextc);…consumetheiteminnextc;…}while(true);}coend利用消息緩沖區實現直接通訊方式的通訊鏈：2.4進程通信圖2-19消息緩沖區的直接通訊2.4.2消息通信

2、間接通信，又稱郵箱(mailbox)通訊方式進程間通過信箱實現通信郵箱是一種數據結構，結構如圖2-20

使用信箱的規則：1）若發送信件時郵箱已滿，則發送進程被置為“等郵箱”狀態，直到信箱有空時才被釋放。2）若取信件時信箱中無信，則接收進程被置為“等信件”狀態，直到有信件時才被釋放。2.4進程通信圖2-20郵箱結構2.4.2消息通信

2、間接通信，又稱郵箱(mailbox)通訊方式send和receive原語定義如下：send(A,message)：向郵箱A送入message；receive(A,message)：從郵箱A取出message2.4進程通信

send實現步驟如下所示：{查找指定郵箱A；若郵箱未滿，則把信件message送入郵箱且釋放“等信件”者；若郵箱已滿置發送信件進程為“等郵箱”狀態；}receive實現步驟如下所示:{查找指定郵箱A；若郵箱中有信，則取出一封信存于message中且釋放“等郵箱”者；若郵箱中無信件則置接收信件進程“等信件”狀態；}2.4.2消息通信

2、間接通信，又稱郵箱(mailbox)通訊方式在間接通訊方式中，通訊鏈具有如下屬性:1)只有當兩個進程有了一個可共享的郵箱時，通訊鏈才在二者之間建立。2)通訊鏈能夠聯系兩個以上的進程。3)每一對通訊進程之間必須有一組不同的鏈，每條鏈對應一個郵箱。4)通訊鏈可以是單向的，又可以是雙向的，如圖2-21所示。2.4進程通信2.4進程通信圖2-21郵箱通信方式2.5