Paging

From Wikipedia, the free encyclopedia

Jump to: navigation, search
 This article may require cleanup to meet Wikipedia's quality standards.
Please improve this article if you can. (October 2007)
This article is about computer virtual memory. For the wireless communication devices, see pager and radio paging. Bank switching is also sometimes referred to as paging.

In computer operating systems that have their main memory divided into pages, a paging, sometimes called swapping, is a transfer of pages between main memory and an auxiliary store, such as hard disk drive.[1] Paging is an important part of virtual memory implemention in most contemporary general-purpose operating systems, allowing to easily use disk storage for data that do not fit into physical RAM. Paging is usually implemented as a task built into the kernel of the operating system.

Contents

[edit] Overview

The Main functions of paging are performed when a program tries to access pages that do not currently reside in RAM, a situation causing page fault:
  1. Handles the page fault, in a manner invisible to the causing program, and takes control.
  2. Determines the location of the data in auxiliary storage.
  3. Determines the page frame in RAM to use as a container for the data.
  4. If a page currently residing in chosen frame has been modified since loading (if it is dirty), writes the page to auxiliary storage.
  5. Loads the requested data into the available page.
  6. Returns control to the program, transparently retrying the instruction that caused page fault.

The need to reference memory at a particular address arises from two main sources:

  • Processor trying to load and execute a program's instructions itself.
  • Data being accessed by a program's instruction.

In step 3, when a page has to be loaded and all existing pages in RAM are currently in use, one of the existing pages must be swapped with the requested new page. The paging system must determine the page to swap by choosing a one that is least likely to be needed within a short time. There are various page replacement algorithms that try to answer such issue.

Most operating systems use the least recently used (LRU) page replacement algorithm. The theory behind LRU is that the least recently used page is the most likely one not to be needed shortly; when a new page is needed, the least recently used page is discarded. This algorithm is most often correct but not always: e.g. a sequential process moves forward through memory and never again accesses the most recently used page.

Most programs that become active reach a steady state in their demand for memory locality both in terms of instructions fetched and data being accessed. This steady state is usually much less than the total memory required by the program. This steady state is sometimes referred to as the working set: the set of memory pages that are most frequently accessed.

Virtual memory systems work most efficiently when the ratio of the working set to the total number of pages that can be stored in RAM is low enough to minimize the number of page faults. A program that works with huge data structures will sometimes require a working set that is too large to be efficiently managed by the page system resulting in constant page faults that drastically slow down the system. This condition is referred to as thrashing: a page is swapped out and then accessed causing frequent faults.

An interesting characteristic of thrashing is that as the working set grows, there is very little increase in the number of faults until the critical point, when faults go up dramatically and majority of system's processing power is spent on handling them.

[edit] Terminology differences - paging versus swapping

Historically, paging sometimes also referred simply to memory allocation scheme using fixed-length pages as opposed to variable-length segments, and without implicit suggestion that virtual memory technique is employed at all or that those pages are transferred to disk.[2] [3] Such usage is rare today.

Some modern systems use the term swapping along with paging. Historically, swapping referred to moving from/to secondary storage a whole program at a time, in a scheme known as roll-in/roll-out. [4] [5] In 1960s, after the concept of virtual memory was introduced—in two variants, either using segments or pages—and swapping was applied to moving, respectively, either segments or pages, between disk and memory. Today with the virtual memory mostly based on pages, not segments, swapping became a fairly close synonym of paging, although with one difference.

In many popular systems, there is a concept known as page cache, of using the same single mechanism for both virtual memory and disk caching. A page may be then transferred to or from any ordinary disk file, not necessarily a dedicated space. In some of such systems, notably Unix-like including Linux, swapping only refers to virtual memory scope and paging to both. Page in is transferring a page from the disk to RAM. Page out is transferring a page from RAM to the disk. But swap in and out only refer to transferring pages between RAM and special, virtual memory dedicated, swap space or swap file, and not any other place on disk.

On the other hand, Microsoft systems from Windows NT line very rarely use the term swapping to differentiate from general paging, and call the dedicated secondary store just a page file.

[edit] Paging in Windows 3.0 line

Virtual memory has been a feature of Microsoft Windows since Windows 3.0 in 1990. Microsoft introduced virtual memory in response to the failures of Windows 1.0 and Windows 2.0, attempting to slash resource requirements for the operating system.

Confusion abounds about Microsoft's decision to refer to the swap file as "virtual memory". Novices unfamiliar with the concept accept this definition without question, and speak of adjusting Windows' virtual memory size. In fact every process has a fixed, unchangeable virtual memory size, usually 2 GiB. The user has only an option to change disk capacity dedicated to paging.

Windows 3.x creates a hidden file named 386SPART.PAR or WIN386.SWP for use as a swap file. It is generally found in the root directory, but it may appear elsewhere (typically in the WINDOWS directory). Its size depends on how much swap space the system has (a setting selected by the user under Control Panel → Enhanced under "Virtual Memory".) If the user moves or deletes this file, a blue screen will appear the next time Windows is started, with the error message "The permanent swap file is corrupt". The user will be prompted to choose whether or not to delete the file (whether or not it exists).

Windows 95 uses a similar file, and the settings for it are located under Control Panel → System → Performance tab → Virtual Memory. Windows automatically sets the size of the page file to start at 1.5× the size of physical memory, and expand up to 3× physical memory if necessary. If a user runs memory-intensive applications on a system with low physical memory, it is preferable to manually set these sizes to a value higher than default.

[edit] Paging in Windows NT line

In NT-based versions of Windows (such as Windows 2000 and Windows XP), the file used for paging is named pagefile.sys. The default location of the page file is in the root directory of the partition where Windows is installed. Windows can be configured to use free space on any available drives for page files.

[edit] Fragmentation of the page file

Occasionally,when the page file is gradually expanded, it can become heavily fragmented and cause performance problems. The common advice given to avoid this problem is to set a single "locked" page file size so that Windows will not resize it. Other people believe this to be problematic in the case that a Windows application requests more memory than the total size of physical and virtual memory. In this case, requests to allocate memory fail, which may cause the programs making the request (including system processes) to crash. Supporters of this view will note that the page file is rarely read or written in sequential order, so the performance advantage of having a completely sequential page file is minimal. However, it is generally agreed that a large page file will allow use of memory-heavy applications, and there is no penalty except that more disk space is used.

Defragmenting the page file is also occasionally recommended to improve performance when a Windows system is chronically using much more memory than its total physical memory. Although this can help slightly, performance concerns are much more effectively dealt with by adding more physical memory.

[edit] Swapping in Linux

In Linux, like in most other Unix-like operating systems, it is common to use a whole partition of a hard disk for swapping. However, with the 2.6 Linux kernel, swap files are just as fast[6] as swap partitions. The administrative flexibility of swap files outweighs that of partitions; since modern high capacity hard drives can remap physical sectors, no partition is guaranteed to be contiguous.

Linux supports using a virtually unlimited number of swapping devices, each of which can be assigned a priority. When the operating system needs to swap pages out of physical memory, it uses the highest-priority device with free space. If multiple devices are assigned the same priority, they are used in a fashion similar to level 0 RAID arrangements. This provides improved performance as long as the devices can be accessed efficiently in parallel. Therefore, care should be taken assigning the priorities. For example, swaps located on the same physical disk should not be used in parallel, but in order ranging from the fastest to the slowest (i.e.: the fastest having the highest priority).

Recently, some experimental improvement to the 2.6 Linux kernel have been made by Con Kolivas, published in his popular -ck patchset[7]. The improvement, called "swap prefetch", employs a mechanism of prefetching previously swapped pages back to physical memory even before they are actually needed, as long as the system is relatively idle (so as not to impair performance) and there is available physical memory to use. This applies to a situation when a "heavy" application has been temporarily used, causing other processes to swap out. After it is closed, both freeing large area of memory and reducing disk load, prefetch of other processes starts, reducing their initial user response time. [8]

[edit] Tuning swapping performance

The backing store for a virtual memory operating system is typically many magnitudes slower than RAM. Therefore it is desirable to reduce or eliminate swapping, where practical. Some operating systems offer settings to influence the kernel's decisions.

  1. Linux offers the /proc/sys/vm/swappiness parameter, which changes the balance between swapping out runtime memory, as opposed to dropping pages from the system page cache.
  2. Windows 2000, XP, and Vista offer the DisablePagingExecutive registry setting, which controls whether user and kernel mode drivers, as well kernel mode OS code and data is eligible for paging out.

[edit] Tuning swap space size

In some older virtual memory operating systems, space in swap backing store is reserved when programs allocate memory for runtime data. OS vendors typically issue guidelines about how much swap space should be allocated. 1.5 times the installed RAM is a typical number. With a large amount of RAM, the disk space needed for the backing store can be very large. Newer versions of these operating systems attempt to solve this problem: for example, some HP-UX kernels offer a tunable swapmem_on that controls whether RAM can be used for memory reservations. In systems with sufficient RAM, this significantly reduces the needed space allocation for the backing store.

[edit] See also

[edit] References

  1. ^ Belzer, Jack; Holzman, Albert G. & Kent, Allen, eds. (1981), "Virtual memory systems", Encyclopedia of computer science and technology, vol. 14, CRC Press, pp. 32, ISBN 0824722140, <http://books.google.com/books?id=KUgNGCJB4agC&printsec=frontcover>
  2. ^ Deitel, Harvey M. (1983), An Introduction to Operating Systems, Addison-Wesley, pp. 181, 187, ISBN 0201144735
  3. ^ Belzer, Jack; Holzman, Albert G. & Kent, Allen, eds. (1981), "Operating systems", Encyclopedia of computer science and technology, vol. 11, CRC Press, pp. 433, ISBN 0824722612, <http://books.google.com/books?id=uTFirmDlSL8C&printsec=frontcover>
  4. ^ Belzer, Jack; Holzman, Albert G. & Kent, Allen, eds. (1981), "Operating systems", Encyclopedia of computer science and technology, vol. 11, CRC Press, pp. 442, ISBN 0824722612, <http://books.google.com/books?id=uTFirmDlSL8C&printsec=frontcover>
  5. ^ Cragon, Harvey G. (1996), Memory Systems and Pipelined Processors, Jones and Bartlett Publishers, pp. 109, ISBN 0867204745, <http://books.google.com/books?id=q2w3JSFD7l4C>
  6. ^ http://lkml.org/lkml/2006/5/29/3
  7. ^ http://kernel.kolivas.org Con Kolivas' 2.6 Linux Kernel patchset
  8. ^ http://ck.wikia.com/wiki/SwapPrefetch SwapPrefetch description on ck kernel wiki. Retrieved 18-09-2007.

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Paging"
Personal tools