Round Robin Scheduling Behavior

Kernel
1

What I think is that when three tasks A (4 ms), B (2 ms), and C (5 ms) have the same priority in FreeRTOS, the scheduler allows Task A to run for one time slice 1ms and then switches to Task B, so Task A pauses. Then Task B runs for one time slice and the scheduler switches to Task C, pausing Task B. After that, the scheduler switches back to Task A, and Task A resumes from where it paused. This switching continues in round robin order.

I am thinking that since Task B only needs 2 ms to complete, once it finishes, will the scheduler continue the same A → B → C sequence, or will it change to only switching between Task A and Task C?

2

Since tasks don’t “complete”, the question is based on bad understanding of the concept. If your tasks each just run continuously, taking the indicated time to complete one cycle of its operation, and then starts back up again, then they will continue to run in the A → B → C → A sequence.

But that is actually a very strange sort of task to be running in a real time system. Normally tasks would be waiting for a signal that they have something to do, then they do their work and send and answer, then wait again. The signal might be that they are supposed to run every x units of time to do their thing, and if the system has been properly designed, they will finish before that time passes so they will wait for the next activation, and do the waiting by blocking, telling the scheduler that they don’t need any time until that signal comes (or time expires).

If this is the case, when B finishes its 2 ms of work, it should block until its work is needed again.

3

As you mentioned that continuously running tasks is a bad design, I tried to think of a practical scenario to understand good vs bad design.

In a system, we need real-time location every 1 second. One task reads GPS data and another sends it over HTTP. Both have equal priority and communicate using a message queue.

My confusion is about timing. Should I use vTaskDelay( )in both tasks so they run every 1 second, or is that the bad design?

Alternatively, we can make only the GPS task periodic using delay, and let the HTTP task block on the queue. This seems like better design, but then how do I ensure data is actually sent every 1 second?

4

Most GPSes are programmed to send a message each second with the updated data, or at least generate a signal that can be used as an interrupt to let the system know to read the update.

Thus, the GPS read routine should be blocking for that message, and then as soon as that happens, processes it and send it/notify the parts of the system waiting for that.

Why wait for the the next “second” to occur to do that? That could mean your HTTP message could be almost 2 seconds old.

The task to send it over HTTPS, would get the notification, and immediately queue up its request to the HTTPS driver.

These tasks might want to put a “timeout” on there waits for event, so they can report an error if messages stop coming, but they should not try to time themselves with vTaskDelay.

Note, wanting to run every second is also very different than the initial description of taking a second to run. A task blocked waiting for the right time to run again isn’t using any processor time, and wouldn’t be considered as “running” when talking of scheduling.

5

Actually, this use case is a prime example where you may think about NOT using concurrency at all. It appears that the event timing is strictly serialized: It is required that every second, GPS is read (or polled), immediately following the communication. So the two tasks act as “coroutines” that periodically invoke each other, in which case you might as well (even better) have a single task that wakes up every second, then reads the GPS (see below for details), then sends the requests ans used vTaskDelayUntil() to go to sleep until the next cycle.

There are nevertheless good reasons for a concurrent design, but only if there is true concurrency involved. Let us assume, for example, that the HTTPS task does not only need to communicate GPS data but also, for example, device alerts, poll the server for firmware updates, or something like that (in other words, it is not only being “fed” by GPS but also other sources).

So my first attempt at a design would be as follows - unless of course a strictly linear single task design as outlined above would suffice:

  • The GPS (as Richard suggested) would be interrupt driven if possible, so the GPS device asynchronously deposits the most recent position in a global variable. It may or may not signal the communicator task with new data availability; if no new data has come in in a second period (which may or may not be the case; for example, if the use case is a flight recorder, the person’s data may not significantly change before launch but constantly after that), the most recent one will not update.

  • The communicator task will simply sit in a vTaskDelayUntil() loop or a timeouting wait on the message and, once awake, either process the message or take whatever is currently in the most recent location variable and send it upstream.

You would need a task for the GPS sampling if there is no other way to query the GPS but to poll it. Interrupt driven is the better choice over polling.

With the design you outline, it is not clear to me why the two tasks need to have the same priority. Polling the GPS device is typically a rather short process, so you do not lose anything (but gain higher determinism) by giving the GPS polling task a higher priority.

6

This is wise advice - as you add more features you may need a scheduler. Until then you may be best served by a simple bare metal program that takes the GPS sample and submits the HTTP message.

7

I agree this can be done in a single task, as there is no hard deadline. I intentionally used two tasks to understand task communication and synchronization

8

I am slightly modifying my initial idea to get a better understanding of what needs to be done.

The system is designed to collect real-time GPS location data and transmit it to a central server at regular one-minute intervals.

It receives location data from a GPS module through a serial interface. Incoming data is captured using an interrupt mechanism and passed to a GPS task, which processes the data and updates the latest location information. A separate HTTP task runs periodically every one minute and sends the most recent location to the central server.

When considering synchronization between tasks, there are several options such as mutexes, semaphores, and message queues. I would first like to understand what approach you would prefer in this scenario.

From my perspective, For signaling from the interrupt to the GPS task, I think a semaphore is a good fit because it provides a simple and efficient way to notify the task that new data is available.

For communication between the GPS task and the HTTP task, I believe a message queue is more suitable because it allows structured data, such as location information, to be safely passed between tasks, avoiding data corruption

I’d like to hear your thoughts on my design and thinking, as it will help me move in the right direction.

9

Actually, my preference here would be that I would have a generic interrupt-driven serial driver that provides the task with the data string via a queue or a stream/message buffer that the GPS task is reading from. This way, you minimize the processing being done in the ISR, and you have a natural buffering if something delays the GPS task a bit.

For most GPSes, this will happen every second. The task might use a timeout to detect that something has gone wrong with the communication link (and do something to handle the error).

Since the HTTP task only wants to update once a minute, and thus will want to ignore most of the GPS updates, it might make sense to have a global communication buffer that holds the last GPS reading. Updates and reading of this buffer will need to be protected to avoid seeing partial updates. This could be done with a mutex, or, since the operation to update/read from/to a local private copy of the structure will be quick, a critical section could also be appropriate (and quicker). The HTTP task would then use a simple xTaskDelayUntil loop to activate itself once a minute, copy the data, and then sends it.

If you wanted to send EVERY reading, then using a queue to send it would make sense, and again, that would provide a natural buffer if things fall behind. I would normally use plain queue and not a message buffer, as the messages should be all the same structure, so the variable size of the message buffer wouldn’t be needed. (Unless you are going to the more esoteric AMP transfer between two cores running different instances of FreeRTOS which has support for message buffers but not Queues).

If you wanted to just keep the most recent data having been sent to the server, then a semaphore with an access to the global data would work, and naturally would drop readings if the sending falls behind.

10

Aside from the mutex addition, this is exactly the same basic architecture I sketched out earlier.

11

Hi Richard,

I don’t see your approach addressing the 1-minute requirement.

What I understand so far is that the GPS continuously sends NMEA sentences (around every second), the UART interrupt receives characters and forms a complete message, and once a full message is available it is pushed into a queue. Then a GPS task wakes up, reads from the queue, and extracts latitude, longitude, etc. up to this point the design is clear to me.

Where I am getting confused is the next step. I need to send this location to a server using HTTP every 1 minute, and I want to make sure this 1-minute requirement is met consistently and not affected by other tasks in the system.

I understand that I can use a queue to pass data from the GPS task to the HTTP task. My current understanding is that after sending the data to the server, the HTTP task should block for 1 minute, so that it wakes up either when new data arrives on the queue or when the 1-minute timeout expires.

I don’t have any idea about task notification APIs at the moment, which is why I am considering using a queue for this behavior.

Does this approach ensure that the tasks will not interfere with each other?

12

First, your design at every point couples the requirements of the consumer into the code of the sender. This builds a lot of extra coupling in your system.

My serial driver for “normal” speed serial ports puts each character as received into the queue, and the reading task “wakes up” to take each character. Only for “high-speed” links do I buffer a full message, and send it.

Since a GPS sends\ data every second, and your HTTP task only wants one datum a minute, sending it all the data is expensive, and having the sender reduce the rate puts too much of the HTTP task specification into the GPS task. That is why for this application, it seems the concept of a global status that the HTTP task gets the most recent value when it wants it makes sense. Note, by its nature, the results of the HTTP task will have variations in it, as that is the nature of HTTP traffic. The use of xTaskDelayUntil will handle most of the issues of interference from other tasks, a proper priority setting will deal with most of the rest. (You do need to make sure your system has adequate processor margins).

Since it is grabbing data once a minute, based on its own actions, there is no need for “notifications” to handle this. Tasks that want to process ALL the data are the sort of ones that will need some form of notification.

You also seem over-concerned about “interference”. It is a fact of life, that the existence of multiple task WILL interfear with each other to some extent, as when one is running, it can’t be running another. The key is understanding this fact, and handling it. This requires knowing your real timing requirements and thinking about them.

13

From your explanation, it seems like instead of sending every GPS update to the HTTP task through a queue, the GPS task should just maintain the latest location as a shared/global value. Then the HTTP task would run independently, wake up every 1 minute using xTaskDelayUntil(), and read whatever the latest GPS value is at that time.

So in this approach, the HTTP task is purely time-driven and does not need queue from the GPS task, since it doesn’t need to process every GPS message.

Is this what you are suggesting?

14

Yes, based on your definition of the HTTP task, it doesn’t need immediate notification of every data point, you can reduce communication resources by having it “pull” the current value when it needs it. The GPS task would “push” a notification only to operations that need quick response, but not to less-time critical operations.

Methods uses strongly depend on the type of requirements that are present.

15

I find that ‘push’ works better.
As soon as the GPS gathered all the information, simply ‘Push’ a message in the system and let everybody know a updated position is available.
Personally I send within that message the required data like parsed coordinates, times and what not. If people uses a shared data, fine… just make sure you use a spinlock or mutex to protect.
For a data ‘copy’ of a structure I prefer a spinlock.

But, if reading GPS data and then update is the main worry point, I would suggest to worry less :slight_smile: Most modern microcontrollers can do so much work, it’s not even funny anymore how much work they can do.

I read GPS, control two transceivers, run a webserver, push data over bluetooth over two characteristics, send data over UDP blink a led… and I still have plenty of processor over to do other work.

16

Yes, the GPS should have a push system in it, so that those things that want EVERY update can get them timely. This could easily be an “Event Group” that it signals, so tasks that want every update can wait for it.

The issue is that the HTTP task does not want EVERY update, just the data once a minute. Do you subscribe to a time update service that emails you once a minute the current time? That is what you would be doing having the HTTP task get notification EVERY event. It will need to burn time 59 times out of 60 just to see that it doesn’t need the data this time.

Your comment on preferring “spinlocks” shows a fundamental misunderstanding of system design. User level application code should NEVER use a “spin-lock” as it can lead to deadlock, especially on single core systems (which your described application could easily fit in.), as if a higher priority task interrupts a task with the spin lock, it would end up spinning until the lower priority task runs to release the spin lock, which can never happen.

Yes, over-powered processors can do a lot of work, but at a cost. It seems you are sometimes concerned about task “interfering” with each other, but want to ignore the primary way they can do so, and that is using up the CPU resources.

17

Addition to these very appropriate remarks: Another common misunderstanding about CPU ressources and RTOS is that the benefits of multitasking (at least on single processor cores) are reverse proportional to the CPU boundness of the tasks. In other words, if the tasks spend most of their time waiting for I/O (“I/O bound”), an RTOS can utilize the waiting time to allow other tasks to do their computations, which will manifest in overall improved throughput. If, however, all your tasks spend all of their time using up CPU cycles (“CPU bound,” the most well known example being the infamous “while (1){}” loop), there is no noticeable time gain for any tasks; the only difference over a purely serialized execution there is that all tasks will over time make some progress, but much slower than they would make otherwise. For predominantly CPU bound computations, multi core processors are truly the only remedy.

A good system design will not only attempt to most naturally model the concurrency in the system (see the earlier posts about why this use case does not have inherent concurrency) but also take into account the “CPU vs. I/O boundness” of the computations chosen for concurrent execution.

18

Hey Richard,

about the spinlocks (I am not the original OP) I am aware if soft spinlocks and deadlocks, in my situations they are hardware spinlocks (Raspberry PICO) I cannot see how this can result in a spinlock as long as the spinlock never blocks. I use them when copying a structure or arrays.

This is the code Raspberry created:

__force_inline static uint32_t spin_lock_blocking(spin_lock_t *lock) {

    uint32_t save = save_and_disable_interrupts();

    spin_lock_unsafe_blocking(lock);

    return save;

}

since the spinlock call also disables interrups, I have assumed they are save
But I would love to read a bit more about it..

19

The RPi PICO is a multi-core processor, so has something like that.

Note, the FreeRTOS Critical Section for multiprocessors does something like that, but for single core systems uses a simpler disable interrupts.

The key point is that these sorts of things are intricately tied into your OS implementation, and going to something outside is asking for a problem, and ties your code to a specific platform, which is what you want to do.

20

Ahh yes, currently I don’t mind to be on one platform. Although I wrapped the spinlock in a RIAA class, so it’s easy to change into something else I simply don’t have time as a hobby to support multiple platforms well.

My main focus will be conspicuity for Aviation, I fly GA aircraft in Europe and I need to have better insight what’s going on around me…