|
信號量機(jī)制 信號量 1965年，荷蘭學(xué)者Dijkstra提出了利用信號量機(jī)制解決進(jìn)程同步問題，信號量正式成為有效的進(jìn)程同步工具，現(xiàn)在信號量機(jī)制被廣泛的用于單處理機(jī)和多處理機(jī)系統(tǒng)以及計算機(jī)網(wǎng)絡(luò)中。 信號量S是一個整數(shù)，S大于等于零時代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，但S小于零時則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。 PV操作 操作系統(tǒng)里進(jìn)程之間通信信號量的兩種操作：PV操作 P,V原語理論 p操作和v操作是不可中斷的程序段，稱為原語。P,V原語中P是荷蘭語的Passeren，相當(dāng)于英文的pass, V是荷蘭語的Verhoog,相當(dāng)于英文中的incremnet。需要注意的是P、V操作對于每一個進(jìn)程來說，都只能進(jìn)行一次。而且必須成對使用。且在P,V愿語執(zhí)行期間不允許有中斷的發(fā)生。 P原語操作的動作是： （1） sem減1； （2） 若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行； （3） 若sem減1后小于零，則該進(jìn)程被阻塞后進(jìn)入與該信號相對應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。 V原語操作的動作是： （1） sem加1； （2） 若相加結(jié)果大于零，則進(jìn)程繼續(xù)執(zhí)行； （3） 若相加結(jié)果小于或等于零，則從該信號的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。 對于具體的實(shí)現(xiàn)，方法非常多，可以用硬件實(shí)現(xiàn)，也可以用軟件實(shí)現(xiàn)。我們采用如下的定義： procedure p(var s:samephore); { s.value=s.value-1; if (s.value<0) asleep(s.queue); } procedure v(var s:samephore); { s.value=s.value+1; if (s.value<=0) wakeup(s.queue); } 其中用到兩個標(biāo)準(zhǔn)過程： asleep(s.queue);執(zhí)行此操作的進(jìn)程控制塊進(jìn)入s.queue尾部，進(jìn)程變成等待狀態(tài) wakeup(s.queue);將s.queue頭進(jìn)程喚醒插入就緒隊(duì)列 對于這個過程，s.value初值為1時，用來實(shí)現(xiàn)進(jìn)程的互斥 P,V原語的應(yīng)用 （1）用P V原語實(shí)現(xiàn)進(jìn)程互斥 把臨界區(qū)置于P(sem) 和V(sem)之間。當(dāng)一個進(jìn)程想要進(jìn)入臨界區(qū)時，它必須先執(zhí)行P原語操作以將信號量sem減1，在進(jìn)程完成對臨界區(qū)的操作后，它必須執(zhí)行V原語操作以釋放它所占用的臨界區(qū)。從而就實(shí)現(xiàn)了進(jìn)程的互斥： 具體的過程我們可以簡單的描述如下： PA: P(sem) <S>; V(sem) PB: P(sem) <S>; V(sem) (2) 用P V原語實(shí)現(xiàn)進(jìn)程同步 進(jìn)程同步問題的解決同樣可以采用這種操作來解決，我們假設(shè)兩個進(jìn)程需要同步進(jìn)行，一個進(jìn)程是計算進(jìn)程，另一個進(jìn)程是打印進(jìn)程，那么這個時候兩個進(jìn)程的定義可以表示為： PC（表示計算進(jìn)程） A: local buf repeat buf=buf until buf=空 計算 得到計算結(jié)果 buf=計算結(jié)果 goto A PP:（表示打印進(jìn)程） B: local pri repeat pri=buf until pri!=空 打印buf中的數(shù)據(jù) 清除buf中的數(shù)據(jù) goto B 相應(yīng)用P,V原語的實(shí)現(xiàn)過程為： PA: deposit(data) Begin local x P(bufempty) 按FIFO方式選擇一個空緩沖區(qū)buf(x) buf(x)=data buf(x)置滿標(biāo)記 V(buffull) end PB:remove(data) Begin local x P(buffull) 按FIFO方式選擇一個裝滿 數(shù)據(jù)的緩沖區(qū)buf(x) data=buf(x) buf(x)置空標(biāo)記 V(bufempty) end （3）用P V原語實(shí)現(xiàn)進(jìn)程通信 我們以郵箱通信為例說明問題： 郵箱通信滿足的條件是： <1>;發(fā)送進(jìn)程發(fā)送消息的時候，郵箱中至少要有一個空格能存放該消息。 <2>;接收進(jìn)程接收消息時，郵箱中至少要有一個消息存在。 發(fā)送進(jìn)程和接收進(jìn)程我們可以進(jìn)行如下的描述： Deposit(m)為發(fā)送進(jìn)程，接收進(jìn)程是remove(m). Fromnum為發(fā)送進(jìn)程的私用信號量，信箱空格數(shù)n。mesnum為接收進(jìn)程的私用信號量，初值為0. Deposit(m): Begin local x P(fromnum) 選擇空格x 將消息m放入空格x中 置格x的標(biāo)志為滿 V(mesnum) end Remove(m) Begin local x P(mesnum) 選擇滿格x 把滿格x中的消息取出放m中 置格x標(biāo)志為空 V(fromnum) end 筆者僅從最基本的進(jìn)程問題上論述P,V原語的應(yīng)用。當(dāng)然關(guān)于這一部分的應(yīng)用是十分廣泛的。比如操作系統(tǒng)文化史上非常經(jīng)典的哲學(xué)家就餐問題，生產(chǎn)-消費(fèi)問題，讀者-寫者問題，理發(fā)師問題等等。大家不妨嘗試一下用信號量的方法進(jìn)行實(shí)現(xiàn)。 |
|
|
