操作系统中的Dekker算法
德克算法
Dekker算法是关键截面问题的第一个解决方案。此算法有很多版本，第5版或最终版本满足以下所有条件，并且在所有条件中效率最高。
解决关键部分问题必须确保满足以下三个条件：
互斥
进展
有限的等待
第一版
Dekker的算法成功实现了互斥。
它使用变量来控制线程执行。
它会不断检查关键部分是否可用。
示例
main(){
int thread_no = 1;
startThreads();
}
Thread1(){
do {
//进入部分
//等到threadno为1-
while (threado == 2)
;
//关键部分
//退出部分
//授予访问其他线程的权限
threadno = 2;
//其余部分
} while (completed == false)
}
Thread2(){
do {
//进入部分
//等到threadno为2-
while (threadno == 1)
;
//关键部分
//退出部分
//授予访问其他线程的权限
threadno = 1;
//其余部分
} while (completed == false)
}问题
Dekker算法的第一个版本的问题是锁步同步的实现。这意味着每个线程都依赖于另一个线程来完成其执行。如果两个进程之一完成其执行，则第二个进程运行。然后，它可以访问已完成的任务并等待其运行。但是完成的过程永远不会运行，因此它将永远不会将访问权返回到第二个过程。因此，第二个进程等待无限的时间。
第二版
在第二版的Dekker算法中，删除了锁步同步。通过使用两个标志指示其当前状态并在入口和出口部分相应地更新它们，可以完成此操作。
示例
main(){
//标志，指示每个线程是否在
//是否具有关键部分。
boolean th1 = false;
boolean th2 = false;
startThreads();
}
Thread1(){
do {
//进入部分
// wait until th2 is in its关键部分
while (th2 == true);
// indicate thread1 entering its关键部分
th1 = true;
//关键部分
//退出部分
// indicate th1 exiting its关键部分
th1 = false;
//其余部分
} while (completed == false)
}
Thread2(){
do {
//进入部分
// wait until th1 is in its关键部分
while (th1 == true);
// indicate th2 entering its关键部分
th2 = true;
//关键部分
//退出部分
// indicate th2 exiting its关键部分
th2 = false;
//其余部分
} while (completed == false)
}问题
此版本违反了互斥。在标志更新期间，如果线程被抢占，则两个线程都进入关键部分。一旦被抢占的线程重新启动，当两个标志都为假时，也可以在启动本身上观察到相同的情况。
第三版
在此版本中，在进入关键部分测试之前会设置关键部分标志，以确保相互排斥。
main(){
//标志，指示每个线程是否在
// queue to enter its关键部分
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
th1wantstoenter = true;
//进入部分
//等到th2想进入
// its关键部分
while (th2wantstoenter == true)
;
//关键部分
//退出部分
//指示th1已完成
// its关键部分
th1wantstoenter = false;
//其余部分
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
//进入部分
//等到th1要输入
// its关键部分
while (th1wantstoenter == true)
;
//关键部分
//退出部分
//指示th2已完成
// its关键部分
th2wantstoenter = false;
//其余部分
} while (completed == false)
}问题
此版本无法解决相互排斥的问题。它还引入了死锁的可能性，两个线程可能同时获得标志，并且它们将等待无限的时间。
第四版
在此版本的Dekker算法中，它会在很短的时间内将flag设置为false以提供控制，并解决了互斥和死锁的问题。
示例
main(){
//标志，指示每个线程是否在
// queue to enter its关键部分
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
th1wantstoenter = true;
while (th2wantstoenter == true) {
//允许访问其他线程
//等待随机的时间
th1wantstoenter = false;
th1wantstoenter = true;
}
//进入部分
//等到th2想进入
// its关键部分
//关键部分
//退出部分
//指示th1已完成
// its关键部分
th1wantstoenter = false;
//其余部分
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
while (th1wantstoenter == true) {
//允许访问其他线程
//等待随机的时间
th2wantstoenter = false;
th2wantstoenter = true;
}
//进入部分
//等到th1要输入
// its关键部分
//关键部分
//退出部分
//指示th2已完成
// its关键部分
th2wantstoenter = false;
//其余部分
} while (completed == false)
}问题
这个版本的问题是无限期推迟。随机时间是不可预测的，具体取决于实施算法的情况，因此在关键业务系统中是不可接受的。
第五版（最终解决方案）
在此版本中，使用加味的螺纹运动来确定进入关键部分。通过解决哪个线程应首先执行的冲突，它提供了互斥并避免了死锁，无限期延迟或锁步同步。此版本的Dekker算法提供了关键截面问题的完整解决方案。
示例
main(){
//表示哪个线程将进入下一步
int favouredthread = 1;
//标志，指示每个线程是否在
// queue to enter its关键部分
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
thread1wantstoenter = true;
//进入部分
//等到th2想进入
// its关键部分
while (th2wantstoenter == true) {
//如果第二线程更受欢迎
if (favaouredthread == 2) {
//允许访问其他线程
th1wantstoenter = false;
//等到该线程被选中
while (favouredthread == 2);
th1wantstoenter = true;
}
}
//关键部分
//支持第二个线程
favouredthread = 2;
//退出部分
//指示th1已完成
// its关键部分
th1wantstoenter = false;
//其余部分
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
//进入部分
//等到th1要输入
// its关键部分
while (th1wantstoenter == true) {
//如果第一个线程更受欢迎
if (favaouredthread == 1) {
//允许访问其他线程
th2wantstoenter = false;
//等到该线程被选中
while (favouredthread == 1);
th2wantstoenter = true;
}
}
//关键部分
//支持第一线程
favouredthread = 1;
//退出部分
//指示th2已完成
// its关键部分
th2wantstoenter = false;
//其余部分
} while (completed == false)
}