Estruturas de dados de árvore simultâneas sem tempo de atualização e sem trava?

20

Ultimamente, tenho lido um pouco da literatura e encontrei algumas estruturas de dados bastante interessantes.

Eu pesquisei vários métodos diferentes para reduzir o tempo de atualização para pior caso, o tempo de atualização [1-7].O(1)

Recentemente, comecei a procurar estruturas de dados sem bloqueio, para oferecer suporte ao acesso simultâneo eficiente.

Alguma dessas técnicas de tempo de atualização do pior caso foi usada na implementação de estruturas de dados sem bloqueio?O(1)

Eu pergunto porque; para mim, elas parecem a extensão prática óbvia desse "aprimoramento teórico".


  1. Tarjan, Robert Endre. “Atualizando uma árvore de pesquisa equilibrada em rotações O (1).” Cartas de processamento de informações 16, no. 5 (1983): 253 - 257.

  2. Driscoll, JR, N Sarnak, DD Sleator e RE Tarjan. “Tornando as estruturas de dados persistentes.” Nos Anais do XVIII Simpósio Anual da ACM sobre Teoria da Computação, 109–121. STOC '86. Nova York, NY, EUA: ACM, 1986.

  3. Levcopoulos, C. e Mark H. Overmars. “Uma árvore de pesquisa equilibrada com O (1) pior caso de atualização de tempo.” Acta Inf. 26, n. 3 (novembro de 1988): 269–277.

  4. Fleischer, Rudolf. Uma árvore de pesquisa equilibrada simples com tempo de atualização de pior caso O (1)

  5. Dietz, Paul F. e Rajeev Raman. “Uma árvore de pesquisa de dedos com tempo de atualização constante.” Cartas de processamento de informações 52, no. 3 (1994): 147 - 154.

  6. Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas e Kostas Tsichlas. “Novas árvores dinâmicas de pesquisa balanceada com tempo de atualização constante de pior caso.” J. Autom. Lang. Pente. 8, n. 4 (julho de 2003): 607–632.

  7. Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis e Kostas Tsichlas. “Árvores ideais para pesquisa de dedos na máquina de ponteiro.” J. Comput. Syst. Sci. 67, n. 2 (setembro de 2003): 381–418.

AT
fonte
2
Considere adicionar links aos documentos como cortesia para as pessoas que desejam investigar seu problema.
Raphael
3
Ok, adicionado nos links para os respectivos artigos.
AT
1
Sugiro reposicionar em cstheory.SE (com um link aqui) se você não receber uma resposta útil em breve.
18412 JeffE
Eu usei a biblioteca de estruturas de dados Practical-free antes. Eles têm algum suporte para estruturas de dados em árvore sem bloqueio. Talvez tenha o que você está procurando.
Reza

Respostas:

4

O(1) não ajuda por si só. Em uma estrutura de dados sem bloqueio, é necessário haver uma única instância atômica quando sua estrutura de dados parece mudar. Todos os invariantes de representação precisam estar em vigor imediatamente antes e imediatamente após aquele instante atômico.

Isso significa que, se você estiver fazendo uma modificação na estrutura de dados, a característica importante é que você pode fazer todos os mods em uma estrutura de dados privada e depois trocar as modificações em uma única instrução atômica.

A liberdade de bloqueio geralmente é mais fácil quando suas estruturas de dados são imutáveis ( puramente funcionais ). Você simplesmente mantém um ponteiro global para a versão atual da estrutura de dados. Os leitores não precisam bloquear nada. As modificações na estrutura de dados são efetuadas trocando o ponteiro global para uma estrutura de dados imutável por outra.

Por exemplo: se você tem uma árvore equilibrada puramente funcional, você:

  1. Registre o ponteiro global atual na raiz da árvore.
  2. Crie uma nova árvore que insira ou exclua um nó. (Isso é logarítmico no tempo e no espaço no número de nós atualmente na árvore e envolve a criação de novos nós desde o ponto de modificação até a raiz e apenas apontando tudo de novo nas partes antigas da versão anterior da estrutura de dados. )
  3. Compare e troque atomicamente o ponteiro global para a raiz. (Observe que isso pode falhar se outra modificação ocorrer entre o momento em que você gravou o ponteiro raiz antigo e agora. Se isso acontecer, volte para a etapa 1 e tente novamente. Isso é chamado de "controle de concorrência otimista".)

Observe que a parte mais importante é o que eu disse acima sobre a necessidade de manter invariantes de representação. Geralmente, não é suficiente ter um algoritmo que faça uma alteração atomicamente no meio da árvore. Por quê? Por exemplo: você pode ter um encadeamento de leitor que está no processo de fazer uma travessia de pré-encomenda da árvore. Se você modificar um nó que é um ancestral do nó que eles estão lendo no momento, você invalidará as condições prévias que eles pensavam que haviam imposto. O leitor precisa poder trabalhar com a estrutura de dados exatamente como era antes de você fazer sua alteração, ou exatamente como será depois que você fizer sua alteração. Não é algo no meio.

Edit : Como o @Raphael apontou, existem técnicas para tornar as estruturas de dados mutáveis ​​livres de bloqueio. Uma prova por construção de que isso sempre pode ser feito é: Contanto que você tenha um único ponteiro global para o "topo" da sua estrutura de dados, mesmo que seja mutável, você sempre poderá copiar toda a estrutura de dados, fazer seus mods para o copiar e, em seguida, usando o controle de concorrência otimista, tente comparar e trocar o ponteiro para sua estrutura de dados recém-criada para o original. A beleza das estruturas funcionais de dados baseadas em árvore é que elas mantêm o custo da cópia baixo em de uma estrutura de dados tamanho .O ( N )O(log(N))O(N)

Lógica Errante
fonte
Eu acho que as técnicas de espera ativa, por exemplo, com comparação e troca, geralmente são chamadas de "bloqueio livre", então existem algumas maneiras de sair, mesmo na configuração mutável.
Raphael
Não estou familiarizado com o termo espera ativa (e o Google não está ajudando). (Se você está falando sobre o trabalho de Kogan e Petrank, isso mostra como transformar algoritmos sem bloqueio em livres de espera.) Adicionei uma edição sobre como lidar com a mutabilidade da liberdade de bloqueio em geral.
Wandering Logic
Por "espera ativa", quero dizer algo como while ( !P ) { noOp(); } doWork();onde noOppode ser um sleepou semelhante.
Raphael
Na parte Editar , você mencionou a técnica para tornar as estruturas de dados mutáveis ​​livres de bloqueios. Conforme indicado, copiamos toda a estrutura de dados, modificamos a cópia e usamos a primitiva CAS. No entanto, como tornar o Copypasso atômico? Parece ser outro problema difícil de atomic snapshot.
Hengxin
@ hengxin: pense no primitivo CAS como um operador de "publicação". Antes da publicação da estrutura de dados, apenas o thread que faz as modificações tem acesso a ela. Depois que a estrutura de dados é publicada, é imutável. A etapa de cópia não precisa ser atômica porque a única coisa que um encadeamento pode estar copiando é uma versão publicada, imutável. Se dois encadeamentos tentarem mutar simultaneamente, ambos copiam a mesma estrutura de dados imutáveis, modificam suas cópias locais e, em seguida, uma das operações do CAS é bem-sucedida e a outra falha. O que falhar precisa recopiar e atualizar.
Wandering Logic