題目：生產(chǎn)者-消費(fèi)者問題算法的設(shè)計(jì)與實(shí)現(xiàn)
目???? 錄
1. 課題概述... 2
2. 合作分工... 2
3. 相關(guān)知識... 2
4. 系統(tǒng)分析... 2
5. 系統(tǒng)設(shè)計(jì)... 2
6. 系統(tǒng)運(yùn)行測試界面截圖... 2
7. 總結(jié)與心得體會... 2
8. 源程序清單... 2
?
1.??? 課題概述
1.1設(shè)計(jì)的目的和要求；
在現(xiàn)代軟件業(yè)的發(fā)展下，互聯(lián)網(wǎng)用戶日漸增多，同一時(shí)間段會有非常的用戶訪問同一個(gè)服務(wù)器，用于用戶并發(fā)操作的同步運(yùn)行概念應(yīng)運(yùn)而生，同步要求在同一個(gè)服務(wù)器內(nèi)面對多個(gè)用戶能夠執(zhí)行并發(fā)操作，對服務(wù)器數(shù)據(jù)進(jìn)行讀取修改等操作，用戶大體上可以簡單概括為分為生產(chǎn)者和消費(fèi)者，生產(chǎn)者負(fù)責(zé)產(chǎn)生數(shù)據(jù)，而消費(fèi)者負(fù)責(zé)消耗數(shù)據(jù)，例如餐飲服務(wù)業(yè)中顧客和后廚之間的關(guān)系，也例如淘寶這類大型電商中，服務(wù)器是通過消息隊(duì)列進(jìn)行彼此之間的通訊的，消息隊(duì)列和應(yīng)用程序之間的架構(gòu)關(guān)系也是生產(chǎn)消費(fèi)者模型，生產(chǎn)者消費(fèi)者問題算法可以用來解決這一模型中數(shù)據(jù)通訊操作。
學(xué)習(xí)該算法有助于我們深入了解程序在多線程下的并發(fā)操作和學(xué)習(xí)多線程中并發(fā)、同步相關(guān)的知識，鞏固對操作系統(tǒng)原理的理解。上機(jī)操作加深我們學(xué)生對知識點(diǎn)的掌握程度和鍛煉業(yè)務(wù)技能。
1.2開發(fā)環(huán)境。
操作系統(tǒng)：Windows 10 家庭中文版
JDK：1.8.0_171
編程實(shí)現(xiàn)軟件：Eclipse Java EE IDE ?Eclipse版本：Mars Release (4.5.0)
2.??? 合作分工
|
姓名 |
具體工作內(nèi)容 |
|
我自己 |
（1）全部內(nèi)容 （2） … |
|
? |
（1） （2） … |
?3.??? 相關(guān)知識
3.1進(jìn)程同步機(jī)制的概念、準(zhǔn)則
概念：在計(jì)算機(jī)中，有些資源是獨(dú)占的，一次只能一個(gè)進(jìn)程進(jìn)行使用。在進(jìn)程同步中，由于采用了多道程序設(shè)計(jì)，內(nèi)存中多道程序處于并發(fā)執(zhí)行狀態(tài)，使得多個(gè)程序的執(zhí)行結(jié)果可能會不可再現(xiàn)，程序這個(gè)概念已經(jīng)無法描繪程序的并發(fā)執(zhí)行，于是引入進(jìn)程這個(gè)概念。
進(jìn)程同步便是對多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，使其并發(fā)執(zhí)行的進(jìn)程之間能夠按照一定的規(guī)則共享系統(tǒng)資源，并且很好的互相合作，從而使進(jìn)程的執(zhí)行結(jié)果具有可再現(xiàn)性。
準(zhǔn)則：
- 空閑讓進(jìn)：當(dāng)沒有進(jìn)程處于臨界區(qū)，可允許一個(gè)請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)
- 忙則等待：當(dāng)已經(jīng)有進(jìn)程進(jìn)入了自己的臨界區(qū)，其他所有企圖進(jìn)入臨界區(qū)的進(jìn)程碧璽等待
- 有限等待：對請求訪問臨界資源的進(jìn)程，應(yīng)當(dāng)保證進(jìn)程在一定時(shí)間內(nèi)進(jìn)入自己的臨界區(qū)
- 讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)去自己的臨界區(qū)，應(yīng)當(dāng)立即釋放處理機(jī)
3.2有界緩沖池、線程的概念
- 有界緩沖池：為了加快數(shù)據(jù)的訪問將需要訪問的數(shù)據(jù)放在緩沖池中，在生產(chǎn)者消費(fèi)者問題中的有界緩沖池表示的是數(shù)據(jù)存放的地方。對于生產(chǎn)者，首先判斷緩沖池中是否有空的緩沖區(qū)，有則再判斷緩沖池是否可用，如可用則鎖住緩沖區(qū)，生產(chǎn)一個(gè)數(shù)據(jù)并放入緩沖區(qū)中；對于消費(fèi)者說下判斷緩沖池中是否有有資源的緩沖區(qū)，如有則判斷緩沖池是否可用，如可用則鎖住緩沖區(qū)，從緩沖池中選取一個(gè)緩沖區(qū)拿取數(shù)據(jù)。有界緩沖池是指緩沖池中的緩沖區(qū)數(shù)量是有限的，對于生產(chǎn)者若有界緩沖池中沒有可用的緩沖區(qū)即緩沖池滿了即阻塞，對于消費(fèi)者若緩沖池中沒有可用資源即緩沖區(qū)中位空即阻塞。
- 線程：進(jìn)程是操作系統(tǒng)中進(jìn)程保護(hù)、并發(fā)執(zhí)行和資源分配的基本單位，操作系統(tǒng)分配資源以進(jìn)程為基本單位。而線程是進(jìn)程的組成部分，它代表了一條順序的執(zhí)行流。線程只擁有一點(diǎn)在運(yùn)行中必不可省的資源。線程定義為進(jìn)程內(nèi)一個(gè)執(zhí)行單元或一個(gè)可調(diào)度實(shí)體。
3.3線程與進(jìn)程的關(guān)系
- 進(jìn)程即是一個(gè)擁有資源的獨(dú)立單位，它可以獨(dú)立分配地址空間，貯存和其他，又是一個(gè)可獨(dú)立調(diào)度和分派的基本單位，一個(gè)進(jìn)程內(nèi)有多個(gè)線程。
- 線程是進(jìn)程的一部分，線程只擁有一點(diǎn)在運(yùn)行中必不可省的資源。線程定義為進(jìn)程內(nèi)一個(gè)執(zhí)行單元或一個(gè)可調(diào)度實(shí)體。線程占用資源少，使得產(chǎn)生、終止、切換線程比進(jìn)程的花費(fèi)少得多，線程機(jī)制也增加了通訊的有效性。線程之間的通訊時(shí)在同一個(gè)進(jìn)程的地址空間內(nèi)，共享主存和文件，所以操作簡單。
3.4信號量機(jī)制的原理
- 信號量機(jī)制是一種有效的進(jìn)程互斥同步工具。進(jìn)程的互斥通過對信號量的操作來完成。
- 記錄型信號量結(jié)構(gòu)：在此結(jié)構(gòu)中信號量是代表資源物理實(shí)體的數(shù)據(jù)結(jié)構(gòu)，且信號量的值只能同構(gòu)兩個(gè)原子操作P、V操作來實(shí)現(xiàn)，分別代表申請資源和釋放資源
- 信號量的類型：
- 公用/互斥信號量：一組為需互斥共享臨界資源的并發(fā)進(jìn)程設(shè)置，代表永久性的共享臨界資源，每個(gè)進(jìn)程均可對它世家P、V操作。
- 專用/同步信號量：一組需同步協(xié)作完成任務(wù)并發(fā)進(jìn)程設(shè)置，代表消耗性的專用資源，只有使用該資源的進(jìn)程才能對其施加P、V操作。
- 信號量取值意義：
- Value > 0 :表示可供使用資源數(shù)
- Value = 0 : 表示資源已經(jīng)被占用，沒有其他進(jìn)程在等待
- Value < 0 : 表示資源已被占用，還有n個(gè)進(jìn)程在因等待資源而阻塞
- 信號量機(jī)制實(shí)現(xiàn)進(jìn)程同步所需遵循規(guī)則，并發(fā)執(zhí)行進(jìn)程為C、P：
- 只有當(dāng)進(jìn)程C把數(shù)據(jù)送入Buffer后，P進(jìn)程才能從Buffer中取出數(shù)據(jù)，否則進(jìn)程P只能等待。
- 只有當(dāng)P進(jìn)程從Buffer取走數(shù)據(jù)后，C進(jìn)程才能將新產(chǎn)生的數(shù)據(jù)再存入道Buffer中去，否則C進(jìn)程只能等待。
?4.??? 系統(tǒng)分析
4.1生產(chǎn)者-消費(fèi)者問題原理
1)????? 生產(chǎn)者-消費(fèi)者問題是最著名的同步問題，用以演示信號量機(jī)制運(yùn)行。描述的是有一組生產(chǎn)者[P1,P2,P3…],一組消費(fèi)者[C1,C2,C3…],他們共享一個(gè)有界緩沖池，生產(chǎn)者向緩沖池中存放數(shù)據(jù)，消費(fèi)者從緩沖池中拿取數(shù)據(jù)，生產(chǎn)者-消費(fèi)者問題是許多需要互相合作進(jìn)程的一種抽象。過程如圖所示：
?
作圖 1 生產(chǎn)者-消費(fèi)者?
2)????? 進(jìn)程同步原理：假設(shè)緩沖池中有n個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)只能存方一個(gè)數(shù)據(jù)。由于緩沖池是臨界資源，只能允許一個(gè)進(jìn)程對其進(jìn)程操作也就是說只能允許一個(gè)生產(chǎn)者存放資源或者一個(gè)消費(fèi)者拿取數(shù)據(jù)。這說明生產(chǎn)者之間、生產(chǎn)者和消費(fèi)者之間、消費(fèi)者之間互斥使用緩沖池。故設(shè)置互斥信號量mutex，代表緩沖池資源，初值1；偽代碼如圖：
?
作圖 2 生產(chǎn)者消費(fèi)者偽代碼?
3)????? 這樣我們就實(shí)現(xiàn)了進(jìn)程間對臨界資源的互斥訪問，但由于緩沖池是有界的，所以我們還需要對緩沖池中的緩沖區(qū)中具有資源進(jìn)行判斷。首先生產(chǎn)者和消費(fèi)者之間需要滿足以下兩個(gè)同步條件：
- 只有在緩沖池中至少有一個(gè)緩沖區(qū)已存入消息后，消費(fèi)者才能從中提取消息，否則消費(fèi)者必須等待。
- 只有緩沖池中至少有一個(gè)緩沖區(qū)是空時(shí)，生產(chǎn)者才能把消息放入緩沖區(qū)，否則生產(chǎn)者必須等待。
4)????? 對于第一個(gè)同步條件，設(shè)置信號量full，代表緩沖池中有資源的緩沖區(qū)的數(shù)目，對于第二個(gè)同步條件，設(shè)置信號量empty，代表緩沖池中沒有資源的空緩沖區(qū)的數(shù)目。
- 對于生產(chǎn)者進(jìn)程在存放數(shù)據(jù)之前需要申請資源，即是否empty>0，若是則可以繼續(xù)申請互斥信號量mutex，如果否的話說明當(dāng)前緩沖池中沒有空的緩沖區(qū)，即生產(chǎn)滿了需要阻塞。
- 對于消費(fèi)者進(jìn)程在消費(fèi)數(shù)據(jù)之前需要申請資源，即是否full>0，若是則可以繼續(xù)申請互斥信號量判斷是否可以訪問緩沖池，若為否則說明緩沖池中沒有帶有數(shù)據(jù)的緩沖區(qū)，此時(shí)需要消費(fèi)者阻塞。
?
作圖 3 生產(chǎn)消費(fèi)者并發(fā)執(zhí)行偽代碼?
5.??? 系統(tǒng)設(shè)計(jì)
5.1系統(tǒng)中主要數(shù)據(jù)結(jié)構(gòu)介紹
算法分為生產(chǎn)者類、消費(fèi)者類、緩沖buffer類
生產(chǎn)者類繼承線程Thread，生產(chǎn)者類帶有一個(gè)buffer是與其他進(jìn)程共享的緩沖類。在生產(chǎn)者類的run(即線程啟動)函數(shù)中，使用while(true)無限次循環(huán)方法體，方法體中是調(diào)用buffer的add()函數(shù)，代表對緩沖池進(jìn)行生產(chǎn)數(shù)據(jù)并存放操作，具體的信號量的判斷全部都設(shè)置道緩沖池buffer類中，隨后線程休眠。這樣的設(shè)計(jì)目的是簡化代碼，生產(chǎn)者和消費(fèi)者都是如此設(shè)計(jì)，提升代碼簡潔度和可讀性。
消費(fèi)者類與生產(chǎn)者類如出一轍，帶有緩沖池buffer類與其他進(jìn)程共享，在run()函數(shù)中調(diào)用buffer類的poll()方法，代表對緩沖池進(jìn)行消費(fèi)操作，具體的信號量判斷在buffer中進(jìn)行。
Buffer緩沖池類，帶有用戶輸入的最大緩沖區(qū)數(shù)量MAX，緩沖區(qū)數(shù)組resource[]，空的緩沖區(qū)數(shù)量empty=MAX，帶有資源的緩沖區(qū)數(shù)量full=0,代表互斥信號量mutex，以及代表以及生產(chǎn)了第幾個(gè)資源nElems。在構(gòu)造方法中對buffer類初始化，resource容量大小設(shè)置為MAX+1，方便計(jì)算與直觀表達(dá)。在Buffer類中對add() 、poll()方法使用關(guān)鍵字synchronized進(jìn)行加鎖，synchronized是一種同步鎖，是把該方法與其他調(diào)用此方法的進(jìn)程之間是互斥關(guān)系，當(dāng)有一個(gè)進(jìn)程成功調(diào)用了該方法即上鎖，其他進(jìn)程企圖調(diào)用該方法會阻塞。也就是說，add() 、poll()方法作為原子操作，構(gòu)建了一個(gè)互斥使用的臨界資源，一次只能由一個(gè)進(jìn)程進(jìn)行add() 、poll()操作，相當(dāng)于只能由一個(gè)進(jìn)程進(jìn)入緩沖池。
5.2程序流程圖及說明
?
作圖 4 程序執(zhí)行流程
?
作圖 5 生產(chǎn)者進(jìn)行生產(chǎn)操作流程【即調(diào)用add()】
?
?
作圖 6 消費(fèi)者進(jìn)行消費(fèi)操作【即調(diào)用poll(0】
?6.??? 系統(tǒng)運(yùn)行測試界面截圖
6.1用戶輸入第1組初始化數(shù)據(jù)
輸入數(shù)據(jù)順序?yàn)椋?生產(chǎn)者數(shù)目、消費(fèi)者數(shù)目、緩沖區(qū)數(shù)目：
作圖 7
?
預(yù)期結(jié)果為，在一般情況下運(yùn)行一段時(shí)間后，由于生產(chǎn)者數(shù)量多而出現(xiàn)阻塞，但又由于緩沖區(qū)數(shù)量多于生產(chǎn)者數(shù)量所以出現(xiàn)生產(chǎn)者阻塞會比較晚，且有可能在程序開始時(shí)就啟動了消費(fèi)者進(jìn)程造成次奧非洲阻塞。
6.2第1組數(shù)據(jù)輸出情況截圖
可以看到除去一開始調(diào)用到了消費(fèi)者進(jìn)程導(dǎo)致消費(fèi)者進(jìn)行阻塞外，在運(yùn)行了一段時(shí)候后才出現(xiàn)了生產(chǎn)者進(jìn)程的阻塞，且后續(xù)出現(xiàn)消費(fèi)者阻塞的概率大大降低。
作圖 8
?
6.3用戶輸入第2組初始化數(shù)據(jù)
輸入數(shù)據(jù)順序?yàn)椋?生產(chǎn)者數(shù)目、消費(fèi)者數(shù)目、緩沖區(qū)數(shù)目：
作圖 9
?
預(yù)期結(jié)果：生產(chǎn)者數(shù)量接近緩沖區(qū)數(shù)量，所以生產(chǎn)者出現(xiàn)阻塞的該路會更大，而對于消費(fèi)者來說除了在程序開始運(yùn)行的時(shí)候調(diào)用了消費(fèi)者進(jìn)程導(dǎo)致的阻塞外，其他情況下阻塞的概率很低。
6.4第2組數(shù)據(jù)輸出情況截圖
可以看到在程序運(yùn)行一段時(shí)間后生產(chǎn)者出現(xiàn)阻塞概率很更大，而消費(fèi)者在后面幾乎不會出現(xiàn)阻塞。
作圖 10
?
6.5用戶輸入第3組初始化數(shù)據(jù)
輸入數(shù)據(jù)順序?yàn)椋?生產(chǎn)者數(shù)目、消費(fèi)者數(shù)目、緩沖區(qū)數(shù)目：
作圖 11
?
消費(fèi)者數(shù)量接近緩沖區(qū)數(shù)量，預(yù)期消費(fèi)者進(jìn)程會多次出現(xiàn)阻塞，而對于生產(chǎn)者來說出現(xiàn)阻塞的概率很低。
6.6第3組數(shù)據(jù)輸出情況截圖
可以看到消費(fèi)者出現(xiàn)多次阻塞，而對于生產(chǎn)者來說出現(xiàn)阻塞的概率很小。
作圖 12
?
6.7其他界面。
作圖 13
?7.??? 總結(jié)與心得體會
7.1 深刻學(xué)習(xí)了在計(jì)算機(jī)中進(jìn)程并發(fā)執(zhí)行的機(jī)制，學(xué)習(xí)了其中運(yùn)用的信號量機(jī)制。
7.2 掌握了編程實(shí)現(xiàn)了多線程并發(fā)操作，學(xué)習(xí)了程序同步相關(guān)的知識。
7.3 在創(chuàng)建生產(chǎn)者和消費(fèi)者進(jìn)程時(shí)同時(shí)傳入進(jìn)程的編號，在輸出進(jìn)程操作時(shí)顯示進(jìn)程編號，這樣會更加直觀地反應(yīng)出各個(gè)線程的運(yùn)行狀態(tài)和了解進(jìn)程同步的運(yùn)行。
8.??? 源程序清單文章來源：http://www.zghlxwxcb.cn/news/detail-479942.html
1 public class Test01 { 2 3 System.out.println("----------生產(chǎn)者："+ a + " 消費(fèi)者： "+b +" 緩沖區(qū)："+max + "----------"); 4 5 Buffer buffer = new Buffer(max); 6 7 for (int i = 0; i < a; i++) { 8 9 new Producer(buffer,i).start();//創(chuàng)建進(jìn)程 10 11 } 12 13 for (int i = 0; i < b; i++) { 14 15 new Consumer(buffer,i).start(); 16 17 } 18 19 } 20 21 class Producer extends Thread{ 22 23 private boolean mutex; 24 25 private Buffer buffer;//緩沖區(qū) 26 27 Random rand = new Random(); 28 29 public Producer(Buffer buffer,int i) { 30 31 this.buffer = buffer; 32 33 this.i = i; 34 35 } 36 37 @Override 38 39 public void run() { 40 41 super.run(); 42 43 while(true){ 44 45 try { 46 47 buffer.add(i);//生產(chǎn) 48 49 Thread.sleep((long)rand.nextInt(1000 - 1 + 1) + 1); 50 51 } catch (InterruptedException e) { 52 53 e.printStackTrace(); 54 55 } 56 57 } 58 59 } 60 61 } 62 63 class Consumer extends Thread{ 64 65 private boolean mutex; 66 67 private Buffer buffer; 68 69 Random rand = new Random(); 70 71 public Consumer(Buffer buffer,int i) { 72 73 this.buffer = buffer;this.i=I; 74 75 } 76 77 @Override 78 79 public void run() { 80 81 super.run(); 82 83 while(true){ 84 85 try { 86 87 buffer.poll(i);//消費(fèi) 88 89 Thread.sleep((long)rand.nextInt(1000 - 1 + 1) + 1); 90 91 } catch (InterruptedException e) { 92 93 e.printStackTrace(); 94 95 } 96 97 } 98 99 } 100 101 } 102 103 class Buffer extends Thread{ 104 105 public synchronized void add(int i){//加鎖，方法是生產(chǎn)者和消費(fèi)者共有的，保障并發(fā)執(zhí)行 106 107 try { 108 109 if(empty != 0){//有空盒子 110 111 if(!mutex){//可用 112 113 int pos = findEmpty();//隨機(jī)找到一個(gè)可用的位置 114 115 nElems++; 116 117 empty--;//P（empty） 118 119 full++; //V（full） 120 121 resource[pos] = nElems; 122 123 System.out.println("生產(chǎn)者#” +i+”生產(chǎn)了第 "+nElems+" 個(gè)面包放入第 "+pos+" 個(gè)位置。"); 124 125 Thread.sleep((long)rand.nextInt(2000 - MIN + 1) + MIN); 126 127 notify();//喚醒其他進(jìn)程 128 129 }else{ 130 131 wait();//阻塞 132 133 } 134 135 }else{ 136 137 System.out.println("生產(chǎn)者#”+i+”阻塞！"); 138 139 wait();//阻塞 140 141 } 142 143 } catch (InterruptedException e) { 144 145 e.printStackTrace(); 146 147 } 148 149 } 150 151 public synchronized void poll(){ 152 153 try { 154 155 //synchronized(resource){ 156 157 if(full != 0){//有面包 158 159 if(!mutex){ 160 161 int pos = findFull(); 162 163 empty++;//V(empty) 164 165 full--;//V(full) 166 167 System.out.println("消費(fèi)者#”+i+”消費(fèi)了第 "+resource[pos]+" 個(gè)面包放回第 "+pos+" 個(gè)空盒子。"); 168 169 resource[pos] = 0;// 170 171 Thread.sleep((long)rand.nextInt(2000 - MIN + 1) + MIN); 172 173 notify(); 174 175 }else{ 176 177 wait(); 178 179 } 180 181 }else{ 182 183 System.out.println("消費(fèi)者#”+i+”阻塞!"); 184 185 wait(); 186 187 } 188 189 } catch (InterruptedException e) { 190 191 e.printStackTrace(); 192 193 } 194 195 } 196 197 }
?文章來源地址http://www.zghlxwxcb.cn/news/detail-479942.html
到了這里，關(guān)于【課設(shè)】生產(chǎn)者-消費(fèi)者問題算法 的設(shè)計(jì)與實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
