【正文】 信號量 ? mutex, 初值為 1，控制互斥訪問緩沖池。} 45 三個經(jīng)典的進程同步問題： 有限緩沖區(qū)問題（生產(chǎn)者 消費者問題）； (The ProducerConsumer Problem) 讀者 寫者問題； (The Read/Write Problem) 哲學(xué)家就餐問題； (The Dining Philosophers Problem) 46 有限緩沖區(qū)的生產(chǎn)者 /消費者問題（生產(chǎn)者和消費者共享一個產(chǎn)品緩沖池）。 V(e)。 V(d)。 V(b)。 解決進程同步問題時關(guān)鍵： 44 一般地，定義 n個信號量來描述有 n條 邊的前趨圖，初值都設(shè)為 0。//發(fā)送已關(guān)門信息 售車票； P(stop)。 Semaphore stop=0,close=0。 …… } …… P(synch)。 輸出機票已售完 。 Ri =Xi。 mutex=1。Ri =Xj； ③ pi再執(zhí)行 Xi= Xi1。 //將票務(wù)中心該次航班的余票 //取出送該進程工作單元 Xi if (Xi=1) { Xi= Xi1。 2）各進程在進入臨界段前先對該信號量進行 P操作，退出臨界段后執(zhí)行 V操作，從而保證各進程互斥的進入相關(guān)臨界段。 4. P,V操作的優(yōu)點： 同步能力強 5. P,V操作的缺點： 程序結(jié)構(gòu)差，易產(chǎn)生死鎖。一個 PCB隊列 } Semaphore Semaphore S。 } 32 實現(xiàn)信號量時與進程調(diào)度相結(jié)合，消除忙等待現(xiàn)象。 enableIntrrupt()。 ? P,V操作的實現(xiàn) 31 P(s)， V(s)的實現(xiàn) P(s){ disableIntrrupt()。 noncritical section }while(1) 29 信號量 (1965年， Dijkstra提出 ) 信號量機構(gòu)：“信號量”、“ P， V操作”。利用Swap指令，可實現(xiàn)對臨界區(qū)的加鎖與解鎖。 //臨界區(qū) lock=false。 enableInterrupt()。 Balance=balance+amount。 count:=N。 M:=M+1。//剩余區(qū) }； 22 例 2： P1,P2兩進程使用同一打印機。 21 一個訪問臨界資源的進程描述如下： While (1) { entry code。 ?對臨界資源的互斥使用，應(yīng)先申請、判斷。 P2 N=account。 account=N。 M=M+1。 例如： 打印機，共享內(nèi)存； 17 例 1同步關(guān)系 S1 S2 S4 S5 S7 S3 S6 進程 P1依次運行 S1，S2， S4， S5， S7； 進程 P2依次運行 S3，S6 18 ? 臨界資源 臨界資源： 一次僅允許一個進程使用的硬件或軟件資源。 (1)當(dāng)有多個子進程時，任一個子進程結(jié)束即將控制返回調(diào)用者，并將子進程調(diào)用 exit（ status）時的 status值送到 status指針?biāo)竼卧小? (2) 父進程 fork（）調(diào)用的返回值是子進程的進程標(biāo)識 pid； (3) 子進程 fork（）調(diào)用的返回值是 0。 ? 實現(xiàn)的兩種方法： 1) OS提供進程創(chuàng)建，結(jié)束和同步的系統(tǒng)調(diào)用； 2) 由并行語言編譯器將并發(fā)語言的語句轉(zhuǎn)化為對 OS的系統(tǒng)調(diào)用。 } 優(yōu)點 : 并發(fā)語句的結(jié)構(gòu)化特征非常好。 Parbegin write(G,s)。 r,s:T。 9 ? 識別程序中的并發(fā)成分有兩種方法： ?程序員寫順序程序，用識別工具識別并發(fā)成分。 M=count,M=M200,count=M。 2. 程序的并發(fā)執(zhí)行 I1 I2 I3 C1 C2 C3 P1 P2 P3 ? 若順序執(zhí)行三個作業(yè)共需要 9（ 3*3）分鐘 ? 并行執(zhí)行三個作業(yè)只需要 5（ 5/3*3）分鐘 計算機操作系統(tǒng) ? 間斷性： 并發(fā)程序由于共享資源或為完成同一項任務(wù)而相互合作，形成相互制約關(guān)系。 難點： 信號量解決進程同步與互斥的方法，死鎖防止、避免。 重點： 臨界段、同步、互斥的概念；信號量的概念和物理意義；消息傳遞的原理，死鎖的概念。 1. 程序的順序執(zhí)行 I1 C1 P1 I2 C2 P2 其中 I、 C、 P分別表示輸入 、 計算和打印操作 圖 32 程序順序執(zhí)行時的前趨圖 順序執(zhí)行的特點： 順序性，封閉性，可再現(xiàn)性 計算機操作系統(tǒng) 概念： 若干個程序（或程序段）同時在系統(tǒng)中運行，這些程序（或程序段）的執(zhí)行在時間上是重疊的，一個程序（或程序段）的執(zhí)行尚未結(jié)束，另一個程序（或程序段）的執(zhí)行已經(jīng)開始。 ? 不可再現(xiàn)性（待續(xù)） 并發(fā)與共享的問題 ：并行程序訪問共享數(shù)據(jù)問題舉例 :(count為共享變量 初值 =300) Program A: … N=count N=N+100 count=N … Program B:… M=count M=M200 count=M … 如果按以下次序占處理機運行 : N=count,N=N+100。 ? 操作系統(tǒng)核心程序也要盡可能地并發(fā)運行 并發(fā)執(zhí)行實現(xiàn) S1 S2 S3 圖 任務(wù)中子任務(wù)關(guān)系示意圖 8 并發(fā)編程方法 ? 傳統(tǒng)的串行程序存在著并行成分： Read (a)； Read (b)； c = a + b； Write (c) Read（ a）和 Read（ b）兩個語句可并行執(zhí)行 。 10 ? 并發(fā)程序設(shè)計語言 并發(fā)語句 ? 它是一種高級語言； ? 語法形式： Parbegin S1； S2； ?Sn ； Parend； 1）并發(fā)語句示例 1 Parbegin read（ a） ； read（ b） ； Parend； c= a+b； write（ c） ； 11 2）并發(fā)語句示例 2 Var F,G:file of T。 while not eof(F) do{ s=r。 } write(G,r)。 12 ? 前面是對并發(fā)的高級語言描述，要真正實現(xiàn)并發(fā)執(zhí)行，需要通過 OS支持的進程機制。 也就是說不管是父進程還是子進程，在占有處理機后，都從 fork（）調(diào)用的返回點開始運行 。 ? wait（ status）：等待子進程結(jié)束。 輸入進程 緩沖區(qū) 計算進程 進程的 同步與互斥 ? 互斥關(guān)系（間接制約）： 把并發(fā)進程間存在的因相互競爭使用獨占資源（共享資源）而產(chǎn)生的制約關(guān)系。 同步與臨