Quartz 4

Disk

2 min read

Disk Structure

A disk is a block structured device, and contains:

A set of magnetic platters, with two heads per platter (double sided) → Multiple tracks per platter All heads read the same track on different platters, this stack of tracks is referred to as a cylinder. Each block has a:

  • Cylinder Number
  • Head Number
  • Sector Number

OS Access

Device drivers manage the IO devices at the IO control layer

  • They’re given commands like: “read drive1, cylinder 72, track 2, sector 10, into memory location 1060” and output low level hardware specific commands to the hardware controller

Basic File Systems will be given a command like “retreive block 123”, and translate this to the device driver

Buffers are used to hold all the data in transit, and caches are used to hold frequently used data

Mapping Files Onto Disk Blocks

A disk block typically has a fixed size A file can be larger than a single block, so we need to split the file, to store it across multiple blocks This is done in three ways

  • Contiguous – like segmentation for memory
  • Linked list – like our freelist malloc last week
  • Indexed – like paging for memory

Contiguous Block Allocation

Each file occupies a set of contiguous blocks Gives best performance in most cases

  • Simple - Only starting location (i.e. block #) and length (number of blocks) are required Example:

Problems

Linked Block Allocation

Each file consist of a linked list of blocks Each block contains a pointer to the next This mean each file ends at a (null) pointer

  • Free Space Management System called when a new block is needed
  • You can improve the efficiency by clustering blocks into groups, but this increases Internal Fragmentation

Benefits

  • No External Fragmentation
  • No compaction

Problems

  • Reliability
  • Locating a block can take many disk seeks and IO

Indexed Block Allocation

Each file has its own index block(s), of pointers towards its data blocks Making it random access. It has dynamic access without external fragmentation, but each file has the extra overhead of an index block

Unix inode

Keeping Track of Free Blocks

This is done either by a:

  • Linked List (freelist)
  • Bitvector (array, with one bit per block)

Graph View

Backlinks