这篇文章会讨论下4个经典的同步模型； 然后会说下死锁的避免，预防，检测和根除。
（1）经典的同步模型
*在操作系统第9版这本书里面， 我找到了4个比较经典的模型。其实大多都是对信号量的灵活运用来叫Race Condition来达到预期效果的小练习。 不知道在以后会不会用得到，不过记录下总是好的。 主要还是这些东西都很有意思。
1. Peterson's Solution(皮特森算法)
Peterson‘s Solution这个算法是一个实现互斥锁的算法。在我个人看来，所有模型里面这个算法是最牛逼的。 因为他单纯的用软件编程就实现了进程同步而不需要使用任何原子性操作方程。 既然是纯编程就能实现的东西， 那肯定要先撸个测试例子看看效果啦。
首先，先搞一个原始方程。 在上一章节里面用了线程同步， 这次换个进程玩玩。
#include<stdio.h>
#include<sys/shm.h>
#include<unistd.h>
#include<stdlib.h>
typedefstruct shared_data{
int counter;
}shared_data;
main()
{
int shmid,status;
struct shared_data *data_ptr;
shmid = shmget(IPC_PRIVATE,sizeof(struct shared_data),0664 | IPC_CREAT);
int pid = fork();
if ( pid <0 ){
perror("fork出现错误\n");
}elseif(pid ==0 ){
data_ptr = (struct shared_data*) shmat(shmid,0,0);
for(int i =0; i <1000000; i++ )
data_ptr -> counter ++;
exit(0);
}else{
data_ptr = (struct shared_data*) shmat(shmid,0,0);
for(int i =0; i <1000000; i++ )
data_ptr -> counter ++;
wait(&status);
printf("The Final Counter is%d\n", data_ptr -> counter);
if(!shmdt(data_ptr))
printf("分离进程间共享内存\n");
if(!shmctl(shmid, IPC_RMID,0))
printf("删除共享内存\n");
}
}
测试结果：
在这里不谈shmid,shmget,shmdt,shmct等进程同步的具体使用细节和原理，以后如果有意向会单独开一个文章具体说说。这个方程的purpose一目了然， 简单地两个进程分别for loop遍历100万次，然后看看最后共享的全局变量的结果是不是200万。 首先这个例子的结果绝对是错误的，原因前一个文章介绍过这里不提。
皮特森算法(该方程有精简的写法，但是为了自己将来的理解，我现在稍微写的繁琐点):
//initialise
bool flag[0] =false;
bool flag[1] =false;
int turn;
//Prosess A;
flag[0] = true;
->*A;
turn = 1;
-> *B;
while (flag[1] ==true && turn ==1);
-> *C;
// critical section
flag[0] = false;
//Process B;
flag[1] = true;
turn = 0;
while (flag[0] ==true && turn ==0);
// critical section
flag[1] =false;
让我来稍微分析下这个算法，首先这两个进程在整个过程中都只会改变他们各自的flag以及turn的值，在进入Critical Section之前他们每次都会检查自己的turn值以及对方的flag值。当这两个值不满足特定情况的时候，对应的Process会已Busy Waiting的情况在原地打转。我在伪代码中标出了4个有可能发生Context Switch的位置，让我们挨个看一看。在这里我们假设只有Process A 和 Process B 两个进程。
在*A的时候，如果发生上下文切换，
1). 假设Process B 会走到 "turn = 0" 的位置之后切换回来，turn 会再次被改写到1之后不管任何时间点发生上下文切换，Process A 都会已自旋的状态被卡在Critical Section以外,直到进程B结束。
2). 假设Process B 会一直走下去。则flag[0] 为true, flag[1]为ture, turn = 0; 则无论再次之后发生任何上下文切换，Process B 都会自旋,直到进程A结束。
在*B的时候，如果发生上下文切换，
1). 假设Process B 会走到 "turn = 0" 的位置之后切换回来，那么Process A会进入临界区，之后无论任何时间点发生上下文切换，Process B都会自旋，直到进程A结束。
2). 假设Process B 会一直往下走， 那Process B会被卡在临界区以外，同样是已自旋的形式，直到进程A结束。
在*C的时候，进程A已经进入临界区，进程B无法进入。
由此我们可以看出，这种算法会给予先运行这段代码的进程一个优先级(以上例子已Process A为例子)，在列出的几种情况来说会有更大的几率先运行Process A，Process B会自旋在Mutex的位置。
接下来，让我们已解决临界区的三个条件来判断下这个算法的准确性(上篇文章有介绍过)。
互斥访问： 两个进程显然不可能同时进入临界区(请参考刚才的三种发生上下文切换的模拟)。
进入(Progress) 和 有限等待(Bounded waiting): 在我看来，这个例子的这两种情况可以一起理解。 当其中一个进程走出临界区的时候，他会改变自己的flag，这样另外一个进程不会永远的自旋并且有机会进入临界区。
好的，现在让我返回刚才那个例子。 我会运用Peterson's Solution的方法来解决刚才所发生的Race Condition问题。
#include <stdio.h>
#include <sys/shm.h>
#include <unistd.h>
#include <stdlib.h>
typedef int bool; enum{false, true};
typedef struct shared_data{
int counter;
int turn;
bool flag[2];
}shared_data;
main()
{
int shmid,status;
struct shared_data *data_ptr;
shmid = shmget(IPC_PRIVATE, sizeof(struct shared_data), 0664 | IPC_CREAT);
int pid = fork();
if( pid < 0){
perror("fork错误\n");
}else if( pid == 0){
data_ptr = (struct shared_data*) shmat(shmid, 0, 0);
data_ptr -> flag[0] = true;
data_ptr -> turn = 1;
while(data_ptr -> flag[1] && data_ptr -> turn == 1);
for(int i = 0; i < 1000000; i++ )
data_ptr -> counter ++;
data_ptr -> flag[0] = false;
exit(0);
}else{
data_ptr = (struct shared_data*) shmat(shmid, 0, 0);
data_ptr -> flag[1] = true;
data_ptr -> turn = 0;
while(data_ptr -> flag[0] && data_ptr -> turn == 0);
for(int i = 0; i < 1000000; i++ )
data_ptr -> counter ++;
data_ptr -> flag[1] = false;
wait(&status);
printf("The Final Counter is %d\n", data_ptr -> counter);
if(!shmdt(data_ptr))
printf("分离进程间共享内存\n");
if(!shmctl(shmid, IPC_RMID, 0))
printf("删除共享内存\n");
}
}
测试结果：
2. Producer and Consumer (生产者、消费者问题)
这个问题在我当初学系统编程的时候有提到过。 当时的lecturer把这个过程比作一个大胃往吃饭，侍者上菜的过程。大胃王会不停地吃掉桌上的菜，而侍者会不停地上菜。 当大胃王吃的慢，菜摆满了一桌的时候，侍者就不能再上菜了。 桌上没有菜的时候，大胃王也没办法吃饭。这个例子中， 吃饭的人就是consumer而上菜的侍者就是producer, 桌上的容量就是buffer size，大小为N。当然这个例子只能讲述下大概的思想，其中的一些小细节例如"生产产品" 和 "将产品移出Buffer"并不能很好地解释。
Whatever,我们来看下伪代码：
Semaphore ProductNum = 0;// Initial Buffer里面的产品数量;
Semaphore RemainderBuffer = N;// Initial Buffer里的剩余数量，因为此时没有东西，所以剩余N个;
Producer:
do{
ProduceTheItem();
wait(RemainderBuffer);//将item放入Buffer之后, Buffer剩余的大小 - 1；
Add the Item to Buffer..
signal(ProductNum);//Buffer里面的Product数量 + 1；
}while(true);
Consumer:
do{
wait(Product);//只有在有Prodcut的时候才能工作；
Move the Item out of Buffer..
signal(ReaminderBuffer);//当移出Buffer里面的产品之后，剩余的Buffer里面的item数量 +1；
ConsumeTheItem();
}while(true);
由伪代码可以看出， 我们控制两个Semaphore分别是Buffer里面产品的数量和Buffer的剩余数量。 当Buffer里面的产品数量(ProductNum) >= 0时， Consumer才可以工作(可以理解为桌上有菜了才能吃)。 当Buffer里面的剩余量为0时， Producer将无法工作(可以理解为桌子放满了没法上菜)。这个例子我觉得是模型里面最简单的一个，很好理解。
3. Reader and Writer(读者和写者)
这个问题的基本理念就是: 读者可以多个一起读取资料，写者只能一个一个的写。 读者读的时候，写者写不了。写者写的时候，读者读不了。
读者可以有多个进程一起访问， 期间因为只是读取程序并不涉及任何修改。 因此多个读者的访问并不会对原来所储存的共享内存也就是所读的内容进行修改，并不需要互斥锁。但是只要有一个读者存在，所有写者将不能进入临界区。
在写者方面，能写的人只有一个。因为写的操作涉及到共享内存因此需要互斥锁。
看一下伪代码:
static int count = 0;
Semaphore Access = 1;
Semaphore mutex = 1;
Reader(){
wait(mutex);
count ++;
if(count == 1)
wait(Access);
signal(mutx);
do.Read();
wait(mutex);
count --;
if( count == 0 )
signal(Access);
signal(mutex);
}
Writer(){
wait(Access);
do.Write();
signal(Access);
}
从上面可以看出， 当只有一个读者进入共享内存的时候，所有写者将无法进入。 之后进入的读者不计算在内，视为相同情况(*这个算法中，我们在意的不是有多少个读者进入共享内存，而是有没有读者进入共享内存)。 在写者方面，道理相同。 只要有一个写者进入临界区，然后任何读者或者写者都不允许再次进入。
现在问题来了， 我们可以设想下一个特殊情况。 有一个读者先进入了共享内存进行read操作，这时来了个写者，这个写者当然会被卡在临界区以外。这时假设在第一个读者没有离开方程的情况下，任何时候来的读者都会加在写者前面。请看下图,
只要有读者来，红色的写者会一直被卡住，而蓝色的写者会持续进入。 最后导致的情况是写者进程会处于严重的饥饿状态。而这个方程不论任何情况都为读者优先，所以被称为Reader Preference。
针对这种情况，我们有一个加强版的version:
static int count = 0;
Semaphore Access = 1;
Semaphore mutex = 1;
Semaphore AdditonLock = 1;
Reader(){
wait(AdditonLock);
wait(mutex);
count ++;
if(count == 1)
wait(Access);
signal(mutx);
signal(AdditonLock);
do.Read();
wait(mutex);
count --;
if( count == 0 )
signal(Access);
signal(mutex);
}
Writer(){
wait(AdditonLock);
wait(Access);
signal(AdditonLock);
do.Write();
signal(Access);
}
在这次改动中，我们新加了一个AdditionLock，所以就会有了双重保险。在读者和写者的进入过程中都会有一个锁儿，当本身的进程进入方程之后，AdditionLock会先关闭再打开。假设我们回到上文提到的饥饿问题。这时当一个读者进去后，假如下一个来的是写者。那么所有读者都会被卡在AdditionLock之外，而那个写者进程则会被卡在AdditionLock和Access两个互斥锁之间之间。
4. 贤者吃饭问题(Dining Philosopher)
假设有5个贤者围着1张桌子吃饭。 在每个贤者的左右两侧都各有一个筷子。 每个贤者只有两个状态，吃饭和思考。
当一个贤者想要吃饭的时候，需要拿他两边的筷子，然后吃饭。当吃完之后，会放下筷子，然后进行思考。
可能出现的问题其实很简单， 如果5个贤者在同一时间点都想吃饭。那么他们肯定有人拿的到一双筷子有人拿不到，或者可能所有人都拿不到一双筷子。
正确的解决办法 :
1. 直接加锁:
do{
wait(mutex);
wait(chopstick[i]);
wait(chopstick[i + 1] % 5);
signal(mutex);
do.eat();
signal(chopstick[i]);
signal(chopsitck[i + 1] % 5);
do.think();
}while(true);
这种方法网上叫他arbitrator(公断人),这里可以理解为服务员。 就是每次服务员都会给贤者递筷子，如果有一个贤者不能得到全部那他必须要等着。
2. Tannenbaum's Solution:
Semaphore me = 1;
Semaphore s[0 ~ 4] = 0;
Semaphore flag[0~4] = 1;
Semaphore
do{
do.thinking();
take_chopstick(i);
do.eating();
drop_chopstick(i);
}while(true);
function take_chopstick(i){
wait(me);
// Critical Section;
flag[i] = hungry;
test(i);
signal(me);
wait(s[i]);
do.eat();
}
function drop_chopstick(i){
wait(me);
flag[i] = thinking;
// Critical Section;
test(i - 1);
test(i + 1);
signal(me);
}
void test(i){
if(flag[i] == hungry && flag[i - 1] != eat && flag[i + 1] != eat){
flag[i] = eat;
signal(s[i]);
}
}
这段代码不难， 稍微看看就能看懂。 在这里就不多做解释了。
（2）死锁(Deadlock)
定义： 当两个或者两个以上的进程都在互相等待彼此完成任务以获得对方的资源。 待续、 太忙、
