[C++知识库]信号量实现前驱关系

利用信号量实现前驱关系
信号量也可以用来描述程序之间或者语句之间的前驱关系。图2-8给出了一个前驱图，其中S1, S2, S3, …, S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。例如，为保证S1 -> S2、 S1 -> S3的前驱关系，应分别设置信号量a1、a2。同样，为了保证 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,应设置信号量bl、b2、c、d、e。

?图1?前驱图举例

实现算法如下：

semaphore ?al=a2=bl=b2=c=d=e=0; ?//初始化信号量
S1() {
? ? // …
? ? V(al); ?V(a2) ; ?//S1已经运行完成
}
S2() {
? ? P(a1); ?//检查S1是否运行完成
? ? // …
? ? V(bl); V(b2); // S2已经运行完成
}
S3() {
? ? P(a2); ?//检查S1是否已经运行完成
? ? // …
? ? V(c); ?//S3已经运行完成
}
S4() {
? ? P(b1); ?//检查S2是否已经运行完成
? ? // …
? ? V(d); ?//S4已经运行完成
}
S5() {
? ? P(b2); ?//检查S2是否已经运行完成
? ? // …
? ? V(e); ?// S5已经运行完成
}
S6() {
? ? P(c); ?//检查S3是否已经运行完成
? ? P(d); ?//检查S4是否已经运行完成
? ? P(e); ?//检查S5是否已经运行完成
? ? // …;
}

代码段：

解：
 已知A,B，那么A2,3B,5A进程可以随时开始：
 设      s1=A2,          s2=3B,         s3=5A,     
         s4=A2+3B,       s5=B+5A,       s6=（A2+3B）/（B+5A）

 设1,2,3,4,5,6号位置分别对应a,b,c,d,e,f,信号量。
 semaphore a,b,c,d,e,f;
 a.value=b.value=c.value=c.value=e.value=f.value=0
 	p1:{  s1,  v(a)  }
 	p2:{  s2,  v(b)  }
 	p3:{  s3,  v(c)  }
 	p4:{  p(a),p(b),s4,v(d)  }
 	p5:{  p(c),s5,v(e) }
 	p6:{  p(d),p(e), s6  }

例题

图2 服务员例题

?补充，信号量类型分为整型信号量和记录型信号量

记录型信号量代码段：

typedef struct{
	int value;
	struct process_control_block *list;//阻塞队列
}semaphore;
wait(semaphore *S){
	S->value--;//申请资源
	if(S->value<0)//表示该类资源已分配完毕，应调用block原语进行自我阻塞
		block(S->list);
}
signal(semaphore *S){
	S->value++;//释放资源
	if(S->value<=0) //表表示该信号量链表中仍有等待的进程被阻塞,应调用wakeup原语。
		wakeup(S->list);