File System

Implementation

Persistent Storage

Allocation Strategies

• How much fragmentation do we get?
  • external segmentation: sequences of blocks are not enough
• How easy is it to allow a file to expand?
• The performance of sequential acce to the file versus random access to the blocks?
• What about the space that is required for meta-data?

Contiguous Allocation

• When a file is created give it blocks in sequence
• The info needed to access a file then:
  • the starting block
  • the size of the file

Extents

• extent: blocks that span over a gap (fragmented)
• Extents make up a single file
• For small file this will work well
• Sequential access still has good performance but a little more work
• Extents stored as an array with the starting block and size of each extent

Linked Allocation

• Pointer for the next block is stored for s block
• Solves the issue of external segmentation
• Random access performs badly

(FAT) File Allocation Table

• File system stores the location of the first block

From	To
2	3
3	4
9	13

Indexed Allocation

• Index array of each block
• Wastes space to store overhead

Multilevel Index