sistemas de archivos sebastián sánchez prieto. sistemas de archivos 2 1999-2004 s2p, ogp &...
TRANSCRIPT
Sistemas de Archivos
Sebastián Sánchez Prieto
1999-2004 S2P, OGP & IGT Sistemas de Archivos 2
Objetivo del SdA
Ocultar al usuario los detalles relativos al almacenamiento de información en dispositivos físicos mediante el uso de abstracciones
La abstracción fundamental proporcionada al usuario es el archivo
Un archivo es una secuencia lógica de datos agrupados bajo un nombre que el propio usuario asigna
Los usuarios pueden referirse al nombre de un archivo independientemente de dónde y cómo se halle físicamente almacenado
1999-2004 S2P, OGP & IGT Sistemas de Archivos 3
Visión funcional: servicios
Servicio de nombrado Identifica un archivo dentro de algún tipo de organización
lógica (p.e jerárquica) Tipo del archivo, que permite saber qué tipo de información
contiene Servicios de almacenamiento
Seguridad, protección y cifrado. Necesario en sistemas multiusuario
Archivos compartidos por varios usuarios Tratamiento especial según el tipo de archivo (FIFOS,
enlaces, dispositivos) Servicios de directorio
Organización lógica (p.e directorios jerárquicos) Publicidad de la información
1999-2004 S2P, OGP & IGT Sistemas de Archivos 4
Visión funcional: organización lógica
En la vida real, las carpetas (archivos) en una oficina se agrupan siguiendo algún criterio establecido por el usuario formando grupos. A estos grupos se les asigna un nombre distinguirlos de otros grupos y para facilitar su localización
Los sistemas de archivos permiten agrupar varios archivos en directorios
Cada directorio tiene un nombre lógico asignado por el usuario
Inicialmente un archivo pertenece a un directorio, aunque sería interesante que un mismo archivo pudiera pertenecer a la vez a varios directorios
1999-2004 S2P, OGP & IGT Sistemas de Archivos 5
Visión funcional: directorios
Directorio único u organización a un solo nivel: Todos los archivos están almacenados en un solo directorio Es la estructura más simple y fácil de soportar y entender No permite clasificar la información de ninguna manera Si el sistema es multiusuario pueden existir problemas para
nombrar los archivos, aunque el espacio de nombres sea muy grande
Directorio por cada usuario u organización a dos niveles: Se asigna un directorio a cada usuario o a cada tipo de archivo Existe un directorio de directorios por encima (Directorio maestro) Existen operaciones para actualizar el Directorio maestro Las operaciones sobre directorios se reducen al del usuario Existen problemas para cooperar entre usuarios
1999-2004 S2P, OGP & IGT Sistemas de Archivos 6
Visión funcional: directorios
Estructura jerárquica en árbol: Es el caso de UNIX No hay diferencia entre el directorio raíz y cualquier otro a
otro nivel Para referirse a un archivo completo es necesario saber su
nombre y el nombre de todos los directorios, desde la raíz hasta el que lo contiene (camino absoluto), o bien desde el directorio actual (camino relativo)
UNIX puede trabajar con cualquier jerarquía de directorios, pero existe una estandarizada
1999-2004 S2P, OGP & IGT Sistemas de Archivos 7
Visión funcional: directorios
/
bin boot dev
X11R6
homelib mntproc sbinetc usr
dict
include
lib
local
man
sbin
share
src
oscar
chan
nacho
var
spool
log
nis
cdrom
floppy
stick
...
... ...
...
progs
mp3
docs
1999-2004 S2P, OGP & IGT Sistemas de Archivos 8
Visión estructural: asignación El sistema de archivos es el encargado de relacionar el nombre del un
archivo con los datos que éste contiene Alternativas de almacenamiento:
Contigua Crecimiento del tamaño de los archivos problemático La política de asignación lleva a fragmentación externa Reubicar la información es un procedimiento muy costoso
Por bloques Elección del tamaño de bloque (fragmentación interna) Contabilidad de bloques libres Es necesario un mecanismo para averiguar qué bloques pertenecen a un
archivo Habitualmente los dispositivos de almacenamiento permiten guardar y
recuperar bloques de tamaño fijo que dependen de su geometría
0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20 21
22 23 24 25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40 41 42 43
.. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. N-2 N-1 N
Archivo 1
Archivo 2
Archivo 3
1999-2004 S2P, OGP & IGT Sistemas de Archivos 9
Visión estructural: localización
Tablas de bloques Mantener una tabla con los
bloques de cada archivo Se guarda el nombre del
archivo junto con el primer bloque que ocupa
El resto de los bloques se obtiene utilizando una estructura de datos especial (FAT)
Para buscar un bloque hay que recorrer todos los anteriores
0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20 21
.. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. N-2 N-1 N
0
1
2
3
4
5
6
7
8
10
9
0
5
3
4
EOF
6
8
7
10
9
EOF
EOF
Archivo 1
Archivo 2
Archivo 3
2
1
7
1999-2004 S2P, OGP & IGT Sistemas de Archivos 10
Visión estructural: localización
Bloques enlazados Se guarda el nombre del
archivo junto con el primer bloque que ocupa
Cada bloque guarda qué bloque es el siguiente
Para buscar un bloque hay que recorrer todos los anteriores
Los bloques de datos contienen información del sistema de archivos, no solo del usuario
Archivo 1
Archivo 2
Archivo 3
2
1
7
0
1
2
3
4
5
6
7
8
9
1999-2004 S2P, OGP & IGT Sistemas de Archivos 11
Visión estructural: localización
Nodos índice Junto con el nombre del
archivo se guardan punteros a todos sus bloques
¿Cuántos bloques ocupará el archivo?
En caso de que el archivo sea muy grande podemos usar distintos niveles de indirección usando para ello bloques de almacenamiento
Archivo 1
Archivo 2
Archivo 3
3
5
9
4
6
10
8
7
0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20 21
22 23 24 25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40 41 42 43
.. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. N-2 N-1 N
11
12
.. .. ....
...... ..
..
11
13 14 15 27
1999-2004 S2P, OGP & IGT Sistemas de Archivos 12
Sistema de archivos FAT
Se divide el disco en bloques de tamaño fijo
Cada archivo se compone de una secuencia de bloques formando una lista enlazada mediante punteros
Para encontrar un bloque es necesario recorrer todos los anteriores
El tamaño de cada una de ellas es fijo y depende del tipo de FAT que utilicemos
Datos
Root Directory
FAT
Boot Record
1999-2004 S2P, OGP & IGT Sistemas de Archivos 13
Ejemplo de sistema de archivos FAT-12
En linux podemos crear un sistema de archivos FAT 12 con la orden:# mkfs.vfat –v /dev/fd0/dev/fd0 has 2 heads and 18 sectors per track,
logical sector size is 512,
using 0xf0 media descriptor, with 2880 sectors;
file system has 2 12-bit FATs and 1 sector per cluster.
FAT size is 9 sectors, and provides 2847 clusters.
Root directory contains 224 slots.
Volume ID is 3fb0ff43, no volume label.
La geometría utilizada en el disquete es: 2 cabezas (2 caras), 18 sectores/pista, 80 pistas por cada cara 2 caras * 80 pistas / cara * 18 sectores/pista = 2880 sectores 2880 sectores * 512 bytes /sector = 1440 Kbytes
Se utiliza un sector por cada cluster Hay dos FAT (copia de seguridad) que ocupan cada una 9
sectores, es decir 9*512=4608 bytes
1999-2004 S2P, OGP & IGT Sistemas de Archivos 14
Sector de arranque (boot sector) Comienza en el primer sector del disco. Ocupa un sector (512 bytes) en FAT12 y FAT16 y 32 sectores en FAT32 Normalmente la información contenida en el Boot Record ocupa sólo 62
bytes Contiene el código que se utiliza durante el arranque para cargar el sistema
operativo en memoria# hexdump -C -s 0x0000 -n 512 /dev/fd000000000 eb 3c 90 6d 6b 64 6f 73 66 73 00 00 02 01 01 00 |.<.mkdosfs......|00000010 02 e0 00 40 0b f0 09 00 12 00 02 00 00 00 00 00 |...@............|00000020 00 00 00 00 00 00 29 a7 b0 7b 40 20 20 20 20 20 |......)..{@ |00000030 20 20 20 20 20 20 46 41 54 31 32 20 20 20 0e 1f | FAT12 ..|00000040 be 5b 7c ac 22 c0 74 0b 56 b4 0e bb 07 00 cd 10 |.[|.".t.V.......|00000050 5e eb f0 32 e4 cd 16 cd 19 eb fe 54 68 69 73 20 |^..2.......This |00000060 69 73 20 6e 6f 74 20 61 20 62 6f 6f 74 61 62 6c |is not a bootabl|00000070 65 20 64 69 73 6b 2e 20 20 50 6c 65 61 73 65 20 |e disk. Please |00000080 69 6e 73 65 72 74 20 61 20 62 6f 6f 74 61 62 6c |insert a bootabl|00000090 65 20 66 6c 6f 70 70 79 20 61 6e 64 0d 0a 70 72 |e floppy and..pr|000000a0 65 73 73 20 61 6e 79 20 6b 65 79 20 74 6f 20 74 |ess any key to t|000000b0 72 79 20 61 67 61 69 6e 20 2e 2e 2e 20 0d 0a 00 |ry again ... ...|000000c0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|*000001f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 55 aa |..............U.|
1999-2004 S2P, OGP & IGT Sistemas de Archivos 15
Interpretación del sector de arranqueEB 3C 90 Instrucción de salto al código de arranque
6D 6B 64 6F 73 66 73 00 Identificación del creador del sistema de archivos. Eneste caso MKDOSFS
00 02 Bytes por sector, en este caso 512 bytes
01 Sectores por cada cluster. En este caso 1
01 Sectores reservados. Número de sectores que hay antes de la FAT. Normalmente 1: el bootrecord00
02 Número de copias de la FAT. Habitualmente 2
E0 00 Número de entradas en la tabla de directorio. En este caso 224 entradas máximo
40 Número de sectores que ocupa la partición. En este caso 2880 sectores de 512 bytes = 1,4M0B
F0 Descriptor de soporte físico. F0 = FDD 1.44 MB 3.5" dos caras, 18 sectores por pista
09 00 Número de sectores que ocupa la FAT. En este caso 9
0
3
11
13
14
16
17
19
21
22
12 00 Número de sectores por cada pista. En este caso 18 sectores por cada pista
02 00 Número de cabezas lectoras. En este caso 2
00 0000 00 Número de sectores ocultos. Son los sectores que aparecen físicamente antes del sector deboot. Son necesario para asegurar el arranque correcto del sistema
00 0000 00 Número de sectores que ocupa la partición. Este campo se utiliza con discos duros, donde elnúmero de sectores no cabe en el campo “número de sectores” anterior
54 3146 41 20 2032 20 Firma con la identificación del sistema de archivos. En este caso FAT12
24
26
32
28
00 Número de dispositivo físico. 00 para FDD y 80h para discos duros36
00 Cabezal actual. Lo utiliza WinNT internamente37
00 Firma del sistema operativo que creó el disco. 29h = WinNT38
43 Número de serie del dispositivo. Actualmente 4 bytes aleatorios39 B0 3FFF
43 20 20... Nombre del sistema de archivos. 11 bytes
54
1999-2004 S2P, OGP & IGT Sistemas de Archivos 16
Tabla de asignación de archivos (FAT)
Está situada después del boot sector Sirve para averiguar los clusters que componen un archivo En el caso de FAT-12 cada entrada ocupa 12 bits, lo que permite
direccionar hasta 2^12=4092 bloques de disco (clusters). Si el tamaño de bloque es 512, el tamaño máximo del sistema de
archivos con FAT-12 es de 4092*512=2^21= 2Mb ¿Y si el sistema de archivos es más grande?
Solución 1: Aumentar el tamaño del bloque Sistema de archivos de 4 Gb (2^32) FAT-12. Capacidad de direccionamiento 2^12 bloques Tamaño del bloque 2^32/2^12 = 2^20 = 1Mb cada bloque ¿Cuánto ocupará en el disco un archivo de 20Kb?
Solución 2: Aumentar el tamaño de las entradas en la FAT FAT-16 FAT-32: Capacidad de direccionamiento 2^32 bloques de 1K/bloque
1999-2004 S2P, OGP & IGT Sistemas de Archivos 17
Tabla de asignación de archivos (FAT)
Cada entrada en la FAT puede significar: 0 = cluster libre 0xFF0-0xFF6 = cluster reservado para
uso interno 0xFF7 = cluster con sectores erróneos Si es un número indica cual es el
siguiente cluster del archivo 0xFF8-0xFFF = Último cluster del
archivo Por ejemplo. Si sabemos que un archivo
comienza en el cluster 3 y tenemos la FAT de la figura, podemos decir que ese archivo se compone de los clusters 3,12 y 18
123
2
1
0x0000
0x0000
0x00000
...
18
...
12
12313
... ...
18 0xFFF
1999-2004 S2P, OGP & IGT Sistemas de Archivos 18
Directorio raíz
Se encuentra en una posición fija del disco Está limitada en tamaño Contiene los nombres de archivos y directorios que se
encuentren en el directorio raíz junto con su primer bloque de disco. Con esta información, consultando la FAT podemos averiguar el resto
223 Nombre de archivo ext atr Reservados Fecha1er
ClusterTamaño
... ... ... ... ... ... ... ...
1 Nombre de archivo ext atr Reservados Fecha1er
ClusterTamaño
Nombre de archivo ext atr Reservados Fecha1er
ClusterTamaño
32 bytes
0
1999-2004 S2P, OGP & IGT Sistemas de Archivos 19
Ejemplo de estructura del directorio raíz
Para localizar la posición del directorio raíz en el disco hay que tener en cuenta que: El sector de boot comienza en el 0 y ocupa 1
sector La tabla FAT ocupa 9 sectores Hay dos tablas FAT Por lo tanto el directorio comienza en el sector
19. 19 * 512 bytes/sector = offset 9728 bytes =
0x2600 Cada entrada en el directorio ocupa 32 bytes y
hay 224 entradas. 224*32= 7168 bytes = 14 sectores
1999-2004 S2P, OGP & IGT Sistemas de Archivos 20
Ejemplo de estructura del directorio raíz# hexdump -C -s 0x2600 -n 512 /dev/fd000002600 e5 2e 00 73 00 77 00 70 00 00 00 00 00 c3 ff ff |...s.w.p........|00002610 ff ff ff ff ff ff ff ff ff ff 00 00 ff ff ff ff |................|00002620 e5 2e 00 61 00 72 00 63 00 68 00 00 00 c3 69 00 |...a.r.c.h....i.|00002630 76 00 6f 00 32 00 2e 00 74 00 00 00 78 00 74 00 |v.o.2...t...x.t.|00002640 e5 52 43 48 49 56 7e 31 53 57 50 20 00 00 0b 66 |.RCHIV~1SWP ...f|00002650 8d 30 8d 30 00 00 0b 66 8d 30 0b 00 00 10 00 00 |.0.0...f.0......|00002660 41 61 00 72 00 63 00 68 00 69 00 0f 00 b5 76 00 |Aa.r.c.h.i....v.|00002670 6f 00 31 00 2e 00 74 00 78 00 00 00 74 00 00 00 |o.1...t.x...t...|00002680 41 52 43 48 49 56 4f 31 54 58 54 20 00 00 09 66 |ARCHIVO1TXT ...f|00002690 8d 30 8d 30 00 00 09 66 8d 30 0a 00 23 00 00 00 |.0.0...f.0..#...|000026a0 41 61 00 72 00 63 00 68 00 69 00 0f 00 55 76 00 |Aa.r.c.h.i...Uv.|000026b0 6f 00 32 00 2e 00 74 00 78 00 00 00 74 00 00 00 |o.2...t.x...t...|000026c0 41 52 43 48 49 56 4f 32 54 58 54 20 00 00 10 66 |ARCHIVO2TXT ...f|000026d0 8d 30 8d 30 00 00 10 66 8d 30 13 00 26 00 00 00 |.0.0...f.0..&...|
0x26C0 41 52 43 48 49 56 4F 32
54 58 54
20
Nombre del archivo
ARCHIVO2
TXTExtensión
attr
20attr
10Hora
66
00Reservados
00 10 66 8D 30 8D 30 00 00
Atributos
Reservados
Hora*2048+Min*32+sec/2 => 12:48
20attr
8DFecha
30 (Año-1980)*512 + Mes*32 + Dia => 13/4/2004
20attr
13Primer cluster
00 Primer cluster = 0x0013 = 19d
20attr
26Tamaño del archivo
00 00 00 Tamaño del archivo 0x00000026=38 bytes
0 0 1 0 0 0 0 0
Re
serv
ad
o
Re
serv
ad
o
Arc
hiv
o
Dir
ect
orio
Etiq
. V
olu
m.
Sis
tem
a
Ocu
lto
So
lo le
ctu
ra
1999-2004 S2P, OGP & IGT Sistemas de Archivos 21
Ejemplo de localización de datos
Localicemos los datos del archivo2.txt Sabemos que comienza en el cluster 19 Para averiguar cuantos datos contiene consultamos la
FAT (sector 1 del disco, desplazamiento 512 bytes)# hexdump -C -s 512 -n 512 /dev/fd0
200 00000200 f0 ff ff 00 00 00 00 00 00 00 00 00 00 00 00 ff
201 00000210 0f 00 00 00 00 00 00 00 00 00 00 00 f0 ff 00 00
202 00000220 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
FAT12 = 12 bit para cada entrada (packing) Cada 24 bits dos entradas Clusters 18 y 19 = 00 F0 FF
Cluster 18: 000 (libre) Cluster 19: FFF (último cluster del archivo)
Por lo tanto nuestro archivo solo tiene un cluster, el 19
1999-2004 S2P, OGP & IGT Sistemas de Archivos 22
Ejemplo de localización de datos
Para localizar el cluster 19 en el disco hay que tener en cuenta: Los sectores de datos comienzan en el 33 (Boot sector + 18
sectores de las dos tablas FAT + 14 sectores del directorio raíz) Los dos primeros clusters están reservados, por lo tanto hay que
restar 2 al número de cluster lógico: Las operaciones a realizar serán:
Restar 2 unidades del cluster lógico 19-2=17 Multiplicar el cluster por el número de sectores por cluster (1 en
nuestro caso)= 17*1=17 Sumar 33 al resultado 17+33= sector 50
La posición dentro del dispositivo de almacenamiento será 50*512=25600 (0x6400h)# hexdump -C -s 0x6400 -n 10000 /dev/fd0
00006400 45 73 74 65 20 65 73 20 65 6c 20 63 6f 6e 74 65 |Este es el conte|
00006410 6e 69 64 6f 20 64 65 6c 20 61 72 63 68 69 76 6f |nido del archivo|
00006420 32 2e 74 78 74 0a 00 00 00 00 00 00 00 00 00 00 |2.txt...........|
00006430 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
1999-2004 S2P, OGP & IGT Sistemas de Archivos 23
Sistema de archivos de UNIX System V
El sistema de archivos reside en cualquier dispositivo que permita almacenar bloques de información; típicamente una partición de un disco
El espacio de almacenamiento se interpreta como una lista de bloques
El tamaño de los bloques marca la granularidad del almacenamiento
El tamaño de bloque físico es de 512 bytes El sistema de archivos trabaja con bloques lógicos. El
manejador de dispositivo se encargará de hacer las traducciones a bloque físico en caso de que fuera necesario
1999-2004 S2P, OGP & IGT Sistemas de Archivos 24
Nodos índice Unix identifica un archivo a
través de un nodo índice (i-node o nodo-i) que almacena toda la información necesaria para localizar los bloques que componen dicho archivo
Cada nodo-i ocupa 128 en Linux 2.2
Punterosdirectos
modo
propietario
tamaño
fecha
Bloquefísico
Bloquefísico
Bloquefísico
Puntero indirectosimple
Puntero indirectodoble
Puntero indirectotriple
Bloquefísico
punteros
Bloquefísico
Bloquefísico
Bloquefísico
Modo: indica qué tipo de archivo es y cuáles son los permisos de acceso al mismo
Propietario: UID y GID del propietario del archivo Punteros directos: 12 punteros directos (32 bit cada uno) Tres punteros con uno, dos y tres niveles de indirección
respectivamente
1999-2004 S2P, OGP & IGT Sistemas de Archivos 25
Tipos de archivos
El tipo de archivo al que se refiere un nodo-i se almacena en el campo modo
Dependiendo del tipo de archivo se aplicará un tratamiento especial: Archivos regulares: necesitan bloques para
almacenar datos Directorios: archivos especiales cuyos bloques
contienen nombres y nodos-i de otros archivos Enlaces simbólicos: contienen el nombre de otro
archivo al que hace referencia.
1999-2004 S2P, OGP & IGT Sistemas de Archivos 26
Archivos especiales: directorios
Los directorios almacenan los nombres que los usuarios dan a sus archivos y los relacionan con sus nodos índice
UNIX establece una relación jerárquica en sus directorios El primer directorio de la jerarquía recibe el nombre de
raíz o root. Los directorios pueden contener cualquier otro objeto del
sistema de archivos (p.e. otro directorio) Cada entrada en un directorio almacena, entre otras
cosas, la siguiente información: Nombre del objeto del sistema de archivos i-node número de nodo índice de dicho objeto
¿Cómo se localiza el nodo índice del archivo /home/elena/quijote.txt?
1999-2004 S2P, OGP & IGT Sistemas de Archivos 27
Búsqueda de un archivo
i-node 9562i-node 9563i-node 9564
i-node 0i-node 1i-node 2i-node 3
1
Buscar el númerode i-node
correspondiente aldirectorio raíz 2
nombrei-node...
usr
213233245
etc...
4332...
34 homei-node 34
dev
34nombrei-node
...
juan
2567655
maria...
887...
776 elena
pedroi-node 775i-node 776i-node 777
776nombrei-node
...
asereje.mp3
3454431244
practica.c...
2759...
9563 quijote.txt
sda.pdf
i-node 33
En un lugar de La Mancha, decuyo nombre no quiero
acordarme, no ha muchotiempo vivía un hidalgo ...
1999-2004 S2P, OGP & IGT Sistemas de Archivos 28
Contabilidad de uso del SdA
Para llevar la contabilidad del espacio disponible en el sistema de archivo se emplean dos estructuras:
Mapa de bit de bloques Mapa de bit de nodos índice
Un mapa de bit es una estructura de datos en la que cada bit representa si un bloque o nodo índice se encuentra libre u ocupado
El tamaño de ambos dependerá del tamaño del sistema de archivos.
Por ejemplo, un sistema de archivos con 256 nodos índice tendrá un mapa de bits de nodos índice con 256/8=32 bytes
1999-2004 S2P, OGP & IGT Sistemas de Archivos 29
Superbloque
Es una estructura de datos que contiene información global sobre el sistema de archivos
La información más importante que mantiene es la siguiente:
Número mágico (0xEF53) indica al software del sistema de archivos que se trata de un sistema de tipo EXT2
Tamaño del bloque del sistema de archivos (p.e 1024) Número de bloques libres Número de nodos índice libres Número del primer nodo índice. Normalmente este nodo
índice es el del directorio raíz (nodo-i número 2).
1999-2004 S2P, OGP & IGT Sistemas de Archivos 30
Creación de un sistema de archivos Un dispositivo de
almacenamiento es una secuencia de bloques de almacenamiento sin ningún significado especial
Cada sistema de archivo escribe en esos bloques la información necesaria para mantener los archivos, directorios, etc. (Metainformación)
El proceso de creación de un sistema de archivos se llama formateado
Por ejemplo, para formatear un disquete con el sistema de archivos ext2 se emplea la siguiente orden mkfs.ext2
# mkfs.ext2 -v /dev/fd0mke2fs 1.27 (8-Mar-2002)Filesystem label=OS type: LinuxBlock size=1024 (log=0)Fragment size=1024 (log=0)184 inodes, 1440 blocks72 blocks (5.00%) reserved for the super userFirst data block=11 block group8192 blocks per group, 8192 fragments per group184 inodes per group
Writing inode tables: doneWriting superblocks and filesystem accounting information: done
#
1999-2004 S2P, OGP & IGT Sistemas de Archivos 31
Creación de un sistema de archivos
27
6
0
1
2
3
4
5
Superbloque
Descriptores de grupo
Mapa de bits debloques
Mapa de bits denodos índice
i-node 1i-node 2i-node 3i-node 4i-node 5i-node 6
i-node 11
Directorio raíz
Bloques defectuosos
Access Control Lists
Access Control Lists
Bootloader
Recuperación inodes borrados
Último nodo índice utilizable
i-node 183i-node 184
Primer nodo índice utilizable
Sector de arranque
i-node 7
29
1439Bloque de datos
1438
Bloque de datos
Bloque de datos
28
Bloque de datos
Bloque de datos
1999-2004 S2P, OGP & IGT Sistemas de Archivos 32
Superbloque# dumpe2fs /dev/fd0dumpe2fs 1.27 (8-Mar-2002)Filesystem volume name: <none>Last mounted on: <not available>Filesystem UUID: 685cf75c-936d-4802-9813-
243a7e9a3902Filesystem magic number: 0xEF53Filesystem revision #: 1 (dynamic)Filesystem features: filetype sparse_superFilesystem state: cleanErrors behavior: ContinueFilesystem OS type: LinuxInode count: 184Block count: 1440Reserved block count: 72Free blocks: 1396Free inodes: 170First block: 1Block size: 1024Fragment size: 1024Blocks per group: 8192Fragments per group: 8192Inodes per group: 184Inode blocks per group: 23Last mount time: Thu Jan 1 01:00:00 1970Last write time: Sat Apr 10 22:24:18 2004Mount count: 0Maximum mount count: 29Last checked: Sat Apr 10 22:10:04 2004Check interval: 15552000 (6 months)Next check after: Thu Oct 7 22:10:04 2004Reserved blocks uid: 0 (user root)Reserved blocks gid: 0 (group root)First inode: 11Inode size: 128
Group 0: (Blocks 1-1439) Primary Superblock at 1, Group Descriptors at 2-2 Block bitmap at 3 (+2), Inode bitmap at 4 (+3) Inode table at 5-27 (+4) 1396 free blocks, 170 free inodes, 5 directories Free blocks: 44-1439 Free inodes: 15-184
Número mágico 0xEF53 Tamaño del bloque 1024 bytes Número de nodos índice 184 Número de bloques 1440 Bloques libres 1396 Tamaño del nodo índice 128 bytes
1999-2004 S2P, OGP & IGT Sistemas de Archivos 33
Ejemplo: Localizar el directorio raíz Creamos un directorio lectura con un archivo llamado quijote.txt
# mkdir lecturas# echo En un lugar de la mancha de cuyo nombre no quiero arcordarme >
quijote.txt
Vamos a localizar el bloque de disco que contiene la información del archivo /lecturas/quijote.txt
Buscamos el nodo índice número 2 que contiene los archivos del directorio raíz. Según la información anterior la tabla de nodos índice comienza en el bloque 5. El inode-2 comenzará en la posición 128 de ese bloque, o lo que es lo mismo (5*1024)+128 = 5248 = 0x1480# hexdump -C -s 0x1400 -n 256 /dev/fd000001400 00 00 00 00 00 00 00 00 11 87 79 40 11 87 79 40 |[email protected]@|00001410 11 87 79 40 00 00 00 00 00 00 00 00 00 00 00 00 |..y@............|00001420 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|*00001480 ed 41 00 00 00 04 00 00 a6 8a 79 40 7f 8a 79 40 |[email protected]@|00001490 7f 8a 79 40 00 00 00 00 00 00 04 00 02 00 00 00 |..y@............|000014a0 00 00 00 00 00 00 00 00 1c 00 00 00 00 00 00 00 |................|000014b0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
1999-2004 S2P, OGP & IGT Sistemas de Archivos 34
Ejemplo: Localizar el directorio raíz
El nodo índice indica que la entrada es un directorio y que el bloque que contiene los datos es el 0x0000001C. Ese bloque de datos comenzara en la posición 0x400*0x1C=0x7000# hexdump -C -s 0x7000 -n 1024 /dev/fd0
00007000 02 00 00 00 0c 00 01 02 2e 00 00 00 02 00 00 00 |................|
00007010 0c 00 02 02 2e 2e 00 00 0b 00 00 00 14 00 0a 02 |................|
00007020 6c 6f 73 74 2b 66 6f 75 6e 64 00 00 0c 00 00 00 |lost+found......|
00007030 d4 03 08 02 6c 65 63 74 75 72 61 73 00 00 00 00 |....lecturas....|
00007040 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
*
00007400
struct ext2_dir_entry_2 {
__u32 inode; /* Inode number; 0: unused */
__u16 rec_len; /* Directory entry length */
__u8 name_len; /* Name length */ __u8 file_type;
char name[up to 255]; /* File name */
};
1999-2004 S2P, OGP & IGT Sistemas de Archivos 35
Ejemplo: Localizar el archivo quijote.txt El nodo índice del directorio lecturas es el 0x1C. Buscamos esa entrada en la
tabla de directorios y obtenemos que su bloque de datos asociado es 0x29. La posición en el disco será 0x29*0x400=0xA400# hexdump -C -s 0xa400 -n 1024 /dev/fd00000a400 0c 00 00 00 0c 00 01 02 2e 00 00 00 02 00 00 00 |................|0000a410 0c 00 02 02 2e 2e 00 00 0d 00 00 00 e8 03 0b 01 |................|0000a420 71 75 69 6a 6f 74 65 2e 74 78 74 00 00 00 00 00 |quijote.txt.....|0000a430 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|*0000a800
El nodo índice del archivo quijote.txt es el 0x0D (13d). Buscamos ese nodo índice y obtenemos que su bloque de datos asociado es el 0x2A. Su posición en el disco será 0x2A*0x400=0xA800# hexdump -C -s 0xA800 -n 1024 /dev/fd00000a800 45 6e 20 75 6e 20 6c 75 67 61 72 20 64 65 20 6c |En un lugar de l|0000a810 61 20 6d 61 6e 63 68 61 20 64 65 20 63 75 79 6f |a mancha de cuyo|0000a820 20 6e 6f 6d 62 72 65 20 6e 6f 20 71 75 69 65 72 | nombre no quier|0000a830 6f 0a 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |o...............|0000a840 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|*0000ac00
1999-2004 S2P, OGP & IGT Sistemas de Archivos 36
Ejemplo: contabilidad
i-node Propósito
2 Directorio raíz
12 lecturas
13 quijote.txt
0
1
2
3
4
Superbloque
Descriptores de grupo
Mapa de bits debloques
Mapa de bits denodos índice
Sector de arranque
1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 0Bit
me
nos
sign
ifica
tivo
Bit
má
ssi
gn
ifica
tivo
Número de bloque
Estado
1
0x1000 FF 001F 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1010 00 00 00 00 00 00 00B
it m
en
os
sign
ifica
tivo
Bit
má
ssi
gn
ifica
tivo
Número de bloque
Estado
1999-2004 S2P, OGP & IGT Sistemas de Archivos 37
0
1
2
3
4
Superbloque
Descriptores de grupo
Mapa de bits debloques
Mapa de bits denodos índice
Sector de arranque
1 1 1 1 1 1 1 1 1 1 1 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 0Bit
me
nos
sign
ifica
tivo
Bit
má
ssi
gn
ifica
tivo
Número de bloque
Estado
1
0x1000 FF 0007 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1010 00 00 00 00 00 00 00B
it m
en
os
sign
ifica
tivo
Bit
má
ssi
gn
ifica
tivo
Número de bloque
Estado
Ejemplo: contabilidad
Si borramos el directorio lecturas se liberan dos entradas en la tabla de nodos índices (lecturas y quijote)
En el mapa de nodos índice aparecen dichos nodos (12 y 13) como libres
Se puede volcar el mapa de bit con la orden: # hexdump -C -s 0x1000 -n 1024 /dev/fd0
1999-2004 S2P, OGP & IGT Sistemas de Archivos 38
Concepto de montaje de SdA
Un sistema de archivos reside en un dispositivo de almacenamiento.
Si tenemos varios sistemas de archivos es posible combinarlos todos formando una única jerarquía
Partiendo de una estructura jerárquica de directorios, es posible colgar de cualquier rama otro sistema de archivos distinto. A este procedimiento se le llama montaje de un sistema de archivos
El usuario no percibe en qué sistema de archivos residen realmente sus datos
Utilizando esta técnica podemos combinar varios sistemas de archivos (diferentes incluso) en una única jerarquía
1999-2004 S2P, OGP & IGT Sistemas de Archivos 39
Montaje de sistemas de archivos
/
/
bin
boot
home
lib
mnt
proc
etc
usr
var
/
practica1
ejercicios
document
/
oscar
chan
nacho
/
bin
boot
home
lib
mnt
proc
etc
usr
var
/
practica1
ejercicios
document
oscar
chan
nacho
EX
T2
FA
T3
2
CIF
1999-2004 S2P, OGP & IGT Sistemas de Archivos 40
Montaje de sistemas de archivos Cada sistema de archivos puede ser de tipos diferentes Cada uno de ellos tiene su propia metainformación (p.e.
superbloque, tabla de nodos índice, etc) Esto significa que habrá tantos nodos índice con el número 2
(directorio raíz) y tantas tablas de nodos índice como sistemas de archivos tengamos montados
El sistema de archivos utiliza la metainformación del sistema de archivos donde nos encontremos
El sistema operativo lleva el control de los sistemas de archivos montados:
# cat /etc/mtab/dev/hda1 / ext2 rwproc /proc proc rw devpts /dev/pts devpts rw/dev/hdb1 /mnt/data ext2 rw/dev/fd0 /mnt/disquete ext2 rw
1999-2004 S2P, OGP & IGT Sistemas de Archivos 41
Enlaces
El sistema de archivos es capaz de relacionar un nombre de archivo con los bloques de datos que contienen la información de dicho archivo
Puede ser útil utilizar varios nombres para referirse al mismo archivo (alias o enlaces)
En UNIX existen dos tipos de enlaces: Enlaces duros. Consiste en dar una entrada de directorio
con el nodo índice del archivo al que queramos enlazar Enlaces blandos (o simbólicos). Son archivos cuyo bloque
de datos contiene el nombre completo (incluyendo la ruta desde la raíz) del archivo que queremos enlazar
1999-2004 S2P, OGP & IGT Sistemas de Archivos 42
Enlaces duros
Varias entradas de directorio apuntando al mismo nodo índice. Los enlaces duros son indistinguibles del archivo original al que apuntan
Se crean con la orden ln# ln ArchivoOriginal.txt duro1
# ln ArchivoOriginal.txt duro2
# ln ArchivoOriginal.txt duro3
# ls –ali
total 21
2 drwxr-xr-x 3 root root 1024 Apr 12 18:15 .
415172 drwxr-xr-x 4 root root 4096 Apr 12 17:59 ..
12 -rw-r--r-- 4 root root 11 Apr 12 18:10 ArchivoOriginal.txt
12 -rw-r--r-- 4 root root 11 Apr 12 18:10 duro1
12 -rw-r--r-- 4 root root 11 Apr 12 18:10 duro2
12 -rw-r--r-- 4 root root 11 Apr 12 18:10 duro3
11 drwx------ 2 root root 12288 Apr 11 19:57 lost+found
El archivo se elimina cuando no hay referencias a él en ninguna entrada de directorio
El nodo índice al que se hace referencia es el nodo índice del sistema de archivos que contiene el archivo referenciado, por lo tanto no se pueden hacer enlaces duros a archivos que residen en otros sistemas de archivos
Mismo nodo índice
Cuatro referencias al mismo archivo
1999-2004 S2P, OGP & IGT Sistemas de Archivos 43
Enlaces blandos
Los enlaces blandos son archivos que contienen el nombre de otro archivo al que referencian
Como archivos que son tienen su propio nodo índice Se crean con ln –s# ln -s ArchivoOriginal.txt blando1
# ln -s ArchivoOriginal.txt blando2
# ln -s ArchivoOriginal.txt blando3
# ls -ali
total 18 2 drwxr-xr-x 3 root root 1024 Apr 12 18:25 .
415172 drwxr-xr-x 4 root root 4096 Apr 12 17:59 ..
12 -rw-r--r-- 1 root root 11 Apr 12 18:10 ArchivoOriginal.txt
13 lrwxrwxrwx 1 root root 19 Apr 12 18:25 blando1 -> ArchivoOriginal.txt
14 lrwxrwxrwx 1 root root 19 Apr 12 18:25 blando2 -> ArchivoOriginal.txt
15 lrwxrwxrwx 1 root root 19 Apr 12 18:25 blando3 -> ArchivoOriginal.txt
11 drwx------ 2 root root 12288 Apr 11 19:57 lost+found
Los nodos índice 13,14 y 15 son de tipo “enlace”, por lo tanto el sistema de archivos los trata de forma especial
1999-2004 S2P, OGP & IGT Sistemas de Archivos 44
Implementación de los enlaces blandos
Observemos el contenido del nodo índice 13# hexdump -C -s 0x1A80 -n 128 /dev/fd0
00001a80 ff a1 00 00 13 00 00 00 eb c2 7a 40 e8 c2 7a 40 |[email protected]@|
00001a90 e8 c2 7a 40 00 00 00 00 00 00 01 00 00 00 00 00 |..z@............|
00001aa0 00 00 00 00 00 00 00 00 41 72 63 68 69 76 6f 4f |........ArchivoO|
00001ab0 72 69 67 69 6e 61 6c 2e 74 78 74 00 00 00 00 00 |riginal.txt.....|
00001ac0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
*
00001ae0 00 00 00 00 8b 6e 2d 48 00 00 00 00 00 00 00 00 |.....n-H........|
00001af0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00001b00
Los nodos índice nunca almacenan nombres de archivos, de hecho el nombre del archivo está situado en las posiciones correspondientes a los punteros a bloques de disco
Esto es un truco para no desperdiciar un bloque entero de disco para contener solo el nombre de un archivo
Hay 15 punteros de 32 bits. 15*4=60 bytes. Mientras el nombre del archivo de destino sea menor de 60 caracteres se podrá emplear esta técnica
En caso contrario hay que reservar un bloque y escribir el nombre del archivo referenciado en él
1999-2004 S2P, OGP & IGT Sistemas de Archivos 45
Journaled File Systems
El sistema de archivos necesita varias estructuras de datos que mantienen el estado de ese sistema de archivos
A esas estructuras de datos que describen a su vez otros datos reciben el nombre de metadatos o metainformación
La metainformación (p.e. superbloque, mapas de bits, etc) se proyecta en memoria para aumentar la eficiencia del sistema de archivos
Cuando el sistema se apaga, los cambios realizados en el sistema de archivos se graban al disco
¿Qué ocurre si el sistema se apaga de forma irregular? (p.e fallo en la tensión de alimentación)
1999-2004 S2P, OGP & IGT Sistemas de Archivos 46
Control de consistencia: fsck Antes de montar un sistema de archivos hay que asegurarse de que
éste se encuentra en un estado consistente Existe un indicador en el superbloque que informa de si el sistema de
archivos se desmontó correctamente la última vez que se utilizó Si el sistema está marcado como dirty se ejecuta una aplicación que
comprueba e intenta corregir las incosistencias (fsck) Comprobar estado del superbloque Comprobar que los nodos-i ocupados/libres son sólo los
marcados como ocupados/libres en el mapa de bits Comprobar que los bloques asignados según el mapa de bits
están asignados a un archivo, y que no haya archivos que hagan referencia a bloques marcados como libres
Comprobar que un mismo nodo-i no está asignado a más de un directorio
Problemas: Hay que comprobar todo el sistema de archivos Si el sistema de archivos es muy grande la comprobación puede
llevar demasiado tiempo
1999-2004 S2P, OGP & IGT Sistemas de Archivos 47
Corrección de inconsistencias
1 2 3 4 5 6 7 8 9
Número de bloque
Estado según el mapade bits 1 1 0 0 1 0 0 1 1
Número de referenciasencontradas al bloque 0 0 1 1 0 1 1 0 0
1 2 3 4 5 6 7 8 9
Número de bloque
Estado según el mapade bits 1 1 0 0 1 0 0 1 1
Número de referenciasencontradas al bloque 0 0 1 0 0 1 1 0 0
El bloque 4 está marcado como ocupado. Sinembargo no hay referencias a él por parte deningún nodo índice. Se corregirá marcando elbloque como libre
1 2 3 4 5 6 7 8 9
Número de bloque
Estado según el mapade bits 1 1 0 1 1 0 0 1 1
Número de referenciasencontradas al bloque 0 0 1 1 0 1 1 0 0
El bloque 4 está marcado como libre. Sinembargo hay referencias a él por parte dealgún nodo índice. Se corregirá marcando elbloque como ocupado
1 2 3 4 5 6 7 8 9
Número de bloque
Estado según el mapade bits 1 1 0 0 1 0 0 1 1
Número de referenciasencontradas al bloque 0 0 1 2 0 1 1 0 0
El bloque 4 está siendo referenciado por dosnodos índice ¿A cuál de ellos pertenecerealmente?
1999-2004 S2P, OGP & IGT Sistemas de Archivos 48
Control de consistencia: journals
Es una nueva aproximación para controlar la consistencia de los sistemas de archivos
Se añade una nueva estructura de datos a la metainformación que ya existía en el sistema de archivos: el journal
Es un cuaderno de bitácora donde se apuntan por orden cronológico las operaciones que se realizan sobre el sistema de archivos
En el arranque del sistema se comprueba si quedaron operaciones pendientes cuando se apagó (anormalmente) el sistema
El objetivo es asegurar que las transacciones sobre el sistema de archivos se hacen de forma atómica
1999-2004 S2P, OGP & IGT Sistemas de Archivos 49
Control de consistencia: transacciones
Una transacción es un conjunto de varias operaciones sobre un dispositivo de almacenamiento
Las transacciones deben asegurar que o bien se terminan con éxito todas las operaciones que componen la transacción o bien no se realiza ninguna de ellas
El objetivo de impedir que una transacción quede a la mitad es evitar inconsistencias en el sistema de archivos
Una transacción debe cumplir cuatro reglas básicas: Atomicidad: o se realiza completa o no se realiza en
absoluto Consistencia: debe mantener la integridad del sistema Aislamiento: debe ejecutarse como si fuera la única petición
en el sistema, sin depender de ninguna otra Perdurabilidad: los cambios deben prevalecer incluso en el
caso de un error
1999-2004 S2P, OGP & IGT Sistemas de Archivos 50
Transacciones
Operaciones para crear un archivo1. Obtener un número de nodo índice
2. Marcar el nodo como ocupado en el mapa de bits
3. Obtener un bloque libre
4. Marcar el bloque como ocupado en el mapa de bits
5. Rellenar los campos del nodo índice con los datos necesarios
6. Dar de alta el nombre del archivo en el directorio junto con el número de su nodo índice
Todas estas operaciones deben ejecutarse como una transacción. Si se interrumpe durante la ejecución podemos crear inconsistencias (p.e un bloque ocupado que no pertenece a ningún nodo índice)
1999-2004 S2P, OGP & IGT Sistemas de Archivos 51
Transacciones: fundamentos
Actualmente, los discos son capaces de finalizar una escritura completa de un bloque físico de 512 bytes incluso si la tensión de alimentación falla durante dicha operación
Este comportamiento sirve para escribir un sector especial que indica cuando una transacción ha finalizado con éxito (commit)
Ejemplo: dado un vector con 10 números (salarios) incrementar todos en un 50%
10 20 30 40 50
15 20 30 40 50
15 30 30 40 50Fallo
15 30 30 40 50
1999-2004 S2P, OGP & IGT Sistemas de Archivos 52
Transacciones: journal log
El fallo anterior se produce porque los cambios se realizan directamente sobre los datos antiguos
Los sistemas de archivos transacciones escriben las modificaciones a realizar en el log. Si todo sale bien se copia el log en el sistema de archivos
Si se produce un fallo antes de concluir la transacción los datos originales siguen intactos
10 20 30 40 50
Registro de transacciones
15 30
Fallo
1999-2004 S2P, OGP & IGT Sistemas de Archivos 53
Transacciones: registro de transacciones
Si la transacción finaliza, se hace una marca especial en el registro de transacciones (commit)
Hecho esto se copian las modificaciones a su destino final y se elimina la transacción del registro
Si se produce un fallo durante la copia, el sistema detectará que hay una transacción inconclusa y la finalizará
10 20 30 40 50
1
Registro de transacciones
15 30
32
45 60 75
Co
mm
it
4 5
15 30 45 40 50
Registro de transacciones
15 30 45 60 75
Co
mm
it
1 32 Fallo
1999-2004 S2P, OGP & IGT Sistemas de Archivos 54
Sistema de archivos virtual de Unix
Proporciona una capa de abstracción adicional entre los programas de usuario y las distintas implementaciones de cada sistema de archivos
Linux permite montar varios tipos de sistemas de archivos distintos
El objetivo es poder acceder a los archivos independientemente del tipo de sistema de archivos empleado
VFS
NT
FS
FA
T
...
CIF
ISO
96
60
Open (“/home/pedro/miarchivo.txt”) Read Write Close