Transcript
03/11/2009
Tema 2 SISTEMA DE FICHEROS
SISTEMA DE FICHEROS Almacenamiento permanentes de información. No No están ligados al ciclo de vida de una aplicación particular. están ligados al ciclo de vida de una aplicación particular. Conjunto de información estructurada de forma lógica. Nombres lógicos y estructurados. Abstraen los dispositivos de almacenamiento físico. Se acceden a través de llamadas al sistema operativo o de bibliotecas de utilidades.
1
03/11/2009
SISTEMA DE FICHEROS Ficheros Directorios Implementación del del sistema sistema de ficheros de ficheros Ejemplos de sistema de sistema de ficheros de ficheros El El servidor servidor de de archivo archivo Aumento de prestaciones de prestaciones Servicios S i i del d l sistema del sistema it d ficheros de ficheros de fi h
Concepto de archivo Un espacio lógico de direcciones contiguas usado para
almacenar datos Tipos de archivos: p Datos: numéricos carácter binarios Programas: código fuente ódi f t archivos objetos (imagen de carga) Documentos
2
03/11/2009
Nombres de archivo. archivo. Extensiones típicas
Estructuras de archivo
3
03/11/2009
Tipos de archivo
(a) Un (a) Un fichero fichero executable (b) Un executable (b) Un archivo archivo
Estructura de archivo ejecutable LINUX Número mágico Número de sec c iones
Cabecera primaria
Tamaño segmento texto Tam año segmento datos
Cabecera de sección 1
Tipo de sección, tamaño de la sección dirección virtual
Cabecera de sección n
Tipo de sección, tamaño de la sección dirección virtual
Sección 1
Código
Sección 2
Datos con valor inicial
Sección n
Datos con valor inicial
Tam año datos sin valor inic ial Tam año tabla de símbolos Valor inicial de registros Direc c ión inic ial
... Opciones
Información de carga Tabla de símbolos
Otra información
4
03/11/2009
Atributos del archivo Nombre: la única información en formato legible por una
persona. Identificación única del archivo y del usuario: y descriptor interno p
del archivo, dueño y grupo del archivo Tipo de archivo: Tipo de archivo: necesario en sistemas que proporciona necesario en sistemas que proporciona
distintos formatos de archivos. Tamaño del archivo: Tamaño del archivo: número de bytes en el archivo, máximo número de bytes en el archivo, máximo
tamaño posible, etc. Protección: Protección: control de accesos y de las operaciones sobre control de accesos y de las operaciones sobre
archivos hi Información temporal: de creación, de acceso, de modificación,
etc. Información de control: archivo oculto, de sistema, normal o Información de control: archivo oculto, de sistema, normal o
directorio, etc.
Operaciones sobre archivos File es un tipo abstracto de datos Create, Delete Write, Read Write Read Open, Close Append, Truncate Seek Rename Set atributos Get atributos Open(Fi) – busca la entrada Fi en el directorio y mueve el
contenido de la entrada desde disco a memoria. Close (Fi) – busca la entrada Fi en el directorio y mueve el
contenido de la entrada desde memoria a disco.
5
03/11/2009
Métodos de acceso I Acceso secuencial: lectura de los bytes del archivo en orden ascendente, empezando por el principio. read next next, , write write next, next, reset reset, no , no read read after last write write, … , … rewind rewind: ir al principio para buscar hacia delante : ir al principio para buscar hacia delante Lectura Lectura ‐‐> posición = posición + datos leídos Dispositivos de cinta Acceso Directo: Acceso Directo: read n, n, write write n, n, goto goto n, n, rewrite rewrite n, n, read read next next, , write write next, … next, … n = número de bloque relativo al origen Dispositivos: discos magnéticos
Acceso secuencial
6
03/11/2009
Protección • Control del dueño Control del dueño//creador del del fichero fichero:: – Qué se se puede puede hacer – Por quíen • Tipos de acesos de acesos – Read – Write – Execute E – Append – Delete – List
Listas de accesos y grupos • •
Modos of aceso of aceso: : read read, , write write, , execute execute Tres clases de usuarios de usuarios RWX 1 1 1 111 RWX b) group access b) group access 6 1 1 0 RWX c) public access c) public access 1 0 0 1 El gestor El gestor cea un un ungrupo ungrupo , por , por ejemplo G, y , y añadir añadir algunos usuarios al grupo.. grupo Definir un un tipo tipo de acceso de acceso para un fichero un fichero particular, particular, por por ejemplo game ame, , o o subdirectorio,. subdirectorio ,. a) owner access owner access
• •
owner chmod
group 761
7
public game
7
03/11/2009
Lista de control de accesos en Windows XP
Bloque de control de fichero típico
8
03/11/2009
Ejemplo. Copia un archivo en otro I #include #include #include #include
#define BUFSIZE
512
main(int argc, char **argv) { int fd_ent, fd_sal; char buffer[BUFSIZE]; int n_read; /* abre el archivo de entrada */ fd_ent = open(argv[1], O_RDONLY); if (fd_ent < 0) perror("open"); exit(-1); }
{
/* crea el archivo de salida */ fd_sal = creat(argv[2], 0644); if (fd_sal < 0) { close(fd_ent); perror("open"); exit(-1); }
Ejemplo. Copia un archivo en otro II
/* bucle de lectura del archivo de entrada */ while ((n_read = read(fd_ent, buffer, BUFSIZE)) > 0) /* escribir el buffer al archivo de salida */ if (write(fd_sal, buffer, n_read) < n_read) { perror("write2); close(fd_ent); close(fd_sal); exit(-1); } } if (n_read < 0) { perror("read"); close(fd_ent); close(fd_sal); exit(-1); } close(fd_ent); close(fd_sal); exit(0); }
{
9
03/11/2009
SISTEMA DE FICHEROS Ficheros Directorios Implementación del del sistema sistema de ficheros de ficheros Ejemplos de sistema de sistema de ficheros de ficheros El El servidor servidor de de archivo archivo Aumento de prestaciones de prestaciones Servicios del del sistema sistema de ficheros de ficheros
Estructura de directorio Una colección de nodos de nodos con información con información sobre los los ficheros ficheros
Directorios
Ficheros
F1 F 1
F2 F 2
F 3
F4 F 4 F n
Ambos residen en disco
10
03/11/2009
Un único nivel de directorios I Un directorio Un directorio para todos los usuarios
Problema de nombres Problema de grupos
Un único nivel de directorios II Un directorio Un directorio para cada usuario
Path de nombres Se puede tener el mismo nombre de archivo para diferentes usuarios. Búsqueda eficiente No tiene capacidad de agrupación
11
03/11/2009
Estructura de directorios en árbol I
Estructura de directorios en árbol II Búsqueda eficiente Capacidad p de agrupación g p Directorio actual (working directory)
cd /spell/mail/ /spell/mail/prog prog
Se denota con “. “.”
Directorios especiales: •
Directorio “..”:: directorio padre de “.”
•
Directorio HOME HOME:: el directorio base del usuario
12
03/11/2009
Estructura de directorios en árbol III nombre absoluto o o relativo relativo El El nuevo nuevo fichero se se crea crea en el en el directorio directorio actual Borrar un un fichero un fichero
rm El El nuevo nuevo subdirectorio se se crea crea en el en el directorio directorio actual
mkdir Ejemplo: Ejemplo : si si el el directorio directorio actual es actual es /mail mkdir count mail prog
copy
prt exp count
Para borrar “mail” borrar el subárbol que cuelga de “mail”
Comparticicón de archivos I
Sistema de ficheros de ficheros que contienen un fichero un fichero compartido 26
13
03/11/2009
Comparticicón de archivos II
(a) Situación anterior al enlace (b) Depués (b) Depués de de crear crear el enlace (c) Después (c) Después de de que que el el dueño dueño original borra original borra el fichero el fichero 27
Enlaces Dos o más nombres hacen referencia al mismo archivo. Dos tipos: Enlace físico El archivo sólo se elimina cuando se borran
todos los enlaces Sólo se permiten enlazar ficheros del mismo
volumen o partición Enlace simbólico El archivo hi se elimina li i cuando d se borra b ell enlace l
físico. Si permanece el enlace simbólico provoca errores al tratar de accederlo. Se puede hacer entre archivos de diferentes
sistema de archivos
14
03/11/2009
Enlace físico /
usr
/
prog.c
pepe
prueba.txt
prog.c
datos.txt pepe
. ..
23 100 28 400
datos.txt prog.c
juan
pepe
juan
. ..
user
lib
juan
pepe datos.txt
usr
user
lib
prueba.txt
. ..
80 100 60
prueba.txt
datos2.txt
juan
datos.txt prog.c
. ..
23 100 28 400
prueba.txt datos2.txt
80 100 60 28
nodo-i 28 enlaces = 2 descripción del fichero
ln /user/pepe/datos.txt /user/juan/datos2.txt
Enlace simbólico /
usr
/
user
lib
pepe datos.txt
prog.c
pepe
. ..
datos.txt prog.c
usr
juan
pepe
prueba.txt
datos.txt
juan 23 100 28 400
. ..
prueba.txt
user
lib
nodo-i 28 80 100 60
Enlaces = 1 descripción del fichero
prog.c
pepe
. ..
datos.txt prog.c
juan prueba.txt
datos2.txt
juan 23 100 28 400
. ..
nodo-i 130 80 100
prueba.txt 60 datos2.txt 130
enlaces = 1 /user/pepe/ datos.txt
ln -s /user/pepe/datos.txt /user/juan/datos2.txt
15
03/11/2009
Grafo acíclico de directorios I Directorios y ficheros y ficheros compartidos
Grafo acíclico de directorios II • link: Un archivo con varios nombres link: Un archivo con varios nombres ‐‐> control de enlaces – un único archivo con contador de enlaces en descriptor (e. Físicos) – archivos nuevos con el nombre destino dentro (e. simbólicos) • Borrado de enlaces: – decrementar contador; si 0 borrar archivo • Problema grave: existencia de bucles en el árbol. Soluciones: – Permitir sólo enlaces a archivos, no subdirectorios – Algoritmo de búsqueda de bucle cuando se hace un enlace Algoritmo de búsqueda de bucle cuando se hace un enlace • Limitación de implementación en UNIX: sólo enlaces físicos dentro del mismo sistema de archivos.
16
03/11/2009
Grafo general de directorios I
Grafo general de directorios II Cómo evitar ciclos ciclos? ?
Permitiendo únicamente enlaces a las hojas
Cada vez que se crea un nuevo link se mira si crea ciclo o no.
Garbage collection
17
03/11/2009
Jerarquía de directorios Árbol de directorios Por Por dispositivo lógico en Windows (c: Por dispositivo lógico en Windows (c:\ dispositivo lógico en Windows (c: (c:\\users users\\miguel miguel\\claves, j: claves, claves, j:\ j:\pepe j:\ pepe\\tmp tmp)) Único para todo el sistema en UNIX (/users Único para todo el sistema en UNIX (/users/miguel/claves, /pepe/ /miguel/claves, /pepe/tmp tmp,, ...) Ventajas: imagen única del sistema y ocultan el tipo de dispositivo Desventajas: ‐ Complican la traducción de nombres, problemas para enlaces físicos entre archivos ‐ Hacen falta servicios para construir la jerarquía: mount /dev/ dev/hda /users umount /users
Montado de sistemas de archivos o particiones • Oculta el nombre del dispositivo físico o partición Volumen raiz (/dev/hd0)
Volumen sin montar (/dev/hd1) /
/
/ mount
/lib
/bin
Volumen montado
/usr
/d 1
/d 2
/d3/f1
/d3
/dev/hd1
/usr /lib
/bin
/usr
/d3/f2
/usr/d1
• En MS En MS‐‐DOS c: DOS c:\\tmp\ tmp\datos.txt
/usr/d 3/f1
/usr/d3
/usr/d 3/f2
18
03/11/2009
Operaciones sobre directorios 1. 2 2. 3. 4. 5. 6. 7 7. 8.
Delete O Opendir di Closedir Create Readdir Rename Link Unlink
Ejemplo:: explorador de Windows Ejemplo
19
03/11/2009
Un ejemplo de listado de directorio UNIX
Bloque de control de fichero descriptor o i-nodo
20
03/11/2009
Ejemplo. Lista un directorio I #include #include #include #define MAX_BUF
256
void id main(int i (i t argc, char h ** **argv) ) { DIR *dirp; struct dirent *dp; char buf[MAX_BUF]; /* imrpime el directorio actual */ getcwd(buf, MAX_BUF); printf("Directorio actual: %s\n", buf); /* abre el directorio pasado como argumento */ dirp = opendir(argv[1]); if (dirp ( p == NULL) ) { fprintf(stderr,"No puedo abrir %s\n", argv[1]); } else { /* lee entrada a entrada */ while ( (dp = readdir(dirp)) != NULL) printf("%s\n", dp->d_name); closedir(dirp); } exit(0); }
SISTEMA DE FICHEROS Ficheros Directorios Implementación del del sistema sistema de ficheros de ficheros Ejemplos de sistema de sistema de ficheros de ficheros El El servidor servidor de de archivo archivo Aumento de prestaciones de prestaciones p Servicios del del sistema sistema de ficheros de ficheros
21
03/11/2009
Correspondencia bloquesbloques-archivos I Se refiere a la forma Se refiere a la forma en en que que los bloques los bloques se organizan se organizan en ficheros.. ficheros Continua Lista Indexada
Correspondencia bloquesbloques-archivos II 1.
Asignación de bloques contiguos. contiguos. – Sencillo de implementar y el rendimiento de la E/S es muy bueno. bueno. – Si no se conoce el tamaño total del archivo cuando se crea, puede ser necesario i buscar b un nuevo hueco h d bloques de bl consecutivos ti cada d vez que el archivo crece. crece. – Fragmentación externa Fragmentación externa ‐‐> compactar el disco.
2.
Asignación de bloques discontinuos. discontinuos. – Se asigna al archivo el primer bloque que se encuentra libre libre.. – No hay fragmentación externa del disco ni búsqueda de huecos huecos.. – Los archivos pueden crecer mientras exista espacio en el disco disco.. – Complica la implementación de la imagen de archivo ‐> mapa de bloques del archivo archivo..
22
03/11/2009
Correspondencia continua I
Correspondencia continua II Acceso muy rápido, poco movimiento del cabezal de disco Buscar un espacio libre suficiente consecutivo •
First fit
•
Best fit
•
Worst fit
Fragmentación externa: •
El espacio libre se distribuye en espacios pequeños El espacio libre se distribuye en espacios pequeños dificiles dificiles de aprovechar
•
Hay que compactar la información
•
Que pasa si el fichero crece o no hay un espacio suficiente?
Correspondencia de de lógico lógico a físico
Q
LA/512 R Bloque al al que que se accede se accede = = Q+ Q+ dirección dirección de comienzo de comienzo Desplazamiento en el bloque en el bloque = R
23
03/11/2009
Correspondencia enlazada I Cada fichero es una lista de de bloques bloques...
block =
pointer
Correspondencia enlazada II
24
03/11/2009
Correspondencia enlazada III Simple – necesita únicamente la dirección de comienzo Gestión de espacio libre - no gasta espacio No N aceso aleatorio l t i Corrrespondencia de lógico a físico
Q LA/512‐1 R
Bloque accedido = = el Q el Q‐‐ésimo en la en la lista lista enlazada Desplazamiento en el bloque en el bloque = R + 1 = R + 1
Correspondencia enlazada III. Tabla
File‐‐allocation table (FAT) File allocation table (FAT) –– en MS en MS‐‐DOS y OS/2
25
03/11/2009
Correspondencia indexada I • Cada archivo tiene sus bloques de índice que incluyen apuntadores a los bloques de disco del archivo archivo.. – El orden lógico se consigue mediante la inserción de los apuntadores en orden creciente, a partir del primero, en los bloques de índices índices.. – Ventaja Ventaja:: basta con traer a memoria el bloque de índices donde está el apuntador a los datos para tener acceso al bloque de datos datos.. Si un apuntador de bloque ocupa 4 bytes y el bloque es de 4 Kbytes, Kbytes, con un único acceso a disco tendremos 1024 apuntadores a bloques del archivo.. archivo – Problema Problema:: el espacio extra necesario para los bloques de índices índices.. • Ese problema, fue resuelto en UNIX BSD combinando un sistema de índices puros con un sistema de índices multinivel, q p que es q que se usa actualmente en UNIX y LINUX. LINUX. – Permite almacenar archivos pequeños sin necesitar bloques de índices índices.. – Permite accesos aleatorios a archivos muy grandes con un máximo de 3 accesos a bloques de índices índices..
Correspondencia indexada II Todos los punteros los punteros están en un bloque en un bloque índice. índice. Vista local Vista local..
index table
26
03/11/2009
Correspondencia indexada III
Correspondencia indexada V Necesita una tabla de índices Acceso aleatorio Acceso A di á i sin dinámico i fragmentación f t ió externa t Correspondencia lógica a física en un fichero de
tamaño máximo 256K words y tamaño de bloque de 512 words. Se necesita únicamente 1 bloque para la tabla de índices Q LA/512 R
Q = desplazamiento Q = desplazamiento en la tabla en la tabla de índices de índices R = desplazamiento en el bloque R = d en el bloque
27
03/11/2009
Tabla de índices enlaza Corrrespondencia de lógico a físico en un fichero de tamaño ilimitado
(tamaño del bloque 512 words). Esquema enlazado – Bloques enlazados en la tabla de índices (no
existe límite en el tamaño tamaño)) Q1 LA/(512*511)
Q1 = bloque Q1 = bloque de la de la tabla tabla de índices de índices R1 = se utiliza como sigue: R1 = se utiliza sigue:
R1 Q2 R1/512 R2
Q2 = desplazamiento en el bloque Q2 = desplazamiento en el bloque de la de la tabla tabla de índices de índices R2 = desplazamiento R2 = desplazamiento en el bloque en el bloque de de fichero fichero
Correspondencia indexada en 2 niveles
outer‐index
index table
file
28
03/11/2009
Correspondencia indexada en 2 niveles Dos niveles de índice (tamaño máximo del fichero 512*512*512
words). Q1 LA/(512*512) R1
Q1 = desplazamiento en el índice Q1 = desplazamiento en el índice externo R1 = se R1 = se utiliza utiliza como sigue: sigue: Q2 R1/512 R2
Q2 = desplazamiento en el bloque Q2 = desplazamiento en el bloque de la de la tabla tabla de índices de índices R2 = desplazamiento R2 = desplazamiento en el bloque en el bloque de de fichero fichero
Esquema combindo: combindo: UNIX (4K bytes/ bytes/bloque bloque))
29
03/11/2009
Manejo de espacio libre I
Para ficheros Para ficheros de tamaño de tamaño 2KBytes
Manejo de espacio libre II • Lista enlazada de bloques de disco con # de bloques libres libres.. • Mapas de bits, bits o vectores de bits bits:: un bit por recurso existente (descriptor de archivo,, bloque o agrupación archivo agrupación)). Si el recurso está libre, libre, el valor del bit asociado al mismo es 1, si está ocupado es 0. – Fácil de implementar y sencillo de usar usar.. Eficiente si el dispositivo no está muy lleno o muy fragmentado. fragmentado. • Listas de recursos libres libres:: mantener enlazados en una lista todos los recursos disponibles (bloques o descriptores de archivos) manteniendo un apuntador al primer elemento de la lista lista.. – Este método no es eficiente, excepto para dispositivos muy llenos y fragmentados – Uso de agrupaciones agrupaciones..
30
03/11/2009
Manejo de espacio libre III
Manejo de espacio libre IV Bit map (n Bit map ( n blocks) 0 1
2
n‐1
bit[i] =
… 1 block[i] free 0 block[i] occupied
Cálculo del primer bloque libre libre::
(número de bits por bits por palabra) * palabra) * (número de palabras con valor 0) + )+ desplazamiento hasta el primer bit a 1
31
03/11/2009
Manejo de espacio libre V
Manejo de espacio libre VI
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Bloques libres
7
Bloques libres
7,1
11
14
16
11,1 14,1
17 16,3
18
(A) (B)
32
03/11/2009
Manejo de espacio libre VII
Manejo de espacio libre VIII Se Se necesita necesita espacio para el b el bit map
Necesita mucho espacio mucho espacio. . Ejemplo Ejemplo:: tamaño bloque = 2 = 212 bytes tamaño disco = 230 bytes (1 gigabyte) n = 230/212 = 218 bits (or 32K bytes)
•
MS‐‐DOS: MS DOS: Agrupaciones Agrupaciones de bloques de bloques
•
Fácil obtener ficheros continuos
Lista de bloques libres
No necesita No necesita mucho espacio mucho espacio
No es No es fácil obtener fincheros continuos
33
03/11/2009
Bloques y agrupaciones • Bloque: agrupación lógica de sectores de disco y es la unidad Bloque: agrupación lógica de sectores de disco y es la unidad de transferencia mínima que usa el sistema de archivos. . de transferencia mínima que usa el sistema de archivos – Optimizar la eficiencia de la entrada/salida de los Optimizar la eficiencia de la entrada/salida de los dispositivos secundarios de almacenamiento. – Todos los sistemas operativos proporcionan un tamaño de bloque por defecto. – Los usuarios pueden definir el tamaño de bloque a usar dentro de un sistema de archivos mediante el mandato mkfs. . mkfs • Agrupación ( Agrupación (cluster cluster): ): conjunto de bloques que se gestionan conjunto de bloques que se gestionan como una unidad lógica de gestión del almacenamiento. como una unidad lógica de gestión del almacenamiento. – El problema que introducen las agrupaciones, y los bloques grandes, es la existencia de fragmentación interna.
Etructura de directorios Lista lineal de de nombres nombres con con punteros punteros a los a los bloques bloques de
datos.. datos
Simple i l de d programar de programar
Consume tiempo Consume tiempo de ejecución
Tabla Hash Hash –– lista lineal con búsqueda hash.
Decrementa el tiempo el tiempo de de búsqueda búsqueda de directorios
Colisiones – cuando dos dos nombres nombres dan el el mismo mismo Hash
Tamaño fijo
34
03/11/2009
Implementación de directorios
MS_DOS/Windows MS DOS/Windows
UNIX
Implementación de directorios II
•Compactación •Caracteres de relleno
•Administración de heap
35
03/11/2009
Sistemas de archivos y particiones I • Previamente a la instalación del sistema de archivos es necesario dividir físicamente, o lógicamente, los discos en particiones o volúmenes. • Una partición es una porción de un disco a la que se la dota de una identidad propia y que puede ser manipulada por el sistema operativo como una entidad lógica independiente. • Una vez creadas las particiones, el sistema operativo debe crear las estructuras de los sistemas de archivos dentro de esas particiones. • Para ello se proporcionan mandatos como format o mkfs al usuario. – #mkswap –c /dev/hda2 20800 – #mkfs ‐c /dev/hda3 –b 8196 123100
Sistemas de archivos y particiones II • Relación Relación sistema de archivos sistema de archivos‐‐dispositivo: – Típico: 1 dispositivo N Típico: 1 dispositivo N ssistemas de archivos (particiones) – Grandes archivos: N dispositivos 1 Grandes archivos: N dispositivos 1 sistema de archivos sistema de archivos
• Típicamente cada dispositivo se divide en una o más particiones (en cada partición sistema de archivos partición sistema de archivos) ) • La tabla de particiones indica el principio, el tamaño y el tipo de cada partición. • Descripción de Descripción de ssistemas de archivos: – El sector de arranque en MS El sector de arranque en MS‐‐DOS – El superbloque en UNIX
• Volumen: Volumen: conjunto coherente de metainformación y datos. conjunto coherente de metainformación y datos.
36
03/11/2009
Sistemas de archivos y particiones II
Partición 4
Partición 5
Partición 2 Partición 3
Organizaciones típicas de SF
37
03/11/2009
Ejemplo de volumen o partición
Consistencia del sistema de archivos I Verificar que la estructura lógica del sistema de archivos es correcta correcta:: 1. El contenido del superbloque responde a las características del sistema it d archivos de archivos. hi . 2. Los mapas de bits de nodos os mapas de bits de nodos‐‐i se corresponden con los nodos i se corresponden con los nodos‐‐i ocupados en el sistema de archivos. 3. Los mapas de bits de bloques se corresponden con los bloques asignados a archivos. 4. Ningún bloque está asignado a más de un archivo. 5. Un mismo nodo‐ n mismo nodo‐i no está asignado a más de un directorio. En UNIX y LINUX: fsck En UNIX y LINUX: fsck fsck /dev/ dev/dsk/c0t0d3s1 dsk/c0t0d3s1 Comprueba el dispositivo físico c0t0d3s1
38
03/11/2009
Consistencia del sistema de archivos II • Consistencia sobre archivos archivos:: – Contador de enlaces > contador real – Contador de enlaces < contador real – Número de nodo nodo‐‐i > Número total de nodos nodos‐‐i – Archivos con bits de protección 0007 – Archivos con privilegios en directorios de usuario
Consistencia del sistema de archivos III
Estados del sitema del sitema de archivo de archivo Recuento de bloques de bloques:: • • •
Se leen todos los I Se Se leen los I‐nodos y se los I‐ y se cuentan los y se cuentan los bloques ocupados los bloques Se examina Se examina el el mapa mapa de bits o la de bits o la lista lista libre para contar bloques libres SE cmparan SE cmparan las dos dos tablas tablas:: (a) Consistente (a) Consistente (b) Bloques (b) Bloques perdidos perdidos: se : se recupera recupera ‐> se agrega > se agrega a la a la lista lista libre (c) Bloque (c) Bloque duplicado en la lista en la lista libre: se libre: se reconstruye reconstruye la lista la lista libre (d) Bloque (d) Bloque de de datos datos duplicado: se duplicado: se realiza realiza una copia del bloque del bloque y se aigna y se aigna a uno a uno de los dos archivos de los dos archivos que tienen el el bloque bloque duplicado ‐> se > se informa informa del ERROR del ERROR
Recuento de I‐ de I‐nodos nodos:: • •
Se inspecciona Se inspecciona el árbol el árbol de directoríos de directoríos y se y se cuentan cuentan los I‐ los I‐nodos …
78
39
03/11/2009
Estructuras del SF en MP I •
Tabla de nodos nodos‐‐i: almacena en memoria la información del nodo nodo‐‐i existente en el disco y otra que se usa dinámicamente y sólo tiene sentido cuando el archivo está abierto abierto.. – Problema: roblema: si sólo hay un campo de apuntador apuntador,, cada operación de un proceso afectaría f t í a todos t d los l demás d á. demás. – Posible solución solución:: incluir la información relativa al archivo dentro del bloque de descripción del proceso (BCP). (BCP).
•
Tabla de archivos abiertos (tdaa) tdaa) por un proceso, dentro del BCP, con sus descriptores temporales y el valor del apuntador de posición del archivo para ese proceso proceso.. – El tamaño de esta tabla define el máximo número de archivos que cada proceso puede tener abierto de forma simultánea. simultánea. – El descriptor de archivo fd indica el lugar de tabla tabla.. La tdaa se rellena de forma ordenada ordenada,, de forma que siempre se ocupa la primera posición libre de la tabla. tabla. – En los sistemas UNIX cada proceso tiene tres descriptores de archivos abiertos por defecto: defecto: entrada estándar, fd = 0, salida estándar, fd = 1, error estándar, fd = 2.
Estructuras del SF en MP III • Tabla intermedia nodo‐ nodo‐i‐posición posición:: entre la tabla de archivos abiertos del BCP y la tabla de nodos nodos‐‐I. Dicha tabla incluye, incluye, entre otras cosas cosas:: – La entrada del nodo nodo‐‐i del archivo abierto en la tabla de nodos nodos‐‐i. – El apuntador de posición correspondiente al proceso, o procesos, que usan el archivo durante esa sesión. sesión. – El modo de apertura del archivo
40
03/11/2009
Estructuras del SF en MP IV Tabla de archivos Tabla de archivos abiertos. P1 abiertos. P2 fd
0 1 2 3 4
23 4563 56 3 678
fd
0 1 2 3 4
Tabla de archivos abiertos. P3
230 563 98 3 247
fd
0 1 2 3 4
2300 53 4 465 326
Nodo-i Posición 98 98 Tabla de nodos-i 98
456 2348 Tabla intermedia de nodos-i y posiciones
SISTEMA DE FICHEROS Ficheros Directorios Implementación del del sistema sistema de ficheros de ficheros Ejemplos de sistema de sistema de ficheros de ficheros El El servidor servidor de de archivo archivo Aumento de prestaciones de prestaciones Servicios del del sistema sistema de ficheros de ficheros
41
03/11/2009
Ejemplo de sistemas de archivos MS‐DOS Boot
Dos copias p Directorio de la FAT Raíz
Datos yy Directorios
UNIX Super Mapas Boot Bloque de bits
nodos‐i
Windows‐NT Super Mapas Descriptores físicos Boot Bloque de bits de archivos
Datos y Directorios
Datos y Directorios
Formatos de entrada de directorio CPM MS‐‐DOS MS MS‐DOS Bytes MS‐ extendida:: extendida MFT Windows 98
42
03/11/2009
El sistema de ficheros de MS MS--DOS I FAT Directorio Raíz Nombre pep_dir •
Información en el directorio – 32 bytes por entrada – Nombre + Extensión ( 8.3 ) – Primer bloque de datos – Atributos ( Subdirectory, System, Hidden, Read‐only, ... ) – Tamaño
fiche1.txt
En grafo En grafo – No hay hard links – Pueden haber soft links
•
FAT de: – 12 bits 4K agrupaciones – 16 bits 64K agrupaciones
KB Agrup Agrup. 5 27 12
f 27
45 45
Directorio pep_dir Nombre carta1.wp prue.zip
•
Atrib Atrib. dir
Atrib. R
KB Agrup. 24
74
16
91
58
51 58 74 75 75 76 76 91 92
El sistema de ficheros de MS MS--DOS II
• Particiones máximas para diferentes tamaños de bloque de bloque 86
43
03/11/2009
El sistema de ficheros Windows 98 Bytes
Checksum Una entrada para (parte de) un nombre de fichero de fichero largo en largo en Windows 98 Windows 98
63
Ejemplo de archivo de archivo con nombre con nombre largo en Windows 98
Sistema de ficheros UNIX V7 I •Superbloque •Formato Formato del SF ( tamaño de bloque, del SF ( tamaño de bloque #inodos, #bloques de datos,... ) •Lista de bloques libres •Lista de inodos libres •Asignación indexada •Almacenada en los inodos •En grafo •hard links y soft links
Entrada de directorio de directorio UNIX V7
88
44
03/11/2009
Sistema de ficheros UNIX V7 II Inodo •tamaño •tipo ( directory, file, link, pipe, dispositivo de caracteres, dispositivo de bloques) •protecciones •tiempos de acceso, modificación, creación •#links •Indices a los bloques de datos •10 indices directos •1 indice indirecto •1 indice indirecto doble •1 indice triple indirecto
Tamaño máximo del archivo: 10Sb+(Sb/4)Sb +(Sb/4)2Sb +(Sb/4)3Sb Sb el tamaño del bloque y direcciones de bloques de 4 bytes.
Un ii‐nodo UNIX Un
89
Sistema de ficheros UNIX V7 III
Pasos para acceder a a //usr usr//ast ast//mbox
45
03/11/2009
SISTEMA DE FICHEROS Ficheros Directorios Implementación del del sistema sistema de ficheros de ficheros Ejemplos de sistema de sistema de ficheros de ficheros El El servidor servidor de de archivo archivo Aumento A t de d prestaciones de prestaciones t i Servicios del del sistema sistema de ficheros de ficheros
Servidor de archivos • Para proporcionar un acceso eficiente y sencillo a los dispositivos de almacenamiento, todos los sistemas operativos tienen un servidor de archivos que permite almacenar buscar y leer datos fácilmente almacenar, buscar y leer datos fácilmente. • Dicho servidor de archivos tiene dos tipos de problemas de diseño muy distintos entre sí sí:: – Definir la visión de usuario del sistema de ficheros ficheros,, incluyendo servicios de archivos, archivos, directorios, directorios, sistemas de archivos,, etc. archivos etc. – Definir los algoritmos y estructuras de datos a utilizar para hacer corresponder la visión del usuario con el sistema físico de almacenamiento secundario secundario..
46
03/11/2009
Estructura del servidor de archivos Proceso de Usuario 1
Proceso de Usuario 2
Proceso de Usuario 3
Proceso de Usuario n
...
Nivel de usuario Nivel de sistema
Sistema de Archivos Virtual Módulo de Organización de Archivos ext2
msdos
Servidor de Bloques
ffs
...
proc
Cache de Bloques
Manejadores de Dispositivo
...
Sistema de de ficheros ficheros virtual • Un sistema Un sistema de ficheros de ficheros virtual (VFS) virtual (VFS) proporciona proporciona una implementación orientada a objetos a objetos del del sistema sistema de ficheros de ficheros.. • VFS permite VFS permite que el el mismo mismo interface de interface de llamadas llamadas al sistema al sistema (API) se utilize en distintos utilize en distintos tipos de sistemas de sistemas de ficheros de ficheros • El API es El API es para el interface VFS, mucho más el interface VFS, mucho más que cualquier tipo específico de SF • Nodo virtual: estructura de información que incluye las características mínimas comunes a todos los sistemas de archivos subyacentes.
47
03/11/2009
Esquema de s de sistema de ficheros de ficheros virtual
Esquema de sistema de sistema de ficheros de ficheros virtual II
48
03/11/2009
Estructura de un nodo virtual de UNIX nodo-v Información del archivo virtual Direcciones de las operaciones virtuales Dirección del nodo-i específico
nodo-i
Direcciones de las operaciones específicas de SA
Tabla de funciones del SA
Niveles del sistema de archivo
Sistema de ficheros virtual Módulo de organización de ficheros Gestión de bloques Manejador de dispositivo
49
03/11/2009
Módulo de organización de archivos •
Proporciona el modelo de archivo del sistema operativo y los servicios de archivos.. archivos
•
Relaciona la imagen lógica del archivo con su imagen física física,, proporcionando algoritmos para trasladar direcciones lógicas de bloques a sus correspondientes direcciones físicas físicas..
•
Gestiona el espacio de los sistemas de archivos archivos,, la asignación de bloques a archivos y el manejo de los descriptores de archivo (nodos‐ nodos‐i de UNIX o registros de Windows NT) NT)..
•
Un módulo de este estilo por cada tipo de archivo soportado (UNIX, AFS, Windows NT, MS MS‐‐DOS, EFS, MINIX, etc etc..).
•
Las llamadas de gestión de archivos y de directorios particulares de cada sistema de archivos se resuelven en el módulo de organización de archivos archivos.. Para ello ello,, se usa la información existente en el nodo nodo‐‐i del archivo afectado por las operaciones. operaciones.
Servidor de bloques • Se encarga de emitir los mandatos genéricos para leer y escribir bloques a los manejadores de dispositivo dispositivo.. • La L E/S de d bloques bl d archivo, de hi y sus posibles ibl optimizaciones, ti i i se lleva ll a cabo en este nivel del servidor de archivos archivos.. • Las operaciones se traducen a llamadas de los manejadores de cada tipo de dispositivo específico y se pasan al nivel inferior del sistema de archivos.. archivos • Esta capa oculta los distintos tipos de dispositivos, usando nombres lógicos para los mismos. mismos. Por ejemplo, /dev dev/hda /hda3 3 será un dispositivo de tipo hard disk (hd hd), ), cuyo nombre principal es a y en el cual se trabaja sobre su partición 3. • Los mecanismos de optimización de la E/S, como la cache de bloques, se incluye en este nivel. nivel.
50
03/11/2009
Descomposición en operaciones de bloques • Archivos con estructura de bytes – Escritura leer
Fichero (tira de bytes)
Bloques
Manejadores de dispositivos • Un manejador por cada dispositivo dispositivo,, o clase de dispositivo dispositivo,, del sistema sistema.. • Su función principal es recibir ordenes de E/S de alto nivel, nivel, tal como move to block 234 move_to_block 234,, y traducirlas al formato que entiende el controlador del dispositivo, dispositivo, que es dependiente de su hardware hardware.. • Habitualmente, Habitualmente, cada dispositivo tiene una cola de peticiones pendientes, pendientes, de forma que un manejador puede atender simultáneamente a varios dispositivos del mismo tipo tipo.. • Una de las principales funciones de los manejadores de dispositivos es recibir las peticiones de entrada/salida y colocarlas en el lugar adecuado de la cola de peticiones del dispositivo afectado. afectado. – La política de inserción en cada cola puede ser diferente, diferente, dependiendo del tipo de dispositivo o de la prioridad de los dispositivos.. Para un disco, por ejemplo dispositivos ejemplo,, se suele usar la política CSCAN.. CSCAN
51
03/11/2009
Flujo de datos en el S. de A A.. read (fd, buffer, tamaño) buffer
Usuario
tamaño archivo lógic o (VFS) archivo lógic o (FFS)
3
4
5
6
bloques del archivo
Bloques lógic os (Servidor de bloques)
1340
1756
840
8322
bloques del dispositivo
1340 Manejador de disc o y dispositivo
1756 bloques del disco
840 8322
SISTEMA DE FICHEROS Ficheros Directorios Implementación del del sistema sistema de ficheros de ficheros Ejemplos de sistema de sistema de ficheros de ficheros El El servidor servidor de de archivo archivo Aumento de prestaciones de prestaciones Sistemas de almacenamiento de almacenamiento masivo
52
03/11/2009
Eficiencia y p y performance • Eficienciencia depende de: – Ubicación en disco y algoritmos en disco y y algoritmos g de directorios de directorios – Tipo de datos de datos en las en las entradas de fichero de fichero de los de los directorios directorios • Performance depende Performance depende de: – Mejoras de performance de performance como como discos virtuales discos virtuales y discos RAM – Caché de disco de disco –– sección separa de memoria de memoria principal principal para para bloques usados frecuentemente – Las Las técnicas free Las técnicas free‐‐behind behind y read behind y read‐‐ahead ahead – para optimizar el ahead – el acceso el acceso secuencial
Incremento de prestaciones. prestaciones. Performance • Basados en el uso de almacenamiento intermedio de datos de entrada/salida en memoria principal. principal. Estos mecanismos son de dos tipos tipos:: – Discos RAM, RAM, cuyos datos están almacenados sólo en memoria memoria.. • Aceptan todas las operaciones de cualquier otro sistema de archivos y son gestionados por el usuario. usuario. • Pseudodispositivos para almacenamiento temporal o para operaciones auxiliares del sistema operativo operativo.. Su contenido es volátil.. volátil – Cache de disco disco,, almacena datos en MP para optimizar accesos posteriores.. posteriores • Se basan basan en la existencia de proximidad espacial y temporal en las referencias a los datos de entrada/salida entrada/salida.. • Dos caches importantes dentro del servidor de archivos archivos:: cache de nombres y cache de bloques bloques..
53
03/11/2009
Cache de bloques I • Acceso a disco mucho más lento que el acceso a memoria
• Fundamento: Fundamento: – Proximidad espacial – Proximidad temporal – Dos clases de flujos de E/S E/S:: • Usan una sola vez cada bloque • Usan repetidamente los bloques
Proceso
P Proceso
Cache
Cache
Disco
Disco
• Estructura Et t d datos de d t en memoria i con los l bloques bl más á frecuentemente f t t utilizados – Lecturas adelantadas – Limpieza de la cache (sync) • Problema: fiabilidad del sistema de archivos.
Cache de bloques II
Estructura de la cache de de la cache de bloques bloques 108
54
03/11/2009
Cache de páginas Cache de páginas Cache de páginas ache de páginas: : esconde esconde páginas en en vez vez de bloques de bloques de disco de disco utilizando utilizando técnicas de de memoria memoria virtual – En la E/S En la E/S mapeada mapeada en en memoria memoria se utiliza se utiliza la cache de la cache de página página – Las Las rutinas rutinas de E/S de E/S utilizan utilizan el buffer cache de disco
Flujo datos con buffer cache read (fd, buffer, tamaño) Usuario
buffer tamaño
arc hivo hi ló lógic i o (VFS) arc hivo lógic o (FFS)
3
4
5
6
bloques del archivo
Bloques lógic os (Servidor de bloques)
1340
1756
840
8322
bloques del dispositivo
Cache de bloques q (Servidor de bloques)
1340
1756
840
8322
1756 bloques del disco
Manejador de disco y dispositivo 8322
55
03/11/2009
Políticas de reemplazo • Algoritmo: Algoritmo: – Comprobar si el bloque a leer está en la cache. cache. • En caso de que no esté esté,, se lee del dispositivo y se copia a la cache. cache. • Si la cache está llena, llena, es necesario hacer hueco para el nuevo q reemplazando p uno de los existentes existentes:: p políticas de bloque reemplazo.. reemplazo • Si el bloque ha sido escrito (sucio): (sucio): política de escritura escritura.. • Políticas de reemplazo reemplazo:: FIFO (First in First Out), Out), segunda oportunidad, oportunidad, MRU (Most Recently Used), Used), LRU (Least Recently Used), Used), etc. etc. – La política de reemplazo más frecuentemente usada es la LRU LRU.. Esta política reemplaza el bloque que lleva más tiempo sin ser usado, usado, asumiendo que no será referenciado próximamente próximamente.. – Los bloques más usados tienden a estar siempre en la cache y, por tanto,, no van al disco tanto disco.. La utilización estricta de esta política puede crear problemas de fiabilidad en el sistema de archivos si el computador falla falla.. – La mayoría de los servidores de archivos distinguen entre bloques especiales y bloques de datos datos..
Políticas de escritura • Escritura inmediata (write write‐‐through through)): se escribe cada vez que se modifica el bloque.. bloque – No hay problema de fiabilidad fiabilidad,, pero se reduce el rendimiento del sistema.. sistema • Escritura diferida (write write‐‐back back)): sólo se escriben los datos a disco cuando se eligen para su reemplazo por falta de espacio en la cache. cache. – Op Optimiza timiza el rendimiento rendimiento,, pero genera los problemas de fiabilidad anteriormente descritos. descritos. • Escritura retrasada (delayed delayed‐‐write write), ), que consiste en escribir a disco los bloques de datos modificados en la cache de forma periódica cada cierto tiempo (30 segundos en UNIX). UNIX). – Compromiso entre rendimiento y fiabilidad fiabilidad.. – Reduce la extensión de los posibles daños por pérdida de datos. datos. – Los bloques especiales se escriben inmediatamente al disco disco.. – No se puede quitar un disco del sistema sin antes volcar los datos de la cache.. cache • Escritura al cierre (write write‐‐on on‐‐close close)): cuando se cierra un archivo, se vuelcan al disco los bloques del mismo que tienen datos actualizados actualizados..
56
03/11/2009
LFS: Sistemas de archivos LogLog-Structured • Las CPUs Las CPUs cada cada vez es más rápida y la memoria y la memoria más grande – La cache de disco La cache de disco puede puede ser ser más más grande – Aumenta el número el número de de peticiones peticiones de lectura de lectura que pueden venir de la cache – Por lo lo que, la lo que que, la mayoría la mayoría de los de los accesos a disco de los accesos a disco serán escritura a disco serán • Los sistemas Los sistemas de fichero de fichero Log structured (LFS o journaling) Log structured (LFS o journaling) graban graban cada actualización como una transacción transacción.. • Todas las transactiones se escriben se escriben en el log – Una transación se considera se considera committed committed cuando cuando se ha escrito se ha escrito en el haya actualizado todavía log, aunque el SF no se el SF no se haya • Las transactiones Las transactiones del log se escriben del log se escriben de forma asíncrona de forma asíncrona en el SF – Cuando el Cuando el fichero fichero se se modifica modifica, la , la transacción transacción se borra se borra del log • Si el SF Si el SF falla falla, el , el resto resto de de transacciones transacciones en el log quedan en el log quedan pendientes
SISTEMA DE FICHEROS Ficheros Directorios Implementación del del sistema sistema de ficheros de ficheros Ejemplos de sistema de sistema de ficheros de ficheros El El servidor servidor de de archivo archivo Aumento de prestaciones de prestaciones p Servicios del sistema de fichero
57
03/11/2009
Operaciones genéricas sobre archivos • creat: creat: crea un archivo con un nombre y protección y devuelve un descriptor • delete delete:: borra el archivo con un nombre • open: abre un archivo con nombre para una(s) operación(es) y devuelve un descriptor • close close:: cierra un archivo abierto con un descriptor • read: read: lee datos de un archivo abierto, usando su descriptor, a un almacén en memoria , p , • write write:: escribe datos a un archivo abierto, usando su descriptor, desde un almacén en memoria • lseek lseek:: mueve el apuntador a relativo_a mueve el apuntador a relativo_a+ desplazamiento + desplazamiento • ioctl ioctl:: permite manipular los atributos de un archivo
Servicios POSIX para archivos • Visión lógica: tira secuencial de bytes • Apuntador de posición a partir del cual se efectúan las operaciones • Descriptores de archivos: enteros de 0 a 64K. Predefinidos: Descriptores de archivos: enteros de 0 a 64K Predefinidos: – 0: entrada estándar – 1: salida estándar – 2: salida de error • Fork Fork: duplicación de BCP, pero compartición de tabla de archivos : duplicación de BCP, pero compartición de tabla de archivos • Servicios consulta y modificación atributos • Protección: – dueño grupo mundo – rwx rwx rwx • Ejemplos: Ejemplos: 755 755 indica indica rwxr rwxr-xr xr-x •
Ejemplo de programación en el libro (Programa 8.1)
58
03/11/2009
Archivos, , directorios Archivos directorios y servicios y servicios en POSIX (UNIX) • Tipos de archivo: – Normales Normales – Directorios – Especiales • Nombres de archivo y directorio: – Nombre completo (empieza por / Nombre completo (empieza por /) • /usr/include/stdio.h – Nombre relativo al directorio actual (no empieza por / Nombre relativo al directorio actual (no empieza por /) • stdio.h stdio.h, , /usr/include es el directorio actual. – La entradas . La entradas . y .. y .. pueden utilizarse para formar rutas de acceso • ../include/stdio.h
stat. Obtiene información sobre un archivo • Servicio: Servicio: #include #include int stat(char *name, struct stat *buf) *buf); ; int fstat(int fd, struct stat *buf) *buf); ; • Argumentos: Argumentos: • name nombre del archivo • fd descriptor p de archivo • buf puntero a un objeto de tipo struct stat donde se almacenará la información del archivo. archivo. • Devuelve: Devuelve: – Cero ó ‐1 si error
59
03/11/2009
stat. Obtiene información sobre un archivo • Descripción: Descripción: – Obtiene información sobre un archivo y la almacena en una estructura d tipo de ti struct t t stat stat: t t: struct stat { mode_t ino_t dev_t nlink_t uid t uid_t gid_t off_t time_t time_t time_t };
st_mode st_mode; ; st_ino st_ino; ; st_dev st_dev; ; st_nlink st_nlink; ; st uid; st_uid; st_uid uid; st_gid st_gid; ; st_size st_size; ; st_atime st_atime; ; st_mtime st_mtime; ; st_ctime st_ctime; ;
/* /* /* /* /* / /* /* /* /* /*
modo del archivo */ número del archivo */ dispositivo */ número de enlaces */ UID del propietario */ / GID del propietario */ número de bytes */ último acceso */ última modificacion */ último modificacion de datos */
Servicios POSIX para directorios • Visión lógica: tabla de entradas nombre lógico, nodo Visión lógica: tabla de entradas nombre lógico, nodo‐‐i • Cada entrada tiene la siguiente estructura: C d d i l i i Struct dirent { char *d_name d_name; ; ... }
/* nombre archivo */
• Gestión complicada porque los nombres de archivo tienen longitud G tió li d l b d hi ti l it d variable. • Servicios POSIX: gestión de directorios y de la tabla •
Ejemplos de programación en el libro (Programas 8.4 y 8.5)
60
03/11/2009
Servicios UNIX para ficheros y directorios Ficheros: stdin(), stdin (), stdout stdout(), (), stderr stderr(), (), creat creat(), (), fstat fstat(), (), fcnt fcnt(), (), flock flock(), link(), pipe(), (), link(), pipe(), mkfifo() mkfifo(), mkfifo () rename(), (), rename rename() rename () truncate(), (), truncate truncate() truncate () dup(), (), dup dup() dup () aio_read(), (), aio_read aio read() read(), aio_write () aio_write(), aio write() write(), () aio_suspend(), aio_suspend (), aio_cancel aio_cancel() () Directorios: mkdir(), mkdir (), rmdir rmdir(), (), opendir opendir(), (), close close(), (), closedir closedir(), (), readdir readdir(), (), chdir chdir(), link(), (), link(), symlink(), symlink (), rewinddir rewinddir(), (), getcwd getcwd(), (),
61