PDF de programación - Sistemas de Archivos Implementación - Módulo 11

Sistemas de Archivos

Implementación

Módulo 11

Departamento de Ciencias e Ingeniería de la Computación

Universidad Nacional del Sur

Objetivos

 Describir los detalles locales de la implementación del

sistema de archivos y estructuras de directorios

 Describir la implementación de sistemas de archivos

remotos

 Discutir algoritmos de alocación de bloques y bloques

libres y compromisos

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

1

Estructura del Sistema de Archivos

Estructura de Archivo

Unidad Lógica de almacenamiento

Colección de información relacionada

El sistema de archivos reside en almacenamiento
secundario (discos).

El sistema de archivo está organizado en capas.

File control block – estructura de almacenaje consistente
de información sobre el archivo.

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Sistema de Archivos en General

Sistema de Archivos

Estructur

a de

Archivos

Registr
os

Manejo

de

Directori

os

Método
s de
Acceso

Bloques
Físicos en
Memoria
Principal,

Bloques
Físicos en

Almacenaje
Secundario

buffers

Planificaci

ón de
Disco

Comand
os de

Usuario

y

Operació

n

Program

Nombres

as

Control

de

acceso

Funciones

de

manipulac

ión de
archivos

Bloque
o

Manejo
Libre

E/
S

Alocaci
ón de
Archivo

s

Manejo de
Archivos

Sistema Operativos

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

2

Un Bloque de Control de Archivos Típico

FCB: File Control Block

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Estructuras de Archivo

Bloques Físicos

Registros Lógicos

Fragmentación

Bloques
físicos

Registros lógicos

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

3

Estructuras del Sistema de Archivos en

Memoria

a) Apertura de un archivo b) Lectura de un archivo

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Implementación de Directorio

Lista lineal de nombres de archivos con punteros a los
bloques de datos.

simple de programar

consume mucho tiempo en la ejecución

Tabla hash – Lista lineal con estructura de datos hash.

Decrece el tiempo de búsqueda en el directorio

colisiones – situaciones donde dos nombres de
archivos van a la misma locación

Tamaño fijo

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

4

Métodos de Alocación

Un método de alocación se refiere a cómo los bloques

de disco de un archivo son ubicados:

Alocación Contigua

Alocación Enlazada

Alocación Indexada

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Alocación Contigua

Cada archivo ocupa un conjunto de bloques contiguos en el disco.

Simple – solo se necesita la locación de comienzo (block #) y la
longitud (número del bloques).

Acceso aleatorio.

Desperdicio de espacio (problema de alocación dinámica).

Los archivos no pueden crecer.

Mapeo de lógico a físico.

Dirección Lógica/512

Q

R

Bloque a ser accedido = Q + dirección de comienzo
Desplazamiento dentro del bloque = R

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

5

Alocación Contigua

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Alocación Enlazada

Cada archivo es una lista enlazada de bloques de
disco: los bloques pueden estar en cualquier lugar del
disco.

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

6

Alocación Enlazada

El archivo es definido por primero y último

Resuelve el problema de almacenaje - cualquier
bloque libre servirá

No soporta (eficientemente) el acceso directo

Simple – necesita solo la dirección inicial

Sistema de administración del espacio libre – no
malgasta espacio

No hay acceso aleatorio

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Alocación Enlazada (Cont.)

 File-Allocation Table (FAT) – alocación de espacio

de disco usado en MS-DOS y OS/2.

entrada de directorio

test

nombre

...
...

217

bloque inicial

0

217

618

339

eof

618

339

N° de bloques del disco - 1

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

7

Alocación Indexada

Pone todos los punteros juntos en bloque índice.

Vista lógica.

Tabla de índices

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Ejemplo de Alocación Indexada

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

8

Alocación Indexada – Mapeo (Cont.)



índice externo

tabla de índices

archivo

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Esquema Combinado: UNIX (4K bytes por bloque)

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

9

Administración de Espacio Libre

Vector de Bits – bit map (n bloques)

0 1 2

n-1

…

bit[i] = 1  bloque[i] libre

0  bloque[i] ocupado

Cálculo del número de bloque

(número de bits por palabra) *
(número de palabras con valor 0) +
offset del primer bit 1

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Administración de Espacio Libre (Cont.)

El bit map requiere espacio extra. Ejemplo:

tamaño bloque = 212 bytes

tamaño disco = 230 bytes (1 gigabyte)

n = 230/212 = 218 bits (o 32K bytes)

Fácil de obtener archivos contiguos

Lista enlazada (lista de libres)

No es fácil obtener espacio contiguo

No malgasta espacio

Agrupamiento

Cuenta

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

10

Administración de Espacio Libre (Cont.)

Necesidad de proteger:

Puntero a la lista de libres

Bit map

Debe mantenerse en disco

Copia en memoria y disco puede diferir.

No se puede permitir para bloque[i] tener una
situación donde bit[i] = 1 en memoria y bit[i] = 0
en el disco.

Solución:

Poner bit[i] = 1 en el disco.

Alocar el bloque[i]

Poner bit[i] = 1 en memoria

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Administración de Espacio Libre (Cont.)

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

11

Eficiencia y Desempeño

La eficiencia depende de:

alocacion en el disco y algoritmos de directorio

tipos de datos mantenidos en la entrada de directorio
del archivos

Desempeño

caché de disco – sección separada de memoria
principal para bloques frecuentemente usados

free-behind y read-ahead – técnicas para optimizar el
acceso secuencial

mejora del desempeño de la PC dedicando una
sección de la memoria como disco virtual, o disco
RAM.

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Distintas Locaciones del Caché de Disco

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

12

Recuperación

Verificador de Consistencia – compara datos en la
estructura de directorio con bloques de datos en el
disco, y trata de reparar inconsistencias.

Uso de programas de sistema para respaldar (back up)
datos del disco a otro dispositivo de almacenaje (floppy
disk, cinta magnética, optical, etc).

Se recuperan archivos perdidos o disco por
restauración de datos del backup.

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

El Sistema de Archivos de Red de Sun (NFS)

 Es una implementación y una especificación de un

sistema de software para acceder a archivos remotos a
través de LANs (o WANs).

 La implementación es parte de los sistema operativos
Solaris y SunOS que corre sobre estaciones de trabajo
Sun usando un protocolo no confiable datagrama
(protocolo UDP/IP) y Ethernet.

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

13

Vista Esquemática de la Arquitectura NFS

JRA © 2008

Sistemas Operativos – Sistemas de Archivos: Implementación

Fin

Módulo 11

Departamento de Ciencias e Ingeniería de la Computación

Universidad Nacional del Sur

14