Memory Management, Paging, Segmentation & Virtual Memory

What main memory is

Main memory (RAM) is the only storage area the processor can address and read directly. It is a large array of bytes, each with its own address, and it is random access — any location takes about the same time to reach as any other. Everything a running process needs — its instructions, its data and its stack — must be in main memory, because the CPU fetches operands and instructions from nowhere else. It is volatile: contents disappear on power-off, which is why permanent copies live on disk.

The operating system’s memory-related job therefore starts at organization level: it must keep track of which parts of memory are free, which are in use and by whom, decide how much memory each process gets, and decide what to move in and out of main memory when it fills up.

Memory organization summary

Caching vs buffering (the required table)

The trade-off. No single technology can be fast, big and cheap at once. Speed and cost per bit track each other: the faster a memory is, the more it costs per bit and the smaller it can practically be. So a system is built as a hierarchy of levels — each level faster, smaller and dearer per bit than the one below it — with an automatic movement of data between adjacent levels so that the program sees one large, fast-looking store.

Why the hierarchy works — locality of reference

A program does not touch memory uniformly. During a short window it keeps returning to the same small region, so a fast, tiny upper level can serve most references:

• Temporal locality — items accessed now are likely to be accessed again soon (loops, the just-executed instruction stream, a hot stack frame).
• Spatial locality — items whose addresses are near each other are likely to be used near each other in time (sequential instructions, array traversal).
• Because of this, moving blocks (cache lines, pages) rather than single words up the hierarchy gives a hit rate high enough that the average access time sits near the fast level while the capacity and price sit near the cheap level.

Utility of cache memory specifically: it hides the gap between CPU speed and main-memory speed. A CPU can finish an instruction in a cycle or two but a RAM access costs many such cycles; a cache keeps the frequently used instructions and data in SRAM so the CPU rarely waits for RAM. The same principle one level down justifies the TLB (caching page-table entries) and the disk/page cache.

Main memory must hold both the operating system and the running user processes, and the OS’s job is to divide it up in the most efficient way possible. Three questions define any strategy: when are addresses fixed, must a process sit in one连续 block, and how is free space tracked.

1. Contiguous vs non-contiguous allocation

The memory is normally split into two partitions — one for the resident OS (usually low memory, because the interrupt vector lives there) and one for user processes. Into that user partition the OS places processes either contiguously (each process gets one single consecutive run of addresses, so a 20 KB process occupies 20 KB of adjacent memory) or non-contiguously (a process’s pieces may be scattered anywhere, and a table puts the pieces back together — this is paging, and in the pure sense segmentation with paging).

2. Absolute code, relocatable code, load-and-go

3. Partitioning — the strategies built on contiguous allocation

• Single contiguous allocation — OS in one part, one user process in the rest; no multiprogramming (MS-DOS).
• Multiple fixed (static) partitioning — memory pre-cut into a fixed number of holes of fixed sizes; a process gets one whole hole. Degree of multiprogramming is capped by the number of holes and waste is internal fragmentation.
• Multiple variable (dynamic) partitioning — holes are created exactly as processes arrive and leave; the OS keeps a free list. Waste is external fragmentation, cured by compaction.
• Paging / segmentation — non-contiguous allocation; no external fragmentation under paging at all (see section F).

Two basic memory-management strategies are named in the printed May-2016 answer: paging, which permits the physical address space of a process to be non-contiguous, and segmentation, which supports the user’s view of memory as a collection of named, variable-length segments addressed as (segment name, offset).

In contiguous allocation each process is contained in a single contiguous section of memory — consecutive blocks with consecutive addresses. In non-contiguous allocation the logical memory of a process is cut into pieces (pages, or segments-then-pages) and the pieces may be placed anywhere free; a per-process table records where each piece went.

The contiguous side, in the words of the printed 2016 answer

“The main memory must accommodate both the operating system and the various user processes. We therefore need to allocate the parts of the main memory in the most efficient way possible … In this contiguous memory allocation, each process is contained in a single contiguous section of memory … The relocation-register scheme provides an effective way to allow the operating system to change dynamically.”

Fixed vs variable partitioning

Multiple fixed partitioning: memory is divided once, at system generation time, into a fixed number of partitions whose sizes are then static. Each partition holds at most one process; a partition is either fully free or fully busy.

Multiple variable (dynamic) partitioning: there are no pre-set holes. The OS keeps a list of holes and, when a process of size n arrives, gives it a hole of exactly n (or n+something) and splits the remainder. When a process exits its space becomes a hole again and adjacent holes are merged.

Buddy system (named in the same question)

Memory is repeatedly halved until a block is large enough to satisfy the request: free blocks are always powers of two, and splitting a block of size 2^U creates two “buddies” of size 2^(U−1). A request S is satisfied by the smallest power-of-two block with 2^(U−1) < S ≤ 2^U (that inequality is exactly as printed in the 2019 answer). When a block is freed, its buddy is merged back if it is also free. Cost: because the block is rounded up to a power of two, the wasted space is internal fragmentation.

All three are hole-selection policies used by variable-partition allocation. The OS holds a list of free holes; a process of size n must be placed in a hole with size ≥ n, and the policy decides which such hole to take.

Which one is best?

Simulation and the papers’ own data agree: first fit and best fit both beat worst fit, and best fit makes the most efficient use of memory overall — but no policy removes external fragmentation, because in all three cases a process needs one hole that is already big enough.

Worked placement for the exam-standard data set (partitions 100K, 500K, 200K, 300K, 600K · processes 212K, 417K, 112K, 426K): under first fit 212K → 500K, 417K → 600K, 112K → the 288K remainder, and 426K must wait; under worst fit 212K → 600K, 417K → 500K, 112K → the 388K remainder and 426K again must wait; under best fit all four are placed (212K → 300K, 417K → 500K, 112K → 200K, 426K → 600K, leaving 83K/88K/174K/88K remainders). → Full table on Numericals.

Internal fragmentation is waste inside an allocated block: the OS gave the process more memory than it asked for, and the extra sliver is unusable by anyone else because it belongs to that process. External fragmentation is waste between allocated blocks: free memory exists in plenty but it is chopped into non-adjacent holes, so no single hole is large enough for the next process.

How paging solves external fragmentation

1. Logical memory is cut into equal-sized pages; physical memory is cut into the same sized frames. Because page size = frame size, any free frame can hold any page.
2. A process of 9 KB with 4 KB pages needs three frames — they may be frames 7, 2 and 11, in any order. Nothing has to be adjacent, so “no hole big enough” simply cannot happen.
3. The page table turns the scattered frames back into a contiguous-looking address space at run time.
4. The cost is that external fragmentation is traded for a small, bounded amount of internal fragmentation in the last page (the Oct-2024 answer names exactly this trade: paging → fixed-size blocks → internal fragmentation; segmentation → variable-size blocks → external fragmentation).

How compaction solves external fragmentation

Compaction shuffles the allocated blocks so that all the free holes merge into one contiguous block at one end of memory. It works only when relocation is possible at execution time — i.e. with dynamic relocation via a base/relocation register, because then moving a process just means changing its base value, not rewriting its code. Total free memory does not change; what changes is that it becomes one hole instead of ten, so the large waiting process can be admitted. The price is that it is pure overhead: potentially gigabytes copied while the system is otherwise idle.

Every instruction that a CPU executes generates an address. The set of all addresses the CPU can generate is the logical (virtual) address space; the set of addresses the memory hardware actually sees is the physical address space. The logical space is normally 0 … 2^m−1 for an m-bit address bus, and it is not the same thing as where the process really sits in RAM.

The MMU, the relocation register, base and limit registers

• MMU (memory-management unit) — the hardware device that performs the run-time mapping from logical to physical addresses. The Dec-2025 answer prints the whole chain explicitly: CPU → logical address 150 → MMU adds the base address 1000 → physical address 1150 → main memory.
• Relocation register = base register — holds the smallest physical address of this process. Its value is added to every address the CPU generates. If the base is 14000, an attempt to address location 0 is relocated to 14000, and location 346 becomes 14346 (the May-2016 printed example).
• Limit register — holds the size of the logical address space of the process. Before adding the base, the MMU compares the generated address with the limit; if the address is greater than or equal to the limit it is illegal and the CPU traps to the OS — this is hardware protection with one register pair per process, which is why a context switch only has to reload two registers.
• Changing the base register lets the OS move a running process in memory without touching its code — the flexibility that makes swapping and compaction possible.

Binding = deciding which memory address a logical address refers to. If it happens before the program starts, addresses are fixed; if it happens during execution, they can still change.

Why only run-time binding is used today

• A process can be moved in physical memory while it is executing — swap-out/swap-in, compaction, page-level replacement, all need this.
• A program larger than RAM can run at all, since its logical space need never be laid down contiguously — the basis of virtual memory (section N).
• Protection and sharing become per-process register settings instead of per-program recompilation.
• Cost: an extra hardware step on every memory reference, which is exactly why the TLB exists.

Swapping is the movement of an entire process (its code, data and stack) out of main memory onto a bulk storage area called the swap space (or backing store), and later back into memory so it can continue exactly where it stopped. It is a whole-process operation, unlike paging, which moves one page at a time.

Why swap at all

• To free memory for other processes when main memory is oversubscribed.
• To raise or lower the degree of multiprogramming according to load.
• Roll out / roll in: a lower-priority process is rolled out so a higher-priority one can be rolled in and run immediately — the classic priority-based use of swapping.

The medium-term scheduler’s role

The medium-term (intermediate) scheduler is the piece of the OS that decides swapping. The three schedulers divide the work as printed in the Oct-2024 Q.1(e) table — long term admits processes to the ready queue, short term chooses which ready process gets the CPU, and the medium term “swaps processes in/out of memory”, focusing on memory management. Concretely it:

1. Watches memory pressure and CPU utilisation.
2. Selects a victim process — usually one that is blocked or low priority — and issues the swap-out, saving its PCB state.
3. Later, when a hole large enough exists, swaps it back in and puts it on the ready queue for the short-term scheduler.
4. Thereby controls the degree of multiprogramming; the long-term scheduler does the same job at job entry, but the medium-term does it dynamically.

Swap cost — the number that makes swapping unpopular

Swap time is dominated by transfer, not by the decision. A standard worked case: a 10,000-word process swapped over a device that moves 1,000 words per millisecond needs 10 ms just for the transfer — plus positioning latency. Since swapping moves the whole process, a large process is expensive to swap, which is why demand-paged systems swap single pages instead and reserve whole-process swapping for the medium-term scheduler’s load control.

Page, frame, page size = frame size

• Page — a fixed-size block of the logical memory of a process.
• Frame — the same fixed-size block of physical memory, i.e. after RAM is cut into equal chunks.
• The two sizes are deliberately made equal, so that any page fits in any frame and physical memory never has to be searched for a hole of a particular size. External fragmentation disappears; the only waste is the slack in the last page (internal fragmentation).
• Typical page sizes: 512 B, 1 KB, 4 KB (very common), 8 KB, up to 16 MB huge pages. Larger pages ⇒ smaller page tables but more internal fragmentation; smaller pages ⇒ the reverse.

The page table

Each process has a page table: one entry per page, mapping page number → frame number (plus valid bit and protection bits). The physical memory “hole” problem is converted into a table look-up. The number of entries in a process’s page table equals its number of pages, so a page table can be very large — which is the price of paging and the reason for the TLB and for inverted page tables.

Why page sizes are powers of 2 — the real reason

Because then splitting an address into page number and offset needs no division at all — it is a pure bit-field operation. Write the address in binary and cut it after m bits, where page size = 2^m:

• the low m bits are the offset — mask them out with AND;
• the remaining high bits are the page number — shift them right by m.

page number = address >> log2(page size)   /* shift, not divide */
offset      = address & (page size - 1)      /* mask,  not modulo */
physical    = (page_table[page number] << log2(page size)) + offset

example, page size 4096 = 2^12, address 8200:
  page number = 8200 >> 12 = 2        offset = 8200 & 4095 = 8
  check: 2 × 4096 + 8 = 8200  ✔   (a division-free split — just a shift and a mask)

If the page size were, say, 1,000 bytes, the CPU would have to divide by 1000 to get the page number and take a remainder for the offset on every single memory reference. A division is many times slower than an AND and a shift, and it would sit on the critical path of every instruction. Making the page size 2^m turns the boundary between the two fields into a fixed bit position, so the hardware is a wire split — no arithmetic.

The Dec-2024 printed answer says the same thing in one sentence: “it is most efficient to break the address into X page bits and Y offset bits rather than perform arithmetic on the address to calculate the page number and offset. Because each bit position represents a power of 2, splitting an address between bits results in a page size that is a power of 2.”

Address-translation arithmetic you must be able to do

Advantages of paging as printed in the Oct-2025 answer: eliminates external fragmentation, allows non-contiguous allocation, simplifies memory management, supports virtual memory. Problems named in the same answer: internal fragmentation, large page tables, an additional memory access per reference, page faults.

(i) Logical address — 8 pages × 1024 words each = 8192 words of logical address space.

8 pages × 1024 words = 8192 words = 2^13
⇒ logical address = 13 bits   (3 bits page number + 10 bits offset)

(ii) Physical address — 32 frames, each of the same 1024 words (frame size = page size) = 32768 words of physical memory.

32 frames × 1024 words = 32768 words = 2^15
⇒ physical address = 15 bits   (5 bits frame number + 10 bits offset)

The same method on the Feb-2019 data (older paper, 10 marks)

Given: logical address space 4096 bytes, main memory 512 bytes, page size 16 bytes.

The two-step memory access problem

Under run-time mapping with a page table kept in main memory, one logical reference becomes two physical accesses:

1. access the page table (using the page number) to obtain the frame number;
2. access the actual word in that frame using the physical address.

That roughly halves instruction-execution speed — a 100 ns memory turns into an effective 200 ns per reference. The fix is to cache the translations, not the data.

TLB — what it is

A Translation Look-aside Buffer is a small, fast, hardware cache — typically 64 to 1024 entries — holding the most recent page-number → frame-number translations. It is associative: the whole page number is compared with all entries in parallel (which is why the older papers call these registers “associative registers”). It is per-process, so it is flushed or tag-guarded on a context switch, and the OS must invalidate entries when it changes a mapping.

Its role, step by step (as printed in the Dec-2024 answer)

1. CPU generates a logical address; its page-number field is searched in the TLB at the same time as the offset field is held aside.
2. TLB hit — the frame number is delivered immediately, combined with the offset, and only one main-memory access is made.
3. TLB miss — the memory-resident page table is looked up (first memory access) to get the frame number, the reference itself is then served (second access), and the freshly found translation is loaded into the TLB, replacing an older entry.
4. Because of locality, hit ratios of 80–99% are normal, so the average cost falls back to near one access per reference.

Effective access time with and without a TLB

Given: hit ratio α = 0.8, main-memory (RAM) access time t = 100 ns, TLB access time T = 50 ns.

Model. The TLB is read on every reference, so T appears in both branches. On a hit, one memory access follows. On a miss, the page table is read from memory and then the word itself is read — two memory accesses.

EAT = α(T + t)      +  (1 − α)(T + 2t)
    = 0.8(50 + 100)  +  0.2(50 + 2 × 100)
    = 0.8(150)       +  0.2(250)
    = 120.0 + 50.0
    = 170.0 ns

Sanity check: 170 ns sits between the 1-access cost (150 ns) and the 2-access cost (250 ns), and it is much better than the 2 × 100 = 200 ns you would pay with no TLB at all.

Segmentation is a memory-management scheme that supports the user’s view of memory. A logical address space is a collection of segments — each a named, variable-length logical unit: the main program, a procedure, a function, an array, a stack, a symbol table, a set of parameters. A logical address is a two-tuple <segment-number, offset>: “which piece”, and “how far into it”.

The segment is not a page in disguise: it has meaning to the programmer and the compiler, it grows and shrinks at run time, and its length is bounded by the address bits (s bits segment number, d bits offset ⇒ 2^s segments of up to 2^d bytes each).

The segment table: base + limit

Each process has a segment table holding two numbers per segment:

• Base — the starting physical address where that segment lives in memory;
• Limit — the length of the segment (its legal offset range).

Translation of logical address <s, d>: index entry s of the segment table, perform the limit check d < limit; if it passes, physical address = base(s) + d. If it fails, the reference is illegal and a segmentation-fault trap is raised — note that this hardware check is nothing to do with the “segmentation fault” of a badly written C program, it is the OS refusing an out-of-range address.

Protection and sharing fall out for free

• Protection: because segments are logical units, per-segment control bits make sense — code segment read/execute-only, data segment read/write, stack read/write/expand. Any attempt to write the code segment or to execute the stack faults.
• Sharing: two processes that use the same routine need only store the same base and limit in their segment tables, so a single physical copy is shared with segment-number agreement. Sharing a page is possible in paging too, but you cannot share “just the code part” of a page that also holds data.

Worked example (printed in the Oct-2025 answer)

Logical address (1, 200):
  check  200 < limit(1) = 700  → legal
  physical = base(1) + 200 = 3000 + 200 = 3200

Two more references on the same table, to show the check: (0, 431) is legal — 431 < 500 — and maps to 1000 + 431 = 1431; (2, 1400) is illegal because 1400 ≥ limit(2) = 1000, so the hardware traps instead of producing an address.

Problems associated with segmentation (as printed in the Oct-2025 answer)

The four rows the Oct-2024 answer prints, in its own order

1. Basic / fragmentation — fixed block size → internal fragmentation vs variable size → external fragmentation.
2. Address — CPU splits the user address into page number + offset vs the user supplying segment number + offset.
3. Size — hardware decides the page size vs the user specifies the segment size.
4. Table — page table holds the base address of each page vs segment table holds segment number and segment length.

Which one is better, and why — the Dec-2025 Q.4(a) answer

For modern operating systems, paging is generally considered better because:

1. It eliminates external fragmentation.
2. Memory allocation is simpler.
3. It works efficiently with virtual memory.
4. It is easier for the operating system to manage.

The same answer then adds the honest counterpoint, which is worth one line for full marks: however, segmentation is better for representing the logical structure of programs (code segment, data segment, stack segment) and provides more natural protection and sharing mechanisms — which is why real systems end up using segmentation with paging rather than choosing between them.

The problem it solves. Pure segmentation gives the user what they want — named, variable-length, separately protected and shareable logical units — but it inherits every ill of contiguous allocation: each segment must land in one contiguous run of free memory, so external fragmentation and compaction come back. Pure paging fixes placement (any frame will do) but destroys the user’s view: a page is a meaningless fixed-size slice that can straddle the end of one routine and the start of the next, so per-module protection and sharing get blunt.

The two-level scheme keeps both benefits. The address space is still divided into segments, but each segment is now paged into fixed-size pages, and those pages are allocated into any free frames. Segmentation supplies the programming-in-the-large structure; paging supplies the allocation mechanism underneath it.

Address generation, step by step

1. The CPU produces a logical address of the form <segment-number s, page-number p, offset d>.
2. Entry s of the segment table is fetched. It holds a segment-table entry (STE): a base that now points at the page table for that segment, plus the segment limit and protection bits.
3. Entry p of that segment’s page table is fetched. It holds a page-table entry (PTE): the frame number (plus a valid bit — the page may be out on disk).
4. The physical address is formed by concatenating the frame number with the offset: frame × frame size + d.

What it buys, and what it costs

Worked bit-field numerical (Jun-2019 Q.2(b), 4 marks)

Given: a system using paging and segmentation with a virtual address space of up to 8 segments, each segment up to 2²⁹ bytes long, the hardware paging each segment into 256-byte pages.

More page/frame arithmetic (Feb-2019 Q.4, Feb-2018 Q.4, Jun-2019 Q.2(b) variants) is worked on Numericals.

Definition. Virtual memory is a memory-management technique that lets a system run a process even when not all of that process is in main memory. It does this by separating the logical address space — the program’s own view, which may be enormous — from physical memory, which is limited, and by bringing pages in from the backing store only when they are actually referenced (demand paging). The programmer sees a contiguous address space of 2^m words; the hardware only ever holds the active subset.

The two advantages asked for (3 marks)

1. A program bigger than physical memory can run, and more programs fit at once. Only the pages currently needed occupy RAM, so the sum of the logical address spaces of all processes may greatly exceed the size of main memory. Memory that would otherwise sit idle holding not-yet-used parts of a program is released for other work, which raises the degree of multiprogramming and therefore CPU utilisation and throughput.
2. Faster start-up and cheaper, simpler programming. Loading a program no longer waits for its whole image to be read from disk — execution can begin as soon as the first page(s) are present, so response and load times drop, and the I/O per job falls too. Programs may also be written against a large, uniform, private address space, with code, data and stack segments protected and shared through the MMU, instead of the programmer having to fit inside the RAM that happens to be free.

Separation of logical from physical — the mechanism in one paragraph

• Compile/link produces a logical address space that starts at 0 and is as large as the address width allows.
• Run-time mapping by the MMU (Fig G-1) turns each reference into a physical one; with paging the mapping is per page, so a process’s physical footprint can be a scattered, partial subset of RAM.
• A page not present in RAM is not an error — it is a page fault, and the OS brings it in (section P). That trap-and-fetch behaviour is precisely what makes the logical space bigger than physical memory without the program noticing.
• Consequence for the OS: memory management becomes a policy problem — which pages to bring in (fetch policy: demand or prepaging) and which to throw out (placement policy: where in memory; replacement policy: which page).

Definition as printed in the Dec-2025 answer

Demand paging is a virtual memory technique in which a page is loaded into main memory only when it is required by a process. Instead of loading the entire program into memory at once, pages are brought into RAM on demand.

Working of demand paging (the five steps to write)

1. A process starts execution.
2. If the required page is already in memory, execution continues.
3. If the page is not in memory, a page fault occurs.
4. The operating system loads the required page from secondary storage (disk) into a free frame in RAM.
5. The page table is updated and execution resumes.

Demand paging is a lazy form of paging: a process is not loaded page by page in advance. Only the pages actually needed at this moment are brought into memory, and a page is fetched only when it is referenced — on demand. The loader never reads the disk blocks of a page that is not yet needed, so a job can start executing with only its first page (or even nothing) resident. Because it swaps pages rather than whole processes, demand paging is also called lazy swapping.

The valid / invalid bit

• Every page-table entry carries one extra bit: v (valid) or i (invalid).
• valid — this page is currently in memory; the frame number in that entry is real and usable.
• invalid — this page is not in memory right now (it was never brought in, or it was swapped out). Any reference to it must not use that entry’s frame number.
• At the very start of a demand-paged process all entries are marked invalid, which is exactly the trick that allows a program to be “loaded” with zero page reads.
• An attempted reference to an invalid page generates a trap to the operating system — this is the page fault handled in section P. The OS finds a free frame, reads the page from the backing store, changes the entry to valid with that frame number, and restarts the instruction.
• Once every page of a process is valid, the process’s memory can no longer grow by faulting — that boundary is what limits a purely paged, non-virtual system.

Pure paging vs demand paging

When demand paging pays off — locality

A typical process references a small fraction of its pages most of the time (loops, hot functions, the active part of the stack). Because of that locality of reference, a modest number of frames can serve a huge address space with a low fault rate. If the fault rate p is small, the cost of virtual memory is nearly invisible; if p grows, the system collapses into thrashing — see the EAT formula in section R.

Page fault — in a demand-paged system, an attempted reference to a page whose page-table entry is marked invalid, i.e. the page is not currently in a physical frame. The hardware traps to the operating system, which brings the page in from the backing store and then lets the same instruction run again. A page fault is not an error; it is the normal working mechanism of virtual memory.

Handling sequence (write these steps in this order)

1. The CPU generates a logical address and the MMU consults the page table.
2. The valid/invalid bit for that page is checked. If valid → nothing unusual happens; the memory reference is completed normally and execution continues.
3. If invalid → the hardware raises a trap to the OS: the page-fault trap handler takes over and saves the process state.
4. The handler examines the trap to confirm it really is a page fault (not an illegal address and not an I/O trap), and identifies which page is needed.
5. The handler checks the page is a legal one for this process (in its address space and within its limits). An illegal reference means the process is terminated; a legal one continues below.
6. A free frame is taken from the free-frame list. If there is no free frame, the page replacement algorithm picks a victim page.
7. If that victim has been modified (its dirty bit is set) it is first written back to the backing store — one extra swap-out; if it is clean it can simply be overwritten.
8. The needed page is scheduled for a disk read into the chosen frame; the faulting process is blocked and the CPU scheduler switches to another ready process (this idle time is what paging hardware exists to exploit).
9. On completion of the I/O the frame is filled; if the frame is shared, the OS copies the new page into each private copy.
10. The page-table entry (and usually the TLB) is updated: frame number written in and the valid bit set.
11. The faulting instruction is restarted exactly where it left off — the program never learns that a fault happened, and this time the reference hits memory.

Hard vs soft page fault (Jun-2019 Q.1(d), 2.5 marks)

Why page replacement is needed

A process is given fewer frames than it has pages, and the total demand of all processes exceeds physical memory. So when a page fault occurs and the free-frame list is empty, the OS cannot simply read the page in — it must first choose a page that is already resident and evict it. If the victim is clean it can be discarded and its frame reused; if it is dirty (modified bit set) it must be written back to backing store first, so a fault costs two memory transfers instead of one. The rule for picking the victim is the page-replacement algorithm.

The reference-string model

• A process’s page accesses are abstracted into a string of page numbers — e.g. 7, 0, 1, 2, 0, 3, 0, 4, … Each number is a reference to that page.
• The process is given n frames, all empty to start with (an empty frame is always used first, and that still counts as a fault).
• Walk the string left to right: a reference to a page already in a frame is a hit; otherwise it is a page fault and, when there is no free frame, the algorithm names the victim.
• The score of an algorithm is the total number of page faults it produces on the string — fewer faults means a lower effective access time.
• The model assumes all frames are empty at the start, references the same string for every algorithm so the comparison is fair, and ignores the cost of a modified victim (which in reality makes FIFO look worse than it scores here).

FIFO — First-In, First-Out

Replace the page that has been in memory longest. Keep the resident pages in load order and evict the head; conceptually it needs one register per page holding its load time, or a queue.

• Merits: trivially easy to understand and to implement — a queue or a clock-hand variant is enough; no per-reference updates, so no extra hardware cost.
• Demerits: age is a poor guide to future use — an old page inside a hot loop gets thrown out and faults straight back; and it suffers Belady’s anomaly (more frames, more faults).

LRU — Least Recently Used

Replace the page that has gone longest without being referenced. It is the reverse of FIFO in one important respect: it uses the past usage order as a prediction of future use, which is justified by locality of reference — a page not touched for a long time is unlikely to be touched soon.

• Merits: usually far fewer faults than FIFO on real strings; it never suffers Belady’s anomaly, because it is a stack algorithm — the set of pages LRU would hold in n − 1 frames is always a subset of the set it holds in n frames, so adding frames can never increase faults. Implemented by counters (load the smallest counter on a fault), a stack (move the referenced page to the top), or the clock/second-chance approximation used by real OSs.
• Demerits: expensive in pure hardware — every memory reference must reorder the structure, so it needs special registers or frequent timer updates; OSs therefore approximate it.

Optimal (MIN / Belady’s algorithm) — replace the page used farthest in the future

Look forward along the reference string and evict the page that will not be needed for the longest time (a page never used again is the perfect victim).

• Merits: provably the fewest faults of any algorithm for the same number of frames and the same string, so it is the benchmark the others are measured against. It also never suffers Belady’s anomaly.
• Demerits: requires future knowledge of the reference string, so it is not implementable in a real OS (only approximable, e.g. by a working-set model).

The ordering rule to remember

So the safe wording is: “Optimal is always ≤ the others; LRU is normally better than FIFO but not guaranteed — check the string.” The full traces and Gantt-style frame grids are on Numericals · page replacement.

Definition. Belady’s anomaly is the counter-intuitive property of some page-replacement algorithms — FIFO is the classic case — whereby increasing the number of page frames can increase the number of page faults. It is named after László Bélády, who demonstrated it in 1969. It should be impossible: more memory ought to mean fewer misses. Its existence proves that FIFO is not a stack algorithm.

The worked demonstration (the example printed in the Jul-2016 answer)

Reference string: 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4

Why it happens: FIFO evicts by age of loading, and a page’s load order is not related to its future use. Adding a frame therefore does not simply “keep one more page” — it re-orders the whole eviction sequence, and the new sequence can evict a page an instant before it is referenced. With LRU this cannot happen: if a page would be kept in n − 1 frames by recency, it is certainly kept in n frames, so the resident set for n − 1 frames is a subset of that for n frames (the stack property) and faults can only fall or stay equal. Optimal has the same guarantee.

Factor 1 — page-table size

A page table is another table in memory, and one entry is needed for every page of every process, so the table is large and must itself be stored in main memory. Its size is fixed by the number of address bits:

• With a 16-bit address and a 1 KB (2¹⁰) page: 2⁶ = 64 entries — a few hundred bits per process, easily affordable.
• With a 32-bit address and a 4 KB (2¹²) page: 2²⁰ = 1,048,576 entries, which at 4 bytes an entry is about 4 MB of page table for one process — which is why real systems use multi-level, hashed or inverted page tables.
• An inverted page table has one entry per frame, not per page, so its size is fixed by physical memory and is shared by all processes (Feb-2019 Q.4 asked exactly this: 32 frames ⇒ 32 entries, versus 256 entries in the ordinary table).

Factor 2 — address-space size

The size of a process’s logical address space is decided by the address width, not by how much RAM exists: 2^m × n bytes for an m-bit logical address with n-byte words. The physical address space is decided by the number of frames × frame size. Those two are independent — and in a virtual-memory system the logical space is normally much larger, which is the whole point (Dec-2024 Q.5(b): 13-bit logical against 15-bit physical; Feb-2019 Q.4: 12-bit logical against 9-bit physical, where RAM is smaller than the program).

Factor 3 — the effective access time formula

Let p be the page-fault rate (0 ≤ p ≤ 1; p = 0 means no faults, p = 1 means every reference faults), ma the memory-access time and pf the total fault overhead. Then:

EAT = (1 − p) · ma  +  p · (page-fault overhead + swap page out
                              + read (swap) page in + swap page in)

      = (1 − p) · ma  +  p · pf

• Page-fault overhead = service the interrupt + find a free frame + start the disk read + update the table + restart the instruction.
• “Swap page out” appears only when the victim page is modified; a clean victim is discarded without a write.
• “Read page” is bounded by seek + rotational latency + transfer, and dominates everything else.
• The value of p cannot be computed — it is a property of the program’s behaviour, so it is measured empirically (count faults over an interval and divide by the number of references), or estimated from the reference string, as in thrashing.
• Magnitude check with the numbers from the paper: ma = 100 ns and a fault service time of 25 ms = 25,000,000 ns. Even at p = 0.001, EAT = 0.999(100) + 0.001(25,000,000) ≈ 25,100 ns — a 250-fold slowdown. That is the real lesson of the question: virtual memory is only worth having while p stays very small.

Meaning. A process is thrashing when it is spending more time paging than executing. It does not have enough frames to hold the pages it is actively using, so it page-faults, replaces a page that it needs again almost immediately, faults again, and keeps cycling. The system as a whole looks busy — the paging device queue is full — while doing almost no useful work. The May-2016 printed definition is the one to quote: “A process is thrashing if it is spending more time paging than executing.”

Cause — the chain the papers ask for

1. The OS monitors CPU utilisation. If utilisation is too low, it raises the degree of multiprogramming by admitting another process — without regard to which processes already own frames.
2. A process enters a new phase of execution and needs more frames. It starts faulting and takes frames away from other processes.
3. Those processes need the pages that were taken from them, so they fault too, and steal frames in turn.
4. All these faulting processes queue for the paging device. While they wait, the ready queue empties and CPU utilisation falls.
5. The CPU scheduler sees falling utilisation and reacts the only way it knows — it admits even more processes, which steals more frames and lengthens the paging queue.
6. The feedback loop closes: page-fault rate rises tremendously, effective memory-access time rises, and no work gets done because the processes spend all their time paging. The frame allocation may even fall below the minimum a low-priority process needs, forcing it to be suspended and paged out entirely — the “swap-in, swap-out level of intermediate CPU scheduling” named in the May-2016 answer.

Effect

• CPU utilisation and system throughput collapse, while paging-device utilisation saturates.
• Effective access time explodes — the EAT of section R with p → 1.
• Response time and turnaround time become terrible even though the ready queue is short.
• The system may appear hung; the swap/paging device is the bottleneck, not the CPU.

Relationship in words

As the degree of multiprogramming increases, CPU utilisation also increases — but more and more slowly — until a maximum is reached. If the degree of multiprogramming is increased even further, thrashing sets in and CPU utilisation drops sharply. At that point, to raise CPU utilisation and stop thrashing, the only remedy is to decrease the degree of multiprogramming. The counter-intuitive part — that “more processes” must mean “less work done” — is the answer’s centre of gravity.

How to eliminate / prevent it

• Reduce the degree of multiprogramming — suspend (swap out) some processes and free their frames for the ones that remain. This is the direct, printed remedy.
• Give each process at least the number of frames it needs for its active pages, instead of spreading frames evenly; the two standard formulations of “how many that is” are the working-set model and the page-fault-frequency (PFF) control.
• Monitor the page-fault rate per process (counters + a timer, or reference bits) and act on it: raise a process’s allocation while its fault rate is above target, lower it when below — but never let the sum of allocations exceed capacity.
• Prevent the feedback loop: do not use CPU utilisation alone as the admission signal, because during thrashing low utilisation is a symptom, not a reason to admit more work.

Demand segmentation is the application of lazy loading to segments instead of pages. Not all of a process’s segments are brought into memory when it starts, and — as the Jan-2024 answer to Q.5(a) puts it for virtual-memory segmentation — segments may be “created but not all at once, not at run time of the program”; a segment is loaded only when the program first references it. Until then its segment-table entry is marked invalid.

How it works

• Each process is divided into logical segments (main routine, procedure, array, stack …) exactly as in section K.
• The segment table entry carries base + limit plus a valid bit. Invalid = not resident.
• A reference to an invalid segment causes a segment fault: the OS traps, finds a free block of memory large enough for the whole segment, reads it in from the backing store, updates the entry to valid and restarts the instruction.
• Advantages are the same ones as for demand paging: startup I/O and memory per process are both proportional to what is actually used, and the logical address space can be much bigger than RAM.

Why it is rarely used

The practical resolution: real systems keep the user-visible segmentation and put demand paging underneath it — segmentation with paging (section M), or the pure-virtual-memory-over-segments variant used by the Intel Core architecture. Then the on-demand unit is a fixed-size page, any free frame will accept it, and the “find a hole as big as the segment” problem disappears. That single sentence is the answer to “why is demand segmentation not used?”.

Overlay. An overlay is a program module that is kept on disk and loaded into main memory only while it is needed, then overwritten by another module when control moves on. The program is split into pieces that are never required simultaneously, and one fixed region of memory — the overlay area — is shared by all of them: whatever is needed now occupies it. This lets a program larger than available memory run on a system with no virtual memory at all, which is exactly what early compilers, assemblers and linkers did.

Who decides — the key distinction. In overlays the programmer (or the program’s own structure) decides which routines are mutually exclusive, how big the overlay area must be, and when to call the overlay driver to load the next module. In swapping and paging the operating system makes all those decisions, with the program completely unaware. That one difference — programmer-managed versus OS-managed — is the mark.

Overlay structure — a small worked example

Suppose a program whose memory budget is 32 KB consists of a main routine that is always active plus three branches of which only one runs at a time:

Memory layout (32 KB budget)
  0  – 11 KB   main routine            (resident)
 12  – 13 KB   overlay driver          (resident)
 14  – 23 KB   OVERLAY AREA  = 10 KB   ← the biggest single module, A or B or C at a time
 24  – 31 KB   data area

Without overlays : 12 + 8 + 6 + 10 + 2 = 38 KB  → does NOT fit in 32 KB.
With overlays    : 12 + 2 + 10 = 24 KB resident, 8 KB spare  → fits.

Run sequence
  main → driver.load(A) → run A → return → main → driver.load(B) → run B → …
  Loading B overwrites the bytes that held A; A is re-read from disk only if needed again.

Three rules the example shows, and the ones worth stating in an answer:

1. Only mutually exclusive modules may share one overlay area — the split must follow the program’s control flow, otherwise a needed module gets overwritten.
2. The overlay area must be at least as large as the largest module that can occupy it (10 KB above), so a single oversized module ruins the design.
3. Time is traded for space: every re-load is a disk read, so the frequently needed module should be made resident and the rarely needed ones overlaid.