Dining Philosophers Probleminin Semaphore’lar İle Çözümü

Dining Philosophers Probleminin Semaphore’lar İle Çözümü


5 filozof bir yuvarlak masa etrafında oturmaktadır. Bu filozoflar yemek yiyeceklerdir. Yemek yemek için yeterli ve gerek şart filozofun oturuduğu  koltuğun sağında ve solunda bulunan her 2 çatalada sahip olmasıdır.Yani filozofun masanın ortasındaki yemeği yiyebilmesi için 2 adet çatala ihtiyacı vardır ve masada 5 filozofun aynı anda yemek yiyebilmesi için yeterli sayıda çatal yoktur.

Bu problemin çözümü ile işletim sisteminin kısıtlı kaynakları deadlock olmayacak şekilde istemcilere nasıl ve hangi kurallar ile dağıttığı modellenmek istenmiştir.Aynı zamanda Dining Philosophers problemi tipik bir senkronizasyon ve deadlock problemidir.

Oluşabilecek Sorunlar : Bu problemde sonucu deadlock olabilecek belli başlı sıkıntılar karşımıza çıkmaktadır.Oluşabilecek sıkıntıları ayrı ayrı incelersek;

1)       Her filozofun aynı anda ve kendilerine göre aynı yöndeki (solundaki veya sağındaki) çatalı alması ile masada bulunan filozofların hiç birinin yemek yiyememe teknik tabirle ilerleyememesi gerçekleşebilir.Bu durumda masaadaki her filozofun elinde 1 çatal bulunur ve hiç biri yemek yeme işlemini gerçekleştiremez. Olayın bu hali alması ile olası 4 deadlock(Mutex,Hold and Wait,No-Preeemption,Circular Wait) şartı gerçekleşmiş olabilir ve sistem bunun sonucunda deadlock’a düşebilir.Bu durumu aşmak için senkronizasyon işleminin doğru bir şekilde yapılması gerekmektedir.

2)       Filozofların 2 sinin yemek yiyebildiği durumu düşünürsek ; yemek yiyen filozofların yemek yeme işlemi bittiğinde yada yemek yeme işlemi belli bir süre yapıldıktan sonra çatalların yemek yemeyi bekleyen filozoflara aktarımı gerçekleşmez ise bu filozoflar starvation yaşayabilir ve ilerleyemezler.Bu durumun sonunda da yine olay deadlock boyutunu alabilir. Bu durumda çatalların el değiştirme işleminin dikkatli,senkron ve düzenli yapılması gerekmektedir.

3)       Bu problemde karşılaşabileceğimiz bir diğer sorunda senkronizasyon problemidir. Bu problemi şu şekilde açacak olursak , bir filozofun yemek yiyebilmesi için yeter şart 2 çatalada eş zamanlı sahip olabilmesi ise filozof bir çatalı aldığı anda diğerinide senkron bir şekilde elinde bulundurmalıdır. Bunu yapamadığı takdirde zaten yemek yeme işlemini gerçekleştiremeyecektir.Bu sebepten ötürü çatalları senkron bir şekilde ele alabilme işlemi bölünmez (atomik) bir yapı veya komşu filozofun elindeki çatalı ihtiyacı olan filozofun kullanması için masaya bırakması ile gerçekleştirilebilecektir.Bu durumda filozof aynı anda 2 çatalıda elinde bulundurup yemek yeme işlemini gerçekleştirebilir.

Önerilen Çözüm :

 

Bu problemlin çözümünde semafor yapısından yararlanacak olursak.Toplam 6 adet semafor kullanmamız problemin çözümü için yeterli olacaktır.

Semaforlardan 5 tanesini; herhangi bir çatallın aynı anda yalnızca 1 kişi tarafından kullanılabilmesi için yani mutual exclusion’ı sağlamak için kullanıcaz. Bu kullanacağımız 5 semafor her bir çatalı ifade etmekte ve binary tipinde olmaktadır.Bu sayede bir anda 1 çatalı yalnızca 1 kişinin kullanabileceğini garanti etmiş oluyoruz.

Kullanacağımız diğer semafor ise senkronizasyonu sağlamak için kullanacağımız semafordur. Bu semafor ise 4 değerine sahip olacak bir semafordur. Bu semafor değerinin 4’ten başlamasının sebebi ise bu durumla ilgili kritik bölgeye 4 kişi alınması sonucunda filozoflardan 1’nin mutlak suretle yemek yiyebilmesidir. Bu değer 5 olsaydı her filozof 1 çatal alıp sistemin kitlenmesine sebebiyet verecekti. Bu değer 4 yapılarak bu durum engellenmiş ve en az 1 filozofa hizmet verme işlemi garanti edilecektir.

Bir filozof yemek işlemeye başlamadan önce ilk başta bakacağı semafor senkronizasyon ile ilgili semafor değeri olacaktır. Eğer bu semaforun korumuş olduğu kritik bölge girilmeye müsait ise filozof bu bölgeye alınacaktır. Bu bölgeye girildikten sonra ilgili semaforun değeri bir azaltılacaktır. Daha sonra filozof sağındaki ve solundaki çatallara ait semafor değerlerini kontrol edecektir eğer bu çatallar alınmaya müsait ise ilgili semafor değerlerii azaltılıp yemek yeme işlemi gerçekleştirilecektir.Yemek yeme işlemi bittikten sonra ilgili çatalların serbest bırakılması için semafor değerleri 1 e set edilip ,çatalı bekleyen filozoflara sinyal yollanacaktır.Daha sonrada senkronizasyon semaforu 1 arttırılıp kritik bölgeden çıkılacaktır. Böylelikle hem senkronizasyon , hem mutex , hemde circular wait sorunu ortadan kaldırılmış dolayısıylada deadlock sorunu ortadan kaldırılmış olacaktır.Önerilen yöntemin akışı aşağıdaki gibidir.

Örnek Pseudo Code:

Semaphore fork[5]={1,1,1,1,1}

Semaphore allowToEat(4);

void philosoper(int id )

{

for(int i=0;i<3;i++)

{

think();

SW(allowToEat);

SW(fork[id]);

SW(fork[id+1%5]);

/ /Critical Section’a Girildi

eating();

SS(fork[id]);

SS(fork[id+1%5]);

SS(allowToEat);

}

think();

}

Referanlar

1-       http://www.cs.mtu.edu/~shene/NSF-3/e-Book/MUTEX/TM-example-philos-1.html

2-       http://www.doc.ic.ac.uk/~jnm/concurrency/classes/Diners/Diners.html

3-       http://laser.cs.umass.edu/verification-examples/dp_standard/dp.html

4-       http://en.wikipedia.org/wiki/Dining_philosophers_problem

5-       http://www.standford.edu

Advertisements

About ... from Emrah METE

Bilgisayar Mühendisi
This entry was posted in Operating Systems, Uncategorized and tagged , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s