Paging Flashcards
What’s another method that allows the physical address space of a process to be non-contiguous?
Paging
Paging divides physical memory into fixed-size blocks, called
page frams
Paging divides virtual memory into blocks of the same size called
pages
Paging uses a page table for
address translation
Does paging need both OS and hardware?
Yes
What sort of fragmentation does paging avoid, and what sort of fragmentation doesn’t it avoid?
Avoids external fragmentation
Doesn’t avoid internal fragmentation
The fact that paging doesn’t need to assume how the heap and stack grow and are used makes it more…
flexible
The fact that the page in the address space and the page frame are the same size in paging makes it easy to allocate and keep a free list, this makes paging more…
simple
To translate a page a virtual address is split into two parts, which are they?
Virtual Page Number (VPN) and offset
Give the definition:
Used as an index into a page table which contains base address of each page in physical memory.
Virtual Page Number (VPN)
Give the definition:
Combined with base address to define the physical memory address that is sent to the memory unit
Offset
To determine where a physical page is in paging we only need to translate the…
page number
What does the page table in paging do?
Keeps track of the mapping of virtual to physical addresses
What is the simplest form a page table?
A linear page table
What does a Page Table Entry (PTE) include?
Translation information, etc.
Give the definition:
A sort of page table that has an entry for each physical page frame of the system. The entry tells us which process is using this page, and which virtual page of the process maps to this physical page
Inverted page table
What are the pros of inverted page tables?
Memory saving
What are the cons of inverted page tables?
Long searching time, page sharing
How is page sharing implemented for a per-process page table?
By letting two pages point to the same frame
How is page sharing implemented for an inverted page table?
It’s difficult to implement
What is the biggest problem with paging?
The performance is affected by a factor of 2 due to every instruction requiring two memory accesses
Why do we use a Table Lookaside Buffer (TLB)?
To speed up the paging translation
Give the definition:
Virtual Page Number (VPN) is in TLB and can be quickly accessed
TLB hit
Give the definition:
VPN is not in TLB. Access page table to get the translation, update the TLB entry with the translation
TLB miss
What sort of locality makes it possible for the TLB to improve performance?
Spatial locality
Give the definition:
An instruction or data item that has been recently accessed will likely be re-accessed soon in the future
Temporal locality
Give the definition:
If a program accesses memory at address X, it will likely soon access memory near X
Spatial locality
TLB is a … associative cache
fully
Why is the TLB a fully associative cache?
- Any given translation can be anywhere in the TLB
- Hardware searches entire TLB in parallell to find the target
What sort of entry is this?
VPN | PFN | Other bits
TLB entry
What is the biggest issue with the TLB?
Context switch
What are the two solutions to the issue with context switch with a TLB?
Flush and Address Space Identifier (ASID)
Give the definition:
- OS flushes the whole TLB on context switch
- Flush operation sets all valid bits to 0
Flush
What solution to context switching has this problem?
The overhead is too high if OS switches processes to frequently
Flush
Give the definition:
- A field in the TLB, sort of like a process identifier
Adsress Space Identifier (ASID)
What do we use instead of smaller pages to solve the problem of too big pages in paging?
Variable page size
Give the definition:
One page table for each logical segment
Paging and segmentation
What does the base register in paging and segmentation combined point to?
Physical address of the page table
What does the limit register in the combination of segmentation and paging determine?
The size of the segment
What are the two problems with combining segmentation and paging?
- Page table waste for sparsely used heap
- External fragmentation
Give the definition:
Creating multiple levels of page tables with an outer level called a page directory which tracks whether a page of the page table is valid
Multi-level paging
Multi-level paging only allocates page-table space in proportion to what?
The amount of address space being used
What are these three points a motivation for?
- Processes spend the majority of time in a small portion of code
- Processes only use a small amount of address space at any moment
- Only a small amount of address space needs to be resident in physical memory
Page swapping
Swapping makes it possible for the total physical address space of all processes to…
exceed the real physical memory of the system
Give the definition:
Reserving of space on the disk for moving pages back and forth
Swap space
How do we know where a pages lives?
Present bit / Valid bit
What’s the objective of page swapping policies?
To minimize the number of page faults (cache misses)
What are the two sorts of page selection?
Demand paging and prefetch
Give the definition:
- Load page only when it’s needed
- Less I/O, less memory
Demand paging
What’s the issue with demand paging?
High page fault cost
Give the definition:
- Load page before referencing
- OS predicts future accessed pages and brings them into memory early
- Works well for some access patterns, like sequential pages
Prefetch
Give the definition:
Copy the page only is a process writes to it (demand)
Copy-On-Write Paging
What is the normal approach to page replacement?
Swap Daemon, Page Daemon
Give the definition:
- There are fewer than LW (Low Watermark) pages available, a background thread that’s responsible for freeing memory is activated
- The thread evicts pages until there are High Watermark (HW) pages available
Swap Daemon, Page Daemon
Average Memory Access Time (AMAT)
Phit * Tm * Pmiss * Td
What are the four most commonly used page replacement policies?
Optimal replacement
FIFO
Least-Recently-Used (LRU)
Give the definition:
Replace the page which isn’t used for the longest time in the future
Optimal replacement
What page replacement policy has the following pros:
Minimal number of page faults
Optimal replacement
What page replacement policy has the following cons:
Impractical, need to predict the future
Optimal replacement
Give the definition:
Replace the page which is loaded into memory first
FIFO
What page replacement policy has the following pros:
Fair, easy to implement
FIFO
What page replacement policy has the following cons:
May evict useful pages
FIFO
Give the definition:
Replace the page which hasn’t been used for the longest time
Least-Recently-Used (LRU)
What page replacement policy has the following pros:
Approximate optimal replacement
LRU
What page replacement policy has the following con:
Difficult to implement
LRU
The performance of replacement policies also depends on…
workloads
When there’s a random workload, which replacement policy works best?
No difference
When there’s a 80/20 workload, which replacement policy works best?
LRU
When there’s a looping sequential workload, which replacement policy works best?
RAND
What happens to the performance of LRU and RAND, if more physical memory is added?
Have fewer, or the same number, of page faults
What happens to the performance of FIFO, if more physical memory is added?
More page faults due to Belady’s anomaly
What does description implement?
- A datastructure to track reference time of all pages
- A timestamp register added to each page
- Approximating of implementation, by finding an old page, but not necessarily the oldest one
LRU
What algorithm does this describe?
A use/reference bit for each page
A circular queue of all physical pages
A clock hand to select which page to evict
Clock algorithm (second chance)
A form of flexible virtual memory management is…
Paging
What VMM has these to challenges:
Slow access
Big page table and high memory consumption
Paging
What is used to solve the problem with slow access in paging?
TLB
What techniques within paging are used when we have a big page table?
Multi-level paging and inverted page tables
What techniques are used when we have a larger address space in paging?
Swapping and replacement
