- block devices
- any secondary storage device - usually disk-like
- models an array of uniform size blocks
- block allocation
- file representations
- contiguous - fast allocation, fast io; inflexible, internal and
external fragmentation
- directly linked lists - minimal overhead, flexible; slow, non-random
access, mixes data and metadata, doesn't cache well
- indirectly linked lists - reasonably fast, quasi-random access,
separates metadata and data; higher overhead
- free-block list
- large disks have a big free list
- bitmaps - no coalescing; cachable
- linked lists - requires expensive setups; no (easy) position
information
- indirect indexing - simpler than bitmaps, but bigger; cachable
- byte-stream io
- mapping between byte-stream position and storage block - like vm calculation
- does writing overwrite or insert
- overwriting - all but the last block is full; fast, simple traversal;
minimal internal fragmentation
- inserting - many partial blocks; slower, more complicated traversal;
much internal fragmentation
- block io
- buffering - the key to good file system performance
- prefetch - anticipating the next disk read
- overlaps processing and io
- more successful with regular access patterns - sequential
- locality still helps with more random access patterns
- cache blocks in the buffer
- serve blocks out of the buffers - no disk io
- works well for metadata - the root directory, free list, file block
list
- buffer replacement algorithms
- files are shared - caching writes causes consistency problems
- write-through caching - maintains consistency, increases disk loads
- periodic flushing - temporary inconsistency, decreases disk loads
This page last modified on 1 December 2004.