PC-aula03-expConc-v0d1-gdocs-set2017 (1)

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.1
Expressão da 
Concorrência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.2
● Autoria e versão
– Alunos de turma de SOII
– C. Geyer
– Versão
● V0.1, 2017-2
● Formato: gdocs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.3
● Sumário
● Visão geral do Assunto
● Grafo de Precedência
● Fork/join
● Parbegin/end
● Vetor de processos
Sumário
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.4
● Abordagem 
● Apresentação das principais formas (mecanismos) 
de criação e gerência da concorrência
● Tipos
● Propriedades
● Prós e contras
● APIs abstratas
● Exemplos
Abordagem
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.5
Conceitos Gerais
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.6
● Termos usados para os fluxos de um PC
● Tarefa
– Forma abstrata
– Independentemente de modelo e linguagem de 
programação
● Processo
– conceito ou construção de SO e bibliotecas
– freqüentemente (↓) associado a uma tarefa
● Thread
– conceito ou construção de SO, bibliotecas e de linguagens
– freqüentemente (↑) associado a uma tarefa
Termos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.7
● Processo
– Mais antigo
– Mais lento (criação, ...)
– Maior consumo de memória
– Oferece mecanismos de proteção entre processos
– Não oferece variáveis (memória) compartilhadas entre 
processos
• Opção via bibliotecas especiais
• Consideradas menos eficientes e “inseguras”
– Mais usado em PC com memória distribuída (redes, ...)
Termos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.8
● Thread
– Em geral o inverso de processo
• P.ex.: mais rápido
– Mais usado em PC com memória compartilhada (1 
computador)
Termos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.9
Tipos Básicos de Criação de Tarefas:
Uma Classificação
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.10
● Tipos de criação de tarefas: => classificação
– Inicialmente, convém considerar as formas pelas 
quais a concorrência da execução pode ser 
especificada. 
– Tipos em função de “quando”
● Estática
● Dinâmica
– Tipos em função de “quem”
● Implícita
● Explícita
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.11
● Tipos em função de “quando”
– estática
• o programa contém a declaração de um conjunto fixo de 
processos
• os quais são ativados simultaneamente, no início da 
execução do programa
• mais simples para o programador
• eventualmente gerência de tarefas mais simples
● -> mais eficiente considerando a quantidade de 
operações de gerência de tarefas (criação, …)
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.12
● Tipos em função de “quando”
– dinâmica
• pois os processos são criados e terminados dinamicamente, 
durante a execução
• mais flexibilidade, pois os processos são criados e 
terminados conforme as necessidades da aplicação
• quantidade variável conforme necessidade em cada 
execução e momento
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.13
● Em função de “quem”
– Implícita e explícita
– Implícita
• sistema cria automaticamente 
– Compilador
– Máquina virtual (JVM, ...)
• mais simples para o programador
• freqüentemente menos flexível
• nem sempre o “sistema” sabe quando, o que, ...
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.14
● Em função de “quem”
– explícita
• programador deve usar uma primitiva ou construção 
específica
• mais flexível
• trabalho extra para o programador
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.15
● Freqüentemente
– estática-implícita
• MPI (biblioteca para programação paralela)
• Versão 1: estática em tempo de carga do programa
• N instâncias do mesmo código onde N é quantidade de cpus
– dinâmica-explícita
• fork (Unix)
• Comando ou procedimento que cria novo processo
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.16
● Outros casos
– dinâmica-implícita
• paralelização automática (via compilação) de linguagens
– Prolog, Lisp
– Fortran, C
• Paralelização semi automática via diretivas de linguagens
– OpenMP
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.17
● Outros casos
– estática-explícita
• SR (linguagem proposta por [Andrews 1991]
• declaração de processos por palavra reservada e begin/end
• ativados no início da execução
• quantidade fixa em todas as execuções
• obs: processos são encapsulados em um “resource” o qual é 
dinâmico
– Vários outros casos: combinando tipos acima
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.18
● Outros casos
– Exercício
• Considere uma linguagem onde se possa criar uma tarefa via marcação 
de um trecho de código com uma palavra reservada
• ...
Task:
x := y +1;
z := fibonacci(x);
...
• É modo implícito ou explícito? Dinâmico ou estático?
Tipos de Criação de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.19
Modelo Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.20
● Grafo de Precedência 
– grafo (usualmente) acíclico dirigido, no qual cada nó 
representa a execução de um processo 
– pode ser interpretado como um grafo de fluxo de processos
– normalmente usado em projeto, especificação, análises, ...
• editor convencional
• editores para PC
– pouco usado em linguagens e bibliotecas de programação
• motivos: 
– alto consumo de espaço em telas e impressões
– necessidade de ser completado com texto
Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.21
● Grafo de Precedência 
● Cada nodo representa um processo;
● Cada arco indica a precedência de execução e 
restrição na ordem dos processos;
● Exemplo:
Pi Pj
– Pj só pode ser executado após Pi, ou seja, Pj 
depende de Pi
Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.22
I1 :: A := X + Y;
I2 :: B := Z + 1;
I3 :: C := A - B;
I4 :: W := C + 1;
Programa:
● Suponha que queremos executar algumas dessas 
instruções concorrentemente. 
Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.23
I1 :: A := X + Y;
I2 :: B := Z + 1;
I3 :: C := A - B;
I4 :: W := C + 1;
Grafo de Precedência - Exemplo 1
Programa:
●Claramente, é possível perceber que a instrução I3 não 
pode ser executada antes de I1 e I2, pois I3 necessita dos 
novos valores de A e B. 
●E o mesmo acontece com I4, que não pode ser executado 
antes que o valor de C seja atualizado por I3.
Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.24
Grafo de Precedência - Exemplo 1
I3 I4 Fim
I2
I1
Grafo de Precedência correspondente ao programa anterior
Início
Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.25
● Considere um grafo de precedência com as seguintes 
relações de precedência:
– C2 e C3 podem ser executados depois da execução de C1;
– C4 pode ser executado depois da execução de C2;
– C5 e C6 podem ser executados depois da execução de C4;
– C7 só
pode ser executado depois da execução de C5, C6 e C3;
Grafo de Precedência - Exemplo 2
Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.26
C1
C2
C3
C4
C5
C6
C7
Grafo de Precedência
Solução: 
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.27
● Limitações
– não representa comunicação contínua (repetida) entre dois 
processos
– não representa comunicação realizada durante a execução 
(subcaso)
– não representa repetições de processos
– na literatura: inúmeros extensões, ou ainda outras propostas, 
para contornar essas e outras limitações
Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.28
● Usos
– Em projeto e especificação de programas concorrentes
– Em análise da complexidade de PCs
– Em programação de programas paralelos
• em geral, modelos mais restritos
• por exemplo, a comunicação entre processos é somente por 
arquivos
– No controle da execução de um Sistema Distribuído
• Sistema composto de vários programas sequenciais
• Meta programação ou programação em 2 níveis
• Ferramentas de workflow
Grafo de Precedência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.29
Modelo Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.30
● Modelo Fork/Join
– As instruções fork e join foram introduzidas por Conway 
[1963] e Dennis e Van Horn [1966];
– Foram a primeira notação de linguagem para especificação de 
concorrência;
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.31
● Fork: semântica
– A instrução fork L produz duas execuções concorrentes (fluxo, 
tarefa) num programa. 
• Uma execução começa na instrução rotulada L, 
• enquanto a outra é a continuação da execução na instrução 
seguinte à instrução fork
• Processo (tarefa) filho: 
● Usualmente a nova execução concorrente
• Processo pai: 
● Usualmente a que executou o fork
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.32
● Fork: semântica
– Para ilustrar este conceito, considere o seguinte 
segmento de programa:
● Ci é um comando qualquer (inclusive composto)
C1;
fork L; // L é um rótulo
C2;
.......
L: C3;
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.33
● Parte do grafo de precedência do 
programa é apresentado na figura ao 
lado.
● Quando a instrução fork L é 
executada, uma nova computação é 
iniciada em C3.
● Esta nova computação executa 
concorrentemente com a antiga 
computação, a qual continua em C2.
C1
Fork
C3C2
Fork / Join
● Fork: semântica (cont. exemplo)
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.34
● Join: semântica
– A instrução join agrupa duas computações concorrentes em 
uma. 
● Cada uma das computações deve requisitar para ser 
agrupada com a outra. 
● Já que as computações podem ter tempos de execução 
diferentes, uma pode executar o join antes da outra e sua 
execução é terminada. 
– A instrução join deve ser executada de forma atômica.
● Sem interrupções na visão de terceiros
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.35
count := 2;
fork L1;
...
C1;
goto L2;
L1: C2;
L2: join count;
Joi
n
C2 C1
C3
Parte do grafo de precedência para a 
programa ao lado
Fork / Join
● Join: semântica x exemplo sintético 1
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.36
C1;
count := 3;
fork L1;
C2;
C4;
fork L2;
C5;
goto L3;
L2: C6;
goto L3;
L1: C3;
L3: join count;
C7;
Ver grafo de precedência
 correspondente
Fork / Join
● Join: semântica x exemplo sintético 2
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.37
Fork / Join
● Join: semântica x exemplo sintético 2
C1
C2
C3
C4
C5
C6
C7
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.38
● Fork / Join: outras características
● É importante notar que a execução de uma instrução fork 
divide uma única computação em duas computações 
independentes. 
● Também é importante salientar que a execução de uma 
instrução join agrupa diversas execuções concorrentes.
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.39
● Fork / Join: outras características
– criação dinâmica de processos, o que dificulta a correção do 
programa;
– quantidade de processos variável em cada execução;
● Através do uso de comandos ifs, whiles, ...
– código do novo processo é o mesmo do processo pai;
● existem variações como por exemplo nas threads ou em 
OO
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.40
● Fork: variações
– variáveis: 2 alternativas em geral;
• A: compartilhamento de variáveis;
• B: duplicação das variáveis, como ocorre no Unix;
● Valor inicial na cópia é idêntico mas depois são 
independentes
– estruturas do tipo goto dão pouca legibilidade ao programa;
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.41
● Fork: exemplos
– SO Unix, Linux
• Formato:
process_id fork();
• process_id: 
● se pai recebe id do filho
● Se filho, recebe zero
• ambos os processos continuam a execução na instrução 
seguinte ao fork
• duplicação de variáveis
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.42
● Fork: exemplos
– SO Unix, Linux
● Uso comum
int pid;
pid = fork();
if pid == -1 {
 “código de erro”
} else if pid == 0 {
 “código do filho”
} else {
 “código do pai”
}
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.43
● Join: variações
– Forma geral: agrupamento de 2 processos 
concorrentes
– Join “n”
● n: número de processos a sincronizar ou terminar no join
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.44
● Join: variações
– Join Pk
● espera pelo término do processo Pk; 
● Pk é normalmente um processo filho;
● é necessário que os processos estejam nomeados para sua 
identificação;
– Join-filho
● espera pelo término de algum filho
● filho não precisa ser identificado (nomeado)
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.45
● Join: variações
– Join usando exit
● o processo que executa join espera pelo término de um 
filho;
● processo filho termina por exit;
● Exemplo:
● filho inicia em I3 e termina
● pai:
● executa I2
● e espera pela morte
do filho
...
I1;
fork LI3;
I2;
join;
I4;
goto LI5;
LI3: I3;
exit;
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.46
● Fork / Join: Implementações
● SOs Unix, Linux
● Biblioteca de programação paralela MPI
Fork / Join
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.47
Modelo de Thread
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.48
Thread
● Variação do fork/join
● Modelo mais usado atualmente para PC
– Devido vantagens básicas: 
• Mais eficiente
• Variáveis compartilhadas
● Inúmeras implementações
– SOs: Unix, Linux, Windows, SOs de dispositivos móveis 
(PDAs, celulares), embarcados, sensores, ...
– Bibliotecas
– Linguagens: Java, C#, Python, ...
Modelo Thread
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.49
● Modelo processo + thread usual
– Um processo pode conter várias threads
– O código main (procedure, método) é uma thread
– Uma thread tem escopo limitado ao de seu processo
• Processo
B não tem acesso a threads de processo A
– Usualmente o escopo de um processo é limitado por um 
computador
• Escopo: hw (cpu, ram, ...) mais o SO
• Logo também o de uma thread
Modelo Thread
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.50
● Criação de Thread
– Primitiva (procedure, método) “create_thread”
– Argumentos
• Procedure que contém o código da thread
• Argumento da procedure
– Retorno
• Identificador da thread
– Semântica
• Similar à do fork
• Thread atual continua execução concorrentemente ao fluxo 
da nova
Modelo Thread
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.51
● Morte de Thread
– Final da procedure (ou método); textual
– Exit
– Kill
• comando (de linguagem ou de biblioteca – método, 
procedimento, função) que solicita o fim da execução de 
uma thread
• Executado por outra thread; frequentemente a thread mãe
• Thread a ser encerrada deve ter nome ou identificador (ID)
Modelo Thread
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.52
● Modelo usual de variáveis em Threads
– Variáveis estáticas
• Compartilhadas entre as threads de um mesmo processo
– Variáveis locais
• Uma cópia por thread
– Argumentos
• Uma cópia por thread
Modelo Thread
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.53
● Implementações de Threads: exemplos
– Posix threads
• Biblioteca padronizada
• SO Unix, Linux e outros
– Java threads
– C# threads
Modelo Thread
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.54
Modelo Parbegin / Parend
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.55
● Parbegin/end
– comando de alto nível para especificação da concorrência;
• comando estruturado
– especifica explicitamente um conjunto de blocos (sequenciais 
internamente) de programa que serão executados 
concorrentemente;
– normalmente encontrado em algumas linguagens
• raramente (nunca?) usado em bibliotecas puras
• exige compilação
Modelo Parbegin / Parend
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.56
● Modelo Parbegin / Parend
– Todos os comandos:
• são encapsulados entre o parbegin e parend 
• e devem ser executados concorrentemente;
– Quantidade fixa de processos (tarefas);
– Sintaxe do comando:
● Parbegin 
 C1;C2;…;Cn 
Parend
– Semântica do comando:
•Cada Ci é um bloco de código autônomo sequencial
•Os Ci são executados concorrentemente.
Modelo Parbegin / Parend
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.57
Parbegin / Parend 
● grafo de precedência que 
corresponde à sintaxe dada 
anteriormente
● C0 e Cn+1 são os comandos 
que aparecem logo antes e após 
da/a instrução parbegin/parend, 
respectivamente. 
● o comando Cn+1 pode ser 
executado somente após todos 
Ci i= 1,2…n , tiverem sido 
executadosCn+1
C2 Cn
...
Co
C1
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.58
C1;
parbegin
C3;
begin
C2;
C4;
parbegin
 C5;
 C6;
 parend;
 end;
parend;
C7;
1. Ver grafo de precedência
 correspondente (próximo slide)
Modelo Parbegin / Parend
Parbegin / Parend: exemplo
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.59
Modelo Parbegin / Parend
C1
C2
C3
C4
C5
C6
C7
Parbegin / Parend: exemplo
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.60
● Modelo Parbegin / Parend
– Vantagens:
• Mais legível;
• Maior facilidade na verificação de erros;
– Desvantagens:
• Todo o grafo de precedências pode ser expresso por 
fork/join, mas nem todo o grafo de precedências pode ser 
representado por parbegin/parend.
● Com fork/join é possível entrar e sair de um 
subgrafo
• Dependendo da sofisticação da linguagem, pode-se 
proibir o uso de goto para dentro ou para fora do 
parbegin/end
Modelo Parbegin / Parend
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.61
Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.62
● Vetor de Processos
– necessita a criação de um vetor de tarefas de n posições
• também pode trabalhar com matrizes;
– todas as tarefas executam o mesmo código
• código é declarado dentro de um laço cujas instruções são 
executadas concorrentemente;
• obs: concorrência entre tarefas!
Modelo Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.63
● Vetor de Processos
– cada processo (tarefa) executa o mesmo código
• Para ser útil => sobre dados diferentes
• Solução implícita (simples)
– Cada tarefa tem um ID distinto correspondendo a índice 
de vetor (ou array, matriz)
– Se vetor: entre 1 (ou 0) e n (ou n-1) 
– Com esses índices se acessa (sub) arrays de dados
» => dados distintos por tarefa
– ou se pode usar comandos tipo “case” (ou “ifs” 
combinados para que cada tarefa faça algo distinto
Modelo Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.64
● Declaração do vetor:
var a[1:n]: real; // sintaxe SR
● Código:
process inicializa (i: 1 to n)
 a[i] := 0
● Código de cada processo:
● a[i] := 0
● Função geral: 
● inicializar o vetor “a” de forma concorrente
Modelo Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.65
● Equivale a
fa i := 1 to n → a[i] := 0 af // sintaxe SR
ou
for (i := 1 to n) {a[i] := 0} 
● Cada tarefa de índice i inicializa uma posição i do vetor
Modelo Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.66
● Declaração das matrizes: (sintaxe SR)
var a[1:n,1:n], b[1:n,1:n]: real;
var c[1:n, 1:n]: real := ( [n], ([n] 0.0))
● Inicialização das matrizes:
fa i:= 1 to n, j:= 1 to n →
read(filea, a[i,j]); read(fileb, b[i,j])
af
Modelo Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.67
● Laço de execução:
process compute (i := 1 to n, j := 1 to n)
 fa k:= 1 to n →
 c[i,j]) := c[i,j] + a[i,k]*b[k,j]
 af
● Comentários:
– criação de n2 processos (2 laços de ordem n)
– matrizes são inicializadas seqüencialmente
– cada tarefa (processo) calcula um elemento da matriz 
resultados
– os elementos são computados em paralelo
Modelo Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.68
● Biblioteca OpenMP
– Padronizada
– Para programação paralela
– Para certos tipos de programas 
• Ou melhor, para certos tipos de padrões de código 
(estruturas)
• Em particular: loops
– Uso de diretivas
• Algo entre implícito e explícito
– Exige compilador especial
– Adicionada às linguagens C, Fortran, ...
Modelo Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.69
● Biblioteca OpenMP
– As tarefas (threads) são criadas de forma implícita
– Quantas tarefas para um loop? Depende de:
• Tamanho do loop (=> tamanho do array)
• Quantidade de cores
• Algum parâmetro de sistema: valor padrão ou programador 
ou usuário
Modelo Vetor de Processos
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.70
API e Atributos de Gerência de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.71
● Todos os ambientes oferecem uma API para gerência de 
tarefas
– Todos: modelo expressão explícita
● Inclui obrigatoriamente
– Codificação da tarefa
– Criação da tarefa
● Inclui usualmente
– Morte da tarefa
– Espera pelo fim (“suicídio”) da tarefa
– Consulta e alteração de atributos básicos
API de 
Tarefas
Programação
concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.72
● Atributos usuais
– Prioridade da tarefa
– Nome da tarefa (opcional quando existe)
• Usada na impressão de traços
● APIs mais sofisticadas
– Variações no escalonamento
– Pool de tarefas
– Grupos de tarefas
API de 
Tarefas
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.73
Questões e Abordagens para Projeto 
de PCs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.74
● Questões de projeto de programas concorrentes
– Quais os tipos (lógica interna) de tarefas?
– Quantas instâncias de cada tipo?
– Quando devem ser criadas?
– Quando devem ser encerradas?
Projeto de PCs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.75
● Metodologia de projeto
– Frequentemente via reuso de padrões clássicos, bem 
conhecidos
– Exemplos
• Produtor / consumidor
• Leitores / escravos
• Mestre / escravos
• “Filósofos”
• Pipeline (linha de produção)
Projeto de PCs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.76
● Metodologia de projeto
– Modelos de Sistemas Distribuídos
• Cliente / Servidor
• P2P
• Grid
• Cluster
Projeto de PCs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.77
● Metodologia de projeto
– Exemplos de Algoritmos Distribuídos
• Difusão de dados
• Coleta de dados
• Eleição de líder
Projeto de PCs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.78
● Metodologia de projeto
– Exemplos Algoritmos Paralelos
• Soma de elementos de um vetor
• Produto vetorial
• Multiplicação de matrizes
• Classificação
Projeto de PCs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.79
● Vários modelos para criação da concorrência
– Modelos de programa concorrente
– APIs para criação e gerência (join, ...) das tarefas
– Variações na semântica das APIs
– Variações na sintaxe das APIs (menos importante)
● Diferentes modelos afetam os outros aspectos da PC
– Sincronização e comunicação
Projeto de PCs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.80
● Existem outros modelos
– Nas linguagens OO
• E com APIs distintas, ...
– Na paralelização de linguagens seqüenciais (Fortran, Lisp, 
Prolog, ...)
• Normalmente usando os modelos acima na implementação
Projeto de PCs
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.81
Resumo da Expressão da 
Concorrência
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.82
● Resumo Final
– Tarefa, processo e thread
– Tipos: estático x dinâmico, implícito x explícito
– Modelos
● Grafo de precedências (ou de comunicação)
● Fork/join
● Thread
● Parbegin/parend
● Array de processos
– API de Gerência de Tarefas
– Projeto e Modelo de PCs
Resumo Final
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.83
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.84
● Reescreva o seguinte programa usando instruções 
parbegin/parend. Certifique-se de que será explorado o 
máximo de paralelismo e que o resultado produzido 
será sempre o mesmo da execução seqüencial.
W := X1 * X2;
V := X3 * X4;
Y := V * X5;
Z := V * X6;
Y := W * Y ;
ANS := Y + Z;
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.85
● Reescreva o seguinte programa usando instruções 
parbegin/parend. Certifique-se de que será explorado o 
máximo de paralelismo e que o resultado produzido 
será sempre o mesmo da execução seqüencial.
W := X1 * X2;
V := X3 * X4;
T := Y1 + Y2;
Y := V * T;
Z := V * X6;
W := W * Y ;
ANS := Y + Z;
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.86
parbegin
W := X1 * X2;
 begin
 V := X3 * X4;
 parbegin
 Y := V * 
X5;
 Z := V * 
X6;
 parend;
 end;
parend;
Y := W * Y ;
ANS := Y + Z;
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.87
● Transforme o grafo de precedência abaixo em um 
programa usando fork/join:
C1
C2
C3
C4
C6
C5
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.88
● Transforme o grafo de precedência abaixo em um 
programa usando fork/join:
C1
C2
C3
C4
C8
C5
C6
C7
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.89
C1;
fork LC3;
fork LC4;
C2;
LJ3: join;
C5;
LJ4: join;
C6;
 
LC3: C3;
 goto LJ3;
LC4: C4;
 goto LJ4; 
Transformação do grafo de 
precedência em um programa 
utilizando instruções fork/join
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.90
● Transforme o grafo de precedência abaixo em um 
programa fork/join e em parbegin/parend. Se o grafo 
não puder ser representado por parbegin/parend, 
explique porquê.
C1
C2
C3
C4
C5
C6 FIM
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.91
C1;
fork LI3;
C2;
fork LI5;
C4;
LJ5: join;
LJ3: join;
C6;
LC3: C3;
 goto LJ3;
LI5: C5;
 goto LJ5;
Transformação do grafo de 
precedência em um programa 
utilizando instruções fork/join
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.92
C1;
parbegin
C3;
begin
 C2;
 parbegin
 C4;
 C5;
 parend;
 end;
parend;
C6;
Transformação do grafo 
de precedência em um 
programa utilizando 
instruções 
parbegin/parend
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.93
● Implemente o grafo de precedência abaixo utilizando fork/join. 
Explique a semântica do fork e do join: início do processo, 
quantidade de processos...
1
5 9
4
3
2
10
7
6
8
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.94
1;
Fork L3;
2;
Fork L5;
4;
8;
J2: Join
J3: Join;
 10;
 exit;
L3: 3;
 Fork 
L7;
 6;
J1: Join;
 goto 
J3;
L7: 7;
goto J1;
L5: 5;
9;
goto J2;
O início do processo se dá com o processo pai (1). O 
comando fork cria processos filhos. A quantidade de 
processos criados é variável. Já a semântica do processo join 
é esperar o término de 2 processos (join padrão) para somente 
depois disso passar para a próxima instrução. O código com 
fork/join não fica legível, mas a criação dos processos é feita 
de forma dinâmica . Exemplo: Fork L3 cria ó processo 3. O 
join de rótulo J1 espera o término da execução de 6 e 7.
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.95
● A partir do programa abaixo que utiliza fork/join, implemente o 
grafo de precedência correspondente.
1;
Fork L3;
Fork L4;
2;
goto J1;
L3: 3;
 Fork L6; 
 5;
J1: Join;
 7;
 Fork L9;
 8;
J2: Join;
J3: Join;
 11;
exit;
L4: 4; 
 goto J4;
L6: 6; 
J4: Join;
 10;
 goto J3; 
L9: 9; 
 goto J2;
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.96
1
5
9
4
3
2
10
7
6
8
11
Exercícios
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.97
Revisão
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.98
● Tipos quanto a “quando”?
● Tipos quanto a “quem”?
● Combinações usuais?
● Tipos mais simples para programador?
● Tipos mais eficientes?
● Tipos mais flexíveis?
Revisão
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.99
● Conceito de grafo de precedência
– nó?
– arco?
– 2 nós ligados por 1 arco?
– 1
nó com 2 ou mais arcos de saída?
– 1 nó com 2 ou mais arcos de entrada?
Revisão
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.100
● Conceito de fork clássico
– função básica?
– código?
– variáveis?
– início?
● Variações no fork Unix?
– sobre acima?
– retorna?
● Problemas de eng. de sw 
Revisão
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.101
● Conceito de join clássico
– versão 2 processos
– versão n (2 ou mais) processos
● Variações no Unix
– nome
– tipo 1 (anônimo)
– tipo 2 (com identificador)
Revisão
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.102
● Parbegin/parend
– estático ou dinâmico?
– implícito ou estático?
– quais funções do modelo fork/join?
– qual o modelo de código?
– qual o modelo de dados?
– o que pode ser proibido no parbegin/parend?
– quais as vantagens?
Revisão
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.103
● Vetor de processos
– estático ou dinâmico?
– implícito ou explícito?
– qual o código?
– qual o modelo de dados?
– qual a similaridade com o parbegin/parend?
– qual a diferença com …?
Revisão
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.104
● Outras primitivas Unix
– sobre identificadores
– término
– código
Revisão
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.105
Bibliografia
● Andrews, G. 
– Concurrent Programming: Principles and Practice. 
– The Benjamim Cummings, 1991.
● Andrews, G.
– Foundations of Multithreaded, Distributed and Parallel Programming.
– Ed. 2001.
● Silberschatz, A. 
– Operating Systems Concepts.
– Addison-Wesley, 5º edição, 1992, e edições seguintes.
– última versão: 9th Edition. Hardcover: 944 pages. Publisher: Wiley; 9 edition 
(December 17, 2012). Language: English. ISBN-10: 1118063333. ISBN-13: 
978-1118063330
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.106
Bibliografia
● Tanenbaum, A. S. 
– Modern Operating Systems.
– Prentice-Hall, 1992, e edições seguintes.
– última versão: 4th Edition. by Hardcover: 1136 pages. Publisher: Pearson; 4 edition 
(March 20, 2014). Language: English. ISBN-10: 013359162X. ISBN-13: 
978-0133591620
● Livros dos professores da UFRGS
– Toscani, S. S., Oliveira, R., Caríssimi, A. Sistemas Operacionais e Programação Concorrente. 
Editora Sagra-Luzzato, 2003. ISBN: 8524106824. 247 páginas.
– Oliveira, R., Caríssimi, A .Toscani, S. S. Sistemas Operacionais - Volume 11. ed. Bookman. 4ª 
ed. 2010.
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.107
Especificações
Autores da 1ª versão
Ingrid de Vargas Mito ingrid@aton.inf.ufrgs.br
Maíra Colling Wenzel maira@aton.inf.ufrgs.br
Local
Instituto de Informática
UFRGS
Disciplina: Sistemas Operacionais II
Ano: 1998/2
Revisões anuais: C. Geyer
Programação concorrente (C. Geyer) Expressão da Concorrência V. 0.0 S.108
Expressão da Concorrência
SOII
Fim