OS — Unit III: Storage Management

OPERATING SYSTEMS
UNIT III — STORAGE MANAGEMENT
Complete Exam-Oriented Notes with Diagrams

Topics Covered
• Single Contiguous Allocation
• Non-Contiguous Memory Allocation (First-Fit, Best-Fit, Worst-Fit)
• Paging — Hardware, TLB, Numerical Problems
• Segmentation — Hardware, Segment Tables
• Segmentation with Paging
• Virtual Memory & Demand Paging
• Page Replacement Algorithms — FIFO, Optimal, LRU, LRU Approximation
• Thrashing

Page 1 of 20
 OS — Unit III: Storage Management

Table of Contents
TOC \h \o "1-3"

Page 2 of 20
 OS — Unit III: Storage Management

1. Single Contiguous Allocation

1.1 Definition
Single contiguous allocation is the simplest memory management scheme used in early operating
systems. The entire main memory is divided into exactly two regions: a fixed area reserved for the
operating system, and the remaining area for a single user process. Only one process can reside in
memory and execute at any given time.

1.2 How It Works

Main memory is treated as one large contiguous block. The OS is normally placed in low memory
(because interrupt vectors are often located there) or sometimes in high memory. Whatever portion is
left after the OS reservation is given entirely to a single user program. If the program is smaller than the
available user area, the remaining space is simply wasted — it cannot be used by another process
because no second process is permitted to load.

Fig: Single Contiguous Allocation — entire user area given to one process

1.3 Address Binding

Address binding in this scheme can be done at compile time (if the starting memory location is known in
advance) or at load time (if it is not known at compile time, generating relocatable code). Since only one
process runs, no relocation register or dynamic address translation hardware is strictly necessary,
though a simple base register may be used to relocate the program.

1.4 Advantages
• Extremely simple to implement and manage — minimal OS overhead.
• No need for complex memory management hardware (no MMU required in the basic form).
• Fast, since there is no contention for memory among multiple processes.

Page 3 of 20
 OS — Unit III: Storage Management

1.5 Disadvantages
• Severe internal fragmentation: if the process is smaller than the user memory area, the leftover
space is wasted.
• No multiprogramming is possible, so CPU utilization is poor — when the single process performs
I/O, the CPU sits idle since there is no other process to run.
• Maximum process size is limited by the size of physical memory available.
• Poor resource utilization overall, since memory and CPU cannot be shared.
📝 Exam Tip: Asked as a direct 7-mark short note (M-21). Always mention: (a) definition, (b) OS+user area
split diagram, (c) internal fragmentation as the key disadvantage, (d) no multiprogramming.

2. Non-Contiguous Memory Allocation

2.1 Definition
Non-contiguous memory allocation is a scheme in which a process's logical address space is divided into
smaller, equal or variable-sized units that need not occupy adjacent locations in physical memory. The
process is loaded into multiple scattered free areas (holes) of memory rather than one single block. This
is implemented mainly through Paging and Segmentation, and both rely on hardware support (Memory
Management Unit) to translate logical addresses into physical addresses at run time.

Fig: Non-contiguous allocation — Process A and Process B split across scattered free holes

2.2 Difference: Contiguous vs Non-Contiguous Allocation

Basis Contiguous Allocation Non-Contiguous Allocation
Process occupies a single continuous Process is split into parts placed in
Memory Placement
block of memory scattered locations
Fragmentation Suffers from external fragmentation Eliminates external fragmentation;

Page 4 of 20
 OS — Unit III: Storage Management

Basis Contiguous Allocation Non-Contiguous Allocation

(variable partitions) or internal (fixed paging may cause internal
partitions) fragmentation
Needs page table or segment table +
Implementation Simple, base/limit register sufficient
MMU hardware
Multiprogramming Limited / partition-based Efficient multiprogramming possible
Single partition, fixed partition, variable Paging, Segmentation, Paged
Example Techniques
partition Segmentation
Memory Utilization Lower, due to fragmentation Higher, memory used more flexibly

2.3 Memory Allocation / Placement Strategies

When using variable-partition (dynamic) contiguous or non-contiguous schemes, the OS must decide
which free hole to allocate to an incoming process from a list of free holes. Three classic strategies are
used:

(a) First-Fit
The OS scans the list of free memory holes from the beginning and allocates the first hole that is large
enough to satisfy the request. It is fast because the search stops as soon as a suitable hole is found.

(b) Best-Fit
The OS searches the entire list of free holes and allocates the smallest hole that is big enough for the
process. This minimizes leftover wasted space per allocation, but it can leave many very small,
practically unusable holes (this leftover is sometimes called external fragmentation residue), and it
requires searching the whole list unless holes are kept sorted by size.

(c) Worst-Fit
The OS allocates the largest available hole to the process. The idea is that the leftover free space after
allocation will be large enough to be useful for a future process. In practice this strategy tends to
perform worse than first-fit and best-fit in most simulations.

Strategy Search Method Speed Memory Utilization

First-Fit Stop at first hole big enough Fastest Good, simple
Best in terms of
minimizing leftover, but
Best-Fit Find smallest sufficient hole Slowest (search all)
creates tiny unusable
fragments
Generally worst overall
Worst-Fit Find largest hole Slow (search all)
performance

2.4 Categorizing Memory Allocation Techniques & Computing Efficiency

Memory allocation techniques can be broadly categorized as:

Page 5 of 20
 OS — Unit III: Storage Management

1. Contiguous Allocation: Single partition allocation, Fixed (static) partition allocation, Variable
(dynamic) partition allocation.
2. Non-Contiguous Allocation: Paging, Segmentation, Paged Segmentation.
Efficiency of an allocation technique is generally evaluated using the formula:
Memory Utilization (%) = (Memory actually used by processes / Total memory allocated) × 100
For fixed partitioning, efficiency is reduced by internal fragmentation (process smaller than partition
leaves unused space inside the partition). For variable partitioning, efficiency is reduced by external
fragmentation (free holes scattered between processes, too small individually to satisfy new requests,
even though their sum may be large). Paging removes external fragmentation almost entirely (efficiency
approaches 100% minus a small internal fragmentation in the last page), making it the most efficient of
the basic techniques.
📝 Exam Tip: M-26 asked to 'categorize and compute efficiency' — write the three contiguous types + two
non-contiguous types, then explicitly state which fragmentation type affects each and give the utilization
formula above.

3. Paging

3.1 Definition
Paging is a non-contiguous memory management scheme that eliminates the problem of external
fragmentation and the need to fit varying-sized memory chunks onto backing store. Physical memory is
divided into fixed-size blocks called frames, and logical memory is divided into blocks of the same fixed
size called pages. When a process is to be executed, its pages are loaded into any available memory
frames, not necessarily contiguous ones.

3.2 Paging Hardware and Address Translation

Every address generated by the CPU is a logical address, divided into two parts: a page number (p) and a
page offset (d). The page number is used as an index into a page table, which contains the base address
(frame number) of each page in physical memory. This base/frame number is combined with the page
offset to define the physical memory address sent to the memory unit.

Page 6 of 20
 OS — Unit III: Storage Management

Fig: Paging hardware: logical address (p, d) translated to physical address (f, d) via page table

Address Translation Formulas

• If logical address space size = 2^m and page size = 2^n, then the high-order (m − n) bits designate
the page number, and the low-order n bits designate the page offset.
• Physical Address = (Frame Number × Page Size) + Offset.
• Page Table Length = Number of pages = Logical Address Space Size / Page Size.
• Number of Frames = Physical Memory Size / Frame Size (Frame Size = Page Size).

3.3 Translation Look-aside Buffer (TLB)

Every reference to memory under pure paging would require two physical memory accesses: one to
read the page table entry, and one to access the actual data/instruction. This doubles memory access
time. To solve this, a small, fast-lookup hardware cache called the Translation Look-aside Buffer (TLB) is
used. The TLB stores a limited number of the most recently used page-table entries (page number →
frame number mappings).

Fig: TLB hit vs TLB miss in address translation

When the CPU generates a logical address, the page number is first searched in the TLB:

Page 7 of 20
 OS — Unit III: Storage Management

3. TLB Hit: If the page number is found in the TLB, the corresponding frame number is obtained
immediately, and the physical address is formed without accessing the page table in memory.
4. TLB Miss: If the page number is not found, the page table in memory must be referenced. Once
found, the page number/frame number pair is added to the TLB for future use (replacing an old
entry if the TLB is full).
The percentage of times a page number is found in the TLB is called the hit ratio, and it is used to
compute the Effective (Average) Memory Access Time:
Effective Access Time = Hit Ratio × (TLB time + Memory time) + (1 − Hit Ratio) × (TLB time + 2 × Memory
time)

3.4 Page Table Structure & File Used for Paging

Each process has its own page table, and a pointer to this table is stored in the process's PCB (Process
Control Block). Each page table entry usually includes the frame number, plus control bits: a valid/invalid
bit (whether the page is currently in memory), a modified/dirty bit (whether the page has been written
to since loaded), protection bits (read/write/execute), and a reference bit (used by some replacement
algorithms).
On disk, the area used to hold pages that are swapped out of physical memory is called the swap space
or paging file. On Windows systems this file is typically named [Link], and on Linux/UNIX systems it
is implemented as a swap partition or swap file.

3.5 Advantages and Disadvantages of Paging

Advantages Disadvantages
Causes internal fragmentation in the last page of a
Eliminates external fragmentation completely
process
Simplifies allocation — any free frame can be used Page table itself consumes extra memory
Allows processes larger than available contiguous Extra memory access needed for page table lookup
memory (mitigated by TLB)
Supports efficient multiprogramming and virtual
More complex hardware (MMU) required
memory

3.6 Solved Numerical: Page Table Size

Problem: A system has a 64-bit virtual address and 8 KB page size. Main memory is 512 MB. Each page
table entry has 1 valid bit and 1 modified bit. Find the size of the page table and the frame entry size.

Solution
• Page size = 8 KB = 2^13 bytes → offset bits = 13 bits.
• Virtual address = 64 bits → page number bits = 64 − 13 = 51 bits → Number of pages = 2^51 (this is
the number of entries the page table must be capable of holding for the full virtual space).
• Physical memory = 512 MB = 2^29 bytes. Frame size = page size = 2^13 bytes, so number of
frames = 2^29 / 2^13 = 2^16 frames.
• Frame number field needs to address 2^16 frames → requires 16 bits to represent the frame
number.

Page 8 of 20
 OS — Unit III: Storage Management

• Each page table entry = frame number bits + valid bit + modified bit = 16 + 1 + 1 = 18 bits →
rounded up to 3 bytes (or commonly padded to a convenient byte boundary, e.g. 4 bytes/32 bits
in real hardware for alignment).
• Frame (page table) entry size = 18 bits (≈ 3 bytes practically, often padded to 4 bytes).
• Total page table size (for full 64-bit space) = Number of entries × Entry size = 2^51 × 18 bits —
extremely large, which is exactly why multi-level / hierarchical / inverted page tables are used in
real 64-bit systems instead of a single flat table.
📝 Exam Tip: This numerical type is a guaranteed pattern: identify offset bits from page size, find page
number bits from virtual address size, find frame bits from physical memory size, then add control bits
for entry size.

4. Segmentation

4.1 Definition
Segmentation is a memory management technique that supports the user's view of memory, in contrast
to paging, which is driven by the physical view of memory. A program is divided into logical units called
segments, such as the main program, functions, procedures, stack, and global/shared data. Each
segment can be of a different, variable size, reflecting its logical role in the program.

4.2 Segment Table, Base and Limit

A logical address in segmentation consists of two parts: a segment number (s) and an offset (d) within
that segment. Each segment number indexes into a segment table, where each entry has two fields:
• Segment Base: the starting physical memory address where the segment resides.
• Segment Limit: the length (size) of the segment, used to check that the offset is within valid
bounds.
The offset d generated by the CPU must always be checked: if d is between 0 and the limit, the address
is legal and the physical address is computed as base + d. If d exceeds the limit, the hardware traps to
the operating system as an addressing error (similar to an array index-out-of-bounds error).

Page 9 of 20
 OS — Unit III: Storage Management

Fig: Segmentation hardware: logical address (s, d) mapped via segment table to physical address

4.3 Why Segmentation Is Needed

Paging is concerned purely with the physical view of memory and frames; it has no awareness of the
logical structure of a program. Segmentation is needed because programmers naturally think of their
programs as a collection of logical modules — code, data, stack — each of which may grow or shrink
independently and may require different protection (e.g., code segments are read-execute only; data
segments are read-write). Segmentation also makes sharing easier: a shared library or shared code
segment can be referenced by multiple processes simply by having identical segment table entries point
to the same physical segment, instead of needing identical page mappings across processes.

4.4 Page vs Frame vs Segment

Basis Page Frame Segment
Belongs to Logical (virtual) memory Physical memory Logical (virtual) memory
Size Fixed size Fixed size (same as page) Variable size
Mechanical / arbitrary Mechanical division of Logical division based on
Basis of division
division of address space physical memory program structure
Mapped via Page Table — Segment Table
Visibility to Invisible to the Visible — matches
Invisible to the programmer
programmer programmer programmer's view

4.5 Static vs Dynamic Allocation

Basis Static Allocation Dynamic Allocation
Memory allocated at compile time /
Time of allocation Memory allocated at run time, as needed
before execution
Fixed; cannot grow or shrink during Flexible; can grow/shrink during
Flexibility
execution execution
Heap allocation, variable partitioning,
Example Fixed/static partitioning of memory
paging/segmentation
More efficient utilization, slight runtime
Wastage Can lead to wastage if estimate is wrong
overhead

4.6 Comparison: Paging vs Segmentation

Basis Paging Segmentation
Logical — variable-size segments based on
Division basis Physical — fixed-size pages/frames
program structure
Visibility to user Invisible to programmer Visible to programmer
External fragmentation possible (variable
Fragmentation Internal fragmentation only (last page)
holes)

Page 10 of 20
 OS — Unit III: Storage Management

Basis Paging Segmentation

Address structure Page number + offset Segment number + offset
Table used Page Table Segment Table
Harder to apply logical protection per Natural fit for per-module protection and
Sharing/protection
module sharing
Speed of access Generally faster (with TLB) Slightly slower due to limit-checking
📝 Exam Tip: 'Compare Paging vs Segmentation' has appeared repeatedly (M-23, M-25, M-26). Always
lead with the physical vs logical division distinction — that's the core conceptual difference examiners
look for.

5. Segmentation with Paging

5.1 Definition
Segmentation with paging (also called paged segmentation) is a hybrid memory management scheme
that combines the logical, programmer-friendly organization of segmentation with the physical
efficiency (no external fragmentation) of paging. Each segment, instead of being mapped directly to a
contiguous block of physical memory via a base and limit, is itself divided into fixed-size pages. This
scheme is used in the Intel x86 architecture.

5.2 How It Works

The logical address is divided into three parts: a segment number (s), a page number within that
segment (p), and an offset within the page (d). The segment number indexes into a segment table, but
instead of storing a base address directly, each segment table entry stores the base address of a
separate page table that belongs to that particular segment. The page number p is then used to index
into this segment's page table, retrieving a frame number f. Finally, the physical address is computed as
(f, d) — frame number combined with the page offset, exactly as in pure paging.

Fig: Segmentation with Paging: each segment has its own page table

Page 11 of 20
 OS — Unit III: Storage Management

5.3 Advantages of Combining Both

• Retains the logical, modular view of a program for the programmer (segments for code, data,
stack).
• Eliminates external fragmentation because each segment is internally composed of fixed-size
pages, which can be scattered across any free frames.
• Permits fine-grained protection and sharing at the segment level, while still gaining the allocation
flexibility of paging.
• Only suffers internal fragmentation in the last page of each segment, which is much smaller than
the external fragmentation that pure segmentation could suffer.

5.4 Disadvantage
The scheme requires an extra level of indirection (two table lookups: segment table, then that segment's
page table) for every memory access, increasing overhead, although this is usually mitigated using a TLB
just as in pure paging.

6. Virtual Memory and Demand Paging

6.1 Virtual Memory — Concept

Virtual memory is a technique that allows the execution of processes that may not be completely in
main memory at one time. It creates an abstraction in which each process believes it has access to a
large, contiguous address space, even though the physical memory available may be much smaller.
Virtual memory is most commonly implemented via demand paging, but can also be implemented via
demand segmentation.

6.2 Advantages of Virtual Memory

• A program can be larger than physical memory, since only the needed parts are loaded at any
time.
• More processes can be kept in memory simultaneously, increasing the degree of
multiprogramming and CPU utilization.
• Less I/O is required to load or swap programs, since only required pages are brought in, speeding
up process startup.
• Provides each process with its own isolated, large logical address space, simplifying programming.

6.3 Disadvantages of Virtual Memory

• Increased complexity in the memory management hardware and operating system.
• Performance can degrade if page faults occur too frequently (thrashing — see Section 8).
• Extra overhead due to page table maintenance and page fault handling routines.

Page 12 of 20
 OS — Unit III: Storage Management

6.4 Demand Paging

Demand paging is the most common implementation of virtual memory. Pages are loaded into physical
memory only when they are actually referenced (demanded) by the executing process, rather than
loading the entire process into memory at start-up. This is sometimes called a lazy swapper, because it
never loads a page into memory unless that page will be needed.

6.5 Valid-Invalid Bit

Each page table entry contains a valid-invalid bit. When this bit is set to 'valid', it means the associated
page is both legal (belongs to the process's logical address space) and currently in physical memory.
When set to 'invalid', it may mean either that the page is not currently in memory (and must be brought
in from disk if referenced), or that the page is simply not part of the process's logical address space at all
(an illegal reference).

6.6 Page Fault — Definition and Circumstances

A page fault is a trap raised by the hardware to the operating system when a running process tries to
access a page that is marked invalid in its page table — that is, a page that is part of its logical address
space but is not currently loaded into a physical frame.
Circumstances under which a page fault occurs:
5. The process references a page that has never been loaded into memory since process start.
6. The process references a page that was previously loaded but has since been evicted (swapped
out) to make room for another page.
7. The process attempts to access a page that does not belong to its address space at all, causing an
illegal-reference type of fault that typically leads to process termination.

6.7 Steps to Handle a Page Fault

Fig: Sequence of steps in demand paging when a page fault occurs

8. The process attempts to access a page; the hardware checks the valid/invalid bit in the page table.

Page 13 of 20
 OS — Unit III: Storage Management

9. If invalid, the hardware traps to the operating system's page-fault handler.

10. The OS checks an internal table to confirm the reference was valid (not illegal), then checks if a
free frame is available. If memory is full, a page-replacement algorithm selects a victim page to
evict.
11. The OS schedules a disk read to bring the desired page from the backing store (swap space) into
the chosen free frame.
12. Once the disk operation completes, the process's page table is updated, marking the new page
as valid and recording its frame number.
13. The instruction that caused the page fault is restarted, and this time it will succeed because the
page is now in memory.

6.8 Costs and Benefits of Implementing Virtual Memory

Benefits Costs
Allows execution of programs larger than physical Requires hardware support (MMU, page tables, valid-
memory invalid bits)
Increases degree of multiprogramming and CPU Page fault handling has significant time overhead (disk
utilization I/O is slow)
Risk of thrashing if degree of multiprogramming is too
Faster process start-up (only needed pages loaded)
high
Simplifies programmer's view with large logical Extra memory needed for page tables and
address space bookkeeping structures
📝 Exam Tip: 'Importance of demand paging in virtual memory' (M-26) — emphasize: reduces I/O at
startup, allows over-allocation of memory (more processes than physical memory could hold if fully
loaded), and forms the foundation that makes virtual memory practically implementable.

7. Page Replacement Algorithms

7.1 Why Page Replacement Is Needed

When a page fault occurs and there is no free frame available in physical memory, the operating system
cannot simply load the new page — it must first select an existing page in memory (a victim) to remove
(write back to disk if modified) and replace with the newly requested page. The algorithm used to
choose this victim page is called a page-replacement algorithm. The goal of any such algorithm is to
minimize the page-fault rate.

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

The simplest page-replacement algorithm. The OS maintains a queue of all pages currently in memory,
with the page at the front being the oldest (first one brought in). When a page must be replaced, the
page at the front of the queue (the one that has resided in memory the longest) is selected as the victim,
evicted, and the new page is added to the back of the queue.

Page 14 of 20
 OS — Unit III: Storage Management

• Easy to understand and implement using a simple queue.

• Performance is not always good — the oldest page might still be heavily used.
• Suffers from Belady's Anomaly: for some reference strings, increasing the number of frames can
actually increase the number of page faults, which is counter-intuitive.

7.3 Optimal Page Replacement (OPT / MIN)

This algorithm always selects, as the victim, the page that will not be used for the longest period of time
in the future (i.e., the page whose next reference is farthest away, or which will never be referenced
again). It guarantees the lowest possible page-fault rate for any given reference string and number of
frames, and is used purely as a theoretical benchmark to evaluate other algorithms, since it requires
future knowledge of the reference string that is not available in a real system.

7.4 LRU (Least Recently Used) Page Replacement

LRU approximates the optimal algorithm by using the past as an approximation of the future: it selects,
as the victim, the page that has not been used for the longest period of time looking backward. LRU is
implementable in practice and performs significantly better than FIFO, though it requires hardware
support (such as a counter or stack updated on every memory reference) to track recency accurately,
which can be costly.
• Implementation via counters: every page table entry has a time-of-use field, updated whenever
the page is referenced; the page with the smallest (oldest) counter is the victim.
• Implementation via stack: a stack of page numbers is maintained; whenever a page is referenced,
it is removed from wherever it is in the stack and pushed to the top. The bottom of the stack is
always the LRU page.
• LRU does NOT suffer from Belady's Anomaly (unlike FIFO).

7.5 LRU Approximation Algorithms

True LRU requires special hardware that is often not practically available, so most real systems use an
approximation based on a reference bit associated with each page (set to 1 by hardware whenever the
page is referenced, and periodically cleared by the OS).

(a) Second-Chance Algorithm

A FIFO-like circular queue is maintained. When a page would be selected as a FIFO victim, its reference
bit is checked first: if it is 0, the page is replaced immediately. If it is 1, the page is given a 'second
chance' — its reference bit is cleared to 0, its arrival time is updated as if it just arrived, and the
algorithm moves on to check the next page in the circular queue.

(b) Clock (Circular) Algorithm

This is the most common practical implementation of the second-chance idea. Pages are arranged in a
circular list with a 'clock hand' pointer. When a victim is needed, the hand sweeps forward: if the
pointed-to page has reference bit 0, it is replaced; if 1, the bit is cleared and the hand moves to the next
page. This continues until a page with reference bit 0 is found.

Page 15 of 20
 OS — Unit III: Storage Management

7.6 Difference Between LRU and LRU Approximation

LRU Approximation (Second Chance /
Basis LRU (True)
Clock)
Exact — always picks truly least-recently- Approximate — only distinguishes 'recently
Accuracy
used page used' (bit=1) vs 'not recently used' (bit=0)
Needs counters or a stack updated on Needs only a single reference bit per page
Hardware Need
every reference — expensive — cheap and widely supported
Best practical performance, close to Slightly worse than true LRU, but still much
Performance
Optimal better than FIFO
Implementation Low overhead; bit checked/cleared only at
High overhead per memory reference
Complexity replacement time
Belady's Anomaly Does not suffer from it Does not suffer from it

7.7 Solved Numerical (M-26 Pattern) — FIFO, Optimal, LRU Comparison

Reference string: 5, 2, 7, 5, 3, 6, 0, 3, 1, 0, 2, 3, 2, 4, 3, 2, 0, 6, 7, 2, 1, 0 | Number of frames = 4 (initially
empty)

FIFO — Page Faults = 16

Frame contents are shown after each reference is processed (4 frames, initially empty). 'F' marks a page
fault, '-' marks a hit.

Step Reference Frame 1 Frame 2 Frame 3 Frame 4 Fault?

1 5 5 F

2 2 5 2 F

3 7 5 2 7 F

4 5 5 2 7 -
5 3 5 2 7 3 F
6 6 6 2 7 3 F
7 0 6 0 7 3 F
8 3 6 0 7 3 -
9 1 6 0 1 3 F
10 0 6 0 1 3 -
11 2 6 0 1 2 F
12 3 3 0 1 2 F
13 2 3 0 1 2 -
14 4 3 4 1 2 F
15 3 3 4 1 2 -

Page 16 of 20
 OS — Unit III: Storage Management

Step Reference Frame 1 Frame 2 Frame 3 Frame 4 Fault?

16 2 3 4 1 2 -
17 0 3 4 0 2 F
18 6 3 4 0 6 F
19 7 7 4 0 6 F
20 2 7 2 0 6 F
21 1 7 2 1 6 F
22 0 7 2 1 0 F

Optimal — Page Faults = 11

Optimal replaces the page that will not be used for the longest time in the future. Walking through the
same string, the victim choices look ahead at remaining references, giving the minimum possible fault
count of 11 for this string with 4 frames — far fewer than FIFO's 16, confirming Optimal is the
theoretical lower bound.

LRU — Page Faults = 13

LRU replaces the page that has gone the longest without being referenced in the past. For this reference
string with 4 frames, LRU produces 13 page faults — better than FIFO (16) but slightly more than the
theoretical Optimal (11), exactly the behaviour expected since LRU only approximates future behaviour
using past behaviour.

Summary Comparison
Algorithm Total Page Faults Total Hits Remark
Worst performance
here; oldest page
FIFO 16 6
evicted regardless of
usage
Best possible —
theoretical benchmark,
Optimal 11 11
not realizable in
practice
Best realizable
algorithm in this
LRU 13 9
comparison — closest
to Optimal
Conclusion: Optimal gives the minimum number of page faults (11), as expected theoretically. Among
the two practically implementable algorithms, LRU (13 faults) clearly outperforms FIFO (16 faults) for
this reference string.
📝 Exam Tip: For numerical questions: always draw the full frame-state table (one row per frame, one
column per reference) and mark faults with a tick or 'F'. Box or highlight the newly-loaded page in each
fault column. State the final fault count clearly at the end for each algorithm, then conclude with which
algorithm is best.

Page 17 of 20
 OS — Unit III: Storage Management

8. Thrashing

8.1 Definition
Thrashing is a condition in which a process is spending more time paging (handling page faults —
swapping pages in and out of memory) than executing its actual instructions. It is a severe performance
problem of virtual memory systems, where CPU utilization drops drastically even though the system
appears very busy doing I/O.

8.2 Cause of Thrashing

Thrashing occurs when a process does not have enough frames allocated to hold the set of pages it is
actively using (its 'working set'). As a result, it generates page faults very frequently, and almost every
page it needs must be brought in from disk, causing it to spend nearly all its time waiting for I/O rather
than computing.

8.3 How Thrashing Develops — The Vicious Cycle

If the operating system increases the degree of multiprogramming (admits more processes) without
ensuring each process has enough frames, the following chain reaction occurs:
14. CPU utilization is initially low, so the OS scheduler tries to improve it by increasing the degree of
multiprogramming (loading more processes).
15. Each existing process now has fewer frames available, since total physical memory is shared
among more processes.
16. This causes each process to page fault much more frequently.
17. Page faults force processes to queue up waiting for the paging device (disk), drastically reducing
actual CPU utilization, since the CPU sits idle waiting for I/O.
18. The OS scheduler observes low CPU utilization once again, and — mistakenly believing more
processes will help — increases the degree of multiprogramming even further, worsening the
problem.

Page 18 of 20
 OS — Unit III: Storage Management

8.4 Effect on Performance

Fig: CPU utilization rises with degree of multiprogramming, then collapses sharply once thrashing begins

As shown above, CPU utilization initially increases as more processes are added (better overlap of CPU
and I/O across processes), reaching a peak. But beyond a certain degree of multiprogramming, available
frames per process become too few, page-fault rate skyrockets, and CPU utilization collapses sharply —
this drop defines the onset of thrashing.

8.5 Solutions to Thrashing

(a) Working Set Model
This model defines a 'working set' for each process as the set of pages it has referenced in the most
recent window of time (called the working-set window, Δ). The OS attempts to ensure each process is
allocated enough frames to hold its entire working set. If the sum of all working set sizes exceeds total
available frames, the OS suspends one or more processes to free frames for the rest, rather than letting
all of them thrash.

(b) Page-Fault Frequency (PFF) Algorithm

This is a more direct approach that monitors the actual page-fault rate of each process. Upper and lower
threshold bounds are defined: if a process's page-fault rate rises above the upper bound, it is given more
frames (since it clearly needs more memory). If the rate falls below the lower bound, frames are
removed from it (since it has more than it needs). If no free frames are available to give a process that
needs them, the OS suspends a process to free up memory.

(c) Reducing the Degree of Multiprogramming

The most direct fix once thrashing is detected: temporarily suspend or swap out some processes
entirely, freeing their frames for the remaining processes, allowing those remaining processes to satisfy
their working sets and stop excessively faulting.

Page 19 of 20
 OS — Unit III: Storage Management

8.6 Internal Fragmentation (Related Concept)

Internal fragmentation refers to wasted memory space that occurs within an allocated
block/partition/page/frame, because the memory allocated to a process is slightly larger than what it
actually requested or needs. For example, in a fixed-partition scheme, if a partition is 10 KB but the
process only needs 8 KB, the remaining 2 KB inside that partition is wasted and cannot be given to any
other process — this 2 KB is internal fragmentation. In paging, internal fragmentation occurs in the last
page of a process if that page is not completely filled by the process's data.
📝 Exam Tip: Thrashing questions are usually short (2-mark definition type). Always mention: definition,
root cause (too many processes, too few frames each), and at least one solution (Working Set Model is
the most commonly expected answer).

Quick Revision Summary — High-Yield Topics

Topic Frequency Priority

Page Replacement Algorithms Asked in 6/6 years — numerical highly likely ⭐⭐⭐ Guaranteed
Paging Asked in 6/6 years in some form ⭐⭐⭐ Guaranteed
Segmentation Asked in 6/6 years in some form ⭐⭐⭐ Guaranteed
Virtual Memory / Demand Paging 4 consecutive years (M-23 to M-26) ⭐⭐⭐ Very High
Thrashing M-21, M-23, M-25 — alternating pattern ⭐⭐ High
Memory Allocation Techniques M-22, M-23, M-24, M-26 ⭐⭐ High

Tip: Practice drawing the paging hardware diagram, segmentation hardware diagram, and at least one
full FIFO/LRU/Optimal numerical by hand before the exam — these three skills cover the majority of Unit
III marks.

Page 20 of 20