Memory Management Flashcards
Memory divided into allocation units. Each unit is a bit, 0 if the unit is free and 1 if occupied
Memory management with bitmaps
Memory managed via nodes
Memory management with linked lists
Process blocks or holes, indicated via first value in linked list
Memory management with linked lists
Look through all segments until an open hole is found of sufficient size. Use up as much of segment as possible
First fit
Keep pointer to last memory hole and insert into next region (hole or ones after) that can fit memory
Next fit
Take the smallest hole that is adequate
Best fit
Take the largest hole possible
Worst fit
Load first instruction at base address and add base address to all other instructions
Static relocation
Base and limit registers
Intel 8088
Brings program into main memory and runs for certain chunk of time
Swapping
Allows program to run even if only part of program in main memory
Virtual memory
Where virtual addresses are mapped to physical addresses
Memory management unit
What occurs during a page fault
- OS picks page to write with disk
- Bring page with needed address into memory
- Restart instruction
Stores frequently accessed frames in the MMU
Translation Lookaside Buffer
Indicates in TLB that page is in use
valid bit
What occurs during TLB page fault
Page table lookup and evict TLB entry
When page table is not in TLB but is in active memory
Soft miss
Page table is not in TLB but is in disk
Hard miss
Entries = virtual address size / (page size * ram size)
Inverted page table number of entries
2^PT_1 * 2^PT_2 * 2^offset
Total addressable memory in Multi level page table
Each process keeps own page table. Converts virtual page number to physical frame / page address
Regular page table
Virtual page for each occupied physical memory frame
Inverted page table
Easier to map from physical to logical addresses
Inverted page table
Easier to map from logical to physical addresses
Regular page table
If page is written to, before we evict it, must
copy it to disk
Pick page which will not be used in future for longest time
Optimal page replacement
Use R and M to create classes of page. Select page from lowest class for eviction
Not Recently Used
not referenced, not modified
class 0
not referenced, modified
class 1
referenced, not modified
class 2
referenced, modified
class 3
keep list ordered by time and evict oldest
FIFO
pages sorted by FIFO. When at end of queue, if R (read) bit is 1, set to 0 and move to end of queue
Second chance algorithm
When page fault occurs, page the hand is pointing to is inspected. If R = 0, evict the page. If R = 1, set R = 0 and advance hand
Clock page replacement algorithm
Replace page that has not been used in the most amount of time
Least recently used
Number of pages at time t used by k most recent memory references. If fault occurs, replace page not in set.
Working set
Reference bit is 1
page referenced during current tick and is in WS
Reference bit is 0
Must manually check if page is in working set
Page not in working set and page is clean
replace page
Page not in working set and page dirty
Write to disk and go to next page in WS
Takes into account just processes that faulted
local paging
takes into account all processes
global paging
Waste memory when working sets shrink
local paging
Use page fault frequency to modify allocation size for each process
global paging
Occurs when pages faults are constantly happening
thrashing
Size of page
sqrt(2s * e), with s process size and e size of page table entry
t = (1 - p) * a + p * f
performance estimation of page fault
allocate dynamic partitions to process when starts up
static partition
manage processes as list of free chunks. Page offset in virtual address space corresponds to address on disk
static partition
don’t allocate disk space in advance, swap pages in/out as needed
dynamic partition
Requires programmer to be aware of underlying technique for MM
segmentation
Number of linear address spaces in paging
1
Number of linear address spaces in segmentation
many
Total address size can exceed size of physical memory
both segmentation and paging
Procedures and data be distinguished and protected separately
Yes for segmentation, no for paging
Handles tables with changing sizes
Yes segmentation, no paging
Linear address space for less physical memory
Invention of paging reason
Allows programs to be divided into logically independent spaces
Invention of segmentation reason
When processes do not need memory anymore, causing gaps in-between segments
external fragmentation
Go through all segments and advance any in-use segment to remove wasted space
compaction
Program requests more memory than needed, leading to excess allocation
internal fragmentation
Paging individual segments
MULTICS
