第2章進程管理

第二部分

進程管理

南昌大學(xué)信息管理系

NanChangUniversityDepartmentofinformationmanager1２.1進程的基本概念22.1.1

程序的順序執(zhí)行及特征1、程序的順序執(zhí)行程序分若干程序段，各程序段之間必須按某種先后順序執(zhí)行，僅當前一操作（程序段）執(zhí)行完后，才能執(zhí)行后繼操作。例如：S1:a:=x+y;

S2:b:=a-5;

S3:c:=b+1;S2必須在S1句后,S3必須在S2句.3又如:輸入、計算、執(zhí)行I1C1p1I2c2p2

I：輸入操作，C：計算操作，P：打印操作

41、順序性2、封閉性3、可再現(xiàn)性2、程序順序執(zhí)行時的特征52.1.2前趨圖前趨圖:

是一個有向無循環(huán)圖DAG(DirectedAcyclicGraph)

，描述進程之間執(zhí)行的前后關(guān)系。結(jié)點：描述一個程序段或進程或一條語句有向邊：表示結(jié)點之間存在的前趨關(guān)系。記為“”6前趨關(guān)系表示:={(Pi,Pj

)|PimustcompletebeforePjmaystart如果(Pi,Pj),可寫成PiPj稱Pi是Pj的直接前趨,而稱Pj是Pi的直接后繼初始結(jié)點:

沒有前趨的結(jié)點終止結(jié)點:沒有后繼的結(jié)點7存在前趨關(guān)系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P5→P7,P6→P7或P={P1,P2,P3,P4,P5,P6,P7}→={(P1,P2)(P1,P3)(

P1,P4)(P2,P5)(P3,P5)(P4,P6)(P5,P7)(P6,P7)}P7P1P3P4P5P6P282.1.3程序并發(fā)執(zhí)行

1、程序并發(fā)執(zhí)行

9I1I2I3I4C1C2C3C4P1P2P3P4相互合作資源共享IiCiIiIi+1CiPiCiCi+1PiPi+1Ii+1和Ci及Pi-1是重疊的。亦即Pi-1和CI以及Ii+1可以并發(fā)執(zhí)行。101、間斷性2、失去封閉性3、不可再現(xiàn)性2、程序并發(fā)執(zhí)行時的特征11例如:兩個循環(huán)程序A和B，它們共享一個變量N。程序A每執(zhí)行一次時，都要做N:=N+1操作；程序B則每執(zhí)行一次時，都要執(zhí)行Print（N）操作，然后再將N置成“0”，程序A和B以不同的速度運行。假定某時刻:N=n則:

12A程序在B程序之前執(zhí)行1、N:=N+1在Print（N）和N:=0之前2、N:=N+1在Print（N）和N:=0之后

3、N:=N+1在Print（N）和N:=0之間

N值分別為n+1，n+1，0N值分別為n，0，1N值分別為n，n+1，0132.1.4進程的特征與狀態(tài)

由于程序執(zhí)行結(jié)果的不可再現(xiàn)性，使得程序不能參與并發(fā)執(zhí)行。為使程序能并發(fā)執(zhí)行，且為了對并發(fā)執(zhí)行的程序加以描述，引入“進程”的概念。１.進程的特征與定義14進程的定義（1）進程是程序的一次執(zhí)行；（2）

進程是可以和別的計算并發(fā)執(zhí)行的計算；（3）

進程可定義為一個數(shù)據(jù)結(jié)構(gòu)及能在其上進行操作的一個程序；（4）

進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動；（5）

進程是程序在一個數(shù)據(jù)集合上的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。15進程的定義進程是進程實體的運行過程,是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。16進程的特征結(jié)構(gòu)特征：動態(tài)性：并發(fā)性：獨立性：異步性：進程實體是由程序段、數(shù)據(jù)段及進程控制塊三部分組成，有人把這三部分統(tǒng)稱為“進程映像”。進程是程序的一次執(zhí)行多個進程實體，同存在于內(nèi)存中，輪流占有處理機和各種資源，走走停停交叉運行。進程是一個獨立進行資源分配和調(diào)度運行的基本單位。這是指進程按各自獨立的、不可預(yù)知的速度向前推進，或者說進程按異步方式運行17進程和程序的區(qū)別：（1）程序是為了完成某項工作時需要計算機執(zhí)行的指令的集合，是靜態(tài)的概念；而進程是程序的執(zhí)行，是動態(tài)的概念。（2）程序是永遠存在的，進程則有生存期，它的存在是暫時的。（3）進程是一個獨立調(diào)度并能和其它進程并發(fā)運行的單位，而程序和程序段則不能作為一個獨立調(diào)度運行的單位，也不能并發(fā)執(zhí)行。182進程三種的基本狀態(tài)

1)就緒狀態(tài):當進程已分配到除CPU以外的所有必要的資源后,只要再獲得CPU便可立即執(zhí)行.

多個就緒狀態(tài)的進程排成一個隊列稱就緒隊列2)執(zhí)行狀態(tài):已獲得CPU,正在執(zhí)行.

單處理機系統(tǒng)–只要一個執(zhí)行狀態(tài)的進程,

多處理機系統(tǒng)–多個執(zhí)行狀態(tài)的進程192進程三種的基本狀態(tài)

(續(xù))3)阻塞狀態(tài)，又稱等待狀態(tài):正在執(zhí)行的進程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行,便放棄處理機,處于阻塞狀態(tài)(等待狀態(tài)).使進程阻塞的典型事件:請求I/O,申請緩沖空間.多個等待狀態(tài)的進程排成一個隊列稱等待隊列進程的三種基本狀態(tài)及其轉(zhuǎn)換P31圖2-520就緒執(zhí)行阻塞進程調(diào)度中斷I/O中斷或等待某事件I/O完成或事件發(fā)生進程狀態(tài)213.進程的掛起狀態(tài)1、終端用戶的需求2、

父進程的需求3、

負荷調(diào)節(jié)的需要4、OS的需要1)、引入掛起狀態(tài)的主要原因:由于進程的不斷創(chuàng)建，系統(tǒng)的資源已經(jīng)不能滿足進程運行的要求，這個時候就必須把某些進程掛起（suspend），對換到磁盤鏡像區(qū)中，暫時不參與進程調(diào)度，起到平滑系統(tǒng)操作負荷的目的

223.進程的掛起狀態(tài)(續(xù))

引入掛起狀態(tài)后,則:就緒狀態(tài)分為:活動就緒狀態(tài)和靜止就緒狀態(tài)活動就緒(Readya)靜止就緒(Readys)活動就緒(Readya):進程處于未被掛起的就緒狀態(tài)靜止就緒(Readys):調(diào)用掛起原語(Suspend)將進程掛起后,該進程便轉(zhuǎn)變?yōu)榈撵o止就緒狀態(tài).靜止就緒(Readys)活動就緒(Readya)處于Readys狀態(tài)的進程,若用激活原語(Active)激活后,該進程轉(zhuǎn)變?yōu)镽eadya狀態(tài).233.進程的掛起狀態(tài)(續(xù))

同樣:阻塞狀態(tài)分為:活動阻塞狀態(tài)和靜止阻塞狀態(tài)活動阻塞(Blockeda)靜止阻塞(Blockeds)活動阻塞(Blockeda):進程處于未被掛起的阻塞狀態(tài)靜止阻塞(Blockeds):進程處于活動阻塞時,調(diào)用掛起原語(Suspend)將進程掛起后,該進程便轉(zhuǎn)變?yōu)榈撵o止阻塞狀態(tài).靜止阻塞(Blockeds)活動阻塞(Blockeda)處于Blockeds狀態(tài)的進程,若用激活原語(Active)激活后,該進程轉(zhuǎn)變?yōu)锽lockeda狀態(tài).243.進程的掛起狀態(tài)(續(xù))

靜態(tài)就緒狀態(tài)表明了進程具備運行條件,但目前在二級存儲器中，只有當它被對換到主存才能被調(diào)度執(zhí)行。靜態(tài)等待狀態(tài)則表明了進程正在等待某一個事件且在二級存儲器中。

掛起的進程將不參與進程調(diào)度直到它們被對換進主存。具有如下特征：該進程不能立即被執(zhí)行。掛起進程可能會等待一個事件，但所等待的事件是獨立于掛起條件的，事件結(jié)束并不能導(dǎo)致進程具備執(zhí)行條件。進程進入掛起狀態(tài)是由于操作系統(tǒng)、父進程或進程本身阻止它的運行。結(jié)束進程掛起狀態(tài)的命令只能通過操作系統(tǒng)或父進程發(fā)出。

25具有掛起狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖活動就緒執(zhí)行靜止就緒靜止阻塞活動阻塞掛起激活掛起請求I/O掛起激活釋放等待事件結(jié)束

262.1.5進程控制塊(ProcessControlBlock)進程控制塊是一個記錄和刻劃進程狀態(tài)及有關(guān)信息的數(shù)據(jù)結(jié)構(gòu),是進程實體的一部分.使一個在多道環(huán)境下不能獨立運行的程序成為一個能獨立運行的基本單位.OS根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理.1、進程控制塊的作用272、進程控制塊中的信息

(1)進程標識符信息：用于唯一標識一個進程

外部標識符:用戶使用內(nèi)部標識符:系統(tǒng)使用28用于保留一個進程在運行時存放在處理器現(xiàn)場中的各種信息，任何一個進程在讓出處理器時必須把此時的處理器現(xiàn)場信息保存到進程控制塊中，而當該進程重新恢復(fù)運行時也應(yīng)恢復(fù)處理器現(xiàn)場。常用的現(xiàn)場信息包括通用寄存器的內(nèi)容、控制寄存器(如PSW寄存器)的內(nèi)容、用戶堆棧指針、系統(tǒng)堆棧指針等。(2)處理機狀態(tài)信息29(3)進程調(diào)度信息進程的當前狀態(tài)；進程的優(yōu)先級；進程調(diào)度所需的其它信息；如進程已等待CPU的時間總和、進程已執(zhí)行的時間總和等；事件；是指進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因30程序和數(shù)據(jù)的地址，是指進程的程序和數(shù)據(jù)所在的內(nèi)存或外存地（首）址資，以便再調(diào)度到該進程執(zhí)行時，能從PCB中找到其程序和數(shù)據(jù)；實現(xiàn)進程同步和通信相關(guān)信息，如消息隊列指針、信號量；資源清單：包括進程所需全部資源、已經(jīng)分得的資源。鏈接指針：給出了本進程PCB所在隊列中的下一個進程的PCB首地址(4)進程控制信息313、PCB的組織方式

(1).鏈接方式

把具有相同狀態(tài)的PCB，用其中的鏈接字，鏈接成一個隊列。32Page33圖2-7PCB鏈接隊列示意圖33(2).索引方式圖2-834頁342.2進程控制

進程圖是用于描述進程家族關(guān)系的有向樹。2.2.1進程的創(chuàng)建

1、進程圖（ProcessGraph）35ABCDEFGHI子進程父進程祖父進程祖先進程362、引起創(chuàng)建進程的事件

(1)、

用戶登錄:分時系統(tǒng)中,有新的合法的登錄命令(2)、作業(yè)調(diào)度:批處理系統(tǒng)中,作業(yè)調(diào)度時(3)、提供服務(wù):運行中的用戶程序提出某種請求時,系統(tǒng)專門創(chuàng)建一個進程來提供所需的服務(wù),例如:p35(4)、應(yīng)用請求

:用戶進程根據(jù)需要創(chuàng)建子進程373、進程的創(chuàng)建

(1)

、申請空白PCB:申請獲得唯一的數(shù)字標識符,并從PCB集合中索取一個空白PCB(2)

、為新進程分配資源:為新進程的程序和數(shù)據(jù)以及用戶棧分配必要的內(nèi)存空間.(3)

、初始化進程控制塊:初始化標識符(填入PCB);初始化處理機,使程序計數(shù)器指向程序的入口地址,使棧指針指向棧頂;初始化進程控制信息,設(shè)置為“就緒狀態(tài)”,設(shè)置優(yōu)先級(通常缺省優(yōu)先級).(4)

、將新進程插入就緒隊列382.2.2進程的終止

(1).正常結(jié)束：如Windows的exit指令，logoff退出等(2).異常結(jié)束：錯誤和故障而被迫使進程終止(3).外界干預(yù)：操作系統(tǒng)干預(yù)或父進程干預(yù)1、引起進程終止的事件2、進程的終止過程

調(diào)用進程終止原語終止指定進程。392.2.2進程的終止(續(xù))

2、進程的終止過程

OS調(diào)用進程終止原語終止指定進程。(1).根據(jù)進程標識符，檢索PCB,讀出進程狀態(tài)(2)若執(zhí)行狀態(tài)，立即終止，并要重新調(diào)度(3)同時終止該進程的子進程。(4)釋放該進程占有的資源(5)從所在的PCB隊列中移出402.2.3進程的阻塞和喚醒

(1)、請求系統(tǒng)服務(wù)但不能滿足

(2)、啟動某種操作,如進程啟動I/O操作,后,阻塞等待,在I/O完成后,由中斷進程喚醒本進程(3)、新數(shù)據(jù)尚未到達,同步進程未完成(4)、無新工作可做時,某些進程自阻塞,等待其它進程來喚醒1、引起進程阻塞和喚醒的事件典型事件：I/O請求；等待輸入。413、進程喚醒過程：2、進程阻塞過程：被阻塞的進程所期待的事件出現(xiàn)時,則由有關(guān)進程調(diào)用喚醒原語wakeup將等待該事件的進程喚醒.把被阻塞的進程從阻塞隊列移出,改狀態(tài)為就緒,插入到就緒中隊列,實現(xiàn)進程從阻塞狀態(tài)到就緒狀態(tài)的轉(zhuǎn)換。正在執(zhí)行的進程,一旦發(fā)現(xiàn)引起阻塞的事件,就調(diào)用阻塞原語block阻塞自己.進程狀態(tài)從執(zhí)行狀態(tài)改為阻塞狀態(tài)。,并將PCB插入到阻塞隊列.422.2.4進程的掛起與激活

1、掛起過程調(diào)用進程掛起原語suspend實現(xiàn)進程掛起檢查掛起進程的狀態(tài),若活動就緒靜止就緒若活動阻塞靜止阻塞若正在執(zhí)行靜止就緒,轉(zhuǎn)向調(diào)度程序重新調(diào)度432.2.4進程的掛起與激活(續(xù))2、激活過程調(diào)用激活原語active將指定進程激活.激活原語先將進程從二級內(nèi)存調(diào)入內(nèi)存,檢查進程狀態(tài):若靜止就緒活動就緒(若為搶占式調(diào)度,則比較被激活進程與當前正在執(zhí)行進程的優(yōu)先級,決定是否需要重新調(diào)度,若不需要按優(yōu)先級插入)若靜止阻塞活動阻塞442.3進程同步

452.3.1進程同步的基本概念

1.兩種形式的制約關(guān)系

(1).間接相互制約關(guān)系(互斥關(guān)系)

例如:有進程A和進程B，如果在進程A提出打印請求時，系統(tǒng)已將唯一的一臺打印機分配給了進程B，則此時進程A只能阻塞，一旦進程B將打印機釋放，才能使進程A由阻塞改變?yōu)榫途w狀態(tài)46(2).直接相互制約關(guān)系(合作關(guān)系)例如：有一進程A通過單向緩沖向進程B提供數(shù)據(jù)。當該緩沖空時，進程B因不能獲得所需數(shù)據(jù)而阻塞，而當進程A把數(shù)據(jù)輸入緩沖區(qū)后，便將進程B喚醒；反之，當緩沖區(qū)已滿時，進程A因不能再向緩沖區(qū)投放數(shù)據(jù)而阻塞，當進程B將緩沖區(qū)數(shù)據(jù)取走后便可喚醒進程A

如：catch1ch2ch3|greptree47

系統(tǒng)中的某些資源如打印機、磁帶機、卡片機，雖然它們可提供給多個進程使用，但在同一時間內(nèi)卻只允許一個進程訪問這些資源。當一個進程還在使用該資源時，其它欲訪問該資源的進程必須等待，僅當該進程訪問完畢并釋放資源后，才允許另一進程對該資源訪問。這種同一時間內(nèi)只允許一個進程訪問的資源稱臨界資源，許多物理設(shè)備，以及數(shù)據(jù)都是臨界資源，它們只能互斥地被共享。2.臨界資源

48著名的生產(chǎn)者--消費者(Producer-ConsumerProblem)問題是計算機操作系統(tǒng)中并發(fā)進程內(nèi)在關(guān)系的一種抽象，是典型的進程同步問題。在操作系統(tǒng)中，生產(chǎn)者進程可以是計算進程、發(fā)送進程；而消費者進程可以是打印進程、接收進程等等。解決好了生產(chǎn)者--消費者問題就解決好了一類并發(fā)進程的同步問題。49問題描述：一群生產(chǎn)者進程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費者進程去消費。為生產(chǎn)者進程和消費者進程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個具有n個緩沖區(qū)的緩沖池。生產(chǎn)者進程將它所生產(chǎn)的產(chǎn)品放入緩沖池，消費者進程可以從緩沖池中取走產(chǎn)品去消費。只要緩沖區(qū)未滿，生產(chǎn)者生產(chǎn)的產(chǎn)品就可投入緩沖池；類似地，只要緩沖池不空，消費者進程就可從緩沖池取走并消耗產(chǎn)品。50

用數(shù)組buffer表示n個（0，1，…，n-1）緩沖區(qū)的緩沖池，用輸入指針in來指示下一個可投放消息的緩沖區(qū)，用輸出指針out來指示下一個可獲取消息的緩沖區(qū)。in=（in+1）modn；out=（out+1）modn；當（in+1）modn=out時，表示緩沖池滿;當in=out表示緩沖池空。整型變量counter，初值為0；生產(chǎn)者投放一個消息counter+1；消費者進程從中取走一個消息時，counter-1。51Varn:integer;Typeitem=…;Varbuffer=array[0,1,…n-1]ofitem;In,out:0,1,…n-1;Counter:0,1,…n;52Producer:repeat┆ produceaniteminnextp; ┆ whilecounter=ndono-op; buffer[in]:=nextp; in:=in+1modn; counter:=counter+1;untilfalse;緩沖池滿，空操作，測試局部變量，暫存剛生產(chǎn)出的消息生產(chǎn)者進程往緩沖區(qū)投放消息，輸入指針加1生產(chǎn)者投放-消息53consumer:repeat whilecounter=odono-op;

nextc:=buffer[out]; out:=out+1modn; counter:=counter-1; consumetheiteminnextc;untilfalse;緩沖池空，空操作，測試局部變量存放要消費的消息消費一消息，輸出指針加1消費者消費一消息54這兩個進程共享變量counter，生產(chǎn)者對它做加1操作，消費者對它做減1操作，這兩個操作在用機器語言實現(xiàn)時?？捎孟旅嫘问矫枋觯簉egister1:=counter;register1:=register1+1;counter:=register1;register2:=counter;register2:=register2-1;counter:=register2;55register1=5register1=6register2=5register2=4counter=6counter=4程序的執(zhí)行不具有可再現(xiàn)性。解決問題的關(guān)鍵:把變量counter作為臨界資源處理。register1:=counter;register1:=register1+1;register2:=counter;register2:=register2-1;counter:=register1;counter:=register2;563.臨界區(qū)

(CriticalSection)我們把每個進程中訪問臨界資源的那段代碼(一段程序)稱為臨界區(qū)。在進入臨界區(qū)之前，對欲訪問的臨界資源進行檢查，看它是否可以被訪問，如果此刻該臨界資源未被訪問，進程便可進入該臨界區(qū)對該資源進行訪問，并設(shè)置它正被訪問的標志；這段用于檢查的代碼稱為進入?yún)^(qū)（entrysection)。而在臨界區(qū)后用于將臨界區(qū)正被訪問的標志恢復(fù)為未被訪問的標志的一段代碼稱為退出區(qū)(exitsection)57描述訪問臨界資源的循環(huán)進程：

repeatentrysection

criticalsection

exitsectionremaindersectionuntilfalse;進入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)584、同步機制應(yīng)遵循的準則

(1)、空閑讓進(2)、忙則等待(3)、有限等待(4)、讓權(quán)等待59假定兩個進程Pi和Pj共享一個臨界資源R。使Pi和Pj互斥訪問資源R的一般性描述：Begin parentbegin

Pi;

Pj; parentendend２.3.2信號量機制

60

wait(s)：whileS≤0donoopP操作

S:=S-1;signal(s)：S:=S+1;V操作wait(s)和signal(s)是兩個原子操作，因此它們在執(zhí)行時是不可中斷的。１、整型信號量

61在整型信號量機制中的wait操作，信號量S≤0，就會不斷地測試，該機制并未遵循“讓權(quán)等待”的準則，而是使該進程處于“忙等”的狀態(tài)。622、記錄型信號量機制

typesemaphore=record value:integer; L:listofprocess;ends.value資源信號量等待信號量鏈表S.L63Procedurewait(s)varS:Semaphore;begin s.value:=s.value-1;ifs.value<0thenblock(S.L)endProceduresignal(s)vars:semaphore;begins.value:=s.value+1;

ifs.value≤0thenwakeup(S,L);end64P.V操作討論1)信號量的物理含義：S>0表示有S個資源可用S=0表示無資源可用S<0則|S|表示S等待隊列中的進程個數(shù)P(S):表示申請一個資源V(S)表示釋放一個資源。信號量的初值應(yīng)該大于等于065

AND同步機制的基本思想是：對若干個臨界資源的分配，采取原子操作方式，要么全部分配到進程，要么一個也不分配，這樣可以避免死鎖。在wait操作中增加了一個“AND”條件，故稱為AND同步，或稱為同時wait操作。3、AND型信號量機制

66procedureSwait(s1，．．．sn)beginifs1>=1&．．．&sn>=1thenfori:=1tondosi:=si-1;

endfor

elsebegin

進程進入第一個迂到的滿足si<1條件的si信號量隊列等待，同時將該進程的程序計數(shù)器地址回退，置為SP操作處。

end67Ssignal(S1,d1，…Sn，dn)fori:=1tondo Si:=Si+dI; Removealltheprocesswaitinginthequeue associatedwithSiintothereadyqueue.endfor;684、信號量集

在記錄型和AND信號量機制中，P、V或SP、SV僅僅能對信號量施行增1或減1操作，每次只能獲得或釋放一個臨界資源。當一請求n個資源時，便需要n次信號量操作，這樣做效率很低。此外，在有些情況下，當資源數(shù)量小于一個下限時，便不預(yù)分配。為此，可以在分配之前，測試某資源的數(shù)量是否大于閥值t。對AND型信號量機制作擴充，便形成了一般型信號量機制。69Swait(S1，t1，d1，…Sn，tn，dn) ifS1≥t1and…andSn≥tnthen fori:=1tondo

Si:=Si-di;

endforelse PlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi<tiandsetitsprogramcountertothebeginningoftheSwaitOperation.

endif;70Ssingnal(S1,d1，…Sn，dn)fori:=1tondo Si:=Si+dI; Removealltheprocesswaitinginthequeue

ussociatedwithSiintothereadyqueue.endfor;71（1）Swait(S，t，d)（2）Swait(S，1，1)（3）Swait(S，1，0)“信號量集”的幾種特殊情況：72２.3.３信號量的應(yīng)用

73varmutex:semaphore:=1;beginparbegin

process1:begin repeat wait(mutex); criticalsection; signal(mutex);

remaindersection; untilfalse;endprocess2:beginrepeat wait(mutex);criticalseition;

signal(mutex);

remainderseetion

untilfalseend

parend

end1、利用信號量實現(xiàn)互斥

74

P1，P2是并發(fā)執(zhí)行的進程，P1有語句S1，P2有語句S2，我們希望S1執(zhí)行后再執(zhí)行S2

。在P1中，用S1；signal(s)；在P2中，用wait(s)；S2；使P1和P2共享一個信號量S，其初值為0２、利用信號量來實現(xiàn)前趨關(guān)系

75S1S2S3S4S5S6abcdefg76vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbegin

beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(d);S5;signal(g);end; beginwait(e);wait(f);wait(g);S6;end;parend;end772.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者—消費者問題2.4.2

哲學(xué)家進餐問題2.4.3讀者—寫者問題782.4.1生產(chǎn)者—消費者問題互斥信號量mutex

:實現(xiàn)對緩沖池的互斥使用;

資源信號量empty:表示空緩沖區(qū)的數(shù)量;full:表示滿緩沖區(qū)的數(shù)量。

1、利用記錄型信號量解決生產(chǎn)者—消費者問題問題描述：同前79Varmutex,empty,full:semaphore:=1,n,0;

Buffer:array[0,…,n-1]ofitem;In,out:integer:=0,0;Beginparbegin

procedure:beginrepeat┇

procedureaniteminnextp;┇

wait(empty);//*wait(mutex);//*//以上兩句改變順序會死鎖

buffer(in):=nextp;

in:=(in+1)modn;

signal(mutex);

signal(full);untilfalse;endconsumer:beginrepeat

wait(full);wait(mutex);

nextc:=buffer(out);out:=(out+1)modn;

signal(mutex);signal(empty);

consumetheiteminnextc;untilfalse;endparendend80注意：(1)用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對出現(xiàn)。(2)對資源信號量empty和full的wait和signal操作，也需要成對出現(xiàn)，但是處于不同的程序中。(3)wait操作順序不能顛倒，先執(zhí)行對資源信號量的wait操作，再執(zhí)行對互斥信號量的wait操作，否則會引起死鎖。81wait(empty);wait(mutex);buffer(in):=nextp;

in:=(in+1)modn;signal(mutex);signal(full);

wait(mutex);wait(empty);//errorbuffer(in):=nextp;

in:=(in+1)modn;signal(mutex);signal(full);

wait(full);wait(mutex);

nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);

82錯誤1：wait(s)與signal(s)次序顛倒。

signal(mutex);

criticalsection

wait(mutex);

用mutex實現(xiàn)進程互斥時，若將wait(s)與signal(s)顛倒,會使多個進程同時進入臨界區(qū)83錯誤2：實現(xiàn)進程互斥時，將signal(mutex)誤寫作wait(mutex)

wait(mutex)；

criticalsectionwait(mutex)；

出錯的進程無法喚醒84錯誤3：實現(xiàn)進程互斥時，在程序中遺漏了wait(mutex)操作，會使多個進程活躍在臨界區(qū)；而遺漏了signal(mutex)操作，則會使其它進程無法再進入臨界區(qū)。

852、利用AND信號量解決生產(chǎn)者—消費者問題

Varmutex,empty,full:semaphore:=1,n,0;

Buffer:array[0,…,n-1]ofitem;In,out:integer:=0,0;Beginparbegin

procedure:beginrepeat┇

procedureaniteminnextp;┇

Swait(empty,mutex); buffer(in):=nextp;

in:=(in+1)modn;

Ssignal(mutex,full);

untilfalse;endconsumer:beginrepeat

Swait(full,mutex);

nextc:=buffer(out);out:=(out+1)modn;

Ssignal(mutex,empty);

consumetheiteminnextc;untilfalse;endparendend86有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子，每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉，為了吃通心粉，每個哲學(xué)家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子。2.4.2

哲學(xué)家進餐問題

問題描述：87

哲學(xué)家用餐問題有益于模擬進程爭奪有限資源—例如磁帶驅(qū)動器或者別的I/0設(shè)備——的互斥性訪問權(quán)。

這里筷子是臨界資源，在一段時間內(nèi)只允許一個哲學(xué)家使用。因此，可以用一個信號量表示一支筷子，由這五個信號量構(gòu)成信號量數(shù)組。分析：88varchopstick;array[0,…,4]ofsemaphore=(1,1,1,1,1);/*所有信號量初始化為1repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);┇eat;┇signal(chopstick[i]);signal(chopstick[(i+1)mod5]);┇think;untilfalse;1.利用記錄型信號量解決哲學(xué)家進餐問題

89以上解答有可能發(fā)生死鎖!對于這樣的死鎖問題可采取以下幾種解決方法：（1）至多只允許四個哲學(xué)家同時進餐，以保證至少有一個哲學(xué)家能進餐，最終釋放出他所使用過的兩支筷子，從而可使更多的哲學(xué)家就餐。（2）僅當哲學(xué)家的左、右兩支筷子均可用時，才允許他拿起筷子進餐。（3）奇數(shù)號哲學(xué)家先拿左邊的筷子，再去拿右邊的筷子，而偶數(shù)呢相反，最后總會有一個哲學(xué)家能獲得兩支筷子而進餐。902、利用AND信號量解決哲學(xué)家就餐問題varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1)

processirepeatthink;Swait(chopstick[(i+1)mod5],chopstick[i]);Eat;Ssignal(chopstick[(i+1)mod5],chopstick[i]);

untilfalse;//可以解決上種解法所存在的死鎖問題!912.4.3讀者—寫者問題

有兩組并發(fā)進程：讀者和寫者，共享一個文件F，要求：(1)允許多個讀者同時執(zhí)行讀操作;(2)任一寫者在完成寫操作之前不允許其它讀者或?qū)懻吖ぷ?(3)寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出。

問題描述：92分析：有讀進程在讀，寫進程不能寫有讀進程在讀，其他讀進程可進入讀有寫進程在寫，其他寫進程和讀進程無法進入寫或讀93互斥信號量Wmutex：實現(xiàn)reader進程與writer進程讀或?qū)憰r的互斥。整型變量readcount：表示正在讀的進程數(shù)目。

互斥信號量Rmutex

：實現(xiàn)多個reader進程對readcount

的訪問。

設(shè)：94VarRmutex,Wmutex:=semaphore:=1,1;readcount:integer:=0;beginparbegin

reader:beginrepeatwait(Rmutex);ifreadcount=0thenwait(Wmutex);readcount:=readcount+1;signal(Rmutex);┇performreadoperation;┇wait(Rmutex)readcount:=readcount-1;ifreadcount=0thensignal(Wmutex);signal(Rmutex);untilfalse;end

writer:beginrepeatwait(Wmutex);performwriteoperation;signal(Wmutex);untilfalseendparendend

1.利用記錄型信號量解決讀者—寫者問題

95由于只要有一個reader進程在讀，便不允許writer進程去寫。因此，僅當readcount=0時，表示沒有reader進程在讀時，reader進程才需要執(zhí)行wait(Wmutex)操作。

若readcount≠0，表示已有讀進程去讀，而讀進程是允許多個同時讀的。僅當reader進程在執(zhí)行了readcount-1操作后，其值為0時，才需執(zhí)行signal(Wmutex)以便讓writer進程進程寫。96Readcounter=0既無讀進程又無寫進程雖無讀進程但有寫進程臨界資源Rmutex用于互斥97２.利用信號量集機制解決讀者—寫者問題增加了一條限制：最多允許RN個讀者同時讀。為此，又引入了一個信號量L，并賦予初值為RN，通過執(zhí)行Swait(L,1,1)操作，來控制讀者讀者的數(shù)目。

98varRNinteger;L,mx:semaphore:=RN,1;beginparbegin

reader:beginrepeatSwait(L,1,1);Swait(mx,1,0);┇performreadoperation┇Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperationSsignal(mx,1);untilfalse;endparendendmx=1允許多個讀進程進入；mx=0阻止任何讀進程進入

L>=RN時，既無讀進程也無寫進程99缺點：（１）易讀性差（２）不利于修改和維護

(３）正確性難以保證2.5管程機制

管程的提出:

采用PV同步機制來編寫并發(fā)程序，對于共享變量及信號量變量的操作將被分散于各個進程中一種新的同步機制--管程1002.5.1管程的基本概念

1、管程的定義

一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)。

管程

局部于管程的共享變量說明

對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程

對局部于管程的數(shù)據(jù)設(shè)置初始值的語句

管程名字101管程的語法為：

typemonitor-name=monitorvariabledeclarations共享變量說明

procedureentryP1(…);begin…end;procedureentryP2(…);begin…end;┇procedureentryPn(…);begin…end;begininitializationcode初始化代碼

end

組過程102

管程的主要特性：（一）模塊化，一個管程是一個基本程序單位，可以單獨編譯（二）抽象數(shù)據(jù)類型，管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)進行操作的代碼（三）管程中的共享變量在管程外部是不可見的，外部只能通過調(diào)用管程中所說明的外部過程（函數(shù)）來間接地訪問管程中的共享變量(四）為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進入1032、條件變量

為了區(qū)別等待的原因，又引入了條件變量condition。每個獨立的條件變量是和進程可能等待的不同原因相聯(lián)系的。

當定義了一個條件變量時，就建立了一個隊列，等待該條件的進程被連到這個隊列上。

104varx,y:condition

表示：

x.waitx.signal

nonbusy:conditionnonbusy.waitnonbusy.signal例如：1052.5.2利用管程解決生產(chǎn)者—消費者問題

procedure-consumer：（1）put(item)過程

（2）get(item)過程

106Typeprocedure-consumer=monitor

名字varin,out,count:integer;

共享變量buffer:array[0,…,,n-1]ofitem;notfull,notempty:condition;procedureentryput(item)

管程入口

beginifcount≥nthennotfull.wait;

//阻塞等待不滿的進程

//并把它連到等待不滿的隊列上。

buffer(in):=nextp;

in:=(in+1)modn;count:=count+1;

ifnotempty.queuethennotempty.signal;//若有等待不空的進程里有，

//則喚醒隊首進程;如果沒有等待不空的進程，則不操作

end//。107Procedureentyget(item)管程入口

Beginifcount≤0thennotempty.wait

//阻塞等待不空的

//進程，并把它連接到等待不空的隊列上

nextc:=buffer(out);out:=(out+1)modn;

count:=count-1;

//若有等待不滿的隊列里有進程，

//喚醒隊首進程

ifnotfull.queuethennotfull.signal;endbeginin:=out:=0;count:=0;end

初始化

108在利用管程解決生產(chǎn)者—消費者問題時，其中的生產(chǎn)者和消費者可描述為：procedure:beginrepeatproduceoninteminnextp;PC.put(item);untilfalse;endConsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end

1092.6進程通信

進程間通信意味著在進程間傳送數(shù)據(jù)，也就是說，在進程之間進行信息交換。

進程通信高級通信:如果要在進程間傳遞大量信息則要用Send/Receive原語（高級通訊原語）低級通信:

P.V操作實現(xiàn)的是進程之間的低級通訊，所以P.V為低級通訊原語。它只能傳遞簡單的信號，不能傳遞交換大量信息1102.6.1進程通信的類型

共享存儲器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)基于共享存儲區(qū)消息傳遞系統(tǒng)直接通信方式間接通信方式管道通信互斥、同步、對方是否存在1112.6.2消息傳遞通信的實現(xiàn)方法

1、直接通信方式

發(fā)送進程發(fā)消息時要指定接收進程的名字，反過來，接收時要指明發(fā)送進程的名字Send(Receiver,message);Receive(Sender,message);*對稱形式：一對一*非對稱形式：多對一（顧客/服務(wù)員）Receive(id,message);112repeat:┇produceaniteminnextp;┇send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);┇consumetheiteminnextc;untilfalse;

生產(chǎn)者、消費者的通信過程如下：1132、間接通信方式信箱頭信箱體信箱發(fā)送進程發(fā)消息時不指定接收進程的名字，而是指定一個中間媒介，即信箱。進程間通過信箱實現(xiàn)通信114Receive(mailbox,message)從指定信箱中接收一個消息。

（1）信箱的創(chuàng)建和撤消。（2）消息的發(fā)送和接收。Send(mailbox,message)將一個消息，發(fā)送到指定信箱。115信箱分為三類：（1）私用信箱（2）公用信箱（3）共享信箱也稱共享文件方式，基于文件系統(tǒng)，利用一個打開的共享文件連接兩個相互通信的進程，文件作為緩沖傳輸介質(zhì)3管道通信(Pipe)1162.6.3消息傳遞系統(tǒng)中的幾個問題

1、通信鏈路2、消息的格式 消息頭：控制信息。 消息正文：發(fā)送進程實際所發(fā)送的數(shù)據(jù)。3、進程同步方式

1、發(fā)送進程阻塞，接收進程阻塞

2、發(fā)送進程不阻塞、接收進程阻塞

3、發(fā)送進程和接收進程均不阻塞1172.6.4消息緩沖隊列通信機制

1、消息緩沖隊列通信機制中的數(shù)據(jù)結(jié)構(gòu)

(1)、消息緩沖區(qū)，可描述為：typemessagebuffer=recordsender;發(fā)送者進程標識符

size;消息長度

text;消息正文

next;指向下一個消息緩沖區(qū)的指令針

end118(2)、PCB中有關(guān)通信的數(shù)據(jù)項進程標識符信息進程控制塊的信息處理機狀態(tài)信息進程調(diào)度信息進程控制信息

119

利用消息緩沖隊列通信機制中，在PCB中應(yīng)增加的數(shù)據(jù)項為：typeprocesscontrolblock=reeord

┇mg;消息隊列隊首指針

mutex;消息隊列互斥信號量

sm;消息隊列資源信號量┇

end1202、發(fā)送原語

Proceduresend(receiver,a)begingetbuf(a.size,i);i.sender:=a.sender;i.size:=a.size;i.text:=a.text;i.next:=0;

getid(PCBset,receiver,j);wait(j.mutex);

insert(j,mg,i);signal(j,mutex);signal(j.sm);end121procedurereceive(b)beginj:=internalname;wait(j.sm);wait(j.mutex);remove(j.mg,i);signal(j.mutex);b.sender:=i.sender;b.text:=i.text;end3、接收原語1222.7線程線程的引