Virtual Memory & Working Sets
Virtual Memory
The logical address space doesn’t have to match the address space of physical memory. This allows us to allocate more memory to processes than there is physical memory in the system.
This is possible by using paging:
- Not all pages need to be in memory.
- Unneeded pages can reside on disk.
- Memory becomes virtual as it is not restricted by physical memory.
Page Faults
Page faults occur when a process references a page that is not in main memory.
This is not an error.
Page faults generate an interrupt because address references cannot be satisfied until the page is swapped in from disk.
The OS response is normally to fetch the page from the disk (demand paging).
Page Replacement Problem
The page replacement problem occurs when we don’t have enough room for a fetched page.
A solution is to swap out a page from physical memory. If this is chosen poorly then persistent swapping (thrashing) will occur.
Page Replacement
The optimal policy is to swap out the page that will not be needed for the longest time.
To estimate this we use the principle of locality:
Over any short period of time, a program’s memory references tend to be spatially localised.
This means that future memory access is likely to be around the most recently accessed memory.
Working Set Model
The principle of locality defines:
- Execution doesn’t tend to jump all over the place.
- Array access will be in the same region of memory.
- Code within a loop will sped time in the same region.
- Generally, 80% of execution stays within 20% of the code.
The working set fo a process is define to be the set of resources (pages) $W(T,s)$ defines in the time interval $[T,T+s]$.
This is to say that $W(12,4)$ is the working set in the time period from 12 to 16.
Example
For the following working set:
| Pages | z | a | b | A | A | A | Z | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|
| Time | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
-
The working set for $W(3,3)$ is $\{a,z\}$.
We count all the pages that are in capitals. This is the third page (represented by the first number) and the three proceeding pages (represented by the second number).
By the principle of locality, the working set for the next time period is likely to be similar to the one for the current period.
Hence for each process:
- Try to ensure it’s working set is in memory.
- Estimate the next working set by recording the set of pages referenced in the preceding time interval.
-
The predicted working set for $W(10,2)$ is $\{a,b\}$.
We look two spaces back from the point specified. These are elements 8 and 9.
Issues
The accuracy of the working set depends on its size:
- If it is too small, it will not cover the entire locality.
- If it is too large, it will cover several localities.
Over time the working set of a process will change as reference to data and code sections move from one locality to another.
- Page fault rates will vary with these transitions.
Other Policies
There are replacement policies for use with demand paging, based loosely on working set principles:
- Least recently used (LRU)
- Replace the leased recently used page.
- First in first out (FIFO)
- Replace the page which has been in memory the longest.
- Least frequently used (LFU)
- Replace the page with the fewest reference in a recent time period.
These methods are covered more in-depth in the COMP108 - Assignment 1 introduction.