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.
Each process is allocated one single contiguous block of main memory.
| 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
{tag, start, length, next}. Faster to scan for holes than a raw bitmap since runs are already pre-computed.(start, length), giving O(1) average lookup of where a named item currently lives — a complement to, not a replacement for, the bitmap/linked-list free-space search.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 (paging address-translation numericals are covered on the Virtual Memory Management page since paging is the mechanism underlying demand-paged virtual memory).
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."
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.