唐伎玲，黃 葵，谷 赫

(長春大學(xué) 計算機(jī)科學(xué)技術(shù)學(xué)院，長春130022)

0 前言

多個進(jìn)程在并發(fā)執(zhí)行時，由于共享同一變量或系統(tǒng)資源，如打印機(jī)等，使這些并發(fā)執(zhí)行的進(jìn)程只能互斥地訪問，致使進(jìn)程之間形成了相互制約的關(guān)系，稱為進(jìn)程互斥。

一組進(jìn)程，為協(xié)調(diào)其推進(jìn)速度，在某些關(guān)鍵點處需要相互等待與相互喚醒，進(jìn)程之間這種相互制約的關(guān)系稱為進(jìn)程同步。

互斥與同步是操作系統(tǒng)與并發(fā)程序設(shè)計的核心問題，為此操作系統(tǒng)必須提供用于實現(xiàn)同步的機(jī)制。從本質(zhì)上講，同步工具就是能用于進(jìn)程(線程)等待或喚醒的機(jī)制，信號量機(jī)制是解決同步問題的常用工具。

如何使用信號量機(jī)制解決各種同步問題，需要準(zhǔn)確理解并牢記信號量機(jī)制的定義，還需要分析和學(xué)習(xí)典型例子，并通過一定數(shù)量的練習(xí)來提高解題的技巧。

1 經(jīng)典案列

1.1 圖書借閱系統(tǒng)

(x:某種書冊數(shù)，設(shè)當(dāng)前x=1)。

如圖1 左圖所示，在并發(fā)環(huán)境下，兩個終端程序若按圖中標(biāo)記的數(shù)字順序并發(fā)執(zhí)行，則會出現(xiàn)將一本書借給兩個讀者的錯誤。為了避免出現(xiàn)這類的錯誤，對共享變量X 的訪問必須互斥，設(shè)置信號量mutex，初值為1，控制的代碼流程如圖1 右圖所示。

圖1 圖書借問系統(tǒng)

1.2 司機(jī)－售票員問題。

在并發(fā)環(huán)境下，司機(jī)進(jìn)程和售票員進(jìn)程向前推進(jìn)過程中有兩個制約關(guān)系，如圖2 左圖所示。這是典型的同步控制，設(shè)置信號量s1 和s2，初值均為0，控制的代碼流程如圖2 右圖所示。

圖2 司機(jī)－售票員問題

1.3 生產(chǎn)者－消費(fèi)者問題

生產(chǎn)者－消費(fèi)者問題是一個著名的進(jìn)程同步問題。它描述的是:有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個具有n 個緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中;消費(fèi)者進(jìn)程可從一個緩沖區(qū)中取走產(chǎn)品去消費(fèi)。盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，即不允許消費(fèi)者進(jìn)程到一個空緩沖區(qū)去取產(chǎn)品，也不允許生產(chǎn)者進(jìn)程向一個已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。

分析問題:將產(chǎn)品和緩沖區(qū)視為組合資源，生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程的推進(jìn)過程中要不斷使用和釋放這對組合資源，因此設(shè)兩個信號量empty=n 和full=0，分別來管理緩沖區(qū)和產(chǎn)品。生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品放入緩沖區(qū)時，要先申請一個緩沖區(qū)，然后釋放一個產(chǎn)品，因此先執(zhí)行wait(empty)，后執(zhí)行signal(full)。消費(fèi)者從緩沖區(qū)取產(chǎn)品時，要先申請一個產(chǎn)品，然后釋放一個緩沖區(qū)，因此要先執(zhí)行wait(full)，后執(zhí)行signal(empty)。又因緩沖區(qū)是多個進(jìn)程共同訪問，必須互斥，因此還需設(shè)置互斥信號量mutex=1，控制的主要代碼如圖3 所示。

1.4 讀者－寫者問題

所謂“讀者－寫者問題”是指一個數(shù)據(jù)文件或記錄可被多個進(jìn)程共享，允許多個進(jìn)程同時讀一個共享對象，因為讀操作不會使數(shù)據(jù)文件混亂。但不允許一個寫進(jìn)程和其他讀進(jìn)程或其它寫進(jìn)程同時訪問共享對象。因為這種訪問將會引起文件內(nèi)容的混亂。

分析問題:這是多個進(jìn)程在共享過程中又有互斥控制的問題。因為寫進(jìn)程與寫進(jìn)程之間、寫進(jìn)程與讀進(jìn)程之間互斥，故設(shè)置一個信號量w=1。又因讀進(jìn)程之間共享，讓第一個讀進(jìn)程執(zhí)行wait(w)操作，最后一個讀進(jìn)程執(zhí)行signal(w)。為了區(qū)分讀進(jìn)程，設(shè)置一個統(tǒng)計變量read_count，初值為0，每當(dāng)一個讀進(jìn)程到達(dá)執(zhí)行read_count+1，離開時執(zhí)行read_count－1;read_count=1 時表示第1 個讀進(jìn)程到達(dá)，當(dāng)read_count=0 時表示最后一個讀進(jìn)程要離開。由于read_count 是多個讀進(jìn)程共享變量，必須互斥訪問，為此再設(shè)置一個信號量r=1。整個問題同步控制的主要代碼如圖4 所示。

圖3 生產(chǎn)者－消費(fèi)者問題

1.5 父母兒女吃水果問題

桌上有一個盤子，可以存放一個水果。父親總是放蘋果到盤子中，而母親則總是放香蕉到盤子中，一個兒子專等吃盤中的香蕉，而一個女兒專等吃盤中的蘋果，試寫出這兩個并發(fā)進(jìn)程能正確執(zhí)行的程序。

分析問題:盤子放一個水果，這是互斥控制;女兒吃父親放的蘋果，兒子吃母親放的香蕉，這是兩個同步控制，因此設(shè)置一個互斥信號量S=1，初值為1，兩個同步信號量a 和b，初值均為0?？刂拼a的流程如圖5 所示。

圖4 讀者－寫者問題

圖5 父母兒女吃水果問題(一)

修改上述問題，桌上有一個盤子，可以存放兩個水果，但每次存和取一個水果。父親總是放蘋果到盤子中，而母親則總是放香蕉到盤子中，兩個兒子專等吃盤中的香蕉，而兩個女兒專等吃盤中的蘋果，試寫出這兩個并發(fā)進(jìn)程能正確執(zhí)行的程序。

分析問題:由于盤子可以放兩個水果，故設(shè)置同種資源信息量E=2，盤子每次放取水果只能一個，因此設(shè)置互斥信號量S=1，兩個同步信號量a=0 和b=0。程序流程如圖6 所示。

圖6 父母兒女吃水果問題(二)

2 求解規(guī)律

通過上述案例的求解分析，關(guān)于互斥與同步問題總結(jié)出以下幾種的常見類型。不同類型的同步問題利用信號量機(jī)制去求解時，信號量的初值設(shè)置以及wait 和signal 操作的規(guī)律如表1 所示。編寫同步問題的代碼時，要分析有哪些進(jìn)程，進(jìn)程在推進(jìn)過程中使用哪類資源，以確定互斥和同步的類型;然后按著進(jìn)程推進(jìn)的活動編寫代碼，設(shè)置信號量的初值和wait、signal 操作。代碼編寫完成后，還需進(jìn)一步分析是否有死鎖和饑餓發(fā)生;若有則要解決，完善代碼;最后還要優(yōu)化代碼，提高程序的并發(fā)度。

表1 同步問題類型表

3 結(jié)語

同步控制是操作系統(tǒng)、并發(fā)程序設(shè)計、多核多線程等計算機(jī)專業(yè)課程中的關(guān)鍵問題，也是難點問題。本文選擇及設(shè)計了幾個經(jīng)典案例，通過對案例問題的求解分析，將同步控制問題劃分為互斥、同步、同種資源等六種類型，并給出了解決這六種類型問題的求解規(guī)律，希望對學(xué)習(xí)者有所借鑒和幫助。

［1］ 湯小丹，湯子瀛.計算機(jī)操作系統(tǒng)［M］.西安:西安電子科學(xué)大學(xué)出版社，2007.

［2］ 左萬歷，周長林.操作系統(tǒng)教程［M］.北京:高等教育出版社，2007.

［3］ 左萬歷.操作系統(tǒng)習(xí)題與實驗指導(dǎo)［M］.北京:高等教育出版社，2005.

［4］ Gary Nutt.操作系統(tǒng)現(xiàn)代觀點［M］.孟祥山，晏益，譯.北京:機(jī)械工業(yè)出版社，2004.