PROCESOS CONCURRENTES

LOS CLÁSICOS PROBLEMAS DE LA SINCRONIZACIÓN DE PROCESOS.

El del fumador de cigarros: Considere un sistema con tres procesos fumadores y un proceso agente. Cada fumador está continuamente enrollando y fumando cigarrillos. Sin embargo, para enrollar y fumar un cigarrillo, el fumador necesita tres ingredientes: tabaco, papel, y fósforos. Uno de los procesos fumadores tiene papel, otro tiene el tabaco y el tercero los fósforos. El agente tiene una cantidad infinita de los tres materiales. El agente coloca dos de los ingredientes sobre la mesa. El fumador que tiene el ingrediente restante enrolla un cigarrillo y se lo fuma, avisando al agente cuando termina. Entonces, el agente coloca dos de los tres ingredientes y se repite el ciclo.

La panadería de Lamport: En este problema una panadería tiene una variedad de panes y pasteles vendidos por n vendedores. Cada uno de los cuales toma un número al entrar. El cliente espera hasta oír su número. Cuando el vendedor se desocupa, llama al siguiente numero.

Los filósofos que cenan (sabios): Hay cinco filósofos chinos que se pasan sus vidas pensando y comiendo. Comparten una mesa circular, alrededor de la cual se sientan. En su centro se encuentra con una provisión infinita de arroz, y sobre ella hay cinco palitos, uno de cada lado de los filósofos. Cuando un filósofo piensa, no interactúa con sus colegas. De vez en cuando, un filósofo tiene hambre y trata de levantar los dos palitos más cercanos a él. Un filósofo puede levantar un palito a la vez, y no puede tomar un palito que ya está en la mano de un vecino. Cuando un filósofo tiene ambos palitos, puede comer. Cuando termino de hacerlo, deja sus dos palitos y comienza a pensar de nuevo.

El barbero dormilón: Una peluquería tiene un barbero, una silla de peluquero y n sillas para que se sienten los clientes en espera, si es que los hay. Si no hay clientes presentes, el barbero se sienta en su silla de peluquero y se duerme. Cuando llega un cliente, este debe despertar al barbero dormilón. Si llegan más clientes mientras el barbero corta el cabello de un cliente, estos deben esperar sentados (si hay sillas desocupadas) o salirse de la peluquería (si todas las sillas están ocupadas). El problema consiste en programar al barbero y los clientes sin entrar en condición de competencia.

Lectores y escritores: Imaginemos una enorme base de datos, como por ejemplo un sistema de reservaciones de en una línea aérea, con muchos procesos en competencia, que intentan leer y escribir en ella. Se puede aceptar que varios procesos lean la base de datos al mismo tiempo, pero si uno de los procesos está escribiendo, (es decir modificando) la base de datos, ninguno de los demás procesos deberá tener acceso a esta, ni siquiera los lectores. El problema es como programar a los lectores y escritores.

Productor/Consumidor: También conocido como bounded buffer problem o problema del buffer limitado. Dos procesos comparten un almacén (buffer) de tamaño fijo. Uno de ellos, el productor, coloca información en el almacén (buffer) mientras que el otro, el consumidor, la obtiene de él. Si el productor desea colocar un nuevo elemento, y el almacén se encuentra lleno, este deberá irse a \dormir". El consumidor despertara al productor cuando elimine un elemento del almacén. De forma análoga, si el almacén esta vació y el consumidor desea eliminar un elemento del almacén, este debe \dormirse" hasta que el productor coloque algo en el almacén.


EXCLUSIÓN MUTUA.

Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusión) se usan en programación concurrente para evitar que fragmentos de código conocidos como secciones críticas accedan al mismo tiempo a recursos que no deben ser compartidos.
a mayor parte de estos recursos son las señales, contadores, colas y otros datos que se emplean en la comunicación entre el código que se ejecuta cuando se da servicio a una interrupción y el código que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupción puede ocurrir entre dos instrucciones cualesquiera del código normal y esto puede provocar graves fallos.
La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.
En un sistema multiprocesador de memoria compartida, se usa la operación indivisible test-and-set sobre una bandera, para esperar hasta que el otro procesador la despeje. La operación test-and-set realiza ambas operaciones sin liberar el bus de memoria a otro procesador. Así, cuando el código deja la sección crítica, se despeja la bandera. Esto se conoce como spin lock o espera activa.
La mayoría de los métodos de exclusión mutua clásicos intentan reducir la latencia y espera activa mediante las colas y cambios de contexto. Algunos investigadores afirman que las pruebas indican que estos algoritmos especiales pierden más tiempo del que ahorran.
A pesar de todo lo dicho, muchas técnicas de exclusión mutua tienen efectos colaterales. Por ejemplo, los semáforos permiten interbloqueos (deadlocks) en los que un proceso obtiene un semáforo, otro proceso obtiene el semáforo y ambos se quedan a la espera de que el otro proceso libere el semáforo. Otros efectos comunes incluyen la inanición, en el cual un proceso esencial no se ejecuta durante el tiempo deseado, y la inversión de prioridades, en el que una tarea de prioridad elevada espera por otra tarea de menor prioridad, así como la latencia alta en la que la respuesta a las interrupciones no es inmediata.

SECCIÓN CRÍTICA.

En programación concurrente, se define como a la porción de código de un programa de computador el cual accede a un recurso compartido (estructura de datos ó dispositivo) que no debe de ser accedido por mas de un hilo en ejecución (thread). La sección crítica por lo general termina en un tiempo determinado y el hilo, proceso ó tarea solo tendrá que esperar un período determinado de tiempo para entrar. Se necesita de un mecanismo de sincronización en la entrada y salida de la sección crítica para asegurar la utilización exclusiva del recurso, por ejemplo un semáforo.
El acceso concurrente se controla teniendo cuidado de las variables que se modifican dentro y fuera de la sección crítica. La sección crítica se utiliza por lo general cuando un programa multihilo actualiza múltiples variables sin un hilo de ejecución separado que lleve los cambios conflictivos a esos datos. Una situación similar, la sección crítica puede ser utilizada para asegurarse de que un recurso compartido, por ejemplo, una impresora, puede ser accedida por un solo proceso a la vez.
La manera en como se implementan las secciones puede variar dependiendo de los diversos sistemas operativos.
Sólo un proceso puede estar en una sección crítica a la vez.

Modelo de sección crítica.

El modelo de sección crítica que vamos a utilizar sigue el siguiente protocolo genérico:
Entrar_SC(esta_SC) /* Solicitud de ejecutar esta_SC */
/* código de esta_SC */
Dejar_SC(esta_SC) /* Otro proceso puede ejecutar esta_SC */
Es decir, cuando un proceso quiere entrar a la sección crítica:
(1) ejecuta Entrar_SC(), y si la sección crítica está ocupada el proceso espera;
(2) ejecuta la sección crítica;
(3) ejecuta Dejar_SC(), permitiendo que entre uno de los procesos en espera.
La decisión de qué proceso es el seleccionado para entrar en el paso (3) puede tener consecuencias importantes, como se comentará más adelante. En general, puede asumirse disciplina FIFO.
Un aspecto fundamental es cómo se realiza la espera en Entrar_SC(), lo que determina el tipo de mecanismo de sincronización que se debe utilizar. Esto dependerá del tiempo que el proceso deba esperar para entrar a la sección crítica. La Figura C muestra un ejemplo de utilización de una sección crítica para implementar sincronización productor-consumidor. Hay que advertir que este ejemplo sólo es válido para un productor y un consumidor. Con n productores y m consumidores se producirían condiciones de carrera. Se propone como ejercicio la modificación de este código para el caso general.