【正文】 中斷。 第二章 進(jìn) 程 管 理 2． 記錄型信號(hào)量 在整型信號(hào)量機(jī)制中的 wait操作，只要是信號(hào)量 S≤0，就會(huì)不斷地測試。 因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則，而是使進(jìn)程處于“忙等”的狀態(tài)。 記錄型信號(hào)量機(jī)制則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。 第二章 進(jìn) 程 管 理 但在采取了 “ 讓權(quán)等待 ” 的策略后 ， 又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況 。 為此 ， 在信號(hào)量機(jī)制中 ， 除了需要一個(gè)用于代表資源數(shù)目的整型變量 value外 ， 還應(yīng)增加一個(gè)進(jìn)程鏈表指針 L， 用于鏈接上述的所有等待進(jìn)程 。 記錄型信號(hào)量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的 。 它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為： 第二章 進(jìn) 程 管 理 type semaphore=record value: integer； L: list of process； end 第二章 進(jìn) 程 管 理 相應(yīng)地， wait(S)和 signal(S)操作可描述為： procedure wait(S) var S： semaphore； begin :=； if 0 then block()； end procedure signal(S) var S: semaphore； begin :=+1； if =0 then wakeup()； end 第二章 進(jìn) 程 管 理 在記錄型信號(hào)量機(jī)制中， 資源的數(shù)目，因而又稱為資源信號(hào)量。對它的每次 wait操作，意味著進(jìn)程請求一個(gè)單位的該類資源，使系統(tǒng)中可供分配的該類資源數(shù)減少一個(gè)，因此描述為 :=；當(dāng)0時(shí)，表示該類資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號(hào)量鏈表 ?？梢?，該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。此時(shí)。對信號(hào)量的每次 signal操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位資源，使系統(tǒng)中可供分配的該類資源數(shù)增加一個(gè)，故:=+1操作表示資源數(shù)目加 1。若加 1后仍是≤0，則表示在該信號(hào)量鏈表中，仍有等待該資源的進(jìn)程被阻塞，故還應(yīng)調(diào)用 wakeup原語，將 待進(jìn)程喚醒。如果 1，表示只允許一個(gè)進(jìn)程訪問臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量，用于進(jìn)程互斥。 第二章 進(jìn) 程 管 理 3． AND型信號(hào)量 上述的進(jìn)程互斥問題，是針對各進(jìn)程之間只共享一個(gè)臨界資源而言的。在有些應(yīng)用場合，是一個(gè)進(jìn)程需要先獲得兩個(gè)或更多的共享資源后方能執(zhí)行其任務(wù)。假定現(xiàn)有兩個(gè)進(jìn)程A和 B，他們都要求訪問共享數(shù)據(jù) D和 E。當(dāng)然，共享數(shù)據(jù)都應(yīng)作為臨界資源。為此，可為這兩個(gè)數(shù)據(jù)分別設(shè)置用于互斥的信號(hào)量 Dmutex和 Emutex，并令它們的初值都是 1。相應(yīng)地，在兩個(gè)進(jìn)程中都要包含兩個(gè)對 Dmutex和 Emutex的操作，即 process A: process B: wait(Dmutex)； wait(Emutex)； wait(Emutex)； wait(Dmutex)； 第二章 進(jìn) 程 管 理 若進(jìn)程 A和 B按下述次序交替執(zhí)行 wait操作： process A: wait(Dmutex)； 于是 Dmutex=0 process B: wait(Emutex)； 于是 Emutex=0 process A: wait(Emutex)； 于是 Emutex=1 A阻塞 process B: wait(Dmutex)； 于是 Dmutex=1 B阻塞 最后，進(jìn)程 A和 B處于僵持狀態(tài)。在無外力作用下，兩者都將無法從僵持狀態(tài)中解脫出來。我們稱此時(shí)的進(jìn)程 A和 B已進(jìn)入 死鎖狀態(tài) 。顯然，當(dāng)進(jìn)程同時(shí)要求的共享資源愈多時(shí)，發(fā)生進(jìn)程死鎖的可能性也就愈大。 第二章 進(jìn) 程 管 理 AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源也不分配給它。 亦即，對若干個(gè)臨界資源的分配，采取原子操作方式：要么把它所請求的資源全部分配到進(jìn)程，要么一個(gè)也不分配。 由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在 wait操作中，增加了一個(gè)“ AND”條件，故稱為 AND同步，或稱為同時(shí) wait操作，即 Swait(Simultaneous 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 place the process in the waiting queue associated with the first Si found with Si1， and set the program count of this process to the beginning of Swait operation endif Ssignal(S1， S2， …， Sn) for i:=1 to n do Si:=Si+1； Remove all the process waiting in the queue associated with Si into the ready queue. endfor； 第二章 進(jìn) 程 管 理 4． 信號(hào)量集 在記錄型信號(hào)量機(jī)制中， wait(S)或 signal(S)操作僅能對信號(hào)量施以加 1或減 1操作，意味著每次只能獲得或釋放一個(gè)單位的臨界資源。而當(dāng)一次需要 N個(gè)某類臨界資源時(shí)，便要進(jìn)行 N次 wait(S)操作，顯然這是低效的。此外，在有些情況下，當(dāng)資源數(shù)量低于某一下限值時(shí)，便不予以分配。因而，在每次分配之前，都必須測試該資源的數(shù)量，看其是否大于其下限值?；谏鲜鰞牲c(diǎn)，可以對 AND信號(hào)量機(jī)制加以擴(kuò)充，形成一般化的“信號(hào)量集”機(jī)制。 Swait操作可描述如下，其中 S為信號(hào)量， d為需求值，而 t為下限值。 第二章 進(jìn) 程 管 理 Swait(S1， t1， d1， …， Sn， tn， dn) if Si=t1 and … and Sn=tn then for i:=1 to n do Si:=Sidi； endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation. endive 第二章 進(jìn) 程 管 理 Ssignal(S1， d1， …， Sn， dn) for i:=1 to n do Si:=Si+di； Remove all the process waiting in the queue associated with Si into the ready queue endfor； 第二章 進(jìn) 程 管 理 下面我們討論一般 “ 信號(hào)量集 ” 的幾種特殊情況： (1) Swait(S， d， d)。 此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S， 但允許它每次申請 d個(gè)資源 ， 當(dāng)現(xiàn)有資源數(shù)少于 d時(shí) ， 不予分配 。 (2) Swait(S， 1， 1)。 此時(shí)的信號(hào)量集已蛻化為一般的記錄型信號(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)?0后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開關(guān)。 第二章 進(jìn) 程 管 理 信號(hào)量的應(yīng)用 1． 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥 為使多個(gè)進(jìn)程能互斥地訪問某臨界資源，只須為該資源設(shè)置一互斥信號(hào)量 mutex，并設(shè)其初始值為 1，然后將各進(jìn)程訪問該資源的臨界區(qū) CS置于 wait(mutex)和 signal(mutex)操作之間即可。這樣，每個(gè)欲訪問該臨界資源的進(jìn)程在進(jìn)入臨界區(qū)之前，都要先對 mutex執(zhí)行 wait操作，若該資源此刻未被訪問，本次 wait操作必然成功，進(jìn)程便可進(jìn)入自己的臨界區(qū)，這時(shí)若再有其他進(jìn)程也欲進(jìn)入自己的臨界區(qū)，此時(shí)由于對mutex執(zhí)行 wait操作定會(huì)失敗，因而該進(jìn)程阻塞，從而保證了該臨界資源能被互斥地訪問。當(dāng)訪問臨界資源的進(jìn)程退出臨界區(qū)后，又應(yīng)對 mutex執(zhí)行 signal操作，以便釋放該臨界資源。利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的進(jìn)程可描述如下： 第二章 進(jìn) 程 管 理 Var mutex: semaphore:=1； begin parbegin process 1: begin repeat wait(mutex)； critical section signal(mutex)； remainder seetion until false； end 第二章 進(jìn) 程 管 理 process 2: begin repeat wait(mutex)； critical section signal(mutex)； remainder section until false； end parend 第二章 進(jìn) 程 管 理 2．利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系 還可利用信號(hào)量來描述程序或語句之間的前趨關(guān)系 。 設(shè)有兩個(gè)并發(fā)執(zhí)行的進(jìn)程 P1和 P2。 P1中有語句 S1； P2中有語句S2。 我們希望在 S1執(zhí)行后再執(zhí)行 S2。 為實(shí)現(xiàn)這種前趨關(guān)系 ，我們只須使進(jìn)程 P1和 P2共享一個(gè)公用信號(hào)量 S， 并賦予其初值為 0， 將 signal(S)操作放在語句 S1后面；而在 S2語句前面插入 wait(S)操作 ， 即 在進(jìn)程 P1中 ， 用 S1； signal(S)； 在進(jìn)程 P2中，用 wait(S)； S2； 第二章 進(jìn) 程 管 理 由于 S被初始化為 0，這樣，若 P2先執(zhí)行必定阻塞，只有在進(jìn)程 P1執(zhí)行完 S1； signal(S)；操作后使 S增為 1時(shí)， P2進(jìn)程方能執(zhí)行語句 S2成功。同樣，我們可以利用信號(hào)量，按照語句間的前趨關(guān)系 (見圖 212)，寫出一個(gè)更為復(fù)雜的可并發(fā)執(zhí)行的程序。 圖 212示出了一個(gè)前趨圖，其中 S1， S2， S3， … ， S6是最簡單的程序段 (只有一條語句 )。為使各程序段能正確執(zhí)行，應(yīng)設(shè)置若干個(gè)初始值為“ 0”的信號(hào)量。如為保證 S1→S 2，S1→S 3的前趨關(guān)系，應(yīng)分別設(shè)置信號(hào)量 a 和 b，同樣，為了保證 S2→S 4， S2→S 5， S3→S 6， S4→S 6和 S5→S 6，應(yīng)設(shè)置信號(hào)量 c， d， e， f， g。 第二章 進(jìn) 程 管 理 Var a,b,c,d,e,f,g： semaphore: =0,0,0,0,0,0,0； begin parbegin begin S1； signal(a)； signal(b)； end； begin wait(a)； S2； signal(c)； 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)； wait(g)； S6； end； parend end 第二章 進(jìn) 程 管 理 圖 212 前趨圖舉例 S4S5S3S1S6S2第二章 進(jìn) 程 管 理 管程機(jī)制 1． 管程的定義 系統(tǒng)中的各種硬件資源和軟件資源，均可用數(shù)據(jù)結(jié)構(gòu)抽象地描述其資源特性，即用少量信息和對該資源所執(zhí)行的操作來表征該資源，而忽略