¿Cómo puede la marca de tiempo causar un "punto muerto global"?

Question

Estoy leyendo un poco sobre las ventajas/desventajas de usar marcas de tiempo para el control de concurrencia en una base de datos distribuida. El material que estoy leyendo menciona que aunque las marcas de tiempo superan los problemas tradicionales de interbloqueo que pueden afectar el bloqueo, todavía existe el problema del "punto muerto global", que es vulnerable.

El material describe el punto muerto global como una situación donde no existe ciclo en los gráficos de espera de los gráficos locales, pero que hay un ciclo en el gráfico global.

Me pregunto cómo podría pasar esto? ¿Podría alguien describir una situación en la que un sistema de marca de tiempo podría causar este problema?

Answer 1

Aquí hay un ejemplo, probablemente el más simple posible. Tenemos máquinas A y B. La máquina A tiene cerraduras T1 y T2 con la relación T1 < T2. La máquina B tiene T3 y T4 con T3 > T4.

Ahora, los gráficos locales son solo que T2 debe esperar a T1 y T3 debe esperar a T4. Entonces no hay ciclos locales. Pero ahora, supongamos que tenemos T4 < T1, por lo que T1 tiene que esperar T4. Y al mismo tiempo T2 < T3 por lo que T3 tiene que esperar para T2. En este caso, hay un ciclo global.

Entonces, ¿cómo ocurre ese ciclo? La clave aquí es que nunca tienes la información completa en un sistema distribuido. Entonces podemos aprender más tarde que las dependencias entre máquinas están ahí. Y luego tenemos un problema.

Answer 2

La marca de tiempo se utiliza para determinar la resolución de conflictos entre procesos locales en una máquina. Proporciona un medio para resolver interbloqueos en ese nivel. Para los procesos distribuidos, existe la posibilidad de que dos procesos en máquinas diferentes estén esperando el uno al otro. Que de hecho es un punto muerto regular, pero en todas las máquinas. Esto se conoce como un punto muerto 'global'. La marca de tiempo de Imho también puede usarse allí, pero aparentemente no es práctica.

Algo de información sobre esto se puede encontrar en http://www.cse.scu.edu/~jholliday/dd_9_16.htm