EECS 482 Winter 03
Problem Set 2
Due 3/3 or 3/5

1) Multi Level Page Tables

In a 32-bit machine we subdivide the virtual address into 4 parts as 
follows: 10-bit 8-bit 6-bit 8-bit, i.e. we use 3-level paging such that
the first 10 bits are the first level, etc.

If the valid virtual address range is the lowest 256 KB:
a) What is the page size in such a system?
b) How many page tables and PTEs are needed for the third level (6-bit)?
b) How many page tables and PTEs are needed for the second level (8-bit)?
b) How many page tables and PTEs are needed for the first level (10-bit)?

2) Paging the Page Table

Page tables take up a lot of space, especially for sparse address spaces.
Storing them in physical memory isn't really a viable option. One way to
address this is paging the page table, i.e. the user page table is in
the kernel's virtual address space. The kernel's page table is still
stored in physical memory.
This adds more steps to translation, since you must first translate
the virtual address for the user's page table, and then use that page
table to translate virtual addresses for the user process.

Kernel's page table starts in physical memory address 0x000 and
user's page table starts at kernel virtual address 0x10500.
Assume page table entry is 1 byte and user wants to fetch the data at
virtual address 0x98ccc. (Page size is 4KB).
a) What is the physical address of the user's PTE?
b) What is the physical address that contains the data?

For part b) assume that the value in user's PTE is Z
For part a) assume that the value of the first PTE in kernel's page
table is 0xa, and each subsequent entry is incremented by 1.

i.e.
Address     PTE Value
0x000        0xa
0x001        0xb
0x002        0xc
...

3) Multi-level page tables

Consider a computer with the following properties:
32-bit addresses, byte addressing
256-byte pages
No TLB
Page table entry occupies 4 bytes
The machine can use 1-level or 3-level paging with equal bits in each level

a) For 1-level paging, if all addresses are in use, how many page tables
are needed and how much memory is occupied by page tables at each level?

b) For 3-level paging, if all addresses are in use, how many page tables
are needed and how much memory is occupied by page tables?

c) For 1-level paging, if only the lowest 4096 and highest 4096 addresses
are in use, how many page tables are needed and how much memory is 
occupied by page tables?

d) For 3-level paging, if only the lowest 4096 and highest 4096 addresses
are in use, how many page tables are needed and how much memory is 
occupied by page tables at each level?

e) Discuss the relative advantages and disadvantages of 1-level paging
and 3-leve paging, assuming all addresses are used.

f) Discuss the relative advantages and disadvantages of 1-level paging
and 3-leve paging, assuming only the highest 4096 and lowest 4096 
addresses are used.

4) Multi Level Page Tables

A computer has a 24-bit virtual address space and 256-byte pages. It uses
two-level page tables. There are X address bits used to index the level-1
page table and Y address bits used to index the level-2 page table. Each
page table entry occupies SIZE bytes of memory. Assume that a page table
with at least one valid entry consumes as much memory as a page table
with its maximum number of valid entries. 

A certain process has two valid regionsin its virtual address space. One
valid region occupies virtual addfesses 0x0-0xFF, and the other occupies
virtual addresses 0x002100-0x0021FF. 

You are to express as general formulas (in terms of X, Y, and SIZE) the
amount of memory consumed by various levels of page tables for this
process. These formulas may be piecewise.

a) Express as a general formula the amount of total memory consumed by 
the level-1 page tables for this process. Show your reasoning.

b) Express as a general formula the amount of total memory consumed by 
the level-2 page tables for this process. Show your reasoning.