进来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 section flag[0] = false; } } void procedure1() { while(true) { flag[1] = true; turn = 0; while(flag[0] && turn == 0) { sleep(1); printf("procedure1 is waiting!\n"); } //critical section flag[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); }
Bear将turn的赋值放在while循环的后面，然后main函数中赋初值，也是可行的。
如有错误，请指正，感激不尽!
参考书籍：
《Modern.Operating.Systems.3rd.Edition》作者：Andrew S.Tanenbaum
参考网站：
https://zh.wikipedia.org/wiki/Peterson
（貌似要FQ）
http://baike.baidu.com/link?url=h-hOJrsTo24PXgPweosxSpnzeaKhJwhz7N3PbZhG_2_M_8U6RQqEYt9KWGzyclw6lr9Qbi4FkLdyrIKDeBQ6qq
原文：http://www.cnblogs.com/zhengruin/p/4994188.html