Cierre Iv

Actividad de cierre lV
Sistemas Concurrentes y Distribuidos Secc: D04
Gutiérrez Salmerón Martha del Carmen
Universidad De Guadalajara
Centro Universitario de Ciencias Exactas e Ingenierías

Relojes físicos y relojes lógicos.

En un sistema distribuido consiste en garantizar que los procesos se ejecuten de forma cronológica y a la misma vez respetar el orden de los eventos dentro del sistema.

-Algoritmo de Cristian
-El algoritmo de Berkeley
-Algoritmos con promedio
-Varias fuentes externas de tiempo

-El algoritmo del grandulón
-Un algoritmo de anillo

Un proceso anuncia que desea comenzar una transacción con uno o más procesos. Pueden negociar varias opciones, crear y eliminar objetos y llevar a cabo ciertas operaciones durante unos momentos. Entonces, el iniciador anuncia que dcsea que todos los demás se comproinetan con el trabajo realizado hasta entonces. Si todos coinciden, los resultados se vuelven permanentes. Si uno o más procesos se niegan (o fallan antes de expresar su acuerdo), entonces la situación regresa al estado que presentaba antes de comenzar la transacción, sin que existan efectos colaterales en los objetos, archivos, bases de datos, etc.

1. Si a y b son eventos en el mismo proceso y a ocurre antes de b, entonces a -> b es verdadero.
2. Si a es el evento del envío de un mensaje por un proceso y b es el evento de la recepción del mensaje por otro proceso, entonces a -> b también es verdadero. Un mensaje no se puede recibir antes de ser enviado o al mismo tiempo en que se envía, puesto que tarda en llegar una cantidad finita de tiempo.

Para la asignación a eventos. Consideremos los tres procesos, los procesos se ejecutan en diferentes máquinas, cada una con su propio reloj y velocidad. Cada reloj corre a una razón constante, sólo que las razones son diferentes debido a las diferencias en los cristales. El tiempo que tarda este mensaje en llegar depende del reloj elegido. Por lo tanto, cada mensaje trae consigo el tiempo de envío, de acuerdo con el reloj del emisor. Cuando un mensaje llega y el reloj del receptor muestra un valor anterior al tiempo en que se envió el mensaje, rápidamente el receptor adelanta su reloj para que tenga una unidad más que el tiempo de envío.

El del anillo de fichas transfiere el control a lo largo del anillo. Cada uno tiene sus puntos fuertes y sus puntos débiles. Muchos algoritmos distribuidos necesitan un coordinador, por lo que vimos dos formas para la elección de éste, el algoritmo del grandulón y otro algoritmo de anillo. Aunque io anterior es interesante e importante, todos son conceptos de bajo nivel. Las transacciones son un concepto de alto nivel que facilita a los programadores el manejo de la exclusión mutua, las cerraduras, la tolerancia de fallas y los bloqueos en un sistema distribuido.

1. El algoritmo del grandulón
2. Un algoritmo de anillo

1. La información relevante se distribuye entre varias máquinas.
2. Los procesos toman las decisiones sólo con base en la información disponible en forma local.
3. Debe evitarse un punto de fallo en el sistema.
4. No existe un reloj común o alguna otra fuente precisa del tiempo global.

A pesar del uso generalizado de la palabra "reloj" para hacer referencia a dichos dispositivos, en realidad no son relojes en el sentido usual. Cronómetro sería una mejor palabra. Un cronómetro de computadora es por lo general un cristal de cuarzo trabajado con precisión. A cada cristal se le asocian dos registros, un contador y un registro mantenedor. Cada oscilación del cristal disminuye en 1 al contador. Cuando el contador toma el valor O, se genera una interrupción y el contador se vuelve a cargar mediante el registro mantenedor.

Cuando existe la restricción adicional de que los relojes no sólo deben ser iguales, sino que además no se desvíen del tiempo real más allá de cierta magnitud, los relojes reciben el nombre de relojes físicos.

Un cronómetro genera una interrupción 60 veces por cada segundo o con cualquier frecuencia que se desee. Cada interrupción recibe el nombre de marca de reloj.

Cuando un sistema tiene n computadoras, los n cristales correspondientes oscilarán a tasas un poco distintas, lo que provoca una pérdida de sincronía en los relojes (de software) y que al leerlos tengan valores distintos. La diferencia entre los valores del tiempo se llama distorsión del reloj.

1. P envía un mensaje ELECCIÓN a los demás procesos con un número mayor.
2. Si nadie responde, P gana la elección y se convierte en el coordinador.
3. Si uno de los procesos con un número mayor responde, toma el control. El trabajo de P termina.

Un método por completo distinto para lograr la exclusión mutua en un sistema distribuido. Aquí tenemos una red basada en un bus, sin un orden inherente en los procesos. En software, se construye un anillo lógico y a cada proceso se le asigna una posición en el anillo. Las posiciones en el anillo se pueden asignar según el orden numérico de las direcciones de la red o mediante algún otro medio. No importa cómo sea el orden. Lo importante es que cada proceso sepa quién es el siguiente en la fila después de él. Al iniciar el anillo, se le da al proceso O una ficha, la cual circula en todo el anillo. Se trasfiere del proceso k al proceso k+ 1 (módulo el tamaño del anillo) en mensajes puntuales. Cuando un proceso obtiene la ficha de su vecino, verifica si intenta entrar a una región critica. En ese caso, el proceso entra a la región, hace todo el trabajo necesario y sale de la región. Después de salir, pasa la ficha a lo largo del anillo. No se permite entrar a una segunda región critica.

Otro algoritmo de elección se basa en el uso de un anillo, sólo que, a diferencia del anillo anterior, éste no utiliza una ficha. Suponemos que los procesos tienen un orden, físico o lógico, de modo que cada proceso conoce a su sucesor. Cuando algún proceso observa que el coordinador no funciona, construye un mensaje ELECCIÓN con su propio número de proceso y envía el mensaje a su sucesor. Si éste está inactivo, el emisor pasa sobre el sucesor y va hacia el siguiente número del anillo o al siguiente de éste, hasta que localiza un proceso en ejecución. En cada paso, el emisor añade su propio número de proceso a la lista en el mensaje.

Muchos de los algoritmos distribuidos necesitan que un proceso actúe como coordinador, iniciador, secuenciador o que desempeñe de cierta forma algún papel especial. En general, no importa cuál de los procesos asuma esta responsabilidad especial, pero uno de ellos debe hacerlo. En esta sección analizaremos los algoritmos para la elección de un coordinador (utilizaremos éste como nombre genérico del proceso especial).

La exclusión mutua es una propiedad de control de concurrencia que se introduce para evitar condiciones de carrera. Es el requisito de que un proceso no puede ingresar a su sección crítica mientras otro proceso concurrente está actualmente presente o ejecutándose en su sección crítica, es decir, solo se permite que un proceso ejecute la sección crítica en un momento dado.

Hasta hace poco, se dispone del hardware y software necesarios para la sincronización de relojes a gran escala (es decir, en todo Internet). Con esta nueva tecnología, es posible mantener millones de relojes sincronizados con UTC, con precisión de unos cuantos milisegundos. Apenas comienzan a aparecer nuevos algoritmos que utilizan relojes sincronizados.