IS CS-2019S1-02

题目来源：Problem 2 日期：2024-08-02 题目主题：CS-操作系统-分页机制

解题思路

1. 第一小问要求解释分页机制的基本概念，需要简明扼要地说明每个术语的含义和作用。
2. 第二小问涉及虚拟地址到物理地址的转换，需要理解页表的结构和使用方法。
3. 第三小问分析两段程序代码的页面错误次数，需要考虑程序的访存模式、页面大小和 LRU 替换策略。

Solution

1. Paging Functionality Terms

• Page: A page is a fixed-size contiguous block of virtual memory.
• Page Table: The page table is a data structure used by the operating system to store the mapping between virtual page numbers and physical frame numbers. Each entry in the page table typically contains the frame number and status bits (e.g., valid bit).
• Page Replacement: Page replacement is the process of selecting a page in physical memory to be replaced when a new page needs to be brought in from secondary storage. This occurs when a page fault happens and there is no free frame available in physical memory.
• Page Fault: A page fault is an exception that occurs when a program tries to access a page that is mapped in the virtual address space but not currently present in physical memory. The operating system must load the required page from secondary storage into a free frame in physical memory.
• Translation Look-aside Buffer (TLB): The TLB is a small, fast cache that stores recent translations from virtual page numbers to physical frame numbers. It is used to speed up virtual address translation by avoiding frequent accesses to the page table in main memory.

2. Virtual to Physical Address Translation

Given:

• 32-bit system with 4GB virtual memory
• 32KB physical memory
• 4KB page size
• Virtual address (VA): $2A0F_{16}$

We can convert the address as follows:

1. Determine address structure:

   • 4GB virtual memory in a 32-bit system implies byte addressing.
   • 4KB page size = $2^{12}$ bytes, so page offset is 12 bits.
   • Virtual page number (VPN) is the remaining bits: $32-12=20$ bits.

2. Expand the given VA:

   • $2A0F_{16}$ is only 16 bits long.
   • Pad with zeros to get 32 bits: $00002A0F_{16}$
   • In binary: $0000000000000010101000001111_2$

3. Split the VA:

   • VPN (20 bits): $0000000000000010_2=2_{10}$
   • Page offset (12 bits): $101000001111_2=A0F_{16}$

4. Look up the page table:

   • VPN = 2
   • Corresponding frame number: $110_2$
   • Valid bit: 1 (page is in memory)

5. Construct the physical address:

   • Physical frame number: $110_2$
   • Page offset: $A0F_{16}$
   • Physical address: $110A0F_{16}=6A0F_{16}$

Therefore, the virtual address $2A0F_{16}$ translates to the physical address $6A0F_{16}$.

3. Page Fault Analysis

Given:

• 32-bit system with 32KB physical memory
• 4KB page size
• Page replacement uses LRU policy
• Compiler optimization is disabled

Initial State Analysis

1. Array size and layout:

   • $1024\times 1024\times 4$ bytes = 4MB
   • Number of pages for A = $\frac{4MB}{4KB}$ = $1024$ pages
   • Elements per page: $\frac{4KB}{4bytes}$ = $1024$ elements

2. Analyzing the given page table:

   • The table shows 16 entries (0 to 15)
   • Max valid pages for A: $\frac{32KB}{4KB}-1=7$ pages in total

3. Physical memory layout:

   • 8 frames of 4KB each
   • 1 frame reserved for other data (program code, page table, etc.)
   • 7 frames available for array A

4. Initial loading:

   • Pages for A are not proactively loaded into memory
   • Page allocation for A starts at a page boundary

Calculations

Program Code 1 (Column-major access)

for (j = 0; j < 1024; j++)
  for (i = 0; i < 1024; i++)
    sum += A[i * 1024 + j];

• First access: 1 page fault (loads the first page)
• Subsequent accesses: Since the LRU policy ensures that the required page is always the least recently used, each access to a new element is an access to a new page, causing a page fault.
• Total page faults $=1024\times 1024=1,048,576$

Program Code 2 (Row-major access)

for (i = 0; i < 1024; i++)
  for (j = 0; j < 1024; j++)
    sum += A[i * 1024 + j];

• First 7 rows: 7 page faults (one for each new page loaded)
• Remaining rows: One page fault per row, since every row is in a new page.
• Total page faults $=7+(1024-7)=1,024$

Conclusion

• Program Code 1 (Column-major access) causes $1,048,576$ page faults.
• Program Code 2 (Row-major access) causes $1,024$ page faults.

知识点

操作系统分页虚拟内存地址转换页面替换LRU

重点词汇

• page 页面
• page table 页表
• page replacement 页面替换
• page fault 页面错误
• Translation Look-aside Buffer (TLB) 转换后备缓冲器
• virtual address 虚拟地址
• physical address 物理地址
• frame number 帧号
• valid bit 有效位
• Least Recently Used (LRU) 最近最少使用

参考资料

1. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts (10th ed.). Wiley. Chapter 9: Virtual Memory.
2. Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th ed.). Pearson. Chapter 3: Memory Management.