50.002 Computation Structures Computation Structures

50.002 Computation Structures
Information Systems Technology and Design
Singapore University of Technology and Design

Problem Set 8

This page contains all practice questions that constitutes the topics learned in Week 11: Virtual Memory, Virtual Machine.

Each topic’s questions are grouped into three categories: basic, intermediate, and challenging. You are recommended to do all basic problem set before advancing further.

Virtual Memory Trivia (Basic)

Consider a virtual memory system that uses a single-level page map to translate virtual addresses into physical addresses. Each of the questions below asks you to consider what happens when one of the design parameters of the original system is changed.

  1. If the physical memory size (in bytes) is doubled, how does the number of bits in each entry of the page table change?

    Show Answer

    Increases by 1 bit. Assuming the page size remains the same, there are now twice as many physical pages, so the physical page number needs to expand by 1 bit.


  2. If the physical memory size (in bytes) is doubled, how does the number of entries in the page map change?

    Show Answer

    No change. The number of entries in the page table is determined by the size of the virtual address and the size of a page – it’s not affected by the size of physical memory.


  3. If the virtual memory size (in bytes) is doubled, how does the number of bits in each entry of the page table change?
    Show Answer

    No change. The number of bits in a page table entry is determined by the number of control bits (usually 2: dirty and resident) and the number of physical pages – the size of each entry is not affected by the size of virtual memory.


  4. If the virtual memory size (in bytes) is doubled, how does the number of entries in the page map change?

    Show Answer

    The number of entries doubles. Assuming the page size remains the same, there are now twice as many virtual pages and so there needs to be twice as many entries in the page map.


  5. If the page size (in bytes) is doubled, how does the number of bits in each entry of the page table change?

    Show Answer

    Each entry is one bit smaller. Doubling the page size while maintaining the size of physical memory means there are half as many physical pages as before. So the size of the physical page number field decreases by one bit.


  6. If the page size (in bytes) is doubled, how does the number of entries in the page map change?
    Show Answer

    There are half as many entries. Doubling the page size while maintaining the size of virtual memory means there are half as many virtual pages as before. So the number of page table entries is also cut in half.


  7. The following table shows the first 8 entries in the page map. Recall that the valid bit is 1 if the page is resident in physical memory and 0 if the page is on disk or hasn’t been allocated. If there are 1024 ($2^{10}$) bytes per page, what is the physical address corresponding to the decimal virtual address 3956? \(\begin{matrix} \text{Virtual Page} & \text{Valid bit} & \text{Physical page}\\ \hline 0 & 0 & 7\\ 1 & 1 & 9\\ 2 & 0 & 3\\ 3 & 1 & 2\\ 4 & 1 & 5\\ 5 & 0 & 5\\ 6 & 0 & 4\\ 7 & 1 & 1\\ \hline \end{matrix}\)
    Show Answer

    3956 = 0xF74. So the virtual page number is 3 with a page offset of 0x374. Looking up page table entry for virtual page 3, we see that the page is resident in memory (valid bit = 1) and lives in physical page 2. So the corresponding physical address is (2<<10)+0x374 = 0xB74 = 2932.


Page Replacement (Basic)

Consider two possible page-replacement strategies: LRU (the least recently used page is replaced) and FIFO (the page that has been in the memory longest is replaced). The merit of a page-replacement strategy is judged by its hit ratio. Assume that, after space has been reserved for the page table, the interrupt service routines, and the operating-system kernel, there is only sufficient room left in the main memory for four user-program pages. Assume also that initially virtual pages 1, 2, 3, and 4 of the user program are brought into physical memory in that order.

  1. For each of the two strategies, what pages will be in the memory at the end of the following sequence of virtual page accesses? Read the sequence from left to right: (6, 3, 2, 8, 4).
    Show Answer

    LRU:
    start: 4 3 2 1
    access 6: replace 1 => 6 4 3 2
    access 3: reorder list => 3 6 4 2
    access 2: reorder list => 2 3 6 4
    access 8: replace 4 => 8 2 3 6
    access 4: replace 6 => 4 8 2 3

    FIFO:
    start: 4 3 2 1
    access 6: replace 1 => 6 4 3 2
    access 3: no change => 6 4 3 2
    access 2: no change => 6 4 3 2
    access 8: replace 2 => 8 6 4 3
    access 4: no change => 8 6 4 3


  2. Which (if either) replacement strategy will work best when the machine accesses pages in the following (stack) order: (3, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 7, 6, …)?

    Show Answer

    LRU misses on pages 3 & 7, hence having 2/8 miss rate. FIFO doesn’t work well on stack accesses, as it will have 5/8 miss rate.


  3. Which (if either) replacement strategy will work best when the machine accesses pages in the following (repeated sequence) order: (3, 4, 5, 6, 7, 3, 4, 5, 6, 7, …)?
    Show Answer

    Both strategies have a 100% miss rate in the steady state.


  4. Which (if either) replacement strategy will work best when the machine accesses pages in a randomly selected order, such as (3, 4, 2, 8, 7, 2, 5, 6, 3, 4, 8, …)?
    Show Answer

    Neither FIFO nor LRU is guaranteed to be the better strategy in dealing with random accesses since there is no locality to the reference stream.


VA-PA Address Translation (Basic)

Consider a virtual memory system that uses a single-level page map to translate virtual addresses into physical addresses. The following table shows the first 8 entries in the page map. If there are 1024 ($2^{10}$) bytes per page, what is the physical address corresponding to the virtual address 0x1C92?

Show Answer

The PA is 0x0492. You can obtain it by figuring out how many bits is the VPN. Given that there's 1024 bytes per page, this gives us the clue that PO is 10 bits, which means that VPN is consisted of 6 bits: 000111. From the table, we find that the PPN is 1 for VPN 7. Appending PPN and PO and making it 16 bits hex representation, we have PO: 0010010010 and PPN: 000001 . Appending them together and converting them to results in 0x0492.


VM Party (Intermediate)

Refer to the state of RAM, pagetable, and TLB above. The addresses in the RAM, D, and R bits are written in binary, while the VPN, PPN, and LRU are written in Hex.

The biggest LRU number refers to the MOST recently used item and vice versa, and that BYTE addressing is used. The total size of the RAM is 4 PAGES and the total number of entries in the pagetable is 8. The letter A, B, C, and D written above refers to the entire page, meaning that address 000000 to 001100 belong to page A, address 010000 to 011100 belong to page B, and so on.

  1. How many bits is PO, PPN, and VPN?

    Show Answer

    #bits of PO is 4, #bits of PPN is 2, #bits of VPN is 3


  2. Which of the following instructions does not require access to the pagetable?
    • ST(R0, 0b1111100, R31)
    • ST(R0, 0b0110100, R31)
    • ADDC(R31, 0x3, R0), ST(R0, 0b0010100, R31)
    • ADDC(R31, 0b1000000, R2), LD(R2, 0b0011000, R3), SHLC(R3, 0x4, R3)
    Show Answer

    You don't require access to the pagetable if the entry is already cached at the TLB. The second instruction and the third instruction requires translation of VPN 3 and VPN 1 which are both present in the TLB -- this means we don't need to access the pagetable anymore.


  3. We want to call the following instruction: ST(R31, 0b1100100, R31). Where is this data with VA of0b1100100 located?

    Show Answer

    VPN 6 is not resident. Therefore it is on disk.


  4. Where will the content for VPN 6 be located in the RAM after the instruction ST(R31, 0b1100100, R31) is executed, i.e: which data – A, B, C, or D will be replaced by the content of VPN 6?

    Show Answer

    It will replace data B since its PPN is not in the pagetable (means that its not a relevant content and can be overwritten).


  5. Draw the state of the TLB after ST(R31, 0b1100100, R31) is executed.

    Show Answer