Structure de données générique concurrente sans blocages ou sans ressources

J’ai récemment posé un certain nombre de questions concernant TVar , et j’ai toujours des préoccupations au sujet de livelock.

J’ai donc pensé à cette structure:

  1. Chaque transaction reçoit une priorité unique (peut-être atsortingbuée par ordre de création).
  2. Les transactions tentent d’obtenir des verrous en lecture / écriture sur les données auxquelles ils accèdent. Naturellement, les lectures simultanées sont correctes, mais un verrou en écriture exclut toutes les autres (à la fois en lecture et en écriture).
  3. Supposons que la transaction A ait une priorité supérieure à la transaction B. Si A détient le verrou, B attend, mais si B détient le verrou et A le souhaite, B est démarré depuis le verrou, A l’obtient et la transaction B redémarre (comme avec TVar ) . B conserve toutefois sa priorité actuelle pour la nouvelle tentative.
  4. Lorsqu’un verrou est libéré et qu’il y a des transactions en attente, il passe à la transaction la plus prioritaire et le rest continue d’attendre.

Je pense que ce système empêche les blocages, mais empêche également la famine (contrairement à TVar ). Je me demandais si quelqu’un avait mis en place un tel système, car cela semble assez évident et je ne veux pas réinventer la roue.

Bien entendu, une telle approche pourrait facilement être étendue pour permettre à l’utilisateur de spécifier des priorités.

La priorité peut être la paire (user_supplied_prio, auto_increment) , user_supplied_prio étant prioritaire, mais les tâches de priorité égales étant user_supplied_prio dans l’ordre FIFO.

Commentaire / solution:

En fait, quand j’y pense, ce que je décris existe déjà dans Haskell, simplement en utilisant un seul IORef entoure toutes les données et en utilisant uniquement atomicModifyIORef . atomicModifyIORef s’assurera que les transactions sont appliquées en séquence. Cependant, on peut penser que cela signifie que la structure de données est séquentielle (c.-à-d. Limitée à un seul thread), mais elle est en réalité parallèle à cause de la paresse.

Pour expliquer cela, considérez une fonction coûteuse f . Nous allons appliquer cela à un Data.Map aux données avec la clé “foo”.

Cela remplace (foo -> x) par (foo -> future(fx)) . Ce thread doit continuer à déterminer ce que (fx) est réellement, mais en attendant, nous pouvons appliquer g à “bar”. Comme appliquer g à “bar” ne nécessite pas le résultat de “foo”, nous pouvons travailler en même temps.

Aucune impasse, aucune famine, éventuellement toutes les transactions seront traitées (à peu près dans l’ordre de leur réception).

    Vous pouvez configurer un thread de travail pour traiter toutes les demandes de manière déterministe, afin que personne ne soit affamé. Cette stratégie serait raisonnablement efficace et insensible au livelock.

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

    IO a est une action qui interroge rapidement et en toute sécurité la valeur avec une action STM en lecture seule. (a -> a) est une fonction pure qui modifie la valeur, donc ((a -> a) -> IO a) est une action qui prend une fonction de modificateur, modifie la valeur en toute sécurité et renvoie la nouvelle valeur.

    Exécutez cette fois pour initialiser l’usine.

     (query, modifierFactory) <- createManagerVactory initValue 

    Ensuite, pour chaque thread, exécutez ceci pour générer un nouveau modificateur.

     myModify <- modifierFactory 

    createManagerFactory ferait ce qui suit:

    • Créez un TVar contenant initValue (appelez-le valueTVar).
    • Créez une TVar contenant une collection vide de TVar (Soit un (a -> a)) (appelez-le modifyTVarCollection)
    • retourne (atomiquement $ readTVar valueTVar) comme résultat de la requête
    • retourne un modifierFactory qui sait à propos de modifyTVarCollection

    modifierFactory ferait ceci:

    • Créez un nouveau TVar (Soit un (a -> a)) (appelez-le modificationsTVar), initialisez-le sur a (Left a) avec la valeur actuelle de valueTVar, et ajoutez-le à modifyTVarCollection
    • renvoyer une action de modificateur qui se charge (Right (a -> a)) dans modifyTVar dans une action STM, puis dans une autre action STM réessaye jusqu'à ce que modifyTVar contienne une valeur (Left a), puis retourne cette valeur.

    Le thread de travail exécutera cette boucle:

    • En une seule action, récupérez toutes les requêtes TVars de modifyTVarCollection et vérifiez leurs valeurs. S'ils contiennent tous des valeurs (Left a), réessayez (cela bloquerait jusqu'à ce qu'un autre thread charge leur modifyTVar avec une fonction de modificateur, ou le modifyFactory crée un nouveau programme modifierTVar et l'ajoute à la collection). Renvoie une liste de tous lesSTTV contenant un droit (a -> a)
    • Itérer sur tous les modifyTVars retournés. Pour chaque TVar, effectuez une action qui lit la fonction modificateur, effectue la modification en toute sécurité et remet le résultat dans le modifyTVar en tant que (Left a)