程序併發常見問題基於訊號量解決方法總結:生產者/消費者問題、讀/寫者問題、銀行家演算法、哲學家進餐(待補充)

NO IMAGE

一、訊號量

  • 訊號量是一個與佇列有關的整型變數。
  • 可以初始化成非負數;
  • semWait操作使訊號量減1。若值為負數,則執行semWait的程序阻塞,否則繼續執行;
  • semSignal操作使訊號量加1。若值小於或等於0,則被semWait操作阻塞的程序被解除阻塞。

訊號量原語semWait和semSignal的定義

strcut semaphore{
int count;
aueueType queue;
};
void semWait(semaphore s) {
s.count--;
if(s.count < 0) {
place this process in s.queue;
block this process;
}
}
void semSignal(semaphore s) {
s.count   ;
if(s.count <= 0) {
remove a process P from s.queue;
place process P on ready list;
}
}

訊號量實現互斥

const int n;
semaphore s = 1;
void P(int i) {
while(true) {
semWait(s);
operate;
semSignal(s);
}
}
void main() {
parbegin(P(1), P(2), ...,P(n));
}

總結

訊號量

  • 一個訊號量可用於n個程序的同步互斥;且只能由semWait、semSignal操作修改。
  • 用於互斥時,S初值為1,取值為1~ – (n-1) (相當於臨界區的通行證,實際上也是資源個數)
    S=1:臨界區可用
    S=0:已有一程序進入臨界區
    S<0:臨界區已被佔用,|S|個程序正等待進入
  • 用於同步時,S初值>=0
    S>=0:表示可用資源個數
    S<0: 表示該資源的等待佇列長度

semWait、semSignal操作
– semWait(S):請求分配一個資源。
– semSignal(S):釋放一個資源。
– semWait、semSignal操作必須成對出現。
– 用於互斥時,位於同一程序內;
– 用於同步時,交錯出現於兩個合作程序內。
– 多個semWait操作的次序不能顛倒,否則可能導致死鎖。
– 多個semSignal操作的次序可任意。

二、生產者/消費者問題

問題描述:
有一個或多個生產者生產某種型別的資料,並放置在緩衝區中;
有一個消費者從緩衝區中取資料,每次取一項;
系統保證避免對緩衝區的重複操作,即任何時候只有一個主體(生產者或消費者)可以訪問緩衝區;
快取已滿時,生產者不能繼續新增資料;
快取已空時,消費者不能繼續移走資料。

producer:


while(true) {
/* produce item v */
while((in   1) % n == out) //等待快取有空位
/* doing nothing */
b[in] = v;
in = (in   1) % n;
}   

consumer:


while(true) {
while(in == out) //此時快取為空,等待生產者生產放入快取後才可消費
/* doing nothing */
w = b[out];
out = (out   1) % n;
/* consume item w */
}

有限緩衝區:

process_concurrent_finite_buffer

使用訊號量解決有限緩衝區生產者消費者問題:

n 表示已生產產品的數量
s 用來控制互斥
e 表示空閒空間數目


semaphore n = 0, s = 1, e = buf - size;
void producer() {
while(true) {
produce();
semWait(e);
semWait(s);
append();
semSignal(s);
semSignal(e);
}
}
void consumer() {
while(true) {
semWait(n);
semWait(s);
take();
semSignal(s);
semSignal(e);
consume();
}
}

例題
1) 桌子上有一個盤子,可以存放一個水果。父親總是放蘋果到盤子中,而母親總是放香蕉到盤子中;兒子專等吃盤中的香蕉,而女兒專等吃盤中的蘋果。

分析:
生產者-消費者問題的一種變形,生產者、消費者以及放入緩衝區的產品都有兩類(蘋果和香蕉),但每類消費者只消費其中固定的一種產品(兒子消費香蕉,女兒消費蘋果)。

資料結構: semaphore dish, apple, banana;
dish: 表示盤子是否為空,用於控制互斥
apple:表示盤子中是否有蘋果,初始值為0
banana:表示盤子中是否有香蕉,初始值為0


process father() {
semWait(dish);
put the apple in the dish;
semSignal(apple);
}
process mother() {
semWait(dish);
put the banana in the dish;
semSignal(banana);
}
process son() {
semWait(banana);
get the banana from the dish;
semSignal(dish);
}
process daughter() {
semWait(apple);
get the apple from the dish;
semSignal(dish);
}

2) 在一個盒子裡,混裝了數量相等的黑白圍棋子。現在用自動分揀系統把黑子、白子分開,設分揀系統有兩個程序P1和P2,其中P1揀白子,P2揀黑子。規定每個程序每次揀一子,當一個程序在揀時,不允許另一個程序去揀;當一個程序揀了一子時,必須讓另一個程序去揀。試用訊號量協調兩個程序的併發執行。

分析:
實際上就是兩個程序的同步問題,也就是揀了一個白棋子才能揀一個黑棋子,兩者成合作關係

資料結構:semaphore s1, s2;
s1 和s2 分別表示可揀白子和黑子,不失一般性,若令先揀白子。初值, s1=1; s2=0;

“` bash

process p1() {
while(true){
semWait(s1);
Pick a white chessman;
semSignal(s2);
}
}

process p2() {
while(true){
semWait(s2);
Pick a white chessman;
semSignal(s1);
}
}

“`

3) 假設一個閱覽室有100個座位,沒有座位時讀者在閱覽室外等待;每個讀者進入閱覽室時都必須在閱覽室門口的一個登記本上登記座位號和姓名,然後閱覽,離開閱覽室時要去掉登記項。每次只允許一個人登記或去掉登記。用訊號量操作描述讀者的行為。

分析:
實際上是一個非常簡單的同步-互斥問題,登記時需要保證互斥,室內人數在100之內時,無需等待,大於100人是,開始需要等待室內有人出來後方可有人入室

資料結構:
strcut {
char name[10];
int number;
} a[100]; //表示進入閱覽室的小朋友
semaphore mutex, seatcount;
mutex: 用來控制互斥,初始值為1
seatcount: 對空座位進行計數,初始值為100;

初始化入室人員資訊
for(int i = 0; i < 100; i  ){
a[i].number = i;
a[i].name = null;
}

“` bash

process readeri(char readername[]) {
semWait(seatcount); //等待空餘作為,若人數未滿100,則直接進入,到達100,則等待
semWait(mutex); //控制互斥

/* 進入是登記 */
for(int i = 0; i < 100; i  )
if(a[i].name == null){  //找到名字為空的座位
a[i].name = readername;
break;
}
reader get the seat nember i;
semSiganl(mutex);
go into the reading room and sit down at the seat number i.
/* 離開時登記 */
semWait(mutex);
a[i].name = null;  
semSignal(mutex);
semSignal(seatcount);
leave reading room;

}

“`

二、讀/寫者問題
描述:
有一個由多個程序共享的資料區,一些程序只讀取這個資料區中的資料,一些程序只往資料區中寫資料。並須滿足以下條件:
任意多的讀程序可以同時讀檔案;
一次只有一個寫程序可以寫檔案;
如果一個寫程序正在寫檔案,那麼禁止任何讀程序讀檔案。

讀者優先

分析:
當一個讀程序開始訪問資料區時,只要至少有一個讀程序正在讀,就為讀程序保留對這個資料區的控制權,因此,寫程序有可能處於飢餓狀態。

資料結構:
readcount: 控制wsem的的設定
wsem: 當沒有讀程序正在讀時,第一個試圖讀的讀程序需要在wsem上等待; 當至少有一個讀程序在讀時,隨後的讀程序無需等待直接進入。
x: 用於確保readcount被正確更新。


int readcount;
semphore x = 1, wsem = 1;
void reader() {
while (true) {
semWait(x);
readcount  ;
if(readcount==1)
semWait(wsem);  //如果是第一個讀者,則要控制wsem
semSignal(x);
READUNIT();   
semWait(x);
readcount--;
if(readcount==0)
semSignal(wsem);
semSignal(x);
}
}
void writer(){
while (true) {
semWait(wsem);
WRITEUNIT();
semSignal(wsem);
}
}

例項:
獨木橋問題:東、西向汽車過獨木橋。橋上無車時允許一方汽車過橋,待全部過完後才允許另一方汽車過橋。用訊號量操作寫出同步演算法。(提示:參考讀者優先的解法)

資料結構:

mutex1/mutex2: 用於確保count1/count2被準備更新
count1/count2: 控制wait的設定
wait: 當沒有車同向的車通過獨木橋時,第一輛通過的車需要在wait上等待; 當至少有一輛同向的車通過時,隨後同方向的車無需等待直接進入。

semaphore wait=1, mutex1=1, mutex2=1;
int count1=0, count2=0; 
process P east(){
semWait(mutex1);
count1  ;
if(count1==1)   semWait(wait);
semSignal(mutex1);
through the singal-log bridge;
semWait(mutex1);
count1--;
if(count1==0)   semSignal(wait);
semSignal(mutex1);
}
process P west(){
semWait(mutex2);
count2  ;
if(count2==1)   semWait(wait);
semSignal(mutex2);
through the singal-log bridge;
semWait(mutex2);
count2--;
if(count2==0)   semSignal(wait);
semSignal(mutex2);
}

待整理。。。