What size are the pages in this system?

They would be 4Kb because the offset has 12 bits.

What is the size of each second level page table?

Each second level page table will have 1024 entries because the second Index is 10 bits. If each entry is 4 bytes as we assumed previously that makes each table 4kb.

interesting that the second level page tables are exactly the same size as a page.

is it a coincidence or was it done on purpose?

What is the size of the outer page table.

The same size for the same reasons.

How much memory is represented by each entry in a second level page table?

Each entry points to a single page that is 4kb.

How much memory does each second level page table represent?

Each table points to up to 1024 pages of 4kb each so 4 MB.

How many entries in the outer page table would be used in the example process from page 1?

The program is 8 MB so it needs 2 entries, the heap is 4 MB so that is another entry and the stack is 2 MB which needs a full entry.

What about the second level page table for the outer page table entry for the stack, is it full?

No it will be half empty.

So by using a 2 level page table, for our example, we only need to keep 5 sub-tables in memory.

The outer page table.

4 inner page tables.

Therefore, while this example would have required 4 MB of page table space for a single level page table it only requires 20 KB when a 2 level page table is used.

 

What is the maximum amount of memory that the two level page table could take up?

4 Kb more than the single level page table. If every second level page table is full then there will be 4 MB worth of second level page tables and one outer page table.

So in that worst case scenario the two level page table doesn't help.

Luckily programs that are that large are very rare so most of the time using a two level page table is very helpful.

It is also possible to use 3 or more level page tables.

The Other Problem With Page Tables:

 

 

So paging solved the problem of not being able to run enough processes at a given time or not being able to run really large processes.

Multi-level page tables solved the problem of the page table taking up too much memory.

 

Let's consider the following instruction on a machine that doesn't use any virtual memory:

 

LOAD BX, 200

 

This instruction gets what is in memory address 200 and puts it into the BX register.