# Difference between revisions of "Paging (memory management)"

In computer operating systems, paging is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory.[1] In this scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. Paging is an important part of virtual memory implementations in modern operating systems, using secondary storage to let programs exceed the size of available physical memory.

For simplicity, main memory is called "RAM" (abbreviated from "random-access memory") and secondary storage is called "disk" (a shorthand for "hard disk drive"), but the concepts do not depend on whether these terms apply literally to a specific computer system.

Memory management scheme

## History

The first memory pages were concepts in computer architecture, regardless of whether a page moved between RAM and disk.[2] [3] For example, on the PDP-8, 7 of the instruction bits comprised a memory address that selected one of 128 (2^7) words. This zone of memory was called a page. This use of the term is now rare. In the 1960s, swapping was an early virtual memory technique. An entire program would be swapped out (or rolled out) from RAM to disk, and another one would be swapped in (or rolled in).[4][5] A swapped-out program would be current but its execution would be suspended while its RAM was in use by another program.

A program might include multiple overlays that occupy the same memory at different times. Overlays are not a method of paging RAM to disk but merely of minimizing the program's use of RAM. Subsequent architectures used memory segmentation, and individual program segments became the units exchanged between disk and RAM. A segment was the program's entire code segment or data segment, or sometimes other large data structures. These segments had to be contiguous when resident in RAM, requiring additional computation and movement to remedy fragmentation.[6]

The invention of the page table let the processor operate on arbitrary pages anywhere in RAM as a seemingly contiguous logical address space. These pages became the units exchanged between disk and RAM.

## The algorithm for determining outdated pages

When allocating space for a new page is necessary to delete any page that is currently located in the memory. Terms of replacement pages are used for deciding what kind of page should be removed from memory. The ideal candidate is a "dead" page that no longer need anyone else (for example, refers to the consummation of the process). If no such pages in memory (or their number is insufficient), used usually local or global page replacement: Rule local replacement allocates each process or group of interrelated processes of a certain number of pages. If the process needs a new page, it has to replace one of their own. Rule global page replacement page you can take any process, using global selection criteria. To implement this approach, you need to select the criteria by which a decision will be made on pages stored in memory. The most frequently useded searching criteria are:

• Least Recently Used. Removed those pages are accessed most for a long time. It is believed that in the future these pages will be a minimum of references.
• Last Recently Used. Deletes recently released pages. This includes the page just to complete the process.

## The swap algorithm

Description of the algorithm swap (swap) can be divided into three parts: the space management in the discharge device, unloading process of the main memory and swapping processes in main memory.

unloading device is a block type, which is a configurable section diska.Togda as usual kernel allocates space for files on the same block in a single operation, to unload the device space is allocated in groups of adjacent blocks. The space allocated to the files used in a static manner; since assignment scheme files under the operating space for a long period of time, its flexibility is understood in the sense of reducing the incidence of fragmentation and therefore the volume of unused space in the file system.

Allocation of space on the discharge device, in contrast, is temporary, to a large extent dependent on the scheduling mechanism processes. The process is placed on the unloading device eventually will come back to the main memory, freeing up space on the external device. Since time is a critical factor, and given the fact that the input and output of data in a single multiblock operation is faster than several single-block operation, the kernel allocates for unloading device continuous space, without taking into account the possible fragmentation.

Since the discharge space allocation unit circuit differs from the circuit used for the file system data structures that record space must also be different. Free space in the file system is described by a linked list of free blocks, which can be accessed through the file system superblock, information about free space on the device is going to unload a table, referred to as "memory card". memory cards, in addition to discharging device used, and other system resources (for example, drivers for some devices), they make it possible to allocate memory device (in the form of adjacent blocks) in a first-appropriate.

Allocation algorithm using a memory card (malloc). Map kernel searches for the first available line containing the number of resource units is sufficient to satisfy the request. If the request covers all the number of units contained in the string line and removes the core condenses map (i.e. the map becomes smaller than one line). Otherwise, the kernel address and resets the number of remaining units in a row in accordance with the number of units allocated on demand. Here is the algorithm for allocation using memory cards:

    malloc algorithm     #allocation algorithm using memory card
input information:  (1) адрес:    #indicates the type of card used
(2) the required number of resource units:
output infomation me:  get address - in case of successful completion s
0 - otherwise
{
for (each card string)
{
if (the required number of resource units located in the card line)
{
if (number of required number = number of units in string)
dlte string from card;
otherwise
или
}
}
return (0);
}


Freeing resources, the kernel is looking for them in the appropriate place at the map. In this case there are three possibilities:

• Freed resources completely cover the gap in the memory card. In other words, they have contiguous addresses with addresses of resources lines immediately preceding and following that. In this case, the core incorporates the newly freed resources with the resources of these lines on a single line card.
• Freed resources partially close the gap in the memory card. If they have an address adjacent to the location of resources line immediately preceding or immediately following this (but not the addresses of the two lines), the kernel address value and resets the number of resources in the corresponding row based on the newly freed resources. The number of rows in the memory map remains unchanged.
• Freed resources partially close the gap in the memory card, but the addresses are not in contact with the addresses of any other map resources. The kernel creates a new row and inserts it in the appropriate place in the map.

In the traditional implementation of the UNIX system uses a single discharge device, but in the last editions of the version V has allowed the presence of a plurality of discharge devices. The kernel selects unloading device in a "circular list" provided that the device has a sufficient contiguous address space. Administrators can dynamically create and delete from the discharge system of the device. If the unloading device is removed from the system, the kernel does not unload the data on it; if the same data is spooled to the device to be removed, it is first emptied and only after the release of a device belonging to the space unit can be removed from the system.

## Thrashing

Main article: Thrashing (computer science)

After completing initialization, most programs operate on a small number of code and data pages compared to the total memory the program requires. The pages most frequently accessed are called the working set.

When the working set is a small percentage of the system's total number of pages, virtual memory systems work most efficiently and an insignificant amount of computing is spent resolving page faults. As the working set grows, resolving page faults remains manageable until the growth reaches a critical point. Then faults go up dramatically and the time spent resolving them overwhelms time spent on the computing the program was written to do. This condition is referred to as thrashing. Thrashing occurs on a program that works with huge data structures, as its large working set causes continual page faults that drastically slow down the system. Satisfying page faults may require freeing pages that will soon have to be re-read from disk. "Thrashing" is also used in contexts other than virtual memory systems; for example, to describe cache issues in computing or silly window syndrome in networking.

A worst case can be imagined on IBM System/370 and comparable mainframes. An execute instruction crossing a page boundary could point to a move instruction that also crosses a page boundary, which is set to move data from a source that crosses a page boundary to a target that crosses a page boundary. This single instruction references eight pages; if not all are in RAM, it will cause a page fault. If the operating system could not allocate eight pages to this program, then remedying the page fault would discard another page the instruction needs, and any restart of the instruction would fault again.

To decrease excessive paging and resolve thrashing problems, a user can increase the number of pages available per program, either by running fewer programs concurrently or increasing the amount of RAM in the computer.

## Sharing

In multi-programming or in a multi-user environment, many users may execute the same program, written so that its code and data are in separate pages. To minimize use of RAM, all users share a single copy of the program. Each process's page table is set up so that the pages that address code point to the single shared copy, while the pages that address data point to different physical pages for each process.

## Implementations

### Ferranti Atlas

The first computer to support paging was the Atlas,[7][8][9] jointly developed by Ferranti, the University of Manchester and Plessey. The machine had an associative (content-addressable) memory with one entry for each 512 word page. The Supervisor[10] handled non-equivalence interruptions and managed the transfer of pages between core and drum in order to provide a one-level store[11] to programs.

### Windows 3.x and Windows 9x

Paging has been a feature of Microsoft Windows since Windows 3.0 in 1990. 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, Windows 98 and Windows Me use 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.

### Windows NT

The file used for paging in the Windows NT family is 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 pagefiles. It is required, however, for the boot partition (i.e. the drive containing the Windows directory) to have a pagefile on it if the system is configured to write either kernel or full memory dumps after a Blue Screen of Death. Windows uses the paging file as temporary storage for the memory dump. When the system is rebooted, Windows copies the memory dump from the pagefile to a separate file and frees the space that was used in the pagefile.[12]

#### Fragmentation

In the default configuration of Windows, the pagefile is allowed to expand beyond its initial allocation when necessary. If this happens gradually, it can become heavily fragmented which can potentially cause performance problems.[13] The common advice given to avoid this is to set a single "locked" pagefile size so that Windows will not expand it. However, the pagefile only expands when it has been filled, which, in its default configuration, is 150% the total amount of physical memory. Thus the total demand for pagefile-backed virtual memory must exceed 250% of the computer's physical memory before the pagefile will expand.

The fragmentation of the pagefile that occurs when it expands is temporary. As soon as the expanded regions are no longer in use (at the next reboot, if not sooner) the additional disk space allocations are freed and the pagefile is back to its original state.

Locking a pagefile size can be problematic if a Windows application requests more memory than the total size of physical memory and the pagefile, leading to failed requests to allocate memory that may cause applications and system processes to fail. Also, the pagefile is rarely read or written in sequential order, so the performance advantage of having a completely sequential page file is minimal. However, a large pagefile generally allows use of memory-heavy applications, with no penalties beside using more disk space. While a fragmented pagefile may not be an issue by itself, fragmentation of a variable size page file will over time create a number of fragmented blocks on the drive, causing other files to become fragmented. For this reason, a fixed-size contiguous pagefile is better, providing that the size allocated is large enough to accommodate the needs of all applications.

The required disk space may be easily allocated on systems with more recent specifications (i.e. a system with 3 GB of memory having a 6 GB fixed-size pagefile on a 750 GB disk drive, or a system with 6 GB of memory and a 16 GB fixed-size pagefile and 2 TB of disk space). In both examples the system is using about 0.8% of the disk space with the pagefile pre-extended to its maximum.

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. This view ignores the fact that, aside from the temporary results of expansion, the pagefile does not become fragmented over time. In general, performance concerns related to pagefile access are much more effectively dealt with by adding more physical memory.

### Unix and Unix-like systems

Unix systems, and other Unix-like operating systems, use the term "swap" to describe both the act of moving memory pages between RAM and disk, and the region of a disk the pages are stored on. In some of those systems, it is common to dedicate an entire partition of a hard disk to swapping. These partitions are called swap partitions. Many systems have an entire hard drive dedicated to swapping, separate from the data drive(s), containing only a swap partition. A hard drive dedicated to swapping is called a "swap drive" or a "scratch drive" or a "scratch disk". Some of those systems only support swapping to a swap partition; others also support swapping to files.

#### Linux

From the end-user perspective, swap files in versions 2.6.x and later of the Linux kernel are virtually as fast as swap partitions; the limitation is that swap files should be contiguously allocated on their underlying file systems. To increase performance of swap files, the kernel keeps a map of where they are placed on underlying devices and accesses them directly, thus bypassing the cache and avoiding filesystem overhead.[14][15] Regardless, Red Hat recommends swap partitions to be used.[16] When residing on HDDs, which are rotational magnetic media devices, one benefit of using swap partitions is the ability to place them on contiguous HDD areas that provide higher data throughput or faster seek time. However, the administrative flexibility of swap files can outweigh certain advantages of swap partitions. For example, a swap file can be placed on any mounted file system, can be set to any desired size, and can be added or changed as needed. Swap partitions are not as flexible; they cannot be enlarged without using partitioning or volume management tools, which introduce various complexities and potential downtimes.

The Linux kernel supports a virtually unlimited number of swap backends (devices or files), supporting at the same time assignment of backend priorities. When the kernel needs to swap pages out of physical memory, it uses the highest-priority backend with available free space. If multiple swap backends are assigned the same priority, they are used in a round-robin fashion (which is somewhat similar to RAID 0 storage layouts), providing improved performance as long as the underlying devices can be efficiently accessed in parallel.[17]

#### OS X

OS X uses multiple swap files. The default (and Apple-recommended) installation places them on the root partition, though it is possible to place them instead on a separate partition or device.[18]

### AmigaOS 4

AmigaOS 4.0 introduced a new system for allocating RAM and defragmenting physical memory. It still uses flat shared address space that cannot be defragmented. It is based on slab allocation method and paging memory that allows swapping. Paging was implemented in AmigaOS 4.1 but may lock up system if all physical memory is used up.[19] Swap memory could be activated and deactivated any moment allowing the user to choose to use only physical RAM.

## Performance

The backing store for a virtual memory operating system is typically many orders of magnitude slower than RAM. Additionally, using mechanical storage devices introduces delay, several milliseconds for a hard disk. Therefore, it is desirable to reduce or eliminate swapping, where practical. Some operating systems offer settings to influence the kernel's decisions.

• 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.
• Windows 2000, XP, and Vista offer the DisablePagingExecutive registry setting, which controls whether kernel-mode code and data can be eligible for paging out.
• Mainframe computers frequently used head-per-track disk drives or drums for page and swap storage to eliminate seek time, and several technologies[20] to have multiple concurrent requests to the same device in order to reduce rotational latency.
• Flash memory has a finite number of erase-write cycles (see Limitations of flash memory), and the smallest amount of data that can be erased at once might be very large (128 KiB for an Intel X25-M SSD [21]), seldom coinciding with pagesize. Therefore, flash memory may wear out quickly if used as swap space under tight memory conditions. On the attractive side, flash memory is practically delayless compared to hard disks, and not volatile as RAM chips. Schemes like ReadyBoost and Intel Turbo Memory are made to exploit these characteristics.

Many Unix-like operating systems (for example AIX, Linux and Solaris) allow using multiple storage devices for swap space in parallel, to increase performance.

### Swap space size

In some older virtual memory operating systems, space in swap backing store is reserved when programs allocate memory for runtime data. Operating system vendors typically issue guidelines about how much swap space should be allocated.

## Addressing limits on 32-bit hardware

Paging is one way of allowing the size of the addresses used by a process, which is the process's "virtual address space" or "logical address space", to be different from the amount of main memory actually installed on a particular computer, which is the physical address space.

### Main memory smaller than virtual memory

In most systems, the size of a process's virtual address space is much larger than the available main memory.[22] For example:

• The address bus that connects the CPU to main memory may be limited. The i386SX CPU's 32-bit internal addresses can address 4 GB, but it has only 24 pins connected to the address bus, limiting installed physical memory to 16 MB. There may be other hardware restrictions on the maximum amount of RAM that can be installed.
• The maximum memory might not be installed because of cost, because the model's standard configuration omits it, or because the buyer did not believe it would be advantageous.
• Sometimes not all internal addresses can be used for memory anyway, because the hardware architecture may reserve large regions for I/O or other features.

### Main memory the same size as virtual memory

A computer with true n-bit addressing may have 2^n addressable units of RAM installed. An example is a 32-bit x86 processor with 4  GB and without Physical Address Extension (PAE). In this case, the processor is able to address all the RAM installed and no more.

However, even in this case, paging can be used to create a virtual memory of over 4 GB. For instance, many programs may be running concurrently. Together, they may require more than 4 GB, but not all of it will have to be in RAM at once. A paging system makes efficient decisions on which memory to relegate to secondary storage, leading to the best use of the installed RAM.

Although the processor in this example cannot address RAM beyond 4 GB, the operating system may provide services to programs that envision a larger memory, such as files that can grow beyond the limit of installed RAM. The operating system lets a program manipulate data in the file arbitrarily, using paging to bring parts of the file into RAM when necessary.

### Main memory larger than virtual address space

A few computers have a main memory larger than the virtual address space of a process, such as the Magic-1,[22] some PDP-11 machines, and some systems using 32-bit x86 processors with Physical Address Extension. This nullifies a significant advantage of virtual memory, since a single process cannot use more main memory than the amount of its virtual address space. Such systems often use paging techniques to obtain secondary benefits:

• The "extra memory" can be used in the page cache to cache frequently used files and metadata, such as directory information, from secondary storage.
• If the processor and operating system support multiple virtual address spaces, the "extra memory" can be used to run more processes. Paging allows the cumulative total of virtual address spaces to exceed physical main memory.
• A process can store data in memory-mapped files on memory-backed file systems, such as the tmpfs file system or file systems on a RAM drive, and map files into and out of the address space as needed.

The size of the cumulative total of virtual address spaces is still limited by the amount of secondary storage available.

Cite error: Invalid <references> tag; parameter "group" is allowed only.
Use <references />, or <references group="..." />