COMP 322 Chapter 7: Virtual Memory Flashcards
To study and learn Chapter 7
Virtual Memory
A collection of one or more logical address spaces.
It may exceed the size of the physical memory
Demand paging
The principle of loading a page into memory only when the page is needed, rather than at the start of the execution.
A present bit
A binary flag/bit in a page table, it indicates whether the corresponding page is currently resident in memory.
If the page is resident, the entry points to the frame that holds the page.
A page fault
An interrupt that occurs when the program attempts to reference a non-resident page.
if a page fault occurs it sets the present bit to 1.
Page replacement
The act of overwriting a page in memory with a different page loaded from the disk when needed.
The modified-bit (m-bit)
A binary bit that indicates whether the corresponding page has been modified during execution.
The modified bit is set to 1 automatically by any instruction that stores data into the page and is used by the OS.
Potential size of the Virtual Memory (VM)
2^(64)
Potential size of segment and page tables
2^(26)
A reference string
The sequence of page numbers referenced by an executing program.
The optimal page replacement algorithm
An algorithm that searches the most distant resident page and replaces it with the page that causes a page fault.
FIFO page replacement algorithm
Selects the page that has been resident in memory for the longest time.
It takes advantage of the principle of locality.
Least-recently-used page replacement algorithm (LRU)
Selects the page that has not been referenced for the longest time.
Requires a queue of length n (The number of memory frames).
When a page fault occurs, the page at the head of the queue is removed and and a new page is inserted at the end.
Requirement for the LRU
The LRU requires the queue of the pages to be modified at each memory reference.
The referenced bit (r-bit)
A bit associated with a page and is set automatically by the hardware whenever the page is referenced by any instruction.
Aging register
it is associated with a page and is shifted periodically to the right by 1 bit.
The aging page replacement algorithm
Does not maintain the pages sorted in the exact LRU order.
It groups together pages referenced during a period of consecutive references.
Each period is represented by 1 bit when shifting the aging register.
Second-chance page replacement algorithm
Is a coarse grain approximation of LRU.
It uses the r-bit to divide all pages into two categories:
recently referenced and non-recently referenced.
A page is then selected from the not-recently referenced category.
The third-chance page replacement algorithm
aka the not-recently used page replacement algorithm (NRU).
It is a coarse grain approximation of the LRU.
It divides the pages into 4 categories which is based on the 4 possible combinations of the r-bit and the m-bit:
The possible combinations are:
(for the modified page)
11 -> 01
01 -> 00
10 -> 00 unmodified page
The optimal working set
a set of resident pages that will be needed in the immediate future and should remain resident.
The working set (WS)
At time t, It is the set of pages referenced during the past d memory operations preceding t.
The working set page replacement algorithm
An algorithm that determines which pages must be resident but not in which frames.
Page fault frequency replacement algorithm
An algorithm takes a direct approach to controlling page fault rate by adjusting the current resident set based on how frequently consecutive page faults occur.
Page fault rate
its the number of page faults f occurring during a number of memory references t.
Effective access time
The average time to access memory in the presence of page faults in the presence of page faults.
