JANTAR DOS FILÓSOFOS

Implementação

O problema é modelado fazendo o uso do conceito de threads e semáforos, implementado através da linguagem concorrente Java.

Java concorrente

O conceito de processamento concorrente de tarefas integra a linguagem Java desde sua criação, através de multithreading. As threads em Java são gerenciadas pela JVM (Máquina Virtual Java), esta só suporta um processo, sendo necessário um novo JVM para cada processo novo. Para o desenvolvedor, o programa começa uma thread com a chamada de main thread, e este é responsável por criar novas threads. Na JVM, as threads são escalonadas de forma preemptiva seguindo o algoritmo escalonador “round-robin”. Isso quer dizer que o escalonador pode pará-las, dar espaço e tempo para outra thread ser executada. A etapa da criação de uma nova thread, está associada a uma classe filha que herda da classe Thread do próprio Java, ou implementado a interface Runnable.

O problema será implementado usando uma thread herdada, representando cada filósofo, para fazer a representação dos garfos será utilizado o conceito de semáforo. Será utilizado também as primitivas de sincronização wait e signal, para contornar a situação de bloqueio ao acessar o mesmo recurso, caso essas primitivas não fossem implementadas. Isso também auxilia no caso de mais de um filósofo ficar com fome ao mesmo tempo e tentar agarrar os garfos no mesmo instante, porém não garante que um filósofo não morra com fome.

Filósofo é uma thread filha da classe Thread
Semáforo representa o garfo
Wait e Signal contra o deadlock

Código

Classe Jantar

public class Jantar
{
   public static void main (String[] args)
   {
      Mesa mesa = new Mesa ();
      for (int filosofo = 0; filosofo < 5; filosofo++)
      {
         new Filosofo("Filosofo_" + filosofo, mesa, filosofo).start();
      }
   }
}

Classe Filósofo

public class Filosofo extends Thread
{
   final static int TEMPO_MAXIMO = 100;
   Mesa mesa;
   int filosofo;

   public Filosofo (String nome, Mesa mesadejantar, int fil)
   {
      super(nome);
      mesa = mesadejantar;
      filosofo = fil;
   }

   public void run ()
   {
      int tempo = 0;
      while (true)
      {
         tempo = (int) (Math.random() * TEMPO_MAXIMO);
         pensar(tempo);
         getGarfos();
         tempo = (int) (Math.random() * TEMPO_MAXIMO);
         comer(tempo);
         returnGarfos();
      }
   }

   public void pensar (int tempo)
   {
      try
      {
         sleep(tempo);
      }
      catch (InterruptedException e)
      {
         System.out.println("O Filófoso pensou em demasia");
      }
   }

   public void comer (int tempo)
   {
      try
      {
         sleep(tempo);
      }
      catch (InterruptedException e)
      {
         System.out.println("O Filósofo comeu em demasia");
      }

Classe Mesa

public class Mesa
{
   final static int PENSANDO = 1;
   final static int COMENDO = 2;
   final static int FOME = 3;
   final static int NR_FILOSOFOS = 5;
   final static int PRIMEIRO_FILOSOFO = 0;
   final static int ULTIMO_FILOSOFO = NR_FILOSOFOS - 1;
   boolean[] garfos = new boolean[NR_FILOSOFOS];
   int[] filosofos = new int[NR_FILOSOFOS];
   int[] tentativas = new int[NR_FILOSOFOS];

   public Mesa()
   {
      for (int i = 0; i < 5; i++)
      {
         garfos[i] = true;
         filosofos[i] = PENSANDO;
         tentativas[i] = 0;
      }
   }

   public synchronized void pegarGarfos (int filosofo)
   {
      filosofos[filosofo] = FOME;
      while (filosofos[aEsquerda(filosofo)] == COMENDO || filosofos[aDireita(filosofo)] == COMENDO)
      {
         try
         {
            tentativas[filosofo]++;
            wait();
         }
         catch (InterruptedException e)
         {
         }
      }
      System.out.println("O Filósofo morreu devido a starvation");
      tentativas[filosofo] = 0;
      garfos[garfoEsquerdo(filosofo)] = false;
      garfos[garfoDireito(filosofo)] = false;
      filosofos[filosofo] = COMENDO;
      imprimeEstadosFilosofos();
      imprimeGarfos();
      imprimeTentativas();
   }

   public synchronized void returningGarfos (int filosofo)
   {
      garfos[garfoEsquerdo(filosofo)] = true;
      garfos[garfoDireito(filosofo)] = true;
      if (filosofos[aEsquerda(filosofo)] == FOME || filosofos[aDireita(filosofo)] == FOME)
      {
         notifyAll();
      }
      filosofos[filosofo] = PENSANDO;
      imprimeEstadosFilosofos();
      imprimeGarfos();
      imprimeTentativas();
   }

   public int aDireita (int filosofo)
   {
      int direito;
      if (filosofo == ULTIMO_FILOSOFO)
      {
         direito = PRIMEIRO_FILOSOFO;
      }
      else
      {
         direito = filosofo + 1;
      }
      return direito;
   }

   public int aEsquerda (int filosofo)
   {
      int esquerdo;
      if (filosofo == PRIMEIRO_FILOSOFO)
      {
         esquerdo = ULTIMO_FILOSOFO;
      }
      else
      {
         esquerdo = filosofo - 1;
      }
      return esquerdo;
   }

   public int garfoEsquerdo (int filosofo)
   {
      int garfoEsquerdo = filosofo;
      return garfoEsquerdo;
   }

   public int garfoDireito (int filosofo)
   {
      int garfoDireito;
      if (filosofo == ULTIMO_FILOSOFO)
      {
         garfoDireito = 0;
      }
      else
      {
         garfoDireito = filosofo + 1;
      }
      return garfoDireito;
   }

   public void imprimeEstadosFilosofos ()
   {
      String texto = "*";
      System.out.print("Filósofos = [ ");
      for (int i = 0; i < NR_FILOSOFOS; i++)
      {
         switch (filosofos[i])
         {
            case PENSANDO :
               texto = "PENSANDO";
               break;
            case FOME :
               texto = "FOME";
               break;
            case COMENDO :
               texto = "COMENDO";
               break;
         }
         System.out.print(texto + " ");
      }
      System.out.println("]");
   }

   public void imprimeGarfos ()
   {
      String garfo = "*";
      System.out.print("Garfos = [ ");
      for (int i = 0; i < NR_FILOSOFOS; i++)
      {
         if (garfos[i])
         {
            garfo = "LIVRE";
         }
         else
         {
            garfo = "OCUPADO";
         }
         System.out.print(garfo + " ");
      }
      System.out.println("]");
   }

   public void imprimeTentativas ()
   {
      System.out.print("Tentou comer = [ ");
      for (int i = 0; i < NR_FILOSOFOS; i++)
      {
         System.out.print(filosofos[i] + " ");
      }
      System.out.println("]");
   }
}

Explicação da implementação em Java

A classe principal que implementa o problema é a Jantar, dentro do método main() um objeto da classe Mesa é instanciado, com isso todos os cinco filósofos da mesa iniciam pensando e com os garfos sobre a mesa. Continuando no main(), um laço é executado cinco vezes criando as threads representadas pelos filósofos no estado de criada (ou new), onde cada uma entra no estado de execução (ou runnable) através do método start() que rodará em sua própria thread de controle.

A classe Filosofo é herdada da classe Thread, está sobrescreve o método run() com o código que será executado pela thread, cada thread define a atividade concorrente pelo método run(), sendo a atividade concorrente iniciada quando é invocado o método start() sobre um objeto.

O método run() (executado por cada thread paralelamente) contém um loop “infinito”, dentro dele o procedimento sleep() é chamado pelo intermediário pensar(), passando um tempo aleatório.
Após isso o procedimento getGarfos() faz que o método pegarGarfos() da classe Mesa seja executado, este método é do tipo synchronized ou seja não permite que duas threads o executem simultaneamente, com isso este método define que o filósofo (thread) esteja com fome, e faz a verificação se algum dos seus vizinhos estão comendo, caso estejam, incrementa o contador de tentativas de pegar o garfo, na sequência o filósofo aguarda outro filósofo desocupar o garfo que está sendo usado, essa espera é devido a utilização do wait() no semáforo, quando o filósofo larga o garfo executa uma operação signal nesse mesmo semáforo.
Após pegar os garfos, ele coloca os garfos que está utilizando como ocupado, e começa a se alimentar.
Quando um filósofo não se alimentar devido aguardar a resposta de outro filósofo, ele morrerá por starvation, já que não lhe foi concedido os garfos para se alimentar.

Ainda dentro de run(), o procedimento comer() é chamado, passando um tempo aleatório a ele, após isso returningGarfos() do tipo synchronized da classe Mesa é chamado através do returnGarfos(), na sequência ele libera os garfos que estava utilizando, e verifica se algum dos filósofos da esquerda ou da direita está esperando uma notificação, avisando que os garfos estão livres para serem utilizados, e coloca o filósofo atual para pensar.

Após isso o loop completa um ciclo e volta a refazer todo esse passo-a-passo novamente, porém variando o tempo de pensar e comer.

Existem ainda outros métodos que não foram detalhados, porém são menos relevantes para entender o código, são eles:

aDireita(): Retorna o filósofo à direita
aEsquerda(): Retorna o filósofo à esquerda
garfoEsquerdo(): Retorna o garfo à esquerda
garfoDireito(): Retorna o garfo à direita
imprimeEstadosFilosofos(): Imprime o estado de cada filósofo
imprimeGarfos(): Imprime o uso de cada garfo
imprimeTentativas(): Imprime as tentativas de pegar os garfos

Exemplo de saída

Temos os vetores Filósofos, Garfos e Tentou comer, imprimindo seus valores da primeira até a última posição em ordem crescente, iniciando imprimindo os valores definidos quando o objeto mesa foi instanciado, e logo em sequência as ações realizadas pelos filósofos (threads).

------------------------INICIO------------------------------
Filósofos = [ PENSANDO PENSANDO PENSANDO PENSANDO PENSANDO ]
Garfos = [ LIVRE LIVRE LIVRE LIVRE LIVRE ]

----------------------------------------------------------
O Filósofo_4 morreu devido a starvation
Filósofos = [ PENSANDO PENSANDO PENSANDO PENSANDO COMENDO ]
Garfos = [ OCUPADO LIVRE LIVRE LIVRE OCUPADO ]
Tentou comer = [ 1 1 1 1 2 ]
Filósofos = [ PENSANDO PENSANDO PENSANDO PENSANDO PENSANDO ]
Garfos = [ LIVRE LIVRE LIVRE LIVRE LIVRE ]
Tentou comer = [ 1 1 1 1 1 ]

--------------------------------------------------------
O Filósofo_0 morreu devido a starvation
Filósofos = [ COMENDO PENSANDO PENSANDO PENSANDO PENSANDO ]
Garfos = [ OCUPADO OCUPADO LIVRE LIVRE LIVRE ]
Tentou comer = [ 2 1 1 1 1 ]
O Filósofo_2 morreu devido a starvation
Filósofos = [ COMENDO PENSANDO COMENDO PENSANDO PENSANDO ]
Garfos = [ OCUPADO OCUPADO OCUPADO OCUPADO LIVRE ]
Tentou comer = [ 2 1 2 1 1 ]
Filósofos = [ COMENDO FOME PENSANDO FOME FOME ]
Garfos = [ OCUPADO OCUPADO LIVRE LIVRE LIVRE ]
Tentou comer = [ 2 3 1 3 3 ]

--------------------------------------------------------
O Filósofo_3 morreu devido a starvation
Filósofos = [ COMENDO FOME PENSANDO COMENDO FOME ]
Garfos = [ OCUPADO OCUPADO LIVRE OCUPADO OCUPADO ]
Tentou comer = [ 2 3 1 2 3 ]
Filósofos = [ PENSANDO FOME PENSANDO COMENDO FOME ]
Garfos = [ LIVRE LIVRE LIVRE OCUPADO OCUPADO ]
Tentou comer = [ 1 3 1 2 3 ]

--------------------------------------------------------
O Filósofo_1 morreu devido a starvation
Filósofos = [ PENSANDO COMENDO PENSANDO COMENDO FOME ]
Garfos = [ LIVRE OCUPADO OCUPADO OCUPADO OCUPADO ]
Tentou comer = [ 1 2 1 2 3 ]
Filósofos = [ FOME PENSANDO PENSANDO COMENDO FOME ]
Garfos = [ LIVRE LIVRE LIVRE OCUPADO OCUPADO ]
Tentou comer = [ 3 1 1 2 3 ]

--------------------------------------------------------
O Filósofo_0 morreu devido a starvation
Filósofos = [ COMENDO PENSANDO PENSANDO COMENDO FOME ]
Garfos = [ OCUPADO OCUPADO LIVRE OCUPADO OCUPADO ]
Tentou comer = [ 2 1 1 2 3 ]
Filósofos = [ COMENDO PENSANDO PENSANDO PENSANDO FOME ]
Garfos = [ OCUPADO OCUPADO LIVRE LIVRE LIVRE ]
Tentou comer = [ 2 1 1 1 3 ]

--------------------------------------------------------
O Filósofo_3 morreu devido a starvation
Filósofos = [ COMENDO PENSANDO PENSANDO COMENDO FOME ]
Garfos = [ OCUPADO OCUPADO LIVRE OCUPADO OCUPADO ]
Tentou comer = [ 2 1 1 2 3 ]
Filósofos = [ PENSANDO PENSANDO FOME COMENDO FOME ]
Garfos = [ LIVRE LIVRE LIVRE OCUPADO OCUPADO ]
Tentou comer = [ 1 1 3 2 3 ]

--------------------------------------------------------
O Filósofo_1 morreu devido a starvation
Filósofos = [ PENSANDO COMENDO FOME COMENDO FOME ]
Garfos = [ LIVRE OCUPADO OCUPADO OCUPADO OCUPADO ]
Tentou comer = [ 1 2 3 2 3 ]
Filósofos = [ PENSANDO COMENDO FOME PENSANDO FOME ]
Garfos = [ LIVRE OCUPADO OCUPADO LIVRE LIVRE ]
Tentou comer = [ 1 2 3 1 3 ]

--------------------------------------------------------
O Filósofo_4 morreu devido a starvation
Filósofos = [ PENSANDO COMENDO FOME PENSANDO COMENDO ]
Garfos = [ OCUPADO OCUPADO OCUPADO LIVRE OCUPADO ]
Tentou comer = [ 1 2 3 1 2 ]
Filósofos = [ PENSANDO COMENDO FOME PENSANDO PENSANDO ]
Garfos = [ LIVRE OCUPADO OCUPADO LIVRE LIVRE ]
Tentou comer = [ 1 2 3 1 1 ]

--------------------------------------------------------
Filósofos = [ FOME PENSANDO FOME PENSANDO PENSANDO ]
Garfos = [ LIVRE LIVRE LIVRE LIVRE LIVRE ]
Tentou comer = [ 3 1 3 1 1 ]

--------------------------------------------------------
O Filósofo_2 morreu devido a starvation
Filósofos = [ FOME PENSANDO COMENDO PENSANDO PENSANDO ]
Garfos = [ LIVRE LIVRE OCUPADO OCUPADO LIVRE ]
Tentou comer = [ 3 1 2 1 1 ]
O Filósofo_0 morreu devido a starvation
Filósofos = [ COMENDO PENSANDO COMENDO PENSANDO PENSANDO ]
Garfos = [ OCUPADO OCUPADO OCUPADO OCUPADO LIVRE ]
Tentou comer = [ 2 1 2 1 1 ]
Filósofos = [ PENSANDO PENSANDO COMENDO PENSANDO PENSANDO ]
Garfos = [ LIVRE LIVRE OCUPADO OCUPADO LIVRE ]
Tentou comer = [ 1 1 2 1 1 ]

--------------------------------------------------------
O Filósofo_4 morreu devido a starvation
Filósofos = [ PENSANDO FOME COMENDO FOME COMENDO ]
Garfos = [ OCUPADO LIVRE OCUPADO OCUPADO OCUPADO ]
Tentou comer = [ 1 3 2 3 2 ]
Filósofos = [ PENSANDO FOME PENSANDO FOME COMENDO ]
Garfos = [ OCUPADO LIVRE LIVRE LIVRE OCUPADO ]
Tentou comer = [ 1 3 1 3 2 ]

--------------------------------------------------------
O Filósofo_1 morreu devido a starvation
Filósofos = [ PENSANDO COMENDO PENSANDO FOME COMENDO ]
Garfos = [ OCUPADO OCUPADO OCUPADO LIVRE OCUPADO ]
Tentou comer = [ 1 2 1 3 2 ]
Filósofos = [ PENSANDO COMENDO PENSANDO FOME PENSANDO ]
Garfos = [ LIVRE OCUPADO OCUPADO LIVRE LIVRE ]
Tentou comer = [ 1 2 1 3 1 ]

--------------------------------------------------------
O Filósofo_3 morreu devido a starvation
Filósofos = [ PENSANDO COMENDO PENSANDO COMENDO PENSANDO ]
Garfos = [ LIVRE OCUPADO OCUPADO OCUPADO OCUPADO ]
Tentou comer = [ 1 2 1 2 1 ]
Filósofos = [ PENSANDO PENSANDO FOME COMENDO PENSANDO ]
Garfos = [ LIVRE LIVRE LIVRE OCUPADO OCUPADO ]
Tentou comer = [ 1 1 3 2 1 ]

--------------------------------------------------------
Filósofos = [ PENSANDO PENSANDO FOME PENSANDO PENSANDO ]
Garfos = [ LIVRE LIVRE LIVRE LIVRE LIVRE ]
Tentou comer = [ 1 1 3 1 1 ]

--------------------------------------------------------
O Filósofo_2 morreu devido a starvation
Filósofos = [ PENSANDO PENSANDO COMENDO PENSANDO PENSANDO ]
Garfos = [ LIVRE LIVRE OCUPADO OCUPADO LIVRE ]
Tentou comer = [ 1 1 2 1 1 ]
Filósofos = [ PENSANDO PENSANDO PENSANDO PENSANDO PENSANDO ]
Garfos = [ LIVRE LIVRE LIVRE LIVRE LIVRE ]
Tentou comer = [ 1 1 1 1 1 ]

PROBLEMA CLÁSSICO - JANTAR DOS FILÓSOFOS

Utilizando linguagem concorrente Java para implementar o problema clássico Jantar dos Filósofos.
Repositório Educacional Aberto (REA)

Descrição do problema

Implementação

O problema é modelado fazendo o uso do conceito de threads e semáforos, implementado através da linguagem concorrente Java.

Java concorrente

Código

Classe Jantar

Classe Filósofo

Classe Mesa

Explicação da implementação em Java

Exemplo de saída

Animação

Sobre

REA desenvolvido para a disciplina de sistemas operacionais da UEPG 2021.

Gustavo Chagas

PROBLEMA CLÁSSICO - JANTAR DOS FILÓSOFOS

Utilizando linguagem concorrente Java para implementar o problema clássico Jantar dos Filósofos. Repositório Educacional Aberto (REA)

Descrição do problema

Implementação

O problema é modelado fazendo o uso do conceito de threads e semáforos, implementado através da linguagem concorrente Java.

Java concorrente

Código

Classe Jantar

Classe Filósofo

Classe Mesa

Explicação da implementação em Java

Exemplo de saída

Animação

Sobre

REA desenvolvido para a disciplina de sistemas operacionais da UEPG 2021.

Gustavo Chagas

Utilizando linguagem concorrente Java para implementar o problema clássico Jantar dos Filósofos.
Repositório Educacional Aberto (REA)