生產(chǎn)者與消費(fèi)者算法實(shí)現(xiàn)

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

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

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

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

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

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

7、流程圖4. 詳細(xì)設(shè)計(jì)4.1程序框架4.1.1生產(chǎn)者與消費(fèi)者的父類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;/兩個(gè)生產(chǎn)者取出數(shù)據(jù)的累加public static int consumerSum = 0;/

8、記錄消費(fèi)者取數(shù)次數(shù)public static int consumerCount = 0;/存放從緩沖區(qū)中取得的數(shù)據(jù)private static int consumerData;/定義線程名public String nameString;/線程互斥信號(hào)，值為 0 表示生產(chǎn)者進(jìn)程，值為 1 表示消費(fèi)者進(jìn)程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;/* 獲得互斥信號(hào) */public static int getMutex() return mutex;/* 設(shè)置互斥信號(hào) */public static void setMutex(int mutex) SuperThread.mutex = mutex;/* 判斷是否有線程訪問緩沖區(qū)，沒有則對(duì)線程進(jìn)行加鎖 */public boolean wait(int mutex)if (mutex = 1) return false;el

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

11、tex) && !isBufferEmpty() /判斷是否訪問緩沖區(qū)/加鎖bufferLock.lock();try /設(shè)置互斥信號(hào)/從緩沖區(qū)取數(shù)/將取數(shù)后的緩沖區(qū)置0/釋放互斥信號(hào)finally/解鎖bufferLock.unlock();/* 消費(fèi)者取得緩沖區(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è)置互斥信號(hào)/向緩沖區(qū)存數(shù)/釋放互斥信號(hào)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)者休眠時(shí)間private int producerDelay;/* 生產(chǎn)者構(gòu)造函數(shù) */public Producer(String name) super(name);/* 獲得生產(chǎn)者休眠時(shí)

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

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

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

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

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

18、者同樣也要用到輔助信號(hào)isBufferEmpty()來判斷緩沖區(qū)是否為空，只有緩沖區(qū)不為空且wait(mutex)為真是，消費(fèi)者才能對(duì)緩沖區(qū)進(jìn)行取數(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的個(gè)數(shù)來判斷，若緩/區(qū)0的個(gè)數(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的個(gè)數(shù)來判斷，若緩/區(qū)不為0的個(gè)數(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)者使用，在條件滿足的情況下對(duì)緩沖區(qū)進(jìn)行存數(shù)操作，而這個(gè)條件就是wait(mutex)=true && ! isBufferFull()=true。對(duì)于消費(fèi)者調(diào)用consume()方法同樣也要滿足這樣一個(gè)條件：wait(mutex)=true && ! isBufferEmpty()=duce()與consume()方法的主要代碼如下：/* 生產(chǎn)數(shù)，即向緩沖區(qū)中存數(shù)*/public void produce()if (wait(mutex) && !isBufferFull() bufferLock.lock

21、();/對(duì)該程序段加鎖，防止其他線程訪問緩沖區(qū)trysetMutex(1);/將線程互斥信號(hào)值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();/釋放互斥信號(hào)，將mutex設(shè)置為0finallybufferLock.unlock();/解鎖/* 消費(fèi)數(shù)，即在緩沖區(qū)中取數(shù) */public void consume()if (wa

22、it(mutex) && !isBufferEmpty() bufferLock.lock();/對(duì)該程序段加鎖，防止其他線程訪問緩沖區(qū)try setMutex(1);/將線程互斥信號(hào)值mutex設(shè)置為1，使之互斥int index = 0;/存放順序查找第一個(gè)為0的數(shù)的下擺int i;for (i = 0; i < buffer.capacity(); i+) /順序查找第一個(gè)為/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;/計(jì)算兩次取數(shù)/之和if (consumerCount = 2) System.out.println("消費(fèi)者取數(shù)之和為："+consumerSum);consumerSum = 0;consumerCount = 0;buffer.put(index-1, 0);/將已取過數(shù)的緩沖區(qū)重新置0consumerPrintBufferData();/輸出取數(shù)后的緩沖區(qū)signal();/釋放互斥信號(hào)，將mutex設(shè)置為0finallybufferLock.unlock();/解鎖5. 調(diào)試分析5.1不啟動(dòng)生產(chǎn)者線程測(cè)試結(jié)果分析由于沒有啟動(dòng)生產(chǎn)者線程，所以緩沖區(qū)為空，從而導(dǎo)致isBufferEmpty()信號(hào)為真，所以消費(fèi)者線程不可訪問緩沖區(qū)取數(shù)。測(cè)試結(jié)果如圖5.1：圖5.1不啟動(dòng)生產(chǎn)者線程測(cè)試結(jié)果5.2不啟動(dòng)消費(fèi)者線程測(cè)試結(jié)果分析因?yàn)闆]啟動(dòng)“消費(fèi)者”而只啟動(dòng)了“生產(chǎn)者”，所以在緩沖區(qū)未滿前“生產(chǎn)者”一直向緩沖區(qū)“生產(chǎn)”數(shù)據(jù)直到緩沖區(qū)滿