Paging
Starting in the late 1960s and early 1970s, there arose the problem that software programs and their data would take up more memory space than was available in the primary storage (RAM). It became necessary to think of ways to break up such a larger program and its data into parts, with less-relevant parts being held in some auxiliary storage. If such additional memory is available, such as in the form of secondary storage on disk, then there are three major ways of doing this:
- Overlays--sections of the application code or data are stored on secondary storage (typically hard drives), and the application has to load them whenever required. This was a common method in personal computers under DOS right up to the early 1990s, but has the disadvantage that applications are slowed down by drive access speeds.
- Swapping--this is slightly similar to the use of overlays, but involves the process scheduler; a whole process, along with its data, is swapped on to disk (or other medium) when necessary, and is swapped back, with the required context-switching by the CPU, when it needs to be run again. Swapping has been there since the 1960s, and is still used in many systems.
- Virtual memory--this is a technique where the apparent memory available to the process or application is expanded seamlessly, without it being made aware of the dirty details involved. Hence, a "virtual memory" is created which is all that the process sees; this virtual memory may be thought of as a magnified memory made available to the process through the action of other components.
The last technique, that of virtual memory, is most pertinent in modern-day architectures and operating systems. It works as follows. A "page" is a small fixed-size block of memory; a "segment" is a variable-size block of memory, usually larger in size. Architectures are commonly either "paged" or "segmented" depending on which they use, but it is not unknown for there to be architectures where a segment is further subdivided into pages. On paged systems, there is a "virtual address" for each page in memory, which is the only address that the process needs to know about. The hardware (specifically, the memory management unit or MMU) takes care of locating the page physically given the virtual address.
If a page requested by the process currently running is already in main memory, well and good. If it is not in main memory, then a "page fault" is said to occur, and it needs to be brought into memory--this is done by use of a special piece of system software called a "page fault trap service routine." Of course, the process will not be given the page as quickly as it would be if the page were already in main memory, but this is of little consequence as the process never has to bother with the details of how the pages it asks for are obtained, and it only sees a virtual memory of more pages than the main memory itself can intrinsically support.
If the pages are only copied on to main memory when they are needed by a process, then we have "demand paging." Pages are then moved into main memory only by the occurrence of page faults. This is a very basic technique, but in many cases, it is possible to do better. For that we use "anticipatory paging," where a page is brought into main memory in anticipation of its possible use. For example, when a certain page has been loaded into main memory because of a page fault, other pages which contain related blocks of data or application code, may be needed shortly. Hence, some software systems even allow user programs to explicitly ask for certain pages to be brought into main memory even before they are referenced.
A question now arises—how does one know which page that is already in memory to replace, when a new one is brought in? Some of the common page replacement techniques are:
- Belady's optimal replacement policy--this is the optimal page replacement policy, unimplementable in practice, which requires precise knowledge of when a page will be needed in future; under this method, one has to know which page will not be required for the longest time in future, and replace it with the one being moved in. Lacking a crystal ball for always knowing which pages will be needed in future, we have to come up with various reasonable guesses, so this method cannot be used in its stated form.
- Random--just pick any page in main memory, without attempting to assess its importance or significance, and replace it with the one being moved. This is obviously the least sophisticated page-replacement method there could be (and it would be really hard for any method to do worse).
- FIFO (first in, first out)--pick the page that has been in main memory the longest, and replace it. This method sounds reasonable, but empirical studies have shown that it is nearly as bad as random replacement--the mere fact that a page has been in main memory a long time does not mean it is useless and can be swapped; in fact, it is possible it should there a long time because it is very useful.
- LRU (least recently used)--pick the page in main memory that has not been used for the longest time, and remove it. This is a sensible policy, but unfortunately it requires that the MMU do a fairly complex job of bookkeeping in order to keep track of times of accesses to pages. Various approximations to LRU replacement are found to be good in practice, and empirical studies have shown that it is the policy that comes the closest to realizing the performance of the impossible Belady policy. That is, the fact that a page has not been used for the longest time is a good indicator generally that it is not going to be used for the longest time to come.
This is the complete article, containing 982 words
(approx. 3 pages at 300 words per page).
