Problema dos Leitores e Escritores utilizando Mutex e Semáforos

O problema dos Leitores e Escritores trata a situação em que várias threads devem acessar a mesma memória compartilhada. Alguns para ler e outros para escrever.
Contudo, existem algumas restrições para realizarmos a leitura e escrita:
- Enquanto um processo estiver escrevendo, nenhum outro processo pode acessar este espaço de memória.
- Enquanto um processo estiver lendo, somente processos querendo ler podem acessar este espaço de memória.

Este problema pode ser abordado de várias formas. Em uma das abordagens, damos preferência ao escritor, ou seja, o escritor, uma vez desejando acesso à memória compartilhada, a obtém mesmo que processos leitores estivessem esperando antes.
Em outra abordagem, damos preferência aos leitores, ou seja, o escritor só obtem acesso à memória compartilhada quando um todos os escritores liberam o acesso. Esta situação é perigosa e pode levar a um starvation do escritor no caso em que temos vários processos leitores.

Em nossa solução, daremos preferência aos leitores.
Para aprender mais sobre este problema, visite: http://en.wikipedia.org/wiki/Readers-writers_problem

Além disso, nossa solução utiliza uma geração de valores randômicos para simular os tempos que o escritor levará para pensar no que irá escrever e o tempo que demora escrevendo na base de dados. E o consumidor terá valores randômicos para simular o tempo em que fica no banco de dados e o tempo em que fica processando as informações adquiridas.

Utilizaremos as instruções pthread_mutex_lock e pthread_mutex_unlock para controlar o acesso às regiões críticas. Documentação do uso pode ser encontrada em: http://www.opengroup.org/onlinepubs/007908775/xsh/pthread_mutex_unlock.html
Para criar estes semáforos, vamos utilizar os seguintes comandos pthread_t e pthrad_mutex_init:
http://opengroup.org/onlinepubs/007908775/xsh/pthread_mutex_init.html


Além disso, devemos criar as threads. Isto pode ser feito utilizando os seguintes comandos:
declaração: pthread_t
criação: pthread_create() - http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_create.html

Aqui, é interessante notar que ao criarmos a thread, ela inicia sua execução. Contudo, a thread principal não pára sua execução! Assim, é necessário utilizarmos o comando pthread_join para evitar que a thread principal termine o programa, e com isso, mate todas as outras threads.
pthread_join() - http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_join.html



Para compilar o programa e gerar o executável, utilizaremos:
gcc [[nome_programa.c]] -o [[nome_programa]] -lpthread
Para executar o programa criado, utilizaremos:
./[[nome_programa]]

Utilizamos o seguinte código:

//Bibliotecas utilizadas
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>

#include <semaphore.h>

#define READERS    20       //quantidade de leitores
#define WRITERS    3        //quantidade de escritores



pthread_mutex_t db;         //exclusao mutua para regioes criticas... controla o acesso ao banco de dados
pthread_mutex_t mutex;      //exclusao mutua para regioes cri­ticas... controla o acesso a variável rc
int   rc;                   //quantidade de leitores lendo ou querendo ler a base de dados


// prototipos-------------------------------------

void read_data_base(void);
void use_data_read(void);
void think_up_data(void);

void write_data_base(void);


void reader() {
while (1) {  /* repete eternamente */

  pthread_mutex_lock(&mutex);           //down(&mutex); garante acesso exclusivo a variavelrc
      rc=rc+1;                              //um novo leitor

      if(rc==1)  pthread_mutex_lock(&db);   //caso este seja o primeiro leitor...
      pthread_mutex_unlock(&mutex);         //up(&mutex); libera o acesso a variavel rc

      read_data_base();                     //le a base de dados
      pthread_mutex_lock(&mutex);           //down(&mutex); garante acesso exclusivo a variavel rc
      rc=rc-1;                              //um leitor a menos...

      if(rc==0) pthread_mutex_unlock(&db);  //caso este seja o ultimo leitor...
      pthread_mutex_unlock(&mutex);         //up(&mutex); libera o acesso a variavel rc

      use_data_read();                      //utiliza as informacoes da base de dados para algum trabalho...
    }
}

void writer() {

while(1)            //repete eternamente

    {
    think_up_data();            //pensa em informações para adicionar a base de dados
        pthread_mutex_lock(&db);    //down(&db); garante acesso exclusivo a base de dados
        write_data_base();          //escreve novas informacoes na base de dados

        pthread_mutex_unlock(&db);  //up(&db); libera o acesso a base de dados
    }
}

void read_data_base()
{

/*quanto tempo o leitor permanecerá lendo a base de dados*/
int readingtime;
readingtime = rand() % 3;

printf("Usuário lendo banco de dados. Total de %d leitores lendo agora.\n",rc);
sleep(readingtime);
}
void use_data_read()
{

/*quanto tempo o leitor permanecerá utilizando os dados lidos*/
int usetime;
usetime = rand() % 20;

printf("Usuário utilizando conhecimento adquirido no banco de dados\n");
sleep(usetime);
}
void think_up_data()
{

/*quanto tempo o escritor gasta pensando no que irá escrever*/
int thinktime;
thinktime = rand() % 10;

printf("Escritor pensando no que irá escrever\n");
sleep(thinktime);
}
void write_data_base()
{

/*quanto tempo o escritor gasta escrevendo na base de dados*/
int writetime;
writetime = rand() % 6;

printf("Escritor escrevendo no banco de dados\n");
sleep(writetime);
}


/////MAIN FUNCTION///////////////////////////////
main()
{

pthread_t writerthreads[WRITERS], readerthreads[READERS]; 
int i;

//inicializacao dos semaforos...
    pthread_mutex_init(&db, NULL);
pthread_mutex_init(&mutex, NULL);


//criação das threads independentes de escritores...
    for(i=0;i<WRITERS;i++){
    pthread_create( &writerthreads[i], NULL,(void *) writer, NULL);
}

//criação das threads independentes de leitores...
    for(i=0;i<READERS;i++){
    pthread_create( &readerthreads[i], NULL,(void *) reader, NULL);
}


for(i=0;i<WRITERS;i++){
    pthread_join(writerthreads[i], NULL);
}

for(i=0;i<READERS;i++){
    pthread_join(readerthreads[i], NULL);
}


exit(0);
}

Assim, obtivemos o seguinte resultado:
andersonaiziro@Aaiziro:~/Documents$ ./reader_writer
Escritor pensando no que irá escrever
Escritor pensando no que irá escrever
Escritor pensando no que irá escrever
Usuário lendo banco de dados. Total de 1 leitores lendo agora.
Usuário lendo banco de dados. Total de 2 leitores lendo agora.
Usuário lendo banco de dados. Total de 3 leitores lendo agora.
Usuário lendo banco de dados. Total de 4 leitores lendo agora.
Usuário lendo banco de dados. Total de 5 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 5 leitores lendo agora.
Usuário lendo banco de dados. Total de 6 leitores lendo agora.
Usuário lendo banco de dados. Total de 7 leitores lendo agora.
Usuário lendo banco de dados. Total de 8 leitores lendo agora.
Usuário lendo banco de dados. Total de 9 leitores lendo agora.
Usuário lendo banco de dados. Total de 10 leitores lendo agora.
Usuário lendo banco de dados. Total de 11 leitores lendo agora.
Usuário lendo banco de dados. Total de 12 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 12 leitores lendo agora.
Usuário lendo banco de dados. Total de 13 leitores lendo agora.
Usuário lendo banco de dados. Total de 14 leitores lendo agora.
Usuário lendo banco de dados. Total de 15 leitores lendo agora.
Usuário lendo banco de dados. Total de 16 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 16 leitores lendo agora.
Usuário lendo banco de dados. Total de 17 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Escritor escrevendo no banco de dados
Escritor pensando no que irá escrever
Usuário lendo banco de dados. Total de 1 leitores lendo agora.
Usuário lendo banco de dados. Total de 2 leitores lendo agora.
Usuário lendo banco de dados. Total de 3 leitores lendo agora.
Usuário lendo banco de dados. Total de 4 leitores lendo agora.
Usuário lendo banco de dados. Total de 5 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 5 leitores lendo agora.
Usuário lendo banco de dados. Total de 6 leitores lendo agora.
Usuário lendo banco de dados. Total de 7 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 5 leitores lendo agora.
Usuário lendo banco de dados. Total de 6 leitores lendo agora.
Usuário lendo banco de dados. Total de 7 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 3 leitores lendo agora.
Usuário lendo banco de dados. Total de 4 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 4 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 3 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Usuário utilizando conhecimento adquirido no banco de dados
Escritor escrevendo no banco de dados
Escritor pensando no que irá escrever
Escritor escrevendo no banco de dados
Escritor pensando no que irá escrever
Escritor escrevendo no banco de dados
Escritor pensando no que irá escrever
Usuário lendo banco de dados. Total de 1 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 1 leitores lendo agora.
Usuário lendo banco de dados. Total de 2 leitores lendo agora.
Usuário lendo banco de dados. Total de 3 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 3 leitores lendo agora.
Usuário lendo banco de dados. Total de 4 leitores lendo agora.
Usuário lendo banco de dados. Total de 5 leitores lendo agora.
Usuário lendo banco de dados. Total de 6 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 6 leitores lendo agora.
Usuário lendo banco de dados. Total de 7 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 7 leitores lendo agora.
Usuário lendo banco de dados. Total de 8 leitores lendo agora.
Usuário lendo banco de dados. Total de 9 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados
Usuário lendo banco de dados. Total de 9 leitores lendo agora.
Usuário lendo banco de dados. Total de 10 leitores lendo agora.
Usuário utilizando conhecimento adquirido no banco de dados

Problema da Barbearia utilizando threads

O problema da Barbearia possui como objetivo manter o barbeiro trabalhando enquanto houver consumidores e descansando quando não há consumidores.
Quando um consumidor chega a barbearia, ele acorda o barbeiro para obter o corte de cabelo, ou senta-se nas cadeiras para esperar se o barbeiro estiver cortando o cabelo de outra pessoa. Caso todas as cadeiras da barbearia estejam ocupadas, o consumidor simplesmente deixa o local.


Este problema é interessante, pois devemos coordenar as atividades sem gerar condições de corrida. Uma solução falha pode resultar em problemas de starvation ou de deadlock entre os processos.
O deadlock é obtido quando o consumidor fica esperando o barbeiro e o barbeiro fica esperando o consumidor.
A situação de starvation é obtida quando os consumidores não possuem uma ordem para o corte de cabelo, assim pode haver a situação em que consumidores não obtem a chance de ter seu cabelo cortado, esperando para sempre.
Em nossa solução, vamos considerar um barbeiro e vários consumidores, chegando em intervalos de tempo randômicos. O barbeiro será uma thread e cada consumidor será outra thread. Teremos semáforos para garantir que situações de deadlock não ocorram. Além disso, consideramos que o tempo para o corte de cabelo será constante para todos os consumidores. Isto pode ser alterado!

Utilizaremos as instruções sem_wait e sem_post para controlar o acesso às regiões críticas. Documentação do uso pode ser encontrada em:
http://www.opengroup.org/onlinepubs/007908775/xsh/sem_wait.html

http://www.opengroup.org/onlinepubs/007908799/xsh/sem_post.html
Para criar estes semáforos, vamos utilizar os seguintes comandos sem_t e sem_init:
http://www.opengroup.org/onlinepubs/007908775/xsh/sem_init.html

Além disso, devemos criar as threads. Isto pode ser feito utilizando os seguintes comandos:
declaração: pthread_t
criação: pthread_create() - http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_create.html

Aqui, é interessante notar que ao criarmos a thread, ela inicia sua execução. Contudo, a thread principal não pára sua execução! Assim, é necessário utilizarmos o comando pthread_join para evitar que a thread principal termine o programa, e com isso, mate todas as outras threads.
pthread_join() - http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_join.html


Para aprender mais sobre este problema, visite: http://en.wikipedia.org/wiki/Sleeping_barber_problem

Utilizando o seguinte comando:
gcc [[nome_programa.c]] -o [[nome_programa]] -lpthread
compilamos o programa e geramos o arquivo executável.
Para executar o programa, utilizamos o seguinte comando:
./[[nome_programa]]

Utilizamos o seguinte código:

//Bibliotecas utilizadas...
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

#define CHAIRS 5           //quantidade de cadeiras na barbearia
#define CONSUMERS 100000    //quantidade total de clientes


/*
typedef   int semaphore; /*os semaforos sao um tipo especial de int
semaphore customers=0;  /*array para controlar o estado de todos
semaphore barbers=0;
semaphore mutex = 1;  /*exclusão mutua para regioes cri­ticas
semaphore s[N];   /*um semaforo por filosofo
*/

sem_t customers;    //semaforo para controlar os consumidores esperando pelo corte de cabel
sem_t barbers;      //semaforo para controlar os barbeiros esperando pelos consumidores
sem_t mutex;        //semaforo para exclusao mutua para regioes criticas
int waiting=0;


//prototipos...
void cut_hair();
void get_haircut();

void barber()
{

while(1)
{
if(waiting==0) printf("Barber esperando consumidores... \n"); //caso a quantidade de pessoas na barbearia seja 0

     sem_wait(&customers);   //down(&customers); dorme se a quantidade de consumidores for 0
     sem_wait(&mutex);       //down(&mutex); garante acesso exclusivo a variavel waiting
     waiting=waiting-1;      //diminui a quantidade de clientes esperando

     sem_post(&barbers);     //up(&barbers); um barbeiro esta pronto para realizar o corte de cabelo
     sem_post(&mutex);       //up(&mutex); libera o acesso a variavel waiting
     cut_hair();             //corta o cabelo do cliente

 }
}

void customer()
{
sem_wait(&mutex);           //down(&mutex); garante acesso exclusivo a variavel waiting

    if(waiting<CHAIRS)          //se nao houver cadeiras livres, vai embora...
    {
waiting = waiting + 1;  //aumenta a quantidade de clientes esperando

        printf("Mais um consumidor! Total de %d consumidores esperando\n",waiting);
sem_post(&customers);   //up(&customers);acorda o barbeiro avisando que temos um novo cliente
        sem_post(&mutex);       //up(&mutex); libera o acesso a variavel waiting

        sem_wait(&barbers);     //down(&barbers); espera se todos os barbeiros estiverem ocupados
        get_haircut();          //obtem corte de cabelo...
    }
else

{
printf("Cadeiras lotadas... vou embora\n");
sem_post(&mutex);
}
}

void cut_hair()
{

/*Barbeiro esta cortando cabelo*/
printf("Barber is cutting hair\n");
sleep(3);
return;
}

void get_haircut()
{
/*Cliente esta recebendo corte de cabelo*/
sleep(3);
return;
}

main()
{
pthread_t barberthread, consumerthread[CONSUMERS];

int i=0,sleeptime;


// Create independent threads each of which will execute function
/*To initialize a semaphore, use sem_init():
int sem_init(sem_t *sem, int pshared, unsigned int value);
sem_init(&sem_name, 0, 10);
*/
sem_init(&customers, 0, 0);

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

pthread_create( &barberthread, NULL,(void *) barber, NULL );

for(i=0;i<CONSUMERS;i++)
{
sleeptime = rand()%5;

sleep(sleeptime);
pthread_create(&consumerthread[i], NULL, (void *) customer, NULL);
}

pthread_join( barberthread, NULL);
for(i=0;i<CONSUMERS;i++){

pthread_join( consumerthread[i], NULL);
}

exit(0);
}

Assim, obtivemos o seguinte resultado:

andersonaiziro@Aaiziro:~/Documents$ ./sleepbarber
Barber esperando consumidores...
Mais um consumidor! Total de 1 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 1 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 1 consumidores esperando
Mais um consumidor! Total de 2 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 2 consumidores esperando
Mais um consumidor! Total de 3 consumidores esperando
Mais um consumidor! Total de 4 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 4 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 4 consumidores esperando
Mais um consumidor! Total de 5 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 5 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 5 consumidores esperando
Cadeiras lotadas... vou embora
Barber is cutting hair
Mais um consumidor! Total de 5 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 5 consumidores esperando
Cadeiras lotadas... vou embora
Cadeiras lotadas... vou embora
Barber is cutting hair
Mais um consumidor! Total de 5 consumidores esperando
Cadeiras lotadas... vou embora
Barber is cutting hair
Mais um consumidor! Total de 5 consumidores esperando
Cadeiras lotadas... vou embora
Barber is cutting hair
Mais um consumidor! Total de 5 consumidores esperando
Barber is cutting hair
Mais um consumidor! Total de 5 consumidores esperando
Barber is cutting hair

Jantar dos Filósofos utilizando threads

O problema dos filósofos consiste em 5 filósofos sentados em uma mesa circular, realizando duas tarefas: pensar ou comer. Enquanto comem, os filósofos não pensam e enquanto pensam, os filósofos não comem.
Na mesa circular, existe um prato de spaghetti para cada filósofo e existe 1 garfo entre cada dois pratos, exemplificado na imagem abaixo. Para comer, o filósofo necessita dos dois garfos (da sua esquerda e da sua direita).


Este problema também pode gerar um deadlock. Isto ocorre na seguinte situação: suponha que todos os filósofos desejem comer ao mesmo tempo. Assim, todos pegam o seu garfo da esquerda simultaneamente. Ao tentarem pegar o garfo da direita, todos os filósofos esperarão eternamente, pois cada filósofo está segurando um garfo.

Na seguinte solução, utilizaremos threads e semáforos. Uma thread para cada um dos filósofos e semáforos para garantir que situações de deadlock não ocorrerão.
Na solução, mantemos constante a quantidade de tempo que o filósofo permanece comendo e a quantidade de tempo que ele permanece pensando. Cada filósofo permanece em 3 estados: HUNGRY, EATING ou THINKING, explicados no código. Caso se deseje maior aleatoriedade na simulação, é possível alterar estes valores para randômicos, utilizando a função rand().

Utilizaremos as instruções sem_wait e sem_post para controlar o acesso às regiões críticas. Documentação do uso pode ser encontrada em:
http://www.opengroup.org/onlinepubs/007908775/xsh/sem_wait.html
http://www.opengroup.org/onlinepubs/007908799/xsh/sem_post.html

Para criar estes semáforos, vamos utilizar os seguintes comandos sem_t e sem_init:
http://www.opengroup.org/onlinepubs/007908775/xsh/sem_init.html

Além disso, devemos criar as threads. Isto pode ser feito utilizando os seguintes comandos:
declaração: pthread_t
criação: pthread_create() - http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_create.html

Aqui, é interessante notar que ao criarmos a thread, ela inicia sua execução. Contudo, a thread principal não pára sua execução! Assim, é necessário utilizarmos o comando pthread_join para evitar que a thread principal termine o programa, e com isso, mate todas as outras threads.
pthread_join() - http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_join.html

Para aprender mais sobre este problema, visite: http://en.wikipedia.org/wiki/Dining_philosophers_problem

O código obtido utilizado foi o seguinte:

//Bibliotecas utilizadas...
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>

#include <semaphore.h>


#define N 5  /* qtdade de filosofos */
#define LEFT (i+N-1)%N/* calculo do vizinho a esquerda de i */
#define RIGHT (i+1)%N   /* calculo do vizinho a direita de i */
#define THINKING 0 /* filosofo pensando */
#define HUNGRY 1 /* filosofo tentando pegar garfos */
#define EATING 2 /* filosofo comendo */
#define TRUE 1

sem_t s[N];                 //um semaforo por filosofo
sem_t mutex;                //exclusao mutua para regioes cri­ticas

int   state[N];        
//array para controlar o estado dos filosofos
pthread_t thread1, thread2, thread3, thread4, thread5;
//uma thread para cada filósofo


// prototipos...

void take_forks(int i);
void put_forks(int i);

void test(int i);
void think(int i);

void eat(int i);

/* i: numero do filosofo, de 0 a N-1 */

void philosopher(int i) {

while (TRUE) {  /* repete eternamente */
 think(i);  /* o filosofo esta pensando */

 take_forks(i); /* pega dois garfos ou bloqueia */
 eat(i);  /* come espaguete */
 put_forks(i); /* coloca os dois garfos de volta na mesa */

}
}

void take_forks(int i) {

sem_wait(&mutex);//down(&mutex); /* entra na regiao cri­tica */

    state[i] = HUNGRY; /* registra que o filosofo i esta com fome */
printf("philosopher %d HUNGRY\n",i);
test(i);  /* tenta pegar 2 garfos */

sem_post (&mutex);//up(&mutex);  /* sai da regiao cri­tica */
    sem_wait(&s[i]);//down(&s[i]); /* bloqueia se os garfos nao foram pegos */

}

void put_forks(i) {
sem_wait(&mutex); //down(&mutex); /* entra na regiao critica */

    state[i] = THINKING;/* o filosofo acabou de comer */
printf("philosopher %d THINKING\n",i);

test(LEFT);  /* verifica se o vizinho da esquerda pode comer agora */
test(RIGHT); /* verifica se o vizinho da direita pode comer agora */
sem_post(&mutex);//up(&mutex);  /* sai da regiao cri­tica */

}

void test(i) {  //testa se os filosofos vizinhos podem comer
     if (state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING){

   state[i] = EATING;
   printf("philosopher %d EATING\n",i);
   sem_post(&s[i]);//up(&s[i]);

     }
}

void think(int i) {
/*Filosofo esta pensando...*/
sleep(1);

return;
}

void eat(int i) {
/*Filosofo esta comendo...*/

sleep(1);
return;
}

//////////////MAIN FUNCTION////////////////////////
main()
{

int  iret1, iret2, iret3, iret4, iret5;

int i;
int p[N] ;

//inicialização dos semáforos...
int sem_init(sem_t *sem, int pshared, unsigned int value);
     for(i= 0; i < N ;i++ )
{

sem_init(&s[i], 0, 1);
 p[i] = i;
}

sem_init(&mutex, 0, 1);

// criação de threads independentes que executarao a funcao...

iret1 = pthread_create( &thread1, NULL,(void *) philosopher,
(int*)p[1]);

iret2 = pthread_create( &thread2, NULL,(void *) philosopher,
(int*)p[2]);

iret3 = pthread_create( &thread3, NULL,(void *) philosopher,
(int*)p[3]);

iret4 = pthread_create( &thread4, NULL,(void *) philosopher,
(int*)p[4]);

iret5 = pthread_create( &thread5, NULL,(void *) philosopher,
(int*)p[0]);

pthread_join( thread1, NULL);

pthread_join( thread2, NULL);
pthread_join( thread3, NULL);
pthread_join( thread4, NULL);

pthread_join( thread5, NULL);

exit(0);
}

Utilizamos o comando
gcc [[nome_programa.c]] -o [[nome_programa]] -lpthread
para compilar e criar o executável.
Para executar o programa, utilizamos o comando:
./[[nome_programa]]

Assim, obtivemos o seguinte resultado para o programa:

andersonaiziro@Aaiziro:~/Documents$ ./filosofos
philosopher 1 HUNGRY
philosopher 1 EATING
philosopher 2 HUNGRY
philosopher 3 HUNGRY
philosopher 3 EATING
philosopher 4 HUNGRY
philosopher 0 HUNGRY
philosopher 1 THINKING
philosopher 0 EATING
philosopher 2 THINKING
philosopher 3 THINKING
philosopher 4 THINKING
philosopher 0 THINKING
philosopher 1 HUNGRY
philosopher 1 EATING
philosopher 2 HUNGRY
philosopher 3 HUNGRY
philosopher 3 EATING
philosopher 4 HUNGRY
philosopher 0 HUNGRY
philosopher 1 THINKING
philosopher 0 EATING
philosopher 3 THINKING
philosopher 2 EATING
philosopher 0 THINKING
philosopher 4 EATING
philosopher 1 HUNGRY
philosopher 3 HUNGRY
philosopher 0 HUNGRY
philosopher 2 THINKING
philosopher 1 EATING
philosopher 4 THINKING
philosopher 3 EATING
philosopher 1 THINKING
philosopher 0 EATING
philosopher 3 THINKING
philosopher 0 THINKING
philosopher 2 HUNGRY
philosopher 2 EATING
philosopher 4 HUNGRY
philosopher 4 EATING

Para verificar o bom comportamento do sistema, basta perceber que não temos filósofos vizinhos comendo ao mesmo tempo.

Problema do Produtor-Consumidor utilizando pipes e processos

O problema do produtor-consumidor é um clássico problema que aborda a sincronização de múltiplos processos.

Este problema consiste de dois processos, o produtor e o consumidor, que compartilham uma memória (buffer). O produtor é responsável por gerar dados e colocá-los no buffer, repetindo estas ações inúmeras vezes. Enquanto isso, o consumidor remove/consome dados do buffer. Como o buffer possui um tamanho limitado, devemos garantir que o processo produtor não irá adicionar dados em um buffer cheio e que o consumidor não irá remover dados de um buffer vazio.

A solução para este problema consiste em colocar os processos para dormir enquanto uma das condições de parada valer. Se o buffer estiver cheio, o produtor dorme. Se o buffer estiver vazio, o consumidor dorme.

Um dos processos é responsável por acordar o outro processo. O produtor acorda o processo consumidor quando inserir dados no buffer; e o consumidor acorda o processo produtor quando remover dados do buffer.

Este problema torna-se interessante, pois soluções inadequadas resultam em um deadlock, ou seja, ambos processos estão dormindo.

Para aprender mais sobre este problema, visite: http://en.wikipedia.org/wiki/Producers-consumers_problem

Em nossa solução, podemos definir a quantidade de processos produtores e a quantidade de processos consumidores teremos. Definimos também a quantidade de pacotes que os produtores criarão e a capacidade máxima do pipe. Para criar os processos filhos, devemos utilizar a instrução fork() - http://www.opengroup.org/onlinepubs/000095399/functions/fork.html

Para produzir um novo produto, cada produtor levará um tempo randômico e para consumir cada produto, cada consumidor levará um tempo também randômico.

Os pipes são utilizados para permitir a comunicação inter-processos. Utilizando suas funções de read e write, conseguimos inserir um novo produto no pipe e remover um produto do pipe, sendo estas, funções realizadas por processos distintos.
Além disso, se desejamos escrever no pipe, devemos fechar a ponta de leitura. E, se desejamos ler do pipe, devemos fechar a ponta de escrita.
Maiores informações podem ser obtidas em: http://www.cs.cf.ac.uk/Dave/C/node23.html

Para compilar o programa e gerar o executável, utilizaremos:
gcc [[nome_programa.c]] -o [[nome_programa]] -lpthread
Para executar o programa criado, utilizaremos:
./[[nome_programa]]

Utilizamos o seguinte código:

//bibliotecas utilizadas...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


//define os lados de leitura e escrita dos pipes...
#define READ 0
#define WRITE 1

//define a quantidade de produtos produzidos pelos produtores e a quantidade de pacotes que um pipe suporta
#define MAX_PROD_PACKS  100
#define MAX_PIPE_PACKS  30

//define a quantidade de produtores e de consumidores
#define PRODUCERS   2
#define CONSUMERS   2


//definimos uma estrutura para os produtos a serem produzidos, armazenando o id do pai
typedef struct prod prod;

struct prod{int prodid;pid_t producerid;};

int fd[2];

int n;

//Prototipos...
void consume_prod(prod*);
prod produce_prod(int);


void producer()
{
int qtdade;
prod newprod;

close(fd[READ]); // Fecha o lado de leitura. Lado nao utilizado

for(qtdade=0;qtdade<MAX_PROD_PACKS;qtdade++){

   newprod = produce_prod(qtdade);               //produz novo item
        printf("Novo item produzido pelo processo %d! \n", getpid());

   write(fd[WRITE],&newprod,sizeof(prod)); // insere novo item no pipe    
    }

close (fd[WRITE]); // Fecha o lado utilizado
}

void consumer()
{

int qtdade;
int resp;
prod consumeprod;
close (fd[WRITE]); /* Fecha o lado de leitura que nao eh utilizado*/

while( 1 ){

   resp = read(fd[READ],&consumeprod,sizeof(prod));
   if(resp==-1){        
       printf("Erro na leitura do pipe\n");
   }

   else if(resp==0){
       printf("Pipe estah vazio... \n");
   }
   else{

       consume_prod(&consumeprod);
   }
}
close (fd[READ]); /* Fecha o lado utilizado*/

}

prod produce_prod(int n){
prod newprod;
int timetoproduce;

timetoproduce = rand()%7;
newprod.prodid = n;

newprod.producerid = getpid();
printf("Processo %d produzindo um novo produto\n",getpid());

sleep(timetoproduce);
return newprod;
}

void consume_prod(prod * t){

int timetoconsume;
timetoconsume=rand()%5;
printf("Processo %d consumindo produto %d do Produtor %d\n",getpid(),t->prodid,t->producerid);

sleep(timetoconsume);
}

void new_producer(){
int newprocess;

newprocess = fork();
if(newprocess==-1){
   printf("Erro na criacao do processo produtor\n");
}

else if(newprocess==0){
   producer();
   exit(0);
}

return;
}
void new_consumer(){
int newprocess;
newprocess = fork();

if(newprocess==-1){
   printf("Erro na criacao do processo consumidor\n");
}
else{

   consumer();
   exit(0);
}

}

int main(){

pipe(fd); //cria o pipe

int i;

/* Criação de Processos Produtores */
for( i=0;i<PRODUCERS;i++){

   new_producer(); 
}
/* Criação de Processos consumidores */
for(i=0;i<CONSUMERS;i++){

   new_consumer();
}
//o processo pai será um processo consumidor
  
exit(0);
}

Assim, obtivemos o seguinte resultado:

andersonaiziro@Aaiziro:~/Documents$ ./prod-cons
Processo 6743 produzindo um novo produto
Processo 6744 produzindo um novo produto
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6745 consumindo produto 0 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6746 consumindo produto 0 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6746 consumindo produto 1 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6742 consumindo produto 1 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6746 consumindo produto 2 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6745 consumindo produto 2 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6746 consumindo produto 3 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6745 consumindo produto 3 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6746 consumindo produto 4 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6742 consumindo produto 4 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6742 consumindo produto 5 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6746 consumindo produto 5 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6742 consumindo produto 6 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6746 consumindo produto 6 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6746 consumindo produto 7 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6745 consumindo produto 7 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6742 consumindo produto 8 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6745 consumindo produto 8 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Processo 6746 consumindo produto 9 do Produtor 6743
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6745 consumindo produto 9 do Produtor 6744
Novo item produzido pelo processo 6743!
Processo 6743 produzindo um novo produto
Novo item produzido pelo processo 6744!
Processo 6744 produzindo um novo produto
Processo 6742 consumindo produto 10 do Produtor 6743
Processo 6742 consumindo produto 10 do Produtor 6744

Verificado o funcionamento do programa, vamos criar os processos zumbis!

Para realizar tal tarefa, vamos inicialmente, identificar uma situação em que temos os processos zumbis. Ao realizar o comando fork(), criamos um processo filho. A morte do processo pai, acarreta na morte do processo filho. Por outro lado, a morte do processo filho deve ser informada ao processo pai. Se o processo pai estiver bloqueado, então o processo filho torna-se um processo zumbi.

Para fazer esta situação acontecer, vamos fazer o processo pai como um processo consumidor e vamos criar uma situação em que não temos mais produtos no pipe. Assim, o processo pai ficará bloqueado e o processo filho não conseguirá informar ao pai sobre seu término, tornando-se um processo zumbi.

Para verificar a situação dos processos, vamos utilizar o seguinte comando:

ps -ax

O resultado desta simulação foi:

A existência de processos zumbi é indicada pela letra Z+.

Motivação Inicial

Após um bimestre do curso de Sistemas Operacionais, ministrado pelo professor Edgar Toshiro Yano, temos condições para desenvolver programas para abordar diferentes soluções para problemas de sincronização de vários processos.

Nos posts seguintes abordaremos os seguintes conceitos: threads, criação de processos filhos, semáforos, mutex e pipes.

Para utilizar os conceitos acima, vamos desenvolver soluções para os seguintes problemas clássicos:

- Produtores e Consumidores ( http://en.wikipedia.org/wiki/Producers-consumers_problem)

- Jantar dos Filósofos (http://en.wikipedia.org/wiki/Dining_philosophers_problem)

- Barbeiro Sonolento (http://en.wikipedia.org/wiki/Sleeping_barber_problem)

- Leitores e Escritores (http://en.wikipedia.org/wiki/Readers-writers_problem)

Nestes problemas clássicos, os conceitos serão utilizados para criar soluções consistentes a todos estes programas. Soluções falhas a cada um desse problemas levam a condições de deadlock, problemas de corrida e starvation. Em um sistema operacional, estes problemas podem acarretar em um sério comprometimento de seu funcionamento e integridade. Assim, é necessário assegurar que tais situações não ocorrerão!
Mais informações sobre estes problemas podem ser encontrados abaixo:

Deadlock: http://en.wikipedia.org/wiki/Deadlock
Race Condition: http://en.wikipedia.org/wiki/Race_condition
Starvation: http://en.wikipedia.org/wiki/Resource_starvation

Além disso, uma boa referência bibliográfica é o livro:
MODERN OPERATING SYSTEMS 2nd ed - A.S.TANENBAUM