The Dining Philosophers Problem
The Dining Philosophers Problem, 1965 yılında Edsger W. Dijkstra tarafından ortaya atılmıştır. Hayatını sadece düşünerek ve yemek yiyerek idame ettiren beş filozof hayal edin. Yemek odasının ortasında yuvarlak bir masa ve beş sandalye olsun. Masada da bir koca tabak yemek var. Ancak aşağıdaki figürde de görüldüğü gibi yalnizca beş tane yemek çubuğu bulunuyor. Her filozof düşünüyor, ne zaman acıkırsa en yakınındaki yemek çubuklarını alıyor. Eğer bir filozof her iki çubuğu da alırsa belli bir süre için yemek yiyebiliyor. Bir filozof yemeğini bitirdikten sonra çubukları bırakıyor ve düşünmeye başıyor (filozoflarımız konuşamaz , yazamazlar ve benzeri hareketlerde bulunamazlar).
The Dining Philosophers Problem, eşzamanlı programlama için standart bir alıştırmadır. Özellikle işletim sistemleri ve dağıtık sistemlerin tasarımı konsunda öğreticidir. Paylaşılan ya da kıt kaynakların yönetimini ele aldığı için ilgi çekici; beceriksizce hazırlanmış birçok uygulamanın kilitlenme (deadlock) yaşayacağı; kurnazlık gerektiren bir problemdir.
Programlama aşamasındaki problem, filozofların belli bir düzen içinde birbirleri arasında yemek çubuklarını kontrol edebilmelerini, paylaşabilmelerini sağlayacak bir simülasyon oluşturmaktır..
Hemen hemen her tipik çözümde filozoflar aşağıdaki gibi bir döngü izlerler:
herzaman{
düşünür (meşgul)
sol çubuk için bekler
sağ çubuk için bekler
yemek yer (meşgul)
sol çubuğu bırakır
sağ çubuğu bırakır
}
Burada meşgul olarak tanımladığımız deyimler, zamanı temsil etmek için kullanılmıştır. Zamanın uzunluğu genelde rastgele olan bir niceliktir. Bekleme deyimleri genelde yemek çubuklarını almak mümkün olana kadar programın çalışmasını önleyen semafor'ları ya da diğer mutex'leri (mutual exclusion) temsil etmek için kullanılır.
Eğer her filozof sol yemek çubuğunu alır ve sağdaki için beklerse, sistem kilitlenir. Filozoflar asla ikinci yemek çubuklarını alamayacağı için, işlemler hiçbir zaman ileri gidemez. Rastgele oluşan meşgul periyodları kilitlenme oluşmasını azaltabilir ancak engelleyemeyeceği de aşikardır. Ara sıra olan kilitlenme durumları gerçekten büyük bir problemdir; kopya edilmesi, tespit edilmesi, çözüm bulunması oldukça zordur. Kilitlenme durumu, dağıtık sistemlerin en tehlikeli problemlerden biridir.
Bazı çözümler, filozofları önce sağ yemek çubuklarını alacak şekilde modifiye ederler. Bu kilitlenmeyi önler ancak, özel bir çözümdür. Diğer durumlarda oluşan kilitlenmeleri engelleyecek şekilde genellenemez. Bazı uygulamalar, garsonlar, odalar, sandalyeler ve kilitlenmeyi önleyebilecek daha birçok nesne içerirler. Bu çözümler tam olarak genelleştirilemediği gibi, oldukça da karmaşıktır.
Birçok çözüm, filozofları doğru şekilde hareket ettirebilme esasına
dayanır. Örneğin, bir filozof yemek çubuklarını alır ve asla
bırakmazsa, yanında oturan filozof bir süre sonra açlıktan ölür.
Peki filozofların bu durumunu betimlemek için nasıl bir program yazabiliriz? İlk önce, filozofların düşünme- çubukları alma- yemek yeme- çubukları bırakma şeklinde bir işlem devrine sahip olduğuna dikkat etmeliyiz.
Görüldüğü gibi buradaki anahtar nokta çubukları alma işlemidir. Bir filozof çubukları nasıl alabilir? Aslında problemin birçok çözüm yolu mevcuttur; eğer tüm filozoflar sağ yemek çubuklarını alırsa, hiçbiri solundakini alamaz. Ve herbiri sağ çubuklarını ellerinde tutarsa ve sol çubuk için beklerse hiçkimse yemek yiyemez. Bu durum kilitlenme (deadlock) olarak adlandırılır. Eğer birkaç filozof, diğerlerinin yemesi için çubuklarını bırakırsa o zaman hiçbir zaman yemek yiyemezler. Bu durum starvation (açlık) olarak adlandırılır. Başka bir olasılık ise tüm filozoflar yemek yer ancak bazıları diğerlerinden daha fazla yer. Bu durum ise lack of fairness (adaletsizlik)olarak adlandırılır. Her bir yemek çubuğu iki filozof tarafından paylaşılmaktadır ve bu nedenden dolayı paylaşılar kaynaklar durumundadırlar. Şüphesiz ki, bir filozofun zaten çoktan komşusu tarafından kullanılan yemek çubuğunu almasını istemeyiz. Görüldüğü üzere bu bir yarış koşuludur (race condition). Okumakta olduğunuz dökümanın ilerliyen kısımlarında bu problemlerden bazıları ele alınmıştır.
Problemi belirtmek için, her bir yemek çubuğunun bir mutex kilit tarafından bir paylaşılan parça olarak korunduğunu gözüne almalıyız. Her filozof yemeğini yemeden önce, sağ ve sol yemek çubuğunu kilitler. Eğer iki edinti de başarılıysa filozofumuzun artık iki kilidi vardır (yani iki yemek çubuğu) ve yemeğini yiyebilir. Yemek yemeyi bitirdikten sonra, artık filozofumuz çubuklarını bırakıp düşünmeye başlayabilir. Aşağıda bu uygulamanın akış şeması gösterilmektedir:
Her yemek çubuğu bir mutex kilitle ilişkilendirilmiştir ve yemek çubuklarını kilitlemek ve serbest bırakmak durumundayız. Eşzamanlı olarak düşünüp yemek yedikleri için her filozof için bir tane olmak üzere beş adet iş parçacığı (thread) yaratmak zorundayız. Her filozof, sağ ve sol olmak yemek çubukları olmak üzere iki mutex kilidine erişebildiği için, mutex kilitleri global değişkenler olarak tanımlanmıştır.
Şimdi yukarıdaki çözümlemenin programa nasıl dönüştürüleceğini görelim; her filozof bir iş parçacığı(thread) olarak koşturulması gerektiğine göre, Thread sınıfından türetilmiş bir Philosopher sınıfı tanımlayalım.
#define PHILOSOPHERS 5
class Philosopher: public Thread
{
public:
Philosopher(int Number, int iter);
private:
int No;
int Iterations;
void ThreadFunc();
};
|
| Dosyayı indirmek için burayı tıklayın (Philosopher.h). |
Hazırlayıcı (constructor) iki argüman alır, filozof iş- parçacığı için atanmış sayı Number ve düşünme- yeme çevrim sayilarini belirtmek için iter.
Bu sınıfın gerçekleştirilebilmesi için, aşağıda gösterildiği gibi, bütün düşünme, yeme, kilitleme ve serbest bırakma mekanizmalarının gerçekleştirilmesi gerekmektedir. Her bir yemek çubuğu bir mutex kilit tarafından korunduğu için, Mutex'e Chopstick[] şeklinde bir gösterici (pointer) dizisi tanımladık. Ana program bu kilitleri ayırdığı için, extern kullanılarak global değişken olarak tanımlandı.
Filler() fonksiyonu birkaç aralık barındıran bir karakter (char) dizisi üretir. Fonksiyonun static olarak tanımlandığına ve bu yüzden yalnızca bu dosyanın içinde kullanılabildiğine dikkat edin (Philosopher.cpp).
Şimdi hazırlayıcıya (constructor) bakalım. İki argüman alır. İlki, Number,ana program tarafından iş parçacığının (thread) hangi filozofu gösterdiğini açıklamak için atanmıştır. İkincisi, iter ise her filozof için düşünme- yemek yeme dönüş sayılarını verir. Hazırlayıcı çok basit bir yapıya sahiptir. İş parçacığına (thread) bir isim verir. Örneğin eğer Number'ın değeri 2 ise (ör: filozof 2), bu iş parçacığının adı Philosopher2 olacaktır.
#include <iostream.h>
#include <stdlib.h>
#include "ThreadClass.h"
#include "Philosopher.h"
extern Mutex *Chopstick[PHILOSOPHERS]; // yemek çubukları için kilitler
static strstream *Filler(int n)
{
int i;
strstream *Space;
Space = new strstream;
for (i = 0; i < n; i++)
(*Space) << ' ';
(*Space) << '\0';
return Space;
}
Philosopher::Philosopher(int Number, int iter)
: No(Number), Iterations(iter)
{
ThreadName.seekp(0, ios::beg);
ThreadName << "Philosopher" << Number << '\0';
}
void Philosopher::ThreadFunc()
{
Thread::ThreadFunc();
strstream *Space;
int i;
Space = Filler(No*2);
for (i = 0; i < Iterations; i++) {
Delay(); // bir süreliğine düşünür
Chopstick[No]->Lock(); // sol yemek çubuğunu alır
Chopstick[(No+1) % PHILOSOPHERS]->Lock(); // sağ yemek çubuğunu alır
cout << Space->str() << ThreadName.str()
<< " begin eating." << endl;
Delay(); // belli bir süreliğine yemek yer
cout << Space->str() << ThreadName.str()
<< " finish eating." << endl;
Chopstick[No]->Unlock(); // sol yemek çubuğunu bırakır
Chopstick[(No+1) % PHILOSOPHERS]->Unlock(); // sağ yemek çubuğunu bırakır
}
Exit();
}
|
| Dosyayı indirmek için buraya tıklayın. (Philosopher.cpp) |
ThreadFunc() fonksiyonu bir filozofun iş parçacığı için çalıştırılabilir kodu gerçekleştirir. Herşeyden önce, No*2 boşluğun bir karakter dizisini yaratır, böylece iş parçacığının çıkışı doğru düzgün girintili yazılabilir. Bundan sonra, bu iş parçacığı Iteration zamanlarını yineler. Her dönüşte, bu iş parçacığı düşünme ve yemek yeme olaylarını simüle eder. Bunun sonucunda, Thread: Delay() sınıfının bir metodunu kullanırız. Delay() 'in amacı, basitçe, iş parçacığının çalışmasını geciktirmektir. Bu durum "bir süreliğine düşünmek" ve "bir süreliğine yemek yemek" olaylarını simüle eder.
Şimdi yemek çubuklarının nasıl kilitlendiğine ve serbest bırakıldığına göz atalım. Yemek çubuklarının yelkovan yönünde numaralandırıldığını varsayalım. Filiozof i için, solundaki yemek çubuğu i ve sağındaki yemek çubuğu i+1'dir. Tabii ki , i+1'i doğrudan kullanamayız, çünkü i=4 olduğunda, sağındaki yemek çubuğu 5 yerine 0 olacaktır. Bu problem, PHILOSOPHERS filozofların sayısı olmak üzere, artık kalan operatoruyle (i+1)%PHILOSOPHERS şeklinde çözülebilir. Yukarıdaki kodda, filozof No bir süreliğine düşünür, Chopstick[No]->Lock() metodunu çağırarak sol yemek çubuğunu kilitler, Chopstick[(No+1)%PHILOSOPHERS]->Lock() metoduyla da sağ yemek çubuğunu kilitler, bir süreliğine yemek yer, Chopstick[No]->Unlock() metodunu çağırarak sol yemek çubuğunu serbest bırakır, Chopstick[(No+1)%PHILOSOPHERS]->Unlock metoduyla da sağ yemek çubuğunu serbest bırakır. Bu koşullar bir düşünme- yemek yeme devrini tamamlar. Bu devir Iteration sayısı kadar tekrar eder.
Yukarıdaki kodda her bir filozofun sağ çubuktan önce sol yemek çubuğunu seçtiğine ya da kilitlediğine dikkat edin.
Ana program yine aşağıda gösterilmiştir. Bir filozofun gerçekleştirmesi gereken düşünme- yemek yeme devir sayısı programdaki tek komut satırı argümanıdır.Mutex kilitleri kullanılmadan önce yaratıldığı için, ana program mutex kilitlerini iş parçacıklarını yaratmadan önce ayırır. Bunu takiben her bir mutex kilidi ChopStick0, Chopstick1,..., Chopstick4 olarak adlandırılır. Bütün yemek çubuğu kilitleri yaratıldıktan sonra, ana iş parçacığı, filozof iş parçacıklarını yaratmaya devam eder ve tüm çocuk iş parçacıklarıyla katılır. Bütün filozof iş parçacıkları bittikten sonra, ana iş parçacığı geri gelir.
#include <iostream.h>
#include <stdlib.h>
#include "ThreadClass.h"
#include "Philosopher.h"
Mutex *Chopstick[PHILOSOPHERS]; // yemek çubukları için kilitler
int main(int argc, char *argv[])
{
Philosopher *Philosophers[PHILOSOPHERS];
int i, iter;
strstream name;
if (argc != 2) {
cout << "Use " << argv[0] << " #-of-iterations." << endl;
exit(0);
}
else
iter = abs(atoi(argv[1]));
for (i=0; i < PHILOSOPHERS; i++) { // yemek çubuklarının mutex kilitlerini hazırlar
name.seekp(0, ios::beg);
name << "ChopStick" << i << '\0';
Chopstick[i] = new Mutex(name.str());
}
for (i=0; i < PHILOSOPHERS; i++) { // fiozofların iş parçacıkalrını (thread) hazırlar
Philosophers[i] = new Philosopher(i, iter);
Philosophers[i]->Begin();
}
for (i=0; i < PHILOSOPHERS; i++)
Philosophers[i]->Join();
Exit();
}
|
| Dosyayı indirmek için burayı tıklayın. (Philosopher-main.cpp) |
Aşağıda bu program hakkında çok önemli gerçeklere yer verilmiştir:
Yukarıda starvation'un basit bir örneği gösterilmiştir. Siz de biraz denemeyle daha karmaşık düşünme- yemek yeme silsileleri bulabilirsiniz.
Yukarıda, her bir filozofun sol çubuğu takiben sağ yemek çubuğunu almasıyla gerçekleşen çözümden bahsettik. Ayrıca çözümün kilitlenmeye (deadlock) yolaçabileceğine ve starvation problemi olduğu üzerinde durduk. Şimdi, halen mutex kilitlerini kullanan ancak kilitlenme sorunu olmayan başka bir çözümden bahsedeceğiz.
Bu çözümümüz, kilitlenmekten kurtulmanın pek de zor olmadığını gösterir. Önceki çözümde, her bir filozofun solundaki yemek çubuğunu almasıyla bir kilitlenme olmuştu. Bu da bir dairesel beklemeyi doğurmuştu. Eğer bu dairesel bekleme kırılırsa, kilitlenme de yok olur. Bunun sonucunda, filozoflarımızı değişik şekilde davranmaya zorlayabiliriz. Tam olarak açıklarsak, bir filozofun önce sağ yemek çubuğunu daha sonra da sol yemek çubuğunu almasını sağlayabiliriz. Sol çubuğu takiben sağ yemek çubuğunu alan bir filozof lefty olarak referans edilmiştir, aksi halde righty. Lefty ve righty filozofların toplamının filozof sayısına eşit olmasına ve ikisinin de sıfıra eşit olmamasına dikkat etmeliyiz. Righty filozofların varolması, önceki örnekte gördüğümüz gibi, dairesel beklemeyi kırabilir. Peki gerçekten dava bundan ibaret midir?
Eğer birkaç tanesinin ya da tüm iş parçacıklarının (thread) dairesel beklemeye girmesiyle kilitlenmenin meydana geleceğini anımsayalım. Dairesel bekleme olmadığını gösterdiğimiz sürece, kilitlenme de olmayacaktır. Aşağıda, yalnızca bir tane sağdaki filozof olduğu kabul edilmiştir. Rastgele seçilmiş bir filozof alabilir ve her iki yemek çubuğunu alıp yemek yeme şansı olduğunu gösterebiliriz. Bu seçilmiş filozof P, sağdaki ya da soldaki bir filozof olabilir.
Eğer righty yemek yiyorsa, aşağıda gösterildiği gibi iki yemek çubuğuna sahiptir. Righty yemeğini bitirdiği zaman iki yemek çubuğunu da bırakır, böylece sol komşusuna yemek yeme şansı doğar, sonuç olarak righty'nin solundaki herkesin yemek yiyebilme şansı oluşmuş olur. Yani kilitlenme yaşanmaz.
P bir lefty'dir ve öncelikle soldaki yemek çubuğunu almak zorundadır. Çünkü P'nin hiç yemek çubuğu yoktur, sol yemek çubuğu, sol komşusu tarafından, Q diyelim, tutulmaktadır. Filozof Q lefty ya da righty olabilir:
Bu program da bir önceki programa benzemektedir. Yine de, lefty ve righty filozoflarımız olduğu için her bir filozofun göstergesi olması gerekir. Programı basitleştirmek için yemek çubuklarını yerleştireceğimiz FirstChopstick ve SecondChopstick şeklinde iki değişken tanımladık. Tam olarak açıklamak gerekirse, her bir filozof FirstChopstick'i takiben SecondChopstick'e sahip olmalı. No adlı değişken filozofun numarasını simgeler ve karakter değişkeni Id filozofun righty mi yoksa lefty mi olduğunu belirtir.
#include <iostream.h>
#include "ThreadClass.h"
#define PHILOSOPHERS 5
class Philosopher: public Thread
{
public:
Philosopher(int Number, char id, int iter); // hazırlayıcı (constructor)
private:
char Id; // either "lefty" or "righty" philosopher
int No;
int FirstChopstick, // alınacak ilk yemek çubuğu
SecondChopstick; // alınacak ikinci yemek çubuğu
int Iteration;
void ThreadFunc();
};
|
| Dosyayı indirmek için buraya tıklayın (lefty-righty.h) |
Bahsedilen program hala aralıklardan oluşan bir katar (string) oluşturmaya yarayan Filler() fonksiyonuna sahiptir. Şimdi hazırlayıcıya (constructor) bakalım. No, Id ve Iteration adında üç private değişkeni argüman olarak kabul eder. Eğer filozofumuz bir lefty ise (referansa göre righty de olabilir) iş parçacığımız (thread) Lefty şeklinde adlandırılır (ya da Righty). Buna göre diğer iş parçacıkları Lefty1, Lefty2,..., Righty3, Righty4 şeklinde adlandırılır. İsimlendirme ana programa bağlıdır. Örneğin, eğer ana program filozof 0, 1, 2 ve 3'ü lefty oalrak atarsa ve 4'ü righty olarak, iş parçacıklarının adı Lefty1, Lefty2, Lefty3, Lefty4, Righty5 olarak adlandırılır. Hazırlayıcı ayrıca, bir filozofun ilk ve ikinci olarak alacağı yemek çubuklarına karar verir. Lefty bir filozof için, önce sol çubuk, takiben de sağ yemek çubuğu alınır. Böylece FirstChopstick ve SecondChopstick değişkenleri sırasıyla, No ve (No + 1) % PHILOSOPHERS değerlerine atanırlar. Righty bir filozof için sıra ters işler. İşlem bittiği zaman, ThreadFunc() fonksiyonu bir öncekiyle hemen hemen aynıdır. Tek fark FirstChopstick ve SecondChopstick'in kullanımlarıdır.
#include <iostream.h>
#include "ThreadClass.h"
#include "lefty-righty.h"
extern Mutex *Chopstick[PHILOSOPHERS];
strstream *Filler(int n)
{
int i;
strstream *Space;
Space = new strstream;
for (i = 0; i < n; i++)
(*Space) << ' ';
(*Space) << '\0';
return Space;
}
Philosopher::Philosopher(int Number, char id, int iter)
: No(Number), Id(id), Iteration(iter)
{
ThreadName.seekp(0, ios::beg);
if (Id == 'L') { // lefty'ler No'yu takiben (No+1)'i alırlar
ThreadName << "Lefty" << Number + 1 << '\0';
FirstChopstick = No;
SecondChopstick = (No + 1) % PHILOSOPHERS;
}
else { // righty'ler (No+1)'İ takiben No'yu alırlar
ThreadName << "Righty" << Number + 1 << '\0';
FirstChopstick = (No + 1) % PHILOSOPHERS;
SecondChopstick = No;
}
}
void Philosopher::ThreadFunc()
{
Thread::ThreadFunc();
strstream *Space;
int i;
Space = Filler(No*2);
for (i = 0; i < Iteration; i++) {
Delay();
Chopstick[FirstChopstick]->Lock();
Chopstick[SecondChopstick]->Lock(); // iki yemek çubuğunu da alırlar
cout << Space->str() << ThreadName.str() << " begin eating." << endl;
Delay();
cout << Space->str() << ThreadName.str() << " finish eating." << endl;
Chopstick[FirstChopstick]->Unlock(); // iki yemek çubuğunu da serbest bırakırlar
Chopstick[SecondChopstick]->Unlock();
}
Exit(); // thread terminates
}
|
| Dosyayı indirmek için buraya tıklatın (lefty-righty.cpp) |
Ana program iki adet komut satırı argümanına ihtiyaç duyar. İlki kaç tane lefty filozof olduğunu, ikincisi ise düşünme- yeme devirlerinin sayısını tutar. Sadece beş tane filozofumuz olduğuna dikkat edin, böylece kilitlenmeye yol açan dairesel beklemeyi kırmak için lefty filzooflarımızın sayısı beşten az olmalı ve en azından bir tane righty filozofumuz olmalı. Önceki örnekte olduğu gibi, bütün mutex kilitleri yemek çubuklarını kilitlemek için kullandık. Sonra filzooflarımız yaratıldı ve birkaç tanesi lefty oalrak atandı. Bir filozof yaratıldıktan sonra, Begin() adlı metod tarafında koşturulnaya başlar. En sonunda, ana program parçacığımız çoçuk iş parçacığının bitirilmesi için bekler ve çıkar.
#include <iostream.h>
#include "ThreadClass.h"
#include "lefty-righty.h"
Mutex *Chopstick[PHILOSOPHERS];
int main(int argc, char *argv[])
{
Philosopher *philosopher[PHILOSOPHERS];
int i;
int n;
strstream name;
if (argc != 3) {
cout << "Usage " << argv[0] << " #-of-lefty " <<
" #-of-iterations." << endl;
exit(-1);
}
else {
n = abs(atoi(argv[1]));
if (n >= PHILOSOPHERS) { // Lefty sayısının geçerli olduğunu kontrol eder
cout << "The number of lefty philosophers MUST be less than "
<< PHILOSOPHERS << endl;
exit(-1);
}
Iteration = abs(atoi(argv[2]));
}
// yemek çubuklarının mutex'lerini kontrol eder
for (i = 0; i < PHILOSOPHERS; i++) {
name.seekp(0, ios::beg);
name << "ChopStick" << i << '\0';
Chopstick[i] = new Mutex(name.str());
}
for (i = 0; i < PHILOSOPHERS; i++) {
if (i < n) // lefty filozof
philosopher[i] = new Philosopher(i, 'L', Iteration);
else // righty filozof
philosopher[i] = new Philosopher(i, 'R', Iteration);
philosopher[i]->Begin();
}
// bütün filzoof thread'larını bekler
for (i=0; i < PHILOSOPHERS; i++)
philosopher[i]->Join();
Exit();
}
|
| Dosyayı indirmek için buraya tıklayın (lefty-righty-main.cpp) |
Bu çözümün bir kilitlenmeye yol açmadığını gösterdik, ancak hala starvation problemine sebep olabilir. Önceki çözümde gördüğümüz starvation problemi bu çözüm için de geçerli olabilir.