Ēdināšanas filozofa problēma ir klasiskā sinhronizācijas problēma, kas saka, ka pieci filozofi sēž ap apaļu galdu un viņu uzdevums ir domāt un ēst alternatīvi. Bļoda ar nūdelēm ir novietota galda centrā kopā ar pieciem irbulīšiem katram filozofam. Lai paēstu filozofam, vajag gan labo, gan kreiso irbulīti. Filozofs var ēst tikai tad, ja ir pieejami gan tiešā filozofa kreisās, gan labās puses irbulīši. Gadījumā, ja filozofam nav pieejami gan tiešās kreisās, gan labās puses irbulīši, tad filozofs noliek savu (kreiso vai labo) irbulīti un atsāk domāt.
Ēdināšanas filozofs demonstrē lielu vienlaicības kontroles problēmu klasi, tāpēc tā ir klasiska sinhronizācijas problēma.
Pieci filozofi sēž ap galdu
Ēdināšanas filozofu problēma - Izpratīsim Dining Philosophers problēmu ar tālāk norādīto kodu. Mēs izmantojām 1. attēlu kā atsauci, lai jūs precīzi saprastu problēmu. Pieci filozofi ir attēloti kā P0, P1, P2, P3 un P4, un pieci irbulīši ar C0, C1, C2, C3 un 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 } } Apspriedīsim iepriekš minēto kodu:
Pieņemsim, ka filozofs P0 vēlas ēst, tas ievadīs Philosopher() funkciju un izpildīs take_chopsticck[i]; to darot, tas saglabājas C0 irbulīša pēc tam tas tiek izpildīts take_chopsticck[ (i+1) % 5]; to darot, tas saglabājas C1 irbulīša (tā kā i = 0, tāpēc (0 + 1) % 5 = 1)
Līdzīgi pieņemsim, ka tagad filozofs P1 vēlas ēst, tas ievadīs Philosopher() funkciju un izpildīs take_chopsticck[i]; to darot, tas saglabājas C1 irbulīša pēc tam tas tiek izpildīts take_chopsticck[ (i+1) % 5]; to darot, tas saglabājas C2 irbulīša (tā kā i = 1, tāpēc (1 + 1) % 5 = 2)
Bet praktiski Chopstick C1 nav pieejams, jo to jau ir izmantojis filozofs P0, tāpēc iepriekš minētais kods rada problēmas un rada sacensību apstākļus.
Ēdināšanas filozofu problēmas risinājums
Mēs izmantojam semaforu, lai attēlotu irbulīti, un tas patiešām darbojas kā ēdināšanas filozofu problēmas risinājums. Ēdināšanas filozofu problēmas risināšanai tiks izmantotas operācijas Wait and Signal, lai izvēlētos irbulīti, var izpildīt gaidīšanas operāciju, savukārt irbulīša atlaišanai var izpildīt semaforu.
Semafors: semafors ir vesels skaitļa mainīgais S, kuram bez inicializācijas var piekļūt tikai ar divām standarta atomu operācijām - gaidīšana un signāls, kuru definīcijas ir šādas:
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></=> Sākotnēji katrs semafora C0, C1, C2, C3 un C4 elements tiek inicializēts uz 1, jo irbulīši atrodas uz galda un neviens no filozofiem tos neuztvēra.
Modificēsim iepriekš minēto Ēdināšanas filozofa problēmas kodu, izmantojot semafora darbības gaidiet un signalizēsim, vēlamais kods izskatās šādi
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 } } Iepriekš minētajā kodā vispirms tiek veikta gaidīšanas darbība take_chopstickC[i] un take_chopstickC [ (i+1) % 5]. Tas parāda, ka filozofs es esmu paņēmis irbulīšus no kreisās un labās puses. Ēšanas funkcija tiek veikta pēc tam.
Pēc filozofa i the ēšanas pabeigšanas signāla darbība tiek veikta uz take_chopstickC[i] un take_chopstickC [ (i+1) % 5]. Tas liecina, ka filozofs esmu ēdis un nolicis gan kreiso, gan labo irbulīši. Beidzot filozofs atkal sāk domāt.
Sapratīsim, kā iepriekš minētais kods sniedz risinājumu ēdināšanas filozofa problēmai?
Pieņemsim, ka i vērtība ir 0 (sākotnējā vērtība), pieņemsim, ka filozofs P0 vēlas ēst, tas ievadīs Filozofs () funkcijā un izpildīs Pagaidiet( take_chopsticckC[i] ); to darot, tas saglabājas C0 irbulīša un samazina semaforu C0 līdz 0 , pēc tam tas tiek izpildīts Pagaidiet( take_chopsticckC[(i+1) % 5] ); to darot, tas saglabājas C1 irbulīša ( tā kā i = 0, tāpēc (0 + 1) % 5 = 1) un samazina semaforu C1 līdz 0
Līdzīgi, pieņemsim, ka tagad Filozofs P1 vēlas ēst, tas ievadīs Philosopher() funkciju un izpildīs Pagaidiet( take_chopsticckC[i] ); to darot, tas mēģinās noturēt C1 irbulīša bet to nevarēs izdarīt , tā kā semafora C1 vērtību jau filozofs P0 ir noteicis uz 0, tāpēc tas ieies bezgalīgā cilpā, kura dēļ filozofs P1 nevarēs izvēlēties irbulīti C1, savukārt, ja filozofs P2 gribēs ēst, tas ieies Filozofā () funkciju un izpildīt Pagaidiet( take_chopsticckC[i] ); to darot, tas saglabājas C2 irbulīša un samazina semaforu C2 līdz 0, pēc tam tas tiek izpildīts Pagaidiet( take_chopsticckC[(i+1) % 5] ); to darot, tas saglabājas C3 irbulīša ( tā kā i = 2, tāpēc (2 + 1) % 5 = 3) un samazina semaforu C3 līdz 0.
Tādējādi iepriekš minētais kods sniedz risinājumu ēdināšanas filozofa problēmai. Filozofs var ēst tikai tad, ja ir pieejami gan tiešā filozofa kreisā, gan labā irbulīši, pretējā gadījumā filozofam jāgaida. Arī vienā piegājienā divi neatkarīgi filozofi var ēst vienlaikus (t.i., filozofs P0 un P2, P1 un P3 un P2 un P4 var ēst vienlaicīgi, jo visi ir neatkarīgi procesi un tie ievēro iepriekš minēto ēdināšanas filozofa problēmas ierobežojumu)
Iepriekš minētā ēdināšanas filozofa problēmas risinājuma trūkums
No iepriekš minētā ēdināšanas filozofa problēmas risinājuma mēs esam pierādījuši, ka divi blakus esošie filozofi nevar ēst vienā un tajā pašā laikā. Iepriekš minētā risinājuma trūkums ir tāds, ka šis risinājums var izraisīt strupceļa stāvokli. Tāda situācija rodas, ja visi filozofi vienlaikus paņem kreiso irbulīti, kas noved pie strupceļa stāvokļa un neviens no filozofiem nevar paēst.
Lai izvairītos no strupceļa, daži no risinājumiem ir šādi:
- Maksimālais filozofu skaits uz galda nedrīkst būt lielāks par četriem, šajā gadījumā filozofam P3 būs pieejams irbulītis C4, tāpēc P3 sāks ēst un pēc ēšanas procedūras pabeigšanas noliks abus irbulīti C3. un C4, t.i., semafors C3 un C4 tagad tiks palielināts līdz 1. Tagad filozofam P2, kurš turēja irbulīti C2, būs pieejams arī irbulis C3, līdz ar to viņš pēc ēšanas noliks irbulīti un ļaus citiem filozofiem ēst.
- Filozofam, kurš atrodas pāra pozīcijā, ir jāizvēlas labais irbulis un tad kreisais irbulītis, savukārt filozofam nepāra pozīcijā jāizvēlas kreisais irbulis un tad labais irbulis.
- Tikai gadījumā, ja abi irbulīši (kreisais un labais) ir pieejami vienlaikus, tikai tad filozofam jāļauj izvēlēties savus irbulīšus
- Visiem četriem sākuma filozofiem (P0, P1, P2 un P3) ir jāizvēlas kreisais irbulītis un pēc tam labais irbulis, savukārt pēdējam filozofam P4 ir jāizvēlas labais irbulis un tad kreisais irbulītis. Tas liks P4 vispirms turēt labo irbulīti, jo P4 labā irbulīša ir C0, ko jau tur filozofs P0 un tā vērtība ir iestatīta uz 0, t.i., C0 jau ir 0, kā rezultātā P4 tiks iesprostots bezgalīgā. cilpa un irbulīša C4 paliek brīva. Līdz ar to filozofam P3 ir pieejams gan kreisais C3, gan labais C4 irbulītis, tāpēc tas sāks ēst un noliks abus irbulīšus, kad beigsies, un ļaus citiem ēst, kas novērš strupceļa problēmu.
Problēmas mērķis bija ilustrēt problēmas, kas saistītas ar izvairīšanos no strupceļa, sistēmas strupceļa stāvoklis ir stāvoklis, kurā nav iespējama sistēmas attīstība. Apsveriet priekšlikumu, kurā katram filozofam ir uzdots rīkoties šādi:
- Filozofam tiek uzdots domāt, līdz ir pieejama kreisā dakša, kad tā ir pieejama, turiet to.
- Filozofam tiek uzdots domāt, līdz ir pieejama īstā dakša, kad tā ir pieejama, turiet to.
- Filozofam ir dots norādījums ēst, kad ir pieejamas abas dakšiņas.
- pēc tam vispirms nolieciet labo dakšiņu
- pēc tam nolieciet kreiso dakšiņu
- atkārtojiet no sākuma.