CONCURRENCIA

El Problema de Control de Concurrencia

Cuando dos o más transacciones se ejecutan concurrentemente, sus operaciones se ejecutan en un modelo intercalado. Esto significa que las operaciones de un programa se ejecutan entre dos operaciones de otro programa. Esta intercalación puede causar que los programas no funcionen correctamente, o interfieran, y de esta manera, dejaría inconsistente a la base de datos. Esta interferencia se debe completamente a la intercalación de las operaciones, puesto que puede ocurrir a pesar de que cada programa funciona correctamente cuando se ejecuta de forma individual y no se presenta falla alguna en el sistema. El objetivo del control de concurrencia es evitar la interferencia y, por ende, los errores.

Veamos algunos ejemplos para entender cómo es que los programas pueden interferir con otros. Volviendo al ejemplo del banco, supongamos que tenemos un programa llamado Depositar, el cual deposita dinero en una cuenta.

Procedure Depositar (Cuenta, Monto)

begin

Start;
temp := Leer(Cuentas[Cuenta]);
temp := temp + Monto;
Escribir(Cuentas[Cuenta],temp);
Commit;

end

Supongamos que la cuenta 7 tiene un saldo de US$1000 y que el cliente 1 deposita US$100 en la cuenta 7 en el mismo instante en el que el cliente 2 deposita US$100000 en la cuenta 7. Cada uno de los clientes llama al procedimiento Depositar de tal manera que se crea una transacción para realizar su actualización. La ejecución concurrente de éstos depósitos produce una secuencia de lecturas y escrituras en la base de datos, tales como

Leer₁(Cuentas[7]) devuelve el valor de US$1000
Leer₂(Cuentas[7]) devuelve el valor de US$1000
Escribir₂(Cuentas[7], US$101000
Commit₂
Escribir₁(Cuentas[7], US$1100)
Commit₁

El resultado de esta ejecución es que la Cuenta[7] contiene US$1100. A pesar que el depósito del cliente 2 concluyó satisfactoriamente, la interferencia con la ejecución de Depósito del cliente 1 causó que el depósito del cliente 2 se pierda. Este fenónemo de actualización perdida ocurre cuando dos transacciones, mientras intentan modificar un dato, ambas leen el valor antiguo del elemento antes que ninguna haya modificado su valor.

Otro problema del control de concurrencia se ilustra con el siguiente programa, llamado ImprimirSuma, el cual imprime la suma de los saldos de dos cuentas.

Procedure ImprimirSuma(Cuenta1, Cuenta2)

begin

Start;
temp1 := Leer(Cuentas[Cuenta1]);
output(temp1);
temp2 := Leer(Cuentas[Cuenta2]);
output(temp2);
temp1 := temp1 $+$ temp2;
output(temp1);
Commit;

end

Supongamos que las cuentas 8 y 9 tiene un saldo de US$200 cada una, y que el cliente 3 imprime los saldos de las cuentas 8 y 9 (utilizando ImprimirSuma) en el mismo instante en el que el cliente 4 transfiere US$100 de la cuenta 8 a la cuenta 9 (utilizando Transferir). La ejecución concurrente de estas dos transacciones puede originar la siguiente ejecución de operaciones de la base de datos.

Leer₄(Cuentas[8]) devuelve el valor de US$200
Escribir₄(Cuentas[8], US$100)
Leer₃ (Cuentas[8]) devuelve el valor de US$100
Leer₃ (Cuentas[9]) devuelve el valor de US$200
Leer₄ (Cuentas[9]) devuelve el valor de US$200
Escribir₄ (Cuentas[9], US$300)
Commit₄
Commit₃

El procedimiento Transferir interfiere con ImprimirSuma en esta ejecución, causando que ImprimirSuma imprima el valor de US$300, la cual no es la suma correcta de los saldos de las cuentas 8 y 9. El procedimiento ImprimirSuma no capturó los US$100 en tránsito de la cuenta 8 a la cuenta 9. Es importante recalcar que, a pesar de la interferencia, Transferir todavíia asigna los valores correctos en la base de datos.

Este tipo de interferencia se denomina análisis inconsistente que ocurre cuando una transacción lee un dato antes que otra transacción lo actualice y lea otro dato después que la misma transacción lo ha actualizado. Es decir, la extracción (lectura) de los datos sólo percibe algunos de los resultados de la transacción de actualización.

Para conseguir el objetivo del control de concurrencia se utiliza un sincronizador. Un sincronizador es un programa (o una colección de ellos) que controla la ejecución concurrente de las transacciones; su función radica en ordenar las operaciones que forman parte de las transacciones que se requieren ejecutar concurrentemente, de tal manera que la ejecución resultante sea correcta. Usando tres operaciones básicas (ejecución, rechazo y retraso de una operación) el sincronizador puede controlar el orden en el cual las operaciones son ejecutadas por el Administrador de Datos (DM). Cuando éste recibe una operación de la transacción (mediante el TM), usualmente trata de pasarla al DM inmediatamente, si no produce alguna ejecución incorrecta. Si el sincronizador decide que la ejecución de la operación puede producir resultados incorrectos, puede o retrasarla (en caso de que pueda procesar correctamente la operación más adelante) o rechazarla (si no es posible procesarla en el futuro de tal manera que produzca resultados correctos).

Por ejemplo, retomemos la ejecución concurrente de dos transacciones Depositar, que depositan US$100 y US$100,000 en la cuenta 7

Leer₁ (Cuentas[7]) devuelve el valor de US$1000
Leer₂ (Cuentas[7]) devuelve el valor de US$1000
Escribir₂ (Cuentas[7], US$101000)
Commit₂
Escribir₁(Cuentas[7], US$1100)
Commit₁

Para evitar esta ejecución incorrecta, un sincronizador debe decidir rechazar Escribir1 provocando que la transacción T1 sea cancelada. En este caso, el usuario o el Administrador de Transacciones puede reenviar T1 , la cual ahora se puede ejecutar sin interferir con T2. Como otra alternativa, el sincronizador puede prevenir la ejecución anterior retrasando Leer2 hasta que reciba y procese Escribir1 y de esta forma evitando que se rechace Escribir1 más adelante.

Por lo tanto, un DBMS que controla la ejecución concurrente de sus transacciones tiene una estructura como la siguiente :

SERIABILIDAD

Teoría de Seriabilidad

En los ejemplos anteriores, los errores fueron causados por la ejecución intercalada de operaciones de transacciones diferentes. Los ejemplos no muestran todas las posibles formas en las que la ejecución de dos transacciones pueden interferir, pero sí ilustran dos de los problemas que surgen con frecuencia debido a la intercalación. Para evitar estos problemas, se deben controlar las intercalaciones entre transacciones.

Una forma de evitar los problemas de interferencia es no permitir que las transacciones se intercalen. Una ejecución en la cual ninguna de dos transacciones se intercala se conoce como serial. Para ser más precisos, una ejecución se dice que es serial si, para todo par de transacciones, todas las operaciones de una transacción se ejecutan antes de cualquier operación de la otra transacción. Desde el punto de vista del usuario, en una ejecución serial se ve como si las transacciones fueran operaciones que el DBS procesa atómicamente. Las transacciones seriales son correctas dado que cada transacción es correcta individualmente, y las transacciones que se ejecutan serialmente no pueden interferir con otra.

Si el DBS procesara transacciones serialmente, significaría que no podría ejecutar transacciones concurrentemente, si entendemos concurrencia como ejecuciones intercaladas. Sin dicha concurrencia, el sistema usaría sus recursos en un nivel relativamente pobre y podría ser sumamente ineficiente.

Una solución puede ser ampliar el rango de ejecuciones permisibles para incluir aquellas que tienen los mismos efectos que las seriales. Dichas ejecuciones se conocen como serializables. Entonces, una ejecución es serializable si produce el mismo resultado y tiene el mismo efecto sobre la base de datos que alguna ejecución serial de las mismas transacciones. Puesto que las transacciones seriales son correctas, y dado que cada ejecución serializable tiene el mismo efecto que una ejecución serial, las ejecuciones serializables también son correctas.

Las ejecuciones que ilustran la actualización perdida y el análisis inconsistente no son serializables. Por ejemplo, ejecutando las dos transacciones de Depositar serialmente, en cualquier orden, da un resultado diferente al de la ejecución intercalada que pierde una actualización, por lo tanto, la ejecución intercalada no es serializable. Similarmente, la ejecución intercalada de Transferir e ImprimirSuma tiene un efecto diferente a los de cada ejecución serial de las dos transacciones, y por ello no es serializable.

Aunque éstas dos ejecuciones intercaladas no son serializables, muchas otras sí lo son. Por ejemplo, consideremos la siguiente ejecución intercalada de Transferir e ImprimirSuma. Esta ejecución tiene el mismo efecto que la ejecución serial de Transferir seguida de ImprimirSuma por lo tanto es serializable.

Leer₄ (Cuentas[8]) devuelve el valor de US$200
Escribir₄ (Cuentas[8], US$100)
Leer₃ (Cuentas[8]) devuelve el valor de US$100
Leer₄ (Cuentas[9]) devuelve el valor de US$200$
Escribir₄ (Cuentas[9], US$300)
Commit₄
Leer₃ (Cuentas[9]) devuelve el valor de US$300
Commit₃

La teoría de Seriabilidad es una herramienta matemática que permite probar si un sincronizador trabaja o no correctamente. Desde el punto de vista de la teoría de Seriabilidad, una transacción es una representación de una ejecución de operaciones de lectura y escritura y que indica el orden en el que se deben ejecutar estas operaciones. Además, la transacción contiene un Commit o un Abort como la última operación para indicar si la ejecución que representa terminó con éxito o no. Por ejemplo, la ejecución del siguiente programa

Procedure P

begin

Start;
temp := Leer(x);
temp := temp + 1;
Escribir(x, temp);
Commit;

end

puede ser presentado como r₁[x] -› w₁[x] -› c₁. Los subíndices identifican esta transacción particular y la distinguen de cualquier otra transacción que acceda al mismo dato. En general, usaremos r₁[x] (o w₁[x] para denotar la ejecución de Leer (o Escribir) ejecutado por la transacción T₁ sobre el dato x.

Cuando se ejecuta concurrentemente un conjunto de transacciones, sus operaciones deben estar intercaladas. La manera de modelar esto es usando una estructura llamada historia. Una historia indica el orden en el que se deben ejecutar las operaciones de las transacciones en relación a otras. Si una transacción T_i especifica el orden de dos de sus operaciones, estas dos operaciones deben aparecer en ese mismo orden en cualquier historia que incluya a T_i. Además, es necesario que una historia especifique el orden de todas las operaciones conflictivas que aparezcan en ella.

Se dice que dos operaciones están en conflicto si ambas operan sobre el mismo dato y al menos una de ellas es una operación de escritura (Escribir). Por lo tanto, Leer(x) está en conflicto con Escribir(x), mientras que Escribir(x) está en conflicto tanto con Leer(x) como con Escribir(x). Si dos operaciones están en conflicto, es muy importante su orden de ejecución. Consideremos las siguientes transacciones

T₁ = r₁[x] -› w₁[x] -› c₁
T₃ = r₃[x] -› w₃[y] -› w₃[x] -› c₃
T₄ = r₄[y] -› w₄[x] -› w₄[y] -› w₄[z] -› c₄

Una historia completa sobre T₁, T₃, T₄ es

H₁ = r₄[y] r₁[x] w₁[x] c₁ w₄[x] r₃[x] w₄[y] w₃[y] w₄[z] w₃[x] c₄ c₃

Clasificación de los sistemas operativos.

Con el paso del tiempo, los Sistemas Operativos fueron clasificándose de diferentes maneras, dependiendo del uso o de la aplicación que se les daba. A continuación se mostrarán diversos tipos de Sistemas Operativos que existen en la actualidad, con algunas de sus características:

Sistemas Operativos por lotes.

Los Sistemas Operativos por lotes, procesan una gran cantidad de trabajos con poca o ninguna interacción entre los usuarios y los programas en ejecución. Se reúnen todos los trabajos comunes para realizarlos al mismo tiempo, evitando la espera de dos o más trabajos como sucede en el procesamiento en serie. Estos sistemas son de los más tradicionales y antiguos, y fueron introducidos alrededor de 1956 para aumentar la capacidad de procesamiento de los programas.

Cuando estos sistemas son bien planeados, pueden tener un tiempo de ejecución muy alto, porque el procesador es mejor utilizado y los Sistemas Operativos pueden ser simples, debido a la secuenciabilidad de la ejecución de los trabajos.

Algunos ejemplos de Sistemas Operativos por lotes exitosos son el SCOPE, del DC6600, el cual está orientado a procesamiento científico pesado, y el EXEC II para el UNIVAC 1107, orientado a procesamiento académico.

Algunas otras características con que cuentan los Sistemas Operativos por lotes son:

• Requiere que el programa, datos y órdenes al sistema sean remitidos todos juntos en forma de lote.
• Permiten poca o ninguna interacción usuario/programa en ejecución.
• Mayor potencial de utilización de recursos que procesamiento serial simple en sistemas multiusuarios.
• No conveniente para desarrollo de programas por bajo tiempo de retorno y depuración fuera de línea.
• Conveniente para programas de largos tiempos de ejecución (ej, análisis estadísticos, nóminas de personal, etc.)
• Se encuentra en muchos computadores personales combinados con procesamiento serial.
• Planificación del procesador sencilla, típicamente procesados en orden de llegada.
• Planificación de memoria sencilla,  generalmente se divide en dos: parte residente del S.O. y programas transitorios.
• No requieren gestión crítica de dispositivos en el tiempo.
• Suelen proporcionar gestión sencilla de manejo de archivos: se requiere poca protección y ningún control de concurrencia para el acceso.

Sistemas Operativos de tiempo real.

Los Sistemas Operativos de tiempo real son aquellos en los cuales no tiene importancia el usuario, sino los procesos. Por lo general, están subutilizados sus recursos con la finalidad de prestar atención a los procesos en el momento que lo requieran. se utilizan en entornos donde son procesados un gran número de sucesos o eventos.

Muchos Sistemas Operativos de tiempo real son construidos para aplicaciones muy específicas como control de tráfico aéreo, bolsas de valores, control de refinerías, control de laminadores. También en el ramo automovilístico y de la electrónica de consumo, las aplicaciones de tiempo real están creciendo muy rápidamente. Otros campos de aplicación de los Sistemas Operativos de tiempo real son los siguientes:

• Control de trenes.
• Telecomunicaciones.
• Sistemas de fabricación integrada.
• Producción y distribución de energía eléctrica.
• Control de edificios.
• Sistemas multimedia.

Algunos ejemplos de Sistemas Operativos de tiempo real son: VxWorks, Solaris, Lyns OS y Spectra. Los Sistemas Operativos de tiempo real, cuentan con las siguientes características:

• Se dan en entornos en donde deben ser aceptados y procesados gran cantidad de sucesos, la mayoría externos al sistema computacional, en breve tiempo o dentro de ciertos plazos.
• Se utilizan en control industrial, conmutación telefónica, control de vuelo, simulaciones en tiempo real., aplicaciones militares, etc.
• Objetivo es proporcionar rápidos tiempos de respuesta.
• Procesa ráfagas de miles de interrupciones por segundo sin perder un solo suceso.
• Proceso se activa tras ocurrencia de suceso, mediante interrupción.
• Proceso de mayor  prioridad expropia recursos.
• Por tanto generalmente se utiliza planificación expropiativa basada en prioridades.
• Gestión de memoria menos exigente que tiempo compartido, usualmente procesos son residentes permanentes en memoria.
• Población de procesos estática en gran medida.
• Poco movimiento de programas entre almacenamiento secundario y memoria.
• Gestión de archivos se orienta  más a velocidad de acceso que a utilización eficiente del recurso.

Sistemas Operativos de multiprogramación (Sistemas Operativos de multitarea).

Se distinguen por sus habilidades para poder soportar la ejecución de dos o más trabajos activos (que se están ejecutado) al mismo tiempo. Esto trae como resultado que la Unidad Central de Procesamiento (UCP) siempre tenga alguna tarea que ejecutar, aprovechando al máximo su utilización.

Su objetivo es tener a varias tareas en la memoria principal, de manera que cada uno está usando el procesador, o un procesador distinto, es decir, involucra máquinas con más de una UCP.

Sistemas Operativos como UNIX, Windows 95, Windows 98, Windows NT, MAC-OS, OS/2, soportan la multitarea.

Las características de un Sistema Operativo de multiprogramación o multitarea son las siguientes:

• Mejora productividad del sistema y utilización de recursos.
• Multiplexa recursos entre varios programas.
• Generalmente soportan múltiples usuarios (multiusuarios).
• Proporcionan facilidades para mantener el entorno de usuarios individuales.
• Requieren validación de usuario para seguridad y protección.
• Proporcionan contabilidad del uso de los recursos por parte de los usuarios.
• Multitarea sin soporte multiusuario se encuentra en algunos computadores personales o en sistemas de tiempo real.
• Sistemas multiprocesadores son sistemas multitareas por definición  ya que  soportan la ejecución simultánea de múltiples tareas sobre diferentes procesadores.
• En general, los sistemas de multiprogramación se caracterizan por tener múltiples programas activos compitiendo por los recursos del sistema: procesador, memoria, dispositivos periféricos.

Sistemas Operativos de tiempo compartido.

Permiten la simulación de que el sistema y sus recursos son todos para cada usuario. El usuario hace una petición a la computadora, esta la procesa tan pronto como le es posible, y la respuesta aparecerá en la terminal del usuario.

Los principales recursos del sistema, el procesador, la memoria, dispositivos de E/S, son continuamente utilizados entre los diversos usuarios, dando a cada usuario la ilusión de que tiene el sistema dedicado para sí mismo. Esto trae como consecuencia una gran carga de trabajo al Sistema Operativo, principalmente en la administración de memoria principal y secundaria.

Ejemplos de Sistemas Operativos de tiempo compartido son Multics, OS/360 y DEC-10.

Características de los Sistemas Operativos de tiempo compartido:

• Populares representantes de sistemas multiprogramados multiusuario, ej.: sistemas de diseño asistido por computador, procesamiento de texto, etc.
• Dan la ilusión de que cada usuario tiene una máquina para  sí.
• Mayoría utilizan algoritmo de reparto circular.
• Programas se ejecutan con prioridad rotatoria que se incrementa con la espera y disminuye después de concedido el servicio.
• Evitan monopolización del sistema asignando tiempos de procesador (time slot).
• Gestión de memoria proporciona protección a programas residentes.
• Gestión de archivo  debe proporcionar protección y control de acceso debido a que  pueden existir múltiples usuarios accesando  a un mismo archivo.

Sistemas Operativos distribuidos.

Permiten distribuir trabajos, tareas o procesos, entre un conjunto de procesadores. Puede ser que este conjunto de procesadores esté en un equipo o en diferentes, en este caso es trasparente para el usuario. Existen dos esquemas básicos de éstos. Un sistema fuertemente acoplado es aquel que comparte la memoria y un reloj global, cuyos tiempos de acceso son similares para todos los procesadores. En un sistema débilmente acoplado los procesadores no comparten ni memoria ni reloj, ya que cada uno cuenta con su memoria local.

Los sistemas distribuidos deben de ser muy confiables, ya que si un componente del sistema se compone otro componente debe de ser capaz de reemplazarlo.

Entre los diferentes Sistemas Operativos distribuidos que existen tenemos los siguientes: Sprite, Solaris-MC, Mach, Chorus, Spring, Amoeba, Taos, etc.

Características de los Sistemas Operativos distribuidos:

• Colección de sistemas autónomos capaces de comunicación y cooperación mediante interconexiones hardware y software.
• Gobierna operación de un S.C. y proporciona abstracción de máquina virtual a los usuarios.
• Objetivo clave es la transparencia.
• Generalmente proporcionan medios para la compartición global de recursos.
• Servicios añadidos: denominación global, sistemas de archivos distribuidos, facilidades para distribución de cálculos (a través de comunicación de procesos internodos, llamadas a procedimientos remotos, etc.).

Sistemas Operativos de red.

Son aquellos sistemas que mantienen a dos o más computadoras unidas a través de algún medio de comunicación (físico o no), con el objetivo primordial de poder compartir los diferentes recursos y la información del sistema.

El primer Sistema Operativo de red estaba enfocado a equipos con un procesador Motorola 68000, pasando posteriormente a procesadores Intel como Novell NetWare.

Los Sistemas Operativos de red más ampliamente usados son: Novell NetWare, Personal NetWare, LAN Manager, Windows NT Server, UNIX, LAN tastic.