Ejemplos de Concurrencia y Sincronizacion

Concurrencia

1.- El hecho de reservar un asiento en una avión mediante un sistema basado en aplicaciones web, cuando decenas de personas en el mundo pueden reservarlo también, nos da una idea de lo importante y crucial que es el control de concurrencia en un sistema de base de datos a mediana o gran escala.

2.- En una Base de Datos bancaria podría ocurrir que se paguen dos cheques en forma simultánea sobre una cuenta que no tiene saldo suficiente para cubrirlos en su totalidad, esto es posible evitarlo si se tiene un control de concurrencia.

Sincronizacion

1.- Cinco filósofos se sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Para comer los fideos son necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su izquierda y derecha. Si cualquier filósofo coge un tenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda coger el otro tenedor, para luego empezar a comer.

Si dos filósofos adyacentes intentan tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.

Si todos los filósofos cogen el tenedor que está a su derecha al mismo tiempo, entonces todos se quedarán esperando eternamente, porque alguien debe liberar el tenedor que les falta. Nadie lo hará porque todos se encuentran en la misma situación (esperando que alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este bloqueo mutuo se denomina interbloqueo o deadlock.

El problema consiste en encontrar un algoritmo que permita que los filósofos nunca se mueran de hambre.

Sincronizacion y Exclusion mutua

Históricamente los lenguajes de programación concurrente y Las APIs de los sistemas operativos ofrecen un conjunto de primitivas que facilitan la interacción entre procesos de forma sencilla y eficiente.

Estas primitivas deben hacer posible:

􀂄Sincronización: Un proceso tiene acceso al estado de flujo de control que en ese instante tiene otro proceso.

􀂄Exclusión mutua: Garantiza que mientras que un proceso accede a un recurso o actualiza una variables compartida, ningún otro proceso accede al mismo recurso o a la variable compartida.

􀂄Sincronización condicional: Garantiza que un recurso sólo es accedido cuando se encuentra en un determinado estado interno.

Síncrono se conocen los límites para el ritmo de deriva de los relojes, al máximo retardo de
transmisión de mensajes y el tiempo para ejecutar cada paso de un proceso.

En un sistema síncrono, por definición hay también un límite superior max del tiempo tomado para transmitir cualquier mensaje.

2.4 Concurrencia y secuenciabilidad

La concurrencia comprende un gran número de cuestiones de diseño, incluyendo la comunicación entre procesos, comparición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos y es fundamental para que existan diseños como Multiprogramación, Multiproceso y Proceso distribuido
Los procesos son concurrentes si existen simultáneamente. Cuando dos o más 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 más procesos sean concurrentes, es necesario que tengan alguna relación entre ellos
La concurrencia puede presentarse en tres contextos diferentes:

• Varias aplicaciones: La multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varios trabajos o aplicaciones activas.

• Aplicaciones estructuradas: Como ampliació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 sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos.

Existen tres modelos de computadora en los que se pueden ejecutar procesos concurrentes:

• Multiprogramación con un único procesador. El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecución de los mismos para dar así una apariencia de ejecución simultánea.

• Multiprocesador. Es una maquina formada por un conjunto de procesadores que comparten memoria principal. En este tipo de arquitecturas, los procesos concurrentes no sólo pueden intercalar su ejecución sino también superponerla.

• Multicomputadora. Es una maquina de memoria distribuida, que está formada por una serie de computadoras. En este tipo de arquitecturas también es posible la ejecución simultánea de los procesos sobre los diferentes procesadores.

En general, la concurrencia será aparente siempre que el número de procesos sea mayor que el de procesadores disponibles, es decir, cuando haya más de un proceso por procesador. La concurrencia será real cuando haya un proceso por procesador. Aunque puede parecer que la intercalación y la superposición de la ejecución de procesos presentan formas de ejecución distintas, se verá que ambas pueden contemplase como ejemplos de procesos concurrentes
Existen diversas razones que motivan la ejecución de procesos concurrentes en un sistema:

• Facilita la programación de aplicaciones al permitir que éstas se estructuren como un conjunto de procesos que cooperan entre sí para alcanzar un objetivo común.

• Acelera los cálculos. Si se quiere que una tarea se ejecute con mayor rapidez, lo que se puede hacer es dividirla en procesos, cada uno de los cuales se ejecuta en paralelo con los demás.

• Posibilita el uso interactivo a múltiples usuarios que trabajan de forma simultánea.

• Permite un mejor aprovechamiento de los recursos, en especial de la CPU, ya que pueden aprovechar las fases de entrada-salida de unos procesos para realizar las fases de procesamiento de otros.

Así como existen las razones que motivan la ejecución de procesos concurrentes, también existen sus contras:

• Inanición e interrupción de procesos

• Ocurrencia de bloqueos

• Que dos o mas procesos requieran el mismo recurso (No apropiativo)

Tipos de procesos concurrentes.
Los procesos que ejecutan de forma concurrente en un sistema se pueden clasificar como:

Proceso independiente: Es aquel que ejecuta sin requerir la ayuda o cooperación de otros procesos. Un claro ejemplo de procesos independientes son los diferentes shells que se ejecutan de forma simultánea en un sistema.
Procesos son cooperantes: Son aquellos que están diseñados para trabajar conjuntamente en alguna actividad, para lo que deben ser capaces de comunicarse e interactuar entre ellos.

En ambos tipos de procesos (independientes y cooperantes), puede producirse una serie de interacciones entre ellos y pueden ser de dos tipos:

• Interacciones motivadas porque los procesos comparten o compiten por el acceso a recursos físicos o lógicos. Por ejemplo, dos procesos independientes compiten por el acceso a disco o para modificar una base de datos.

• Interacción motivada porque los procesos se comunican y sincronizan entre sí para alcanzar un objetivo común, Por ejemplo, un compilador que tiene varios procesos que trabajan conjuntamente para obtener un solo archivo de salida.

Elementos a gestionar y diseñar a causa de la concurrencia.
Se pueden enumerar los siguientes:

1. El sistema operativo debe ser capaz de seguir la pista de los distintos procesos activos. Esto lo hace por medio de PBC’s (Bloque de Control de Procesos)

2. El sistema operativo debe asignar y quitar los distintos recursos a cada proceso activo. Entre estos recursos se incluyen:

• Tiempo de procesador: Es función de la planificación.
• Memoria: La mayoría de los sistemas operativos emplean esquemas de memoria virtual.
• Archivos:
• Dispositivos de E/S:

3. El sistema operativo debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos.

4. Los resultados de un proceso deben ser independientes de la velocidad relativa a la que se realiza la ejecución con respecto a otros procesos concurrentes.

*Instituto tecnológico de Celaya, Sistemas operativos unidad III, (n.d.). Extraído el 24 de octubre de 2008 desde http://sisinfo.itc.mx/ITC-APIRGG/Materias/Mat1/SistOp-I_Unid3.php#

2.3 Procesos Ligeros Hilos o hebras

El concepto de proceso engloba dos conceptos separados y potencialmente independientes: uno relativo a la propiedad de recursos y otro que hace referencia a la ejecución.
Unidad que posee recursos: A un proceso se le asigna un espacio de memoria y, de tanto en tanto, se le puede asignar otros recursos como dispositivos de E/S o ficheros.
Unidad a la que se le asigna el procesador: Un proceso es un flujo de ejecución (una traza) a través de uno o más programas. Esta ejecución se entremezcla con la de otros procesos. De tal forma, que un proceso tiene un estado (en ejecución, listo, etc) y una prioridad de expedición u origen. La unidad planificada y expedida por el sistema operativo es el proceso.
En la mayoría de los sistemas operativos, estas dos características son, de hecho, la esencia de un proceso. Sin embargo, son independientes, y pueden ser tratadas como tales por el sistema operativo. Esta distinción ha conducido en los sistemas operativos actuales a desarrollar la construcción conocida como thread, cuyas traducciones más frecuentes son hilo, hebra y proceso ligero. Si se tiene esta división de características, la unidad de asignación de la CPU se conoce como hilo, mientras que a la unidad que posee recursos se le llama proceso.
Dentro de un proceso puede haber uno o más hilos de control cada uno con:
· Un estado de ejecución (en ejecución, listo, bloqueado).
· Un contexto de procesador, que se salva cuando no esté ejecutándose.
· Una pila de ejecución.
· Algún almacenamiento estático para variables locales.
· Acceso a la memoria y a los recursos de ese trabajo que comparte con los otros hilos.
Los beneficios clave de los hilos se derivan de las implicaciones del rendimiento: se tarda menos tiempo en crear un nuevo hilo de un proceso que ya existe, en terminarlo, y en hacer un cambio de contexto entre hilos de un mismo proceso. Al someter a un mismo proceso a varios flujos de ejecución se mantiene una única copia en memoria del código, y no varias.
Un ejemplo de aplicación que podría hacer uso de los hilos es un servidor de ficheros de una red de área local. Cada vez que llega una solicitud de una operación sobre un fichero, se puede generar un nuevo hilo para su gestión. El servidor gestiona multitud de solicitudes, por tanto, se pueden crear y destruir muchos hilos en poco tiempo para dar servicio a estas peticiones. Si el servidor es un multiprocesador, se pueden ejecutar varios hilos de un mismo proceso simultáneamente y en diferentes procesadores.[1]

Un proceso ligero (thread o hebra) es un programa en ejecución que comparte la imagen de la memoria y otras informaciones con otros procesos ligeros.

Figura 1 Procesos ligeros

Es una unidad básica de utilización de la CPU consistente en un juego de registros y un espacio de pila. Comparte el código, los datos y los recursos con sus hebras pares

Una tarea (o proceso pesado) está formada ahora por una o más hebras

Una hebra sólo puede pertenecer a una tarea

 Figura 2 Tareas con una y varias hebras

CARACTERISTICAS


Se comparten recursos. La compartición de la memoria permite a las hebras pares comunicarse sin usar ningún mecanismo de comunicación inter-proceso del SO.

La conmutación de contexto es más rápida gracias al extenso compartir de recursos

No hay protección entre las hebras. Una hebra puede escribir en la pila de otra hebra del mismo proceso

Estado de los procesos ligeros

Un proceso ligero puede estar ejecutando, listo o bloqueado.

   

Figura 3 Estados de los Procesos ligeros

Paralelismo
Los procesos ligeros permiten paralelizar una aplicación.[2]

Figura 4 Paralelismo

[1] Milenkovic M. (1994). Sistemas Operativos. Conceptos y Diseño, 2ª Edición, McGraw-Hill.
Stallings, W. (1993).Computer Organization and Architecture, 3ª Edición. New York: Macmillan.
[2] HILOS (THREAD) (n.d.). Extraído el 24 de octubre de 2008 desde http://xue.unalmed.edu.co/~gsanchez/downloads/hilos.pdf