Dekker Algoritması Nedir ?

Dekker algoritması, karşılıklı dışlamayı (mutual exclusion) sağlamak için kullanılan bir eşzamanlı programlama (concurrent programming) algoritmasıdır. 1964'te T. J. Dekker tarafından geliştirilen ve adını da buradan alan algoritma, iki threadin çakışma yaratmaksızın paylaşılamayacak (yani bir seferde sadece bir threadin kullanabileceği) bir kaynağı, sadece iletişim için paylaşılan bir bellek yardımıyla, kullanmalarına olanak tanır. Basit bir vardiya (yani threadler arası sıra bölüştüren) algoritmasındaki dikkatli değiştirmeden (strict alternation) kaçınır. Dekker algoritması karşılıklı dışlama için icat edilmiş ilk algoritmalardandır.
Algoritmanın yapısı

Eğer iki işlem aynı anda kritik bölgeye girmeye çalışırsa, Dekker algoritması o anki sıraya göre hangi işlemin sırasıysa, sadece o bir tek işlemin kritik bölgeye girmesine izin verir. Eğer bir işlem zaten kritik bölgedeyse, diğer işlem yoğun beklemede ilk işlemin kritik bölgeden çıkmasını bekler. Bunu gerçekleştirmek için iki bayrak kullanılırlar: f0 ve f1. Bunlar kritik bölgeye girme amacını belirtirken, bir sıra değişkeni sayesinde iki işlem arasında hangisinin öncelikli olduğu belirtilir.

Algoritmanın sözde kodu şu şekilde yazılabilir:

tr.wikipedia.org

 f0 := false
 f1 := false
 turn := 0   // veya 1
 
 // işlem 1                          // işlem 2
 p0:                                 p1:
     f0 := true                          f1 := true
     while f1 {                          while f0 {
         if turn ≠ 0 {                       if turn ≠ 1 {
             f0 := false                         f1 := false
             while turn ≠ 0 {                    while turn ≠ 1 {
             }                                   }
             f0 := true                          f1 := true
          }                                  }
     }                                    }

    // kritik bölge                       // kritik bölge 
    ...                                   ...
    // kalan bölge                        // kalan bölge
    turn := 1                             turn := 0
    f0 := false                           f1 := false

Etiketler: Dekker Algoritması,İnternet Ve Teknoloji