motivación y recursos para la programación concurrente


Hoy hemos tenido el segundo seminario (la segunda sesión presencial) de la asignatura de programación concurrente. Entre ayer y hoy hemos dado los cuatro primeros temas del primer módulo dedicados a la motivación y los procesos y los threads y los recursos de la programación concurrente.

Motivación

En el primer tema hemos aprendido que la concurrencia se implementa mediante servicios estándar de sistemas operativos POSIX, mecanismos de librerías del lenguaje de programación o librerías de estándares de sistemas distribuidos. También sabemos ahora que existen objetos matemáticos formales (i.e métodos formales) que sirven para describir la concurrencia y analizar y diseñar sistemas concurrentes aunque de forma limitada como son las álgebras de procesos y las redes de Petri. Los sistemas reales que constan de muchos procesos concurrentes se suelen diseñar y analizar mediante técnicas de simulación.

La motivación de la programación concurrente surge por la necesidad de realizar aplicaciones de tiempo real, por la aparición del paradigma de programación orientada a objetos, por la naturaleza concurrente de los problemas reales que hay que resolver (sistemas operativos, GUIs, operaciones de entrada y salida, sistemas multimedia, control de sistemas físicos etc) y por la arquitectura hardware con muchos núcleos de computación distribuidos que deben ser aprovechados de forma eficiente.

Un programa se compone de sentencias y la línea de flujo de control (i.e thread) que establece el orden en el que se ejecutan las sentencias. Según el número de líneas de flujo de control y los requerimientos temporales un programa puede ser secuencial, concurrente o de tiempo real. Los programas concurrentes tienen varias líneas de flujo de control. Las sentencias no se ejecutan con un orden estricto, la secuencia de sentencias se suceden entre puntos de sincronización (con o sin intercambio de datos) La situación se puede describir como un conjunto de procesos que colaboran y/o compiten entre sí por los recursos de computación y comunicación. Todo esto dificulta enormemente la verificación de tales programas (en comparación un programa secuencial con un orden estricto de ejecución de sentencias en donde el tiempo de ejecución de cada sentencia no influye en el resultado la verificación es más sencilla)

La programación concurrente tiene un número de ventajas que hay que señalar. Para muchas aplicaciones se presenta como el modelo más simple y natural. Los objetos reales son concurrentes por lo que el diseño orientado al objeto se facilita enormemente. Hace posible compartir recursos en sistemas complejos, optimizando el uso de esos recursos en plataformas monoprocesadoras y reduciendo el tiempo de ejecución en plataformas multiprocesadoras. Facilita la programación en tiempo real, como tareas que se planifican en función de su urgencia. Y puesto que se pueden hace despliegues dinámicos (bajo demanda) en plataformas de ejecución, los programas se hacen más fiables.

Procesos y Threads

En el segundo tema hemos aprendido el concepto de proceso, su estructura, estados y gestión. Este concepto es central en la concurrencia. Una plataforma de ejecución concurrente está compuesta por una serie de procesos que conforman la lógica de la aplicación y que se ejecutan en una plataforma de ejecución compuesta por uno o más procesadores. Cada proceso tiene uno o más hilos de ejecución (i.e threads), cada uno de los cuales realiza una tarea secuencial. La concurrencia será real o simulada en función del número de procesadores. Los threads tendrán que intercambiar entre sí mensajes con información o de sincronismo ya que tendrán dependencias de datos o de control.

Los procesos pueden ser estáticos, determinados en tiempo de diseño y creados al inicio de la ejecución de la aplicación o dinámicos creados durante la ejecución del programa en función de los datos. El ciclo de vida de los procesos es un tarea costosa en tiempo de procesador. Los procesos pueden tener una estructura plana o ser jerárquicos (dependencia en forma de árbol) Existen varias estrategias de creación de procesos y múltiples causas para su terminación. Normalmente los procesos pasan por una serie de estados cuyo número depende del sistema en el que estén inscritos. El tránsito entre los diferentes estados es determinado por la necesidad de realizar operaciones de entrada y salida o sincronización y por el planificador de procesos con sus políticas de planificación.

interacción y problemas

En el tercer tema hemos visto en detalle los modelos de interacción entre procesos, los problemas que plantean la sincronización y la exclusión mutua y en el cuarto tema, las patologías de la programación concurrente.

Los procesos de una aplicación concurrente pueden ser independientes entre sí y competir por los recursos de computación (i.e el procesador), cooperar con dependencias de datos (uno genera información que otro necesita) o control (dos necesitan llegar al mismo punto al mismo tiempo) o competir por el uso de recursos que debe utilizar cada uno en régimen exclusivo (sin interferencias)

Si la aplicación se desarrolla con una metodología orientada a objetos puede haber tres tipos de objetos: activos (con thread propio), neutros (ofrecen servicios a los objetos activos y pueden ser usados de forma simultánea) o pasivos (prestan servicios a los objetos activos y arbitran el uso simultáneo cuando varios objetos activos intentan hacer uso simultáneo de sus servicios de acuerdo a una estrategia propia) Estos últimos representan los recursos de interacción.

Los objetos pasivos deben ser construidos a partir de componentes de sincronización pasivos (i.e semáforos, señales, zonas de exclusión mutua), definiendo primitivas de sincronización, que introducen cierta complejidad y posibilidad de errores (problemas básicos de la programación concurrente) a cambio de ser muy eficientes.

Los dos problemas básicos de la programación concurrente son la actualización concurrente de variables compartidas y la sincronización en la ejecución de tareas en las que la lógica de la aplicación requiere que un proceso no pueda ejecutar una sentencia hasta que otro proceso hay ejecutado una sentencia de la que depende.

El primer problema se presenta en un ejemplo en los apuntes consistente en una aplicación de control de un parque público. En este parque se dispone de varias puertas de acceso. Cada entrada tiene un torno (puerta giratoria) que tiene un proceso que envía un evento cada vez que entra una persona. Los procesos de los tornos de ejecutan de manera concurrente. Hay una variable global llamada cuenta en donde se almacenan las personas que han entrado. Los eventos de las puertas son tratados por procesos independientes que acceden a la variable global para incrementarla cada vez que reciben un evento. Para que este sistema funcione correctamente tiene que haber una exclusión mutua entre los procesos de manera que la operación de incremento se convierta en atómica (i.e mientras se realiza ningún otro proceso pueda tener acceso a la variable compartida)

Lo que hay que tener en cuenta es que el incremento de una variable no es una operación atómica, es decir, que esta formada por una serie de pasos que pueden ser interrumpidos. Los pasos en el caso de un incremento son la serie de instrucciones que tiene que ejecutar la CPU: cargar del valor de la variable global de la memoria a un registro (i.e el acumulador), incremento del aculmulador y escritura del valor del registro en memoria. Estas instrucciones básicas pueden entrelazarse en cualquier combinación en la operación simultánea de incremento que realizan los diversos procesos de cada puerta, dando origen al problema.

El segundo problema (sincronización) tiene su problema tipo en el llamado problema del productor-consumidor. Se tiene un proceso consumidor que produce un dato cada cierto tiempo y un proceso consumidor que consume un dato, que se comunican a través de un buffer de capacidad limitada a 1 dato. Aquí un proceso escribe en el buffer y otro lee. Pero además el que lee no debe realizar la operación de lectura antes de que el productor lo haya depositado. Esto quiere decir que tiene que haber una sincronización entre ambos.

La solución de la exclusión mutua de hace con un mecanismo llamado algoritmo de peterson, en el que se define una sección crítica de los procesos en la cual no pueden estar simultáneamente, con un protocolo de entrada y un protocolo de salida.

En los apuntes se proponen soluciones al problema de sincronización que implican el uso de mecanismos de espera activa en el que el consumidor realiza un bucle infinito hasta que el productor deposita el dato. Esto es ineficiente y no es aceptable.

Un comentario en “motivación y recursos para la programación concurrente

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s