【正文】 1 第 4章 進(jìn)程的同步與通信、進(jìn)程死鎖 主要內(nèi)容： 并發(fā)執(zhí)行，臨界段，信號(hào)量，經(jīng)典進(jìn)程同步問(wèn)題，消息傳遞原理，死鎖。 重點(diǎn)： 臨界段、同步、互斥的概念；信號(hào)量的概念和物理意義；消息傳遞的原理，死鎖的概念。 難點(diǎn)： 信號(hào)量解決進(jìn)程同步與互斥的方法，死鎖防止、避免。 計(jì)算機(jī)操作系統(tǒng) 前趨圖： 用于描述一個(gè)程序的各部分（程序段或語(yǔ)句）間的執(zhí)行順序關(guān)系，或者是一個(gè)大的計(jì)算各子任務(wù)間的因果關(guān)系。 1）是一個(gè)有向無(wú)循環(huán)圖； 2）圖的結(jié)點(diǎn)對(duì)應(yīng)程序中的一條語(yǔ)句、 一個(gè)程序段或一個(gè)進(jìn)程； 3）結(jié)點(diǎn)間的有向邊：表示兩個(gè)結(jié)點(diǎn)之 間存在的偏序或前趨關(guān)系 “ →” ； s1 s3 s2 s5 s4 s7 s6 1. 程序的順序執(zhí)行 計(jì)算機(jī)操作系統(tǒng) 指各程序段按照某種先后次序執(zhí)行，僅當(dāng)前一個(gè)操作執(zhí)行完后才能執(zhí)行后繼操作。 1. 程序的順序執(zhí)行 I1 C1 P1 I2 C2 P2 其中 I、 C、 P分別表示輸入 、 計(jì)算和打印操作 圖 32 程序順序執(zhí)行時(shí)的前趨圖 順序執(zhí)行的特點(diǎn)： 順序性，封閉性，可再現(xiàn)性 計(jì)算機(jī)操作系統(tǒng) 概念： 若干個(gè)程序（或程序段）同時(shí)在系統(tǒng)中運(yùn)行，這些程序（或程序段）的執(zhí)行在時(shí)間上是重疊的，一個(gè)程序（或程序段）的執(zhí)行尚未結(jié)束，另一個(gè)程序（或程序段）的執(zhí)行已經(jīng)開(kāi)始。 2. 程序的并發(fā)執(zhí)行 I1 I2 I3 C1 C2 C3 P1 P2 P3 ? 若順序執(zhí)行三個(gè)作業(yè)共需要 9（ 3*3）分鐘 ? 并行執(zhí)行三個(gè)作業(yè)只需要 5（ 5/3*3）分鐘 計(jì)算機(jī)操作系統(tǒng) ? 間斷性： 并發(fā)程序由于共享資源或?yàn)橥瓿赏豁?xiàng)任務(wù)而相互合作，形成相互制約關(guān)系。 程序并發(fā)執(zhí)行的特點(diǎn)： ? 失去封閉性： 多個(gè)程序共享系統(tǒng)中的各種資源，資源的狀態(tài)將由多個(gè)程序改變，失去封閉性。一個(gè)程序執(zhí)行時(shí)，會(huì)受到其他程序的影響。 ? 不可再現(xiàn)性（待續(xù)） 并發(fā)與共享的問(wèn)題 ：并行程序訪問(wèn)共享數(shù)據(jù)問(wèn)題舉例 :(count為共享變量 初值 =300) Program A: … N=count N=N+100 count=N … Program B:… M=count M=M200 count=M … 如果按以下次序占處理機(jī)運(yùn)行 : N=count,N=N+100。 M=count,M=M200,count=M。 count=N. 結(jié)果 count=400(應(yīng)為 200)* 7 并發(fā)的需要 ? 操作系統(tǒng)應(yīng)盡量支持用戶(hù)態(tài)程序最大限度地并發(fā)執(zhí)行。 ? 程序設(shè)計(jì)要利用 OS對(duì)并發(fā)運(yùn)行的支持，安排事務(wù)并發(fā)執(zhí)行。 ? 操作系統(tǒng)核心程序也要盡可能地并發(fā)運(yùn)行 并發(fā)執(zhí)行實(shí)現(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）兩個(gè)語(yǔ)句可并行執(zhí)行 。 9 ? 識(shí)別程序中的并發(fā)成分有兩種方法： ?程序員寫(xiě)順序程序，用識(shí)別工具識(shí)別并發(fā)成分。再組織使用操作系統(tǒng)的并發(fā)機(jī)制。 ?由程序員識(shí)別并發(fā)成分 : ? 用并發(fā)程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)并發(fā)程序， 由編譯系統(tǒng)安排并發(fā)； ? 直接利用操作系統(tǒng)的系統(tǒng)調(diào)用。 10 ? 并發(fā)程序設(shè)計(jì)語(yǔ)言 并發(fā)語(yǔ)句 ? 它是一種高級(jí)語(yǔ)言； ? 語(yǔ)法形式： Parbegin S1； S2； ?Sn ； Parend； 1）并發(fā)語(yǔ)句示例 1 Parbegin read（ a） ； read（ b） ； Parend； c= a+b； write（ c） ； 11 2）并發(fā)語(yǔ)句示例 2 Var F,G:file of T。 r,s:T。 reset(F)。 read(F,r)。 while not eof(F) do{ s=r。 Parbegin write(G,s)。 read(F,r)。 Parend。 } write(G,r)。 } 優(yōu)點(diǎn) : 并發(fā)語(yǔ)句的結(jié)構(gòu)化特征非常好。 缺點(diǎn)： 存在著描述能力不強(qiáng)的缺點(diǎn)，即存在著用 Parbegin/Parend語(yǔ)句無(wú)法描述的并發(fā)優(yōu)先關(guān)系。 改進(jìn)手段： 輔以其他手段，則并發(fā)語(yǔ)句可以大大增加其描述并發(fā)的能力。 12 ? 前面是對(duì)并發(fā)的高級(jí)語(yǔ)言描述，要真正實(shí)現(xiàn)并發(fā)執(zhí)行，需要通過(guò) OS支持的進(jìn)程機(jī)制。 ? 實(shí)現(xiàn)的兩種方法： 1) OS提供進(jìn)程創(chuàng)建，結(jié)束和同步的系統(tǒng)調(diào)用； 2) 由并行語(yǔ)言編譯器將并發(fā)語(yǔ)言的語(yǔ)句轉(zhuǎn)化為對(duì) OS的系統(tǒng)調(diào)用。 13 與進(jìn)程相關(guān)的系統(tǒng)調(diào)用 ? UNIX操作系統(tǒng)利用進(jìn)程支持并發(fā)執(zhí)行； ? 它提供了如下系統(tǒng)調(diào)用： ? fork（）：創(chuàng)建一個(gè)新進(jìn)程。 (1) 該子進(jìn)程繼承了父進(jìn)程的程序空間，復(fù)制了父進(jìn)程的數(shù)據(jù)段和棧段。 也就是說(shuō)不管是父進(jìn)程還是子進(jìn)程，在占有處理機(jī)后，都從 fork（）調(diào)用的返回點(diǎn)開(kāi)始運(yùn)行 。 (2) 父進(jìn)程 fork（）調(diào)用的返回值是子進(jìn)程的進(jìn)程標(biāo)識(shí) pid； (3) 子進(jìn)程 fork（）調(diào)用的返回值是 0。 14 ? exit（ status）：進(jìn)程結(jié)束。該系統(tǒng)調(diào)用發(fā)出后，操作系統(tǒng)將從系統(tǒng)中刪除調(diào)用 exit的進(jìn)程，并將 status值傳給等待它結(jié)束的父進(jìn)程。 ? wait（ status）：等待子進(jìn)程結(jié)束。 (1)當(dāng)有多個(gè)子進(jìn)程時(shí)，任一個(gè)子進(jìn)程結(jié)束即將控制返回調(diào)用者，并將子進(jìn)程調(diào)用 exit（ status）時(shí)的 status值送到 status指針?biāo)竼卧小? (2)在控制返回調(diào)用者時(shí)，同時(shí)將所等到的子進(jìn)程 pid作為 wait（）系統(tǒng)調(diào)用函數(shù)的返 ? waitpid（ pid， ? ）：等待 pid所指定的進(jìn)程結(jié)束。 15 多進(jìn)程實(shí)現(xiàn)前述的讀寫(xiě)并發(fā)程序 pid = fork（ ） if pid = = 0 then { read（ b） ； exit（ 0） ； } else read（ a） ； wait（ status） ； c = a+b； write（ c）； 16 ? 同步關(guān)系（直接制約）： 為了完成一個(gè)共同任務(wù)，相互協(xié)作的幾個(gè)進(jìn)程需要在某些確定點(diǎn)上協(xié)調(diào)他們的工作，等待來(lái)自其它進(jìn)程的信息，以調(diào)整它們的推進(jìn)速度，方可順利執(zhí)行完畢。 輸入進(jìn)程 緩沖區(qū) 計(jì)算進(jìn)程 進(jìn)程的 同步與互斥 ? 互斥關(guān)系（間接制約）： 把并發(fā)進(jìn)程間存在的因相互競(jìng)爭(zhēng)使用獨(dú)占資源（共享資源）而產(chǎn)生的制約關(guān)系。 例如： 打印機(jī)，共享內(nèi)存； 17 例 1同步關(guān)系 S1 S2 S4 S5 S7 S3 S6 進(jìn)程 P1依次運(yùn)行 S1，S2， S4， S5， S7； 進(jìn)程 P2依次運(yùn)行 S3，