Primer resultado en Google para "vector libre de cerrojo" es un trabajo de investigación escrito por Damian Dechev, Peter Pirkelbauer y Bjarne Stroustrup que describe un vector teórico sin cerrojo. ¿Se ha implementado este u otro vector sin bloqueos?¿Hay una implementación de vector sin bloqueo?
MS proporciona ppl :: concurrent_vector e Intel proporciona tbb :: concurrent_vector. En Windows, al menos, ppl y tbb son parte del C-Runtime.
* Concurrente * y sin bloqueo son cosas completamente diferentes –
Tiene la razón, es simultáneo y no tiene bloqueos. Tenía la impresión de que la implementación de MS ppl de concurrent_vector estaba libre de bloqueos. ¿No es así? – Unknown1987
Tiendo a suponer que, a menos que se especifique lo contrario, ninguna biblioteca está bloqueada, y no he visto ninguna referencia en un vistazo rápido a la documentación que indica que ppl :: concurrent_vector no tiene cerrojo. –
Acabo de ver qué es un vector, en la wikipedia.
Creo (solo un minuto o dos de pensar, por supuesto) una versión totalmente libre de bloqueos es un poco problemática.
Considerar; creas la matriz, accedes a ella de forma normal, etc. Para esto no necesitas estar libre de bloqueos. El problema viene cuando necesitas cambiar el tamaño. El hilo que entra y descubre esto necesita malloc. Esta es una operación realmente única: otros hilos en este punto deben bloquearse/girar. Si intentaron ayudar, p. hacer el malloc ellos mismos, podría tener muchos hilos emitiendo el malloc. Ahora bien, podría ser que en la práctica el número de subprocesos es bajo, está bien, en cuyo caso puede tener una cantidad de subprocesos ejecutando el malloc, con el ganador activando atómicamente la nueva memoria y los perdedores viendo esto y luego libre () ing su memoria.
Luego de realizar la copia, cuando un hilo trata de acceder a un elemento, así, tendremos que hacer un seguimiento de todos los de las matrices asignadas en una lista, y se accede a ellos a través de la lista, el más antiguo primero , hasta que encontremos el elemento que queremos y, si no está en la matriz más reciente, lo movemos y luego accedemos a él.
También necesitamos una forma para que un hilo sepa que ha movido el elemento final y puede liberar ese conjunto, así que tendremos que contar los elementos; entonces tenemos un riesgo de requisitos de asignación potencialmente ilimitados. Lo que es más, la estructura de datos (he dicho una lista, pero podrían ser otras cosas, aunque no serán tan buenas, prolíficamente) tendrá que ser atómica (ya que quizás los hilos podrían eliminar una matriz al mismo tiempo) y una lista atómica sin cerraduras fue hasta hace poco el pináculo de las estructuras de datos sin cerraduras, tan complejas como pueden ser, que requieren SMR y con una implementación compleja.
(digo hasta hace poco - Hace poco alguien inventó un árbol rojo-negro sin bloqueo, todo el asunto, añadir y borrar!)
TBH, no entiendo por qué alguien podría usar un vector. ¿Por qué no usar simplemente un árbol binario equilibrado o un hash?
http://www.linuxsoftware.co.nz/containerchoice.png –
Tal vez [libcds] (http://libcds.sourceforge.net/)? –
¿Podría el votante de bajos explicarse a sí mismo? – qdii
votos cojos – Justicle