Créer une file d'attente de blocage <T> dans .NET?

163

J'ai un scénario où j'ai plusieurs threads s'ajoutant à une file d'attente et plusieurs threads lisant à partir de la même file d'attente. Si la file d'attente atteint une taille spécifique, tous les threads qui remplissent la file d'attente seront bloqués lors de l'ajout jusqu'à ce qu'un élément soit supprimé de la file d'attente.

La solution ci-dessous est celle que j'utilise actuellement et ma question est la suivante: comment cela peut-il être amélioré? Y a-t-il un objet qui active déjà ce comportement dans la BCL que je devrais utiliser?

internal class BlockingCollection<T> : CollectionBase, IEnumerable
{
    //todo: might be worth changing this into a proper QUEUE

    private AutoResetEvent _FullEvent = new AutoResetEvent(false);

    internal T this[int i]
    {
        get { return (T) List[i]; }
    }

    private int _MaxSize;
    internal int MaxSize
    {
        get { return _MaxSize; }
        set
        {
            _MaxSize = value;
            checkSize();
        }
    }

    internal BlockingCollection(int maxSize)
    {
        MaxSize = maxSize;
    }

    internal void Add(T item)
    {
        Trace.WriteLine(string.Format("BlockingCollection add waiting: {0}", Thread.CurrentThread.ManagedThreadId));

        _FullEvent.WaitOne();

        List.Add(item);

        Trace.WriteLine(string.Format("BlockingCollection item added: {0}", Thread.CurrentThread.ManagedThreadId));

        checkSize();
    }

    internal void Remove(T item)
    {
        lock (List)
        {
            List.Remove(item);
        }

        Trace.WriteLine(string.Format("BlockingCollection item removed: {0}", Thread.CurrentThread.ManagedThreadId));
    }

    protected override void OnRemoveComplete(int index, object value)
    {
        checkSize();
        base.OnRemoveComplete(index, value);
    }

    internal new IEnumerator GetEnumerator()
    {
        return List.GetEnumerator();
    }

    private void checkSize()
    {
        if (Count < MaxSize)
        {
            Trace.WriteLine(string.Format("BlockingCollection FullEvent set: {0}", Thread.CurrentThread.ManagedThreadId));
            _FullEvent.Set();
        }
        else
        {
            Trace.WriteLine(string.Format("BlockingCollection FullEvent reset: {0}", Thread.CurrentThread.ManagedThreadId));
            _FullEvent.Reset();
        }
    }
}
Eric Schoonover
la source
5
.Net comment a des classes intégrées pour vous aider dans ce scénario. La plupart des réponses énumérées ici sont obsolètes. Voir les réponses les plus récentes en bas. Examinez les collections de blocage thread-safe. Les réponses sont peut-être obsolètes, mais c'est toujours une bonne question!
Tom A
Je pense que c'est toujours une bonne idée de se renseigner sur Monitor.Wait / Pulse / PulseAll même si nous avons de nouvelles classes simultanées dans .NET.
thewpfguy
1
D'accord avec @thewpfguy. Vous voudrez comprendre les mécanismes de verrouillage de base dans les coulisses. Il convient également de noter que Systems.Collections.Concurrent n'existait qu'en avril 2010, puis uniquement dans Visual Studio 2010 et supérieur. Certainement pas une option pour les hold-outs VS2008 ...
Vic
Si vous lisez ceci maintenant, jetez un œil à System.Threading.Channels pour une implémentation multi-écrivains / multi-lecteurs, limitée, bloquant facultativement de ceci pour .NET Core et .NET Standard.
Mark Rendle

Réponses:

200

Cela semble très dangereux (très peu de synchronisation); que diriez-vous de quelque chose comme:

class SizeQueue<T>
{
    private readonly Queue<T> queue = new Queue<T>();
    private readonly int maxSize;
    public SizeQueue(int maxSize) { this.maxSize = maxSize; }

    public void Enqueue(T item)
    {
        lock (queue)
        {
            while (queue.Count >= maxSize)
            {
                Monitor.Wait(queue);
            }
            queue.Enqueue(item);
            if (queue.Count == 1)
            {
                // wake up any blocked dequeue
                Monitor.PulseAll(queue);
            }
        }
    }
    public T Dequeue()
    {
        lock (queue)
        {
            while (queue.Count == 0)
            {
                Monitor.Wait(queue);
            }
            T item = queue.Dequeue();
            if (queue.Count == maxSize - 1)
            {
                // wake up any blocked enqueue
                Monitor.PulseAll(queue);
            }
            return item;
        }
    }
}

(Éditer)

En réalité, vous voudriez un moyen de fermer la file d'attente pour que les lecteurs commencent à sortir proprement - peut-être quelque chose comme un indicateur booléen - s'il est défini, une file d'attente vide revient simplement (plutôt que de bloquer):

bool closing;
public void Close()
{
    lock(queue)
    {
        closing = true;
        Monitor.PulseAll(queue);
    }
}
public bool TryDequeue(out T value)
{
    lock (queue)
    {
        while (queue.Count == 0)
        {
            if (closing)
            {
                value = default(T);
                return false;
            }
            Monitor.Wait(queue);
        }
        value = queue.Dequeue();
        if (queue.Count == maxSize - 1)
        {
            // wake up any blocked enqueue
            Monitor.PulseAll(queue);
        }
        return true;
    }
}
Marc Gravell
la source
1
Que diriez-vous de changer l'attente en WaitAny et de passer dans un waithandle de fin sur la construction ...
Sam Saffron
1
@ Marc - une optimisation, si vous vous attendiez à ce que la file d'attente atteigne toujours sa capacité, serait de passer la valeur maxSize dans le constructeur de la file d'attente <T>. Vous pouvez ajouter un autre constructeur à votre classe pour s'adapter à cela.
RichardOD
3
Pourquoi SizeQueue, pourquoi pas FixedSizeQueue?
mindless.panda
4
@Lasse - il libère le (s) verrou (s) pendant Wait, afin que d'autres threads puissent l'acquérir. Il récupère le (s) verrou (s) lorsqu'il se réveille.
Marc Gravell
1
Bien, comme je l'ai dit, il y avait quelque chose que je n'obtenais pas :) Cela me donne certainement envie de revoir une partie de mon thread-code ....
Lasse V. Karlsen
14

"Comment ça pourrait être amélioré?"

Eh bien, vous devez examiner chaque méthode de votre classe et considérer ce qui se passerait si un autre thread appelait simultanément cette méthode ou toute autre méthode. Par exemple, vous placez un verrou dans la méthode Remove, mais pas dans la méthode Add. Que se passe-t-il si un thread s'ajoute en même temps qu'un autre thread est supprimé? Mauvaises choses.

Considérez également qu'une méthode peut renvoyer un deuxième objet qui fournit l'accès aux données internes du premier objet - par exemple, GetEnumerator. Imaginez qu'un thread passe par cet énumérateur, un autre thread modifie la liste en même temps. Pas bon.

Une bonne règle de base est de simplifier la tâche en réduisant au minimum le nombre de méthodes de la classe.

En particulier, n'héritez pas d'une autre classe de conteneur, car vous exposerez toutes les méthodes de cette classe, ce qui permettra à l'appelant de corrompre les données internes ou de voir les modifications partiellement complètes des données (tout aussi mauvaises, car les données semble corrompu à ce moment). Cachez tous les détails et soyez totalement impitoyable sur la façon dont vous autorisez l'accès à eux.

Je vous conseille fortement d'utiliser des solutions prêtes à l'emploi - obtenir un livre sur le filetage ou utiliser une bibliothèque tierce. Sinon, compte tenu de ce que vous essayez, vous allez déboguer votre code pendant une longue période.

De plus, ne serait-il pas plus logique que Remove renvoie un élément (par exemple, celui qui a été ajouté en premier, car il s'agit d'une file d'attente), plutôt que l'appelant choisissant un élément spécifique? Et lorsque la file d'attente est vide, Remove devrait également se bloquer.

Mise à jour: la réponse de Marc met en œuvre toutes ces suggestions! :) Mais je vais laisser ceci ici car il peut être utile de comprendre pourquoi sa version est une telle amélioration.

Daniel Earwicker
la source
12

Vous pouvez utiliser BlockingCollection et ConcurrentQueue dans l'espace de noms System.Collections.Concurrent

 public class ProducerConsumerQueue<T> : BlockingCollection<T>
{
    /// <summary>
    /// Initializes a new instance of the ProducerConsumerQueue, Use Add and TryAdd for Enqueue and TryEnqueue and Take and TryTake for Dequeue and TryDequeue functionality
    /// </summary>
    public ProducerConsumerQueue()  
        : base(new ConcurrentQueue<T>())
    {
    }

  /// <summary>
  /// Initializes a new instance of the ProducerConsumerQueue, Use Add and TryAdd for Enqueue and TryEnqueue and Take and TryTake for Dequeue and TryDequeue functionality
  /// </summary>
  /// <param name="maxSize"></param>
    public ProducerConsumerQueue(int maxSize)
        : base(new ConcurrentQueue<T>(), maxSize)
    {
    }



}
Andreas
la source
3
BlockingCollection est défini par défaut sur Queue. Donc, je ne pense pas que ce soit nécessaire.
Curtis White
BlockingCollection conserve-t-il l'ordre comme une file d'attente?
joelc
Oui, lorsqu'il est initialisé avec un ConcurrentQueue
Andreas
6

Je viens de faire tomber ceci en utilisant les extensions réactives et je me suis souvenu de cette question:

public class BlockingQueue<T>
{
    private readonly Subject<T> _queue;
    private readonly IEnumerator<T> _enumerator;
    private readonly object _sync = new object();

    public BlockingQueue()
    {
        _queue = new Subject<T>();
        _enumerator = _queue.GetEnumerator();
    }

    public void Enqueue(T item)
    {
        lock (_sync)
        {
            _queue.OnNext(item);
        }
    }

    public T Dequeue()
    {
        _enumerator.MoveNext();
        return _enumerator.Current;
    }
}

Pas nécessairement entièrement sûr, mais très simple.

Mark Rendle
la source
Qu'est-ce que le sujet <t>? Je n'ai pas de résolveur pour son espace de noms.
theJerm
Cela fait partie des extensions réactives.
Mark Rendle
Pas une réponse. Cela ne répond pas du tout à la question.
makhdumi
5

C'est ce que je suis venu opter pour une file d'attente de blocage bornée thread safe.

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

public class BlockingBuffer<T>
{
    private Object t_lock;
    private Semaphore sema_NotEmpty;
    private Semaphore sema_NotFull;
    private T[] buf;

    private int getFromIndex;
    private int putToIndex;
    private int size;
    private int numItems;

    public BlockingBuffer(int Capacity)
    {
        if (Capacity <= 0)
            throw new ArgumentOutOfRangeException("Capacity must be larger than 0");

        t_lock = new Object();
        buf = new T[Capacity];
        sema_NotEmpty = new Semaphore(0, Capacity);
        sema_NotFull = new Semaphore(Capacity, Capacity);
        getFromIndex = 0;
        putToIndex = 0;
        size = Capacity;
        numItems = 0;
    }

    public void put(T item)
    {
        sema_NotFull.WaitOne();
        lock (t_lock)
        {
            while (numItems == size)
            {
                Monitor.Pulse(t_lock);
                Monitor.Wait(t_lock);
            }

            buf[putToIndex++] = item;

            if (putToIndex == size)
                putToIndex = 0;

            numItems++;

            Monitor.Pulse(t_lock);

        }
        sema_NotEmpty.Release();


    }

    public T take()
    {
        T item;

        sema_NotEmpty.WaitOne();
        lock (t_lock)
        {

            while (numItems == 0)
            {
                Monitor.Pulse(t_lock);
                Monitor.Wait(t_lock);
            }

            item = buf[getFromIndex++];

            if (getFromIndex == size)
                getFromIndex = 0;

            numItems--;

            Monitor.Pulse(t_lock);

        }
        sema_NotFull.Release();

        return item;
    }
}
Kevin
la source
Pourriez-vous fournir des exemples de code sur la façon dont je mettrais en file d'attente certaines fonctions de thread à l'aide de cette bibliothèque, y compris la façon dont j'instancierais cette classe?
theJerm
Cette question / réponse est un peu datée. Vous devriez regarder l'espace de noms System.Collections.Concurrent pour bloquer la prise en charge de la file d'attente.
Kevin
2

Je n'ai pas complètement exploré le TPL, mais ils pourraient avoir quelque chose qui correspond à vos besoins, ou à tout le moins, du fourrage Reflector pour s'inspirer.

J'espère que cela pourra aider.

TheMissingLINQ
la source
Je sais que c'est vieux, mais mon commentaire s'adresse aux nouveaux venus dans SO, comme OP le sait déjà aujourd'hui. Ce n'est pas une réponse, cela aurait dû être un commentaire.
John Demetriou le
0

Eh bien, vous pourriez regarder la System.Threading.Semaphoreclasse. A part ça, non, vous devez le faire vous-même. AFAIK il n'y a pas de telle collection intégrée.

Vilx-
la source
J'ai regardé cela pour limiter le nombre de threads qui accèdent à une ressource, mais cela ne vous permet pas de bloquer tout accès à une ressource en fonction d'une condition (comme Collection.Count). AFAIK de toute façon
Eric Schoonover
Eh bien, vous faites cette partie vous-même, comme vous le faites maintenant. Simplement au lieu de MaxSize et _FullEvent, vous avez le sémaphore, que vous initialisez avec le bon nombre dans le constructeur. Ensuite, à chaque ajout / suppression, vous appelez WaitForOne () ou Release ().
Vilx-
Ce n'est pas très différent de ce que vous avez maintenant. Juste plus simple IMHO.
Vilx-
Pouvez-vous me donner un exemple montrant que cela fonctionne? Je n'ai pas vu comment ajuster dynamiquement la taille d'un sémaphore que ce scénario nécessite. Puisque vous ne devez pouvoir bloquer toutes les ressources que si la file d'attente est pleine.
Eric Schoonover le
Ahh, changer de taille! Pourquoi ne l'avez-vous pas dit immédiatement? OK, alors un sémaphore n'est pas pour vous. Bonne chance avec cette approche!
Vilx-
-1

Si vous voulez un débit maximal, permettant à plusieurs lecteurs de lire et à un seul écrivain d'écrire, BCL a quelque chose appelé ReaderWriterLockSlim qui devrait vous aider à réduire votre code ...

DavidN
la source
Je veux que personne ne puisse écrire si la file d'attente est pleine.
Eric Schoonover le
Alors vous le combinez avec une serrure. Voici quelques très bons exemples albahari.com/threading/part2.aspx#_ProducerConsumerQWaitHandle albahari.com/threading/part4.aspx
DavidN
3
Avec queue / dequeue, tout le monde est un écrivain ... un verrou exclusif sera peut-être plus pragmatique
Marc Gravell
Je sais que c'est vieux, mais mon commentaire s'adresse aux nouveaux venus dans SO, comme OP le sait déjà aujourd'hui. Ce n'est pas une réponse, cela aurait dû être un commentaire.
John Demetriou le