操作系统中的 Dekker 算法
operating systemwindowsmca更新于 2026/2/6 4:37:17
Dekker 算法
Dekker 算法是临界区问题的第一个解决方案。该算法有多个版本，第五个版本(即最后一个版本)满足以下所有条件，是所有版本中效率最高的。
临界区问题的解决必须满足以下三个条件:
- 互斥
- 进展
- 有限等待
第一个版本
- 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 {
// 进入临界区
// 等待 th2 进入临界区
while (th2 == true);
// 指示线程 1 进入临界区
th1 = true;
// 临界区
// 退出部分
// 指示 th1 退出其临界区
th1 = false;
// 剩余部分
} while (completed == false)
}
Thread2(){
do {
// 进入部分
// 等到 th1 进入其临界区
while (th1 == true);
// 指示 th2 进入其临界区
th2 = true;
// 临界区
// 退出区
// 指示 th2 退出其临界区
th2 = false;
// remainder section
} while (completed == false)
}
问题
此版本违反了互斥原则。在标志更新期间，如果线程被抢占，则两个线程都会进入临界区。一旦被抢占的线程重新启动，在启动时，当两个标志都为 false 时，也会观察到同样的情况。
第三版
在此版本中，临界区标志在进入临界区测试之前设置，以确保互斥。
main(){
// 标志用于指示每个线程是否在
// 进入其临界区的队列
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
th1wantstoenter = true;
// 入口段
// 等待直到 th2 想要进入
// 其临界段
while (th2wantstoenter == true)
;
// 临界段
// 出口段
// 指示 th1 已完成
// 其临界区
th1wantstoenter = false;
// 剩余区
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
// 入口区
// 等待 th1 想要进入
// 其临界区
while (th1wantstoenter == true)
;
// 临界区
// 退出区
// 指示 th2 已完成
// 其临界区
th2wantstoenter = false;
// 剩余区
} while (completed == false)
}
问题
此版本未能解决互斥问题。它还引入了死锁的可能性，两个线程可能同时获得标志，并且它们将无限期地等待。
第四版
在此版本的 Dekker 算法中，它将标志设置为 false 一小段时间以提供控制，并解决了互斥和死锁问题。
示例
main(){
// 标志，指示每个线程是否在
// 进入其临界区的队列
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
th1wantstoenter = true;
while (th2wantstoenter == true) {
// 允许访问其他线程
// 等待随机时间
th1wantstoenter = false;
th1wantstoenter = true;
}
// 进入段
// 等待直到 th2 想要进入
// 其临界区
// 临界区
// 退出区
// 指示 th1 已完成
// 其临界区
th1wantstoenter = false;
// 剩余区
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
while (th1wantstoenter == true) {
// 允许访问其他线程
// 等待随机时间
th2wantstoenter = false;
th2wantstoenter = true;
}
// 入口段
// 等待直到 th1 想要进入
// 其临界段
// 临界段
// 出口段
// 指示 th2 已完成
// 其临界段
th2wantstoenter = false;
// 剩余段
} while (completed == false)
}
问题
此版本的问题在于无限期推迟。随机时间量是不可预测的，具体取决于算法的实现情况，因此在业务关键型系统中是不可接受的。
第五版(最终解决方案)
在此版本中，使用指定线程运动来确定进入临界区。它通过解决哪个线程应该先执行的冲突来提供互斥，并避免死锁、无限期推迟或锁步同步。此版本的 Dekker 算法提供了临界区问题的完整解决方案。
示例
main(){
// 表示下一个进入的线程
int favoredthread = 1;
// 标志，指示每个线程是否处于
// 进入临界区的队列
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
thread1wantstoenter = true;
// 进入临界区
// 等待直到 th2 想要进入
// 临界区
while (th2wantstoenter == true) {
// 如果第二个线程更受欢迎
if (favouredthread == 2) {
// 允许访问其他线程
th1wantstoenter = false;
// 等待直到此线程被优先访问
while (favouredthread == 2);
th1wantstoenter = true;
}
}
// 临界区
// 支持第二个线程
favoredthread = 2;
// 退出区
// 指示 th1 已完成
// 其临界区
th1wantstoenter = false;
// 剩余部分
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
// 进入部分
// 等待直到 th1 想要进入
// 其临界区
while (th1wantstoenter == true) {
// 如果第一个线程更受欢迎
if (favaouredthread == 1) {
// 允许访问其他线程
th2wantstoenter = false;
// 等待此线程被优先访问
while (favouredthread == 1);
th2wantstoenter = true;
}
}
// 临界区
// 优先使用第一个线程
favoredthread = 1;
// 退出区
// 指示 th2 已完成
// 其临界区
th2wantstoenter = false;
// 剩余区
} while (completed == false)
}
