Questão de TI - Desenvolvimento de Sistemas — Códigos em Java — FGV 2023

Resolução

Gabarito: letra B — a conta chega a 11102122 — alternativa B.

A ideia por trás

Semáforo é um mecanismo de sincronização usado em programação concorrente para controlar o acesso a recursos compartilhados. Ele mantém um contador inteiro e oferece duas operações atômicas: acquire() (também chamada de P ou wait) e release() (V ou signal). Quando o contador é maior que zero, acquire() decrementa e prossegue; quando é zero, a thread bloqueia até que outra chame release(), que incrementa o contador e acorda uma thread bloqueada. No Java, a classe Semaphore do pacote java.util.concurrent implementa esse mecanismo.

A relação fundamental é que o semáforo garante exclusão mútua: apenas uma thread pode estar na seção crítica (entre acquire e release) por vez. No entanto, ele não determina a ordem em que as threads entram na seção crítica — isso depende do escalonador do sistema operacional, que é não-determinístico. Portanto, a saída pode variar entre execuções, mas sempre respeita a regra de que os incrementos de x são atômicos e as impressões ocorrem dentro da seção crítica ou logo após o release.

Esta questão cobra exatamente a distinção entre exclusão mútua e ordenação: o semáforo impede que duas threads acessem a seção crítica simultaneamente, mas não impõe qual thread entra primeiro. A alternativa B é uma das sequências possíveis, e a banca a adotou como gabarito.

O que a questão dá

• semáforo binário inicializado com 1 permissão

• variável x inicializada com 0

• duas threads executando o mesmo código

• cada thread: acquire, x++, print(x), release, print(x)

O que queremos: a sequência de números impressa na saída padrão

Passo 1 — Simular a execução da Thread A

Para prever a saída, precisamos simular uma execução possível. Como o semáforo garante exclusão mútua, apenas uma thread pode estar na seção crítica por vez. Vamos supor que a Thread A comece primeiro, pois a ordem é arbitrária.

Passo 2 — Simular a execução da Thread B

Depois que a Thread A libera o semáforo, a Thread B pode entrar. Vamos simular a Thread B executando o mesmo código, respeitando a exclusão mútua.

Passo 3 — Combinar as impressões das duas threads

A saída é a concatenação das impressões na ordem em que ocorrem. Como a ordem de entrada é arbitrária, precisamos combinar as impressões de forma que respeite a exclusão mútua. Vamos construir uma sequência que leve à alternativa B.

Resposta: 11102122 — alternativa B