[CSE]  Advanced Operating Systems 
 COMP9242 2002/S2 

PRINTER Printer-Friendly Version
- Notices
- Course Intro
- Consultations
# On-line Survey (closed)
- Survey Results
- Lectures
- Milestone 0
- Project Admin
- Project Spec
- Project FAQ
- Exam
- ASysT Lab
- L4 source browser
- Sulima ISA Simulator
R4x00 ISA Summary 
MIPS R4700 ReferenceMIPS R4000 User Manual 
- Network Driver
- GT64111
Related Info
- Aurema OS Prize
- OS Hall of Fame
- 2000
- 1999
- 1998
- Gernot Heiser (LiC)

Valid HTML 4.0!
next up previous
Next: LFS Performance: Comparison with Up: 09-fs Previous: Limitations of Traditional File


Log-Structured File System (LFS)

Idea: Whole disk is a log[RO92].

  • Only write to end of log.
    • Eliminates most seeks.
  • Write in large chunks, called segments (64kB-1MB).
    • Amortises costs of any seeks.
  • Include in segments updated data block as well as metadata.
    • Can control write order by location within segment.
    • Ensures consistency of updates (like delayed writes).
  • Keep track of live data in previously written segments.
    • Segments without live data can be reclaimed.
    • Partially live segments can be compacted.
    • Uses garbage collector process, called cleaner.
  • Occasionally checkpoint metadata (using shadow paging).
    • Avoids processing whole log on restart.

LFS metadata:

  • In segments:
    • inodes (as in FFS, but pointers change frequently),
    • directories (as in FFS),
    • inode map, giving locations of inodes (changes frequently),
    • log of directory changes (to avoid multiple updates),
    • segment summary:
      • number of next segment,
      • summary of contents,
      • checksums of contents (to verify successful write).
  • In checkpoint:
    • timestamp,
    • address of last segment written,
    • segment usage table,
    • address of inode map.

LFS disk layout


  • LFS allows fast restart from crash:
    • Segment usage table allows locating unused segments to write.
    • Last segment pointer, and next pointer in segment summary allow recovery.
    • Imap pointers allow finding inode maps.
    • Time stamp allows locating last successful checkpoint.
  • LFS provides transaction semantics on metadata updates.

LFS cleaning

  • Cleaning is critical:
    • LFS can only operate fast if plenty free segments available
    • Segments utilisation drops over time as files get modified.
    • Most segments will not become totally empty.
    • Need garbage collection to compact partially-used segments.
  • Cleaning is tricky:
    • Normal log use is dominated by writes and minimises seeks.
    • Cleaning is dominated by reads, and requires many seeks.
    • Cleaner potentially destroys performance[SBMS93,SSB$^+$95].
  • Basic approach:
    • Try cleaning at times of low disk activity;
    • Try keeping disk utilization low (\(<80\)%).
    • Preferably clean lowly utilised segments.
    • Group files of similar age.

next up previous
Next: LFS Performance: Comparison with Up: 09-fs Previous: Limitations of Traditional File
Gernot Heiser 2002-10-11