How does pistachio deal with the priority inversion?

[lion]

     Hi, All. Question again.
     When a high priority thread A perform IPC receive from B, but B is not in polling state. So A blocked.
     Before B can perform the IPC that unblocks A, a third thread C with priority
between A and B becomes ready,preempts B and runs. If lots of such thread C,
IPC will be very slow.
     How  pistachio deal with this? I read some code,it seems no special process.
     Thanks!

---
Best regards

Bo Liu


_________________________________________________________________
Discover the new Windows Vista
http://search.msn.com/results.aspx?q=windows+vista&mkt=en-US&form=QBRE

[Raphael Neider]

Hi Bob,

> When a high priority thread A perform IPC receive from B, but B is not
> in polling state. So A blocked.  Before B can perform the IPC that
> unblocks A, a third thread C with priority between A and B becomes
> ready,preempts B and runs. If lots of such thread C, IPC will be very
> slow.

IPC won't start at all as B will never run.

> How  pistachio deal with this? I read some code,it seems no special
> process.  Thanks!

L4 leaves this problem to the OS on top, it does not deal with
starvation/priority inversion at all. Scheduling on L4 is still
not solved satisfactorily.

Regards,
Raphael

[lion]

Some parts of this message have been removed. Learn more about Nabble's security policy.

>
> IPC won't start at all as B will never run.
>
So thread A will Blocked for a very long time untill B gets to run?
 
>
> L4 leaves this problem to the OS on top, it does not deal with
> starvation/priority inversion at all. Scheduling on L4 is still
> not solved satisfactorily.
 
NOw, I am messed by L4's schedule mechanism. It' based on static priority and timeslice.
When a very high priority thread being wakeup. It will be scheduled untill a time interrupt happen?
And does Pistachio support kernel preempt like the linux kernel 2.6?
 
Thanks a lot!

---
Best regards

Bo Liu

---

Discover the new Windows Vista Learn more!

[Raphael Neider]

> > IPC won't start at all as B will never run.
> So thread A will Blocked for a very long time untill B gets to run?

Yes. However, you can use timeouts in A's IPC operation to avoid/recover
from such situations.

> > L4 leaves this problem to the OS on top, it does not deal with
> > starvation/priority inversion at all. Scheduling on L4 is still not
> > solved satisfactorily.
>  
> NOw, I am messed by L4's schedule mechanism. It' based on static priority and
> timeslice.  When a very high priority thread being wakeup. It will be
> scheduled untill a time interrupt happen?

How can a high priority thread wake up?
  1. receive IPC
  2. timeout, detected at some timer interrupt

In the first case, either a user thread or an interrupt thread explicitly
calls the high priority thread, immediately scheduling it for execution.

In the second case, I assume, the scheduler is invoked after having detected
that a (high priority) thread has reached a timeout.
But even if I am wrong and we do not immediately schedule the timed-out thread,
it will be scheduled after the end of the current timeslice (given no thread
with a still higher priority becomes ready in the meantime).

I am not sure about the 'until' in your question: The woken thread will
be dispatched no later than on the next timer interrupt (see above case 2).
It might be run earlier (case 1 above), but then it can run for a complete
timeslice (which is typically much longer than the timer period).

> And does Pistachio support kernel preempt like the linux kernel 2.6?

The L4 kernel is not preemptible (interrupts are disabled while inside
the kernel) except during string IPC and possibly during the recursive
unmap operation: Here we explicitly enable interrupts to reduce IRQ handler
latency.
All other code paths through the kernel are rather short, so that making
the kernel preemptible would not pay.

Hope that helped,
Raphael

[lion]

Some parts of this message have been removed. Learn more about Nabble's security policy.

> The woken thread will
> be dispatched no later than on the next timer interrupt (see above case 2).
> It might be run earlier (case 1 above), but then it can run for a complete
> timeslice (which is typically much longer than the timer period).

Yeah,that's what i want. Thanks a lot.
What's more,does time donation(you said which is typically much longer than the timer period) happened here?
if so ,could you explain it(time donation) a little more for me?

> The L4 kernel is not preemptible (interrupts are disabled while inside
> the kernel) except during string IPC and possibly during the recursive
> unmap operation: Here we explicitly enable interrupts to reduce IRQ handler
> latency.
> All other code paths through the kernel are rather short, so that making
> the kernel preemptible would not pay.

I known that for IA32 when entering kernel space, it's must through the int gate(or call gate) whether interrupt or system call.
And the after through the gate ,all interrupts will be disabled(set IF flag).
But, I didn't find where these interrupts be enabled again?.  Enabled when the interrupted thread(or any thread?) return back to user level? 
 
Thank you for your time!

---
Best regards

Bo Liu

> Date: Wed, 15 Oct 2008 13:32:04 +0200
> From: neider@...
> To: bo-liu@...
> CC: l4ka@...
> Subject: Re: How does pistachio deal with the priority inversion?
>
> > > IPC won't start at all as B will never run.
> > So thread A will Blocked for a very long time untill B gets to run?
>
> Yes. However, you can use timeouts in A's IPC operation to avoid/recover
> from such situations.
>
> > > L4 leaves this problem to the OS on top, it does not deal with
> > > starvation/priority inversion at all. Scheduling on L4 is still not
> > > solved satisfactorily.
> >
> > NOw, I am messed by L4's schedule mechanism. It' based on static priority and
> > timeslice. When a very high priority thread being wakeup. It will be
> > scheduled untill a time interrupt happen?
>
> How can a high priority thread wake up?
> 1. receive IPC
> 2. timeout, detected at some timer interrupt
>
> In the first case, either a user thread or an interrupt thread explicitly
> calls the high priority thread, immediately scheduling it for execution.
>
> In the second case, I assume, the scheduler is invoked after having detected
> that a (high priority) thread has reached a timeout.
> But even if I am wrong and we do not immediately schedule the timed-out thread,
> it will be scheduled after the end of the current timeslice (given no thread
> with a still higher priority becomes ready in the meantime).
>
> I am not sure about the 'until' in your question: The woken thread will
> be dispatched no later than on the next timer interrupt (see above case 2).
> It might be run earlier (case 1 above), but then it can run for a complete
> timeslice (which is typically much longer than the timer period).
>
> > And does Pistachio support kernel preempt like the linux kernel 2.6?
>
> The L4 kernel is not preemptible (interrupts are disabled while inside
> the kernel) except during string IPC and possibly during the recursive
> unmap operation: Here we explicitly enable interrupts to reduce IRQ handler
> latency.
> All other code paths through the kernel are rather short, so that making
> the kernel preemptible would not pay.
>
> Hope that helped,
> Raphael
>

---

Get news, entertainment and everything you care about at Live.com. Check it out!

[Raphael Neider]

> > The woken thread will be dispatched no later than on the next timer
> > interrupt (see above case 2). It might be run earlier (case 1 above), but
> > then it can run for a complete timeslice (which is typically much longer
> > than the timer period).

> Yeah, that's what i want. Thanks a lot.  What's more, does time donation (you
> said which is typically much longer than the timer period) happened here?  if
> so, could you explain it (time donation) a little more for me?

Typical timeslices are 10ms (on x86), the timer interrupt fires every 1000us
(microseconds), i.e., every 1ms or 10 times per timeslice. That's what I meant
with timeslices being much longer that the timer period.

Timeslice donation always occurs when we switch threads behind the scheduler's
back, i.e., during IPC. The kernel scheduler maintains a timeslice_tcb, which
is a pointer to the thread on whose timeslice we run (and on which we base our
decisions as to whether the current timeslice is over or not), but this is
updated only in schedule(), end_of_timeslice(), and preempt_thread(), none of
which is called during IPC. There we just use switch_to() ...

If the low prio thread B sends an IPC to the high prio thread A, A will be
woken and immediately dispatched (bypassing the scheduler) and continue
execution on B's timeslice until the timeslice expires (or A yields or blocks).
At the end of B's timeslice, the scheduler will be invoked and probably select
A to run. This time, however, also the timeslice_tcb is updated to point to A,
so that A will run on its own timeslice.

> > The L4 kernel is not preemptible (interrupts are disabled while inside the
> > kernel) except during string IPC and possibly during the recursive unmap
> > operation: Here we explicitly enable interrupts to reduce IRQ handler
> > latency.  All other code paths through the kernel are rather short, so that
> > making the kernel preemptible would not pay.

> I known that for IA32 when entering kernel space, it's must through the int
> gate(or call gate) whether interrupt or system call.  And the after through
> the gate ,all interrupts will be disabled(set IF flag).  But, I didn't find
> where these interrupts be enabled again?.  Enabled when the interrupted
> thread(or any thread?) return back to user level?

Yes, interrupts are either implicitly turned on when leaving the kernel via
iret (return from interrupt) or explicitly via sti (set interrupt flag, thus
*enabling* interrupts) just before leaving the kernel via sysexit/sysret on
the IPC path.

Regards,
Raphael