File System Refresher

I/O Device Basics

How to integrate I/O devices into the computer system

• connected with CPU by a series of buses

• hierarchical structure:
• high-performance bus is costly, and should be short. Only some fast devices should use it.
• hierarchical structure allows more devices to be connected to the CPU

How CPU interacts with devices

• Device components:
• hardware interface: expose abstractions to outside world
• internal structure: implement the abstractions

• Three kinds of protocols:
• polling: cpu do the data transfer, and status checking
• interrupt: cpu do the data transfer, and then context switch to other tasks, switch back when receiving interrupts from devices.
• prevent wasting cpu time on polling
• sometimes not a good solution, for example for some short device tasks the context switch and interrupt handling overhead may outweigh the polling overhead.
• Direct Memory Access: have a DMA engine, which is also a device to do the work. The cpu specifies the destination device, the data location, and size, the DMA engine will do the data transfer. After the device tasks completed an interrupt is issued to cpu from DMA engine.

How to communicate with devices actually

• I/O instructions: specialized instructions provided by the ISA, defining what should be done before issuing an instruction to communicate with devices. One example is in and out instructions on x86.

• Memory mapped I/O: map devices to certain locations in address space, issuing loads and stores to these locations are equal to transfer data from or to these devices.

How to make OS more device neutral

• add an abstraction layer that hides the device details.

• Other parts of OS only use the abstract interfaces.

• This is device drivers.

Summary

• devices are connected to cpu by all kinds of buses.

• cpu interacts with devices through their interfaces, conforming some protocols.
• polling, interrupts, DMA
• 2 methods to communicate with devices: specialized instructions and memory mapped I/O

• use device drivers to make OS device neutral.

Hard Disk Drives

Hard Disk Drives Interfaces and Internals

• interface: provides an address space of n sectors, numbered from 0 ~ n - 1. Accessing adjacent places is assumed to be fast.

• structure:
• a set of platters (each with 2 surfaces)
• each surface contains many tracks (concentric circles)
• each track contains many fixed-size sectors (often 512 Bytes, for example)
• disk head: for locating track

• Cost of Accessing Data:
• seek and rotate are slow, often in the magnitute of milliseconds
• sequential access is significantly faster than random access

File System Implementation: case study on vsfs

Mental Model of File System: what on-disk data structures are needed? how they are used in accessing files?

Organization of File System

• Data Blocks: containing user data

• i-node blocks: containing i-nodes, which contain meta data about file and points to data blocks.

• i-node bitmap: for i-nodes allocation

• data bitmap: for data blocks allocation

• super block: meta data for file system, such as the number of i-nodes, start of i-node table …

I-Node

• meta data

• direct pointers to data blocks

• indirect pointers

Directory

• a set of (name, inode) pair

• treat as a special kind of file