操作系统-进程与线程（同步互斥典型模型-读者写者模型，哲学家进餐问题）

王道操作系统学习笔记，心得

1. 读者写者模型

问题描述：
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

因此对这种情况，我们要求

1. 允许多个读者可以同时对文件执行读操作
2. 只允许一个写者往文件中写信息
3. 任一写者在完成写操作之前不允许其他读者或写者工作
4. 写者执行写操作前，应让已有的读者和写者全部退出。

分析互斥关系：

1. 读进程和写进程之间是互斥关系，写进程和写进程之间是互斥关系。

2. 读进程和读进程之间不存在互斥关系

这里选择一个变量记录正在读文件的读进程个数.
只有首次读时需要加锁，其他情况读进程不需要加锁。
同理，只有当最后一个读进程释放时，才可以释放这个信号量。
这样的话，读进程和读进程就可以并发的运行了。

伪代码：

semaphore rw=1; 实现对文件的互斥访问的信号量
int count=0; //记录现在正在有几个读进程正在访问文件

//写进程
write(){
	while(true){
		//申请对文件访问
		P(rw);
		写文件
		V(rw);
	}
}

read(){
	while(true){
		if(count==0){
			P(rw);
		}
		count+=1;
		
		读文件

		count-=1;
		if(count==0){
			V(rw);
		}
	}
}

但是，上述伪代码还存在问题

1. 因为对count变量的赋值和检查不是原子的。
   所以可能存在两个进程（线程）同时检测到count==0，从而进入条件中，导致一个读进程被阻塞。
2. 如果读进程比较多，写进程可能会出现饥饿情况。

这里可以通过设置互斥信号量来保证个进程访问count变量是互斥的。

同时再设置一个信号量w，用于防止写进程饥饿问题，这个信号量需要被所有的读者和写者一起竞争，申请到这个信号量，就说明有申请rw的资格。这样就解决了饥饿。

这里我认为，因为读进程申请到rw之后很难再释放，所以导致了写进程的饥饿，所以要对如何分配rw进行限制，所有进程都竞争申请rw的资格，如果一个读进程申请到了可以申请rw的资格，原子性的判断完count之后，就把申请rw资格让出来，这时候写进程就有机会申请到申请rw的资格，其他的读线程因为没有申请到申请rw的资格，没办法和写进程抢，所以只能等写进程完成操作后才行。

所以最后代码为：

semaphore rw=1; //实现对文件的互斥访问的信号量
int count=0; //记录现在正在有几个读进程正在访问文件
semaphore mutex=1; //实现对count的原子访问

semaphore w=1;//用于优化申请rw，防止写线程饥饿

//写进程
write(){
	while(true){
		P(w);
		
		//申请对文件访问
		P(rw);
		写文件
		V(rw);
		
		V(w);
	}
}

read(){
	while(true){
		P(w);
		
		P(mutex);
		if(count==0){
			P(rw);
		}
		count+=1;
		V(mutex);
		
		V(w);
		
		读文件
		
		P(mutex);
		count-=1;
		if(count==0){
			V(rw);
		}
		V(mutex);
	}
}

2. 哲学家进餐问题

问题描述：
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

同步互斥关系分析：

1. 首先5个进程，每个进程对周围的进程是互斥关系，需要争夺这个进程左右两边的资源。
2. 一个进程需要同时申请到两个临界资源才会开始执行自己的代码。

5个进程，就有5个临界区资源，为了实现5个临界资源的互斥访问，先定义5个互斥信号量。

为了描述问题，首先将进程和临界资源抽线成下图：

对于每一个进程的左边临界资源编号和这个进程编号相同，右边临界资源编号为（i+1）%5

首先先写出最直接思路，再分析问题改进：

semaphore chopstick [5]={1,1,1,1,1};

//编号为i的进程/线程
Pi(){
	while(true){
		//拿左边的资源
		P(chopstick[i]);
		//拿右边的资源
		P(chopstick[(i+1)%5]);
		
		吃饭

		//释放左边的资源
		V(chopstick[i]);
		P(chopstick[(i+1)%5]);
	}
}

但是如果5个线程同时申请到自己左边的资源后，自己右边的资源已经被其他线程申请到了，所以此时就会出现死锁现象。

解决方法有多种：

1. 可以规定最多只有4个进程运行解决这个问题，也就是说至少有一个进程左右资源是可以申请的。
2. 也可以规定奇数编号的进程只能拿先拿左边的临界资源，偶数编号的进程只能先拿右边的临界资源。这样保证了进程在进入阻塞时，自己没有申请到任意的临界资源，避免死锁。
3. 也可以规定进程拿左和拿右资源是原子的。一个进程必须拿起左右两个资源才会释放锁，其他进程不可能和它竞争左右资源，因为他们会被阻塞在加锁处。

这里使用第三种方法

semaphore chopstick [5]={1,1,1,1,1};

semaphore mutex=1;//保证进程拿左右资源是原子的。

//编号为i的进程/线程
Pi(){
	while(true){
		P(mutex);
		//拿左边的资源
		P(chopstick[i]);
		//拿右边的资源
		P(chopstick[(i+1)%5]);
		V(mutex);
		
		吃饭
		
		//释放左边的资源
		V(chopstick[i]);
		P(chopstick[(i+1)%5]);
	}
}