Práctica Sincronización de Sistemas Distribuidos (Sistemas Operativos)

De Cuba-Wiki
La versión para imprimir ya no se admite y puede contener errores de representación. Actualiza los marcadores del navegador y utiliza en su lugar la función de impresión predeterminada del navegador.

Plantilla:Back

Ejercicio 01:

Por ej: del nodo1 al nodo2, 8->10

Ejercicio 02:

En el enfoque centralizado de la exclusión mutua al recibir un mensaje de un proceso que está liberando su acceso exclusivo a la región crítica que estaba usando, el coordinador normalmente otorga permiso al primer proceso de la cola. Idear otro algoritmo posible para que lo use el coordinador.

Rta:
Otorgar el permiso al último proceso de la cola, establecer una cola de prioridad, mas corto primero, etc.

Ejercicio 03:

También sobre el caso centralizado de la exclusión mutua supongamos que el coordinador se cae. Provocará esto la caída del sistema ? De no ser así, en qué circunstancias pasará esto ? Existe alguna forma de evitar el problema y lograr que el sistema sea tolerante a fallas del coordinador ?

Rta:

Se produce la caída del sistena si existen procesos que requieren recursos para su ejecución, ya que al estar caído el coordinador no tienen forma de obtener esos permisos. En cambio si todos los procesos ya tienen permiso para acceder a los recursos necesarios para continuar su ejecución entonces no hacen uso del coordinador y el sistema seguiria en funcionamiento.

Para evitar el problema y lograr tolerancia a fallas se puede elejir un nuevo coordinador con algoritmos de elección (Cap 23 pag 7).

Ejercicio 04:

El algoritmo de Ricart y Agrawala tiene el problema de que si el proceso se cayó antes de responder al requerimiento de un proceso de ingresar a una región crítica, la falta de respuesta será interpretada como denegatoria de permiso. Se sugiere que todos los requerimientos sean respondidos inmediatamente para permitir fácilmente la detección de procesos caídos. Existe alguna circunstancia en la cual incluso esto sea insuficiente ? Discuta.

Si el proceso que no responde es el que tiene la region critica al momento de caerse, se cae en una inconsistencia en los datos al reasignar el uso de la region critica a otro proceso.

Ejercicio 05:

Un sistema distribuido puede tener múltiples regiones críticas independientes. Imagínese que el proceso 0 quiere ingresar a la región crítica A y el proceso 1 quiere la región crítica B. Puede el algoritmo de Ricart Agrawala llevar a un abrazo mortal ? Explique la respuesta.

Si la region critica A en algun momento necesita usar la region critica B y viceversa, puede llegar a suceder un deadlock, ya que cuando 1 va a pedir B, no puede acceder y queda bloqueado, lo mismo con el proceso 2 y A.

Ejercicio 06:

Supongamos que dos procesos detectan la muerte del coordinador y ambos deciden enviar un mensaje de elección usando el algoritmo Bully. Qué sucede ?

Queda como organizador el de mayor numero. Si el coordinador caido vuelve a levantarse, desplaza al elegido previamente.

Ejercicio 07:

Ejercicio 08:

Ejercicio 09:

Ejercicio 10:

Ejercicio 11:

Ejercicio 12:

Ejercicio 13:

Ejercicio 14:

Ejercicio 15:

Ejercicio 16:

Ejercicio 17:

El control de concurrencia con sellos temporales asegura la serializacion? Discuta.

Si una TR se inicio despues de la actual y hace el COMMIT, la TR actual se aborta y esto es lo que garantiza el orden correcto. Osea no se mezclan de forma incorrecta las TRs.

Ejercicio 18:

Ejercicio 19:

Ejercicio 20:

Un proceso con sello temporal 50 necesita un recurso retenido por un proceso con sello temporal 100, que sucede en :

a) espera-muere b) golpea-espera

a) como el sello temporal 50 es mas viejo, el proceso con sello 100 mantiene los recursos y el mas viejo (con 50) espera. b) el proceso viejo tiene derecho de prioridad, por lo que toma el recurso del proceso joven. Se puede porque hay transacciones y lo que ocurre es que se cancela la transaccion que involucraba al proceso joven.

Ejercicio 21:

Ejercicio 22:

Como se comparan los algoritmos de manejo de la exclusion mutua, el centralizado y el distribuido (Ricart y Agrawala), respecto del problema de un unico punto de falla?

Centralizado : tiene un unico punto de falla (el coordinador). Distribuido : tiene n puntos de fallas

Ejercicio 23:

Cuales de las siguientes propiedades no pertence a las transacciones atomicas:

  • a serialicidad
  • b la propiedad todo o nada
  • permanencia
  • sincronizacion
  • atomicidad
  • todos
  • ninguna

creo que ninguna, no se como se deduce la sincronizacion quiza de la serialicidad.

Ejercicio 24:

Marque cual (cuales) de las siguientes aserveraciones es falsa:

  • a) el COMMIT de una subtransaccion altera el mundo real en forma permanente
  • b) el COMMIT de una transaccion altera el mundo real en forma permanente
  • c) el ABORT de una transaccion solo afecta a ella y no a las subtransacciones disparadas por ella.
  • a) Falso, las subtransaccion son permanentes para el universo de la transaccion padre.
  • b) Verdadero, es la propiedad de durability de las TRs
  • c) Falso, cuando la TR hace ABORT las subtransacciones no tienen afecto.

Ejercicio 25:

Existe ROLLBACK en la implementacion de transacciones con espacio privado de trabajo? Justifique.

No existe, porque directamente se descarta el espacio.

Ejercicio 26:

Cual de los siguientes metodos de control de concurrencia esta libre de deadlock:

  • a) bloqueo
  • b) bloquedo de dos etapas
  • c) bloque de dos etapas estricto
  • d) control de concurrencia estricto
  • e) sellos temporales
  • a) No esta libre
  • b) No esta libre, se los TRs se ejecutan en orden inverso por ejemplo.
  • c) no esta libre (calculo)
  • d) LIBRE
  • e) LIBRE

Ejercicio 27:

Un proceso mas joven desea un recurso detenido por un proceso mas viejo. Que sucede si el esquema de prevencion de abrazo mortal utiliza la tecnica de wait-die? wound-wait?

  • wait-die : el proceso joven muere
  • wound-wait : el proceso espera.

Ejercicio 28:

Cuáles de los siguiente problemas ocurre en el algoritmo de Cristian (existe un servidor de tiempo con hora WWV)
para sincronizar relojes físicos :
a)- requiere sincronización global
b)- demora de propagación de la señal en el medio
c)- imposibilidad de retroceder el reloj global
d)- todas
e)- ninguna



Rta:

Los problemas que ocurren son:
b) Demora de la propagación de la señal en el medio.
c) Imposibilidad de retroceder el reloj global.(la idea para solucionar esto, es que el reloj avance mas lento hasta alcanzar la hora correcta).

Ejercicio 29:

Cuál de los siguientes algoritmos de sincronización de relojes físicos se basa en promedios de horas respecto de
los nodos cercanos a cada nodo con hora WWV ?
a)- Algoritmo de Cristian
b)- Algoritmo de Lamport
c)- Algoritmo Berkeley
d)- todos
e)- ninguno

Rta:
Creo que ninguno. Porque:
a) El algoritmo de Cristian si bien puede promediar la hora, no lo hace en base a los nodos cercanos, sino que pregunta repetidas veces a un servidor WWV.
b) El algortimo de Lamport es solo para sincronización de relojes lógicos.
c) El algoritmo de Berkeley, puede no existir máquina WWV.

Ejercicio 30:

Porque no es sencillo detectar la perdida del token en el algoritmo de token ring para el manejo de la exclusion mutua?

porque a lo mejor el proceso tarda mucho, problema de red. El problema esta mas que nada en que el tiempo de uso del token no esta acotado.

Ejercicio 31:

Ejercicio 32:

Ejercicio 33:

Ejercicio 34:

En el algoritmo Berkeley de sincronización de relojes físicos existe un demonio en el servidor de tiempo. Cuál es su función ? :
a)- enviar la hora a cada nodo de la red
b)- otorgar permisos para la administración de la exclusión mutua
c)- promediar las horas recibidas de todos y cada uno de los nodos
d)- realizar un promedio de las horas recibidas solo de los nodos cercanos
e)- todas
f)- ninguna

Rta:
La función del demonio de Berkeley es:
a) enviar la hora a cada nodo de la red.
c) promediar las horas recibidas de todos y cada uno de los nodos.

Ejercicio 35:

Que desicion toma un nodo que detecta la caida del coordinador en un esquema de eleccion Bully:

  • se auto elije coordinador
  • envia un mensaje de eleccion a todos los nodos con menor numeros que el propio.
  • todas
  • ninguna

Rta : ninguna. Autoelegirse no puede sin ser el de mayor numero disponible. enviar mensaje lo hace pero a los de MAYOR numero.

Ejercicio 36:

En el algoritmo de eleccion de coordinador token ring quien es el que decide cual es el nuevo coordinador?

  • cualquiero nodo que detecto la caida
  • el nodo de mayor numero activo en la instalacion
  • el nodo de menor numero acrivo en la instancias
  • todas
  • ninguna


Rta : el nodo de mayor numero activo en la instalacion.

Ejercicio 37:

Existe ROLLBACK en la implementacion de transacciones con log de grabacion anticipada? Justifique.

Si existe, y lo que se hace es revisar el log en forma inversa.

Ejercicio 38:

Ejercicio 39:

Ejercicio 40:

Si se utiliza la tecnica de bloqueo de dos etapas estricto cuando se liberan los bloqueos adquiridos por la transaccion?

  • en la fase de retraccion
  • al momento del commit
  • en la fase de crecimiento
  • todas
  • ninguna


Rta : al momento del commit

Ejercicio 41:

cual de los siguientes meotdos para la administracion de control de concurrencia brinda el maximo grado de paralelismo?

  • bloqueo
  • bloque de dos etapas
  • bloque de dos etapas estricto
  • control de concurrencia optimista
  • sellos temporales
  • todos
  • ninguna

Rta : el maximo lo brinda concurrencia optimista. bloque podria estar atras de optimista si tiene una granularidad alta (osea muy bajo nivel), pero optimista sigue siendo mejor ya que permite todo sin restriccion.

Ejercicio 42:

Indique verdadero o falso

  • a) cuando una transaccion encuentra un sello temporal mayor al propio que ya realizo commit debe ser abortada
  • b) los sellos temporales estan libres de deadlock
  • c) los sellos temporales aseguran un orden correcto de procesamiento de las transacciones.
  • a) Verdadero, ya que eso quiere decir que otra TR mas nueva modifo algo que la TR actual tiene que usar por lo que es invalido y se tiene que abortar.
  • b) Verdadero
  • c) Verdadero, las marcas permiten que se ejecuten en orden

Ejercicio 43:

Ejercicio 44:

Indicar si la siguiente frase es falsa o verdadera :

"Evitar los falsos abrazos mortales en un esquema de deteccion distribuida es posible mediante timing global y consultas realizadas por el coordinador ante la deteccion de un posible abrazo mortal."

Verdadero, cuando se detecta un posible abrazo y para comprobar si este es falso se le pregunta a todos los procesos para saber si falto que llegue algun mensaje anterior al tiempo donde se produce el falso bloqueo.

Ejercicio 45:

Ejercicio 46:

Ejercicio 47:

Enunciado exactamente igual al ej 28.

Rta:
Déjà vécu!
(ver ej 28)

Ejercicio 48:

Enunciado exactamente igual al ej 29.

Rta:
Déjà vécu!
(ver ej 29)

Ejercicio 49:

Ejercicio 50:

Qué sucede con dos eventos que ocurren simultáneamente (misma hora) según el algoritmo de Lamport en un sistema distribuido ?

Rta:
Si ambos eventos no tienen nada que ver, no pasa nada, se ejecutan concurrentemente, pero si por ejemplo requieren el mismo recurso, el algoritmo de Lamport arbitrariamete podría decidir que se le otorga al de menor número de nodo.

Yo no estoy seguro de que esa respuesta sea correcta. Lo que tiene que pasar con lamport es que todos los tiempos tienen que ser distintos, y si dos eventos ocurren simultaneamente lamport usa el punto decimal. Por ejemplo si los dos eventos A,B ocurren en T=20, entonces lamport los ve como 20.1 y 20.2.

Ejercicio 51:

Clasifique de menos a mayor los siguientes esquemas de manejo de la exclusion mutua respecto del trafico que circula en la red. La red posee p nodos, considere el pedido, uso y liberacion de la zona critica. Justifique su clasificacion

  • a centralizado
  • b distribuidos (Ricart y Agrawala)
  • c token ring

Rta

a<b<c

  • a) solo utiliza 3 mensajes. el pedido, el OK y la liberacion.
  • b) b utilizan 2(p-1) mensajes, ya que primero mando p-1 mensajes para ver si esta libre y p-1 respuestas
  • c) en token ring la cantidad de mensajes no esta acotada, ya que si nadie pide recursos la ficha podria rotar todo el tiempo.

Ejercicio 52:

Ejercicio 53:

Como se puede evitar el doble suicidio en el esquema de deteccion de abrazo mortal distribuido? (Chandy,Misra y Hass) ?


Rta : para evitar el doble suicidio el mensaje ademas debe llevar una lista de los procesos en el ring. Cuando dio toda la vuelta se tiene que elegir con alguna politica algun proceso, por ejemplo el de numero mas grande. De esta forma, varios procesos eligen la misma victima.

Ejercicio 54:

Ejercicio 55:

Ejercicio 56:

Ejercicio 57:

Elija un algoritmo de sincronización de relojes físicos que le parezca mejor y fundamente su elección.

Rta:
Un algoritmo de sincronización bueno podria ser el de promedios, por ser sencillo, descentralizado al contrario de Cristian y Berkeley y puede no utilizar máquina WWV al contrario de "multiples fuentes externas".

Ejercicio 58:

Ejercicio 59:

Que es el almacenamiento estable y para que se lo utiliza en el esquema de Transacciones?

Almacenamiento estable es un tipo de almacenamiento que esta dise;ado para sobrevivir a todo, salvo catastrofes naturales. Consiste en duplicar la informacion en discos, como con RAID1 por ejemplo.

el almacenamiento estable es adecuado para aplicaciones con transacciones porque proveen un alto grado de tolerancia a fallas.

Ejercicio 60: