基于信號(hào)量的生產(chǎn)者_(dá)消費(fèi)者問題設(shè)計(jì)與分析_圖文

1、第22卷第5期合肥工業(yè)大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版Vo l.22No.5 2008年10月JOU RNAL OF H EFEI U NIVE RSIT Y OF T ECH NOLOGY(Social S ciencesOct.2008基于信號(hào)量的生產(chǎn)者 消費(fèi)者問題設(shè)計(jì)與分析劉曉平, 石 慧, 凌 實(shí), 杜 琳, 田衛(wèi)東(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,合肥 230009摘 要:生產(chǎn)者 消費(fèi)者問題是操作系統(tǒng)課程教學(xué)中進(jìn)程同步與互斥的經(jīng)典問題,深刻理解此問題對(duì)理解操作系統(tǒng)中的進(jìn)程管理具有重要意義。文章應(yīng)用可視化的方法、基于多線程方式,對(duì)生產(chǎn)者 消費(fèi)者問題進(jìn)行了模擬,并通過實(shí)際測(cè)試比較了生產(chǎn)者、消費(fèi)者之間設(shè)

2、置單一互斥信號(hào)量與設(shè)置兩個(gè)互斥信號(hào)量?jī)煞N不同方式對(duì)程序運(yùn)行效率的影響。在給學(xué)生以直觀映像的同時(shí),引導(dǎo)學(xué)生對(duì)此問題進(jìn)行深入思考,激發(fā)學(xué)生的創(chuàng)新意識(shí)。關(guān)鍵詞:操作系統(tǒng);生產(chǎn)者 消費(fèi)者問題;進(jìn)程同步;可視化;程序設(shè)計(jì)中圖分類號(hào):T P391 文獻(xiàn)標(biāo)志碼:A 文章編號(hào):1008 3634(200805 0084 05Design and A nalysis of Producer consumerProblem Based on Semaphore M echanismLIU Xiao ping, SH I H ui, LING Shi, DU Lin, TIAN Wei dong (School o

3、f Com puter Science and Information Engin eering,H efei U nivers ity of T echnology,Hefei230009,Chin aAbstract:Pro ducer consumer problem is a classic example of processes synchronization and mutual ex clusion in teaching of operating sy stem.Deep understanding that is o f great sig nificance for ri

4、ght un der standing of the process manag em ent.In this paper,a m ulti threaded based sim ulation progr am m ing o f this pro blem is presented.Tw o different sem aphore mechanism s:producer and consumer pro cesses w ith shared m utex o r two different mutex es,are compar ed on the impact o f o pera

5、tional effi ciency by actual test.In addition to a visual image to students,it can also g uide students on the prob lem in depth reflection and inspire their aw areness of innovation.Key words:operating system;pr oducer consumer pro blem;process synchro nization;visualization; pro gramm ing操作系統(tǒng)(Oper

6、ating System是高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)一門重要的專業(yè)基礎(chǔ)課程,掌握了操作系統(tǒng)才能領(lǐng)會(huì)計(jì)算機(jī)系統(tǒng)核心軟件的本質(zhì),才能自如地進(jìn)行計(jì)算機(jī)軟件開發(fā)、能動(dòng)地推進(jìn)計(jì)算機(jī)應(yīng)用向縱深方向發(fā)展。在操作系統(tǒng)課程的教學(xué)中,進(jìn)程管理、內(nèi)存管理和文件管理1三大部分是主要內(nèi)容。其中如何有效地使用信號(hào)量機(jī)制來(lái)實(shí)現(xiàn)并發(fā)進(jìn)程的同步與互斥是在進(jìn)程管理教學(xué)中面臨的主要問題。歷來(lái)研究進(jìn)程同步的經(jīng)典問題有 生產(chǎn)者 消費(fèi)者問題 哲學(xué)家進(jìn)餐問題和 讀者寫者問題等。 生產(chǎn)者 消費(fèi)者問題作為其中較為基礎(chǔ)的問題,對(duì)理解進(jìn)程同步互斥具有重要意義,進(jìn)而有利于學(xué)生引申思考和解決其他進(jìn)程同步問題,因此,本文將以此為研究對(duì)象,探討進(jìn)程同步

7、問題。收稿日期:2007 09 20基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60673028作者簡(jiǎn)介:劉曉平(1964-,男,山東濟(jì)南人,教授,博士生導(dǎo)師。一、生產(chǎn)者 消費(fèi)者問題生產(chǎn)者 消費(fèi)者(Producer Consumer問題是一個(gè)著名的進(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ā)進(jìn)行,在他們之間設(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)程都是以異步方式進(jìn)行的,但他們之間必須保持同步,即不允許消費(fèi)者進(jìn)

8、程到一個(gè)空的緩沖區(qū)中去取產(chǎn)品,也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品2。文獻(xiàn)2,3中對(duì)于此問題的解決是分別通過記錄型信號(hào)量和AND 信號(hào)量來(lái)實(shí)現(xiàn)進(jìn)程間的同步與互斥。文獻(xiàn)4中采用有限狀態(tài)機(jī)(FSM 和Petri 網(wǎng)的方法描述生產(chǎn)者 消費(fèi)者問題,并對(duì)FSM 和Petri 網(wǎng)進(jìn)行了比較。文獻(xiàn)5提出了在Window s 平臺(tái)下通過動(dòng)態(tài)鏈接庫(kù)(DLL,實(shí)現(xiàn)多個(gè)生產(chǎn)者與消費(fèi)者進(jìn)程共享緩沖區(qū)的解決辦法,以提高參與通信進(jìn)程的數(shù)據(jù)交換速度。文獻(xiàn)6則采用Java 語(yǔ)言通過管程機(jī)制實(shí)現(xiàn)了生產(chǎn)者 消費(fèi)者問題,使得用戶擺脫在操作PV 原語(yǔ)時(shí)的復(fù)雜性和困難性,為進(jìn)程同步問題研究提供了另一種有效的

9、方法。以上文獻(xiàn)均是對(duì)生產(chǎn)者 消費(fèi)者問題進(jìn)行原理性驗(yàn)證和定性的有益探討,對(duì)學(xué)生理解進(jìn)程同步與互斥的概念和思想具有一定的推動(dòng)作用。筆者也在長(zhǎng)期的教學(xué)工作中結(jié)合大量的課堂教學(xué)與相應(yīng)課程設(shè)計(jì)進(jìn)行了有益的探索。本文通過可視化設(shè)計(jì),實(shí)時(shí)重現(xiàn)生產(chǎn)者 消費(fèi)者問題的運(yùn)行過程,并采用單一信號(hào)量與多信號(hào)量?jī)煞N機(jī)制的實(shí)現(xiàn)對(duì)比,定性結(jié)合定量的研究方法分析不同信號(hào)量設(shè)置對(duì)程序效率的影響,從而加強(qiáng)學(xué)生對(duì)進(jìn)程同步問題的原理和算法的理解,指導(dǎo)學(xué)生應(yīng)用科學(xué)的方法分析問題和解決問題;同時(shí)通過程序的設(shè)計(jì)實(shí)現(xiàn),還可以提高學(xué)生應(yīng)用C/C+進(jìn)行程序設(shè)計(jì)的能力,激發(fā)學(xué)生的新思路。二、算法描述1.臨界區(qū)和w ait(S /sig nal(S

10、操作(1臨界區(qū):臨界區(qū)是指并發(fā)進(jìn)程中與共享變量有關(guān)的程序段。(2信號(hào)量S :可用臨界資源數(shù)量,取值只允許為 0 和 1 的信號(hào)量稱為二元信號(hào)量,主要用作互斥變量(m utex;取值允許為整數(shù)的信號(hào)量稱為一般信號(hào)量(semaphor e,主要用于進(jìn)程間的同步問題。(3w ait(S /sig nal(S 操作:最初由Dijkstra 提出的兩個(gè)原子操作概念2,信號(hào)量除初始化外僅能通過這兩個(gè)標(biāo)準(zhǔn)的原子操作w ait(S 和signal(S 來(lái)訪問。原子操作在執(zhí)行時(shí)是不可中斷的,即當(dāng)一個(gè)進(jìn)程在修改某信號(hào)量時(shí),沒有其他進(jìn)程可同時(shí)對(duì)該信號(hào)量進(jìn)行修改,以解決進(jìn)程間同步和互斥的問題。w ait(S 操作:對(duì)

11、某資源信號(hào)量S 作w ait 操作,表示申請(qǐng)資源,可用資源數(shù)S =S 1;如果S 0,表示無(wú)資源可用,本進(jìn)程掛起,變成等待資源S 的 等待 狀態(tài)。signal(S 操作:對(duì)某資源信號(hào)量S 作sig nal 操作,表示釋放資源,可用資源數(shù)S =S +1;如果S !0,表示有進(jìn)程在等待該資源,則釋放該進(jìn)程,即將等待該資源S 的首進(jìn)程的狀態(tài)變?yōu)?就緒 狀態(tài),去等待CPU 繼續(xù)運(yùn)行。2.基于信號(hào)量的生產(chǎn)者 消費(fèi)者問題算法假定在生產(chǎn)者和消費(fèi)者之間的共用緩沖區(qū)中,緩沖區(qū)的數(shù)量為n ,這時(shí)利用互斥信號(hào)量mutex 實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖區(qū)的互斥使用;利用信號(hào)量sem aphoreEmpty 和sem aphore

12、Full 分別表示緩沖區(qū)中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效,只要緩沖區(qū)未滿,生產(chǎn)者便可將消息送入緩沖區(qū);只要緩沖區(qū)未空,消費(fèi)者便可從緩沖區(qū)中取走一個(gè)消息。根據(jù)對(duì)互斥信號(hào)量mutex 的不同設(shè)置方式,有兩種不同的算法:(1生產(chǎn)者、消費(fèi)者共用一個(gè)互斥信號(hào)量mutex ,即生產(chǎn)者進(jìn)程間、消費(fèi)者進(jìn)程間和生產(chǎn)者、消費(fèi)者85第5期 劉曉平,等:基于信號(hào)量的生產(chǎn)者 消費(fèi)者問題設(shè)計(jì)與分析進(jìn)程均互斥,同一時(shí)間僅能有一個(gè)進(jìn)程訪問緩沖區(qū),兩類進(jìn)程的算法流程如圖1 所示。(2生產(chǎn)者、消費(fèi)者分別設(shè)置各自的互斥信號(hào)量,即生產(chǎn)者進(jìn)程間使用producerMutex 進(jìn)行互斥,消費(fèi)者進(jìn)程間使用con

13、sumerMutex 進(jìn)行互斥,而生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程間不互斥。只要有可用資源,兩類進(jìn)程可以同時(shí)訪問緩沖區(qū),同一時(shí)間最多允許兩個(gè)進(jìn)程訪問緩沖區(qū),兩類進(jìn)程的算法流程如圖2所示。需要區(qū)別的是,兩種算法除了互斥信號(hào)量設(shè)置方式的不同之外,對(duì)緩沖區(qū)的結(jié)構(gòu)有著不同的要求。算法1由于同一時(shí)間僅能有一個(gè)進(jìn)程訪問緩沖區(qū),所以緩沖區(qū)只需一個(gè)指針p 來(lái)記錄當(dāng)前的讀寫位置即可;算法2同一時(shí)間最多允許兩個(gè)進(jìn)程訪問緩沖區(qū),需要有兩個(gè)指針ptop 、pbottom 來(lái)分別指向生產(chǎn)者、消費(fèi)者的下一個(gè)寫入、讀取位置。了解對(duì)兩種不同互斥信號(hào)量的設(shè)置方式對(duì)程序及操作系統(tǒng)造成的影響,能有效地幫助學(xué)生深入理解生產(chǎn)者 消費(fèi)者問題,進(jìn)而

14、更好地理解進(jìn)程間同步和互斥的概念及實(shí)現(xiàn)方法。為了在教學(xué)過程中給學(xué)生以更直觀的展示,筆者設(shè)計(jì)和開發(fā)了一個(gè)生產(chǎn)者 消費(fèi)者問題的仿真程序,用多線程的方式來(lái)模擬多進(jìn)程的行為,并以可視化的方式實(shí)時(shí)地將運(yùn)行過程展示出來(lái)。程序界面以方塊表示每個(gè)線程,并標(biāo)明屬性,以顏色區(qū)別生產(chǎn)者和消費(fèi)者線程,同時(shí)動(dòng)態(tài)地繪制每個(gè)線程生產(chǎn)和消費(fèi)的物品數(shù)量。程序分別對(duì)上述兩種算法進(jìn)行了實(shí)現(xiàn),如圖3、圖4所示。二者在界面部分的主要區(qū)別是緩沖區(qū)Buff er 部分,由于兩種算法對(duì)緩沖區(qū)的結(jié)構(gòu)有著不同要求,圖3是以堆棧的存取方式來(lái)演示只有一個(gè)指針標(biāo)記的方式,而圖4 是以類似循環(huán)隊(duì)列的方式來(lái)演示兩個(gè)指針的標(biāo)記方式。86 合肥工業(yè)大學(xué)學(xué)報(bào)(

15、社會(huì)科學(xué)版 2008年10月三、測(cè)試比較1.評(píng)價(jià)模型和測(cè)試用例這里利用Amdahl 7定律評(píng)價(jià)上述兩種算法,Amdahl 定律定義了由于采用特殊的方法所能獲得的加速比的大小,即絕對(duì)加速比(SpeedupS :其中,為設(shè)置一個(gè)互斥信號(hào)量(算法1時(shí)實(shí)際生產(chǎn)/消費(fèi)一定數(shù)量的物品所需要的時(shí)間;為分別設(shè)置兩個(gè)互斥信號(hào)量(算法2時(shí)實(shí)際生產(chǎn)/消費(fèi)同樣數(shù)量的物品所需要的時(shí)間。Amdahl 定律適用于負(fù)載固定的情況。具體到這兩個(gè)算法的比較即要盡量保持測(cè)試時(shí)的參數(shù)及運(yùn)行環(huán)境的一致。根據(jù)上述對(duì)兩個(gè)算法的描述,對(duì)于相同數(shù)量的任務(wù)量(完全生產(chǎn)和消費(fèi)完該數(shù)量的物品所需要的時(shí)間主要受如下參數(shù)影響,如表1所示:表1 算法涉及

16、參數(shù)因 素參 數(shù)緩沖區(qū)生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程可以看到程序的運(yùn)行時(shí)間受到許多參數(shù)的影響,為了盡量準(zhǔn)確地比較兩種算法,現(xiàn)做如下討論:(1緩沖區(qū)的數(shù)量需要設(shè)置足夠大,使程序運(yùn)行過程中不會(huì)出現(xiàn)因緩沖區(qū)不足而造成的等待時(shí)間,以盡可能排除由于對(duì)信號(hào)量semaphoreFull 進(jìn)行的wait 和signal 操作造成的影響;(2生產(chǎn)者總的生產(chǎn)能力(個(gè)數(shù)*(生產(chǎn)一個(gè)產(chǎn)品時(shí)間+寫入緩沖區(qū)時(shí)間應(yīng)與消費(fèi)者總的消費(fèi)能力(個(gè)數(shù)*(消費(fèi)1個(gè)產(chǎn)品時(shí)間+讀取緩沖區(qū)時(shí)間相同,使程序運(yùn)行過程中不會(huì)出現(xiàn)過分空閑的狀態(tài),以盡可能排除由于對(duì)信號(hào)量semaphoreEmpty 進(jìn)行的wait 和signal 操作造成的影響;(3由于實(shí)際

17、生產(chǎn)產(chǎn)品和消費(fèi)產(chǎn)品的操作均在互斥區(qū)外進(jìn)行,對(duì)兩種互斥變量設(shè)置方法造成的影響是相同的,因此這里設(shè)生產(chǎn)一個(gè)產(chǎn)品時(shí)間和消費(fèi)一個(gè)產(chǎn)品時(shí)間相等,且為一個(gè)定值。因此,這里僅對(duì)生產(chǎn)者、消費(fèi)者不同進(jìn)程個(gè)數(shù)(2、4、8和讀/寫緩沖區(qū)時(shí)間(0ms 、10ms 、100ms 、1000ms的不同情況進(jìn)行測(cè)試和比較。2.試結(jié)果與分析測(cè)試環(huán)境為:硬件:CPU 采用Intel Pentium 4(3.06GHz軟件:操作系統(tǒng)為Window s XP Pro sp2圖5-7分別是生產(chǎn)者、消費(fèi)者線程各2、4、8個(gè)時(shí),算法2相對(duì)于算法1在生產(chǎn)、消費(fèi)相同數(shù)量物品時(shí)不同讀/寫緩沖區(qū)時(shí)間的設(shè)定條件下得到的加速比?？梢钥吹?在讀、寫緩

18、沖區(qū)時(shí)間設(shè)置較小,線程數(shù)較少時(shí),算法2較算法1的加速效果并不明顯,而讀、寫緩沖區(qū)時(shí)間較大時(shí)(1000ms,穩(wěn)定于接近兩倍的加速。87第5期 劉曉平,等:基于信號(hào)量的生產(chǎn)者 消費(fèi)者問題設(shè)計(jì)與分析這主要是由于較大的讀寫緩沖區(qū)時(shí)間使互斥變量的設(shè)置方式對(duì)程序運(yùn)行時(shí)間的影響占了主導(dǎo)地位,即算圖7 生產(chǎn)者 消費(fèi)者線程數(shù)分別為4時(shí)加速比法2對(duì)算法1的修改占程序運(yùn)行時(shí)間的比例加大,由Amdahl 定律可知程序的加速比得以體現(xiàn)。這里需要指出的是在讀、寫緩沖區(qū)時(shí)間設(shè)置為10ms 的情況時(shí),算法2較算法1的效率甚至有所下降,加速比呈現(xiàn)小于1的趨勢(shì),該現(xiàn)象本文目前尚不能給出圓滿的解答,尚需進(jìn)一步實(shí)例測(cè)試并與計(jì)算環(huán)境相

19、結(jié)合進(jìn)行研究。由上述測(cè)試實(shí)驗(yàn)可以清楚地看出兩種互斥變量的設(shè)置方式對(duì)程序造成的影響。算法2由于使用兩個(gè)互斥變量使生產(chǎn)者和消費(fèi)者之間不互斥,在讀/寫緩沖區(qū)時(shí)間較大時(shí),較算法1在執(zhí)行效率上有較大提升,能得到理想的兩倍加速比。四、結(jié)束語(yǔ)生產(chǎn)者 消費(fèi)者問題歷來(lái)是研究進(jìn)程同步的典型問題,深刻理解此問題對(duì)理解操作系統(tǒng)中進(jìn)程同步的本質(zhì)具有重要意義,進(jìn)而為后期的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。本文以此為對(duì)象,作為探討進(jìn)程同步問題的切入點(diǎn)。經(jīng)典教材中的生產(chǎn)者 消費(fèi)者問題均以單一互斥信號(hào)量的方式進(jìn)行描述,即生產(chǎn)者、消費(fèi)者共用一個(gè)互斥信號(hào)量。這樣雖然簡(jiǎn)化了模型,易于學(xué)生理解,但就問題本身的約束條件而言,并沒有要求生產(chǎn)者與消費(fèi)者之間要互斥的訪問緩沖區(qū)。對(duì)設(shè)置兩個(gè)互斥信號(hào)量與設(shè)置單個(gè)信號(hào)量?jī)煞N不同方式的比較,對(duì)學(xué)生進(jìn)一步理解該問題具有積極作用。合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院可視化與協(xié)同計(jì)算研究室(VCC,在可視化、仿真技術(shù)等方面有著豐富的經(jīng)驗(yàn),所以在探討此問題上,本文采用可視化的方式實(shí)時(shí)地演示了程序的運(yùn)行過程,使得學(xué)生對(duì)原本理論性較強(qiáng)、內(nèi)容抽象的該問題有了一個(gè)直觀的理解;通過對(duì)設(shè)置兩個(gè)互斥信號(hào)量與設(shè)置單個(gè)信號(hào)量?jī)煞N不同方式的測(cè)試對(duì)比,運(yùn)用定性結(jié)合定量的分析方法比較不同信號(hào)量設(shè)置的效率問題,進(jìn)一步加深了學(xué)生對(duì)進(jìn)程同