Virtual Memory

Computer memory can be classified as primary (/main) or secondary. Primary memory is directly addressable by the processor, while secondary memory is not directly addressable.

Prior to Virtual Memory (VM) code and data addressable by running processes was restricted to being small enough to fit into primary memory. This could be partitioned to allow concurrent processes.

The size of main-memory therefore placed restrictions on the number of processes and on the size of the processes & addressable data. Techniques (overlays, swapping and virtual memory) were developed to overcome these restrictions.

Virtual Memory

  • Provides uniform handling of program code and data (transparent to programmer)
  • Provides the abstraction of a larger directly addressable memory than is actually available in the form of primary memory
  • Decouples logical address (used by programs) from the main memory address.
  • Includes part of the secondary memory in the memory space

Since the processor can only directly address main memory, VM management involves hardware and software techniques that automatically transfer code and data between main and secondary memory.

Most VM implementations are based on fixed size blocks called pages and encompass the machine's main memory and a dedicated portion of disk called the paging area.

Multics and IBM System/38

These allowed all files to exist in virtual memory, thus eliminating the need for a separate filestore and creating a flat store. This required every byte of every file to have a unique virtual address (36-bits).
A 36-bit virtual addressing space proved inadequate as file-data grew. Implementation of wider VMs were impractical because of the size of data structures required.

Memory mapped files

This method temporarily associates a range of virtual addresses with the data in a file.

MONADS

MONADS implements new memory management techniques which are used to manage a 60-bit wide VM (128-bits in MONADS-MM). This system allows all data to exist in VM, providing a flat-store of practical size.

Conventional VM

In a conventional virtual memory system the VM space is partitioned into fixed-sized blocks called pages. Main memory is partitioned into the same sized blocks called page frames.
A mapping is maintained between VM pages and their location in main/secondary memory. When ever the processor reads from or writes to a virtual address the address is mapped onto a main-memory location.
If such a mapping is not possible a page fault condition occurs. Upon a page fault occuring:

  1. The OS suspends the process generating the fault-address
  2. Moves the required VM page into main memory (page retrieval)
  3. Updates the mapping data
  4. Reactivates the suspended process.

To provide room for further pages it is necessary to remove others from main-memory (page discard). The process of retrieval and discard is called paging.

Multiprogrammed computers support multiple processes running concurently. Processes are allotted slices of CPU time by the process scheduler. Typically each process runs in its own virtual memory space which contains the process stack, code and temporary data structures.
Virtual addresses used by each process are the same, but the mapping data is different for each process. Switching between mapping data occurs with each process switch. This technique provides protection of access to data stored in a process virtual memory space.

To achieve this virtual to main memory mapping, a page table is typically utilised. The length of such a table is proportional to the number of virtual pages. Multiprogrammed machines typically have a a page table per process, with a page table switch accompanying a process switch.

Page table

virtual-page # Present bit Status field Location field

location: main memory frame number for pages in main memory, disk address for pages not currently in main memory
present: whether or not the virtual page is in main memory
status: access info (read, write, execute) plus info used by the page discard algorithm.

Information about the disk location of pages currently in main memory is kept in a separate table called a frame table, indexed on main-memory page number.
To improve performance, a high-speed translation lookaside buffer is commonly used to store the most recent accessed address translation entries; this relies on the principle of locality of reference.

Address translation

This occurs as shown below:
address_trans.png

For small virtual memories the page table is small enough to be kept in main memory. For larger virtual memories it is not feasible to hold the page table in main memory. Eg: VAX-11 with a VM size of up to 232 bytes and a page size of 29 bytes requires a page table of 32 megabytes. Such a table is potentially needed for every process.

The solution is to hold page tables in virtual memory. As a result, page faults occur reading the page table. It is thus necessary to lock some information about page tables in main memory and to recursively build the page tables.

For example: VAX-11 uses a 256KB second level page table which is locked down in main memory. Multi-level page tables mean extra memory accesses for address translation with the risk of more page faults.

The problem with the conventional page table approach is that the length of page tables is proportional to the size of virtual memory.

"By separating the mapping of virtual addresses to main memory addresses from the mapping of virtual addresses to disk addresses, the length of main memory page tables is reduced to being proportional to the size of main memory".

  • Page tables are not needed for translating virtual addresses to main memory addresses
  • To improve efficiency of discard, the Main Memory Table (MMT) is used to map the contents of main memory page frames to disk locations

A separate mechanism is used to find the disk location of virtual pages.

  • This technique is used in MONADS.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License