Paging

Question 1

What happens to the physical address space when paging is introduced?

Answer 1

Divided into fixed sized blocks called frames

Question 2

What happens to the logical address space when paging is introduced?

Answer 2

Divided into fixed size blocks called pages.

Question 3

How does paging work?

Answer 3

Logical pages are allocated into physical frames

Question 4

How are the logical addresses structured?

Answer 4

Two part logical address, page number (p) and page offset (d)

p = m-n
d = n
Where m = logical address space.

Question 5

What does the page number index?

Answer 5

Page table, the lookup table that maps page numbers to frame addresses in physical memory.

Question 6

How are the pages mapped to frames?

Answer 6

Page number doesn’t have to be the same as the frame number in memory, the page table handles the translation.

Question 7

What is the size of a page?

Answer 7

Defined by hardware, typically 4/8KB. However, many systems support multiple page sizes.

Question 8

What is the relationship between processes and paging?

Answer 8

Page table per process, defines the logical address space of the process.

Required pages allocated from available frames

Question 9

What fragmentation does paging cause?

Answer 9

External - none.

Internal - Depends on page size and process requirements.

Question 10

What are the trade-offs of page size?

Answer 10

Smaller pages = less internal fragmentation

larger pages = smaller page table

Question 11

How are page tables implemented?

Answer 11

Dedicated registers, fast but only feasible for small page tables.

Page table held in memory, dedicated register points to page table when executing - pointer stored in PCB on context switch

Question 12

What is the translation look-aside buffer?

Answer 12

TLB, set of dedicated high-speed associative registers, each containing a key:value.

Lookup examines all keys simultaneously.

Fast, expensive

Question 13

Why should address translation be cached?

Answer 13

Exploit temporal and spatial locality in programs

Avoid page table lookups

Question 14

What is TLB used for?

Answer 14

Subset of page table entries stored in TLB, keys are page numbers and values are frame numbers. Looked in before page table.

Question 15

What happens on hit and miss in a TLB?

Answer 15

TLB Hit: Frame found

TLB Miss: Lookup page table, storage entry in TLB and replace existing entry if needed.

Question 16

What is the TLB hit ratio?

Answer 16

Percentage of times a page number is found in the TLB, determining effective memory access time (eat)

a = memory access time
b = TLB access time

eat = (hit ratio * (a + b)) + ((1 - hit ratio) * (2 * a + b))

Question 17

How is protection implemented using paging?

Answer 17

Protection bits associated with each frame. One bit can indicate R/W or R-Only. Violation causes trap to kernel.

Question 18

Why do we need multi-level paging?

Answer 18

Logical address space typically large and as such, simple page tables would be very large.

Question 19

How does hierarchical paging work?

Answer 19

Page the page table - non contiguous.

Outer page table indexes pages of the page table, entries contain frame numbers for page table pages. Table contents as before.

Question 20

What happens to the page table entries logical address when we expand the page table?

Answer 20

p1, p2 = m - n/2

p1, p2, d

Question 21

What are the limits of hierarchical paging?

Answer 21

In standard paging, each process has a page table, a lot of page tables.

Just about works for 48 bits (four levels)

Question 22

How do inverted page tables work?

Answer 22

Single central page table with entry for each frame. Size proportional to the size of physical memory.

Question 23

What does each entry in the inverted page table contain?

Answer 23

• Virtual address of page stored in frame.
• PID
• Flags

Question 24

How do hashed inverted page tables work?

Answer 24

Hash function applied to page number, hit if pid matches current process.

Question 25

How do hashed inverted page tables deal with collisions

Answer 25

Chaining scheme required

Hash function chosen to minimise collisions

Search chain for PID