algorithm - moz - Cómo implementar la lista de salto sin bloqueo

title tag

Question

Necesito implementar una lista de omisión sin bloqueo. Intenté buscar papeles. Desafortunadamente, todo lo que encontré fueron listas enlazadas únicas sin bloqueo (en muchos tipos) Sin embargo, ¿cómo implementar la lista de salto sin bloqueo?

Answer 1

Las listas de salto sin bloqueo se describen en el libro El arte de la programación con multiprocesadores y en el informe técnico Práctico libertad de bloqueo , que se basa en una tesis doctoral sobre el tema. La discusión de la lista de omisión comienza en la página 53. Este proyecto de código de Google incluye una implementación de ejemplo, basada en estas fuentes.

Hay discusiones relacionadas, enlaces a publicaciones e implementaciones (no necesariamente sin bloqueo) en la Lista de omisión de preguntas de SO vs. Árbol binario , y Listas de omisión: ¿las ha usado alguna vez? .

Answer 2

Este documento presenta una lista de saltos sin bloqueo y sin espera. Es fácil de implementar: lo implementé hace unas semanas como parte de Intel Threading Challenge 2010 (consulte la pestaña SkipList en la mitad de la página).

Java incluye una implementación de una lista de omisión simultánea, java.util.concurrent.ConcurrentSkipListMap .