Concurrente estructura de datos genéricos sin interbloqueos o falta de recursos

Question

Recientemente he hecho una serie de preguntas con respecto a TVar, y todavía me preocupan los bloqueos en directo.

Así que pensé en esta estructura:

1. Cada transacción obtiene una prioridad única (tal vez asignado el fin de la 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 contiene 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 interbloqueos, 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, este enfoque podría ampliarse fácilmente para permitir al usuario especificar las 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 pienso en ello, lo que describo ya existe en Haskell, simplemente mediante el uso de un IORef envuelto alrededor de todos los datos, y sólo utilizando 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 costosa función f. Vamos a aplicar esto a un Data.Map a los datos con la clave "foo".

Esto reemplaza (foo -> x) con (foo -> future(f x)). Este hilo continuará resolviendo lo que realmente es (f x), 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 serán procesadas (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.

Ejecute 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:

• Crear una TVAR contiene initValue (llámese valueTVar).
• Crear una TVAR que contiene una colección vacía de TVAR (ya sea un (a -> a)) (llamarlo el modifyTVarCollection)
• retorno (atómicamente $ readTVar valueTVar) como la 'consulta' resultado
• cambio una modifierFactory que sabe sobre el modifierFactory modifyTVarCollection

haría esto:

• Crear un nuevo TVAR (ya sea un (a -> a)) (llámese modifyTVar), inicializar a un (izquierda una) con el valor actual del valorTVar y agréguelo a modifyTVarCollection
• devuelve una acción modificadora que carga (Derecha (a -> a)) en el modifyTVar en una acción STM, luego en otra acción STM reintenta hasta que modifyTVar contenga a (resultado de la izquierda a), luego devuelva ese valor.

El subproceso de trabajo iría en este bucle:

• en una sola acción, agarrar todos los TVars de consulta de la modifyTVarCollection, y comprobar 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 TV modificados que contienen una derecha (a -> a)
• Iteramente 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 devuelva el resultado al modifyTVar como (a la izquierda)