RFC: extending uasyncio scheduling algorithm with different priorities

Great strides have been made towards millisecond level scheduling but the algorithm could be further improved. Given the importance of cooperative scheduling in many firmware solutions this is arguably worth addressing.

Non time critical coros should be good citizens by periodically suspending execution. Such coros should be scheduled in round-robin fashion with other similar coros, while being pre-empted by coros which have timed out or responded to events.
Currently round-robin scheduling is achieved by issuing await asyncio.sleep(0). This means that they are scheduled with the same priority as a coro which issued a sleep_ms(20) and which has timed out, so compromising the accuracy of the timeout. A means of requesting low priority round-robin scheduling would ensure that coros which had timed out, and those which had responded to events (see 2.), were scheduled with the minimum possible latency.
A means is needed for a coro to respond to events with minimum latency. This implies a means of testing their readiness at every iteration of the scheduler.
Currently the best that can be achieved is to run a loop which tests the condition, and if it has not occurred issue sleep(0). The coro thus runs in round-robin with other such coros, with response to the condition next being tested only after all the other coros have run.

If point 1 were addressed, point 2 would be fixed by default, since a loop which issued sleep(0) would continue to be scheduled with high priority enabling it to test the condition with low latency. This seems a more natural way to code the coro compared to using the ioread mechanism.

Currently round-robin scheduling is achieved by issuing await asyncio.sleep(0)

I'm not sure what you mean by this. uasyncio (with a recent fix) uses fair, round-robin scheduling for all coroutines, period. The most efficient wait to yield control back to the scheduler is, well, just "yield".

General response - uasyncio implements asyncio-like framework, simplified. And asyncio doesn't have any facilities like you described, so adding those aren't priority thus. Feel to further elaborate why it would need to have all those, addressing the obvious counter-argumenys: a) (u)asyncio is a cooperative scheduling framework, so it doesn't, and can't guarantee deadlines (because they depend on user coroutines and not scheduler); b) unit of scheduling - 1ms - is purposedly large, to ensure that a number of (well-written) coros can run within the same scheduling unit, and yet small enough to offer "real-time" behavior wrt to human interaction (but definitely not enough for low-level control of high-speed mechanisms, e.g. servos, BLDC motors), etc.

It's commonplace to have non time critical coros. When these yield, their resumption should occur only when there are no pending priority coros. This is doubtless not an issue in typical web apps, but when we're seeking millisecond level scheduling I'd suggest that it is. Such coros shouldn't compete with coros which have timed out, or which have executed sleep(0).

I'm suggesting a mechanism should exist for issuing a default low priority yield. Such coros would be scheduled, in mutually round-robin fashion, only when no critical coros are ready for scheduling. This would be the normal way of yielding, perhaps in response to yield, with coros only issuing sleep(0) if they need to be re-scheduled ASAP.

The inherent limitations of cooperative multi-tasking notwithstanding I think that, in typical applications, this has the potential for reducing the latency of time-critical coros and for enhancing the accuracy of sleep_ms. It can be implemented without changing the API. In supplying sleep_ms asyncio has already been enhanced - I'm merely suggesting an "under the hood" mechanism for improving the performance of fast coros.

Once again, there're no priorities in asyncio, hence no in uasyncio. But you're welcome to theorize how they can be implemented (without compromising efficiency!), and if a viable idea is found, to prototype it.

reducing the latency of time-critical coros and for enhancing the accuracy

This assumes there's something to reduce and to enhance - on scheduler level, not on coroutine level. But such a need wasn't shown.

@dpgeorge

I'll await other comments: maybe I'm wrong in perceiving a need/benefit. @dpgeorge?

In a last-ditch effort to attract further comments, the following demonstrates this.

import uasyncio as asyncio
import utime as time

tmax = 0
tmin = 1000000

async def report(secs):
    count = 0
    while True:
        await asyncio.sleep(secs)
        count += secs
        print('{} t = {:5.1f}ms max {:5.1f}ms min'.format(count, tmax / 1000, tmin / 1000))

async def low_priority(ms):
    while True:
        yield # Ideally signal a low priority yield by some means
        time.sleep_ms(ms) # Simulate processing of some kind

async def priority(ms):
    global tmax, tmin
    while True:
        tstart = time.ticks_us()
        await asyncio.sleep_ms(ms)  # Time critical
        delta = time.ticks_diff(time.ticks_us(), tstart)
        tmax = max(tmax, delta)
        tmin = min(tmin, delta)
        

loop = asyncio.get_event_loop()
loop.create_task(report(10))
loop.create_task(priority(10))
for _ in range(20):
    loop.create_task(low_priority(10))
loop.run_forever()

The outcome shows that the nominal 10ms "time critical" delay is a fairly consistent 200ms:

MicroPython v1.8.7-456-ge402c51 on 2017-04-04; PYBv1.1 with STM32F405RG
Type "help()" for more information.
>>> import rats8
10 t = 204.2ms max 199.9ms min
20 t = 204.2ms max 199.9ms min

As expected the delay in the "priority" task is actually independent of its nominal 10ms value. It is given by T*N where T is the processing time in the low priority task and N is the number of low priority tasks.

With provision for scheduling at low priority I would hope to see (with the values in the test script) 20ms max, 10ms min. The maximum would occur when the sleep_ms(10) times out immediately after one of the low priority coros has been scheduled. The high priority coro would be scheduled as soon as the running coro executed a "low priority yield".

Paul: I'll close this issue if nobody considers it worth pursuing.

The example that is given here definitely shows the "problem", or at least it shows that (u)asyncio is not suited to handling such workloads.

time.sleep_ms(ms) # Simulate processing of some kind

Sorry, but you don't do such things in cooperative multitasking. If you do such things, you need preemptive multitasking (threading). In cooperative multitasking, each task should voluntarily work in steps, each << scheduling time. I.e. in our case, each task must guaranteedly run noticeably less than 1ms.

So, remove that line, bump number of tasks to 100 (from 20), and measure the scheduling delay with proper cooperative tasks. Then bump number to 200, 500, 1000, etc. - let's see how many proper tasks uasyncio can handle before scheduling delay becomes a concern. That will establish a baseline, from which it can be considered what can be done for improper taskloads.

Paul: I'll close this issue if nobody considers it worth pursuing.

Well, you perfectly know that we have tickets unresolved for years. Yet - nobody closes them, they wait for enough momentum to gather. For this case, I made clear that it's outside the scope of the core uasyncio. But at the same time, uasyncio was always intended to be flexible and extensible, so I don't see why you wouldn't be able to "hack" it to address the issues above, perhaps in an adhoc way. But you would need to start looking for a way to do that, I can't be the only one who knows how uasyncio works ;-).

OK, here is a hack to suggest a possible implementation. A coro yields False to flag a low priority reschedule (I'm not advocating this syntax - it's just a demo). I tested with the following script:

import uasyncio as asyncio
import utime as time
import pyb

tmax = 0
tmin = 1000000

async def report(secs):
    count = 0
    while True:
        await asyncio.sleep(secs)
        count += secs
        print('{} t = {:5.1f}ms max {:5.1f}ms min'.format(count, tmax / 1000, tmin / 1000))

async def low_priority():
    while True:
        yield False
        time.sleep_us(int((5 + pyb.rng()/2**27) *1000)) # Simulate processing: block 5 - 13ms

async def priority(ms):
    global tmax, tmin
    while True:
        tstart = time.ticks_us()
        await asyncio.sleep_ms(ms)  # Time critical
        delta = time.ticks_diff(time.ticks_us(), tstart)
        tmax = max(tmax, delta)
        tmin = min(tmin, delta)


loop = asyncio.get_event_loop()
loop.create_task(report(10))
loop.create_task(priority(10))
for _ in range(20):
    loop.create_task(low_priority())
loop.run_forever()

which produced

MicroPython v1.8.7-456-ge402c51 on 2017-04-04; PYBv1.1 with STM32F405RG
Type "help()" for more information.
>>> 
>>> import rats8
10 t =  22.6ms max   9.4ms min
20 t =  23.1ms max   9.4ms min
30 t =  23.1ms max   9.4ms min
40 t =  23.1ms max   9.4ms min
50 t =  23.1ms max   9.4ms min
60 t =  23.4ms max   9.4ms min

The low priority coros block for a maximum of 13ms so the maximum delay in the "fast" coro of 23ms accords with my expectations (nominal delay + 13ms latency). I'm unsure why the minimum is fractionally below 10ms.

Sorry, but you don't do such things in cooperative multitasking.

When using cooperative multitasking in firmware applications it's vital to understand the timing requirements of the application, both as a whole and in terms of the needs of each thread. While having sub-millisecond blocking is ideal, it isn't always feasible; it's only necessary if there is at least one coro requiring a precise short delay.

100 tasks is quite a few for this type of platform, but my curiosity was piqued so I adapted the above script to run that number and changed the numbers so that they blocked for random periods in the range 200-520ns. I tested with the official version of core.py and with the demo version, in the latter case both using the low priority (LP) feature and ignoring it. Results were as follows:

core.py   LP   threads  delay        10ms delay   Calculated
demo      Y    100     200-520ns     9.3-23.9ms   10-10.52ms
demo      N    100     200-520ns     49.0-81.0ms  10-62ms
official  n/a  100     200-520ns     49.7-76.7ms  10-62ms

The LP mode improves the delay accuracy but the modified code does slightly degrade performance relative to the official version when this feature is unused. For completeness the script is included below.

import uasyncio as asyncio
import utime as time
import pyb

tmax = 0
tmin = 1000000

async def report(secs):
    count = 0
    while True:
        await asyncio.sleep(secs)
        count += secs
        print('{} t = {:5.1f}ms max {:5.1f}ms min'.format(count, tmax / 1000, tmin / 1000))

async def low_priority():
    while True:
        yield False
        time.sleep_us(int((5 + pyb.rng()/2**27) * 40)) # Simulate processing: block 200-520ns

async def priority(ms):
    global tmax, tmin
    while True:
        tstart = time.ticks_us()
        await asyncio.sleep_ms(ms)  # Time critical
        delta = time.ticks_diff(time.ticks_us(), tstart)
        tmax = max(tmax, delta)
        tmin = min(tmin, delta)


loop = asyncio.get_event_loop(110)
loop.create_task(report(10))
loop.create_task(priority(10))
for _ in range(100):
    loop.create_task(low_priority())
loop.run_forever()

periods in the range 200-520ns

Really, nanoseconds?

so I adapted the above script

Right, you did that, but you didn't do what was proposed:

remove that line, bump number of tasks to 100 (from 20), and measure the scheduling delay with proper cooperative tasks. Then bump number to 200, 500, 1000

So, we'll still need to wait till someone would do that and establish a proper measurement baseline.

Really, nanoseconds?

Sorry, us of course :)

OK, here's the outcome (using the official uasyncio):

Tasks
 100        31ms
 200        53ms
 500       118ms
1000       227ms

(Difference between maximum and minimum times was minimal.) Code was as above with

async def low_priority():
    while True:
        yield

@dpgeorge

I guess this a useful benchmark of the (commendably fast) scheduler. So here are the results from the latest build which fixes #164. These demonstrate that the fix has had a minimal effect on performance.

Tasks   Time(ms, avg.)
 100     32
 200     54
 500    121
1000    233

Returning to the original topic, the benefit of a low priority mode. In the above tests I considered the effect on time delay values, but there is another common use-case. Consider a typical firmware application: an instrumentation project involving a dozen pushbuttons and two instances of a device driver. Assume that the device driver is written in Python and, when a reading is being taken, must respond to external events with low latency. Each pusbutton needs debouncing and has a continuously running coro to detect state changes and run a callback.

The 12 pushbutton coros can tolerate considerable latency. The requirements of the device driver are best met if, for the duration of a reading, the scheduler executes the driver instances in turn without also scheduling each pushbutton in round-robin fashion.

Similar considerations apply when you consider a touch GUI. This has a continuously running coro. When a touch is detected it polls each on-screen object to determine if the touch is within the boundary of that object. When the touched object is found, a callback is run. Again this coro can tolerate considerable latency, the only eventual consequence being some loss of responsiveness.

In applications with a user interface it's useful to be able to prioritise time-critical activities, perhaps only for brief periods, at the expense of some UI latency. The situation is typically asymmetrical: the time-critical coros may well execute rapidly while (in the case of a GUI) the UI coro may be relatively slow. So the impact of a high priority coro on the UI responsiveness may be trivial. By contrast scheduling the UI coro may impose a significant latency on the time-critical ones.

The solution I'm proposing enables high priority coros to prevent the scheduling of low priority ones by yielding a zero delay. This presents an obvious hazard if used incorrectly. But one no worse than running a loop without yielding at all: I'm sure we've all done that :) And the hazard only emerges if the low priority feature is actually used: normal code will run unchanged.

@dpgeorge Do you have any observations on this?

I've posted an improved implementation here with a demo program. A coro now calls for low priority scheduling by issuing:

await asyncio.low_priority

Benchmark results with the new official core and the modified version are

Coros Official   Modified
 100    32ms       33ms
 200    54ms       56ms
 500   121ms      126ms
1000   233ms      243ms

@dpgeorge

@dpgeorge Do you have any observations on this?

Not really, I didn't have time yet to go deeply into uasyncio, outside its use in basic networking. uasyncio is still in its infancy and it's yet to be seen what it's good (and not good) for, but your tests are encouraging. (You may also want to look into pyboard's threading, just enable MICROPY_PY_THREAD in stmhal/mpconfigport.h.)

I now have a version of core.py with a reasonable implementation of the priority mechanism. It is documented here. The doc references some benchmarks three of which may be run against official and modified versions. It also describes practical use cases.

tl;dr summary:

A solution such as this enhances the practical usability of millisecond-level scheduling.
It adds after(t),after_ms(t) and call_after(...) to yield with low priority - the implication of after being a time with a defined minimum but whose maximum may be imprecise compared to the regular methods.
The impact on timing performance of existing application code is too small to measure.
With appropriate application design the scheduling latency and timing accuracy of normal coros is substantially improved.
In benchmark timing.py a 10ms nominal delay run under the official version produced times in the range 407.9 to 410.9ms. Under the modified version times were 9.8 to 10.8ms.

If there is any interest I would be happy to submit a PR but from previous discussion I've concluded that this is something of a minority enthusiasm.

Peter, I agree entirely with your examples of high and low priority coros. Lots of industrial control and instrumentation applications have need for some semi real time tasks as well as low priority background tasks. Other examples - time sensitive: check oil pressure, safety interlocks, reading conveyor belt weight, etc and low priority: GUI (as you suggested), calculating results and writing to disk or network, checking ingredient levels, etc.

I am trying to introduce MicroPython to industrial developers. I have started to have some success. The usual reponsed is either "real programmers use C, there is no need for any other language" or "it won't be fast enough, I need low latency interrupts, RTOS, etc". Memory hasn't been an issue, in fact I was recently asked to upgrade a 128k STM32F103 t a 512k or 1M STM32F405 so the developer could use FreeRTOS. The application is running a PID temperature control algorithm and some low priority tasks. The C version has the same MCU memory requirements as a MicroPython version would.

Being able to demonstrate more deterministic and faster response for priority tasks will make the conversion in industry easier. I don't have an immediate application, but I want to rewrite some embedded C applications in MicroPython to demonstrate how capable it is. I would certainly use your version of uasyncio. If there is no more interest now I will try to demonstrate a use case once I get a real industrial application running.

My only concern, as you point out in the docs, is that low priority coros may never run. Would it be worth scheduling the next low priority coro on a slow tick (maybe 20 to 100 msec) if thy are stalled? This shouldn't have much affect on normal scheduling, occasionally adding 1 msec extra delay.

The market for CPython and MicroPython is different and I think this is a valid case for deviating from asyncio.

Thankyou for your great work with uasyncio and MicroPython.

Chris Mason

@chrismas9

@chrismas9 Thank you for your comments. I'll consider your idea but my thinking is that a normal coro issuing yield (or await asyncio.sleep(0)) should not compete with low priority coros. It is a matter of programmer discipline to avoid time consuming loops which never yield. By the same token, a loop with a zero delay will lock out low priority coros. But both loops have a purpose. In a coro it's
sometimes necessary to write

for _ in range n:
   # do something

where the "something" requires repetition at a rapid, deterministic rate. It's up to the programmer to consider the delay in the context of cooperative scheduling, and to ensure that the coro does yield when appropriate. By my reckoning it's equally valid to write

for _ in range n:
   # do something
   await asyncio.sleep(0)

subject to a similar caveat that the coro either yields with a nonzero time delay or issues a low priority yield when it's appropriate to do so.

There might be just one other high priority coro and this code enables you to determine and control the worst case latency implied by the yield. With your modification this latency would be longer, harder to calculate, and non-deterministic. In both examples with great power comes great responsibility :)

So my view is that it's a feature rather than a design flaw.

Peter, another possibility would be to add an optional second argument to after being a maximum delay before the low priority coro would run, even if normal coros were scheduled. Omitting the second parameter would give the current behaviour.

await after_ms(100, 250) would for example refresh the GUI between approx 100 and 250 msec and prevent any noticeable lag at the cost of some uncertainty in normal coros. It would actually let you create multiple levels of priority depending on the size of the delays.

In some cases accurate timing is important, in others short delays are important, but not the exact time. For example you can open a machine guard and crush your hand in 500 msec, but you can't in 10 or 20 msec.

This is just a thought. I'll leave it up to your better experience to decide whether it has merit.

Chris

@chrismas9

@chrismas9 This is evidently more flexible but from a quick look at the implementation I think it would add significantly to the size of the module; the present solution re-uses much of Paul's code. So I've thought some more about your first suggestion.

This could be handled by an event loop method, say max_overdue_ms(t=None). The default would cause the scheduler to work as at present. A time value would cause a low priority coros to be scheduled if it became overdue by more than that amount.

I'll consider these ideas further - I do think something along these lines would be worthwhile. Thank you for the suggestions.

Pete

@peterhinch

@peterhinch Thanks for considering my ideas. I'm sorry I can't help with the code. My interest is to make things more robust for non professional programmers in industry. Programming is a secondary role for many people.

At one company I am trying to merge the programming from the electronics department (STM32 and C) with the mech and elec people who use PLC's and get them all to use MicroPython. The idea is that applications will be written by the programmers (maybe with C libraries for the secret sauce), but the field techs will be able to tweak and calibrate them when they install them. Even if the program needs cleaning up later they will be able to commission the machine and debug the software. Once it's installed and working the programmers can clean it up and release it. They use PLC's so they can do the field debugging without the programmers travelling to site.

In this scenario my interest is in making MycroPython and uasyncio less breakable in the hands of the field techs. They might have to add a coro for an unexpected sensor or device and I would rather the program works, but not quite as well, than have the GUI freeze and they can't work out why.

Chris

@chrismas9

@chrismas9 I have posted a version which implements this. Comments welcome.

@peterhinch

@peterhinch That's great, thanks. I will review it with one of our embedded programmers. As soon as I can get a real world application started with uasyncio I will give you more feedback. Chris

@chrismas9

@chrismas9 I hope users express sufficient interest for @pfalcon and @dpgeorge to see the merits of an official solution to this issue, whether along the lines of my approach or otherwise. Your two argument idea is more flexible but I want to minimise changes to the official code. The mod remains quite simple.

I'm convinced that some solution to the issues of timing accuracy and latency is needed to facilitate practical use of millisecond class scheduling.

@pfalcon

I hope users express sufficient interest for @pfalcon and @dpgeorge to see the merits of an official solution to this issue

No, that's not how it works. We don't invent our stuff here, we implement subset of Python language for constrained systems. Where we stray away from it, it's because of those constraints we have, not because "we can" or "because we want it to make us coffee" - just because we have to. At all times, we choose "smaller" solution (not strictly monotonically by all criteria, sometimes we make bigger API to get smaller memory usage, but "smaller" is always the top-level goal).

Thus, if upstream asyncio doesn't have "priorities", then uasyncio can't have either. If you want to measure the level of enthusiasm, feel to submit patches (or just start a discussion) upstream.

On the other hand, just as asyncio, uasyncio strives to be extensible (at least so far), so you can subclass it and implement any (almost, perhaps) additional functionality via natural extension points. So, if today you need 2 levels of priorities, and tomorrow 3 - yes, you can. And nothing of that needs to be in uasyncio upstream.

The RFC stemmed from specific, real-world requirements of bare metal programming. Since Python normally runs under a pre-emptive OS without direct hardware access I doubt I'd find enthusiasm in asyncio upstream for ideas on millisecond-level timing.

Given that sleep_ms etc. have been added, it seemed logical to provide a mechanism to enable them to achieve their potential. But I take your point about extensibility. It's just Python after all :)

MicroPython targets running Python on microcontrollers with constrained resources (lower clock speed, lower RAM, lower ROM), and applications that run in these embedded environments often have real-time requirements. Therefore MicroPython should not just reimplement what CPython does, because it's used in an entirely different class of application. If MicroPython (or it's libraries) need to make changes to suit the specialised target applications, then it shouldn't shy away from it just because CPython doesn't do it that way. A lot of embedded requirements would not be on the radar for CPython devs. If that is the philosophy of MicroPython then the arguments for sticking with C/C++ are more valid.

As an official solution isn't going to happen I'll persist with my own efforts; I have further ideas on enhancing its performance in embedded systems. MicroPython (coupled with the good design of the official library) makes such changes straightforward.

@peterhinch

@peterhinch : You may be interested to survey how other asyncio alternatives (going to) go out of their way to do things similar to what you're talking about: python-trio/trio#32

Thank you for the link - an interesting approach with an ingenious implementation. However I concur 100% with your view that deterministic round-robin scheduling is vital to the baremetal firmware writer.

The most salient reason is in inter-task communication. Assume fair round-robin scheduling and consider the case where a task signals another and then yields. If the recipient always cedes control with yield the scheduler guarantees that the recipient has received the signal (and possibly signalled a response) when the sender's execution resumes. In a scheme where the signalled task might not have been scheduled, unpleasant code in the form of an interlock would be required.

Deterministic scheduling also facilitates worst-case timing analysis.

Lastly I think the design philosophy is wrong for time sensitive firmware which accesses hardware. The Trio team aim to emulate the behaviour of a preemptive scheduler. This has evident merits in the case of CPU-bound systems and in their principal targets of web and monitoring applications.

One would hope that time critical firmware systems are not CPU-bound. Programmers who choose cooperative scheduling in preference to pre-emptive do so for specific reasons. One of these is fast deterministic scheduling. Such users would expect to understand (at a high level) how the scheduling algorithm works, and can be expected to design tasks which don't hog execution without yielding.

Regarding my experiment with additional priority levels I was interested to see if this could be bolted on to uasyncio. But actual use cases are uncommon. A common requirement is task cancellation. When can we hope to see PR's #3380 and micropython/micropython-lib#221 merged?

Navigation Menu

Repository navigation

RFC: extending uasyncio scheduling algorithm with different priorities #2989

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

RFC: extending uasyncio scheduling algorithm with different priorities #2989

Description

Activity

pfalcon commented on Apr 1, 2017

peterhinch commented on Apr 1, 2017

pfalcon commented on Apr 1, 2017

peterhinch commented on Apr 1, 2017

peterhinch commented on Apr 4, 2017

dpgeorge commented on Apr 4, 2017

pfalcon commented on Apr 4, 2017

peterhinch commented on Apr 4, 2017

peterhinch commented on Apr 5, 2017

pfalcon commented on Apr 5, 2017

peterhinch commented on Apr 5, 2017

peterhinch commented on Apr 8, 2017

peterhinch commented on Apr 8, 2017

dpgeorge commented on Apr 11, 2017

peterhinch commented on Apr 29, 2017

chrismas9 commented on Apr 29, 2017

peterhinch commented on Apr 30, 2017

chrismas9 commented on Apr 30, 2017

peterhinch commented on May 1, 2017

chrismas9 commented on May 1, 2017

peterhinch commented on May 1, 2017

chrismas9 commented on May 1, 2017

peterhinch commented on May 1, 2017

pfalcon commented on May 1, 2017

peterhinch commented on May 1, 2017

BrendanSimon commented on May 6, 2017

peterhinch commented on May 6, 2017

pfalcon commented on Nov 27, 2017

peterhinch commented on Nov 28, 2017

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions