lkml.org 
[lkml]   [2009]   [Jul]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: RFC for a new Scheduling policy/class in the Linux-kernel
    On Fri, Jul 17, 2009 at 09:40:59AM +0200, Henrik Austad wrote:

    > Why cannot you expect real-time tasks using a deadline scheduler to provide
    > some estimate of the execution cost? How can you ever hope to run a deadline
    > scheduler without this?

    This depends on what you mean by a "deadline scheduler".
    Personally, I don't think it makes much sense for an OS to support
    scheduling of aperiodic "jobs" on job deadlines. If you have
    chunks of application work that logically should be viewed as
    jobs, with approximately known WCET and deadlines, the right way
    to handle that is to have server thread(s), with associated job
    queue(s) that order their own queues by job deadline. The servers
    are provisioned with enough CPU capacity to provide the desired
    level of service for the anticipated load. If load-shedding is
    required at times, that is the responsibility of the server, which
    is part of the application and has the application-specific
    knowledge needed to make such decisions. (Alternatively,
    the server could negotiated for a higher CPU share if it starts
    missing deadlines.)

    What it makes sense for the OS to provide is what I'll loosely
    call "CPU shares". Deadline scheduling is a good way to implement
    this, since the schedulability analysis is relatively clean
    (including max. tardiness). That is each server thread has a
    "period" and is entitled to a certain budgeted amount of time each
    period, and the period is the deadline for getting that much CPU
    time. Constant Bandwidth and Total Bandwidth are two such
    policies. (I recently reviewed a paper that worked the kinks out
    of the published Constant Bandwidth in a very nice way. If I can
    find that it has been since published, or if there is a public
    pre-print technical report, I'll try to send the reference in
    another e-mail.)

    With CPU shares, we do have something like a WCET, but it is
    really a maximum allowed execution time. In this case, I'm not
    sure it makes much (any?) sense to worry about laxity, though.
    This should not be a hard-deadline situation (indeed, I don't
    think it makes sense for an OS as complicated as Linux to talk
    about truly hard deadlines). It may be enough to know the maximum
    lag or tardiness.

    Of course, if you want to put in special support for periodic
    tasks (say for sensor polling or poriodic actuator output), you
    can do that, but to me the right model is probably not a thread.
    It would make more sense to me for such tasks to implemented as
    event handlers.

    > How can you use deadlines based on priorities? A priority is a
    > one-way mapping of deadlines for a set of tasks.

    I had in mind several different ways.

    1) You can preserve a range of nominal "deadlines" that are
    above and below the range of real deadlines used in scheduling.
    For example:

    A) reserve the maximum representable time value for
    tasks that should never run (suspended).
    This value is useful for bandwidth
    limiting aperiodic server scheduling, if you really want to
    keep a temporarily out-of-budget server from competing with
    other tasks. Note that the pure constant-bandwith server is not enough
    in this respect, since it would still have a deadline earlier
    than non-realtime - tasks in the B range.

    B) Reserve a few values below that for tasks that are
    fixed-priority and lower in priority than all true deadline tasks.
    Some of these "deadlines" can be used for SCHED_FIFO and SCHED_RR
    that we want to be below the deadline-scheduler and also for
    SCHED_OTHER.

    C) The main band of deadlines is used for real deadline
    scheduling. (I don't believe it would technicall violate the
    POSIX standard to have a hidden "hole" between SCHED_FIFO and
    SCHED_RR values, but if there are seriou objections, one could
    pick a priority in the middle of the RT range and say that these
    deadline scheduled tasks are executing at that priority.)

    D) Reserve a few values close to zero for tasks that
    are fixed-priority and higher in priority than all true
    deadline tasks. This is useful for SCHED_FIFO and SCHED_RR
    that we want to be above the deadline-scheduler, and
    also for hybrid EDZL and EDF scheduling algorithms.
    EDZL would use such a value when a task reaches zero laxity.
    Hybrid EDF uses such a value for tasks that have high
    enough processor utilizations (> 50%), to achieve a higher
    schedulable system utilization than pure EDF.

    You have lost nothing in deadline representation, since the values
    used for these two fixed-priority ranges are useless for real
    deadlines.

    2) Within the range (C) ("real" deadline scheduling), you can also
    implement something close enough to priority to serve the purposes
    for which priority is typically used, by using an aperiodic-server
    type scheduling algorithm and giving "high priority" tasks short
    replenishment periods (and so shorter relative deadlines).

    > Are we going to place all tasks in the kernel into rt-deadline
    > tasks? I had the impression that we wanted a class for a special
    > set of tasks.

    I think it could be done.
    See my scheme above for translating everthing into deadlines.

    Ted


    \
     
     \ /
      Last update: 2009-07-17 15:39    [W:2.505 / U:0.884 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site