haskell - Estructura de datos genéricos concurrente sin interbloqueos o falta de recursos

concurrency deadlock

Question

Hace poco hice una serie de preguntas sobre TVar , y todavía tengo dudas sobre el bloqueo en vivo.

Entonces pensé en esta estructura:

1. Cada transacción obtiene una prioridad única (tal vez asignada en orden de creación).
2. Las transacciones intentan obtener bloqueos de lectura / escritura en los datos a los que acceden. Naturalmente, las lecturas simultáneas están bien, pero un bloqueo de escritura excluye todos los demás (tanto de lectura como de escritura).
3. Digamos que la transacción A tiene mayor prioridad que la transacción B. Si A retiene el bloqueo, B espera, pero si B retiene el bloqueo y A lo quiere, B se inicia desde el bloqueo, A lo obtiene y la transacción B se reinicia (como con TVar ) . B sin embargo mantiene su prioridad actual para el reintento.
4. Cuando se libera un bloqueo y hay transacciones esperando, pasa a la transacción de mayor prioridad, y el resto continúa esperando.

Creo que este sistema evita los bloqueos, pero también previene la inanición (a diferencia de TVar ). Me preguntaba si alguien ha implementado un sistema así, ya que parece bastante obvio y no quiero reinventar la rueda.

Por supuesto, tal enfoque podría extenderse fácilmente para permitir al usuario especificar prioridades.

La prioridad podría ser el par (user_supplied_prio, auto_increment) , con user_supplied_prio teniendo prioridad, pero las tareas de igual prioridad se resuelven en orden FIFO.

Comentario / Solución:

En realidad, cuando lo pienso, lo que describo ya existe en Haskell, simplemente usando un IORef envuelto alrededor de todos los datos, y solo usando atomicModifyIORef . El atomicModifyIORef asegurará que las transacciones se apliquen en secuencia. Sin embargo, uno puede pensar que esto significa que la estructura de datos es secuencial (es decir, está efectivamente limitada a un hilo) pero en realidad es paralela debido a la pereza.

Para explicar esto, considere una función costosa f . Vamos a aplicar esto a un Data.Map a los datos con la clave "foo".

Esto reemplaza (foo -> x) con (foo -> future(fx)) . Este hilo continuará (fx) qué es (fx) realidad, pero mientras tanto podemos aplicar g a "bar". Como aplicar g a "bar" no necesita el resultado de "foo", podemos resolver esto al mismo tiempo.

Sin interbloqueos, sin inanición, eventualmente todas las transacciones se procesarán (más o menos en el orden en que se reciben).

Answer 1

Puede configurar un hilo de trabajo para procesar todas las solicitudes de forma determinista, para que nadie se muera de hambre. Esta estrategia sería razonablemente eficiente e inmune a Livelock.

-- yes, this is a horrible name
createManagerFactory :: a -> IO ((IO a), IO (((a -> a) -> IO a)))

IO a es una acción que consulta de forma segura y rápida el valor con una acción STM de solo lectura. (a -> a) es una función pura que modifica el valor, entonces ((a -> a) -> IO a) es una acción que toma una función modificadora, modifica el valor de manera segura y devuelve el nuevo valor.

Ejecuta esto una vez para inicializar la fábrica.

(query, modifierFactory) <- createManagerVactory initValue

Luego, para cada subproceso, ejecute esto para generar un nuevo modificador.

myModify <- modifierFactory

createManagerFactory haría lo siguiente:

• Crea un TVar que contenga initValue (llámalo valueTVar).
• Crea un TVar que contenga una colección vacía de TVar (O bien a (a -> a)) (llámalo modifyTVarCollection)
• return (atómicamente $ readTVar valueTVar) como resultado de la ''consulta''
• devuelve un modifierFactory que conoce acerca de modifyTVarCollection

modifierFactory haría esto:

• Cree un nuevo TVar (bien a (a -> a)) (llámalo modifyTVar), inícielo en a (Izquierda a) con el valor actual del valor TVar y agréguelo a modifyTVarCollection
• devuelve una acción modificadora que carga (Right (a -> a)) en el modifyTVar en una acción STM, luego en otra acción STM reintenta hasta que modifyTVar contenga un valor de resultado (Izquierda a), luego devuelve ese valor.

El hilo de trabajo ejecutaría este ciclo:

• En una acción, tome todas las consultas TVars de modifyTVarCollection y compruebe sus valores. Si todos contienen valores (de la izquierda a), vuelva a intentarlo (esto bloquearía hasta que otro subproceso cargue su modifyTVar con una función modificadora, o modifierFactory creó un nuevo modificadorTVar y lo agregó a la colección). Devuelve una lista de todos los modifyTVars que contienen un Derecho (a -> a)
• Iterato sobre todos los modifiedTVars devueltos. Para cada TVar, realice una acción que lea la función modificadora, realice la modificación de forma segura y vuelva a colocar el resultado en modifyTVar como (A la izquierda a)