Quality RTOS & Embedded Software

 Real time embedded FreeRTOS RSS feed 
Real time embedded FreeRTOS mailing list 
Quick Start Supported MCUs PDF Books Trace Tools Ecosystem TCP & FAT Training




Loading

v5.3.1 Starved Tasks

Posted by John W. on June 28, 2009
I've tried using the search function - but I guess that either doesn't work so good anymore or I don't know where the one is just to search this forum.

I am using Preemption - and it seems that tasks that are just 1 level difference in priority are getting somewhat starved - has anyone else noticed this?

Thanks,
John

RE: v5.3.1 Starved Tasks

Posted by Richard Damon on June 28, 2009
For a task to get time assigned to it, all task of higher priority need to block, priority is strict. Preemption affects task with exactly the same priority, causing them to run in a round robin manner, it will not force a task to yield to a lower priority task.

RE: v5.3.1 Starved Tasks

Posted by Richard on June 28, 2009
There is a menu system going from left to right at the top of the page, starts "Summary - Tracker - Forums - Code - etc.". If you hover over Forums there is a search link. These forums are a bit crappy but SourceForge are replacing them with a completely new system soon.

Regards.

RE: v5.3.1 Starved Tasks

Posted by Richard on June 28, 2009
V5.3.1 introduced two new ports, but didn't change any of the scheduler code, so I don't think the issue (if there is one) is related specifically to the V5.3.1 version.

John - can you provide a more details of the scenario you are seeing? How many tasks are running, what are their relative priorities?

Regards.

RE: v5.3.1 Starved Tasks

Posted by John W. on June 30, 2009
Richard,

27 tasks running on an MSP430 - maybe that's pushing it...;)

I had priority levels set to 7 - cut that back to 4. I saw tasks with only a different priority 3 vs. 2 getting starved - or at least I think that is what I saw. Kernel reported 27 tasks running.

I guess I should say this as well - the processor I am using has some significant errata - and some is when you are running the debugger with the processor in LPM (low power mode) - so it is not outside of the realm of possibility that the tasks are running but in the debugger it appears they aren't.


RE: v5.3.1 Starved Tasks

Posted by John W. on June 30, 2009
Sorry - somehow the last msg posted before I was finished.

Obviously I can try disabling LPM mode and giving it another try - and/or reduce the # of tasks and see if that affects what is going on.

Thanks,
John

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 3, 2009
Actually this is quite the problem I'm having. FreeRTOS works as described, lower priority does not get any slice of the time unless all higher level tasks block.

I thought it would get a proportional slice of time according to its priority level, but it does not.

So I have a task (which is the main purpose of whole application btw) that needs to run as fast as possible. So I think I have two choices;

1) Delay the task;

Delaying task is in the resolution of SYSTICK interval, which is 1ms at the moment, and even that is said to be faster than necessary. 1ms delay for that task is inacceptable. So this option is not viable.

2) Yield

This looks like the perfect solution. It would request a context switch process others. But this doesn't work as expected. Because I believe that in the context switch, FreeRTOS again choses highest priority task to run.

So what is the best way to build a task that consumes ALL available CPU time while don't let other tasks to starve. Maybe suspend the high priority task, and then resume it from other tasks ?

Besides, I moved my watchdog petting in IDLE task, so that I'm sure that the system runs stable. If a starvation occur (idle never runs) that I reset the device, with the highest priority task turned off. So use can fix the problem. Is this a good idea ?

RE: v5.3.1 Starved Tasks

Posted by Richard Damon on July 3, 2009
A task that want to consume all available cycles and not starve other tasks must be put at the idle priority. Priority doesn't mean how much of the CPU the task will get (at least as far as FreeRTOS), but how urgent the task needs to be run.

Yield only is useful if you have multiple tasks at a given priority.

If you have a task that need to run before some other task, but also wants to consume all available CPU resources, then you have an error in specification, you need to split the task into two pieces, one that needs to be done urgently, but has a finite resource need, and a second that can be placed at idle priority that consumes all available CPU time.

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 3, 2009
Hello Richard,

Thanks again for your prompt and informative reply.

Yes, FreeRTOS scheduler concept is a bit non-traditional with respect to modern OSes, hence the confusion I believe.

Imagine a situation like this;

1) Ethernet task
2) Serial communication task
3) User program

Now, user program needs to run as fast as possible with all available horse power and is very important (the main purpose of the whole application).

If I put this task at a higher priority level, it will consume all CPU and no other tasks can run (SYSTICK rate delay, 1ms, is not acceptable here).

If I put this User Task in the same priority level of other tasks (ethernet, serial) they all will work... but if there's excessive use of ethernet or serial communication they will make User Prog run slower (I don't want this).

If I put User Task in Idle priority level, the above problem will occur again.

What would be the best solution ?

Kind regards,

Engin

RE: v5.3.1 Starved Tasks

Posted by Adam Turowski on July 3, 2009
The answer is that all depends on project requirement.

I would (almost) always assume, that communication tasks are more important, because usually one is after data throughput. So the user program can run on lower priority, and that way it will get all awailable CPU power not affecting throughput of data processed by Ethernet and serial.

If it is your use case please add the estimate of Ethernet and serial cpu power needs and extract it from total available cpu power. This will give you and estimate, how much cpu power user task will get. If it is not enough, you should either consider using faster CPU or changing requirement for projects.

Hope that help,
Adam

RE: v5.3.1 Starved Tasks

Posted by Richard Damon on July 3, 2009
This is a spec issue. The communications tasks will need to have a certain amount of CPU time to do their job. PERIOD. If a message comes in, it must be processed or dropped. It also must be processed within a certain amount of time, or you will over fill your buffers and lose info. If they can not take this much time and still leave enough time for your main task, than you don't have enough CPU to meet your requirements.

One possible solution would be to have the communication tasks (or ISR) see if they are starting to get too many messages in a short period of time, and if so throw away the extra messages and send a "shut up" reply back.

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 3, 2009
In this application the most important thing is the User Programmed task. It checks inputs and performs login on them and update outputs (this are electrical outputs).

If communication has higher priority, they will make the user program slower during heavy communication... hence yield a instable outcome.

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 3, 2009
And Richard,

I want to leave the throttling to the protocol... i.e. TCP will understand that it didn't receive ACK and other end will end up slowing down the connection. Same applies for serial transmission.

Is that non-sense ?

RE: v5.3.1 Starved Tasks

Posted by Adam Turowski on July 3, 2009
I see. So your "user application" is really real time measurement/output stuff. In that case the solution is a follows:
- the actual measurement/outputtind data is done on timer driven interrupt
- processing of these data is done in high priority task
- Ethernet/serial protocols runs as lower priority task and these protocols have to have throttling of data build in.

That way your "user application" task will get as much processing power as it needs and Ethernet/serial task will get the rest and that amount . But Ethernet/serial interface throughput will adapt without loosing the data.

RE: v5.3.1 Starved Tasks

Posted by Richard Damon on July 3, 2009
You have stated that the user program is to run "as often as possible", this is incompatible with it being a high priority task, this implies that if the comm is lower priority then this, that it should be run and it is right that it starves.

I think the issue is the "as often as possible" is incorrect, but should be defined as needing to be run at least at a certain rate. (I am assuming that it is some form of loop that has distinct cycles). If this can be defined, then you can record the time the loop starts, and when a loop finishes, you can see how long you can delay till you need to run again, and delay that long, letting the comm task use that slack. You can also base the time to start the next off of the time you scheduled the last to start + your interval allowed.

If you want it to run faster than this rate if the comms aren't using time, then rather than just delaying, wait on a semaphore for with a may as computed above, and have a small task at idle priority signal the semaphore when it gets time. (The main computation task will want to first take the semaphore with 0 wait, then again with the desired wait to make sure there is time available NOW).

RE: v5.3.1 Starved Tasks

Posted by Adam Turowski on July 3, 2009
It makes sense.

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 3, 2009
Adam exactly!

My previous design was to run the user app via a timer interrupt. While it is a rock-solid solution it has its draw backs. In our application user can download both very small and very big applications. And unless you do some complex design you'll end up configuring your timer for the biggest application.

i.e. smallest app could take 30us and you can run it via 20KHz timer. In that case it will consume 60% CPU and everything is fine.

But a bigger program can take 200us... so you have to run it in around 4KHz timer.

So you are bound to worst case with that design and you'll end up running user prog like at 4KHz and a small program could (which could be run much more faster) will be bound to that speed.

To overcome this drawback, I thought I could run the user app in a task so it will use as much as possible. But I think the scheduler is not very suitable for this kind of design.

Kind regards,

Engin

RE: v5.3.1 Starved Tasks

Posted by Richard Damon on July 3, 2009
I can see a couple of possible solutions to your problem.

1) Put comm task above user in priority, and add code there to limit CPU that can be taken with forced waits.

2) Make the user define a repeat period they want from their program, and if it starves the I/O accept it or back off the rate some.

3) Have a wrapper around the user task and measure the time it takes and adjust the rate it runs at based on this (something like wait for 10% of the time it took to run that loop, that give 90% to the user and 10% to comm)

RE: v5.3.1 Starved Tasks

Posted by Richard on July 3, 2009
> Yes, FreeRTOS scheduler concept is a bit non-traditional with
> respect to modern
> OSes, hence the confusion I believe.


It’s a fixed priority preemptive scheduler - about as traditional as you can get for this class of RTOS. [fixed priority meaning the scheduler does not change the task priorities itself, not that application writers cannot change the priority].

Regards.

RE: v5.3.1 Starved Tasks

Posted by Adam Turowski on July 3, 2009
I would go for third solution because:
- it needs almost no additional user involvement than providing task code
- it allows you to easily adapt to (almost) any user aplication giving the best performance
- your program still controls everything and can preserve say 10% of CPU for transmission tasks. It can also output the user message saying: "Your task is running with speed x kHz". If it is not acceptable for user, he can refactor his code.

This is my personal opinion. The final solution of course depends on specification. And last thing: scheduler is really applicable to this kind of solution.

Regards,
Adam

RE: v5.3.1 Starved Tasks

Posted by Richard on July 3, 2009
I'm quite confused by some of the statements in this thread. The CPU provides a certain amount of power - either it is fast enough to run the user task and the comms tasks or it isn't.

Using a kernel adds an overhead in that there is a tick interrupt, but can also save a whole lot of CPU cycles by allowing your application to be completely event driven - any cycles that would otherwise be spent polling are freed for other processing. On balance whether you get more or less grunt from using a kernel depends on the application, but generally on a well designed event driven system you will get more processing done with the kernel.

If the user task must run "as fast as possible" then this is a really soft real time requirement, as it means it does not need to run at all if its impossible for it to get CPU processing.

If on the other hand it needs to run whenever an event occurs then you need to specify how often the event can occur, and what the response time must be along with how long it would take in the worst case to respond to the event.

If on yet another hand it needs to run at a certain frequency then you need to say what that frequency is.

If the required execution frequency is in the KHz range then I would suggest using a port that implements efficient interrupt nesting. For example any of the Cortex M3 ports. Some of the M3 demos run a 20KHz timer in an interrupt that has a priority above the priority used by the kernel (note here I'm talking about interrupt priorities, not task priorities). That works just fine. The tasks then run whenever the interrupt is not running.

If the required frequency is in the 10's of ms then a scheme whereby a task runs periodically using vTaskDelayUntil() might be a simpler solution.

Regards.

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 3, 2009
Third solution suggests adjusting the rate of task. Is there such a thing ? Or do you mean rate of the hardware timer interrupt ?

This is what I mean by complex stuff btw.

To make such a measurement I'd need a hardware timer to keep track of the time in micro seconds. Do-able.

I started to embrace dynamically adjusting timer frequency.

Hardware timers are perfect for many many things. Only problem it has is the fixed frequency rate was inefficient for small programs.

Tasks are good, as it will automagically adopt itself to best performance. But it turned out that I cannot let other processes to run for a very short period of time, that is due to time resolution of systick which is 1khz at the moment, and even that is considered very high for FreeRTOS.

I'm losing the line where it starts being Real Time and where not. It looks like _I_ could not create the real-time application I needed with FreeRTOS.

And I think the hardware timer interrupt with adjustable frequency looks like a more stable way to go.

Kind regards,

Engin

RE: v5.3.1 Starved Tasks

Posted by Richard Damon on July 3, 2009
Since your delays sound like they are going to be shorter than your main timer tick, have your user task delay by waiting on a semaphore, and have a second higher speed timer signal that semaphore when it is time for the user task to run.

You could then even drop the rate of the system timer tick, as you don't really need a small time slice for anything, the limiting factor will be what resolution delays the comm tasks will need.

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 3, 2009
You mean; make the user program task highest priority and block it using a semaphore. So that I can signal the task to unblock from a high frequency hardware timer ? And if it needs to be waken up the FreeRTOS will immediately issue a context switch upon the return of the timer ISR. Via portEND_SWITCHING_ISR( xSwitchRequired ).

Is that so ?

RE: v5.3.1 Starved Tasks

Posted by Adam Turowski on July 3, 2009
Yes.

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 6, 2009
Hmm. Now that I've started implementing this I've noticed that this approach will also starve other tasks also just like other approach we have talked earlier.

Imagine I'm waking up the user task in every 250us with timer interrupt. If the execution of the user task took longer than that. It will be immediately executed again once it is over, since it is the highest priority task. If this is the case, this is not a robust design. Right ?

Kind regards,

Engin

RE: v5.3.1 Starved Tasks

Posted by Engin AYDOGAN on July 6, 2009
I think one last approach, maybe the simplest, could be to use a one-shot timer to provide a finer resolution vTaskDelay functionality.

i.e. in every loop-end of the user-task, I'll initiate a one-shot timer, that will unblock the next loop round. So my user-task will wait, say, 50us all the time.

This looks like a good idea, right ?

Only disadvantage will be that that 50us could be a waste of time on some occasions, hence lower efficiency.

RE: v5.3.1 Starved Tasks

Posted by Adam Turowski on July 6, 2009
No, it is not robust. Thats why it have been suggested to go for adaptive scheme to avoid that kind of situation. It seems that you cannot rely on how long user application execute and if this time is relatively constant.

Personally I would do two things to get around that:
1) I would create global variable (flag), which would be increased every time idle task is called. It could be done in vAplicationIdleHook().
2) I would create the monitoring task with highest prority in the system (higher that user app task). This task has to be executed say every 50ms and it checks the value of flag variable, clearing it afterwards. If the value is greater that zero, it means that idle task has been executed and there was no task starving. In that case timer period can be decreased. If this value is zero it means that there is starving and timer period has to be increased.

Of course you should start with relatively large timer period.to prevent starving at the beginning. Then whole system will adapt and provide you the best achievable performance.

Hope that helps,
Adam

RE: v5.3.1 Starved Tasks

Posted by John W. on July 7, 2009
>> Yes, FreeRTOS scheduler concept is a bit non-traditional with
>> respect to modern
>> OSes, hence the confusion I believe.


> It’s a fixed priority preemptive scheduler - about as traditional as you can get for this class >of RTOS. [fixed priority meaning the scheduler does not change the task priorities itself, not >that application writers cannot change the priority].

>Regards.

If a fixed priority preemptive scheduler starves tasks that are n-1in priority, with n being the highest priority - then you have a round-robin scheduler (at n). I think this is what I am seeing.

Here's a great link that explains the differences in schedulers - I am providing this as a reference and not as a direct response to Richard -

http://www1bpt.bridgeport.edu/sed/projects/cs503/Spring_2001/kode/os/scheduling.htm

I know I've seen this asked before - but if you have say, 27 tasks, and 7 priorities, is that better or worse than having 27 tasks, and 4 priorities? Will the tasks running at priority 7 and 4 respectively always starve tasks scheduled with priority 1?

Thanks,
John

RE: v5.3.1 Starved Tasks

Posted by Richard Damon on July 7, 2009
Fixed priority means that the highest priority tasks get the cpu when they ask for it. It WILL cause starvation of lower priority tasks if the higher priority tasks ask for all the CPU time, just like that article talks about. Priority N will ALWAYS run before priority N-1, if it is available to run.

How many priority levels do you need, well that depends on your application. Tasks that should share the CPU using round robin scheduling should be at the same priority. tasks that should interrupt another as soon as they are ready to run should be at distinct levels in order of priority.

RE: v5.3.1 Starved Tasks

Posted by John W. on July 8, 2009
I must be missing something in this discussion - what is the point of having priorities if it is guaranteed that n-1 will be starved? This is the same as round-robin and makes priorities moot, doesn't it.

I thought the intent of the preemptive scheduler in FreeRTOS was to be a bit more cooperative - giving time slices to lower priority tasks. What am I missing here?

Thanks,
John

RE: v5.3.1 Starved Tasks

Posted by Richard Damon on July 8, 2009
n-1 will get starved only if n uses all available time. In most systems, the higher priority task do short important tasks, and the lower priority tasks do longer operations which are less time critical. The Fixed Priority system has the advantage of simplicity, and is sufficient for many applications. There are other scheduling algorithms used in real time systems like nearest deadline, that may give better results but require more planing. A scheduling system that would keep a priority n task from staving the n-1, would tend to actually have poorer real time performance, as it is harder to make sure the high priority task completes in time.

Preemptive actually means that higher priority tasks get more priority, as the high priority task will start as soon as it becomes ready, even if this requires "preempting" the lower priority task in the middle of its work. The alternative are "Cooperative" scheduling, where tasks need to periodically yield control, giving what ever task now is the highest priority ready task. Cooperative systems are simpler, and sometimes faster as you don't need to worry about as many synchronization issues, it does suffer from more latency for the high priority task as they need to wait for the next yeild before they can start.

RE: v5.3.1 Starved Tasks

Posted by Richard on July 8, 2009
There are three main types of task:

1) Periodic. Runs at a fixed frequency, remaining in the blocked state (allowing other tasks to run) when its not running. If the frequency has to be very accurate then it needs to be a high priority. If its timing requirements are not so strict then it can be a lower priority.

2) Event driven. Unblocks and does something only when necessary (maybe a data packet arrived, or somebody pressed a button). When its not processing an event it remains in the blocked state and allows lower priority tasks to run. The important thing here is polling should be avoided as it wastes CPU time. The faster the response needs to be the higher the event driven task priority should be.

3) Continuous processing tasks. These are tasks that always have something to do and are therefore always in the ready state - meaning tasks of lower priority will not run but tasks of equal priority will time slice. Continuous processing tasks are very rare.

Regards.


[ Back to the top ]    [ About FreeRTOS ]    [ Sitemap ]    [ ]




Copyright (C) 2004-2010 Richard Barry. Copyright (C) 2010-2016 Real Time Engineers Ltd.
Any and all data, files, source code, html content and documentation included in the FreeRTOSTM distribution or available on this site are the exclusive property of Real Time Engineers Ltd.. See the files license.txt (included in the distribution) and this copyright notice for more information. FreeRTOSTM and FreeRTOS.orgTM are trade marks of Real Time Engineers Ltd.

Latest News:

FreeRTOS V9.0.0 is now available for download.


Free TCP/IP and file system demos for the RTOS


Sponsored Links

⇓ Now With No Code Size Limit! ⇓
⇑ Free Download Without Registering ⇑


FreeRTOS Partners

ARM Connected RTOS partner for all ARM microcontroller cores

Renesas Electronics Gold Alliance RTOS Partner.jpg

Microchip Premier RTOS Partner

RTOS partner of NXP for all NXP ARM microcontrollers

Atmel RTOS partner supporting ARM Cortex-M3 and AVR32 microcontrollers

STMicro RTOS partner supporting ARM7, ARM Cortex-M3, ARM Cortex-M4 and ARM Cortex-M0

Xilinx Microblaze and Zynq partner

Silicon Labs low power RTOS partner

Altera RTOS partner for Nios II and Cortex-A9 SoC

Freescale Alliance RTOS Member supporting ARM and ColdFire microcontrollers

Infineon ARM Cortex-M microcontrollers

Texas Instruments MCU Developer Network RTOS partner for ARM and MSP430 microcontrollers

Cypress RTOS partner supporting ARM Cortex-M3

Fujitsu RTOS partner supporting ARM Cortex-M3 and FM3

Microsemi (previously Actel) RTOS partner supporting ARM Cortex-M3

Atollic Partner

IAR Partner

Keil ARM Partner

Embedded Artists