Virtual memory
Encyclopedia
In computing
, virtual memory is a memory management
technique developed for multitasking
kernels
. This technique virtualizes
a computer architecture
's various forms of computer data storage (such as random-access memory
and disk storage
), allowing a program
to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM).
Most modern operating systems that support virtual memory also run each process
in its own dedicated address space
, allowing a program to be designed as though it has sole access to the virtual memory. However, some older operating systems (such as OS/VS1
and OS/VS2 SVS
) and even modern ones (such as IBM i) are single address space operating system
s that run all processes in a single address space composed of virtualized memory.
Systems that employ virtual memory:
Memory virtualization
is a generalization of the concept of virtual memory.
Virtual memory is an integral part of a computer architecture
; all implementations (excluding emulators and virtual machine
s) require hardware support, typically in the form of a memory management unit
built into the CPU
. Consequently, older operating systems, such as those for the mainframes
of the 1960s, and those for personal computers of the early to mid 1980s (e.g. DOS
), generally have no virtual memory functionality, though notable exceptions for mainframes of the 1960s include:
and the Apple Lisa
is an example of a personal computer of the 1980s which features virtual memory.
Embedded system
s and other special-purpose computer systems that require very fast and/or very consistent response times may opt not to use virtual memory due to decreased determinism
; virtual memory systems trigger unpredictable interrupt
s that may produce unwanted "jitter
" during I/O operations
. This is because embedded hardware costs are often kept low by implementing all such operations with software (a technique called bit-banging
) rather than with dedicated hardware. In any case, embedded systems usually have little use for complicated memory hierarchies.
. Virtual memory was therefore introduced not only to extend primary memory, but to make such an extension as easy as possible for programmers to use. To allow for multiprogramming
and multitasking
, many early systems divided memory between multiple programs without virtual memory, such as early models of the PDP-10
via registers
. Paging
was first developed at the University of Manchester
as a way to extend the Atlas Computer's working memory by combining its 16 thousand words of primary core memory
with an additional 96 thousand words of secondary drum memory
. The first Atlas was commissioned in 1962 but working prototypes of paging had been developed by 1959. In 1961, the Burroughs Corporation independently released the first commercial computer with virtual memory, the B5000, with segmentation
rather than paging.
Before virtual memory could be implemented in mainstream operating systems, many problems had to be addressed. Dynamic address translation required expensive and difficult to build specialized hardware; initial implementations slowed down slightly access to memory. There were worries that new system-wide algorithms utilizing secondary storage would be less effective than previously used application-specific algorithms. By 1969, the debate over virtual memory for commercial computers was over; an IBM
research team led by David Sayre showed that their virtual memory overlay system consistently worked better than the best manually controlled systems. The first minicomputer
to introduce virtual memory was the Norwegian NORD-1
; during the 1970s, other minicomputers implemented virtual memory, notably VAX
models running VMS
.
Virtual memory was introduced to the x86 architecture with the protected mode
of the Intel 80286
processor, but its segment swapping technique scaled poorly to larger segment sizes. The Intel 80386
introduced paging support underneath the existing segmentation
layer, enabling the page fault exception to chain with other exceptions without double fault
. However, loading segment descriptors was an expensive operation, causing operating system designers to rely strictly on paging rather than a combination of paging and segmentation.
into pages, blocks of contiguous virtual memory addresses. Pages are usually at least 4 kilobyte
s in size; systems with large virtual address ranges or amounts of real memory generally use larger page sizes.
s are used to translate the virtual addresses seen by the application into physical address
es used by the hardware to process instructions; such hardware that handles this specific translation is often known as the memory management unit
. Each entry in the page table holds a flag indicating whether the corresponding page is in real memory or not. If it is in real memory, the page table entry will contain the real memory address at which the page is stored. When a reference is made to a page by the hardware, if the page table entry for the page indicates that it is not currently in real memory, the hardware raises a page fault
exception
, invoking the paging supervisor component of the operating system
.
Systems can have one page table for the whole system, separate page tables for each application and segment, a tree of page tables for large segments or some combination of these. If there is only one page table, different applications running at the same time
use different parts of a single range of virtual addresses. If there are multiple page or segment tables, there are multiple virtual address spaces and concurrent applications with separate page tables redirect to different real addresses.
When all physical memory is already in use, the paging supervisor must free a page in primary storage to hold the swapped-in page. The supervisor uses one of a variety of page replacement algorithm
s such as least recently used to determine which page to free.
mechanisms rely on an array of pointers to their handlers, such as I/O
completion and page fault
. If the pages containing these pointers or the code that they invoke were pageable, interrupt-handling would become far more complex and time-consuming, particularly in the case of page fault interrupts. Hence, some part of the page table structures is not pageable.
Some pages may be pinned for short periods of time, others may be pinned for long periods of time, and still others may need to be permanently pinned. For example:
In IBM's operating systems for System/370
and successor systems, the term is "fixed", and pages may be long-term fixed, or may be short-term fixed. Control structures are often long-term fixed (measured in wall-clock time, i.e., time measured in seconds, rather than time measured in less than one second intervals) whereas I/O buffers are usually short-term fixed (usually measured in significantly less than wall-clock time, possibly for a few milliseconds). Indeed, the OS has a special facility for "fast fixing" these short-term fixed data buffers (fixing which is performed without resorting to a time-consuming Supervisor Call instruction). Additionally, the OS has yet another facility for converting an application from being long-term fixed to being fixed for an indefinite period, possibly for days, months or even years (however, this facility implicitly requires that the application firstly be swapped-out, possibly from preferred-memory, or a mixture of preferred- and non-preferred memory, and secondly be swapped-in to non-preferred memory where it resides for the duration, however long that might be; this facility utilizes a documented Supervisor Call instruction).
and similar OSes, some parts of systems memory are managed in virtual-real mode, where every virtual address corresponds to a real address, specifically interrupt
mechanisms, paging supervisor and tables in older systems, and application programs using non-standard I/O management. For example, IBM's z/OS has 3 modes (virtual-virtual, virtual-real and virtual-fixed).
, dividing virtual address spaces into variable-length segments. A virtual address here consists of a segment number and an offset within the segment. The Intel 80286
supports a similar segmentation scheme as an option, but it is rarely used. Segmentation and paging can be used together by dividing each segment into pages; systems with this memory structure, such as Multics
and IBM System/38, are usually paging-predominant, segmentation providing memory protection.
In the Intel 80386
and later IA-32
processors, the segments reside in a 32-bit
linear, paged address space. Segments can be moved in and out of that space; pages there can "page" in and out of main memory, providing two levels of virtual memory; few if any operating systems do so, instead using only paging. Early non-hardware-assisted x86 virtualization
solutions combined paging and segmentation because x86 paging offers only two protection domains whereas a VMM / guest OS / guest applications stack needs three. The difference between paging and segmentation systems is not only about memory division; segmentation is visible to user processes, as part of memory model semantics. Hence, instead of memory that looks like a single large vector, it is structured into multiple spaces.
This difference has important consequences; a segment is not a page with variable length or a simple way to lengthen the address space. Segmentation that can provide a single-level memory model in which there is no differentiation between process memory and file system consists of only a list of segments (files) mapped into the process's potential address space.
This is not the same as the mechanisms provided by calls such as mmap
and Win32's MapViewOfFile, because inter-file pointers do not work when mapping files into semi-arbitrary places. In Multics, a file (or a segment from a multi-segment file) is mapped into a segment in the address space, so files are always mapped at a segment boundary. A file's linkage section can contain pointers for which an attempt to load the pointer into a register or make an indirect reference through it causes a trap. The unresolved pointer contains an indication of the name of the segment to which the pointer refers and an offset within the segment; the handler for the trap maps the segment into the address space, puts the segment number into the pointer, changes the tag field in the pointer so that it no longer causes a trap, and returns to the code where the trap occurred, re-executing the instruction that caused the trap. This eliminates the need for a linker completely and works when different processes map the same file into different places in their private address spaces.
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, virtual memory is a memory management
Memory management
Memory management is the act of managing computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed. This is critical to the computer system.Several...
technique developed for multitasking
Computer multitasking
In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...
kernels
Kernel (computing)
In computing, the kernel is the main component of most computer operating systems; it is a bridge between applications and the actual data processing done at the hardware level. The kernel's responsibilities include managing the system's resources...
. This technique virtualizes
Hardware virtualization
Computer hardware virtualization is the virtualization of computers or operating systems. It hides the physical characteristics of a computing platform from users, instead showing another abstract computing platform...
a computer architecture
Computer architecture
In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....
's various forms of computer data storage (such as random-access memory
Random-access memory
Random access memory is a form of computer data storage. Today, it takes the form of integrated circuits that allow stored data to be accessed in any order with a worst case performance of constant time. Strictly speaking, modern types of DRAM are therefore not random access, as data is read in...
and disk storage
Disk storage
Disk storage or disc storage is a general category of storage mechanisms, in which data are digitally recorded by various electronic, magnetic, optical, or mechanical methods on a surface layer deposited of one or more planar, round and rotating disks...
), allowing a program
Application software
Application software, also known as an application or an "app", is computer software designed to help the user to perform specific tasks. Examples include enterprise software, accounting software, office suites, graphics software and media players. Many application programs deal principally with...
to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM).
Most modern operating systems that support virtual memory also run each process
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
in its own dedicated address space
Address space
In computing, an address space defines a range of discrete addresses, each of which may correspond to a network host, peripheral device, disk sector, a memory cell or other logical or physical entity.- Overview :...
, allowing a program to be designed as though it has sole access to the virtual memory. However, some older operating systems (such as OS/VS1
OS/VS1
Operating System/Virtual Storage 1, or OS/VS1,was an IBM mainframe computer operating system designed to be run on IBM System/370 hardware....
and OS/VS2 SVS
OS/VS2 (SVS)
Single Virtual Storage refers to Release 1 of Operating System/Virtual Storage 2 ; it is the successor system to the MVTBut not 65MP option of Operating System/360...
) and even modern ones (such as IBM i) are single address space operating system
Single address space operating system
In computer science, a single address space operating system is a type of operating system with simple memory management which uses only one globally shared virtual address space.- List of SASOS Projects :...
s that run all processes in a single address space composed of virtualized memory.
Systems that employ virtual memory:
- use hardware memory more efficiently than do systems without virtual memory.
- make the programming of applications easier:
- by hiding fragmentationFragmentation (computer)In computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases reducing the performance. The term is also used to denote the wasted space itself....
, - by delegating to the kernel the burden of managing the memory hierarchy (there is no need for the program to handle overlaysOverlay (programming)In a general computing sense, overlaying means "replacement of a block of stored instructions or data with another" Overlaying is a programming method that allows programs to be larger than the computer's main memory...
explicitly), - and, when each process is run in its own dedicated address space, by obviating the need to relocateRelocation (computer science)"Relocation is the process of assigning load addresses to various parts of [a] program and adjusting the code and data in the program to reflect the assigned addresses."...
program code or to access memory with relative addressing.
- by hiding fragmentation
Memory virtualization
Memory virtualization
In computer science, memory virtualization decouples volatile random access memory resources from individual systems in the data center, and then aggregates those resources into a virtualized memory pool available to any computer in the cluster. The memory pool is accessed by the operating system...
is a generalization of the concept of virtual memory.
Virtual memory is an integral part of a computer architecture
Computer architecture
In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....
; all implementations (excluding emulators and virtual machine
Virtual machine
A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...
s) require hardware support, typically in the form of a memory management unit
Memory management unit
A memory management unit , sometimes called paged memory management unit , is a computer hardware component responsible for handling accesses to memory requested by the CPU...
built into the CPU
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
. Consequently, older operating systems, such as those for the mainframes
Mainframe computer
Mainframes are powerful computers used primarily by corporate and governmental organizations for critical applications, bulk data processing such as census, industry and consumer statistics, enterprise resource planning, and financial transaction processing.The term originally referred to the...
of the 1960s, and those for personal computers of the early to mid 1980s (e.g. DOS
DOS
DOS, short for "Disk Operating System", is an acronym for several closely related operating systems that dominated the IBM PC compatible market between 1981 and 1995, or until about 2000 if one includes the partially DOS-based Microsoft Windows versions 95, 98, and Millennium Edition.Related...
), generally have no virtual memory functionality, though notable exceptions for mainframes of the 1960s include:
- The Atlas SupervisorAtlas SupervisorThe Atlas Supervisor was the program which managed the allocation of processing resources of Manchester University's Atlas Computer so that the machine was able to act on many tasks and user programs concurrently....
for the AtlasAtlas Computer (Manchester)The Atlas Computer was a joint development between the University of Manchester, Ferranti, and Plessey. The first Atlas, installed at Manchester University and officially commissioned in 1962, was one of the world's first supercomputers, considered to be the most powerful computer in the world at...
. - MCP for the Burroughs B5000.
- TSS/360TSS/360The IBM Time Sharing System TSS/360 was an early time-sharing operating system designed exclusively for a special model of the System/360 line of mainframes, the Model 67. Made available on a trial basis to a limited set of customers in 1967, it was never officially released as a supported product...
and CP/CMSCP/CMSCP/CMS was a time-sharing operating system of the late 60s and early 70s, known for its excellent performance and advanced features...
for the IBM System/360 Model 67IBM System/360 Model 67The IBM System/360 Model 67 was an important IBM mainframe model in the late 1960s. Unlike the rest of the S/360 series, it included features to facilitate time-sharing applications, notably a DAT box to support virtual memory and 32-bit addressing...
. - MulticsMulticsMultics was an influential early time-sharing operating system. The project was started in 1964 in Cambridge, Massachusetts...
for the GE 645. - The Time Sharing Operating SystemTime Sharing Operating SystemTime Sharing Operating System, or TSOS, was an operating system for RCA mainframe computers of the Spectra 70 series.RCA was in the computer business until 1971. Then it sold its computer business to Sperry Corporation; Sperry offered TSOS renaming it to VS/9...
for the RCA Spectra 70RCA Spectra 70The RCA Spectra 70 was a line of electronic data processing equipment manufactured by the Radio Corporation of America’s computer division beginning in April 1965...
/46.
and the Apple Lisa
Apple Lisa
The Apple Lisa—also known as the Lisa—is a :personal computer designed by Apple Computer, Inc. during the early 1980s....
is an example of a personal computer of the 1980s which features virtual memory.
Embedded system
Embedded system
An embedded system is a computer system designed for specific control functions within a larger system. often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. By contrast, a general-purpose computer, such as a personal...
s and other special-purpose computer systems that require very fast and/or very consistent response times may opt not to use virtual memory due to decreased determinism
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
; virtual memory systems trigger unpredictable interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
s that may produce unwanted "jitter
Jitter
Jitter is the undesired deviation from true periodicity of an assumed periodic signal in electronics and telecommunications, often in relation to a reference clock source. Jitter may be observed in characteristics such as the frequency of successive pulses, the signal amplitude, or phase of...
" during I/O operations
Input/output
In computing, input/output, or I/O, refers to the communication between an information processing system , and the outside world, possibly a human, or another information processing system. Inputs are the signals or data received by the system, and outputs are the signals or data sent from it...
. This is because embedded hardware costs are often kept low by implementing all such operations with software (a technique called bit-banging
Bit-banging
Bit banging is a technique for serial communications using software instead of dedicated hardware. Software directly sets and samples the state of pins on the microcontroller, and is responsible for all parameters of the signal: timing, levels, synchronization, etc...
) rather than with dedicated hardware. In any case, embedded systems usually have little use for complicated memory hierarchies.
History
In the 1940s and 1950s, all larger programs had to contain logic for managing primary and secondary storage, such as overlayingOverlay (programming)
In a general computing sense, overlaying means "replacement of a block of stored instructions or data with another" Overlaying is a programming method that allows programs to be larger than the computer's main memory...
. Virtual memory was therefore introduced not only to extend primary memory, but to make such an extension as easy as possible for programmers to use. To allow for multiprogramming
Multiprogramming
Computer multiprogramming is the allocation of a computer system and its resources to more than one concurrent application, job or user ....
and multitasking
Computer multitasking
In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...
, many early systems divided memory between multiple programs without virtual memory, such as early models of the PDP-10
PDP-10
The PDP-10 was a mainframe computer family manufactured by Digital Equipment Corporation from the late 1960s on; the name stands for "Programmed Data Processor model 10". The first model was delivered in 1966...
via registers
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
. Paging
Paging
In computer operating systems, paging is one of the memory-management schemes by which a computer can store and retrieve data from secondary storage for use in main memory. In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called...
was first developed at the University of Manchester
University of Manchester
The University of Manchester is a public research university located in Manchester, United Kingdom. It is a "red brick" university and a member of the Russell Group of research-intensive British universities and the N8 Group...
as a way to extend the Atlas Computer's working memory by combining its 16 thousand words of primary core memory
Magnetic core memory
Magnetic-core memory was the predominant form of random-access computer memory for 20 years . It uses tiny magnetic toroids , the cores, through which wires are threaded to write and read information. Each core represents one bit of information...
with an additional 96 thousand words of secondary drum memory
Drum memory
Drum memory is a magnetic data storage device and was an early form of computer memory widely used in the 1950s and into the 1960s, invented by Gustav Tauschek in 1932 in Austria....
. The first Atlas was commissioned in 1962 but working prototypes of paging had been developed by 1959. In 1961, the Burroughs Corporation independently released the first commercial computer with virtual memory, the B5000, with segmentation
Segmentation (memory)
Memory segmentation is the division of computer memory into segments or sections. Segments or sections are also used in object files of compiled programs when they are linked together into a program image, or when the image is loaded into memory...
rather than paging.
Before virtual memory could be implemented in mainstream operating systems, many problems had to be addressed. Dynamic address translation required expensive and difficult to build specialized hardware; initial implementations slowed down slightly access to memory. There were worries that new system-wide algorithms utilizing secondary storage would be less effective than previously used application-specific algorithms. By 1969, the debate over virtual memory for commercial computers was over; an IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
research team led by David Sayre showed that their virtual memory overlay system consistently worked better than the best manually controlled systems. The first minicomputer
Minicomputer
A minicomputer is a class of multi-user computers that lies in the middle range of the computing spectrum, in between the largest multi-user systems and the smallest single-user systems...
to introduce virtual memory was the Norwegian NORD-1
NORD-1
The NORD-1 was Norsk Data's first minicomputer. It was the first commercially available computer made in Norway.It was a 16-bit system, developed in 1967. The first NORD-1 installed was at the heart of a complete ship system aboard the M/S Taimyr, a Japanese-built cargo liner...
; during the 1970s, other minicomputers implemented virtual memory, notably VAX
VAX
VAX was an instruction set architecture developed by Digital Equipment Corporation in the mid-1970s. A 32-bit complex instruction set computer ISA, it was designed to extend or replace DEC's various Programmed Data Processor ISAs...
models running VMS
OpenVMS
OpenVMS , previously known as VAX-11/VMS, VAX/VMS or VMS, is a computer server operating system that runs on VAX, Alpha and Itanium-based families of computers. Contrary to what its name suggests, OpenVMS is not open source software; however, the source listings are available for purchase...
.
Virtual memory was introduced to the x86 architecture with the protected mode
Protected mode
In computing, protected mode, also called protected virtual address mode, is an operational mode of x86-compatible central processing units...
of the Intel 80286
Intel 80286
The Intel 80286 , introduced on 1 February 1982, was a 16-bit x86 microprocessor with 134,000 transistors. Like its contemporary simpler cousin, the 80186, it could correctly execute most software written for the earlier Intel 8086 and 8088...
processor, but its segment swapping technique scaled poorly to larger segment sizes. The Intel 80386
Intel 80386
The Intel 80386, also known as the i386, or just 386, was a 32-bit microprocessor introduced by Intel in 1985. The first versions had 275,000 transistors and were used as the central processing unit of many workstations and high-end personal computers of the time...
introduced paging support underneath the existing segmentation
Segmentation (memory)
Memory segmentation is the division of computer memory into segments or sections. Segments or sections are also used in object files of compiled programs when they are linked together into a program image, or when the image is loaded into memory...
layer, enabling the page fault exception to chain with other exceptions without double fault
Double fault
On the x86 architecture, a double fault exception occurs if the processor encounters a problem while trying to service a pending interrupt or exception. An example situation when a double fault would occur is when an interrupt is triggered but the segment in which the interrupt handler resides is...
. However, loading segment descriptors was an expensive operation, causing operating system designers to rely strictly on paging rather than a combination of paging and segmentation.
Paged virtual memory
Nearly all implementations of virtual memory divide a virtual address spaceVirtual address space
Virtual address space is a memory mapping mechanism available in modern operating systems such as OpenVMS, UNIX, Linux, and Windows NT...
into pages, blocks of contiguous virtual memory addresses. Pages are usually at least 4 kilobyte
Kilobyte
The kilobyte is a multiple of the unit byte for digital information. Although the prefix kilo- means 1000, the term kilobyte and symbol KB have historically been used to refer to either 1024 bytes or 1000 bytes, dependent upon context, in the fields of computer science and information...
s in size; systems with large virtual address ranges or amounts of real memory generally use larger page sizes.
Page tables
Page tablePage table
A page table is the data structure used by a virtual memory system in a computer operating system to store the mapping between virtual addresses and physical addresses. Virtual addresses are those unique to the accessing process...
s are used to translate the virtual addresses seen by the application into physical address
Physical address
In computing, a physical address, also real address, or binary address, is the memory address that is represented in the form of a binary number on the address bus circuitry in order to enable the data bus to access a particular storage cell of main memory.In a computer with virtual memory, the...
es used by the hardware to process instructions; such hardware that handles this specific translation is often known as the memory management unit
Memory management unit
A memory management unit , sometimes called paged memory management unit , is a computer hardware component responsible for handling accesses to memory requested by the CPU...
. Each entry in the page table holds a flag indicating whether the corresponding page is in real memory or not. If it is in real memory, the page table entry will contain the real memory address at which the page is stored. When a reference is made to a page by the hardware, if the page table entry for the page indicates that it is not currently in real memory, the hardware raises a page fault
Page fault
A page fault is a trap to the software raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. In the typical case the operating system tries to handle the page fault by making the required page accessible at a location...
exception
Exception
Exception may refer to:* An action that is not part of ordinary operations or standards* Exception handling, in programming languages** or a programming interrupt itself of which exception handling is meant to deal with....
, invoking the paging supervisor component of the operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
.
Systems can have one page table for the whole system, separate page tables for each application and segment, a tree of page tables for large segments or some combination of these. If there is only one page table, different applications running at the same time
Multiprogramming
Computer multiprogramming is the allocation of a computer system and its resources to more than one concurrent application, job or user ....
use different parts of a single range of virtual addresses. If there are multiple page or segment tables, there are multiple virtual address spaces and concurrent applications with separate page tables redirect to different real addresses.
Paging supervisor
This part of the operating system creates and manages page tables. If the hardware raises a page fault exception, the paging supervisor accesses secondary storage, returns the page that has the virtual address that resulted in the page fault, updates the page tables to reflect the physical location of the virtual address and tells the translation mechanism to restart the request.When all physical memory is already in use, the paging supervisor must free a page in primary storage to hold the swapped-in page. The supervisor uses one of a variety of page replacement algorithm
Page replacement algorithm
In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out when a page of memory needs to be allocated...
s such as least recently used to determine which page to free.
Pinned pages
Operating systems have memory areas that are pinned (never swapped to secondary storage). For example, interruptInterrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
mechanisms rely on an array of pointers to their handlers, such as I/O
I/O
I/O may refer to:* Input/output, a system of communication for information processing systems* Input-output model, an economic model of flow prediction between sectors...
completion and page fault
Page fault
A page fault is a trap to the software raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. In the typical case the operating system tries to handle the page fault by making the required page accessible at a location...
. If the pages containing these pointers or the code that they invoke were pageable, interrupt-handling would become far more complex and time-consuming, particularly in the case of page fault interrupts. Hence, some part of the page table structures is not pageable.
Some pages may be pinned for short periods of time, others may be pinned for long periods of time, and still others may need to be permanently pinned. For example:
- The paging supervisor code and drivers for secondary storage devices on which pages reside must be permanently pinned, as otherwise paging wouldn't even work because the necessary code wouldn't be available.
- Timing-dependent components may be pinned to avoid variable paging delays.
- Data buffers that are accessed directly by, say, peripheral devices that use direct memory accessDirect memory accessDirect memory access is a feature of modern computers that allows certain hardware subsystems within the computer to access system memory independently of the central processing unit ....
or I/O channels must reside in pinned pages while the I/O operation is in progress because such devices and the buses to which they are attached expect to find data buffers located at physical memory addresses; regardless of whether the bus has a memory management unit for I/OIOMMUIn computing, an input/output memory management unit is a memory management unit that connects a DMA-capable I/O bus to the main memory...
, transfers cannot be stopped if a page fault occurs and then restarted when the page fault has been processed.
In IBM's operating systems for System/370
System/370
The IBM System/370 was a model range of IBM mainframes announced on June 30, 1970 as the successors to the System/360 family. The series maintained backward compatibility with the S/360, allowing an easy migration path for customers; this, plus improved performance, were the dominant themes of the...
and successor systems, the term is "fixed", and pages may be long-term fixed, or may be short-term fixed. Control structures are often long-term fixed (measured in wall-clock time, i.e., time measured in seconds, rather than time measured in less than one second intervals) whereas I/O buffers are usually short-term fixed (usually measured in significantly less than wall-clock time, possibly for a few milliseconds). Indeed, the OS has a special facility for "fast fixing" these short-term fixed data buffers (fixing which is performed without resorting to a time-consuming Supervisor Call instruction). Additionally, the OS has yet another facility for converting an application from being long-term fixed to being fixed for an indefinite period, possibly for days, months or even years (however, this facility implicitly requires that the application firstly be swapped-out, possibly from preferred-memory, or a mixture of preferred- and non-preferred memory, and secondly be swapped-in to non-preferred memory where it resides for the duration, however long that might be; this facility utilizes a documented Supervisor Call instruction).
Virtual-real operation
In OS/VS1OS/VS1
Operating System/Virtual Storage 1, or OS/VS1,was an IBM mainframe computer operating system designed to be run on IBM System/370 hardware....
and similar OSes, some parts of systems memory are managed in virtual-real mode, where every virtual address corresponds to a real address, specifically interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
mechanisms, paging supervisor and tables in older systems, and application programs using non-standard I/O management. For example, IBM's z/OS has 3 modes (virtual-virtual, virtual-real and virtual-fixed).
Thrashing
When paging is used, a problem called "thrashing" can occur, in which the computer spends an unsuitable amount of time swapping pages to and from a backing store, hence slowing down useful work. Adding real memory is the simplest response, but improving application design, scheduling, and memory usage can help.Segmented virtual memory
Some systems, such as the Burroughs B5500, do not use paging; instead, they use segmentationSegmentation (memory)
Memory segmentation is the division of computer memory into segments or sections. Segments or sections are also used in object files of compiled programs when they are linked together into a program image, or when the image is loaded into memory...
, dividing virtual address spaces into variable-length segments. A virtual address here consists of a segment number and an offset within the segment. The Intel 80286
Intel 80286
The Intel 80286 , introduced on 1 February 1982, was a 16-bit x86 microprocessor with 134,000 transistors. Like its contemporary simpler cousin, the 80186, it could correctly execute most software written for the earlier Intel 8086 and 8088...
supports a similar segmentation scheme as an option, but it is rarely used. Segmentation and paging can be used together by dividing each segment into pages; systems with this memory structure, such as Multics
Multics
Multics was an influential early time-sharing operating system. The project was started in 1964 in Cambridge, Massachusetts...
and IBM System/38, are usually paging-predominant, segmentation providing memory protection.
In the Intel 80386
Intel 80386
The Intel 80386, also known as the i386, or just 386, was a 32-bit microprocessor introduced by Intel in 1985. The first versions had 275,000 transistors and were used as the central processing unit of many workstations and high-end personal computers of the time...
and later IA-32
IA-32
IA-32 , also known as x86-32, i386 or x86, is the CISC instruction-set architecture of Intel's most commercially successful microprocessors, and was first implemented in the Intel 80386 as a 32-bit extension of x86 architecture...
processors, the segments reside in a 32-bit
32-bit
The range of integer values that can be stored in 32 bits is 0 through 4,294,967,295. Hence, a processor with 32-bit memory addresses can directly access 4 GB of byte-addressable memory....
linear, paged address space. Segments can be moved in and out of that space; pages there can "page" in and out of main memory, providing two levels of virtual memory; few if any operating systems do so, instead using only paging. Early non-hardware-assisted x86 virtualization
X86 virtualization
In computing, x86 virtualization is the facility that allows multiple operating systems to simultaneously share x86 processor resources in a safe and efficient manner, a facility generically known as hardware virtualization...
solutions combined paging and segmentation because x86 paging offers only two protection domains whereas a VMM / guest OS / guest applications stack needs three. The difference between paging and segmentation systems is not only about memory division; segmentation is visible to user processes, as part of memory model semantics. Hence, instead of memory that looks like a single large vector, it is structured into multiple spaces.
This difference has important consequences; a segment is not a page with variable length or a simple way to lengthen the address space. Segmentation that can provide a single-level memory model in which there is no differentiation between process memory and file system consists of only a list of segments (files) mapped into the process's potential address space.
This is not the same as the mechanisms provided by calls such as mmap
Mmap
In computing, mmap is a POSIX-compliant Unix system call that maps files or devices into memory. It is a method of memory-mapped file I/O. It naturally implements demand paging, because initially file contents are not entirely read from disk and do not use physical RAM at all...
and Win32's MapViewOfFile, because inter-file pointers do not work when mapping files into semi-arbitrary places. In Multics, a file (or a segment from a multi-segment file) is mapped into a segment in the address space, so files are always mapped at a segment boundary. A file's linkage section can contain pointers for which an attempt to load the pointer into a register or make an indirect reference through it causes a trap. The unresolved pointer contains an indication of the name of the segment to which the pointer refers and an offset within the segment; the handler for the trap maps the segment into the address space, puts the segment number into the pointer, changes the tag field in the pointer so that it no longer causes a trap, and returns to the code where the trap occurred, re-executing the instruction that caused the trap. This eliminates the need for a linker completely and works when different processes map the same file into different places in their private address spaces.
See also
- Computer memoryComputer memoryIn computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...
- Memory addressMemory addressA digital computer's memory, more specifically main memory, consists of many memory locations, each having a memory address, a number, analogous to a street address, at which computer programs store and retrieve, machine code or data. Most application programs do not directly read and write to...
- Address spaceAddress spaceIn computing, an address space defines a range of discrete addresses, each of which may correspond to a network host, peripheral device, disk sector, a memory cell or other logical or physical entity.- Overview :...
- Virtual address spaceVirtual address spaceVirtual address space is a memory mapping mechanism available in modern operating systems such as OpenVMS, UNIX, Linux, and Windows NT...
- Address space
- CPU designCPU designCPU design is the design engineering task of creating a central processing unit , a component of computer hardware. It is a subfield of electronics engineering and computer engineering.- Overview :CPU design focuses on these areas:...
- Page (computing)Page (computing)A page, memory page, or virtual page is a fixed-length contiguous block of virtual memory that is the smallest unit of data for the following:* memory allocation performed by the operating system for a program; and...
- Page tablePage tableA page table is the data structure used by a virtual memory system in a computer operating system to store the mapping between virtual addresses and physical addresses. Virtual addresses are those unique to the accessing process...
- PagingPagingIn computer operating systems, paging is one of the memory-management schemes by which a computer can store and retrieve data from secondary storage for use in main memory. In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called...
- Working setWorking setPeter Denning defines “the working set of information W of a process at time t to be the collection of information referenced by the process during the process time interval ”. Typically the units of information in question are considered to be memory pages...
- Memory management unitMemory management unitA memory management unit , sometimes called paged memory management unit , is a computer hardware component responsible for handling accesses to memory requested by the CPU...
- Cache algorithmsCache algorithmsIn computing, cache algorithms are optimizing instructions – algorithms – that a computer program or a hardware-maintained structure can follow to manage a cache of information stored on the computer...
- Page replacement algorithmPage replacement algorithmIn a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out when a page of memory needs to be allocated...
- Page table
- Segmentation (memory)Segmentation (memory)Memory segmentation is the division of computer memory into segments or sections. Segments or sections are also used in object files of compiled programs when they are linked together into a program image, or when the image is loaded into memory...
- System/38System/38The System/38 was a midrange computer server platform manufactured and sold by the IBM Corporation. The system offered a number of innovative features, and was the brainchild of IBM engineer Dr. Frank Soltis...
- System/38
- Memory managementMemory managementMemory management is the act of managing computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed. This is critical to the computer system.Several...
- Memory allocation
- Protected modeProtected modeIn computing, protected mode, also called protected virtual address mode, is an operational mode of x86-compatible central processing units...
, an x86X86 architectureThe term x86 refers to a family of instruction set architectures based on the Intel 8086 CPU. The 8086 was launched in 1978 as a fully 16-bit extension of Intel's 8-bit based 8080 microprocessor and also introduced segmentation to overcome the 16-bit addressing barrier of such designs...
mode that allows for virtual memory.
Further reading
- Hennessy, John L.; and Patterson, David A.; Computer Architecture, A Quantitative Approach (ISBN 1-55860-724-2)