进程死锁算法——Peterson与Dekker

本文主要是介绍进程死锁算法——Peterson与Dekker，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

进来Bear正在学习巩固并行的基础知识，所以写下这篇基础的有关并行算法的文章。

在讲述两个算法之前，需要明确一些概念性的问题，

Race Condition（竞争条件），Situations like this, where two or more processes are reading or writing some shared data and the final result depends on who runs precisely when, are called race conditions.多个进程(线程)读写共享区域（共享文件、共享变量、共享内存等）时，最后的结果依赖于他们执行的相对时间。

Critical Regions（关键区域），That part of the program where the shared memory is accessed.在程序中，访问共享内存的部分。

Mutual exclusion（互斥）, that is, some way of making sure that if one process is using a shared variable or file, the other processes will be excluded from doing the same thing.指在一个进程在使用共享区域时，防止另外的进程做同样的事情。

同样，需要四个条件来找到一个好的解决方案，实现进程(线程)之间的互斥：

Dekker算法与Peterson算法就是用来实现进程或者线程之间的互斥。

Dekker算法:（参考了百度百科上面的Dekker算法解析，还是挺易懂的）

Dekker算法可以用于控制两个进程（线程）之间的同步，如下实现的功能就是专门用于线程的同步：

其中，flag[2]用来表示是否想要使用关键区，turn用来表示具有访问权限的进程ID。（重点看注释，通过注释，挺好理解的哟~ ）

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#define true 1
#define false 0
typedef int bool;
bool flag[2];
int turn;
void visit(int num)
{sleep(1);printf("P%d is visting\n",num);
}
void P0()
{while(true){flag[0] = true;//P0想使用关键区。while(flag[1])//检查P1是不是也想用？{if(turn == 1)//如果P1想用，则查看P1是否具有访问权限？{flag[0] = false;//如果有，则P0放弃。while(turn == 1);//检查turn是否属于P1。flag[0] = true;//P0想使用。}}visit(0); //访问Critical Partition。turn = 1; //访问完成，将权限给P1。flag[0] = false;//P0结束使用。}
}
void P1()
{while(true){flag[1] = true; //P1想使用关键区。while(flag[0]) //检查P0是不是也想用？{if(turn == 0) //如果P0想用，则查看P0是否具有访问权限？{flag[1] = false; //如果有，则P1放弃。while(turn == 0); //检查turn是否属于P1。flag[1] = true; // P1想使用。}}visit(1); //访问Critical Partition。turn = 0; //访问完成，将权限给P0。flag[1] = false; //P1结束使用。}
}
void main()
{pthread_t t1,t2;flag[0] = flag[1] = false;turn = 0;int err;err =  pthread_create(&t1,NULL,(void*)P0,NULL);if(err != 0) exit(-1);err = pthread_create(&t2,NULL,(void*)P1,NULL);if(err != 0 ) exit(-1);pthread_join(t1,NULL);pthread_join(t2,NULL);exit(0);
}

如上所示，如果 flag数组和turn都没有符合使用关键区的条件的时候，是不可能进入关键区的。

Peterson算法：

Peterson算法也是保证两个进程（线程）实现互斥的方法，比之前的Dekker算法更加简单，他同样提供了两个变量，保证进程不进入关键区，一个是flag[2]，一个是turn，两者的表达意思也类似，flag数组表示能否有权限使用关键区，turn是指有访问权限的进线程ID。（注释很重要，帮助你理解）

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#define true 1
#define false 0
typedef int bool;
bool flag[2];
int turn;
void procedure0()
{while(true){flag[0] = true;turn = 1;while(flag[1] && turn == 1)//退出while循环的条件就是，要么另一个线程
//不想要使用关键区，要么此线程拥有访问权限。{sleep(1);printf("procedure0 is waiting!\n");}//critical sectionflag[0] = false;}
}
void procedure1()
{while(true){flag[1] = true;turn = 0;while(flag[0] && turn == 0){sleep(1);printf("procedure1 is waiting!\n");}//critical sectionflag[1] = false;}
}
void main()
{pthread_t t1,t2;flag[0] = flag[1] = false;int err;turn = 0;err =  pthread_create(&t1,NULL,(void*)procedure0,NULL);if(err != 0) exit(-1);err = pthread_create(&t2,NULL,(void*)procedure1,NULL);if(err != 0 ) exit(-1);pthread_join(t1,NULL);pthread_join(t2,NULL);exit(0);
}