操作系统信号量机制
信号量机制简介
进程互斥的四种软件实现方式：单标志、双标志先检查、双标志后检查、peterson算法
进程互斥的三种硬件实现方法：中断屏蔽法、TS/TSL指令、Swap/XCHG指令
上述所有方法都无法解决让权等待
迪杰斯特拉提出一种信号量机制。用户进程可以通过使用操作系统提供一对原语对信号量进行操作，从而很方便的实现进程同步互斥
信号量是一个变量用于记录系统资源数量，可以是整数，也可以是一个较为复杂的记录型信号量。
一对原语：wait（S）和signal（S）/P（S）和V（S）
P、V操作底层实现
整数型信号量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int S = 1;
void wait(int S){
while(S <= 0);
S=S-1;
}
void signal(int S){
S=S+1;
}
void process01(){
wait(S);
使用资源;
signal(S);
}
|
记录型信号量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| typedef struct{
int value;
struct process *L;
} semaphore;
void wait(semaphore S){
S.value--;
if(S>value < 0){
block(S.L);
}
}
void signal(samephore S){
S.value++;
if(S.value <=0){
wakeup(S.L);
}
}
|
信号量机制实现同步互斥
实现进程互斥
- 分析并发进程关键活动，划定临界区
samephore mutex=1;
- 设置互斥信号量
mutex，初值为同时能够进入临界区的进程数量一般初值为1
- 进入临界区
P(mutex)–申请资源
- 退出临界区
V(mutex)–释放资源
- PV操作必须同步出现，缺少P操作无法保证互斥访问，缺少V操作会导致资源不被释放永不唤醒
实现进程同步
同步要求：各程序需要并发有序地推进 1.
分析在什么地方需要实现一前一后 2. 设置同步信号量 3.
在“前操作”之后执行V(S) 4.
在“后操作”之前执行P(S) 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
typedef struct{
int value;
struct process *L;
} semaphore;
semaphore S = 0;
void p1(){
···
V(S);
···
}
void p2(){
}
|
V(S) 4.
在“后操作”之前执行P(S) ### 经典同步互斥问题 ####
生产者消费者问题 生产者、消费者、n个缓冲区
缓冲区必须互斥访问
缓冲区没满生产者放入
缓冲区不空消费者消费
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
typedef struct{
int value;
struct process *L;
}semaphore;
semaphore mutex;
semaphore full;
semaphore empty;
producer(){
生产产品
P(mutex);
V(full);
将产品放入缓冲区
V(mutex);
P(empty);
}
consumer(){
P(mutex);
V(empty);
消费产品;
P(full);
V(mutex);
}
|
吸烟者问题
三个烟鬼，各自持有三种卷烟材料A,B,C中的两种，现有一材料提供者provider会在一个桌子上轮流放置一种材料，烟鬼得到相应的材料后可合成成品烟然后吸食，现使用信号量机制解决烟鬼抽烟问题
对桌子的访问需要互斥的访问，放置、取走材料需要同步的进行。烟鬼抽完烟后需告诉厂商自己已经抽完，可以进行下一次取得材料的操作。
1
2
3
4
5
6
7
8
| 循环：
放置A材料->烟鬼1取材料+吸烟
or
放置B材料->烟鬼2取材料+吸烟
or
放置C材料->烟鬼#取材料+吸烟
返回完成信息
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| semaphore A=0；
semaphore B=0；
semaphore C=0；
seamphore finish=1;
int i=0;
provider(){
while(1){
P(finish);
if(i%==0){
放入材料A；
V(A);
}
else if(i%==1){
放入材料B；
V(A);
}
else if(i%==2){
放入材料C；
V(A);
}
i++;
}
}
MA(){
if(A.value==1){
P(A);
取走材料A，卷烟抽烟;
V(finish);
}
}
MB(){
}
MC(){
}
|
读者写者问题
两种进程，读者，写者进程，要求： 1. 可以多个读者同时读取 2.
仅一位写者在同一时刻可进行写入 3. 写者操作之前需要所有读者退出文件
1
| 互斥关系:写者-读者、写者-写者、同时读取不存在互斥关系
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| semaphore mutex=1;
semaphore Rnums=1;
int Rnum=0;
semaphore w=1;
Write(){
while(1){
P(w);
P(mutex);
写文件
V(mutex);
V(w);
}
}
Read(){
while(1){
if(==0){
P(mutex);
}
Rnum++;
读文件;
Rnum--;
if(i==0){
V(mutex);
break;
}
}
}
Read_plus(){
while(1){
P(Rnums);
if(==0){
P(mutex);
}
Rnum++;
V(Rnums);
读文件;
Rnum--;
if(i==0){
V(mutex);
break;
}
}
}
Read_plus(){
while(1){
P(w);
P(Rnums);
if(==0){
P(mutex);
}
Rnum++;
V(Rnums);
V(w);
读文件;
Rnum--;
if(i==0){
V(mutex);
break;
}
}
}
|
需要一气呵成的操作应该想到使用互斥信号量的P、V操作
哲学家进餐问题
一个圆桌上有五名哲学家围坐一桌，每名哲学家不是在思考就是在吃饭，但桌子上只有两个相邻的哲学家之间才有一根筷子，哲学家想要进行就餐必须同时拿起左右手边的两根筷子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| semaphore chopsticks[5]={1,1,1,1,1};
Pi(){
while(1){
p(chopsticks[i]);
p(chopsticks[(i+1)%5]);
吃饭;
V(chopsticks[i]);
V(chopsticks[(i+1)%5]);
}
}
semaphore chopsticks[5]={1,1,1,1,1};
semaphore mutex=1;
Pi(){
while(1){
P(mutex);
p(chopsticks[i]);
p(chopsticks[(i+1)%5]);
V(mutxe);
吃饭;
V(chopsticks[i]);
V(chopsticks[(i+1)%5]);
}
}
|
