uasyncio scheduling algorithm

C programming, build, interpreter/VM.
Target audience: MicroPython Developers.
User avatar
pythoncoder
Posts: 5956
Joined: Fri Jul 18, 2014 8:01 am
Location: UK
Contact:

uasyncio scheduling algorithm

Post by pythoncoder » Sun Apr 02, 2017 7:05 am

For those who don't normally follow GitHub I raised an RFC on this topic https://github.com/micropython/micropython/issues/2989. I'd welcome any input to it.

In particular, before I waste time hacking code am I barking up the wrong tree? ;)
Peter Hinch
Index to my micropython libraries.

User avatar
Roberthh
Posts: 3667
Joined: Sat May 09, 2015 4:13 pm
Location: Rhineland, Europe

Re: uasyncio scheduling algorithm

Post by Roberthh » Tue Apr 04, 2017 7:46 am

Sorry, Peter, for being a little bit tardy. I've seen your discussion on Github and can follow the intention, but I have have no opiion about it. nevertheless (or: exaclty then), I can make a few words. You maybe one of few who really work with asyncio on Micropython, and have therefore some experience about what is missing. So your word must be considered. I'm just a little bit sceptic whther ESP8266 is a platform worth this effort, given it's unpredictable code timing. And still, this is Micropython on Microcontrollers, even if there is already a lot of stuff in it which is not micro. I suggested such things myself. So one must always be careful when introducing new features, because it's hard to get rid of them.

User avatar
pythoncoder
Posts: 5956
Joined: Fri Jul 18, 2014 8:01 am
Location: UK
Contact:

Re: uasyncio scheduling algorithm

Post by pythoncoder » Tue Apr 04, 2017 4:26 pm

Hi Robert. My suggestion is platform agnostic. The demo/hack I posted today changes only uasyncio.core which is written in Python; testing was on the Pyboard. I share your doubts about the ESP8266 and ESP32 platforms. But on fast targets I think a change along the lines I'm suggesting would be a worthwhile improvement.

I know feature-creep is a hazard but the change seems minor and easily implemented. The API change would not affect existing code. And I think it's beneficial, given the fast response times uasyncio now boasts. Time will tell if anyone shares my enthusiasm. ;)
Peter Hinch
Index to my micropython libraries.

User avatar
Roberthh
Posts: 3667
Joined: Sat May 09, 2015 4:13 pm
Location: Rhineland, Europe

Re: uasyncio scheduling algorithm

Post by Roberthh » Tue Apr 04, 2017 7:07 pm

Hello Pete, I was a little bit mislead. uasyncio is pure Python code, and so it's up to the user which variant to use, if they are clearly maintained. Obviously it's more nice to have them in the 'official' micropython lib...
I gave your code a try on ESP9266. Still my Pyboards are all in use. The results:

Code: Select all

10 t =  28.6ms max  10.9ms min
20 t =  28.6ms max  10.7ms min
30 t =  28.6ms max  10.7ms min
40 t =  28.6ms max  10.7ms min
50 t =  29.3ms max  10.7ms min
60 t =  29.3ms max  10.7ms min
The only change I had to make was for getting a random number. And yes, the range of generated numbers is 5000..13000. On esp32, the number match more the pyboard results:

Code: Select all

10 t =  23.0ms max   9.9ms min
20 t =  23.0ms max   9.8ms min
30 t =  23.0ms max   9.8ms min
40 t =  23.0ms max   9.8ms min
50 t =  23.0ms max   9.8ms min
60 t =  24.1ms max   9.8ms min
In addition to the rng change I had to enable the utimeq module. But that's all.

User avatar
pythoncoder
Posts: 5956
Joined: Fri Jul 18, 2014 8:01 am
Location: UK
Contact:

Re: uasyncio scheduling algorithm

Post by pythoncoder » Wed Apr 19, 2017 4:33 pm

For anyone following this I've posted an experimental version of uasyncio supporting a simple priority mechanism. This enables applications to be written in a way which can substantially reduce scheduling latency and improve timing accuracy. It is documented here https://github.com/peterhinch/micropyth ... ASTPOLL.md.
Peter Hinch
Index to my micropython libraries.

User avatar
Roberthh
Posts: 3667
Joined: Sat May 09, 2015 4:13 pm
Location: Rhineland, Europe

Re: uasyncio scheduling algorithm

Post by Roberthh » Wed Apr 19, 2017 8:16 pm

Hi Peter. That looks good. I instantly updated my copy of your repository. As always this module is excellently documented.

SpotlightKid
Posts: 463
Joined: Wed Apr 08, 2015 5:19 am

Re: uasyncio scheduling algorithm

Post by SpotlightKid » Wed Apr 19, 2017 10:40 pm

Good write up! I will try it as soon as I have time to dig into my uPy projects again (which may be one or two months off).

BrendanSimon
Posts: 33
Joined: Wed Sep 07, 2016 10:46 am

Re: uasyncio scheduling algorithm

Post by BrendanSimon » Sat May 06, 2017 11:32 am

This is great work Peter, and I personally think this has a place in the core MicroPython code base, one way or another.

Any real-time (or pseudo real-time) system needs the ability to give tasks priorities. Two questions come to mind.

1. Why did you decide that your modifications would apply to low priority tasks, and that the existing yield mechanisms would be considered normal priority (i.e. the higher priority)?

My gut instinct would have been to treat the existing yield mechanisms as low priority, and have the modifications apply to high priority tasks.

That way all existing code doesn't have to change to make the tasks low priority. You just change the tasks of interest to be high priority.

2. I feel that the priority mechanisms could be generalised to provide more than two levels of priority. I don't know how much is enough 4, 8, 16 ... ? I'm thinking of a number of queues to handle each of the priorities, and this could be user configurable.

Another approach would be to have the priority as an attribute of the task. The scheduler could order it in the single queue based on priority? That way there is only 1 queue.

i.e. a co-operative real-time system. I'm sure you've thought about this and I'm wondering what your conclusions were.

As an example, how does your implementation handle a largeish number of "normal" (high) priority tasks that expire at the same time, but you want one of them (the last one scheduled) to have a higher priority and be executed first?

User avatar
pythoncoder
Posts: 5956
Joined: Fri Jul 18, 2014 8:01 am
Location: UK
Contact:

Re: uasyncio scheduling algorithm

Post by pythoncoder » Sat May 06, 2017 5:08 pm

Some interesting ideas there. Perhaps a little history is required. When I posted my code I hoped that the changes (or at least the basic concept) would be incorporated in the official build, so I worked on the principle of keeping changes to the absolute minimum. My aim was to obsolete my old scheduler rather than to award myself the job of maintaining a new one ;)

It's now evident that the ideas aren't going to be accepted so I'll do my best with a fork, as I remain convinced that the official library is insufficiently flexible for some embedded applications. The lib is still under development so to some extent I'm aiming at a moving target; I still feel inclined to minimise changes.

The idea of a single queue handling priority as well as time would be nontrivial, and would involve modifying the firmware in addition to the Python library. I feel disinclined to go down that route. Multiple queues would be easy, but I'm not convinced that typical firmware applications really require this. My personal view is to keep it "micro" but I welcome other opinions.

In both my implementation and the official version multiple standard coros which are ready for execution will be scheduled in "fair" round-robin fashion.

This means that if there are N coros, each polling an event in a tight loop with a zero delay yield, each event will be tested once every N iterations of the scheduler. In many, perhaps most, situations this is probably OK. But there may be events requiring a faster response. What I think is needed is a means of polling an event on every iteration of the scheduler. This effectively introduces a third tier of priority, one above the standard level. This would work by yielding a callback function rather than a time, the callback returning True when scheduling is required.

It would need using with care because of the potential impact on the task switching overhead of the scheduler: polling functions need to be fast executing and few in number. Typically they would be a lambda or a simple bound method which tests a flag set by a hardware interrupt. Such a mechanism would enable a small number of coros to respond to events in a time corresponding to the worst case processing time of any one other coro.
Peter Hinch
Index to my micropython libraries.

User avatar
pythoncoder
Posts: 5956
Joined: Fri Jul 18, 2014 8:01 am
Location: UK
Contact:

Re: uasyncio scheduling algorithm

Post by pythoncoder » Fri May 12, 2017 4:07 pm

I've updated https://github.com/peterhinch/micropython-async.git. This now has an option for fast scheduling. A coro can issue

Code: Select all

await asyncio.when(callback)
where callback is a user-supplied function or bound method returning a boolean. The callback will be run and tested on every iteration of the scheduler: if it returns True the coro will continue. This provides a very fast response to an event at the expense of some performance loss in the scheduler: running each pending callback inevitably imposes some scheduling latency. It is still possible to keep the total latency implicit in the scheduler below 500μs.

The mechanism should therefore be used sparingly with few fast-running callback functions. If it is not used by an application, there is no measurable effect on the scheduler's performance (implicit latency ~230μs).

This effectively obsoletes my old scheduler; its one facility not implemented in either uasyncio or my modified version is the ability of one task to control another. Python's asyncio provides this via Tasks and Futures. It's inappropriate to hack this as the maintainers may implement these objects at a future date. I've only implemented features which lie beyond the Python standard, which the maintainers do not intend to add, and which I think are of value on bare metal targets.

My current view is that this modified version is complete barring bugfixes.
Peter Hinch
Index to my micropython libraries.

Post Reply