Operating Systems · Group Presentation
Directory & Disk Structure
How an operating system lays out, finds and protects data on a disk
Presented by
Muhammad Kaleem
Muhammad Faheem
Ahmad Mehmood
Hanzala Amjad
Muhammad Saran
Roadmap
Five parts, one storage story
01
Disk Structure
Muhammad Kaleem
02
Disk Scheduling & Performance
Muhammad Faheem
03
Allocation & Free-Space Management
Ahmad Mehmood
04
Directory Structure
Hanzala Amjad
05
Directory Implementation & Reliability
Muhammad Saran
01
Part 01
Disk Structure
Presented by Muhammad Kaleem
Platters, tracks & sectors
HDD vs SSD
Logical blocks
Partitions: MBR & GPT
Boot process
Physical structure
Inside a hard disk
Sector
Track
Spindle
Read/write head
Platter
Magnetic disk; data on both surfaces
Track
One concentric ring on a surface
Sector
Smallest unit on a track: 512 B or 4 KB
Cylinder
The same track number on every platter
R/W head
One per surface, all moved together by the arm
Capacity = cylinders × heads × sectors/track × bytes/sector
Storage devices
Hard disk vs solid-state drive
Mechanical
HDD
Spinning platters and a moving arm
Typical speed
100–200 MB/s
Electronic
SSD
Flash memory chips, no motion
Typical speed
500–7,000 MB/s
Disk scheduling
Matters less
Logical structure
How a disk is organised logically
LBA 0
The OS sees one flat array of logical blocks
LBA n−1
MBR vs GPT
| Feature | MBR | GPT |
| Max disk size | 2 TB | 9.4 ZB |
| Partitions | 4 primary | 128 |
| Firmware | BIOS | UEFI |
| Backup header | No | Yes |
Boot sequence
1
Power on: firmware (BIOS/UEFI) runs self-test
2
Firmware reads the boot block on the disk
3
Bootstrap loader loads the OS kernel
4
Kernel mounts the root file system
02
Part 02
Disk Scheduling & Performance
Presented by Muhammad Faheem
Seek, latency & transfer
FCFS · SSTF
SCAN · C-SCAN
LOOK · C-LOOK
Worked example
Disk performance
Three delays in every disk access
Access time
=
Seek
+
Rotational latency
+
Transfer
3–10 ms
Seek time · largest
Move the arm to the correct track. This is the cost scheduling tries to cut.
≈ 4.2 ms
Rotational latency
Wait for the sector to spin under the head: on average half a turn at 7,200 RPM.
< 1 ms
Transfer time
Read or write the bits as they pass under the head. Small next to the others.
Disk scheduling attacks seek time: reorder the waiting requests so the arm travels less.
Scheduling algorithms
Six classic scheduling algorithms
FCFS
First Come, First Served
Serves requests in the order they arrive.
+ Fair, simple − Wild arm swings
SSTF
Shortest Seek Time First
Always picks the request closest to the head.
+ Low seek − Far requests can starve
SCAN
The elevator algorithm
Sweeps to one end of the disk, then reverses.
+ No starvation − Edges wait longer
C-SCAN
Circular SCAN
Sweeps one way only, then jumps back to the start.
+ More uniform waiting time
LOOK
Smarter SCAN
Like SCAN, but turns at the last request, not the disk edge.
+ Skips empty travel
C-LOOK
Smarter C-SCAN
Like C-SCAN, but jumps from the last request to the first.
+ Uniform and efficient
Worked example
Worked example: SSTF
Request queue
Service order · head starts at 53
53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
236
cylinders of head movement
FCFS needs 640 for the same queue
0
50
100
150
199
53
65
67
37
14
98
122
124
183
Results
Total head movement, compared
Same queue (98, 183, 37, 122, 14, 124, 65, 67), head at 53, cylinders 0–199
SCAN and LOOK move toward 0 first; C-SCAN and C-LOOK move toward 199 and count the return jump.
03
Part 03
Allocation & Free-Space Management
Presented by Ahmad Mehmood
Contiguous
Linked & FAT
Indexed & inodes
Bit vector
Grouping & counting
Allocation methods
Three ways to place a file on disk
Contiguous
A: start 1, length 4
+ Fast sequential and direct access
− External fragmentation; hard to grow
Linked
A: 9 → 2 → 14 → 6 → end
+ No external fragmentation
− Sequential access only; a pointer in every block
Indexed
Index block 5 → 0, 7, 11, 13
+ Fast direct access, no fragmentation
− Extra index block per file
Free-space management
Tracking free space
Bit vector (bitmap)
1 = free, 0 = allocated · one bit per block, so finding a free block is a fast scan
Linked list
Each free block points to the next free block. No extra space, but slow to walk.
head → 2 → 3 → 4 → 5 → 8 …
Grouping
The first free block stores the addresses of the next n free blocks.
block 2: [3, 4, 5, 8] → next group
Counting
Store runs as (start, count) instead of listing every block.
(2, 4) (8, 6)
Comparison
Allocation methods side by side
| Method | Access | Fragmentation | Overhead | Seen in |
| Contiguous | Fast, direct | External | None | CD-ROM (ISO 9660) |
| Linked | Sequential only | None | Pointer per block | FAT (USB drives) |
| Indexed | Fast, direct | None | Index block per file | Unix inodes |
Modern systems mix them: ext4 uses extents — contiguous runs of blocks tracked by an index tree.
04
Part 04
Directory Structure
Presented by Hanzala Amjad
Directory operations
Single-level
Two-level
Tree-structured
Acyclic & general graph
Absolute vs relative paths
Directory basics
What a directory does
A directory is a symbol table: it maps each file name to its file control block — location, size, owner and permissions.
Search
Find the entry for a file name
Create
Add an entry for a new file
Delete
Remove an entry, free its space
List
Show files and their attributes
Rename
Change a file’s name or place
Traverse
Visit every entry, e.g. for backup
Early designs
Single-level and two-level directories
Single-level
All files share one directory. − Names must be unique; no grouping; messy with many users.
Two-level
Each user gets a directory. + The same name (“a”) can exist for different users. − Hard to share files.
The modern standard
Tree-structured directory
Absolute path
/home/alice/os.pdf
Starts at the root. Means the same thing from anywhere.
Relative path
Current directory: /home
alice/os.pdf
Starts at the current working directory.
Sharing files
Acyclic and general graphs
Acyclic graph
Files can be shared through links, but no cycles are allowed, so a search always ends. − Deleting needs a reference count.
General graph
Links may point back up and form cycles. − Searches must avoid looping forever; garbage collection reclaims unreachable files.
05
Part 05
Directory Implementation & Reliability
Presented by Muhammad Saran
Linear list vs hash table
Mounting
RAID 0 · 1 · 5 · 10
NTFS, FAT32 & ext4
Conclusion
Implementation
Implementing directories and mounting
Linear list
Lookup checks entries one by one
+ Simple to program
− Search is O(n): slow for big directories
Hash table
+ O(1) average lookup
− Collisions (bucket 2); fixed table size
Mounting
/mnt/usb
↑ mount
USB drive · FAT32
+ Attaches a file system at a mount point so it joins the tree
Windows shows it as a drive letter, e.g. E:\
Reliability
RAID: many disks, one reliable volume
Each dark column is a disk. Data blocks are labelled A1, B1 …; parity blocks end in “p”.
RAID 0
Striping
2+ disks · survives 0 failures
+ Fastest, full capacity
RAID 1
Mirroring
2+ disks · survives 1 failure
− Only 50% usable space
RAID 5
Distributed parity
3+ disks · survives 1 failure
+ Good balance of speed and safety
RAID 10
Mirror + stripe
4+ disks · 1 per mirror pair
+ Speed and redundancy
Real-world examples
Real systems: Windows and Linux
Windows
One tree per drive letter
C:\Users\Student\os.pdf
NTFS
Journaling, permissions, very large files
FAT32
Simple and portable; 4 GB file limit
exFAT
Flash drives without the 4 GB limit
Linux
One tree from the root /
/home/student/os.pdf
ext4
Journaling, extents, files up to 16 TB
XFS
High performance for large files
Btrfs
Snapshots and data checksums
Conclusion
Key takeaways
01
The OS sees a disk as one flat array of logical blocks.
Muhammad Kaleem
02
Smart scheduling cut head movement from 640 to 208 cylinders.
Muhammad Faheem
03
Allocation methods trade access speed against fragmentation.
Ahmad Mehmood
04
Directories grew from one flat list into trees and graphs.
Hanzala Amjad
05
Hashing, mounting and RAID make storage fast and reliable.
Muhammad Saran
Directory & Disk Structure
Thank you
Questions?
01
Muhammad Kaleem · Disk Structure
02
Muhammad Faheem · Disk Scheduling & Performance
03
Ahmad Mehmood · Allocation & Free-Space Management
04
Hanzala Amjad · Directory Structure
05
Muhammad Saran · Directory Implementation & Reliability