Haskell: ¿Cómo funciona TVar?

Question

¿Cómo funciona TVar? Por lo que he leído, intenta ejecutar todas las transacciones inmediatamente después de recibirlas, sin embargo, una transacción completada invalida otras transacciones que se están ejecutando actualmente, que luego deben reiniciarse. ¿Es así como funciona TVar?

Si este fuera el caso, si hubiera transacciones de 1 ms de largo que ocurrieran cada 100 ms, ¿eso significaría que una transacción que tarda 200 ms en procesarse nunca se completaría?

Answer 1

Mientras dos transacciones accedan a TVars distinto, ambas pueden comprometerse simultáneamente sin invalidarse mutuamente.

Sólo para que quede claro cuando una transacción es invalidado, consideremos el siguiente escenario:

1. Supongamos que t :: TVar Int se inicializa a 0 y se lee a través de readTVar t al comienzo de una transacción A.
2. Mientras tanto, en otro hilo, se inicia la transacción B en la que se ejecuta writeTVar t 1. Supongamos que B confirma antes del A. El sistema STM comprobará si hay inconsistencias y concluirá que es seguro para B comprometerse en este punto, por lo que ahora writeTVar t 1 entra en vigencia.
3. Esto, sin embargo, hace que la transacción A se invalide dado que el valor anterior 0 de t se leyó al comienzo de A. (Si A se permitió a cometer, obtendríamos una violación de la atomicidad.)

El documento original [1] en el sistema STM de Haskell (ver Sección 6.5) responde a su pregunta:

"El hambre es posible. Por ejemplo, una transacción que se ejecuta durante puede entrar repetidamente en conflicto con transacciones más cortas. Creemos que es poco probable que se produzca la inanición en la práctica, pero no se puede decir sin más experiencia ".

[1] Tim Harris, Simon Marlow, Simon Peyton Jones y Maurice Herlihy. Conferencia de ACM sobre Principios y Práctica de Programación Paralela 2005 (PPoPP'05).

Answer 2

Si hubiera transacciones de 1 ms de largo que ocurrieran cada 100 ms, ¿eso significaría que una transacción que tarda 200 ms en procesarse nunca se completaría? Sólo

Transacciones conflicto si se tocan los mismos TVar s, por lo que si algunas de las transacciones 1ms evitarse todas las variables afectadas por las transacciones de 200 ms, 200 ms, entonces el uno sería capaz de completar. Además, dado que la mónada STM es bastante estricta sobre lo que está permitido en el interior (solo accesos de memoria y cálculos puros), es muy inusual tener tal disparidad entre la longitud de las transacciones; por lo general, serán solo algunas lecturas/escrituras de memoria largas, y todos los IO y otros cálculos se realizarán fuera de la transacción.Además, si una transacción en particular alguna vez queda bloqueada para siempre por otras transacciones es un problema de planificación; No estoy 100% seguro de cómo se ve el planificador actual de GHC, pero parece plausible que dé preferencia a las transacciones más antiguas (o mayores tasas de fallas).

Dicho esto, Livelock es un problema muy real con STM, y es tan insidioso y tan difícil de razonar como un punto muerto en las implementaciones de concurrencia de bloqueo más tradicionales.

¿Cómo funciona TVar?

Probablemente disfrutará de this paper.