Jantar dos Filósofos - Programação Paralela
Publicado por Uilian Ries (última atualização em 13/12/2012)
[ Hits: 43.556 ]
Homepage: https://uilianries.github.io
Download jantar_dos_filosofos.c
Um programa concorrente especifica dois ou mais processos concorrentes, onde cada um executa um programa sequencial.
Tais processos interagem por meio da comunicação, o que traz a necessidade de sincronização.
O problema de sincronização mais conhecido é o do "Jantar dos Filósofos". Ele foi proposto por Dijkstra (1965) como um problema clássico de sincronização e possui a seguinte situação:
1) Cinco filósofos estão sentados ao redor de uma mesa circular para o jantar.
2) Cada filósofo possui um prato para comer macarrão.
3) Os filósofos dispõem de hashis e e cada um precisa de 2 hashis para comer.
4) Entre cada par de pratos existe apenas um hashi: Hashis precisam ser compartilhados de forma sincronizada.
5) Os filósofos comem e pensam, alternadamente. Eles não se atém a apenas uma das tarefas.
6) Além disso, quando comem, pegam apenas um hashi por vez: Se conseguir pegar os dois come por alguns instantes e depois larga os hashis.
O problema é coordenar o uso dos hashi de maneira que nenhum filósofo fique com fome. Esse problema exemplifica muito bem muitas soluções e muitos problemas encontrados na programação concorrente. Pode facilmente ocorrer o deadlock se cada filósofo pegar o seu hashi da esquerda e se recusar a liberá-lo até ter comido. Pode ocorrer a inanição se dois filósofos conspirarem contra um terceiro.
Na solução dada abaixo, é livre de impasse e permite o máximo paralelismo a uma número arbitrário de filósofos. Ela usa um arranjo de estado para controlar se um filsofo está comendo, pensando ou faminto. Um filósofo só pode mudar comer se nenhum de seus vizinhos estiverem comendo.
O programa utiliza um arranjo de semáforos, um por filósofo, assim o filósofos famintos podem ser bloqueados se os garfos necessários estiverem ocupados.
Comando para compilar no GCC:
$ gcc -o jantar_dos_filosofos.o jantar_dos_filosofos.c -pthread
Bom estudo.
/****************************************************************************** * arquivo...: jantar_dos_filosofos.c * descriусo.: Um clássico da programação paralela, Dijkstra (1965) * * * autor.....: Uilian Ries <uilianries@gmail.com> * data......: 27/11/2012 * ********************************************************************************/ //-- INCLUDE -------------------------------------------------------------------- #include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> //-- CONSTANTES ----------------------------------------------------------------- #define QUANT (5) //Quantidade de filósofos #define ESQUERDA (id_filosofo + QUANT - 1) % QUANT //Id do filósofo a esquerda do id #define DIREITA (id_filosofo + 1) % QUANT //Id do filósofo a direita do id #define PENSANDO (0) //Id para estado pensado #define FAMINTO (1) //Id para estado de fome #define COMENDO (2) //Id para estado comendo //-- GLOBAL --------------------------------------------------------------------- int estado [QUANT]; //Estado dos filósofos pthread_mutex_t mutex; //Região crítica pthread_mutex_t mux_filo [QUANT]; //Mutex por filósofo pthread_t jantar[QUANT]; //Todos os filósofos //-- PROTOTIPAÇÃO --------------------------------------------------------------- void * filosofo ( void * param ); void pegar_hashi ( int id_filosofo ); void devolver_hashi ( int id_filosofo ); void intencao ( int id_filosofo ); void comer ( int id_filosofo ); void pensar ( int id_filosofo ); //------------------------------------------------------------------------------- /*! * @fn void * filosofo ( void * param ) * @brief Função que simula um filósofo * @param vparam id do filósofo */ void * filosofo ( void * vparam ) { int * id = (int *) (vparam); //Repassa o id do filósofo printf("Filosofo %d foi criado com sucesso\n", *(id) ); while ( 1 ) { pensar( *(id) ); //Aguarda o filósofo pensar pegar_hashi( *(id) ); //Filósofo pega os hashis comer( *(id) ); //Aguarda comer devolver_hashi( *(id) ); //Devolver os hashis pra mesa } pthread_exit( (void*) 0 ); //Legado do retorno } //------------------------------------------------------------------------------- /*! * @fn void pegar_hashi ( int id_filosofo ) * @brief Função que filósofo pega os hashis da mesa * @param id_filosofo id do filósofo */ void pegar_hashi ( int id_filosofo ) { pthread_mutex_lock( &(mutex) ); //Entra na regiсo crítica printf("Filosofo %d esta faminto\n", id_filosofo); estado[ id_filosofo ] = FAMINTO; //Altera o estado do filósofo intencao( id_filosofo ); //Intenção de pegar os hashis pthread_mutex_unlock( &(mutex) ); //Sai na região crítica pthread_mutex_lock( &(mux_filo[id_filosofo]) ); //Bloqueia os hashis } //------------------------------------------------------------------------------- /*! * @fn void devolver_hashi ( int id_filosofo ) * @brief Função que filósofo devolve os hashis para a mesa * @param id_filosofo id do filósofo */ void devolver_hashi ( int id_filosofo ) { pthread_mutex_lock ( &(mutex) ); //Entra na regiсo crítica printf("Filosofo %d esta pensando\n", id_filosofo); estado[ id_filosofo ] = PENSANDO; //Terminou de comer intencao( ESQUERDA ); //Vê se o vizinho da esquerda pode comer agora intencao( DIREITA ); //Vê se o vizinho da direita pode comer agora pthread_mutex_unlock ( &(mutex) ); //Sai da regiсo crítica } //------------------------------------------------------------------------------- /*! * @fn void intencao ( int id_filosofo ) * @brief Função que filósofo tem intenção de pegar os hashis para comer * @param id_filosofo id do filósofo */ void intencao ( int id_filosofo ) { printf("Filosofo %d esta com intencao de comer\n", id_filosofo); if( (estado[id_filosofo] == FAMINTO) && //Se o filósofo está come fome (estado[ESQUERDA] != COMENDO) && //Se o vizinho da esquerda não está comendo (estado[DIREITA] != COMENDO ) ) //Se o vizinho da direita nсo está comendo { printf("Filosofo %d ganhou a vez de comer\n", id_filosofo); estado[ id_filosofo ] = COMENDO; //Filósofo ganho a vez de comer pthread_mutex_unlock( &(mux_filo[id_filosofo]) ); //Libera os hashis } } //------------------------------------------------------------------------------- /*! * @fn void pensar ( int id_filosofo ) * @brief Função que filósofo fica pensando */ void pensar ( int id_filosofo ) { int r = (rand() % 10 + 1); printf("Filosofo %d pensa por %d segundos\n", id_filosofo, r ); sleep( r ); //Gasta um tempo em segundos } //------------------------------------------------------------------------------- /*! * @fn void comer ( int id_filosofo ) * @brief Função que filósofo fica comendo */ void comer ( int id_filosofo ) { int r = (rand() % 10 + 1); printf("Filosofo %d come por %d segundos\n", id_filosofo, r); sleep( r ); //Gasta um tempo em segundos } //------------------------------------------------------------------------------- int main ( void ) { int cont; //Contador auxiliar int status; //Criação da thread //Inicia os mutexes pthread_mutex_init( &(mutex), NULL); for( cont = 0 ; cont < QUANT ; cont++ ) { pthread_mutex_init( &(mux_filo[cont]), NULL ); } //Inicia threads (filósofos) for( cont = 0 ; cont < QUANT ; cont++ ) { //verifica se ocorreu erro status = pthread_create( &(jantar[cont]), NULL, filosofo, (void *) &(cont) ); if ( status ) { printf("Erro criando thread %d, retornou codigo %d\n", cont, status ); return EXIT_FAILURE; } } //Destroi antes de sair pthread_mutex_destroy( &(mutex) ); for( cont = 0 ; cont < QUANT ; cont++ ) { pthread_mutex_destroy( &(mux_filo[cont]) ); } pthread_exit( NULL ); return EXIT_SUCCESS; }
Tipos de Dados Abstrato - TDA - Números Complexos
Árvore de busca binária com frequência de consultas
Conversão de Decimal para Binário
Atenção a quem posta conteúdo de dicas, scripts e tal (6)
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
O mínimo que você precisa saber sobre o terminal (parte 2)
O mínimo que você precisa saber sobre o terminal (parte 1)
Como iniciar uma máquina virtual do VirtualBox automaticamente no boot do LUbuntu 18 LTS
Mudar o gerenciador de login (GDM para SDDM e vice-versa) - parte 2
Como deixar as abas do Firefox mais fininhas
Mudar o gerenciador de login (GDM para SDDM)
"Tentando" fazer com que programas rodem no Wayland e no X11
O que você está ouvindo agora? [2] (163)
Formatar NVM Express 1.3 de forma segura por completo (2)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta