The free list

The system keeps a linked list of free (currently unassigned ) pages in memory, known as the free list . For performance and to handle emergencies, the kernel tries to keep a certain minimum amount of memory in the free list at all times. If the list shrinks to a point where something must be done to get more pages, the pagedaemon is started up. The pagedaemon attempts to find some space by taking pages away from processes ” but only old pages that (hopefully) are not in use. To find space, it makes a pass through a section of the page list, cleaning out the "referenced" bit. After a short time, it makes another pass through the same pages and checks to see if they have actually been referenced during that period. If not, these pages are candidates for theft, and the kernel will move them onto the free list for possible use by somebody else. Of course, if the page has been modified at some point, it will have to be written out to disk before being reused, but there is also a "modified" bit in the page information to let the kernel know. (These are known as dirty pages , since they have been scribbled on).

The algorithm used by the pagedaemon is called the "clock hands" method. Think of memory as a big ring like the outside of a clock face with two hands moving around this ring, separated by a bit of space (time). One hand cleans out the referenced bit in the status field, and the following hand looks for untouched pages. The "handspread" (amount of time between the actions of the hands), how often the page daemon runs, when it is started up, and how much memory it checks in one pass are all tunable parameters in the kernel.

Note that when a page is put onto the free list, it is not cleaned out: The data that was there is still available. Thus, if a program that lost one of its pages needs it back again, there is a good possibility that the page, even though it is not mapped into this process's address space, is still in memory (on the free list) with the same information still in it. In this case, the process can grab it back again. This is known as a reclaim , or a soft page fault, because it does not require any disk I/O to retrieve information.

To make this scheme work better, the pages that are put onto the free list can be placed in the front (and therefore used first) or stuck on the end. For example, pages used for a program's stack space might be put on the front of the list when that program exits, because the data in those pages is of no earthly use to any other process. However, pages that contain data from a disk file are stuck on the back end of the list, because somebody might need them later on. So if somebody runs the ls program, reads all the pages of code into memory, and exits, all those pages will, of course, have to go on the free list. But the next time ls is run, there is a good chance that all the necessary pages are still in memory, still on the free list, still with the correct contents ” and no disk (or network) activity is necessary in order to get ls back in operation again.