week 4 Flashcards
address space
set of addresses that a process can use to address memory
- each process has it’s own individual address space
base and limit registers
uses dynamic relocation
base register - contains physical address where program begins in memory
limit register - contains length of program
MMU uses limit register to find location for logical address (if logical address < limit register)
logical address + base register = physical address
swapping
brings process into memory, running it, putting it back on the disk
memory compaction
move all allocated memory downwards to turn multiple holes in memory into one big hole
- requires a lot of CPU time
bitmap
structure for tracking memory allocation (memory management)
- memory divided into allocation units of fixed size
- small allocation units: larger bitmap
- large allocation units: big chunk of memory wasted in last unit of process
when MMU brings in a process:
- search bitmap for space the size of process units (slow operation)
linked lists (for memory management)
- linked list tracks allocated (P - process) and free (H - hole) memory segments
- each entry tracks: starting address, length, pointer to next item
algorithms for allocating memory to linked list
first fit: MMU scans alomg list for first hole that is big enough
next fit: first fit but with a tracker that tracks the last allocated hole, searching from there instead of the start of the list
(slightly worse performance than next fit)
best fit: MMU searches entire list, choses smallest hole big enough
(slower than first fit, more wasted memory than first fit because it creates a lot of tiny holes)
worst fit: MMU scans along entire list, choses the biggest hole
(doesn’t perform well either)
IMPROVMENT: use separate lists for holes and processes, only search holes list
quick fit: maintains separate lists for different sizes of holes
(very fast, expensive for swapping out memory)
virtual address space
contains fixed size units called pages
virtual addresses sent by CPU to MMU
MMU maps virtual address to physical address and then to the memory bus
corresponding units in memory are called page frames
page fault
occurs when a program references an unmapped address
- operating system choose least used page frame and writes it to the disk
- fetches reference page into freed page
- restarts trapped instruction
page table entry
contains:
- absent/present bit: 1 if entry can be used, 0 if entry is not in memory (page fault)
- protection bit: 0 for read and write, 1 for read only
- modified bit: 0 for not modified (can be discarded if page frame is reclaimed), 1 for modified (must be written to disk if page is reclaimed)
- referenced bit: 0 for not accessed, 1 for accessed (used to chose which pages to evict, accessed pages are less favourable to evict)
TLB
translation lookaside buffer
- implementation for speeding up paging and handling large virtual address spaces
- inside the MMU
- consists of a small number of entries containing the most frequently used pages
columns
- valid
- virtual page
- modified bit
- protection bit
- page frame
if page number is not in the TLB, MMU detects miss and searches the page table
- evicts TLB entry
- replaces it with current page table lookup
protection fault
generated when instruction tries to write on a read only page
optimal page replacement algorithm
impossible to implement
- chose page with the highest number of instructions to be executed before the page will be referenced (no way to track)
not recently used page replacement algorithm
refers to referenced and modified bits, removes pages in this order:
R: 0, M: 0
R: 0, M: 1 (possible when page was modified before clock tick cleared R, needs to be copied to disk)
R: 1, M: 0
R: 1, M: 1
FIFO page replacement algorithm
oldest page in TLB removed when TLB miss occurs
CON: may remove heavily used pages
second chance page replacement algorithm
FIFO but checks the R bit of the oldest page before evicting page
if R = 1, bit is cleared and page is added to the end of the list
if R = 0, evict the page
if all bits in TLB have been referenced, algorithm degenerates into FIFO
least recently used page replacement algorithm
evicts the page that has been unused for the longest amount of time
- maintain linked list, with the most used page at the front of the list
CON: list must be updated for every memory reference
easily implemented with 64-bit counter hardware (which few machines have)
NFU (not frequently used) algorithm:
software counter can be used:
- each page maintains a counter
- at every clock tick, r bit added to the counter
CON: heavily used pages that are no longer being used are still considered to be heavily used (to combat: counters shifted one bit to the right before r bit is added, r bit added to leftmost bit (not rightmost): process known as aging)
FURTHER CON: aging counters have a finite number of bits, bits that are 0000000 will still have different ages unbeknownst to program
how to calculate the amount of memory needed to store a page table
page table size = number of pages x page table entry size
find number of pages by:
number of pages = address space size / page size
unit conversions for bytes -> kilobytes -> megabytes -> gigabytes
1GB = 1 x 2^10 x 2^10 x 2^10 bytes
1MB = 1 x 2^10 x 2^10 bytes
1KB = 1 x 2^10 bytes
how to calculate the address translation time
chance of TLB hit x TLB clock cycle +
chance of page table hit x PTE clock cycle +
change of page fault x page replacement time
