One Lane Bridge (Tek Şeritli Köprü) Problemi

Yazan : Şadi Evren ŞEKER

Bu problemde, tek şeritli bir köprünün iki ucundan gelen araçların karşıya geçmesini senkronize etmemiz isteniyor. Köprü tek şeritli olduğu için anlık olarak bir yönde araç geçişi mümkün olabiliyor. Bir aracın karşıya geçmesi, ancak karşı taraftan gelen araç olmadığı zaman mümkündür. Köprünün iki tarafında da duyargaların (sensor) yerleştirildiğini düşünelim ve aynı zamanda iki tarafta da trafik ışıkları bulunsun. Bu durumda her aracın bir işlem (process) olarak düşünülüdğü sistemde Varma () ve Ayrılma() fonksiyonlarını kodlamamız isteniyor. Ayrıca bu fonksiyonlara, işlemler tarafından yön bilgisinin geçirilebileceğini de kabul edebilirsiniz.

Şekilde görüldüğü üzere köprünün iki tarafında da bekleyen araçlar bulunmakta ve bu araçlardan anlık olarak bir araç karşı tarafa geçebilmektedir.

Çözüm:

Problemin çözümü için öncelikle bir global değişken tanımlamamız gerekiyor. Bu değişken, o anda bulunan araç sayısını tutacak. İkinci bir değişken ise o andaki köprünün akış yönünü tutmaktan sorumlu olsun. Yani bütün işlemler (processes) bu değişkenlere erişebilecek ve dolayısıyla anlık olarak hangi yönde akışın olduğu ve kaç araç bulunduğu bilgisi bütün işlemler için erişilebilen tek bir yerde tutulacak. Elbette bu tanım anında bir senkronizasyon problemini beraberinde getiriyor.

Temel olarak eş programlama (concurrent programming) problemlerinde iki problem bulunur. Bunlar:

• Eş farklılık (Mutual Exclusion)

• İlerleme (Progress)

Olarak bilinir. Yani aynı anda bir işlemin çalışması ve birden fazla işlemin çalışmasının engellenmesi eş farklılık problemi olarak geçerken, herhangi bir işlemin kilitlenmemesi (deadlock) kıtlığa girmemesi (starvation) veya problemin çözümüne ilerleme kat edilmesi ilerleme (progress) olarak geçer.

Bu soruları eğitim amacıyla çözdüğümüz için bu problemde iki farklı senkronizasyon (synchronisation) yöntemini beraber kullanacağız. Öncelikle eş farklılık (mutex) için kilit (lock) senkronizasyonu kullanacağız, ardından kritik alanımız olan (critical section) yön değişimi için koşullu değişken (conditional variable) kullanacağız.

Eş farklılık için (mutex) bütün işlemlerden önce kilit koyup bütün işlemlerden sonra kilidi açıyoruz.

İlerleme için (yani bir taraftan araç geçiyorken, diğer taraftan araç gelmesi halinde, diğer taraftaki aracında günün birinde geçmesini sağlamak için) koşullu değişken (conditional variable) kullanacağız. Bunu yön değiştirme işleminde yapıyoruz. Bir araç köprüyü terk edince (depart) yön değiştirmek mümkün hale gelir. Bu durum olunca köprünün iki yanında bekleyen araçlara duyurularak bir yarış koşulu (racing condition) oluşturulur, kim önce bu yarışı kazanırsa o taraftan araçlar geçmeye başlar.

int arac_sayisi = 0; 
enum yon = {acik, sola, saga}; 
yon kopru_yonu = acik; 
Lock *lock = new Lock(); 
Condition *cv = new Condition(); 


void Depart (yon aracin_yonu) { 
   lock->Acquire(); 
   arac_sayisi--; 
   if (arac_sayisi == 0) {
      kopru_yonu = acik;
      cv->Broadcast(lock);
   }
   lock->Release();
}



void Arrive (yon aracin_yonu) 
   lock->Acquire();
   while (kopru_yonu != aracin_yonu || kopru_yonu != acik) { 
         cv->Wait(lock);
   }
   arac_sayisi++;
   kopru_yonu = aracin_yonu;
   lock->Release(); 
} 

Yukarıdaki çözümde, yön değiştirme durumu olan kopru_yonu = aracin_yonu şeklindeki satırdan önce aracin yönündeki hareketin mümkün olup olmadığı bir whilde döngüsü ile kontrol edilmektedir. Bu kontrolden geçildikten sonra kritik alanımız olan (critical section) köprünün yönünü değiştirme işlemi çalıştırılabilir.

Yukarıdaki çözümde, kilitlenme riski (deadlock) bulunmaz çünkü anlık olarak tek bir işlem (process) çalışabilir, bu durum mutex uygulaması ile güvenceye alınmıştır.

Yukarıdaki çözümde tek sorun, kıtlık olma ihtimalidir (starvation) bunun sebebi bir yönden gelen araçların diğer yönden gelenlere göre öncelik kazanması ve yarış durumu (racing condition) düşünüldüğünde sıranın hiç karşı tarafa geçmemesi ihitmalidir. Bu durumu da çözmek için belirli bir sayı belirleyelim, örneğin n olsun. Bu n sayısından fazla bir yönden araç, diğer yönden araç geçmeden arka arkaya geçememeli kuralı koyabiliriz. Örneğin n = 5 olsun, bu durumda sağdan sola arka arkaya en fazla 5 araç geçebilir ve sonra durup soldan sağa geçmeyi bekleyecektir. Bu kuralımızı koda eklersek aşağıdaki gibi bir durum ortaya çıkar:

int arac_sayisi = 0; 
int n = 5;
int solsayac = 0;
int sagsayac = 0;
enum yon = {acik, sola, saga}; 
yon kopru_yonu = acik; 
Lock *lock = new Lock(); 
Condition *cv = new Condition(); 


void Depart (yon aracin_yonu) { 
   lock->Acquire(); 
   arac_sayisi--; 
   if(aracin_yonu == sola){
     sagsayac = 0;
     solsayac++;
   }
   else{
     sagsayac++;
     solsayac= 0;
   }
   if (arac_sayisi == 0) {
      kopru_yonu = acik;
      cv->Broadcast(lock);
   }
   lock->Release();
}



void Arrive (yon aracin_yonu) 
   lock->Acquire();
   if(aracin_yonu == sola && solsayac >= n)
	   cv->Wait(lock);
   if(aracin_yonu == saga && sagsayac >= n)
	   cv->Wait(lock);
   while (kopru_yonu != aracin_yonu || kopru_yonu != acik) { 
         cv->Wait(lock);
   }
   arac_sayisi++;
   kopru_yonu = aracin_yonu;
   lock->Release(); 
} 

}

Yukarıdaki yeni çözümde, aracin geldiği yön ile bu yönün sayaçlarına bakılmakta, şayet aracın geldiği yönde, tanımlı olan n değeri kadar veya daha fazla araç geçiş yapmışsa bu araç bekletilmektedir.

Araçların ayrılması sırasnda ise, ayrılan aracın tersi istakemtindeki sayaç sıfırlanmaktadır (çünkü bu yöndeki araçların arka arkaya geçmesi durumu bozulmuş, ters yönden bir araç geçmiştir).

Ayrıca araçlar köprüyü terk ederken, artık geçme işlemi tamamlandığına göre aracın yönünden geçen araçların sayısı bir arttırılmaktadır.

Yukarıdaki yeni çözümde, kıtlık ve kilitlenme problemleri çözülmüş olur. Ancak bir tehlike kıtlık (starvation) çözümünü getirirken tanımladığımız n değerinin 1 olması durumudur. Bu durumda kilitlenme olma ihtimali bulunur ve okuyucu bunu kendisi deneyerek bulabilir.

Ayrıca ben işletim sistemleri dersini alırken (sene 1998 ) vizede aynı soru sorulmuş ve soruyu boruhattı (pipeline) yaklaşımı ile çözmeye çalışmıştım. Neden böyle bir zorluk çıkardığımı bilmiyorum ama o zamanki yaklaşımıma göre bir yönde bir araç geçerken arkasından birden fazla aracın takip edebileceği ve köprü üzerinde anlık olarak i tane araç bulunabileceği kabulü ile soruyu çözmüştüm (sanırım gerçek hayatta bu şekilde olduğu için). Bu yaklaşımın genel olarak senkronizasyona bir etkisi olmamakla birlikte, yön değiştirme kararlarının köprüden geçmeyi bekleyen araçların bekleme sürelerine etkisi olmaktadır. Bu durum aslında senkronizasyon problemi ile birlikte işlemci zamanlamasında kullanılan yaklaşımların da tasarıma eklenmesini gerektirir. Okuyucu bu durumu çözerek deneyebilir.

Diğer İşletim Sistemi Senkronizasyon Problemleri ve Çözümleri:

• Producer Consumer Problem (Üretici Tüketici Problemi)

• Dining Philosophers Problem (Filozofların Akşam Yemeği)

• Sleeping Barbers Problem (Uyuyan Berberler Problemi)