Historia

A menudo se asume que Dijkstra instigó el estudio de la programación concurrente en su ahora clásico artículo "Procesos secuenciales de cooperación", publicado en 1967. Ciertamente, en ese artículo vemos la introducción de algunos problemas ahora bien conocidos como "The Dining Philosophers "," The Sleeping Barber "y" The Dutch Flag Problem ", y quizás lo más importante, el problema de la sección crítica y su solución utilizando semáforos. Este artículo fue, de hecho, el primero en tener una visión de alto nivel de la programación concurrente. Como nota aparte, es interesante observar que el mismo artículo introduce la noción de interbloqueo y presenta un algoritmo que puede detectar la posible presencia de bloqueos. Sin embargo, a principios de la década de 1960, primero se presentó Conway y luego Dennis y Van Horn. La idea de múltiples hilos de control se introdujo en este momento, y es interesante observar que algunos de los problemas de acceso a recursos compartidos, como la memoria, también se abordaron en ese momento. Al igual que en el desarrollo de lenguajes de programación [secuencial] de alto nivel, los investigadores se dieron cuenta de los problemas asociados con el uso de estas construcciones de bajo nivel, principalmente en el área de tratar de escribir programas de manera correcta y rápida. y como resultado se inventaron construcciones de más alto nivel y más restrictivas. Por lo tanto, ahora vemos una plétora de diferentes técnicas para proporcionar programación concurrente controlada, muchas de las cuales examinaremos con mayor detalle en los últimos capítulos de este libro

La computación concurrente se desarrolló a partir de trabajos anteriores sobre ferrocarriles y telegrafía, del siglo XIX y principios del XX, y algunos términos datan de este período, como semáforos. Estos surgieron para abordar la cuestión de cómo manejar múltiples trenes en el mismo sistema ferroviario (evitando colisiones y maximizando la eficiencia) y cómo manejar múltiples transmisiones a través de un conjunto determinado de cables (mejorando la eficiencia), como a través de multiplexación por división de tiempo (década de 1870) ).

Es fascinante observar la evolución de la programación concurrente a lo largo del tiempo y cómo sus fundamentos se pueden rastrear hasta problemas prácticos en sectores como ferrocarriles y telegrafía. Además de los hitos mencionados, hay algunos aspectos y desarrollos adicionales a considerar:

1. Lenguajes Concurrentes: A medida que la programación concurrente evolucionó, surgieron lenguajes de programación específicos para manejar la concurrencia de manera más efectiva. Ejemplos notables incluyen Erlang, desarrollado por Ericsson para sistemas de telecomunicaciones concurrentes, y Ada, que también incluye características para la concurrencia.
2. Modelos de Concurrencia: A lo largo del tiempo, se han propuesto varios modelos de concurrencia para abordar los desafíos de la programación concurrente. Ejemplos incluyen el modelo de actores, el modelo CSP (Comunicating Sequential Processes) de Tony Hoare, y el modelo de memoria transaccional.
3. Programación Concurrente en la Era de los Multiprocesadores: Con el aumento de los sistemas multiprocesador y la computación en paralelo, la programación concurrente se ha vuelto aún más crucial. Las tecnologías como OpenMP y MPI permiten la programación concurrente en entornos de multiprocesadores y clústeres.
4. Concurrencia en el Desarrollo de Software Moderno: En el contexto actual, donde la concurrencia y la paralelización son esenciales para aprovechar al máximo la potencia de hardware moderno, se han desarrollado marcos y bibliotecas para facilitar la programación concurrente. Ejemplos incluyen el uso de hilos en lenguajes como Java y Python, así como bibliotecas como concurrent.futures y asyncio.
5. Problemas Emergentes en Concurrencia: A medida que las aplicaciones se vuelven más complejas, surgen nuevos desafíos en la programación concurrente, como la gestión de la concurrencia en entornos distribuidos, la sincronización de datos compartidos y la resolución de problemas de rendimiento y escalabilidad.

Filosofía

Es la división de un problema en subproblemas que se solucionan de forma individual, para crear un programa o aplicación que no se vea afectada en tiempo real.
Las dificultades de la concurrencia:

• ¿Cómo mantener el acceso a recursos compartidos correcto y eficiente?
• ¿Cómo permitir a los programadores razonar sobre un programa concurrente?
• ¿Cómo modelar la composición de tareas concurrentes?
• ¿Cuál es la abstracción más ergonómica para escribir programas concurrentes?

Modelos de concurrencia

La solución general en el mundo de la computación viene a apoyarnos en la solución a estos problemas: la abstracción.

Definición

Hace referencia a las técnicas de programación que son utilizadas para expresar la concurrencia entre tareas y solución de los problemas de comunicación y sincronización entre procesos. La programación concurrente es la ejecución simultánea de múltiples tareas interactivamente. Estas tareas pueden ser un conjunto de procesos o hilos de ejecución creados por un único programa. Las tareas se pueden ejecutar en una sola CPU (multiprogramación), en varios procesadores, o en una red de computadores distribuidos.

La programación concurrente no es más que la forma en la cual podemos resolver ciertas problemáticas de forma concurrente, es decir, ejecutando múltiples tareas a la misma vez y no de forma secuencial. En un programa concurrente las tareas puede continuar sin la necesidad que otras comiencen o finalicen.
Si bien es cierto que la programación concurrente acarrea ciertos problemas, principalmente al momento de compartir información entre tareas, también es cierto que si se implementa de forma correcta, podremos, en casos puntuales, mejorar significativamente el performance de nuestras aplicaciones.

Concurrencia VS Paralelismo

Este puede llegar a ser uno de los puntos que más interés puede llegar a causar en los programadores y con justa razón, ya que son términos que pueden llegar a confundirse fácilmente, es por ello que es necesario aprender a diferenciarlos.

La concurrencia es una forma de estructurar una solución que puede ser paralelizable (Aunque no siempre)

Concurrencia

• Soporta dos o más acciones en progreso
• Procesos que se ejecutan de manera independiente
• Lidiar con muchas cosas al tiempo
• Sobre la estructura

Paralelismo

• Soporta dos o más acciones ejecutándose simultáneamente
• Procesos que se ejecutan Simultáneamente (tal vez relacionados)
• Hacer muchas cosas al tiempo
• Sobre la ejecución

Como diferenciarlas?

La concurrencia y el paralelismo han sido extensamente discutidos, pero al momento de definirlos, varios autores salen con su propia definición y esta variedad no hacen tan fácil la tarea de entender. En términos sencillos, se puede explicar así:

Un programa es concurrente si puede soportar dos o más acciones en progreso.

Un programa es paralelo si puede soportar dos o más acciones ejecutándose simultáneamente."

La palabra clave es en progreso.

Un programa es concurrente por que maneja varias tareas al mismo tiempo, define acciones que pueden ser ejecutadas al mismo tiempo.
Y para que un programa sea paralelo, no solo debe ser concurrente, sino que tambien debe estar diseñado para correr en un medio con hardware paralelo (GPU's, procesadores multi-core, etc).

Puede ser visto como que la concurrencia es la propiedad de un programa, mientras que el paralelismo es la forma en la que se ejecuta un programa concurrente.

Para entender esta diferencia, también podemos usar una analogía de una cafetería y un barista, y en la que hay dos tareas disponibles: tomar pedidos y preparar café.

Supongamos que tenemos la cafetería con un solo barista. En este escenario, el barista toma pedidos y prepara café para los clientes que llegan. Mientras espera que el café se prepare, en lugar de estar inactivo, puede atender a otro cliente y tomar su pedido. Aunque cada tarea individual (tomar un pedido o preparar café) no ocurre al mismo tiempo, la cafetería está manejando múltiples flujos de trabajo de manera concurrente a través del barista. Es como si el barista estuviera alternando entre tomar pedidos y preparar bebidas, gestionando varias tareas de manera eficiente aunque no todas estén en progreso de forma simultánea. A esto se le conoce como concurrencia.

Ahora, supongamos que tenemos una cafetería con varios baristas, cada uno con su propia área de trabajo y su propia máquina de café. En esta situación, cada barista puede atender a un cliente de manera independiente. Pueden tomar pedidos y preparar bebidas de forma simultánea. La clave aquí es que las acciones de cada barista están ocurriendo verdaderamente al mismo tiempo, aprovechando los recursos individuales de cada uno. Este escenario refleja el paralelismo, donde múltiples tareas se ejecutan simultáneamente gracias a la disponibilidad de recursos independientes (múltiples baristas). Cada barista es como un núcleo de procesador en un sistema que permite la verdadera simultaneidad en la ejecución de tareas.

Relación

Múltiples procesos pueden ser ejecutados al mismo tiempo. En otras palabras, la programación concurrente se comporta igual que la paralela cuando tenemos un sistema multiprocesador en el cual cada unidad de procesamiento ejecuta un proceso o hilo. En la imagen inferior podemos ver que la unidad de procesamiento 2 y 3 se comportan igual.

Ejemplo de concurrencia:

Imagina una aplicación de descarga de música, en la cual puedes descargar un número determinado de canciones al mismo tiempo, cada canción es independiente de la otra, por lo que la velocidad y el tiempo que tarde en descargarse cada una no afectara al resto de canciones. Esto lo podemos ver como un proceso concurrente, ya que cada descarga es un proceso totalmente independiente del resto.

Observa la imagen, cada descarga se procesa de forma separada, y al final a una descarga no le importa el estado de las demás. Ya que cada descarga es una tarea completamente diferente.

Ejemplo de paralelismo:

Imagina la clásica página de viajes, donde nos ayudan a buscar el vuelo más barato o las mejores promociones, para hacer esto, la página debe de buscar al momento en cada aerolínea el vuelo más barato, con menos conexiones, etc. Para esto puedo hacerlo de dos formas, buscar secuencialmente en cada aerolínea las mejores promociones (muy tardado) o utilizar el paralelismo para buscar al mismo tiempo las mejores promociones en todas las aerolíneas.

Observemos en la imagen como el proceso parte de una entrada inicial (inputs) los cuales definen las características del vuelo a buscar, luego se utiliza la concurrencia para buscar en las cuatro aerolíneas al mismo tiempo. Veamos que en este proceso es indispensable que las 4 búsquedas terminen para poder arrojar un resultado. Podemos ver claramente la relación entre los 4 procesos, ya que el resultado de uno puedo afectar al proceso final.

Observemos también que una vez que los cuatro procesos terminan, hay un subproceso adicional encargado de unir los resultados y arrojar un resultado final.

Proceso o Hilo ?

Primero, los procesos son más pesados de crear y, por lo tanto, utilizan más capacidades de computadora que los hilos. Esto permite entonces de hacer tareas más pesadas.

En segundo lugar, los procesos son totalmente independientes entre ellos. No comparten ningún dato entre ellos; Mientras que, los hilos pueden compartir información fácilmente.

Desafortunadamente, esto crea un problema: si dos hilos trabajan con los mismos datos, se puede crear errores como, por ejemplo, el valor cambia sin entender por qué. De hecho, cuando se realizan dos tareas al mismo tiempo, si modificamos los datos en un hilo y hacemos lo mismo en la otra, será imposible predecir qué hilo modificarán primero la variable.
Para esto, hay un sistema para "bloquear" los datos en un hilo. Una vez que este hilo desbloqueará los datos, el otro hilo recibirá una señal de que puede modificarlo.
Para resumir, cuando se trabaja en los mismos datos con dos subprocesos diferentes, es necesario bloquear los datos en un hilo en el momento de modificarlo, y luego desbloquearlo.

Hay que aclarar la concurrencia no solo es paralelismo, ya que, cuando hay más procesos o hilos el scheduler del sistema operativo interviene y divide la ejecución de los procesos, característica que la programación paralela NO tiene cada proceso tiene que ser ejecutado exclusivamente en una unidad de procesamiento. En la parte inferior podemos apreciar mejor la diferencia.

Cuadro comparativo Procesos vs Hilos:

#	Procesos	Hilos
1	Son programas en ejecución.	Son segmentos de procesos.
2	Tardan más tiempo en terminar.	Tardan menos tiempo en terminar.
3	Toma más tiempo crearlos.	Toma menos tiempo crearlos.
4	Toma más tiempo hacer el cambio de contexto.	Toma menos tiempo hacer el cambio de contexto.
5	Son menos eficientes en términos de comunicación.	Son meás eficientes en términos de comunicación.
6	Consumen más recursos.	Consumen menos recursos.
7	Son aislados.	Comparten memoria.
8	Son denominados "heavy weight process".	Son denominados "light weight process".
9	Los procesos tienen su propio PCB, Stack y espacio en memoria.	Los hilos tienen el PCB de sus padres, su propio Thread Control Block (TCB) y Stack y un espacio de memoria compartido.

Ejemplos Gophers

Los Gophers son la mascota de Go (un roedor) los cuales se usaran para el siguiente ejemplo.
Imagina que tenemos un Gopher que tiene que llevar una pila de libros a un incinerador, para esto, usa un carro para llevar cierta cantidad de libros al incinerador y luego volver a la pila para reponer dicho carro.

Si agregamos otro Gopher al ejemplo este no podrá hacer nada porque las herramientas estarán ocupadas por su compañero como se ve en la siguiente imagen.

Para este caso simple tenemos dos soluciones simples, una concurrente y la otra paralela.
La solución concurrente es que se añada otro carro para que el segundo Gopher pueda trabajar, sin embargo esto ocasiona que se necesite una sincronización entre los Gophers porque si los dos llegan al incinerador al mismo tiempo uno tendrá que esperar al otro, provocando una pérdida de efectividad.

La solución paralela es duplicar todo, usando dos pilas de libros, dos carros y dos incineradores, provocando que no se necesite gestionar la sincronización entre los Gophers y que ambos puedan trabajar todo el tiempo.

Para complicar el ejemplo ahora vamos a usar 4 Gophers. Usando una solución concurrente podemos gestionar a los 4 Gophers para que hagan tareas diferentes y completamente independientes, el primero llena el carro con libros, el segundo lleva el carro al incinerador, el tercero arroja los libros del carro al incinerador, y el cuarto regresa el carro a la pila de libros.

Como se dijo anteriormente una solución concurrente puede ser fácilmente paralelizadle, y en este ejemplo no es la excepción, lo único que se necesita es duplicar todo y que todo se haga al tiempo.

Conceptos

Proceso

Un proceso no solamente es el código de un programa, un proceso tiene un contador de programa el cual es un registro del computador que indica la dirección de la siguiente instrucción que será ejecutada por el proceso, Pila de proceso Esta contiene datos temporales tales como: Los parámetros de las funciones, direcciones de retorno, variables locales , … , Sección de datos la cual contiene datos tales como las variables locales, Heap: Cúmulo de memoria que es la memoria que se asigna dinámicamente al proceso n tiempo de ejecución

Note que un programa por sí sólo no es un proceso, ya que este es una entidad pasiva que contiene una lista de instrucciones almacenadas en disco ( archivo ejecutable), mientras que un proceso es una entidad activa, el cual cumple todas las características descritas anteriormente.

Estados del proceso

Cuando un proceso es ejecutado este cambia de estados, los estados que todo proceso tiene por lo general son:

• Nuevo: El proceso se está creando.

• Corriendo: Se están ejecutando las instrucciones.

• Espera: El proceso está esperando que algún evento ocurra.

• Preparado: El proceso está esperando ser asignado al procesador.

• Terminado: El proceso a terminado la ejecución.

PCB ( Bloque de control de proceso )

Cada proceso se representa en el sistema operativo mediante el PCB, entre los elementos de información que este contiene se encuentran:

• Estado del proceso: New, ready, running, waiting, halted, ...

• Contador del programa:

• Registros de la CPU: Estos varían en cuanto a número y tipo dependiendo de la arquitectura del procesador

• Información de planificación de la CPU: Parametros de planificación como prioridad de procesos, punteros a las colas de planificación ...

• Información de gestión de memoria: Tablas de páginas , tablas de segmentos, dependiendo los mecanismos de gestión del S.O

Hilo

Se puede definir como una unidad básica de ejecución del Sistema Operativo para la utilización del CPU. Este es quien va al procesador y realiza todos los cálculos para que el programa se pueda ejecutar. Es necesario, ya que debe contar con al menos un hilo para que cualquier programa sea ejecutado. Cada hilo tiene: id de hilo, contador de programa, registros, stack. Dentro de las características que se encuentran se tiene que cada hilo tiene información del código de máquina que se va a ejecutar en el procesador, sus respectivos datos, el acceso a los archivos, el registro y su respectivo stack en donde se guarda toda la información necesaria del hilo como son las variables locales, variables de retorno o algo a lo que se acceda en tiempo de ejecución. Los hilos que pertenecen a un mismo proceso comparten: sección de código, sección de datos, entre otros recursos del sistema. El multithreading es la capacidad para poder proporcionar múltiples hilos de ejecución al mismo tiempo. Una aplicación por lo general es implementada como un proceso separado con muchos hilos de control. Dentro de las semejanzas de hilo y multihilo es que poseen un solo bloque de control de proceso (PCB) y un solo espacio de direcciones de proceso. Por el contrario, en las diferencias es que mientras un hilo tiene una pila para sus registros y stack, el multihilo tiene una pila para cada hilo con subbloques de control internos, incluyendo la pila de registros y sus respectivos stacks. Se dice que los hilos de ejecución que comparten recursos agregando estos recursos da como resultado el proceso.

Caracteristicas:

• Modelo apropiativo: Los hilos deben operar bajo la suposición de que su ejecución puede verse interrumpida por el sistema operativo en cualquier momento.
• Posibilidad de recursos compartidos: Diferentes hilos en un proceso pueden acceder a la misma región de memoria, o descriptores de archivos comunes (entre otros).
• Soporte directo al paralelismo: Se puede asumir con confianza que usar hilos en un sistema multiprocesador lleva a una mayor utilización de esta característica.

Diseño:

• Creación de un hilo: La abstracción básica es la ejecución de una función como punto de entrada para un hilo individual, y la obtención de un recurso vinculado a dicha ejecución. Un hilo puede comenzar con:
• Un puntero a una función
• Una clausura
• Un método en un objeto

Un hilo se puede monitorear con:

• Un identificador en una tabla
• Un objeto nuevo
• El estado del objeto que la crea
• Comunicación: Los hilos se pueden comunicar por medio de memoria compartida. Para asegurar que esta memoria es accedida de manera correcta, se provee al programador con primitivas de sincronización: semáforos, exclusiones mutuas, tipos atómicos.

Multiprogramación

Es una técnica de multiplexación que permite de múltiples procesos en un único procesador. Es importante resaltar que los procesos nunca corren en paralelo en el procesador, ya que en cada instante de tiempo solo se ejecuta un proceso en el procesador.

Multiproceso

Es una técnica en la cual se hace uso de dos o más procesadores en una computadora para ejecutar uno o varios procesos.

Corrutinas

Una corrutina es un componente de programación concurrente que permite la ejecución cooperativa de múltiples tareas en un mismo hilo de ejecución. A diferencia de los hilos tradicionales, donde el sistema operativo es responsable de la planificación y la asignación de tiempo de ejecución, las corrutinas son controladas por el programador y pueden ceder el control de manera explícita.

Características:

• Modelo cooperativo: Las corrutinas tienen que ser programadas de manera que cedan la ejecución en momentos apropiados, y eviten acaparar recursos.
• Contextos ligeros: Las corrutinas requieren un uso de memoria considerablemente menor, gracias a que no definen el contexto completo: un solo hilo de S.O. puede aprovisionar múltiples corrutinas.
• Soporte opcional de paralelismo: Las corrutinas suelen modelar la concurrencia como un cambio de contexto dentro de un mismo hilo, sin embargo, es probable que un runtime moderno permita configurar para usar múltiples hilos.

Diseño:

• Cooperación Deben existir constructos en el lenguaje (palabras clave, interfaces, u otros) que permitan señalizar el punto en el que una corrutina cede la ejecución.

Algunas formas de sintaxis que pueden permitir esto:

• Funciones que retornan handles, con métodos adecuados.
• Objetos compartidos que monitorean el estado de cada subrutina.
• Palabras claves que indican la oportunidad para cambiar de contexto, como yield o await.

Event Loop

Caracteristicas:

• Modelo bloqueante deferido: Se establece un mecanismo para registrar la ocurrencia de eventos y la ejecución de tareas en respuesta a diferentes tipos de eventos, al final de un ciclo de ejecución.
• Concurrente, no paralelo por defecto: Este modelo permite describir la ocurrencia de diferentes eventos intercaladamente en un sólo hilo, y responder a eventos que serían bloqueantes con el registro de un evento. De esta manera se consigue un uso óptimo de recursos, pero no se modela el acceso a capacidades paralelas.
• Memoria local El alcance de los recursos es análogo al de un programa secuencial.

Diseño:

El registro de acciones a ejecutar en respuesta a eventos tiene una solución que se ajusta perfectamente: las clausuras.
Sin embargo, el uso de clausuras para el uso de los valores resultantes de computaciones deferidas tiene problemas de ergonomía (véase: pirámide de la perdición).
Alternativas:

• Promesas/Futuros: Objetos con métodos adecuados.
• Async/Await: Palabras claves para describir computaciones deferidas.

Actores

En el contexto de la programación concurrente, un actor es una entidad de ejecución independiente que encapsula su propio estado y procesamiento. Los actores se comunican entre sí a través del intercambio de mensajes, y cada actor tiene una cola de mensajes asociada. Cada mensaje recibido es procesado secuencialmente por un único actor a la vez, lo que evita problemas de concurrencia como las condiciones de carrera.

Características:

• Procesos ligeros: Un actor es una unidad de procesamiento análoga al proceso, pero manejada por un proceso del S.O. real: la máquina virtual del lenguaje de programación. Gracias a esto, cada actor es extremadamente pequeño.
• Modelo apropiativo: La máquina virtual actúa como el árbitro de la ejecución de los actores, deteniendo su ejecución de acuerdo a medidas globales.
• Paralelismo: Según las capacidades de la máquina virtual, el paralelismo puede ser tan automático como al usar hilos.

Diseño:

El modelo de actores establece que estas unidades mínimas no comparten memoria, y su viabilidad es independiente de la de los otros. Esto implica:

• Comunicación por mensajes: los actores se informan de su estado y solicitan computaciones a partir de mensajes, y, por tanto, no comparten memoria mutable.
• Pureza: Los actores solo conocen su estado interno, y los mensajes que obtienen del exterior, que pueden pensarse como argumentos a una función pura. De ahí la capacidad de paralelismo.
• Manejo de errores optimista: los errores causados por condiciones inusuales y transitorias son manejados reiniciando un actor, manteniendo el programa global en curso.

Procesamiento distribuido

Es cuando uno o varios procesos son ejecutados en una o más computadores

Planificación De Procesos

Estrategia de los sistemas operativos con la que se es posible compartir la CPU entre los diferentes procesos alojados en memoria. La calendarización es un manejo de colas con el objetivo de maximizar el uso de recursos y minimizar retardos.

Tipos de Calendarización

Calendarización a corto plazo

• Determina cuáles programas son admitidos al sistema para la ejecución.
• El objetivo principal es mantener una mezcla balanceada de tareas, como los límites de entrada/salida y de procesador.
• Controla el nivel de multiprogramación.

Calendarización a mediano plazo

Calendarización a largo plazo

• Hace parte del swapping del sistema.
• Agrega y remueve procesos de memoria.
• Reduce el nivel de multiprogramación del sistema.

Cambios de contexto

• Registers
• Stack pointer
• Program counter

Criterios de Calendarización

• Utilización de CPU: mantener el CPU lo más ocupado posible
• Throughput: Procesos completados por unidad de tiempo
• Tiempo de vuelta: tiempo en completar un proceso en específico
• Tiempo de espera: tiempo en el que un proceso ha estado en la cola de ready
• Tiempo de respuesta: tiempo que toma desde la creación del proceso hasta su primera respuesta

Algoritmos de Calendarización

• First-Come, First-Served (FCFS)

Algoritmo simple de calendarización, en el que asigna el procesador según el orden de llegada a la cola de ready y lo ejecuta hasta el final, como ventajas tienen un buen throughput y tiempo de vuelta, como desventajas malos tiempos de respuesta y de espera, en cuanto a utilización de CPU tiene la ventaja de que hace pocos cambios de contexto, mas se desaprovecha el CPU cuando los procesos tienen que esperar a entradas y/o salidas.

• Shortest-Job-First (SJF)

con SJF se ejecuta primero el proceso con menor tiempo de ejecución que se encuentre en la cola de ready, a comparación de FCFS tiene mejor tiempo de respuesta, mejor throughput, menores tiempos de espera, en cuanto a uso del CPU se comporta igual a FCFS, como desventaja tiene la dificultad de predecir el tiempo de ejecución de un proceso.

• Priority Scheduling

Introduce una necesidad en el que unos procesos deben tener prioridad sobre otros, para ello asocia un numero indicando el nivel de prioridad a cada proceso cuando están en la cola de ready selecciona el de mayor prioridad, como desventaja los procesos con baja prioridad podrían sufrir de starvation tardando mucho o nunca saliendo de la cola de ready, esto se soluciona utilizando una técnica en la que a medida que va pasando el tiempo se incrementa la prioridad de un proceso en la cola, por lo que aquellos que lleven mucho tiempo en esta irán aumentando su prioridad. Dependiendo de las prioridades que se le asignen a cada proceso puede tener buenos o malos tiempos. Hay que tener en cuenta que si ningún otro proceso está en la cola de ready ejecutara el único que haya en la cola, más en el momento que llegue un proceso con mayor prioridad se sacara de ejecución el de menor y el CPU lo ocupara el que acaba de llegar con mayor prioridad, esto se evidencia en el ejemplo a continuación:

• Round Robin (RR)

Se asigna un tiempo de CPU (time quantum) para todos los procesos, estos se ejecutarán durante ese tiempo según el orden de llegada, en cuanto completan el tiempo asignado se sacan de ejecución y se regresan a la cola de ready, este procedimiento se repite hasta que el proceso complete toda su ejecución. Como ventaja tiene bajos tiempos de espera y de respuesta, peor tiempo de vuelta y throughput mas bajo que SJF, el uso del CPU baja por el mayor numero de cambios de contexto que debe hacer, por lo que es importante escoger un buen time quantum, si se escoge un tiempo muy corto habrá muchos cambios de contexto y los procesos tardaran mucho más en terminar, si se escoge muy grande se perderían las ventajas del algoritmo, se suele usar tiempos de 10ms a 100ms, también hay que tener en cuenta que para que sea optimo este tiempo debe ser mayor al que tarda el procesador en hacer un cambio de contexto.

• Multiple-Level Queues

la cola de ready se parte en varias colas que determinan la prioridad de los procesos, cada cola implementa su propio algoritmo de calendarización y adicionalmente también se hace calendarización entre las colas

Ejemplo Algoritmos de Calendarización

En la figura se puede ver cómo son atendidos 5 procesos según cada algoritmo.

¿Qué se puede ejecutar concurrentemente?

No todas las partes de un programa se pueden ejecutar concurrentemente:

• En la primera columna está claro que la primera sentencia se debe ejecutar antes que la segunda
• En la segunda columna, el orden en que se ejecuten no tiene importancia

En general existen unas condiciones para saber que se puede ejecutar concurrentemente: Condiciones de Bernstein.

Condiciones de Bernstein

Para poder determinar si dos conjuntos de instrucciones se pueden ejecutar concurrentemente, sea Sk un conjunto de instrucciones a ejecutar, llamamos:

• L(Sk) = {a1, a2, ...an} al conjunto de lectura, formado por todas las variables cuyos valores son referenciados (se leen) durante la ejecución de las instrucciones Sk.
• E(Sk) = {b1, b2, ...bm} al conjunto de escritura, formado por todas las variables cuyos valores son actualizados durante la ejecución.

Para que se puedan ejecutar concurrentemente dos conjuntos de instrucciones Si y Sj se debe cumplir que ninguno escriba lo que el otro lee o escribe:

Problemas de los programas concurrentes

Al lidiar con varias tareas al tiempo los programas concurrentes pueden presentar varios problemas :

• Violación de la exclusión mutua : Como se menciono anteriormente, es cuando más de un hilo trata de ejecutar la sección critica de un programa y lo logra, obteniendo asi resultados indeseados. Por ejemplo, tenemos una expresión de tipo:
  x = x + 1
  Donde x tiene un valor inicial de 6, entonces al haber violación de exclusión mutua, varios hilos podrian tomar una copia local de x, añadir 1 y todos devuelven 7 a x, lo cual es algo que no se quiere.
  Un ejemplo que replica este problema en Java, un contador que al final deberia dar 1000000, pero siempre arroja diferentes resultados:
  

        // Ejemplo hecho para ilustrar la mutabilidad del estado compartido de los hilos.
        // Muestra un resultado distinto cada vez que se corre el programa
  
        public class Counting {
          public static void main(String[] args) throws InterruptedException {
          class Counter {
          int counter = 0;
          public void increment() { counter++; }
          public int get() { return counter; }
          }
          final Counter counter = new Counter();
  
          class CountingThread extends Thread {
          public void run() {
          for (int x = 0; x < 500000; x++) {
          counter.increment();
          }
          }
          }
  
          CountingThread t1 = new CountingThread();
          CountingThread t2 = new CountingThread();
          t1.start(); t2.start();
          t1.join(); t2.join();
          System.out.println(counter.get());//deberia dar 1000000
          }
        }
      

  Y el resultado es:
  

        Picked up _JAVA_OPTIONS: -Djava.io.tmpdir=/home/user/tmp/ -Xms64m
        883345
        ~/Java$ java Counting
        Picked up _JAVA_OPTIONS: -Djava.io.tmpdir=/home/user/tmp/ -Xms64m
        830292
        ~/Java$ java Counting
        Picked up _JAVA_OPTIONS: -Djava.io.tmpdir=/home/user/tmp/ -Xms64m
        1000000
        ~/Java$ java Counting
        Picked up _JAVA_OPTIONS: -Djava.io.tmpdir=/home/user/tmp/ -Xms64m
        964409
        ~/Java$ java Counting
        Picked up _JAVA_OPTIONS: -Djava.io.tmpdir=/home/user/tmp/ -Xms64m
        945471
        ~/Java$ java Counting
        Picked up _JAVA_OPTIONS: -Djava.io.tmpdir=/home/user/tmp/ -Xms64m
        961164
        ~/Java$
      

  Esto se debe a que no hay un orden total como sucede en la programación secuencial, hay un orden parcial, lo que genera un orden de precedencia de las instrucciones que se deben ejecutar muy diferente, de tal manera que en dicho árbol se muestra un orden de ejecución simultáneo para todas las instrucciones del programa.
  
  
  
  
• Deadlock : Tambien conocido como abrazo mortal, ocurre cuando un proceso espera un evento que nunca va a pasar. Aunque se puede dar por comunicación entre procesos , es más frecuente que se de por manejo de recursos. En este caso, deben cumplirse 4 condiciones para que se de un "deadlock" :
  • Los procesos deben reclamar un acceso exclusivo a los recursos.
  • Los procesos deben retener los recursos mientras esperan otros.
  • Los recursos pueden no ser removidos de los procesos que esperan.
  • Existe una cadena circular de procesos donde cada proceso retiene uno o más recursos que el siguiente proceso de la cadena necesita.
  Las técnicas utilizadas para evitar estos problemas consisten en negar una de las cuatro condiciones anteriormente mencionadas.
  Un ejemplo que replica este problema es este de a continuación, escrito en Ada. Aqui dos procesos se ejecutan de manera finita, mientras que otros dos, los que hacen los llamados funcionan en un ciclo infinito y al final se quedan esperando algo que nunca va a ocurrir:
  

  
        with Ada.Text_IO;
        use Ada.Text_IO;
        procedure Meals1 is
  
          HOURS : constant := 1;
          type PERSON is (BILL, JOHN);
  
          package Enum_IO is new Ada.Text_IO.Enumeration_IO(PERSON);
          use Enum_IO;
  
          task Bills_Day;
  
          task Johns_Day;
  
          task Restaurant is
          entry Eat_A_Meal(Customer : PERSON);
          end Restaurant;
  
          task Burger_Boy is
          entry Eat_A_Meal(Customer : PERSON);
          end Burger_Boy;
  
          task body Bills_Day is
          My_Name : PERSON := BILL;
          begin
          delay 1.0 * HOURS;
          Restaurant.Eat_A_Meal(My_Name);
          delay 1.0 * HOURS;
          Restaurant.Eat_A_Meal(My_Name);
          delay 1.0 * HOURS;
          Restaurant.Eat_A_Meal(My_Name);
          end Bills_Day;
  
          task body Johns_Day is
          My_Name : PERSON := JOHN;
          begin
          delay 0.4 * HOURS;
          Restaurant.Eat_A_Meal(My_Name);
          delay 0.4 * HOURS;
          Restaurant.Eat_A_Meal(My_Name);
          delay 4.0 * HOURS;
          Restaurant.Eat_A_Meal(My_Name);
          end Johns_Day;
  
          task body Restaurant is
          begin
          loop
          accept Eat_A_Meal(Customer : PERSON) do
          Put(Customer);
          Put_Line(" esta ordenando en el restaurante");
          delay 0.5 * HOURS;
          Put(Customer);
          Put_Line(" esta comiendo en el restaurante");
          delay 0.5 * HOURS;
          end Eat_A_Meal;
          end loop;
          end Restaurant;
  
          task body Burger_Boy is
          begin
          loop
          accept Eat_A_Meal(Customer : PERSON) do
          Put(Customer);
          Put_Line(" esta ordenando en el McDonalds");
          delay 0.1 * HOURS;
          Put(Customer);
          Put_Line(" esta comiendo en el McDonalds");
          delay 0.1 * HOURS;
          end Eat_A_Meal;
          end loop;
          end Burger_Boy;
  
        begin
          null;
        end Meals1;
      

  Y el resultado es:

        JOHN esta ordenando en el restaurante
        JOHN esta comiendo en el restaurante
        BILL esta ordenando en el restaurante
        BILL esta comiendo en el restaurante
        JOHN esta ordenando en el restaurante
        JOHN esta comiendo en el restaurante
        BILL esta ordenando en el restaurante
        BILL esta comiendo en el restaurante
        BILL esta ordenando en el restaurante
        BILL esta comiendo en el restaurante
        JOHN esta ordenando en el restaurante
        JOHN esta comiendo en el restaurante
  
  
      

  Se queda atascado en medio de la ejecución.
• Aplazamiento indefinido : O tambien conocido como "starvation" o "lockout", se da cuando el algoritmo que maneja los recursos no tiene en cuenta el tiempo que lleva esperando ese proceso. Para solucionar esto entre procesos que compiten se puede manejar de tal manera que mientras más espere un proceso, más alta será su prioridad, aunque una solución más sencilla y aplicable a un rango mayor de circunstancias es tratar con los procesos estrictamente en su orden de espera.
  Un ejemplo en Ada es el siguiente, en este, un hilo se queda esperando una respuesta de otro proceso que nunca va a ocurrir por que la tarea Gourmet ya acabo, y por eso no va a ser llamada:

  
          with Ada.Text_IO;
          use Ada.Text_IO;
  
          procedure HotDog is
  
            task Gourmet is
            entry Make_A_Hot_Dog;
            end Gourmet;
  
            task body Gourmet is
            begin
            Put_Line("Voy a preparar un perro caliente");
            for Index in 1..5 loop --si se cambia el 4 por un 5 se entrará en inanicion porque el task main del procedure hotdog no recibira la llamada
            accept Make_A_Hot_Dog do
            delay 0.8;
            Put("Pongo el perro caliente en la mesa ");
            Put_Line(" y le pongo mostaza");
            end Make_A_Hot_Dog;
            end loop;
            Put_Line("ya no quiero mas perros calientes");
            end Gourmet;
  
          begin
            for Index in 1..4 loop
            Gourmet.Make_A_Hot_Dog;
            delay 0.1;
            Put_Line("como lo que me queda de perro caliente");
            New_Line;
            end loop;
            Put_Line("ya estoy lleno");
          end HotDog;
      

  Y su resultado es:

        Voy a preparar un perro caliente
        Pongo el perro caliente en la mesa y le pongo mostaza
        como lo que me queda de perro caliente
  
        Pongo el perro caliente en la mesa y le pongo mostaza
        como lo que me queda de perro caliente
  
        Pongo el perro caliente en la mesa y le pongo mostaza
        como lo que me queda de perro caliente
  
        Pongo el perro caliente en la mesa y le pongo mostaza
        como lo que me queda de perro caliente
  
        ya estoy lleno
      

• Injusticia : también conocido como "unfairness", ocurre cuando el programa no tiene mecanismos para asegurar que se da un progreso "parejo" en las tareas concurrentes, este es un aspecto que el diseñador debe tener en cuenta al desarrollar el programa, cualquier descuido a la "justicia" de un programa podría generar un aplazamiento indefinido.
• False sharing:

  Es un fenómeno en programación concurrente en el cual dos o más hilos o procesos, que trabajan en diferentes partes de la memoria, comparten una caché. Aunque están modificando datos independientes, debido a la arquitectura de la caché, las actualizaciones de una región de memoria pueden invalidar la caché de otra región, haciendo necesaria una nueva sincronización, resultando en un rendimiento subóptimo y problemas de concurrencia.

  En arquitecturas de computadoras modernas, la memoria se organiza en líneas de caché. Si dos hilos modifican datos ubicados en la misma línea de caché, aunque sean datos diferentes, la caché podría invalidarse continuamente, generando un overhead innecesario.

  El false sharing puede tener un impacto significativo en el rendimiento, ya que puede resultar en una mayor competencia por recursos de caché y la invalidación frecuente de cachés. Esto puede llevar a un aumento en el tiempo de ejecución y una disminución de la eficiencia del programa.

  Para mitigar el false sharing, se pueden emplear varias estrategias:

  • Alineación de Variables: Asegurarse de que las variables utilizadas por hilos concurrentes estén alineadas de manera que ocupen diferentes líneas de caché.
  • Padding: Agregar relleno (padding) entre variables para separarlas en líneas de caché diferentes y evitar la interferencia entre ellas.
  • Técnicas de Optimización del Compilador: Algunos compiladores ofrecen opciones para alinear variables y optimizar la disposición en la memoria.

  A continuación se presenta una demostración visual del problema del uso compartido de memoria caché False Sharing:

Notebook problemas prog. concurrente

Propiedades de los programas concurrentes

Seguridad

• Exclusión mutua : Solo hay un proceso presente en una sección critica, aunque esto puede llegar a ser contraproducente al momento de la ejecución.
• No deadlock : Ningun proceso debe ser retrasado esperando un evento que nunca va a ocurrir.
• Correctitud parcial : Si el programa termina, la salida sera lo es requerido.

Vida

• Justicia : Un proceso que puede ser ejecutado, va a ser ejecutado.
• Comunicación confiable : Un mensaje enviado por un proceso sera recibido por otro.
• Correctitud completa : Cuando el programa termina, el resultado obtenido es el resultado requerido.

Sincronizacion

Cuando tenemos varios procesos o hilos en la ejecución, en muchos casos no queremos que estos se ejecuten al mismo tiempo. El mecanismo que controla el orden de ejecución de determinadas tareas lo llamamos SINCRONIZACION.

¿Por qué el algunos casos no queremos que los hilos se ejecuten al mismo tiempo?

porque se dan condiciones de carrera.

Condición de carrera

“Una condición de carrera es un comportamiento del software en el cual la salida depende del orden de ejecución de eventos que no se encuentran bajo control”

• Se da cuando uno o más hilos ejecutan secciones que otro hilo podría usar al mismo tiempo, y en estas modifica variables que podrían afectar la ejecución del resto de hilos.
• Se pueden producir cuando varios threads NO acceden en exclusión mutua a un recurso compartido.
• El nombre viene de la idea de dos procesos compiten en una carrera para acceder a un recurso compartido.
• Se convierte en un fallo siempre que el orden de ejecución no sea el esperado.

Problema del Lector - Escritor

Cuando tenemos varios lectores y escritores, por ejemplo, en un base de datos, muchos procesos van a intentar leer o escribir al mismo tiempo, lo cual no podemos permitir, ya que, nuestra informacion se podria perder, duplicar, corromper entre otros. Solo es posible que un proceso leo o escriba y que los demas esperen su turno.

Problema del Productor - Consumidor

Existen uno o más productores y uno o más consumidores, todos almacenan y extraen productos de una misma bodega. El productor produce productos cada vez que puede, y el consumidor los consume cada vez que lo necesita.

Problema:
¿Cómo coordinamos a los productores y consumidores, para que los productores no produzcan más ítems de los que se pueden almacenar en el momento, y los consumidores no adquieran más ítems de los que hay disponibles?.

Solucion:
Desde el punto de vista de la programación concurrente la solución a este problema se plantea a través de herramientas de sincronización. La primera solución y la más sencilla es implementar bodegas que sean excluyentes, es decir si un consumidor o productor se encuentra haciendo de la bodega, nadie más pueda hacerlo, indicando este estado con cualquier tipo de señal o aviso, implementado a través de semáforos binarios, cuyo concepto también es explicado en esta página.

La anterior solución aunque es funcional y completamente viable, no es del todo acertada, luego de profundizar en el enfoque de la programación concurrente se destaca que tiene fallos muy probables, debido a que puedo agregar más actores a este ambiente, y si solo uno de estos no aplica la metodología del semáforo de manera acertada la información se corromperá, además de contener un bloque de código igual en todos los consumidores y productores. Para solucionar esto se plantea una solución a través de un monitor el cual se encargará de revisar los procesos de compra y producción, eliminando así el código clonado, además de organizar los procesos desde el objeto de las bodegas en sí.

Punto Muerto e Interbloqueo

Se dice que un proceso está en punto muerto si se está esperando un evento que no ocurrirá. Un interbloqueo, por lo general, implica varios procesos y puede conducir a la terminación del programa. El interbloqueo puede ocurrir cuando los procesos se comunican (por ejemplo, dos procesos intentan enviarse mensajes entre sí de manera simultánea y sincrónica) pero es un problema más frecuentemente asociado con administración de recursos. En este contexto son necesarios cuatro condiciones para que exista un interbloqueo:

• Los procesos deben reclamar el acceso exclusivo a los recursos.
• Los procesos deben contener algunos recursos mientras esperan otros (es decir, adquirir recursos de forma fragmentaria).
• Los recursos no pueden eliminarse de los procesos en espera (sin preferencia).
• Existe una cadena circular de procesos en la que cada proceso tiene uno o más recursos requeridos por el siguiente proceso en la cadena.

Las técnicas para evitar (o recuperarse de) un punto muerto se basan en negar, al menos, una de estas condiciones. Una de las mejores técnicas (aunque poco prácticas) para evitar interbloqueos es el algoritmo del banquero de Dijkstra. Dijkstra también planteó lo que se ha convertido en un clásico ejemplo ilustrativo en este campo: el de los "filósofos gastronómicos".

Aplazamiento indefinido (o inanición o cierre patronal)

Se dice que un proceso se pospone indefinidamente si se retrasa esperando un evento que puede no ocurrir. Esta situación puede surgir cuando las solicitudes del recurso se administran utilizando un algoritmo que no hace provisión por el tiempo de espera de los procesos involucrados. Las técnicas para evitar el problema colocan procesos competitivos en un orden de prioridad tal que cuanto más tiempo espera un proceso, mayor es su se convierte en prioridad. Tratar los procesos estrictamente en su orden de demora es una solución más simple que es aplicable en muchas circunstancias. para una discusión de estas técnicas.

Injusticia

En general, se cree que cuando existe competencia entre procesos de igual estatus en un programa concurrente, se debe hacer algún intento para asegurar que los procesos en cuestión progresen uniformemente; es decir, para asegurar que no haya injusticia manifiesta al momento de satisfacer las necesidades de esos procesos. La equidad en un sistema concurrente se puede considerar tanto a nivel de diseño como de implementación del sistema. Para el diseñador es simplemente una pauta a observar al desarrollar un programa; cualquier descuido de la equidad puede conducir a un aplazamiento indefinido, dejando el programa incorrecto. Para un implementador del sistema es nuevamente una guía. La mayoría de los lenguajes de programación concurrentes no abordan la equidad. En cambio, el problema se deja en manos de los escritores del compilador y los desarrolladores del software de soporte en tiempo de ejecución

Ocupado Esperando

Independientemente del entorno en el que se desarrolle un programa concurrente ejecutado, rara vez es aceptable que cualquiera de sus procesos ejecute un bucle en espera de un cambio de estado del programa. Esto se conoce como "ocupado esperando". Las variables de estado involucradas constituyen un bloqueo de giro. No es en sí mismo un error, pero desperdicia energía del procesador, lo que a su vez puede conducir a la violación de un requisito de desempeño. Idealmente, la ejecución del proceso en cuestión debe suspenderse y continuar sólo cuando se cumple la condición para que progrese.

Errores transitorios

En presencia de no determinismo, las fallas en un programa concurrente pueden aparecer como errores transitorios; es decir, el error puede ocurrir o no dependiendo de la ruta de ejecución tomada en una activación particular del programa. La causa de un error transitorio tiende a ser difícil de identificar porque los eventos que lo preceden a menudo no se conocen precisamente y la fuente del error no puede, en general, ser encontrada por experimentación. Así, una de las habilidades en el diseño de cualquier programa concurrente es la habilidad de expresarlo en una forma que garantiza el comportamiento correcto del programa a pesar de cualquier incertidumbre sobre el orden en que se realizan algunas operaciones individuales. Eso es, no debe haber ninguna parte del programa cuyo comportamiento correcto depende del tiempo.

Sección Critica

Para solucionar estos inconvenientes hay que identificar las secciones de código en las que se pueden dar condiciones de carrera y permitir que solo un hilo entre a estas secciones a la vez. Podríamos pensar en un cruce de autos como una sección critica, en la que los autos que vayan en otro sentido no podrán ingresar al cruce hasta que los carros del carril que tiene el semáforo en verde (tienen permiso de entrar a la sección critica) terminen de pasar.

La cena de los filósofos

El problema de la cena de los filósofos es una de las analogías más populares usadas para explicar la concurrencia, sus problemas y acciones de mitigación. Existen n filósofos, n tenedores, y n platos de pasta en la mesa. Dicha pasta debe comerse con dos tenedores, por lo que en el caso inicial, no todos pueden comer a la vez. Entonces, los filósofos compiten por obtener los tenedores en un tiempo corto, porque de lo contrario morirán de hambre. Una vez un filósofo termina de comer, suelta ambos tenedores.

Si dos filósofos intentan tomar el mismo tenedor en un momento dado, estamos ante una condición de carrera.

Por otra parte, si todos los filósofos toman el tenedor que está a su derecha entonces todos se quedaran esperando infinitamente. Nadie va a ceder su tenedor porque todos están en la misma situación. Esta es la situación que puede abstraerse como un interbloqueo.

Como podemos hacer para que los filósofos no se mueran de hambre?. Interesante no, el problema en sí tiene muchas soluciones pero solo vamos a enunciar una: Un filosofo toma los dos tenedores y se los demás hacen una cola alrededor de la mesa para saber cual es el siguiente hasta que todos acaban.

¿Cómo atacar el problema de los filósofos?

• Round-robin: Es quizás la opción más intuitiva pero menos eficiente. Se implementa un sistema de turnos, y cada filósofo come cuando sea su turno propio. Idealmente, deben tener tiempo limitado por turno, porque de lo contrario, los últimos en esperar morirían de hambre. Puede pensarse como un carrusel.
  
  
• Cola de pensadores: Esta solución requiere de algo de detalle matemático y algorítmico. Cuando un filósofo toma un tenedor, espera un tiempo aleatorio para obtener el otro. Si no hay ninguno libre, suelta el primero, se lo entrega al primero de la cola y se va hacia atrás a esperar su turno nuevamente.
  
  
• Árbitro o moderador: Para lograr esta solución se necesita introducir a un actor nuevo, que no haga parte activa de la cena. Este actor -llamado árbitro o moderador- debe velar porque en cada escenario de n filósofos, sólo haya n-1 sentados en la mesa. De esta manera, se garantiza que al menos uno de los filósofos pueda terminar su comida. Cuando el primer filósofo haya terminado, se retirará del recinto e intercambiará lugares con quien estaba esperando.
  
  

Métodos de sincronización y comunicación

Existen diversas formas en las que podemos sincronizar y comunicar los hilos, entre ellas tenemos:

• Semáforos:
  • Un hilo adquiere permiso al entrar a la sección crítica, al finalizar la respectiva sección critica libera el permiso.
  • Está formado por una posición de memoria y dos instrucciones, una para reservarlo (wait o down) y otra para liberarlo (signal o up). A esto se le puede añadir una cola de threads para recordar el orden en que se hicieron la peticiones.
  • Soporte del SO para garantizar la exclusión mutua.
  • Sincronizar dos o más threads o procesos, de modo que su ejecución se realice de forma ordenada y sin conflictos entre ellos.
  • Es una solución con un bajo nivel de abstracción, por lo cual se debe implementar en todo el programa, y puede generar graves problemas de seguridad e implementación.
  
  
  
  

  EJEMPLO: (Solución posterior)
  
  Existen uno o más productores y uno o más consumidores, todos almacenan y extraen productos de una misma bodega. El productor produce productos cada vez que puede, y el consumidor los consume cada vez que lo necesita.
  
  Problema:
  
  ¿Cómo coordinamos a los productores y consumidores, para que los productores no produzcan más ítems de los que se pueden almacenar en el momento, y los consumidores no adquieran más ítems de los que hay disponibles?.
  
  Solución:
  Desde el punto de vista de la programación concurrente la solución a este problema se plantea a través de herramientas de sincronización. La primera solución y la más sencilla es implementar bodegas que sean excluyentes, es decir si un consumidor o productor se encuentra haciendo de la bodega, nadie más pueda hacerlo, indicando este estado con cualquier tipo de señal o aviso, implementado a través de semáforos binarios.
  
  

• Exclusión mutua:
  La exclusión mutua es una propiedad del control de concurrencia, cuyo proposito es evitar condiciones de carrera, es decir, que dos procesos no intenten acceder a un mismo recurso compartido al tiempo (sección crítica). Por ejemplo, un bloque de memoria.
  
  EJEMPLO:
  
  
  
  Se podría realizar una analogía con una breve historia: Alice y Bob comparte un patio, Alice tiene un gato y Bob un perro. Las mascotas no se llevan bien, por lo que nunca deberán estar en el patio juntas. La idea sería mirar el patio, ver si está vacío y, si lo está, liberar a la mascota. El cuidado sería que los dos dueños de las mascotas podrían mirar el patio al mismo tiempo. La comunicación explícita es requerida para poder coordinarse. El protocolo que se llevaría a cabo sería poner a utilizar llamadas para establecer comunicación, pero alguno de los dos puede estar ocupado y no responder. Es necesario hacer énfasis en que la comunicación debe ser persistente.
  
  Dentro de las posibles soluciones para este problema se tienen el uso de las variables compartidas, estas son leídas por todos pero escritas solo por un proceso en un instante de tiempo. También se podrían utilizar locks, que es una especie de bloqueo al recurso compartido, el proceso que posea el lock será el único que puede acceder a la sección crítica. La exclusión mutua no puede ser solucionada a través de comunicación transitiva ni interrupciones.


• Monitores:
  Cada hilo tiene un turno, todos los hilos deben esperar mientras el hilo que tenga el turno esté presente en la sección crítica. Aquí los métodos son ejecutados haciendo uso de exclusión mutua porque varios hilos de procesos van a querer ingresar en diferentes tiempos pero solo es permitido que ingrese uno y así pueda estar activo en el monitor en cierto instante de tiempo. Puesto a que es una implementación con un alto nivel de abstracción, ofrece más garantías con respecto a seguridad y tolerancia a fallos que otras implementaciones para planificar procesos.







• Mensajes:
  Los hilos se comunican y sincronizan por medio de mensajes, avisandole a los otros hilos cuando puede hacer sus respectivas ejecuciones sobre la sección crítica. Un mensaje suele tener dos partes. Una "cabecera" y el "cuerpo".
  La cabecera usualmente consta de los identificadores de los procesos emisor y receptor el tipo de mensaje y la longitud del mensaje.
  En el cuerpo se especifica la información adicional que se requiera.
  Para el paso de mensajes existen distintos tipos de direccionamiento.
  • Direccionamiento directo: EL proceso emisor especifica cual será el proceso receptor y de igual forma el proceso receptor conoce cual es el proceso emisor del mensaje.
  • Direccionamiento implícito: EL proceso emisor especifica cual será el proceso receptor, pero el proceso receptor no tiene información sobre el proceso emisor.
  • Direccionamiento indirecto: En este caso los mensajes no se envían directamente al receptor, sino que se envían a una estructura de datos denominada buzón o mailbox.
    En este caso, los procesos que deban entrar en una sección critica deberán leer el buzón para conocer si dicha sección se encuentra habilitad o no.
• Aspectos a tener en cuenta en el paso de mensajes
  
  • Buzones: Existen dos casos al trabajar con buzones, en el primero el proceso es el propietario. Para el segundo caso el Sistema Operativo es el responsable del buzón.
  • Sincronización de los mensajes: Es necesario identificar en que secciones criticas es necesario aplicar envio bloqueante y recepción bloqueante o una combinación de estas ya que una mala implementación de paso de mensajes puede terminar en una nueva condición de carrera.

como ejemplo supongamos que en 2 o más bancos se hacen transacciones sobre una misma cuenta, si en uno de los bancos (un hilo) cambia el valor de la cuenta mientras en otro banco se realiza una transacción sobre la misma se daría una condición de carrera, para evitar esto usaremos los múltiples métodos de sincronización:

Ejemplo en java de semaforos:

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;
import java.util.concurrent.Semaphore;
import java.util.logging.Level;
import java.util.logging.Logger;

//la clase extiende de thread
public class Banco2 extends Thread{
    static int cuenta=0;
    int Operaciones;
    int [] transaccion;
    final Semaphore available = new Semaphore(1, true);
    boolean[] used = new boolean[1];

    public Banco2(int Operaciones, int[] transaccion) {
        this.Operaciones = Operaciones;
        this.transaccion = transaccion;
    }




    //se sobreescribe el metodo run, que es el que correra al momento de iniciar los hilos
    @Override
    public void run()  {
        try {
        //el hilo adquiere permiso para entrar a la seccion critica
        available.acquire();
        for(int i=0;i< this.Operaciones;i++){
           int temp=cuenta;
                temp=temp+this.transaccion[i];
                cuenta=temp;
            }
        //el hilo libera el permiso
        available.release();
         } catch (InterruptedException ex) {
                Logger.getLogger(Banco2.class.getName()).log(Level.SEVERE, null, ex);
        }


    }
    public static void main(String[] args) throws InterruptedException {
         Scanner sc;

        try {
            //se recibe un archivo con operaciones de entrada y se guardan en arreglos
            sc = new Scanner(new FileReader("C:/archivo3.txt"));
            int A=sc.nextInt();
            int B=sc.nextInt();
            int [] arregloA= new int[A];
            int [] arregloB= new int[B];
            for (int i=0;i< A;i++){
                arregloA[i]=sc.nextInt();
            }
            for (int i=0;i< B;i++){
                arregloB[i]=sc.nextInt();
            }
            Banco2 a=new Banco2(A,arregloA);
            Banco2 b=new Banco2(B,arregloB);
            //se crean los hilos asociados a cada instancia de la clase
            a.start();
            b.start();
            //join de los hilos con el hilo principal de ejecucion
            a.join();
            b.join();
            System.out.println(cuenta);
    }catch (FileNotFoundException ex) {
            Logger.getLogger(Banco2.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

}

Ejemplo en java de monitores:

  import java.io.FileNotFoundException;
  import java.io.FileReader;
  import java.util.Scanner;
  import java.util.logging.Level;
  import java.util.logging.Logger;

  //igual extiende de la clase hilo
  public class Banco3 extends Thread{
      static int cuenta=0;
      int Operaciones;
      int [] transaccion;
      //usamos turnos para saber cual hilo debe ejecutarse
      static boolean turno = true;

      public Banco3(int Operaciones, int[] transaccion) {
          this.Operaciones = Operaciones;
          this.transaccion = transaccion;
      }

      public synchronized void Operar() throws InterruptedException{
          //mientras el turno no este disponible el hilo espera
          while(!turno) {
              wait();
          }
          //si el turno esta disponible, se toma, poniéndolo como false para el resto
          //de hilos
          turno=false;
          for(int i=0;i< this.Operaciones;i++){
                  int temp=cuenta;
                  temp=temp+this.transaccion[i];
                  cuenta=temp;

          }
          //el turno se libera y se le notifica a los hilos que estaban en espera
          turno=true;
          notifyAll();
      }
      @Override
      public void run()  {
          try {
              Operar();
          } catch (InterruptedException ex) {
              Logger.getLogger(Banco3.class.getName()).log(Level.SEVERE, null, ex);
          }
      }
      public static void main(String[] args) throws InterruptedException {
           Scanner sc;

          try {
              sc = new Scanner(new FileReader("C:/archivo3.txt"));
              int A=sc.nextInt();
              int B=sc.nextInt();
              int [] arregloA= new int[A];
              int [] arregloB= new int[B];
              for (int i=0;i< A;i++){
                  arregloA[i]=sc.nextInt();
              }
              for (int i=0;i< B;i++){
                  arregloB[i]=sc.nextInt();
              }
              Banco3 a=new Banco3(A,arregloA);
              Banco3 b=new Banco3(B,arregloB);
              a.start();
              b.start();
              a.join();
              b.join();
              System.out.println(cuenta);
      }catch (FileNotFoundException ex) {
              Logger.getLogger(Banco3.class.getName()).log(Level.SEVERE, null, ex);
          }
      }

  }

Ejemplo en java de mensajes (es necesario usar el toolkit de akka):

  import akka.actor.UntypedActor;
  //extiende de un actor de la toolkit de akka
public class BankActor extends UntypedActor{
    static public int cuenta=0;
    //los actores se comunican entre si, se sobreescribe el metodo
    //de onReceive que se ejecuta cuando un hilo recibe mensajes de otro hilo
    @Override
    public void onReceive(Object message) throws Exception {
        if(message instanceof Integer) {
            int a= new Integer((int) message);
            int temp=cuenta;
            temp=temp+a;
            cuenta=temp;
        }else{
            //se tiene en cuenta si el actor no puede comprender el mensaje que se le envio
            unhandled(message);
        }
    }
}


import akka.actor.ActorRef;
import akka.actor.ActorSystem;
import akka.actor.Props;
import java.util.Scanner;


public class Akka {

    public static void main(String[] args) {
        //se instancia un sistema de comunicacion entre los actores
        ActorSystem system=ActorSystem.create("Transacciones");
        //se instancian los dos actores
        ActorRef bankActor = system.actorOf(new Props(BankActor.class), "Transaccion1");
        ActorRef bankActor2 = system.actorOf(new Props(BankActor.class), "Transaccion2");
        Scanner sc2 = new Scanner(System.in);
        int A = sc2.nextInt();
        int B = sc2.nextInt();
        int [] arregloA= new int[A];
        int [] arregloB= new int[B];
        int mayor=0;
        if (A< B){mayor=B;}
        else {mayor=A;}
        for (int i=0;i< mayor;i++){
            //los actores se comunican entre si las transacciones que van haciendo
            if (i< A){
                arregloA[i]=sc2.nextInt();
                bankActor.tell(arregloA[i],null);
            }
            if (i< B){
                arregloB[i]=sc2.nextInt();
            bankActor2.tell(arregloB[i],null);
            }
        }
        system.shutdown(); //cierra la comunicacion
        system.awaitTermination();//join con el hilo principal
        System.out.println(BankActor.cuenta);
    }
}

• Solucion del problema Productor - Consumidor

- Con semaforos

semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;

procedure producer() {
  while (true) {
    item = produceItem();
    down(emptyCount);
    putItemIntoBuffer(item);
    up(fillCount);
  }
}

procedure consumer() {
  while (true) {
    down(fillCount);
    item = removeItemFromBuffer();
    up(emptyCount);
    consumeItem(item);
  }
}

- Con monitores

monitor ProducerConsumer {
  int itemCount;
  condition full;
  condition empty;

  procedure add(item) {
    while (itemCount == BUFFER_SIZE) {
        wait(full);
    }
    putItemIntoBuffer(item);
    itemCount = itemCount + 1;
    if (itemCount == 1) {
        notify(empty);
    }
  }

  rocedure remove() {
      while (itemCount == 0) {
          wait(empty);
      }

      item = removeItemFromBuffer();
      itemCount = itemCount - 1;

      if (itemCount == BUFFER_SIZE - 1) {
          notify(full);
      }
      return item;
  }
}

procedure producer() {
    while (true) {
        item = produceItem()
        ProducerConsumer.add(item)
    }
}

procedure consumer() {
    while (true) {
        item = ProducerConsumer.remove()
        consumeItem(item)
    }
}

Los métodos de sincronización y comunicación se explican de mejor forma mediante el uso del notebook, pues los temas se explican con el uso python y C++.

Notebook

Herramientas de verificación de sistemas concurrentes

Redes de Petri

CSP (Communicating Sequential Processes)

FDR (Failures-Divergence Refinement)

JCSP (Java communicating sequential processes)

Aplicaciones del paradigma

En la cotidianeidad encontramos muchos ejemplos de concurrencia y paralelismo en múltiples procesos con los que interactuamos continuamente. De ellos podemos abstraer características propias que los identifican, así como las partes que los conforman, con el fin de tratar de entender y modelarlos en un entorno virtual.

El mundo real contiene actores que ejecutan acciones independientemente, pero que se comunican entre sí al realizarlas. Es por esto que, al modelar el mundo, se deben componer y coordinar muchas ejecuciones paralelas.

• Redes ferroviarias
• El cuerpo humano y sus diferentes sistemas
• Sistemas de ensamblaje dentro de fábricas
• Equipos de desarrollo de software

Entre muchas otras acciones cotidianas que deben de coordinar distintos procesos para poder ser cumplidas con éxito y funcionar de manera óptima.

La concurrencia y el paralelismo nos brindan bastantes herramientas para que la modelación de dichos procesos se realice de manera más apegada a la realidad y, así mismo, para encontrar formas de que estos procesos sean más eficientes al poder separarlos y distribuirlos en pequeños subprocesos que los conformen y se ejecuten en paralelo, es decir, de una manera ligeramente más natural que una ejecución secuencial.

Concurrencia en Software

La concurrencia y el paralelismo son ampliamente utilizados en distintos enfoques y formas de software, al punto en que constantemente utilizamos programas o escribimos código sin saber que muchos de estos procesos están paralelizados para brindar una mejor experiencia al usuario. Algunos ejemplos de la utilización de concurrencia y paralelismo en ciertos softwares y sistemas son:

• Multiprogramming

  Dentro de un sistema operativo se pueden ejecutar muchos programas y/o procesos al mismo tiempo y compartiendo la misma memoria. Esto se logra al descomponerlos en subprocesos asignados a distintos núcleos dentro de un procesador.

  
  
  
  
  
  • Descargas
  • Transmisión de datos
  • Lectura de archivos
  • Conexión a internet
  • Manejo de drivers de audio y video
• 
  
  

  Muchos algoritmos se pueden dividir en partes concurrentes

  • Mergesort
  • Quicksort
  • Sumar una lista sumando fragmentos en paralelo
  • Cálculo de números primos
  • Comprobación de la igualdad de las secuencias de hojas en los árboles

  

• Motores de videojuegos

  Los motores que soportan la ejecución de videojuegos deben realizar distintos subprocesos que, orquestados correctamente, componen la experiencia del jugador, como lo son:

  
  • Game logic
  • Físicas
  • IA
  • Gráficos
  • Inputs del jugador
  • Música y sonido

Otros ejemplos puntuales son:

• Manejo de eventos asincrónicos como la llegada de paquetes de red
• Ocultar la latencia, mostrando resultados de carga paulatinamente
• Manejo de redes con múltiples equipos
• Simulación de eventos complejos
• Servidores web
• Sistema multimedia
• Cálculo numérico
• Interacción por GUI
• Sistemas gestores de bases de datos
• Sistemas Operativos
• Sistemas de control
• Simulación
• Videojuegos