Sincronización y Comunicación entre Procesos: Una Mirada en Profundidad

Conceptos Fundamentales

La sincronización entre procesos se refiere al ordenamiento temporal de las operaciones, crucial para evitar condiciones de carrera. Su objetivo principal es permitir que un proceso continúe su ejecución solo después de que ocurra un evento específico.

La comunicación entre procesos, por otro lado, implica el intercambio de datos. Esta comunicación facilita la cooperación entre procesos para lograr un objetivo común.

Problemas de Concurrencia

• Programas secuenciales: Definen una secuencia de instrucciones ejecutadas en un procesador (proceso o tarea). No dependen de otros procesos ni del algoritmo de planificación.
• Programas concurrentes: Especifican dos o más procesos secuenciales que pueden ejecutarse simultáneamente. Requieren mecanismos de sincronización y comunicación.
• Exclusión Mutua: Asegura que los recursos críticos sean accedidos por un solo proceso a la vez. Es un problema clave en la ejecución concurrente.

Grafos de Precedencia y Condiciones de Bernstein

Grafos de precedencia: Son grafos sin ciclos donde cada nodo representa una sentencia o un conjunto de instrucciones secuenciales.

Condiciones de Concurrencia de Bernstein: Son condiciones que deben cumplir dos o más procesos para ser considerados concurrentes. Se basan en los conjuntos de Lectura (R(Si)) y Escritura (W(Si)) de las sentencias:

1. R(Si) ∩ W(Sj) = ∅
2. W(Si) ∩ R(Sj) = ∅
3. W(Si) ∩ W(Sj) = ∅

Si estas tres condiciones resultan en el conjunto vacío, se puede asegurar que no hay dependencia entre las sentencias y pueden ejecutarse concurrentemente.

Especificaciones Concurrentes

• Instrucciones FORK: Indican el inicio de la concurrencia, creando e iniciando dos instrucciones concurrentes.
• Instrucciones JOIN: Recombinan la concurrencia en una sola instrucción, indicando la finalización de la concurrencia.
• COBEGIN/COEND: Permiten que todas las instrucciones entre ellas se ejecuten concurrentemente.
• Implementación:
  • COBEGIN/COEND deben ser construcciones del lenguaje de programación.
  • FORK puede implementarse mediante llamadas al sistema (syscall).
  • El proceso creador se denomina «padre».
  • El proceso creado se denomina «hijo», y puede crear otros hijos.
  • Los nuevos procesos pueden obtener recursos del sistema operativo o compartirlos con el padre.
  • El padre puede ejecutar concurrentemente con el hijo o esperar a que termine.

Relaciones y Conflictos entre Procesos Concurrentes

• Proceso independiente: No afecta ni es afectado por otros procesos. Su ejecución es determinista.
• Proceso interactuante: Puede afectar o ser afectado por otros procesos. Su ejecución no es predecible.
• Condición de Carrera (Race Condition): El resultado de la ejecución depende del orden de ejecución de los procesos interactuantes.

Para resolver las condiciones de carrera, se necesita la exclusión mutua, que garantiza que solo un proceso utilice un recurso compartido a la vez.

Otros conflictos relacionados con el uso de recursos incluyen:

• Inanición (Starvation): Uno o varios procesos nunca reciben suficiente tiempo de ejecución.
• Espera Circular: Varios procesos forman una cadena de espera que los involucra a todos.
• No Expropiación: Un recurso asignado a un proceso no puede ser arrebatado.
• Espera Ocupada: Un proceso gasta tiempo verificando si un recurso fue liberado.
• Exclusión Mutua (Región Crítica): Solo un proceso puede estar dentro de la sección de código que accede a un recurso compartido (región crítica).
• Ocupar y Esperar: Un proceso pide un recurso, lo obtiene y, antes de liberarlo, pide otro recurso que ya está asignado.

Responsabilidades del Sistema Operativo

1. Rastrear los procesos activos.
2. Asignar y liberar recursos (tiempo de CPU, memoria, archivos, dispositivos de E/S).
3. Proteger los datos y recursos de cada proceso.

Ventajas y Desventajas de la Concurrencia

Ventajas:

1. Evita tiempos muertos del procesador.
2. Comparte y optimiza el uso de recursos.
3. Permite la modularidad.
4. Acelera los cálculos.
5. Mayor comodidad.

Desventajas:

1. Inanición e interrupción de procesos.
2. Interbloqueos (deadlocks).
3. Complejidad en el tratamiento de recursos no apropiativos.

El Problema de la Región Crítica

• Región Crítica: Es una sección de código donde un proceso accede a un recurso compartido para modificarlo. Se ejecuta de forma exclusiva.

Definición de Wikipedia: En programación concurrente, una sección crítica es la parte del código donde se accede a un recurso compartido que no debe ser accedido por más de un proceso o hilo.

Propiedades para el Uso de la Región Crítica:

1. Exclusión Mutua: Solo un proceso a la vez puede ejecutar su región crítica.
2. Progreso: Un proceso fuera de su región crítica no debe impedir que otros entren.
3. Espera Limitada: Un proceso debe poder entrar a la región crítica después de un número limitado de intentos.
4. Abandono: Debe salir de la región crítica en un tiempo finito.
5. Penalidad: No debe consumir tiempo de ejecución mientras espera.
6. Privilegio: Ningún proceso debe monopolizar la región crítica.

Algoritmos de Sincronización con Espera Activa

La espera activa implica que el proceso sigue ocupando la CPU mientras no puede entrar a su región crítica (no se bloquea).

1. Solución Simple: Usa un flag. Si el flag es cero, lo pone en uno y entra a la región crítica; si es uno, espera.
2. Espera Ocupada por Turnos: Usa una variable global «turno». Exige alternancia estricta.
3. Solución de Peterson: Similar a la alternancia, pero agrega un vector de flags para indicar el interés en entrar a la región crítica.
4. Algoritmo de Dekker: Algoritmo para la exclusión mutua de dos procesos, utilizando dos variables booleanas y una variable extra para indicar el turno.
5. Algoritmo de Lamport (Panadería): Usa un sistema de «toma de turno».
6. Mecanismos de Hardware:
   • Deshabilitar Interrupciones: Impide que un proceso sea interrumpido. No funciona en multiprocesadores.
   • Instrucciones Especiales del Procesador:
     • Test-and-Set (TAS o TSL): Examina un valor; si es cero, lo cambia a uno y devuelve verdadero. Puede causar inanición y deadlock.
     • Compare-and-Swap (CAS): Intercambia el contenido de un registro con una posición de memoria.
7. Cola de Espera: Provee un ordenamiento explícito en el uso de la región crítica. Los procesos que no pueden entrar se colocan en una cola.

Semáforos

Un semáforo es una herramienta genérica para la sincronización de procesos. Es una variable protegida que solo puede ser accedida y alterada por las operaciones atómicas down() (P) y up() (V), y una operación de inicialización.

Tipos de Semáforos:

• Binarios: Pueden tomar valores 0 y 1.
• Mutex: Pueden tomar valores 1, 0 y negativos.
• Contadores (Generales): Pueden tomar valores enteros no negativos, cero y negativos.

Algoritmos sin Espera Activa

• Semáforos sin Espera Activa: Utilizan una estructura con una variable para el valor del semáforo y una cola de procesos asociada.

Comunicación entre Procesos (IPC)

• Mensaje: Porción de datos con un encabezado (identificación del emisor, receptor, longitud, tipo) y un cuerpo (contenido). Se usan las primitivas send y receive.
• Comunicación Directa: Los procesos envían y reciben mensajes entre sí. Requiere que los procesos se conozcan.
• Comunicación Indirecta: Los mensajes se envían a un buzón (mailbox). Los procesos comparten un buzón para comunicarse.
• Comunicación Sincrónica: El emisor se bloquea hasta que el receptor esté listo.
• Comunicación Asincrónica: Los procesos no se bloquean.
• Comunicación Semi-Sincrónica: Usa un send no bloqueante y un receive bloqueante.
• Modelo Productor-Consumidor: Describe dos procesos concurrentes:
  • Productor: Genera datos.
  • Consumidor: Utiliza los datos generados por el productor.

Protocolo de Sincronización Productor-Consumidor:

• Si el productor intenta poner un elemento en un buffer lleno, se demora hasta que el consumidor saque uno.
• Si el consumidor intenta tomar un mensaje de un buffer vacío, se demora hasta que el productor ingrese uno.

Algoritmos para el Modelo Productor-Consumidor:

1. Con sleep() y wakeup(): Usa una variable para contar los lugares ocupados en el buffer. Puede presentar condiciones de carrera.
2. Con contadores de eventos: Usa variables especiales con operaciones atómicas (read, advance, await).
3. Con semáforos: Usa tres semáforos (mutex, vacío, lleno).

Deadlocks (Interbloqueos)

Un deadlock es un estado en el que dos o más procesos esperan por condiciones que nunca se cumplirán, causadas por los propios procesos del conjunto. Es un bloqueo permanente.

Causas de Deadlock:

• Petición de Recursos: Un proceso solicita un recurso no disponible y queda esperando.
• Comunicación entre Procesos: Los procesos esperan mensajes de otros miembros del grupo, y no hay mensajes en tránsito.

Tipos de Recursos:

• Reutilizables: Pueden ser usados por un proceso y no se agotan (canales de E/S, memoria).
• Consumibles: Se crean y se destruyen (interrupciones, señales, mensajes).

Condiciones Necesarias y Suficientes para un Deadlock:

• Exclusión Mutua: Los recursos no son compartibles.
• Retener y Esperar: Un proceso retiene recursos mientras espera por otros.
• No Expropiación: Los recursos solo pueden ser liberados voluntariamente por el proceso.
• Espera Circular: Existe una cadena circular de procesos esperando recursos.

Grafos de Asignación de Recursos: Representan la asignación y solicitud de recursos mediante vértices (procesos y recursos) y arcos.

Estrategias para Tratar Deadlocks

• Ignorarlo: La estrategia más simple, usada cuando la frecuencia de deadlocks es baja.
• Prevenirlo: Imponer restricciones para evitar que ocurra alguna de las cuatro condiciones:
  • Exclusión Mutua: Permitir que un proceso no espere si un recurso no está disponible.
  • Retener y Esperar: Solicitar todos los recursos al inicio o liberar los recursos antes de solicitar otros.
  • No Expropiación: Liberar todos los recursos si se solicita uno no disponible, o permitir que el sistema operativo expropie recursos.
  • Espera Circular: Imponer un orden lineal de ejecución.
• Detectar y Recuperar: Abortar procesos o usar puntos de control (checkpoints) para recuperarse de un deadlock. Implica overhead. Métodos:
  • Abortar todos los procesos involucrados.
  • Retroceder los procesos a un punto de control.
  • Abortar procesos uno por uno.
  • Quitar recursos a un proceso y entregárselos a otro.

Etiquetas: comunicación entre procesos, Concurrencia, condiciones de Bernstein, deadlocks, exclusión mutua, región crítica, sincronización de procesos