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)


13 yıl 4 ay önce eklendi

Sabah namazının kazası nasıl kılınır? Gitarla kolay çalınan şarkıların akorları İngiliz kız isimleri Doğa ile ilgili şiirler Dünyaca ünlü bilim adamlarımız ve sanatçılarımız Osmanlı Devleti'nin Padişahları Kimlere zekat verilir? Topkapı Sarayı'nda 5 Asırdır Kesintisiz Kur'an-ı Kerim okunuyor Son kapattığınız TAB'ı yeniden açma kısayolu Ünlü Matematikçiler ve Hayatları 1 Prenses Isabella Fortuna kimdir, Isabella Fortuna'nın özgeçmişi Mona Lisa Resminin Özellikleri Şizofren Nedir? Şizofren Ne Demek Gizli Dosyaları Göremiyorum, Gizli Dosya ve Klasörleri Nasıl Görebilirim? Uçağı Kim icat etti (Wright Kardeşler) Enerji kaynaklarının çevreye olumlu 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