Backing Store

Backing Store

In our study of page replacement algorithms, we saw how a page is chosen for removal. We have not said much about where on the disk it is put when it is paged out. Let us now explain some of the problems related to disk management. The simplest algorithm for allocating page space on the disk is to have a special swap partition on the disk, or even better on a separate disk from the file system (to balance the I/O load). Most UNIX systems work like this. This partition does not have a normal file system on it, which removes all the overhead of converting offsets in files to block addresses. Instead, block numbers relative to the start of the partition are used throughout.

When the system is booted, this swap partition is empty and is represented in memory as a single entry giving its origin and size. In the simplest scheme, when the first process is started, a chunk of the partition area the size of the first process is reserved and the remaining area reduced by that amount. As new processes are started, they are allocated chunks of the swap partition equal in size to their core images. As they finish, their disk space is freed. The swap partition is managed as a list of free chunks.

Associated with each process is the disk address of its swap area, that is, where on the swap partition its image is kept. This information is kept in the process table. Calculating the address to write a page to becomes simple: just add the offset of the page within the virtual address space to the start of the swap area. On the other hand, before a process can start, the swap area must be initialized. One way is to copy the entire process image to the swap area, so that it can be brought in as required. The other is to load the complete process in memory and let it be paged out as required.

On the other hand, this simple model has a problem: processes can increase in size after starting. Although the program text is generally fixed, the data area can sometimes grow, and the stack can always grow. As a result, it may be better to reserve separate swap areas for the text, data, and stack and allow each of these areas to consist of more than one chunk on the disk.

The other extreme is to allocate nothing in advance and allocate disk space for each page when it is swapped out and deallocate it when it is swapped back in. Thus, processes in memory do not tie up any swap space. The disadvantage is that a disk address is required in memory to keep track of each page on disk. In other words, there must a table per process telling for each page on disk where it is. The two alternatives are illustrated in Figure 1.

Paging to a static swap area

In Figure 1(a), a page table with eight pages is shown. Pages 0, 3, 4, and 6 are in main memory. Pages 1, 2, 5, and 7 are on disk. The swap area on disk is as large as the process virtual address space (eight pages), with each page having a fixed location to which it is written when it is removed from main memory. Calculating this address requires knowing only where the process paging area begins, since pages are stored in it contiguously in order of their virtual page number. A page that is in memory always has a shadow copy on disk, but this copy may be out of date if the page has been customized since being loaded. The shaded pages in memory indicate pages not present in memory. The shaded pages on the disk are (in principle) superseded by the copies in memory, although if a memory page has to be swapped back to disk and it has not been customized since it was loaded, the (shaded) disk copy will be used.

In Figure 1(b), pages do not have fixed addresses on disk. When a page is swapped out, an empty disk page is selected on the fly and the disk map (which has room for one disk address per virtual page) is updated accordingly. A page in memory has no copy on disk. Their entries in the disk map hold an invalid disk address or a bit marking them as not in use.

Having a fixed swap partition is not always possible. For instance, no disk partitions may be available. In this case, one or more large, preallocated files within the normal file system can be used. Windows uses this approach. On the other hand, an optimization can be used here to reduce the amount of disk space required. Since the program text of every process came from some (executable) file in the file system, the executable file can be used as the swap area. Better yet, since the program text is normally read-only, when memory is tight and program pages have to be removed from memory, they are just discarded and read in again from the executable file when required. Shared libraries can also work this way.


disk management, algorithm, file system, address space, memory