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)


7 yıl 4 ay önce eklendi

Namazda rukû ve secdede ne söylenir? Klasik gitar notaları Yeşilay haftası şiirleri Yunus Emre şiirlerinden örnekler II. Mehmet (Fatih Sultan Mehmet) Dönemi (1451-1481) Telgraf nedir, telgrafın çalışması İllere ve belediyelere bütçeden ayrılan mali kaynaklar 1916 Sykes-Picot Antlaşması Din Felsefesi Dünyadaki farklı ırklar Tasavvuf felsefesi nedir, Tasavvuf felsefesinin özellikleri Pablo Picasso kimdir, Pablo Picasso'nun hayatı 2008 yılında dünyadaki nükleer santraller ve konumları Bir bardak kolanın dakika dakika zararları nelerdir? Kağıdı kim buldu, Kağıt icadı Sıvı ölçüleri Karınca duası, Karınca duasının okunuşu ve anlamı Akvaryum Balık Türleri, Akvaryum Balıklarının İsimleri ve Özellikleri 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