Produtores e Consumidores

O problema em questão possui um grau de abstração tão grande que pode ser aplicado nos mais diversificados setores, como a agricultura.

Neste problema, um conjunto de processos Produtores suprem de mensagens para um conjunto de processos consumidores. Estes processos compartilham uma fila de buffer comum onde mensagens são depositados pelos produtores e removidas pelos consumidores. Todos os processos são assíncronos no sentido de que produtores e consumidores podem depositar e remover mensagens a qualquer tempo. Duas condições tem de ser satisfeitas: Nenhum processo consumidor pode remover uma mensagem quando o buffer estiver vazio e nenhum processo produtor pode depositar uma mensagem com o buffer cheio.

Problemas de integridade podem aparecer se múltiplos consumidores (ou produtores) tentarem remover (ou inserir) mensagens no buffer ao mesmo tempo. Por exemplo, as estruturas de dados associadas (ponteiros para buffers) podem não ser atualizados consistentemente, ou dois produtores tentam colocar mensagens no mesmo buffer. O acesso ao buffer e as estruturas de dados associadas devem constituir uma seção crítica.

Bibliografia: http://www.jr.eti.br

Utilizei pipes na solução do problema, seguindo a proposta feita pelo Professor. Com o tempo extra fornecido pelo Professor, foi possível completar o código do programa. Os testes apresentaram bons resultados, como mostra o screenshot após o código. Poderia ter sido mais bem implementada a questão dos tempos entre produção e consumo dos produtos - incluindo tempos randômicos, por exemplo -, para refletir melhor uma situação real.

Abaixo, o código do programa:

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

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

#define NUMBER_PRODUCERS 2
#define NUMBER_CONSUMERS 2
#define NUMBER_PIPES 20
#define NUMBER_ITEMS 10 //number of items per pipe

#define TIME_PRODUCE 2 //time to make a new product
#define TIME_CONSUME 3 //time to consume a product

//defines which side of the pipe reads/writes
#define READ 0
#define WRITE 1

#define TRUE 1

typedef struct product product;

struct product {
int prod_id;
pid_t product_id;
};

int fd[2];

void cons_product(int,int);

void producer() {
 product new;

 int i;

 close(fd[READ]);

 for (i=0; i<NUMBER_ITEMS; i++) {

 
 /*new = prod_product(i);*/

//BEGINS prod_product
 new.prod_id = i;

 new.product_id = getpid();

 printf("Process #%d produces product #%d.\n",new.product_id, new.prod_id);

 sleep(TIME_PRODUCE);

//ENDS prod_product

 write(fd[WRITE], &new, sizeof(product));
 }

 close(fd[WRITE]);

}

void consumer() {
 product aux;

 int i;
 int ok_process;

 close(fd[WRITE]);

 while(TRUE) {
 ok_process = read(fd[READ], &aux, sizeof(product));

 if (ok_process < 0) printf("Could not read from pipe.\n");
 else  {

  if (ok_process == 0) printf("Empty pipe.\n");
  else cons_product(aux.product_id, aux.prod_id);
  }
 
 }

 close(fd[READ]);

 
}

product prod_product(int id){
 product new;

 
 new.prod_id = id;

 new.product_id = getpid();

 printf("Process #%d produces product #%d.\n",new.product_id, id);

 sleep(TIME_PRODUCE);

 return new;

}

void cons_product(int producer_process, int index){

 int consumer_number = getpid();

 printf("Process #%d consumes product #%d from producer #%d.\n", consumer_number, index, producer_process);

 sleep(TIME_CONSUME);

}

void call_new_producer(){
 int ok_process;

 ok_process = fork();

 if (ok_process == -1) {

  printf("Could not create a new process.");
  exit(-1);
  }

 else if (ok_process == 0) producer();

}

void call_new_consumer(){
 int ok_process;

 ok_process = fork();

 if (ok_process == -1) {
  printf("Could not create a new process.");

  exit(-1);
  }

 else consumer();
}

int main() {

 int i;

 pipe(fd);

 for (i=0; i<NUMBER_PRODUCERS; i++) call_new_producer();

 for (i=0; i<NUMBER_CONSUMERS; i++) call_new_consumer();

return 0;
}

Leitores e Escritores

O problema dos Leitores e Escritores é um dos mais conhecidos sobre Programação Concorrente. Este problema considera a existência de vários processos que tentam acessar a uma área de memória compartilhada, uns para ler, outros para escrever. O que se pretende é que um leitor e um escritor não colidam na sua atividade para que não se corra o risco de um ir ler o que outro ainda não acabou de escrever, ou de um escritor ir escrever sobre dados ainda não lidos pelo processo leitor.

No entanto, não parece haver impedimento algum para que, pelo menos os leitores, não possam aceder em simultâneo a referida área de memória compartilhada, bastando para tal que, um processo que pretenda ler, se certifique da presença de algum outro leitor ou da ausência de escritores.

O que não podemos permitir é que mais do que um escritor tenha acesso simultâneo. Isto poderia conduzir a uma alteração indevida do valor compartilhado.

Surge, então, um novo cenário em que vários leitores podem estar em simultâneo na seção crítica, enquanto que não se pode permitir a entrada a mais do que um escritor de cada vez, bem como a permanência simultânea de processos de tipos distintos (um leitor e um escritor, por exemplo). Variações a este caso, são a concessão de prioridade a leitores ou a escritores. Isto vem evitar que os leitores, por exemplo, ocupem de tal forma a seção compartilhada que não deixem espaço para que os escritores lá possam entrar.

O que é importante referir após a apresentação destes exemplos é que, além de termos de recorrer aos semáforos para controlar o acesso dos vários processos a memória compartilhada, temos também de garantir, nas várias versões apresentadas, uma exclusão mútua as variáveis auxiliares necessárias para o controle de entrada e saída.

Bibliografia: http://www.jr.eti.br

O trecho apresentado a seguir consiste em uma solução para uma versão simplificada do problema. Considerei que existiam 20 leitores e um escritor que desejam acessar a base de dados. Os tempos de leitura e escrita selecionados (vide começo do programa) encaminham o problema para a seguinte situação: o escritor entra antes dos leitores e lá fica durante o tempo de escrita; os leitores entram a seguir e não ocorre liberação para o escritor acessar novamente, já que ele não tem qualquer tipo de prioridade sobre os leitores. O programa está mostrado logo abaixo. Logo depois, um screenshot do funcionamento do programa está exibido para comprovar o que foi dito anteriormente.

#include<semaphore.h>
#include<pthread.h>

#include<math.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define NUMBER_READERS 20
#define TRUE 1
#define FALSE 0
#define READ_TIME 1
#define WRITE_TIME 3


pthread_mutex_t mutex;

pthread_mutex_t db;
int rc = 0;

void read_data_base(int i){

 printf("There are %d readers in the database.\n", i);
}

void write_data_base(){
 printf("There is a writer in the database.\n");
}

void reader(void) {
 while(TRUE) {
  pthread_mutex_lock(&mutex);

  rc++;
  if (rc == 1) pthread_mutex_lock(&db);

  pthread_mutex_unlock(&mutex);
  read_data_base(rc);
  sleep(READ_TIME);

  pthread_mutex_lock(&mutex);
  rc--;
  if (rc == 0) pthread_mutex_unlock(&db);

  pthread_mutex_unlock(&mutex);
 }  
}

void writer(void) {
 while(TRUE) {

  pthread_mutex_lock(&db);
  write_data_base();
  sleep(WRITE_TIME);
  pthread_mutex_unlock(&db); 
 }
}

void* call_writer(void* arg){
 writer();
}

void* call_reader(void* arg){
 reader();
}

int main() {

 int i;

 pthread_mutex_init(&mutex, NULL);
 pthread_mutex_init(&db, NULL);

 pthread_t mr_writer;
 pthread_create(&mr_writer, NULL, call_writer, NULL);

 pthread_t readers[NUMBER_READERS]; 
 for (i=0; i<NUMBER_READERS; i++) {

  pthread_create(&readers[i], NULL, call_reader, (void*) i);

  sleep(READ_TIME);  
  }

return 0;
}

Barbeiro Dorminhoco

O problema é análogo ao de manter um barbeiro trabalhando quando existem clientes, descansando quando há nenhum e fazendo tudo isso de uma forma ordenada. O barbeiro e seus clientes podem ser representados por seus referidos processos.
A seguir, um trecho em C que pode resolver mais esse problema. O problema foi ligeiramente simplificado:

• Supondo que apenas 25 clientes chegaram em intervalos regulares de um segundo;
• Supondo que o barbeiro leva dois segundos para fazer um corte;
• Supondo que a barbearia tem cinco cadeiras para os clientes aguardarem a vez, como ilustra a figura ao lado.
  

Considerando o que foi levantado, o trecho abaixo pode solucionar o problema enunciado:

#include<semaphore.h>
#include<pthread.h>

#include<math.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define CHAIRS 5

#define NUMBER_CUSTOMERS 25

#define TRUE 1
#define FALSE 0

#define NEW_CUSTOMER 1 //time between the arrival of two customers
#define HAIRCUT_TIME 2 //time to finish a haircut

sem_t customers, barbers, mutex;

int waiting = 0;

void cut_hair(){
 printf("Barber is working!! %d free chair(s)\n", CHAIRS-waiting);
}

void get_haircut(int i){
 printf("Customer #%d is getting a haircut!\n", i);
}

void barber(void){
 while(TRUE){
 sem_wait(&customers);

 sem_wait(&mutex);
 waiting--;
 sem_post(&mutex);
 sem_post(&barbers);

 cut_hair();
 sleep(HAIRCUT_TIME);
 }
}

void customer(int i){

 sem_wait(&mutex);
 if(waiting<CHAIRS) {
  waiting++;

  sem_post(&customers);
  sem_post(&mutex);
  sem_wait(&barbers);

  get_haircut(i);
  }
 else {
 sem_post(&mutex);

 printf("Barber shop is full! Customer #%d cannot wait!\n", i);
 }
}

void* call_barber(void* arg){

 barber();
}

void* call_new_customer(void* arg){
 customer( (int) arg);
}

int main() {
 int i; 
 sem_init(&customers, 0, 0);

 sem_init(&barbers, 0, 1);
 sem_init(&mutex, 0, 1);

 pthread_t mr_barber;
 pthread_create(&mr_barber, NULL, call_barber, NULL);

 pthread_t customer[NUMBER_CUSTOMERS];
 
 for (i=0; i<NUMBER_CUSTOMERS; i++) {

  printf("Customer #%d arrives! %d free chair(s)\n", i, CHAIRS-waiting);
  pthread_create(&customer[i], NULL, call_new_customer, (void*) i);

  sleep(NEW_CUSTOMER);  
  }

return 0;
}

A seguir, um screenshot para comprovar o bom funcionamento do programa desenvolvido.

Jantar dos Filósofos

O jantar dos filósofos, o mais famoso dos problemas clássicos de programação concorrente, apresenta, mais uma vez, a competição por um conjunto de recursos - neste caso os garfos. Na verdade, os filósofos não podem comer todos ao mesmo tempo já que não há "garfos" que cheguem para todos. Além disso é preciso garantir que os filósofos não se impeçam uns aos outros de comer entrando num deadlock.

Este problema consiste em cinco filósofos estão sentados em círculo, tentando comer espaguete com a ajuda de garfos. Cada filósofo possui uma bacia de massa mas há apenas cinco garfos, colocados um a direita e outro a esquerda de cada filósofo, para serem compartilhados entre eles. Isto cria um problema, pois ambos os garfos (direita e esquerda) são necessários para cada um dos filósofos poder comer. As alternativas dos filósofos compreendem duas fases: Pensar e Comer. No modo pensar, um filósofo não segura um garfo. Porém, quando está com fome(depois de ficar por um tempo finito no modo Pensar) o filósofo tenta pegar os dois garfos na direita e esquerda.

Cada filósofo recebe um número identificador. Para evitar situções de deadlock, todos os filósofos com número par tentam agarrar primeiro no garfo à sua esquerda e os ímpares tentam agarrar primeiro no garfo à direita.

(Bibliografia: http://www.jr.eti.br)

A seguir, um código em C para resolver esse clássico problema:

#include<semaphore.h>
#include<pthread.h>

#include<math.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

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

#define TRUE 1
#define FALSE 0

int state[N];

sem_t mutex;
sem_t s[N];

void test(int i){

if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {

state[i] = EATING;
sem_post(&s[i]);
}
}

void think(int i){
printf("Philosopher #%d says: I think, therefore I am.\n",i);
}

void eat(int i){
printf("Philosopher #%d enjoys his meal.\n",i);
}

void take_forks(int i) {
sem_wait(&mutex);
state[i] = HUNGRY;

test(i);
sem_post(&mutex);
sem_wait(&s[i]);
}

void put_forks(int i) {
sem_wait(&mutex);
state[i] = THINKING;

test(LEFT);
test(RIGHT);
sem_post(&mutex);
}

void philosopher(int i) {
while(TRUE) {
think(i);

// sleep(drand48()/10000);
  sleep(1);
take_forks(i);
eat(i);

// sleep(drand48()/10000);
  put_forks(i);
}
}

void* call_philosopher(void* arg){

/*int i = arg;*/
philosopher( (int) arg);
}

int main(){

int i;
pthread_t threads[N];

time_t t1;
time(&t1);

srand48((long) t1);

sem_init(&mutex, 0, 1);

for (i=0; i<N; i++) sem_init(&s[i], 0, 0);

for (i=0; i<N; i++) {
pthread_create(threads, NULL, call_philosopher, (void*) i);
}

for (i=0; i<N; i++) pthread_join(threads[i], NULL);


return 0;
}

A seguir, um screenshot para comprovar o bom funcionamento: