[lkml]   [1998]   [Nov]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: Schedule idle
    On Mon, Nov 09, 1998 at 08:33:28PM +0100, Rik van Riel wrote:
    > > Linux kernel assumes that a kernel mode thread should progess
    > > until _it_ (the thread) decides to reschedule
    > >
    > > Priority based RT assumes that the highest priority runnable
    > > process will advance at any time.
    > >
    > > If the OS tries to believe both propositions at the same time it will die.
    > Not neccesarily. There are certain things you can do
    > do avoid this situation. Firstly, RT processes usually
    > don't take up loads of CPU time. If they do, you're
    > better off with a separate system anyway; you're
    > right on that.

    Orthogonal. It's not how much time they use, it's what gets to run when.

    > OTOH, I have been running RT processes for a long
    > time now (can you say 1.3) without actually
    > experiencing any of the problems you mentioned.

    That's because of the modest implementation of Posix soft RT.

    > > >way, the problem is not with the SCHED_IDLE patch.
    > >
    > > Of course it is.
    > The SCHED_IDLE idea is just an extension of the
    > realtime paradigm. I take it you're not really
    > serious about wanting to back _that_ out of the
    > kernel.

    "just an extension" is not a meaningful term. Posix soft rt is a
    peculiar spec -- all api and almost no semantics. So supporting it is
    not a problem -- pretending that it can be meaningfully extended is a problem.

    > Hint: you don't need the SCHED_IDLE patch to bump
    > into the priority inversion scheme, hence the
    > problem is somewhere else.

    It's good to try to define terms precisely. If we define "priority inversion"
    as the condition of a higher priority task waiting for a lower priority task,
    then we see that this is an inescapable property of the Linux design.
    For example, (nice -10 cat junk | nice 10 cat ) makes the higher priority
    "cat" wait on the lower priority "cat" once the pipe fills. Or consider
    the do_fork code and ask what happens if high priority process A wants
    to fork after low priority process B has acquired the semaphore and kernel
    lock. So "priority inversion" is not a "problem" in Linux, it is an
    intrinsic part of the operation of the kernel. It only becomes a problem
    when people want to pretend that this design can also support RT semantics.
    One might just as well claim that there is a lack of mobility problem in
    a furnace -- furnaces are supposed to produce heat, not to move, and
    UNIXs are designed to optimize throughput, not support a rather simple
    minded RT semantics.

    It's worth noting that even in pure priority scheduled systems, priority
    inversion is a fact of life as soon as there is any kind of communication or
    resource sharing. You can only fix this problem in papers where you
    declare all tasks to be assumed to be noninterfering.

    > > >Consider the following scenario:
    > > >- SCHED_OTHER process bangs on the FS
    > Which is fully threaded, except for some properly
    > protected areas.
    > > >- low-priority RT process computes primes or whatever
    > > >- high-priority RT process occasionally wakes up, reads a device and
    > > > uses the FS.
    > Priority inheritance would solve the problem.

    Explain how.
    And consider: Low priority A allocates a buffer and sleeps waiting for I/O
    "RT" process B asks for a buffer and finds none.
    Low priority process A enters a system call and does

    High priority task B calls global_cli

    > > >Just as in your example, the important RT process gets locked out of
    > > >the FS if schedule() is called with locks held. So, the problem isn't
    > > >with SCHED_IDLE, it's elsewhere.
    > >
    > > The problem is that you are introducing a complex mechanism to do
    > > something unspecified.
    > The 'something unspecified' means solving possible
    > problems with priority inversion that might be
    > hidden somewhere in the code.

    Still no specification. What is the desired semantics of process operation?
    If a RT process X is runnable and the highest priority, when should it
    run? Soon? At once? As soon as a pre-emption point is reached?

    > > Spell out what "important RT" means precisely and you will be in a
    > > position to make your code work. If you want a completely
    > > preemptable kernel, you have your work cut out for you. God alone
    > > knows what it means for a high priority RT task to "use the FS".
    > Uhmm, this is rather vague -- what is the hidden message
    > in this paragraph?

    There's no hidden message. I'm simply pointing out that if you have
    specifications that depend on undefined words e.g. "important" and "RT"
    whcih have absolutely no meaning in this context, then your solutions will
    be, in the words of some guy, like a hippo blundering around.


    Victor Yodaiken
    Department of Computer Science
    New Mexico Institute of Mining and Technology
    Socorro NM 87801
    PowerPC Linux page
    Real-Time Page

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:45    [W:0.030 / U:5.596 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site