Problémom filozofa stolovania je klasický problém synchronizácie, ktorý hovorí, že päť filozofov sedí okolo kruhového stola a ich úlohou je myslieť a jesť alternatívne. Miska rezancov je umiestnená v strede stola spolu s piatimi paličkami pre každého z filozofov. Aby filozof zjedol, potrebuje pravú aj ľavú paličku. Filozof môže jesť iba vtedy, ak má k dispozícii ľavú aj pravú paličku filozofa. V prípade, že nie sú k dispozícii obe bezprostredné ľavé a pravé paličky filozofa, filozof odloží svoju (buď ľavú alebo pravú) paličku a začne znova premýšľať.
Jedálenský filozof demonštruje veľkú triedu problémov s riadením súbežnosti, preto ide o klasický synchronizačný problém.
Päť filozofov sediacich okolo stola
Problém filozofov stravovania - Poďme pochopiť problém stravovacích filozofov s nižšie uvedeným kódom, ako referenciu sme použili obrázok 1, aby ste problém presne pochopili. Päť filozofov je reprezentovaných ako P0, P1, P2, P3 a P4 a päť paličiek C0, C1, C2, C3 a 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 } } Poďme diskutovať o vyššie uvedenom kóde:
Predpokladajme, že filozof P0 chce jesť, vstúpi do funkcie Philosopher() a vykoná sa zober_palicku[i]; tým to drží C0 palička potom sa vykoná take_chopstick[ (i+1) % 5]; tým to drží C1 palička ( keďže i = 0, teda (0 + 1) % 5 = 1)
Podobne predpokladajme, že teraz chce filozof P1 jesť, vstúpi do funkcie Philosopher() a vykoná zober_palicku[i]; tým to drží C1 palička potom sa vykoná take_chopstick[ (i+1) % 5]; tým to drží C2 palička ( keďže i = 1, teda (1 + 1) % 5 = 2)
Prakticky Chopstick C1 však nie je k dispozícii, pretože ju už prevzal filozof P0, a preto vyššie uvedený kód generuje problémy a spôsobuje preteky.
Riešenie problému stravovacích filozofov
Používame semafor na znázornenie paličky a to skutočne funguje ako riešenie problému filozofov stolovania. Operácie Wait a Signal sa použijú na riešenie problému Dining Philosophers Problem, na výber paličky možno vykonať operáciu čakania, zatiaľ čo na uvoľnenie signálu paličky možno vykonať semafor.
Semafor: Semafor je celočíselná premenná v S, ku ktorej okrem inicializácie pristupujú iba dve štandardné atómové operácie - čakanie a signál, ktorých definície sú nasledovné:
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></=> Na začiatku sa každý prvok semaforu C0, C1, C2, C3 a C4 inicializuje na 1, keď sú paličky na stole a žiadny z filozofov ich nezdvihne.
stdin v c
Upravme vyššie uvedený kód problému Dining Philosopher Problem pomocou semaforových operácií čakania a signálu, požadovaný kód vyzerá takto
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 } } Vo vyššie uvedenom kóde sa prvá operácia čakania vykoná na take_chopstickC[i] a take_chopstickC [ (i+1) % 5]. Toto ukazuje, že filozof som zdvihol paličky zľava a sprava. Potom sa vykoná funkcia jedenia.
Po dokončení jedenia filozofom i the sa vykoná signálna operácia na take_chopstickC[i] a take_chopstickC [(i+1) % 5]. To ukazuje, že filozof, ktorého som zjedol a odložil ľavú aj pravú paličku. Nakoniec filozof začne znova premýšľať.
Poďme pochopiť, ako vyššie uvedený kód poskytuje riešenie problému filozofa stolovania?
Nech hodnota i = 0 ( počiatočná hodnota ), Predpokladajme, že filozof P0 chce jesť, vstúpi do funkcie Philosopher() a vykoná Wait( take_chopstickC[i] ); tým to drží C0 palička a znižuje semafor C0 na 0 , potom sa vykoná Wait( take_chopstickC[(i+1) % 5] ); tým to drží C1 palička ( keďže i = 0, teda (0 + 1) % 5 = 1) a redukuje semafor C1 na 0
Podobne predpokladajme, že teraz chce filozof P1 jesť, vstúpi do funkcie Philosopher() a vykoná Wait( take_chopstickC[i] ); tým sa to pokúsi udržať C1 palička ale nebude to môcť urobiť , keďže hodnotu semaforu C1 už filozof P0 nastavil na 0, preto sa dostane do nekonečnej slučky, kvôli ktorej filozof P1 nebude môcť vybrať paličku C1, zatiaľ čo ak chce filozof P2 jesť, vstúpi do filozofa () fungovať a vykonávať Wait( take_chopstickC[i] ); tým to drží C2 palička a zníži semafor C2 na 0, potom sa vykoná Wait( take_chopstickC[(i+1) % 5] ); tým to drží C3 palička ( keďže i =2, teda (2 + 1) % 5 = 3) a redukuje semafor C3 na 0.
Vyššie uvedený kód teda poskytuje riešenie problému filozofa stolovania. Filozof môže jesť iba vtedy, ak sú k dispozícii okamžité ľavé aj pravé paličky filozofa, inak filozof musí čakať. Naraz môžu súčasne jesť aj dvaja nezávislí filozofi (t. j. filozof P0 a P2, P1 a P3 a P2 a P4 môžu jesť súčasne, pretože všetky sú nezávislé procesy a riadia sa vyššie uvedeným obmedzením problému filozofa stolovania)
Nevýhodou vyššie uvedeného riešenia problému filozofa stolovania
Z vyššie uvedeného riešenia problému filozofa stolovania sme dokázali, že žiadni dvaja susediaci filozofi nemôžu jesť v rovnakom čase. Nevýhodou vyššie uvedeného riešenia je, že toto riešenie môže viesť k zablokovaniu. Táto situácia nastane, ak všetci filozofi uchopia ľavú paličku naraz, čo vedie k mŕtvemu bodu a žiadny z filozofov nemôže jesť.
Aby ste sa vyhli zablokovaniu, niektoré z riešení sú nasledovné -
- Maximálny počet filozofov na stole by nemal byť viac ako štyria, v tomto prípade bude pre filozofa P3 k dispozícii palička C4, takže P3 začne jesť a po ukončení svojej jedenej procedúry odloží obe paličky C3. a C4, t. j. semafor C3 a C4 sa teraz zvýši na 1. Teraz bude mať filozof P2, ktorý držal paličku C2, k dispozícii aj paličku C3, teda podobne po jedle odloží paličku a umožní jesť ostatným filozofom.
- Filozof na párnom mieste by mal vybrať pravú a potom ľavú paličku, zatiaľ čo filozof na nepárnej pozícii by mal vybrať ľavú a potom pravú.
- Iba v prípade, ak sú obidve paličky (ľavá a pravá) k dispozícii súčasne, iba vtedy by mal mať filozof možnosť vybrať si paličky.
- Všetci štyria začínajúci filozofi (P0, P1, P2 a P3) by si mali vybrať ľavú paličku a potom pravú, zatiaľ čo posledný filozof P4 by si mal vybrať pravú a potom ľavú paličku. To prinúti P4 držať svoju pravú paličku ako prvú, pretože pravá palička P4 je C0, ktorú už drží filozof P0 a jej hodnota je nastavená na 0, t.j. C0 je už 0, kvôli čomu bude P4 uväznený do nekonečna. slučka a palička C4 zostáva neobsadené. Preto má filozof P3 k dispozícii ľavú C3 aj pravú C4 paličku, preto začne jesť a po dokončení odloží obe paličky a nechá jesť ostatných, čím sa odstráni problém uviaznutia.
Návrh problému mal ilustrovať výzvy, ako sa vyhnúť zablokovaniu, stav zablokovania systému je stav, v ktorom nie je možný žiadny pokrok systému. Zvážte návrh, v ktorom je každý filozof poučený, aby sa správal takto:
- Filozof je poučený, aby premýšľal, kým nebude k dispozícii ľavá vidlica, a keď bude k dispozícii, podržte ju.
- Filozof je poučený, aby premýšľal, kým nebude k dispozícii správna vidlička, a keď bude k dispozícii, podržte ju.
- Filozof dostane pokyn jesť, keď sú k dispozícii obe vidličky.
- potom najprv položte pravú vidličku
- potom položte ľavú vidličku dole
- opakujte od začiatku.