Memory management questions

Assume you have a small virtual address space of size 64 KB. Further assume that this is a system that uses paging and that each page is of size 8 KB.
(a) How many bits are in a virtual address in this system?

16 (1-KB of address space needs 10 bits, and 64 needs 6; thus 16).

(b) Recall that with paging, a virtual address is usually split into two components: a virtual page number (VPN) and an offset. How many bits are in the VPN?

3. Only eight 8-KB pages in a 64-KB address space.

(c) How many bits are in the offset?

16 (VA) - 3 (VPN) = 13.
Alternately: an 8KB page of course requires 13 bits to address each byte (213 = 8192).

(d) Now assume that the OS is using a linear page table, as discussed in class. How many entries does this linear page table contain?

One entry per virtual page. Thus, 8.

Now assume you again have a small virtual address space of size 64 KB, that the system again uses paging, but that each page is of size 4 bytes (note: not KB!).


(a) How many bits are in a virtual address in this system?

Still 16. The address space is the same size.

(b) How many bits are in the VPN?

14.

(c) How many bits are in the offset?

Just 2 (4 bytes).

(d) Again assume that the OS is using a linear page table. How many entries does this linear page table contain?
2**14, or 16,384.
____________________________________________________________________________________

 Consider the following segment table:

Segment  Base  Length
    0   219    600
    1  2300     14
    2    90    100
    3  1327    580
    4  1952     96

What are the physical addressed for the following logical addresses?

(a) 0,430

(b) 1,10

(c) 2,500

(d) 3,400

(e) 4,112

• (a) 219 + 430 = 649
• (b) 2300 + 10 = 2310
• (c) illegal reference; traps to operating system
• (d) 1327 + 400 = 1727
• (e) illegal reference; traps to operating system 

___________________________________________________________________________


Consider a paging system with the page table stored in memory.

(a) If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?

(b) If we add associative registers, and 75% of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)

• 400 nanoseconds. 200 ns to access the page table plus 200 ns to access the word in memory.
• 250 nanoseconds. 75% of the time it's 200 ns, and the other 25% of the time it's 400ns, so the equation is:

  e.a. = (.75*200)+(.25*400)

  ________________________________________________________________________
  
  A certain computer provides its users with a virtual memory space of 2**32 bytes. The computer has 2**18 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4K bytes. A user process generated the virtual address 11123456. Explain how the system establishes the corresponding physical location.
  
  * The virtual address in binary form is
  
  0001 0001 0001 0010 0011 0100 0101 0110
  
  Since the page size is 2**12, the page table size is 2**20. Therefore, the low-order 12 bits (0100 0101 0110) are used as the displacement into the page, while the remaining 20 bits (0001 0001 0001 0010 0011) are used as the displacement in the page table.