Operating Systems Lecture Notes

2014 November 25 • File Systems at Rest

---

Outline

• Disk
  • Partitions and disk blocks.
• Buffering
  • Management and coherence.
• Access provisions.

Disk Layouts

• A disk can be divided up into one or more partitions.
  • Each partition corresponds to a file system.
• Disk sector 0 is the master boot record (MBR).
  • The MBR ends with the partition table.
• The MBR identifies at least one of the partitions as bootable.
• The boot sequence (usually BIOS) reads the MBR.

Partitions

• Small MBRs identify a few (up to 4) primary partitions.
  • Large disks have lots of space.
• A designated extended (primary) partition contains a logical partition table.
  • There can be any number of logical partitions.
  • Logical partitions aren’t directly bootable.
  • GRUB handles that problem.

Partitions Illustrated

Why Partition?

• Multiple file systems.
  • Performance: swap partition, selective back-ups.
  • Reliability: limit loss.
  • Convenience: multi-boot systems, sharing data.
• Why not partition?
  • Get the partition sizes wrong.
  • Partition editors are touchy.

Disk Block Size

• A file is a sequence of file blocks.
• How big’s a file block?
  • Some multiple of sector, track, or cylinder.
• The classic time vs space trade-off.
  • Large file blocks: high performance, low utilization.
  • Small file blocks: vice versa, plus overhead.
• Time is more precious than space.

Block-Size Example

• Assume a disk with

  2¹⁷ (= 131,072) bytes/track
  7,200 rpm (= 8.33 msec/r)
  10 msec average seek time

• The transfer time for a k-byte block is

  10 + 8.33/2 + (k/2¹⁷)×8.33

• What’s a good value for k?

Time v Space Illustrated

• 2k file size.

Performance

• Disk delay is bad (5 nsec/byte), latency is worse (10 msec).
• Objects accessed frequently should be close at hand.
• Primary store Disk-block buffer (or cache)

  

Buffer Write-Through

• A block gets written to the cache, and gets written to the disk.

  

• This is write-through buffering.
• Disk traffic is decoupled, but not isolated, from demand.
• The next step is fully decouple trafic and demand.

Buffer Write-Back

Buffer Coherence

• Write-back buffering decouples a bit too much.
  • The buffer has expected disk state, not the disk.

  

• This state difference is the buffer coherence problem.

Coherence Problems

• Buffer (in)coherence can violate shared assumptions.

  

• File system metadata incoherence can be fatal.
  • Write-back early and often, or write-through always.

Buffer Reading

• A buffer-read miss.

  

• Prefetching

  

Buffer Management

• A full buffer needs to eject blocks.
  • Similar to VS page management.
  • Not as performance demanding; more time and space for management overhead.
• True LRU is possible, but data semantics inteferes.
  • Important data are not LRU.
  • Important data doesn't get flushed.
• Use LRU and selected write-back.

Technology Advances

• Disks and primary store are getting bigger.
  • And faster, but not as fast as they're getting bigger.
  • And disk less so than RAM.
• Buffers can be easily be large enough to satisfy most I-O requests.
• But metadata coherence and write-backs force writes.
  • Inefficient writes too: small and scattered.

Amortization

• Condense small scattered writes into a single large (1 mbyte) journal (or log) entry.
• A full journal entry is written to end of a sequence of journal entries on disk.
  • Minimal and friendly disk arm movement.
• The disk partition contains the file system and the journal-entry sequence.
• The combination is known as a journaling (formally log-structured) file system.

Untangling The Journal

• A journal entry a combination of all previous writes.
  • A hodgepodge of data from everywhere, including file-system metadata.
• A scavenger or cleaner untangles the journal back into the file system.
  • Periodically scheduled at slack times.
• The journal also serves as a checkpoint for crash recovery.
  • This requires delicate journal write-back.

Access

• A general view of access:
  • An object presents a set of operations it performs.
  • An agent can invoke operations on an object.
    • An agent can be an object, and vice versa.
• With no access restrictions, any agent can invoke any operation on any object.

Access Control

• An access (or permissions or protection) matrix describes a less permissive scheme.

  

Access Permissions

• o_{i, j} is the set of operations agent A_i can perform on object O_j.
• If A_i wants to perform o_k on O_j, check to see if o_k \(\in\) o_{i, j}.
  • In theory, do this look-up on every operation.
• The access matrix is an object with operations for manipulating access permissions.

Analysis

• The reference monitor is the agent using the access matrix in this way.
• An access matrix is conceptually simple, but it's:
  • huge; many agents and objects.
  • sparse; most agents ignore most objects.
  • fine grained: every agent vs every object.
  • high overhead: every agent vs every object.

Matrix Sections

• There are two ways to cut the matrix down to size: along the rows and along the columns.
• Cutting along a row creates a capability for an agent.

  

• An agent's A capability lists the objects and operations A can perform.

Another Cut

Cutting along a column creates an access-control list (ACL). An object's ACL lists the agents and the operations they can perform. ACLs are the basis for most advanced permission systems.

Summary

• Disks are divided into partitions with a file-system per partition.
  • A File system is further divided.
• Disk buffering helps hide disk-based latency and delay.
  • But incurs problems similar to those in VS paging.

References

• Taking Advantage of Linux Capabilities by Michael Bacarella in Linux Journal, May, 2002.

---

This page last modified on 2012 April 11.