題目：生產者-消費者問題演算法的設計與實現 目 錄 1. 課題概述... 2 2. 合作分工... 2 3. 相關知識... 2 4. 系統分析... 2 5. 系統設計... 2 6. 系統運行測試界面截圖... 2 7. 總結與心得體會... 2 8. 源程式清單... 2 1. 課題概述 1.1 ...
題目：生產者-消費者問題演算法的設計與實現
目 錄
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 = 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 }
