Memoria y Sistemas de Archivos

3.1 ¿Por qué la memoria necesita un administrador?

En un sistema monoprogramado la cuestión sería trivial: un único programa ocupa la memoria y listo. Pero los sistemas operativos modernos son multiprogramados: mantienen varios procesos cargados a la vez para que, mientras uno espera una operación de entrada/salida, el procesador pueda dedicarse a otro. Esa convivencia obliga a subdividir la memoria principal y a repartirla con criterio.

El objetivo de fondo es mantener el procesador ocupado. Si la memoria estuviera mal administrada, el CPU pasaría buena parte del tiempo ocioso esperando a que los procesos terminen sus operaciones de E/S. La gestión de memoria es, entonces, lo que hace viable la multiprogramación.

Los cinco requisitos de la gestión de memoria

Stallings (2005) sistematiza cinco requisitos que todo administrador de memoria debe satisfacer. Conviene revisarlos uno por uno, porque cada técnica que veremos más adelante existe para cumplir alguno de ellos. Las tarjetas se dan vuelta al hacer clic.

Regla mnemotécnica: Re-Pro-Com-Log-Fis — Reubicación, Protección, Compartición, organización Lógica y organización Física.

3.2 Particionamiento de la memoria

Las técnicas históricas más simples para repartir la memoria son el particionamiento fijo y el dinámico. Hoy casi no se usan —se prefieren la paginación y la segmentación—, pero entenderlas es clave porque introducen el problema central de toda gestión de memoria: la fragmentación. Un detalle importante: en el particionamiento un proceso solo puede ocupar una partición (la técnica de overlays permite cargar módulos adicionales para superar ese límite), y todo el esquema trabaja con direcciones relativas.

3.3 Algoritmos de ubicación

En el particionamiento dinámico, cuando llega un proceso hay que decidir en qué hueco libre colocarlo. Existen tres estrategias clásicas, y la elección no es inocente: cada una deja la memoria en un estado distinto y afecta la fragmentación futura.

• Primer ajuste (first-fit): recorre desde el principio y usa el primer hueco lo bastante grande. Es rápido porque corta apenas encuentra uno.
• Mejor ajuste (best-fit): busca el hueco cuyo tamaño sea el más cercano al pedido. Suena ideal, pero tiende a dejar fragmentos diminutos e inservibles.
• Siguiente ajuste (next-fit): como el primer ajuste, pero retoma la búsqueda desde la última posición asignada en lugar de volver al principio.

3.4 El sistema buddy (de "compañeros")

El sistema buddy es un punto medio elegante entre el particionamiento fijo y el dinámico. La memoria se administra en bloques cuyo tamaño es siempre una potencia de dos. Cuando llega un pedido, se toma el bloque más chico que lo contenga; si es demasiado grande, se parte por la mitad repetidamente —generando pares de "compañeros" (buddies)— hasta llegar al tamaño justo. Al liberar memoria, si los dos compañeros quedan libres, se fusionan de nuevo. Esto hace que asignar y liberar sea muy rápido. Una versión modificada se usa para administrar la memoria del núcleo en UNIX.

3.5 Reubicación y los tres tipos de dirección

Un proceso no siempre vive en el mismo lugar de la memoria: el intercambio (swap) a disco y la compactación pueden moverlo. Por eso el sistema necesita un mecanismo de reubicación. Para entenderlo hay que distinguir tres tipos de dirección, que el hardware traduce en tiempo de ejecución:

La traducción de dirección lógica a física requiere soporte de hardware especial (un registro base que se suma a la dirección relativa, y un registro límite que verifica que no se salga de la partición). Gracias a esto, mover un proceso solo implica cambiar el registro base.

3.6 Paginación

La paginación es la versión mejorada del particionamiento fijo, y resuelve la fragmentación de raíz. La idea: dividir tanto la memoria como los procesos en unidades de tamaño fijo. A las porciones de la memoria física se las llama marcos (frames); a las porciones del proceso, páginas. Como cualquier página entra en cualquier marco, desaparece la fragmentación externa y la interna se reduce a, como mucho, una fracción de la última página.

Cada proceso tiene su tabla de páginas, que indica en qué marco está alojada cada una de sus páginas. El sistema operativo mantiene además una lista de marcos libres. La dirección lógica se parte en dos campos: un número de página y un desplazamiento dentro de ella. El hardware usa el número de página para buscar el marco en la tabla, y conserva el desplazamiento tal cual.

3.7 Segmentación

Si la paginación mejora el particionamiento fijo, la segmentación mejora el dinámico. Aquí el programa se divide en segmentos de tamaño variable que responden a criterios lógicos: un segmento para el código, otro para la pila, otro para una tabla de datos. La dirección lógica lleva un número de segmento y un desplazamiento.

La gran diferencia con el particionamiento dinámico es que los segmentos no necesitan ser contiguos. La tabla de segmentos guarda, para cada uno, su dirección inicial (base) y su longitud (límite). Traducir implica: verificar que el desplazamiento no supere la longitud del segmento, y luego sumar la base. A diferencia de la paginación, la segmentación es visible para el programador, que puede aprovecharla para organizar el programa de forma modular.

Ambos enfoques pueden combinarse (segmentación paginada) para tomar lo mejor de cada uno: la modularidad lógica de los segmentos y la ausencia de fragmentación externa de las páginas.

3.8 Memoria virtual (Fotheringham, 1961)

La memoria virtual da a cada programa su propio espacio de direcciones virtuales, dividido en páginas. La clave es que esas páginas no necesitan estar todas en la memoria física para poder ejecutar el programa. Solo se cargan las que hacen falta en cada momento; el resto vive en el área de swap del disco.

Cuando el programa accede a una dirección cuya página está en RAM, el hardware hace la traducción al instante. Pero si la página no está presente, se dispara un fallo de página: el sistema operativo recibe la alerta, busca la página faltante en el swap, la carga en un marco libre y reanuda la instrucción. Este mecanismo encaja perfecto con la multiprogramación: mientras un proceso espera que su página llegue del disco, el CPU se dedica a otro.

El componente de hardware que realiza la traducción es la MMU (Unidad de Administración de Memoria). El flujo de un acceso es el siguiente:

3.9 La tabla de páginas por dentro

Cada entrada de la tabla de páginas guarda mucho más que el número de marco. Estos campos son los que permiten que la memoria virtual funcione de forma segura y eficiente. Al hacer clic en cada bit se explica su rol.

Estructuras que aceleran u optimizan la paginación

3.10 Algoritmos de reemplazo de páginas

Cuando ocurre un fallo de página y no hay marcos libres, el sistema operativo debe elegir una página que esté en memoria y desalojarla para hacer lugar. La pregunta del millón es cuál. Una mala elección puede provocar que la página recién expulsada se necesite enseguida (un fenómeno conocido como hiperpaginación o thrashing). Estos son los algoritmos clásicos, ordenados de ideal a práctico:

4.1 ¿Por qué existen los archivos?

La memoria principal tiene tres limitaciones fatales para guardar información a largo plazo: es pequeña (el tamaño del espacio de direcciones la acota), es volátil (al terminar el proceso, su información se pierde) y no permite que varios procesos compartan datos persistentes con facilidad. De ahí surgen tres requerimientos que todo sistema de almacenamiento permanente debe cumplir:

Para el usuario, lo importante de un archivo es su apariencia: cómo se llama, de qué se compone, cómo se protege y qué operaciones admite. Un par de detalles que suelen confundir: UNIX distingue mayúsculas y minúsculas en los nombres, MS-DOS no. Un archivo puede tener varias extensiones (pagina.html.zip), y esas extensiones son meras convenciones: indican algo sobre la naturaleza del archivo, pero el SO no las impone. Todo archivo lleva además atributos o metadatos: fecha de última modificación, tamaño, permisos, etc.

4.2 Cómo se estructuran los archivos

Hay tres maneras de organizar internamente un archivo, y la elección define cuánto "entiende" el SO de su contenido:

Tipos de archivos

Windows maneja archivos y directorios regulares. UNIX agrega dos tipos especiales, fiel a su filosofía de "todo es un archivo":

Históricamente, las cintas magnéticas solo permitían acceso secuencial. Con la llegada de los discos duros apareció el acceso aleatorio: poder saltar directamente a cualquier registro mediante su llave, sin leer todo lo anterior.

4.3 Operaciones sobre archivos

El sistema operativo expone once operaciones básicas sobre archivos, accesibles mediante llamadas al sistema:

4.4 Directorios y rutas

Hay dos formas de organizar los directorios. La primera —un único directorio que contiene todos los archivos— se usaba antiguamente y se vuelve inmanejable apenas hay muchos archivos. La que se impuso es la jerarquía de directorios: un directorio raíz del que cuelgan los directorios de cada usuario, sus subdirectorios y archivos, formando un árbol.

Para nombrar un archivo dentro del árbol hay dos clases de ruta. Las rutas absolutas parten siempre del directorio raíz y son únicas; el separador cambia según el sistema: UNIX usa /, Windows \ y MULTICS >. Las rutas relativas parten del directorio actual de trabajo. En ellas, . referencia el directorio actual y .. el directorio padre (salvo en la raíz, donde apunta a sí misma).

4.5 Operaciones sobre directorios (UNIX)

UNIX define ocho operaciones de directorio. Dos merecen una nota: readdir devuelve la siguiente entrada de un directorio abierto, y link permite vincular un mismo archivo a más de un directorio (la base de los enlaces duros y de los archivos compartidos).

4.6 Implementación de archivos: ¿cómo se guardan en el disco?

El disco se divide en particiones, cada una con su propio sistema de archivos. Al arrancar (o al montar la partición por primera vez) se lee el superbloque, que contiene los parámetros clave del sistema de archivos. La gran pregunta de diseño es: ¿cómo se lleva el registro de qué bloques del disco pertenecen a cada archivo? Hay cuatro estrategias clásicas, cada una con un balance distinto entre simplicidad, velocidad de acceso secuencial y velocidad de acceso aleatorio.

4.7 El nodo-i por dentro

El inodo merece su propia sección porque es la estructura que sostiene a UNIX y Linux. La idea ingeniosa está en cómo maneja archivos grandes sin desperdiciar espacio en los chicos: guarda unas pocas direcciones directas a bloques, y reserva las últimas para direcciones indirectas, que apuntan a bloques que a su vez contienen más direcciones. Así, un archivo pequeño usa solo punteros directos, mientras que uno enorme se expande a través de la indirección. Hacé clic en cada parte del inodo.

Implementación de directorios

Un directorio es, internamente, una tabla que asocia nombres con la ubicación de los archivos. Hay dos enfoques:

Archivos compartidos: un mismo archivo puede aparecer en varios directorios. Se logra con una estructura dedicada: un inodo compartido (enlace duro) o un archivo de tipo LINK (enlace simbólico).

4.8 Sistemas de archivos avanzados

Con discos cada vez más lentos en comparación con CPU y RAM, las escrituras de trozos pequeños se volvieron un cuello de botella. De ahí surgieron diseños más sofisticados:

Por eso en Linux "no existen las unidades C: o D:": todos los discos se montan dentro del mismo árbol de directorios, y se accede a ellos por igual aunque tengan sistemas de archivos distintos.

4.9 Administración del espacio en disco

Casi todos los sistemas dividen los archivos en bloques de tamaño fijo que no necesitan ser adyacentes —mover un bloque suelto es más barato que reubicar el archivo entero—. La elección del tamaño de bloque es un compromiso clásico:

Registro de bloques libres

El sistema necesita saber qué bloques están libres. Hay dos métodos, y el laboratorio permite compararlos lado a lado:

4.10 Cuotas y respaldos

Cuotas de disco

El administrador puede limitar cuántos archivos y bloques puede tener cada usuario. Se manejan dos umbrales: el límite suave, que se puede exceder temporalmente (con advertencias), y el límite duro, que no se puede sobrepasar bajo ninguna circunstancia.

Respaldos (backups)

Perder un sistema de archivos es peor que perder la computadora: el hardware se reemplaza, la información no. Por eso los respaldos son críticos. Algunas buenas prácticas: respaldar directorios específicos en lugar de todo el sistema, omitir los archivos que no cambiaron desde el último respaldo (respaldo incremental), y —según Tanenbaum— evitar comprimir los respaldos, porque un solo error en el medio puede arruinar todo el archivo comprimido. Hutchinson y colaboradores (1999) propusieron tomar instantáneas rápidas copiando estructuras críticas y aplicando copy-on-write a los cambios posteriores.

Hay dos estrategias para volcar (respaldar) un disco:

4.11 Consistencia del sistema de archivos

Una caída en medio de la escritura de un bloque puede dejar el sistema de archivos en un estado inconsistente. Para detectarlo y repararlo, UNIX tiene fsck y Windows tiene scandisk. La verificación trabaja en dos frentes: los bloques y los directorios.

Verificación de bloques

El programa arma dos tablas de contadores, una por bloque del disco. La primera cuenta cuántas veces aparece cada bloque en uso (referenciado por algún inodo); la segunda, cuántas veces aparece en la lista de bloques libres. La regla de oro: cada bloque debe aparecer exactamente una vez, en una sola de las dos tablas. Si aparece en ambas, o en ninguna, hay un problema.

Verificación de directorios

Se usa una tabla que cuenta, por archivo, en cuántos directorios aparece, y se compara con la cuenta de vínculos almacenada en su inodo. Dos errores posibles: si la cuenta del inodo es mayor que las entradas reales, el archivo queda "huérfano" y desperdicia espacio; si es menor, es peligroso, porque al borrar un enlace el archivo podría eliminarse aunque todavía esté referenciado en otro lado. La solución es ajustar las cuentas para que coincidan. fsck también detecta inodos inválidos, permisos riesgosos y archivos con bit SETUID sospechoso.

4.12 Rendimiento y desfragmentación

Varias técnicas mejoran el rendimiento del sistema de archivos. Bloques más grandes favorecen la lectura secuencial. Los sistemas con inodos pagan un costo —dos accesos, uno al inodo y otro al bloque—, que se mitiga colocando los inodos a la mitad del disco (reduce a la mitad la distancia de búsqueda) o dividiendo el disco en grupos de cilindros, cada uno con sus propios inodos y bloques libres (McKusick y col., 1984). También ayudan los cachés y la lectura adelantada.

Con el uso, crear y borrar archivos va dejando el disco fragmentado: archivos y huecos esparcidos por todas partes, lo que degrada el rendimiento. La desfragmentación reordena los archivos para hacerlos contiguos y juntar el espacio libre. En Windows se usa defrag. Algunos archivos no se mueven (paginación, hibernación, bitácora). Linux, con ext2/ext3, sufre mucha menos fragmentación gracias a cómo elige los bloques.

4.13 Síntesis de la unidad