生產(chǎn)者與消費者算法實現(xiàn)

1、課程設(shè)計說明書題目: 生產(chǎn)者與消費者算法模擬 院 系： 計算機科學(xué)與工程 專業(yè)班級： 信息安全(xxxx)班 學(xué) 號： 201130xxxx 學(xué)生姓名： xxxx 指導(dǎo)教師： xxxx 2013年 xx月 xx 日 xxxx大學(xué)課程設(shè)計（論文）任務(wù)書 計算機 院系 計算機 教研室學(xué) 號20113xxxxx學(xué)生姓名xxxx專業(yè)（班級）xxxxx設(shè)計題目生產(chǎn)者與消費者算法模擬設(shè)計技術(shù)參數(shù)（1）系統(tǒng)作業(yè)或進程的數(shù)目；（2）系統(tǒng)資源的種類和數(shù)目；（3）系統(tǒng)作業(yè)或進程的對每類資源的最大需求數(shù)目；（4）系統(tǒng)作業(yè)或進程已分配的資源數(shù)目。設(shè)計要求（1）檢查系統(tǒng)安全狀態(tài)：根據(jù)系統(tǒng)作業(yè)或進程的對每類資源的最大需求

2、數(shù)目、已分配的資源數(shù)目等計算是否存在安全序列。（2）檢查系統(tǒng)是否可以繼續(xù)某個進程資源分配請求。工作量 要求設(shè)計說明書的字?jǐn)?shù)在3000字以上。工作計劃2012.11.25-11.26 根據(jù)課程設(shè)計的要求，查找相關(guān)資料，完成需求分析；2012.11.26-11.27 進行系統(tǒng)的概要設(shè)計；2012.11.27-11.28 進行系統(tǒng)的詳細(xì)設(shè)計和源代碼的書寫；2013.11.29-11.30 對系統(tǒng)進行調(diào)試分析，寫出課程設(shè)計報告。參考資料1 Cay S.Horstmann,Gary Cornell編著.JAVA核心技術(shù) 卷 I.北京：機械工業(yè)出版社,2008.2 鄭莉編著.Java語言程序設(shè)計（第二版）

3、.北京：清華大學(xué)出版社,2011.3 呂國英等編著.算法設(shè)計與分析.北京：清華大學(xué)出版社，2009.4 馬小軍等編.軟件工程項目案例與實踐指導(dǎo). 北京：清華大學(xué)出版社，2013.5 湯子瀛等編著. 計算機操作系統(tǒng).西安：西安電子科技大學(xué)出版社,2011.指導(dǎo)教師簽字教研室主任簽字2012年xx月xx日指導(dǎo)教師評語：成績： 指導(dǎo)教師： 年 月 日xxxx大學(xué)課程設(shè)計（論文）成績評定表目錄1.問題描述11.1目的11.2設(shè)計要求12.需求分析13. 概要設(shè)計13.1程序流程圖14. 詳細(xì)設(shè)計24.1程序框架24.1.1生產(chǎn)者與消費者的父類24.1.2 生產(chǎn)者類54.1.3 消費者類64.1.4 主

4、程序入口64.2基本算法分析74.2.1 wait(mutex)與signal()數(shù)值信號74.2.2 isBufferEmpty()與isBufferFull()信號74.2.3 produce()存數(shù)方法與consume()取數(shù)方法85. 調(diào)試分析105.1不啟動生產(chǎn)者線程測試結(jié)果分析105.2不啟動消費者線程測試結(jié)果分析116. 用戶手冊117. 測試結(jié)果128. 設(shè)計體會13參考文獻(xiàn)13附錄131.問題描述1.1目的掌握信號的使用方法和P、V操作的定義，掌握使用P、V操作實現(xiàn)進程之間同步與互斥的方法，加深對進程同步互斥概念的理解。1.2設(shè)計要求設(shè)計一程序，由一個進程創(chuàng)建三個子進程，三個

5、子進程一個是生產(chǎn)者進程，兩個是消費者進程，且要求：l 父子進程都使用父進程創(chuàng)建的共享存儲區(qū)進行通信，由生產(chǎn)者進程將一個數(shù)組中的十個數(shù)值發(fā)送到由5個緩沖區(qū)組成的共享內(nèi)存中；l 兩個消費者進程輪流接收并輸出這十個數(shù)值，同時將兩個消費者進程讀出的數(shù)值進行累加求各和。l 考慮生產(chǎn)者進程生產(chǎn)的速度和消費者進程速度。2.需求分析生產(chǎn)者-消費者問題是一個著名的進程同步問題。既然有進程間的同步，也就必將涉及到進程之間的互斥與通信問題，對于這個問題的解決有著很強的現(xiàn)實意義。它的現(xiàn)實意義在于可以類比到計算機中對于臨界資源的互斥共享。生產(chǎn)者與消費者就好比是對計算機臨界資源訪問的程序或用戶，而臨界資源如打印機、磁帶機

6、等設(shè)備。3. 概要設(shè)計3.1程序流程圖說明：圖3.1 程序流程圖所示，首先生產(chǎn)者與消費者線程創(chuàng)建，便就去訪問緩沖區(qū)。對于生產(chǎn)者若緩沖區(qū)沒有被其他線程訪問，且緩沖區(qū)未滿則生產(chǎn)數(shù)據(jù)存放到緩沖區(qū)，若其中有一條件沒有滿足則生產(chǎn)者線程進入阻塞狀態(tài)。而對于消費者同樣也需要緩沖區(qū)沒有被其他線程訪問，但同時要求緩沖區(qū)未空才能從緩沖區(qū)取數(shù)據(jù)，若其中有一個條件為滿足則同樣進入阻塞狀態(tài)?！吧a(chǎn)者”線程創(chuàng)建“消費者”阻塞“生產(chǎn)者”向緩沖區(qū)放入數(shù)據(jù)否是否有線程訪問緩沖區(qū)否是是“消費者”或“生產(chǎn)者”阻塞緩沖區(qū)是否滿否是否有線程訪問緩沖區(qū)是緩沖區(qū)是否空否“消費者”線程創(chuàng)建“生產(chǎn)者”阻塞“消費者”從緩沖區(qū)中取數(shù)圖3.1 程序

7、流程圖4. 詳細(xì)設(shè)計4.1程序框架4.1.1生產(chǎn)者與消費者的父類public class SuperThread extends JPanel/定義緩沖區(qū)的讀寫鎖private Lock bufferLock;/ 共享緩沖區(qū)public static IntBuffer buffer = IntBuffer.allocate(5);/生產(chǎn)者數(shù)組public int array = 1,5,6,9,8,11,13,10,7,3;/生產(chǎn)者執(zhí)行的次數(shù)public static int count = 0;/兩個生產(chǎn)者取出數(shù)據(jù)的累加public static int consumerSum = 0;/

8、記錄消費者取數(shù)次數(shù)public static int consumerCount = 0;/存放從緩沖區(qū)中取得的數(shù)據(jù)private static int consumerData;/定義線程名public String nameString;/線程互斥信號，值為 0 表示生產(chǎn)者進程，值為 1 表示消費者進程public static int mutex = 0;/* 構(gòu)造函數(shù) */public SuperThread(String name)/主要完成一些變量的初始化/* 獲得線程名 */public String getNameString() return nameString;/* 設(shè)置

9、線程名 */public void setNameString(String nameString) String = nameString;/* 獲得互斥信號 */public static int getMutex() return mutex;/* 設(shè)置互斥信號 */public static void setMutex(int mutex) SuperThread.mutex = mutex;/* 判斷是否有線程訪問緩沖區(qū)，沒有則對線程進行加鎖 */public boolean wait(int mutex)if (mutex = 1) return false;el

10、se return true;/* 釋放進程操作完成信號，其實本質(zhì)就是修改mutex的信號值 */public static void signal()mutex = 0;/* 判斷緩沖區(qū)是否為空 */public boolean isBufferEmpty()/根據(jù)緩沖區(qū)中是否有0存在來判斷是否為空/若0的個數(shù)為5則為空，反之則不為空/* 判斷緩沖區(qū)是否為滿 */public boolean isBufferFull()/根據(jù)緩沖區(qū)中是否有0存在來判斷是否為空/若0的個數(shù)為0則為滿，反之則不滿/* 消費數(shù)，即在緩沖區(qū)中取數(shù) */public void consume()if (wait(mu

11、tex) && !isBufferEmpty() /判斷是否訪問緩沖區(qū)/加鎖bufferLock.lock();try /設(shè)置互斥信號/從緩沖區(qū)取數(shù)/將取數(shù)后的緩沖區(qū)置0/釋放互斥信號finally/解鎖bufferLock.unlock();/* 消費者取得緩沖區(qū)數(shù)據(jù)*/public int getBufferData(int index)/完成取數(shù)操作return data;/* 生產(chǎn)數(shù)，即向緩沖區(qū)中存數(shù)*/public void produce()if (wait(mutex) && !isBufferFull() /判斷是否訪問緩沖區(qū)bufferLock

12、.lock();/加鎖try/設(shè)置互斥信號/向緩沖區(qū)存數(shù)/釋放互斥信號finally/解鎖bufferLock.unlock();/* 生產(chǎn)者向公共緩沖區(qū)放數(shù)據(jù)*/public void putBufferData(int index)/完成想緩沖區(qū)存數(shù)操作4.1.2 生產(chǎn)者類public class Producer extends SuperThread implements Runnable/ 生產(chǎn)者休眠時間private int producerDelay;/* 生產(chǎn)者構(gòu)造函數(shù) */public Producer(String name) super(name);/* 獲得生產(chǎn)者休眠時

13、間 */public int getProducerDelay() return producerDelay;/* 設(shè)置生產(chǎn)者休眠時間*/public void setProducerDelay(int producerDelay) ducerDelay = producerDelay;/* 線程中的run函數(shù)，線程啟動時默認(rèn)調(diào)用的函數(shù)*/Overridepublic void run() /線程啟動后向緩沖區(qū)存數(shù)操作4.1.3 消費者類public class Consumer extends SuperThread implements Runnable /* 消費者休眠時

14、間 */private int consumerDelay;/* 消費者構(gòu)造函數(shù) */public Consumer(String name) super(name);/* 獲得消費者休眠時間 */public int getConsumerDelay() return consumerDelay;/* 設(shè)置消費者休眠時間 */public void setConsumerDelay(int consumerDelay) this.consumerDelay = consumerDelay;/* 線程中的run函數(shù)，線程啟動時默認(rèn)調(diào)用的函數(shù) */Overridepublic void run(

15、) while (true) /線程啟動后向緩沖區(qū)取數(shù)操作4.1.4 主程序入口主函數(shù) main(String args) /生產(chǎn)者與消費者對象定義producer、consumer1、consumer2 /設(shè)置休眠參數(shù),如1000、2000、2500/創(chuàng)建線程producerThread、consumer1Thread、consumer2Thread /啟動線程producerThread.start()、consumer1Thread.start()、/consumer2Thread.start();4.2基本算法分析4.2.1 wait(mutex)與signal()數(shù)值信號數(shù)值信號wa

16、it(mutex)主要是通過整型值mutex的設(shè)置來表示緩沖區(qū)是否已被訪問，具體過程為：當(dāng)有線程需要訪問緩沖區(qū)時，先確定wait(mutex)信號值，若mutex的值為1則wait(mutex)為真，便可進行下一步操作，若mutex的值為0則wait(mutex)為不為真，該線程阻塞。當(dāng)線程完成對緩沖區(qū)的訪問后需要調(diào)用signal()信號對信號值mutex進行釋放，釋放后mutex的值為1，以便其他線程能夠訪問緩沖區(qū)。wait(mutex)與signal()的主要代碼如下：public boolean wait(int mutex)/wait(mutex)信號if (mutex = 1) re

17、turn false;else return true;public static void signal()/signal()信號mutex = 0;4.2.2 isBufferEmpty()與isBufferFull()信號對于以上所述的wait(mutex)信號還不足以控制線程之間的同步與互斥，還必須使用到isBufferEmpty()與isBufferFull()兩個信號。對于生產(chǎn)者要用到信號isBufferFull()來判斷緩沖區(qū)是否為滿，當(dāng)wait(mutex)型號值為真且isBufferFull()信號值不為真時，生產(chǎn)者線程才能對緩沖區(qū)進行存數(shù)操作，否則就阻塞等待機會。而對于消費

18、者同樣也要用到輔助信號isBufferEmpty()來判斷緩沖區(qū)是否為空，只有緩沖區(qū)不為空且wait(mutex)為真是，消費者才能對緩沖區(qū)進行取數(shù)操作。isBufferEmpty()與isBufferFull()的主要代碼如下：public boolean isBufferEmpty()/判斷緩沖區(qū)是否為空int count = 0;for (int i = 0; i < buffer.capacity(); i+) if (buffer.get(i) = 0) /根據(jù)緩沖區(qū)中的0的個數(shù)來判斷，若緩/區(qū)0的個數(shù)為5（緩沖區(qū)容量為5），則為空/反之不為空count +;if (count

19、 = 5) return true;else return false;public boolean isBufferFull()/判斷緩沖區(qū)是否為滿int count = 0;for (int i = 0; i < buffer.capacity(); i+) if (buffer.get(i) != 0) /根據(jù)緩沖區(qū)中不為0的個數(shù)來判斷，若緩/區(qū)不為0的個數(shù)小于5（緩沖區(qū)容量為5），/則不為滿，反之為滿count +;if (count < 5) return false;else return true;4.2.3 produce()存數(shù)方法與consume()取數(shù)方法pr

20、oduce()方法由生產(chǎn)者使用，在條件滿足的情況下對緩沖區(qū)進行存數(shù)操作，而這個條件就是wait(mutex)=true && ! isBufferFull()=true。對于消費者調(diào)用consume()方法同樣也要滿足這樣一個條件：wait(mutex)=true && ! isBufferEmpty()=duce()與consume()方法的主要代碼如下：/* 生產(chǎn)數(shù)，即向緩沖區(qū)中存數(shù)*/public void produce()if (wait(mutex) && !isBufferFull() bufferLock.lock

21、();/對該程序段加鎖，防止其他線程訪問緩沖區(qū)trysetMutex(1);/將線程互斥信號值mutex設(shè)置為1，使之互斥int index = 0;for (int i = 0; i < buffer.capacity(); i+)/尋找存數(shù)的位置if (buffer.get(i) = 0) index = i;break;putBufferData(index);/向緩沖區(qū)中存入數(shù)據(jù)signal();/釋放互斥信號，將mutex設(shè)置為0finallybufferLock.unlock();/解鎖/* 消費數(shù)，即在緩沖區(qū)中取數(shù) */public void consume()if (wa

22、it(mutex) && !isBufferEmpty() bufferLock.lock();/對該程序段加鎖，防止其他線程訪問緩沖區(qū)try setMutex(1);/將線程互斥信號值mutex設(shè)置為1，使之互斥int index = 0;/存放順序查找第一個為0的數(shù)的下擺int i;for (i = 0; i < buffer.capacity(); i+) /順序查找第一個為/0的數(shù)if (buffer.get(i) = 0) index = i;break;else if(buffer.get(4) > 0)/緩沖區(qū)為滿的情況index = 5;consum

23、erData = getBufferData(index-1);/取數(shù)據(jù)consumerCount +;if (consumerCount <= 2 ) consumerSum = consumerSum + consumerData;/計算兩次取數(shù)/之和if (consumerCount = 2) System.out.println("消費者取數(shù)之和為："+consumerSum);consumerSum = 0;consumerCount = 0;buffer.put(index-1, 0);/將已取過數(shù)的緩沖區(qū)重新置0consumerPrintBufferData();/輸出取數(shù)后的緩沖區(qū)signal();/釋放互斥信號，將mutex設(shè)置為0finallybufferLock.unlock();/解鎖5. 調(diào)試分析5.1不啟動生產(chǎn)者線程測試結(jié)果分析由于沒有啟動生產(chǎn)者線程，所以緩沖區(qū)為空，從而導(dǎo)致isBufferEmpty()信號為真，所以消費者線程不可訪問緩沖區(qū)取數(shù)。測試結(jié)果如圖5.1：圖5.1不啟動生產(chǎn)者線程測試結(jié)果5.2不啟動消費者線程測試結(jié)果分析因為沒啟動“消費者”而只啟動了“生產(chǎn)者”，所以在緩沖區(qū)未滿前“生產(chǎn)者”一直向緩沖區(qū)“生產(chǎn)”數(shù)據(jù)直到緩沖區(qū)滿