#139 suspend()/resume() not enough for writing other synchronisation objects

[Liviu Ionescu (ilg)]

While working on the implementation of the CMSIS++ RTOS API over FreeRTOS, I translated most of the calls to native FreeRTOS calls, and everything worked as expected, but I also had to implement some objects which are not available in FreeRTOS.

The initial code looked like this:

wait()
{
    ...
    list.add(node);
    suspend();
    list.remove(node);
    ...
}

// Can be called from ISRs, and may occur at any time.
notify()
{
    ...
    if (!list.empty())
        list.top().resume();
    ...
}

Unfortunately, this did not work. If notify() occurs right after add(), but before suspend(), the notification seems lost for ever.

If my understanding of the problem is correct, then it is a common mistake in schedulers, caused by a lack of atomicity which allows resume() to occur right before suspend() coupled with the decision to keep the running task in the ready list. If this is the case, resume() either does not identify the thread as suspended, or already finds it in the ready list, and generally it is ineffective. But the real problem is the implementation of suspend(), which, if done carelessly, and if the running thread is kept in the ready list, removes it and, if no other notify() or timeout follows, the tread will sleep forever.

The solution requires to group in a critical region the add() with suspend(), but since suspend() itself does a reschedule, it is a bad idea to use a critical region that spans over scheduling points (it is not necessarily a mistake, my previous RTOSes were able to do this, but I agree that this is not nice).

My workaround was to split the vTaskSuspend() in its two functional parts, vTaskPrepareSuspend() to handle the part that removes the thread from the ready list and vTaskPerformSuspend() to perform the context switch.

The new code looks like this:

wait()
{
    ...
    critical.enter();
        list.add(node);
        prepare_suspend(); // -> vTaskPrepareSuspend()
    critical.exit();
    reschedule(); // -> vTaskPerformSuspend()
    list.remove(node);
    ...
}

With such a code there seem to be no more notifications lost.

Other solution would be to address the removal of the thread during suspend(); this requires a counter per thread, cleared when the thread becomes the current thread, and incremented by resume(); if suspend() finds this count set, it no longer removes the current thread from the ready list.

An even better solution is to no longer keep the current thread in the ready list, but remove it when the thread is running, and add it via resume(), but this depends on the scheduler design.

As a general remark, I think that these kind of problems occurs when the RTOS does not maintain a clear separation between the scheduler and the synchronisation objects, and uses direct, internal calls to implement the synchronisation objects, while publishing a public API (resume()/suspend()) that is actually not functional.

One of the goals of CMSIS++ RTOS API was to also define such a portable scheduler API to allow writing portable synchronisation objects, that do not depend on a specific scheduler.

Given the experience with FreeRTOS, the current API using two separate functions (prepare_suspend()/reschedule()) plus resume(), seems to cover most usual cases.

You can view the current version of tasks.c at

https://github.com/xpacks/freertos/blob/xpack/FreeRTOS/Source/tasks.c

(in the history page you can view the diffs).

Since this problem affects the ability of writing new synchronisation objects using FreeRTOS, I would qualify it as a design problem that needs to be addressed.

If you come with a better idea than splitting suspend() into two calls, I'm open to any suggestions.

Regards,

Liviu

[Richard Barry]

Preamble - suspending a task is performed extremely rarely, and is definitely NOT intended as a task synchronisation mechanism - as attempting to use it as such has potential application level race conditions. This is discussed in the book I think, definitely in the training classes, and hinted at here: http://www.freertos.org/taskresumefromisr.html [this is a very old documentation page, but notes "xTaskResumeFromISR() should not be used to synchronise a task with an interrupt if..."]. The reason for this is that 'resumes' are not latched, whereas synronisation using something such as a task notification, or semaphore, is latched. If a certain circumastance leads to a sequence of Resume->Suspend, where the resume is intended to resume a task that is not yet suspended, then it won't work. Whereas if there is a sequence of SemaphoreGive->SemaphoreTake (or the direct to task notification equivalent) then it will work as giving the semaphore keeps the semaphore available for when the take is performed (hence my use of the term 'latched').

Your text is a bit over my head - so lets take it one step at a time. First I need to understand the issue you are having with the current implementation - which removes a task from the ready list and adds it to the suspended list as a [pseudo] single operation [due to the critical section]:

taskENTER_CRITICAL();
{
  pxTCB = prvGetTCBFromHandle( xTaskToSuspend );

  if( uxListRemove( &( pxTCB->xGenericListItem ) ) == ( UBaseType_t ) 0 )
  {
    taskRESET_READY_PRIORITY( pxTCB->uxPriority );
  }

  /* Is the task waiting on an event also? */
  if( listLIST_ITEM_CONTAINER( &( pxTCB->xEventListItem ) ) != NULL )
  {
    ( void ) uxListRemove( &( pxTCB->xEventListItem ) );
  }

  vListInsertEnd( &xSuspendedTaskList, &( pxTCB->xGenericListItem ) );
}
taskEXIT_CRITICAL();

When the critical section is exited it is possible for a context switch to occur immediately. That would happen if, for example, a tick interrupt was pending. If a context switch does not occur then the suspended task is still executing so a context switch away from the now suspended task is performed.

if( pxTCB == pxCurrentTCB )
{
  if( xSchedulerRunning != pdFALSE )
  {
    portYIELD_WITHIN_API();
  }
else
{
}

[Liviu Ionescu (ilg)]

suspending a task is performed extremely rarely, and is definitely NOT intended as a task synchronisation mechanism

if suspend() should not be used, resume is present in two variants (for suspended threads and for timeouts) but there is not way of telling the difference, then what is left, in terms of a clear, public APIs allowing to write custom synchronisation objects?

If a certain circumastance leads to a sequence of Resume->Suspend, where the resume is intended to resume a task that is not yet suspended, then it won't work.

the problem here is not "If a certain circumstance leads to a sequence of resume() -> suspend()", the problem is that there is no way of preventing this, because it would require a critical section like this:

wait()
{
    ...
    critical.enter();
        list.add(node);
        suspend();
    critical.exit();
    list.remove(node);
    ...
}

First I need to understand the issue you are having with the current implementation - which removes a task from the ready list and adds it to the suspended list as a [pseudo] single operation [due to the critical section]:

I don't have a problem with it, this part is fine, if you would read carefully the original message you would discover I named this part vTaskPrepareSuspend(), and I use it in a critical section with my add(node).

from your answer it looks like you did not get the question.

if my text is ambiguous, I can rephrase, but perhaps you could read it again, and point me exactly where you do not understand.

or, if you want another approach, you can imagine you need to write a new synchronisation object (for example a memory pool), and you have to do it only with the publicly available API. there are good chances that you won't be able.

the message explained exactly the problems I faced while implementing such an object, the reasons why these problems occured (you call it non-latching resume()), and the workaround I found, to split suspend() into two parts, workaround that seems fully functional.

[Richard Barry]

Ok, so maybe I'm being dumb here - although currently I'm thinking this is a feature request, not a bug.

From your original post:

but I also had to implement some objects which are not available in FreeRTOS

Could you give an example of one such object. You mention memory pools in your second post, and I've seen the memory pool documentation on the link you gave, but I'm not sure how that is a synchronisation object. For example, one of the buffer allocation schemes in the TCP/IP stack is basically a memory pool and a counting semaphore is used to manage access to the resources - one count for each available buffer - then if a task attempts to obtain a buffer from an exhausted pool where the semaphore count is zero it automatically enters the Blocked state and automatically unblocks if a buffer is returned as the semaphore's count is incremented.

wait()
{
    ...
    list.add(node);
    suspend();
    list.remove(node);
    ...
}

What is this? I am assuming it is a generic template for a synchronisation object, where wait() would be "wait for object type X" or "wait for object type Y". Annotated it might then look like:

wait()
{
    ...
    // Add the calling task to the list of tasks waiting for object X.
    list.add(node);
    // Suspend the task because now it is waiting for object X so can't run.
    suspend();
    // If code after suspend() executes then the task must be unsuspended
    // so remove it from the list of objects that are waiting for object X.
    list.remove(node);
    ...
}

// Can be called from ISRs, and may occur at any time.
notify()
{
    ...
    // Object X is available, if there is a task waiting for it then...
    if (!list.empty())
        // Resume the task, so it then gets removed from the list waiting for
        // the object as annotated in the wait() function above.
        list.top().resume();
    ...
}

I will wait for your comments on that so far, because if I'm wrong here then everything else I might write from here on will be a waste of typing...

Conversation only below here:
The RTOS is designed to be self contained, rather than provide public functions that allow it to be extended. There are a few cases however where it can be extended - for example if you want to create your own non-portable low power tickless function then there is a callback you can implement, and that callback manages sequencing using a scheduler lock (suspends the scheduler). If my annotation in this code within this post is what you intend then it might be that the same can be done here. Also, it might be that the task is removed from the list of tasks waiting for object X within the notify() function rather than in the wait() function - which is I think how the existing notify equivalents work.

Also, if the issue is you can't tell if something is suspend, and should therefore be resumed, or block, and should therefore be aborted, something could be put into the code that gives you that information.

[Liviu Ionescu (ilg)]

I'm thinking this is a feature request, not a bug.

well, my original understanding of suspend()/resume() was that these are the scheduler primitives for building synchronisation objects on top of them. from this point of view, this was a bug, since they do not provide the expected functionality.

if you explictly deny using them for this purpose, then, yes, this might be reclassified as a feature request, to provide a different set of primitives for the scheduler basic API.

The RTOS is designed to be self contained, rather than provide public functions that allow it to be extended.

and how should this be considered, a feature or a bug?

with CMSIS++ I planned for a more generic, neutral and portable approach, and this implies the scheduler to provide a simple API.

I'm convinced such an API can be designed, and I think it can be done in such a way to not impact performances in any way. (not using such an API is as strange as a shoemaker wearing other ones shoes ;-) )

with a scheduler that does not keep the current thread in the ready list (my personal view on schedulers), the two functions suspend()/resume() are enough, since resume() will simply add the thread to the ready list, and it doesn't matter if it does it before or after suspend().

trying to apply this concept to FreeRTOS failed, since suspend() removes the current thread from the ready list, and its resume() is not latched, so the combination is affected by a race condition.

Could you give an example of one such object?

any object you can imagine. we are talking about a generic scheduler API, that should allow writing any synchronisation object.

a memory pool and a counting semaphore

yes, sure, you can always compose some objects from other objects, but this is not the point, since it will not help identifying the generic scheduler API.

in this specific case, I decided to implement the memory pool with the same API as the other POSIX inspired functions (alloc(), try_alloc(), timed_alloc()) and to make them all similar to the other standalone, portable, synchronisation objects.

the same applies for the rest of the portable CMSIS++ synchronisation objects, they are present in CMSIS++ as reference. the user can choose to use either the objects provided by the actual RTOS running beneath CMSIS++, or the portable objects, the selection being done with a simple define.

this mechanism is actually fully functional for the version of CMSIS++ running on top of FreeRTOS.

I will wait for your comments on that so far,

the annotations are generally right. the generic object may be a queue, a mutex, a semaphore, etc.

when the requested resource is not available, the current thread is added to a waiting list. when the resource becomes available, one or all threads in the waiting list are notified.

the complete case is actually slightly more complex, since the thread should be added to two lists, the waiting list and the clock timeout list. regardless how the thread is resumed, the corresponding node is removed from the list, but when suspend() returns, the other list should be cleared too.

the full code looks like:

wait(duration_t timeout)
{
    Waiting_node thread_node{this_thread::thread()};
    Timeout_node timeout_node{this_thread::thread(), timeout};

    // Add the calling task to the list of tasks waiting for object X.
    waiting_list.add(thread_node);
    // Add the calling task to the clock list.
    clock_list.add(timeout_node);

    // Suspend the task because now it is waiting for object X so can't run.
    suspend();
    // The thread returned, either the resource is available or timeout.

    // Remove the node from the clock list, if not already removed by timeout
    clock_list.add(timeout_node);
    // Remove the node from the waiting list, if still there
    waiting_list.add(thread_node);
    ...
}

(NB: although not relevant for the discussion, please note that the two list nodes are allocated on the thread stack, they are perfectly safe here until the function returns).

your own non-portable low power tickless function then there is a callback you can implement ... If my annotation in this code within this post is what you intend then it might be that the same can be done here.

nope, the goal is much more generic than the low power tickless functionality you mention.

Also, if the issue is you can't tell if something is suspend, and should therefore be resumed, or block, and should therefore be aborted, something could be put into the code that gives you that information.

not exactly.

once again, I already solved the problem, I have a fully functional port of CMSIS++ running on top of FreeRTOS, with each object running either as FreeRTOS native or via my portable implementation.

for this I added a few functions to tasks.c (github.com), and they seem to work very well.

my generic interface originally included suspend()/resume(), but since this does not work with FreeRTOS, I adjusted my design to use a more generic prepare_suspend()/reschedule()/resume().

since you expressed some initial interest on CMSIS++, I thought it is fair to inform you about the progress, and ask your oppinion about the implementation, being fully open in case you have a better suggestion.

if this was a misunderstanding and you are not interested in having the best possible CMSIS++ port running on top of FreeRTOS, no problem, I can manage.

(same for the #127, where my generic critical sections collided with yours).

[Liviu Ionescu (ilg)]

a small correction, in the last code sample, after suspend(), the calls should read:

...

   // Remove the node from the clock list, if not already removed by timeout
    clock_list.remove(timeout_node);

    // Remove the node from the waiting list, if still there
    waiting_list.remove(thread_node);

 ...

[Richard Barry]

if this was a misunderstanding and you are not interested

Of course I'm interested, otherwise I won't be spending this time trying
to understand what it is you want/require.

well, my original understanding of suspend()/resume() was that these are
the scheduler primitives for building synchronisation objects

I don't think the existing implementation uses them for that purpose
anywhere.

and how should this be considered, a feature or a bug?

I consider it to be a unique use case that nobody has wanted before.
The normal use case is to use the API to create an application, not use
the API to extend the functionality - hence it might take some work to
provide you with what you need. FreeRTOS does what you want,
internally, but does not expose it to the public API. For example the
functions that 'add to event list' and 'remove from event list' are file
scope only. It might be that public interfaces to these implementation
details could be created.

More soon...

[Liviu Ionescu (ilg)]

FreeRTOS does what you want, internally, but does not expose it to the public API.

that's obvious, since it works very well, I have no problem with this, actualy this was the reason I chose to use it as the first implementation for CMSIS++, to be sure I don't have to chase bugs in other parts than my own code. ;-)

For example the functions that 'add to event list' and 'remove from event list' are file scope only. It might be that public interfaces to these implementation details could be created.

if that would be useful, sure, why not.

however, for my specific need, these interfaces might not be very useful, I already keep such waiting lists and clock timeout lists, portably and scheduler neutral, all I need is a reliable way to suspend and resume threads, without risking any race conditions.

[Richard Damon]

If I understand what you are asking for, it sounds like you have a fundamental difference in process model.

If FreeRTOS, the running task will be the highest priority Ready task. (There are cases where without premption turned on, there may be a momentarily a higher priority task ready, but we need to wait to for an allowed prememption point to make the switch).

The suspend function marks a task as suspended, so not ready, and if it was the running task does a context switch. It is not an error to suspend a task that is already suspended.

The resume function marks a task as not suspended, so might be ready (unless it is blocking on some other resource). It is also not an error to resume a task that isn't suspended.

This does mean that a resume being sent to a task just before it is going to suspend itself will act differntly than if the resume happend just after the suspend, i.e. we have a race condition.

It sounds like what you want is a primative that is remembers so that if you send it to a task and then the task wants to 'suspend' that the system remembers that it has already been kicked an goes on, of it it hasn't been kicked, it suspends until it gets the kick operation. There is such a primitive, and that is called a semaphore (or a counting semaphore if you want to stack multiple levels of 'resume'). This could either be a one per task semaphore, or using the direct to task signalling ability.

[Richard Barry]

If I understand what you are asking for, it sounds like you have a
fundamental difference in process model.

Not quite, I think it is more subtle than that. The intention is to map
the FreeRTOS API onto the CMSIS++ API - the execution model of
applications that use the RTOS would be the same whether they used the
native FreeRTOS API or the CMSIS++ API.

The conversation is more about how to implement CMSIS++ features for
which there is no direct mapping, or more generally, how to use FreeRTOS
features to extend the functionality to provide additional RTOS
primitives. The problem is with regards to how the suspend/resume
mechanism could be used to achieve that - but currently the
suspend/resume mechanism was not designed for that purpose - so then how
could it be designed to allow it to be used for that purpose.

[Liviu Ionescu (ilg)]

fully agree

[Liviu Ionescu (ilg)]

If I understand what you are asking for, it sounds like you have a fundamental difference in process model.

sorry, you are probably right in many of the details you presented, but they do not address the question.

if after several long messages it is still hard to get it, it looks I have a serious communication or a language problem.

please allow me one more try. forget everything explained above. the hypothetic exercise is the following: implement a semaphore (or a message queue, a mutex, or anything else you want), without using any of the existing semaphores, message queus, mutex, flags, or any other such high level synchronisation object, only with publically available scheduler/thread/kernel related calls.

my claim is that with FreeRTOS, this is currently not possible, and Real Time Engineers Ltd confirmed that at least suspend/resume are not appropriate for this.

my second claim is that by splitting the vTaskSuspend() in two parts that I named vTaskPrepareSuspend() to handle the part that removes the thread from the ready list and vTaskPerformSuspend() to perform the context switch, this becomes possible (this solution worked for me). for a better readability, in my scheduler API these functions were renamed prepare_suspend() and reschedule().

my third claim is that if the current running thread would not be kept in the ready list, but be removed right before rescheduling it, this split would not have been necessary, and a simple suspend() would be enough.

please do not take this as a criticism or a complain, I am just reporting several facts that I experienced while implementing CMSIS++ over FreeRTOS.

if these reports can be used for improving FreeRTOS, that's fine. if not, that's ok too, for me it was a useful experience anyway, since it helped improve the CMSIS++ scheduler API, which right now seems to cover most (all?) existing RTOS cases.

[Richard Damon]

Spliting suspend in the two pieces introduces a different form of race I think. If you do the prepare_suspend to remove from the ready list, then add to the request queue and then reschedule, you run the risk of a time based automatic reschedule happening between the prepare and the add, making your task an orphen that no one knows needs to be restarted.

If I understand your proposal, you seem to be suggesting that the currently running task not be on the 'ready' list, so that suspend can detect that a resume was called on the task recently so that the suspend won't stop the task. What happens if between the add and the suspend we first get the interrupt that does the resume, and then we get a timer tick causing a round robin reschedule, and then when it gets back to us we do the suspend. Do you expect the round robin reschedule to remember that the task is in the excess resume state? If so, then you really are asking that there be embeded in a task a semaphore, that is rased on a resume and taken by a suspend, but we don't call it a semaphore.

[Liviu Ionescu (ilg)]

you run the risk of a time based automatic reschedule happening between the prepare and the add, making your task an orphen that no one knows needs to be restarted.

this is exactly what happened before the split, the thread was sleeping for ever.

maybe I don't understand the FreeRTOS internals, but how could a time based reschedule happen if both the prepare_suspend() and the add() would be inside a critical section?

[Richard Barry]

Reading this on my phone and not read the whole thread, so my reply might not answer the question correctly, but all the RTOS ports are designed to allow a forced context switch in a critical section. Either the switch will occur as the critical section is exited, or the task will switch to a another task that is not in a critical section (so all interrupts are enabled), then reenter a critical section the next time the original task executes. Would explain that better if the keyboard on my phone was larger.

[Richard Damon]

Inside a critical section, you wouldn't get the time based reschedule, so I think you are ok there. As RTE said, once you are using a critical section, I think you can do the add and the current suspend inside the critical section and avoid the problem too.

I am also not sure what you objection is to using the direct to task notification API in task.h to get around this issue either. You seem to be trying to use as little of FreeRTOS as possible and reimplement as much as possible.

[Liviu Ionescu (ilg)]

I am also not sure what you objection is to using the direct to task notification API in task.h to get around this issue either.

is this API universal enough, to be realistically implementable in most RTOSes, so I can use it as the CMSIS++ scheduler API?

@Richard Damon, if you do not know what CMSIS++ is, please take a look at http://micro-os-plus.github.io/cmsis-plus/rtos/, the picture should be helpful. between the large yellow CMSIS++ RTOS API and the green 3rd party RTOS there are both dotted arrows for calls that can be directly translated and full arrows for calls that are implemented in the blue rectangle, that access the scheduler via the scheduler API.

[Richard Damon]

The question isn't can other RTOSes implement the direct to task notification, but, since it is part of the core task.c/task.h, can you use its features to support implementing the API interface you are given. Given the race conditon you have described (which has also been pointed out should be fixable with a critical section), the 'traditional' answer would be a semaphore, as it has the needed 'memory' to remove the race. The direct to task notification can be used to implement a light weight per task semaphore that seems ideal for your problem. You replace your current suspend by a wait for event, and the resume with a signal event, and I think everything should work as you desire.

The other question is if FreeRTOS is full featured enough that rather than using it to implement just the CMSIS++ Scheduler API, should you have it implement CMSIS++ RTOS C++ API, i.e be a full replacement for the uOS++ refernece implementation.

FreeRTOS is more than just a scheduler, and that seems to be part of the issue you are running into. We are given from the FreeRTOS API something that is probably more like the CMSIS++ RTOS API, than the scheduler API.

[Liviu Ionescu (ilg)]

if FreeRTOS is full featured enough

as of now, FreeRTOS does not provide all the primitives required by the CMSIS++ RTOS API. that's the main purpose of the portable synchronisation objects, to provide a backup solution for RTOSes that are not as close to POSIX as CMSIS++ expects.

We are given from the FreeRTOS API something that is probably more like the CMSIS++ RTOS API, than the scheduler API.

I don't have a problem with this, if the RTOS provides the desired functionality, I have the means to directly forward it to the user via the CMSIS++ RTOS API. If not, or if the user chooses so, the reference synchronisation can be used with granularity down to each object.

you can take a look at how this works in the doxygen cross reference. for example the semaphore implementation is:

http://micro-os-plus.github.io/reference/cmsis-plus/os-semaphore_8cpp_source.html#l00532

if OS_INCLUDE_RTOS_PORT_SEMAPHORE is defined, the port::Semaphore::timed_wait (this, timeout); is used, with no special overhead, being an inline.

the scheduler::_link_node() does the magic with the lists and the discussed prepare_suspend()

http://micro-os-plus.github.io/reference/cmsis-plus/os-core_8cpp_source.html#l00218

(unfortunatelly the doxygen site is not mobile friendly, I appologise for this)

[Liviu Ionescu (ilg)]

also as a reference, here is the file with the mapping of the CMSIS++ RTOS API over the FreeRTOS calls:

https://github.com/xpacks/freertos/blob/xpack/cmsis-plus/include/cmsis-plus/rtos/port/os-inlines.h

(probably it might be further optimised, but for now it passes the Keil CMSIS RTOS validator, so I would say it is a good start).

[Liviu Ionescu (ilg)]

The Cortex-M3 port will not yield inside a critical section, but yields
attempted inside the critical section are held pending [by the hardware]
and occur immediately that the critical section is exited. Other ports
will yield directly in the critical section, then manage entry back into
the critical section when the task that yielded next executes - hence my
comments above about why it is best that application writers don't do this.

in this case this confirms that the safest way for the scheduler API is to have separate prepare_suspend()/reschedule(), to allow the ready list queue operations to be executed inside a critical region, and still have the reschedule() outside the critical region.

[Richard Barry]

Ticket moved from /p/freertos/bugs/128/