Yemek filozofunun problemi, Beş filozofun dairesel bir masa etrafında oturduğunu ve görevlerinin alternatif olarak düşünmek ve yemek yemek olduğunu söyleyen klasik senkronizasyon problemidir. Masanın ortasına bir kase erişte ve her filozof için beş yemek çubuğu yerleştirilir. Bir filozofun yemek yemesi için hem sağ hem de sol yemek çubuğuna ihtiyacı vardır. Bir filozof ancak filozofun hem sol hem de sağ yemek çubukları mevcutsa yemek yiyebilir. Filozofun hem sol hem de sağ çubuklarının mevcut olmaması durumunda, filozof (sol veya sağ) çubuklarını bırakır ve yeniden düşünmeye başlar.
Yemek filozofu, eşzamanlılık kontrol problemlerinin geniş bir sınıfını göstermektedir, dolayısıyla bu klasik bir senkronizasyon problemidir.
java dizisini dilimle
Beş Filozof masanın etrafında oturuyor
Yemek Filozoflarının Sorunu - Aşağıdaki kod ile Yemek Filozofları Problemini anlayalım, problemi tam olarak anlamanızı sağlamak için şekil 1'i referans olarak kullandık. Beş Filozof P0, P1, P2, P3 ve P4 olarak temsil edilirken beş yemek çubuğu da C0, C1, C2, C3 ve C4 ile temsil edilir.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Yukarıdaki kodu tartışalım:
Filozof P0'ın yemek istediğini varsayalım, Philosopher() fonksiyonuna girecek ve çalıştıracaktır. take_chopstick[i]; bunu yaparak tutar C0 yemek çubuğu bundan sonra yürütülür take_chopstick[ (i+1) % 5]; bunu yaparak tutar C1 yemek çubuğu ( i =0 olduğundan (0 + 1) % 5 = 1)
Benzer şekilde, şimdi Filozof P1'in yemek istediğini, Philosopher() fonksiyonuna gireceğini ve çalıştıracağını varsayalım. take_chopstick[i]; bunu yaparak tutar C1 yemek çubuğu bundan sonra yürütülür take_chopstick[ (i+1) % 5]; bunu yaparak tutar C2 yemek çubuğu ( i =1 olduğundan (1 + 1) % 5 = 2)
Ancak Practical Chopstick C1, filozof P0 tarafından zaten alınmış olduğundan mevcut değildir, dolayısıyla yukarıdaki kod sorunlar yaratır ve yarış durumu üretir.
Yemek Felsefecileri Sorununun Çözümü
Yemek çubuğunu temsil etmek için semafor kullanıyoruz ve bu gerçekten de Yemek Felsefecileri Problemine bir çözüm görevi görüyor. Yemek Filozofları Probleminin çözümü için Bekleme ve Sinyal işlemleri kullanılacak olup, yemek çubuğu seçmek için bekleme işlemi, yemek çubuğu sinyalini bırakmak için semafor çalıştırılabilir.
Semafor: Bir semafor, S'deki bir tam sayı değişkenidir ve başlatma dışında yalnızca iki standart atomik işlemle (bekleme ve sinyal) erişilir; tanımları aşağıdaki gibidir:
1. wait( S ) { while( S <= 0) ; s--; } 2. signal( s ) { s++; < pre> <p>From the above definitions of wait, it is clear that if the value of S <= 0 then it will enter into an infinite loop(because of the semicolon; after while loop). whereas job signal is to increment value s.< p> <p>The structure of the chopstick is an array of a semaphore which is represented as shown below -</p> <pre> semaphore C[5]; </pre> <p>Initially, each element of the semaphore C0, C1, C2, C3, and C4 are initialized to 1 as the chopsticks are on the table and not picked up by any of the philosophers.</p> <p>Let's modify the above code of the Dining Philosopher Problem by using semaphore operations wait and signal, the desired code looks like</p> <pre> void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } </pre> <p>In the above code, first wait operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows philosopher i have picked up the chopsticks from its left and right. The eating function is performed after that.</p> <p>On completion of eating by philosopher i the, signal operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows that the philosopher i have eaten and put down both the left and right chopsticks. Finally, the philosopher starts thinking again.</p> <h3>Let's understand how the above code is giving a solution to the dining philosopher problem?</h3> <p>Let value of i = 0( initial value ), Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C0 chopstick</strong> and reduces semaphore C0 to 0 <strong>,</strong> after that it execute <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C1 chopstick</strong> ( since i =0, therefore (0 + 1) % 5 = 1) and reduces semaphore C1 to 0</p> <p>Similarly, suppose now Philosopher P1 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it will try to hold <strong>C1 chopstick</strong> but will not be able to do that <strong>,</strong> since the value of semaphore C1 has already been set to 0 by philosopher P0, therefore it will enter into an infinite loop because of which philosopher P1 will not be able to pick chopstick C1 whereas if Philosopher P2 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C2 chopstick</strong> and reduces semaphore C2 to 0, after that, it executes <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C3 chopstick</strong> ( since i =2, therefore (2 + 1) % 5 = 3) and reduces semaphore C3 to 0.</p> <p>Hence the above code is providing a solution to the dining philosopher problem, A philosopher can only eat if both immediate left and right chopsticks of the philosopher are available else philosopher needs to wait. Also at one go two independent philosophers can eat simultaneously (i.e., philosopher <strong>P0 and P2, P1 and P3 & P2 and P4</strong> can eat simultaneously as all are the independent processes and they are following the above constraint of dining philosopher problem)</p> <h3>The drawback of the above solution of the dining philosopher problem</h3> <p>From the above solution of the dining philosopher problem, we have proved that no two neighboring philosophers can eat at the same point in time. The drawback of the above solution is that this solution can lead to a deadlock condition. This situation happens if all the philosophers pick their left chopstick at the same time, which leads to the condition of deadlock and none of the philosophers can eat.</p> <p>To avoid deadlock, some of the solutions are as follows -</p> <ul> <li>Maximum number of philosophers on the table should not be more than four, in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and after the finish of his eating procedure, he will put down his both the chopstick C3 and C4, i.e. semaphore C3 and C4 will now be incremented to 1. Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available, hence similarly, he will put down his chopstick after eating and enable other philosophers to eat.</li> <li>A philosopher at an even position should pick the right chopstick and then the left chopstick while a philosopher at an odd position should pick the left chopstick and then the right chopstick.</li> <li>Only in case if both the chopsticks ( left and right ) are available at the same time, only then a philosopher should be allowed to pick their chopsticks</li> <li>All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the left chopstick. This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start eating and will put down its both chopsticks once finishes and let others eat which removes the problem of deadlock.</li> </ul> <p>The design of the problem was to illustrate the challenges of avoiding deadlock, a deadlock state of a system is a state in which no progress of system is possible. Consider a proposal where each philosopher is instructed to behave as follows:</p> <ul> <li>The philosopher is instructed to think till the left fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to think till the right fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to eat when both forks are available.</li> <li>then, put the right fork down first</li> <li>then, put the left fork down next</li> <li>repeat from the beginning.</li> </ul> <hr></=></p></=> Başlangıçta, C0, C1, C2, C3 ve C4 semaforunun her bir elemanı, yemek çubukları masanın üzerinde olduğundan ve filozofların hiçbiri tarafından alınmadığından 1 olarak başlatılır.
rr algoritması
Yemek Felsefesi Probleminin yukarıdaki kodunu semafor işlemlerini wait ve signal kullanarak değiştirelim, istenen kod şuna benzer:
void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } Yukarıdaki kodda take_chopstickC[i] ve take_chopstickC [ (i+1) % 5] üzerinde ilk bekleme işlemi yapılıyor. Bu, filozofa yemek çubuklarını sağından ve solundan aldığımı gösteriyor. Bundan sonra yeme fonksiyonu gerçekleştirilir.
Filozof i the tarafından yeme işlemi tamamlandıktan sonra take_chopstickC[i] ve take_chopstickC [ (i+1) % 5] üzerinde sinyal işlemi gerçekleştirilir. Bu, filozofun hem sol hem de sağ yemek çubuklarını yediğimi ve bıraktığımı gösteriyor. Sonunda filozof yeniden düşünmeye başlar.
Yukarıdaki kodun yemek felsefesi problemine nasıl bir çözüm getirdiğini anlayalım mı?
i = 0 (başlangıç değeri) değeri olsun, Farz edelim ki Filozof P0 yemek yemek istiyor, Philosopher() fonksiyonuna girecek ve çalıştıracak Bekle( take_chopstickC[i] ); bunu yaparak tutar C0 yemek çubuğu ve semafor C0'ı 0'a düşürür , bundan sonra yürütülür Bekle( take_chopstickC[(i+1) % 5] ); bunu yaparak tutar C1 yemek çubuğu ( i =0 olduğundan (0 + 1) % 5 = 1) ve C1 semaforunu 0'a düşürür
Benzer şekilde, şimdi Filozof P1'in yemek istediğini, Philosopher() fonksiyonuna gireceğini ve çalıştıracağını varsayalım. Bekle( take_chopstickC[i] ); bunu yaparak tutmaya çalışacak C1 yemek çubuğu ama bunu yapamayacağım , Semafor C1'in değeri filozof P0 tarafından zaten 0'a ayarlandığından sonsuz bir döngüye girecek, bu nedenle filozof P1 yemek çubuğunu C1 seçemeyecek, oysa Filozof P2 yemek isterse Filozof P2'ye girecek () işlevini kullanın ve çalıştırın Bekle( take_chopstickC[i] ); bunu yaparak tutar C2 yemek çubuğu ve semafor C2'yi 0'a düşürür, bundan sonra çalıştırır Bekle( take_chopstickC[(i+1) % 5] ); bunu yaparak tutar C3 yemek çubuğu ( i =2 olduğundan (2 + 1) % 5 = 3) ve C3 semaforunu 0'a düşürür.
Dolayısıyla yukarıdaki kod, yemek felsefecisi sorununa bir çözüm sunmaktadır. Bir filozof, yalnızca filozofun hem sol hem de sağ yemek çubukları mevcutsa yemek yiyebilir, aksi takdirde filozofun beklemesi gerekir. Ayrıca iki bağımsız filozof tek seferde aynı anda yemek yiyebilir (örn. P0 ve P2, P1 ve P3 ve P2 ve P4 hepsi bağımsız süreçler olduğundan ve yukarıdaki yemek felsefesi probleminin kısıtlamasını takip ettiğinden aynı anda yemek yiyebilirler)
Yemek felsefesi probleminin yukarıdaki çözümünün dezavantajı
Yemek felsefecisi sorununun yukarıdaki çözümünden, iki komşu filozofun aynı anda yemek yiyemeyeceğini kanıtladık. Yukarıdaki çözümün dezavantajı, bu çözümün kilitlenme durumuna yol açabilmesidir. Bu durum, tüm filozofların aynı anda sol çubuklarını çekmeleri durumunda ortaya çıkar, bu da çıkmaza yol açar ve hiçbir filozof yemek yiyemez.
Kilitlenmeyi önlemek için çözümlerden bazıları şunlardır:
- Masadaki maksimum filozof sayısı dörtten fazla olmamalıdır, bu durumda filozof P3 için C4 yemek çubuğu bulunacaktır, yani P3 yemeğe başlayacak ve yeme işlemi bittikten sonra hem C3 yemek çubuğunu bırakacaktır. ve C4 yani semafor C3 ve C4 artık 1'e artırılacak. Artık C2 yemek çubuğunu tutan filozof P2'nin elinde de C3 yemek çubuğu olacak, dolayısıyla benzer şekilde yemek yedikten sonra yemek çubuğunu bırakacak ve diğer filozofların yemek yemesini sağlayacak.
- Eşit konumdaki bir filozof önce sağ çubuğu, sonra da sol çubuğu seçmelidir; tek konumdaki bir filozof ise önce sol çubuğu, sonra da sağ çubuğu seçmelidir.
- Ancak her iki yemek çubuğunun (sol ve sağ) aynı anda mevcut olması durumunda, ancak o zaman bir filozofun yemek çubuklarını seçmesine izin verilmelidir.
- Başlangıçtaki dört filozofun tümü (P0, P1, P2 ve P3) sol yemek çubuğunu ve ardından sağ yemek çubuğunu seçmeli, son filozof P4 ise sağ yemek çubuğunu ve ardından sol yemek çubuğunu seçmelidir. P4'ün sağ çubuğu zaten filozof P0 tarafından tutulan ve değeri 0'a ayarlı olan C0 olduğu için bu, P4'ü önce sağ yemek çubuğunu tutmaya zorlayacaktır, yani C0 zaten 0'dır, çünkü P4 sonsuz bir tuzağa düşecektir. döngü ve çubuk C4 boş kalır. Bu nedenle, filozof P3'ün hem sol C3 hem de sağ C4 çubukları vardır, bu nedenle yemeye başlayacak ve bittiğinde her iki çubuklarını da bırakacak ve diğerlerinin yemesine izin verecek, bu da kilitlenme sorununu ortadan kaldıracaktır.
Sorunun tasarımı, kilitlenmeden kaçınmanın zorluklarını göstermekti; bir sistemin kilitlenme durumu, sistemin ilerlemesinin mümkün olmadığı bir durumdur. Her filozofa aşağıdaki gibi davranmasının söylendiği bir öneri düşünün:
- Felsefeciye, sol çatal mevcut olana kadar düşünmesi, mevcut olduğunda onu tutması talimatı verilir.
- Felsefeciye doğru çatal bulununcaya kadar düşünmesi ve bu çatal mevcut olduğunda onu tutması talimatı verilir.
- Felsefeciye her iki çatal da mevcut olduğunda yemek yemesi talimatı verilir.
- sonra ilk önce sağ çatalı indirin
- sonra sol çatalı aşağıya indirin
- baştan tekrarlayın.