Limites para coleções sem bloqueio?

David Rodríguez - dribeas escreveu em um comentário no StackOverflow que "Nem todas as coleções podem ser implementadas sem bloqueios". Não tenho certeza se isso é verdade e não consigo encontrar provas de qualquer maneira.

Essa declaração não é muito precisa, mas deixe-me reformulá-la de uma maneira um pouco mais formal: para cada tipo de coleção C, existe um tipo de coleção sem bloqueio C_LF que oferece o mesmo conjunto de operações e onde cada operação no C_LF tem a mesma complexidade big-O que a operação correspondente ativada C.

A propósito, não espero uma transformação.

Como eu estava um pouco confuso, começo esclarecendo alguns conceitos na questão.

Coleção . Não vejo razão para gastar tempo definindo rigorosamente o que "coleção" significa quando podemos simplesmente perguntar o que acontece com estruturas de dados em geral. Uma estrutura de dados ocupa uma parte da memória e possui algumas operações que podem acessar essa memória e que podem ser invocadas pelos usuários . Esses usuários podem ser processadores distintos ou apenas threads diferentes, isso não nos interessa. Tudo o que importa é que eles possam executar operações em paralelo.

Sem bloqueio . Herlihy e Boss dizem que uma estrutura de dados fica livre de bloqueios quando um usuário com falha não impede novos usos da estrutura de dados. Por exemplo, imagine que você derrame água em um processador que está no meio da inserção de um nó em um conjunto classificado. Bem, se outros processadores tentarem inserir posteriormente nesse conjunto classificado, eles terão êxito. ( Editar: De acordo com esta definição, é o caso de que, se uma estrutura de dados usa bloqueios então é não bloquear-livre, mas é não o caso de que, se uma estrutura de dados não usa fechaduras, em seguida, que é isento de bloqueio.)

Com essas definições, acho que Herlihy e Boss basicamente dizem que a resposta é transformar regiões críticas em transações.

Mas, você pode perguntar, isso tem a mesma complexidade? Não sei se a pergunta faz sentido. Considere push(x) { lock(); stack[size++] = x; unlock(); }. Esta é uma operação de tempo constante? Se você ignorar a operação de bloqueio e, portanto, outros usuários, poderá responder SIM. Se você não deseja ignorar outros usuários, realmente não há como dizer se o push será executado em tempo constante. Se você subir um nível e ver como a pilha é usada por algum algoritmo específico, poderá dizer que o push sempre levará tempo constante (medido agora em termos do que quer que seja a entrada do seu algoritmo paralelo). Mas isso realmente é uma propriedade do seu algoritmo, portanto, não faz sentido dizer que o push é uma operação de tempo constante.

Em resumo, se você ignorar o quanto um usuário executando uma operação aguarda outros usuários, o uso de transações em vez de regiões críticas responde afirmativamente à sua pergunta. Se você não ignorar o tempo de espera, precisará ver como a estrutura de dados é usada.

Eu acho que "COLEÇÕES" significa "filas, pilhas, listas vinculadas, árvores, ..."

De http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

Através de um design e implementação cuidadosos, é possível construir estruturas de dados seguras para uso simultâneo sem a necessidade de gerenciar bloqueios ou encadeamentos de blocos. Essas estruturas de dados sem bloqueio podem aumentar o desempenho, permitindo simultaneidade extra e podem melhorar a robustez, evitando alguns dos problemas causados ​​pela inversão de prioridade nas configurações locais ou por falhas de máquinas e links em sistemas distribuídos.

A melhor introdução geral aos nossos algoritmos sem bloqueio é o artigo Programação simultânea sem bloqueios, atualmente em fase de submissão, que abrange nossos projetos de memória transacional de software baseada em palavras e de comparação e troca de várias palavras, e memória transacional de software baseada em objetos.

Se "sem bloqueio" significa "não use semáforos, mutex, monitores, ..." do sistema operacional, então acho (mas não sou especialista) que toda coleção pode ser feita sem bloqueio usando leitura atômica de gravação / gravação modificar primitivas que devem ser suportadas pelo hardware.

$O(\cdot)$

Documentação exaustiva sobre o assunto pode ser encontrada online:

http://www.google.it/search?q=lock+free+algorithm+filetype%3Apdf

(... e mais referências no final de cada documento)