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

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

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

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

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

5、序為每個并行語句Si設置一個進程。,程序并行性表示舉例,假設有一個程序由 S0Sn+1個語句， 其中 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,算數表達式求值: (a-b)*(c-d)+(e/f)*2,a b c d e f,2,并行程序設計的特點,并行、異步的在系統(tǒng)內運行 共享各類資源，彼此相互制約 只有在

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

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

8、序快時，有些數據會丟失； 如輸入程序送入一個字符“B”，緊接著（當輸出程序還未取走字符“B”）又送入字符“N”，這時輸出程序取走的是“N”，“B”就丟失了。,并發(fā)執(zhí)行實例：謄抄,三個并發(fā)執(zhí)行程序的謄抄 get程序負責從輸入序列f中讀取字符并送到緩沖區(qū)s中； copy程序把緩沖區(qū)s中的數據復制到緩沖區(qū)t中去; put程序從緩沖區(qū)t中取出數據打印。,若程序錯寫成： 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三個程序段并發(fā)執(zhí)行，就有六種組合： 1、copy;put;get 導致結果：g=(R1,R1) 2、copy;get;put 導致結果：g=(R1,R1) 3、put;copy;get 導致結果：g=(R1,R1) 4、put;get;copy 導致結果：g=(R1,R1) 5、get;copy;put 導致結果：g=(R1,R2) 6、get;put;copy 導致結果：g=(R1,R1) 這就是與時間有關的錯誤。,程序并發(fā)執(zhí)行的特點,失去了程序的封閉性 如果程序執(zhí)行的結果是一個與時間無關

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

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

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

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

14、: while flagj do skip,中斷屏蔽法,禁止一切中斷發(fā)生。 單CPU中，引起進程切換的唯一原因是中斷，故單CPU下可行。 缺點： 代價高，影響并發(fā)性 不安全，將禁止一切中斷權利給了普通用戶。 局限性：不適合多CPU，一個進程只能禁止本CPU的中斷。,硬件指令方法,思路：一條指令完成讀寫兩個操作 手段：執(zhí)行硬件指令的CPU封鎖內存總線，以禁止其他CPU在該指令完成前訪問內存。 兩種指令： TS指令和Swap指令,硬件指令方法（續(xù)）,TS：test-and-set指令，讀出指定標志后把該標志設置為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指令：該指令的功能是交換兩個字的內容。 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,存在的缺點,忙等待：上述硬件指令雖然可以有效的保證進程間互斥，但是進程在臨界段中執(zhí)行時，其他想進入臨界段的進程必須不斷地檢測布爾變量lock的值，這就造成了處理機時的浪費，通常稱這種情況為“忙等待”。 饑餓：由于采用隨機從等待隊列中選取進程，會出現有的進程一直處于等待。 需CPU支持,硬件指令方法的優(yōu)點,不但適用于單處理器情況，而且適用于共享主存的SMP多處理器情況（即對稱多處理器）； 方法簡單，行而有效； 可以被使用于多重臨界段

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

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

19、，使其變?yōu)榫途w狀態(tài)，然后返回原進程繼續(xù)執(zhí)行其他代碼 忙等待方式 S:=S1,硬件指令實現互斥的同步原語,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; /開鎖,信號量的數據結構,整型：忙等待方式 記錄型結構：阻塞等待方式 type SemaphoreRecord value:integer L: point to PCB

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

21、：4個進程共享2臺打印機,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),利用信號量實現互斥,描述：多個進程共享臨界資源，并且對資源的訪問是互斥的，資源可用單位數為1。,Begin parbegin P1； Pi； Pn； parend end,Pi： Begin Repeat 臨界段; 剩余段； forever end,var mutex:Semaphore；,mutex:=1；,wait(mutex);,signa

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

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

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

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

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

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

28、區(qū)中取出數據”； signal(E); forever end,生產者、消費者問題,Main（） begin F:=0; E:=n; mutex:= 1; cobegin Producer 1; Producer 2; Producer n; Consumer1; Consumer2; Consumer m; coend end,生產者、消費者問題,特點 Wait次序不能顛倒，否則會出現死鎖 當E0，Fn時， P：wait（mutex）-p:wait(E)- S:wait(mutex)-S:wait(F) 當En，F0時， S：wait（mutex）-S:wait(F)- P:wait(mut

29、ex)-P:wait(E) 生產者和消費者的緩沖指針P、C不能同時移動。即緩沖分配不能同時進行。 可改進：將兩個互斥信號量來分別控制對指針P、C的操作。,閱讀者、寫入者問題,定義：指多個進程對一個共享資源進行讀寫操作的問題。 閱讀者：對共享資源進行讀操作的進程。 寫入者：對共享資源進行寫操作的進程 原則： 任何時候寫入者最多只允許1個，閱讀者可有多個； 對共享資源的讀寫操作限制關系包括: “讀”“寫” ：互斥 “寫”“寫”：互斥 “讀”“讀”：允許 當無寫入者正在訪問共享數據集時，閱讀者可以進行訪問，否則必須等待。 當無閱讀者正在訪問共享數據集時，寫入者可以進行訪問，否則必須等待。,閱讀者、寫

30、入者問題,信號量的考慮： 兩個共享資源： Readcount:記錄正在讀的閱讀者人數。 共享數據集 Readcount的訪問：對閱讀者是互斥的，用mutex作訪問的互斥信號量。 共享數據集的訪問：對寫操作互斥，讀寫操作互斥，用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); 讀數據集；wait(mutex);readcount:=readcount-1; if readcount=0 then signal(wrt); signal(mutex); end,Writeri: begin wait(wrt);寫數據集； signal(wrt); end; parend,閱讀者、寫入者問題,特點： 某種程度上，閱讀者優(yōu)先，寫入者總在所有閱讀者完成后才進行。 各閱讀者可并發(fā)運行。 練習： 讀者優(yōu)先= 寫入者優(yōu)先 兩種情形： 1、寫入者封鎖后來的閱讀者； 2、第一個寫入者封鎖后來的閱讀者，并且后來的寫入者可以優(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,哲學家用餐問題,一個典型的進程同步問題。 問題的描述：有五個哲學家，他們的生活是交替地進行思考和就餐。哲學家們共一張圓桌，周圍放有五張椅子，每人坐一張。在圓桌上有五個碗和五只筷子，當一個哲學家思考時，他不與同事交談，饑餓時便試圖取左、右最靠近他的筷子，但他可能一支都拿不到。只有在他拿到兩支筷子時方能就餐。餐畢，放下筷子繼續(xù)思考。,一個簡單的解法是，用一個信號量表示一支筷子 這五個信號量構成信號量數組，其描述為： var chopstick:

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

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

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

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

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

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

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

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

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

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

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

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

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