【正文】 處于監(jiān)控器內(nèi)等待，直到它能再次獲得互斥訪問(wèn)，恢復(fù)執(zhí)行。 ? 信號(hào)和出口 SX:既然被占了先 ,發(fā)信號(hào)的進(jìn)程也就不等了 .立即從監(jiān)控器出口或從過(guò)程返回。 ? 信號(hào)和繼續(xù) SC:當(dāng)無(wú)占先時(shí)發(fā)信號(hào)的進(jìn)程繼續(xù)執(zhí)行 .直至它進(jìn)入等待或返回之前 ,其它進(jìn)程是不許進(jìn)入監(jiān)控器的。也可以采用其它辦法實(shí)現(xiàn)條件同步。 UNIX采用上述條件同步。因而共享變量不能并發(fā)訪問(wèn)。 各種語(yǔ)言實(shí)現(xiàn)監(jiān)控器時(shí)的原語(yǔ)語(yǔ)義差異 監(jiān)控器有三個(gè)特征：第一，監(jiān)控器封裝了共享變量，共享變量?jī)H能由監(jiān)控器內(nèi)的過(guò)程訪問(wèn)。 while open0 do wait (customer_left) end。 end。 while chair=0 do wait (chair_occupied) end。 end。 while open=0 do wait (door_open) end。 barber := barber1。 end SEMAPHORE. 注 :本例中 “ ?” 號(hào)表示和前一個(gè)語(yǔ)句并行執(zhí)行的語(yǔ)句 ,以下同 . 例 *** 貪睡的理發(fā)師的模擬解 monitor BARBER_SHOP:: var barber := 0,chair :=0,open =0。 ? if not empty(pos) then signal(pos) endif。 end。 var pos :cond； //當(dāng) V中 pos隊(duì)列非空示真 proc P( ) is if s0 then s:= s1 endif。 end。 end。 //當(dāng) s0， pos示信為真 proc P( ) is while s=0 do wait (pos) end。 （ 見(jiàn)下例 ***） 例 * 以監(jiān)控器作信號(hào)燈 monitor SEMAPHORE:: var s:= 0。 (見(jiàn)下例 **) (5) 會(huì)合同步 進(jìn)程交互是客戶 /服務(wù)器 (C/S)關(guān)系時(shí) ,為此兩交互進(jìn)程必須會(huì)合 (rendezvou)才能得到服務(wù)。 end。 count := count 1。 result := buf [front]。 end。 count := count+1。 buf [rear] := data。 var not_full:cond； //當(dāng) count q示信為真 var not_empty:cond。 : end begin 初始化，激活進(jìn)程 end monitor. 例 : 有界緩沖區(qū)的監(jiān)控器實(shí)現(xiàn)算法 monitor BOUNDED_BUFFER:: var buf[1..q]： TYPE。 end。 proc op1 (形參表 1) is op1 體 end。此外： ? 進(jìn)程和共享變量耦合太緊 ? 臨界區(qū)利寫不利讀，一多了就太散，因而也難修改 四、監(jiān)控器 Dijkstra建議是把分散在整個(gè)程序中的 region語(yǔ)句進(jìn)一步集中成為一個(gè)模塊叫做監(jiān)控器 (monitor)。 end PRODUCER_CONSUMER_CCR. 條件臨界區(qū)評(píng)價(jià) 條件臨界區(qū)最主要的優(yōu)點(diǎn)是概念清晰。 end loop。 m=buf； region sema do empty := empty + 1 end。 end。 region sema do full := full + 1 end。 process PRODUCER [i:1..M]:: loop PRODUCER[i] 產(chǎn)生一條消息 m。 var empty:sema,full:sema。 這樣 , 進(jìn)程處于就緒或阻塞狀態(tài)且未運(yùn)行 。 事實(shí)上多數(shù)分時(shí)處理的機(jī)器 , 單主機(jī)多處理器的機(jī)器是用系統(tǒng)調(diào)用并行核 (或叫管理程序 )實(shí)現(xiàn)的 。 end。 思考問(wèn)題 。 V(forks[1])。 P(forks[5])。 end。 思考問(wèn)題 。 V(forks[i])。 P(forks[i+1])。 故算法如下 : program DINING＿ PHILO: var forks [1..5]: sem:= (5*1)。 每個(gè)哲學(xué)家的行為過(guò)程即為一進(jìn)程 。 如果每人拿一把叉子等待其它人放下叉子 , 就產(chǎn)生死鎖 。經(jīng)典的例子是哲學(xué)家就餐問(wèn)題。 選擇互斥是更為復(fù)雜的同步機(jī)制。 end loop。V (empty)。 front := front mod q+1。 P(mutexF)。 end。 V(full)。 rear := rear mod q+1。 P(matexD)。 ∥ buf 的下標(biāo)變量 var empty : sem :=q , full: sem :=0, ∥ 劈分二值信號(hào) var mutexD: sem := 1, mutexF: sem :=1。 其算法如下 : program PROD＿ CONS var buf [1...q], mi, mj: TYPE。 將 P,V操作擴(kuò)充到多進(jìn)程 , 多資源 (多個(gè)臨界段 )也是很容易的 。 將信號(hào)變量 s一分為二 (empty, full)簡(jiǎn)化了傳遞方向 。 end loop。 ∥ 從 buf取出消息 m的三條操作 m := buf。 end。 V(full)。 deposit : P(empty)。 ∥ 任意類型 TYPE var empty : sem := 1, full : sem := 0。以下是生產(chǎn)者 /消費(fèi)者著名問(wèn)題的同步解。 P, V操作很容易擴(kuò)大到 n個(gè)進(jìn)程競(jìng)爭(zhēng)一個(gè)臨界段。 end。 P2的非臨界段 。 臨界段 。 end p1。 ∥ 出口協(xié)議 P1的非臨界段 。 ∥ 入口協(xié)議 臨界段 。 var mutex : Semaphore := 1。 ∥ ?await? 表達(dá)延遲的原語(yǔ) V(s) : s := s+1。 在其上定義了兩個(gè)操作 P, V(取自荷蘭語(yǔ)字頭 , 即 wait（ 等待 ） 和 signal（ 示信 ） 。 二 、 信號(hào)燈 Dijkstra 首先理解到忙等待的低級(jí)和設(shè)計(jì)麻煩 , 提出了完整的信號(hào)燈 (semaphores)理論 (1968)。 end loop。 enter1 := false。 while enter1 and turn = “P1” do skip。 end. process P2:: loop enter2 := true。 end loop。 enter2 := false。 while enter2 and turn = “P2” do skip。 ∥ 或賦初值 “ P2” process P1:: loop enter1 := true。 enter2 : Boolean := false。 為此 , 尋找以忙等待實(shí)現(xiàn)互斥同步的算法 , 從 65年到 81年有許多名家寫了上百篇論文 , 最后 peterson的算法 (1981)獲得滿意的解。如果某進(jìn)程進(jìn)入循環(huán)且正在更新 lock為 true期間 , 第二個(gè)進(jìn)程又訪問(wèn)了 lock(為 false), 那么它也進(jìn)入臨界段。 end P2。 end do。 look := false。 process pn : end SPIN＿ LOCK process P2:: loop when not lock do lock := true。 end loop。 ∥ 出口協(xié)議 P1的非臨界段 。 ∥ 入口協(xié)議 臨界段 。 這就是著名的自旋鎖 (spin lock), 其算法如下 : 基于共享變量的通訊機(jī)制 program SPIN＿ LOCK: var Lock := false。 程度員也無(wú)法阻塞停止某個(gè)進(jìn)程 。競(jìng)爭(zhēng)進(jìn)程以測(cè)定進(jìn)入條件 (鎖 )保持協(xié)調(diào)地進(jìn)入臨界段 , 我們說(shuō)它在語(yǔ)義上保證了條件同步 。 或送出的消息總能到達(dá)目的進(jìn)程 , 活性深深受到執(zhí)行機(jī)構(gòu)調(diào)度策略的影響 ? 公平性 (fairness)指在有限進(jìn)展的假設(shè)下沒(méi)有一個(gè)進(jìn)程處于死等狀態(tài) . – 無(wú)條件公平性 :調(diào)度策略如能保證每個(gè)無(wú)條件的原子功能均能執(zhí)行 – 弱公平性 :在具有條件原子動(dòng)作時(shí) , 若條件原子動(dòng)作能執(zhí)行并依然保持無(wú)條件公平性 , 則為弱公平性 – 強(qiáng)公平性 :條件原子動(dòng)作一定能執(zhí)行 , 則為強(qiáng)公平性 并發(fā)語(yǔ)言需要解決的基本問(wèn)題 ? 進(jìn)程管理：創(chuàng)建；起動(dòng)（或恢復(fù)）執(zhí)行；阻塞 (或叫凍結(jié) )；停止執(zhí)行；阻塞父進(jìn)程創(chuàng)建子進(jìn)程；撤銷進(jìn)程等六種操作。解決的辦法是在改變某些進(jìn)程的優(yōu)先級(jí) , 在公平性和合理性上作某種折衷 主要內(nèi)容： ? 并發(fā)程序設(shè)計(jì)的基本概念 ? 并發(fā)程序帶來(lái)的問(wèn)題 ? 需要解決的基本問(wèn)題 ? 程序語(yǔ)言示例 并發(fā)語(yǔ)言需要解決的基本問(wèn)題 ? 安全性 (safety)是程序在執(zhí)行期間不會(huì)出現(xiàn)異常的結(jié)果 .對(duì)于順序程序指其最終狀態(tài)是正確的 .對(duì)于并發(fā)程序指保證共享變量的互斥訪問(wèn)和無(wú)死鎖出現(xiàn) ? 活性 (liveness)是程序能按預(yù)期完成它的工作 .對(duì)于順序程序指程序能正常終止 .對(duì)于并發(fā)程序指每個(gè)進(jìn)程能得到它所要求的服務(wù) 。如果優(yōu)先級(jí)不當(dāng)就會(huì)造成某些進(jìn)程永遠(yuǎn)處于阻塞態(tài) , 死等 (但不是死鎖 )。于是 , 除了先來(lái)先服務(wù)而外 , 在調(diào)度例程中約定或在條件中加入優(yōu)先級(jí)表來(lái)達(dá)到此目的。相對(duì)最公平 , 但有的進(jìn)程占用一種資源時(shí)間過(guò)長(zhǎng) , 致使其它資源長(zhǎng)期閑置。 ? 定向 /廣播式通信 所謂定向是發(fā)送方指明接受方 .而廣播式通信發(fā)送方只向公共信道發(fā)送信息 ,任何共享該信道的成員均可接受 , 所以是異步通信 、 單向的 . 主要內(nèi)容 ? 并發(fā)程序設(shè)計(jì)的基本概念 ? 并發(fā)程序帶來(lái)的問(wèn)題 ? 需要解決的基本問(wèn)題 ? 程序語(yǔ)言示例 帶來(lái)的問(wèn)題 (1) 速度依賴 (2) 輸入值依賴 (3) 不確定性 (4) 死鎖 (5) 死等 帶來(lái)的問(wèn)題 (1) 速度依賴 并發(fā)程序執(zhí)行結(jié)果 ,取決于順序成分進(jìn)程執(zhí)行的相對(duì)速度 .對(duì)于并發(fā)且有實(shí)時(shí) (real time)要求的程序 ,執(zhí)行結(jié)果還取決于絕對(duì)速度 . 并發(fā)程序調(diào)整相對(duì)速度的辦法是延遲快進(jìn)程 .把進(jìn)程掛起來(lái) (進(jìn)入懸置態(tài) )待到指定條件滿足才喚醒該進(jìn)程 .其基本原語(yǔ)是 : await表達(dá)式 do 語(yǔ)句｜進(jìn)程 帶來(lái)的問(wèn)題 (2) 輸入值依賴 同一并發(fā)程序兩組數(shù)據(jù)輸入可能會(huì)有很大差別 帶來(lái)的問(wèn)題 (3) 不確定性 順序程序兩次同樣值的測(cè)試 ,一般情況下都是一致的 .即所說(shuō)的再現(xiàn) .并發(fā)程序因上述原因往往沒(méi)有確定的結(jié)果值 .對(duì)于有副作用的函數(shù)或表達(dá)式這種先后次序的差異影響則更大 帶來(lái)的問(wèn)題 (4) 死鎖（ deadlock）是一種狀態(tài) ,由于進(jìn)程對(duì)資源有互不相兼容的要求而使進(jìn)程無(wú)法進(jìn)展 .表現(xiàn)為 : 受到排斥 進(jìn)程永遠(yuǎn)訪問(wèn)不到所需資源 循環(huán)等待 進(jìn)程資源分配鏈形成一封閉回路 無(wú)占先 (no preemption) 進(jìn)程無(wú)法放棄所占的、其它進(jìn)程需要的資源 .所謂占先 ,只要所據(jù)資源的進(jìn)程未處于使用狀態(tài) ,另一優(yōu)先級(jí)高的進(jìn)程有了要求 ,則此資源被后者占去 把持 (wait and hold) 相互以占有對(duì)方資源為放棄已占資源的先決條件 帶來(lái)的問(wèn)題 ? 解決死鎖的方法 : – 利用工具作靜態(tài)死鎖檢測(cè) ,可以避免或減少死鎖出現(xiàn)的可能 – 或事前 ,讓進(jìn)程同時(shí)提出所有需要的資源 , 消除把持條件 , 或強(qiáng)行給資源排序 , 按此順序滿足要求 , 消除循環(huán)等待條件 – 或事前 ,為調(diào)度程序聲明最大的資源需求 – 一旦出現(xiàn) , 最笨的 辦法是重新啟動(dòng) , 試換數(shù)據(jù) , 找出原因改正之。 P是一個(gè)進(jìn)程 , 它并行執(zhí)行 Q進(jìn)程 , 則 P