前兩天寫了個簡單的線程池，結果在處理線程的同步互斥上花了不少時間，覺得有必要把以前學習的知識再過一遍，這次主要復習的是幾個非常經典的同步互斥問題。
一、生產者消費者問題
問題描述：
只有緩沖區沒滿時，生產者才能把消息放入到緩沖區，否則必須等待；只有緩沖區不空時，消費者才能從中取出消息，否則必須等待。由於緩沖區是臨界資源，它只允許一個生產者放入消息，或者一個消費者從中取出消息。
問題分析：
1、關系分析：生產者和消費者對緩沖區互斥訪問是互斥關系，同時生產者和消費者又是一個相互協作的關系，只有生產者生產之後，消費者才能消費，它們也是同步關系。
2、整理思路：因為只有生產者和消費者兩個線程，且這兩個線程存在著互斥關系和同步關系。那麼需要解決的是互斥和同步的PV操作的位置。
3、信號量設置：互斥鎖mutex用於控制互斥訪問緩沖池；信號量full用於記錄當前緩沖池中“滿”緩沖區數，初值為 0；信號量empty用於記錄當前緩沖池中“空”緩沖區數，初值為n。
#define N 10
sem_t empty;//空閒緩沖區信號量，初始化為N
sem_t full;//滿緩沖區信號量，初始化為0
pthread_mutex_t mutex;//對緩沖區產品互斥訪問
int product_num = 0;//緩沖區產品數目
void *producter_f(void *arg)
{
while (1)
{
usleep(1000000);
printf("produce an item\n");//生產數據
sem_wait(&empty);//獲取空緩沖區單元
pthread_mutex_lock(&mutex);//進入臨界區
product_num++;//將數據放入緩沖區
printf("producter: the num of product is %d\n", product_num);
pthread_mutex_unlock(&mutex);//離開臨界區
sem_post(&full);//滿緩沖區加1
}
}
void *consumer_f(void *arg)
{
while (1)
{
sem_wait(&full);//獲取空緩沖區單元
pthread_mutex_lock(&mutex);//進入臨界區
product_num--;
printf("consumer: the num of product is %d\n", product_num);
pthread_mutex_unlock(&mutex);//離開臨界區
sem_post(&empty);//空緩沖區加1
usleep(5000000);
printf("consume an item\n");//消費數據
}
}運行結果：
該類問題要注意對緩沖區大小為n的處理，當緩沖區中有空時便可對empty變量執行P 操作，一旦取走一個產品便要執行V操作以釋放空閒區。對empty和full變量的P操作必須放在對mutex的P操作之前。如果生產者線程先執行P(mutex)，然後執行P(empty)，消費者執行P(mutex),然後執行P(fall),這樣可不可以？答案是否定的。設想生產者線程已經將緩沖區放滿，消費者線程並沒有取產品，即empty = 0，當下次仍然是生產者線程運行時，它先執行P(mutex)封鎖信號量，再執行P(empty)時將被阻塞，希望消費者取出產品後將其喚醒。輪到消費者線程運行時，它先執行P(mutex)，然而由於生產者線程已經封鎖mutex信號量，消費者線程也會被阻塞，這樣一來生產者、消費者線程都將阻塞，都指望對方喚醒自己，陷入了無休止的等待。同理，如果消費者線程已經將緩沖區取空，即 full = 0,下次如果還是消費者先運行，也會出現類似的死鎖。不過生產者釋放信號量時，mutex、full先釋放哪一個無所謂，消費者先釋放mutex還是empty都可以。
二、讀者-寫者問題
問題描述：
有讀者和寫者兩組並發線程，共享一個文件，當兩個或以上的讀線程同時訪問共享數據時不會產生副作用，但若某個寫線程和其他線程（讀線程或寫線程）同時訪問共享數據時則可能導致數據不一致的錯誤。因此要求：①允許多個讀者可以同時對文件執行讀操作；②只允許一個寫者往文件中寫信息；③任一寫者在完成寫操作之前不允許其他讀者或寫者工作；④寫者執行寫操作前，應讓已有的讀者和寫者全部退出。
問題分析：
1) 關系分析。由題目分析讀者和寫者是互斥的，寫者和寫者也是互斥的，而讀者和讀者不存在互斥問題。
2) 整理思路。兩個線程，即讀者和寫者。寫者是比較簡單的，它和任何線程互斥，用互斥信號量的P操作、V操作即可解決。讀者的問題比較復雜，它必須實現與寫者互斥的同時還要實現與其他讀者的同步，因此，僅僅簡單的一對P操作、V操作是無法解決的。那麼，在這裡用到了一個計數器，用它來判斷當前是否有讀者讀文件。當有讀者的時候寫者是無法寫文件的，此時讀者會一直占用文件，當沒有讀者的時候寫者才可以寫文件。同時這裡不同讀者對計數器的訪問也應該是互斥的。
3) 信號量設置。首先設置信號量count為計數器，用來記錄當前讀者數量，初值為0; 設置mutex為互斥鎖，用於保護更新count變量時的互斥；設置互斥信號量rw用於保證讀者和寫者的互斥訪問。
sem_t rw;//保護讀者和寫者互斥地訪問文件，初始化為1
pthread_mutex_t mutex;//保護更新reader_num時的互斥
int reader_num = 0;//用於記錄讀者數量
void *writer_f(void *arg)
{
sem_wait(&rw);//互斥訪問共享文件
usleep(2000000);
printf("writing ...\n");
sem_post(&rw); //釋放共享文件
}
void *reader_f(void *arg)
{
pthread_mutex_lock(&mutex);//互斥訪問reader_num變量
if (reader_num == 0)
{
sem_wait(&rw);//阻止寫線程寫
}
reader_num++;//讀者計數器加1
printf("reader num add the num is %d \n", reader_num);
pthread_mutex_unlock(&mutex);//釋放互斥變量
usleep(2000000);
printf("reading ...\n");
pthread_mutex_lock(&mutex);//互斥訪問reader_num變量
reader_num--;//讀者計數器減1
printf("reader num dec the num is %d \n", reader_num);
if (reader_num == 0)
{
sem_post(&rw);//允許寫線程寫
}
pthread_mutex_unlock(&mutex);//釋放互斥變量
}運行結果：
在上面的算法中，讀線程是優先的，也就是說，當存在讀線程時，寫操作將被延遲，並且只要有一個讀線程活躍，隨後而來的讀線程都將被允許訪問文件。這樣的方式下，會導致寫線程可能長時間等待，且存在寫線程“餓死”的情況。
如果希望寫線程優先，即當有讀線程正在讀共享文件時，有寫線程請求訪問，這時應禁止後續讀線程的請求，等待到已在共享文件的讀線程執行完畢則立即讓寫線程執行，只有在無寫線程執行的情況下才允許讀線程再次運行。為此，增加一個信號量並且在上面的程序中 writer_f()和reader_f()函數中各增加一對PV操作，就可以得到寫線程優先的解決程序。
sem_t rw;//保護讀者和寫者互斥地訪問文件，初始化為1
sem_t w;//用於實現寫優先，初始化為1
pthread_mutex_t mutex;//保護更新reader_num時的互斥
int reader_num = 0;//用於記錄讀者數量
void *writer_f(void *arg)
{
sem_wait(&w);
sem_wait(&rw);//互斥訪問共享文件
usleep(2000000);
printf("writing ...\n");
sem_post(&rw); //釋放共享文件
sem_post(&w);
}
void *reader_f(void *arg)
{
sem_wait(&w);
pthread_mutex_lock(&mutex);//互斥訪問reader_num變量
if (reader_num == 0)
{
sem_wait(&rw);//阻止寫線程寫
}
reader_num++;//讀者計數器加1
printf("reader num add the num is %d \n", reader_num);
pthread_mutex_unlock(&mutex);//釋放互斥變量
sem_post(&w);
usleep(2000000);
printf("reading ...\n");
pthread_mutex_lock(&mutex);//互斥訪問reader_num變量
reader_num--;//讀者計數器減1
printf("reader num dec the num is %d \n", reader_num);
if (reader_num == 0)
{
sem_post(&rw);//允許寫線程寫
}
pthread_mutex_unlock(&mutex);//釋放互斥變量
}
三、哲學家進餐問題
問題描述：
一張圓桌上坐著5名哲學家，每兩個哲學家之間的桌上擺一根筷子，桌子的中間是一碗米飯，如圖2-10所示。哲學家們傾注畢生精力用於思考和進餐，哲學家在思考時，並不影響他人。只有當哲學家饑餓的時候，才試圖拿起左、 右兩根筷子（一根一根地拿起）。如果筷子已在他人手上，則需等待。饑餓的哲學家只有同時拿到了兩根筷子才可以開始進餐，當進餐完畢後，放下筷子繼續思考。
問題分析：
1) 關系分析。5名哲學家與左右鄰居對其中間筷子的訪問是互斥關系。
2) 整理思路。顯然這裡有五個線程。本題的關鍵是如何讓一個哲學家拿到左右兩個筷子而不造成死鎖或者饑餓現象。那麼解決方法有兩個，一個是讓他們同時拿兩個筷子；二是對每個哲學家的動作制定規則，避免饑餓或者死鎖現象的發生。
3) 信號量設置。定義互斥信號量數組chopstick[5] = {l, 1, 1, 1, 1}用於對5個筷子的互斥訪問。
對哲學家按順序從0～4編號，哲學家i左邊的筷子的編號為i，哲學家右邊的筷子的編號為(i+l)%5。
該算法存在以下問題：當五個哲學家都想要進餐，分別拿起他們左邊筷子的時候（都恰好執行完wait(chopstick[i]);)筷子已經被拿光了，等到他們再想拿右邊的筷子的時候（執行 wait(chopstick[(i+l)%5]);)就全被阻塞了，這就出現了死鎖。
為了防止死鎖的發生，可以對哲學家線程施加一些限制條件，比如至多允許四個哲學家同時進餐;僅當一個哲學家左右兩邊的筷子都可用時才允許他抓起筷子;對哲學家順序編號，要求奇數號哲學家先抓左邊的筷子，然後再轉他右邊的筷子，而偶數號哲學家剛好相反。正解制定規則如下：假設釆用第二種方法，當一個哲學家左右兩邊的筷子都可用時，才允許他抓起筷子。
sem_t chopstick
;//定義信號量數組，初始化為1
pthread_mutex_t mutex;//保護取筷子時的互斥
int reader_num = 0;//用於記錄讀者數量
void *philosopher_i(void *arg)
{
int index = *(int *)arg;
pthread_mutex_lock(&mutex);//在取筷子前獲得互斥量
sem_wait(&chopstick[index]);//取左邊筷子
sem_wait(&chopstick[(index+1) % 5]);//取右邊筷子
printf("get two chopstick the index is %d\n", index);
pthread_mutex_unlock(&mutex);//釋放取筷子的互斥量
usleep(2000000);
printf("eating... the index is %d\n", index);//進餐
sem_post(&chopstick[index]);//放回左邊筷子
sem_post(&chopstick[(index+1) % 5]);//放回右邊筷子
usleep(2000000);
printf("thinking... the index is %d\n", index);//思考
}運行結果：
四、吸煙者問題
問題描述：
假設一個系統有三個抽煙者線程和一個供應者線程。每個抽煙者不停地卷煙 並抽掉它，但是要卷起並抽掉一支煙，抽煙者需要有三種材料：煙草、紙和膠水。三個抽煙 者中，第一個擁有煙草、第二個擁有紙，第三個擁有膠水。供應者線程無限地提供三種材料， 供應者每次將兩種材料放到桌子上，擁有剩下那種材料的抽煙者卷一根煙並抽掉它，並給供 應者一個信號告訴完成了，供應者就會放另外兩種材料在桌上，這種過程一直重復（讓三個 抽煙者輪流地抽煙)。
問題分析：
1) 關系分析。供應者與三個抽煙者分別是同步關系。由於供應者無法同時滿足兩個或 以上的抽煙者，三個抽煙者對抽煙這個動作互斥（或由三個抽煙者輪流抽煙得知
2) 整理思路。顯然這裡有四個線程。供應者作為生產者向三個抽煙者提供材料。
3) 信號量設置。信號量offer1、offer2、offer3分別表示煙草和紙組合的資源、煙草和 膠水組合的資源、紙和膠水組合的資源。信號量finish用於互斥進行抽煙動作。
sem_t offer1;//定義信號量對應煙草和紙組合的資源，初始化為1
sem_t offer2;//定義信號量對應煙草和膠水組合的資源，初始化為1
sem_t offer3;//定義信號量對應紙和膠水組合的資源，初始化為1
sem_t finish;//定義信號量表示吸煙者是否完成，初始化為1
void *provider_f(void *arg)
{
while (1)
{
int rand_num = rand() % 3;
if (rand_num == 0)
{
sem_post(&offer1);//提供煙草和紙
}
else if (rand_num == 1)
{
sem_post(&offer2);//提供煙草和膠水
}
else
{
sem_post(&offer3);//提供紙和膠水
}
usleep(1000000);
printf("put two material on table\n");
sem_wait(&finish);
}
}
void *smoker1_f(void *arg)
{
while (1)
{
sem_wait(&offer1);
usleep(1000000);
printf("remove the paper and glue\n");//拿走紙和膠水
sem_post(&finish);
}
}
void *smoker2_f(void *arg)
{
while (1)
{
sem_wait(&offer2);
usleep(1000000);
printf("remove the tobacco and glue\n");//拿走煙草和膠水
sem_post(&finish);
}
}
void *smoker3_f(void *arg)
{
while (1)
{
sem_wait(&offer3);
usleep(1000000);
printf("remove the paper and tobacco\n");//拿走紙和煙草
sem_post(&finish);
}
}運行結果：
參考：
http://c.biancheng.net/cpp/html/2600.html
