Problema dos Produtores e Consumidores utilizando pipes

O Problema dos Produtores e Consumidores ocorre quando diversos processos de dois tipos (produtor e consumidor) compartilham um buffer para envio de mensagens. Os produtores são responsáveis por criar "objetos" e colocá-los no buffer. Já os consumidores retiram esses objetos do buffer. O buffer obedece o comportamendo de uma fila, "first in first out"
O problema ocorre quando dois produtores tentam colocar objetos no buffer ao mesmo tempo ou quando dois consumidores retiram objetos do buffer ao mesmo tempo. A solução deve ser capaz permitir somente um produtor adcionando objeto e um consumidor retirando objeto ao mesmo tempo.
Também é necessário gerenciar as situações em que o buffer estpa cheio, impossibilitando uma nova adição, e quando está vazio, impossibilitando que um objeto seja consumido.

Na implementação aqui apresentada, utilizou-se os pipes do padrão posix, que possui todos os requerimentos necessários para o buffer. Por ser thread-safe, ele possibilita somente que um processo esteja adicionando objeto ao pipe e somenque um que esteja consumindo. Também já gerencia os casos em que o buffer está vazio ou cheio.

Nessa solução são criados 10 produtores que adionam um objeto ao pipe, que corresponde ao index que identifica o produtor. Em seguida, são criados 5 consumidores e após 6 segundos mais 10 produtores. Os consumidores estão sempre lendo o pipe até que seja esvaziado e então o processo é finalizado.

Abaixo segue o código da solução:
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<unistd.h>

#define LER 0 //indexa a leitura no pipe
#define ESCREVER 1 //indexa a escrita no pipe
#define PRODUTORES 10; // define numero de produtores
#define CONSUMIDORES 5; // define numero de leitores


int fd [2];

void produtor( int produtor);

void consumidor(int consumidor);
void criar_consumidor(int consumidor);

void criar_produtor(int produtor);

main ()
{
int j = 0;

pipe (fd);

//cria produtores
int i = PRODUTORES;
for (j = 1; j <= i; j++)
{
criar_produtor(j);
}

//cria consumidores
i = CONSUMIDORES;
for (j = 1; j<= i; j++)
{

criar_consumidor(j);
}

sleep(6); //espera 6 s para produzir mais
i = PRODUTORES;

for (j = i +1 ; j <= 2*i; j++)
{
criar_produtor(j);
}


return 0;
}

void produtor(int produtor_id)
{

int bytes_escritos;


close(fd[LER]);


bytes_escritos = write (fd[ESCREVER],&produtor_id, sizeof(int));

if (bytes_escritos == -1) { //se ocorre erro fecha processo
printf("\nProblema na escrita do produtor %d", produtor_id);
exit(-1);
}

else{
printf("\nProdutor %d enviou mensagem", produtor_id); //conseguiu enviar mensagem
}

close (fd[ESCREVER]);

exit(0);


}

void consumidor(int consumidor_id)
{

int msg;
int bytes_lidos;
int max_zero;

while(1){

sleep(1); //intervalo de 1 s entre as leituras

close (fd[ESCREVER]);
bytes_lidos = read (fd[LER],&msg, sizeof(int));


if (bytes_lidos == 0){ //caso não tenha nada no pipe finaliza o processo
printf("\nConsumidor %d saiu", consumidor_id);

break;
}
else if (bytes_lidos == -1){//se ocorre erro na leitura, sai
printf("\nProblema na leitura do consumidor %d",consumidor_id );

exit(-1);
}
else printf("\nConsumidor %d leu mensagem: %d com %d bytes\n", consumidor_id, msg, bytes_lidos);

}

close(fd[LER]);

exit(0);

}

void criar_consumidor(int consumidor_id)
{

int pid;
pid = fork ();
if (pid == 0){//caso seja processo filho realiza operação de consumidor

consumidor(consumidor_id);
}
}

void criar_produtor(int produtor_id)
{
int pid;

pid = fork ();

if (pid == 0){//caso seja processo filho realiza operação de produtor

produtor(produtor_id);
}
}

O resultado é mostrado abaixo:


Produtor 1 enviou mensagem
Produtor 2 enviou mensagem
Produtor 3 enviou mensagem
Produtor 4 enviou mensagem
Produtor 5 enviou mensagem
Produtor 6 enviou mensagem
Produtor 7 enviou mensagem
Produtor 8 enviou mensagem
Produtor 9 enviou mensagem
Produtor 10 enviou mensagem
Consumidor 1 leu mensagem: 1 com 4 bytes

Consumidor 2 leu mensagem: 2 com 4 bytes

Consumidor 3 leu mensagem: 3 com 4 bytes

Consumidor 4 leu mensagem: 4 com 4 bytes

Consumidor 5 leu mensagem: 5 com 4 bytes

Consumidor 1 leu mensagem: 6 com 4 bytes

Consumidor 2 leu mensagem: 7 com 4 bytes

Consumidor 3 leu mensagem: 8 com 4 bytes

Consumidor 4 leu mensagem: 9 com 4 bytes

Consumidor 5 leu mensagem: 10 com 4 bytes

Consumidor 1 leu mensagem: 11 com 4 bytes

Produtor 11 enviou mensagem
Consumidor 3 leu mensagem: 12 com 4 bytes

Produtor 12 enviou mensagem
Consumidor 2 leu mensagem: 13 com 4 bytes

Produtor 13 enviou mensagem
Consumidor 4 leu mensagem: 14 com 4 bytes

Produtor 14 enviou mensagem
Consumidor 5 leu mensagem: 15 com 4 bytes

Produtor 15 enviou mensagem
Produtor 16 enviou mensagem
Produtor 17 enviou mensagem
Produtor 18 enviou mensagem
Produtor 19 enviou mensagem
Produtor 20 enviou mensagem
Consumidor 1 leu mensagem: 16 com 4 bytes

Consumidor 3 leu mensagem: 17 com 4 bytes

Consumidor 2 leu mensagem: 18 com 4 bytes

Consumidor 4 leu mensagem: 19 com 4 bytes

Consumidor 5 leu mensagem: 20 com 4 bytes

Consumidor 1 saiu
Consumidor 3 saiu
Consumidor 2 saiu
Consumidor 4 saiu
Consumidor 5 saiu

O resultado mostra que nenhum consumidor obteve uma mensagem igual, que nenhuma mensagem foi perdida e que as ordem em que as mensagens chegaram foi a mesmo em que foram enviadas.

Com o comando "ps -aux" no console do linux, pode-se ver informações sobre os processos decorrentes do programa executado. Abaixo segue o output:

david 7524 0.0 0.0 3780 368 pts/2 S+ 04:24 0:00 ./prod
david 7525 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7526 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7527 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7528 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7529 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7530 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7531 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7532 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7533 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7534 0.0 0.0 0 0 pts/2 Z+ 04:24 0:00 [prod]
david 7535 0.0 0.0 3784 244 pts/2 S+ 04:24 0:00 ./prod
david 7536 0.0 0.0 3784 244 pts/2 S+ 04:24 0:00 ./prod
david 7537 0.0 0.0 3784 244 pts/2 S+ 04:24 0:00 ./prod
david 7538 0.0 0.0 3784 244 pts/2 S+ 04:24 0:00 ./prod
david 7539 0.0 0.0 3784 244 pts/2 S+ 04:24 0:00 ./prod
david 7541 0.0 0.0 7472 912 pts/1 S+ 04:24 0:00 grep prod

Pode-se notar que alguns processo estão em estado zoobie (Z+) e outros estão dormindo (+S). Os processos domindo são os consumidores que dormiram em virtude do comando sleep(), os demais podem ser processos filhos, tanto consumidores ou produtores, que estão esperando o proceso finalizá-los.

O Problema dos Leitores e Escritores

Esse problema simula a sistemática de acesso à um banco de dados. Existem diversos diversos leitores e escritores buscando ler/modificar um dado compartilhado. É necessário então que quando um escritor estiver atualizando o dado, nenhum outro leitor ou escritor possa acessar aquele dado, visto que os escritores podem acabar acessando um dado desatualizado e os escritores podem moficar um dado antigo, modificá-lo e sobescrever o dado atualizado por outro escritor.
A solução ideal deve permitir que vários leitores possam acessar o dado ao mesmo tempo, mas quando um escrito esta atualizando o dado nenhum outro processo deve ter acesso.
A sulução utilizaou dois mutex, uma para pegar acesso exclusivo ao dado, impossiblitando que dois escritores modifiquem ao mesmo tempo; e outro para acessar uma variável que conta o número de leitores lendo ou querendo ler o dado. Dessa forma, esse ultimo mutex controla o acesso dos escritores ao dado.

O código da solução é mostrado abaixo:

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

#define N_ESC 3 //número de escritores
#define N_LEIT 4 //número de leitores

pthread_t t_escritores[N_ESC]; //vetor de threads para escritores
pthread_t t_leitores[N_LEIT]; //vetor de threadas para leitores

pthread_mutex_t mutex; //mutex para acesso de rc

pthread_mutex_t acesso_d; //mutex para acesso do dado
int dados_lidos[N_LEIT]; //vetor que quarda o dado lido
int dado = 0; //dado à ser lido e escrito


int n_le = 0; //número de threads lendo ou querendo ler

void *leitor(void *id);

void *escritor(void *id);
void ler_dado(int leitor);

void utilizar_dado_lido(int leitor);
void pensar_dado(int escritor);

void escrever_dado(int escritor);


main(){

//variáveis para controle de loop e validação da criação de threads e mutexes
int res;

void *resultado_thread_leit[N_LEIT];
void *resultado_thread_esc[N_ESC];


//criação de mutexs
res = pthread_mutex_init(&mutex, NULL);
if (res!= 0 ){

perror("\nFalha na criacao do mutex de acesso a n_le");
exit(EXIT_FAILURE);
}

res = pthread_mutex_init(&acesso_d, NULL);

if (res!= 0 ){
perror("\nFalha na criacao do mutex de acesso ao dados");

exit(EXIT_FAILURE);
}

int aux[N_ESC];
int j;

//criação das threads dos escritores
for (j = 0 ; j<N_ESC; j++)
{

aux[j] = j;
res = pthread_create(&t_escritores[aux[j]], NULL, escritor, (void *)&aux[j]);
if (res!= 0 ){

perror("\nFalha na criacao da thread");
exit(EXIT_FAILURE);
}
}
//criação de threadas dos leitores
int aux2[N_LEIT];

for (j = 0 ; j<N_LEIT; j++)
{

aux2[j] = j;
res = pthread_create(&t_leitores[aux2[j]], NULL, leitor, (void *)&aux2[j]);
if (res!= 0 ){

perror("\nFalha na criacao da thread");
exit(EXIT_FAILURE);
}
}

//link das threads
for (j = 0 ; j<N_ESC; j++)
{
res = pthread_join(t_escritores[j], &resultado_thread_esc[j] );
if (res!= 0 )
{

perror("\nFalha no thread join do consumidor" );
exit(EXIT_FAILURE);
}

}

for (j = 0 ; j<N_LEIT; j++)
{
res = pthread_join(t_leitores[j], &resultado_thread_leit[j] );
if (res!= 0 )
{

perror("\nFalha no thread join do consumidor" );
exit(EXIT_FAILURE);
}
}
return 0;

}

//função da thread do leitor
void *leitor(void *id)
{
int i = *(int *)id;

while (1) { //loop infinito
pthread_mutex_lock(&mutex); //pega acesso à n_le
n_le = n_le + 1; //acrecentando numero que estão lendo ou querendo ler

if (n_le == 1) pthread_mutex_lock(&acesso_d); //ve se é o primeiro leitor

pthread_mutex_unlock(&mutex); //libera acesso à n_le
ler_dado(i); //le o dado
pthread_mutex_lock(&mutex); //pega acesso exclusivo à n_le

n_le = n_le +(-1); //reduz o numero que está lendo
if (n_le == 0) pthread_mutex_unlock(&acesso_d); //se for o último libera o acesso ao dado para escrita

pthread_mutex_unlock(&mutex); //libera acesso à n_le
utilizar_dado_lido(i); //região não crítica
}
}


void *escritor(void *id)
{
int i = *(int *)id;

while (1) { //loop infinito
pensar_dado(i); //região não crítica
pthread_mutex_lock(&acesso_d); //pega acesso exclusivo ao dado

escrever_dado(i); //modifica o dado
pthread_mutex_unlock(&acesso_d); //libera acesso
}
}

void ler_dado(int leitor)
{
dados_lidos[leitor] = dado; //salva o dado no vetor de dados lidos

printf("\nLeitor %d leu dado: %d", leitor, dados_lidos[leitor]);

}

void utilizar_dado_lido(int leitor)
{

printf("\nLeitor %d utilizando dado", leitor);
sleep(rand()%5); //demora até 5 s para utilizar o dado
//sleep(1.f);

}

void pensar_dado(int escritor)
{
printf("\nEscritor %d pensando em dado", escritor);

sleep(rand()%5); //demora até 5 s para pensar no dado

}

void escrever_dado(int escritor)
{

dado = dado + escritor; //soma o dado ao número do escritor
printf("\nEscritor %d escreveu novo dado: %d", escritor, dado);
}

Para facilitar a forma de verificar se o código é válido foi definido que os escritores, ao acessar o dado, fará somente somar o dado antigo ao número do escritor. Assim, para verificar se está funcionando basta ver que o dado acessado pelpos leitores sempre cresce de acordo com o número do ultimo escritor que o modificou. O resiltado abaixo confirma o funciomento correto:


Escritor 0 pensando em dado
Escritor 1 pensando em dado
Escritor 2 pensando em dado
Leitor 0 leu dado: 0
Leitor 0 utilizando dado
Leitor 0 leu dado: 0
Leitor 0 utilizando dado
Leitor 1 leu dado: 0
Leitor 1 utilizando dado
Leitor 1 leu dado: 0
Leitor 1 utilizando dado
Leitor 2 leu dado: 0
Leitor 2 utilizando dado
Leitor 3 leu dado: 0
Leitor 3 utilizando dado
Escritor 1 escreveu novo dado: 1
Escritor 1 pensando em dado
Leitor 1 leu dado: 1
Leitor 1 utilizando dado
Escritor 1 escreveu novo dado: 2
Escritor 1 pensando em dado
Escritor 2 escreveu novo dado: 4
Escritor 2 pensando em dado
Escritor 2 escreveu novo dado: 6
Escritor 2 pensando em dado
Leitor 2 leu dado: 6
Leitor 2 utilizando dado
Escritor 0 escreveu novo dado: 6
Escritor 0 pensando em dado
Leitor 0 leu dado: 6
Leitor 0 utilizando dado
Leitor 0 leu dado: 6
Leitor 0 utilizando dado
Leitor 1 leu dado: 6
Leitor 1 utilizando dado
Escritor 0 escreveu novo dado: 6
Escritor 0 pensando em dado
Escritor 1 escreveu novo dado: 7
Escritor 1 pensando em dado
Leitor 0 leu dado: 7
Leitor 0 utilizando dado
Leitor 3 leu dado: 7
Leitor 3 utilizando dado
Escritor 0 escreveu novo dado: 7
Escritor 0 pensando em dado
Escritor 1 escreveu novo dado: 8
Escritor 1 pensando em dado
Leitor 1 leu dado: 8
Leitor 1 utilizando dado
Leitor 1 leu dado: 8
Leitor 1 utilizando dado
Leitor 2 leu dado: 8
Leitor 2 utilizando dado
Escritor 2 escreveu novo dado: 10
Escritor 2 pensando em dado
Leitor 3 leu dado: 10
Leitor 3 utilizando dado
Leitor 3 leu dado: 10
Leitor 3 utilizando dado
Escritor 1 escreveu novo dado: 11
Escritor 1 pensando em dado
Leitor 0 leu dado: 11
Leitor 0 utilizando dado
Leitor 1 leu dado: 11
Leitor 1 utilizando dado
Escritor 2 escreveu novo dado: 13
Escritor 2 pensando em dado
Leitor 2 leu dado: 13
Leitor 2 utilizando dado
Escritor 0 escreveu novo dado: 13
Escritor 0 pensando em dado
Escritor 1 escreveu novo dado: 14
Escritor 1 pensando em dado
Leitor 0 leu dado: 14
Leitor 0 utilizando dado
Escritor 1 escreveu novo dado: 15
Escritor 1 pensando em dado
Leitor 0 leu dado: 15
Leitor 0 utilizando dado
Leitor 2 leu dado: 15
Leitor 1 leu dado: 15
Leitor 1 utilizando dado
Leitor 2 utilizando dado
Leitor 3 leu dado: 15
Leitor 3 utilizando dado
Leitor 0 leu dado: 15
Leitor 0 utilizando dado
Escritor 0 escreveu novo dado: 15
Escritor 0 pensando em dado
Escritor 1 escreveu novo dado: 16
Escritor 1 pensando em dado
Escritor 2 escreveu novo dado: 18
Escritor 2 pensando em dado
Leitor 2 leu dado: 18
Leitor 2 utilizando dado
Leitor 2 leu dado: 18
Leitor 2 utilizando dado
Leitor 2 leu dado: 18

O Problema do Barbeiro Adormecido

Outro problema clássico de CIP consistem em uma barbearia com um barbeiro, um série de cadeiras e clientes. Os pontos abaixo definem o problema:
- Cada vez que o barbeiro termina de cortar um cabelo e não existe clientes esperando, ele adormece.
- Cada vez que um cliente chega à barbearia e vê que nem uma cadeira está vazia ele não entra na barbearia e vai embora
- Quando um consumidor que está sentado na cadeira esperando vê que o barbeiro terminou de cortar um cabelo, ele tenta ser o próximo a ter o cabelo cortado.
A problemática consiste em programar consumidores e barbeio evitando condições de corrida.
A solução aplicada utiliza-se de três semáforos:

clientes - conta o número de clientes;
barbeiros - conta o número de barbeiros disponíveis.
mutex - para realizar exclusão múltipla para acesso da variável que define o número de clientes esperando;

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

#define CADEIRAS 5 //numero de cadeiras

sem_t clientes; //semaforo para numero de clientes
sem_t barbeiros; //semaforo para numero de barbeiros
sem_t mutex; //mutex para acesso à numero de clientes esperando
int n_espera = 0; //numero de clientes esperando

pthread_t t_barbeiro; //thread para o barbeiro
int n_cortados = 0; // numero de cabelos cortados

void cabelo_cortado(int i_con);

void cortar_cabelo();
void *barbeiro ();
void *consumidor (void *i_cons);

main()
{

int res; //variáveis para controle de loop e validação da criação de threads e semaforos
int j;


//criação do semáforo mutex
res = sem_init(&mutex, 0, 1);

if (res!= 0 ){
perror("\nFalha na criacao de mutex");

exit(EXIT_FAILURE);
}

//criação do semáfor de clientes
res = sem_init(&clientes, 0, 0);

if (res!= 0 ){
perror("\nFalha na criacao do semaforo de clientes");

exit(EXIT_FAILURE);
}

//Iniciação da semáforo de barbeiro
res = sem_init(&barbeiros, 0, 0);

if (res!= 0 ){
perror("\nFalha no semaforo de barbeiros");

exit(EXIT_FAILURE);
}

//Criação da thread do barbeiro
res = pthread_create(&t_barbeiro, NULL, barbeiro, (void *)&j);
if (res!= 0 ){

perror("\nFalha na criacao da thread de barbeiro");
exit(EXIT_FAILURE);
}

int n = 20;// numero de clientes

void *resultado_thread[n];
void *resultado_thread_barbeiro;
pthread_t t[n]; //vetor das threads

int aux[n];

//criação das threads
for (j = 0 ; j<n; j++)
{

aux[j] = j;
sleep(2.f); //intervalo entre a chegada de consumdores
res = pthread_create(&t[aux[j]], NULL, consumidor, (void *)&aux[j]);
if (res!= 0 ){

perror("\nFalha na criacao da thread");
exit(EXIT_FAILURE);
}


}

//join na thread do barbeiro
res = pthread_join(t_barbeiro, &resultado_thread_barbeiro);
if (res!= 0 ){

perror("\nFalha no thread join");
exit(EXIT_FAILURE);

}

//join nas threads de clientes
for (j = 0 ; j<n; j++)
{
res = pthread_join(t[j], &resultado_thread[j] );
if (res!= 0 )
{

perror("\nFalha no thread join do consumidor" );
exit(EXIT_FAILURE);
}
}
return 0;
}


//função da thread do barbeiro
void *barbeiro()
{

while (1) {
sem_wait(&clientes); //dorme se clientes for 0

sem_wait(&mutex); // pega acesso ao numero de clientes esperando
n_espera = n_espera +(-1); //decrementa clientes

sem_post(&barbeiros); // o barbeiro está livre
sem_post(&mutex); //libera o acesso ao numero de clientes esperando
cortar_cabelo(); //corta o cabelo

}
pthread_exit("exit from thread");
}

void *consumidor(void *i_con)
{

int i = *(int *)i_con;
sem_wait(&mutex); //pega acesso exclusivo ào numero de clientes esperando

if (n_espera < CADEIRAS) { //verifica se tem cadeiras vagas
n_espera = n_espera + 1; //entra e incrementa numero de clientes esperando

printf("\nConsumidor %d entra na barbearia", i);
sem_post(&clientes); //acorda barbeiro se necessário
sem_post(&mutex); //libera acesso exclusivo à numero de clientes esperando

sem_wait(&barbeiros); //dorme se o barbeiro não está disponivel
cabelo_cortado(i); //se levanta e corta o cabelo
} else {

printf("\nConsumidor %d viu que estava cheiro e foi embora", i);
sem_post(&mutex); //se não possui espaço vai embroa
}

pthread_exit("exit from thread");
}

void cabelo_cortado(int i_con){
printf("\nConsumidor %d foi cortar o cabelo", i_con);
}

void cortar_cabelo(){
n_cortados++;
sleep(3.f);
printf("\nBarbeiro terminou corte de cabelo n %d", n_cortados);
}

No primeiro teste realizado, foram produzidos 20 clientes com intervalo de 2 s entre eles e o corte durando 3 s, assim a maior parte deles teve o cabelo cortado. O resultado abaixo confirma o esperado.


Consumidor 0 entra na barbearia
Consumidor 0 foi cortar o cabelo
Consumidor 1 entra na barbearia
Barbeiro terminou corte de cabelo n 1
Consumidor 1 foi cortar o cabelo
Consumidor 2 entra na barbearia
Barbeiro terminou corte de cabelo n 2
Consumidor 2 foi cortar o cabelo
Consumidor 3 entra na barbearia
Consumidor 4 entra na barbearia
Barbeiro terminou corte de cabelo n 3
Consumidor 3 foi cortar o cabelo
Consumidor 5 entra na barbearia
Barbeiro terminou corte de cabelo n 4
Consumidor 4 foi cortar o cabelo
Consumidor 6 entra na barbearia
Consumidor 7 entra na barbearia
Barbeiro terminou corte de cabelo n 5
Consumidor 5 foi cortar o cabelo
Consumidor 8 entra na barbearia
Barbeiro terminou corte de cabelo n 6
Consumidor 6 foi cortar o cabelo
Consumidor 9 entra na barbearia
Consumidor 10 entra na barbearia
Barbeiro terminou corte de cabelo n 7
Consumidor 7 foi cortar o cabelo
Consumidor 11 entra na barbearia
Barbeiro terminou corte de cabelo n 8
Consumidor 8 foi cortar o cabelo
Consumidor 12 entra na barbearia
Consumidor 13 entra na barbearia
Barbeiro terminou corte de cabelo n 9
Consumidor 9 foi cortar o cabelo
Consumidor 14 entra na barbearia
Barbeiro terminou corte de cabelo n 10
Consumidor 10 foi cortar o cabelo
Consumidor 15 entra na barbearia
Consumidor 16 viu que estava cheiro e foi embora
Barbeiro terminou corte de cabelo n 11
Consumidor 11 foi cortar o cabelo
Consumidor 17 entra na barbearia
Barbeiro terminou corte de cabelo n 12
Consumidor 12 foi cortar o cabelo
Consumidor 18 entra na barbearia
Consumidor 19 viu que estava cheiro e foi embora
Barbeiro terminou corte de cabelo n 13
Consumidor 13 foi cortar o cabelo
Barbeiro terminou corte de cabelo n 14
Consumidor 14 foi cortar o cabelo
Barbeiro terminou corte de cabelo n 15
Consumidor 15 foi cortar o cabelo
Barbeiro terminou corte de cabelo n 16
Consumidor 17 foi cortar o cabelo
Barbeiro terminou corte de cabelo n 17
Consumidor 18 foi cortar o cabelo

O segundo teste foi feito produzindo-se todos os clientes sem intervalo. O esperado é que o primeiro cliente entre na barbearia e tenha logo seu cabelo, os próximos cinco entram ficam esperando até cortar o cabelo e os demais chegam à barbearia mas vão embora quando vêem que não tem cadeira vazia. O resultado abaixo confirma o esperado:

Consumidor 0 entra na barbearia
Consumidor 0 foi cortar o cabelo
Consumidor 1 entra na barbearia
Consumidor 2 entra na barbearia
Consumidor 3 entra na barbearia
Consumidor 4 entra na barbearia
Consumidor 5 entra na barbearia
Consumidor 6 viu que estava cheiro e foi embora
Consumidor 7 viu que estava cheiro e foi embora
Consumidor 8 viu que estava cheiro e foi embora
Consumidor 9 viu que estava cheiro e foi embora
Consumidor 10 viu que estava cheiro e foi embora
Consumidor 11 viu que estava cheiro e foi embora
Consumidor 12 viu que estava cheiro e foi embora
Consumidor 13 viu que estava cheiro e foi embora
Consumidor 14 viu que estava cheiro e foi embora
Consumidor 15 viu que estava cheiro e foi embora
Consumidor 16 viu que estava cheiro e foi embora
Consumidor 17 viu que estava cheiro e foi embora
Consumidor 18 viu que estava cheiro e foi embora
Consumidor 19 viu que estava cheiro e foi embora
Barbeiro terminou corte de cabelo n 1
Consumidor 1 foi cortar o cabelo
Barbeiro terminou corte de cabelo n 2
Consumidor 2 foi cortar o cabelo
Barbeiro terminou corte de cabelo n 3
Consumidor 3 foi cortar o cabelo
Barbeiro terminou corte de cabelo n 4
Consumidor 4 foi cortar o cabelo
Barbeiro terminou corte de cabelo n 5
Consumidor 5 foi cortar o cabelo

Problema do Jantar dos Filósofos

O Problema do Jantar dos Filósofos é um dos problemas clássicos de CIP. Consiste basicamente em uma mesa redonda com N pratos e um garfo entre cada dois pratos. Cada filósofo se posiciona em frente de cada prato e sua vida alterna entre dois estados, comer e pensar. Para comer é necessário a utilização de dos dois garfos ao lado do prato do filósofo. Quando está com fome, o filósofo tenta pegar o garfo de um lado e, se conseguir, pega o outro garfo e come. Após um tempo, ele colocar os garfos de volta a mesa e volta à pensar. A solução para o problema consiste em fazer com que nenhum filósofo fique esperando eternamente para pegar os garfos.
A solução apresentada aqui utiliza uma atribuição de um dos três estados aos filósofos: comendo, pensando e com fome. O filósofo só passa para o estado comendo caso os dois vizinhos não estajam comendo.

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

#define N 5 //numeor de filosofos
#define ESQUERDO (i+N+(-1))%(N) //indice do vizinho esquerdo
#define DIREITO (i+1)%N //indice do vizinho direto
#define PENSANDO 0 //estado pensando
#define FOME 1 //estado com fome
#define COMENDO 2 //estado comendo

int estado[N]; //vetor que guarda estado dos filosfos
sem_t mutex; //mutex para regiões críticas
sem_t s[N]; //semáforo para cada filósofo

pthread_t t[N]; //vetor de threads para filósofos

void pegar_garfos(int i);
void devolver_garfos(int i) ;

void testar(int i);
void pensar(int i);

void comer(int i);
void *filosofo (void *arg);

void imprime_estados();


int main(int argc, char *argv){


//variáveis para criação e validação das threadas
int res;
int j;
void *resultado_thread[N];


//criação de mutex
res = sem_init(&mutex, 0, 1);

if (res!= 0 ){
perror("\nFalha no semaforo");

exit(EXIT_FAILURE);
}
else printf("\n Mutex criado");

//criação do vetor de semáforos
for(j = 0; j<5; j++){

res = sem_init(&s[j], 0, 0);
if (res!= 0 ){

perror("\nFalha no semaforo");
exit(EXIT_FAILURE);
}
else printf("\nSemaforo %d criado", j);
}
//criação das threadas dos filósofos

int aux[5];
for(j = 0; j<5; j++){

aux[j] = j;
estado[j] = PENSANDO;
res = pthread_create(&t[j], NULL, filosofo, (void *)&aux[j]);
if (res!= 0 ){

perror("\nFalha na criacao da thread");
exit(EXIT_FAILURE);
}
else printf("\n Thread do filósofo %d criado", j);
}

//join nas threads dos filósofos

for(j = 0; j<5; j++){

res = pthread_join(t[j], &resultado_thread[j] );
if (res!= 0 ){

perror("\nFalha no thread join");
exit(EXIT_FAILURE);

}
}
return 0;
}

void *filosofo (void *arg)
{
int i = *(int *)arg;

while (1) { //loop infinito
pensar(i); //filósofo pensando
pegar_garfos(i); //faz tentativa de pegar garfos até conseguir

comer(i); //come
devolver_garfos(i); //devolve garfos a mesa
}

pthread_exit("exit from thread");
}

void pegar_garfos(int i) //i é o identificador do filósofo

{
sem_wait(&mutex); //entra na região crítica
estado[i] = FOME; //muda estado para fome

testar(i); //vê se é possível pegar garfos
sem_post(&mutex); //sai da região crítica
sem_wait(&s[i]); //fica bloqueado caso não tenha pego os garfos

}

void devolver_garfos(int i)
{
sem_wait(&mutex); //entra na região crítica

estado[i] = PENSANDO; //muda estado para pensando
testar(ESQUERDO); //ve se o vizinho esquerdo pode comer

testar(DIREITO); //ve se o vizinho direto pode comer
sem_post(&mutex); //sai da região critica
}

void testar(int i) /* i: filosofo number, from 0 to N−1 */
{
if (estado[i] == FOME && estado[ESQUERDO] != COMENDO && estado[DIREITO] != COMENDO) {

estado[i] = COMENDO;//come se estiver com fome e nenhum vizinho está comendo
imprime_estados(); //imprime estado dos filósofos para validar
sem_post(&s[i]);
}
}


void pensar(int i)
{
sleep(rand()%5);//pensa durante um tempo de 0 a 5 s

}

void comer(int i)
{
sleep(rand()%5);//come durante um tempo de 0 a 5s

}
void imprime_estados(){

printf("\nFilosofos: 0 1 2 3 4");
printf("\n ");

int j;
char e;
for(j = 0; j<N; j++){

if (estado[j] == PENSANDO) e = 'P';

else if (estado[j] == COMENDO) e = 'C';

else e = 'F';
printf("%c ",e);
}
}


Abaixo segue o resultado do teste realizado. São exibidos o estado de cada filósofo representado pelos caracteres:
'C' - o filósofo está comendo;
'F' - o filósofo está com fome;
'P' - o filósofo está pensando;


Mutex criado
Semaforo 0 criado
Semaforo 1 criado
Semaforo 2 criado
Semaforo 3 criado
Semaforo 4 criado
Thread do filósofo 0 criado
Thread do filósofo 1 criado
Thread do filósofo 2 criado
Filosofos: 0 1 2 3 4
P P P C P
Thread do filósofo 3 criado
Thread do filósofo 4 criado
Filosofos: 0 1 2 3 4
P C P C F
Filosofos: 0 1 2 3 4
C P F C F
Filosofos: 0 1 2 3 4
C P C P F
Filosofos: 0 1 2 3 4
C F P C F
Filosofos: 0 1 2 3 4
C F C P F
Filosofos: 0 1 2 3 4
P F C P C
Filosofos: 0 1 2 3 4
C F C P P
Filosofos: 0 1 2 3 4
P C P F P
Filosofos: 0 1 2 3 4
P C P C P
Filosofos: 0 1 2 3 4
C P P C F
Filosofos: 0 1 2 3 4
C P C P F
Filosofos: 0 1 2 3 4
P F P P C
Filosofos: 0 1 2 3 4
P C P P C
Filosofos: 0 1 2 3 4
P P C P C
Filosofos: 0 1 2 3 4
C P C F P


O teste mostra que em nenhum momento existem filósofos adjacentes comendo, sempre o vizinho de um filósofo comento está pensando ou com fome.