Semáforos en sistemas concurrentes

Sincronización en Memoria Compartida

• Se exploran soluciones de exclusión mutua y sincronización basadas en el uso de memoria compartida entre procesos.
• Estas soluciones se dividen en:
  • Soluciones de bajo nivel con espera ocupada, basadas en instrucciones de lectura/escritura directa y bucles de espera.
  • Soluciones de alto nivel, con una capa de software que ofrece una interfaz y bloquea procesos en espera.

Soluciones de Bajo Nivel con Espera Ocupada

• Un proceso en espera entra en un bucle indefinido revisando continuamente si una condición se cumple.
• Se clasifican en:
  • Soluciones Software: Operaciones de lectura/escritura de datos simples en memoria compartida.
  • Soluciones Hardware (cerrojos): Instrucciones de máquina específicas dentro del repertorio de los procesadores.

Soluciones de Alto Nivel

• Las soluciones de bajo nivel son propensas a errores, generan algoritmos complejos y afectan al rendimiento de la CPU.
• Las soluciones de alto nivel incluyen:
  • Semáforos: Construidos sobre soluciones de bajo nivel, utilizan servicios del SO para bloquear y reactivar procesos.
  • Regiones críticas condicionales: Soluciones de nivel superior a los semáforos, implementables sobre estos.
  • Monitores: Soluciones de alto nivel implementables en lenguajes orientados a objetos (Java, Python).

Estructura de los Procesos con Secciones Críticas

• Un proceso con una sección crítica (SC) se estructura en tres etapas:
  • Protocolo de Entrada (PE): Instrucciones incluyendo posibles esperas para acceder a la SC.
  • Sección Crítica (SC): Instrucciones ejecutadas por un solo proceso a la vez.
  • Protocolo de Salida (PS): Instrucciones que permiten a otros procesos saber que la SC está libre.
• Las sentencias fuera de estas etapas se denominan Resto de Sentencias (RS).

Acceso Repetitivo a las Secciones Críticas

• Se simplifica el análisis asumiendo que cada proceso tiene una única SC contigua y se ejecuta en un bucle infinito con dos pasos: SC (con PE y PS) y RS.
• El proceso puede finalizar en la sección RS.

Diagrama de Estados de un Proceso

• Un proceso pasa por los estados de Protocolo de Entrada, Sección Crítica, Protocolo de Salida y Resto de Sentencias.
• Solo se puede terminar en Resto de Sentencias.
• En el Protocolo de Entrada se introducen esperas para garantizar la exclusión mutua en la Sección Crítica.

Comportamiento de los Procesos

• Para implementar soluciones correctas, se asume que los procesos terminan su sección crítica en un tiempo finito.
• Durante la sección crítica, un proceso no debe finalizar, abortar, entrar en bucle infinito o ser bloqueado externamente.
• Se busca minimizar el tiempo en SC.

Propiedades para Exclusión Mutua

• Un algoritmo de Exclusión Mutua debe ser correcto cumpliendo tres propiedades mínimas:
  • Exclusión mutua: Un solo proceso puede ejecutar una sentencia de la SC en un momento dado.
  • Progreso: Si ningún proceso está en la SC, y algunos compiten, uno debe poder acceder en un tiempo finito
  • Espera limitada: Un proceso tiene un límite máximo en el número de veces que otros procesos pueden entrar a la SC mientras espera.
• Además, se valoran propiedades deseables como eficiencia y equidad.

Refinamiento Sucesivo de Dijkstra

• Es una serie de algoritmos que resuelven el problema de la exclusión mutua.
• Comienza con una versión simple incorrecta y realiza mejoras sucesivas. La versión final correcta es el Algoritmo de Dekker.
• Se asumen dos procesos (P0 y P1) ejecutando un bucle infinito con PE, SC, PS y otras sentencias.

Algoritmo de Dekker

• Es un algoritmo correcto para la exclusión mutua y es el resultado del refinamiento sucesivo de Djikstra.
• Cada proceso incluye una espera de cortesía si ambos coinciden en el PE.
• Para evitar interbloqueos, la espera de cortesía la realiza un proceso de forma alterna.
• Un variable permite determinar el fin de la espera de cortesía.

Algoritmo de Peterson

• Es un algoritmo correcto para exclusión mutua y más simple que el de Dekker.
• Utiliza variables lógicas que expresan la presencia en el PE o SC, más una variable de turno para resolver el interbloqueo.
• Se asigna a la variable de turno al inicio del PE dando preferencia al primer proceso en llegar.
• A diferencia de Dekker, el PE usa un solo bucle en lugar de bucles anidados.

Soluciones Hardware con Espera Ocupada (Cerrojos)

• Los cerrojos son una solución hardware para la exclusión mutua y la sincronización, basada en espera ocupada.
• La espera ocupada es un bucle ejecutado hasta que ningún otro proceso esté en la sección crítica.
• Un valor lógico compartido (cerrojo) indica si un proceso está en la SC. El cerrojo se actualiza en el protocolo de salida.
• Se requiere de instrucciones hardware especificas.

La Instrucción TestAndSet

• Instrucción máquina atómica (indivisible) disponible en algunos procesadores.
• Admite la dirección de memoria de una variable lógica como cerrojo.
• Lee el valor anterior del cerrojo, lo pone a true y devuelve el valor anterior, todo de forma atómica.

Desventajas de los Cerrojos

• Las esperas consumen tiempo de CPU.
• El acceso directo a los cerrojos puede llevar a errores.
• No garantizan equidad.

Uso de los Cerrojos

• Se usan restringidamente en componentes de software del sistema operativo o librerías de tiempo real.
• La ejecución de la SC debe llevar un intervalo corto de tiempo ya que las esperas ocupadas son cortas y la CPU no se desaprovecha tanto.

Semáforos para Sincronización

• Solucionan o aminoran los problemas de soluciones de bajo nivel y tienen un uso más amplio.
• No se utiliza espera ocupada, si no bloqueo de procesos utilizando la CPU de forma mucho mas eficiente.
• Resuelven el problema de exclusión mutua de forma sencilla utilizando esquemas sencillos.
• Un estructura de datos a las se accede únicamente mediante subprogramas específicos mejorando la seguridad de los programas.

Bloqueo y Desbloqueo de Procesos

• Los semáforos exigen que los procesos bloqueados no ocupen la CPU.
• Un proceso elige quedarse bloqueado.
• Un proceso en ejecución elige que se desbloquee otro proceso bloquedo.
• Se permite varios conjuntos de procesos bloqueados simultáneos.
• Necesita servicios externos proporcionados por el SO

Estructura de un Semáforo

• Un semáforo es una instancia de una estructura de datos con:
  • Un conjunto de procesos bloqueados esperando al semáforo.
  • Un valor natural (entero no negativo) llamado valor del semáforo.

Operaciones del Semáforo

• sem_wait(s): Bloquea el proceso si s es 0. Disminuir el valor en uno
• sem_signal(s): Aumenta el valor dese uno. Reactiva a uno de los procesos esperando.

Invariante de un Semáforo

• Dado un semáforo s en el tiempo t, su valor es el valor inicial + llamadas a sem_signal - llamadas a sem_wait >= 0
• Los cuatro valores son enteros
• La igualdad se cumple cuando no se esta ejecutando ni sem_wait ni sem_signal
• No cuentan sem_wait no completadas

Implementación sem _wat sem_signal

• Exclusión mutua sobre cada semáforo.

Patrones de Uso de Semáforos

• Esquema para solucionar la sincronización de un problema típico sencillo.
• Espera única: un proceso espera a que otro complete una sentencia.
• Exclusión mutua: acceso a una sección por parte de un número aleatorio de procesos.
• Problema del Productor/Consumidor: similar al de espera única pero repetida en un bucle.

Espera Única

• Un proceso "consumidor" lee una variable compartida.
• La sentencias deben de ser atómicas.

Espera Única: Solución con semáforo

• Se utiliza un semáforo cuyo valor es 1 solo cuando existe un valor para leer.

Espera Única : Verificación

• En cualquier instante, el número que se a ejecutado sem_signal se escribe después de E donde ns es menor o igual #E
• Se sigue para ver el invariante del monitor.

Uso de Semáforos para Exclusión Mutua

• Un semáforo se inicializa a 1 y se usa wait antes de la sección crítica y signal después de la sección crítica.

Verificación de Exclusión Mutua

• El número de procesos ejecutándose con un semáforo es: 0 <= nsc = nw - nw

Sincronización tipo Productor/Consumidor

• El problema de Productor/Consumidor es igual al que ya se conoce pero con lecturas y escrituras repetidas.

Solution Del Problema de Productores y Consumidores

• Se utiliza uno nuevo inicial izado en 1

Limitaciones de los semáforos

• Los problemas complejos con sincronización pueden ser difíciles de verificar.
• Al igual que los errores pueden provocar estados incorrectos.

Monitores como Mecansimo de Alto Nivel

• Se evita variables globales, se hacen explícitas las variables y las operaciones están protegidas. Esto permite tener acceso estructurado y encapsulación.

Estructura y Functionalidad de un Monitor

• El acceso es garantizado de forma mutua garantizando la sicnronización.

Ventajas sobre los Semáforos

• Los monitores hacen que los problemas sean más fáciles de ver.

Sintaxis de Un Monitor

• Se declara especificando las variables permanentes, los procedimientos del monitor y el código inicializado.

Componentes de Un Monitor

• Variables permanentes:
  • Pueden ser accedidas del código.
  • permanecen sin modificaciones.
• Procedimientos
  • Toman nuevos valores
• Código de inicialización
  • Fija un valor inicial.

Cola Del Monitor Para Exclusiones Mutuas

• Si el proceso que va a ser afectado no es el que se necesita entonces se bloquea y se añade a una cola.
• Cuando un proceso abandone el monitor y están todos libres, la cola seguirá como FIFO para garantizar la validez.

Estructura de UN Semáforo

• La exclusividad mutua se garantiza pero los procesos bloqueados no ocupan la CPU.
• Un hilo se solicita el bloqueo para la espera.
• Se utiliza cola dependiendo de que variable se necesite para la siguiente operación y se guarda con el orden de que se necesita.

Monitores para la sincronización

• Implementar sincronizaciones donde se requieran de facilidades.
• con semáforos solo existe bloqueo o activaciones pero con esto se puede bloquear y activar selectivamente.

Diseño para la verificación de monitores

• Un usuario sólo tiene acceso a las variables mediante un conjunto de funciones
• Es un recurso compartido al cual se accede de forma concurrente
• Exclusión mutua con los accesos a procedimientos.

Cond

• Variable tipo condición para hacer al SO saber cuando un proceso espere y libere al monitor.
• Wait y Signal:
  • El proceso llama a wait indicando que espera una condición
  • Otro proceso llama a señal una vez que la condición se ha cumplido
• Los procesos que hagan wait liberan la seguridad del monitor permitiendo que puedan entrar otros.

Semántica Y Exclusividad Mutua

• Un subproceso se solicita el bloqueo para la espera indicandole con prioridad al SO.
• Señal:
  • Hay tipos de procedimientos de señal, a veces un programa funciona con un semáforo pero no con otro, y viceversa.
    • Signal Y Continuar, el programa señal intenta hacer el signal pero otro programa ocupa ese valor por lo que a veces da errores por la espera.
    • Signal Y Salida, el monitor señal libera el camino, pero el asignante es quien ejecuta.
    • Signal y esperar por una condición.

Colas De Prioridad

• El planificador se le notifica del código dependiente de los tiempos por lo que así se puede poner uno con mayor o menor capacidad de tiempo.
• Se usan para la espera en FIFO.

El Problema de Los Escritores y Lectores

• Hay procesos que leen la estructura de datos, pero no pueden hacer nada más, su código simplemente lee y debe de ser hecho de forma concurrente, los escritores se van al último ciclo de la operación.
• Para implementar la sincronización correctamente se usaran 4 procedimientos.
• Para implementar se supone que el monitor se le llama cuando un proceso entra en modo lectura, para implementar se supone que si hay mas de 0 escritores, se espera a que no haya ninguno activo.

Cola De Urgencias

• Se tiene más prioridad en un monitor de espera con señal.

Este cuestionario explora el comportamiento y las propiedades de los semáforos en sistemas concurrentes. Aborda las operaciones sem_wait y sem_signal, condiciones de bloqueo, y el uso de semáforos binarios. También cubre cómo los semáforos previenen condiciones de carrera.