操作系統(tǒng)原理第二章

1

計(jì)算機(jī)操作系統(tǒng)主講:四川大學(xué)計(jì)算機(jī)學(xué)院

劉循liuxun@2

第2章進(jìn)程的描述與控制

為了描述程序在并發(fā)執(zhí)行時(shí)對(duì)系統(tǒng)資源的共享，我們需要一個(gè)描述程序執(zhí)行時(shí)動(dòng)態(tài)特征的概念，這就是進(jìn)程。在本章中，我們將討論進(jìn)程概念、進(jìn)程控制和進(jìn)程間關(guān)系。3本章內(nèi)容:進(jìn)程的基本概念進(jìn)程控制進(jìn)程同步經(jīng)典進(jìn)程的同步問(wèn)題管程機(jī)制進(jìn)程通信線程42.1進(jìn)程的基本概念前驅(qū)圖程序順序執(zhí)行及其特征程序并發(fā)執(zhí)行及其特征程序的特征與狀態(tài)進(jìn)程控制塊5

前驅(qū)圖是一個(gè)有向無(wú)循環(huán)圖.

圖中每個(gè)結(jié)點(diǎn)可用于表示一條語(yǔ)句、一個(gè)程序段或進(jìn)程；

結(jié)點(diǎn)間的有向邊則表示在兩結(jié)點(diǎn)之間存在的偏序或前趨關(guān)系“→”,如果Pi→Pj,稱Pi是Pj的前趨，而Pi是Pj的直接后繼.2.1.1前驅(qū)圖6123456

在前趨圖中，沒(méi)有前趨的結(jié)點(diǎn)稱為初始站點(diǎn)(InitialNode)，沒(méi)有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(FinalNode)。

每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，它可用該結(jié)點(diǎn)所含的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間來(lái)計(jì)量。2.1.1前驅(qū)圖72.1.2程序順序執(zhí)行及其特征1程序的順序執(zhí)行

s1:a:=x+y;s2:b:=a-5;s3:c:=b+1;程序按固定的流程執(zhí)行下去：S1S2S382程序順序執(zhí)行的特征：(1)順序性-完成前一操作才能進(jìn)入下一操作；(2)封閉性-運(yùn)行時(shí)獨(dú)占資源,結(jié)果不受外界影響；(3)可再現(xiàn)性-多次執(zhí)行結(jié)果一致。I1C1P1I2C2P22.1.2程序順序執(zhí)行及其特征92.1.3程序并發(fā)執(zhí)行及其特征1.程序的并發(fā)執(zhí)行三個(gè)進(jìn)行輸入﹑計(jì)算﹑打印的程序并發(fā)執(zhí)行：I1I2I3I4C1C2C3C4P1P2P3P410s1:a:=x+2;s2:b:=y+4;s3:c:=a+b;s4:d:=c+b;2.1.3程序并發(fā)執(zhí)行及其特征S1S3S4S2112.程序并發(fā)執(zhí)行時(shí)的特征間斷性；失去封閉性；不可再現(xiàn)性。2.1.3程序并發(fā)執(zhí)行及其特征12例:程序A和B，如果A:N=N+1,B:Print(N)，

N的初始值為n

若執(zhí)行順序?yàn)?

N:=N+1;print(N);N:=0;則N值為n+1,n+1,0;

若執(zhí)行順序?yàn)?

print(N);

N:=N+1;N:=0;則N值為n,n+1,0;

若執(zhí)行順序?yàn)?

print(N);N:=0;

N:=N+1;為則N值為n,0,1;

可見(jiàn)并發(fā)執(zhí)行時(shí)程序結(jié)果不可再現(xiàn).2.1.3程序并發(fā)執(zhí)行及其特征13程序并發(fā)執(zhí)行的條件

程序并發(fā)執(zhí)行，雖然能有效地提高資源利用率和系統(tǒng)的吞吐量，但必須采取某種措施，以便并發(fā)程序能保持其“可再現(xiàn)性”。

2.1.3程序并發(fā)執(zhí)行及其特征14

定義符號(hào)：R(Pi)＝{a1,a2…,am},用以表示程序A在執(zhí)行期間所需參考的所有變量的集合，稱為“讀集“;W(pi)＝{b1,b2…,bn},是程序pi在執(zhí)行期間要改變的所有變量的集合，稱為“寫集”。 若兩個(gè)程序P1和p2能滿足下述條件，它們便能并發(fā)執(zhí)行，且具有可再現(xiàn)性。該條件在1966年首先由Bernstein提出．又稱為Bernstein條件：R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}。2.1.3程序并發(fā)執(zhí)行及其特征15

例:有四條語(yǔ)句:

S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1S1:a:=x+y的讀集為R(S1)={x,y},寫集為W(S1)={a};S2:b:=z+1的讀集為R(S2)={z},寫集為W(S2)=;S3:c:=a–b的讀集為R(S3)={a,b},寫集為W(S3)={c};S4:w:=c+1的讀集為R(S4)={c},寫集為W(S4)={w};16可見(jiàn):R(S1)∩W(S2)∪R(S2)∩W(S1)∪W(S1)∩W(S2)={},S1與S2可以并發(fā);R(S1)∩W(S4)∪R(S4)∩W(S1)∪W(S1)∩W(S4)={},S1與S4可以并發(fā);R(S1)∩W(S3)∪R(S3)∩W(S1)∪W(S1)∩W(S3)≠{},S1與S3不可并發(fā);R(S2)∩W(S3)∪R(S3)∩W(S2)∪W(S2)∩W(S3)≠{},S2與S3不可并發(fā);172.2進(jìn)程的描述進(jìn)程的定義和特征進(jìn)程的基本狀態(tài)及轉(zhuǎn)換掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)182.2.1進(jìn)程的定義和特征

它對(duì)應(yīng)虛擬處理機(jī)、虛擬存儲(chǔ)器和虛擬外設(shè)等資源的分配和回收；引入多進(jìn)程，提高了對(duì)硬件資源的利用率，但又帶來(lái)額外的空間和時(shí)間開(kāi)銷，增加了OS的復(fù)雜性.

1進(jìn)程的定義定義：可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。192.進(jìn)程的特征動(dòng)態(tài)性：進(jìn)程是程序的執(zhí)行過(guò)程,創(chuàng)建而產(chǎn)生﹑調(diào)度而執(zhí)行﹑撤消而消亡；獨(dú)立性：各進(jìn)程的地址空間相互獨(dú)立，除非采用進(jìn)程間通信手段；并發(fā)性:進(jìn)程可以并發(fā)執(zhí)行,而程序卻不能.異步性：“虛擬”；結(jié)構(gòu)特征：進(jìn)程實(shí)體由程序段、數(shù)據(jù)段和進(jìn)程控制快組成,統(tǒng)稱為“進(jìn)程映像”。2.2.1進(jìn)程的定義和特征201進(jìn)程的三種基本狀態(tài)

進(jìn)程在運(yùn)行中不斷地改變其運(yùn)行狀態(tài)。通常，一個(gè)運(yùn)行進(jìn)程必須具有以下三種基本狀態(tài):

(1)就緒狀態(tài)(Read)-得到除處理機(jī)外所有資源; (2)執(zhí)行狀態(tài)(Run)-獲得了處理機(jī); (3)阻塞狀態(tài)(Block)-因某事件暫停執(zhí)行;

如果再加上”新(New)狀態(tài)”,”終止(Terminated)狀態(tài)”共有5種狀態(tài)。2.2.2進(jìn)程的基本狀態(tài)及轉(zhuǎn)換21進(jìn)程的狀態(tài)及其轉(zhuǎn)換IO請(qǐng)求或其他事件運(yùn)行就緒阻塞進(jìn)程調(diào)度中斷等待的事件完成新進(jìn)程結(jié)束2.2.2進(jìn)程的基本狀態(tài)及轉(zhuǎn)換2三種基本狀態(tài)的轉(zhuǎn)換22

1進(jìn)程的掛起狀態(tài)

(1)掛起狀態(tài)的引入:終端用戶的需要:發(fā)現(xiàn)運(yùn)行情況時(shí)終端用戶希望程序停下來(lái).父進(jìn)程的需要:父進(jìn)程要協(xié)調(diào)各子進(jìn)程之間關(guān)系.操作系統(tǒng)的需要:掛起進(jìn)程檢查資源使用情況.對(duì)換的需要:掛起對(duì)換的進(jìn)程.負(fù)荷調(diào)節(jié)的需要:掛起進(jìn)程減輕負(fù)荷.2.2.3掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換23進(jìn)程的狀態(tài)及其轉(zhuǎn)換IO請(qǐng)求或其他事件

運(yùn)行活動(dòng)就緒活動(dòng)阻塞進(jìn)程調(diào)度中斷等待的事件完成(2)引入掛起狀態(tài)的轉(zhuǎn)換圖靜止阻塞靜止就緒創(chuàng)建結(jié)束等待的事件完成掛起掛起釋放釋放2.2.3掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換

2引入掛起原語(yǔ)操作后三個(gè)進(jìn)程狀態(tài)的轉(zhuǎn)換242.2.4進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)1.操作系統(tǒng)中用于管理控制的數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)系統(tǒng)中，對(duì)于每個(gè)資源和每個(gè)進(jìn)程都設(shè)置了一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于表征其實(shí)體，稱之為資源信息表或進(jìn)程信息表，其中包含了資源或進(jìn)程的標(biāo)識(shí)、描述、狀態(tài)等信息以及一批指針。OS管理這些數(shù)據(jù)結(jié)構(gòu)一般分為以下四類：內(nèi)存表設(shè)備表文件表用于進(jìn)程管理的進(jìn)程表252.2.4進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)2.進(jìn)程控制塊PCB的作用為了描述和控制進(jìn)程的運(yùn)行，系統(tǒng)為每個(gè)進(jìn)程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)——進(jìn)程控制塊（PCB-ProcessControlBlock）,它是由OS維護(hù)的用來(lái)記錄進(jìn)程相關(guān)信息的唯一標(biāo)志，當(dāng)OS創(chuàng)建一個(gè)進(jìn)程時(shí)，就為該進(jìn)程創(chuàng)建了一個(gè)PCB。263.進(jìn)程控制塊中的信息:進(jìn)程標(biāo)識(shí)符信息(內(nèi)-外標(biāo)識(shí)符);處理機(jī)狀態(tài)信息(通用寄存器﹑指令寄存器﹑程序狀態(tài)字﹑用戶棧指針);進(jìn)程調(diào)度信息(進(jìn)程狀態(tài)﹑進(jìn)程優(yōu)先級(jí)﹑進(jìn)程調(diào)度所需的其它信息﹑事件----阻塞因);進(jìn)程控制信息(程序和數(shù)據(jù)地址﹑進(jìn)程同步和進(jìn)程通信機(jī)制﹑資源清單﹑鏈接指針).2.2.4進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)274.進(jìn)程控制塊的組織方式鏈接方式：各狀態(tài)的進(jìn)程形成不同的鏈表：就緒鏈表、阻塞鏈表.索引方式：同一狀態(tài)的進(jìn)程歸入一個(gè)index表（由index指向PCB），多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的index表,各狀態(tài)的運(yùn)行形成不同的索引表：就緒索引表、阻塞索引表.2.2.4進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)28作業(yè)：P84:2,4,7,8292.3進(jìn)程控制

操作系統(tǒng)內(nèi)核進(jìn)程的創(chuàng)建進(jìn)程的終止進(jìn)程的阻塞與喚醒進(jìn)程的掛起與激活302.3進(jìn)程控制

為了提供對(duì)PCB(和OS其它數(shù)據(jù))的保護(hù),通常將處理機(jī)的執(zhí)行狀態(tài)分為系統(tǒng)態(tài)和用戶態(tài)兩種:系統(tǒng)態(tài):又稱作特權(quán)方式，內(nèi)核方式，管理方式,控制方式.用戶態(tài):通常用戶程序運(yùn)行在用戶態(tài).31

將一些與硬件緊密相關(guān)的模塊:中斷處理程序，各種常用設(shè)備的驅(qū)動(dòng)程序，以及運(yùn)行頻率較高的模塊都安排在緊靠硬件的軟件層次中，并使它們常駐內(nèi)存，以便提高OS的運(yùn)行效率,并對(duì)它們加以特殊的保護(hù)。通常把這一部分稱為OS的內(nèi)核。2.3.1操作系統(tǒng)內(nèi)核321支撐功能中斷處理時(shí)鐘管理原語(yǔ)操作2.3.1操作系統(tǒng)內(nèi)核332資源管理功能進(jìn)程管理存儲(chǔ)器管理設(shè)備管理2.3.1操作系統(tǒng)內(nèi)核34

2.3.2進(jìn)程的創(chuàng)建1.進(jìn)程的層次結(jié)構(gòu)

在OS中，允許一個(gè)進(jìn)程創(chuàng)建另一個(gè)進(jìn)程，通常把創(chuàng)建進(jìn)程的進(jìn)程稱為父進(jìn)程，而把被創(chuàng)建的進(jìn)程稱為子進(jìn)程。子進(jìn)程可以創(chuàng)建跟多的孫進(jìn)程，由此便形成了一個(gè)進(jìn)程的層次結(jié)構(gòu)。352.3.2進(jìn)程的創(chuàng)建2.進(jìn)程圖ABCDEFGHIJBCBCBC362.3.2進(jìn)程的創(chuàng)建3引起進(jìn)程創(chuàng)建的事件:

--用戶登陸

--作業(yè)調(diào)度

--提供服務(wù)

--應(yīng)用請(qǐng)求

372.3.2進(jìn)程的創(chuàng)建4進(jìn)程的創(chuàng)建步驟

--申請(qǐng)空白PCB --為新進(jìn)程分配資源

--初始化進(jìn)程控制塊

--將新進(jìn)程插入就緒隊(duì)列381.引起進(jìn)程終止的事件

--正常結(jié)束

--異常結(jié)束:越界﹑保護(hù)錯(cuò)﹑特權(quán)指令錯(cuò)﹑非法指令錯(cuò)﹑運(yùn)行超時(shí)﹑等待超時(shí)﹑算術(shù)運(yùn)算錯(cuò)﹑I/O故障

--外界干預(yù):操作員或操作系統(tǒng)﹑父進(jìn)程請(qǐng)求﹑父進(jìn)程終止2.3.3進(jìn)程的終止392.進(jìn)程的終止過(guò)程：(1)根據(jù)被終止進(jìn)程的標(biāo)識(shí)符．從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)。(2)若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即中止該進(jìn)程的執(zhí)行．并設(shè)置調(diào)度標(biāo)志為真．用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度．選擇——新進(jìn)程，把處理機(jī)分配結(jié)它。2.3.3進(jìn)程的終止402.進(jìn)程的終止過(guò)程：(3)若該進(jìn)程還有子、孫進(jìn)程，還將其所有子孫進(jìn)程予以終止，以防它們成為不可控的。(4)將該進(jìn)程所擁行的全部資源，或者歸還給其父進(jìn)程，或者歸還給系統(tǒng)。(5)將被終止進(jìn)程(它的PCB)從所在隊(duì)列(或鏈表)中移出，等待其它程序來(lái)搜集信息。2.3.3進(jìn)程的終止412.3.4進(jìn)程的阻塞與喚醒1.引起進(jìn)程阻塞和喚醒的事件:請(qǐng)求系統(tǒng)服務(wù);啟動(dòng)某種操作;新數(shù)據(jù)尚未到來(lái);無(wú)新工作可做.422.進(jìn)程阻塞過(guò)程:

正在執(zhí)行的進(jìn)程，當(dāng)發(fā)現(xiàn)引起進(jìn)程阻塞的事件時(shí)，無(wú)法繼續(xù)執(zhí)行，便停止執(zhí)行﹑改PCB中狀態(tài)﹑插入到阻塞隊(duì)列﹑保留處理機(jī)狀態(tài).3.進(jìn)程喚醒過(guò)程:

阻塞的進(jìn)程，當(dāng)發(fā)現(xiàn)引起進(jìn)程阻塞的事件已經(jīng)完成時(shí)，便從阻塞隊(duì)列中移出﹑改PCB中狀態(tài)﹑插入就緒隊(duì)列.2.3.3進(jìn)程的阻塞與喚醒432.3.5進(jìn)程的掛起與激活

用戶請(qǐng)求將自己掛起或父進(jìn)程請(qǐng)求將自己的某個(gè)子進(jìn)程掛起時(shí)，系統(tǒng)利用掛起原語(yǔ)，將進(jìn)程掛起。父進(jìn)程或用戶請(qǐng)求激活指定的進(jìn)程時(shí)，用激活原語(yǔ)激活進(jìn)程。進(jìn)程的掛起過(guò)程:原語(yǔ):suspend();進(jìn)程的激活過(guò)程:原語(yǔ):active();掛起激活A(yù)ctive()Suspend()442.4進(jìn)程的同步引入進(jìn)程同步的主要任務(wù):

使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。即保證諸進(jìn)程互斥地訪問(wèn)臨界資源。452.4.1進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系(1)間接相互制約關(guān)系多進(jìn)程資源共享（互斥):

例如：打印機(jī)中打印進(jìn)程A，B.(2)直接相互制約關(guān)系:

表現(xiàn)為多進(jìn)程執(zhí)行順序有先后關(guān)系。buffer生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程462.4.1進(jìn)程同步的基本概念2臨界資源

定義:

在某一時(shí)刻只能一個(gè)進(jìn)程獨(dú)占的資源.

例如:

硬件:打印機(jī),繪圖儀,掃描儀等.

軟件:數(shù)據(jù)變量﹑參數(shù)等。47生產(chǎn)者——消費(fèi)者問(wèn)題:

有n個(gè)緩沖區(qū)的緩沖池;in指示下一個(gè)可投放消息的緩沖區(qū),生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)消息后in+1;out指示下一個(gè)可獲取消息緩沖區(qū),消費(fèi)者進(jìn)程消費(fèi)并取走一個(gè)消息后out+1;

循環(huán)緩沖池:in:=(in+1)modn;out:=(out+1)modn;2.4.1進(jìn)程同步的基本概念482.4.1進(jìn)程同步的基本概念共享下列變量:varn,integer;typeitem=…;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;in,out初始化為1;當(dāng)兩個(gè)進(jìn)程單獨(dú)執(zhí)行時(shí)沒(méi)有問(wèn)題:492.4.1進(jìn)程同步的基本概念

Producer:Repeat

……

produceaniteminnexto;

…….whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;Untilfalse;

502.4.1進(jìn)程同步的基本概念Consumer:Repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumetheiteminnextc;Untilfalse；51當(dāng)兩個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)可能按以下順序發(fā)生:register1:=counter;register2:=counter;register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2;

當(dāng)counter=5時(shí)上面執(zhí)行后正確答案為5(生產(chǎn)一個(gè),消費(fèi)一個(gè));2.4.1進(jìn)程同步的基本概念52但是也可以按以下順序發(fā)生:(同樣counter=5)register1:=counter;(register1=5)register1:=register1+1;(register1=6)register2:=counter;(register2=5)register2:=register2-1;(register2=4)counter:=register1;(counter=6)counter:=register2;(counter=4)

結(jié)果counter=4,與前面的結(jié)果不一致,程序并發(fā)執(zhí)行的結(jié)果不可再現(xiàn).原因是變量counter是一個(gè)臨界資源,應(yīng)互斥訪問(wèn).53

3臨界區(qū)（Criticalsection）

每個(gè)進(jìn)程中訪問(wèn)臨界資源的代碼段就是臨界區(qū).

repeatentrysection;(進(jìn)入?yún)^(qū))

criticalsection;(臨界區(qū))

exitsection;(退出區(qū))

remaindersection

（剩余區(qū)）

untilfalse

2.4.1進(jìn)程同步的基本概念544同步機(jī)制應(yīng)遵循的準(zhǔn)則

(1)空閑讓進(jìn)

(2)忙則等待

(3)有限等待

(4)讓權(quán)等待2.4.1進(jìn)程同步的基本概念55用軟件方法解決進(jìn)程互斥問(wèn)題(1)算法1:

變量turn表示允許進(jìn)入臨界區(qū)的進(jìn)程編號(hào)

repeatwhileturn≠idono-op;criticalsection;turn:=j;remaindersectionuntilfalse;

存在問(wèn)題是:同一進(jìn)程不能連續(xù)的進(jìn)入臨界區(qū).違背空閑讓進(jìn)的原則.2.4.1進(jìn)程同步的基本概念56算法2:設(shè)置一個(gè)數(shù)組flag[i];flag[i]=true進(jìn)程Pi正在臨界區(qū);

初始值flag[i]=false所有進(jìn)程未進(jìn)入臨界區(qū);varflag:array[0,1,…,n]ofboolean;

2.4.1進(jìn)程同步的基本概念57repeatwhileflag[j]dono-op;flag[i]:=true;

criticalsection;

flag[i]:=false;remaindersectionuntilfalse;

存在問(wèn)題:多個(gè)進(jìn)程都看到對(duì)方?jīng)]進(jìn)臨界區(qū)而決定進(jìn)去時(shí)則會(huì)發(fā)生沖突,互不相讓.違背忙則等待的原則.2.4.1進(jìn)程同步的基本概念58算法3:設(shè)置一個(gè)數(shù)組flag[i];flag[i]=true進(jìn)程Pi希望進(jìn)入臨界區(qū);

同時(shí)滿足flag[j]=false時(shí)才進(jìn)入臨界區(qū);varflag:array[0,1,…,n]ofboolean;2.4.1進(jìn)程同步的基本概念59repeatflag[i]:=true;whileflag[j]dono-op;

criticalsection;

flag[i]:=false;remaindersectionuntilfalse;

存在問(wèn)題:多個(gè)進(jìn)程首先表示自己要進(jìn)入臨界區(qū),再去判斷其余進(jìn)程是否會(huì)進(jìn)入臨界區(qū),結(jié)果是都認(rèn)為對(duì)方會(huì)進(jìn)入臨界區(qū)而謙讓,都不進(jìn)去.違背空閑讓進(jìn)的原則.2.4.1進(jìn)程同步的基本概念602.4.1進(jìn)程同步的基本概念算法4:設(shè)置一個(gè)數(shù)組flag[i]和一個(gè)變量turn;

一個(gè)進(jìn)程為了進(jìn)入臨界區(qū)flag[i]=true,turn=j;

同時(shí)滿足flag[j]=false或者turn=i時(shí)才進(jìn)入臨界區(qū);varflag:array[0,1,…,n]ofboolean;

61repeatflag[i]:=true;turn:=j;while(flag[j]andturn=j)dono-op;

criticalsection;

flag[i]:=false;remaindersectionuntilfalse;

不存在問(wèn)題.2.4.1進(jìn)程同步的基本概念622.4.2硬件同步機(jī)制

1關(guān)中斷

關(guān)中斷試試先互斥的最簡(jiǎn)單的方法之一。在進(jìn)入鎖測(cè)試之前關(guān)閉中斷，知道完成鎖測(cè)試并上鎖之后才能打開(kāi)中斷。這樣，進(jìn)程在臨界區(qū)執(zhí)行期間，計(jì)算機(jī)系統(tǒng)不響應(yīng)中斷，從而不會(huì)引發(fā)調(diào)度，也就不會(huì)發(fā)生進(jìn)程或線程切換。

缺點(diǎn)：濫用關(guān)中斷權(quán)力可能導(dǎo)致嚴(yán)重后果。關(guān)中斷時(shí)間過(guò)長(zhǎng)會(huì)影響系統(tǒng)效率。關(guān)中斷方法不適用與多CPU系統(tǒng)。632.4.2硬件同步機(jī)制

2利用Test-and-Set指令實(shí)現(xiàn)互斥指令:FunctionTS(varlock:boolean):booleanbeginTS:=lock;lock:=ture;end;64利用TS實(shí)現(xiàn)進(jìn)程互斥:repeatwhileTS(lock)doskip;criticalsectionlock:=false;remaindersectionuntilfalse;2.4.2硬件同步機(jī)制652.4.2硬件同步機(jī)制3利用Swap指令實(shí)現(xiàn)互斥Swap指令:ProcedureSwap(vara,b:boolean)vartemp:boolean;begintemp:=a;a:=b;b:=temp;end;662.4.2硬件同步機(jī)制利用Swap實(shí)現(xiàn)進(jìn)程互斥:repeatkey:=true;repeatSwap(lock,key);untilkey=false;criticalsectionlock:=false;remaindersectionuntilfalse;672.4.3信號(hào)量機(jī)制Dijkstra把互斥的關(guān)鍵含義抽象成信號(hào)量（semaphore)概念，并引入wait、signal操作作為同步源語(yǔ)。信號(hào)量是被保護(hù)的量，只有wait、signal操作和信號(hào)量初始化操作才能訪問(wèn)和改變它的值。

681整形信號(hào)量(1)Wait(s)、signal(s)操作定義wait（S）:whiles≤0dono-ops:=s-1;Signal(s)s=s+1;

注意:Wait(s)、signal(s)是兩個(gè)原子操作。整形信號(hào)量s的值為0還是1，當(dāng)s<=0時(shí)，Wait(s)操作會(huì)不停的進(jìn)行測(cè)試.并為遵循讓權(quán)等待。2.4.3信號(hào)量機(jī)制692.記錄型信號(hào)量2.4.3信號(hào)量機(jī)制Wait(s)、signal(s)操作定義typesemaphore=recordvalue:integer;L:Listofprocess;end;

702.4.3信號(hào)量機(jī)制2.記錄型信號(hào)量proceduresignal（s）

vars:semaphore;beginS.value:=S.value+1;ifS.value≤0thenwakeup(S,L)end;712.4.3信號(hào)量機(jī)制procedurewait（s）

vars:semaphore;beginS.value:=S.value-1;ifS.value<0thenblock(S,L)end;2.記錄型信號(hào)量722.4.3信號(hào)量機(jī)制2.記錄型信號(hào)量

在記錄型信號(hào)量中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目。因而又稱為資源信號(hào)量。當(dāng)S.value0<0時(shí)，表示資源已經(jīng)分配完畢，進(jìn)程調(diào)用block原語(yǔ)進(jìn)入阻塞狀態(tài)。

732.4.3信號(hào)量機(jī)制

ProducerA:ProducerB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);但是A進(jìn)程B按下述次序交替進(jìn)行：ProducerA:wait(Dmutex),Dmutex=0;ProducerB:wait(Emutex),Emutex=0;ProducerA:wait(Emutex),Emutex=-1,A阻塞;ProducerB:wait(Dmutex),Dmutex=-1,B阻塞;最后AB兩進(jìn)程都處于僵持狀態(tài)。3.AND型信號(hào)量742.4.3信號(hào)量機(jī)制

基本思想:將進(jìn)程在整個(gè)運(yùn)行過(guò)程中所需的所有臨界資源,一次性的全部分配給進(jìn)程,待該進(jìn)程使用完后再一起釋放.

3.AND型信號(hào)量752.4.3信號(hào)量機(jī)制Swait（S1,S2,…,Sn）

ifS1≥1and…andSn≥1thenfori:=1tondoSi:=Si-1;endfor;else

…….endif;3.AND型信號(hào)量762.4.3信號(hào)量機(jī)制Ssignal（S1,S2,…,Sn）

fori:=1tondoSi:=Si+1;

……endfor;3.AND型信號(hào)量772.4.3信號(hào)量機(jī)制4.信號(hào)量集一次需要N個(gè)某類臨界資源時(shí):Swait（S1,ti,d1,…Sn,tn,dn）

ifS1≥t1and…andSn≥tnthenfori=:=1tondoSi:=Si-di;endfor;else

…….endif;782.4.3信號(hào)量機(jī)制Ssignal（S1,d1,…Sn,dn）

fori:=1tondoSi:=Si+di;

……endfor;4.信號(hào)量集792.4.3信號(hào)量機(jī)制討論:Swait(S,d,d),此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量,但允許每次申請(qǐng)d個(gè)資源,當(dāng)發(fā)現(xiàn)資源少于d時(shí),不予分配;Swait(S,1,1),此時(shí)在信號(hào)量為記錄型信號(hào)量或互斥信號(hào)量.Swait(S,1,0),此時(shí)在信號(hào)量為可控開(kāi)關(guān).4.信號(hào)量集802.4.4信號(hào)量的應(yīng)用1.利用信號(hào)量實(shí)現(xiàn)互斥生產(chǎn)者-消費(fèi)者問(wèn)題:Varmutex:semaphore:=1;beginparbegin81Process1:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;end2.4.4信號(hào)量的應(yīng)用1.利用信號(hào)量實(shí)現(xiàn)互斥822.4.4信號(hào)量的應(yīng)用1.利用信號(hào)量實(shí)現(xiàn)互斥process2:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse；

end;parend832.利用信號(hào)量來(lái)描述前趨關(guān)系S1S2S3S4S5S62.4.4信號(hào)量的應(yīng)用842.4.4信號(hào)量的應(yīng)用vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbeginbeginS1;signai(a);signai(b);end;beginwait(a);S2;signai(c);signai(d);end;beginwait(b);S3;signai(e);end;beginwait(c);S4;signai(f);end;beginwait(d);S5;signai(g);end;beginwait(e);wait(f);wait(g);S6;end;parend;end;852.4.5管程機(jī)制1.管程的定義

系統(tǒng)中的各種硬件資源和軟件資源均可用數(shù)據(jù)結(jié)構(gòu)抽象得描述其資源特性，即用少量信息和對(duì)該資源所執(zhí)行的操作來(lái)表征該資源，而忽略它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。因此，可以利用共享數(shù)據(jù)結(jié)構(gòu)抽象地表示系統(tǒng)中的共享資源，并且將對(duì)該共享數(shù)據(jù)結(jié)構(gòu)實(shí)施的特定操作定義為一組過(guò)程。進(jìn)程對(duì)共享資源的申請(qǐng)、釋放和其他操作必須通過(guò)這組過(guò)程，有效得實(shí)現(xiàn)進(jìn)程互斥。

代表共享資源的數(shù)據(jù)結(jié)構(gòu)以及由對(duì)該共享數(shù)據(jù)結(jié)構(gòu)實(shí)施操作的一組過(guò)程所組成的資源管理程序共同構(gòu)成了一個(gè)操作系統(tǒng)的資源管理模塊，稱之為管程。862.4.5管程機(jī)制2.條件變量

同常，一個(gè)進(jìn)程被阻塞或者掛起的條件可有多個(gè)，因此在管程中設(shè)置了多個(gè)條件變量。

管程中的條件變量都須予以說(shuō)明，其形式為：conditionx,y；對(duì)條件變量的操作僅僅是wait和signal，因此條件變量也是一個(gè)抽象得數(shù)據(jù)類型。(1)x.wait:正在調(diào)用管程的進(jìn)程因條件x需要被阻塞或掛起，則調(diào)用x.wait將自己插入到x條件的等待隊(duì)列上，并釋放管程，直到x條件變化。此時(shí)其他進(jìn)程可以使用該管程。(2)x.signal:正在調(diào)用管程的進(jìn)程發(fā)現(xiàn)x條件發(fā)生了變化，則調(diào)用x.signal，重新啟動(dòng)一個(gè)因x條件而阻塞或掛起的進(jìn)程，如果存在多個(gè)這樣的進(jìn)程，則選擇其中一個(gè)，如果沒(méi)有，繼續(xù)執(zhí)行原進(jìn)程，不產(chǎn)生任何結(jié)果。87

2.5經(jīng)典進(jìn)程同步問(wèn)題生產(chǎn)者——消費(fèi)者問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題讀者寫者問(wèn)題882.5.1生產(chǎn)者——消費(fèi)者問(wèn)題

生產(chǎn)者—消費(fèi)者是同步與互斥的抽象.在前面已對(duì)該問(wèn)題作了描述,但未考慮進(jìn)程的互斥與同步問(wèn)題,造成了數(shù)據(jù)counter的不確定性.下面用信號(hào)量機(jī)制解決該問(wèn)題.89

設(shè):生產(chǎn)者和消費(fèi)者之間的共用緩沖池中具有n個(gè)緩沖區(qū),利用互斥信號(hào)量mutex使兩進(jìn)程實(shí)現(xiàn)對(duì)緩沖區(qū)的互斥利用.利用資源信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和緩沖池中滿緩沖區(qū)的數(shù)量.生產(chǎn)者和消費(fèi)者相互等效,只要緩沖池未滿,生產(chǎn)者可向緩沖池中送入消息;只要緩沖池未空,消費(fèi)者可從緩沖池中取走消息;1利用記錄型信號(hào)量解決生產(chǎn)者---消費(fèi)者問(wèn)題2.5.1生產(chǎn)者——消費(fèi)者問(wèn)題90varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,1,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin1利用記錄型信號(hào)量解決生產(chǎn)者---消費(fèi)者問(wèn)題2.5.1生產(chǎn)者——消費(fèi)者問(wèn)題91Producer:beginrepeat

…produceraniteminnextp;

…wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);untilfalse;end;92Consumer:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);consumetheiteminnextc;untilfalse；

end;93parend;End;1利用記錄型信號(hào)量解決生產(chǎn)者---消費(fèi)者問(wèn)題2.5.1生產(chǎn)者——消費(fèi)者問(wèn)題94

在本類問(wèn)題中要注意對(duì)互斥信號(hào)量mutex的操作wait(mutex)和signal(mutex)必須成對(duì)出現(xiàn):對(duì)資源信號(hào)量empty和full的操作wait(empty)和signal(empty)﹑wait(full)和signal(full)必須成對(duì)出現(xiàn),但分別處于不同的進(jìn)程程序中.如生產(chǎn)者進(jìn)程wait(empty)處于阻塞等待時(shí),則消費(fèi)者進(jìn)程signal(empty)將生產(chǎn)者進(jìn)程喚醒.在生產(chǎn)者進(jìn)程中的wait(empty)和wait(mutex)﹑消費(fèi)者進(jìn)程中的wait(full)和wait(mutex)的前后順序不能寫反,否則會(huì)引起兩個(gè)進(jìn)程死鎖.先釋放互斥信號(hào)量mutex,后釋放資源信號(hào)量有利于提高兩個(gè)進(jìn)程訪問(wèn)臨界資源(緩沖區(qū))的速度.95用Swait(empty,mutex)代替wait(empty)和wait(mutex);用Ssignal(mutex,full)代替signal(mutex)和signal(full);用Swait(full,mutex)代替wait(full)和wait(mutex);用Ssignal(mutex,empty)代替signal(mutex)和signal(empty);2.利用AND信號(hào)量解決生產(chǎn)者---消費(fèi)者問(wèn)題2.5.1生產(chǎn)者——消費(fèi)者問(wèn)題96varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,1,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin2.利用AND信號(hào)量解決生產(chǎn)者---消費(fèi)者問(wèn)題2.5.1生產(chǎn)者——消費(fèi)者問(wèn)題97Producer:beginrepeat

…produceraniteminnextp;

…Swait(empty,mutex);buffer(in):=nextp;in:=(in+1)modn;Ssignal(mutex,full);untilfalse;end;98Consumer:beginrepeatSwait(full,mutex);nextc:=buffer(out);out:=(out+1)modn;Ssignal(mutex,empty);consumetheiteminnextc;untilfalse；

end;parend;End;99生產(chǎn)者—消費(fèi)者進(jìn)程:(1)建立管程:

為管程命名為PC,定義數(shù)據(jù)結(jié)構(gòu)如下:

變量count表示緩沖池中已有的消息數(shù)目.put(item)過(guò)程:當(dāng)count≥n,表示緩沖池滿,生產(chǎn)者等待.get(item)過(guò)程:當(dāng)count≤0,表示緩沖池空,消費(fèi)者等待.2.5.1生產(chǎn)者——消費(fèi)者問(wèn)題2.利用管程解決生產(chǎn)者---消費(fèi)者問(wèn)題100PC管程描述如下:typeproducer-consumer=monitorvarin,out,count:integer;buffer:array[0,1,…,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;101procedureentryget(item)beginifcount≤0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.queuethennotfull.signal;end;

beginin:=out:=0;count:=0;end;102(2)應(yīng)用管程:

producer:beginrepeatproduceaniteminnextp;

PC.put(item);untilfalse;end;consumer:beginrepeat

PC.get(item);consumetheiteminnextc;untilfalse;end;103

如圖:哲學(xué)家平時(shí)在思考，當(dāng)感到餓時(shí)就拿起左右兩邊的筷子用餐，用餐完畢放下筷子。只有在拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐完畢放下筷子繼續(xù)思考。2.5.2哲學(xué)家就餐問(wèn)題104

對(duì)問(wèn)題的解決方案：筷子作為臨界資源,在一段時(shí)間內(nèi)只允許一個(gè)哲學(xué)家使用,用一個(gè)信號(hào)量表示一只筷子,五支筷子用五個(gè)信號(hào)量,五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組:chopstick[1],chopstick[2],chopstick[3],chopstick[4],chopstick[5];1.利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題2.5.2哲學(xué)家就餐問(wèn)題105varchopstick:array[0,…,4]ofsemaphore;chopstick[i]=1;Repeatwait(chopstick[i]);wait(chopstick[(i+1)MOD5]);

…eat；

…signal(chopstick[i]);signal(chopstick[(i+1)MOD5);

…think；Untilfalse；106由于哲學(xué)家是圍著圓桌吃飯,5支筷子編號(hào)為1,2,3,4,5.所以要用mod運(yùn)算.哲學(xué)家先拿左邊的筷子再拿右邊的筷子,成功后便可進(jìn)餐,進(jìn)餐后先放左邊的筷子再放右邊的筷子,該方法可以保證不會(huì)有兩個(gè)相鄰的哲學(xué)家同時(shí)進(jìn)餐,但可能引起死鎖.因?yàn)榧偃缥鍌€(gè)哲學(xué)家同時(shí)拿起左邊的筷子時(shí),會(huì)因每個(gè)無(wú)第二只筷子可拿而無(wú)限等待,產(chǎn)生死鎖.107避免哲學(xué)家就餐死鎖的方法:最多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐,保證至少有一個(gè)哲學(xué)家能夠進(jìn)餐,最終總會(huì)釋放出他所使用過(guò)的兩支筷子,從而可使其他哲學(xué)家進(jìn)餐.當(dāng)哲學(xué)家左右兩支筷子均可用時(shí),才允許他拿起筷子進(jìn)餐.規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左邊的筷子再拿右邊的筷子;偶數(shù)號(hào)哲學(xué)家相反.1和2號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子,1和2號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子.即都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子,再競(jìng)爭(zhēng)偶數(shù)號(hào)筷子,最后總有一個(gè)哲學(xué)家可以獲得兩支筷子而進(jìn)餐.1082.利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題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；2.5.2哲學(xué)家就餐問(wèn)題109問(wèn)題的引出：一個(gè)數(shù)據(jù)文件或記錄(數(shù)據(jù)庫(kù)中的對(duì)象,如表或行)可供若干進(jìn)程共享，其中有些進(jìn)程要求讀;而另一些進(jìn)程要求寫或修改.把要求讀的進(jìn)程稱為“reader進(jìn)程”,把要求寫或修改的進(jìn)程稱為“writer進(jìn)程”.由于讀操作不會(huì)引起數(shù)據(jù)文件混亂,允許多個(gè)reader進(jìn)程同時(shí)讀一個(gè)數(shù)據(jù)對(duì)象,但不會(huì)允許一個(gè)writer進(jìn)程和其它writer進(jìn)程或reader進(jìn)程同時(shí)讀一個(gè)數(shù)據(jù)對(duì)象(可以用Bernstein條件驗(yàn)證).2.5.3讀者——寫者問(wèn)題110用互斥信號(hào)量wmutex實(shí)現(xiàn)reader進(jìn)程與writer進(jìn)程的讀或?qū)懙幕コ?用整形變量readcount表示正在讀的進(jìn)程數(shù)目,由于進(jìn)入讀和離開(kāi)讀的進(jìn)程都要寫改變量,該變量是臨界資源,用信號(hào)量rmutex實(shí)現(xiàn)互斥;只有readcounter=0時(shí),writer進(jìn)程才能寫或修改.1.利用記錄型信號(hào)量解決讀者---寫者問(wèn)題2.5.3讀者——寫者問(wèn)題111varrmutex,wmutex:semaphore:=1,1;readcouner:integer:=0;beginparbegin1.利用記錄型信號(hào)量解決讀者---寫者問(wèn)題2.5.3讀者——寫者問(wèn)題112reader:beginrepeatwait(rmutex);ifreadcounter=0thenwait(wmutex);readcounter:=readcounter+1;signal(rmutex);

…performreadoperation;

…wait(rmutex);readcounter:=readcounter-1;ifreadcounter=0thensignal(wmutex);signal(rmutex);untilfalse;end;113writer:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse；

end;parend;End;1142.利用信號(hào)量集機(jī)制解決讀者---寫者問(wèn)題增加一限制:最多只允許RN個(gè)讀者同時(shí)讀;引入信號(hào)量L,初值為RN;通過(guò)執(zhí)行wait(L,1,1)操作,控制讀者的數(shù)目,每當(dāng)有一個(gè)讀者進(jìn)入時(shí),都要先執(zhí)行wait(L,1,1)操作,使L的值減1,當(dāng)有RN個(gè)讀者進(jìn)入讀后,L便減為0,第RN+1個(gè)讀者要進(jìn)入讀時(shí)必然會(huì)因wait(L,1,1)操作失敗而阻塞.2.5.3讀者——寫者問(wèn)題115varRNinteger;L,mx:semaphore:=RN,1;beginparbegin2.利用信號(hào)量集機(jī)制解決讀者---寫者問(wèn)題2.5.3讀者——寫者問(wèn)題116reader:beginrepeatSwait(L,1,1);Swait(mx,1,0);

…performreadoperation;

…Ssignal(L,1);untilfalse;end;117writer:beginrepeatSwait(mx,1,1;L,RN,0);performwrteoperation;Ssignal(mx,1);untilfalse；

end;parend;End;118其中,Swait(mx,1,0)語(yǔ)句起著開(kāi)關(guān)的作用;只要無(wú)writer進(jìn)程進(jìn)入寫,mx=1,reader進(jìn)程就都可以進(jìn)入讀;只要一旦有進(jìn)程進(jìn)入寫時(shí),其mx=0,則任何reader進(jìn)程都無(wú)法進(jìn)入讀;Swait(mx,1,1,L,RN,0)語(yǔ)句表示僅當(dāng)即無(wú)writer進(jìn)程寫(mx=1)﹑又無(wú)reader進(jìn)程在讀(L=RN)時(shí),write進(jìn)程才能寫入臨界區(qū)寫.2.利用信號(hào)量集機(jī)制解決讀者---寫者問(wèn)題2.5.3讀者——寫者問(wèn)題119信號(hào)量其它應(yīng)用問(wèn)題

(1)下圖給出了四個(gè)進(jìn)程合作完成某個(gè)任務(wù)的前趨圖，試說(shuō)明這四個(gè)進(jìn)程間的同步關(guān)系，并用程序來(lái)實(shí)現(xiàn)。S3S1S2S4abcd120vara,b,c,d:semaphore:=0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);end;beginwait(b);S3;signal(d);end;beginwait(c);wait(d);S4;end;parend;end;121(2)設(shè)有8個(gè)程序prog1,prog2,prog3,…,prog8。它們?cè)诓l(fā)系統(tǒng)中執(zhí)行時(shí)有如圖所示的控制關(guān)系，試用信號(hào)量機(jī)制實(shí)現(xiàn)這些程序間的同步。prog1prog2prog3prog4prog5prog6prog7prog8122得到相應(yīng)的前驅(qū)圖并設(shè)置信號(hào)量如下:prog1prog2prog3prog4prog5prog6prog7prog8S13S14S15S23S24S25S36S48S57S78S68123本題是進(jìn)程同步問(wèn)題.beginS13,S14,S15,S23,S24,S25,S36,S57,S68,S48,S78

:semaphore:=0,0,0,0,0,0,0,0,0,0,0;parbeginbeginprog1;signal(S13);signal(S14);signal(S15);end;beginprog2;signal(S23);signal(S24);signal(S25);end;beginwait(S13);wait(S23);prog3;signal(S36);end;beginwait(S14);wait(S24);prog4;signal(S48);end;beginwait(S15);wait(S25);prog5;signal(S57);end;beginwait(S36);prog6;signal(S68);end;beginwait(S57);prog7;signal(S78);end;beginwait(S68);wait(S48);wait(S78);prog8;end;parend;end;124

(3)有三個(gè)進(jìn)程PI﹑PC﹑PO協(xié)作解決打印問(wèn)題:PI將文件從磁盤讀入主存緩沖區(qū)1,每執(zhí)行一次讀一個(gè)記錄;PC將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2,每執(zhí)行一次復(fù)制一個(gè)記錄;PO將緩沖區(qū)2的內(nèi)容打印出來(lái),每執(zhí)行一次打印一個(gè)記錄;

緩沖區(qū)的大小等于一條記錄的大小.用信號(hào)量機(jī)制解決進(jìn)程同步.125緩沖區(qū)1緩沖區(qū)2輸入打印PIPCPO126PI與PC共用緩沖區(qū)1,PC與PO共用緩沖區(qū)2,緩沖區(qū)是臨界資源.PI與PC不可能同時(shí)申請(qǐng)緩沖區(qū)1,因?yàn)榫彌_區(qū)1為空時(shí),只有PI可申請(qǐng)并使用;緩沖區(qū)1為滿時(shí),只有PC可申請(qǐng)并使用.只用同步機(jī)制便可使PI與PC互斥使用緩沖區(qū)1,設(shè)置信號(hào)量empty1,full1用于緩沖區(qū)1的訪問(wèn).

同理對(duì)PC與PO,設(shè)置信號(hào)量empty2,full2用于緩沖區(qū)2的訪問(wèn).127varempty1,full1,empty2,full2:semaphore:=1,0,1,0;beginparbeginPI:beginrepeatwait(empty1);puttobuffer1;signal(full1);untilfalse;end;128PC:beginrepeatwait(full1);getfrombuffer1;signal(empty1);wait(empty2);puttobuffer2;signal(full2);untilfalse;end;129PO:beginrepeatwait(full2)getfrombuffer2;signal(empty2);untilfalse;end;parend;end;130

(4)有一個(gè)倉(cāng)庫(kù)，可以存放A和B兩種產(chǎn)品。但要求：每次只能存入一種產(chǎn)品（A或者B）；

-N<(A產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量)<M.

其中,N和M是正整數(shù).試用P,V操作描述A和B的如庫(kù)過(guò)程.

解答:該題是一個(gè)典型的生產(chǎn)者與消費(fèi)者進(jìn)程同類的問(wèn)題；從-N<(A產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量)<M得:A產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量<MB產(chǎn)品數(shù)量-A產(chǎn)品數(shù)量<N131

若只放入A產(chǎn)品而不放入B產(chǎn)品,則A最多可放M-1次便被阻塞,即A進(jìn)程每操作一次就應(yīng)當(dāng)將計(jì)數(shù)器減1,當(dāng)計(jì)數(shù)器值為0時(shí),進(jìn)程A被阻塞;計(jì)數(shù)器Sa為資源信號(hào)量，初值為M-1.

若只放入B產(chǎn)品而不放入A產(chǎn)品,則B最多可放N-1次便被阻塞,即B進(jìn)程每操作一次就應(yīng)當(dāng)將計(jì)數(shù)器減1,當(dāng)計(jì)數(shù)器值為0時(shí),進(jìn)程B被阻塞;計(jì)數(shù)器Sb為資源信號(hào)量，初值為N-1.每當(dāng)放入一個(gè)A產(chǎn)品,可令B產(chǎn)品的計(jì)數(shù)器加1，表示B產(chǎn)品可以多一次放入產(chǎn)品的機(jī)會(huì)．倉(cāng)庫(kù)是臨界資源，設(shè)置信號(hào)量mutex控制兩進(jìn)程的互斥訪問(wèn)．132var

mutex,Sa,Sb:semaphore:=1,M-1,N-1;beginparbeginA產(chǎn)品:beginrepeatwait(Sa);

wait(mutex);

A入庫(kù)

signal(mutex);

signal(Sb);untilfalse;end;133B產(chǎn)品:beginrepeatwait(Sb);

wait(mutex);

B入庫(kù)

signal(mutex);

signal(Sa);untilfalse;end;parend;end;134

(5)進(jìn)程A1,A2,…,An1通過(guò)m個(gè)緩沖區(qū)向進(jìn)程B1,B2,…,Bn2不斷的發(fā)送消息．發(fā)送和接受工作遵循如下規(guī)則：每個(gè)發(fā)送進(jìn)程一次發(fā)送消息，寫入一個(gè)緩沖區(qū)，緩沖區(qū)大小與消息長(zhǎng)度一樣；對(duì)每個(gè)消息，B1,B2,…,Bn2都需各接受一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)；

m個(gè)緩沖區(qū)滿時(shí)，發(fā)送進(jìn)程等待；沒(méi)有可讀的消息時(shí)，接受進(jìn)程等待．試用信號(hào)量機(jī)制組織正確的發(fā)送和接受操作．135解答:某Ai往buffer中寫消息，必須向所有Bj發(fā)信號(hào)；每個(gè)Bj讀出消息后都應(yīng)向發(fā)送該消息的Ai回信號(hào)，Ai在收到所有Bj的回答時(shí),才可以認(rèn)為該消息被取走,即緩沖區(qū)空出一個(gè).所以一個(gè)Ai同所有Bj之間都有單獨(dú)的同步信號(hào).

設(shè)mutex為緩沖區(qū)訪問(wèn)的互斥信號(hào)量;empty[i]為發(fā)送進(jìn)程i可向緩沖區(qū)發(fā)送的消息數(shù)量;full[i]為接受進(jìn)程i可從緩沖區(qū)接收的消息數(shù)量.136var

mutex:semaphore:=1;Fori:=1ton2dobeginempty[i]:=m;/*信號(hào)量empty[i]置初值*/full[i]:=0;/*信號(hào)量full[i]置初值*/end;

beginparbegin137Ai發(fā)送:beginfori:=1ton1dowait(empty[i]);wait(mutex);

發(fā)送消息;signal(mutex);fori:=1ton1dosignal(full[i]);end;138Bj接收消息:beginforj:=1ton2dowait(full[j])wait(mutex);

接收消息;signal(mutex);forj:=1ton2dosignal(empty[j]);end;parend;End;139

(6)進(jìn)程之間存在哪幾種相互制約關(guān)系？各是什么原因引起？下列活動(dòng)分別屬于那種制約關(guān)系？若干同學(xué)去圖書館借書；兩對(duì)舉行籃球比賽；流水線生產(chǎn)的各道工序；商品生產(chǎn)和社會(huì)消費(fèi)。

解答:若干同學(xué)去圖書館借書；(互斥)

兩對(duì)舉行籃球比賽；(互斥)

流水線生產(chǎn)的各道工序；(同步)

商品生產(chǎn)和社會(huì)消費(fèi)。(同步)140(7)有一閱覽室,讀者進(jìn)入閱覽室必須先在一張登記表(TB)上登記,該表為每一座位設(shè)一個(gè)表目,讀者離開(kāi)時(shí)要消掉其登記信息,閱覽室共有100個(gè)座位,為了描述讀者的動(dòng)作,請(qǐng)寫用信號(hào)量機(jī)制寫出進(jìn)程間同步算法。約定:(1)flag為0表示座位空閑,1表示座位被占用。

(2)用語(yǔ)句i=getflag(0)可搜索到一個(gè)空座位i,

用語(yǔ)句i.flag=0或1可給標(biāo)志位賦值。

(3)用i=getname(readname)可搜索到某讀者所登記的座位號(hào)i;

用=0或=readname可給姓名字段賦值，0表示清除讀者姓名。

(4)記數(shù)信號(hào)量用count,互斥信號(hào)量用mutex。141

解答：進(jìn)入閱覽室，首先檢查是否有空位子，無(wú)則等待有則登記。設(shè)置信號(hào)量count控制各進(jìn)程對(duì)座位的爭(zhēng)奪，讀者離去時(shí)，便可以釋放該座位。登記時(shí)要對(duì)座位表中各量進(jìn)行修改，該過(guò)程相對(duì)于各進(jìn)程而言為互斥操作，設(shè)信號(hào)量mutex，控制讀者進(jìn)入和離去時(shí)對(duì)表的互斥修改。題目所提供的各種語(yǔ)句只是用在修改登記表時(shí)所進(jìn)行的具體操作，對(duì)本題的同步互斥問(wèn)題無(wú)任何影響，照抄即可。142varcount,mutex:semaphore:=100,1;

讀者進(jìn)程:begin

進(jìn)入閱覽室

wait(count); wait(mutex); i:=getflag(0); i.flag:=1;:=readname;signal(mutex);143

坐下看書

wait(mutex);i:=getname(readname);:=0;i.flag=0;signal(mutex);signal(count);

離開(kāi)

end;

144

2.6進(jìn)程通信進(jìn)程通信的類型消息傳遞通信的實(shí)現(xiàn)方式直接消息傳遞系統(tǒng)實(shí)例1452.6.1進(jìn)程通信的類型1共享存儲(chǔ)系統(tǒng)（Shared-MemorySystem)

基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式:

需要程序員直接設(shè)置公用數(shù)據(jù)結(jié)構(gòu)及讀寫操作﹑進(jìn)程同步.

低級(jí)通信,效率低.

基于共享存儲(chǔ)區(qū)的通信方式:

在存儲(chǔ)器中化出一塊共享存儲(chǔ)區(qū),進(jìn)程可以對(duì)共享存儲(chǔ)區(qū)中的數(shù)據(jù)進(jìn)行讀寫.程序員只需向系統(tǒng)申請(qǐng)共享區(qū),并指定共享區(qū)的關(guān)鍵字.系統(tǒng)返回申請(qǐng)成功則可直接使用.

高級(jí)通信,效率較高.1462.6.1進(jìn)程通信的類型2管道(pipe)通信系統(tǒng)

所謂管道，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)它們之間通信的一個(gè)共享文件，又名pipe文件。向管道（共享文件）提供輸入的發(fā)送進(jìn)程（即寫進(jìn)程）以字符流形式將大量的數(shù)據(jù)送入管道；而接收管道輸出的接受進(jìn)程（即讀進(jìn)程）則從管道中接收數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，又稱為管道進(jìn)程。1472.6.1進(jìn)程通信的類型3消息傳遞系統(tǒng)（MessagepassingSystem）進(jìn)程間的數(shù)據(jù)交換以消息(message)為單位.message是一個(gè)報(bào)文.OS提供一組發(fā)送和接受原語(yǔ)send,receive。實(shí)現(xiàn)方式的不同又可分為:

直接通信:直接發(fā)送和接收消息.

間接通信:通過(guò)郵箱。(3)管道通信（pipe)

協(xié)調(diào):互斥,同步,雙方存在.1482.6.1進(jìn)程通信的類型4客戶機(jī)-服務(wù)器系統(tǒng)（Client-Serversystem）這種通信機(jī)制，在網(wǎng)絡(luò)環(huán)境的各種應(yīng)用領(lǐng)域已經(jīng)成為當(dāng)前主流的通信機(jī)制，主要實(shí)現(xiàn)方法分為三類：（1）套接字（socket）（2）遠(yuǎn)程過(guò)程調(diào)用（3）遠(yuǎn)程方法調(diào)用1492.6.2消息傳遞通信的實(shí)現(xiàn)方