File system layout; free block management

File system layout

A file system layout is the way the disk is organised to store the file system. A disk is divided into partitions; each partition holds an independent file system.

 Sector 0                      whole disk
 +-----+-----------+-------------+-------------+
 | MBR | Partition | Partition 1 | Partition 2 |
 |     |   table   |             |   ...       |
 +-----+-----------+-------------+-------------+

 One partition:
 +------+-------+----------+---------+------+----------------+
 | Boot | Super | Free-    | I-nodes | Root | Files and      |
 | block| block | space    |         | dir  | directories    |
 |      |       | mgmt     |         |      |                |
 +------+-------+----------+---------+------+----------------+

• MBR (Master Boot Record): sector 0; contains boot code and the partition table with start and end of each partition and the active one. The BIOS reads and runs it, which loads the boot block of the active partition.
• Boot block: first block of a partition; program that loads the operating system.
• Superblock: key information about the file system: type (magic number), number of blocks, block size, number of i-nodes, free-block counts.
• Free space management: bit map or list of free blocks.
• I-nodes: an array of i-nodes, one per file (attributes and block addresses).
• Root directory: top of the directory tree.
• Data area: all the other files and directories.

Management of free blocks of secondary storage

The OS must keep track of which disk blocks are free. Common methods:

1. Bit map (bit vector) - one bit per block: 1 = free, 0 = allocated (or the reverse). Example: for a disk of 16 blocks where blocks 2, 3, 5, 8, 9 are free:

 block: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
 bit  : 0 0 1 1 0 1 0 0 1 1  0  0  0  0  0  0

Simple and easy to find n consecutive free blocks. Size = number of blocks / 8 bytes: a 16 GB disk with 1 KB blocks has 16 M blocks, so the map needs 16 Mbit = 2 MB.

2. Linked list of free blocks - each free block holds the address of the next free block; the OS keeps only the head. No extra space is used, but traversing the list is slow.

 head -> [2 |->3] -> [3 |->5] -> [5 |->8] -> [8 |->9] -> nil

3. Grouping - the first free block stores the addresses of n free blocks; the last of those holds the addresses of the next n. Many free blocks can be found quickly.

4. Counting - store the address of the first free block and the number of contiguous free blocks following it, e.g. (2,2), (5,1), (8,2). Short list when free space is contiguous.

5. Free list in blocks (pointer blocks) - Tanenbaum: a block holds as many free block numbers as fit (e.g. 255 in a 1 KB block with 4-byte numbers); when it empties, the next list block is read.

Bit map needs more memory than the list on a nearly full disk, but is better on a nearly empty disk.