ESCUELA DE PREPARACIÓN DE OPOSITORES E. P. O. Cl. La Merced, 8 - Bajo A Telf.: 968 24 85 54 30001 MURCIA INF19·- SA119 Sistemas operativos: gestión de archivosy dispositivos. Esquema. , 1 11'l'I"~()l){J(:(:l()l'J ..............•.............•............................•......................•................................. :2. ' 2 GESTION DE ARCHIVOS 2 2.1 IMPLANTACIÓN DE ARCHIVOS 2 2.1.1 Asignación enforma de lista enlazada 2 2.1. 2 Asignación mediante una lista enlazada y un índice 3 2. 1. 3 Nodos-i. 3 2.2 IMPLANTACIÓN DE DIRECTORIOS 4 2.2.1 Directorios en MS-DOS 4 2.2.2 Directorios en UNIX 4 2.3 ARCHIVOS COMPARTIDOS 4 2.4 ADMINISTRACIÓN DEL ESPACIO EN DISCO 5 2. 4.1 Tamaño del bloque 5 2.4.2 Registro de los bloques libres 5 2.4.3 Cuotas de disco 5 2.5 FIABILIDAD DEL SISTEMA DE ARCHIVOS 6 2. 5.1 Manejo de un bloque defectuoso 6 2. 5.2 Consistencia delsistema de archivos 6 2. 6 RENDIMIENTO DEL SISTEMA DE ARCHIVOS 7 2. 6.1 Caché de disco : 7 2. 6.2 Reducción de la cantidad de movimiento del brazo del disco 8 2.7 MECANISMOS DE PROTECCIÓN 8 2. 7.1 Dominios deprotección 8 2. 7.2 Listas para control de acceso 9 2. 7.3 Posibilidades 9 , 3 GESTION DE DISPOSITIVOS 9 3 .1 MANEJADORES DE INTERRUPCIONES l O 3 .2 MANEJADORES DE DISPOSITIVOS 10 3 .3 SOFTWARE DE E/S INDEPENDIENTE DEL DISPOSITIVO 10 3.4 SOFTWARE DEE/SEN ELESPACIO DEL USUARIO 10 '1- l.Jl'JI~ 11 4.1 EL SISTEMA DE ARCHIVOS EN UNIX 11 4.2 GESTIÓNDE DISPOSITIVOS EN UNIX 11 4.3 IMPLEMENTACIÓN DEL SISTEMA DE ARCHIVOS EN UNIX 12 5 MS-DOS 14 5 .1 EL SISTEMA DE ARCHIVOS EN MS-DOS 14 5.2 GESTIÓN DE DISPOSITIVOS EN MS-DOS 15 5.3 IMPLEMENTACIÓN DEL SISTEMA DE ARCHIVOS EN MS-DOS 15 6 WINDOWS 2000 18 6.1 ELSISTEMADEARCHIVOSFAT 18 6.2 NTFS 21 Escuela de Preparación de Opositores E.P .O. v05 INF19- SAI19. Página 2 6.2.1 Conceptosfundamentales 21 6.2.2 Implementación delsistema dearchivos Windows 2000 21 7 CONCLUSIONES 25 1 Introducción. Todas las aplicaciones necesitan almacenar y recuperar la información. Tenemos tres condiciones esenciales para el almacenamiento de la información a largo plazo: debe ser posible almacenar una cantidad muy grande de información, la información debe sobrevivir a la conclusión del proceso que la utiliza, y debe ser posible que varios procesos tengan acceso concurrente a la información. La solución a estos problemas es el almacenamiento de la información en discos y otros medios externos, en unidades llamadas archivos. La información almacenada en los archivos debe ser persistente; es decir, no debe verse afectada por la creación y término de un proceso. Un archivo debe desaparecer sólo en caso de su eliminación explícita por parte del propietario. Los archivos son administrados por el sistema operativo. Su estructura, nombre, forma de acceso, uso, protección e implantación son temas fundamentales en el diseño de un sistema operativo. Aquella parte del sistema operativo que trabaja con los archivos se conoce como el sistema de archivos. Otra de las funciones principales de un sistema operativo es el control de todos los dispositivos de entrada/salida de la computadora. Debe enviar comandos a los dispositivos, detectar las interrupciones y controlar los errores. También debe proporcionar una interfaz entre los dispositivos y el resto del sistema, sencilla y fácil de usar. En la medida de lo posible, la interfaz debe ser la misma para todos los dispositivos (independencia del dispositivo). En este tema presentamos un análisis detallado de la gestión de archivos y de dispositivos en un sistema operativo. 2 Gestión de archivos. 2.1 Implantación de archivos. El aspecto clave de la implantación del almacenamiento de archivos es el registro de los bloques asociados a cada archivo. Se utilizan distintos métodos en los distintos sistemas. 2.1.1 Asignación en forma de lista enlazada. Un método para el almacenamiento de archivos es mantener a cada uno de ellos como una lista enlazada de bloques en disco. La primera palabra de cada bloque se utiliza como puntero a la siguiente. El resto del bloque contiene datos. Archivo A Archívo B ~ o ~ ~ o .... Bloque Bloque Blogue Bloque Blogue Blogue Bloque Bloque Blogue de de de de de de de de de archivo arch iv archivo archivo archivo archivo archivo archivo archivo o o 1 2 3 4 o 1 2 3 Bloque fisico 4 7 2 10 12 6 3 11 14 Con este método se puede utilizar cada bloque del disco. No se pierde espacio debido a la fragmentación. Además, es suficiente que la entrada del directorio guarde Escuela de Preparación de Opositores E.P.O. v05 INF 19 - SAI 19. Página 3 sólo la dirección en disco del primer bloque. El resto se puede encontrar a partir de esto. Por otro lado, el acceso aleatorio es lento. 2.1.2 Asignación mediante una lista enlazada y un índice. Podemos mejorar la asignación mediante lista enlazada si se toma la palabra del puntero de cada bloque del disco y se le coloca en una tabla o índice de la memoria. La siguiente figura muestra la apariencia de la tabla para el ejemplo de la figura anterior. Bloque fisico o 1 2 3 10 4 11 5 7 El archivo A comienza aquí 6 7 3 El archivo B comienza aquí 8 2 9 10 12 11 14 12 o 13 14 o 15 En ambas figuras, tenemos dos archivos. El archivo A utiliza los bloques 4, 7, 2, 1 O y 12 del disco, en ese orden, mientras que el archivo B utiliza los bloques 6, 3, 11 y 14, en ese orden. Mediante esta organización, todo el bloque está disponible para los datos. Además, el acceso aleatorio es mucho más sencillo. Como en el método anterior, es suficiente que el dato del directorio contenga un solo entero (el número de bloque inicial) y con ello localizar todos los bloques restantes, sin importar el tamaño del archivo. MS-DOS utiliza este método para la asignación del espacio en disco. La principal desventaja de este método es que toda la tabla debe estar en la memoria. 2.1.3 Nodos-i. Otro método para controlar los bloques correspondientes a cada archivo es asociar a cada archivo una pequeña tabla, llamada nodo-i (nodo índice), la cual contiene los atributos y direcciones en disco de los bloques del archivo. Las primeras direcciones en disco se almacenan en el propio nodo-i, de forma que, en el caso de archivos pequeños, toda la información necesaria esté contenida en el nodo-i, el cual se traslada del disco a la memoria principal al abrir el archivo. Para los archivos un poco más grandes, una de las direcciones en el nodo-i es la dirección de un bloque en disco llamado bloque simplemente indirecto. Este bloque contiene las direcciones en disco adicionales. Si éste no es suficiente, otra dirección en el nodo-i, el bloque doblemente indirecto, contiene la dirección de un bloque que presenta una lista de los bloques simplemente indirectos. Cada uno de estos bloques apunta a unos centenares de bloques de datos. Si esto todavía no es suficiente, se puede utilizar un bloque triplemente indirecto. UNIX utiliza este esquema. Escuela de Preparación de Opositores E.P.O. v05 INF19- SAI19. Página 4 2.2 Implantación de directorios. Antes de poder leer un archivo, éste debe ser abierto. Al abrir un archivo, el sistema operativo utiliza el nombre de la ruta de acceso dado por el usuario para localizar el dato en el directorio. El dato del directorio contiene la información necesaria para encontrar los bloques en el disco. Según el sistema, esta información podría ser la dirección en disco de todo el archivo, el número del primer bloque o el número del nodo-i. En todos los casos, la principal función del sistema de directorios es asociar el nombre en ASCII del archivo con la información necesaria para localizar los datos. Un aspecto íntimamente ligado con esto es la posición de almacenamiento de los atributos. Una posibilidad obvia es almacenarlos de forma directa dentro del dato del directorio. Para los sistemas que utilizan los nodos-i, otra posibilidad es almacenar los atributos en el nodo-i, en vez de utilizar la entrada del directorio. 2.2.1 Directorios en MS-DOS. La siguiente figura muestra un dato de directorio en MS-DOS. Tiene una longitud de 32 bytes y contiene el nombre del archivo, sus atributos y el número del primer bloque. El número del primer bloque se utiliza como un índice en una tabla del tipo lista enlazada con índice. Los bloques se pueden determinar al seguir la cadena. Bytes 8 3 1 10 2 2 2 4 Nombre Extensión Atributos Reservado Hora Fecha Nº del primer Tamaño del archivo bloque En MS-DOS, los directorios pueden contener otros directorios, lo que conduce a un sistema jerárquico de archivos. 2.2.2 Directorios en UNIX. En la estructura de directorios utilizada en UNIX cada entrada contiene un nombre de archivo y su número de nodo-i. Toda la información relativa al tipo, tamaño, tiempos, propiedad y bloques en disco está contenida en el nodo-i. Bytes 2 14 i Nobre del archivo I I Nº de nodo-i Al abrir un archivo, el sistema de archivos debe tomar el nombre de archivo proporcionado y localizar sus bloques en disco. 2.3 Archivos compartidos. Un archivo compartido puede aparecer simultáneamente en distintos directorios, los cuales pertenecen a distintos usuarios. La siguiente figura muestra un sistema de archivos donde un archivo de C está presente también en uno de los directorios de B. La conexión entre el directorio de B y el archivo compartido se llama enlace. A B e . 9 e e e (, ' Escuela de Preparación de Opositores E.P.O. v05 INF19 - SAI19. Página 5 Los archivos compartidos presentan problemas. Si los directorios contienen direcciones en disco, hay que hacer una copia de las direcciones en disco en el directorio B al enlazar el archivo. Si B o C se añaden al archivo, los nuevos bloques se listan sólo en el directorio del usuario que hace el añadido. Este problema se puede . resolver de dos formas. En la primera solución, los bloques del disco se listan en una pequeña estructura de datos asociada al propio archivo. Los directorios apuntarían entonces sólo a esa pequeña estructura de datos. Este es el punto de vista que se utiliza en UNIX (donde la pequeña estructura de datos es el nodo-i). En la segunda solución, B se enlaza con uno de los archivos C, haciendo que el sistema cree un nuevo archivo, el cual entra en el directorio B. Este nuevo archivo sólo contiene el nombre de la ruta de acceso del archivo al cual se enlaza. Este punto de vista se llama enlace simbólico. 2.4 Administración del espacio en disco. Casi todos los sistemas de archivos dividen los archivos en bloques de tamaño fijo que no tienen que ser adyacentes. 2.4.1 Tamaño del bloque. Si se tiene una unidad de asignación grande, corno un cilindro, esto significa que cada archivo ocupará todo un cilindro. Por otro lado, el uso de una pequeña unidad de asignación implica que cada archivo constará de muchos bloques. La lectura de cada bloque requiere por lo general de un retraso por la búsqueda y la rotación, por lo que la lectura de un archivo con muchos bloques pequeños será muy lenta. El compromiso usual es elegir un tamaño de bloque de 512 bytes, IK ó 2K. 2.4.2 Registro de los bloques libres. Se utilizan por lo general dos métodos. El primero consiste en el uso de una lista enlazada de bloques de disco, en la que cada bloque contiene tantos números de bloques libres como pueda. Con un bloque de lK y un número de bloque de 16 bits, cada bloque de la lista de bloques libres contiene los números de 511 bloques libres. Un disco de 20M necesita una lista de bloques libres con un máximo de 40 bloques para mantener 20K números de bloques libres. La otra técnica para la administración del 'espacio libre es el mapa de bits. Un disco con n bloques necesita un mapa de bits con n bits. Los bloques libres se representan con el valor 1 en el mapa y los bloques asignados con el valor O (o viceversa). Un disco de 20M necesita 20K bits para ese mapa, lo cual sólo requiere tres bloques. Sólo en el caso que el disco esté casi lleno, el esquema de lista enlazada utiliza menos bloques que el mapa de bits. 2.4.3 Cuotas de disco. Los sistemas operativos multiusuario, como UNIX, proporcionan con frecuencia mecanismos para establecer las cuotas en el disco. La idea es que un administrador del sistema asigne a cada usuario una proporción máxima de archivos y bloques y que el sistema operativo garantice que los usuarios no excedan sus cuotas. Cuando un usuario abre un archivo, se localizan los atributos y direcciones en disco y se colocan en una tabla de archivos abiertos en la memoria principal. Entre los atributos está una entrada que indica el propietario del archivo. Cualquier aumento del tamaño del archivo se carga a la cuota del propietario. Escuela de Preparación de Opositores E.P.O. v05 INF 19 - SAI 19. Página 6 Una segunda tabla contiene el registro de las cuotas para cada uno. de los usuarios que tengan un archivo abierto en ese momento, aun cuando el archivo haya sido abierto por alguien más. Cuando se escribe una nueva entrada en la tabla de archivos abiertos, se introduce un puntero al registro de la cuota del propietario para poder localizar con facilidad los distintos límites. Cada vez que se añade un bloque a un archivo, se incrementa el total de bloques cargados al propietario y se verifica este valor contra los límites estricto y flexible. Se puede exceder el límite flexible, pero el límite estricto no. Cualquier intento por añadir algo a un archivo al haber alcanzado el límite estricto produce un error. También se verifica el número de archivos. Cuando un usuario pretende iniciar una sesión, el sistema verifica el archivo de cuotas. Si se ha excedido cualquiera de los límites, aparece un mensaje de advertencia y el contador de advertencias restantes se reduce en uno. Si el contador llega a O, el usuario ha ignorado demasiadas veces la advertencia y no se le permite iniciar su sesión. Este método tiene la propiedad de que los usuarios pueden exceder su límite flexible durante una sesión terminal, siempre que eliminen su exceso antes de salir del sistema. Los límites estrictos nunca deben ser excedidos. 2.5 Fiabilidad del sistema de archivos. 2.5.1 Manejo de un bloque defectuoso. Se utilizan dos tipos de soluciones al problema de los bloques defectuosos, una hardware y otra software. La solución hardware consiste en dedicar un sector del disco a la lista de bloques defectuosos. Al inicializar el controlador por primera vez, éste lee la lista de bloques defectuosos y elige un bloque (o pista) de reserva para reemplazar los defectuosos, registrando la asociación en la lista de bloques defectuosos. De ahí en adelante, las solicitudes del bloque defectuoso utilizarán el de repuesto. La solución software requiere construir un archivo con todos los bloques defectuosos. Esta técnica los elimina de la lista de bloques libres, de forma que nunca pueden aparecer en los archivos de datos. Mientras no se lea o escriba en este archivo de bloques defectuosos, no surgirán problemas. 2.5.2 Consistencia del sistema de archivos. Muchos sistemas de archivo leen bloques, los modifican y escriben en ellos después. Si el sistema falla, el sistema de archivos puede quedar inconsistente. La mayoría de las computadoras tiene una utilidad que verifica la consistencia del sistema de archivos. Se puede ejecutar al arrancar el sistema; en particular, después de un fallo. A continuación describimos el funcionamiento de dicha utilidad en UNIX. Para verificar la consistencia de los bloques, se construye una tabla con dos contadores para cada bloque. El primer contador mantiene el número de veces que el bloque está presente en un archivo; el segundo registra el número de veces que está presente en la lista de bloques libres (o en el mapa de bits de los bloques libres). El programa lee todos los nodos-i, construyendo una lista de todos los números de los bloques utilizados en el archivo correspondiente. Al leer cada número de bloque, se incrementa su contador en la primera tabla. El programa examina a continuación la lista o el mapa de bits de los bloques libres para localizar todos los bloques que no se estén utilizando. Cada aparición de un bloque en la lista de bloques libres hace que se incremente su contador en la segunda tabla. Si el sistema de archivos es consistente, cada bloque tiene un 1 en la primera o en la segunda tabla. Si un bloque no aparece en Escuela de Preparación de Opositores E.P.O. v05 INFl 9 - SAI19. Página 7 ninguna de las tablas, es un bloque faltante, que se añade a la lista de bloques libres. Sin embargo, puede ocurrir que un bloque aparezca dos veces en la lista de bloques libres (imposible con un mapa de bits). La solución de este caso es reconstruir la lista de bloques libres. También puede ocurrir que el mismo bloque de datos aparezca en uno o más archivos, debiendo entonces asignar un bloque libre, copiar en él el contenido del bloque en cuestión e insertar la copia en uno de los archivos. Por último, si un bloque esté presente en un archivo y en la lista de bloques libres hay que eliminarlo de la lista de bloques libres. Además, debe verificarse también el sistema de directorios. También en este caso se utiliza una tabla de contadores, pero por directorio y no por bloque. Se inicia en el directorio raíz y se desciende de forma recursiva en el árbol, para inspeccionar cada uno de los directorios del sistema de archivos. Para cada uno de los archivos en cada directorio, se incrementa el contador del nodo-i de dicho archivo. Al terminar de hacer esto, se tiene una lista en la que el índice es el número de nodo-i, la cual indica el número de directorios que apuntan a ese nodo-i. Compara entonces estos números con los contadores de enlaces almacenados en los propios nodos-i. En un sistema consistente de archivos, ambos contadores deben coincidir. Si el contador de enlaces es diferente del número de entradas del directorio, entonces debe hacerse que el contador de enlaces en el nodo-i tome el valor correcto. Si el valor correcto es O, el archivo debe eliminarse. Estas dos operaciones, la verificación de bloques y de directorios se integran en una sola por razones de eficiencia. Es posible hacer otras verificaciones heurísticas. Por ejemplo, los directorios tienen un formato definido, con números de nodo-i y nombres ASCII. Si el número de un nodo-i es mayor que el número de nodos-i en el disco, el directorio tiene algún daño. 2.6 Rendimiento delsistema dearchivos. 2.6.1 Caché de disco. La técnica más común para reducir los accesos a disco es el bloque caché o buffer caché. Un caché es una colección de bloques que pertenecen desde el punto de vista lógico al disco, pero que se mantienen en la memoria por razones de rendimiento. Se utilizan varios algoritmos para la administración del caché, pero uno de los más comunes es el de verificar todas las solicitudes de lectura para saber si el bloque solicitado se encuentra en el caché. En caso afirmativo, se satisface la solicitud sin un acceso a disco. Si el bloque no se encuentra en el caché, primero se lee para que esté dentro de él y después se copia al lugar donde se necesite. Las siguientes solicitudes del mismo bloque se pueden satisfacer por medio del caché. Cuando hay que cargar un bloque en un caché totalmente ocupado, hay que eliminar algún bloque y volverlo a escribir en disco si ha sido modificado antes de haberlo traído del disco. Esta situación es muy parecida a la paginación y se pueden aplicar los algoritmos usuales de paginación, como FIFO, la segunda oportunidad y LRU. UNIX tiene una llamada al sistema, SYNC, que obliga a todos los bloques modificados a salir del disco inmediatamente. Al iniciar el sistema, un programa, inicia también un ciclo infinito en el que se llama a SYNC, haciendo una pausa de 30 segundos entre las llamadas. Como resultado, no más de 30 segundos de trabajo se pierden debido a un fallo. Escuela de Preparación de Opositores E.P .O. v05 INFl 9 - SAI 19. Página 8 MS-DOS escribe cada bloque modificado al disco, tan pronto como haya sido escrito. Los cachés en los que todos los bloques modificados se escriben de nuevo al disco de forma inmediata se llaman cachés de escritura. 2.6.2 Reducción de la cantidad de movimiento del brazo del disco. Al escribir un archivo de salida, el sistema de archivos debe asignar los bloques, uno a la vez, conforme sea necesario. Si se registran los bloques libres en un mapa de bits y todo este mapa se encuentra dentro de la memoria principal, es bastante fácil elegir un bloque libre tan cercano corno sea posible al bloque anterior. Con una lista de bloques libres, parte de la cual está en el disco, es mucho más difícil asignar los bloques en forma cercana entre sí. Sin embargo, aun con una lista de bloques libres, se puede hacer cierta asociación de bloques manteniendo un registro del espacio para almacenamiento en el disco no por bloques, sino por grupos de bloques consecutivos. Si una pista contiene 64 sectores de 512 bytes, el sistema podría utilizar bloques de lK (2 sectores), pero podría asignar el espacio en unidades de 2 bloques (4 sectores). Esto no es lo mismo que tener un bloque de tamaño 2K, puesto que el caché seguiría utilizando bloques de 1K, y las transferencias también serían de lK; pero la lectura secuencial de un archivo en un sistema que de otro modo estaría inactivo reduciría el número de búsquedas en factor de dos, lo cual mejoraría en mucho el rendimiento. Otro cuello de botella en el rendimiento de los sistemas que utilizan nodos-i o su equivalente es que la lectura de un archivo, incluso uno pequeño, requiere dos accesos al disco: uno para el nodo-i y otro para el bloque. Un método sencillo para mejorar el rendimiento es colocar los nodos-i a mitad del disco, con lo cual se reduce a la mitad el tiempo promedio de búsqueda entre el nodo-i y el primer bloque. Otra idea es dividir el disco en grupos de cilindros, cada uno con sus propios nodos-i, bloques y lista de bloques libres. Al crear un nuevo archivo, se puede elegir cualquier nodo-i, pero al hacer esto, se intenta encontrar un bloque en el mismo grupo de cilindros que el nodo-i. 2. 7 Mecanismos deprotección. A continuación nos concentraremos en algunas de las técnicas que utilizan los sistemas operativos para la protección de archivos u otras cosas. 2.7.1 Dominios de protección. Un dominio es un conjunto de parejas (objeto, derechos). Cada pareja determina un objeto y cierto subconjunto de las operaciones que se pueden llevar a cabo en él. Un derecho es, en este contexto, el permiso para realizar alguna de las operaciones. Para aclarar la idea de un dominio de protección, analizaremos UNIX. En UNIX, el dominio de un proceso queda definido mediante la identificación del usuario (uid) y la identificación de su grupo (gid). Dada cualquier combinación (uid, gid), es posible elaborar una lista completa de todos los objetos (archivos, dispositivos de E/S representados mediante archivos especiales, etc), a los que puede tener acceso; además, se puede determinar si se permite el acceso para lectura, escritura o ejecución. Dos procesos con la misma combinación (uid, gid) tendrán acceso al mismo conjunto de objetos. Los procesos con distintos valores (uid, gid) tendrán acceso a un conjunto distinto de archivos. Escuela de Preparación de Opositores E.P .O. v05 INF19 - SAI19. Página 9 2.7.2 Listas para control de acceso. La mayoría de los dominios no tienen acceso alguno a la mayoría de los objetos. Esta técnica asocia a cada objeto una lista (ordenada) con todos los dominios que pueden tener acceso al objeto y la forma de dicho acceso. Esta lista se llama lista de control de acceso (ACL). Si se implantara en UNIX, lo más sencillo sería colocar la ACL de cada archivo en un bloque de disco independiente e incluir el número de bloque en el nodo-i del archivo. UNIX proporciona tres bits rwx, para cada archivo, para el propietario, el grupo del propietario y los demás. Este esquema es de nuevo la ACL, pero comprimida a nueve bits. Es una lista asociada con el objeto, la cual indica quién puede tener acceso y en qué forma. El propietario de un objeto puede modificar su ACL en cualquier momento, lo que hace fácil prohibir accesos antes permitidos. El único problema es que es probable que la modificación de la ACL no afecte a los usuarios que utilicen en ese momento el objeto. 2.7.3 Posibilidades. Al utilizar este método, se asocia a cada proceso una lista de objetos a los cuales puede tener acceso, junto con una indicación de las operaciones permitidas en cada uno; en otras palabras, su dominio. Esta lista se llama lista de posibilidades y los elementos individuales de ella se llaman posibilidades. Cada posibilidad tiene un campo Tipo, el cual indica el tipo del objeto; un campo Derechos, un mapa de bits que indica las operaciones básicas permitidas en este tipo de objeto; así como un campo Objeto, un puntero al propio objeto (por ejemplo, su número de nodo-i). Las listas de posibilidades son a su vez objetos y se les puede apuntar desde otras listas de posibilidades, lo que facilita la existencia de subdominios compartidos. Con frecuencia, se hace referencia a las posibilidades mediante su posición en la lista. 3 Gestión de dispositivos. El software de EIS se organiza como una serie de capas, donde las capas inferiores oculten las peculiaridades del hardware a las capas superiores de forma que éstas se preocupen por presentar una interfaz agradable, limpia y regular a los usuarios. Un concepto clave en el diseño del software de E/S es la independencia del dispositivo. El sistema operativo debe encargarse de los problemas causados por el hecho de que los dispositivos sean distintos y requieran directivas diferentes. El objetivo de lograr nombres uniformes está relacionado con el de independencia del dispositivo. El nombre de un archivo o dispositivo debe ser sólo una cadena o un entero y no debe depender del dispositivo. En UNIX, todos los discos se pueden integrar juntos en la jerarquía del sistema de archivos de maneras arbitrarias, de forma que el usuario no tenga que tener conciencia del nombre de cada dispositivo. Otro aspecto importante del software de E/Ses el manejo de errores. En general, los errores deben manejarse lo más cerca posible del hardware. Si el controlador descubre un error de lectura, debe tratar de corregirlo. Si no puede corregirlo, debería controlarlo, tal vez mediante la forma de leer el bloque de nuevo. Muchos errores son momentáneos, tales como los de lectura provocados por partículas de polvo en la cabeza de lectura y desaparecen al repetirse la operación. Sólo en el caso en que los niveles inferiores no puedan resolver el problema, se informa a los niveles superiores. Escuela de Preparación de Opositores E.P.O. v05 INF19- SAil9. Página 10 Otro de los aspectos claves son las transferencias síncrona (por bloques) o asíncrona (controlada por intenuptores). La mayor parte de la E/S es asíncrona, pero los programas son más fáciles de escribir si las operaciones de E/S son por medio de bloques (después de un comando READ, el programa se suspende hasta que los datos estén disponibles en el buffer). El sistema operativo se encarga de hacer que las operaciones controladas por interruptores parezcan del tipo de bloques para el usuario. El concepto final que analizaremos es la comparación de los dispositivos que se pueden compartir y los dispositivos de uso exclusivo. Algunos de los dispositivos de EIS, como los discos, pueden ser utilizados por varios usuarios al mismo tiempo. Otros dispositivos, como las impresoras, deben dedicarse a un solo usuario hasta concluir con él. El uso de dispositivos de uso exclusivo presenta también una serie de dificultades. De nuevo, el sistema operativo debe administrar los dispositivos compartidos y de uso exclusivo de forma que evite dichos problemas. Estos objetivos se logran al estructurar el software de E/S en cuatro capas: manejadores de interrupciones, directivas de dispositivos, software de sistema operativo independiente de los dispositivos, y software a nivel usuario. E EIS; Sot'aar. iftd£~¢e,1tlfJ dlldiçol«1.o 3.1 Manejadores de interrupciones. Las interrupciones deben ocultarse en lo más profundo del sistema operativo, de modo que sólo una pequeña parte del sistema sepa de ellas. La mejor forma de esconderlas es que cada proceso que inicie una operación de E/S se bloquee hasta que termine la E/S y ocurra la intenupción. Al ocurrir la interrupción, el procedimiento de interrupción realiza lo debido para eliminar el bloqueo del proceso que lo inició. 3.2 Manejadores de dispositivos. En este apartado deben explicarse los manejadores de dispositivos que hemos estudiado en profundidad en el tema 18, página 5, apartado 3.2. 3.3 Software de EIS independiente del dispositivo. En este apartado debe explicarse el software de E/S independiente del dispositivo que hemos estudiado en profundidad en el tema 18, página 6, apartado 3.3. 3.4 Software de EIS en el espacio del usuario. En este apartado debe explicarse el software de E/S en el espacio del usuario que hemos estudiado en profundidad en el tema 18, página 7, apartado 3.4. Escuela de Preparación de Opositores E.P.O. v05 INF19- SAI19. Página 11 4 UNIX. 4.1 El sistema de archivos en UNIX Cuando un proceso desea leer o escribir en un archivo, primero debe abrir éste. Un archivo se abre mediante la llamada al sistema OPEN, cuyo primer argumento es el nombre de la ruta de acceso del archivo por abrir y cuyo segundo argumento especifica si el archivo se va a leer o escribir o ambos. El sistema verifica si el archivo existe y, de ser así, inspecciona los bits de derechos para ver si el que hace la llamada tiene permitido el acceso al archivo de la manera deseada. Si se permite el acceso, el sistema devuelve un entero positivo pequeño llamado descriptor de archivo a quien hizo la llamada. Si el acceso está prohibido (o el archivo no existe), se devuelve un -1 para indicar un error. Las llamadas para la lectura o escritura en el archivo utilizan el descriptor de archivo para identificarlo. Al iniciar un proceso, siempre dispone de tres descriptores de archivo: O para la entrada estándar, 1 para la salida estándar y 2 para el error estándar. El primer archivo abierto recibe el descriptor de archivo 3, el siguiente el descriptor de archivo 4, etc. Al cerrarse un archivo, se libera su descriptor de archivo, el cual se puede asignar al abrir un nuevo archivo. Existen dos formas para especificar los nombres de archivos en UNIX, tanto para el shell como para la llamada al sistema OPEN. La primera utiliza una ruta absoluta de acceso, que indica la forma de llegar al archivo desde el directorio raíz. Los nombres de las rutas absolutas de acceso son con frecuencia largos. Por esta razón, UNIX permite a los usuarios que designen el directorio en el que trabajan en un momento dado como el directorio de trabajo. Los nombres de las rutas de acceso se pueden determinar entonces en forma relativa al directorio de trabajo. Tal nombre se llama ruta relativa de acceso. A menudo ocurre que un usuario necesita hacer referencia a un archivo que pertenece a otro usuario o que al menos se localiza en un lugar distinto en el árbol de archivos. UNIX proporciona una solución a este problema y permite que los usuarios hagan una nueva entrada en el directorio que apunte a un archivo existente. Tal entrada se conoce como un enlace. Muchas computadoras tienen dos o más discos. Cuando existen varias unidades de disco, surge la cuestión de la forma de controlarlas. Una solución es colocar un sistema de archivos autocontenido en cada uno de ellos y mantenerlos independientes. Con esta solución, el usuario tiene que especificar tanto el dispositivo como el archivo cuando se necesite algo no predefinido. La solución de UNIX es permitir que un disco se monte en el árbol de directorios de otro disco. El usuario ve entonces un único árbol de archivos y no tiene que preocuparse por el lugar donde reside un archivo en un dispositivo. El comando anterior se convierte en que es igual al caso en que todo estuviera en el disco duro desde el principio. 4.2 Gestión de dispositivos en UNIX En este apartado debe explicarse la E/S en UNIX que hemos estudiado en profundidad en el tema 18, página 17, apartado 7.1. Escuela de Preparación de Opositores E.P.O. v05 INF19- SAII9. Página 12 4.3 Implementación del sistema de archivos en UNIX Todos los discos que contienen sistemas de archivos en UNIX tienen la organización que se muestra en la figura. Blogue de arranque Superbloque Nodos-i Blogues de datos I I I I I I I I I I I El bloque O no es utilizado por UNIX y contiene a menudo código para el arranque de la computadora. El bloque 1 es el superbloque. Contiene información crítica relativa a la organización del sistema de archivos: el número de nodos-i, el número de bloques en disco y el inicio de la lista de bloques libres en disco (que, por lo general, tiene unos cuantos centenares de entradas). La destrucción del superbloque provocaría que el sistema de archivos quede ilegible. Después del superbloque están los nodos-i. Se numeran de 1 hasta cierto máximo. Cada nodo-i tiene una longitud de 64 bytes y describe a un archivo. Un nodo-i contiene la información contable (propietario, bits de protección, etc.) así como la información suficiente para localizar todos los bloques del disco que contengan los datos del archivo. Después de los nodos-i están los bloques de datos. Todos los archivos y directorios se almacenan aquí. Si un archivo o directorio consta de más de un bloque, los bloques no tienen por qué ser adyacentes en el disco. De hecho, es probable que los bloques de un archivo grande estén diseminados por todo el disco. Un directorio en el sistema tradicional de archivos consta de una colección no ordenada de entradas de 16 bytes. Cada entrada contiene un nombre de archivo (de hasta 14 caracteres arbitrarios) y el número del nodo-i del archivo. Para abrir un archivo en el directorio de trabajo, el sistema sólo lee el directorio, compara el nombre a buscar con cada entrada, hasta que encuentra el nombre o concluye que no está presente. Si el archivo está presente, el sistema extrae el número del nodo-i y lo utiliza como un índice en la tabla de nodos-i (en el disco) para localizar el nodo-i correspondiente y traerlo a la memoria. El nodo-i se coloca en la tabla de nodos-i, una estructura de datos en el núcleo que conserva todos los nodos-i de los archivos y directorios abiertos en cada momento. Para la búsqueda de un nombre absoluto de ruta de acceso el sistema localiza el directorio raíz, que siempre utiliza el nodo-i 2 ya que el nodo-i 1 se reserva para el manejo de los bloques defectuosos. Entonces busca la cadena en el directorio raíz, para obtener el número de nodo-i del directorio especificado. Se busca entonces este nodo-i y se extraen los bloques del disco de él, de forma que se pueda leer el directorio y buscar la siguiente cadena. Este proceso continúa hasta encontrar el fichero y su número de nodo-i. El uso de un nombre relativo de una ruta de acceso ahorra una cantidad sustancial de trabajo al sistema. Veamos ahora la forma en que el sistema lee un archivo. Recordemos que una forma típica de utilizar la llamada al sistema READ se ve de la manera siguiente: count=read(fd,buffer,nbytes). Cuando el núcleo obtiene el control, sólo debe iniciar con estos tres parámetros y la información en la estructura del usuario de quien hizo la llamada. Uno de los elementos en la estructura del usuario es la tabla de descriptores de archivo. Sus índices son los descriptores de archivo y contiene una entrada por cada archivo abierto (hasta cierto número máximo, que, por lo general, es 20). La idea es iniciar con este descriptor de archivo y terminar con el correspondiente nodo-i. Consideremos un posible diseño, mediante el cual basta colocar un puntero al nodo-i en la tabla de descriptores de archivo. Aunque este método es Escuela de Preparación de Opositores E.P.O. v05 INF19- SAI19. Página 13 sencillo, no funciona. El problema es el siguiente: cada descriptor de archivo tiene asociada una posición de archivo, la cual indica el byte donde iniciará la siguiente lectura (o escritura). ¿Adónde debe ir? Una posibilidad es colocarla en la tabla de nodos-i. Sin embargo, este método falla si ocurre que dos o más procesos no relacionados entre sí abren el mismo archivo al mismo tiempo, puesto que cada uno de ellos tiene su propia posición de archivo. Una segunda posibilidad es colocar la posición del archivo en la tabla de descriptores de archivo. De esa forma, cada proceso que abra un archivo obtiene su posición del archivo particular. Por desgracia, este esquema también falla, pero el razonamiento es más sutil y tiene que ver con la naturaleza de los archivos compartidos en UNIX. El truco consiste en utilizar una nueva tabla, la tabla de descripción de archivos abiertos entre la tabla de descriptores de archivo y la tabla de nodos-i y colocar ahí la posición de archivo (y el bit de lectura/escritura). De regreso en el problema de realizar un READ, hemos mostrado entonces la forma de localizar la posición de archivo y el nodo-i. El nodo-i contiene las direcciones en discos de los primeros 1 O bloques del archivo. Si la posición de archivo cae en los primeros 1 O bloques; el bloque se lee y los datos se copian al usuario. Para los archivos mayores de 1 O bloques, un campo en el nodo-i contiene 1a dirección en disco de un bloque simplemente indirecto. Este bloque contiene las direcciones en disco de más bloques en disco. Por ejemplo, si un bloque tiene lK y la dirección en disco es de 4 bytes, el bloque simplemente indirecto puede contener 256 direcciones del disco. Así, este esquema funciona para archivos de hasta 266K en total. Después de esto, se utiliza un bloque doblemente indirecto. Este contiene las direcciones de 256 bloques simplemente indirectos, cada uno de los cuales contiene las direcciones de 256 bloques de datos. Si todavía esto no basta, el nodo-i tiene espacio para bloques triplemente indirectos. Escuela de Preparación de Opositores E.P.O. v05 INFl 9 - SAI 19. Página 14 T J 5 MS-DOS. 5.1 El sistema de archivos en MS-DOS. El patrón original del sistema de archivos de MS-DOS 1.0 se tomó de CP/M, con el uso de un solo directorio y el uso de bloques para el control de archivos para la E/S. A partir de MS-DOS 2.0, se añadió un sistema jerárquico de archivos, al estilo de UNIX, con descriptores de archivo y llamadas al sistema. Los nombres de archivo en MS-DOS tienen una parte básica de 8 caracteres, que pueden estar seguidos por una extensión. La extensión siempre comienza con un punto y puede contener de 1 a 3 caracteres. En ambos casos, los nombres de archivo se conforman con cualquier secuencia de caracteres válidos. Para el shell de UNIX, ABC, Abc y abc son tres archivos no relacionados entre sí. Para el shell de MS-DOS, son el mismo archivo. UNIX tiene propietarios, grupos, protección, enlaces y sistema de archivos montados, nada de lo cual posee MS-DOS. Otra característica que MS-DOS posee y UNIX no, es la presencia de atributos de archivo. Existen cuatro atributos: readonly (el archivo no puede ser modificado), archive (el archivo ha sido modificado desde el último respaldo), system (archivo de sistema que no se puede eliminar mediante el comando del), y hidden (el archivo no se lista mediante el comando dir). El soporte de varios discos sin tener montaje presenta un problema. Es necesario que el usuario proporcione el nombre del dispositivo, digamos a:, para el primer disco, b: para el segundo y e: para el disco duro. Si no se proporciona el código del dispositivo, se asume el valor activo. Escuela de Preparación de Opositores E.P.O. v05 INF19-SAII9. Página 15 5.2 Gestión de dispositivos en MS-DOS. En este apartado debe explicarse la E/S en MS-DOS que hemos estudiado en profundidad en el tema 18, página 19, apartado 8.1. 5.3 Implementación delsistema de archivos en MS-DOS. La organización de un disco duro y un disco flexible son diferentes. Nos concentraremos en un disco duro. Todos los discos duros tienen la misma organización, la cual se muestra en la figura. Se tor primario de arranque Partici ó~ Partición I Partición 2 Partición 3 UNIX ----------- --- ---------- --- -------- FAT ---- Blogues de dato"s----------. ~ ~ctorio raíz I I I I I I I Sector secundario de arranque Duplicado opcional de FAT El sector de arranque contiene la información crítica relativa al sistema de archivos, así como el código para la inicialización del sistema. Después vienen las tablas con el registro del espacio del disco. A éstas le sigue el directorio raíz y todo lo demás. El sector de arranque siempre inicia con una instrucción jump que salta sobre la información descriptiva en el sector y va al principio del código. De esta forma, el mecanismo de arranque de la ROM puede leer el sector de arranque en la memoria y simplemente saltar al principio de él, sin tener que preocuparse por la distribución interna. Después viene una lista de parámetros clave, entre los que están el número de bytes por sector, el número de sectores por bloque, el número de tablas de distribución de archivos (FAT), el tamaño del directorio raíz, el tamaño del dispositivo y datos similares. Después de estos parámetros viene el código del mecanismo de arranque. A diferencia del mecanismo de arranque de ROM, que sólo lee en el sector O y transfiere hacia él, este código sabe que su labor es arrancar MS-DOS. (El código del ROM también puede arrancar UNIX y cualquier otro sistema operativo.) El código del sector de arranque localiza el directorio raíz y busca en él los archivos io.sys y msdos.sys. A continuación, utiliza el BIOS para cargarlos y saltar al inicio de io.sys. El sector de arranque contiene la tabla de partición al final. Esta tabla contiene entradas que indican el inicio y final de cada partición, hasta un máximo de cuatro. Cada partición puede contener un sistema de archivos distinto. De esta forma, MS-DOS y UNIX pueden coexistir alegremente en el mismo disco duro, cada uno con su propia partición. Se puede indicar que cierta partición está ACTIVA, para permitir que ésta se inicialice al arrancar el sistema desde el disco duro. La utilidad de MS-DOS fdisk permite a los usuarios crear, eliminar y modificar el tamaño de las particiones. Una vez dividido el disco en particiones y colocado los sistemas de archivo en cada una de ellas, una nueva división del disco en particiones requiere, por lo general, la fragmentación de todos los sistemas de archivo y la construcción de los nuevos desde cero. Después del sector de arranque viene la FAT que lleva un registro de todo el espacio en disco en el dispositivo. Esta tabla cumple las mismas funciones en MS-DOS que la tabla de nodos-i y la lista de bloques libres en UNIX. Para una mayor fiabilidad, a veces se hace una copia de Ia FAT, de forma que el sistema no se pierda si la FAT principal se vuelve ilegible. Escuela de Preparación de Opositores E.P.O. v05 INFI 9 - SAI19. Página 16 La FAT contiene una entrada por cada bloque del disco. El tamaño de bloque dado en el sector de arranque y puede ir de un sector (por ejemplo, en los discos RAM) hasta 8 sectores (por ejemplo, para los discos duros de gran tamaño). El tamaño de la entrada de la FAT era de 12 bits en la versión I.O, pero como este tamaño sólo puede manejar discos de hasta 4096 bloques, al surgir los grandes discos duros, éste se modificó a 16 bits, lo que permite hasta 64K bloques por partición. Las particiones mayores de 32M se manejan mediante tamaños de bloque mayores que los 512 bytes estándar (por ejemplo, 2K bloques para discos de 1 OOM). La organización conceptual de la FAT se muestra en la figura (la organización real es distinta, puesto que los campos están codificados de una manera extraña). FAT o X Tamaño 1 X del disco 2 EOF Archivo A: 6 •I 8 •I ..w 3 13 4 4 2 I 5 4 Archivo B: 5 •I 9 ..DIJ 6 8 7 LIBRE Archivo C: I 10 I .._¡ 3 I ..DIJ y 8 9 12 10 3 11 LIBRE 12 EOF 13 EOF 14 LIBRE 15 DEFECTUOSO Existe una correspondencia uno a uno entre las entradas de la FAT y los bloques del disco, excepto por las primeras dos entradas de la FAT, que codifican la clase del disco. En este ejemplo, mostramos tres archivos, A, B y C. El archivo A comienza en el bloque 6. El dato de la FAT para 6 es 8, lo que significa que el segundo bloque del archivo es el bloque 8. La entrada de la FAT para 8 es 4, lo que indica que el siguiente bloque es 4. El dato de la FAT para 4 es 2. Por último, el dato para 2 es un código especial que indica el fin del archivo. Así, con el número del primer bloque de un archivo, es posible localizar todos los demás bloques, al seguir la cadena a través de la FAT. El dato del directorio para cada archivo contiene el bloque inicial y la FAT proporciona el resto de la cadena. Los bloques libres se marcan en la FAT mediante otro código especial. Si un archivo crece, MS-DOS busca una entrada libre en la FAT y asigna ese bloque al archivo. De forma similar, se utiliza otro código para marcar los bloques ilegibles. Para ver la forma en que se integra la FAT al sistema de archivos, rastreemos una llamada al sistema OPEN de principio a fin. Comienza cuando MS-DOS busca un descriptor libre en la tabla de descriptores de archivo, que es un array de 20 bytes. Cada uno de los bytes en la tabla de descriptores de archivo contiene un índice de 1 byte de tamaño hacia la tabla maestra de archivos (que es más o menos análoga a la tabla de nodos-i de UNIX); o bien contiene un código que indica que el descriptor no está en uso. Si se localiza un descriptor libre, se busca en la tabla de archivos del sistema un espacio libre. Escuela de Preparación de Opositores E.P.O. v05 INFI 9 - SAil 9. Página 17 Si también esto sucede, entonces se examina el nombre de la ruta de acceso del archivo por abrir para ver si es con, !pt o el nombre de otro de los archivos especiales. El directorio y la extensión se ignoran en esta comparación. Si no es un archivo especial, se verifica el primer carácter para ver si es \. En caso de que sí lo sea, la ruta de acceso es absoluta y la búsqueda comienza en el directorio raíz. En caso contrario, la ruta de acceso es relativa y la búsqueda comienza en el directorio de trabajo. En este respecto, MS-DOS es esencialmente igual a UNIX. Un directorio en MS-DOS tiene un dato de 32 bytes por cada archivo o directorio que contenga, como se muestra en la figura. 16 bits Nombre (8) - - - Extensión (3' - IAIOIVISIHIRI Reservado para uso futuro (10) - - - - Hora (2) Fecha(2) Primer bloque (2) Tamaño del archivo (4) - Los primeros 11 caracteres contienen el nombre y extensión del archivo. A diferencia de UNIX, el punto que separa la parte principal del nombre y su extensión no se almacena en el directorio de manera explícita. A continuación viene el byte de atributo, con los siguientes bits: A - Bit de archivar (activo si se modifica el archivo, inactivo si se ha respaldado) D - Activo para indicar que el dato es un directorio V - Activo para indicar que la entrada es para la etiqueta de volumen S - Activo para indicar archivos de sistema (es decir, no eliminables) H - Activo para los archivos ocultos (es decir, no listados por dir) R - Bit para indicar exclusivo para lectura (no se puede escribir en el archivo) Se puede leer o escribir en el byte de atributo mediante llamadas al sistema. La fecha y hora de la última modificación se almacenan en los dos campos siguientes. El código utiliza 6 bits para los segundos, 6 bits para los minutos, 4 para la hora, 5 para el día, 4 para el mes y 7 para el año (a partir de 1980). Los últimos dos campos contienen el número del primer bloque y el tamaño del archivo. El principio de la cadena en la FAT se puede localizar por medio del número de bloque, con lo cual se pueden localizar todos los demás bloques. Es interesante comparar la implementación del sistema de archivos de MS-DOS con el de UNIX. En UNIX, una entrada de directorio contiene el nombre del archivo y el número de nodo-i y nada más. El resto de la información, como el tamaño del archivo, la fecha y hora de su creación y los números de bloque están contenidos en el Escuela de Preparación de Opositores E.P .O. v05 INFI 9 - SAI 19. Página 18 nodo-i. MS-DOS no tiene nodos-i, por lo que todo está dentro de la entrada del directorio. Este diseño hace imposibles los enlaces, puesto que no puede funcionar el hecho de tener dos entradas de directorio con el mismo número de bloque inicial. Esto también significa que el acceso aleatorio a un bloque cercano al final de un archivo de gran tamaño requiere de una búsqueda considerable a través de la FAT. Por otro lado, el acceso aleatorio a un bloque cercano al final de un archivo de gran tamaño en UNIX requiere de uno o más accesos al disco. De regreso a la llamada al sistema OPEN, si la búsqueda tiene éxito, la entrada del directorio se copia en la tabla de archivos del sistema, la cual tiene una entrada por cada archivo abierto. El campo de posición de archivo toma entonces el valor O. El hecho de que el campo de posición de archivo se encuentre en este lugar no provoca problemas como lo haría en UNIX, puesto que no existe el peligro de que un usuario independiente pudiese abrir el archivo. Por último, el descriptor de archivo se regresa a quien hizo la llamada y se completa la llamada OPEN. 6 Windows 2000. Windows 2000 reconoce varios sistemas de archivos, de entre los que destacamos FAT-16, FAT-32 y NTFS. FAT-16 es el antiguo sistema de archivos de MS-DOS; usa direcciones de disco de 16 bits, lo que lo limita a particiones de disco de 2 GB. FAT-32 emplea direcciones de disco de 32 bits y maneja particiones de disco de hasta 2 TB. NTFS utiliza direcciones de disco de 64 bits y puede en teoria manejar particiones de disco de hasta 264 bytes, aunque otras consideraciones lo limitan a tamaños más pequeños. 6.1 El sistema de archivos FAT. El sistema de archivos FAT tiene tres versiones: FAT-12, FAT-16 y FAT 32, dependiendo del número de bits que tenga una dirección de disco. En realidad, en FAT- 32 sólo se usan los 28 bits de orden bajo de las direcciones de disco. En todas las FATs, el bloque de disco puede definirse como algún múltiplo de 512 bytes (y puede ser diferente para cada partición), y el conjunto de tamaños de bloque permitidos (llamados tamaños de clúster por Microsoft) es diferente para cada variante. La primera versión de MS-DOS usaba FAT-12 con bloques de 512 bytes, lo que daba un tamaño de partición máximo de 212 x 512 bytes (en realidad, sólo 4086 X 512 bytes, porque 1 O de las direcciones de disco se usaban como marcadores especiales: fin de archivo, bloque defectuoso, etcétera). Con estos parámetros, el tamaño máximo de una partición de disco era de aproximadamente 2 MB, y el tamaño de la FAT en la memoria era de 4096 entradas de dos bytes cada una. El uso de una entrada de tabla de 12 bits habría sido demasiado lento. Este sistema funcionaba bien con discos flexibles, pero cuando salieron los discos duros se convirtió en un problema, que Microsoft resolvió permitiendo tamaños de bloque adicionales de 1, 2 y 4 KB. Este cambio conservó la estructura y el tamaño de la tabla FAT-12, pero permitió particiones de disco de hasta 16 MB. Así, que puesto que MS-DOS reconocía cuatro particiones por unidad de disco, el nuevo sistema de archivos FAT-12 funcionaba con discos de hasta 64 MB. Para superar este límite se introdujo FAT-16, con punteros de disco de 16 bits. Además, se permitieron tamaños de bloque de 8, 16 y 32 KB. La tabla FAT-16 ocupaba Escuela de Preparación de Opositores E.P.O. v05 INF 19 - SAI 19. Página 19 128 KB. La partición de disco más grande que se puede manejar con FAT-16 es de 2 GB (64K entradas de 32 KB cada una) y el disco más grande es de 8 GB, o sea, cuatro particiones de 2 GB cada una. A partir de la segunda versión de Windows 95, se introdujo el sistema de archivos FAT-32, con sus direcciones de disco de 28 bits. En este sistema, las particiones podían ser en teoría de 228 x 215 bytes, pero en realidad están limitadas a 2 TB (2048 GB) porque internamente el sistema lleva el control de los tamaños de las particiones en sectores de 512 bytes empleando un número de 32 bits, y 29 x 232 es 2 TB. Además, se permitieron nombres de archivo de más de 8 + 3 caracteres. Para ello, se adoptó un diseño para manejar nombres de archivo largos, que fuera compatible con el viejo sistema de nombres 8 + 3 de MS-DOS. Esta decisión implicó que la estructura de directorios tenía que ser compatible con la de MS-DOS, aunque se utilizaron los 1 O bytes reservados de las entradas de directorio de MS-DOS. Los cambios, como se muestra en la siguiente figura, consisten en la adición de cinco campos nuevos donde solían estar los 1 O bytes desocupados. El campo NT sirve sobre todo para asegurar cierta compatibilidad con Windows NT, en el sentido de mostrar los nombres de archivo en mayúsculas o minúsculas. El campo Seg resuelve el problema de que no es posible almacenar la hora del día en un campo de 16 bits. Otro campo nuevo es Último acceso, que almacena la fecha (pero no la hora) del último acceso al archivo. Por último, el cambio al sistema de archivos FAT-32 implica que los números de bloque ahora son de 32 bits, así que se necesita un campo adicional de 16 bits para almacenar los 16 bits superiores del número de bloque inicial. 2 Para representar los nombres de archivo largos de modo que sean compatibles con MS-DOS se asignan dos nombres a cada archivo: uno largo (en Unicode, por compatibilidad con Windows NT) y un nombre 8 + 3 por compatibilidad con MS-DOS. Cuando se crea un archivo cuyo nombre no obedece las reglas de MS-DOS, se crea un nombre MS-DOS para el archivo tomando los primeros seis caracteres del nombre, convertidos a mayúsculas, y se anexa - 1 para formar el nombre base. Si el nombre ya existe, se usa el sufijo -2, y así sucesivamente. Además, se eliminan los espacios y puntos adicionales y ciertos caracteres especiales se convierten en caracteres de subrayado. Todo archivo tiene un nombre MS-DOS que se almacena empleando el formato de directorio de la figura anterior. Si el archivo también tiene un nombre largo, se almacena en una o más entradas de directorio que preceden inmediatamente al nombre de archivo MS-DOS. Cada entrada de nombre largo contiene hasta 13 caracteres (Unicode). Las entradas se almacenan en orden inverso, con el principio del nombre justo delante de la Escuela de Preparación de Opositores E.P.O. v05 INFI 9 - SAI 19. Página 20 entrada MS-DOS y fragmentos subsiguientes antes de ella. El formato de cada entrada de nombre largo se muestra en la siguiente figura. 1 10 1 1 1 12 l I 5 \ / Para saber si una entrada de directorio contiene un nombre de archivo MS-DOS o un fragmento de nombre largo, se usa el campo Atributos. En el caso de una entrada de nombre largo el campo tiene un valor que corresponde a una combinación imposible de atributos, de modo que los programas MS-DOS que lean el directorio harán caso omiso de esa entrada, por considerarla no válida. Los fragmentos del nombre se unen consecutivamente en función del campo Secuencia. Puesto que sólo usa 6 bits, en teoría el tamaño máximo de los nombres de archivo es 63 x 13 = 819 caracteres (los nombres están limitados a 260 caracteres por razones históricas). Además, cada entrada de nombre largo contiene un campo de Suma de comprobación para evitar que si se crea un archivo con nombre largo y luego, arrancando con MS-DOS se elimina el nombre de archivo MS-DOS del directorio (pero no se elimina el nombre largo, porque no se sabe que existe), al crear un nuevo archivo que reutilice la entrada de directorio desocupada tendremos una secuencia válida de entradas de nombre largo, justo antes de una entrada de archivo MS-DOS, que nada tiene que ver con el nombre largo. El campo Suma de comprobación permite detectar esta situación, verificando que el nombre de archivo MS-DOS que sigue a un nombre largo en verdad corresponde a él. En la siguiente figura se muestra un ejemplo de nombre de archivo largo. d o A t 8."GT- o h ', t o o q u o l I • o 1 e , l o ' • AR ;J A o- ,. Desde el punto de vista conceptual, la implementación del sistema de archivos FAT-32 es similar a la del sistema de archivos FAT-16. Sin embargo, en lugar de una tabla de 64K entradas, hay tantas entradas como se necesiten para cubrir la parte del disco que contiene datos. Si se usa el primer millón de bloques, desde una perspectiva conceptual la tabla tiene un millón de entradas. Para evitar la necesidad de tenerlas todas en la memoria a la vez, se mantiene una "ventana" que ve hacia la tabla, y sólo mantiene una parte de ella en la memoria en un momento dado. Escuela de Preparación de Opositores E.P .O. v05 INF 19 - SAI 19. Página 21 6.2 NTFS. 6.2.1 Conceptos fundamentales. Los nombres de archivo individuales en NTFS están limitados a 255 caracteres; las rutas completas están limitadas a 32,767 caracteres. Los nombres de archivo están en Unicode, lo que permite a personas de países en los que no se usa el alfabeto latino escribir nombres de archivo en su idioma. NTFS distingue entre mayúsculas y minúsculas en los nombres de archivo. Un archivo NTFS consiste en múltiples atributos, cada uno de los cuales se representa con un flujo de bytes. Casi todos los archivos tienen unos cuantos flujos cortos, como el nombre del archivo y su identificador de objeto de 64 bits, y un flujo largo (sin nombre) que contiene los datos. Sin embargo, un archivo también puede tener dos o más flujos de datos (largos). Cada flujo tiene su propio tamaño y se puede bloquear con independencia de todos los demás flujos. La longitud máxima de un flujo es de 264 bytes. Se emplean punteros de archivo para llevar el control del punto dentro de cada flujo en el que un proceso está en un momento dado. 6.2.2 Implementación del sistema de archivos Windows 2000. Cada volumen NTFS contiene archivos, directorios, mapas de bits y otras estructuras de datos. Cada volumen está organizado como una sucesión lineal de bloques de tamaño fijo para cada volumen, que varía entre 512 bytes y 64 KB, dependiendo del tamaño del volumen. Se hace referencia a los bloques por su desplazamiento respecto al principio del volumen, empleando números de 64 bits. La principal estructura de datos de cada volumen es la tabla maestra de archivos (MFT; Master File Table), que es una sucesión lineal de registros de tamaño fijo (1 KB). Cada registro describe un archivo o directorio: contiene los atributos del archivo, como su nombre y marcas de tiempo, y la lista de direcciones de disco donde están sus bloques. Si un archivo es extremadamente grande, a veces es necesario usar dos o más registros MFT para contener la lista de todos los bloques, en cuyo caso el primer registro MFT apunta a los demás registros MFT. Un mapa de bits lleva el control de qué entradas de la MFT están desocupadas. La MFT es en sí un archivo y puede colocarse en cualquier lugar del volumen. Además, el archivo puede crecer hasta un tamaño máximo de 248 registros. Cada registro consiste en una secuencia de pares (encabezado de atributo, valor). Cada atributo empieza con un encabezado que indica de qué atributo se trata y qué longitud tiene. Si el valor del atributo es lo bastante corto como para que quepa en el registro se coloca ahí. Si es demasiado largo, se coloca en otro lugar del disco y en el registro se pone un puntero a él. Los primeros 16 registros están reservados para archivos de metadatos. El nombre de cada uno de estos archivos comienza con un signo de dólar. El primer registro describe el archivo MFT mismo. Windows 2000 halla el primer bloque del archivo MFT examinando el bloque de arranque, donde la dirección del primer bloque del archivo MFT se instala en el momento de instalarse el sistema. El registro 1 es una copia de la primera parte del archivo MFT. El registro 2 es el archivo de registro. Cuando se efectúan cambios estructurales al sistema de archivos, como añadir un nuevo directorio o eliminar uno que ya existe, la acción se asienta aquí Escuela de Preparación de Opositores E.P.O. v05 INF19-SAI19. Página 22 antes de efectuarse, para aumentar las posibilidades de una recuperación correcta en caso de fallo. El registro 3 contiene información acerca del volumen, como su tamaño, y versión. La información acerca de los atributos está en el registro 4. Luego viene el directorio raíz, en el registro 5. Se lleva el control del espacio libre en el volumen con un mapa de bits cuyos atributos y direcciones en disco están en el registro 6. El siguiente registro apunta al archivo del cargador de autoarranque. El registro 8 sirve para enlazar todos los bloques defectuosos. El registro 9 contiene la información de seguridad. El registro 1 O se usa para la conversión de mayúsculas y minúsculas. Por último, el registro 11 es un directorio que contiene archivos diversos para cosas como cuotas de disco, identificadores de objetos, puntos de reanálisis, etc. Los últimos cuatro registros se han reservado para uso futuro. Cada registro consiste en un encabezado de registro seguido de una secuencia de pares (encabezado de atributo, valor). El encabezado contiene un número mágico que sirve para verificar la validez, un número consecutivo que se actualiza cada vez que el registro se reutiliza para un nuevo archivo, un contador de referencias al archivo, el número real de bytes usados en el registro y algunos otros campos diversos. Después del encabezado del registro viene el encabezado del primer atributo, luego el primer valor de atributo, el encabezado del segundo atributo, el valor del segundo atributo y así sucesivamente. NTFS define 13 atributos que pueden aparecer en registros MFT. Cada registro consiste en una sucesión de encabezados de atributo, cada uno de los cuales identifica el atributo que está encabezando y da la longitud y la ubicación del campo de valor junto con diversos indicadores y otra información. Normalmente, los valores de atributo vienen inmediatamente después de sus encabezados, pero si un valor es demasiado largo se podría colocar en otro bloque de disco. Se dice que tal atributo es un atributo no residente. Algunos atributos, como el nombre, pueden repetirse, pero todos deben aparecer en un orden fijo en el registro MFT. Los encabezados de los atributos residentes ocupan 24 bytes; los de atributos no residentes son más largos porque contienen información acerca de dónde se encuentra el atributo en el disco. El campo de información estándar contiene el dueño del archivo, información de seguridad, las marcas de hora que necesita POSIX, la cuenta de enlaces, los bits de sólo lectura y de archivado, etc. Se trata de un campo de longitud fija que siempre está presente. El nombre de archivo está en Unicode y es de longitud variable. Para hacer que los archivos con nombres que no son de MS-DOS sean accesibles para los programas viejos de 16 bits, los archivos también pueden tener un nombre MS-DOS de 8 + 3 caracteres. Si el nombre de archivo real se ajusta a la regla 8 + 3 de MS-DOS, no se usa un nombre MS-DOS secundario. En NT 4.0, la información de seguridad podía colocarse en un atributo, pero en Windows 2000 se coloca toda en un solo archivo con el fin de que varios archivos puedan compartir la misma descripción de seguridad. Por último, llegamos al atributo que contiene los datos. El nombre del flujo, si existe, va en este encabezado de atributo. Después del encabezado viene una lista de direcciones de disco que indica los bloques contenidos en el archivo, o bien, en el caso de archivos de unos cuantos cientos de bytes el archivo mismo. Cuando los datos reales del archivo se colocan en el registro MFT, se habla de un archivo inmediato. El modelo para llevar el control de los bloques de disco es que siempre que es posible se asignan en series de bloques consecutivos. Una forma de lograr estas series consecutivas es asignar el espacio de disco en grupos de varios bloques. Escuela de Preparación de Opositores E.P.O. v05 INF 19 - SAI 19. Página 23 Los bloques de un archivo se describen mediante una secuencia de registros, cada uno de los cuales describe una serie de bloques lógicamente contiguos. En el caso de un archivo sin huecos, sólo habrá uno de esos registros. Los archivos que se escriben en orden de principio a fin pertenecen a esta categoría. Si un archivo contiene un hueco habrá dos registros. Cada registro empieza con un encabezado que da el desplazamiento del primer bloque dentro del archivo. Luego viene el desplazamiento del primer bloque que no cubre este registro. Cada encabezado de registro va seguido de uno o más pares, cada uno de los cuales da una dirección de disco y una longitud. La dirección en disco es el desplazamiento del bloque de disco a partir del principio de su partición; la longitud es el número de bloques que hay en la serie. El registro de serie puede contener tantos pares como sea necesario. En la siguiente figura se ilustra el uso de este esquema con un archivo de nueve bloques divididos en tres series. If f¡ tt • a • • I • I • •' o ' • • • I • • I • • • I t • ' ... . ' • •• •• • • • . ' . ' ' I t • I • • • • I • • • • •" • • t ' I i • .. ~ En esta figura tenemos un registro MFT para un archivo corto (toda la información acerca de los bloques del archivo cabe en un solo registro MFT). Consiste en las tres series de bloques consecutivos en el disco. La primera serie comprende los bloques 20-23, la segunda, los bloques 64-65, y la tercera, los bloques 80-82. Cada una de estas series se graba en el registro MFT como un par (dirección en disco, número de bloques). El número de series depende de lo bien que el asignador de bloques de disco haya hecho su trabajo de encontrar series de bloques consecutivos en el momento en que se creó el archivo. En el caso de un archivo de n bloques, el número de series puede variar entre I y n incluyendo a este último. Conviene hacer aquí varios comentarios. Primero, no existe un límite superior para el tamaño de los archivos que pueden representarse de esta manera. Si no se efectúa compresión de direcciones, cada par requiere dos números de 64 bits, para un total de 16 bytes. Sin embargo, un par podría representar un millón de bloques de disco consecutivos, o más. De hecho, un archivo de 20 MB que consta de 20 series de un millón de bloques de 1 KB cada una cabe con facilidad en un registro MFT, mientras que no cabría un archivo de 60 KB diseminado en 60 bloques aislados. Segundo, aunque la forma directa de representar cada par ocupa 2 x 8 bytes, existen métodos de compresión para reducir el tamaño de los pares a menos de 16 bytes. En la práctica, es común que los pares ocupen sólo 4 bytes. Nuestro primer ejemplo fue fácil: toda la información del archivo cabía en un solo registro MFT. Sin embargo, si el Escuela de Preparación de Opositores E.P.0. v05 INF19- SAI19. Página 24 archivo es tan grande o está tan fragmentado que la información de bloques no cabe en un registro MFT, se usan dos o más registros MFT. En la figura siguiente vemos un archivo cuyo registro base está en el registro MFT 102. Hay demasiadas series para u11 solo registro MFT, así que se calcula el número de registros de extensión necesarios y sus índices se colocan en el registro base. El resto del registro se usa para las primeras k series de datos. 03. ... Q2 10 oo ........._,.... ~__..,.,,... En teoría, no debería ser necesario especificar el final de una secuencia de series, porque esta información puede calcularse a partir de los pares de serie. El motivo para "sobreespecificar" esta información es hacer más eficiente el desplazamiento del brazo de disco: para encontrar un bloque que está a un desplazamiento dado de archivo, basta con examinar los encabezados de los registros; no es necesario examinar los pares de . sene. Cuando se ha ocupado todo el espacio del registro 102, el almacenamiento de las series continúa en el registro MFT 105. En este registro se meten tantas series como quepan. Cuando se llene también este registro, el resto de las series se guardan en el registro MFT 108. Así, pueden usarse muchos registros MFT para manejar archivos grandes fragmentados. Surge un problema si se necesitan tantos registros MFT que no haya suficiente espacio en el registro base para dar todos sus índices. Este problema tiene una solución: la lista de registros MFT de extensión se hace no residente (es decir, se almacena en disco y no en el registro MFT base). Así, podrá crecer hasta el tamaño necesario. En la figura siguiente se muestra una entrada de MFT para un directorio pequeño. El registro contiene varias entradas de directorio, cada una de las cuales describe un archivo o directorio. Cada entrada tiene una estructura de longitud fija seguida de un nombre de archivo de longitud variable. La parte fija contiene el índice de la entrada de MFT correspondiente al archivo, la longitud del nombre de archivo y otros campos e indicadores diversos. La búsqueda de una entrada en un directorio se efectúa examinando todos los nombres de archivo por turno. ..... • &:atzh1dlœ Una&mâde~oon--etlncl::eNFtdìi ¡,.,..lido de EticabeUdo 81QIM). la ~-nombtl dl mchhlo.el~ ftlbtnadõn ,I dlJ M\hM) yti;aDS QW:if)Ol B~ -~ enea.so Escuela de Preparación de Opositores E.P.O. v05 INF19- SAI19. Página 25 Los directorios grandes emplean un formato distinto. En lugar de enumerar los archivos de manera lineal, se utiliza un árbol B+ para poder efectuar una búsqueda alfabética y facilitar la inserción de nuevos nombres de archivo en el lugar correcto del directorio. 7 Conclusiones. Los implementadores del sistema de archivos deben preocuparse por llevar un registro de los bloques en disco correspondientes a cada archivo, la forma de compartir los archivos y la forma de administrar el espacio libre en disco. Los directorios se pueden ordenar de varias formas, en un rango que va desde colocar el nombre, atributos y direcciones en disco hasta sólo colocar en ellos el nombre y un número de nodo-i. Los archivos compartidos, el manejo de los bloque defectuosos, los respaldos, la consistencia y el caché también son temas importantes. En cuanto a la gestión de dispositivos hemos analizado el hardware de EIS y la relación de los dispositivos de E/S con los controladores de EIS, que son los que tienen que trabajar con el software. Después hemos analizado los cuatro niveles de software de E/S: las rutinas de interrupción, los manejadores de dispositivos, el software independiente de los dispositivos y las bibliotecas y spoolers de EIS que se ejecutan en el espacio del usuario. Las rutinas de interrupción guardan el estado de la máquina, después dan servicio al dispositivo y verifican los errores. En general, es recomendable utilizarlas lo menos posible, de manera consistente con el rendimiento requerido. Los manejadores de dispositivos controlan todos los detalles específicos de uno o más dispositivos. Su labor es ocultar los detalles engorrosos a los niveles superiores. El software independiente del dispositivo realiza cosas como el almacenamiento en buffers y la asignación. Este software es el mismo para varios dispositivos. En UNIX el sistema de archivos soporta archivos regulares, directorios y dos tipos de archivos especiales. Los directorios pueden contener subdirectorios, lo que conduce a un sistema jerárquico de archivos. La E/S se realiza mediante los archivos especiales de carácter y de bloque, los cuales se integran al sistema de archivos. El sistema de archivos utiliza tres tablas básicas: la tabla de descriptores de archivo, la tabla de descripción de archivos abiertos y la tabla de nodos-i. Cada archivo abierto tiene datos en estas tres tablas. El sistema de archivos de MS-DOS soporta los directorios jerárquicos, las rutas de acceso absolutas y relativas y muchas de las llamadas del sistema de archivos de UNIX, del cual tomaron su modelo. La EIS se realiza mediante archivos especiales, tanto de bloque como de carácter. El sistema de archivos se basa en el uso de una FAT para cada disco. Para cada archivo, la FAT contiene una cadena de bloques. Las entradas del directorio en MS-DOS contienen parte de la información que en UNIX estaba dentro de los nodos-i.