第2章進(jìn)程管理

第二部分

進(jìn)程管理

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

NanChangUniversityDepartmentofinformationmanager1２.1進(jìn)程的基本概念22.1.1

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

S2:b:=a-5;

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

I：輸入操作，C：計(jì)算操作，P：打印操作

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

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

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

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

沒有前趨的結(jié)點(diǎn)終止結(jié)點(diǎn):沒有后繼的結(jié)點(diǎn)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í)行時(shí)的特征11例如:兩個(gè)循環(huán)程序A和B，它們共享一個(gè)變量N。程序A每執(zhí)行一次時(shí)，都要做N:=N+1操作；程序B則每執(zhí)行一次時(shí)，都要執(zhí)行Print（N）操作，然后再將N置成“0”，程序A和B以不同的速度運(yùn)行。假定某時(shí)刻: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進(jìn)程的特征與狀態(tài)

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

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

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

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

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

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

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

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

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

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

父進(jìn)程的需求3、

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

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

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

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

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

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

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

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

(1)進(jìn)程標(biāo)識(shí)符信息：用于唯一標(biāo)識(shí)一個(gè)進(jìn)程

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

(1).鏈接方式

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

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

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

(1)、

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

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

(1)

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

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

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

、將新進(jìn)程插入就緒隊(duì)列382.2.2進(jìn)程的終止

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

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

2、進(jìn)程的終止過程

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

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

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

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

452.3.1進(jìn)程同步的基本概念

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

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

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

如：catch1ch2ch3|greptree47

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

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

用數(shù)組buffer表示n個(gè)（0，1，…，n-1）緩沖區(qū)的緩沖池，用輸入指針in來指示下一個(gè)可投放消息的緩沖區(qū)，用輸出指針out來指示下一個(gè)可獲取消息的緩沖區(qū)。in=（in+1）modn；out=（out+1）modn；當(dāng)（in+1）modn=out時(shí)，表示緩沖池滿;當(dāng)in=out表示緩沖池空。整型變量counter，初值為0；生產(chǎn)者投放一個(gè)消息counter+1；消費(fèi)者進(jìn)程從中取走一個(gè)消息時(shí)，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)者進(jìn)程往緩沖區(qū)投放消息，輸入指針加1生產(chǎn)者投放-消息53consumer:repeat whilecounter=odono-op;

nextc:=buffer[out]; out:=out+1modn; counter:=counter-1; consumetheiteminnextc;untilfalse;緩沖池空，空操作，測試局部變量存放要消費(fèi)的消息消費(fèi)一消息，輸出指針加1消費(fèi)者消費(fèi)一消息54這兩個(gè)進(jìn)程共享變量counter，生產(chǎn)者對它做加1操作，消費(fèi)者對它做減1操作，這兩個(gè)操作在用機(jī)器語言實(shí)現(xiàn)時(shí)?？捎孟旅嫘问矫枋觯簉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)我們把每個(gè)進(jìn)程中訪問臨界資源的那段代碼(一段程序)稱為臨界區(qū)。在進(jìn)入臨界區(qū)之前，對欲訪問的臨界資源進(jìn)行檢查，看它是否可以被訪問，如果此刻該臨界資源未被訪問，進(jìn)程便可進(jìn)入該臨界區(qū)對該資源進(jìn)行訪問，并設(shè)置它正被訪問的標(biāo)志；這段用于檢查的代碼稱為進(jìn)入?yún)^(qū)（entrysection)。而在臨界區(qū)后用于將臨界區(qū)正被訪問的標(biāo)志恢復(fù)為未被訪問的標(biāo)志的一段代碼稱為退出區(qū)(exitsection)57描述訪問臨界資源的循環(huán)進(jìn)程：

repeatentrysection

criticalsection

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

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

Pi;

Pj; parentendend２.3.2信號(hào)量機(jī)制

60

wait(s)：whileS≤0donoopP操作

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

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

typesemaphore=record value:integer; L:listofprocess;ends.value資源信號(hào)量等待信號(hào)量鏈表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)信號(hào)量的物理含義：S>0表示有S個(gè)資源可用S=0表示無資源可用S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)P(S):表示申請一個(gè)資源V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于065

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

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

endfor

elsebegin

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

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

在記錄型和AND信號(hào)量機(jī)制中，P、V或SP、SV僅僅能對信號(hào)量施行增1或減1操作，每次只能獲得或釋放一個(gè)臨界資源。當(dāng)一請求n個(gè)資源時(shí)，便需要n次信號(hào)量操作，這樣做效率很低。此外，在有些情況下，當(dāng)資源數(shù)量小于一個(gè)下限時(shí)，便不預(yù)分配。為此，可以在分配之前，測試某資源的數(shù)量是否大于閥值t。對AND型信號(hào)量機(jī)制作擴(kuò)充，便形成了一般型信號(hào)量機(jī)制。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)“信號(hào)量集”的幾種特殊情況：72２.3.３信號(hào)量的應(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、利用信號(hào)量實(shí)現(xiàn)互斥

74

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

。在P1中，用S1；signal(s)；在P2中，用wait(s)；S2；使P1和P2共享一個(gè)信號(hào)量S，其初值為0２、利用信號(hào)量來實(shí)現(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)典進(jìn)程的同步問題2.4.1生產(chǎn)者—消費(fèi)者問題2.4.2

哲學(xué)家進(jìn)餐問題2.4.3讀者—寫者問題782.4.1生產(chǎn)者—消費(fèi)者問題互斥信號(hào)量mutex

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

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

1、利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問題問題描述：同前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);//*//以上兩句改變順序會(huì)死鎖

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)用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對出現(xiàn)。(2)對資源信號(hào)量empty和full的wait和signal操作，也需要成對出現(xiàn)，但是處于不同的程序中。(3)wait操作順序不能顛倒，先執(zhí)行對資源信號(hào)量的wait操作，再執(zhí)行對互斥信號(hào)量的wait操作，否則會(huì)引起死鎖。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錯(cuò)誤1：wait(s)與signal(s)次序顛倒。

signal(mutex);

criticalsection

wait(mutex);

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

wait(mutex)；

criticalsectionwait(mutex)；

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

852、利用AND信號(hào)量解決生產(chǎn)者—消費(fèi)者問題

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

哲學(xué)家進(jìn)餐問題

問題描述：87

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

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

89以上解答有可能發(fā)生死鎖!對于這樣的死鎖問題可采取以下幾種解決方法：（1）至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐，以保證至少有一個(gè)哲學(xué)家能進(jìn)餐，最終釋放出他所使用過的兩支筷子，從而可使更多的哲學(xué)家就餐。（2）僅當(dāng)哲學(xué)家的左、右兩支筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。（3）奇數(shù)號(hào)哲學(xué)家先拿左邊的筷子，再去拿右邊的筷子，而偶數(shù)呢相反，最后總會(huì)有一個(gè)哲學(xué)家能獲得兩支筷子而進(jìn)餐。902、利用AND信號(hào)量解決哲學(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ā)進(jìn)程：讀者和寫者，共享一個(gè)文件F，要求：(1)允許多個(gè)讀者同時(shí)執(zhí)行讀操作;(2)任一寫者在完成寫操作之前不允許其它讀者或?qū)懻吖ぷ?(3)寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出。

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

互斥信號(hào)量Rmutex

：實(shí)現(xiàn)多個(gè)reader進(jìn)程對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.利用記錄型信號(hào)量解決讀者—寫者問題

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

若readcount≠0，表示已有讀進(jìn)程去讀，而讀進(jìn)程是允許多個(gè)同時(shí)讀的。僅當(dāng)reader進(jìn)程在執(zhí)行了readcount-1操作后，其值為0時(shí)，才需執(zhí)行signal(Wmutex)以便讓writer進(jìn)程進(jìn)程寫。96Readcounter=0既無讀進(jìn)程又無寫進(jìn)程雖無讀進(jìn)程但有寫進(jìn)程臨界資源Rmutex用于互斥97２.利用信號(hào)量集機(jī)制解決讀者—寫者問題增加了一條限制：最多允許RN個(gè)讀者同時(shí)讀。為此，又引入了一個(gè)信號(hào)量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允許多個(gè)讀進(jìn)程進(jìn)入；mx=0阻止任何讀進(jìn)程進(jìn)入

L>=RN時(shí)，既無讀進(jìn)程也無寫進(jìn)程99缺點(diǎn)：（１）易讀性差（２）不利于修改和維護(hù)

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

管程的提出:

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

1、管程的定義

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

管程

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

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

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

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

typemonitor-name=monitorvariabledeclarations共享變量說明

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

end

組過程102

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

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

當(dāng)定義了一個(gè)條件變量時(shí)，就建立了一個(gè)隊(duì)列，等待該條件的進(jìn)程被連到這個(gè)隊(duì)列上。

104varx,y:condition

表示：

x.waitx.signal

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

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;

//阻塞等待不滿的進(jìn)程

//并把它連到等待不滿的隊(duì)列上。

buffer(in):=nextp;

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

ifnotempty.queuethennotempty.signal;//若有等待不空的進(jìn)程里有，

//則喚醒隊(duì)首進(jìn)程;如果沒有等待不空的進(jìn)程，則不操作

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

Beginifcount≤0thennotempty.wait

//阻塞等待不空的

//進(jìn)程，并把它連接到等待不空的隊(duì)列上

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

count:=count-1;

//若有等待不滿的隊(duì)列里有進(jìn)程，

//喚醒隊(duì)首進(jìn)程

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

初始化

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

1092.6進(jìn)程通信

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

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

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

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

1、直接通信方式

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

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

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

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

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

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

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

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

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

size;消息長度

text;消息正文

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

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

119

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

┇mg;消息隊(duì)列隊(duì)首指針

mutex;消息隊(duì)列互斥信號(hào)量

sm;消息隊(duì)列資源信號(hào)量┇

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線程線程的引