Cha4 并发性：互斥和同步并发 (concurrency)导致的问题
资源共享引起的危险
最佳资源分配
难以定位程序错误进程的相对执行速度不可预测回显字符的 Echo过程
Void echo()
{
In=getchar();
Chout=chin;
Putchar(chout);
}
P1P2
共享资源的问题
Process p1
.
chin=getchar();
.
.
.
Chout=chin;
Putchar(chout);
Process p2
.
,
chin=getchar();
Chout=chin;
Putchar(chout);
.
a
b
b
b
OS需要管理的问题
能够记住所有进程
为每个进程分配资源
– CPU,内存，文件,I/O设备
保护进程的数据和物理资源
保证进程结果与执行速度无关进程的交互知道程度 关系 对其他进程的影响潜在问题相互不知道 竞争 结果无影响计时受影响互斥死锁饿死间接知道对方
－共享对象通过共享合作 结果受影响计时受影响互斥死锁饿死数据一致性直接知道对方
－通信原语通过通信合作 结果受影响计时受影响死锁饿死进程中的资源争用
I/O设备，内存,CPU……
临界资源与临界区 critical section
互斥 mutual exclusion
– 多个进程不能同时使用临界资源
死锁 deadlock
– 多个进程循环等待对方占用的资源
– 全部处于阻塞状态
饥饿 starvation
– 临界资源只被部分进程轮流使用
– 有的进程永远无法获得进程中的资源争用
P1 P2
互斥
P1 P2
R1
R2死锁
P1 P2 P3
R1 饥饿互斥机制
Const int n=进程数
Void p(int i)
{while true
{entercritical (i);
临界区
Exitcritical (i);
…}}
Void main()
{parbegin (p(R1),p(R2),…,p(Rn))}
进程通过共享合作
P1
a=a+1；
b=b+1;
P2
b=2*b；
a=2*a;
写操作的互斥
数据的一致性共享的变量、文件、数据库 ……
进程间通过通信的合作
P1 P2
P1
P2
P3
死锁饥饿互斥的要求
每次只有一个进程进入临界区
没有进程在临界区内时其他进程可以进入
需要进入临界区的进程不会被无限延迟
进程在临界区停留时间有限
在非临界区停止的进程不影响其他进程
对相关进程的速度和处理器数量没有限制互斥的实现软件方法 dekker算法peterson算法机器指令 中断禁用专门的机器指令由 OS或程序语言提供支持信号量管程消息
Dekker算法 1－用 turn表示进入次序
P0
…
While turn<>0;
临界区；
Turn=1;
…
P1
…
While turn<>1;
临界区；
Turn=0;
…
必须轮流使用临界区
如果 P0失败,P1会永久阻塞忙等待
busy waiting
Dekker算法 2－用 flag表示各自状态
P0
…
While flag[1];
Flag[0]=true;
临界区；
Flag[0]=false;
…
P1
…
While flag[0];
Flag[1]=true;
临界区；
Flag[1]=false;
…
如果 P0在临界区内失败,P1会永久阻塞
不能保证互斥
1
2
3
4
a
b
c
d
1
a
2
b
3
c
Dekker算法 3－先表明意愿再检查
P0
…
Flag[0]=true;
While flag[1];
临界区；
Flag[0]=false;
…
P1
…
Flag[1]=true;
While flag[0];
临界区；
Flag[1]=false;
…
如果 P0在临界区内失败,P1会永久阻塞
可能导致死锁
1
2
3
4
a
b
c
d
1
a
2
b
Dekker算法 4－根据对方状态决定是否让步
P0
…
Flag[0]=true;
While flag[1];
{Flag[0]=false;
Delay;
Flag[0]=true;
}
临界区；
Flag[0]=false;
…
P1
…
Flag[1]=true;
While flag[0];
{Flag[1]=false;
Delay;
Flag[1]=true;
}
临界区；
Flag[1]=false;
…
活锁
Dekker算法更正 －用 turn表示该谁坚持
P0
…
While true
{Flag[0]=true;
While flag[1]
If turn == 1
{flag[0]=false；
While turn==1;
flag[0]=true； }
临界区；
Turn=1;
Flag[0]=false;
}
P1
…
While true
{Flag[1]=true;
While flag[0]
If turn == 0
{flag[1]=false；
While turn==0;
flag[1]=true； }
临界区；
Turn=0;
Flag[1]=false;
}
我想进入临界区如果对方也想，则如果该 P0坚持，则我暂时让步等待对方退出然后我再表明意愿现在允许 P0进入
peterson算法
P0
…
While true
{Flag[0]=true;
turn=1;
While flag[1] & turn==1;
临界区；
Flag[0]=false;
}
P1
…
While true
{Flag[1]=true;
turn=0;
While flag[0] & turn==0;
临界区；
Flag[1]=false;
}
硬件支持－中断禁用
While true
{禁止中断；
临界区；
启用中断；
……
}
执行效率低
不适合多处理器系统硬件支持－机器指令
Boolean testset(int i)
{ if i==0
{i=1;
Return true;}
Else
return false;
}
i=0时，改为 1，通过
i=1时，不通过实现互斥 1
Const int n=进程数；
Int bolt;
void p(int i)
{while true
{while !testset(bolt);
临界区；
bolt=0;}}
void main()
{bolt=0;
Parbegin (p(1),p(2),…p(n))}
bolt=0时，
改为 1，通过
bolt=1时，
不通过硬件支持－机器指令
void exchange(int reg,int mem)
{ int temp;
Temp=mem;
Mem=reg;
Reg=temp;
}
交换两个参数值实现互斥 2
Const int n=进程数；
Int bolt;
void p(int i)
{int keyi;
while true
{keyi=1;
while keyi<>0 exchange(keyi,bolt);
临界区；
exchange(keyi,bolt);}}
void main()
{bolt=0;
Parbegin (p(1),p(2),…p(n))}
bolt=0时，
改为 1，通过
bolt=1时，
不通过机器指令方法
适合多处理器
进程数目不限
容易证明
支持多临界区
使用忙等待
可能饿死
可能死锁信号量方法
多个进程可以通过信号实现合作
一个进程可以被迫停止，直到收到某信号才能继续发送信号 signal(s)
接收信号 wait(s)
s代表临界资源 (的数量 )
原理
signal(s)
– 进程释放一个临界资源 （ s数量加 1）
– S>0 资源有剩余 (继续 )
– S=0 资源正好够用 (唤醒一个进程 )
– S<0 资源仍然不够用 (唤醒一个进程 )
Wait(s)
– 假设给进程分配一个临界资源 (s数量减 1)
– S>0 资源有剩余 (继续 )
– S=0 资源正好用完 (继续 )
– S<0 资源不够用 (阻塞进程 )
信号量的操作
wait(s)
- -s
继续执行进程阻塞
S>=0
S<0
signal(s)
+ +s 唤醒一个进程继续执行
S<=0
S>0
原语－执行过程不可中断原语定义
Structure semaphore
{int count;
Queue type que;}
Void wait(semaphore s)
{s.count--;
If (s.count<0)
{该进程放入 s.que
阻塞该进程 }}
Void signal(semaphore s)
{s.count++;
If (s.count<=0)
{从 s.que挑选某进程唤醒该进程 }}
资源剩余数量等待该资源的进程二元信号量原语的定义
Structure binary_semaphore
{enum (0,1) value;
Queue type que;}
Void waitb(binary_semaphore s)
{s.count--;
If (s.value=1)
s.value=0
Else {该进程放入 s.que
阻塞该进程 }}
二元信号量原语的定义
Void signal(binary_semaphore s)
{s.count++;
If s.que.is_empty()
s.value=1;
Else {从 s.queue挑选某进程该进程就绪 }}
信号量中的队列
强信号量－按先进先出次序唤醒
弱信号量－未规定唤醒次序
D
A
B
C
初始 s＝ 1
信号量机制的使用
A
S=0 C D B
B
就绪队列挂起队列
B
S=-1
D
S=0
A C D
S=1
D
0
A C
执行 A
执行 B
执行 D
唤醒 B
B A C
信号量机制的使用
C
S=-1 D B A
S=-3B A C
D
S=-2
D
执行 C
执行 AB
执行 D
B A C
使用信号量的互斥
Const int n=进程数
Semaphore s=1;
Void p(int i)
{while true
{ wait(s);
临界区；
Signal(s);
……}}
Void main()
{parbegin
(p(1),p(2),…p(n));}
访问共享数据
0
1
0
0
0
Wait(lock)
Wait(lock)
Wait(lock)
signal(lock)
1
signal(lock)
signal(lock)
A B C
0
B
B C
C
临界区生产者 /消费者问题
producer:
while true
{生产产品 v；
b[in]=v;
in++;}
consumer:
while true
{while in<=out;
w=b[out];
out++;
消费产品 v;}
b[1] b[2] b[3] ……
out in
使用二元信号量解决
int n;
binary_semaphore s=1;
binary_semaphore delay=0;
void producer()
{ produce();
waitb(s);
append();
n++;
if n==1 signalb(delay);
signalb(s); }
void consumer()
{ waitb(delay);
{waitb(s);
take();
n--;
signalb(s);
consume();
if n ==0 waitb(delay); }}
可能的情况生产者 消费者 s n delay
1 0 0
1 waitb(s); 0 0 0
2 n++; 0 1 0
3 if n==1 signalb(delay); 0 1 1
4 signalb(s); 1 1 1
5 waitb(delay); 1 1 0
6 waitb(s); 0 1 0
7 n--; 0 0 0
8 signalb(s); 1 0 0
9 waitb(s); 0 0 0
10 n++; 0 1 0
可能的情况生产者 消费者 s n delay
11 if n==1
signalb(delay);
0 1 1
12 signalb(s); 1 1 1
13 If n==0 waitb(delay); 1 1 1
14 waitb(s); 0 1 1
15 n--; 0 0 1
16 signalb(s); 1 0 1
17 If n==0 waitb(delay); 1 0 0
18 waitb(s); 0 0 0
19 n--; 0 -1 0
20 signalb(s); 1 -1 0
使用二元信号量解决
int n;
binary_semaphore s=1;
binary_semaphore delay=0;
void producer()
{ produce();
waitb(s);
append();
n++;
if n==1
signalb(delay);
signalb(s); }
void consumer()
{int m;
waitb(delay);
waitb(s);
take();
n--;
m=n;
signalb(s);
consume();
if m==0 waitb(delay); }
使用一般 信号量解决
semaphore n=0;
semaphore s=1;
void producer()
{while true
{produce();
wait (s);
append();
signal(s);
signal(n); }}
void consumer()
{while true
{wait(n);
wait(s);
take();
signal(s);
consume();}}
void main()
{parbegin
(producer,consumer);}
有限缓冲区
producer:
while true
{生产产品 v；
while ((in+1)%n==out);
b[in]=v;
in=(in+1)%n;}
consumer:
while true
{while in==out;
w=b[out];
out=(out+1)%n;
消费产品 v;}
b[1] b[2] b[3] … b[n] b[1] b[2] b[3] … b[n]
out in in out
信号量－有限缓冲区
const int sob=长度；
semaphore n=0;
semaphore s=1;
semaphore e=sob;
void producer()
{while true
{produce();
wait(e);
wait (s);
append();
signal(s);
signal(n); }}
void consumer()
{while true
{wait(n);
wait(s);
take();
signal(s);
signal(e) ;
consume();}}
void main()
{parbegin
(producer,consumer);}
信号量的实现－ testset
wait(s)
{while (!testset(s.flag));
s.count--;
if (s.count<0)
{该进程 → s.queue;
阻塞该进程 ;}
else s.flag=0;
}
signal(s)
{while (!testset(s.flag));
s.count++;
if (s.count<=0)
{从 s.queue选取某进程 ;
唤醒该进程 ;}
s.flag=0;
}
信号量的实现－中断
wait(s)
{禁止中断；
s.count--;
if (s.count<0)
{该进程 → s.queue;
阻塞该进程 ;
允许中断； }
else 允许中断 ;
}
signal(s)
{禁止中断；
s.count++;
if (s.count<=0)
{从 s.queue选取某进程 ;
唤醒该进程 ;}
允许中断；
}
理发店问题
semaphore max_capacity=20; 店内允许的最大客户数
semaphore sofa=3; 沙发可坐人数
semaphore barber_chair=3; 椅子数
semaphore coord=3; 理发师数
semaphore
cust_ready=0,finished=0,leave_b_chair=0,payment=0,receipt=0;
不公平的理发店 1
void customer()
{wait(max_capacity);
进店；
wait(sofa);
坐沙发 ;
wait(barber_chair);
离开沙发；
signal(sofa);
坐椅子
signal(cust_ready)
wait(finished);
离开椅子；
signal(leave_b_chair);
付款；
signal(payment);
wait(receipt);
离店；
signal(max_capacity);
}
不公平的理发店 2
void barber()
{while true
{wait(cust_ready);
wait(coord);
理发；
signal(coord);
signal(finished);
wait(leave_b_chair);
signal(barber_chair);
}}
void cashier()
{while true
{wait(payment);
wait(coord);
收款；
signal(coord);
signal(receipt);}}
公平的理发店 1
semaphore max_capacity=20;
semaphore sofa=3;
semaphore barber_chair=3;
semaphore coord=3;
semaphore
cust_ready=0,finished=0,leave_b_chair=0,paym
ent=0,receipt=0;
semaphore mutex1=1,mutex2=1;
semaphore finished[50]={0};
int count;
公平的理发店 2
void customer()
{int custnr;
wait(max_capacity);
进店；
wait(mutex1);
count++;
custnr=count;
signal(mutex1);
wait(sofa);
坐沙发 ;
wait(barber_chair);
离开沙发；
signal(sofa);
坐椅子
wait(mutex2);
enqueue(custnr);
signal(cust_ready);
signal(mutex2);
Wait (finished[custnr]);
离开椅子；
signal(leave_b_chair);
付款；
signal(payment);
wait(receipt);
离店；
signal(max_capacity);
}
公平的理发店 3void barber()
{int b_cust;
while true
{ wait(cust_ready);
Wait(mutex2);
Dequeue(b_cust);
Signal(mutex2);
wait(coord);
理发；
signal(coord);
signal(finished[b_cust]);
wait(leave_b_chair);
signal(barber_chair);
}}
void cashier()
{while true
{wait(payment);
wait(coord);
收款；
signal(coord);
signal(receipt);}}
资源共享引起的危险
最佳资源分配
难以定位程序错误进程的相对执行速度不可预测回显字符的 Echo过程
Void echo()
{
In=getchar();
Chout=chin;
Putchar(chout);
}
P1P2
共享资源的问题
Process p1
.
chin=getchar();
.
.
.
Chout=chin;
Putchar(chout);
Process p2
.
,
chin=getchar();
Chout=chin;
Putchar(chout);
.
a
b
b
b
OS需要管理的问题
能够记住所有进程
为每个进程分配资源
– CPU,内存，文件,I/O设备
保护进程的数据和物理资源
保证进程结果与执行速度无关进程的交互知道程度 关系 对其他进程的影响潜在问题相互不知道 竞争 结果无影响计时受影响互斥死锁饿死间接知道对方
－共享对象通过共享合作 结果受影响计时受影响互斥死锁饿死数据一致性直接知道对方
－通信原语通过通信合作 结果受影响计时受影响死锁饿死进程中的资源争用
I/O设备，内存,CPU……
临界资源与临界区 critical section
互斥 mutual exclusion
– 多个进程不能同时使用临界资源
死锁 deadlock
– 多个进程循环等待对方占用的资源
– 全部处于阻塞状态
饥饿 starvation
– 临界资源只被部分进程轮流使用
– 有的进程永远无法获得进程中的资源争用
P1 P2
互斥
P1 P2
R1
R2死锁
P1 P2 P3
R1 饥饿互斥机制
Const int n=进程数
Void p(int i)
{while true
{entercritical (i);
临界区
Exitcritical (i);
…}}
Void main()
{parbegin (p(R1),p(R2),…,p(Rn))}
进程通过共享合作
P1
a=a+1；
b=b+1;
P2
b=2*b；
a=2*a;
写操作的互斥
数据的一致性共享的变量、文件、数据库 ……
进程间通过通信的合作
P1 P2
P1
P2
P3
死锁饥饿互斥的要求
每次只有一个进程进入临界区
没有进程在临界区内时其他进程可以进入
需要进入临界区的进程不会被无限延迟
进程在临界区停留时间有限
在非临界区停止的进程不影响其他进程
对相关进程的速度和处理器数量没有限制互斥的实现软件方法 dekker算法peterson算法机器指令 中断禁用专门的机器指令由 OS或程序语言提供支持信号量管程消息
Dekker算法 1－用 turn表示进入次序
P0
…
While turn<>0;
临界区；
Turn=1;
…
P1
…
While turn<>1;
临界区；
Turn=0;
…
必须轮流使用临界区
如果 P0失败,P1会永久阻塞忙等待
busy waiting
Dekker算法 2－用 flag表示各自状态
P0
…
While flag[1];
Flag[0]=true;
临界区；
Flag[0]=false;
…
P1
…
While flag[0];
Flag[1]=true;
临界区；
Flag[1]=false;
…
如果 P0在临界区内失败,P1会永久阻塞
不能保证互斥
1
2
3
4
a
b
c
d
1
a
2
b
3
c
Dekker算法 3－先表明意愿再检查
P0
…
Flag[0]=true;
While flag[1];
临界区；
Flag[0]=false;
…
P1
…
Flag[1]=true;
While flag[0];
临界区；
Flag[1]=false;
…
如果 P0在临界区内失败,P1会永久阻塞
可能导致死锁
1
2
3
4
a
b
c
d
1
a
2
b
Dekker算法 4－根据对方状态决定是否让步
P0
…
Flag[0]=true;
While flag[1];
{Flag[0]=false;
Delay;
Flag[0]=true;
}
临界区；
Flag[0]=false;
…
P1
…
Flag[1]=true;
While flag[0];
{Flag[1]=false;
Delay;
Flag[1]=true;
}
临界区；
Flag[1]=false;
…
活锁
Dekker算法更正 －用 turn表示该谁坚持
P0
…
While true
{Flag[0]=true;
While flag[1]
If turn == 1
{flag[0]=false；
While turn==1;
flag[0]=true； }
临界区；
Turn=1;
Flag[0]=false;
}
P1
…
While true
{Flag[1]=true;
While flag[0]
If turn == 0
{flag[1]=false；
While turn==0;
flag[1]=true； }
临界区；
Turn=0;
Flag[1]=false;
}
我想进入临界区如果对方也想，则如果该 P0坚持，则我暂时让步等待对方退出然后我再表明意愿现在允许 P0进入
peterson算法
P0
…
While true
{Flag[0]=true;
turn=1;
While flag[1] & turn==1;
临界区；
Flag[0]=false;
}
P1
…
While true
{Flag[1]=true;
turn=0;
While flag[0] & turn==0;
临界区；
Flag[1]=false;
}
硬件支持－中断禁用
While true
{禁止中断；
临界区；
启用中断；
……
}
执行效率低
不适合多处理器系统硬件支持－机器指令
Boolean testset(int i)
{ if i==0
{i=1;
Return true;}
Else
return false;
}
i=0时，改为 1，通过
i=1时，不通过实现互斥 1
Const int n=进程数；
Int bolt;
void p(int i)
{while true
{while !testset(bolt);
临界区；
bolt=0;}}
void main()
{bolt=0;
Parbegin (p(1),p(2),…p(n))}
bolt=0时，
改为 1，通过
bolt=1时，
不通过硬件支持－机器指令
void exchange(int reg,int mem)
{ int temp;
Temp=mem;
Mem=reg;
Reg=temp;
}
交换两个参数值实现互斥 2
Const int n=进程数；
Int bolt;
void p(int i)
{int keyi;
while true
{keyi=1;
while keyi<>0 exchange(keyi,bolt);
临界区；
exchange(keyi,bolt);}}
void main()
{bolt=0;
Parbegin (p(1),p(2),…p(n))}
bolt=0时，
改为 1，通过
bolt=1时，
不通过机器指令方法
适合多处理器
进程数目不限
容易证明
支持多临界区
使用忙等待
可能饿死
可能死锁信号量方法
多个进程可以通过信号实现合作
一个进程可以被迫停止，直到收到某信号才能继续发送信号 signal(s)
接收信号 wait(s)
s代表临界资源 (的数量 )
原理
signal(s)
– 进程释放一个临界资源 （ s数量加 1）
– S>0 资源有剩余 (继续 )
– S=0 资源正好够用 (唤醒一个进程 )
– S<0 资源仍然不够用 (唤醒一个进程 )
Wait(s)
– 假设给进程分配一个临界资源 (s数量减 1)
– S>0 资源有剩余 (继续 )
– S=0 资源正好用完 (继续 )
– S<0 资源不够用 (阻塞进程 )
信号量的操作
wait(s)
- -s
继续执行进程阻塞
S>=0
S<0
signal(s)
+ +s 唤醒一个进程继续执行
S<=0
S>0
原语－执行过程不可中断原语定义
Structure semaphore
{int count;
Queue type que;}
Void wait(semaphore s)
{s.count--;
If (s.count<0)
{该进程放入 s.que
阻塞该进程 }}
Void signal(semaphore s)
{s.count++;
If (s.count<=0)
{从 s.que挑选某进程唤醒该进程 }}
资源剩余数量等待该资源的进程二元信号量原语的定义
Structure binary_semaphore
{enum (0,1) value;
Queue type que;}
Void waitb(binary_semaphore s)
{s.count--;
If (s.value=1)
s.value=0
Else {该进程放入 s.que
阻塞该进程 }}
二元信号量原语的定义
Void signal(binary_semaphore s)
{s.count++;
If s.que.is_empty()
s.value=1;
Else {从 s.queue挑选某进程该进程就绪 }}
信号量中的队列
强信号量－按先进先出次序唤醒
弱信号量－未规定唤醒次序
D
A
B
C
初始 s＝ 1
信号量机制的使用
A
S=0 C D B
B
就绪队列挂起队列
B
S=-1
D
S=0
A C D
S=1
D
0
A C
执行 A
执行 B
执行 D
唤醒 B
B A C
信号量机制的使用
C
S=-1 D B A
S=-3B A C
D
S=-2
D
执行 C
执行 AB
执行 D
B A C
使用信号量的互斥
Const int n=进程数
Semaphore s=1;
Void p(int i)
{while true
{ wait(s);
临界区；
Signal(s);
……}}
Void main()
{parbegin
(p(1),p(2),…p(n));}
访问共享数据
0
1
0
0
0
Wait(lock)
Wait(lock)
Wait(lock)
signal(lock)
1
signal(lock)
signal(lock)
A B C
0
B
B C
C
临界区生产者 /消费者问题
producer:
while true
{生产产品 v；
b[in]=v;
in++;}
consumer:
while true
{while in<=out;
w=b[out];
out++;
消费产品 v;}
b[1] b[2] b[3] ……
out in
使用二元信号量解决
int n;
binary_semaphore s=1;
binary_semaphore delay=0;
void producer()
{ produce();
waitb(s);
append();
n++;
if n==1 signalb(delay);
signalb(s); }
void consumer()
{ waitb(delay);
{waitb(s);
take();
n--;
signalb(s);
consume();
if n ==0 waitb(delay); }}
可能的情况生产者 消费者 s n delay
1 0 0
1 waitb(s); 0 0 0
2 n++; 0 1 0
3 if n==1 signalb(delay); 0 1 1
4 signalb(s); 1 1 1
5 waitb(delay); 1 1 0
6 waitb(s); 0 1 0
7 n--; 0 0 0
8 signalb(s); 1 0 0
9 waitb(s); 0 0 0
10 n++; 0 1 0
可能的情况生产者 消费者 s n delay
11 if n==1
signalb(delay);
0 1 1
12 signalb(s); 1 1 1
13 If n==0 waitb(delay); 1 1 1
14 waitb(s); 0 1 1
15 n--; 0 0 1
16 signalb(s); 1 0 1
17 If n==0 waitb(delay); 1 0 0
18 waitb(s); 0 0 0
19 n--; 0 -1 0
20 signalb(s); 1 -1 0
使用二元信号量解决
int n;
binary_semaphore s=1;
binary_semaphore delay=0;
void producer()
{ produce();
waitb(s);
append();
n++;
if n==1
signalb(delay);
signalb(s); }
void consumer()
{int m;
waitb(delay);
waitb(s);
take();
n--;
m=n;
signalb(s);
consume();
if m==0 waitb(delay); }
使用一般 信号量解决
semaphore n=0;
semaphore s=1;
void producer()
{while true
{produce();
wait (s);
append();
signal(s);
signal(n); }}
void consumer()
{while true
{wait(n);
wait(s);
take();
signal(s);
consume();}}
void main()
{parbegin
(producer,consumer);}
有限缓冲区
producer:
while true
{生产产品 v；
while ((in+1)%n==out);
b[in]=v;
in=(in+1)%n;}
consumer:
while true
{while in==out;
w=b[out];
out=(out+1)%n;
消费产品 v;}
b[1] b[2] b[3] … b[n] b[1] b[2] b[3] … b[n]
out in in out
信号量－有限缓冲区
const int sob=长度；
semaphore n=0;
semaphore s=1;
semaphore e=sob;
void producer()
{while true
{produce();
wait(e);
wait (s);
append();
signal(s);
signal(n); }}
void consumer()
{while true
{wait(n);
wait(s);
take();
signal(s);
signal(e) ;
consume();}}
void main()
{parbegin
(producer,consumer);}
信号量的实现－ testset
wait(s)
{while (!testset(s.flag));
s.count--;
if (s.count<0)
{该进程 → s.queue;
阻塞该进程 ;}
else s.flag=0;
}
signal(s)
{while (!testset(s.flag));
s.count++;
if (s.count<=0)
{从 s.queue选取某进程 ;
唤醒该进程 ;}
s.flag=0;
}
信号量的实现－中断
wait(s)
{禁止中断；
s.count--;
if (s.count<0)
{该进程 → s.queue;
阻塞该进程 ;
允许中断； }
else 允许中断 ;
}
signal(s)
{禁止中断；
s.count++;
if (s.count<=0)
{从 s.queue选取某进程 ;
唤醒该进程 ;}
允许中断；
}
理发店问题
semaphore max_capacity=20; 店内允许的最大客户数
semaphore sofa=3; 沙发可坐人数
semaphore barber_chair=3; 椅子数
semaphore coord=3; 理发师数
semaphore
cust_ready=0,finished=0,leave_b_chair=0,payment=0,receipt=0;
不公平的理发店 1
void customer()
{wait(max_capacity);
进店；
wait(sofa);
坐沙发 ;
wait(barber_chair);
离开沙发；
signal(sofa);
坐椅子
signal(cust_ready)
wait(finished);
离开椅子；
signal(leave_b_chair);
付款；
signal(payment);
wait(receipt);
离店；
signal(max_capacity);
}
不公平的理发店 2
void barber()
{while true
{wait(cust_ready);
wait(coord);
理发；
signal(coord);
signal(finished);
wait(leave_b_chair);
signal(barber_chair);
}}
void cashier()
{while true
{wait(payment);
wait(coord);
收款；
signal(coord);
signal(receipt);}}
公平的理发店 1
semaphore max_capacity=20;
semaphore sofa=3;
semaphore barber_chair=3;
semaphore coord=3;
semaphore
cust_ready=0,finished=0,leave_b_chair=0,paym
ent=0,receipt=0;
semaphore mutex1=1,mutex2=1;
semaphore finished[50]={0};
int count;
公平的理发店 2
void customer()
{int custnr;
wait(max_capacity);
进店；
wait(mutex1);
count++;
custnr=count;
signal(mutex1);
wait(sofa);
坐沙发 ;
wait(barber_chair);
离开沙发；
signal(sofa);
坐椅子
wait(mutex2);
enqueue(custnr);
signal(cust_ready);
signal(mutex2);
Wait (finished[custnr]);
离开椅子；
signal(leave_b_chair);
付款；
signal(payment);
wait(receipt);
离店；
signal(max_capacity);
}
公平的理发店 3void barber()
{int b_cust;
while true
{ wait(cust_ready);
Wait(mutex2);
Dequeue(b_cust);
Signal(mutex2);
wait(coord);
理发；
signal(coord);
signal(finished[b_cust]);
wait(leave_b_chair);
signal(barber_chair);
}}
void cashier()
{while true
{wait(payment);
wait(coord);
收款；
signal(coord);
signal(receipt);}}
