monitor Condition variable
管程
管程的定義
管程是對共享數(shù)據(jù)的訪問進(jìn)行控制的特殊的一段程序：
- 這是編譯器的一段代碼，在運(yùn)行的時(shí)候執(zhí)行
管程是一個(gè)壓縮了如下內(nèi)容的模塊：
- 共享的數(shù)據(jù)結(jié)構(gòu)
- 對共享數(shù)據(jù)的操作
- 在不同線程之間的同步操作
它能夠：
- 保證數(shù)據(jù)不會有非同步的訪問
- 只允許線程以合理的方式訪問共享數(shù)據(jù)
管程的語義
管程保證互斥訪問：
一次只能有一個(gè)線程“在管程中”（也就是執(zhí)行管程提供的程序）
如果一個(gè)線程在管程中的時(shí)候，有第二個(gè)線程調(diào)用管程中的程序，則這第二個(gè)線程會被阻塞。
如果在管程中的線程被阻塞了，則另外一個(gè)線程就可以進(jìn)入管程
問題：
管程和我們了解的臨界區(qū)有什么區(qū)別呢？
我的理解：管程包括了對共享數(shù)據(jù)的處理函數(shù)。用戶只能使用管程提供的方式，不能自定義；但在臨界區(qū)中用戶可以對共享數(shù)據(jù)做任何事情。臨界區(qū)是指會對共享數(shù)據(jù)產(chǎn)生data race的代碼段，無論是否采取保護(hù)措施臨界區(qū)都是存在的。而管程可以被認(rèn)為是對臨界區(qū)進(jìn)行保護(hù)的一段代碼，包裝了臨界區(qū)和對其互斥訪問的管理。
- 管程的并行是什么含義呢？
管程的使用實(shí)例
Monitor account {
double balance;
double withdraw(amount) {
balance = balance –amount;
return balance;
}
}
如果一個(gè)線程想在管程中等待呢？——條件變量（condition variables）
Attention：
共享變量并不是
if語句中的判斷條件，所以不能if(condition) { ... }
條件變量是：
-
Sleep:線程需要的資源無法獲取的時(shí)候，讓線程等待 -
Wake(or signal):資源可以訪問的時(shí)候叫醒線程 - 'Wakeall (or signalAll)':叫醒所有等待線程
條件變量就是實(shí)現(xiàn)上述操作的一種方式
條件變量 & 鎖
條件變量不能代替鎖，而是和鎖互補(bǔ)的一種機(jī)制
- Wait(condition, lock)
首先釋放鎖，將線程放到
condition的等待隊(duì)列中，如果線程再醒過來，將重新獲得鎖。
在放在等待隊(duì)列的時(shí)候，會讓線程sleep，等sleep返回的時(shí)候，它是被另外一個(gè)持有鎖的線程叫醒的。
- Signal(condition)
叫醒一個(gè)在condition的等待隊(duì)列上的線程
- Broadcast(condition)
叫醒所有在
condition的等待隊(duì)列上的線程
條件變量 & 管程：
管程中的一個(gè)條件變量一般表示的含義是：一個(gè)線程要在管程中繼續(xù)運(yùn)行所需要的條件（比如消費(fèi)者需要資源不為空才能消費(fèi)）
Monitor M {
...monitored variables;
Condition c, d;
void enter_monitor(...) {
if( extra property C not true) wait(c); //等待管程的鎖
do what you have to do
if(extra property true D) signal(d);//叫起在d上等待的線程
}
}
一般條件變量對應(yīng)的操作為：
Wait( ) : 等待管程的鎖，或者等待條件變量被signal了
`Signal( ):’ 叫醒一個(gè)等待線程
'Broadcase( ):' 叫醒所有等待線程
條件變量 != 信號量
有條件變量的管程 != 信號量
但它們可以相互實(shí)現(xiàn)
其區(qū)別在于，對管程訪問用鎖控制，下面是具體分析：
-
wait()操作會阻塞當(dāng)前線程，并放開鎖 - 線程要能進(jìn)行
wait()操作，必須在管程內(nèi)部，也就是必須持有鎖 - Semaphore::P只是阻塞了在隊(duì)列上的線程，線程還沒有持有信號量
-
Signal()使得一個(gè)等待線程被喚醒 - 如果沒有等待的線程，這個(gè)信號其實(shí)沒有用
- 但對Semaphore::V()會增加信號量的值，使得將來其他線程能訪問
- 也就是Condition沒有歷史，但Semaphore是有的。
使用管程和條件變量解決實(shí)際問題
（一）有限緩沖區(qū)問題描述：
有一個(gè)被producer和consumer共享的資源池
- producer向其中放入資源
- consumer從其中拿出資源消耗。
producer和consumer執(zhí)行速度不同：
- 沒有嚴(yán)格的串行化
- 任務(wù)是獨(dú)立執(zhí)行的
- 在buffer上不會發(fā)生線程切換
安全要求：
- 如果nc是消費(fèi)了的資源數(shù)，np是生產(chǎn)了的資源數(shù)，N是buffer的大小。則
0 ≤ np - nc ≤ N
有限緩沖區(qū)代碼
Monitor bounded_buffer {
Resource buffer[N];
//Variables for indexing buffer
Condition not_full; //space in buffer;
Condition not_empty; //value in buffer
void put_resource (Resource R){
if(buffer array is full)
wait(not_full);
Add R to buffer array;
signal(not_empty);
}
Resource get_resource() {
if(buffer array is empty)
wait(not_empty);
Get resource R from buffer array;
signal(not_full);
return R;
}
}
（二）讀者寫者問題
分析：
- 使用Mesa管程，有四個(gè)函數(shù)
StartReadStartWriteEndReadEndWrite - 用
nrnw分別表示讀者和寫者的數(shù)量 - 在
nw = 0的時(shí)候可以讀 - 在'(nw = 0) && (nr = 0)`的時(shí)候可以寫
實(shí)現(xiàn)：
Monitor RW {
int nr = 0, nw = 0;
Condition canRead, canWrite;
void StartRead() {
while(nw != 0) wait(canRead);
nr++;
}
void EndRead() {
nr--;
if(nr == 0) signal(canWrite);
}
void Start Write() {
while(nr != 0 || nw != 0) wait(canRead);
nw++;
}
void EndWrite() {
nw--;
signal(canWrite);
signal(canRead);
}
}
兩種不同的管程實(shí)例——Hoare管程和Mesa管程
兩者的區(qū)別主要是signal()的語義不一樣
Hoare monitors（original）
-
signal()立刻就會進(jìn)行線程切換，即將調(diào)用signal()的線程切換下CPU，讓被wakeup的線程運(yùn)行 -
condition一定會被這個(gè)被wakeup的線程一直持有
Mesa monitors（Mesa，Java）
-
signal()的時(shí)候，是把一個(gè)線程叫醒然后放入readyList，然后繼續(xù)執(zhí)行當(dāng)前線程 -
condition在不一定被這個(gè)被wakeup的線程持有，線程再一次進(jìn)入管程的時(shí)候，必須檢查condition是否滿足。（因?yàn)榭赡鼙?code>readyList上前面的線程用掉了）
具體使用的區(qū)別：
Hoare：
if(empty)
wait(condition)
Mesa：
while(empty)
wait(condition)
比較：
Mesa管程更易于使用，也更有效
- 因?yàn)樯舷挛牡那袚Q比較少，而且容易支持broadcast
Hoare管程則相對不夠靈活
- 但更容易理解
