On Mon, 3 Jun 1996 23:15:10 -0400, "Sheldon E. Newhouse"
<sen@math.msu.edu> said:
> When real memory is exhausted, how does the system choose to swap?
Black magic. :)
Basically, it guesses...
> Is it based on programs which have been idle the longest, use the
> fewest resources, or what?
No. It doesn't look at the properties of particular programs at all.
Instead, it looks at the usage characteristics of memory pages. Even
programs which are quite active can be holding large areas of memory
which they aren't using, so by looking at the page level we can still
swap these out while preserving the commonly used data.
> Is there a specific algorithm which is used, relating cache, etc?
There are several algorithms, which essentially come down to four
things: the cache recycler (shrink_mmap in linux/mm/filemap.c), which
recycles cache pages and buffers; the swapper (swap_out in
linux/mm/vmscan.c) and the related shared-memory swapper (shm_swap in
linux/ipc/shm.c); and the balancing loop (try_to_free_page in
linux/mm/vmscan.c) which tries to balance out the swapping between
these three swappers.
The individual swappers basically use clock algorithms; we sweep
continually through the available pages, and each time we encounter a
page which has been accessed since the last sweep we mark it used; if
it wasn't accessed since that pass, we consider swapping it.
The page cache code only keeps one bit of information per page, and
discards data if it has been unused for one entire memory sweep. The
swapper code keeps a bit more information on each page, tracking
recent usage, so that it ends up discarding not the least RECENTLY
used pages but the least FREQUENTLY used.
> Also, how and when does the system relinquish the swapped space when
> it no longer needs it?
Many things don't need to be released; if we're just caching data
(either stuff we have read or binaries we are executing), then when
they get "swapped out" they are just discarded there and then.
Swapped data, however, needs to be released when the process exits or
exec()s. The exit_mm function does all of that.
> Where might I find out about these things?
In the kernel source! There are also a number of books around which
document the internals of the BSD or SVR4 unix operating systems, and
they will give you a start; linux doesn't use exactly the same
algorithms but uses many of the same ideas.
Cheers,
Stephen.
-- Stephen Tweedie <sct@dcs.ed.ac.uk> Department of Computer Science, Edinburgh University, Scotland.