07 Ambientes informaticos distribuidos Flashcards
Concurrencia distribuida
Hasta ahora estudiamos la concurrencia en sistemas mono y multiprocesador. En este capítulo vamos a estudiar las consideraciones que hay que tener en cuenta a la hora de estudiar el problema de la sección crítica en ambientes distribuidos.
En los ambientes distribuidos hay 3 algoritmos que sirven para lograr la exclusión mutua: centralizado, distribuido y token ring.
[explicar los 3]
[explicar 2 alg. de eleccion - bully, ring]
Todo lo estudiado hasta ahora necesita meterse en el bajo nivel. Lo idea para trabajar en sistemas distribuidos es armar alguna abstracción que permita hacer uso del sistema sin tener que preocuparse por esos detalles. En esta línea de razonamiento es que estudiamos las Transacciones. En el modelo transaccional, el sistema está formado por un cjto. de procesos independientes, donde cada uno puede fallar aleatoriamente; los errores son manejados por la capa de comunicación y hay un almacenamiento estable que se suele implementar con duplicaciones. Las primitivas de las transacciones son begin, abort y end transaction, read y write. Las propiedades del sistema cumplen las famosas siglas ACID (atomic, consistente, isolated, durable). Respecto de su implementación, estudiamos los casos de Workspace privado [mencionar mejora en que se puede copiar solamente los inodos necesarios] y writeahead log. Por último, para realizar el commit de una transacción, hay se recurre al commit en dos fases, en que […] [es robusto ante crashes].
Cuando múltiples transacciones se están ejecutando en simultáneo, es necesario integrar algún mecanismo de control de concurrencia. En la materia estudiamos 3 de ellos: Locking [granularidad, two-phase locking y strict 2pl, deadlock], concurrencia optimista y timestamps. […]
Finalmente, como vimos que puede haber deadlock en la adquisicion de Locks, introducimos mecanismos de deteccion y prevencion de deadlocks. Para la detección estudiamos una solución centralizada y otra distribuida. En la solución centralizada hay un nodo coordinador que mantiene el estado general del grafo. Si bien es muy simple, puede suceder que los msjs lleguen desordenados generando un falso deadlock, pero esto se puede solucionar con los relojes de Lamport. El algoritmo distribuido consiste en lo siguiente. Cuando un proceso desea esperar por un recurso, debe enviar un probe message a él o los procesos que posean dicho recurso. El mensaje que envía contiene tres números: el proceso que se acaba de bloquear, el proceso que envía el mensaje y el proceso al cual se lo está enviando. Cuando le llega un mensaje, el receptor chequea si él mismo se encuentra esperando por algún recurso. Si ese es el caso, el mensaje es actualizado, manteniendo el primer número pero modificando el segundo por su propio número y el tercero por el número del proceso del cual espera el recurso. Luego, le envía el mensaje a este proceso al cual espera. Si el mensaje da toda la vuelta retornando al emisor original, hay un ciclo y el sistema presenta un deadlock. Existen varias formas de romper el deadlock. Una posible solución sería que el emisor original se suicide. Sin embargo, esto tiene un problema cuando varios procesos ejecutan el algoritmo en simultáneo, ya que varios procesos podrían terminar muertos innecesariamente; con uno de ellos alcanza. Una posible alternativa, entonces, es tener un campo más en el probe message que liste la identidad de todos los procesos por los cuales pasó el mensaje (cada proceso se va agregando a esta lista); luego, ante la presencia de un deadlock, se mata únicamente al proceso con el número más alto. Si varios procesos ejecutan el algoritmo al mismo tiempo, la víctima final será la misma.
Prevencion
La prevención de deadlocks consiste en diseñar al sistema de forma tal de que sea imposible estructuralmente de que existan deadlocks. Los algoritmos que veremos a continuación son para sistemas distribuidos y ambos se basan en la idea de asignar a cada proceso un timestamp en el momento en el que empiezan. [wait - die, wound-wait]
Ambientes informaticos distribuidos.
Finalmente está el tema de los ambientes informáticos distribuidos. Los ambientes inf. dist. están formados por Entidades, que son la unidad de cómputo del ambiente informático distribuido y puede ser un proceso o un procesador. Cada una de las entidades cuenta con acceso de lectura y escritura a una memoria local privada (no compartida con otras entidades), que a su vez contiene registros de estado y de valor. Las entidades pueden realizar las siguientes operaciones: pueden realizar procesamiento local, pueden comunicarse con otras entidades por medio de mensajes, y finalmente también pueden setear y resetear un reloj local. Habiendo presentado las operaciones que puede realizar una entidad, cabe destacar que la misma es de carácter reactivo, es decir que reacciona a estímulos externos. Estos estímulos se pueden generar dentro de los límites del sistema (pero fuera de la entidad), como los arribos de mensajes y que suene la alarma del reloj, o bien se pueden generar por fuera de los límites del sistema, como un impulso espontáneo. Según el libro, los impulsos espontáneos son vistos por las entidades como actos de Dios, es decir, no ocurren imprevisiblemente, y cuando ocurren, disparan el envío de mensajes e inicio de cómputo. Concretamente, el ejemplo que plantea el libro es el de un banco, en el que los servidores y los ATMs son entidades, y un impulso espontáneo es la acción de un usuario que quiere retirar dinero en un momento dado. Las entidades no tienen control sobre eso, no saben cuándo sucederá, pero cuando sucede, se disparan todo tipo de mensajes y cómputos. Esos mensajes y cómputos que se disparan al recibir un impulso espontáneo se llaman acciones. Las acciones son atómicas y finitas, ya que una vez que arranca la secuencia de operaciones, se van a ejecutar sin interrupción y hasta el final. Notar que si bien decimos que una entidad responde a un impulso espontáneo con una acción, una posible acción es la acción nula, que consiste en no reaccionar. La relación entre el evento que ocurre y el estado en que se encuentra una entidad al momento de recibir el evento se llama regla. Notar que para cada posible evento y estado, debe existir una única regla. Finalmente, todo el set de reglas que debe obedecer una entidad se llama Comportamiento, Protocolo o Algoritmo distribuido. El comportamiento colectivo es homogéneo si todas las entidades que lo componen tienen el mismo comportamiento. Notar que hay una propiedad que indica que todo comportamiento colectivo se puede transformar en homogéneo. El ejemplo que plantea el libro es el siguiente: por más que un comportamiento colectivo sea heterogéneo, se lo puede transformar en homogéneo escribiendo una nueva entidad con el comportamiento de ambos sistemas, pero controlando cuál de los dos ejecutar mediante un if que chequea qué entidad está ejecutando.
1.2 Ahondando en la comunicación entre entidades: las entidades se comunican por medio de mensajes, que en el fondo son simples secuencias de bits finitas. Una entidad no necesariamente se puede comunicar con cualquier otra entidad del sistema. Es por ello que tiene sentido mantener una topología de la red de posibles conexiones mediante un grafo dirigido.
1.3 Habiendo definido las principales partes de un ambiente informático distribuido, es importante presentar los dos axiomas dominantes: en primer lugar está el axioma de delays de comunicación finitos, que establece que de no haber fallas en el sistema, un mensaje va a llegar a destino en algún momento. En segundo lugar está el axioma de orientación local, que establece que una entidad puede distinguir entre sus vecinos de entrada y de salida, es decir que puede distinguir qué vecino le envía un mensaje, y puede también enviar un mensaje a un destino determinado.
Algunas características y propiedades del sistema pueden ser aprovechadas para resolver algún problema en particular. Esto se logra al introducir estas características dentro del set de reglas. Notar que al aprovechar estas reglas, se restringe naturalmente la aplicabilidad del protocolo, por lo que esto recibe el nombre de restricción. Entre ellas se encuentran propiedades de la comunicación, confiabilidad y sincronismo. Nosotros estudiamos las restricciones de comunicación, topológicas, de confiabilidad y temporales. En las restricciones de comunicación están el ordenamiento de mensajes, que establece que en ausencia de fallas, los mensajes que transmite una entidad llegan al destino en el mismo orden en que fueron enviados; por otro lado, si un sistema tiene todas las líneas de tipo full duplex, entonces vale la comunicación recíproca que establece que si existe (x,y) en E, entonces también existe (y,x) en E, siendo E el cjto. de arcos del grafo dirigido. Un sistema en el que hay enlaces duplex en que (x,y) = (y,x), tiene también enlaces bidireccionales. Respecto de la topología, la topología de comunicación del grafo del sistema es fuertemente conexo. Respecto de las restricciones de confiabilidad, se pueden nombrar la detección de falla de enlace, que establece que las entidades se dan cuenta si se cae un enlace entre ellas, detección de falla de la entidad, que establece que las entidades se dan cuenta si alguno de los vecinos se cayó, entrega garantizada, que establece que cualquier mensaje enviado será recibido con su contenido intacto, y confiabilidad parcial y total, que establecen que no ocurrirán fallas o que no han ni ocurrirań fallas. Respecto de las restricciones temporales, se establece que los delays de comunicación son acotados por una constante delta, que los delays de comunicación en ausencia de fallas es igual a unidad de tiempo, y que todos los relojes locales se incrementan simultáneamente y el intervalo de incremento es constante.
1.4 Las medidas de comparación de los algoritmos distribuidos son el costo y la complejidad. El costo se puede medir como cantidad de mensajes enviados y recibidos (M), M/entidad o M/link. El tiempo, en cambio, puede referir al tiempo ideal o real total de ejecución del protocolo.
1.5 Para entender mejor los conceptos planteados hasta ahora, el libro nos brinda un ejemplo de broadcasting que establece que al ejecutar el protocolo, todas las entidades tendrán la información al cabo de un tiempo finito, y que cualquiera de las entidades puede iniciar la difusión de info. Para simplificar el problema, asumimos las siguientes restricciones: hay enlaces bidireccionales, es decir que el grafo no es dirigido, no hay fallas en el sistema, el grafo es conexo y finalmente que una única entidad arranca la difusión de información. Una primera solución a este problema establece que el nodo initiator debe enviar un mensaje en caso de recibir un impulso espontáneo, pero no debe realizar nada en caso de recibir un mensaje; el resto de los nodos deben reenviar el mensaje recibido en caso de recibir un mensaje, pero no realizan nada en caso de recibir un impulso espontáneo. Esta solución tiene el problema de que es posible que suceda que los mensajes queden rebotando entre las distintas entidades. Para solucionar esta falencia, se introducen cambios de estado, de forma que después de haber recibido un mensaje, los nodos cambian su estado a done. Adicionalmente, se introduce la regla de que si alguien está en estado done y recibe algún mensaje o impulso espontáneo, entonces no reacciona. Esta solución es correcta, pero tiene la ineficiencia fácilmente evitable de reenviarle el mensaje al nodo que le acaba de transmitir ese mismo mensaje. Si se evita eso, en lugar de enviar 2m msjs, se puede lograr enviar solamente 2m - n + 1.
1.6 Los eventos desencadenan acciones en un tiempo futuro. Los distintos delays resultan en distintas ejecuciones del protocolo con posibles resultados diferentes. Los eventos disparan acciones que pueden generar nuevos eventos. Si suceden, los nuevos eventos ocurrirán en un tiempo futuro. Finalmente, una ejecución se describe por la secuencia de eventos que ocurrieron.
Respecto de los estados de las entidades, se establece que si una entidad recibe el mismo evento en dos ejecuciones distintas, y s1 y s2 son estados internos, si s1=s2 -> el nuevo estado interno de la entidad será el mismo en ambos casos. Del mismo modo, si un evento ocurre en dos entidades cuyos estados internos son s1 y s2, y s1 = s2, entonces el nuevo estado interno de las entidades será el mismo.
Ahora bien, para describir el estado global del entorno en un tiempo t, es necesario tomar en cuenta el estado de todas las entidades al tiempo t, además de las ejecuciones producidas a partir de eventos que todavía no lograron ejecutarse. Esto se llama Configuración. Las configuraciones son como fotos del sistema en un tiempo t.
Para dar cierre a esta parte de la materia, se pueden definir tres niveles y tres tipos de conocimiento. Los niveles de conocimiento se distinguen entre local, implícito y explícito. Los tipos son: información métrica, que se información numérica sobre la red, como podrían ser la cantidad de nodos y aristas del grafo, diámetro, etc., propiedades topológicas, que es el conocimiento sobre las propiedades de la topología, es decir si es grafo es un anillo, si es acíclico, etc., y finalmente están los mapas topológicos, es decir, un mapa de la vecindad de la entidad hasta una distancia d, como puede ser una matriz de adyacencia del grafo.
