Principle of Locality
- With reference to paging schemes, locality of reference suggests that, within a process, the next memory reference will very likely be from the same page as the last memory reference
- ! We don’t need all of a process in memory, just its working set (recently/frequently used pages)
Paging vs Partitioning
-
Paging improves over partitioning because:
- Processes can move around; OS just updates page tables
- Pages don’t need to be contiguous
-
With locality, not all pages need to be in RAM → OS can fetch them only on demand
- This leads to virtual memory
-
@ It is not necessary for all pages of a process to be in memory at any one time during its execution
Advantages of Paging
- A process can run even if only part of it is in RAM
- As long as the next instruction or data location it wants is in RAM
- OS loads missing pages from disk when needed
- This allows:
- More processes in memory → better CPU utilisation
- Demand-based loading (not all memory at once)
- A single process to use more memory than physically installed
- This is virtual memory programs think they have a big continuous memory space, but OS maps it onto RAM + disk
Resident Working Sets
- Working set → the pages of a process currently loaded in RAM
- Also known as resident set
- Trade-off:
- Too big → fewer processes fit → less multiprogramming
- Too small → constant page faults → slow (thrashing)
- In practice, OS balances how many processes & how many pages per process
Virtual Memory
- Page tables become more complex when using virtual memory
- The contents of the page tables becomes more complex
- Page tables now store more info per entry:
- P bit: indicates if the page in RAM
- M bit: has the page been modified since it entered RAM
- Hardware + OS together handle translation and fault handling
Page Replacement
- When a Running process requests a page not in RAM, a page fault results and a frame in memory must be replaced with required page
- If memory is full, an existing page must be evicted
- ! This leads to an issue:
- If a page is evicted just before it is required, it will need to be paged back in
- If this continues, page thrashing is observed
- There needs to be intelligent selection of which page to replace
VM Implementation Considerations
- ? When to load pages?
- Demand paging: only when referenced
- Pre-paging: guess which pages will be needed soon and load in advance
- ? Where to put them in RAM?
- Similar placement strategies (first-fit, best-fit, next-fit), but usually doesn’t matter much for pages
- ? Which page to evict?
- First-in, first-out simple, but can kick out heavily used pages
- Least-recently-used good in theory, but costly to implement
- Many approximations exist (OS research topic in the 70s!)
- ? How many processes to admit at once?
- More processes = higher CPU utilisation
- Too many = small working sets → thrashing