Marcus Leandro Rosa Santos

Instituto Tecnológico de Aeronáltica
aluno: Marcus Leandro Rosa Santos
professor: Edgar Toshiro Yano
ano/sem: 2009/1o.
data:08/05/2009

Introdução

Nesse laboratório, temos como objetivo implementar problemas clássicos de sistema operacional usando semáforos, threads, mutex e processos no sistema operacional LINUX. Os problemas a serem implementados estão lsitados abaixo:

- Problema dos filósofos jantando
- Problema dos leitores e escritores
- Problema do barbeiro adormecido
- Problema do banheiro (Exercício 1 da 1ª prova de CES-33/ITA-2009)
- Problema das mensagens (Exercício 7 da 1ª prova de CES-33/ITA-2009)

Cabe salientar que para compilar o código em c no linux, utilizei o seguinte comando no terminal (consola):
gcc -lpthread -o codigo codigo.c

Desenvolvimento

Problema os filósofos jantando

jantar.JPG

Este problema se trata de cinco filósofos que podem comer ou pensar. A disposição dos garfos e pratos na mesa circular consiste de cinco pratos e cinco garfos, tendo sempre ao lado de cada prato dois garfos. 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, para cada filosofo foi utilizada 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]. O código que é a solução encontrada para o problema encontra-se escrito abaixo:

#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <semaphore.h>
#include <time.h>
 
#define TRUE 1
#define FALSE 0
#define N 5
#define LEFT (i+4)%N
#define RIGHT (i+1)%N    
#define THINKING 0
#define HUNGRY 1
#define EATING 2
 
typedef int semaphore;
int state[N];
sem_t mutex; // semaforo
sem_t s[N]; //semaforo
 
void * philosopher(void *);
void take_forks(int);
void put_forks(int);
void test(int);
 
int main(){
    int i;    
    pthread_t  filosofo[N];
    sem_init(&mutex,0,1); // inicializando o semaforo
    int filo[N];
    for(i=0 ; i<N ; i++) 
        sem_init(&s[i],0,0); // inicializando o semaforo
    for(i=0 ; i<N ; i++){
        filo[i] = i;
        pthread_create(&filosofo[i], NULL, philosopher,(void *) &filo[i]);
    }    
    pthread_join(filosofo[3],NULL); //faz o main esperar o thread1    
        exit(EXIT_SUCCESS);
    return 0;
}
 
void * philosopher(void *arg){
    int i = *(int *) arg;
    while(TRUE){
        printf("filosofo %d esta pensando\n",i); // think()
        srand(time(NULL));
        sleep(rand()%2+1); // espera 1 ou 2 segundos.
 
        take_forks(i);
        printf("filoso %d esta comendo\n",i); // eat()
        srand(time(NULL));
        sleep(rand()%2+1); // espera 1 ou 2 segundos.
 
        put_forks(i);
    }
}
 
void take_forks(int i){    
    sem_wait(&mutex); // down()
    state[i] = HUNGRY;
    test(i);
    sem_post(&mutex); // up()
    sem_wait(&s[i]); // down()
}
 
void put_forks(int i){
    sem_wait(&mutex); //down()
    state[i] = THINKING;    
    test(LEFT);
    test(RIGHT);
    sem_post(&mutex); //up()
}
 
void test(int i){
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){
        state[i] = EATING;
        sem_post(&s[i]);
    }
}

Abaixo segue o teste feito no console:

filosofos_teste.png

Problema dos leitores e escritores

Neste problema temos a seguinte condição: Os leitores podem acessar os dados de um banco de dados num determinado instante somente se nenhum escritor estiver utilizando o mesmo. Mais de um leitor pode ler o conteúdo do banco de uma vez, mas somente um escritor pode escrever no banco num dado instante. Quando um escritor está escrevendo, somente ele tem acesso ao banco, tendo tanto outros escritores como leitores que esperar este terminar a escrita para poderem acessar o banco. A implementação da resolução desse problema é ilustrada abaixo em código c. Cabe por fim ressaltar que a resolução desse problema requer a utilização de dois mutex, um para controlar o acesso ao banco de dados e outro para controlar operações em váriaveis que requerem disputa.

#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <semaphore.h>
#include <math.h>
 
#define TRUE 1
#define FALSE 0
 
sem_t mutex;
sem_t db;
int rc = 0;
 
void * reader(void *);
void * writer(void *);
 
int main(){
    pthread_mutex_init(&mutex,NULL);
    pthread_mutex_init(&db,NULL);
    // vetores para guardar o endereço de cada escritor, para passar na criação da thread.    
    int leitor[] = {1,2,3,4,5}; 
    int escritor[] = {1,2,3,4};
 
    pthread_t leitores[5];
    pthread_t escritores[4];
    int i;
    for(i = 0 ; i < 4 ; i++){
        pthread_create(&escritores[i],NULL,writer,(void *)&escritor[i]);
    }
    for(i = 0 ; i < 5; i++){
        pthread_create(&leitores[i],NULL,reader,(void *)&leitor[i]);
    }
    pthread_join(leitores[0],NULL);
    pthread_join(escritores[0],NULL);
    return 0;
}
 
void * reader(void *arg){
    int i = *(int *)arg;
    while(TRUE){
        pthread_mutex_lock(&mutex); // obtem acesso exclusivo ao rc
        rc = rc + 1; // mais um leitor agora
        if(rc == 1) pthread_mutex_lock(&db); // se este for o primeiro, obtem acesso exclusivo ao banco, para que enquanto tenha leitores não haja escritor.
        pthread_mutex_unlock(&mutex); // libera acesso exclusivo de rc
        printf("leitor %d: lendo o banco de dados.\n",i); //read_data_base()
        srand(time(NULL));
          sleep(rand()%2 + 1);
        pthread_mutex_lock(&mutex);
        rc = rc -1;
        if(rc == 0) pthread_mutex_unlock(&db);
        pthread_mutex_unlock(&mutex); // libera acesso ao rc
        printf("leitor %d: lido o banco.\n",i); // use_data_read()
        srand(time(NULL));
          sleep(rand()%2 + 1);
    }
}
 
void * writer(void *arg){
    int i = *(int *)arg;
    while(TRUE){
        printf("escritor %d: pensando no que escrever.\n",i); // think_up_data()
        srand(time(NULL));
         sleep(rand()%2 + 1);
        pthread_mutex_lock(&db); // obtem acesso exclusivo
        printf("escritor %d: escrevendo no banco.\n",i); //write_data_base()
        srand(time(NULL));
          sleep(rand()%2 + 1);
        pthread_mutex_unlock(&db); // libera acesso exclusivo
    }
}

A figura abaixo nos mostra o resultado do console.

leitor_escritor_teste.png

Problema do barbeiro adormecido

A descrição do problema da barbeari é a seguinte: Há um barbeiro numa barbearia com n cadeiras. Se não há nenhum cliente para ser atendido, o barbeiro senta sobre a sua cadeira e adormece. Se um cliente chega e o barbeiro está dormindo, este deve acordá-lo. Se outros clientes forem chegando, e o barbeiro estiver atendendo alguém, eles vão se sentando nas cadeiras disponíveis. Caso todas as cadeiras estejam ocupadas, os que estão excedendo vão embora. O desafio é programar o barbeiro e os clientes sem que eles caiam em condições de corrida.
O meu código que implementa este problema está descrito abaixo:

#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <semaphore.h>
#include <time.h>
 
#define CHAIRS 5
#define TRUE 1
#define FALSE 0
 
typedef int semaphore;
 
sem_t customers; //semaforo
sem_t barbers ; //semaforo
sem_t mutex ; //semaforo
int waiting = 0;
 
void * barber(void *);
void * customer(void *);    
 
int main(){
    sem_init(&customers,0,0); 
    sem_init(&barbers,0,0); // inicializando os semaforos.
    sem_init(&mutex,0,1);
 
    int Num_cliente = 1; // variavel para contar o número de cliente atendidos.
    pthread_t *clientes;
    pthread_t barbeiro;
 
    pthread_create(&barbeiro,NULL,barber,NULL); //inicializando a thread do barbeiro.
 
    while(TRUE){
        clientes = (pthread_t*) malloc(sizeof(pthread_t));
        pthread_create(clientes,NULL,customer,(void*)&Num_cliente);
        srand(time(NULL));
        sleep(rand()%2 + 1); // espera por 1 ou 2 segundos.        
        Num_cliente++;    
    }
    // O join nao eh necessario. Temos um loop infinito na main.
    return 0;
}
 
void * barber(void *arg){
    while(TRUE){
        sem_wait(&customers); // down() -> dorme se não tem cliente
        sem_wait(&mutex); // down() -> entra na região crítica
        waiting = waiting -1;
        sem_post(&barbers); // up() -> barbeiro, já cortou um cabelo e agora está disponível, assim ele acorda (chama da fila de espera) um cliente.
        sem_post(&mutex); // up() -> sai da região crítica.
        printf("cortei um cabelo!\n"); // cut_hair()
        srand(time(NULL));
        sleep(rand()%4 + 1); //espera por 1,2,3 ou 4 segundos            
    }
}
 
void * customer(void *arg){
    int i = *(int *)arg;
    sem_wait(&mutex);
    if(waiting < CHAIRS){
        waiting = waiting +1;
        printf("tamanho da fila: %d\n",waiting);
        sem_post(&customers); // acorda o barbeiro, se ele estiver dormindo
        sem_post(&mutex); // entra na região crítica
        sem_wait(&barbers); // dorme (espera) se o barbeiro não está disponível.
        printf("%dº cliente de cabelo cortado.\n",i); // get_haircut()
        srand(time(NULL));
        sleep(rand()%2 + 1); // espera 1 ou 2 segundos.
    }
    else
        sem_post(&mutex);
    pthread_exit(NULL);    
}

O teste do problema está disponível a seguir.

barbearia_teste.png

Problema do banheiro (Exercício 1 da 1ª prova de CES-33/ITA-2009)

As regras de uso de um banheiro permite que, quando uma mulher estiver no banheiro, outra mulher poderá entrar mas um homem não e vice-versa. Um sinal na porta indica em qual dos três estados o banheiro se encontra: Vazio, Com Mulher, Com Homem. Abaixo segue a implementação dos seguintes e procedimentos: Mulher_quer_entrar, Homem_quer_entrar, mulher_sai, mulher_entra, homem_sai, homem_entra.

Cabe mensionar que a resolução desse problema é muito similar a do problema dos leitores e escritores, com a diferença que só temos leitores, que no caso são os homens e as mulheres, o banco de dados seria análogo ao banheiro, nesse caso. Tendo isso como base segue abaixo a seguinte implementação para esse problema:

#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <semaphore.h>
#include <math.h>
 
#define VAZIO 0
#define Com_Mulher 1
#define Com_Homem 2
 
pthread_mutex_t mutex1;
pthread_mutex_t mutex2;  
pthread_mutex_t banheiro;
 
int num_Homem = 0; // numero de homens no banheiro.
int num_Mulher = 0; // numero de mulheres no banheiro.
 
void * Mulher_quer_entrar(void *);
void * Homem_quer_entrar(void *);
void mulher_entra(int);
void mulher_sai(int);
void homem_entra(int);
void homem_sai(int);
 
int main(){
    int i;
    pthread_mutex_init(&mutex1,NULL);
    pthread_mutex_init(&mutex2,NULL);
    pthread_mutex_init(&banheiro,NULL);
 
    int mulher[] = {1,2,3,4,5};
    int homem[] = {1,2,3,4,5};
 
    pthread_t homens[5];
    pthread_t mulheres[5];
 
    for(i = 0 ; i < 5 ; i++){
        pthread_create(&homens[i],NULL,Homem_quer_entrar, (void *) &homem[i]);
        pthread_create(&mulheres[i],NULL,Mulher_quer_entrar, (void *) &mulher[i]);
    }
 
    for(i = 0 ; i < 5 ; i++){
        pthread_join(homens[i],NULL);
        pthread_join(mulheres[i],NULL);
    }
 
    return 0;
}
 
void * Mulher_quer_entrar(void *arg){
    int i = *(int *)arg;            
 
        pthread_mutex_lock(&mutex1);
        num_Mulher++;
        if(num_Mulher == 1) pthread_mutex_lock(&banheiro);
        pthread_mutex_unlock(&mutex1);
        mulher_entra(i); 
        printf("mulher %d esta dentro do banheiro.\n",i);
        pthread_mutex_lock(&mutex1);
        num_Mulher--;
        mulher_sai(i); 
        if(num_Mulher == 0) pthread_mutex_unlock(&banheiro);
        pthread_mutex_unlock(&mutex1);
        pthread_exit(NULL);    
 
}
 
void * Homem_quer_entrar(void *arg){
    int i = *(int *)arg;        
 
        pthread_mutex_lock(&mutex2);
        num_Homem++;
        if(num_Homem == 1) pthread_mutex_lock(&banheiro);
        pthread_mutex_unlock(&mutex2);
        homem_entra(i);
        printf("homem %d esta dentro do banheiro.\n",i);
        pthread_mutex_lock(&mutex2);
        num_Homem--;
        homem_sai(i); 
        if(num_Homem == 0) pthread_mutex_unlock(&banheiro);
        pthread_mutex_unlock(&mutex2);
        pthread_exit(NULL);    
 
}
 
void mulher_entra(int i){
    printf("mullher %d entrou no banheiro.\n",i);
    srand(time(NULL));
    sleep(rand()%2+1);
}
 
void mulher_sai(int i){
    printf("mulher %d saiu do banheiro.\n",i);
    srand(time(NULL));
    sleep(rand()%3+1);
}
 
void homem_entra(int i){
    printf("homem %d entrou no banheiro.\n",i);
    srand(time(NULL));
    sleep(rand()%3+1);
}
 
void homem_sai(int i){
    printf("homem %d saiu do banheiro.\n",i);
    srand(time(NULL));
    sleep(rand()%2+1);
}

Abaixo segue a execução no console.

provaQ1_teste.png

Problema das mensagens (Exercício 7 da 1ª prova de CES-33/ITA-2009)

Este problema se consiste em implementar as operações send() e recieve() utilizando semaforos.

Com uma apurada visão, é fácil perceber que esse problema é análogo ao dos produtores e consumidores, onde o produtor seria o send e o recepetor seria o recieve, sendo assim, torna fácil a implementação dessas operações, considerenado que o algoritmo é conhecido. Abaixo segue o código em c seguido de teste no console do linux.

#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <semaphore.h>
#include <math.h>
 
#define TRUE 1
#define FALSE 0
#define N 100
 
typedef int mensagem;
sem_t mutex;
sem_t empty;
sem_t full;
 
int buffer[N];
int posicao = 0; //variável para guardar o índice do último elemento do buffer.
 
void * send(void *);
void * recieve(void *);
 
int main(){
    sem_init(&mutex,0,1);
    sem_init(&empty,0,N);
    sem_init(&full,0,0);    
 
    pthread_t sender;
    pthread_t reciever;
 
    pthread_create(&sender,NULL,send,(void *)NULL);
    pthread_create(&reciever,NULL,recieve,(void *)NULL);
 
    pthread_join(reciever,NULL);
    pthread_join(sender,NULL);    
}
 
void * send(void *arg){
    while(1){        
        srand(time(NULL));
        int mensagem = rand()%10; //mensagem eh um int
 
        sem_wait(&empty);
        sem_wait(&mutex);
 
        buffer[(posicao % N)] = mensagem; // coloca mensagem no buffer
        printf("mensagem: %d colocada no buffer.\n",mensagem);                
        posicao++;
        sleep(rand()%2+1);
        sem_post(&mutex);
        sem_post(&full);            
    }
}
 
void * recieve(void *arg){
    while(1){        
        int retorno;
 
        sem_wait(&full);
        sem_wait(&mutex);
 
        retorno = buffer[(posicao % N)];                
        posicao--; // remove mensagem do buffer.
 
        sem_post(&mutex);
        sem_post(&empty);
        printf("mensagem recebida.\n");    
        srand(time(NULL));
        sleep(rand()%2+1);        
    }
}

teste:

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