Week 7

Question 1

Suppose we have the following.

010101

What is the virtual address?

What is the virtual page number?

What is the offset?

Answer 1

Virtual Address: 21
Virtual page number: 1
Offset: 5

Question 2

What are the steps for converting a virtual address into a physical address?

Answer 2

1. Encode the physical frame number
2. Encode the physical page offset

Question 3

How does the OS find a free page?

Answer 3

One option is to keep a free list of available pages.

Because the pages are all the same size, the OS can just grab the first page in the list.

Question 4

How does the OS keep track of which process is using which physical page?

Answer 4

Using a per process data structure called a page table.

Question 5

What are some pros of paging?

Answer 5

We don’t have to allocate a physical page for all virtual pages in the address space. (use a valid bit to keep track)

We can use protection bits to mark pages as readable, writeable or executable.

We can swap pages from memory to disk and back again, allowing us to support address spaces larger than physical memory.

Different processes can share pages.

Question 6

What is a linear page table?

Answer 6

Each row in this table is a page table entry describing the mapping for a single page.

Each page table entry stores the information necessary for translation: physical frame number, protection bits, present bit, valid bit, etc.

Question 7

What are some cons of paging?

Answer 7

Memory waste. Hundreds of MBs across all processes. We need to put this information in memory.

More memory accesses. Translation is slow. Hardware must look up the correct page table entry before it can translate a virtual address.

Complexity. Swapping pages in and out means more complexity and performance challenges.

Question 8

PAGING PRACTICE

Assume we are given a virtual address. How do we calculate the cirtual page number?

Answer 8

Zero out everything but the VPN bits using a logical & operation with a bit mask.

Use a shift to move the VPN over

VPN = (VirtualAddress & VPN_MASK) >> SHIFT

Question 9

PAGING PRACTICE

How do we calculate offset?

Answer 9

Mask out everything but the offset bits

Offset = VirtualAddress & OFFSET_MASK

Question 10

How do we find the correct page table entry in a linear page table?

Answer 10

First we find the page table index. This is the same as the virtual page number.

Second we account for the page table entry size and where the page table starts in memory. The page table base register (PTBR) stores the base address of the page table.

PTE_Addr = (VPN * sizeof(PTE) + PTBR

Question 11

PAGING PRACTICE

How do we check for error conditions?

Answer 11

Raise segmentation fault if PTE is not valid.
~~~
PTE.Valid == False
~~~

Raise protection fault if memory access violates protection bits
~~~
CanAccess(PTE.ProtectBits) == False
~~~

Question 12

PAGING PRACTICE

How can we calculate the physical address now that we know the physical page number?

Answer 12

PhysAddr = (PTE.PFN << PFN_SHIFT) | Offset

Question 13

What is the approach for TLBs?

Answer 13

Cache recent translations in the translation look aside buffer (TLB) to avoid costly accesses to the page table.

The TLB stores VPN | PFN | other bits

Question 14

What happens on a TLB hit?

Answer 14

Fast if the TLB already has the translation for the virtual page number, we can directly access the physical memory.

Question 15

Who handles the TLB miss?

Answer 15

Hardware managed. Requires knowledge of page table location and the format of the page table entries.

software (OS) managed: hardware jumps to a trap handler and the OS handles the TLB miss, updating the TLB. (more flexible than just using software).

Question 16

What happens on a TLB Miss?

Answer 16

Slow if the TLB does not have translation, then we need to grab, parse the corresponding page table entry, add it to the cache and try again.

Question 17

How do we handle a context switch in a TLB?

Answer 17

Option 1: Flush the TLB by removing all TLB entries. Costly if you frequently context switch.

Option 2: Address-space Identifier field. Link TBL entries to a
particular address space. More complex. May reduce the number
of entries that each process can use.

Question 18

Where do we put the cache (TLB)?

Answer 18

Make it part of the hardware’s
memory management unit (MMU).

Question 19

The size problem

Suppose that we make the pages larger. That is we Increase the reach of each page table entry by increasing the page size, e.g., 16KB pages instead of 4KB.

What are some pros and cons

Answer 19

Pros: Table size decreases by same factor as the page size increases. TLB is now more effective as well. There is support for
this in many architectures (e.g., x86-64).

Cons: increased potential for internal fragmentation. Not great for sparse address spaces

Question 20

What is a multi level page table?

Answer 20

> Idea: split the page table into pages. If an entire page table page is
unused, don’t put it in memory.
To track the pages of the page table, we use a hierarchy of page
directory.
We call this design a multi-level page table