華科電信系操作系統(tǒng).ppt

1、第五章 并行性：互斥和同步,為了充分利用計(jì)算機(jī)各部分的能力，使之并行運(yùn)行以提高計(jì)算機(jī)系統(tǒng)的效率和性能，計(jì)算機(jī)界一直在堅(jiān)持不懈地、不遺余力地發(fā)展并行技術(shù)。近幾十年來，隨著多道程序設(shè)計(jì)、多處理器系統(tǒng)、分布式處理系統(tǒng)技術(shù)的發(fā)展，操作系統(tǒng)的并行技術(shù)不斷完善。,掌握 程序順序執(zhí)行和并行執(zhí)行的含義和特點(diǎn) 并行執(zhí)行的表示方法 臨界段的定義、目的、設(shè)計(jì)原則 同步和互斥的含義、實(shí)現(xiàn)方式 信號量機(jī)制：信號量定義、物理意義、信號量的使用（互斥、同步、生產(chǎn)者/消費(fèi)者， 閱讀者/寫入者等）。 進(jìn)程通信,多道程序設(shè)計(jì)基礎(chǔ)并行程序設(shè)計(jì),并行程序設(shè)計(jì) 進(jìn)程間的同步和互斥 同步和互斥的執(zhí)行工具 同步機(jī)構(gòu)在實(shí)際程序設(shè)計(jì)中的應(yīng)用

2、進(jìn)程通信 *管程 *Windows NT中的同步和互斥機(jī)制,1、程序的順序執(zhí)行,處理機(jī)逐條的一次只執(zhí)行一條指令 主存儲塊一次只訪問一個(gè)字或字節(jié) 外設(shè)一次只能傳送一個(gè)數(shù)據(jù)塊 傳統(tǒng)程序設(shè)計(jì)方法：順序程序執(zhí)行,程序的順序執(zhí)行,概念: 一個(gè)程序由若干個(gè)程序段組成，而這些程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式就稱為程序的順序執(zhí)行。 例如：,程序順序執(zhí)行的特點(diǎn),順序性 處理機(jī)嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每個(gè)操作必須在下一個(gè)操作開始之前結(jié)束。 封閉性 程序一旦開始執(zhí)行，其計(jì)算結(jié)果不受外界的影響，當(dāng)程序的初始條件給定之后，其后的狀態(tài)只能由程序本身確定，即只有本程序才能改變它。 可再現(xiàn)性 程序執(zhí)行的結(jié)

3、果與初始條件有關(guān)，而與執(zhí)行時(shí)間無關(guān)。即只要程序的初始條件相同，它的執(zhí)行結(jié)果是相同的，不論它在什么時(shí)間執(zhí)行，也不管計(jì)算機(jī)的運(yùn)行速度。,多道程序環(huán)境程序設(shè)計(jì)思想：并行程序設(shè)計(jì),例：在系統(tǒng)中有n個(gè)作業(yè)，每個(gè)作業(yè)都有三個(gè)處理步驟，輸入數(shù)據(jù)、處理、輸出，即Ii,Ci,Pi (i=1,2,3,.,n)。 這些作業(yè)系統(tǒng)中執(zhí)行時(shí)是對時(shí)間的偏序，有些操作必須在其它操作之前執(zhí)行，這是有序的，但有些操作是可以同時(shí)執(zhí)行的。,例如: I1、C1、P1的執(zhí)行必須嚴(yán)格按照I1，C1，P1的順序，而P1與I2，C1與I2,I3與P1是可以同時(shí)執(zhí)行的。,程序并行執(zhí)行 （定義） 若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，這些程序的執(zhí)行在時(shí)間

4、上是重迭的，一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始，即使這種重迭是很小的，也稱這幾個(gè)程序段是并行執(zhí)行的。,程序并行性的表示之一：有向圖,程序并行性的表示之二：并行語言,并行語言：并行PASCAL，CSP/K語言，MODULA語言，擴(kuò)充的Ada等. 并行語句記號: cobegin S1;S2;S3;.;SN coend; Si(i=1,2,3,.,n)表示n個(gè)語句（程序段），這n個(gè)語句用cobegin和coend括起來表示這n個(gè)語句是可以并發(fā)執(zhí)行的。co是concurrent的頭兩個(gè)字符。 有的書用parbegin和parend表示。 Si: 簡單語句，復(fù)合語句，并行語句。 編譯程

5、序?yàn)槊總€(gè)并行語句Si設(shè)置一個(gè)進(jìn)程。,程序并行性表示舉例,假設(shè)有一個(gè)程序由 S0Sn+1個(gè)語句， 其中 S1Sn語句是并發(fā)執(zhí)行的。 程序如下： S0; cobegin S1;S2;S3;.;SN coend; Sn+1;,程序并行性表示舉例,+,*,*,/,-,-,BEGIN COBEGIN t1=a-b t2=c-d t3=e/f COEND COBEGIN t4=t1*t2 t5=t3*2 COEND t6=t4+t5 END,算數(shù)表達(dá)式求值: (a-b)*(c-d)+(e/f)*2,a b c d e f,2,并行程序設(shè)計(jì)的特點(diǎn),并行、異步的在系統(tǒng)內(nèi)運(yùn)行 共享各類資源，彼此相互制約 只有在

6、嚴(yán)格遵循并行程序設(shè)計(jì)的原則下，程序運(yùn)行的結(jié)果才是確定的，否則，可能產(chǎn)生意料不到的情況,并發(fā)執(zhí)行實(shí)例：謄抄,一個(gè)循環(huán)程序順序執(zhí)行的謄抄 算法1： 輸入：f 輸出：g while (f 不為空） input ; output ; 由這個(gè)程序完成謄抄工作是不會(huì)出錯(cuò)的。,并發(fā)執(zhí)行實(shí)例：謄抄,兩個(gè)程序并發(fā)執(zhí)行完成謄抄 設(shè)有一臺標(biāo)準(zhǔn)輸入設(shè)備（鍵盤），和一臺標(biāo)準(zhǔn)輸出設(shè)備（顯示器或打印機(jī)），輸入程序負(fù)責(zé)從標(biāo)準(zhǔn)設(shè)備中讀取一個(gè)字符，送緩沖區(qū)中。輸出程序從緩沖區(qū)中取數(shù)據(jù)，送標(biāo)準(zhǔn)設(shè)備輸出。,并發(fā)執(zhí)行實(shí)例：謄抄,算法：2 cobegin f: Begin while (不為結(jié)束符）/* 輸入程序段 */ input;

7、/* 從標(biāo)準(zhǔn)輸入設(shè)備讀入一個(gè)數(shù)據(jù) */ write_buf; /* 將讀入的數(shù)據(jù)送到bufferf */ End g: Begin while(buffer不為空） /* 輸出程序段 */ read_buf; /* 從bufferf中取數(shù)據(jù) */ output; /* 送打印機(jī)輸出 */ End coend ,并發(fā)執(zhí)行實(shí)例：謄抄,這兩個(gè)程序段并發(fā)執(zhí)行時(shí)可能出現(xiàn)如下情況： 1、輸出程序運(yùn)行的速度比輸入程序快時(shí)，有些輸出會(huì)重復(fù)； 如輸入送入了一個(gè)字符“A”，輸出取出打印“A”，當(dāng)輸入還未送入新的數(shù)據(jù)，輸出程序已執(zhí)行，又取出“A”打印，這樣“A”的輸出就重復(fù)了，出錯(cuò)。 2、輸入程序執(zhí)行的速度比輸出程

8、序快時(shí)，有些數(shù)據(jù)會(huì)丟失； 如輸入程序送入一個(gè)字符“B”，緊接著（當(dāng)輸出程序還未取走字符“B”）又送入字符“N”，這時(shí)輸出程序取走的是“N”，“B”就丟失了。,并發(fā)執(zhí)行實(shí)例：謄抄,三個(gè)并發(fā)執(zhí)行程序的謄抄 get程序負(fù)責(zé)從輸入序列f中讀取字符并送到緩沖區(qū)s中； copy程序把緩沖區(qū)s中的數(shù)據(jù)復(fù)制到緩沖區(qū)t中去; put程序從緩沖區(qū)t中取出數(shù)據(jù)打印。,若程序錯(cuò)寫成： while(謄抄未完成） cobegin copy; put; get; coend ,初始狀態(tài)： f=(R1,R2,.,Rn) s=() t=() g=() 首先順序執(zhí)行了一次 get(s,f), copy(t,s) put(g,t)

9、 f=(R1,R2,.,Rn) s=(R1),t=(R1),g=(R1),然后，copy,put,get三個(gè)程序段并發(fā)執(zhí)行，就有六種組合： 1、copy;put;get 導(dǎo)致結(jié)果：g=(R1,R1) 2、copy;get;put 導(dǎo)致結(jié)果：g=(R1,R1) 3、put;copy;get 導(dǎo)致結(jié)果：g=(R1,R1) 4、put;get;copy 導(dǎo)致結(jié)果：g=(R1,R1) 5、get;copy;put 導(dǎo)致結(jié)果：g=(R1,R2) 6、get;put;copy 導(dǎo)致結(jié)果：g=(R1,R1) 這就是與時(shí)間有關(guān)的錯(cuò)誤。,程序并發(fā)執(zhí)行的特點(diǎn),失去了程序的封閉性 如果程序執(zhí)行的結(jié)果是一個(gè)與時(shí)間無關(guān)

10、的函數(shù)，即具有封閉性。 若一個(gè)程序的執(zhí)行可改變另一個(gè)程序的變量，象二個(gè)并發(fā)程序完成謄抄的例子，程序執(zhí)行的結(jié)果不僅依賴于程序的初始條件，還依賴于程序執(zhí)行時(shí)的相對速度，在這種情況下就失去了程序的封閉性。,程序并發(fā)執(zhí)行的特點(diǎn),程序并發(fā)執(zhí)行的相互制約 在多道程序設(shè)計(jì)的環(huán)境下，程序是并發(fā)執(zhí)行的。即系統(tǒng)中有多道程序在“同時(shí)”執(zhí)行，這些程序之間要共享系統(tǒng)的資源，程序之間有合作（通信）的關(guān)系。合作與競爭產(chǎn)生一系列的矛盾，這些矛盾實(shí)際上是一種相互制約，有直接的，也有間接。,3、進(jìn)程間的同步與互斥,同步：指多個(gè)進(jìn)程因協(xié)同合作而發(fā)生的一種直接制約關(guān)系。進(jìn)程相互配合，共同完成一個(gè)任務(wù)。 互斥：指多個(gè)進(jìn)程因競爭共享資源

11、而發(fā)生的一種間接制約關(guān)系。有許多資源在使用上具有排他性，或者說只能互斥作用，進(jìn)程間需要互相競爭，才有可能使用這些資源，如打印機(jī)等。 互斥也是一種同步。一種特殊的同步。 互斥的概念來自于諸進(jìn)程對獨(dú)占使用資源（設(shè)備）的競爭，是進(jìn)程之間的間接制約關(guān)系。 同步來源于多個(gè)進(jìn)程的合作，是進(jìn)程之間的直接制約關(guān)系。,臨界段的提出,多道程序環(huán)境進(jìn)程之間存在資源共享； 硬件：外設(shè) 軟件：共享代碼段、共享數(shù)據(jù)結(jié)構(gòu)等； 進(jìn)程訪問共享資源時(shí)有約束： 共享資源不支持多進(jìn)程同時(shí)進(jìn)行讀寫操作； 共享資源不支持多進(jìn)程同時(shí)訪問。 進(jìn)程間資源訪問沖突 共享變量的修改沖突 操作順序沖突,臨界資源：每次只允許一個(gè)進(jìn)程訪問的共享資源。

12、臨界段：進(jìn)程中訪問臨界資源（共享變量）的代碼段。 訪問同一臨界資源的各臨界段分散在各有關(guān)進(jìn)程的程序中。,臨界段設(shè)計(jì)原則,互斥性：每次允許一個(gè)進(jìn)程停留在臨界段。 有限逗留：進(jìn)程只能 在臨界段內(nèi)逗留有限時(shí)間。 有限等待：進(jìn)程不能無限期等待在臨界段之外。 前進(jìn)性：臨界段外進(jìn)程不可以阻止其他進(jìn)程進(jìn)入臨界段。 有空讓進(jìn)：若有多個(gè)進(jìn)程同時(shí)要求進(jìn)入臨界段，應(yīng)在有限的時(shí)間內(nèi)讓其中一個(gè)進(jìn)入臨界段，不應(yīng)相互阻塞。 通用性：不能預(yù)期和假定進(jìn)程進(jìn)展的相對速度以及可用的處理器的數(shù)目。（如進(jìn)程的速度、cpu個(gè)數(shù)、有無硬件指令支持等）。,互斥的實(shí)現(xiàn)方法,臨界段就是為了解決互斥資源的訪問問題 軟件實(shí)現(xiàn) 用軟件解決方法來解決進(jìn)

13、程間的同步和互斥有著很大的局限性，并不是很理想。 硬件方法 中斷屏蔽方法 硬件指令方法,軟件方法,解法1：雙標(biāo)志、先檢查,后表態(tài)。 標(biāo)志表示是否已在臨界段。 問題：兩個(gè)進(jìn)程可能同時(shí)進(jìn)入臨界段，違背互斥性原則。 P1 P2 p1 p2 : while flagj do skip : flagi := true,軟件方法,解法2：用一個(gè)指針表示哪個(gè)應(yīng)進(jìn)入臨界段， 問題：強(qiáng)制兩個(gè)進(jìn)程輪流進(jìn)入臨界段，違背前進(jìn)性原則。 P1讓出后，P2使用前， p1不可能在進(jìn)入 解法3：雙標(biāo)志，先表態(tài)，后查看。 問題：可能兩個(gè)進(jìn)程都進(jìn)入不了臨界段，違背有空讓進(jìn)。 P1 p2 p1 p2 : flagi := true

14、: while flagj do skip,中斷屏蔽法,禁止一切中斷發(fā)生。 單CPU中，引起進(jìn)程切換的唯一原因是中斷，故單CPU下可行。 缺點(diǎn)： 代價(jià)高，影響并發(fā)性 不安全，將禁止一切中斷權(quán)利給了普通用戶。 局限性：不適合多CPU，一個(gè)進(jìn)程只能禁止本CPU的中斷。,硬件指令方法,思路：一條指令完成讀寫兩個(gè)操作 手段：執(zhí)行硬件指令的CPU封鎖內(nèi)存總線，以禁止其他CPU在該指令完成前訪問內(nèi)存。 兩種指令： TS指令和Swap指令,硬件指令方法（續(xù)）,TS：test-and-set指令，讀出指定標(biāo)志后把該標(biāo)志設(shè)置為True。 該指令由PASCAL語言描述如下： Function Test-and-S

15、et(var flag:boolean):boolean begin Test-and-Set:=flag; flag : =true end,TS指令的使用： repeat while TS(lock) do skip; 臨界段代碼； lock： false； 其他代碼； forever,硬件指令方法（續(xù)）,Swap指令：該指令的功能是交換兩個(gè)字的內(nèi)容。 PASCAL語言描述如下： Proceduce Swap(var a,b:boolean) var temp : boolean; begin temp : =a; a:=b; b:=temp; end,swap使用： repeat key

16、 = true; repeat swap(lock,key); until keyfalse； 臨界段代碼； lock : false; 其他代碼； forever,存在的缺點(diǎn),忙等待：上述硬件指令雖然可以有效的保證進(jìn)程間互斥，但是進(jìn)程在臨界段中執(zhí)行時(shí)，其他想進(jìn)入臨界段的進(jìn)程必須不斷地檢測布爾變量lock的值，這就造成了處理機(jī)時(shí)的浪費(fèi)，通常稱這種情況為“忙等待”。 饑餓：由于采用隨機(jī)從等待隊(duì)列中選取進(jìn)程，會(huì)出現(xiàn)有的進(jìn)程一直處于等待。 需CPU支持,硬件指令方法的優(yōu)點(diǎn),不但適用于單處理器情況，而且適用于共享主存的SMP多處理器情況（即對稱多處理器）； 方法簡單，行而有效； 可以被使用于多重臨界段

17、情況，每個(gè)臨界段可以定義自己的共享變量。,4、信號量,用軟件和硬件的方法來解決互斥的問題，都存在一定的缺點(diǎn)，荷蘭著名的計(jì)算機(jī)科學(xué)家Dijkstra，于1965年提出了一個(gè)同步機(jī)構(gòu)，稱之為信號量。其基本原則是在多個(gè)相互合作的進(jìn)程之間使用相同的信號來同步，一個(gè)進(jìn)程強(qiáng)制的被停止在一個(gè)特定的地方直到收到一個(gè)專門的信號，這個(gè)信號也就是信號量。,信號量定義,除初始化外，僅能由兩個(gè)同步原語對其進(jìn)行操作的整型變量。 兩個(gè)同步原語分別成為wait和signal（也稱為P和V）。 類型： 二元信號量：信號量的值僅允許取0或1，主要用于互斥變量。 一般信號量：信號量取值允許為非負(fù)整數(shù)，主要用于進(jìn)程間的一般同步。 在

18、實(shí)際操作系統(tǒng)中，一般情況下是由機(jī)器硬件提供Wait、signal操作的指令，當(dāng)然是原子操作，若機(jī)器不提供wait、signal操作的指令，則操作系統(tǒng)提供Wait、Signal操作原語。,同步原語,作為OS核心代碼的一部分，其執(zhí)行不受進(jìn)程調(diào)度和執(zhí)行的打斷。 進(jìn)程的等待方式可以分為 阻塞等待方式和忙等待方式 在不同的等待方式下，Wait和signal操作實(shí)現(xiàn)的方式略有不同。,Wait操作,阻塞等待方式 S:=S-1 若S=0 則進(jìn)程繼續(xù)執(zhí)行其他代碼 若S0 則 S:=S-1,signal操作,阻塞等待方式 S:=S+1 若S0 則進(jìn)程繼續(xù)執(zhí)行其他代碼 若S=0 則從該信號量等待隊(duì)列中移出第一個(gè)進(jìn)程

19、，使其變?yōu)榫途w狀態(tài)，然后返回原進(jìn)程繼續(xù)執(zhí)行其他代碼 忙等待方式 S:=S1,硬件指令實(shí)現(xiàn)互斥的同步原語,Wait(S): While TS(lock) do skip /上鎖 While S=0 do skip; /同步原語代碼 S: =S-1; lock : =false; /開鎖 Signals(S): While TS(lock) do skip /上鎖 S: =S+1; /同步原語代碼 lock : =false; /開鎖,信號量的數(shù)據(jù)結(jié)構(gòu),整型：忙等待方式 記錄型結(jié)構(gòu)：阻塞等待方式 type SemaphoreRecord value:integer L: point to PCB

20、end,兩種比較方式的比較,阻塞等待： 信號量采用記錄型數(shù)據(jù)結(jié)構(gòu) 實(shí)現(xiàn)復(fù)雜，須操作就緒隊(duì)列和阻塞隊(duì)列 進(jìn)程間開銷大 忙等待： 信號量采用整型 實(shí)現(xiàn)簡單 可減少進(jìn)程間開關(guān)開銷 CPU資源浪費(fèi),信號量的物理意義,信號量S的初值表示可用資源數(shù) 當(dāng)S0時(shí)，S的值表示還?？捎觅Y源數(shù) 當(dāng)S0，意味著有資源可以申請，操作后，S=S-1意味著資源減少 Signal操作：釋放資源，執(zhí)行Signal操作之后，S=S+1,意味著資源數(shù)增加,信號量的物理意義,信號量的變化范圍： 設(shè)可用資源數(shù)為m，進(jìn)程數(shù)為n 忙等待：0=S =m 阻塞等待: -(n-m)=S =m,P4,P1,P2,P3,就緒隊(duì)列,運(yùn)行,等待隊(duì)列,例

21、：4個(gè)進(jìn)程共享2臺打印機(jī),S：2 1P1:wait(s) 0 p2:wait(s) -1 p3:wait(s) -2 p4:wait(s) -1p1:signal(s) 0 p2:signal(s) p3:signal(s) p4:signal(s),利用信號量實(shí)現(xiàn)互斥,描述：多個(gè)進(jìn)程共享臨界資源，并且對資源的訪問是互斥的，資源可用單位數(shù)為1。,Begin parbegin P1； Pi； Pn； parend end,Pi： Begin Repeat 臨界段; 剩余段； forever end,var mutex:Semaphore；,mutex:=1；,wait(mutex);,signa

22、l(mutex);,利用信號量實(shí)現(xiàn)互斥,為臨界資源設(shè)置一個(gè)互斥信號量mutex，其初值為1；在每個(gè)進(jìn)程中將臨界區(qū)代碼置于wait(mutex)和signal(mutex)原語之間. 必須成對使用wait和signal原語：遺漏wait原語則不能保證互斥訪問，遺漏signal原語則不能在使用臨界資源之后將其釋放（給其他等待的進(jìn)程）；wait、signal原語不能次序錯(cuò)誤、重復(fù)或遺漏.,利用信號量來實(shí)現(xiàn)同步,用信號量及wait、signal操作來描述左圖 1、說明進(jìn)程的同步關(guān)系 進(jìn)程P1、P2可并行執(zhí)行，P3的執(zhí)行必須等待P1、P2都完成后才能開始執(zhí)行。 2、設(shè)置信號燈，說明含義、初值。 s13

23、= 0 表示進(jìn)程P1尚未執(zhí)行完成； s23 = 0 表示進(jìn)程P2尚未執(zhí)行完成；,利用信號量來實(shí)現(xiàn)同步,程序描述 main() int s13=0;s23=0; parbegin p1; p2; p3; parend; ,P1() signal(s13); P2() . signal(s23); ,P3() wait(s13); wait(s23); . ,共享緩沖區(qū)的合作進(jìn)程的同步,設(shè)有一個(gè)緩沖區(qū)buffer，大小為一個(gè)字節(jié)， CP進(jìn)程不斷產(chǎn)生字符，送buffer， IOP進(jìn)程從buffer中取出字符打印。 如不加控制，會(huì)有多種打印結(jié)果，這取決于這兩個(gè)進(jìn)程運(yùn)行的相對速度。在這眾多的打印結(jié)果中，

24、只有CP、IOP進(jìn)程的運(yùn)行剛好匹配的一種是對的，其它均為錯(cuò)誤，并且不能重現(xiàn)。,要保證打印結(jié)果的正確，CP、IOP必須遵循以下同步規(guī)則: 當(dāng)CP把結(jié)果送入buffer后，IOP才能從buffer中取，否則IOP必須等待； 當(dāng)IOP從buffer中取走數(shù)據(jù)后，CP才能將新產(chǎn)生數(shù)據(jù)送buffer，否則也必須等待。,解決這個(gè)問題的步驟： 分析問題，弄清楚同步關(guān)系，如上分析； 設(shè)置信號量，說明含義、初值； 寫出程序描述。,Main() int sb=1;sa=0; cobegin CP(); IOP(); coend ,Sb 表示buffer是否有空位存放數(shù)據(jù)，初值為1表示可以存放一個(gè)數(shù)據(jù)。 Sa表示是

25、否有數(shù)據(jù)打印，初值為0，表示沒有數(shù)據(jù)供打印。,CP() while(計(jì)算未完） 獲得一個(gè)計(jì)算結(jié)果； wait(sb); 將數(shù)據(jù)放入buffer； signal(sa); ,IOP() while(打印未完） wait(sa); 從buffer中取數(shù)據(jù)； signal(sb); 打??； ,生產(chǎn)者、消費(fèi)者問題,定義：指若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)時(shí)，對緩沖區(qū)資源的使用問題。 生產(chǎn)者：向共享緩沖區(qū)寫入數(shù)據(jù)的進(jìn)程。 消費(fèi)者：從共享緩沖區(qū)讀取數(shù)據(jù)的進(jìn)程。,生產(chǎn)者、消費(fèi)者問題,描述： 若共享區(qū)為n個(gè)，可將這n個(gè)緩沖區(qū)視為共享資源。 任何時(shí)刻，一個(gè)緩存區(qū)只允許一個(gè)進(jìn)程對其操作。 緩沖區(qū)空時(shí)，生產(chǎn)者可

26、寫入數(shù)據(jù)（不許寫重），否則等待。消費(fèi)者讀取數(shù)據(jù)后的緩存成為生產(chǎn)者的可用資源。 緩沖區(qū)中有數(shù)據(jù)時(shí)，消費(fèi)者讀取數(shù)據(jù)（不許取重），否則等待。生產(chǎn)者寫入數(shù)據(jù)的緩存成為消費(fèi)者的可用資源。 生產(chǎn)者和消費(fèi)者都以異步方式運(yùn)行，但必須保持同步，即各自只能操作各自的可用資源。,生產(chǎn)者、消費(fèi)者問題,緩沖池：N個(gè)緩沖區(qū) P：一組生產(chǎn)者共用的指向空緩沖區(qū)頭的指針； C：一組消費(fèi)者共用的指向滿緩沖區(qū)頭的指針。 互斥操作： 分配空緩沖區(qū)和移動(dòng)指針P; 釋放滿緩沖區(qū)和移動(dòng)指針C;,滿 C P 空,生產(chǎn)者、消費(fèi)者問題,信號量設(shè)置 3個(gè)信號量 E：表示空的緩沖區(qū)數(shù)，初值為n； F：表示滿的緩沖區(qū)數(shù)，初值為0； Mutex：分配緩

27、沖區(qū)的互斥信號量，初值為1。,生產(chǎn)者、消費(fèi)者問題,var E,F: Semaphore； muntex: binary Semaphore; Procedure producer begin repeat wait(E); wait(mutex); “分配空緩沖區(qū)并調(diào)整指針P的臨界段”； Signal(mutex); “向緩沖區(qū)中裝入數(shù)據(jù)”； Signal(F); forever end,生產(chǎn)者、消費(fèi)者問題,Procedure Consumers begin repeat wait(F); wait(mutex); “分配滿緩沖區(qū)并調(diào)整指針C的臨界段”； signal(mutex); “從緩沖

28、區(qū)中取出數(shù)據(jù)”； signal(E); forever end,生產(chǎn)者、消費(fèi)者問題,Main（） begin F:=0; E:=n; mutex:= 1; cobegin Producer 1; Producer 2; Producer n; Consumer1; Consumer2; Consumer m; coend end,生產(chǎn)者、消費(fèi)者問題,特點(diǎn) Wait次序不能顛倒，否則會(huì)出現(xiàn)死鎖 當(dāng)E0，F(xiàn)n時(shí)， P：wait（mutex）-p:wait(E)- S:wait(mutex)-S:wait(F) 當(dāng)En，F(xiàn)0時(shí)， S：wait（mutex）-S:wait(F)- P:wait(mut

29、ex)-P:wait(E) 生產(chǎn)者和消費(fèi)者的緩沖指針P、C不能同時(shí)移動(dòng)。即緩沖分配不能同時(shí)進(jìn)行。 可改進(jìn)：將兩個(gè)互斥信號量來分別控制對指針P、C的操作。,閱讀者、寫入者問題,定義：指多個(gè)進(jìn)程對一個(gè)共享資源進(jìn)行讀寫操作的問題。 閱讀者：對共享資源進(jìn)行讀操作的進(jìn)程。 寫入者：對共享資源進(jìn)行寫操作的進(jìn)程 原則： 任何時(shí)候?qū)懭胝咦疃嘀辉试S1個(gè)，閱讀者可有多個(gè)； 對共享資源的讀寫操作限制關(guān)系包括: “讀”“寫” ：互斥 “寫”“寫”：互斥 “讀”“讀”：允許 當(dāng)無寫入者正在訪問共享數(shù)據(jù)集時(shí)，閱讀者可以進(jìn)行訪問，否則必須等待。 當(dāng)無閱讀者正在訪問共享數(shù)據(jù)集時(shí)，寫入者可以進(jìn)行訪問，否則必須等待。,閱讀者、寫

30、入者問題,信號量的考慮： 兩個(gè)共享資源： Readcount:記錄正在讀的閱讀者人數(shù)。 共享數(shù)據(jù)集 Readcount的訪問：對閱讀者是互斥的，用mutex作訪問的互斥信號量。 共享數(shù)據(jù)集的訪問：對寫操作互斥，讀寫操作互斥，用wrt作訪問的互斥信號量。,閱讀者、寫入者問題,var mutex,wrt:Semaphore; readcount:integer; mutex:=wrt:=1;readcount:=0; parbegin Readeri: beginwait(mutex); readcount:=readcount+1; if readcount=1 then wait(wrt);s

31、ignal(mutex); 讀數(shù)據(jù)集；wait(mutex);readcount:=readcount-1; if readcount=0 then signal(wrt); signal(mutex); end,Writeri: begin wait(wrt);寫數(shù)據(jù)集； signal(wrt); end; parend,閱讀者、寫入者問題,特點(diǎn)： 某種程度上，閱讀者優(yōu)先，寫入者總在所有閱讀者完成后才進(jìn)行。 各閱讀者可并發(fā)運(yùn)行。 練習(xí)： 讀者優(yōu)先= 寫入者優(yōu)先 兩種情形： 1、寫入者封鎖后來的閱讀者； 2、第一個(gè)寫入者封鎖后來的閱讀者，并且后來的寫入者可以優(yōu)先于閱讀者；,寫入優(yōu)先,Var v

32、,w,r,mutwx,k:semaphore;RC,WC:integer; begin w:=r:=v:=k:=1;RC:=WC:=0; parbegin READER: begin wait(r);wait(v); if RC=0 then wait(w); RC:=RC+1; signal(v);signal(r); 閱讀； wait(v); RC:=RC-1; if RC=0 then signal(w); signal(v); end,WRITER: begin wait(k);if WC=0 then wait(r); WC:=WC+1;signal(k); wait(w); 寫入；

33、signal(w);wait(k);WC:=WC-1; if WC=0 then signal(r);signal(k); end parend end,哲學(xué)家用餐問題,一個(gè)典型的進(jìn)程同步問題。 問題的描述：有五個(gè)哲學(xué)家，他們的生活是交替地進(jìn)行思考和就餐。哲學(xué)家們共一張圓桌，周圍放有五張椅子，每人坐一張。在圓桌上有五個(gè)碗和五只筷子，當(dāng)一個(gè)哲學(xué)家思考時(shí)，他不與同事交談，饑餓時(shí)便試圖取左、右最靠近他的筷子，但他可能一支都拿不到。只有在他拿到兩支筷子時(shí)方能就餐。餐畢，放下筷子繼續(xù)思考。,一個(gè)簡單的解法是，用一個(gè)信號量表示一支筷子 這五個(gè)信號量構(gòu)成信號量數(shù)組，其描述為： var chopstick:

34、array0.4 of semaphore; 所有信號量被初始化為1 ，第i個(gè)哲學(xué)家的活動(dòng)可描述為： repeat wait (chopsticki); wait(chopstick (i+1) mod 5 ); . eat; . signal (chopsticki); signal (chopstick(i+1) mod 5); . think; . forever;,上述解法可保證不會(huì)有兩個(gè)相鄰的哲學(xué)家同時(shí)就餐; 但可能引起死鎖。假如五個(gè)哲學(xué)家同時(shí)饑餓而拿起各自左邊的筷子，使五個(gè)信號量chopstick均為0；當(dāng)他們再試圖去拿右邊的筷子時(shí)，他們都無限期地等待。 死鎖問題可采取以下解決方法

35、： 至多只允許四個(gè)哲學(xué)家同時(shí)就餐，以保證至少有一個(gè)哲學(xué)家可以就餐，最終總會(huì)釋放出他所用過的筷子，從而可使更多的哲學(xué)家就餐； 僅當(dāng)哲學(xué)家的左、右兩支筷子均可用時(shí)，才允許他拿起筷子就餐； 規(guī)定奇數(shù)號哲學(xué)家先拿起其左邊筷子，然后再去拿右邊筷子；而偶數(shù)號哲學(xué)家則相反。 按此規(guī)定，1、2號哲學(xué)家競爭1號筷子，3、4號哲學(xué)家競爭3號筷子，即五個(gè)哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶號筷子，最后總會(huì)有某一個(gè)哲學(xué)家能獲得兩支筷子而就餐。,睡著的理發(fā)師問題,問題描述：在理發(fā)館中，有一個(gè)理發(fā)師，一張理發(fā)椅和n個(gè)為等待顧客所設(shè)的椅子。如果沒有顧客來，理發(fā)師就會(huì)坐在理發(fā)椅上睡覺，當(dāng)一個(gè)顧客來到時(shí)，他必須喚醒睡著

36、了的理發(fā)師。如果在理發(fā)師理發(fā)時(shí)，又有別的顧客到達(dá)，他們要么坐下(如果有空的椅子)，要么離開(如果所有的椅子都被坐滿)。用信號量和wait、signal操作寫出理發(fā)師和顧客行為的程序描述。,5、進(jìn)程間的通信,進(jìn)程通信：指進(jìn)程之間的信息交換。 作業(yè)若干個(gè)可并行執(zhí)行的進(jìn)程協(xié)同完成一個(gè)工作（同步）進(jìn)程通信（在進(jìn)程之間交換一定數(shù)量的信息）。 進(jìn)程通信方式： 低級通信原語：交換信息量較少。如互斥，同步機(jī)構(gòu)。 高級通信原語：交換信息量較多。如直接通信，間接通信。 高級通信原語： 直接通信：一個(gè)進(jìn)程直接發(fā)送消息給接受者進(jìn)程；Send( P, Msg ); Receive( P, Msg ); 間接通信：進(jìn)程通

37、過一個(gè)“信箱”來傳遞消息。Send( A, Msg ); Receive( A, Msg );,直接通信,要求發(fā)送進(jìn)程和接收進(jìn)程都以顯示的方式提供對方的標(biāo)識符。通常系統(tǒng)提供兩條通信原語。 原語send（P，消息）：把一個(gè)消息發(fā)送給進(jìn)程P 原語receive（Q，消息）：從進(jìn)程Q接收一個(gè)消息,消息隊(duì)列,通常一個(gè)進(jìn)程可以與多個(gè)進(jìn)程通信，即可以向多個(gè)進(jìn)程發(fā)送消息，也可以接收來自多個(gè)進(jìn)程的消息。為了便于進(jìn)程接收和處理這些消息，一般采用消息隊(duì)列通信機(jī)制，將消息組織成消息隊(duì)列，用鏈指針鏈接起來，頭指針放在進(jìn)程的PCB中。,有關(guān)數(shù)據(jù)結(jié)構(gòu),消息隊(duì)列 type Msg record MsgSend； MsgSi

38、ze； MsgText； MsgNext； end,PCB中部分?jǐn)?shù)據(jù) type PCB record Msgmq； 首指針 MsgMutex；互斥信號量 MsgSm； 資源信號量 end,發(fā)送和接收過程,發(fā)送進(jìn)程在自己地址空間設(shè)置一發(fā)送區(qū)，將發(fā)送的消息正文，發(fā)送者進(jìn)程標(biāo)示符，消息長度填入其中，然后調(diào)用發(fā)送原語。 發(fā)送原語根據(jù)發(fā)送區(qū)的消息長度，申請一緩沖區(qū)，將發(fā)送區(qū)的消息復(fù)制到緩沖區(qū)中。并獲得接收進(jìn)程的內(nèi)部標(biāo)識符，然后將緩沖區(qū)掛在接收進(jìn)程的消息隊(duì)列上。 接收進(jìn)程調(diào)用接收原語，從自己的消息隊(duì)列中摘下消息隊(duì)列中的消息，并將其中的數(shù)據(jù)復(fù)制到指定的消息接收區(qū)。,發(fā)送區(qū):a,進(jìn)程A,消息緩沖區(qū),PCB:

39、B,Msgmq,接收區(qū):b,進(jìn)程B,Receive(A,b),Sender:A,Size:5,Text:Hello,同步機(jī)制,信號量： 互斥信號量（mutex）：對消息對列指針的操作 等待信號量（swait）：消息資源數(shù),發(fā)送時(shí)： wait(mutex); 將消息鏈入隊(duì)列； signal（mutex）； signal（swait）；,接收時(shí)： wait（swait）； wait(mutex); 從隊(duì)列中摘取消息； signal（mutex）；,間接通信,進(jìn)程間發(fā)送或接收消息通過一個(gè)信箱來進(jìn)行，消息可以被理解成信件 原語send（A，信件）：把一封信件（消息）傳送到信箱A 原語receive（A

40、，信件）：從信箱A接收一封信件（消息）,間接通信的實(shí)現(xiàn),信箱是存放信件的存儲區(qū)域，每個(gè)信箱可以分成信箱特征和信箱體兩部分。信箱特征指出信箱容量、信件格式、指針等；信箱體用來存放信件 發(fā)送信件：如果指定的信箱未滿，則將信件送入信箱中由指針?biāo)甘镜奈恢?，并釋放等待該信箱中信件的等待者；否則發(fā)送信件者被置成等待信箱狀態(tài) 接收信件：如果指定信箱中有信，則取出一封信件，并釋放等待信箱的等待者，否則接收信件者被置成等待信箱中信件的狀態(tài),6、管道,管道（pipeline）源自“貝爾實(shí)驗(yàn)室”開發(fā)的Unix,是Unix最具特色的進(jìn)程通信方式； 也稱共享文件方式，基于文件系統(tǒng)，利用一個(gè)打開的共享文件實(shí)現(xiàn)進(jìn)程間的相

41、互通信，文件作為緩沖傳輸介質(zhì)。 管道是進(jìn)程間以字節(jié)流方式傳送的通信通道，通過通常的 IO 接口來存取。創(chuàng)建管道后，通過使用操作系統(tǒng)的任何讀或?qū)?IO 系統(tǒng)調(diào)用來讀或者寫它。 管道通常是單向的；常用于命令行所指定的輸入輸出重定向和管道命令。在使用管道前要建立相應(yīng)的管道，然后才可使用。 Windows 管道與 Linux 管道的區(qū)別： Windows 使用單一句柄（類似于 Linux 文件描述符）支持雙向 IO。 Linux 管道返回兩個(gè)文件描述符來實(shí)現(xiàn)雙向 IO。,管道具有如下三個(gè)突出的特點(diǎn) 發(fā)送進(jìn)程能以比較簡單的方式，源源不斷地把產(chǎn)生的消息以自然流的方式寫入管道，而不需要考慮對每次傳送的信息長

42、度的限制。 接收進(jìn)程能在適當(dāng)?shù)臅r(shí)機(jī)從管道按需提取信息，同樣也不必以固定的消息長度為單位進(jìn)行。 發(fā)送和接收進(jìn)程都能以一定的方式了解對方進(jìn)程是否存在，并且可以通過管道的現(xiàn)存消息情況（管道空、管道有信息、管道滿）等相互協(xié)調(diào)動(dòng)作。,7、套接字,套接字（socket）起源于Unix BSD版本，目前已經(jīng)被Unix和Windows操作系統(tǒng)廣泛采用，并支持TCP/IP協(xié)議，即支持本機(jī)的進(jìn)程間通信，也支持網(wǎng)絡(luò)級的進(jìn)程間通信 雙向的，數(shù)據(jù)格式為字節(jié)流（一對一）或報(bào)文（多對一，一對多）；主要用于網(wǎng)絡(luò)通信； 支持client-server模式和peer-to-peer模式，本機(jī)或網(wǎng)絡(luò)中的兩個(gè)或多個(gè)進(jìn)程進(jìn)行交互。提供

43、TCP/IP協(xié)議支持 UNIX套接字(基于TCP/IP)：send, sendto, recv, recvfrom; 在Windows NT中的規(guī)范稱為Winsock(與協(xié)議獨(dú)立，或支持多種協(xié)議)：WSASend, WSASendto, WSARecv, WSARecvfrom;,8、Windows NT中的同步和互斥機(jī)制,NT是多機(jī)操作系統(tǒng),支持對稱多處理模式, 同步和互斥由多種機(jī)制實(shí)現(xiàn). 內(nèi)核中的同步和互斥機(jī)制：實(shí)現(xiàn)多處理器之間的同步. 提高臨界段代碼執(zhí)行的中斷優(yōu)先級：實(shí)現(xiàn)同一處理機(jī)中的互斥； 轉(zhuǎn)鎖機(jī)制（spin-lock）：用T-S指令實(shí)現(xiàn)多處理機(jī)間的互斥。,Windows NT中的同步

44、和互斥機(jī)制,“等待和信號設(shè)置”機(jī)制：實(shí)現(xiàn)線程之間的同步(即一個(gè)線程主動(dòng)停止執(zhí)行并等待其他現(xiàn)成執(zhí)行一些操作)。 進(jìn)程通信機(jī)制: 客戶進(jìn)程與服務(wù)器進(jìn)程間的通信采用交換信息的方式. 小消息通信方法: 少于256bytes(將消息傳給與服務(wù)器相連的端口對象)； 大消息通信方法: 多于256bytes (將消息指針傳給與服務(wù)器相連的端口對象,并把消息存放在共享的主存區(qū)域中)； 多通信端口機(jī)制: 當(dāng)子系統(tǒng)有多個(gè)通信端口時(shí)用。,Windows NT同步對象,Mutex對象：互斥對象，相當(dāng)于互斥信號量，在一個(gè)時(shí)刻只能被一個(gè)線程使用。有關(guān)的API： CreateMutex創(chuàng)建一個(gè)互斥對象，返回對象句柄； Ope

45、nMutex返回一個(gè)已存在的互斥對象的句柄，用于后續(xù)訪問； ReleaseMutex釋放對互斥對象的占用，使之成為可用；,（1） NT支持的三種同步對象,對象名稱是由用戶給出的字符串。不同進(jìn)程中用同樣的名稱來創(chuàng)建或打開對象，從而獲得該對象在本進(jìn)程的句柄。,Semaphore對象：相當(dāng)于資源信號量，取值在0到指定最大值之間，用于限制并發(fā)訪問的線程數(shù)。有關(guān)的API： CreateSemaphore創(chuàng)建一個(gè)信號量對象，指定最大值和初值，返回對象句柄； OpenSemaphore返回一個(gè)已存在的信號量對象的句柄，用于后續(xù)訪問； ReleaseSemaphore釋放對信號量對象的占用；,Event對象：

46、事件對象，相當(dāng)于觸發(fā)器，可通知一個(gè)或多個(gè)線程某事件的出現(xiàn)。有關(guān)的API： CreateEvent創(chuàng)建一個(gè)事件對象，返回對象句柄； OpenEvent返回一個(gè)已存在的事件對象的句柄，用于后續(xù)訪問； SetEvent和PulseEvent設(shè)置指定事件對象為可用狀態(tài)； ResetEvent設(shè)置指定事件對象為不可用狀態(tài)（nonsignaled）；手工復(fù)位，并喚醒所有等待線程；,（2）同步對象等待,(1) WaitForSingleObject在指定的時(shí)間內(nèi)等待指定對象為可用狀態(tài)(signaled state)； DWORD WaitForSingleObject( HANDLE hHandle, / handle of object to wait for DWORD dwMilliseconds/ time-out interval in milliseconds ); (2) WaitForMultipleObjects在指定的時(shí)間內(nèi)等待多個(gè)對象為可用狀態(tài)； DWORD WaitForMultipleObjects( DWORD nCount, /對象句柄數(shù)組中的句柄數(shù)； CONST HANDLE *lpHandles, / 指向?qū)ο缶?/p>