Dekker algoritması

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:

  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

Kategori:Eşzamanlı algoritmalar