Preemption by an equal priority task

marc7 wrote on Friday, February 02, 2018:

Hello everyone,

I’m using the following configuration:

#define configUSE_PREEMPTION    1
#define configUSE_TIME_SLICING  0

With this configuration, and a system where all the tasks have the same priority, I was expecting that the scheduler would never trigger a context switch unless a task explicitely blocks itself. But this is not what I am observing. By digging into the code, I found that the “xTaskIncrementTick” function, which is called by the Tick interrupt handler, was triggering a context switch when a delayed task of higher or equal priority was unblocked. Below is a copy of the involved code in tasks.c:

				/* A task being unblocked cannot cause an immediate
				context switch if preemption is turned off. */
				#if (  configUSE_PREEMPTION == 1 )
				{
					/* Preemption is on, but a context switch should
					only be performed if the unblocked task has a
					priority that is equal to or higher than the
					currently executing task. */
					if( pxTCB->uxPriority >= pxCurrentTCB->uxPriority )
					{
						xSwitchRequired = pdTRUE;
					}
					else
					{
						mtCOVERAGE_TEST_MARKER();
					}
				}
				#endif /* configUSE_PREEMPTION */

Please note that giving a semaphore from an interrupt service routine might unblock a waiting task but will never preempt the current task if the unblocked task has equal priority.

his confuses me and I’m wondering what the really expected behavior is. Should a task be able to preempt another task of equal priority?

Thank you in advance for your answer.

Marc

rtel wrote on Friday, February 02, 2018:

#define configUSE_PREEMPTION 1

With this setting you have left preemption turned on. That means the
scheduler will always run the highest priority task that is able to run.
So if a delayed task becomes able to run (its delay period expires),
and if that delayed task has a priority above the currently executing
task, then it will get selected to run - which is what you are observing.

#define configUSE_TIME_SLICING 0

With this setting you have turned time slicing off. If time slicing
were on then tasks of equal priority that are ready to run will share
CPU time by being switched in and out on each tick interrupt - the tick
period being the length of the time slice. That won’t happen if time
slicing is turn off - but that does not effect any other scheduling
decisions.

marc7 wrote on Friday, February 02, 2018:

Hi Richard,

Thank you for replying.

Actually, my concern is that I observe that my task is preempted by another task of equal priority. I agree that it can be preempted when another task of higher priority becomes ready, but not another task of equal priority…

rtel wrote on Friday, February 02, 2018:

The only thing you have turned off is time slicing. That means tasks of
equal priority that are already in the ready state won’t time slice. No
other scheduling decisions are effected. In this case you have a task
entering the ready state, so it is not effected by the time slicing setting.

alemannia wrote on Monday, February 05, 2018:

Hi Richard,

Let’s put time slicing apart because that’s not something we want to use. The actual question is about scheduling policy in preemptive mode. Imagine we have 2 tasks with the same priority. Task A is running a lengthy computation and task B is sleeping. When the sleep time of task B expires, it seems that it will wake up and then preempt taks A. That’s what we deduce from the equal sign in the following condition

if( pxTCB->uxPriority >= pxCurrentTCB->uxPriority )

In our previous kernel (VDK) only taks with higher priority could preempt tasks with lower priority, like this:

if( pxTCB->uxPriority > pxCurrentTCB->uxPriority )

Tasks with equal priority did not preempt the currently running task.
Do I understand FreeRTOS preemption policy correctly or did I miss somting?

huska6 wrote on Monday, February 05, 2018:

Hi Richard,

we have seen recently the same behavior.

in the history https://www.freertos.org/History.txt

there is

Changes between V7.6.0 and V8.0.0 released 19th Feb 2014

http://www.freertos.org/upgrading-to-FreeRTOS-V8.html

Other updates:

+ Previously, when a task left the Blocked state, a context switch was
  performed if the priority of the unblocked task was greater than or equal
  to the priority of the Running task.  Now a context switch is only
  performed if the priority of the unblocked task is greater than the
  priority of the Running task.

But this seems to be not true, because also the equally prioritized tasks can preempt others at timeouts.

Could you pelase clarify teh behavior?

Thanks
Regards
Jiri

rtel wrote on Monday, February 05, 2018:

Yes - I remember that change. I will have to check through the source
and release history to see what the situation is. It might be that
change effects context switches in places other than the tick interrupt
(for example, when a queue or semaphore causes a task to unblock) and
that the case in the tick interrupt was never updated. In any case I
will report back.

rtel wrote on Wednesday, February 07, 2018:

Quick update on this:

Looking at the code for current version the tick interrupt is not the
only place where a context switch occurs if the priority is greater than
or equal to - it seems to be the norm. Looks like the change was
reverted at some point and now the tests rely on it. I’m sat on a plane
at the moment and can’t check the other versions from here, but will do
when I’m able.

alemannia wrote on Friday, February 09, 2018:

Hi Richard,

Thanks for the information so far. It would be really interesting to know the motivation for reverting the scheduling policy back to “greater than or equal” instead of “greater than”.

huska6 wrote on Friday, February 16, 2018:

Hi Richard,

thank you fro addressing this issue.
could you please update us on this topic?

Thanks,
BR, Jiri

marc7 wrote on Tuesday, March 06, 2018:

Hi Richard,

Any news about this topic?

Thanks!
Marc

rtel wrote on Tuesday, March 06, 2018:

The change history says the change was made between V7.6.0 and V8.0.0,
so they are the two files I’m comparing, and it looks like the only
place the code was changes was in regards to when a context switch is
performed is in xTaskRemoveFromEventList() - and that change remains in
V10.0.1, so it wasn’t reverted. In which case the change history is
misleading.

xTaskRemoveFromEventList() is called when an event occurs on an object
(queue, semaphore, event group, mutex, etc.) that has a task blocked
waiting for the event. In V7.6.0 a context switch will occur if the
task that was waiting for the event has a priority greater than or equal
to the task that is currently running, whereas in V8.0.0 a context
switch will only occur if the task that was waiting for the event has a
priority higher than the currently executing task.

marc7 wrote on Friday, March 23, 2018:

Hi Richard,

Thank you for looking at the change history.

So what I understand is that xTaskRemoveFromEventList() has been changed not to do a context switch when the task that was waiting for the event has the same priority as the task that is currently running. Am I right?

In this case, why don’t we do the same change in the xTaskIncrementTick() function, which precisely sometimes do a context switch to execute a task that has the same priority as the currently running task? Wouldn’t it be more consistent?

Thanks!

Marc

huska6 wrote on Friday, March 23, 2018:

Hi Marc, Richard,

I totally agree with Marc - if one principle is applied, it should be applied everywhere.

Thanks for considering this idea.

BR, Jiri

richard_damon wrote on Friday, March 23, 2018:

Changing tasks on the tick to another one of equal priority should be control by the time-slicing option, as that is specifically what time slicing is. If the tick interrupt changes to a task of the same priority when time slicing is off, that would sound like a bug.

rtel wrote on Friday, March 23, 2018:

So what I understand is that xTaskRemoveFromEventList() has been changed
not to do a context switch when the task that was waiting for the event
has the same priority as the task that is currently running. Am I right?

Looking back, this was done to prevent thrashing back and forth in cases
where, for example, two tasks are using a mutex in a tight loop (not a
good thing to do in any case) - it was very wasteful of CPU time.

In this case, why don’t we do the same change in the
xTaskIncrementTick() function, which precisely sometimes do a context
switch to execute a task that has the same priority as the currently
running task? Wouldn’t it be more consistent?

[I think as already pointed out] incrementing a tick is a different
scenario to unblocking a task due to an event (queue write, etc.) - it
can only happen on a time slice boundary.

huska6 wrote on Monday, March 26, 2018:

Hi All,

If the tick interrupt changes to a task of the same priority when time slicing is off, that would sound like a bug.

I beleive this is the case we discuss about

BR jiri

rtel wrote on Monday, March 26, 2018:

Inside the tick interrupt, if a task is removed from the blocked list,
and that task has the same priority as the currently running task, and
configUSE_PREEMPTION is 1, then a switch to the unblocked task will
occur. This task switch is not performed because of a time slice, but
because of pre-emption (as per the discussion in this thread about
whether this was change to “greater than” or “greater than or equal to”
the currently executing task). See line 2684 (at the time of writing):
https://sourceforge.net/p/freertos/code/HEAD/tree/trunk/FreeRTOS/Source/tasks.c

Inside the tick interrupt, regardless of which task is executing, if
there is another task at the same priority as the currently executing
task, and configUSE_PREEMPTION and configUSE_TIME_SLICING are both 1,
then a context switch is performed - this is the switch caused by having
configUSE_TIME_SLICING set to 1 - if configUSE_TIME_SLICING is set to 0
then a new task will not be selected just because there are other tasks
at the same priority as the running task. See line 2707 (at the time of
writing) on the same link.

christophe-p wrote on Wednesday, March 06, 2019:

Sorry to come back to this thread but I don’t understand the conclusion and I have the same question.
When I read the comment and the code of the line 2684 (2755 in the last version 10.2.0), it is indicated that it could be a switch context with an other task of the same priority although the configUSE_TIME_SLICING is not enabled. Is it right ?

rtel wrote on Wednesday, March 13, 2019:

[sorry for delayed reply - due to this going into arbitration for some
reason - never worked out why that happens as I have that feature turned
off]

Not read through the whole thread again, just this post, and line
numbers refer to V10.2.0.

There is a difference between a context switch occurring because a task
is unblocked (lines 2755 to 2770) and a context switch occurring simply
because a task has come to the end of its timeslice and there are other
tasks of equal priority (lines 2778 to 2789). As the code is the first
will happen regardless of whether time slicing is on or off, the second
won’t.

There is a question as to whether line 2761 (if( pxTCB->uxPriority >=
pxCurrentTCB->uxPriority )) should instead use > rather than >= but it
could be argued either way I think.