É um bloqueio (espera) livre possível lista duplamente ligada?

Question

Esta pergunta com C # tag, mas se for possível, deve ser possível em qualquer idioma.

É possível implementar uma lista duplamente ligada usando operações bloqueadas para fornecer sem espera de bloqueio? Eu gostaria de inserir, adicionar e remover e limpar sem esperar.

Answer 1

Uma simples busca no Google irá revelar muitos papéis lista duplamente ligados livre-lock.

No entanto, eles são baseados em CAS atômica (compare e swap).

Eu não sei como atômica as operações em C # são, mas de acordo com o site

http://www.albahari.com/threading/part4.aspx

operações C # só são garantidos para ser atômica para ler e escrever um campo de 32 bits. Nenhuma menção de CAS.

Answer 2

Sim, é possível, aqui está a minha aplicação de um STL-como Bloquear-Free duplamente vinculada lista em C ++.

código de exemplo que gera threads para executar aleatoriamente ops em um lista

Ela exige um 64-bit comparar-and-swap para operar sem problemas ABA. Esta lista só é possível por causa de um livre-lock gerenciador de memória .

Confira o benchmarks na página 12 . Desempenho da lista escala linearmente com o número de tópicos como contenção aumenta. O paralelismo algoritmo suportes para acessos disjuntos, de modo a contenção tamanho da lista aumenta pode diminuir.

Answer 3

Aqui está uma papel que discribes um bloqueio livre lista doublly ligados.

Apresentamos um eficiente e prático implementação livre-lock de um concorrente deque ou seja disjuntos-paralelo acessível e usos primitivas atômicas que estão disponíveis em sistemas de computadores modernos. Anteriormente algoritmos livre de fechadura conhecidos de deques ou são baseados em não-disponíveis primitivas de sincronização atômicas, única implementar um subconjunto do funcionalidade, ou não são concebidos para acessos disjuntos. Nosso algoritmo é com base em uma lista duplamente ligada, e requer apenas uma única palavra comparar-and-swap ...

Ross Bencina tem algumas ligações realmente boas que eu só encontrei com papéis numerious e excamples código fonte para " Algumas notas sobre algoritmos sem bloqueio e sem espera ".

Answer 4

Eu não acredito que isso é possível, desde que você está tendo para definir múltiplas referências em um tiro, e as operações interligadas são limitados em seu poder.

Por exemplo, tomar a operação de adição - se você está inserindo o nó B entre A e C, você precisa definir B-> seguinte, B-> prev, A-> seguinte, e C-> prev em um atômica Operação. Interlocked não pode lidar com isso. elementos do pré-ajuste B nem sequer ajuda, porque outro segmento pode decidir fazer uma inserção enquanto você está se preparando "B".

Eu concentrar mais em obter o bloqueio como de grão fino quanto possível, neste caso, não tentando eliminá-lo.

Answer 5

Leia a nota - eles pretendem puxar ConcurrentLinkedList de 4,0 antes da versão final do VS2010

Answer 6

Bem, você realmente não tenho perguntou como fazê-lo. Mas, desde que você pode fazer uma CAS atômica em C # é perfeitamente possível.

Na verdade eu só estou trabalhando através de uma implementação de um livre lista de espera duplamente ligada em C ++ no momento.

Aqui está o papel descrevendo-o. http://www.cse.chalmers.se/~tsigas/papers /Haakan-Thesis.pdf

E uma apresentação que também pode fornecer algumas pistas. http://www.ida.liu.se/ ~ chrke / cursos / Multi / diapositivos / Lock-Free_DoublyLinkedList.pdf

Answer 7

É possível algoritmos livres de bloqueio de gravação para todas estruturas de dados copiáveis ??na maioria das arquiteturas [1]. Mas é difícil para escrever os eficientes.

Eu escrevi um implementação do lista duplamente ligada livre-lock por Håkan Sundell e Philippas Tsigas para .Net. Note que ele não suporta PopLeft atômica devido ao conceito.

[1]: resultados Impossibilidade e universalidade para espera-: Maurice Herlihy freesynchronization (1988)

Answer 8

FWIW, .NET 4.0 está adicionando um ConcurrentLinkedList, um threadsafe lista duplamente ligada no namespace System.Collections.Concurrent. Você pode ler o documentação ou o post descrevendo-o.

Answer 9

Eu diria que a resposta é um muito profundamente qualificado "sim, é possível , mas difícil". Para implementar o que você está pedindo, você precisa basicamente algo que compile as operações em conjunto para garantir que não haja colisões; como tal, seria muito difícil para criar uma aplicação geral para o efeito, e ele ainda teria algumas limitações significativas. Provavelmente seria mais simples para criar uma implementação específica adaptada às necessidades específicas, e mesmo assim, não seria "simples" por qualquer meio.