Unit 4 · Memory Management

Lecture 9: Cache organisation & locality of reference

Learning outcomes

Describe cache memory organisation and the principle of locality of reference.

Lecture Notes

Main content

Exam-Oriented Add-On: Memory Management and Related Numericals

This section adds focused theory and solved examples for common university-style questions on page replacement, partitioning, paging hardware, fragmentation, virtual memory, thrashing, locality of reference, and a few linked topics from scheduling and disk management.

Solved Numericals Page Replacement Partitions TLB Thrashing Disk Scheduling

1. Purpose of a Page Replacement Algorithm

A page replacement algorithm is needed when a page fault occurs and all available memory frames are already occupied. In that situation, the operating system must choose one page currently in memory to remove so that the required page can be loaded.

Main purpose: Select a victim page so that future page faults are minimized and the system keeps performing efficiently.

Good page replacement improves demand-paging performance. Poor page replacement can increase the page-fault rate and may even contribute to thrashing. The lecture plan also places FIFO, Optimal, and LRU exactly in the page-replacement section of the course. :contentReference[oaicite:3]{index=3}

Worked Example: Limited-lookahead Optimal Replacement

In this modified optimal algorithm, the operating system predicts correctly only up to the next 4 page references (including the current reference). Page sequence:

1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4

Number of frames = 3, initially empty.

Step	Page	Status	Frames after reference	Decision
1	1	Fault	[1]	Load 1
2	3	Fault	[1, 3]	Load 3
3	2	Fault	[1, 3, 2]	Load 2
4	4	Fault	[4, 3, 2]	Replace 1
5	2	Hit	[4, 3, 2]	—
6	3	Hit	[4, 3, 2]	—
7	1	Fault	[4, 1, 2]	Replace 3
8	2	Hit	[4, 1, 2]	—
9	4	Hit	[4, 1, 2]	—
10	3	Fault	[4, 1, 3]	Replace 2
11	1	Hit	[4, 1, 3]	—
12	4	Hit	[4, 1, 3]	—

Total page faults = 6

2. Multiprogramming with Variable Partitions

2.1 Discussion

In multiprogramming with variable partitions, memory is not divided into fixed blocks beforehand. Instead, the operating system allocates a partition according to the actual size of each process. When a process terminates, its memory becomes a free hole that can be reused for another process.

This improves memory utilization because space is not wasted inside large fixed partitions assigned to small processes. However, the system may suffer from external fragmentation because free memory gets split into scattered holes.

How it improves utilization: memory is allocated approximately as needed, so less space remains idle inside allocated blocks.

2.2 Fixed Partitions vs Variable Partitions

Basis	Fixed Partitioning	Variable Partitioning
Partition size	Predefined and fixed	Created dynamically according to process size
Memory waste	Can waste space inside partitions	Usually less internal waste
Fragmentation type	Mainly internal fragmentation	Mainly external fragmentation
Flexibility	Low	High
Compaction need	Usually not required	May be required
Complexity	Simpler	More complex allocation management

2.3 Internal and External Fragmentation

Type	Meaning	Where it commonly appears
Internal Fragmentation	Unused space exists inside an allocated block.	Fixed partitioning, paging last page
External Fragmentation	Total free memory exists, but it is scattered into small noncontiguous holes.	Variable partitioning, pure segmentation

3. Demand Paging Numerical: Maximum Page Table Entries

Consider a demand paging system with:

Logical address size = 32 bits
Physical address size = 20 bits
Page size = 2048 bytes = 2¹¹

Number of bits used for page offset:

Offset bits = log₂(2048) = 11

Therefore, page number bits in the logical address:

Page number bits = 32 − 11 = 21

Maximum number of logical pages, and hence maximum number of page-table entries:

2²¹ = 2,097,152

Maximum number of page-table entries = 2,097,152

4. Paging and Segmentation: Compare and Contrast

Aspect	Paging	Segmentation
Basic unit	Fixed-size page	Variable-size logical segment
Programmer view	Not natural	Natural and logical
Fragmentation	Internal fragmentation	External fragmentation
Protection	Page-level bits	Segment-level base, limit, permissions
Best suited for	Modern virtual-memory systems with efficient frame management	Systems needing logical modular protection and sharing

Short conclusion: Paging is usually better for efficient physical-memory management, while segmentation is better for representing the logical structure of programs.

5. Virtual Memory Concepts

Virtual memory allows a process to execute even when the whole process is not in main memory. The process sees a large logical address space, while only the needed pages are kept in RAM and the rest stay on backing store.

The syllabus explicitly includes virtual memory, demand paging, page replacement algorithms, thrashing, and locality of reference in Unit IV. :contentReference[oaicite:4]{index=4}

5.1 Important ideas

Logical address space: memory seen by the process
Physical address space: actual RAM addresses
Page table: maps virtual pages to physical frames
Demand paging: loads a page only when referenced

5.2 Physical vs Logical Address Space

Type	Meaning
Logical Address Space	The set of addresses generated by the CPU for a process.
Physical Address Space	The set of actual addresses in main memory.

6. Thrashing and Locality of Reference

The OS text explains that programs move from locality to locality, and that if a process is given enough frames for its current locality, page faults stay low; if not, the process can thrash. Locality is also the unstated principle behind caching. :contentReference[oaicite:5]{index=5} :contentReference[oaicite:6]{index=6}

6.1 Thrashing

Thrashing is a condition in which the system spends more time bringing pages into memory than executing useful instructions.

6.2 Locality of reference

Locality of reference means a process tends to access a small group of pages repeatedly for some time. This is why caches work and why virtual memory is practical. If accesses were completely random, caching would be useless. :contentReference[oaicite:7]{index=7}

Type of locality	Meaning	Example
Temporal	A recently used item is likely to be used again soon.	Loop counter reused in each iteration
Spatial	Nearby items are likely to be accessed soon.	Sequential array traversal

7. Paging Hardware Support Using TLB

The lecture plan explicitly lists paging hardware support (TLB) in the memory-management module. :contentReference[oaicite:8]{index=8}

A TLB (Translation Lookaside Buffer) is a small, fast associative memory that stores recently used page-table entries. If the page number is found in the TLB, address translation is very fast. Otherwise, the system must consult the page table in main memory.

Figure: On a TLB hit, translation is fast; on a miss, the page table in memory must be checked.

7.1 Hit ratio and miss ratio

Hit ratio (h): fraction of references found in associative registers / TLB
Miss ratio: 1 − h

Worked Example: Required Hit Ratio

Given:

Associative-register access time = 100 ns
Main-memory page-table access time = 800 ns
Required effective access time = 125 ns

Using the simplified model:

EAT = h × 100 + (1 − h) × 800

125 = 100h + 800 − 800h
125 = 800 − 700h
700h = 675
h = 675 / 700 = 0.9642857

Required hit ratio ≈ 0.9643 = 96.43%

8. Demand Paging Numerical with FIFO, LRU, and Optimal

Page-reference string:

0, 9, 0, 1, 8, 1, 8, 7, 8, 7, 1, 2, 8, 2, 7, 8, 2, 3, 8, 3

Number of page frames = 3

Final answers

Replacement algorithm	Number of page faults
FIFO	8
LRU	9
Optimal	7

Why Optimal is best

Optimal replacement always removes the page whose next use lies farthest in the future, so it gives the minimum possible page-fault count for a given reference string and frame count.

9. Multilevel Feedback Queue Scheduling (MLFQ)

The lecture plan lists Multilevel Feedback Queue in the scheduling module. :contentReference[oaicite:9]{index=9}

MLFQ is a CPU-scheduling algorithm in which processes move between multiple queues based on their behavior. Short and interactive jobs are kept in higher-priority queues, while CPU-bound jobs gradually move to lower-priority queues.

Higher queues usually use smaller time quantum.
Lower queues usually use larger time quantum or FCFS.
A process using too much CPU gets demoted.
A starving process may be promoted by aging.

Main strength: MLFQ favors interactive jobs while still allowing long jobs to progress.

10. Disk Scheduling Example

Disk scheduling is part of the later storage module in your lecture plan. :contentReference[oaicite:10]{index=10}

Track requests:

45, 20, 90, 10, 50, 60, 80, 25, 70

Initial head position = 49

Assumption for SCAN / C-SCAN / LOOK: head initially moves toward the higher-numbered tracks. For SCAN and C-SCAN, assume disk tracks range from 0 to 99.

Algorithm	Service order	Total head movement
SSTF	50, 45, 60, 70, 80, 90, 25, 20, 10	131
SCAN	50, 60, 70, 80, 90, 99, 45, 25, 20, 10	139
C-SCAN	50, 60, 70, 80, 90, 99, 0, 10, 20, 25, 45	194
LOOK	50, 60, 70, 80, 90, 45, 25, 20, 10	121

Observation: Under the stated assumption, LOOK gives the least head movement here because it reverses at the last actual request instead of going all the way to the physical end of the disk.

11. Quick University-Style Answers

Purpose of page replacement algorithm: choose a victim page when memory is full so that future page faults are minimized.

Variable partitioning: improves memory utilization by allocating memory according to process size, but suffers from external fragmentation.

Maximum page-table entries: for 32-bit logical address and 2 KB page size, entries = 2²¹ = 2,097,152.

Demand paging fault counts with 3 frames: FIFO = 8, LRU = 9, Optimal = 7.

Required TLB hit ratio for 125 ns EAT: about 96.43%.