操作系統(tǒng)中互斥與同步問題求解方法的探析

唐伎玲，黃 葵，谷 赫

(長春大學 計算機科學技術學院，長春130022)

0 前言

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

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

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

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

1 經(jīng)典案列

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

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

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

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

1.2 司機－售票員問題。

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

圖2 司機－售票員問題

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

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

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

1.4 讀者－寫者問題

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

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

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

1.5 父母兒女吃水果問題

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

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

圖4 讀者－寫者問題

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

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

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

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

2 求解規(guī)律

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

表1 同步問題類型表

3 結語

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

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

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

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

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