Re: From cooperative to preemptive scheduler [Stack]

From	Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups	comp.arch.embedded
Subject	Re: From cooperative to preemptive scheduler [Stack]
Date	2020-01-15 23:30 +0200
Organization	Tidorum Ltd
Message-ID	<h89ek2Ft3g7U1@mid.individual.net> (permalink)
References	<qv0lmu$up1$1@dont-email.me> <qvkc2v$3p8$1@dont-email.me> <h897biFrkeqU1@mid.individual.net> <h89dhsFss9jU1@mid.dfncis.de>

Show all headers | View raw

On 2020-01-15 23:12, Hans-Bernhard Bröker wrote:
> Am 15.01.2020 um 20:26 schrieb Niklas Holsti:
> 
>> Having a single stack rather than per-task stacks is easier if one has
>> to program the high-water-mark method for measuring stack usage
>> separately and manually for each stack.
> 
> No.  It's exactly as easy.  You just do the same thing for each stack as
> you would for a single one.

In terms of intrinsic difficulty, yes. In terms of the amount of manual 
work, no.

>> Static analysis of stack usage bounds, either by a dedicated tool from
>> the machine code or as an extra function of the compiler and linker, is
>> really so simple
> 
> Objection.  It is simple only in a limited class of use cases.  As soon
> as there is any use of function pointers or the merest hint of possible
> recursion, static stack analysis becomes equivalent to Turing's Halting
> Problem.  Problems don't really get much harder than that one.

In theory, yes. In practice, no. The Halting Problem is impossible to 
solve for *all* programs. It doesn't mean that solutions are impossible 
for a *large* class of *common* programs.

Most programs are designed cleanly enough to make stack-usage analysis 
possible. An exact value is not needed; an upper bound is enough, if it 
isn't very pessimistic. Assuming that the type system is not broken, a 
whole-program analysis can figure out all possible target functions of 
any function pointer.

For recursion, I agree that some manual support (provide a bound on the 
depth of recursion) is usually needed. However, embedded programs rarely 
use recursion in any non-trivial way. And most functions have 
stack-frames of static size; it is rare to allocate dynamic amounts of 
stack.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Back to comp.arch.embedded | Previous | Next — Previous 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