Re: Out of memory kernel death

Tim Hollebeek (tim@franck.Princeton.EDU)
Thu, 8 May 1997 15:59:22 -0400 (EDT)

Justin Dossey writes ...
>
> WARNING: I am NOT a kernel expert. However, I can think.
>
> On Thu, 8 May 1997, Tim Hollebeek wrote:
> > How do you avoid this? Obviously we want to kill the process that, if
> > left alive, would most quickly eat all the available memory if such a
> > process exists. We can't predict the future, but we *can* figure out
> > who has been allocating memory the fastest in the past and assume this
> > is likely to continue. So I suggest killing the process with the
> > (highest total size/running time); the X server and other large, but
> > long running processes should be quite low on that list. If you want
> > an even more accurate heuristic, a bit of overhead can be added to track
> > number of page allocations during the last <arbitrary time period> or
> > a decaying "memory demand" load average. But those are more complex.
>
> Suppose I were to write a program, that I will call K, that did two
> things:
>
> 1) check for the existence of a certain process, and if it didn't
> exist, spawn that process[a].
> 2) _gradually_ take up all available memory.
>
> [a] Pick your favorite memory-hog spike program.
>
> Seems to me that a kernel (or a daemon) that killed _the process_ with
> the highest total size / running time, would fail to catch K.
>
> A typical scenario:
> 1. I launch K.
> 2. K launches [a].
> 3. Kernel kills [a].
> 4. K increments memory usage by a few hundred bytes
> 5. K launches [a].
> 6. Kernel kills [a].
>
> Etc, Etc, Etc, ad nauseam. At the apex of this memory-increasing
> cycle, K would be launching [a] as quickly as it possibly could, and
> the kernel would be killing [a] as quickly as it possibly could,
> eating CPU like never before. The kernel would _not_, however, kill
> K, because it always sees [a] as the process with the highest memory
> usage-runtime ratio.

First of all, let me say I personally am not interested in preventing
malicious processes from being able to perform DOS attacks; I personally
am interested in making sure the system survives common non-malicious
failure modes. Unfortunately, it isn't hard for a non-malicious process
to cause rather severe problems under the current scenario.

However, I do have two comments with regard to your suggestion:

(1) It basically comes down to the idea of one process whose job it is to
always create a process that is the most attractive one to be killed,
regardless of what the heuristic is. I think one can prove one cannot
defend against this as long as the process in question can spawn processes
fast enough.

(2) despite the inclusion of the fact that K grows slowly, K *does* have a
higher score than processes that have been around longer than K, based
on the fact that it has a shorter time and a larger memory usage.
So step 4 is actually irrelevant; if K does in fact grow to the point
to where it is itself a memory hog, it will be high on the target list,
and assuming the "queue" isn't blocked by quickly spawning [a] processes,
it will get killed soon. (note that [a] processes need to be spawned
*and* have time to grow to a point where their score surpasses K's score;
this takes a bit of CPU time when K is large)

The reason for this is that the "ratio" method has the "most memory" solution
and "most recent" solutions as limiting cases. Among processes that have been
around for approximately the same amount of time, the largest is killed; among
processes that use approximately the same amount of time, the newest one is
killed.

---------------------------------------------------------------------------
Tim Hollebeek | Disclaimer :=> Everything above is a true statement,
Electron Psychologist | for sufficiently false values of true.
Princeton University | email: tim@wfn-shop.princeton.edu
----------------------| http://wfn-shop.princeton.edu/~tim (NEW! IMPROVED!)