操作系統中信號量機制的應用分析

沈云琴 成浩暉

摘要：本文深入分析了進程同步中的經典問題“生產者-消費者問題”、“讀者-寫者問題”的同步和互斥關系，并對各種算法進行了分析和對比，進而讓讀者深入理解信號量機制的應用和?PV?原語的使用。

關鍵詞：生產者;消費者;同步;互斥;信號量

一、引言

《操作系統原理》課程是計算機科學與技術、大數據、物聯網等計算機相關專業的基礎課程、核心課程，也是計算機408研究生考試中計算機類專業的一門必考專業課，一直受到國內外計算機專業教師的高度重視。課程內容涉及到操作系統的原理與技術、具體的設計與實現，主要內容包括處理機管理、進程管理、存儲管理、設備管理和文件系統管理等核心功能的設計與實現。通過學習，使學生建立起對操作系統的整體及各個功能的認識，讓學生了解和掌握操作系統是如何管理和控制計算機系統中的所有軟硬件資源，以及操作系統是如何為用戶提供一個方便靈活、安全可靠的工作環境的。從而進一步提升學生的軟件開發能力乃至系統軟件開發能力。

目前的操作系統都建立在進程這一基本概念之上。在傳統的操作系統中，為了提高資源利用率和系統吞吐量，通常采用多道程序技術將多個程序同時裝入內存，使它們并發執行，此時，進程作為資源分配和調度的基本單位，為保證多個進程能有條不紊地運行，必須引入進程同步機制，所以進程管理是該課程中及其重要的內容。其中，進程的同步和互斥也是課程中的難點。進程同步中的“信號量機制”是解決進程同步互斥問題中的一種有效方法。本文將圍繞經典進程同步問題對這一機制進行論述，說明這個機制的應用和引申。

二、信號量機制介紹

信號燈是人類社會中應用于交通管理等領域的一種設備，人們可以利用信號燈的狀態（顏色）來規范相關活動。如十字路口的交通管理等。操作系統中的信號量機制類似于信號燈，起著規范進程運行的作用。

1965年，荷蘭學者Dijkstra提出了信號量（Semaphores）機制，其是一種卓有成效的進程同步工具。在長期且廣泛的應用中，信號量機制得到了很大的發展，它從整型信號量經記錄型信號量、AND型信號量，進而發展為“信號量集”機制?，F在，信號量機制已被廣泛應用于單處理機和多處理機系統以及計算機網絡中。

1、整型信號量

最初由Dijkstra把整型信號量定義為一個表示自愿數目的整型量S，它與一般整型量不同，除初始化外，僅能通過兩個標準的原子操作來訪問，即wait（s）?和signal（s）操作，這兩個操作也被成為P操作和V操作，可描述為：

wait（S）{

while?S<=0;?/*do?no-op*/

S--;

}

signal（S）{?/*V（S）?*/

S++;

}

2、記錄型信號量

記錄型信號量是不存在“忙等”現象的進程同步機制。除需要一個用于代表資源數目的整型變量value外，再增加一個進程鏈表L，用于鏈接所有等待該資源的進程。

3、AND型信號量

AND型信號量機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程，其它所有可能為之分配的資源，也不分配給它。

4、信號量集

記錄型信號量只能做+1或-1運算，當一次需要多個資源時，可能要進行多次操作。有時對資源還有一個低限要求，當低于最低限是就不許再分配了。因此在每次分配之前，要檢查以上兩個因素?；诖?，可以對AND信號量機制加以擴充，形成一般化的信號量集機制。即針對進程所申請的所有資源以及每類資源不同的需求量，在一次wait（s）或signal（s）操作中完成它們的申請或釋放。

三、信號量的應用

在多道程序環境下，進程同步問題十分重要，也相當有趣，因此吸引了不少學者對它進行研究，由此產生了一系列經典的進程同步問題，其中較有代表性的是“生產者-消費者問題”、“讀者-寫者問題”、“哲學家進餐問題”。下面就“生產者-消費者問題”、“讀者-寫者問題”進行討論。

1、利用記錄型信號量解決“生產者-消費者問題”

1）問題描述：一組生產者進程和一組消費者進程共享一個初始為空、大小為n的緩沖區，只有緩沖區沒滿時，生產者才能把產品放入緩沖區，否則必須等待;只有緩沖區不空時，消費者才能從中取出消息，否則必須等待。由于緩沖區是臨界資源，它只允許一個生產者放入產品，或一個消費者從中取出產品。

2）關系分析：生產者和消費者對緩沖區互斥訪問是互斥關系，同時生產者和消費者又是一個相互協作的關系，只有生產者生產之后，消費者才能消費，它們也是同步關系。這兩個進程存在著互斥關系和同步關系。那么需要解決的是互斥和同步PV操作的位置。

3）信號量設置：信號量mutex作為互斥信號量，用于控制互斥訪問緩沖區，互斥信號量初值為1;信號量full用于記錄當前緩沖池中的滿緩沖區數，初值為0，信號量empty用于當前記錄緩沖池中的空緩沖區數，初值為n。

2、問題引申

1）該類問題要注意對緩沖區大小為n的處理，P（full）?、P（empty）與P（mutex）的順序不可顛倒。

設想生產者進程已將緩沖區放滿，消費者進程并沒有取產品，即empty=0，當下次仍然是生產者進程運行時，它先執行P（mutex）封鎖信號量，在執行P（empty）時將被阻塞，希望消費者取出產品將其喚醒。輪到消費者進程運行時，它先執行P（mutex），然而由于生產者進程已經封鎖mutex信號量，消費者進程也會被阻塞，這樣一來生產者、消費者進程都將阻塞，都指望對方喚醒自己，因此陷入了無休止的等待。同理，若消費者進程已將緩沖區取空，即full=0，下次若還是消費者先運行，也會出現類似的死鎖。不過生產者釋放信號量時，mutex、full先釋放哪一個無所謂，消費者先先釋放mutex或empty都可以。

2）關于Mutex互斥信號量的設置是否必要的問題。

在生產者和消費者都是唯一的問題中，生產者和消費者是同步關系，生產者和消費者之間使用empty和full兩個資源信號量進行同步，一定滿足“放完才能取”的條件，因此此時互斥信號量mutex可以去掉。但在多生產者和消費者的情況下，需要保證多個生產者和多個消費者互斥地訪問緩沖池，否則會導致出錯。例如，兩個生產者執行了P（empty）操作，此時第一個生產者執行buffer（in）=nextp，這時第二個生產者也執行這條語句，由于第一個生產者沒有來得及執行in=（in+1）?%?n，即沒有使指針后移，導致第二個生產者的數據覆蓋了第一個生產者的數據，而不是放在了第一個數據的下一個緩沖區，接下來兩個進程分別執行一次后移指針操作，這樣就導致了有一個空緩沖區（本來應當放置第二個數據的緩沖區）被當作已有數據緩沖區對待，從而出錯。因此，在多生產者或多消費者的情況下，必須設置mutex互斥信號量，以保證對緩沖池的互斥訪問。

3、利用記錄型信號量解決“讀者-寫者問題”

1）問題描述：有讀者和寫者兩組并發進程，共享一個文件，兩個或以上的讀進程同時訪問共享數據時不會產生副作用，但若某個寫進程和其他進程（讀進程或寫進程）同時訪問共享數據時則可能導致數據不一致的錯誤。因此要求：允許多個讀者可以同時對文件執行讀操作;只允許一個寫者往文件中寫信息;任一寫者在完成寫操作之前不允許不允許其他讀者或寫者工作;寫者執行寫操作前，應讓已有的讀者和寫者全部退出。

2）關系分析：讀者和寫者、寫者和寫者是互斥的，讀者和讀者不互斥。兩個進程，即讀者和寫者。寫者較簡單，它和任何進程互斥，用互斥信號量的P、V操作即可解決。讀者的問題比較復雜，它必須在實現與寫者互斥的同時，實現與其他讀者的同步，因此簡單的一對P操作、V操作無法解決。

3）信號量設置。為實現Reader與Writer進程間在讀或寫時的互斥而設置了一個互斥信號量mutex。另外，再設置一個整型變量Readcount表示正在讀的進程數目。又因為Readcount是一個可被多個Reader進程訪問的臨界資源，因此，應該為它設置一個互斥信號量rmutex。算法如下：

semaphore?rmutex=1;

semaphore?mutex=1;

int?readcount=0;

void?reader（?;）?{

do?{

wait（rmutex）;

if?（readcount==0）?wait（mutex）;

readcount++;

signal（rmutex）;

…?…

perform?read?operation;

…?…

wait（rmutex）;

readcount--;

if?（readcount==0）?signal（mutex）;

signal（rmutex）;//

}while（TRUE）;

}

void?writer（?）?{

do?{

wait（mutex）;

perform?write?operation;

signal（mutex）;

}?while（TRUE）;

}

4、公平算法（按照到達順序進行操作）

在上面的算法中，讀進程是優先的，即當存在讀進程時，寫操作將被延遲，且只要有一個讀進程活躍，隨后而來的讀進程都將被允許訪問文件。這樣的方式會導致寫進程可能長時間等待，存在寫進程餓死的情況?？稍黾右粋€信號量在上面程序的reader（?）和writer（?）函數中各增加一對PV操作，就可解決寫進程優先。

進程的執行順序完全按照到達順序，即一個讀者試圖進行讀操作時，如果有寫者正等待進行寫操作或正在進行寫操作，后續讀者要等待先到達的寫者完成操作后才開始讀操作。增設一個信號量，初值為1，用于表示是否存在正在寫或者等待的寫者，若存在，則禁止新讀者進入。

由于存在互斥信號量，因此當第一個寫者到來時，就會占用該信號量，從而阻止了后續其他讀者的進入請求，只有當之前申請寫操作的寫者進入數據區完成寫操作后，才會釋放互斥信號量，后續讀者才能進入。在這個算法中，將讀寫兩種進程放在平等的地位，完全按照進程到達的順序來執行。設置互斥信號量的目的在于控制進程按照順序來進行操作，避免讀進程的優先）。

5、寫者優先算法

即當寫者和讀者同時等待時，后續寫者到達時可以插隊到等待的讀者之前，只要等待隊列中有寫者，不管何時到達，都優先于讀者被喚醒，則需要增設額外的信號量進行控制。增設信號量，用于控制寫者到達時可以優先于讀者進入臨界區，當有寫者到達時，只需要等待前面的寫者寫完就可以直接進入臨界區，而不論讀者是在該寫者之前還是之后到達。另外，需要增設一個整數用于統計寫者的數量，再設置信號量，用于控制寫者互斥訪問該整數。

該算法增設了信號量，用于實現寫者插隊的目的。當第一個寫者到達時，申請占用該信號量，占用成功后就一直占用，后續到達的讀者進程會因申請不到該信號量而阻塞，而后續寫者到達時，由于不需要申請該信號量，因此就排在這個寫者后面，從而達到插隊目的。直到所有寫者已經寫完，最后一個寫者釋放了該信號量，讀者才能繼續執行讀操作。當新的寫者到達時，繼續占用該信號量，阻止后續的讀者進行讀操作，重復進行此過程。此算法真正實現了寫者優先，新寫者也可以優先于先到的等待讀者占用數據區進行操作。

四、結語

只要有多個同類進程（同類進程是指使用同一個記錄型信號量的進程，比如若干消費者進程都在使用empty信號量），就一定要使用互斥信號量;若同類進程只有一個，則記錄型信號量即可完成進程同步。換句話說，互斥信號量是給同類進程準備的?！白x者-寫者問題”中又引入了讀者優先、寫者優先、公平算法進一步討論，使學生更加深刻地理解進程之間同步互斥的關系，信號量的應用以及PV原語的使用。作者通過多年的操作系統原理授課經驗得出，這種講授方法言簡意賅，把抽象的內容融入案例中，循序漸進，能調動學生的學習積極性、主動性及熱情，實踐表明此方法教學效果良好，深得學生好評。

參考文獻：

[1]湯小丹，湯子瀛等.計算機操作系統（第4版）[M].西安：西安電子科技大學出版社，2014：57-72.

[2][美]威廉·斯托林斯（William?Stallings）主編.操作系統精髓與設計原理（第8版）[M].人民郵電出版社.2019：181-192.

[3]]李姍姍，董威，羅宇，文艷軍，廖湘科?.國產操作系統研發對系統能力培養的需求與實踐[J].2018，11（40）：32-36.

[4]蔡學森，于繁華，戴金波，顧晗昕，周洋洋.案例法在操作系統原理教學中的應用[J].長春師范大學學報，2015（8）：123-125.

[5]徐為民.研究生課程“線性系統理論”教學內容的組織方式探索[J].教育教學論壇，2017（36）：233-234.

作者簡介：

沈云琴（1982-），女，云南昭通人，碩士，講師，研究方向：云計算技術及數據分析。

成浩暉（2002-），男，陜西渭南人，本科，研究方向：計算機軟件。