簡介
引入管程的原因
信號量機制的缺點:進程自備同步操作,P(S)和V(S)操作大量分散在各個進程中,不易管理,易發生死鎖。1974年和1977年,Hore和Hansen提出了管程。
管程特點:管程封裝了同步操作,對進程隱蔽了同步細節,簡化了同步功能的調用界面。用戶編寫並發程式如同編寫順序(串列)程式。
引入管程機制的目的:1、把分散在各進程中的臨界區集中起來進行管理;2、防止進程有意或無意的違法同步操作;3、便於用高級語言來書寫程式,也便於程式正確性驗證。
管程的定義
管程是由局部於自己的若干公共變數及其說明和所有訪問這些公共變數的過程所組成的軟體模組。
組成部分
1)局部於管程的共享變數;
2)對數據結構進行操作的一組過程;
3)對局部於管程的數據進行初始化的語句。
管程的屬性
共享性:管程可被系統範圍內的進程互斥訪問,屬於共享資源
安全性:管程的局部變數只能由管程的過程訪問,不允許進程或其它管程直接訪問,管程也不能訪問非局部於它的變數。
互斥性:多個進程對管程的訪問是互斥的。任一時刻,管程中只能有一個活躍進程。
封裝性:管程內的數據結構是私有的,只能在管程內使用,管程內的過程也只能使用管程內的數據結構。進程通過調用管程的過程使用臨界資源。管程��Java中已實現。
管程結構分析
管程的組成結構
(1)局部數據和條件變數組成管程內的數據結構;
(2)過程/函式1~過程/函式k組成管程內的一組過程對管程內的數據結構進行操作;
(3)初始化代碼對管程內的數據結構進行初始化。
管程入口處的等待佇列
管程是互斥進入的,所以當一個進程試圖進入一個巳被占用的管程時它應當在管程的入口處等待,因而在管程的入口處應當有一個進程等待佇列,稱作入口等待佇列。
管程內的資源等待佇列
管程是用於管理資源的,當進入管程的進程因資源被占用等原因不能繼續運行時使其等待,即將等待資源的進程加入資源等待佇列,該佇列由條件變數維護。資源等待佇列可以由多個,每種資源一個佇列。
條件變數
條件變數(例如名稱為c)是管程內的一種數據結構,且只有在管程中才能被訪問,它對管程內的所有過程是全局的,只能通過兩個原語操作來控制它。
c.wait( )-調用進程阻塞並移入與條件變數c相關的佇列中,並釋放管程,直到另一個進程在該條件變數c上執行signal( )喚醒等待進程並將其移出條件變數c佇列。
c.signal( )-如果存在其他進程由於對條件變數c執行wait( )而被阻塞,便釋放之;如果沒有進程在等待,那么,信號被丟棄。
條件變數與P、V操作中信號量的區別:
條件變數是一種信號量,但不是P、V操作中純粹的計數信號量,沒有與條件變數關聯的值,不能像信號量那樣積累供以後使用,僅僅起到維護等待進程佇列的作用。因此在使用條件變數x時,通常需要定義一個與之配套使用的整型變數x-count用於記錄條件變數x所維護等待佇列中的進程數。
管程內的緊急等待佇列
當一個進入管程的進程執行等待操作wait時,其它進程應該被允許進入管程;
當一個進入管程的進程執行喚醒操作signal時(如P喚醒Q),管程中便存在兩個同時處於活動狀態的進程,由於任一時刻,管程中只能有一個活躍進程。所以處理辦法為:
1)P等待Q繼續,直到Q退出或等待
2)Q等待P繼續,直到P等待或退出
3)規定喚醒signal為管程中最後一個可執行的操作
管程的實現
Hoare管程數據結構
mutex
信號量mutex管理管程入口處的等待佇列,供管程中過程互斥調用,初值為1。
進程調用管程中的任何過程時,應執行P(mutex);進程退出管程時應執行V(mutex)開放管程,以便讓其他調用者進入。
為了使進程在等待資源期間,其他進程能進入管程,故在wait操作中也必須執行V(mutex),否則會妨礙其他進程進入管程,導致無法釋放資源。
執行wait操作的進程需要釋放信號量mutex,不在mutex信號量上等待,而在其它條件變數(或信號量)上等待。
next和next-count
信號量next管理管程內的緊急等待佇列其初值為0,凡發出signal操作的進程應該用P(next)掛起自己,加入緊急等待佇列,直到被釋放進程退出管程或產生其他等待條件。
進程在退出管程的過程前,須檢查是否有別的進程在信號量next(即緊急等待佇列)上等待,若有,則用V(next)喚醒它。next-count初值為0,用來記錄在next (即緊急等待佇列)上等待的進程個數。
x-sem和 x-count
信號量x-sem用來管理資源等待佇列,其初值為0,進程申請資源得不到滿足時,執行P(x-sem)掛起,加入x-sem所代表的資源佇列。由於釋放資源時,需要知道是否有別的進程在等待資源,用計數器x-count(初值為0)記錄等待資源(即資源等待佇列中)的進程數。
執行signal操作時,應讓等待資源(即資源等待佇列中)的諸進程中的某個進程立即恢復運行,而不讓其他進程搶先進入管程,這可以用V(x-sem)來實現。