對操作系統中信號量問題的一點認識

李　儉　張明輝　任立權

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

關鍵詞:信號量;同步;互斥

中圖分類號:G642 文獻標識碼:B

在多道程序環境下,操作系統如何實現進程之間的同步和互斥顯得極為重要。荷蘭學者Dijkstra給出了一種解決并發進程間互斥與同步關系的通用方法,即信號量機制。他定義了一種名為“信號量”的變量,并且規定在這種變量上只能做所謂的P操作和V操作。現在,信號量機制已經被廣泛地應用于單處理機和多處理機系統以及計算機網絡中,這也是學習操作系統的重點和難點之一。本文就利用信號量實現進程間的同步和互斥問題進行了分析。

1引言

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

信號量的定義如下:

type semaphore=record

/*定義信號量*/

begin

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

L:list of process;

/*與該信號量相關聯的隊列*/

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,則阻塞執行該P操作的進程*/

end

當執行P(S)操作時,信號量S的值減1,如果S≥0,表示可以繼續執行;如果S<0,表示該進程只能進入S信號量的阻塞隊列中等待,由調度程序重新調度其他進程執行。需要注意的是,使該信號量S的值增加的進程會將該阻塞進程喚醒,該進程一旦獲得處理機,就可以直接進入臨界區,無需再執行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

當執行V(S)操作時,信號量S的值加1,如果S≤0,則喚醒S信號量阻塞隊列隊首的阻塞進程,將其狀態從阻塞狀態轉變為就緒狀態,執行V操作的進程繼續執行;如果S>0,則說明沒有進程在該信號量的阻塞隊列當中,因此,無需喚醒其他進程,該進程繼續執行。

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

2利用信號量實現進程互斥

利用信號量實現進程互斥的進程可描述如下:

Var s:semaphore:=1;

/*設置信號量s的初值為1*/

begin

parbegin/*并發開始*/

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

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

用信號量實現進程互斥的特點:

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

(2)P、V操作位于臨界區前后,在一個進程里成對出現。

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

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

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

(6) 當信號量s>0時,s表示還允許進入臨界區的進程數,即剩下的臨界資源個數)。

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

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

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

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

本例題的解決方法如下:

Vars1,s2:semaphore:=100,1;

/*設置兩個信號量,分別對應座位和表這兩個臨界 資源*/

parbegin

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

begin

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

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

登記;

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

讀書;

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

注銷;

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

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

end

parend

3利用信號量實現進程同步

可以通過一個例子來說明進程同步的實現。

例如,有一個緩沖區,某一個時刻只能存一個數據,計算進程P1將計算出的結果放入緩沖區,輸出進程P2往外取數據輸出,進程P1一旦放入數據后,必須等進程P2取出數據以后它才能繼續往里放,否則會導致前一次放入的數據丟失;進程P2取出數據后,必須等進程P1放入下一個數據后它才能夠繼續取,否則會導致兩次取出的是同一個數據。可見,這是一個典型的進程同步關系,進程P1和P2在協調著共同完成一個任務。

解決這個同步問題的進程描述如下:

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

begin

parbegin

P1:

begin

repeat

獲得數據;

計算;

送至緩沖區;

V(s1);

P(s2);

until false;

end

P2:

begin

repeat

P(s1);

從緩沖區中取數據;

輸出;

V(s2);

until false;

end

parend

end

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

用信號量實現進程同步的特點:

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

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

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

我們通過一個實例來進一步說明。A、B兩組學生進行投球比賽,規定一個組學生投一個球后應讓另一個組學生投球,假設讓A組同學先投,試寫出A、B兩個進程。

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

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

解決這個同步問題的進程描述如下:

方法一:

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

parbegin

process A:

begin

投球;

/*A組學生先投,沒有條件限制*/

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

P(s1);

/*等待B組學生投球之后再投球*/

end

process B:

begin

P(s2);

/*等待A組學生投球之后再投球*/

投球;

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

end

parend

方法二:

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

parbegin

process A:

begin

P(s1);

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

投球;

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

end

process B:

begin

P(s2);

投球;

V(s1);

end

parend

4結束語

本文對利用信號量實現進程間的同步和互斥問題進行了探討,總結出了作者在教學過程中的一點體會,希望對操作系統的教學有所幫助。

參考文獻:

[1] 湯子瀛,哲鳳屏,湯小丹. 計算機操作系統[M]. 2版. 西安:西安電子科技大學出版社.2001.

[2] 劉乃琦,吳躍. 計算機操作系統[M]. 北京:電子工業出版社.1997.

[3] 張堯學,史美林,張高. 計算機操作系統教程[M]. 3版. 北京:清華大學出版社.2006.