Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

Virtual Memory In-class Exercise Solution

Addrspace.png

1. There are a couple of ways to solve this problem.

1.a) There are 1024 entries and the whole table has to represent 2^32 bytes.

       So, 2^32 / 2^10 = 2^22 ==> Each entry maps 4 MB.

1.b) Each entry points to an L2 page table. An L2 table has 2^10 entries and

       each entry maps 4 KB (2^12), so 2^12 * 2^10 = 2^22.

2. So, L1Table[0] maps from address 0 to ...

       L1Table[1] maps from address 0x00400000 to ...
       L1Table[2] maps from address 0x00800000

How did we get that?

2.a) The first entry has 0's in the top 10 bits; the next entry has a 1 in the top 10 bits. So, the top 8 bits are 0's (0x00) and now the bits 01 must comprise the top 2 bits of the 3rd digit: X X X X => 0 1 X X so, if the X's are 0's, the third hex digit (from the most significant end) is 4.

2.b) We said that each entry is 2^22 in size: that's 4 MB which is 1 << 22, which is: 0x400000, so each entry adds this much to the address.

3. 

  0x08048000 (start)   ==> top 10 bits are: 0000 1000 00 -> ndx = 0x20 (=32)
  0x0804b008 (heap)    ==> same
  0x0804a024 (global)  ==> same
  0x08048870 (const global) ==> same
  0x080484a0 (main) == same
  0xb7e674a0 (printf) ==> top 10 bits are: 1011 0111 11 -> ndx = 0x2DF = (735)
  0xbffff0b0 (stack)  ==> top 10 bits are: 1011 1111 11 -> ndx = 0x2FF = (767)

4. Three (indices 32, 735, and 767 -- see diagram).

5. There are a bunch of items that are on the same page:

       start, const global, main

6. So, we'll only need 5 pages. 

   First L2 Table:
       At ndx 0x048: start, const global, main
       At ndx 0x04B: heap
       At ndx 0x04A: global
   Second L2 Table:
       At ndx 0x267: printf
   Third L2 Table:
       At ndx 0x3ff: stack
File:Pagetables.png

7. If the VAS is 8 bits; the low 4 bits are offset and the high 4 bits are the page number, so you would have 16 entries in the page table.

8. If we want the mask that produces the offset on the page, we would need: Binary: 1111 Hex: 0xF If we wanted a mast to produce the page number, we would need: Binary 00001111 Hex: 0xF0

9. ((uintptr_t) VAS) >> 4

10. (uintptr_t)VAS & 0xF

11. You would need a phyiscal page number (probably 4 bits, although there is nothing to prevent you from making it bigger, which would allow you to support physical memory larger than the virtual address space). And I guess we'd need protection bits (2 bits: invalid, read-only, read-write, read-execute). And then 1 bit for privilege/unprivilege. Wow, we have one bit to spare!

12. Well, we need 6 bits to add to the offset, so we'd just store a 6-bit page number in the PTE instead of a 4-bit one.

Code solutions are in the sample-soln branch of the exercises.