Проблем филозофа у трпезарији је класични проблем синхронизације који каже да пет филозофа седе око кружног стола и њихов посао је да размишљају и једу алтернативно. Здела резанаца је постављена на средину стола заједно са пет штапића за сваког од филозофа. Да би јео филозоф треба и десни и леви штапић за јело. Филозоф може да једе само ако су му доступни и леви и десни штапићи за јело. У случају да и леви и десни штапић за јело филозофа нису доступни, филозоф спушта (било леви или десни) штапић за јело и поново почиње да размишља.
Филозоф у трпезарији демонстрира велику класу проблема контроле истовремености, па је то класичан проблем синхронизације.
Пет филозофа седе око стола
Дининг Пхилосопхерс Проблем - Хајде да разумемо проблем филозофа у ресторану са кодом у наставку, користили смо слику 1 као референцу да бисмо тачно разумели проблем. Пет филозофа су представљени као П0, П1, П2, П3 и П4, а пет штапића за јело са Ц0, Ц1, Ц2, Ц3 и Ц4.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Хајде да разговарамо о горњем коду:
Претпоставимо да Пхилосопхер П0 жели да једе, ући ће у функцију Пхилосопхер() и извршити таке_цхопстицк[и]; чинећи ово држи Ц0 штапић за јело након тога се извршава таке_цхопстицк[ (и+1) % 5]; чинећи ово држи Ц1 штапић за јело (пошто је и =0, дакле (0 + 1) % 5 = 1)
Слично, претпоставимо да сада Пхилосопхер П1 жели да једе, ући ће у функцију Пхилосопхер() и извршити таке_цхопстицк[и]; чинећи ово држи Ц1 штапић за јело након тога се извршава таке_цхопстицк[ (и+1) % 5]; чинећи ово држи Ц2 штапић за јело (пошто је и =1, дакле (1 + 1) % 5 = 2)
Али практично штапић Ц1 није доступан јер га је већ узео филозоф П0, стога горњи код генерише проблеме и производи услове за трку.
Решење проблема филозофа у ресторану
Користимо семафор да представимо штапић за јело и ово заиста делује као решење проблема филозофа у ресторану. Операције чекања и сигнала ће се користити за решење проблема филозофа у ресторану, за бирање штапића може се извршити операција чекања, док се за отпуштање сигналног штапића може извршити семафор.
Семафор: Семафор је целобројна променљива у С, којој осим иницијализације приступају само две стандардне атомске операције - чекање и сигнал, чије су дефиниције следеће:
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></=> У почетку, сваки елемент семафора Ц0, Ц1, Ц2, Ц3 и Ц4 је иницијализован на 1 пошто су штапићи на столу и није их покупио ниједан филозоф.
Хајде да изменимо горњи код Проблема филозофа у ресторану коришћењем семафорских операција чекања и сигнала, жељени код изгледа као
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 } } У горњем коду, прва операција чекања се изводи на таке_цхопстицкЦ[и] и таке_цхопстицкЦ [ (и+1) % 5]. Ово показује филозофу да сам покупио штапиће са леве и десне стране. Функција исхране се врши након тога.
По завршетку једења од стране филозофа и, операција сигнала се изводи на таке_цхопстицкЦ[и] и таке_цхопстицкЦ [ (и+1) % 5]. Ово показује да сам филозоф којег сам појео и спустио и леви и десни штапић за јело. Најзад, филозоф поново почиње да размишља.
Хајде да разумемо како горњи код даје решење за проблем филозофа у ресторану?
Нека је вредност и = 0 (почетна вредност), претпоставимо да филозоф П0 жели да једе, ући ће у функцију Пхилосопхер() и извршити Сачекајте( таке_цхопстицкЦ[и] ); чинећи ово држи Ц0 штапић за јело и смањује семафор Ц0 на 0 , након тога се извршава Сачекајте( таке_цхопстицкЦ[(и+1) % 5] ); чинећи ово држи Ц1 штапић за јело ( пошто је и =0, дакле (0 + 1) % 5 = 1) и смањује семафор Ц1 на 0
Слично томе, претпоставимо да сада Пхилосопхер П1 жели да једе, ући ће у функцију Пхилосопхер() и извршити Сачекајте( таке_цхопстицкЦ[и] ); чинећи ово покушаће да задржи Ц1 штапић за јело али то неће моћи , пошто је вредност семафора Ц1 већ подесио на 0 од стране филозофа П0, он ће ући у бесконачну петљу због чега филозоф П1 неће моћи да убере штапић Ц1, док ако филозоф П2 жели да једе, он ће ући у пхилосопхер () функција и извршавање Сачекајте( таке_цхопстицкЦ[и] ); чинећи ово држи Ц2 штапић за јело и смањује семафор Ц2 на 0, након тога се извршава Сачекајте( таке_цхопстицкЦ[(и+1) % 5] ); чинећи ово држи Ц3 штапић за јело ( пошто је и =2, дакле (2 + 1) % 5 = 3) и смањује семафор Ц3 на 0.
Стога горњи код пружа решење за проблем филозофа у ресторану, филозоф може да једе само ако су му доступни и леви и десни штапићи за јело, иначе филозоф мора да сачека. Такође у једном тренутку два независна филозофа могу да једу истовремено (тј. филозоф П0 и П2, П1 и П3 и П2 и П4 могу да једу истовремено јер су сви независни процеси и прате горе наведено ограничење проблема филозофа у ресторану)
Недостатак горњег решења проблема филозофа трпезарије
Из горњег решења проблема филозофа у ресторану, доказали смо да два суседна филозофа не могу да једу у истом тренутку. Недостатак горњег решења је у томе што ово решење може довести до стања застоја. Ова ситуација се дешава ако сви филозофи у исто време бирају свој леви штап, што доводи до стања ћорсокака и нико од филозофа не може да једе.
Да бисте избегли застој, нека од решења су следећа -
- Максималан број филозофа на столу не би требало да буде већи од четири, у овом случају ће филозофу П3 бити на располагању штап Ц4, тако да ће П3 почети да једе и након завршетка своје процедуре јела, он ће спустити своја оба штапића Ц3. и Ц4, тј. семафори Ц3 и Ц4 ће сада бити повећани на 1. Сада ће филозоф П2 који је држао штапић Ц2 такође имати на располагању штапић Ц3, па ће на сличан начин он спустити свој штап након јела и омогућити другим филозофима да једу.
- Филозоф на парној позицији треба да изабере десни штап, а затим леви штап, док филозоф на непарном положају треба да изабере леви штап, а затим десни штап.
- Само у случају да су оба штапића (леви и десни) доступна у исто време, само тада филозофу треба дозволити да бере штапиће за јело
- Сва четири почетна филозофа (П0, П1, П2 и П3) треба да изаберу леви штап, а затим десни штап, док последњи филозоф П4 треба да одабере десни штап, а затим леви штап. Ово ће приморати П4 да прво држи свој десни штап јер је десни штап од П4 Ц0, који већ држи филозоф П0 и његова вредност је постављена на 0, тј. Ц0 је већ 0, због чега ће П4 бити заробљен у бесконачно петља и штап Ц4 остају празни. Стога филозоф П3 има на располагању и леви Ц3 и десни Ц4 штапић, стога ће почети да једе и одложиће оба штапића када заврши и пустити другима да једу што отклања проблем застоја.
Дизајн проблема је био да илуструје изазове избегавања застоја, стање застоја система је стање у којем напредак система није могућ. Размотрите предлог у коме је сваком филозофу наложено да се понаша на следећи начин:
- Филозоф је упућен да размишља док лева виљушка не буде доступна, када је доступна, држите је.
- Филозоф је упућен да размишља док десна виљушка не буде доступна, када је доступна, држите је.
- Филозоф је упућен да једе када су обе виљушке доступне.
- затим прво спустите десну виљушку
- затим спустите леву виљушку
- понови од почетка.