Problema 2 Fabio Imada

retornar

Problema dos Filosofos

Introdução

Neste laboratório serão trabalhados conceitos de threads e semáforos.
Para tanto, será implementado o clássico Problema dos Filósofos em linguagem C, cujo o enunciado segue abaixo:

"Existem n filósofos ao redor de uma mesa redonda dispondo de n garfos, sendo que cada filosofo possue à sua frente 2 garfos, sendo garfo direito compartilhad com o filósofo à sua direita, e o esquerdo com o filósofo à sua esquerda.
Para comer o filósofo precisa pegar os dois garfos, caso contrário, irá aguardar até que os dois garfos à sua frente estejam disponíveis.
Vale notar que o filósofo apenas pensa e come."

Para implementar tal problema, cada filósofo foi tratado em uma thread sendo que todas as threads compartilham dados do estado de seu filósofo. Dessa forma, a utilização dos garfos foi abstraída para a regra, o filósofo só come se ninguém imediatamente ao seu lado estiver comendo.

Os semáforos foram utilizados para duas funções distintas:

  • Proteger o acesso à variável dos estados, evitando condições de corrida.
  • Promover a interação entre as threads, que dormem ao ver que o filósofo não pode comer e devem ser acordadas quando é possível comer.

Threads em C

Utilizando threads, podemos ter vários processamentos sendo executados simultâneamente. Isto é interessante principalmente quando o que está sendo processado em paralelo não possui dependência mútua e quando os processos em paralelo precisam interagir entre si, neste caso a interação deve ser feita com cuidado para evitar condições de corrida.

A programação multi-thread é possível através da utilização da biblioteca "pthread.h".
As threads são definidas pelo tipo pthread_t, devem ser inicializadas com uma função com pthread_create, voltam à thread principal com pthread_join quando a função em que foram inicializadas executa pthread_exit.
É possível ver mais detalhes na parte "Desenvolvimento", onde há um exemplo de utilização.

Semáforos em C

Semáforos são entidades de sincronização capazes de garantir que uma quantidade máxima determinada de processos acessem uma área simultaneamente.
Eles fazem tal proteção através dos comandos abaixo:

  • Down - O processo verifica o valor do semáforo
    • Se for zero, o processo dorme. Ao ser acordado, ele irá decrementar o valor do semáforo e entrar na área protegida;
    • Se for maior do que zero, o processo irá decrementar o valor do semáforo e entrará na área protegida.
  • Up - O processo incrementa o valor do semáforo e acorda os processos que estão aguardando.

A implementação dos semáforos em C é feita através da biblioteca "semaphore.h".
Os semáforos podem ser compartilhados pelas threads (no exemplo, eles são colocados como variáveis globais, compartilhados por todas as threads do programa) e são definidos pelo tipo sem_t, devem ser inicializados com sem_init (onde são carregados com seu valor inicial) e executam as funções de up e down com sem_post e sem_wait, respectivamente.

Desenvolvimento

O problema dos filósofos simula processos competindo por recursos escassos. Por isso, procurou-se uma solução que utilize-se tais recursos (garfos) ao máximo. Para tanto, os filósofos que desejam comer fazem uma transação para pegar os garfos: ou pegam os dois, ou não pegam nenhum. Desse modo, nenhum recurso fica semi-ocupado e, principalmente, evita-se os deadlocks. Isso também é muito mais eficiente do que permitir que, por exemplo, apenas um filósofo coma por vez.
Foi colocado um tempo de sleep para que o filosofo não executasse as atividades de pensar e comer imediatamente, caso contrário, observou-se que apenas o primeiro filósofo pensava e comia (e depois que limitou-se a quantidade de vezes que o ciclo repetia, um filósofo por vez terminava seu ciclo de vida: ser criado, pensar/comer n vezes, morrer).

Conteúdo do arquivo filosofos.c

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <semaphore.h>
 
#define N            5            // Número de filósofos
#define ESQUERDA    (i+N-1)%N
#define DIREITA     (i+1)%N
#define PENSANDO    0
#define ESPERANDO   1
#define COMENDO     2
 
int estado[N];
sem_t mutex;
sem_t s[N];
 
void imprime_estados(){
    int i;
    for(i = 0 ;  i < N ; i++){
        switch(estado[i]){
            case 0: printf("Pensando  "); break;
            case 1: printf("Esperando "); break;
            case 2: printf("Comendo   "); break;
        }
    }
    printf("\n");
}
 
void pensa(int i) {
    usleep(rand() % 1000000);
}
 
void come( i) {
    usleep(rand() % 1000000);
}
 
/* Verifica estado dos vizinhos. Se algum vizinho estiver comendo, nada pode fazer.
 * Caso contrário, começa a comer e entra na área protegida pelo semáforo binário
 * s[i]. */
void testa_vizinhos(int i) {
    if (estado[i] == ESPERANDO && estado[ESQUERDA] != COMENDO
            && estado[DIREITA] != COMENDO) {
        estado[i] = COMENDO;
        imprime_estados();
        sem_post(&s[i]);
    }
}
 
/* Tenta pegar garfos, porém verifica antes se os vizinhos estão utilizando os garfos.
 * Caso estejam, a thread irá dormir. Caso contrário, s[i] terá recebido um up() em
 * testa_vizinho() e não irá dormir. */
void pega_garfos(int i) {
    sem_wait(&mutex);
    estado[i] = ESPERANDO;
    imprime_estados();
    testa_vizinhos(i);
    sem_post(&mutex);
    sem_wait(&s[i]);
}
 
/* Filósofo termina de comer e volta a pensar. Antes disso, verifica se algum dos
 * vizinhos estava aguardando seu término e em caso positivo, acorda o tal vizinho(s). */
void baixa_garfos(int i) {
    sem_wait(&mutex);
    estado[i] = PENSANDO;
        imprime_estados();
    testa_vizinhos(ESQUERDA);
    testa_vizinhos(DIREITA);
    sem_post(&mutex);
}
 
/* Realiza o ciclo de vida do filósofo 100 vezes e então termina a thread. */
void filosofo(int i) {
    int n;
    printf("Iniciando filosofo %d\n", i);
    for (n = 0; n < 10; n++) {
        pensa(i);
        pega_garfos(i);
        come(i);
        baixa_garfos(i);
    }
    pthread_exit("--- Filosofo %d terminou ---\n");
}
 
int main() {
    int res, res_parc, i;
    pthread_t thread[N];
 
    /* Criando Semáforos */
    sem_init(&mutex, 0, 1);
 
    for (res = 0, i = 0; i < N; i++) {
        res_parc = sem_init(&s[0], 0, 1);
        res += res_parc;
    }
    if (res != 0) {
        perror("Erro em inicializacao de semaforos\n");
        exit(EXIT_FAILURE);
    }
    /* Criando filósofos e checando se foi tudo ok */
    for (res = 0, i = 0; i < N; i++) {
        res_parc = pthread_create(&thread[i], NULL, (void*) filosofo, (int*) i);
        res += res_parc;
    }
    if (res != 0) {
        perror("Erro em criacao de threads\n");
        exit(EXIT_FAILURE);
    }
    /* Juntando threads */
    for (res = 0, i = 0; i < N; i++) {
        res_parc = pthread_join(thread[i], NULL);
        res += res_parc;
    }
    if (res != 0) {
        perror("Erro em join threads\n");
        exit(EXIT_FAILURE);
    }
    exit(EXIT_SUCCESS);
}

Screenshots

A tela abaixo apresenta o comando para compilar o programa e sua execução.

filosofos.png

retornar

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License