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

Bu sayfada, klasik eşzamanlılık (concurrency) problemlerinden biri olan “Makarna (Spagetti) Yiyen Düşünürler Problemi” ele alınmaktadır. Problem, çok sayıda sürecin paylaşımlı kaynaklara erişim sırasında nasıl senkronize edilmesi gerektiğini modelleyen temel bir düşünce deneyidir. Özellikle kilitlenme (deadlock), aç kalma (starvation) ve yarış durumu (race condition) gibi işletim sistemi kavramlarını açıklamak için kullanılır. Aşağıda bu probleme yönelik modelleme, çözüm yaklaşımları ve örnek uygulamalar yer almaktadır.

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)