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

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

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

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

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

1引言

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

信號量的定義如下:

type semaphore=record

/*定義信號量*/

begin

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

L:list of process;

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

end

P(S)操作可描述為:

procedure P(S)

var S: semaphore;

begin

S.value:=S.value-1;

/*信號量的值減1*/

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

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

end

當(dāng)執(zhí)行P(S)操作時,信號量S的值減1,如果S≥0,表示可以繼續(xù)執(zhí)行;如果S<0,表示該進(jìn)程只能進(jìn)入S信號量的阻塞隊列中等待,由調(diào)度程序重新調(diào)度其他進(jìn)程執(zhí)行。需要注意的是,使該信號量S的值增加的進(jìn)程會將該阻塞進(jìn)程喚醒,該進(jìn)程一旦獲得處理機(jī),就可以直接進(jìn)入臨界區(qū),無需再執(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)操作時,信號量S的值加1,如果S≤0,則喚醒S信號量阻塞隊列隊首的阻塞進(jìn)程,將其狀態(tài)從阻塞狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài),執(zhí)行V操作的進(jìn)程繼續(xù)執(zhí)行;如果S>0,則說明沒有進(jìn)程在該信號量的阻塞隊列當(dāng)中,因此,無需喚醒其他進(jìn)程,該進(jìn)程繼續(xù)執(zhí)行。

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

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

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

Var s:semaphore:=1;

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

用信號量實現(xiàn)進(jìn)程互斥的特點:

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

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

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

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

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

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

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

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

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

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

本例題的解決方法如下:

Vars1,s2:semaphore:=100,1;

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

parbegin

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

begin

P(s1);/*申請一個座位*/

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

登記;

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

讀書;

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

注銷;

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

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

end

parend

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

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

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

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

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

begin

parbegin

P1:

begin

repeat

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

計算;

送至緩沖區(qū);

V(s1);

P(s2);

until false;

end

P2:

begin

repeat

P(s1);

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

輸出;

V(s2);

until false;

end

parend

end

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

用信號量實現(xiàn)進(jìn)程同步的特點:

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

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

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

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

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

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

解決這個同步問題的進(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é)束語

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

參考文獻(xiàn):

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

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

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