FileSystem-SOR2

Vista previa del material en texto

Sistema de Archivos
¿Qu ́e es un archivo?
Para nosotros (y para los sistemas operativos como Unix): una
secuencia de bytes, sin estructura.
Se los identifica con un nombre.
El nombre puede incluir una extensi ́on que podr ́ıa servir para
distinguir el contenido. Por ejemplo:
archivo.txt: archivo con contenido de texto.
archivo.bat: archivo interpretable por la l ́ınea de comandos
windows.
archivo.c: archivo con c ́odigo fuente en C.
Metadata: Tienen fecha, due ̃no, etc
(3) Los sistemas de archivos
¿Y qu ́e es un sistema de archivos ?
¿Qu ́e buscamos ?
Abstracci ́on, abstracci ́on, abstracci ́on.
¿Conocen alguno ?
Los sistemas de archivos
Existe un m ́odulo dentro del kernel encargado de organizar la
informaci ́on en disco: sistema de archivos o file system.
Algunos SO soportan s ́olo uno (ejemplo: DOS s ́olo soporta
FAT),
...otros m ́as de uno (Windows soporta FAT, FAT32, NTFS,
etc.),
... y otros como los Unix modernos suelen venir con soporte
para algunos pero mediante m ́odulos din ́amicos de kernel se
puede hacer que soporten casi cualquiera.
Otros file systems populares: UFS, FFS, ext2, ext3, ext4, XFS,
RaiserFS, ZFS, ISO-9660.
Existen incluso file systems distribuidos, es decir, file systems
donde los datos est ́an distribuidos en varias m ́aquinas en la
red. Por ejemplo: NFS, DFS, SMBFS, AFS, CodaFS, etc
(5) Ejemplo del help de fdisk
0 Vide 1e Hidden W95 FAT1 80 Old Minix
1 FAT12 24 NEC DOS 81 Minix / old Lin
2 XENIX root 39 Plan 9 82 Linux swap / So
3 XENIX usr 3c PartitionMagic 83 Linux
4 FAT16 <32M 40 Venix 80286 84 OS/2 hidden C:
5 Extended 41 PPC PReP Boot 85 Linux extended
6 FAT16 42 SFS 86 NTFS volume set
7 HPFS/NTFS 4d QNX4.x 87 NTFS volume set
8 AIX 4e QNX4.x 2nd part 88 Linux plein tex
9 AIX bootable 4f QNX4.x 3rd part 8e Linux LVM
a OS/2 Boot Manag 50 OnTrack DM 93 Amoeba
b W95 FAT32 51 OnTrack DM6 Aux 94 Amoeba BBT
c W95 FAT32 (LBA) 52 CP/M 9f BSD/OS
e W95 FAT16 (LBA) 53 OnTrack DM6 Aux a0 IBM Thinkpad hi
f W95 Etendu (LBA 54 OnTrackDM6 a5 FreeBSD
10 OPUS 55 EZ-Drive a6 OpenBSD
11 Hidden FAT12 56 Golden Bow a7 NeXTSTEP.
6) Responsabilidades del FS
C ́omo se organizan, de manera l ́ogica, los archivos.
Interna: c ́omo se estructura la informaci ́on dentro del archivo.
E.g. Windows y Unix usan secuencia de bytes. La
responsabilidad es del usuario.
Externa: c ́omo se ordenan los archivos. Hoy en d ́ıa todos los
FS soportan el concepto de directorios, lo que hace que la
organizaci ́on sea jer ́arquica, con forma de ́arbol. Algunos est ́an
proponiendo directamente b ́usqueda.
C ́omo se nombrar ́a a los archivos.
Caracteres de separaci ́on de directorio.
Si tienen o no extensi ́on.
Restricciones a la longitud y caracteres permitidos
Distinci ́on o no entre may ́usculas y min ́usculas.
Prefijado o no por el equipo donde se encuentran.
Ejemplos:
/usr/local/etc/apache.conf
C:\Program Files\Antivirus\Antivirus.exe
\\SERVIDOR3\Parciales\parcial1.doc
servidor4:/ejercicios/practica3.pdf
Árbol de directorio
¿Qu ́e es el punto de montaje?
Imaginemos que tengo m ́as de un disco.
En realidad, m ́as de una unidad de almacenamiento externo.
Por ejemplo un USB.
Coloco el dispositivo
¿C ́omo me refiero a ́el ?
¿C ́omo sabe el SO que ya est ́a colocado?
Esto se llama montaje montaje. Y pueden averiguar porqu ́e
incluso exist ́ıa antes que existan los USB ! ∆!
Y para eso se invent ́o el comando mount, que le indicaba al
SO que el dispositivo ya est ́a colocado, y qu ́e punto del grafo
de nombres de archivos vamos a considerar como la ra ́ız de lacinta.
Eso permite cosas como
/dispositivos/usb/usb1/Fernandez/planilla.ods.
Responsabilidades del FS (cont.)
M ́as all ́a de las decisiones que se tomen sobre los puntos
anteriores, hay que ver qu ́e pasa tras bambalinas.
¿C ́omo se representa un archivo? ∆!
Y dos preguntas relacionadas:
¿C ́omo gestiono el espacio libre?
¿Qu ́e hago con los metadatos? (ie, los datos sobre los datos:
permisos, atributos, etc.).
Las respuestas a estas preguntas determinan las caracter ́ısticas
del FS, especialmente en cuanto a su rendimiento y
confiabilidad.
Lo primero que hay que entender es que para el FS un archivo
es una lista de bloques + metadata.
Representando archivos: Asignaci ́on contigua
La forma m ́as sencilla de representarlos es poner a los bloques
contiguos en el disco.
Las lecturas son insuperablemente r ́apidas, pero...
¿Qu ́e pasa si el archivo crece y no tengo m ́as espacio?
¿Qu ́e hago con la fragmentaci ́on?
La tabla de asignaci ́on de archivos es simple.
Nadie usa este esquema en FS de lectoescritura.
El paso obvio: Asignaci ́on Encadenada
El paso obvio es tener punteros al bloque que sigue. Una lista
encadenada
Esta lista puede ser pensada en realidad como un arreglo
donde en cada posici ́on est ́a el puntero a la siguiente.
Esto soluciona ambos problemas, pero:
Si bien las lecturas consecutivas son razonablemente r ́apidas,
las lecturas aleatorias son muy lentas.
Adem ́as, desperdicio espacio de cada bloque indicando d ́onde
est ́a el siguiente.
La tabla de asignaci ́on de archivos es simple.
Qu ́e sucede si se pierde (rompe) un bloque de la lista ?
Vuelta de tuerca: Asignaci ́on Indexada
Hay una vuelta de tuerca que se le puede dar a este problema.
Tengo una tabla que por cada bloque me dice en qu ́e bloque
est ́a el siguiente elemento de la lista.
Ejemplo. El archivo A est ́a en los bloques 1, 2, 5, 7 y 9, el
archivo B en los bloques 4, 3 y 8.
Acceso aleatorio r ́apido. El bloque de ́ındice entra en ram.
Pero puede ser lento acceder a archivos completos
Vuelta de tuerca 2: Asignaci ́on Indexada por secci ́on
variable
M ́as vueltas de tuerca
La tabla anterior ahora tiene asignaci ́on contigua (si quiero).
Acceso aleatorio r ́apido. El bloque de ́ındice entra en ram.
Leer un archivo es r ́apido ya que los bloques est ́an cercanos
Tabla m ́as chica porque referencia a menos bloques
FAT
FAT (file allocation table) usa un sistema enlazado en una
tabla de asignaci ́on.
Creado para floppy’s en 1977. Luego FAT12, FAT16 y FAT32
Soluciona ambos problemas, porque no desperdicio espacio del
bloque y porque al tener en memoria todos los bloques que
necesito puedo leerlos fuera de orden y no es tan ineficiente
para las lecturas no secuenciales.
Sin embargo, tengo que tener toda la tabla en memoria.
Puede ser inmanejable para discos grandes.
Adem ́as, ́unica tabla: mucha contenci ́on.
Por otra parte, es poco robusto: si el sistema cae, la tabla
estaba en memoria.
FAT tiene otras limitaciones: no maneja seguridad
Y... nodos
Linux: Ext2 (1992)
Viene de UFS (unix filesystem) o Berkeley Fast File System.
Primer fs comercial de unix. (1984)
Estructura:
Y... nodos
La soluci ́on Unix son los inodos.
Cada archivo tiene uno.
En las primeras entradas hay atributos (tama ̃no, permisos,
etc.).
Luego est ́an las direcciones de algunos bloques, directamente.
Esto permite acceder r ́apidamente a archivos peque ̃nos (si
pensamos en bloques de disco de 8 KB, esto permite hasta 96
KB).
Sigue una entrada que apunta a un bloque llamados single
indirect block. En este bloque hay punteros a bloques de
datos. Eso sirve para archivos de hasta 16 MB.
A continuaci ́on una entrada llamada double indirect block,
que apunta a una tabla de single indirect blocks. Con eso se
cubren archivos de hasta 32 GB.
Le sigue un triple indirect block, que apunta a un bloque de
double indirect blocks. Eso cubre hasta 70 TB.
inodos (cont.)
Permite tener en memoria s ́olo las tablas correspondientes a los archivos
abiertos.
Una tabla por archivo → mucha menos contenci ́on.
Consistencia: s ́olo est ́an en memoria las listas correspondientes a los
archivos abiertos
Implementaci ́on de directorios
¿C ́omo se implementa el ́arbol de directorios?
Se reserva un inodo como entrada al root directory.
Por cada archivo o directorio dentro del directorio hay una
entrada.
Dentro del bloque se guarda una lista de (inodos, nombre de
archivo/directorio).
En algunos casos, cuando los directorios son grandes, conviene
pensarlos como una tabla de hash m ́as que como una lista
lineal de nombres,para facilitar las b ́usquedas.
A veces esto se hace a mano, en la capa de software de
aplicaci ́on.
¿Y d ́onde est ́an los inodos?
nodos - Archivos y Directorios
Estructura de FS Ext2
El superbloque (superblock) contiene metadatos cr ́ıticos del
sistema de archivos tales como informaci ́on acerca del
tama ̃no, cantidad de espacio libre y donde se encuentra los
datos. Si el superbloque es da ̃nado, y su informaci ́on se pierde,
no podr ́ıa determinar que partes del sistema de archivos
contiene informaci ́on.
Ext2 - superbloque
(25) Ext2 - superbloque (cont.)
Ext2 - Group Descriptor
(27) Ext2 - Inode
(28) Links - inodos
ln /foo/bar /tmp/moo
ln -s /foo/bar /tmp/moo
Atributos
Cuando se habla de metadata en general se incluyen los
inodos (o la estructura de datos que sea que use el FS) pero
adem ́as otra informaci ́on.
Por ejemplo:
Permisos (default y ACLs).
Tama ̃nos.
Propietario/s.
Fechas de creaci ́on, modificaci ́on, acceso.
Bit de archivado.
Tipo de archivo (regular, dispositivo virtual, pipe, etc.).
Flags.
Conteo de referencias.
CRC o similar.
Manejo del espacio libre
Otro problema es c ́omo manejar el espacio libre.
Una t ́ecnica posible es utilizar un mapa de bits empaquetado,
donde los bits en 1 significan libre.
As ́ı, si una palabra tiene todos 0 puedo saltearla por completo
con una ́unica comparaci ́on.
Pero requiere tener el vector en memoria, y eso no est ́a bueno.
Tambi ́en podemos tener una lista enlazada de bloques libres.
En general se clusteriza. Es decir, si un bloque de disco puede
contener n punteros a otros bloques, los primeros n − 1
indican bloques libres y el ́ultimo es el puntero al siguiente
nodo de la lista.
Un refinamiento consiste en que cada nodo de la lista indique,
adem ́as del puntero, cu ́antos bloques libres consecutivos hay a
partir de ́el.
Cach ́e
Una manera de mejorar el rendimiento es mediante la
introducci ́on de un cach ́e. ∆!
Ie, una copia en memoria de bloques del disco.
Se maneja de manera muy similar a las p ́aginas.
De hecho, los SO modernos manejan un cach ́e unificado para
ambas, ya que si no, al mapearse archivos en memoria,
tendr ́ıamos dos copias de lo mismo.
Un efecto muy interesante del cach ́e es que puede grabar las
p ́aginas de manera ordenada, de manera tal que el
administrador de E/S pueda planificar m ́as eficientemente la
escritura. ∆!
A veces, las aplicaciones pueden configurarse para hacer
escritura sincr ́onica, es decir, escribiendo en disco
inmediatamente.
Esto es mucho m ́as lento.
Consistencia
¿Qu ́e pasa si se corta la energ ́ıa el ́ectrica antes de que se
graben a disco los cambios?
Los datos se pierden. Por eso se provee el system call fsync(),
para indicarle al SO que queremos que las cosas se graben s ́ı o
s ́ı. Es decir, que grabe las p ́aginas “sucias” del cach ́e.
Sin embargo, el sistema podr ́ıa interrumpirse en cualquier
momento.
La alternativa m ́as tradicional consiste en proveer un programa
que restaura la consistencia del FS. En Unix se llama fsck.
B ́asicamente, recorre todo el disco y por cada bloque cuenta
cu ́antos inodos le apuntan y cu ́antas veces aparece
referenciado en la lista de bloques libres. Dependiendo de los
valores de esos contadores se toman acciones correctivas,
cuando se puede.
Consistencia (cont.)
La idea es agregarle al FS un bit que indique apagado normal.
Si cuando el sistema levanta ese bit no est ́a prendido, algo
sucedi ́o y se debe correr fsck.
El problema es que eso toma mucho tiempo y el sistema no
puede operar normalmente hasta que este proceso termine.
Hay algunas alternativas para evitar eso, total o parcialmente.
Una se llama soft updates: se trata de rastrear las
dependencias en los cambios de la metadata para grabar s ́olo
cuando hace falta.
Sigue haciendo falta una recorrida por la lista de bloques
libres, pero se puede hacer mientras el sistema est ́a
funcionando.
Otra: journaling. ∆
Journaling
Algunos FS, como ReiserFS, ZFS, ext3, NTFS, etc. llevan un
log o journal.
Ie, un registro de los cambios que habr ́ıa que hacer.
Eso se graba en un buffer circular. Cuando se baja el cach ́e a
disco, se actualiza una marca indicando qu ́e cambios ya se
reflejaron.
Si el buffer se llena, se baja el cach ́e a disco.
Hay un impacto en performance pero es bajo porque:
Este registro se escribe en bloques consecutivos, y una
escritura secuencial es mucho m ́as r ́apida que una aleatoria.
Los FS que no hacen journal escriben a disco inmediatamente
los cambios en la metadata, para evitar da ̃nos mayores en los
archivos.
Cuando el sistema levanta, se aplican los cambios a ́un no
aplicados. Esto es mucho m ́as r ́apido que recorrer todo el
disco.
Caracter ́ısticas avanzadas
Otras cosas que puede incluir un FS avanzado:
Cuotas de disco:
Idea: limitar cu ́anto espacio puede utilizar cada usuario.
Notar: puede ser dif ́ıcil de implementar. No alcanza con poner
un contador simple en el write() porque puede haber escrituras
concurrentes.
Encripci ́on:
¿C ́omo/d ́onde guardo la clave?
Por ejemplo, CFS y EFS.
Snapshots:
Son “fotos” del disco en determinado momento.
Se hacen inst ́aneamente.
El SO s ́olo duplica los archivos que se modifican.
Muy bueno para hacer copias de seguridad.
Btrfs
Caracter ́ısticas avanzadas (cont.)
Manejo de RAID por software.
Desventaja: m ́as lento.
Ventaja: mayor control.
Independencia de proveedor.
A veces, nuevos niveles de redundancia (por ejemplo, ZFS).
Compresi ́on.
Performance
Muchos factores impactan en el rendimiento:
Tecnolog ́ıa de disco.
Pol ́ıtica de scheduling de E/S.
Tama ̃nos de bloque.
Cach ́es del SO.
Cach ́es de las controladoras.
Manejo general de locking en el kernel.
FS
Journaling vs. softupdates. La batalla continua...
Ver por ejemplo;
http://www.usenix.org/event/usenix2000/general/
full_papers/seltzer/seltzer_html/
¿Hasta el ́ultimo nanosegundo de performace? Tal vez pueda
sacrificar un poco en pos de mantenibilidad o robustez.
Algunos n ́umeros - Ext2
Supongamos una particion Ext2 de 8GB, con bloques de 4KB.
El bloque de bitmap de datos (4KB) describe 32K bloques de
datos (es decir, 128 MB).
Entonces, como mucho se requieren 64 grupos de bloques.
M ́as info: Libro Undestanding the Linux Kernel - 3rd edition