Проблемът на трапезния философ е класическият проблем на синхронизацията, който казва, че петима философи седят около кръгла маса и тяхната работа е да мислят и да ядат алтернативно. Купа с юфка се поставя в центъра на масата заедно с пет клечки за всеки от философите. За да яде един философ се нуждае както от дясната, така и от лявата клечка. Философът може да яде само ако са налични и лявата, и дясната клечка за хранене на философа. В случай, че и лявата, и дясната пръчица на философа не са налични, тогава философът оставя своята (лява или дясна) пръчица и започва да мисли отново.
Философът за хранене демонстрира голям клас проблеми с контрола на паралелността, следователно това е класически проблем за синхронизация.
Петима философи, седнали около масата
Проблем с философите за хранене - Нека разберем проблема с философите за хранене с кода по-долу, използвахме фигура 1 като справка, за да ви накараме да разберете проблема точно. Петимата философи са представени като P0, P1, P2, P3 и P4, а петте пръчици са представени като C0, C1, C2, C3 и C4.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Нека обсъдим горния код:
Да предположим, че Philosopher P0 иска да яде, той ще влезе във функцията Philosopher() и ще изпълни take_chopstick[i]; като прави това, то се задържа C0 клечка за хранене след това се изпълнява take_chopstick [ (i+1) % 5]; като прави това, то се задържа C1 клечка за хранене (тъй като i =0, следователно (0 + 1) % 5 = 1)
По същия начин да предположим, че сега Philosopher P1 иска да яде, той ще влезе във функцията Philosopher() и ще изпълни take_chopstick[i]; като прави това, то се задържа C1 клечка за хранене след това се изпълнява take_chopstick [ (i+1) % 5]; като прави това, то се задържа C2 клечка за хранене (тъй като i =1, следователно (1 + 1) % 5 = 2)
програма за прости числа в java
Но Практически Chopstick C1 не е наличен, тъй като вече е бил взет от философа P0, следователно горният код генерира проблеми и създава състояние на състезание.
Решението на проблема с философите за хранене
Ние използваме семафор, за да представим клечка за хранене и това наистина действа като решение на проблема с философите за хранене. Операциите Wait и Signal ще бъдат използвани за решаването на проблема Dining Philosophers, за избиране на пръчица може да се изпълни операция изчакване, докато за пускане на пръчица може да се изпълни сигнален семафор.
Семафор: Семафорът е целочислена променлива в S, която освен инициализацията е достъпна само от две стандартни атомарни операции - чакане и сигнал, чиито дефиниции са както следва:
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></=> Първоначално всеки елемент от семафора C0, C1, C2, C3 и C4 се инициализира на 1, тъй като клечките са на масата и не се вдигат от никой от философите.
Нека модифицираме горния код на проблема Dining Philosopher чрез използване на семафорни операции чакане и сигнал, желаният код изглежда така
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 } } В горния код първата операция за изчакване се извършва на take_chopstickC[i] и take_chopstickC [ (i+1) % 5]. Това показва, че философ съм вдигнал клечките отляво и отдясно. След това се изпълнява хранителната функция.
При завършване на храненето от философа i the, сигналната операция се извършва върху take_chopstickC[i] и take_chopstickC [ (i+1) % 5]. Това показва, че философът, който съм ял и съм оставил лявата и дясната пръчица. Накрая философът започва да мисли отново.
Нека разберем как горният код дава решение на проблема с философа за хранене?
Нека стойността на i = 0 (начална стойност), Да предположим, че Philosopher P0 иска да яде, той ще влезе във функцията Philosopher() и ще изпълни Изчакайте( take_chopstickC[i]); като прави това, то се задържа C0 клечка за хранене и намалява семафор C0 до 0 , след това се изпълнява Изчакайте( take_chopstickC[(i+1) % 5]); като прави това, то се задържа C1 клечка за хранене ( тъй като i =0, следователно (0 + 1) % 5 = 1) и редуцира семафор C1 до 0
По същия начин, да предположим, че сега Philosopher P1 иска да яде, той ще влезе във функцията Philosopher() и ще изпълни Изчакайте( take_chopstickC[i]); като прави това, то ще се опита да задържи C1 клечка за хранене но няма да може да направи това , тъй като стойността на семафора C1 вече е зададена на 0 от философа P0, следователно той ще влезе в безкраен цикъл, поради което философът P1 няма да може да вземе клечка C1, докато ако философът P2 иска да яде, той ще влезе във философа () функция и изпълнение Изчакайте( take_chopstickC[i]); като прави това, то се задържа C2 клечка за хранене и намалява семафор C2 до 0, след което се изпълнява Изчакайте( take_chopstickC[(i+1) % 5]); като прави това, то се задържа C3 клечка за хранене (тъй като i =2, следователно (2 + 1) % 5 = 3) и редуцира семафор C3 до 0.
sonu nigam
Следователно горният код предоставя решение на проблема с философа за хранене. Философът може да яде само ако са налични незабавно лявата и дясната клечка за хранене на философа, в противен случай философът трябва да изчака. Също така наведнъж двама независими философи могат да ядат едновременно (т.е. философ P0 и P2, P1 и P3 & P2 и P4 могат да се хранят едновременно, тъй като всички са независими процеси и те следват горното ограничение на проблема с философа за хранене)
Недостатъкът на горното решение на проблема с философа за хранене
От горното решение на проблема с трапезарния философ доказахме, че двама съседни философи не могат да ядат по едно и също време. Недостатъкът на горното решение е, че това решение може да доведе до състояние на блокиране. Тази ситуация се случва, ако всички философи вдигнат лявата си пръчица едновременно, което води до състояние на безизходица и никой от философите не може да яде.
За да избегнете задънена улица, някои от решенията са както следва -
- Максималният брой философи на масата не трябва да бъде повече от четирима, в този случай пръчицата C4 ще бъде достъпна за философ P3, така че P3 ще започне да яде и след края на процедурата си по хранене той ще остави двете си пръчици C3 и C4, т.е. семафорът C3 и C4 сега ще бъдат увеличени до 1. Сега философът P2, който държеше пръчица C2, също ще има налична пръчица C3, следователно по подобен начин той ще остави своята пръчица след хранене и ще даде възможност на други философи да ядат.
- Философ в четна позиция трябва да вземе дясната клечка и след това лявата клечка, докато философ в нечетна позиция трябва да вземе лявата клечка и след това дясната клечка.
- Само в случай, че и двете пръчици (лява и дясна) са налични едновременно, само тогава на философ трябва да бъде позволено да вземе своите пръчици
- Всички четирима начални философи (P0, P1, P2 и P3) трябва да изберат лявата клечка и след това дясната клечка, докато последният философ P4 трябва да вземе дясната клечка и след това лявата клечка. Това ще принуди P4 да държи дясната си пръчица първо, тъй като дясната пръчица на P4 е C0, която вече се държи от философа P0 и нейната стойност е зададена на 0, т.е. C0 вече е 0, поради което P4 ще бъде хванат в безкраен примка и клечка C4 остават празни. Следователно философът P3 има на разположение както лявата C3, така и дясната C4 пръчица, следователно ще започне да яде и ще остави двете си пръчици, след като приключи, и ще остави другите да ядат, което премахва проблема с безизходицата.
Дизайнът на проблема беше да илюстрира предизвикателствата при избягване на безизходица, безизходно състояние на система е състояние, в което не е възможен прогрес на системата. Помислете за предложение, при което всеки философ е инструктиран да се държи, както следва:
- Философът е инструктиран да мисли, докато лявата вилка стане достъпна, когато е достъпна, задръжте я.
- Философът е инструктиран да мисли, докато дясната вилица е достъпна, когато е налична, задръжте я.
- Философът е инструктиран да яде, когато и двете вилици са налични.
- след това поставете първо дясната вилица
- след това поставете лявата вилица надолу
- повторете отначало.