| 一. 信號(hào)量的概念 |
| 1． 信號(hào)量的類型定義 |
每個(gè)信號(hào)量至少須記錄兩個(gè)信息：信號(hào)量的值和等待該信號(hào)量的進(jìn)程隊(duì)列。它的類型定義如下：（用類PASCAL語言表述）
semaphore = record
value: integer;
queue: ^PCB;
end;
其中PCB是進(jìn)程控制塊，是操作系統(tǒng)為每個(gè)進(jìn)程建立的數(shù)據(jù)結(jié)構(gòu)。
s.value>=0時(shí)，s.queue為空；
s.value<0時(shí)，s.value的絕對(duì)值為s.queue中等待進(jìn)程的個(gè)數(shù)；
|
|
|
|
| 2． PV原語 |
對(duì)一個(gè)信號(hào)量變量可以進(jìn)行兩種原語操作：p操作和v操作，定義如下： procedure p(var s:samephore);
{
s.value=s.value-1;
if (s.value<0) asleep(s.queue);
}
procedure v(var s:samephore);
{
s.value=s.value+1;
if (s.value<=0) wakeup(s.queue);
}
其中用到兩個(gè)標(biāo)準(zhǔn)過程：
asleep(s.queue);執(zhí)行此操作的進(jìn)程的PCB進(jìn)入s.queue尾部，進(jìn)程變成等待狀態(tài)
wakeup(s.queue);將s.queue頭進(jìn)程喚醒插入就緒隊(duì)列
s.value初值為1時(shí)，可以用來實(shí)現(xiàn)進(jìn)程的互斥。
p操作和v操作是不可中斷的程序段，稱為原語。如果將信號(hào)量看作共享變量，則pv操作為其臨界區(qū)，多個(gè)進(jìn)程不能同時(shí)執(zhí)行，一般用硬件方法保證。一個(gè)信號(hào)量只能置一次初值，以后只能對(duì)之進(jìn)行p操作或v操作。
由此也可以看到，信號(hào)量機(jī)制必須有公共內(nèi)存，不能用于分布式操作系統(tǒng)，這是它最大的弱點(diǎn)。
|
|
|
|
| 二. 實(shí)例 |
| 1． 生產(chǎn)者-消費(fèi)者問題（有buffer） |
問題描述：
一個(gè)倉庫可以存放K件物品。生產(chǎn)者每生產(chǎn)一件產(chǎn)品，將產(chǎn)品放入倉庫，倉庫滿了就停止生產(chǎn)。消費(fèi)者每次從倉庫中去一件物品，然后進(jìn)行消費(fèi)，倉庫空時(shí)就停止消費(fèi)。
解答：
進(jìn)程：Producer - 生產(chǎn)者進(jìn)程，Consumer - 消費(fèi)者進(jìn)程
共有的數(shù)據(jù)結(jié)構(gòu)：
buffer: array [0..k-1] of integer;
in,out: 0..k-1;
— in記錄第一個(gè)空緩沖區(qū)，out記錄第一個(gè)不空的緩沖區(qū)
s1,s2,mutex: semaphore;
— s1控制緩沖區(qū)不滿,s2控制緩沖區(qū)不空,mutex保護(hù)臨界區(qū)；
初始化s1=k,s2=0,mutex=1
producer（生產(chǎn)者進(jìn)程）：
Item_Type item;
{
while (true)
{
produce(&item);
p(s1);
p(mutex);
buffer[in]:=item;
in:=(in+1) mod k;
v(mutex);
v(s2);
}
}
consumer（消費(fèi)者進(jìn)程）：
Item_Type item;
{
while (true)
{
p(s2);
p(mutex);
item:=buffer[out];
out:=(out+1) mod k;
v(mutex);
v(s1);
consume(&item);
}
}
|
|
|
|
| 2． 第一類讀-寫者問題 |
問題描述：
一些讀者和一些寫者對(duì)同一個(gè)黑板進(jìn)行讀寫。多個(gè)讀者可同時(shí)讀黑板，但一個(gè)時(shí)刻只能有一個(gè)寫者，讀者寫者不能同時(shí)使用黑板。對(duì)使用黑板優(yōu)先級(jí)的不同規(guī)定使讀者-寫者問題又可分為幾類。第一類問題規(guī)定讀者優(yōu)先級(jí)較高，僅當(dāng)無讀者時(shí)允許寫者使用黑板。
解答：
進(jìn)程：writer - 寫者進(jìn)程，reader - 讀者進(jìn)程
共有的數(shù)據(jù)結(jié)構(gòu)：
read_account:integer;
r_w,mutex: semaphore;
— r_w控制誰使用黑板,mutex保護(hù)臨界區(qū)，初值都為1
reader - (讀者進(jìn)程）：
{
while (true)
{
p(mutex);
read_account++;
if(read_account=1) p(r_w);
v(mutex);
read();
p(mutex);
read_account--;
if(read_account=0) v(r_w);;
v(mutex);
}
}
writer - (寫者進(jìn)程）：
{
while (true)
{
p(mutex);
write();
v(mutex);
}
}
|
|
|
|
| 3． 哲學(xué)家問題 |
問題描述：
一個(gè)房間內(nèi)有5個(gè)哲學(xué)家，他們的生活就是思考和進(jìn)食。房間里有一張圓桌，中間放著一盤通心粉（假定通心粉無限多）。桌子周圍放有五把椅子，分別屬于五位哲學(xué)家每?jī)晌徽軐W(xué)家之間有一把叉子，哲學(xué)家進(jìn)食時(shí)必須同時(shí)使用左右兩把叉子。
解答：
進(jìn)程：philosopher - 哲學(xué)家
共有的數(shù)據(jù)結(jié)構(gòu)&過程：
state: array [0..4] of (think,hungry,eat);
ph: array [0..4] of semaphore;
— 每個(gè)哲學(xué)家有一個(gè)信號(hào)量，初值為0
mutex: semaphore;
— mutex保護(hù)臨界區(qū)，初值=1
procedure test(i:0..4);
{
if ((state[i]=hungry) and (state[(i+1)mod 5]<>eating)
and (state[(i-1)mod 5]<>eating))
{ state[i]=eating;
V(ph[i]);
}
}
philosopher(i:0..4)：
{
while (true)
{
think();
p(mutex);
state[i]=hungry;
test(i);
v(mutex);
p(ph[i]);
eat();
p(mutex);
state[i]=think;
test((i-1) mod 5);
test((i+1) mod 5);
v(mutex);
}
}
|
