RTLinux Scheduling

RTLinux Scheduling

Post by Ryan Kingsbu » Sun, 13 Jul 2003 04:31:19



Hello Everyone,

I am testing a number of different real-time Linux variants (RTLinux,
KURT, and RTAI) to see how they compare to each other as well as
commercial RTOS solutions.  As part of the tests to characterize the
scheduling behavior of RTLinux, I have created a program that creates
three identical periodic threads.  These threads are designed such
that they can not complete their task within one scheduling period.
While this wouldn't be an intentional design choice in a real system,
I need to test how the scheduler handles this situation.  I have set
the threads to use FIFO scheduling and they all have an equal priority
level.

Since the threads are of equal priority, I expected them to execute in
a "round robin" fashion, however, one process seems to hog the CPU
until its finishes its finite number of periods (I picked an arbitrary
number of times for each of the threads to run).  Once the first
process completes, one of the remaining two hogs the CPU and so on.  

The bottom line is: I would like to know  how the RTLinux scheduler
arbitrates between two identical threads that are both requesting CPU
time.  Any help would be appreciated.

Thanks,

Ryan Kingsbury
NASA Glenn Research Center

 
 
 

RTLinux Scheduling

Post by Steve Wa » Sun, 13 Jul 2003 07:13:53




>I am testing a number of different real-time Linux variants (RTLinux,
[ ... ]
>                                                          I have set
>the threads to use FIFO scheduling and they all have an equal priority
>level.

OK.  Do you understand what FIFO scheduling means?

Quote:>Since the threads are of equal priority, I expected them to execute in
>a "round robin" fashion, however, one process seems to hog the CPU
>until its finishes its finite number of periods (I picked an arbitrary
>number of times for each of the threads to run).  Once the first
>process completes, one of the remaining two hogs the CPU and so on.  

Yes, that's exactly what I would expect.  If you want round robin,
ask for it.

Quote:>The bottom line is: I would like to know  how the RTLinux scheduler
>arbitrates between two identical threads that are both requesting CPU
>time.  Any help would be appreciated.

SCHED_FIFO means "run until complete".  SCHED_RR means "round-robin
equal priority threads".  You want the latter.
--
Steve Watt KD6GGD  PP-ASEL-IA          ICBM: 121W 56' 57.8" / 37N 20' 14.9"

   Free time?  There's no such thing.  It just comes in varying prices...

 
 
 

RTLinux Scheduling

Post by Ed Skinne » Tue, 15 Jul 2003 22:01:42





>>I am testing a number of different real-time Linux variants (RTLinux,
> [ ... ]
>>                                                          I have set
>>the threads to use FIFO scheduling and they all have an equal priority
>>level.

> OK.  Do you understand what FIFO scheduling means?

>>Since the threads are of equal priority, I expected them to execute in a
>>"round robin" fashion, however, one process seems to hog the CPU until
>>its finishes its finite number of periods (I picked an arbitrary number
>>of times for each of the threads to run).  Once the first process
>>completes, one of the remaining two hogs the CPU and so on.

> Yes, that's exactly what I would expect.  If you want round robin, ask for
> it.

>>The bottom line is: I would like to know  how the RTLinux scheduler
>>arbitrates between two identical threads that are both requesting CPU
>>time.  Any help would be appreciated.

> SCHED_FIFO means "run until complete".  SCHED_RR means "round-robin equal
> priority threads".  You want the latter.

And note that if the interval you have selected for each of your threads
to run is less than the round-robin period of the OS, changing to SCHED_RR
may not appear to have any effect.
 
 
 

RTLinux Scheduling

Post by Ryan Kingsbu » Tue, 15 Jul 2003 21:42:04


Steve and the group,

First of all I would like to apologize for not completely describing
the problem that I believe I am observing.  I do understand the basic
principles behind FIFO and round-robin scheduling, however, I don't
believe I understand how these schemes behave in scenarios where the
CPU does not have enough time to complete everything that is requested
of it.

In my test program, the init_module picks a "masterStartTime" in the
future for all threads.  This masterStartTime is set as the
currentTime+1sec (with appropriate conversions to nanoseconds).  The
init_module routine then creates three identical threads with equal
priorIty (lets call them A, B, and C) and they schedule themselves as
follows:

pthread_make_periodic_np (pthread_self(), masterStartTime,
periodTaskA);

The constant "periodTaskA" is defined to be the same for all three
threads and the masterStartTime is guaranteed to be far enough in the
future that all three threads can start, setup scheduling,  and get to
their first "pthread_wait_np()" statement before any of the period
scheduling begins.

Before I go into a detailed description of what I think is happening,
I want to explain what the threads actually do when they are
executing.  Each of the threads have a constant execution time that is
defined just as the period was above.  Upon passing the
pthread_wait_np() statement, the thread grabs the current time (using
clock_gethrtime()) adds its execution time and stores the result in a
variable.  Then the program enters an empty while loop with the
following condition: "while(gethrtime(CLOCK_REALTIME)<endTime)".
After the while busy loop, the program loops back to the
pthread_wait_np().  The loop also contains some writes to a real-time
FIFO for time logging purposes and a counter to keep track of how many
iterations of the loop (the other loop containing the
pthread_wait_np()) we have performed.  The most important detail of
the task is that the execution time is greater than or equal to the
scheduling period (ie the task can't finish before it is scheduled to
run again).

OK, back to the hypothetical situation.  All three threads are now
waiting for the "masterStartTime" to begin execution.  It seems to be
a *shoot as to which of the threads start first, however, lets
just say that B was selected first by the scheduler.  As B executes,
the "masterStartTime" elapses for tasks A and C.  In FIFO scheduling,
I would expect them to be added to the scheduling queue at this point.
Since B executes for longer than its period, the second iteration of B
is added to the queue before the first iteration finishes.  Now, the
scheduling FIFO should look as follows (first on the left, last on the
right):

C,A,B(2)
or
A,C,B(2)

Once iteration 1 of thread B completes I would expect the scheduling
FIFO to grab the next task in line (this should be either task A or C
depending on which was queued first).  I would expect this behavior to
continue until the defined number of iterations for each thread were
complete.

Let me now describe what I am really observing.  The first thread to
be selected for execution seems to be random.  Once this thread
completes its first iteration, it gets scheduled again even though the
start times of the other two threads has long since passed.  This
thread continues to execute iteration after iteration until it
completes, then one of the remaining two threads is chosen and a
similar behavior occurs.  It seems that with FIFO scheduling enabled,
the thread that currently has control of the CPU has a higher real
priority than non-executing threads even though they all have an equal
"sched_priority" parameter.

One possible cause for this behavior that I came come up with, and
this may be way out in left-field, is that the pthread_wait_np()
command doesn't actually tell the scheduler that the current task is
done.  Rather, the function only checks to see if the task is scheuled
to run again.  Since in our case it is scheduled to run again it does
so without being preempted by the scheduler since the other queued
tasks are of equal priority.

Another even less likely scenario that I came up with is that the
schedule favors the executing task over equal priority queued tasks.
It would do this in order to save time with context switching in a
different task.

I am going to experiment with how the system behaves in this scenario
using the round-robin scheduling policy.  If you would like to see my
source code or the plots of task execution that have made with Kiwi
just let me know, I'd be glad to post them.  Thanks again for your
input.

Regards,

Ryan
AG4ZP


wrotE:



>>I am testing a number of different real-time Linux variants (RTLinux,
>[ ... ]
>>                                                          I have set
>>the threads to use FIFO scheduling and they all have an equal priority
>>level.

>OK.  Do you understand what FIFO scheduling means?

>>Since the threads are of equal priority, I expected them to execute in
>>a "round robin" fashion, however, one process seems to hog the CPU
>>until its finishes its finite number of periods (I picked an arbitrary
>>number of times for each of the threads to run).  Once the first
>>process completes, one of the remaining two hogs the CPU and so on.  

>Yes, that's exactly what I would expect.  If you want round robin,
>ask for it.

>>The bottom line is: I would like to know  how the RTLinux scheduler
>>arbitrates between two identical threads that are both requesting CPU
>>time.  Any help would be appreciated.

>SCHED_FIFO means "run until complete".  SCHED_RR means "round-robin
>equal priority threads".  You want the latter.
>--
>Steve Watt KD6GGD  PP-ASEL-IA          ICBM: 121W 56' 57.8" / 37N 20' 14.9"

>   Free time?  There's no such thing.  It just comes in varying prices...

 
 
 

RTLinux Scheduling

Post by Steve Wa » Wed, 16 Jul 2003 06:03:52




>First of all I would like to apologize for not completely describing
>the problem that I believe I am observing.  I do understand the basic
>principles behind FIFO and round-robin scheduling, however, I don't
>believe I understand how these schemes behave in scenarios where the
>CPU does not have enough time to complete everything that is requested
>of it.

Thanks for the complete description -- it helps a lot.

Quote:>In my test program, the init_module picks a "masterStartTime" in the
>future for all threads.  This masterStartTime is set as the
>currentTime+1sec (with appropriate conversions to nanoseconds).  The
>init_module routine then creates three identical threads with equal
>priorIty (lets call them A, B, and C) and they schedule themselves as
>follows:

>pthread_make_periodic_np (pthread_self(), masterStartTime,
>periodTaskA);

I haven't investigated how pthread_make_periodic_np()/pthread_wait_np()
work, so I'll make an educated guess.  My guess is that make_periodic
says "awaken this thread, if it's in pthread_wait_np, every {blah}."
It appears from your description of the symptom, that it is probably
implemented with a counting semaphore, so pthread_wait_np decrements
that semaphore, and make_periodic creates a threda to increment it
at the desired rate.  (At minimum, that's how I'd implement it based
solely on the names.)

Quote:>[ ... ]                                The most important detail of
>the task is that the execution time is greater than or equal to the
>scheduling period (ie the task can't finish before it is scheduled to
>run again).
>OK, back to the hypothetical situation.  All three threads are now
>waiting for the "masterStartTime" to begin execution.  It seems to be
>a *shoot as to which of the threads start first, however, lets

If they're all scheduled to awaken at exactly the same time, it is
indeed "hard to predict". ;)

Quote:>just say that B was selected first by the scheduler.  As B executes,
>the "masterStartTime" elapses for tasks A and C.  In FIFO scheduling,
>I would expect them to be added to the scheduling queue at this point.
>Since B executes for longer than its period, the second iteration of B
>is added to the queue before the first iteration finishes.  Now, the
>scheduling FIFO should look as follows (first on the left, last on the
>right):

Except that I can't think of any system that would actually implement
the functionality by dynamically instantiating multiple copies of the
thread (or, maybe, some "thread scheduling" token?).

Quote:>C,A,B(2)
>or
>A,C,B(2)
>Once iteration 1 of thread B completes I would expect the scheduling
>FIFO to grab the next task in line (this should be either task A or C
>depending on which was queued first).  I would expect this behavior to
>continue until the defined number of iterations for each thread were
>complete.

Except that what you're expecting increases the number of context
switches (and thus pure overhead) needed to do the job.  This system
is already guaranteed to fail:  None of the threads can ever meet
their deadlines.  Whether the best bet is to give the currently
scheduled thread another crack at it, or to cause extra context
switches and hope things eventually catch up is one of those judgement
calls that won't ever be right for all systems -- you want it one way
sometimes and the other way sometimes.

Quote:>Let me now describe what I am really observing.  The first thread to
>be selected for execution seems to be random.  Once this thread
>completes its first iteration, it gets scheduled again even though the
>start times of the other two threads has long since passed.  This
>thread continues to execute iteration after iteration until it
>completes, then one of the remaining two threads is chosen and a
>similar behavior occurs.  It seems that with FIFO scheduling enabled,
>the thread that currently has control of the CPU has a higher real
>priority than non-executing threads even though they all have an equal
>"sched_priority" parameter.

This implies that the pthread_wait_np (oh, you do know that _np means
"non portable", right?) does *NOT* give up its time slice.  If you want
to force that behavior, with this implementation, add a pthread_yield()
somewhere in the vicinity (probably before) the pthread_wait_np().

Quote:>One possible cause for this behavior that I came come up with, and
>this may be way out in left-field, is that the pthread_wait_np()
>command doesn't actually tell the scheduler that the current task is
>done.  Rather, the function only checks to see if the task is scheuled
>to run again.  Since in our case it is scheduled to run again it does
>so without being preempted by the scheduler since the other queued
>tasks are of equal priority.

Bingo.

Quote:>Another even less likely scenario that I came up with is that the
>schedule favors the executing task over equal priority queued tasks.
>It would do this in order to save time with context switching in a
>different task.

I strongly suspect that's part of the reasoning.

Quote:>I am going to experiment with how the system behaves in this scenario
>using the round-robin scheduling policy.  If you would like to see my
>source code or the plots of task execution that have made with Kiwi
>just let me know, I'd be glad to post them.  Thanks again for your
>input.

With SCHED_RR, I bet it preempts at the rr_interval, and moves on to
the next thread.  Because all deadlines are being blown, you will then
degenerate to a pure round-robin until every thread completes its loop.

Whether this is any more or less desirable depends on your requirements.
--
Steve Watt KD6GGD  PP-ASEL-IA          ICBM: 121W 56' 57.8" / 37N 20' 14.9"

   Free time?  There's no such thing.  It just comes in varying prices...