[lkml]   [1998]   [Nov]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: Schedule idle
On Tue, Nov 10, 1998 at 05:12:25PM -0300, Gordon P. Oliver wrote:
> That's because you are considering the _generic_ case. And almost all realtime

I've never seen a good specific case.

> In the "academic" RT literature (and in the _real_ use that caused ?Wind
> River? to add priority inheritance) there are many more cases like this that
> have bounded times for locking the semaphore, but, because they are in

I disagree. There are many cases where poor programming and mixing priority
scheduling with blocking causes failure conditions, but these all have better
solutions that do not require priority inheritance. Essentially priority inheritance
is a hack to allow people who don't understand synchronization to use threads and
mostly get away with it.

> >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).
> _please_ We can do better than this. Only semaphores (not spinlocks) need
> to have the priority inheritance. This can be done with lists off the
> semaphore and tasks... You don't really need to scan anything. It does
> make the down/up calls more heavyweight. The scheduler doesn't even notice.

The down/up calls are "more heavyweight" because they must scan the lists. Think
about how much work is involved and how many synchronization points are introduced.
And think about why it's important to use this mechanism for semaphores but
not important when exactly the same type of "inversion" can happen on, for example,
memory allocation with sleeps -- just because you don't call it a semaphore does
not mean it does not have the same semantics.

> Note that the up/down calls would only have to be heavyweight if they had
> priority inheritance enabled (i.e. at up, the process has been promoted, and
> at down, semaphore is locked by a lower priority process).

Right: so you introduce another unpredictable form of latency.

> >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.
> ehm. Not. The job of the OS is to assure that it doesn't deadlock processes
> that wouldn't otherwise deadlock. If a user has a producer process at high
> priority and a consumer at low priority he loses. That's not deadlock, that's
> just simple poor assignment of priorities.

But that is exactly the error that paralyzed Mars Lander. Consider a high priority
consumer that reads a pipe from a low priority producer. The consumer finds an
empty pipe and sleeps. The producer can't run because a medium priority process
is hogging the cpu. This won't be a problem in regular Linux because even low
priority tasks progress eventually and because there is no timing assurance for
the high priority task. But if you are going to claim that the high priority task
is RT and the medium is also RT, then the high priority task may hang indefinitely.


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