COMPUTER ORGANIZATION & ARCHITECTURE

Answer: (ii) 1-way set associative

Direct-mapped cache is equivalent to 1-way set associative: each block maps to exactly one set (n blocks = n sets, 1 block per set). n-way would be fully associative.

Answer: (iii) 190 ns (simple); 200 ns hierarchical - both shown

Given: $T_c=100\,ns$, $T_m=1000\,ns$, $h=0.9$, $miss=0.1$

• Simultaneous access (common textbook for this question):
  $T_{avg}= h\cdot T_c + (1-h)\cdot T_m = 0.9\times100 + 0.1\times1000 = 90+100 = 190\,ns$ → Option (iii)

• Hierarchical access (cache checked first, then memory on miss):
  $T_{avg}= h\cdot T_c + (1-h)\cdot(T_c+T_m) = T_c+(1-h)T_m = 100+100 = 200\,ns$ → Option (ii)

Most WBUT/MAKAUT PYQs expect (iii) 190 ns. If hierarchical model is assumed, answer is 200 ns.

Answer: (i) pages

Explanation:

• Virtual memory - Programs (logical address space) are divided into fixed-size blocks called pages.
• Physical memory is divided into same-size blocks called frames/page frames.
• Page table maps virtual page number → physical frame number for address translation via MMU.
• Segments are variable-size logical divisions (segmentation), while blocks is generic; for pure paging the division is pages.

Hence programs are divided into pages, physical memory into frames.

Answer: (ii) LRU

Explanation:

• LRU (Least Recently Used): Evicts block that has not been referenced for longest time - exploits temporal locality; needs timestamp/counter/stack.
• FIFO: Evicts oldest inserted block regardless of recent use.
• Random Replacement: Random victim - simple hardware.

LRU gives best hit rate among three but most complex to implement.

Answer: (iii) 1024

Calculation:
Desired: $32K \times 32$ bit
Available: $128 \times 8$ bit

• Depth expansion: $32K / 128 = 32768/128 = 256$ rows
• Width expansion: $32 / 8 = 4$ chips per row
• Total chips: $256 \times 4 = 1024$

Hence 1024 chips required. Same as Q77.

Answer: Theoretically 4K bytes (4 chips) → among given options (c) 8K is closest listed; ideal answer 4K

Explanation:
Chip: $1K \times 8$ bit = 1KB, 8-bit wide.
CPU bus: 32-bit wide → need $32/8 = 4$ chips in parallel per word to match width.

• One row (4 chips): $1K \times 32$ bit = 4KB
• This is smallest feasible memory (must be multiple of 4 chips to fill bus).

Given options list 12K/10K/8K/16K/24K (no 4K), the smallest listed option that satisfies 4-chip grouping and is ≥4K is c) 8K (2 rows of 4 chips = 8KB). If 4K were listed it would be exact answer. Some textbooks directly answer 4K for this configuration.

Answer: (iii) 3

Explanation:
Standard DMA controller (e.g., Intel 8237) has 3 main registers per channel:

1. Address Register - holds starting address of memory block (source/destination)
2. Word Count Register - number of words/bytes to transfer
3. Control/Status Register - direction, mode (burst/cycle stealing), enable

Some descriptions count 4 including Data Buffer register, but classic exam answer is 3 registers.

Virtual Memory, Paging and TLB

Virtual Memory: Technique that allows execution of program larger than physical main memory by using disk (swap) as extension. CPU generates virtual/logical address, translated by MMU to physical address. Gives programmer illusion of large contiguous memory and provides isolation/protection.

Paging: Virtual and physical memory divided into fixed equal blocks - pages (virtual) and frames (physical), e.g. 4KB. Virtual address = [Virtual Page Number (VPN) | Offset]. Page Table stores mapping VPN -> Frame No. + valid/dirty/protection bits. On page fault (valid=0), OS brings page from disk, updates table.

Example: 32-bit virtual addr, 4KB pages (offset 12 bits). VA = 0x00403ABC -> VPN = 0x00403, Offset=0xABC. Page Table[0x00403]= Frame 0x00A -> PA=0x00AABC.

TLB - Translation Lookaside Buffer: Small, fully-associative high-speed cache of recently used Page Table Entries inside MMU.

• TLB Hit: VPN found in TLB -> frame number returned in ~1 cycle, no memory access.
• TLB Miss: Search page table in memory (or walk), load entry into TLB, may cause page fault.

Effective Access Time: $EAT = h \cdot (c+ m) + (1-h)(c+2m)$ where $h$= hit ratio, $c$= TLB time, $m$= memory time. With $h \approx 98\%$, EAT $\approx$ memory speed. TLB greatly reduces translation overhead. Replacement via LRU/random, flush on context switch.

Locality of Reference:

Principle that memory accesses are clustered, not random — basis for caches and virtual memory.

• Temporal Locality: Recently accessed locations tend to be accessed again soon (e.g., loops, stack variables). → Keep them in cache.
• Spatial Locality: If a location is accessed, nearby locations will be accessed soon (e.g., sequential instructions, arrays). → Fetch blocks/lines.

Due to locality, a small fast cache can achieve hit rate ~90-95% and make average access time close to cache speed despite large, slow main memory.

Cache Coherence Problem:

Occurs in multiprocessor / multi-cache systems where multiple caches may hold copies of the same memory block.

If one processor (P1) writes to its cached copy of block X, other caches holding X become stale/inconsistent with main memory and with each other. Subsequent reads by other processors would get old data.

• Problem: Ensuring all caches and main memory see a consistent view of shared data after writes.
• Solutions: Snooping protocols (write-invalidate, write-update / write-broadcast), directory-based protocols, MESI state machine.

Without coherence, program correctness is violated.

Why WMFC is needed:

Main memory (DRAM) is asynchronous and slower than CPU. Its access time is variable and longer than one CPU clock period. CPU issues read/write by placing address/data on bus and issues Memory Enable but cannot proceed until memory completes the operation.

WMFC (Wait-for-Memory-Function-Completed) is a control step where CPU waits for MFC (Memory Function Completed) signal from memory controller.

• Ensures data in MDR/MBR is valid before it is used (read) or guarantees write has been latched.
• Synchronizes fast synchronous CPU with slow asynchronous memory.
• Without WMFC, CPU would fetch stale/wrong data or overwrite next operation, causing incorrect execution. Cycle time = access time + recovery time, so next memory operation can start only after WMFC/MFC.

In synchronous control sequence: MAR ← address; MDR ← data (for write); WMFC; MDR ← valid data (for read).

Answer: 16 chips

Each RAM chip = $128 \times 8$ = 128 bytes (128 locations of 8-bit words).

Required capacity = 2048 bytes.

$$\text{No. of chips} = \frac{\text{Required capacity}}{\text{Chip capacity}} = \frac{2048}{128} = 16$$

So 16 chips of $128 \times 8$ are needed (arranged as $16 \times 128 = 2048$ bytes; 8-bit width matches, no width expansion needed — only depth expansion; needs 11 address lines, 7 for chip internal, 4 for chip select via decoder).

Answer: (iv) 19 ns

Average memory access time (hierarchical access: check cache first, go to memory only on miss):

$$T_{avg} = h \cdot T_c + (1-h)\cdot T_m$$

Given hit rate $h = 90\% = 0.9$, $T_c = 10$ ns, $T_m = 100$ ns:

$$T_{avg} = 0.9 \times 10 + 0.1 \times 100 = 9 + 10 = 19 \text{ ns}$$

If counting $T_c + T_m$ on miss (simultaneous vs hierarchical variants), then $0.9 \times 10 + 0.1 \times 110 = 20$ ns — but with given options, 19 ns is the expected answer.

Correct option: (iv) 19 ns

Answer: (ii) Cycle time

• Access time = time between initiation of read/write operation and completion (data available).
• Cycle time = minimum time delay between initiations of two successive independent memory operations. It = access time + recovery/recharge time needed for memory to recover before next access (e.g., DRAM precharge).
• Always cycle time ≥ access time.

Hence delay between initiations of two independent operations is cycle time. So option (ii) cycle time is correct. Other options: transfer rate = bytes/sec, latency = delay to first bit.

Importance of Cache Memory (2 Marks)

Cache is a small, very fast SRAM between CPU and main memory that bridges the speed gap between high-speed processor and relatively slow DRAM main memory.

1. Speed Gap: CPU cycle time is ~1ns while DRAM access is ~50-100ns. Without cache, CPU would stall waiting for memory. Cache (access ~2-5ns) supplies most needed words at CPU speed.
2. Exploits Locality of Reference: Due to temporal locality (recently used data reused soon) and spatial locality (next addresses likely accessed), ~90-95% accesses hit in cache, giving average access time ≈ cache time.
3. Result: Improves effective memory access time, increases throughput, reduces memory bandwidth demand. Hence hit ratio and system performance increase significantly despite small size and high cost/bit.

Locality of Reference - Defined (2 Marks)

Locality of reference is the empirical observation that memory references tend to cluster in a small region over a short time interval. It is the basis for cache and virtual memory.

1. Temporal Locality: If a memory location is referenced, it is likely to be referenced again soon. e.g. loops, reusable variables, stack. Keeping recently used blocks in cache yields hits.

2. Spatial Locality: If a location is referenced, nearby locations are likely to be referenced soon. e.g. sequential instruction fetch, arrays. Fetching a whole block/line exploits this.

3. Sequential Locality: Special case of spatial — ordered instruction execution.

Due to locality, 90/10 rule holds: 90% of time CPU accesses only 10% of address space, making cache hierarchy very effective.

ROM Cell Features (2 Marks)

ROM (Read Only Memory) cell stores a fixed bit permanently:

1. Non-volatile: Retains contents without power — used for bootstrap, firmware, microprogram.

2. Mask-programmed: Contents written at fabrication via contact mask / transistor presence (1 = transistor present, 0 = absent). Not field-writable.

3. Non-destructive read: Reading does not erase cell; access via address decoder → word line → bit line sense.

4. High density, low cost/bit for large volumes; slower write-once but fast read comparable to RAM.

5. Variants: PROM (fusible link, OTP), EPROM (floating gate, UV erase), EEPROM/Flash (electrically erasable) retain ROM cell principle but allow reprogramming.

Single ROM cell = 1 transistor + contact/via; array is OR plane of word lines.

Definition:
$$\text{Hit Ratio } (h) = \frac{\text{Number of hits}}{\text{Total number of accesses}} = \frac{\text{Hits}}{\text{Hits + Misses}}$$

$$Miss\ Ratio = 1 - h$$

Where hit = data found in faster memory (Cache), miss = data not found and must be fetched from lower level (Main memory).

Hit ratio is usually expressed for cache: $h_{cache}$, also applicable to TLB, etc.

Significance - AMAT (Average Memory Access Time):

The effective access time depends critically on hit ratio:

$$AMAT = h \times T_{hit} + (1-h)\times T_{miss}$$

or for hierarchical memory:

$$AMAT = T_{cache} + (1-h) \times T_{memory}$$

• High $h$ ($\approx$ 0.9-0.99 due to locality of reference) → $AMAT \approx T_{cache}$ → system performs near cache speed, despite large cheap main memory.
• Low $h$ → AMAT → approaches main memory time, cache is ineffective and penalty dominates.
• Used to evaluate/design cache: organization, block size, associativity, replacement policy all aim to maximize $h$. Helps in deciding cache size vs. cost trade-off and in calculating effective CPU stall cycles due to memory.

Example: $T_{cache}=10ns$, $T_{memory}=100ns$, $h=0.95$ → $AMAT = 0.95\times10 + 0.05\times(10+100)=14.5ns$ vs $100ns$ without cache.

Answer: (iii) Replacement algorithms

Explanation:
In cache mapping (especially set-associative and fully-associative), a miss with no empty block requires evicting an existing block. The policy that decides which block to evict is the replacement algorithm.

• FIFO (First-In First-Out): Evicts the block that has been in cache longest (oldest load), using a queue per set. Simple to implement, but not always efficient (does not consider locality).
• LRU (Least Recently Used): Evicts the block least recently accessed, exploiting temporal locality. Most effective general policy; approximates optimal. Implemented via counters/linked list or $n$-way LRU bits. Higher hardware overhead.

Why not other options:

• (i) Mapping techniques: Direct, Associative, Set-Associative - decide where a block can be placed.
• (ii) Addressing techniques: Way of forming addresses.
• (iv) Write policies: Write-through / Write-back (and Write-allocate) - handle consistency between cache and main memory on writes, not eviction.

Hence FIFO and LRU belong to replacement policy class; choice directly affects miss rate and hit ratio.

Hypothetical: Instruction = 32 bits = 8 bits opcode + 24 bits address/immediate.

(a) Maximum Directly Addressable Memory Capacity

Direct field = $32-8 = 24$ bits.

If byte-addressable: $Capacity = 2^{24}$ bytes $=16,777,216$ B $=16$ MB.

If word-addressable (32-bit word =4B): $2^{24}$ words $= 2^{24}\times4 = 2^{26}$ B $=64$ MB, i.e. $4M$ words.

Note: If microprocessor internally has full 32-bit address bus, theoretical max = $2^{32}$ B $=4$ GB, but with given format without indirect/indexing you can only encode 24-bit direct address $\Rightarrow$ only $16$ MB directly without using indirect or paging.

(b) Impact of Bus Width on Speed

Assume memory and CPU are 32-bit, but buses narrower:

i) 32-bit address bus, 16-bit data bus

• Address bus 32-bit $\Rightarrow$ can address full $2^{32}=4$ GB.
• Data bus 16-bit $\Rightarrow$ each 32-bit instruction or operand needs 2 bus cycles to fetch/transfer (16 bits per cycle).
  • e.g. Instruction fetch: $T_{fetch}=2\times T_{bus}$ vs $1\times$ with 32-bit data bus.
  • Data read/write of 32-bit word also 2 cycles. Bus bandwidth halved: $BW = 16$ bits/cycle vs $32$.
  • Needs two memory accesses, causes wait states, effective CPI increases.
  • Still functionally correct, but speed roughly ~50% for memory-intensive code + extra control logic (byte assembly, multiplexing).

ii) 16-bit address bus, 16-bit data bus

• Address 16-bit $\Rightarrow$ directly addressable = $2^{16}=64$ KB only! Massive limitation.
  • To access beyond 64KB need banking, segment registers, page registers, or multiplexed address (like 8086 with 20-bit via segment:offset) – adds software/hardware overhead and slowdown.
  • Cannot use full 32-bit address field; higher bits must be latched in two cycles (address multiplexing) or ignored.
• Data 16-bit $\Rightarrow$ same 2-cycle fetch as case (i).
• Overall: Much slower than (i) + severely limited memory. Requires extra bus cycles to send full 32-bit address (send low 16 then high 16) if attempting to address 4GB, effectively 2 address cycles + 2 data cycles per access. System speed degraded by $> 2\times$ and programmability restricted.

Summary: Widening address bus increases address space; widening data bus increases throughput. Halving data bus doubles memory cycles. Halving address bus collapses address space.

(c) Bits needed for PC and IR

• Instruction Register (IR): Must hold full instruction $=32$ bits (8 opcode +24 operand). So $IR=32$ bits.
• Program Counter (PC): Must hold address of next instruction.
  • If holding direct field only: $24$ bits (to address $16$ MB).
  • If holding full memory address (32-bit address bus): $32$ bits to address full $4$ GB, even though instruction can only encode 24 bits directly (rest via indirect).
  • Practical design: $PC=32$ bits, $IR=32$ bits. For byte-addressable with word-aligned instructions (4B), PC increments by 4.

Exam answer: $IR=32$ bits, $PC=24$ bits minimum ($32$ bits for full 4GB system).

Hierarchical Memory Structure

Memory is organized as a pyramid/hierarchy based on trade-off between speed - cost - capacity - access time. Faster memory per bit is costlier and smaller.

              ↑ Speed, Cost/bit
              |  Capacity ↓
    +-----------------+
    |  CPU Registers  |  < 1 ns, <1KB, fastest, costliest
    +-----------------+
    |     Cache       |  L1: 2-5 ns, 32-64KB
    |  L1 | L2 | L3   |  L2: 5-10 ns, 256KB-8MB  SRAM
    +-----------------+
    |   Main Memory   |  50-100 ns, 4-32 GB, DRAM
    |   (Primary)     |
    +-----------------+
    |  Secondary      |  5-10 ms, 256GB-4TB
    |  SSD / HDD      |
    +-----------------+
    |  Tertiary /     |  sec-min, TB-PB, Optical Tape
    |  Off-line       |  Archival, slowest, cheapest
    +-----------------+
              ↓ Slower, Cheaper, Larger

Levels in Detail

1. Registers (Top)

• Inside CPU, <32-64 words, flip-flops, 0.5-1 ns, directly accessed by ALU.

2. Cache Memory (SRAM)

• Between CPU and RAM. Holds copies of frequently used blocks (locality of reference).
• L1 split I/D, L2 unified, L3 shared. Hit ratio ~ 90-95%. Block size 32-128B.
• Managed by hardware.

3. Main Memory (DRAM)

• Primary memory, volatile, 4-32 GB. Byte-addressable. Managed by OS + MMU.

4. Secondary (Magnetic/Flash)

• Non-volatile, virtual memory backing store, page file on SSD/HDD.

5. Tertiary/Offline

• Tape libraries, optical jukebox for backup.

Key Principles

• Inclusion: Data at level $i$ is subset/copy of level $i+1$ (Cache contains copy of RAM block).
• Locality: Temporal (recently used reused) & Spatial (neighbors used) → hierarchy works.
• Access time: $T_{eff}= H\times T_{cache} + (1-H)\times (T_{cache}+T_{main})$ where $H$ is hit rate.
• Cost: $C_{avg}= \frac{\sum C_i S_i}{\sum S_i}$

Advantages: Gives illusion of large, cheap memory with speed near registers; transparent to programmer via memory management; exploits locality.

Modern example PC: Registers ~1KB, L1 64KB, L2 512KB, L3 8MB, RAM 16GB, SSD 1TB, HDD/Cloud TB.

Virtual Memory Concept

Virtual memory is a memory management technique that gives program illusion of large contiguous main memory (e.g. $4$ GB) while physically only part resides in RAM; remainder kept on secondary storage (disk). Address generated by CPU (virtual/logical) is translated to physical via MMU.

CPU generates              MMU + Page Table + TLB                Main Memory / Disk
Virtual Address  ----->   Translation  -----> Physical Address ---> RAM (if present)
  32-bit                    VPN -> PFN       32-bit              else Page Fault -> Disk

• Virtual address space $>>$ Physical address space (e.g. $2^{32}$ virtual vs $2^{28}$ physical).
• Transparent to programmer, allows multiprogramming, protection, demand paging.
• Uses locality – only active pages kept in RAM.

Diagram: Paged Virtual Memory Mapping

Virtual Address (32b)
+----------------------+------------------+
| Virtual Page Number  | Page Offset      |
|  VPN (20b)           |  OFFSET (12b)    |  -> 4KB pages
+-----------+----------+-----+------------+
            |                  |
            v                  |
     +--------------+          |
     | Page Table   | TLB      |
     | (in RAM)     | cache    |
     | VPN -> PFN   |          |
     +------+-------+          |
            |                  |
            v                  v
Physical Address (32b)
+----------------------+------------------+
| Physical Frame Number| Offset           |
|  PFN (20b)           | (12b same)       |
+----------------------+------------------+

RAM: [Frame 0][Frame 1]...[Frame N]   Disk: swap space with all pages

Virtual to Physical Mapping Steps (Paging)

Assume page size $4$ KB $=2^{12}$ B $\Rightarrow$ offset $12$ bits, VPN $20$ bits for $32$-bit virtual.

1. CPU generates virtual address $VA = (VPN, offset)$.
2. MMU looks up TLB (Translation Lookaside Buffer) – cache of page table.
   • TLB hit: get PFN immediately.
   • TLB miss: access page table in RAM (pointed by Page Table Base Register - PTBR). May be multi-level (e.g. 2-level for 32-bit).
3. Page Table Entry (PTE) contains: PFN, valid bit, dirty, protection (R/W/X), referenced.
   • If valid=1: $PA = PFN \times PAGE\_SIZE + offset$ (concatenation).
   • If valid=0: Page Fault → trap to OS. OS loads required page from disk to free frame (using replacement e.g. LRU), updates PTE, restarts instruction.
4. Physical address sent to cache/memory.

Example: $VA=0x12345678$, page $4$ KB $\Rightarrow$ VPN=$0x12345$, offset=$0x678$; page table maps VPN $0x12345 \rightarrow PFN 0x00ABC$ $\Rightarrow$ $PA=0x00ABC678$.

Segmentation + Paging: Sometimes VA = segment + offset; segment table → page table. But pure paging described above is most common (x86, ARM).

Advantages: Large logical space, protection/isolation, sharing, efficient multiprogramming, demand loading.

Overhead: Translation time (mitigated by TLB $>95\%$ hit), page fault handling, fragmentation (internal).

Given

• Cache size $C =16$ KB $=16384$ B $=2^{14}$ B
• Associativity $k=4$ (4-way set associative)
• Block size = $8$ words, Word = $32$ bits $=4$ B
  $\Rightarrow$ Block = $8\times4=32$ B $=2^{5}$ B
• Physical address space $4$ GB $=2^{32}$ B $\Rightarrow$ Physical address $32$ bits

Calculations

1. Number of blocks in cache:
$N_{blocks}= C / Block =16384/32=512$ blocks $=2^{9}$

2. Number of sets:
$N_{sets}= N_{blocks}/k =512/4=128$ sets $=2^{7}$
$\Rightarrow$ SET field $s = \log_2 N_{sets}=7$ bits

3. WORD / Offset field:
Block = $32$ B. Byte offset within block = $\log_2 32 =5$ bits.
This $5$ bits comprises:

• Word offset within block: $\log_2 8 =3$ bits (select 1 of 8 words)
• Byte offset within word: $\log_2 4 =2$ bits (select 1 of 4 bytes)

If address is word-addressable, WORD field = $3$ bits.
If byte-addressable (standard), combined offset = $5$ bits.

Common naming in question: WORD field = $5$ bits (or split $3+2$).

4. TAG field:
$TAG = Physical\_bits - SET - OFFSET$

• Byte-addressable: $TAG =32 -7 -5 =20$ bits
• Word-addressable with byte split: $TAG =32 -7 -3 -2 =20$ bits same.

Answer

Physical Address (32 bits)
+-----------+---------+---------------+
| TAG 20b   | SET 7b  | WORD/OFFSET 5b|
|           |         | (3b word+2b byte)|
+-----------+---------+---------------+

• TAG = 20 bits
• SET = 7 bits
• WORD/Offset = 5 bits (3 bits word + 2 bits byte)

If counting WORD only (word index): WORD=3 bits, BYTE=2 bits, TAG=20, SET=7.

Check: $20+7+5=32$.

Alternative: If cache size given as $16$ KB words (unlikely), then $C=16K\times4=64KB$ $\Rightarrow$ sets $=512$ $\Rightarrow$ SET=9, TAG=18. But standard is bytes → answer above.

A) Virtual address → Physical address mapping (Paging)

Virtual address generated by CPU is not real RAM address. MMU translates via Page Table + TLB.

Assume $V=32$ bits, page $4$ KB $=2^{12}$ B $\Rightarrow$ offset $12$b, VPN $20$b.

VA (32b): [ VPN 20b | Offset 12b ]
                 |
                 v
          +-------------------+
          | TLB (cache)       |---- hit ----> PFN
          | VPN -> PFN        |
          +---------+---------+
                    | miss
                    v
          Page Table in RAM (PTBR points)
          PTE: [ PFN | valid | prot | dirty | ref ]
                    |
                    v
PA (32b): [ PFN 20b | Offset 12b ]  (concatenation)

Steps:

1. Split VA into VPN + offset.
2. Search TLB ( ~64-512 entries, associative). Hit → PFN in 1 cycle.
3. Miss → hardware walks page table (often 2-level: Dir + Page table) in memory; may fault.
4. If PTE valid=1 → $PA = PFN \ll 12 | offset$; check protection.
5. If valid=0 → Page fault → OS loads page from disk to frame, updates PTE, restarts.
6. TLB updated.

Segmentation variant: $VA = segment+offset$ → segment table → page table. But paging alone is core.

---

B) Cache Write Methods

When CPU writes, cache and main memory can become incoherent. Policies:

1. Write-Through

• Write to both cache and main memory simultaneously.
• Simple, coherent, but every write goes to bus → high traffic, slow.
• Usually with write buffer to hide latency.
• On read miss, block fetched.

CPU Write → Cache + Memory (together)

2. Write-Back (Copy-Back)

• Write only to cache; set Dirty bit per block. Memory updated only on eviction of dirty block.
• Reduces bus traffic (many writes coalesced). Faster.
• Needs dirty bit + extra control; memory stale until write-back.

CPU Write → Cache (dirty=1)  ---- later on replace ---> Memory

3. Allocation policy on Write Miss

• Write-Allocate (Fetch on Write): On write miss, load block to cache then write (common with write-back).
• No-Write-Allocate (Write-Around): On write miss, write directly to memory, not loading to cache. Common with write-through to avoid polluting cache with write-only data.

Typical combos:

• Write-Through + No-Write-Allocate
• Write-Back + Write-Allocate (most performant, used in L1/L2)

Comparison:

Property	Write-Through	Write-Back
Memory update	Immediate	Deferred (on evict)
Bus traffic	High	Low
Dirty bit	No	Yes
Speed	Slower	Faster
Coherence	Simple	Complex (need snooping)

Example: $4$-way cache: Write hit in write-back sets dirty; on replacement if dirty=1, 32B block written back to RAM before loading new block.

Swapping and Use in Memory Management

Definition

Swapping is moving a process (or part) temporarily out of main memory (RAM) to secondary storage (backing store / swap space on disk) and bringing it back later for execution. Introduced for multiprogramming when RAM insufficient.

Swap Out: RAM --> Disk; Swap In: Disk --> RAM. Managed by medium-term scheduler (swapper) and dispatcher.

How Swapping Works

1. System keeps Ready Queue of processes in memory and Swap Device queue on disk.
2. When memory pressure high or process blocked (e.g. I/O wait) and higher priority process arrives, dispatcher selects victim (e.g. lowest priority, sleeping).
3. Victim's entire address space (or at least resident pages) is copied to swap file, its PCB updated (state = swapped, location = disk), frames freed.
4. Later when memory free or process becomes ready, swapper selects swapped process, finds contiguous / non-contiguous free frames, loads it back, possibly at different physical address (requires relocation via base-limit registers or paging).

Time = swap size / transfer rate. E.g. 10 MB process, disk 20 MB/s => 0.5s out +0.5s in =1s overhead -> swapping is expensive, attempted only when needed.

Types

• Whole process swapping (old UNIX, embedded) - simple but costly.
• Page swapping / paging (modern VM) - swap only pages/frames, not whole process.
• Roll in / Roll out for priority scheduling.

Usefulness / Advantages

1. Degree of Multiprogramming: Allows more processes than fits in RAM to co-exist by multiplexing memory over time, increasing CPU utilization.
2. Handles Insufficient Memory: Large process (>RAM) can still run by swapping parts; avoids need for all processes to fit simultaneously.
3. Compaction: Swapping out creates holes, allows memory compaction to reduce external fragmentation (combine free blocks) and allocate contiguous memory.
4. Priority Scheduling: High priority process swapped in quickly by swapping out low priority.
5. I/O Idle Utilization: Blocked process swapped out so its RAM used by ready processes.
6. Foundation for Virtual Memory: Modern demand paging is refined swapping per page with lazy loading.

Disadvantages / Considerations

• Swap time overhead and disk I/O bottleneck; double transfer.
• Need for relocation hardware.
• Not suitable for real-time if swap time unpredictable.
• Thrashing if swapped too frequently.
• Requires swap space reservation on disk.

Swapping vs Paging

Swapping	Paging (demand)
Whole process moved	Only required pages moved
Contiguous allocation needed	Non-contiguous frames ok
High overhead	Lower per-fault overhead

Effective only if combined with compaction and medium-term scheduling; modern OS uses swapping + virtual memory so that Total Logical Memory >> Physical RAM.

Diagram:

Main Memory                Disk (Swap Space)
[ P1 ][hole][ P2 ]   swap out P2 -->  [P2 image]
[ P1 ][ P3 ][hole]   <-- swap in P4   [P4 image][P2]

Free frames consolidated after swap.

Associative Memory (Content Addressable Memory - CAM)

Definition: Memory accessed by content (data) rather than by address. CPU supplies a search word (key); memory simultaneously compares it with all stored words in parallel and marks those that match. Access time is constant $O(1)$ irrespective of location. Opposite of Random Access Memory (RAM) where $address \rightarrow data$.

Also called Associative Storage / Content Addressable Memory.

Block Diagram

                   +-----------------------------+
Search Word (Argument) -->| Argument Register (A)     |
  (key + mask)     |   Key Register (K)  Mask (M) |
                   +-------------+---------------+
                                 | (unmasked bits)
                                 v
                   +-----------------------------+
                   | Associative Memory Array    |  Word0: bit0..bit n + Match logic
                   |  Word1  } each with         |  Word1:  comparator (XNOR per bit)
                   |  ...    } comparison logic  |  ...     + AND of bits
                   |  Wordm  }                   |
                   +-------------+---------------+
                                 | Match lines Mi (Mi=1 if word i matches A on K=1 bits)
                                 v
                   +-----------------------------+
                   | Encoder / Priority or       |
                   | Match Register + Selector   |----> Matched word(s) out
                   +-----------------------------+

• Argument Register A: holds search key.
• Key Register K: 1 means compare that bit, 0 = don't care (maskable).
• Mask Register M (optional): disables masked bits.
• Match Logic per word: $M_i = \bigwedge_{j: K_j=1} (A_j \oplus \text{Word}_{ij})'$ =1 only if all unmasked bits equal.
• Output is either first matching word (priority encoder) or all matches flagged.

Operation: Load $A$ and $K$, assert search, all words compare in parallel (one clock), $M_i$ vector produced, encoder outputs address/data of matched word. Write modifies matched word(s).

Example: 4 words 1010, 1100, 1011, 0010; search $A=1010$, $K=1110$ (don't care LSB) => matches word0 (1010) and word2 (1011).

Cost & Characteristics

• Fast search $O(1)$ but hardware heavy: comparator per bit per word => $m \times n$ XNOR gates. Expensive, power hungry, so used small.
• Word size typically 16-64 bits, capacity $32$ to $4K$ words.

Effective Utilization

1. Cache Memory / TLB (Translation Lookaside Buffer): Most important use. Fully associative cache / TLB stores block tags; CPU searches tag in parallel to find hit/miss without set indexing. E.g. TLB maps virtual page -> physical frame: associative lookup of VPN yields PPN in one cycle.

2. Virtual Memory Page Table Cache: Hardware search of page table.

3. Database / Pattern Matching: Search records by field (e.g. find all employees with age=30) without scanning.

4. Networking: Router's forwarding table, packet classification, firewall ACLs, Ethernet switch MAC lookup, IP longest prefix match -> ternary CAM (TCAM) with don't-care.

5. AI / Fault tolerance: Associative recall, spare memory remapping.

In COA syllabus: used to implement fully associative cache and TLB where hit time must be minimal; otherwise direct-mapped is cheaper. Hybrid set-associative + CAM for tags is practical trade-off.

Cache Replacement Algorithms

When a cache miss occurs in associative / set-associative cache and set is full, one line must be evicted. Direct-mapped needs no choice. Algorithm balances hit rate vs hardware cost.

1. Least Recently Used (LRU)

Evict the line not used for longest time (least recent). Exploits temporal locality.
Implementation: Per set maintain recency stack / counters. For 2-way, single bit per set; for $k$-way, $\log_2 k!$ states or $k$ counters, or pseudo-LRU tree.
Pros: Best hit rate, approximates optimal. Cons: $O(k)$ bits, complex for large $k$ (e.g. 8-way needs 3 bits per line).

2. First-In First-Out (FIFO) / Round-Robin

Evict oldest inserted line (first loaded). No regard to reuse.
Implementation: Circular pointer per set; increment on insertion.
Pros: Very simple, $\log_2 k$ bits per set. Cons: May evict hot line that was loaded early but still frequent (Belady anomaly in paging).

3. Least Frequently Used (LFU)

Evict line with fewest hits since insertion. Keeps hot lines.
Implementation: Counter per line, increment on hit; on replacement choose min counter.
Pros: Good for skewed access. Cons: Counters saturate, stale history; hot line pollutes after phase change; extra storage.

4. Random Replacement

Pick victim uniformly at random (LFSR).
Pros: Zero bookkeeping, no pathological worst case, surprisingly competitive; used in ARM Cortex, many LLCs.
Cons: Slightly lower hit rate than LRU (~2-5%) but saves power/area.

5. Optimal (Belady's / MIN) - Theoretical

Evict line whose next use is furthest in future (requires future knowledge). Gives minimum misses, used only as offline benchmark to evaluate others. Not implementable.

6. Others

• Not Most Recently Used (NMRU): Opposite of LRU, protect MRU; simpler than LRU.
• Not Recently Used (NRU) / Clock: One reference bit per line, clock hand clears bits; evict first with $R=0$.
• Pseudo-LRU (PLRU) Tree: Binary tree of bits per set, approximates LRU with $\approx k-1$ bits vs $k\log k$.

Algorithm	Hit rate	Hardware	Where used
LRU	High	High	L1/L2 small associativity
PLRU	Near LRU	Medium	Intel L2/L3
FIFO	Medium	Low	Simple caches
Random	Medium	Minimal	LLC, ARM
LFU	Workload dep	High	Not common in cache
Optimal	Max (bound)	N/A	Analysis

Example: 2-way set with lines A,B. Access sequence A B A C.
LRU: After A B A, LRU=B, so C replaces B.
FIFO: After A B A, FIFO=A (oldest), so C replaces A -> one extra miss vs LRU.
Random: 50% chance.

Modern caches: Pseudo-LRU or Tree-LRU for 4-16 way, Random for large LLC to save power; inclusion of dirty bit may bias to evict clean line first to avoid write-back.

Set-Associative Cache Design (Numerical)

Given: Block = $4 \times 16$-bit words $=64$ bits $=8$ bytes
Cache capacity $=4096$ words $\times16$ bit $=65536$ bits $=8192$ bytes
Set size $k =2$ (2-way set-associative)
Cacheable main memory $=64K \times32$ bits $=65536\times4$ bytes $=256$ KB

1. Number of Blocks & Sets

$$N_{blocks}= \frac{\text{Cache words}}{\text{words per block}} = \frac{4096}{4}=1024 \text{ blocks}$$

$$N_{sets}= \frac{N_{blocks}}{k}= \frac{1024}{2}=512 \text{ sets}$$

$$Set\;index\;bits = \log_2 N_{sets}= \log_2 512 =9 \text{ bits}$$

$$Block\;offset\;(word) = \log_2 4 =2 \text{ bits (selects one of 4×16-bit words)}$$
If normalized to 32-bit CPU word: block $=2\times32$ bits $\Rightarrow$ offset $=1$ bit. Add byte offset $1$ bit if byte-addressed.

2. Address Interpretation

Main memory $64K\times32$ bits needs $16$ bits for 32-bit word address ($2^{16}=64K$). Equivalent $128K\times16$ bits needs $17$ bits for 16-bit word address.

Case A - 16-bit word address (most exam-expected):
Total 17 bits ($0$-$16$ for $128K$)

$$Tag\;bits = 17 - Set\;bits - Word\;offset =17-9-2=6 \text{ bits}$$

17-bit word address:
| Tag (6) | Set index (9) | Word (2) |
  16-11      10-2            1-0

If CPU byte-addressed: add $1$ bit byte offset inside 16-bit word:
Tag(6) | Set(9) | Word(2) | Byte(1) =18 bits total for $256$KB.

Case B - 32-bit word address (normalized):
Total $16$ bits, block $=2$ words

16-bit address:
| Tag (6) | Set (9) | Block offset (1) |
 15-10      9-1          0

With byte offset: Tag(6)|Set(9)|Word(1)|Byte(2) =18 bits ($Byte2$ because 32-bit =4 bytes).

3. Cache Structure Design

• Organization: $512$ sets $\times$ $2$ lines/set $=1024$ lines.
• Each line: Valid(1) + Dirty(1) + Tag(6) + Data(64 bits = 4×16 bits). Optionally LRU bit per set (1 bit for 2-way).
• Data RAM: $8192$ bytes, divided into $1024$ blocks of 8 bytes.
• Tag RAM: $1024 \times 6$ bits (or $512\times2\times6$ ).
• Size: Total tag storage $\approx 1024\times6=6144$ bits.

CPU Address (17-bit word) ---> [Tag 6] [Set 9] [W 2]
                                  |       |      |
                          +-------+ +-----+ +----+
                          |         |      |    word mux 4:1
                  Tag compare (×2)  --> set decoder 512 --> selected set's 2 tags
                          | HIT if tag match & Valid=1
                          v
                    Data out (selected 16-bit word or 32-bit word)

Operation: Set field selects one of 512 sets (both ways read in parallel); Tag field compared associatively with 2 tags in set; if match, Word offset selects one of 4 words in block (or 1 of 2×32-bit words). Replacement uses LRU per set.

For exam diagram show set decoder, two comparators, $2:1$ MUX and valid/LRU bits. Numbers: 512 sets, 2 lines/set, 8 bytes/block, 9+2+6 split.

Check: Cache ratio $= 8\text{KB} / 256\text{KB}=1/32$.

Cache Mapping Techniques

Cache maps main memory blocks to cache lines. For memory address: Tag | Line/Set Index | Word/Offset. Three techniques:

1. Direct Mapping

• Rule: Each memory block $j$ maps to exactly one cache line: Line = j mod (number_of_lines)
• Address: Tag | Line | Word (e.g., 12-bit tag, 8-bit line, 6-bit word for 64-byte block)
• Hardware: One comparator per access, simple.
• Pros: Simple, cheap, fast hit time (one tag compare).
• Cons: Conflict misses high - if two blocks map to same line they thrash (even if other lines empty). No flexibility. Worst hit ratio.
• Use: Low-cost caches.

2. Fully Associative Mapping

• Rule: Any memory block can go to any cache line. No index field.
• Address: Tag | Word only. Cache stores Tag per line.
• Hardware: CAM - all tags compared in parallel (content-addressable memory) + valid bit. Replacement algorithm needed (LRU, FIFO, Random).
• Pros: Most flexible, lowest conflict misses - best hit ratio for given size. No thrashing.
• Cons: Expensive (parallel comparators for every line), slow for large cache (many comparators, high power). Replacement logic complex. Suitable only for small caches (e.g., TLB).
• Use: Small fully-associative TLB, victim caches.

3. Set-Associative Mapping (k-way)

• Compromise between 1 and 2. Cache divided into sets, each set has $k$ lines. Set = j mod (number_of_sets). Block can go to any of $k$ lines within set.
• Address: Tag | Set | Word
• Examples: 2-way, 4-way, 8-way. If $k=1$ -> Direct, if $k = lines$ -> Fully associative.
• Hardware: $k$ comparators per set (parallel within set), plus set decode.
• Pros: Good balance - reduces conflict misses greatly (e.g., 4-way removes most thrashing) with modest hardware cost. Most used in modern CPUs (L1: 4-8 way, L2/L3: 8-16 way).
• Cons: Slightly slower than direct (k compares + mux), needs replacement within set (LRU approx).
• Intel Example: 32KB 8-way L1, 1MB 16-way LLC.

Comparison Summary

Technique	Lines per block	Comparators	Hit time	Miss rate	Cost
Direct	1	1	Fastest	Highest	Lowest
2/4-way Set	k	k	Medium	Medium-Low	Medium
Fully Associative	All	All lines	Slow (large)	Lowest	Highest

Other merits/demerits:

• Capacity vs Conflict vs Compulsory misses: Direct suffers conflict; Fully associative only compulsory+capacity; Set-associative reduces conflict sharply even 2-way improves miss rate ~30-40%.
• Replacement: Direct - no choice; Associative/Set - need LRU.
• Victim Cache / Pseudo-associative: Extra small fully-associative buffer for direct-mapped conflict blocks.

Modern processors use Set-Associative (typically 4-16 way) as sweet spot; TLBs use Fully-Associative; cheap microcontrollers may use Direct-mapped.

TLB and Cache Operations for Virtual Address

Virtual (Logical) address from CPU is translated to Physical address via TLB + Page Table, then Physical address accesses Cache + Main Memory.

Address Split Example (32-bit VA, 4KB pages, 32KB 4-way cache 64B blocks)

• VA: Virtual Page Number (VPN) | Page Offset (12 bits) (20+12 for 4KB)
• PA: Physical Page Number (PPN) | Page Offset
• PA for cache: Tag | Set | Block Offset (e.g., PPN part provides Tag+Set)

Integrated Flow

CPU generates VIRTUAL ADDRESS (VA)
            |
            v
      +------------+      TLB Hit (80-99%)       +-----------------+
      |    TLB     | --------------------------->|   CACHE         |
      |(Translation|  VPN -> PPN translation    | (Physically     |
      | Lookaside  |                             |  tagged/indexed)|
      | Buffer)    |  TLB Miss -> Page Table     |                 |
      | CAM 64-1024|  walk (hardware / OS)       | Tag | Set | Off |
      +------------+  -> refill TLB              +--------+--------+
            |                                      |Hit | Miss
            | Miss                                 v      v
      +------------+                          +-------+ +--------+
      | Page Table |                          | Data to CPU | Main Memory |
      | in Memory  |                          +-------+  (fetch block -> cache)
      |(2-level)   |
      +------------+
            |
            v
      Physical Address (PA) = PPN + offset  ---> to Cache & Memory protection check

Step-by-Step Operations

1. CPU issues VA: VPN + Offset. Also permission bits checked.

2. TLB Lookup (parallel with cache - virtually indexed):

   • TLB Hit: CAM compares VPN with all entries (valid+ASID). Returns PPN in ~1 cycle. Form PA = PPN || offset.
   • TLB Miss: Hardware page table walker reads page table in memory (2-4 accesses for multi-level), brings PTE to TLB. If page not in memory -> Page Fault -> OS loads from disk.

3. Cache Access (using PA - physically indexed physically tagged PIPT, most common):

   • Decode PA: Set = (PA >> blockOffset) % sets, compare Tag array for that set (4-way).
   • Cache Hit: Data returned to CPU (~4-10 cycles L1). No memory access.
   • Cache Miss: Request goes to L2/L3 / Main Memory; block (64B) fetched to cache line (with Tag), then to CPU. TLB and cache may be accessed in parallel or sequentially depending on design:
     • PIPT: TLB first, then cache (safe, needs translation).
     • VIPT: Index with VA bits (no alias), Tag with PA -> overlaps TLB.
     • VIVT: Both virtual - needs flush on context switch.

4. Overlap / Virtually Indexed Physically Tagged (VIPT) optimization: L1 cache can start set decode using page offset bits (12 bits = not translated) while TLB translates VPN. On translation complete, tag compare uses PPN.

Protection & Extras

• TLB PTE contains Valid, Dirty, Referenced, R/W/X, U/S, Cacheability bits - checked on translation.
• On context switch, TLB flush or ASID-tagged entries avoid flush.
• Multi-level Inclusive TLB + L1/L2 Cache hierarchy: TLB miss cost 20-100 cycles; Page fault ms.

Summary: VA -> TLB (VPN->PPN) -> PA -> Cache(Tag/Set match) -> Hit? -> CPU : Memory. TLB is cache for page table, Cache is cache for memory blocks.

Hardwired vs Microprogrammed Control Unit

Aspect	Hardwired Control	Microprogrammed Control
Principle	Control signals generated by combinational circuit (logic gates, encoder/decoder, sequence counter SC, flip-flops). Fixed wiring.	Control signals generated by microprogram stored in Control Memory (ROM). Each microinstruction bit = one control signal; execution = fetching microinstructions.
Structure	Gates + Decoder (IR opcode -> D0-D7) + Timing $T_0..T_{15}$ from SC + Flip-flops (E, I) + Encoder to generate $S_2S_1S_0$, $LD_{AC}$ etc.	Control Address Register (CAR), Control Data Register (CDR), Control Memory (256x20 bits), Next-address logic / Sequencer, Control Buffer Register.
Storage	No stored program. Combinational logic.	Microprogram in ROM/RAM (firmware). $n$ microinstructions per machine instruction.
Speed	Fast (gate delay only) ~ 1-2 gate levels. Ideal for RISC, pipelined.	Slower (control memory access each microcycle, ~1 memory fetch per microinstruction)
Flexibility	Inflexible - to change instruction set need to redesign hardware/wiring. Complex to modify.	Flexible - change by updating microcode ROM; add new instruction by adding microroutine. Easy to support CISC complex instructions.
Design Cost	Complex design for many instructions (many states, hard to debug). But cheap hardware for simple ISAs.	Easier design: write microprogram akin to programming. Modular.
Complexity handling	Becomes unwieldy when instructions > ~50, addressing modes many (state explosion).	Handles complex instructions (MUL, interrupt) easily - just longer microroutine. Used in CISC (IBM 360, VAX, 68000).
Control signals	Generated as Boolean equations: e.g., $LD_{AR}= D_4T_0 + D_5T_4$	Each bit of microinstruction directly drives signal: $F_1F_2F_3, D_7..D_0$ etc.
Modification	Requires hardware change (ECN).	Can be patched via writable control store (WCS) - firmware update.
Example	RISC processors (MIPS, ARM), old 8085 hardwired, Mano basic computer simplified hardwired version.	Historical: IBM System/360, Intel microcode for x86 CISC, modern x86 decodes complex instructions to micro-ops from microcode ROM.
Control memory size	None	Need $2^k \times$ width ROM; control throughput is fetch-decode of microinstructions (horizontal vs vertical microcode).
Techniques	Sequence counter + decoder; one-hot, PLA	Horizontal (many bits per microinst, parallel) vs Vertical (encoded fields, compact) ; Wilkes model.

Diagram Analogy

• Hardwired: IR,T,I,SC -> Combinational Logic (PLA) -> 30 control lines
• Microprogrammed: IR -> Map -> CAR -> Control Memory -> CDR -> control lines; CDR.next_addr -> CAR

Horizontal vs Vertical within Microprogrammed

• Horizontal: 40-60 bits, each bit one signal - high parallelism, fast but large ROM.
• Vertical: 16-20 bits encoded, needs decoder, compact but slower.

Modern hybrid: RISC core hardwired for simple ops + microcode ROM for complex x86 instructions translated to micro-ops (e.g., Intel/AMD).

Conclusion: Use Hardwired when speed is critical and instruction set simple/small; use Microprogrammed when instruction set is complex/variable and design flexibility/upgradeability matters.

Different Ways ROM Can Be Programmed

ROM (Read Only Memory) programming refers to how data is written into ROM. Based on programmability and erasability, types are:

1. Mask Programmed ROM (MROM)

• When programmed: At time of manufacturing by manufacturer using photographic mask.
• Mechanism: Transistor connections at crosspoints defined by mask. Presence/absence of transistor = 1/0.
• Features: Non-field programmable, cheapest per unit in mass production but high setup cost, 100% non-erasable.
• Use: Firmware, character generators, microcode where volume high and code never changes.

2. PROM (Programmable ROM) - One Time Programmable (OTP)

• Mechanism: Manufactured as all 0s/1s with fusible NiCr links at each bit. User programs with PROM programmer which applies high current pulse (20-50mA, ~10-12V) to blow fuses for desired bits.
• Process: Address selected -> data applied -> programming pulse for each word.
• Features: Field programmable once, cannot be erased; if mistake chip discarded.

3. EPROM (Erasable PROM)

• Uses FAMOS transistors with floating gate storing charge.
• Programming: Electrical - with EPROM programmer, apply Vpp ~21-25V pulse to inject hot electrons into floating gate via avalanche. 0 = charged, 1 = uncharged.
• Erasing: UV light (~253.7nm) through quartz window for 15-20 min erases entire chip by photoelectric discharge. Then reprogrammable (typically ~1000 cycles).
• Types: UV-EPROM

4. EEPROM (Electrically Erasable PROM) / E²PROM

• Uses FLOTOX/ MNOS structure with thin oxide allowing Fowler-Nordheim tunneling.
• Programming & Erasing: Both electrically - no UV, no removal from circuit. Byte/word erasable using ~20V internal charge pump.
• Features: ~10^4-10^5 cycles, slower write (ms vs ns read), more expensive per bit due to 2 transistor per cell.

5. Flash Memory (Advanced EEPROM)

• Bulk/ sector erase instead of byte erase using same tunneling.
• Programming: Electrical with on-chip charge pump. Erase entire block at once (~1s), program byte/page wise.
• Features: High density, in-system programmable, ~10^5-10^6 cycles, used in SSD, pen drives, BIOS.

Summary Table:

Type	Programmability	Erasability	Volatility
MROM	Factory mask only	No	Non-volatile
PROM	Once by user (fuse)	No	Non-volatile
EPROM	User, electrical	UV whole chip	Non-volatile
EEPROM	User, electrical byte-wise	Electrical byte-wise	Non-volatile
Flash	User, electrical sector-wise	Electrical block-wise	Non-volatile

For exam, diagram of ROM array with row/column decoders and fuse/ floating gate cell should be drawn.

Challenges of Concurrent Memory Access in Parallel Processing

Multiple processors/cores accessing shared memory simultaneously creates conflicts due to true/false sharing. Key challenges:

1. Race Conditions & Data Inconsistency

Two CPUs read-modify-write same location x without synchronization:

P1: R x(5) -> +1 -> W x(6)
P2: R x(5) -> +1 -> W x(6) // lost update, expected 7

Without atomicity, final value non-deterministic.

2. Cache Coherence

Each core has private L1/L2 cache. If P1 caches x=5 and P2 updates to 6, P1 still sees stale 5. Need coherence protocol (MSI/MESI) with invalidation/update, adding bus traffic and latency.

3. Memory Consistency Model

Order in which writes by one CPU become visible to others. Sequential consistency vs weak consistency. Without fences/barriers, reordering by compiler/CPU leads to subtle bugs.

4. Synchronization Overhead

Need locks, semaphores, barriers, atomic CAS. Lock contention serializes execution, creates critical section bottleneck, reduces speedup (Amdahl). Lock granularity trade-off: fine-grain = overhead, coarse-grain = contention.

5. False Sharing

Two unrelated variables a,b in same cache line (64B). P1 writes a, P2 writes b -> line bounces between caches via invalidations despite no true sharing, degrades performance by 10-100x.

6. Memory Contention & Bandwidth

Shared bus/memory controller saturates. In UMA, all accesses via single bus -> bottleneck. In NUMA, remote memory access latency 2-3x local -> non-uniform performance, need locality optimization.

7. Deadlock / Livelock / Priority Inversion

Circular wait on locks -> deadlock. Livelock when both back-off repeatedly. Requires deadlock avoidance protocols.

8. Scalability & Coherence Traffic

Snoopy protocol broadcasts limit to ~32 cores; directory protocols add memory overhead and indirection latency for large systems.

Solution directions: MESI/MOESI + directory, atomic primitives (LL/SC), transactional memory, lock-free data structures, cache-line padding, NUMA-aware allocation.

Direct Mapped Cache - Final Block Status

Cache size $C=8$ blocks (0-7). Direct mapped: index = block mod 8.

Requests: 3,5,2,8,0,63,9,16,20,17,25,18,30,24,2,63,5,82,17,24

Trace:

#	Block	Index ($mod8$)	Action	Cache state 0-7
-	-	-	init	[-,-,-,-,-,-,-,-]
1	3	3	miss	[-,-,-,3,-,-,-,-]
2	5	5	miss	[-,-,-,3,-,5,-,-]
3	2	2	miss	[-,-,2,3,-,5,-,-]
4	8	0	miss	[8,-,2,3,-,5,-,-]
5	0	0	miss evict 8	[0,-,2,3,-,5,-,-]
6	63	7	miss	[0,-,2,3,-,5,-,63]
7	9	1	miss	[0,9,2,3,-,5,-,63]
8	16	0	miss evict 0	[16,9,2,3,-,5,-,63]
9	20	4	miss	[16,9,2,3,20,5,-,63]
10	17	1	miss evict 9	[16,17,2,3,20,5,-,63]
11	25	1	miss evict 17	[16,25,2,3,20,5,-,63]
12	18	2	miss evict 2	[16,25,18,3,20,5,-,63]
13	30	6	miss	[16,25,18,3,20,5,30,63]
14	24	0	miss evict 16	[24,25,18,3,20,5,30,63]
15	2	2	miss evict 18	[24,25,2,3,20,5,30,63]
16	63	7	hit	[24,25,2,3,20,5,30,63]
17	5	5	hit	[24,25,2,3,20,5,30,63]
18	82	2	miss evict 2	[24,25,82,3,20,5,30,63]
19	17	1	miss evict 25	[24,17,82,3,20,5,30,63]
20	24	0	hit	[24,17,82,3,20,5,30,63]

Final Cache Status

• Block 0: 24
• Block 1: 17
• Block 2: 82
• Block 3: 3
• Block 4: 20
• Block 5: 5
• Block 6: 30
• Block 7: 63

Vector form: [24, 17, 82, 3, 20, 5, 30, 63] for indices 0-7.

Hits = 3 (63,5,24); Misses = 17. No fully associative/LRU needed - direct mapped deterministic.

Paging in Memory Management

1. Definition

Paging is a non-contiguous memory allocation technique that eliminates external fragmentation. It divides both logical (virtual) address space and physical memory into fixed-size blocks:

• Pages: Fixed-size blocks of logical/virtual memory (e.g., 4 KB)
• Frames (Page Frames): Same-size blocks of physical memory
• Page Table: Data structure maintained by OS that maps page number -> frame number. Each process has its own page table base register (PTBR).

Logical address = $(p, d)$ where $p$ = page number (index into page table), $d$ = offset within page.

Physical address = $(f, d)$ where $f$ = frame number from page table entry.

Translation:

Logical Addr (e.g., 16-bit with 1K page): 
 |  page p  | offset d |
      |           |-------> offset passes unchanged
      v
 Page Table[p] -> frame f
      |
 Physical Addr = f * page_size + d

With TLB (Translation Lookaside Buffer) caching recent translations for speed.

Example: Page size 4KB, 32-bit VA: 20-bit $p$, 12-bit $d$. Logical addr 0x00403ABC : $p=0x00403$, $d=0xABC$ -> if PageTable[0x00403]=0x07F1A then physical = 0x07F1AABC.

If page not in memory, page fault occurs - OS loads page from disk (demand paging, virtual memory).

2. Diagram

  Process Virtual Memory              Page Table               Physical Memory
  +---------------+               +------------+             +---------------+
  | Page 0        |-------------->| Frame 2    |------------>| Frame 0       |
  +---------------+               +------------+             +---------------+
  | Page 1        |-------------->| Frame 5    |------------>| Frame 1       |
  +---------------+               +------------+             +---------------+
  | Page 2        |               | invalid    |             | Frame 2: Pg0  |
  +---------------+               +------------+             +---------------+
  | Page 3        |-------------->| Frame 1    |             | Frame 3       |
  +---------------+               +------------+             +---------------+
                                                                 Frame 5: Pg1

3. Advantages of Paging

1. No External Fragmentation: Any free frame can be allocated to any page; memory is used efficiently. Compaction not needed.

2. Supports Virtual Memory: Allows process size > physical memory via demand paging; only needed pages loaded, rest on disk.

3. Simplifies Memory Management: Fixed-size blocks easy to manage with free-frame list; allocation/deallocation fast.

4. Allows Sharing: Shared pages (common code/libraries) can map to same frame in different processes - saves memory.

5. Memory Protection: Page table entry contains protection bits (R/W/X, user/supervisor) - prevents illegal access; invalid entries cause trap.

6. Supports Multiprogramming: Multiple processes can reside in fragmented physical frames simultaneously.

7. Efficient Swapping: Swapping whole pages is easy; copy-on-write optimization possible.

Disadvantage (for completeness): Internal fragmentation (last page may be partially unused ~ half page average), and page table overhead (+ TLB needed) and extra memory reference if TLB miss (2 accesses).

Differentiate between Expansion and Extension of Memory

Although both are techniques to increase memory capacity using smaller chips, they address different dimensions: depth (words) vs. width (bits). Sometimes textbooks use the terms interchangeably, but standard distinction is:

Aspect	Memory Expansion (Word/Depth Expansion)	Memory Extension (Bit/Width Extension)
Goal	Increase number of words (depth) e.g., $1K\times8$ -> $4K\times8$	Increase word length / bits per word (width) e.g., $1K\times4$ -> $1K\times8$
What is increased	Address space (more addresses)	Data bus width (more bits per address)
Address lines	Extra MSB lines needed for chip selection; address split into chip-select + intra-chip address	Same address lines to all chips; no extra address decoding for width
Data lines	Data width unchanged; chips' data buses share via tri-state/bus, only one active at a time	Data buses concatenated; each chip contributes part of word, all active simultaneously
Chip Select (CS) logic	Decoder required: $m$-to-$2^{m}$ decoder driven by high-order address bits enables one chip at a time	No decoder: CS of all chips tied together (common CS), all chips enabled together
Connection	Address buses common, data buses common (wired-OR via tri-state), CS decoded	Address buses common, data buses split/combined, CS common
Example	Four $1K\times8$ to make $4K\times8$: <br> A0-A9 to all chips, A10-A11 -> 2:4 decoder -> CS0-CS3. Data D0-D7 common bus.	Two $1K\times4$ to make $1K\times8$: <br> A0-A9 to both, CS0=CS1= CS, Chip1 D0-D3 -> system D0-D3, Chip2 D0-D3 -> system D4-D7.
Diagram	CPU A0-A9 ----> all chips A0-A9<br>`CPU A10-A11 -> Decoder -> CS0	CS1
Analogy	Adding more pages to a book (more pages)	Widening each page (more columns per page)

Diagrams

Expansion (Depth) $2K\times8$ using $1K\times8$ x2:

          A0-A9 +----------------+
      +---------->| 1Kx8 Chip0   |----> D0-D7 --+
      |           +----------------+            | Tri-state
A0-A9-+           +----------------+            +--> System D0-D7
      +---------->| 1Kx8 Chip1   |----> D0-D7 --+
      |           +----------------+
A10 --> Decoder -> CS0 (A10=0), CS1 (A10=1)  (only one active)

Extension (Width) $1K\times8$ using $1K\times4$ x2:

A0-A9 ------> +--------+  D0-D3 ----> System D0-D3
              |1Kx4 C0 |
CS   -------->|        |
              +--------+
A0-A9 ------> +--------+  D0-D3 ----> System D4-D7
              |1Kx4 C1 |
CS   -------->|        |
              +--------+

Combined: To make $4K\times16$ from $1K\times8$ chips, do both: need 4 groups (expansion) each with 2 chips in parallel (extension) = 8 chips.

In short: Expansion = more words, Extension = wider words. Both together give arbitrary $M \times N$ memory from $m \times n$ chips.

Solution - RAM Chip Organization & SRAM vs DRAM

A) Organization of a Typical RAM Chip:

A RAM chip of size $2^k \times m$ (e.g., $1024 \times 8$, $16K \times 1$) has:

• Memory Array: Matrix of memory cells arranged in rows $\times$ columns. For $1024 \times 8$, 8192 cells (128 rows $\times$ 64 columns).
• Address Decoder: $k$ address lines decoded to select one row/word. Row decoder selects row, column decoder selects bit group. Example: 10 lines for 1024 words (5 for row, 5 for column or 10 for row).
• Memory Cells: Each cell stores 1 bit (flip-flop for SRAM, capacitor+transistor for DRAM).
• Chip Select (CS) / Chip Enable (CE): Enables chip only when selected - allows building larger memories by combining chips.
• Read/Write Control (RD/WR, WE, OE): $W=0$ write enabled, $W=1$ read.
• Bidirectional Data Lines ($I/O_{0}..I/O_{m-1}$): Input data for write, output for read - tri-state buffers. $m$ lines = word length.
• Address Lines ($A_0..A_{k-1}$): Input address.

Construction of larger memory: Using chip select and address decoding. Eg., to make $2K \times 8$ from two $1K \times 8$ chips, $A_{10}$ drives CS via decoder.

Block diagram: Address Lines -> Row/Column Decoder -> Memory Cell Array -> Sense Amplifiers / Write Drivers -> Data Lines. Control logic coordinates CS, OE, WE.

B) Difference between Static RAM (SRAM) and Dynamic RAM (DRAM):

Parameter	Static RAM (SRAM)	Dynamic RAM (DRAM)
Cell Design	6 transistors (bistable latch/flip-flop)	1 transistor + 1 capacitor (charge storage)
Storage	Holds data as long as power on (static)	Charge leaks, needs periodic refresh every ~2ms
Refresh Circuit	Not needed	Required (refresh controller, ROW strobing)
Density	Low (6T per bit)	High (1T per bit) - 4-5x denser
Speed	Fast (access 1-10 ns, no refresh overhead)	Slower (access 50-70 ns + refresh)
Power	More power per cell, but no refresh power	Less per cell, but refresh consumes power
Cost	Costly per bit	Cheap per bit
Use	Cache (L1,L2,L3), fast buffers, registers	Main memory (DDR SDRAM)
Volatility	Volatile (like DRAM)	Volatile

Summary: SRAM = speed, DRAM = density & cost-effectiveness for large memory.

Typical RAM Chip Pin Diagram: $A_0-A_9$, $D_0-D_7$, $\overline{CS}$, $\overline{WE}$, $\overline{OE}$, $V_{cc}$, $GND$.

Address space $8K=2^{13}$, memory $4K$, page $1K \Rightarrow 8$ virtual pages (0-7), $4$ page frames. Reference string length $15$:

$$4,2,0,1,2,6,1,4,0,1,0,2,3,5,7$$

Table shows resident set after each reference. F = page fault.

(i) FIFO - evict oldest loaded page

Ref	Hit/Fault	Resident set (4 frames)	Evicted	FIFO queue (oldest→newest)
4	F	4, -, -, -	-	[4]
2	F	4, 2, -, -	-	[4,2]
0	F	4, 2, 0, -	-	[4,2,0]
1	F	4, 2, 0, 1	-	[4,2,0,1]
2	Hit	4, 2, 0, 1	-	[4,2,0,1]
6	F	6, 2, 0, 1	4	[2,0,1,6]
1	Hit	6, 2, 0, 1	-	[2,0,1,6]
4	F	6, 4, 0, 1	2	[0,1,6,4]
0	Hit	6, 4, 0, 1	-	[0,1,6,4]
1	Hit	6, 4, 0, 1	-	[0,1,6,4]
0	Hit	6, 4, 0, 1	-	[0,1,6,4]
2	F	6, 4, 2, 1	0	[1,6,4,2]
3	F	6, 4, 2, 3	1	[6,4,2,3]
5	F	5, 4, 2, 3	6	[4,2,3,5]
7	F	5, 7, 2, 3	4	[2,3,5,7]

• Faults $=10$, Hits $=5$, Hit ratio $5/15=33.3\%$.
• Final resident pages {2,3,5,7}.

(ii) LRU - evict least recently used

Maintains recency; on hit update timestamp.

Ref	Hit/Fault	Resident set	Evicted (LRU)
4	F	4, -, -, -	-
2	F	4, 2, -, -	-
0	F	4, 2, 0, -	-
1	F	4, 2, 0, 1	-
2	Hit	4, 2, 0, 1	- (2 MRU)
6	F	6, 2, 0, 1	4 (LRU)
1	Hit	6, 2, 0, 1	- (1 MRU)
4	F	6, 2, 4, 1	0 (LRU, not used since time 3)
0	F	6, 0, 4, 1	2 (LRU)
1	Hit	6, 0, 4, 1	-
0	Hit	6, 0, 4, 1	-
2	F	2, 0, 4, 1	6 (LRU)
3	F	2, 0, 3, 1	4 (LRU)
5	F	2, 0, 3, 5	1 (LRU)
7	F	2, 7, 3, 5	0 (LRU)

• Faults $=11$, Hits $=4$, Hit ratio $26.7\%$.
• Final resident pages {2,3,5,7} (same final set but different intermediate eviction order; LRU has one extra fault).

Note for this string FIFO outperforms LRU by 1 fault - shows FIFO not always worse, but LRU generally avoids Belady's anomaly and is stack-optimal.

Solution - Page Fault and Page Replacement Algorithms (14M)

What is a Page Fault?
In virtual memory with demand paging, pages are loaded from secondary storage (disk) to main memory only when needed. A page fault is an exception (trap) that occurs when a running process tries to access a page that is currently not present in main memory (valid bit = 0 in Page Table or TLB miss). The MMU detects this via page table entry's present/absent bit and raises interrupt #14 (x86).

What does it signify?

• Indicates miss in main memory hierarchy; required page (or segment of program/data) is still on disk (swap space).
• Triggers OS fault handler: OS must block the process, allocate a free frame, read the page from disk into frame (I/O), update page table (frame number, valid=1), and restart the faulting instruction.
• High frequency = thrashing if insufficient frames (working set > memory).
• Counted as overhead: interrupt + context switch + disk I/O (ms) >> memory access (ns).

Page fault handling steps:

1. Trap to OS, save registers.
2. Check if reference was legal (segmentation violation vs valid page on disk).
3. Find free frame (or victim via replacement algorithm if none free).
4. If victim dirty, write back to disk.
5. Read required page from disk into frame (DMA).
6. Update page table, TLB invalidated.
7. Restart process at faulting instruction.

Page Replacement Algorithms - when memory is full (no free frame), which victim page to evict:

1. FIFO (First-In First-Out):

• Replaces page that has been in memory longest (queue). Simple via FIFO queue.
• Belady's Anomaly: More frames can increase faults! Not stack algorithm.
• Example: Reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames -> 9 faults.

2. Optimal (OPT / MIN) - Theoretical:

• Replaces page that will not be used for longest period in future (furthest next use). Gives minimum faults, used as benchmark.
• Impossible to implement perfectly (requires future knowledge), but approximated.
• Example: Same string -> 7 faults (optimal).

3. LRU (Least Recently Used):

• Replaces page that has not been used for longest time in past. Exploits locality.
• Implementation: counter/timestamp or stack, or approximation via reference bits.
• Good performance, close to Optimal. Stack algorithm (more frames never hurts).
• Example: With same string -> 10 faults.

4. Approx. LRU variants:

• NRU / Clock (Second Chance): Circular queue with reference bit R. Give second chance if R=1 then clear and rotate; if R=0 replace. Efficient.
• Aging / LFU / MFU: Least Frequently Used (count accesses) / Most Frequently Used - but LFU suffers cache pollution.

5. LIFO / Random:

• LIFO replaces last loaded; Random picks random victim - simple, avoids Belady but unpredictable.

Comparison Table:

Algorithm	Needs future?	Overhead	Anomaly	Performance
FIFO	No	Low	Yes	Poor
Optimal	Yes	-	No	Best (ideal)
LRU	No	High (stack)	No	Good
Clock	No	Low	No	Good approx.
LFU	No	Medium	No	Depends

Selection criteria: Fault rate, implementation cost, hardware support (R and M bits in page table entry help Clock/LRU approximation). Modern OS uses Clock (enhanced second chance with Dirty bit) or LRU approximation with aging.

Dirty bit: If victim page modified (M=1), must write back before replacement - double I/O cost, so some algorithms prefer clean victims (NRU class 0: R=0 M=0).

Swapping in Memory Management

Definition

Swapping is the technique of temporarily moving a process (whole or part) from main memory (RAM) to secondary storage (swap space/backing store) and bringing it back later for execution.Introduced in early time-sharing systems (Atlas, UNIX) to support multiprogramming beyond physical memory size.

Stored image on disk is called swap-out; retrieving is swap-in (roll-out / roll-in).

How it Works

1. Scheduler detects low free frames or blocked process waiting for I/O.
2. Swapper (mid-term scheduler) selects victim process → copies its entire address space (code, data, stack, PCB) to contiguous swap area on disk.
3. Page tables / base-limit registers updated, frames freed.
4. Later when memory available and process scheduled, swapper reads image back (possibly at different physical address → requires relocation / dynamic binding via relocation register).

Modern systems swap pages/segments, not whole processes (demand paging is a lazy swap).

Diagram: Main Memory [P1|P2|P3|hole] ↔ Disk Swap Area [P4(swapped)] ↔ Scheduler

Why Used? (Objectives)

• Multiprogramming degree: Run more processes than fits in RAM. Example $8$ processes $\times 200KB =1.6MB$ on $1MB$ RAM via time-multiplexing.
• Memory compaction / fragmentation removal: Swapping out creates large contiguous free blocks, reducing external fragmentation.
• Priority & scheduling: Swap out low-priority/blocked processes to give room to urgent ones (mid-term suspend).
• Fairness & time-sharing: Quantum expired → swap out to let next process in.
• Emergency handling: Low-memory handler frees RAM quickly.
• I/O overlap & backing store for paging: Pages not resident stay on disk.

Types

• Whole-process swapping: Simple but heavy I/O (entire address space).
• Page swapping (paging): Swap only pages, more efficient, foundation for virtual memory.
• Segment swapping: Similar for segmented systems.

Cost & Issues

• Transfer time: Main cost $T_{swap}=2\times (size/transfer-rate) + seek/latency$. e.g. $10MB/100MBps=100ms$. So swap only if process idle for longer.
• Blocked I/O: Process with pending I/O or pinned pages cannot be swapped.
• Thrashing risk: Excessive swapping degrades CPU utilization → need working set / locality.

Today pure swapping rare; virtual memory + demand paging is generalized swapping with finer granularity, and swap file/partition remains as overflow store.

Virtual Memory

Definition: Virtual memory is a memory management technique that makes an application think it has contiguous, large private address space, independent of physical RAM size, by automatically moving data between RAM and disk (swap/backing store) via paging/segmentation. It gives illusion of virtual size >> physical size.

OS + MMU provide address translation per reference; only active working set stays in RAM, rest on disk, loaded on demand (page fault).

Why Virtual Memory?

• Run programs larger than physical memory.
• Multiprogramming isolation & protection (each process virtual space).
• Simplified linking/loading, no external fragmentation (with paging).

Logical (Virtual) vs Physical Address - Roles

Logical / Virtual Address - Generated by CPU before translation.

• Address seen by process/compiler: e.g. $32$-bit virtual → $4GB$ per process ($2^{32}$), $48$-bit in x86-64.
• Partitioned: | Virtual Page Number (VPN) | Offset | (offset = page size bits; e.g. $4KB$ page → $12$ bits offset).
• Never used to access RAM directly; goes through MMU.
• Contiguous from process view; sparse vs file mapping allowed.
• Protect bits checked per virtual page.

Physical Address - Actual address on RAM bus after translation.

• After MMU/TLB lookup: | Physical Frame Number (PFN) | Offset |.
• Range limited by installed RAM: e.g. $1GB$ RAM → $30$-bit physical.
• Used by cache/memory controller.
• Multiple virtual pages (even from different processes) can map to same physical frame (shared memory) or one virtual page can map nowhere (paged out → page fault).

Translation flow:

CPU issues VA ──► TLB (VPN→PFN) hit? ──► PA to cache/RAM
                  │ miss
                  └─► Page Table walk (in RAM) ──► PFN + valid bit
                               │ invalid (not resident)
                               └─► Page Fault → OS loads frame from disk, updates table, retries

Example: VA 0x00403F12 ($VPN=0x403, offset=0xF12$) with $4KB$ pages, page table maps $VPN\ 0x403 → PFN\ 0x1A2$ → PA 0x1A2F12.

Key distinction: Logical addresses give program portability & protection; physical addresses give actual storage location. Compiler/linker deals in logical; MMU/OS manages physical. Without translation, process would see raw RAM limits and fragmentation.

Modern extensions: Demand paging, copy-on-write, memory-mapped files, TLB, multi-level page tables all build on this split.

Cache mapping decides how a main memory block maps to cache line(s). Let cache have $2^c$ lines, memory have $2^m$ blocks, address = Tag + Index/Set + Word/Offset.

1. Direct Mapping

Each memory block $i$ maps to exactly one cache line: $line = i \mod (\text{no. of lines})$.
Address split: $|Tag| + |Line| + |Word|$.
e.g., 4096 lines need 12 line bits. With 64-word blocks (6 bits), address = Tag(remaining)+12+6.

• Search: Compare only that line's tag - fast, simple.
• Miss: Replacement is forced, no choice.
• Drawback: Thrashing - two blocks mapping to same line continuously collide even if cache has free lines.

2. Associative (Fully Associative) Mapping

Any memory block can go to any cache line. Address = $|Tag| + |Word|$ only; no line field.

• Search: Content-addressable memory (CAM) compares incoming Tag with all line tags in parallel.
• Replacement: Need algorithm - LRU, FIFO, Random.
• Advantage: No collision thrashing, best hit rate.
• Drawback: Expensive comparators for all lines, slow for large cache.

3. Set-Associative Mapping

Compromise. Cache divided into $S$ sets, each set has $k$ lines ($k$-way). Block $i$ maps to $set = i \mod S$, can occupy any of $k$ lines within set.

• Address: $|Tag| + |Set| + |Word|$.
  Example $k=2$, 4096 lines → 2048 sets → 11 set bits. Address = Tag+11+6.

• Search: Index set via Set field, associatively compare Tag among $k$ lines in that set only.

• Replacement: Choose within set (LRU).

• Special cases: $k=1$ → Direct, $k = \text{no. of lines}$ → Fully Associative.

• Tradeoff: Hit rate improves with larger $k$ but cost increases. Typical $k=2,4,8$.

Replacement policies (LRU, LFU, FIFO) apply to associative and set-associative when set is full. Write policies: Write-through + write-allocate/no-allocate, Write-back.

Cache Memory Organization (7 Marks)

1. Introduction:
Cache is a small, very fast SRAM between CPU and main memory that exploits locality of reference (temporal & spatial) to reduce average access time. CPU first checks cache; on hit data returned quickly, on miss block fetched from main memory.

Hierarchy: CPU ↔ L1 ↔ L2 ↔ Main Memory ↔ Disk. Cache stores blocks/lines consisting of tag + data block + valid/dirty bits.

2. Mapping Techniques:
Mapping determines where a main memory block can be placed in cache.

a) Direct Mapping:
Each memory block $j$ maps to exactly one cache line: Cache Line = j mod m where $m$ = number of lines. Address split: | Tag | Line | Word |.

• Advantage: Simple hardware, low cost, fast lookup.
• Disadvantage: High conflict misses – two blocks mapping to same line thrash even if other lines empty. Hit ratio lower.

b) Fully Associative Mapping:
Any block can go into any line. Address split: | Tag | Word |. Tag compared associatively with all line tags in parallel.

• Advantage: Most flexible, minimum conflict misses, best hit ratio.
• Disadvantage: Expensive – requires associative CAM comparator for every line, slow for large cache.

c) k-Way Set-Associative Mapping: Compromise.
Cache divided into $v = m/k$ sets, each set has $k$ lines. Block $j$ maps to Set = j mod v, can occupy any of $k$ lines within that set. Address split: | Tag | Set | Word |.
Example: 2-way, 4-way. Direct ($k=1$) and Fully Associative ($k=m$) are extremes.

• Advantage: Reduces conflicts while keeping hardware manageable. Widely used (e.g., Intel uses 8-way/16-way).
• Disadvantage: Moderate hardware complexity.

3. Replacement Algorithms (needed when set is full):

• LRU (Least Recently Used): Replaces block not used longest time. Best hit ratio, implemented via counters/stack. Common.
• FIFO: Replaces first-loaded block. Simple but not optimal, suffers Belady effect.
• LFU: Replaces least frequently used.
• Random: Random selection, simple hardware, average performance.

4. Write Policies (on write hit):

• Write-Through: Data written to both cache and main memory simultaneously. Simple, consistent but high bus traffic. Uses write buffer.
• Write-Back (Copy-Back): Write only to cache and set dirty bit. Block written back to memory only on replacement. Less traffic, better performance but coherence complex.
• On write miss: Write-Allocate (fetch block to cache then write) vs No-Write-Allocate (write directly to memory).

Performance: $T_{avg}=h \cdot T_c + (1-h)\cdot T_m$ where $h$=hit rate.