【文章內容簡介】 …. …... Peterson算法 (兩個進程的 Peterson算法 ) Boolean flag[2]: 數組元素 int turn。 Void P0 ( ) { while( TRUE) { flag[0]= TRUE。 turn=0。 while(flag[1]amp。amp。turn==0) /*wait*/ /*critical area*/ flag[0]=false。 /*noncritical area*/ } } Void P1 ( ) { while (TRUE) { flag[1]= TRUE。 turn=1。 while(flag[0]amp。amp。turn==1)/*wait*/ /*critical area*/ flag[1]=false。 /*noncritical area*/ } } Flag [0] Flag [1] 初始值為 false Peterson算法是正確的算法 turn=j。描述可進入的進程（同時修改標志值） ? 檢查對方 flag，如果不在臨界區(qū)則自己進入－－空閑則入； ? 否則再檢查 turn：保存的是較晚的一次賦值，則較晚的進程等待，較早的進程進入－－先到先入，后到等待。 硬件手段 ( TSLtest and set lock ) 原子操作：這種操作在運行的過程中，是不能也不允許被打斷的，它是操作的最底層的部分，是不可分割的，稱其為原子操作。 TSL工作原理：將一個存儲器字讀到寄存器當中，然后在這個內存中存一個非零的值。這個讀寫的過程是個原子操作，是不可分割的。 Enter_region: tsl register , lock cmp register, 0 jne enter_region ret Leave_region: move lock, 0 ret 硬件方法的優(yōu)點 ? 適用于任意數目的進程，在單處理器或多處理器上 ? 簡單，容易驗證其正確性 ? 可以支持進程內存在多個臨界區(qū)，只需為每個臨界區(qū)設立一個布爾變量 硬件方法的缺點 ? 等待要耗費 CPU時間，不能實現(xiàn) 讓權等待 ? 可能 饑餓 ：從等待進程中隨機選擇一個進入臨界區(qū)，有的進程可能一直選不上 ? 可能死鎖（見下頁） 睡眠和喚醒的引入 對于 Peterson和 TSL問題，都能夠很好地實現(xiàn)互斥，但也都同時存在問題： **忙等待，浪費 CPU的資源。 **進程的優(yōu)先級有差別：當有兩個進程， A、 B， A的優(yōu)先級高，處于就緒狀態(tài)，而此時， B在臨界區(qū)內，由于優(yōu)先級低，故無法被調度，也就無法離開臨界區(qū)，那 A就只能夠在臨界區(qū)外等待。 解決的途徑就是引入新的概念：睡眠 喚醒 睡眠：對應著在臨界區(qū)外的不停判斷和等待； 喚醒：對應著觸發(fā)另一個滿足條件的進程進入臨界區(qū)。 生產者和消費者問題： 問題描述： 若干進程通過有限的共享緩沖區(qū)交換數據。其中， 生產者 進程不斷寫入，而 消費者 進程不斷讀出；共享緩沖區(qū)共有 N個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。 等待使用資源的消費者 共享的緩沖區(qū) 生產者 define N 100 int count=0。 void producer ( void ) { while ( TRUE ) { produce_item ( )。 if (count== N) sleep ( )。 enter_item ( )。 count=count+1。 if (count==1) wakeup (consumer) } } void consumer( void ) { while ( TRUE ) { remove_item ( )。 if (count==0) sleep ( )。 enter_item ( )。 count=count1。 if (count==N1) wakeup (producer ) } } 對于生產者： 只有當緩沖區(qū)里為零的時候，這時候消費者才有可能睡覺； 對于消費者： 只有當緩沖區(qū)里裝滿的時候，這時候生產者才有可能睡覺。 導致的問題：類 Spooler目錄問題 緩沖區(qū)為空，消費者檢查，得到 count=0,但未睡覺的時候，被調度程序掛起，此時它將保留一個局部變量來存儲 count的值，此時生產者開始工作并向緩沖區(qū)內放入資源，當資源等于 1后，向消費者發(fā)送喚醒信號，而此時消費者沒有睡眠，等消費者被恢復以后，檢查自己存儲過的 count，發(fā)覺它等于零，則開始睡眠，而生產者則不停生產，當緩沖區(qū)滿了以后自己也開始睡眠，這時候他們就都處于睡眠狀態(tài)。 信號量 1965年，由荷蘭學者 Dijkstra提出（所以 P、 V分別是荷蘭語的test(proberen)和 increment(verhogen)），是一種卓有成效的 進程同步機制 。 原理：兩個或多個進程可以通過簡單的信號進行合作，一個進程可以被迫在某一個位置停止，直到他接受到一個特定的信號。 為了發(fā)信號，需要一個特殊的變量 信號量 s 為了通過信號量 s傳送信號，進程可執(zhí)行原語 signal (s)。 為了通過信號量 s接收信號，進程可執(zhí)行原語 wait (s)。 對信號量的操作 1. 一個信號量可以初始化為非負數 2. Wait操作是信號量減一，如果值變?yōu)榱素摂?，則執(zhí)行 wait的進程被阻塞； Signal操作是信號量加一，如果值不是正數，則被 wait操作阻塞的進程被解除阻塞。 除了以上三種操作以外，沒有任何其他地方可以檢查或操作信號量。 Wait==P Signal==V 多元信號量的 P V 操作 Struct semaphore{ int count。 queueType queue。 } Void wait(semaphore s) { 。 if ( 0 ) { place this process in 。 block this process。 } } Void signal(semaphore s) { + + 。 if ( =0 ) { remove a process P from 。 place process P on ready list。 } } 此處的 wait 和 signal 都是原子操作，不會被中斷影響。 二元信號量的 P V操作 Void waitB (binary_semaphore s) { if ( == 1 ) =0。 else { place this process in 。 block this process。 } } Void signalB (binary_semaphore s) { if ( ( ) ) =1。 else { remove a process P from 。 place process P on ready list。 } } Struct binary_semaphore { enmu ( zero , one ) value。 queueType queuw 。 } P原語 wait(s) 。 //表示申請一個資源 。 if ( 0) //表示沒有空閑資源 。 { 調用進程進入等待隊列 。 阻塞調用進程 。 } V原語 signal(s) ++。 //表示釋放一個資源； if ( = 0) //表示有進程處于阻塞狀態(tài)； { 從等待隊列 P。 進程 P進入就緒隊列 。 } V原語通常喚醒進程等待隊列中的頭一個進程 利用信號量實現(xiàn)互斥 為臨界資源設置一個互斥信號量 mutex(MUTual Exclusion)，其初值為 1；在每個進程中將臨界區(qū)代碼置于 P(mutex)和 V(mutex)原語之間 必須成對使用 P和 V原語：遺漏 P原語則不能保證互斥訪問，遺漏 V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）； P、 V原語不能次序錯誤、重復或遺漏 V(mutex)。critical sectionremainder sectionP(mutex)。define N 100 //緩沖區(qū)內槽數 Typedef int semaphore。 semaphore mutex=1。 semaphore full=0。 semaphore empty=N。 Void producer(void) { int item。 while(TRUE) { produce_item ( amp。item ) 。 down( amp。empty ) 。 down ( amp。mutex ) 。 enter_item ( item ) 。 up ( amp。mutex ) 。 up( amp。full ) 。 } } Void consumer(void) { int item。 while(TRUE) { down( amp。full ) 。 down ( amp。mutex ) 。 remove_item ( item ) 。 up ( amp。mutex ) 。 up( amp。empty ) 。 consumer_item ( item ) 。 } } 上面程序是利用信號量互斥來解決生產者 消費者問題的。 其中： 信號量 mutex用于互斥，保證任意時刻只能有一個進程讀寫緩沖區(qū)和相關的變量，保證了臨界區(qū)、臨界資源的合理安全使用。 信號量 full和 empty用來保證一定的時間順序發(fā)生或不發(fā)生，它用來通知生產者和消費者，保證了當緩沖區(qū)滿的時候生產者停止運行，以及當緩沖區(qū)空的時候消費者停止運行。 管程 1. 信號量同步的缺點 ? 同步操作分散：信號量機制中，同步操作分散在各個進程中，使用不當就可能導致各進程死鎖（如 P、 V操作的次序錯誤、重復或遺漏） ? 易讀性差：要了解對于一組共享變量及信號量的操作是否正確，必須通讀整個系統(tǒng)或者并發(fā)程序； ? 不利于修改和維護：各模塊的獨立性差，任一組變量或一段代碼的修改都可能影響全局； ? 正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個復雜的系統(tǒng)沒有邏輯錯誤； 2. 管程的引入 1973年， Hoare和 Hanson所提出；其基本思想是把信號量及其操作原語封裝在一個對象內部。即：將共享變量以及對共享變量能夠進行的所有操作集中在一個模塊中。 管程的定義： 管程是關于共享資源的數據結構及一組針對該資源的操作過程所構成的軟件模塊。 管程可增強模塊的獨立性： 系統(tǒng)按資源管理的觀點分解成若干模塊，用數據表示抽象系統(tǒng)資源，同時分析了共享資源和專用資源在管理上的差別，按不同的管理方式定義模塊的類型和結構，使同步操作相對集中，從而增加了模塊的相對獨立性 引入管程可提高代碼的可讀性，便于修改和維護，正確性易于保證：采用集中式同步機制。一個操作系統(tǒng)或并發(fā)程序由若干個這樣的模塊所構成，一個模塊通常較短，模塊之間關系清晰。 3. 管程的主要特性 模塊化：一個管程是一個基本程序單位，可以單獨編譯； 抽象數據類型：管程是一種特殊的數據類型，其中不僅有數據，而且有對數據進行操作的代碼 信息封裝：管程是半透明的，管程中的外部過程（函數）實現(xiàn)了某些功能，至于這些功能是怎樣實現(xiàn)的，在其外部則是不可見的 . 4. 管程的實現(xiàn)要素 管程中的共享變量在管程外部是不可見的，外部只能通過調用管程中所說明的外部過程（函數）來間接地訪問管程中的共享變量； 為了保證管程共享變量的數據完整性，規(guī)定管程互斥進入； 管程通常是用來管理資源的，因而在管程中應當設有進