)]}'
{
  "commit": "45c01e824991b2dd0a332e19efc4901acb31209f",
  "tree": "20d889b97636410c6ae425ff5dec90479d8cbb1a",
  "parents": [
    "39b945a37bac2b692773a470890c8ba301485b15"
  ],
  "author": {
    "name": "Gregory Haskins",
    "email": "ghaskins@novell.com",
    "time": "Mon May 12 21:20:41 2008 +0200"
  },
  "committer": {
    "name": "Ingo Molnar",
    "email": "mingo@elte.hu",
    "time": "Fri Jun 06 15:19:25 2008 +0200"
  },
  "message": "sched: prioritize non-migratable tasks over migratable ones\n\nDmitry Adamushko pointed out a known flaw in the rt-balancing algorithm\nthat could allow suboptimal balancing if a non-migratable task gets\nqueued behind a running migratable one.  It is discussed in this thread:\n\nhttp://lkml.org/lkml/2008/4/22/296\n\nThis issue has been further exacerbated by a recent checkin to\nsched-devel (git-id 5eee63a5ebc19a870ac40055c0be49457f3a89a3).\n\n\u003eFrom a pure priority standpoint, the run-queue is doing the \"right\"\nthing. Using Dmitry\u0027s nomenclature, if T0 is on cpu1 first, and T1\nwakes up at equal or lower priority (affined only to cpu1) later, it\n*should* wait for T0 to finish.  However, in reality that is likely\nsuboptimal from a system perspective if there are other cores that\ncould allow T0 and T1 to run concurrently.  Since T1 can not migrate,\nthe only choice for higher concurrency is to try to move T0.  This is\nnot something we addessed in the recent rt-balancing re-work.\n\nThis patch tries to enhance the balancing algorithm by accomodating this\nscenario.  It accomplishes this by incorporating the migratability of a\ntask into its priority calculation.  Within a numerical tsk-\u003eprio, a\nnon-migratable task is logically higher than a migratable one.  We\nmaintain this by introducing a new per-priority queue (xqueue, or\nexclusive-queue) for holding non-migratable tasks.  The scheduler will\ndraw from the xqueue over the standard shared-queue (squeue) when\navailable.\n\nThere are several details for utilizing this properly.\n\n1) During task-wake-up, we not only need to check if the priority\n   preempts the current task, but we also need to check for this\n   non-migratable condition.  Therefore, if a non-migratable task wakes\n   up and sees an equal priority migratable task already running, it\n   will attempt to preempt it *if* there is a likelyhood that the\n   current task will find an immediate home.\n\n2) Tasks only get this non-migratable \"priority boost\" on wake-up.  Any\n   requeuing will result in the non-migratable task being queued to the\n   end of the shared queue.  This is an attempt to prevent the system\n   from being completely unfair to migratable tasks during things like\n   SCHED_RR timeslicing.\n\nI am sure this patch introduces potentially \"odd\" behavior if you\nconcoct a scenario where a bunch of non-migratable threads could starve\nmigratable ones given the right pattern.  I am not yet convinced that\nthis is a problem since we are talking about tasks of equal RT priority\nanyway, and there never is much in the way of guarantees against\nstarvation under that scenario anyway. (e.g. you could come up with a\nsimilar scenario with a specific timing environment verses an affinity\nenvironment).  I can be convinced otherwise, but for now I think this is\n\"ok\".\n\nSigned-off-by: Gregory Haskins \u003cghaskins@novell.com\u003e\nCC: Dmitry Adamushko \u003cdmitry.adamushko@gmail.com\u003e\nCC: Steven Rostedt \u003crostedt@goodmis.org\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\nSigned-off-by: Thomas Gleixner \u003ctglx@linutronix.de\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "bfb8ad8ed1717bf95f82ddf7ea8b5b40bb7fbe7b",
      "old_mode": 33188,
      "old_path": "kernel/sched.c",
      "new_id": "7178b8c2351ce5f12289bfe858f52f636fd493a9",
      "new_mode": 33188,
      "new_path": "kernel/sched.c"
    },
    {
      "type": "modify",
      "old_id": "3432d573205d415d8a02070c3f59d3ab2f68fbbb",
      "old_mode": 33188,
      "old_path": "kernel/sched_rt.c",
      "new_id": "fefed39fafd8fa6b5088ea8c4179c01ddd7debab",
      "new_mode": 33188,
      "new_path": "kernel/sched_rt.c"
    }
  ]
}