Práctica DE Coordinación Distribuida - Sistemas Distribuidos PDF

Preview

Summary

Solucion Posible a Practica de coordinacion distribuida ...

Description

PRÁCTICA DE COORDINACIÓN DISTRIBUIDA 1. ¿Cuáles son las asunciones respecto a los canales de comunicación?    

Sistema asíncrono Los procesos no fallan La entrega de mensajes es fiable Los procesos acceden a los recursos a través de una SC

2. ¿Qué es la exclusión mutua y la exclusión mutua distribuida?  

Exclusión mutua: el acceso a la sección crítica se regula por medio de variables compartidas, por ejemplo semáforos. Exclusión mutua distribuida: el acceso a la sección crítica se basa en paso de mensajes.

3. ¿Qué requisitos debe cumplir la exclusión mutua?  

EM1: Seguridad A lo sumo un proceso puede estar ejecutándose a la vez en la SC

  

EM2: Pervivencia Las peticiones de entrada/salida de la SC al final son concedidas Sin interbloqueos ni inanición

 

EM3: Ordenación Si una petición para entrar en la SC ocurrió “antes que” otra, entonces la entrada en la SC se garantiza en ese orden

4. ¿Cuáles son los criterios de evaluación de la exclusión mutua?  

Ancho de banda consumido Proporcional al número de mensajes enviados en cada operación de entrada y salida de la SC

 

Retraso del cliente Cuánto tarda en entrar y salir de la SC

 

Retraso en la sincronización Tiempo que pasa entre que un cliente sale de la SC y el siguiente que esté esperando entra Proporcional al número de mensajes necesarios entre la salida de un proceso de la SC y la entrada del siguiente proceso c



5. ¿Por qué es provechoso el uso de relojes lógicos en lugar de los relojes físicos? La idea de un reloj lógico consiste en crear un sistema de convergencia del tiempo mediante la medición de las derivas, de tal suerte que la noción de tiempo universal se sustituye por la noción de un tiempo global auto-ajustable. Los relojes lógicos son útiles para ordenar eventos en ausencia de un reloj común. 6. Menciona la diferencia entre el algoritmo de Christian y el algoritmo de Berkeley. Algoritmo de Berkeley Es un algortimo centralizado utiliza un servidor maestro.es que va a generar la sincronia pide periodicamente a las otra computadores que en este caso van a ser esclavas sus relojes

calcula la diferencia o sea el desvio de su reloj para sincronizar es mas envia su propio reloj y luego de los otros relojes esclavos y saca el promedio para sincronizar. no toma en cuenta el tiempo UTC y solo es local. En cambio el algoritmo de Cristian utiliza un servidor de tiempo para poder sincronizar computadores. atraves de la señal UTC. 7. Se tiene tres procesos P1, P2 y P3, representa algún ejemplo de la planificación de los procesos siguiendo el algoritmo de “ocurre antes de”. 8. ¿Cuál es la complicación del algoritmo de anillo de Chang y Roberts?  

La primera, que el fallo de cualquiera de los nodos provocará el fallo del sistema completo, ya que romperá el anillo circular con el que se conectan todos los nodos. La segunda, que no se consigue el acceso en el orden en el que los nodos se añaden al anillo, ya que dependerá del lugar donde se encuentre el testigo. Si el testigo se encuentra en el lado contrario del anillo al lugar donde se introduce un nuevo nodo puede ser que dicho nodo reciba el permiso para acceder a la sección crítica después que otro que se haya incluido posteriormente, si este último se introdujo entre el testigo y el primero.

9. ¿Cuáles son las desventajas del algoritmo de Ricart y Agrawala? Puede producirse el fallo de cualquiera de los equipos y entonces no responder a las peticiones, lo que ocasionaría que se interpretara, de manera errónea, como la denegación de entrada a la sección crítica, bloqueando también todas las peticiones siguientes al fallo. Esto puede arreglarse si a los mensajes de petición siempre se responde con un ACK, de forma que si un equipo no contestara se consideraría que está caído y se le saca del grupo para evitar fallos. Otro posible fallo es el de entrar en la región crítica cuando se recibe el permiso de la mayoría de los procesos y no de todos en total. Para evitar este caso, en este algoritmo siempre es necesaria la respuesta de todos los demás nodos para entrar en la región crítica, es decir, un proceso se mantendrá a la espera hasta que no reciba (N-1) respuestas 10. ¿Cuál es la principal limitante del algoritmo centralizado? Sugiere una variante.

11. En el algoritmo del Grandulón, ¿qué pasa si dos procesos detectan la caída del coordinador de forma simultánea y ambos deciden hacer una elección?

1. p1 convoca elecciones al detectar la caída de p4. 2. p2 y p3 responden y continúan con el proceso. 3. p1 y p2 han recibido respuesta de p2, pero p3 caeantes de enviar coordinador p1 detecta la caída por el paso de timeout. 4. Continúa el proceso hasta que p2 se hace coordinador. 12. ¿Cómo se podría tolerar la falla del coordinador en un sistema centralizado? Mediante el uso de un testigo (token) que se envía por mensajes. No considera los tiempos locales en que se enviaron los mensajes. 13. ¿Cómo son afectadas las memorias cachés cuando se sincronizan los relojes internos de los procesadores de un sistema distribuido? 14. En el algoritmo de Ricart y Agrawala, ¿cómo se puede interpretar cuando un proceso falla y no responde a la solicitud de otro proceso para entrar a una región crítica? Puede producirse el fallo de cualquiera de los equipos y entonces no responder a las peticiones, lo que ocasionaría que se interpretara, de manera errónea, como la denegación de entrada a la sección crítica, bloqueando también todas las peticiones siguientes al fallo. Esto puede arreglarse si a los mensajes de petición siempre se responde con un ACK, de forma que

si un equipo no contestara se consideraría que está caído y se le saca del grupo para evitar fallos. Otro posible fallo es el de entrar en la región crítica cuando se recibe el permiso de la mayoría de los procesos y no de todos en total. Para evitar este caso, en este algoritmo siempre es necesaria la respuesta de todos los demás nodos para entrar en la región crítica, es decir, un proceso se mantendrá a la espera hasta que no reciba (N-1) respuestas 15. ¿Cuáles son los algoritmos de la exclusión mutua?   

Algoritmo con servidor central Algoritmo basado en anillo (token-ring) Algoritmo de Ricart y Agrawala

16. ¿Cuáles son las características del Algoritmo de Ricart y Agrawala?  

Cumple EM1, EM2 y EM3 (uso de relojes lógicos) Rendimiento o Ancho de banda  (N-1) mensajes de petición de entrada  (N-1) mensajes de concesión de entrada o Retraso de sincronización  1 mensaje (el del proceso actualmente en la SC) o Mejora: si un proceso entra en la SC y quiere volver a entrar, no debería reiniciar el protocolo si no ha recibido peticiones

17. ¿La siguiente figura a que algoritmo de exclusión mutua corresponde y cuál es su funcionamiento?

Corresponde al Algoritmo de Ricart y Agrawala.    

P1 multidifunde una petición para entrar en la SC, en su tiempo C1=41 P2, concurrentemente, multidifunde en su petición en su tiempo C2=34 P3 no esta interesado en la SC, asi que responde inmediatamente a ambos P1, observando que su tiempo lógico es mayor que el de P2, le responde o P2 no responde a P1, pero lo mantiene en cola para responderle cuando salga de la SC

18. ¿Cuál es el funcionamiento del Algoritmo de Maekawa? 19. ¿Cuáles son los Requisitos de la Elección distribuida? Requisitos E1: Seguridad Un proceso participante Pi tiene ei = ┴ o ei=P, donde P es el proceso con identificador mayor que no se ha caído al final de la ejecución del algoritmo de elección. E2: Pervivencia 



Todos los Procesos Pi participan y, al final, fijan ei ≠ ┴; o bien se han caído.

20. ¿En qué consiste el Algoritmo en anillo en Elección distribuida? ➢ Un proceso convoca elecciones y pasa su identificador al siguiente en el anillo • Si el identificador del proceso es mayor que el recibido, cambia el identificador • Cuando llega el mensaje al proceso convocante, finaliza la elección, transmitiendo en el mismo orden el identificador elegido 21. ¿Cuáles son las consideraciones En el Algoritmo abusón (bully) de la Elección distribuida? Consideraciones   

Permite la caída de procesos durante la elección o Utiliza timeouts para detectar fallos de procesos Supone comunicación fiable Cada proceso conoce qué procesos tienen identificadores mayores y puede comunicarse con ellos

22. ¿Cuáles es el funcionamiento resumido del Algoritmo abusón (bully) de la Elección distribuida? Funcionamiento resumido 1. El convocante envía mensajes elección a los procesos de id mayor 2. Si ninguno le respone, multidifunde que es el nuevo coordinador 3. Si alguno le responde, el convocante inicial queda en espera, y los procesos que responden inician un nuevo proceso de elección como convocantes (vuelta al paso 1) 23. ¿Cuál es el objetivo de la multidifusión? Objetivo: entrega de mensajes a un grupo de procesos distribuidos, garantizando  

Fiabilidad: todos los procesos del grupo reciben el mensaje Orden: el orden de entrega del mensaje es acordado y se respeta

24. ¿Cuáles son los tipos de multidifusión?   

Multidifusión básica Multidifusión fiable Multidifusión ordenada

25. ¿Cuáles la clasificación de la multidifusión ordenada?   

Ordenación FIFO: si un proceso realiza multicast(g,m) y luego multicast(g,m’), m debe entregarse siempre antes de m’ Ordenación causal: si multicast(g,m) → multicast(g,m’) entonces m debe entregarse siempre antes que m’ Ordenación total: si un proceso entrega m antes que m’, entonces todo proceso entrega m antes que m’. (este es por acuerdo de ISIS).

26. Encierre en un circulo V si el texto es verdadero F si es falso.

1

V

F

En el algoritmo de servidor central Un servidor concede los permisos para entrar en la SC.

2

V

F

En el algoritmo de servidor central considera los tiempos locales en que se enviaron los mensajes

3

V

F

El Algoritmo basado en anillo utiliza el Paso de testigos con la ayuda de un

servidor central 4

V

F

El Algoritmo de Ricart y Agrawala Cumple EM1, EM2 y EM3 gracias al uso de relojes lógicos.

5

V

F

La Elección distribuida es Elegir un proceso único para que tome un determinado rol.

6

V

F

El Algoritmo en anillo en la elección distribuida cumple E1 (seguridad), E2 (pervivencia) y E3 (ordenación).

7

V

F

Los tipos de mensajes del Algoritmo abusón en Elección distribuida solo: elección y respuesta.

8

V

F

En Algoritmo abusón Si un proceso sabe que tiene el id (no fallido) más alto Se elige a sí mismo coordinador enviando el mensaje coordinador a todos los de identificador más bajo (proceso abusón)

9

V

F

La Multidifusión fiable Debe cumplir con las condiciones de: Integridad, Validez y Acuerdo

1 0

V

F

Ordenación FIFO: si multicast(g,m) → multicast(g,m’) entonces m debe entregarse siempre antes que m’...