[lkml]   [2009]   [Jul]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: RFC for a new Scheduling policy/class in the Linux-kernel
    On Tue, Jul 14, 2009 at 01:16:52PM -0400, James H. Anderson wrote:
    > ... BTW, I should say that I am not
    > familiar with the PEP protocol that has been discussed in this thread.
    > I assume it doesn't work under GEDF, or you wouldn't have asked the
    > question...

    I have not seen the definition of PEP, but from the context of
    this discussion I infer that it refers to an implementation of
    priority inheritance. As such, with pretty much any global
    scheduling policy, the set of other tasks whose critical sections
    could stack up is bounded only by the number of tasks in the

    In any case, I have misunderstood what PEP is, let me attempt
    to summarize what I have inferred:

    A high priority running task that would otherwise become blocked
    waiting for a lower-priority lock-holding task to release the lock
    can give up its prority/shot at execution to the lower-priority
    task that is blocking it. That is, when a task A is "blocked" for
    a lock it can stay in the run-queue so long as the task B that is
    (ultimately, transitively) blocking it is in (the same?)
    run-queue. At any point where the scheduler would choose to
    execute A it instead finds B, by traversing wait-for links between
    tasks, and executes B. The priority order of the run-queue can be
    based on any (partial) ordering relation, including deadlines.

    A slight complexity is that if B is allowed to suspend itself
    while holding a lock, and does so, one must run back and also
    remove the tasks like A from the run-queue, and when B wakes up,
    one must do the revers. However, the frequency of deep nesting
    of wait-for relationships seems small.

    For GEDF on SMP, a question is how to handle the case where A is
    blocked on one processor and B may be running on a different one.
    This seems to require removing A from the run-queue when it is

    Of course, the current Linux model appears not to fully support
    GEDF, since run-queues are per-processor, subject to explicit
    migration. So, as infer from the preceding messages, the question
    above transforms into whether to migrate A to B's processor
    run-queue or to migrate B to A's processor run-queue?


     \ /
      Last update: 2009-07-15 23:23    [W:0.022 / U:85.184 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site