sistema de ficheros1 horas 1introducciÓn5 2procesos y threads8 3gestiÓn de memoria8...
Post on 22-Jan-2016
219 Views
Preview:
TRANSCRIPT
Sistema de Ficheros 1
Horas
1 INTRODUCCIÓN
5
2 PROCESOS Y THREADS
8
3 GESTIÓN DE MEMORIA
8
4 ENTRADA/SALIDA
4
5 GESTIÓN DE FICHEROS
4
S.O.I TemarioCurso: 04/05
Sistema de Ficheros 2
Tema 4. Sistemas de Ficheros
• INTRODUCCIÓN• Aspectos básicos
• Ficheros
• Directorios
• IMPLEMENTACIÓN• Aspecto de un Sistema de Ficheros
• Almacenamiento de ficheros
• Estructura de los directorios
• Gestión del espacio en disco
• Fiabilidad del Sistema de Ficheros
• Rendimiento del Sistema de Ficheros
Sistema de Ficheros 3
Introducción
Sistema de Ficheros: Organización de la información• Directorios
• Ficheros• Gran capacidad
• Permanente
• Acceso concurrente y seguro
Ficheros
NombrePropietario, Protecciones, Tiempos,Ubicación, Tamaño, Tipo, etc.
Contenido
• Atributos:
• Operaciones:
vs
¿Visible al Usuario?
int open(nombre, modo) Descriptor de Fichero
read (df, ...), write (df, ...), lseek (df, ...)
stat (df, ...), fstat (nombre)
close (df)
Descripción
-rw-r---- 1 pcarazo 2062 14321 May 20 13:52 practica1.c
ls -l
Sistema de Ficheros 4
Introducción
dforg = open (“/usr/pepe/uno.txt”, O_RDONLY, 0);
dfdst = open (“/tmp/copia.txt”,
O_WRONLY | O_CREATE | O_TRUNC, 0600);do {
leidos = read (dforg, &buf, 4096);
write (dfdst, &buf, leidos);
} while (leidos == 4096);
close (dforg); close (dfdst);
cp /usr/pepe/uno.txt /tmp/copia.txt
Otras cuestiones:
Organizaciones: Tipo: Normal, Directorio,
Octeto, registro, árbol, ... Especial, Pipe, ...
Extensiones Acceso: Secuencial/Directo
Sistema de Ficheros 5
Introducción ( Directorios )
NombrePropietario, Protecciones, Tiempos,Ubicación, Tamaño, Tipo, etc.
• Atributos:
• Operaciones: open, read, write, lseek, stat, fstat, close
crear, borrar, renombrar, ... (Ficheros / Directorios)
Descripción
Contenido
Entradas de Ficheros (Nombre [Descripción])
• Estructura:
• 1 Nivel Un único directorio
• 2 Niveles Un directorio por usuario + Directorio Maestro
• M Niveles Árbol de directorios• Nombre de ruta: Absoluta vs Relativa
• Directorio de trabajo (Actual)
Sistema de Ficheros 6
Implementación ( Aspecto de un Sistema de Ficheros )
BLibres Bloques con el contenido de los ficherosDirectorio
Bootstrap Disco de Arranque
Superbloque Tamaño del disco, # máximo de ficheros, ...
Nombre1, Descripción1Nombre2, Descripción2Nombre3, Descripción3......................................NombreN, DescripciónN
MBR Partición activa
Sistema de Ficheros 7
Implementación ( Almacenamiento de Ficheros )
Asignación de bloques contiguos vs dispersos
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 31 2
F2: 4..8F3: 9..15
F1: 0..3 Pros: • Fácil registrar Ubicación (Inicio..Fin)
• Eficiencia en acceso secuencial y directo
Contras: • Dificultad para crecer:
• Crear con el tamaño máximo:
desperdicio, ¿se conoce?
• Buscar un hueco mayor y copiarlo allí
• Complejo elegir dónde ubicar el fichero:• Se borra F2
• Se crea F4 (3)
F4
4..6 6..8
?
Políticas similares a gestión de memoria
En general
Fragmentación ExternaFragmentaciónInterna
Sistema de Ficheros 8
1024
Implementación ( Lista encadenada “distribuida” )
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 31 2
A
A: 6, 2
B: 5, 12
C: 10, 13
B C
Pegas: • Acceso directo ineficiente (muchos accesos):
readByte (A, último) Bloques 6, 8, 4 y 2
• Poca fiabilidad:
¡ Bloque 8 erróneo ! Inaccesibles 4, 2, ...
• Más complejo calcular el acceso directo
readByte (A, 3070) y bloques de 1024B
0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0Bloque lógico Offset
A
8
1022
2B parapuntero
¿necesario?
Sistema de Ficheros 9
XX
0123456789
101112131415
F.A.T.Tamaño
disco
AB
C
AB C
Implementación ( Lista encadenada “centralizada global” )
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 51
FAT
8, 4, 2
9, 12
3, 13
A: 6
B: 5
C: 10
En la descripción del fichero se indica cuál es el primer bloque
En la FAT se indica el resto
8
4
2
EOF
3
13
EOF
9
EOF
12
FREE
FREE
FREEBAD
Acceso directo muy eficiente si toda la FAT
está cargada en M.P.
¿Problemas?
Historia de MSDOS
?
Sistema de Ficheros 10
Implementación ( Lista encadenada “centralizada local” )
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 51
AB C
AB C
2 3 4 5 6 7 8 9 0 1 2 3 4 51
FAT
10 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
C 103
13
¡ Sólo necesario tener en M.P. las FAT de los ficheros abiertos !
¿Tamaño FAT’s?
FAT de 512B, punteros de 2B son 256 punteros
¡Tamaño maximo fichero 256KB!
A
B
C
Cada fichero su FAT
Asignación Indexada
¿Dónde?
Sistema de Ficheros 11
Implementación ( Bloques de índices encadenados “Unix” )
descripción i-nodo
propietario,
tamaño, etc.Ubicación
FAT local de 12 entradas
Ptr[0]
1024
Ptr[1]
Ptr[11]Ptr_I
Bloque dePunterosa datos
¿Cuántos?4Bytes256
Ptr_IIPtr_III
Ficherosde hasta
Leer un byte# accesos
12K 1268K 1,2 64M 1..3 16G 1..4¿Seguro?
hola.txtnombre
contenido
Sistema de Ficheros 12
Implementación ( Estructura de los Directorios )
MSDOS: Ejemplo de disquetes de 360K
Lista de 112 entradas de 32B
Límite sólo para \
10
Nombre EXT LONG
8 3 1 422 2
AtributosOcultoSólo lecturaDirectorio
FechaHora Primer Bloque
FAT¿Inconveniente de nombre y descripción juntos?
FAT1 Bloques con el contenido de ficheros y dir.Directorio
Raíz \FAT2
Sistema de Ficheros 13
7 ptr directos
Ptr_I
Ptr_II
Ptr_III
64B
descripciones 409590
Implementación ( Estructura de los Directorios “UNIX like” )
Bloques ficheros y directorios
/
inodos
0 1 2 3 N
51280
modo# enlaces
uidgid
tamaño
T. acceso
T. modificación
T. cambio inodo
Entradas de 16B
inodo nombre2 14
/1 .1 ..
Bootstrap
Superbloque
inodos libres
Bloques libres
2 hola.txt hola.txt
nombres
¿Gestiónde
entradas?
Sistema de Ficheros 14
Implementación ( Directorios: Nombres de longitud variable )
inodo nombre2 14 a.out
practica.cenUnLugarDeLaMancha.txt
?
inodo nombre
4Longitud
TotalLongitudNombre
2 2 255 como máximo + \0…
Solaris
1055360 12 1 .000
819456 12 2 ..00
1055361 24 14 filesystem.txt00
1055362 20 9 inode.txt000
1055363 16 7 dir.txt0
1055364 20 9 fstat.txt000
1055365 20 11 opendir.txt0
¿ rm fstat.txt ?
36
Sistema de Ficheros 15
Implementación ( Directorios: Ficheros compartidos )
link (“/usr/jim/memo”, “/usr/ast/note”)
/
usrtmp dev
ast jim
gamestest
bin
memo
f.c
prog1memonote
16814070
mailgamestestnote
/usr/ast31705938
binmemof.cprog1
/usr/jim
inodo 702
A: compartir nodo + cuántos
#enlaces
• ¿ jim => rm /usr/jim/memo ?
• ¿ /ast y /jim en S.F. distintos ?
Sistema de Ficheros 16
Implementación ( Directorios: Ficheros compartidos )
link (“/usr/jim/memo”, “/usr/ast/note”)
/
usrtmp dev
ast jim
gamestest
bin
memo
f.c
prog1memonote
inodo 90simbólico
16814090
mailgamestestnote
/usr/ast31705938
binmemof.cprog1
/usr/jim
B: Enlaces simbólicos
modo
/usr/jim/memo
Ptr[0]
?
Sistema de Ficheros 17
Implementación ( Gestión del espacio en disco )• Tamaño del bloque: Cilindro – Pista - Sector
grande
pequeño
• Fragmentación interna ¿1/2 bloque por fichero?
• Peor ajuste al tamaño medio ficheros1984 (1K) ..... 1997 (12K..15K)
• Baja la velocidad de transferencia
Sea:32.768 Bytes por pista16,67 mseg de Trotación30 mseg de Tposicionarse
Kbytes/s
128 256 512 1K 2K 4K 8KTamaño
del Bloque
200
150
100
50
0
Lo más habitual
40MB - 160KB - 0,5KB 40GB
3,36
% uso disco100
75
50
25
0Ficheros de 1K
Sistema de Ficheros 18
BLibres BloquesDirectorio
Disco 20M y bloques de 1K
MP
MB
• Para que sea eficiente, debe estar entero en MP
Implementación ( Gestión del espacio en disco )• Gestión de bloques libres:
Implentar eficientemente: int pedirBloque() y liberarBloque(int)
Mantenerse en disco como información permanente
0 0 0
1 11 11111
000
11
bloques ocupados
bloques libres
0101101111100011------------
Mapa debitsmount
sync, umount, shutdown
MPSi sólo cabe un bloque en MP,
¿borrar un fichero de 4 bloques?
4..8 accesos a disco
Sistema de Ficheros 19
MP
Implementación ( Gestión del espacio en disco )Disco de 40GB y bloques de 1K => Mapa de 5MB ¿Todo en M.P.?
• Lista encadenada distribuida
LBLibres Directorio
pu
F1
LBLibres Directorio
pu
• Borrar F1 1 acceso a disco (E)
Sin accederal disco
• Pedir bloque libre 1 acceso a disco (L)
Sistema de Ficheros 20
Implementación ( Gestión del espacio en disco )
• Lista encadenada centralizada (Bloques de índices libres)
LBLibres Directorio
FAT
• Sea un disco de 20MB y bloques de 1K 20480 bloques
LBLibres Bloques (libres / ocupados)
40 41 42 204790 39
¡Formatear!41,42,43,44,45, ---------------------,20478,20479
Pedir 3 bloques
Liberar bloque 41
40,41,42,44,45, ---------------------,20478,2047941,42,43
40,41,41,44,45, ---------------------,20478,2047941,42
Sistema de Ficheros 21
MP
4142
511
0
Implementación ( Tamaño de la lista de bloques libres )Con disco de 20MB y bloques de 1K 20480 bloques:
Si ptrBloque son 2B LBLibres = (20439*2)/1024 = 40 bloques
LBLibres Bloques (libres / ocupados)
40 41 42 204790 39
Con un solo
bloque en MP hay
eficiencia
Pidobloque
Liberobloque
80511
500
80511
512
1023
1
411023
4142
511
0512
1023
119968
20479
39
0
411023
119968
20479
39
shutdownPtr 1er bloque libre
1::1020Tamaño disco, ....82B
Con 2 ó 3 bloques en MP sí hay eficiencia
Sistema de Ficheros 22
Implementación ( Fiabilidad )
Fiabilidad: Protección frente a imponderables (Hw / Sw)
Problema
• Bloque erróneo
Tratamiento
• Lista de bloques defectuosos
• Disco inservible • Copias preventivas
Hw
leve
serio
• S.F. IncoherenteSw ÙÐ
þØ dir¶ÐðòÎþõ暥Ħťů�
• Restaurar coherencia
scandisk
fsck
Sistema de Ficheros 23
Implementación ( Fiabilidad “Copias preventivas” )
• Sistemas de volcadosCintas ¡ Lentos y Voluminosos !
• Volcados incrementales
Volcar cambios desde volcado anterior
• Un disco lógico y dos físicos
Datos0
Copia1
Disco 0
UCP
Datos1
Copia0
Disco 1
¿Mejor?
www.exabyte.com
Datos
Disco 0
UCP
Copia
Disco 1
160GB a 12MB/seg 999$
¿ RAID ?
Sistema de Ficheros 24
Implementación ( Fiabilidad “Consistencia SF” )
Mapa |Lista
Nodos
Mapa |Lista
BloquesI-Nodos Bloques De bloques
Libres OcupadosPunteros a bloques
L O = E
L ∩ O = Ø
∩
¿Algoritmo?
00
00
00
00
00
00
0 1 2 3 nBloqueLibreOcupado
• Casos:
01
10
coherente
00
perdido ?/lost+found
02
Repetido libre ? Dejar uno
20
Repetido ocupado
Replicarlo?
1
++
1
++
Sistema de Ficheros 25
Implementación ( Fiabilidad “Consistencia SF” )
De ficheros
modo# enlaces
uidgid
tamaño
T. acceso
T. modificación
T. cambio inodo
# enlaces
16814070
mailgamestestnote
/usr/ast31705938
binmemof.cprog1
/usr/jim
inodo 702 #enlaces
¿Algoritmo?
OK
0 0 0 0 0 00 1 2 3 nNodo
# entradas70
0
• Recorrer SF
1
++
2
++
• Recorrer nodos:#entradas = #enlaces
Sistema de Ficheros 26
Implementación ( Rendimiento: Caché de bloques )
L3 L2
L1I
L1D
UCP1,6 GHzMP
1615
Cachébloques
• Viable LRU
Reciente (MRU) Antiguo (LRU)
?
• Búsqueda rápida
Tabla hash
• Tipos de bloques: nodo-i, ptr, datos
sync + update
Cache transparente W
Sistema de Ficheros 27
Implementación ( Rendimiento: otras mejoras )
• Leer (traer a cache) por adelantado “prefetch”
• Asignar bloques contiguos a ficheros: zona = n bloques
• Ubicación de inodos más distribuida
top related