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