Aula 03 — Programação Concorrente: Notação e Modelos de Execução

Objetivos

Ao final desta aula você deve ser capaz de:

• Distinguir execução sequencial de execução concorrente, identificando quando tarefas podem ser paralelizadas.
• Construir e interpretar grafos de precedência a partir de dependências entre tarefas.
• Traduzir um grafo de precedência para a notação Fork/Join, indicando corretamente os labels e o contador do JOIN.
• Traduzir um grafo de precedência (quando possível) para a notação Parbegin/Parend, usando blocos begin/end aninhados.
• Identificar as limitações do Parbegin/Parend e reconhecer grafos que só podem ser expressos com Fork/Join.
• Relacionar as notações teóricas com as primitivas reais do UNIX (fork(), wait()) e POSIX Threads (pthread_create(), pthread_join()).

---

Conteúdo

Por que programação concorrente?

Programas sequenciais executam uma instrução de cada vez — simples de raciocinar, mas subutilizam hardware moderno. Processadores com múltiplos núcleos, discos SSD e GPUs ficam ociosos enquanto o programa aguarda a conclusão de uma única tarefa.

A programação concorrente permite que múltiplas tarefas progridam ao mesmo tempo, seja em verdadeiro paralelismo (múltiplos núcleos) ou em paralelismo aparente (interleaving por time-sharing em um único núcleo).

Analogia: uma montadora não fabrica carros sequencialmente — primeiro 100% da lataria de um carro, depois a pintura etc. A linha de montagem executa várias etapas em paralelo em carros diferentes. A programação concorrente aplica o mesmo raciocínio ao software.

Por que é difícil? Tarefas concorrentes frequentemente compartilham dados. A ordem exata de execução — o interleaving — é não determinística e controlada pelo escalonador do SO. Isso abre espaço para condições de corrida, deadlocks e starvation — tópicos que serão aprofundados a partir da Aula 05.

Nesta aula o foco é anterior: como expressar e raciocinar sobre quais tarefas podem (ou devem) ser executadas em paralelo, usando notações formais.

---

Grafo de Precedência

Um grafo de precedência é um DAG (Directed Acyclic Graph — grafo dirigido acíclico) onde:

• Cada nó representa uma tarefa (instrução, função, processo).
• Cada aresta S_i → S_j indica que S_j só pode começar após S_i terminar (dependência de dados ou de controle).
• Tarefas sem aresta entre si podem ser executadas em paralelo.

Exemplo 1 — execução completamente sequencial:

Nenhum paralelismo possível: cada tarefa depende da anterior.

Exemplo 2 — paralelismo total após S1:

S2, S3 e S4 podem ser executadas em paralelo após S1. S5 aguarda todas.

Exemplo 3 — dependências parciais (grafo "diamante"):

S2 e S3 paralelas entre si; S4 aguarda ambas.

---

Notação Fork/Join

Proposta por Conway, Dennis e Van Horn (1963), a notação Fork/Join é completa — capaz de expressar qualquer grafo de precedência.

Primitivas

Primitiva	Semântica
FORK L	Cria um novo fluxo de execução a partir do label L. O fluxo original continua na próxima instrução.
JOIN n	Operação atômica. Decrementa o contador n. Se n > 0 após decremento, o fluxo atual termina. Se n = 0, o fluxo atual continua.
GOTO L	Desvio incondicional (garante que apenas um fluxo chegue ao JOIN final).

JOIN é atômico: nenhum outro processo pode interrompê-lo durante o decremento e teste — garantindo que exatamente um fluxo continue.

Exemplo: grafo com S2 e S3 paralelas

Grafo:        S1 → {S2 ∥ S3} → S4

count := 2;
FORK L_S3;
    S2;              /* fluxo original executa S2 */
    GOTO L_join;
L_S3:
    S3;              /* fluxo novo executa S3     */
L_join:
    JOIN count;      /* count=2→1: primeiro a chegar termina */
                     /* count=1→0: segundo a chegar continua */
S4;

Rastreando a execução:

Exemplo mais complexo: três tarefas paralelas

Grafo: S1 → {S2 ∥ S3 ∥ S4} → S5

count := 3;
FORK L2;          /* cria fluxo para S3 */
FORK L3;          /* cria fluxo para S4 */
S2;
GOTO L_fim;
L2: S3;
    GOTO L_fim;
L3: S4;
L_fim:
    JOIN count;
S5;

Limitação do Fork/Join

Embora completo, Fork/Join resulta em código espaguete — repleto de GOTOs que dificultam a leitura e a manutenção. Para grafos simples, existe uma alternativa mais legível.

---

Notação Parbegin/Parend

Proposta por Dijkstra (1968), também conhecida como Cobegin/Coend. É uma construção de linguagem estruturada em bloco — sem GOTOs.

Semântica

PARBEGIN
    S1;
    S2;
    ...
    Sn;
PAREND;

Todas as instruções entre PARBEGIN e PAREND são executadas concorrentemente. O fluxo principal só prossegue após todas terem terminado (sincronização implícita no PAREND).

Podem ser aninhadas usando blocos begin/end para expressar dependências sequenciais dentro de ramos paralelos.

Exemplo: grafo "diamante"

Grafo: S1 → {S2 ∥ S3} → S4

S1;
PARBEGIN
    S2;
    S3;
PAREND;
S4;

Exemplo com ramos mais complexos

Grafo:
  S1 → {S2 → S4 ∥ S3} → S5

S1;
PARBEGIN
    begin
        S2;
        S4;       /* S4 depende de S2, executa após dentro do mesmo ramo */
    end;
    S3;
PAREND;
S5;

Exemplo com aninhamento

Grafo: S1 → {S2 → {S4 ∥ S5} → S6 ∥ S3} → S7

S1;
PARBEGIN
    begin
        S2;
        PARBEGIN
            S4;
            S5;
        PAREND;
        S6;
    end;
    S3;
PAREND;
S7;

---

Fork/Join vs Parbegin/Parend: quando usar cada um

Critério	Fork/Join	Parbegin/Parend
Expressividade	Completa — qualquer grafo	Parcial — só grafos com estrutura aninhada
Legibilidade	Baixa (GOTOs)	Alta (estrutura em blocos)
Implementação	Primitivo de baixo nível	Construção de linguagem de alto nível
Análise formal	Mais flexível	Mais simples de verificar
Equivalente moderno	fork() + wait() (UNIX)	pthread_create() + pthread_join() ou OpenMP #pragma omp parallel

Grafos que Parbegin/Parend NÃO consegue expressar são aqueles com dependências cruzadas (cross-dependencies) — onde o final de um ramo paralelo depende de um ponto intermediário de outro ramo, mas não de seu final.

Exemplo de grafo inexpressível com Parbegin/Parend:

Nota: S4 depende tanto de S2 quanto de S3, e S3 depende de S2. Essa dependência cruzada não tem estrutura hierárquica compatível com PARBEGIN/PAREND.

Um grafo com dependência cruzada entre ramos paralelos não tem estrutura aninhada compatível com PARBEGIN/PAREND — exige Fork/Join com GOTOs.

---

Conexão com primitivas reais do UNIX/POSIX

As notações teóricas têm correspondentes diretos na prática:

Notação teórica	Primitiva UNIX/POSIX	Observação
FORK L	fork()	Cria processo-filho; o pai continua na linha seguinte
JOIN n	wait() / waitpid()	Pai aguarda término de n filhos
PARBEGIN ... PAREND	pthread_create() + pthread_join()	Cada instrução vira uma thread; pthread_join() é o PAREND
PARBEGIN ... PAREND	#pragma omp parallel (OpenMP)	Diretiva de compilador para paralelismo em laços

/* Executável — Parbegin/Parend com 2 threads POSIX */
/* Compile: gcc -o par demo_par.c -lpthread           */
#include <pthread.h>  /* pthread_create, pthread_join  */
#include <stdio.h>

/* Cada função representa uma das tarefas paralelas   */
void *tarefa_S2(void *arg) {
    printf("S2 executando (thread %lu)\n", pthread_self());
    return NULL;
}

void *tarefa_S3(void *arg) {
    printf("S3 executando (thread %lu)\n", pthread_self());
    return NULL;
}

int main(void)
{
    pthread_t t2, t3;   /* handles das duas threads     */

    /* S1 (sequencial antes do PARBEGIN)               */
    printf("S1 concluído\n");

    /* PARBEGIN — dispara S2 e S3 em paralelo          */
    pthread_create(&t2, NULL, tarefa_S2, NULL);
    pthread_create(&t3, NULL, tarefa_S3, NULL);

    /* PAREND — aguarda ambas concluírem (JOIN implícito) */
    pthread_join(t2, NULL);
    pthread_join(t3, NULL);

    /* S4 (sequencial após o PAREND)                   */
    printf("S4: ambas as threads concluídas\n");
    return 0;
}

Executável — requer gcc e a biblioteca pthread (-lpthread). Teste em qualquer sistema Linux.

Atividade prática rápida: compile e execute o código acima. Observe que a ordem de impressão de S2 e S3 pode variar entre execuções — isso é o interleaving em ação. Execute várias vezes para confirmar o não-determinismo.

---

Exercícios

Questões dissertativas

Q1

Explique com suas próprias palavras o que é um grafo de precedência. Qual a semântica de um nó e de uma aresta nesse grafo? Como identificar quais tarefas podem ser executadas em paralelo?

Q2

Considere o seguinte grafo de precedência: S1 → S2; S1 → S3; S2 → S4; S3 → S4; S4 → S5. Escreva o programa equivalente usando a notação Parbegin/Parend.

Q3Difícil

Dado o grafo: S1 → S2; S1 → S3; S2 → S5; S3 → S4; S4 → S5; S5 → S6. Escreva o programa usando Fork/Join. Em seguida, tente escrever com Parbegin/Parend e explique se é possível.

Q4

Explique a semântica exata da primitiva JOIN n. Por que é essencial que JOIN seja uma operação atômica?

Q5

Converta o programa Fork/Join abaixo para um grafo de precedência: count := 2; FORK L1; S2; GOTO L2; L1: S3; L2: JOIN count; S4;

Q6

Qual é a relação entre PARBEGIN/PAREND e pthread_create()/pthread_join() na prática? Escreva o esqueleto de código C que implementa: S1 sequencial, depois S2 e S3 paralelas, depois S4 sequencial.

Q7

Um programador afirma: 'Sempre que possível, devo usar Parbegin/Parend em vez de Fork/Join porque é mais legível.' Avalie criticamente essa afirmação.

Q8

Dado o programa Parbegin/Parend abaixo, construa o grafo de precedência correspondente: S1; PARBEGIN begin S2; S4; end; S3; PAREND; S5;

Q9

Explique o conceito de interleaving. Por que ele torna a programação concorrente mais difícil de depurar do que a programação sequencial?

Q10Difícil

Compare as notações Fork/Join e Parbegin/Parend em termos de: (a) expressividade, (b) legibilidade, (c) equivalente moderno em linguagens de programação.

---

Quiz de múltipla escolha

Quiz10 questões

1. Em um grafo de precedência, o que significa a ausência de aresta (direta ou indireta) entre os nós S_i e S_j?

• a)S_i deve executar antes de S_j obrigatoriamente
• b)S_j deve executar antes de S_i obrigatoriamente
• c)S_i e S_j podem ser executadas em paralelo
• d)S_i e S_j nunca podem ser executadas no mesmo programa
• e)S_i e S_j sempre compartilham dados

2. Na notação Fork/Join, qual é o valor inicial correto do contador passado para JOIN quando se quer sincronizar 3 fluxos paralelos?

• a)0 — o contador começa em zero e vai até 3
• b)1 — representa o fluxo principal
• c)2 — representa apenas os fluxos criados por FORK
• d)3 — representa todos os fluxos que chegam ao JOIN
• e)4 — inclui o fluxo original mais os 3 criados

3. Por que a operação JOIN é especificada como atômica?

• a)Para garantir que todos os processos executem na mesma velocidade
• b)Para evitar que dois fluxos simultâneos corrompam o contador e ambos prossigam (ou nenhum prossiga)
• c)Para forçar a execução sequencial de todos os processos após o JOIN
• d)Para eliminar a necessidade de GOTOs no programa
• e)Para permitir que o escalonador interrompa o JOIN a qualquer momento

4. Qual das seguintes afirmações sobre Parbegin/Parend está CORRETA?

• a)Parbegin/Parend é mais expressivo que Fork/Join e pode representar qualquer grafo
• b)Parbegin/Parend é equivalente em expressividade ao Fork/Join
• c)Parbegin/Parend só pode representar grafos com estrutura de dependências hierarquicamente aninhável
• d)Parbegin/Parend exige o uso de GOTOs para expressar dependências complexas
• e)Parbegin/Parend foi proposto antes do Fork/Join como modelo de concorrência

5. Qual primitiva POSIX Threads corresponde semanticamente ao PAREND da notação Parbegin/Parend?

• a)pthread_create() — cria as threads paralelas
• b)pthread_exit() — encerra a thread atual
• c)pthread_join() — aguarda uma thread terminar
• d)pthread_mutex_lock() — protege seção crítica
• e)pthread_cancel() — cancela uma thread

6. Dado: 'count := 2; FORK L1; S2; GOTO L2; L1: S3; L2: JOIN count; S4;' — quantos processos/fluxos executam S4?

• a)0 — nenhum fluxo chega ao S4
• b)1 — exatamente um fluxo continua após o JOIN
• c)2 — ambos os fluxos continuam após o JOIN
• d)Depende da velocidade dos processos
• e)Depende do valor de count em tempo de execução

7. Qual é a principal limitação do Parbegin/Parend em relação ao Fork/Join?

• a)Parbegin/Parend não pode expressar paralelismo de nenhum tipo
• b)Parbegin/Parend não suporta mais de dois ramos paralelos
• c)Parbegin/Parend não consegue expressar grafos com dependências cruzadas entre ramos paralelos
• d)Parbegin/Parend requer que todas as tarefas tenham o mesmo tempo de execução
• e)Parbegin/Parend não permite aninhamento de blocos paralelos

8. No código: 'S1; PARBEGIN S2; begin S3; S4; end; PAREND; S5;' — qual é a ordem de execução correta?

• a)S1 → S2 → S3 → S4 → S5 (puramente sequencial)
• b)S1 → {S2 ∥ S3} → S4 → S5
• c)S1 → {S2 ∥ (S3 → S4)} → S5
• d)S1 → S2 → {S3 ∥ S4} → S5
• e)S1 → {S2 ∥ S3 ∥ S4} → S5

9. O que é interleaving no contexto de programação concorrente?

• a)A técnica de embaralhar dados de entrada para melhorar o desempenho
• b)O entrelaçamento das instruções de múltiplos processos/threads pelo escalonador, em ordem não determinística
• c)A técnica de dividir um programa em módulos independentes
• d)O mecanismo pelo qual threads compartilham variáveis globais
• e)O processo de criação de um novo processo filho via fork()

10. Qual construção moderna é o equivalente mais direto de Parbegin/Parend em C com suporte a múltiplos núcleos?

• a)fork() + wait() da biblioteca unistd.h
• b)#pragma omp parallel do OpenMP
• c)signal() + sigwait() para comunicação entre processos
• d)pipe() para comunicação entre processos pai e filho
• e)mmap() para memória compartilhada entre processos

---

Referências

Principais (essenciais)

• SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais. 9. ed. LTC, 2015.
  • Seções: 2.2, 2.3, 2.4, 2.5 (interface e chamadas de sistema), 3.3 (operações sobre processos)
• TANENBAUM, A. S. Sistemas Operacionais Modernos. 4. ed. Pearson, 2016.
  • Cap. 2.2 — Threads (modelos de programação concorrente)

Aprofundamento (opcionais)

• STALLINGS, W. Operating Systems: Internals and Design Principles. 9. ed. Pearson, 2018. Cap. 4 — Threads.
• Conway, M. E. "A Multiprocessor System Design." AFIPS Fall Joint Computer Conference, 1963. (artigo original do Fork/Join)
• Dijkstra, E. W. "Cooperating Sequential Processes." Technical Report EWD-123, 1968. (artigo original do Parbegin/Parend)
• GeeksforGeeks — Parbegin/Parend Concurrent Statement (leitura complementar acessível)

---

Recursos Complementares

Opcional — Vídeos selecionados para reforçar os conceitos desta aula.

▶14:35

ENOpcional

Process Management — Processes and Threads

Neso Academy

Revisão do conceito de processo e introdução às threads como unidade de execução paralela — contexto essencial para as notações de concorrência.

▶11:43

ENOpcional

Operating Systems: Crash Course Computer Science #18

CrashCourse

Panorama objetivo sobre concorrência, escalonamento e abstrações de processos, útil para conectar os grafos de precedência com a prática.

▶2:11:13

ENAprofundamento

Introduction to Operating System | Full Course for Beginners

Mike Murphy Co

Para aprofundar em paralelismo e sincronização em uma trilha contínua. Foque nos trechos sobre processos, threads e concorrência.

▶25:00:00

ENAprofundamento

Operating Systems — Full Course (25h)

freeCodeCamp.org

Curso completo de SO. Para esta aula, foque nos módulos sobre Process Management e Concurrency. Use como referência ao longo de todo o semestre.