Homework 9.

Express all answers in the form "2^n bytes", e.g. "2^12 bytes", etc.
After expressing your answers as powers of 2, please also feel free to
express your answers in everyday units, such as kB, MB, GB, TB, PB, EB, etc.

When writing down the answer for each of these questions, show your reasoning
and the calculations that you're using to get to the answer. DO NOT simply write down 
the final result.

Please hand in the homework *at the beginning* of the discussion section.



Small note on notation: There is a somewhat inconsistent convention of using
"B" for Byte and "b" for bit. Mostly in CS291SP we will refer to bytes, and not
bits. In measuring network speeds and in electrical engineering contexts,
however, bits rather than bytes are commonly used.




1) Consider a computer with the following properties:

   32-bit addresses, byte addressing.
   Pages of size 2^9=512 bytes
   Page table entries (PTEs) of size 4 bytes.

Consider a program with one set of valid addresses:
0xFFFEFFFF to 0xFFFFFFFF-1 are valid.

1a) How big is the virtual address space of that machine?

1b) What is the maximum number of pages?

1c) If single-level page tables are used, how much space is consumed by this
process's page table? 

1d) How much space is consumed by PTEs with the "valid" bit set? 

1e) How much total memory is consumed by page tables if we have 256=2^8 of 
these processes running? 


2) Repeat for a machine with 64-bit addresses, and everything else
the same. Are single-level page tables adequate, or do we need a better
solution? Why?


3) Now use a two-level page table for problem 1.
32-bit addresses, byte addressing. Pages of size 2^12=4k bytes.
PTEs size 4bytes. Let the level-0 index be 8 bits.

3a) How big is level-1 index in bits?

3b) What is the size of the Level-0 page table?

3c) What is the size of a Level-1 page table?

3d) Consider a range of valid addresses from 0xFFFEFFFF to 0xFFFFFFFF-1. 
What is minimum size of the process' page table?
(hint: think about how many valid pages there are and how many level-1
pages we would need to store them; remember that all processes have
exactly one level-0 page table. What is the total space needed to store all those
page tables?)