Cap6
Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 29,02 KB
Antecedentes
El problema de la sección crítica
Solución de Peterson
Hardware de sincronización
Semáforos
Problemas clásicos de sincronización
Monitores
Ejemplos de sincronización
Transacciones atómicas
2
Acceso concurrente a datos compartidos puede resultar
en inconsistencia de datos
Mantener la consistencia de datos requiere de
mecanismos para asegurar la ejecución ordenada de
procesos cooperativos
Suponga que queremos ofrecer una solución para el
problema del productor-consumidor. Podemos lograr
esto llevando la cuenta de buffers llenos. Inicialmente,
la cuenta vale 0. El productor es responsable de
incrementar la cuenta después de producir un buffer
nuevo y el consumidor la decrementa después de
consumir un buffer.
Condición de concurso
count++ puede implementarse como
register1 = count
register1 = register1 + 1
count = register1
count-- puede implementarse como
register2 = count
register2 = register2 - 1
count = register2
Considera la ejecución alternada, iniciando con count = 5:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
6
Solución problema de la sección crítica
Exclusión Mutua - Si el proceso Pi está ejecutando en su
sección crítica, ningún otro proceso puede entrar a su sección
crítica
Progreso - Si ningún proceso está ejecutando en su sección
crítica y existen un procesos que desean entrar a su sección
crítica, la selección de los procesos que entrarán a
continuación en su sección crítica no puede posponerse
indefinidamente
Espera acotada - Debe limitarse el número de veces que
otros procesos son permitidos en sus regiones críticas
después de que un proceso solicita entrar en su sección
crítica y antes de que ésta solicitud le sea concedida
Asume que cada proceso se ejecuta a velocidad mayor a
cero
No asumimos nada acerca de la velocidad relativa de los
7
Problema de la sección crítica
Condición de concurso - Cuando existe acceso
concurrente a datos compartidos y el resultado final
depende del orden de ejecución.
Sección crítica - Segmento del código donde se accede
a los datos compartidos.
Sección de entrada - Código que solicita permiso para
acceder a la sección crítica.
Sección de salida - Código que se ejecuta después de
salir de la sección crítica
8
Estructura de un proceso típico
9
Solución de Peterson
Solución para dos procesos
Asume que las instrucciones LOAD y STORE son
atómicas; i.e. que no pueden interrumpirse.
Los dos procesos comparten dos variables:
int turn;
Boolean flag[2]
La variable turn indica a quién le toca entrar en su
sección crítica.
El arreglo flag se utiliza para indicar si un proceso está
listo para entrar a su sección crítica. flag[i] = true ¡implica
que el proceso Pi está listo!
10
Algoritmo para el proceso Pi
11
Sección crítica utilizando candados
12
Hardware de sincronización
Muchos sistemas proveen soporte de hardware para
código de sección crítica
Uniprocesadores - pueden deshabilitar interrupciones
El código en ejecución actual no puede ser sacado
del procesador (no-preemption)
Generalmente muy ineficiente en sistemas
multiprocesador
No escalan bien los SO que hacen esto
Máquinas modernas ofrecen instrucciones atómicas
especiales
Atómica = no se puede interrumpir
Ya sea probar palabra en memoria y asignar valor
O intercambiar contenido de dos palabras de memoria
Semáforo
Herramienta de sincronización que no requiere espera ocupada
(busy waiting)
Semáforo S - variable entera
Dos operaciones estándar modifican S: acquire() y release()
Originalmente llamadas P() y V()
Menos complicado
Sólo puede accederse a través de dos operaciones atómicas
Semáforo como herramienta de
Semáforo de cuenta - valor entero con rango sobre un
dominio no restringido
Semáforo Binary - valor entero con rango entre 0 y 1;
más sencillo de implementar
También conocido como candado mutex
Implementación de semáforos
Debe garantizar que nunca dos procesos cualesquiera
pueden ejecutar acquire () y release () en el mismo
semáforo al mismo tiempo
Por tanto, su implementación se convierte en el
problema de sección crítica, donde colocamos el código
para wait y signal.
Ahora podemos tener espera ocupada en la
implementación de la sección crítica
Afortunadamente el código es corto
Espera ocupada es pequeña si la sección crítica
es inusualmente ocupada
Nótese que aplicaciones pueden pasar mucho tiempo en
sus secciones críticas y por lo tanto esta NO es una
buena solución.
Implementación de semáforos sin espera
Con cada semáforo existe una cola de espera asociada.
Cada entrada en una cola de espera tiene dos datos:
valor (de tipo entero)
apuntador a la siguiente entrada en la lista
Dos operaciones:
block - coloca al proceso que invoca la operación en
la cola de espera apropiada.
wakeup - quita uno de los procesos de la cola de
espera y lo pasa a la cola de listos.
Implementación de semáforos sin espera
Implementación de acquire():
Implementación de release():
Abrazo mortal y hambruna
Abrazo mortal (Deadlock) - dos o más procesos esperan
indefinidamente por un evento que sólo puede generar uno de los
procesos que esperan
Sean S y Q dos semáforos iniciados a 1
P0 P1
S.acquire(); Q.acquire();
Q.acquire(); S.acquire();
S.release(); Q.release();
Q.release(); S.release();
Hambruna (Starvation) - bloqueo indefinido. Un proceso nunca
puede eliminarse de la cola de un semáforo donde está suspendido.
Problemas clásicos de sincronización
Problema del buffer acotado
Problema de lectores y escritores
Problema de los filósofos comensales
Problema de buffer acotado
N buffers, cada uno puede contener un elemento
Semáforo mutex iniciado en 1
Semáforo full iniciado en 0
Semáforo empty iniciado al valor N.
Problema de lectores y escritores
Un conjunto de datos está compartido entre un número de
procesos concurrentes
Lectores - solamente leen el conjunto de datos; ellos no
realizan actualizaciones
Escritores - pueden leer y escribir.
Problema - permitir que múltiples lectores lean de
simultánea. Solo un escritor puede acceder a los datos
compartidos al mismo tiempo.
Datos compartidos
Conjunto de datos
Semáforo mutex iniciado en 1.
Semáforo db iniciado en 1.
Entero readerCount iniciado en 0.
Problemas con los semáforos
Uso correcto de las operaciones de semáforos:
mutex.acquire() . mutex.release()
mutex.wait() mutex.wait()
Omitir mutex.wait () o mutex.release() (o ambos)
Monitores
Una abstracción de alto nivel que provee un mecanismo
conveniente y efectivo para sincronización de procesos
Solamente un proceso puede estar activo dentro de un
monitor en un momento dado
Sincronización en Pthreads
El API de Pthreads es independiete del SO
Provee:
candados mutex
variables de condición
Extensiones no-portables incluyen:
candados read-write
spin locks
Transacciones atómicas
Modelo del sistema
Recuperación basada en bitácoras (logs)
Puntos de control (Checkpoints)
Transacciones atómicas concurrentes
Modelo del sistema
Asegura que las operaciones ocurren como una única unidad
de trabajo, todas o ninguna
Relacionado con el campo de bases de datos
El reto es asegurar atomicidad a pesar de fallas del sistema
de cómputo
Transacción - colección de instrucciones u operaciones que
realizan una única función lógica
Nos interesan los cambios en almacenamiento estable -
disco
Transacción es una serie de operaciones de lectura y
escritura
Termina con la operación commit (transacción exitosa) o
abort (transacción fallida)
Transacción abortada debe rebobinar y deshacer los
cambios a su estado original
Tipos de medio de almacenamiento
Almacenamiento volátil - la información almacenada
aquí no sobrevive caídas del sistema
Ejemplo: memoria principal, cache
Almacenamiento no-volátil - la información usualmente
sobrevive caídas
Ejemplo: disco y cinta
Almacenamiento estable - No se pierde información
NO es posible en realidad, aproximación vía
replicación o dispositivos RAID con modos
independientes de falla
Meta es asegurar la atomicidad de la transacción donde las fallas
ocasionan la pérdida de información en almacenamiento volátil
Recuperación basada en bitácoras
Registro en almacenamiento estable acerca de todas las
modificaciones de una transacción
Más común es bitácora write-ahead
Bitácora en almacenamiento estable, cada entrada
describe una operación de escritura, incluyendo:
Nombre de transacción
Nombre de un dato
Valor anterior
Nuevo valor
Se escribe cuando la transacción Ti inicia
Se escribe cuando Ti commits
La entrada en bitácora debe llegar al almacenamiento
estable antes de realizar la operación
Algoritmo recuperación basado bitácora
Utilizando la bitácora, el sistema puede manejar cualquier
error de memoria volátil
Undo(Ti) regresa valores de datos actualizados por Ti
Redo(Ti) asigna los valores de todos los datos en la
transacción Ti a nuevos valores
Undo(Ti) y redo(Ti) deben ser idempotentes
Múltiples ejecuciones deben tener el mismo resultado
como una sóla ejecución
Si el sistema falla, regresa a su estado original todos los
datos a través de la bitácora
Si bitácora contiene sin , undo(Ti)
Si bitácora contiene y , redo(Ti)
Puntos de control (Checkpoints)
Bitácora puede ser larga y la recuperación llevar mucho
tiempo
Puntos de control acortan la bitácora y tiempo de
recuperación.
Esquema de puntos de control:
Enviar todas las entradas de bitácora en memoria volátil a
almacenamiento estable
Enviar todos los datos modificados de volátil a estable
Enviar una entrada a la bitácora en
almacenamiento estable
Ahora recuperación solo incluye Ti, tal que Ti inició su
ejecución antes del punto de control más reciente y todas las
transacciones después de Ti.
Toas las demás transacciones ya están en almacenamiento
estable
Transacciones concurrentes
Debe ser equivalente a ejecución en serie - serialización
Pueda realizar todas las operaciones en la sección
crítica
Ineficiente, demasiado restrictiva
Algoritmos de control de concurrencia proveen
serialización
Serialización
Considera dos elementos de datos A y B
Considera las transacciones T0 y T1
Ejecuta T0 y T1 atómicamente
Ejecutar la secuencia llamada calendarizar
Atómicamente ejecutar la transacción llamada
calendario serial
Para N transacciones, hay N! calendarios seriales
válidos
Calendario no-serial
Calendario no-serial permite ejecución encimada
Resultado no necesariamente incorrecto
Considera el calendario S, operaciones Oi, Oj
Conflicto si acceden el mismo dato, con al menos un
write
Si Oi, Oj son consecutivos y operaciones en distintas
transacciones & Oi y Oj no se conflictúan
Entonces S con orden invertido Oj Oi equivalente a S
Si S puede convertirse S via operaciones de
intercambio no-conflicitivas
S es conflicto-serializable
Protocolo de candados
Asegura la serialización asociando candados con cada
elemento en los datos
Sigue protocolo de candado para control de acceso
Candados
Compartido - Ti tiene candado modo compartido (S)
sobre elemento Q, Ti puede leer Q pero no escribir
Exclusivo - Ti tiene candado exclusivo (X) sobre Q, Ti
puede leer y escribir Q
Requiere que cada transacción en elemento Q adquiera
el candado apropiado
Si ya tiene un candado, la nueva solicitud puede tener
que esperar
Similar al algoritmo de lectores-escritores
Protocolo de candado de dos fases
Generalmente asegura conflicto-serializabilidad
Cada transacción envía solicitudes lock y unlock en dos
fases
Creciendo - obteniendo candados
Encogiendo - liberando candados
No previene abrazos mortales
Protocolos basados en timestamps
Selecciona orden entre transacciones por adelantado -
ordenados por timestamp
Transacción Ti asociado con TS(Ti) antes que Ti inicie
TS(Ti) < TS(Tj) si Ti entra al sistema antes que Tj
TS puede generarse a partir del reloj del sistema o
como un contador lógico incrementado con cada
entrada de la transacción
Timestamps determinan el orden de serialización
Si TS(Ti) < TS(Tj), sistema debe garantizar calendario
equivalente al calendario serial donde Ti aparece
antes que Tj
Protocolo basado en timestamp
Elemento Q obtiene dos timestamps
W-timestamp(Q) - timestamp más grande de cualquier
transacción que ejecutó write(Q) con éxito
R-timestamp(Q) - timestamp más grande de un read(Q)
exitoso
Se actualiza cada vez que se ejecutan read(Q) o write(Q)
Protocolo ordenado por timestamp asegura que posibles read
y write se ejecutan en el orden adecuado
Suponga Ti ejecuta read(Q)
Si TS(Ti) < W-timestamp(Q), Ti necesita leer el valor de Q
que ya fue sobre-escrito
Operación read rechazada y Ti rebobinada
Si TS(Ti) ¡Ý W-timestamp(Q)
read ejecutado, R-timestamp(Q) = max(R-timestamp
(Q), TS(Ti))
Protocolo basado en timestamp
Suponga Ti ejecuta write(Q)
Si TS(Ti) < R-timestamp(Q), valor Q producido por Ti
era requerido anteriormente y Ti asume que nunca
sería producido
Operación write rechazada, Ti rebobinada
Si TS(Ti) < W-timestamp(Q), Ti intenta escribir un
valor obsoleto de Q
Operación write rechazada y Ti rebobinada
En otro caso, se ejecuta write
Cualquier transacción rebobinada Ti recibe un nuevo
timestamp y es re-iniciada
Algoritmo asegura conflicto-serializabilidad y está libre
de abrazos mortales
Variables de condició n
Condition x, y;
Dos operaciones en una variable de condició n:
x.wait () - el proceso que invoca esta operació n es
suspendido.
x.signal () - reinicia uno de los procesos (si existe)
que invocó x.wait ()
Solució n a los filó sofos comensales
Cada filó sofo invoca las operaciones takeForks(i) y
returnForks(i) en esta secuencia:
dp.takeForks(i)
COMER
dp.returnForks(i)
Sincronizació n en Java
Java provee sincronizació n a nivel del lenguaje.
Cada objeto Java tiene asociado un candado.
Este candado se adquiere utilizando el mé todo
synchronized.
Este candado es liberado cuando sales del mé todo
synchronized.
Los hilos esperando adquirir el candado del objeto son
puestos en el conjunto de entrada del candado.
Sincronizació n en Java
Cada objeto tiene asociado un conjunto de entrada
6. Silberschatz, Galvin and Gagne © 2007 Operating System Concepts with Java - 7 th Edition, Nov 15, 2006
Sincronizació n en Java
Mé todos sincronizados insert() y remove()
Sincronizació n Java wait/notify()
Cuando un hilo ejecuta wait():
1. El hilo libera el candado del objeto;
2. El estado del hilo cambia a bloqueado;
3. El hilo es puesto en el conjunto de espera del objeto.
Cuando un hilo invoca notify():
1. Un hilo arbitrario T del conjunto de espera es
seleccionado;
2. T se mueve del conjunto de espera al de entrada;
3. El estado de T cambia a Runnable.
Sincronizació n Java
Conjuntos de entrada y espera
Sincronizació n Java
La llamada a notify() selecciona un hilo arbitrario del
conjunto de espera. Es posible que el hilo seleccionado
no espera en la condició n por la cual fue notificado.
La llamada notifyAll() selecciona todos los hilos en el
conjunto de espera y los mueve al de entrada.
En general, notifyAll() es una estrategia má s
conservadora que notify().
Sincronizació n Java
En lugar de sincronizar un mé todo completo,
bloques de có digo se declaran sincronizado
Sincronizació n Java
Sincronizació n de bloque con wait()/notify()
Caracterí sticas de concurrencia Java5
Una variable de condició n se crea primero con
ReentrantLock y despué s invocando su mé todo newCondition()
Una vez hecho esto, es posible invocar los
mé todos await() y signal().
Ejemplos de sincronizació n
Solaris
Windows XP
Linux
Pthreads
Sincronizació n en Solaris
Implementa una variedad de candados para soportar
multi-tarea, multi-hilos (incluyendo hilos de tiempo real) y
multi-procesamiento
Utiliza mutexes adaptables por razones de eficiencia
para segmentos pequeñ os de có digo
Utiliza variables de condició n y candados de lectoresescritores
cuando secciones mayores de có digo
requieren acceso a datos
Utiliza turnstiles para ordenar la lista de hilos esperando
para tomar un mutex adaptable o un candado de lectorescritor
64
Sincronizació n en Windows XP
Utiliza má scaras de interrupció n para proteger el acceso
a recursos globales en sistemas uni-procesador
Utiliza spinlocks en sistemas multi-procesador
Tambié n provee objetos despachadores que pueden
actuar como mutexes y semá foros
Los objetos despachadores tambié n proveen eventos
Un evento actú a como una variable de condició n
Sincronizació n Linux
Linux:
Deshabilita las interrupciones para implementar
secciones crí ticas cortas
Linux provee:
semá foros
spin locks
El problema de la sección crítica
Solución de Peterson
Hardware de sincronización
Semáforos
Problemas clásicos de sincronización
Monitores
Ejemplos de sincronización
Transacciones atómicas
2
Acceso concurrente a datos compartidos puede resultar
en inconsistencia de datos
Mantener la consistencia de datos requiere de
mecanismos para asegurar la ejecución ordenada de
procesos cooperativos
Suponga que queremos ofrecer una solución para el
problema del productor-consumidor. Podemos lograr
esto llevando la cuenta de buffers llenos. Inicialmente,
la cuenta vale 0. El productor es responsable de
incrementar la cuenta después de producir un buffer
nuevo y el consumidor la decrementa después de
consumir un buffer.
Condición de concurso
count++ puede implementarse como
register1 = count
register1 = register1 + 1
count = register1
count-- puede implementarse como
register2 = count
register2 = register2 - 1
count = register2
Considera la ejecución alternada, iniciando con count = 5:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
6
Solución problema de la sección crítica
Exclusión Mutua - Si el proceso Pi está ejecutando en su
sección crítica, ningún otro proceso puede entrar a su sección
crítica
Progreso - Si ningún proceso está ejecutando en su sección
crítica y existen un procesos que desean entrar a su sección
crítica, la selección de los procesos que entrarán a
continuación en su sección crítica no puede posponerse
indefinidamente
Espera acotada - Debe limitarse el número de veces que
otros procesos son permitidos en sus regiones críticas
después de que un proceso solicita entrar en su sección
crítica y antes de que ésta solicitud le sea concedida
Asume que cada proceso se ejecuta a velocidad mayor a
cero
No asumimos nada acerca de la velocidad relativa de los
7
Problema de la sección crítica
Condición de concurso - Cuando existe acceso
concurrente a datos compartidos y el resultado final
depende del orden de ejecución.
Sección crítica - Segmento del código donde se accede
a los datos compartidos.
Sección de entrada - Código que solicita permiso para
acceder a la sección crítica.
Sección de salida - Código que se ejecuta después de
salir de la sección crítica
8
Estructura de un proceso típico
9
Solución de Peterson
Solución para dos procesos
Asume que las instrucciones LOAD y STORE son
atómicas; i.e. que no pueden interrumpirse.
Los dos procesos comparten dos variables:
int turn;
Boolean flag[2]
La variable turn indica a quién le toca entrar en su
sección crítica.
El arreglo flag se utiliza para indicar si un proceso está
listo para entrar a su sección crítica. flag[i] = true ¡implica
que el proceso Pi está listo!
10
Algoritmo para el proceso Pi
11
Sección crítica utilizando candados
12
Hardware de sincronización
Muchos sistemas proveen soporte de hardware para
código de sección crítica
Uniprocesadores - pueden deshabilitar interrupciones
El código en ejecución actual no puede ser sacado
del procesador (no-preemption)
Generalmente muy ineficiente en sistemas
multiprocesador
No escalan bien los SO que hacen esto
Máquinas modernas ofrecen instrucciones atómicas
especiales
Atómica = no se puede interrumpir
Ya sea probar palabra en memoria y asignar valor
O intercambiar contenido de dos palabras de memoria
Semáforo
Herramienta de sincronización que no requiere espera ocupada
(busy waiting)
Semáforo S - variable entera
Dos operaciones estándar modifican S: acquire() y release()
Originalmente llamadas P() y V()
Menos complicado
Sólo puede accederse a través de dos operaciones atómicas
Semáforo como herramienta de
Semáforo de cuenta - valor entero con rango sobre un
dominio no restringido
Semáforo Binary - valor entero con rango entre 0 y 1;
más sencillo de implementar
También conocido como candado mutex
Implementación de semáforos
Debe garantizar que nunca dos procesos cualesquiera
pueden ejecutar acquire () y release () en el mismo
semáforo al mismo tiempo
Por tanto, su implementación se convierte en el
problema de sección crítica, donde colocamos el código
para wait y signal.
Ahora podemos tener espera ocupada en la
implementación de la sección crítica
Afortunadamente el código es corto
Espera ocupada es pequeña si la sección crítica
es inusualmente ocupada
Nótese que aplicaciones pueden pasar mucho tiempo en
sus secciones críticas y por lo tanto esta NO es una
buena solución.
Implementación de semáforos sin espera
Con cada semáforo existe una cola de espera asociada.
Cada entrada en una cola de espera tiene dos datos:
valor (de tipo entero)
apuntador a la siguiente entrada en la lista
Dos operaciones:
block - coloca al proceso que invoca la operación en
la cola de espera apropiada.
wakeup - quita uno de los procesos de la cola de
espera y lo pasa a la cola de listos.
Implementación de semáforos sin espera
Implementación de acquire():
Implementación de release():
Abrazo mortal y hambruna
Abrazo mortal (Deadlock) - dos o más procesos esperan
indefinidamente por un evento que sólo puede generar uno de los
procesos que esperan
Sean S y Q dos semáforos iniciados a 1
P0 P1
S.acquire(); Q.acquire();
Q.acquire(); S.acquire();
S.release(); Q.release();
Q.release(); S.release();
Hambruna (Starvation) - bloqueo indefinido. Un proceso nunca
puede eliminarse de la cola de un semáforo donde está suspendido.
Problemas clásicos de sincronización
Problema del buffer acotado
Problema de lectores y escritores
Problema de los filósofos comensales
Problema de buffer acotado
N buffers, cada uno puede contener un elemento
Semáforo mutex iniciado en 1
Semáforo full iniciado en 0
Semáforo empty iniciado al valor N.
Problema de lectores y escritores
Un conjunto de datos está compartido entre un número de
procesos concurrentes
Lectores - solamente leen el conjunto de datos; ellos no
realizan actualizaciones
Escritores - pueden leer y escribir.
Problema - permitir que múltiples lectores lean de
simultánea. Solo un escritor puede acceder a los datos
compartidos al mismo tiempo.
Datos compartidos
Conjunto de datos
Semáforo mutex iniciado en 1.
Semáforo db iniciado en 1.
Entero readerCount iniciado en 0.
Problemas con los semáforos
Uso correcto de las operaciones de semáforos:
mutex.acquire() . mutex.release()
mutex.wait() mutex.wait()
Omitir mutex.wait () o mutex.release() (o ambos)
Monitores
Una abstracción de alto nivel que provee un mecanismo
conveniente y efectivo para sincronización de procesos
Solamente un proceso puede estar activo dentro de un
monitor en un momento dado
Sincronización en Pthreads
El API de Pthreads es independiete del SO
Provee:
candados mutex
variables de condición
Extensiones no-portables incluyen:
candados read-write
spin locks
Transacciones atómicas
Modelo del sistema
Recuperación basada en bitácoras (logs)
Puntos de control (Checkpoints)
Transacciones atómicas concurrentes
Modelo del sistema
Asegura que las operaciones ocurren como una única unidad
de trabajo, todas o ninguna
Relacionado con el campo de bases de datos
El reto es asegurar atomicidad a pesar de fallas del sistema
de cómputo
Transacción - colección de instrucciones u operaciones que
realizan una única función lógica
Nos interesan los cambios en almacenamiento estable -
disco
Transacción es una serie de operaciones de lectura y
escritura
Termina con la operación commit (transacción exitosa) o
abort (transacción fallida)
Transacción abortada debe rebobinar y deshacer los
cambios a su estado original
Tipos de medio de almacenamiento
Almacenamiento volátil - la información almacenada
aquí no sobrevive caídas del sistema
Ejemplo: memoria principal, cache
Almacenamiento no-volátil - la información usualmente
sobrevive caídas
Ejemplo: disco y cinta
Almacenamiento estable - No se pierde información
NO es posible en realidad, aproximación vía
replicación o dispositivos RAID con modos
independientes de falla
Meta es asegurar la atomicidad de la transacción donde las fallas
ocasionan la pérdida de información en almacenamiento volátil
Recuperación basada en bitácoras
Registro en almacenamiento estable acerca de todas las
modificaciones de una transacción
Más común es bitácora write-ahead
Bitácora en almacenamiento estable, cada entrada
describe una operación de escritura, incluyendo:
Nombre de transacción
Nombre de un dato
Valor anterior
Nuevo valor
Se escribe
estable antes de realizar la operación
Algoritmo recuperación basado bitácora
Utilizando la bitácora, el sistema puede manejar cualquier
error de memoria volátil
Undo(Ti) regresa valores de datos actualizados por Ti
Redo(Ti) asigna los valores de todos los datos en la
transacción Ti a nuevos valores
Undo(Ti) y redo(Ti) deben ser idempotentes
Múltiples ejecuciones deben tener el mismo resultado
como una sóla ejecución
Si el sistema falla, regresa a su estado original todos los
datos a través de la bitácora
Si bitácora contiene
Puntos de control (Checkpoints)
Bitácora puede ser larga y la recuperación llevar mucho
tiempo
Puntos de control acortan la bitácora y tiempo de
recuperación.
Esquema de puntos de control:
Enviar todas las entradas de bitácora en memoria volátil a
almacenamiento estable
Enviar todos los datos modificados de volátil a estable
Enviar una entrada
almacenamiento estable
ejecución antes del punto de control más reciente y todas las
transacciones después de Ti.
Toas las demás transacciones ya están en almacenamiento
estable
Transacciones concurrentes
Debe ser equivalente a ejecución en serie - serialización
Pueda realizar todas las operaciones en la sección
crítica
Ineficiente, demasiado restrictiva
Algoritmos de control de concurrencia proveen
serialización
Serialización
Considera dos elementos de datos A y B
Considera las transacciones T0 y T1
Ejecuta T0 y T1 atómicamente
Ejecutar la secuencia llamada calendarizar
Atómicamente ejecutar la transacción llamada
calendario serial
Para N transacciones, hay N! calendarios seriales
válidos
Calendario no-serial
Calendario no-serial permite ejecución encimada
Resultado no necesariamente incorrecto
Considera el calendario S, operaciones Oi, Oj
Conflicto si acceden el mismo dato, con al menos un
write
Si Oi, Oj son consecutivos y operaciones en distintas
transacciones & Oi y Oj no se conflictúan
Entonces S con orden invertido Oj Oi equivalente a S
Si S puede convertirse S via operaciones de
intercambio no-conflicitivas
S es conflicto-serializable
Protocolo de candados
Asegura la serialización asociando candados con cada
elemento en los datos
Sigue protocolo de candado para control de acceso
Candados
Compartido - Ti tiene candado modo compartido (S)
sobre elemento Q, Ti puede leer Q pero no escribir
Exclusivo - Ti tiene candado exclusivo (X) sobre Q, Ti
puede leer y escribir Q
Requiere que cada transacción en elemento Q adquiera
el candado apropiado
Si ya tiene un candado, la nueva solicitud puede tener
que esperar
Similar al algoritmo de lectores-escritores
Protocolo de candado de dos fases
Generalmente asegura conflicto-serializabilidad
Cada transacción envía solicitudes lock y unlock en dos
fases
Creciendo - obteniendo candados
Encogiendo - liberando candados
No previene abrazos mortales
Protocolos basados en timestamps
Selecciona orden entre transacciones por adelantado -
ordenados por timestamp
Transacción Ti asociado con TS(Ti) antes que Ti inicie
TS(Ti) < TS(Tj) si Ti entra al sistema antes que Tj
TS puede generarse a partir del reloj del sistema o
como un contador lógico incrementado con cada
entrada de la transacción
Timestamps determinan el orden de serialización
Si TS(Ti) < TS(Tj), sistema debe garantizar calendario
equivalente al calendario serial donde Ti aparece
antes que Tj
Protocolo basado en timestamp
Elemento Q obtiene dos timestamps
W-timestamp(Q) - timestamp más grande de cualquier
transacción que ejecutó write(Q) con éxito
R-timestamp(Q) - timestamp más grande de un read(Q)
exitoso
Se actualiza cada vez que se ejecutan read(Q) o write(Q)
Protocolo ordenado por timestamp asegura que posibles read
y write se ejecutan en el orden adecuado
Suponga Ti ejecuta read(Q)
Si TS(Ti) < W-timestamp(Q), Ti necesita leer el valor de Q
que ya fue sobre-escrito
Operación read rechazada y Ti rebobinada
Si TS(Ti) ¡Ý W-timestamp(Q)
read ejecutado, R-timestamp(Q) = max(R-timestamp
(Q), TS(Ti))
Protocolo basado en timestamp
Suponga Ti ejecuta write(Q)
Si TS(Ti) < R-timestamp(Q), valor Q producido por Ti
era requerido anteriormente y Ti asume que nunca
sería producido
Operación write rechazada, Ti rebobinada
Si TS(Ti) < W-timestamp(Q), Ti intenta escribir un
valor obsoleto de Q
Operación write rechazada y Ti rebobinada
En otro caso, se ejecuta write
Cualquier transacción rebobinada Ti recibe un nuevo
timestamp y es re-iniciada
Algoritmo asegura conflicto-serializabilidad y está libre
de abrazos mortales
Variables de condició n
Condition x, y;
Dos operaciones en una variable de condició n:
x.wait () - el proceso que invoca esta operació n es
suspendido.
x.signal () - reinicia uno de los procesos (si existe)
que invocó x.wait ()
Solució n a los filó sofos comensales
Cada filó sofo invoca las operaciones takeForks(i) y
returnForks(i) en esta secuencia:
dp.takeForks(i)
COMER
dp.returnForks(i)
Sincronizació n en Java
Java provee sincronizació n a nivel del lenguaje.
Cada objeto Java tiene asociado un candado.
Este candado se adquiere utilizando el mé todo
synchronized.
Este candado es liberado cuando sales del mé todo
synchronized.
Los hilos esperando adquirir el candado del objeto son
puestos en el conjunto de entrada del candado.
Sincronizació n en Java
Cada objeto tiene asociado un conjunto de entrada
6. Silberschatz, Galvin and Gagne © 2007 Operating System Concepts with Java - 7 th Edition, Nov 15, 2006
Sincronizació n en Java
Mé todos sincronizados insert() y remove()
Sincronizació n Java wait/notify()
Cuando un hilo ejecuta wait():
1. El hilo libera el candado del objeto;
2. El estado del hilo cambia a bloqueado;
3. El hilo es puesto en el conjunto de espera del objeto.
Cuando un hilo invoca notify():
1. Un hilo arbitrario T del conjunto de espera es
seleccionado;
2. T se mueve del conjunto de espera al de entrada;
3. El estado de T cambia a Runnable.
Sincronizació n Java
Conjuntos de entrada y espera
Sincronizació n Java
La llamada a notify() selecciona un hilo arbitrario del
conjunto de espera. Es posible que el hilo seleccionado
no espera en la condició n por la cual fue notificado.
La llamada notifyAll() selecciona todos los hilos en el
conjunto de espera y los mueve al de entrada.
En general, notifyAll() es una estrategia má s
conservadora que notify().
Sincronizació n Java
En lugar de sincronizar un mé todo completo,
bloques de có digo se declaran sincronizado
Sincronizació n Java
Sincronizació n de bloque con wait()/notify()
Caracterí sticas de concurrencia Java5
Una variable de condició n se crea primero con
ReentrantLock y despué s invocando su mé todo newCondition()
Una vez hecho esto, es posible invocar los
mé todos await() y signal().
Ejemplos de sincronizació n
Solaris
Windows XP
Linux
Pthreads
Sincronizació n en Solaris
Implementa una variedad de candados para soportar
multi-tarea, multi-hilos (incluyendo hilos de tiempo real) y
multi-procesamiento
Utiliza mutexes adaptables por razones de eficiencia
para segmentos pequeñ os de có digo
Utiliza variables de condició n y candados de lectoresescritores
cuando secciones mayores de có digo
requieren acceso a datos
Utiliza turnstiles para ordenar la lista de hilos esperando
para tomar un mutex adaptable o un candado de lectorescritor
64
Sincronizació n en Windows XP
Utiliza má scaras de interrupció n para proteger el acceso
a recursos globales en sistemas uni-procesador
Utiliza spinlocks en sistemas multi-procesador
Tambié n provee objetos despachadores que pueden
actuar como mutexes y semá foros
Los objetos despachadores tambié n proveen eventos
Un evento actú a como una variable de condició n
Sincronizació n Linux
Linux:
Deshabilita las interrupciones para implementar
secciones crí ticas cortas
Linux provee:
semá foros
spin locks