Memory Management

CSS Optional — Paper-II, Section-A · P-II.III.V · Distinct from Virtual Memory Management (next page) — this page covers physical memory allocation; Virtual Memory covers demand paging, page replacement, and thrashing.

0. Classification of Memory Management Techniques (full picture)

Visual Classification Tree

flowchart TD
    A["Memory Management Techniques"] --> B["Contiguous Allocation"]
    A --> C["Non-Contiguous Allocation"]
    A --> D["Overlays (pre-virtual-memory technique)"]

    B --> B1["Single Contiguous Allocation"]
    B --> B2["Multiple Partitioning"]
    B2 --> B2f["Fixed (Static) Partitioning"]
    B2f --> B2fa["Equal-size"]
    B2f --> B2fb["Unequal-size"]
    B2 --> B2d["Dynamic (Variable) Partitioning"]
    B2d --> B2da["First-Fit / Best-Fit / Worst-Fit / Next-Fit"]

    C --> C1["Paging"]
    C1 --> C1a["Single-level (flat)"]
    C1 --> C1b["Multilevel (Hierarchical)"]
    C1 --> C1c["Hashed Page Table"]
    C1 --> C1d["Inverted Page Table"]
    C --> C2["Segmentation"]
    C --> C3["Segmentation with Paging (hybrid)"]

Why this exact shape: two versions of this tree circulate in CSS prep material — a flatter one that puts Fixed/Dynamic Partition directly under Contiguous with no grouping node, and the more textbook-precise one (used here) that groups them under an explicit "Multiple Partitioning" node, contrasted with Single Contiguous Allocation as the other branch of Contiguous Allocation. This is the more correct of the two: it mirrors how the concept is actually taught ("contiguous allocation is single-partition or multiple-partition; multiple-partition is fixed or dynamic") and earns an extra structure mark for naming the grouping level explicitly.
It also extends the simplified diagrams commonly seen in prep material by adding Hashed Page Table (needed once an address space exceeds ~32 bits) and splitting Fixed Partitioning into Equal-size vs Unequal-size, since they behave differently for placement and fragmentation — both are frequently left off simplified diagrams but are fair game in a CSS answer.

Classification Table (with rationale per technique)

Top-level category	Technique	Key idea
Contiguous Allocation	Single Contiguous Allocation	Entire memory (minus OS) given to one process — no multiprogramming
Contiguous Allocation	Fixed (Static) Partitioning — Equal-size	Memory pre-divided into N equal fixed regions
Contiguous Allocation	Fixed (Static) Partitioning — Unequal-size	Pre-divided into fixed regions of different sizes, matched to expected job sizes
Contiguous Allocation	Dynamic (Variable) Partitioning	A partition is carved to the exact size of each incoming process
Non-Contiguous Allocation	Paging — Single-level	One flat page table per process, fixed-size frames
Non-Contiguous Allocation	Paging — Multilevel (Hierarchical)	The page table itself is paged, to shrink per-process table size
Non-Contiguous Allocation	Paging — Hashed Page Table	Virtual page number hashed into a chained table — used for large (>32-bit) address spaces
Non-Contiguous Allocation	Paging — Inverted Page Table	One entry per physical frame (not per logical page) — table size tied to physical memory, not per-process address space
Non-Contiguous Allocation	Segmentation	Variable-size, logically meaningful units (code/stack/heap/data)
Non-Contiguous Allocation	Segmentation with Paging (hybrid)	Each segment is itself paged — combines segmentation's logical protection with paging's no-external-fragmentation
Pre-Virtual-Memory Technique	Overlays	Programmer manually swaps mutually-exclusive code modules in/out of one shared region

This page covers every row above except demand paging/page replacement, which belong to Virtual Memory Management (a process only starts running once its required pages/segments are resident — what happens after that, on a page fault, is the VM page's job).

1. Contiguous Memory Allocation

Each process is allocated one single contiguous block of main memory. It splits first into Single Contiguous Allocation vs Multiple Partitioning — and Multiple Partitioning then splits again into Fixed vs Dynamic. Naming "Multiple Partitioning" as the parent of Fixed/Dynamic (rather than listing Fixed and Dynamic as flat, unrelated options) is the structurally correct version and the one examiners expect.

Single contiguous allocation: the simplest scheme — one process (plus the resident OS) occupies all of memory; no multiprogramming is possible (historically used in early single-user systems).
Multiple Partitioning: memory is divided among several processes at once (enabling multiprogramming), via one of the two schemes below.
Fixed (static) partitioning: memory divided into fixed-size regions in advance, at boot time.
- Equal-size partitions: all regions the same size — placement is trivial (any free partition works, since none fits better than another), but a process larger than the partition size simply cannot run, and a small process wastes most of its partition.
- Unequal-size partitions: regions of different pre-set sizes — a process is matched to the smallest partition that can still hold it (effectively a Best-Fit applied to a fixed, small set of partitions), reducing (but not eliminating) wasted space per job.
- Both variants cause internal fragmentation (wasted space inside a partition when the process is smaller than it) and cannot reclaim that waste without changing the partition boundaries.
Variable/dynamic partitioning: a partition is carved out to exactly the process's size. Avoids internal fragmentation but causes external fragmentation (free memory scattered in small, unusable holes between allocated blocks) — fixed by periodic compaction (shuffling processes to consolidate free space, at the cost of CPU time and process downtime).

📐 Numerical — Internal Fragmentation Under Unequal Fixed Partitioning

Memory is pre-divided into four fixed partitions: P1=100K, P2=200K, P3=300K, P4=400K. Four processes arrive: J1=90K, J2=180K, J3=270K, J4=350K, each assigned (best-fit style) to the smallest partition that can still hold it.

Job	Size	Assigned partition	Internal fragmentation
J1	90K	P1 (100K)	100−90 = 10K
J2	180K	P2 (200K)	200−180 = 20K
J3	270K	P3 (300K)	300−270 = 30K
J4	350K	P4 (400K)	400−350 = 50K

Total internal fragmentation = 10 + 20 + 30 + 50 = 110K, even though every job was matched to its best available fixed partition — the structural cost of fixed partitioning that no placement algorithm can remove (only re-partitioning or switching to dynamic/paged allocation can).

Allocation (fit) algorithms for a free-space list (dynamic partitioning)

Algorithm	Rule	Trade-off
First-Fit	Allocate the first free hole big enough, scanning from the start	Fast; tends to leave small unusable fragments early in memory
Best-Fit	Allocate the smallest hole that is still big enough (scans the whole list)	Minimizes wasted space per allocation, but leaves many tiny, useless fragments over time and is slower
Worst-Fit	Allocate the largest available hole	Leaves the largest possible leftover free chunk (more likely reusable), but performs poorly overall
Next-Fit	Like First-Fit, but resumes scanning from where the previous search left off (not from the start)	Spreads allocations more evenly across memory; avoids repeatedly re-scanning the front of the list

📐 First-Fit/Best-Fit/Worst-Fit/Next-Fit compared head-to-head, plus Buddy System & compaction numericals:

Memory Allocation Algorithms — Deep Dive & Solved Numericals

2. Tracking Free/Used Memory — full classification

Bit Vector / Bitmap: one bit per fixed-size allocation unit (1 = allocated, 0 = free). Simple, fixed overhead, but scanning for a run of free bits can be slow.
Linked List (per block): the textbook baseline — every individual free block holds a pointer to the next free block; simple but traversal cost grows with the number of free blocks.
Grouping: a modification of the linked list — the first free block stores the addresses of the next n−1 free blocks, plus a pointer to another block that stores the next group of addresses. Finding n free blocks becomes a near-O(1) lookup instead of n separate traversals — useful when a request routinely needs several blocks at once (e.g., contiguous file-system allocation).
Counting: exploits the fact that memory is usually freed/allocated in contiguous runs, not one block at a time — instead of one entry per free block, keep only the address of the first block of each run plus a count of how many free blocks follow it. (The {tag, start, length, next} linked-list-of-runs structure used elsewhere on this page is exactly this Counting technique implemented as a linked list.)
Hash Table: maps an active process/page's name directly to its (start, length), giving O(1) average lookup of where a named item currently lives — this answers "where is X?", a different question from "where is a free hole?", so it complements rather than replaces the four techniques above.

📐 Micro-example — Grouping vs Counting on the same free-space

Free blocks (by starting address), each 1 unit long, in a contiguous run: addresses 200, 201, 202, 203, 204 are all free (5 free units), followed by allocated space, then addresses 300, 301 free (2 units).

Pure per-block linked list: 7 separate nodes, one per free address (200→201→202→203→204→300→301→NULL).
Counting: only 2 entries needed — (start=200, count=5) and (start=300, count=2) — because each run is stored once, not block-by-block.
Grouping (with n=4): one block at address 200 stores [201, 202, 203, →next-group-block]; that next-group-block stores [204, 300, 301] — reconstructs the same information in 2 blocks' worth of storage, but is designed to satisfy a "give me n free blocks" request in one lookup rather than a full scan.

3. Segmentation (contrast with Paging)

Memory is divided into variable-sized, logically meaningful segments (code, stack, heap, data) rather than fixed-size pages — this matches how a programmer actually thinks about a program, but re-introduces external fragmentation, which the fixed-size pages of paging avoid entirely.

Segmentation with Paging (hybrid scheme)

Pure segmentation still suffers external fragmentation (segments are variable length); pure paging has no logical/protection meaning (a page boundary rarely lines up with a code/data boundary). The hybrid fixes both: each segment is itself divided into fixed-size pages. A logical address becomes (segment number, page number, offset) — the segment table entry no longer points directly to a physical base, but to the page table for that segment. This gives segmentation's per-segment protection/sharing granularity and paging's freedom from external fragmentation, at the cost of one extra level of address translation (and hence one more memory access unless cached in the TLB).

4. Paging Hardware Details (beyond the address-translation numerical)

Each process has a Page Table Base Register (PTBR) pointing to its page table in memory. Every logical address translation therefore normally costs two memory accesses (one to read the page table, one for the actual data) — exactly why a TLB (see [Virtual Memory Management]) is essential in practice, not optional.

Each page-table entry also carries a valid-invalid bit: "valid" means the page belongs to the process's logical address space and is in memory; "invalid" means either the page isn't part of the process's address space at all (an illegal access → trap), or it's a legal page that simply isn't currently in memory (→ a page fault, handled by [Virtual Memory Management]). This single bit is what lets hardware distinguish "you made an error" from "you need to wait while I fetch this."

Page Table Structures — the classification examiners expect

A flat/single-level page table gets impractically large for a modern address space (see numerical below), so real systems use one of three alternatives:

Structure	Idea	Used when
Single-level (flat)	One array, one entry per virtual page, indexed directly by page number	Small address spaces only — otherwise wastes huge amounts of memory on unused regions
Multilevel (hierarchical)	The page table itself is paged (2 levels on 32-bit systems, up to 4–5 on 64-bit systems) — outer table entries can be left empty (null) for unused address regions	32-bit and 64-bit systems — the practical default
Hashed Page Table	Virtual page number is hashed into a table; each bucket is a chain of `(VPN, frame, next)` entries to resolve collisions	Address spaces wider than 32 bits, where even a multilevel table would need too many levels
Inverted Page Table	One entry per physical frame (not per logical page), storing `(PID, VPN)` — the whole system shares one table	Systems that want table size to scale with physical RAM, not with (address-space size × number of processes)

📐 Numerical — Why Multilevel Paging Exists (flat vs 2-level table size)

32-bit logical address space, page size = 4 KB (2¹²), page-table entry size = 4 bytes.

Flat (single-level) table: entries = 2³² / 2¹² = 2²⁰ = 1,048,576 entries × 4 bytes = 4 MB — per process, allocated in full even if the process only uses a few KB of address space.
2-level table: to keep each page-table page itself exactly one page (4 KB) in size, entries per table page = 4096 ÷ 4 = 1024 = 2¹⁰. That accounts for 10 bits; splitting the remaining 32 − 12(offset) = 20 bits into two 10-bit fields gives the classic layout: 10 bits (outer/directory index) + 10 bits (inner table index) + 12 bits (offset) = 32 bits.
For a process that only actively uses, say, 8 MB of address space: it needs 1 outer table (4 KB) + only the inner tables that are actually referenced — 8 MB ÷ (1024 entries × 4 KB per inner table) = 2 inner tables (2 × 4 KB = 8 KB). Total ≈ 12 KB, versus 4 MB for the flat table — a 300×+ saving, because unused regions of the address space never need an inner table allocated at all.

📐 Numerical — Inverted Page Table Size

Physical memory = 1 GB (2³⁰ bytes), frame size = 4 KB (2¹²).

Number of physical frames = 2³⁰ / 2¹² = 2¹⁸ = 262,144 frames.
An inverted page table needs exactly one entry per frame (262,144 entries total) — regardless of how many processes are running or how large each one's logical address space is.
Taking an illustrative entry size of 8 bytes (PID + virtual page number + control bits): total table size = 262,144 × 8 bytes = 2,097,152 bytes = 2 MB — fixed, system-wide.
Contrast: 50 processes each with their own flat 4 MB page table (from the numerical above) would need 50 × 4 MB = 200 MB of page-table memory in total — the inverted table's 2 MB is dramatically smaller precisely because it doesn't duplicate structure per process.
The catch: looking up a given (PID, VPN) now means searching the inverted table instead of directly indexing it — real systems pair an inverted page table with a hash table (hashing on VPN) to keep this lookup fast, rather than a full linear scan.

5. Segmentation Hardware

A Segment Table maps each segment number to a base (starting physical address) and a limit (segment length); a Segment Table Base Register (STBR) points to it, analogous to the PTBR for paging. A logical address here is (segment-number, offset); the hardware checks offset < limit (else a protection trap — a segmentation fault) before adding offset to base. Because segments are variable length and logically meaningful, permission bits (read/write/execute) can be set per segment — e.g. marking the code segment execute-only and read-only, which paging (uniform fixed-size pages with no inherent logical meaning) cannot do as naturally without extra page-level permission bits mimicking this.

6. Buddy System (a classic allocation algorithm, distinct from First/Best/Worst/Next-Fit)

Memory is only ever allocated in block sizes that are powers of 2. A request is rounded up to the nearest power of 2; if no free block of that exact size exists, the next larger available block is recursively split in half ("buddies") until a block of the right size is produced. On freeing, a block is merged back with its buddy if that buddy is also free, recursively, restoring larger blocks — an elegant compromise that makes coalescing fast (an O(log n) address-arithmetic check, no scanning) at the cost of internal fragmentation (a request for 65 units still gets a 128-unit block).

7. Swapping (contiguous-allocation-era concept, extended by demand paging today)

Swapping moves an ENTIRE process's memory image between RAM and a disk swap area to free memory for other processes — the medium-term scheduler decides which process to swap out (e.g. a long-waiting or memory-hungry one) and back in later. Pure whole-process swapping is largely obsolete on modern systems in favour of paging's finer-grained demand paging (see [Virtual Memory Management]), but the concept remains directly examinable as its own topic, and the exact step-by-step procedure was asked in CSS 2019 (see that page's numerical).

8. Overlays (the pre-virtual-memory technique)

Before demand paging existed, a program larger than available physical memory was made runnable by having the programmer (not the OS) split it into a small resident root/main module plus multiple overlay modules that are mutually exclusive in time (never needed simultaneously) and share the same physical memory region, loaded in and out under explicit program control.

📐 Numerical — Memory Saved by Overlaying

A program has a root module (50K, always resident) and two modules — Pass-1 (100K) and Pass-2 (100K) of a two-pass assembler — which are never executing at the same time.

Without overlays: all three must be resident together = 50 + 100 + 100 = 250K required.
With overlays: root (50K, resident) + a single shared 100K overlay region used first by Pass-1, then overwritten by Pass-2 on demand = 150K required.
Memory saved = 250 − 150 = 100K, letting the program run on a machine with only 150K of available memory.
Exam distinction: overlays are managed manually by the programmer/linker (deciding what can never coexist); virtual memory's demand paging achieves a similar effect automatically, managed by the OS, without the programmer needing to identify mutually-exclusive modules at all — this is the single most commonly tested contrast for this topic.

9. Relocation & Protection (why compaction/swapping are even possible)

A process cannot simply be assigned fixed physical addresses at compile time if it might be moved later (by swapping or compaction) — this is solved with dynamic relocation using a relocation register (base) and a limit register, checked by hardware on every memory reference:

Physical address = logical address + relocation register
Legal only if logical address < limit register; otherwise the hardware raises a protection trap (addressing error) before the memory access happens

📐 Numerical — Relocation & Limit Register Check

Given: relocation register = 15,000, limit register = 6,000.

CPU generates logical address 3,200: check 3,200 < 6,000 → legal → physical address = 3,200 + 15,000 = 18,200.
CPU generates logical address 6,500: check 6,500 < 6,000 → fails → trap: addressing error, access denied before it ever reaches physical memory.
Exam point: this is exactly what makes compaction and swapping safe — the OS only needs to update the relocation register's value when it moves a process; every address the process generates is still checked and translated automatically by hardware, with no change needed to the process's own code.

📐 Worked Numericals (dedicated practice pages)

Memory Management — Solved Numericals

Bitmap allocation + First-Fit + Next-Fit + linked-list/hash-table equivalents (2021, 20-mark multi-part), paging address translation (2018). The fixed-partitioning, multilevel-paging, inverted-page-table, overlay, and relocation-register numericals above are additional practice for syllabus angles not yet asked in a past paper but fully within scope.

🎯 CSS Exam Angle

Memory Management numericals reward showing the bitmap/list transformation step by step, not just the final answer — always redraw (or re-describe) the full structure after each operation rather than jumping to the end state, since past papers award marks separately for each intermediate part.
When a question just says "discuss memory management techniques," start from the classification table in Section 0 — naming both branches (contiguous vs non-contiguous) and every technique under each earns structure marks before you even get to detail.
If a question mentions a very large (64-bit-scale) address space, that is the cue to discuss Hashed or Inverted Page Tables, not plain multilevel paging — naming the right structure for the stated address-space size is itself worth marks.

📌 Past CSS Paper Frequency

Year	Question	Marks
2018	Paging address translation (VPN, offset, physical address)	6
2021	Bitmap memory management: fill bitmap, First-Fit, Next-Fit, linked-list & hash-table equivalents (5-part numerical)	20
2021	Logical/physical address space size from address-bit-width	4

⚠️ MCQ Traps

Next-Fit resumes from the last allocation point, not from index 0 — the most common error is applying First-Fit logic when the question specifies Next-Fit.
Best-Fit is not "best" for overall memory health — despite the name, it tends to leave many small, unusable fragments over time; Worst-Fit's leftover chunks are paradoxically often more reusable.
Internal fragmentation = fixed partitioning's (and Buddy System's) problem; external fragmentation = variable partitioning's (and pure segmentation's) problem. Don't swap these.
Equal-size vs unequal-size fixed partitioning: equal-size needs no fit algorithm at all (any free partition is identical); unequal-size effectively runs a Best-Fit search over a small, fixed set of partition sizes — don't describe fixed partitioning as a single undifferentiated scheme.
Segmentation ≠ Paging: segments are variable-sized and logically meaningful (code/stack/heap); pages are fixed-size and purely physical units with no inherent logical meaning. Segmentation-with-paging combines both — it is not a third, unrelated scheme.
The valid-invalid bit covers TWO distinct cases — an illegal access outside the process's space, and a legal page simply not resident yet — a question asking "what does an invalid bit mean" expects both, not just one.
The Buddy System always allocates in powers of 2, which trades some internal fragmentation for very fast merging — don't describe it as fragmentation-free.
Inverted page table size depends on physical memory size, not on the number of processes or their address-space size — the opposite is true of a flat per-process page table.
Overlays are programmer-managed; demand paging (virtual memory) is OS-managed — never describe overlays as "automatic."
Grouping speeds up satisfying multi-block requests; Counting shrinks storage for contiguous free runs — they solve different problems and are often confused with each other in MCQs.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-II · Q5(c) · 6 marks

Q. What happens in the following cases? (i) The job size (time slice) is kept very low in time-sharing systems. (ii) The page size is kept very small in paged memory management.

Ans.

(i) Very small time slice in time sharing: response to users is quick, but the CPU spends a large share of its time context switching (saving and loading registers), so the useful work drops and throughput falls. A very large slice makes the system behave like FCFS, with poor response. The quantum should be larger than most CPU bursts but not very large (typically 10–100 ms).
(ii) Very small page size:
- internal fragmentation decreases (less wasted space in the last page)
- the page table becomes very large, using more memory
- more pages mean more TLB misses and page faults
- more disk transfers, each with seek and latency overhead, so I/O efficiency falls
Trade-off: typical page sizes are 4 KB, balancing fragmentation against table size and I/O cost.

MCQs

2024 P-II · Q3. Making a system store data in memory contiguously would:

(A) Result in less computation while searching for data ✅
(B) Result in more computation while searching data
(C) Make storing data very easy, as one does not have to search for available memory to store
(D) None of these
Answer: (A).
Why: with contiguous storage the address of any item is base address + index × size, a single calculation, so access is fast and simple. Option (C) is false because finding a free block large enough for contiguous storage does need a search (and causes fragmentation).

2017 · Paper-I · Q8(d) · 5 marks

Q. Write a short note on resource allocation during runtime processes.