資料結構
網路
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+ 瀏覽量
廣告