经典同步问题

生产者消费者问题

进程间关系为“生产资源-消费资源”

semaphore mutex = 1;
semaphore full = 0;
semaphore empty = n;
 
producer(){
	while(1){
		produce an item;//生产数据
		P(empty);
		P(mutex);
		add to buffer;//将数据放入缓冲区
		V(mutex);
		V(full);
	}
}
 
consumer(){
	while(1){
		P(full);
		P(mutex);
		remove an item from buffer;//从缓冲区取出数据
		V(mutex);
		V(empty);
		consume the item;//消费数据
	}
}

理发师问题

进程间关系为“服务-被服务”

最基础的模板：无等待上限，服务人员可休息

semaphore server = 0;
semaphore customer = 0;
semaphore mutex = 1;
 
server(){
	while(1){
		P(customer);
		P(mutex);
		叫号;
		V(mutex);
		V(server);
		提供服务;
	}
}
 
customer(){
	while(1){
		P(mutex);
		取号;
		V(mutex);
		V(customer);
		P(server);
		被服务;
	}
}

读者写者问题

同类进程不互斥、异类进程互斥

int count = 0;
semophore mutex = 1;//更新count时互斥
semophore rw = 1;//读进程和写进程互斥
semophore w = 1;//优先写进程
 
writer(){
	while(1){
		P(w);
		P(rw);
		writing;
		V(rw);
		V(w);
	}
}
 
reader(){
	while(1){
		P(w);
		P(mutex);
		if(count == 0) P(rw);//第一个读进程加锁
		count++;
		V(mutex);
		V(w);
		reading;
		P(mutex);
		count--;
		if(count == 0)V(rw);//最后一个读进程解锁
		V(mutex);
	}
}

哲学家进餐问题

只有一类进程，每个进程需要同时拥有多种资源才能运行

semaphore chopsticks[5] = {1,1,1,1,1};//下标为i的筷子代表第i位哲学家右手边的筷子
 
//方法一：当一个哲学家左右筷子都可用时，一起拿起左右两只筷子
semaphore mutex = 1;
pi(int i){
	while(1){
		P(mutex);
		P(chopsticks[i]);
		P(chopsticks[((i-1)+5)%5]);//左手的筷子
		V(mutex);
		eat;
		V(chopsticks[i]);
		V(chopsticks[((i-1)+5)%5]);
		think;
	}
}
 
//方法二：至多允许四个哲学家同时用餐
semaphore num = 4;
pi(int i){
	while(1){
		P(num);
		P(chopsticks[i]);
		P(chopsticks[((i-1)+5)%5]);
		eat;
		V(chopsticks[i]);
		V(chopsticks[((i-1)+5)%5]);
		V(num);
		think;
	}
}
 
//方法三：对哲学家编号，奇数号的先拿左边筷子，偶数号的正好相反
pi(int i){
	while(1){
		if(i%2==1){
			P(chopsticks[((i-1)+5)%5]);
			P(chopsticks[i]);
			eat;
			V(chopsticks[((i-1)+5)%5]);
			V(chopsticks[i]);
			think;
		}else{
			P(chopsticks[i]);		
			P(chopsticks[((i-1)+5)%5]);
			eat;
			V(chopsticks[i]);
			V(chopsticks[((i-1)+5)%5]);
			think;
		}
	}
}

单纯的同步问题

前驱后继图

semaphore s12=s13=s24=s25=s46=s56=s36
 
S1(){
	...;
	V(s12);
	V(s13);
}
 
S2(){
	P(s12);
	...;
	V(s24);
	V(s25);
}
 
S3(){
	P(s13);
	...;
	V(s36);
}
 
S4(){
	P(s24);
	...;
	V(s46);
}
 
S5(){
	P(s25);
	...;
	V(s56);
}
 
S6(){
	P(s46);
	P(s56);
	P(s36);
	...;
}