Makarna (Spagetti) Yiyen Düşünürler Problemi

En eğlenceli bilgisayar problemlerinden biridir.

N adet düşünür bir masanın etrafına oturmuştur.

Bunlar yeterince düşündükten sonra acıkırlar.

Her birinin önünde birer tabak makarna vardır.

Tüm tabakların arasında da birer çatal bulunmaktadır.

Dolayısıyla N adet makarna tabağı ve N adet çatal vardır.

Düşünürler ne yazık ki iki çatal kullanmadan makarna yiyememektedir.

Dolayısıyla yan yana oturan iki düşünür aynı anda makarna yiyememektedir.
N kişilik bir masada en fazla tamsayı ( N/2 ) adet düşünür yemek yiyebilir.

Düşünürlerimizin hiçbiri aç kalmayacak şekilde, düşünürlerin hayatları bilgisayar ortamında nasıl modellenmelidir?

HATALI ÇÖZÜM

proses düşünür ( i : integer )
{
    while ( true ) do
        düşün ( );
        çatal_al ( i );
        çatal_al ( (i+1) mod N );
            ye ( );
        çatal_bırak ( i );
        çatal_bırak ( (i+1) mod N );
    end while
}

Herbir düşünür yukarıdaki şekilde düşünürse oluşabilecek problemi görebildiniz mi?

Öyle bir an gelebilir ki, her düşünür sadece çatal_al ( i ); komutunu çalıştırabilir.

Bu durumda her biri sağ eline çatalı alabilecek, diğer eli boş kalacaktır.

Dolayısıyla, her biri açlıktan ölebilir :) Kimse çatalını bırakmıyor.

Sonuç: Ölümcül Kilitlenme

DOĞRU ÇÖZÜM

Elimizdeki düşünürler sadece 3 işlem yapmaktadırlar.

Hayatlarını durum geçiş diyagramı ile gösterelim:

Birbirleriyle aynı anda bazı işlemleri yapamamaları sağlanmalıdır.

Semafor: İşletim sistemi desteği ile karşılıklı dışlamanın çözüldüğü yapı.
Kritik bölgeye girişi P ( sem ), çıkışı ise V ( sem ) ifade etsin.

durum [ 1...N ] // her düşünürün durumu
sem_dışla = 1 // kritik bölgeye tek girişi garantiler
sem_izin [ 1...N ] // kullanıcıların kullanım izni

proses düşünür ( i : integer )
{
    while ( true ) do
        düşün ( );
        çatal_al ( i );
            ye ();
        çatal_bırak ( i );
    end while
}

proses çatal_al ( i : integer )
{
    begin
        P ( sem_dışla );
        durum [ i ] = "aç"
        dene ( i );
        V ( sem_dışla );
        P ( sem_izin [ i ] ); // semaforun değeri 1 olmalı ki askıya alınmasın
    end
}

proses dene ( i : integer )
{
    var sağ, sol : integer;
    begin
        sağ = ( i + N - 1 ) mod N;
        sol = ( i + 1 ) mod N;
        if(durum [ i ] == "aç" and durum [ sol ] <> "ye" and durum [ sağ ] <> "ye")
            V ( sem_izin [ i ] );
    end
}

proses çatal_bırak ( i : integer )
{
    var sağ, sol : integer;
    begin
        sağ = ( i + N - 1 ) mod N;
        sol = ( i + 1 ) mod N;
        P ( sem_dışla );
        durum [ i ] = "düşün"
        dene ( sol ); // solumdaki arkadaş için çatalı ele geçirmeyi deniyorum
        dene ( sağ ); // sağımdaki arkadaş için çatalı ele geçirmeyi deniyorum
        V ( sem_dışla );
    end
}

İlginç bir çalışma: Karşılıklı Dışlama (Tek Sayfalık Makale)