Forums

Task priorities in non strictly real-time systems

Started by pozz January 3, 2020
pozz wrote:
> Il 03/01/2020 15:19, David Brown ha scritto:
<snop>
> > You're right, cooperative scheduling is better if I want to reuse the > functions used in superloop architecture (that is a cooperative scheduler). >
Preemptive scheduling probably causes more problems than it solves, over some problem domains. SFAIK, cooperative multitasking can be very close to fully deterministic, with interrupts being the part that's not quite deterministic. -- Les Cargill
Clifford Heath wrote:
> On 5/1/20 11:58 am, pozz wrote:
<snip>
> > I wish I could, but it is actually a frightfully difficult subject. > Basically it's the same as thread-safe programming. > Only about 1% of programmers think they can do it. > Of those, only about 1% actually can. >
I could show anyone how in an afternoon. So I take your statement as being "only 1% of 1% have been forced to take that afternoon to learn it." I should qualify that - I could show anyone working on a classic architecture how. With multilevel caches and certain sorts of MMUs, there may be more to it. I'm thinking the WindRiver drivers course was about one week, which should about cover everything conceptually.
> It's the 0.99% that you have to worry about. At least some of them for > Toyota. Don't be one of them! > > However, this difficulty is precisely why Rust was created. Although I > haven't yet done a project in Rust, I've done enough multi-threaded work > in C++ to know that the ideas in Rust are a massive leap forwards, and > anyone doing this kind of work (especially professionally) owes it to > their users to learn it. >
I seriously doubt Rust represents some quantum leap here. <snip>
> > You need to understand about basic mutex operations, preferably also > semaphores, and beyond that to read and write barriers (if you want to > write lock-free code). It's a big subject. >
And that's about an afternoon, really. Not so much the barriers and bothering with lock-free. That may take a little more.
> Clifford Heath.
-- Les Cargill
Paul Rubin wrote:
> pozz <pozzugno@gmail.com> writes: >> As I already wrote many times, I don't have experience with RTOS and >> task sync mechanism such as semaphores, locks, mutexes, message queues >> and so on. >> So I'm not able to understand when a sync is really needed. >> >> Could you point on a good simple material to study (online or book)? > > I have found it simplest to have tasks communicate by message passing, > the so-called "CSP model" (communicating sequential processes), rather > than fooling around with explicit locks. With locks you have to worry > about lock inversion and all kinds of other madness, and your main hope > of getting it right is formal methods, like Lamport used for the Paxos > algorithm. Message passing incurs some cpu overhead because of the > interprocess communication and context switches, but it gets rid of a > lot of ways things go wrong. > > If your RTOS supports message passing (look for "mailboxes" in the RTOS > docs) then I'd say use them. >
Mailboxes are just semaphores with extra steps :) When I've written mailboxes for use in user space, they usually use a semaphore. In kernel space, you're already under a "semaphore" ( but still subject to asynchronous interrupts ). This of course varies by O/S....
> The language most associated with CSP style is Erlang, which doesn't > really fit on small embedded devices, but Erlang materials might still > be a good place to learn about the style. Erlang inventor Joe > Armstrong's book might be a good place to start: >
Erlang is a fine system,. The ( arguably ) best thing it provides is the "actor pattern", which applies independent of language choice. <snip> -- Les Cargill
pozz wrote:
> Il 03/01/2020 15:28, Niklas Holsti ha scritto:
<snip>
> > Yes, converting a blocking task in a non-blocking state-machine task can > be hard, but it's complex to write tasks in a preemption schuduler (you > need to know when to use locks, semaphores, mutexes and so on). > >
The question becomes - how important is determinism in your system? IMO, this can be expressed in economic terms - more determinism means fewer times the phone rings. <snip> -- Les Cargill
On 2020-01-05 21:46, Les Cargill wrote:
> pozz wrote: >> >> Yes, converting a blocking task in a non-blocking state-machine task >> can be hard, but it's complex to write tasks in a preemption schuduler >> (you need to know when to use locks, semaphores, mutexes and so on).
I think that makes it sound harder than it is. Avoid directly shared variables when you can, using whatever message-passing tools the language or RTOS provides, or wrap all operations that access shared data in mutexes, and that will solve most problems. What remains is mainly the skill and experience to design the shared data structures so that the mutex-protected operations are short and snappy without introducing polling, race conditions, deadlocks or starvation. But that polish is needed only for systems where processing resources are tight, which is not often the case today.
> The question becomes - how important is determinism in your system? IMO, > this can be expressed in economic terms - more determinism means fewer > times the phone rings.
I've been implementing pre-emptive, priority-driven real-time systems, off and on, since the mid-80's and never has the phone rung because of the non-determinism. Yes, many customer write requirements saying that they want "simple, deterministic scheduling", and then write other requirements for which the only clean solution is a pre-emptive system. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ .
On 6/1/20 6:39 am, Les Cargill wrote:
> Clifford Heath wrote: >> On 5/1/20 11:58 am, pozz wrote: > <snip> >> >> I wish I could, but it is actually a frightfully difficult subject. >> Basically it's the same as thread-safe programming. >> Only about 1% of programmers think they can do it. >> Of those, only about 1% actually can. >> > > I could show anyone how in an afternoon. So I take your statement as > being "only 1% of 1% have been forced to take that afternoon to learn it." > > I should qualify that - I could show anyone working on a classic > architecture how. With multilevel caches and certain sorts of MMUs, > there may be more to it. > > I'm thinking the WindRiver drivers course was about one week, which > should about&#2013266080; cover everything conceptually. > >> It's the 0.99% that you have to worry about. At least some of them for >> Toyota. Don't be one of them! >> >> However, this difficulty is precisely why Rust was created. Although I >> haven't yet done a project in Rust, I've done enough multi-threaded >> work in C++ to know that the ideas in Rust are a massive leap >> forwards, and anyone doing this kind of work (especially >> professionally) owes it to their users to learn it. >> > > I seriously doubt Rust represents some quantum leap here. > > <snip> >> >> You need to understand about basic mutex operations, preferably also >> semaphores, and beyond that to read and write barriers (if you want to >> write lock-free code). It's a big subject. >> > > And that's about an afternoon, really. Not so much the barriers and > bothering with lock-free. That may take a little more.
Behold a 0.99%-er! :)
On 1/5/20 2:32 PM, Les Cargill wrote:
> pozz wrote: >> Il 03/01/2020 15:19, David Brown ha scritto: > <snop> >> >> You're right, cooperative scheduling is better if I want to reuse the >> functions used in superloop architecture (that is a cooperative >> scheduler). >> > > Preemptive scheduling probably causes more problems than it solves, over > some problem domains. SFAIK, cooperative multitasking can be very close > to fully deterministic, with interrupts being the part that's not quite > deterministic. >
Preemptive scheduling solves a lot of serious issues when there are significant Real-Time requirements, as without it, every task needs to at least check for a possible task switch often enough to allow the tight real-time operations to complete on time. Yes, if that operation can be done COMPLETELY is the hardware ISR, then other operations don't need to worry about them as they are just interrupts. It isn't that uncommon for these sorts of operations to need resources that mean they can't just complete in an ISR. Which is better for a give set of tasks if very dependent on those tasks, and the skill set of the programmer(s). I tend to find for the problems I personally run into, preemption works well.
On 1/5/2020 12:32 PM, Les Cargill wrote:
> pozz wrote: >> Il 03/01/2020 15:19, David Brown ha scritto: > <snop> >> >> You're right, cooperative scheduling is better if I want to reuse the >> functions used in superloop architecture (that is a cooperative scheduler). > > Preemptive scheduling probably causes more problems than it solves, over some > problem domains. SFAIK, cooperative multitasking can be very close to fully > deterministic, with interrupts being the part that's not quite deterministic.
Preemptive frameworks can be implemented in a variety of ways. It need NOT mean that the processor can be pulled out from under your feet at any "random" time. Preemption happens whenever the scheduler is invoked. In a system with a time-driven scheduler, then the possibility of the processor being rescheduled at any time exists -- whenever the jiffy dictates. However, you can also design preemptive frameworks where the scheduler is NOT tied to the jiffy. In those cases, preemption can only occur when "something" that changes the state of the run queue transpires. So, barring "events" signalled by an ISR, you can conceivably execute code inside a single task for DAYS and never lose control of the processor. OTOH, you could end up losing control of the processor some epsilon after acquiring it -- if you happen to do something that causes the scheduler to run. E.g., raising an event, sending a message, changing the priority of some task, etc. In each of these instances, a preemptive framework will reexamine the candidates in the run queue and possibly transfer control to some OTHER "task" that it deems more deserving of the processor than yourself. process(); // something that takes a REALLY LONG time raise_event(PROCESSING_DONE); In the above, process() can proceed undisturbed (subject to the ISR caveat mentioned above), monopolizing the processor for as long as it takes. There will be no need for synchronization primitives within process() -- because nothing else can access the resources that it is using! *If* a task "of higher priority" (ick) is ready and waiting for the PROCESSING_DONE event, then the raise_event() call will result in THAT task gaining control of the processor. To the task that had done this process()ing, the raise_event() call will just seem to take a longer time than usual! It's easy to see how a time-driven mechanism is added to such a system: you just treat the jiffy as a significant event and let the scheduler reevaluate the run queue when it is signaled. I.e., every task in the run queue is effectively waiting on the JIFFY_OCCURRED event. (i.e., the jiffy becomes "just another source of events" that can cause the run queue to be reexamined) It's easy to see how you can get the same benefits of cooperative multitasking with this preemptive approach without having to litter the code with "yield()" invocations. This leads to more readable code AND avoids the race/synchronization issues that time-driven preemption brings about. The developer does have to be aware that any OS call can result in a reschedule(), though!
Clifford Heath wrote:
> On 6/1/20 6:39 am, Les Cargill wrote: >> Clifford Heath wrote: >>> On 5/1/20 11:58 am, pozz wrote: >> <snip> >>> >>> I wish I could, but it is actually a frightfully difficult subject. >>> Basically it's the same as thread-safe programming. >>> Only about 1% of programmers think they can do it. >>> Of those, only about 1% actually can. >>> >> >> I could show anyone how in an afternoon. So I take your statement as >> being "only 1% of 1% have been forced to take that afternoon to learn >> it." >> >> I should qualify that - I could show anyone working on a classic >> architecture how. With multilevel caches and certain sorts of MMUs, >> there may be more to it. >> >> I'm thinking the WindRiver drivers course was about one week, which >> should about&#2013266080; cover everything conceptually. >> >>> It's the 0.99% that you have to worry about. At least some of them >>> for Toyota. Don't be one of them! >>> >>> However, this difficulty is precisely why Rust was created. Although >>> I haven't yet done a project in Rust, I've done enough multi-threaded >>> work in C++ to know that the ideas in Rust are a massive leap >>> forwards, and anyone doing this kind of work (especially >>> professionally) owes it to their users to learn it. >>> >> >> I seriously doubt Rust represents some quantum leap here. >> >> <snip> >>> >>> You need to understand about basic mutex operations, preferably also >>> semaphores, and beyond that to read and write barriers (if you want >>> to write lock-free code). It's a big subject. >>> >> >> And that's about an afternoon, really. Not so much the barriers and >> bothering with lock-free. That may take a little more. > > Behold a 0.99%-er! > > :)
We can larf, but I think there's less to serialization than is made of it. -- Les Cargill
Richard Damon wrote:
> On 1/5/20 2:32 PM, Les Cargill wrote: >> pozz wrote: >>> Il 03/01/2020 15:19, David Brown ha scritto: >> <snop> >>> >>> You're right, cooperative scheduling is better if I want to reuse the >>> functions used in superloop architecture (that is a cooperative >>> scheduler). >>> >> >> Preemptive scheduling probably causes more problems than it solves, >> over some problem domains. SFAIK, cooperative multitasking can be very >> close to fully deterministic, with interrupts being the part that's >> not quite deterministic. >> > > Preemptive scheduling solves a lot of serious issues when there are > significant Real-Time requirements,
I don't know how to square the two things being said in that sentence fragment. Preemptive is inherently less deterministic than cooperative.
> as without it, every task needs to > at least check for a possible task switch often enough to allow the > tight real-time operations to complete on time.
Yes. You need to conform to some granularity in time.
> Yes, if that operation > can be done COMPLETELY is the hardware ISR,
Not so much...
> then other operations don't > need to worry about them as they are just interrupts. It isn't that > uncommon for these sorts of operations to need resources that mean they > can't just complete in an ISR. >
This isn't about interrupts; it's about chunking the mainline processing into phrases. After each phrase the thread can block.
> Which is better for a give set of tasks if very dependent on those > tasks, and the skill set of the programmer(s). I tend to find for the > problems I personally run into, preemption works well.
Preemption is often the default state now, and people simply get used to it. -- Les Cargill