"Banheiro da Balada" : como controlar entrada de homens e mulheres?

Neste exercício, propomos uma solução para sincronizar o acesso ao banheiro de uma "balada". Como normalmente um único banheiro está disponível para ambos os sexos utilizarem, faz-se necessário desenvolver uma solução que sincronize o acesso de homens e mulheres, com algumas restrições. Caso o banheiro esteja vazio, qualquer pessoa pode entrar. As seguintes devem ser do mesmo sexo, até que o banheiro se esvazie novamente, dando oportunidade para alguém do sexo oposto entrar.

A seguir apresentamos o código-fonte da solução proposta seguido de testes que compravam o bom-funcionamento do programa.

// banheiro da balada

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>
#include <errno.h>

#define N_MULHERES 5
#define N_HOMENS 5

// estados do banheiro
#define VAZIO 0
#define COM_MULHER 1
#define COM_HOMEM 2

pthread_mutex_t mutex_banheiro;
int homens_no_banheiro = 0;
int mulheres_no_banheiro = 0;
int estado = 0;

char *homem_nome[N_HOMENS] = {"Abraham", "Bill", "Carl", "David", "Stri"};
char *mulher_nome[N_MULHERES] = {"Alice", "Pri", "Julia", "Yoko", "Pam"};

int dummy[5]; 

void *homem(void *arg);
void *mulher(void *arg);

void mulher_quer_entrar(int id);
void mulher_quer_sair(int id);
void homem_quer_entrar(int id);
void homem_quer_sair(int id);

void error_exit(const char*);

int main() {
 
 srand(time(NULL));

 int res;
 pthread_t mulher_thread[N_MULHERES], homem_thread[N_HOMENS];
 void *thread_result;
 int index;

 //init dummy array
 for (index = 0; index < 5; index++){
  dummy[index]=index;
 }
 
 // iniciar mutex
 res = pthread_mutex_init(&mutex_banheiro, NULL);
 if(res != 0) error_exit("Inicializacao do mutex falhou");

 
 // criar threads
 for (index = 0; index < N_MULHERES; index ++) {
  res = pthread_create(&mulher_thread[index],NULL,mulher, (void *)&dummy[index]);
  if (res != 0) error_exit("Thread creation failed");
 }
 for (index = 0; index < N_HOMENS; index ++) {
  res = pthread_create(&homem_thread[index],NULL,homem, (void *)&dummy[index]);
  if (res != 0) error_exit("Criacao de thread falhou");
 }

 // join todos threads. assim, esperamos todos threads criados
 // terminarem sua execução

 for (index = 0; index < N_MULHERES; index++) {
  res = pthread_join(mulher_thread[index],&thread_result);
  if (res != 0) error_exit("Thread join falhou");
 }
 
 for (index = 0; index < N_HOMENS; index++) {
  res = pthread_join(homem_thread[index],&thread_result);
  if (res != 0) error_exit("Thread join falhou");
 }

 // kill semaphores, mutexes
 pthread_mutex_destroy(&mutex_banheiro);


 return 1;
}

void *mulher(void *arg){
 int id = *(int *) arg;

 sleep(rand() % 4); // antes de tentar entrar pela 1a vez

 mulher_quer_entrar(id);
 sleep(rand()% 4); // dentro do banheiro
 mulher_quer_sair(id);
 
 pthread_exit("exiting thread.\n"); 
  
}

void *homem(void *arg){
 int id = *(int *) arg;
 
 sleep(rand() % 4); // antes de tentar entrar pela 1a vez
 
 homem_quer_entrar(id);
 sleep(rand()% 4); // dentro do banheiro
 homem_quer_sair(id);
 
 pthread_exit("exiting thread.\n"); 
}

void mulher_quer_entrar(int id) {
 
 printf("%s quer entrar no banheiro.\n.", mulher_nome[id]);
 while (1) {
  pthread_mutex_lock(&mutex_banheiro);
  if (estado != COM_HOMEM) {
   estado = COM_MULHER;
   mulheres_no_banheiro++;
   printf("%s entra no banheiro, agora com %d mulheres.\n",
       mulher_nome[id], mulheres_no_banheiro);
   pthread_mutex_unlock(&mutex_banheiro);
   break;
  }
  pthread_mutex_unlock(&mutex_banheiro);
 }
}

void mulher_quer_sair(int id) {

 printf("%s quer entrar no banheiro\n.", mulher_nome[id]);
 pthread_mutex_lock(&mutex_banheiro);
 mulheres_no_banheiro--;
 if (mulheres_no_banheiro == 0){
  estado = VAZIO;
  printf("%s sai do banheiro, agora vazio.\n",
      mulher_nome[id]);
 }else{
  printf("%s sai do banheiro, agora com %d mulheres.\n",
      mulher_nome[id], mulheres_no_banheiro);
 }
 pthread_mutex_unlock(&mutex_banheiro);
 
}

void homem_quer_entrar(int id) {
 
 printf("%s quer entrar no banheiro\n.", homem_nome[id]);
 while (1) {
  pthread_mutex_lock(&mutex_banheiro);
  if (estado != COM_MULHER) {
   estado = COM_HOMEM;
   homens_no_banheiro++;
   printf("%s entra no banheiro, agora com %d homens.\n",
       homem_nome[id], homens_no_banheiro);
   pthread_mutex_unlock(&mutex_banheiro);
   break;
  }
  pthread_mutex_unlock(&mutex_banheiro);
 }
}

void homem_quer_sair(int id) {
 printf("%s quer sair do banheiro\n.", homem_nome[id]);
 
 pthread_mutex_lock(&mutex_banheiro);
 homens_no_banheiro--;
 if (homens_no_banheiro == 0){
  estado = VAZIO;
  printf("%s sai do banheiro, agora vazio.\n",
      homem_nome[id]);
 }else{
  printf("%s sai do banheiro, agora com %d homens.\n",
      homem_nome[id], homens_no_banheiro);
 }
 pthread_mutex_unlock(&mutex_banheiro);
 
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

O teste a seguir descreve uma possível sequência de utilização do banheiro. Observe que os resultados estão de acordo com o esperado.

Bill quer entrar no banheiro
.Yoko quer entrar no banheiro.
.Pri quer entrar no banheiro.
.Bill entra no banheiro, agora com 1 homens.
Pam quer entrar no banheiro.
.Julia quer entrar no banheiro.
.Alice quer entrar no banheiro.
.Carl quer entrar no banheiro
.Stri quer entrar no banheiro
.Carl entra no banheiro, agora com 2 homens.
Stri entra no banheiro, agora com 3 homens.
Abraham quer entrar no banheiro
.Abraham entra no banheiro, agora com 4 homens.
Abraham quer sair do banheiro
.Abraham sai do banheiro, agora com 3 homens.
Bill quer sair do banheiro
.Bill sai do banheiro, agora com 2 homens.
Carl quer sair do banheiro
.Carl sai do banheiro, agora com 1 homens.
David quer entrar no banheiro
.Stri quer sair do banheiro
.David entra no banheiro, agora com 2 homens.
Stri sai do banheiro, agora com 1 homens.
David quer sair do banheiro
.David sai do banheiro, agora vazio.
Pam entra no banheiro, agora com 1 mulheres.
Yoko entra no banheiro, agora com 2 mulheres.
Pri entra no banheiro, agora com 3 mulheres.
Alice entra no banheiro, agora com 4 mulheres.
Julia entra no banheiro, agora com 5 mulheres.
Julia quer entrar no banheiro
.Julia sai do banheiro, agora com 4 mulheres.
Pam quer entrar no banheiro
.Pam sai do banheiro, agora com 3 mulheres.
Yoko quer entrar no banheiro
.Yoko sai do banheiro, agora com 2 mulheres.
Pri quer entrar no banheiro
.Pri sai do banheiro, agora com 1 mulheres.
Alice quer entrar no banheiro
.Alice sai do banheiro, agora vazio.

Comunicação entre processos: "Produtores e Consumidores" utilizando pipes e processos

Nos posts anteriores utilizamos threads para solucionar alguns clássicos problemas IPC. Neste post utilizaremos pipes e forks para solucionar o problema dos "Produtores e Consumidores", demonstrando como pode ser feita a comunicação entre processos.

Produtores colocam dados em um buffer, enquanto consumidores retiram dados do buffer. O problema surge quando produtores tentarem colocar dados em um buffer já cheio ou, analogamente, consumidores tentarem retirar dados de um buffer vazio.

A solução aqui apresentada utiliza pipes, permitindo que processos produtores se comuniquem com consumidores. Mais especificamente, um único pipe é criado e todos os processos o utilizam para retirar ou inserir dados. Considerando que as operações são thread-safe, a solução garante o bom comportamento do programa, como demonstrado pelos testes.

Os processos gerados a partir do processo pai executarão o código de Producer ou Consumer.
A fim de permitir a comunicação entre os mesmos, inicialmente criamos um pipe (executando na linha de comando -- $ mkfifo thePipe

A seguir, apresentamos o código-fonte dos dois arquivos.

// producer.c

#include <stdio.h>
#include <fcntl.h>
#include <string.h>

int main () {
  int fd, messageLen, i;
  char message [100]; /* Prepare message */
  sprintf (message, "Hello from producer PID %d parent is %d",
           getpid (), getppid());
  messageLen = strlen (message) + 1;
  do /* Keep trying to open the file until successful */
  {
      fd = open ("thePipe", O_WRONLY); /* Open named pipe for writing */
      if (fd == -1) sleep (1); /* Try again in 1 second */
  } while (fd == -1);
  for (i = 1; i <= 3; i++) /* Send three messages */     {         write (fd, message, messageLen); /* Write message down pipe */         sleep (3); /* Pause a while */     }     close (fd); /* Close pipe descriptor */     return 1; }  

// consumer.c

#include <stdio.h>
#include <fcntl.h>
#include <sys/types.h>

int readLine (int fd,char *str);
int main () {
int fd;
char str[100];
fd = open ("thePipe", O_RDONLY); /* Open it for reading */
while (readLine (fd, str)) /* Display received messages */
 printf ("%s\n", str);
close (fd); /* Close pipe */
sleep(3);
return 1;
}

/* Read a single NULL-terminated line into str from fd */
/* Return 0 when the end-of-input is reached and 1 otherwise */
int readLine (int fd,char *str) {
int n;
do /* Read characters until NULL or end-of-input */
{
n = read (fd, str, 1); /* Read one character */
} while (n > 0 && *str++ != 0 );
return (n > 0); /* Return false if end-of-input */
}

Finalmente, apresentamos o programa que será executado e ordenará a geração dos processos-filho.

//producer_consumer.c

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/types.h>

void create_producer();
void create_consumer();

int main() {

int index;

create_producer();
create_producer();
create_consumer();

return 1;

}

void create_producer() {
printf("Produtor criado.\n");
int pid = fork();
if (pid == 0) {
execlp("./producer","producer",NULL);
}
}

void create_consumer() {
printf("Consumidor criado.\n");
int pid = fork();
if (pid == 0) {
execlp("./consumer","consumer",NULL);
}
}

Note que quando o processo filho completa sua execução mas ainda tem uma entrada em sua process table (para permitir que o pai leia seu status de saída) este passa a se denominar zombie.
Podemos simular tal situação se colocarmos o processo-pai para dormir por um longo período e o processo-filho apenas executando exit(0). Enquanto o pai dormir, o filho será um zombie. Note que isto é diferente de processo-órfão.

Finalmente, um simples teste.

bash-3.2$ ./consumer & ./producer &./producer &
[1] 2526
[2] 2527
[3] 2528
Hello from producer PID 2527
Hello from producer PID 2528
Hello from producer PID 2527
Hello from producer PID 2528
Hello from producer PID 2527
Hello from producer PID 2528

[1]   Exit 1                  ./consumer
[2]-  Exit 1                  ./producer
[3]+  Exit 1                  ./producer
bash-3.2$

Utilizando semáforos em sistemas Darwin

Nos últimos posts, apresentamos soluções para alguns clássicos problemas de comunicação entre processos e threads. Os programas foram implementados e executados no Mac OS X , sistema operacional baseado em UNIX e construído sobre uma camada Darwin.

Neste post, apresentamos algumas (sensíveis) restrições acerca do uso de semáforos em sistemas Darwin.

O padrão POSIX inclui especificações para semáforos nomeados e não-nomeados.
Para a nossa finalidade , semáforos não-nomeados (unnamed semaphores) seriam suficientes. Entretato, apenas o padrão nomeado (named semaphores) está disponível no Darwin. Neste caso, podemos criar e finalizar um semáforo da seguinte forma:

#include <semaphore.h>
sem_t * sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
int sem_close(sem_t *sem);
int sem_unlink(const char *name);

O sútil problema ocorre quando o processo do programa é killed durante execução, situação na qual os semáforos não são fechados e unlinked apropriadamente. Como o kernel do Darwin (aparentemente) não limpa estes semáforos imediatamente, uma solução é necessária para evitar que subsequentes execuções do programa utilizem o antigo semáforo (residual).
Isto pode ocorrer caso novas chamadas de sem_open() utilizem a mesma string 'name'.

A solução proposta é gerar uma (longa) string aleatória cada vez que se deseje um novo semáforo. Assim em posts anteriores, as declarações tomam a seguinte forma:

sem_t * sem_open(rand_str(const char *sem_name,int strlength),
      O_CREAT ,0, unsigned int sem_init_value);

Usar semáforos no Mac OS X passa então a não mais ser uma experiência frustrante!

Implementando problema dos "Leitores e Escritores" utilizando semáforos.

Olá leitores! Continuamos aqui a série de posts sobre problemas de comunicação entre threads e processos, desta vez abordando o problema dos "Leitores e Escritores".
Esse clássico problema de concorrência modela o acesso a um banco de dados. A situação proposta é a de um banco de dados que é acessado por leitores e escritores. A operação de leitura não requer uso exclusivo de tal banco, isto é, outros leitores também podem estar presentes. Já a operação de escrita requer exclusividade de acesso. A questão então é: como sincronizar leitores e escritores?

A seguir, apresentamos uma solução para tal problema utilizando semáforos.
Finalmente, os testes apresentados comprovam o bom funcionamento de nossa implementação.

CÓDIGO-FONTE

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>
#include <errno.h>

#define NREADERS 5
#define NWRITERS 5
#define MAX_DB_TIME 2
#define MAX_TIME_BEFORE_START 4

sem_t *db;
pthread_mutex_t mutex;
int rc = 0;
char *readers[5] = {"Abraham", "Bill", "Carl", "David", "Ellen"};
char *writers[5] = {"Stri", "ManoPri", "Chipuruto", "Cone", "Flavio"};

int dummy[NREADERS];

void *reader(void *arg);
void *writer(void *arg);
void read_data_base();
void use_data_read();
void think_up_data();
void write_data_base();

void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);


int main() {
 
 srand(time(NULL));

 int res;
 pthread_t reader_thread[NREADERS], writer_thread[NWRITERS];
 void *thread_result;
 char *dbsem_name; // utilizaremos o padrao POSIX named sem
 int index;

 //init dummy array
 for (index = 0; index < NREADERS; index++){
  dummy[index]=index;
 }
 
 // iniciar mutex
 res = pthread_mutex_init(&mutex, NULL);
 if(res != 0) error_exit("Inicializacao do mutex falhou");

 // iniciar semaforos
 // atencao: em sistemas darwin, utilizamos sem_open ao inves de sem_init
 // no Mac OS X, apenas *semaforos nomeados* estao implementados.

 db = sem_open(rand_str(dbsem_name,8),O_CREAT,0,1);
 if (db == SEM_FAILED) printf("criacao de semaforo falhou.\n");
 
 // criar threads
 for (index = 0; index < NWRITERS; index ++) {
  res = pthread_create(&writer_thread[index],NULL,writer, (void *)&dummy[index]);
  if (res != 0) error_exit("Thread creation failed");
 }
 for (index = 0; index < NREADERS; index ++) {
  res = pthread_create(&reader_thread[index],NULL,reader, (void *)&dummy[index]);
  if (res != 0) error_exit("Criacao de thread falhou");
 }

 // join thread. é suficiente único join p/ este programa
 // pois todas as threads tem loop infinito.

 res = pthread_join(writer_thread[0],&thread_result);
 if (res != 0) error_exit("Thread join falhou");

 // kill semaphores, mutexes
 pthread_mutex_destroy(&mutex);
 // closing and unlink semaphores
 sem_close_n_unlink(db, dbsem_name);

 return 1;
}

void *reader(void *arg){
 int id = *(int *) arg;

 while (1) {
  pthread_mutex_lock(&mutex);
  printf("=%s will try to read.\n", readers[id]);
  rc = rc + 1;
  if (rc == 1) sem_wait(db);  // se 1o leitor...
  pthread_mutex_unlock(&mutex);
  printf("==%s is reading, totaling  %d readers.\n",
      readers[id], rc);
  read_data_base();
  pthread_mutex_lock(&mutex);
  rc = rc - 1;
  if (rc == 0) {
   sem_post(db); //se ultimo leitor...
   printf("=%s is done reading and realease db.\n", readers[id]);
  }
  else {
   printf("%s is done reading. %d readers are left\n", 
       readers[id], rc);
  }
  pthread_mutex_unlock(&mutex);
  use_data_read();
 }

 pthread_exit("exiting thread.\n"); 
}

void *writer(void *arg){
 int id = *(int *) arg;
 
 while (1) {
  think_up_data();
  printf(".%s will try  to write into db.\n", writers[id]);  
  sem_wait(db);
  printf("..%s is writing into db.\n", writers[id]);  
  write_data_base();
  sem_post(db);
  printf(".%s is done writing and realesed db.\n", writers[id]);  
 }
 
 pthread_exit("exiting thread.\n"); 
}

void read_data_base() {
 sleep(rand() % MAX_DB_TIME);
}

void use_data_read() {
 sleep(rand() % MAX_DB_TIME);
}

void think_up_data() {
 sleep(rand() % MAX_DB_TIME); 
}

void write_data_base() {
 sleep(rand() % MAX_DB_TIME);
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}

TESTES

  

.Stri will try  to write into db.
..Stri is writing into db.
.Stri is done writing and realesed db.
.Stri will try  to write into db.
..Stri is writing into db.
.Chipuruto will try  to write into db.
.Cone will try  to write into db.
=Abraham will try to read.
.Stri is done writing and realesed db.
..Chipuruto is writing into db.
.Stri will try  to write into db.
.ManoPri will try  to write into db.
.Flavio will try  to write into db.
.Chipuruto is done writing and realesed db.
..Cone is writing into db.
.Chipuruto will try  to write into db.
.Cone is done writing and realesed db.
==Abraham is reading, totaling  1 readers.
=Bill will try to read.
.Cone will try  to write into db.
==Bill is reading, totaling  2 readers.
=Carl will try to read.
==Carl is reading, totaling  3 readers.
=David will try to read.
==David is reading, totaling  4 readers.
=Ellen will try to read.
==Ellen is reading, totaling  5 readers.
Abraham is done reading. 4 readers are left
David is done reading. 3 readers are left
=Abraham will try to read.
==Abraham is reading, totaling  4 readers.
Bill is done reading. 3 readers are left
Ellen is done reading. 2 readers are left
Carl is done reading. 1 readers are left
=Carl will try to read.
==Carl is reading, totaling  2 readers.
=David will try to read.
==David is reading, totaling  3 readers.
Abraham is done reading. 2 readers are left
=Bill will try to read.
==Bill is reading, totaling  3 readers.
=Ellen will try to read.
==Ellen is reading, totaling  4 readers.
Carl is done reading. 3 readers are left
Ellen is done reading. 2 readers are left
=Ellen will try to read.
==Ellen is reading, totaling  3 readers.
David is done reading. 2 readers are left
=David will try to read.
==David is reading, totaling  3 readers.
=Abraham will try to read.
==Abraham is reading, totaling  4 readers.
Abraham is done reading. 3 readers are left
Bill is done reading. 2 readers are left
=Carl will try to read.
==Carl is reading, totaling  3 readers.
Carl is done reading. 2 readers are left
Ellen is done reading. 1 readers are left
=David is done reading and realease db.
=David will try to read.
..Stri is writing into db.
.Stri is done writing and realesed db.
..ManoPri is writing into db.
.Stri will try  to write into db.
.ManoPri is done writing and realesed db.
.ManoPri will try  to write into db.
..Flavio is writing into db.
.Flavio is done writing and realesed db.
..Chipuruto is writing into db.
.Flavio will try  to write into db.

Implementando as operações send e receive utilizando semáforos.

Desta vez, implementaremos as importantes operações de send e receive utilizando semáforos! Esta implementação simples demonstra como dois threads um receiver e outro sender podem simular o ambiente para utilizar as funções send e receive.

CÓDIGO-FONTE

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

#define BUFFER_SIZE 10
#define FANCIEST_MSG 15
#define BUSY_WAIT 3
#define FILE_MODE       (S_IRWXU | S_IRWXG | S_IRWXO )


sem_t *empty_msgs, *full_msgs;
pthread_mutex_t buffer_mutex;
int buffer[BUFFER_SIZE];
int buffer_head = 0;
int dummy = 0;

void *sender (void *arg);
void *receiver (void *arg);
void send (int msg);
void receive();
void print_buffer();
void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);


int main() {
 srand(time(NULL));
 int res;
 pthread_t my_sender, my_receiver;
 void *thread_result;
 
 // start w/ N EMPTY MESSAGES << sem empty messages.
 // produces has an item to give to the consumer?
  // sem_wait(&sem_empty_msg)
  // sem_post(&sem_full_msg)
 res = pthread_mutex_init(&buffer_mutex,NULL);
 if(res != 0){
  perror("Inicializacao de mutex falhou");
  exit(EXIT_FAILURE);
 }

 char *empty_sem_name, *full_sem_name;
 
 empty_msgs = sem_open(rand_str(empty_sem_name,8),O_CREAT,0,BUFFER_SIZE);//, FILE_MODE,BUFFER_SIZE);
 if (empty_msgs == SEM_FAILED) {printf ("sem_failed.\n");}
 full_msgs = sem_open(rand_str(full_sem_name,8),O_CREAT,0,0);
 // if (full_msgs == SEM_FAILED) {printf ("sem_failed.\n");}

 res  = pthread_create(&my_sender,NULL,sender,(void *)&dummy);
 if (res != 0){
  perror("Thread creation failed");
  exit(EXIT_FAILURE);
 }
 res =  pthread_create(&my_receiver,NULL,receiver,(void *)&dummy);
 if (res != 0){
  perror("Thread creation failed");
  exit(EXIT_FAILURE);
 }

 res = pthread_join(my_sender, &thread_result);
 if (res != 0){
  perror("Thread join failed");
  exit(EXIT_FAILURE);
 }

 //destroy mutex
 pthread_mutex_destroy(&buffer_mutex);
 // closing and unlink semaphores
 sem_close_n_unlink(empty_msgs, empty_sem_name);
 sem_close_n_unlink(full_msgs, full_sem_name);
 return 1;
}


void *sender (void *arg) {
 int id = *(int *) arg; // irrelevante pois supomos apenas um sender
 int msg;
 while(1){
  msg = rand () % FANCIEST_MSG;
  sleep(rand() % BUSY_WAIT);
  printf("sender has a msg: %d\n", msg);
  sem_wait(empty_msgs); //check whether we can send
  send(msg);
  sem_post(full_msgs); //receive remembers to receive
 }
}

void *receiver (void *arg) {
 int id = *(int *) arg; 
 while(1){
  sem_wait(full_msgs);
  sleep(rand() % BUSY_WAIT);
  receive();
  sem_post(empty_msgs);
 }
}

void send(int msg) {
 pthread_mutex_lock(&buffer_mutex);
 printf("sender inserted msg %d in buffer\n", msg);
 buffer[buffer_head] = msg;
 buffer_head++;
 print_buffer();
 pthread_mutex_unlock(&buffer_mutex);
}

void receive() {
 int msg;
 pthread_mutex_lock(&buffer_mutex);
 printf("receiver removing msg %d in buffer\n", buffer[buffer_head - 1]);
 msg = buffer[buffer_head - 1];
 buffer_head--;
 print_buffer();
 pthread_mutex_unlock(&buffer_mutex);
}
 
void print_buffer(){
 int index;
 printf("buffer is... ");
 for (index = 0; index < buffer_head; index++){
  printf(". %d .", buffer[index]);
 }
 printf("\n");
}


void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}
 

TESTES

sender has a msg: 5
sender inserted msg 5 in buffer
buffer is... . 5 .
sender has a msg: 2
sender inserted msg 2 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 1
sender inserted msg 1 in buffer
buffer is... . 5 .. 2 .. 1 .
receiver removing msg 1 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 13
sender inserted msg 13 in buffer
buffer is... . 5 .. 2 .. 13 .
sender has a msg: 3
sender inserted msg 3 in buffer
buffer is... . 5 .. 2 .. 13 .. 3 .
receiver removing msg 3 in buffer
buffer is... . 5 .. 2 .. 13 .
sender has a msg: 9
sender inserted msg 9 in buffer
buffer is... . 5 .. 2 .. 13 .. 9 .
receiver removing msg 9 in buffer
buffer is... . 5 .. 2 .. 13 .
sender has a msg: 10
sender inserted msg 10 in buffer
buffer is... . 5 .. 2 .. 13 .. 10 .
sender has a msg: 0
receiver removing msg 10 in buffer
buffer is... . 5 .. 2 .. 13 .
sender inserted msg 0 in buffer
buffer is... . 5 .. 2 .. 13 .. 0 .
sender has a msg: 4
receiver removing msg 0 in buffer
buffer is... . 5 .. 2 .. 13 .
sender inserted msg 4 in buffer
buffer is... . 5 .. 2 .. 13 .. 4 .
receiver removing msg 4 in buffer
buffer is... . 5 .. 2 .. 13 .
sender has a msg: 0
sender inserted msg 0 in buffer
buffer is... . 5 .. 2 .. 13 .. 0 .
receiver removing msg 0 in buffer
buffer is... . 5 .. 2 .. 13 .
receiver removing msg 13 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 11
sender inserted msg 11 in buffer
buffer is... . 5 .. 2 .. 11 .
sender has a msg: 9
receiver removing msg 11 in buffer
buffer is... . 5 .. 2 .
sender inserted msg 9 in buffer
buffer is... . 5 .. 2 .. 9 .
receiver removing msg 9 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 14
sender inserted msg 14 in buffer
buffer is... . 5 .. 2 .. 14 .
receiver removing msg 14 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 7
sender inserted msg 7 in buffer
buffer is... . 5 .. 2 .. 7 .
sender has a msg: 13
sender inserted msg 13 in buffer
buffer is... . 5 .. 2 .. 7 .. 13 .
sender has a msg: 2
sender inserted msg 2 in buffer
buffer is... . 5 .. 2 .. 7 .. 13 .. 2 .

"O barbeiro dorminhoco": Uma solução utilizando threads e semáforos

Olá pessoal!
Continuando a série de posts sobre problemas IPC (Inter-Process Communication), apresentamos agora o problema do "Barbeiro Dorminhoco", acompanhado por uma uma solução que utiliza threads e semáforos. Finalmente, testes são apresentados, comprovando o bom funcionamento de nossa solução.

A situação é bem simples: imagine uma salão de cabelereiros onde, após demissões em massa, apenas o barbeiro-chefe trabalha, atendendo aos clientes que chegam.
Sempre que o expediente está tranquilo demais..... o barbeiro adormece! Este só volta a acordar quando um novo cliente chega, ansioso por um corte.

CÓDIGO-FONTE

 
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>
#include <errno.h>

#define N 20
#define CHAIRS 5
#define MAX_CUT_TIME 5
#define MAX_TIME_BEFORE_START 8

sem_t *customers, *barbers;
pthread_mutex_t mutex;
int waiting = 0;
int customer_id[N];
int barber_id;
char* customer_name[20] = 
 {"A","B","C","D","E", "F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T"};

void *barber(void *arg);
void *customer(void *arg);
void cut_hair();
void get_haircut(int i);
void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);

int main() {
 
 srand(time(NULL));

 int res;
 pthread_t barber_thread, cust_thread[N];
 void *thread_result; 
 int index;

 for (index = 0; index < N; index++) {
  customer_id[index] = index;
 }
 barber_id = 0;
 
 //iniciar mutex
 res = pthread_mutex_init(&mutex, NULL);
 if (res != 0) error_exit("Inicializacao do mutex falhou");

 // iniciar semaforos
 // atencao: em sistemas darwin, utilizamos sem_open ao inves de sem_init
 // pois no Mac OS X, apenas *semaforos nomeados* estao implementados.

 char *barbersem , *customersem;
 barbers = sem_open(rand_str(barbersem,8),O_CREAT,0,0);
 customers = sem_open(rand_str(customersem,8),O_CREAT,0,0);

 // criar threads
 res = pthread_create(&barber_thread, NULL, barber, (void *)&barber_id);
 if (res != 0) error_exit("Criacao de thread falhou");

 for (index = 0; index < N; index++) {
  res = pthread_create(&cust_thread[index],NULL,customer,(void *)&customer_id[index]);
  if (res != 0) error_exit("Criacao de thread falhou");
 }

 res = pthread_join(barber_thread,&thread_result);
 if (res != 0) error_exit("Falhou quando tentou pthread_join");

 //destroy mutex
 pthread_mutex_destroy(&mutex);
 // closing and unlink semaphores
 sem_close_n_unlink(barbers, barbersem);
 sem_close_n_unlink(customers, customersem);

 return 1;
}

void *barber(void *arg){
 int id = *(int *) arg;
 while (1) {
  printf("Barbeiro desocupado.\n");
  sem_wait(customers);
  printf("== Fila de espera tem  %d clientes.\n", waiting);
  pthread_mutex_lock(&mutex);
  waiting = waiting - 1;
  sem_post(barbers);
  printf("Barbeiro pronto para cortar algum cabelo.\n");
  pthread_mutex_unlock(&mutex);
  cut_hair();
 }
}

void *customer(void *arg) {
 
 int id = *(int *) arg;
 sleep(rand() % MAX_TIME_BEFORE_START); //simular o comportamento de chegada dos clientes
 
 pthread_mutex_lock(&mutex);
 if (waiting < CHAIRS) {
  waiting = waiting + 1;
  sem_post(customers);
  printf("%s esta na fila de espera. Tamanho da fila eh %d.\n", customer_name[id], waiting);
  pthread_mutex_unlock(&mutex);
  sem_wait(barbers);
  get_haircut(id);
 }
 else {
  printf("  Cliente %s passando direto. Fila cheia!\n", customer_name[id]);
  pthread_mutex_unlock(&mutex);
 }
 pthread_exit("customer exits.\n");
}

void cut_hair() {
 sleep(3);
}

void get_haircut(int i) {
 printf("%s esta cortando o cabelo\n", customer_name[i]);
 sleep(3);
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}
 

TESTES

Abaixo, apresentamos a saída obtida durante execução do problema. Observe
que, de fato, ela é consistente com as restrições impostas pelo enunciado do
problema.

Barbeiro desocupado.
F esta na fila de espera. Tamanho da fila eh 1.
H esta na fila de espera. Tamanho da fila eh 2.
Q esta na fila de espera. Tamanho da fila eh 3.
== Fila de espera tem 3 clientes.
Barbeiro pronto para cortar algum cabelo.
F esta cortando o cabelo
D esta na fila de espera. Tamanho da fila eh 3.
N esta na fila de espera. Tamanho da fila eh 4.
I esta na fila de espera. Tamanho da fila eh 5.
Cliente J passando direto. Fila cheia!
Cliente C passando direto. Fila cheia!
Cliente K passando direto. Fila cheia!
Cliente P passando direto. Fila cheia!
Barbeiro desocupado.
== Fila de espera tem 5 clientes.
Barbeiro pronto para cortar algum cabelo.
H esta cortando o cabelo
A esta na fila de espera. Tamanho da fila eh 5.
Cliente E passando direto. Fila cheia!
Cliente S passando direto. Fila cheia!
Cliente T passando direto. Fila cheia!
Cliente L passando direto. Fila cheia!
Cliente O passando direto. Fila cheia!
Cliente R passando direto. Fila cheia!
Barbeiro desocupado.
== Fila de espera tem 5 clientes.
Barbeiro pronto para cortar algum cabelo.
Q esta cortando o cabelo

"Jantar dos Filósofos" - Uma Solução utilizando Threads e Semáforos

Proposto em 1965 por Esdger Dijkstra, o clássico "Jantar dos Filósofos" ilustra o problema de concorrência em computação, apresentando-se como uma explicação teórica do deadlock.

A situação proposta é a de um mesa de jantar ao redor da qual estão sentados 5 (cinco) filósofos, cada um capaz de realizar apenas duas atividades, mutuamente exclusivas: pensar ou comer.
Na frente de cada filósofo existe um delicioso prato de spaghetti pronto para ser devorado. Um garfo é posicionado entre cada par de filósofos e, considerando a dificuldade para comer tal saboroso macarrão, cada filósofo precisa de dois garfos para fazer sua refeição. Além disso, podem apenas usar o garfo imediatamente à sua direita ou esquerda.

A questão proposta por Dijkstra é então: como programar os filósofos de modo evitar a situação de deadlock, onde todos esperam eternamente para o outro garfo tornar-se disponível?

A seguir, apresentamos o código que implementa uma solução para tal problema, utilizando threads e semáforos. Finalmente, testes são apresentados para comprovar o bom funcionamento da solução.


CÓDIGO-FONTE

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

#define MAX_THINK_TIME 5   
#define MAX_EAT_TIME 5    
#define N  5    
#define LEFT  (i+N-1)%N   
#define RIGHT  (i+1)%N  
#define THINKING 0   
#define HUNGRY  1   
#define EATING  2   

int state[N];       // vetor de estados. um estado para cada filósofo
pthread_mutex_t mutex;     // mutex para região crítica
sem_t *sem[N];       // vetor de semáforos. um sem para cada filósofo.
char *friends[5] = {"Abraham", "Bill", "Carl", "David", "Ellen"};  // pretty-printing para N=5

int dummy[N];

void *philosopher (void *arg);  
void take_forks(int i);    
void put_forks(int i);
void test(int i);
void think(int i);
void eat(int i);
void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);


int main() {

 srand(time(NULL));   // fornecendo seed para uma nova série números pseudo-random
 int res;
 pthread_t philo_thread[N];  // vetor contém uma thread para cada filósofo
 void *thread_result;  // thread resultado para ser usada em pthread_join
 int index;
 
 //init dummy array
 for (index = 0; index < N; index++){
  dummy[index]=index;
 }
 
 // iniciar mutex
 res = pthread_mutex_init(&mutex, NULL);
 if(res != 0){
  perror("Inicializacao de mutex falhou");
  exit(EXIT_FAILURE);
 }

 // iniciar semaforos
 // atencao: em sistemas darwin, utilizamos sem_open ao inves de sem_init
 // no Mac OS X, apenas *semaforos nomeados* estao implementados.
 char *philosem_names[N];
 for (index = 0; index < N; index ++){
  sem[index] = sem_open(rand_str(philosem_names[N],8),O_CREAT,0,0);
 }

 for (index = 0; index < N; index++){
  state[index]=THINKING; //estado inicial dos filosofos
 }
 
 //criar filosofos
 for (index = 0; index < N; index++){
  res = pthread_create(&philo_thread[index], NULL, philosopher, (void *)&dummy[index] );
  if (res != 0){
   perror("Thread creation failed");
   exit(EXIT_FAILURE);
  }
 }

 res = pthread_join(philo_thread[0], &thread_result);
 if (res != 0){
  perror("Thread join failed");
  exit(EXIT_FAILURE);
 }
 printf("Thread joined, it returned this %s\n", (char*)thread_result);

 pthread_mutex_destroy(&mutex);
 // closing and unlink semaphores
 for (index = 0; index < N; index++) {
  sem_close_n_unlink(sem[index], philosem_names[index]);
 }
 return 1;
}

//what does a philopher do?
void *philosopher(void *arg){
 int id = *(int *) arg;
 while(1){
  think(id);
  take_forks(id);
  eat(id);
  put_forks(id);
 }
}

void take_forks(int i) {
 pthread_mutex_lock(&mutex);
 printf("Filosófo %s está com fome\n", friends[i]);
 state[i] = HUNGRY;
 test(i);
 pthread_mutex_unlock(&mutex);
 sem_wait(sem[i]);
}

void put_forks(int i) {
 pthread_mutex_lock(&mutex);
 printf("Filosófo %s está pensando\n", friends[i]);
 state[i] = THINKING;
 test(LEFT);
 test(RIGHT);
 pthread_mutex_unlock(&mutex);
}

void test(int i){
 if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
  printf("Filosófo %s está comendo.  %s está %d. %s está %d.\n",
      friends[i], friends[LEFT],state[LEFT], friends[RIGHT], state[RIGHT]);
  
  state[i] = EATING;
  sem_post(sem[i]);
 }else{
  printf("Filosófo %s está %d.  %s está %d. %s está %d.\n",
      friends[i], state[i], friends[LEFT], state[LEFT], friends[RIGHT], state[RIGHT]);
 }
}

void think(int i){
 sleep(rand() % MAX_THINK_TIME);
}

void eat(int i){
 sleep(rand() % MAX_EAT_TIME);
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}

TESTES
A seguir apresentamos a saída do programa em execução. Esta foi desenvolvida de modo a tornar evidente o bom funcionamento do programa.
Considere o mapeamento: THINKING --> 0, HUNGRY --> 1, EATING --> 2.
A fim de facilitar a compreensão da saída, considere:
"Filósofo Carl está comendo. Bill está 0. David está 0." significa que enquanto o filósofo Carl está comendo, os dois ao seu lado estão pensando, significando que as restrições do problema estão satisfeitas.

Filosófo Carl está com fome
Filosófo Carl está comendo.  Bill está 0. David está 0.
Filosófo Abraham está com fome
Filosófo Abraham está comendo.  Ellen está 0. Bill está 0.
Filosófo Bill está com fome
Filosófo Bill está 1.  Abraham está 2. Carl está 2.
Filosófo Abraham está pensando
Filosófo Ellen está 0.  David está 0. Abraham está 0.
Filosófo Bill está 1.  Abraham está 0. Carl está 2.
Filosófo Carl está pensando
Filosófo Bill está comendo.  Abraham está 0. Carl está 0.
Filosófo David está 0.  Carl está 0. Ellen está 0.
Filosófo David está com fome
Filosófo David está comendo.  Carl está 0. Ellen está 0.
Filosófo Ellen está com fome
Filosófo Ellen está 1.  David está 2. Abraham está 0.
Filosófo Abraham está com fome
Filosófo Abraham está 1.  Ellen está 1. Bill está 2.
Filosófo Bill está pensando
Filosófo Abraham está comendo.  Ellen está 1. Bill está 0.
Filosófo Carl está 0.  Bill está 0. David está 2.
Filosófo David está pensando
Filosófo Carl está 0.  Bill está 0. David está 0.
Filosófo Ellen está 1.  David está 0. Abraham está 2.
Filosófo Ellen está pensando
Filosófo David está 0.  Carl está 0. Ellen está 0.
Filosófo Abraham está 2.  Ellen está 0. Bill está 0.
Filosófo Ellen está com fome
Filosófo Ellen está 1.  David está 0. Abraham está 2.
Filosófo David está com fome
Filosófo David está comendo.  Carl está 0. Ellen está 1.
Filosófo Carl está com fome
Filosófo Carl está 1.  Bill está 0. David está 2.
Filosófo Abraham está pensando
Filosófo Ellen está 1.  David está 2. Abraham está 0.
Filosófo Bill está 0.  Abraham está 0. Carl está 1.
Filosófo Ellen está pensando
Filosófo David está 2.  Carl está 1. Ellen está 0.
Filosófo Abraham está 0.  Ellen está 0. Bill está 0.
Filosófo Abraham está com fome
Filosófo Abraham está comendo.  Ellen está 0. Bill está 0.
Filosófo David está pensando
Filosófo Carl está comendo.  Bill está 0. David está 0.
Filosófo Ellen está 0.  David está 0. Abraham está 2.
Filosófo David está com fome
Filosófo David está 1.  Carl está 2. Ellen está 0.
Filosófo David está pensando
Filosófo Carl está 2.  Bill está 0. David está 0.
Filosófo Ellen está 0.  David está 0. Abraham está 2.
Filosófo Bill está com fome
Filosófo Bill está 1.  Abraham está 2. Carl está 2.