sistema de ficheros1 horas 1introducciÓn5 2procesos y threads8 3gestiÓn de memoria8...

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


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


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


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


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)


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


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


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?


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

?


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?


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


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


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?


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


Implementación ( Directorios: Ficheros compartidos )

link (“/usr/jim/memo”, “/usr/ast/note”)

/

usrtmp dev

ast jim

mail

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 ?


Implementación ( Directorios: Ficheros compartidos )

link (“/usr/jim/memo”, “/usr/ast/note”)

/

usrtmp dev

ast jim

mail

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]

?


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


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


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)


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


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


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


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 ?


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

++


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


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


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

sistema de ficheros1 horas 1introducciÓn5 2procesos y threads8 3gestiÓn de memoria8...

Documents