Paging Flashcards
What happens to the physical address space when paging is introduced?
Divided into fixed sized blocks called frames
What happens to the logical address space when paging is introduced?
Divided into fixed size blocks called pages.
How does paging work?
Logical pages are allocated into physical frames
How are the logical addresses structured?
Two part logical address, page number (p) and page offset (d)
p = m-n
d = n
Where m = logical address space.
What does the page number index?
Page table, the lookup table that maps page numbers to frame addresses in physical memory.
How are the pages mapped to frames?
Page number doesn’t have to be the same as the frame number in memory, the page table handles the translation.
What is the size of a page?
Defined by hardware, typically 4/8KB. However, many systems support multiple page sizes.
What is the relationship between processes and paging?
Page table per process, defines the logical address space of the process.
Required pages allocated from available frames
What fragmentation does paging cause?
External - none.
Internal - Depends on page size and process requirements.
What are the trade-offs of page size?
Smaller pages = less internal fragmentation
larger pages = smaller page table
How are page tables implemented?
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
What is the translation look-aside buffer?
TLB, set of dedicated high-speed associative registers, each containing a key:value.
Lookup examines all keys simultaneously.
Fast, expensive
Why should address translation be cached?
Exploit temporal and spatial locality in programs
Avoid page table lookups
What is TLB used for?
Subset of page table entries stored in TLB, keys are page numbers and values are frame numbers. Looked in before page table.
What happens on hit and miss in a TLB?
TLB Hit: Frame found
TLB Miss: Lookup page table, storage entry in TLB and replace existing entry if needed.
What is the TLB hit ratio?
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))
How is protection implemented using paging?
Protection bits associated with each frame. One bit can indicate R/W or R-Only. Violation causes trap to kernel.
Why do we need multi-level paging?
Logical address space typically large and as such, simple page tables would be very large.
How does hierarchical paging work?
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.
What happens to the page table entries logical address when we expand the page table?
p1, p2 = m - n/2
p1, p2, d
What are the limits of hierarchical paging?
In standard paging, each process has a page table, a lot of page tables.
Just about works for 48 bits (four levels)
How do inverted page tables work?
Single central page table with entry for each frame. Size proportional to the size of physical memory.
What does each entry in the inverted page table contain?
- Virtual address of page stored in frame.
- PID
- Flags
How do hashed inverted page tables work?
Hash function applied to page number, hit if pid matches current process.
How do hashed inverted page tables deal with collisions
Chaining scheme required
Hash function chosen to minimise collisions
Search chain for PID
