【正文】 信號(hào)量來(lái)描述程序或語(yǔ)句之間的前趨關(guān)系 。 設(shè)有兩個(gè)并發(fā)執(zhí)行的進(jìn)程 P1和 P2。 P1： S1； P2： S2 ； P1 → P2， 設(shè)信號(hào)量 S=0， P1( ) P2( ) { S1 ； { wait(S) ； signal(S)； S2； } } 第二章 進(jìn) 程 管 理 例：混合：順序 /并行 s f Pa Pb Pc 同步規(guī)則： ①當(dāng) Pa完成后， Pb才能開(kāi)始執(zhí)行； ①當(dāng) Pa完成后， Pc才能開(kāi)始執(zhí)行。 Pa Pb Pc 進(jìn)程流圖 前趨圖 第二章 進(jìn) 程 管 理 main ( ) Pa ( ) Pb ( ) Pc ( ) { { { { int Sb=0。 : wait(Sb)。 wait(Sc)。 int Sc=0。 : : : cobegin : : : Pa( )。 signal(Sb)。 : : Pb( )。 signal(Sc)。 } } Pc( )。 } coend } //Sb: pb是否能開(kāi)始執(zhí)行， Sc: pc是否能開(kāi)始執(zhí)行 . 第二章 進(jìn) 程 管 理 main () { int Sa=0。 /*Pa是否執(zhí)行完 */ cobegin Pa()。 Pb()。 Pc()。 coend } 解法 2：也可以只設(shè)置一個(gè)信號(hào)量 Sa=0 Pa() { ….. V(Sa)。 V(Sa)。 } Pb() { P(Sa)。 …… } Pc() { P(Sa)。 ….. } 第二章 進(jìn) 程 管 理 s f Pa Pc Pb 同步規(guī)則： 當(dāng) Pa和 Pb都完成后， Pc才能開(kāi)始執(zhí)行。 ? 例：下圖如何用信號(hào)量實(shí)現(xiàn)同步 Pa Pb Pc 進(jìn)程流圖 前趨圖 第二章 進(jìn) 程 管 理 main ( ) pa ( ) pb ( ) pc ( ) { { { { int Sa=0。 : : wait(Sa)。 int Sb=0。 : : wait(Sb)。 cobegin : : : pa( )。 : : : pb( )。 signal(Sa)。 signal(Sb)。 : pc( )。 } } } coend } //Sa: pa是否執(zhí)行完畢， Sb: pb是否 執(zhí)行完畢。 可否只設(shè)置一個(gè)信號(hào)量 Sa=0？ 第二章 進(jìn) 程 管 理 思考 第二章 進(jìn) 程 管 理 var a,b,c,d,e,f,g,h:semaphore := 0,0,0,0,0,0,0,0。 begin parbegin begin S1。signal(a)。 signal(b)。 signal(c)。 end begin wait(a)。 S2。 signal(d)。 end begin wait(b)。 S3。 signal(e)。 end begin wait(c)。 S4。 signal(f)。 end begin wait(d)。 S5。 signal(g)。 end begin wait(e)。 wait(f)。 S6 。 signal( h)。 end begin wait(g)。 wait(h)。 S7。 end parend end 簡(jiǎn)單做法：有多少“ → ”就設(shè)多少信號(hào)量 第二章 進(jìn) 程 管 理 3． AND型信號(hào)量 對(duì)于兩個(gè)互斥進(jìn)程 A和 B，他們都要求訪問(wèn)共享數(shù)據(jù) D和 E。 互斥的信號(hào)量 Dmutex=1， Emutex=1 process A: process B: wait(Dmutex)； wait(Emutex)； wait(Emutex)； wait(Dmutex)； 第二章 進(jìn) 程 管 理 若進(jìn)程 A和 B按下述次序 交替執(zhí)行 wait操作： A: wait(Dmutex)； 于是 Dmutex=0 B: wait(Emutex)； 于是 Emutex=0 A: wait(Emutex)； 于是 Emutex=1 A阻塞 B: wait(Dmutex)； 于是 Dmutex=1 B阻塞 最后，進(jìn)程 A和 B處于僵持狀態(tài) 。在無(wú)外力作用下，兩者都將無(wú)法從僵持狀態(tài)中解脫出來(lái)。我們稱(chēng)此時(shí)的進(jìn)程 A和 B已進(jìn)入 死鎖狀態(tài) 。 第二章 進(jìn) 程 管 理 AND同步機(jī)制的基本思想是 ：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源， 一次性全部 地 分配給 進(jìn)程，待進(jìn)程使用完后再 一起釋放 。 亦即，對(duì)若干個(gè) 臨界資源 的分配，采取 原子操作 方式：要么把它所請(qǐng)求的資源全部分配到進(jìn)程，要么一個(gè)也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在 wait操作 中，增加了一個(gè) “ AND”條件，故稱(chēng)為 AND同步 ，或稱(chēng)為同時(shí) wait操作 . 第二章 進(jìn) 程 管 理 Swait(S1， S2， … ， Sn) if Si=1 and … and Sn=1 then for i:=1 to n do Si:=Si1； endfor else 將進(jìn)程插入第 i（ Si1）個(gè)等待隊(duì)列， 設(shè)置該進(jìn)程的程序計(jì)數(shù)器到 Swait操作的開(kāi)始 endif Ssignal(S1， S2， … ， Sn) for i:=1 to n do Si:=Si+1； 將所有等待 Si資源的進(jìn)程移到就緒隊(duì)列 endfor； Swait(Simultaneous wait)定義如下 : 第二章 進(jìn) 程 管 理 4． 信號(hào)量集 在記錄型信號(hào)量機(jī)制中， wait(S)或 signal(S)操作僅能對(duì)信號(hào)量施以加 1或減 1操作，意味著每次只能獲得或釋放一個(gè)單位的臨界資源。而當(dāng)一次需要 N個(gè)某類(lèi)臨界資源時(shí)，便要進(jìn)行 N次 wait(S)操作，顯然這是低效的。此外，在有些情況下，當(dāng)資源數(shù)量低于某一下限值時(shí)，便不予以分配。因而，在每次分配之前，都必須測(cè)試該資源的數(shù)量，看其是否大于其下限值?；谏鲜鰞牲c(diǎn)，可以 對(duì) AND信號(hào)量機(jī)制 加以擴(kuò)充，形成 一般化的“信號(hào)量集”機(jī)制 。 第二章 進(jìn) 程 管 理 Swait（ s[n]， t[n]， d[n]） 操作可描述如下 ， 其中 S為信號(hào)量 ，d為需求值 ， 而 t為下限值 。 Swait(S1， t1， d1， … ， Sn， tn， dn) if S1=t1 and … and Sn=tn then for i:=1 to n do Si:=Sidi； endfor else 將進(jìn)程插入第 i（ Sit）個(gè)等待隊(duì)列， 設(shè)置該進(jìn)程的程序計(jì)數(shù)器到 Swait操作的開(kāi)始 endfor。 c程序如何寫(xiě)？ 第二章 進(jìn) 程 管 理 Ssignal(S1， d1， …， Sn， dn) for i:=1 to n do Si:=Si+di； 將所有等待 Si資源的進(jìn)程移到就緒隊(duì)列 endfor； 第二章 進(jìn) 程 管 理 一般 “ 信號(hào)量集 ” 的 特例 ： n=1 (1) Swait(S， d， d)。 d=t， 一個(gè)信號(hào)量 S， 每次申請(qǐng) d個(gè)資源 ， 當(dāng)現(xiàn)有資源數(shù)少于 d時(shí) ， 不予分配 。 (2) Swait(S， 1， 1)。 d=t=1， 記錄型信號(hào)量 (S1時(shí) )或 互斥信號(hào)量 (S=1時(shí) )。 (3) Swait(S， 1， 0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng) S≥1 時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng) S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè) 可控開(kāi)關(guān) 。 ？？？ d=0 第二章 進(jìn) 程 管 理 wait、 signal操作優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 簡(jiǎn)單，而且表達(dá)能力強(qiáng)（可解決 所有的同步互斥問(wèn)題）； 缺點(diǎn)： 不夠安全， wait、 signal操作不當(dāng)會(huì)產(chǎn)生死鎖，實(shí)現(xiàn)復(fù)雜，易讀性差，不利于修改和維護(hù)，正確性難以保證。 第二章 進(jìn) 程 管 理 管程機(jī)制 為什么要引入管程 (Monitors) 信號(hào)量機(jī)制功能強(qiáng)大，但使用時(shí)對(duì)信號(hào)量的操作分散，而且難以控制，讀寫(xiě)和維護(hù)都很困難。因此后來(lái)又提出了一種 集中式同步進(jìn)程 ——管程。其 基本思想 是將共享變量和對(duì)它們的操作集中在一個(gè)模塊中，操作系統(tǒng)或并發(fā)程序就由這樣的模塊構(gòu)成。這樣模塊之間聯(lián)系清晰，便于維護(hù)和修改，易于保證正確性。 管程通常是用于管理資源的。 第二章 進(jìn) 程 管 理 管程機(jī)制 管程的基本概念 ? 管程的定義 ?? 由過(guò)程、初始化序列和局部數(shù)據(jù)組成的 軟件模塊 ??? 特點(diǎn) ? 局部變量只能被管程的過(guò)程訪問(wèn)； ? 進(jìn)程通過(guò)調(diào)用管程的過(guò)程進(jìn)入管程； ? 只能有一個(gè)進(jìn)程在管程中執(zhí)行 ，其他被阻塞。 ??? 條件變量 x——解決同步問(wèn)題 ?? ?? 第二章 進(jìn) 程 管 理 管程的結(jié)構(gòu) condition c1 wait(c1) … condition wait() Urgent queue signal 局部數(shù)據(jù) 條件變量 過(guò)程 1 過(guò)程 k 出口 初始化代碼 入口 管程 等待調(diào)用的進(jìn)程隊(duì)列 管程等待區(qū)域 … 第二章 進(jìn) 程 管 理 管程、信號(hào)量、進(jìn)程區(qū)別 ?信號(hào)量和條件變量區(qū)別 P57 ?wait: S。 阻塞