Comment montrer que le motif de verrouillage revérifié avec TryGetValue Dictionnaire ne threadsafe

https://stackoverflow.com/questions/2624301

26-09-2019
|

Question

Récemment, je l'ai vu quelques projets C # qui utilisent un modèle de verrouillage double contrôle sur un Dictionary. Quelque chose comme ceci:

private static readonly object _lock = new object();
private static volatile IDictionary<string, object> _cache = 
    new Dictionary<string, object>();

public static object Create(string key)
{
    object val;
    if (!_cache.TryGetValue(key, out val))
    {
        lock (_lock)
        {
            if (!_cache.TryGetValue(key, out val))
            {
                val = new object(); // factory construction based on key here.
                _cache.Add(key, val);
            }
        }
    }
    return val;
}

Ce code est incorrect, puisque le Dictionary peut être « croissance » dans la collection _cache.Add() en _cache.TryGetValue (en dehors de la serrure) est itérer sur la collection. Il pourrait être extrêmement improbable dans de nombreuses situations, mais il est toujours mauvais.

Y at-il un programme simple pour démontrer que ce code échoue?

Est-il judicieux d'incorporer cela dans un test unitaire? Et si oui, comment?

La solution

Dans cet exemple, exception # 1 est jeté presque instantanément sur ma machine:

var dict = new Dictionary<int, string>() { { 1234, "OK" } };

new Thread(() =>
{
    for (; ; )
    {
        string s;
        if (!dict.TryGetValue(1234, out s))
        {
            throw new Exception();  // #1
        }
        else if (s != "OK")
        {
            throw new Exception();  // #2
        }
    }
}).Start();

Thread.Sleep(1000);
Random r = new Random();
for (; ; )
{
    int k;
    do { k = r.Next(); } while (k == 1234);
    Debug.Assert(k != 1234);
    dict[k] = "FAIL";
}

Cependant, le comportement exact de code qui est pas conçu pour être thread-safe est imprévisible .
Vous ne peut pas compter sur elle . Ainsi, le code de double contrôle est en effet cassé.

Je ne sais pas si je serais test unitaire ce, bien que, comme le test du code concurrent (et de le faire à droite) est beaucoup plus compliqué que d'écrire le code concurrent en premier lieu.

Autres conseils

Il est clair que le code est threadsafe. Ce que nous avons ici est un cas évident des risques d'optimisation prématurée.

Rappelez-vous, le but du motif de verrouillage revérifié est améliorer les performances de code en éliminant le coût de la serrure. Si le verrou est incontesté, il est incroyablement pas cher déjà. Par conséquent, le motif de verrouillage double contrôle ne se justifie que dans les cas (1) où le verrou va être fortement contestée, ou (2) où le code est si très performances sensibles que le coût d'une serrure unconstested est encore trop élevé.

Il est clair que nous ne sommes pas dans le second cas. Vous utilisez un dictionnaire pour l'amour du ciel. Même sans la serrure, il va faire des comparaisons et des recherches qui seront des centaines ou des milliers de fois plus cher que les économies d'éviter un blocage incontesté.

Si nous sommes dans le premier cas, alors figure ce qui cause l'affirmation et à éliminer que . Si vous faites beaucoup d'attente autour d'un verrou puis comprendre pourquoi ce qui est et remplacer le verrouillage avec un lecteur-graveur-lock ou de restructurer l'application mince de telle sorte que pas tant de fils tapent sur le même verrou à la temps.

Dans les deux cas, il n'y a aucune raison de faire des techniques à faible verrouillage dangereuses, sensibles à la mise en œuvre. Vous devriez être seulement en utilisant des techniques à faible blocage dans les cas extrêmement rares où vous avez vraiment, vraiment ne peut pas prendre le coût d'un blocage incontesté.

Je ne pense pas vraiment que vous besoin pour le prouver, il vous suffit de diriger les gens vers la page documentation Dictionary<TKey, TValue> :

Un dictionnaire peut prendre en charge simultanément plusieurs lecteurs, tant que la collection ne soit pas modifiée. Même si, l'énumération d'une collection est intrinsèquement pas une procédure thread-safe. dans les rares cas où une énumération soutient avec accès en écriture, la collection doit être verrouillé pendant l'énumération entière. Pour permettre la collecte d'accéder par plusieurs threads pour la lecture et l'écriture, vous devez implémenter votre propre synchronisation.

Il est en fait un fait bien connu (ou devrait être) que vous ne pouvez pas lire à partir d'un dictionnaire, tandis qu'un autre thread est en train d'écrire à elle. Je l'ai vu quelques sortes de questions « question de multi-threading » bizarre ici sur le SO, où il est apparu que l'auteur n'a pas réalisé que ce n'était pas sûr.

Le problème est pas lié spécifiquement à verrouillage double contrôle, il est juste que le dictionnaire n'est pas une classe de thread-safe, pas même pour un seul auteur / scénario unique lecteur.

Je vais aller un peu plus loin et vous montrer pourquoi, dans le réflecteur, c'est thread-safe:

private int FindEntry(TKey key)
{
    // Snip a bunch of code
    for (int i = this.buckets[num % this.buckets.Length]; i >= 0;
        i = this.entries[i].next)
    // Snip a bunch more code
}

private void Resize()
{
    int prime = HashHelpers.GetPrime(this.count * 2);
    int[] numArray = new int[prime];
    // Snip a whole lot of code
    this.buckets = numArray;
}

Regardez ce qui peut arriver si la méthode de Resize arrive à être en cours d'exécution alors que même un lecteur appelle FindEntry:

Discussion A: Ajoute un élément, ce qui entraîne dans un resize dynamique;
Fil B: Calcule le seau offset (nombre de godets de code de hachage%);
Discussion A: Change les seaux pour avoir une taille différente (prime);
Discussion B: Choisit un indice d'élément de la nouveau array seau au vieux index seau;
Discussion pointeur de B n'est plus valide.

Et c'est exactement ce qui échoue dans l'exemple de DTB. Enfilez une recherche pour une clé qui est connu à l'avance pour être dans le dictionnaire, et pourtant il ne se trouve pas. Pourquoi? Parce que la méthode de FindValue choisi ce qu'il pensait être le seau correct, mais avant même d'avoir eu la chance de l'intérieur du regard, fil B changé les seaux, et maintenant le thread A est à la recherche dans certains seau totalement aléatoire qui ne contient pas ou même conduire à la droit d'entrée.

Morale de l'histoire: TryGetValue n'est pas une opération atomique, et Dictionary<TKey, TValue> est pas une classe de thread-safe. Ce n'est pas écrit simplement concomitantes dont vous avez besoin à vous soucier; vous ne pouvez pas avoir en même temps en lecture écrit non plus.

En réalité, le problème est en fait beaucoup plus profond que cela, en raison de l'instruction réordonnancement par la gigue et la CPU, les caches obsolètes, etc. - il n'y a aucune barrière de mémoire soit utilisés ici - mais cela devrait prouver au delà d'une doute qu'il ya une condition de course évidente si vous avez un appel de Add en cours d'exécution en même temps que l'invocation de TryGetValue.

La raison pour laquelle je pense que cette question revient encore et encore:

Pre-2.0, Avant Generics (BG), Hashtable était le conteneur associatif primaire dans .NET, qui fournit en effet des garanties de filetage. De MSDN :
   "Hashtable est thread-safe pour une utilisation par plusieurs threads de lecture et un seul thread d'écriture. Il est thread-safe pour une utilisation multi-thread lorsque seulement l'un des threads effectuent des opérations d'écriture (mise à jour), ce qui permet Reads sans verrouillage fourni que les écrivains sont sérialisés à la Hashtable. "

Avant que quelqu'un obtient très excité, il y a des limites.
  Voir par exemple ce message de Brad Abrams , qui possède Hashtable.
  Un peu d'histoire plus historique sur Hashtable se trouve ici (... à la fin: "Après cette longue diversion - Qu'en est-Hashtable?")
.

Pourquoi Dictionary<TKey, TValue> échoue dans le cas ci-dessus:

Pour prouver qu'il échoue, il suffit de trouver un exemple, donc je vais essayer cela.
  Un Redimensionner arrive que la table se développe.
  Le redimensionnement, une nouvelle mouture arrive et on voit ce que les deux dernières lignes:

this.buckets = newBuckets;
//One of the problems here.
this.entries = newEntries;

Le tableau buckets contient les index dans le tableau de entries.   Disons que nous avons 10 entrées jusqu'à présent et maintenant nous ajoutons une nouvelle.
  Allons plus faire semblant par souci de simplicité que nous ne l'avons pas et ne se collisions.
  Dans l'ancien buckets, nous avons eu des indices en cours d'exécution de 0 à 9 -. Si nous avions pas de collision
  Maintenant, les index dans la nouvelle série de tableau de buckets de 0 à 10 (!).
  Nous changeons maintenant le champ buckets privé pour pointer vers les nouveaux seaux.
  S'il y a un lecteur faisant TryGetValue() en ce moment, il utilise les nouveaux seaux pour obtenir l'index, mais utilise ensuite le nouveau index à lire dans le vieux array entrées, depuis le champ entries encore des points aux anciennes entrées.
  L'une des choses que l'on peut obtenir - en plus de faux lit - est un IndexOutOfRangeException convivial
.   Un autre « grand » façon d'y arriver est en @ explication Aaronaught. (... et les deux peuvent se produire, par exemple, comme dans exemple de DTB).

Ceci est vraiment un exemple, Dictonary n'a pas été conçu et n'a jamais voulu être thread-safe. Il a été conçu pour être rapide, mais - cela signifie que le verrou ne sera pas tenu longtemps.

Y compris le code dans la question, vous pouvez le tester avec le code suivant.

//using System.Collections.Generic;
//using System.Threading;

private static volatile int numRunning = 2;
private static volatile int spinLock = 0;

static void Main(string[] args)
{
    new Thread(TryWrite).Start();
    new Thread(TryWrite).Start();
}

static void TryWrite()
{
    while(true) 
    {
        for (int i = 0; i < 1000000; i++ )
        {
            Create(i.ToString());
        }

        Interlocked.Decrement(ref numRunning);
        while (numRunning > 0) { } // make sure every thread has passed the previous line before proceeding (call this barrier 1)

        while (Interlocked.CompareExchange(ref spinLock, 1, 0) != 0){Thread.Sleep(0);} // Aquire lock (spin lock)
        // only one thread can be here at a time...

        if (numRunning == 0) // only the first thread to get here executes this...
        {
            numRunning = 2; // resets barrier 1
            // since the other thread is beyond the barrier, but is waiting on the spin lock,
            //  nobody is accessing the cache, so we can clear it...
            _cache = new Dictionary<string, object>(); // clear the cache... 
        }

        spinLock = 0; // release lock...
    }

}

Ce programme essaie juste de se Create pour traverser la collection comme il est « cultivé ». Il doit être exécuté sur une machine avec au moins deux noyaux (ou deux processeurs), et échouera probablement après un certain temps à cette exception.

System.Collections.Generic.Dictionary`2.FindEntry(TKey key)

L'ajout de ce test est difficile car il est un test probabiliste, et vous ne savez pas combien de temps il faudra à l'échec (si jamais). Je suppose que vous pourriez choisir une valeur comme 10 secondes et le laisser fonctionner pendant longtemps. Si elle ne manque pas dans ce laps de temps, le test passe. Pas le meilleur, mais quelque chose. Vous devez également vérifier que Environment.ProcessorCount > 1 avant d'exécuter le test, sinon la probabilité qu'il n'est minuscule.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow