Virtual Memory
1. The Basic Concepts of Virtual Memory
The Basic Definition
Virtual memory:
- Extends the external storage space into main memory space
- Lets a program address a space larger than the physical memory
- Automates the memory management
Virtual address:
- The address the program uses
- The logical address space
- Larger than the physical memory
Physical address:
- The address in the actual memory
- The physical address space
- Constrained by the physical memory
The Working Principle
Address translation:
- Converts a virtual address into a physical address
- Done through a page table or a segment table
- The hardware and the operating system work together
Bringing pages in on demand:
- The pages are brought in as the program runs
- Reduces the memory footprint
- Raises the memory utilisation
Page replacement:
- Pages are replaced when the memory runs short
- A suitable page is chosen to be evicted
- Keeps the program running correctly
The Advantages of Virtual Memory
Enlarging the address space:
- A program can use an address space larger than the physical memory
- Supports the running of large programs
- Simplifies program development
Raising the memory utilisation:
- Several programs share the physical memory
- Reduces the waste of memory
- Supports multitasking
Simplifying the memory management:
- The operating system manages the memory automatically
- The programmer does not have to care about the allocation
- Raises the development efficiency
2. Paged Virtual Memory
The Basic Concepts
Page:
- The basic unit of the virtual address space
- A memory block of a fixed size
- Usually 4KB or larger
Page frame:
- The basic unit of the physical memory
- The same size as a page
- Holds the physical position of a page
Page table:
- Records the mapping from the virtual pages to the physical page frames
- Every process has its own page table
- Held in memory
The Structure of the Page Table
Page table entry:
- Page frame number: the address of the physical page frame
- Valid bit: whether the page is in memory
- Protection bits: the access rights of the page
- Dirty bit: whether the page has been modified
- Reference bit: whether the page has been accessed
Multilevel page table:
- Reduces the memory occupied by the page table
- Supports large address spaces
- Allocates the page tables on demand
The Address Translation Process
The basic steps:
- Extract the virtual page number
- Look up the page table entry
- Check the valid bit
- Compute the physical address
The page table lookup:
- Uses the virtual page number as the index
- Finds the corresponding entry in the page table
- Obtains the physical page frame number
The address computation:
- Physical address = physical page frame number × page size + the offset within the page
- Offset within the page = virtual address mod the page size
3. Segmented Virtual Memory
The Basic Concepts
Segment:
- A logically related collection of data
- A memory block of a variable size
- For example the code segment, the data segment, and the stack segment
Segment table:
- Records the mapping from the segment number to the physical address
- Contains the segment base address and the segment length
- Supports the dynamic growth of a segment
The Structure of the Segment Table
Segment table entry:
- Segment base address: the starting address of the segment in the physical memory
- Segment length: the size of the segment
- Valid bit: whether the segment is in memory
- Protection bits: the access rights of the segment
The Address Translation Process
The basic steps:
- Extract the segment number
- Look up the segment table entry
- Check the offset within the segment
- Compute the physical address
The segment table lookup:
- Uses the segment number as the index
- Finds the corresponding entry in the segment table
- Obtains the segment base address and the segment length
The address computation:
- Physical address = segment base address + the offset within the segment
- Offset within the segment = virtual address - the starting address of the segment
4. Segmented-Paged Virtual Memory
The Basic Concepts
Segmented-paged:
- Combines the advantages of segmentation and paging
- Segments first, then pages
- Supports the dynamic growth of a segment and the page replacement
The address structure:
- Segment number: identifies the segment
- Page number: the page number within the segment
- Offset within the page: the byte address within the page
The Address Translation Process
The basic steps:
- Extract the segment number and look up the segment table
- Extract the page number and look up the page table
- Compute the physical address
The two-level lookup:
- The first level: the segment table lookup
- The second level: the page table lookup
- Combines the advantages of the two schemes
5. The TLB
The Basic Concepts
TLB:
- Translation Lookaside Buffer
- A cache of the address translations
- Accelerates the address translation process
The working principle:
- Caches the address translations that are used often
- Reduces the number of page table lookups
- Raises the speed of the address translation
The Structure of the TLB
A TLB entry:
- Virtual page number: the page number of the virtual address
- Physical page frame number: the corresponding physical page frame number
- Valid bit: whether the TLB entry is valid
- Protection bits: the access rights
The TLB organisation:
- Fully associative: fast lookup
- Set associative: balances speed against cost
- Direct mapping: simple to implement
How the TLB Works
The TLB lookup:
- Extract the virtual page number
- Search the TLB in parallel
- On a hit, use the result directly
- On a miss, look up the page table
The TLB update:
- The TLB is updated whenever the page table is updated
- It uses a write-through or a write-back policy
- Guarantees the consistency of the TLB
TLB Performance Optimisation
The TLB hit rate:
- Raise the TLB hit rate
- Reduce the number of page table lookups
- Optimise the access pattern of the program
The size of the TLB:
- Increase the capacity of the TLB
- Cache more translation results
- Balance the cost against the performance
Exercise 1
What is the role of the TLB?
Approach: Answer in five layers — what the TLB accelerates, what memory accesses it saves, what access pattern it exploits, how it fits into the hierarchy, and what it saves in power — and close with a summary sentence.
Steps:
- Accelerating the address translation:
- Caches the address translations that are used often
- Reduces the number of page table lookups
- Raises the speed of the address translation
- Reducing the memory accesses:
- Avoids a page table access on every translation
- Reduces the memory access latency
- Raises the overall performance of the system
- Optimising the access pattern:
- Exploits the spatial locality of the program
- Caches the translations of the recently accessed addresses
- Raises the TLB hit rate
- Supporting the multilevel caching:
- Acts as a cache of the address translations
- Works together with the data cache
- Forms a complete memory hierarchy
- Lowering the power consumption:
- Reduces the number of page table accesses
- Lowers the power of the memory accesses
- Raises the energy efficiency
Answer: The TLB (Translation Lookaside Buffer) is a cache of the address translations. It accelerates the translation by caching the results that are used often, which reduces the number of page table lookups and the memory access latency and therefore raises the overall performance. It optimises the access pattern by exploiting the spatial locality of the program and caching the recently used translations, so its hit rate goes up. It also completes the memory hierarchy, sitting alongside the data cache as the cache of the address translations, and it lowers the power consumption by cutting the number of page table accesses.
Exercise 2
What is the difference between paged virtual memory and segmented virtual memory?
Approach: Compare the two schemes on the seven axes that separate them — the basic unit, the address structure, the management method, the address translation, the memory allocation, the protection mechanism, and the application scenario.
Steps:
- The basic unit:
- Paged: the page, of a fixed size
- Segmented: the segment, of a variable size
- The address structure:
- Paged: page number + the offset within the page
- Segmented: segment number + the offset within the segment
- The management method:
- Paged: managed page by page, which supports the page replacement
- Segmented: managed segment by segment, which supports the segment swapping
- The address translation:
- Paged: a page table lookup, then the physical address is computed
- Segmented: a segment table lookup, then the offset within the segment is checked
- The memory allocation:
- Paged: allocated page by page, which may produce internal fragmentation
- Segmented: allocated segment by segment, which may produce external fragmentation
- The protection mechanism:
- Paged: protection at the page level
- Segmented: protection at the segment level, which is more flexible
- The application scenario:
- Paged: general-purpose systems, which support multitasking
- Segmented: specialised systems, which support modular programs
Answer: In paged virtual memory the unit is the fixed-size page, the address is a page number plus an offset within the page, the memory is managed page by page with page replacement, the translation goes through a page table lookup, the allocation is page-granular and may leave internal fragmentation, and the protection is at the page level. In segmented virtual memory the unit is the variable-size segment, the address is a segment number plus an offset within the segment, the memory is managed segment by segment with segment swapping, the translation goes through a segment table lookup and checks the offset, the allocation is segment-granular and may leave external fragmentation, and the protection is at the segment level and is more flexible. Paging fits general-purpose multitasking systems, while segmentation fits specialised systems with modular programs.
| Term | Abbreviation | Explanation |
|---|---|---|
| Virtual memory | VM | Uses the auxiliary memory to enlarge the logical address space |
| Virtual address | - | The logical address that the program uses |
| Physical address | - | The address in the actual memory |
| Address translation | - | The mapping from a virtual address to a physical address |
| Paged virtual memory | - | Virtual memory that is managed page by page |
| Page | - | A fixed-size block of the virtual address space |
| Page frame | - | A fixed-size block of the physical memory |
| Page table | - | The table that maps the pages to the page frames |
| Page table entry | PTE | One entry of a page table |
| Page table base register | PTBR | Holds the starting address of the page table |
| Page fault | - | The accessed page is not in memory |
| Page replacement | - | Choosing a page to evict on a page fault |
| First In First Out replacement | FIFO | The page that entered first is evicted first |
| Least Recently Used replacement | LRU | The page that has not been used for the longest time is evicted first |
| Clock replacement | - | A circular scan that approximates LRU |
| Working set | - | The set of pages a process has recently accessed |
| Thrashing | - | Frequent page faults that degrade the efficiency of the system |
| Segmented virtual memory | - | Virtual memory that is managed segment by segment |
| Segment | - | A logically meaningful block of a variable length |
| Segment table | - | The table that maps the segments to the physical addresses |
| Segmented-paged virtual memory | - | Segments first, then pages |
| Translation Lookaside Buffer | TLB | The high-speed cache that accelerates the address translation |
| Multilevel page table | - | A page table organised in layers |
| Inverted page table | - | A page table organised by the physical page frame |