Programacion Distribuida

El concepto de programación distribuida es esencial para entender el vocabulario básico de SOA y se basa
en Remote Procedure Call.

Sumario

  1. Introducción
  2. Corrección en programación distribuida
  3. Exclusión mutua
  4. Semáforos
  5. Monitores
  6. Pasaje de mensajes
  7. Exclusión mutua distribuida
  8. Transacciones y control de concurrencia
  9. Bloqueos
  10. Control optimista de la concurrencia
  11. Ordenamiento por marca de tiempo
  12. Comparación de m&
    eacute;todos de control de concurrencia
  13. Referencias

Introducción

La palabra "distribuida" en términos como computación distribuida, sistema distribuido y algoritmo distribuido se refería originalmente a computadoras individuales que estaban físicamente distribuidas en un área geográfica. Estos términos se usan hoy en día en un contexto más amplio, aun a procesos autónomos que se ejecutan en una misma computadora física y que interactúan con pasaje de mensajes.[1]

Según Coulouris et al[5], un sistema distribuido es aquel cuyos componetes están localizados en una red de computadoras y se comunican y coordinan sus acciones mediante pasaje de mensajes.

Se identifican las siguientes propiedades:

n

  • Hay varias unidades computacionales autónomas, cada una con su propia memoria local.
  • Las unidades se comunican entre sí mediante pasaje de mensajes.[1]
  • Se deben compartir recursos entre las distintas unidades computacionales, sea para acceder a bases de datos, impresoras, dispositivos de video, etc.
  • La ejecución de procesos en las distintas unidades computacionales es concurrente, es decir, operan en forma simultánea y pueden requerir acceso también simultáneo a los recursos compartidos.

Estas entidades computacionales se conocen como Nodos.

El objetivo de los sistemas distribuidos es realizar una tarea cuyo procesamiento está distribuido en varios procesos. Puede requerirse acceder a una base de datos que está en una computadora, o un servicio web que está en otra. Así, los pasos necesarios para completar la tarea involucran utilizar
recursos de distintos sistemas, que pueden encontrarse en distintos lugares físicos.

Para comprender los problemas de la programación concurrente y distribuida, primero debemos comprender la programación concurrente y cómo se resuelven sus problemas antes de pasar a hablar de lo que ocurre cuando los procesos que se deben comunicar están aislados de otros.

Se comenzará por discutir cuándo un programa concurrente es correcto para de ahí derivar las principales características que tienen estos programas cuando su funcionamiento es apropiado.

A continuación se discutirán los distintos algoritmos y recursos computacionales que se utilizan para resolver los problemas planteados por la concurrencia.

Finalmente se discutirá cómo se resuelven los mismos problemas cuando los programas son no solamente concurrentes sino también distribuidos.

n

Corrección en programación concurrente

Para los programas secuenciales, el concepto de corrección es tan evidente que muchas veces no se define el concepto de corrección, pero para los programas concurrentes es imperativo formalizar este concepto ya que es muy diferente y no intuitivo, y porque a veces la verificación de corrección se vuelve crucial.[4]

Hay dos definiciones de corrección. Sea P(x) una propiedad de las variables de entrada x y Q(x,y) una propiedad de las variables de entrada x y variables de salida y. Entonces para valores a cualesquiera de las variables de entrada, se define corrección de la siguiente forma:

Corrección parcial: Si P(a) es verdadera y el programa termina cuando se inicia con los valores a para
las variables de entrada x, entonces Q(x,y) es verdadera donde b son los valores de las variables de salida al momento de la terminación. [4]

Corrección total: Si P(a) es verdadera, entonces el programa termina y la propiedad Q(x,y) es verdadera para los valores de entrada a para x y b para las variables de salida y.[4]

La corrección de programas se define en términos de las propiedades de las secuencias de ejecución [4]. En programación distribuida es imposible garantizar si una tarea se realizará antes de otra o no, ya que al ejecutarse las tareas en distintas computadoras, a menos que se comuniquen, no hay coordinación y el orden de realización de las tareas puede variar. Por lo tanto, una propiedad está impl&
iacute;citamente definida "para todas las secuencias de ejecución".

Propiedades de corrección

Hay dos clases de propiedades de corrección:[4]

Propiedades de seguridad: estas propiedades siempre deben ser ciertas.

Propiedades de vivacidad: estas propiedades deberán ser verdad ahora o en el futuro.

La propiedad de seguridad más común es la exclusión mutua: dos procesos no deberán realizar una cierta tarea a la vez, una de estas tareas deberá ser completada antes que la otra. El orden en el que se ejecutarán estas tareas no es importante. Pero siempre debe ser cierto que cuando un proceso requiere acceso a un recurso compartido, digamos una base de datos, para operaciones que puedan afectar al recurso, digamos una actualización, este acceso debe ser exclusivo.[4]

Otra
propiedad de seguridad muy importante es la ausencia de deadlock. Un proceso que no termine siempre deberá poder hacer trabajo útil. Un proceso que no responda a una señal o pedido está en "deadlock" y esto nunca deberá ocurrir. Un proceso en "deadlock" no responde, está "colgado".[4]

La corrección parcial puede ser satisfecha por cualquier proceso que no termine (no así la corrección total, que requiere que el proceso termine), y las propiedades de seguridad pueden ser satisfechas por un proceso que no haga nada. Si los procesos no acceden a un recurso compartido, no habrá problemas para compartirlo. Pero si realmente acceden a recursos compartidos, se deben cumplir propiedades de vivacidad. Si un proceso requiere usar la base de datos, el pedido deberá ser satisfecho. El término técnico es la ausencia de "inanición". Esta es una
especificación débil porque un programa que acceda a la base de datos después de mil años sería correcto, porque estas propiedades no tienen en cuenta el tiempo, pero si el sistema no es malicioso, "ahora o en el futuro" será relativamente pronto a menos que haya "contención" para acceder al recurso.[4]

Un tipo particular de propiedad de vivacidad es la propiedad de equidad. Si hay contención hay que especificar una forma de resolverla. Hay cuatro formas posibles de equidad:

  • Equidad débil: si un proceso hace un pedido contínuamente, finalmente se le otorgará.
  • Equidad fuerte: si un proceso hace un pedido infinitamente a menudo, finalmente se le otorgará.
  • Espera lineal: Si un proceso hace un pedido, se le otorgará antes que a otro se lo otorguen más de una vez.
  • FIFO (
    primero entrado, primero salido)
    : Si un proceso hace un pedido, se le otorgará antes que otro
    que hizo un pedido más tarde.

La diferencia entre equidad débil y equidad fuerte se muestra en la figura 1. Un proceso requiere un recurso cambiando el valor de una señal a 1. La línea superior muestra el proceso P1 que manda un pedido en forma periódica y luego cancelando el pedido mientras que P2, que se muestra en la línea inferior, manda un pedido y lo deja activo durante un período indefinido. El proceso que otorga los pedidos recibe las señales en los momentos t0, t1, t2, etc. Tal como se ve, este sistema es de equidad débil porque otorgará el pedido de P2 pero no equidad fuerte porque no otorgará el pedido de P1. Aun cuando P1 hace su pedido infinitamente a menudo, el servidor podrá recibir las señales justo cuando P1 no está pidiendo. Un sistema con equidad fuerte
otorgará el pedido de P1.[4]

Equidad fuerte y debil
Equidad fuerte y debil

Figura 1: Equidad débil y fuerte

Estos conceptos de equidad no son muy prácticos porque dependen de "ahora o en el futuro" e " inifinitamente a menudo". La espera lineal es un concepto práctico porque dice que una vez que un proceso hizo un pedido, podrá ser sobrepasado por otros pedidos, pero solamente una vez. FIFO es la especificación de equidad más fuerte. En un sistema centralizado es fácil de implementar. En un sistema
distribuido, no está claro qué significa "más tarde", así que se necesitan definiciones más débiles de equidad.[4]

Exclusión mutua

Como dijimos antes, la exclusión mutua es para una situación en donde dos o más procesos deben realizar una tarea en forma exclusiva, como ser, acceder a un recurso compartido.

Para realizar esto se emplean diversas técnicas de señalización, para indicar la necesidad de un proceso de realizar la tarea exclusiva, que denominaremos "sección crítica". Este tutorial no pretende ser una descripción detallada de los diversos métodos existentes; solamente se describirán y explicarán cómo se usan.

Algoritmo de la panadería

Este algoritmo se basa en compartir memoria entre procesos y
por lo tanto no es muy útil para la programación distribuida ya que procesos en distintas computadoras no pueden compartir memoria, pero es la idea básica en la que se basan todos los demás algoritmos.

En este algoritmo, un proceso que desea ejecutar su sección crítica debe tomar un número cuyo valor es más grande que el de todos los demás números emitidos. Luego, cada proceso pregunta el número de todos los demás procesos y cuando su número sea el más bajo de todos, entrará a la sección crítica.

El algoritmo de la panadería satisface las propiedades de exclusión mutua y ausencia de inanición, ya que finalmente todos los procesos entrarán a su sección crítica a medida que aquellos procesos con el número de ticket más bajo hayan entrado. Este algoritmo no se vuelve práctico para la ya
comentada situación de ausencia de memoria compartida y para cuando la cantidad de procesos que compiten por la sección crítica es muy grande.[4]

Semáforos

Un semáforo es un mecanismo de concurrencia implementado por el sistema operativo que utiliza memoria compartida. Se trata de una variable entera que toma solamente valores positivos. Se definen dos operaciones sobre un semáforo S:

  • Wait(S): Si S>1 entonces S:=S-1 o suspender la ejecución del proceso. Se dice que el proceso está detenido en el semáforo S.
  • Signal(S): Si hay procesos suspendidos en el semáforo, despertar a uno, de lo contrario S:=S+1.

Un semáforo que puede tomar cualquier valor positivo es un semáforo general. Un semáforo que solamente puede tener valores 0 o 1 es un semáforo binario.[
4]

Para entrar en la sección crítica, un programa es más simple que con el algoritmo del Panadero, teniendo solamente que ejecutar la sentencia Wait(S). Luego de la sección crítica, se requiere solamente ejecutar Signal(S).

Los programas que utilizan semáforos satisfacen todas las propiedades de seguridad y vivacidad [4]:

  • Exclusión mutua
  • Ausencia de Deadlock
  • No hay inanición.

Monitores

Los semáforos se introdujeron para tener una primitiva de sincronización que no requiriese "espera ocupada". Usando semáforos se pueden resolver los problemas básicos de programación concurrente. Sin embargo, el semáforo es una primitiva de bajo nivel, porque no es estructurada. Si se construyera un gran sistema solamente con
semáforos, la responsabilidad por el uso correcto de los semáforos se distribuye en todos los programadores, y si uno se olvida de llamar a Signal(S) al final de una sección crítica, puede ocurrir deadlock y la falla podría ser difícil de localizar.

El monitor es una primitiva estructurada que concentra la responsabilidad de la corrección en unos pocos módulos.[4]

El monitor controla el acceso a un recurso compartido, ofreciendo servicios a las aplicaciones que desean usar el recurso. Si dos procesos llaman al monitor, la implementación asegura que sus pedidos se procesen secuencialmente para preservar la exclusión mutua.

La sintaxis del monitor se basa en encapsular datos y los procedimientos que operan sobre ellos en un solo módulo. La interfaz del monitor consistirá de una serie de procedimientos, que operan con datos ocultos dentro del
módulo. La diferencia con cualquier otro módulo, es que un monitor no solamente protege a los datos de un acceso irrestricto, sino que también sincroniza las llamadas a los procedimientos de la interfaz. La implementación asegura que se ejecutan en exclusión mutua.[4]

Implementaciones en lenguajes de programación

El monitor puede implementarse usando semáforos. En el lenguaje Java, se utiliza la palabra registrada Synchronized para construir un monitor. Una clase con todos sus métodos declarados synchronized es un monitor. El lenguaje asegura que cada uno de los métodos así declarados sea invocado en exclusión mutua por los procesos invocantes.

Pasaje de mensajes

El pasaje de mensajes es un mecanismo de comunicación entre diferentes threads dentro de un proceso, diferentes procesos en el mismo nodo, y
diferentes procesos en distintos nodos. [3]

Las clasificaciones de mensajes son las siguientes, de acuerdo a la forma de funcionar:

  • Según su Sincronización: Mensajes asíncronos y síncronos
  • Comunicación directa simétrica y asimétrica
  • Comunicación indirecta

El mensaje es un dato que se transmite entre dos hilos o procesos, como se ha dicho anteriormente. El proceso que emite el mensaje se denomina emisor y el que lo recibe, Receptor.

Comunicación directa simétrica

El emisor identifica claramente al receptor y el receptor identifica al emisor.

Comunicación directa asimétrica

El emisor identifica al receptor pero el receptor no conoce al emisor, en este caso el receptor puede aceptar mensajes de cualquier emisor, mientras
que en el caso anterior, el receptor debe indicar de qué emisor espera un mensaje.

Comunicación indirecta

El emisor no conoce al receptor, y el receptor no conoce al emisor. Debe haber un intermediario como por ejemplo un buzón.

Sincronización

  • Mensajes Síncronos: coincide en el tiempo el momento de realizar el envío y recepción. Los procesos que se comunican se esperan al momento de comunicarse; si el emisor está por enviar el mensaje y el receptor no está listo para recibir, el emisor se bloquea, y viceversa, si el receptor al momento de recibir el mensaje determina que el emisor todavía no envió su mensaje, se bloquea. Un ejemplo de esto es la conversación telefónica.[3]
  • Mensajes Asíncronos: el emisor envía el mensaje sin esperar a que se reciba, y el receptor recibe el mensaje
    sin esperarlo. El mensaje se almacena temporalmente en un buffer mediando entre el envío y la recepción. Un ejemplo de esto es la comunicación por e-mail.[3]

Rendez-vous

Este es un esquema de comunicación síncrona asimétrica, en donde el emisor queda bloqueado hasta que el receptor responda, y cuando éste lo haga, el emisor continuará su proceso. El receptor declara puntos de entrada ("Entry"), que son invocados por el emisor. El proceso receptor se bloquea cuando llega al punto de entrada a la espera de que un emisor dispare un mensaje. El receptor puede también realizar otras acciones como por ejemplo esperar un cierto tiempo y continuar sus tareas, o aceptar un mensaje solamente al ocurrir determinadas circunstancias preestablecidas.

Canales

Propuestos por el científico inglés C.A.R. Hoare (también conocido por
inventar el algoritmo Quicksort), son entidades que sirven como vías de comunicación entre procesos. Estos canales tienen nombre y funcionan como si fuera comunicación simétrica, en donde el emisor y receptor conocen el nombre del canal por el que habrán de comunicarse, y estos pueden enviar o recibir datos del canal.

Esta funcionalidad deberá ser implementada por los sistemas operativos y lenguajes de programación, siendo las Unix Pipes un ejemplo de tal implementación en sistemas operativos y canales en el lenguaje Erlang.

Exclusión mutua distribuida

Los procesos distribuidos necesitan coordinar sus actividades. Si un conjunto de proesos comparte un recurso o conjunto de recursos, a menudo se requiere la exclusión mutua para impedir la interferencia y asegurar la consistencia cuando se accede a esos recursos. Este es el problema de la sección crítica
mencionado anteriormente. En un sistema distribuido no se pueden usar recursos como la memoria compartida, debiéndose confiar únicamente en pasaje de mensajes.[5]

Algoritmos para la exclusión mutua

Se considera un sistema de N procesos p1, p2…n, que no comparten variables. Los procesos acceden a recursos compartidos, pero lo hacen en una sección crítica. Por simplicidad se asumirá que hay solamente una pero se pueden extender a varias secciones críticas.

Se asumirá que el sistema es asíncrono, los procesos no fallan, y el envío de mensajes es confiable, de modo que todo mensaje enviado es finalmente recibido intacto exactamente una vez.

La aplicación deberá realizar la llamada enter() para acceder a la sección crítica, bloqueándose si es necesario; resourceAccess() para utilizar el recurso, y finalmente
exit() para permitir a otros procesos utilizar el ya liberado recurso.

Los requerimientos de exclusión mutua serán los siguientes:

  • ME1 (seguridad): A lo sumo un proceso ejecutará su sección crítica por vez.
  • ME2 (vivacidad): Las solicitudes para entrar a la sección crítica finalmente tendrán éxito.
  • ME3 (orden de solicitud): si un proceso A requiere acceder a su sección crítica y un proceso B hace
    su requerimiento después, la solicitud se otorgará en ese orden.

Se evaluará la eficiencia de los algoritmos de exclusión mutua en base a los siguientes criterios:

  • Ancho de banda consumido, proporcional a la cantidad de mensajes que se envían en cada operación
    enter() y exit().
  • Demora del cliente que cada proceso tiene en cada operación enter() y
    exit()
  • El efecto del algoritmo en el desempeño del sistema. Este se medirá como el ritmo al que los procesos en conjunto acceden a la sección crítica, dada que alguna comunicación es necesaria entre los procesos. Se mide este efecto usando la demora de sincronización entre la salida de un proceso de su sección crítica y la entrada del siguiente; el ritmo será mayor cuando este tiempo de sincronización sea más breve.[5]

Algoritmo del servidor central

La foma más simple de lograr la exclusión mutua es usar un server que otorgue permisos para entrar a la sección crítica. Para entrar a una sección crítica, un proceso envía un mensaje al servidor y espera de él una respuesta. Conceptualmente, la respuesta constituye un Token que significa el permiso para entrar a la sección crítica. Si ning&
uacute;n otro proceso tiene la token al momento de la solicitud, el servidor responde inmediatamente, otorgando la token. Si la token es retenida por algún otro proceso, el servidor no responde pero manda la solicitud a una coa. Al salir de la sección crítica se envía un mensaje al servidor, devolviendo la token.

Si la cola de procesos en espera no está vacía, entonces el server escoge la entrada más antigua, la remueve y responde al proceso correspondiente. El proceso elegido retiene la token.

Dadas las suposiciones de que no ocurren fallas, es fácil ver que se cumplen las condiciones de seguridad y vivacidad.

Ahora se evaluará el desempeño del algoritmo. Entrar en la sección crítica toma dos mensajes, uno de solicitud y otro de otorgamiento, y retrasa al proceso que requiere durante el tiempo que toma el viaje del mensaje. Salir de la sección cr&
iacute;tica solamente requiere un mensaje para liberarla. Asumiendo que se utiliza pasaje de mensajes asíncrono, esto no demora al proceso saliente.

El servidor podría convertirse en un cuello de botella para todo el sistema. La demora de sincronización es el tiempo que toma un viaje de ida y vuelta al servidor: un mensaje de liberación que llega al servidor, seguido de un mensaje de otorgamiento al siguiente proceso que entra en la sección crítica.[5]

Algoritmo de anillo

Una de las formas más fáciles de lograr la exclusión mutua de N procesos sin requerir un proceso adicional (como el servidor central) es ordenarlos en un anillo lógico. Esto requiere que cada proceso tenga un canal de comunicación con el siguiente proceso del anillo. La idea es que la exclusión se otorga obteniendo un token en la forma de un mensaje transmitido de proceso en
proceso en una dirección única, digamos en sentido de las agujas del reloj, alrededor del anillo. La topología en anillo podría no estar relacionada con las conexiones físicas de las computadoras subyacentes.

Si un proceso no requiere entrar a la sección crítica cuando recibe el token, entonces lo reenvía a su vecino. El proceso que requiera el token, deberá esperar hasta que lo obtenga, pero lo retiene. Para salir de la sección crítica, el proceso manda el token a su vecino.

Es inmediato verificar que se cumplen las condiciones ME1 y ME2, pero el token no se obtiene por orden de solicitud. Este algoritmo consume ancho de banda de red en forma contínua salvo cuando un proceso está en la sección crítica: los procesos envían mensajes a lo largo del anio aun cuando no hay procesos que requieran entrar en la sección crítica. La demora que tiene cada
proceso que requiere la entrada es entre 0 mensajes (cuando acaba de recibir la token) y N mensajes (cuando acaba de transmitir la token al siguiente). Para salir de la sección crítica se requiere solamente un mensaje. La demora de sincronización entre la salida de un proceso y la entrada del otro varía entre 1 y N mensajes.[5]

Algoritmo de Agrawala y Ricart

Ricart y Agrawala desarrollaron un algoritmo que implementa exclusión mutua entre N procesos pares que se basa en multicast (envío de mensajes de un emisor a varios receptores). La idea básica es que los procesos que requieren entrar a la sección crítica mandan un mensaje a todos los otros, y puede entrar solamente cuando todos los otros procesos han contestado ese mensaje. Las condiciones bajo las cuales un proceso responde a una solicitud se diseñan para asegurar que se cumplan las condiciones ME1, ME2 y ME3.

Cada
proceso guarda su estado, que puede ser fuera de la sección crítica (Released), esperando entrar (Wanted) o ejecutando la sección crítica (Held), en una variable estado.

Si un proceso requiere entrada y el estado de todos los otros procesos es Released, entonces todos los procesos responderán inmediatamente a la solicitud y el proceso que la solicita obtendrá el acceso. Si algún proceso está en el estado Held, entonces ese proceso no responderá a solicitudes hasta que haya terminado con la sección crítica y por lo tanto el solicitante no obtendrá el acceso. Si dos o más procesos requieren entrar al mismo tiempo, entonces la solicitud de aquel proceso con la marca de tiempo menor será el primero en recoger las N-1 respuestas, otorgándosele acceso. Si los procesos tienen una marca de tiempo igual, las solicitudes se ordenan de acuerdo al identificador del proceso. Nótese que
cuando un proceso requiere entrada, demora el procesar solicitudes de otros procesos hasta que su propia solicitud haya sido enviada y se haya grabado la marca de tiempo T de su solicitud. Esto se hace así para que los procesos tomen decisiones consistentes cuando procesan solicitudes.

Este algoritmo satisface la propiedad de seguridad ME1. Si fuera posible que dos procesos pi y pj entren a la sección crítica a la vez, entonces los dos procesos tendrían que haber respondido al otro. Pero como los pares <T,p> son totalmente ordenados, esto es imposible. Del mismo modo, este algoritmo satisface ME2 y ME3.[5]

Obtener acceso a la sección crítica toma 2(N-1) mensajes en el algoritmo: N-1 para transmitir la solicitud, seguido de N-1 respuestas. O, si hay soporte de hardware para multicast, se requiere un solo mensaje para la solicitud, el total es entonces N mensajes. Es por lo tanto un algoritmo caro,
en términos de consumo de ancho de banda, que otros algoritmos descriptos. Sin embargo, la demora en solicitar entrada es el tiempo que tardan los mensajes en ir y volver.[5]

Algoritmo de votación de Maekawa

Maekawa observó que para que un proceso entre en la sección crítica no es necesario que todos sus pares le otorguen acceso. El proceso solamente necesita obtener el permiso para entrar de un subconjunto de sus pares, siempre y cuando los subconjuntos usados por dos procesos cualesquiera se superpongan. Podemos pensar que los procesos votan unos por otros para entrar a la sección crítica. Un proceso "candidato" debe obtener suficientes votos para entrar. Los procesos en la intersección de dos conjuntos de votantes aseguran la propiedad de seguridad ME1, que a lo sumo un proceso puede entrar a la sección crítica, emitiendo su voto por solamente un candidato.

r

Para obtener acceso a la sección crítica, un proceso pi manda mensajes de solicitud a todos los K-1 miembros de su subconjunto de votantes, y pi no puede entrar a la sección crítica hasta que reciba K-1 mensajes de respuesta. Cuand un proceso pj en ese conjunto recibe el mensaje de pi, envía una respuesta de inmediato, a menos que su estado sea Held o que ya haya respondido ("votado") desde que recibió un mensaje Release por última vez. Si no, pone el mensaje de solicitud en una cola (por orden de llegada) y envía un mensaje de respuesta ("voto"). Para salir de la sección crítica, pi envía mensajes Release a todos los K-1 miembros.

Este algoritmo satisface la propiedad ME1. Si fuera posible que dos procesos pi y pj entren a la sección crítica a la vez, entonces los procesos en la intersección de sus conjuntos de votantes tendrían que haber votado por los
dos. Pero el algoritmo impone que un proceso vote a lo sumo una vez entre sucesivas recepciones de un mensaje Release, así que esta situación es imposible.

Desafortunadamente, este algoritmo puede sufrir deadlock. Se consideran 3 procesos, p1, p2 y p3 con V1={p1,p2},
V2={p2,p3} y V3={p3,p1}. Si los tres procesos requieren acceso a la sección criítica a la vez, es posible que p1 responda a p2 y retener a p3, que p2 responda a p3 y retenga a p1, y que p3 responda a p1 y retenga a p2. Cada uno de los procesos recibio una de dos respuestas y ninguno puede proseguir.

Este algoritmo se puede adaptar para liberarlo del deadlock. En el protocolo adaptado, los procesos mandan a una cola las solicitudes en un orden de solicitud (usando marcas de tiempo), para que también se satisfaga ME3. El consumo de ancho de banda de este algoritmo es 2*sqrt(N) por cada entrada a la sección crítica y sqrt(N) por salida (asumiendo que no
existe soporte de hardware para multicast). El total 3*sqrt(N) es superior a 2(N-1) requerido por el algoritmo de Agrawala y Ricart, si N>4. La demora del cliente es la misma que la de Agrawala y Ricart, pero la demora de sincronización es peor: es el tiempo de ir y volver del mensaje en vez de solamente la transmisión de este.[5]

Transacciones y control de concurrencia

Aquí se discutirá la aplicación de transacciones y control de concurrencia a objetos compartidos
administrados por los servidores.

Una transacción define una secuencia de operaciones del servidor que el servidor garantiza que son atómicas en la presencia de múltiples clientes y caídas del servidor. Las transacciones anidadas se estructuran de conjuntos de otras transacciones. Son útiles en sistemas distribuidos porque permiten concurrencia adicional.

n

Todos los protocolos de control de concurrencia se basan en el criterio de equivalencia serial y se derivan de reglas para conflictos entre operaciones. Se describen tres métodos:

  • Se usan locks para ordenar las transacciones que usan los mismos objetos de acuerdo al orden de llegada de las operaciones a los objetos.
  • El control optimista de concurrencia permite que las transacciones procedan hasta que estén listas para confirmarse, donde se hace un control para ver si han realizado operaciones conflictivas en los objetos.
  • El orden por marca de tiempo usa estas marcas para ordenar las transacciones que acceden a los mismos objetos de acuerdo a sus momentos de comienzo.

Introducción a transacciones

El objetivo de las transacciones es asegurar que todos los objetos administrados por un servidor queden en un estado consistente cuando son utilizados por múltiples transacciones y en
presencia de caídas del servidor. La transacción es un conjunto de operaciones que deben realizarse como una unidad indivisible por los servidores que administran esos objetos. Los servidores deben garantizar que o la transacción entera se completa y sus cambios quedan grabados en el almacenamiento permanente, o en el caso de que uno de ellos caiga, sus efectos son eliminados. La transacción también es considerada indivisible desde el punto de vista del cliente en el sentido que las operaciones de una transacción no pueden observar los efectos parciales de las operaciones de otras.[5]

Para ilustrar algunos ejemplos se usará un ejemplo bancario. Cada cuenta está representada por un objeto remoto cuya interfaz cuenta provee operaciones para hacer depósitos y extracciones y para solicitar y cambiar el saldo. Cada sucursal del banco está representado por un objeto remoto cuya interfaz sucursal da
operaciones para crear nuevas cuentas, buscar una cuenta por su nombre y solicitar el total de fondos de la sucursal.

Operaciones de la interfaz Cuenta
depositar(monto) Deposita la cantidad monto en la cuenta
extraer(monto) Extrae la cantidad monto de la cuenta
darSaldo()->monto Devuelve el saldo de la cuenta
cambiarSaldo(monto) Cambia el saldo de la cuenta a la cantidad monto

Figura 3: operaciones de las interfases Cuenta y Sucursal

Para implementar la cuenta y la sucursal, se puede emplear el concepto de monitor, como en Java, declarando todos estos métodos como synchronized. Para implementación en otros lenguajes de programación, se deben utilizar otro tipo de herramientas de sincronización como los semá
foros.

A continuación se presenta como ejemplo una transacción: una serie de operaciones que involucran las cuentas A, B y C. Las primeras dos acciones transfieren $100 de A a B y las segundas dos transfieren $200 de C a B. Un cliente realiza una transferencia con una extracción seguida de un depósito.

Transaction T:
A.extraer(100);
B.depositar(100);
C.extraer(200);
B.depositar(200);

Las transacciones se originaron en los sistemas de base de datos. En ese contexto, una transacción es una ejecución de un programa que accede a una base de datos. Las transacciones se introdujeron en los sistemas distribuidos en la forma de sistemas de archivos transaccionales. En el contexto de un servidor de archivos transaccional, una transacción es una ejecución de una secuencia de requerimientos para operaciones de archivos. En ambos modelos, el cliente observará que
los datos se transforman de un estado consistente a otro.

Las transacciones pueden ser provistas por Middleware como CORBA. En el IDL se puede especificar que un objeto o serie de objetos mediante la interfaz TransactionalObject. El cliente dispone además operaciones para indicar el comienzo y fin de una transacción. [5]

Un servidor que soporte transacciones debe sincronizar sus operaciones suficientemente como para asegurar que se cumpla el requisito de aislamiento. Una forma de hacer esto es realizar las transacciones en serie, de a una en algún orden arbitrario. Desafortunadamente, esta solución es inaceptable para los servidores cuyos recursos se comparten entre múltiples usuarios interactivos. En el ejemplo bancario, es deseable permitir que varios cajeros realicen transacciones on-line al mismo tiempo. El objetivo de cualquier servidor que soporte transacciones es de maximizar la concurrencia. Por lo
tanto, se permitirá ejecutar las transacciones en forma concurrente si tienen el mismo efecto que una ejecución en serie, o sea, si son serializables.

Propiedades ACID

Las propiedades de una transacción pueden recordarse fácilmente utilizando la sigla ACID:

  • Atomicidad: la transacción debe completarse totalmente, o no completarse.
  • Consistencia: una transacción lleva al sistema de un estado consistente a otro.
  • aIslamiento: los efectos de una transacción no son visibles por otras hasta que la operación se termina.
  • Durabilidad: una vez que una transacción finaliza, los cambios deben estar guardados en el almacenamiento permanente.

Control de Concurrencia

Existen dos problemas muy conocidos de transacciones concurrentes en el contexto del ejemplo bancario, el problema de la "
actualización perdida" y el de las "recuperaciones inconsistentes". Ambos problemas pueden evitarse usando ejecuciones de transacciones serialmente equivalentes. A lo largo de los ejemplos, las operaciones extraer, depositar, cambiarSaldo y darSaldo son operaciones sincronizadas, esto es, cada una de esas operaciones es atómica.

La actualización perdida. Este problema se ilustra con el siguiente par de transacciones en las cuentas A,B y C, cuyos saldos iniciales son $100, $200 y $300 respectivamente. La transacción T transfiere un monto de la cuenta A a la cuenta B. La transacción U transfiere un monto de la cuenta C a la cuenta B. En ambos casos, el monto transferido se calcula para incrementar el saldo de B en 10%. El efecto neto en la cuenta B de ejecutar las transacciones T y U debería ser el incrementar el saldo de la cuenta B en 10% dos veces, así su valor final será $242.

Transacción T: Transacción U
saldo=B.darSaldo(); saldo=B.darSaldo();
B.cambiarSaldo(saldo*1.1); B.cambiarSaldo(saldo*1.1);
A.extraer(saldo/10); C.extraer(saldo/10);
saldo=B.darSaldo(); $200
saldo=B.darSaldo(); $200
B.cambiarSaldo(saldo*1.1); $220
B.cambiarSaldo(saldo*1.1); $220
A.extraer(saldo/10) $80
C.extraer(saldo/10) $280

Figura 3: problema de la actualización perdida

Ahora, se considera el efecto de permitir que las transacciones T y U se ejecuten en forma concurrente como en la figura 3. Las dos transacciones leen el saldo de B como $200 y depositan $20. Este resultado es incorrecto, aumentando el saldo de B en $20 en vez de $42. Esto es una ilustración del problema de la actualización perdida. La actualización de U se pierde porque T la sobreescribe sin verla. Las dos transacciones leyeron el valor viejo antes que la otra haya escrito el nuevo.

Transacción V: Transacción W:
A.extraer(100); unaSucursal.darTotalSucursal();
B.depositar(100);
A.extraer(100); $100
total=A.darSaldo(); $100
total=total+B.darSaldo(); $300
total=total+C.darSaldo();
B.depositar(
100); $300

Figura 4: problema de la recuperación inconsistente

Recuperación inconsistente: La figura 4 muestra otro ejemplo relacionado con una cuenta bancaria donde la transacción V transfiere una suma de la cuenta A a la B y la transacción W llama al método darTotalSucursal para obtener la suma de todos los saldos de las cuentas del banco. Los saldos de las dos cuentas, A y B, son inicialmente $200. El resultado de darTotalSucursal incluye la suma de A y B como $300, lo cual está mal. Esta es una ilustración del problema de recuperación inconsistente. Las extracciones de W son inconsistentes porque V realizó solamente la parte de extracción de la transferencia al momento en que se calculó la suma.

Equivalencia serial: si se sabe que cada una de varias transacciones tiene el efecto correcto cuando se la hace sola, podemos deducir que si
estas transacciones se hacen de a una por vez en algún orden, el efecto combinado también será correcto. Una intercalación de las operaciones de las transacciones en la cual el efecto combinado es igual al que hubiera tenido si las transacciones se hubieran realizado de a una por vez en algún orden es una intercalación serialmente equivalente.

El uso de la equivalencia serial como criterio para una ejecución concurrente correcta impide la aparición de actualizaciones perdidas y recuperaciones inconsistentes.

La actualización perdida ocurre cuando dos transacciones leen el valor viejo de una variable y lo usan para calcular el valor nuevo. Esto no puede ocurrir si una transacción se hace antes de la otra, porque la transacción posterior leerá el valor escrito por la anterior. Como una intercalación serialmente equivalente de dos transacciones produce el mismo efecto que una
ejecución en serie, podemos resolver el problema de la actualización perdida por medio de la equivalencia serial.

La recuperación inconsistente puede ocurrir cuando una transacción de recuperación se ejecuta en forma concurrente con una transacción de actualización. No puede ocurrir si la transacción de recuperación se realiza antes o después de la actualización.[5]

Operaciones en conflicto: cuando decimos que un par de operaciones están en conflicto, significa que su efecto combinado depende del orden en el que se ejecutan. Para simplificar, consideramos una operación de escribir y una de leer. La operación leer accede al valor de un objeto y la de escribir cambia su valor. Las reglas de conflicto se muestran en la tabla a continuación.

Operaciones de
diferentes transacciones

Conflicto Motivo
Leer Leer No El efecto de las operaciones de leer no depende del orden de ejecución
Leer Escribir El efecto de una operación de leer y una de escribir depende del orden de ejecución
Escribir Escribir El efecto de dos operaciones de escribir depende del orden de ejecución

La equivalencia serial puede definirse en términos de conflictos de operaciones de la siguiente manera: [5]

Para que dos transacciones sean serialmente equivalentes, es necesario y suficiente que todos los pares de operaciones en conflicto de las dos transacciones se ejecuten en el mismo orden en todos los objetos que ambas utilizan.

Bloqueos

Un mecanismo simple de serialización es el uso de bloqueos exclusivos. El
servidor intenta bloquear cualquier objeto que esté por ser usado por una transacción cliente. Si un cliente intenta acceder a un objeto que ya está bloquedo por la transacción de otro cliente, esa solicitud es suspendida y el cliente tiene que esperar hasta que el objeto esté desbloqueado.

En la figura 5 se muestra el uso de bloqueos exclusivos. Muestra las mismas transacciones que la figura 3 pero con una columna extra para cada transacción que muestra el bloqueo, espera y desbloqueo. En este ejemplo, se asume que cuando las transacciones T y U comienzan, los saldos de A, B y C todavía no están bloqueados. Cuando la transacción T está por usar la cuenta B, se bloquea para T. Luego, cuando la transacción U está por usar B, y B está bloqueada por T, la transacción U espera. Cuando la transacción T se confirma, B se desbloquea, con lo cual la transacción U retoma. El uso del
bloqueo sobre B serializa el acceso a B.

Transacción T: Transacción U:
saldo=B.darSaldo(); saldo=B.darSaldo();
B.cambiarSaldo(saldo*1.1); B.cambiarSaldo(saldo*1.1);
A.extraer(saldo/10); C.extraer(saldo/10);
Operaciones Bloqueos Operaciones Bloqueos
openTransaction
saldo=B.darSaldo() Bloqueo de B
B.cambiarSaldo(saldo*1.1); openTransaction
A.extraer(saldo/10) Bloqueo de A B.darSaldo() Espera por bloqueo de T sobre B
closeTransaction Desbloquea A,B
B.cambiarSaldo(saldo*1.
1);
Bloqueo de B
C.extraer(saldo/10); Bloqueo de C
closeTransaction Desbloquea B,C

Bloqueo en dos fases

Para asegurar que todos los pares de operaciones en conflicto se ejecuten en el mismo orden, a una transacción no se le permiten nuevos bloqueos después de liberar un bloqueo. La primera fase de la transacción es una "fase de crecimiento", durante la cual se adquieren nuevos bloqueos. En la segunda fase, se liberan los bloqueos ("fase de achicamiento"). Esto se llama Bloqueo en dos fases.

A causa de que las transacciones pueden abortar, se necesitan ejecuciones estrictas para impedir "lecturas sucias" (lecturas de datos modificados por transacciones no confirmadas) y "escrituras prematuras" (cuando dos transacciones actualizan el mismo objeto y la primera aborta y la
segunda no, el valor actualizado del objeto podría restaurarse erroneamente al valor anterior antes de la primera actualización descartando nuevo valor de la segunda transacción). En un régimen estricto, una transacción que necesita leer o escribir un objeto debe ser retrasada hasta que otras transacciones que escribieron el mismo objeto hayan confirmado o abortado. Para obligar el cumplimiento de esta regla, los bloqueos aplicados durante el proceso de una transacción son retenidos hasta que la transacción se confirma o aborta. Esto se llama bloqueo en dos fases estricto. La presencia de los bloqueos impide que otras transacciones lean o escriban los objetos. Cuando se confirma una transacción, para asegurar la recuperabilidad, se deben retener los bloqueos sobre todos los objetos actualizados hasta que hayan sido grabados en el almacenamiento permanente. [5]

Para aumentar la velocidad de los procesos, quiz&
aacute; un bloqueo exclusivo para una operación de lectura sea demasiado. Es preferible tener un esquema de bloqueos en donde se permitan a varias transacciones leer un objeto, o a una sola transacción escribiéndolo, pero no los dos. Se usan dos clases de bloqueos: bloqueo de lectura y bloqueo de escritura. Antes de una operación de lectura de una transacción, se debe colocar un bloqueo de lectura sobre el objeto. Antes de una operación de escritura de una transacción, se debe colocar un bloqueo de escritura sobre el objeto. Cuando no sea posible colocar el bloqueo de forma inmediata, la transacción (y el cliente) tiene que esperar hasta que sea posible – una solicitud de un cliente nunca se rechaza.

Como los pares de operaciones de lectura de diferentes transacciones no entran en conflicto, un intento de colocar un bloqueo de lectura sobre un objeto con un bloqueo de lectura siempre es exitoso. Todas las transacciones que lean el
mismo objeto comparten ese bloqueo de lectura. Por esta razón, los bloqueos de lectura son llamados bloqueos compartidos.

Las reglas de operación en caso de conflicto son las siguientes:

  1. Si una transacción T ya realizó una operación de lectura sobre un objeto en particular, entonces una transacción concurrente U no debe escribir ese objeto hasta que T se haya confirmado o abortado.
  2. Si una transacción T ya realizó una operación de escritura sobre un objeto en particular, entonces una transacción concurrente U no debe leer ni escribir ese objeto hasta que T se confirme o aborte.

En la tabla a continuación se muestra la compatibilidad de bloqueos. En la primera columna de la tabla se muestra el bloqueo existente, si hay. Las casillas de la primera fila muestran el tipo de bloqueo requerido. Cada casilla muestra el efecto sobre una transacción
que requiere el tipo de bloqueo dado cuando ya existe el tipo de bloqueo dado a la izquierda.

Para un objeto Bloqueo requerido
Lectura Escritura
Bloqueo existente Ninguno Ok Ok
lectura Ok Esperar
escritura Esperar Esperar

A continuación se muestran las reglas utilizadas en bloqueo estricto de dos fases:

  1. Cuando una operación accede a un objeto dentro de una transacción:
    1. Si el objeto no está bloqueado, se bloquea y la operación continúa.
    2. Si el objeto tiene un bloqueo que conflictúa con el colocado por otra transacción, la transacción debe esperar hasta que se desbloquee.
    3. n

    4. Si el objeto tiene un bloqueo que no conflictúa, el bloqueo se comparte y la operación continúa.
    5. Si el objeto ya fue bloqueado en la misma transacción, se elevará la exclusividad del bloqueo si es necesario y la operación continúa (cuando la elevación es impedida por un bloqueo en conflicto,
      se usa la regla b).
  2. Cuando se confirma una transacción o se aborta, el servidor desbloquea todos los objetos que bloqueó para la transacción.

Deadlocks

El uso de bloqueos puede llevar al Deadlock. Esto viene cuando una transacción espera a otra para que desbloquee un objeto, y esta a su vez espera a la primera a que desbloquee. De esta manera ninguna de las dos transacciones progresa.

Una solución para prevenir los Deadlocks, que sería simple pero no demasiado buena, sería bloquear todos los objetos que
use la transacción cuando esta comienza. Esto tendría que ser ejecutado como una operación atómica para evitar deadlocks en esta etapa. Tal transacción no podría entrar en deadlock con otra transacción, pero restringe el acceso a recursos compartidos de manera innecesaria. Además, a veces es imposible predecir al inicio de una transacción cuáles objetos se van a usar. Este es el caso generalmente en aplicaciones interactivas, porque el usuario tendría que decir de antemano exactamente qué objetos piensa usar, lo cual es inconcebible en aplicaciones web, porque permite a los usuarios encontrar objetos que antes no conocían. También se puede prevenir el deadlock pidiendo bloqueos sobre objetos en un orden predefinido, pero esto podría resultar en bloqueo prematuro y reducción de la concurrencia.

Detección de Deadlocks

Se podrían detectar deadlocks
encontrando ciclos en los grafos de espera de bloqueos. Habiendo detectado el deadlock, hay que elegir una transacción para abortar y romper el ciclo.

Agotamiento del tiempo de espera de liberación de un bloqueo

Poner tiempos de espera para los bloqueos es un método muy común para resolver deadlocks. Cada bloqueo tiene un tiempo limitado durante el cual es invulnerable. Después de ese tiempo, se vuelve vulnerable. Si ninguna otra transacción compite por el objeto bloqueado, un objeto con un bloqueo vulnerable permanece bloqueado. Sin embargo, si hay alguna transacción está esperando acceder al objeto protegido por un bloqueo vulnerable, el bloqueo se rompe (o sea, el objeto se desbloquea) y la transacción que espera retoma. La transacción cuyo bloqueo se rompe generalmente es abortada.

Hay muchos problemas en el uso de bloqueos como remedio para los deadlocks: el peor problema
es que a veces las transacciones se abortan porque rompen sus bloqueos, pero no hay deadlock. En un sistema sobrecargado, la cantidad de transacciones cuyo tiempo de espera se agota aumentará y las transacciones largas serán penalizadas. Además, es difícil decidir en una duración para el tiempo de espera. Por el contrario, si se usa detección de deadlocks, las transacciones se abortan porque ocurren deadlocks y hay que elegir qué transacción abortar.

Control optimista de la concurrencia

Existen desventajas de los bloqueos, y se ha propuesto una alternativa para la serialización de las transacciones que evita estas desventajas. Estas son las desventajas de los bloqueos:

  • El mantenimiento de bloqueos es una sobrecarga que no existe en sistemas que no soportan el uso compartido de recursos. Aun las transacciones de solo lectura, que no afectan la integridad de los
    datos, deben en general usar bloqueos para garantizar que los datos leídos no sean modificados por otras transacciones al mismo tiempo. El bloqueo podría ser necesario solamente en el peor caso.
  • El uso de bloqueos puede resultar en un Deadlock. La prevención de Deadlocks reduce la concurrencia severamente, y por lo tanto las situaciones de deadlock deben resolverse por el uso de tiempos de espera o detección de deadlock. Ninguna de estas dos soluciones es satisfactoria para programas interactivos.
  • Para evitar transacciones abortadas en cascada, no se pueden liberar los bloqueos hasta el final de la transacción. Esto puede reducir significativamente el potencial de concurrencia.

Esta alternativa es "optimista" porque se basa en la observación de que, en la mayoría de las
aplicaciones, la probabilidad de que las transacciones de dos clientes accedan al mismo objeto es baja. Se permite
proseguir a las transacciones como si no hubiera posibilidad de conflicto con otras transacciones hasta que el cliente complete su tarea y emita una llamada closeTransaction. Cuando surge el conflicto, alguna transacción generalmente es abortada y deberá ser reiniciada por el cliente. Cada transacción tiene las siguientes fases:[5]

  • Fase de trabajo: Durante la fase de trabajo cada transacción tiene una versión tentativa de cada uno de los objetos que actualiza. Esta es una copia de la versión confirmada más recientemente del objeto. El uso de versiones tentativas le permiten a la transacción abortar (sin efecto sobre los objetos), durante la fase de trabajo o si falla la validación debido a otras transacciones en conflicto. Las operaciones de lectura se hacen inmediatamente, si una versión tentativa para la transacción ya existe, una operación de lectura lo accede; si no,
    accede el valor más recientemente confirmado del objeto. Las operaciones de escritura graban los nuevos valores (que son invisibles a otras transacciones) como valores tentativos. Cuando hay varias transacciones concurrentes, pueden coexistir varios valores tentativos del mismo objeto. Además se mantienen dos registros de los objetos accedidos durante una transacción: un conjunto de lectura que tiene los objetos leídos por la transacción, y un conjunto de escritura que contiene los objetos escritos por la transacción. Nótese que como todas las operaciones de lectura se realizan sobre objetos confirmados, no pueden ocurrir las lecturas sucias.[5]
  • Fase de validación: cuando se recibe la llamada closeTransaction, la transacción se valida para establecer si sus operaciones entraron en conflicto con las operaciones de otras transacciones sobre los mismos objetos. Si la validación es exitosa, entonces la
    transacción se confirma. Si la validación falla, entonces hay que usar alguna forma de resolución de conflictos, y habrá que abortar la transacción actual, o las otras con las cuales tiene conflicto.
  • Fase de actualización: Si una transacción es válida, todos los cambios grabados en sus versiones tentativas de los objetos se hacen permanentes. Las transacciones de solo lectura se pueden confirmar inmediatamente después de pasar la validación. Las transacciones de escritura están listas para confirmarse una vez que las versiones tentativas de los objetos fueron grabadas en el almacenamiento permanente.

Ordenamiento por marca de tiempo

En las técnicas de control de concurrencia basadas en el ordenamiento por marcas de tiempo, cada operación es validada cuando se realiza. Si la operación no puede ser validada, la transacci&
oacute;n se aborta inmediatamente y puede ser reiniciada por el cliente. A cada una de las transacciones se le asigna una marca de tiempo única cuando comienza. La marca de tiempo define su posición en la secuencia de tiempo de las transacciones. Las solicitudes de las transacciones pueden ser totalmente ordenadas de acuerdo con sus marcas de tiempo. La regla básica del ordenamiento por marca de tiempo se basa en el conflicto de operaciones y es como sigue:

La solicitud de una transacción para escribir un objeto es válida solamente si ese objeto fue leído y escrito por última vez por transacciones anteriores. La solicitud de una transacción para leer un objeto es válida solamente si ese objeto fue escrito por una transacción anterior.

Esta regla asume que hay solamente una versión de un objeto y restringe el acceso a una transacción por vez. Si cada transacción tiene su
propia versión tentativa de cada objeto que accede, entonces múltiples transacciones concurrentes pueden acceder al mismo objeto. La regla de ordenamiento por marca de tiempo se refina para asegurar que cada transacción acceda un conjunto consistente de versiones de los objetos. También debe asegurar que las versiones tentativas de los objetos sean confirmadas en el orden determinado por las marcas de tiempo de las transacciones que las realizaron. Esto se logra haciendo esperar a las transacciones, cuando sea necesario, a que las transacciones anteriores completen sus escrituras. Las operaciones de escritura se podrán realizar después de que la operación closeTransaction haya retornado, sin hacer esperar al cliente. Pero el cliente debe esperar cuando las operaciones de lectura deben esperar a que terminen las transacciones anteriores. Esto no produce deadlocks porque las transacciones solamente esperan a las anteriores (y no puede haber ciclos en el grafo de
espera).

Las marcas de tiempo se asignan del reloj del server, o se puede hacer un "pseudo-tiempo" basado en un contador (reloj lógico de Lamport).

Regla Tc Ti Resultado
1 escribir leer Tc no debe escribir un objeto que fue leído por ninguna Ti
donde Ti>Tc. Esto requiere que Tc >= máxima marca de tiempo del objeto.
2 escribir escribir Tc no debe escribir un objeto que haya sido escrito por cualquier Ti donde Ti>Tc. Esto requiere que Tc>marca de tiempo para escritura del objeto confirmado
3 leer escribir Tc no debe leer un objeto que haya sido escrito por cualquier Ti donde Ti>Tc. Esto requiere que Tc>marca de tiempo para escritura del objeto confirmado

Comparación de mé
todos de control de concurrencia

Se describieron tres métodos distintos para controlar el acceso concurrente a datos compartidos: bloqueo en dos fases estricto, métodos optimistas y ordenamiento por marca de tiempo. Todos los métodos tienen recargas en tiempo y espacio que requieren, y todos limitan hasta cierto punto el potencial para operación concurrente.

El método de ordenamiento por marca de tiempo es similar al bloqueo en dos fases en que los dos usan enfoques pesimistas en los cuales los conflictos se detectan a medida que se utilizan los objetos. Por otro lado, el método de ordenamiento por marca de tiempo decide el orden de serialización en forma estática, cuando comienza una transacción. El método de bloqueo en dos fases decide el orden de serialización en forma dinámica, según el orden en que los objetos son utilizados. Marca de tiempo resulta mejor que bloqueo en dos
fases para transacciones de solo lectura, y el bloqueo en dos fases es mejor que marcas de tiempo para transacciones de actualización.

Cuando se usa control optimista de concurrencia, a todas las transacciones se les permite continuar, pero algunas son abortadas cuando intentan confirmarse, lo cual hace que sea relativamente eficiente cuando hay pocos conflictos pero habría que repetir bastante trabajo para cuando se aborta una transacción.

Referencias

[1] – Distributed Programming en http://en.wikipedia.org/wiki/Distributed_programming
[2] – Brand, Per: “The Design Philosophy of Distributed Programming Systems: the Mozart Experience”, Royal Institute of Technology, Suecia, 2005.
Disponbile online en http://www.sics.se/~perbrand/mozart.pdf
[3] – Message Passing en http://www.cs.lmu.edu/~ray/notes/messagepassing
[4] – Ben Ari, M: “Principles of Concurrent and Distributed Programming”, Prentice-Hall, 1990
[5] – Coulouris, G et al: “Distributed Systems, concepts and design”, 3ra edición, Addison-Wesley, 2003

Be the first to comment

Leave a Reply

Your email address will not be published.


*