CS 111 Lecture 11 Notes

File Systems

Prepared by Michael Sweatt and Steven Collison

Overview

In previous lectures, we described how an operating system interacts with storage while abstracting away the details of the logic used to store and retrieve files. In this lecture we will begin to describe the data structures and algorithms used to efficiently store and retrieve data on disk.

Some I/O Performance Metrics

• Utilization: The percent of the CPU doing useful work.
• Throughput: Rate at which requests are served (I/O requests served/sec).
• Latency: The amount of time it takes to serve a request.
• Transfer speed: The rate of data flow for I/O requests (Bits/sec)
• Capacity: The amount of data a device can hold.

Network Router: A Hypothetical Example

Hardware Specification

• Flash memory
• 1 GHz x86 CPU
• Programmed I/O Requires 1000 cycles (1 microsec)
• Device Latency: 100 microsec
• Programmed I/Os per command: 5
• Our Computation Requires: 5000 cycles (5 microsec)

Techniques to do I/O

Polling: Simplest Approach

• Request size: 1 byte
• Latency: 100 microsec
• Throughput: 10 kB/s
• CPU utilization: 5%

Batching: If a little is good more is better

• Request size: 840 bytes
• Latency: 1000 microseconds
• Throughput: 21 kB/s
• CPU Utilization: 10.5%

Batching + Interrupts: Blocking with big block size

• Latency: 106 microseconds
• Throughput: 18 kB/s
• CPU Utilization: 8.9%

DMA: Direct Memory Access

• Latency: 61 microseconds
• Throughput: 91 kB/s
• CPU Utilization: 45%

Batching + Polling: Hybrid

• Latency: 56 microseconds
• Throughput: 91 kB/s
• CPU Utilization: 84%

Real Hard drive Specs

• Device = Seagate Barracuda ES2 1TB
• Actual run-of-the-mill device
• Large capacity used in storage farms
• Mainstream model
• Controller has 16 MiB cache
• 4.16 ms average rotational latency
• 7200rpm drive = 120Hz
  • The amount of time it takes to do 1 rotation = 8.33 ms
  • About twice the average latency
  • Average latency = assume data is halfway away from read head
• Read seek time 8.5 ms average
• Write seek time 9.5 ms average
  • The two differ because write is harder than read
    • The write heads need to be positioned more accurately than read heads
• Track-to-track 0.8 ms read, 1.0 ms write
• 1287 Mb/s (megabits) max internal transfer read
• 116 MB/s (megabytes) max sustained transfer rate (0.93 Gb/s)
  • Sustained means if we keep reading
• 3 Gb/s external transfer rate (SAS)
  • Can't really get data this fast from disk, maybe in short bursts. Actual is 0.93 Gb/s
• 12.5 Watts for typical operations, 9W when idle
• 1.2 million hours mean time before failure (MTBF)
  • If run 24/7, there is AFR chance that it will fail in a year
• 0.73% AFR = annualized failure rate
  • When we write data to disk then read data back from disk, if there is 1 bit error, it recovers and gives correct data
  • However, If there are enough errors on disk, the error-correcting codes will not be sufficient, and there will be unreoverable errors

Performance Concerns

The primary bottleneck we are concerned with are:

• 4.16ms average latency
• 8.5ms average for read seek

A simple solution would be to overlap the latencies by performing these actions concurrently:
This solution is impractical since we cannot easier predict where the next request will be, making it hard to overlap the two operations.
The two has to be added which is approximately 13ms.

File System Design

Eggert FS

• Represents hard drive as a linear array of sectors
• Every file starts on sector boundaries
• The beginning of the disk is reserved for a table of the file entries
• Each file entry:
• maps a filename to the start of the file and its size
• Structure (16 bytes total):
• 10 bytes : filename
• short int: start of file
• int: File size:
• Pros:
• Low indexing overhead
• Simple
• Possible Issues:
• Internal fragmentation: Wasted data for each file since files must start on sector boundary
• External fragmentation: If a file is destroyed clean up does not occur often
• Files cannot easily grow
• Problem is directory order not contiguous data order

FAT File System

• FAT: File Allocation Table
• Clusters physical sectors into logical blocks
• Block 0: boot sector
• Block 1: Super block
• FS Version
• Partition size
• Count Used blocks
• Root directory
• Implemented as a linked list of sorts
• Each entry in the FAT is indexed by block number
• Each entry contains the block number for the next portion of the file
• There are 2 special values:
• NULL: designates the end of a file
• -1: designates a free block
• Structure of a file
• 8 bytes for the name
• 3 bytes for the extension
• Additional metadata for:
• size
• type
• etc
• Pitfall: renaming files

Due to the structure of the FAT it is easy to rename a file in the same directory, but very difficult for files in different directories.

Unix File System(UFS)

• inode table



• Indexed by inode number
• Each inode entry contains:
• File Owner
• File Group
• Permisions
• Size
• Link count: The number of files that current refer to this inode
• A table for all blocks that contain the file
• Direct Block Pointers: First level contains pointers to blocks
• Indirect Block Pointers:After those are exhausted the next level a pointer a to an array of block pointer
• Double Indirect Pointer: Last comes a pointer to an array of indirect block pointer
• Note that there is no filename here
• Special inodes
• inode 0: Reserved by the OS
• inode 1: Root directory
• Directories
• Maps files names to inode numbers
• OS treats as regular files and thus they have inodes numbers themselves

Further Reading

These cover the topics mentioned here in more detail and depth, some to a point beyond the scope of the course.