Lecture Notes for Operating Systems

Implementing Files, 27 November 2002

1. block devices

   1. any secondary storage device - usually disk-like

   2. models an array of uniform size blocks

2. block allocation

   1. file representations

      1. contiguous - fast allocation, fast io; inflexible, internal and external fragmentation

      2. directly linked lists - minimal overhead, flexible; slow, non-random access, mixes data and metadata, doesn't cache well

      3. indirectly linked lists - reasonably fast, quasi-random access, separates metadata and data; higher overhead

   2. free-block list

      1. large disks have a big free list

      2. bitmaps - no coalescing; cachable

      3. linked lists - requires expensive setups; no (easy) position information

      4. indirect indexing - simpler than bitmaps, but bigger; cachable

3. byte-stream io

   1. mapping between byte-stream position and storage block - like vm calculation

   2. does writing overwrite or insert

      1. overwriting - all but the last block is full; fast, simple traversal; minimal internal fragmentation

      2. inserting - many partial blocks; slower, more complicated traversal; much internal fragmentation

4. block io

   1. buffering - the key to good file system performance

   2. prefetch - anticipating the next disk read

      1. overlaps processing and io

      2. more successful with regular access patterns - sequential

      3. locality still helps with more random access patterns

   3. cache blocks in the buffer

      1. serve blocks out of the buffers - no disk io

      2. works well for metadata - the root directory, free list, file block list

      3. buffer replacement algorithms

   4. files are shared - caching writes causes consistency problems

      1. write-through caching - maintains consistency, increases disk loads

      2. periodic flushing - temporary inconsistency, decreases disk loads

This page last modified on 1 August 2002. pm4_include(/export/home/uf/rclayton/lib/html/skel-tail.html)