CSCI-UA.0202 Spring 2015 Homework 6

Handed out Friday, March 20, 2015
Due 10:00 AM, Friday, March 27, 2015

Homework 6

These problems should be done on your own. As usual, we're not going to grade these strictly (we'll mainly look at whether you attempted them). But they reinforce knowledge and skills that the remaining labs will assume, so you ought to work through them carefully.

Virtual memory brushup

If you have not done it yet, do the VM fundamentals reading. This reading includes practice problems, and we ask about those here.

Give your answer to problem 9.1 (p779)
Give your answer to problem 9.2 (p781)
Give your answer to problem 9.3 (p790)
Give your answer to problem 9.4 (p798)

Segmentation

Based on the 14-bit segmentation scheme that we saw in lecture (in which the top two bits select a segment, the bottom 12 bits represent the offset, etc.), choose True or False for the following assertions, and justify:

T/F Two different virtual addresses in the same segment can point to the same physical address.
T/F Two different virtual addresses in different segments can point to the same physical address.
T/F Using segmentation, a virtual address can be mapped into arbitrary physical address if configured properly.
(e.g. virtual address 0x1424 can be mapped to any address in [0x0, 0x3fff].)

Page table walking

In this question, you are going to manually simulate the page table walking that the x86 does to translate virtual addresses to physical addresses. You will translate two virtual addresses. Some notes:

This is the standard x86 32-bit two-level page table structure (discussed in lecture, depicted on the handouts, etc).
You can ignore segmentation.
The content of %cr3 (the pointer to the page directory) is 0xffff1000.
The permission bits of page directory entries and page table entries are set to 0x7 (which means PTE_U | PTE_W | PTE_P, using the terminology of lab 5). This means that the virtual addresses are valid, and that user programs can read (load) from and write (store) to the virtual address.
The memory pages are listed below. On the left side of the pages are their addresses. For example, the address of the "top-left" memory block (4 bytes) is 0xf0f02ffc, and its content is 0xf0f03007.

 
             +------------+            +------------+            +------------+            +------------+
 0xf0f02ffc  | 0xf00f3007 | 0xff005ffc | 0xbebeebee | 0xffff1ffc | 0xd5202007 | 0xffff5ffc | 0xdeadbeef |
             +------------+            +------------+            +------------+            +------------+
             | ...        |            | ...        |            | ...        |            | ...        |
             +------------+            +------------+            +------------+            +------------+
 0xf0f02800  | 0xff005007 | 0xff005800 | 0xf00f8000 | 0xffff1800 | 0xef005007 | 0xffff5800 | 0xff005000 |
             +------------+            +------------+            +------------+            +------------+
             | ...        |            | ...        |            | ...        |            | ...        |
             +------------+            +------------+            +------------+            +------------+
 0xf0f02000  | 0xffff5007 | 0xff005000 | 0xc5201000 | 0xffff1000 | 0xf0f02007 | 0xffff5000 | 0xc5202000 |
             +------------+            +------------+            +------------+            +------------+

Based on the pages and %cr3 value above, what's the output of the following C excerpt? (Note: %x in printf means printing out the integer in hexadecimal format.)

  int *ptr1 = (int *) 0x0;
  int *ptr2 = (int *) 0x200ffc;
  printf("%x %x\n", *ptr1, *ptr2);

TLB, page faults

Assume that the assembly code below is executed after a context switch. Make the following additional assumptions:

The TLB is flushed (emptied) after context switch (this is how the x86 works).
Suppose all data pages (i.e. 0x200000, 0x300000) are stored on disk when instruction 0x500 is executing.
There is no prefetching.

[context switch]
0x500     movl 0x200000, %eax    # move data in address 0x200000 to register %eax
0x504     incl %eax, 1           # add one to %eax
0x508     movl %eax, 0x300000    # move register %eax to memory location 0x300000

Answer the following questions:

How many TLB misses will happen, and for which pages?
How many page faults will happen, and for which pages?

Last updated: Mon May 04 11:24:46 -0400 2015 [validate xhtml]