01 - Programación concurrente PDF

Preview

Summary

Download 01 - Programación concurrente PDF

Description

Programación Concurrente

Algoritmos Concurrentes y Paralelos

1. Introducción Cuando se habla de concurrencia se hace referencia a tareas, actividades o procesos que ocurren en un mismo momento de tiempo.

La concurrencia en sistemas de software hace referencia a los procesos del sistema que se ejecutan en forma simultánea y que, en algunos casos, pueden interactuar entre sí. Un sistema informático distribuido es la arquitectura de sistema que logra que un conjunto de computadoras, estaciones de trabajo y servidores se comporten como sistema informático único. En este tipo de entorno informático, los usuarios desconocen dónde se están ejecutando sus procesos, pero pueden utilizarlos desde cualquier punto del sistema sin ningún tipo de restricción. Los sistemas informáticos distribuidos y concurrentes han sido estudiados extensamente, lo que ha llevado a plantearse las dificultades por resolver y los beneficios de usar dichos sistemas. Los actuales avances en el procesamiento y la tecnología de redes y herramientas de software hacen factible lograr las siguientes ventajas:     

mayor rendimiento; compartir recursos; mayor extensibilidad; mayor confiabilidad, disponibilidad y tolerancia a fallas; rentabilidad.

Figura 1: Ejemplo de concurrencia en una base de datos

Fuente: elaboración propia.

El diseño de sistemas distribuidos es varios órdenes de magnitud más difícil que el diseño de sistemas centralizados. Implica tener en cuenta una gran cantidad de opciones y decisiones, como la configuración física del sistema, la red de comunicación y características de la plataforma informática,

2

programación de tareas y asignación de recursos políticas y mecanismos, control de consistencia, control de concurrencia y seguridad, por nombrar solo algunos. Deben considerarse dificultades como la falta de madurez en el campo de la computación distribuida y concurrente, el comportamiento asincrónico e independiente de los sistemas y el comportamiento relacionado con la dispersión geográfica. Hubo éxitos limitados en el diseño de sistemas distribuidos de propósito específicos como sistemas bancarios, sistemas de procesamientos de transacciones en línea y sistemas de punto de venta. Sin embargo, el diseño confiable de un sistema distribuido de propósito general, que reúna las ventajas de los sistemas centralizados (accesibilidad, gestión y coherencia) y los sistemas en red (intercambio, crecimiento, costo y autonomía), sigue siendo un desafío.

Al hablar de sistemas concurrentes no siempre implica hablar de sistemas paralelos. Pero hablar de sistemas paralelos siempre implica hablar de sistemas concurrentes.

Una de las técnicas que se puede utilizar para incrementar el rendimiento de los sistemas (secuenciales) es implementar el procesamiento paralelo. Existen implementadas arquitecturas de computadoras que proporcionan un auténtico procesamiento paralelo que justifican el interés actual en llevar a cabo investigaciones y desarrollar el procesamiento paralelo, el procesamiento concurrente, los sistemas distribuidos, los sistemas de tiempo real, etcétera. Dentro de estos estudios e investigaciones, una parte importante está dedicada a la mejora en el diseño de algoritmos paralelos y distribuidos, incluyendo el desarrollo de metodologías y modelos de programación paralela que ayuden a la programación de estos algoritmos (Dartheliber, 2013). Los sistemas concurrentes posibilitan que las operaciones pueden ser ejecutadas en un solo procesador, en múltiples procesadores en un solo equipo o en múltiples procesadores en equipos separados, físicamente o virtualmente, y, por supuesto, permitiendo distintos hilos de ejecución. Existen diversos modelos matemáticos para el cálculo de la concurrencia, como las redes de Petri, los procesos Calculi, el modelo máquina de accesos random en paralelo, o bien el modelo actor y el lenguaje reo (San Jose State University , s. f.).

La programación concurrente es la simultaneidad en la ejecución de múltiples tareas. Estas tareas pueden ser un conjunto de procesos o hilos de ejecución creados por un único programa. Las tareas se pueden ejecutar en un solo CPU (multiprogramación), en varios procesadores o en una red de computadores distribuidos. La programación concurrente está relacionada con la programación

3

paralela, pero enfatiza más la interacción entre tareas. Así, la correcta secuencia de interacciones o comunicaciones entre los procesos y los nodos los procesos coordinados de recursos que se comparten por tareas son las claves de esta disciplina. (“Procesos concurrentes”, s. f., https://bit.ly/2JKplKP).

Los procesos en un sistema concurrente pueden interactuar entre ellos mientras se están ejecutando en el mismo equipo o en múltiples equipos. Dado esto, el número de combinaciones posibles en su ejecución por sus estados tiende a ser extremadamente grande, lo que da como resultado final la posibilidad de ser indeterminado. Cuando el uso de recursos compartidos es concurrente, tiende a problemas de indeterminación dirigida a bloqueo mutuo e inanición (starvation) (“Sistemas distribuidos”, 2018). Cuando hablamos de desarrollar sistemas concurrentes, estamos hablando de implementar técnicas fiables para coordinar su ejecución, el intercambio de información, la asignación de memoria y su ejecución programada tendiente a minimizar la respuesta de tiempo y maximizar el rendimiento (“Administración de memoria”, s. f).

4

2. Características y evolución histórica Tom Kilburn y David Howarth fueron pioneros en el uso de interrupciones para simular ejecución simultánea (concurrencia) de varios programas en la computadora Atlas y esta técnica de programación se conoció como multiprogramación. Los primeros sistemas de multiprogramación fueron programados en lenguaje ensamblador, sin ningún fundamento ni marco conceptual. El menor error de programación podía hacer que estos sistemas se comporten de una manera completamente errática, haciendo que las pruebas de los programas fueran casi imposibles. A finales de la década de los 60, los sistemas operativos multiprogramados se habían convertido en algo tan grande y poco confiable que sus diseñadores hablaron abiertamente de una crisis de software. El concepto original de multitarea de [IBM OS / 360] preveía competencia sin restricciones de recursos para realizar una serie de tareas concurrentemente. De esta forma, a medida que el sistema evolucionó, se descubrieron muchos casos deadlock. A mediados de la década de 1960, los informáticos dieron los primeros pasos hacia una investigación más profunda de la programación concurrente. En menos de quince años, conceptos fundamentales fueron descubiertos y expresados mediante notación de programación, que más tarde fueron utilizados para construir lenguajes de programación, y estos usados para desarrollar sistemas operativos. Se introdujeron en las computadoras dispositivos controladores de entrada-salida independientes llamados canales, que eran programables. Los sistemas operativos se organizaron como una colección de procesos ejecutándose concurrentemente, o sea, al mismo tiempo, algunos en los canales y otros ejecutándose en el procesador principal. En ese momento, la programación de sistemas con capacidades de concurrencia se hacía a bajo nivel, en lenguaje ensamblador. Además de no disponerse de lenguajes de alto nivel con capacidades de concurrencia, se priorizaba la supuesta eficiencia del código escrito directamente en ensamblador. En 1972, Brinch Hansen desarrolló el lenguaje de alto nivel Concurrent Pascal y dio lugar a otros lenguajes de alto nivel para incorporar concurrencia. Desde ese momento, la programación concurrente ha ido ganando interés y actualmente se utiliza en la implementación de numerosos sistemas.

5

De alguna forma, el desarrollo de la programación concurrente fue motivado originalmente, por el deseo de desarrollar sistemas operativos fiables. Existen varios hitos que fortalecen el hecho de que la programación concurrente sea tan importante, a saber: 

El desarrollo del concepto de thread o hilo: esto les permite a los programas ejecutarse con mayor velocidad en comparación con los programas que utilizan el concepto de proceso (los hilos se distinguen de los procesos en el hecho de que estos son, por lo general, independientes, por lo que guardan información de estados e interactúan a través de mecanismos de comunicación del sistema; en cambio, los hilos, generalmente, comparten recursos de forma directa) (Historia de la programación concurrente, 2013).



La aparición y desarrollo de Internet: es conocida también como la red de redes. Esto nos conduce a pensar en sistemas distribuidos, lo que fomenta el desarrollo y la utilización de programas concurrentes.



La aparición y fácil disponibilidad de lenguajes orientados a objetos de propósito general, como JAVA, que brindan librerías para la programación concurrentes ha fortalecido el hecho de que aparezcan más personas capacitadas en este tipo de desarrollo y, a su vez, más interés en ello (Gamavi, 2008).

Fueron pioneros en este campo: Edsger Wybe Dijkstra, Per Brinch Hansen y Charles Antony Richard. 

Edsger Wybe Dijkstra fue un científico de la computación de origen holandés. Sus principales contribuciones fueron el algoritmo para encontrar en un grafo la ruta más corta (SPF), conocido como algoritmo Dijkstra, y usado actualmente como base para el protocolo de enrutamiento open shortest path first (OSPF). También el concepto de deadlock, o abrazo mortal, y su solución mediante semáforos y regiones de código con acceso exclusivo. Este aporte fue la base de la programación concurrente y parte fundamental de cualquier sistema operativo. También es conocido por promover la verificación formal de programas y la eliminación de la sentencia GOTO, entre otros tantos aportes.

6

Figura 2: Edsger Dijkstra

Fuente: Richards, 2002, https://goo.gl/skAVx3



Per Brinch Hansen fue un informático danés-estadounidense, pionero de la programación concurrente y reconocido arquitecto de los sistemas operativos. En la década de los 60 fue arquitecto de la minicomputadora 4000 RC, donde estableció el concepto de Kernel del sistema operativo. En los 70 desarrolló el primer lenguaje de programación concurrente: Pascal concurrente. Sus principales trabajos se volcaron en dos libros: Operating System Principles (Principios de los sistemas operativos) y The Architecture of Concurrent Programs (La arquitectura de los programas concurrentes).

Figura 3: Per Brinch Hansen

Fuente: [Imagen sin título sobre Brinch Hansen]. (1959). Recuperada de https://goo.gl/wcZasD



Charles Antony Richard Hoare, también conocido como Tony Hoare, es un científico en computación de origen británico. Recibió el premio Turing en 1980, fue nombrado miembro de la Royal Society en 1982 y sir por la reina británica en 2000. Actualmente, es investigador principal en el Microsoft Research Center de Cambridge. Entre sus aportes se

7

encuentran el algoritmo quicksort, el algoritmo de ordenación más ampliamente usado en el mundo, cuyo origen se debió a la necesidad de ordenar una lista de palabras como en un diccionario y para lo cual se basó en la técnica “divide y vencerás”, a partir del cual convirtió un problema complejo en muchos más simples. En su artículo de 1969, “An axiomatic basis for computer programming”, se enuncian unas leyes lógicas que permiten comprender el significado de los programas, independientemente de las máquinas que los ejecutan. Esta lógica (lógica Hoare, en su honor) proporcionó las reglas matemáticas de inferencia para razonar sobre la corrección de programas imperativos. Hoare también desarrolló el lenguaje formal CSP (communicating sequential processes), que es un lenguaje formal para describir patrones de interacción en sistemas concurrentes. También sirve de base para la definición del lenguaje de programación Occam.

Figura 4: Charles Antony Richard Hoare

Fuente: Monniaux, 2005, https://goo.gl/xtfg5N

8

3. Herramientas de desarrollo concurrente En la programación concurrente, los lenguajes suelen usar diferentes herramientas para el desarrollo del entorno de programación: 

Interfaces de programación de aplicaciones (API, por su siglas en inglés application programming interface): se trata de un conjunto de librerías añadidas a un lenguaje específico (en principio, sin soporte concurrente). Estas librerías dan el soporte necesario al lenguaje para la implementación de diferentes paradigmas de programación.



Middleware: es una capa software distribuida, que se sitúa sobre el sistema operativo (de red) y antes de la capa de aplicación; de esta forma, abstrae la heterogeneidad del entorno. Esta capa se integra para simplificar la tarea de programación y gestión de las aplicaciones distribuidas. Proporciona una serie de servicios de valor añadido, como servicios de nombres, transacciones, etcétera, como mecanismos para facilitar el desarrollo de aplicaciones distribuidas. Su desafío principal es la integración de aplicaciones y servicios, promoviendo la interoperabilidad cuando se ejecutan en plataformas heterogéneas (por ejemplo, CORBA, DCOM, RMI, SOAP, etc.) (Jorba Esteve y Suppi, 2008).



Lenguajes específicos: existen lenguajes de programación que ayudan al desarrollo concurrente, proveyendo técnicas y librerías para soportar tareas concurrentes (p. ej. Ada y Occam) (Jorba Esteve y Suppi, 2008).

9

4. Aplicaciones concurrentes. Ventajas e inconvenientes Al momento de desarrollar aplicaciones concurrentes, es necesario tener en cuenta algunos aspectos como sus ventajas e inconvenientes. Existen ejemplos de aplicaciones, tanto reales como académicas, que también pueden ilustrar algunas de las dificultades que se encuentran durante el desarrollo de una aplicación concurrente.

4.1. Ventajas

Programar concurrentemente permite que nuestros sistemas sean fácilmente escalables, ya que, por un lado, nos permite modularidad y, por el otro, nos ayuda a que sean mucho más eficientes debido a la posibilidad de ejecución en paralelo de múltiples instrucciones.



Velocidad de ejecución: el hecho de disponer de múltiples actividades dentro de la aplicación permite que esta pueda concluir su trabajo de manera más rápida.



Escalabilidad: un sistema es considerado escalable cuando es capaz de administrar en forma adecuada las cargas de trabajo crecientes o cuando tiene la capacidad para crecer para adaptarse a tales cargas. En las aplicaciones concurrentes se pueden utilizar ambas descripciones combinando la distribución y replicación de componentes.



Gestión de las comunicaciones: el uso eficiente de los recursos permite que aquellos relacionados con la comunicación entre actividades sean explotados de forma sencilla en una aplicación concurrente. Si la comunicación está basada en el intercambio de mensajes a través de la red, esta comunicación no implicará que toda la aplicación se detenga esperando alguna respuesta. El uso de mecanismos sincrónicos de comunicación entre actividades se puede integrar de manera natural en una aplicación concurrente.



Flexibilidad: las aplicaciones concurrentes utilizan un diseño modular y estructurado, en el que se pone atención a qué es lo que debe hacer cada actividad, qué recursos requiere y qué módulos del programa necesitará ejecutar. Si los requisitos de la aplicación cambiaran, es relativamente sencillo identificar en qué módulos se deben realizar ajustes para incorporar esas variaciones en la especificación y a qué actividades implicarían.



Menor hueco semántico: un buen número de aplicaciones informáticas requieren el uso de varias actividades simultáneas. Si

10

estas aplicaciones se implantan como programas concurrentes, resulta más sencillo su diseño que si se intentara implantarlas como un solo programa secuencial.

4.2. Desventajas 

Programación delicada: durante el desarrollo de aplicaciones concurrentes se puede presentar lo que se conoce como “condición de carrera” o competencia. Ocurre cuando dos o más procesos acceden a un recurso compartido sin control, de manera que el resultado combinado de este acceso depende del orden de llegada. Esto puede generar inconsistencias imprevistas en el valor de las variables o atributos compartidos entre las actividades, cuando estas los modifiquen. Un segundo problema son los interbloqueos.



Depuración compleja: una aplicación concurrente, al estar compuesta por múltiples actividades, puede intercalar las sentencias que ejecuten cada una de sus actividades de diferentes maneras en cada ejecución. Por ello, aunque se proporcionen las mismas entradas a la aplicación, los resultados generados pueden ser diferentes en distintas ejecuciones. Si alguno de estos resultados fuese incorrecto, resultaría bastante difícil la reproducción de esa ejecución. Además, como para depurar cualquier aplicación informática, se suelen utilizar herramientas especializadas (diferentes tipos de depuradores). La propia gestión del depurador podría evitar que se diera la traza que provocó ese error.

11

5. Aplicaciones reales Dos aplicaciones claras de los algoritmos concurrentes son los propios sistemas operativos modernos, que realizan múltiples operaciones en forma concurrente, y el software de simulación científica, que es ejecutado en clusters computacionales (arquitectura paralela y distribuida).

En esta sección revisaremos ejemplos de aplicaciones concurrentes reales, que proporcionarán la base para comprender algunos de los aspectos que revisaremos posteriormente: 1) Servidor web Apache: Apache es un servidor web gratuito y de código abierto que emplea programación concurrente. El objetivo de un servidor web es la gestión de cierto conjunto de páginas web ubicadas en ese servidor. Dichas páginas resultan accesibles utilizando el protocolo HTTP (o hypertext transfer protocol). Los navegadores deben realizar peticiones a estos servidores para obtener el contenido de las páginas que muestran en sus ventanas. El trabajo de un servidor web es proveer a muchos usuarios diferentes y al mismo tiempo diferentes páginas. En este contexto, se vuelve interesante tener múltiples hilos de ejecución, permitiendo que cada uno de ellos atienda a un cliente distinto; de esta manera, habilita la paralelización de la gestión de múltiples clientes (Bustos, 2018). Para que la propia gestión de los hilos no genere un alto esfuerzo, Apache utiliza un conjunto de hilos (o thread pool) en espera, que, a su vez, son coordinados por un hilo adicional (una suerte de dispacher o coordinador) que atiende las peticiones que van llegando; de esta manera, asocia cada petición a los hilos del conjunto que queden disponibles. 2) Videojuegos: gran parte de los actuales videojuegos se construyen como aplicaciones concurrentes compuestas por múltiples hilos de ejecución. Se suele utilizar un motor de videojuegos que se encarga de proporcionar un soporte básico para la renderización, la detección de colisiones, el sonido, las animaciones, etcétera. Los motores permiten que múltiples hilos se encarguen de estas facetas. De esta forma, el rendimiento de los videojuegos puede aumentar en caso de disponer de un equipo, cuyo procesador disponga de múltiples núcleos. 3) Navegador web: cuando Google presentó su navegador Chrome en diciembre de 2008, su arquitectura era muy distinta a la del resto de navegadores web utilizados en ese momento (Microsoft Internet Explorer, Mozilla Firefox, Opera, etc.). En Chrome, cada pestaña abierta está soportada por un proceso independiente. De este modo, si alguna de las pestañas falla, el resto de ellas puede s...