Yazan: Şadi Evren ŞEKER
Bilgisayar mühendisliğinde, birbirinde ayrı işlerin kontrolü için kullanılır. Aynı anda çalışan işlerin birbirinden tamamen ayrı olması için (mutually exclusive), bazı kontrollerin yapılması gerekmektedir. Algoritma bu problemi aşağıdaki şekilde çözer.
Yukarıdaki kodda görüldüğü üzere, kod üç kısımdan oluşmaktadır:
- Bariyer
- Kritik alan
- Bitiş
Bariyer kodunda, işlem (process), diğer çalışmakta olan ve o anda kritik bir koda erişen işlemleri bekler. Kendi önündeki bariyerin kalkmasıyla kritik alana girer. Bu alana o anda giren tek işlemdir çünkü kendi önündeki bariyerin kalkması ancak diğer işlemin bitiş kodunu çalıştırması ile mümkündür. Kritik alandaki görevini yerine getirdikten sonra bitiş kodunu çalıştırır ve beklemeden olan diğer işlemin bariyerlerini kaldırır.
Yukarıdaki kodda kullanılan flag dizisi (array), boolean tipinde olup o anda hangi işlemin çalıştığını tutmaktadır. Örneğin yukarıdaki kodun simetriği olarak diğer işlemin kodu aşağıdaki şekilde verilebilir:
İkinci kod ile ilk kod karşılaştırılırsa, flag[] ve turn değişkenlerine göre kimin çalışacağı belirlenmektedir.
Kodlarda bulunan 7. Satırdaki while döngüsü, aslında bekleme işlemini sağlar. Bu döngü turn değişkenine göre sonsuza kadar beklemektedir. Ancak diğer işlem tarafından değeri değiştirilince işlem çalışmasına devam edebilir.
Burada kullanılan turn değişkeni, iki işlem de aynı anda kritik alana girmek istiyorsa, anlık olarak bir tanesinin girmesini sağlar. Flag değişkeni ise o anda kritik alan girmek isteyen diğer işlem olup olmadığını kontrol eder.
Örneğin P1 işlemi, kritik alana girmek istemiyorsa, P2 işleminin kritik alana girerken turn değişkenine bakmasının bir anlamı yoktur. Benzer şekilde P2 işleminin kritik alan ihtiyacı yoksa, P1 de turn değişkenine bakmaz. Ancak iki işlem (yani P1 ve P2) aynı anda kritik alana girmek istiyorlarsa turn değişkeni anlamlı olur.
Bu tip beklemelere meşgul bekleme (busy wait) ismi verilir. Bu ismin verilme sebebi, işlemin sürekli olarak değişkenin değerine bakarak değeri değişene kadar beklemesidir. Bu bekleme işleminin sürekli bir kontrol yapıyor olması, işlemci üzerinde bir yük getirmektedir.
Algoritmanın diğer bir özelliği ise kilitlenme (deadlock) ve kıtlık (starvation) konularına karşı dayanıklı olmasıdır. Algoritmamızda kilitlenme (deadlock) olmayacağı, turn değişkeninin kullanılmasından anlaşılabilir. Bu değişkenin sistemde anlık olarak tek değeri bulunacak (1 veya 0) ve bu değere göre sistem iki işlemden bir tanesini çalıştıracaktır.
Kıtlık (starvation) problemini görmek için ise bir ihtimalin daha hesaplanması gerekir. Buna göre örneğin P1 çalışıyor ve P0 bekliyorken, P1 işini bitirip P0’ın kilidini kaldırdığında P0 henüz çalışmaya başlamadan P1 yeniden çalışıyor mu diye algoritmaya bakmalıyız. Diğer bir deyişle, sürekli olarak kritik alana erişmeye çalışan P1 ve P0 işlemlerinden örneğin P1 işini bitirip kritik alandan çıktından sonra henüz P0 kritik alana girmeden yeniden P1 kritik alana giriyorsa kıtlık (starvation) oluşuyor demektir.
Algoritmada böyle bir durum yaşanmaz. Bunun sebebi algoritmanın kullandığı flag değişkenidir. P1 işlemi, kritik alandan çıkarken, beklemede olan P0 işleminin bariyerini kaldırır ve bu kaldırma sonucunda P0 işlemi çalışırken P1’in yeniden çalışmasını engelleyici biçimde, diğer tarafın flag değişkenini atar.
Kısaca algoritma kilitlenme (deadlock) ve kıtlık (starvation) ihtimallerine karşı başarılı bir şekilde çalışır.