Feature request: Scheduler that prioritizes tasks that have been waiting the longest

When running 2 tasks with the same priority, if one never blocks, the other will never run, even if the other also doesn't block. When I first discovered this behavior I thought it was a bug, however according to the documentation it's the intended behavior.

I can understand the rationalization of "you shouldn't be running a non-blocking task at the same priority as other tasks anyway" but it still seems intuitive to me that 2 non-blocking tasks should be able to run.

I've implemented a scheduler that timestamps tasks when they run, and uses that timestamps to break a tie when the priority is the same. It works, but it does have some drawbacks.

It creates a dependency of the time library. This maybe isn't a big deal, but I have noticed the very minimal dependencies of this library.
It is inherently going to run a tiny bit slower and use a tiny bit more memory, and this may not be acceptable.
My implantation awkwardly tacks the timestamp to the Task object while it's passing through the scheduler, which is a bit uncomfortable, but I didn't want to touch the code for the task object itself.

I've also had the idea of keeping a counter of how many iterations the scheduler has been through, but this counter could grow very large indeed, and probably isn't practical.

Interested to hear any feedback anyone has on this idea

h0dgep0dge/pyRTOS@911b01d9e3d1629f5e2339e5d70435cf098da227

I've included a version of the default scheduler I rewrote to better understand what was going on, and then the version where I've subbed out prioritizing the RUNNING state for prioritizing tasks that have been waiting

First, yes, it is the intended behavior. RTOS's in real-world applications need to meet certain reliability requirements, and this means deterministic scheduling, or as close as you can get. When you set two tasks to the same priority, it is difficult to serve both tasks at the same time as remaining 100% predictable. There are many reasons this might be a problem. One is reliability in production. Another is ease of debugging, which can become extremely difficult when running multiple tasks at the same priority. (If you are familiar with debugging multi-threaded applications on regular PC systems, you'll understand this.)

Second, what you seem to want is something more like a desktop OS that is not an RTOS. On desktop systems, instead of a deterministic scheduler where each task has a unique priority, you can have multiple tasks with the same priority, and the OS scheduler handles scheduling in some kind of "fair" way. If you want to run multiple tasks that are independent, and the reliability and predictability of RTOS is unnecessary, this is what you want. There are a lot of scheduling strategies that can be used for this (each with strengths and weaknesses). If you are not already familiar with them and you want to learn, consider getting a college level "Operating Systems" textbook. (One of those strategies is indeed prioritizing the task that has waited the longest. There's also a "round robin" scheduling strategy, several strategies based on need for or availability of I/O resources, and others.)

Third, I made PyRTOS to be extensible like this intentionally! If my default scheduler (which is modeled after FreeRTOS) doesn't do what you want, you can write your own, and I have no problem with people writing non-RTOS schedulers for this, if that's what they need.

While I don't want to include any alternate schedulers into the compiled releases (mainly to minimize size), I'd be happy to setup a place in the repository for alternate schedulers, for anyone who might need something other than the default. (I hope you don't mind if I rename it though. I don't recall exactly what it is, but there is an official name for a scheduler that prioritizes the task that has been waiting the longest.)

As far as drawbacks go:

Dependency on time isn't an issue, as time is already included in the default CircuitPython.
You are right that this kind of scheduler comes with an extra time cost. That's a tradeoff people will have to consider when using a more complex scheduler, and there are plenty of cases where it is worth the cost.
I have no problem with an implementation that tacks an extra variable onto the Tasks. In fact, one of the things I love about Python is that even objects are dynamically typed, allowing things like this. It's not reasonable to create a new Task type class just for this scheduler, but this scheduler needs the task objects to track this value, so it's a perfectly good solution in my book. It would be nice if there was a better place to tack it on than the scheduler loop, for performance reasons, but I'm not sure there is without modifying the main PyRTOS code to treat this as a special case, which I don't want to do.

Well, I wasn't planning to take a close look at your scheduler code until tomorrow, but then I accidentally did. It's very simple with minimal modifications. I like it. Nicely done. If you don't mind, I'll see if I can work this into a good place in the code base, probably with that name change I mentioned (after I look up the official name of that kind of scheduler). I won't include it in the official mpy releases, but I can add a recipe to the Makefile to include this in place of the default scheduler, for those who want to streamline a build that uses this while maintaining optimal size. (And I can add a section on it to the documentation.)

If I have time tomorrow, I'll address the thing you mentioned about an iteration counter for the scheduler. While you are right that it wouldn't be practical due to size constraints, for specific use cases (which don't include keeping an accurate count of total iterations) there are some options for looping counter. It could be more practical to use a looping counter instead of time.monotonic() for this kind of scheduling, for example.

Thanks for such a prompt response! Some context on this, the reason this even came up is because writing an application using this library is a requirement for a tertiary course I'm taking on industrial automation, so this whole ordeal is a learning experience, and this is great feedback.

I've just started my mid-semester break, and I'm very interested in having a go at implementing some more scheduler algorithms, and also some blocking functions that respect io in circuitpython. I would be happy to keep it as a fork, but definitely feel free to pick and choose anything you'd like to pull into your repo, even if only to have some more code examples.

Ok, so iteration counter: Instead of time.monotonic(), an iteration counter could be used. This might save a little bit of memory, and it would avoid at least one function call and whatever other underlying stuff time.monotonic() needs to do. Instead of counting unbounded, the counter can loop. Now, normally this would create a problem where you loop and suddenly task "last run" records are out of order. The solution to this is to reduce the "last run" records on all of the tasks when looping, and then setting the counter to the the highest "last run" + 1 instead of 0.

Basically, you would find the task with the lowest "last run" value. You would iterate through all of the tasks subtracting that value from all of their "last run" records, so that the lowest one is at 0. Then you would find the task with the highest "last run" value (after the subtraction step) and set the counter to one more than that value.

For large counter ranges and many tasks sharing the same priority, this could reduce the counter range significantly. If it is reduced too much, this could result in frequent roll overs. Since the roll overs have a lot of math, this would reduce performance. There are two potential solutions to this. One is compressing the range during rollover. Say you have three tasks, with "last run" values of 100, 150, and 200. Normal rollover would reduce these to 0, 50, and 100, starting the new counter at 101. If your counter rolls over at 256 (a bit low, but for this example it's reasonable), your counter range is reduced to 155 before the next roll over. Since the distance between "last run" values is irrelevant though, you could set the first to 0, the second to 1, and the third to 2, starting the next counter loop at 3.

Maybe an even better way to do this though, is to keep track of the last value used when setting "last run" for another task (that isn't the current one). As long as the task doesn't change, don't increment the "last run" value. So, say I have a task with "last run" set to 25, and I switch to a different task. No matter how many times that task is selected by the scheduler, it's "last run" is set to 26. When it switches to another task, that new task is set to 27 and then not changed. This does the distance compression as you go instead of during rollovers. You'll still need rollover handling when your top limit is reached, but rollovers will be fairly cheap, since you only have to subtract them all down so the lowest is 0 and then set the counter to 1 + the highest. And this way you can set the counter range to only a few times the number of tasks, keeping it very low (256 is actually very reasonable, if not kind of high, for an application with up to 20 tasks or so).

Anyhow, that's my take on using a counter instead of time.monotonic(). Hopefully it's not too boring! I think that last idea would give you the most optimal results, and if the counter limit is user modifiable, it could be tuned by the user (larger limit means rollover less often at the cost of more memory, while smaller limit uses less memory but incurs CPU cost of rollover more often).

Yesterday I wrote another implementation that keeps a list of tasks, each time a task is executed the corresponding entry on the list is moved to the end of the list, and then when a priority tie needs to be broken the tie goes to the task with the lowest index in the list. h0dgep0dge/pyRTOS@3e9c787bf8c0a8398cd1e95fd04dc6310718cef4

Unfortunately this is very slow, I believe because there are so many array operations with unfavorable time complexity. I did a benchmark running 100 tasks, each running 1000 iterations, and according to that test my time_scheduler runs about 5x slower than the default scheduler, and the new recent_scheduler runs about 50x slower.

I have one or two ideas to optimize this approach, but I don't think it has hope of being much faster while there are still operations that need to iterate over the entire list of tasks. I also have another idea for an algorithm that's more in the increment vein, but hopefully without the issue of the increment variable exploding in value.

And thanks for the extra ideas, I'd like to chase those down too at some point.

EDIT: I've made an optimization by calling the array functions fewer times and caching the result, but it's still not worth using in comparison to the version that uses time.monotonic().

I tried the incrementing design I alluded to. How it ended up working is that each task object gets a "subPriority" attribute, which is set to 0 when a task runs, is incremented when 2 tasks are compared with the same subPriority, and is used to break the tie between tasks with the same normal priority. It seems to work well, and is almost as fast as the time.monotonic() approach.

In this case it seems like there is no substitute for simplicity, and the time.monotonic() runs fast enough for its use to not matter. Although I just realized that all my speed testing has been running on my laptop, and not running in circuitpython, so it's entirely possible that the circuitpython implementation of now.monotonic() is slow enough for it to matter.

Still working on this, spending plenty of time thinking it over.

Rybec / pyRTOS

Feature request: Scheduler that prioritizes tasks that have been waiting the longest #16