Return to search

Estruturas de dados concorrentes: um estudo de caso em skip graphs. / Concurrent data structures: a case-study on skip graphs

Muitos dos sistemas de computação existentes atualmente são concorrentes, ou seja, neles constam diversas entidades que, ao mesmo tempo, operam sobre um conjunto de recursos compartilhados. Nesse contexto, devemos controlar a concorrência das diversas operações realizadas, ou então a interferência entre elas poderia causar inconsistências nos recursos compartilhados ou nas próprias operações realizadas. Nesse texto, vamos tratar especificamente de estruturas de dados concorrentes, ou seja, estruturas de dados cujas operações associadas -- consideramos inserção, remoção e busca -- sejam passíveis de execução simultânea por diversas entidades. Tendo em vista o controle da concorrência, vamos adotar uma abordagem baseada no emprego de locks, uma primitiva de sincronização muito usual na literatura. Nossa discussão será apresentada em termos de certas estruturas de dados chamadas skip graphs, que têm propriedades interessantes para outros contextos, como o contexto de sistemas distribuídos. / Many existing computer systems are concurrent, or, in other words, they are composed of many entities that, at the same time, operate over some set of shared resources. In this context, we must control the concurrency of the operations, otherwise the interference between them could cause inconsistencies in the shared resources or in the operations themselves. In this text, we specifically discuss concurrent data structures, or, in other words, data structures over which the associated operations -- we consider insertion, removal and search -- could be executed simultaneously by various entities. In order to control the concurrency, we will employ an aproach based on the use of locks, a widely known synchronization primitive in the literature. Our discussion will be presented in terms of data structures called skip graphs, which have interesting properties in other contexts, as the context of distributed systems.

Identiferoai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-29092008-132758
Date27 August 2008
CreatorsMendes, Hammurabi das Chagas
ContributorsFernandes, Cristina Gomes
PublisherBiblioteca Digitais de Teses e Dissertações da USP
Source SetsUniversidade de São Paulo
LanguagePortuguese
Detected LanguageEnglish
TypeDissertação de Mestrado
Formatapplication/pdf
RightsLiberar o conteúdo para acesso público.

Page generated in 0.002 seconds