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.