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

1、哈爾濱師范大學(xué)學(xué)年論文題目生產(chǎn)者與消費(fèi)者問題學(xué)生楊善明指導(dǎo):教師倫立軍 教授年級(jí)2008 級(jí)專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)系別計(jì)算機(jī)科學(xué)與技術(shù)系學(xué)院計(jì)算機(jī)科學(xué)與信息工程學(xué)院哈爾濱師范大學(xué)2011年 6 月論文提要生產(chǎn)者一消費(fèi)者問題(Producer_consumer )是一個(gè)經(jīng)典的進(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è)置有個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程可將它所生產(chǎn)的產(chǎn) 品放入一個(gè)緩沖區(qū)中，消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)取得一個(gè)產(chǎn)品消費(fèi)。盡管所有的生產(chǎn)者進(jìn) 程和消費(fèi)者進(jìn)程都是以異步的方式運(yùn)行的，但它們之間必須保

2、持同步，即不允許消費(fèi)者進(jìn)程 到一個(gè)空緩沖區(qū)去取產(chǎn)品，也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝有消息尚未被取走產(chǎn)品的緩沖區(qū) 投放產(chǎn)品。如下圖所示：一叱消費(fèi)者1消費(fèi)者24消費(fèi)者mn個(gè)大小相等的緩沖區(qū)，鉀 個(gè)緩沖區(qū)可存放個(gè)消息在中引入進(jìn)程后，雖然提高了資源的利用率和系統(tǒng)的吞吐量，但由于進(jìn)程的異步性，也會(huì)給系統(tǒng)造成混亂，尤其是在它們爭用臨界資源的時(shí)候。例如，當(dāng)多個(gè)進(jìn)程去爭用一臺(tái)打印機(jī)時(shí)，有可能使多個(gè)進(jìn)程的輸出結(jié)果交織在一起，難于區(qū)分；而當(dāng)多個(gè)進(jìn)程去爭用共享變量，表格，鏈表時(shí)，有可能使數(shù)據(jù)處理出錯(cuò)。 進(jìn)程同步的主要任務(wù)就是使并發(fā)執(zhí)行的諸進(jìn)程之間 能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。進(jìn)程同步其優(yōu)

3、點(diǎn)在于能夠讓操作系統(tǒng)更加有效地對(duì)資源進(jìn)行管理和調(diào)度，最大潛力地發(fā)揮處理機(jī)的性能。讓系統(tǒng)的執(zhí)行更加暢通無阻，盡可能地讓系統(tǒng)少出現(xiàn)一些由于系統(tǒng)資源分 配不合理所帶來的死鎖、 死機(jī)之類的事情的發(fā)生。 保持了處理機(jī)的高速運(yùn)行之后從用戶角度 來說程序運(yùn)行所花費(fèi)的時(shí)間就會(huì)更短。從而保證了處理機(jī)在相同的時(shí)間內(nèi)有更大的吞吐量。而把并發(fā)進(jìn)程的同步和互斥問題一般化，就可以得到一個(gè)抽象的一般模型，即本次課程設(shè)計(jì)的任務(wù)：生產(chǎn)者一消費(fèi)者問題。i生產(chǎn)者和消費(fèi)者的問題楊善明摘 要：在多道程序環(huán)境下， 進(jìn)程同步問題十分重要， 也是一個(gè)相當(dāng)有趣的問題，因而 吸引了不少學(xué)者對(duì)它進(jìn)行研究，并由此而產(chǎn)生了一系列經(jīng)典的進(jìn)程同步問題。其

4、中比較有代表性的有生產(chǎn)者一消費(fèi)者問題”、讀者一寫者問題”、哲學(xué)家進(jìn)餐問題”等等。通過對(duì) 這些問題的研究和學(xué)習(xí)，可以幫助我們更好地理解進(jìn)程同步概念及實(shí)現(xiàn)方法。關(guān)鍵詞：操作系統(tǒng) 進(jìn)程同步 生產(chǎn)者與消費(fèi)者 多線程本文討論了多線程編程及其可行性，說明了在 Windows環(huán)境下進(jìn)行多線程編程的意義，并重點(diǎn)討論了 C+Builder平臺(tái)下如何開發(fā)多線程應(yīng)用程序這一問題，通過實(shí)現(xiàn)"生產(chǎn)者一消費(fèi)者問題"這一著名的進(jìn)程同步問題，比較清晰地反映了在 Windows環(huán)境下進(jìn)行多線程編程 技術(shù)及其實(shí)現(xiàn)的作用和效果。一、設(shè)計(jì)思想我們把系統(tǒng)中使用某一類資源的進(jìn)程稱為該資源的消費(fèi)者，而把釋放同類資源的進(jìn)

5、程稱為該資源的生產(chǎn)者。例如在計(jì)算進(jìn)程與打印進(jìn)程公用一個(gè)緩沖區(qū)時(shí)，計(jì)算進(jìn)程把數(shù)據(jù)送入緩沖區(qū)，打印進(jìn)程從緩沖區(qū)中取數(shù)據(jù)打印輸出，因此，計(jì)算進(jìn)程相當(dāng)于數(shù)據(jù)資源的生產(chǎn)者，而打印進(jìn)程相當(dāng)于消費(fèi)者， 二者之間必須保持同步。 基于這一問題，我們將使用生產(chǎn)者和消費(fèi) 者這一同步機(jī)制算法來處理該問題。二、解決方案首先，我們知道，生產(chǎn)者一消費(fèi)者問題是一個(gè)同步問題。即生產(chǎn)者和消費(fèi)者之間應(yīng)滿足如下條件：1）消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的。2）生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的。另外，由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程之間必須互斥。其次，我們還必須考慮面臨的

6、問題是屬于進(jìn)程互斥還是進(jìn)程同步，或是互斥與同步的混合問題。然后根據(jù)共享資源的數(shù)量以及使用共享資源的規(guī)則正確的定義信號(hào)量及其初值。最后，還要對(duì)結(jié)果進(jìn)行分析處理。若結(jié)果中生產(chǎn)和消費(fèi)進(jìn)程都已處理完時(shí)，但還可能 出現(xiàn)以下兩種情況：一是還有生產(chǎn)進(jìn)程，但沒有空緩沖，且消費(fèi)進(jìn)程暫時(shí)已完，所以此時(shí)， 只能結(jié)束等待新的消費(fèi)進(jìn)程產(chǎn)生空緩沖。二是還有消費(fèi)進(jìn)程，但沒有了滿緩沖，且生產(chǎn)進(jìn)程暫時(shí)已完，此時(shí)，只能結(jié)束等待新的生產(chǎn)進(jìn)程來輸入數(shù)據(jù)，產(chǎn)生新的滿緩沖等。在程序中應(yīng) 能作出相應(yīng)的判斷和處理。三、程序的運(yùn)行設(shè)置本程序的執(zhí)行是在 C+的環(huán)境中通過手動(dòng)輸入生產(chǎn)者和消費(fèi)者線程的運(yùn)行速度來控制程序的運(yùn)行的。為了實(shí)現(xiàn)生產(chǎn)者進(jìn)程能

7、把生產(chǎn)出來的產(chǎn)品正確的存入緩沖區(qū)，和消費(fèi)者進(jìn)程能夠從緩沖區(qū)中取產(chǎn)品進(jìn)行消費(fèi)，防止因等待資源而出現(xiàn)死鎖的現(xiàn)象，首先設(shè)置兩個(gè)時(shí)間：生產(chǎn)者生產(chǎn)一個(gè)產(chǎn)品后等待的時(shí)間t1,和消費(fèi)者消費(fèi)一個(gè)產(chǎn)品后等待的時(shí)間t2,來控制生產(chǎn)者和消費(fèi)者進(jìn)程執(zhí)行的速度。其函數(shù)原形是sleep(tl)和sleep(t2)其中t1、t2指定義掛起執(zhí)行線程的時(shí)間，以毫秒為單位，取值為0時(shí)，該線程將余下的時(shí)間片交給處于就緒狀態(tài)的同一優(yōu)先級(jí)的其他線程。若沒有處于就緒狀態(tài)的同一優(yōu)先級(jí)的其他線程，則函數(shù)立即返回。四、信號(hào)量機(jī)制的引用為了生產(chǎn)者進(jìn)程送入緩沖池的消息能被消費(fèi)者進(jìn)程正確地取出消費(fèi)，我們引入了信號(hào)量機(jī)制以避免進(jìn)程在執(zhí)行的過程中沒有保

8、持同步的情況發(fā)生。設(shè)置了信號(hào)量機(jī)制以后，生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程只能對(duì)緩沖區(qū)互斥地訪問，也就是 當(dāng)生產(chǎn)者進(jìn)程執(zhí)行的時(shí)候消費(fèi)者進(jìn)程不能執(zhí)行，反之奕然。其使用原理如下：一個(gè)進(jìn)程在執(zhí)行的時(shí)候它必需擁有信號(hào)量而且在執(zhí)行的過程會(huì)一直 占有信號(hào)量直到進(jìn)程運(yùn)行結(jié)束時(shí)釋放信號(hào)量，這樣就能保證多個(gè)進(jìn)程的互斥執(zhí)行。五、實(shí)驗(yàn)程序的結(jié)構(gòu)圖六、運(yùn)行結(jié)果與分析成 *C:Docu>entsand SettingsAd>±nistrator桌面'操作系統(tǒng)作業(yè)'生產(chǎn)者消費(fèi)者程 可融入文件是=thread 1P5thread 2P4thread 3lP2.Q00Q00thread 4IC313

9、2Producer3 sends the producerequire.Producer3 befinto produceat position0.Produeer3 f inishprodueing-position0 i 3ConsunieF4 requestto consume 1 productProducer2 sends the producerequire.Producer2 beginto produceat position1.Pi'oducei'2 f inishprodue ingzpos ition11:2Producer1 sends the prod

10、ucerequire.ProducoF1 bofinto produceat position2.Producer1 finishprodueing- -position 2 J： 1Consumer4 begin toconsume1 productConsiimei'4 £ inish consuming1：position 2 J： -1Consunier4 requestto consume 3 productConsume i44 be grin toconsume3 productConsumer4 f inish consuning3獸position 0 J：

11、 -1Consuner4 requestto consume 2 productCo ns nine i'4 begin toconsume2 productGo ns liner4 f inish consuming2：position1 : -1RLL Producer and consumer haue finished their work. Press anj/ key to quit?其中實(shí)驗(yàn)數(shù)據(jù)是:31P52P43P24C31321、在每個(gè)程序中坐須先做P(mutex),后做V(mutex),二者要成對(duì)出現(xiàn)。夾在二者中間的代碼段就是該進(jìn)程的臨界區(qū)。2、對(duì)同步信號(hào)量full

12、和empty的P, V操作同樣必須成對(duì)出現(xiàn)，但它們分別位于不同 的程序中。3、無論在生產(chǎn)者進(jìn)程中還是在消費(fèi)者進(jìn)程中，兩個(gè)P操作的次序不能顛倒：應(yīng)先執(zhí)行同步信號(hào)量的P操作，然后執(zhí)行互斥信號(hào)量的P操作。否則可能造成進(jìn)程死鎖。七、結(jié)論通過這次實(shí)驗(yàn)了解到生產(chǎn)者 -消費(fèi)者問題是一個(gè)經(jīng)典的進(jìn)程同步問題，以及在其中使用 信號(hào)量機(jī)制，生產(chǎn)者與消費(fèi)者問題要求我們?cè)O(shè)計(jì)在同一個(gè)進(jìn)程地址空間內(nèi)執(zhí)行的兩個(gè)線程。生產(chǎn)者線程生產(chǎn)物品，然后將物品放置在一個(gè)空緩沖區(qū)中供消費(fèi)者線程消費(fèi)，而消費(fèi)者線程從緩沖區(qū)中獲得物品，然后釋放緩沖區(qū)。當(dāng)生產(chǎn)者線程生產(chǎn)物品時(shí)，如果沒有空緩沖區(qū)可用， 那么生產(chǎn)者線程必須等待消費(fèi)者線程釋放出一個(gè)空緩沖

13、區(qū)，當(dāng)消費(fèi)者線程消費(fèi)物品時(shí)，如果沒有滿的緩沖區(qū)，那么消費(fèi)者線程將被阻塞，直到新的物品被生產(chǎn)出來。這次生產(chǎn)者和消費(fèi)者問題的課程設(shè)計(jì)，不但加深了我對(duì)操作系統(tǒng)中多線程機(jī)制的理解和認(rèn)識(shí)，更讓我認(rèn)識(shí)到知識(shí)的掌握，僅靠學(xué)習(xí)理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，要與實(shí)際動(dòng)手操作相結(jié)合才能更好的理解和分析問題。八、結(jié)束語通過本次設(shè)計(jì)，我更近一步地了解了 OS的進(jìn)程機(jī)制和信號(hào)量實(shí)現(xiàn)生產(chǎn)者消費(fèi)者問題的 并發(fā)控制全過程，尤其是對(duì)多進(jìn)程程序設(shè)計(jì)方法有了更深的理解。在書本上學(xué)習(xí)有關(guān)進(jìn)程的同步的問題只是理論上的說法，并沒有一個(gè)實(shí)際的東西，至少應(yīng)是看得見的， 對(duì)其含義也只是處于表面上的理解。這次實(shí)驗(yàn)我才體會(huì)到進(jìn)程同步的真正涵義。最后，我還要感謝倫老師在實(shí)驗(yàn)過程中給予的指導(dǎo)和同學(xué)的幫助。特別是在實(shí)驗(yàn)開始時(shí)，我根本搞不懂是做什么， 是倫老師給予引導(dǎo)才使我對(duì)此