c# - threading - Cola de prioridad concurrente en.NET 4.0

thread programming c#

Question

Parece que hay muchas mejoras en .NET 4.0 relacionadas con la concurrencia que pueden depender de colas de prioridad concurrentes. ¿Existe una implementación de colas de prioridad decente dentro del marco disponible para su reutilización?

Answer 1

Bueno, pasaron 7 años, pero para la posteridad, me gustaría responder con mi implementación.

Documentación: Opcionalmente aguardable fácil de usar Cola de prioridad concurrente

Código fuente: github

paquete de nuget

• Libre de bloqueo,
• Altamente concurrente,
• genérico en el tipo de elemento almacenado,
• genérico en el tipo de prioridad, pero limitado a las prioridades representadas por la enumeración .net, prioridad fuertemente tipada,
• Se definió explícitamente el orden descendente de prioridades durante la construcción.
• capacidad para detectar el recuento de elementos y por número de elementos de prioridad,
• capacidad de encolar - orden descendente de prioridades,
• capacidad de anular el nivel de prioridad de salida,
• potencialmente aguardable,
• potencialmente prioritario basado en esperar,

Answer 2

Dado que todas las respuestas actuales están desactualizadas o no ofrecen una solución viable, existe una implementación en MSDN que es utilizable. Tenga en cuenta que las prioridades más bajas se procesan primero en esta implementación.

Answer 3

Hay una implementación como parte de "Ejemplos de programación paralela con .NET Framework" en msdn. Ver ParallelExtensionsExtras .

Enlace directo al código fuente para el archivo ConcurrentPriorityQueue.cs

Answer 4

Opciones:

1) Si su cola no va a volverse grande, use un montón y bloquee toda la estructura para cada inserción y eliminación.

2) Si su cola va a ser grande, podría usar un algoritmo como este:

http://www.research.ibm.com/people/m/michael/ipl-1996.pdf

Este algoritmo permite que varios subprocesos trabajen con la estructura del montón de forma simultánea sin correr el riesgo de daños o puntos muertos al admitir el bloqueo de grano fino de solo partes del árbol a la vez. Tendría que realizar pruebas comparativas para ver si la sobrecarga de las operaciones adicionales de bloqueo y desbloqueo cuesta más que la contención sobre el bloqueo de todo el montón.

3) Si pretende evitar los bloqueos por completo, otro algoritmo, mencionado en el enlace anterior, sugiere el uso de una cola de solicitudes FIFO (fácilmente implementable sin bloqueos), y un hilo separado que es lo único que toca el montón. Tendría que medir para ver cómo la sobrecarga de cambiar de enfoque entre subprocesos que utilizan objetos de sincronización en comparación con la sobrecarga de un simple bloqueo directo.

Antes de comenzar, valdría la pena ver qué tan malo es el impacto en una implementación sencilla utilizando el bloqueo. Puede que no sea la implementación más eficiente, pero si todavía realiza órdenes de magnitud más rápido de lo que nunca necesitará, entonces la facilidad de mantenimiento (es decir, cualquier persona, incluyéndose a sí mismo un año, puede simplemente mirar el código). y entienda lo que hace) puede superar la pequeña fracción del tiempo de CPU ocupado en el mecanismo de puesta en cola.

Espero que esto ayude :-)

Answer 5

Puede que tenga que rodar su propio. Una forma relativamente fácil sería tener una serie de colas regulares, con disminución de prioridad.

Básicamente, se insertaría en la cola para la prioridad apropiada. Luego, en el lado del consumidor, bajaría de la lista, de la prioridad más alta a la más baja, verificando si la cola no está vacía y consumiendo una entrada si es así.

Answer 6

Recientemente, estaba creando una máquina de estados en la que necesitaba eventos con marca de tiempo. En lugar de un simple tic del reloj, necesitaba eventos cronometrados con sus propias ID para poder distinguir un evento de otro.

La investigación de este problema me llevó a la idea de usar una cola de prioridad. Podría poner en cola los eventos programados junto con su información en cualquier orden; La cola de prioridad se encargaría de ordenar los eventos correctamente. Un temporizador verificará periódicamente la cola de prioridad para ver si es hora de que se dispare el evento en la cabecera de la cola. Si es así, elimina la cola del evento e invoca al delegado asociado con él. Este enfoque era exactamente lo que estaba buscando.

Buscando aquí en CodeProject

https://www.codeproject.com/Articles/13295/A-Priority-Queue-in-C

Encontré que ya se había escrito una clase de cola de prioridad [^]. Sin embargo, se me ocurrió que podría escribir mi propia cuenta usando a mi viejo amigo, la lista de saltos. Esto tendría la ventaja de que la operación de cola de espera solo tomaría O (1) tiempo, mientras que la operación en cola aún sería un registro (n) en promedio. Pensé que usar listas de salto de esta manera era lo suficientemente novedoso como para merecer su propio artículo.

Asi que aqui esta. Espero lo encuentres interesante.

Answer 7

Tal vez puedas usar mi propia implementación de un PriorityQueue. Implementa mucho más que lo usual push / pop / peek, características que implementé cada vez que encontré la necesidad de hacerlo. También tiene bloqueos para la concurrencia.

Los comentarios al código son muy apreciados :)

public class PriorityQueue<T> where T : class
{
    private readonly object lockObject = new object();
    private readonly SortedList<int, Queue<T>> list = new SortedList<int, Queue<T>>();

    public int Count
    {
        get
        {
            lock (this.lockObject)
            {
                return list.Sum(keyValuePair => keyValuePair.Value.Count);
            }
        }
    }

    public void Push(int priority, T item)
    {
        lock (this.lockObject)
        {
            if (!this.list.ContainsKey(priority))
                this.list.Add(priority, new Queue<T>());
            this.list[priority].Enqueue(item);
        }
    }
    public T Pop()
    {
        lock (this.lockObject)
        {
            if (this.list.Count > 0)
            {
                T obj = this.list.First().Value.Dequeue();
                if (this.list.First().Value.Count == 0)
                    this.list.Remove(this.list.First().Key);
                return obj;
            }
        }
        return null;
    }
    public T PopPriority(int priority)
    {
        lock (this.lockObject)
        {
            if (this.list.ContainsKey(priority))
            {
                T obj = this.list[priority].Dequeue();
                if (this.list[priority].Count == 0)
                    this.list.Remove(priority);
                return obj;
            }
        }
        return null;
    }
    public IEnumerable<T> PopAllPriority(int priority)
    {
        List<T> ret = new List<T>();
        lock(this.lockObject)
        {
            if (this.list.ContainsKey(priority))
            {
                while(this.list.ContainsKey(priority) && this.list[priority].Count > 0)
                    ret.Add(PopPriority(priority));
                return ret;
            }
        }
        return ret;
    }
    public T Peek()
    {
        lock (this.lockObject)
        {
            if (this.list.Count > 0)
                return this.list.First().Value.Peek();
        }
        return null;
    }
    public IEnumerable<T> PeekAll()
    {
        List<T> ret = new List<T>();
        lock (this.lockObject)
        {
            foreach (KeyValuePair<int, Queue<T>> keyValuePair in list)
                ret.AddRange(keyValuePair.Value.AsEnumerable());
        }
        return ret;
    }
    public IEnumerable<T> PopAll()
    {
        List<T> ret = new List<T>();
        lock (this.lockObject)
        {
            while (this.list.Count > 0)
                ret.Add(Pop());
        }
        return ret;
    }
}

Answer 8

Verifique las colecciones seguras para subprocesos en .NET Framework 4 y sus características de rendimiento, pero AFAIK no hay una cola de prioridad lista para usar. Todas las nuevas colecciones seguras para subprocesos no mantienen el orden, pero puedes crear las tuyas por encima de ellas. Compruebe @ manera de Steven.