Como posso escrever uma estrutura livre de bloqueio?

Question

Na minha aplicação multithreaded e vejo contenção de bloqueio pesado nele, impedindo que boa escalabilidade através de múltiplos núcleos. Eu decidi programação livre uso de bloqueio para resolver esta situação.

Como posso escrever uma estrutura livre de bloqueio?

Answer 1

A resposta curta é:

Você não pode.

Long resposta é:

Se você está fazendo esta pergunta, você não provavelmente sabe o suficiente para ser capaz de criar uma estrutura livre de bloqueio. Criação de estruturas livres de bloqueio é extremamente difícil, e apenas especialistas neste campo pode fazê-lo. Em vez de escrever o seu próprio, procurar uma implementação existente. Quando você encontrá-lo, verificar como é amplamente usado, quão bem ele é documentado, se for bem comprovada, quais são as limitações -. Até mesmo alguns estrutura livre de bloqueio outras pessoas publicados são quebrados

Se você não encontrar uma estrutura livre de bloqueio correspondente à estrutura que você está usando, em vez adaptar o algoritmo de modo que você pode usar algum já existente.

Se você ainda insistem em criar a sua própria estrutura de livre de bloqueio, certifique-se:

• começar com algo muito simples
• entender o modelo de memória de sua plataforma de destino (incluindo leitura reordenação gravação restrições /, quais operações são atômica)
• estudar muito sobre problemas de outras pessoas encontradas ao implementar estruturas livres de bloqueio
• não apenas adivinhar se ele vai trabalhar, provar
• fortemente testar o resultado

Mais leitura:

Lock Free e esperar algoritmos livres em Wikipedia

Herb Sutter: Trava-Free cupom: Uma falsa sensação de segurança

Answer 2

Use uma biblioteca, como Threading Building Blocks da Intel , ele contém muito poucas estruturas de bloqueio -free e algoritmos . Eu realmente não recomendaria tentar código sem bloqueio de gravação si mesmo, é extremamente sujeito a erros e difícil de acertar.

Answer 3

Escrever código livre bloqueio thread-safe é difícil; mas este artigo de Herb Sutter irá ajudar a começar.

Answer 4

Como sblundy salientou, se todos os objetos são imutáveis, somente leitura, você não precisa se preocupar com bloqueio, no entanto, isso significa que você pode ter que copiar objetos muito. Copiando geralmente envolve malloc e malloc usos de bloqueio para alocações de memória sincronizar entre threads, assim objetos imutáveis ??pode comprar-lhe menos do que você pensa (ele próprio malloc escalas bastante mal e malloc é lento , se você faz um monte de malloc em uma seção crítica do desempenho, não espere bom desempenho).

Quando você só precisa atualizar variáveis ??simples (por exemplo, 32 ou 64 bits int ou ponteiros), execute simplesmente operações de adição ou subtração sobre eles ou apenas trocar os valores de duas variáveis, a maioria das plataformas oferecem "operações atômicas" para que (ainda mais CCG ofertas estes também). Atomic não é o mesmo que thread-safe . No entanto, marcas atômicas certeza que, se uma thread escreve um valor de 64 bits para um local de memória, por exemplo, e outra thread lê a partir dele, a uma leitura tanto recebe o valor antes da operação de gravação ou depois da operação de gravação, mas nunca um quebrado value in-between a operação de gravação (por exemplo, aquele em que o primeiro 32 bits já são o novo, o último 32 bit ainda são o valor antigo! Isso pode acontecer se você não usar o acesso atômica sobre um tal variável).

No entanto, se você tem um struct C com 3 valores, que pretende actualizar, mesmo se você atualizar todos os três com operações atômicas, estes são três operações independentes, portanto, um leitor pode ver a estrutura com um valor já ser atualização e dois não sendo atualizado. Aqui você vai precisar de um bloqueio se deve assegurar, o leitor quer vê todos os valores no ser struct o antigo ou os novos valores.

Uma maneira de fazer bloqueios escala muito melhor está usando R / W fechaduras. Em muitos casos, as atualizações de dados são bastante raras (operações de gravação), mas o acesso a dados é muito frequente (leitura dos dados), pense em coleções (Hashtables, árvores). Nesse caso R / W fechaduras você vai comprar um ganho de desempenho enorme, como muitos segmentos pode realizar uma leitura de bloqueio ao mesmo tempo (eles não vão bloquear uns aos outros) e somente se um thread quer um bloqueio de gravação, todos os outros tópicos são bloqueados durante o tempo que a atualização for executada.

A melhor maneira de evitar fio-questões é a de não compartilhar os dados entre threads. Se cada ofertas de rosca maior parte do tempo com dados de nenhum outro segmento tem acesso, você não vai precisar de bloqueio para que os dados em todos os (também operações não atômicas). Portanto, tente compartilhar o mínimo de dados possível entre threads. Então você só precisa de uma maneira rápida de mover dados entre threads se você realmente tem que (ITC, Inter Comunicação Thread). Dependendo do seu sistema operacional, plataforma e linguagem de programação (infelizmente você nos nenhuma delas disse), vários métodos poderosos para ITC pode existir.

E, finalmente, um outro truque para trabalhar com dados compartilhados, mas sem qualquer bloqueio é para garantir que os tópicos não acessar as mesmas partes dos dados compartilhados. Por exemplo. se dois tópicos compartilhar um array, mas só vai acessar mesmo, o outro apenas índices ímpares, você precisa de nenhum bloqueio. Ou se ambos compartilham o mesmo bloco de memória e só se usa a metade superior dele, o outro apenas o inferior, você não precisa de bloqueio. Embora não seja dito, que isso vai levar a bom desempenho; especialmente não em CPUs multi-core. operações de gravação de um segmento para esses dados compartilhados (executando um núcleo) pode forçar o cache para ser liberado para outro segmento (em execução em outro núcleo) e estas liberações do cache são muitas vezes o gargalo de garrafa para aplicações multithread em execução em CPUs multi-core modernos.

Answer 5

Como meu professor (Nir Shavit de "The Art of multiprocessador programação") disse à classe: Por favor, não. A principal razão é a capacidade de teste - você não pode testar o código de sincronização. Você pode executar simulações, você pode até mesmo estresse teste. Mas é aproximação grosseira na melhor das hipóteses. O que você realmente precisa é prova de correcção matemática. E muito poucos capazes compreendê-los, muito menos escrevê-los. Assim, como os outros tinham dito: uso bibliotecas existentes. Blog Joe Duffy levantamentos algumas técnicas (seção 28). O primeiro que você deve tentar é a árvore-splitting -. Pausa para tarefas menores e combinar

Answer 6

A imutabilidade é uma abordagem para bloqueio evitar. Veja discussão Eric Lippert e implementação de coisas como pilhas imutáveis ??e filas .

Answer 7

in re. A resposta de Suma, mostra Maurice Herlithy na arte de multiprocessador de programação que realmente qualquer pode ser escrita sem fechaduras (ver capítulo 6). iirc, Isto essencialmente envolve tarefas de separação em processamento de elementos nodais (como uma função de fecho), e enqueuing cada um. Threads irá calcular o estado, seguindo todos os nós do mais recente em cache. Obviamente, isso poderia, no pior dos casos, resultar em um desempenho sequencial, mas tem propriedades Lockless importantes, impedindo cenários onde tópicos poderia se programadas para fora por longos peroids de tempo quando eles estão mantendo bloqueios. Herlithy também atinge desempenho teórico livre de espera, o que significa que um segmento não vai acabar esperando uma eternidade para ganhar a enqueue atômica (este é um monte de código complicado).

A multi-threaded fila / pilha é surpreendentemente disco (veja a ABA problema ). Outras coisas podem ser muito simples. Se acostumaram a while (true) {atomicCAS até que eu troquei} blocos; eles são incrivelmente poderoso. Uma intuição para o que é correto com CAS pode ajudar o desenvolvimento, mas você deve usar o bom teste e ferramentas talvez mais poderosos (talvez ESBOÇO , próximo MIT Kendo , ou rodada ?) para verificar a correção se você pode reduzi-la a uma estrutura simples.

Por favor, poste mais sobre o seu problema. É difícil dar uma resposta boa, sem detalhes.

Editar immutibility é bom, mas de aplicabilidade é limitada, se eu estou entendendo direito. Realmente não superar os perigos de gravação pós-lidos; considerar dois threads em execução "mem = newNode (MEM)"; eles pudessem ler tanto mem, então ambos escrevemos; não é o correto para a função de incremento clássico. Além disso, é provavelmente lento devido a alocação de pilha (que tem de ser sincronizados através de threads).

Answer 8

Inmutability teria esse efeito. Muda para o resultado objeto em um novo objeto. Lisp funciona desta forma sob as cobertas.

Item 13 do Effective Java explica esta técnica.

Answer 9

Cliff Click tem cúpula alguma grande pesquisa sobre estruturas de dados de bloqueio livre, utilizando máquinas de estados finitos e também postou um monte de implementações para Java. Você pode encontrar seus documentos, slides e implementações em seu blog: http://blogs.azulsystems.com/cliff/

Answer 10

Use uma implementação existente, como esta área de trabalho é o reino de especialistas de domínio e PhDs (se você quer bem feito!)

Por exemplo, há uma biblioteca de código aqui:

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

Answer 11

A maioria dos algoritmos ou estruturas livre-lock começar com alguma operação atômica, ou seja, uma mudança para algum local de memória que uma vez iniciada por um fio será concluído antes de qualquer outra thread pode executar essa mesma operação. Você tem uma tal operação em seu ambiente?

aqui para o papel canônica sobre este assunto.

Além disso, tente este wikipedia artigo artigo para obter mais idéias e links.

Answer 12

O princípio básico para a sincronização de livre-lock é esta:

• sempre que você está lendo a estrutura, você siga a leitura com um teste para ver se a estrutura foi transformado desde que você começou a leitura e repetição até que você consiga ler sem outra coisa que vem junto e mutação enquanto estiver fazê-lo;

• sempre que você está transformando a estrutura, você organizar o seu algoritmo e os dados de modo que haja uma única etapa atômica que, se tomadas, faz com que toda a mudança para se tornar visível para os outros segmentos, e organizar as coisas de modo que nenhum da mudança é visível a menos que passo é dado. Você usar qualquer lockfree mecanismo atômica existe em sua plataforma para essa etapa (por exemplo, comparar-and-set, ligada carga + store-condicional, etc.). Nesse passo que você deve, então, verificar para ver se qualquer outro segmento sofreu uma mutação do objeto desde a operação mutação começou, comprometer se não tem e começar de novo se ele tem.

Há uma abundância de exemplos de estruturas de livre-lock na web; sem saber mais sobre o que você está implementando e em que plataforma é difícil ser mais específico.

Answer 13

Se você estiver escrevendo suas próprias estruturas de dados livre-lock para uma CPU multi-core, não se esqueça sobre barreiras de memória! Além disso, considerar olhando para técnicas Software Transação memória .

Answer 14

Bem, isso depende do tipo de estrutura, mas você tem que tornar a estrutura para que ele cuidadosamente e detecta silenciosamente e lida com possíveis conflitos.

Eu duvido que você pode fazer um que é 100% livre de bloqueio, mas, novamente, depende de que tipo de estrutura que você precisa para construir.

Você também pode precisar de caco a estrutura para que os vários segmentos trabalhar em itens individuais, e, posteriormente, sincronizar / recombinam.

Answer 15

Como mencionado, ele realmente depende de que tipo de estrutura que você está falando. Por exemplo, você pode escrever uma fila de livre-lock limitado, mas não aquele que permite o acesso aleatório.

Answer 16

Reduzir ou eliminar o estado mutável compartilhado.

Answer 17

Em Java, utilizar os pacotes java.util.concurrent em JDK 5 + em vez de escrever o seu próprio. Como foi mencionado acima, este é realmente um campo para especialistas, ea menos que você tem um ano de reposição ou dois, rolando seu próprio não é uma opção.

Answer 18

Você pode esclarecer o que entende por estrutura?

Agora, eu estou supondo que você quer dizer a arquitetura geral. Você pode realizá-lo por não compartilhar memória entre processos, e usando um modelo de ator para seus processos.

Answer 19

Dê uma olhada no meu ligação ConcurrentLinkedHashMap para um exemplo de como escrever um bloqueio estrutura de dados -livre. Ele não se baseia em quaisquer trabalhos acadêmicos e não requer anos de pesquisa como outros implicam. Ele simplesmente pega engenharia cuidadosa.

Meu implementação usa um ConcurrentHashMap, que é um algoritmo de lock-per-balde, mas não contam com esse detalhe de implementação. Pode ser facilmente substituído com a implementação livre de bloqueio de Cliff Click. Peguei emprestado uma idéia de Cliff, mas usado muito mais explicitamente, é modelar todas as operações CAS com uma máquina de estado. Isso simplifica muito o modelo, como você vai ver que eu tenho fechaduras pseudo através dos estados ING. Outro truque é permitir que a preguiça e determinação, conforme necessário. Você vai ver isso muitas vezes com recuo ou deixar outros tópicos "ajuda" para limpeza. No meu caso, eu decidi permitir que nós mortas na lista de ser despejada quando atingem a cabeça, ao invés de lidar com a complexidade de removê-los a partir do meio da lista. Eu posso mudar isso, mas eu não inteiramente confiar no meu algoritmo de retrocesso e queria adiar uma mudança importante como adotar uma abordagem de bloqueio de 3 nós.

O livro "The Art of multiprocessador programação" é um grande primer. No geral, porém, eu recomendo evitando projetos sem bloqueio no código do aplicativo. Muitas vezes é simplesmente um exagero, onde outra, menos propenso a erros, as técnicas são mais adequadas.

Answer 20

Se você ver contenção de bloqueio, eu primeiro tentar usar bloqueios mais granulares em suas estruturas de dados ao invés de completamente lock-livre algoritmos.

Por exemplo, eu atualmente trabalho no aplicativo com vários segmentos, que tem um sistema de mensagens personalizado (lista de filas para cada tópicos, a fila contém mensagens para thread para processo) para passar informações entre threads. Há um bloqueio global sobre esta estrutura. No meu caso, eu não preciso de velocidade muito, por isso realmente não importa. Mas se esse bloqueio se tornaria um problema, ele poderia ser substituído por bloqueios individuais em cada fila, por exemplo. Em seguida, adicionar / remover elemento de / para a fila específica que fez não afeta outras filas. Ainda haveria um bloqueio global para adicionar nova fila e tal, mas não seria muito sustentou.

Mesmo uma única fila de vários produz / consumidor pode ser escrita com bloqueio granular em cada elemento, em vez de ter um bloqueio global. Isso também pode eliminar a disputa.

Answer 21

Se você ler várias implementações e documentos sobre o assunto, você vai notar que há o seguinte tema comum:

1) compartilhados objetos de estado são lisp / style clojure inmutable : ou seja, todas as operações de gravação são implementadas copiar o estado existente em um novo objeto, modificações dar para o novo objeto e, em seguida, tentar atualização o estado compartilhado (obtido a partir de um ponteiro alinhada que pode ser actualizado com o CAS primitivo). Em outras palavras, você nunca modificar um objeto existente, que pode ser lido por mais do que o segmento atual. Inmutability pode ser otimizada utilizando a semântica copy-on-write para grande, objetos complexos, mas isso é uma outra árvore de nozes

2) você especificar claramente o que permitiu a transição entre o estado atual e no próximo são válidos : Então validar que o algoritmo é válido se tornar ordens de magnitude mais fácil

3) Handle descartado referências em listas ponteiro perigo por thread . Depois que os objetos de referência são seguros, reutilização, se possível

Veja outro post relacionado de mina onde algum código implementado com semáforos e semáforos é (parcialmente) reimplemented em um estilo livre-lock: exclusão mútua e semáforos