数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究操作系统中的Dekker算法
Dekker算法
Dekker算法是解决临界区问题的第一个解决方案。该算法有多个版本，第五版或最终版本满足以下所有条件，并且是其中效率最高的。
临界区问题的解决方案必须确保以下三个条件
- 互斥
- 进展
- 有界等待
第一个版本
- Dekker算法成功实现了互斥。
- 它使用变量来控制线程执行。
- 它不断检查临界区是否可用。
示例
main(){
int thread_no = 1;
startThreads();
}
Thread1(){
do {
// entry section
// wait until threadno is 1
while (threado == 2)
;
// critical section
// exit section
// give access to the other thread
threadno = 2;
// remainder section
} while (completed == false)
}
Thread2(){
do {
// entry section
// wait until threadno is 2
while (threadno == 1)
;
// critical section
// exit section
// give access to the other thread
threadno = 1;
// remainder section
} while (completed == false)
}问题
Dekker算法第一个版本的问题是锁步同步的实现。这意味着每个线程都依赖于其他线程来完成其执行。如果两个进程之一完成了其执行，则第二个进程运行。然后它授予已完成进程访问权限并等待其运行。但已完成进程永远不会运行，因此它永远不会将访问权限返回给第二个进程。因此，第二个进程无限期地等待。
第二个版本
在Dekker算法的第二个版本中，去除了锁步同步。这是通过使用两个标志来指示其当前状态并在入口和出口部分相应地更新它们来完成的。
示例
main(){
// flags to indicate whether each thread is in
// its critial section or not.
boolean th1 = false;
boolean th2 = false;
startThreads();
}
Thread1(){
do {
// entry section
// wait until th2 is in its critical section
while (th2 == true);
// indicate thread1 entering its critical section
th1 = true;
// critical section
// exit section
// indicate th1 exiting its critical section
th1 = false;
// remainder section
} while (completed == false)
}
Thread2(){
do {
// entry section
// wait until th1 is in its critical section
while (th1 == true);
// indicate th2 entering its critical section
th2 = true;
// critical section
// exit section
// indicate th2 exiting its critical section
th2 = false;
// remainder section
} while (completed == false)
}问题
此版本违反了互斥。在标志更新期间，如果线程被抢占，则两个线程都进入临界区。一旦抢占的线程重新启动，在开始时也可以观察到相同的情况，当两个标志都为假时。
第三个版本
在此版本中，在进入临界区测试之前设置临界区标志以确保互斥。
main(){
// flags to indicate whether each thread is in
// queue to enter its critical section
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
th1wantstoenter = true;
// entry section
// wait until th2 wants to enter
// its critical section
while (th2wantstoenter == true)
;
// critical section
// exit section
// indicate th1 has completed
// its critical section
th1wantstoenter = false;
// remainder section
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
// entry section
// wait until th1 wants to enter
// its critical section
while (th1wantstoenter == true)
;
// critical section
// exit section
// indicate th2 has completed
// its critical section
th2wantstoenter = false;
// remainder section
} while (completed == false)
}问题
此版本未能解决互斥问题。它还引入了死锁的可能性，两个线程都可能同时获得标志，并且它们将无限期地等待。
第四个版本
在此版本的Dekker算法中，它将标志设置为假一小段时间以提供控制，并解决互斥和死锁问题。
示例
main(){
// flags to indicate whether each thread is in
// queue to enter its critical section
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
th1wantstoenter = true;
while (th2wantstoenter == true) {
// gives access to other thread
// wait for random amount of time
th1wantstoenter = false;
th1wantstoenter = true;
}
// entry section
// wait until th2 wants to enter
// its critical section
// critical section
// exit section
// indicate th1 has completed
// its critical section
th1wantstoenter = false;
// remainder section
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
while (th1wantstoenter == true) {
// gives access to other thread
// wait for random amount of time
th2wantstoenter = false;
th2wantstoenter = true;
}
// entry section
// wait until th1 wants to enter
// its critical section
// critical section
// exit section
// indicate th2 has completed
// its critical section
th2wantstoenter = false;
// remainder section
} while (completed == false)
}问题
无限延迟是此版本的问题。随机时间量是不可预测的，具体取决于算法实现的环境，因此在业务关键系统中是不可接受的。
第五个版本（最终解决方案）
在此版本中，使用带颜色的线程运动来确定进入临界区的条件。它通过解决哪个线程应该首先执行的冲突，提供互斥并避免死锁、无限延迟或锁步同步。此版本的Dekker算法提供了临界区问题的完整解决方案。
示例
main(){
// to denote which thread will enter next
int favouredthread = 1;
// flags to indicate whether each thread is in
// queue to enter its critical section
boolean th1wantstoenter = false;
boolean th2wantstoenter = false;
startThreads();
}
Thread1(){
do {
thread1wantstoenter = true;
// entry section
// wait until th2 wants to enter
// its critical section
while (th2wantstoenter == true) {
// if 2nd thread is more favored
if (favaouredthread == 2) {
// gives access to other thread
th1wantstoenter = false;
// wait until this thread is favored
while (favouredthread == 2);
th1wantstoenter = true;
}
}
// critical section
// favor the 2nd thread
favouredthread = 2;
// exit section
// indicate th1 has completed
// its critical section
th1wantstoenter = false;
// remainder section
} while (completed == false)
}
Thread2(){
do {
th2wantstoenter = true;
// entry section
// wait until th1 wants to enter
// its critical section
while (th1wantstoenter == true) {
// if 1st thread is more favored
if (favaouredthread == 1) {
// gives access to other thread
th2wantstoenter = false;
// wait until this thread is favored
while (favouredthread == 1);
th2wantstoenter = true;
}
}
// critical section
// favour the 1st thread
favouredthread = 1;
// exit section
// indicate th2 has completed
// its critical section
th2wantstoenter = false;
// remainder section
} while (completed == false)
}
更新于： 2019年10月17日
11K+ 浏览量
广告