SCHED_RR/SCHED_FIFO and kernel threads?

SCHED_RR/SCHED_FIFO and kernel threads?

[Patrik Hägglund]

Hi all,

When I use 2.6 kernels (2.6.11) and run processes whith SCHED_RR or 
SCHED_FIFO scheduling, kernel activity - in the form of kernel threads - 
gets starved. Googling gave me this thread: 
http://www.ussg.iu.edu/hypermail/linux/kernel/0411.1/0182.html, which 
discuss the topic brifely.

As I remember it, using a 2.4 (or 2.2?) kernel it was possible to run 
processes using SCHED_RR/SCHED_FIFO scheduling classes (as defined by 
the Process Scheduling option in POSIX), at different priorities, 
whitout starving console input/output. For example, in one virtual 
terminal I stared a "supervisor" shell with SCHED_FIFO at priority 20, 
and then the job tasks I wanted to "run" in other virtual terminals, now 
still with SCHED_FIFO, but with lower priorities. If the job tasks 
dead-locked or ran into infinite loops, I just switched to the 
"supervisor" shell and killed the job tasks. I think I also - as an 
alternative - started the whole X server in "supervisor mode". I this 
way, I was able to get deterministic scheduling between tasks, and was 
still able to avoid locking the machine when things went wrong.

However, using 2.6 kernels the "supervisor mode" doesn't work anymore. 
Using virtual terminals at the console, I'm unable to switch to another 
VT (using alt-F2), or switch window focus in X.

Kernel threads seems to generally be scheduled in the SCHED_OTHER class 
(with the 'migration' thread as an exception).

As I see it, "kernel activity" shall not be starved by user-space 
processes. Therefore, I was very suprised by this behaviour when I saw 
it in 2.6.11.

Can someone explain how this is supposed to work? Is this the common 
design solution used by other operating systems that use kernel threads 
and have SCHED_RR/SCHED_FIFO scheduling (i.e. other POSIX operating 
systems with kernel threads)? Was there any discussion about the design 
when this migration of kernel acitivity into threads started?

Regards,
Patrik Hägglund

Re: SCHED_RR/SCHED_FIFO and kernel threads?

[Chris Friesen]

Patrik Hägglund wrote:

> Kernel threads seems to generally be scheduled in the SCHED_OTHER class 
> (with the 'migration' thread as an exception).

This is on purpose.  The idea is that realtime processes get all the 
time they request.  If the kernel threads are interrupting the realtime 
app, then the latency of the realtime app is degraded.

> As I see it, "kernel activity" shall not be starved by user-space 
> processes. Therefore, I was very suprised by this behaviour when I saw 
> it in 2.6.11.

If you want specific kernel threads to take priority, you can always 
manually make then SCHED_RR/SCHED_FIFO yourself.

Chris

Re: SCHED_RR/SCHED_FIFO and kernel threads?

[Patrik Hägglund]

Chris Friesen wrote:

> Patrik Hägglund wrote:
>
>> Kernel threads seems to generally be scheduled in the SCHED_OTHER 
>> class (with the 'migration' thread as an exception).
>
>
> This is on purpose.  The idea is that realtime processes get all the 
> time they request.  If the kernel threads are interrupting the 
> realtime app, then the latency of the realtime app is degraded.

Don't you get the problem with priority inversion? I.e., if you have two 
processes, P1 and P2, scheduled with SCHED_FIFO, where P1 has higer 
priority than P2. Now, if P1 gets blocked and needs some kernel thread 
to execute to get unblocked, then P2 is scheduled before the kernel 
thread, and can execute without any time limit.

That is, you should be much better off if the kernel threads has a 
_high_ priority. Then the execution progress can only be blocked by 
kernel threads, not by user space threads and processes. Or have I 
missed something?

(Besides that, as I see it, SCHED_RR/SCHED_FIFO are scheduling 
abstractions on their own, not necessarily  connected to  "low latency " 
or "realtime".)

Re: SCHED_RR/SCHED_FIFO and kernel threads?

[Steven Rostedt]

On Fri, 2005-06-17 at 08:38 +0200, Patrik Hägglund wrote:
> Don't you get the problem with priority inversion? I.e., if you have two 
> processes, P1 and P2, scheduled with SCHED_FIFO, where P1 has higer 
> priority than P2. Now, if P1 gets blocked and needs some kernel thread 
> to execute to get unblocked, then P2 is scheduled before the kernel 
> thread, and can execute without any time limit.

Yep, that could happen.

> That is, you should be much better off if the kernel threads has a 
> _high_ priority. Then the execution progress can only be blocked by 
> kernel threads, not by user space threads and processes. Or have I 
> missed something?

Still have that problem with priority inversion. Kernel threads share
date structures with user processes (when they are in kernel mode) and
that kernel thread that is needed may get blocked on a process that is
lower in priority than the two mentioned above.

> 
> (Besides that, as I see it, SCHED_RR/SCHED_FIFO are scheduling 
> abstractions on their own, not necessarily  connected to  "low latency " 
> or "realtime".)

Only in the vanilla kernel. See Ingo's RT work. It handles priority
inversion and SCHED_RR/SCHED_FIFO are actually connected to "low
latency" and "realtime".

http://people.redhat.com/mingo/realtime-preempt/

-- Steve

Re: SCHED_RR/SCHED_FIFO and kernel threads?

[Patrik Hägglund]

Steven Rostedt wrote:

>On Fri, 2005-06-17 at 08:38 +0200, Patrik Hägglund wrote:
>  
>
>>Don't you get the problem with priority inversion? I.e., if you have two 
>>processes, P1 and P2, scheduled with SCHED_FIFO, where P1 has higer 
>>priority than P2. Now, if P1 gets blocked and needs some kernel thread 
>>to execute to get unblocked, then P2 is scheduled before the kernel 
>>thread, and can execute without any time limit.
>>    
>>
>
>Yep, that could happen.
>
>  
>
>>That is, you should be much better off if the kernel threads has a 
>>_high_ priority. Then the execution progress can only be blocked by 
>>kernel threads, not by user space threads and processes. Or have I 
>>missed something?
>>    
>>
>
>Still have that problem with priority inversion. Kernel threads share
>date structures with user processes (when they are in kernel mode) and
>that kernel thread that is needed may get blocked on a process that is
>lower in priority than the two mentioned above.
>
>  
>
>>(Besides that, as I see it, SCHED_RR/SCHED_FIFO are scheduling 
>>abstractions on their own, not necessarily  connected to  "low latency " 
>>or "realtime".)
>>    
>>
>
>Only in the vanilla kernel. See Ingo's RT work. It handles priority
>inversion and SCHED_RR/SCHED_FIFO are actually connected to "low
>latency" and "realtime".
>
>http://people.redhat.com/mingo/realtime-preempt/
>
>-- Steve
>
>
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at  http://www.tux.org/lkml/
>
>  
>
Thanks for the pointer to Ingo's work. I will have a look.

Regarding my last comment: What I was trying to say was that I thought 
there are _basic_ aspects to consider (i.e. my original problem with 
kernel starvation) when implementing SCHED_RR/SCHED_FIFO _before_ you 
consider how to implement them in a "low latency" or "realtime" context.

/Patrik Hägglund

Re: SCHED_RR/SCHED_FIFO and kernel threads?

[Patrik Hägglund]

Well, Ingo's patch didn't made any difference for my problem with kernel 
starvation.

As expected, the workaround of raising the priority of the 'events' 
kernel thread made it possible to switch VT or switch windows in X (as 
described in my first mail), when running a simple infinite loop. When 
running arbitrary programs, I expect that all kernel threads needs 
higher priority.

I guess that the point with kernel threads is to push heavy kernel 
requests "backwards in the queue", thereby lowering the mean latency for 
SHED_OTHER processes. Therefore, using high priorities for kernel 
threads was not an option. However, this comes at the price of breaking 
SCHED_FIFO/SCHED_RR.

The only clean solution is probably to have priorities that are reserved 
for kernel threads. I saw that kernel threads in LynxOS may use a 
priority of 1/2 above of the user-space tasks it serves. This seems like 
a good solution to the problem.

Any other patches out there, ready for a test?

/Patrik Hägglund

Re: SCHED_RR/SCHED_FIFO and kernel threads?

[Patrik Hägglund]

Well, Ingo's patch didn't made any difference for my problem with kernel 
starvation.

As expected, the workaround of raising the priority of the 'events' 
kernel thread made it possible to switch VT or switch windows in X (as 
described in my first mail), when running a simple infinite loop. When 
running arbitrary programs, I expect that all kernel threads needs 
higher priority.

I guess that the point with kernel threads is to push heavy kernel 
requests "backwards in the queue", thereby lowering the mean latency for 
SHED_OTHER processes. Therefore, using high priorities for kernel 
threads was not an option. However, this comes at the price of breaking 
SCHED_FIFO/SCHED_RR.

The only clean solution is probably to have priorities that are 
exclusively reserved for use by the kernel. I saw that kernel threads in 
LynxOS may use a priority of 1/2 above of the user-space tasks it 
serves. This seems like a good solution to the problem.

Any other patches out there, ready for a test?

/Patrik Hägglund

Re: SCHED_RR/SCHED_FIFO and kernel threads?

[Lee Revell]

On Wed, 2005-06-22 at 00:18 +0200, Patrik Hägglund wrote:
> The only clean solution is probably to have priorities that are 
> exclusively reserved for use by the kernel. I saw that kernel threads
> in LynxOS may use a priority of 1/2 above of the user-space tasks it 
> serves. This seems like a good solution to the problem. 

No, it's not, because some SCHED_FIFO/SCHED_RR threads do not need any
kernel services, and are perfectly happy with stalling the rest of the
kernel until they're done.

Lee

Re: SCHED_RR/SCHED_FIFO and kernel threads?

[Lee Revell]

On Thu, 2005-06-16 at 17:25 +0200, Patrik Hägglund wrote:
> For example, in one virtual 
> terminal I stared a "supervisor" shell with SCHED_FIFO at priority
> 20, 
> and then the job tasks I wanted to "run" in other virtual terminals,
> now 
> still with SCHED_FIFO, but with lower priorities. 

I believe there's a Sysrq to drop all SCHED_FIFO processes to
SCHED_OTHER.  But yes, in general, bad things will happen if you are not
careful with SCHED_FIFO.

Lee