Makarna yiyen filozoflar problemi

Reyizlerin reyizi Edsger Dijkstra 1965 yılında, ögrencilere ne sorsam, ne sorsam diye düşünürken "dining philosophers problem" diye bir problem icad etmiş.

Problemin tanımı basit.

Resimdeki masada 5 tane filozof oturduğunu düşünün. Filozoflarımızın yaşam şifreleri çok basit. Düşünüyorlar, acıkınca da yemek yiyorlar. Sonra tekrar düşünmeye devam ediyorlar; sonra tekrar yemek yiyorlar. Sonsuza kadar gidiyor bu durum.

Masada ise sadece 5 tane çatal var. İşin tricky kısmı ise şu; bir filozof ortadaki makarnayı yemek için 2 tane çatala ihtiyaç duyuyor.

Dolayısıyla bir filozofun yaşam döngüsü şu şekilde:

while True:
    dusun();
    catallari_al();
    makarnayi_vur();
    catallari_birak();

Çözmemiz gereken problem ise şu:

Tüm filozoflar aynı anda yemek yemeye kalkarsa sofrada yeterince çatal (resource) yok. Dolayısıyla, bu filozofların yönetimi, kaynak paylaşımı nasıl olmalı ki, yemeye niyetlenen bir filozof mutlaka -eninde sonunda- iki çatal elde edip yemeğini yiyebilmeli.

Dikkat etmemiz gereken şeyler:

Filozoflar(Threadler) arasında Deadlock oluşmamalı. Örneğin, sonsuza kadar birbirini bekleyen filozoflar (Bırak şu çatalı da yiyelim!)
Herhangi bir filozof aç kalmamalı. (4 tanesi götürdü, vurdu makarnaları, biri aç kaldı. Olur mu? Olmaz.)
Aynı anda birden fazla filozof makarna yiyebilmeli.

Filozof Sınıfı

Filozofların hangi çatalları alıp kullanmaları gerektiği konusunda 2 yardımcı metod yazalım. isimleri left ve right olsun.

class Philosopher:

    def __init__(self, *args, **kwargs):
        self.index = kwargs.pop("index")

    @property
    def left(self):
        return self.index

    @property
    def right(self):
        # when it gets to 5, (4 + 1) % 5 = 0
        return (self.index + 1) % 5

Her filozofun 0..4 arası index'i olduğunu varsayarsak; çatalları da bu indexle aynı şekilde ilişkilendirebiliriz.

left metodu; filozofun numarası ile aynı sonucu versin. 4.filozof sol eline 4.çatalı alsın.
right metodu ise mod5'e gore index+1'i versin. 4.filozof, sağ eline 0. çatalı alacak bu şekilde. (masa yuvarlak, filozof ve çatal sayısı 5.)

class Philosopher:

    def __init__(self, *args, **kwargs):
        self.index = kwargs.pop("index")

    @property
    def left(self):
        return self.index % 5

    @property
    def right(self):
        # when it gets to 5, (4 + 1) % 5 = 0
        return (self.index + 1) % 5

çatalları ise, bir liste halinde hepsi birer semafor olacak şekilde tanımlayalım. (Semafor kullanıyoruz, zira 2 filozof aynı anda, aynı çatala meyledebilir, critical section'da kavga etmesinler.)

forks = [Semaphore(1) for i in xrange(5)]

Filozofa ekleyeceğimiz sadece 2 metod kaldı. getforks(), ve putforks()

getforks() -> çatalları al, yemeye başla.
putforks() -> yemeni bitir, çatalları geri bırak.

def get_forks(self):
    self.forks[self.left].acquire()
    self.forks[self.right].acquire()

def put_forks(self):
    self.forks[self.left].release()
    self.forks[self.right].release()

Bir filozof, çatal alacağı zaman önce solundaki çatalı bekliyor. Eğer çatal boştaysa (Semaforlar sağolsun) alıyor, sonra sağdaki çatalı bekliyor. Eğer o da boştaysa amenna, direkt makarnayı göturmeye başlıyor. (random çalışma süresi olan bir self.eat metodu ile)

Çatallara erişim semaforlar tarafından kontrol edildiği için her şey güzel gibi. Kodların çalışan, derli toplu hali dining-philosophers-deadlock.py üzerinde var.

Bu kodu 3-5 defa çalıştırın sisteminizde python varsa. Birkaç denemeden sonra şöyle bir deadlock ile karşılaşacaksınız.

$ python dining-philosophers-deadlock.py

1 got the left fork 1
2 got the left fork 2
4 got the left fork 4
0 got the left fork 0
3 got the left fork 3

Tüm filozoflar, aynı anda sol çatallarını aldı. Sağdaki çatalın boşalmasını bekliyor. Ama boşa düşmeyecek hiçbiri; zira, hepsi beklemede.

Bu duruma terminolojide deadlock diyoruz. Grup halinde threadlerimiz, sürekli askıda birbirlerinden işlem bekliyorlar.

Çözüm

65'ten bu yana bu problem çokca tartışılmış ve çeşitli çözümler getirilmiş. Ben en beğendiğim çözümü uygulayacağım.

Aynı anda maksimum 4 filozofa işlem yapma izni verirsek, bu durumdan kurtulabiliriz. En kötü ihtimalle 4 filozof birden de sol çatalı kaldırsa, 1 tane sağ çatal boşta olacak; ve filozoflardan biri yemeye devam edebilecek.

Az önce yazdığımız koda ufak bir değişiklik yaparak bu durumu elde edebiliyoruz.

multiplex = Semaphore(4)

diye bir semafor daha tanımlayıp;

def get_forks(self):
    self.multiplex.acquire()
    self.forks[self.left].acquire()
    self.forks[self.right].acquire()


def put_forks(self):
    self.forks[self.left].release()
    self.forks[self.right].release()
    self.multiplex.release()

Filozofların çatalları aldığı yerde, multiplex'in değerini bir düşürüp, çatalları bıraktığı yerde ise multiplex değerini bir arttırıp aynı anda maksimum 4 filozofun yeme işlemiyle meşgul olabileceğini karara bağlamış oluyoruz.

Terminojide bu pattern'e ise multiplex deniyor.

Örneğin bir cafe sahibisiniz. Ağırlayabileceğiniz kişi sayısı belli. Aynı anda cafenizde N kişi bulunabilir. Cafenizin içerisini de critical section olarak düşünün. Bu durumda Semaphore(N) gibi bir semafor yardımıyla, içerdeki kişilerin hesabını tutar, gereğinden fazla yük altında kalmazsınız.

Çözümün derlenmiş toplanmış, çalışır hali ise dining-philosophers-multiplex.py adresinde. Başka semafor puzzle'ları ile ilgilenirseniz de repoya bekleriz.

Problemle ilgili diğer detaylara ve diğer çözümlere ise wikipedia/Diningphilosophersproblem üzerinden ulaşabilirsiniz.

Tags: concurrent programming, dijkstra

Emre Yılmaz

Filozof Sınıfı