The disk caches examined in previous chapters used RAM as an extension of the disk; the goal was to improve system response time and the solution was to reduce the number of disk accesses. In this chapter, we introduce an opposite approach called swapping , in which the kernel uses some space on disk as an extension of RAM. Swapping is transparent to the programmer: once the swapping areas are properly installed and activated, the processes may run under the assumption that they have all the physical memory available that they can address, never knowing that some of their pages are stored away and retrieved again as needed.
Disk caches enhance system performance at the expense of free RAM, while swapping extends the amount of addressable memory at the expense of access speed. Thus, disk caches are “good” and desirable, while swapping should be regarded as some sort of last resort to be used whenever the amount of free RAM becomes too scarce.
We start by defining swapping in Section 16.1. Then we describe in Section 16.2 the main data structures introduced by Linux to implement swapping. We discuss the swap cache and the low-level functions that transfer pages between RAM and swap areas, and vice versa. The two crucial sections are Section 16.5, where we describe the procedure used to select a page to be swapped out to disk, and Section 16.6, where we explain how a page stored in a swap area is read back into RAM when the need occurs.
This chapter effectively concludes our discussion of memory management. Just one topic remains to be covered—namely, page frame reclaiming; this is done in the last section, which is related only in part to swapping. With so many disk caches around, including the swap cache, all the available RAM could eventually end up in these caches and no more free RAM would be left. We shall see how the kernel prevents this by monitoring the amount of free RAM and by freeing pages from the caches or from the process address spaces, as the need occurs.
Swapping serves two main purposes:
To expand the address space that is effectively usable by a process
To expand the amount of dynamic RAM (i.e., what is left of the RAM once the kernel code and static data structures have been initialized) to load processes
Let’s give a few examples of how swapping benefits the user. The simplest is when a program’s data structures take up more space than the size of the available RAM. A swap area will allow this program to be loaded without any problem, and thus to run correctly. A more subtle example involves users who issue several commands that try to simultaneously run large applications that require a lot of memory. If no swap area is active, the system might reject requests to launch a new application. In contrast, a swap area allows the kernel to launch it, since some memory can be freed at the expense of some of the already existing processes without killing them.
These two examples illustrate the benefits, but also the drawbacks, of swapping. Simulation of RAM is not like RAM in terms of performance. Every access by a process to a page that is currently swapped out increases the process execution time by several orders of magnitude. In short, if performance is of great importance, swapping should be used only as a last resort; adding RAM chips still remains the best solution to cope with increasing computing needs. It is fair to say, however, that in some cases, swapping may be beneficial to the system as a whole. Long-running processes typically access only half of the page frames obtained. Even when some RAM is available, swapping unused pages out and using the RAM for disk cache can improve overall system performance.
Swapping has been around for many years. The first Unix system kernels monitored the amount of free memory constantly. When it became less than a fixed threshold, they performed some swapping out. This activity consisted of copying the entire address space of a process to disk. Conversely, when the scheduling algorithm selected a swapped-out process, the whole process was swapped in from disk.
This approach was abandoned by modern Unix kernels, including Linux, mainly because process switches are quite expensive when they involve swapping in swapped-out processes. To compensate for the burden of such swapping activity, the scheduling algorithm must be very sophisticated: it must favor in-RAM processes without completely shutting out the swapped-out ones.
In
Linux, swapping is currently performed at the page level rather than
at the process address space level. This finer level of granularity
has been reached thanks to the inclusion of a hardware paging unit in
the CPU. Recall from Section 2.4.1 that
each Page Table entry includes a Present flag; the
kernel can take advantage of this flag to signal to the hardware that
a page belonging to a process address space has been swapped out.
Besides that flag, Linux also takes advantage of the remaining bits
of the Page Table entry to store the location of the swapped-out page
on disk. When a Page Fault exception occurs, the corresponding
exception handler can detect that the page is not present in RAM and
invoke the function that swaps the missing page in from the disk.
Much of the algorithm’s complexity is thus related to swapping out. In particular, four main issues must be considered:
Which kind of page to swap out
How to distribute pages in the swap areas
How to select the page to be swapped out
When to perform page swap out
Let’s give a short preview of how Linux handles these four issues before describing the main data structures and functions related to swapping.
Swapping applies only to the following kinds of pages:
Pages that belong to an anonymous memory region of a process (for instance, a User Mode stack)
Modified pages that belong to a private memory mapping of a process
Pages that belong to an IPC shared memory region (see Section 19.3.5)
The remaining kinds of pages are either used by the kernel or used to map files on disk. In the first case, they are ignored by swapping because this simplifies the kernel design; in the second case, the best swap areas for the pages are the files themselves.
Each swap area is organized into slots , where each slot contains exactly one page. When swapping out, the kernel tries to store pages in contiguous slots to minimize disk seek time when accessing the swap area; this is an important element of an efficient swapping algorithm.
If more than one swap area is used, things become more complicated. Faster swap areas—swap areas stored in faster disks—get a higher priority. When looking for a free slot, the search starts in the swap area that has the highest priority. If there are several of them, swap areas of the same priority are cyclically selected to avoid overloading one of them. If no free slot is found in the swap areas that have the highest priority, the search continues in the swap areas that have a priority next to the highest one, and so on.
When choosing pages for swap out, it would be nice to be able to rank them according to some criterion. Several Least Recently Used (LRU) replacement algorithms have been proposed and used in some kernels. The main idea is to associate a counter storing the age of the page with each page in RAM—that is, the interval of time elapsed since the last access to the page. The oldest page of the process can then be swapped out.
Some computer platforms provide sophisticated support for LRU
algorithms; for instance, the CPUs of some mainframes automatically
update the value of a counter included in each Page Table entry to
specify the age of the corresponding page. But 80 × 86
processors do not offer such a hardware feature, so Linux cannot use
a true LRU algorithm. However, when selecting a candidate for swap
out, Linux takes advantage of the Accessed flag
included in each Page Table entry, which is automatically set by the
hardware when the page is accessed. As we’ll see
later, this flag is set and cleared in a rather simplistic way to
keep pages from being swapped in and out too much.
Swapping out is useful when the kernel is dangerously low on memory. As the kernel’s first defense against critically low memory, it keeps a small reserve of free page frames that can be used only by the most critical functions. This turns out to be essential to avoid system crashes, which might occur when a kernel routine invoked to free resources is unable to obtain the memory area it needs to complete its task. To protect this reserve of free page frames, Linux may perform a swap out on the following occasions:
By a kernel thread denoted as kswapd that is activated periodically whenever the number of free page frames falls below a predefined threshold.
When a memory request to the buddy system (see Section 7.1.7) cannot be satisfied because the number of free page frames would fall below a predefined threshold.