Blog de Miguel Llopis

System.Collections.Concurrent: Estructuras de datos para computación paralela en .Net 4.0

Una de las principales novedades introducidas en .net 4.0 y Visual Studio 2010 es la inclusión de mecanismos para la resolución de problemas de computación paralela. Este soporte se ha incorporado de muy diversas formas a nuestro querido framework, mediante la adición de nuevas instrucciones con capacidades de multiprocesamiento tales como los bucles paralelos (Parallel.Foreach, etc), operadores de consultas LINQ paralelos (PLINQ), invocaciones paralelas (Parallel_Invoke), encadenamiento de operaciones (Continuations), entre otras…

Tradicionalmente, los problemas fundamentales de la Programación Concurrente han sido la implementación de mecanismos efectivos para la comunicación y sincronización. Por una parte, perseguimos el objetivo de la compartición de información entre procesos (por ejemplo, el uso de los resultados de un proceso como valores de entrada para el otro), y por otra parte, buscamos que dicha comunicación a nivel de datos sea sincronizada (de modo que un proceso “espere” datos tan sólo en el momento adecuado, cuando estos estén disponibles, ya que de lo contrario se producirían situaciones como la espera ocupada (implementada habitualmente del modo: while(true) { TryToRead(buffer); }, que degradarían el rendimiento de nuestro programa).

Estas situaciones se han tratado de resolver mediante el uso de memoria compartida entre los distintos agentes/procesos/hilos de nuestra aplicación concurrente (escoged alguna de esas tres palabras dependiendo del nivel de granularidad de nuestro paralelismo, o del patrón de concurrencia que vayamos a emplear). Para controlar el acceso a esta memoria compartida, se han implementado mecanismos cuya función principal consiste en aislar en nuestro código aquellas instrucciones que acceden a esta memoria compartida, bien sea para modificarla o simplemente consultar su contenido (a estos conjuntos de instrucciones en nuestro código se les suele conocer también con el nombre de secciones críticas). Dentro de estos mecanismos de control para el acceso a la sección crítica, podemos encontrar diversas aproximaciones, como los semáforos, monitores o procedimientos para el paso de mensajes (que a su vez pueden ser de tipo bloqueante o no bloqueante).

El uso de estos mecanismos básicos ha sido a menudo una dificultad añadida a la tarea del programador, que ha sumado una complejidad excesiva al proceso de abstracción del problema concurrente y su implementación posterior.

Un enfoque alternativo a este problema consiste en el uso de abstracciones que nos proporcionen una implementación de estos mecanismos de control de acceso a las zonas de memoria compartida de forma totalmente transparente al desarrollador. De este modo, resultará más sencillo centrarse en la resolución del problema concreto que le ocupa, y abstraer los mecanismos de control de operaciones básicas de memoria sobre las cuales deberá apoyarse para alcanzar su solución pero que, por otra parte, resultan comunes a cualquier problema de tipo concurrente.

Es sobre este último grupo, estructuras de datos para computación paralela, sobre el que me gustaría hablaros en este post: las nuevas estructuras de datos con soporte para concurrencia introducidas en el .Net framework 4.0, concretamente en el namespace: System.Collections.Concurrent

Dentro de este espacio de nombres, podremos encontrar las siguientes estructuras de datos:

  • BlockingCollection<T>: Se trata de una estructura que nos proporciona acceso a una colección de elementos. El acceso a esta colección se puede bloquear/desbloquear y también es posible acotar su capacidad.
  • ConcurrentBag<T>: Colección no ordenada de objetos.
  • ConcurrentDictionary<TKey, Value>: Colección de tuplas key-value a la que se puede acceder concurrentemente.
  • OrderablePartitioner(TSource): Permite configurar la forma en que prentendemos dividir los datos procedentes de un determinado origen en un conjunto de particiones. Idealmente, es la colección inicial a emplear ante problemas del tipo “divide y vencerás”
  • Partitioner(TSource): Similar al anterior, pero en esta ocasión dispondremos de una serie de métodos de particionado predefinidos, que podremos aplicar sobre arrays, listas y otros objetos enumerables.

Seguidamente, mostraremos un ejemplo del uso de estas estructuras de datos en un problema clásico de la Programación Concurrente: el problema del productor-consumidor.

Solución al problema del Productor-Consumidor empleando BlockingCollection<T>

Resumiendo a grandes rasgos este problema, trataremos de resolver una situación en la que dos tipos de procesos diferentes se comunican a través de un buffer de forma concurrente. Mientras uno de los dos procesos (el productor) escribe bloques de información en dicho buffer a medida que dispone de ellos, el otro (consumidor) se encarga de leerlos.

Existen diferentes variantes del problema: cambiando el número de productores o de consumidores presentes, modificando las características del buffer de forma que éste pueda tener un tamaño limitado o infinito, o también alterando la persistencia de los contenidos del buffer (por ejemplo, si un bloque de datos es borrado del buffer tras haber sido leído por un consumidor).

Vamos a ver cómo implementar algunos de estos patrones concurrentes mediante el uso de BlockingCollection<T>, proporcionada por el espacio de nombres de .Net 4.0: System.Collections.Concurrent, tal cual comentábamos antes.

1) Productor-Consumidor (1:1) con buffer ilimitado e información no persistente:

En este caso, crearemos dos nuevas tareas Producer y Consumer, haciendo uso del objeto Task (Task.Factory.StartNew). El Producer generará valores aleatorios que escribirá en el buffer mediante el uso del método Add() del mismo. Será necesario realizar una llamada al método CompleteAdding() para indicar que la actual operación de escritura sobre el buffer se ha completado.

Por su parte, el consumidor leerá los elementos presentes en el buffer iterando sobre el mismo. El método GetConsumingEnumerable() nos permite obtener nuestra BlockingCollection<int> como IEnumerable<int>. Por último, el consumidor se quedará a la espera de nuevos valores añadidos al buffer por parte del productor (consumer.Wait()).

 

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;
using System.Threading;
 
namespace ProducerConsumer
{
    class Program
    {
        static void Main(string[] args)
        {
            BlockingCollection<int> buffer = new BlockingCollection<int>();
 
            var producer = Task.Factory.StartNew(() =>
                {
                    Random rand = new Random();
                    for (int i = 0; i < 3; i++)
                    {
                        Thread.Sleep(1000);
                        int item = rand.Next();
                        buffer.Add(item);
                        Console.WriteLine("Productor escribe {0} , item);
                                            en el buffer"
                    }
                    buffer.CompleteAdding();                    
                });
 
            var consumer = Task.Factory.StartNew(() =>
            {
                foreach (var item in buffer.GetConsumingEnumerable())
                {
                    Console.WriteLine("Consumidor lee {0} , item);
                                            del buffer"
                }
            });
 
            consumer.Wait();
            Console.ReadLine();
        }
    }
}

El resultado podemos verlo a continuación, el productor genera tres valores aleatorios y los escribe en el buffer, mientras que el lector leerá cada uno de ellos del buffer y los muestra.

image

2) Productor-Consumidor (1:1) con buffer ilimitado e información persistente:

En este segundo escenario, las restricciones del problema serán las mismas que en el caso anterior, con la única diferencia de que la información escrita en el buffer no será eliminada después de que el consumidor la haya utilizado.

Para ello, tan sólo deberemos cambiar una línea en el código mostrado anteriormente, en lugar de acceder en el consumidor al buffer mediante el metódo buffer.GetConsumingEnumerable() accederemos de la siguiente forma: foreach(var item in buffer)

3) Productores – Consumidores (N:N) con buffer ilimitado e información no persistente.

En este caso, la única diferencia con respecto a los escenarios anteriores es que deberemos “envolver” la creación del productor y del consumidor en sendos bucles, para generar el número deseado de productores y de consumidores.

4) Productores-Consumidores (N:N) con buffer limitado e información no persistente.

 

La última variante que veremos hoy sobre el problema del Productor-Consumidor es la relacionada con la limitación del tamaño de nuestro buffer. En este caso, limitaremos el número de elementos de nuestra BlockingCollection<int>.

Para ello, únicamente deberemos emplear una de las sobrecargas del constructor de esta clase, indicando el número de elementos tope de la colección:

BlockingCollection<int> buffer = new BlockingCollection<int>(3);
 
De este modo, hemos limitado a 3 el número de elementos que nuestra colección puede contener. Por tanto, si el productor desea escribir en este buffer y el número de elementos ha alcanzado el máximo, el propio productor se bloqueará, dejando paso al consumidor para que consuma un valor, y posteriormente retomando el control sobre el buffer para escribir el valor que tenía preparado.
 
La elección de un tamaño apropiado para nuestro buffer, así como el uso de una cadencia de lectura/escritura (número de items afectados por cada operación de acceso al buffer) serán dos decisiones importantes a tomar en este caso. Teniendo en cuenta que, generalmente, las situaciones de bloqueo tienen un efecto positivo y otro negativo. En el lado positivo de la balanza, un bloqueo supone una resolución a un conflicto coherente con la lógica de nuestra solución, pero por otra parte, supone cierta degradación en el rendimiento de nuestra aplicación concurrente.
 
Happy Coding!
Posted: 31/10/2009 10:05 por Miguel LLopis | con 4 comment(s) |
Comparte este post:

Comentarios

José Miguel Torres ha opinado:

Muy bueno chaval!! Me parece un tema interesantísimo del que vamos a tener que remangarnos las mangas y ponernos a ello en breve y mas con las posibilidades de .NET FX 4.0.

Excelente ;-)

# October 31, 2009 9:49 PM

Juan Irigoyen ha opinado:

Excelente artículo Miguel, que envidia me das...

Un saludo.

# November 4, 2009 10:24 PM