Neste artigo o nosso assunto central será a programação concorrente. Este paradigma foca-se principalmente na interação e execução de multitarefas, assim sendo, uma das principais preocupações quando nos deparamos com um algoritmo deste género são os problemas que podem ocorrer na sincronização e na partilha de recursos.
As vantagens da programação concorrente são o aumento do desempenho do programa, devido ao aumento da quantidade de tarefas que podem ser executadas durante um determinado período de tempo.
Ao longo das próximas linhas vamos debruçarmo-nos sobre alguns factos deste género de programação.
Como referimos há pouco, um dos principais problemas a ter em conta é o problema da sincronização. E podemos considerar vários casos neste problema, quer seja com ler e/ou escrever um ficheiro, partilhar recursos ou ter o problema do produtor-consumidor com um entrepósito limitado.
Mas antes de avançarmos, vamos recuar ainda um pouco atrás de modo a que o leitor se recorde e/ou familiarize mais simplesmente com esta temática.
A programação concorrente é um paradigma de programação usado na construção de programas de computador que fazem uso da execução concorrente de várias tarefas computacionais que podem ser implementadas como programas separados ou como um conjunto de threads criadas por um único programa. Nesta altura faz sentido diferenciar o termo processo do termo thread, enquanto que para executar um processo precisamos de uma pilha e de valores de registo que nos dizem o estado desse processo, uma thread é uma linha ou contexto de execução, ou seja é uma forma de um processo se dividir a si mesmo em duas ou mais tarefas que podem ser executadas concorrentemente.
As threads podem compartilhar o mesmo espaço de memória assim como podem partilhar as mesmas variáveis, ao contrário dos processos que têm as suas próprias variáveis, pilha e alocação de memória.
Por este motivo caro leitor, é fácil admitirmos que criar e finalizar uma thread é mais rápido e mais simples do que fazer a mesma operação utilizando processos. A comunicação entre threads é também mais simples que a comunicação entre processos, uma vez que as variáveis usadas são comuns.
As threads podem ser implementadas pelo programador ou ser implementadas automaticamente pelo kernel. Por exemplo, normalmente o Windows não escalona processos mas sim threads.
Algumas das operações mais usadas no âmbito das threads envolvem a criação de uma thread e a junção de threads (pthread_create e pthread_join).
Voltando então a uma das perguntas principais: Porque sincronizar?
Porque o acesso concorrente a dados e recursos partilhados pode criar uma situação de inconsistência desses mesmos recursos, isto porque as várias instâncias acedem e manipulam-nos de uma forma “simultânea”, dando azo a situações de inconsistência e de falha. Então para que uma rotina ou programa seja consistente são precisos mecanismos que assegurem a execução ordenada e correta dos processos cooperantes.
Um dos mecanismos computacionais que podemos usar para que não haja inconsistência de recursos são os semáforos. Um semáforo é uma variável, um mecanismo de sincronização sem espera ativa. Esta variável pode ser manipulada através de duas primitivas atómicas, isto é, que não podem ser interrompidas por processos.
A sua função é controlar o acesso a recursos partilhados num ambiente multitarefa. A invenção desse tipo de variável é atribuída a Edsger Dijkstra.
Quando declaramos um semáforo, o seu valor indica quantos processos (ou threads) podem ter acesso ao recurso partilhado. Assim, para partilhar um recurso o leitor deve verificar qual o valor do semáforo para saber qual a ação a executar.
Assim, e de forma a consolidar os conhecimentos, as principais operações sobre semáforos são:
- Inicialização
- Recebe como parâmetro um valor inteiro indicando a quantidade de processos que podem aceder a um determinado recurso.
- Operação wait
- Decrementa o valor do semáforo. Se o semáforo está com valor zero, o processo é posto em espera. Para receber um sinal, um processo executa o wait e bloqueia se o semáforo impedir a continuação da sua execução.
- Operação signal
- Se o semáforo estiver com o valor zero e existir algum processo em espera, um processo será acordado. Caso contrário, o valor do semáforo é incrementado. Para enviar um sinal, um processo executa um signal.
As operações de incrementar e decrementar devem ser operações atômicas, ou indivisíveis, isto é, a instrução deve ser executada na totalidade sem que haja interrupções. Enquanto um processo estiver a executar uma dessas duas operações, nenhum outro processo pode executar outra operação nesse mesmo semáforo, devendo esperar que o primeiro processo encerre a sua operação. Essa obrigação evita condições de disputa entre as várias threads.
Para evitar espera, o que desperdiça processamento da máquina, a operação wait utiliza uma estrutura de dados (geralmente uma FIFO). Quando um processo executa essa operação e o semáforo tem o seu valor a zero, este valor é posto na estrutura. Quando um outro processo executar a operação signal havendo processos nessa mesma estrutura, uma delas é retirada (no caso FIFO, é retirada a primeira que entrou).
Tendo em conta que há necessidade de garantir a consistência dos recursos, a utilização mais simples do semáforo é em situações na qual se utiliza o princípio da exclusão mútua, isto é, que só um processo é executado de cada vez. Para isso utiliza-se um semáforo binário, com inicialização em 1. Esse semáforo binário atua como um mutex.
O princípio da exclusão mútua ou mutex, é uma técnica usada em programação concorrente para evitar que dois processos ou threads tenham acesso simultaneamente a um recurso partilhado. Esta partilha dá origem à chamada secção crítica que pode ser protegida da seguinte forma:
pthread_mutex_lock() [secção critica] pthread_mutex_unlock()
Então, um meio simples para exclusão mútua é a utilização do tal semáforo binário, isto é, que só pode assumir dois valores distintos, 0 e 1. O fecho do semáforo deve ser feito antes de utilizar o recurso e deve ser libertado só depois do uso o recurso. Tendo em conta que apenas um processo pode entrar de cada vez na secção crítica, então os outros processos devem esperar pela sua vez.
Contudo o uso do princípio da exclusão mútua, pode originar alguns problemas, como por exemplo deadlocks ou starvation (inanição).
Um deadlock, ou bloqueio, é referente a uma situação em que existe um impasse entre dois ou mais processos, isto é, no nosso contexto, quando dois ou mais processos tentam aceder ao mesmo recurso, bloqueiam-se mutuamente impedindo a boa continuação do algoritmo.
Ocorre quando várias threads do conjunto estão à espera da libertação de um recurso por uma outra thread que, por sua vez, aguarda a libertação de outro recurso alocado ou dependente da primeira thread.
A starvation por seu lado, ocorre quando uma thread nunca é executada por estar à espera de uma resposta que uma outra thread supostamente lhe dará, contudo esta última thread por algum motivo (a thread pode morrer ou ficar bloqueada) nunca lhe dá a resposta esperada. Diz-se que neste caso a thread se torna um zombie, esperando uma resposta que possivelmente nunca terá.
Quando o escalonamento não é feito adequadamente, pode haver inanição. Uma solução para esta situação é a existência de um tempo máximo de espera.
A ocorrência da inanição dá-se também quando os programas entram em ciclo infinito (razão pela qual também se dá o nome de preterição indefinida a esta situação) e não fazem nenhum progresso no processamento, ao contrário do deadlock, que ocorre quando os processos permanecem bloqueados, dependendo da liberação dos recursos por eles alocados.
Após esta pequena explicação teórica, vamos caro leitor voltar ao algoritmo escolhido para fonte central deste artigo, o jantar dos filósofos. Este é considerado um problema clássico de programação concorrente, criado em 1965 por Edsger Dijkstra e tem como objetivo principal demonstrar a alocação de recursos quando temos processos que concorrem pela alocação dos mesmos, ou seja, os recursos disponíveis são escassos. Neste problema há a necessidade de reservar recursos entre vários processos sem deadlock ou starvation.
Algoritmo – O Jantar dos Filósofos
Considere 5 filósofos que passam a vida a pensar e a comer. Partilham uma mesa redonda rodeada por 5 cadeiras sendo que cada uma das cadeiras pertence a um filósofo. No centro da mesa encontra-se uma taça de arroz e estão 5 garfos na mesa, um para cada filósofo.
Quando um filósofo pensa não interage com os seus colegas. De tempos em tempos, cada filósofo fica com fome e tenta apanhar os dois garfos que estão mais próximos (os garfos que estão ou à esquerda ou à direita). O filósofo apenas pode apanhar um garfo de cada vez e como o leitor compreende, não pode apanhar um garfo se este estiver na mão do vizinho. Quando um filósofo esfomeado tiver 2 garfos ao mesmo tempo ele come sem largar os garfos. Apenas quando acaba de comer, o filósofo pousa os garfos, libertando-os e começa a pensar de novo. O nosso objetivo é ter uma representação/implementação que nos permita simular este jantar sem que haja problemas de deadlock ou starvation.
Para isso, o jantar será modelado usando uma thread para representar cada filósofo e usaremos semáforos para representar cada garfo. Quando um filósofo tenta agarrar um garfo executa uma operação wait no semáforo, quando o filósofo larga o garfo executa uma operação signal nesse mesmo semáforo. Cada filósofo (thread) vai seguir o algoritmo, ou seja, todos fazem as mesmas ações. Como deve estar já o leitor a pensar, o facto de seguirem o mesmo algoritmo pode dar azo à situação de deadlock, dai a utilização das primitivas de sincronização wait e signal. Uma outra possibilidade de deadlock seria o facto de mais do que um filósofo ficar com fome ao mesmo tempo, os filósofos famintos tentariam agarrar os garfos ao mesmo tempo. Isto é outro ponto que uma solução satisfatória terá que ter em atenção, devendo ser salvaguardado o facto de um filósofo não morrer à fome. Devemos recordar o leitor que uma solução livre de deadlock não elimina necessariamente a possibilidade de um filósofo morrer esfomeado.
Por todos estes motivos, o jantar dos filósofos é um algoritmo que deve ser implementado com algum cuidado por parte do programador.
Com o recurso à rede das redes, o leitor pode facilmente encontrar vários exemplos de implementação deste algoritmo em várias linguagens, contudo, também este artigo seguidamente apresenta um exemplo de uma implementação simples em C e em Java para que o leitor possa comparar os respetivos códigos.
Como criar Threads em Java (Exemplo)
Criamos uma classe que implemente a interface Runnable:
public class OlaRunnable implements Runnable
{
public void run()
{
System.out.println("A Thread comecou!");
}
public static void main(String args[])
{
(new Thread(new OlaRunnable())).start();
}
}
ou então criamos uma subclasse de Thread:
public class OlaThread extends Thread
{
public void run()
{
System.out.println("A Thread comecou!");
}
public static void main(String args[]) {
(new OlaThread()).start();
}
}
É necessário definir o método run(), requerido pela interface Runnable, para qualquer uma das opções escolhidas pelo programador. Esse método define o que irá acontecer após invocar o método start() na instância previamente criada.
Interromper uma Thread
Para pararmos a execução de uma thread, invocamos o método Thread.sleep() que recebe como parâmetro o número de milissegundos que a thread irá ficar bloqueada.
Este método pode lançar uma excepção (InterruptedException), logo é necessário “apanhá-la” de forma correcta.
Semáforos
Os semáforos são uma primitiva de concorrência muito básica que suportam o acesso concorrente a zonas de memória partilhada, ainda que alguns problemas de sincronização possam surgir, tais como deadlocks e starvation. Para que esses problemas possam ser eliminados, convém usar soluções melhores para exclusão mútua, como por exemplo, monitores.
Segue um exemplo de como utilizar um semáforo em Java:
import java.util.concurrent.Semaphore;
public class Semaforo
{
// (...)
Semaphore s = new Semaphore(1);
s.acquire();
// Código crítico
s.release()
//(...)
}Como criar Threads em C (Exemplo)
#include <stdio.h>
#include <pthread.h>
void *hello()
{
printf("Hello World\n");
pthread_exit(NULL);
}
int main()
{
pthread_t id;
int status;
status = pthread_create(&id ,NULL ,hello, NULL);
if(status!=0)
exit(-1);
pthread_exit(NULL);
return 0;
}Para compilar e executar este programa com o gcc, o leitor deve fornecer os comandos gcc -o hellothread hellothread.c -lpthread.
Semáforos em C
Utilizam a biblioteca semaphore.h.
Tipo: sem_t representação dum semáforo.
int sem_init(sem_t *sem, int pshared, unsigned int value);int sem_wait(sem_t * sem);int sem_post(sem_t * sem);
Jantar dos Filósofos – Implementação em Java
Classe Jantar
public class Jantar
{
public static void main (String[] args)
{
Mesa mesa = new Mesa ();
for (int filosofo = 0; filosofo < 5; filosofo++)
{
new Filosofo("Filosofo_" + filosofo, mesa, filosofo).start();
}
}
}Classe Filosofo
public class Filosofo extends Thread
{
final static int TEMPO_MAXIMO = 100;
Mesa mesa;
int filosofo;
public Filosofo (String nome, Mesa mesadejantar, int fil)
{
super(nome);
mesa = mesadejantar;
filosofo = fil;
}
public void run ()
{
int tempo = 0;
while (true)
{
tempo = (int) (Math.random() * TEMPO_MAXIMO);
pensar(tempo);
getGarfos();
tempo = (int) (Math.random() * TEMPO_MAXIMO);
comer(tempo);
returnGarfos();
}
}
public void pensar (int tempo)
{
try
{
sleep(tempo);
}
catch (InterruptedException e)
{
System.out.println("O Filófoso pensou em demasia");
}
}
public void comer (int tempo)
{
try
{
sleep(tempo);
}
catch (InterruptedException e)
{
System.out.println("O Filósofo comeu em demasia");
}
}
public void getGarfos()
{
mesa.pegarGarfos(filosofo);
}
public void returnGarfos()
{
mesa.returningGarfos(filosofo);
}
}Classe Mesa
public class Mesa
{
final static int PENSANDO = 1;
final static int COMENDO = 2;
final static int FOME = 3;
final static int NR_FILOSOFOS = 5;
final static int PRIMEIRO_FILOSOFO = 0;
final static int ULTIMO_FILOSOFO = NR_FILOSOFOS - 1;
boolean[] garfos = new boolean[NR_FILOSOFOS];
int[] filosofos = new int[NR_FILOSOFOS];
int[] tentativas = new int[NR_FILOSOFOS];
public Mesa()
{
for (int i = 0; i < 5; i++)
{
garfos[i] = true;
filosofos[i] = PENSANDO;
tentativas[i] = 0;
}
}
public synchronized void pegarGarfos (int filosofo)
{
filosofos[filosofo] = FOME;
while (filosofos[aEsquerda(filosofo)] == COMENDO || filosofos[aDireita(filosofo)] == COMENDO)
{
try
{
tentativas[filosofo]++;
wait();
}
catch (InterruptedException e)
{
}
}
System.out.println("O Filósofo morreu devido a starvation");
tentativas[filosofo] = 0;
garfos[garfoEsquerdo(filosofo)] = false;
garfos[garfoDireito(filosofo)] = false;
filosofos[filosofo] = COMENDO;
imprimeEstadosFilosofos();
imprimeGarfos();
imprimeTentativas();
}
public synchronized void returningGarfos (int filosofo)
{
garfos[garfoEsquerdo(filosofo)] = true;
garfos[garfoDireito(filosofo)] = true;
if (filosofos[aEsquerda(filosofo)] == FOME || filosofos[aDireita(filosofo)] == FOME)
{
notifyAll();
}
filosofos[filosofo] = PENSANDO;
imprimeEstadosFilosofos();
imprimeGarfos();
imprimeTentativas();
}
public int aDireita (int filosofo)
{
int direito;
if (filosofo == ULTIMO_FILOSOFO)
{
direito = PRIMEIRO_FILOSOFO;
}
else
{
direito = filosofo + 1;
}
return direito;
}
public int aEsquerda (int filosofo)
{
int esquerdo;
if (filosofo == PRIMEIRO_FILOSOFO)
{
esquerdo = ULTIMO_FILOSOFO;
}
else
{
esquerdo = filosofo - 1;
}
return esquerdo;
}
public int garfoEsquerdo (int filosofo)
{
int garfoEsquerdo = filosofo;
return garfoEsquerdo;
}
public int garfoDireito (int filosofo)
{
int garfoDireito;
if (filosofo == ULTIMO_FILOSOFO)
{
garfoDireito = 0;
}
else
{
garfoDireito = filosofo + 1;
}
return garfoDireito;
}
public void imprimeEstadosFilosofos ()
{
String texto = "*";
System.out.print("Filósofos = [ ");
for (int i = 0; i < NR_FILOSOFOS; i++)
{
switch (filosofos[i])
{
case PENSANDO :
texto = "PENSANDO";
break;
case FOME :
texto = "FOME";
break;
case COMENDO :
texto = "COMENDO";
break;
}
System.out.print(texto + " ");
}
System.out.println("]");
}
public void imprimeGarfos ()
{
String garfo = "*";
System.out.print("Garfos = [ ");
for (int i = 0; i < NR_FILOSOFOS; i++)
{
if (garfos[i])
{
garfo = "LIVRE";
}
else
{
garfo = "OCUPADO";
}
System.out.print(garfo + " ");
}
System.out.println("]");
}
public void imprimeTentativas ()
{
System.out.print("Tentou comer = [ ");
for (int i = 0; i < NR_FILOSOFOS; i++)
{
System.out.print(filosofos[i] + " ");
}
System.out.println("]");
}
}Jantar dos Filósofos – Implentação em C
#include<stdio.h>
#include<stdlib.h>
#include<semaphore.h>
#include<pthread.h>
#define N 5
#define PENSAR 0
#define FOME 1
#define COMER 2
#define ESQUERDA (nfilosofo+4)%N //agarrar garfo
//da esquerda
#define DIREITA (nfilosofo+1)%N //agarrar garfo
//da direita
void *filosofo(void *num);
void agarraGarfo(int);
void deixaGarfo(int);
void testar(int);
sem_t mutex;
sem_t S[N]; //inicializacao do semáforo
int estado[N];
int nfilosofo[N]={0,1,2,3,4};
void *filosofo(void *num)
{
while(1)
{
int *i = num;
sleep(1);
agarraGarfo(*i);
sleep(1);
deixaGarfo(*i);
}
}
void agarraGarfo(int nfilosofo)
{
sem_wait(&mutex);
estado[nfilosofo] = FOME;
printf("Filosofo %d tem fome.\n", nfilosofo+1);
//+1 para imprimir filosofo 1 e nao filosofo 0
testar(nfilosofo);
sem_post(&mutex);
sem_wait(&S[nfilosofo]);
sleep(1);
}
void deixaGarfo(int nfilosofo)
{
sem_wait(&mutex);
estado[nfilosofo]=PENSAR;
printf("Filosofo %d deixou os garfos %d e %d.\n", nfilosofo+1, ESQUERDA+1, nfilosofo+1);
printf("Filosofo %d esta a pensar.\n", nfilosofo+1);
testar(ESQUERDA);
testar(DIREITA);
sem_post(&mutex);
}
void testar(int nfilosofo)
{
if(estado[nfilosofo]==FOME && estado[ESQUERDA]
!=COMER && estado[DIREITA]!=COMER)
{
estado[nfilosofo]=COMER;
sleep(2);
printf("Filosofo %d agarrou os garfos %d e %d.\n", nfilosofo+1, ESQUERDA+1, nfilosofo+1);
printf("Filosofo %d esta a comer.\n", nfilosofo+1);
sem_post(&S[nfilosofo]);
}
}
int main() {
int i;
pthread_t thread_id[N]; //identificadores das
//threads
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(&thread_id[i], NULL, filosofo, &nfilosofo[i]);
//criar as threads
printf("Filosofo %d esta a pensar.\n",i+1);
}
for(i=0;i<N;i++)
pthread_join(thread_id[i],NULL); //para
//fazer a junção das threads
return(0);
}Chegados à reta final deste artigo gostaríamos mais uma vez de recordar o caro leitor da importância do bom uso dos mecanismos de sincronização.
Apesar de o jantar dos filósofos ser um problema clássico de sincronismo, é também uma situação teórica, contudo a verdade é que no “mundo real” há várias situações em que mecanismos de sincronização são usados e extremamente necessários, quer seja por exemplo, por uma simples transação bancária (em que há a necessidade de garantir a integridade e a boa sincronização do saldo real da nossa conta) ou até mesmo o algoritmo de sincronização dos sinais luminosos de transito (em que para que não haja acidentes há que garantir que duas ruas com vias contrárias, que terminem no mesmo cruzamento, não permitam a passagem de transito ao mesmo tempo—o cruzamento seria neste caso a secção crítica).
Este artigo é o primeiro de uma série de artigos de programação tendo como base principal a linguagem C e a linguagem Java como base auxiliar, que esperamos que siga atentamente.