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

Access time

5–10 ms

Moving parts

Yes

Typical speed

100–200 MB/s

Cost per GB

Low

Disk scheduling

Critical

Electronic

SSD

Flash memory chips, no motion

Access time

≈ 0.1 ms

Moving parts

None

Typical speed

500–7,000 MB/s

Cost per GB

Higher

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

Boot

MBR · GPT

Partition 1

C: · NTFS

Partition 2

D: · data

Free

unallocated

MBR vs GPT

FeatureMBRGPT
Max disk size2 TB9.4 ZB
Partitions4 primary128
FirmwareBIOSUEFI
Backup headerNoYes

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

98

183

37

122

14

124

65

67

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

FCFS

640 · highest

SSTF

236

SCAN

236

C-SCAN

382

LOOK

208 · lowest

C-LOOK

322

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

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

A: start 1, length 4

+ Fast sequential and direct access

− External fragmentation; hard to grow

Linked

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

A: 9 → 2 → 14 → 6 → end

+ No external fragmentation

− Sequential access only; a pointer in every block

Indexed

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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)

0

0

1

1

1

1

0

0

1

1

1

1

1

1

0

0

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

MethodAccessFragmentationOverheadSeen in
ContiguousFast, directExternalNoneCD-ROM (ISO 9660)
LinkedSequential onlyNonePointer per blockFAT (USB drives)
IndexedFast, directNoneIndex block per fileUnix 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

Directory

cat

bo

a

test

data

mail

All files share one directory. − Names must be unique; no grouping; messy with many users.

Two-level

Master directory

User 1

User 2

User 3

cat

a

a

test

data

mail

Each user gets a directory. + The same name (“a”) can exist for different users. − Hard to share files.

The modern standard

Tree-structured directory

/

bin

home

usr

ls

alice

bob

lib

notes.txt

os.pdf

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

root

dict

spell

words

list

count

link

Files can be shared through links, but no cycles are allowed, so a search always ends. − Deleting needs a reference count.

General graph

root

dict

spell

words

list

count

cycle

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

a.txt

→

b.c

→

os.pdf

Lookup checks entries one by one

+ Simple to program

− Search is O(n): slow for big directories

Hash table

0

notes

1

—

2

a.txt → os.pdf

3

b.c

+ 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

A1

A3

A2

A4

2+ disks · survives 0 failures

+ Fastest, full capacity

RAID 1

Mirroring

A1

A2

A1

A2

2+ disks · survives 1 failure

− Only 50% usable space

RAID 5

Distributed parity

A1

B1

Cp

A2

Bp

C1

Ap

B2

C2

3+ disks · survives 1 failure

+ Good balance of speed and safety

RAID 10

Mirror + stripe

A1

A3

A1

A3

A2

A4

A2

A4

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

C:\

D:\

E:\

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

/bin

/etc

/home

/dev

/mnt

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

← → or click to move · F fullscreen · N speaker notes