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

ÇÖ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)


6 yıl 6 ay önce eklendi

Basketbolun kuralları (kısaca) Roma rakamlarının yazılışı, roma rakamları nasıl yazılır? Şapka Kanunu'na karşı olması sebebiyle idam edilenler Kur'an-ı Kerim'de içki (alkol) ile ilgili ayetler var mı? Bilek güreşi nasıl kazanılır? "Ramazan" Kelimesinin Anlamı Nedir? Coğrafi Keşifler Hangi mahkeme hangi davalara bakar Kendisini ısıtarak kanseri yenen doktor! Din Felsefesi ile ilgili bilgiler Tavsiye Edilen Kitaplar Güzel sanat dallarında kullanılan malzemeler ve özellikleri Yazı Ne Zaman Bulundu Ülkemizde ve dünyada ilk televizyon yayınları ne zaman başladı Eritrosit Nedir, Eritrosit Ne Demek Büyük patlama, kâinatın ilk sakini! Cep telefonlarının SAR değerleri Köpekler Çikolata Yerse Neden Ölür? İllerin telefon alan kodları 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