基于信號量的生產(chǎn)者_消費者問題設(shè)計與分析_圖文

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

2、置單一互斥信號量與設(shè)置兩個互斥信號量兩種不同方式對程序運行效率的影響。在給學(xué)生以直觀映像的同時,引導(dǎo)學(xué)生對此問題進行深入思考,激發(fā)學(xué)生的創(chuàng)新意識。關(guān)鍵詞:操作系統(tǒng);生產(chǎn)者 消費者問題;進程同步;可視化;程序設(shè)計中圖分類號:T P391 文獻標志碼:A 文章編號: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é)校計算機科學(xué)與技術(shù)專業(yè)一門重要的專業(yè)基礎(chǔ)課程,掌握了操作系統(tǒng)才能領(lǐng)會計算機系統(tǒng)核心軟件的本質(zhì),才能自如地進行計算機軟件開發(fā)、能動地推進計算機應(yīng)用向縱深方向發(fā)展。在操作系統(tǒng)課程的教學(xué)中,進程管理、內(nèi)存管理和文件管理1三大部分是主要內(nèi)容。其中如何有效地使用信號量機制來實現(xiàn)并發(fā)進程的同步與互斥是在進程管理教學(xué)中面臨的主要問題。歷來研究進程同步的經(jīng)典問題有 生產(chǎn)者 消費者問題 哲學(xué)家進餐問題和 讀者寫者問題等。 生產(chǎn)者 消費者問題作為其中較為基礎(chǔ)的問題,對理解進程同步互斥具有重要意義,進而有利于學(xué)生引申思考和解決其他進程同步問題,因此,本文將以此為研究對象,探討進程同步

7、問題。收稿日期:2007 09 20基金項目:國家自然科學(xué)基金資助項目(60673028作者簡介:劉曉平(1964-,男,山東濟南人,教授,博士生導(dǎo)師。一、生產(chǎn)者 消費者問題生產(chǎn)者 消費者(Producer Consumer問題是一個著名的進程同步問題。它描述的是:有一群生產(chǎn)者進程在生產(chǎn)產(chǎn)品,并將這些產(chǎn)品提供給消費者進程去消費。為使生產(chǎn)者進程和消費者進程能并發(fā)進行,在他們之間設(shè)置了一個具有N 個緩沖區(qū)的緩沖池,生產(chǎn)者進程可以將其所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中,消費者進程可以從一個緩沖區(qū)中取得產(chǎn)品去消費。盡管所有的生產(chǎn)者進程和消費者進程都是以異步方式進行的,但他們之間必須保持同步,即不允許消費者進

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

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

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

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

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

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

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

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

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

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

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

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