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