Module 10 Vocab Flashcards
Virtual Memory
virtual memory is the memory that is allocated to a process for storing its in-memory state. It is considered “virtual” because at creation, it is not yet mapped into physical memory locations. Virtual memory is broken down into the code, data, stack, and heap segments, creating a standardized memory representation between all processes. Virtual memory offers the OS a complete separation of logical and physical addresses.
Segmentation
divides the address space into variable sized segments or logical addressable units. These include the code, stack, heap, and data segments.
Virtual Memory Page
a contiguous block of virtual memory addresses of a fixed range, which is the same as page frames. A page is the smallest unit of addressability to virtual memory available to the OS for memory management. Pages will not contain addresses from different segments of virtual memory.
Page Frames
a contiguous block of physical memory addresses of a fixed range, which is the same as the size of virtual memory pages. Virtual memory pages swapped into main memory from storage are mapped to page frames.
Disk Controller
enables the CPU to communicate with the disk storage
Paging
Paging is the technique by which the OS swaps in various virtual memory pages as they are needed as virtual memory is typically much larger than physical memory.
Memory Management Unit (MMU)
translates virtual addresses to physical addresses. Divides the virtual address space into pages.
Validity Bit
stored in the page table; 1 if a page is in memory and 0 if it is not
Page Table
a table exists for each process to map from a page number to page frame
Swap File
space in the hard disk that operates as an extension of the RAM for portions of the process virtual memory that do not fit in RAM. Pages can be stored in the swap file to create room for other processes to execute in RAM.
Protection Bit
stored in the page table; set to read, write, or execute depending on the segment
Reference Bit
stored in the page table; allows us to detect pages that are frequently used by setting this bit to 1 when a page is accessed
Modified (“Dirty”) bit
stored in the page table; set to 1 if a page has been written to and 0 otherwise (on pure reads)
Multi-level paging
divide up the virtual addresses such that the highest order group indexes into a top level page table, the second highest order group indexes into the next level page table, and so on. When looking up in a multi-level page table, the corresponding bits of the page number are used to index into each level until we get to the page table of interest. This strategy is used because virtual memory is often larger than physical memory and each process has its own page table, thus the total amount of memory required to store page tables needs to be managed.
Inverted Page Table
stores entries in the form of (page-frame, process ID, and page number), which is like a hash table, to help find the desired page frames and avoid a linear search of the page table
Offset
in the offset number, the lower order bits correspond to the offset at which we want to access addresses within a given page, and the higher order bits represent the page we want to access
Transaction Lookaside Buffer (TLB)
small cache maintained within the MMU hardware to lookup pages before we go to main memory to retrieve the page table. The TLB is associative memory.
Page Fault
when a page is requested but is not currently in physical memory; causes a trap to the kernel
Page Replacement
when a page is required, but physical memory is full, the page replacement process selects one of the current pages in physical memory to be written ut to disk
FIFO
replace the longest resident page that is already in memory
Other Policies Include
second-chance algorithm, clock algorithm, least recently used algorithm (LRU), approximate LRU
Stack Property
incrementing the amount of frames from m to m+1 cannot increase the number of page faults
Belady’s Anomaly
some page replacement policies do not respect the stack algorithm property
What is the goal of memory management in virtual memory architecture?
To map virtual memory to physical memory for each process using the Memory Management Unit (MMU).
Ex. It’s like giving each process its own GPS to find the actual location of its data in RAM.
What is the MMU (Memory Management Unit)?
A hardware component that translates virtual addresses to physical addresses.
Ex. Like a translator converting room numbers (virtual) into actual building locations (physical).
What is paging in virtual memory?
Dividing memory into fixed-size chunks (pages) to manage memory efficiently.
EX. Think of cutting a book into equal-sized pages so you can store or retrieve any page easily.
What is segmentation in virtual memory?
Dividing memory into variable-size segments based on logical divisions like code, data, stack.
Ex. Like splitting a suitcase into flexible compartments based on item size.
What is a frame?
A fixed-size chunk of physical memory (RAM) where a page can be stored.
What is a page?
A fixed-size chunk of virtual memory that maps to a frame in RAM.
What is swap space?
Reserved disk space used when RAM is full to temporarily store pages.
Ex. Like using your hard drive as overflow storage when your desk is full.
What is a page table?
A data structure that maps virtual pages to physical frames.
What is a page fault?
When the CPU tries to access a page not currently in RAM.
What is swapping?
Moving pages between RAM and disk (swap space).
Ex. Like rotating clothes in and out of storage when your closet is full.
What is thrashing?
Excessive swapping that causes a system to slow down.
Ex. Like spending so much time getting files from storage that you stop working.
What is virtual address space?
The total range of addresses a program can use, not all of which map to physical memory.
Why is each page 4KB (2¹² bytes)?
It’s a standard size, allowing easy division and addressing.
EX. Makes math and hardware design simpler and efficient.
What does VPN (Virtual Page Number) do?
Identifies which page a memory location belongs to.
What is the offset in a virtual address?
Specifies the exact location within a page.
How is virtual address translated to physical?
The MMU uses the page number to look up the frame, combines it with the offset.
Why is mapping from virtual to physical memory not 1-to-1?
Pages can be mapped out of order, depending on availability.
What is the role of the page table in this mapping?
It links virtual page numbers to physical frame numbers.
What does the MMU output?
A physical address in the form (frame number, offset).
Where is the page table stored?
In physical memory, pointed to by each process’s PCB.
What is a validity bit?
A bit indicating whether a page is in memory (1) or not (0).
What is the dirty (modified) bit?
Indicates if a page has been written to; used to avoid unnecessary disk writes.
What is the referenced bit?
Set by hardware when a page is accessed; used in page replacement algorithms.
What is the swap file?
A file used to store pages that don’t currently fit in RAM.
How are holes in the swap file reused?
A bitmap tracks used (1) and free (0) blocks to recycle space efficiently.
What are the tradeoffs of large page sizes?
Fewer pages and smaller tables, but more internal fragmentation.
What are the tradeoffs of small page sizes?
Less memory waste but larger page tables.
Why can’t page tables fit in memory on 64-bit systems?
There are too many entries; the table would be too large.
What is a multi-level page table?
A tree-like structure that breaks the page table into smaller pieces to save memory.
What is an inverted page table?
Maps physical memory instead of virtual, reducing table size.
What is the TLB (Translation Lookaside Buffer)?
A small hardware cache that stores recent page table entries for fast access.
What happens if a page is not found in TLB?
A TLB miss occurs, and the system falls back to the full page table lookup.
What happens during a page fault?
The system pauses the process, loads the required page from disk into RAM, updates the page table, and resumes execution.
What is the role of a page replacement policy?
To decide which page to evict from RAM when space is needed.
What is the problem with simple page tables for large programs?
They reserve too much space even if the program doesn’t use all of it, leading to wasted memory.
What is the solution to overly large page tables?
Use multi-level paging to make it hierarchical, loading only parts of the page table as needed.
Ex. Like folders within folders on your computer.
What is multi-level paging?
A method that organizes page tables as a tree, allowing only parts to be loaded into memory.
Ex. Instead of loading every contact in your phone, only load the group you’re texting.
What is the tradeoff of multi-level paging?
It’s slower due to multiple lookups but saves memory. Speed loss is minimized using cache.
What is a TLB (Translation Lookaside Buffer)?
A small, fast cache in the MMU that stores recently used page table entries.
Why do we need a TLB?
Accessing main memory is slow (~10ns), while CPU cycles are fast (~1ns). TLB reduces the time by caching page table lookups.
What happens if the TLB has the page info?
It’s a TLB hit — the CPU gets the physical address very fast.
What happens on a TLB miss?
The system falls back to the full page table and may replace a TLB entry.
What is associative memory in the context of TLBs?
It’s memory that is searched by content instead of address to quickly find if a mapping exists.
What does a TLB entry contain?
Page number, frame number, reference bit, modified bit, and protection bits.
What is the reference bit in a TLB?
It indicates if the page was accessed recently.
Ex. 1 for hot (used), 0 for cold (unused).
What is the modified (dirty) bit in a TLB?
It indicates whether the page was changed. If so, it must be saved before eviction.
What is the protection bit in a TLB?
It controls access rights like read-only, write, or no access.
What happens when memory content is updated?
The corresponding TLB entry must be updated too (and vice versa).
What is an inverted page table?
Instead of mapping virtual page → physical frame, it maps physical frame → virtual page.
Why use inverted page tables?
To save space, especially useful on 64-bit systems with huge address spaces.
What does an entry in an inverted page table contain?
A physical page frame, process ID, and virtual page number.
How do you find a page frame in inverted page tables?
Using a hash table to map virtual pages to frames.
What is a page fault?
A page fault happens when a program tries to access memory that isn’t currently in RAM.
Ex. A program tries to use data that was moved to disk, triggering a fetch.
What is page replacement?
Swapping out an existing page from RAM to make room for a new one from disk.
Ex. Replacing a cold page in RAM with one the program needs now.
What happens if the dirty bit is set during replacement?
The page is copied back to disk before eviction because it was changed.
A word doc page with edits needs saving before it’s removed from RAM.
What is the dirty bit used for?
Shows whether a page has been modified in RAM and needs saving.
Ex. Dirty = changes made, needs saving.
What is the goal of a page replacement policy?
Evict pages that are least likely to be used again soon.
What is the optimal (OPT) page replacement policy?
Evicts the page that will be used farthest in the future. Not realistic.
What is LRU (Least Recently Used)?
Removes the page that hasn’t been used in the longest time.
Ex. Like cleaning out your fridge by tossing the food you haven’t touched in weeks.
What is the cost comparison of memory access types?
TLB lookup = small, page table = medium, disk access = very slow.
What are two ways to improve virtual memory performance?
- Add more RAM. 2. Use better replacement policies (like LRU).
What is a reference string?
A sequence of page requests by a program.
Ex. [2, 3, 2, 1, 5, 2…]
Shows the pages accessed and adds them to a list. Typically used in page replacement policy
What is FIFO in page replacement?
First-in, first-out. Removes oldest page first, regardless of usage.
What is the competitive ratio in paging?
Ratio of real algorithm’s page faults vs. OPT. Closer to 1 = better.
How does the reference and modified bits help LRU approximation?
OS checks if pages were recently used or written to, helping decide eviction.
What is the second-chance algorithm?
FIFO with a twist: If the page was recently used (R=1), don’t evict it yet—give it another try.
What is the clock algorithm?
Like second-chance but uses a circular list with a ‘hand’ to point at pages. Evict if R=0, else give another chance.
How does the counter-based LRU method work?
Each memory access updates a timestamp; oldest timestamp = evict. Very accurate but expensive.
How does the list-based LRU method work?
Most recently used page goes to the end. Evict from the front.
Ex. Like a playlist where the newest song is added last.
What is the aging algorithm?
Each page has an 8-bit counter. Every 40ms, shift right and add reference bit on left. Higher value = used recently.
What is a stack algorithm?
An algorithm where more memory never increases page faults.
Ex. LRU is one.
What is Belady’s Anomaly?
Adding more memory causes more page faults.
Ex. FIFO can cause this.
What is thrashing?
System spends more time swapping pages than doing useful work.
Ex. Too many apps open, none run well.
What is demand-paging in Linux?
Pages are loaded into memory only when needed.
Ex. Like loading apps on-demand rather than all at once.
What is the role of the page daemon in Linux?
It manages paging, like deciding what to evict or keep in memory.
What are the 4 types of pages in Linux?
- Unreclaimable – Kernel use, can’t evict 2. Swappable – User data, needs to go to disk when evicted 3. Syncable – Write immediately when dirtied 4. Discardable – Unused, can evict right away.
What is the Linux page replacement strategy?
Uses two LRU lists: active and inactive. Evict from inactive first.
When does Linux move a page to the inactive list?
If it hasn’t been referenced recently.
When is a page moved back to the active list in Linux?
When it’s accessed again and its reference flag is set.
