Sistemas Operativos

El método más simple para implementar un directorio consiste en utilizar una lista lineal o vector de nombres de archivos e identificadores del FCB.

Las acciones a realizar, para implementar cada una de las posibles operaciones sobre el directorio, serían:

La principal desventaja de un directorio implementado como una lista lineal de entradas es que para localizar un archivo es necesario realizar una búsqueda lineal, lo cual puede resultar muy costoso en directorios con un número muy grande de archivos. Utilizando una lista ordenada se puede reducir el tiempo medio de búsqueda, pero complica los procesos de creación y borrado, pues puede que sea necesario mover cantidades importantes de información para mantener la lista ordenada.

También se puede utilizar una lista enlazada, tanto para reducir el tiempo necesario para borrar un archivo como para facilitar la tarea de mantener ordenada la lista.

Los sistemas de archivos FAT y FAT32 implementan los directorios utilizando una lista lineal, donde en cada entrada se almacena el nombre del archivo y el FCB del mismo. Al borrar un archivo, la entrada correspondiente se marca poniendo 0xE5 en el primer caracter del nombre del archivo.

Los sistemas de archivos ext2 y UFS también utilizan una lista lineal no ordenada, donde solo se almacena el nombre del archivo o subdirectorio y el identificador del inodo —el FCB, esos sistemas de archivo— correspondiente. En caso de borrar un archivo, el identificador del inodo se pone a 0.

En los directorios implementados con una tabla de dispersión también se almacenan las entradas de directorio en una lista lineal, pero al mismo tiempo se utiliza una tabla de dispersión para reducir enormemente el tiempo de búsqueda en el directorio. Para obtener la ubicación de dicho archivo dentro de la lista lineal, se usa un índice calculado con cierta función de dispersión a partir del nombre del archivo.

El único inconveniente es que debemos tratar la posible aparición de colisiones, que son aquellas situaciones en las que dos nombres de archivo dan lugar, al aplicarles la función de dispersión, la misma ubicación en la tabla. Esto se puede resolver utilizando una lista enlazada en cada entrada de la lista —cada entrada en la lista señalaría la ubicación de la siguiente entrada de la lista que tiene el mismo valor para la función de dispersión— a cambio de que las búsquedas sean un poco más lentas. En cualquier caso, este método será normalmente más rápido que una búsqueda lineal por todo el directorio.

Para mantener el directorio ordenado, algunos sistemas de archivos modernos utilizan estructuras de datos en árbol más sofisticadas, como por ejemplo árboles B.

Un caso concreto es el sistema de archivos NTFS, utilizado por Microsoft Windows. NTFS utiliza una estructura de datos denominada árbol B+ para almacenar el índice de los nombres de archivo contenidos en un directorio.

En la entrada en la MFT (Master File Table) de cada directorio se almacena un atributo denominado raíz del índice. Si el directorio es de pequeño tamaño, la raíz del índice contiene todas las entradas de archivos del directorio, pero para un directorio de gran tamaño, la raíz del índice solo puede almacenar unas pocas entradas de archivos del directorio. En ese caso la raíz del índice contiene el nivel superior del árbol B+. Es decir, cada una de esas entradas de archivos en la raíz del índice incluye también un puntero al bloque del disco que contiene un nodo del árbol con las entradas con nombres alfabéticamente anteriores a ese. Si en dicho nodo tampoco caben todas las entradas, solo podrá contener algunas de ellas, por lo que cada una tendrá, a su vez, un puntero a un nuevo nodo del árbol; y así sucesivamente.

Las ventajas de los árboles B+ son:

La asignación contigua requiere que cada archivo ocupe un conjunto contiguo de bloques en el disco. Esto es muy eficiente, puesto que el acceso a todos los datos de un archivo requiere un movimiento mínimo del cabezal del disco.

El problema de la asignación contigua puede verse como un caso concreto del problema de la asignación dinámica del almacenamiento (véase el Apartado 15.5). Es decir, que en un momento dado tendremos una petición de tamaño N que deberemos satisfacer con una lista de huecos libres de tamaño variable. Como estudiamos anteriormente, las estrategias más comunes son las del primer ajuste y el mejor ajuste.

En la asignación enlazada cada archivo es una lista enlazada de bloques de disco, pudiendo estos bloques estar dispersos por todo el disco:

Este mecanismo resuelve todos los problemas de la asignación contigua y además:

Sin embargo, la asignación enlazada también tiene sus desventajas.

El mecanismo de asignación indexada agrupa todos los punteros de la asignación enlazada en una única ubicación: el bloque de índices. Así se resuelve la falta de eficiencia de la asignación enlazada convencional —en ausencia de FAT— cuando se realizan accesos aleatorios.

Este mecanismo soporta el acceso aleatorio eficiente, además de no sufrir el problema de la fragmentación externa. Sin embargo, también tiene sus desventajas:

Entre los mecanismos que pueden utilizarse para resolver este último problema están los siguientes:

Para mejorar el rendimiento de los mecanismos de asignación indexados, es muy común que el sistema operativo intente mantener los bloques de índices en la memoria.

La lista de espacio libre puede ser implementada como un vector de bits o mapa de bits, donde cada bloque es representado por un bit. Si el bloque está libre, el bit está a 1, mientras que si el bloque está asignado, el bit está a 0.

Este enfoque es relativamente sencillo y eficiente, puesto que muchos procesadores disponen de instrucciones para manipular bits, que pueden utilizarse para obtener rápidamente el primer bloque libre. Por ejemplo, la familia de procesadores x86, a partir del Intel 80386, tiene instrucciones que devuelven la posición del primer bit a 1 en el valor de un registro.

Sin embargo, leer el vector de bits, modificarlo y actualizarlo en disco en cada ocasión, es tremendamente ineficiente. Por tanto, usar vectores de bits es ineficiente, a menos que se mantenga el vector completo en la memoria principal, escribiéndose ocasionalmente en el disco.

Esto último puede ser imposible para los discos de gran tamaño, en función de la cantidad de memoria principal. Por ejemplo, un disco de 40 GiB con bloques de 512 bytes necesitará un mapa de bits de más de 10 MiB, lo que no es un gran requisito para un sistema moderno, pero sí lo era hace dos décadas.

Otra técnica consiste en enlazar todos los bloques de disco libres. Para eso se puede guardar un puntero al primer bloque libre en una ubicación especial del disco y que ese bloque contenga un puntero al siguiente bloque libre del disco. El segundo bloque contenga un puntero al tercer bloque libre, y así sucesivamente.

El inconveniente es que recorrer la lista no resulta eficiente, pues tenemos que leer cada bloque para conocer la dirección del siguiente bloque libre en disco. Sin embargo, debemos tener en cuenta que no es frecuente tener que recorrer la lista de espacio libre completa porque, por lo general, basta con encontrar el primer bloque libre para asignar el espacio.

Una modificación de la técnica basada en la lista enlazada consiste en almacenar las direcciones de N bloques libres en el primer bloque libre. Los primeros N — 1 de esos bloques estarían realmente libres, pero el último de ellos apuntaría a otro bloque con N bloques libres. Así podrían localizarse rápidamente las direcciones de un gran número de bloques libres, lo cual mejora la eficiencia respecto a la técnica de lista enlazada.

Generalmente los bloques son asignados o liberados en bloques contiguos, especialmente si el espacio es asignado mediante asignación contigua o en extensiones o clústeres. Esto puede ser aprovechado para mantener una lista donde cada entrada almacena la dirección del primer bloque de un conjunto de bloques libres contiguo, así como el número de bloques del conjunto.

Por ejemplo, el sistema de archivos XFS utiliza un árbol B+ para almacenar las direcciones de las extensiones de bloques libres y mantenerlas ordenadas por el tamaño de la extensión a la que apuntan. Así el sistema operativo puede localizar rápidamente el espacio libre necesario para satisfacer una necesidad concreta.

El primer nivel es la interfaz del sistema de archivos, a la que acceden los desarrolladores a través de las llamadas al sistema. En sistemas POSIX, estamos hablando de las llamadas open(), read(), write() y close(), entre otras. Y de los descriptores de archivos con los que se identifican los archivos abiertos.

Esta interfaz es la misma sea cual sea el sistema de archivos al que se esté intentando acceder.

El segundo nivel es la interfaz del sistema de archivos virtual o VFS (Virtual File System). Este nivel es utilizado por el anterior para atender las peticiones realizadas.

Describe operaciones genéricas sobre cualquier sistema de archivos y estructuras genéricas. Por ejemplo, el FCB virtual, que identifica de forma unívoca a cada archivo o directorio en uso en todo el sistema, dando acceso a sus metadatos.

Este nivel cumple con dos importantes funciones:

El tercer nivel es donde se implementa cada tipo de sistema de archivos o los distintos protocolos de los servidores de archivos en la red. La interfaz VFS recurre a la implementación correspondiente para cada tipo de sistema de archivos, para satisfacer las solicitudes de los niveles superiores.

Así, por ejemplo, un read() puede implicar que se tenga que recuperar el vnodo del archivo involucrado desde la tabla de archivos abiertos, usando el descriptor de archivo indicado en la llamada al sistema. Después, se invoca la operación VFS read() sobre el vnodo, en la implementación concreta de VFS según el tipo de sistema de archivos involucrado. Será esa implementación quien extraiga del vnodo la información necesaria —por ejemplo, el inodo real del archivo en el sistema de archivos— para llevar a cabo la operación indicada, según las especificidades del sistema de archivos.

En un disco duro magnético el tiempo de acceso al disco T^d viene determinado por el tiempo de búsqueda T^b y la latencia rotacional T^r:

El tiempo de búsqueda T^b es el tiempo que se tarda en mover el brazo del disco hasta el cilindro deseado. Mientras que la latencia rotacional T^r es el tiempo que hay que esperar para que el disco gira hasta que la cabeza llegue al sector deseado del cilindro. Por lo tanto, el tiempo de acceso al disco es menor cuando se realizan accesos consecutivos a sectores físicamente próximos que cuando están dispersos por todo el disco.

El ancho de banda o tasa de transferencia del disco es el total de bytes transferidos en una petición dividida por el tiempo total que transcurre desde la primera solicitud de servicio hasta el final de la última transferencia, con la que se termina de atender la petición. Al considerar todo el tiempo necesario para atender la petición, a más tiempo de acceso al disco menor es el ancho de banda.

En los dispositivos de almacenamiento basados en memorias de estado sólido (véase el Apartado 18.1.3) el tiempo de acceso viene determinado por las características de la memoria —entre otros factores— lo que hace que las diferencias entre accesos secuenciales y accesos aleatorios sean mucho menos significativas.

Cuando se solicita una operación de E/S sobre el almacenamiento, si la controladora y la unidad de disco están desocupadas, el sistema operativo puede atender la petición sobre la marcha. Pero si están ocupadas, el sistema operativo almacena la solicitud en una cola de peticiones pendientes. Cuando se resuelve una solicitud, el sistema operativo escoge otra de la cola y se comunica con el hardware para programar la siguiente petición. La cuestión es ¿cuál es el orden adecuado para escoger la peticiones de E/S de la cola, si se quiere acceder al disco de la forma más eficaz posible?

En la planificación FCFS (First Come, First Served) o primero que llega, primero servido la cola de E/S al disco es FIFO. Es decir, que las solicitudes se atienden en orden de llegada.

Es el algoritmo de planificación más simple y es equitativo, en sentido de que atiende a todos los procesos por igual. Pero, lamentablemente, no proporciona el servicio más rápido en discos duros magnéticos, donde interesa mover el brazo del disco lo menos posible.

En la planificación SSTF (Sortest Seek Time First) o algoritmo de tiempo de búsqueda más corto, de toda cola se selecciona la solicitud con el menor tiempo de búsqueda desde la posición actual de la cabeza. Este algoritmo de planificación primero da servicio a las solicitudes cercanas a la posición actual de la cabeza, antes de alejarse para dar servicio a otras solicitudes, dado que el tiempo de búsqueda se incrementa a medida que lo hace el número de cilindros que es necesario recorrer para llegar a una posición dada.

Aun así, la solución no es óptima, dado que puede provocar inanición de algunas solicitudes, si van llegando constantemente nuevas solicitudes sobre regiones cercanas a donde está actualmente la cabeza del disco.

En la planificación SCAN, algoritmo de exploración o del ascensor, el brazo del disco comienza en un extremo del disco y se mueve hacia el otro, atendiendo solicitudes a medida que pasa por cada cilindro, hasta llegar al otro extremo del disco. En el otro extremo, la dirección de movimiento de la cabeza se invierte para recorrer el disco en sentido inverso, repitiendo el proceso.

Suponiendo que las solicitudes se distribuyen de forma uniforme a lo largo del disco, es de suponer que cuando se llega a un extremo —justo antes de volver— la cantidad de solicitudes en dicho extremo será notablemente menor que dónde comenzó el barrido que acaba de terminar. Entonces ¿por qué no volver a empezar desde ese extremo?

A la variante del SCAN que cuando llega a un extremo vuelve al inicio, para volver a barrer desde allí, sin atender ninguna solicitud por el camino, se la denomina C-SCAN —de Circula SCAN—. Con esta variante el tiempo que tiene que esperar una solicitud para ser atendida es más uniforme que con el algoritmo SCAN original.

En teoría los algoritmos SCAN y C-SCAN hacen que el brazo recorra los cilindros del primero al último, pero normalmente no se suelen implementar así.

Por lo general, cuando en el recorrido del brazo, tras atender una solicitud, se descubre que ya no hay más solicitudes siguiendo la misma dirección, el brazo invierte la dirección sin llegar hasta el extremo del disco.

A estas variantes de SCAN y C-SCAN se las denomina (LOOK) y (C-LOOK), respectivamente.

Los algoritmos N-Step-SCAN y N-Step-LOOK son variantes de los algoritmos SCAN y LOOK, respectivamente; donde se limita a N el número de solicitudes que se atenderán en cada barrido del brazo del disco. Estos algoritmos funcionan de la siguiente manera:

Si en lugar de copiar N peticiones de la segunda a la primera cola, se copian todas las solicitudes pendientes, el algoritmo se denomina F-SCAN.

Estos algoritmos previenen un problema denominado rigidez del brazo —o arm stickiness, en inglés— a diferencia de los algoritmos SSTF, SCAN, C-SCAN, LOOK y C-LOOK, que no lo hacen. El término rigidez del brazo hace referencia a cuando hay un flujo continuo de solicitudes para el mismo cilindro, esto hace que con los algoritmos vistos hasta ahora, el brazo no avance por los cilindros hasta llegar al otro extremo. Como F-SCAN, N-Step-SCAN y N-Step-LOOK separan las solicitudes en dos colas —haciendo que las nuevas tengan que esperar— el brazo siempre continúa su barrido hacia el extremo del disco.

El planificador CFQ (Completely Fair Queuing) se diseñó para compartir de forma equitativa el ancho de banda entre todos los procesos que solicitan acceso al disco. Fue utilizado por defecto en muchas distribuciones de Linux hasta la versión 5.0 del núcleo y funciona de la siguiente manera: