# data[].attributes.body
¡Ninguno de los algoritmos para exclusión mutuadescritos toleraría perder mensajes, si los canales no fueran confiables!

# data[].attributes.headline
Algoritmo de Ricart y Agrawala (exclusión mutua)

# data[].attributes.subject
Algoritmo de Ricart y Agrawala (exclusión mutua)

# data[].attributes.body
Emplea multicast y relojes lógicos

# data[].attributes.headline
Algoritmo basado en anillo (exclusión mutua)

# data[].attributes.subject
Algoritmo basado en anillo (exclusión mutua)

# data[].attributes.headline
Algoritmo del servidor central (exclusión mutua)

# data[].attributes.subject
Algoritmo del servidor central (exclusión mutua)

# data[].attributes.body
Definiciones.- En un sistema distribuido con N procesos:

*No se comparten las variables entre procesos.
*El acceso a los recursos se realiza en la sección crítica.
*Suposiciones:
+Sólo una sección crítica a la vez.
+El sistema distribuido es asíncrono.
+Los procesos no fallan.
+La entrega de mensajes es confiable:
-Siempre se entregan.
-No existe entrega duplicada.
*Protocolo para ejecución de la sección crítica (SC), "pseudocódigo"
entrar() //Bloquear si es necesario
accesarRecursos()
salir() //Ahora pueden ingresar otros procesos
*Requerimientos para la exclusión mutua:
+Seguridad: Sólo un proceso puede entrar a la SC a la vez.
+Viveza: Las solicitudes para entrar y salir de la SC evitan el abrazo de la muerte (deadlocks; puntos muertos) e inanición.
+Orden: Las solicitudes de ingreso a la SC se forman en una cola

# data[].attributes.body
Se lleva a cabo en una colección de procesos que comparten recursos. Sus objetivos son:

En el acceso a los recursos:
*Prevenir interferencia
*Asegurar consistencia

En la sección crítica:
*Sistemas distribuidos ➔ Ningún servicio de un solo kernel
local (por ejemplo, semáforos o variables mutex) funciona.
*La solución debe estar basada solamente en mensajes.

En algunos casos ➔ Servidor ➔ Administración y mecanismos de exclusión mutua ➔ Recursos compartidos ➔ ¿Y si no hay servidor?

Para esos casos existen los algoritmos para exclusión mutua.

# data[].attributes.headline
Algoritmo de elección  del bravucón o "Bully"

# data[].attributes.subject
Algoritmo de elección  del bravucón o "Bully"

# data[].attributes.body
SOPORTA QUE FALLEN PROCESOS DURANTE LA ELECCIÓN
Es síncrono (emplea tiempos para determinar fallas)
La entrega de mensajes es confiable.
Cada proceso sabe cuales procesos tienen los ID's mas grandes.

Tipos de mensaje : Elección, Respuesta y Coordinador.

El empleo de tiempo para detectar fallas consiste en determinar tiempos maximos de espera de respuesta con base en la latencia que puede existir en procesamiento y envío. Si se excede dicho tiempo, hay algo mal con el proceso destino, se dice que tiene una falla temporal o permanente.

Como los procesos conocen los identificadores mas grandes, si no se ha determinado el coordinador (mensaje coordinador), se comienza a buscar enviando mensajes, si ninguno de los procesos con id's > al id del proceso actual, se nombra a si mismo coordinador y emite los mensajes necesarios.

En este algoritmo no se garantiza el requerimiento de SEGURIDAD, ya que se puede dar el caso en que dos procesos se autonombren coordinadores al mismo tiempo.

# data[].attributes.attachment_link.title
Screenshot-2018-5-31 Acerca de Cómputo distribuido (Cómputo en la nube) 2018-2 Semestre 4.png

# data[].attributes.body
En este algoritmo:
- los procesos se pueden "reacomodar" como un anillo lógico.
- Los mensajes son enviados en sentido de las manecillas del reloj.
- Se elige un coordinador (proceso con el id mas grande)
- Inicialmente cada proceso se marca como no participante.
- Procede a marcarse a si mismo como participante
- coloca su mensaje de elección y lo envía a su vecino más cercano, en sentido de las manecillas.
- en los siguientes pasos se reciben los mensajes y se determina el coordinador con el criterio del identificador mas grande.

Este algoritmo es el indicado para la comprensión de los algoritmos de elección, pero debido a que no tolera fallas, es poco usado en la practica.

# data[].attributes.attachment_link.title
Screenshot-2018-5-30 Acerca de Cómputo distribuido (Cómputo en la nube) 2018-2 Semestre 4.png

# data[].attributes.body
- Seguridad: DEBE OCURRIR LA ELECCION.
O aun no se realiza una elección o la elección ya ocurrio.

-Viveza: Todos los procesos participan en la elección o dejan de funcionar.

# data[].attributes.body
Un proceso puede INICIAR una elección (realiza acción que ejecuta algoritmo de elección).

Un proceso es PARTICIPANTE o NO-PARTICIPANTE, es decir, está involucrado o no en una elección.

Solo puede haber UN proceso elegido.

Cada proceso tiene un identificador.

# data[].attributes.body
El algoritmo de elección sirve para elegir un solo proceso que represente un rol particular.

En la exclusión mutua dijimos que teniamos un "pool" de procesos,

Un solo proceso de los N existentes se debe elegir como servidor central.

Si el proceso elegido se retira, se debe establecer uno nuevo con otra elección.

# data[].attributes.body
Conjunto de operaciones sobre un conjunto de objetos que se debe ejecutar como una unidad indivisible en el servidor que los administra.

El servidor debe garantizar que la transacción entera se lleva a cabo y que sus resultados se coloquen en almacenamiento permanente o, si una o más operaciones fallan, que sus efectos se eliminen por completo

# data[].attributes.body
Asegurar que todos los objetos administrados
por un servidor permanezcan en un estado
consistente cuando se accesan dentro de una o
más transacciones y en presencia de caídas del
propio servidor.

Objetos recuperables.- Objetos factibles de recuperar
después de una caída del servidor que los administra.

Objetos ⇨ Memoria volátil (RAM) o persistente (disco duro).

Servidor ➔ Objetos (suficiente información de su estado) ➔
Memoria persistente ➔ Recuperación de caídas del servidor.

# data[].attributes.headline
Propiedades ACID                     -Atomicidad Transacción ⇨ Todo o nada.                               -Consistencia Transacción ⇨ Lleva al sistema ⇨ Estado consistente⇨ Otro estado consistente                                 -Isolation (aislamiento)Transacción ⇨ No interfiere con otras transacciones                             -DurabilidadTransacción ⇨ Se completa ⇨ Efectos permanentes

# data[].attributes.subject
Propiedades ACID                     -Atomicidad Transacción ⇨ Todo o nada.                               -Consistencia Transacción ⇨ Lleva al sistema ⇨ Estado consistente⇨ Otro estado consistente                                 -Isolation (aislamiento)Transacción ⇨ No interfiere con otras transacciones                             -DurabilidadTransacción ⇨ Se completa ⇨ Efectos permanentes

# data[].attributes.body
Todo o nada
Transacción
Se completa ⇨ Efectos se reflejan ⇨ Objetos
Falla o se aborta ⇨ No tiene efecto alguno

Atomicidad de fallas
Efectos atómicos aunque falle el servidor

Durabilidad
Transacción satisfactoria ⇨ Efectos se reflejan en
almacenamiento permanente (archivos en disco o algún otro
medio permanente)

Aislamiento
Cada transacción no interfiere con otras transacciones
Efectos intermedios ⇨ No son visibles ⇨ Otras transacciones

# data[].attributes.body
Transacciones serializables
o equivalentes en serie

Requisito de aislamiento

Ejecutar las transacciones en serie ⇨ Una después de
otra, en un cierto orden

Servidores de transacciones ⇨ Maximizar concurrencia

Si las transacciones se ejecutan concurrentemente y tienen el
mismo efecto que su ejecución en serie, se les denomina
serializables o equivalentes en serie

# data[].attributes.headline
Transacciones serializables o equivalentes en serie

# data[].attributes.subject
Transacciones serializables o equivalentes en serie

# data[].attributes.body
Requisito de aislamiento

Ejecutar las transacciones en serie ⇨ Una después de
otra, en un cierto orden

Servidores de transacciones ⇨ Maximizar concurrencia

Si las transacciones se ejecutan concurrentemente y tienen el
mismo efecto que su ejecución en serie, se les denomina
serializables o equivalentes en serie

# data[].attributes.body
Intercalación de las operaciones de dos o más
transacciones en la cual el efecto combinado es el
mismo al resultante de ejecutar las transacciones
una después de otra, en un cierto orden.

Dos transacciones diferentes tienen el mismo efecto:
-Si las operaciones read devuelven los mismos valores y
-Si los atributos de los objetos terminan con los mismos valores

El empleo de la equivalencia en serie para control de la
concurrencia, evita la perdida de actualizaciones y las
lecturas inconsistentes

# data[].attributes.body
Dos operaciones están en conflicto cuando su
efecto combinado depende del orden de ejecución.
Operación read.- Acceso al valor de un objeto.
Operación write.- Cambiar el valor del objeto.

# data[].attributes.body
Los interbloqueos se pueden detectar buscando
ciclos en el grafo espera-por

Detectado un interbloqueo, se elige una transacción
para abortar con el fin de romper el interbloqueo

# data[].attributes.headline
RECUPERACIÓN Recuperación cuando se aborta

# data[].attributes.subject
RECUPERACIÓN Recuperación cuando se aborta

# data[].attributes.body
El servidor elimina todos los efectos  de las transacciones abortadas.

Operaciones
read -> a.getBalance()
balance = a.getBalance()  $100

write -> setBalance()
setBalance(balance +10)   $110

# data[].attributes.body
LECTURAS SUCIAS

Estrategia de recuperación

- Abortar en cascada
Posponer los commits de una transacción que ha visto el estado de otra, que aún no ha hecho commit.

ESCRITURAS PREMATURAS

Estrategia de recuperación

- Ejecución estricta de transacciones
Posponer las operaciones read y write sobre un objeto hasta que
todas las transacciones que previamente escribieron sobre dicho objeto, hayan abortado o hecho commit.

# data[].attributes.body
Transacciones compuestas por otras transacciones.

Ventajas

- Las del mismo nivel en la jerarquía se pueden
ejecutar de forma concurrente.
- Pueden abortar o hacer commit independientemente.
-La transacción padre puede decidir si aborta o no

Transacción plana (flat)

Todo su trabajo se realiza al mismo nivel entre openTransaction y un commit o un abort.

Reglas de las subtransacciones para el commit

1. Transacción - Commit/abortar - Después - Transacciones hijas - completas

2. Substracción completa - Commit provisional/
abortar - Por separado - Abortar es definitivo

3. Transacción padre aborta - Todas sus hijas abortan

4. Transacción hija aborta - Padre decide abortar o no

5. Transacción de nivel superior (top-level) commit - Todas las subtransacciones commit - Si ninguno de
sus ancestros ha abortado

# data[].attributes.body
Serialización empleando bloqueos.

En este esquema de serialización de
operaciones, un servidor intentará bloquear los objetos que cualquier operación de una transacción cliente intente emplear.

Si un cliente solicita acceso a un objeto que ya está bloqueado por una transacción de otro cliente, la petición se suspende y el cliente debe esperar hasta que el objeto sea desbloqueado

# data[].attributes.body
Solución simple: Bloquear todo lo necesario

Al inicio de la transacción y en forma atómica

No puede tener interbloqueos

Restringe innecesariamente el acceso a los recursos
compartidos

En ocasiones no es posible predecir al inicio de la
transacción todos los objetos que se van a utilizar

# data[].attributes.body
La equivalencia en serie requiere.

Accesos una transacción ⇨ Objeto ⇨ Serializar ⇨ Accesos de otras transacciones.

Pares de operaciones en conflicto ⇨ Ejecución ⇨ Mismo orden.

Para asegurar esto ⇨ Transacción con bloqueo en 2 fases ⇨ No nuevos bloqueos ⇨ Después ⇨ Liberar algún bloqueo.

# data[].attributes.body
Se puede utilizar un grafo espera-por para
representar las relaciones de espera entre las
transacciones en ejecución
En un grafo espera-por los nodos representan
transacciones y las aristas representan relaciones
espera-por entre ellas

Existe una arista del nodo T al U cuando la
transacción T espera que la transacción U libere un
bloqueo

# data[].attributes.body
1ª fase ⇨ Crecimiento ⇨ Adquisición de bloqueos

2ª fase ⇨ Contracción ⇨ Liberación de bloqueos

Mantener los bloqueos hasta que los efectos de la transacción sean escritos en almacenamiento permanente.

# data[].attributes.body
Bajo una ejecución estricta
A fin de evitar lecturas sucias y escrituras
prematuras, una transacción que requiere leer o escribir sobre un objeto se debe posponer hasta que cualquier otra transacción que haya escrito previamente sobre el mismo objeto haga commit o aborte.

Para asegurar lo anterior
Cualquier bloqueo aplicado durante el progreso de una transacción se debe mantener hasta que la transacción haga commit o aborte.

# data[].attributes.body
Que cada transacción, dentro de un conjunto de
transacciones anidadas, no observe los efectos
parciales de las otras transacciones en el conjunto

# data[].attributes.body
Un estado en el cual cada miembro de un grupo
de transacciones espera que otro miembro
libere un bloqueo

# data[].attributes.body
Objetivo: Serializar el acceso a los objetos para

Que cada conjunto de transacciones anidadas sea una
entidad única que no debe observar los efectos
parciales de otro conjunto de transacciones anidadas

Cada bloqueo adquirido por una subtransacción exitosa es
heredado por sus ancestros cuando aquélla se completa

# data[].attributes.body
Promoción de un bloqueo:

Convertir un bloqueo a uno más fuerte, es decir, más
exclusivo o más restrictivo

Un bloqueo de escritura es más exclusivo que uno de lectura

# data[].attributes.body
Problemas

Transacciones abortadas (por vulnerabilidad) aún sin
existir interbloqueos

Las transacciones que requieren mucho tiempo para
efectuarse son penalizadas

La elección del tiempo de espera es muy difícil

Si el interbloqueo se detecta, en lugar de usar los
tiempos de espera, la transacción a abortar se elige
con mejor fundamento

# data[].attributes.body
Tiempos de espera para bloqueos

Método de resolución de interbloqueos

Bloqueo ⇨ Periodo limitado de invulnerabilidad

Terminado el periodo ⇨ Bloqueo vulnerable

Bloqueo sigue ⇨ No transacción ⇨ En competencia

Bloqueo se rompe ⇨ Generalmente su transacción se
aborta ⇨ Alguna transacción ⇨ Requiere ⇨ Objeto del
bloqueo

# data[].attributes.body
La elección de la transacción a abortar no es simple

Algunos factores que se pueden considerar son:

Edad de la transacción (¿cuánto tiempo lleva en ejecución?)

Número de ciclos de interbloqueo en los que interviene

Número de recursos que tiene bloqueados

Etc.

# data[].attributes.body
Operación read ⇨ Bloqueo de lectura

Operación write ⇨ Bloqueo de escritura

Objeto bloqueado ⇨ Esperar ➔ Nunca se rechaza

Una o mas operaciones read ⇨ No están en conflicto
⇨ Las transacciones comparten el candado de lectura
⇨ Bloqueos compartidos

# data[].attributes.body
No es seguro degradar (hacer menos exclusivo) un
bloqueo aplicado por una transacción antes de que
ésta haga commit

El resultado es más permisivo y pondría en riesgo la
equivalencia en serie de las operaciones de las
transacciones involucradas

# data[].attributes.body
Adoptar esquema de bloqueos ⇨ Muchas
transacciones concurrentes ⇨ Leyendo un objeto ⇨ O
una sola transacción ⇨ Escribiéndolo ⇨ Ambos no