對(duì)操作系統(tǒng)中信號(hào)量問題的一點(diǎn)認(rèn)識(shí)

李　儉　張明輝　任立權(quán)

摘要:本文針對(duì)目前操作系統(tǒng)中利用信號(hào)量解決進(jìn)程間的同步和互斥的問題,系統(tǒng)地總結(jié)了解決問題的一般性規(guī)律。首先介紹了信號(hào)量的定義及在信號(hào)量上可以執(zhí)行的兩個(gè)操作,并分別詳細(xì)說明了如何利用信號(hào)量實(shí)現(xiàn)進(jìn)程間的同步和互斥,最后結(jié)合實(shí)例說明了這兩種方法在實(shí)際問題中的具體運(yùn)用。

關(guān)鍵詞:信號(hào)量;同步;互斥

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

在多道程序環(huán)境下,操作系統(tǒng)如何實(shí)現(xiàn)進(jìn)程之間的同步和互斥顯得極為重要。荷蘭學(xué)者Dijkstra給出了一種解決并發(fā)進(jìn)程間互斥與同步關(guān)系的通用方法,即信號(hào)量機(jī)制。他定義了一種名為“信號(hào)量”的變量,并且規(guī)定在這種變量上只能做所謂的P操作和V操作?，F(xiàn)在,信號(hào)量機(jī)制已經(jīng)被廣泛地應(yīng)用于單處理機(jī)和多處理機(jī)系統(tǒng)以及計(jì)算機(jī)網(wǎng)絡(luò)中,這也是學(xué)習(xí)操作系統(tǒng)的重點(diǎn)和難點(diǎn)之一。本文就利用信號(hào)量實(shí)現(xiàn)進(jìn)程間的同步和互斥問題進(jìn)行了分析。

1引言

信號(hào)量是一個(gè)具有非負(fù)初值的整型變量,并且有一個(gè)隊(duì)列與它關(guān)聯(lián)。因此,定義一個(gè)信號(hào)量時(shí),要給出它的初值,并給出與它相關(guān)的隊(duì)列指針。信號(hào)量除初始化外,僅能通過P、V兩個(gè)操作來訪問,這兩個(gè)操作都由原語(yǔ)組成,即在執(zhí)行過程中不可被中斷,也就是說,當(dāng)一個(gè)進(jìn)程在修改某個(gè)信號(hào)量時(shí),沒有其他進(jìn)程可同時(shí)對(duì)該信號(hào)量進(jìn)行修改。

信號(hào)量的定義如下:

type semaphore=record

/*定義信號(hào)量*/

begin

value:integer;/*整型變量*/

L:list of process;

/*與該信號(hào)量相關(guān)聯(lián)的隊(duì)列*/

end

P(S)操作可描述為:

procedure P(S)

var S: semaphore;

begin

S.value:=S.value-1;

/*信號(hào)量的值減1*/

if S.value<0 then block(S,L)

/*若信號(hào)量的值小于0,則阻塞執(zhí)行該P(yáng)操作的進(jìn)程*/

end

當(dāng)執(zhí)行P(S)操作時(shí),信號(hào)量S的值減1,如果S≥0,表示可以繼續(xù)執(zhí)行;如果S<0,表示該進(jìn)程只能進(jìn)入S信號(hào)量的阻塞隊(duì)列中等待,由調(diào)度程序重新調(diào)度其他進(jìn)程執(zhí)行。需要注意的是,使該信號(hào)量S的值增加的進(jìn)程會(huì)將該阻塞進(jìn)程喚醒,該進(jìn)程一旦獲得處理機(jī),就可以直接進(jìn)入臨界區(qū),無(wú)需再執(zhí)行P(S)操作。

V(S)操作可描述為:

procedure V(S)

var S: semaphore;

begin

S.value:=S.value+1;

if S.value≤0

then wakeup(S,L);

end

當(dāng)執(zhí)行V(S)操作時(shí),信號(hào)量S的值加1,如果S≤0,則喚醒S信號(hào)量阻塞隊(duì)列隊(duì)首的阻塞進(jìn)程,將其狀態(tài)從阻塞狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài),執(zhí)行V操作的進(jìn)程繼續(xù)執(zhí)行;如果S>0,則說明沒有進(jìn)程在該信號(hào)量的阻塞隊(duì)列當(dāng)中,因此,無(wú)需喚醒其他進(jìn)程,該進(jìn)程繼續(xù)執(zhí)行。

需要說明的是,信號(hào)量的初值一定是一個(gè)非負(fù)的整數(shù),但是在運(yùn)行過程中,信號(hào)量的值可正可負(fù)。

2利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥

利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的進(jìn)程可描述如下:

Var s:semaphore:=1;

/*設(shè)置信號(hào)量s的初值為1*/

begin

parbegin/*并發(fā)開始*/

process1:

begin

repeat

P(s);

critical section

V(s);

remainder section

until false;

end

process2:

begin

repeat

P(s);

critical section

V(s);

remainder section

until false;

end

parend

end

以上描述的是并發(fā)執(zhí)行的兩個(gè)進(jìn)程process1和process2,這兩個(gè)進(jìn)程的臨界區(qū)(critical section)對(duì)應(yīng)的是一個(gè)臨界資源,為了保證這兩個(gè)進(jìn)程能夠互斥地使用臨界資源,在每個(gè)進(jìn)程的臨界區(qū)前后分別加上對(duì)同一個(gè)信號(hào)量的P操作和V操作,就好象分別是關(guān)鎖和開鎖操作一樣。我們將該信號(hào)量的初值設(shè)為1,無(wú)論哪一個(gè)進(jìn)程先獲得處理機(jī),在進(jìn)入臨界區(qū)之前都要進(jìn)行P操作,執(zhí)行P操作后,信號(hào)量s的值為0,該進(jìn)程可以繼續(xù)執(zhí)行;若該進(jìn)程在臨界區(qū)內(nèi)失去處理機(jī),而由另一個(gè)進(jìn)程獲得處理機(jī)執(zhí)行時(shí),執(zhí)行的進(jìn)程在進(jìn)入臨界區(qū)之前執(zhí)行P操作時(shí),信號(hào)量s的值就為-1,此時(shí)該進(jìn)程就得阻塞,進(jìn)入到信號(hào)量s的等待隊(duì)列當(dāng)中等待;當(dāng)在臨界區(qū)內(nèi)的進(jìn)程再次獲得處理機(jī)繼續(xù)執(zhí)行后,退出臨界區(qū)時(shí),執(zhí)行V操作,信號(hào)量s的值為0,此時(shí)它要去喚醒阻塞進(jìn)程,然后繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。

用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的特點(diǎn):

(1)要找對(duì)臨界區(qū),范圍小了會(huì)出錯(cuò),范圍大了會(huì)影響進(jìn)程運(yùn)行。

(2)P、V操作位于臨界區(qū)前后,在一個(gè)進(jìn)程里成對(duì)出現(xiàn)。

(3)2個(gè)進(jìn)程對(duì)1個(gè)臨界資源互斥使用時(shí)信號(hào)量初值為1,取值范圍為-1,0,1。

(4) 當(dāng)n個(gè)進(jìn)程要互斥使用m個(gè)同類臨界資源時(shí)(n>m),用信號(hào)量實(shí)現(xiàn)互斥時(shí),信號(hào)量的初值應(yīng)為m,即該類可用資源的數(shù)目。信號(hào)量的取值范圍為-(n-m)~m。

(5) 當(dāng)信號(hào)量s<0時(shí),|s|為等待該資源的進(jìn)程的個(gè)數(shù);即因該資源而阻塞的阻塞隊(duì)列中進(jìn)程個(gè)數(shù)。

(6) 當(dāng)信號(hào)量s>0時(shí),s表示還允許進(jìn)入臨界區(qū)的進(jìn)程數(shù),即剩下的臨界資源個(gè)數(shù))。

(7) 執(zhí)行一次P(s)操作,表示請(qǐng)求一個(gè)臨界資源,s-1后,當(dāng)s<0時(shí),表示可用資源沒有了,進(jìn)程阻塞。

(8) 執(zhí)行一次V(s)操作,表示釋放一個(gè)臨界資源,s+1后,若s<=0,表示還有進(jìn)程在阻塞隊(duì)列中,要去喚醒一個(gè)阻塞進(jìn)程。

我們通過一個(gè)實(shí)例來進(jìn)一步說明。有一個(gè)閱覽室共100個(gè)座位,用一張表來管理它,每個(gè)表目記錄座位號(hào)以及讀者姓名。讀者進(jìn)入時(shí)要先在表上登記,退出時(shí)要注銷登記?？梢杂眯盘?hào)量及其P、V操作來描述各個(gè)讀者“進(jìn)入”和“注銷”工作之間的關(guān)系。

分析:由于一個(gè)座位在某一時(shí)刻只能分配給一個(gè)讀者,所以對(duì)于多個(gè)讀者來說,一個(gè)座位就是一個(gè)臨界資源,100個(gè)座位即相當(dāng)于此類臨界資源有100個(gè),可以設(shè)置一個(gè)信號(hào)量s1來管理座位,且其初始值為100。每個(gè)讀者來后,首先要看看是否有座位,即對(duì)s1執(zhí)行一次P操作,只要有座位,P操作后s1值大于等于0,此時(shí)就可以拿表來登記了。用一張表來管理這100個(gè)座位,每名讀者進(jìn)入或退出時(shí)都要在表上登記,并且每次只能有一個(gè)讀者使用這張表,所以這一張表也相當(dāng)于是臨界資源,可以設(shè)置一個(gè)信號(hào)量s2來管理表格。所以一共要設(shè)置兩個(gè)信號(hào)量分別用來管理這兩類臨界資源。

本例題的解決方法如下:

Vars1,s2:semaphore:=100,1;

/*設(shè)置兩個(gè)信號(hào)量,分別對(duì)應(yīng)座位和表這兩個(gè)臨界 資源*/

parbegin

processreader(i)(i=1,2,……):

begin

P(s1);/*申請(qǐng)一個(gè)座位*/

P(s2);/*拿表進(jìn)行登記*/

登記;

V(s2);/*登記后放回表*/

讀書;

P(s2);/*拿表進(jìn)行注銷*/

注銷;

V(s2);/*注銷后放回表*/

V(s1); /*釋放一個(gè)座位*/

end

parend

3利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步

可以通過一個(gè)例子來說明進(jìn)程同步的實(shí)現(xiàn)。

例如,有一個(gè)緩沖區(qū),某一個(gè)時(shí)刻只能存一個(gè)數(shù)據(jù),計(jì)算進(jìn)程P1將計(jì)算出的結(jié)果放入緩沖區(qū),輸出進(jìn)程P2往外取數(shù)據(jù)輸出,進(jìn)程P1一旦放入數(shù)據(jù)后,必須等進(jìn)程P2取出數(shù)據(jù)以后它才能繼續(xù)往里放,否則會(huì)導(dǎo)致前一次放入的數(shù)據(jù)丟失;進(jìn)程P2取出數(shù)據(jù)后,必須等進(jìn)程P1放入下一個(gè)數(shù)據(jù)后它才能夠繼續(xù)取,否則會(huì)導(dǎo)致兩次取出的是同一個(gè)數(shù)據(jù)?？梢?這是一個(gè)典型的進(jìn)程同步關(guān)系,進(jìn)程P1和P2在協(xié)調(diào)著共同完成一個(gè)任務(wù)。

解決這個(gè)同步問題的進(jìn)程描述如下:

Var s1,s2:semaphore:=0,0;

begin

parbegin

P1:

begin

repeat

獲得數(shù)據(jù);

計(jì)算;

送至緩沖區(qū);

V(s1);

P(s2);

until false;

end

P2:

begin

repeat

P(s1);

從緩沖區(qū)中取數(shù)據(jù);

輸出;

V(s2);

until false;

end

parend

end

以上實(shí)現(xiàn)的是兩個(gè)并發(fā)進(jìn)程P1和P2的同步關(guān)系。這里設(shè)了兩個(gè)信號(hào)量s1和s2,分別是兩個(gè)進(jìn)程用來進(jìn)行相應(yīng)的消息傳遞以便來實(shí)現(xiàn)同步的,一般實(shí)現(xiàn)同步的信號(hào)量的初值可以設(shè)為0。因?yàn)楸仨毾扔?jì)算,后輸出,所以P1進(jìn)程的執(zhí)行要先于P2。如果P2先獲得處理機(jī),則P2要先執(zhí)行一個(gè)P(s1)操作,由于s1的初值為0,所以執(zhí)行P(s1)后,P2會(huì)阻塞;P1獲得處理機(jī)后可以一直執(zhí)行,當(dāng)放完數(shù)據(jù)以后,它要執(zhí)行V(s1),即看一下是否有進(jìn)程在信號(hào)量s1的隊(duì)列中等待,若有,它要去喚醒;然后,為了防止P1繼續(xù)往緩沖區(qū)中放數(shù)據(jù),在執(zhí)行V(s1)操作之后,馬上又執(zhí)行P(s2),隨即阻塞,直等到P2取完數(shù)據(jù)輸出后執(zhí)行V(s2)將其喚醒。

用信號(hào)量實(shí)現(xiàn)進(jìn)程同步的特點(diǎn):

(1) 配對(duì)的P、V操作分別在不同的進(jìn)程里。有的時(shí)候P操作和V操作的個(gè)數(shù)并不相等。

(2) 初值一般為0,需要設(shè)一個(gè)以上的信號(hào)量(例如2個(gè)進(jìn)程同步,需要設(shè)2個(gè)信號(hào)量,分別用來傳遞信息)。

(3) 在實(shí)現(xiàn)進(jìn)程同步時(shí),需要分析哪個(gè)進(jìn)程不可以先執(zhí)行,在不允許直接進(jìn)行的操作前面加上P操作來進(jìn)行條件限制。并在使其操作成為可能的其他進(jìn)程的操作后面加上對(duì)同一個(gè)信號(hào)量的V操作。

我們通過一個(gè)實(shí)例來進(jìn)一步說明。A、B兩組學(xué)生進(jìn)行投球比賽,規(guī)定一個(gè)組學(xué)生投一個(gè)球后應(yīng)讓另一個(gè)組學(xué)生投球,假設(shè)讓A組同學(xué)先投,試寫出A、B兩個(gè)進(jìn)程。

由題意分析可知,一個(gè)組學(xué)生投一個(gè)球的前提條件是另一個(gè)組的學(xué)生投球之后,即有條件制約,同樣,另一個(gè)

組學(xué)生投球也受到該組學(xué)生投球的條件制約,由此可知該問題是一個(gè)進(jìn)程同步的問題。所以,要在有條件制約的投球動(dòng)作前加上一個(gè)P操作,即條件不滿足時(shí)就阻塞;在投球動(dòng)作結(jié)束后,要加上一個(gè)V操作,即自己的投球動(dòng)作完成之后,使另一組學(xué)生的投球動(dòng)作成為可能。

解決這個(gè)同步問題的進(jìn)程描述如下:

方法一:

Var s1,s2:semaphore:=0,0;

parbegin

process A:

begin

投球;

/*A組學(xué)生先投,沒有條件限制*/

V(s2);/*使B組學(xué)生可以投球*/

P(s1);

/*等待B組學(xué)生投球之后再投球*/

end

process B:

begin

P(s2);

/*等待A組學(xué)生投球之后再投球*/

投球;

V(s1); /*使A組學(xué)生可以投球*/

end

parend

方法二:

Var s1,s2:semaphore:=1,0;

parbegin

process A:

begin

P(s1);

/*A組學(xué)生先投,s1初始值為1,不阻塞*/

投球;

V(s2); /*使B組學(xué)生可以投球*/

end

process B:

begin

P(s2);

投球;

V(s1);

end

parend

4結(jié)束語(yǔ)

本文對(duì)利用信號(hào)量實(shí)現(xiàn)進(jìn)程間的同步和互斥問題進(jìn)行了探討,總結(jié)出了作者在教學(xué)過程中的一點(diǎn)體會(huì),希望對(duì)操作系統(tǒng)的教學(xué)有所幫助。

參考文獻(xiàn):

[1] 湯子瀛,哲鳳屏,湯小丹. 計(jì)算機(jī)操作系統(tǒng)[M]. 2版. 西安:西安電子科技大學(xué)出版社.2001.

[2] 劉乃琦,吳躍. 計(jì)算機(jī)操作系統(tǒng)[M]. 北京:電子工業(yè)出版社.1997.

[3] 張堯?qū)W,史美林,張高. 計(jì)算機(jī)操作系統(tǒng)教程[M]. 3版. 北京:清華大學(xué)出版社.2006.