Programa Concurrente

Programa Concurrente Concepto: Programa Concurrente es un programa que tiene mas de una linea lógica de ejecución, es decir, es un programa que parece que varias partes del mismo se ejecutan simultáneamente.

Programa Concurrente puede correr en varios procesadores simultáneamente o no. Esta importancia de la concurrencia es especialmente destacable en sistemas operativos como Linux, que además de concurrentes, presentan unos mecanismos de concurrencia estables.

Introducción

El concepto fundamental de la programación concurrente es la noción de proceso. El termino proceso fue utilizado por primera vez por los diseñadores del sistema Multics en los años 60’s. Desde entonces, el termino proceso, utilizado a veces como sinónimo de tarea, ha tenido muchas definiciones. A continuación se presentan algunas: Un programa en ejecución.

• Una actividad asíncrona
• El “espíritu animado” de un procedimiento
• El “centro de control” de un procedimiento en ejecución
• Lo que se manifiesta por la existencia de un “bloque de control del proceso” en el sistema operativo
• La entidad a la que se asignan los procesadores
• La unidad “despachable”

Aunque se han dado muchas otras definiciones, no hay una definición universalmente aceptada, pero el concepto de “Programa en ejecución” parece ser el que se utiliza con mas frecuencia. Un programa es una entidad inanimada; solo cuando un procesador le “infunde vida” se convierte en la entidad “activa” que se denomina proceso. Un proceso pasa por una serie de datos discretos. Se dice que un proceso se esta ejecutando (estado de ejecución), si tiene asignada la CPU. Se dice que un proceso esta listo(estado listo) si pudiera utilizar la CPU en caso de haber una disponible. Un proceso esta bloqueado (estado bloqueado) si se esta esperando que suceda algún evento antes de poder seguir la ejecución.

Los procesos secuenciales se han usado tradicionalmente para estudiar la concurrencia. ADA, es un lenguaje que maneja procesos secuenciales. Tanto sistemas paralelos como distribuidos son concurrentes; pero un sistema concurrente puede ser no paralelo ni distribuido, como acontece, por ejemplo, con los sistemas operativos monoprocesadores y multitarea, que son concurrentes pero no son paralelos ni distribuidos. Como ya se menciono los procesos son concurrentes si existen simultanemente. La concurrencia es el punto clave de la Multiprogramación, el Multiproceso y el Proceso distribuido y fundamental para el diseño de sistemas operativos. La concurrencia comprende un gran numero de cuestiones diseño, incluyendo la comunicación entre procesos, compartición y competencia por lo recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos.

La concurrencia puede presentarse en tres contextos diferentes

• Varias aplicaciones: La multiprogramación se creo para permitir que el tiempo de procesador de la maquina fuese compartido dinámicamente entre varios trabajos o aplicaciones activas.
• Aplicaciones estructuradas: Como aplicación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.
• Estructura del Sistema Operativo: Las mismas ventajas de estructuración son aplicables a los programadores de sistema y se han comprobado que algunos sistemas operativos están implementados con un conjunto de procesos.

Principios Generales de la concurrencia

En un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo para dar la apariencia de ejecución simultanea

En un sistema con varios procesadores, no solo es posible intercalar los procesos, sino también superponerlos. La intercalación y la superposición representan formas de ejecución muy diferentes. Ambas técnicas pueden contemplarse como ejemplos de proceso concurrente y ambas plantean los mismos problemas. En el caso de un sistema monoprocesador, los problemas creados por la multiprogramación parten del hecho de que la velocidad relativa de ejecución de los procesos no puede predecirse.

Los procesos concurrentes pueden funcionar en forma totalmente independiente unos de otros, o pueden ser asíncronos, lo cual significa que en ocasiones requieren cierta sincronización o cooperación. Cuando dos o mas procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos. Es importante mencionar que para que dos o mas procesos sean concurrentes, es necesario que tengan alguna relación entre ellos como puede ser la cooperación para un determinado trabajo o el uso de información o recursos compartidos, por ejemplo: en un sistema de un procesador, la multiprogramación es una condición necesaria pero no suficiente para que exista concurrencia, ya que los procesos pueden ejecutarse de forma totalmente independiente.

Las interacciones entre procesos tienen dos formas

• Primero comunicación.- Si tenemos varios procesos ejecutando y queremos que interactúen entre ellos para solucionar un determinado problema, y por tanto, necesitan intercambiar información, es decir necesitan comunicarse. Esto implica el intercambio de datos entre procesos, ya sea por medio de un mensaje implícito o a trabes de variables compartidas. Una variable es compartida entre procesos si es visible al código de esos procesos.

Mediante la comunicación se consigue que la ejecución de un proceso influya en la ejecución de otro.

• Segundo sincronización.- La sincronización (sinónimo de espera) es habitualmente necesaria cuando dos procesos se comunican puesto que la velocidad a la que se ejecutan no es predecible. Para que un proceso se comuniqué con otro, aquel deberá realizar acciones que sea capaz de detectar y esto solo funciona si realizar y detectar ocurren en este orden. Relaciona el seguimiento de un proceso con el seguimiento de otro. En otras palabras, la sincronización implica intercambio de información de control entre procesos.

La necesidad de contar con comunicación y sincronización puede verse en términos de competencia y cooperación entre procesos. La competencia ocurre cuando el proceso requiere el uso exclusivo de un recurso, como cuando dos procesos compiten por usar la misma impresora, o para reservar un asiento en un vuelo. Aquí la sincronización es necesaria para garantizar a un proceso el uso exclusivo de un recurso. La cooperación ocurre cuando dos procesos trabajan en distintas partes del mismo problema y por lo general incluyen a la comunicación y a la sincronización.

Propiedades de Vida

La ejecución concurrente de un proceso genera dos tipos de corrección: la seguridad y la vida. La seguridad se encarga de obtener la respuesta “correcta”. La vida tiene que ver con la tasa de avance de un proceso, es decir, con la velocidad a la cual avanza el calculo. La competencia por los recursos impone restricciones en el entrelazamiento de seguimientos.

Existen dos visiones del paralelismo:

• Paralelismo Hardware: Es el paralelismo definido por la arquitectura de la maquina.
• Paralelismo Software: Es el paralelismo definido por la estructura del programa. Se manifiesta en las instrucciones que no tienen interdependencias.

El paralelismo se presenta, a su vez, en dos formas

• Paralelismo de control: Se pueden realizar dos o mas operaciones simultáneamente. Se presenta en los pipelines y las múltiples unidades funcionales. El programa no necesita preocuparse de este paralelismo, pues se realiza a nivel hardware.
• Paralelismo de datos: una misma operación se puede realizar sobre varios elementos simultáneamente.

Características de la Concurrencia

Los procesos concurrentes tienen las siguientes características:

1. Indeterminismo: Las acciones que se especifican en un programa secuencial tienen un orden total, pero en un programa concurrente el orden es parcial, ya que existe una incertidumbre sobre el orden exacto de ocurrencia de ciertos sucesos, esto es, existe un indeterminismo en la ejecución. De esta forma si se ejecuta un programa concurrente varias veces pude producir resultados diferentes partiendo de los mismos datos.
2. Interacción entre procesos: Los programas concurrentes implican interacción entre los distintos procesos que los componen:

• Los procesos que comparten recursos y compiten por el acceso a los mismos.
• Los procesos que se comunican entre si para intercambiar datos.

1. Gestión de recursos: Los recursos compartidos necesitan una gestión especial. Un proceso que desee utilizar un recurso compartido debe solicitar dicho recurso, esperar a adquirirlo, utilizarlo y después liberarlo. Si el proceso solicita el recurso pero no puede adquirirlo en ese momento, es suspendido hasta que el recurso este disponible. La gestión de recursos compartidos es problemática y se debe realizar de tal forma que se eviten situaciones de retraso indefinido ( espera indefinidamente por un recurso) y de deadlock (bloqueo indefinido o abrazo mortal).
2. Comunicación: La comunicación entre procesos puede ser síncrona, cuando los procesos necesitan sincronizarse para intercambiar los datos, o asíncrona, cuando un proceso que suministra los datos no necesita esperar a que el proceso receptor los recoja, ya que los deja en un buffer de comunicación temporal.

Problemas de la Concurrencia

En los sistemas de tiempo compartido (aquellos con varios usuarios, procesos, tareas, trabajos que reparten el uso de CPU entre estos) se presentan muchos problemas debido a que los procesos compiten por los recursos del sistema. Los programas concurrentes a diferencia de los programas secuenciales tienen una serie de problemas muy particulares derivados de las características de la concurrencia:

1. Violación de la exclusión mutua: En ocasiones ciertas acciones que se realizan en un programa concurrente no proporcionan los resultados deseados. Esto se debe a que existe una parte del programa donde se realizan dichas acciones que constituye una región critica, es decir, es una parte del programa en la que se debe garantizar que si un proceso accede a la misma, ningún otro podrá acceder. Se necesita pues garantizar la exclusión mutua.
2. Bloqueo mutuo o deadlock: Un proceso se encuentra en estado de deadlock si esta esperando por un suceso que no ocurrirá nunca. Se puede producir en la comunicación de procesos y mas frecuentemente en la gestión de recursos. Existen cuatro condiciones necesarias para que se pueda producir deadlock:

• Los procesos necesitan acceso exclusivo a los recursos.
• Los procesos necesitan mantener ciertos recursos exclusivos mientras esperan por otros.
• Los recursos no se pueden obtener de los procesos que están a la espera.
• Existe una cadena circular de procesos en la cual cada proceso posee uno o mas de los recursos que necesita el siguiente proceso en la cadena.

1. Retraso indefinido o starvation: Un proceso se encuentra en starvation si es retrasado indefinidamente esperando un suceso que no puede ocurrir. Esta situación se puede producir si la gestión de recursos emplea un algoritmo en el que no se tenga en cuenta el tiempo de espera del proceso.
2. Injusticia o unfairness: Se pueden dar situaciones en las que exista cierta injusticia en relación a la evolución de un proceso. Se deben evitar situaciones de tal forma que se garantice que un proceso evoluciona y satisface sus necesidades sucesivas en algún momento.
3. Espera ocupada: En ocasiones cuando un proceso se encuentra a la espera por un suceso, una forma de comprobar si el suceso se ha producido es verificando continuamente si el mismo se ha realizado ya. Esta solución de espera es muy poco efectiva, porque desperdicia tiempo de procesamiento, y se debe evitar. La solución ideal es suspender el proceso y continuar cuando se haya cumplido la condición de espera.
4. Condiciones de Carrera o Competencia: La condición de carrera (race condition) ocurre cuando dos o mas procesos accedan a un recurso compartido sin control, de manera que el resultado combinado de este acceso depende del orden de llegada.
5. Postergación o Aplazamiento Indefinido(a): Consiste en el hecho de que uno o varios procesos nunca reciban el suficiente tiempo de ejecución para terminar a su tarea. Por ejemplo, que un proceso ocupa un recurso y lo marque como ocupado y que termine sin marcarlo como desocupado. Si algún otro proceso pide ese recurso, lo vera ocupado y esperara indefinidamente a que se desocupe.
6. Condición de Espera Circular:Esto ocurre cuando dos o mas procesos forman una cadena de espera que los involucra a todos.
7. Condición de No apropiación: Esta condición no resulta precisamente de la concurrencia, pero juega un papel muy importante en este ambiente. Esta condición especifica que si un proceso tiene asignado un recurso, dicho recurso no puede arrebatarsele por ningún motivo, y estará disponible hasta que el proceso lo suelte por su voluntad.

Se debe evitar, pues, que dos procesos se encuentren en su sección critica al mismo tiempo. Las técnicas para prevenir el deadlock consiste en proveer mecanismos para evitar que se presente una o varias de las cuatro condiciones necesarias de deadlock.

• Asignar recursos en orden lineal: Esto significa que todos los recursos están etiquetados con un valor diferente y los procesos solo pueden hacer peticiones de recursos hacia adelante.
• Asignar todo o nada: Este mecanismo consiste en que el proceso pida a todos los recursos que van a necesitar de una vez y el sistema se los da solamente si puede dárselos todos, sino, no le da nada y lo bloquea.
• Algoritmo del banquero: Este algoritmo usa una tabla de recursos para saber cuantos recursos tiene de todo tipo. También requiere que los procesos informen del máximo de recursos que van a usar de cada tipo. Cuando un proceso pide un recurso, el algoritmo verifica si a asignándole ese recurso todavía le quedan otros del mismo tipo para que alguno de los procesos en el sistema todavía se le pueda dar hasta su máximo. Si la respuesta es negativa, se dice que el sistema esta en estado inseguro y se hace esperar a ese proceso.

Para detectar un deadlock, se pude usar el mismo algoritmo del banquero, que aunque no dice que hay un deadlock, si dice cuando se esta en estado inseguro que es la antesala de deadlock. Sin embargo, para detectar el deadlock se puede usar las gráficas de recursos. En ellas se puede usar cuadrados para indicar procesos y círculos para los recursos, y las flechas para indicar si un recurso ya esta asignado a un proceso o si un proceso esta esperando un recurso. El deadlock es detectado cuando se puede hacer un viaje de ida y vuelta desde un proceso o recurso.

Bibliografía

• http://itver.edu.mx/so1/definiciones%20de%20proceso.htm
• http://lara.pue.udlap.mx/sist_oper/capitulo5.html
• http://agamenon.uniandes.edu.co/~c21437/ma-bedoy/taxonomi.htm
• http://itver.edu.mx/so1/Definiciones%2032.htm
• http://1ml.ls.fi.upm.es/~angel/concurrente/96notes/nodel15.html
• http://www.biocristalografria.df.ibilce.unesp.br/irbis/disertacion/node239.html
• http://gsyc.escet.urjc.es/simple_com/phd-thesis-es/node53.html
• http://1ml.ls.fi.upm.es/~angel/concurrente/96notes/nodel16.html
• http://tiny.uasnet.mx/prof/cln/ccu/mario/sisop/sisop06.htm
• http://fciencias.ens.uabc.mx/notas_cursos/so2/c_concu.html