---
Author:
- Amanda Luna
Bibliography:
- 'references.bib'
Date: Agosto 2019
Title: 'Apostila - Programao Concorrente'
---
# Apostila - Programao Concorrente
Sumário
=================================
[O que é programao concorrente ?](https://github.com/avdLuna/ConcurrentProgramming#o-que-%C3%A9-programa%C3%A7%C3%A3o-concorrente-)
[Threads](https://github.com/avdLuna/ConcurrentProgramming#threads)
* [Definio](https://github.com/avdLuna/ConcurrentProgramming#defini%C3%A7%C3%A3o)
* [Problemas que podemos ter](https://github.com/avdLuna/ConcurrencyProgramming#problemas-que-podemos-ter)
* [Estados de uma thread](https://github.com/avdLuna/ConcurrentProgramming#estados-de-uma-thread)
[Introduo a Threads em Java](https://github.com/avdLuna/ConcurrentProgramming#introdu%C3%A7%C3%A3o-a-threads-em-java)
* [Comeando a trabalhar com threads (Java)](https://github.com/avdLuna/ConcurrentProgramming#come%C3%A7ando-a-trabalhar-com-threads-java)
* [Métodos para trabalhar com threads (Java)](https://github.com/avdLuna/ConcurrentProgramming#m%C3%A9todos-para-trabalhar-com-threads-java)
* [Trabalhando com múltiplas threads (Java)](https://github.com/avdLuna/ConcurrentProgramming#trabalhando-com-m%C3%BAltiplas-threads-java)
[Introduo a threads em C](https://github.com/avdLuna/ConcurrentProgramming#introdu%C3%A7%C3%A3o-a-threads-em-c)
* [Comeando a trabalhar com threads (C)](https://github.com/avdLuna/ConcurrentProgramming#come%C3%A7ando-a-trabalhar-com-threads-c)
* [Métodos para trabalhar com threads (C)](https://github.com/avdLuna/ConcurrentProgramming#m%C3%A9todos-para-trabalhar-com-threads-c)
* [Trabalhando com múltiplas threads (C)](https://github.com/avdLuna/ConcurrentProgramming#trabalhando-com-m%C3%BAltiplas-threads-c)
[Excluso Mútua](https://github.com/avdLuna/ConcurrentProgramming#exclus%C3%A3o-m%C3%BAtua)
* [Produtor/Consumidor](https://github.com/avdLuna/ConcurrentProgramming#produtorconsumidor)
* [Produtor/Consumidor (Java)](https://github.com/avdLuna/ConcurrentProgramming#produtorconsumidor-java)
* [Produtor/Consumidor (C)](https://github.com/avdLuna/ConcurrentProgramming#produtorconsumidor-c)
O que é programao concorrente ?
=================================
Os sistemas de computao modelam o mundo e este contém atores que
executam independentemente, mas se comunicam uns com os outros. Na
modelagem do mundo, muitas (possivelmente) execues paralelas precisam
ser compostas e coordenadas, e é aí que entra o estudo da
concorrência.
A concorrência nada mais é do que a coordenao e gesto destas linhas
independentes de execuo e pode ocorrer quando
várias cópias da mesma tarefa so executadas ao mesmo tempo, mas no
decorrer de sua execuo, essas cópias se comunicam umas com as outras,
via memória compartilhada ou passagem de mensagens.
Ou seja, programao concorrente fornece uma maneira de tornar eficaz
uso de sistemas paralelos e distribuídos que executam muitas tarefas
simultaneamente.
Um detalhe importante é que **no** devemos confundir concorrência com
paralelismo, pois concorrência é sobre *lidar* com muitas coisas de uma
só vez, já paralelismo é sobre *fazer* muitas coisas ao mesmo
tempo.
Threads
=======
Definio
---------
De forma simplista e direta, uma thread é uma linha (thread) de execuo
de um processo ou também pode ser vista como um
subprocesso de um processo. Como threads têm algumas das propriedades
dos processos, às vezes eles so chamados de *processos leves*.
Threads têm exatamente o mesmo espao de endereamento, o que significa
que elas também compartilham as mesmas variáveis globais. Tendo em vista
que toda thread pode acessar todo espao de endereamento de memória
dentro do espao de endereamento do processo, um thread pode ler,
escrever, ou mesmo apagar a pilha de outro thread, o
que é considerado um grande problema. Para evitar isto, uma das
possíveis solues é garantir **excluso mútua**, que nada mais é do que
garantir que apenas uma thread entre nos espaos com recursos
compartilhados.
Estes espaos com recursos compartilhados so chamados de **regies
críticas**, nas quais podem ocorrer **condies de corrida**. Estas
ocorrem quando múltiplas threads entram nesta regio de forma
concorrente (ao mesmo tempo). O resultado final da execuo da tarefa
pode ser afetado pelo fluxo de execuo das threads.
Problemas que podemos ter
-------------------------
Seguem aqui alguns problemas que poderemos ter quando ocorrem condies
de corrida nas regies críticas
- Livelock
- Os livelocks ocorrem quando as threads so escalonadas, mas no
esto fazendo progresso porque esto reagindo continuamente às
alteraes de estado uma da outra. A alta utilizao da CPU sem
nenhum sinal de trabalho real sendo feito é um sinal clássico de
aviso de um livelock. Os Livelocks so incrivelmente difíceis de
detectar e diagnosticar.
- Deadlock
- Um deadlock ocorre quando duas ou mais threads esperam uma a
outra, formando um ciclo e impedindo que todas elas avancem.
Deadlocks geralmente so introduzidos por desenvolvedores
tentando resolver condies da corrida.
- Starvation
- Starvation é um atraso indefinido ou bloqueio permanente de uma
ou mais threads em um aplicativo multithread. Threads que no
esto sendo escalonadas para serem executadas, mesmo que no
estejam bloqueadas ou esperando por qualquer outra coisa, esto
em starvation.
Estados de uma thread
---------------------
A execuo de uma thread pode passar por quatro estados: novo,
executável, bloqueado e encerrado. Um exemplo de como funciona a trocas
entre estes estados na JVM pode ser vista na figura abaixo.
![Estados de uma thread na
JVM[]{label="EstadosThread"}](ima004.jpg)
- A thread está no estado de novo, quando é criada. Ou seja, quando é
alocada área de memória para ela através do operador new.Ao ser
criada, a thread passa a ser registrada dentro da JVM, para que a
mesma posso ser executada.
- A thread está no estado de executável, quando for ativada. O
processo de ativao é originado pelo método *start()*. importante
frisar que uma thread executável no está necessariamente sendo
executada, pois quem determina o tempo de sua execuo é a JVM ou o
S.O.
- A thread está no estado de bloqueado, quando for desativada. Para
desativar uma thread é necessário que ocorra uma das quatro
operaes a seguir:
1. Foi chamado o método *sleep(long tempo)* da thread;
2. Foi chamado o método *suspend()* da thread (método deprecado);
3. A thread chamou o método *wait()*;
4. A thread chamou uma operao de I/O que bloqueia a CPU;
- Para a thread sair do estado de bloqueado e voltar para o estado de
executável, uma das seguintes operaes deve ocorrer, em oposio as
aes acima:
- Retornar após o tempo especificado, caso a thread estiver
adormecida;
- Retornar através do método *resume()*, caso a thread tiver sido
suspensa (método deprecado);
- Retornar com o método *notify()* (ou *notifyAll()*), caso a
thread estiver em espera;
- Retornar após a concluso da operao de I/O.
- A thread está no estado de encerrado, quando encerrar a sua
execuo. Isto pode acorrer pelo término do método *run()*, ou pela
chamada explícita do método *stop()*.
Por agora no se preocupe tanto com essas nomenclaturas, detalharemos
elas na seo seguinte.
Introduo a Threads em Java
============================
Existem dois jeitos para se implementar thread em java:
1. Derivar da classe *Thread* (extends)
2. Implementar a interface *Runnable*
O segundo jeito é o mais recomendado, pois, ao estender *Thread*, cada
uma das suas threads tem um objeto exclusivo associado a ele, enquanto
implementando *Runnable*, muitas threads podem compartilhar a mesma
instncia de objeto. Além disso, quando há necessidade de estender uma
superclasse, implementar a interface *Runnable* é mais apropriado do que
usar a classe *Thread*, pois podemos estender outra classe ao
implementar a interface para criar uma thread, mas, se apenas
esterdermos a classe *Thread*, no poderemos herdar de nenhuma outra
classe.
Comeando a trabalhar com threads (Java)
----------------------------------------
Como dito anteriormente, o melhor jeito para comear a brincar com
threads é criando uma nova classe que implementa a interface *Runnable*
Para implementar esta interface, só é necessário implementar um único
método, chamado *run()*, que será o que a sua thread irá executar.
Para criar uma thread, temos o seguinte trecho de código:
Thread t = new Thread(Runnable target, String name);
Em que o parmetro `Runnable target` se refere a classe que implementa
*Runnable* e o método *run()* e o parmetro `String name` ao nome da
thread, que é opcional.
Temos como exemplo o programa apresentado a seguir
public class ThreadsWorking implements Runnable {
@Override
public void run() {
System.out.println("Minha thread executando");
}
}
class ThreadsExample{
public static void main(String[] args) {
Thread minhaThread = new Thread(new ThreadsWorking());
minhaThread.start();
}
}
*Exemplo 1*
A saída esperada para esta execuo é apenas a linha
Minha thread executando
Métodos para trabalhar com Threads (Java)
-----------------------------------------
Segue abaixo uma lista com alguns métodos disponíveis da classe
*Thread*:
- `void run()` -- Deve conter o código que se deseja executar, quando
a thread estiver ativa;
- `void start()` -- Inicia a thread;
- `void stop()` -- encerra a thread;
- `static void sleep(long tempo)` -- deixa thread corrente inativa por
no mínimo tempo milisegundos e promove outra thread;
- `static void yield()` -- Deixa a thread em execuo temporariamente
inativa e, quando possível, promove outra thread de mesma prioridade
ou maior;
- `void join()` -- Aguarda outra thread para encerrar;
- `boolean isAlive()` -- retorna true caso uma thread estiver no
estado executável ou bloqueado. Nos demais retorna false;
- `void wait()` -- Interrompe a thread corrente e coloca a mesma na
fila de espera (do objeto compartilhado) e aguarda que a mesma seja
notificada. Este método somente pode ser chamado dentro de um método
de sincronizado;
- `void notify()` -- Notifica a próxima thread, aguardando na fila;
- `void notifyAll()` -- Notifica todas as threads.
Para mais detalhes e conhecer mais métodos disponíveis, você pode
consultar a
[documentao](https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html)
de *Thread*
Trabalhando com múltiplas threads (Java)
----------------------------------------
Para entendermos sobre múltiplas threads em java, observemos o código
abaixo.
public class MyThread implements Runnable {
private String id;
Thread t;
public MyThread(String id) {
this.id = id;
this.t = new Thread(this, id);
t.start();
}
@Override
public void run() {
try {
for (int i = 0; i < 3; i++) {
System.out.println("Thread " + id + " executando");
Thread.sleep(1000);
}
} catch (InterruptedException e) {
System.out.println(id + "interrompida");
}
System.out.println("Thread " + id + " terminando");
}
}
class ThreadsExample{
public static void main(String[] args) {
MyThread t1 = new MyThread("1");
MyThread t2 = new MyThread("2");
MyThread t3 = new MyThread("3");
}
}
*Exemplo 2*
O output desse programa foi:
Thread 3 executando
Thread 1 executando
Thread 2 executando
Thread 2 executando
Thread 1 executando
Thread 3 executando
Thread 1 executando
Thread 3 executando
Thread 2 executando
Thread 2 terminando
Thread 1 terminando
Thread 3 terminando
Neste programa, temos a execuo de três threads simultneamente, em que
cada uma delas faz um *sleep()* de 1000 milissegundos e imprime na tela
seu id.
Com o output, podemos perceber que as threads no executam de maneira
sequencial (1,2,3) e sim de maneira concorrente, em que a thread que
pega a CPU primeiro é a que será executada. Também podemos perceber que
o encerramentos destas também no segue um padro e que no
necessariamente a primeira thread a ser executada é a primeira a
terminar.
Introduo a Threads em C
=========================
Para comear a implementar threads em C, basta inserir o seguinte
comando no seu código:
``` {style="CStyle"}
#include
```
Comeando a trabalhar com threads (C)
-------------------------------------
Para criar uma thread em C, temos o seguinte trecho de código:
``` {style="CStyle"}
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void*), void *arg);
```
Em que,
- `pthread_t *thread` - é onde você coloca a *pthreadt* que será
inicializada;
- `const pthread_attr_t *attr` - é onde se mantém dados que mudam o
comportamento da thread. Se você no sabe o que está fazendo, o
ideal é por *NULL* no lugar;
- `void *(*start_routine)(void*)` - aqui é onde se coloca a funo que
a thread irá executar quando estiver pronta;
- `void *arg` - aqui é onde se passam os argumentos para a funo que
vai ser executada (se tiver).
Com isso, poderíamos substituir os parmetros para que ficassem assim:
``` {style="CStyle"}
int pthread_create(minha_thread, NULL, minha_funcao, argumentos_da_funcao);
```
Obs. Se você está com dificuldades em entender como funcionam os
apontadores, talvez
[isto](https://www.tutorialspoint.com/cprogramming/c_pointers.htm)
possa lhe ajudar.
Agora vejamos um programa semelhante ao *exemplo 1* feito em Java, agora
em C
``` {style="CStyle"}
#include
#include
void* run(void* args){
int id = (int) args;
printf("Ola, eu sou a thread que voce criou\nMeu ID e %d e eu estou executando\n", id);
pthread_exit(NULL);
}
int main(int argc, char *argv[]){
pthread_t minha_thread;
pthread_create(&minha_thread, NULL, &run, (void *) 1);
pthread_join(minha_thread, NULL);
return 0;
}
```
*Exemplo 3*
O output para este programa é
``` {style="CStyle"}
Ola, eu sou a thread que voce criou
Meu ID e 1 e eu estou executando
```
Métodos para trabalhar com threads (C)
--------------------------------------
Segue abaixo ums lista com algumas funes básicas de *pthread*:
- `pthread_create(pthread_t *, const pthread_attr_t *,void *(*)(void *), void *)`
-- Cria uma thread baseado nos parmetros colocados;
- `pthread_join(pthread_t thread, void **value_ptr)` -- Suspende a
execuo da thread corrente até que a thread passada como parmetro
termine. O segundo parmetro contém o valor passado em
*pthread_exit*;
- `pthread_exit(void *value_ptr);` -- Termina a thread que a chamou e
disponibiliza o valor de *\*valueptr* para qualquer chamada de
funo *join* que contenha a thread atual.
Agora algumas funes envolvendo mutex:
- `pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr);`
-- Inicia o mutex que foi passado no primeiro parmetro. O segundo
parmetro refere-se aos atributos do mutex, se você no sabe o que
está fazendo, o ideal é por *NULL*;
- `pthread_mutex_lock(pthread_mutex_t *mutex);` -- Bloqueia o mutex
especificado no parmetro. Se o mutex já estiver bloqueado por outra
thread, a thread aguarda que o mutex se torne disponível. A thread
que bloqueou o mutex torna-se sua atual proprietária e permanece
como proprietária até que a mesmo thread o tenha desbloqueado;
- `pthread_mutex_unlock(pthread_mutex_t *mutex);` -- Libera o mutex
especificado no parmetro. Se uma ou mais threads estiverem
aguardando para bloquear o mutex,o unlock com que uma dessas threads
saia do lock com o mutex do parmetro. Se nenhuma threads estiver
aguardando o mutex, o mutex será desbloqueado sem proprietário
atual;
- `pthread_mutex_destroy(pthread_mutex_t *mutex);` -- Deleta o mutex
especificado no parmetro.
Por último, envolvendo variáveis condicionais:
- `pthread_cond_init(pthread_cont_t *cv, const pthread_condattr_t *cattr);`
-- Inicia a variável condicional passada no primeiro parmetro. O
segundo parmetro refere-se aos atributos dessa variável
condicional, se você no sabe o que está fazendo, o ideal é por
*NULL*;
- `pthread_cond_wait(pthread_cont_t *cv,pthread_mutex_t *mutex);` -- Esta
funo bloqueia até que a condio seja sinalizada (*signal()*. Ele
atomicamente libera a trava mutex associada antes de bloquear, e
atomicamente a adquire novamente antes de retornar;
- `pthread_cond_signal(pthread_cont_t *cv);` -- Desbloqueia uma thread
específica;
- `pthread_cond_broadcast(pthread_cont_t *cv);` -- Desbloqueia todas as
threads que estiverem bloqueadas;
- `pthread_cond_destroy(pthread_cont_t *cv);` -- Destrói a variável
condicional passada no parmetro.
Uma coisa que você pode estar se perguntando é: Por que, destas funes,
o wait necessita, além da variável condicional, um mutex? A resposta
para isto é que o mutex é usado para *proteger* a variável condicional
quando ocorre o *wait()*. O *wait()* irá \"atomicamente\" desbloquear o
mutex, permitindo que outros acessem a variável de condio para
*signal()*. Ento, quando ocorre um *signal()* ou *broadcast()*
envolvendo a variável condicional, uma ou mais threads bloqueadas sero
acordados e o mutex será magicamente bloqueado novamente para essa
thread.
Para mais detalhes e conhecer mais funes disponíveis, você pode
consultar a
[documentao](http://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread.h.html).
Trabalhando com múltiplas threads (C)
-------------------------------------
Para entendermos sobre múltiplas threads em C, observemos a verso em C
do código contido no *exercício 2*.
``` {style="CStyle"}
#include
#include
#include
void* run(void* args){
int id = (int) args;
for (int i = 0; i < 3; i++){
printf("Thread %d executando\n", id);
sleep(1);
}
printf("Thread %d terminando\n", id);
pthread_exit(NULL);
}
int main(int argc, char *argv[]){
int i;
pthread_t pthreads[3];
for (i = 0; i < 3; i++) {
pthread_create(&pthreads[i], NULL, &run, (void*) i + 1);
}
for (i = 0; i < 3; i++) {
pthread_join(pthreads[i], NULL);
}
return 0;
}
```
*Exemplo 4*
O output gerado foi:
Thread 1 executando
Thread 2 executando
Thread 3 executando
Thread 1 executando
Thread 3 executando
Thread 2 executando
Thread 3 executando
Thread 1 executando
Thread 2 executando
Excluso mútua
==============
Como já vimos antes, excluso mútua nada mais é do que garantir que
apenas uma thread entre na regio crítica, evitando assim, condies de
corrida. Nas sees abaixo exploraremos solues em C e Java que
utilizam este recurso para proteger o código.
Produtor/Consumidor
------- ... ...