4_a_Administración de sistemas de Archivos (1).pdf

4 SISTEMAS DE ARCHIVOS Todas las aplicaciones de computadora requieren almacenar y recuperar información. Mientras un proceso está en ejecución, puede almacenar una cantidad limitada de información dentro de su pro- pio espacio de direcciones. Sin embargo, la capacidad de almacenami...

4 SISTEMAS DE ARCHIVOS Todas las aplicaciones de computadora requieren almacenar y recuperar información. Mientras un proceso está en ejecución, puede almacenar una cantidad limitada de información dentro de su pro- pio espacio de direcciones. Sin embargo, la capacidad de almacenamiento está restringida por el ta- maño del espacio de direcciones virtuales. Para algunas aplicaciones este tamaño es adecuado; para otras, tales como las de reservaciones en aerolíneas, las bancarias o las de contabilidad corporativa, puede ser demasiado pequeño. Un segundo problema relacionado con el mantenimiento de la información dentro del espacio de direcciones de un proceso es que cuando el proceso termina, la información se pierde. Para muchas aplicaciones (por ejemplo, una base de datos) la información se debe retener durante semanas, meses o incluso indefinidamente. Es inaceptable que esta información se desvanezca cuando el proceso que la utiliza termine. Además, no debe desaparecer si una falla en la computadora acaba con el proceso. Un tercer problema es que frecuentemente es necesario que varios procesos accedan a (partes de) la información al mismo tiempo. Si tenemos un directorio telefónico en línea almacenado dentro del es- pacio de direcciones de un solo proceso, sólo ese proceso puede tener acceso al directorio. La manera de resolver este problema es hacer que la información en sí sea independiente de cualquier proceso. En consecuencia, tenemos tres requerimientos esenciales para el almacenamiento de informa- ción a largo plazo: 1. Debe ser posible almacenar una cantidad muy grande de información. 2. La información debe sobrevivir a la terminación del proceso que la utilice. 3. Múltiples procesos deben ser capaces de acceder a la información concurrentemente. 255 www.FreeLibros.me 256 SISTEMAS DE ARCHIVOS CAPÍTULO 4 Durante muchos años se han utilizado discos magnéticos para este almacenamiento de largo plazo, así como cintas y discos ópticos, aunque con un rendimiento mucho menor. En el capítulo 5 estu- diaremos más sobre los discos, pero por el momento basta con pensar en un disco como una secuen- cia lineal de bloques de tamaño fijo que admite dos operaciones: 1. Leer el bloque k. 2. Escribir el bloque k. En realidad hay más, pero con estas dos operaciones podríamos (en principio) resolver el problema del almacenamiento a largo plazo. Sin embargo, éstas son operaciones muy inconvenientes, en especial en sistemas extensos uti- lizados por muchas aplicaciones y tal vez varios usuarios (por ejemplo, en un servidor). Unas cuan- tas de las preguntas que surgen rápidamente son: 1. ¿Cómo encontramos la información? 2. ¿Cómo evitamos que un usuario lea los datos de otro usuario? 3. ¿Cómo sabemos cuáles bloques están libres? y hay muchas más. Así como vimos la manera en que el sistema operativo abstrajo el concepto del procesador pa- ra crear la abstracción de un proceso y el concepto de la memoria física para ofrecer a los procesos espacios de direcciones (virtuales), podemos resolver este problema con una nueva abstracción: el archivo. En conjunto, las abstracciones de los procesos (e hilos), espacios de direcciones y archivos son los conceptos más importantes en relación con los sistemas operativos. Si realmente compren- de estos tres conceptos de principio a fin, estará preparado para convertirse en un experto en siste- mas operativos. Los archivos son unidades lógicas de información creada por los procesos. En general, un dis- co contiene miles o incluso millones de archivos independientes. De hecho, si concibe a cada archi- vo como un tipo de espacio de direcciones, no estará tan alejado de la verdad, excepto porque se utilizan para modelar el disco en vez de modelar la RAM. Los procesos pueden leer los archivos existentes y crear otros si es necesario. La información que se almacena en los archivos debe ser persistente, es decir, no debe ser afectada por la creación y ter- minación de los procesos. Un archivo debe desaparecer sólo cuando su propietario lo remueve de ma- nera explícita. Aunque las operaciones para leer y escribir en archivos son las más comunes, existen muchas otras, algunas de las cuales examinaremos a continuación. Los archivos son administrados por el sistema operativo. La manera en que se estructuran, de- nominan, abren, utilizan, protegen, implementan y administran son tópicos fundamentales en el di- seño de sistemas operativos. La parte del sistema operativo que trata con los archivos se conoce como sistema de archivos y es el tema de este capítulo. Desde el punto de vista del usuario, el aspecto más importante de un sistema de archivos es su apariencia; es decir, qué constituye un archivo, cómo se denominan y protegen los archivos qué operaciones se permiten con ellos, etcétera. Los detalles acerca de si se utilizan listas enlazadas (li- gadas) o mapas de bits para llevar la cuenta del almacenamiento libre y cuántos sectores hay en un bloque de disco lógico no son de interés, aunque sí de gran importancia para los diseñadores del sis- www.FreeLibros.me SECCIÓN 4.1 ARCHIVOS 257 tema de archivos. Por esta razón hemos estructurado el capítulo en varias secciones: las primeras dos están relacionadas con la interfaz del usuario para los archivos y directorios, respectivamente; después incluimos un análisis detallado acerca de cómo se implementa y administra el sistema de archivos; por último, daremos algunos ejemplos de sistemas de archivos reales. 4.1 ARCHIVOS En las siguientes páginas analizaremos los archivos desde el punto de vista del usuario; es decir, có- mo se utilizan y qué propiedades tienen. 4.1.1 Nomenclatura de archivos Los archivos son un mecanismo de abstracción. Proporcionan una manera de almacenar informa- ción en el disco y leerla después. Esto se debe hacer de tal forma que se proteja al usuario de los detalles acerca de cómo y dónde se almacena la información y cómo funcionan los discos en rea- lidad. Probablemente, la característica más importante de cualquier mecanismo de abstracción sea la manera en que los objetos administrados son denominados, por lo que empezaremos nuestro exa- men de los sistemas de archivos con el tema de la nomenclatura de los archivos. Cuando un proce- so crea un archivo le proporciona un nombre. Cuando el proceso termina, el archivo continúa existiendo y puede ser utilizado por otros procesos mediante su nombre. Las reglas exactas para denominar archivos varían un poco de un sistema a otro, pero todos los sistemas operativos actuales permiten cadenas de una a ocho letras como nombres de archivos le- gales. Por ende, andrea, bruce y cathy son posibles nombres de archivos. Con frecuencia también se permiten dígitos y caracteres especiales, por lo que nombres como 2, urgente! y Fig.2-14 son a menudo válidos también. Muchos sistemas de archivos admiten nombres de hasta 255 caracteres. Algunos sistemas de archivos diferencian las letras mayúsculas de las minúsculas, mientras que otros no. UNIX cae en la primera categoría; MS-DOS en la segunda. Así, un sistema UNIX puede tener los siguientes nombres como tres archivos distintos: maria, Maria y MARIA. En MS-DOS, to- dos estos nombres se refieren al mismo archivo. Tal vez sea adecuado hacer en este momento un paréntesis sobre sistemas de archivos. Win- dows 95 y Windows 98 utilizan el sistema de archivos de MS-DOS conocido como FAT-16 y por ende heredan muchas de sus propiedades, como la forma en que se construyen sus nombres. Win- dows 98 introdujo algunas extensiones a FAT-16, lo cual condujo a FAT-32, pero estos dos sistemas son bastante similares. Además, Windows NT, Windows 2000, Windows XP y.WV admiten ambos sistemas de archivos FAT, que en realidad ya son obsoletos. Estos cuatro sistemas operativos basa- dos en NT tienen un sistema de archivos nativo (NTFS) con diferentes propiedades (como los nom- bres de archivos en Unicode). En este capítulo, cuando hagamos referencia a los sistemas de archivos MS-DOS o FAT, estaremos hablando de FAT-16 y FAT-32 como se utilizan en Windows, a menos que se especifique lo contrario. Más adelante en este capítulo analizaremos los sistemas de archivos FAT y en el capítulo 11 examinaremos el sistema de archivos NTFS, donde analizaremos Windows Vista con detalle. www.FreeLibros.me 258 SISTEMAS DE ARCHIVOS CAPÍTULO 4 Muchos sistemas operativos aceptan nombres de archivos en dos partes, separadas por un pun- to, como en prog.c. La parte que va después del punto se conoce como la extensión del archivo y por lo general indica algo acerca de su naturaleza. Por ejemplo, en MS-DOS, los nombres de archi- vos son de 1 a 8 caracteres, más una extensión opcional de 1 a 3 caracteres. En UNIX el tamaño de la extensión (si la hay) es a elección del usuario y un archivo puede incluso tener dos o más exten- siones, como en paginainicio.html.zip, donde.html indica una página Web en HTML y.zip indica que el archivo se ha comprimido mediante el programa zip. Algunas de las extensiones de archivos más comunes y sus significados se muestran en la figura 4-1. Extensión Significado archivo.bak Archivo de respaldo archivo.c Programa fuente en C archivo.gif Imagen en Formato de Intercambio de Gráficos de CompuServe archivo.hlp Archivo de ayuda archivo.html Documento en el Lenguaje de Marcación de Hipertexto de World Wide Web archivo.jpg Imagen fija codificada con el estándar JPEG archivo.mp3 Música codificada en formato de audio MPEG capa 3 archivo.mpg Película codificada con el estándar MPEG archivo.o Archivo objeto (producido por el compilador, no se ha enlazado todavía) archivo.pdf Archivo en Formato de Documento Portable archivo.ps Archivo de PostScript archivo.tex Entrada para el programa formateador TEX archivo.txt Archivo de texto general archivo.zip Archivo comprimido Figura 4-1. Algunas extensiones de archivos comunes. En algunos sistemas (como UNIX) las extensiones de archivo son sólo convenciones y no son impuestas por los sistemas operativos. Un archivo llamado archivo.txt podría ser algún tipo de ar- chivo de texto, pero ese nombre es más un recordatorio para el propietario que un medio para trans- portar información a la computadora. Por otro lado, un compilador de C podría insistir que los archivos que va a compilar terminen con.c y podría rehusarse a compilarlos si no tienen esa termi- nación. Las convenciones como ésta son especialmente útiles cuando el mismo programa puede mane- jar diferentes tipos de archivos. Por ejemplo, el compilador C puede recibir una lista de varios ar- chivos para compilarlos y enlazarlos, algunos de ellos archivos de C y otros archivos de lenguaje ensamblador. Entonces, la extensión se vuelve esencial para que el compilador sepa cuáles son ar- chivos de C, cuáles son archivos de lenguaje ensamblador y cuáles son archivos de otro tipo. Por el contrario, Windows está consciente de las extensiones y les asigna significado. Los usua- rios (o procesos) pueden registrar extensiones con el sistema operativo y especificar para cada una cuál programa “posee” esa extensión. Cuando un usuario hace doble clic sobre un nombre de archi- vo, el programa asignado a su extensión de archivo se inicia con el archivo como parámetro. Por www.FreeLibros.me SECCIÓN 4.1 ARCHIVOS 259 ejemplo, al hacer doble clic en archivo.doc se inicia Microsoft Word con archivo.doc como el ar- chivo inicial a editar. 4.1.2 Estructura de archivos Los archivos se pueden estructurar en una de varias formas. Tres posibilidades comunes se descri- ben en la figura 4-2. El archivo en la figura 4-2(a) es una secuencia de bytes sin estructura: el sis- tema operativo no sabe, ni le importa, qué hay en el archivo. Todo lo que ve son bytes. Cualquier significado debe ser impuesto por los programas a nivel usuario. Tanto UNIX como Windows uti- lizan esta metodología. 1 Byte 1 Registro Hormiga Zorro Cerdo Gato Vaca Perro Cabra León Búho Pony Rata Gusano Gallina Ibis Cordero (a) (b) (c) Figura 4-2. Tres tipos de archivos. (a) Secuencia de bytes. (b) Secuencia de registros. (c) Árbol. Hacer que el sistema operativo considere los archivos sólo como secuencias de bytes provee la máxima flexibilidad. Los programas de usuario pueden colocar cualquier cosa que quieran en sus archivos y denominarlos de cualquier manera conveniente. El sistema operativo no ayuda, pero tampoco estorba. Para los usuarios que desean realizar cosas inusuales, esto último puede ser muy importante. Todas las versiones de UNIX, MS-DOS y Windows utilizan este modelo de archivos. La primera configuración en la estructura se muestra en la figura 4-2(b). En este modelo, un ar- chivo es una secuencia de registros de longitud fija, cada uno con cierta estructura interna. El con- cepto central para la idea de que un archivo sea una secuencia de registros es la idea de que la operación de lectura devuelva un registro y la operación de escritura sobrescriba o agregue un re- gistro. Como nota histórica, hace algunas décadas, cuando reinaba la tarjeta perforada de 80 colum- nas, muchos sistemas operativos de mainframes basaban sus sistemas de archivos en archivos consistentes de registros de 80 caracteres; es decir, en imágenes de la tarjeta. Estos sistemas tam- bién admitían archivos con registros de 132 caracteres, que fueron destinados para la impresora de www.FreeLibros.me 260 SISTEMAS DE ARCHIVOS CAPÍTULO 4 línea (que en esos días eran grandes impresoras de cadena con 132 columnas). Los programas leían la entrada en unidades de 80 caracteres y la escribían en unidades de 132 caracteres, aunque los úl- timos 52 podían ser espacios, desde luego. Ningún sistema de propósito general de la actualidad uti- liza ya este modelo como su sistema de archivos primario, pero en aquellos días de las tarjetas perforadas de 80 columnas y del papel de impresora de línea de 132 caracteres, éste era un modelo común en las computadoras mainframe. El tercer tipo de estructura de archivo se muestra en la figura 4-2(c). En esta organización, un archivo consiste de un árbol de registros, donde no todos son necesariamente de la misma longitud; cada uno de ellos contiene un campo llave en una posición fija dentro del registro. El árbol se or- dena con base en el campo llave para permitir una búsqueda rápida por una llave específica. La operación básica aquí no es obtener el “siguiente” registro, aunque eso también es posible, sino obtener el registro con una llave específica. Para el archivo del zoológico de la figura 4-2(c), podríamos pedir al sistema que, por ejemplo, obtenga el registro cuya llave sea pony, sin preocu- parnos acerca de su posición exacta en el archivo. Además, se pueden agregar nuevos registros al archivo, con el sistema operativo, y no el usuario, decidiendo dónde colocarlos. Evidentemente, es- te tipo de archivos es bastante distinto de los flujos de bytes sin estructura que se usan en UNIX y Windows, pero se utiliza de manera amplia en las grandes computadoras mainframe que aún se emplean en algún procesamiento de datos comerciales. 4.1.3 Tipos de archivos Muchos sistemas operativos soportan varios tipos de archivos. Por ejemplo, UNIX y Windows tie- nen archivos y directorios regulares. UNIX también tiene archivos especiales de caracteres y de blo- ques. Los archivos regulares son los que contienen información del usuario. Todos los archivos de la figura 4-2 son archivos regulares. Los directorios son sistemas de archivos para mantener la estructura del sistema de archivos. Estudiaremos los directorios un poco más adelante. Los archi- vos especiales de caracteres se relacionan con la entrada/salida y se utilizan para modelar dispo- sitivos de E/S en serie, tales como terminales, impresoras y redes. Los archivos especiales de bloques se utilizan para modelar discos. En este capítulo estaremos interesados principalmente en los archivos regulares. Por lo general, los archivos regulares son archivos ASCII o binarios. Los archivos ASCII con- sisten en líneas de texto. En algunos sistemas, cada línea se termina con un carácter de retorno de carro. En otros se utiliza el carácter de avance de línea. Algunos sistemas (por ejemplo, MS-DOS) utilizan ambos. No todas las líneas necesitan ser de la misma longitud. La gran ventaja de los archivos ASCII es que se pueden mostrar e imprimir como están, y se pueden editar con cualquier editor de texto. Además, si muchos programas utilizan archivos ASCII para entrada y salida, es fácil conectar la salida de un programa con la entrada de otro, como en las canalizaciones de shell. (La plomería entre procesos no es más fácil, pero la interpretación de la in- formación lo es si una convención estándar, tal como ASCII, se utiliza para expresarla). Otros archivos son binarios, lo cual sólo significa que no son archivos ASCII. Al listarlos en la impresora aparece un listado incomprensible de caracteres. Por lo general tienen cierta estructura interna conocida para los programas que los utilizan. www.FreeLibros.me SECCIÓN 4.1 ARCHIVOS 261 Por ejemplo, en la figura 4-3(a) vemos un archivo binario ejecutable simple tomado de una de las primeras versiones de UNIX. Aunque técnicamente el archivo es sólo una secuencia de bytes, el sistema operativo sólo ejecutará un archivo si tiene el formato apropiado. Este archivo tiene cin- co secciones: encabezado, texto, datos, bits de reubicación y tabla de símbolos. El encabezado em- pieza con un supuesto número mágico, que identifica al archivo como un archivo ejecutable (para evitar la ejecución accidental de un archivo que no tenga este formato). Después vienen los tama- ños de las diversas partes del archivo, la dirección en la que empieza la ejecución y algunos bits de bandera. Después del encabezado están el texto y los datos del programa en sí. Éstos se cargan en memoria y se reubican usando los bits de reubicación. La tabla de símbolos se utiliza para depurar. Nombre del Número mágico módulo Encabezado Tamaño del texto Tamaño de los datos Encabezado Datos Tamaño del BSS Tamaño de la tabla Módulo Propietario de símbolos objeto Protección Punto de entrada Tamaño Banderas Encabezado Texto Módulo objeto Datos Encabezado Bits de reubicación Módulo objeto Tabla de símbolos (a) (b) Figura 4-3. (a) Un archivo ejecutable. (b) Un archivo. Nuestro segundo ejemplo de un archivo binario es un archivo, también de UNIX. Consiste en una colección de procedimientos (módulos) de biblioteca compilados, pero no enlazados. A cada uno se le antepone un encabezado que indica su nombre, fecha de creación, propietario, código de www.FreeLibros.me 262 SISTEMAS DE ARCHIVOS CAPÍTULO 4 protección y tamaño. Al igual que en el caso del archivo ejecutable, los encabezados de los módu- los están llenos de números binarios. Al copiarlos a la impresora se produciría basura como salida. Cada sistema operativo debe reconocer por lo menos un tipo de archivo —su propio archivo ejecutable— y algunos reconocen más. El antiguo sistema TOPS-20 (para el DECsystem 20) hacía algo más, ya que examinaba la hora de creación de cualquier archivo a ejecutar. Después localiza- ba el archivo de código fuente y veía si éste se había modificado desde la última vez que se creó el binario. Si así era, recompilaba automáticamente el código fuente. En términos de UNIX, el pro- grama make había sido integrado al shell. Las extensiones de archivo eran obligatorias, por lo que el sistema operativo podía saber cuál programa binario se derivaba de cuál fuente. Tener archivos fuertemente tipificados como éstos ocasiona problemas cada vez que el usuario hace algo que los diseñadores del sistema no esperaban. Por ejemplo, considere un sistema en el que los archivos de salida de un programa tienen la extensión.dat (archivos de datos). Si un usuario es- cribe un programa formateador que lea un archivo.c (programa de C), lo transforma (por ejemplo, convirtiéndolo a un esquema de sangría estándar) y después escribe el archivo transformado como salida, el archivo de salida será de tipo.dat. Si el usuario trata de ofrecer esto al compilador de C pa- ra que lo compile, el sistema se rehusará debido a que tienen la extensión incorrecta. Los intentos de copiar archivo.dat a archivo.c serán rechazados por el sistema como inválidos (para proteger al usua- rio contra los errores). Mientras que este tipo de “amabilidad con el usuario” puede ayudar a los novatos, vuelve lo- cos a los usuarios experimentados debido a que tienen que dedicar un esfuerzo considerable para sortear la idea del sistema operativo en cuanto a lo que es razonable y lo que no. 4.1.4 Acceso a archivos Los primeros sistemas operativos proporcionaban sólo un tipo de acceso: acceso secuencial. En es- tos sistemas, un proceso podía leer todos los bytes o registros en un archivo en orden, empezando desde el principio, pero no podía saltar algunos y leerlos fuera de orden. Sin embargo, los archivos secuenciales podían rebobinarse para poder leerlos todas las veces que fuera necesario. Los archi- vos secuenciales eran convenientes cuando el medio de almacenamiento era cinta magnética en vez de disco. Cuando se empezó a usar discos para almacenar archivos, se hizo posible leer los bytes o re- gistros de un archivo fuera de orden, pudiendo acceder a los registros por llave en vez de posición. Los archivos cuyos bytes o registros se pueden leer en cualquier orden se llaman archivos de ac- ceso aleatorio. Son requeridos por muchas aplicaciones. Los archivos de acceso aleatorio son esenciales para muchas aplicaciones, como los sistemas de bases de datos. Si el cliente de una aerolínea llama y desea reservar un asiento en un vuelo es- pecífico, el programa de reservación debe poder tener acceso al registro para ese vuelo sin tener que leer primero los miles de registros de otros vuelos. Es posible utilizar dos métodos para especificar dónde se debe empezar a leer. En el primero, cada operación read da la posición en el archivo en la que se va a empezar a leer. En el segundo se provee una operación especial (seek) para establecer la posición actual. Después de una operación seek, el archivo se puede leer de manera secuencial desde la posición actual. Este último método se utiliza en UNIX y Windows. www.FreeLibros.me SECCIÓN 4.1 ARCHIVOS 263 4.1.5 Atributos de archivos Todo archivo tiene un nombre y sus datos. Además, todos los sistemas operativos asocian otra in- formación con cada archivo; por ejemplo, la fecha y hora de la última modificación del archivo y su tamaño. A estos elementos adicionales les llamaremos atributos del archivo. Algunas personas los llaman metadatos. La lista de atributos varía considerablemente de un sistema a otro. La tabla de la figura 4-4 muestra algunas de las posibilidades, pero existen otras. Ningún sistema existente tiene todos, pero cada uno de ellos está presente en algún sistema. Atributo Significado Protección Quién puede acceso al archivo y en qué forma Contraseña Contraseña necesaria para acceder al archivo Creador ID de la persona que creó el archivo Propietario El propietario actual Bandera de sólo lectura 0 para lectura/escritura; 1 para sólo lectura Bandera oculto 0 para normal; 1 para que no aparezca en los listados Bandera del sistema 0 para archivos normales; 1 para archivo del sistema Bandera de archivo 0 si ha sido respaldado; 1 si necesita respaldarse Bandera ASCII/binario 0 para archivo ASCII; 1 para archivo binario Bandera de acceso aleatorio 0 para sólo acceso secuencial; 1 para acceso aleatorio Bandera temporal 0 para normal; 1 para eliminar archivo al salir del proceso Banderas de bloqueo 0 para desbloqueado; distinto de cero para bloqueado Longitud de registro Número de bytes en un registro Posición de la llave Desplazamiento de la llave dentro de cada registro Longitud de la llave Número de bytes en el campo llave Hora de creación Fecha y hora en que se creó el archivo Hora del último acceso Fecha y hora en que se accedió al archivo por última vez Hora de la última modificación Fecha y hora en que se modificó por última vez el archivo Tamaño actual Número de bytes en el archivo Tamaño máximo Número de bytes hasta donde puede crecer el archivo Figura 4-4. Algunos posibles atributos de archivos. Los primeros cuatro atributos se relacionan con la protección del archivo e indican quién pue- de acceder a él y quién no. Todos los tipos de esquemas son posibles, algunos de los cuales estudia- remos más adelante. En algunos sistemas, el usuario debe presentar una contraseña para acceder a un archivo, en cuyo caso la contraseña debe ser uno de los atributos. Las banderas son bits o campos cortos que controlan o habilitan cierta propiedad específica. Por ejemplo, los archivos ocultos no aparecen en los listados de todos los archivos. La bandera de archivo es un bit que lleva el registro de si el archivo se ha respaldado recientemente. El programa www.FreeLibros.me 264 SISTEMAS DE ARCHIVOS CAPÍTULO 4 de respaldo lo desactiva y el sistema operativo lo activa cada vez que se modifica un archivo. De esta forma, el programa de respaldo puede indicar qué archivos necesitan respaldarse. La bandera temporal permite marcar un archivo para la eliminación automática cuando el proceso que lo creó termina. Los campos longitud de registro, posición de llave y longitud de llave sólo están presentes en los archivos en cuyos registros se pueden realizar búsquedas mediante el uso de una llave. Ellos pro- porcionan la información requerida para buscar las llaves. Los diversos tiempos llevan la cuenta de cuándo se creó el archivo, su acceso y su modifica- ción más recientes. Éstos son útiles para una variedad de propósitos. Por ejemplo, un archivo de código fuente que se ha modificado después de la creación del archivo de código objeto corres- pondiente necesita volver a compilarse. Estos campos proporcionan la información necesaria. El tamaño actual indica qué tan grande es el archivo en el presente. Algunos sistemas operati- vos de computadoras mainframe antiguas requieren que se especifique el tamaño máximo a la ho- ra de crear el archivo, para poder permitir que el sistema operativo reserve la cantidad máxima de almacenamiento de antemano. Los sistemas operativos de estaciones de trabajo y computadoras personales son lo bastante inteligentes como para arreglárselas sin esta característica. 4.1.6 Operaciones de archivos Los archivos existen para almacenar información y permitir que se recupere posteriormente. Dis- tintos sistemas proveen diferentes operaciones para permitir el almacenamiento y la recuperación. A continuación se muestra un análisis de las llamadas al sistema más comunes relacionadas con los archivos. 1. Create. El archivo se crea sin datos. El propósito de la llamada es anunciar la llegada del archivo y establecer algunos de sus atributos. 2. Delete. Cuando el archivo ya no se necesita, se tiene que eliminar para liberar espacio en el disco. Siempre hay una llamada al sistema para este propósito. 3. Open. Antes de usar un archivo, un proceso debe abrirlo. El propósito de la llamada a open es permitir que el sistema lleve los atributos y la lista de direcciones de disco a memoria principal para tener un acceso rápido a estos datos en llamadas posteriores. 4. Close. Cuando terminan todos los accesos, los atributos y las direcciones de disco ya no son necesarias, por lo que el archivo se debe cerrar para liberar espacio en la tabla interna. Mu- chos sistemas fomentan esto al imponer un número máximo de archivos abiertos en los pro- ceso. Un disco se escribe en bloques y al cerrar un archivo se obliga a escribir el último bloque del archivo, incluso aunque ese bloque no esté lleno todavía. 5. Read. Los datos se leen del archivo. Por lo general, los bytes provienen de la posición ac- tual. El llamador debe especificar cuántos datos se necesitan y también debe proporcionar un búfer para colocarlos. www.FreeLibros.me SECCIÓN 4.1 ARCHIVOS 265 6. Write. Los datos se escriben en el archivo otra vez, por lo general en la posición actual. Si la posición actual es al final del archivo, aumenta su tamaño. Si la posición actual está en medio del archivo, los datos existentes se sobrescriben y se pierden para siempre. 7. Append. Esta llamada es una forma restringida de write. Sólo puede agregar datos al final del archivo. Los sistemas que proveen un conjunto mínimo de llamadas al sistema por lo general no tienen append; otros muchos sistemas proveen varias formas de realizar la mis- ma acción y algunas veces ésos tienen append. 8. Seek. Para los archivos de acceso aleatorio, se necesita un método para especificar de dón- de se van a tomar los datos. Una aproximación común es una llamada al sistema de nom- bre seek, la cual reposiciona el apuntador del archivo en una posición específica del archivo. Una vez que se completa esta llamada, se pueden leer o escribir datos en esa po- sición. 9. Get attributes. A menudo, los procesos necesitan leer los atributos de un archivo para realizar su trabajo. Por ejemplo, el programa make de UNIX se utiliza con frecuencia pa- ra administrar proyectos de desarrollo de software que consisten en muchos archivos fuen- te. Cuando se llama a make, este programa examina los tiempos de modificación de todos los archivos fuente y objeto, con los que calcula el mínimo número de compilaciones re- queridas para tener todo actualizado. Para hacer su trabajo, debe analizar los atributos, a saber, los tiempos de modificación. 10. Set attributes. Algunos de los atributos puede establecerlos el usuario y se pueden mo- dificar después de haber creado el archivo. Esta llamada al sistema hace eso posible. La in- formación del modo de protección es un ejemplo obvio. La mayoría de las banderas también caen en esta categoría. 11. Rename. Con frecuencia ocurre que un usuario necesita cambiar el nombre de un archivo existente. Esta llamada al sistema lo hace posible. No siempre es estrictamente necesaria, debido a que el archivo por lo general se puede copiar en un nuevo archivo con el nuevo nombre, eliminando después el archivo anterior. 4.1.7 Un programa de ejemplo que utiliza llamadas al sistema de archivos En esta sección examinaremos un programa simple de UNIX que copia un archivo de su archivo fuente a un archivo destino. Su listado se muestra en la figura 4-5. El programa tiene una mínima funcionalidad y un reporte de errores aún peor, pero nos da una idea razonable acerca de cómo fun- cionan algunas de las llamadas al sistema relacionadas con archivos. Por ejemplo, el programa copyfile se puede llamar mediante la línea de comandos copyfile abc xyz para copiar el archivo abc a xyz. Si xyz ya existe, se sobrescribirá. En caso contrario, se creará. www.FreeLibros.me 266 SISTEMAS DE ARCHIVOS CAPÍTULO 4 #include #define TAM_BUF 4096 #define MODO_SALIDA 0700 int main(int argc, char *argv[]) { int ent_da, sal_da, leer_cuenta, escribir_cuenta: char bufer[TAM_BUF]; if (argc != 3) exit(1); ent_da = open(argv, O_RDONLY); if (ent_da < 0) exit(2); sal_da = creat(argv, MODO_SALIDA); if (sal_da < 0) exit(3); while (TRUE) { leer_cuenta = read(ent_da,bufer,TAM_BUF); if (lee_cuenta ast>mailbox Sin importar cuál carácter se utilice, si el primer carácter del nombre de la ruta es el separador, en- tonces la ruta es absoluta. El otro tipo de nombre es el nombre de ruta relativa. Éste se utiliza en conjunto con el con- cepto del directorio de trabajo (también llamado directorio actual). Un usuario puede designar un directorio como el directorio de trabajo actual, en cuyo caso todos los nombres de las rutas que no empiecen en el directorio raíz se toman en forma relativa al directorio de trabajo. Por ejemplo, si el directorio de trabajo actual es /usr/ast, entonces el archivo cuya ruta absoluta sea /usr/ast/mail- box se puede referenciar simplemente como mailbox. En otras palabras, el comando de UNIX cp /usr/ast/mailbox /usr/ast/mailbox.bak y el comando cp mailbox mailbox.bak hacen exactamente lo mismo si el directorio de trabajo es /usr/ast. A menudo es más conveniente la forma relativa, pero hace lo mismo que la forma absoluta. Algunos programas necesitan acceder a un archivo específico sin importar cuál sea el directo- rio de trabajo. En ese caso, siempre deben utilizar nombres de rutas absolutas. Por ejemplo, un co- rrector ortográfico podría necesitar leer /usr/lib/dictionary para realizar su trabajo. Debe utilizar el nombre de la ruta absoluta completo en este caso, ya que no sabe cuál será el directorio de trabajo cuando sea llamado. El nombre de la ruta absoluta siempre funcionará, sin importar cuál sea el di- rectorio de trabajo. Desde luego que, si el corrector ortográfico necesita un gran número de archivos de /usr/lib, un esquema alternativo es que emita una llamada al sistema para cambiar su directorio de trabajo a /usr/lib y que después utilice dictionary como el primer parámetro para open. Al cambiar en forma explícita el directorio de trabajo, sabe con certeza dónde se encuentra en el árbol de directorios, pa- ra poder entonces usar rutas relativas. Cada proceso tiene su propio directorio de trabajo, por lo que cuando éste cambia y después termina ningún otro proceso se ve afectado y no quedan rastros del cambio en el sistema de archi- vos. De esta forma, siempre es perfectamente seguro para un proceso cambiar su directorio de tra- bajo cada vez que sea conveniente. Por otro lado, si un procedimiento de biblioteca cambia el directorio de trabajo y no lo devuelve a su valor original cuando termina, el resto del programa tal www.FreeLibros.me SECCIÓN 4.2 DIRECTORIOS 271 vez no funcione, ya que el supuesto directorio de trabajo que debería tener ahora podría ser inváli- do. Por esta razón, los procedimientos de biblioteca raras veces cambian el directorio de trabajo y cuando deben hacerlo siempre lo devuelven a su posición original antes de regresar. La mayoría de los sistemas operativos que proporcionan un sistema de directorios jerárquico tienen dos entradas especiales en cada directorio: “.” y “..”, que por lo general se pronuncian “pun- to” y “puntopunto”. Punto se refiere al directorio actual; puntopunto se refiere a su padre (excepto en el directorio raíz, donde se refiere a sí mismo). Para ver cómo se utilizan estas entradas especia- les, considere el árbol de archivos de UNIX en la figura 4-8. Cierto proceso tiene a /usr/ast como su directorio de trabajo. Puede utilizar.. para subir en el árbol. Por ejemplo, puede copiar el archi- vo /usr/lib/dictionary a su propio directorio mediante el comando cp../lib/dictionary. La primera ruta instruye al sistema que vaya hacia arriba (al directorio usr) y después baje al direc- torio lib para encontrar el archivo dictionary. / bin Directorio raíz etc lib usr tmp bin etc lib usr tmp ast jim lib ast lib jim /usr/jim dict. Figura 4-8. Un árbol de directorios de UNIX. El segundo argumento (punto) nombra el directorio actual. Cuando el comando cp obtiene un nombre de directorio (incluyendo punto) como su último argumento, copia todos los archivos a ese www.FreeLibros.me 272 SISTEMAS DE ARCHIVOS CAPÍTULO 4 directorio. Desde luego que una forma más normal de realizar la copia sería utilizar el nombre de ruta absoluta completo del archivo de origen: cp /usr/lib/dictionary. Aquí el uso de punto ahorra al usuario la molestia de escribir dictionary una segunda vez. Sin em- bargo, también funciona escribir cp /usr/lib/dictionary dictionary al igual que cp /usr/lib/dictionary /usr/ast/dictionary Todos estos comandos realizan exactamente lo mismo. 4.2.4 Operaciones de directorios Las llamadas al sistema permitidas para administrar directorios exhiben más variación de un siste- ma a otro que las llamadas al sistema para los archivos. Para dar una impresión de lo que son y có- mo funcionan, daremos un ejemplo (tomado de UNIX). 1. Create. Se crea un directorio. Está vacío, excepto por punto y puntopunto, que el sistema coloca ahí de manera automática (o en unos cuantos casos lo hace el programa mkdir). 2. Delete. Se elimina un directorio. Se puede eliminar sólo un directorio vacío. Un directorio que sólo contiene a punto y puntopunto se considera vacío, ya que por lo general éstos no se pueden eliminar. 3. Opendir. Los directorios se pueden leer. Por ejemplo, para listar todos los archivos en un directorio, un programa de listado abre el directorio para leer los nombres de todos los ar- chivos que contiene. Antes de poder leer un directorio se debe abrir, en forma análoga al proceso de abrir y leer un archivo. 4. Closedir. Cuando se ha leído un directorio, se debe cerrar para liberar espacio en la tabla interna. 5. Readdir. Esta llamada devuelve la siguiente entrada en un directorio abierto. Antes era po- sible leer directorios utilizando la llamada al sistema read común, pero ese método tiene la desventaja de forzar al programador a conocer y tratar con la estructura interna de los direc- torios. En contraste, readdir siempre devuelve una entrada en formato estándar, sin impor- tar cuál de las posibles estructuras de directorio se utilice. 6. Rename. En muchos aspectos, los directorios son sólo como archivos y se les puede cam- biar le nombre de la misma forma que a los archivos. 7. Link. La vinculación (ligado) es una técnica que permite a un archivo aparecer en más de un directorio. Esta llamada al sistema especifica un archivo existente y el nombre de una ru- ta, creando un vínculo desde el archivo existente hasta el nombre especificado por la ruta. www.FreeLibros.me SECCIÓN 4.3 IMPLEMENTACIÓN DE SISTEMAS DE ARCHIVOS 273 De esta forma, el mismo archivo puede aparecer en varios directorios. A un vínculo de es- te tipo, que incrementa el contador en el nodo-i del archivo (para llevar la cuenta del núme- ro de entradas en el directorio que contienen el archivo), se le llama algunas veces vínculo duro (o liga dura). 8. Unlink. Se elimina una entrada de directorio. Si el archivo que se va a desvincular sólo es- tá presente en un directorio (el caso normal), se quita del sistema de archivos. Si está pre- sente en varios directorios, se elimina sólo el nombre de ruta especificado. Los demás permanecen. En UNIX, la llamada al sistema para eliminar archivos (que vimos antes) es, de hecho, unlink. La lista anterior contiene las llamadas más importantes, pero hay unas cuantas más; por ejemplo, para administrar la información de protección asociada con un directorio. Una variante sobre la idea de vincular archivos es el vínculo simbólico (liga simbólica). En vez de tener dos nombres que apunten a la misma estructura de datos interna que representa un ar- chivo, se puede crear un nombre que apunte a un pequeño archivo que nombre a otro. Cuando se utiliza el primer archivo, por ejemplo, abierto, el sistema de archivos sigue la ruta y busca el nom- bre al final. Después empieza el proceso de búsqueda otra vez, utilizando el nuevo nombre. Los víncu- los simbólicos tienen la ventaja de que pueden traspasar los límites de los discos e incluso nombrar archivos en computadoras remotas. Sin embargo, su implementación es poco menos eficiente que los vínculos duros. 4.3 IMPLEMENTACIÓN DE SISTEMAS DE ARCHIVOS Ahora es el momento de cambiar del punto de vista que tiene el usuario acerca del sistema de ar- chivos, al punto de vista del que lo implementa. Los usuarios se preocupan acerca de cómo nom- brar los archivos, qué operaciones se permiten en ellos, cuál es la apariencia del árbol de directorios y cuestiones similares de la interfaz. Los implementadores están interesados en la forma en que se almacenan los archivos y directorios, cómo se administra el espacio en el disco y cómo hacer que todo funcione con eficiencia y confiabilidad. En las siguientes secciones examinaremos varias de estas áreas para ver cuáles son los problemas y las concesiones que se deben hacer. 4.3.1 Distribución del sistema de archivos Los sistemas de archivos se almacenan en discos. La mayoría de los discos se pueden dividir en una o más particiones, con sistemas de archivos independientes en cada partición. El sector 0 del disco se conoce como el MBR (Master Boot Record; Registro maestro de arranque) y se utiliza para arrancar la computadora. El final del MBR contiene la tabla de particiones, la cual proporciona las direcciones de inicio y fin de cada partición. Una de las particiones en la tabla se marca como acti- va. Cuando se arranca la computadora, el BIOS lee y ejecuta el MBR. Lo primero que hace el pro- grama MBR es localizar la partición activa, leer su primer bloque, conocido como bloque de arranque, y ejecutarlo. El programa en el bloque de arranque carga el sistema operativo contenido www.FreeLibros.me 274 SISTEMAS DE ARCHIVOS CAPÍTULO 4 en esa partición. Por cuestión de uniformidad, cada partición inicia con un bloque de arranque no contenga un sistema operativo que se pueda arrancar. Además, podría contener uno en el futuro. Además de empezar con un bloque de arranque, la distribución de una partición de disco varía mucho de un sistema de archivos a otro. A menudo el sistema de archivos contendrá algunos de los elementos que se muestran en la figura 4-9. El primero es el superbloque. Contiene todos los pa- rámetros clave acerca del sistema de archivos y se lee en la memoria cuando se arranca la compu- tadora o se entra en contacto con el sistema de archivos por primera vez. La información típica en el superbloque incluye un número mágico para identificar el tipo del sistema de archivos, el núme- ro de bloques que contiene el sistema de archivos y otra información administrativa clave. Disco completo Tabla de particiones Partición de disco MBR Bloque de Super Administración Nodos-I Directorio Archivos y directorios arranque bloque del espacio libre raíz Figura 4-9. Una posible distribución del sistema de archivos. A continuación podría venir información acerca de los bloques libres en el sistema de archivos, por ejemplo en la forma de un mapa de bits o una lista de apuntadores. Ésta podría ir seguida de los nodos-i, un arreglo de estructuras de datos, uno por archivo, que indica todo acerca del archivo. Después de eso podría venir el directorio raíz, que contiene la parte superior del árbol del sistema de archivos. Por último, el resto del disco contiene todos los otros directorios y archivos. 4.3.2 Implementación de archivos Probablemente la cuestión más importante al implementar el almacenamiento de archivos sea man- tener un registro acerca de qué bloques de disco van con cuál archivo. Se utilizan varios métodos en distintos sistemas operativos. En esta sección examinaremos unos cuantos de ellos. Asignación contigua El esquema de asignación más simple es almacenar cada archivo como una serie contigua de bloques de disco. Así, en un disco con bloques de 1 KB, a un archivo de 50 KB se le asignarían 50 bloques consecutivos. Con bloques de 2 KB, se le asignarían 25 bloques consecutivos. www.FreeLibros.me SECCIÓN 4.3 IMPLEMENTACIÓN DE SISTEMAS DE ARCHIVOS 275 En la figura 4-10(a) podemos ver un ejemplo de asignación de almacenamiento contigua. Aquí se muestran los primeros 40 bloques de disco, empezando con el bloque 0, a la izquierda. Al prin- cipio el disco estaba vacío, después se escribió un archivo A de cuatro bloques de longitud al dis- co, empezando desde el principio (bloque 0). Posteriormente se escribió un archivo de seis bloques llamado B, empezando justo después del archivo A. Observe que cada archivo empieza al inicio de un nuevo bloque, por lo que si el archivo A fue- ra realmente de 31/2 bloques, se desperdiciaría algo de espacio al final del último bloque. En la fi- gura se muestra un total de siete archivos, cada uno empezando en el bloque que va después del final del archivo anterior. Se utiliza sombreado sólo para facilitar la distinción de cada archivo. No tiene un significado real en términos de almacenamiento. Archivo A Archivo C Archivo E Archivo G (4 bloques) (6 bloques) (12 bloques) (3 bloques) … Archivo B Archivo D Archivo F (3 bloques) (5 bloques) (6 bloques) (a) (Archivo A) (Archivo C) (Archivo E) (Archivo G) … Archivo B 5 bloques libres 6 bloques libres (b) Figura 4-10. (a) Asignación contigua de espacio de disco para siete archivos. (b) El estado del disco después de haber removido los archivos D y F. La asignación de espacio en disco contiguo tiene dos ventajas significativas. En primer lugar es simple de implementar, ya que llevar un registro de la ubicación de los bloques de un archivo se reduce a recordar dos números: la dirección de disco del primer bloque y el número de bloques en el archivo. Dado el número del primer bloque, se puede encontrar el número de cualquier otro blo- que con una simple suma. En segundo lugar, el rendimiento de lectura es excelente debido a que el archivo completo se puede leer del disco en una sola operación. Sólo se necesita una búsqueda (para el primer bloque). Después de eso, no son necesarias más búsquedas ni retrasos por rotación, por lo que los datos lle- gan con el ancho de banda completa del disco. Por ende, la asignación contigua es simple de im- plementar y tiene un alto rendimiento. Por desgracia, la asignación contigua también tiene una desventaja ligeramente significante: con el transcurso del tiempo, los discos se fragmentan. Para ver cómo ocurre esto, examine la figura 4-10(b). www.FreeLibros.me 276 SISTEMAS DE ARCHIVOS CAPÍTULO 4 Aquí se han eliminado dos archivos, D y F. Cuando se quita un archivo, sus bloques se liberan natural- mente, dejando una serie de bloques libres en el disco. El disco no se compacta al momento para quitar el hueco, ya que eso implicaría tener que copiar todos los bloques que van después del hueco, que po- drían ser millones. Como resultado, el disco al final consiste de archivos y huecos, como se ilustra en la figura. Al principio esta fragmentación no es un problema, ya que cada nuevo archivo se puede escri- bir al final del disco, después del anterior. Sin embargo, en un momento dado el disco se llenará y será necesario compactarlo, lo cual es en extremo costoso o habrá que reutilizar el espacio libre de los huecos. Para reutilizar el espacio hay que mantener una lista de huecos, lo cual se puede hacer. Sin embargo, cuando se cree un nuevo archivo será necesario conocer su tamaño final para poder elegir un hueco del tamaño correcto y colocarlo. Imagine las consecuencias de tal diseño. El usuario empieza un editor de texto o procesador de palabras para poder escribir un documento. Lo primero que pide el programa es cuántos bytes ten- drá el documento final. Esta pregunta se debe responder o el programa no continuará. Si el núme- ro dado finalmente es demasiado pequeño, el programa tiene que terminar prematuramente debido a que el hueco de disco está lleno y no hay lugar para colocar el resto del archivo. Si el usuario tra- ta de evitar este problema al proporcionar un número demasiado grande como tamaño final, por de- cir 100 MB, tal vez el editor no pueda encontrar un hueco tan grande y anuncie que el archivo no se puede crear. Desde luego que el usuario tiene la libertad de iniciar de nuevo el programa dicien- do 50 MB esta vez y así en lo sucesivo hasta que se encuentre un hueco adecuado. Aún así, no es probable que este esquema haga que los usuarios estén felices. Sin embargo, hay una situación en la que es factible la asignación contigua y de hecho, se uti- liza ampliamente: en los CD-ROMs. Aquí todos los tamaños de los archivos se conocen de antema- no y nunca cambiarán durante el uso subsiguiente del sistema de archivos del CD-ROM. Más adelante en este capítulo estudiaremos el sistema de archivos del CD-ROM más común. La situación con los DVDs es un poco más complicada. En principio, una película de 90 mi- nutos se podría decodificar como un solo archivo de una longitud aproximada de 4.5 GB, pero el sistema de archivos utilizado, conocido como UDF (Universal Disk Format, Formato de disco uni- versal), utiliza un número de 30 bits para representar la longitud de un archivo, limitando el tama- ño de los archivos a 1 GB. Como consecuencia, las películas en DVD se almacenan generalmente como tres o cuatro archivos de 1 GB, cada uno de los cuales es contiguo. Estas partes físicas del único archivo lógico (la película) se conocen como fragmentos. Como mencionamos en el capítulo 1, la historia se repite a menudo en las ciencias compu- tacionales, a medida que van surgiendo nuevas generaciones de tecnología. En realidad, la asig- nación contigua se utilizó en los sistemas de archivos en discos magnéticos hace años, debido a su simpleza y alto rendimiento (la amabilidad con el usuario no contaba mucho entonces). Des- pués se descartó la idea debido a la molestia de tener que especificar el tamaño final del archivo al momento de su creación. Pero con la llegada de los CD-ROMs, los DVDs y otros medios óp- ticos en los que se puede escribir sólo una vez, los archivos contiguos son repentinamente una buena idea otra vez. Por lo tanto, es importante estudiar los antiguos sistemas y las ideas, que conceptualmente eran claras y simples, debido a que pueden aplicarse a los sistemas futuros en formas sorprendentes. www.FreeLibros.me SECCIÓN 4.3 IMPLEMENTACIÓN DE SISTEMAS DE ARCHIVOS 277 Asignación de lista enlazada (ligada) El segundo método para almacenar archivos es mantener cada uno como una lista enlazada de blo- ques de disco, como se muestra en la figura 4-11. La primera palabra de cada bloque se utiliza co- mo apuntador al siguiente. El resto del bloque es para los datos. Archivo A 0 Bloque Bloque Bloque Bloque Bloque de de de de de archivo archivo archivo archivo archivo 0 1 2 3 4 Bloque 4 7 2 10 12 físico Archivo B 0 Bloque Bloque Bloque Bloque de de de de archivo archivo archivo archivo 0 1 2 3 Bloque 6 3 11 14 físico Figura 4-11. Almacenamiento de un archivo como una lista enlazada de bloques de disco. A diferencia de la asignación contigua, en este método se puede utilizar cada bloque del disco. No se pierde espacio debido a la fragmentación del disco (excepto por la fragmentación interna en el último bloque). Además, para la entrada del directorio sólo le basta con almacenar la dirección de disco del primer bloque. El resto se puede encontrar a partir de ella. Por otro lado, aunque la lectura secuencial un archivo es directa, el acceso aleatorio es en ex- tremo lento. Para llegar al bloque n, el sistema operativo tiene que empezar desde el principio y leer los n – 1 bloques anteriores, uno a la vez. Es clarto que tantas lecturas serán demasiado lentas. Además, la cantidad de almacenamiento de datos en un bloque ya no es una potencia de dos, debido a que el apuntador ocupa unos cuantos bytes. Aunque no es fatal, tener un tamaño peculiar es menos eficiente debido a que muchos programas leen y escriben en bloques, cuyo tamaño es una potencia de dos. Con los primeros bytes de cada bloque ocupados por un apuntador al siguiente blo- que, leer el tamaño del bloque completo requiere adquirir y concatenar información de dos bloques de disco, lo cual genera un gasto adicional de procesamiento debido a la copia. Asignación de lista enlazada utilizando una tabla en memoria Ambas desventajas de la asignación de lista enlazada se pueden eliminar si tomamos la palabra del apuntador de cada bloque de disco y la colocamos en una tabla en memoria. La figura 4-12 mues- www.FreeLibros.me 278 SISTEMAS DE ARCHIVOS CAPÍTULO 4 tra cuál es la apariencia de la tabla para el ejemplo de la figura 4-11. En ambas figuras tenemos dos archivos. El archivo A utiliza los bloques de disco 4, 7, 2, 10 y 12, en ese orden y el archivo B uti- liza los bloques de disco 6, 3, 11 y 14, en ese orden. Utilizando la tabla de la figura 4-12, podemos empezar con el bloque 4 y seguir toda la cadena hasta el final. Lo mismo se puede hacer empezan- do con el bloque 6. Ambas cadenas se terminan con un marcador especial (por ejemplo,
1) que no sea un número de bloque válido. Dicha tabla en memoria principal se conoce como FAT (File Allocation Table, Tabla de asignación de archivos). Bloque físico 0 1 2 10 3 11 4 7 El archivo A empieza aquí 5 6 3 El archivo B empieza aquí 7 2 8 9 10 12 11 14 12 –1 13 14 –1 15 Bloque sin utilizar Figura 4-12. Asignación de lista enlazada que utiliza una tabla de asignación de archi- vos en la memoria principal. Utilizando esta organización, el bloque completo está disponible para los datos. Además, el ac- ceso aleatorio es mucho más sencillo. Aunque aún se debe seguir la cadena para encontrar un des- plazamiento dado dentro del archivo, la cadena está completamente en memoria y se puede seguir sin necesidad de hacer referencias al disco. Al igual que el método anterior, la entrada de directorio necesita mantener sólo un entero (el número de bloque inicial) y aún así puede localizar todos los bloques, sin importar qué tan grande sea el archivo. La principal desventaja de este método es que toda la tabla debe estar en memoria todo el tiem- po para que funcione. Con un disco de 200 GB y un tamaño de bloque de 1 KB, la tabla necesita 200 millones de entradas, una para cada uno de los 200 millones de bloques de disco. Cada entra- da debe tener un mínimo de 3 bytes. Para que la búsqueda sea rápida, deben tener 4 bytes. Así, la tabla ocupará 600 MB u 800 MB de memoria principal todo el tiempo, dependiendo de si el siste- ma está optimizado para espacio o tiempo. Esto no es muy práctico. Es claro que la idea de la FAT no se escala muy bien en los discos grandes. www.FreeLibros.me SECCIÓN 4.3 IMPLEMENTACIÓN DE SISTEMAS DE ARCHIVOS 279 Nodos-i Nuestro último método para llevar un registro de qué bloques pertenecen a cuál archivo es asociar con cada archivo una estructura de datos conocida como nodo-i (nodo-índice), la cual lista los atri- butos y las direcciones de disco de los bloques del archivo. En la figura 4-13 se muestra un ejem- plo simple. Dado el nodo-i, entonces es posible encontrar todos los bloques del archivo. La gran ventaja de este esquema, en comparación con los archivos vinculados que utilizan una tabla en me- moria, es que el nodo-i necesita estar en memoria sólo cuando está abierto el archivo correspon- diente. Si cada nodo-i ocupa n bytes y puede haber un máximo de k archivos abiertos a la vez, la memoria total ocupada por el arreglo que contiene los nodos-i para los archivos abiertos es de sólo kn bytes. Sólo hay que reservar este espacio por adelantado. Atributos de archivo Dirección del bloque de disco 0 Dirección del bloque de disco 1 Dirección del bloque de disco 2 Dirección del bloque de disco 3 Dirección del bloque de disco 4 Dirección del bloque de disco 5 Dirección del bloque de disco 6 Dirección del bloque de disco 7 Dirección del bloque de apuntadores Bloque de disco que contiene direcciones de disco adicionales Figura 4-13. Un nodo-i de ejemplo. Por lo general, este arreglo es mucho más pequeño que el espacio ocupado por la tabla de ar- chivos descrita en la sección anterior. La razón es simple: la tabla para contener la lista enlazada de todos los bloques de disco es proporcional en tamaño al disco en sí. Si el disco tiene n bloques, la tabla necesita n entradas. A medida que aumenta el tamaño de los discos, esta tabla aumenta li- nealmente con ellos. En contraste, el esquema del nodo-i requiere un arreglo en memoria cuyo ta- maño sea proporcional al número máximo de archivos que pueden estar abiertos a la vez. No importa si el disco es de 10 GB, de 100 GB ó de 1000 GB. Un problema con los nodos-i es que si cada uno tiene espacio para un número fijo de direccio- nes de disco, ¿qué ocurre cuando un archivo crece más allá de este límite? Una solución es reser- www.FreeLibros.me 280 SISTEMAS DE ARCHIVOS CAPÍTULO 4 var la última dirección de disco no para un bloque de datos, sino para la dirección de un bloque que contenga más direcciones de bloques de disco, como se muestra en la figura 4-13. Algo aun más avanzado sería que dos o más de esos bloques contuvieran direcciones de disco o incluso bloques de disco apuntando a otros bloques de disco llenos de direcciones. Más adelante volveremos a ver los nodos-i, al estudiar UNIX. 4.3.3 Implementación de directorios Antes de poder leer un archivo, éste debe abrirse. Cuando se abre un archivo, el sistema operativo utiliza el nombre de la ruta suministrado por el usuario para localizar la entrada de directorio. Esta entrada provee la información necesaria para encontrar los bloques de disco. Dependiendo del sis- tema, esta información puede ser la dirección de disco de todo el archivo (con asignación contigua), el número del primer bloque (ambos esquemas de lista enlazada ) o el número del nodo-i. En todos los casos, la función principal del sistema de directorios es asociar el nombre ASCII del archivo a la información necesaria para localizar los datos. Una cuestión muy relacionada es dónde deben almacenarse los atributos. Cada sistema de ar- chivos mantiene atributos de archivo, como el propietario y la hora de creación de cada archivo, de- biendo almacenarse en alguna parte. Una posibilidad obvia es almacenarlos directamente en la entrada de directorio. Muchos sistemas hacen eso. Esta opción se muestra en la figura 4-14(a). En este diseño simple, un directorio consiste en una lista de entradas de tamaño fijo, una por archivo, que contienen un nombre de archivo (de longitud fija), una estructura de los atributos del archivo y una o más direcciones de disco (hasta cierto máximo) que indique en dónde se encuentran los blo- ques de disco. juegos atributos juegos correo atributos correo noticias atributos noticias trabajo atributos trabajo Estructura de (a) (b) datos que contiene los atributos Figura 4-14. (a) Un directorio simple que contiene entradas de tamaño fijo, con las di- recciones de disco y los atributos en la entrada de directorio. (b) Un directorio en el que cada entrada sólo hace referencia a un nodo-i. Para los sistemas que utilizan nodos-i, existe otra posibilidad para almacenar los atributos en los nodos-i, en vez de hacerlo en las entradas de directorio. En ese caso, la entrada de directorio puede ser más corta: sólo un nombre de archivo y un número de nodo-i. Este método se ilustra en www.FreeLibros.me SECCIÓN 4.3 IMPLEMENTACIÓN DE SISTEMAS DE ARCHIVOS 281 la figura 4-14(b). Como veremos más adelante, este método tiene ciertas ventajas sobre el método de colocarlos en la entrada de directorio. Los dos esquemas que se muestran en la figura 4-14 co- rresponden a Windows y UNIX, respectivamente, como veremos más adelante. Hasta ahora hemos hecho la suposición de que los archivos tienen nombres cortos con longitud fija. En MS-DOS, los archivos tienen un nombre base de 1 a 8 caracteres y una extensión opcional de 1 a 3 caracteres. En UNIX Version 7, los nombres de los archivos eran de 1 a 14 caracteres, in- cluyendo cualquier extensión. Sin embargo, casi todos los sistemas operativos modernos aceptan nombres de archivos más largos, con longitud variable. ¿Cómo se pueden implementar éstos? El esquema más simple es establecer un límite en la longitud del nombre de archivo, que por lo general es de 255 caracteres y después utilizar uno de los diseños de la figura 4-14 con 255 ca- racteres reservados para cada nombre de archivo. Este esquema es simple, pero desperdicia mucho espacio de directorio, ya que pocos archivos tienen nombres tan largos. Por cuestiones de eficien- cia, es deseable una estructura distinta. Una alternativa es renunciar a la idea de que todas las entradas de directorio sean del mismo tamaño. Con este método, cada entrada de directorio contiene una porción fija, que por lo general empieza con la longitud de la entrada y después va seguida de datos con un formato fijo, que co- múnmente incluyen el propietario, la hora de creación, información de protección y demás atribu- tos. Este encabezado de longitud fija va seguido por el nombre del archivo, sin importar la longitud que tenga, como se muestra en la figura 4-15(a) en formato big-endian (por ejemplo, SPARC). En este ejemplo tenemos tres archivos, sexto-proyecto, personaje y ave. Cada nombre de archivo se ter- mina con un carácter especial (por lo general 0), el cual se representa en la figura mediante un cua- dro con una cruz. Para permitir que cada entrada de directorio empiece en un límite de palabra, cada nombre de archivo se rellena a un número entero de palabras, que se muestran como cuadros som- breados en la figura. Una desventaja de este método es que cuando se elimina un archivo, en su lugar queda un hue- co de tamaño variable dentro del directorio, dentro del cual el siguiente archivo a introducir pue- de que no quepa. Este problema es el mismo que vimos con los archivos de disco contiguos, sólo que ahora es factible compactar el directorio ya que se encuentra por completo en la memoria. Otro problema es que una sola entrada en el directorio puede abarcar varias páginas, por lo que puede ocurrir un fallo de páginas al leer el nombre de un archivo. Otra manera de manejar los nombres de longitud variable es hacer que las mismas entradas de directorio sean de longitud fija y mantener los nombres de los archivos juntos en un heap al final del directorio, como se muestra en la figura 4-15(b). Este método tiene la ventaja de que cuando se remueva una entrada, el siguiente archivo a introducir siempre cabrá ahí. Desde luego que el heap se debe administrar y todavía pueden ocurrir fallos de página al procesar los nombres de los archi- vos. Una pequeña ganancia aquí es que ya no hay una verdadera necesidad de que los nombres de archivos empiecen en límites de palabras, por lo que no se necesitan caracteres de relleno después de los nombres de archivos en la figura 4-15(b), como se hizo en la figura 4-15(a). En todos los diseños mostrados hasta ahora se realizan búsquedas lineales en los directorios de principio a fin cuando hay que buscar el nombre de un archivo. Para los directorios en extremo largos, la búsqueda lineal puede ser lenta. Una manera de acelerar la búsqueda es utilizar una tabla de hash en cada directorio. Llamemos n al tamaño de la tabla. Para introducir un nombre de archivo, se codifica en hash con un valor entre 0 y n
1, por ejemplo, dividiéndolo entre n y tomando el www.FreeLibros.me 282 SISTEMAS DE ARCHIVOS CAPÍTULO 4 Longitud de entrada Apuntador al nombre Entrada del archivo 1 del archivo 1 para un Atributos del archivo 1 Atributos del archivo 1 archivo Entrada s e x t Apuntador al nombre para un archivo o - p r del archivo 2 o y e c Atributos del archivo 2 t o Apuntador al nombre Longitud de entrada del archivo 3 del archivo 2 Atributos del archivo 3 Atributos del archivo 2 p e r s o n a j e s e x t Longitud de entrada o - p r del archivo 3 o y e c Atributos del archivo 3 t o p Heap a v e e r s o n a j e a v e (a) (b) Figura 4-15. Dos maneras de manejar nombres de archivos largos en un directorio. (a) En línea. (b) En un heap. residuo. De manera alternativa, las palabras que componen el nombre del archivo se pueden sumar y esta cantidad se divide entre n, o algo similar. De cualquier forma, se inspecciona la entrada de la tabla correspondiente al código de hash. Si no está en uso, un apuntador se coloca ahí a la entrada del archivo. Las entradas de archivos siguen la tabla de hash. Si esa ranura ya está en uso, se construye una lista enlazada, que encabeza la en- trada de la tabla y que encadena todas las entradas con el mismo valor de hash. Para buscar un archivo se sigue el mismo procedimiento. El nombre de archivo se codifica en hash para seleccionar una entrada en la tabla hash. Todas las entradas en la cadena que encabeza esa ranura se verifican para ver si el nombre de archivo está presente. Si el nombre no se encuentra en la cadena, el archivo no está presente en el directorio. El uso de una tabla de hash tiene la ventaja de que la búsqueda es mucho más rápida, pero la desventaja de una administración más compleja. En realidad es sólo un candidato serio en los siste- mas donde se espera que los directorios rutinariamente contengan cientos o miles de archivos. Una manera distinta de acelerar la búsqueda en directorios extensos es colocar en caché los resultados de las búsquedas. Antes de iniciar una búsqueda, primero se realiza una verificación para ver si el nombre del archivo está en la caché. De ser así, se puede localizar de inmediato. Desde lue- go, el uso de la caché sólo funciona si un número relativamente pequeño de archivos abarcan la ma- yoría de las búsquedas. www.FreeLibros.me