Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #29109

Re: From cooperative to preemptive scheduler: a real example

Show all headers | View raw

Il 16/01/2020 21:24, Niklas Holsti ha scritto:
> On 2020-01-16 15:48, pozz wrote:
>> Il 15/01/2020 17:53, Niklas Holsti ha scritto:
>     ...
>>> The approach where all real-time "tasks" are interrupts is called 
>>> "foreground-background", I believe. It was popular in the 
>>> microcomputer era, before real-time kernels became popular -- it gave 
>>> most of the same benefits (pre-emption) but scheduled by HW 
>>> (interrupt priorities).
>>
>> Yes "foreground-background" is another name, but it says nothing about 
>> the blocking/non-blocking of background (non interrupts) tasks.
>> If you have blocking (long running) tasks, you will not have a 
>> reactive system (only interrupts will be reactive).
> 
> Reactivity was the very point of the architecture - anything that needed 
> quick response executed at interrupt level. The background was just a 
> sequential process that handled all the non-time-critical things (often 
> stuff delegated from the interrupt levels).
> 
> Those machines usually had prioritized interrupt systems where a 
> higher-priority interrupt could interrupt (and thus pre-empt) a running 
> lower-priority interrupt handler. So the systems were definitely reactive.

I was using reactive word with another meaning.

Real-time response is critical and must be managed by interrupts (that 
can preempt background tasks). If a char is received from a UART with a 
single-byte FIFO, you *need* to move it in RAM as soon as possible, to 
avoid discarding the next byte that could arrive immediately after.

Reactivity is much less critical. You press a button on a keyboard and 
you expect to see that character on the display as soon as possible. It 
can appear after 10ms and you will be very happy (wow, this PC is very 
reactive), but can appear, maybe a few times, after 500ms and you will 
be less happy (shit, how slow is this PC?). In both cases, the system 
does its job.

I usually manage reactivity of the system in non-interrupt background 
tasks. In order to have high reactivity, I need to maintain the 
superloop duration short (of course, if the tasks are maximum 10), so my 
first rule when implementing a task: it mustn't block waiting for I/O or 
mustn't spend too much time in calculations.
If this happens, I try to transform the task in state-machine and I can 
say the reactivity of the system is normally very good.

Of course, I know there are some extreme cases where you have 100 tasks 
(I admit it's impossible to maintain a good general reactivity in this 
case, even if every single task is fast) or when a task is very CPU 
intensive (FFT, encryption, ...).
I think those are examples of a few applications where preemptive 
multitasking approach is the right answer to have a good reactivity.

But in many many other applications you can guarantee real-time (through 
interruts) and reactivity (through non-blocking background tasks) with a 
simple superloop cooperative approach, without multitask issues (...and 
critical bugs) but with an additional complexity (state-machine).


>> If the tasks are coded as non-blocking (maybe with the help of 
>> state-machines), you will be able to have a reactive system even for 
>> the non-interrupts tasks.
> 
> Not needed in a foreground-background system.

What is not needed? Reactivity?


>>>> [pozz:] Interrupts are always present, even in superloop.
>>>
>>> Again a design choice. Some critical systems don't want *any* 
>>> pre-emption, even by interrupts -- simplicity reigns. ...
>>
>> I don't think this is an example that can be considered "typical" and 
>> I know there are "extreme cases" where a singular approach is needed.
> 
> Ok, but you said "always". 

My shame... often.


> I remember other examples of systems not 
> using interrupts -- usually small, quick-and-dirty-but-good-enough 
> applications.
> 
>>>> [pozz:] Maybe I am wrong, but I implement ISRs with great care
>>>> and attention,
>>>
>>> Of course you are right to use great care and attention, and 
>>> especially in ISRs.
>>>
>>>> but they are very small and limited.
>>>
>>> Many tasks in pre-emptive systems are also small and limited -- for 
>>> example, one of my designs has a task whose main loop just takes a 
>>> data-packet from an input queue, computes its CRC and appends it to 
>>> the packet, and puts the updated packet in an output queue. A handful 
>>> of source lines. ... 
>> I think you could write that task without a state-machine in superloop 
>> architecture:
> 
> If the result is fast enough, compared to the shortest deadline, of 
> course you can. But you can't be sure it will be fast enough if you 
> don't know (a) the maximum length of the packets (b) the speed of the 
> processor (c) the shortest deadline that would be at risk.
> 
> Note also that even if the CRC computation is fast enough not to 
> endanger other deadlines, if you make it one "task" in a superloop with 
> 100 other "tasks", it will be called only once per 100 "task" executions 
> (once per superloop iteration) which will limit the rate of packet flow, 
> which may violate a hard performance requirement.

Again you show examples that appears to me at minimum "extreme", not 
"typical". How many times you write applications with 100 tasks?

Ok, maybe it's better to say that I usually work on MCUs with internal 
Flash and RAM, just to say Cortex-Mx. My experience is with MCUs that 
run at maximum 100MHz and manage Ethernet or TFT, not together.

Now those MCUs are little monsters that can manage at the same time 
Ethernet, SD cards with FAT filesystems, USB, TFT display and so on. In 
those complex applications, I admit a preemptive approach could be a 
better choice.

[OT]
Anyway I don't know how much space those little monsters have in the 
market. Should I design a board with a lot of fast interfaces and the 
cost or power consumption weren't so important, most probably I would 
choose an embedded Linux SOM with a lot of Flash and RAM. And maybe I 
will choose Python as the language that speed up a lot the development.
[/OT]


> To fix that problem, you would have to go to a "major cycle - minor 
> cycle" design in which the superloop is the "major" cycle, but consists 
> of some number of "minor" cycles each of which calls the CRC computation 
> "task", to ensure that it is called often enough. This was the standard 
> approach to real-time systems before pre-emption became acceptable.
> 
> I only gave the CRC task as an example of a "task" that is as short as 
> or shorter than typical interrupt handlers. But perhaps that was going 
> off-topic.
> 
> (You may ask, why was that CRC calculation in a task of its own, and not 
> just in a subroutine called from other tasks? Because the processor had 
> a HW CRC unit, which the task used, and the CRC task serialized accesses 
> to that HW unit. So the task in fact blocked, waiting for the HW unit to 
> compute the CRC.)
> 
>> And here you don't have to think about multithreading issues (race 
>> condition, sharing resources, ...).
> 
> The multithreading issues in the CRC task are solved by the queue 
> data-structure, which is "task-safe" and used all around the system. No 
> specific multithreading problems for the CRC task. Five minutes to 
> design, 15 to implement.

Maybe multitasking issues aren't too complex... issues, after acquiring 
some experience and knowledge. At the moment they appear to me very complex.


>>>> [pozz:] Normally the biggest part of the firmware is related to the 
>>>> application/tasks, not interrupts.
>>>
>>> Except in the aforementioned foreground-background designs.
>>
>> Even in foreground-background ISRs are limited to critical real-time 
>> events.
> 
> You still don't get the point. In a foreground-background system, the 
> "interrupt service routines" (the foreground) *are* the tasks and 
> implement all of the main system functions. The background process is 
> used only for the "left-overs" -- say, memory scrubbing in a space-based 
> system. Of course there may be a considerable amount of "left-overs" if 
> deadlines are tight and some non-urgent but interrupt-triggered 
> activities can't fit in the foreground processing.

What I mean with "foreground-background" system is another thing. A few 
critical real-time requirements are managed in foreground interrupts 
routines, the biggest part of the application, that should be reactive 
for the user, are managed by some background tasks.

I have an example of an IoT board based on a Cortex-M3 MCU by NXP. The 
MCU communicates with a remote device through a RS485 bus, and with a 
Cloud system (actually AWS) through Ethernet.
In this application I have three main foreground ISR-based drivers 
(timer, Ethernet and UART) and some background tasks: lwip TCP/IP stack, 
RS485 protocol parser, LEDs and some other minors.

The real-time requirements are only for communication links: we 
shouldn't loose Ethernet frames nor RS485 characters.
When some events are communicated over RS485, a message is published on 
the Cloud as soon as possible.

This system is implemented with a superloop cooperative approach and I 
can say the reactivity is good.

The Internet protocol is MQTTs, so the security layer mbedTLS runs 
together with lwip. It hasn't been a simple job, because mbedTLS needed 
a lot of RAM during TLS session handshake.
lwip can work in "no OS" systems by calling sys_check_timeouts() 
function regularly... and I simply call it in my superloop.

MQTT client state-machine is not so complex, there are only a few main 
states:
- waiting for DNS replay (to resolve server domain address)
- waiting for MQTT connection ack from the server
- MQTT connected (where the message are published)

I admit mbedTLS is very slow during TLS session startup, because of 
asymmetric encryption (the MCU doesn't have hw crypto engine). During 
this period reactivity isn't good.
I don't loose chars from RS485 (thanks to interrupts), but a timeout 
expires on the RS485 remote device that thinks the Ethernet board is 
dead. Luckily this happens only during TLS startup and the problem can 
be filtered in a simple way.

Recently I have seen that mbedTLS added a feature to split CPU intensive 
calculations in smaller steps, exactly to avoid blocking in cooperative 
systems[*]. I think they implent somewhat similar to a state-machine.

Just to say that this isn't so illogical approach.

[*]https://tls.mbed.org/kb/development/restartable-ecc

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 02:08 +0100
  Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-06 19:37 -0700
    Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 10:11 +0100
      Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-07 07:51 -0700
        Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 23:51 +0100
          Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 01:39 +0200
            Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:42 +0100
              Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 18:39 +0200
          Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-08 23:12 -0700
            Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:49 +0100
          Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-08 23:12 -0700
          Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-09 01:33 -0700
  Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-07 09:38 +0200
    Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-08 00:02 +0100
      Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 00:54 +0200
        Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-09 12:19 +0100
          Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 14:03 +0200
            Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:32 +0100
              Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 18:53 +0200
                Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-16 14:48 +0100
                Re: From cooperative to preemptive scheduler: a real example upsidedown@downunder.com - 2020-01-16 21:04 +0200
                Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-16 22:24 +0200
                Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-17 02:05 +0100
                Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-18 23:03 +0200
  Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-14 13:27 +0100
    Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-14 20:10 +0100
      Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-15 09:36 +0100
        Re: From cooperative to preemptive scheduler [Stack] Stef <stef33d@yahooI-N-V-A-L-I-D.com.invalid> - 2020-01-15 11:30 +0100
          Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-15 11:51 +0100
        Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-15 21:51 +0100
    Re: From cooperative to preemptive scheduler [Stack] Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 21:26 +0200
      Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-15 22:12 +0100
        Re: From cooperative to preemptive scheduler [Stack] Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 23:30 +0200

csiph-web