Memory Management Practice Questions

This problem analyzes page faults using the First-In, First-Out (FIFO) replacement policy. We can break down the process into two phases.

System Parameters:

• Page Frames: 4
• Page Replacement Policy: FIFO
• Initial State: No pages loaded.

Phase 1: First access to 100 distinct pages
Let the sequence of distinct pages be $p_1, p_2, ..., p_{100}$.

1. The first 4 accesses ($p_1, p_2, p_3, p_4$) will each cause a page fault because the frames are initially empty. The frames will contain $[p_1, p_2, p_3, p_4]$.
2. For every subsequent access to a new, distinct page ($p_5$ to $p_{100}$), the page will not be in memory, causing a page fault.
3. Since all 100 pages are distinct, every access in this phase results in a page fault.
   After this phase, the 4 frames will hold the last 4 pages accessed: $[p_{97}, p_{98}, p_{99}, p_{100}]$.
   Page Faults in Phase 1 = 100

Phase 2: Accessing the same 100 pages in reverse order
The access sequence is now $p_{100}, p_{99}, p_{98}, p_{97}, p_{96}, ..., p_1$.

1. Access $p_{100}$: This is a hit, as $p_{100}$ is in memory. Faults = 0.
2. Access $p_{99}$: This is a hit, as $p_{99}$ is in memory. Faults = 0.
3. Access $p_{98}$: This is a hit, as $p_{98}$ is in memory. Faults = 0.
4. Access $p_{97}$: This is a hit, as $p_{97}$ is in memory. Faults = 0.
5. Access $p_{96}$: This is a fault. The page $p_{96}$ is not in memory. According to FIFO, the oldest page ($p_{97}$) is replaced. The frames become $[p_{98}, p_{99}, p_{100}, p_{96}]$.
6. This pattern continues for the remaining 95 accesses (from $p_{95}$ down to $p_1$). Each access will cause a fault because the required page will have been replaced long ago.

Number of faults in this phase corresponds to the accesses from $p_{96}$ to $p_1$, which is 96 pages.
Page Faults in Phase 2 = 96

Total Page Faults
Total Faults = Faults (Phase 1) + Faults (Phase 2) = $100 + 96 = 196$.

Belady's anomaly describes the phenomenon where increasing the number of available page frames can lead to an increase in the number of page faults.

1. Belady's Anomaly Definition: This anomaly occurs when a page replacement algorithm produces more page faults for a reference string when allocated more memory frames.
2. FIFO (First-In, First-Out): This policy evicts the page that has been in memory for the longest time, regardless of how often it's being used.
3. FIFO and Anomaly: FIFO's decision to replace pages is based solely on their arrival time, not on their usage frequency or future access. This "memory-less" property can cause it to evict frequently used pages, leading to an increase in page faults with more frames.
4. Other Policies: Optimal and LRU (Least Recently Used) are stack algorithms, meaning they possess the inclusion property (the set of pages in memory with $m$ frames is always a subset of pages in memory with $m+1$ frames). Stack algorithms, including LRU and Optimal, provably do not suffer from Belady's anomaly. MRU (Most Recently Used) is not a stack algorithm but often behaves similarly to FIFO in exhibiting the anomaly.

Therefore, FIFO is the classic example where Belady's anomaly can occur.

A page fault is a trap raised by the hardware when a running program attempts to access a virtual memory address that is not currently mapped to physical RAM ($RAM$).
Since the required data is not in the physical memory, the CPU cannot complete the memory access operation.
The operating system handles this fault by fetching the missing page from secondary storage (disk) and loading it into the $RAM$.
This mechanism is essential for implementing virtual memory, allowing processes to operate as if they have more memory than is physically available.
Thus, a page fault specifically occurs when a program tries to access a page that is not currently in memory.

A single-level page table for a large virtual address space (e.g., 32-bit or 64-bit) would be prohibitively large, requiring entries for every possible virtual page, even if unused. Multilevel page tables solve this by organizing the page table hierarchically. Unused portions of the virtual address space do not require their corresponding lower-level page tables to be allocated in physical memory. This "paging the page table" approach significantly reduces the total physical memory consumed by the page table itself, especially for sparsely populated address spaces.

A page table's purpose is to map virtual pages to physical memory frames. When a virtual address is presented, its virtual page number (VPN) is used as an index into the page table. Each entry in the page table, corresponding to a specific VPN, must contain the physical page frame number (PFN) where that virtual page is stored in main memory. The VPN itself is implicitly given by the entry's position (index) in the table, making the PFN the crucial information for address translation. While other information like access rights can be included, the PFN is fundamental.

The Optimal page replacement algorithm functions by replacing the page that will not be used for the longest duration in the future. Because it utilizes perfect knowledge of future memory references, it inherently makes the mathematically ideal choice at every step, thereby minimizing the total number of page faults for any given reference string. In contrast, algorithms like First-In-First-Out (FIFO), Least Recently Used (LRU), and the Second Chance algorithm rely only on historical data or heuristics to estimate future needs. Since these heuristics cannot perfectly predict the future, the Optimal algorithm is theoretically proven to yield the lowest possible page fault rate.

The Dirty bit tracks if a memory page has been modified, signaling a write-back to secondary storage if the page is evicted ($I-b$). The R/W bit defines access permissions (read/write), serving as a mechanism for page protection ($II-c$). The Reference bit records whether a page has been accessed, facilitating decision-making for page replacement policies like LRU ($III-d$). The Valid bit indicates whether the page is currently residing in physical memory, which is essential for checking page initialization or status upon access ($IV-a$). Matching these definitions results in the sequence $I-b, II-c, III-d, IV-a$.

Overlaying is a memory management technique used to execute programs that exceed the size of the available physical memory. By partitioning a program into distinct segments, only the necessary portions are loaded into memory at any given time. While this allows large programs to run on limited hardware, it requires the programmer to explicitly manage the swapping of these segments, which increases development complexity and effort. Consequently, it is not transparent to the user and is an outdated manual alternative to modern virtual memory.

A logical address is composed of a page number and a page offset.
The number of pages is $8 = 2^3$, which requires 3 bits to address.
The page size is $1024 = 2^{10}$ words, which requires 10 bits for the offset.
The total number of bits in the logical address is the sum of these parts: $3 + 10 = 13$ bits.
Alternatively, the total logical address space is $2^3 \times 2^{10} = 2^{13}$ words, necessitating 13 bits.

Dynamic Address Translation (DAT) is the process of mapping a virtual address to a physical address at runtime. In a paging system, memory is fragmented into non-contiguous frames, requiring every logical $V_{address}$ to be converted into a physical $P_{address}$ during execution. This translation is performed by dedicated hardware, typically the Memory Management Unit (MMU), which utilizes page tables to resolve addresses in real-time. Because this high-speed hardware mechanism allows the system to treat non-contiguous physical memory as a continuous logical address space, it is the fundamental hardware requirement necessary to implement paging.

Thrashing occurs when an operating system spends more time swapping pages in and out of $RAM$ than executing instructions. Page replacement algorithms are responsible for deciding which pages to evict; if these algorithms make poor choices, they may frequently evict pages that are needed immediately after, resulting in excessive page faults. This inefficient management forces the $CPU$ to spend most of its time performing $I/O$ operations rather than executing processes. Consequently, since the effectiveness of memory management directly dictates the page fault rate, suboptimal paging algorithms are a primary cause of thrashing.

Page numbers are calculated as $\lfloor \text{Address} / 16 \rfloor$, yielding the sequence: $0, 0, 0, 1, 1, 2, 2, 0, 4, 4, 5, 5, 1, 2, 5, 5$.
Using the LRU policy with 4 frames:

1. Access $0, 1, 2$ causes 3 faults: Memory = $\{0, 1, 2\}$.
2. Access $0$ is a hit; $4$ causes a fault: Memory = $\{0, 1, 2, 4\}$.
3. Access $5$ causes a fault (evicting $1$, LRU): Memory = $\{0, 2, 4, 5\}$.
4. Access $1$ causes a fault (evicting $2$, LRU): Memory = $\{0, 4, 5, 1\}$.
5. Access $2$ causes a fault (evicting $0$, LRU): Memory = $\{4, 5, 1, 2\}$.
6. Final accesses $5, 5$ are hits.
   Total page faults $= 7$. Final pages in memory $= \{1, 2, 4, 5\}$.

The physical address is 36 bits, and the page frame size is 4 KB ($2^{12}$ bytes). A page table entry (PTE) points to the start of the next page table or page frame.

1. Third-level PTEs point to 4 KB page frames. Addressing a 4 KB aligned address requires $36 - 12 = 24$ bits.
2. Second-level PTEs point to third-level page tables. Each third-level table has $2^9$ entries of 4 bytes, totaling $2^9 \times 4 = 2$ KB ($2^{11}$ bytes). Addressing a 2 KB aligned address requires $36 - 11 = 25$ bits.
3. First-level PTEs point to second-level page tables. Each second-level table also has $2^9$ entries, totaling $2^{11}$ bytes, requiring $36 - 11 = 25$ bits to address the 2 KB aligned base.

Thus, the required bits for the first, second, and third levels are 25, 25, and 24.

The effective access time ($EAT$) is calculated by considering the time taken for both TLB hits and TLB misses. Given a TLB access time $t_{TLB} = 10$ ns, memory access time $t_{MEM} = 50$ ns, and hit ratio $h = 0.9$:

1. TLB hit time: $T_{hit} = t_{TLB} + t_{MEM} = 10 + 50 = 60$ ns.
2. TLB miss time: $T_{miss} = t_{TLB} + 2 \times t_{MEM} = 10 + 100 = 110$ ns.
3. The formula for $EAT$ is: $EAT = h \times T_{hit} + (1 - h) \times T_{miss}$.
4. Substituting the values: $EAT = 0.9 \times 60 + 0.1 \times 110 = 54 + 11 = 65$ ns.

When a page fault occurs at address $x$, the memory loads the range $[x, x+99]$. We trace the address sequence as follows:

1. $\text{0100}$: Fault (load $[100, 199]$)
2. $\text{0200}$: Fault (load $[200, 299]$)
3. $\text{0430}$: Fault (load $[430, 529]$)
4. $\text{0499}, \text{0510}$: Hits (both in $[430, 529]$)
5. $\text{0530}$: Fault (load $[530, 629]$)
6. $\text{0560}$: Hit (in $[530, 629]$)
7. $\text{0120}$: Fault (load $[120, 219]$)
8. $\text{0220}$: Fault (load $[220, 319]$)
9. $\text{0240}, \text{0260}$: Hits (both in $[220, 319]$)
10. $\text{0320}$: Fault (load $[320, 419]$)
11. $\text{0410}$: Hit ($320 \leq 410 \leq 419$, so it is in $[320, 419]$)

Counting the faults: $1 (100) + 1 (200) + 1 (430) + 1 (530) + 1 (120) + 1 (220) + 1 (320) = 7$ faults.

The optimal page replacement policy replaces the page that will not be used for the longest period of time in the future.

Given frames: $3$. Reference string: $1, 2, 1, 3, 7, 4, 5, 6, 3, 1$.

1. $1$: Fault. Frames: $[1, \_, \_]$. Faults: $1$.
2. $2$: Fault. Frames: $[1, 2, \_]$. Faults: $2$.
3. $1$: Hit. Frames: $[1, 2, \_]$. Faults: $2$.
4. $3$: Fault. Frames: $[1, 2, 3]$. Faults: $3$.
5. $7$: Fault. Pages $1, 2, 3$ are in frames. $1$ is used at index $9$, $2$ is never used again, $3$ is used at index $8$. Replace $2$. Frames: $[1, 7, 3]$. Faults: $4$.
6. $4$: Fault. Pages $1, 7, 3$ are in frames. $1$ is used at index $9$, $7$ is never used again, $3$ is used at index $8$. Replace $7$. Frames: $[1, 4, 3]$. Faults: $5$.
7. $5$: Fault. Pages $1, 4, 3$ are in frames. $1$ is used at index $9$, $4$ is never used again, $3$ is used at index $8$. Replace $4$. Frames: $[1, 5, 3]$. Faults: $6$.
8. $6$: Fault. Pages $1, 5, 3$ are in frames. $1$ is used at index $9$, $5$ is never used again, $3$ is used at index $8$. Replace $5$. Frames: $[1, 6, 3]$. Faults: $7$.
9. $3$: Hit. Frames: $[1, 6, 3]$. Faults: $7$.
10. $1$: Hit. Frames: $[1, 6, 3]$. Faults: $7$.

Total page faults = $7$.

The final answer is $\boxed{A}$

To calculate the difference in page faults between LRU and Optimal policies:

1. Least Recently Used (LRU) Page Faults:
   | Reference | Frame 1 | Frame 2 | Frame 3 | Faults | LRU to replace (if full) |
   | :-------- | :------ | :------ | :------ | :------- | :----------------------- |
   | 1 | 1 | | | F (1) | - |
   | 2 | 1 | 2 | | F (2) | - |
   | 1 | 1 | 2 | | H | - |
   | 3 | 1 | 2 | 3 | F (3) | - |
   | 7 | 1 | 3 | 7 | F (4) | 2 |
   | 4 | 3 | 7 | 4 | F (5) | 1 |
   | 5 | 7 | 4 | 5 | F (6) | 3 |
   | 6 | 4 | 5 | 6 | F (7) | 7 |
   | 3 | 5 | 6 | 3 | F (8) | 4 |
   | 1 | 6 | 3 | 1 | F (9) | 5 |
   Total LRU faults: 9

2. Optimal Page Faults:
   | Reference | Frame 1 | Frame 2 | Frame 3 | Faults | Optimal to replace (future) |
   | :-------- | :------ | :------ | :------ | :------- | :-------------------------- |
   | 1 | 1 | | | F (1) | - |
   | 2 | 1 | 2 | | F (2) | - |
   | 1 | 1 | 2 | | H | - |
   | 3 | 1 | 2 | 3 | F (3) | - |
   | 7 | 1 | 3 | 7 | F (4) | 2 (not used again) |
   | 4 | 1 | 3 | 4 | F (5) | 7 (not used again) |
   | 5 | 1 | 3 | 5 | F (6) | 4 (not used again) |
   | 6 | 1 | 3 | 6 | F (7) | 5 (not used again) |
   | 3 | 1 | 3 | 6 | H | - |
   | 1 | 1 | 3 | 6 | H | - |
   Total Optimal faults: 7

3. Difference:
   $\text{Difference} = \text{LRU Faults} - \text{Optimal Faults} = 9 - 7 = 2$

The number of more page faults with LRU than Optimal is 2.

The final answer is $\boxed{C}$

Statement P: "Increasing the number of page frames allocated to a process sometimes increases the page fault rate."
This phenomenon is known as Belady's Anomaly, which is a known issue with the First-In, First-Out (FIFO) page replacement algorithm. For certain page reference strings, increasing the number of allocated frames can indeed lead to an increase in page faults. Since the problem specifies FIFO, P is true.

Statement Q: "Some programs do not exhibit locality of reference."
Locality of reference (temporal and spatial) is a characteristic observed in most programs, allowing caching and virtual memory to be effective. However, it's not universally true for all programs. Programs with highly random memory access patterns across a large address space would not exhibit good locality. Therefore, Q is true.

Relationship between P and Q:
Belady's Anomaly (P) is a property of the FIFO algorithm itself, independent of whether a program exhibits locality of reference. While poor locality can lead to high page fault rates, it is not the cause of Belady's Anomaly. The anomaly occurs because FIFO blindly removes the oldest page, which might still be actively used, leading to more faults when more frames are available for specific reference patterns.

Thus, both P and Q are true, but Q is not the reason for P.