Tema 2: Sincronización en Memoria Compartida

SOLUCIONES
1. Bajo Nivel con espera ocupada
  1. software (operaciones estándar)
    1. ALGORITMOS(para 2 procesos)
      1. DEKKER
      2. PETERSON
    2. ESTRUCTURA DE LOS PROCESOS CON SECCIONES CRÍTICAS
      1. E/S en secciones crítcas
      2. acceso repetitivo
      3. condiciones sobre el comportamiento de los procesos
    3. PROPIEDADES PARA LA E.M
    4. REFINAMIENTOS
      1. DIJKSTRA
        ALGORITMO DE DEKKER
        VERSIÓN 1: No es correcta, no se cumple la propiedad de EM
        VERSIÓN 2: No es correcta, se DA la propiedad de EM pero no se cumple la propiedad de PROGRESO EN LA EJECUCIÓN
        VERSIóN 3: No e correcta. ahora se cumple el PROGRESO DE EJECUCIÓN pero no se cumple la propiedad de la EM
        VERSIÓN 4: No es correcta, se DA la propiedad de EM pero no se cumple la propiedad de PROGRESO EN LA EJECUCIÓN puede ocurrir INTERBLOQUEO
        VERSIÓN 5: la posibilidad de interbloqueo es pequeña, por tanto no se cumple la propiedad de progreso
        Protocolo de Entrada(PE), Sección crítica(SC), Protocolo de Salida(PS), otras sentencias del proceso(RS)
    5. E.M, Progreso, Espera limitada, Eficiencia, Equidad
  2. Hardware (Cerrojos) instrucciones máquina
    1. desventajas
      1. las esperas ocupadas consumen tiempo de CPU
      2. se puede acceder directamente a los cerrojos
      3. no se cumplen ciertas condiciones de quidad
    2. uso de los cerrojos es restringido
  3. se basa en programas que contienen instrucciones de bajo nivel (lectura, escritura) y bucles para realizar esperas
  4. Exclusión Mutua con espera ocupada : Para asegurar la exclusión mutua deben incluir una secuencia de 3 pasos, Protocolo de Entrada, Salida y sección crítica
2. ALTO NIVEL
  1. Semáforos
    1. se construyen sobre las instrucciones de bajo nivel, usando servicios del SO para bloquear y reactivar procesos. Se puede usar para resolver problemas de SINCRONIZACIÓN. El mecánismo se implementa mediante instancias de estructura de datos a las que se accede únicamente mediante subprogramas específicos (aumenta la SEGURIDAD y SIMPLICIDAD)
    2. ESTRUCTURA
      1. ELEMENTOS
        Conjunto de procesos bloqueados. INICIALIZACIÓN: vacío
        Valor Natural (no negativo). INICIALIZACION: valor inicial del semáforo
        Anmerkungen:
        valor del semáforo
      2. un semáforo es una instancia de una estructura de datos. * esta estructura reside en memoria compartida.
    3. OPERACIONES
      1. sem_wait( S ) : if (S > 0) S-- ; else if(s==0) bloquear;
      2. sem_signal(S) : if (! s.isEmpty()) desbloquear; else s++;
    4. USO
      1. EXCLUSIÓN MUTUA
        semáforo inicializado a 1, y haciendo sem_wait antes de la sección crítica y sem_signal después de la sección crítica
      2. SINCRONIZACIÓN
        el problema de prod-cons se resuelve fácilmente
    5. LIMITACIONES
      1. solo resuelve problemas sencillos de sincronización. Problemas más complejos son difíciles de verificar su válidez. Al igual que los cerrojos, programas erroneos puede provocar que haya procesos bloqueados indefinidamente o estados incorrectos.
    6. Inconvenientes de usar mecánismos como los semáforos. Basado en variables globales (impide el diseño MODULAR y reduce la ESCALABILIDAD). Las operaciones se encuentran dispersas y NO protegidas (posibilidad de errores).
  2. regiones criticas
    1. solución de mas alto nivel que los semáforos, se pueden implementar sobre semáforos
  3. Monitores
    1. solución de mas alto nivel que las otras soluciones y se pueden implementar en algunos lenguajes orientados a objetos (JAVA, PYTHON).
    2. FUNCIONAMIENTO
      1. COMUNICACIÓN
        Cuando un proceso necesita OPERAR sobre un recurso compartido deberá realizar una llamada a uno de los procedimientos exportados. Cuando el proceso esta ejecutando el procedimiento decimos que esta dentro del monitor
      2. EXCLUSIÓN MUTUA
        Si un proceso esta dentro del monitor ningún otro proceso podrá entrar, hasta que el otro proceso que esta dentro termine
      3. SON OBJETOS PASIVOS
        Después de ejecutar el código de inicialización, un monitor es un objeto pasivo y el código de sus procedimientos solo se ejecuta cuando estos son invocados.
      4. INSTANCIACIÓN
        Para cada recurso compartido se tendría que definir un monitor. Para recursos con estructura y comportamiento idéntico podemos instanciar de forma parametrizada tantas veces como recursos se quiera controlar.
      5. COLA PARA E.M
        si un proceso esta DENTRO y otro proceso intenta ejecutar un procedimiento del monitor este proceso se queda bloqueado en la cola del monitor.
        Cuando un proceso ABANDONA se desbloquea un proceso de la cola, que ya puede entrar al monitor.
        Si la cola del monitor esta VACÍA el monitor está LIBRE y el primer proceso que ejecute una llamada a uno de sus procedimientos entrará al monitor. Para garantizar la VIVACIDAD del sistema, la planificación DE LA COLA debe seguir una política FIFO
        FORMA parte del ESTADO del monitor
    3. DEFINICION
      1. PROPIEDADES
        EXCLUSIÓN MUTUA en el acceso a los procedimientos
        E.M garantizada por definición. La IMPLEMENTACION garantiza que NUNCA 2 procesos estarán ejecutando simultáneamente algún procedimiento del monitor
        VENTAJAS sobre los semáforos
        Variables protegidas
        acceso estructurado
        Exclusión mutua garantizada.
      2. SINTAXIS
      3. COMPONENTES
        variables permanentes
        almacenan el estado del recurso compartido
        procedimientos internos o procedimientos exportados
        manipulan las variables permanentes
        código de inicialización
        Se inicializa las variables permanentes. se ejecuta una única vez
        VARIABLES CONDICION
      4. Permite: *definir objetos abstractos compartidos*. Garantizar el acceso exclusivos a las variables e implementar sincronización. El *recurso compartido* se percibe como un objeto. *Acceso estructurado y encapsulación*: se accede al recurso mediante un conjunto de operaciones. El usuario ignora la(s) variable (s) que representan al recurso y la implementación de las las operaciones. asociadas
    4. SINCRONIZACIÓN
      1. VARIABLES CONDICIÓN (señales)
        debe declararse una vble condición para cualquier condición lógica de SINCRONIZACIÓN. No tiene valor asociado (No requiere inicialización). representan colas. mas de un proceso puede estar dentro del monitor aunque solo uno estará ejecutándose.
      2. COLAS DE CONDICIÓN
        OPERACIONES
        cond.wait()
        cond.signal()
        cond.queue()
        Propiedad FIFO
        signal reactivara al proceso que lleve más tiempo esperando
        evita la inanición. Ningun efecto sobre la logica del programa solo mejoran las caracteristicas dependientes del TIEMPO
        CON PRIORIDAD
        Usa colas FIFO. cond.wait(PRIORIDAD: Integer). Tras bloqueo se ordena a los procesos en la cola por PRIORIDAD. cond.Signal reanuda al proceso con volor mas bajo de PRIORIDAD
    5. SEMANTICA
      1. SEÑALAR Y CONTINUAR
        Proceso señalador continua su ejecución dentro del monitor hasta que sale o se bloquea. AL continuar dentro del monitor el proceso señalador podría hacer falsa la condicion lógica por la que esperaba el proceso señalado. Esta semántica OBLIGA a programar la operación wait en un bucle
      2. SEÑALAR Y SALIR
        El proceso señalador sale del monitor despues de ejecutar cond.signal. Esta semántica condiciona el ESTILO de progrmación ya que obliga a colocar SIEMPRE la operación signal como última instrucción
      3. SEÑALAR Y ESPERAR
        El proceso señalador se bloquea justo despues de ejecutar la operación signal. El proceso señalado entra de forma inmediata al monitor. El proceso señalador entra en la cola de procesos del monitor. Es una semántica INJUSTA
      4. SEÑALAR Y ESPERA URGENTE
        Esta solución intenta corregir el problema de la falta de EQUITATIVIDAD de (SS) El proceso señalador se bloquea justo despues de ejecutar la operación signal. El proceso señalado entra de forma inmediata al monitor. El proceso señalador entra en una nueva cola de procesos que esperan para acceder al monitor (cola de procesos urgentes)
      5. POTENCIA EXPRESIVA: todas las semánticas son capaces de resolver los mismos problemas. FACILIDAD DE USO: la semántica SS condiciona el estilo de programación. EFICIENCIA: las semánticas SE y SU resultan ineficiente "suponiendo un bloqueo innecesario -> doble cambio de contexto en CPU" la semántica SC es un poco ineficiente al obligar usar un bucle para cada instrucción signal
    6. VERIFICACIÓN
    7. IMPLEMENTACIÓN CON SEMÁFOROS
      1. COLA DEL MONITOR: semáforo MUTEX. COLA PROC. URGENTES: semáforo NEXT y el nÚmero de procesos en la cola se contabiliza en la variable NEXT_COUNT (necesaria para implementar la semántica SU) esta implementación no permite llamadas recursivas
      2. COLA DEL MONITOR. COLA DE PROCESOS URGENTES, COLA DE PROCESOS BLOQUEADOS
    8. semáforos y monitores son equivalentes en potencia expresiva pero los monitores facilitan el desarrollo
  4. ofrece interfaces de acceso a estructuras de datos, ademas se usa bloqueos de procesos

Nächster

Tema 2: Sincronización en Memoria Compartida

Beschreibung

Zusammenfassung der Ressource

ähnlicher Inhalt

	Erstellt von Marlene Vásquez vor etwa 8 Jahre