第2章 進(jìn)程和處理機(jī)管理_第1頁
第2章 進(jìn)程和處理機(jī)管理_第2頁
第2章 進(jìn)程和處理機(jī)管理_第3頁
第2章 進(jìn)程和處理機(jī)管理_第4頁
第2章 進(jìn)程和處理機(jī)管理_第5頁
已閱讀5頁,還剩72頁未讀 繼續(xù)免費閱讀

付費下載

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

第2章進(jìn)程和處理機(jī)管理要求學(xué)生掌握順序程序和并發(fā)程序;進(jìn)程的定義、特點及狀態(tài)變遷;進(jìn)程管理;進(jìn)程間的同步與互斥;進(jìn)程通信;死鎖產(chǎn)生的原因與解除方法。第2章進(jìn)程和處理機(jī)管理

2.1進(jìn)程及其有關(guān)概念

2.2進(jìn)程管理

2.3進(jìn)程的同步與互斥

2.4進(jìn)程通信

2.5死鎖

2.6小結(jié)2.1.1順序程序

1.順序程序:程序中若干操作必須按照某種先后次序來執(zhí)行,并且每次操作前和操作后的狀態(tài)之間都有一定的關(guān)系。2.1進(jìn)程及其有關(guān)概念2.順序程序的基本特征

(1)程序執(zhí)行的順序性(2)資源利用的獨占性,又叫程序執(zhí)行的封閉性(3)執(zhí)行結(jié)果的確定性2.1.2并發(fā)程序

1.并發(fā)執(zhí)行:如果有多個程序段同時在系統(tǒng)中運行且執(zhí)行時間是重疊的,即使重疊很小,我們也稱這幾個程序段是并發(fā)執(zhí)行的。

2.要求:兩個或兩個程序處于運行狀態(tài)2.1進(jìn)程及其有關(guān)概念圖2-1三個并發(fā)程序段示意圖2.1.2并發(fā)程序

3.用語句形式描述并發(fā)程序(執(zhí)行如圖2-2)

s0;cobegins1;s2;…sn;coend sn+1; 2.1進(jìn)程及其有關(guān)概念圖2-2并發(fā)程序執(zhí)行的優(yōu)先圖2.1.2并發(fā)程序

4.并發(fā)執(zhí)行和并行執(zhí)行的區(qū)別:

前者是在一段時間內(nèi),從宏觀上看好象它們是在同時執(zhí)行,而實際上CPU是按照一定的策略在輪流執(zhí)行它們,在任一時刻,實際上只有一個程序段在執(zhí)行。而并行執(zhí)行需要多CPU的支持,在任一時刻,可以實現(xiàn)多個程序段的真正同時執(zhí)行。5.引入并發(fā)程序的目的:主要是為了提高資源利用率,從而提高系統(tǒng)效率2.1進(jìn)程及其有關(guān)概念6.比較順序程序和并發(fā)執(zhí)行

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

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

1.進(jìn)程定義最能反映進(jìn)程實質(zhì)的定義有:1)進(jìn)程是程序的一次執(zhí)行2)進(jìn)程是可以和別的計算并發(fā)執(zhí)行的計算3)進(jìn)程可定義為一個數(shù)據(jù)結(jié)構(gòu)及能在其上進(jìn)行操作的一個程序。4)進(jìn)程是一個程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行所發(fā)生的活動。2.1進(jìn)程及其有關(guān)概念5)進(jìn)程是程序在一個數(shù)據(jù)集合上的運行過程,是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。進(jìn)程的一個正式的定義是::進(jìn)程是在自身的虛擬地址空間運行的一個單獨的程序,是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位

這個定義包含的含義是:1)進(jìn)程一個動態(tài)的概念,而程序是一個靜態(tài)的概念。

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

2.進(jìn)程和程序的區(qū)別:

⑴進(jìn)程是程序的一次運行,屬于動態(tài)概念;程序是指令的集合,是靜態(tài)概念。⑵進(jìn)程包含數(shù)據(jù)和運行其上的程序,這樣靜態(tài)地觀察進(jìn)程與程序含義相近。⑶同一程序運行于若干個不同的集合上時,它將屬于若干個不同的進(jìn)程。或者說,兩個不同的進(jìn)程可以包含相同的程序。2.1進(jìn)程及其有關(guān)概念2.1.3進(jìn)程的定義及其特征

2.進(jìn)程和程序的區(qū)別:

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

3.進(jìn)程和作業(yè)的區(qū)別:一個正在執(zhí)行的進(jìn)程稱為一個作業(yè),而且作業(yè)可以包含一個或多個進(jìn)程,尤其是當(dāng)使用了管道和重定向命令時。4.進(jìn)程的特征⑴動態(tài)⑵并發(fā)⑶獨立⑷交互⑸異步

2.1進(jìn)程及其有關(guān)概念2.1.4進(jìn)程的類型1、系統(tǒng)進(jìn)程和用戶進(jìn)程,兩者的區(qū)別:⑴系統(tǒng)進(jìn)程被分配一個初始資源集,這些資源可以獨占,也可被擁有更高優(yōu)先權(quán)的系統(tǒng)進(jìn)程優(yōu)先使用。用戶進(jìn)程要通過系統(tǒng)服務(wù)請求手段競爭系統(tǒng)資源。⑵用戶進(jìn)程不能直接做I/O操作,而系統(tǒng)進(jìn)程可以直接進(jìn)行。⑶系統(tǒng)進(jìn)程在管態(tài)下活動,用戶進(jìn)程在目態(tài)下活動。2.1進(jìn)程及其有關(guān)概念2.1.4進(jìn)程的類型2、父進(jìn)程和子進(jìn)程系統(tǒng)或用戶首先創(chuàng)建的進(jìn)程稱父進(jìn)程;在父進(jìn)程下面的進(jìn)程稱子進(jìn)程。進(jìn)程圖如圖2-5所示:進(jìn)程圖:是一棵包含一個根結(jié)點有向樹,Pi到結(jié)點Pj的一條邊表示進(jìn)程Pj是由進(jìn)程Pi創(chuàng)建的2.1進(jìn)程及其有關(guān)概念圖2.5進(jìn)程圖2.1.4進(jìn)程的類型2、父進(jìn)程和子進(jìn)程進(jìn)程圖反映了進(jìn)程間的父子關(guān)系:創(chuàng)建與被創(chuàng)建、控制與被控制關(guān)系,體現(xiàn)了進(jìn)程間的層次關(guān)系。

父子進(jìn)程間的關(guān)系主要為:⑴進(jìn)程控制:父創(chuàng)建或刪除子⑵運行方式:同時運行或最后運行⑶資源共享:全部或部分共享資源2.1進(jìn)程及其有關(guān)概念2.2.1進(jìn)程的狀態(tài)及其轉(zhuǎn)換1、進(jìn)程的三個基本狀態(tài)⑴運行狀態(tài)⑵就緒狀態(tài)

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

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

2.2進(jìn)程管理進(jìn)程標(biāo)識符進(jìn)程當(dāng)前狀態(tài)當(dāng)前隊列指針總鏈指針程序開始地址進(jìn)程優(yōu)先級CPU現(xiàn)場保護(hù)區(qū)進(jìn)程通信家族聯(lián)系占有資源清單表2-1PCB的一般結(jié)構(gòu)2.2.2進(jìn)程的組成3、PCB表的兩種組織方式

1)線性表;2)鏈接表。如圖2-8所示

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

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

2.2進(jìn)程管理Next0Next1Next2

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

2.2進(jìn)程管理圖2.9狀態(tài)轉(zhuǎn)換2.2.3進(jìn)程控制

原語:程序、我們把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段。原語可以是機(jī)器指令集的擴(kuò)充,其特點是執(zhí)行期間不允許中斷,它是一個不可分割的基本單位。用于進(jìn)程控制的原語有:創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等2.2進(jìn)程管理2.2.3進(jìn)程控制

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

priority[i]=K;∥置優(yōu)先數(shù)

cpustate[i]=S;∥置CPU狀態(tài)

mainstore[i]=M;∥置內(nèi)存始址

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

status[i]=“readys”;∥置該進(jìn)程為就緒狀態(tài)

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

parent[i]=*;∥置創(chuàng)建它的父進(jìn)程名insert(progeny(*),i);∥插入進(jìn)程簇中

setaccountingdata;∥建立記帳信息

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

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

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

3、掛起進(jìn)程

進(jìn)程掛起方式:自身掛起;掛起指定標(biāo)識符的進(jìn)程;進(jìn)程全部或部分子孫進(jìn)程掛起

在掛起進(jìn)程控制中主要完成以下工作:1)定位欲掛起的進(jìn)程PCB;2)將其運行的有關(guān)現(xiàn)場信息放至調(diào)用者指定的區(qū)域;3)將進(jìn)程變?yōu)閽炱馉顟B(tài);4)如果進(jìn)程從運行狀態(tài)變?yōu)閽炱馉顟B(tài),則請求重新調(diào)度。2.2進(jìn)程管理假設(shè)掛起指定標(biāo)識符為n的進(jìn)程,調(diào)用者指定區(qū)域為a,則掛起進(jìn)程原語可描述為:2.2進(jìn)程管理Suspend(n,a){i=get-internal-name(n);//根據(jù)指定標(biāo)識符n獲取進(jìn)程內(nèi)部號S=status[i];//把狀態(tài)賦給sIf(s==”Executing”)Stop(i);//若進(jìn)程為執(zhí)行態(tài),則中斷CPUA=copy-PCB[i];//保存PCB狀態(tài)到指定區(qū)域Status(i)=(s=”Blockeda”?”Blockeds”:”Ready”);//若狀態(tài)為活動阻塞,則掛起進(jìn)程為靜止阻塞,否則為就緒狀態(tài)

If(s=”Executing”)Scheduler;//若為執(zhí)行態(tài),則重新調(diào)度}2.2.3進(jìn)程控制

4、喚醒進(jìn)程

進(jìn)程喚醒方法:1)有系統(tǒng)進(jìn)程喚醒;2)有事件發(fā)生進(jìn)程喚醒

喚醒進(jìn)程原語完成的主要工作如下:1)定位被喚醒的進(jìn)程PCB;2)將其改變?yōu)榫途w狀態(tài),插入就緒隊列;3)請求重新調(diào)度。2.2進(jìn)程管理假設(shè)喚醒指定標(biāo)識符為n的進(jìn)程,則喚醒進(jìn)程原語可描述為:2.2進(jìn)程管理

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

衡量各種調(diào)度算法性能優(yōu)劣的指標(biāo):

1)CPU利用率——主要目標(biāo)CPU利用率=CPU利用的時間/開機(jī)運行的總時間

2)等待時間3)響應(yīng)時間4)I/O設(shè)備的利用率5)“時空”代價2.2進(jìn)程管理2.2.4進(jìn)度調(diào)度進(jìn)程調(diào)度方式:剝奪調(diào)度和非剝奪調(diào)度下面介紹幾種常見的進(jìn)程調(diào)度方法1.先來先服務(wù)(Firstcomefirstservice,FCFS)2.輪轉(zhuǎn)法(RR,RoundRobin)將CPU的處理時間分成固定大小的時間片,進(jìn)程時間片內(nèi)輪轉(zhuǎn)執(zhí)行

關(guān)鍵問題:如何確定時間片的大小

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

P124P23P33

2.2進(jìn)程管理圖2-10執(zhí)行過程1圖2-11執(zhí)行過程2FCFS調(diào)度算法其他調(diào)度算法2.輪轉(zhuǎn)法設(shè)有如下4個就緒進(jìn)程:進(jìn)程下一個CPU周期

P16P23P31P47

則如圖2-12所示2.2進(jìn)程管理01234567qATT圖2-12平均周轉(zhuǎn)時間ATT與時間片q之間的關(guān)系2.2.4進(jìn)度調(diào)度3.多級反饋輪轉(zhuǎn)法思想:不同級別的就緒隊列分配給不同時間片,優(yōu)先級高的為第一級隊列,時間片最小,隨著隊列級別降低,時間片加大

例如:考慮由3個隊列組成的多級隊列調(diào)度3個隊列的編號分別為0,1,2,如下圖2.2進(jìn)程管理2.2.4進(jìn)度調(diào)度4.優(yōu)先數(shù)法(Priority)思想:按進(jìn)程的優(yōu)先級確定調(diào)度優(yōu)先權(quán)優(yōu)先級確定方法:(1)靜態(tài)法:可按進(jìn)程類型、資源的要求、用戶要求指定(2)動態(tài)法:原則是合理地分配CPU時間、緊急的程序優(yōu)先2.2進(jìn)程管理實例解釋:假設(shè)就緒狀態(tài)有4個進(jìn)程,每個進(jìn)程所需運行時間如下所示。進(jìn)程 所需運行時間

1 62 33147進(jìn)程到達(dá)次序為1,2,3,4。試分別按先來先服務(wù)調(diào)度算法、短進(jìn)程優(yōu)先調(diào)度算法和時間片輪轉(zhuǎn)法(時間片分1,3,5,6)給出進(jìn)程調(diào)度順序,并計算平均等待時間。2.2進(jìn)程管理解:(1)先來先服務(wù)調(diào)度算法進(jìn)程調(diào)度順序為:

平均等待時間:T=1/4×(0+6+9+10)=6.25(2)短進(jìn)程優(yōu)先調(diào)度算法進(jìn)程調(diào)度順序為:平均等待時間:T=1/4×(4+1+0+10)=3.75(3)時間片輪轉(zhuǎn)法

2.2進(jìn)程管理解:·時間片為1,進(jìn)程調(diào)度順序如下:

平均等待時間: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,進(jìn)程調(diào)度順序如下:平均等待時間:T=1/4×((0+7)+3+6+(7+3))=1/4×(7+3+6+10)=6.52.2進(jìn)程管理解:·時間片為5,進(jìn)程調(diào)度順序如下:平均等待時間:T=1/4×((0+9)+5+8+(9+1))=1/4×(9+5+8+10)=8·時間片為6,相當(dāng)于先來先服務(wù)調(diào)度算法。其進(jìn)程調(diào)度順序和平均等待時間與先來先服務(wù)調(diào)度算法相同。總結(jié):短進(jìn)程優(yōu)先調(diào)度算法使進(jìn)程平均等待時間最小。對于時間片輪轉(zhuǎn)法,進(jìn)程平均等待時間與時間片的大小有關(guān)。

2.2進(jìn)程管理進(jìn)程間的兩種主要關(guān)系:

1、互斥關(guān)系,也稱間接制約關(guān)系:各進(jìn)程間競爭、互斥使用共享資源

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

步互

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

臨界資源:一次只允許一個進(jìn)程使用的資源

臨界區(qū):在進(jìn)程中涉及到臨界資源的程序段

使用臨界區(qū)、解決互斥問題應(yīng)遵守以下原則:

1)有空讓進(jìn)2)等待3)多中擇一4)有限等待5)讓權(quán)等待2.3進(jìn)程的同步與互斥2.3.1臨界區(qū)

我們先看一下幾個問題:問題1:設(shè)進(jìn)程P1,P2,共享一臺打印機(jī)問題2:生產(chǎn)者/消費者問題(Producer/Consumer)這里,生產(chǎn)者和消費者進(jìn)程因為共享使用著一個軟件資源――產(chǎn)品系列,若按不恰當(dāng)?shù)膱?zhí)行順序,則隊列操作就會出現(xiàn)混亂。2.3進(jìn)程的同步與互斥小結(jié):從以上二個例子可以看到,進(jìn)程之間若共享互斥資源(共享外設(shè)—打印機(jī),共享隊列等),則會出現(xiàn)互斥問題,即存在臨界區(qū)問題。2.3.2互斥

進(jìn)程互斥進(jìn)入方法:

1、用禁止中斷實現(xiàn)互斥

2、用鎖操作原語實現(xiàn)互斥為共享資源設(shè)置一把鎖。鎖用變量W表示:W=0表示共享資源可用。W=1表示共享資源不可用,已有進(jìn)程訪問

有關(guān)鎖的基本操作如下:

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

3、信號量及P、V操作原語實現(xiàn)互斥

信號量(Semaphore)是表示資源的物理實體,是一個與隊列有關(guān)的整型變量。信號量是一個數(shù)據(jù)結(jié)構(gòu),一般定義如下:

strucsemaphore{intvalue; pointer_PCBqueue;}2.3進(jìn)程的同步與互斥信號量說明:

semaphores;3、信號量及P、V操作原語實現(xiàn)互斥P、V操作是指在信號量上定義的兩個操作。設(shè)信號量為s,對s的P操作記為P(s),對它的操作記為V(s)。2.3進(jìn)程的同步與互斥P操作對應(yīng)的過程如下:P(s){s.value――;if(s.value<0){該進(jìn)程狀態(tài)置為等待狀態(tài);

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

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

1、同步類別:

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

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

生產(chǎn)一個產(chǎn)品;P(s1);

送產(chǎn)品到緩沖區(qū);V(s2);};C:while(true){P(s2);

從緩沖區(qū)取產(chǎn)品;V(s1);

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

生產(chǎn)產(chǎn)品;P(S1);

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

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

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

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

生產(chǎn)產(chǎn)品;P(S1);P(mutex);

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

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

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

1、進(jìn)程通信:是指進(jìn)程之間的信息交換。2、進(jìn)程通信類型1)

共享存儲器系統(tǒng)2)消息系統(tǒng)進(jìn)程間的信息交換以消息或者報文為單位消息系統(tǒng)有兩種通信方式:a)直接通信方式

原語:send(接收者ID,消息)和receive(發(fā)送者ID,消息)2.4進(jìn)程通信b)間接通信方式如右圖,進(jìn)程間有中間實體(信箱)2.4進(jìn)程通信發(fā)送進(jìn)程接收進(jìn)程信箱頭信箱1信箱2

間接通信方式3)

利用共享文件(管道)的通信方式

發(fā)送進(jìn)程接收進(jìn)程圖3-12利用共享文件(管道)通信2.4.2消息通信

通信鏈:是指進(jìn)程之間進(jìn)行通信存在的鏈路連接,通信鏈有物理通信鏈和邏輯通信鏈之分。

通信方式主要有:直接或間接通信;對稱或非對稱通信。

1、直接通信

直接通信的一個基本原則是:發(fā)送/接收消息的每一個進(jìn)程,通信時都必須明顯地指明接收/發(fā)送方的名字。2.4進(jìn)程通信2.4.2消息通信

1、直接通信直接通信通信鏈的屬性主要包括以下方面:1)參加通信的雙方;2)每條通信鏈嚴(yán)格地對應(yīng)兩個進(jìn)程;3)任意一對進(jìn)行通信的進(jìn)程,均嚴(yán)格地存在一條通信鏈;4)通信鏈?zhǔn)请p向的,可雙向傳輸

其中,send和receive原語定義為:

Send(P,message):發(fā)送message給進(jìn)程P;

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

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

2、間接通信,又稱郵箱(mailbox)通訊方式進(jìn)程間通過信箱實現(xiàn)通信郵箱是一種數(shù)據(jù)結(jié)構(gòu),結(jié)構(gòu)如圖2-20

使用信箱的規(guī)則:1)若發(fā)送信件時郵箱已滿,則發(fā)送進(jìn)程被置為“等郵箱”狀態(tài),直到信箱有空時才被釋放。2)若取信件時信箱中無信,則接收進(jìn)程被置為“等信件”狀態(tài),直到有信件時才被釋放。2.4進(jìn)程通信圖2-20郵箱結(jié)構(gòu)2.4.2消息通信

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

send實現(xiàn)步驟如下所示:{查找指定郵箱A;若郵箱未滿,則把信件message送入郵箱且釋放“等信件”者;若郵箱已滿置發(fā)送信件進(jìn)程為“等郵箱”狀態(tài);}receive實現(xiàn)步驟如下所示:{查找指定郵箱A;若郵箱中有信,則取出一封信存于message中且釋放“等郵箱”者;若郵箱中無信件則置接收信件進(jìn)程“等信件”狀態(tài);}2.4.2消息通信

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論