[lkml]   [1998]   [Nov]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: Schedule idle
> > 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.

i.e. (nice -10 cat junk | nice 10 cat & nice 5 cat bigjunk)

The nice -10 then may find itself waiting for the nice 5 to let the nice 10
run and empty the pipe.

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

Consider the first scenario. Low allocates buffer and sleeps on I/O. "RT"
blocks on Low. You don't care about this, although it gives an unbounded delay.
Then Medium runs so when Low wakes, Low will not run and release buffer right
away because Medium is running. This delay does bother you more than the
other, for reasons I don't understand -- that's ok, this delay is a big deal
in the academic RT literature and I don't understand that either. For
me, one unbounded timing delay is the same as another. But, now you propose
to fix the second kind of delay with "elegant" priority inheritance.
This would simply involve promoting Low to the priority of RT while RT
is waiting on Low. When Low releases the buffer, all it needs to do is
scan the list of all processes waiting for any other resources it may hold
and then resume the highest priority of any of these or its own priority
if nobody is waiting (this is what Solaris does). Now we have gone
from a simple scheduler change to satisfy Posix 1.b to a scheme by which
the OS searches the list of all sleep queues each time a process
releases a resource (note that without this search we have the possibility of
Low gets resource A, Low gets B and sleeps, RT_A blocks on Low raising Low
to RT priority, RT_B blocks on A raising Low to RT_B priority, Low releases
B and then becomes Low priority again) Of course, we need to apply this
method, not only to buffers, but to any IPC between a RT task and any other
task, such as the pipe example above. But then we need to do a search on
delay chains each time a process blocks too because:
LowA | LowB | LowC | RT_Critical
means that LowA,LowB, and LowC must all be promoted, thus when RT_Critical
first blocks on its pipe, the OS needs to determine the entire chain,
and dynamically adjust it as the pipes fill and empty.
Now all system tasks pay the price
for this "feature" whether they need it or not.

Is that really what you want?

> > > > 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 run ASAP. I guess we can all agree

Good sentiment!
How is this different from any other process? X needs to run ASAP or
the screen looks bad, Emacs needs to run ASAP or it does not respond
to keyclicks. Are they RT? I'm not being sarcastic here, it's quite
difficult to determine what "soft RT" should look like and I know it's
a real problem for some people. But Linux should provide a real solution,
not repeat the mistakes of others.

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