Silberschatz 10a castellano cap14

Vista previa del material en texto

CAPÍTULO 14
Implementación de Sistemas de Archivos
Como vimos en el Capítulo 13, el sistema de archivos proporciona el mecanismo para almacenamiento y acceso al contenido de archivos, incluidos los datos y programas. Los sistemas de archivos generalmente residen permanentemente en un almacenamiento secundario, que está diseñado para almacenar una gran cantidad de datos. Este capítulo se ocupa principalmente de cuestiones que tienen que ver con el almacenamiento de archivos y el acceso al almacenamiento secundario más común, unidades de disco duro y dispositivos de memoria no volátiles. Exploramos formas para estructurar el uso de archivos, para asignar espacio de almacenamiento, para recuperar espacio liberado, para rastrear las ubicaciones de los datos, y para conectar otras partes del sistema operativo para almacenamiento secundario. Los problemas de rendimiento se consideran a lo largo del capítulo.
Un sistema operativo de propósito general determinado proporciona varios sistemas de archivos. Además, muchos sistemas operativos permiten a los administradores o usuarios agregar sistemas de archivos. ¿Por qué tantos? Los sistemas de archivos varían en muchos aspectos, incluidas las características, rendimiento, confiabilidad y objetivos de diseño, y diferentes sistemas de archivos pueden servir para diferentes propósitos. Por ejemplo, se utiliza un sistema de archivos temporal para un almacenamiento rápido y recuperación de archivos no persistentes, mientras que el sistema de archivos de almacenamiento secundario predeterminado (como Linux ext4) sacrifica el rendimiento por características de confiabilidad. Como hemos visto a lo largo de este estudio de sistemas operativos, hay muchas opciones y variaciones, lo que hace que la cobertura completa sea un desafío. En este capítulo, nos concentramos en los denominadores comunes.
OBJETIVOS DEL CAPÍTULO
• Describir los detalles de la implementación de estructuras de directorios y sistemas de archivos locales.
• Analizar los algoritmos de asignación de bloques y el manejo de bloques libres.
• Explorar los problemas de rendimiento y eficiencia de los sistemas de archivos.
• Observar la recuperación de fallas en el sistema de archivos.
• Describir el sistema de archivos WAFL como un ejemplo concreto.
14.1 Estructura del sistema de archivos
Los discos proporcionan la mayor parte del almacenamiento secundario en el que se mantienen los sistemas de archivos. Dos características que los hacen convenientes para este propósito:
1. Un disco se puede reescribir en el mismo lugar; es posible leer un bloque del disco, modificarlo y volver a escribirlo en el mismo bloque.
2. Un disco puede acceder directamente a cualquier bloque de información que contenga. Por lo tanto, es fácil de acceder a cualquier archivo de forma secuencial o aleatoria, y cambiando de un archivo a otro requiere que la unidad mueva los cabezales de lectura y escritura y esperando a que el medio gire.
Los dispositivos de memoria no volátil (NVM) se utilizan cada vez más para el almacenamiento de archivos y, por tanto, como ubicación para sistemas de archivos. Se diferencian de los discos duros en que no se pueden reescribir en su lugar y tienen diferentes características de desempeño. Discutimos la estructura del disco y del dispositivo NVM en detalle en el Capítulo 11.
Para mejorar la eficiencia de E/S, las transferencias de E/S entre la memoria y el almacenamiento masivo se realizan en unidades de bloques. Cada bloque de una unidad de disco duro tiene uno o más sectores. Según la unidad de disco, el tamaño del sector suele ser de 512 bytes o 4.096 bytes. Los dispositivos NVM suelen tener bloques de 4096 bytes y los métodos para la transferencia utilizados son similares a los utilizados por las unidades de disco.
Los sistemas de archivos brindan un acceso eficiente y conveniente al dispositivo de almacenamiento al permitir que los datos se almacenen, ubiquen y recuperen fácilmente. Un sistema de archivos plantea dos problemas de diseño bastante diferentes. El primer problema es definir cómo un usuario debe mirar al sistema de archivos. Esta tarea implica definir un archivo y sus atributos, las operaciones permitidas en un archivo y la estructura del directorio para organizar archivos. El segundo problema es la creación de algoritmos y estructuras de datos para mapear el sistema de archivos lógicos en los dispositivos físicos de almacenamiento secundario.
El sistema de archivos en sí mismo, se compone generalmente de muchos niveles diferentes. La estructura que se muestra en la Figura 14.1 es un ejemplo de un diseño en capas. Cada nivel en el diseño utiliza las características de los niveles inferiores para crear nuevas características para su uso en Niveles más altos.
Figura 14.1 Sistema de archivos en capas
El nivel de control de E/S consta de controladores de dispositivos (drivers) y controladores de interrupciones (interrupt handlers) para transferir información entre la memoria principal y el sistema de disco. Un controlador del dispositivo puede considerarse un traductor. Su entrada consta de comandos de alto nivel, como "recuperar bloque 123". Su salida consta de instrucciones específicas de hardware de bajo nivel, que utiliza la placa controladora de hardware, que conecta el dispositivo de E/S con el resto del sistema. El controlador del dispositivo (driver) generalmente escribe patrones de bits específicos en ubicaciones especiales en la memoria del controlador de E/S para indicarle a la placa controladora en qué ubicación del dispositivo actuar y qué acciones tomar. Los detalles de los controladores de dispositivos y la infraestructura de E/S se tratan en el capítulo 12.
El sistema de archivos básico (llamado "subsistema de E/S de bloque" en Linux) necesita solo emitir comandos genéricos al controlador de dispositivo apropiado para leer y escribir bloques en el dispositivo de almacenamiento. Emite comandos a la unidad basada en direcciones de bloques lógicos. También se ocupa de la planificación de solicitudes de E/S. Esta capa también administra los búferes de memoria y los cachés que contienen varios sistemas de archivos, directorio y bloques de datos. Un bloque en el búfer se asigna antes de que ocurra la transferencia de un bloque de almacenamiento masivo. Cuando el búfer está lleno, el administrador del búfer debe encontrar más memoria que funcione como búfer o liberar espacio de búfer para permitir que una solicitud de E/S sea completada. Los cachés se utilizan para almacenar los metadatos de uso frecuente del sistema de archivos para mejorar el rendimiento, por lo que la gestión de sus contenidos es fundamental para el rendimiento óptimo del sistema.
El módulo de organización de archivos conoce los archivos y sus bloques lógicos. Los bloques lógicos de cada archivo están numerados del 0 (o 1) al N. El módulo de organización del archivo también incluye el administrador de espacio libre, que rastrea los bloques y proporciona estos bloques al módulo de organización de archivos cuando son solicitados.
Finalmente, el sistema lógico de archivos gestiona la información de metadatos. Los Metadatos incluyen toda la estructura del sistema de archivos excepto los datos reales (o el contenido de los archivos). El sistema lógico de archivos administra la estructura de directorios para proporcionar al módulo de organización de archivos la información que este último necesita, dado un nombre de archivo simbólico. Mantiene la estructura de archivos a través de bloques de control de archivos. Un bloque de control de archivo (FCB) (un inodo en los sistemas de archivos UNIX) contiene información sobre el archivo, incluida el propietario, los permisos y la ubicación del contenido del archivo. El sistema lógico de archivos también es responsable de la protección, como se explica en los Capítulos 13 y 17.
Cuando se utiliza una estructura en capas para la implementación del sistema de archivos, la duplicación de código se minimiza. El control de E/S y, a veces, el código del sistema básico de archivospuede ser utilizado por varios sistemas de archivos. Cada sistema de archivos puede tener su propio sistema de archivos lógico y módulos de organización de archivos. Desafortunadamente, las capas pueden introducir más sobrecarga al sistema operativo, lo que puede resultar en una disminución del rendimiento. El uso de capas, incluida la decisión sobre cuántas capas usar y lo que debe hacer cada capa, es un gran desafío en el diseño de nuevos sistemas.
Actualmente se utilizan muchos sistemas de archivos y la mayoría de los sistemas operativos admiten más de uno. Por ejemplo, la mayoría de los CD-ROM están escritos en formato ISO 9660, un formato estándar acordado por los fabricantes de CD-ROM. Además de los sistemas de archivos de medios extraíbles, cada sistema operativo tiene uno o más sistemas de archivos. UNIX utiliza el sistema de archivos UNIX (UFS), que se basa en Berkeley Fast File System (FFS). Windows admite formatos de sistema de archivos de disco FAT, FAT32 y NTFS (o sistema de archivos de Windows NT), así como formatos de sistemas de archivos CD-ROM y DVD. Aunque Linux admite más de 130 sistemas de archivos diferentes, el sistema de archivos estándar de Linux se conoce como el sistema de archivos extendido, con las versiones más comunes son ext3 y ext4. También hay sistemas de archivos distribuidos en los que un sistema de archivos de un servidor es montado por uno o más clientes computadoras a través de una red.
La investigación del sistema de archivos sigue siendo un área activa del diseño e implementación de un sistema operativo. Google creó su propio sistema de archivos para cumplir las necesidades específicas de almacenamiento y recuperación de la empresa, que incluyen un acceso de alto rendimiento desde muchos clientes con el uso de una gran cantidad de discos. Otro proyecto interesante es el sistema de archivos FUSE, que proporciona flexibilidad en desarrollo y uso de sistemas de archivos mediante la implementación y ejecución de código de sistemas de archivos a nivel de usuario en lugar de a nivel de kernel. Usando FUSE, un usuario puede agregar un nuevo sistema de archivos a una variedad de sistemas operativos y puede usar ese sistema de archivos para administrar sus archivos.
14.2 Operaciones del sistema de archivos
Como se describió en la Sección 13.1.2, los sistemas operativos implementan llamadas al sistema open() y close() que requieren los procesos que soliciten acceso al contenido de un archivo. En esta sección, profundizamos en las estructuras y operaciones utilizadas para implementar las operaciones de sistema de archivos.
14.2.1 Antecedentes
Se utilizan varias estructuras en almacenamiento y en memoria para implementar un sistema de archivos. Estas estructuras varían según el sistema operativo y el sistema de archivos, pero se aplican algunos principios generales.
En el almacenamiento, el sistema de archivos puede contener información sobre cómo iniciar un sistema operativo almacenado allí, el número total de bloques, el número y ubicación de bloques libres, estructura de directorios y archivos individuales. Muchos de estas estructuras se detallan en el resto de este capítulo. Aquí, los describimos brevemente:
• El bloque de control de arranque (boot control block) (por volumen) puede contener información que necesita el sistema para iniciar un sistema operativo desde ese volumen. Si el disco no contiene un sistema operativo, este bloque puede estar vacío. Normalmente es el primer bloque de un volumen. En UFS, se denomina bloque de arranque. En NTFS, es el sector de arranque de partición.
• El bloque de control de volumen (por volumen) o superblock contiene detalles de volumen, como el número de bloques en el volumen, el tamaño de los bloques, un contador de bloques libres y punteros a bloques libres, y un contador de FCBs libres y punteros a los FCBs. En UFS, esto se llama superblock. En NTFS, se almacena en la tabla de archivos Maestra.
• Se utiliza una estructura de directorio (por sistema de archivos) para organizar los archivos. En UFS, esto incluye nombres de archivo y números de inodo asociados. En NTFS, se almacena en la tabla de archivo maestro.
• Un FCB por archivo contiene muchos detalles sobre el archivo. Tiene un número identificador único para permitir la asociación con una entrada de directorio. En NTFS, esta información en realidad se almacena dentro de la tabla de archivos maestra, que utiliza una estructura relacional de la base de datos, con una fila por archivo.
La información en memoria se utiliza tanto para la administración del sistema de archivos como para mejora del rendimiento mediante el almacenamiento en caché. Los datos se cargan en el momento del montaje, actualizándolos durante las operaciones del sistema de archivos y descartándolos al desmontar. Se pueden incluir algunos tipos de estructuras.
• Una tabla de montaje en memoria contiene información sobre cada volumen montado.
• Una caché de la estructura de directorios en memoria contiene la información del directorio de los directorios accedidos recientemente. (Para los directorios montados, puede contener un puntero a la tabla de volumen).
• La tabla de archivos abiertos en todo el sistema contiene una copia del FCB de cada archivo, así como otra información.
• La tabla de archivos abiertos por proceso contiene punteros a las entradas apropiadas en la tabla de archivos abiertos de todo el sistema, así como otra información, para todos los archivos abiertos por el proceso.
• Los búferes contienen bloques del sistema de archivos cuando se leen o escriben en un sistema de archivos.
Para crear un nuevo archivo, un proceso llama al sistema lógico de archivos. El sistema lógico de archivos conoce el formato de las estructuras de directorio. Para crear un nuevo archivo, asigna un nuevo FCB. (Alternativamente, si la implementación del sistema de archivos crea todos los FCB – como una tabla- en el momento de la creación del sistema de archivos, se asigna un FCB del conjunto de FCB.) El sistema lee el directorio apropiado en la memoria, actualiza el nuevo FCB con su nombre de archivo, y lo vuelve a escribir en el sistema de archivos. Un FCB se muestra en la Figura 14.2.
Algunos sistemas operativos, incluido UNIX, tratan un directorio exactamente igual como un archivo: uno con un campo de "tipo" que indica que es un directorio. Otros sistemas operativos, incluido Windows, implementan llamadas al sistema separadas para archivos y directorios y tratan los directorios como entidades separadas de los archivos. Lo que sea para cuestiones estructurales más grandes, el sistema lógico de archivos puede llamar al módulo de organización de archivos para mapear las E/S de directorio en ubicaciones de bloques de almacenamiento, que se pasan en el sistema de archivos básico y el sistema de control de E/S.
Figura 14.2 Un bloque de control de archivos típico.
14.2.2 Uso
Ahora que se ha creado un archivo, se puede utilizar para las E/S. Primero, sin embargo, debe ser abierto. La llamada open () pasa un nombre de archivo al sistema lógico de archivos. La llamada al sistema open () busca primero en la tabla de archivos abiertos de todo el sistema para ver si el archivo ya está siendo utilizado por otro proceso. Si es así, se crea una entrada en la tabla de archivos abiertos por proceso y un puntero a la tabla de archivos abiertos de todo el sistema existente. Este algoritmo puede ahorrar gastos generales sustanciales. Si el archivo aún no está abierto, se busca el nombre de archivo dado en la estructura del directorio. Algunas partes de la estructura del directorio suelen ser almacenadas en la memoria caché para acelerar las operaciones de directorio. Una vez que se encuentra el archivo, su FCB se copia en una tabla de archivos abiertos de todo el sistema en la memoria. Esta tabla no solo almacena el FCB, sino que lleva cuenta del número de procesos que tienen el archivo abierto.
A continuación, se realiza una entrada en la tabla de archivos abiertos por proceso, con un puntero a la entrada en la tabla de archivosabiertos de todo el sistema y algunos otros campos. Estos otros campos pueden incluir un puntero a la ubicación actual en el archivo (para la próxima operación de lectura () o escritura ()) y el modo de acceso en el que se abre el archivo. La llamada open () devuelve un puntero a la entrada de la tabla de archivos abiertos por proceso del sistema de archivos. Todas las operaciones de archivo se realizan a través de este puntero. El nombre del archivo puede no ser parte de la tabla de archivos abiertos, ya que el sistema lo utiliza una sola vez, hasta que el FCB apropiado está ubicado en el disco. Sin embargo, podría almacenarse en caché para ahorrar tiempo en las siguientes aperturas del mismo archivo. El nombre dado a la entrada varía. Los sistemas UNIX se refieren a él como descriptor de archivos; Windows se refiere a él como manejador de archivo.
Cuando un proceso cierra el archivo, la entrada de la tabla por proceso se elimina y el contador de aperturas se reduce en la entrada de la tabla de archivos abiertos en el sistema. Cuando todos los procesos de usuario que abrieron el archivo, lo cierran, los metadatos actualizados se copian de nuevo en la estructura de directorio del disco y se elimina la entrada de la tabla de archivos abiertos de todo el sistema.
Los aspectos de almacenamiento en caché de las estructuras del sistema de archivos no deben pasarse por alto. La mayoría de los sistemas mantienen toda la información sobre un archivo abierto, excepto los bloques de datos reales, en la memoria. El sistema BSD UNIX es típico en el uso de cachés en cualquier lugar de las E/S del disco que se pueden guardar. Su tasa de aciertos de caché promedio del 85 por ciento, muestra que esta técnica vale la pena implementar. Se describe el sistema BSD UNIX completamente en el Apéndice C.
Se resumen las estructuras operativas de una implementación de sistema de archivos en la Figura 14.3.
14.3 Implementación del directorio
La selección de algoritmos de asignación y gestión de directorios afecta significativamente la eficiencia, el rendimiento y la confiabilidad del sistema de archivos. En esta sección, discutimos las compensaciones involucradas en elegir uno de estos algoritmos.
Figura 14.3 Estructuras del sistema de archivos en memoria. (a) Archivo abierto. (b) Archivo leído
14.3.1 Lista lineal
El método más simple de implementar un directorio es usar una lista lineal de nombres de archivos con punteros a los bloques de datos. Este método es sencillo de programar, pero lleva mucho tiempo ejecutarlo. Para crear un nuevo archivo, primero debemos buscar en el directorio para asegurarnos de que ningún archivo existente tenga el mismo nombre. Luego, agregamos una nueva entrada al final del directorio. Para eliminar un archivo, buscamos en el directorio el archivo con ese nombre y luego liberamos el espacio asignado. Para reutilizar la entrada de directorio, podemos hacer una de varias cosas. Podemos marcar la entrada como no utilizada (por ejemplo, asignándole un nombre especial, como un nombre en blanco, asignándole un número de i-nodo no válido (como 0), o incluyendo un bit usado/no usado en cada entrada), o podemos adjuntarlo a una lista de entradas de directorio libres. Una tercera alternativa es copiar la última entrada en el directorio en la ubicación liberada y para disminuir la longitud del directorio. También se puede utilizar una lista enlazada para reducir el tiempo necesario para eliminar un archivo.
La verdadera desventaja de una lista lineal de entradas de directorio es que para encontrar un archivo requiere una búsqueda lineal. La información del directorio se utiliza con frecuencia y los usuarios notará si el acceso es lento. De hecho, muchos sistemas operativos implementan una caché de software para almacenar la información de directorio utilizada más recientemente. Un acierto de caché evita la necesidad de volver a leer constantemente la información de un almacenamiento secundario. Una lista ordenada permite una búsqueda binaria y disminuye el tiempo promedio de búsqueda. Sin embargo, el requisito de que la lista se mantenga ordenada puede complicar la creación y eliminación de archivos, ya que es posible que tengamos que mover cantidades sustanciales de información de directorio para mantener un directorio ordenado. Una estructura de datos más sofisticada como un Árbol balanceado, podría ayudar aquí. Una ventaja de la lista ordenada es que se puede listar un directorio ordenado sin que se obtenga un directorio ordenado por separado.
14.3.2 Tabla hash
Otra estructura de datos utilizada para un directorio de archivos es una tabla hash. Aquí, una lista lineal almacena las entradas del directorio, pero también se utiliza una estructura de datos hash. La tabla hash toma un valor calculado a partir del nombre del archivo y devuelve un puntero al nombre del archivo en la lista lineal. Por lo tanto, puede reducir considerablemente el tiempo de búsqueda del directorio. La inserción y eliminación también son bastante sencillas, aunque algunas disposiciones deben realizarse para colisiones: situaciones en las que dos nombres de archivo dan la misma ubicación.
Las mayores dificultades con una tabla hash son su tamaño generalmente fijo y la dependencia de la función hash en ese tamaño. Por ejemplo, supongamos que haga una tabla hash de sondeo lineal que contenga 64 entradas. La función hash convierte nombres de archivo en números enteros de 0 a 63 (por ejemplo, utilizando el resto de una división por 64). Si más tarde intentamos crear un archivo número 65, debemos ampliar el directorio tabla hash, digamos, a 128 entradas. Como resultado, necesitamos una nueva función hash. que debe asignar nombres de archivo en el rango de 0 a 127, y debemos reorganizar las entradas de directorio existentes para reflejar sus nuevos valores de función hash.
Alternativamente, podemos usar una tabla hash de desbordamiento encadenado. Cada entrada hash puede ser una lista enlazada en lugar de un valor individual, y podemos resolver colisiones agregando la nueva entrada a la lista enlazada. Las búsquedas pueden ralentizarse un poco, porque la búsqueda de un nombre puede requerir recorrer una lista enlazada de entradas de la tabla en colisión. Aún, así es probable que este método sea mucho más rápido que una búsqueda lineal en todo el directorio.
14.4 Métodos de asignación
La naturaleza de acceso directo del almacenamiento secundario nos da flexibilidad en la implementación de archivos. En casi todos los casos, muchos archivos se almacenan en el mismo dispositivo. El principal problema es cómo asignar espacio a estos archivos para que el almacenamiento el espacio se utiliza de forma eficaz y se puede acceder a los archivos rápidamente. Tres métodos principales de asignación de espacio de almacenamiento secundario se utilizan ampliamente: contiguo, enlazado, e indexado. Cada método tiene ventajas y desventajas, aunque algunos de los sistemas admiten los tres, es más común que un sistema utilice un método para todos los archivos dentro de un tipo de sistema de archivos.
14.4.1 Asignación contigua
La asignación contigua requiere que cada archivo ocupe un conjunto de bloques contiguos en el dispositivo. Las direcciones en los dispositivos definen un orden lineal en el dispositivo. Con este orden, se asume que sólo un trabajo está accediendo al dispositivo, accediendo al bloque b + 1 después del bloque b normalmente no requiere movimiento de cabeza. Cuando el movimiento de la cabeza es necesario (desde el último sector de un cilindro hasta el primer sector del siguiente cilindro), la cabeza solo necesita moverse de una pista a la siguiente. Por lo tanto, para discos duros, el número de búsquedas de disco necesarias para acceder a archivos asignados de forma contigua es mínimo (asumiendo que los bloques con direcciones lógicas cercanas están cerca físicamente), como es el tiempo de búsqueda cuando finalmente se hace una búsqueda.
La asignación contigua de un archivo se define por la dirección del primer bloque y longitud (en unidadesde bloque) del archivo. Si el archivo tiene n bloques de longitud y comienza en ubicación b, luego ocupa los bloques b, b + 1, b + 2, ..., b + n - 1. La entrada del directorio para cada archivo indica la dirección del bloque de inicio y la longitud del área asignada para este archivo (Figura 14.4). La asignación contigua es fácil de implementar, pero tiene limitaciones y, por lo tanto, no se utiliza en los sistemas de archivos modernos.
Acceder a un archivo que se ha asignado de forma contigua es fácil. Para acceso secuencial, el sistema de archivos recuerda la dirección del último bloque referenciado y, cuando sea necesario, lee el siguiente bloque. Para acceder en forma directa al bloque i de un archivo que comienza en el bloque b, podemos acceder inmediatamente al bloque b + i. Por tanto, tanto el acceso secuencial como el directo puede apoyarse mediante la asignación contigua.
Figura 14.4 Asignación contigua de espacio en disco.
Sin embargo, la asignación contigua tiene algunos problemas. Una dificultad es encontrar espacio para un nuevo archivo. El sistema elegido para gestionar el espacio libre determina cómo se realiza esta tarea; estos sistemas de gestión se analizan en Sección 14.5. Se puede utilizar cualquier sistema de gestión, pero algunos son más lentos que otros.
El problema de la asignación contigua puede verse como un caso particular del problema general de asignación dinámica de almacenamiento discutido en la Sección 9.2, que implica cómo satisfacer una solicitud de tamaño n de una lista de huecos libres. El primer ajuste (first fit) y el mejor ajuste (best fit) son las estrategias más comunes que se utilizan para seleccionar un hueco libre del conjunto de huecos disponibles. Las simulaciones han demostrado que tanto el primer ajuste como el mejor ajuste son más eficientes que los de peor ajuste en términos de uso de tiempo y almacenamiento. Ni el primer ajuste ni el mejor ajuste son claramente mejores en términos de utilización del almacenamiento, pero el primero ajuste es generalmente más rápido.
Todos estos algoritmos sufren del problema de la fragmentación externa. Como los archivos se asignan y eliminan, el espacio de almacenamiento libre se divide en pequeños pedazos. La fragmentación externa existe siempre que el espacio libre se divide en trozos. Eso se convierte en un problema cuando la porción contigua más grande es insuficiente para una solicitud; el almacenamiento está fragmentado en varios huecos, ninguno de los cuales es suficientemente grande para almacenar los datos. Dependiendo de la cantidad total de almacenamiento en disco y del tamaño de archivo en promedio, la fragmentación externa puede ser un problema menor o mayor.
Una estrategia para evitar la pérdida de cantidades significativas de espacio de almacenamiento con la fragmentación externa consiste en copiar un sistema de archivos completo en otro dispositivo. Luego, el dispositivo original se libera por completo, creando un gran espacio contiguo libre. Luego copiamos los archivos de nuevo en el dispositivo original asignando espacio contiguo de este gran hueco. Este esquema compacta todo el espacio libre en un espacio contiguo, resolviendo el problema de la fragmentación. Sin embargo, el costo de esta compactación es tiempo y el costo puede ser particularmente alto para dispositivos de almacenamiento grandes. Compactar estos dispositivos puede llevar horas y puede ser necesario semanalmente. Algunos sistemas requieren que esta función se realice fuera de línea, con el sistema de archivos desmontado. Durante este tiempo de inactividad, generalmente no se puede permitir el funcionamiento normal del sistema, por lo que dicha compactación es evitada a toda costa en las máquinas de producción. La mayoría de los sistemas modernos que necesitan de la desfragmentación pueden realizarla en línea durante las operaciones normales del sistema, pero la penalización de rendimiento puede ser sustancial.
Otro problema con la asignación contigua es determinar cuánto espacio se necesita para un archivo. Cuando se crea el archivo, la cantidad total de espacio será necesario encontrarle y asignarle. ¿El creador (programa o persona) conoce el tamaño del archivo que se va a crear? En algunos casos, esta determinación puede ser bastante simple (copiar un archivo existente, por ejemplo). En general, sin embargo, el tamaño de un archivo de salida puede ser difícil de estimar. 
Si asignamos muy poco espacio a un archivo, podemos encontrar que el archivo no podría crecer. Especialmente con una estrategia de asignación más adecuada, el espacio, en ambos lados del archivo pueden estar en uso. Por lo tanto, no podemos agrandar el archivo en su lugar. Entonces existen dos posibilidades. Primero, el programa de usuario puede terminar, con un mensaje de error apropiado. El usuario debe asignar más espacio y ejecutar el programa nuevamente. Estas ejecuciones repetidas pueden resultar costosas. Para prevenir esta situación, el usuario normalmente sobreestimará la cantidad de espacio necesario, lo que resultará en considerable espacio desperdiciado. La otra posibilidad es encontrar un hueco más grande, copiar el contenido del archivo al nuevo espacio y liberar el espacio anterior. Esta serie de acciones puede repetirse mientras exista espacio, aunque puede ser pérdida de tiempo. El usuario nunca necesita ser informado explícitamente sobre lo que está sucediendo, sin embargo; el sistema continúa a pesar del problema, aunque más y más lentamente.
Incluso si se conoce de antemano la cantidad total de espacio necesario para un archivo, la preasignación puede ser ineficaz. Un archivo que crezca lentamente durante un largo período (meses o años) debe tener suficiente espacio para su tamaño final, aunque gran parte de ese espacio no se use durante mucho tiempo. Por tanto, el archivo tiene una gran cantidad de fragmentación interna.
Para minimizar estos inconvenientes, un sistema operativo puede utilizar un esquema de asignación contigua modificada. Aquí, se asigna una porción contigua de espacio inicialmente. Entonces, si esa cantidad resulta no ser lo suficientemente grande, otra porción se agrega al espacio contiguo, conocido como extensión. La ubicación de los bloques de un archivo luego se registra como una ubicación y un contador de bloques, más un enlace al primer bloque de la siguiente extensión. En algunos sistemas, el propietario del archivo puede establecer el tamaño de la extensión, pero esta configuración da como resultado ineficiencias si la estimación del propietario es incorrecta. La fragmentación interna aún puede ser un problema si las extensiones son demasiado grandes y la fragmentación externa puede convertirse en un problema ya que se asignan y desasignan extensiones de diferentes tamaños. El sistema de archivos comercial de Symantec Veritas utiliza extensiones para optimizar el rendimiento. Veritas es un reemplazo de alto rendimiento para estándar UNIX UFS.
14.4.2 Asignación enlazada
La asignación enlazada resuelve todos los problemas de asignación contigua. Con asignación enlazada, cada archivo es una lista enlazada de bloques de almacenamiento; los bloques pueden estar esparcidos en cualquier lugar del dispositivo. El directorio contiene un puntero al primer y al último bloque del archivo. Por ejemplo, un archivo de cinco bloques puede comenzar en el bloque 9 y continúe en el bloque 16, luego en el bloque 1, luego en el bloque 10 y finalmente en el bloque 25 (Figura 14,5). Cada bloque contiene un puntero al siguiente bloque. Estos indicadores no son puestos a disposición del usuario. Por lo tanto, si cada bloque tiene un tamaño de 512 bytes y la dirección de un bloque (el puntero) requiere 4 bytes, luego el usuario ve bloques de 508 bytes.
Para crear un nuevo archivo, simplemente creamos una nueva entrada en el directorio. Con asignación enlazada, cada entrada de directorio tiene un puntero al primer bloque de archivos. Este puntero se inicializa a nulo (el valor del puntero al final de la lista) para significar un archivovacío. El campo de tamaño también se establece en 0. Una escritura en el archivo hace que el sistema de gestión de espacio libre encuentre un bloque libre, y este nuevo bloque escrito se enlace con un fin del archivo. Para leer un archivo, simplemente leemos bloques siguiendo los punteros de un bloque a otro. No hay fragmentación externa con asignación enlazada, y cualquier bloque libre en la lista de espacio libre se puede utilizar para satisfacer una solicitud. No es necesario declarar el tamaño de un archivo cuando se crea el archivo. Un archivo puede seguir creciendo mientras haya bloques libres disponibles. Por consiguiente, nunca es necesario compactar el espacio del disco.
Sin embargo, la asignación enlazada tiene desventajas. El mayor problema es que sólo se puede utilizar de forma eficaz para archivos de acceso secuencial. Para encontrar el i-ésimo bloque de un archivo, debemos comenzar por el principio de ese archivo y seguir los punteros hasta llegar al bloque i. Cada acceso a un puntero requiere una lectura de un dispositivo de almacenamiento, y todo el tiempo que ello implica. En consecuencia, es ineficaz lograr un acceso directo para archivos de asignación enlazados.
Otra desventaja es el espacio requerido para los punteros. Si un puntero requiere 4 bytes de un bloque de 512 bytes, entonces el 0,78 por ciento del disco se utiliza para punteros, en lugar de para información. Cada archivo requiere un poco más espacio de lo que sería de otra manera.
Figura 14.5 Asignación enlazada de espacio en disco.
La solución habitual a este problema es reunir bloques en múltiplos, llamados clústeres y asignar clústeres en lugar de bloques. Por ejemplo, el sistema de archivos puede definir un clúster como cuatro bloques y operar en el almacenamiento secundario dispositivo solo en unidades de clúster. Luego, los punteros usan un porcentaje mucho menor del espacio del archivo. Este método permite que la asignación de bloques lógicos a físicos siga siendo simple, pero mejore el rendimiento del disco duro (porque menos movimientos de cabezal de disco son necesarios) y reduce el espacio necesario para la asignación de bloques y la administración de la lista de huecos libres. El costo de este enfoque es un aumento en la fragmentación interna, porque se desperdicia más espacio cuando un clúster está parcialmente lleno que cuando un bloque está parcialmente lleno. También el rendimiento de una E/S aleatoria sufre, debido a una solicitud de una pequeña cantidad de datos, transfieriendo una gran cantidad de datos. Se pueden usar clústeres para mejorar el tiempo de acceso al disco para muchos otros algoritmos también, por lo que son utilizados en la mayoría de los sistemas de archivos.
Otro problema más de la asignación enlazada es la confiabilidad. Recuerde que los archivos están enlazados por punteros esparcidos por todo el dispositivo, y considere qué sucedería si un puntero se perdiera o se dañara. El error (bug) en el sistema operativo por una falla del software o del hardware puede resultar en una lectura de puntero incorrecto. Este error, a su vez, podría resultar en un enlace a la lista de espacio libre o a otro archivo. Una solución parcial es utilizar listas doblemente enlazadas y otra es almacenar el nombre del archivo y el número de bloque relativo en cada bloque. Sin embargo, estos esquemas requieren aún más gastos generales para cada archivo.
Una variación importante en la asignación enlazada es el uso de una tabla de asignación de archivo (FAT). Se utilizó este método simple pero eficiente de asignación de espacio en disco por el sistema operativo MS-DOS. Una sección de almacenamiento al comienzo de cada volumen se reserva para contener la tabla. La tabla tiene una entrada para cada bloque del disco lógico (unidad o partición) y está indexada por número de bloque. La FAT se usa de la misma manera que una lista enlazada. La entrada del directorio contiene el número de bloque del primer bloque del archivo. La entrada de la tabla indexada por ese número de bloque contiene el número de bloque del siguiente bloque del archivo. Esta cadena continúa hasta que llega al último bloque, que tiene una entrada de la tabla con un valor especial de fin de archivo. Un bloque sin usar se indica con un valor 0 en la tabla. Asignar un nuevo bloque a un archivo es una simple cuestión de encontrar la primera entrada de la tabla con valor 0 y reemplazar el valor de fin de archivo con la dirección del nuevo bloque. Luego, el 0 se reemplaza con el valor de fin de archivo. Un ejemplo ilustrativo es la estructura FAT que se muestra en la Figura 14.6 para un archivo que consta de bloques de disco 217, 618 y 339.
El esquema de asignación FAT puede resultar en un número significativo de movimientos de cabezales del disco, a menos que la FAT esté en caché. La cabeza del disco debe moverse al inicio del volumen para leer la FAT y encontrar la ubicación del bloque en cuestión, luego moverse a la ubicación del bloque en sí. En el peor de los casos, ambos movimientos ocurren para cada uno de los bloques. Un beneficio es que se mejora el tiempo de acceso aleatorio, porque el cabezal del disco puede encontrar la ubicación de cualquier bloque leyendo la información en la FAT
Figura 14.6 Tabla de asignación de archivos.
14.4.3 Asignación indexada
La asignación enlazada resuelve los problemas de fragmentación externa y la declaración de tamaño inicial en la asignación contigua. Sin embargo, en ausencia de una FAT, la asignación enlazada no puede soportar un acceso directo eficiente, ya que los punteros a los bloques están esparcidos con los bloques mismos por todo el disco y deben recuperarse en orden. La asignación indexada resuelve este problema al traer todos los punteros juntos en una ubicación: en un bloque índice.
Cada archivo tiene su propio bloque índice, que es una matriz de direcciones de bloques de almacenamiento. La entrada i en el bloque índice apunta al bloque i del archivo. El directorio contiene la dirección del bloque índice (Figura 14.7). Para encontrar y leer el bloque i, usamos el puntero en la entrada del bloque índice i. Este esquema es similar al esquema de paginación descrito en la Sección 9.3.
Cuando se crea el archivo, todos los punteros del bloque índice se establecen en nulos. Cuando se escribe por primera vez el bloque i, se obtiene un bloque del administrador de espacio libre, y su dirección se coloca en la i-ésima entrada del bloque de índice.
La asignación indexada admite el acceso directo, sin sufrir problemas de fragmentación externa, porque cualquier bloque libre en el dispositivo de almacenamiento puede satisfacer una solicitud de más espacio. La asignación indexada sufre de espacio desperdiciado. La sobrecarga del puntero del bloque índice es generalmente mayor que la sobrecarga del puntero de la asignación enlazada. Considere un caso común en el que tener un archivo de solo uno o dos bloques, con asignación enlazada, perdemos el espacio de un solo puntero por bloque. Con asignación indexada, un bloque índice completo debe asignarse, incluso si solo uno o dos punteros no serán nulos.
Figura 14.7 Asignación indexada de espacio en disco.
Este punto plantea la cuestión de cuán grande debería ser el bloque índice. Cada archivo debe tener un bloque índice, por lo que queremos que el bloque índice sea tan pequeño como sea posible. Sin embargo, si el bloque índice es demasiado pequeño, no podrá sostener suficientes punteros para un archivo grande, y tendrá que estar disponible un mecanismo para lidiar con este problema. Los mecanismos para este propósito incluyen los siguientes:
• Esquema enlazada. Un bloque de índice es normalmente un bloque de almacenamiento. Por lo tanto, puede ser leído y escrito directamente por sí mismo. Para permitir archivos grandes, podemos enlazar juntos varios bloques de índice. Por ejemplo, un bloque índice puede contener un pequeño encabezado que da el nombre del archivo y un conjunto de las primeras 100 direcciones de bloques de disco. La siguiente dirección (la últimapalabra en el bloque índice) es nula (para un archivo pequeño) o es un puntero a otro bloque de índice (para un archivo grande).
• Índice multinivel. Otra variante utiliza un bloque índice de primer nivel para apuntar a un conjunto de bloques índice de segundo nivel, que a su vez apuntan a los bloques de archivos. Para acceder a un bloque, el sistema operativo utiliza el índice de primer nivel para encontrar un bloque índice de segundo nivel y luego usa ese bloque para encontrar el bloque de datos deseado. Este enfoque podría continuarse hasta un tercero o cuarto nivel, dependiendo del tamaño de archivo máximo deseado. Con bloques de 4096 bytes, podríamos almacenar 1.024 punteros de cuatro bytes en un bloque índice. Dos niveles de índices permiten 1.048.576 bloques de datos y un tamaño de archivo de hasta 4 GB.
Figura 14.8 El inodo UNIX.
• Esquema combinado. Otra alternativa, utilizada en sistemas de archivos basados ​​en UNIX, es mantener los primeros, digamos, 15 punteros del bloque índice en el inodo del archivo. Los primeros 12 de estos punteros apuntan a bloques directos; es decir, contienen direcciones de bloques que contienen datos del archivo. Así, los datos para pequeños archivos (de no más de 12 bloques) no necesitan un bloque índice separado. Si el tamaño del bloque es de 4 KB, luego se puede acceder directamente a hasta 48 KB de datos. Los siguientes tres punteros apuntan a bloques indirectos. El primero apunta a un solo bloque indirecto, que es un bloque índice que no contiene datos sino las direcciones de bloques que contienen datos. El segundo apunta a un bloque de doble indirección, que contiene la dirección de un bloque que contiene las direcciones de bloques que contienen punteros a los bloques de datos reales. El último puntero contiene el Dirección de un bloque de triple indirección. (El inodo de UNIX se muestra en la Figura 14.8.) 
Bajo este método, el número de bloques que se pueden asignar a un archivo excede la cantidad de espacio direccionable por los punteros de archivo de 4 bytes utilizados por muchos sistemas operativos. Un puntero de archivo de 32 bits alcanza solo 232 bytes, o 4 GB. Muchas implementaciones de UNIX y Linux ahora admiten punteros de archivos de 64 bits, que permite que los archivos y sistemas de archivos tengan un tamaño de varios exabytes. El sistema de archivos ZFS admite punteros a archivos de 128 bits.
Los esquemas de asignación indexada tienen los mismos problemas que la asignación enlazada. Específicamente, los bloques índices se pueden almacenar en caché en la memoria, pero los bloques de datos pueden estar repartidos por todo un volumen.
14.4.4 Rendimiento
Los métodos de asignación que hemos discutido varían en su eficiencia de almacenamiento. y tiempos de acceso al bloque de datos. Ambos son criterios importantes para seleccionar el método/métodos para que un sistema operativo lo implemente.
Antes de seleccionar un método de asignación, necesitamos determinar cómo se utilizarán en los sistemas. Un sistema con acceso mayoritariamente secuencial no debe utilizar el mismo método que un sistema con acceso mayoritariamente aleatorio.
Para cualquier tipo de acceso, la asignación contigua requiere solo un acceso para conseguir un bloque. Dado que podemos mantener fácilmente la dirección inicial del archivo en la memoria, podemos calcular inmediatamente la dirección del bloque i (o el bloque siguiente) y leerlo directamente.
Para la asignación enlazada, también podemos mantener la dirección del siguiente bloque en memoria y leerlo directamente. Este método está bien para el acceso secuencial; sin embargo, para el acceso directo, un acceso al bloque i puede requerir lecturas del bloque i. Este problema indica por qué la asignación enlazada no se debe utilizar para una aplicación cuando se requiere acceso directo.
Como resultado, algunos sistemas admiten archivos de acceso directo mediante el uso de archivos contiguos y archivos de asignación y acceso secuencial con asignación enlazada. Para estos sistemas, el tipo de acceso usual a realizar debe declararse cuando se crea el archivo. Un archivo creado para el acceso secuencial se enlazará y no se puede utilizar para acceso para acceso directo. Un archivo creado para acceso directo será contiguo y puede admitir tanto acceso directo como acceso secuencial, pero se debe declarar su longitud máxima cuando se crea. En este caso, el sistema operativo debe tener las estructuras de datos y algoritmos para admitir ambos métodos de asignación. Los archivos pueden ser convertidos de un tipo a otro mediante la creación de un nuevo tipo de archivo deseado, en el que se copia el contenido del archivo antiguo. El archivo antiguo puede entonces ser eliminado y el nuevo archivo renombrado.
La asignación indexada es más compleja. Si el bloque índice ya está en memoria, entonces el acceso se puede realizar directamente. Sin embargo, mantener el bloque índice en la memoria requiere un espacio considerable. Si este espacio de memoria no está disponible, entonces es posible que tengamos que leer primero el bloque índice y luego el bloque de datos deseado. Para un índice de dos niveles, pueden ser necesarias dos lecturas de bloque índice. Para un archivo extremadamente grande, acceder a un bloque cerca del final del archivo requiere lectura de todos los bloques índice antes de que finalmente el bloque de datos necesario se pueda leer. Por lo tanto, el rendimiento de la asignación indexada depende de la estructura de índice, del tamaño del archivo y de la posición del bloque deseado.
Algunos sistemas combinan la asignación contigua con la asignación indexada usando asignación contigua para archivos pequeños (hasta tres o cuatro bloques) y automáticamente cambian a una asignación indexada si el archivo aumenta de tamaño. Ya que la mayoría de los archivos son pequeños y la asignación contigua es eficiente para archivos pequeños, el promedio del rendimiento puede ser bastante bueno.
Se están utilizando muchas otras optimizaciones. Dada la disparidad entre la velocidad de CPU y velocidad del disco, no es descabellado agregar miles de instrucciones adicionales al sistema operativo para salvar algunos movimientos de las cabezas del disco. Además, esta disparidad está aumentando con el tiempo, hasta el punto en que cientos de miles de instrucciones podrían utilizarse razonablemente para optimizar los movimientos de la cabeza. 
Para los dispositivos NVM, no hay búsquedas de cabeza de disco, por lo que se necesitan diferentes algoritmos y optimizaciones. Usando un algoritmo antiguo que gasta muchos ciclos de CPU que intentan evitar un movimiento de cabeza inexistente serían muy ineficaces. Los sistemas de archivos existentes se están modificando y se están creando nuevos para lograr máximo rendimiento de los dispositivos de almacenamiento NVM. Estos desarrollos apuntan a reducir la cantidad de instrucciones y el camino general entre el dispositivo de almacenamiento y el acceso de la aplicación a los datos.
14.5 Gestión del espacio libre
Dado que el espacio de almacenamiento es limitado, necesitamos reutilizar el espacio de los archivos eliminados para archivos nuevos. (Los discos ópticos de una sola escritura solo permiten una escritura en cualquier sector dado y, por lo tanto, no es físicamente posible la reutilización). Para hacer un seguimiento de espacio en disco, el sistema mantiene una lista de espacio libre. La lista de espacio libre registra todos los bloques libres: los que no están asignados a algún archivo o directorio. Para crear un archivo, buscamos en la lista de espacio libre la cantidad de espacio requerida y asignamos ese espacio al nuevo archivo. A continuación, este espacio se elimina de la lista de espacios libres. Cuando se elimina un archivo, su espacio se agrega a la lista de espacios libres. La lista de espacio libre, a pesar de su nombre, no se implementa necesariamente como una lista, como discutimos siguiente.
14.5.1 Vector de bits
Con frecuencia, la lista de espacio libre se implementa como un mapa de bitso un vector de bits. Cada bloque está representado por 1 bit. Si el bloque está libre, el bit es 1; si el bloque está asignado, el bit es 0.
Por ejemplo, considere un disco donde los bloques 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 y 27 están libres y el resto de bloques están asignados. El espacio libre mapa de bits sería
001111001111110001100000011100000 ...
La principal ventaja de este enfoque es su relativa simplicidad y su eficiencia para encontrar el primer bloque libre o n bloques libres consecutivos en el disco. De hecho, muchas computadoras proporcionan instrucciones de manejo de bits que se pueden utilizar efectivamente para ese propósito. Una técnica para encontrar el primer bloque libre en un sistema que usa un vector de bits para asignar espacio es verificar secuencialmente cada palabra en el mapa de bits para ver si tiene valor 0 o no, ya que una palabra con valor 0 contiene solo bits en 0 y representa un conjunto de bloques asignados. Se escanea en la palabra el primer no 0 para el primer bit, que es la ubicación del primer bloque libre. El cálculo del número de bloque es:
(número de bits por palabra) × (número de palabras de valor 0) + desplazamiento del primer bit.
Nuevamente, vemos características de hardware que impulsan la funcionalidad del software. Desafortunadamente, los vectores de bits son ineficientes a menos que el vector completo se mantenga en la memoria principal (y se escriba en el dispositivo que contiene el sistema de archivos ocasionalmente para las necesidades de back-up). Mantenerlo en la memoria principal es posible, para dispositivos pequeños, pero no para los más grandes. Un disco de 1,3 GB con bloques de 512 bytes necesitaría un mapa de bits de más de 332 KB para rastrear sus bloques libres, aunque agrupando los bloques en grupos de cuatro reduce este número a alrededor de 83 KB por disco. Un Disco de 1-TB con bloques de 4 KB requerirían 32 MB (240/212 = 228 bits = 225 bytes = 25 MB) para almacenar su mapa de bits. Dado que el tamaño del disco aumenta constantemente, el problema con los vectores de bit seguirá aumentando también.
Figura 14.9 Lista enlazada de espacio libre en disco.
14.5.2 Lista enlazada
Otro enfoque para la gestión del espacio libre es enlazar todos los bloques, manteniendo un puntero al primer bloque libre en una ubicación especial en el sistema de archivos y almacenarlo en la memoria caché. Este primer bloque contiene un puntero al siguiente bloque libre, y así sucesivamente. Recuerde nuestro ejemplo anterior (Sección 14.5.1), en el que los bloques 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 y 27 eran libres y el resto de los bloques fueron asignados. En esta situación, mantendríamos un puntero para el bloque 2 como el primer bloque libre. El bloque 2 contendría un puntero al bloque 3, que apuntaría al bloque 4, que apuntaría al bloque 5, que apuntaría al bloque 8, y así sucesivamente (Figura 14.9). Este esquema no es eficiente; para recorrer la lista, debemos leer cada bloque, lo que requiere un tiempo de E/S sustancial en los discos duros. Sin embargo afortunadamente, recorrer la lista libre no es frecuente. 
Generalmente el sistema operativo simplemente necesita un bloque libre para poder asignar ese bloque a un archivo, por lo que se utiliza el primer bloque de la lista libre. El método FAT incorpora la estructura de datos de contabilidad de bloques libres en la asignación. No hace falta otro método.
14.5.3 Agrupación
Una modificación del enfoque de lista libre almacena las direcciones de n bloques libres en el primer bloque libre. Los primeros n − 1 bloques son realmente libres. El último bloque contiene las direcciones de otros n bloques libres, y así sucesivamente. Las direcciones de una gran cantidad de bloques libres ahora se pueden encontrar rápidamente, a diferencia de la situación cuando se utiliza el enfoque estándar de la lista enlazada.
14.5.4 Conteo
Otro enfoque aprovecha el hecho de que, por lo general, varios bloques pueden asignarse o liberarse simultáneamente, especialmente cuando el espacio se asigna con el algoritmo de asignación contigua o mediante agrupación. Por lo tanto, en lugar de mantener una lista de n direcciones de bloques libres, podemos mantener la dirección del primer bloque libre y el número (n) de bloques contiguos libres que siguen al primer bloque. Cada entrada en la lista de espacio libre consta de una dirección de dispositivo y un contador. Aunque cada entrada requiere más espacio que una dirección de disco simple, la lista general es más corta, siempre que el contador sea generalmente mayor que 1. Tenga en cuenta que este método de seguimiento del espacio libre es similar al método de asignación de bloques extendido. Estas entradas se pueden almacenar en un árbol balanceado, en lugar de una lista enlazada, para una búsqueda, inserción y eliminación eficientes.
14.5.5 Mapas de espacios
Los sistemas de archivos ZFS (sistemas de archivos Z) de Oracle (que se encuentra en Solaris y en algunos otros sistemas operativos) fue diseñado para abarcar una gran cantidad de archivos, directorios e incluso sistemas de archivos (en ZFS, podemos crear jerarquías de sistemas de archivos). En estas escalas, los metadatos de las E/S pueden tener un gran impacto en el rendimiento. Considere, por ejemplo, que la lista de espacio libre se implementa como un mapa de bits, los mapas de bits deben modificarse en el momento que se asignan y cuando se liberan los bloques. Liberar 1 GB de datos en un disco de 1 TB podría provocar la actualización de miles de bloques de mapas de bits, porque esos bloques de datos podrían estar esparcidos por todo el disco. Claramente, las estructuras de datos para tal sistema podrían ser grandes e ineficientes.
En su gestión del espacio libre, ZFS utiliza una combinación de técnicas para controlar el tamaño de las estructuras de datos y minimizar la E/S necesaria para administrar esas estructuras. Primero, ZFS crea metaslabs para dividir el espacio del dispositivo en trozos de tamaño manejable. Un volumen dado puede contener cientos de metaslabs. Cada metaslab tiene un mapa espacial asociado. ZFS usa el algoritmo de conteo para almacenar información sobre bloques libres. En lugar de escribir estructuras de conteo en disco, utiliza técnicas de sistema de archivos estructurados por registros para escribirlas. El mapa espacial es un registro de toda la actividad del bloque (asignación y liberación), ordenados por tiempo, en formato de conteo. Cuando ZFS decide asignar o liberar espacio de un metaslab, carga el mapa espacial asociado en la memoria en una estructura de árbol balanceado (una operación muy eficiente), indexada por desplazamiento, y reproduce el registro en esa estructura. El mapa de espacio en memoria es entonces una representación precisa del espacio asignado y libre en el metaslab. ZFS también condensa el mapa tanto como sea posible combinando bloques libres contiguos en una sola entrada. Finalmente, la lista de espacio libre se actualiza en el disco como parte del programa de operaciones orientado a transacciones de ZFS. Durante la fase de recopilación y clasificación, las solicitudes de bloques pueden aún ocurrir, y ZFS satisface estas solicitudes del registro. En esencia, la lista libre es el registro más el árbol balanceado.
14.5.6 Recorte de bloques no utilizados
HDD y otros medios de almacenamiento que permiten sobrescribir bloques para actualizaciones solo necesita la lista libre para administrar el espacio libre. Los bloques no necesitan ser tratados especialmente cuando son liberados. Un bloque liberado normalmente conserva sus datos (pero sin ningún puntero de archivo al bloque) hasta que los datos se sobrescriban cuando el bloque es el siguiente asignado.
Dispositivos de almacenamiento que no permiten sobrescribir, como los dispositivos de almacenamiento NVM basados ​​en flash, sufren mucho cuando se aplican estos mismos algoritmos. Recordar de la Sección 11.1.2 que dichos dispositivos deben borrarse antes de que puedan volver a escribir, y que esos borradosdeben hacerse en grandes trozos (bloques, conjunto de páginas) y toma un tiempo relativamente largo en comparación con las lecturas o escrituras.
Se necesita un nuevo mecanismo para permitir que el sistema de archivos informe al almacenamiento dispositivo que una página es libre y se puede considerar para su eliminación (una vez que el bloque que contiene la página es completamente libre). Ese mecanismo varía según el almacenamiento controlador. Para las unidades conectadas a ATA, es TRIM, mientras que para el almacenamiento basado en NVMe, es el comando unallocate. Cualquiera que sea el comando del controlador específico, este mecanismo mantiene el espacio de almacenamiento disponible para escribir. Sin tal capacidad, el dispositivo de almacenamiento se llena y necesita recolección de basura y borrado de bloques, lo que provoca una disminución en el rendimiento de escritura de E/S de almacenamiento (conocido como "acantilado de escritura"). Con el mecanismo TRIM y capacidades similares, la recolección de basura y Los pasos de borrado pueden ocurrir antes de que el dispositivo esté casi lleno, lo que permite que el dispositivo proporcionar un rendimiento más consistente.
14.6 Eficiencia y rendimiento
Ahora que hemos discutido varias opciones de asignaciones de bloques y administración de directorios, podemos considerar su efecto en el rendimiento y uso eficiente del almacenamiento. Los discos tienden a representar un cuello de botella importante en el rendimiento del sistema, ya que es el componente principal de la computadora más lento. Incluso los dispositivos NVM son lentos en comparación con la CPU y la memoria principal, por lo que su rendimiento se debe optimizar también. En esta sección, discutimos una variedad de técnicas que se utilizan para mejorar la eficiencia y el rendimiento del almacenamiento secundario.
14.6.1 Eficiencia
El uso eficiente del espacio del dispositivo de almacenamiento depende en gran medida de los algoritmos de asignación y los directorios en uso. Por ejemplo, los inodos de UNIX están preasignados en un volumen. Incluso un disco vacío tiene un porcentaje de su espacio perdido en inodos. Sin embargo, al preasignar los inodos y distribuirlos por el volumen, mejoramos el rendimiento del sistema de archivos. Este rendimiento mejorado es resultado de la asignación de UNIX y los algoritmos de espacio libre, que tratan de mantener los bloques de datos de un archivo cerca del bloque de inodo de ese archivo para reducir el tiempo de búsqueda.
Como otro ejemplo, reconsideremos el esquema de agrupamiento (clustering) discutido en Sección 14.4, que mejora el rendimiento de búsqueda y transferencia de archivos a costa de fragmentación interna. Para reducir esta fragmentación, BSD UNIX varía el tamaño del clúster a medida que crece un archivo. Se utilizan grandes grupos donde se pueden llenar, y los grupos pequeños se utilizan para archivos pequeños y el último grupo de un archivo. Este sistema se describe en el Apéndice C.
Los tipos de datos que normalmente se guardan en la entrada del directorio (o inodo) de un archivo también requieren consideración. Por lo general, se registra una "fecha de última de escritura" para proporcionar información al usuario y para determinar si el archivo necesita ser respaldado. Algunos sistemas también mantienen una "fecha de último acceso" para que el usuario pueda determinar cuándo se leyó el archivo por última vez. El resultado de mantener esta información es que, siempre que se lee el archivo, se debe escribir de un campo de la estructura del directorio. Eso significa que el bloque se debe leer en la memoria, cambiar una sección y bloquear la escritura de nuevo en el dispositivo, porque las operaciones en el almacenamiento secundario ocurren solo en bloques (o grupos). Por tanto, cada vez que se abre un archivo para su lectura, su FCB debe leerse y escribirse también. Este requisito puede ser ineficaz para archivos a los que se accede con frecuencia, por lo que debemos sopesar su beneficio con su costo de rendimiento al diseñar un sistema de archivos. Generalmente, todos los elementos de datos asociados con un archivo deben ser considerados por su efecto sobre la eficiencia y el rendimiento.
Considere, por ejemplo, cómo la eficiencia se ve afectada por el tamaño de los punteros utilizado para acceder a los datos. La mayoría de los sistemas utilizan punteros de 32 bits o de 64 bits El uso de punteros de 32 bits limita el tamaño de un archivo a 232, o 4 GB. El uso de punteros de 64 bits permite tamaños de archivo muy grandes, pero los punteros de 64 bits requieren más espacio para almacenar. Como resultado, los métodos de asignación y gestión del espacio libre (listas enlazadas, índices, etc.) utilizan más espacio de almacenamiento. 
Una de las dificultades para elegir un tamaño de puntero o, de hecho, cualquier asignación fija tamaño dentro de un sistema operativo: es prever los efectos de cambios en la tecnología. Considere que el IBM PC XT tenía un disco duro de 10 MB y un MS-DOS Sistema de archivos FAT que solo admite 32 MB. (Cada entrada FAT era de 12 bits, apuntando a un clúster de 8 KB). A medida que aumentaban las capacidades del disco, los discos más grandes tenían que dividirse en particiones de 32 MB, porque el sistema de archivos no podía rastrear bloques más allá de 32 MB. A medida que los discos duros con capacidades de más de 100 MB se volvieron comunes, Las estructuras de datos del disco y los algoritmos en MS-DOS tuvieron que modificarse para permitir sistemas de archivos más grandes. (Cada entrada FAT se expandió a 16 bits y luego a 32 bits.) Las decisiones iniciales del sistema de archivos se tomaron por razones de eficiencia; sin embargo, con la llegada de la versión 4 de MS-DOS, millones de usuarios de computadoras tuvieron inconvenientes cuando tuvieron que cambiar al nuevo sistema de archivos más grande. El sistema de archivos de Solaris, ZFS utiliza punteros de 128 bits, que teóricamente nunca debería necesitar ser extendido. (La masa mínima de un dispositivo capaz de almacenar 2128 bytes utilizando El almacenamiento a nivel atómico sería de unos 272 trillones de kilogramos).
Como otro ejemplo, considere la evolución del sistema operativo Solaris. Originalmente, muchas estructuras de datos eran de longitud fija, asignadas en el sistema en el momento que se inicializa. Estas estructuras incluían la tabla de procesos y la tabla de archivos abiertos. Cuando la tabla de procesos se llenó, no se pudieron crear más procesos. Cuando la tabla de archivos se llenó, no se pudieron abrir archivos. para prestar servicios a los usuarios. Los tamaños de las tablas solo se pueden aumentar recompilando el kernel y reiniciar el sistema. Con versiones posteriores de Solaris, (como con kernels modernos de Linux) casi todas las estructuras del kernel se asignan dinámicamente, eliminando estos límites artificiales en el rendimiento del sistema. Por supuesto, los algoritmos que manipulan estas tablas son más complicados, y el funcionamiento del sistema es un poco más lento porque debe asignar y desasignar dinámicamente entradas de la tabla; pero ese precio es el habitual para una funcionalidad más general.
14.6.2 Rendimiento
Incluso después de haber seleccionado los algoritmos básicos del sistema de archivos, aún podemos mejorar el rendimiento de varias formas. Como se discutió en el Capítulo 12, los controladores de dispositivo de almacenamiento incluyen memoria local para formar una caché integrada que es suficientemente grande para almacenar pistas o bloques completos a la vez. En un disco duro, una vez que se realiza una búsqueda, la pista se lee en la caché del disco comenzando en el sector bajo el cabezal de disco (reduciendo el tiempo de latencia). El controlador de disco luego transfiere solicitudes al sistema operativo. Una vez que el controlador de disco deja los bloques en la memoria principal, el sistema operativo puede almacenarlos en caché.
Algunos sistemas mantienen una sección separada de la memoria principal para un búfer-caché,donde los bloques se mantienen bajo el supuesto de que se utilizarán de nuevo en breve. Otros sistemas almacenan en caché los datos del archivo utilizando una caché de página. La caché de página utiliza técnicas de memoria virtual para almacenar en caché los datos del archivo como páginas en lugar de como bloques orientados al sistema de archivos. El almacenamiento en caché de datos de archivos utilizando direcciones virtuales es por lejos, más eficiente que el almacenamiento en caché a través de bloques de disco físico, ya que accede a la interfaz con memoria virtual en lugar del sistema de archivos. Varios sistemas, incluidos Solaris, Linux y Windows utilizan el almacenamiento en caché de páginas para almacenar en caché ambas páginas de proceso y archivos de datos. Esto se conoce como memoria virtual unificada.
Figura 14.10 E/S sin caché de búfer unificado.
Algunas versiones de UNIX y Linux proporcionan una caché de búfer unificada. Para ilustrar los beneficios de la caché de búfer unificada, considere las dos alternativas para abrir y acceder a un archivo. Un enfoque es utilizar el mapeo de memoria (Sección 13.5); el segundo es utilizar las llamadas al sistema estándar read () y write (). Sin una caché de búfer unificada, tenemos una situación similar a la de la Figura 14.10. Aquí, las llamadas al sistema read () y write () pasan por un búfer caché. La llamada de asignación de memoria, sin embargo, requiere el uso de dos cachés: la caché de página y el caché del búfer. Un mapeo de memoria procede leyendo en disco los bloques del sistema de archivos y almacenarlos en la caché del búfer. Porque el sistema de memoria virtual no interactúa con la caché del búfer, el contenido del archivo en la caché del búfer debe copiarse en la caché de la página. Esta situación, conocida como doble caché, requiere almacenar en caché los datos del sistema de archivos dos veces. No solo esto desperdicia memoria sino también desperdicia una cantidad significativa de CPU y ciclos de E/S debido al movimiento de datos extra dentro de la memoria del sistema. Además, inconsistencias entre los dos cachés puede resultar en archivos corruptos. Por el contrario, cuando se proporciona caché de búfer, tanto la asignación de memoria como las llamadas al sistema de lectura () y escritura () utilizan la misma caché de página. Esto tiene el beneficio de evitar el doble almacenamiento en caché y permite que el sistema de memoria virtual administre los datos del sistema de archivos. La caché de búfer unificada se muestra en la Figura 14.11.
Independientemente de si estamos almacenando en caché: bloques de almacenamiento o páginas (o ambos), parece razonable para el reemplazo de páginas o bloques, el algoritmo menos recientemente utilizado (LRU) (Sección 10.4.4). Sin embargo, la evolución de los algoritmos de Solaris, de almacenamiento en caché de páginas revelan la dificultad de elegir un algoritmo. Solaris permite a los procesos y a la caché de páginas compartir la memoria no utilizada. Versiones anteriores a Solaris 2.5.1 no hacían distinción entre la asignación de páginas a un proceso y asignarlos a la caché de la página. Como resultado, un sistema que realiza muchas operaciones de E/S utilizan la mayor parte de la memoria disponible para almacenar páginas en caché. Por las altas tasas de E/S, el escáner de páginas (Sección 10.10.3) recupera páginas de los procesos, en lugar desde la caché de la página, cuando se ejecuta con baja memoria libre. Solaris 2.6 y Solaris 7 implementaron opcionalmente la paginación por prioridad, en la que el escáner de páginas dio prioridad a las páginas de procesamiento sobre la caché de páginas. Solaris 8 aplicó un límite fijo para procesar las páginas y la caché de páginas del sistema de archivos, y evitar que se expulse a otro fuera de la memoria. Solaris 9 y 10 nuevamente cambiaron los algoritmos para maximizar el uso de la memoria y minimizar la hiperpaginación.
Otro problema que puede afectar el rendimiento de la E/S es si la escritura en el sistema de archivos se produce de forma sincrónica o asincrónica. Escrituras sincrónicas ocurren en el orden en que el subsistema de almacenamiento los recibe, y las escrituras no se almacenan en búfer. Por lo tanto, la rutina de llamada debe esperar a que los datos llegar a la unidad antes de que pueda continuar. En una escritura asincrónica, los datos se almacenan en la caché y el control vuelve al proceso que llama. La mayoría de las escrituras son asincrónicas. Sin embargo, las escrituras de metadatos, entre otras, pueden ser sincrónicas. Los sistemas operativos suelen incluir una bandera en la llamada al sistema abierto para permitir un proceso para solicitar que las escrituras se realicen sincrónicamente. Por ejemplo, Las bases de datos utilizan esta función para transacciones atómicas, para asegurar que los datos lleguen almacenamiento estable en el orden requerido.
Figura 14.11 E/S usando una caché de búfer unificada.
Algunos sistemas optimizan la caché de página utilizando diferentes algoritmos de reemplazo, dependiendo del tipo de acceso del archivo. Un archivo que está siendo leído o escrito secuencialmente no debería tener sus páginas reemplazadas en el orden LRU, porque la página utilizada más recientemente se utilizará en último lugar, o quizás nunca. En cambio, el acceso secuencial se puede optimizar mediante técnicas conocidas como free-behind y lectura por adelantado. Free-behind elimina una página del búfer tan pronto como la página siguiente es solicitada. No es probable que las páginas anteriores se vuelvan a utilizar y desperdician espacio de búfer con la lectura anticipada, una página solicitada y varias páginas leídas y se almacenan en caché. Es probable que estas páginas se soliciten después de que se procesa la página actual. Recuperar estos datos del disco en una sola transferencia y almacenarlos en caché ahorra una cantidad considerable de tiempo. Uno podría pensar que un caché por pistas en el controlador eliminaría la necesidad de lectura anticipada en un sistema multiprogramado. Sin embargo, debido a la alta latencia y la sobrecarga involucrados en hacer muchas pequeñas transferencias desde la caché de pistas a la memoria principal, realizar una lectura anticipada sigue siendo beneficioso.
La caché de página, el sistema de archivos y los controladores de dispositivo tienen algunas interacciones. Cuando se escriben pequeñas cantidades de datos en un archivo, las páginas se almacenan en búfer en la memoria caché y el controlador del dispositivo de almacenamiento ordena su cola de salida según la dirección del dispositivo. Estas dos acciones permiten que un controlador de disco minimice la búsqueda, con el movimiento de cabeza del disco. A menos que se requieran escrituras síncronas, un proceso que escriba en disco simplemente escribe en la caché, y el sistema escribe asincrónicamente los datos al disco cuando sea conveniente. El proceso de usuario hace las escrituras muy rápidas. Cuando los datos se leen desde un archivo de disco, el sistema de E/S de bloques realiza una lectura anticipada; sin embargo, las escrituras son mucho más asincrónicas que las lecturas. Así, La salida al disco a través del sistema de archivos suele ser más rápida que la entrada para pequeñas transferencias, contrario a la intuición. No importa cuánto almacenamiento en búfer y caché haya, las E/S disponibles, grandes y continuas pueden sobrepasar la capacidad y terminar con un cuello de botella en el rendimiento del dispositivo. Considere escribir un archivo de película grande en un HDD. Si el archivo es más grande que la caché de página (o la parte de la caché de la página disponible para el proceso), la caché de la página se llenará y todas las E/S ocurrirán en velocidad de conducción. Los discos duros actuales leen más rápido de lo que escriben, por lo que en este caso los aspectos de rendimiento se invierten del rendimiento de E/S más pequeño.
14.7 Recuperación
Los archivos y directorios se guardan tanto en la memoria principal como en el volumende almacenamiento, y se debe tener cuidado para asegurar que una falla del sistema no resulte en la pérdida de datos o en la inconsistencia de datos. Una falla del sistema puede causar inconsistencias entre Estructuras de datos del sistema de archivos en almacenamiento, como estructuras de directorio, punteros de bloques libres y punteros de FCB libres. Muchos sistemas de archivos realizan cambios a estas estructuras. Una operación típica, como la creación de un archivo, puede implicar muchos cambios estructurales dentro del sistema de archivos en el disco. Se modifican Estructuras de directorio, se asignan FCB, se asignan bloques de datos y la cuenta de bloques libres porque todos estos bloques se reducen. Estos cambios pueden ser interrumpidos por un accidente, y pueden resultar inconsistencias entre las estructuras. Por ejemplo, el contador de FCBs libres puede indicar que se ha asignado un FCB, pero la estructura de directorio no apunta al FCB. Para agravar este problema está el almacenamiento en caché que hacen los sistemas operativos para optimizar el rendimiento de E/S. Algunos cambios pueden desaparecer directamente en el almacenamiento, mientras que otros pueden almacenarse en caché. Si los cambios en caché no llegan al dispositivo de almacenamiento antes de que se produzca un bloqueo, es posible que se produzcan más daños. 
Además de los desastres puede haber errores en la implementación del sistema de archivos, controladores de dispositivos, e incluso las aplicaciones de usuario pueden dañar un sistema de archivos. Los sistemas de archivos tienen diversos métodos para lidiar con la corrupción, dependiendo de los datos del sistema de archivos. estructuras y algoritmos. A continuación, trataremos estos problemas.
14.7.1 Comprobación de coherencia
Cualquiera sea la causa de la corrupción, un sistema de archivos primero debe detectar los problemas y luego corregirlos. Para la detección, un escaneo de todos los metadatos en cada sistema de archivo puede confirmar o negar la consistencia del sistema. Desafortunadamente, este escaneo puede tomar minutos u horas y debe hacerse cada vez que se inicia el sistema. Alternativamente, un sistema de archivos puede registrar su estado dentro de los metadatos del sistema de archivos. Al comienzo de cualquier cambio de metadatos, se establece un bit de estado para indicar que los metadatos están en constante cambio. Si todas las actualizaciones de los metadatos se completan correctamente, el archivo el sistema puede borrar ese bit. Sin embargo, si el bit de estado permanece establecido, se está ejecutando un control de consistencia.
El verificador de coherencia (un programa de sistemas como fsck en UNIX) compara los datos en la estructura del directorio y otros metadatos con el estado en almacenamiento e intenta corregir cualquier inconsistencia que encuentre. Los algoritmos de asignación y de administración de gestión del espacio libre dictan qué tipos de problemas puede encontrar y qué tan exitoso será para corregirlos. Por ejemplo, si se utiliza la asignación enlazada y hay un enlace de cualquier bloque al siguiente bloque, entonces todo el archivo se puede reconstruir a partir de los bloques de datos, y la estructura del directorio se puede recrear. Por el contrario, la pérdida de una entrada de directorio en un sistema de asignación indexada puede ser desastroso, porque los bloques de datos no se conocen unos a otros. Por esta razón, algunos sistemas de archivos UNIX tienen caché con entradas de directorio para lecturas, y las escrituras que resulten en la asignación de espacio, u otros cambios de metadatos, se deben realizar sincrónicamente, antes de que se escriba en los bloques de datos. Por supuesto, aún pueden ocurrir problemas si una escritura sincrónica se la interrumpe por un problema. Algunos dispositivos de almacenamiento NVM contienen una batería o un supercondensador para proporcionar suficiente energía, incluso durante una pérdida de energía, para escribir datos de los búferes del dispositivo a los medios de almacenamiento para que no se pierdan. Pero incluso esas precauciones no protegen contra la corrupción debido a un problema.
14.7.2 Sistemas de archivos estructurados por registros
Los informáticos a menudo encuentran que los algoritmos y tecnologías originalmente utilizados en un área son igualmente útiles en otras áreas. Tal es el caso de los algoritmos de recuperación basados ​​en registros de bases de datos. Estos algoritmos de registro se han aplicado con éxito al problema de la comprobación de la coherencia. La resultante de las implementaciones se conoce como sistemas de archivos basados en transacciones orientadas a registros (o registro en diario). Tenga en cuenta que, con el enfoque de verificación de coherencia discutido en la sección anterior, esencialmente permitimos que las estructuras se rompan y se reparen con la recuperación. Sin embargo, existen varios problemas con este enfoque. Uno es que la inconsistencia puede ser irreparable. Es posible que la comprobación de coherencia no pueda recuperar las estructuras, lo que resulta en la pérdida de archivos e incluso directorios completos. La verificación de la coherencia puede requerir la intervención humana para resolver conflictos, y eso es inconveniente si no hay ningún humano disponible. El sistema puede permanecer indisponible hasta que el humano le diga cómo proceder. La verificación de la coherencia también requiere de tiempo del sistema. Para comprobar terabytes de datos, se pueden necesitar varias horas.
La solución a este problema es aplicar técnicas de recuperación basadas en registros para actualizaciones de metadatos del sistema de archivos. Tanto NTFS como el sistema de archivos Veritas utilizan este y se incluye en versiones recientes de UFS en Solaris. De hecho, es ahora común en muchos sistemas de archivos, incluidos ext3, ext4 y ZFS.
Básicamente, todos los cambios de metadatos se escriben secuencialmente en un registro. Cada conjunto de operaciones para realizar una tarea específica es una transacción. Una vez los cambios se escriben en este registro, se consideran confirmados, y la llamada al sistema puede volver al proceso del usuario, lo que le permite continuar ejecución. Mientras tanto, estas entradas de registro se reproducen en todas las estructuras del sistema de archivos. A medida que se realizan los cambios, se actualiza un puntero para indicar qué acciones se han completado y cuáles aún están incompletas. Cuando transacción comprometida se completa y la entrada se realiza en el registro, indicándola. El archivo de registro es en realidad un búfer circular. Un búfer circular escribe en el final de su espacio y luego continúa al principio, sobrescribiendo los valores más antiguos. Como no quisiéramos que el búfer escribiera sobre datos que aún no se han guardado, se evita ese escenario. El registro puede estar en una sección separada del sistema de archivos o incluso en un dispositivo de almacenamiento separado.
Si el sistema falla, el archivo de registro contendrá cero o más transacciones. Las transacciones que contiene, no se completaron en el sistema de archivos, aunque fueron comprometidas por el sistema operativo, por lo que ahora deben completarse. Las transacciones se pueden ejecutar desde el puntero hasta que se complete el trabajo para que las estructuras del sistema de archivos sigan siendo coherentes. El único problema ocurre cuando se canceló una transacción, es decir, no se comprometió antes de que el sistema se estrelló. Cualquier el cambio de dicha transacción se haya aplicado al archivo, el sistema debe deshacerse, conservando nuevamente la consistencia del sistema de archivos. Esta recuperación es todo lo que se necesita después de una caída, eliminando cualquier problema con comprobación de coherencia.
Un beneficio adicional de usar el registro en las actualizaciones de metadatos del disco es que las actualizaciones proceden mucho más rápido que cuando se aplican directamente a las estructuras de datos de disco. La razón se