[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.168 / U:1.892 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site