Paging

Question 1

• What is the basic idea of paging?

- What problems of segmentation does it solve?

Answer 1

• We divide the memory into fixed-size slots of memory “Page frames” (as opposed to segmentation). Pages are the memory called.
• Internal (e.g. big constructs like the heap) and external fragmentation

Question 2

What is the page table?

Answer 2

The page table is the heart of paging. It maps virtual address numbers (VPN) to physical frame numbers (PFN). Each process needs to have a page table.

Question 3

How does the address translation work?

Answer 3

The virtual address is divided into VPN and offset. The VPN is the number of bits needed to address all pages (e.g. for 4 pages it is 2 bits). The rest is the offset (size of the page).
- The offset is the same for physical address but the VPN to PFN can change completely (even the nr. of bits).

Question 4

• What is the Translation Lookaside Buffer (TLB)?
• What problem of paging does it fix?
• What is the principle of locality?

Answer 4

• Hardware based cache in the MMU
• Fixes the problem of using too much memory for having all pages in memory
• Locality means that most of the time the same memory (temporal loc) or a near memory address (spatial loc) is accessed

Question 5

How does a TLB Entry look like?

Answer 5

TLB entry is fully associative

• VPN
• PFN
• Valid bit (If this entry is filled or not)
• Protection bit (read write exec)
• Address space identifiers (ASID) (to which process it belongs)

Question 6

TLB is efficient because of the principle of locality but the memory consumption of paging remains.

• Why are huge pages a bad solution ?
• Why is the combination of paging and segmentation not optimal?

Answer 6

• Internal fragmentation

- Internal and external fragmentation through segmentation

Question 7

• What is the multi-level page table?

Answer 7

• Basic idea: Use another level (directory) to reference page chunks. This solves memory consumption on the cost of efficiency. (Tradeoff)

Question 8

How does the multi-level page table work? (Generally)

Answer 8

1. Divide page table into page-sized chunks
2. Use a page directory to reference the page-sized chunks
3. Returns PFN of chunk or indicates that the whole chunk is empty

Question 9

What datastructure is the page directory?

- What does a page directory entry need?

Answer 9

• Linear array with one entry per chunk
• Valid bit (indicates if chunk is used or not)
• PFN of the page table chunk