OS Assignment 5

赖海斌
12211612

1. Question1 [50pts]

In a demand-paging memory management system, suppose the page table contents for a certain process are as follows (for a single-level page table, with H denoting hexadecimal values):

The page size is 4 KB, the access time for main memory is 100 ns, the access time for the TLB is 10 ns, and the average time to handle a page fault, including the time to update the TLB and page table, is 10^8 ns. Assuming:

1. The TLB is initially empty.
2. During address translation, the TLB is accessed first. If there is a miss in the TLB, the page table is accessed subsequently (ignoring the time taken to update the TLB after accessing the page table).
3. A valid bit set to 0 indicates that the page is not present in memory, causing a page fault interrupt. After the page fault interrupt handling is completed, the execution returns to the instruction that triggered the page fault to execute.

Given a virtual address access sequence of 1333H , 0555H , 2555H

(1）Assuming there are enough free pages available in OS. What is the time required to access each of the three virtual addresses mentioned above? Give the calculation process. The answer should include the time cost of the final access to the physical address.

Answer for Q1.1:

Since we have a 4 KB page, that means for the lower 12 bits represent the offset within the page.

(a) 1333H
For 1333H, we have virtual page number 1, and 333 for offset

• The TLB is initially empty, so a TLB miss occurs. Go for page table.
• Look up the page table for page number 1. The page table entry for page 1 has a valid bit of 1 (valid), so the page is in memory and can be mapped to physical frame 122H.

Total Time:

• TLB Miss:  10 ns.
• Page Table Lookup: 100 ns (Look up page table in Main memory)
• Memory Access: 100 ns 

So intotal, 133H needs 210ns

(b) 0555H
We have virtual page number 0, and 555 for offset

• The TLB is initially empty, so a TLB miss occurs. Go for page table.
• In page table, the virtual page number 0 is invalid, causing a page fault. And OS try to handle.
• After OS handles page fault, we access the physical memory address again

Total Time:

• TLB Miss:  10 ns.
• Page Table Lookup: 100 ns (Look up page table in Main memory)
• Page Fault: 10^8 ns
• Access TLB again, miss: 10ns
• Memory Access again : 100 ns 
  So intoatal, 0555H needs 100,000,220 ns.

(c) 2555H
We have virtual page number 2, and 555 for offset

• The TLB is initially empty, so a TLB miss occurs. Go for page table.
• Look up the page table for page number 2. The page table entry for page 2 has a valid bit of 1 (valid), so the page is in memory and can be mapped to physical frame 233H.

Total Time:

• TLB Miss:  10 ns.
• Page Table Lookup: 100 ns (Look up page table in Main memory)
• Memory Access: 100 ns 

So intotal, 2555H needs 210ns

(2）Suppose the operating system permits processes to use only two physical pages with frame numbers 122H and 233H, employing the Least Recently Used (LRU) replacement algorithm. Given the certain access sequence above, what is the physical address for the virtual address 0555H? Please explain the reasoning behind your answer.

Answer for Q1.2

Since we only can use two physical pages in TLB with 122H and 233H.
After we fetech 1333H , we fetch 0555H . A page fault happens, OS will help MMU to rebuild the mapping. At this time, According to LRU replacement, physical pages 122H has just been used. So 233H will be reconnect to virtual page number 0.

Then, the PFN 233H will be connected to 555H, become the final physical address 233555H .

Question 2 [50pts]

Here is a computer with a riscv64 architecture, employing the Sv39 multi-level paging mechanism. The formats for physical and virtual addresses are as follows.

Assuming there are only three free physical pages in memory, with physical page numbers being 0x000_0008_6000 , 0x000_0008_6001 , and 0x000_0008_6002 . When a process requests a physical page, the operating system adopts an allocation strategy of assigning physical page numbers from largest to smallest. At a certain point, the value in the satp register is 0x8000_0000_0008_4000 , with all PTEs in the root page table being zero. The current process attempts to access the valid virtual address 0x0000_0021_2345_6789

Please simulate the computer's handling of the page fault interrupt, allocate the corresponding physical page, correctly fill in the corresponding page table entry, and find the corresponding physical address. Complete the following blanks (in hexadecimal, ignoring the actual setting of flag bits in each level of page table entries, all flags set to 0 is OK).

1. The physical address of the root page table is ______, and the value of the ____ th page table entry is ________.
2. The physical address of second-level page table is _____, and the value of the ____th page table entry is _____\.
3. The physical address of third-level page table is ______, and the value of the ____th page table entry is ______.
4. The physical address corresponding to the virtual address 0x0000_0021_23456789 is _____

Answer

An example help me analysis from 14.3. Page Tables — Introduction to Operating Systems

For Sv39:
From lower bit to higher bit:
the address 0x0000_0021_2345_6789 have:
offset = 0x789
VPN[2] = 0x056
VPN[1] = b'10_0011_010 = 0x11A
VPN[0] = b'010_0001_00 = 0x084

All PTEs in the root page table are zero.

Root page table

For satp value 0x8000_0000_0008_4000,

Figure reference: SV39 多级页表的硬件机制 - rCore-Tutorial-Book-v3 3.6.0-alpha.1 文档

当 MODE 设置为 0 的时候，代表所有访存都被视为物理地址；而设置为 8 的时候，SV39 分页机制被启用，所有 S/U 特权级的访存被视为一个 39 位的虚拟地址，它们需要先经过 MMU 的地址转换流程，如果顺利的话，则会变成一个 56 位的物理地址来访问物理内存；否则则会触发异常，这体现了分页机制的内存保护能力。

So the physical address of the root page table is 0x00_0008_4000.

The VPN[2] = 0x084, so we need to access the PTE at index 0x084 in the root page table. Since all PTEs in the root page table are initially zero, a page fault occurs, and the operating system will allocate a new physical page for the second-level page table.

Physical page allocation: The system allocates physical pages in the largest-to-smallest order. The largest free physical page is 0x000_0008_6002, so the second-level page table will be placed at this address.

For our PTE, we have

 63      54 53      28 27      19 18      10 9   8 7 6 5 4 3 2 1 0
+----------+----------+----------+----------+-----+-+-+-+-+-+-+-+-+
| reserved |  PPN[2]  |  PPN[1]  |  PPN[0]  | RSW |D|A|G|U|X|W|R|V|
+----------+----------+----------+----------+-----+-+-+-+-+-+-+-+-+
     10         26          9          9       2   1 1 1 1 1 1 1 1

The value of the root PTE at index 0x084 is:

PTE = 0x0000_0000_2180_0800

Here, 0x2180_0800 represents the physical address of the second-level page table (0x000_0008_6002).

So the physical address of the root page table is MARKDOWN_HASHc87d52f2199bb22364da98f4d3b3badcMARKDOWNHASH, the value of the _\MARKDOWN_HASH107ca442ee0b4a849f93b3a8b413c0e6MARKDOWNHASH__ th page table entry is __\MARKDOWN_HASH18ebe5c91114f31b121dfa7d5b3580f9MARKDOWNHASH____.

This entry will give us the memory address for the second level page table.

The physical page number of the second-level page table will be 0x000_0008_6002. Since VPN[1] = 0x11A, and the table is newly allocated, a new third-level page table is created. Its physical page number is 0x000_0008_6001 .

The physical address of second-level page table is __MARKDOWN_HASH8727aa770ccbb88cf5a3eb5d793d4d48MARKDOWNHASH \__ , and the value of the \MARKDOWN_HASHfac244a0d359012391a793a2848ba98aMARKDOWNHASH___th page table entry is _\MARKDOWN_HASHe070c8b06083ab8c2db96258ef16e1a9MARKDOWNHASH___\.

For the third page table, The physical address of third-level page table is __MARKDOWN_HASH47928025bb8d89cd7517bfd068b60762MARKDOWNHASH____ , and the value of the _\MARKDOWN_HASH669cf9d68faa95727095c0573c8ecf54MARKDOWNHASH__th page table entry is _\MARKDOWN_HASHd20edeb026a0cbf7f0f153511a4c6a37MARKDOWNHASH___.

So the physical address corresponding to the virtual address 0x0000_0021_2345_6789 is 0x00_0000_8600_0789.