カーネルのバージョンによって挙動が異なる

kernel 2.4.31

http://lxr.linux.no/linux-old+v2.4.31/kernel/sched.c#L130

この頃は sched.c に goodness という関数があり、そこで決まっている。

 130 /*
 131 * This is the function that decides how desirable a process is..
 132 * You can weigh different processes against each other depending
 133 * on what CPU they've run on lately etc to try to handle cache
 134 * and TLB miss penalties.
 135 *
 136 * Return values:
 137 *       -1000: never select this
 138 *           0: out of time, recalculate counters (but it might still be
 139 *              selected)
 140 *         +ve: "goodness" value (the larger, the better)
 141 *       +1000: realtime process, select this.
 142 */
...
 160        if (p->policy == SCHED_OTHER) {
 161                /*
 162                 * Give the process a first-approximation goodness value
 163                 * according to the number of clock-ticks it has left.
 164                 *
 165                 * Don't do any other calculations if the time slice is
 166                 * over..
 167                 */
 168                weight = p->counter;
 169                if (!weight)
 170                        goto out;
...
 178
 179                /* .. and a slight advantage to the current MM */
 180                if (p->mm == this_mm || !p->mm)
 181                        weight += 1;
 182                weight += 20 - p->nice;
 183                goto out;
 184        }

scheduler にわりあてられた tick が余っている量と、nice値による優先度が高ければ goodness が上がる。

kernel 2.6.32

mm/oom_kill.c の badness という関数で決めている

  54/**
  55 * badness - calculate a numeric value for how bad this task has been
  56 * @p: task struct of which task we should calculate
  57 * @uptime: current uptime in seconds
  58 *
  59 * The formula used is relatively simple and documented inline in the
  60 * function. The main rationale is that we want to select a good task
  61 * to kill when we run out of memory.
  62 *
  63 * Good in this context means that:
  64 * 1) we lose the minimum amount of work done
  65 * 2) we recover a large amount of memory
  66 * 3) we don't kill anything innocent of eating tons of memory
  67 * 4) we want to kill the minimum amount of processes (one)
  68 * 5) we try to kill the process the user expects us to kill, this
  69 *    algorithm has been meticulously tuned to meet the principle
  70 *    of least surprise ... (be careful when you change it)
  71 */

実装コードのコメントを見るべき http://lxr.linux.no/linux+v2.6.32/mm/oom_kill.c#L55

  • プロセスのメモリサイズが badness のベース
  • swapoff(2)を呼んでるプロセスであれば、badness を最高値にして return
    • /proc/sys/vm/swappiness の設定とは別の話
  • 子プロセスがあれば、その子プロセスのメモリサイズ/2 を badness に加算
  • badness /= sqrt(cpu_time)
    • cpuを使うプロセスであればあるほど小さくなる (cpu_time は 10秒単位)
  • badness /= sqrt(sqrt(run_time))
    • 起動時間がながければながいほど小さくなる (run_time は1000秒単位)

kernel 3.7.6

oom_kill.c の oom_badness という関数で決めている

   /**
175 * oom_badness – heuristic function to determine which candidate task to kill
176 * @p: task struct of which task we should calculate
177 * @totalpages: total present RAM allowed for page allocation
178 *
179 * The heuristic for determining which task to kill is made to be as simple and
180 * predictable as possible. The goal is to return the highest value for the
181 * task consuming the most memory to avoid subsequent oom failures.
182 */

実装コードのコメントを見るべき http://lxr.linux.no/linux+v3.7.6/mm/oom_kill.c#L175

  • プロセスのメモリ割合が badness のベース
  • rootプロセスに3%のボーナス
  • oom_score_adj の全体からの割合を出して加算

すごいシンプルになってる。OOM Killer に賢さを期待するな感が出ている。
kernel 4系もほぼ同じ。