本文摘自湯小丹主編《計(jì)算機(jī)操作系統(tǒng)》（第三版）2.4 經(jīng)典進(jìn)程的同步問
在多道程序環(huán)境下,進(jìn)程同步問題十分重要,也是相當(dāng)有趣的問題,因而吸引了不少 學(xué)者對(duì)它進(jìn)行研究,由此而產(chǎn)生了一系列經(jīng)典的進(jìn)程同步問題,其中較有代表性的是“生 產(chǎn)者—消費(fèi)者”問題、“讀者—寫者問題”焚虱、“哲學(xué)家進(jìn)餐問題”等等。通過對(duì)這些問題的研 究和學(xué)習(xí),可以幫助我們更好地理解進(jìn)程同步的概念及實(shí)現(xiàn)方法。
生產(chǎn)者—消費(fèi)者問題
前面我們已經(jīng)對(duì)生產(chǎn)者—消費(fèi)者問題(The proceducer-consumer problem)做了一些描述, 但未考慮進(jìn)程的互斥與同步問題,因而造成了數(shù)據(jù)(Counter)的不定性。由于生產(chǎn)者—消費(fèi)者 問題是相互合作的進(jìn)程關(guān)系的一種抽象,例如,在輸入時(shí),輸入進(jìn)程是生產(chǎn)者,計(jì)算進(jìn)程 是消費(fèi)者;而在輸出時(shí),計(jì)算進(jìn)程是生產(chǎn)者,而打印進(jìn)程是消費(fèi)者。因此,該問題有很大 的代表性及實(shí)用價(jià)值。本小節(jié)將利用信號(hào)量機(jī)制來解決生產(chǎn)者—消費(fèi)者問題。
1. 利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問題
假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中,具有 n 個(gè)緩沖區(qū),這時(shí)可利用互斥信號(hào) 量 mutex 實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用声畏。利用信號(hào)量 empty 和 full 分別表示緩沖池中空緩 沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效,只要緩沖池未滿,生產(chǎn)者 便可將消息送入緩沖池;只要緩沖池未空,消費(fèi)者便可從緩沖池中取走一個(gè)消息姻成。對(duì)生產(chǎn) 者—消費(fèi)者問題可描述如下:
Var mutex,empty,full: semaphore:=1,n,0;
buffer:array[0,...,n-1] of item;
in,out: integer:=0,0;
begin
parbegin
proceducer: begin
repeat
...
producer an item nextp;
...
wait(empty);
wait(mutex);
buffer(in):=nextp;
in:=(in+1) mod n;
signal(mutex);
signal(full);
until false;
end
consumer: begin
repeat
wait(full);
wait(mutex);
nextc:=buffer(out);
out:=(out+1) mod n;
signal(mutex);
signal(empty);
consumer the item in nextc;
until false;
end
parend
end
在生產(chǎn)者—消費(fèi)者問題中應(yīng)注意:首先,在每個(gè)程序中用于實(shí)現(xiàn)互斥的 wait(mutex)和 signal(mutex)必須成對(duì)地出現(xiàn);其次,對(duì)資源信號(hào)量 empty 和 full 的 wait 和 signal 操作,同 樣需要成對(duì)地出現(xiàn),但它們分別處于不同的程序中插龄。例如,wait(empty)在計(jì)算進(jìn)程中,而 signal(empty)則在打印進(jìn)程中,計(jì)算進(jìn)程若因執(zhí)行 wait(empty)而阻塞,則以后將由打印進(jìn)程 將它喚醒;最后,在每個(gè)程序中的多個(gè) wait 操作順序不能顛倒,應(yīng)先執(zhí)行對(duì)資源信號(hào)量的 wait 操作,然后再執(zhí)行對(duì)互斥信號(hào)量的 wait 操作,否則可能引起進(jìn)程死鎖。
2. 利用 AND 信號(hào)量解決生產(chǎn)者—消費(fèi)者問題
對(duì)于生產(chǎn)者—消費(fèi)者問題,也可利用 AND 信號(hào)量來解決,即用 Swait(empty,mutex) 來代替wait(empty)和wait(mutex);用Ssignal(mutex,full)來代替signal(mutex)和signal(full); 用 Swait(full,mutex)來代替 wait(full)和 wait(mutex),以及用 Ssignal(mutex,empty)代替 Signal(mutex)和 Signal(empty)科展。利用 AND 信號(hào)量來解決生產(chǎn)者—消費(fèi)者問題的算法描述 如下:
Var mutex,empty,full: semaphore:=1,n,0;
buffer:array[0,...,n-1] of item;
in out: integer:=0,0;
begin
parbegin
producer: begin
repeat
...
produce an item in nextp;
...
Swait(empty,mutex);
buffer(in):=nextp;
in:=(in+1)mod n;
Ssignal(mutex,full);
until false;
end
consumer:begin
repeat
Swait(full,mutex);
Nextc:=buffer(out);
Out:=(out+1) mod n;
Ssignal(mutex,empty);
consumer the item in nextc;
until false;
end
parend
end
3. 利用管程解決生產(chǎn)者—消費(fèi)者問題
在利用管程方法來解決生產(chǎn)者—消費(fèi)者問題時(shí),首先便是為它們建立一個(gè)管程,并命 名為 ProclucerConsumer,或簡(jiǎn)稱為 PC均牢。其中包括兩個(gè)過程:
- put(item)過程。生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中,并用整型變 量 count 來表示在緩沖池中已有的產(chǎn)品數(shù)目,當(dāng) count≥n 時(shí),表示緩沖池已滿,生產(chǎn)者須 等待才睹。
- get(item)過程徘跪。消費(fèi)者利用該過程從緩沖池中取出一個(gè)產(chǎn)品,當(dāng)count≤0時(shí),表示 緩沖池中已無可取用的產(chǎn)品,消費(fèi)者應(yīng)等待。
PC 管程可描述如下:
type producer-consumer=monitor
Var in,out,count: integer;
buffer: array[0, ..., n-1] of item; notfull,notempty:condition;
procedure entry put(item)
begin
if count>=n then notfull.wait;
buffer(in):=nextp;
in:=(in+1) mod n;
count:=count+1;
if notempty.queue then notempty.signal;
end
procedure entry get(item)
begin
if count<=0 then notempty.wait; nextc:=buffer(out);
out:=(out+1) mod n;
count:=count-1;
if notfull.quene then notfull.signal;
end
begin in:=out:=0;
count:=0
end
在利用管程解決生產(chǎn)者—消費(fèi)者問題時(shí),其中的生產(chǎn)者和消費(fèi)者可描述為:
producer: begin
repeat
produce an item in nextp;
PC.put(item);
until false;
end
consumer: begin
repeat
PC.get(item);
consume the item in nextc;
until false;
end
哲學(xué)家進(jìn)餐問題
由 Dijkstra 提出并解決的哲學(xué)家進(jìn)餐問題(The Dinning Philosophers Problem)是典型的同 步問題琅攘。該問題是描述有五個(gè)哲學(xué)家共用一張圓桌,分別坐在周圍的五張椅子上,在圓桌 上有五個(gè)碗和五只筷子,他們的生活方式是交替地進(jìn)行思考和進(jìn)餐垮庐。平時(shí),一個(gè)哲學(xué)家進(jìn) 行思考,饑餓時(shí)便試圖取用其左右最靠近他的筷子,只有在他拿到兩只筷子時(shí)才能進(jìn)餐。 進(jìn)餐完畢,放下筷子繼續(xù)思考坞琴。
1. 利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問題
經(jīng)分析可知,放在桌子上的筷子是臨界資源,在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用哨查。 為了實(shí)現(xiàn)對(duì)筷子的互斥使用,可以用一個(gè)信號(hào)量表示一只筷子,由這五個(gè)信號(hào)量構(gòu)成信號(hào) 量數(shù)組。其描述如下:
Var chopstick: array[0,...,4] of semaphore;
所有信號(hào)量均被初始化為 1,第 i 位哲學(xué)家的活動(dòng)可描述為:
repeat
wait(chopstick[i]);
wait(chopstick[(i+1)mod 5]);
...
eat;
...
signal(chopstick[i]);
signal(chopstick[(i+1)mod 5]);
...
think;
until false;
在以上描述中,當(dāng)哲學(xué)家饑餓時(shí),總是先去拿他左邊的筷子,即執(zhí)行 wait(chopstick[i]);
成功后,再去拿他右邊的筷子,即執(zhí)行 wait(chopstick[(i+1)mod 5]);又成功后便可進(jìn)餐剧辐。進(jìn) 餐完畢,又先放下他左邊的筷子,然后再放右邊的筷子寒亥。雖然,上述解法可保證不會(huì)有兩 個(gè)相鄰的哲學(xué)家同時(shí)進(jìn)餐,但有可能引起死鎖。假如五位哲學(xué)家同時(shí)饑餓而各自拿起左邊 的筷子時(shí),就會(huì)使五個(gè)信號(hào)量 chopstick 均為 0; 當(dāng)他們?cè)僭噲D去拿右邊的筷子時(shí),都將因 無筷子可拿而無限期地等待荧关。對(duì)于這樣的死鎖問題,可采取以下幾種解決方法:
- 至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子,最終能保證至少有一位哲學(xué)家能夠 進(jìn)餐,并在用畢時(shí)能釋放出他用過的兩只筷子,從而使更多的哲學(xué)家能夠進(jìn)餐溉奕。
- 僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí),才允許他拿起筷子進(jìn)餐忍啤。
- 規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子,然后再去拿右邊的筷子,而偶數(shù)號(hào)哲學(xué)家則 相反加勤。按此規(guī)定,將是 1、2 號(hào)哲學(xué)家競(jìng)爭(zhēng) 1 號(hào)筷子;3檀轨、4 號(hào)哲學(xué)家競(jìng)爭(zhēng) 3 號(hào)筷子。即五位 哲學(xué)家都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子,獲得后,再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子,最后總會(huì)有一位哲學(xué)家能獲 得兩只筷子而進(jìn)餐欺嗤。
2. 利用 AND 信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題
在哲學(xué)家進(jìn)餐問題中,要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐,這在本 質(zhì)上就是前面所介紹的 AND 同步問題,故用 AND 信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法参萄。描述 如下:
Var chopsiick array of semaphore:=(1,1,1,1,1);
processi
repeat
think;
Sswait(chopstick[(i+1)mod 5],chopstick[i]);
eat;
Ssignat(chopstick[(i+1)mod 5],chopstick[i]);
until false;
讀者—寫者問題
一個(gè)數(shù)據(jù)文件或記錄,可被多個(gè)進(jìn)程共享,我們把只要求讀該文件的進(jìn)程稱為“Reader 進(jìn)程”,其他進(jìn)程則稱為“Writer 進(jìn)程”。允許多個(gè)進(jìn)程同時(shí)讀一個(gè)共享對(duì)象,因?yàn)樽x操作不 會(huì)使數(shù)據(jù)文件混亂煎饼。但不允許一個(gè) Writer 進(jìn)程和其他 Reader 進(jìn)程或 Writer 進(jìn)程同時(shí)訪問共 享對(duì)象,因?yàn)檫@種訪問將會(huì)引起混亂讹挎。所謂“讀者—寫者問題(Reader-Writer Problem)”是 指保證一個(gè) Writer 進(jìn)程必須與其他進(jìn)程互斥地訪問共享對(duì)象的同步問題。讀者—寫者問題 常被用來測(cè)試新同步原語。
1. 利用記錄型信號(hào)量解決讀者—寫者問題
為實(shí)現(xiàn) Reader 與 Writer 進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互斥信號(hào)量 Wmutex筒溃。 另外,再設(shè)置一個(gè)整型變量 Readcount 表示正在讀的進(jìn)程數(shù)目马篮。由于只要有一個(gè) Reader 進(jìn) 程在讀,便不允許 Writer 進(jìn)程去寫。因此,僅當(dāng) Readcount=0,表示尚無 Reader 進(jìn)程在讀 時(shí),Reader 進(jìn)程才需要執(zhí)行 Wait(Wmutex)操作怜奖。若 Wait(Wmutex)操作成功,Reader 進(jìn)程便 可去讀,相應(yīng)地,做 Readcount+1 操作浑测。同理,僅當(dāng) Reader 進(jìn)程在執(zhí)行了 Readcount 減 1 操作后其值為0時(shí),才須執(zhí)行signal(Wmutex)操作,以便讓W(xué)riter進(jìn)程寫。又因?yàn)镽eadcount 是一個(gè)可被多個(gè) Reader 進(jìn)程訪問的臨界資源,因此,也應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量 rmutex歪玲。
讀者—寫者問題可描述如下:
Var rmutex,wmutex: semaphore:=1,1;
Readcount: integer:=0;
begin
parbegin
Reader: begin
repeat
wait(rmutex);
if readcount=0 then wait(wmutex);
Readcount:=Readcount+1;
signal(rmutex);
...
perform read operation;
...
wait(rmutex);
readcount:=readcount-1;
if readcount=0 then signal(wmutex);
signal(rmutex);
until false; end
writer: begin
repeat
wait(wmutex);
perform write operation;
signal(wmutex);
until false; end
parend
end
2. 利用信號(hào)量集機(jī)制解決讀者—寫者問題
這里的讀者—寫者問題與前面的略有不同,它增加了一個(gè)限制,即最多只允許 RN 個(gè)讀 者同時(shí)讀迁央。為此,又引入了一個(gè)信號(hào)量 L,并賦予其初值為 RN,通過執(zhí)行 wait(L,1,1) 操作,來控制讀者的數(shù)目。每當(dāng)有一個(gè)讀者進(jìn)入時(shí),就要先執(zhí)行 wait(L,1,1)操作,使 L 的值減 1滥崩。當(dāng)有 RN 個(gè)讀者進(jìn)入讀后,L 便減為 0,第 RN+1 個(gè)讀者要進(jìn)入讀時(shí),必然會(huì)因 wait(L,1,1)操作失敗而阻塞岖圈。對(duì)利用信號(hào)量集來解決讀者—寫者問題的描述如下:
Var RN integer;
L,mx: semaphore:=RN,1;
begin
parbegin
reader: begin
repeat
Swait(L,1,1);
Swait(mx,1,0);
...
perform read operation;
...
Ssignal(L,1);
until false;
end
writer: begin
repeat
Swait(mx,1,1;L,RN,0);
perform write operation;
Ssignal(mx,1);
until false;
end
parend end
其中,Swait(mx,1,0)語句起著開關(guān)的作用。只要無 writer 進(jìn)程進(jìn)入寫,mx=1,reader 進(jìn) 程就都可以進(jìn)入讀钙皮。但只要一旦有 writer 進(jìn)程進(jìn)入寫時(shí),其 mx=0,則任何 reader 進(jìn)程就都無法進(jìn)入讀蜂科。Swait(mx,1,1;L,RN,0)語句表示僅當(dāng)既無 writer 進(jìn)程在寫(mx=1),又無reader 進(jìn)程在讀(L=RN)時(shí),writer 進(jìn)程才能進(jìn)入臨界區(qū)寫。
http://gurglessh.github.io/2016/04/12/經(jīng)典進(jìn)程的同步問題/
