Cómo implementar la lista de salto libre de bloqueo

Question

necesito para implementar una lista de salto libre de bloqueo. Traté de buscar documentos. Por desgracia todo lo que encontré fue listas enlazadas individuales sin bloqueo (en muchos sabores). Sin embargo la forma de aplicar la lista de salto libre de la cerradura?

Answer 1

Mostrar listas de bloqueo libres se describen en el libro El arte de la programación de multiprocesador , y el informe técnico práctico bloqueo libertad , que se basa en una tesis doctoral sobre el tema. La lista de discusión de salto comienza en la página 53. Un ejemplo de implementación, en base a estas fuentes, se incluye en este Google proyecto de código de .

Hay discusiones relacionadas, enlaces a la literatura y las implementaciones (no necesariamente lock-libre) en las preguntas de SO Lista Saltar vs Binary Tree y listas skip - nunca las usaron .

Answer 2

Este documento presenta una lista de salto sin bloqueo y sin esperar. Es sencillo de implementar - He implementado esto hace unas semanas como parte de la Intel Threading de Challenge 2010 (ver la pestaña SkipList mitad de la página.)

Java incluye una implementación de una lista de salto concurrente, java .util.concurrent.ConcurrentSkipListMap .