file allocation Flashcards
contiguous file allocation
the data that represents the file is stored together in one place in the file system
in the file, the next byte will also be the next byte on the storage medium
what are two benefits of contiguous file allocation
fast access: since all the blocks are adjacent you dont have to look for the next block
good for cd disks bluray etc as you map the entire file system before you write and when you do write each file is there in its entirety so you know how much it needs
what are two negatives of contiguous file allocation
you must know the size of each file before storing as you need to know how much space is needed before you start writing the next file
external fragmentation: you end up with unused blocks between files as you dont know how much space they need
what are the five types of file allocation
contiguous allocation
linked list allocation
indexed allocation
multi-level indexed allocation
combined allocatin
combined allocation
top level index block gives you access to data blocks for small files and for larger files the block points to another index level/block
small files =fast, large files = slower
multi-level indexed allocation
blocks with pointers pointing to blocks with pointers for however many levels you need for the size of the files
negative of multi-level indexed allocation
overhead with traversing
the more levels you have means more overhead which increases access time
positive of multi-level indexed allocation
can have larger files
how do extents work
the file system tries to allocate contiguous blocks but if you run out of space a new extent is created somewhere else on the disk
what is an extent
it describes a contiguous set of blocks on the disk that belong to a file and usually includes the starting block number and the length (number of blocks)
linked list allocation
takes each block for a file and create a chain/list
how does linked list allocation work
you have a directory entry with info including the start and end
in linked list why do we need to know the end of it just not the start
so we can append data to the end of the chain if needed
how does linked list allocation have storage overhead
the blocks dont have to be adjacent to eachother on the medium so theres a cost for moving between them as we need to store the pointer to the next block
how does linked list allocation avoid external fragmentation
due to blocks not being stored next to eachother so just point to the next block
what is a positive of linked list allocation
only has internal fragmentation
usually in the last block which is bounded by the size of the block and its lifetime
what is a negative of linked list allocation
only offers sequential access: you must follow the chain from the start to find something
indexed allocation
one of the blocks in the disk holds pointers to the blocks that represent data for that file
how do we access data in indexed allocation
via the block number and the offset within the block
what are two positives of indexed allocation
simple and fast
if you dont need to store the data then you can store a null pointer -> sparse files / files with holes
what are sparse files/ files with holes
files that for some of the blocks are empty
how are files represented in indexed allocation
each file is represented by an index block and each pointer points to a data block
what is a negative of indexed allocation
the size of the block limits pointers therefore it limits the size of file that you can have
