Problema filozofului de mese este problema clasică a sincronizării, care spune că Cinci filosofi stau în jurul unei mese circulare și treaba lor este să gândească și să mănânce alternativ. Un castron de tăiței este plasat în centrul mesei împreună cu cinci betisoare pentru fiecare dintre filozofi. Pentru a mânca un filozof are nevoie atât de bețișorul drept, cât și de cel stâng. Un filozof poate mânca numai dacă sunt disponibile atât bețișoarele imediat stânga, cât și cele din dreapta ale filosofului. În cazul în care nu sunt disponibile atât bețișoarele imediat stânga cât și cele din dreapta ale filosofului, atunci filosoful își lasă jos betisoarele (fie din stânga, fie din dreapta) și începe să se gândească din nou.
Filosoful mesei demonstrează o clasă mare de probleme de control al concurenței, de aceea este o problemă clasică de sincronizare.
Cinci filozofi stând în jurul mesei
Problema filozofilor dining - Să înțelegem problema Dining Philosophers cu codul de mai jos, am folosit fig. 1 ca referință pentru a vă face să înțelegeți problema exact. Cei cinci filozofi sunt reprezentați ca P0, P1, P2, P3 și P4 și cinci betisoare prin C0, C1, C2, C3 și 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 } } Să discutăm despre codul de mai sus:
Să presupunem că Philosopher P0 vrea să mănânce, va intra în funcția Philosopher() și va executa luați_bețișon[i]; făcând asta ține betisoare C0 dupa aceea se executa luați_bețișon[ (i+1) % 5]; făcând asta ține betisoare C1 (de vreme ce i =0, prin urmare (0 + 1) % 5 = 1)
În mod similar, să presupunem că acum Philosopher P1 vrea să mănânce, va intra în funcția Philosopher() și va executa lua_bețișon[i]; făcând asta ține betisoare C1 dupa aceea se executa luați_bețișon[ (i+1) % 5]; făcând asta ține betisoare C2 (de vreme ce i =1, prin urmare (1 + 1) % 5 = 2)
Dar Practic Chopstick C1 nu este disponibil deoarece a fost deja preluat de filozoful P0, prin urmare codul de mai sus generează probleme și produce condiție de cursă.
Rezolvarea problemei filosofilor dining
Folosim un semafor pentru a reprezenta o bețișoară și aceasta acționează cu adevărat ca o soluție a problemei Filozofilor de masă. Operațiile Wait și Signal vor fi folosite pentru rezolvarea problemei Dining Philosophers, pentru alegerea unei bețișoare se poate executa operația de așteptare, în timp ce pentru eliberarea unui bețișor se poate executa semaforul de semnal.
Semafor: Un semafor este o variabilă întreagă în S, care în afară de inițializare este accesată de doar două operații atomice standard - așteptare și semnal, ale căror definiții sunt după cum urmează:
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></=> Inițial, fiecare element al semaforului C0, C1, C2, C3 și C4 este inițializat la 1, deoarece bețișoarele sunt pe masă și nu sunt ridicate de niciunul dintre filozofi.
Să modificăm codul de mai sus al problemei dining Philosopher utilizând operații cu semafor, așteptați și semnalați, codul dorit arată ca
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 } } În codul de mai sus, prima operație de așteptare este efectuată pe take_chopstickC[i] și take_chopstickC [ (i+1) % 5]. Asta arată filosofului că am luat bețișoarele din stânga și din dreapta. Funcția de mâncare este efectuată după aceea.
După terminarea mesei de către filozoful i the, operația de semnal este efectuată pe take_chopstickC[i] și take_chopstickC [ (i+1) % 5]. Asta arată că filozoful pe care l-am mâncat și a pus jos atât bețișoarele din stânga cât și din dreapta. În cele din urmă, filozoful începe să gândească din nou.
Să înțelegem cum codul de mai sus oferă o soluție problemei filosofului de mese?
Fie valoarea lui i = 0(valoarea inițială), Să presupunem că Philosopher P0 vrea să mănânce, va intra în funcția Philosopher() și va executa Așteptați( ia_bețișonC[i] ); făcând asta ține betisoare C0 și reduce semaforul C0 la 0 , dupa aceea se executa Așteptați( take_chopstickC[(i+1) % 5] ); făcând asta ține betisoare C1 ( deoarece i = 0, prin urmare (0 + 1) % 5 = 1) și reduce semaforul C1 la 0
În mod similar, să presupunem că acum Philosopher P1 vrea să mănânce, va intra în funcția Philosopher() și va executa Așteptați( ia_bețișonC[i] ); făcând acest lucru va încerca să țină betisoare C1 dar nu va putea face asta , întrucât valoarea semaforului C1 a fost deja setată la 0 de către filozoful P0, de aceea va intra într-o buclă infinită din cauza căreia filosoful P1 nu va putea să aleagă betisoarele C1, în timp ce dacă Philosoful P2 vrea să mănânce, va intra în Philosopher. () funcţionează şi execută Așteptați( ia_bețișonC[i] ); făcând asta ține betisoare C2 și reduce semaforul C2 la 0, după aceea, se execută Așteptați( take_chopstickC[(i+1) % 5] ); făcând asta ține betisoare C3 (de vreme ce i =2, prin urmare (2 + 1) % 5 = 3) și reduce semaforul C3 la 0.
Prin urmare, codul de mai sus oferă o soluție la problema filozofului de luat masa, Un filosof poate mânca numai dacă sunt disponibile atât bețișoarele din stânga cât și cele din dreapta ale filosofului, altfel filosoful trebuie să aștepte. De asemenea, dintr-o dată, doi filozofi independenți pot mânca simultan (adică, filosof P0 și P2, P1 și P3 și P2 și P4 pot mânca simultan, deoarece toate sunt procese independente și urmează constrângerea de mai sus a problemei filosofului mesei)
Clasa abstractă poate avea constructor
Dezavantajul soluției de mai sus a problemei filozofului mesei
Din soluția de mai sus a problemei filosofului dining, am dovedit că doi filozofi vecini nu pot mânca în același moment în timp. Dezavantajul soluției de mai sus este că această soluție poate duce la o stare de blocaj. Această situație se întâmplă dacă toți filozofii își aleg bețișorul din stânga în același timp, ceea ce duce la starea de impas și niciunul dintre filosofi nu poate mânca.
Pentru a evita blocajul, unele dintre soluții sunt următoarele -
- Numărul maxim de filozofi de pe masă nu trebuie să fie mai mare de patru, în acest caz, betișa C4 va fi disponibilă pentru filozoful P3, așa că P3 va începe să mănânce și, după terminarea procedurii sale de mâncare, va lăsa jos ambele bețișoare C3. și C4, adică semaforul C3 și C4 vor fi acum incrementați la 1. Acum, filozoful P2 care ținea bețișorul C2 va avea și bețișorul C3 disponibil, prin urmare, în mod similar, își va lăsa jos bețișorul după ce a mâncat și va permite altor filosofi să mănânce.
- Un filozof aflat într-o poziție egală ar trebui să aleagă bețișorul din dreapta și apoi bețișorul din stânga, în timp ce un filosof aflat într-o poziție impară ar trebui să aleagă bețișorul din stânga și apoi bețișul din dreapta.
- Numai în cazul în care ambele bețișoare (stânga și dreapta) sunt disponibile în același timp, numai atunci un filozof ar trebui să aibă voie să-și aleagă betisoarele.
- Toți cei patru filozofi de start (P0, P1, P2 și P3) ar trebui să aleagă betisa din stânga și apoi cea din dreapta, în timp ce ultimul filosof P4 ar trebui să aleagă betisa din dreapta și apoi cea din stânga. Acest lucru îl va forța pe P4 să țină mai întâi bețișorul drept, deoarece bețișorul drept al lui P4 este C0, care este deja ținut de filozoful P0 și valoarea sa este setată la 0, adică C0 este deja 0, din cauza căruia P4 va rămâne prins într-un infinit. bucla și betisa C4 rămâne liberă. Prin urmare, filozoful P3 are disponibile atât bețișoarele C3 stânga, cât și cele din dreapta C4, de aceea va începe să mănânce și își va lăsa ambele bețișoare jos odată ce termină și îi va lăsa pe alții să mănânce, ceea ce elimină problema blocajului.
Proiectarea problemei a fost să ilustreze provocările evitării blocajului, o stare de blocaj a unui sistem este o stare în care nu este posibil nici un progres al sistemului. Luați în considerare o propunere în care fiecare filozof este instruit să se comporte după cum urmează:
- Filosoful este instruit să gândească până când furculița din stânga este disponibilă, când este disponibilă, ține-o.
- Filosoful este instruit să gândească până când furculița potrivită este disponibilă, când este disponibilă, ține-o.
- Filosoful este instruit să mănânce atunci când ambele furculițe sunt disponibile.
- apoi, puneți mai întâi furculița dreaptă jos
- apoi, puneți furculița din stânga jos
- repeta de la inceput.