Forums

RTOS scheduler development

Started by brOS September 7, 2009
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
On Mon, 07 Sep 2009 16:13:44 -0500, "brOS" <bogdanrosandic@gmail.com>
wrote:

>I am new here, and I would like to ask something about implementing >fixed-priority preemptive scheduling(rate monotonic aproach) on MSP430 >family.
From the rest of your post, I'm assuming by "fixed-priority" you don't mean to include equal priorities as a possibility.
>Can anyone tell me what is usual way to implement call of scheduler's >dispatcher?
Yes.
>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.
Ask yourself, "How does it 'become ready?'"
>As I understand in that moment scheduler's dispatcher which >is used for context switching should be called.
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.
>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?
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
On 2009-09-07, brOS <bogdanrosandic@gmail.com> wrote:
> 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.
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: http://www.amazon.com/MicroC-OS-II-Kernel-CD-ROM/dp/1578201039 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. --
On Mon, 07 Sep 2009 16:13:44 -0500, "brOS" <bogdanrosandic@gmail.com>
wrote:

>Can anyone tell me what is usual way to implement call of scheduler's >dispatcher?
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
brOS wrote:
> Can anyone tell me what is usual way to implement call of scheduler's > dispatcher?
"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)
"brOS" <bogdanrosandic@gmail.com> wrote in message 
news:I_Wdnb57x4kV6jjXnZ2dnUVZ_g2dnZ2d@giganews.com...
> 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
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