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

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 ] = ""
        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 ] == "" 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)


8 yıl 5 ay önce eklendi

Hz. İbrahim'in Kısaca Hayatı Türk Sanat Müziği şarkıları listesi Engelliler hakkında bilgiler Anneler Günü ile ilgili şiirler Kurtuluş savaşı ne zaman başladı ve bitti Sektörlere göre elektrik tüketimi En ilginç bilimsel deneyler Alo ne demektir? 2018 Kurban Bayramı Tarihi Ünlü Matematikçiler ve Hayatları 2 Kobe Bryant'ın Hayatı Güzel Sanat dallarından eser olarak kabul edilmesi için geçirdiği aşamalar Hangi akarsu üzerinde hangi baraj var Kaykay Hakkında Detaylı Bilgiler Silgi nasıl yapılır Enerji kaynaklarının çevreye olumsuz etkileri Doğal afetler nelerdir, doğal afetler hakkında bilgi Batıl inançlar Vücudunuz hakkındaki inanılmaz gerçekler Makarna (Spagetti) Yiyen Düşünürler Problemi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28