【文章內(nèi)容簡介】 程交叉執(zhí)行的一段程序。 ?并發(fā)進(jìn)程的制約關(guān)系 – 間接制約（進(jìn)程互斥） ?由于 共享公有資源 而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象。 ?不允許兩個(gè)以上的共享公有資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū) ?系統(tǒng)資源：如 A、 B兩進(jìn)程競爭打印機(jī) – 直接制約（進(jìn)程同步） ?由于 共享對(duì)方的私有資源 所引起的制約。 ?進(jìn)程間合作：如輸入進(jìn)程、計(jì)算進(jìn)程和打印進(jìn)程 47 ? 空閑讓進(jìn) – 各并發(fā)進(jìn)程享有平等的、獨(dú)立的競爭共有資源的權(quán)利， 在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時(shí)，其他并發(fā)進(jìn)程可以進(jìn)入。 ? 讓權(quán)等待 – 不能進(jìn)入臨界區(qū)的進(jìn)程不能阻止其它進(jìn)程進(jìn)入臨界區(qū)。 ? 忙則等待 – 并發(fā)進(jìn)程中的若干個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入 。 ? 有限等待 – 從進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)開始，應(yīng)在有限時(shí)間內(nèi)能夠進(jìn)入，不會(huì)產(chǎn)生死鎖。 進(jìn)程互斥執(zhí)行必須滿足四個(gè)準(zhǔn)則 48 互斥的加鎖實(shí)現(xiàn) 設(shè)鎖定位 Key[S]：屬于臨界區(qū)Ｓ，在Ｓ的數(shù)據(jù)結(jié)構(gòu)中。 key[S]==1： 臨界區(qū) S可用 key[S]==0： 臨界區(qū)Ｓ不可用。 lock ( key[S] ) 臨界區(qū) unlock( key[S] ) ?unlock(key[S]) ： key[S] ← 1 ?lock(key[S])： ?key[S]==0時(shí)， 不允許任何進(jìn)程進(jìn)入臨界區(qū)， ?key[S]==1時(shí)， 僅允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。 lock (x)： begin local v repeat v←x until v==1 x←0 end 有些機(jī)器在硬件中設(shè)置了“測試與設(shè)置”指令，保證第一步和第二步執(zhí)行不可分離。 加鎖 臨界區(qū)可用 當(dāng)同時(shí)有幾個(gè)進(jìn)程調(diào)用 lock(key[S])時(shí)， 在 x←0 語句執(zhí)行之前，可能已有兩個(gè)以上的進(jìn)程由于 key[S]==1而進(jìn)入臨界區(qū) 49 加鎖法的問題 ?不能完全保證 “ 只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū) ” ?循環(huán)測試鎖定位將損耗較多的 CPU計(jì)算時(shí)間。 ?將導(dǎo)致在某些情況下出現(xiàn)不公平現(xiàn)象。 PB B： lock( key[S] ) ＜Ｓ＞ unlock(key[S] ) goto B PA A： lock(key[S] ) 〈 Ｓ 〉 unlock(key[S] ) goto A 進(jìn)程 PB將處于永久饑餓狀態(tài) (starvation) 設(shè) PA已通過 lock 而進(jìn)入 S。 在 PA執(zhí)行 unlock前， key[S] ==0且 PB沒有進(jìn)入 S的機(jī)會(huì)。 當(dāng) PA執(zhí)行完 unlock 后， goto A ， PA將又立即去執(zhí)行 lock 。 50 信號(hào)量和 P,V原語 ? 荷蘭科學(xué)家 。 ? 信號(hào)量 sem是一整數(shù)，與臨界區(qū)所使用的資源有關(guān) ? 物理含義 – S0： 有 S個(gè)資源可用 – S==0： 無資源可用 – S0： |S|表示 S等待隊(duì)列中的進(jìn)程個(gè)數(shù) ? 值只能由 P、 V操作來改變，操作系統(tǒng)利用它的狀態(tài)對(duì)進(jìn)程和資源進(jìn)行管理 信號(hào)量 (semaphore) 51 ? 訪問信號(hào)量的原子操作。 ? P(S) ： 申請(qǐng)一個(gè)資源 ； V(S)： 釋放一個(gè)資源 ? 不可中斷的過程，在屏蔽中斷的情況下連續(xù)執(zhí)行。 ? 實(shí)現(xiàn)并發(fā)進(jìn)程對(duì)臨界區(qū)的訪問。 P， V 原語 圖 P原語操作功能 圖 V原語操作功能 52 P， V操作的優(yōu)缺點(diǎn) ?優(yōu)點(diǎn) – 簡單 – 表達(dá)能力強(qiáng) ?用 P、 V操作可解決任何同步互斥問題 ?缺點(diǎn) – 不夠安全 。 P、 V操作使用不當(dāng)會(huì)出現(xiàn)死鎖 – 遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜 53 用 P、 V原語實(shí)現(xiàn)進(jìn)程互斥 ?sem＝ =1：進(jìn)程 PA、 PB都沒有進(jìn)入臨界區(qū) S ?sem＝ =0：進(jìn)程 PA、 PB中的一個(gè)已經(jīng)進(jìn)入臨界區(qū) ?sem＝ =1：一個(gè)進(jìn)程已經(jīng)進(jìn)入臨界區(qū)，另一個(gè)進(jìn)程 阻塞，等待進(jìn)入臨界區(qū) 設(shè) sem為 互斥信號(hào)量 ，值為（ 1， 0， 1），初值為 1：沒有并發(fā)進(jìn)程使用該臨界區(qū)。有兩個(gè)并發(fā)的進(jìn)程 PA、 PB 54 進(jìn)程同步 ? 同步的概念 ? 私用信號(hào)量 ? 用 P, V原語操作實(shí)現(xiàn)同步 ? 生產(chǎn)者 消費(fèi)者問題 55 同步的概念 ? Pc的輸出結(jié)果是 Pp的執(zhí)行條件， ? Pp的執(zhí)行結(jié)果也是 Pc的執(zhí)行條件。 PP: local Pri B： Repeat Pri ← Buf Until Buf==空 打印 Pri中的數(shù)據(jù) 清除 Pri中的數(shù)據(jù) Goto B PC： local cal A:計(jì)算 得到計(jì)算結(jié)果 cal ← 計(jì)算結(jié)果 Repeat Buf← cal Until Buf==滿 Goto A 假定 PC和 PP對(duì)公用緩沖區(qū) Buf 已采取了互斥措施。 反復(fù)測試語句，造成 CPU時(shí)間的浪費(fèi) 56 進(jìn)程同步的消息傳送實(shí)現(xiàn) ? 如果沒有相應(yīng)的解決方法，進(jìn)程的直接制約將會(huì)造成大量的 CPU時(shí)間浪費(fèi)。 ? 最簡單和直觀的方法：直接制約的進(jìn)程互相給對(duì)方進(jìn)程發(fā)送 執(zhí)行條件已經(jīng)具備的 信號(hào) 。省去對(duì)執(zhí)行條件的測試。 ? 消息（事件） ： 合作進(jìn)程間互相發(fā)送的信號(hào)。 wait(消息名）： 進(jìn)程等待到合作進(jìn)程發(fā)來的消息繼續(xù)執(zhí)行 signal（消息名）： 向合作進(jìn)程發(fā)送消息，將其值置 true。 消息名： Bufempty： Buf空； Buffull： Buf滿 初始化： Bufempty=true， Buffull=false PC： A:wait(Bufempty) 計(jì)算 Buf ← 計(jì)算結(jié)果 Bufempty ← false signal(Buffull) Goto A PP： B:wait(Buffull) 打印 Buf中的數(shù)據(jù) 清除 Buf中的數(shù)據(jù) Buffull ← false signal(Bufempty) Goto B ?進(jìn)程同步 ：并發(fā)進(jìn)程因直接制約，需發(fā)送消息而互相合作、等待，使得各進(jìn)程按一定的速度執(zhí)行的過程。 ?合作進(jìn)程 ：具有同步關(guān)系的一組并發(fā)進(jìn)程。 57 私用信號(hào)量 ?私用信號(hào)量 – 用于進(jìn)程同步，在制約進(jìn)程和被制約進(jìn)程之間，而不是整組進(jìn)程間使用。 – 初值： ０或某個(gè)正整數(shù)ｎ ， 表示資源的數(shù)目 。只允許擁有它的進(jìn)程對(duì)之施加Ｐ操作 ?公用信號(hào)量 – 互斥時(shí)使用的信號(hào)量 – 聯(lián)系著一組并發(fā)進(jìn)程， 初值為１ ，每個(gè)進(jìn)程均可對(duì)之施加Ｐ、Ｖ操作。 58 用 P, V原語操作實(shí)現(xiàn)同步 圖 緩沖區(qū)隊(duì)列 步驟： ?設(shè)置私用信號(hào)量并賦初值 ?進(jìn)程 Pa： Bufempty＝ n ?進(jìn)程 Pb： Buffull＝ ０ ?利用 P,V原語和私用信號(hào)量規(guī)定各進(jìn)程的執(zhí)行次序。 Pa,Pb通過緩沖區(qū)隊(duì)列傳送數(shù)據(jù)。假定數(shù)據(jù)塊長等于緩沖區(qū)長度 條件： 1. Pa往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí) ,至少有一個(gè)緩沖區(qū)是空的 。 2. Pa發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出方式排列。 3. 在 Pa至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前， Pb不可能從緩沖區(qū)中取出數(shù)據(jù) 。 59 PA: deposit(data): begin local x P(Bufempty)； 選一空緩沖區(qū) Buf(x)； Buf(x)← data Buf(x)置滿標(biāo)記 Ｖ (Buffull) end PB: remove(data): begin local x Ｐ (Buffull)； 選一滿緩沖區(qū) Buf(x) data ← Buf(x) Buf(x)置空標(biāo)記 Ｖ ( Bufempty) end 用 P、 V原語操作實(shí)現(xiàn)同步 ?deposit(data)的執(zhí)行結(jié)果是 remove(data)的執(zhí)行條件 , ?當(dāng)緩沖隊(duì)列全部裝滿數(shù)據(jù)時(shí) ,remove(data)的執(zhí)行結(jié)果又是deposit(data)的執(zhí)行條件。 60 P、 V 操作討論 ? P、 V操作必須成對(duì)出現(xiàn)。 ?互斥操作 ： 同處于同一進(jìn)程 ?同步操作 ： 不在同一進(jìn)程中 出現(xiàn) ?如果 P(S1)和 P(S2) 在一起，那么 P操作的順序至關(guān)重要 – 一個(gè)同步 P操作與一個(gè)互斥 P操作在一起：同步 P操作在前 – 兩個(gè) V操作順序無關(guān)緊要 61 生產(chǎn)者 消費(fèi)者問題 圖 生產(chǎn)者 消費(fèi)者問題 ?資源的消費(fèi)者 :使用某一類資源的進(jìn)程 ?資源的生產(chǎn)者 :釋放某一類資源的進(jìn)程。 把并發(fā)進(jìn)程的同步和互斥問題一般化 ?同步 ?消費(fèi)者想接收數(shù)據(jù)，有界緩沖區(qū)至少有一個(gè)單元是滿的； ?生產(chǎn)者想發(fā)送數(shù)據(jù)，有界緩沖區(qū)至少有一個(gè)單元是空的。 ?互斥 ： 有界緩沖區(qū)是臨界資源 62 生產(chǎn)者和消費(fèi)者問題 ?mutex：公用信號(hào)量，保證生產(chǎn)者和消費(fèi)者之間的互斥。表示可用 有界緩沖區(qū)個(gè)數(shù)，初值為 1。 ?avail：生產(chǎn)者的私用信號(hào)量，有界緩沖區(qū)中的空單元數(shù)，初值為 n。 ?full：消費(fèi)者的私用信號(hào)量，有界緩沖區(qū)中的非空單元數(shù) ,初值為 0。 deposit(data): begin Ｐ (avail) Ｐ (mutex) 送數(shù)據(jù)入緩沖區(qū)某單元 Ｖ (full) Ｖ (mutex) end remove(data): begin Ｐ (full) Ｐ (mutex) 取緩沖區(qū)中某單元數(shù)據(jù) Ｖ (avail) Ｖ (mutex) end 同步 P操作與互斥 P操作在一起：同步 P操作在前 Ｐ原語次序混亂，將會(huì)造成進(jìn)程之間的死鎖。 63 進(jìn)程同步和互斥間的關(guān)系 ?相似處 – 互斥是