Keywords: virtual address | physical address | page table | memory management | operating system
Abstract: This article explores the mechanism of address translation in a system with 16-bit virtual and physical addresses and 4KB page size. By analyzing page table structure, page offset calculation, and frame mapping, it explains how to convert given virtual addresses (e.g., 0xE12C, 0x3A9D) to corresponding physical addresses. Based on core principles from the best answer and supplemented with examples, it step-by-step demonstrates the conversion process, including binary decomposition, page table lookup, and reference bit setting, providing practical guidance for understanding operating system memory management.
Introduction
In operating system memory management, translating virtual addresses to physical addresses is a core concept that achieves memory abstraction and protection through page table mechanisms. This article is based on a specific case: a system with 16-bit virtual and physical addresses and a 4KB page size, detailing the address translation process. The system has a virtual address space of 2^16 = 65,536 bytes, a physical address space of 65,536 bytes, and a page size of 4,096 bytes (4KB).
Page Size and Offset Calculation
The page size determines the number of bits used for offset in an address. Given a page size of 4,096 bytes, we calculate log2(4096) to determine the offset bits. Since 4096 = 2^12, the offset is 12 bits. This means the lower 12 bits of the virtual address directly map to the corresponding offset in the physical address, as page size is consistent in both virtual and physical address spaces.
Virtual Address Structure Decomposition
In a 16-bit virtual address, the offset occupies 12 bits, leaving 4 bits for the page number. Specifically, the virtual address can be decomposed into: the high 4 bits represent the page number, and the low 12 bits represent the page offset. For example, the virtual address 0xE12C in binary is 1110 0001 0010 1100, where 1110 (decimal 14) is the page number, and 0001 0010 1100 is the offset.
Page Table and Frame Mapping
The page table stores mappings from page numbers to frame numbers. In this system, there are 2^4 = 16 pages, with each page table entry containing a frame number and a reference bit. The reference bit tracks whether a page has been accessed and is periodically zeroed by a thread. Based on the provided page table (as shown in the image), for instance, page number 14 maps to frame number 3.
Address Translation Steps
Translating a virtual address to a physical address involves the following steps: first, convert the virtual address to binary; second, extract the high 4 bits as the page number; then, look up the page table to get the corresponding frame number; finally, combine the frame number with the low 12-bit offset to form the physical address. Taking 0xE12C as an example: binary is 1110 0001 0010 1100, page number 14 maps to frame number 3 (binary 0011), so the physical address is 0011 0001 0010 1100, i.e., 0x312C. Additionally, the reference bit for entry 14 in the page table should be set to 1.
Example Analysis
Here is the translation process for other virtual addresses:
- 0x3A9D: binary 0011 1010 1001 1101, page number 3 maps to frame number 10 (binary 1010), physical address is 1010 1010 1001 1101, i.e., 0xAA9D.
- 0xA9D9: binary 1010 1001 1101 1001, page number 10 maps to frame number 5 (binary 0101), physical address is 0101 1001 1101 1001, i.e., 0x59D9.
- 0x7001: binary 0111 0000 0000 0001, page number 7 maps to frame number 15 (binary 1111), physical address is 1111 0000 0000 0001, i.e., 0xF001.
- 0xACA1: binary 1010 1100 1010 0001, page number 10 maps to frame number 5 (binary 0101), physical address is 0101 1100 1010 0001, i.e., 0x5CA1.
In all translations, the offset part (low 12 bits) remains unchanged, verifying the principle of page size consistency.
Reference Bit Management
During translation, each time a page is accessed, the reference bit in the corresponding page table entry should be set to 1 to indicate the page has been referenced. This aids the operating system in page replacement algorithms (e.g., LRU). For example, after translating 0xE12C, the reference bit for page table entry 14 needs to be updated to 1.
Conclusion
Through this analysis, we have demonstrated the complete process of translating virtual addresses to physical addresses in a 16-bit system with 4KB pages. Key points include: offset calculation based on page size, address decomposition into page number and offset, page table lookup for frame mapping, and reference bit setting. This method is not only applicable to this case but can also be generalized to other memory management scenarios, helping to understand core mechanisms of operating systems.