RTOS scheduler development

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Dear all,

I am new here, and I would like to ask something about implementing
fixed-priority preemptive scheduling(rate monotonic aproach) on MSP430
family.

Can anyone tell me what is usual way to implement call of scheduler's
dispatcher?
For example if there are two tasks, high priority HPTask and low LPTask.
Assume that LPTask is active and in the middle of its execution HPTask
becomes ready. As I understand in that moment scheduler's dispatcher which
is used for context switching should be called. What I'm curious about is
how can scheduler now that some event like refreshing tasks ready list
happened? I mean, if LPTask is executing and using CPU, who or what is
tracking changes of tasks ready list for example? Or maybe timer's ISR call
scheduler in some predefined period of time?

Thanks in advance!
Regards,
brOS  

      
                    
---------------------------------------        
This message was sent using the comp.arch.embedded web interface on
http://www.EmbeddedRelated.com

Re: RTOS scheduler development

Quoted text here. Click to load it

From the rest of your post, I'm assuming by "fixed-priority" you don't
mean to include equal priorities as a possibility.

Quoted text here. Click to load it

Yes.


Ask yourself, "How does it 'become ready?'"

Quoted text here. Click to load it

If you think about the above question I asked, you'd have your answer.
There are a variety of means by which a task 'becomes ready.'  They
either involve an interrupting event or else an operating system call.
Either way, control is already out of the hands of the low priority
task.  In other words, the call for context switching is already in
progress.  There is nothing more to worry about.

Quoted text here. Click to load it

Just think closely and it all becomes clear.  The basic idea of fixed
priorities without equal priorities in play is that the highest
priority task that is ready to run is... actually running.  Since your
case proposes that a low priority task is currently running, then it
must be the case that it is the highest priority task that is ready to
run... by definition.

Now, there must be some reason why the higher priority task isn't
running.  Perhaps it is sleeping on a timer.  In that case, and
presuming that the heartbeat timer generates interrupts (isn't polled
by a call initiated by that low priority task) that interrupt the low
priority task, when the timer interrupt takes place hopefully a
remaining time counter is decremented quickly.  If that expires, the
task should be moved to the ready queue (if you design this well and
other purposes allow it, it may only require the change of a single
pointer to achieve.)  Then you have some options to consider.  You can
either return from the interrupt and allow the low priority task to
make a normal call into the O/S and perform the transfer then.  The
advantage here is that you won't be pre-empting library routines and
that simplifies things a lot.  Or you can simply pre-empt the low
priority task once this high priority task is ready and switch stacks
and return.  The context of the low priority task, including the
interrupt state info, remains on the low priority task stack.
Eventually, things will get back to that and a return from interrupt
will return control to the interrupted low priority process.  Some
things can complicate this -- general interrupt states are an issue.
But that's the idea.

Pre-emption is almost always expensive.  If for no other reason, then
because you may be interrupting a library routine that uses static
memory and another task may also call it, destroying the prior context
there.  You need to know what you are doing, with pre-emption.  And
that takes some study.  It's easy enough to implement ignorantly, but
harder to do so with the thorough, comprehensive knowledge that it
takes to make it truly safe.

There are other reasons for a high priority task to be off of the run
queue and elsewhere.  It's not just about timing/sleeping.  It could
be waiting on an interrupt event other than the timer, or waiting on a
semaphore or message, etc.  Some of these are trivially handled.  For
example, if the task is waiting on a message then when some other
running task sends the message, it must call the O/S to actually send
it.  When that takes place, once again the O/S has control and at a
convenient place (function call boundary) to make a switch.  All the
O/S does is post the message, reschedule the task that received it to
see if it bubbles to the top or not, then returns to the highest
priority task in the run queue once that rescheduling is done.  That
will automatically cause the waiting task to run if it is the highest
priority at the time.

Hopefully, all that makes sense.  It's really quite easy.  I'd
recommend the original book by Douglas Comer called XINU (not one of
his follow-ons, but the first book he published only) if you are new
to these ideas and want a book designed from the beginning to talk to
people who are new and need a clear, cleanly conceived path towards
understanding that is laid out well for the newby.  Tannenbaum's
books, by comparison, are frighteningly complex and shouldn't be
tackled until you have gone through Douglas Comer's XINU book.

Jon

Re: RTOS scheduler development
Quoted text here. Click to load it
[...]
Quoted text here. Click to load it

You've already gotten a pretty good response. But, I think
you're going to need a book. You don't appear to have any
backround at all in RTOS architecture, and a clear description
of how everything works from the ground up would probably be
invaluable.

I recommend LaBrosse's book on MicroC/OS-II:

  (Amazon.com product link shortened)

Even if you don't want to use uC/OS-II on your project, it'll
give you a good solid background that's applicable to most
RTOSes.
  
--

Re: RTOS scheduler development

Quoted text here. Click to load it

The expression "significant event" was often used in some old real
time executives.

In addition to the usual completetion of an interrupt service routine,
any call to a system routine like SleepXXX, ReceiveXXX or WaitforXXX
should be considered as "significant event".

From the point of view of an low priority task, executing a high
priority task, it just looks like waiting for an interrupt service
routine taking a large amount of time to complete.

Paul
 

Re: RTOS scheduler development
Quoted text here. Click to load it

"After anything that can change the runnability of a 'waiting'
task".

If you think about this carefully, it's pretty easy to figure
out when to call the scheduler.  (there are tricks you can apply
to avoid needless calls to the scheduler but they can be ignored
for now).

For example, the jiffy often causes a call to the schedule
to *preempt* the currently running task when (if) its timeslice
expires.

Or, if an ISR signals an "event" (semaphore, etc. -- depends on
the model you are using) that some task might be waiting on.

Or, if the running task (or, an ISR) pushes data down a pipe
that has another task blocking on a *read()* of that pipe
(i.e., data is now available so the read() can be satisfied
and the blocked task resumed).

<shrug>  You have to look at the mechanisms that your particular
OS supports to determine which *can* alter the run-ability of
blocked tasks.  Then, figure out the most efficient way of
rescheduling when those "things" happen.

 > What I'm curious about is how can scheduler now that some event
 > like refreshing tasks ready list happened?

*Some* piece of code executed that, in your example, "refresh(ed)
tasks ready list".  So, that piece of code calls (directly or
indirectly) the scheduler.  (in practice, you can set a flag
to determine *if* there has been any *material* change in the
ready list so that the scheduler isn't invoked needlessly)

Re: RTOS scheduler development
Quoted text here. Click to load it

The other advice is to get a book, and I would also suggest that you do
that.

However, to give a quick and simple answer to your question...
If the LPTask is running, then 'something' must have happened to make the
HPTask runnable.
It is this 'something' that needs to be detected and dealt with by your
scheduler.
'something' might be a timer tick, or an ethernet packet received, or a
button pressed, in which case an interrupt/exception will have occurred. You
will then attach scheduler code to your interrupt service routine and that
will change the program counter to your HPTask.
The reason that you need to get a good book is because so much more needs to
be done for this simple action to occur. The 'required destructible context'
of at least the LPTask and the HPTask must be saved and restored (typically
on a stack). You will also need to consider disabling and restoring
interrupts like this during certain sections of critical code within your
scheduler.

The bottom line is that without an interrupt or exception of some kind,
LPTask will run forever. The Interrupt will typically come from some
external event or timer. The code that deals with the Interrupt is where
your scheduler gets the opportunity to change what is running.

But get a book. :)

Kevin.

Kevin Pope
Nohau UK Ltd.
main site: http://www.nohau.co.uk
Online Store: http://shopnohau.co.uk



Site Timeline