Memory is a scare resource, so we may want to create the illusion of having more memory to be able to run more (and bigger) processes at once. We do this by swapping data from and to disk using page faults to trigger re-loading.
Virtual Memory (OS)
Virtual memory refers to the specific illusion (implemented using virtual address translation) of the computer having more memory available to processes than it actually has physical memory. We move data to a swap device further down the storage hierarchy.
Link to original
Storage Hierarchy
To get the best performance for cost, we build systems using a mix of technologies.
| Type | Example | Speed | Cost |
|---|---|---|---|
| Registers | Custom | Fastest | Most Expensive |
| Cache Memory | Custom, SRAM | ||
| Main Memory | DRAM | ||
| Backing Storage | HDD, SSD | Slowest | Cheapest |
Disk (OS)
A disk is a block device meaning they read and write data in large units at a time, typically between 512 bytes to 4 kB. Unlike memory, they are persistent but not byte- or word-addressable, only block-addressable.
Link to original
Operating systems often provide a layer of abstraction above this:
- the filesystem
- a tree of files (leaf nodes)
- directories (branch nodes)
Implementing Swapping
Page tables as defined by the hardware are no longer sufficient to keep track of what’s in our virtual address space. As far as the hardware knows, page tables exist only to map each page number to either a frame number or ‘invalid’ (nothing mapped).
There are two ways we can go about implementing swap information:
- The cheap option is to stash extra information in invalid page table entries. If hardware sees a PTE with a non-set valid bit, it is just ignored, so as the OS we can use the rest of the bits as we like.
This also means we need to know what the data is and how it is encoded so that when a page fault comes in, we can properly handle the fault. We need to know information such as what disk block the data is at, what permissions apply, whether copy-on-write applies, etc. - The realistic option is to keep a separate data structure, e.g. Linux has a red-black tree of virtual memory areas which also allows lazy creation of page table entries.
Demand-paged virtual memory
These sorts of systems are known as demand-paged meaning they transfer page-sized chunks of memory on demand when a fault comes in.
Being lazy increases performance but it is not straightforward, in any case:
- fault handling makes processes wait on I/O
- frequent swapping hurts performance
- being more eager may save time if we can predict which pages are needed proactively transferring data before it is needed is called prefetching
Modern systems combine demand paging with judicious prefetching often based on heuristics or some predictive model.
There are other features we can provide such as:
- Block cache: keep an in-memory cache of blocks of files on disk (but don’t cache the swap file)
- Memory-mapped files: provide files on disk as data in memory (but don’t cache these blocks)
A modern unified virtual memory system treats cacheable disk I/O and swappable memory roughly the same, but avoiding the issues laid out for each.