When a program needs more memory than is physically present, the memory management layer of the operating system is invoked, usually by means of a special interrupt generated by the processor itself. The operating system must allocate additional memory to the program before allowing it to proceed.
The simplest solution is to divide our physical memory into a number of logical pages. When a program requires memory it is allocated a number of pages. This can happen both when it is initially loaded or if it needs additional memory at a later stage. If all the available pages are already in use the memory management system looks for a page that it can reclaim. This is normally done by choosing the page which has memory the longest (the least recently loaded approach) or which has not been used for the longest time (the least recently used approach).
When a suitable page has been identified, it is written out to a special system file on the hard disk, the swap file and the space freed is allocated to the program which requested an additional page. This process is known as swapping, and gives programs access to a virtually unlimited amount of virtual memory. If a page which has been swapped out is required again by a program, the memory manager is again triggered by the processor and can swap the required page back into memory.
Unfortunately, neither the least recently loaded approach, nor the least recently used approach is perfect. A page may have been in memory for a long time because it is used frequently, so if it is swapped out it may need to be swapped in again almost immediately. Similarly, a page may not have been used for some time, because it is near the end of a sequence of pages which are within a loop. This can also lead to it being swapped in again almost as soon as it is swapped out.
How does a program know where to find a specific page? Hardware, either within the processor or in a special chip called a Memory Management Unit (MMU), automatically translates the logical addresses used by programs into the physical addresses where the information is actually stored. The set of physical memory locations is known as the memory space and the set of virtual memory locations is known as the address space.
Mapping between the address space and the memory space is carried out by means of a page table which is held in a special, protected area of memory. When the program issues an address (the memory location it wants to access) to the processor, it is split into two parts – the page number, and an offset within that page. The MMU uses the page number to look up the page table.
The page table entry gives the physical page number where the page is loaded, along with additional information, such as when the page was last used, whether it has been modified, and whether it is actually present in memory at the moment. If it is not currently present, another page must be swapped out to make way for it.