经典同步问题

1.经典同步问题

进程同步：使得并发进程能够有序推进，解决异步中无序推进带来的不确定性（执行有前后顺序）
进程互斥：一个进程访问或对某资源进行操作时，其余进程无法对该资源进行操作（我操作你不能）

1.1 生产者-消费者问题

有一个队列（缓冲区），生产者在队列头部，消费者在队列尾部，生产者从队头放东西（数据），消费者从队尾取东西（数据）
下图来自《半小时漫画计算机》

如果队列里空了，消费者必须阻塞等待，等到生产者放入东西后再告诉消费者来拿（队列没满，生产者生产）
如果队列里满了，生产者必须阻塞等待，等到消费者取走东西后再告诉生产者去放（队列没空，消费者消费）
放数据和取数据两个操作存在先后次序，即存在同步

注意：
1.因为缓冲区是临界资源，二者不能同时操作队列，因此需要互斥锁（mutex clock）
2.线程还得在满足上述条件时通知另一个线程

互斥锁：线程在对资源操作前尝试加锁，成功加锁后对资源进行操作，操作完成后解锁，即同一个时刻只能有一个线程持有该锁

下图来自《半小时漫画计算机》


一个生产者,一个消费者

semaphore muxtex=1;		//互斥信号量
semaphore empty=n;		//同步信号量，初始状态有n个空缓冲区单元
semaphore full=0;		//同步信号量，初始状态有0个满缓冲区单元
producer(){
    		//生产者进程
	while(1){
    
		produce data;
		P(empty);	//申请一个空缓冲区单元
		P(mutex);	//进入临界区上互斥锁
		add data into buffer;	//向缓冲区内填入数据，该缓冲区单元变为满缓冲区单元
		V(mutex);	//退出临界区释放互斥锁
		V(full);	//释放该满缓冲区单元
	}
}
consumer(){
    		//消费者进程
	while(1){
    
		P(full);	//申请一个满缓冲区单元
		P(mutex);	//进入临界区上互斥锁
		remove data from buffer;	//从缓冲区内取走数据，该缓冲区单元变为空缓冲区单元
		V(mutex);	//退出临界区释放互斥锁
		V(empty);	//释放该空缓冲区单元
	}
}

假设一个情形：缓冲区处于满的状态（empty=0，full=n），如果调换生产函数中两个P操作的前后顺序，那么会出现死锁

P(mutex);	//上互斥锁
P(empty);	//申请空缓冲区单元，但此时没有空的缓冲区单元，所以进程会在此等待，也就无法释放互斥锁，造成了死锁问题

故需要先同步，后互斥才能避免这种情况的死锁问题

1.2 读者-写者问题

读者只能读取数据，不能修改数据
写者可以读取数据，可以修改数据

semaphore rw=1;	//实现对共享文件的互斥访问
writer(){
    	//写者进程
	while(1){
    
		P(rw);	//申请操作共享文件
		write(); //写文件
		V(rw);	//释放共享文件
	}
}
reader1(){
    	//读者进程1
	while(1){
    
		P(rw);	//申请访问共享文件
		read(); //读文件
		V(rw);	//释放共享文件
	}
reader2(){
    	//读者进程2
	while(1){
    
		P(rw);	//申请访问共享文件
		read(); //读文件
		V(rw);	//释放共享文件
	}	
}

上述情况中，如果有多个读者同一时刻调用 reader 来读取文件，首先这类行为是被允许的，但由于读取前上锁了，多个读者之间为互斥的关系，故多个读者无法同时读取文件，那么如何实现多个读者同时读取文件呢？我们引入一个变量 count 记录正在读取文件的读者数量,并引入互斥信号量 countmutex 来使得进程互斥访问count变量

semaphore rw=1;	//实现对共享文件的互斥访问
int count=0;	//当前正在访问共享文件的进程数量，初始值为0
semaphore countmutex=1;	//保证对count变量的互斥访问
writer(){
    	//写者进程
	while(1){
    
		P(rw);	//申请操作共享文件
		write(); //写文件
		V(rw);	//释放共享文件
	}
}
reader1(){
    	//读者进程1
	while(1){
    
		P(countmutex);
		//if(count==0)可以判断当前读进程是否为第一个读进程或最后一个读进程
		if(count == 0)	//某个读者进程调用reader，检查count为0，表示当前无进程访问共享文件
			P(rw);	//申请访问共享文件
		count++;	//上一步进程已经申请读取文件，故当前访问共享文件进程数量加1
		V(countmutex);
		read();	 	//进程读取文件
		P(countmutex);
		count--;	//上一步进程已经读取完成，故当前访问共享文件进程数量减1
		if(count == 0)	//判断当前是否还有正在读取文件的进程，如果满足，则表示没有，可以释放锁
			V(rw);	//释放访问共享文件的锁
		V(countmutex);
	}
reader2(){
    	//读者进程2
	while(1){
    
		P(countmutex);
		//if(count==0)可以判断当前读进程是否为第一个读进程或最后一个读进程
		if(count == 0)	//某个读者进程调用reader，检查count为0，表示当前无进程访问共享文件
			P(rw);	//申请访问共享文件
		count++;	//上一步进程已经申请读取文件，故当前访问共享文件进程数量加1
		V(countmutex);
		read();	 	//进程读取文件
		P(countmutex);
		count--;	//上一步进程已经读取完成，故当前访问共享文件进程数量减1
		if(count == 0)	//判断当前是否还有正在读取文件的进程，如果满足，则表示没有，可以释放锁
			V(rw);	//释放访问共享文件的锁
		V(countmutex);
	}
}

虽然上面实现了多个读者同时读取共享文件的操作，但这种情况还存在一个隐患就是多个读者如果一直在读取共享文件，此时写者进程却一直在阻塞等待，这样可能会导致写者进程饿死,为了解决写进程可能饿死的情况,我们需要实现写优先
我们引入互斥信号量 w 来实现写优先
(实际上并不是真正的写优先,需要读写公平策略才能实现真正的写优先)

semaphore rw=1;	//保证读者和写者互斥访问文件
int count =0;	//正在读取文件的进程个数，初始时并没有进程正在读取文件
semaphore mutex=1;	//进程对count变量进行互斥访问
semaphore w=1;	//用于实现写优先。防止多个读进程读取文件时，写进程由于阻塞等待时间过长而饿死
writer(){
    	//写者进程1
	while(1){
    
		P(w);	//对写进程加锁
		P(rw);	//对写文件加锁
		写文件
		V(rw);	//对写文件解锁
		V(w);	//对写进程解锁
	}
}
reader1(){
    	//读者进程1
	while(1){
    
		P(w);	
		P(mutex);	//对变量count加锁
		if(count==0)	//检查目前没有进程在读取文件
			P(rw);		//如果有写者，则阻塞写者
		count++;		//目前正在读取文件的进程数+1
		V(mutex);	//对变量count解锁
		V(w);			
		读文件
		P(mutex);	//对变量count加锁
		count--;	//上一个进程读取完成，目前正在读取文件的进程数-1
		if(count==0)	//检查目前没有进程在读取文件
			V(rw);		//对读文件解锁
		V(mutex);	//对变量count解锁
	}
reader2(){
    	//读者进程2
	while(1){
    
		P(w);	
		P(mutex);	//对变量count加锁
		if(count==0)	//检查目前没有进程在读取文件
			P(rw);		//如果有写者，则阻塞写者
		count++;		//目前正在读取文件的进程数+1
		V(mutex);	//对变量count解锁
		V(w);			
		读文件
		P(mutex);	//对变量count加锁
		count--;	//上一个进程读取完成，目前正在读取文件的进程数-1
		if(count==0)	//检查目前没有进程在读取文件
			V(rw);		//对读文件解锁
		V(mutex);	//对变量count解锁
	}
}

假设读者1,写者1,读者2并发执行
写者1在读者2前执行,实现了写优先,避免了写进程饿死的情况

1.3 哲学家进餐问题

一个饭桌上有5位哲学家(5个进程),5只筷子(5个临界资源),只有当哲学家同时拿起自己左右两侧的筷子才可以进行吃饭(访问临界资源),如果无法同时拿到2只筷子,则哲学家思考(进程阻塞等待)

下图来自王道考研操作系统

假设5位哲学家同时拿起自己左侧的筷子,每个哲学家都在等待右边的哲学家放下筷子,且不会主动放下自己手中的筷子,这样就出现了死锁

如何解决死锁问题?
方案一: 4位哲学家同时拿起左侧的筷子,3号也拿起了右侧的筷子,吃完后,放下2只筷子,2号拿起3号放下的筷子吃饭
在3号哲学家吃饭的同时,0号,1号,2号在占用着1个资源的同时还在阻塞等待(有些浪费资源)

semaphore chopstick[5]={
    1,1,1,1,1}; //信号量(临界资源数量,1根筷子代表1个临界资源)
Pi(){
    	//第i个哲学家进程
	do{
    
		P(chopstick[i]);	//取左侧筷子
		P(chopstick[(i+1)%5]);	//取右侧筷子
		eat;
		V(chopstick[i]);	//放回左侧筷子
		V(chopstick[(i+1)%5]);	//放回右侧筷子
		think;
	}while(1);
}

方案二: 奇数号哲学家先拿左侧的筷子,后拿右侧的筷子,偶数号哲学家先拿右侧的筷子,后拿左侧的筷子
如果两个哲学家争抢其中一只筷子,肯定会有其中一个哲学家争抢上,另一个哲学家则会空手(不占用资源进行阻塞等待)

方案三: 仅当哲学家左右两侧的筷子都属于可用状态时,才抓起两只筷子吃饭

考虑能不能一次拿起2根筷子,然后才做出决定,这就会就避免出现死锁,这是哲学家就餐问题的精髓

semaphore chopstick[5]={
    1,1,1,1,1};	//信号量(临界资源数量,1根筷子代表1个临界资源)
semaphore mutex = 1;	//互斥信号量,互斥取筷子
Pi(){
    	//第i个哲学家进程
	do{
    
		P(mutex);	//上锁
		P(chopstick[i]);	//取左侧筷子
		P(chopstick[(i+1)%5]);	//取右侧筷子
		V(mutex);	//解锁
		eat;
		V(chopstick[i]);	//放回左侧筷子
		V(chopstick[(i+1)%5]);	//放回右侧筷子
		think;
	}while(1);
}

1.4 吸烟者问题

本质为：单生产者 — 多消费者的问题

供应者无限提供三种材料：纸、胶水、烟草，且每次只提供其中两种
吸烟者手里只有一种材料，只有当拥有另外两种材料时，才可以卷出香烟，并抽烟，抽完烟告诉供应者，供应者继续供应材料放到桌子上

互斥关系：
三个吸烟者进程互斥访问桌子（容量为1的缓冲区）
同步关系：
桌子上出现组合1，则第一个吸烟者取走
桌子上出现组合2，则第二个吸烟者取走
桌子上出现组合3，则第三个吸烟者取走
某个吸烟者吸完后给供应者发送信号，则供应者继续供应材料放到桌子上

下图来自王道考研操作系统

下图来自王道考研操作系统

int num=0;		//用于实现三个吸烟者轮流吸烟
semaphore offer1=0;
semaphore offer2=0;
semaphore offer3=0;
semaphore finish=0;
provider(){
    
	while(1){
    
		num++;	
		num=num%3;	//使得吸烟者0，1，2轮流获得材料
		if(num==0)
			V(offer1);	//释放组合1材料：纸+胶水
		else if(num==1)
			V(offer2);	//释放组合2材料：烟草+胶水
		else
			V(offer3);	//释放组合3材料：烟草+纸
	将材料放至桌子上
	P(finish);	//接收来自吸烟者的完成信号
	}
}

smoker1(){
    
	while(1){
    
		P(offer1);	//吸烟者1拿走组合1材料
		用三种材料制作香烟后吸烟
		V(finish);	//通知供应者，吸烟完成
	}
}

smoker2(){
    
	while(1){
    
		P(offer2);	//吸烟者2拿走组合2材料
		用三种材料制作香烟后吸烟
		V(finish);	//通知供应者，吸烟完成
	}
}

smoker3(){
    
	while(1){
    
		P(offer3);	//吸烟者3拿走组合3材料
		用三种材料制作香烟后吸烟
		V(finish);	//通知供应者，吸烟完成
	}
}