Story Transcript
Sistemas operativos Tema 10: Sistemas de ficheros
Sistemas de ficheros ► El
sistema de ficheros suele ser el aspecto más visible de un SO para los usuarios. ► Objetivos: Ofrecer una visión uniforme del almacenamiento de información en memoria secundaria. ► El
SO oculta las propiedades físicas de los discos, y define una unidad lógica de almacenamiento: el fichero.
Gestionar el espacio de almacenamiento y el acceso a la información.
Sistemas de ficheros ► Los
primeros SO soportaban tipos de ficheros, incorporando código para interpretar su estructura y contenido. ► Actualmente, se tiende a ver los ficheros como secuencias no interpretadas de bytes. Máxima flexibilidad, pero mínimo soporte: queda todo en manos de las aplicaciones. Todo lo más, el SO distingue ficheros ejecutables, y tipos de documentos según el programa con que se crean o editan.
Métodos de acceso a ficheros ►
Acceso secuencial: se accede a las distintas partes de un fichero una tras otra, en un orden predeterminado. Al abrir un fichero, el puntero de L/E se sitúa al principio del mismo. Cada operación de L/E accede a la posición apuntada y hace que el puntero avance a la posición siguiente.
►
Acceso directo: se puede acceder a las distintas partes de un fichero en cualquier orden. Los ficheros se ven como secuencias de bloques de longitud fija. Las operaciones de L/E indican un número de bloque relativo al comienzo del fichero.
►
Se puede simular de manera eficiente el acceso secuencial sobre dispositivos de acceso directo, pero no viceversa.
Estructura física y lógica
Estructuras de sistemas de ficheros ► Muchos
sistemas de ficheros combinan dos estructuras distintas: Directorio de dispositivo. ► Contiene
información sobre las propiedades físicas de cada fichero: localización en el dispositivo de almacenamiento, tamaño, etc.
Directorio de ficheros. ► Contiene
información sobre las propiedades lógicas de cada fichero: nombre, tipo, propietario, permisos, etc.
► La
vinculación entre ambas estructuras se hace a través de un identificador unívoco de fichero.
Directorio de nivel único ►
Todas las entradas en el mismo nivel. directorio
ficheros
► ►
Solución adoptada en los directorios de dispositivo. No se utiliza en directorios de ficheros, por dos motivos principales:
Falta de organización lógica. Limitaciones al nombramiento: no podría haber dos ficheros con el mismo nombre, aunque pertenecieran a distintos usuarios.
Directorio de dos niveles ►
Un directorio por cada usuario. so1
p1.c
p2.c
func.h func.c
so2
directorio raíz
so3
p1.tgz notas
p1.c
p1b.c
core
directorios de usuario ficheros
► ►
Sólo se requiere unicidad de nombres dentro de cada directorio. Un usuario puede acceder a los ficheros de otro indicando caminos de búsqueda.
Estructura de árbol ► Generalización
del directorio de dos niveles.
Los usuarios pueden crear subdirectorios. home
so1
p1.pdf
prac1.c p1.pdf func.h func.c
so2
bin
opt
bash
gcc
p1.tgz p1b.tgz p1.c
info
share
texinfo web2c
Estructura de árbol ► Dos
tipos de caminos:
Absolutos: desde el directorio raíz. Relativos: desde el directorio actual. ► Existe
un único camino para cada fichero o subdirectorio desde el directorio raíz.
Estructura de grafo acíclico ►
Ficheros y subdirectorios pueden tener varios caminos desde el directorio raíz (y, por extensión, varios nombres). dict
list
all
w
spell
count
list
count words
radc
w7
list
Estructura de grafo acíclico ►
El grafo acíclico facilita la compartición de ficheros y subdirectorios entre usuarios. Sin embargo, complica los mecanismos de generación de estadísticas de disco, copia de seguridad, etc.
►
Implementaciones: Información replicada. ► Al
modificar un fichero, por consistencia, hay que modificar igualmente todas sus réplicas.
Una única copia, y enlaces a los ficheros o subdirectorios compartidos. ► Al
borrar un fichero o subdirectorio, se elimina un enlace. ► El fichero o subdirectorio se borra cuando no quedan enlaces a él (se necesita un contador de referencias).
Estructura de grafo general ►
Se permite la aparición de ciclos, enlazando subdirectorios de nivel superior. dict
list
spell
count words
old
list
radc
ipc
w7
list
Estructura de grafo general ► ►
La existencia de bucles complica la generación de estadísticas y los mecanismos de copia de seguridad. Problemas con el borrado: pueden existir subdirectorios con el contador de referencias a un valor distinto de cero, y que sin embargo no son alcanzables desde el directorio raíz. Información inaccesible. Se necesita un recolector de basura.
►
Pocas ventajas con respecto al grafo acíclico Æ la estructura de grafo general apenas se utiliza.
Asignación de espacio
Asignación de espacio ► Objetivos
principal:
análogos a la gestión de memoria
Aprovechamiento de espacio. Acceso eficiente a los ficheros.
► Compromiso
asignación:
común a todas las formas de
Como el almacenamiento se realiza por bloques, aparece una fragmentación interna media de ½ bloque por fichero. ► ¿Mejor
bloques pequeños?
► ¿Mejor
bloques grandes?
Para reducir los accesos a disco, debería maximizarse la cantidad de información leída en cada operación de E/S.
Asignación contigua ►
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A cada fichero se le asigna un conjunto de bloques contiguos en disco. Estrategias first-fit, best-fit o worst-fit. El directorio de dispositivo almacena la dirección del primer bloque y el número de bloques que le siguen.
Soporte eficiente para acceso secuencial y para acceso directo. ► Fragmentación externa. ►
Se requieren mecanismos de compactación.
►
Otras cuestiones:
¿Cómo saber cuánto espacio necesitará un fichero? ¿Qué hacer si un fichero crece y no hay bloques libres después del último?
Asignación enlazada ►
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Se ve cada fichero como una lista enlazada de bloques. El directorio de dispositivo almacena la dirección del primer bloque. Cada bloque almacena un puntero al siguiente.
►
No hay fragmentación externa.
Aún así, la compactación puede mejorar el rendimiento de la E/S.
Soporte eficiente sólo para acceso secuencial. ► El espacio ocupado en punteros se hace notorio con bloques pequeños. ► La pérdida de un puntero hace inaccesible el resto del fichero. ►
Asignación indexada ►
BI
1
2
3
4
5
6
7
8
9
10
BI
12
13
14
15
16
17
18
19
20
Cada fichero tiene un bloque índice (BI), con punteros a los bloques que almacenan sus datos.
El directorio de dispositivo almacena la dirección del BI.
► ► ►
Soporte eficiente para acceso secuencial y para acceso directo. No hay fragmentación externa. Ficheros pequeños desaprovechan gran parte de su BI Æ despilfarro de espacio. ¿Bloques pequeños?
►
En el BI caben un determinado número de punteros Æ tamaño máximo de los ficheros limitado. ¿Bloques grandes?
Bloques índice enlazados BI
1
2
3
BI
5
6
7
8
9
10
11
BI
13
14
15
16
17
18
19
20
►
El último puntero de un bloque índice puede apuntar a otro bloque índice. No hay limitación de tamaño.
►
Acceso más lento al final de los ficheros.
Bloques índice multinivel BI1
BI2
BI2
BI2
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
►
►
Los bloques índice de primer apuntan a bloques índice de segundo nivel, y así sucesivamente. Sólo apuntan a bloques de datos los bloques índice de nivel más bajo. Sigue habiendo limitación de tamaño.
►
Se accede por igual a cualquier parte de los ficheros.
Gestión del espacio libre
Gestión de espacio libre ►
La gestión del espacio libre implica: Buscar y asignar espacio libre cuando se crea un fichero. Registrar como libre el espacio que ocupaba un fichero que se borra. Actualizar el mapa del espacio libre cuando un fichero crece o se trunca.
►
Consideraciones importantes: Espacio en disco necesario para almacenar el propio mapa de espacio libre. Facilidad para encontrar 1 bloque libre o n bloques libres contiguos. Facilidad para actualizar el mapa de espacio libre.
Vector de bits 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
► Un
bit por cada bloque de disco.
0 Æ bloque libre 1 Æ bloque asignado 101000011101001100000 ► Por
cuestiones de eficiencia, el vector se suele cargar en memoria.
Vector de bits ►
Ventajas: Fácil de implementar y usar con cualquier método de asignación. Facilidad para encontrar un bloque libre o un conjunto de bloques contiguos libres. Actualización sencilla.
101000011101001100000 ►
Inconveniente: tamaño excesivo con discos grandes.
Ejemplo: disco de 16 GB y bloques de 512 bytes Æ vector de 8MB. ► Reservar
8 MB de memoria, o recorrer hasta 16384 bloques de disco.
Solución: usar bloques libres para gestionar el espacio libre.
Lista enlazada de bloques libres ►
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
►
►
Mínimo desperdicio de espacio: sólo se necesita almacenar la dirección del primer bloque libre. Con asignación no contigua, para buscar n bloques libres hay que leer n-1 bloques. Con asignación contigua, por lo general, hay que leer muchos más.
Lista enlazada de secciones libres 0
0
1
2
3
4
5
6
7
8
3
0
9
10
11
12
13
14
15
16
17
18
19
20
1
4
► Cada
bloque de la lista enlazada indica cuántos bloques libres le siguen. Mayor eficiencia para la asignación contigua.
Lista enlazada de bloques índice 0
BI
2
3
4
5
BI
7
8
9
10
11
12
13
14
15
BI
17
18
19
BI
►
Un bloque índice contiene un cierto número de punteros a bloques libres, más un puntero a otro bloques índice. Se pueden localizar rápidamente un gran número de bloques libres.
►
Alternativa más eficiente para asignación contigua: apuntar a secciones de bloques libres contiguos.
Fin