Reloges logicos

Universidad Politécnica de
GÓMEZ PALACIO

Sistemas Operativos

Presentado por

NAFTEL OVALLE MARMOLEJO

CARRERA:

INGENIERÍA EN TECNOLOGÍAS DE INFORMACIÓN

RELOJES LOGICOS
Lamport inventó un mecanismos simple por el que la relación sucedió antes puede capturarse numéricamente, denominado reloj lógico. Un reloj lógico de Lamport es un contador software que se incrementamonótonamente, cuyos valores no necesitan tener ninguna relación particular con ningún reloj físico.
No podemos inferir que los valores del reloj dado son aquéllos inmediatamente después del suceso para el que son adyacentes.
RELOJES LÓGICOS TOTALMENTE ORDENADOS.
Algunos pares de sucesos distintos, generados por diferentes procesos, tiene marcas de tiempo de Lamport numéricamente idénticas. Sin embargo,podemos crear un orden sobre los sucesos, esto es, uno para el que todos los pares de sucesos distintos están ordenados, teniendo en cuenta los identificadores de los procesos en los que ocurren los sucesos.
Lamport la utilizó, para ordenar la entrada de procesos en una sección crítica.
RELOJES VECTORIALES.
Mattern y Fidge desarrollaron relojes vectoriales para vencer la deficiencia de losrelojes de Lamport, del hecho que no podemos deducir que un reloj vectorial para un sistema de N procesos es un vector de N enteros.
Cada proceso mantiene su propio reloj vectorial Vi, que utiliza para colocar marcas de tiempo en los sucesos locales. Como las marcas de tiempo de Lamport, cada proceso adhiere el vector de marcas de tiempo en los mensajes que envía al resto, y hay unas reglas sencillaspara actualizar los relojes.
Los vectores de marcas de tiempo tienen la desventaja, comparados con las marcas de tiempo de Lamport, de precisar una cantidad de almacenamiento y de carga real de mensajes que es proporcional a N, el número de procesos. Charron Bost mostró que, si somos capaces de decir N es inevitable. Sin embargo, existen técnias para almacenar y transmitir cantidades más pequeñasde datos, a costa del procedimiento precisado para reconstruir los vectores completos. Raynal y Singha dan cuenta de algunas de estas técnicas. También describen la noción de relojes matricules, en que los procesos mantienen estimaciones de los vectores de tiempo de otros procesos así como las suyas propias.
ESTAMPA DE TIEMPO
Una estampa de tiempo es un identificador simple que sirve paraidentificar cada transacción de manera única. Otra propiedad de las estampas de tiempo es la monoticidad, esto es, dos estampas de tiempo generadas por el mismo administrador de transacciones deben ser monotonicamente crecientes. Así, las estampas de tiempo son valores derivados de un dominio totalmente ordenado.

Figura 6.5. Comunicación en candados de dos fases distribuidos.
Existen varias formasen que las estampas de tiempo se pueden asignar. Un método es usar un contador global monotonicamente creciente. Sin embargo, el mantenimiento de contadores globales es un problema en sistemas distribuidos. Por lo tanto, es preferible que cada nodo asigne de manera autónoma las estampas de tiempos basándose en un contador local. Para obtener la unicidad, cada nodo le agrega al contador su propioidentificador. Así, la estampa de tiempo es un par de la forma
<contador local, identificador de nodo>
Note que el identificador de nodo se agrega en la posición menos significativa, de manera que, éste sirve solo en el caso en que dos nodos diferentes le asignen el mismo contador local a dos transacciones diferentes.
El administrador de transacciones asigna también una estampa de tiempo atodas las operaciones solicitadas por una transacción. Más aún, a cada elemento de datos x se le asigna una estampa de tiempo de escritura, wts(x), y una estampa de tiempo de lectura, rts(x); sus valores indican la estampa de tiempo más grande para cualquier lectura y escritura de x, respectivamente.
El ordenamiento de estampas de tiempo (TO) se realiza mediante la siguiente regla:
Regla TO:...