Virtual memory

From Computer History Wiki
(Redirected from Demand paging)
Jump to: navigation, search

Virtual memory or paging refers to a technique in which not all of the memory contents corresponding to a given virtual address space has to be 'resident', i.e. in actual physical main memory, while the computation which is using that address space is running.

When a reference it made to a memory location which is not resident (instead, it is generally stored in secondary storage, usually disk), the computation is stopped while the operating system arranges to have the missing memory contents made resident; once they are resident, the computation is allowed to proceed.

Details

There are usually three related things going on when virtual memory is in use:

  • What we can call virtual addressing (also called relocation), which means that the addresses seen by a user's computation, e.g. a process, is not the actual address of the main memory location that the hardware knows for that memory location, but rather a 'virtual' address private to that user/process. (Early memory management systems such as base and bounds registers provided this feature alone.)
  • What we can call non-residence, or demand loading - i.e. a computation can run without all of its virtual memory being present in physical memory, and missing items are automatically brought in by the operating system when they are needed. To do this, the user's memory has to be divided into blocks somehow, either through segmentation, or via the third:
  • Dividing the address space into pages, identically-sized blocks of address space; similarly, the physical main memory is also divided into similarly-sized page frames. When demand loading is in use, only a selected subset of the pages of a given computation's address space are assigned to page frames at any given time, and missing ones are brought into free page frames as they are needed.

In modern systems, generally all three are going on, but this is not necessarily mandatory. For example, one can have the first two without having the third; e.g. the Burroughs B5000 supported demand loading of segments, but did not have paging. It is also possible to have a sytem which has paging, but not demand loading - the paging would only be used for memory allocation (see the bottom of this page for why paging is advantageous for this).

Some systems (e.g. Multics) had/have support for multiple page sizes. The distinction between segments (which usually can be of varying size) and multiple page sizes is that segments are generally visible to to user as first-class objects, are supported in the CPU (in the instructions), etc; whereas pages are generally invisible to the user.

(But not always; some OS's allow processes to share pages, or to map file pages into process address spaces, etc. Which can make it complex to separate the two concepts...)

Segments also usually have a much larger range of sizes (the segment size, measured in small units, is often stored in a field as part of the data which describes the segment to the CPU's hardware), whereas with variable page sizes, only a few are supported.

Systems which implement a single-level store often use both segmentation and paging to do so; the segments are visible to the users, and are invisibly broken up into pages for making them resident in main memory. (The segment sizes are often given in pages in such systems.)

There is no requirement that a virtual memory system have only two levels of storage; some systems had more (e.g. Multics, which used a three-level virtual memory system, with core, drum and disk memories; later modified to fast semi-conductor main memory, slower bulk core, and disk).

Advantages

The advantages of virtual memory are several-fold:

  • It allows a computation to use more memory than the amount of actual physical memory on the machine; this oftem simplifies the program, over having to work within the confines of a more limited amount of memory.
  • The obverse face of the above is that instead of having to explicitly manage which data is kept in main memory, and which is in secondary storage, the operating system automatically performs this work on the user's behalf.

In addition, the use of fixed-size pages, and the usual practise of allowing any page of the address space to be allocated to any page frame, means there is no 'breakage' of main memory, and no need to move data around in main memory to coalesce free space (which was usually necessary on systems which did not use pages).

Implementation

In many of the first machines which implemented virtual memory (such as the KA10), an additional piece of hardware, the pager (sometimes called a paging box) was inserted in between the CPU and main memory, to perform the relocation function. The pager sometimes needed direct access to the internals of the CPU, to properly perform the demand loading function, which meant adding a pager was not necessarily a simple 'drop in' operation. (The KT11-B Paging Option for the PDP-11/20 is a example of this.)

See also

Further reading

  • Peter J. Denning, [ Virtual Memory], Computing Surveys, Vol. 2, No. 3, September 1977 - includes some sections which have fairly detailed mathematical models