Virtual Memory Part 2 Flashcards
What 6 steps are required when handling a page fault?
1. OS figures out:
•Invalid reference
➔abort process
•Just not in memory
➔bring page in
2. Locate page on disk
3. Find a free page frame
4. Swap page from disk to frame (I/O operation)
5. Reset page table, set valid bit to 1
6. Restart the instruction that caused page faultIf the OS doesn’t have enough memory when swapping, it needs to ______ an __________ page in physical memory to make room for the _______ page
evict, existing, incoming
What does a page replacement policy do?
It handles the eviction of existing pages in physical memory to make room for the incoming page
What are 3 page replacement policies?
- First-in-first-out
- Least recently used
- Second-chance (Clock)
We can save swap out _______ if the victim page was ___ ________
overhead, not modified
The goal of Page Replacement Algorithms is to…
minimize page-fault rate
To evaluate a _____ __________ ________, we compute the number of page faults that will occur if we follow a set sequence of memory page references
Page Replacement Algorithm
We expect the number of page faults to ________ as the number of physical frames allocated to process ________
decreases, increases
For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 3 page frames using the FIFO algorithm?
9
For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the FIFO algorithm?
10
What is Belady’s Anomaly?
More frames may result in more page faults
A pro of the FIFO replacement algorithm is that it is…
easy to understand an implement
Why is performance not always good with the FIFO replacement algorithm?
- May replace a page that is used heavily
- Suffers from Belady’s Anomaly
The optimal replacement algorithm would replace the page that has not been used for the _______ time
longest
For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the optimal replacement algorithm?
6
Can we implement the optimal replacement algorithm? If so, how? If not, why?
No, because we cannot predict the future
What is the optical replacement algorithm used for?
It is used as a benchmark for comparing algorithms
With the Least Recently Used Algorithm, we try to ________ the optimal policy by __________ the future based on the _______
approximate, inferring, past
With the Least Recently Used Algorithm, we replace the page that has not been used for the _________ time
longest
Why do we replace the page that has not been used for the longest time in the LRU algorithm?
The page may not be needed anymore. Ex. pages of an initialization module
Does LRU suffer from Belady’s Anomaly?
No
For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the LRU algorithm?
8
In the LRU counter implementation, each page-table entry has a ______-___-____ field
time-of-use
In the LRU counter implementation, the CPU ______ _____ is copied into the time-of-use field upon page ________
logical clock, reference
What are 4 cons of the LRU counter implementation?
- Search overhead
- Memory write overhead
- Clock overflow
- Need hardware support
LRU _____ implementation is not common in practice
counter
In the LRU stack implementation, a _____ of page numbers is stored in a _______-linked list
stack, doubly
In the LRU stack implementation, the least recently used page sinks to the _______
bottom
What is a pro of the LRU stack implementation?
There is no need to search when replacing a page
What are 2 cons of the LRU stack implementation?
- Each memory reference becomes more expensive
- Needs hardware support
Can we implement LRU without hardware support? Why or why not?
No. It is too costly and will slow every memory reference by a factor of at least 10
The second chance replacement is also known as the ______ replacement
clock
Clock replacement is an __________ of LRU
approximation
In the clock replacement algorithm, each page has a ________ bit, initially set to ____
reference, zero
In the clock replacement algorithm, the _______ is set to one when a page is referenced
ref_bit
In the clock replacement algorithm, the algorithm maintains a ______ pointer to the next ______
moving, victim
In the clock replacement algorithm, explain the process of choosing a page to replace.
If ref_bit== 0 {
replace it
}
Else {
set ref_bit to 0
move pointer to next page
}What is thrashing?
a process is busy swapping pages in and out more than executing on CPU
What happens when the page-fault rate is very high?
- Low CPU utilization
- Makes OS think it needs to increase multiprogramming
- OS admits another process to system
How do we prevent trashing?
Give a process as many page frames as it needs
In the locality model only pages needed to execute the _______ _______ are kept. Once we execute another _______, we bring in the new ______
current function, function, pages
________ refers to the set of pages actively used together
locality
We can figure out the size of a locality using the ______-___ model
working-set
The working set is the set of _____- in the most recent delta memory __________
pages, references
The working set is a ______ _______
moving window
At each reference, a new reference is added at one end and _______ at the other from the working set
dropped
In the WS model, what happens if delta is too small?
it will not encompass entire locality
In the WS model, what happens if delta is too large?
it will encompass several localities
___________ the entire working set is costly
maintaining
We can approximate the WS with an _______ timer and _________ bit
interval, reference
There is a direct relation between the ________ _____ of a process and its _______ ____ rate
working set, page fault
To control trashing using page fault rate, we can ________ page-fault rate and ______/______ allocated frames accordingly
monitor, increase/ decrease
To control trashing using page fault rate, we need to establish an ________ page fault rate
acceptable
______ memory is treated differently from user memory
kernel
Some kernel memory needs to be _________
contiguous
Kernel memory cannot afford a ____ _____, and thus virtual memory is too ________
page fault, expensive
Often, a ____-_______ pools is dedicated to kernel which it allocates the needed memory
free-memory
The _______ system and ____ allocation are two examples of allocating kernel memory
buddy, slab
How does the buddy system allocate memory?
Allocates memory from fixed-size segment consisting of physically-contiguous pages
In the buddy system, memory is allocated in powers of ___
two
In the buddy system, when a ______ allocation is needed than what is available, split the _____ into the next lower power of 2
smaller, chunk
In the buddy system, adjacent chunks are ________ to form a large segment
combined
The slab allocator creates _______, each consisting of one or more ______
caches, slabs
In the slab allocator, a slab is one or more ________ __________ pages
physically contiguous
In the slab allocator, each cache is filled with object __________
instantiations
In the slab allocator, there is a cache for each unique kernel _______ __________
data structure
In the slab allocator, objects are initially marked as _____
free
In the slab allocator, when structures are stored, the objects are marked as _____
used
In the slab allocator, what are 2 benefits?
- Fast memory allocation
- No fragmentation
For memory-mapped files, we ____ a file into memory address space
map
What is the process if mapping a file into memory address space?
A page-sized portion of the file is read from the file system into a physical frame
Memory-mapped files is one way of implementing ______ _______ for IPC
shared memory
What are 2 benefits of memory mapped files?
- Efficient, as memory accesses are less costly then I/O
- Simple, as I/O operations in files are treated as memory accesses
What are 4 things page size selection impacts?
- Fragmentation
- Page table size
- I/O overhead
- Locality
In pre-paging, the OS brings in ____ or ____ of the pages a process will need, before they are _______
some, all, referenced
What is the tradeoff for pre-paging?
Pro: reduce number of page faults at process start-up
Con: May waste memory and I/O because some of these pages may not be used
In what scenario do we need to use I/O interlock?
- Process uses page for I/O request
- the page is replaced
- I/O comes back, but page is gone
What does I/O interlock do?
Locks the buffer/page in memory
