Estudo de Estruturas de Dados Não Bloqueantes e Análise de Impacto do seu uso sobre uma Aplicação Paralela

Abstract

Usufruir da capacidade de processar requisições simultaneamente ou paralelamente é uma forma comum de aumentar o desempenho computacional. A programação concorrente, entretanto, impõe desafios gerados pelo impacto de diferentes unidades de processamento trabalharem com dados sobre um mesmo espaço de memória. Para garantir o progresso de um sistema concorrente a estados consistentes é prático definir regiões críticas e utilizar de mecanismos de exclusão mútua. Estruturas de dados preparadas para acesso concorrente podem ser projetadas utilizando desse método, fazendo com que determinada área da estrutura não tenha acessos simultâneos, permitindo uma aquisição da área por um processo, e colocando os outros processos em espera. Essa forma de lidar com os acessos concorrentes pode inibir o paralelismo e colocar em espera processos por tempo indeterminado. Apesar disso, estruturas de dados podem ser construídas com garantias quanto ao não-bloqueio e progresso. Uma estrutura lock-free garante o progresso de ao menos um processo em um número finito de passos na realização de operações sobre a estrutura; e em uma estrutura wait-free o progresso em um número finito de passos é garantido para todos os processos. Essas garantias são altamente desejadas em sistemas distribuídos, que aproveitam do poder de processamento de nós distribuídos em uma rede para fornecer garantias como disponibilidade, escalabilidade e concorrência. Porém estruturas eficientes com essas propriedades são difíceis de construir. Neste trabalho, foram estudadas construções de estruturas que fornecem essas garantias e avaliou o impacto de seu uso em uma aplicação paralela. Para a análise de desempenho, foram conduzidas simulações e testes em uma aplicação modificada, adaptada para incorporar essas estruturas de dados. Antes desse processo, também foi verificada a disponibilidade de implementações em bibliotecas de programação existentes, as quais oferecem ferramentas para a construção de ambientes com tais características.