What’s wrong with gluttonous philosophers?

Question

When it comes to concurrent programming, they always mention 3 classic problems/competition models:

1. producers and consumers
2. readers and writers
3. glutton philosophers (or dinner of philosophers)

I searched the site but in no time I found explaining what is this problem.

My doubts then are:

• what is the problem of gluttonous philosophers? (more focused on the statement/metaphor of the problem)
• what does the dinner of philosophers actually model? (more focused on the technical thing than is this problem, leaving the metaphor aside)
• what is its importance to a programmer? when a programmer should care directly about this problem?
• Is there anything real and everyday that we run into this problem without knowing it? I don’t know, in a database?

Answer 1

Dinner of the Philosophers

Description of the problem:

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

Rules of the problem:

• Philosophers eat and think, alternately
• When they eat, they only take one Hashi at a time
• If you can catch both, eat for a few moments and then drop the hashis

The X of the matter: How to prevent them from getting blocked?

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 */
    }
}

The code above works?

In pegue_hashi(): If all philosophers take Ashi from the left, none will take the right - DEADLOCK

Behold

And how to solve?

After picking up the Hashi from the left, the philosopher checks to see if the one on the right is free. If not, return the Hashi you have taken, wait a while and try again.

What’s wrong with this solution?

If all philosophers take Hashi from the left at the same time:

• You’ll see the one on the right isn’t free
• They’ll drop their Ashi and wait
• They’ll take Ashi again from the left
• You’ll see the one on the right isn’t free
• ... (Infinite looping)

Then the problems that must be avoided:

• Deadlock - all philosophers take a single Hashi at the same time
• Starvation - philosophers are indefinitely picking up hashis simultaneously.

Now what? What do I need to do?

We could make them wait a random time

• Reduces the chance of starvation
• In most applications, trying again is no problem
• Via ethernet, this is exactly what is done with sending packages
• What if this process is used to control safety in a nuclear power plant? It’s a good idea?

We return to another question: How to avoid multiple attempts?

The use of traffic lights 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 an appropriate solution in practice, however, it has a performance problem:

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

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

Use an arrangement - state - to identify whether a philosopher is eating, thinking or hungry (thinking about taking hashis).

• A philosopher can only eat (state) if none of the neighbors are eating
• Use a traffic light arrangement, 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 the dinner of philosophers actually models?

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

• What is its importance to a programmer? when a programmer should care directly about this problem?

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

Source of the answer:

• Classic Problems of Inter-Process Communication

• THREADS, TRAFFIC LIGHTS AND DEADLOCKS - PHILOSOPHERS' DINNER

Answer 2

Problem of gluttonous philosophers (dinner of philosophers):

---

Imagine a round table with five chairs and in each of the chairs is seated a philosopher. At this table there are 5 spaghetti dishes and 5 forks, and in front of each dish of Pandi there will be a philosopher. However, in order to eat each philosopher you 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.

In order to eat them all at the same time it would take 10 forks.

Problem: If everyone wants to eat and pick up a fork, each philosopher will have a fork but none of them will be able to eat. We will have a deadlock, for all philosophers will be eternally waiting for the other fork, giving themselves a deadlock. In the context of this dinner it happens when all philosophers are prevented from eating, because they have no conditions for such.

Deadlock: occurs when two or more proceedings are prevented from continuing, by are waiting for a resource that will never be available.

---

In technical terms, each philosopher represents a process and each fork a resource and a competition for resources is considered one of the models of competition. To prevent this from happening it is necessary to synchronize the processes, so that when one is using a certain resource another process will have to wait to use that same resource.

---

Importance for a programmer: This is an important situation for a programmer, to be able to visualize a deadlock situation and to realize the importance of good use of synchronization mechanisms.

---

Real situations: The only real situation I found is the case of traffic lights, let’s imagine that these were not synchronized, what would happen is that eventually these would both green and there would be accidents, so it is essential that these are synchronized to to avoid accidents and to allow less traffic.

Research sources:

First

Second

Third

Fourth

Fifth

Answer 3

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 little more knowledge to be drawn from the proposed problem.

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

As explained, there are 5 forks (a resource, let’s imagine a synchronization object) on the table and 5 philosophers (one thread). Each philosopher needs 2 forks to eat. How all philosophers are hungry (threads are running code) each philosopher takes a fork (acquires the resource).

1. Well-behaved philosophers and therefore not a problem

But so far there is no problem, because a philosopher has the brilliant idea to drop your fork, in return, the philosopher who wants his fork buys him dinner (i.e., threads deal with an arbritrador, who must obtain the resource). Once this philosopher has finished eating (releasing the resource), all the other philosophers go running looking for the fork (get the resource). Like philosophers are very competitive so they decided that those who manage to get the first eat fork. 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 philosophers can eat and illustrates that there are only 5 forks for 5 philosophers (and each philosopher needs two forks) does not mean that they cannot dine, of course, in a properly organised process.

2. Due identification of the problem

So we’re going to do a narrative of an unorganized process, to properly identify what’s the matter:

Philosophers sit at the table and begin to think. As they are hungry, As soon as the food gets to the table, they try to pick up the two forks near you. Some philosophers decide to start by taking the fork on the left and others decide the one on the right.

Table 1: Soon by chance on the first attempt all philosophers got a single fork and never no one eats because they wait forever for other philosophers to leave their fork.

Scenario 2: A Philosopher has managed to get 2 forks but as soon as he finishes eating he gets flattened with the confused 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 label.

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

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

3.1. Example of a solution, using orderly resource acquisition (c#)

The previous solution did not take over the case where philosophers all got the fork on 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 over

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-thread environments (for example nodejs) then you will never have problems with resource acquisition.

In principle if Voce uses a transitional database, the database solves this problem by itself. At least MSSQL solves.

The SQL Server Database Engine Automatically detects deadlock Cycles Within SQL Server. The Database Engine chooses one of the Sessions as a deadlock Victim and the Current transaction is terminated with an error to break the deadlock.

In free translation:

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

TL;DR

1. The problem of philosophers is not a problem if the process is properly organized.
2. For there to really be a problem it is necessary to acquire resources in an uneven way
3. In particular, the acquisition of resources in different order is reported and viewed relatively simply
4. The moral of the story is that it will normally be sufficient to acquire and release resources in the same order

Answer 4

Answer 2 (new)

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

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

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

Today with the wide range of resources and languages we have, the issue is in parts branched by 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

• Solution of resource hierarchy

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

• Arbitration solution

Solution where there is an "arbiter" in the context, for example the waiter, who will give the permissions and orders to philosophers.

• Chandy / Misra Solution

In 1984, K. Mani Chandy and J. Misra, gave the solution similar to arbitrary, but as long as philosophers spoke to each other, using "requests", that is, each philosopher would request the fork from his neighbor on the right and on the left, thus allowing, would have the 2 tools, and if not succeeding, could expect the request of another and borrow his own fork, not falling into deadlock.

---

Answer 1 (old) [ -2 ]

I will respond briefly from my point of view, with my words, that is, the line of thought is the same, but sometimes clear that we may have other paths.

what is the problem of gluttonous philosophers?

In my view, simply a great analogy, between process x resource, task x execution, or even more examples that we can fit.

what philosophers' dinner actually models?

A well-thought-out problem for a logical question. Yet, if applied in logic it would be easier to solve, since we control all paths.

how important it is to a programmer?

First of all, right from the start on "where to start to resolve the situation" and after, what the ways, and what the best.

when a programmer should care directly about this problem?

There’s the "X" of the question in my view. I understand that, very briefly, we should always have well defined the algorithm, not to enter the deadlock, as in the answer above.

That is, the importance of setting priorities, soon example, a list of tasks that must be performed but depends on each other (would be philosophers, who depend on forks), and then if everyone needs to be performed, which is the priority, That is, what has the power to pass in front ? Or for example, on a scale from 0 to 100, what is the priority level of that ?

Is there anything real and everyday that we run into this problem without knowing it? I don’t know, in a database?

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

If anyone understands differently, please comment !