OS — Memory Management Notes

OPERATING SYSTEMS
Memory Management: Paging, Segmentation & Virtual Memory

Detailed Exam Notes for 14-Mark Questions

Topics Covered: Paging | Segmentation | Segmentation with Paging | Virtual Memory | Demand
Paging | Page Replacement Algorithms

Prepared as a complete revision guide — definitions, diagrams (described), formulas, solved numericals and
comparison tables.

Page 1
 OS — Memory Management Notes

Table of Contents
1. Paging........................................................................................................................................ 3
2. Segmentation.............................................................................................................................6
3. Segmentation with Paging......................................................................................................... 8
4. Virtual Memory Concepts........................................................................................................10
5. Demand Paging........................................................................................................................ 12
6. Page Replacement Algorithms.................................................................................................14
7. Likely 14-Mark Exam Questions (Quick Reference)..................................................................21

Page 2
 OS — Memory Management Notes

1. Paging

1.1 Concept and Need

Paging is a memory management technique that eliminates the need for contiguous allocation of
physical memory and thus avoids the problem of external fragmentation. In paging, physical memory
is divided into fixed-size blocks called frames, and logical (virtual) memory is divided into blocks of the
same fixed size called pages. The page size is always a power of two (commonly 4 KB), which simplifies
the hardware calculation of addresses.
When a process is to be executed, its pages are loaded into any available frames in physical memory
— the frames need not be contiguous. This separation of the programmer's logical view of memory
from the actual physical memory is the key idea behind paging.

1.2 Address Translation

Every logical address generated by the CPU is split by the hardware into two parts:
• Page Number (p): used as an index into the page table. The page table contains the base
address of each page in physical memory (i.e., the frame number).
• Page Offset (d): combined with the base address to define the actual physical address that
is sent to the memory unit. The offset is the same for both logical and physical address since
the frame size equals the page size.
Physical Address = (Frame Number × Page Size) + Page Offset
If the logical address space size is 2^m and the page size is 2^n, then the higher-order (m − n) bits of
the logical address designate the page number, and the lower-order n bits designate the page offset.

Diagram (described): Paging Address Translation

CPU generates Logical Address → split into (Page Number p | Offset d) → 'p' indexes the Page Table →
Page Table returns Frame Number f → Physical Address is formed as (f, d) → sent to Physical Memory.
The Page Table itself resides in main memory, and a special CPU register called the Page Table Base
Register (PTBR) points to it.

1.3 Hardware Support — Translation Look-aside Buffer (TLB)

Since the page table is stored in main memory, every logical-to-physical address translation would
normally require two memory accesses — one for the page table and one for the actual data. To
speed this up, modern CPUs use a small, fast-lookup hardware cache called the Translation Look-aside
Buffer (TLB). The TLB stores recently used page-number to frame-number mappings.
1. CPU generates a logical address with page number p.
2. The TLB is searched in parallel for p. If found (a TLB hit), the frame number is obtained
instantly.
3. If not found (a TLB miss), the page table in memory is consulted, the frame number is
retrieved, and the (p, f) pair is added to the TLB for future use.

Page 3
 OS — Memory Management Notes

Effective Access Time (EAT) is used to measure the performance gain from the TLB:
EAT = (Hit Ratio × (TLB time + Memory time)) + (Miss Ratio × (TLB time + 2 ×
Memory time))
Solved Example: Suppose TLB search time = 20 ns, memory access time = 100 ns, and hit ratio = 80%.
Then EAT = 0.8 × (20 + 100) + 0.2 × (20 + 200) = 0.8 × 120 + 0.2 × 220 = 96 + 44 = 140 ns. Without a TLB,
every access would cost 200 ns (two memory accesses), so the TLB clearly improves performance.

1.4 Protection and Sharing in Paging

• Valid–Invalid Bit: Each page table entry has a valid/invalid bit. 'Valid' means the page
belongs to the process's logical address space and is legal; 'invalid' means the page is not
part of the process's address space, and any reference traps to the OS.
• Read/Write/Execute Bits: Extra protection bits attached to each frame in the page table
indicate whether a page can be read, written, or executed, allowing fine-grained protection.
• Page Sharing: Reentrant (non-self-modifying) code, such as shared libraries or common
editor/compiler code, can be shared among multiple processes by mapping multiple page
table entries from different processes onto the same physical frames, saving memory.

1.5 Structure of the Page Table

(a) Hierarchical (Multilevel) Paging
Modern systems support very large logical address spaces (2^32 to 2^64), so a single page table
would itself become too large to keep entirely in memory. The solution is to page the page table itself,
creating a two-level (or multi-level) paging scheme.
In a two-level scheme, the logical address is divided into three parts: an outer page number p1, an
inner page number p2, and an offset d. p1 indexes an outer page table whose entries point to inner
page tables; p2 then indexes the appropriate inner page table to obtain the actual frame number.
Logical Address = (p1 | p2 | d)
(b) Hashed Page Tables
Commonly used for address spaces larger than 32 bits. The virtual page number is hashed into a page
table; each entry in this hash table contains a linked list of elements that hash to the same location,
each storing the virtual page number, the mapped frame number, and a pointer to the next element.
Searching involves hashing the virtual page number and walking the chain to find a match.

(c) Inverted Page Tables

A standard page table has one entry per page in the logical address space, which wastes space when
most of that space is unused. An inverted page table instead has one entry per physical frame,
recording which (process-id, page-number) pair occupies that frame. This dramatically reduces the
memory needed to store the table, but lookups become slower since the table must be searched by
frame content rather than indexed directly — often mitigated using a hash table.

Page 4
 OS — Memory Management Notes

1.6 Advantages and Disadvantages of Paging

Advantages Disadvantages
No external fragmentation — any free frame can Internal fragmentation in the last page of a process
hold any page if it does not exactly fill a frame
Simplifies allocation — free frames can be tracked Page table itself consumes memory, more so for
with a simple list/bitmap large address spaces
Allows non-contiguous allocation; logical memory Extra memory reference for page table lookup
can exceed contiguous physical blocks (mitigated by TLB, but TLB miss adds overhead)
Supports sharing of code/data pages between Multilevel/hashed/inverted tables add translation
processes complexity
Exam Tip: For a 14-mark question on paging, always include: definition, diagram description, address
translation formula, TLB and EAT calculation, page table types, and advantages/disadvantages — this
structure alone can fill a full answer.

Page 5
 OS — Memory Management Notes

2. Segmentation

2.1 Concept and Need

Segmentation is a memory-management scheme that supports the programmer's/user's view of
memory, rather than treating memory as one flat array of bytes. A program is naturally a collection of
logical units such as the main program, functions/subroutines, objects, global variables, the stack, and
symbol tables — each of variable length. Segmentation divides the logical address space into such
variable-sized segments, each identified by a segment name/number and a length.

2.2 Address Translation

A logical address under segmentation consists of two parts:
Logical Address = <Segment Number (s), Offset (d)>
The segment number s is used to index a Segment Table. Each segment table entry has two fields:
• Base: the starting physical address where the segment resides in memory.
• Limit: the length (size) of the segment.
The offset d is checked against the limit: if 0 ≤ d < limit, the physical address is computed as Base + d. If
d ≥ limit, the hardware traps an addressing error to the operating system (this provides automatic
bounds protection).
Physical Address = Segment Table[s].Base + d (valid only if d < Limit)
Diagram (described): Segmentation Address Translation
CPU generates Logical Address → split into (Segment Number s | Offset d) → 's' indexes the Segment
Table → entry gives (Base, Limit) → hardware compares d with Limit → if valid, Physical Address =
Base + d → sent to Physical Memory; otherwise a trap (segmentation fault) is raised.

2.3 Protection and Sharing in Segmentation

• Protection Bits: Each segment table entry can carry validation bits and protection bits
(read/write/execute) — protection is naturally applied at the level of a logical unit (e.g., the
whole 'function' or 'array' segment), which is more meaningful than protecting arbitrary
fixed-size pages.
• Sharing: Segments can be shared between processes by having the segment-table entries of
two different processes point to the same base address in physical memory. This is
convenient for sharing common code such as libraries.

2.4 Advantages and Disadvantages of Segmentation

Advantages Disadvantages
Matches the logical (programmer's) view of a Suffers from external fragmentation since segments
program are of variable size

Page 6
 OS — Memory Management Notes

Advantages Disadvantages
Each segment can grow or shrink independently Requires dynamic storage allocation (best-fit/first-
(e.g., a stack segment) fit) and periodic compaction
Protection and sharing are meaningful at the level Segment table lookup adds overhead, similar to
of logical units paging
No internal fragmentation (segment exactly Allocating variable-sized segments is harder than
matches the logical unit size) allocating fixed-size frames

2.5 Paging vs Segmentation — Comparison

Basis Paging Segmentation
Division of memory Fixed-size pages/frames Variable-size logical segments
Invisible — managed by
Visibility to programmer Visible — reflects program structure
OS/hardware
Address format <Page Number, Offset> <Segment Number, Offset>
Fragmentation Internal fragmentation External fragmentation
Frame number, valid bit, protection
Table entry fields Base, limit, protection bits
bits
Sharing/protection
Page-level (arbitrary) Segment-level (logical, meaningful)
granularity

Page 7
 OS — Memory Management Notes

3. Segmentation with Paging

3.1 Motivation
Pure paging eliminates external fragmentation but loses the logical, programmer-friendly view of
memory and makes protection/sharing of meaningful program units harder. Pure segmentation
preserves the logical view and gives meaningful protection but reintroduces external fragmentation
because segments have variable size. Segmentation with paging is a hybrid scheme that combines the
advantages of both: it keeps the logical segmentation view for the programmer, while each segment
is itself divided into fixed-size pages, so physical memory allocation behaves like paging and external
fragmentation is avoided.
This approach was used in the MULTICS system, and a similar combined approach is used in the
protected mode of Intel x86 processors, where a logical address first goes through segmentation
translation and the resulting linear address is then translated through paging.

3.2 Address Translation Steps

In this scheme, a logical address has three components:
Logical Address = <Segment Number (s), Page Number (p), Offset (d)>
4. The segment number s indexes the Segment Table. Instead of storing a direct base address,
each segment table entry now stores the base address of a Page Table for that segment,
along with the segment length (limit) for bounds checking.
5. The hardware checks that p is within the limit of that segment's page table.
6. The page number p then indexes that segment's page table to obtain the frame number f in
physical memory.
7. The physical address is finally formed by combining the frame number f with the offset d,
exactly as in ordinary paging.
Physical Address = (Frame Number f from Segment's Page Table[p]) + Offset d
Diagram (described): Segmentation-with-Paging Translation
Logical Address (s, p, d) → 's' indexes Segment Table → entry gives (Page-Table Base for this segment,
Limit) → 'p' indexes that Page Table (after a limit check) → entry gives Frame Number f → Physical
Address = (f, d) → sent to Physical Memory. Two levels of table lookup are therefore required
(segment table, then page table), which a TLB greatly speeds up.

3.3 Advantages and Disadvantages

Advantages Disadvantages
No external fragmentation (each segment is page- Extra level of indirection — two table lookups per
allocated) memory access
Retains logical, modular view of a program for the More memory consumed for both segment tables
programmer and per-segment page tables

Page 8
 OS — Memory Management Notes

Advantages Disadvantages
Protection and sharing can be applied meaningfully
More complex hardware/OS support required
at the segment level
Segments can grow by simply adding more pages, Greater translation latency unless TLB hit rates are
without relocation high
Exam Tip: A common 14-mark question is 'Explain segmentation with paging with a diagram.' Always
state the 3-part address (s, p, d), draw/describe the two-step lookup, and mention MULTICS / Intel x86
as real examples.

Page 9
 OS — Memory Management Notes

4. Virtual Memory Concepts

4.1 Definition and Motivation

Virtual memory is a technique that allows the execution of processes that may not be completely
resident in main (physical) memory. It separates the logical (virtual) address space, as seen by the
program, from the physical address space, as actually available in RAM, allowing a program's logical
address space to be much larger than the physical memory installed on the machine.
Virtual memory is what gives the programmer the illusion of a very large, uniform main memory, even
though the underlying hardware may have far less physical RAM, by transparently using disk (the
swap/backing store) as an extension of memory.

4.2 Why Virtual Memory Is Needed

• Allows a program larger than physical memory to be executed, since only the actively used
parts need to reside in memory at any instant.
• Increases the degree of multiprogramming, because each process occupies less physical
memory on average, allowing more processes to be kept in memory simultaneously, which
improves CPU utilization and throughput.
• Reduces I/O needed to load or swap user programs into memory, so each user program
runs faster.
• Allows programmers to write code without worrying about the exact amount of physical
memory available.
• Enables useful features such as memory-mapped files, shared libraries, and efficient process
creation (copy-on-write).

4.3 Locality of Reference

Virtual memory (and demand paging in particular) is practically effective because of the principle of
locality of reference: as a process executes, it tends to access a relatively small, localized portion of its
address space at any given time.
• Temporal locality: recently accessed memory locations are likely to be accessed again soon
(e.g., loop variables).
• Spatial locality: memory locations near a recently accessed location are likely to be
accessed soon (e.g., sequential array access).
Because of locality, only a small working set of pages needs to be kept in memory at a time to achieve
good performance, which is the foundation on which demand paging is built.

4.4 Virtual Address Space Layout

A typical virtual address space of a process is organized (from low to high addresses) as follows:
8. Text/Code segment — fixed size, at the lowest addresses.

Page 10
 OS — Memory Management Notes

9. Initialized and uninitialized data segment, directly above the text segment.
10. Heap — grows upward (towards higher addresses) as the program dynamically allocates
memory.
11. Unused / hole region — a large gap of unused virtual address space between the heap and
the stack, allowing both to grow without colliding.
12. Stack — grows downward (towards lower addresses) at the highest addresses, used for
function call frames and local variables.
This layout (heap growing up, stack growing down, with a large unused gap in between) is precisely
what makes sparse virtual address spaces practical — the unused hole costs nothing because pages
are only allocated/backed when actually touched.

4.5 Benefits of Virtual Memory

Benefit Explanation
Higher degree of More processes fit in physical memory since each uses only the
multiprogramming frames it currently needs
Larger logical address space A process can be larger than the available physical memory
Less I/O for swapping Only required pages are loaded, not the entire process image
Copy-on-write fork() lets parent and child share pages until either
Faster process creation
writes
Shared libraries and memory-mapped files use the same physical
Efficient page sharing
frames across processes

Page 11
 OS — Memory Management Notes

5. Demand Paging

5.1 Concept
Demand paging is the most common implementation mechanism for virtual memory. Under demand
paging, a page is loaded into physical memory only when it is actually demanded — i.e., referenced —
during execution, rather than loading the entire process into memory in advance. The component of
the OS responsible for bringing pages in this lazy fashion is sometimes called a 'lazy swapper' or simply
the pager.
Demand paging reduces the amount of memory and the amount of I/O needed to start and run a
process, since unused pages (e.g., rarely executed error-handling code) may never need to be brought
into memory at all.

5.2 Valid–Invalid Bit and the Page Fault

Each entry in the page table has a valid–invalid bit. 'Valid' indicates the associated page is both legal
and currently in physical memory. 'Invalid' indicates either that the page is not part of the process's
logical address space, or that it is a legal page that has simply not yet been brought into memory from
disk. When a process tries to access a page marked invalid (but legal), the hardware generates a trap
called a page fault.

5.3 Steps in Handling a Page Fault

13. The OS checks an internal table (kept with the process's PCB) to determine whether the
reference was a valid or an invalid memory access.
14. If the reference was invalid, the process is terminated. If it was valid but the page has simply
not yet been brought in, the OS proceeds to page it in.
15. A free frame is located, typically by taking one from a free-frame list maintained by the OS.
16. A disk read operation is scheduled to bring the desired page into the newly allocated frame.
17. When the disk I/O completes, the process's page table is updated to mark that page as
valid/resident, and the frame number is recorded.
18. The instruction that was interrupted by the page-fault trap is restarted. The process can
now access the page exactly as if it had always been in memory.
Exam Tip: This 6-step page-fault handling sequence is one of the most frequently asked 14-mark
questions. Always number the steps and explicitly mention the free-frame list, disk I/O, page table
update, and instruction restart.

5.4 Pure Demand Paging

In the extreme case, a process can be started with absolutely zero pages in memory — this is called
pure demand paging. The very first instruction fetch causes a page fault for the page containing that
instruction; pages continue to be brought in, one fault at a time, as each is referenced for the first
time. Eventually, most of the pages a process needs are in memory, and faults reduce dramatically
due to locality of reference.

Page 12
 OS — Memory Management Notes

5.5 Performance of Demand Paging — Effective Access Time

Let p be the probability of a page fault (0 ≤ p ≤ 1), and ma be the memory access time. Then the
Effective Access Time (EAT) is:
EAT = (1 − p) × ma + p × (page fault service time)
Solved Example: Suppose memory access time ma = 200 nanoseconds and average page-fault service
time = 8 milliseconds = 8,000,000 ns. If the page-fault rate p = 0.001 (one fault per 1000 references):
EAT = (1 − 0.001) × 200 + 0.001 × 8,000,000 = 199.8 + 8000 = 8199.8 ns ≈ 8.2
microseconds
This is over 40 times slower than the no-fault access time of 200 ns, even though only 1 in 1000
references caused a fault. This dramatically illustrates why the page-fault rate must be kept extremely
low (often required to be well under 0.001) for virtual memory to perform acceptably — otherwise
thrashing-level slowdowns occur.

5.6 Copy-on-Write (COW)

Copy-on-write is an optimization used during process creation with fork(). Instead of physically
copying the parent's entire address space into the child, the parent and child are initially allowed to
share the same physical pages, with those pages marked as copy-on-write in both page tables. If
either process attempts to modify (write to) a shared page, only then is a private copy of just that page
created for the writing process — hence 'copy on write.' This drastically speeds up process creation
since pages that are never modified (which, after a typical fork()+exec(), is most of them) are never
actually duplicated.

Page 13
 OS — Memory Management Notes

6. Page Replacement Algorithms

6.1 Why Page Replacement Is Needed

With demand paging, the degree of multiprogramming can be increased by over-committing
memory: the sum of the memory sizes of all processes can exceed actual physical memory, since not
all pages of all processes are resident at once. However, this means that at some point all physical
frames may become occupied, and a page fault occurs for a page that has no free frame to go into.
The OS must then choose a victim page already in memory to remove (replace) to make room for the
newly required page. The chosen replacement algorithm directly affects the number of page faults,
and hence overall system performance — the goal is to choose the algorithm with the lowest possible
page-fault rate.

6.2 Basic Page-Replacement Procedure

19. Find the location of the desired page on the disk (backing store).
20. Find a free frame: (a) if a free frame exists, use it; (b) if not, use a page-replacement
algorithm to select a victim frame.
21. If the victim page was modified (its modify/dirty bit is set), write it back to disk before reuse;
if unmodified, it can simply be discarded.
22. Read the desired page into the newly freed frame; update the page table and frame table
accordingly.
23. Restart the process from the point of the page fault.

6.3 Evaluating Algorithms — Reference String

Page-replacement algorithms are evaluated by running them against a reference string (a sequence
of page numbers accessed by a process) for a given number of available frames, and counting the
resulting number of page faults. Fewer faults indicate a better algorithm for that workload. The
following classic reference string with 3 frames is used below to illustrate FIFO, Optimal, and LRU:
Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 (3 frames
available)

6.4 FIFO (First-In First-Out) Page Replacement

The FIFO algorithm replaces the page that has been in memory the longest, regardless of how recently
or frequently it was used. It is implemented using a simple FIFO queue: when a page is brought into
memory, it is inserted at the tail of the queue; the victim for replacement is always taken from the
head (the oldest page).
Worked Example (3 frames):

Step Ref F1 F2 F3 Fault?

1 7 7 - - Fault

Page 14
 OS — Memory Management Notes

Step Ref F1 F2 F3 Fault?

2 0 7 0 - Fault
3 1 7 0 1 Fault
4 2 0 1 2 Fault
5 0 0 1 2 -
6 3 1 2 3 Fault
7 0 2 3 0 Fault
8 4 3 0 4 Fault
9 2 0 4 2 Fault
10 3 4 2 3 Fault
11 0 2 3 0 Fault
12 3 2 3 0 -
13 2 2 3 0 -
14 1 3 0 1 Fault
15 2 0 1 2 Fault
16 0 0 1 2 -
17 1 0 1 2 -
18 7 1 2 7 Fault
19 0 2 7 0 Fault
20 1 7 0 1 Fault
Total page faults with FIFO (3 frames) = 15 out of 20 references.

Belady's Anomaly
A surprising and important property of FIFO is Belady's Anomaly: for some reference strings,
increasing the number of available frames can actually increase the number of page faults, instead of
decreasing it as one would intuitively expect. The classic example uses the reference string 1, 2, 3, 4,
1, 2, 5, 1, 2, 3, 4, 5: with 3 frames, FIFO produces 9 page faults, but with 4 frames it produces 10 page
faults. This counter-intuitive behaviour is a major drawback of FIFO and motivated the search for
stack-based algorithms (like LRU) that never exhibit this anomaly.

6.5 Optimal (OPT / MIN) Page Replacement

The Optimal algorithm replaces the page that will not be used for the longest time in the future. It
guarantees the lowest possible page-fault rate for a fixed number of frames and never suffers from
Belady's Anomaly. However, it is not implementable in a real system because it requires future
knowledge of the reference string, which is generally unknowable in advance. It is used purely as a
theoretical benchmark to measure how close practical algorithms come to the best possible
performance.

Page 15
 OS — Memory Management Notes

Worked Example (3 frames):

Step Ref F1 F2 F3 Fault?

1 7 7 - - Fault
2 0 7 0 - Fault
3 1 7 0 1 Fault
4 2 0 1 2 Fault
5 0 0 1 2 -
6 3 0 2 3 Fault
7 0 0 2 3 -
8 4 2 3 4 Fault
9 2 2 3 4 -
10 3 2 3 4 -
11 0 2 3 0 Fault
12 3 2 3 0 -
13 2 2 3 0 -
14 1 2 0 1 Fault
15 2 2 0 1 -
16 0 2 0 1 -
17 1 2 0 1 -
18 7 0 1 7 Fault
19 0 0 1 7 -
20 1 0 1 7 -
Total page faults with Optimal (3 frames) = 9 out of 20 references — the lowest of all three algorithms,
as expected since it is the theoretical best case.

6.6 LRU (Least Recently Used) Page Replacement

LRU approximates the optimal algorithm by using the recent past as a predictor of the near future: it
replaces the page that has not been used for the longest period of time. LRU is a 'stack algorithm' and
provably never suffers from Belady's Anomaly — adding more frames can never increase the number
of faults.
Worked Example (3 frames):

Step Ref F1 F2 F3 Fault?

1 7 7 - - Fault
2 0 0 7 - Fault

Page 16
 OS — Memory Management Notes

Step Ref F1 F2 F3 Fault?

3 1 0 1 7 Fault
4 2 0 1 2 Fault
5 0 0 1 2 -
6 3 0 2 3 Fault
7 0 0 2 3 -
8 4 0 3 4 Fault
9 2 0 2 4 Fault
10 3 2 3 4 Fault
11 0 0 2 3 Fault
12 3 0 2 3 -
13 2 0 2 3 -
14 1 1 2 3 Fault
15 2 1 2 3 -
16 0 0 1 2 Fault
17 1 0 1 2 -
18 7 0 1 7 Fault
19 0 0 1 7 -
20 1 0 1 7 -
Total page faults with LRU (3 frames) = 12 out of 20 references — better than FIFO (15) but worse than
the unattainable Optimal (9), which is the expected ordering: Optimal ≤ LRU ≤ FIFO.

Implementing LRU
• Counter implementation: Every page-table entry has a 'time-of-use' field, and the CPU has a
logical clock/counter that increments on every memory reference. Whenever a page is
referenced, the current clock value is copied into that page's time-of-use field. The
replacement victim is the page with the smallest (oldest) time-of-use value. This requires a
search through the page table at replacement time, and a clock-update write on every
memory reference.
• Stack implementation: A doubly linked list (stack) of page numbers is maintained.
Whenever a page is referenced, it is moved to the top of the stack. The bottom of the stack
is always the least recently used page, so no search is needed at replacement time.
However, updating the stack on every single reference requires changing up to six pointers,
which is itself costly without special hardware support.
Because true LRU needs hardware support (a register or stack updated on every memory reference)
that most systems lack, in practice LRU is only approximated.

Page 17
 OS — Memory Management Notes

6.7 LRU Approximation Algorithms

(a) Additional-Reference-Bits Algorithm
Each page is associated with an 8-bit byte in addition to its single reference bit. At regular, fixed
intervals, a timer interrupt occurs and the OS shifts the reference bit of every page into the high-order
bit of its history byte, shifting the other bits right by one position (discarding the low-order bit). The
page whose history byte has the smallest numerical value has been used least recently among the
pages tracked, and is chosen for replacement; ties can be broken using FIFO.

(b) Second-Chance (Clock) Algorithm

This is a simple, widely-used circular-queue approximation of LRU. Pages are kept in a circular list with
a 'hand' pointer. Each page has a single reference bit, which is set to 1 by hardware whenever the
page is accessed. When a victim is needed, the algorithm inspects the page the hand currently points
to:
• If its reference bit is 0, that page is replaced immediately.
• If its reference bit is 1, the page is given a 'second chance' — its reference bit is cleared to 0,
it is left in memory, and the hand advances to the next page in the circular list; this repeats
until a page with reference bit 0 is found.
The name 'clock algorithm' comes from visualizing the pages arranged in a circle, with the hand
sweeping around like a clock's hand.

(c) Enhanced Second-Chance Algorithm

This refinement uses both the reference bit and the modify (dirty) bit together, forming four classes of
pages:
24. (0, 0) — not recently used, not modified: best candidate for replacement (cheapest, no
write-back needed).
25. (0, 1) — not recently used, but modified: must be written back to disk before reuse.
26. (1, 0) — recently used, not modified: likely to be used again soon.
27. (1, 1) — recently used and modified: least desirable to replace right now.
The algorithm scans circularly (as in the clock algorithm) and replaces the first page found in the
lowest non-empty class, which both reduces the number of disk writes and approximates LRU
behaviour effectively.

6.8 Counting-Based Page Replacement Algorithms

• LFU (Least Frequently Used): Maintains a count of references made to each page, and
replaces the page with the smallest count, on the reasoning that an actively used page
should have a high reference count. A drawback: a page used heavily during a process's
initial phase may retain a high count even though it is no longer being used later, making it
falsely 'protected' from replacement.
• MFU (Most Frequently Used): Based on the argument that the page with the smallest count
was probably just brought into memory and has yet to be used, so the page with the largest

Page 18
 OS — Memory Management Notes

count is replaced instead. Both LFU and MFU are uncommon in practice because they only
roughly approximate optimal behaviour and carry additional bookkeeping overhead.

6.9 Comparison of Page Replacement Algorithms

Belady's Practical
Algorithm Principle
Anomaly? Implementability
Simple; easy with a
Replace oldest page in memory Yes — can
FIFO queue, but weak
(queue order) occur
performance
Not implementable —
Replace page not used for longest needs future
Optimal (OPT) No
time in the future knowledge; used as a
benchmark only
Needs special hardware
Replace page not used for longest No (stack
LRU (counters/stack) for
time in the past algorithm)
exact implementation
Approximates LRU using a single Practical; widely used in
Second-Chance / Clock No
reference bit in a circular list real operating systems
Practical; reduces disk
Enhanced Second- Uses (reference, modify) bit pairs to writes, used in
No
Chance form 4 classes Macintosh OS and
others
Rarely used; poor
Replace page with smallest
LFU — adaptability to changing
reference count
access patterns
Replace page with largest reference Rarely used; weak
MFU —
count theoretical justification

6.10 Thrashing and the Working-Set Model (Related Concept)

If a process does not have enough frames to hold the pages it actively needs, it will page-fault very
frequently, since almost every page it touches must be brought in again. This high page-fault rate
keeps the CPU busy mostly with paging I/O rather than useful computation — a phenomenon called
thrashing. Ironically, if the OS misreads low CPU utilization (caused by thrashing) as a sign that it
should admit more processes to increase utilization, it will allocate even fewer frames per process,
worsening the faulting rate further and deepening the thrashing spiral.
• Working-Set Model: Defines a working set as the set of pages a process has referenced in
the most recent Δ references (the 'working-set window'). The OS monitors each process's
working set size and only runs a process if enough frames are available to hold its entire
current working set, thereby preventing thrashing.
• Page-Fault Frequency (PFF) Strategy: Directly monitors each process's page-fault rate. If the
rate rises above an upper threshold, the process is given more frames; if it falls below a

Page 19
 OS — Memory Management Notes

lower threshold, frames may be removed — keeping the fault rate within an acceptable
band.

6.11 Frame Allocation Algorithms (Supporting Concept)

• Equal Allocation: Total available frames are divided equally among all active processes,
regardless of process size.
• Proportional Allocation: Frames are allocated to each process in proportion to its size, so a
larger process receives more frames than a smaller one.
• Global vs Local Replacement: In global replacement, a process may select a victim frame
from the entire set of frames in memory (even frames belonging to other processes), which
can increase throughput but reduces predictability. In local replacement, a process may only
replace one of its own allocated frames, giving more consistent per-process performance.

Page 20
 OS — Memory Management Notes

7. Likely 14-Mark Exam Questions (Quick Reference)

Use this checklist while revising — each of these can be answered directly using the corresponding
section above:
1. Explain paging with a neat diagram. Discuss the structure of the page table. → Section 1
2. What is the TLB? Derive/explain the Effective Access Time with an example. → Section 1.3
3. Explain segmentation with its address translation mechanism and protection scheme. →
Section 2
4. Compare and contrast paging and segmentation. → Section 2.5
5. Explain segmentation with paging, with a diagram, and state where it is used in practice. →
Section 3
6. What is virtual memory? Explain its benefits and the layout of a virtual address space. →
Section 4
7. Explain demand paging and the step-by-step procedure for handling a page fault. →
Section 5.3
8. Derive the Effective Access Time formula for demand paging with a numerical example. →
Section 5.5
9. Explain copy-on-write and its benefit during process creation. → Section 5.6
10. Explain FIFO, Optimal, and LRU page-replacement algorithms with a solved example
reference string. What is Belady's Anomaly? → Section 6.3–6.6
11. Explain the Second-Chance (Clock) and Enhanced Second-Chance algorithms as
approximations of LRU. → Section 6.7
12. What is thrashing? Explain the working-set model used to control it. → Section 6.10

End of Notes — Good luck with your exam!

Page 21