Upload
concepcion-alvarez-rivas
View
222
Download
0
Embed Size (px)
Citation preview
1Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
ISistemas de ficherosSistemas de ficheros
MS-DOS
2Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Estructura del disco en MS-DOS
Partición 1 Partición 2 (MS-DOS) Partición 4Partición 3
FAT
Sector de arranque secundario
Direct.raíz
Copia de FAT
Bloques de datos
Sector de arranque primarioMBR (Master Boot Record)
3Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Estructura del disco en MS-DOS – Sector de arranque primario (MBR: Master Boot
Record). Es un sector (512 bytes). Contiene: El programa de arranque: la BIOS supondrá que el MBR
contiene código ejecutable si los dos últimos bytes del MBR son 0xAA55. Sólo puede llegar hasta el byte 0x1BD (446 bytes).
La tabla de particiones se encuentra en 0x1BE: indica el principio, el tamaño y el tipo de cada partición. Se manipula con comandos como fdisk
– 0x1BE, primera partición. – 0x1CE, segunda partición. – 0x1DE, tercera partición. – 0x1EE, cuarta partición.
4Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Organización de una partición MS-DOS La partición contiene:
– Cabecera: información previa a la zona de datos. Está organizada en sectores (512 bytes) y contiene:
Sector de arranque FAT (File Allocation Table): tabla que describe a qué
fichero pertenece cada cluster de datos. Contiene una entrada por cada cluster de datos. Los clusters libres y defectuosos se marcan con un código especial.
Copia de la FAT: para mejorar la fiabilidad Directorio raíz: es el único directorio que no se
implementa como un fichero.
– Zona de datos donde se almacenan los ficheros. Se organiza en clusters (2N sectores contiguos).
5Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Sector de arranque de MS-DOSEl sector de arranque de MS-DOS contiene
– Información sobre el sistema de archivos como: Número de bytes por sector. Número de sectores por cluster. Tamaño del directorio raíz. Número de tablas FAT. Tamaño del dispositivo.
– Código para iniciar el s.o.: Búsqueda del directorio raíz. Carga de los ficheros “io.sys” y “msdos.sys”. Transfiere control al “io.sys”.
6Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
La FAT (File Allocation Table)– MS-DOS organiza los ficheros como una lista enlazada, pero
los punteros no se encuentran en el cluster, sino en una estructura de datos denominada (FAT) localizada en los primeros sectores del disco.
– La FAT contiene una entrada por cada cluster de datos. Esta entrada puede indicar:
Si el cluster está libre (código especial) Si el cluster es defectuoso (código especial) En el caso que el cluster esté ocupado, indica el siguiente cluster
o final de fichero (código especial) si es el último.
7Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
La FAT (File Allocation Table)
6 8 4 2
5 9 12
10 3 13
f1
f2
f3
f1 ... 6f2 ... 5f3 ... 10
DIRECTORIO
EOF2133249586
libre748
129310
error11EOF12EOF13libre14
reservado1reservado0 TamañoTamaño
del discodel disco...Nombre fichero
1er cluster
8Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Ejemplos de FAT
ClustersTamaño Partición
4 KB 8 KB 16 KB 32 KB
8 GB 8 MB 4 MB 2 MB 1 MB16 GB 16 MB 8 MB 4 MB 2 MB32 GB 32 MB 16 MB 8 MB 4 MB64 GB 64 MB 32 MB 16 MB 8 MB
2 TB (2,048 GB) --1,024MB
512MB
256 MB
AtributosFAT12 FAT16 FAT32
Se utiliza enDisquetes yparticiones(pequeñas)
Particiones(pequeñas ymedianas)
Particiones(medianas y
grandes)Tamaño de
entrada12 bits 16 bits 28 bits
Máximo número deClusters
4,078 65,518 ~268,435,456
Tamaño de Cluster 0.5 KB a 4 KB 2 KB a 32 KB 4 KB a 32 KBMáximo tamaño de
la partición16,736,256 2,147,123,200 Aprox. 2^41
Tamaño FAT,
utilizando FAT32
9Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
La FAT: análisis – El acceso directo sigue siendo costoso de implementar
(aunque no tanto como en la asignación enlazada) debido al elevado número de desplazamientos del cabezal del disco:
Ejemplo: lseek (fd, 32768,0) Si la FAT no se encuentra completa en memoria son necesarios en el peor caso 33 accesos a bloques. No obstante, colocar parte de la FAT en una cache en memoria mejora significativamente el caso medio.
– Diseño poco elegante: en una misma estructura de datos se mezcla información de diferentes ficheros.
– Baja fiabilidad: la pérdida de un bloque de la FAT puede ocasionar la pérdida del disco entero.
Posible mejora: replicar la FAT.
10Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Directorios en MS-DOS – Estructura de directorios: árbol.
– Los directorios son ficheros con un número arbitrario de entradas excepto el directorio raíz que está en la cabecera del disco y tiene un tamaño máximo prefijado (Ejemplo: 224 entradas para disquetes de 3.5”).
– La entrada de directorio contiene todos los atributos del fichero de forma residente excepto los datos, para los cuales sólo se indica el primer cluster (la FAT proporciona el resto de punteros).
11Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Entrada de directorio en MS-DOS– Contiene:
Nombre del fichero Extensión: .exe, .txt, etc. (Ext.) Atributos: del sistema, ocultos, etc. Tiempo de última modificación (Tiempo), Fecha de creación (Fecha). Puntero al primer cluster de datos. Tamaño del fichero (Tamaño).
Nombre Ext. Reservado
8 3 1 10 2 4
Atributos
Tamaño
2 2
Fecha
Bytes
Tiempo 1er cluster
12Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Evolución de los sistemas de archivo basados en MS-DOS:– FAT12 (DOS anteriores a la versión 4.0 y disquetes)
Valores de cluster en la FAT son de 12 bits. Máximo número de clusters direccionables = 4078 (18 valores
reservados) Nombre de fichero = 8 + 3 caracteres. El número de entradas del directorio ‘\’ está limitado.
– FAT16 (DOS posteriores a la versión 4.0) Valores de cluster en la FAT son de 16 bits. Máximo número de clusters direccionables = 65518. Valores límite de las particiones: 65518 * tamaño del cluster.Tamaño del Cluster Tamaño Máximo Partición (MB)
2 kB 127’98 MB4 kB 255’96 MB8 kB 511’92 MB16 kB 1023’84 MB32 kB 2.047’69 MB
13Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Evolución de los sistemas de archivo basados en MS-DOS:– VFAT (Windows 95 OSR1 y DOS 7.x)
Valores de cluster en la FAT son de 12 ó 16 bits. Long File Names (LFN): nombre del fichero (255 caracteres), alias
atributos adicionales (RO | Hidden | System | Vol Label). Acceso a disco utilizando las rutinas de 16 ó 32 bits (high-speed
& protected mode).
– FAT32 (Windows 95 OSR2) Valores de cluster en la FAT son de 28 bits. No está limitado el tamaño ni el número de entradas en ‘\’. Teóricamente puede soportar discos con 268 millones de clusters
(2TB). ¿Tamaño de la FAT?:
14Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMS-DOSMS-DOS
Evolución de los sistemas de archivo basados en MS-DOS:– FAT32 (Windows 95 OSR2)
ParticiónCluster
4 kB 8 kB 16 kB 32 kb8 GB 8 MB 4 MB 2 MB 1 MB16 GB 16 MB 8 MB 4 MB 2 MB32 GB 32 MB 16 MB 8 MB 4 MB64 GB 64 MB 32 MB 16 MB 8 MB
2 TB (2.048 GB) -- 1.024 MB 512 MB 256 MB
15Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
ISistemas de ficherosSistemas de ficheros
Unix / Minix
16Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IUnixUnix
Estructura de datos nodo-i (i-node) – Estructura de datos donde se registran todos los atributos de un
fichero excepto el nombre.
– Utiliza asignación indexada de bloques con punteros a bloques directos, indirectos, doblemente indirectos y triplemente indirectos.
Estructura de datos nodo-i : análisis – Acceso aleatorio eficiente: El número máximo de accesos a
disco está limitado a 4. Los punteros indirectos sólo se utilizan para ficheros grandes y muy
grandes (que son escasos). Para los ficheros pequeños el acceso es muy eficiente.
– Diseño elegante y fiable: cada fichero tiene su estructura de datos separada.
17Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IUnixUnix
Nodos-iModo
NODO-I
datos
datos
datos
datos datos
datos
datos
Núm. enlacesUIDGID
longitudTiempo creación
Tiempo modificaciónTiempo acceso
10 punteros
directos
1 puntero indirecto1 ptr indirecto doble1 ptr indirecto triple
datos
etc.
18Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IUnixUnix
Directorios en UNIX – La estructura de directorios es un grafo acíclico dirigido (DAG).
– Los directorios son ficheros.
– La entrada de directorio (denominada enlace) no tiene ningún atributo residente; sólo el nombre del fichero y una referencia al nodo-i (número de nodo-i ).
– El nombre del fichero incluye la extensión (total 14 bytes por defecto, pero con posibilidad de especificar nombres más largos en la configuración del sistema).
Nombre de ficheroNúm
nodo-i
2 14Bytes
19Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMinixMinix
Nodo-i en Minix
0123456i
di
propietariogrupo
instante modif.
nº de enlaces
indirectodoble indirecto
7 zonas
512zonas
datos
datos
datos
datos
.
.
.
datos
datos
5122
zonas
.
.
.
.
.
.
.
.
.
datos
datos
datos
datos
modo
tamaño
tipo: directorio, regular, especialbits de permiso
En una zona de 1024 bytes caben 512 referencias
de 2 bytes
16 bits
32 b
yte
s
20Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMinixMinix
Directorios en MINIX – La entrada de directorio es de 16 bytes:
2 para nodo-i y 14 para nombre
– Cuando se crea un directorio, se crean las entradas ‘.’ y ‘..’ automáticamente.
– El nodo-i 1 describe al directorio raíz
– Cuando se borra una entrada se marca con el nodo-i 0
/
home etcusr
unx os2
4 .1 ..
278 unx987 os2
987 .4 ..
1 .1 ..3 usr4 home5 etc
21Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMinixMinix
Estructura del disco en MINIX – Un partición Minix se construye sobre un entramado de bloques
de tamaño fijo. La estructura de la partición consta de: La cabecera estructurada en grupos de bloques con las estructuras
de datos del sistema de ficheros Los bloques de datos estructurados en zonas. Las zona es la
unidad de asignación. 1 zona = 2N bloques. En la distribución estándar, una zona equivale a un bloque.
superbloque
bloque de arranque
mapa denodos-i
mapa dezonas
bloques denodos-i
zonas dedatos
22Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMinixMinix
Estructura del disco en MINIX – Bloque de arranque: contiene el programa de arranque que
carga el sistema operativo y le transfiere control.
– Superbloque: es una estructura de datos con la descripción de la estructura del disco: tamaño y ubicación de cada elemento.
– Mapa bits nodos-i: es un vector de bits que indica los nodos-i libres y ocupados. Existe un bit por cada nodo-i.
– Mapa bits zonas: es un vector de bits que indica las zonas libres y ocupadas. Existe un bit por cada zona.
– Bloques de nodos-i: contienen las estructuras de datos nodos-i. Una por cada fichero. El número de nodos-i depende del tamaño de la partición. El nodo-i 0 no se utiliza.
– Bloques de datos: bloques que almacenan bloques de datos de ficheros regulares, directorios y de referencias a otros bloques.
23Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMinixMinix
Superbloque de MINIX
Número de bloques
Número de nodos-i
Número de bloquespara el mapa de nodos-i
Número de bloquespara el mapa de zonas
Primer bloque de datos
Número mágico
Asignado al crear el sistema de archivos. Puede sermenor que el tamaño de la partición
Asignado al crear el sistema de archivos. Es fijadopor el usuario o se asigna un valor calculado por defecto
[Número de nodos-i / Número de bits por bloque]
[Número de zonas de datos / Número de bits por bloque]
2 (arranque y superbloque) + Número de bloquespara el mapa de nodos-i + Número de bloques
para el mapa de bloques + Número de bloques de nodos-i
Un valor numérico que sirve para “garantizar” queesta partición contiene un sistema de archivos MINIX
24Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMinixMinix
Tamaños estándar en MINIX– Bloque (=Zona): 1024 bytes
– Referencia a bloque: 2 bytes
– Enlace en directorio: 16 bytes
– Nodo-i: 32 bytes Cálculo del tamaño del fichero máximo
Con punteros de 16 bits, tamaño de zona de 1Kb y la estuctura del nodo-i descrita el tamaño del fichero máximo es el mínimo entre las siguientes cantidades:
– 216 * 1Kb = 64 Mb
– 7*1Kb + (1Kb / 2) * 1Kb + (1Kb / 2)2 * 1Kb=
7 Kb + 512 Kb + 262.144 Kb = 262.633 Kb (aprox. 256.5 Mb)
25Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMinixMinix
Cálculo de la estructura de una partición en MINIX– Tamaños calculados en MINIX dados:
T (número de bloques del sistema de archivos) y
F (número de nodos-i máximo sin incluir el cero): Bits_Por_Bloque: 1024*8 = 8192 Enlaces_Por_Zona: 1024 / 16 = 64 Referencias_Por_Zona: 1024 / 2 = 512 Nodos-i_Por_Bloque: 1024 / 32 = 32 Bloques_Mapa_Nodos-i: F / Bits_Por_Bloque Bloques_Mapa_Zonas: Zonas de datos / Bits_Por_Bloque Bloques_Nodos-i: F / Nodos-i_Por_Bloque Bloques_De_Datos: T - 2 - Bloques_Mapa_Nodos-i -
Bloques_Mapa_Zonas - Bloques_Nodos-i
26Tema: Casos de estudio
S0
2
Sis
tem
as
op
era
tivos I
IMinixMinix
Zonas y bloques en Minix– Para direccionar particiones de gran tamaño, Minix permite
agupar los bloques de datos en zonas.
– Una zona = 2N bloques. El valor N se almacena en el superbloque.
– El primer bloque de datos (valor almacenado en el superbloque) se reajusta para que coincida con el comienzo de una zona.
– Ejemplo: Bloque: 1024 bytes Zona: 4 Bloques Enlaces_Por_Zona: 4096 / 16 = 256 Referencias_Por_Zona: 4096 / 2 = 2048