Q1Computer Architecture

This is a standard problem in virtual memory organization, relating the size of the logical (virtual) address space to the physical memory space, and to the paging structure.

(i) Number of words in the address space: the address space is specified by 24 bits (units), meaning the logical/virtual address can range over 2^24 distinct addresses. Therefore the address space contains:

(ii) Number of words in memory space: the corresponding physical memory space is specified by 16 bits, meaning the physical memory can address 2^16 distinct locations. Therefore the memory space contains:

(iii) Number of pages and blocks: if each page (in the logical address space) or block (in the physical memory space) consists of 2^k words, the number of pages is found by dividing the total address space by the page size, and the number of blocks is found by dividing the total memory space by the block size:

This illustrates the fundamental relationship in paged virtual memory systems: the logical address is split into a page number field (24-k bits, selecting one of 2^(24-k) pages) and a page offset field (k bits, selecting a word within the page), while the physical address is similarly split into a block number field (16-k bits) and the same offset field (k bits), with the page table performing the mapping from page number to block number for each currently resident page. Since the address space (2^24) is much larger than the memory space (2^16), only a small fraction of the total pages can reside in physical memory at any time, with the remainder held on secondary storage until needed — the essential mechanism that gives virtual memory its ability to run programs larger than physical RAM.

Numerical illustration for a specific page size: if k = 10 (i.e., each page/block holds 2^10 = 1024 words, a common realistic page size), then the number of pages would be 2^(24-10) = 2^14 = 16,384 pages in the address space, while the number of physical blocks would be 2^(16-10) = 2^6 = 64 blocks in memory. This concretely shows the huge disparity between logical and physical capacity in this problem — with only 64 physical page frames available to hold pages from a logical space of 16,384 possible pages, the operating system's page-replacement policy (deciding which resident page to evict when a new page must be brought in) becomes critical to overall system performance, since the vast majority of a program's pages must remain on disk at any given time and be swapped in only as referenced.

Common page-replacement policies include First-In-First-Out (FIFO, evicting the oldest resident page), Least Recently Used (LRU, evicting the page whose most recent access is furthest in the past, approximating the ideal but requiring tracking overhead), and Optimal (evicting the page that will not be used for the longest time in the future, which requires future knowledge and so serves only as a theoretical benchmark for comparing practical algorithms), each offering different trade-offs between implementation complexity and how closely they approach optimal performance in minimizing page faults.