Проблема обідаючого філософа — це класична проблема синхронізації, яка говорить, що п’ятеро філософів сидять за круглим столом, і їхня робота — поперемінно думати та їсти. Миску з локшиною ставлять у центрі столу разом із п’ятьма паличками для кожного з філософів. Щоб їсти, філософу потрібні як права, так і ліва палички. Філософ може їсти, лише якщо є ліворуч і праворуч палички для їжі філософа. У випадку, якщо обидві ліві та праві палички для їжі філософа недоступні, тоді філософ відкладає свою (ліву чи праву) палички та починає думати знову.
Філософ обіду демонструє великий клас проблем керування паралелізмом, отже, це класична проблема синхронізації.
П'ять філософів сидять за столом
Обідна проблема філософів - Давайте розберемося з проблемою Dining Philosophers за допомогою наведеного нижче коду, ми використали малюнок 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]; роблячи це, воно тримається С1 паличка для їжі ( оскільки 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
Але Practically Chopstick C1 недоступний, оскільки він уже був використаний філософом P0, отже, наведений вище код створює проблеми та створює умови змагання.
Рішення проблеми філософів обіду
Ми використовуємо семафор, щоб представити паличку для їжі, і це справді діє як рішення проблеми філософів обіду. Операції «Очікування» та «Сигнал» використовуватимуться для розв’язання проблеми «Філософи обіду», для вибору палички для їжі можна виконати операцію очікування, а для відпускання палички для їжі можна виконати семафор сигналу.
Семафор: семафор є цілочисельною змінною в 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 їв і відклав і ліву, і праву палички. Нарешті філософ починає думати знову.
Давайте зрозуміємо, як наведений вище код вирішує проблему обіднього філософа?
Нехай значення i = 0 (початкове значення), припустимо, що Philosopher P0 хоче їсти, він увійде у функцію Philosopher() і виконає Зачекайте( take_chopstickC[i]); роблячи це, воно тримається C0 паличка для їжі і зменшує семафор C0 до 0 , після цього його виконати Зачекайте( take_chopstickC[(i+1) % 5] ); роблячи це, воно тримається С1 паличка для їжі ( оскільки i =0, тому (0 + 1) % 5 = 1) і зводить семафор C1 до 0
Аналогічно, припустімо, що зараз Philosopher P1 хоче їсти, він увійде у функцію Philosopher() і виконає Зачекайте( take_chopstickC[i]); роблячи це, він намагатиметься утриматися С1 паличка для їжі але не зможе цього зробити , оскільки значення семафора C1 вже було встановлено на 0 філософом P0, тому він увійде в нескінченний цикл, через який філософ P1 не зможе взяти паличку C1, тоді як, якщо філософ P2 захоче їсти, він увійде в Philosopher () функцію та виконайте Зачекайте( take_chopstickC[i]); роблячи це, воно тримається C2 паличка для їжі і зменшує семафор C2 до 0, після чого він виконується Зачекайте( take_chopstickC[(i+1) % 5] ); роблячи це, воно тримається C3 паличка для їжі ( оскільки i =2, отже (2 + 1) % 5 = 3) і зводить семафор C3 до 0.
амплітудна модуляція
Таким чином, наведений вище код забезпечує вирішення проблеми обіднього філософа. Філософ може їсти, лише якщо доступні обидві ліві та праві палички для їжі філософа, інакше філософу потрібно почекати. Крім того, одночасно два незалежні філософи можуть їсти одночасно (тобто філософ 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 палички, тому він почне їсти і відкладе обидві палички, коли закінчить, і дозволить іншим їсти, що усуває проблему тупика.
Розробка проблеми полягала в тому, щоб проілюструвати труднощі уникнення тупикової ситуації. Тупиковий стан системи — це стан, у якому прогрес системи неможливий. Розглянемо пропозицію, згідно з якою кожному філософу наказано поводитися наступним чином:
- Філософу наказано думати, поки ліва вилка не буде доступна, коли вона доступна, тримайте її.
- Філософу наказано думати, поки не буде доступна права вилка, коли вона доступна, тримайте її.
- Філософу наказано їсти, коли доступні обидві виделки.
- потім спочатку покладіть праву вилку
- потім опустіть ліву вилку
- повторити з початку.