GRUPO Nº 7

Asignatura: SISTEMAS OPERATIVOS

Tema: TRANSACCIÓN Y CONTROL DE CONCURRENCIA

Integrantes:

· AYALA MOSQUEDA MARIA DE LOS ANGELES

· IBARRA SILVIA ELISABETH

· AVALOS NATALIA

· GARCIA DANIEL ANDRES

· JACOBACCI SANTIAGO

· LECCA JORGE

· AGUIRRE ALEJANDRO

· AVALOS LEONARDO

· FALABELLA MAURICIO

· LARROZA WALTER

· CHAVES MARIO

· IRAMAIN DANIEL MARCELO

· MAIZ JULIO

· LOPEZ CESAR

AÑO 2002

ÍNDICE

INTRODUCCIÓN ------------------------------------------------------------1

TRANSACCIONES---------------------------------------------------------------3

APLICACIONES DE TRANSACCIONES-----------------------------------------3

DEFINICIÓN DE TRANSACCIONES-----------------------------------------------3

PROPIEDADES DE LAS TRANSACCIONES-----------------------------------4

INSTRUCCIONES PARA EL USO DE TRANSACCIONES------------------5

TÉCNICAS DE IMPLANTACIÓN DE TRANSACCIONES--------------------5

ESTRUCTURA DE TRANSACCIONES--------------------------------------------6

PROCESAMIENTO DE TRANSACCIONES--------------------------------------7

CONDICIONES DE TERMINACIÓN DE TRANSACCIONES----------------9

TRANSACCIONES EN LOS SISTEMAS DE ARCHIVOS DISTRIBUIDOS-10

CONTROL DE CONCURRENCIA-------------------------------------------10

ALGORITMOS DE CERRADURAS O BASADOS EN CANDADOS-----11

CONTROL OPTIMISTA DE LA CONCURRENCIA---------------------------13

ALGORIMOS BASADOS EN MARCAS DE TIEMPO-----------------------14

CONTROL DE CONCURRENCIA EN SISTEMAS DE ARCHIVOS-----14 DISTRIBUIDOS

INTRODUCCION

La gran cantidad de avances e innovaciones tecnológicas que se produjeron en los últimos años tuvieron como resultado un cambio en la forma de observar a los sistemas de información, en general a las aplicaciones computacionales.

Existen avances tecnológicos que se realizan de forma constante en dispositivos de almacenamiento, circuitos, programas y metodologías. Dichos avances van de la mano junto con la demanda de los usuarios y programas para la explotación de dichos dispositivos mejorados.

Un área en la cual las soluciones están ocupando tecnología con nuevas arquitecturas, es en la de los

Sistemas distribuidos de información. Estos sistemas se refieren al manejo de datos almacenados en muchos

Sitios ligados a través de una red de comunicaciones. Un caso particular de estos sistemas distribuidos es lo que se conoce como base de datos distribuidas.

En los sistemas de base de datos distribuidas se persigue la integración de sistemas de base de datos diversos, no necesariamente homogéneos para dar a los usuarios una visión global de la información disponible. Este proceso de integración no implica la centralización de la información, mas bien, con la ayuda de la tecnología de redes de computadoras la información se mantiene distribuida y los sistemas de bases de datos distribuidos permiten el acceso a ella como si estuviera localizada en un solo lugar. La distribución de la información permite tener accesos rápidos a la misma, tener copias de la información para accesos más rápidos y para tener respaldo en caso de fallas. Un sistema de base de datos distribuida es el resultado de la integración de una base de datos distribuida con un sistema para su manejo.

Existen diversos factores relacionados a la construcción de base de datos distribuidas que no se presentan en base de datos centralizadas los más importantes son:

· Diseño de base de datos distribuida:

Se debe considerar la forma de distribuir la información entre diferentes sitios, primero, como fragmentar la información, segundo, como asignar cada fragmento entre los diversos sitios de la red Se debe considerar también si la información esta replicada es decir, si existen copias múltiples del mismo dato y, en ese caso, como mantener la consistencia de la información.

· Procesamiento de consultas:

En base de datos distribuidas el procesamiento de consultas adquiere mayor relevancia que en base de datos centralizadas. El objetivo es convertir transacciones de usuario en instrucciones para manipulación de datos.

· Control de concurrencia:

Es la actividad de coordinar accesos concurrentes a la base de datos, permite a los usuarios acceder a la base de datos de una forma multiprogramada mientras se mantiene la imagen de que cada usuario esta utilizándola solo en sistema dedicado. Asegura que transacciones múltiples sometidas por usuarios diferentes no interfieran unas con otras de forma que se produzcan resultados incorrectos. El control de concurrencia en base de datos distribuidas es más compleja que en sistemas centralizados. Un aspecto interesante del control de concurrencia es el manejo de ínterbloqueos, el sistema no debe permitir que dos o más transacciones se bloqueen entre ellas.

· Confiabilidad :

En cualquier sistema de base de datos, centralizado o distribuido, se debe ofrecer garantías de que la informacion es confiable. Así cada consulta o actualización de la informacion se realiza mediante transacciones, las cuales tienen un inicio y un fin. En sistemas distribuidos, el manejo de atomicidad y durabilidad de las transacciones es aun más complejo, ya que una sola transacción puede involucrar dos o más sitios de la red.

Responsabilidades del gestor de la base de datos

· Manejo de transacciones en forma atómica:

Puede ser muy frecuente que los datos sean totalmente incorrectos al ocurrir un fallo en una transacción como un corto en la energía eléctrica por ejemplo, por lo que una transacción debe ocurrir por completo o no ocurrir en lo absoluto a esto se refiere la atomicidad.

· Control de concurrencia o de los accesos simultáneos a la base de datos:

De no ser considerada esta responsabilidad se pueden dar el caso que una serie de actualizaciones a los mismos datos pero en tiempos minimamente diferentes, hagan que se pierdan todas las actualizaciones menos la última.

· Conservar la Seguridad de los datos

(borrados accidentales, fallos diversos, catástrofes, etc.) mediante técnicas de respaldo y recuperación. Si no se considera esto podría ocurrir una caos en el sistema.

· Personalización

(accesos no autorizados, intrusos, curiosos, etc.). Un ejemplo de lo que pasaría de no tomarlo en cuenta sería que cualquier usuario podría tener acceso a toda la información existente en nuestra base de datos

· Integridad

(reglas): De no tomarse en cuenta podrían aceptarse datos inválidos, sin sentido.. Definir, construir y manipular bases de datos.

También cabe mencionar como trabajan los sistemas de archivos distribuidos, sus características y propiedades, donde también se usa el modelo transaccional.

Ø Un sistema de archivos puede caracterizarse por las siguientes propiedades:

· <Estructura de los archivos

· <Atributos de los archivos

· <operaciones posibles sobre los archivos

· <Control de acceso y seguridad

· <Control de consistencia del propio sistema

Diferentes sistemas de archivos tienen modelos diferentes pero se usan ampliamente tres modelos. En el primero, un archivo es un bloque de datos sin ninguna estructura conocida para el servidor de archivos, dado que el servidor de archivos no conoce la estructura interna de sus archivos no puede ejecutar ninguna operación sobre las partes de esos archivos.

El segundo modelo nos presenta un modelo plano, que consiste en una secuencia ordenada de registros y en el cual los registros no necesitan ser todos del mismo tamaño y tipo.

El modelo mas general de archivos es el jerárquico, que toma la forma de un árbol. Cada nodo del árbol puede tener una etiqueta, un registro de datos, ambas cosas o ninguna.

Todos los archivos tienen atributos que los describen, como mínimo cada archivo debe tener un nombre u otro identificador y un tamaño indicando cuanto almacenamiento ocupa actualmente.

Algunos atributos son creados con el archivo y permanecen inalterados, otros (por ejemplo, la fecha de la última modificación) son mantenidos automáticamente por el sistema.

Una vez establecidas las características de los objetos de trabajo, cada sistema brinda algún mecanismo para manipular los mismos, es decir, un conjunto de operaciones que pueden efectuarse sobre el sistema de archivos. Las operaciones de archivos pueden aplicarse a un archivo como un todo o a los registros individuales que lo componen.

Algunos sistemas de archivos soportan operaciones de directorio. Los usuarios pueden crear y borrar directorios, mover archivos de un directorio a otro etc.

Todos los sistemas de archivos deben enfrentarse de alguna manera con el control de acceso y la protección de sus datos. La forma mas simple y menos confiable es asumir que todas las maquinas clientes son honestas y solo llevan a cabo los pedidos que correspondan. En una red pública la dirección del llamador provista por el concesionario del servicio durante el establecimiento de la conexión puede ser suficiente para autenticar al llamador como un equipo confiable. Por otro lado, las computadoras personales sobre una LAN son elementos más peligrosos, por lo que se necesitan mejores métodos para estos casos. Uno de esos métodos es verificar el emisor de cada pedido, ya sea incluyendo un password en cada pedido o usando algún método de autenticación digital. Un método mas elaborado es tener una o más password por archivo (una para lectura y otra para escritura, por ejemplo) .

El último detalle en analizar de los sistemas de archivos es el de la consistencia del mismo. El problema se plantea a partir que la manipulación de datos, tanto de usuario como del sistema, se lleva a cabo básicamente en memoria mientras que el disco sirve como almacenamiento estable y como soporte intermedio para operaciones con grandes volúmenes de datos. Así puede ocurrir que, ante una eventualidad, no puedan reflejarse adecuadamente en el disco los cambios llevados a cabo en memoria dando lugar, por ejemplo, a bloques que pretenden ser utilizados por mas de un archivo, a bloques que no están marcados como ocupados pero que tampoco forman parte de un archivo, etc.-

TRANSACCIONES

Los sistemas distribuidos son muy confiables debido a la posibilidad de brindar redundancia y autonomía de recursos en diferentes nodos, esto posibilita detectar y localizar fallas, sin embargo tenemos varios aspectos que representan problemas para la integridad de los recursos y que a su vez motivan el uso de transacciones

<Dificultad para mantener consistencia en los datos

<Una misma vía de comunicación no siempre puede ser utilizada para suministrar interacción entre dos procesos

<Requerimientos de procesamientos en paralelo

<Manejo interactivo de uno o mas usuarios

APLICACIONES DE TRANSACIONES

<Base de datos

<Base de datos distribuidas

<Sistema de archivos distribuidos

<Desarrollo de aplicaciones tolerantes a fallos

DEFINICIÓN DE TRANSACIONES

Las transacciones fueron originalmente desarrolladas para ser utilizadas dentro de los sistemas de base de datos, donde se usaba para ayudar en el mantenimiento de los datos de las aplicaciones y que dependían de la consistencia de la informacion almacenada.

Las transacciones son mecanismos que ayudan a simplificar la construcción de sistemas confiables mediante procesos que proporcionan soporte uniforme para invocar y sincronizar operaciones como:

<Operaciones de comparación de datos

<Aseguramiento de la seriabilidad de las transacciones con otras

<Atomicidad en su comportamiento

<Recuperación de fallas

La palabra transacción describe una secuencia de operaciones con uno o más recursos que transforman su estado actual en un nuevo estado de consistencia. Es un conjunto de operaciones sobre datos que son tratadas como una unidad. Una transacción puede terminar, haciendo sus cambios persistentes, o abortar voluntaria o involuntariamente.

Dentro del área de los sistemas computacionales el concepto de transacciones fue inicialmente utilizado para definir la consistencia entre múltiples usuarios en una base de datos. Una transacción es una colección de operaciones que hacen transformaciones consistentes de los estados de un sistema conservando la consistencia del sistema. Una base de datos esta en estado consistente si cumple todas las restricciones de integridad definidas sobre ella. Los cambios de estado se dan debido a actualización, inserción y eliminación de la informacion. Se quiere asegurar que la base de datos no entre en un estado de inconsistencia, pero durante la ejecución de una transacción, la base de datos puede estar temporalmente en un estado inconsistente. Lo importante aquí es asegurar que la base de datos vuelva aun estado consistente al concluir la ejecución de una transacción (Figura A)

Figura A . Un modelo de transacción.

Lo que se persigue con el uso de transacciones es por un lado contar con una transparencia adecuada de las acciones concurrentes a una base de datos y por el otro tener una transparencia adecuada en el manejo de las fallas que se pueden presentar en una base de datos.

Comentario sobre el modelo

Una transacción es una acción atómica, siendo una unidad de control de concurrencia y de recuperación. Las transacciones se mantienen consistentes solo si se efectúa a partir de un estado consistente. Las transacciones simplifican el modelo computacional dado que proveen:

< Transparencia de concurrencia

< Transparencia de fallos

PROPIEDEADES DE LAS TRANSACCIONES

· Atomicidad:

Una transacción es tratada como una unidad de operación. Por lo tanto todas las acciones de la transacción se llevan a cabo o ninguna de ellas se realiza .La atomicidad requiere que si una transacción se interrumpe por una falla, sus resultados parciales deben ser deshechos. Se efectúan todas las transacciones, pero en caso de fallas no se realiza ninguna. Una transacción debe concluir comprometida o abortada. En el caso del compromiso se instalan todas las actualizaciones y en el aborto se descartan todas las actualizaciones.

· Consistencia :

Una transacción es un programa correcto que lleva la base de datos de un estado consistente a otro con la misma característica. Gracias a esto, las transacciones no violan las reglas de integridad de una base de datos.

· Aislamiento :

Durante la ejecución de una transacción, esta no debe revelar sus resultados a otras transacciones concurrentes antes de su compromiso. Si varias transacciones se ejecutan concurrentemente, los resultados deben ser los mismos que si ellas se hubieran ejecutado en forma secuencial (Seriabilidad). La seriabilidad consiste en asegurarse que los cambios siguen un orden adecuado.

· Durabilidad :

Es la propiedad de las transacciones que asegura que una vez que una transacción realiza su compromiso, sus resultados son permanentes y no pueden ser borrados de la base de datos, se asegura que los resultados de una transacción sobrevivirán a fallas del sistema.

Las transacciones brindan una ejecución atómica y confiable en presencia de fallas, una ejecución correcta en presencia de accesos de usuario múltiples y un manejo correcto de replicas (en el caso que se soporten).

INSTRUCCIONES PARA EL USO DE TRANSACIONES

La programación con uso de transacciones requiere de instrucciones especiales, las cuales deben ser proporcionadas por el sistema operativo, por el compilador del lenguaje o por el manejador de la base de datos, algunos son:

BEGIN _TRANSACCIÓN: Los comandos siguientes forman una transacción

END _ TRANSACCIÓN: Termina la transacción y se intenta un compromiso

ABORT_ TRANSACCIÓN: Se elimina la transacción, se recuperan los valores anteriores

READ: Se leen datos de un archivo

WRITE: Se escriben datos en un archivo

Las operaciones entre BEGIN y END forman el cuerpo de la transacción y deben ejecutarse todas o ninguna de ellas. La cantidad exacta de instrucciones disponibles para manejar transacciones depende del tipo de objetos y operaciones que deban ser procesadas.

TÉCNICAS DE IMPLANTACIÓN DE TRANSACCIONES

> Área de trabajo privada

> Bitácora de escritura anticipada

> Protocolo de compromiso de dos fases (two-phase)

1. Área de trabajo privada:

Consiste en realizar copias de los bloques que serán utilizados dentro de una transacción de manera que se trabaje con estas copias para realizar todas las modificaciones necesarias. Todo el espacio de trabajo con la informacion que será utilizada es contenida dentro de estas copias denominado área de trabajo privada. Los demás usuarios trabajaran con la copia original de los bloques pero no podrán obtener una segunda copia de los mismos.

Al iniciarse la transacción el proceso obtiene una copia privada de los datos.Lecturas y escrituras sobre la zona privada. Para optimizar solo se crean copias privadas de los datos modificados. Una segunda optimización para los datos que están organizados en bloques apuntados desde un índice, como los ficheros, es crear copias solo de los fragmentos modificados.

2. Bitácora de escritura anticipada:

Este método consiste en realizar una copia con todas las transacciones que van siendo ejecutadas hacia un bloque o espacio (LOG) de trabajo que sea estable, esta lista se la conoce como lista de intenciones.

Las transacciones serán actualizadas con la informacion una vez que se ha determinado el fin de la transacción.

Se modifican los datos pero antes se escribe en un log sobre memoria estable la descripción de la operación. En el log también se escriben registros para indicar el inicio y fin de la transacción, cuando se aborta la transacción se recorre el log para deshacer los cambios. Después de una caída temporal, se debe recorrer el log. Si una transacción no ha escrito su registro de fin se aborta, si lo ha escrito, se hacen los cambios pendientes. Para evitar recorrer todo el log después de un fallo temporal de la maquina, se usan generalmente checkpoints.

3. Protocolo de compromiso de dos fases:

En un sistema distribuido una transacción puede afectar a varios procesadores lo cual dificulta la atomicidad. La solución más típica es el protocolo de compromiso de dos fases (C2F). En este protocolo existe un coordinador que normalmente es el proceso que inicio la transacción.

Fase 1: El coordinador escribe en el log almacenado en memoria estable el registro (preparar T). Manda un mensaje con ese contenido a los nodos implicados en la transacción. Cada proceso implicado decide si esta listo para hacer el compromiso, escribe en su log la decisión (listo T o no listo T) y la manda en un mensaje al coordinador.

Fase 2: Si el coordinador recibe alguna respuesta negativa u obtiene alguna falla de respuesta decide abortar la transacción. En caso contrario decide realizar el compromiso.

El coordinador escribe en el log la decisión y manda un mensaje a los procesos implicados. Cada proceso que recibe el mensaje escribe en su log la decisión del coordinador y realiza la acción correspondiente.

La terminación de una transacción se hace mediante la regla del compromiso global. El coordinador aborta una transacción si y solo si al menos un proceso implicado decide abortar. El coordinador hace un compromiso de la transacción si y solo si todos los participantes deciden realizar el compromiso.

Comportamiento ante un fallo de un nodo: El nodo N se recupera después de una caída transitoria y detecta que la transacción T estaba a medias. Si el log contiene (compromiso T) se realiza la transacción. Si contiene (abort T) se aborta la transacción, si contiene (listo T) debe consultar al coordinador para determinar si se compromete o aborta la transacción, si no hay mensajes en el log se aborta.

Comportamiento ante fallos del coordinador: Cada nodo implicado N debe decidir sobre la transacción T. Si el log contiene (compromiso T) se realiza la transacción. Si contiene (abort T) se aborta, si no contiene (listoT) el coordinador no ha podido decidir el compromiso, por lo tanto, lo mas apropiado es abortar la transacción. Si todos los nodos tienen (listo T) pero ninguno tiene (compromiso T) o (abort T) no se puede determinar la decisión del coordinador. Se debería esperar que se recuperase.

ESTRUCTURA DE LAS TRANSACCIONES

La estructura de una transacción usualmente viene dada según el modelo de la transacción, estas pueden ser planas (simples) o anidadas.

· Transacciones planas:

Consisten en una secuencia de operaciones primitivas encerradas entre las palabras clave BEGIN y END. Por ejemplo:

BEGIN _TRANSACTION Reservación

....

END.

· Transacciones Anidadas :

Consiste en tener transacciones que dependen de otras, estas transacciones están incluidas dentro de otras de un nivel superior y se las conoce como subtransacciones. La transacción de nivel superior puede producir hijos (subtransacciones) que hagan más fácil la programación del sistema y mejoras del desempeño.

En las transacciones anidadas las operaciones de una transacción pueden ser así mismo otras transacciones. Por ejemplo:

BEGIN _TRANSACTION Reservación

..........

BEGIN _TRANSACTION Vuelo

........

END.( Vuelo ) ......

BEGIN _TRANSACTION Hotel

........

END

......

END.

Una transacción anidada dentro de otra conserva las mismas propiedades que las de su padre, esto implica, que puede contener así mismo transacciones dentro de ella. Existen restricciones obvias en una transacción anidada: debe empezar después que su padre y debe terminar antes que el. El compromiso de una subtransaccion es condicional al compromiso de su padre, si el padre de una o varias subtransacciones aborta, las subtransacciones hijas también serán abortadas. Las transacciones anidadas brindan un nivel mas alto de concurrencia entre transacciones. Ya que una transacción consiste de varias transacciones es posible tener mayor concurrencia dentro de una sola transacción.

Así también, es posible recuperarse de de fallas de forma independiente de cada subtransaccion. Esto limita el daño a una parte mas pequeña de la transacción, haciendo que el costo de la recuperación sea el menor.

También se deben considerar el orden de las lecturas y escrituras. Si las acciones de lectura y escritura pueden ser mezcladas sin ninguna restricción, entonces, a este tipo de transacciones se les conoce como Generales .Por el contrario, si se restringe o impone que un dato debe ser leído antes de que pueda ser escrito entonces se tendrán transacciones Restringidas. Si las transacciones son restringidas a que todas las acciones de lectura se realicen antes de las acciones de escritura entonces se les conoce como de Dos Pasos. Finalmente existe un modelo de acción para transacciones restringidas en donde se aplica aun más la restricción de que cada par < read , write > tiene que ser ejecutado de manera atómica.

PROCESAMIENTO DE TRANSACCIONES

Los siguientes son los aspectos más importantes relacionados con el procesamiento de transacciones:

· Modelo de estructura de transacciones

Es importante considerar si las transacciones son planas o anidadas.

· Consistencia de la base de datos interna

Los algoritmos de control de datos tienen que satisfacer las restricciones de integridad cuando una transacción pretende hacer un compromiso.

· Protocolos de confiabilidad

En transacciones distribuidas es necesario introducir medios de comunicación entre los diferentes nodos de una red para garantizar la atomicidad de las transacciones.

· Algoritmos de control de concurrencia

Deben sincronizar la ejecución de transacciones concurrentes bajo el criterio de correctitud. La consistencia entre transacciones se garantiza mediante el aislamiento de las mismas.

· Protocolos de control de replicas

Se refiere a como garantizar la consistencia mutua de datos replicados.

El procesamiento de transacciones básicamente consiste en una serie de modificaciones (transacciones) a un determinado recurso del sistema (por ejemplo una base de datos) y en donde se define un punto de inicio y un punto de terminación que define un bloque entre el conjunto de operaciones que son realizadas.

Dentro de este proceso en bloque los demás usuarios no pueden modificar nada hasta que no se presente un estado estable de los datos, esto ocasiona inconsistencia temporal y conflictos. Para evitar lo anterior se implementan dos maneras diferentes:

<Ejecución de transacciones serializadas

< Ejecución de transacciones calendarizadas

1- Ejecutar transacciones serializadas:

Es un sistema que permite el procesamiento de transacciones en forma secuencial o serializado dándole una secuencia a cada transacción, este proceso reduce el rendimiento del sistema, pero tiene como ventaja que el proceso de sincronización es más sencillo.

2- Ejecutar transacciones calendarizadas:

Permite el proceso de transacciones asignándoles tiempos de procesamiento el cual permite incrementar el rendimiento del sistema ya que se ejecuta un máximo de procesos en forma concurrente y no a través de una serie. La ventaja es que a un mismo tiempo de reloj se pueden hacer dos operaciones, aunque el proceso de sincronización es mas complicado.

Un aspecto muy importante en el manejo de transacciones es el de mantener y aplicar algoritmos de control sobre los datos o recursos; para ese control también se utilizan protocolos que proporcionen confiabilidad como lo siguientes:

< Atomicidad

< Protocolos de recuperación total

< Protocolos de compromiso global

El control de las transacciones también requiere de controlar la concurrencia del acceso y uso hacia el recurso que se esta manipulando, ese control de concurrencia tiene dos objetivos:

< Como sincronizar la ejecución concurrente de transacciones

< Consistencia intra transacción (Aislamiento)

Para llevar a cabo el control de concurrencia dentro de un proceso de transacciones se manejan dos modos:

< Ejecución centralizada de transacciones (Figura B)

< Ejecución distribuida de transacciones (Figura C)

Figura B. Ejecución centralizada de transacciones.

Figura C. Ejecución distribuida de transacciones.

CONDICIONES DE TERMINACION DE UNA TRANSACCION

Una transacción siempre termina, aun en la presencia de fallas. Si una transacción termina de manera exitosa se dice que la transacción hace un compromiso. Si la transacción se detiene sin terminar su tarea, se dice que la transacción aborta . Cuando la transacción es abortada, puede ser por distintas razones relacionadas con la naturaleza de la transacción misma, o por conflicto con otras transacciones o por fallo de un proceso o computador, entonces su ejecución es detenida y todas las acciones ejecutadas hasta el momento son deshechas regresando a la base de datos al estado antes de su ejecución. A esta operación también se la conoce como rollback.

TRANSACCIONES EN LOS SISTEMAS DE ARCHIVOS DISTRIBUIDOS

Como alternativa a tener clientes que instalen bloqueos individuales, algunos servidores de archivos soportan acciones atómicas, a menudo llamadas transacciones. Cuando esta disponible esta facilidad, un cliente puede indicarle al servidor que comience una transacción, seguida por cualquier numero de aperturas y operaciones de archivos, y finalizar con un comando para terminar la transacción. El servidor debe ser capaz de llevar a cabo todos los pedidos efectuados de forma atómica (indivisible) sin interferencia de otros pedidos de clientes. Si el cliente decide abortar la transacción o finalizan sus temporizadores, todos los archivos son restaurados al estado anterior al comienzo de la transacción. Una transacción es cualquier operación de E/S sobre un archivo que modifica el contenido de un archivo existente del mismo. Esto incluye el agregar datos, cambiar el tamaño y sobrescribir datos existentes.

En una implementación, junto al archivo de datos existe el denominado transaction log file que mantiene la descripción de las modificaciones hechas sobre el archivo de datos y el mantenimiento de este archivo se llama transaction tracking. La operación denominada transaction rollback es aquella por la cual las alteraciones indicadas en el log se deshacen retornando los datos al estado previo (estado inicial), que se supone consistente.

Dentro de los objetivos de diseño de un sistema de transacciones se tienen:

< Minimizar la sobrecarga de los sistemas de archivos , < Identificar automáticamente las inconsistencias de datos. Una vez identificados debe producirse una operación rollback sin la intervención del usuario. Obviamente mientras se produce esta operación, debe negarse el acceso a los archivos potencialmente corruptos. < maximizar la portabilidad.

La clave esta en la posibilidad de volver al punto de partida y, si corresponde, rehacer las operaciones.

Para ello debe disponerse de la siguiente informacion:

< Identificación completa y univoca del archivo de datos.

< El modo y los permisos utilizados al abrir el archivo.

< La ubicación de los datos modificados.

< Una copia de los datos originales.

< La descripción de la alteración que tuvo lugar.

< Los datos con que se llevo a cabo tal modificación.

Esta informacion convenientemente organizada, forma el núcleo de los denominados registros de transacciones, la unidad de datos de datos de los archivos log

EL CONTROL DE CONCURRENCIA EN EL MODELO TRANSACCIONAL

Los bloqueos se pueden definir formalmente como sigue: "Un conjunto de procesos se bloquean si cada proceso del conjunto esta esperando un evento que solo otro proceso del conjunto puede provocar". Puesto que todos los procesos están en espera, ninguno de ellos podrá ocasionar nunca ninguno de los eventos que podrían desbloquear a algunos de los otros miembros del conjunto y los demás procesos seguirán esperando indefinidamente

El control de concurrencia trata sobre los problemas de aislamiento y consistencia del procesamiento de transacciones. El control de concurrencia distribuido en sistema de manejo de bases de datos distribuidas asegura que la consistencia de la base de datos se mantiene, en un ambiente distribuido multiusuario. Si las transacciones son internamente consistentes, la manera más simple de lograr este objetivo es ejecutar cada transacción sola, una después de otra. Sin embargo esto puede afectar enormemente el desempeño de un sistema de manejo de bases de datos distribuidas dado que el nivel de concurrencia se reduce al mínimo. El nivel de concurrencia, el numero de transacciones activas, es probablemente el parámetro mas importante en sistemas distribuidos. Los mecanismos de control de concurrencia buscan encontrar un balance entre el mantenimiento de la consistencia de la base de datos y el mantenimiento de un alto nivel de concurrencia. El fallo en diseño de mecanismos apropiados de sincronización y en obligar su uso por cada proceso que utiliza recursos comunes, produce frecuentemente un comportamiento erróneo del sistema y rupturas que son notablemente difícil de depurar. La concurrencia puede producir un incremento de la productividad cuando se implementan correctamente, pero puede también degradar la fiabilidad cuando la sincronización impropia entre procesos contamina el sistema con errores artificios de tiempo.

Si no se lleva a cabo un adecuado control de concurrencia, se podrían llegar a presentar dos anomalías. En primer lugar, se pueden perder actualizaciones provocando que los efectos de algunas transacciones no se reflejen en la base de datos. En segundo lugar, pueden presentarse recuperaciones de informacion inconsistentes.

Los algoritmos para el control de concurrencia son útiles cuando se ejecutan varias transacciones al mismo tiempo

Los principales algoritmos son:

< Los de cerradura o basados en candados

< El de control optimista de la concurrencia

< El de las marcas de tiempo

El conjunto de algoritmos pesimistas esta formado por algoritmos basados en candados, algoritmos basados en ordenamiento por estampas de tiempo y algoritmos híbridos. Los algoritmos optimistas se componen por los algoritmos basados en candados y algoritmos basados en estampas de tiempo. (Figura D)

Figura D. Clasificación de los algoritmos de control de concurrencia.

ALGORITMOS DE CERRADURA O BASADOS EN CANDADOS

En los algoritmos basados en candados, las transacciones indican sus intenciones solicitando candados al despachador (llamado el administrador de candados) Los candados son de lectura , también llamados compartidos, o de escritura , también llamados exclusivos.

En sistemas basados en candados, el despachador es un administrador de candados . El administrador de transacciones le pasa al administrador de candados la operación sobre la base de datos (lectura o escritura) e información asociada, como por ejemplo el elemento de datos que es accesado y el identificador de la transacción que está enviando la operación a la base de datos. El administrador de candados verifica si el elemento de datos que se quiere accesar ya ha sido bloqueado por un candado. Si el candado solicitado es incompatible con el candado con que el dato está bloqueado, entonces, la transacción solicitante es retrasada. De otra forma, el candado se define sobre el dato en el modo deseado y la operación a la base de datos es transferida al procesador de datos. El administrador de transacciones es informado luego sobre el resultado de la operación. La terminación de una transacción libera todos los candados y se puede iniciar otra transacción que estaba esperando el acceso al mismo dato.

Se usan cerraduras o candados de lectura o escritura sobre los datos. Para asegurar la secuencialidad se usa un protocolo de dos fases, en la fase de crecimiento de la transacción se establecen los cerrojos y en la fase de decrecimiento se liberan los cerrojos. Hay que tener en cuenta que se pueden producir ínterbloqueos. En los sistemas distribuidos el nodo que mantiene un dato se encarga normalmente de gestionar los cerrojos sobre el mismo.

Candados de dos fases : En los candados de dos fases una transacción le pone un candado a un objeto antes de usarlo. Cuando un objeto es bloqueado con un candado por otra transacción, la transacción solicitante debe esperar. Cuando una transacción libera un candado, ya no puede solicitar más candados. En la primera fase solicita y adquiere todos los candados sobre los elementos que va a utilizar y en la segunda fase libera los candados obtenidos uno por uno.

Puede suceder que si una transacción aborta después de liberar un candado, otras transacciones que hayan accesado el mismo elemento de datos aborten también provocando lo que se conoce como abortos en cascada. Para evitar lo anterior, los despachadores para candados de dos fases implementan lo que se conoce como los candados estrictos de dos fases en los cuales se liberan todos los candados juntos cuando la transacción termina (con compromiso o aborta).

Candados de dos fases centralizados: En sistemas distribuidos puede que la administración de los candados se dedique a un solo nodo del sistema, por lo tanto, se tiene un despachador central el cual recibe todas las solicitudes de candados del sistema. La comunicación se presenta entre el administrador de transacciones del nodo en donde se origina la transacción , el administrador de candados en el nodo central y los procesadores de datos de todos los nodos participantes. Los nodos participantes son todos aquellos en donde la operación se va a llevar a cabo.

Figura E. Comunicación en un administrador centralizado de candados de dos fases.

La crítica más fuerte a los algoritmos centralizados es el "cuello de botella" que se forma alrededor del nodo central reduciendo los tiempos de respuesta de todo el sistema. Su disponibilidad es reducida a cero cuando se presentan fallas en el nodo central.

Candados de dos fases distribuidos:

En los candados de dos fases distribuidos se presentan despachadores en cada nodo del sistema. Cada despachador maneja las solicitudes de candados para los datos en ese nodo. Una transacción puede leer cualquiera de las copias replicada del elemento x, obteniendo un candado de lectura en cualquiera de las copias de x. La escritura sobre x requiere que se obtengan candados para todas las copias de x. Los mensajes de solicitud de candados se envían a todos los administradores de candados que participan en el sistema. Las operaciones son pasadas a los procesadores de datos por los administradores de candados. Los procesadores de datos envían su mensaje de "fin de operación" al administrador de transacciones coordinador

Figura F. Comunicación en candados de dos fases distribuidos

CONTROL OPTIMISTA DE LA CONCURRENCIA

Los algoritmos de control de concurrencia pesimistas asumen que los conflictos entre transacciones son muy frecuentes y no permiten el acceso a un dato si existe una transacción conflictiva que accesa el mismo dato. Así, la ejecución de cualquier operación de una transacción sigue la secuencia de fases: validación , lectura , cómputo y escritura (ver Figura G). Los algoritmos optimistas, por otra parte, retrasan la fase de validación justo antes de la fase de escritura (ver Figura G). De esta manera, una operación sometida a un despachador optimista nunca es retrasada.

Las operaciones de lectura, cómputo y escritura de cada transacción se procesan libremente sin actualizar la base de datos corriente. Cada transacción inicialmente hace sus cambios en copias locales de los datos. La fase de validación consiste en verificar si esas actualizaciones conservan la consistencia de la base de datos. Si la respuesta es positiva, los cambios se hacen globales (escritos en la base de datos corriente). De otra manera, la transacción es abortada y tiene que reiniciar

Lo que se hace es dejar ejecutar las transacciones y si al terminar se detecta que ha habido conflicto se aborta y se reinicia la transacción.

Cada transacción tiene tres fases:.

< Fase de lectura: Cuerpo de la transacción donde se copian datos desde la base de datos, copias que pueden ser actualizadas pero sin copiar a la base de datos

< Fase de validación: Se comprueba que no existan conflictos

< Fase de escritura: Si no existen conflictos se instalan lo cambios en la base de datos

Conflictos entre operaciones: Dos operaciones están en conflicto entre si cuando, operan sobre los mismos datos, una de las operaciones es de escritura, o cada operación pertenece a diferentes transacciones.

Figura G. Fases de la ejecución de una transacción a) pesimista, b) optimista

ALGORITMOS BASADOS EN MARCAS DE TIEMPO

A diferencia de los algoritmos basados en candados, los algoritmos basados en marcas de tiempo no pretenden mantener la seriabilidad por la exclusión mutua. En su lugar eligen un orden de serializacion en primera instancia y ejecutan las transacciones de acuerdo a ese orden. En estos algoritmos cada transacción lleva asociada una marca de tiempo. Cada dato lleva asociado dos marcas de tiempo: uno de lectura y otro de escritura, que reflejan la marca de tiempo de la transacción que hizo la ultima operación de ese tipo sobre el dato. Para leer la marca de tiempo de escritura del dato, debe ser menor que el de la transacción, si no aborta. Para escribir las marcas de tiempo de escritura y lectura del dato, deben ser menores que el de la transacción, sino se aborta. Esta técnica esta libre de Ínterbloqueos pero puede darse que halla que repetir varias veces la transacción. En los sistemas distribuidos se puede usar un mecanismo como, los relojes de Lamport para asignar marcas de tiempo.

CONTROL DE CONCURRENCIA EN SISTEMAS DE ARCHIVOS DISTRIBUIDOS

Hasta aquí se a hablado sobre el modelo transaccional haciendo hincapié en lo referido a base de datos distribuidas. En adelante se desarrollara como se emplea el control de concurrencia en sistemas distribuidos de archivos

Los sistemas de archivos que forman parte de una red de computadoras tienen múltiples clientes de los que encargarse. Si dos o mas clientes, accidentalmente o no, deciden acceder al mismo archivo al mismo tiempo pueden producirse conflictos. La solución utilizada es permitir a los usuarios el uso de bloqueos sobre los archivos de trabajo. La idea es sencilla, mientras un usuario esta trabajando sobre una parte de los datos, otros no podrán hacerlo de manera que las distintas actualizaciones se efectuaran en forma sucesiva y ordenada sin interferencias. Se utilizan dos clases de bloqueos: Los bloqueos compartidos que por lo general se usan para lectura , y los bloqueos exclusivos que normalmente se usan para escritura. La granularidad del bloqueo es otra consideración importante. Es posible bloquear archivos enteros, pero también es posible bloquear archivos enteros o subárboles, cuanto menor sea la unidad lógica bloqueada mayor será la concurrencia admisible. El concepto de bloqueo introduce varios problemas de contrapartida. Primero, si un cliente necesita acceder a varios archivos, como ocurre de forma común cuando se efectúan transferencias de dinero en aplicaciones bancarias, hay una posibilidad de abrazo mortal.

Abrazos mortales:

Principalmente, existen dos métodos para manejar el problema de los abrazos mortales. Podemos usar algún protocolo para asegurar que el sistema nunca entrará en un estado de abrazo mortal. Alternativamente, podemos permitir que el sistema entre en un estado de abrazo mortal y después recuperarnos. El recuperarse de un abrazo mortal puede ser muy difícil y muy caro. Por ello, primeramente consideraremos los métodos para asegurar que no ocurran los abrazos mortales. Comúnmente, existen dos métodos. El de PREVENCIÓN de abrazos mortales y el de EVASIÓN de abrazos mortales. Un conjunto de procesos está en un abrazo mortal cuando todos los procesos en ese conjunto están esperando un evento que sólo puede ser causado por otro proceso en el conjunto. Los eventos a los cuales nos estamos refiriendo son
concernientes con la asignación y liberación de recursos principalmente. Sin embargo, pueden llevar a la
existencia de abrazos mortales.

Para ejemplificar un estado de abrazo mortal, se considerara un sistema con tres unidades de disco. Supongamos que existen tres procesos, cada uno de ellos tiene asignada una de las unidades de disco. Si ahora cada proceso pide otra unidad de disco, los tres procesos se encuentran ahora en un estado de abrazo mortal. Cada uno esta esperando el evento "unidad de disco liberada", lo cual solo puede ser causada por alguno de los otros procesos en espera. Este ejemplo ilustra un abrazo mortal involucrando procesos compitiendo por el mismo tipo de recurso. Los abrazos mortales pueden también involucrar diferentes tipos de recursos. Por ejemplo, consideremos un sistema con una impresora y una unidad de disco. Supongamos que el proceso A tiene asignada la unidad de disco y que el proceso B tiene asignada la impresora. Ahora, si A pide la impresora y B pide la unidad de disco, ocurre un abrazo mortal.

Ejemplo de un abrazo mortal.

Es obvio que un abrazo mortal es una condición indeseable. En un abrazo mortal, los procesos nunca terminan de ejecutarse y los recursos del sistema están amarrados, evitando que otros procesos puedan siquiera empezar.

Condiciones Necesarias . Una situación de abrazo mortal puede surgir sí y solo sí las siguientes cuatro condiciones ocurren simultáneamente en un sistema:

Exclusión Mutua. Cada recurso se asigna por lo regular exactamente a un proceso o bien esta disponible. Al menos un recurso es mantenido en un modo no-compartible;

esto es, sólo un proceso a la vez puede usar el recurso. Si otro proceso solicita ese recurso, tiene que ser retardado hasta que el recurso haya sido liberado.

Retener y Esperar. Los procesos que regularmente contienen recursos otorgados antes pueden solicitar nuevos recursos. Debe existir un proceso que retenga al menos un recurso y esté esperando para adquirir recursos adicionales que están siendo retenidos por otros procesos.

No existe el derecho de desasignar : Los recursos previamente otorgados no pueden extraerse por la fuerza de un proceso. Deben ser liberados explícitamente por el proceso que los contiene. Los recursos no pueden ser desasignados ; esto es, un recurso sólo puede ser liberado voluntariamente por el proceso que lo retiene, después de que el proceso ha terminado su tarea.

Espera Circular. Debe haber una cadena de dos o más procesos, cada uno de los cuales esté esperando un recurso contenido en el siguiente miembro de la cadena. Debe existir un conjunto {p0, p1, ...,pn} de procesos en espera tal que p0 esté esperando por un recurso que está siendo retenido por p1, p1 está esperando por un recurso que está siendo retenido por p2, ..., pn-1 está esperando por un recurso que está siendo retenido por pn y pn está esperando por un recurso que está siendo retenido por p0.

Se remarca que las cuatro condiciones deben de cumplirse para que pueda ocurrir un abrazo mortal. La condición de espera circular implica la condición de retener y esperar, de tal manera que las cuatro condiciones no son totalmente independientes. Sin embargo, puede ser útil el considerar cada condición por separado.

Una forma de modelar estas condiciones es usando un grafo de recursos: los círculos representan procesos, los cuadrados recursos. Una arista desde un recurso a un proceso indica que el recurso ha sido asignado al proceso. Una arista desde un proceso a un recurso indica que el proceso ha solicitado el recurso, y está bloqueado esperándolo. Entonces, si hacemos el grafo con todos lo procesos y todos los recursos del sistema y encontramos un ciclo, los procesos en el ciclo están bajo bloqueo mutuo.

Ejemplo de un grafo de recursos.

La discusión del control de concurrencia hasta aquí se ha centralizado alrededor del problema de que hacer cuando múltiples usuarios quieren actualizar el mismo archivo. Una manera completamente diferente es prevenir todas las actualizaciones. Desde este punto de vista, los archivos son inmutables; una vez que se crea un archivo no puede modificarse. En este caso, para incorporar nueva informacion en el archivo, un cliente puede crear una nueva versión del archivo que reemplaza (pero no modifica) el original. De esta manera, un archivo se vuelve una secuencia de versiones inmutables. La sincronización entre procesos es necesaria para prevenir y corregir errores de sincronización debidos al acceso concurrente de recursos compartidos, tales como estructuras de datos o dispositivos de E/S, de procesos contendientes. La sincronización entre procesos también permite intercambiar señales de tiempo entre procesos cooperantes para garantizar las relaciones específicas de precedencia impuestas por el problema que se resuelva. Sin una sincronización adecuada entre procesos, la actualización entre variables compartidas puede inducir a errores de tiempo relacionadas con la concurrencia que son con frecuencia difíciles de depurar. Una de las causas principales de este problema es que procesos concurrentes puedan tener valores temporalmente inconsistentes de una variable compartida mientras se actualizan. Los semáforos son un mecanismo sencillo pero poderoso de sincronización entre procesos. Los semáforos satisfacen la mayoría de los requerimientos que hemos especificado para un buen mecanismo de control de concurrencia, sin incluir suposiciones sobre las velocidades y prioridades relativas de los procesos contendientes y sin saber nada sobre los otros contendientes excepto que existen probablemente. Mediante el uso de semáforos se pueden resolver algunos problemas bien conocidos de sincronización, como los de PRODUCTOR/CONSUMIDOR y LECTORES/ESCRITORES.

Sincronización entre procesos

La ejecución concurrente de procesos, puede producir mejoras significativas de rendimiento respecto a la ejecución secuencial de programas. Cuando es critico el rendimiento, se puede dividir el trabajo en varios procesos cooperantes definidos por el programador para explotar la posible concurrencia de un programa o aplicación dada. Sin embargo, para que funcione apropiadamente un grupo de procesos, se deben sincronizar sus actividades de forma que asegure la observancia de las relaciones de precedencia dictadas por el problema que se está resolviendo. La sincronización entre procesos es necesaria para preservar la integridad del sistema y prevenir problemas de tiempo producidos por el acceso concurrente a recursos compartidos por múltiples procesos. En general, los procesos cooperantes deben sincronizarse siempre que intenten usar recursos compartidos por varios de ellos, tales como estructuras de datos o dispositivos físicos comunes. El fallo en diseño de protocolos apropiados de sincronización y en obligar su uso por cada proceso que utiliza recursos comunes, produce frecuentemente un comportamiento erróneo del sistema y rupturas que son notablemente difíciles de depurar. La concurrencia puede producir un incremento de la productividad cuando se implementan correctamente, pero puede también degradar la fiabilidad cuando la sincronización impropia entre procesos contamina el sistema con errores artificios de tiempo.