Chapter 1
Storage Hierarchy & Caching
Effective Access Time - cached memory
F 1.1
EAT = h × Tcache
+ (1 − h) × Tmain
Variables
h hit ratio (fraction of accesses
found in cache, 0 ≤ h ≤ 1)
Tcache time to access
the cache
Tmain time to access
main memory (on a miss)
Worked Example
Cache access = 5 ns, Main memory access = 100 ns, Hit ratio = 0.90
1.EAT = 0.90 × 5 + (1 − 0.90) × 100
2.EAT = 4.5 + 10
=EAT = 14.5 ns
This is the general caching principle. The same structure applies to
TLB (Ch 8) and virtual memory (Ch 9).
Chapter 5
CPU Scheduling
Turnaround Time
F 5.1
TAT = Finish Time − Arrival Time
Variables
TAT total time from submission to
completion
Finish Time time when process
completes execution
Arrival Time time when process
entered the system
Worked Example
Process P1 arrives at t=0, finishes at t=24.
1.TAT = 24 − 0
=TAT = 24 ms
Waiting Time
F 5.2
WT = TAT − Burst Time
≡ Finish Time − Arrival Time − Burst Time
Variables
WT time spent in the ready queue
(not executing)
Burst Time CPU time the process
actually needs
Worked Example - FCFS with P1=24ms, P2=3ms, P3=3ms (arrive at t=0)
Gantt: P1[0 - 24] → P2[24 - 27] → P3[27 - 30]
P1WT = 24 − 0 − 24 = 0 ms
P2WT = 27 − 0 − 3 = 24 ms
P3WT = 30 − 0 − 3 = 27 ms
AvgAvg WT = (0 + 24 + 27) / 3 = 17 ms
Average Waiting / Turnaround Time
F 5.3
Avg WT =
Σ WTi
n
Avg TAT =
Σ TATi
n
Variables
n total number of processes
Σ sum over all n processes
Worked Example - SJF (non-preemptive): P1=6ms, P2=8ms, P3=7ms,
P4=3ms (all arrive t=0)
SJF order: P4[0 - 3] → P1[3 - 9] → P3[9 - 16] → P2[16 - 24]
P1WT = 9 − 0 − 6 = 3 ms
P2WT = 24 − 0 − 8 = 16 ms
P3WT = 16 − 0 − 7 = 9 ms
P4WT = 3 − 0 − 3 = 0 ms
AvgAvg WT = (3 + 16 + 9 + 0) / 4 = 7 ms
SJF gives minimum average waiting time for a given set of processes
- it is provably optimal for non-preemptive scheduling.
Exponential Averaging - next CPU burst prediction
F 5.4
τn+1 = α × tn
+ (1 − α) × τn
Variables
τn+1 predicted
length of next CPU burst
tn actual length of the
most recent CPU burst
τn previous
prediction
α weighting factor (0 ≤
α ≤ 1), typically 0.5
Worked Example - α = 0.5, starting prediction τ1
= 10 ms
Actual bursts observed: t₁ = 6, t₂ = 4, t₃ = 6
1.τ₂ = 0.5 × 6 + 0.5 × 10 = 3 + 5 = 8 ms
2.τ₃ = 0.5 × 4 + 0.5 × 8 = 2 + 4 = 6 ms
3.τ₄ = 0.5 × 6 + 0.5 × 6 = 3 + 3 = 6 ms
NoteEach older burst has weight (1−α)ʲ - exponentially
decreasing influence
Special cases: α = 0 → prediction never changes (τn+1
= τ0). α = 1 → only the last actual burst
matters (τn+1 = tn).
Round Robin - maximum wait before first run
F 5.5
Max wait ≤ (n − 1) × q
Variables
n number of processes in the ready
queue
q time quantum (time slice)
Worked Example - n=3 processes, q=4 ms
P1=24ms, P2=3ms, P3=3ms. Gantt: P1[0 - 4] P2[4 - 7] P3[7 - 10]
P1[10 - 14] P1[14 - 18] P1[18 - 22] P1[22 - 26] P1[26 - 30]
MaxMax wait = (3 − 1) × 4 = 8 ms
P1WT = (30 − 0 − 24) = 6 ms
P2WT = (7 − 0 − 3) = 4 ms
P3WT = (10 − 0 − 3) = 7 ms
AvgAvg WT = (6 + 4 + 7) / 3 = 5.67 ms
q must be large relative to context-switch overhead. Rule of thumb:
80% of CPU bursts should be shorter than q.
Chapter 8
Main Memory - Address Translation
Logical Address Space Size
F 8.1
Logical Address Space = 2m bytes
where m = bits
in logical address
Variables
m total bits in logical address =
page bits + offset bits
Page bits = log₂(number of pages)
Offset bits = log₂(page size in
bytes)
Worked Example
128 pages, page size = 1 KB (= 2¹⁰ bytes). Physical memory = 256
frames.
1.Offset bits = log₂(1024) = 10 bits
2.Page bits = log₂(128) = 7 bits
3.Logical address bits = 7 + 10 = 17 bits
4.Frame bits = log₂(256) = 8 bits
5.Physical address bits = 8 + 10 = 18 bits
=Logical = 17 bits (128 KB space) | Physical = 18 bits (256
KB)
Paging - Logical to Physical Address
F 8.2
Logical address LA:
p = ⌊LAPage Size⌋ d = LA
mod Page Size
Physical address = Frame(p) × Page Size + d
Physical address = Frame(p) × Page Size + d
Variables
p page number (index into page
table)
d page offset (position within the
page)
Frame(p) frame number from page
table lookup
Worked Example
Page size = 2 KB = 2048 bytes. Page table: page 0→frame 1, page
1→frame 4, page 2→frame 3. Find physical address of logical
address LA = 2524.
1.p = ⌊2524 / 2048⌋ = 1 (page 1)
2.d = 2524 mod 2048 = 476
3.Frame(1) = 4 (from page table)
4.Physical = 4 × 2048 + 476 = 8192 + 476
=Physical address = 8668
Chapter 8
Segmentation - Address Translation
Segmentation - Physical Address & Validity Check
F 8.3
Logical: <s,
d>
If d ≥ limits → TRAP (segment violation)
Physical = bases + d
If d ≥ limits → TRAP (segment violation)
Physical = bases + d
Variables
s segment number
d offset within the segment
bases starting physical
address of segment s
limits length of segment
s - offset must be < limit
Worked Example
Segment table: seg 0 → base=1000, limit=400 | seg 1 → base=2500,
limit=100 | seg 2 → base=90, limit=500
⟨0,350⟩350 < 400 ✓ → Physical = 1000 + 350 = 1350
⟨1,80⟩80 < 100 ✓ → Physical = 2500 + 80 = 2580
⟨2,600⟩600 ≥ 500 ✗ → TRAP - illegal address
RuleOffset d must always be strictly less than segment
limit
Segmentation suffers from external fragmentation (variable segment
sizes leave gaps). Paging suffers from internal fragmentation (last
page may be only partially filled).
Chapter 8
Paging - Bit Calculations
Number of Pages & Frames
F 8.4
Pages =
Logical Memory Size
Page Size
Frames =
Physical Memory Size
Frame Size
Variables
Page Size = Frame Size always equal
- defined by hardware
Page bits = log₂(Pages)
Offset bits = log₂(Page Size)
Frame bits = log₂(Frames)
Worked Example
Physical memory = 256 KB, Logical memory (per process) = 64 KB,
Page size = 2 KB
a.Pages = 64 KB / 2 KB = 32 pages
b.Frames = 256 KB / 2 KB = 128 frames
c.Page bits = log₂(32) = 5 bits
d.Offset bits = log₂(2048) = 11 bits
e.Frame bits = log₂(128) = 7 bits
=Logical addr = 16 bits | Physical addr = 18 bits
Contiguous Allocation - Logical to Physical (Address
Mapping)
F 8.5
Physical = Base + Logical
(if Logical <
Limit)
Variables
Base starting physical address of
the process partition
Limit size of the process partition
- logical address must be < Limit
Worked Example
Process has Base = 5000, Limit = 2000. Translate logical address
1500.
1.Check: 1500 < 2000 ✓ (valid)
2.Physical = 5000 + 1500
=Physical address = 6500
Chapter 8
TLB & Effective Access Time
Effective Access Time with TLB
F 8.6
EAT = h × (c + m) +
(1 − h) × (c + 2m)
= c + m + (1 − h) × m [simplified]
Variables
h TLB hit ratio (fraction of page
lookups found in TLB)
c TLB access time
m main memory access time
c + m TLB hit path: TLB lookup +
one memory access
c + 2m TLB miss path: TLB lookup +
page table access + data access
Worked Example A - from course slides (Ch 8)
TLB access c = 20 ns, Memory access m = 100 ns, Hit ratio h = 0.80
Hit0.80 × (20 + 100) = 0.80 × 120 = 96 ns
Miss0.20 × (20 + 200) = 0.20 × 220 = 44 ns
=EAT = 96 + 44 = 140 ns
Worked Example B - from course quiz (Ch 8)
TLB access c = 10 ns, Memory access m = 50 ns, Hit ratio h = 0.90
Hit0.90 × (10 + 50) = 0.90 × 60 = 54 ns
Miss0.10 × (10 + 100) = 0.10 × 110 = 11 ns
=EAT = 54 + 11 = 65 ns
Worked Example C - from quiz 4 answer
TLB access c = 15 ns, Memory access m = 100 ns, Hit ratio h = 0.90
Hit0.90 × (15 + 100) = 0.90 × 115 = 103.5 ns
Miss0.10 × (15 + 200) = 0.10 × 215 = 21.5 ns
=EAT = 103.5 + 21.5 = 125 ns
On a TLB HIT: only one memory access needed (for the actual data).
On a TLB MISS: two memory accesses needed (page table + data). The
TLB is a cache for the page table.
Bitmap Free Space - First Free Block Number
F 8.7
First free block = (bits/word) × (zero-value words) + offset
of first 1-bit
Variables
bits/word number of bits per word
(e.g. 8, 16, 32)
zero-value words number of words
where ALL bits = 0 (all allocated)
offset bit position of first 1-bit
in the first non-zero word
bit = 1 block is FREE |
bit = 0 block is ALLOCATED
Worked Example - from Ch 12 slides
8 bits per word. Bitmap: Word 0 = 00000000 | Word 1 = 00000000 |
Word 2 = 00010000
1.Zero-value words before first free = 2 (words 0 and 1)
2.Word 2 = 00010000 → first 1-bit is at offset 3 (counting from
left, 0-indexed)
3.First free block = 8 × 2 + 3
=First free block = block 19
Chapter 9
Virtual Memory & Demand Paging
Effective Access Time - Demand Paging
F 9.1
EAT = (1 − p) × ma
+ p × page fault service time
Variables
p page fault rate (0 ≤ p ≤
1). p=0 → no faults; p=1 → every access faults
ma memory access time (when page is
in RAM)
page fault service time overhead +
swap page out + swap page in + restart
Worked Example - from course slides (Ch 9)
Memory access time ma = 200 ns, Page fault service time = 8 ms =
8,000,000 ns
1.EAT = (1 − p) × 200 + p × 8,000,000
2.EAT = 200 − 200p + 8,000,000p
3.EAT = 200 + 7,999,800p ns
If p=0.001EAT = 200 + 7,999.8 ≈ 8,200 ns = 8.2 µs (41× slowdown)
Even a very small page fault rate (p = 0.001 = 0.1%) slows the
system dramatically. This is why minimizing page faults is critical.
Contiguous Allocation - Disk Block Address Mapping
F 9.2
Q =
LA
Block Size
R = LA mod Block Size
Disk block = Start Address + Q Displacement = R
Disk block = Start Address + Q Displacement = R
Variables
LA logical address (file offset in
bytes)
Q block number within the file
(quotient)
R byte offset within that block
(remainder)
Start Address first disk block
number of the file
Worked Example - from Ch 12 slides
Block size = 1024 bytes. File A starts at disk block 6. Find disk
block for file offset LA = 2500.
1.Q = ⌊2500 / 1024⌋ = 2
2.R = 2500 mod 1024 = 452
3.Disk block = 6 + 2 = 8
=Block 8, displacement 452 bytes into the block
Linked Allocation - Logical to Physical Block
F 9.3
Q =
LA
Block Size − Pointer Size
R = LA mod (Block Size −
Pointer Size)
Displacement into block = R + Pointer Size
Displacement into block = R + Pointer Size
Variables
Pointer Size bytes used by the
next-block pointer stored in each block
Q follow the linked chain Q blocks
from the start
R offset within that Qth block
(after the pointer)
Worked Example
Block size = 512 bytes, Pointer size = 4 bytes. Find block for LA
= 600.
1.Effective data per block = 512 − 4 = 508 bytes
2.Q = ⌊600 / 508⌋ = 1 (follow 1 pointer link)
3.R = 600 mod 508 = 92
4.Displacement = 92 + 4 = 96 bytes into the block
=Go to 1st linked block, read at offset 96
Linked allocation has no external fragmentation but cannot support
efficient direct/random access - must traverse the chain from the
beginning each time.
Indexed Allocation - Logical to Physical Block
F 9.4
Q =
LA
Block Size
R = LA mod Block Size
Disk block = index_block[Q] Displacement = R
Disk block = index_block[Q] Displacement = R
Variables
index_block[Q] Qth entry in the
file's index block = actual disk block number
R byte offset within that disk
block
Worked Example
Block size = 512 bytes. Index block contains: [14, 22, 9, 35, 8].
Find location for LA = 600.
1.Q = ⌊600 / 512⌋ = 1
2.R = 600 mod 512 = 88
3.index_block[1] = 22 → go to disk block 22
=Disk block 22, displacement 88 bytes
Indexed allocation supports efficient random access (unlike linked).
UNIX inodes use a combined scheme: 12 direct pointers +
single/double/triple indirect blocks for large files.
Chapter 12
File System - Free Space Bitmap
Bitmap Size Required for a Disk
F 12.1
Number of blocks =
Disk Size
Block Size
Bitmap size (bytes) = Number of blocks 8
Bitmap size (bytes) = Number of blocks 8
Variables
1 bit represents 1 disk block (1 =
free, 0 = allocated)
8 bits per byte
Worked Example - from Ch 12 slides
Disk size = 1 TB = 1,099,511,627,776 bytes. Block size = 4 KB =
4096 bytes.
1.Blocks = 1,099,511,627,776 / 4096 = 268,435,456 blocks
2.Bitmap bytes = 268,435,456 / 8 = 33,554,432 bytes
=Bitmap size = 32 MB
Compared to disk size (1 TB), the 32 MB bitmap is tiny - about
0.003% overhead. The bitmap must be kept in memory for efficient
free-block searches.