Si uso bloqueos, ¿puede mi algoritmo seguir sin bloqueo?

Una definición común de sin bloqueo es que al menos un proceso avanza. ¹

Si tengo una estructura de datos simple, como una cola, protegida por un bloqueo, entonces un proceso siempre puede avanzar, ya que un proceso puede adquirir el bloqueo, hacer lo que quiera y liberarlo.

Entonces, ¿cumple con la definición de sin bloqueo?

¹ Véase, por ejemplo, M. Herlihy, V. Luchangco y M. Moir. Sincronización sin obstrucciones: colas de doble final como ejemplo. En Computación distribuida, 2003. "Está libre de bloqueos si solo garantiza que algún subproceso siempre progresa".

Esa no es una definición de sin bloqueo.

Si puede garantizar el progreso, entonces tiene un punto muerto libre , y si tiene la finalización eventual de cada solicitud, entonces tiene un hambre libre , pero no un bloqueo.

Me pregunto si su simple ejemplo realmente proporciona esto de todos modos. Necesita jerarquías de bloqueo, etc. para garantizar realmente el progreso cuando hay varios bloqueos involucrados.

He estudiado El arte de la programación multiprocesador ¹ y su texto carece de claridad, al igual que el libro al que se refiere. Aquí hay algunas citas de TAMPP:

Cita 1 (Definición de sin bloqueo)

Un método no tiene bloqueo si garantiza que, con frecuencia infinita, algunas llamadas de método finalizan en un número finito de pasos.

Cita 2 (Definición de no bloqueo)

nunca se requiere una invocación pendiente de un método total para esperar a que se complete otra invocación pendiente.

Cita 3 (afirme que sin bloqueo no se bloquea)

Las condiciones de progreso sin bloqueo sin espera y sin bloqueo garantizan que el cómputo en su conjunto avance, independientemente de cómo el sistema programe los subprocesos.

El problema es que el reclamo en la Cita 3 obviamente no se deriva de la definición en la Cita 1. Como ya se mencionó, una cola sincronizada parece satisfacer la Cita 1: infinitamente a menudo algún método adquirirá el bloqueo y se completará con éxito.

Observe específicamente la frase bastante vaga en la Cita 3: "independientemente de cómo el sistema programa los hilos". Esto no está precedido por ningún tipo de descripción formal del "sistema de programación de subprocesos", por lo que nos queda reconstruir sus propiedades en función de nuestras ideas preconcebidas sobre lo que deberían significar las definiciones :

1. el sistema siempre ejecuta instrucciones de algún hilo;
2. nunca puede ejecutar instrucciones de ningún hilo dado ;
3. Todos los hilos están invocando el método en consideración.

En un sistema de este tipo, un método de bloqueo no puede estar libre de bloqueos: si el subproceso que mantiene el bloqueo nunca más se programa para la ejecución, no habrá otro subproceso que pueda completar la invocación de su método en un número finito de pasos, pero habrá algunos hilos que están ejecutando pasos del método. Para un sistema más realista, uno que garantice dar tiempo de CPU a cada hilo eventualmente, la definición debe incluir explícitamente la propiedad de no bloqueo:

Definición corregida de sin bloqueo

Un método no tiene bloqueo si no está bloqueado y, además, garantiza que, con frecuencia infinita, algunas llamadas de método finalicen en un número finito de pasos.

¹ Maurice Herlihy, Nir Shavit, El arte de la programación multiprocesador, Elsevier 2008, pp. 58-60

La terminología no siempre es coherente, pero creo que lo importante es hacer las siguientes preguntas sobre un algoritmo o sistema propuesto:

1. ¿Hay alguna secuencia de eventos en los que los subprocesos podrían quedarse atascados esperándose el uno al otro, incluso si todos los subprocesos tuvieran todo el tiempo de CPU que podrían usar [si es así, no está libre de punto muerto]
2. Si un hilo se bloqueó durante un largo tiempo arbitrario, ¿podría detener otros hilos o perjudicar la operación del sistema durante un tiempo arbitrariamente largo [si es así, no es sin bloqueo].
3. ¿Existe alguna combinación de programación de hilos al menos teóricamente posible que podría hacer que todos los hilos vuelvan a intentar repetidamente las mismas operaciones mientras se invalida el trabajo de los demás, sin que nadie avance [si es así, no está libre de bloqueo]
4. Si a algunos subprocesos se les da suficiente tiempo de CPU en relación con otro, ¿podrían forzar al último subproceso a volver a intentar sus operaciones indefinidamente [si es así, no está libre de espera].

Gran parte de la importancia de los algoritmos sin bloqueo no es que sean más rápidos que los algoritmos sin bloqueo, sino más bien el hecho de que no son propensos a morir si un hilo se desvía [tenga en cuenta que tal garantía simplemente requiere que los algoritmos sean sin bloqueo, pero todos los algoritmos sin bloqueo lo son]. Es posible que un algoritmo sin bloqueo use bloqueos, pero solo si los intentos de adquisición de bloqueo incluyen tiempos de espera junto con algoritmos para garantizar que siempre sea posible que alguien progrese (por ejemplo, un algoritmo podría usar un CompareExchangeciclo como su principal método de arbitraje, pero use bloqueos para arbitrar el acceso cuando la contención parezca alta; si un bloqueo parece mantenerse durante demasiado tiempo, otros hilos podrían decidir abandonar los esfuerzos para usar ese bloqueo y, en su lugar, crear uno nuevo.CompareExchange, hacer que los clientes abandonen el bloqueo no pondría en peligro la consistencia del sistema, aunque puede significar que el código que había estado manteniendo el bloqueo anterior no se realizará ningún trabajo hasta que también abandone el bloqueo antiguo y se alinee con el nuevo.

Debe mirar la "definición" que cita en contexto :

La forma tradicional de implementar estructuras de datos compartidos es utilizar la exclusión mutua (bloqueos) para garantizar que las operaciones concurrentes no interfieran entre sí. El bloqueo tiene una serie de desventajas con respecto a la ingeniería del software, la tolerancia a fallas y la escalabilidad (ver [8]). En respuesta, los investigadores han investigado una variedad de técnicas alternativas de sincronización que no emplean la exclusión mutua . Una técnica de sincronización es sin esperas si asegura que cada hilo continuará progresando ante el retraso arbitrario (o incluso la falla) de otros hilos. No tiene bloqueo si solo garantiza que algún subproceso siempre progresa.

Estás utilizando bloqueos para la exclusión mutua, por lo que no están hablando de una técnica sin bloqueo.

Si uso bloqueos, ¿puede mi algoritmo seguir sin bloqueo?

Podría ser, pero depende del algoritmo.

Si tengo una estructura de datos simple, como una cola, protegida por un bloqueo, entonces un proceso siempre puede avanzar, ya que un proceso puede adquirir el bloqueo, hacer lo que quiera y liberarlo.

Entonces, ¿cumple con la definición de sin bloqueo?

Nota per se .

Si el paso "hacer lo que quiere" no implica la adquisición de otros bloqueos, y se garantiza que se completará en un tiempo finito, entonces esta parte particular de su algoritmo estará libre de puntos muertos.

Sin embargo, si esas condiciones previas no se cumplen, existe al menos la posibilidad de puntos muertos ...

El ejemplo que da no está libre de bloqueo por la siguiente razón.

La compatibilidad con un subproceso adquiere el bloqueo, y el programador del sistema operativo suspendió el subproceso durante un período solitario infinito, entonces todo el subproceso no puede avanzar porque ninguno puede adquirir el bloqueo adquirido por el subproceso suspendido.

En términos generales, los algoritmos que usan bloqueos no están libres de bloqueo.

Tenga en cuenta que sin bloqueo y sin bloqueo son dos conceptos diferentes. sin punto muerto significa que no hay posibilidad de punto muerto, pero podría haber un bloqueo en vivo que puede evitar que todo el sistema avance. La libertad de bloqueo es más fuerte que eso porque significa que algunos subprocesos en el sistema siempre avanzan con un número finito de pasos.