經典的程序同步問題-----生産者-消費者問題詳解

本文和接下來幾篇博文是對上篇文章（程序同步機制）的一次實踐，通過具體的例子來加深理論的了解，會用三個經典的程序同步問題來進行講解，并且會配有僞代碼和Java實踐（使用多線程模拟），深入的進行講解。

程序同步問題是一個非常重要且相當有趣的問題，因而吸引了很多學者對他進行研究，比如在前幾篇部落格中提到的老熟人迪傑斯特拉，由此也産生了一系列經典的程序同步問題，本文就選取其中較為代表性的生産者-消費者問題來進行學習，以幫助我們更好的了解程序同步的概念及實作方法。

生産者-消費者問題是互相合作的程序關系的一種抽象，例如，在輸入時，輸入程序是生産者，計算程序是消費者；而在輸出時，則計算程序是生産者，而列印程序是消費者，是以該問題有很大的代表性及實用價值。并且現在很多技術都使用到了，最典型的就是消息隊列。

本文主要是對經典程序同步問題的求解，是以在這裡先給出一個解題思路（僅代表個人意見、如有疑問，可評論區讨論）：

分析清楚題目涉及的程序間制約關系；
設定信号量（包括信号量的個數和初值，寫出信号量實體含義）；
給出程序相應程式的算法描述或流程控制，并把P、V操作加到程式适當之處。

1.問題描述

有一群生産者程序在生産産品，并将這些産品提供給消費者程序進行消費。為了使生産這程序與消費者程序能并發的執行，在兩者之間設定了一個具有n個緩沖區的緩沖池，生産者程序将其生産的産品放到一個緩沖區（緩沖池中的一個存儲機關）中；消費者程序可從一個緩沖區中取走産品去消費。

需要注意的是，盡管所有的生産者和消費者都是以異步的方式運作的，但是他們之間必須保持同步，既不允許消費者程序在緩沖區為空時去取産品，也不允許生産者程序在緩沖區已滿且産品尚未被取走時向緩沖區投放産品。

2.問題分析

緩沖池一次隻能有一個程序通路；
隻要緩沖池未滿，生産者就可以把産品送入緩沖區；
隻要緩沖池未空，消費者就可以從緩沖區中取走産品。

下圖是一個生産者與消費者程序執行的流程圖，從圖中我們可以很清晰的看到上述的三個程序間的關系，其中生産者和消費者中操作緩沖區都需要先進行申請，也就是我們說的進入區，操作完成後要執行釋放，也就是退出區，通過這樣來實作對緩沖池的互斥通路。通過圖中的貫通兩個程序的虛線來實作生産者和消費者的同步關系。

3.信号量設定

由于有界緩沖池是一個臨界資源，必須互斥使用，這時可以利用互斥信号量mutex實作諸程序對緩沖池的互斥使用。因為是互斥信号量，是以mutex初值為１。

另外，可以設定兩個同步信号量：一個表示緩沖池中空緩沖區的數目，用empty表示，初值為緩沖池的大小n；另一個表示已滿緩沖區的數目，即緩沖池中消息的數量，用full表示，初值為０。

除了信号量外，我們可以使用循環連結清單來表示有界緩沖池，假設緩沖池的大小為n，我們用buffer[n]來表示，另外還有兩個隊首指針in和隊尾指針out，其初值都為0。

4.記錄型信号量解決生産者-消費者問題

首先我們先使用記錄型信号量來解決生産者-消費者問題，根據上面的分析，我們先給出僞代碼：

int in=0,out=0;
//item為消息的結構體
item buffer[n];                       
semaphore mutex=1,empty=n,full=0;     //初始化信号量

void producer(){
do {
//生産者産生一條消息
producer an item nextp;
    ...
//判斷緩沖池中是否仍有空閑的緩沖區
P(empty);
//判斷是否可以進入臨界區（操作緩沖池）
P(mutex);
//向緩沖池中投放消息
buffer[in] = nextp;
//移動入隊指針
in = (in + 1) % n;
//退出臨界區，允許别的程序操作緩沖池
V(mutex);
//緩沖池中非空的緩沖區數量加1，可以喚醒等待的消費者程序
V(full);
  }while(true);
}

void consumer(){
do {
//判斷緩沖池中是否有非空的緩沖區（消息）
P(full); 
//判斷是否可以進入臨界區（操作緩沖池）
P(mutex);
//從緩沖池中取出消息
nextc = buffer[out];
//移動出隊指針
out = (out + 1) % n;
//退出臨界區，允許别的程序操作緩沖池
V(mutex);
//緩沖池中空緩沖區數量加1，可以喚醒等待的生産者程序
V(empty);
//消費消息
consumer the item in nextc;
    ...
  }while(true);
}

通過上面的僞代碼，我們可以看到，在每個程式中用于實作互斥的P(mutex)和V(mutex)必須成對的出現，并且要出現在同一個程式中；對于用于控制程序同步的信号量full和empty，其P、V操作也必須要成對的出現，但他們分别處于不同的程式之中。還有比較重要的就是，每個程式中的多個P操作順序不能颠倒，比如說生産者程序，應先執行對資源信号量的P操作–P(empty)，再執行對互斥信号量的P操作–P(mutex)，否則可能會因為持有了互斥鎖，但是沒有空閑的緩沖區而導緻生産者程序阻塞，但是别的程序又無法進入臨界區，導緻程序發生死鎖。

下面給出對應的Java 多線程的實作，為了簡單，臨界緩沖池我使用了一個長度為50的list來模拟，代碼如下：

/**
* 記錄型信号量
*/
static final Semaphore mutex = new Semaphore(1);

static List<Integer> buffer = new ArrayList<>();

static final Semaphore empty = new Semaphore(50);
static final Semaphore full = new Semaphore(0);     //資料定義

static Integer count = 0;

static class Producer extends Thread {
Producer(String name) {
super.setName(name);
  }

@Override
public void run() {
do {
try {
//判斷緩沖池中是否仍有空閑的緩沖區
empty.acquire();
//判斷是否可以進入臨界區（操作緩沖池）
mutex.acquire();
log.info("生産了一條消息：【{}】", count);
//向緩沖池中投放消息
buffer.add(count++);
//Thread.sleep(1000);
//釋放資源
full.release();
mutex.release();
      } catch (InterruptedException e) {
log.error("生産消息時産生異常！");
      }
    } while (true);
  }
}

static class Consumer extends Thread {
Consumer(String name) {
super.setName(name);
  }

@Override
public void run() {
do {
try {
//判斷緩沖池中是否仍有空閑的緩沖區
full.acquire(); 
//判斷是否可以進入臨界區（操作緩沖池）    
mutex.acquire();      
log.info("消費了一條消息：【{}】", buffer.remove(0));
//Thread.sleep(1000);
empty.release();
mutex.release();
      } catch (InterruptedException e) {
log.error("消費消息時産生異常！");
      }
    } while (true);
  }
}

public static void main(String[] args) {            //測試
Producer p1 = new Producer("p1");
Producer p2 = new Producer("p2");

Consumer c1 = new Consumer("c1");
Consumer c2 = new Consumer("c2");
p1.start();
p2.start();
c1.start();
c2.start();
}

5.使用AND型信号量解決生産者-消費者問題

對于AND型信号量，我們就不做過多的說明了，我們直接給出生産者-消費者問題的僞代碼解決，也沒有什麼變化，主要是信号量申請部分：

...                                   //定義信号量并初始化

void producer(){
do {
//生産者産生一條消息
producer an item nextp;
    ...
//判斷緩沖池中是否仍有空閑的緩沖區&&是否可以進入臨界區
Swait(empty, mutex);
//向緩沖池中投放消息
buffer[in] = nextp;
//移動入隊指針
in = (in + 1) % n;
//退出臨界區&&消息數量加1，可以喚醒等待的消費者程序
Ssignal(mutex, full);
  }while(true);
}

void consumer(){
do {
//判斷緩沖池中是否有消息&&是否可以進入臨界區
Swait(full, mutex);
//從緩沖池中取出消息
nextc = buffer[out];
//移動出隊指針
out = (out + 1) % n;
//退出臨界區&&緩沖池中空緩沖區數量加1，可以喚醒等待的生産者程序
Ssignal(mutex, empty);
//消費消息
consumer the item in nextc; 
    ...
  }while(true);
}

對應的Java代碼實作可以參看我的另一篇博文。

6.使用信号量集解決生産者-消費者問題

信号量集是對AND型型号量的一次擴充，其代碼不同的就在于wait操作可以一次申請多個資源和可以設定資源配置設定下限，下面是僞代碼：

...                                   //定義信号量并初始化

void producer(){
do {
producer an item nextp;
    ...
//判斷緩沖池中是否仍有空閑的緩沖區&&是否可以進入臨界區
Swait(empty, 1, 1, mutex, 1, 1);
//向緩沖池中投放消息
buffer[in] = nextp; 
//移動入隊指針
in = (in + 1) % n;
//退出臨界區&&消息數量加1，可以喚醒等待的消費者程序
Ssignal(mutex, 1, full, 1); 
  }while(true);
}

void consumer(){
do {
//判斷緩沖池中是否有消息&&是否可以進入臨界區
Swait(full, 1 ,1 , mutex, 1, 1); 
//從緩沖池中取出消息
nextc = buffer[out];
//移動出隊指針
out = (out + 1) % n;
//退出臨界區&&消息數量減1，可以喚醒等待的生産者程序
Ssignal(mutex, 1, empty, 1);
//消費消息
consumer the item in nextc;
    ...
  }while(true);
}

7.使用管程解決生産者-消費者問題

對管程，我們在前面的文章中詳細的進行了介紹，在這裡也使用管程來解決實際的問題，僞代碼如下(我們對于管程内部的過程進行簡單的描述)：

Monitor ProducerConsumer {
intem buffer[N];
int in=0,out=0;
condition notempty,notfull;//條件變量 非空和非滿
int count=0;//緩沖區中消息的數量

//放消息的過程
void put(item x){
//如果緩沖池滿了，則将線程阻塞到notfull中
if(count >= N){
cwait(notfull);
    }
//向緩沖池中投放消息
buffer[in] = nextp;
//移動入隊指針
in = (in + 1) % N;
//緩沖區中消息加一
count++;
//喚醒因為沒消息消費阻塞的消費者線程
signal(notempty);
  }

//取消息的過程
void get(item x){
//如果緩沖池為空，則将線程阻塞到notempty中
if(count <= 0){
cwait(notempty);
    }
x = buffer[out];//從緩沖池中取出消息
out = (out + 1) % n;//移動出隊指針
count--;//緩沖區中消息減一
signal(notfull);//喚醒因為沒空間存放消息阻塞的生産者線程
  }
}PC;

void producer(){
do {
//生産者産生一條消息
producer an item nextp;
    ...
PC.put(nextp);//将消息放入到緩沖池中
  }while(true);
}

void consumer(){
item x;
do {
PC.get(x);//從緩沖池中取出消息
consumer the item in nextc;//消費消息
    ...
  }while(true);
}

又到了分隔線以下，本文到此就結束了，本文内容全部都是由部落客自己進行整理并結合自身的了解進行總結，如果有什麼錯誤，還請批評指正。

本文的所有java代碼都已認證測試，對其中有什麼疑惑的，可以評論區留言，歡迎你的留言與讨論；另外原創不易，如果本文對你有所幫助，還請留下個贊，以表支援。

經典的程序同步問題-----生産者-消費者問題詳解

1.問題描述

2.問題分析

3.信号量設定

4.記錄型信号量解決生産者-消費者問題

5.使用AND型信号量解決生産者-消費者問題

6.使用信号量集解決生産者-消費者問題

7.使用管程解決生産者-消費者問題

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method