📌 Chapter 1 - Introduction & Architecture
OS Roles
  • Resource Allocator - manages CPU, mem, I/O; decides conflicts
  • Control Program - prevents errors & improper use
  • Kernel = one program running at all times
  • Kernel mode bit = 0 | User mode bit = 1
  • Privileged instructions → kernel mode only
Interrupt Mechanics
  • Interrupt vector = table of ISR addresses
  • Trap/Exception = software-generated interrupt (error or syscall)
  • OS saves state → runs ISR → restores state & resumes
  • Polling vs Vectored interrupt detection
  • DMA: one interrupt per block, not per byte
Storage Hierarchy
Level Size Speed Volatile?
Registers ~8B 0.3 ns Yes
Cache MB 1 ns Yes
RAM GB 100 ns Yes
SSD TB ~100 µs No
HDD TB ~8 ms No
Faster ↑ = Smaller + More Expensive + Volatile
Multiprocessor Types
  • Asymmetric - master assigns work to slaves (large systems)
  • Symmetric (SMP) - all CPUs equal, self-scheduling (most common)
Multiprogramming vs Timesharing
  • Multiprogramming - keeps CPU busy by switching on I/O waits
  • Timesharing - rapid switching so users can interact (interactive)
Bootstrap / Boot Sequence
  • Stored in ROM/EPROM (firmware)
  • Order: BIOS → Boot Loader → Kernel → Apps
  • Initializes CPU registers, device controllers, memory
Timer
  • Prevents CPU monopolization - decrements counter → interrupt at 0
  • Set before scheduling each process
Dual-Mode Operation
User mode (bit=1) → syscall → Kernel mode (bit=0) ← return ←
  • Mode bit provided by hardware
  • Privileged: set timer, access I/O, manage interrupts, halt CPU
  • Syscall changes mode to kernel; return resets to user
🏗 Chapter 2 - OS Structure & Services
OS Structures Compared
Model Key Trait Pro Con
Monolithic All in kernel space Fast Hard to maintain
Layered Abstraction levels Easy debug Slow (many calls)
Microkernel Min kernel + user services Secure, portable IPC overhead
Modular Loadable modules Flexible -
Hybrid Mix of above Performance Complexity
System Calls
  • Interface between running program and OS
  • Accessed via API (Win32 / POSIX / Java)
  • Each call has an index number in syscall table
6 Categories:
  • Process fork, exec, exit, wait
  • File open, read, write, close
  • Device request, release, read, write
  • Info get/set time, attributes
  • Protection get/set permissions
  • Comms send, receive, create connection
Parameter Passing Methods
  • Registers - simplest, limited by register count
  • Memory block/table - address passed in register (Linux, Solaris)
  • Stack - pushed by program, popped by OS
Key Distinctions
  • printf() = library call (NOT a syscall)
  • write() = actual syscall beneath printf
  • POSIX API = Unix/Linux/macOS system interface
⚙ Chapter 3 - Processes
Process Memory Layout
  • Text - program code (read-only)
  • Data - global/static variables (initialized)
  • Heap - dynamic allocation (malloc), grows ↑
  • Stack - local vars, return addresses, params, grows ↓
Stack ↓ .............. Heap ↑ Data section | Text section
Process States
New → Ready → Running → Waiting → Ready ↓ Terminated
  • New being created
  • Ready waiting for CPU
  • Running executing on CPU
  • Waiting blocked on I/O/event
  • Terminated done
  • WAITING → RUNNING is NOT a valid transition!
PCB Contents
  • Process state, PID
  • Program counter (PC)
  • CPU registers
  • Scheduling info (priority, queue pointers)
  • Memory-management info
  • Accounting info (CPU used, time limits)
  • I/O status (open files, devices)
PCB saved/restored on every context switch
Schedulers
Scheduler Selects Frequency
Long-term (Job) Jobs → ready queue Very slow (mins)
Short-term (CPU) Ready → CPU Every few ms
Medium-term (Swap) Swap in/out Intermediate
  • I/O-bound - many short CPU bursts
  • CPU-bound - few long CPU bursts
  • Long-term controls degree of multiprogramming
fork() / exec() Rules
  • fork() returns 0 to child, child PID to parent, −1 on error
  • Child gets copy of parent's address space (independent)
  • Stack, Heap NOT shared - shared memory segments are
  • exec() replaces child's address space with new program
  • wait() prevents zombie; no wait() = zombie process
  • Parent dies without wait() = orphan process
n forks in loop = 2ⁿ total processes
IPC Models
Shared Memory
  • Faster (no kernel intervention)
  • User controls synchronization
  • Good for large data
  • Race condition risk
Message Passing
  • Easier to implement
  • OS manages transfers
  • Good for small data
  • Slower (syscall overhead)
🧵 Chapter 4 - Threads
Thread vs Process
Resource Shared?
Code section ✓ Shared
Data section ✓ Shared
OS resources (files) ✓ Shared
Program counter ✗ Own
Register set ✗ Own
Stack ✗ Own
Threading Models
Model Mapping Concurrency Examples
Many-to-One N user → 1 kernel No parallel Green Threads
One-to-One 1 user → 1 kernel True parallel Windows, Linux
Many-to-Many N user → M kernel Flexible Solaris <v9
Two-Level M:M + bound Best HP-UX, IRIX
  • Many-to-One: one blocking call blocks all threads
  • One-to-One: overhead from many kernel threads
Thread Benefits
  • Responsiveness - keep running if part is blocked
  • Resource Sharing - threads share process memory
  • Economy - faster to create/switch than processes
  • Scalability - exploit multicore CPUs
Parallelism Types:
  • Data parallelism - same op on different data subsets
  • Task parallelism - different ops on (possibly same) data
Solaris: creating a process is 30× slower than a thread
📅 Chapter 5 - CPU Scheduling
Scheduling Criteria
  • Maximize: CPU Utilization, Throughput
  • Minimize: Turnaround, Waiting, Response time
Turnaround Time = Finish - Arrival Waiting Time = Turnaround - Burst Response Time = First Response - Arrival
  • Preemptive: 2, 3 (running→ready, waiting→ready)
  • Non-preemptive: 1, 4 (running→waiting, terminates)
Algorithm Comparison
Algorithm Preempt? Starvation? Optimal?
FCFS No No No (convoy effect)
SJF (non-pre) No Yes Min avg WT*
SRTF (pre-SJF) Yes Yes Min avg WT
Priority Both Yes No
Round Robin Yes No No
MLQ/MLFQ Both Possible -
*SJF = optimal for minimum average waiting time given all arrivals at t=0
Round Robin Key Rules
  • Time quantum q → preempt, add to end of ready queue
  • q large → degenerates to FCFS
  • q small → high context switch overhead
  • Rule: 80% of CPU bursts should be < q
  • Higher avg turnaround than SJF but better response
n processes, quantum q: Max wait = (n-1) × q
Scheduling Calculation Template
Given: Process, Arrival(AT), Burst(BT), Priority Step 1: Draw Gantt chart using chosen algorithm Step 2: Waiting Time (WT) = Start Time - Arrival Time (or TAT - BT) Step 3: Turnaround (TAT) = Finish Time - Arrival Time Step 4: Avg WT = Σ WT / n Avg TAT = Σ TAT / n For Preemptive SJF (SRTF): at each arrival check if new process has shorter remaining time → preempt For Priority: smaller number = higher priority (unless stated otherwise)
Priority + Starvation
  • Starvation - low-priority process never runs
  • Aging - gradually increase priority of waiting processes
  • MLQ - separate queues per priority level; no movement between
  • MLFQ - processes can move between queues (aging-like)
🔒 Chapter 6 - Process Synchronization
Critical Section Requirements
  • Mutual Exclusion - only one process in CS at a time
  • Progress - if CS empty, a waiting process must be able to enter
  • Bounded Waiting - limit on how many times others enter before you
Structure:
entry section critical section exit section remainder section
Semaphore Operations
wait(S): S--; if S < 0 → block process signal(S): S++; if S ≤ 0 → wakeup one blocked process
  • Binary semaphore (mutex) - 0 or 1; provides mutual exclusion
  • Counting semaphore - unrestricted range; tracks resource count
  • Init to 1 → mutex lock
  • Init to 0 → ordering/synchronization (P1 signal → P2 runs)
  • Init to n → bounded buffer with n slots
Peterson's Solution
Shared: int turn; bool flag[2]; Process Pi: flag[i] = true; turn = j; while (flag[j] && turn == j); // busy wait /* critical section */ flag[i] = false;
  • Satisfies all 3 CS requirements for 2 processes
  • Busy waits - wastes CPU
Classic Problems
Bounded Buffer:
mutex=1, full=0, empty=n Producer: wait(empty)→wait(mutex)→add→signal(mutex)→signal(full) Consumer: wait(full)→wait(mutex)→remove→signal(mutex)→signal(empty)
Readers-Writers:
mutex=1, rw_mutex=1, read_count=0 1st reader: wait(rw_mutex) | last reader: signal(rw_mutex) Writer: wait(rw_mutex) → write → signal(rw_mutex)
Dining Philosophers:
chopstick[5] = {1,1,1,1,1} (semaphores) wait(chop[i]); wait(chop[(i+1)%5]); eat; signal(chop[i]); signal(chop[(i+1)%5]);
  • Naive approach → deadlock (all pick left chopstick)
Deadlock Conditions (ALL must hold)
  • Mutual Exclusion - resource held exclusively
  • Hold and Wait - holding one, waiting for another
  • No Preemption - resource not taken away
  • Circular Wait - P0→R0→P1→R1→…→Pn→P0
Mnemonic: Many Hungry Naughty Cats
Starvation - process never leaves semaphore queue (≠ deadlock)
Busy wait - spinning in while loop, wasting CPU
Monitors
  • High-level sync construct - only one process active inside at a time
  • No explicit locking needed
  • Condition variables: x.wait() suspends, x.signal() resumes one
  • x.signal() with no waiting = no effect (unlike semaphore)
Signal-and-wait: signaler waits for signaled to leave Signal-and-continue: signaled waits for signaler to leave
💾 Chapter 8 - Main Memory Management
Address Binding Stages
  • Compile time - absolute addresses; must recompile if location changes
  • Load time - relocatable code; bind when loaded
  • Execution time - bind at runtime; needs MMU hardware support
  • Logical addr (virtual) - generated by CPU
  • Physical addr - seen by memory unit
  • Logical = Physical at compile/load time; differ at execution time
Fragmentation
Type Where Solution
External Free space scattered Compaction / Paging / Segmentation
Internal Inside allocated block Smaller page size
Allocation Policies:
  • First-fit - first hole big enough (fastest)
  • Best-fit - smallest adequate hole (least waste, slow)
  • Worst-fit - largest hole (generally worst, largest leftover)
First-fit = fastest speed; Best-fit = best space utilization
Paging Address Translation
Logical Address: [Page# p | Offset d] m bits total: p = m-n bits, d = n bits Page size = 2ⁿ bytes → offset = n bits Num pages = logical space / page size = 2^p Physical Address = Frame# × page_size + offset = frame# concatenated with d
  • Page table stored in memory; PTBR points to it
  • Without TLB: 2 memory accesses per reference
  • Internal fragmentation possible; no external fragmentation
TLB & EAT Formulas
EAT = h×(c+m) + (1-h)×(c+2m) h = TLB hit ratio m = memory access time c = TLB access time TLB hit → access TLB + access memory = c + m TLB miss → access TLB + page table + memory = c + 2m
Example: h=0.9, c=10ns, m=100ns EAT = 0.9×(10+100) + 0.1×(10+100+100) = 0.9×110 + 0.1×210 = 99 + 21 = 120 ns
Segmentation
Logical Address: <segment#, offset> Segment Table entry: {base, limit} Physical Address = base[s] + d Valid if: d < limit[s]; else → trap (illegal access)
  • Matches programmer's view (functions, arrays, stack)
  • External fragmentation; no internal fragmentation
  • Can share segments between processes (same base+limit)
Paging Address Bits - Quick Calc
Given: N pages, page size P bytes → Logical bits = log₂(N) + log₂(P) → Offset bits = log₂(P) (= log₂(frame_size)) → Page# bits = log₂(N) Given: F frames, frame size P bytes → Physical bits = log₂(F) + log₂(P)
Example: 256 pages, 4KB page, 64 frames Page# = log₂(256) = 8 bits Offset = log₂(4096) = 12 bits Logical = 20 bits Physical = log₂(64)+12 = 6+12 = 18 bits
🌐 Chapter 9 - Virtual Memory
Demand Paging
  • Load pages only when needed (lazy swapper)
  • Valid-invalid bit: v=in memory, i=on disk
  • Access to i page → page fault trap
Page Fault Steps:
1. Check internal table (PCB) → valid reference? 2. No → abort; yes but not in memory → page it in 3. Get free frame 4. Swap page in from disk 5. Update page table (valid bit = v) 6. Restart the faulting instruction
EAT with Page Faults
EAT = (1-p) × ma + p × page_fault_service_time p = page fault rate (0 ≤ p ≤ 1) ma = memory access time If p=0 → EAT = ma (no faults) If p=1 → every access is a fault
Example: ma=200ns, fault_time=8ms=8,000,000ns EAT = (1-p)×200 + p×8,000,000 = 200 + 7,999,800p ns
Page Replacement Algorithms
Algorithm Replaces Belady's? Optimal?
FIFO Oldest loaded Yes ⚠ No
Optimal (OPT) Farthest future use No Yes
LRU Least recently used No Good approx
  • Belady's anomaly - more frames → MORE faults (FIFO only)
  • OPT is impossible in practice (needs future knowledge)
  • LRU ≈ OPT looking backward; good real-world choice
Thrashing
  • Process spends more time paging than executing
  • Symptoms: CPU util low, disk util high (~97%)
  • Cause: too many processes, insufficient frames
Solutions:
  • Decrease degree of multiprogramming
  • Add more physical RAM
  • Use working set model to allocate frames
CPU↓ + Disk↑ = Thrashing
Dirty Bit (Modify Bit)
  • Bit = 0 when page first loaded
  • Bit = 1 when page is written to
  • If dirty=0 when evicting → no write to disk needed
  • If dirty=1 → must write back (expensive)
  • Reduces number of disk writes significantly
Page Fault Counting - Steps
Reference string: 1 2 3 4 1 2 5 1 2 3 4 5 Frames: 3 FIFO: track load order → evict oldest LRU: track last-use time → evict least recently used OPT: look ahead → evict page used farthest in future Count ✗ = page fault each time page not in frames
All frames empty initially → first k unique pages cost k faults
📁 Chapter 11 - File System Interface
Directory Structures
Structure Unique Names? Grouping? Sharing?
Single-level Yes (all users) No No
Two-level Per user only No Hard
Tree Per path Yes No links
Acyclic Graph Multiple names OK Yes Yes (links)
General Graph Multiple names OK Yes Yes (cycles)
Access Methods
  • Sequential - process records in order; tapes, compilers
  • Direct/Random - jump to any record; fixed-length records; DB
  • Indexed - index file → data; ISAM; handles large files
File Operations
  • Create, Write, Read, Seek (reposition), Delete, Truncate
  • Open → moves directory entry to memory (open-file table)
  • Close → writes back to directory on disk
  • Open-file table tracks: file pointer, open count, disk location, access rights
Protection - UNIX Model
RWX | RWX | RWX Owner | Group | Universe r=4, w=2, x=1 chmod 755 → 111 101 101 → rwxr-xr-x
  • ACL - per-file user+permission list (verbose but flexible)
  • Dangling pointer problem with links → use reference count
🗄 Chapter 12 - File System Implementation
Disk Block Allocation Methods
Method Ext. Frag? Random Access? Grow?
Contiguous Yes Yes Hard
Linked No No (sequential) Easy
Indexed No Yes Yes
Contiguous Allocation
LA / BlockSize → Q (block number from start of file) LA % BlockSize → R (displacement within block) Disk block = start_address + Q Displacement = R
  • Simple; best read performance
  • External fragmentation; hard to grow file; need to know size upfront
Linked Allocation
Q = LA / (BlockSize - PointerSize) → Qth block in chain R = LA % (BlockSize - PointerSize) → offset within block Displacement = R + PointerSize
  • No external fragmentation; easy to grow
  • Sequential access only; pointer overhead; reliability risk
  • FAT = variation: pointers in table (not in blocks) → cacheable
Indexed Allocation
Index block: [ptr₀, ptr₁, ..., ptrₙ] Q = LA / BlockSize → index into index block R = LA % BlockSize → offset within data block Physical block = index_block[Q] Displacement = R
  • Random access; no external fragmentation
  • Overhead of index block; UNIX uses multi-level (inode)
Free Space Management
Method How Pro Con
Bit vector 1 bit per block Fast, simple Large on big disks
Linked list Chain free blocks No waste Slow traversal
Grouping n free addrs in 1st free block Faster than linked Complex
Counting (start, count) pairs Compact Complex
Bit vector block number: = (bits/word) × (# zero-value words) + (offset of first 1-bit)
I/O Operations - Block Add/Remove
Op Contiguous Linked Indexed
Add at start 201 1 1
Add at middle 101 52 1
Add at end 1 3 1
Remove start 198 1 0
Remove middle 98 52 0
Remove end 0 100 0
Assumes 100-block file; index block in memory for indexed
⚠ Common Mistakes & Traps
Process & Thread Traps
  • fork() n times in a loop → 2ⁿ processes (NOT n+1)
  • fork() returns 0 to child - NOT child's PID
  • WAITING → RUNNING is INVALID state transition
  • Stack/heap are NOT shared between threads (each has own)
  • Many-to-One: one blocking syscall blocks ALL threads in process
  • Context switch time is pure overhead - no useful work done
Memory & Scheduling Traps
  • Paging = NO external fragmentation (but has internal)
  • Segmentation = NO internal fragmentation (but has external)
  • Pure paging: logical addr = physical addr is WRONG (execution-time binding differs)
  • FIFO can suffer Belady's Anomaly; LRU and OPT cannot
  • SJF is optimal only for same-arrival processes; SRTF for preemptive
  • Priority: smaller integer = higher priority (common convention, verify per question)
Synchronization Traps
  • Deadlock needs ALL 4 conditions simultaneously (not just one)
  • Dining philosophers naive solution causes deadlock if all pick left chopstick
  • signal() on monitor condition with no waiting process = NO EFFECT
  • Semaphore signal() always wakes one (unlike condition variables)
  • Omitting wait(mutex) or signal(mutex) → mutual exclusion broken
  • Doing two wait()s on same semaphore → deadlock
File System Traps
  • Contiguous: adding block at end = 1 I/O; at beginning = 201 I/Os (100 blocks file)
  • Indexed: all add/insert operations = 1 disk write (index in memory)
  • Linked allocation: cannot support efficient random access
  • Bit vector: block# calc uses 0-value words (all bits=0), not just any word
  • printf() ≠ system call; write() is the underlying syscall
🎯 Past Exam-Style Questions
Q1 Easy  If the kernel is single-threaded, a user-level thread making a blocking syscall will…? ▼
Answer: (c) Cause the entire process to block, even if other threads are available to run.
Because the kernel sees only one thread - the single kernel thread. All user threads map to it.
Q2 Easy  What is the output of: int x=10; fork(); if child: x-=5; fork(); x*=3; print at Line A (child of child)? ▼
Line A = 15. Parent: x=10. First fork → child gets x=10. Child does x-=5 → x=5. Second fork → grandchild gets x=5. Both do x*=3. Grandchild (Line A) prints 5×3=15.
Line B (original parent after wait): x is still 10 (fork() copies don't affect parent).
Q3 Medium  Processes: P1(AT=0,BT=8), P2(AT=3,BT=4), P3(AT=4,BT=2), P4(AT=6,BT=4). Draw FCFS Gantt & compute waiting times. ▼
FCFS (non-preemptive, first-come first-served):
P1
0→8
P2
8→12
P3
12→14
P4
14→18
WT: P1=0, P2=8-3=5, P3=12-4=8, P4=14-6=8 → Avg WT = (0+5+8+8)/4 = 5.25
Q4 Medium  TLB access=10ns, memory=50ns, hit ratio=90%. Compute EAT. ▼
EAT = 0.9×(10+50) + 0.1×(10+50+50) = 0.9×60 + 0.1×110 = 54 + 11 = 65 ns
Hit: TLB + memory = 60ns. Miss: TLB + page table + memory = 110ns.
Q5 Medium  Logical address 2524, page size=2KB. Page table: P0→frame3, P1→frame0, P2→frame2, P3→frame1. Find physical address. ▼
Page size = 2KB = 2048 bytes Page# = 2524 / 2048 = 1 (P1) Offset = 2524 % 2048 = 476 Frame = page_table[1] = 0 Physical = 0 × 2048 + 476 = 476
Q6 Medium  Reference string: 1,2,3,4,2,1,5,6,2,1,2,3 with 3 frames. How many page faults with FIFO? ▼
FIFO (3 frames): Ref: 1 2 3 4 2 1 5 6 2 1 2 3 F1: 1 1 1 4 4 4 5 5 5 5 5 3 F2: 2 2 2 2 2 2 6 6 6 6 6 F3: 3 3 3 3 3 3 3 3 3 3 ← wait - step through carefully: Fault:✗ ✗ ✗ ✗ - - ✗ ✗ - - - ✗ = 8 page faults
Tip: track eviction order by FIFO queue - oldest loaded frame is evicted.
Q7 Medium  Semaphore S=0. Process P1: [code; S1; wait(S)] and P2: [code; S2; signal(S)]. Which executes first? ▼
S2 always executes before S1 is FALSE. Actually: S1 always executes AFTER S2.
P1 reaches wait(S) → S=0 → blocks. P2 must execute signal(S) first → S=1 → P1 unblocks and runs S1.
This is a classic ordering/synchronization pattern using semaphore initialized to 0.
Q8 Hard  256 pages, 4KB page size, 64 frames. (a) Bits in logical address? (b) Bits in physical address? ▼
(a) Logical: page# bits = log₂(256)=8; offset bits=log₂(4096)=12 Total logical = 8+12 = 20 bits (b) Physical: frame# bits=log₂(64)=6; offset=12 Total physical = 6+12 = 18 bits
Q9 Hard  Preemptive SJF: P1(AT=0,BT=8), P2(AT=1,BT=4), P3(AT=2,BT=9), P4(AT=3,BT=5). Compute avg waiting time. ▼
SRTF Gantt: P1[0→1] P2[1→5] P4[5→10] P1[10→17] P3[17→26] (at t=1: P2 BT=4 < P1 remaining=7 → preempt) (at t=5: P4 BT=5 < P1 remaining=7; P3 BT=9 → P4 runs) (at t=10: only P1, P3 remain; P1 remaining=3 < P3's 9 → P1) WT: P1=(10-1-1)+(start consideration)=start_run - arrival - burst_done Simpler: WT=TAT - BT TAT: P1=17-0=17, P2=5-1=4, P3=26-2=24, P4=10-3=7 WT: P1=17-8=9, P2=4-4=0, P3=24-9=15, P4=7-5=2 Avg WT=(9+0+15+2)/4=26/4=6.5 ms
Q10 Hard  File has 100 blocks. Using linked allocation, how many disk I/Os to add a block in the middle? ▼
Answer: 52 I/Os
Must read 50 blocks to reach the middle (50 reads). Then write the new block (1 write). Then update the 50th block's next-pointer (1 read + 1 write = 2 I/Os). Total = 50+2 = 52.
Note: the 50th block must be read first to get its pointer, then written back with updated pointer.
Q11 Hard  Bit vector: bits/word=8, Word0=00000000, Word1=00000000, Word2=00010000. What is the first free block? ▼
Block# = (bits/word) × (#zero-value words) + offset of first 1-bit = 8 × 2 + 3 = 19
Word2 = 00010000 → first 1-bit is at position 3 (counting from left, 0-indexed).
Q12 Hard  CPU util=10%, Paging disk=97.7%, Other I/O=5%. Is this thrashing? How to fix? ▼
Yes, this is thrashing. Signs: CPU very low, paging disk almost maxed.
Fixes:
1. Decrease degree of multiprogramming (suspend some processes)
2. Add more physical RAM
3. Use working set model to allocate enough frames per process
⚡ Quick Reference Formulas
Memory Calculations
Page size = 2ⁿ bytes → offset = n bits Num pages = 2^(total_bits - offset_bits) Physical bits = log₂(frames) + offset_bits Logical addr → Physical addr (paging): p = LA / page_size d = LA % page_size PA = frame_table[p] × page_size + d Segmentation check: if d ≥ limit[s] → TRAP (illegal) PA = base[s] + d
Scheduling Formulas
TAT = Finish_Time - Arrival_Time WT = TAT - Burst_Time Response = First_Response - Arrival_Time Avg WT = Σ(WT_i) / n Avg TAT = Σ(TAT_i) / n RR max wait = (n-1) × quantum
EAT Formulas
TLB EAT: h=hit ratio, c=TLB time, m=mem time EAT = h(c+m) + (1-h)(c+2m) Page Fault EAT: p=fault rate, ma=mem access, ft=fault time EAT = (1-p)×ma + p×ft Linked alloc address: Q = LA / (BS - PS) R = LA % (BS - PS) Disp = R + PointerSize