Memory Management Practice Questions

The problem asks for the page fault rate, which can be derived from the formula for Effective Memory Access Time (EAT).

Let's define the given variables:

• $p$ = Page fault rate (the value we want to find).
• $M$ = Memory access time when the page is in memory (a 'hit').
• $D$ = Memory access time when a page fault occurs (a 'miss'). This includes the time to handle the fault and access the page.
• $X$ = Experimentally measured average memory access time (EAT).

The effective access time (X) is a weighted average of the access times for hits and misses:
$X = (\text{Probability of a hit}) \times (\text{Time for a hit}) + (\text{Probability of a miss}) \times (\text{Time for a miss})$

The probability of a hit is $(1-p)$, and the probability of a miss (a page fault) is $p$. Substituting the variables:
$X = (1 - p) \cdot M + p \cdot D$

Our goal is to solve this equation for $p$. Let's rearrange the terms:
$X = M - pM + pD$
$X - M = pD - pM$
$X - M = p(D - M)$

Finally, isolate $p$ by dividing both sides by $(D - M)$:
$p = \frac{X - M}{D - M}$

This expression correctly represents the page fault rate.

Initial state: $J1(200K), J2(350K), J3(300K)$ are allocated, leaving a $150K$ free hole. When $J1$ finishes, holes are $200K$ and $150K$.
First Fit: $J4(120K)$ takes the $200K$ hole (leaving $80K$), $J5(150K)$ takes the $150K$ hole, and $J6(80K)$ fits into the remaining $80K$ hole. All jobs succeed.
Best Fit: $J4(120K)$ takes the $150K$ hole (leaving $30K$), and $J5(150K)$ takes the $200K$ hole (leaving $50K$).
Under Best Fit, $J6(80K)$ fails because the largest available hole is $50K$.
Since First Fit accommodates all jobs and Best Fit fails to allocate $J6$, First Fit performs better.

The described process, known as memory compaction, involves coalescing scattered free memory fragments into a single contiguous block to minimize external fragmentation. While "defragmentation" is a common term, this action is a fundamental feature of many Garbage Collection algorithms, which re-organize the heap to ensure allocated space is adjacent, thereby maximizing available contiguous memory. Other options like "Collision" and "Concatenation" are unrelated to this OS memory management technique, and "Dynamic Memory Allocation" refers to the initial acquisition of memory rather than its subsequent cleanup or consolidation.

To determine the total page faults using the optimal replacement algorithm with $3$ frames for the reference string $\{0, 9, 0, 1, 8, 1, 8, 7, 8, 7, 1, 2, 8, 2, 7, 8, 2, 3, 8, 3\}$:

1. Initial accesses $\{0, 9, 1\}$ incur $3$ page faults, resulting in frames $\{0, 9, 1\}$.
2. Access $\{8\}$: Replaces $9$ (never used again), resulting in frames $\{0, 8, 1\}$ (Fault $4$).
3. Access $\{7\}$: Replaces $0$ (never used again), resulting in frames $\{7, 8, 1\}$ (Fault $5$).
4. Access $\{2\}$: Replaces $1$ (never used again), resulting in frames $\{7, 8, 2\}$ (Fault $6$).
5. Access $\{3\}$: Replaces $7$ (never used again), resulting in frames $\{3, 8, 2\}$ (Fault $7$).
6. Remaining references $\{8, 3\}$ result in hits, totaling $7$ page faults.

S1: Random page replacement algorithm can suffer from Belady's anomaly. The random choice of a page to evict does not guarantee that an optimal or near-optimal choice is made. It is possible to construct a reference string where, with more frames, a series of "unlucky" random choices leads to more page faults than with fewer frames. Therefore, S1 is true.

S2: LRU (Least Recently Used) page replacement algorithm is a stack algorithm. A key property of stack algorithms is that the set of pages in memory with $k$ frames is always a subset of the set of pages in memory with $k+1$ frames. This property ensures that increasing the number of frames will never increase the number of page faults. Thus, LRU does not suffer from Belady's anomaly. Therefore, S2 is false.

Given the virtual address space is $40$ bits and the page size is $16$ KB ($2^{14}$ bytes), the page offset requires $14$ bits.
The number of virtual pages is $2^{40-14} = 2^{26}$.
Since each page table entry is $48$ bits, which equals $6$ bytes, the total page table size is $2^{26} \times 6$ bytes.
Converting this to megabytes ($2^{20}$ bytes), the size is $\frac{2^{26} \times 6}{2^{20}}$ MB.
This calculation results in $2^6 \times 6 = 64 \times 6 = 384$ MB.

[CORRECT_OPTION: 384]

The solution demonstrates the concept by analyzing a smaller, analogous problem: a sequence of (1, 2, 3, 4, 1, 2, 3, 4) with 2 page frames.

For this smaller example:

• LIFO (Last-In-First-Out): Results in 7 page faults.
• Optimal: Results in 6 page faults.

The difference is $7 - 6 = 1$.

This pattern holds for the original problem. For the first 20 distinct pages, both algorithms will have 20 faults. The difference in performance occurs during the second pass of the sequence. Generalizing from the smaller example, the difference in the number of page faults between the LIFO and Optimal policies is 1.

Initial memory state is $\{1, 2\}$ with $1$ being the LRU page.

1. References $1$ and $2$: Hits (memory remains $\{1, 2\}$ with $2$ as MRU).
2. Reference $4$: Fault (memory becomes $\{1, 2, 4\}$, fault 1).
3. Reference $5$: Fault (replace $1$ (LRU), memory $\{2, 4, 5\}$, fault 2).
4. Reference $2$: Hit (memory $\{4, 5, 2\}$, $2$ is MRU).
5. Reference $1$: Fault (replace $4$ (LRU), memory $\{5, 2, 1\}$, fault 3).
6. Reference $2$: Hit (memory $\{5, 1, 2\}$, $2$ is MRU).
7. Reference $4$: Fault (replace $5$ (LRU), memory $\{1, 2, 4\}$, fault 4).
   Total page faults = 4.

The phenomenon where increasing the number of allocated memory frames leads to an increase in the page fault rate is known as Belady's Anomaly. Among the standard page replacement algorithms, only the First-In, First-Out (FIFO) algorithm is susceptible to this issue. Other algorithms like LRU and OPT do not suffer from Belady's Anomaly, as their performance generally improves or stays the same with more frames.

To calculate the required address bus width, we first determine the total memory capacity in bytes:
$4 \text{ GB} = 4 \times 2^{30} \text{ bytes} = 2^2 \times 2^{30} \text{ bytes} = 2^{32} \text{ bytes}$.
Given the memory is word-addressable with a word size of 2 bytes, the total number of addressable words is:
$\text{Number of words} = \frac{\text{Total bytes}}{\text{Bytes per word}} = \frac{2^{32}}{2^1} = 2^{31} \text{ words}$.
To address $2^{31}$ unique word locations, the number of address bits $N$ must satisfy $2^N = 2^{31}$, which results in $N = 31$.

[CORRECT_OPTION: N/A]

The effective access time ($EAT$) is calculated using the formula $EAT = (1 - p) \times T_{mem} + p \times S$, where $p$ is the page fault rate, $T_{mem}$ is the memory access time, and $S$ is the page fault service time. Given $T_{mem} = 20 \text{ ns}$, $p = 10^{-6}$, and $S = 10 \text{ ms} = 10^7 \text{ ns}$, we substitute these values into the equation:
$EAT = (1 - 10^{-6}) \times 20 + 10^{-6} \times 10^7$
$EAT = 0.999999 \times 20 + 10 = 19.99998 + 10 = 29.99998 \text{ ns}$
Rounding the result, we obtain approximately $29.9 \text{ ns}$.

Given a $32$-bit virtual address and a $4\text{ KB}$ ($2^{12}$ bytes) page size, the page offset requires $12$ bits.
The number of virtual page number (VPN) bits is $32 - 12 = 20$ bits.
With $128$ total entries and $4$-way associativity, the number of sets is $128 / 4 = 32$.
The number of index bits required to select one of the $32$ sets is $\log_2(32) = 5$ bits.
The minimum size of the TLB tag is calculated by subtracting the index bits from the VPN bits: $20 - 5 = 15$ bits.

To find the virtual address length, we first determine the number of entries in the page table.

1. Size of a Page Table Entry (PTE):
   The physical address is 32 bits. The page size is 8 KB ($2^{13}$ B), so the page offset requires 13 bits.
   The number of bits for the frame number (translation) is $32 - 13 = 19$ bits.
   Total PTE size = 1 (valid) + 1 (dirty) + 3 (permission) + 19 (translation) = 24 bits.
2. Number of Page Table Entries:
   Max page table size is 24 MB.
   Number of entries = $\frac{24 \text{ MB}}{24 \text{ bits}} = \frac{24 \times 2^{20} \times 8 \text{ bits}}{24 \text{ bits}} = 2^{23}$ entries.
3. Virtual Address Space:
   The total virtual address space is (Number of entries) $\times$ (Page size) = $2^{23} \times 8 \text{ KB} = 2^{23} \times 2^{13} \text{ B} = 2^{36}$ B.
   Therefore, the length of the virtual address is 36 bits.

The best-fit memory allocation algorithm places a process in the smallest available partition that is large enough to hold it. The allocation proceeds as follows:

1. Process of 357 KB is allocated to the 400 KB partition. Remaining partitions: {200, 600, 500, 300, 250}.
2. Process of 210 KB is allocated to the 250 KB partition. Remaining partitions: {200, 600, 500, 300}.
3. Process of 468 KB is allocated to the 500 KB partition. Remaining partitions: {200, 600, 300}.
4. Process of 491 KB is allocated to the 600 KB partition. Remaining partitions: {200, 300}.
   The partitions of 200 KB and 300 KB are not allotted to any process.

Computer memory management uses Virtual Memory to extend address space by swapping data between RAM and secondary storage. A page fault occurs when a process attempts to access data not currently in physical RAM, requiring a slow retrieval from the disk. Increasing total RAM allows the operating system to keep a larger working set of data pages in memory simultaneously. By reducing the reliance on disk swapping, the frequency of page faults drops significantly. Because RAM access time $\ll$ disk access time, minimizing these faults leads to superior system performance.

A logical address in a segmented memory system consists of two parts: the segment number and the segment offset.
Given 32 segments, the number of bits required to identify the segment is $\log_2(32) = 5$ bits.
Each segment has a size of 1k bytes, which is $2^{10}$ bytes, so the offset requires $\log_2(2^{10}) = 10$ bits.
The total length of the logical address is the sum of the bits for the segment number and the segment offset: $5 + 10 = 15$ bits.

The 40-bit virtual address is partitioned into a tag, a set index, and a page offset.
The page size is 8 KB = $2^{13}$ bytes, so the page offset (word offset) requires 13 bits.
The TLB has 32 sets, so the set index requires $\log_2(32) = 5$ bits.
The length of the TLB tag is the remaining portion of the virtual address.
Tag length = Total virtual address bits - Set index bits - Page offset bits
Tag length = $40 - 5 - 13 = 22$ bits.

A dirty bit (or modify bit) is a flag in a page table entry that indicates whether a page in main memory has been modified since it was loaded. When the operating system needs to evict a page to free memory, it checks this bit to determine if the page is "dirty." If the bit is $0$ (clean), the page matches the version on the disk, allowing the OS to discard it without performing an unnecessary write operation. If the bit is $1$, the page has been modified and must be written back to the paging device before the frame is reclaimed. This mechanism optimizes system performance by minimizing unnecessary I/O transfers.