lkml.org 
[lkml]   [1998]   [Nov]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Schedule idle
On Mon, 9 Nov 1998 yodaiken@chelm.cs.nmt.edu wrote:
> On Mon, Nov 09, 1998 at 08:33:28PM +0100, Rik van Riel wrote:

> > 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.

There are certain semantics though. One of them is
that a high priority RT task never sched_yield()s
to a lower priority one. Yes, this is a bug in the
current Linux implementation. Yes, this is fixed
in the SCHED_IDLE patch.

> > 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.

Why? The more I read your message the less I am concerned
that is is a real issue.

> 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.

This is not a problem since Linux doesn't let the high
priority process do busy waiting on the lock. Since no
busy waiting is done the low priority task gets a fair
chance to release the lock again.

Only a third, medium priority, CPU eating task can
ruin this situation. To properly fix it, we will
want priority inheritance. There might be other
ways, but none of them are as elegant or efficient.

> > 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.
> or
> Low priority process A enters a system call and does
> global_cli
> High priority task B calls global_cli

These two scenarios are non-problems in Linux, since
the high priority task will block and let the other
one finish the critical section and release the lock.

> > > 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?

An RT process should pun ASAP. I guess we can all agree
on that. If ASAP isn't good enough people should switch
to your RT-Linux. In the problem cases above, ASAP is
when the lock is released. This means we want the lock
to be released ASAP and priority inheritance looks like
an excellent way of achieving that goal, as long as we
remember to put the process back on it's own run queue
when the lock is released (so it can't re-aquire the
lock when another process wants it).

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

OK, then lets define RT as "must run ASAP when it becomes
runnable". Something like this is good enough for soft RT
as is currently used in the Linux kernel.

The "as soon as possible" should serve as an incentive to
absolutely minimize the latency experienced by an RT task.
We can measure the latency and give some figures about it
as soon as the implementation is ready. If it's not good
enough people can (and should) switch to your RT-Linux.
As you said it yourself, Linux is a timesharing system
with some RT stuff grafted on top and you can never
expect it to run perfectly under all circumstances.

regards,

Rik -- slowly getting used to dvorak kbd layout...
+-------------------------------------------------------------------+
| Linux memory management tour guide. H.H.vanRiel@phys.uu.nl |
| Scouting Vries cubscout leader. http://www.phys.uu.nl/~riel/ |
+-------------------------------------------------------------------+

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:45    [from the cache]
©2003-2011 Jasper Spaans