Embed Size (px)
Citation preview
Implementacion de F.S.
Asignación espacio
Manejo espacio libre Emely Arráiz
Ene-Mar 08
Manejo del espacio
Métodos de Asignación de espacio– Contigua– Enlazada– Indexada
Contigua
File Name Start BlockLength
FileAFileBFileCFileDFileE
2 39 5
18 830 326 3
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34
FileA
FileB
FileC
FileE
FileD
Características
El archivo ocupa un conjunto de bloques continuos en el disco.
Archivo definido por base mas longitud Soporta acceso secuencial y directo Dificultad de asignación de espacio o incrementar
el tamaño del archivo.
Enlazada
File Name Start Block End
... ... ...
......FileB 28
...1
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34
FileB
Características
Archivo definido por primer y ultimo bloque Archivo puede crecer, mientras que existan
bloques libres. No tiene problema de almacenaje, cualquier
bloque libre servirá Acceso directo no soportado de manera eficiente Espacio requerido para el apuntador Poco confiable
File-Allocation Table (FAT)
File-allocation table (FAT) – disk-space allocation used by MS-DOS and OS/2
Indexada
File Name Index Block
...
...
...
...FileB 24
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34
FileB
1831428
Archivo definido por un índice Soporta acceso directo y secuencial Overhead de espacio con el bloque de índice No hay fragmentación
Características
Unix I-node
Manejo espacio libre
Vector de bits
…
0 1 2 n-1
bit[i] = 0 block[i] libre
1 block[i] ocupado
Fácil para manejar archivos contiguo
Vector de bits
El mapa de bits requiere de espacio adicional. Ejemplo– Tamano del bloque = 2^12 bytes (4KB).– Tamano del disco = 2^30 bytes(1GB)– n= 2^30/2^12 = 2^18 (32KB 0 8 bloques)
Manejo de espacio libre
Lista enlazada – todos los bloques libres se encuentran
unidos por medio de apuntadores– El requerimiento de espacio contiguo no
puede ser satisfecho fácilmente– Emplea poco espacio. Es decir poco
overhead
Lista enlazada
Grupos– Almacena las direcciones de los bloques libres en
el primer bloque libre– permite encontrar las direcciones de los bloques
libres rápidamente.
Manejo de espacio libre
Counting– Guarda junto con la dirección del primer bloque
libre, el número de bloques contiguos que hay– Requiere de una tabla mas corta que la del
esquema de grupos pero ocupa cada entrada mas espacio.
Manejo de espacio libre
Manejo de espacio libre
Need to protect:– Pointer to free list– Bit map
Must be kept on disk Copy in memory and disk may differ Cannot allow for block[i] to have a situation where bit[i] =
1 in memory and bit[i] = 0 on disk
– Solution: Set bit[i] = 1 in disk Allocate block[i] Set bit[i] = 1 in memory
Implementacion de Directorios
Linear list of file names with pointer to the data blocks– simple to program– time-consuming to execute
Hash Table – linear list with hash data structure– decreases directory search time– collisions – situations where two file names hash
to the same location– fixed size
Desempeno
Cache de disco – se separa un pedazo de memoria para los bloques usados con mas frecuencia.
Crear en memoria discos virtuales o discos RAM (RAM disk)
