Programación concurrente & C++11(Parte 1: Conceptos generales).

Los procesadores diseñados en la actualidad conciben el uso de múltiples núcleos en un solo chip, están presentes en la mayoría de los dispositivos como smartphones, tablets, laptops, PCs, videoconsolas y muchos otros dispositivos, realmente se han abaratado mucho los costos de estos productos al punto que hoy se han vuelto soluciones de propósito general reemplazando el diseño original de un solo núcleo y teniendo los fabricantes en la mira los procesadores multinucleo que se han vuelto los nuevos reyes del mercado, esta competencia ha puesto en manos del usuario final más poder de computo que nunca antes. La arquitectura multinucleo es el diseño que pone múltiples procesadores en un solo encapsulado o chip, cada procesador es llamado core o núcleo, este diseño es conocido como CMP(Chip Multiprocessors), aunque también se conocen por CMP los procesadores hyperthreaded, que son chips con un solo núcleo que permiten la ejecución de dos o más tareas ejecutándose en un mismo procesador debido a que tienen algunas partes de su hardware duplicadas lo que permite simular el procesador como si tuviese varios núcleos pero en realidad es un solo procesador capaz de ejecutar varios hilos al mismo tiempo, en lo que nos interesa en este post, desarrollo de software, entenderemos por CMP a procesadores capaces de ejecutar varias tareas al mismo tiempo independientemente de la estructura interna del hardware. El principal problema de esto es que el software tradicional que se diseñaba para ejecutarse de forma secuencial y debe ser rediseñado para explotar al máximo estas nuevas capacidades del hardware. Para entender mejor esto, delineemos algunos conceptos que son necesarios dominar.

Programa:

Este es un conjunto de instrucciones detallando tareas a ejecutar sobre datos o recursos de manera general, puede ser ejecutado por el CPU directamente para los lenguajes compilados como C, C++, GO entre otros o puede ser ejecutado por una máquina virtual o intérprete, lo más importante es que el programa es un producto del programador.
Proceso:

Un proceso es básicamente un programa en ejecución, los sistemas operativos(SO) actuales bien pueden tener varias instancias de programas ejecutándose o sea varios procesos que pueden llegar a cientos o miles. Un proceso tiene su propio espacio de direcciones, tiene una entrada en la tablade procesos, un estado, un identificador, se puede decir de manera general que un proceso es una asociación de recursos generados en el sistema e importante aclarar que a diferencia del programa que es producto del programador, el proceso es producto del SO.
Hilo software:
De acuerdo al estándar POSIX, un proceso debe tener un(o más de uno) control de flujo, cada flujo de ejecución de estos es lo que se conoce como “hilo software”, entre un “hilo software” y un proceso existen diferencias importantes a remarcar. Cada proceso contiene su propio espacio de direcciones mientras que los “hilos software” comparten todos el espacio de direcciones del proceso que los ha creado. A diferencia del proceso que puede ser visto como una asociación de recursos en el sistema el “hilo software” puede ser visto como un camino de ejecución de la lógica de proceso. En el “hilo software” las operaciones de cambio de contexto y comunicación suelen ser más eficientes dado que todos los “hilos software” de un proceso comparten el mismo espacio de direcciones.
Hilo hardware:
La medida de la cantidad de tareas independientes que el hardware puede ejecutar realmente simultáneas.

Paralelismo:

Un sistema se dice que es paralelo si puede soportar dos o más “hilos software” de ejecución simultáneamente, o sea si el número de “hilos hardware” es mayor que uno.

Concurrencia:

Un sistema se dice que es concurrente si puede soportar dos o más “hilos software” en progreso al mismo tiempo. 

El concepto clave y la diferencia entre las definiciones de paralelismo y concurrencia es la frase "en progreso". Una aplicación concurrente tendrá dos o más “hilos software” en curso en algún momento. Esto puede significar que la aplicación tiene dos o más “hilos software” que están siendo intercambiadas por el sistema operativo en un procesador de solo un “hilo hardware”, lo que los intercambia como “en ejecución/suspendido” constantemente. En la ejecución en paralelo, debe haber varios “hilos hardware” disponibles en la plataforma de computación. En ese caso, los dos (o más) “hilos software” podrían ser asignados a cada “hilo hardware” separado y se ejecutarían simultáneamente. Entonces "paralelo" es un subconjunto de "concurrente". Es decir, se puede escribir una aplicación concurrente que utilice varios subprocesos o procesos, pero si usted no tiene varios “hilos hardware” disponibles, no será capaz de ejecutar su código en paralelo. Por lo tanto, la programación concurrente y concurrencia abarcan todas las actividades de programación y de ejecución que involucran a múltiples flujos de ejecución implementadas con el fin de resolver un solo problema.

En la Fig. 1 se muestra un ejemplo de un sistema con dos tareas a realizar(representadas con verde y rojo), cada una se divide en pequeñas porciones. En una maquina de dos “hilos hardware”, cada tarea se puede ejecutar en su propio “hilo hardware”. En una máquina de un solo “hilo hardware”, las tareas se intercambian constantemente, ejecutando una de las pequeñas porciones cada vez como se muestra en la Fig. 2, con el fin de hacer el cambio de tareas, el sistema tiene que realizar un cambio de contexto, y esto lleva tiempo, lo que se representa con el espaciado(en negro), ya que será un tiempo empleado por el SO y que no es la tarea final que nos interesa. Para llevar a cabo un cambio de contexto, el SO tiene que guardar el estado del CPU (incluido el puntero de instrucciones) de la tarea que esta ejecutando, seleccionar la tarea a ejecutar, volver a cargar el estado del CPU para la tarea que se va a cambiar, entre otras muchas cosas que causan demora.

Fig. 1

 

Fig. 2

 

Incluso con un sistema paralelo es común tener más tareas que “hilos hardware”, por lo que el cambio de tarea se usa incluso en estos casos. La Fig. 3 muestra la conmutación de tareas entre las cuatro tareas en una máquina de dos “hilos hardware”.

Fig. 3

 

Según lo que vimos las ventajas de la concurrencia parecen estar acotadas por “algo”, entonces: ¿cuándo debemos usarla y hasta que punto? Hay dos razones principales para utilizar la concurrencia en una aplicación: Separación de asuntos(separation of concerns) y rendimiento. Por lo general las demás razones son derivadas de estas.

El uso de concurrencia para la separación de asuntos.

Se puede utilizar la concurrencia para separar las distintas áreas de funcionalidad, incluso cuando las operaciones en estas áreas distintas deben ocurrir al mismo tiempo. Por ejemplo las aplicaciones de usuario deben hacer la tarea determinada para la que han sido creadas, pero además deben “escuchar” las ordenes del usuario mientras hacen dicha tarea, imagine por ejemplo un programa para grabar discos(tarea que demora) y mientras está grabando un disco en background nos permite ir preparando el próximo que grabaremos. En un solo hilo, la aplicación tiene que comprobar la entrada del usuario a intervalos regulares mientras se graba, fusionando así el código de grabación de disco con el código de interfaz de usuario. Si se usa concurrencia para separar estos asuntos, el código de interfaz de usuario y el de grabación ya no tiene por qué ser tan estrechamente entrelazados, y así estamos reduciendo el acoplamiento :). Un hilo puede manejar la interfaz de usuario y el otro la grabación, así que se necesita algún mecanismo de comunicación entre ellos para si el usuario decide por ejemplo cancelar la grabación en curso, esto da la ilusión de la capacidad de respuesta, porque el subproceso de interfaz le respondió de inmediato a una solicitud del usuario. En este caso, el número de “hilos software” es independiente del número de “hilos hardware” disponibles, porque la concurrencia se basa en el diseño conceptual en lugar de un intento de aumentar el rendimiento.

El uso de concurrencia para el rendimiento.

El aumento de la potencia de cálculo de las máquinas con varios “hilos hardware” no viene de correr una sola tarea más rápido, sino de la ejecución de múltiples tareas de forma concurrente. Antiguamente los programadores veían como la velocidad de ejecución de sus programas aumentaba por el simple hecho de salir nuevos procesadores al mercado, sin ningún esfuerzo de su parte pero ahora se nos han terminado las vacaciones ggg, si el software en verdad quiere tomar ventaja de las nuevas generaciones de procesadores que han salido, el software deberá ser capaz de ejecutar varias tareas de forma concurrente. En este sentido se conocen dos maneras principales de aumentar el rendimiento mediante concurrencia:

Concurrencia de tareas.

Concurrencia de datos.

El uso de concurrencia para el rendimiento es igual que cualquier otra estrategia de optimización: se tiene el potencial de mejorar en gran medida el rendimiento de la aplicación, pero también puede complicar el código, por lo que es más difícil de entender y más propenso a errores. Por lo tanto sólo vale la pena hacerlo para aquellas partes de rendimiento crítico de la aplicación donde está el potencial de ganancia medible.

Cuándo no utilizar la concurrencia.

Tan importante como saber cuándo y cómo usar la concurrencia es saber cuándo no utilizarla. Intuitivamente podríamos recomendar no usar la concurrencia cuando el beneficio no supera el costo. El código que implementa concurrencia es más difícil de entender en muchos casos, por lo que hay un costo intelectual directo a escribir y mantener código concurrente, y la complejidad adicional también puede dar lugar a más errores. A menos que la ganancia potencial de rendimiento sea lo suficientemente grande o la separación de asuntos lo suficientemente claras para justificar el tiempo de desarrollo adicional necesario para hacer las cosas bien y los costos adicionales asociados con el mantenimiento de código concurrente, no utilice la concurrencia. En algunas circunstancias, algunas soluciones de software y algoritmos son mejores implementarlos usando las técnicas de programación secuencial. En algunos casos, al introducir la sobrecarga del procesamiento paralelo puede afectar el rendimiento. La concurrencia tiene un costo. Si la cantidad de trabajo(cómputo) requeridos para resolver un problema secuencialmente en software es menor que la cantidad de trabajo requerida para crear nuevos hilos y/o procesos o menor que el trabajo requerido para coordinar la comunicación entre las tareas que se ejecutan de forma concurrente, entonces el enfoque secuencial es mejor. Entonces, la necesidad y/u oportunidad de la concurrencia es mayormente descubierta durante las tareas de descomposición, más adelante veremos sobre esto. Para nuestro propósito, descomposición es el proceso de dividir un proceso, un problema o una solución en sus partes fundamentales. Algunas veces las parte son agrupadas en áreas lógicas(que son, ordenamiento y búsqueda, cálculo, entrada-salida, y otras). En otras situaciones, las partes son agrupadas como recursos lógicos(procesador, base de datos, comunicación y otras más). Además, la ganancia de rendimiento podría no ser tan grande como se esperaba. Conclusión, no toda aplicación de software requiere del procesamiento concurrente y te insto a notar aquí que procesamiento concurrente no implica procesamiento paralelo como ya hemos estado viendo.

Existen diversos factores que afectan el rendimiento, veamos por ejemplo los del tipo “cuello de botella”:

La ley de Amdahl(incremento de velocidad ≤ 1 / [ƒ + (1 - ƒ) / p] = p / [1 + ƒ (p - 1)]; una pequeña fracción ƒ de procesamiento intrínsecamente secuencial o no paralelizable, limita severamente el incremento de velocidad que se puede lograr con los procesadores p). Una tarea de una unidad de tiempo, para la cual la fracción ƒ es no paralelizable (lo que tarda el mismo tiempo ƒ en ambas máquinas secuenciales y paralelas) y el restante 1 - ƒ es totalmente paralelizable [lo que se ejecuta en el tiempo (1 - ƒ) / p en una máquina de p procesadores], tiene una duración de ƒ + (1 - ƒ) / p en la máquina paralela.

La Fig.4 es la gráfica del incremento de velocidad en función del número de procesadores para diferentes valores de la fracción intrínsecamente secuencial ƒ. el incremento de velocidad no puede 

Fig. 4

 

exceder 1 / ƒ, no importa que tantos procesadores se usen. Así, por ƒ = 0,1, el incremento de velocidad tiene un límite superior de 10. Afortunadamente, existen aplicaciones para las que la sobrecarga secuencial es muy pequeña. Además, la sobrecarga secuencial no tiene por qué ser una fracción constante del trabajo independiente del tamaño del problema. De hecho, existen aplicaciones para las que la sobrecarga secuencial, disminuye como una fracción del trabajo computacional. Estrechamente relacionado con la ley de Amdahl es la observación de que algunas aplicaciones no tienen paralelismo inherente, lo que limita el incremento de velocidad que se puede lograr cuando se utilizan varios procesadores.

Fig. 5

 

La Fig. 5 muestra un gráfico de tareas que caracterizan un procesamiento. Cada uno de los nodos numerados en el gráfico es un procesamiento de unidad de tiempo y las flechas representan dependencias de datos o los requisitos previos de la ejecución en cada nodo. Un único procesador puede ejecutar las tareas del gráfico en 13 unidades de tiempo. Debido a que la ruta crítica del nodo de entrada del 1 al nodo de salida 13 pasa a través de 8 nodos, un procesador paralelo no lo puede hacer mucho mejor, ya que necesita al menos 8 unidades de tiempo para ejecutar el grafo de tareas. Por lo tanto, el plano de velocidad asociada con este gráfico particular nunca puede exceder de 1,625, no importa que tantos procesadores se usen.

Definamos las siguientes notaciones:

p: Número de procesadores.

W(p): Número total de operaciones hechas por los p procesadores; esto es también referido como trabajo computacional o energía.

T(p): Tiempo de ejecución con los p procesadores; claramente, T(1) = W(1) y T(p) <= W(p).

S(p): Incremento de velocidad = T(1)/T(p).

E(p): Eficiencia = T(1)/pT(p)

R(p): Redundancia = W(p)/W(1).

U(p): Utilización = W(p)/pT(p).

Q(p): Calidad = T³(1)/pT²(p)W(p).

A partir de esto se pueden establecer algunas relaciones:

1 ≤ S(p ) ≤ p

U(p) = R(p) * E(p)

E(p) = S(p)/p

Q(p) = E(p) * S(p)/R(p)

1/p <= E(p) <= U(p) <= 1

1 <= R(p) <= 1/E(p) <= p

Q(p) <= S(p) <= p

Ejemplo:

El cálculo de la suma de 16 números puede ser representado por un árbol binario(proceso de descomposición) con T(1) = W(1) = 15. Asumamos que las adiciones consumen una unidad de tiempo e ignoremos todo lo demás.

Con p = 8 procesadores, tenemos:

W(8) = 15                      T(8) = 4                                   E(8) = 15/(8 * 4) = 47%

S(8) = 15/4 = 3.75         R(8) = 15/15                           Q(8) = 1.76

En esencia, los 8 procesadores realizan todas las adiciones en el mismo nivel del árbol en cada unidad de tiempo, a partir de los nodos hoja y terminando en la raíz. La relativamente baja eficiencia es el resultado del paralelismo limitado cerca de la raíz del árbol. Ahora, suponiendo que las operaciones de adición que están alineadas verticalmente en la Fig. 6 son para ser realizadas por el mismo procesador y que cada transferencia entre procesadores que está representada por una flecha oblicua, también requiere una unidad de trabajo(tiempo), los resultados para p = 8 procesadores se convierten en:

W(8) = 22                       T(8) = 7                                   E(8) = 15/(8 × 7) = 27%

S(8) = 15/7 = 2.14          R(8) = 22/15 = 1.47                Q(8) = 0.39

La eficiencia en este último caso es menor incluso, primeramente porque las transferencias entre procesadores constituyen una sobrecarga en lugar de una operación útil.

Fig. 6

 

Además de los factores de tipo “cuello de botella”, se dice que la concurrencia “tiene un costo”, y se manifiesta principalmente cuando es concurrencia basada en paralelismo:

Hay una sobrecarga inherente asociado con el lanzamiento de un hilo, ya que el SO tiene que asignar los recursos del núcleo asociados y espacio de pila y luego añadir el nuevo hilo al planificador, todo lo cual lleva tiempo. Si la tarea a ejecutar en el hilo se completa rápidamente, el tiempo real tomada por la tarea puede ser eclipsado por la sobrecarga de lanzar el hilo, posiblemente haciendo que el rendimiento general de la aplicación peor que si la tarea tenía sido ejecutadas directamente por el hilo de devolución de resultado. Además, los hilos son un recurso limitado. Si usted tiene demasiados hilos de ejecución a la vez, estos consumen recursos del SO y puede hacer que el sistema en su conjunto tenga una ejecución más lenta. No sólo eso, sino que el uso de demasiados hilos puede agotar la memoria disponible o espacio de direcciones de un proceso, porque cada hilo requiere un espacio de pila separada. Esto es particularmente un problema para los procesadores de 32 bits con una arquitectura plana donde hay un límite de 4 GB de espacio de direcciones disponibles: si cada hilo tiene una pila de 1 MB (como es típico en muchos sistemas), entonces el espacio de direcciones sería todo utilizado con 4.096 hilos, sin permitir ningún espacio para datos estáticos o para el heap. Aunque los sistemas de 64-bit (o sistemas más grandes) no tienen este límite de espacio de direcciones directa, todavía tienen recursos finitos: si ejecutan demasiadas condiciones de competencia, que implican las secciones criticas; proteger variables, semáforos, …, este tiempo puede causar problemas.

Por último, mientras más hilos que se estén ejecutando, el sistema tiene que hacer más cambio de contexto de las operaciones. Cada cambio de contexto toma tiempo que podría ser usado haciendo un trabajo útil, por lo que en algún momento de la adición de un hilo adicional en realidad reducirá el rendimiento general de la aplicación en lugar de aumentarlo. Por esta razón, si usted está tratando de lograr el mejor rendimiento posible del sistema, es necesario ajustar el número de “hilos software” al número de “hilos hardware” disponibles.

En los posts que siguen veremos algunas técnicas para implementar la concurrencia de forma correcta, tendremos algún ejemplo de “tareas de descomposición”, concurrencia basada en paralelismo, concurrencia basada en tareas y programación funcional, sí, programación funcional en C++. Una de las múltiples ventajas que posee C++ como lenguaje de programación es el hecho de soportar múltiples paradigmas de desarrollo con un sencillez de implementación aceptable, a diferencia de Java por ejemplo que todo debe ser un objeto, C++ soporta programación orientada a objetos, programación genérica, programación imperativa o procedural, programación funcional, programación concurrente y otros.