Sistemas Operativos

Tema 5. Sistemas de archivos

© 1998-2019 José Miguel Santos – Alexis Quesada – Francisco Santana –

Belén Esteban

1
Contenidos

 Interfaz del sistema de archivos

 Implementación del sistema de archivos

2
Interfaz del sistema de archivos

 Concepto de archivo/fichero
 Métodos de acceso
 Directorios
 Protección

3
Almacenamiento secundario

 Características físicas:
 Barato (en comparación con la RAM)
 Lento (en comparación con la RAM)
 No volátil
 Heterogéneo (cintas y discos magnéticos, discos ópticos,
discos SSD, tarjetas extraíbles…)
 En un sistema típico, el almacenamiento secundario
se utiliza para:
 Almacenar el código ejecutable de las aplicaciones
 Almacenar los documentos de los usuarios
 Guardar copias de seguridad
 Servir de respaldo para la memoria virtual
 …

4
Interfaz de los dispositivos de
almacenamiento
 Los dispositivos de almacenamiento secundario
nos ofrecen una interfaz muy básica para leer y
escribir información.
 El núcleo abstrae las operaciones en una
interfaz independiente del dispositivo,
normalmente un array de bloques de datos de
tamaño fijo, ej. write_block(block_id, data[])

0 1 2 … 123 124 …

5
Necesidades de los usuarios

 La interfaz de los periféricos y del núcleo tiene un

nivel de abstracción demasiado bajo, comparado
con las necesidades de los usuarios.
 Los usuarios trabajan con este tipo de entidades:
 Aplicaciones (programas ejecutables)
 Documentos de texto
 Bases de datos
 Fotos, vídeos, canciones
 A un usuario (o a un programador) no podemos
decirle que para leer un documento tenga que
ordenarle al sistema: “busca en el disco los bloques
357, 48 y 13”.

6
Solución del SO:
concepto de ARCHIVO (file)
 El sistema operativo ofrece una entidad abstracta
más próxima a los conceptos que maneja el usuario
 ARCHIVO
 Un archivo es un objeto identificable mediante un
nombre y que guarda información persistente.
 Ejemplos: “mifoto.jpg”, “apuntes-fso.docx”,
“winword.exe”
 Persistente = no volátil = duradera
 Sobre un archivo se pueden realizar diversas
operaciones: crear, leer, escribir, eliminar, etc.
 Un archivo es un tipo abstracto de datos =
operaciones públicas + estructura de datos

7
Atributos del archivo

 Además del contenido, cada archivo tiene unos atributos que

describen sus características:
 Nombre (cadena de caracteres)
 Tipo de archivo (necesario en sistemas que reconocen distintos
tipos)
 Ubicación en el dispositivo
 Tamaño
 Información de protección
 Fechas, horas e identificación del usuario
 Cada SO establece un conjunto de atributos para sus
ficheros, y limitaciones sobre ellos (ej. longitud máxima del
nombre).

8
Directorios

 Casos de uso:
 Un usuario quiere trabajar con el documento “tema5.pptx”.
¿Cómo sabe el SO que ese archivo existe? ¿Dónde está
ubicado en el disco?
 Un usuario quiere saber qué archivos contiene un disco (obtener
un inventario de los nombres de esos archivos).
 El SO debe manejar una estructura con el catálogo de
los archivos  directorio o tabla de contenidos.
 El directorio debe estar almacenado en el disco.
 (por eficiencia, se puede tener una copia en RAM mientras se
trabaja con él).
 Cada entrada en el directorio contiene los atributos de
un archivo y su localización en el disco.

9
Sistemas de archivos
(file systems)
 El término “sistema de archivos” tiene dos
usos:
 Se llama sistema de archivos al componente
del sistema operativo que se encarga de
ofrecer todas las funcionalidades
relacionadas con archivos y directorios.
 También se llama sistema de ficheros a la
estructura de información que se crea en el
almacenamiento secundario (disco) para
almacenar los archivos y directorios.

10
Operaciones sobre archivos:
abrir y cerrar
 La mayor parte de las operaciones requieren buscar la
entrada en el directorio asociada al archivo (con todos
sus atributos).
 Mejora: operaciones para abrir y cerrar archivos
 Se guarda en memoria principal la info de cada archivo abierto y
se mantiene ahí hasta que el archivo se cierra.
 Tabla de archivos abiertos
 Indice, puntero o descriptor de fichero

12
Tipos y estructuras de archivos
 La información guardada puede ser de muchos
tipos: ejecutables, textos, fotos, bases de
datos…
 ¿cómo reconoce el SO qué tipo de información
contiene el archivo?
 En Windows  se usan las últimas letras del nombre
como indicador del tipo
 En Mac (versiones antiguas)  unos atributos
marcan el tipo de archivo
 En Unix  el SO no reconoce tipos de archivos
 Todos los S.O. deben reconocer al menos un
formato de archivo: la de un archivo
ejecutable.

13
Métodos de acceso
 Archivo: secuencia de registros lógicos de longitud fija
 ¿De qué manera se accede a la información almacenada en
los archivos?
 Algunos SO ofrecen un solo método de acceso mientras que otros
ofrecen diferentes métodos de acceso

 ACCESO SECUENCIAL
 Se basa en un modelo de archivo de cinta

 ACCESO DIRECTO o RELATIVO

 Se basa en el modelo de archivo de disco

 ACCESO INDEXADO
 Requiere de estructuras adicionales: tablas de indices

14
Directorios
 Sistema de Archivos  Miles de archivos
 ¿Cómo los organizamos?
 Particiones/Minidiscos/Volúmenes
 Directorio de dispositivo, Tabla de Contenido del Volumen o
simplemente Directorio

15
Operaciones sobre directorios

 Buscar un archivo por nombre

 Crear archivos
 Borrar Archivos
 Renombrar archivos
 Listar el directorio
 Recorrer el sistema de ficheros

16
Organización de directorios
 Único nivel (espacio plano)
 Dos niveles
 Arbóreo
 Grafo acíclico (enlaces)
 Grafo general (enlaces sin restricciones)

17
Directorio de nivel único

 Estructura de directorio más sencilla: todos los archivos

se guardan en el mismo directorio

 Problemas:
 Conflictos de nombres (al aumentar el numero de ficheros)
 Mala organización en sistemas multiusuario
 El tiempo de búsqueda tiende a aumentar

18
Directorio de dos niveles
 Desventaja principal de la estructura de nivel único 
confusión de nombres entre diferentes usuarios
 Solución natural  un directorio por usuario

19
Directorio de dos niveles
 Se resuelve el problema de conflictos de nombres
(entre diferentes usuarios)
 Problema: compartir información (algunos sistemas
impiden el acceso a los directorios de otros usuarios)
 Aparece el concepto de ruta (path)
 Archivos de sistema  usuario especial

20
Directorio con estructura de árbol
 Directorio de dos niveles  árbol de dos niveles
 Generalización  árbol de altura arbitraria
(subdirectorios)

21
Directorio con estructura de árbol

 Se reducen al mínimo los conflictos de nombres

 Directorio  archivo que se trata de manera especial

 Los nombres de los archivos son rutas sobre el árbol

de directorios: rutas absolutas o relativas

 Aparece el concepto de “directorio de trabajo”

 Política a seguir para la eliminación de directorios

 “Caminos de búsqueda ” (facilita el hecho de que

varios usuarios quieran compartir ficheros)

22
Directorios en grafo acíclico
 La estructura de árbol dificulta compartir archivos o
directorios
 Se puede generalizar el esquema de directorio con
estructura de árbol permitiendo a los directorios tener
subdirectorios y archivos compartidos, sin ciclos

23
Directorios en grafo acíclico

 ¿Cómo se puede implementar?

 Duplicar la información (complica la consistencia)
 Nueva entrada de directorio: ENLACE o LINK (es un puntero a
otro archivo o directorio)

 Estructura de directorios de grafo acíclico es más

flexible que un árbol sencillo pero más compleja
 Un mismo archivo podría tener diferentes nombres de camino
absoluto -> Copias de seguridad dobles???
 Eliminación  ¿ Cuándo puede liberarse o reutilizarse el
espacio asignado a un archivo compartido ?

24
Directorios en grafo acíclico

25
 Organización de directorios:
resumen
Directorio doble nivel  Caso particular
Usuarios pueden crear  Directorio grafo acíclico
subdirectorios
 Requieren el uso de
Directorio estructura árbol algoritmos que detecten
Links ciclos en grafos (problema:
costoso en tiempo)

Directorio estructura grafo general

 Problemas
 Evitar búsquedas repetidas
 Liberación de espacio al eliminar
un archivo
 Recolector de basuras (“Garbage
Colection”)
 Consume mucho tiempo y por ello
pocas veces se intenta

26
Protección de archivos

 Necesidad de mantener la seguridad de la

información:
 De daños físicos (integridad)
 Copias de seguridad
 Accesos indebidos (privacidad)
 Múltiples mecanismos según
 Tipo sistema
 Seguridad requerida

27
Protección

 Muchos sistemas definen privilegios de uso: cada

usuario solo puede realizar ciertas operaciones sobre un
archivo (acceso controlado)
 Tipo de operaciones
 Leer, Escribir, Ejecutar, Anexar, Eliminar, Listar

 Diferentes mecanismos de protección

 Listas y grupos de acceso
 Claves
 Técnicas criptográficas

28
IMPLEMENTACIÓN DEL
SISTEMA DE ARCHIVOS

29
Implementación del sistema de
archivos
 Estructura del Sistema de Archivos
 Métodos de Asignación
 Administración del espacio libre
 Implementación de directorios

30
Estructura del sistema de archivos
 SISTEMA DE ARCHIVOS  reside de manera
permanente en almacenamiento secundario
 Con el objetivo de aumentar la eficiencia E/S  las
transferencias entre la memoria y el disco se efectúan
en unidades de bloques (uno o más sectores)
 Discos  dos características importantes que los
convierten en un medio cómodo para almacenar
muchos archivos
 Leer bloque/ Modificarlo y volverlo a escribir (rescribir)
 Se puede acceder directamente a cualquier bloque de
información del disco

31
Organización del sistema de
archivos
 Un sistema de archivos presenta dos problemas de
diseño muy distintos:

 Definir que aspecto debe presentar el sistema de archivos a

los usuarios (atributos, operaciones, estructura de directorios,
etc...)

 Definir los algoritmos y estructuras de datos que permiten

mapear el sistema de ficheros lógico sobre los equipos físicos

32
Métodos de asignación de espacio

 OBJETIVO: asignar espacio a ficheros de modo que el

espacio en disco se aproveche de forma eficaz y se
pueda acceder rápidamente a los archivos

 Asignación Contigua
 Asignación Enlazada
 Asignación Indexada

33
Asignación contigua

 Cada fichero ocupa un

conjunto de bloques
contiguos en el disco
(optimiza movimiento de
las cabezas del disco)
 Entrada de directorio para
cada fichero
 Dirección del bloque inicial
 Longitud del área asignada
al archivo (nº bloques)

34
Asignación contigua

 Permite manejar acceso tanto secuencial como directo

 Dificultades
 Encontrar espacio para la creación de un fichero
 Algoritmos mas utilizados
 Primer ajuste (First Fit)
 Mejor ajuste (Best Fit)
 Desde un punto de vista de aprovechamiento del espacio no existen
diferencias pero el primero suele ser mas rápido

 Problema ambos algoritmos: Fragmentación Externa

 Solución: Compactación (pero es una solución costosa)

35
Asignación contigua

 Otro problema importante:

 Determinar cuanto espacio se necesita para un fichero
 En unas ocasiones es sencillo (cuando el archivo es copia de
otro)
 Otras es muy complicado:
 ¿Pecar por defecto?
 ¿Pecar por exceso?
 Incluso cuando se conoce la cantidad total de espacio
requerido, la preasignación puede ser ineficiente
 Crecimiento lento (fragmentación interna)

36
Asignación enlazada

 Cada fichero es una lista

enlazada de bloques de
disco
 Entrada de directorio
contiene:
 Puntero al primer y último
bloque del archivo

37
Asignación enlazada:
pros y contras

 Se solucionan los problemas de la asignación contigua

 No se produce fragmentación externa
 No es necesario declarar de antemano el tamaño del archivo

 Desventajas:
 Solo eficiente para acceso secuencial
 Si se accede de forma directa a un punto aleatorio del archivo,
hay que recorrer todos los bloques desde el principio (para ir
siguiendo los enlaces)
 Los punteros desperdician una parte del bloque de datos

38
Asignación enlazada

 Robustez: ¿Qué sucede si se daña uno de los bloques del

archivo?
 Soluciones
 Listas doblemente enlazadas (enlace hacia adelante y hacia atrás)
 Almacenar el nombre del archivo y el numero de bloque relativo en
cada bloque
 Problema: gasto extra de espacio

40
Asignación indexada
 La idea: reunir todos los punteros del archivo en un
bloque de índices

 Cada archivo tiene un

bloque índice.
 La i-ésima entrada del
bloque índice apunta al
i-ésimo bloque del
archivo.

41
Asignación indexada:
pros y contras
 El acceso directo se realiza en un tiempo constante
(solo necesita acceder al bloque de índices y luego al
bloque de datos del archivo).
 Requiere un bloque de datos adicional (el bloque de
índices). Esto impacta más en archivos de pequeño
tamaño.
 Con respecto a la asignación contigua, requiere un
acceso adicional a disco (al bloque de índices)  pero
el bloque de índices se puede guardar en caché.

42
Asignación indexada:
tamaño del bloque de índices
 El tamaño del bloque de datos limita el número de
índices, y con ello el tamaño máximo que puede tener
un archivo.
Ejemplo:
 Tamaño de bloque = 1KiB = 1024 bytes
 Tamaño de un enlace = 2 bytes
 En un bloque de índices caben 1024/2 = 512 entradas
 Por tanto, un archivo puede tener hasta 512 bloques
 Tamaño máximo de un archivo = 512 · 1KiB = 512KiB

43
Asignación indexada:
tamaño del bloque de índices
 ¿Qué podemos hacer para resolver la
limitación de tamaño del bloque de índices?
 Permitir que los índices ocupen varios bloques
contiguos  ojo, fragmentación
 Lista enlazada de índices  ojo, ineficiente
 Estructura multinivel (bloque de índices que
apunta a un segundo nivel de bloques de índices)
 esta fue la solución de UNIX

44
Asignación indexada:
esquema multinivel de Unix

45
Asignación enlazada con FAT

 FAT = File Allocation Table

 Variación del método de asignación enlazada.
 Creada para MS-DOS  continúa usándose en
memorias flash (VFAT)
 Idea: reunir todos los enlaces en una única
estructura de datos compacta dentro del disco.
 Se reserva una zona al principio del disco al principio
para guardar la tabla.
 Cada entrada de la tabla corresponde a un bloque. Su
contenido nos dice dónde está el siguiente bloque.

46
Asignación enlazada con FAT

 Los enlaces del

fichero “test”
están en la FAT.

47
Asignación enlazada con FAT
 Beneficio: mejora el tiempo de acceso aleatorio, comparada con la
enlazada.
 En dispositivos pequeños, la FAT completa se puede traer a la RAM.
Esta caché acelera los accesos a los archivos.
 Para recorrer un archivo, solo hacen falta los bloques de la FAT en
los que está la información de los enlaces del archivo. Si esos
bloques están bastante cercanos entre sí, no hará falta leer muchos
bloques.
 Robustez: si un bloque de la FAT se daña, se pierden numerosos
enlaces de múltiples archivos. Solución: mantener varias copias de
la FAT.

48
Mejora: asignación contigua con
extensiones (extents)
 Los SF más modernos (NTFS, XFS…) utilizan un híbrido entre
la asignación contigua y las no contiguas.
 Si se puede, el archivo utiliza un conjunto contiguo de
bloques de datos.
 Si no basta con un espacio contiguo, se busca otra
extensión de bloques contiguos.
 En la entrada en directorio se guarda la información de todas
las extensiones. Por cada extensión: bloque inicial, nº
bloques.
 El algoritmo para acceder a un punto aleatorio del archivo es
más complejo, pero en general mantiene un nivel bajo de
fragmentación y se consume muy poco espacio en estructuras
de control.

49
Administración del espacio libre
 Se pueden usar varias estructuras:
 Mapa de bits
 Tabla en una zona fija del disco. Un bit por cada bloque de datos, que
marca si el bloque está libre u ocupado.
 Lista enlazada
 El SO mantiene un apuntador al primer bloque libre. Este a su vez
apuntará al siguiente bloque libre, etc.
 Lista enlazada con información de bloques libres
 El primer bloque libre se comporta como un “bloque índice” de
bloques libres
 FAT  si un bloque está libre, su entrada en la FAT tiene un valor
que así lo indica

50
Implementación de directorios

 Implementación básica: lista lineal

 Lista de nombres de archivos con punteros a los bloques de
datos, más otros atributos.
 Sencillo de implementar (vector), pero rendimiento pobre en
directorios con muchas entradas.

51
Implementación de directorios

 Los sistemas modernos usan estructuras

más eficientes:
 Tabla hash
 Árboles B (NTFS, ext4…)
 Los árboles B funcionan muy bien en
directorios con muchas entradas, sin
penalizar demasiado el coste de
almacenamiento de la estructura y el código
adicional.

52
Archivos: sumario (1)
Interfaz con el sistema de archivos
Datos
TAD Atributos
Operaciones ← mejora: tabla de archivos abiertos
 Ficheros
Secuencial
Tipos de acceso Directo
Indexado (ISAM)

Particiones
Operaciones
Protección
Único nivel
 Directorios Dos niveles
Organización Árbol
Grafo sin ciclos
Grafo con ciclos

53
Archivos: sumario (2)
Implementación del sistema de archivos
Simple
Contigua Con extensiones

 Métodos de asignación Simple

Por clusters
Enlazada
FAT

Simple
Enlazado
Indexada Múltiples niveles
Combinado

Vector de bits
 Administración del espacio libre Lista enlazada de bloques libres
Lista enlazada con info. de bloques libres
FAT
Lista lineal
 Implementación de directorios Tabla de dispersión (hash)
Árbol B*

54