CS330 · Chapter 12 · Annotated SlidesFile-System Implementation
Original
Overview

File-System Implementation

On-disk and in-memory file-system structures, the allocation methods (contiguous, linked, FAT, indexed and the UNIX combined scheme), and free-space management with bit vectors, linked lists, grouping and counting.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 37 slides
  1. 1 Slide 1
  2. 2 Outline of this lecture
  3. 3 Objectives
  4. 4 File System Implementation
  5. 5 on-disk File-System Implementation
  6. 6 On-disk File-System Implementation (Cont.)
  7. 7 In-Memory File System Structures
  8. 8 In-Memory File System Structures
  9. 9 Allocation Methods
  10. 10 Allocation Methods - Contiguous
  11. 11 Example
  12. 12 Contiguous Allocation
  13. 13 Example
  14. 14 Allocation Methods – Linked
  15. 15 Linked Allocation
  16. 16 Linked Allocation
  17. 17 Linked Allocation (Cont.)
  18. 18 Linked Allocation
  19. 19 Allocation Methods – Linked (Cont.)
  20. 20 File-Allocation Table
  21. 21 Allocation Methods - Indexed
  22. 22 Example of Indexed Allocation
  23. 23 Indexed Allocation (Cont.)
  24. 24 Combined Scheme: UNIX UFS
  25. 25 Free Space Management
  26. 26 Free-Space Management: 1) Bit Vector
  27. 27 Free-Space Management: 1) Bit Vector (Cont.)
  28. 28 Example:
  29. 29 Free-Space Management: 1) Bit Vector (Cont.)
  30. 30 Given the following: • Block Size: 4 KB=4096 bytes • Disk Size: 1 TB=1024=1,099,511,627,776 bytes Calculation:
  31. 31 Free-Space Management: 2) Linked List
  32. 32 Free-Space Management: 2) Linked List(cont.)
  33. 33 Free-Space Management: 3) Grouping
  34. 34 Free-Space Management: 3) Grouping
  35. 35 Free-Space Management: 4) Counting
  36. 36 Free-Space Management: 4) Counting
  37. 37 Slide 37
Slide 1 / 37

Slide 1

Slide 1: Slide 1
Slide 2 / 37

Outline of this lecture

Slide 2: Outline of this lecture
Slide 3 / 37

Objectives

Slide 3: Objectives
Slide 4 / 37

File System Implementation

Slide 4: File System Implementation
Slide 5 / 37

on-disk File-System Implementation

Slide 5: on-disk File-System Implementation
Slide 6 / 37

On-disk File-System Implementation (Cont.)

Slide 6: On-disk File-System Implementation (Cont.)
Slide 7 / 37

In-Memory File System Structures

Slide 7: In-Memory File System Structures
Slide 8 / 37

In-Memory File System Structures

Slide 8: In-Memory File System Structures
Slide 9 / 37

Allocation Methods

Slide 9: Allocation Methods
Slide 10 / 37

Allocation Methods - Contiguous

Slide 10: Allocation Methods - Contiguous

Notes

  1. Contiguous: each file occupies consecutive blocks (start, length). Fast sequential and direct access; external fragmentation, hard to grow.

Exam angle

PredictionQ1

Which allocation method suffers from external fragmentation?

Slide 11 / 37

Example

Slide 11: Example
Slide 12 / 37

Contiguous Allocation

Slide 12: Contiguous Allocation
Slide 13 / 37

Example

Slide 13: Example
Slide 14 / 37

Allocation Methods – Linked

Slide 14: Allocation Methods – Linked

Notes

  1. Linked: each block points to the next. No external fragmentation, but direct access is slow and a lost pointer breaks the chain.

Exam angle

PredictionQ1

Linked allocation supports efficient direct access.

Slide 15 / 37

Linked Allocation

Slide 15: Linked Allocation
Slide 16 / 37

Linked Allocation

Slide 16: Linked Allocation
Slide 17 / 37

Linked Allocation (Cont.)

Slide 17: Linked Allocation (Cont.)
Slide 18 / 37

Linked Allocation

Slide 18: Linked Allocation
Slide 19 / 37

Allocation Methods – Linked (Cont.)

Slide 19: Allocation Methods – Linked (Cont.)
Slide 20 / 37

File-Allocation Table

Slide 20: File-Allocation Table

Notes

  1. FAT: the next-block pointers live in a table at the start of the volume (cached), so direct access is faster.

Slide 21 / 37

Allocation Methods - Indexed

Slide 21: Allocation Methods - Indexed

Notes

  1. Indexed: each file has an index block of pointers. Direct access without external fragmentation; costs the index block.

Slide 22 / 37

Example of Indexed Allocation

Slide 22: Example of Indexed Allocation
Slide 23 / 37

Indexed Allocation (Cont.)

Slide 23: Indexed Allocation (Cont.)
Slide 24 / 37

Combined Scheme: UNIX UFS

Slide 24: Combined Scheme: UNIX UFS

Notes

  1. UNIX inode: 12 direct pointers + single, double and triple indirect blocks.

Exam angle

PredictionQ1

4 KB blocks and 4-byte pointers. How much data can one single-indirect block address?

Compare with the model answer

4096 / 4 = 1024 pointers × 4 KB = 4 MB.

Slide 25 / 37

Free Space Management

Slide 25: Free Space Management
Slide 26 / 37

Free-Space Management: 1) Bit Vector

Slide 26: Free-Space Management: 1) Bit Vector

Notes

  1. Bit vector: one bit per block (1 = free in the slides). Easy to find contiguous space; the map takes disk-size / block-size bits.

Exam angle

PredictionQ1

A 1 TB disk with 4 KB blocks needs a bit map of:

Slide 27 / 37

Free-Space Management: 1) Bit Vector (Cont.)

Slide 27: Free-Space Management: 1) Bit Vector (Cont.)
Slide 28 / 37

Example:

Slide 28: Example:
Slide 29 / 37

Free-Space Management: 1) Bit Vector (Cont.)

Slide 29: Free-Space Management: 1) Bit Vector (Cont.)
Slide 30 / 37

Given the following: • Block Size: 4 KB=4096 bytes • Disk Size: 1 TB=1024=1,099,511,627,776 bytes Calculation:

Slide 30: Given the following: • Block Size: 4 KB=4096 bytes • Disk Size: 1 TB=1024=1,099,511,627,776 bytes Calculation:
Slide 31 / 37

Free-Space Management: 2) Linked List

Slide 31: Free-Space Management: 2) Linked List
Slide 32 / 37

Free-Space Management: 2) Linked List(cont.)

Slide 32: Free-Space Management: 2) Linked List(cont.)
Slide 33 / 37

Free-Space Management: 3) Grouping

Slide 33: Free-Space Management: 3) Grouping
Slide 34 / 37

Free-Space Management: 3) Grouping

Slide 34: Free-Space Management: 3) Grouping
Slide 35 / 37

Free-Space Management: 4) Counting

Slide 35: Free-Space Management: 4) Counting
Slide 36 / 37

Free-Space Management: 4) Counting

Slide 36: Free-Space Management: 4) Counting
Slide 37 / 37

Slide 37

Slide 37: Slide 37