Jantar dos Filósofos - Programação Paralela
Publicado por Uilian Ries (última atualização em 13/12/2012)
[ Hits: 43.699 ]
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; }
Converter arquivos Bitmap para ASCII-art
Método de Newton Modificado p/ Raízes Multiplas
Compartilhando a tela do Computador no Celular via Deskreen
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
Como renomear arquivos de letras maiúsculas para minúsculas
Imprimindo no formato livreto no Linux
Vim - incrementando números em substituição
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Não to conseguindo resolver este problemas ao instalar o playonelinux (1)
Excluir banco de dados no xampp (1)
[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