【正文】 關(guān)車門； signal(close)。 //發(fā)送門已關(guān)的同步信息 售車票； wait(stop)。 //開門前先測試是否停車 開車門； 乘客上下車； until false end parend 管程機制 ? 信號量機制存在下列 3點不足： ? critical section、 entry section和exit section都由用戶編寫； ? 信號量操作原語分散在各程序代碼中，由進(jìn)程來執(zhí)行，系統(tǒng)無法有效控制、管理； ? wait和 signal操作的錯誤使用（次序錯誤、重復(fù)、遺漏等），編譯程序和操作系統(tǒng)都無法發(fā)現(xiàn)、糾正，可導(dǎo)致死鎖。 系統(tǒng)中的各種硬件資源和軟件資源，均可用數(shù)據(jù)結(jié)構(gòu)抽象地描述其資源特性，即用少量信息和對該資源所執(zhí)行的操作來表征該資源，而忽略了它們的內(nèi)部結(jié)構(gòu)和實現(xiàn)細(xì)節(jié)。 例如，對一臺電傳機，可用與分配該資源有關(guān)的狀態(tài)信息 (busy或 free)和對它執(zhí)行請求與釋放的操作，以及等待該資源的進(jìn)程隊列來描述。又如，一個 FIFO隊列，可用其隊長、隊首和隊尾以及在該隊列上執(zhí)行的一組操作來描述。 ? 將所有進(jìn)程對某一臨界資源的同步操作都集中起來，構(gòu)成所謂的 “ 秘書 ” 進(jìn)程，凡要訪問該臨界資源的進(jìn)程，都需先報告 “ 秘書 ” ，由其實現(xiàn)諸進(jìn)程的同步。由此引入管程。 ? 管程（ Monitor）： 一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)程序所執(zhí)行的一組操作。這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)，是進(jìn)程間同步的機制，它保證進(jìn)程互斥地使用臨界資源。 管程 的組成 管程的四個組成部分： ? 名稱 ? 數(shù)據(jù)結(jié)構(gòu)說明 ? 對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的 一組過程 /函數(shù) ? 初始化語句 局部于管程的數(shù)據(jù)結(jié)構(gòu) ， 僅被局部于管程的過程訪問 。 局部于管程的過程 ，也僅能訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu) 。 管程 （ 相當(dāng)于圍墻 ） 把共享變量和對它進(jìn)行操作的若干過程圍起來 。 圖 213 管程的示意圖 共享數(shù)據(jù)?一組操作過程初始化代碼進(jìn)入隊列條件( 不忙) 隊列管程的語法描述如下： type monitor_name = MONITOR； 共享變量說明 ； define (能被其他模塊引用的 )過程名列表 ； use (要調(diào)用的本模塊外定義的 )過程名列表 ； procedure 過程名 (形式參數(shù)表 )； begin end。 … … function 函數(shù)名 (形式參數(shù)表 )：值類型； begin end； begin 管程的局部數(shù)據(jù)初始化語句序列 ； end … … ? 說明： ? 局部于管程的數(shù)據(jù)結(jié)構(gòu)，只能被局部于管程內(nèi)的過程訪問； ? 局部于管程的過程只能訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)； ? 一個進(jìn)程只有通過調(diào)用管程內(nèi)的外部過程才能進(jìn)入管程內(nèi)部訪問共享數(shù)據(jù)； ? 管程每次只允許一個進(jìn)程進(jìn)入，由此實現(xiàn)互斥，由編譯程序編譯時完成 ? 模塊化 :一個管程是一個基本程序單位，可以單獨編譯 ? 抽象數(shù)據(jù)類型 :管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)進(jìn)行操作的代碼 ? 信息掩蔽 :管程是半透明的，管程中的外部過程（函數(shù)）實現(xiàn)了某些功能，管程中的外部過程（函數(shù)）實現(xiàn)了某些功能，至于這些功能是怎樣實現(xiàn)的，在其外部則是不可見的 管程的三個主要的特性 管程和進(jìn)程的比較 ? 主要體現(xiàn)在以下幾個方面： ? (1) 雖然二者都定義了數(shù)據(jù)結(jié)構(gòu)，但進(jìn)程定義的是私有數(shù)據(jù)結(jié)構(gòu) PCB，管程定義的是公共數(shù)據(jù)結(jié)構(gòu)，如消息隊列等； ? (2) 二者都存在對各自數(shù)據(jù)結(jié)構(gòu)上的操作，但進(jìn)程是由順序程序執(zhí)行有關(guān)的操作，而管程主要是進(jìn)行同步操作和初始化操作； 管程和進(jìn)程的比較 ? (3) 設(shè)置進(jìn)程的目的在于實現(xiàn)系統(tǒng)的并發(fā)性，而管程的設(shè)置則是解決共享資源的互斥使用問題； ? (4) 進(jìn)程通過調(diào)用管程中的過程對共享數(shù)據(jù)結(jié)構(gòu)實行操作，該過程就如通常的子程序一樣被調(diào)用，因而管程為被動工作方式，進(jìn)程則為主動工作方式； 管程和進(jìn)程的比較 ? (5) 進(jìn)程之間能并發(fā)執(zhí)行，而管程則不能與其調(diào)用者并發(fā)； ? (6) 進(jìn)程具有動態(tài)性，由 “ 創(chuàng)建 ” 而誕生，由 “ 撤銷 ” 而消亡，而管程則是操作系統(tǒng)中的一個資源管理模塊，供進(jìn)程調(diào)用。 2．條件變量 ? 在利用管程實現(xiàn)進(jìn)程同步時，必須設(shè)置同步工具， 管程機制中設(shè)置兩個同步原語 wait和 signal來實現(xiàn)進(jìn)程同步。進(jìn)程通過管程請求臨界資源未滿足時，管程調(diào)用 wait將其入等待隊列 。當(dāng)其它進(jìn)程訪問完后，管程調(diào)用 signal喚醒等待進(jìn)程。 2．條件變量 ? 考慮一種情況：當(dāng)一個進(jìn)程調(diào)用了管程，在管程中時被阻塞或掛起，直到阻塞或掛起的原因解除，而在此期間，如果該進(jìn)程不釋放管程，則其它進(jìn)程無法進(jìn)入管程，被迫長時間地等待。 ? 為了解決這個問題，引入了條件變量condition。通常，一個進(jìn)程被阻塞或掛起的條件 (原因 )可有多個，因此在管程中設(shè)置了多個條件變量，對這些條件變量的訪問，只能在管程中進(jìn)行。 2．條件變量 ? 管程中對每個條件變量都須予以說明，其形式為： Var x， y： condition。對條件變量的操作僅僅是 wait和 signal，其含義為： ? ① ：正在調(diào)用管程的進(jìn)程因 x條件需要被阻塞或掛起，則調(diào)用 自己插入到 x條件的等待隊列上 ， 并釋放管程 ，直到 x條件變化。此時其它進(jìn)程可以使用該管程。 2．條件變量 ? ② ：正在調(diào)用管程的進(jìn)程 發(fā)現(xiàn)x條件發(fā)生了變化 ，則 調(diào)用 ，重新啟動一個因 x條件而阻塞或掛起的進(jìn)程。如果存在多個這樣的進(jìn)程，則選擇其中的一個，如果沒有，則繼續(xù)執(zhí)行原進(jìn)程，而不產(chǎn)生任何結(jié)果。這與信號量機制中的 signal操作不同，因為后者總是要執(zhí)行 s:=s+1操作，因而總會改變信號量的狀態(tài)。 2．條件變量 ? 例如：對生產(chǎn)者 消費者問題 ? condition notempty,notfull。 ? notempty,notfull分別表示不空、不滿條件； ? 若無空緩沖區(qū)，調(diào)用 阻塞生產(chǎn)者進(jìn)程； ? 若全空，則調(diào)用 ()阻塞消費者進(jìn)程。 問題：多個進(jìn)程出現(xiàn)在管程中 當(dāng)一個進(jìn)入管程的進(jìn)程執(zhí)行等待操作時，它應(yīng)當(dāng)釋放管程的互斥權(quán)；當(dāng)一個進(jìn)入管程的進(jìn)程執(zhí)行喚醒操作時（如Ｐ喚醒Ｑ），管程中便存在兩個同時處于活動狀態(tài)的進(jìn)程 處理方法有三種： ? Ｐ等待Ｑ繼續(xù)，直到Ｑ退出或等待 ? Ｑ等待Ｐ繼續(xù)，直到Ｐ等待或退出 ? 規(guī)定喚醒為管程中最后一個可執(zhí)行的操作 經(jīng)典進(jìn)程的同步問題 ? 三個經(jīng)典的進(jìn)程同步問題： ? 生產(chǎn)者 消費者問題； ? (The ProducerConsumer Problem) ? 哲學(xué)家進(jìn)餐問題； ? (The Dining Philosophers Problem) ? 讀者 寫者問題； ? (The ReadWrite Problem) 生產(chǎn)者 — 消費者問題 問題： 有若干生產(chǎn)者、消費者，共享使用 n個緩沖區(qū)組成的緩沖池： 生產(chǎn)者： 每次產(chǎn)生一個數(shù)據(jù)，放入一個空緩沖區(qū)。若無空緩沖區(qū)，則阻塞； 消費者： 每次從有數(shù)據(jù)的緩沖區(qū)取一個數(shù)據(jù)消費。若所有緩沖區(qū)皆為空，則阻塞； 0 1 2 n1 Producers Consumers In Out 指針移動： in:=(in+1) % n In：空緩沖區(qū)的頭指針，Out：滿緩沖區(qū)的頭指針 1．利用記錄型信號量解決生產(chǎn)者 — 消費者問題 ? 假定在生產(chǎn)者和消費者之間的公用緩沖池中，具有 n個緩沖區(qū)，這時可利用互斥信號量 mutex實現(xiàn)諸進(jìn)程對緩沖池的互斥使用。利用信號量 empty和 full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。 ? 分析： ? 同步： 若所有緩沖區(qū)皆空，消費者阻塞等待生產(chǎn)者生產(chǎn)；若所有緩沖區(qū)皆滿，生產(chǎn)者阻塞等待消費者消費。 ? 設(shè)置同步信號量： ? empty表示現(xiàn)有空緩沖區(qū)數(shù)，初值 =n ? full表示現(xiàn)有滿緩沖區(qū)數(shù)，初值 =0 ? 互斥： 生產(chǎn)者、消費者對緩沖池的操作必須互斥。設(shè)置互斥信號量 mutex， 初值 =1 ? 定義變量： item TYPE buffer[n]。 表示各緩沖區(qū)； ? integer in=0,out=0。 生產(chǎn)、消費緩沖區(qū)指針； Var mutex， empty， full: semaphore:=1,n,0； buffer:array[0， …， n1] of item； in， out: integer:=0， 0； begin parbegin proceducer: begin repeat producer an item nextp； wait(empty)； … … wait(mutex)； buffer(in):=nextp； in:=(in+1) mod n； signal(mutex)； signal(full)； until false； end consumer: begin repeat wait(full)； wait(mutex)； nextc:=buffer(out)； out:=(out+1) mod n； signal(mutex)； signal(empty)； consumer the item in nextc； until false； end parend end wait原語，當(dāng)按如下順序執(zhí)行時： 消費者 : wait(mutex)。 /* 執(zhí)行語句后 mutex為 0*/ 消費者 : wait(full)。 /* full為 1，消費者等待 */ 生產(chǎn)者 : wait(empty)。 /* empty為 k1*/ 生產(chǎn)者 : wait(mutex)。 /* mutex為 1，生產(chǎn)者等待 */ 結(jié)果：導(dǎo)致死鎖。所以 wait原語的次序不能顛倒 ! 2. 如果對調(diào)兩個 signal原語，會使臨界資源的釋放減緩，但加速了 signal(full)和 signal(empty)的操作，總體上無大的影響。 所以 signal原語的次序無關(guān)緊要 ! wait和 signal必須成對地出現(xiàn) ； 資源信號量 的 wait和 signal操作，同樣需要 成對地出現(xiàn) ，但它們分別 處于不同的程序中 。 多個 wait操作順序不能顛倒 ，應(yīng) 先 執(zhí)行對 資源信號量 wait操作，然 后 再執(zhí)行對互斥信號量 wait操作，否則可能引起進(jìn)程死鎖。 在生產(chǎn)者 — 消費者問題中應(yīng)注意 2．利用 AND信號量解決生產(chǎn)者 —消費者問題 ? 在上面的解決方法中，進(jìn)程中的兩個 wait原語的位置不能顛倒，否則，可能導(dǎo)致死鎖，使用AND信號量機制來實現(xiàn)，將對信號量 empty 與 mutex的兩個 wait操作用一個swait(empty,mutex)操作來實現(xiàn)，將對信號量 full與 mutex的兩個 wait操作用一個swait(full,mutex)操作來實現(xiàn)，就可以避免死鎖的產(chǎn)生。實現(xiàn)如下： Var mutex， empty， full: semaphore:=1， n， 0； buffer:array[0， …， n1] of item； in out: integer:=0， 0； begin parbegin producer: begin repeat produce an item in nextp； Swait(empty， mutex)； buffer(in):=nextp； in:=(in+1)mod n； Ssignal(mutex， full)；