7220573
Description
Mind Map by Marlene Vásquez, updated more than 1 year ago
|
Created by Marlene Vásquez
about 8 years ago
|
|
Tema 2: Sincronización en
Memoria Compartida
- SOLUCIONES
- Bajo Nivel con espera ocupada
- software (operaciones
estándar)
- ALGORITMOS(para 2 procesos)
- DEKKER
- PETERSON
- DEKKER
- ESTRUCTURA DE LOS
PROCESOS CON
SECCIONES CRÍTICAS
- E/S en secciones crítcas
- acceso repetitivo
- condiciones sobre el
comportamiento de los
procesos
- E/S en secciones crítcas
- PROPIEDADES PARA LA E.M
- REFINAMIENTOS
- 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
- VERSIÓN 1: No es correcta, no se cumple
la propiedad de EM
- Protocolo de Entrada(PE),
Sección crítica(SC),
Protocolo de Salida(PS), otras
sentencias del proceso(RS)
- ALGORITMO DE
DEKKER
- DIJKSTRA
- E.M,
Progreso,
Espera
limitada,
Eficiencia,
Equidad
- ALGORITMOS(para 2 procesos)
- Hardware (Cerrojos)
instrucciones máquina
- desventajas
- las esperas ocupadas consumen tiempo de CPU
- se puede acceder directamente a los cerrojos
- no se cumplen ciertas condiciones de quidad
- las esperas ocupadas consumen tiempo de CPU
- uso de los cerrojos es restringido
- desventajas
- se basa en programas que contienen
instrucciones de bajo nivel (lectura,
escritura) y bucles para realizar esperas
- 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
- software (operaciones
estándar)
- ALTO NIVEL
- Semáforos
- 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)
- ESTRUCTURA
- ELEMENTOS
- Conjunto de procesos bloqueados.
INICIALIZACIÓN: vacío
- Valor Natural (no negativo). INICIALIZACION:
valor inicial del semáforo
Annotations:
- valor del semáforo
- Conjunto de procesos bloqueados.
INICIALIZACIÓN: vacío
- un semáforo es una instancia de una estructura de
datos. * esta estructura reside en memoria compartida.
- ELEMENTOS
- OPERACIONES
- sem_wait( S ) :
if (S > 0) S-- ;
else if(s==0)
bloquear;
- sem_signal(S) :
if (! s.isEmpty())
desbloquear;
else s++;
- sem_wait( S ) :
if (S > 0) S-- ;
else if(s==0)
bloquear;
- USO
- 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
- 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
- SINCRONIZACIÓN
- el problema de prod-cons se
resuelve fácilmente
- el problema de prod-cons se
resuelve fácilmente
- EXCLUSIÓN MUTUA
- LIMITACIONES
- 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.
- 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.
- 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).
- 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)
- regiones criticas
- solución de mas alto nivel que
los semáforos, se pueden
implementar sobre semáforos
- solución de mas alto nivel que
los semáforos, se pueden
implementar sobre semáforos
- Monitores
- solución de mas alto nivel que las otras
soluciones y se pueden implementar en
algunos lenguajes orientados a objetos
(JAVA, PYTHON).
- FUNCIONAMIENTO
- 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
- 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
- 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
- Si un proceso esta dentro del monitor ningún otro
proceso podrá entrar, hasta que el otro proceso que
esta dentro termine
- 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.
- 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.
- 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.
- 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.
- 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
- FORMA parte del ESTADO del monitor
- si un proceso esta DENTRO y otro proceso intenta
ejecutar un procedimiento del monitor este
proceso se queda bloqueado en la cola del monitor.
- COMUNICACIÓN
- DEFINICION
- 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
- 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.
- Variables protegidas
- EXCLUSIÓN MUTUA
en el acceso a los
procedimientos
- SINTAXIS
- COMPONENTES
- variables
permanentes
- almacenan el estado del
recurso compartido
- almacenan el estado del
recurso compartido
- procedimientos internos o
procedimientos exportados
- manipulan las variables
permanentes
- manipulan las variables
permanentes
- código de
inicialización
- Se inicializa las variables permanentes.
se ejecuta una única vez
- Se inicializa las variables permanentes.
se ejecuta una única vez
- VARIABLES CONDICION
- variables
permanentes
- 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
- PROPIEDADES
- SINCRONIZACIÓN
- 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.
- 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.
- COLAS DE CONDICIÓN
- OPERACIONES
- cond.wait()
- cond.signal()
- cond.queue()
- cond.wait()
- Propiedad FIFO
- signal reactivara al
proceso que lleve más
tiempo esperando
- 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
- 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
- OPERACIONES
- VARIABLES CONDICIÓN (señales)
- SEMANTICA
- 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
- 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
- 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
- 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
- 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
- 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
- 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)
- 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)
- 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
- SEÑALAR Y CONTINUAR
- VERIFICACIÓN
- IMPLEMENTACIÓN CON SEMÁFOROS
- 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
- COLA DEL MONITOR.
COLA DE PROCESOS
URGENTES, COLA DE
PROCESOS
BLOQUEADOS
- 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
- semáforos y monitores
son equivalentes en
potencia expresiva pero
los monitores facilitan el
desarrollo
- solución de mas alto nivel que las otras
soluciones y se pueden implementar en
algunos lenguajes orientados a objetos
(JAVA, PYTHON).
- ofrece interfaces de acceso a
estructuras de datos, ademas
se usa bloqueos de procesos
- Semáforos
- Bajo Nivel con espera ocupada
Want to create your own Mind Maps for free with GoConqr? Learn more.