Interfaz del sistema de archivos PDF

Interfaz del sistema de archivos 11 Sistemas operativos y distribuidos Gustavo Distel [email protected] DCIC - UNS  Interfaz del sistema de archivos Contenido Concepto de archivo...

Interfaz del sistema de archivos 11 Sistemas operativos y distribuidos Gustavo Distel [email protected] DCIC - UNS  Interfaz del sistema de archivos Contenido Concepto de archivo. Métodos de acceso. Estructura del directorio. Protección. Archivos mapeados en memoria. 2 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos El sistema de archivos consta de dos partes: ○ Una colección de archivos, cada uno de los cuales almacena datos relacionados. ○ Una estructura de directorio, que organiza y proporciona información sobre todos los archivos del sistema. El SO abstrae las propiedades físicas de los dispositivos de almacenamiento para definir el archivo como una unidad lógica de almacenamiento. Los archivos se mapean a dispositivos físicos, los cuales generalmente son no volátiles (NVM, HDDs, cintas magnéticas y discos ópticos). Un archivo es una colección de información relacionada, asociada a un nombre que se graba en almacenamiento secundario, con un formato libre (como archivos de texto) o con un formato rígido. En general, un archivo es una secuencia de bits, bytes, líneas o registros, cuyo significado está definido por el creador y el usuario del archivo. 3 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Un archivo tiene una determinada estructura definida, que depende de su tipo. ○ Archivo de texto: es una secuencia de caracteres organizados en líneas (y quizás páginas). ○ Archivo fuente: es una secuencia de funciones, con declaraciones seguidas de sentencias ejecutables. ○ Archivo ejecutable: es una serie de secciones de código que el cargador (loader) puede llevar a memoria y ejecutar. 4 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Atributos de los archivos Un archivo se nombra con una cadena de caracteres, como i_wanna_rock.c. ○ Algunos sistemas diferencian mayúsculas y minúsculas y otros no. Los atributos de un archivo varían de un SO a otro, pero generalmente son: ○ Nombre: información que se mantiene en forma legible para el ser humano. ○ Identificador: etiqueta única, generalmente un número, identifica el archivo en el sistema de archivos; non-human-readable name. ○ Tipo: información necesaria para sistemas que admiten diferentes tipos de archivos. ○ Ubicación: puntero a un dispositivo y ubicación del archivo en ese dispositivo. ○ Tamaño: tamaño del archivo (en bytes, words o bloques) y posiblemente el tamaño máximo permitido. ○ Protección: información de control de acceso; quién puede leer, escribir, ejecutar, etc. ○ Marcas de tiempo e identificación de usuario: información de su creación, última modificación y último uso. Estos datos pueden ser útiles para la protección, seguridad y monitoreo de uso. 5 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Atributos de los archivos La información de todos los archivos se mantiene en la estructura de directorios, que reside en el mismo dispositivo que los archivos. Por lo general, una entrada de directorio consta del nombre del archivo y su identificador único. El identificador, a su vez, localiza los otros atributos del archivo. 6 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Operaciones de archivo Un archivo es un tipo de datos abstracto, razón por la cual, para definirlo correctamente, se deben considerar las operaciones que se pueden realizar sobre estos. ○ Crear un archivo: Para crear un archivo se necesitan dos pasos: primero, se debe encontrar espacio en el sistema de archivos para el archivo; segundo, se debe crear una entrada para el nuevo archivo en un directorio. ○ Abrir un archivo: En lugar de que cada operación de archivo deba especificar un nombre, lo que obliga al sistema operativo a evaluar el nombre, verificar los permisos de acceso, entre otros pasos, se utiliza una operación previa llamada open(). Esta operación, cuando se ejecuta correctamente, devuelve un identificador de archivo que se emplea como argumento en todas las operaciones posteriores, excepto en la creación y eliminación de archivos. ○ Escribir un archivo: Para escribir en un archivo, se realiza una llamada al sistema que incluye tanto el identificador del archivo abierto como la información que se desea escribir. El sistema debe gestionar un puntero de escritura que indique la ubicación en el archivo donde se llevará a cabo la próxima escritura, en caso de ser secuencial. Este puntero debe actualizarse cada vez que se realice una escritura. 7 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Operaciones de archivo Un archivo es un tipo de datos abstracto, razón por la cual, para definirlo correctamente, se deben considerar las operaciones que se pueden realizar sobre estos. ○ Leer un archivo: Para leer un archivo, se usa una llamada al sistema que indica el identificador del archivo y la ubicación en memoria para el bloque leído. El sistema gestiona un puntero de lectura que se actualiza tras cada operación, indicando la posición actual en el archivo. Este puntero, compartido para lectura y escritura, simplifica el sistema y ahorra espacio. ○ Reposicionamiento en un archivo: El puntero de posición actual de un archivo abierto se ajusta a un valor específico. Este reposicionamiento no requiere necesariamente realizar operaciones de entrada/salida. Esta acción también se conoce como búsqueda en el archivo. ○ Borrar/Eliminar un archivo: Para eliminar un archivo, primero se localiza su entrada en el directorio correspondiente. Una vez identificada, se libera el espacio ocupado por el archivo para que pueda ser reutilizado y se elimina o marca como disponible la entrada en el directorio. Es importante destacar que, en sistemas que permiten enlaces duros (múltiples nombres o entradas de directorio que apuntan al mismo archivo), el contenido del archivo no se elimina hasta que se elimine el último enlace. ○ Truncar un archivo: En lugar de eliminar el archivo y luego volver a crearlo, esta función permite que todos los atributos permanezcan sin cambios, excepto la longitud del archivo. El archivo se puede restablecer a cero liberando su espacio. 8 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Operaciones de archivo El SO mantiene una tabla, llamada tabla de archivos abiertos, que contiene información sobre todos los archivos abiertos. Cuando se solicita una operación de archivo, el archivo se especifica a través de un índice en esta tabla, por lo que no se requiere búsqueda. Cuando el archivo ya no se usa activamente, el proceso lo cierra y el SO elimina su entrada de la tabla de archivos abiertos, liberando potenciales bloqueos. Normalmente, el SO utiliza dos niveles de tablas internas: una tabla por proceso y una tabla de todo el sistema. La tabla por proceso tiene todos los archivos que un proceso ha abierto. En esta tabla se almacena información del uso del proceso sobre el archivo. 9 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Operaciones de archivo Cada entrada en la tabla por proceso apunta, a su vez, a una tabla de archivos abiertos en todo el sistema. La tabla de todo el sistema contiene información independiente del proceso, como la ubicación del archivo en el disco, las fechas de acceso y el tamaño del archivo. Una vez que un archivo ha sido abierto por un proceso, la tabla de todo el sistema incluye una entrada para ese archivo. Cuando otro proceso ejecuta una llamada open(), simplemente se agrega una nueva entrada a la tabla de archivos abiertos del proceso que apunta a la entrada en la tabla de todo el sistema. Por lo general, la tabla de archivos abiertos tiene un open count asociado con cada archivo, para indicar cuántos procesos lo han abierto. ○ Cada close() lo decrementa y al llegar a cero, el archivo ya no estará en uso y se elimina la entrada de la tabla de archivos abiertos. 10 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Operaciones de archivo En resumen, un archivo abierto cuenta con la siguiente información asociada: ○ Puntero de archivo: mantiene la última ubicación de lectura-escritura. Este puntero es único para cada proceso que opera en el archivo y, por lo tanto, debe mantenerse separado de los atributos del archivo en el disco. ○ Contador de archivos abiertos: a medida que se cierran los archivos, el SO debe reutilizar las entradas de la tabla de archivos abiertos o podría quedarse sin espacio en la tabla. Es posible que varios proc. hayan abierto un archivo y deba esperar a que se cierre el último antes de eliminar la entrada de la tabla de archivos abiertos. El contador de archivos abiertos mantiene el número de aperturas y cierres y llega a cero en el último cierre. Luego, el sistema puede eliminar la entrada. ○ Ubicación del archivo: información necesaria para ubicar el archivo, que se guarda en memoria para que el sistema, en cada operación, no tenga que leerla de la estructura de directorio. ○ Derechos de acceso: cada proceso abre un archivo en un modo de acceso. Esta información se almacena en una tabla por proceso, así el SO puede permitir o denegar posteriores solicitudes de E/S. 11 SOYD 2024 - Gustavo C. Distel Interfaz del sistema de archivos GNU/Linux 12 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos GNU/Linux La imagen anterior muestra la relación entre los descriptores de archivos, los descriptores de archivos abiertos y los i-nodos. En la imagen dos procesos tienen varios descriptores de archivos abiertos. En el proceso A, los descriptores 1 y 20 se refieren al mismo descriptor de archivo abierto, el 23. El descriptor 2 del proceso A y el descriptor 2 del proceso B se refieren a un único descriptor de archivo abierto, el 73. Este escenario podría ocurrir después de una llamada a fork() (es decir, el proceso A es el padre del proceso B, o viceversa). Finalmente, vemos que el descriptor 0 del proceso A y el descriptor 3 del proceso B se refieren a diferentes descripciones de archivos abiertos, pero que estos descriptores se refieren a la misma entrada de la tabla i-nodo, el 1976; en otras palabras, al mismo archivo. Esto ocurre porque cada proceso llamó independientemente a open() para el mismo archivo. Podría ocurrir una situación similar si un solo proceso abriera el mismo archivo dos veces. 13 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Operaciones de archivo Algunos SOs proporcionan facilidades para bloquear un archivo abierto: ○ Shared lock: similar a un lock de lector; varios procesos pueden adquirirlo al mismo tiempo. ○ Exclusive lock: similar a un lock escritor; solo puede adquirirlo un proceso a la vez. Además, se pueden proporcionar bloqueos obligatorios (mandatory) o de aviso (advisory). Bloqueo obligatorio: una vez que un proceso adquiere un bloqueo exclusivo, el SO evitará que cualquier otro proceso acceda al archivo bloqueado. Por ej., si un proceso adquiere un bloqueo exclusivo en el archivo system.log, si se intenta abrir desde otro proceso (como un editor de texto) el SO impedirá el acceso hasta que se libere el bloqueo exclusivo. 14 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Operaciones de archivo Bloqueo de aviso: es responsabilidad de los desarrolladores asegurarse de que los bloqueos se adquieran y liberen adecuadamente. El SO no impedirá que el editor de texto obtenga acceso a system.log. En realidad, el editor de texto debe programarse de modo que adquiera manualmente el bloqueo antes de acceder al archivo, a diferencia del bloqueo obligatorio que es el SO el que garantiza la integridad del bloqueo. Como regla general, los SOs Windows adoptan el bloqueo obligatorio, y los sistemas UNIX emplean bloqueos de aviso, es decir: ○ Linux: El acceso concurrente será posible a menos que las aplicaciones involucradas respeten los bloqueos establecidos. ○ Windows: El sistema bloqueará automáticamente cualquier acceso al archivo si está bloqueado. 15 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Tipos de archivo Una técnica común para implementar tipos de archivo es incluir el tipo como parte del nombre del archivo. ○ El nombre se divide en dos partes: un nombre y una extensión, generalmente separados por un punto (i_wanna_rock.mp3). ○ De esta manera, el usuario y el SO pueden saber solo por el nombre qué tipo de archivo es. El sistema usa la extensión para indicar el tipo de archivo y el tipo de operaciones que se pueden realizar en él. El sistema UNIX utiliza un número mágico almacenado al principio de algunos archivos binarios para indicar el tipo de datos del archivo (por ej., el formato de un archivo de imagen). Las extensiones pueden ser utilizadas o ignoradas por una aplicación determinada, pero eso depende del programador de la aplicación. En sistemas UNIX/Linux, el comando file identifica el tipo de datos de un archivo, examinando el contenido del archivo (incluyendo el número mágico si está presente) en lugar de confiar en la 16 extensión. SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Estructura de archivo Los tipos de archivo también se pueden usar para indicar la estructura interna del archivo. Algunos SOs soportan un conjunto de estructuras de archivos compatibles con el sistema, con operaciones especiales para manipular archivos con esas estructuras. Algunos SOs imponen (y admiten) un número mínimo de estructuras de archivos. Este enfoque ha sido adoptado en UNIX, Windows y otros. UNIX considera cada archivo como una secuencia de bytes (1 byte son 8-bits) y el SO no realiza ninguna interpretación de estos bits. Este esquema proporciona la máxima flexibilidad pero poco soporte. Cada programa debe incluir su propio código para interpretar un archivo. Sin embargo, todos los SOs deben admitir al menos una estructura, la de un archivo ejecutable, para que el sistema pueda cargar y ejecutar programas. 17 SOYD 2024 - Gustavo C. Distel  Interfaz del sistema de archivos Estructura interna de archivo Los discos tienen un tamaño de bloque bien definido, determinado por el tamaño de un sector. Todas las E/S de disco se realizan en unidades de un bloque (registro físico), y todos los bloques son del mismo tamaño. El tamaño del registro lógico, el tamaño del bloque físico y la técnica de empaquetado determinan cuántos registros lógicos hay en cada bloque físico. ○ El empaque puede realizarse por el programa del usuario o por el SO. En cualquier caso, el archivo puede considerarse una secuencia de bloques. Todas las funciones básicas de E/S operan en términos de bloques. Debido a que el espacio en disco siempre se asigna en bloques, una parte del último bloque de cada archivo generalmente se desperdicia (fragmentación interna). 18 SOYD 2024 - Gustavo C. Distel  Métodos de acceso Acceso secuencial La información en el archivo se procesa en orden, un registro después del otro. Este modo de acceso es el más común; por ej., lectores de texto y reproductores de música suelen acceder a los archivos de esta manera. El acceso secuencial se basa en un modelo de cinta de un archivo y funciona bien tanto en dispositivos de acceso secuencial como en los de acceso aleatorio. Operaciones: ○ read_next(). ○ write_next(). 19 SOYD 2024 - Gustavo C. Distel  Métodos de acceso Acceso directo Un archivo está formado por registros lógicos de longitud fija que permiten a los programas leer y escribir registros rápidamente sin ningún orden en particular. Se basa en un modelo de disco, ya que los discos permiten el acceso aleatorio a cualquier bloque de archivos. El archivo se ve como una secuencia numerada de bloques o registros. Por lo tanto, podemos leer el bloque 14, luego leer el bloque 53 y luego escribir el bloque 7. No hay restricciones en el orden de lectura o escritura. Los archivos de acceso directo son de gran utilidad para el acceso inmediato a grandes cantidades de información. Las bases de datos son a menudo de este tipo. Operaciones: ○ read(n). ○ write(n). 20 SOYD 2024 - Gustavo C. Distel  Métodos de acceso Otros métodos de acceso Se pueden construir otros métodos de acceso sobre un método de acceso directo. Estos métodos generalmente implican la construcción de un índice para el archivo. El índice, como un índice en la parte posterior de un libro, contiene punteros a los distintos bloques. Para encontrar un registro en el archivo, primero buscamos el índice y luego usamos el puntero para acceder al archivo directamente y encontrar el registro deseado. 21 SOYD 2024 - Gustavo C. Distel  Estructura de directorios El directorio puede considerarse como una tabla de símbolos que traduce nombres de archivo en sus bloques de control. Al considerar una estructura de directorio en particular, se debe tener en cuenta las operaciones que se realizarán: ○ Buscar un archivo. ○ Crear un archivo. ○ Eliminar un archivo. ○ Listar un directorio. ○ Cambiar el nombre de un archivo. ○ Recorrer el sistema de archivos. 22 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorio de un solo nivel Todos los archivos están contenidos en el mismo directorio, que es fácil de mantener y comprender. Sin embargo, un directorio de un solo nivel tiene limitaciones significativas cuando aumenta el número de archivos o cuando el sistema tiene más de un usuario. Como todos los archivos están en el mismo directorio, deben tener nombres únicos. La mayoría de los sistemas de archivos admiten nombres de hasta 255 caracteres (MS-DOS permitia 11), por lo que es relativamente fácil seleccionar nombres de archivo únicos. Incluso un usuario con directorios de un solo nivel puede tener dificultades para recordar los nombres de todos los archivos a medida que aumenta su número. 23 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorio de dos niveles En la estructura de directorios de dos niveles, cada usuario tiene su propio directorio de usuario (UFD - user file directory). Los UFD tienen estructuras similares, pero cada uno tiene los archivos de un solo usuario. Cuando se inicia un trabajo de usuario o un usuario inicia sesión, se busca en el directorio maestro de archivos (MFD - master file directory) del sistema. El MFD se indexa por nombre de usuario o número de cuenta, y cada entrada apunta al UFD de dicho usuario. 24 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorio de dos niveles Aunque la estructura de directorios de dos niveles resuelve el problema de colisión de nombres, aún tiene desventajas. Esta estructura aísla efectivamente a un usuario de otro. El aislamiento es una ventaja cuando los usuarios son completamente independientes, pero es una desventaja cuando los usuarios desean cooperar en alguna tarea y acceder a los archivos de los demás. Algunos sistemas simplemente no permiten que un usuario acceda a los archivos locales de otro usuario. Si se permite el acceso, un usuario debe tener la capacidad de nombrar un archivo en el directorio de otro usuario. Para nombrar un archivo en particular de forma única en un directorio de dos niveles, debemos proporcionar tanto el nombre de usuario como el nombre del archivo. 25 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorio de dos niveles Un directorio de dos niveles puede considerarse como un árbol, o un árbol invertido, de altura 2. La raíz del árbol es el MFD, sus descendientes directos son los UFD, los descendientes de los UFD son los propios archivos y los archivos son las hojas del árbol. La especificación de un nombre de usuario y un nombre de archivo define una ruta en el árbol desde la raíz (el MFD) hasta una hoja (el archivo especificado). Por lo tanto, un nombre de usuario y un nombre de archivo definen un nombre de ruta. Cada archivo en el sistema tiene un nombre de ruta. Para nombrar un archivo de forma única, el usuario debe conocer el nombre de la ruta del archivo deseado. 26 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorios estructurados en árbol Los árboles son la estructura de directorios más común. El árbol tiene un directorio raíz, y cada archivo en el sistema tiene una única ruta. Un directorio (o subdirectorio) contiene un conjunto de archivos o subdirectorios. Un directorio es simplemente otro archivo, pero se trata de manera especial. Un bit en cada entrada del directorio define la entrada como un archivo (0) o como un subdirectorio (1). 27 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorios estructurados en árbol Cada proceso tiene un directorio actual (current directory). El directorio actual debe contener la mayoría de archivos que son de interés actual para el proceso. Cuando se hace referencia a un archivo, se busca en el directorio actual. Si se necesita un archivo que no está en el directorio actual, entonces el usuario generalmente debe especificar un nombre de ruta o cambiar el directorio actual para indicar el directorio que contenga ese archivo. Cuando se inicia un trabajo de usuario o cuando el usuario inicia sesión en la shell, se establece un directorio actual. A partir de esa shell, se pueden generar otros procesos. El directorio actual de cualquier subproceso suele ser el directorio del padre cuando fue creado. 28 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorios estructurados en árbol Los nombres de ruta pueden ser de dos tipos: absolutos y relativos. ○ En UNIX y Linux, un nombre de ruta absoluto comienza en la raíz (que se designa con una "/" inicial) y sigue una ruta hasta el archivo especificado, indicando los nombres de directorio en la ruta. ○ Un nombre de ruta relativo define una ruta desde el directorio actual. Por ej., si el directorio actual es /spell/mail , el nombre de ruta relativo prt/first se refiere al mismo archivo que el nombre de ruta absoluto /spell/mail/prt/first. Con esta estructura se puede permitir a los usuarios acceder a los archivos de otros usuarios. ○ Por ej., el usuario B puede acceder a un archivo del usuario A especificando la ruta. ○ El usuario B puede especificar una ruta absoluta o relativa. Alternativamente, el usuario B puede cambiar su directorio actual para que sea el directorio del usuario A y acceder al archivo por su nombre. 29 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorios de grafos acíclicos Una estructura de árbol prohíbe compartir archivos o directorios. Un gráfico acíclico (es decir, un gráfico sin ciclos) permite que los directorios compartan subdirectorios y archivos. El mismo archivo o subdirectorio puede estar en dos directorios diferentes. El gráfico acíclico es una generalización natural del esquema de directorio con estructura de árbol. 30 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorios de grafos acíclicos Los archivos y subdirectorios compartidos se pueden implementar de varias maneras; en UNIX por ej., se crea una nueva entrada de directorio llamada enlace (link). Un enlace es, en la práctica, un puntero a otro archivo o subdirectorio. Por ej., un enlace puede implementarse como un nombre de ruta absoluto o relativo. Cuando se hace una referencia a un archivo, buscamos en el directorio. Si la entrada del directorio está marcada como un enlace, el nombre del archivo real se incluye en la información del enlace. Resolvemos el enlace utilizando ese nombre de ruta para localizar el archivo real. El SO ignora estos enlaces al atravesar árboles de directorios para preservar la estructura acíclica del sistema. Una estructura de directorio de grafo acíclico es más flexible que una estructura de árbol simple, pero también más compleja. Varios problemas deben considerarse: ○ Un archivo puede tener múltiples nombres de ruta absolutos. ○ Otro problema implica la eliminación, dado que pueden quedar punteros colgados. 31 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorios de grafos general Cuando se agregan enlaces a un estructura de árbol ésta se destruye, lo que resulta en una estructura de grafo simple. Si se permite que existan ciclos en los directorios, se debe evitar buscar un componente dos veces, por razones de corrección y rendimiento. Un alg. mal diseñado podría dar como resultado un bucle infinito que busca continuamente a través del ciclo y nunca termina. 32 SOYD 2024 - Gustavo C. Distel  Estructura de directorios Directorios de grafos general Existe un problema similar cuando intentamos determinar cuándo se puede eliminar un archivo. Con los grafos acíclicos, un valor de 0 en las referencias significa que no hay más referencias al archivo o directorio, y el archivo se puede eliminar. Sin embargo, cuando existen ciclos, la cantidad de referencias puede no ser 0 incluso cuando ya no sea posible hacer referencia a un directorio o archivo. Esta anomalía resulta de la posibilidad de autorreferencia (o un ciclo) en la estructura del directorio. En estos casos generalmente se necesita usar un garbage collection. Un garbage collector recorre todo el sistema de archivos, marcando todo lo que se puede acceder. Luego, en una segunda pasada recoge todo lo que no está marcado en una lista de espacio libre. Un garbage collector consume mucho tiempo y, por lo tanto, rara vez se utiliza. 33 SOYD 2024 - Gustavo C. Distel  Protección La información en un sistema informático se debe resguardar de daños físicos (confiabilidad - reliability) y del acceso inadecuado (protección - protection). La confiabilidad se logra, en general, mediante la duplicación de archivos (backups (copias de seguridad)). Contar con programas de sistema que copien automáticamente, o con intervención del operador, los archivos del disco a la cinta en intervalos regulares (diarios, semanales o mensuales), para preservar una copia en caso de destrucción accidental del sistema de archivos. ○ Los sistemas de archivos pueden dañarse por problemas de HW, como errores de lectura/escritura, subidas o bajadas de tensión, caídas del cabezal, suciedad, temperaturas extremas, vandalismo o eliminación accidental. Además, errores en el SW del sistema de archivos pueden ocasionar la pérdida del contenido de los archivos. La protección se puede proporcionar de varias maneras. ○ Para una notebook, se puede brindar protección al requerir nombre de usuario y contraseña para autenticación en el SO, encriptar el almacenamiento secundario y utilizar firewall. ○ En un sistema multiusuario se necesitan mecanismos más avanzados para permitir solo el acceso válido de los datos. 34 SOYD 2024 - Gustavo C. Distel  Protección Tipos de accesos Los mecanismos de protección proporcionan acceso controlado al limitar los tipos de acceso que se pueden realizar. Se pueden controlar varios tipos de operaciones: ○ Leer: leer del archivo. ○ Escribir: escribir o reescribir el archivo. ○ Ejecutar: cargar el archivo en la memoria y ejecutarlo. ○ Añadir: escribir nueva información al final del archivo. ○ Eliminar: eliminar el archivo y liberar espacio para su posible reutilización. ○ Lista: listar el nombre y los atributos del archivo. ○ Cambio de atributo: cambiar los atributos del archivo. 35 SOYD 2024 - Gustavo C. Distel  Protección Control de acceso El esquema más general es asociar a cada archivo y directorio una lista de control de acceso (access control list - ACL) que especifique los nombres de usuario y los tipos de acceso permitidos para cada usuario. Cuando un usuario solicita acceso a un archivo en particular, el SO verifica la lista de acceso asociada con ese archivo. ○ Si ese usuario aparece en la lista para el acceso solicitado, se permite el acceso. ○ De lo contrario, se produce una violación de protección y el usuario no tendrá acceso al archivo. Este enfoque tiene la ventaja de permitir metodologías de acceso complejas. El principal problema con las listas de acceso es su longitud. Si queremos permitir que todos lean un archivo, debemos enumerar todos los usuarios con acceso de lectura. 36 SOYD 2024 - Gustavo C. Distel  Protección Control de acceso Esta técnica tiene dos consecuencias indeseables: ○ La construcción de la lista puede ser una tarea tediosa, especialmente si no conocemos de antemano la lista de usuarios en el sistema. ○ La entrada del directorio, anteriormente de tamaño fijo, ahora debe ser de tamaño variable, lo que resulta en una administración de espacio más complicada. Estos problemas pueden resolverse mediante el uso de una versión condensada de la lista de acceso; muchos sistemas reconocen tres clasificaciones de los usuarios: ○ Propietario: el usuario que creó el archivo es el propietario. ○ Grupo: un conjunto de usuarios que comparten el archivo y necesitan acceso similar conforman un grupo o grupo de trabajo. ○ Otros: todos los demás usuarios en el sistema. Un enfoque común es combinar ACLs con el esquema de control de acceso de propietario, grupo y universo. 37 SOYD 2024 - Gustavo C. Distel  Protección Control de acceso: permisos en Linux 38 SOYD 2024 - Gustavo C. Distel  Protección Control de acceso: permisos en FreeNAS (FreeBSD) 39 SOYD 2024 - Gustavo C. Distel  Protección Control de acceso: permisos en masOS Catalina 40 SOYD 2024 - Gustavo C. Distel  Protección Control de acceso: permisos en Windows 41 SOYD 2024 - Gustavo C. Distel  Archivos mapeados en memoria Sea una lectura secuencial de un archivo en disco utilizando las llamadas estándar del sistema open(), read() y write(). ○ Cada acceso al archivo requiere una llamada al sistema y un acceso al disco. Alternativamente, podemos usar las técnicas de memoria virtual para tratar la E/S de archivos como accesos a memoria. Este enfoque permite que una parte del espacio de direcciones virtuales se asocie lógicamente con el archivo. Esto puede aumentar significativamente en el rendimiento. 42 SOYD 2024 - Gustavo C. Distel  Archivos mapeados en memoria Mecanismo básico La asignación de memoria de un archivo se realiza asignando un bloque de disco a una página (o páginas) en la memoria. El acceso inicial al archivo se realiza mediante paginación por demanda ordinaria, lo que resulta en un page fault. Sin embargo, una parte del archivo del tamaño de una página se lee desde el sistema de archivos en una página física. Las lecturas y escrituras posteriores en el archivo se manejan con rutinas de accesos a memoria. Manipular archivos a través de memoria, en lugar de incurrir en la sobrecarga de usar las llamadas al sistema read() y write(), simplifica y acelera el acceso y uso de los archivos. Se debe considerar que las escrituras en el archivo asignado en la memoria no son necesariamente escrituras inmediatas (sincrónicas) en el archivo en el almacenamiento secundario. En general, el archivo se actualiza cuando se cierra. 43 SOYD 2024 - Gustavo C. Distel  Archivos mapeados en memoria Mecanismo básico Se puede permitir a múltiples procesos mapear el mismo archivo permitiendo intercambiar datos. Las escrituras de cualquiera de los procesos modifican los datos en la memoria virtual y serán vistos por todos los que mapean la misma sección del archivo. Las llamadas al sistema de mapeo de memoria también pueden admitir la funcionalidad de copy-on-write, lo que permite que los procesos compartan un archivo en modo de lectura pero tengan las copias de cualquier dato que modifiquen. 44 SOYD 2024 - Gustavo C. Distel Implementación del sistema de archivos 12 Sistemas operativos y distribuidos Gustavo Distel [email protected] DCIC - UNS  Implementación del sistema de archivos Contenido Estructura del sistema de archivos. Operaciones del sistema de archivos. Métodos de asignación. Gestión del espacio libre. 46 SOYD 2024 - Gustavo C. Distel  Implementación del sistema de archivos Un sistema operativo de propósito general proporciona diversos sistemas de archivos, permitiendo además agregar otros. Los sistemas de archivos varían en muchos aspectos, tales como sus características, el rendimiento, la confiabilidad, los objetivos de diseño y, a su vez, pueden tener diferentes propósitos. Por ejemplo, se utiliza un sistema de archivos temporal para el almacenamiento y la recuperación rápida de archivos no persistentes, mientras que para el sistema de archivos de almacenamiento secundario (como ext4 en GNU/Linux) se sacrifica rendimiento por confiabilidad y por tener más características. 47 SOYD 2024 - Gustavo C. Distel  Estructura del sistema de archivos La mayor parte del almacenamiento secundario lo proporcionan los discos duros, donde se mantienen los sistemas de archivos. Los discos duros son convenientes por dos características: ○ Es posible leer un bloque del disco, modificarlo y volver a escribirlo. ○ Se puede acceder directamente a cualquier bloque de información, por lo tanto, es sencillo acceder a cualquier archivo de forma secuencial o aleatoria; cambiar de un archivo a otro requiere que la unidad mueva los cabezales de lectura y escritura y esperar a que gire. Los dispositivos de memoria no volátil (NVM - Nonvolatile memory) se utilizan cada vez más para el almacenamiento de archivos, y hoy en día están reemplazando por completo a los discos duros tradicionales. 48 SOYD 2024 - Gustavo C. Distel  Estructura del sistema de archivos Para mejorar la eficiencia, las transferencias de E/S entre la memoria y el almacenamiento masivo se realizan en unidades de bloques(blocks). Cada bloque de una unidad de disco duro tiene uno o más sectores; dependiendo de la unidad de disco, el tamaño del sector suele ser de 512 bytes o 4096 bytes. Los dispositivos NVM suelen tener bloques de 4.096 bytes y los métodos de transferencia son similares a los utilizados por las unidades de disco. Los sistemas de archivos brindan un acceso eficiente y conveniente al dispositivo de almacenamiento al permitir que los datos se almacenen, ubiquen y recuperen fácilmente. Un sistema de archivos plantea dos problemas de diseño bastante diferentes: ○ Definir cómo debe verse el sistema de archivos para el usuario. Esta tarea implica definir un archivo y sus atributos, las operaciones permitidas en un archivo y la estructura de directorios para organizar archivos. ○ Crear algoritmos y estructuras de datos para mapear el sistema de archivos lógico en los dispositivos físicos de almacenamiento secundario. 49 SOYD 2024 - Gustavo C. Distel  Estructura del sistema de archivos El sistema de archivos en sí, se compone generalmente de muchos niveles diferentes. La estructura que se muestra en la imagen es un ejemplo de diseño en capas. Cada nivel utiliza las características de los niveles inferiores para crear nuevas características para uso de los niveles superiores. El nivel de control de E/S consta de controladores de dispositivos (device drivers) y manejadores de interrupciones (interrupt handlers) para transferir información entre la memoria principal y el sistema del disco. 50 SOYD 2024 - Gustavo C. Distel  Estructura del sistema de archivos Un controlador de dispositivo es como un traductor. Su entrada consta de comandos de alto nivel, como "recuperar el bloque 123" y su salida consta de instrucciones de bajo nivel específicas del HW que utiliza el controlador que conecta el dispositivo de E/S con el resto del sistema. El controlador del dispositivo generalmente escribe patrones de bits específicos en ubicaciones especiales en la memoria del controlador de E/S para indicarle al controlador en qué ubicación del dispositivo actuar y qué acciones tomar. El sistema de archivos básico (llamado “block I/O subsystem” en GNU/Linux) envía comandos genéricos al controlador de dispositivo para leer y escribir bloques en el dispositivo de almacenamiento. Envía comandos a la unidad basándose en direcciones de bloques lógicos. También se ocupa de la planificación de solicitudes de E/S, buffers de memoria y cachés que contienen varios sistemas de archivos, directorios y bloques de datos. 51 SOYD 2024 - Gustavo C. Distel  Estructura del sistema de archivos El módulo de organización de archivos conoce los archivos y sus bloques lógicos, los cuales están numerados en cada archivo del 0 (o 1) a N. También incluye el administrador de espacio libre, que rastrea los bloques no asignados y los proporciona a este módulo cuando se solicitan. El sistema de archivos lógico gestiona la información de metadatos, que incluyen toda la estructura del sistema de archivos excepto los datos reales (o el contenido de los archivos). También gestiona la estructura de directorios para proporcionar al módulo de organización de archivos la información que éste necesita, dándole un nombre de archivo simbólico. Mantiene la estructura de archivos a través de bloques de control de archivos. Un bloque de control de archivos (file control block - FCB) (un inodo en los sistemas de archivos UNIX) contiene información sobre el archivo, incluida la propiedad, los permisos y la ubicación del contenido del archivo. 52 SOYD 2024 - Gustavo C. Distel  Estructura del sistema de archivos Cuando se utiliza una estructura en capas para la implementación del sistema de archivos, se minimiza la duplicación de código. El control de E/S y, a veces, el código del sistema de archivos básico pueden ser utilizados por múltiples sistemas de archivos. Cada sistema de archivos puede tener su propio sistema de archivos lógico y su módulo de organización de archivos. Desafortunadamente, las capas pueden generar una mayor sobrecarga del sistema operativo, lo que puede resultar en una disminución del rendimiento. El uso de capas, incluida la decisión sobre cuántas capas usar y qué debe hacer cada capa, es un desafío importante en el diseño de nuevos sistemas. 53 SOYD 2024 - Gustavo C. Distel  Operaciones del sistema de archivos Descripción general Para implementar un sistema de archivos se utilizan varias estructuras en memoria y en almacenamiento. Estas estructuras varían según el sistema operativo y el sistema de archivos, pero se aplican algunos principios generales. En el almacenamiento, el sistema de archivos puede contener información sobre cómo arrancar un sistema operativo almacenado allí, la cantidad total de bloques, la cantidad y la ubicación de los bloques libres, la estructura de directorios y los archivos individuales. ○ Un bloque de control de arranque (por volumen) puede contener la información que necesita el sistema para arrancar un SO desde ese volumen. Si el disco no contiene un SO, este bloque puede estar vacío. Normalmente es el primer bloque de un volumen. En UFS, se denomina bloque de arranque (boot block). En NTFS, es el sector de arranque de la partición (partition boot sector). ○ Un bloque de control de volumen (por volumen) contiene detalles del volumen, como la cantidad de bloques en el volumen, el tamaño de los bloques, un recuento de bloques libres y punteros de bloques libres, y un recuento de FCB libres y punteros de FCB. En UFS, esto se denomina superbloque. En NTFS, se almacena en la tabla maestra de archivos. 54 SOYD 2024 - Gustavo C. Distel  Operaciones del sistema de archivos Descripción general Se utiliza una estructura de directorios (por sistema de archivos) para organizar los archivos. En UFS, ○ esto incluye los nombres de archivo y los números de inodo asociados. En NTFS, se almacena en la tabla maestra de archivos. ○ Un FCB de un archivo contiene muchos detalles sobre el archivo. Tiene un número de identificación único que permite asociarlo con una entrada de directorio. En NTFS, esta información se almacena en realidad dentro de la tabla maestra de archivos, que utiliza una estructura de base de datos relacional, con una fila por archivo. La información en memoria se utiliza tanto para la gestión del sistema de archivos como para la mejora del rendimiento mediante el almacenamiento en caché. Los datos se cargan en el momento del montaje, se actualizan durante las operaciones del sistema de archivos y se descartan en el momento del desmontaje. Se pueden incluir varios tipos de estructuras. ○ Una tabla de montaje en memoria contiene información sobre cada volumen montado. ○ Un caché de estructura de directorio en memoria contiene la información de directorios a los que se accedió recientemente (en el caso de directorios en los que se montan volúmenes, puede contener un puntero a la tabla de volúmenes). 55 SOYD 2024 - Gustavo C. Distel  Operaciones del sistema de archivos Descripción general La tabla de archivos abiertos de todo el sistema contiene una copia del FCB de cada archivo ○ abierto, así como otra información. ○ La tabla de archivos abiertos por proceso contiene punteros a las entradas apropiadas en la tabla de archivos abiertos de todo el sistema, así como otra información, para todos los archivos que el proceso ha abierto. ○ Los buffers contienen bloques del sistema de archivos cuando se leen o escriben en un sistema de archivos. Para crear un nuevo archivo, un proceso llama al sistema de archivos lógico. El sistema de archivos lógico conoce el formato de las estructuras de directorios. Para crear un nuevo archivo, asigna un nuevo FCB (alternativamente, si la implementación del sistema de archivos crea todos los FCB en el momento de creación del sistema de archivos, se asigna un FCB del conjunto de FCB libres). A continuación, el sistema lee el directorio apropiado en la memoria, lo actualiza con el nuevo nombre de archivo y FCB, y lo vuelve a escribir en el sistema de archivos. 56 SOYD 2024 - Gustavo C. Distel  Métodos de asignación La naturaleza de acceso directo del almacenamiento secundario nos da flexibilidad en la implementación de archivos. El principal problema es cómo asignar espacio a los archivos para que el espacio de almacenamiento se utilice de manera eficaz y se pueda acceder rápidamente a los archivos. Principalmente se utilizan tres métodos de asignación de espacio de almacenamiento secundario: ○ Contiguo. ○ Enlazado. ○ Indexado. 57 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación contigua Cada archivo ocupa un conjunto de bloques contiguos en el dispositivo. El acceso al bloque b + 1 después del bloque b requiere pocos movimientos en un disco HDD. Un archivo se define por la dirección del primer bloque y la longitud (en bloques) del archivo. Si el archivo tiene n bloques de largo y comienza en la ubicación b, entonces ocupa los bloques b, b + 1, b + 2,..., b + n - 1. La entrada del directorio para cada archivo indica la dirección del bloque de inicio y la longitud asignada para el archivo. La asignación contigua es fácil de implementar pero tiene limitaciones y, por lo tanto, no se usa en los sistemas de archivos modernos. 58 SOYD 2024 - Gustavo C. Distel Métodos de asignación Asignación contigua 59 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación contigua Acceso secuencial: el sistema de archivos mantiene la dirección del último bloque al que se hace referencia y, cuando es necesario, lee el siguiente bloque. Acceso directo: para acceder al bloque i de un archivo que comienza en el bloque b, se accede inmediatamente al bloque b + i. Desventajas: ○ Encontrar espacio para un archivo nuevo. Idem a los problemas de asignación de memoria contigua, los cuales tienen fragmentación externa. ○ Determinar cuánto espacio se necesita para un archivo. Estas desventajas pueden ser minimizadas con un esquema de asignación contigua modificado, donde se utilizan extents: conjunto contiguo de bloques los cuales, a su vez, están enlazados. Si los extents son grandes habrá fragmentación interna. Habrá fragmentación externa a medida que se asignen y desasignen extents de diferentes tamaños. 60 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación contigua: ejemplo Considerar un sistema que utiliza asignación contigua y asumiendo que: ○ El bloque de control de archivo se encuentra en memoria. ○ El bloque con información a agregar se encuentra en memoria. ○ En el cálculo de la cantidad operaciones de E/S, si la ubicación del primer bloque del archivo cambia, no incluir la operación necesaria para reescribir esa información en la entrada de directorio del disco. ○ Hay espacio para que el archivo crezca al final, pero no al principio. ○ El bloque del medio es el 25to bloque. ○ No incluir ninguna operación de E/S para agregar o remover un bloque de la lista de espacio libre. ¿Cuántas operaciones de lectura y escritura se requieren para agregar o remover un bloque de un archivo de 50 bloques para cada uno de los siguientes casos? Si el bloque: ○ a) Se agrega al inicio. ○ b) Se agrega después del bloque del medio. ○ c) Se agrega al final. ○ d) Se elimina del inicio. ○ e) Se elimina del medio. ○ f) Se elimina del final. 61 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación contigua: ejemplo Respuestas: ○ a)Se agrega al inicio: 101; cada bloque de todo el archivo debe desplazarse sobre el siguiente bloque (una lectura y una escritura por cada bloque) y luego se escribe el nuevo bloque al inicio. ○ b)Se agrega después del bloque del medio: 51; la segunda mitad, que consta de 25 bloques, debe desplazarse sobre el siguiente bloque y luego se escribe el nuevo bloque. ○ c)Se agrega al final: 1; solo se escribe el nuevo bloque al final. ○ d)Se elimina del inicio: 0 o 98 0: simplemente se actualiza el puntero de entrada al directorio para que apunte al segundo bloque. 98: se mueven todos los bloques desde el segundo bloque hasta el final un bloque, lo que requiere 49 operaciones de lectura y 49 operaciones de escritura. ○ e)Se elimina del medio: 50; para eliminar el bloque 25, se deben mover 25 bloques de a un bloque, lo que requiere una operación de lectura y una de escritura por cada uno. ○ f)Se elimina del final: 0; se actualiza la información de longitud en memoria. 62 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación enlazada La asignación enlazada resuelve los problemas de la asignación contigua. Cada archivo es una lista enlazada de bloques, que pueden estar dispersos en cualquier parte del dispositivo. El directorio contiene un puntero al primer y último bloque del archivo. Por ej., un archivo de cinco bloques puede comenzar en el bloque 9 y continuar en el bloque 16, luego el bloque 1, luego el bloque 10 y finalmente el bloque 25. Cada bloque contiene un puntero al siguiente bloque, los cuales no están disponibles para el usuario. Por lo tanto, si cada bloque tiene un tamaño de 512 bytes y una dirección de bloque (el puntero) requiere 4 bytes, entonces el usuario ve bloques de 508 bytes. 63 SOYD 2024 - Gustavo C. Distel Métodos de asignación Asignación enlazada 64 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación enlazada Para crear un archivo se agrega una nueva entrada en el directorio; cada entrada de directorio tiene un puntero al primer bloque, el cual se inicializa en null indicando un archivo vacío. No hay fragmentación externa y no es necesario declarar el tamaño de un archivo al crearlo. Desventajas: ○ Solo se puede usar de manera efectiva para archivos de acceso secuencial. Para encontrar el bloque i-ésimo de un archivo, debemos comenzar al principio de ese archivo y seguir los punteros hasta llegar al bloque i-ésimo. Cada acceso a un puntero requiere una lectura al dispositivo de almacenamiento. En consecuencia, es ineficiente para el acceso directo. ○ El espacio de los punteros: si un puntero requiere 4 bytes de un bloque de 512 bytes, entonces el 0.78% del disco se está utilizando para punteros, en lugar de información. ○ Confiabilidad (reliability). 65 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación enlazada La solución habitual a este problema es reunir múltiples bloques, llamados clusters, y asignar clusters en lugar de bloques. Los punteros usan un porcentaje menor del espacio del archivo. Este método mejora el rendimiento del HDD (se requieren menos búsquedas de la cabeza del disco) y disminuye el espacio y gestión de la lista de espacio libre. El costo de este enfoque es que aumenta la fragmentación interna. Los clusters se pueden usar para mejorar el tiempo de acceso a disco para muchos otros algoritmos, por lo que se usan en la mayoría de los sistemas de archivos. Otro problema es la confiabilidad (reliability). ○ Un bug en SW del SO o una falla de HW puede dar lugar a un puntero equivocado. Este error a su vez podría dar lugar a un enlace a la lista de espacio libre o a otro archivo. ○ Una solución parcial es usar listas doblemente enlazada, y otra es almacenar el nombre del archivo y el número de bloque relativo en cada bloque. Sin embargo, estos esquemas requieren aún más sobrecarga para cada archivo. 66 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación enlazada Una variación es el uso de una tabla de asignación de archivos (file allocation table, FAT). Al comienzo de cada volumen se reserva espacio para la tabla, la cual tiene una entrada para cada bloque y está indexada por número de bloque. La entrada de directorio contiene el número de bloque del primer bloque del archivo. ○ La entrada de la tabla indexada por ese número de bloque contiene el número de bloque del siguiente bloque en el archivo. ○ Esta cadena continúa hasta llegar al último bloque, que tiene un valor especial de final de archivo como entrada de la tabla. Un bloque no utilizado se indica mediante un valor de tabla de 0. ○ Asignar un nuevo bloque a un archivo consta en encontrar la primer entrada de la tabla con valor 0 y reemplazar el valor de fin de archivo anterior con la dirección del nuevo bloque. Un ejemplo ilustrativo de la estructura FAT se muestra a continuación para un archivo con bloques de disco 217, 618 y 339. 67 SOYD 2024 - Gustavo C. Distel Métodos de asignación Asignación enlazada 68 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación enlazada: ejemplo Respuestas: ○ a)Se agrega al inicio: 1; se escribe el nuevo bloque, haciendo que apunte al siguiente bloque y luego se actualiza el primer puntero del bloque en memoria. ○ b)Se agrega después del bloque del medio: 27; para posicionarse en el medio se deben leer 25 bloques. Posteriormente, se necesita una escritura del nuevo nodo apuntando al bloque 26 anterior. Se necesita otra escritura para escribir el bloque 25 y que apunte al nuevo bloque. ○ c)Se agrega al final: 3; primero se debe leer el último bloque, dado por puntero al último bloque y, entonces, se escribe el nuevo bloque. A continuación, el último bloque leído anteriormente se vuelve a escribir con el puntero del siguiente bloque modificado para apuntar al nuevo bloque. Al final, el puntero al último bloque se actualiza en memoria. ○ d)Se elimina del inicio: 1; se lee el primer bloque para llegar al puntero del segundo bloque y luego el puntero de la entrada del directorio se actualiza para apuntar al segundo bloque. ○ e)Se elimina del medio: 26; para encontrar el puntero al bloque 26, son necesarias 25 lecturas. Luego, el siguiente puntero del bloque 24 se actualiza con este valor. ○ f)Se elimina del final: 50; el puntero del bloque de cola debe actualizarse para que apunte al anterior al último bloque y la única forma de obtener el penúltimo bloque es leer los 49 bloques anteriores. Luego, el siguiente puntero del bloque 49 debe actualizarse a un puntero nulo. Se actualiza el puntero a la cola en memoria. 69 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación indexada La asignación enlazada resuelve los problemas de fragmentación externa y la declaración de tamaño de la asignación contigua. Pero el acceso directo no es eficiente, ya que los punteros a los bloques están dispersos con bloques en todo el disco y deben recuperarse en orden. La asignación indexada resuelve este problema al reunir todos los punteros en una ubicación: el bloque índice. Cada archivo tiene su propio bloque índice, que es una matriz de direcciones de bloques. La i-ésima entrada en el bloque índice apunta al i-ésimo bloque del archivo. El directorio contiene la dirección del bloque índice. Para encontrar y leer el bloque i-ésimo, usamos el puntero en la entrada i-ésima del bloque índice. 70 SOYD 2024 - Gustavo C. Distel Métodos de asignación Asignación indexada 71 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación indexada Cuando se crea el archivo, todos los punteros en el bloque índice se setean a null. Cuando el bloque i-ésimo se escribe por primera vez, se obtiene un bloque del espacio libre y su dirección se coloca en la entrada i-ésima del bloque índice. Admite acceso directo, sin fragmentación externa, porque cualquier bloque libre en el dispositivo de almacenamiento puede satisfacer la solicitud. Sin embargo, se desperdicia espacio. ○ La sobrecarga de punteros en el bloque índice es generalmente mayor que la sobrecarga de punteros en la asignación enlazada. ○ Considere el caso que se tiene un archivo de uno o dos bloques. Con la asignación enlazada, perdemos el espacio de solo un puntero por bloque. Con la asignación indexada, se debe asignar un bloque índice completo, incluso si solo uno o dos punteros son distintos de null. 72 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación indexada Entonces se plantea la cuestión de qué tamaño debe tener el bloque de índice. Cada archivo debe tener un bloque de índice, por lo que queremos que el bloque de índice sea lo más pequeño posible. Sin embargo, si el bloque de índice es demasiado pequeño, no podrá contener suficientes punteros para un archivo grande y deberá estar disponible un mecanismo para lidiar con este problema. Para este propósito existen los siguientes mecanismos: Esquema enlazado: un bloque índice es del tamaño de un bloque. Para permitir archivos grandes, se pueden enlazar varios bloques índice. ○ Por ej., un bloque índice puede contener un encabezado pequeño que indique el nombre del archivo y un conjunto de las primeras 100 direcciones de bloque de disco. La siguiente dirección (la última palabra en el bloque índice) es null (para un archivo pequeño) o es un puntero a otro bloque índice (para un archivo grande). 73 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación indexada Índice multinivel: un bloque índice de primer nivel apunta a un conjunto de bloques de índice de segundo nivel, que a su vez apuntan a los bloques de archivo. ○ Para acceder a un bloque, el SO usa el índice de primer nivel para encontrar un bloque índice de segundo nivel y luego usa ese bloque para encontrar el bloque de datos deseado. ○ Este enfoque podría continuar a un tercer o cuarto nivel, dependiendo del tamaño máximo de archivo deseado. ○ Con bloques de 4.096 bytes, podríamos almacenar 1.024 punteros de 4 bytes en un bloque índice. Dos niveles de índices permiten 1.048.576 bloques de datos y un tamaño de archivo de hasta 4 GB. 74 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación indexada Esquema combinado: otra alternativa, utilizada en sistemas de archivos basados en UNIX, es mantener los primeros, por ej., 15 punteros del bloque índice en el inodo del archivo. ○ Los primeros 12 de estos punteros apuntan a bloques directos; es decir, contienen direcciones de bloques que contienen datos del archivo. Archivos pequeños (no más de 12 bloques) no necesitan un bloque índice separado. Si el tamaño del bloque es de 4 KB, se accede directamente hasta 48 KB de datos. ○ Los siguientes tres punteros apuntan a bloques indirectos. El primero apunta a un bloque indirecto: bloque índice que no contiene datos, sino las direcciones de los bloques que sí contienen datos. El segundo apunta a un doble bloque indirecto: contiene la dirección de un bloque que contiene las direcciones de los bloques que contienen punteros a bloques de datos. El último puntero contiene la dirección de un triple bloque indirecto. 75 SOYD 2024 - Gustavo C. Distel Métodos de asignación Asignación indexada 76 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación indexada Bajo este método, el número de bloques que se pueden asignar a un archivo excede la cantidad de espacio direccionable por los punteros de archivo de 4 bytes utilizados por muchos SOs. Un puntero de archivo de 32 bits alcanza solo 232 bytes, o 4 GB. Muchas implementaciones de UNIX y Linux ahora admiten punteros de archivos de 64 bits, lo que permite que los archivos y sistemas de archivos tengan un tamaño de varios exbibytes. El sistema de archivos ZFS admite punteros de archivos de 128 bits. Los esquemas de asignación indexada sufren algunos de los mismos problemas de rendimiento que la asignación enlazada. Los bloques de índice pueden almacenarse en la memoria caché, pero los bloques de datos pueden extenderse por todo un volumen. 77 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Asignación indexada: ejemplo Respuestas (asumiendo que todos los bloques índice están en memoria y no es necesario escribir éste en disco): ○ a)Se agrega al inicio: 1; se escribe el nuevo bloque y se actualiza el bloque índice en memoria. ○ b)Se agrega después del bloque del medio: 1; se escribe el nuevo bloque y se actualiza el bloque índice en memoria. ○ c)Se agrega al final: 1; se escribe el nuevo bloque y se actualiza el índice en memoria. El nuevo bloque se escribe, haciendo que apunte al siguiente bloque. Actualizar el primer puntero de bloque en memoria. ○ d)Se elimina del inicio: 0; el bloque se elimina del bloque índice en memoria. ○ e)Se elimina del medio: 0; el bloque se elimina del bloque índice en memoria. ○ f)Se elimina del final: 0; el bloque se elimina del bloque índice en memoria.. 78 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Ejemplo cálculo de inodo Considere un i-nodo con 12 punteros a bloques directos, 1 puntero a un bloque indirecto simple, 1 puntero a un bloque indirecto doble y 1 puntero a un bloque indirecto triple. Si los bloques tienen un tamaño de 8-kilobyte y los punteros son de 64 bits, ¿Cual es el tamaño máximo teórico de un archivo para cada uno de los siguientes casos? a)El archivo usa solo punteros directos. b)El archivo usa solo punteros directos y simples indirectos. c)El archivo usa solo punteros directos, simples y dobles indirectos. d)El archivo usa solo punteros directos, simples, dobles y triples indirectos. 79 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Ejemplo cálculo de inodo Los punteros directos apuntan a bloques de datos en disco y dado que cada bloque es de 8 kilobytes: ○ Directos = 12 x 8 KB = 96 KB. Para el caso de los indirectos se debe saber cuantos punteros caben en un bloque de disco ○ Cantidad de punteros = 8 KB ÷ 8 bytes = 1024 punteros a bloques. Luego se puede calcular cada caso en particular: ○ Simple indirecto = 1024 * 8KB = 8 MB = 8,388,608 bytes. ○ Doble indirecto = 1024 * 1024 * 8 KB = 8 GB = 8,589,934,592 bytes. ○ Triple indirecto = 1024 * 1024 * 1024 * 8 KB = 8 TB = 8,796,093,022,208 bytes. 80 SOYD 2024 - Gustavo C. Distel  Métodos de asignación Ejemplo cálculo de inodo Respuestas: ○ a) 96 KB = 98.304 bytes. ○ b) 8 MB + 96 KB = 8.486.912 bytes. ○ c) 8 GB + 8 MB + 96 KB = 8.598.421.504 bytes. ○ d) 8 TB + 8 GB + 8 MB + 96 KB = 8.804.691.443.712 bytes. 81 SOYD 2024 - Gustavo C. Distel  Gestión de espacio libre Vector de bits Cada bloque está representado por 1 bit. Si el bloque está libre, el bit es 1; si el bloque está asignado, el bit es 0. Por ejemplo, consideremos un disco donde los bloques 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 y 27 están libres y el resto de los bloques están asignados. El mapa de bits de espacio libre sería: ○ 001111001111110001100000011100000 … La principal ventaja de este enfoque es su relativa simplicidad y su eficiencia para encontrar el primer bloque libre o n bloques libres consecutivos en el disco. Para encontrar el primer bloque libre se busca en cada palabra del mapa un valor distinto de 0, ya que una palabra con 0 contiene solo 0 bits y representa un conjunto de bloques asignados. La primera palabra que no es 0 se explora buscando el primer bit en 1. El cálculo del número de bloque es: ○ (number of bits per word) × (number of 0-value words) + offset of first 1 bit. 82 SOYD 2024 - Gustavo C. Distel  Gestión de espacio libre Lista enlazada Otro enfoque para la gestión del espacio libre es enlazar todos los bloques libres, manteniendo un puntero al primer bloque libre en una ubicación especial en el sistema de archivos y almacenándolo en memoria caché. Este primer bloque contiene un puntero al siguiente bloque libre, y así sucesivamente. Para el ej. anterior se mantiene un puntero al bloque 2 como el primer bloque libre. El bloque 2 contendría un puntero al bloque 3, que apuntaría al bloque 4, que apuntaría al bloque 5, que apuntaría al bloque 8, y así sucesivamente. Este esquema no es eficiente: ○ Para recorrer la lista, debemos leer cada bloque, lo que requiere un tiempo considerable de E/S en discos duros. Sin embargo, recorrer la lista libre no es una acción frecuente. ○ Por lo general, el SO simplemente necesita un bloque libre para poder asignarlo a un archivo, por lo que se utiliza el primer bloque de la lista libre. 83 SOYD 2024 - Gustavo C. Distel Gestión de espacio libre Lista enlazada 84 SOYD 2024 - Gustavo C. Distel  Recuperación (Recovery) Backup and Restore Los dispositivos de almacenamiento a veces fallan, motivo por el cual hay que ser precavido y garantizar que los datos involucrados en la falla no se pierdan para siempre. Con este fin, se pueden utilizar programas del sistema para realizar copias de seguridad (back up) de los datos de un dispositivo de almacenamiento a otro, como una cinta magnética u otro dispositivo de almacenamiento secundario. La recuperación tras la pérdida de un archivo individual o de un dispositivo completo puede involucrar la restauración (restoring) de los datos desde una copia de seguridad. Para minimizar esta copia, se puede utilizar información de la entrada del directorio de cada archivo. Por ejemplo, si el programa de copia de seguridad conoce cuándo se realizó la última copia de un archivo y la última fecha de escritura en el directorio, indica que el archivo no ha cambiado desde esa fecha y entonces no es necesario volver a copiarlo. 85 SOYD 2024 - Gustavo C. Distel  Recuperación (Recovery) Backup and Restore Un típico programa de respaldo puede ser el siguiente: ○ Día 1. Copiar a un medio de respaldo todos los archivos del sistema de archivos. Esto se llama copia de seguridad completa (full backup). ○ Día 2. Copiar a otro medio todos los archivos modificados desde el día 1. Esta es una copia de seguridad incremental (incremental backup). ○ Día 3. Copiar a otro medio todos los archivos modificados desde el día 2. ○ … ○ Día N. Copiar a otro medio todos los archivos modificados desde el día N-1. Luego volver al día 1. La copia de seguridad del nuevo ciclo puede escribirse sobre el conjunto anterior o en un nuevo conjunto de medios de copia de seguridad. 86 SOYD 2024 - Gustavo C. Distel  Recuperación (Recovery) Backup and Restore Con este método, podemos restaurar un sistema de archivos completo utilizando la copia de seguridad completa y continuar con cada una de las copias de seguridad incrementales. Cuanto mayor sea el valor de N, mayor será la cantidad de medios que se deben leer para una restauración completa. Una ventaja de este ciclo de copia de seguridad es que podemos restaurar cualquier archivo eliminado accidentalmente durante el ciclo, recuperando el archivo de la copia de seguridad del día anterior. La duración del ciclo es un compromiso entre el tamaño de la copia de seguridad necesaria y la cantidad de días cubiertos por una restauración. Una alternativa para disminuir la cantidad de cintas que se deben leer para realizar una restauración, es realizar una copia de seguridad completa y luego, cada día, hacer una copia de seguridad de todos los archivos que han cambiado desde la copia completa. 87 SOYD 2024 - Gustavo C. Distel  Recuperación (Recovery) Backup and Restore De esta manera, se puede realizar una restauración a través de la copia de seguridad incremental más reciente y la copia de seguridad completa, sin necesidad de otras copias de seguridad incrementales. La desventaja es que se modificarán más archivos cada día, por lo que cada copia de seguridad incremental sucesiva implica más archivos y más medios de copia de seguridad. Un usuario puede notar que un archivo en particular falta o está dañado mucho después de que se produjo el daño. Por este motivo, normalmente planeamos realizar una copia de seguridad completa de vez en cuando, que se guardará “para siempre”. Es una buena idea almacenar estas copias de seguridad permanentes lejos de las copias de seguridad regulares, para protegerlas contra peligros, como un incendio que destruya la computadora y las copias de seguridad. 88 SOYD 2024 - Gustavo C. Distel Estructura interna del sistema de archivos 13 Sistemas operativos y distribuidos Gustavo Distel [email protected] DCIC - UNS  Estructura interna del sistema de archivos Contenido Sistema de archivos. Montaje del sistema de archivos. Particiones y montaje. Compartición de archivos. Virtual File Systems. Sistema de archivos remoto. Semántica de consistencia. NFS. 90 SOYD 2024 - Gustavo C. Distel  Sistemas de archivos Una computadora de uso general puede tener varios dispositivos de almacenamiento, los cuales se pueden dividir en particiones, que contienen volúmenes, que a su vez contienen sistemas de archivos. Además un volumen también puede abarcar varias particiones. Un volumen es un dispositivo de almacenamiento, como un disco fijo, un disquete o un CD-ROM, que está formateado para almacenar directorios y archivos. Un volumen grande se puede dividir en más de un volumen lógico, también llamado partición. Cada volumen lógico está formateado para ser utilizado por un sistema de archivos basado en medios particular, como NTFS, FAT o CDFS [Microsoft]. Los volúmenes existen en el nivel lógico del sistema operativo y las particiones existen en el nivel físico específico de los medios. A veces existe una correspondencia uno a uno, pero esto no está 91 garantizado [wiki]. SOYD 2024 - Gustavo C. Distel  Sistemas de archivos Windows Disk Management (diskmgmt.msc). 92 SOYD 2024 - Gustavo C. Distel  Sistemas de archivos Linux gnome disk utility. 93 SOYD 2024 - Gustavo C. Distel  Sistemas de archivos El siguiente comando muestra los sistemas de archivos soportados por el kernel de Linux ejecutado actualmente: 94 SOYD 2024 - Gustavo C. Distel  Montaje del sistema de archivos Al igual que un archivo debe abrirse antes de que pueda usarse, un sistema de archivos debe montarse antes de que pueda estar disponible para los procesos. La estructura de directorios puede tener múltiples volúmenes que contienen distintos sistemas de archivos, los cuales deben montarse para que estén disponibles dentro del espacio de nombres del sistema de archivos. Para montar un sistema de archivos, el SO recibe el nombre del dispositivo y el punto de montaje, que indica la ubicación dentro de la estructura de archivos donde se adjuntará el sistema de archivos. Normalmente, un punto de montaje es un directorio vacío. En Linux se puede utilizar el comando mount para montar un sistema de archivo. ○ Uso: mount -t type device dir ○ Ej.: para montar el dispositivo foo en /dir: mount /dev/foo /dir. 95 SOYD 2024 - Gustavo C. Distel  Montaje del sistema de archivos La imagen de arriba a la izquierda muestra un sistema de archivos existente. La imagen de arriba a la derecha muestra un volumen desmontado que reside en /device/dsk. La imagen de abajo muestra el montaje del volumen que reside en /device/dsk en /users. 96 SOYD 2024 - Gustavo C. Distel  Montaje del sistema de archivos La familia de SOs Microsoft Windows mantiene una estructura de directorio de dos niveles, con dispositivos y volúmenes a los cuales se les asigna letras de unidad. Cada volumen tiene una estructura de directorio de grafo general asociada con su letra de unidad: ○ drive-letter:∖path∖to∖file Las versiones actuales de Windows permiten montar un sistema de archivos, tal como lo hace UNIX. En el momento del arranque Windows detecta automáticamente todos los dispositivos y monta todos los sistemas de archivos encontrados. En algunos sistemas, como UNIX, los comandos de montaje son explícitos. Un archivo de configuración del sistema contiene una lista de dispositivos y puntos de montaje para el montaje automático en el momento del arranque, pero otros montajes se pueden hacer manualmente. 97 SOYD 2024 - Gustavo C. Distel  Particiones y montaje Cada partición puede ser "raw", que no contiene ningún sistema de archivos, o "cooked", que contiene un sistema de archivos. Un disco raw se utiliza cuando no es apropiado un sistema de archivos. El espacio de intercambio (swap) de UNIX puede utilizar una partición raw. Si una partición contiene un sistema de archivos de arranque (bootable), que tiene un SO instalado y configurado, entonces la partición también necesita información de arranque. Esta información tiene su propio formato, porque en el momento del arranque el sistema no tiene cargado el código del sistema de archivos y, por lo tanto, no puede interpretar el formato del sistema de archivos. La información de arranque suele ser una serie secuencial de bloques cargados como una imagen en la memoria. 98 SOYD 2024 - Gustavo C. Distel  Particiones y montaje El bootstrap loader conoce la estructura del sistema de archivos para encontrar y cargar el kernel e iniciar su ejecución. Si el boot loader no conoce el formato de un sistema de archivos en particular, un SO almacenado en ese sistema de archivos no es bootable. La partición raíz seleccionada por el cargador de arranque, que contiene el kernel del SO y, a veces, otros archivos del sistema, se monta en el momento del arranque. Como parte de una operación de montaje exitosa, el SO verifica que el dispositivo contenga un sistema de archivos válido, pidiendo al controlador del dispositivo que lea el directorio del dispositivo y verificando que el directorio tenga el formato esperado. Si el formato no es válido, se debe verificar la consistencia de la partición y posiblemente corregirla, con o sin la intervención del usuario. Finalmente, el SO marca en su tabla de montaje en memoria que un sistema de archivos está montado, junto con el tipo de sistema de archivos, los detalles de esta función dependen del SO. 99 SOYD 2024 - Gustavo C. Distel  Compartición de archivos Múltiples usuarios Para la implementación de la compartición y protección, el sistema debe mantener más atributos de archivos y directorios de los que se necesitan en un sistema de un solo usuario. La mayoría de los SOs han evolucionado para utilizar los conceptos de propietario (o usuario, o owner) de archivo (o directorio) y grupo (group). Los ID de propietario y grupo de un archivo (o directorio) se almacenan con los demás atributos de archivo. Cuando un usuario solicita una operación en un archivo, el ID de usuario se puede comparar con el atributo de propietario para determinar si el usuario solicitante es el propietario del archivo. Asimismo, se pueden comparar los ID de grupo y el resultado indica qué permisos son aplicables. Luego, el sistema aplica esos permisos a la operación solicitada y los permite o los deniega. 100 SOYD 2024 - Gustavo C. Distel  Virtual File Systems Un método para implementar múltiples tipos de sistemas de archivos es escribir rutinas de directorio y archivo para cada tipo de sistema de archivos, aunque es un método deficiente. Actualmente, la mayoría de los SOs utilizan técnicas orientadas a objetos para simplificar, organizar y modularizar la implementación. El uso de estos métodos permite implementar diferentes sistemas de archivos dentro de la misma estructura, incluidos los sistemas de archivos de red, como NFS (ver más adelante). Los usuarios pueden acceder a archivos en múltiples sistemas de archivos en la unidad local o incluso en sistemas de archivos disponibles en red, sin darse cuenta de las diferencias entre los sistemas de archivos. Para aislar la funcionalidad básica de llamada al sistema de los detalles de implementación se utilizan estructuras y procedimientos de datos. El sistema de archivos virtual es la capa de software en el kernel que proporciona la interfaz del sistema de archivos a los programas del espacio de usuario. También proporciona una abstracción dentro del kernel que permite que coexistan diferentes implementaciones del sistema de archivos. 101 SOYD 2024 - Gustavo C. Distel  Virtual File Systems Primer capa; interfaz del sistema de archivos: ○ LLamadas al sistema open(), read(), write() y close(), y descriptores de archivos. Segunda capa; sistema de archivos virtual (VFS). ○ Separa operaciones genéricas del sistema de archivos de su implementación. Varias implementaciones para la interfaz VFS pueden coexistir en la misma máquina, lo que permite un acceso transparente a diferentes tipos de sistemas de archivos montados localmente. ○ Proporciona un mecanismo para representar de forma única un archivo en una red. El VFS se basa en una estructura de representación de archivos, Tercer capa: denominada vnode, que contiene un designador ○ Implementa el tipo de sistema de archivos o el numérico para un archivo único en toda la red. protocolo del sistema de archivos remoto. 102 SOYD 2024 - Gustavo C. Distel  Virtual File Systems VFS distingue los archivos locales de los remotos, y los archivos locales se distinguen según sus tipos de sistema de archivos. VFS utiliza operaciones específicas del sistema de archivos para manejar solicitudes locales de acuerdo con sus tipos de sistema de archivos además, llama a los procedimientos de protocolo NFS (u otros procedimientos de protocolo para otros sistemas de archivos de red) para solicitudes remotas. Los manejadores de archivo se construyen a partir de los vnodes relevantes y se pasan como argumentos a estos procedimientos. 103 SOYD 2024 - Gustavo C. Distel  Sistemas de archivos remotos Las redes permiten compartir recursos distribuidos en un campus o incluso en todo el mundo. ○ Un recurso para compartir son los datos en forma de archivos. A través de la evolución de la tecnología de archivos y redes, los métodos de compartición de archivos remotos han cambiado. ○ El primer método implementado implica la transferencia manual de archivos entre máquinas a través de programas como ftp. ○ El segundo método utiliza un sistema de archivos distribuido (DFS), en el que los directorios remotos son visibles desde una máquina local. ○ El tercer método, la World Wide Web, es una reversión al primero utilizando un navegador. 104