題目：生產者-消費者問題演算法的設計與實作
目 錄
1. 課題概述... 2
2. 合作分工... 2
3. 相關知識... 2
4. 系統分析... 2
5. 系統設計... 2
6. 系統運行測驗界面截圖... 2
7. 總結與心得體會... 2
8. 源程式清單... 2
1. 課題概述
1.1設計的目的和要求；
在現代軟體業的發展下，互聯網用戶日漸增多，同一時間段會有非常的用戶訪問同一個服務器，用于用戶并發操作的同步運行概念應運而生，同步要求在同一個服務器內面對多個用戶能夠執行并發操作，對服務器資料進行讀取修改等操作，用戶大體上可以簡單概括為分為生產者和消費者，生產者負責產生資料，而消費者負責消耗資料，例如餐飲服務業中顧客和后廚之間的關系，也例如淘寶這類大型電商中，服務器是通過訊息佇列進行彼此之間的通訊的，訊息佇列和應用程式之間的架構關系也是生產消費者模型，生產者消費者問題演算法可以用來解決這一模型中資料通訊操作，
學習該演算法有助于我們深入了解程式在多執行緒下的并發操作和學習多執行緒中并發、同步相關的知識，鞏固對作業系統原理的理解，上機操作加深我們學生對知識點的掌握程度和鍛煉業務技能，
1.2開發環境，
作業系統：Windows 10 家庭中文版
JDK：1.8.0_171
編程實作軟體：Eclipse Java EE IDE Eclipse版本：Mars Release (4.5.0)
2. 合作分工
|
姓名 |
具體作業內容 |
|
我自己 |
（1）全部內容 （2） … |
|
|
（1） （2） … |
3. 相關知識
3.1行程同步機制的概念、準則
概念：在計算機中，有些資源是獨占的，一次只能一個行程進行使用，在行程同步中，由于采用了多道程式設計，記憶體中多道程式處于并發執行狀態，使得多個程式的執行結果可能會不可再現，程式這個概念已經無法描繪程式的并發執行，于是引入行程這個概念，
行程同步便是對多個相關行程在執行次序上的協調，使其并發執行的行程之間能夠按照一定的規則共享系統資源，并且很好的互相合作，從而使行程的執行結果具有可再現性，
準則：
- 空閑讓進：當沒有行程處于臨界區，可允許一個請求進入臨界區的行程立即進入自己的臨界區
- 忙則等待：當已經有行程進入了自己的臨界區，其他所有企圖進入臨界區的行程碧璽等待
- 有限等待：對請求訪問臨界資源的行程，應當保證行程在一定時間內進入自己的臨界區
- 讓權等待：當行程不能進去自己的臨界區，應當立即釋放處理機
3.2有界緩沖池、執行緒的概念
- 有界緩沖池：為了加快資料的訪問將需要訪問的資料放在緩沖池中，在生產者消費者問題中的有界緩沖池表示的是資料存放的地方，對于生產者，首先判斷緩沖池中是否有空的緩沖區，有則再判斷緩沖池是否可用，如可用則鎖住緩沖區，生產一個資料并放入緩沖區中；對于消費者說下判斷緩沖池中是否有有資源的緩沖區，如有則判斷緩沖池是否可用，如可用則鎖住緩沖區，從緩沖池中選取一個緩沖區拿取資料，有界緩沖池是指緩沖池中的緩沖區數量是有限的，對于生產者若有界緩沖池中沒有可用的緩沖區即緩沖池滿了即阻塞，對于消費者若緩沖池中沒有可用資源即緩沖區中位空即阻塞，
- 執行緒：行程是作業系統中行程保護、并發執行和資源分配的基本單位，作業系統分配資源以行程為基本單位，而執行緒是行程的組成部分，它代表了一條順序的執行流，執行緒只擁有一點在運行中必不可省的資源，執行緒定義為行程內一個執行單元或一個可調度物體，
3.3執行緒與行程的關系
- 行程即是一個擁有資源的獨立單位，它可以獨立分配地址空間，貯存和其他，又是一個可獨立調度和分派的基本單位，一個行程內有多個執行緒，
- 執行緒是行程的一部分，執行緒只擁有一點在運行中必不可省的資源，執行緒定義為行程內一個執行單元或一個可調度物體，執行緒占用資源少，使得產生、終止、切換執行緒比行程的花費少得多，執行緒機制也增加了通訊的有效性，執行緒之間的通訊時在同一個行程的地址空間內，共享主存和檔案，所以操作簡單，
3.4信號量機制的原理
- 信號量機制是一種有效的行程互斥同步工具，行程的互斥通過對信號量的操作來完成，
- 記錄型信號量結構：在此結構中信號量是代表資源物理物體的資料結構，且信號量的值只能同構兩個原子操作P、V操作來實作，分別代表申請資源和釋放資源
- 信號量的型別：
- 公用/互斥信號量：一組為需互斥共享臨界資源的并發行程設定，代表永久性的共享臨界資源，每個行程均可對它世家P、V操作，
- 專用/同步信號量：一組需同步協作完成任務并發行程設定，代表消耗性的專用資源，只有使用該資源的行程才能對其施加P、V操作，
- 信號量取值意義：
- Value > 0 :表示可供使用資源數
- Value = https://www.cnblogs.com/ZKU-CZB/archive/2023/06/12/0 : 表示資源已經被占用，沒有其他行程在等待
- Value < 0 : 表示資源已被占用，還有n個行程在因等待資源而阻塞
- 信號量機制實作行程同步所需遵循規則，并發執行行程為C、P：
- 只有當行程C把資料送入Buffer后，P行程才能從Buffer中取出資料，否則行程P只能等待，
- 只有當P行程從Buffer取走資料后，C行程才能將新產生的資料再存入道Buffer中去，否則C行程只能等待，
4. 系統分析
4.1生產者-消費者問題原理
1) 生產者-消費者問題是最著名的同步問題，用以演示信號量機制運行，描述的是有一組生產者[P1,P2,P3…],一組消費者[C1,C2,C3…],他們共享一個有界緩沖池，生產者向緩沖池中存放資料，消費者從緩沖池中拿取資料，生產者-消費者問題是許多需要互相合作行程的一種抽象，程序如圖所示：
作圖 1 生產者-消費者
2) 行程同步原理：假設緩沖池中有n個緩沖區，每個緩沖區只能存方一個資料，由于緩沖池是臨界資源，只能允許一個行程對其行程操作也就是說只能允許一個生產者存放資源或者一個消費者拿取資料，這說明生產者之間、生產者和消費者之間、消費者之間互斥使用緩沖池，故設定互斥信號量mutex，代表緩沖池資源，初值1；偽代碼如圖：
作圖 2 生產者消費者偽代碼
3) 這樣我們就實作了行程間對臨界資源的互斥訪問，但由于緩沖池是有界的，所以我們還需要對緩沖池中的緩沖區中具有資源進行判斷，首先生產者和消費者之間需要滿足以下兩個同步條件：
- 只有在緩沖池中至少有一個緩沖區已存入訊息后，消費者才能從中提取訊息，否則消費者必須等待，
- 只有緩沖池中至少有一個緩沖區是空時，生產者才能把訊息放入緩沖區，否則生產者必須等待，
4) 對于第一個同步條件，設定信號量full，代表緩沖池中有資源的緩沖區的數目，對于第二個同步條件，設定信號量empty，代表緩沖池中沒有資源的慷訓沖區的數目，
- 對于生產者行程在存放資料之前需要申請資源，即是否empty>0，若是則可以繼續申請互斥信號量mutex，如果否的話說明當前緩沖池中沒有空的緩沖區，即生產滿了需要阻塞，
- 對于消費者行程在消費資料之前需要申請資源，即是否full>0，若是則可以繼續申請互斥信號量判斷是否可以訪問緩沖池，若為否則說明緩沖池中沒有帶有資料的緩沖區，此時需要消費者阻塞，
作圖 3 生產消費者并發執行偽代碼
5. 系統設計
5.1系統中主要資料結構介紹
演算法分為生產者類、消費者類、緩沖buffer類
生產者類繼承執行緒Thread，生產者類帶有一個buffer是與其他行程共享的緩沖類，在生產者類的run(即執行緒啟動)函式中，使用while(true)無限次回圈方法體，方法體中是呼叫buffer的add()函式，代表對緩沖池進行生產資料并存放操作，具體的信號量的判斷全部都設定道緩沖池buffer類中，隨后執行緒休眠，這樣的設計目的是簡化代碼，生產者和消費者都是如此設計，提升代碼簡潔度和可讀性，
消費者類與生產者類如出一轍，帶有緩沖池buffer類與其他行程共享，在run()函式中呼叫buffer類的poll()方法，代表對緩沖池進行消費操作，具體的信號量判斷在buffer中進行，
Buffer緩沖池類，帶有用戶輸入的最大緩沖區數量MAX，緩沖區陣列resource[]，空的緩沖區數量empty=MAX，帶有資源的緩沖區數量full=0,代表互斥信號量mutex，以及代表以及生產了第幾個資源nElems，在構造方法中對buffer類初始化，resource容量大小設定為MAX+1，方便計算與直觀表達，在Buffer類中對add() 、poll()方法使用關鍵字synchronized進行加鎖，synchronized是一種同步鎖，是把該方法與其他呼叫此方法的行程之間是互斥關系，當有一個行程成功呼叫了該方法即上鎖，其他行程企圖呼叫該方法會阻塞，也就是說，add() 、poll()方法作為原子操作，構建了一個互斥使用的臨界資源，一次只能由一個行程進行add() 、poll()操作，相當于只能由一個行程進入緩沖池，
5.2程式流程圖及說明
作圖 4 程式執行流程
作圖 5 生產者進行生產操作流程【即呼叫add()】
作圖 6 消費者進行消費操作【即呼叫poll(0】
6. 系統運行測驗界面截圖
6.1用戶輸入第1組初始化資料
輸入資料順序為： 生產者數目、消費者數目、緩沖區數目：
作圖 7
預期結果為，在一般情況下運行一段時間后，由于生產者數量多而出現阻塞，但又由于緩沖區數量多于生產者數量所以出現生產者阻塞會比較晚，且有可能在程式開始時就啟動了消費者行程造成次奧非洲阻塞，
6.2第1組資料輸出情況截圖
可以看到除去一開始呼叫到了消費者行程導致消費者進行阻塞外，在運行了一段時候后才出現了生產者行程的阻塞，且后續出現消費者阻塞的概率大大降低，
作圖 8
6.3用戶輸入第2組初始化資料
輸入資料順序為： 生產者數目、消費者數目、緩沖區數目：
作圖 9
預期結果：生產者數量接近緩沖區數量，所以生產者出現阻塞的該路會更大，而對于消費者來說除了在程式開始運行的時候呼叫了消費者行程導致的阻塞外，其他情況下阻塞的概率很低，
6.4第2組資料輸出情況截圖
可以看到在程式運行一段時間后生產者出現阻塞概率很更大，而消費者在后面幾乎不會出現阻塞，
作圖 10
6.5用戶輸入第3組初始化資料
輸入資料順序為： 生產者數目、消費者數目、緩沖區數目：
作圖 11
消費者數量接近緩沖區數量，預期消費者行程會多次出現阻塞，而對于生產者來說出現阻塞的概率很低，
6.6第3組資料輸出情況截圖
可以看到消費者出現多次阻塞，而對于生產者來說出現阻塞的概率很小，
作圖 12
6.7其他界面，
作圖 13
7. 總結與心得體會
7.1 深刻學習了在計算機中行程并發執行的機制，學習了其中運用的信號量機制，
7.2 掌握了編程實作了多執行緒并發操作，學習了程式同步相關的知識，
7.3 在創建生產者和消費者行程時同時傳入行程的編號，在輸出行程操作時顯示行程編號，這樣會更加直觀地反應出各個執行緒的運行狀態和了解行程同步的運行，
8. 源程式清單
1 public class Test01 { 2 3 System.out.println("----------生產者："+ a + " 消費者： "+b +" 緩沖區："+max + "----------"); 4 5 Buffer buffer = new Buffer(max); 6 7 for (int i = 0; i < a; i++) { 8 9 new Producer(buffer,i).start();//創建行程 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;//緩沖區 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);//生產 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);//消費 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){//加鎖，方法是生產者和消費者共有的，保障并發執行 106 107 try { 108 109 if(empty != 0){//有空盒子 110 111 if(!mutex){//可用 112 113 int pos = findEmpty();//隨機找到一個可用的位置 114 115 nElems++; 116 117 empty--;//P（empty） 118 119 full++; //V（full） 120 121 resource[pos] = nElems; 122 123 System.out.println("生產者#” +i+”生產了第 "+nElems+" 個面包放入第 "+pos+" 個位置，"); 124 125 Thread.sleep((long)rand.nextInt(2000 - MIN + 1) + MIN); 126 127 notify();//喚醒其他行程 128 129 }else{ 130 131 wait();//阻塞 132 133 } 134 135 }else{ 136 137 System.out.println("生產者#”+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("消費者#”+i+”消費了第 "+resource[pos]+" 個面包放回第 "+pos+" 個空盒子，"); 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("消費者#”+i+”阻塞!"); 184 185 wait(); 186 187 } 188 189 } catch (InterruptedException e) { 190 191 e.printStackTrace(); 192 193 } 194 195 } 196 197 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/554956.html
標籤：其他
上一篇：Java XML教程_編程入門自學教程_菜鳥教程-免費教程分享
下一篇：返回列表