Memory Management Practice Questions

To determine the completion time of $J7$, we track the memory blocks and request queue over time. Initial free blocks are $\{2k, 4k, 8k, 20k\}$.

1. At $t=0$: Requests $J1$ to $J4$ are allocated using best-fit:
   • $J1(2k)$ on $2k$ (finishes $t=4$)
   • $J2(14k)$ on $20k$ (finishes $t=10$, rem: $6k$)
   • $J3(3k)$ on $4k$ (finishes $t=2$, rem: $1k$)
   • $J4(6k)$ on $8k$ (finishes $t=8$, rem: $2k$)
2. $t=2$ to $8$: $J5(6k, 4)$ waits as no block $\ge 6k$ is free. At $t=8$, $J4$ completes, freeing $8k$. $J5$ is allocated to $8k$ and finishes at $t=8+4=12$.
3. At $t=10$: $J2$ completes, freeing the $20k$ block. $J6(10k, 1)$ is next in the queue, allocated to $20k$, and finishes at $t=10+1=11$.
4. At $t=11$: $J6$ completes, leaving $10k$ free ($20k - 10k$). $J7(7k, 8)$ is the next request. It is allocated to the $10k$ block (best-fit).
5. Completion: $J7$ starts at $t=11$ and runs for $8$ units.
   $11 + 8 = 19$

Virtual memory is a memory management technique that provides an abstraction of physical memory, creating an illusion of a much larger address space than is physically available. By utilizing demand paging, the operating system loads only the active portions of a program into Main Memory while keeping the remainder on secondary storage. This mechanism decouples the logical address space from physical memory constraints. Consequently, the system can execute programs that exceed the total capacity of the installed physical RAM. This directly enables the capability described in option B.

The minimum number of page frames required by a process must ensure that any single instruction can complete its execution without deadlock or infinite page fault cycles. If an instruction spans page boundaries or utilizes indirect addressing referencing distinct pages, those pages must simultaneously reside in memory to execute that instruction. Because the Instruction Set Architecture ($ISA$) defines the maximum instruction length, addressing modes, and the specific memory access patterns, it inherently determines the worst-case scenario for page residency. Therefore, the $ISA$ sets the absolute constraint for the minimum frame allocation necessary for a process to execute.

In the working-set strategy, the operating system monitors the total demand for memory by calculating $D = \sum WSS_i$, where $WSS_i$ is the working-set size of process $i$. Thrashing occurs when $D$ exceeds the total available physical frames. To maintain stability, if $D$ is significantly less than the total available frames, the system has surplus memory, allowing the OS to increase the degree of multiprogramming by initiating a new process (Statement I). Conversely, if $D$ exceeds the total available frames, the system is overcommitted, requiring the OS to select a process to suspend to free frames and prevent thrashing (Statement II). Thus, both actions are utilized by the operating system.

Virtual memory provides essential process isolation and memory protection, ensuring programs operate within their own independent address spaces. Without virtual memory, processes must access physical addresses directly, which creates critical conflicts where one process could easily overwrite the memory or data of another. Efficient multi-user support requires the operating system to dynamically assign memory while ensuring strict protection boundaries between different users. Since the hardware can no longer map separate virtual address spaces to protected physical memory regions, implementing secure and simultaneous multi-user execution becomes effectively impossible. Thus, the inability to isolate processes directly leads to the failure of efficient multi-user support.

To calculate the memory overheads:

1. Segmentation ($S$): The overhead is the total number of segments multiplied by the segment table entry size:
   $S = (4 + 5 + 3 + 8) \times 8 \text{ bytes} = 20 \times 8 = 160 \text{ bytes}.$

2. Two-level Paging ($P$): With a page size of 1 KB, the total number of pages required is $858$. For two-level paging, the overhead is the outer page table plus the inner page tables:
   $\text{Outer table} = \lceil 858 / 256 \rceil \times 4 \text{ bytes} = 4 \times 4 = 16 \text{ bytes}.$
   $\text{Inner tables} = 858 \times 4 = 3432 \text{ bytes}.$
   $P = 16 + 3432 = 3448 \text{ bytes}.$

3. Segmentation and Paging ($T$): The overhead includes the segment table size plus the page tables for each segment (totaling all pages):
   $T = (\text{Segment table}) + (\text{Total page table entries}) \times 4 \text{ bytes}.$
   $T = 160 + (858 \times 4) = 160 + 3432 = 3592 \text{ bytes}.$

Comparing the calculated values $S = 160$, $P = 3448$, and $T = 3592$, we find $S < P < T$.

To calculate the effective average instruction execution time, we first determine the Effective Memory Access Time ($EAT$). For a 2-level paging system, a TLB miss typically incurs two additional memory accesses to resolve the page tables (assuming the data access is included in the instruction's $2$ memory accesses). Thus, $EAT$ is:
$EAT = h \times t_{mem} + (1-h) \times (2 \times t_{mem}) = 0.9(150\text{ ns}) + 0.1(300\text{ ns}) = 135 + 30 = 165\text{ ns}$
Next, we calculate the contribution of page faults to the execution time. Given a page fault rate $p = 10^{-4}$ and service time $t_{pf} = 8\text{ ms} = 8,000,000\text{ ns}$:
$T_{pf\_penalty} = p \times t_{pf} = 10^{-4} \times 8,000,000\text{ ns} = 800\text{ ns}$
The total instruction execution time is the sum of CPU time, memory access time, and page fault penalty:
$T_{total} = t_{cpu} + (n_{mem} \times EAT) + T_{pf\_penalty} = 100\text{ ns} + (2 \times 165\text{ ns}) + 800\text{ ns} = 100 + 330 + 800 = 1230\text{ ns}$

To determine the bits available for protection and other information, we first identify the physical page number (PPN) field size within the page table entry (PTE). Given the physical address space is 30 bits and the page size is $4\text{ KB} = 2^{12}\text{ bytes}$, the offset requires $\log_2(2^{12}) = 12$ bits. Consequently, the PPN requires $30 - 12 = 18$ bits. Since the total size of each PTE is 32 bits, the number of bits remaining for protection and other information is:
$\text{Available Bits} = \text{Total PTE Size} - \text{PPN Size} = 32 - 18 = 14 \text{ bits}.$

Given a 32-bit virtual address space, the total number of bytes is $2^{32}$. With a page size of $1 \text{ KB} = 2^{10} \text{ bytes}$, the number of entries required in a one-level page table is $\frac{2^{32}}{2^{10}} = 2^{22}$. Assuming each page table entry (PTE) is $4 \text{ bytes}$, the total memory required for the page table of a single process is $2^{22} \times 4 \text{ B} = 16 \text{ MB}$. Allocating $16 \text{ MB}$ of contiguous physical memory for each process's page table is impractical and inefficient, leading to excessive memory overhead. This excessive consumption of physical memory for page table storage is the primary constraint.

To find the average access time, we consider the two cases for the translation look-aside buffer (TLB):

1. TLB Hit (96%): The physical address is available immediately. The total time is the TLB access plus the average cache access time:
   $T_{hit} = T_{TLB} + (T_{Cache} + (1 - H_{Cache}) \times M) = 1 + (1 + 0.1 \times 10) = 3 \text{ ns}$
2. TLB Miss (4%): We must perform a 2-level page table walk, requiring two memory accesses ($2 \times M$), followed by the cache access:
   $T_{miss} = T_{TLB} + 2M + (T_{Cache} + (1 - H_{Cache}) \times M) = 1 + 20 + (1 + 0.1 \times 10) = 23 \text{ ns}$
3. Average Time:
   $T_{avg} = 0.96 \times T_{hit} + 0.04 \times T_{miss} = 0.96 \times 3 + 0.04 \times 23 = 2.88 + 0.92 = 3.8 \text{ ns}$

Rounding $3.8 \text{ ns}$ to the nearest $0.5 \text{ ns}$ gives $4 \text{ ns}$.

The first level (L1) page table requires $2^{10} = 1024$ entries, each 4 bytes, totaling $4 \text{ KB}$. The virtual addresses involve three distinct regions: the code pages ($0x00000000$ to $0x00001FFF$) map to L1 index $0$, the data pages ($0x00400000$ to $0x00401FFF$) map to L1 index $1$, and the stack page ($0xFFFFF000$) maps to L1 index $1023$. Since three distinct entries in the L1 page table are used, three second-level (L2) page tables must be allocated in memory. Each L2 page table contains $2^{10} = 1024$ entries, each 4 bytes, amounting to $4 \text{ KB}$ per table. Thus, the total memory required is $4 \text{ KB} (L1) + 3 \times 4 \text{ KB} (L2) = 16 \text{ KB}$.

The optimal page replacement algorithm aims to minimize the total number of page faults by selecting the page $p$ currently in memory that will be referenced farthest in the future. If memory contains the set of pages $S$, the algorithm identifies the page $p \in S$ such that the time $t$ until its next access is maximized. By replacing this page, the algorithm ensures that the memory slot remains free of page faults for the longest possible duration. Unlike LRU or LFU algorithms, which rely on past reference patterns or access frequencies, the optimal strategy requires knowledge of future access sequences. Thus, the algorithm selects the page that will not be used for the longest time in the future.

Virtual memory acts as an abstraction layer, mapping a program's logical address space to physical memory addresses, making option A true. It facilitates the execution of programs larger than the available primary memory through demand paging, validating option B. Because only required portions of a process are loaded into memory, more processes can reside in memory concurrently, thus increasing the degree of multiprogramming, which confirms option C. Conversely, virtual memory does not reduce context switching overhead; instead, it introduces additional overhead, such as updating page tables and flushing Translation Lookaside Buffers (TLBs) during context switches, making option D false.

The virtual address space is $2^{32}$ bytes and the page size is $4\text{ KB}$ ($2^{12}$ bytes), resulting in $\frac{2^{32}}{2^{12}} = 2^{20}$ total virtual pages.
The physical memory is $64\text{ MB}$ ($2^{26}$ bytes), meaning there are $\frac{2^{26}}{2^{12}} = 2^{14}$ physical pages.
Each page table entry (PTE) must address $2^{14}$ physical pages, requiring at least 14 bits to index them.
Using a 2-byte (16-bit) entry size to accommodate the index and necessary status bits, the total page table size is:
$\text{Size} = 2^{20} \text{ entries} \times 2 \text{ bytes/entry} = 2^{21} \text{ bytes} = 2 \text{ MB}$.

The FIFO page replacement algorithm does not satisfy the inclusion property, meaning the set of pages resident in memory with $n$ frames is not necessarily a subset of the pages resident with $n+1$ frames. Because of this, the page fault count is not monotonic with respect to the number of allocated frames. This specific behavior, where increasing available physical memory results in an increased number of page faults for certain reference strings, is known as Belady's Anomaly. Thus, increasing the number of page frames can sometimes increase the number of page faults.

Given $T_{access} = 1 \, \mu s$, $T_{fault} = 10 \, ms = 10,000 \, \mu s$, and hit ratio $p = 0.9999$.
The miss ratio is $1 - p = 0.0001$.
The average memory access time formula is $T_{avg} = p \times T_{access} + (1 - p) \times T_{fault}$.
Substituting the values, we get $T_{avg} = (0.9999 \times 1 \, \mu s) + (0.0001 \times 10,000 \, \mu s)$.
Simplifying gives $T_{avg} = 0.9999 \, \mu s + 1 \, \mu s = 1.9999 \, \mu s$.

A thread is an execution unit scheduled and run by the $CPU$ (3).
The virtual address space is an abstraction used to manage and access physical $Memory$ (2).
A file system provides an organized structure for storing data on a persistent $Disk$ (4).
A signal is an asynchronous notification mechanism, similar to an $Interrupt$ (1), used to communicate with or control processes.
These correspondences yield the mapping (A) - 3, (B) - 2, (C) - 4, (D) - 1.

A multi-user, multi-processing operating system requires hardware support for process isolation and system protection. Address translation (A) is critical to create distinct virtual address spaces, preventing cross-process memory interference and ensuring protection. Dual-mode execution (C) (privileged vs. non-privileged) is necessary to ensure user-space processes cannot execute restricted instructions, modify system registers, or access hardware directly. Conversely, DMA (B) is merely an I/O performance optimization, and demand paging (D) is an optional memory management strategy. Thus, the system fundamentally relies on the hardware-level enforcement of memory isolation and CPU execution mode switching to function correctly.

[CORRECT_OPTION: A, C]

Virtual memory allows programs larger than physical RAM to execute by swapping pages between secondary storage and physical memory, which directly validates option D.
It provides hardware-enforced memory isolation (option B) by ensuring that the translation mechanism prevents a process from accessing memory outside its assigned virtual address space.
Option A is incorrect because virtual memory introduces translation overhead, such as $TLB$ lookups and page table walks, which makes it slower than direct physical memory access.
While relocation (Option C) is supported by virtual memory, the primary architectural advantages defining the system are address space extension and process protection.
Therefore, options B and D are the correct advantages.

[CORRECT_OPTION: B, D]