信号量与 PV操作
记录型信号量及其应用
二元信号量
同时型信号量及其应用
一般型信号量及其应用
3.3.1 同步和同步机制
著 名 的 生 产 者 --消费者 ( Producer-
Consumer Problem) 问题是计算机操作系统中并发进程内在关系的一种抽象,
是典型的进程同步问题 。 在操作系统中,
生产者进程可以是计算进程,发送进程；
而消费者进程可以是打印进程,接收进程等等 。 解决好了生产者 --消费者问题就解决好了一类并发进程的同步问题 。
生产者 --消费者问题表述如下：
有 n个生产者和 m个消费者,连接在一个有 k个单位缓冲区的有界缓冲上,
故又叫有界缓冲问题 。 其中,pi和 cj
都是并发进程,只要缓冲区未满,
生产者 pi生产的产品就可投入缓冲区；类似地,只要缓冲区不空,消费者进程 cj就可从缓冲区取走并消耗产品 。
可以把生产者 -消费者问题的算法描述如下：
var k:integer;
type item:any;
buffer:array[0..k-1]of item;
in,out:integer:=0;
coumter:integer:=0;
process producer
while (TRUE) /*无限循环
produce an item in nextp; /*生产一个产品
if (counter==k) sleep( ); /*缓冲满时,生产者睡眠
buffer[in]:=nextp; /*将一个产品放入缓冲区
in:=(in+1) mod k; /*指针推进
counter:=counter+1; /*缓冲内产品数加 1
if (counter==1) wakeup( consumer); /* 缓冲为空了,加进一件产品并唤醒消费者
process consumer
while (TRUE) /* 无限循环
if (counter==0) sleep ( ); /* 缓冲区空,消费者睡眠
nextc:=buffer[out]; /* 取一个产品到 nextc
out:=(out+1) mod k; /* 指针推进
counter:=counter-1; /* 取走一个产品,计数减 1
if (counter==k-1) wakeup( producer); /*
缓冲满了,取走一件产品并唤醒生产者
consume thr item in nextc; /* 消耗产品
生产者和消费者进程对 counter
的交替执行会使其结果不唯一
生产者和消费者进程的交替执行会导致进程永远等待，造成系统死锁
前一节介绍的种种方法虽能保证互斥,
可正确解决临界区调度问题,但有明显缺点 。 对不能进入临界区的进程,采用忙式等待 (busy waiting)测试法,浪费
CPU时间 。 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性,加重了用户编程负担 。
1965年荷兰的计算机科学家
E.W.Dijkstra提出了新的同步工具 --信号量和 P,V操作。
记录型信号量与 PV操作
信号量：一种软资源
原语：执行时不可被中断的过程
P操作原语和 V操作原语
信号量按其用途可分为两种：
公用信号量：联系一组并发进程,相关的进程均可在此信号量上执行 P和 V操作 。 初值常常为 1，
用于实现进程互斥 。
私有信号量：联系一组并发进程,仅允许此信号量拥有的进程执行 P操作,而其他相关进程可在其上施行 V操作 。 初值常常为 0或正整数,多用于并发进程同步 。
信号量按其取值可分为两种：
二元信号量：仅允许取值为 0和 1,主要用于解决进程互斥问题 。
一般信号量：允许取值为非负整数,主要用于解决进程间的同步问题 。
1、整型信号量
设 s为一个正整形量,除初始化外,仅能通过 P,V
操作来访问它,这时 P操作原语和 V操作原语定义如下,。
P(s)； 当信号量 s大于 0时,把信号量 s减去 l，
否则调用 P(s)的进程等待直到信号量 s大于 0时 。
V(s),把信号量 s加 1。
P(s) 和 V(s) 可以写成：
P(s),while s≤ 0 do null operation
s,=s-1；
V(s),s,=s+1；
2、记录型信号量
设 s为一个记录型数据结构,其中一个分量为整形量 value,另一个分量为信号量队列 queue,这时 P操作原语和 V操作原语的定义修改如下：
P(s)； 将信号量 s减去 l,若结果小于 0，
则调用 P(s)的进程被置成等待信号量 s的状态 。
V(s),将信号量 s加 1,若结果不大于 0，
则释放一个等待信号量 s的进程 。
记录型信号量和 P操作,V操作可表示成如下的数据结构和不可中断过程：
记录型信号量与 PV操作
type semaphore = record
value:integer;
queue,list of process;
end
procedure P(var s:semaphore);
begin
s,= s – 1; /* 把信号量减去 1 */
if s < 0 then W(s); /* 若信号量小于 0,则调用 P(s)的进程被置成等待信号量 s的状态 */
end;
procedure V(var s:semaphore);
begin
s,= s + 1; /* 把信号量加 1 */
if s <= 0 then R(s); /* 若信号量小于等于 0,则释放一个等待信号量 s的进程 */
end;
记录型信号量与 PV操作
推论 1：若信号量 s为正值,则该值等于在封锁进程之前对信号量 s可施行的 P操作数,亦等于 s所代表的实际还可以使用的物理资源数
推论 2：若信号量 s为负值,则其绝对值等于登记排列在该信号量 s队列之中等待的进程个数,亦即恰好等于对信号量 s实施 P操作而被封锁起来并进入信号量 s队列的进程数
推论 3：通常,P操作意味着请求一个资源,V
操作意味着释放一个资源 。 在一定条件下,P
操作代表挂起进程操作,而 V操作代表唤醒被挂起进程的操作
3、二元信号量
设 s为一个记录型数据结构,其中一个分量为
value,它仅能取值 0和 1,另一个分量为信号量队列 queue,这时我们把二元信号量上的 P、
V操作记为 BP和 BV,BP操作原语和 BV操作原语的定义如下：
type binary semaphore=record
value(0,1);
queue,list of process
end;
type binary semaphore=record
value(0,1);
queue,list of process
end;
procedure BP(var s:semaphore);
if s.value=1;
then
s.value=0;
else begin
w(s.queue);
end;
procedure BV(var s:semaphore);
if s.queue is empty;
then
s.value=1;
else begin
R(s.queue);
End;
记录型信号量解决进程互斥问题
s,semaphore;
s,= 1;
cobegin
……
process Pi
begin
……
P(s);
临界区；
V(s);
……
end;
……
coend;
记录型信号量解决机票问题
A,A R R A Y [ 1,,m ] O F i n t e g e r ;
s,semaphore;
s,= 1;
cobegin
process Pi
var Xi:integer;
begin
L1,
按旅客定票要求找到 A[j] ；
P(s)
Xi,= A[j];
If Xi>=1
then begin
Xi:=Xi - 1 ; A [ j ],= X i ;
V(s); 输出一张票 ；
end;
else begin
V(s); 输出票已售完 ；
end;
goto L1;
end;
coend;
A,A R R A Y [ 1,,m ] O F i n t e g e r ;
s,A R R A Y [ 1,,m ] O F e m a p h o r e ;
s[j],= 1;
cobegin
process Pi
var Xi:integer;
begin
L1,
按旅客定票要求找到 A[j] ；
P(s[j])
Xi,= A[j];
If Xi>=1
then begin
Xi:=Xi - 1 ; A [ j ],= X i ;
V(s[j]); 输出一张票 ；
end;
else begin
V(s[j]); 输出票已售完 ；
end;
goto L1;
e nd;
coend;
哲学家吃通心面 问题有五个哲学家围坐在一圆桌旁,桌中央有一盘通心面,每人面前有一只空盘于,每两人之间放一把叉子 。 每个哲学家思考,饥饿,然后吃通心面 。 为了吃面,每个哲学家必须获得两把叉子,且每人只能直接从自己左边或右边去取叉子哲学家吃通心面问题
var forki,array[0..4] of semaphore;
forki,= 1;
cobegin
process Pi // i=0,1,2,3,4,
begin
L1:
思考；
P(fork[i])；
P(fork[(i+1)mod 5])；
吃通心面；
V(fork[i])；
V(fork[(i+1)mod 5])；
goto L1;
end;
coend;
有若干种办法可避免这类死锁：
至多允许四个哲学家同时吃；
奇数号先取左手边的叉子,偶数号先取右手边的叉子；
每个哲学家取到手边的两把叉子才吃,否则一把叉子也不取 。
哲学家吃通心面问题
var forki,array[0..4] of semaphore;
forki,= 1;
cobegin
process Pi // i=0,1,2,3,4,
begin
L1:
思考；
P(fork[i])； // i=4,P(fork[0])
P(fork[i+1])； // i=4,P(fork[4])
吃通心面；
V(fork[i])；
V(fork[(i+1)mod 5])；
goto L1;
end;
coend;
生产者消费者问题
生产者和消费者共享缓冲区
缓冲区空时,生产者可放入产品 （ 不许放重 ）,否则等待
缓冲区中有产品时,消费者可取出产品 （ 不许取重 ）,否则等待
① 一个生产者,一个消费者共享一个缓冲区
② 一个生产者,一个消费者共享多个缓冲区
③ 多个生产者,多个消费者共享多个缓冲区
④ 多个生产者,多个消费者共享一个缓冲区
⑤ 多个生产者,一个消费者共享多个缓冲区
⑥ 一个生产者,多个消费者共享多个缓冲区生产者消费者问题
B,integer;
process producer
begin
L1,
produce a product ；
B,= product ；
goto L1;
end;
process consumer
begin
L2,
product:= B ；
consume a product ；
goto L2;
end;
记录型信号量解决生产者消费者问题
B,integer;
sput:semaphore ； / * 可以使用的空缓冲区数 * /
sget:sema p h o r e ; / * 缓冲区内可以使用的产品数 * /
s p u t,= 1 ; / * 缓冲区内允许放入一件产品 * /
sget,= 0; /* 缓冲区内没有产品 */
process producer
begin
L1,
produce a product ；
P(sput);
B,= product ；
V(sget);
goto L1;
end;
process consumer
begin
L2,
P(sget);
product:= B ；
V(sput);
consume a product ；
goto L2;
end;
记录型信号量解决生产者消费者问题
B,ARRAY[0..k - 1] OF integer;
sput:semaphore ； / * 可以使用的空缓冲区数 * /
sget:sema p h o r e ; / * 缓冲区内可以使用的产品数 * /
s p u t,= k ; / * 缓冲区内允许放入 k 件产品 * /
sget,= 0; /* 缓冲区内没有产品 */
putptr,getptr,integer;
putptr,= 0; getptr,= 0;
process producer_i
begin
L1:produce a p r o d u c t ；
P(sput);
B[putptr],= p r o d u c t ；
p u t p t r,= ( p u t p t r + 1 ) m o d k ;
V(sget);
goto L1;
end;
process consumer_j
begin
L2:P(sget);
Product:= B[getptr] ；
g e t p t r,= ( g e t p t r + 1 ) m o d k ;
V(sput);
consume a product ；
goto L2;
end;
记录型信号量解决生产者消费者问题
B,ARRAY[0..k - 1] OF integer;
sput:semaphore ； / * 可以使用的空缓冲区数 * /
sget:sema p h o r e ; / * 缓冲区内可以使用的产品数 * /
s p u t,= k ; / * 缓冲区内允许放入 k 件产品 * /
sget,= 0; /* 缓冲区内没有产品 */
putptr,getptr,integer;
putptr,= 0; getptr,= 0;
s:semaphore ； / * 互斥使用 putptr,getptr */
s,= 1 ；
process producer_i
begin
L1:produce a p r o d u c t ；
P(sput);
P(s);
B[putptr],= p r o d u c t ；
p u t p t r,= ( p u t p t r + 1 ) m o d k ;
V(s);
V(sget);
goto L1;
end;
process consumer_j
begin
L2:P(sget );
P(s);
Product:= B[getptr] ；
g e t p t r,= ( g e t p t r + 1 ) m o d k ;
V(s);
V(sput);
consume a product ；
goto L2;
end;
苹果桔子问题桌上有一只盘子,每次只能放入一只水果；爸爸专向盘子中放苹果 (apple)，
妈妈专向盘子中放桔于 (orange),一个儿子专等吃盘子中的桔子,一个女儿专等吃盘子里的苹果记录型信号量解决苹果桔子问题
plate,integer;
sp:semaphore； /* 盘子里可以放几个水果 */
sg1:semaphore; /* 盘子里有桔子 */
sg2:semaphore; /* 盘子里有苹果 */
sp,= 1; /* 盘子里允许放入一个水果 */
sg1,= 0; /* 盘子里没有桔子 */
sg2,= 0; /* 盘子里没有苹果 */
cobegin
process father
begin
L1,削一个苹果；
P(sp);
把苹果放入 plate；
V(sg2);
goto L1;
end;
process mother
begin
L2,剥一个桔子；
P(sp);
把桔子放入 plate；
V(sg1);
goto L2;
end;
process son
begin
L3,P(sg1);
从 plate中取桔子；
V(sp);
吃桔子；
goto L3;
end;
process daughter
begin
L4,P(sg2);
从 plate中取苹果；
V(sp);
吃苹果；
goto L4;
end;
coend
读者写者问题有两组并发进程：读者和写者,共享一个文件 F,要求：
允许多个读者同时执行读操作
任一写者在完成写操作之前不允许其它读者或写者工作
写者执行写操作前,应让已有的写者和读者全部退出记录型信号量解决读者写者问题
var rc,wc,integer:=0;
W,R,semaphore;
rc,= 0; /* 读进程计数 */
W,= 1;
R,= 1;
procedure read;
begin
P(R);
rc,= rc + 1;
i f r c = 1 t h e n P ( W ) ；
V(R);
读文件；
P(R);
rc,= rc - 1;
i f r c = 0 t h e n V ( W ) ；
V(R);
end;
procedure writ e;
begin
P(W);
写文件 ;
V(W);
end;
理发师问题
理发店理有一位理发师,一把理发椅和 n
把供等候理发的顾客坐的椅子
如果没有顾客,理发师便在理发椅上睡觉
当一个顾客到来时,它必须叫醒理发师
如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,他们就坐下来等待,
否则就离开记录型信号量解决理发师问题
var waiting,integer; /*等候理发的顾客数
CHAIRS:integer; /*为顾客准备的椅子数
customers,barbers,mutex,semaphore;
customers,= 0; barbers,= 0; waiting,= 0; mutex,= 1;
Procedure barber;
begin
while(TRUE); /*理完一人,还有顾客吗?
P(cutomers); /*若无顾客,理发师睡眠
P(mutex); /*进程互斥
waiting,= waiting – 1; /*等候顾客数少一个
V(barbers); /*理发师去为一个顾客理发
V(mutex); /*开放临界区
cut-hair( ); /*正在理发
end;
procedure customer
begin
P(mutex); /*进程互斥
if waiting<CHAIRS begin /*看看有没有空椅子
waiting,= waiting+1; /* 等候顾客数加 1
V(customers); /*必要的话唤醒理发师
V(mutex); /*开放临界区
P(barbers); /*无理发师,顾客坐着养神
get-haircut( ); /*一个顾客坐下等理发
end
V(mutex); /*人满了,走吧 !
end;
同时型信号量
procedure SP(Var s1,．．,sn,semaphore)
begin
if s1>=1 &,．,& sn>=1 then begin
for i:= 1 to n do si:= si-1;
end else begin
进程进入第一个迂到的满足 si<1条件的 si信号量队列等待,
同时将该进程的程序计数器地址回退,置为 SP操作处 。
end
end
procedure VP(Var s1,．．,sn,semaphore)
begin
for i:=1 to n do begin
si:=si+1;
从所有 si信号量等待队列中移出进程并置入就绪队列 。
end
end
把进程在整个运行其间所要的临界资源,一次性全部分配给进程,待该进程使用完临界资源后再全部释放同时型信号量解决生产者消费者问题
var B,arrary [0,… k - 1] of item;
sput,s e m a p h o r e,= k ; / * 可以使用的空缓冲区数 * /
sget:semaphore:=0; / * 缓冲区内可以使用的产品数 * /
mutex:semaphore:=1; /* 互斥信号量
s p u t,= k ; / * 缓冲区内允许放入产品数 * /
sget,= 0; / * 缓冲区内没有产品 * /
in:integer:= 0;
out:integer:= 0;
process producer_i
begin
L1:produce a produc t ；
SP(sput,mutex);
B[in],= product ；
in:=(in+1) mod k;
SV(mutex,sget);
goto L1;
end;
process consumer_j
begin
L2:SP(sget,mutex);
Product:= B[out] ；
out:=(out+1) mod k;
SV(mutex,sput);
consume a product ；
goto L2;
end;
一般型信号量及其应用
procedure SP(s1,t1,d1;…,sn,tn,dn)
var s1,… sn:semaphore; t1,… tn:integer; d1,… dn:integer;
begin
if s1>=t1& … &sn>=tn then begin
for i,=1 to n do si:=si-di;
end else begin
进程进入第一个迂到的满足 si<ti条件的 si信号量队列等待,
同时将该进程的程序计数器地址回退,置为 SP操作处 。
end
end
procedure SV((s1,d1;… sn,dn)
var s1,… sn:semaphore; d1,… dn:integer;
begin
for i:=1 to n do begin
si:=si+di;
从所有 si信号量等待队列中移出进程并置入就绪队列 。
end
End
对同时型信号量进行扩充,允许一次申请多个资源一般信号量的一些特殊情况：
SP(s,d,d) 此时在信号量集合中只有一个信号量,即仅处理一种临界资源,但允许每次可以申请 d个,当资源数少于 d个时,不予分配 。
SP(s,1,1) 此时信号量集合已蜕化为记录型信号量 (当 s>1时 )或互斥信号量 (s=1时 )。
SP(s,1,0) 这是一个特殊且很有用的信号量,当 s>=1时,允许多个进程进入指定区域；
当 s变成 0后,将阻止任何进程进入该区域 。 也就是说,它成了一个可控开关 。
一般型信号量解决读者写者问题
v a r rn,i n t e g e r;
L,s e m a p h o re,= rn ;
W,s e m a p h o re,= 1 ;
p ro c e s s re a d e r
b e g i n
re p e a t
S P (L,1,1 );
S P (W,1,0 );
R e a d t h e fi l e ;
S V (L,1 );
U n t i l fa l s e ;
e n d
p ro c e s s w ri t e r
b e g i n
re p e a t
S P (W,1,1 ; L,rn,0 );
W ri t e t h e fi l e ;
S V (W,1 );
U n t i l fa l s e ;
en d
记录型信号量及其应用
二元信号量
同时型信号量及其应用
一般型信号量及其应用
3.3.1 同步和同步机制
著 名 的 生 产 者 --消费者 ( Producer-
Consumer Problem) 问题是计算机操作系统中并发进程内在关系的一种抽象,
是典型的进程同步问题 。 在操作系统中,
生产者进程可以是计算进程,发送进程；
而消费者进程可以是打印进程,接收进程等等 。 解决好了生产者 --消费者问题就解决好了一类并发进程的同步问题 。
生产者 --消费者问题表述如下：
有 n个生产者和 m个消费者,连接在一个有 k个单位缓冲区的有界缓冲上,
故又叫有界缓冲问题 。 其中,pi和 cj
都是并发进程,只要缓冲区未满,
生产者 pi生产的产品就可投入缓冲区；类似地,只要缓冲区不空,消费者进程 cj就可从缓冲区取走并消耗产品 。
可以把生产者 -消费者问题的算法描述如下：
var k:integer;
type item:any;
buffer:array[0..k-1]of item;
in,out:integer:=0;
coumter:integer:=0;
process producer
while (TRUE) /*无限循环
produce an item in nextp; /*生产一个产品
if (counter==k) sleep( ); /*缓冲满时,生产者睡眠
buffer[in]:=nextp; /*将一个产品放入缓冲区
in:=(in+1) mod k; /*指针推进
counter:=counter+1; /*缓冲内产品数加 1
if (counter==1) wakeup( consumer); /* 缓冲为空了,加进一件产品并唤醒消费者
process consumer
while (TRUE) /* 无限循环
if (counter==0) sleep ( ); /* 缓冲区空,消费者睡眠
nextc:=buffer[out]; /* 取一个产品到 nextc
out:=(out+1) mod k; /* 指针推进
counter:=counter-1; /* 取走一个产品,计数减 1
if (counter==k-1) wakeup( producer); /*
缓冲满了,取走一件产品并唤醒生产者
consume thr item in nextc; /* 消耗产品
生产者和消费者进程对 counter
的交替执行会使其结果不唯一
生产者和消费者进程的交替执行会导致进程永远等待，造成系统死锁
前一节介绍的种种方法虽能保证互斥,
可正确解决临界区调度问题,但有明显缺点 。 对不能进入临界区的进程,采用忙式等待 (busy waiting)测试法,浪费
CPU时间 。 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性,加重了用户编程负担 。
1965年荷兰的计算机科学家
E.W.Dijkstra提出了新的同步工具 --信号量和 P,V操作。
记录型信号量与 PV操作
信号量：一种软资源
原语：执行时不可被中断的过程
P操作原语和 V操作原语
信号量按其用途可分为两种：
公用信号量：联系一组并发进程,相关的进程均可在此信号量上执行 P和 V操作 。 初值常常为 1，
用于实现进程互斥 。
私有信号量：联系一组并发进程,仅允许此信号量拥有的进程执行 P操作,而其他相关进程可在其上施行 V操作 。 初值常常为 0或正整数,多用于并发进程同步 。
信号量按其取值可分为两种：
二元信号量：仅允许取值为 0和 1,主要用于解决进程互斥问题 。
一般信号量：允许取值为非负整数,主要用于解决进程间的同步问题 。
1、整型信号量
设 s为一个正整形量,除初始化外,仅能通过 P,V
操作来访问它,这时 P操作原语和 V操作原语定义如下,。
P(s)； 当信号量 s大于 0时,把信号量 s减去 l，
否则调用 P(s)的进程等待直到信号量 s大于 0时 。
V(s),把信号量 s加 1。
P(s) 和 V(s) 可以写成：
P(s),while s≤ 0 do null operation
s,=s-1；
V(s),s,=s+1；
2、记录型信号量
设 s为一个记录型数据结构,其中一个分量为整形量 value,另一个分量为信号量队列 queue,这时 P操作原语和 V操作原语的定义修改如下：
P(s)； 将信号量 s减去 l,若结果小于 0，
则调用 P(s)的进程被置成等待信号量 s的状态 。
V(s),将信号量 s加 1,若结果不大于 0，
则释放一个等待信号量 s的进程 。
记录型信号量和 P操作,V操作可表示成如下的数据结构和不可中断过程：
记录型信号量与 PV操作
type semaphore = record
value:integer;
queue,list of process;
end
procedure P(var s:semaphore);
begin
s,= s – 1; /* 把信号量减去 1 */
if s < 0 then W(s); /* 若信号量小于 0,则调用 P(s)的进程被置成等待信号量 s的状态 */
end;
procedure V(var s:semaphore);
begin
s,= s + 1; /* 把信号量加 1 */
if s <= 0 then R(s); /* 若信号量小于等于 0,则释放一个等待信号量 s的进程 */
end;
记录型信号量与 PV操作
推论 1：若信号量 s为正值,则该值等于在封锁进程之前对信号量 s可施行的 P操作数,亦等于 s所代表的实际还可以使用的物理资源数
推论 2：若信号量 s为负值,则其绝对值等于登记排列在该信号量 s队列之中等待的进程个数,亦即恰好等于对信号量 s实施 P操作而被封锁起来并进入信号量 s队列的进程数
推论 3：通常,P操作意味着请求一个资源,V
操作意味着释放一个资源 。 在一定条件下,P
操作代表挂起进程操作,而 V操作代表唤醒被挂起进程的操作
3、二元信号量
设 s为一个记录型数据结构,其中一个分量为
value,它仅能取值 0和 1,另一个分量为信号量队列 queue,这时我们把二元信号量上的 P、
V操作记为 BP和 BV,BP操作原语和 BV操作原语的定义如下：
type binary semaphore=record
value(0,1);
queue,list of process
end;
type binary semaphore=record
value(0,1);
queue,list of process
end;
procedure BP(var s:semaphore);
if s.value=1;
then
s.value=0;
else begin
w(s.queue);
end;
procedure BV(var s:semaphore);
if s.queue is empty;
then
s.value=1;
else begin
R(s.queue);
End;
记录型信号量解决进程互斥问题
s,semaphore;
s,= 1;
cobegin
……
process Pi
begin
……
P(s);
临界区；
V(s);
……
end;
……
coend;
记录型信号量解决机票问题
A,A R R A Y [ 1,,m ] O F i n t e g e r ;
s,semaphore;
s,= 1;
cobegin
process Pi
var Xi:integer;
begin
L1,
按旅客定票要求找到 A[j] ；
P(s)
Xi,= A[j];
If Xi>=1
then begin
Xi:=Xi - 1 ; A [ j ],= X i ;
V(s); 输出一张票 ；
end;
else begin
V(s); 输出票已售完 ；
end;
goto L1;
end;
coend;
A,A R R A Y [ 1,,m ] O F i n t e g e r ;
s,A R R A Y [ 1,,m ] O F e m a p h o r e ;
s[j],= 1;
cobegin
process Pi
var Xi:integer;
begin
L1,
按旅客定票要求找到 A[j] ；
P(s[j])
Xi,= A[j];
If Xi>=1
then begin
Xi:=Xi - 1 ; A [ j ],= X i ;
V(s[j]); 输出一张票 ；
end;
else begin
V(s[j]); 输出票已售完 ；
end;
goto L1;
e nd;
coend;
哲学家吃通心面 问题有五个哲学家围坐在一圆桌旁,桌中央有一盘通心面,每人面前有一只空盘于,每两人之间放一把叉子 。 每个哲学家思考,饥饿,然后吃通心面 。 为了吃面,每个哲学家必须获得两把叉子,且每人只能直接从自己左边或右边去取叉子哲学家吃通心面问题
var forki,array[0..4] of semaphore;
forki,= 1;
cobegin
process Pi // i=0,1,2,3,4,
begin
L1:
思考；
P(fork[i])；
P(fork[(i+1)mod 5])；
吃通心面；
V(fork[i])；
V(fork[(i+1)mod 5])；
goto L1;
end;
coend;
有若干种办法可避免这类死锁：
至多允许四个哲学家同时吃；
奇数号先取左手边的叉子,偶数号先取右手边的叉子；
每个哲学家取到手边的两把叉子才吃,否则一把叉子也不取 。
哲学家吃通心面问题
var forki,array[0..4] of semaphore;
forki,= 1;
cobegin
process Pi // i=0,1,2,3,4,
begin
L1:
思考；
P(fork[i])； // i=4,P(fork[0])
P(fork[i+1])； // i=4,P(fork[4])
吃通心面；
V(fork[i])；
V(fork[(i+1)mod 5])；
goto L1;
end;
coend;
生产者消费者问题
生产者和消费者共享缓冲区
缓冲区空时,生产者可放入产品 （ 不许放重 ）,否则等待
缓冲区中有产品时,消费者可取出产品 （ 不许取重 ）,否则等待
① 一个生产者,一个消费者共享一个缓冲区
② 一个生产者,一个消费者共享多个缓冲区
③ 多个生产者,多个消费者共享多个缓冲区
④ 多个生产者,多个消费者共享一个缓冲区
⑤ 多个生产者,一个消费者共享多个缓冲区
⑥ 一个生产者,多个消费者共享多个缓冲区生产者消费者问题
B,integer;
process producer
begin
L1,
produce a product ；
B,= product ；
goto L1;
end;
process consumer
begin
L2,
product:= B ；
consume a product ；
goto L2;
end;
记录型信号量解决生产者消费者问题
B,integer;
sput:semaphore ； / * 可以使用的空缓冲区数 * /
sget:sema p h o r e ; / * 缓冲区内可以使用的产品数 * /
s p u t,= 1 ; / * 缓冲区内允许放入一件产品 * /
sget,= 0; /* 缓冲区内没有产品 */
process producer
begin
L1,
produce a product ；
P(sput);
B,= product ；
V(sget);
goto L1;
end;
process consumer
begin
L2,
P(sget);
product:= B ；
V(sput);
consume a product ；
goto L2;
end;
记录型信号量解决生产者消费者问题
B,ARRAY[0..k - 1] OF integer;
sput:semaphore ； / * 可以使用的空缓冲区数 * /
sget:sema p h o r e ; / * 缓冲区内可以使用的产品数 * /
s p u t,= k ; / * 缓冲区内允许放入 k 件产品 * /
sget,= 0; /* 缓冲区内没有产品 */
putptr,getptr,integer;
putptr,= 0; getptr,= 0;
process producer_i
begin
L1:produce a p r o d u c t ；
P(sput);
B[putptr],= p r o d u c t ；
p u t p t r,= ( p u t p t r + 1 ) m o d k ;
V(sget);
goto L1;
end;
process consumer_j
begin
L2:P(sget);
Product:= B[getptr] ；
g e t p t r,= ( g e t p t r + 1 ) m o d k ;
V(sput);
consume a product ；
goto L2;
end;
记录型信号量解决生产者消费者问题
B,ARRAY[0..k - 1] OF integer;
sput:semaphore ； / * 可以使用的空缓冲区数 * /
sget:sema p h o r e ; / * 缓冲区内可以使用的产品数 * /
s p u t,= k ; / * 缓冲区内允许放入 k 件产品 * /
sget,= 0; /* 缓冲区内没有产品 */
putptr,getptr,integer;
putptr,= 0; getptr,= 0;
s:semaphore ； / * 互斥使用 putptr,getptr */
s,= 1 ；
process producer_i
begin
L1:produce a p r o d u c t ；
P(sput);
P(s);
B[putptr],= p r o d u c t ；
p u t p t r,= ( p u t p t r + 1 ) m o d k ;
V(s);
V(sget);
goto L1;
end;
process consumer_j
begin
L2:P(sget );
P(s);
Product:= B[getptr] ；
g e t p t r,= ( g e t p t r + 1 ) m o d k ;
V(s);
V(sput);
consume a product ；
goto L2;
end;
苹果桔子问题桌上有一只盘子,每次只能放入一只水果；爸爸专向盘子中放苹果 (apple)，
妈妈专向盘子中放桔于 (orange),一个儿子专等吃盘子中的桔子,一个女儿专等吃盘子里的苹果记录型信号量解决苹果桔子问题
plate,integer;
sp:semaphore； /* 盘子里可以放几个水果 */
sg1:semaphore; /* 盘子里有桔子 */
sg2:semaphore; /* 盘子里有苹果 */
sp,= 1; /* 盘子里允许放入一个水果 */
sg1,= 0; /* 盘子里没有桔子 */
sg2,= 0; /* 盘子里没有苹果 */
cobegin
process father
begin
L1,削一个苹果；
P(sp);
把苹果放入 plate；
V(sg2);
goto L1;
end;
process mother
begin
L2,剥一个桔子；
P(sp);
把桔子放入 plate；
V(sg1);
goto L2;
end;
process son
begin
L3,P(sg1);
从 plate中取桔子；
V(sp);
吃桔子；
goto L3;
end;
process daughter
begin
L4,P(sg2);
从 plate中取苹果；
V(sp);
吃苹果；
goto L4;
end;
coend
读者写者问题有两组并发进程：读者和写者,共享一个文件 F,要求：
允许多个读者同时执行读操作
任一写者在完成写操作之前不允许其它读者或写者工作
写者执行写操作前,应让已有的写者和读者全部退出记录型信号量解决读者写者问题
var rc,wc,integer:=0;
W,R,semaphore;
rc,= 0; /* 读进程计数 */
W,= 1;
R,= 1;
procedure read;
begin
P(R);
rc,= rc + 1;
i f r c = 1 t h e n P ( W ) ；
V(R);
读文件；
P(R);
rc,= rc - 1;
i f r c = 0 t h e n V ( W ) ；
V(R);
end;
procedure writ e;
begin
P(W);
写文件 ;
V(W);
end;
理发师问题
理发店理有一位理发师,一把理发椅和 n
把供等候理发的顾客坐的椅子
如果没有顾客,理发师便在理发椅上睡觉
当一个顾客到来时,它必须叫醒理发师
如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,他们就坐下来等待,
否则就离开记录型信号量解决理发师问题
var waiting,integer; /*等候理发的顾客数
CHAIRS:integer; /*为顾客准备的椅子数
customers,barbers,mutex,semaphore;
customers,= 0; barbers,= 0; waiting,= 0; mutex,= 1;
Procedure barber;
begin
while(TRUE); /*理完一人,还有顾客吗?
P(cutomers); /*若无顾客,理发师睡眠
P(mutex); /*进程互斥
waiting,= waiting – 1; /*等候顾客数少一个
V(barbers); /*理发师去为一个顾客理发
V(mutex); /*开放临界区
cut-hair( ); /*正在理发
end;
procedure customer
begin
P(mutex); /*进程互斥
if waiting<CHAIRS begin /*看看有没有空椅子
waiting,= waiting+1; /* 等候顾客数加 1
V(customers); /*必要的话唤醒理发师
V(mutex); /*开放临界区
P(barbers); /*无理发师,顾客坐着养神
get-haircut( ); /*一个顾客坐下等理发
end
V(mutex); /*人满了,走吧 !
end;
同时型信号量
procedure SP(Var s1,．．,sn,semaphore)
begin
if s1>=1 &,．,& sn>=1 then begin
for i:= 1 to n do si:= si-1;
end else begin
进程进入第一个迂到的满足 si<1条件的 si信号量队列等待,
同时将该进程的程序计数器地址回退,置为 SP操作处 。
end
end
procedure VP(Var s1,．．,sn,semaphore)
begin
for i:=1 to n do begin
si:=si+1;
从所有 si信号量等待队列中移出进程并置入就绪队列 。
end
end
把进程在整个运行其间所要的临界资源,一次性全部分配给进程,待该进程使用完临界资源后再全部释放同时型信号量解决生产者消费者问题
var B,arrary [0,… k - 1] of item;
sput,s e m a p h o r e,= k ; / * 可以使用的空缓冲区数 * /
sget:semaphore:=0; / * 缓冲区内可以使用的产品数 * /
mutex:semaphore:=1; /* 互斥信号量
s p u t,= k ; / * 缓冲区内允许放入产品数 * /
sget,= 0; / * 缓冲区内没有产品 * /
in:integer:= 0;
out:integer:= 0;
process producer_i
begin
L1:produce a produc t ；
SP(sput,mutex);
B[in],= product ；
in:=(in+1) mod k;
SV(mutex,sget);
goto L1;
end;
process consumer_j
begin
L2:SP(sget,mutex);
Product:= B[out] ；
out:=(out+1) mod k;
SV(mutex,sput);
consume a product ；
goto L2;
end;
一般型信号量及其应用
procedure SP(s1,t1,d1;…,sn,tn,dn)
var s1,… sn:semaphore; t1,… tn:integer; d1,… dn:integer;
begin
if s1>=t1& … &sn>=tn then begin
for i,=1 to n do si:=si-di;
end else begin
进程进入第一个迂到的满足 si<ti条件的 si信号量队列等待,
同时将该进程的程序计数器地址回退,置为 SP操作处 。
end
end
procedure SV((s1,d1;… sn,dn)
var s1,… sn:semaphore; d1,… dn:integer;
begin
for i:=1 to n do begin
si:=si+di;
从所有 si信号量等待队列中移出进程并置入就绪队列 。
end
End
对同时型信号量进行扩充,允许一次申请多个资源一般信号量的一些特殊情况：
SP(s,d,d) 此时在信号量集合中只有一个信号量,即仅处理一种临界资源,但允许每次可以申请 d个,当资源数少于 d个时,不予分配 。
SP(s,1,1) 此时信号量集合已蜕化为记录型信号量 (当 s>1时 )或互斥信号量 (s=1时 )。
SP(s,1,0) 这是一个特殊且很有用的信号量,当 s>=1时,允许多个进程进入指定区域；
当 s变成 0后,将阻止任何进程进入该区域 。 也就是说,它成了一个可控开关 。
一般型信号量解决读者写者问题
v a r rn,i n t e g e r;
L,s e m a p h o re,= rn ;
W,s e m a p h o re,= 1 ;
p ro c e s s re a d e r
b e g i n
re p e a t
S P (L,1,1 );
S P (W,1,0 );
R e a d t h e fi l e ;
S V (L,1 );
U n t i l fa l s e ;
e n d
p ro c e s s w ri t e r
b e g i n
re p e a t
S P (W,1,1 ; L,rn,0 );
W ri t e t h e fi l e ;
S V (W,1 );
U n t i l fa l s e ;
en d
