For the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO replacement produces 9 page faults with 3 frames and 10 with 4 frames. This shows that:

FIFO can suffer Belady’s anomaly, because it is not a stack algorithm

The simulation contains an arithmetic error, since more frames cannot increase faults

FIFO can suffer Belady’s anomaly, because it is not a stack algorithm

The reference string is not a valid one

Which of the following statements about page replacement are true?

Belady’s anomaly can occur under FIFO replacement

LRU can never produce more faults with more frames

The optimal algorithm needs knowledge of future references

Belady’s anomaly can occur under FIFO replacement

LRU can never produce more faults with more frames

LRU always produces at most as many faults as FIFO on the same string and frame count

The optimal algorithm needs knowledge of future references

Which file allocation strategy cannot provide direct access to the k-th block of a file without reading the earlier blocks?

All three provide direct access

Internal fragmentation is characteristic of paging, while external fragmentation is characteristic of segmentation. The reason is:

Paging allocates fixed-size units, so waste falls inside the last unit; segments vary in size, so waste falls between them

Pages are smaller than segments

Paging allocates fixed-size units, so waste falls inside the last unit; segments vary in size, so waste falls between them

Segmentation does not use a page table

Paging requires compaction and segmentation does not

Memory Management, Virtual Memory and File Systems

Virtual memory is one idea with a large amount of arithmetic hanging off it: let a program address more memory than exists, and keep only the pages it is using in RAM. Paging is the mechanism. A virtual address splits into a page number and an offset, the page number indexes a page table to get a frame number, and the offset is carried across untouched — which is the fact that makes every address-translation question mechanical, because the offset width is fixed by the page size and everything else follows. Two costs then appear, and both are examined numerically. The first is time: a page table in memory means every access needs two memory accesses, which is why there is a TLB, and why the expected access time is a weighted average you compute rather than recall. The second is space: a 32-bit address space with 4 KB pages needs 2²⁰ entries, so a single-level page table is 4 MB per process, which is why real page tables are multi-level. Then page replacement, where the questions are almost entirely counting page faults on a given reference string — and where one result is worth carrying in first, because it is deeply counter-intuitive: more frames can mean more page faults. That is Belady’s anomaly, it happens under FIFO, and it cannot happen under LRU or OPT for a structural reason worth understanding rather than memorising. Finally file systems, which reduce to one question asked in a dozen costumes: given this way of recording where a file’s blocks are, what is the largest file, and can you reach block k without reading the ones before it?

The Two Costs of a Page Table

A page table lives in memory, so a naive lookup costs two memory accesses per instruction — one to read the entry and one to fetch the data. The TLB is a small associative cache of recent translations that removes the first access on a hit, and the expected time is then a weighted average over hit and miss. Take a TLB access of 20 ns, a memory access of 100 ns, and a hit ratio of 80%, with the convention that the TLB is consulted first and memory afterwards. On a hit the cost is 20 + 100 = 120 ns; on a miss it is 20 + 100 + 100 = 220 ns, because you pay for the failed lookup, then the page table, then the data. So EMAT = 0.8(120) + 0.2(220) = 96 + 44 = 140 ns. Raise the hit ratio to 90% and it falls to 130 ns — each 10 points of hit ratio is worth exactly one memory access, which is a useful sanity check on any answer.

⚠️ State the TLB convention, because two are in circulation

The same numbers give different answers under two different reasonable readings, and a question that does not say which it means is ambiguous rather than hard. Under TLB-then-memory (used above) a hit costs TLB + memory = 120 ns. Under overlapped lookup, where the TLB is searched while the memory access begins, a hit costs just the memory access, 100 ns, and the miss penalty is what the TLB time adds. A third variation charges only one memory access on a miss, treating the page table as cached. So: read the question for the words TLB access time against TLB lookup is overlapped, and if it is silent, use TLB-then-memory and say so — that is the convention almost every Indian textbook and previous GATE paper uses. What is never negotiable is the structure: EMAT = (hit ratio)(cost of a hit) + (miss ratio)(cost of a miss), and the arithmetic slip to avoid is forgetting that a miss still pays the TLB time it wasted.

🧠 Page table size, and why two levels

Everything comes from the offset. With 4 KB pages the offset is 12 bits, so a 32-bit virtual address leaves 20 bits of page number and therefore 2²⁰ = 1,048,576 pages. At 4 bytes per entry that is 2²² bytes = 4 MB of page table, per process, resident, whether or not the process uses that much memory — which is the whole motivation for the multi-level design. Now split it: 4 KB / 4 bytes = 1024 = 2¹⁰ entries fit in one page of table, so the 20-bit page number divides into 10 | 10, giving the classic 10 | 10 | 12 breakdown of a two-level 32-bit scheme. The saving is not in the total size but in what must be resident: the outer table is one page, and only the inner tables covering pages actually in use need to exist. The same arithmetic answers the reverse question too — asked for the number of levels, divide the page-number width by log₂(entries per page) and round up.

ℹ️ Paging fragments internally; segmentation fragments externally

The two schemes fail in opposite ways, and the pair of words is examined directly. Paging uses fixed-size frames, so a request always fits some free frame exactly and there is never an unusable gap between allocations — but the last page of a process is usually partly empty, which is internal fragmentation, averaging half a page per process. Segmentation uses variable-size segments matched to logical units, so nothing is wasted inside a segment — but freeing segments of different sizes leaves holes too small to use, which is external fragmentation, and it is the one that needs compaction to fix. The compact statement: paging wastes space inside the last allocation, segmentation wastes it between allocations. Combined schemes (paged segmentation) exist precisely to keep segmentation’s logical view while paying only paging’s internal cost.

Page Replacement, Counted on One String

The table below runs the standard reference string 1 2 3 4 1 2 5 1 2 3 4 5 through all three algorithms at both 3 and 4 frames, because the interesting facts are all comparisons and a single row shows none of them. Count faults by simulating: a reference to a page already resident is a hit and changes nothing except (for LRU) the recency order; a reference to an absent page is a fault, and if every frame is occupied the algorithm’s rule chooses the victim — FIFO evicts the page loaded longest ago, LRU the page used longest ago, OPT the page whose next use is furthest in the future.

Page faults on 1 2 3 4 1 2 5 1 2 3 4 5, computed by simulation
Algorithm	3 frames	4 frames	What the pair shows
FIFO	9	10	Belady’s anomaly — more frames, more faults
LRU	10	8	A stack algorithm — never worse with more frames
OPT	7	6	The unreachable lower bound, needing the future

🎯 Why FIFO can get worse and LRU cannot: the stack property

An algorithm is a stack algorithm when the set of pages it keeps in n frames is always a subset of the set it would keep in n + 1 frames. If that holds, every hit at n frames is still a hit at n + 1, so the fault count cannot rise and Belady’s anomaly is impossible. LRU has the property: the pages it holds are the n most recently used, and the n most recent are always among the n + 1 most recent. OPT has it for the same reason with the future in place of the past. FIFO does not, and the reason is that its choice ignores use entirely — it evicts by load order, so adding a frame changes the arrival pattern of evictions and can throw out a page that the smaller configuration happened to keep. That is not a flaw in the arithmetic; it is a real behaviour, and 9 → 10 above is it. The examinable statement is therefore precise: Belady’s anomaly can occur under FIFO, cannot occur under LRU or OPT, and the reason is a subset relation rather than anything about how good the algorithms are.

⚠️ LRU is not always better than FIFO — on this very string it is worse

Read the 3-frame column again: FIFO takes 9 faults and LRU takes 10. LRU is the better heuristic — it approximates OPT by betting that recent use predicts future use — but a heuristic is a bet, and on a particular string it can lose. This one cycles through 1, 2, 3, 4 in a way that keeps evicting exactly the page about to be needed, which punishes recency. So two claims must be kept apart, because options routinely conflate them. True: LRU never suffers Belady’s anomaly, because it is a stack algorithm. False: LRU always produces fewer faults than FIFO. The first is a theorem about one algorithm across frame counts; the second is a comparison between algorithms on a fixed frame count, and no such guarantee exists. If a question gives you a string, count — do not reason from which algorithm is supposed to be smarter.

File Allocation: Largest File, and Direct Access

The three allocation strategies, on the two things questions ask
Strategy	Direct access to block k?	Main weakness
Contiguous	Yes — start + k	External fragmentation; a file cannot grow in place
Linked	No — you must walk k links	No direct access; one bad pointer loses the tail
Indexed (inode)	Yes — read the index block	The index itself costs space, and needs indirection to scale

🧠 The inode maximum-file-size computation, done once

Take an inode with 10 direct pointers, one single-indirect and one double-indirect, a 1 KB block and a 4-byte pointer. Everything follows from one number: a block holds 1024 / 4 = 256 pointers. Now add up what each kind of pointer reaches. The 10 direct pointers reach 10 blocks. The single indirect points at one block of pointers, reaching 256 blocks. The double indirect points at a block of 256 pointers, each of which points at a block of 256 pointers, reaching 256 × 256 = 65,536 blocks. Total = 10 + 256 + 65,536 = 65,802 blocks, and at 1 KB each that is 65,802 KB = 64.26 MB. Two habits make this reliable. Compute pointers-per-block first and write it down, because every later term is a power of it. And answer in the unit the question asks for — a great many marks are lost converting 65,802 KB to MB by dividing by 1000. If a triple indirect is present it adds 256³ = 16,777,216 blocks and dwarfs everything before it, which is why the direct pointers matter for small files and nothing else.

Key takeaways

The offset is carried across translation untouched, so the page size fixes it and everything else follows.
EMAT = (hit)(TLB + memory) + (miss)(TLB + memory + memory) — a miss still pays the wasted TLB time.
32-bit space, 4 KB pages, 4-byte entries: 2²⁰ pages, a 4 MB flat table, and a 10 | 10 | 12 two-level split.
Paging wastes space inside the last allocation; segmentation wastes it between allocations.
Belady’s anomaly is real: FIFO takes 9 faults at 3 frames and 10 at 4 on 1 2 3 4 1 2 5 1 2 3 4 5.
LRU and OPT are stack algorithms, so the anomaly cannot occur — but LRU can still lose to FIFO on a string.
Compute pointers-per-block first; every indirect term is a power of it.
Linked allocation is the one that cannot reach block k directly; contiguous and indexed both can.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

A TLB access takes 20 ns and a memory access 100 ns. The page table is in main memory and the TLB hit ratio is 80%. The TLB is consulted first and memory afterwards. The effective memory access time in ns is ______
Numerical answer — type the value.
Show answer
Answer: 140
140 ns. On a hit the translation comes from the TLB and one memory access fetches the data: 20 + 100 = 120 ns. On a miss the TLB lookup is wasted but still paid for, then the page table is read from memory, then the data: 20 + 100 + 100 = 220 ns. Weighting: 0.8(120) + 0.2(220) = 96 + 44 = 140. The commonest wrong answer is 120, from forgetting that a miss costs an extra memory access rather than the same one. The second commonest is 116, from omitting the TLB time on a miss — but the lookup happened, so it is charged. A quick sanity check: the answer must lie strictly between 120 and 220, and much nearer the first because hits are four times as likely.
For the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO replacement produces 9 page faults with 3 frames and 10 with 4 frames. This shows that:
1. The simulation contains an arithmetic error, since more frames cannot increase faults
2. FIFO can suffer Belady’s anomaly, because it is not a stack algorithm
3. The reference string is not a valid one
4. FIFO is always worse than LRU
Show answer
Answer: B — FIFO can suffer Belady’s anomaly, because it is not a stack algorithm
Belady’s anomaly, and it is a real behaviour rather than a mistake. An algorithm is a stack algorithm when the pages it holds in n frames are always a subset of those it would hold in n + 1; that guarantees every hit survives an extra frame, so faults cannot rise. LRU has the property (the n most recent are among the n + 1 most recent) and so does OPT; FIFO does not, because it evicts by load order and ignores use entirely, so adding a frame reshuffles which pages happen to be oldest. Option A is the intuition the question exists to break. Option D overreaches in a way this very string refutes — at 3 frames LRU takes 10 faults here against FIFO’s 9, so LRU is not always better; what is always true is only that LRU cannot show the anomaly.
An inode has 10 direct block pointers, one single-indirect pointer and one double-indirect pointer. The block size is 1 KB and each block pointer is 4 bytes. The maximum file size in MB, rounded to two decimal places, is ______
Numerical answer — type the value.
Show answer
Answer: 64.26
64.26 MB. Compute pointers per block first: 1024 / 4 = 256. Then each pointer class contributes a power of that. Direct: 10 blocks. Single indirect: one block of pointers, so 256 blocks. Double indirect: 256 pointer blocks each holding 256 pointers, so 256² = 65,536 blocks. The total is 10 + 256 + 65,536 = 65,802 blocks, and at 1 KB per block that is 65,802 KB. Dividing by 1024 gives 64.26 MB. Two traps sit in this one question. Dividing by 1000 instead of 1024 gives 65.80, which is the most frequently seen wrong answer. And note the double indirect supplies 99.6% of the total, so an answer near 64 MB is right while one near 0.25 MB means the squaring was dropped.
A system has a 32-bit virtual address space, 4 KB pages and 4-byte page table entries. The size of a single-level page table per process is:
1. 1 MB
2. 4 MB
3. 4 KB
4. 1 GB
Show answer
Answer: B — 4 MB
4 MB. A 4 KB page needs a 12-bit offset, leaving 32 − 12 = 20 bits of page number, so there are 2²⁰ = 1,048,576 pages and therefore that many entries. At 4 bytes each: 2²⁰ × 2² = 2²² bytes = 4 MB, per process, and resident whether the process uses that much memory or not. That figure is the entire motivation for multi-level page tables — 4 KB / 4 bytes = 1024 entries fit in one page, so the 20-bit page number splits 10 | 10 and only the inner tables covering pages actually in use need to exist. Option A drops the entry size and reports the count of pages in mega-units. Option C is the size of one page of the table, not the table. Option D would follow from a 4-byte entry per byte of address space, which is off by the page size.
Which of the following statements about page replacement are true?
1. Belady’s anomaly can occur under FIFO replacement
2. LRU can never produce more faults with more frames
3. LRU always produces at most as many faults as FIFO on the same string and frame count
4. The optimal algorithm needs knowledge of future references
Show answer
Answer: A — Belady’s anomaly can occur under FIFO replacement; B — LRU can never produce more faults with more frames; D — The optimal algorithm needs knowledge of future references
A, B and D. A is Belady’s anomaly, demonstrated on 1 2 3 4 1 2 5 1 2 3 4 5 where FIFO goes 9 → 10 faults from 3 frames to 4. B is the stack property: LRU holds the n most recently used pages, which are always a subset of the n + 1 most recently used, so no hit is lost by adding a frame. D is the definition of OPT and the reason it is a benchmark rather than an implementation — it evicts the page whose next use is furthest away, which requires the reference string in advance. C is false, and the same string refutes it: at 3 frames LRU takes 10 faults against FIFO’s 9. LRU is the better heuristic, betting that recent use predicts future use, and this string is built to punish exactly that bet by cycling through pages so that the least-recently-used one is always the next needed. Keep the two claims separate: B is about one algorithm across frame counts and holds; C is a comparison between algorithms at a fixed frame count and does not.
Which file allocation strategy cannot provide direct access to the k-th block of a file without reading the earlier blocks?
1. Contiguous allocation
2. Linked allocation
3. Indexed allocation
4. All three provide direct access
Show answer
Answer: B — Linked allocation
Linked allocation. Each block stores the address of the next, so the address of block k is only discoverable by reading blocks 0 through k − 1 — k disk accesses to reach one block, which is why linked allocation suits sequential files and nothing else. Contiguous allocation computes the address arithmetically as start + k, a single access. Indexed allocation reads the index block once and then goes straight to the entry for k. The trade is worth stating both ways: linked allocation is the only one of the three with no external fragmentation and free growth, since the next block can be anywhere, and it pays for that with the loss of direct access and with the fragility that one corrupted pointer orphans the whole tail of the file.
Internal fragmentation is characteristic of paging, while external fragmentation is characteristic of segmentation. The reason is:
1. Pages are smaller than segments
2. Paging allocates fixed-size units, so waste falls inside the last unit; segments vary in size, so waste falls between them
3. Segmentation does not use a page table
4. Paging requires compaction and segmentation does not
Show answer
Answer: B — Paging allocates fixed-size units, so waste falls inside the last unit; segments vary in size, so waste falls between them
The cause is the allocation unit, not the size. Because every frame is the same size, any free frame satisfies any request exactly, so no unusable gap can form between allocations — but a process rarely fills a whole number of pages, so its last page is partly empty: internal fragmentation, averaging half a page per process. Segments are sized to logical units, so nothing is wasted inside one, but freeing segments of differing sizes leaves holes too small for the next request: external fragmentation. Option A gets the direction of causation wrong; making pages large increases internal fragmentation rather than converting it. Option C is beside the point and also loose — segmentation uses a segment table, and paged segmentation uses both. Option D inverts the remedy: external fragmentation is what compaction addresses, so it belongs to segmentation.
Raising the TLB hit ratio from 80% to 90% in the system above (TLB 20 ns, memory 100 ns, TLB consulted first) changes the effective access time from 140 ns to:
1. 120 ns
2. 130 ns
3. 126 ns
4. 100 ns
Show answer
Answer: B — 130 ns
130 ns. The hit cost is 120 ns and the miss cost 220 ns, so 0.9(120) + 0.1(220) = 108 + 22 = 130. The structure is worth reading off rather than recomputing: the two costs differ by exactly one memory access, 100 ns, so every 10 points of hit ratio is worth 10 ns — which both gives the answer instantly and provides a check on any EMAT question with these parameters. Option A is the hit cost itself, which is the limit as the ratio approaches 100% but is not reached at 90%. Option D forgets the TLB access is charged even on a hit, which would only be right under the overlapped-lookup convention this question does not use. Option C would follow from an arithmetic slip in the weighting rather than any different reading.