Paging Flashcards
What is paging?
The process of splitting physical memory into equal sized blocks.
Page
A virtual block.
Process Address Space
Set of logical addresses that a process references in its code.
Process Memory Addresses Locations
Will appear as one contiguous range in process address space, but in reality they are multiple pages that could be anywhere in physical memory.
Page Frame
The physical memory used by a page.
Page Table
Each process has a page table that maps a logical page onto a physical memory frame, and needs to be stored into memory as a part of the process image. The address is stored in the page table base register within the CPU.
Virtual Addresses
Split into high part (stores an index into page table) and low part (stores the offset into the physical page frame).
Lets say we have 4 pages in process address space, with process memory addresses 0 to 3. The page table would assign these indexes to wherever they are in physical memory.
We could have the 0th page matching to the 7th frame/index in memory, for example.
Now lets say we want a specific part in the 0th page, which is four bits. The 1st index of the page contains the information we need. So we then look at the high part of the virtual address, aka the first half of the bits, which gives us the index of the virtual page. Taking this index, we look at the page table, and whatever the index assigns to is the position of the frame the page maps to, aka 7.
We then look at the low part of the virtual address, aka the second half of the bits, which is the index within the frame. We look for the index, and retrieve the data from it.
The virtual address could then look like this in a 8 bit system: 00010111. 0001 represents 1, the index of the virtual page, and 0111 represents the index of the data in the frame.
Paging vs. Segmentation
Memory allocation is much easier with fixed size (pages), and fragmentation is eliminated.
Segmentation with Paging
Intel x86 MMU supports segmentation with paging, in which:
- process memory is split into logical segments
- segments are stored within pages
This allows the logical segments with the advantages of fixed sizes.
Page Swapping/ Paging Out
Pages being stored on disk when there is too much allocation of memory. If a process tries to access a page in main memory, however, a page fault occurs since the page is on the disk. So an interrupt is sent, which an interrupt handler catches, resulting in the page being loaded from disk.
Page Swapping Techniques
Least Recently Used
First In First Out
Least Frequently Used
Second Chance -> uses FIFO but keeps pages that were recently used.
Principle of Locality
“Over any soft period of time, a process’s memory references tend to be spatially localised” which means that memory addresses that a process refers to in the next time period are likely to be close to addresses used in the current period. This helps guessing the next memory address easier for processes that frequently come back.
POL Determined Results
- instructions don’t usually jump all over the place.
- code within a loop spends tie in same area
- accessing an array or other data structure will be around same area
A general rule of thumb is that execution stays within 20% of a process’s pages for 80% of the time.
Working Set
The set of pages W(T, s) used in the time period from T to T + s (refer to Principle of Locality).
Working Set Accuracy
The accuracy depends if it is too big (will cover several localities and therefore the predictions won’t matter as much since it is just a bigger area) or too small (the prediction is way too concise, and won’t come true as much)
