Bruno

Laboratório de CES-33

Instituto Tecnológico de Aeronáutica

Professor: Edgar Toshiro Yano
Aluno: Bruno César Alves
Data: 08/05/2009

Objetivo:

Este laboratório tem o intuito de explorar o uso de semáforos, threads, mutex e processos no sistema operacional LINUX. Para tanto, foram desenvolvidas algumas aplicações em liguagem c da solução de alguns problemas típicos:
- Problema dos produtores e consumidores usando pipe
- Problema dos filósofos jantando
- Problema dos leitores e escritores
- Problema do barbeiro adormecido
- Problema do banheiro (Ex1 - Prova de CES-33 / ITA-2009)
- Problema das mensagens (Ex7 - Prova de CES-33 / ITA-2009)
Para a execução das aplicação, foi utilizado o gcc no terminal do LINUX.

Soluções:

Problema dos produtores e consumidores usando pipe

O problema dos produtores e consumidores trata do envio e recepção de dados a partir de um buffer. Para a solução desse problemas foi criada uma aplicação que utiliza pipes que comunicam processos criados com fork().

Segue o código da aplicação que soluciona o problema para varios produtores e receptores:

#include <stdio.h>
#include <string.h>
#define READ          0             //indice de leitura da saida do pipe
#define WRITE        1             //indice de escrita da entrada do pipe
#define PRODUTORES   15             //define numero de produtores
#define LEITORES     8            //define numero de leitores
 
char mensagem[] = "Hello World";
int main ()
{
    int fd [2],i,j;
    pipe (fd);
    if (fork () == 0) 
    {
        for(i=0;i<PRODUTORES;i++)
        {
            close(fd[READ]); /* Close unused end */
            write (fd[WRITE],mensagem, strlen (mensagem) + 1); /* include NULL*/
            printf("Enviei uma mensagem para meu processo pai\n");
            close (fd[WRITE]); /* Close used end*/
            sleep(1);
        }
    }
    else
    {
        for(j=0;j<LEITORES;j++){
            char message[15];
            close (fd[WRITE]); /* Close unused end */
            read (fd[READ], message, 15);
            printf("Recebi essa mensagem de meu filho: %s\n",message);
            close (fd[READ]); /* Close used end */ 
            sleep(2);
        }
    }
    return 0;
}

A execução da aplicação gerou o seguinte resultado:

pipe

Problema dos filósofos jantando

Philosphers.jpg

O primeiro problema trata de cinco filósofos que podem comer ou pensar, porém, de acordo com a disposição dos garfos e pratos na figura acima, um filósofo só pode se alimentar quando seus vizinhos não estão comendo. O problema principal, na computação, é a questão da disputa entre filósofos diferentes na tentativa de pegar o mesmo garfo.
O codigo abaixo mostra a solução do problema, para a implementação da solução, cada filosofo foi tratado como uma thread e os acessos aos pratos foram controlados por semáforos. O semáforo mutex é usado para criar exclusão mutua de forma que os filosofos não verifiquem a possibilidade de comer ao mesmo tempo, já o semáforo s[i], é utilizado para a exclusão mutua da variável state[i].

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <semaphore.h>
#include <pthread.h>
#include <time.h>

#define N          5                  // numero de filósofos
#define LEFT      (i+4)%N             // número do filósofo a esquerda
#define RIGHT     (i+1)%N             // número do filósofo a direita
#define THINKING   0                  // filosofo pensando
#define HUNGRY     1                  // filosofo tentando pegar os garfos
#define EATING     2                  // filosofo comendo
#define TRUE       1                  // booleano verdadeiro
#define FALSE      0                  // booleano falso

int state[N];                         // vetor com os estados dos filosofos
sem_t mutex;                          // semaforo principal 
sem_t s[N];                // semaforo individual

void *thread_function (void *arg);      // função executada na chamada do thread
void filosofo(int i);            // ação do filósofo
void pega_garfos(int i);        // tentativa de pegar garfos do filósofo i
void solta_garfos(int i);        // filosofo i para de comer
void testa(int i);            // filosofo i pega os garfos de for possível
void pensa(int i);            // filosofo i pensa
void come(int i);            // filosofo i come
void imprime();                // imprime status dos filósofos

int main()
{
    int i,j,k, res;
    void * thread_result;
    pthread_t threads[N];
    printf("| FILOSOFO  1 | FILOSOFO  2 | FILOSOFO  3 | FILOSOFO  4 | FILOSOFO  5 |\n");
    //inicialização de semaforos
    if(sem_init(&mutex,0,1) != 0)
    {
        perror("Problema ao inicializar semaforo principal.\n");
        exit(EXIT_FAILURE);
    }
    for(i = 0; i<N ; i++)
    {
        if(sem_init(&s[i],0,0) != 0)
        {    
            perror("Problema ao inicializar semaforo individual.\n");
            exit(EXIT_FAILURE);
        }
    }
    //inicialização das threads
    for(j = 0; j<N ; j++)
    {
        k = j;
        if(pthread_create(threads+i,NULL,thread_function, (void *)&k) != 0)
        {
            perror("Problema ao inicializar thread.\n");
            exit(EXIT_FAILURE);
        }
    }
    sleep(1);
    //espera da função main pelas threads
        if(pthread_join(threads[0],&thread_result) !=0 )
        {
              perror("thread join failed");
               exit(EXIT_FAILURE);
        }
    return 0;
}
void *thread_function (void *arg)
{
filosofo(*(int *) arg);
pthread_exit(NULL);
}
void filosofo(int i)
{
    while(TRUE)
    {
        sleep(0.5f);
        pensa(i);
        pega_garfos(i);
        come(i);
        solta_garfos(i);
    }
}
void pega_garfos(int i)
{
    sem_wait(&mutex);          //entra na região crítica para testar
    state[i] = HUNGRY;
    testa(i);
    sem_post(&mutex);        //sai da região crítica para testar
    sem_wait(&s[i]);         //entra na região crítica para a variável  state
}
void solta_garfos(int i)
{
    sem_wait(&mutex);        //entra na região crítica para testar
    state[i]=THINKING;
    testa(LEFT);
    testa(RIGHT);
    sem_post(&mutex);        //sai da região crítica para testar
}
void pensa(int i)
{
        srand ( time(NULL) );
        sleep(rand()%2 + 1);
}
void come(int i)    
{
        srand ( time(NULL) );
        sleep(rand()%2 + 1);
}
void testa(int i)
{
    if(state[i] == HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING)
    {
        state[i] = EATING;    
        sem_post(&s[i]);    //sai da região crítica para a variável state
            imprime();
    }
}
void imprime()
{
    int l;
    for (l = 0; l < 5; l++)
    {
        if(state[l]==0) printf("|   pensando  ");
        if(state[l]==1) printf("|   faminto   ");
        if(state[l]==2) printf("|   COMENDO   ");
    }
    printf("|\n");
}

Na execução da aplicação pode-se observar que em nenhum momento filosofos vizinhos comem ao mesmo tempo:

filosofos

Problema dos leitores e escritores

Este problema trata de leitores e escritores que acessam algum tipo de dado. Este dado não pode ser lido e escrito ao mesmo tempo, sua leitura pode ser feita por vários leitores, porém somente um escritor pode acessar os dados ao mesmo tempo.
Foi criada uma aplicação que abstrai a tentativa de acesso a um banco de dados.

Segue o código fonte produzido:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <semaphore.h>
#include <pthread.h>
#include <time.h>
 
#define ESCRITORES    3
#define LEITORES      5
#define TRUE          1
#define FALSE          0
 
int escritores[] = {1, 2, 3};        //escritores
int leitores[] = {1, 2, 3, 4, 5};    //leitores
pthread_mutex_t mutex;            //semaforo que cria exclusão mutua para a variavel rc
sem_t db;                //semaforo que cria exclusão mutua para o acesso ao banco de dados
int rc = 0;                //armazena o numero de leitores no banco de dados
void *reader(void *arg);         //função do thread de um leitor    
void *writer(void *arg);        //função do thread de um escritor
void think_up_data(int id);        //criaçao de dado
void write_data_base(int id);        //inserção de dado
void read_data_base(int id);        //leitura de dado
void use_data_read(int id);        // uso de dado
 
int main()
{
    void * thread_result;
    pthread_t *threads;
    int i;
 
    if(sem_init(&db,0,1) != 0)
    {
        perror("Problema ao inicializar o semaforo do bando de dados.\n");
        exit(EXIT_FAILURE);
    }
 
    if(pthread_mutex_init(&mutex,NULL) != 0)
    {
        perror("Problema ao inicializar mutex.\n");
        exit(EXIT_FAILURE);
    }
 
    for(i=0;i<ESCRITORES;i++){
        srand(time(NULL));
            sleep(rand()%2 + 1);    
        threads = (pthread_t*) malloc(sizeof(pthread_t));
        if(pthread_create(threads,NULL,writer, (void *)(escritores+i)) != 0)
        {
            perror("Problema ao inicializar thread de escritor.\n");
            exit(EXIT_FAILURE);
        }
    }
    for(i=0;i<LEITORES;i++){    
        srand(time(NULL));
            sleep(rand()%2 + 1);
        threads = (pthread_t*) malloc(sizeof(pthread_t));
        if(pthread_create(threads,NULL,reader, (void *)(leitores+i)) != 0)
        {
            perror("Problema ao inicializar thread de leitor.\n");
            exit(EXIT_FAILURE);
        }
    }
        if(pthread_join(threads[0],&thread_result) !=0 )
        {
              perror("thread join failed");
               exit(EXIT_FAILURE);
        }
    return 0;
}
void *reader(void *arg)
{
    while(TRUE)
    {
        pthread_mutex_lock(&mutex);
        rc = rc + 1;
        if(rc == 1) sem_wait(&db);
        pthread_mutex_unlock(&mutex);        
        read_data_base(*(int *) arg);
        pthread_mutex_lock(&mutex);
        rc = rc - 1;
        if(rc == 0) sem_post(&db);
        pthread_mutex_unlock(&mutex);
        use_data_read(*(int *) arg);
    }
}
void *writer(void *arg)
{
    while(TRUE)
    {
        think_up_data(*(int *) arg);
        sem_wait(&db);
        write_data_base(*(int *) arg);
        sem_post(&db);
    }
}
void think_up_data(int id)
{
    srand(time(NULL));
    sleep(rand()%2 + 1);    
}
void write_data_base(int id)
{
    printf("Escritor %d escrevendo dado...\n",id);
    srand(time(NULL));
    sleep(rand()%2 + 1);    
    printf("Escritor %d termina de escrever...\n",id);
}
void read_data_base(int id)
{
    printf("Leitor %d lendo dado...\n",id);
    srand(time(NULL));
    sleep(rand()%2 + 1);    
}
void use_data_read(int id)
{
    srand(time(NULL));
    sleep(rand()%2 + 1);    
}

A solução satizfaz os requisitos do problema:

leitor_escritor

Problema do barbeiro adormecido

Alguns barbeiros desejam fazer cortes de cabelo. Sabendo que clientes chegam a todo momento, a solução deste problema deve permitir que os clientes sejam atendidos de forma organizada.
Segue o código da aplicação que realiza os cortes de cabelo:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <semaphore.h>
#include <pthread.h>
#include <time.h>
 
#define BARBERS      3
#define CADEIRAS     5
#define VERDADEIRO   1
#define FALSO        0
 
int barbeiros[] = {1, 2, 3};            //barbeiro
sem_t costumers;                          //semaforo que controla os clientes
sem_t barbers;                          //semaforo que controla os barbeiros
sem_t mutex;                              //semaforo que cria exclusão mutua
int esperando = 0;                //variavel que armazena a quantidade de clientes esperando
 
void *barber (void *arg);            //função da thread do barbeiro
void *costumer (void *arg);            //função da thread do cliente
void ganha_corte();                //função que realiza o corte
void corta_cabelo(int barbeiro);        //função que exprime a satifação do cliente em ter o cabelo cortado
 
int main()
{
    void * thread_result;
    pthread_t *threads;
    int i;
 
    if(sem_init(&mutex,0,1) != 0)
    {
        perror("Problema ao inicializar o semaforo mutex.\n");
        exit(EXIT_FAILURE);
    }
    if(sem_init(&barbers,0,0) != 0)
    {
        perror("Problema ao inicializar semaforo barbers.\n");
        exit(EXIT_FAILURE);
    }
    if(sem_init(&costumers,0,0) != 0)
    {
        perror("Problema ao inicializar semaforo costumers.\n");
        exit(EXIT_FAILURE);
    }
 
    for(i=0;i<BARBERS;i++){    
        threads = (pthread_t*) malloc(sizeof(pthread_t));
        if(pthread_create(threads,NULL,barber, (void *)(barbeiros+i)) != 0)
        {
            perror("Problema ao inicializar thread barbers.\n");
            exit(EXIT_FAILURE);
        }
    }
    while(VERDADEIRO)
    {
        srand(time(NULL));
            sleep(rand()%2 + 1);
        threads = (pthread_t*) malloc(sizeof(pthread_t));
        if(pthread_create(threads,NULL,costumer, NULL) != 0)
        {
            perror("Problema ao inicializar thread costumers.\n");
            exit(EXIT_FAILURE);
        }
    }
    return 0;
}
 
void *barber (void *arg)
{
    while(VERDADEIRO)
    {
        sem_wait(&costumers);
        sem_wait(&mutex);
        esperando = esperando - 1;
        sem_post(&barbers);
        sem_post(&mutex);
        corta_cabelo(*(int *) arg);
        srand(time(NULL));
            sleep(rand()%(*(int *) arg));
    }
}
 
void *costumer (void *arg)
{
    sem_wait(&mutex);
    if(esperando<CADEIRAS)
    {
        esperando = esperando + 1;
        sem_post(&costumers);
        sem_post(&mutex);
        sem_wait(&barbers);
        ganha_corte();
    }else
    {
        sem_post(&mutex);
    }
pthread_exit(NULL);
}
void corta_cabelo(int barbeiro)
{
    printf("Barbeiro %d: Cortei um cabelo\n",barbeiro);
}
void ganha_corte()
{
    printf("Cliente: Ganhei um corte de cabelo\n");
}

Foi obtido o seguinte resultado durante a execução:

barbeiro

Problema do banheiro

Em um banheiro é proibida a entrada de homens e mulheres ao mesmo tempo. Considerando que as mulheres e homens são vistos como threads pela aplicação, a entrada no banheiro foi controlada por semáforos.

Segue o código fonte da aplicação:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <semaphore.h>
#include <pthread.h>
#include <time.h>
 
#define TRUE          1
#define FALSE          0
 
pthread_mutex_t mutex_h;                //controla acesso a variavel mulher
pthread_mutex_t mutex_m;                //controla acesso a variavel homem    
sem_t banheiro;                        //controla acesso ao banheiro
int com_homem = 0;                    //armazena quantidade de homens no banheiro
int com_mulher = 0;                    //armazena quantidade de mulheres no banheiro    
int vazio = 0;                        //indica que o banheiro esta vazio
int k=0;                        //usado pra criação de threads
 
void homem_quer_entrar(int id);                //função executada quando homem tenta entrar
void homem_sai(int id);                    //função executada quando homem sai
void mulher_quer_entrar(int id);            //função executada quando mulher tenta entrar
void mulher_sai(int id);                //função executada quando mulher sai
void *thread_homem_function(void *arg);            //função da thread do homem
void *thread_mulher_function(void *arg);        //função da thread do mulher
 
int main()
{
    int j=0;
    void * thread_result;
    pthread_t *threads_h;
    pthread_t *threads_m;
    //inicialização dos semáforos
    if(sem_init(&banheiro,0,1) != 0)
    {
        perror("Problema ao inicializar o semaforo do banheiro.\n");
        exit(EXIT_FAILURE);
    }
 
    if(pthread_mutex_init(&mutex_h,NULL) != 0)
    {
        perror("Problema ao inicializar mutex.\n");
        exit(EXIT_FAILURE);
    }
    if(pthread_mutex_init(&mutex_m,NULL) != 0)
    {
        perror("Problema ao inicializar mutex.\n");
        exit(EXIT_FAILURE);
    }
    //geração de threads
    while(1)
    {
        k++;
        threads_m = (pthread_t*) malloc(sizeof(pthread_t));
        if(pthread_create(threads_m,NULL,thread_mulher_function, (void *)&k) != 0)
        {
            perror("Problema ao inicializar thread de mulher.\n");
            exit(EXIT_FAILURE);
        }
 
        threads_h = (pthread_t*) malloc(sizeof(pthread_t));
        if(pthread_create(threads_h,NULL,thread_homem_function, (void *)&k) != 0)
        {
            perror("Problema ao inicializar thread de homem.\n");
            exit(EXIT_FAILURE);
        }
        sleep(1);
    }
        if(pthread_join(threads_h[0],&thread_result) !=0 )
        {
              perror("thread join failed");
               exit(EXIT_FAILURE);
        }
    return 0;
}
void homem_quer_entrar(int id)
{
    srand(time(NULL));
    sleep(rand()%2 + 2);
    pthread_mutex_lock(&mutex_h);
    com_homem = com_homem + 1;
    if(com_homem == 1) sem_wait(&banheiro);
    printf("Homem entrou\n");
    pthread_mutex_unlock(&mutex_h);    
}
void homem_sai(int id)
{
    pthread_mutex_lock(&mutex_h);
    com_homem = com_homem - 1;
    if(com_homem == 0) sem_post(&banheiro);
    printf("Homem saiu\n");
    pthread_mutex_unlock(&mutex_h);
}
void mulher_quer_entrar(int id)
{
    srand(time(NULL));
    sleep(rand()%2 + 2);
    pthread_mutex_lock(&mutex_m);
    com_mulher = com_mulher + 1;
    if(com_mulher == 1) sem_wait(&banheiro);
    printf("Mulher entrou\n");
    pthread_mutex_unlock(&mutex_m);        
}
void mulher_sai(int id)
{
    pthread_mutex_lock(&mutex_m);
    com_mulher = com_mulher - 1;
    if(com_mulher == 0) sem_post(&banheiro);
    printf("Mulher saiu\n");
    pthread_mutex_unlock(&mutex_m);
}
 
void *thread_homem_function(void *arg)
{
    homem_quer_entrar(*(int*)arg);
    srand(time(NULL));
    sleep(rand()%2 + 1);
    homem_sai(*(int*)arg);
    pthread_exit(NULL);
}
void *thread_mulher_function(void *arg)
{
    mulher_quer_entrar(*(int*)arg);
    srand(time(NULL));
    sleep(rand()%2 + 1);    
    mulher_sai(*(int*)arg);
    pthread_exit(NULL);
}

Na execução da solução apresentada foi obtido o seguinte resultado:

Problema das mensagens

Neste problema, mensagens pre-determinadas são enviadas de uma pessoa para a outra (como as usadas em alguns celulares). Esse problema é análogo ao primeiro problema resolvido com o uso de pipes, porém, desta vez, a solução foi feita usando semáforos e substituido o buffer por um vetor chamado correio.

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <semaphore.h>
#include <pthread.h>
#include <time.h>
#include <string.h>
 
#define N          100            //tamanho da caiza de correio
#define TRUE       1            
#define FALSE      0
#define M        6            // numero de mensagens
 
pthread_mutex_t mutex;            //protege caixa de correio
sem_t empty;                //protege retirada de caixa de correio vazia
sem_t full;                //protege colocada na caixa de correio cheia
char* mensagens[20] = { "Olá" , "Tchau" , "Feliz Aniversário" , "Desculpa" , "Tenha um bom dia" , "Estou com saudades"};
int correio[N];
int inicio = 0;                //inicio da fila no vetor correio
int fim = 0;                //fim da fila no vetor correio
 
int cria_mensagem();            //cria uma mensagem
void send(int mensagem);        //envia uma mensagem
int receive();                //recebe uma mensagem
void usa_mensagem(int mensagem);    //usa uma mensagem
void *recebe_mensagem(void* arg);       //função da thread que recebe mensagem
void *envia_mensagem(void* arg);    //função da thread que envia mensagem
 
int main()
{
    int j=0;
    void * thread_result;
    pthread_t *threads_envia;
    pthread_t *threads_recebe;
    if(pthread_mutex_init(&mutex,NULL) != 0)
    {
        perror("Problema ao inicializar mutex.\n");
        exit(EXIT_FAILURE);
    }
    if(sem_init(&full,0,0) != 0)
    {
        perror("Problema ao inicializar o semaforo full.\n");
        exit(EXIT_FAILURE);
    }
    if(sem_init(&empty,0,N) != 0)
    {
        perror("Problema ao inicializar o semaforo empty.\n");
        exit(EXIT_FAILURE);
    }
    threads_envia = (pthread_t*) malloc(sizeof(pthread_t));
    if(pthread_create(threads_envia,NULL,envia_mensagem, NULL) != 0)
    {
        perror("Problema ao inicializar thread que envia mensagem.\n");
        exit(EXIT_FAILURE);
    }
    threads_recebe = (pthread_t*) malloc(sizeof(pthread_t));
    if(pthread_create(threads_recebe,NULL,recebe_mensagem, NULL) != 0)
    {
        perror("Problema ao inicializar thread que recebe mensagem.\n");
        exit(EXIT_FAILURE);
    }
        if(pthread_join(threads_recebe[0],&thread_result) !=0 )
        {
              perror("thread join failed");
               exit(EXIT_FAILURE);
        }
    return 0;
}
void *envia_mensagem(void* arg)
{
    while(1)
    {
    int mensagem;
    mensagem = cria_mensagem();
    sem_wait(&empty);
    pthread_mutex_lock(&mutex);
    send(mensagem);
    pthread_mutex_unlock(&mutex);
    srand(time(NULL));
    sleep(rand()%2 + 1);
    sem_post(&full);
    }
}
void *recebe_mensagem(void* arg)
{
    int mensagem;
    while(1)
    {
    int mensagem;    
    sem_wait(&full);
    pthread_mutex_lock(&mutex);
    mensagem = receive();
    pthread_mutex_unlock(&mutex);
    srand(time(NULL));
    sleep(rand()%2 + 1);
    sem_post(&empty);
    usa_mensagem(mensagem);
    }
}
int cria_mensagem()
{
    int mensagem;
    srand(time(NULL));
    mensagem = rand()%M;
    printf("Mensagem criada: %s\n", mensagens[mensagem]);
    return mensagem;
}
void send(int mensagem)
{
    correio[fim] = mensagem;
    fim = (fim + 1)%N;    
}
int receive()
{
    int mensagem;
    mensagem = correio[inicio];
    inicio = (inicio + 1)%N;
    return mensagem;
}
void usa_mensagem(int mensagem)
{
    printf("Mensagem recebida: %s\n",mensagens[mensagem]);
}

Segue o resultado obtido:

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