Virtual memory 32354 226167106 2008-07-17T03:19:46Z 210.94.41.89 /* Paging supervisor */ {{otheruses4|the computer term|the TBN game show|Virtual Memory (game show)}} [[Image:VirtualMem01.png|thumb|250px|The program thinks it has a large range of contiguous addresses; but in reality the parts it is currently using are scattered around [[RAM]], and the inactive parts are saved in a disk file.]] [[Virtual memory]] is a [[computer]] system technique which gives an application program the impression that it has contiguous working memory, while in fact it may be physically fragmented and may even overflow on to disk storage. Systems that use this technique make programming of large applications easier and use real physical memory (e.g. [[RAM]]) more efficiently than those without virtual memory. Note that "virtual memory" is not just "using disk space to extend physical memory size". Extending memory is a normal consequence of using virtual memory techniques, but can be done by other means such as [[overlay (programming)|overlay]]s or swapping programs and their data completely out to disk while they are inactive. The definition of "virtual memory" is based on tricking programs into thinking they are using large blocks of ''contiguous'' addresses. All modern general-purpose computer [[operating system]]s use virtual memory techniques for ordinary applications, such as word processors, spreadsheets, multimedia players, accounting, etc. Few older operating systems, such as [[DOS]] of the 1980s, or those for the [[mainframe computer|mainframes]] of the 1960s, had virtual memory functionality - notable exceptions being the [[Atlas Computer (Manchester)|Atlas]] and [[B5000]]. [[Embedded system]]s and other special-purpose computer systems which require very fast, very consistent response time do not generally use virtual memory. ==Implementation techniques== ===Paged virtual memory=== Almost all implementations of virtual memory divide the [[virtual address space]] of an application program into [[page (computing)|page]]s; a page is a block of contiguous virtual memory addresses. Pages are usually at least 4K [[byte]]s in size, and systems with large virtual address ranges or large amounts of real memory (e.g. [[RAM]]) generally use larger page sizes. ====Page tables==== Almost all implementations use [[page table]]s to translate the virtual addresses seen by the application program into [[physical address]]es (also referred to as "real addresses") used by the hardware to process instructions. Each entry in a page table contains the starting virtual address of the page--either the real memory address at which the page is actually stored, or an indicator that the page is currently held in a disk file (if the system uses disk files to let applications use amounts of virtual memory which exceed real memory). Systems can have one page table for the whole system or a separate page table for each application. If there is only one, different applications which are [[multiprogramming|running at the same time]] share a single virtual address space, i.e. they use different parts of a single range of virtual addresses. Systems which use multiple page tables provide multiple virtual address spaces - concurrent applications think they are using the same range of virtual addresses, but their separate page tables redirect to different real addresses. ====Paging==== [[Demand paging |Paging]] is the process of saving inactive virtual memory pages to disk and restoring them to real memory when required. Most virtual memory systems enable programs to use virtual address ranges which in total exceed the amount of real memory (e.g. [[RAM]]). To do this they use disk files to save virtual memory pages which are not currently active, and restore them to real memory when they are needed. Pages are not necessarily restored to the same real addresses from which they were saved - applications are aware only of virtual addresses. Usually when a page is going to be restored to real memory, the real memory already contains another virtual memory page which will be saved to disk before the restore takes place. ====Dynamic address translation==== When a [[CPU]] fetches an instruction located at a particular virtual address or, while executing an instruction, fetches data from a particular virtual address or stores data to a particular virtual address, the virtual address must be translated to the corresponding physical address. This is done by a hardware component, sometimes called a [[memory management unit]], which looks up the real address (from the page table) corresponding to a virtual address and passes the real address to the parts of the [[CPU]] which execute instructions. If the page tables indicate that the virtual memory page is not currently in real memory, the hardware raises a [[page fault]] [[exception]] (special internal signal) which invokes the paging supervisor component of the [[operating system]] (see below). ====Paging supervisor==== This part of the operating system creates and manages the page tables. If the dynamic address translation hardware raises a page fault exception, the paging supervisor searches the page file(s) (on disk) for the page containing the required virtual address, reads it into real physical memory, updates the page tables to reflect the new location of the virtual address and finally tells the dynamic address translation mechanism to start the search again. Usually all of the real physical memory is already in use and the paging supervisor must first save an area of real physical memory to disk and update the page table to say that the associated virtual addresses are no longer in real physical memory but saved on disk. Paging supervisors generally save and overwrite areas of real physical memory which have been [[Cache algorithms |least recently used]], because these are probably the areas which are used least often. So every time the dynamic address translation hardware matches a virtual address with a real physical memory address, it must put a time-stamp in the page table entry for that virtual address. ====Permanently resident pages==== All virtual memory systems have memory areas that are "pinned down", i.e. cannot be swapped out to secondary storage, for example: *[[Interrupt]] mechanisms generally rely on an array of pointers to the handlers for various types of interrupt ([[I/O]] completion, [[timer]] event, program error, [[page fault]], etc.). If the pages containing these pointers or the code that they invoke were pageable, interrupt-handling would become even more complex and time-consuming; and it would be especially difficult in the case of page fault interrupts. *The page tables are usually not pageable. *[[Data buffer]]s that are accessed outside of the CPU, for example by peripheral devices that use [[direct memory access]] (DMA) or by [[I/O channel]]s. Usually such devices and the [[Bus (computing) | buses]] (connection paths) to which they are attached use physical memory addresses rather than virtual memory addresses. Even on buses with an [[IOMMU]], which is a special [[memory management unit]] that can translate virtual addresses used on an I/O bus to physical addresses, the transfer cannot be stopped if a page fault occurs and then restarted when the page fault has been processed. So pages containing locations to which or from which a peripheral device is transferring data are either permanently pinned down or pinned down while the transfer is in progress. *Timing-dependent kernel/application areas cannot tolerate the varying response time caused by paging. =====Virtual=real operation===== In [[MVS]], [[z/OS]], and similar OSes, some parts of the systems memory are managed in virtual=real mode, where every virtual address corresponds to a real address. Those are: * [[interrupt]] mechanisms * paging supervisor and page tables * all [[data buffer]]s accessed by [[I/O channel]]s{{fact|date=November 2007}} * application programs which use non-standard methods of managing I/O and therefore provide their own buffers and communicate directly with peripherals (programs that create their own [[channel command word]]s). In IBM's early virtual memory operating systems virtual=real mode was the only way to "pin down" pages. z/OS has 3 modes, V=V (virtual=virtual; fully pageable), V=R and V=F (virtual = fixed, i.e. "pinned down" but with DAT operating).<ref name="IBMzOSConcepts">{{ cite web | title=z/OS Basic Skills Information Center: z/OS Concepts | url=http://publib.boulder.ibm.com/infocenter/zoslnctr/v1r7/topic/com.ibm.zconcepts.doc/zconcepts.pdf }}</ref> ===Segmented virtual memory=== Some systems, such as the [[Burroughs large systems]], do not use paging to implement virtual memory. Instead, they use [[segmentation (memory)|segmentation]], so that an application's virtual address space is divided into variable-length segments. A virtual address consists of a segment number and an offset within the segment. Memory is still physically addressed with a single number (called ''absolute'' or ''linear'' address). To obtain it, the processor looks up the segment number in a segment table to find a segment descriptor.<ref>{{cite book|url=http://computer-refuge.org/bitsavers/pdf/burroughs/B5000_5500_5700/5000-21005_B5000_operChar.pdf|title=The Operational Characteristics of the Processors for the Burroughs B5000|pp.2-3,2-4,3-2 through 3-4, 4-1 through 4-3|accessdate=2007-11-13}}</ref> The segment descriptor contains a flag indicating whether the segment is present in main memory and, if it is, the address in main memory of the beginning of the segment (segment's ''[[base address|base]]'' address) and the length of the segment. It checks whether the offset within the segment is less than the length of the segment and, if it isn't, an interrupt is generated. If a segment is not present in main memory, a hardware interrupt is raised to the operating system, which may try to read the segment into main memory, or to ''swap in''. The operating system might have to remove other segments (''swap out'') from main memory in order to make room in main memory for the segment to be read in. Notably, the [[Intel 80286]] supported a similar segmentation scheme as an option, but it was unused by most operating systems. It is possible to combine segmentation and paging, usually dividing each segment into pages. In systems that combine them, such as [[Multics]] and the [[IBM System/38]] and [[IBM System i]] machines, virtual memory is usually implemented with paging, with segmentation used to provide memory protection.<ref>{{cite book|url=http://computer-refuge.org/bitsavers/pdf/ge/GE-645/GE-645_SystemMan_Jan68.pdf|title=GE-645 System Manual|pages=pp21-30|date=January 1968|accessdate=2007-11-13}}</ref><ref>{{cite web|author=[[Fernando J. Corbató|F. J. Corbató]], [[Victor A. Vyssotsky|V. A. Vyssotsky]]|title=Introduction and Overview of the Multics System|url=http://www.multicians.org/fjcc1.html|accessdate=2007-11-13}}</ref><ref>{{cite web|author=E. L. Glaser, J. F. Couleur, G. A. Oliver|title=System Design of a Computer for Time Sharing Applications|url=http://www.multicians.org/fjcc2.html}}</ref> With the [[Intel 80386]] and later [[IA-32]] processors, the segments reside in a [[32-bit]] linear paged address space, so segments can be moved into and out of that linear address space, and pages in that linear address space can be moved in and out of main memory, providing two levels of virtual memory; however, few if any operating systems do so. Instead, they only use paging. The difference between virtual memory implementations using pages and using segments is not only about the memory division with fixed and variable sizes, respectively. In some systems, e.g. [[Multics]], or later [[System/38]] and [[Prime Computer|Prime]] machines, the segmentation was actually visible to the user processes, as part of the semantics of a memory model. In other words, instead of a process just having a memory which looked like a single large vector of bytes or words, it was more structured. This is different from using pages, which doesn't change the model visible to the process. This had important consequences. A segment wasn't just a "page with a variable length", or a simple way to lengthen the address space (as in [[Intel 80286]]). In Multics, the segmentation was a very powerful mechanism that was used to provide a single-level virtual memory model, in which there was no differentiation between "process memory" and "file system" - a process' active address space consisted only a list of segments (files) which were mapped into its potential address space, both code and data. <ref>{{Citation | last = Bensoussan | first = A. | last2 = Clingen | first2 = C. T. | date = May 1972 | year = 1972 | title = The Multics Virtual Memory: Concepts and Design | journal = Communications of the ACM | volume = 15 | issue = 5 | pages = 308–318 | url = http://www.multicians.org/multics-vm.html | doi = 10.1145/355602.361306 }}</ref> It is not the same as the later [[mmap]] function in Unix, because inter-file pointers don't work when mapping files into semi-arbitrary places. Multics had such addressing mode built into most instructions. In other words it could perform relocated inter-segment references, thus eliminating the need for a [[linker]] completely.<ref name="denning"/> This also worked when different processes mapped the same file into different places in their private address spaces.<ref>{{Citation | first = E.I. | last = Organick | title = The Multics System: An Examination of Its Structure | publisher = MIT Press | year = 1972 }}</ref> ==Avoiding thrashing== All implementations need to avoid a problem called "[[thrashing_(computer_science)|thrashing]]", where the computer spends too much time shuffling blocks of virtual memory between real memory and disks, and therefore appears to work slower. Better design of application programs can help, but ultimately the only cure is to install more real memory. For more information see [[Paging]]. ==History== In the 1940s and 1950s, before the development of a virtual memory, all larger programs had to contain logic for managing two-level storage (primary and secondary, today's analogies being RAM and hard disk), such as [[Overlay (programming)|overlaying]] techniques. Programs were responsible for moving overlays back and forth from secondary storage to primary. The main reason for introducing virtual memory was therefore not simply to extend primary memory, but to make such an extension as easy to use for programmers as possible.<ref name="denning">{{ cite journal | authorlink = Peter J. Denning | last = Denning | first = Peter | title = Before Memory Was Virtual | journal = In the Beginning: Recollections of Software Pioneers | year = 1997 | url = http://cs.gmu.edu/cne/pjd/PUBS/bvm.pdf }}</ref> Many systems already had the ability to divide the memory between multiple programs (required for [[multiprogramming]] and [[computer multitasking|multiprocessing]]), provided for example by "base and bounds registers" on early models of the [[PDP-10]], without providing virtual memory. That gave each application a private address space starting at an address of 0, with an address in the private address space being checked against a bounds register to make sure it's within the section of memory allocated to the application and, if it is, having the contents of the corresponding base register being added to it to give an address in main memory. This is a simple form of [[segmentation (memory)|segmentation]] without virtual memory. Virtual memory was developed in approximately 1959–1962, at the [[University of Manchester]] for the [[Atlas Computer]], completed in 1962.<ref>http://www.computer50.org/kgill/atlas/atlas.html Atlas design includes virtual memory</ref> However, [[Bearbeiten von Fritz-Rudolf Güntsch | Fritz-Rudolf Güntsch]], one of Germany's pioneering computer scientists and later the developer of the [[Telefunken]] TR 440 mainframe, claims to have invented the concept in 1957 in his doctoral dissertation ''Logischer Entwurf eines digitalen Rechengerätes mit mehreren asynchron laufenden Trommeln und automatischem Schnellspeicherbetrieb'' (''Logic Concept of a Digital Computing Device with Multiple Asynchronous Drum Storage and Automatic Fast Memory Mode''). In 1961, [[Burroughs Corporation|Burroughs]] released the [[B5000]], the first commercial computer with virtual memory.<ref>http://web.mac.com/joynerian/iWeb/Ian%20Joyner/Burroughs.html Ian Joyner on Burroughs B5000 </ref><ref>{{Citation | first = Harvey G. | last = Cragon | title = Memory Systems and Pipelined Processors | publisher = Jones and Bartlett Publishers | pages = 113 | year = 1996 | url = http://books.google.com/books?id=q2w3JSFD7l4C | isbn = 0867204745 }}</ref> It used [[segmentation (memory)|segmentation]] rather than [[paging]]. Like many technologies in the history of computing, virtual memory was not accepted without challenge. Before it could be implemented in mainstream operating systems, many models, experiments, and theories had to be developed to overcome the numerous problems. Dynamic address translation required a specialized, expensive, and hard to build hardware, moreover initially it slightly slowed down the access to memory.<ref name="denning"/> There were also worries that new system-wide algorithms of utilizing secondary storage would be far less effective than previously used application-specific ones. By [[1969]] the debate over virtual memory for commercial computers was over.<ref name="denning"/> An [[IBM]] research team led by David Sayre showed that the virtual memory overlay system consistently worked better than the best manually controlled systems. Possibly the first [[minicomputer]] to introduce virtual memory was the Norwegian [[NORD-1]]. During the 1970s, other minicomputers implemented virtual memory, notably [[VAX]] models running [[OpenVMS|VMS]]. Virtual memory was introduced to the x86 architecture with the [[protected mode]] of the [[Intel 80286]] processor. At first it was done with [[segment swapping]], which became inefficient with larger segments. The [[Intel 80386]] introduced support for paging underneath the existing [[Segmentation (memory)|segmentation]] layer. The page fault exception could be chained with other exceptions without causing a [[double fault]]. == See also == * [[Physical memory]] and its [[physical address]] * [[Memory address]] ** [[Address space]] ** [[Virtual address space]] * [[CPU design]] * [[Page (computing)]] ** [[Page table]] ** [[Paging]] ** [[Working set]] ** [[Memory management unit]] ** [[Cache algorithms]] ** [[Page replacement algorithm]] * [[Segmentation (memory)]] ** [[System/38]] * [[Memory management]] * [[Memory allocation]] * [[Protected mode]], a [[x86 architecture|x86]]'s name of virtual memory addressing ==References== {{reflist|2}} * John L. Hennessy, David A. Patterson, ''Computer Architecture, A Quantitative Approach'' (ISBN 1-55860-724-2) * Virtual Memory Secrets by Murali == External links == *[http://linux-mm.org/ Linux Memory Management] *[http://gnulinuxclub.org/index.php?option=com_content&task=view&id=161&Itemid=32 Linux Kernel Mailing List Discussion] *Pointers to [http://web-cat.cs.vt.edu/AlgovizWiki/VirtualMemory virtual memory visualizations] *[http://msdn2.microsoft.com/en-us/library/ms810616.aspx The Virtual-Memory Manager in Windows NT] {{FOLDOC}} [[Category:Virtual memory]] [[ar:ذاكرة افتراضية]] [[be-x-old:Віртуальная памяць]] [[ca:Memòria virtual]] [[cs:Virtuální paměť]] [[da:Virtuel hukommelse]] [[de:Virtuelle Speicherverwaltung]] [[es:Memoria virtual]] [[eu:Alegiazko memoria]] [[fa:حافظه مجازی]] [[fr:Mémoire virtuelle]] [[gl:Memoria virtual]] [[ko:가상 메모리]] [[id:Memori virtual]] [[it:Memoria virtuale]] [[he:זיכרון וירטואלי]] [[lt:Virtualioji atmintis]] [[hu:Virtuális memória]] [[nl:Virtueel geheugen]] [[ja:仮想記憶]] [[pl:Pamięć wirtualna]] [[pt:Memória virtual]] [[ru:Виртуальная память]] [[simple:Virtual memory]] [[sk:Virtuálna pamäť]] [[sl:Navidezni pomnilnik]] [[fi:Näennäismuisti]] [[sv:Virtuellt minne]] [[tr:Sanal bellek]] [[zh:虚拟内存]]