沈云琴 成浩暉

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

關(guān)鍵詞：生產(chǎn)者;消費者;同步;互斥;信號量

一、引言

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

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

二、信號量機制介紹

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

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

1、整型信號量

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

wait（S）{

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

S--;

}

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

S++;

}

2、記錄型信號量

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

3、AND型信號量

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

4、信號量集

記錄型信號量只能做+1或-1運算，當一次需要多個資源時，可能要進行多次操作。有時對資源還有一個低限要求，當?shù)陀谧畹拖奘蔷筒辉S再分配了。因此在每次分配之前，要檢查以上兩個因素?；诖耍梢詫ND信號量機制加以擴充，形成一般化的信號量集機制。即針對進程所申請的所有資源以及每類資源不同的需求量，在一次wait（s）或signal（s）操作中完成它們的申請或釋放。

三、信號量的應用

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

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

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

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

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

2、問題引申

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

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

2）關(guān)于Mutex互斥信號量的設(shè)置是否必要的問題。

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

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

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

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

3）信號量設(shè)置。為實現(xiàn)Reader與Writer進程間在讀或?qū)憰r的互斥而設(shè)置了一個互斥信號量mutex。另外，再設(shè)置一個整型變量Readcount表示正在讀的進程數(shù)目。又因為Readcount是一個可被多個Reader進程訪問的臨界資源，因此，應該為它設(shè)置一個互斥信號量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、公平算法（按照到達順序進行操作）

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

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

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

5、寫者優(yōu)先算法

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

該算法增設(shè)了信號量，用于實現(xiàn)寫者插隊的目的。當?shù)谝粋€寫者到達時，申請占用該信號量，占用成功后就一直占用，后續(xù)到達的讀者進程會因申請不到該信號量而阻塞，而后續(xù)寫者到達時，由于不需要申請該信號量，因此就排在這個寫者后面，從而達到插隊目的。直到所有寫者已經(jīng)寫完，最后一個寫者釋放了該信號量，讀者才能繼續(xù)執(zhí)行讀操作。當新的寫者到達時，繼續(xù)占用該信號量，阻止后續(xù)的讀者進行讀操作，重復進行此過程。此算法真正實現(xiàn)了寫者優(yōu)先，新寫者也可以優(yōu)先于先到的等待讀者占用數(shù)據(jù)區(qū)進行操作。

四、結(jié)語

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

參考文獻：

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

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

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

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

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

作者簡介：

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

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