Misplaced Pages

#978021

136-401: For simplicity, main memory is called "RAM" (an acronym of random-access memory ) and secondary storage is called "disk" (a shorthand for hard disk drive , drum memory or solid-state drive , etc.), but as with many aspects of computing, the concepts are independent of the technology used. Depending on the memory model , paged memory functionality is usually hardwired into a CPU/MCU by using

272-660: A Memory Management Unit (MMU) or Memory Protection Unit (MPU) and separately enabled by privileged system code in the operating system 's kernel . In CPUs implementing the x86 instruction set architecture (ISA) for instance, the memory paging is enabled via the CR0 control register . In the 1960s, swapping was an early virtual memory technique. An entire program or entire segment would be "swapped out" (or "rolled out") from RAM to disk or drum, and another one would be swapped in (or rolled in ). A swapped-out program would be current but its execution would be suspended while its RAM

408-427: A computer operating system that uses paging for virtual memory management , page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory ( page fault ) and a free page cannot be used to satisfy the allocation, either because there are none, or because

544-461: 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

680-475: A page frame in RAM, the processor treats this invalid memory reference as a page fault and transfers control from the program to the operating system. The operating system must: When all page frames are in use, the operating system must select a page frame to reuse for the page the program now needs. If the evicted page frame was dynamically allocated by a program to hold data, or if a program modified it since it

816-479: A bit called its mark. Initially, we set all pages as unmarked. During a stage (a period of operation or a sequence of requests) of page requests, we mark a page when it is first requested in this stage. A marking algorithm is such an algorithm that never pages out a marked page. If ALG is a marking algorithm with a cache of size k, and OPT is the optimal algorithm with a cache of size h, where h ≤ k {\displaystyle h\leq k} , then ALG

952-489: A displacement deferred addressing mode, where the longword containing the operand address crosses a page boundary, and the source and destination could both cross page boundaries. This single instruction references ten pages; if not all are in RAM, each will cause a page fault. As each fault occurs the operating system needs to go through the extensive memory management routines perhaps causing multiple I/Os which might include writing other process pages to disk and reading pages of

1088-563: A few dozen or few hundred bits of such memory could be provided. The first practical form of random-access memory was the Williams tube . It stored data as electrically charged spots on the face of a cathode-ray tube . Since the electron beam of the CRT could read and write the spots on the tube in any order, memory was random access. The capacity of the Williams tube was a few hundred to around

1224-421: A hard drive. This entire pool of memory may be referred to as "RAM" by many developers, even though the various subsystems can have very different access times , violating the original concept behind the random access term in RAM. Even within a hierarchy level such as DRAM, the specific row, column, bank, rank , channel, or interleave organization of the components make the access time variable, although not to

1360-441: A hot topic of research and debate in the 1960s and 1970s. That mostly ended with the development of sophisticated LRU (least recently used) approximations and working set algorithms. Since then, some basic assumptions made by the traditional page replacement algorithms were invalidated, resulting in a revival of research. In particular, the following trends in the behavior of underlying hardware and user-level software have affected

1496-530: A keystroke is not in main memory, then if the user enters a keystroke, the server will take one or more page faults, requiring those pages to read from swap before the keystroke can be processed, slowing the response to it. If those pages do not remain in memory, they will have to be faulted in again to handle the next keystroke, making the system practically unresponsive even if it's actually executing other tasks normally. macOS uses multiple swap files. The default (and Apple-recommended) installation places them on

SECTION 10

#1732779696979

1632-408: A lot of random writes, while SSDs do not have this problem. Certainly the default values work well in most workloads, but desktops and interactive systems for any expected task may want to lower the setting while batch processing and less interactive systems may want to increase it. When the system memory is highly insufficient for the current tasks and a large portion of memory activity goes through

1768-424: A memory capacity that is a power of two. Usually several memory cells share the same address. For example, a 4 bit "wide" RAM chip has four memory cells for each address. Often the width of the memory and that of the microprocessor are different, for a 32 bit microprocessor, eight 4 bit RAM chips would be needed. Often more addresses are needed than can be provided by a device. In that case, external multiplexors to

1904-437: A new page that has not been referenced. Clock is a more efficient version of FIFO than Second-chance because pages don't have to be constantly pushed to the back of the list, but it performs the same general function as Second-Chance. The clock algorithm keeps a circular list of pages in memory, with the "hand" (iterator) pointing to the last examined page frame in the list. When a page fault occurs and no empty frames exist, then

2040-412: A page fault. Some operating systems periodically look for pages that have not been recently referenced and then free the page frame and add it to the free page queue, a process known as "page stealing". Some operating systems support page reclamation ; if a program commits a page fault by referencing a page that was stolen, the operating system detects this and restores the page frame without having to read

2176-587: A page has been used. Thus, the page with the lowest counter can be swapped out when necessary. The main problem with NFU is that it keeps track of the frequency of use without regard to the time span of use. Thus, in a multi-pass compiler, pages which were heavily used during the first pass, but are not needed in the second pass will be favoured over pages which are comparably lightly used in the second pass, as they have higher frequency counters. This results in poor performance. Other common scenarios exist where NFU will perform similarly, such as an OS boot-up. Thankfully,

2312-462: A page to be modified yet not referenced, this happens when a class 3 page has its referenced bit cleared by the timer interrupt. The NRU algorithm picks a random page from the lowest category for removal. So out of the above four page categories, the NRU algorithm will replace a not-referenced, not-modified page if such a page exists. Note that this algorithm implies that a modified but not-referenced (within

2448-404: A portion of a computer's RAM, allowing it to act as a much faster hard drive that is called a RAM disk . A RAM disk loses the stored data when the computer is shut down, unless memory is arranged to have a standby battery source, or changes to the RAM disk are written out to a nonvolatile disk. The RAM disk is reloaded from the physical disk upon RAM disk initialization. Sometimes, the contents of

2584-517: A process incurs a page fault, a local page replacement algorithm selects for replacement some page that belongs to that same process (or a group of processes sharing a memory partition ). A global replacement algorithm is free to select any page in memory. Local page replacement assumes some form of memory partitioning that determines how many pages are to be assigned to a given process or a group of processes. Most popular forms of partitioning are fixed partitioning and balanced set algorithms based on

2720-555: A relatively slow ROM chip are copied to read/write memory to allow for shorter access times. The ROM chip is then disabled while the initialized memory locations are switched in on the same block of addresses (often write-protected). This process, sometimes called shadowing , is fairly common in both computers and embedded systems . As a common example, the BIOS in typical personal computers often has an option called "use shadow BIOS" or similar. When enabled, functions that rely on data from

2856-453: A similar and better algorithm exists, and its description follows. The not frequently used page-replacement algorithm generates fewer page faults than the least recently used page replacement algorithm when the page table contains null pointer values. The aging algorithm is a descendant of the NFU algorithm, with modifications to make it aware of the time span of use. Instead of just incrementing

SECTION 20

#1732779696979

2992-542: A single MOS transistor per capacitor. The first commercial DRAM IC chip, the 1K Intel 1103 , was introduced in October 1970. Synchronous dynamic random-access memory (SDRAM) was reintroduced with the Samsung KM48SL2000 chip in 1992. Early computers used relays , mechanical counters or delay lines for main memory functions. Ultrasonic delay lines were serial devices which could only reproduce data in

3128-458: A slow swap, the system can become practically unable to execute any task, even if the CPU is idle. When every process is waiting on the swap, the system is considered to be in swap death . Swap death can happen due to incorrectly configured memory overcommitment . The original description of the "swapping to death" problem relates to the X server . If code or data used by the X server to respond to

3264-429: 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

3400-469: A subset of the process virtual addresses to physical addresses. In addition, in most architectures the page table holds an "access" bit and a "dirty" bit for each page in the page table. The CPU sets the access bit when the process reads or writes memory in that page. The CPU sets the dirty bit when the process writes memory in that page. The operating system can modify the access and dirty bits. The operating system can detect accesses to memory and files through

3536-491: A switch that lets the control circuitry on the chip read the capacitor's state of charge or change it. As this form of memory is less expensive to produce than static RAM, it is the predominant form of computer memory used in modern computers. Both static and dynamic RAM are considered volatile , as their state is lost or reset when power is removed from the system. By contrast, read-only memory (ROM) stores data by permanently enabling or disabling selected transistors, such that

3672-410: A system with 6 GB of memory and a 16 GB fixed-size page file and 2 TB of disk space). In both examples, the system uses about 0.8% of the disk space with the page file 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

3808-525: A systemwide pool from which they can be recovered if not already re-used. FIFO is a conservative algorithm, so it is k k − h + 1 {\displaystyle {\tfrac {k}{k-h+1}}} -competitive. A modified form of the FIFO page replacement algorithm, known as the Second-chance page replacement algorithm, fares relatively better than FIFO at little cost for

3944-611: A thousand bits, but it was much smaller, faster, and more power-efficient than using individual vacuum tube latches. Developed at the University of Manchester in England, the Williams tube provided the medium on which the first electronically stored program was implemented in the Manchester Baby computer, which first successfully ran a program on 21 June, 1948. In fact, rather than the Williams tube memory being designed for

4080-431: A virtually unlimited number of swap backends (devices or files), and also supports assignment of backend priorities. When the kernel swaps 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

4216-434: Is k k − h + 1 {\displaystyle {\tfrac {k}{k-h+1}}} -competitive. The least recently used (LRU) page replacement algorithm, though similar in name to NRU, differs in the fact that LRU keeps track of page usage over a short period of time, while NRU just looks at the usage in the last clock interval. LRU works on the idea that pages that have been most heavily used in

Memory paging - Misplaced Pages Continue

4352-486: Is k k − h + 1 {\displaystyle {\tfrac {k}{k-h+1}}} -competitive. So every marking algorithm attains the k k − h + 1 {\displaystyle {\tfrac {k}{k-h+1}}} -competitive ratio. LRU is a marking algorithm while FIFO is not a marking algorithm. An algorithm is conservative, if on any consecutive request sequence containing k or fewer distinct page references,

4488-459: Is 60 ; setting it higher can cause high latency if cold pages need to be swapped back in (when interacting with a program that had been idle for example), while setting it lower (even 0) may cause high latency when files that had been evicted from the cache need to be read again, but will make interactive programs more responsive as they will be less likely to need to swap back cold pages. Swapping can also slow down HDDs further because it involves

4624-462: Is a Linux kernel parameter that controls the relative weight given to swapping out of runtime memory , as opposed to dropping pages from the system page cache , whenever a memory allocation request cannot be met from free memory. Swappiness can be set to a value from 0 to 200. A low value causes the kernel to prefer to evict pages from the page cache while a higher value causes the kernel to prefer to swap out "cold" memory pages. The default value

4760-406: 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 support more virtual memory than physical memory. For instance, many programs may be running concurrently. Together, they may require more physical memory than can be installed on

4896-544: Is a marking algorithm, so it is k k − h + 1 {\displaystyle {\tfrac {k}{k-h+1}}} -competitive. Random replacement algorithm replaces a random page in memory. This eliminates the overhead cost of tracking page references. Usually it fares better than FIFO, and for looping memory references it is better than LRU, although generally LRU performs better in practice. OS/390 uses global LRU approximation and falls back to random replacement when LRU performance degenerates, and

5032-615: Is a type of flip-flop circuit, usually implemented using FETs . This means that SRAM requires very low power when not being accessed, but it is expensive and has low storage density. A second type, DRAM, is based around a capacitor. Charging and discharging this capacitor can store a "1" or a "0" in the cell. However, the charge in this capacitor slowly leaks away, and must be refreshed periodically. Because of this refresh process, DRAM uses more power, but it can achieve greater storage densities and lower unit costs compared to SRAM. To be useful, memory cells must be readable and writable. Within

5168-423: 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 might occur on VAX processors. A single MOVL crossing a page boundary could have a source operand using a displacement deferred addressing mode, where the longword containing the operand address crosses a page boundary, and a destination operand using

5304-412: Is an algorithm that works as follows: when a page needs to be swapped in, the operating system swaps out the page whose next use will occur farthest in the future. For example, a page that is not going to be used for the next 6 seconds will be swapped out over a page that is going to be used within the next 0.4 seconds. This algorithm cannot be implemented in a general purpose operating system because it

5440-433: Is analogous to a prefetch input queue in a CPU. Swap prefetching will prefetch recently swapped-out pages if there are enough free pages for them. If a program ends, the operating system may delay freeing its pages, in case the user runs the same program again. The free page queue is a list of page frames that are available for assignment. Preventing this queue from being empty minimizes the computing necessary to service

5576-501: Is as follows: suppose the hardware has a 64-bit counter that is incremented at every instruction. Whenever a page is accessed, it acquires the value equal to the counter at the time of page access. Whenever a page needs to be replaced, the operating system selects the page with the lowest counter and swaps it out. Because of implementation costs, one may consider algorithms (like those that follow) that are similar to LRU, but which offer cheaper implementations. One important advantage of

Memory paging - Misplaced Pages Continue

5712-482: 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. The Linux kernel supports

5848-403: Is far more expensive than the dynamic RAM used for larger memories. Static RAM also consumes far more power. CPU speed improvements slowed significantly partly due to major physical barriers and partly because current CPU designs have already hit the memory wall in some sense. Intel summarized these causes in a 2005 document. First of all, as chip geometries shrink and clock frequencies rise,

5984-440: Is impossible to compute reliably how long it will be before a page is going to be used, except when all software that will run on a system is either known beforehand and is amenable to static analysis of its memory reference patterns, or only a class of applications allowing run-time analysis. Despite this limitation, algorithms exist that can offer near-optimal performance — the operating system keeps track of all pages referenced by

6120-419: Is more expensive to produce, but is generally faster and requires less dynamic power than DRAM. In modern computers, SRAM is often used as cache memory for the CPU . DRAM stores a bit of data using a transistor and capacitor pair (typically a MOSFET and MOS capacitor , respectively), which together comprise a DRAM cell. The capacitor holds a high or low charge (1 or 0, respectively), and the transistor acts as

6256-496: 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. In most systems, the size of a process's virtual address space is much larger than the available main memory. For example: A computer with true n -bit addressing may have 2 addressable units of RAM installed. An example

6392-517: Is rarely used in its unmodified form. This algorithm experiences Bélády's anomaly . In simple words, on a page fault, the frame that has been in memory the longest is replaced. FIFO page replacement algorithm is used by the OpenVMS operating system, with some modifications. Partial second chance is provided by skipping a limited number of entries with valid translation table references, and additionally, pages are displaced from process working set to

6528-489: Is reduced by the size of the shadowed ROMs. The ' memory wall is the growing disparity of speed between CPU and the response time of memory (known as memory latency ) outside the CPU chip. An important reason for this disparity is the limited communication bandwidth beyond chip boundaries, which is also referred to as bandwidth wall . From 1986 to 2000, CPU speed improved at an annual rate of 55% while off-chip memory response time only improved at 10%. Given these trends, it

6664-509: Is requested. (This is often in combination with pre-cleaning, which guesses which pages currently in RAM are not likely to be needed soon, and pre-writing them out to storage). When a page fault occurs, anticipatory paging systems will not only bring in the referenced page, but also other pages that are likely to be referenced soon. A simple anticipatory paging algorithm will bring in the next few consecutive pages even though they are not yet needed (a prediction using locality of reference ); this

6800-469: Is set. The setting of the bits is usually done by the hardware, although it is possible to do so on the software level as well. At a certain fixed time interval, a timer interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current timer interval are marked with a referenced bit. When a page needs to be replaced, the operating system divides the pages into four classes: Although it does not seem possible for

6936-459: 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 page file is back to its original state. Locking a page file size can be problematic if a Windows application requests more memory than the total size of physical memory and the page file, leading to failed requests to allocate memory that may cause applications and system processes to fail. Also,

SECTION 50

#1732779696979

7072-458: Is that by the time the precleaned page is actually selected for the replacement, the I/O will complete and the page will be clean. Precleaning assumes that it is possible to identify pages that will be replaced next . Precleaning that is too eager can waste I/O bandwidth by writing pages that manage to get re-dirtied before being selected for replacement. The (h,k)-paging problem is a generalization of

7208-406: Is the linked list method, which uses a linked list containing all the pages in memory. At the back of this list is the least recently used page, and at the front is the most recently used page. The cost of this implementation lies in the fact that items in the list will have to be moved about every memory reference, which is a very time-consuming process. Another method that requires hardware support

7344-423: Is the processor-memory performance gap, which can be addressed by 3D integrated circuits that reduce the distance between the logic and memory aspects that are further apart in a 2D chip. Memory subsystem design requires a focus on the gap, which is widening over time. The main method of bridging the gap is the use of caches ; small amounts of high-speed memory that houses recent operations and instructions nearby

7480-433: Is to set a single "locked" page file size so that Windows will not expand it. However, the page file only expands when it has been filled, which, in its default configuration, is 150% of the total amount of physical memory. Thus the total demand for page file-backed virtual memory must exceed 250% of the computer's physical memory before the page file will expand. The fragmentation of the page file that occurs when it expands

7616-474: Is used up. Swap memory could be activated and deactivated any moment allowing the user to choose to use only physical RAM. 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

7752-605: Is used, pages are loaded only when they are referenced. A program from a memory mapped file begins execution with none of its pages in RAM. As the program commits page faults, the operating system copies the needed pages from a file, e.g., memory-mapped file , paging file, or a swap partition containing the page data into RAM. Some systems use only demand paging —waiting until a page is actually requested before loading it into RAM. Other systems attempt to reduce latency by guessing which pages not in RAM are likely to be needed soon, and pre-loading such pages into RAM, before that page

7888-400: The k k − h + 1 {\displaystyle {\tfrac {k}{k-h+1}}} -competitive ratio. LRU, FIFO and CLOCK are conservative algorithms. There are a variety of page replacement algorithms: The theoretically optimal page replacement algorithm (also known as OPT, clairvoyant replacement algorithm, or Bélády's optimal page replacement policy)

8024-578: The Atanasoff–Berry Computer , the Williams tube and the Selectron tube . In 1966, Robert Dennard invented modern DRAM architecture for which there is a single MOS transistor per capacitor. While examining the characteristics of MOS technology, he found it was capable of building capacitors , and that storing a charge or no charge on the MOS capacitor could represent the 1 and 0 of a bit, while

8160-984: The IBM M44/44X and its MOS operating system (1964), the SDS 940 and the Berkeley Timesharing System (1966), a modified IBM System/360 Model 40 and the CP-40 operating system (1967), the IBM System/360 Model 67 and operating systems such as TSS/360 and CP/CMS (1967), the RCA 70/46 and the Time Sharing Operating System (1967), the GE 645 and Multics (1969), and the PDP-10 with added BBN -designed paging hardware and

8296-456: The Intel i860 processor used a random replacement policy (Rhodehamel 1989 ). The not frequently used (NFU) page replacement algorithm requires a counter, and every page has one counter of its own which is initially set to 0. At each clock interval, all pages that have been referenced within that interval will have their counter incremented by 1. In effect, the counters keep track of how frequently

SECTION 60

#1732779696979

8432-475: The TENEX operating system (1969). Those machines, and subsequent machines supporting memory paging, use either a set of page address registers or in-memory page tables to allow the processor to operate on arbitrary pages anywhere in RAM as a seemingly contiguous logical address space. These pages became the units exchanged between disk and RAM. When a process tries to reference a page not currently mapped to

8568-442: The working set model. The advantage of local page replacement is its scalability: each process can handle its page faults independently, leading to more consistent performance for that process. However global page replacement is more efficient on an overall system basis. Modern general purpose computers and some embedded processors have support for virtual memory . Each process has its own virtual address space. A page table maps

8704-432: The 1960s with bipolar memory, which used bipolar transistors . Although it was faster, it could not compete with the lower price of magnetic core memory. In 1957, Frosch and Derick manufactured the first silicon dioxide field-effect transistors at Bell Labs, the first transistors in which drain and source were adjacent at the surface. Subsequently, in 1960, a team demonstrated a working MOSFET at Bell Labs. This led to

8840-505: The BIOS's ROM instead use DRAM locations (most can also toggle shadowing of video card ROM or other ROM sections). Depending on the system, this may not result in increased performance, and may cause incompatibilities. For example, some hardware may be inaccessible to the operating system if shadow RAM is used. On some systems the benefit may be hypothetical because the BIOS is not used after booting in favor of direct hardware access. Free memory

8976-544: The Baby, the Baby was a testbed to demonstrate the reliability of the memory. Magnetic-core memory was invented in 1947 and developed up until the mid-1970s. It became a widespread form of random-access memory, relying on an array of magnetized rings. By changing the sense of each ring's magnetization, data could be stored with one bit stored per ring. Since every ring had a combination of address wires to select and read or write it, access to any memory location in any sequence

9112-465: The LRU algorithm is that it is amenable to full statistical analysis. It has been proven, for example, that LRU can never result in more than N-times more page faults than OPT algorithm, where N is proportional to the number of pages in the managed pool. On the other hand, LRU's weakness is that its performance tends to degenerate under many quite common reference patterns. For example, if there are N pages in

9248-584: The LRU pool, an application executing a loop over array of N + 1 pages will cause a page fault on each and every access. As loops over large arrays are common, much effort has been put into modifying LRU to work better in such situations. Many of the proposed LRU modifications try to detect looping reference patterns and to switch into suitable replacement algorithm, like Most Recently Used (MRU). A comparison of ARC with other algorithms (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) can be found in Megiddo & Modha 2004. LRU

9384-402: The MOS transistor could control writing the charge to the capacitor. This led to his development of a single-transistor DRAM memory cell. In 1967, Dennard filed a patent under IBM for a single-transistor DRAM memory cell, based on MOS technology. The first commercial DRAM IC chip was the Intel 1103 , which was manufactured on an 8   μm MOS process with a capacity of 1   kbit , and

9520-408: The R (referenced) bit is inspected at the hand's location. If R is 0, the new page is put in place of the page the "hand" points to, and the hand is advanced one position. Otherwise, the R bit is cleared, then the clock hand is incremented and the process is repeated until a page is replaced. This algorithm was first described in 1969 by Fernando J. Corbató . CLOCK is a conservative algorithm, so it

9656-489: The RAM comes in an easily upgraded form of modules called memory modules or DRAM modules about the size of a few sticks of chewing gum. These can be quickly replaced should they become damaged or when changing needs demand more storage capacity. As suggested above, smaller amounts of RAM (mostly SRAM) are also integrated in the CPU and other ICs on the motherboard , as well as in hard-drives, CD-ROMs , and several other parts of

9792-444: The RAM device, multiplexing and demultiplexing circuitry is used to select memory cells. Typically, a RAM device has a set of address lines A 0 , A 1 , . . . A n {\displaystyle A_{0},A_{1},...A_{n}} , and for each combination of bits that may be applied to these lines, a set of memory cells are activated. Due to this addressing, RAM devices virtually always have

9928-587: The SP95 memory chip for the System/360 Model 95 . Dynamic random-access memory (DRAM) allowed replacement of a 4 or 6-transistor latch circuit by a single transistor for each memory bit, greatly increasing memory density at the cost of volatility. Data was stored in the tiny capacitance of each transistor, and had to be periodically refreshed every few milliseconds before the charge could leak away. Toshiba 's Toscal BC-1411 electronic calculator , which

10064-420: The active process from disk. If the operating system could not allocate ten 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

10200-407: The algorithm will incur k or fewer page faults. If ALG is a conservative algorithm with a cache of size k, and OPT is the optimal algorithm with a cache of h ≤ k {\displaystyle h\leq k} , then ALG is k k − h + 1 {\displaystyle {\tfrac {k}{k-h+1}}} -competitive. So every conservative algorithm attains

10336-487: The amount of RAM in the computer. 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 RAM use, 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. Different programs might also use

10472-696: The cache and avoiding filesystem overhead. 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. Swappiness

10608-405: The computer system. In addition to serving as temporary storage and working space for the operating system and applications, RAM is used in numerous other ways. Most modern operating systems employ a method of extending RAM capacity, known as "virtual memory". A portion of the computer's hard drive is set aside for a paging file or a scratch partition , and the combination of physical RAM and

10744-534: The contents back into RAM. The operating system may periodically pre-clean dirty pages: write modified pages back to disk even though they might be further modified. This minimizes the amount of cleaning needed to obtain new page frames at the moment a new program starts or a new data file is opened, and improves responsiveness. (Unix operating systems periodically use sync to pre-clean all dirty pages; Windows operating systems use "modified page writer" threads.) After completing initialization, most programs operate on

10880-474: The counters of pages referenced, putting equal emphasis on page references regardless of the time, the reference counter on a page is first shifted right (divided by 2), before adding the referenced bit to the left of that binary number. For instance, if a page has referenced bits 1,0,0,1,1,0 in the past 6 clock ticks, its referenced counter will look like this in chronological order: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Page references closer to

11016-448: The development of metal–oxide–semiconductor (MOS) memory by John Schmidt at Fairchild Semiconductor in 1964. In addition to higher speeds, MOS semiconductor memory was cheaper and consumed less power than magnetic core memory. The development of silicon-gate MOS integrated circuit (MOS IC) technology by Federico Faggin at Fairchild in 1968 enabled the production of MOS memory chips . MOS memory overtook magnetic core memory as

11152-408: The device are used to activate the correct device that is being accessed. RAM is often byte addressable, although it is also possible to make RAM that is word-addressable. One can read and over-write data in RAM. Many computer systems have a memory hierarchy consisting of processor registers , on- die SRAM caches, external caches , DRAM , paging systems and virtual memory or swap space on

11288-437: The dominant memory technology in the early 1970s. Integrated bipolar static random-access memory (SRAM) was invented by Robert H. Norman at Fairchild Semiconductor in 1963. It was followed by the development of MOS SRAM by John Schmidt at Fairchild in 1964. SRAM became an alternative to magnetic-core memory, but required six MOS transistors for each bit of data. Commercial use of SRAM began in 1965, when IBM introduced

11424-415: The drive, causing other files to become fragmented. For this reason, a fixed-size contiguous page file 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 page file on a 750 GB disk drive, or

11560-410: The extent that access time to rotating storage media or a tape is variable. The overall goal of using a memory hierarchy is to obtain the fastest possible average access time while minimizing the total cost of the entire memory system (generally, the memory hierarchy follows the access time with the fast CPU registers at the top and the slow hard drive at the bottom). In many modern personal computers,

11696-433: The fact that, aside from the temporary results of expansion, the page file does not become fragmented over time. In general, performance concerns related to page file access are much more effectively dealt with by adding more physical memory. Unix systems, and other Unix-like operating systems, use the term "swap" to describe the act of substituting disk space for RAM when physical RAM is full. In some of those systems, it

11832-435: The following means: Most replacement algorithms simply return the target page as their result. This means that if target page is dirty (that is, contains data that have to be written to the stable storage before page can be reclaimed), I/O has to be initiated to send that page to the stable storage (to clean the page). In the early days of virtual memory, time spent on cleaning was not of much concern, because virtual memory

11968-696: The form of integrated circuit (IC) chips with MOS (metal–oxide–semiconductor) memory cells . RAM is normally associated with volatile types of memory where stored information is lost if power is removed. The two main types of volatile random-access semiconductor memory are static random-access memory (SRAM) and dynamic random-access memory (DRAM). Non-volatile RAM has also been developed and other types of non-volatile memories allow random access for read operations, but either do not allow write operations or have other kinds of limitations. These include most types of ROM and NOR flash memory . The use of semiconductor RAM dates back to 1965 when IBM introduced

12104-412: The fundamental building block of computer memory . The memory cell is an electronic circuit that stores one bit of binary information and it must be set to store a logic 1 (high voltage level) and reset to store a logic 0 (low voltage level). Its value is maintained/stored until it is changed by the set/reset process. The value in the memory cell can be accessed by reading it. In SRAM, the memory cell

12240-519: The gap between RAM and hard disk speeds, although RAM continues to be an order of magnitude faster, with single-lane DDR5 8000MHz capable of 128 GB/s, and modern GDDR even faster. Fast, cheap, non-volatile solid state drives have replaced some functions formerly performed by RAM, such as holding certain data for immediate availability in server farms - 1 terabyte of SSD storage can be had for $ 200, while 1 TB of RAM would cost thousands of dollars. Page replacement algorithm In

12376-460: The goal of page replacement is to minimize total time waiting for memory, it has to take into account memory requirements imposed by other kernel sub-systems that allocate memory. As a result, page replacement in modern kernels ( Linux , FreeBSD , and Solaris ) tends to work at the level of a general purpose kernel memory allocator, rather than at the higher level of a virtual memory subsystem. Replacement algorithms can be local or global. When

12512-484: 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"

12648-416: The improvement. It works by looking at the front of the queue as FIFO does, but instead of immediately paging out that page, it checks to see if its referenced bit is set. If it is not set, the page is swapped out. Otherwise, the referenced bit is cleared, the page is inserted at the back of the queue (as if it were a new page) and this process is repeated. This can also be thought of as a circular queue. If all

12784-441: The kernel's decisions. Many Unix-like operating systems (for example AIX , Linux , and Solaris ) allow using multiple storage devices for swap space in parallel, to increase performance. 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. Paging

12920-452: The last timer interval) page is less important than a not-modified page that is intensely referenced. NRU is a marking algorithm, so it is k k − h + 1 {\displaystyle {\tfrac {k}{k-h+1}}} -competitive. The simplest page-replacement algorithm is a FIFO algorithm. The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm that requires little bookkeeping on

13056-545: The means of producing inductance within solid state devices, resistance-capacitance (RC) delays in signal transmission are growing as feature sizes shrink, imposing an additional bottleneck that frequency increases don't address. The RC delays in signal transmission were also noted in "Clock Rate versus IPC: The End of the Road for Conventional Microarchitectures" which projected a maximum of 12.5% average annual CPU performance improvement between 2000 and 2014. A different concept

13192-436: The memory cannot be altered. Writable variants of ROM (such as EEPROM and NOR flash ) share properties of both ROM and RAM, enabling data to persist without power and to be updated without requiring special equipment. ECC memory (which can be either SRAM or DRAM) includes special circuitry to detect and/or correct random faults (memory errors) in the stored data, using parity bits or error correction codes . In general,

13328-440: The memory dump. When the system is rebooted, Windows copies the memory dump from the page file to a separate file and frees the space that was used in the page file. In the default configuration of Windows, the page file 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. The common advice given to avoid this

13464-417: The model of paging problem: Let h,k be positive integers such that h ≤ k {\displaystyle h\leq k} . We measure the performance of an algorithm with cache of size h ≤ k {\displaystyle h\leq k} relative to the theoretically optimal page replacement algorithm . If h < k {\displaystyle h<k} , we provide

13600-467: The monolithic (single-chip) 16-bit SP95 SRAM chip for their System/360 Model 95 computer, and Toshiba used bipolar DRAM memory cells for its 180-bit Toscal BC-1411 electronic calculator , both based on bipolar transistors . While it offered higher speeds than magnetic-core memory , bipolar DRAM could not compete with the lower price of the then-dominant magnetic-core memory. In 1966, Dr. Robert Dennard invented modern DRAM architecture in which there's

13736-401: 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 (even if it does not exist). 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

13872-434: The number of free pages is lower than some threshold. When the page that was selected for replacement and paged out is referenced again it has to be paged in (read in from disk), and this involves waiting for I/O completion. This determines the quality of the page replacement algorithm: the less time waiting for page-ins, the better the algorithm. A page replacement algorithm looks at the limited information about accesses to

14008-410: The optimal page replacement algorithm with strictly less resource. The (h,k)-paging problem is a way to measure how an online algorithm performs by comparing it with the performance of the optimal algorithm, specifically, separately parameterizing the cache size of the online algorithm and optimal algorithm. Marking algorithms is a general class of paging algorithms. For each page, we associate it with

14144-443: The order it was written. Drum memory could be expanded at relatively low cost but efficient retrieval of memory items requires knowledge of the physical layout of the drum to optimize speed. Latches built out of triode vacuum tubes , and later, out of discrete transistors , were used for smaller and faster memories such as registers . Such registers were relatively large and too costly to use for large amounts of data; generally only

14280-430: 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, a large page file generally allows the use of memory-heavy applications, with no penalties besides using more disk space. While a fragmented page file may not be an issue by itself, fragmentation of a variable size page file will over time create several fragmented blocks on

14416-468: 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. 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

14552-600: The page frame least likely to be needed soon, often through the least recently used (LRU) algorithm or an algorithm based on the program's working set . To further increase responsiveness, paging systems may predict which pages will be needed soon, preemptively loading them into RAM before a program references them, and may steal page frames from pages that have been unreferenced for a long time, making them available. Some systems clear new pages to avoid data leaks that compromise security; some set them to installation defined or random values to aid debugging. When pure demand paging

14688-443: The pages have their referenced bit set, on the second encounter of the first page in the list, that page will be swapped out, as it now has its referenced bit cleared. If all the pages have their reference bit cleared, then second chance algorithm degenerates into pure FIFO. As its name suggests, Second-chance gives every page a "second-chance" – an old page that has been referenced is probably in use, and should not be swapped out over

14824-424: The pages provided by hardware, and tries to guess which pages should be replaced to minimize the total number of page misses, while balancing this with the costs (primary storage and processor time) of the algorithm itself. The page replacing problem is a typical online problem from the competitive analysis perspective in the sense that the optimal deterministic algorithm is known. Page replacement algorithms were

14960-571: The paging file form the system's total memory. (For example, if a computer has 2 GB (1024 B) of RAM and a 1 GB page file, the operating system has 3 GB total memory available to it.) When the system runs low on physical memory, it can " swap " portions of RAM to the paging file to make room for new data, as well as to read previously swapped information back into RAM. Excessive use of this mechanism results in thrashing and generally hampers overall system performance, mainly because hard drives are far slower than RAM. Software can "partition"

15096-403: The paging problem is measured using amortized analysis . The not recently used (NRU) page replacement algorithm is an algorithm that favours keeping pages in memory that have been recently used. This algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit

15232-407: The part of the operating system . The idea is obvious from the name – the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the oldest arrival in front. When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected. While FIFO is cheap and intuitive, it performs poorly in practical application. Thus, it

15368-464: The partition where Windows is installed. Windows can be configured to use free space on any available drives for page files. It is required, however, for the boot partition (i.e., the drive containing the Windows directory) to have a page file 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

15504-413: The past few instructions are most likely to be used heavily in the next few instructions too. While LRU can provide near-optimal performance in theory (almost as good as adaptive replacement cache ), it is rather expensive to implement in practice. There are a few implementation methods for this algorithm that try to reduce the cost yet keep as much of the performance as possible. The most expensive method

15640-555: The performance of page replacement algorithms: Requirements for page replacement algorithms have changed due to differences in operating system kernel architectures. In particular, most modern OS kernels have unified virtual memory and file system caches, requiring the page replacement algorithm to select a page from among the pages of both user program virtual address spaces and cached files. The latter pages have specific properties. For example, they can be locked, or can have write ordering requirements imposed by journaling . Moreover, as

15776-798: The present time have more impact than page references long ago. This ensures that pages referenced more recently, though less frequently referenced, will have higher priority over pages more frequently referenced in the past. Thus, when a page needs to be swapped out, the page with the lowest counter will be chosen. The following Python code simulates the aging algorithm. Counters V i {\displaystyle V_{i}} are initialized with 0 and updated as described above via V i ← ( R i ≪ ( k − 1 ) ) | ( V i ≫ 1 ) {\displaystyle V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)} , using arithmetic shift operators . In

15912-577: The processor, speeding up the execution of those operations or instructions in cases where they are called upon frequently. Multiple levels of caching have been developed to deal with the widening gap, and the performance of high-speed modern computers relies on evolving caching techniques. There can be up to a 53% difference between the growth in speed of processor and the lagging speed of main memory access. Solid-state hard drives have continued to increase in speed, from ~400 Mbit/s via SATA3 in 2012 up to ~7 GB/s via NVMe / PCIe in 2024, closing

16048-417: The program, and it uses those data to decide which pages to swap in and out on subsequent runs. This algorithm can offer near-optimal performance, but not on the first run of a program, and only if the program's memory reference pattern is relatively consistent each time it runs. Analysis of the paging problem has also been done in the field of online algorithms . Efficiency of randomized online algorithms for

16184-486: The root partition, though it is possible to place them instead on a separate partition or device. 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

16320-455: The same amount of time irrespective of the physical location of data inside the memory, in contrast with other direct-access data storage media (such as hard disks and magnetic tape ), where the time required to read and write data items varies significantly depending on their physical locations on the recording medium, due to mechanical limitations such as media rotation speeds and arm movement. In today's technology, random-access memory takes

16456-539: The same libraries. To save space, only one copy of the shared library is loaded into physical memory. Programs which use the same library have virtual addresses that map to the same pages (which contain the library's code and data). When programs want to modify the library's code, they use copy-on-write , so memory is only allocated when needed. Shared memory is an efficient means of communication between programs. Programs can share pages in memory, and then write and read to exchange data. The first computer to support paging

16592-435: The same type, simply because it takes longer for signals to traverse a larger circuit. Constructing a memory unit of many gibibytes with a response time of one clock cycle is difficult or impossible. Today's CPUs often still have a mebibyte of 0 wait state cache memory, but it resides on the same chip as the CPU cores due to the bandwidth limitations of chip-to-chip communication. It must also be constructed from static RAM, which

16728-515: The system, 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. Random-access memory Random-access memory ( RAM ; / r æ m / ) is a form of electronic computer memory that can be read and changed in any order, typically used to store working data and machine code . A random-access memory device allows data items to be read or written in almost

16864-400: The term RAM refers solely to solid-state memory devices (either DRAM or SRAM), and more specifically the main memory in most computers. In optical storage, the term DVD-RAM is somewhat of a misnomer since, it is not random access; it behaves much like a hard disc drive if somewhat slower. Aside, unlike CD-RW or DVD-RW , DVD-RAM does not need to be erased before reuse. The memory cell is

17000-558: The transistor leakage current increases, leading to excess power consumption and heat... Secondly, the advantages of higher clock speeds are in part negated by memory latency, since memory access times have not been able to keep pace with increasing clock frequencies. Third, for certain applications, traditional serial architectures are becoming less efficient as processors get faster (due to the so-called von Neumann bottleneck ), further undercutting any gains that frequency increases might otherwise buy. In addition, partly due to limitations in

17136-503: The underlying devices can be efficiently accessed in parallel. 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

17272-582: 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 . Ferranti 's Atlas , and the Atlas Supervisor developed at the University of Manchester , (1962), was the first system to implement memory paging. Subsequent early machines, and their operating systems, supporting paging include

17408-498: Was Samsung's 64   Mbit DDR SDRAM chip, released in June 1998. GDDR (graphics DDR) is a form of DDR SGRAM (synchronous graphics RAM), which was first released by Samsung as a 16   Mbit memory chip in 1998. The two widely used forms of modern RAM are static RAM (SRAM) and dynamic RAM (DRAM). In SRAM, a bit of data is stored using the state of a six- transistor memory cell , typically using six MOSFETs. This form of RAM

17544-493: Was expected that memory latency would become an overwhelming bottleneck in computer performance. Another reason for the disparity is the enormous increase in the size of memory since the start of the PC revolution in the 1980s. Originally, PCs contained less than 1 mebibyte of RAM, which often had a response time of 1 CPU clock cycle, meaning that it required 0 wait states. Larger memory units are inherently slower than smaller ones of

17680-462: Was first implemented on systems with full duplex channels to the stable storage, and cleaning was customarily overlapped with paging. Contemporary commodity hardware, on the other hand, does not support full duplex transfers, and cleaning of target pages becomes an issue. To deal with this situation, various precleaning policies are implemented. Precleaning is the mechanism that starts I/O on dirty pages that are (likely) to be replaced soon. The idea

17816-473: Was in use by another program; a program with a swapped-out segment could continue running until it needed that segment, at which point it would be suspended until the segment was swapped in. 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 RAM use. Subsequent architectures used memory segmentation , and individual program segments became

17952-410: Was introduced in 1965, used a form of capacitor-bipolar DRAM, storing 180-bit data on discrete memory cells , consisting of germanium bipolar transistors and capacitors. While it offered higher speeds than magnetic-core memory, bipolar DRAM could not compete with the lower price of the then dominant magnetic-core memory. Capacitors had also been used for earlier memory schemes, such as the drum of

18088-460: Was possible. Magnetic core memory was the standard form of computer memory until displaced by semiconductor memory in integrated circuits (ICs) during the early 1970s. Prior to the development of integrated read-only memory (ROM) circuits, permanent (or read-only ) random-access memory was often constructed using diode matrices driven by address decoders , or specially wound core rope memory planes. Semiconductor memory appeared in

18224-402: Was read into RAM (in other words, if it has become "dirty"), it must be written out to disk before being freed. If a program later references the evicted page, another page fault occurs and the page must be read back into RAM. The method the operating system uses to select the page frame to reuse, which is its page replacement algorithm , is important to efficiency. The operating system predicts

18360-433: Was released in 1970. The earliest DRAMs were often synchronized with the CPU clock (clocked) and were used with early microprocessors. In the mid-1970s, DRAMs moved to the asynchronous design, but in the 1990s returned to synchronous operation. In 1992 Samsung released KM48SL2000, which had a capacity of 16   Mbit . and mass-produced in 1993. The first commercial DDR SDRAM ( double data rate SDRAM) memory chip

18496-479: Was the supercomputer Atlas , jointly developed by Ferranti , the University of Manchester and Plessey in 1963. The machine had an associative ( content-addressable ) memory with one entry for each 512 word page. The Supervisor handled non-equivalence interruptions and managed the transfer of pages between core and drum in order to provide a one-level store to programs. Paging has been a feature of Microsoft Windows since Windows 3.0 in 1990. Windows 3.x creates

#978021