Los datos de los sistemas de bases de datos se almacenan en archivos. Cada archivo esta dividido en unidades de almacenamiento de longitud constante denominada bloques (unidades de asignación de almacenamiento y de transferencia de datos). Cada bloque puede contener varios elementos de datos dependiendo de la organización física de los datos, en su mayoría cada elemento de dato no utiliza dos o más bloques.

Uno de los principales objetivos del sistema de bases de datos es minimizar el número de transferencias de bloques entre el disco y la memoria, una manera de lograrlo es mantener en lo posible la mayor cantidad de bloques en la memoria del sistema, de tal forma que no sea necesario el acceso al disco.

Dado que no es posible mantener todos los bloques en la memoria principal, se debe aplicar estrategias para optimizar el uso de espacio en la memoria. La memoria intermedia (buffer) es la parte de la memoria principal disponible para el almacenamiento de bloques del disco. Siempre se guarda una copia del bloque en el disco, pero esta copia puede ser una versión más antigua del bloque de la memoria intermedia. El subsistema de la asignación del espacio de la memoria intermedia se denomina gestor de la memoria intermedia.

Gestor de la memoria intermedia

El sistema de base de datos formulan solicitudes al gestor de la memoria intermedia cuando necesitan bloques de disco. Si el bloque ya esta en la memoria intermedia el gestor envía la dirección de memoria del bloque. Si el bloque no se halla en la memoria intermedia, el gestor de la memoria intermedia asigna en primer lugar espacio al bloque en la memoria intermedia, descartando algún otro bloque si hace falta para hacer sitio para el nuevo bloque. Sólo se vuelve a escribir en el disco el bloque que se descarta si se modificó desde la última vez que se escribió en el disco. A continuación, el gestor de la memoria intermedia lee el bloque del disco y lo escribe en la memoria intermedia, y pasa la dirección del bloque en la memoria principal al solicitante. un Gestor de memoria intermedia se asemeja a un gestor de la memoria virtual de un sistema operativo. Sin embargo, el trabajo del gestor de la memoria intermedia es mas complejo, puesto que las direcciones de memoria no resultan suficientes para direccionar todos los bloques en la memoria intermedia, entonces es necesario utilizar técnicas más complejas que los esquemas de gestión de la memoria virtual habituales:

• Estrategia de sustitución. Cuando no queda espacio libre en la memoria intermedia hay que eliminar un bloque de ésta antes de que se pueda escribir en él otro nuevo. Generalmente los sistemas operativos utilizan un esquema menos recientemente utilizado (Least Recently Used, LRU), en el que se vuelve a escribir en el disco y se elimina de la memoria intermedia el bloque al que se ha hecho referencia menos recientemente.

• Bloques clavados. Para que el sistema de bases de datos pueda recuperarse de las caídas resulta necesario limitar las ocasiones en que se puede volver a escribir el bloque en el disco. Se dice que un bloque al que no se le permite que se vuelva a escribir en el disco está clavado. Aunque muchos sistemas operativos no permiten trabajar con bloques clavados, esta prestación resulta esencial para la implementación de un sistema de bases de datos resistente a las caídas.

• Salida forzada de los bloques. Hay situaciones en las que resulta necesario volver a escribir el bloque en el disco, aunque no se necesite el espacio de memoria intermedia que ocupa. Este proceso de escritura se denomina salida forzada del bloque.

Políticas para la sustitución

El objetivo de las estrategias de sustitución de los bloques de la memoria intermedia es la minimización de los accesos al disco. En los programas de propósito general no resulta posible predecir con precisión los bloques a los que se hará referencia. Por tanto, los sistemas operativos utilizan la pauta anterior de las referencias a los bloques como forma de predecir las referencias futuras. La suposición que suele hacerse es que es probable que se vuelva a hacer referencia a los bloques a los que se ha hecho referencia recientemente. Por tanto, si hay que sustituir un bloque, se sustituye el bloque al que se ha

hecho referencia menos recientemente. Este enfoque se denomina esquema de sustitución de bloques LRU.

LRU es un esquema de sustitución aceptable para los sistemas operativos. Sin embargo, los sistemas de bases de datos pueden predecir la pauta de las referencias futuras con más precisión que los sistemas operativos. Las peticiones del usuario al sistema de bases de datos comprenden varias etapas. El sistema de bases de datos suele poder determinar con antelación los bloques que se necesitarán examinando cada una de las etapas necesarias para llevar a cabo la operación solicitada por el usuario.

Por tanto, a diferencia de los sistemas operativos, que deben confiar en el pasado para predecir el futuro, los sistemas de bases de datos pueden tener información concerniente al menos al futuro a corto plazo.

Para ilustrar la manera en que la información relativa al futuro acceso a los bloques permite mejorar la estrategia LRU considérese el procesamiento de la expresión del álgebra relacional:

prestatario |x| cliente

Supóngase que la estrategia escogida para procesar esta solicitud viene dada por el programa en seudocódigo mostrado a continuación.

for each tupla p de prestatario do

for each tupla c de cliente do

if p[nombre-cliente] = c [nombre-cliente]

then begin

sea x una tupla definida de la manera siguiente:

x[nombre-cliente] := p [nombre-cliente]

x[número-préstamo] := p [número-préstamo]

x[calle-cliente ] := c [calle-cliente ]

x[ciudad-cliente ] := c [ciudad-cliente ]

incluir la tupla x como parte del resultado de prestatario |X| cliente

end

end

end

Supóngase que las dos relaciones de este ejemplo se guardan en archivos diferentes. En este ejemplo se puede ver que, una vez que se haya procesado la tupla de prestatario, no se vuelve a necesitar. Por tanto, una vez que se ha completado el procesamiento de un bloque completo de tuplas de prestatario, ese bloque ya no se necesita en la memoria principal, aunque se haya utilizado recientemente. Deben darse instrucciones al gestor de la memoria intermedia para liberar el espacio ocupado por el bloque de prestatario tan pronto como se haya procesado la última tupla. Esta estrategia de gestión de la memoria intermedia se denomina estrategia de extracción inmediata.

Considérense ahora los bloques que contienen las tuplas de cliente. Hay que examinar una vez cada bloque de las tuplas cliente por cada tupla de la relación prestatario. Cuando se completa el procesamiento del bloque cliente se sabe que no se tendrá nuevamente acceso a este hasta que se hayan procesado todos los demás bloques de cliente. Por tanto, el bloque de cliente al que se haya hecho referencia más recientemente será el último bloque al que se vuelva a referenciar, y el bloque de cliente al que se haya hecho referencia menos recientemente será el bloque al que se vuelva a hacer referencia a continuación. Este conjunto de suposiciones es el reverso exacto del que forma la base de la estrategia LRU. En realidad, la estrategia óptima para la sustitución de bloques es la estrategia más recientemente utilizada (Most Recently Used, MRU). Si hay que eliminar de la memoria intermedia un bloque de cliente, la estrategia MRU escoge el bloque utilizado más recientemente. Para que la estrategia MRU funcione correctamente en el ejemplo propuesto, el sistema debe clavar el bloque de cliente que se esté procesando. Después de que se haya procesado la última tupla de cliente el bloque se desclava y se transforma en el bloque utilizado más recientemente.

Además de utilizar la información que pueda tener el sistema respecto de la solicitud que se esté procesando, el gestor de la memoria intermedia puede utilizar información estadística concerniente a la probabilidad de que una solicitud haga referencia a una relación concreta. Por ejemplo, el diccionario de datos que guarda el esquema lógico de las relaciones y su información del almacenamiento físico es una de las partes de la base de datos a la que se tiene acceso con mayor frecuencia. Por tanto, el gestor de la memoria intermedia debe intentar no eliminar de la memoria principal los bloques del diccionario de datos a menos que se vea obligado a hacerlo por otros factores.

La estrategia ideal para la sustitución de bloques necesita información sobre las operaciones de la bases de datos (las que se estén realizando y las que se realizarán en el futuro). No se conoce ninguna estrategia aislada que responda bien a todas las situaciones posibles.

En realidad, un número sorprendentemente grande de bases de datos utilizan LRU a pesar de los defectos de esa estrategia. Los ejercicios exploran estrategias alternativas.

La estrategia utilizada por el gestor de la memoria intermedia para la sustitución de los bloques se ve influida por factores distintos del momento en que se volverá a hacer referencia al bloque. Si el sistema está procesando de manera concurrente las solicitudes de varios usuarios, puede que el subsistema para el control de la concurrencia tenga que posponer ciertas solicitudes para asegurar la conservación de la consistencia de la base de datos. Si se proporciona al gestor de la memoria intermedia información del subsistema

de control de la concurrencia que indique las solicitudes que se posponen, puede utilizar esta información para modificar su estrategia de sustitución de los bloques.

De manera específica, los bloques que necesiten las solicitudes activas (no pospuestas) pueden retenerse en la memoria intermedia a expensas de los bloques que necesiten las solicitudes pospuestas.

El subsistema para la recuperación de caídas impone restricciones estrictas a la sustitución de los bloques. Si se ha modificado un bloque, no se permite al gestor de la memoria intermedia volver a copiar la versión nueva del bloque de la memoria intermedia al disco, dado que eso destruiría la versión anterior.

Por el contrario, el gestor de bloques debe solicitar permiso del subsistema para la recuperación de averías antes de escribir los bloques. Puede que el subsistema para la recuperación de averías exija que se fuerce la salida de otros bloques antes de conceder autorización al gestor de la memoria intermedia para escribir el bloque solicitado.