Memoria
Caché
En los sistemas de archivos
convencionales, el fundamento para la memoria caché es la reducción de la E/S
de disco (lo que aumenta el rendimiento), en un SAD el objetivo es reducir el
tráfico en la red. Esquema Básico, el concepto de memoria caché es sencillo, si
los datos necesarios para satisfacer la solicitud de acceso no se encuentran en
la memoria cache, se trae una copia de servicio al usuario y los accesos se
llevan a cabo con la copia de memoria caché.
La idea es conservar allí los
bloques de disco de acceso mas reciente, para así manejar localmente los
accesos repetidos a la misma información y no aumentar el tráfico de la red. Se
utiliza una política de reemplazo (por ejemplo, la de utilización menos
reciente) para limitar el tamaño de la memoria caché. Políticas de
Actualización, la política empleada para escribir los bloques de datos
modificados en la copia maestra del servidor tiene un efecto decisivo sobre la
confiabilidad y el rendimiento del sistema. La política mas sencilla consiste
en escribir los datos directamente en el disco tan pronto se coloquen en una
memoria caché. La ventaja de la escritura directa es su confiabilidad, ya que
se pierde poca información si un sistema cliente falla. Sin embargo, esta política
requiere que cada acceso de escritura espere hasta que se envíe la información
al servidor, por lo que representa una escritura de escaso rendimiento. La
memoria caché con escritura directa equivale a usar el servicio remoto para
accesos de escritura y explotar la memoria cache únicamente para accesos de
lectura. NFS proporciona el acceso de escritura directa.
Consistencia, una maquina cliente
se enfrenta al problema de decidir si una copia de datos en memoria caché local
es consistente con la copia maestra ( y por tanto, puede usarse). Si la maquina
cliente determina que sus datos en memoria caché están desfasados, ya no pueden
servir para los accesos y hay que colocar en la memoria caché una copia
actualizada de los datos. Existen dos enfoques para verificar la validez de los
datos en memoria caché ..:
Enfoque
iniciado por el cliente, el cliente inicia una comprobación de validez, en la
cual se pone en contacto con el servidor y comprueban si los datos locales son
consistentes con la copia maestra.
Enfoque
iniciado por el servidor, el servidor anota, para cada cliente, las partes de
los archivos que coloca en memoria cache, y cuando detecta una inconsistencia,
debe reaccionar. Una posible fuente inconsistencia ocurre cuando dos clientes,
que trabajan en modos conflictivos, colocan en memoria caché un archivo.
Comunicación en grupos
(Algoritmos Para la Sincronización de Relojes)
Si una máquina tiene un receptor
de UTC, todas las máquinas deben sincronizarse con ella. Si ninguna máquina
tiene un receptor de UTC:• Cada máquina lleva el registro de su propio tiempo.•
Se debe mantener el tiempo de todas las máquinas tan cercano como sea posible.
Se supone que cada máquina tiene un cronómetro que provoca una interrupción “h”
veces por segundo. Cuando el cronómetro se detiene, el manejador de
interrupciones añade “1” a un reloj en software. El reloj en software mantiene
un registro del número de marcas (interrupciones) a partir de cierta fecha
acordada antes; al valor de este reloj se lo llama “C”.
Algoritmo de Cristian
Es adecuado para sistemas en los
que:• Una máquina tiene un receptor UTC, por lo que se la llama despachador del
tiempo.• El objetivo es sincronizar todas las máquinas con ella. Cada máquina
envía un mensaje al servidor para solicitar el tiempo actual, periódicamente,
en un tiempo no mayor que d / 2 r segundos. El despachador del tiempo responde
prontamente con un mensaje que contiene el tiempo actual “CUTC”.Cuando el
emisor obtiene la respuesta puede hacer que su tiempo sea “CUTC”.Un gran
problema es que el tiempo no puede correr hacia atrás:• “CUTC” no puede ser
menor que el tiempo actual “C” del emisor.• La atención del requerimiento en el
servidor de tiempos requiere un tiempo del manejador de interrupciones.•
También se debe considerar el tiempo de transmisión. El cambio del reloj se
debe introducir de manera global:• Si el cronómetro genera 100 interrupciones
por segundo:
Cada
interrupción añade 10 mseg al tiempo.
Para
atrasar solo agregaría 9 mseg.
Para
adelantar agregaría 11 mseg.
La
corrección por el tiempo del servidor y el tiempo de transmisión se hace
midiendo en el emisor:• El tiempo inicial (envío) “T0”.• El tiempo final
(recepción) “T1”.• Ambos tiempos se miden con el mismo reloj. El tiempo de
propagación del mensaje será (T1 - T0) / 2. Si el tiempo del servidor para
manejar la interrupción y procesar el mensaje es “I”:• El tiempo de propagación
será (T1 - T0 - I) / 2. Para mejorar la precisión:• Se toman varias
mediciones.• Se descartan los valores extremos.• Se promedia el resto. El tiempo
de propagación se suma al tiempo del servidor para sincronizar al emisor cuando
éste recibe la respuesta.
Algoritmo de Berkeley
En el algoritmo de Cristian el
servidor de tiempo es pasivo. En el algoritmo de Berkeley el servidor de
tiempo:• Es activo.• Realiza un muestreo periódico de todas las máquinas para
preguntarles el tiempo.• Con las respuestas:
Calcula
un tiempo promedio.
Indica
a las demás máquinas que avancen su reloj o disminuyan la velocidad del mismo
hasta lograr la disminución requerida.
Es
adecuado cuando no se dispone de un receptor UTC.
Algoritmos con Promedio
Los anteriores son algoritmos
centralizados. Una clase de algoritmos descentralizados divide el tiempo en
intervalos de resincronización de longitud fija:• El i -ésimo intervalo:
Inicia
en “T0 + i R” y va hasta “T0 + (i + 1) R”.
“T0”
es un momento ya acordado en el pasado.
“R” es
un parámetro del sistema.
Al inicio
de cada intervalo cada máquina transmite el tiempo actual según su reloj.
Debido a la diferente velocidad de los relojes las transmisiones no serán
simultáneas. Luego de que una máquina transmite su hora, inicializa un
cronómetro local para reunir las demás transmisiones que lleguen en cierto
intervalo “S”.Cuando recibe todas las transmisiones se ejecuta un algoritmo
para calcular una nueva hora para los relojes. Una variante es promediar los
valores de todas las demás máquinas. Otra variante es descartar los valores
extremos antes de promediar (los “m” mayores y los “m” menores). Una mejora al
algoritmo considera la corrección por tiempos de propagación.
Varias Fuentes Externas de Tiempo
Los sistemas que requieren una
sincronización muy precisa con UTC se pueden equipar con varios receptores de
UTC. Las distintas fuentes de tiempo generaran distintos rangos (intervalos de
tiempo) donde “caerán” los respectivos UTC, por lo que es necesaria una
sincronización. Como la transmisión no es instantánea se genera una cierta
incertidumbre en el tiempo. Cuando un procesador obtiene todos los rangos de
UTC:• Verifica si alguno de ellos es ajeno a los demás y de serlo lo descarta
por ser un valor extremo.• Calcula la intersección (en el tiempo) de los demás
rangos.• La intersección determina un intervalo cuyo punto medio será el UTC y
la hora del reloj interno. Se deben compensar los retrasos de transmisión y las
diferencias de velocidades de los relojes. Se debe asegurar que el tiempo no
corra hacia atrás. Se debe resincronizar periódicamente desde las fuentes
externas de UTC.
Exclusión Mutua
Cuando un proceso debe leer o
actualizar ciertas estructuras de datos compartidas:• Primero ingresa a una
región crítica para lograr la exclusión mutua y garantizar que ningún otro
proceso utilizará las estructuras de datos al mismo tiempo. En sistemas
monoprocesadores las regiones críticas se protegen con semáforos, monitores y
similares. En sistemas distribuidos la cuestión es más compleja.
Un Algoritmo Centralizado
La forma más directa de lograr la
exclusión mutua en un sistema distribuido es simular a la forma en que se lleva
a cabo en un sistema monoprocesador. Se elige un proceso coordinador. Cuando un
proceso desea ingresar a una región crítica:• Envía un mensaje de solicitud al
coordinador:
Indicando
la región crítica.
Solicitando
permiso de acceso.
• Si
ningún otro proceso está en ese momento en esa región crítica:
El
coordinador envía una respuesta otorgando el permiso.
• Cuando
llega la respuesta el proceso solicitante entra a la región crítica. Si un
proceso pide permiso para entrar a una región crítica ya asignada a otro proceso:•
El coordinador no otorga el permiso y encola el pedido. Cuando un proceso sale
de la región crítica envía un mensaje al coordinador para liberar su acceso
exclusivo:• El coordinador extrae el primer elemento de la cola de solicitudes
diferidas y envía a ese proceso un mensaje otorgando el permiso, con lo cual el
proceso queda habilitado para acceder a la región crítica solicitada. Es un
esquema sencillo, justo y con pocos mensajes de control. La limitante es que el
coordinador puede ser un cuello de botella y puede fallar y bloquear a los
procesos que esperan una respuesta de habilitación de acceso.
Un Algoritmo Distribuido
El objetivo es no tener un único
punto de fallo (el coordinador central). Un ej. es el algoritmo de Lamport
mejorado por Ricart y Agrawala. Se requiere un orden total de todos los eventos
en el sistema para saber cuál ocurrió primero. Cuando un proceso desea entrar a
una región crítica:• Construye un mensaje con el nombre de la región crítica,
su número de proceso y la hora actual.• Envía el mensaje a todos los demás
procesos y de manera conceptual a él mismo.• Se supone que cada mensaje tiene
un reconocimiento. Si el receptor no está en la región crítica y no desea
entrar a ella, envía de regreso un mensaje o.k. al emisor. Si el receptor ya
está en la región crítica no responde y encola la solicitud. Si el receptor
desea entrar a la región crítica pero aún no lo logró, compara:• La marca de
tiempo del mensaje recibido con,• La marca contenida en el mensaje que envió a
cada uno.• La menor de las marcas gana.• Si el mensaje recibido es menor el
receptor envía un o.k.• Si su propio mensaje tiene una marca menor el receptor
no envía nada y encola el pedido. Luego de enviar las solicitudes un proceso:•
Espera hasta que alguien más obtiene el permiso.• Cuando llegan todos los
permisos puede entrar a la región crítica. Cuando un proceso sale de la región
crítica:• Envía mensajes o.k. a todos los procesos en su cola.• Elimina a todos
los elementos de la cola. La exclusión mutua queda garantizada sin bloqueo ni
inanición. El número de mensajes necesarios por entrada es “2(n - 1)”, siendo
“n” el número total de procesos en el sistema. No existe un único punto de
fallo sino “n”:• Si cualquier proceso falla no responderá a las solicitudes.•
La falta de respuesta se interpretará como negación de acceso: o Se bloquearán
los siguientes intentos de los demás procesos por entrar a todas las regiones
críticas. Se incrementa la probabilidad de fallo en “n” veces y también el
tráfico en la red. Se puede solucionar el bloqueo si:• El emisor espera y sigue
intentando hasta que regresa una respuesta o,• El emisor concluye que el destinatario
está fuera de servicio. Otro problema es que:• Se utilizará una primitiva de
comunicación en grupo o,• Cada proceso debe mantener la lista de miembros del
grupo, incluyendo los procesos que ingresan, los que salen y los que fallan.•
Se complica para gran número de procesos. Un importante problema adicional es
que:• Todos los procesos participan en todas las decisiones referentes a las
entradas en las regiones críticas.• Se sobrecarga el sistema. Una mejora
consiste en permitir que un proceso entre a una región crítica con el permiso
de una mayoría simple de los demás procesos (en vez de todos):• Luego de que un
proceso otorgó el permiso a otro para entrar a una región crítica, no puede
otorgar el mismo permiso a otro proceso hasta que el primero libere su permiso.
Algoritmos de Elección
Son los algoritmos para la
elección de un proceso coordinador, iniciador, secuenciador, etc.. El objetivo
de un algoritmo de elección es garantizar que iniciada una elección ésta
concluya con el acuerdo de todos los procesos con respecto a la identidad del
nuevo coordinador.
