Relatório: Exclusão Mútua

Construir mecanismos para garantir a exclusão mútua entre processos ou threads não é

uma tarefa trivial. Esta página traz alguns exemplos de mecanismos para obter a exclusão

mútua - alguns dos quais não funcionam!

O código de base consiste em 100 threads, onde cada thread tenta fazer 100.000

incrementos em uma variável global compartilhada sum. Se tudo correr bem, o valor final

da variável sum deve ser 100×100.000 = 10.000.000.

Exclusão Mútua

Exclusão mútua é uma técnica utilizada em programação concorrente que evita que dois

processos ou threads tenham acesso simultâneo a um recurso compartilhado, acesso esse

chamado de seção crítica.

Sem coordenação (me1-none.c)

Compilando e rodando o programa me1-none.c obtémO código de base consiste em 100 threads, onde cada thread tenta fazer 100.000

incrementos em uma variável global compartilhada sum. Se tudo correr bem, o valor final

da variável sum deve ser 100×100.000 = 10.000.000.

Exclusão Mútua

Exclusão mútua é uma técnica utilizada em programação concorrente que evita que dois

processos ou threads tenham acesso simultâneo a um recurso compartilhado, acesso esse

chamado de seção crítica.

Sem coordenação (me1-none.c)

Compilando e rodando o programa me1-none.c obtém-se o seguinte resultado:

No programa em questão, todas as 100 threads criadas tem acesso à seção crítica,

manipulando a variável sum, visto que não há nenhuma forma de controle de acesso simultâneo,

levado a um resultado diferente do esperado.

A solução ingênua (me2-naive.c)

Compilando e rodando o programa me2-naive.c obtém-se o seguinte resultado:

No programa em questão foi implementada uma variável de controle busy, que controla

a entrada na seção crítica. Porém, ao analisar-se a saída do programa, vê-se que o problema de

múltiplas threads acessando a seção crítica simultaneamente ainda ocorre. Observando-se o

código do programa me2-naive.c, percebe-se que a variável busy de nada serve, pois a mesma

não realiza de fato o controle ao acesso da seção crítica, visto que todas as threads tem acesso

também à variável busy dentro das funções enter_cs e leave_cs.

Alternância (me3-altern.c)

Compilando e rodando o programa me3-altern.c obtém-se o seguinte resultado:

No programa me3-altern.c é definida uma variável turn, que indica quem pode acessar a

seção crítica a cada instante. Saindo da seção crítica, cada thread incrementa o valor de turn,

liberando o acesso a próxima thread a seção crítica. O resultado tende ao esperado, porém

somente 1 thread tem acesso à seção crítica por vez, e as outras threads ficam em espera ativa,

verificando o valor de turn a todo momento, até que sua vez de acessar a seção crítica chegue,

gerando assim um grande desperdício de CPU, que pode ser observado pela imagem acima,

onde o programa rodou por mais de 10 minutos e ainda assim não chegou ao resultado esperado.

A instrução TSL (me4-tsl.c)

Compilando e rodando o programa me4-tsl.c obtém-se o seguinte resultado:

No programa me4-tsl.c é utilizada uma estrutura do tipo Test-and-Set Lock, construída a

partir de uma operação OR atômica,

...