Philosophers' Dinner

Problem description:

• Five philosophers are sitting around a circular table for dinner.
• Every philosopher has a dish for eating noodles.
• In addition, they have hashis rather than forks
• Each needs 2 hashis
• Between each pair of dishes there is only one hashi.
• Hashis need to be shared in a synchronized way

ProblemRules:

• Philosopherseatandthink,inturn
• Whentheyeat,theygetonlyonehashiatatime
• Ifyoucangetthetwo,eatforafewmomentsandthendropthehashis

TheXofthequestion:Howtopreventthemfrombeingblocked?

Solutions

#define N 5 /* número de filósofos */ void filosofo(int i) /* i: número do filósofo, de 0 até 4 */ { while(true){ pense(); /* Filosofo está pensando */ pegue_hashi(i); /* pegue o Hashi esquerdo */ pegue_hashi((i+1) % N); /* pegue o Hashi direito; % é o operador módulo */ coma(); /* yum-yum, spaghetti rs */ largar_hashi(i) ; /* larga o hashi esquerdo*/ largar_hashi((i+1) % N); /* larga o hashi direito */ } }

Does the above code work?

In pegue_hashi() : If all philosophers get the hash on the left, none will take the one on the right - DEADLOCK

See

Andhowtosolve?

Afterpickingupthelefthashi,thephilosophercheckstoseeiftherightoneisfree.Ifitisnot,returnthehashiyoupickedup,waitabit,andtryagain.

Whatistheproblemwiththissolution?

Ifallphilosopherstakethelefthashatthesametime:

• Summertherightisnotfree
• Dropyourhashiandwait
• Retrievethelefthashagain
• Summertherightisnotfree
• ...(Loopinginfinite)

Thentheissuesthatshouldbeavoided:

• Deadlock-allphilosophersgetasinglehashiatthesametime
• Starvation - philosophers go on indefinitely hashis simultaneously.

What now? What do I need to do?

We could make them wait for a random time

• Reduces the chance of starvation
• In most applications, trying again is not a problem
• Via ethernet, this is exactly what is done with packet forwarding
• What if this process is used in nuclear plant safety control? Is this a good idea?

Return to another question : How to avoid multiple attempts?

Using semaphores would solve the problem, see:

#define N 5 /* número de filósofos */
semaphore mutex = 1;

void filosofo(int i) /* i: número do filósofo, de 0 até 4 */
{
    while(true){
         pense();  /* Filosofo está pensando */
         down(&mutex); /* requisita o semáforo */
         pegue_hashi(i); /* pegue o Hashi esquerdo */
         pegue_hashi((i+1) % N); /* pegue o Hashi direito; % é o operador módulo */
         coma(); /* yum-yum, spaghetti rs */
         largar_hashi(i) ; /* larga o hashi esquerdo*/
         largar_hashi((i+1) % N); /* larga o hashi direito */
         up(&mutex); /* Libera o semáforo para os outros */
    }
}

Theoretically, it is a suitable solution in practice, however, it has a performance problem:

• Only a philosopher can eat at any given time
• With 5 hashis, we should allow 2 philosophers to eat at the same time

But after all, how do I solve without deadlocks or starvation and with maximum parallelism to an arbitrary number of philosophers?

Use a state array to identify whether a philosopher is eating, thinking, or hungry (thinking of taking the hashis).

• A philosopher can only eat (state) if none of his neighbors are eating
• Use a set of semaphores, one per philosopher
• Hungry philosophers can be blocked if hashis are busy

Rewriting the code:

#define N 5 /* número de filósofos */
#define LEFT /* número do vizinho da ESQUERDA */
#define RIGHT /* número do vizinho da DIREITA */
#define PENSANDO 0 /* Filósofo está pensando */
#define FAMINTO 1 /* Filósofo está faminto */
#define COMENDO 2 /* Filósofo está comendo */
typedef int semaphore; /* o semáforo é um tipo especial de int  */
int state[N]; /* Array para acompanhar o estado de todos*/
semaphore mutex = 1; /* exclusão mútua para regiões críticas */
semaphore s[N]; /* um semáforo por filósofo */

void filosofo(int i) /* i: número do filósofo, de 0 até 4 */
{

   while(true){
      pense();  /* Filosofo está pensando */

      pegue_hashi(i); /* pegue os dois Hashis */

      coma(); /* yum-yum, spaghetti rs */

      largar_hashi(i) ; /* larga os dois Hashis */             
  }
}

void pegue_hashi(int i){ /* i: numero do filosofo, de 0 até N-1 */
   down(&mutex); /* entra na região crítica */
   state[i] = FAMINTO; /* recorda o fato que o filósofo i está faminto */
   testa(i); /* tenta adquirir as DUAS hashis */
   up(&mutex); /* sai da região crítica */
   down(&s[i]); /* bloqueie se os hashis não foram adquiridos */ 
}

void largar_hashi(i){ /* i: numero do filosofo, de 0 até N-1 */
   down(&mutex); /* entra na região crítica */
   state[i] = PENSANDO; /* recorda o fato que o filósofo i está faminto */
   testa(LEFT); /* veja se o vizinho da esquerda pode agora comer */ 
   testa(RIGHT ); /* veja se o vizinho da direita pode agora comer */
   up(&mutex); /* sai da região crítica */
}

void testa(i){ /* i: numero do filosofo, de 0 até N-1 */
   if(state[i] == FAMINTO && state[LEFT] != COMENDO && state[RIGHT] != COMENDO ){
      state[i] = COMENDO;
      up(&s[i]); /* libera se os hashis foram adquiridos */
    }
}

• What does the philosophers' dinner actually model?

Useful for modeling processes that compete for exclusive access to a limited number of resources.

• How important is it to a programmer? when a programmer should you care about this problem directly?

The advantages of concurrent programming is the increase in program performance, due to the increase in the number of tasks that can be performed during a certain period of time. Concurrent access to data and shared resources can create a situation of inconsistency of these same resources, because the various instances access and manipulate simultaneously, giving situations of inconsistency and failure. So for a routine or program to be consistent, mechanisms are needed to ensure the orderly and correct execution of cooperative processes.

Response Source:

• Classic Inter-Process Communication Problems

• THREADS, SEMÁFOROS AND DEADLOCKS - O DINING OF THE PHILOSOPHERS

Problem of the gluttonous philosophers (dinner of the philosophers):

Imagine a round table with 5 chairs and in each of the chairs is sitting a philosopher. At this table there are 5 dishes of spaghetti and 5 forks, and in front of each spaghetti dish will be a philosopher. However, to be able to eat each philosopher will have to use 2 forks.

That is, with 5 forks on the table and 5 philosophers, can only eat 2 philosophers at the same time getting 1 fork to spare.

Being able to eat all of them at the same time would require 10 forks.

Problem:Ifeveryonewantstoeatandpickupafork,everyphilosopherwillhaveafork,butnoneofthemwillbeabletoeat.Wewillhaveastalemate,forallphilosopherswilleternallywaitfortheotherfork,givingthemselvesadeadlock.Inthecontextofthisdinnerhappenswhenallphilosophersarepreventedfromeatingbecausetheycannotaffordforthat.

DeadLock:occurswhentwoormoreprocessesarepreventedfromcontinuing,forarewaitingforafeaturethatwillneverbeavailable.

Intechnicalterms,eachphilosopherrepresentsaprocessandeachforkisaresourceandthereiscompetitionforresources,andisthereforeconsideredoneofthecompetitionmodels.Topreventthisfromhappeningitisnecessarytosynchronizetheprocesses,sothatwhenoneisusingacertainresourceanotherprocesswillhavetowaittousethatsameresource.

Importancetoadeveloper:Thisisanimportantsituationforaprogrammertobeabletovisualizeadeadlocksituationandtounderstandtheimportanceofusingsynchronizationmechanisms.

Realsituations:TheonlyrealsituationIfoundisthecaseoftrafficlights,thatthesewerenotsynchronized,whatwouldhappenisthateventuallythesewouldandtherewouldbeaccidents,soitisessentialthattheyaresynchronizedtoavoidaccidentsandtoallowlesstraffic.

Searchsources:

First

Second

Terceira

Quarta

Farm

    

The problem of gluttonous philosophers has already been explained by @ idkWhy. I just wanted to complement his response since in my opinion there is a bit more knowledge to be removed from the proposed problem.

This response takes into account other narratives that are not part of the problem as it was originally proposed in 1965 by Dijkstra. Normally the focus always falls to the problem of obtaining resources, however I would also like to explore narratives where there is no problem getting resources.

As explained, there are 5 forks (a feature, let's imagine a synchronization object) on the table and 5 philosophers (one thread). Each philosopher needs 2 forks to eat. As all philosophers are starving (threads are running code) each philosopher grabs a fork (gets the resource).

1. Well behaved philosophers, and for this reason a non-problem

But so far there is still no problem, because a philosopher has the brilliant idea to drop his fork, in return, the philosopher who wants his fork (ie, threads negotiate with an arbritador, who must obtain the resource). Once this philosopher has finished eating (releasing the resource), all other philosophers go running for the fork (purchase the resource). Like philosophers very competitive so they decided that those who fork first eat first. Let's give an example?

Filosofo = F
Garfo = G

F1 pega o G1
F2 pega o G2
F3 pega o G3
F4 pega o G4
F5 pega o G5

F2 decide largar o seu garfo.
F4 decidiu pagar o jantar a F2 
F4 obteve G2
F4 acabou de jantar e largou G2 e G4

F1, F2, F3, F5 vao pegar os garfos G2 e G4 o mais rapidamente possível.
Apenas dois deles terao sucesso.

A história repete-se de forma similar a quando F4 obteve o seu garfo, excepto que é de notar
que a medida que os filósofos vão acabando o seu jantar vai havendo mais garfos disponíveis.

This unnecessarily long and complicated narrative would be a possible solution so that the philosophers can eat and illustrates that there are only 5 forks there. 5 philosophers (and every philosopher needs two forks) does not mean that they can not dine, of course, in a properly organized process.

2. Proper identification of the problem

So let's make a narrative of an unorganized process, to properly identify what is the problem:

The philosophers sit at the table and begin to think. As they are famished, As soon as the food reaches the table, they try to get the 2 forks near you. Some philosophers decide to start by picking up the fork on the left and others deciding on the right.

Cenáro 1: Then by chance on the first try all the philosophers got a single fork and never no one could eat, for they wait forever for the other philosophers to leave their fork.

Scenario 2: A Philosopher has managed to get 2 forks but as soon as he has finished eating he is overpowered by confusion of all other philosophers, they are waiting for the wrong fork.

2.1. Exemplification of the problem (C #)

private static Random r = new Random(500);
private static int numeroFilosos = 200;
static void Main(string[] args)
{
    var garfos = Enumerable.Range(0, numeroFilosos)
        .Select(i => new Mutex(false))
        .ToArray();

    var filosofos = Enumerable.Range(0, numeroFilosos)
        .Select(i => new Thread(ComeOJantar)
        {
            IsBackground = false
        })
        .ToArray();
    for (int i = 0; i < filosofos.Length; i++)
    {
        //Os filosofos tem conhecimento dos garfos que estao ao seu lado
        filosofos[i].Start(Tuple.Create(garfos[i], garfos[(i+1)% filosofos.Length]));
    }
    Thread.Sleep(TimeSpan.FromSeconds(2));
    Parallel.ForEach(filosofos, f => f.Join());
    Console.WriteLine("Todos os filosofos comeram");
}

private static void ComeOJantar(object o)
{
    var dados = o as Tuple<Mutex, Mutex>;
    var garfo1 = dados.Item1;
    var garfo2 = dados.Item2;

    //Os filosofos obtem os garfos á pressa, uns obtem o da direita primeiro e outros
    //o da esquerda.
    if (r.NextDouble() > 0.5)
    {
        garfo1.WaitOne();
        garfo2.WaitOne();
        Thread.Sleep(TimeSpan.FromSeconds(1));
        //Os filosofos também nao tem cuidado em qual garfo poisar primeiro
        garfo1.ReleaseMutex();
        garfo2.ReleaseMutex();
    }
    else
    {
        garfo2.WaitOne();
        garfo1.WaitOne();
        Thread.Sleep(TimeSpan.FromSeconds(2));
        //Os filosofos também nao tem cuidado em qual garfo poisar primeiro
        garfo2.ReleaseMutex();
        garfo1.ReleaseMutex();
    }
}

3 Philosophers with table labels.

Once again we explore an organized process. This time the philosophers have table tags and decide to always take the left fork first.

It is still possible that philosophers obtain only the left fork. For this reason, they decide to drop their fork and think for a while so that their neighbor, if they are interested, can get their fork

3.1. Example of a solution, using resource ordering (C #)

The previous solution did not take account of the case where the philosophers got all the fork to their left

private static void ComeOJantar(object o)
{
    var dados = o as Tuple<Mutex, Mutex>;
    var garfoEsquerda = dados.Item1;
    var garfoDaDireita = dados.Item2;

    garfoEsquerda.WaitOne(); //os filosofos obtem o garfo da esquerda

    //este sleep serve apenas para efeitos ilustrativos
    //ele ajuda a simular a situação em que todos os filósofos 
    //conseguem obter o garfo da esquerda
    Thread.Sleep(TimeSpan.FromSeconds(5));

    //Os filosofos tentam agarrar o garfo da direita o mais rápidamente possivel
    //Contudo todos os garfos já estao ocupados
    while (!garfoDaDireita.WaitOne(TimeSpan.FromMilliseconds(50)))
    {
        //O filosofo decide largar o seu garfo e espera que o seu 
        //vizinho vá buscar o seu garfo
        garfoEsquerda.ReleaseMutex();

        //Este sleep faz parte da solução. 
        //Ele evita que o filosofo adquira o mesmo garfo imediatamente após o ter largado
        Thread.Sleep(TimeSpan.FromMilliseconds(r.Next(1, 5) * 100));

        garfoEsquerda.WaitOne();
    }
    //Neste momento os filosofos tem ambos os garfos e podem comer
    Thread.Sleep(TimeSpan.FromSeconds(1));
    garfoDaDireita.ReleaseMutex();
    garfoEsquerda.ReleaseMutex();
}

4. Victory victory, history has ended

The moral of this problem is that in competing environments you have to be careful in what order you acquire resources. If you work in single-threaded environments (for example nodejs) then you will never have problems with resource acquisition.

In principle if you use a transitional database, the database solves this problem for you. At least MSSQL resolves .

  

The SQL Server Database Engine automatically detects deadlock cycles   within SQL Server. The Database Engine chooses one of the sessions as   deadlock victim and the current transaction is terminated with an   error to break the deadlock.

Free translation:

The SQL server database detects deadlocks within SQL Server. He chooses one of the sessions as a deadlock victim and the current transaction is terminated with an error to break the deadlock

TL; DR

The problem of philosophers is no problem, if the process is properly organized.

In order to really exist, there must be resource acquisition in an unordered way

In particular, the acquisition of resources in different order is reported and viewed relatively simply

The moral of the story is that it will usually be enough to acquire and release resources in the same order

  

Answer 2 (new)

Complementing the general answers, I add an addendum, which in my view is considerable, and also practically reinforcing my first response:

As stated in Bruno Costa's reply, the problem in question was formulated by Edsger W. Dijkstra in 1965 .

With that, going back there where there were not many programming languages like today, and also features of the most limited languages, is really a simple exercise to show problems in synchronizations (as it says in the source itself).

Nowadays with the great range of resources and languages we have, the issue is in parts branched out for ourselves due to ideas beyond the proposed context (a simple synchronization exercise).

On Wikipedia, you have all the history and solutions to the problem:

Dining philosophers problem

• Resource Hierarchy Solution

What was the original solution proposed by Dijkstra, treating philosophers as processes and forks as resources.

• Arbitrage Solution

Solution where you have a "referee" in the context, for example the waiter, who will give the permissions and orders to the philosophers.

• Chandy / Misra Solution

In 1984, K. Mani Chandy and J. Misra gave the solution akin to arbitrary, but counting on philosophers to speak to each other using "requests," that is, each philosopher would solicit the fork from his right-hand neighbor and to the left, thus allowing, would have the 2 tools, and in case of failure, could wait to request another and lend his own fork, not falling into deadlock.

  

Answer 1 (old) [-2]

I will answer briefly from my point of view, with my words, that is, the line of thought is the same, but sometimes it is clear that we can have other ways.

What is the problem of gluttonous philosophers?

As I see it, it's simply a great analogy between process x feature, task x execution, or even more examples that we can fit in.

What does the philosophers' dinner actually model?

A well-crafted problem for a logical question. Although, if applied in the logic would be easier to solve, since we control all the ways.

How important is it to a programmer?

First of all, first of all, "where to begin to solve the situation" and after, what forms, and which is the best.

When should a programmer be directly concerned about this problem?

So that's the "X" of the question as I see it. I understand that, very briefly, we should always have well defined algorithm, not to enter the deadlock, as in the above answer.

That is, the importance of setting priorities, in brief example, a list of tasks that must be performed but depends on each other (they would be the philosophers, who depend on the forks), and then if they all need to be executed, what is the priority, that is, who has the power to move ahead? Or for example, on a scale of 0 to 100, what is the priority level of that?

Is there anything real and everyday that we run into with this problem without knowing it? I do not know, in a database?

An example with database: What is deadlock in SQL Server?

If someone understands differently, please comment!