Il problema del filosofo a tavola è il classico problema della sincronizzazione secondo il quale cinque filosofi sono seduti attorno a un tavolo circolare e il loro compito è pensare e mangiare alternativamente. Al centro del tavolo viene posta una ciotola di tagliatelle insieme a cinque bacchette per ciascuno dei filosofi. Per mangiare un filosofo ha bisogno sia della bacchetta destra che di quella sinistra. Un filosofo può mangiare solo se ha a disposizione entrambe le bacchette destra e sinistra. Nel caso in cui entrambe le bacchette sinistra e destra del filosofo non siano disponibili, il filosofo mette giù la bacchetta (sinistra o destra) e inizia a pensare di nuovo.
Il filosofo della cena dimostra un'ampia classe di problemi di controllo della concorrenza, quindi è un classico problema di sincronizzazione.
Cinque filosofi seduti attorno al tavolo
Problema dei filosofi a tavola - Comprendiamo il problema dei filosofi a tavola con il codice seguente, abbiamo usato la fig 1 come riferimento per farti capire esattamente il problema. I cinque Filosofi sono rappresentati da P0, P1, P2, P3 e P4 e i cinque bastoncini da C0, C1, C2, C3 e 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 } } Parliamo del codice sopra:
Supponiamo che il Filosofo P0 voglia mangiare, entrerà nella funzione Filosofo() ed eseguirà prendi_bacchette[i]; così facendo regge Bacchette C0 dopodiché viene eseguito prendi_bacchette[ (i+1) % 5]; così facendo regge Bacchette C1 ( poiché i =0, quindi (0 + 1) % 5 = 1)
Allo stesso modo, supponiamo che ora il Filosofo P1 voglia mangiare, entrerà nella funzione Filosofo() ed eseguirà prendi_bacchette[i]; così facendo regge Bacchette C1 dopodiché viene eseguito prendi_bacchette[ (i+1) % 5]; così facendo regge Bacchette C2 ( poiché i =1, quindi (1 + 1) % 5 = 2)
lancia la stringa come int
Ma Praticamente Chopstick C1 non è disponibile in quanto è già stata presa dal filosofo P0, quindi il codice sopra genera problemi e produce race condition.
La soluzione del problema dei filosofi a tavola
Usiamo un semaforo per rappresentare una bacchetta e questo funge davvero da soluzione al problema dei filosofi a tavola. Le operazioni Wait e Signal verranno utilizzate per la soluzione del problema dei filosofi a tavola, per la scelta di una bacchetta si può eseguire l'operazione di attesa mentre per rilasciare il segnale della bacchetta si può eseguire un semaforo.
Semaforo: un semaforo è una variabile intera in S, a cui, a parte l'inizializzazione, si accede solo da due operazioni atomiche standard: attesa e segnale, le cui definizioni sono le seguenti:
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></=> Inizialmente, ogni elemento del semaforo C0, C1, C2, C3 e C4 viene inizializzato a 1 poiché le bacchette sono sul tavolo e non vengono prese da nessuno dei filosofi.
Modifichiamo il codice precedente del problema del filosofo a tavola utilizzando le operazioni del semaforo wait and signal, il codice desiderato assomiglia a
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 } } Nel codice precedente, la prima operazione di attesa viene eseguita su take_chopstickC[i] e take_chopstickC [ (i+1) % 5]. Questo mostra al filosofo che ho preso le bacchette da sinistra e da destra. Successivamente viene eseguita la funzione del mangiare.
Al termine del pasto da parte del filosofo i, l'operazione di segnale viene eseguita su take_chopstickC[i] e take_chopstickC [ (i+1) % 5]. Ciò dimostra che il filosofo ha mangiato e ha posato sia la bacchetta sinistra che quella destra. Alla fine il filosofo ricomincia a pensare.
Capiamo come il codice sopra fornisce una soluzione al problema del filosofo a tavola?
Sia il valore di i = 0 (valore iniziale), supponiamo che il Filosofo P0 voglia mangiare, entrerà nella funzione Filosofo() ed eseguirà Aspetta( prendi_bastoneC[i] ); così facendo regge Bacchette C0 e riduce il semaforo C0 a 0 , dopodiché viene eseguito Aspetta( prendi_bastoneC[(i+1) % 5] ); così facendo regge Bacchette C1 ( poiché i =0, quindi (0 + 1) % 5 = 1) e riduce il semaforo C1 a 0
Allo stesso modo, supponiamo che ora il Filosofo P1 voglia mangiare, entrerà nella funzione Filosofo() ed eseguirà Aspetta( prendi_bastoneC[i] ); in questo modo proverà a trattenere Bacchette C1 ma non sarà in grado di farlo , poiché il valore del semaforo C1 è già stato impostato a 0 dal filosofo P0, quindi entrerà in un ciclo infinito per cui il filosofo P1 non potrà prendere la bacchetta C1 mentre se il Filosofo P2 vuole mangiare entrerà in Filosofo () funzione ed eseguirla Aspetta( prendi_bastoneC[i] ); così facendo regge Bacchette C2 e riduce il semaforo C2 a 0, dopodiché viene eseguito Aspetta( prendi_bastoneC[(i+1) % 5] ); così facendo regge Bacchette C3 ( poiché i =2, quindi (2 + 1) % 5 = 3) e riduce il semaforo C3 a 0.
apprendimento automatico e tipi
Quindi il codice sopra fornisce una soluzione al problema del filosofo a tavola. Un filosofo può mangiare solo se sono disponibili entrambe le bacchette immediatamente sinistra e destra del filosofo, altrimenti il filosofo deve aspettare. Inoltre due filosofi indipendenti possono mangiare contemporaneamente (cioè filosofo P0 e P2, P1 e P3 e P2 e P4 possono mangiare simultaneamente poiché tutti i processi sono indipendenti e seguono il vincolo di cui sopra del problema del filosofo della cena)
Lo svantaggio della soluzione di cui sopra del problema del filosofo a tavola
Dalla soluzione del problema del filosofo a tavola, abbiamo dimostrato che due filosofi vicini non possono mangiare nello stesso momento. Lo svantaggio della soluzione di cui sopra è che questa soluzione può portare ad una condizione di stallo. Questa situazione si verifica se tutti i filosofi prendono la bacchetta sinistra contemporaneamente, il che porta alla condizione di stallo e nessuno dei filosofi può mangiare.
Per evitare lo stallo, alcune delle soluzioni sono le seguenti:
- Il numero massimo di filosofi sul tavolo non deve essere superiore a quattro, in questo caso, la bacchetta C4 sarà disponibile per il filosofo P3, quindi P3 inizierà a mangiare e dopo aver terminato la procedura di consumo, metterà giù entrambe le bacchette C3 e C4, cioè i semafori C3 e C4 verranno ora incrementati a 1. Ora il filosofo P2 che teneva in mano la bacchetta C2 avrà anche la bacchetta C3 a disposizione, quindi allo stesso modo, metterà giù la bacchetta dopo aver mangiato e consentirà ad altri filosofi di mangiare.
- Un filosofo in una posizione pari dovrebbe prendere la bacchetta destra e poi quella sinistra mentre un filosofo in una posizione dispari dovrebbe prendere la bacchetta sinistra e poi quella destra.
- Solo nel caso in cui entrambe le bacchette (sinistra e destra) siano disponibili contemporaneamente, solo allora a un filosofo dovrebbe essere consentito di scegliere le bacchette
- Tutti e quattro i filosofi iniziali (P0, P1, P2 e P3) dovrebbero prendere la bacchetta sinistra e poi quella destra, mentre l'ultimo filosofo P4 dovrebbe prendere la bacchetta destra e poi quella sinistra. Ciò costringerà P4 a tenere prima la bacchetta destra poiché la bacchetta destra di P4 è C0, che è già impugnata dal filosofo P0 e il suo valore è impostato su 0, cioè C0 è già 0, per cui P4 rimarrà intrappolato in un infinito il cappio e la bacchetta C4 rimangono vacanti. Quindi il filosofo P3 ha a disposizione sia la bacchetta sinistra C3 che quella destra C4, quindi inizierà a mangiare e metterà giù entrambe le bacchette una volta finito e lascerà che gli altri mangino, eliminando il problema dello stallo.
La progettazione del problema era quella di illustrare le sfide per evitare lo stallo, uno stato di stallo di un sistema è uno stato in cui non è possibile alcun progresso del sistema. Consideriamo una proposta in cui a ciascun filosofo viene chiesto di comportarsi come segue:
- Al filosofo viene chiesto di pensare finché la biforcazione sinistra non sarà disponibile, e quando sarà disponibile, trattenerla.
- Al filosofo viene detto di pensare finché non sarà disponibile la forchetta giusta e, quando sarà disponibile, di trattenerla.
- Al filosofo viene detto di mangiare quando entrambe le forchette sono disponibili.
- quindi, metti giù per prima la forchetta destra
- quindi, metti giù la forcella sinistra
- ripetere dall'inizio.