Questão 7 Prova 1 2009

ENUNCIADO

Implementar as primitivas send e receive utilizando semáforos.

INTRODUÇÃO

Semáforos só funcionam porque há memória compartilhada entre os processos. Mesmo em sistemas com múltiplas CPUs, uma instrução TSL pode proteger o semáforo.
Monitores são restritos porque nem todas as linguagens implementam esse recurso.
Como fazer em SDs (Sistemas distribuidos), onde a memória dos sistemas é distribuída (cada um possui a sua, sem comunicação entre elas)?
A solução é o uso de passagem de mensagens.Esse método usa duas funções, send e receive. Essas funções podem ser implementadas em bibliotecas, portanto podem ser acrescentadas a qualquer linguagem sem problemas.

Send(destino, $msg) envia uma msg para um destino qualquer.
Receive(fonte, &msg) recebe uma mensagem de fonte (pode ser qualquer uma)

Há alguns problemas aqui que não existem nos outros métodos.
Como as msgs são enviadas via rede, podem ser extraviadas. Isso exige confirmações (acknowledgements), estabelecimentos de relógios para timeouts e retransmissões.
Como um ack pode ser extraviado, uma msgs pode ser enviada duas vezes. Isso exige também o uso de sequências para evitar duplicidade.
Esse método exige um sistema de identificação dos processos, de forma que send e receive sejam não ambíguos.
Dependendo do motivo da comunicação, pode-se exigir autenticação das partes envolvidas
O receive pode ser bloqueante (se não houver msgs prontas para o processo, ele bloqueia (comunicação síncrona).
Também é possível devolver um código de erro. Assim, o processo não fica bloqueado (comunicação assíncrona).

IMPLEMENTACÃO

Para implementar as primitivas send e receive, não levou-se em consideracão o tratamento da duplicidade, visto que, para testar o codigo, foi usado o o problema do produtor e consumidor com mensagens em uma mesma maquina.

O problema do produtor e consumidor com mensagens

#define N 100 /* número de posições no buffer */
#define MSIZE 4 /* tamanho da mensagem */
typedef int message[MSIZE];
void producer(void)
{
int item;
message m; /* buffer de mensagem */
while (TRUE)
{
produce_item(&item); /* gera algo para ser colocado no buffer */
receive(consumer, &m); /* aguarda a chegada de mensagem vazia */
build_message (&m, item); /* constroi uma mensagem para enviar */
send (consumer, &m); /* envia um item ao consumidor */
}
}
void consumer(void)
{
int item, i;
message m;
for (i = 0; i < N; i++) send (producer, &m); /* envia N mensagens vazias */
while (TRUE)
{
receive (producer, &m); /* recebe mensagem contendo um item*/
extract_item(&m, &item); /* retira item da mensagem */
send (producer, &m); /* envia de volta resposta com mensagem vazia */
consumer_item(item); /* faz algo com o item recebido */
}
}

Nessa solução, o consumidor envia ao produtor N msgs vazias. Sempre que o produtor produzir um item, usa uma das msgs vazias para enviá-lo ao consumidor.

Uma solução para o sistema de passagem de msgs é o uso de caixas. Uma caixa postal é um buffer que pode receber um certo número de mensagens. As funções de send e receive endereçam as caixas postais (não os processos). Um processo precisa ter direito para acessar uma caixa postal.
Se a caixa postal estiver cheia, o send de um processo bloqueia. Da mesma forma, se estiver vazia o receive de um processo bloqueia.

Outra forma de implementar send e receive é sem buffer. Nesse caso, a transferência entre as duas funções é direta. Assim, para que um processo chame send o outro deve estar em receive. Se não, o processo bloqueia até que o seu par feche a comunicação. Também chamado de rendezvous.

Utilizei a primeira solucão.

/* ***********************************************************
Implementação da solução do problema produtor e consumidor
utilizando troca de mensagens com send e receive
 
O programa recebe 2 parametro:
 - primeiro corresponde ao número de produres para gerar
 - segundo corresponde ao número de consumidores para gerar 
 
Tiago Porto, Maio 2009
 
*********************************************************** */
 
#include <semaphore.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
 
#define FALSE 0
#define TRUE 1
#define PRODUCER 0
#define CONSUMER 1
 
void *producer(void *arg);
void *consumer(void *arg);
void send(int ident, char *m);
void receive(int ident, char *m);
 
/* Definicão dos semaforos */
sem_t mutex, full_p, empty_p, full_c, empty_c;
 
/* Definicao das caixas de postais */
char producer_mailbox[1000], consumer_mailbox[1000];
 
main(int argc, char* argv[]) {
    int n_producer, n_consumer, max_producer, max_consumer, i;
    pthread_t producer_thread[100], consumer_thread[100];
 
    /* Inicializacao dos semaforos */
    sem_init(&mutex, 0, 1);
    sem_init(&full_p, 0, 10);
    sem_init(&empty_p, 0, 0);
    sem_init(&full_c, 0, 0);
    sem_init(&empty_c, 0, 10);
 
    /* Inicializacao das caixas postais */
    for(i=0; i<10; i++)    
        strcpy(producer_mailbox, "    ");
     strcpy(consumer_mailbox, "");
 
    max_producer=atoi(argv[1]);
    max_consumer=atoi(argv[2]);
 
    /* Criando os threads produtoras */
    for(i=0; i<max_producer; i++)
        pthread_create(&producer_thread[i], NULL, producer, (void *)i);
 
    /* Criando as threads consumidoras */
    for(i=0; i<max_consumer; i++)
        pthread_create(&consumer_thread[i], NULL, consumer, (void *)i);
 
    getchar();
 
}
/* Funcao do produtor */
void *producer(void *arg){
    int i=(int)arg;
    char item[5], m[5];
    printf("Produtor %d criado\n", i);
 
    while(TRUE){
        usleep(rand()%500000);
        sprintf(item, "%4d", i);    // Produz a mensagem
            receive(CONSUMER, &m);        // Recebe o ack
        strcpy(m, item);           // Anexa a mensagem
        printf("# Produtor %d produz: %s\n", i, m);
        send(CONSUMER, &m);         // Envia a mensagem
    }
 
}
/* Funcao do consumidor */
void *consumer(void *arg){
 
    int i=(int)arg, j;
    char item[5], m[5];
    printf("Consumidor %d criado\n", i);
 
    while(TRUE){
        usleep(rand()%500000);
        receive(PRODUCER, &m);     // Recebe a mensagem
        printf("> Consumidor %d consome: %s!\n", i, m);  
        send(PRODUCER, &m);      //Envia a mensagem ack
 
    }
}
/* Primitiva receive */
void receive(int id, char *m){
    if(id==CONSUMER){
        sem_wait(&full_p);
        sem_wait(&mutex);
        strncpy(m,producer_mailbox, 4);
        if(strlen(producer_mailbox)<=4)
            strcpy(producer_mailbox,"");
        else
            strcpy(producer_mailbox, &producer_mailbox[4]);
 
        sem_post(&mutex);
        sem_post(&empty_p);
    } else {
        sem_wait(&full_c);
        sem_wait(&mutex);
        strncpy(m,consumer_mailbox, 4);
        if(strlen(consumer_mailbox)<=4)
            strcpy(consumer_mailbox,"");
        else
            strcpy(consumer_mailbox, &consumer_mailbox[4]);
        sem_post(&mutex);
        sem_post(&empty_c);
    }
}
/* Primitiva send */
void send(int ident, char *m){
    if(ident==CONSUMER){
        sem_wait(&empty_c);
        sem_wait(&mutex);
        strcat(consumer_mailbox,m);    // Posta a mensagem
        sem_post(&mutex);
        sem_post(&full_c);
    } else {
        sem_wait(&empty_p);
        sem_wait(&mutex);
        strcat(producer_mailbox,m);    // Posta a mensagem
        sem_post(&mutex);
        sem_post(&full_p);
    }    
}

TESTE

Teste 1: 1 produtor e 1 consumidor
Teste 2: 4 produtores e 1 consumidor
Teste 3: 1 produtor e 4 consumidores
Teste 4: 1 produtor

$ ./ex7 1 1
Produtor 0 criado
Consumidor 0 criado
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
> Consumidor 0 consome:    0!
> Consumidor 0 consome:    0!
# Produtor 0 produz:    0
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
> Consumidor 0 consome:    0!
^C
$ ./ex7 4 1
Produtor 2 criado
Produtor 0 criado
Produtor 1 criado
Produtor 3 criado
Consumidor 0 criado
# Produtor 3 produz:    3
# Produtor 1 produz:    1
> Consumidor 0 consome:    3!
# Produtor 2 produz:    2
# Produtor 2 produz:    2
# Produtor 3 produz:    3
# Produtor 0 produz:    0
# Produtor 2 produz:    2
> Consumidor 0 consome:    1!
> Consumidor 0 consome:    2!
# Produtor 3 produz:    3
# Produtor 1 produz:    1
# Produtor 3 produz:    3
# Produtor 1 produz:    1
# Produtor 2 produz:    2
# Produtor 1 produz:    1
> Consumidor 0 consome:    2!
# Produtor 1 produz:    1
> Consumidor 0 consome:    3!
# Produtor 0 produz:    0
^C
$ ./ex7 1 4
Produtor 0 criado
Consumidor 0 criado
Consumidor 1 criado
Consumidor 2 criado
Consumidor 3 criado
# Produtor 0 produz:    0
> Consumidor 2 consome:    0!
# Produtor 0 produz:    0
> Consumidor 1 consome:    0!
# Produtor 0 produz:    0
> Consumidor 3 consome:    0!
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
# Produtor 0 produz:    0
> Consumidor 1 consome:    0!
# Produtor 0 produz:    0
> Consumidor 2 consome:    0!
# Produtor 0 produz:    0
> Consumidor 3 consome:    0!
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
# Produtor 0 produz:    0
> Consumidor 2 consome:    0!
# Produtor 0 produz:    0
> Consumidor 3 consome:    0!
# Produtor 0 produz:    0
> Consumidor 1 consome:    0!
# Produtor 0 produz:    0
> Consumidor 0 consome:    0!
^C
Produtor 0 criado
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
# Produtor 0 produz:    0
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License