Sistemas de archivos — ejercicios tipo examen con bloques, FAT, i-nodos y enlaces (y el atajo que apuntaba a la nada)

Respuesta: Un objeto con nombre que guarda información persistente, que sigue ahí después de apagar

Persistente significa no volátil, duradero: la información sobrevive a que se apague el ordenador. Lo demás son estructuras que el SO usa para gestionarlo.

• El usuario → Una estructura de datos duradera
• La interfaz de llamadas al sistema (Unix) → Una colección de bytes
• El núcleo del SO → Una colección de bloques

El usuario ve un documento; read() y write() ven bytes sin importarles qué significan; el núcleo lo guarda y lo lee por bloques (la unidad de transferencia, mayor que un sector).

Respuesta: El tamaño · Las fechas de creación y de modificación · La localización en el dispositivo · La información de protección (permisos)

Los atributos de los apuntes son nombre, tipo, localización, tamaño, protección, fechas y versión. Recuerda que esta pregunta penaliza: marcar un distractor resta.

• V — open() copia en memoria principal la información de control del archivo para no ir al directorio en cada operación.
• V — En Unix, el descriptor que devuelve open() es el índice de la entrada reservada en la tabla de archivos abiertos del proceso.
• F — Cada read() vuelve a buscar el nombre del archivo en el directorio del disco.
• F — close() borra el archivo del disco si nadie más lo tiene abierto.

Abrir sirve justo para no repetir la búsqueda: el directorio se consulta una vez y después se trabaja con la copia en RAM a través del descriptor.

close() solo libera los recursos que el archivo ocupaba en memoria; el archivo sigue en el disco.

Respuesta: Sigue existiendo, con sus atributos, pero con tamaño 0

Truncar: fuera el contenido, se quedan la entrada de directorio y los atributos (nombre, permisos, fechas…). Borrar se lo lleva todo.

En Windows el tipo se deduce de la extensión del nombre; en Unix el sistema operativo no reconoce tipos de archivo; aun así, todo SO tiene que entender al menos el formato del archivo ejecutable.

Windows mira las últimas letras del nombre; Unix trata el contenido como bytes sin más; y cualquier SO necesita reconocer los ejecutables para poder cargarlos y lanzarlos.

Respuesta: El módulo del sistema operativo que ofrece los servicios de archivos y directorios · La organización de la información que se crea en el disco para guardar archivos y directorios

Uno es software (el módulo del SO) y el otro es la estructura de datos que queda escrita en el dispositivo (por ejemplo, un disco formateado en ext4 o FAT32).

Respuesta: Secuencial

Es el modelo básico de Unix y Windows: open → read → read… La posición actual avanza sola.

Respuesta: lseek

lseek(fd, desplazamiento, SEEK_SET) mueve la posición; el siguiente read() empieza ahí, sin pasar por lo de antes.

• Secuencial → Una cinta que solo avanza o retrocede
• Directo → Un array de bloques al que saltas por posición
• Indexado (ISAM) → Una tabla ordenada que se consulta por una clave

En el indexado, el SO mantiene uno o varios archivos índice ocultos para buscar por clave (por ejemplo, un apellido). Hoy se hace fuera del núcleo, en las bases de datos.

Orden correcto:

1. Nivel único
2. Dos niveles
3. Árbol
4. Grafo acíclico
5. Grafo general

Cada modelo añade algo: separar usuarios (dos niveles), subdirectorios (árbol), compartir sin copiar (acíclico) y enlaces sin restricciones, con ciclos (general).

Respuesta: Nivel único

Es el más sencillo y el que peor escala: choques de nombres entre usuarios y búsquedas lentas cuando hay muchos archivos.

Respuesta: /home/laura/ic2/grupo/notas.txt

La ruta absoluta empieza en la raíz, que es la / inicial. No se escribe «/root/…»: root es otro directorio (el del administrador).

Respuesta: practica/Makefile

La relativa parte del directorio de trabajo, así que se quita el principio común (/home/sergio/ic2/) y no lleva / al principio.

• V — Con dos niveles, sergio y laura pueden tener cada uno un archivo practica.c.
• F — El modelo en árbol permite que un mismo archivo cuelgue de dos rutas distintas.
• V — En un grafo acíclico, las dos rutas llevan al mismo objeto, no a una copia.
• V — En un grafo general, un programa que recorre los directorios puede no terminar.

El árbol tiene justo esa desventaja: no permite compartir. El grafo acíclico lo resuelve con enlaces y el general admite enlaces a directorios de más arriba, que forman ciclos.

Respuesta: Los datos siguen accesibles por copia-laura.csv; el contador de enlaces del i-nodo baja de 2 a 1

Un enlace duro es otro nombre para el mismo i-nodo. Mientras quede algún nombre (contador > 0), los datos siguen ahí.

• ln -s apuntes.md atajo.md → Un enlace simbólico
• ln apuntes.md otro.md → Un enlace duro
• cp apuntes.md copia.md → Una copia independiente

La s de -s es de symbolic. Sin -s, ln crea otro nombre para el mismo i-nodo. cp duplica los datos: si cambias uno, el otro no cambia.

Respuesta: Permitir enlaces solo a archivos, no a directorios · Recolección de basura (de memoria) para lo que quede inalcanzable · Usar algoritmos que detecten ciclos al recorrer

Las tres son las soluciones de los apuntes. La primera es la que usa Unix con los enlaces duros: no se pueden hacer a directorios.

Respuesta: Montar el sistema de archivos del pendrive en el punto de montaje /media/usb

Antes de usar un sistema de archivos hay que montarlo: su árbol se cuelga de un directorio del árbol existente.

Respuesta: Listas de control de acceso (ACL) · Contraseñas · Cifrado

Una ACL es una lista de pares <usuario, permisos>. El cifrado protege incluso si alguien se lleva el disco físico.

Orden correcto:

1. Capa lógica
2. Capa de control de bloques
3. Capa de comandos básicos
4. Capa de driver

Lógica: directorios e i-nodos. Control de bloques: de bloque lógico a físico. Comandos básicos: leer y escribir bloques, búferes. Driver: hablar con el controlador e interrupciones.

• Contigua → El bloque inicial y la longitud
• Enlazada → El primer bloque (y a veces el último); los demás enlaces van dentro de los bloques
• Indexada → El número del bloque de índices

En la contigua basta con inicio + longitud porque los bloques van seguidos. En la enlazada, cada bloque dice cuál es el siguiente. En la indexada, todos los punteros están juntos en el bloque de índices.

Respuesta: Enlazada

El número del siguiente bloque estaba dentro del bloque dañado: la cadena se rompe ahí.

Respuesta: Indexada multinivel (punteros directos e indirectos simple, doble y triple)

Unix resolvió el límite del bloque de índices con varios niveles: unos punteros llevan a datos y otros a bloques de índices.

• V — La asignación contigua sufre fragmentación externa: puede haber sitio libre en total y no caber un archivo.
• F — La asignación enlazada sufre fragmentación externa.
• V — En la indexada, un archivo de un solo bloque de datos ocupa dos bloques.
• V — La FAT es una variante de la asignación enlazada.

En la práctica de IC2 del artículo, informe.pdf no cabía en contigua con 11 bloques libres porque el mayor hueco era de 4.

La enlazada y la indexada usan cualquier bloque libre, así que no tienen fragmentación externa (solo la interna del último bloque).

Respuesta: Los enlaces están juntos y se pueden guardar en caché o traer enteros a la RAM · Los bloques de datos no pierden bytes con el número del siguiente

La FAT saca los enlaces de los bloques y los reúne en una tabla al principio del disco: recorrer la cadena es mirar la tabla, no leer bloque a bloque.

En un mapa de bits hay un bit por bloque; en una lista enlazada cada bloque libre apunta al siguiente; y en un disco FAT la propia tabla marca los libres.

El mapa de bits es el del Unix tradicional. En la lista enlazada, el SO solo guarda un puntero al primer libre (o usa ese primer libre como bloque de índices con los demás).

Respuesta: 1024

En el bloque de índices caben 2048 / 4 = 512 punteros, así que el archivo tiene como mucho 512 bloques: 512 × 2 KiB = 1024 KiB (1 MiB).

Respuesta: El indirecto simple

Con 4 KiB y punteros de 4 B, un bloque de índices guarda 1024 punteros: el simple cubre 1024 bloques, del 12 al 1035.

Respuesta: 3

40 000 es mayor que 1035 y menor que 1 049 612: va por el indirecto doble. Lecturas: bloque de índices de arriba + bloque de índices de abajo + bloque de datos = 3.

• V — Una lista lineal de entradas es fácil de programar, pero muy lenta con miles de archivos.
• V — NTFS y ext4 usan árboles B (o variantes) para los directorios grandes.
• F — Con una tabla hash hay que comparar el nombre con todas las entradas.
• F — El directorio solo existe en RAM; en el disco solo están los datos.

La tabla hash calcula la casilla a partir del nombre y va directa. El directorio se guarda en el disco (en RAM, como mucho, una copia para ir más rápido).

Bloques = tamaño / espacio útil, redondeando hacia arriba. En contigua, FAT e indexada el bloque entero es para datos (2048 B); en la enlazada cada bloque pierde 4 B con el número del siguiente: útiles 2044 B.

notas.txt: 3000 / 2048 = 1,46 → 2 en todas (y 2 + 1 = 3 en la indexada).

grupo.c es la trampa: 6144 = 3 × 2048 cabe justo en 3 bloques, pero en la enlazada 3 × 2044 = 6132 < 6144: le faltan 12 bytes y necesita un cuarto bloque.

memoria.pdf: 9000 / 2048 = 4,39 → 5 y 9000 / 2044 = 4,40 → 5; en la indexada, 5 + 1 = 6.

Totales: 10, 11, 10 y 13. La indexada gasta un bloque de índices por archivo, aunque el archivo sea pequeño.

Contigua: el bloque k está en inicio + k; se calcula sin leer nada más: 1 lectura siempre.

Enlazada: el número del bloque k solo se conoce leyendo el bloque k − 1, y así hacia atrás: k + 1 lecturas (1, 4 y 5).

FAT en RAM: los saltos de la cadena se hacen en la tabla, en memoria, y luego se lee solo el bloque de datos: 1 lectura.

Indexada: primero el bloque de índices (su entrada k es la dirección) y después el bloque de datos: 2 lecturas para cualquier k.

Punteros por bloque de índices: 2048 / 4 = 512. Cada nivel multiplica por 512: 10, 512, 512² = 262 144 y 512³ = 134 217 728 bloques.

Acumulado (bloques × 2 KiB): 10 × 2 = 20 KiB; (10 + 512) × 2 = 1 044 KiB; (522 + 262 144) × 2 = 525 332 KiB; y con el triple, 134 480 394 bloques × 2 = 268 960 788 KiB.

En GiB: 268 960 788 / 1 048 576 = 256,5 GiB. Casi todo lo pone el triple: 512³ × 2 KiB = 2^27 × 2^11 B = 2^38 B = 256 GiB.

Con 4 KiB y punteros de 4 B caben 1024 punteros por bloque. Los directos llegan a los bloques 0-11, el simple a los 12-1035 y el doble a los 1036-1 049 611.

apuntes.md: 30 / 4 = 7,5 → 8 bloques: todos con punteros directos, 0 bloques de índices; el último (bloque 7) se lee con 1 lectura.

dataset.csv: 2 MiB / 4 KiB = 512 bloques: 12 directos + 500 por el simple → 1 bloque de índices. El último (511) cae en el simple: índice + datos = 2 lecturas.

grabacion.mp4: 100 MiB / 4 KiB = 25 600 bloques: 12 directos + 1024 del simple + 24 564 del doble. El doble gasta su bloque de arriba más ⌈24 564 / 1024⌉ = 24 bloques debajo: 1 + 1 + 24 = 26 bloques de índices. El último bloque se alcanza por el doble: 3 lecturas.

Todo en potencias de 2: 256 GiB = 2^38 B y 8 KiB = 2^13 B → 2^38 / 2^13 = 2^25 = 33 554 432 bloques.

Mapa de bits: un bit por bloque → 2^25 bits = 2^22 bytes = 4 MiB.

FAT: una entrada de 4 B (2^2) por bloque → 2^25 × 2^2 = 2^27 B = 128 MiB: 32 veces más que el mapa de bits.

Enlazada: útiles 1024 − 8 = 1016 B; 3 MiB = 3 145 728 B; 3 145 728 / 1016 = 3 096,19 → 3 097 bloques.

Con tres enlaces: útiles 1024 − 24 = 1000 B; 3 145 728 / 1000 = 3 145,728 → 3 146 bloques.

Respuesta modelo:

En la asignación contigua cada archivo ocupa bloques seguidos y el directorio solo guarda el bloque inicial y la longitud; el bloque k está en inicio + k, así que el acceso secuencial y el directo son muy rápidos, pero sufre fragmentación externa (puede no haber un hueco seguido aunque sobre espacio) y le cuesta que el archivo crezca.

En la enlazada los bloques pueden estar en cualquier sitio y cada uno guarda el número del siguiente; el directorio guarda el primero (y a veces el último). Desaparece la fragmentación externa, pero llegar al bloque k obliga a leer los k anteriores, cada bloque pierde unos bytes con el enlace y, si uno se daña, se pierde todo lo que viene detrás. La FAT es su variante con los enlaces reunidos en una tabla.

En la indexada todos los punteros del archivo están en un bloque de índices cuya dirección guarda el directorio; tampoco hay fragmentación externa y el acceso directo cuesta dos lecturas para cualquier bloque, a cambio de gastar un bloque extra por archivo (pesa en los pequeños) y de perderlo todo si se daña el bloque de índices.

Respuesta modelo:

Un enlace duro es otra entrada de directorio que apunta al mismo i-nodo que el original: no hay original y copia, sino dos nombres para el mismo archivo, y el i-nodo cuenta cuántos nombres tiene. Se crea con ln datos.csv copia.csv. Si se borra datos.csv, el contador baja de 2 a 1 y los datos siguen accesibles por copia.csv; solo se liberan cuando el contador llega a 0. Solo se puede hacer a archivos y dentro del mismo sistema de archivos.

Un enlace simbólico es un archivo pequeño que guarda la ruta del original, como un acceso directo de Windows. Se crea con ln -s datos.csv atajo.csv. Puede apuntar a directorios y a otros sistemas de archivos, pero si se borra el original queda colgando: apunta a una ruta que ya no existe.

Respuesta modelo:

El i-nodo guarda los atributos del archivo (modo, propietario, tamaño, fechas, contador de enlaces) y los punteros a sus bloques. Un único bloque de índices limitaría el tamaño del archivo a los punteros que caben en un bloque, así que Unix usa varios niveles: 12 punteros directos llevan a bloques de datos (los archivos pequeños no gastan bloques de índices), el indirecto simple lleva a un bloque de punteros, el doble a un bloque de bloques de punteros y el triple añade un nivel más.

Con bloques de 4096 bytes y punteros de 8 caben 4096 / 8 = 512 punteros por bloque. El máximo es (12 + 512 + 512² + 512³) bloques × 4 KiB = 48 KiB + 2 MiB + 1 GiB + 512 GiB, unos 513 GiB. Casi todo lo aporta el triple: 512³ × 4 KiB = 2^27 × 2^12 B = 2^39 B = 512 GiB.

Respuesta modelo:

Con un mapa de bits se reserva una zona fija del disco con un bit por bloque que dice si está libre u ocupado; es compacto y permite buscar huecos seguidos, y es el método del Unix tradicional.

Con una lista enlazada, el SO solo guarda el número del primer bloque libre y cada libre guarda el del siguiente; no gasta espacio extra, pero recorrerla obliga a leer bloques. Una variante usa el primer libre como bloque de índices con los números de los demás.

En los sistemas FAT no hace falta otra estructura: la entrada de un bloque libre en la FAT tiene un valor que lo marca como libre.

Cálculo: 64 GiB / 4 KiB = 2^36 / 2^12 = 2^24 bloques, así que el mapa tiene 2^24 bits = 2^21 bytes = 2 MiB.