Structure de données générique concurrente sans impasse ou ressource insuffisante

Question

J'ai récemment demandé à un certain nombre de questions concernant l' TVar, et j'ai toujours des inquiétudes à propos absence de cycle non productif.

Alors j'ai pensé à cette structure:

1. Chaque transaction obtient un unique priorité (peut-être alloués dans l'ordre de création).
2. Les opérations de tenter d'obtenir de lecture/écriture des verrous sur les données qu'ils ont accès. Naturellement, lectures simultanées sont d'accord, mais un verrou en écriture exclut tous les autres (à la fois en lecture et en écriture).
3. Dire Une transaction a priorité plus élevée que les transactions B. Si Une détient le verrou, B attend, mais si B détient le verrou et Un le veut, B est démarré à partir de la serrure, Un obtient, et l'opération B redémarre (comme avec TVar). B toutefois conserve sa priorité actuelle pour la nouvelle tentative.
4. Lorsqu'un verrou est libéré et il y a des transactions en attente, il va à la priorité la plus élevée de la transaction, et le reste à continuer à attendre.

Ce système je crois empêche les blocages, mais aussi de prévenir la famine (contrairement à TVar). Je me demandais si quelqu'un a mis en place un tel système, car il me semble assez évident, et je ne veux pas réinventer la roue.

Bien sûr, une telle approche pourrait facilement être étendue pour permettre à l'utilisateur de définir les priorités.

La priorité pourrait être la paire (user_supplied_prio, auto_increment), avec user_supplied_prio qui prend le pas, mais l'égalité de priorité des tâches de résolution 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 IORef enroulé autour de toutes les données, et en utilisant seulement atomicModifyIORef. L' atomicModifyIORef permettra de s'assurer que les transactions sont appliqués dans l'ordre. Cependant, on peut penser que cela signifie que la structure de données est séquentielle (c'est à dire effectivement limité à un seul thread) mais c'est en réalité parallèle en raison à la paresse.

Pour expliquer cela, prenons une fonction coûteuse f. Nous allons l'appliquer à un Data.Map pour les données avec la clé "foo".

Cela remplace (foo -> x) avec (foo -> future(f x)). Ce fil doit continuer à travailler sur ce (f x) est en fait, mais en attendant, nous pouvons appliquer g de "bar". Depuis l'application g de "bar" n'a pas besoin de la suite de "foo", nous pouvons faire ce travail en même temps.

Pas de blocages, pas de famine, finalement, toutes les transactions seront traitées (à peu près dans l'ordre où ils sont reçus).

Answer 1

Vous pouvez mettre en place un thread pour traiter toutes les demandes de manière déterministe, donc personne n'est mort de faim. Cette stratégie devrait être raisonnablement efficace immunitaire et à l'absence de cycle non productif.

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

IO une action en toute sécurité et rapidement les requêtes de la valeur en lecture seule de la STM à l'action. (a -> a) est une pure fonction qui modifie la valeur de ((a -> a) -> IO a) est une action qui prend un modificateur de fonction, en toute sécurité modifie la valeur, et renvoie la nouvelle valeur.

Exécuter une fois pour initialiser l'usine.

(query, modifierFactory) <- createManagerVactory initValue

Ensuite, pour chaque thread, exécutez la commande suivante pour générer un nouveau modificateur.

myModify <- modifierFactory

createManagerFactory s'effectuer les opérations suivantes:

• Créer un TVar contenant initValue (appeler valueTVar).
• Créer un TVar contenant vide de collecte de TVar (Soit un (une -> a)) (appelons le modifyTVarCollection)
• retour (atomiquement $ readTVar valueTVar) comme les "interroger" le résultat
• de retour d'un modifierFactory qui connaît bien le modifyTVarCollection

modifierFactory pourrait faire ceci:

• Créer un nouveau TVar (Soit a (a -> a)) (appel il modifyTVar), initialiser une (de Gauche a) avec la valeur actuelle de la valueTVar, et l'ajouter à modifyTVarCollection
• de retour d'un modificateur d'action que les charges (Droite (a -> a)) dans le modifyTVar dans un STM action, puis dans une autre STM action tentatives jusqu'à ce que le modifyTVar contient une (de Gauche a) la valeur du résultat, puis renvoyer cette valeur.

Le thread de travail permettrait de courir cette boucle:

• Dans une action, saisir toutes les requêtes TVars de la modifyTVarCollection, et de vérifier leurs valeurs. Si ils contiennent tous (à Gauche a) valeurs, retry (ce serait bloqué jusqu'à ce qu'un autre thread chargé de leur modifyTVar avec un modificateur de la fonction, ou la modifierFactory créé un nouveau modifierTVar et de l'ajouter à la collection). Une liste de tous les modifyTVars contenant une Droite (a -> a)
• Parcourir toutes les retournés modifyTVars. Pour chaque TVar, effectuer une action qui lit la touche de fonction, en toute sécurité effectuer la modification, et met le résultat dans la modifyTVar comme un (Laissé)