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

唐伎玲，黃 葵，谷 赫

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

0 前言

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

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

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

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

1 經(jīng)典案列

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

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

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

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

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

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

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

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

生產(chǎn)者－消費(fèi)者問(wèn)題是一個(gè)著名的進(jìn)程同步問(wè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è)置了一個(gè)具有n 個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中;消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi)。盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，即不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品，也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。

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

1.4 讀者－寫者問(wèn)題

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

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

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

1.5 父母兒女吃水果問(wèn)題

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

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

圖4 讀者－寫者問(wèn)題

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

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

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

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

2 求解規(guī)律

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

表1 同步問(wèn)題類型表

3 結(jié)語(yǔ)

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

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

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

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

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