Forums

Task priorities in non strictly real-time systems

Started by pozz January 3, 2020
Don Y wrote:
> 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.&#2013266080; In a system > with a time-driven scheduler, then the possibility of the processor > being rescheduled at any time exists -- whenever the jiffy dictates. >
That seems to me to be incorrect. "Preemptive" means "the scheduler runs on the timer tick." I'd say "inherently".
> However, you can also design preemptive frameworks where the scheduler > is NOT tied to the jiffy.&#2013266080; In those cases, preemption can only occur > when "something" that changes the state of the run queue transpires.
I agree in that I think we have to hold the run queue discipline separate from whether the jiffy tick runs the run queue. But in my mind at least, your "something" is inherently cooperative - a thread has blocked - unless that "something" is the timer tick. At this point, I should probably say that my opinion on this is probably derived from the Peterson-Silberchatz book.
> 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.&#2013266080; E.g., raising an event, sending a message, > changing the priority of some task, etc.&#2013266080; 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. > > &#2013266080;&#2013266080;&#2013266080; process();&#2013266080;&#2013266080; // something that takes a REALLY LONG time > &#2013266080;&#2013266080;&#2013266080; raise_event(PROCESSING_DONE); >
So how is "raise_event" not blocking? Er, rather, what value would that serve? It's nominally the same as a relinquish() operation on a semaphore. I see this as three cases: - current task priority < another ready task - then the intention of priority is thwarted. - priorities are equal. Meh - flip a coin, possibly biased away from the current task. - Greater than - well, we're not gonna switch, are we? So I think this all sums to "it's blocking."
> In the above, process() can proceed undisturbed (subject to the > ISR caveat mentioned above), monopolizing the processor for as long > as it takes.&#2013266080; 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.&#2013266080; To the task > that had done this process()ing, the raise_event() call will just > seem to take a longer time than usual! >
Right; so it's "fractionally" blocking. Like dude, that's totally cooperative multitasking :) The running thread did something to run the ready queue. Historically, this all goes back to the transition from "batch" to "multiuser" in the Dark Ages - it was necessary to synthesize an event to switch. A time was as good as anything.
> It's easy to see how a time-driven mechanism is added to such > a system:&#2013266080; you just treat the jiffy as a significant event > and let the scheduler reevaluate the run queue when it is > signaled.&#2013266080; I.e., every task in the run queue is effectively > waiting on the JIFFY_OCCURRED event. >
Yep. However, I'm not prepared to call the absence of the jiffy event preemptive. In truth, it's kinda like a middle place between "cooperative big loop stuff" and a fully preemptive situation.
> (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.
I really think of the goal here to chunk an operation into meaningful ... chunks, each of which is more or less "atomic", and yielding between them. I've never had that not work out for me. Goes back to things on DOS in state machines, headending on things like multiple serial ports.
> This leads to more
> readable code AND avoids the race/synchronization issues that > time-driven preemption brings about.
Mmmmm.... I think you still have those when it comes to shared state. That's more of something to prove out locally. I will say - I prefer to think in terms of "regulation", like a regulator clock releasing things, when I can more than "grab(); process() ; relinquish();" if I can. &#2013266080; The developer does have to
> be aware that any OS call can result in a reschedule(), though!
It's been my experience that any O/S call should be assumed to cause a running of the ready queue :) -- Les Cargill
On 6/1/20 2:00 pm, Les Cargill wrote:
> Clifford Heath wrote: >> On 6/1/20 6:39 am, Les Cargill wrote: >>> Clifford Heath wrote: >>>> 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. > We can larf, but I think there's less to serialization than is made of it.
Serialization using one giant lock isn't too hard - that's how people write code using interrupts. But it's a very simplified case, and the problem is to use such simple locking to construct correct algorithms at a higher level. Many apparently straightforward algorithms have dire pathologies when the atomic operations can get interspersed at will. In many cases the bugs will not ever show up during testing. And *that* is the real problem. Such code must be *correct by construction*, but people generally don't work that way. Clifford Heath.
Hi Les,

On 1/5/2020 8:26 PM, Les Cargill 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. > > That seems to me to be incorrect. "Preemptive" means "the scheduler runs on the > timer tick." I'd say "inherently".
Then, by your definition, any system without a scheduler tied to the jiffy is "cooperative"? And, any system without a jiffy (at all!) would also have to be considered cooperative? How do you further refine systems wherein OS calls run the scheduler if the run queue has been altered as opposed to those that only run the scheduler when "yield()" is invoked? Do you expect the current task to EVER lose control of the processor in the following code fragment (in a cooperative system)? process(...); raise_event(...); send_message(...); // consider case of message queue "full"! receive_message(...); // consider case of no message is pending! If I disable the timer interrupt (e.g., assume timer fails!) in a preemptive system, do you expect the processor to ever transfer control to any other task (same code fragment)?
>> 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. > > I agree in that I think we have to hold the run queue discipline separate from > whether the jiffy tick runs the run queue. But in my mind > at least, your "something" is inherently cooperative - a thread has > blocked - unless that "something" is the timer tick.
The "something" is not "yield()". Should the developer be surprised by the fact that the scheduler ran (in a cooperative system)? If the developer tries to transmit a character via a UART and the UART Tx register is presently full, should he expect his task to lock up the processor while waiting for the UART ISR to (eventually) make the Tx register "ready"? (in a cooperative system? in a preemptive system with the timer IRQ disabled?) [What does the putchar() code look like in each of these cases? Do you *spin* waiting on the UART? ] A more natural expectation (re: preemption) is that calling on the "system" should be fair game for the system to preempt the current task whenever the situation changes enough to alter the choice of "most runnable" task. A more natural expectation (re: cooperative) is that the absence of an explicit "yield()" means the task retains control of the processor.
> At this point, I should probably say that my opinion on this is > probably derived from the Peterson-Silberchatz book. > >> 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); > > So how is "raise_event" not blocking? Er, rather, what value would that serve? > It's nominally the same as a relinquish() operation on a semaphore. I see this > as three cases:
In a cooperative environment (using my above definition), I could raise dozens of events, sequentially, without fear of any of them being acted upon /until I explicitly yield()-ed/. I wouldn't worry about adding some sort of mechanism to treat the series of raise()'s as an atomic operation -- because my postponing of the yield() effectively guarantees this atomicity. Effectively, this becomes: priority = get_priority(); set_priority(MAX+1); raise_event(...); ... raise_event(...); set_priority(priority); (i.e., running the scheduler in each raise() will still not steal the processor away from the current task)
> - current task priority < another ready task - then the intention > of priority is thwarted. > > - priorities are equal. Meh - flip a coin, possibly biased away from > the current task. > > - Greater than - well, we're not gonna switch, are we? > > So I think this all sums to "it's blocking." > >> 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! > > Right; so it's "fractionally" blocking. Like dude, that's > totally cooperative multitasking :) The running thread did something to > run the ready queue.
I'd wager that most folks using cooperative multitasking DON'T expect a task switch to occur at any time other than yield(). And, have probably not coded to guard against these possibilities.
> Historically, this all goes back to the transition from "batch" to "multiuser" > in the Dark Ages - it was necessary to synthesize an event to switch. A time > was as good as anything. > >> 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. > > Yep. However, I'm not prepared to call the absence of the jiffy > event preemptive.
Yes you'll agree that the scheduler can run at times OTHER than the jiffy? And, the user shouldn't be surprised that his task has lost control of the processor between two lines of code, neither of which was a "yield()"?
> In truth, it's kinda like a middle place between "cooperative big loop stuff" > and a fully preemptive situation.
Another misnomer is "big loop == cooperative". The "big loop" serves the function of (crude, naive, simplistic) scheduler. It's presence is not required for a cooperative system. E.g., yield() could call a function that saves the current PC/state on the current stack, examines a list of TCBs on the run queue, selects the most runnable, restores the stack from that TCB, restores the state for that task and "returns" to the PC resident on that stack. No timer. No loop. 100% cooperative. The earliest designs I worked on saved NO task state (besides PC), supported different "task priorities" and didn't require any special mechanisms to ensure the statements in a task() were processed sequentially. So: while(FOREVER) { task1(); task2(); task3(); } task1() { foo = 0; yield(); foo++; yield(); foo++; yield(); if (2 != foo) { panic(); <blah> } } would behave as you'd expect (i.e., no panic). You can do this on all sorts of super-tiny processors that don't seem like they'd lend themselves to multitasking, otherwise.
>> (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. > > I really think of the goal here to chunk an operation into meaningful > ... chunks, each of which is more or less "atomic", and yielding between them.
If you look at many practical applications, you can see how this almost naturally follows. E.g., you update a FIFO (head, tail, contents) and THEN do something that exposes the scheduler -- instead of having to remember to lock the scheduler out while you do SOME of the FIFO update, tinker around with something unrelated, finish the balance of the FIFO update and THEN unlock the scheduler. Paraphrasing the above: task1() { not_done: if (data != available) return; grab_available_data(); yield(); process_grabbed_data(); yield(); if (data == complete) { // act on the processed data } else { goto not_done; } <blah> } I.e., grab_available_data() likely involves talking to a shared FIFO (the producer being some other process). Note that there is no need for synchronization primitives because grab_available_data() is written NOT to contain any explicit yield()'s -- and the developer operates on the assumption that he can do anything he wants without losing control of the processor as long as he avoids yield()! Likewise, while this task moves on (during its next activation) to process_grabbed_data(), the producer can have been working on making more data available (in the aforementioned FIFO). It's not hard to look at a "task" (job?) as consisting of these incremental steps towards the desired solution. The only contrivance is the presence of the "yield()" statements; i.e., you could see how the code would make sense "as is" with them elided... the series of steps would likely remain the same!
> I've never had that not work out for me. Goes back to things > on DOS in state machines, headending on things like multiple > serial ports. > >> This leads to more >> readable code AND avoids the race/synchronization issues that >> time-driven preemption brings about. > > Mmmmm.... I think you still have those when it comes to shared state.
Only if you allow operations on parts of that state that SHOULD be updated concurrently to be broken by the placement of a yield() -- or, other system call (which could effectively bring about a preemption, in the preemptive case).
> That's more of something to prove out locally. I will say - I prefer to > think in terms of "regulation", like a regulator clock releasing things, when I > can more than "grab(); process() ; relinquish();" if I can.
Isn't my above example exactly this? With yield()'s interposed between steps?
>> The developer does have to >> be aware that any OS call can result in a reschedule(), though! > > It's been my experience that any O/S call should be assumed > to cause a running of the ready queue :)
Should reading a character from a UART cause the scheduler to run? (what if the UART doesn't have data pending? Should the call cause the system to spin -- effectively blocking ALL tasks?) Should posting a datagram cause the system to spin until the network is ready to XMIT it? Should the network stack be implmented in an ISR? Where are the routines that one would consider "O/S calls" enumerated (so I know if it's safe to call them without risk of a reschedule())? Do all the debug() mechanisms exist within the O/S framework? Or, outside it? This is why it's "safer" to assume that cooperative frees the developer from thinking about losing the processor in all cases other than an explicit yield(). And, that the scheduler in the cooperative case need not be a "super loop"; you may not be able to predict the successor task to yours when you yield! (but, you can be assured that nothing will steal the processor away from you until you relinquish it!) And, why its safer for preemptive to require the developer to behave as if any O/S call can cause preemption. And, that the timer may or may not be tied to the scheduler. Your system can work in the absence of a timer -- and, the absence of "yield()"! Treat the domain of O/S characteristics as a multiaxis space where each choice/implementation-option gives you another degree of freedom. It allows for a greater variety of approaches without pidgeon-holing solutions into just a few naive stereotypes. Exercise: Try writing an application where the timer just provides timing services but doesn't run the scheduler. Or, where the timer doesn't exist, at all! The run-time dynamics of your solution will change; but, the basic solution will likely remain the same. Likewise, try writing cooperative solutions where the processor can't be stolen away *without* a yield(). And, solutions where ANY operation that might affect another task's readiness could potentially result in a reschedule. And, solutions where there's no "superloop" but, rather, some other sort of scheduler. Try writing with a single/shared stack. Try writing with *no* saved state. You'll be amused at how LITTLE you need to actually solve many problems. Then, start to wonder why you're "expecting so much"! :>
On Sun, 5 Jan 2020 17:08:56 -0700, Don Y <blockedofcourse@foo.invalid>
wrote:

>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.
What is a jiffy ? Is it the time between two clock interrupts as in Linux ? What is so special about timer interrupts vs. other interrupts e.g. UART interrupts ? Here is example how a very simple pre-emptive RT kernel worked: In the original version for a processor with only a few registers and when the hardware saved all registers on the stack before the interrupt service routine (ISR) was executed and restored after the return from interrupt instruction was executed. When the system was started in the main program, a subroutine call was executed for each task to be created. This subroutine allocated a local stack for the task as well as a 3 byte task control block consisting of 1 byte task state and 2 byte saved stack pointer. The task was started, which then performed a software interrupt storing original registers for that task on the local stack. After all task had been created in priority sequence, the main program entered an eternal loop (the null task) possibly containing a wait for interrupt instruction to reduce power consumption. The 3 byte task control blocks were in fixed priority order (as created) and adjacent locations in memory. When a task was running using its local stack and some kind of hardware interrupt occurred, the registers were saved on local stack by the hardware. The active stack pointer was then stored into the task specific saved SP in the task control block. The ISR was then executed using the local stack, potentially altering the runnability of some other dormant task. Before performing a return from interrupt the scheduler was executed. The scheduler checked the task state byte of each created task (requiring just 3 instructions/task). If no new higher priority task had become runnable, the scheduler performed a simple return from interrupt restoring the registers from the local stack and the suspended task was resumed. However, if the ISR had made a higher priority task runnable, The scheduler would then load the stack pointer from the saved stack pointer from the new stack and a return from interrupt is performed, restoring the saved registers from the newly activated local stack and the activated task continued from where it was originally suspended. If a running task had no more work to do but wanted to wait for an interrupt or message from other task, it could execute a software interrupt, saving the registers on local stack and activate the scheduler. If no tasks were runnable, execution fell through into the null task at the end of the main program. With processors with more registers in which all registers weren't saved automatically upon each interrupt, the scheduler had to check if a task switch to a new task needs to be performed, the additional registers were pushed to the old stack and from the new stack additional registers were loaded before returning from interrupt. If no task switching was required, no additional register saves/restores were needed, just the hardware save/restore was automatically executed. Thus, a RT kernel can be really simple.
On 1/6/2020 1:44 AM, upsidedown@downunder.com wrote:
> On Sun, 5 Jan 2020 17:08:56 -0700, Don Y <blockedofcourse@foo.invalid> > wrote: > >> 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. > > What is a jiffy ? Is it the time between two clock interrupts as in > Linux ? What is so special about timer interrupts vs. other interrupts > e.g. UART interrupts ?
A jiffy is nominally the basic unit of time in a particular system. It need never be exposed to a developer (or user). It may (or may not!) correspond to the period of the fastest timer interrupt used as a timebase in a system. [There are certain contexts where it takes on very specific -- and numerical -- meanings] There's nothing magical about the jiffy. But, it's typically wired to an IRQ (directly or indirectly). With all the right mechanisms in place for a preemptive system, the jiffy can just raise an event (JIFFY_OCCURRED) and a very high priority "task" *in* the kernel will be dispatched which will run the scheduler. An event raised by a UART IRQ can be handled identically. The task(s) that are waiting on the assertion of that event are "immediately" run as the scheduler discovers them to be ready (and, presumably, of sufficient "priority" to cause the currently running task to be preempted). E.g., you don't need a timer to have a preemptive system. You could implement an "RS232 filter" with a pair of UARTs each raising UARTx_READY events that cause UARTx_Task() to be made ready -- instead of coding all of that in the ISRs for the UARTs. Let the ISRs handle the timely actions -- like pulling characters out of the receiver, twiddling RTS/CTS/DCD/DTR, injecting flow control characters -- XON/XOFF -- in the Tx stream, etc. Let the tasks handle the "filtering" activities without burdening the ISRs. Repeat the analysis for a network packet being received, a message being passed from one task/process to another, etc. As events can alter the state of the run queue -- by making eligible to run those tasks that are presently BLOCKING, awaiting specific events -- when raise_event is invoked, it is common to run the scheduler to reexamine the run queue and make any adjustments to the selection of "currently executing task". As an "event" carries no real information (data) beyond the fact that it *occurred*, it is typically a very lightweight mechanism. There are typically very few of them supported by the OS -- often defined by the number of bits in the native "word size" (this allows a task to specify a *set* of events in which it may have an interest -- as a bit-vector; any ONE will suffice). This simplifies the work of deciding if ANY of the waiting task's significant events have made it eligible to run. [Note that events are transient; they aren't stored like "flags". So, if an event happens and you're not watching for it, you never *see* it!]
> Here is example how a very simple pre-emptive RT kernel worked: > > In the original version for a processor with only a few registers and > when the hardware saved all registers on the stack before the > interrupt service routine (ISR) was executed and restored after the > return from interrupt instruction was executed. > > When the system was started in the main program, a subroutine call was > executed for each task to be created. This subroutine allocated a > local stack for the task as well as a 3 byte task control block > consisting of 1 byte task state and 2 byte saved stack pointer. The > task was started, which then performed a software interrupt storing > original registers for that task on the local stack.
This (storing present state on the task's stack) is a common approach. It is also possible to store the register state *in* the TCB (a larger structure being needed for that). But, these are just efficiency tradeoffs.
> After all task had been created in priority sequence, the main program > entered an eternal loop (the null task) possibly containing a wait for > interrupt instruction to reduce power consumption. > > The 3 byte task control blocks were in fixed priority order (as > created) and adjacent locations in memory. > > When a task was running using its local stack and some kind of > hardware interrupt occurred, the registers were saved on local stack > by the hardware. The active stack pointer was then stored into the > task specific saved SP in the task control block. The ISR was then
Meaning you have to remember where the TCB (3 bytes, in your example) is for the currently executing task.
> executed using the local stack, potentially altering the runnability > of some other dormant task. > > Before performing a return from interrupt the scheduler was executed.
The problem with this is that the scheduler may end up being bulky and take a nontrivial amount of time to make up its mind. Another approach is to "schedule" the scheduler to run at the COMPLETION of the ISR. I.e., interpose the scheduler's invocation between the "return-from-interrupt" and the actual "return to task that was interrupted".
> The scheduler checked the task state byte of each created task > (requiring just 3 instructions/task). If no new higher priority task > had become runnable, the scheduler performed a simple return from > interrupt restoring the registers from the local stack and the > suspended task was resumed.
Deciding and picking can often be far more complicated actions. And, the criteria used to make that selection are often not simple (static?) priorities.
> However, if the ISR had made a higher priority task runnable, The > scheduler would then load the stack pointer from the saved stack > pointer from the new stack and a return from interrupt is performed, > restoring the saved registers from the newly activated local stack and > the activated task continued from where it was originally suspended. > > If a running task had no more work to do but wanted to wait for an > interrupt or message from other task, it could execute a software > interrupt, saving the registers on local stack and activate the > scheduler. > > If no tasks were runnable, execution fell through into the null task > at the end of the main program. > > With processors with more registers in which all registers weren't > saved automatically upon each interrupt, the scheduler had to check if > a task switch to a new task needs to be performed, the additional > registers were pushed to the old stack and from the new stack > additional registers were loaded before returning from interrupt. If > no task switching was required, no additional register saves/restores > were needed, just the hardware save/restore was automatically > executed.
A kernel can be even simpler! It all depends on how much you expect of it. Imagine an array of addresses and a pointer to an address in that array. Each address points INTO a task. (i.e., initially, the addresses each reference the first instruction of each task). The scheduler selects one of these array elements (tasks!) for execution based on some criteria (perhaps strictly sequential, perhaps some priority scheme or SET of priorities, etc.). The last line of the scheduler effectively jumps THROUGH the address stored in the array. As the stored address represents the address of a statement in that particular task, this effectively starts (or resumes!) the task at that instruction. When the task yields (easier case to describe than preemption), the current PC replaces the address in that array. The next task to execute is selected (i.e., the pointer into the array advances to the next array element, in the case of a simple sequential "big loop" scheduler) and the process repeats, as above. It's relatively easy to get the contents of the program counter that needs to be saved -- just look at the return address for the call to the YIELD routine (it's sitting right there on the stack!) This, of course, assumes you don't need to preserve any other state as you transition from one task to another (remember, yield() happens between statements!). And, that the stack penetration remains consistent every time yield() is invoked! (cuz you can't rejigger the stack back to the penetration level it had been at for the other tasks!) Imagine how you'd implement multitasking in a *tiny* PIC! [This last restriction proves to be of little consequence when designing for small processors -- that often can't AFFORD a stack per process and would be content to share the same stack for ALL processes!]
> Thus, a RT kernel can be really simple.
The semantic issue becomes one of deciding whether or not the implementation really provides RT services and guarantees. I tend to call these crude, tiny kernels MTOSs instead of RTOSs as many of the algorithms chosen are, by necessity, sloppy and inelegant (no real timeliness guarantees) owing to the lack of resources to "do it better". But, even with crude tools, you can implement many desireable features. E.g., timers can simply be "software counters" that are advanced with the passage of time -- as noted by the "timer handler" which is driven by a TIMER_EVENT (or, polling a timer_flag that is the sole item communicated between a timer ISR and it!). When a timer reaches a particular value (typically zero with timers counting down), it "sticks". A task wanting to wait for the expiration of a timer can simply examine the contents of THAT specific timer and, if non-zero, continue waiting. Else, advance to the statement after the Wait(). [If you use delta timers then the effort required of the timer handler becomes constant as only the most-ready-to-expire timer is ever manipulated.] As I said to Les, it's really interesting to see how MUCH you can do with how LITTLE! You're likely not going to explore the possibilities until you're tasked with designing in such an environment. (we tend to get spoiled by an overabundance of resources, nowadays!)
On Sun, 5 Jan 2020 21:26:13 -0600, Les Cargill
<lcargill99@comcast.com> wrote:

>Don Y wrote: >> 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.&nbsp; In a system >> with a time-driven scheduler, then the possibility of the processor >> being rescheduled at any time exists -- whenever the jiffy dictates. > >That seems to me to be incorrect. "Preemptive" means "the scheduler runs >on the timer tick." I'd say "inherently".
Not exactly. "Preemptive" really means only that the task is not (entirely) in control of when a context switch can occur. Preemption does not have to be based on time, and Don suggested a scenario where it is based on changes to the run queue. Since only the OS (via interrupt, I/O completion, etc.) or the running program can do something that changes the run queue, the program does, in effect, exert *some* control over when a context switch occurs. If no event happens that causes a change to the run queue - or events that do happen leave the same task in control - that task could run indefinitely, just as if it were highest priority in a time based system. YMMV, George
Clifford Heath wrote:
> On 6/1/20 2:00 pm, Les Cargill wrote: >> Clifford Heath wrote: >>> On 6/1/20 6:39 am, Les Cargill wrote: >>>> Clifford Heath wrote: >>>>> 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. >> We can larf, but I think there's less to serialization than is made of >> it. >
Well said, Clifford, by the way.
> Serialization using one giant lock isn't too hard - that's how people > write code using interrupts. But it's a very simplified case, and the > problem is to use such simple locking to construct correct algorithms at > a higher level. >
I really feel it's just a matter of people stretching metaphors beyond the breaking point. Most of the example cases I have seen to illustrate these pathologies are rather contrived. Most of these are due to ... reversing dependencies within a logic structure, not abuse of constructs. And yes, I have trouble reading that sentence too. I also don't want to appear to be too blase about things like cache lines, memory fences and all that. I just mean basic semaphores.
> Many apparently straightforward algorithms have dire pathologies when > the atomic operations can get interspersed at will.
Because it can't very well be "at will". Aren't semaphores like the escapement mechanism in a regulator clock more than anything else? They say "Not now."
> In many cases the > bugs will not ever show up during testing. And *that* is the real > problem. Such code must be *correct by construction*, but people > generally don't work that way. >
I will not disagree; it doesn't mean I have to like that state of affairs. To an extent the very word "correct" seems to inspire helplessness.
> Clifford Heath.
-- Les Cargill
Don Y wrote:
> Hi Les, >
Hey Don. :)
> On 1/5/2020 8:26 PM, Les Cargill 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.&#2013266080; In a system >>> with a time-driven scheduler, then the possibility of the processor >>> being rescheduled at any time exists -- whenever the jiffy dictates. >> >> That seems to me to be incorrect. "Preemptive" means "the scheduler >> runs on the timer tick." I'd say "inherently". > > Then, by your definition, any system without a scheduler tied to > the jiffy is "cooperative"?&#2013266080; And, any system without a jiffy (at > all!) would also have to be considered cooperative? >
There may be a jiffy because we always need a global free-running timer from which other timers can be derived.
> How do you further refine systems wherein OS calls run the > scheduler if the run queue has been altered as opposed to > those that only run the scheduler when "yield()" is invoked? > > Do you expect the current task to EVER lose control of the > processor in the following code fragment (in a cooperative > system)? > > &#2013266080;&#2013266080;&#2013266080;&#2013266080; process(...); > &#2013266080;&#2013266080;&#2013266080;&#2013266080; raise_event(...); > &#2013266080;&#2013266080;&#2013266080;&#2013266080; send_message(...);&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; // consider case of message queue "full"! > &#2013266080;&#2013266080;&#2013266080;&#2013266080; receive_message(...);&#2013266080;&#2013266080; // consider case of no message is pending! >
Absolutely.
> If I disable the timer interrupt (e.g., assume timer fails!) > in a preemptive system, do you expect the processor to ever > transfer control to any other task (same code fragment)? >
Yep. There are a lot of options, but I'd expect each case there to potentially reshuffle the queue. "Cooperative" just means the thread must explicitly yield at some point. That means you have to know which entry points in the O/S call stack can yield and when.
>>> However, you can also design preemptive frameworks where the scheduler >>> is NOT tied to the jiffy.&#2013266080; In those cases, preemption can only occur >>> when "something" that changes the state of the run queue transpires. >> >> I agree in that I think we have to hold the run queue discipline >> separate from whether the jiffy tick runs the run queue. But in my mind >> at least, your "something" is inherently cooperative - a thread has >> blocked - unless that "something" is the timer tick. > > The "something" is not "yield()".&#2013266080; Should the developer be surprised by > the fact that the scheduler ran (in a cooperative system)? >
Never. Perhaps it's incorrect, but by long habit, I have always assumed this in my own work.
> If the developer tries to transmit a character via a UART and the > UART Tx register is presently full, should he expect his task to > lock up the processor while waiting for the UART ISR to (eventually) > make the Tx register "ready"?&#2013266080; (in a cooperative system?&#2013266080; in a > preemptive system with the timer IRQ disabled?) > > [What does the putchar() code look like in each of these cases? > Do you *spin* waiting on the UART? ] >
That is about context. There are three expected outcomes ( all IMO ): - Increment a "oops, dropped send to UART" counter. - "spinlock" and wait - Go around and try again later.
> A more natural expectation (re: preemption) is that calling on the > "system" should be fair game for the system to preempt the current > task whenever the situation changes enough to alter the choice of > "most runnable" task. >
Yep!
> A more natural expectation (re: cooperative) is that the absence > of an explicit "yield()" means the task retains control of the > processor. >
By what nature? :) I think that's mildly naive more than natural.
>> At this point, I should probably say that my opinion on this is >> probably derived from the Peterson-Silberchatz book. >> >>> 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.&#2013266080; E.g., raising an event, sending a message, >>> changing the priority of some task, etc.&#2013266080; 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. >>> >>> &#2013266080;&#2013266080;&#2013266080;&#2013266080; process();&#2013266080;&#2013266080; // something that takes a REALLY LONG time >>> &#2013266080;&#2013266080;&#2013266080;&#2013266080; raise_event(PROCESSING_DONE); >> >> So how is "raise_event" not blocking? Er, rather, what value would >> that serve? It's nominally the same as a relinquish() operation on a >> semaphore. I see this as three cases: > > In a cooperative environment (using my above definition), I > could raise dozens of events, sequentially, without fear of > any of them being acted upon /until I explicitly yield()-ed/. > I wouldn't worry about adding some sort of mechanism to > treat the series of raise()'s as an atomic operation -- because > my postponing of the yield() effectively guarantees this atomicity. > > Effectively, this becomes: > &#2013266080;&#2013266080;&#2013266080;&#2013266080; priority = get_priority(); > &#2013266080;&#2013266080;&#2013266080;&#2013266080; set_priority(MAX+1); > &#2013266080;&#2013266080;&#2013266080;&#2013266080; raise_event(...); > &#2013266080;&#2013266080;&#2013266080;&#2013266080; ... > &#2013266080;&#2013266080;&#2013266080;&#2013266080; raise_event(...); > &#2013266080;&#2013266080;&#2013266080;&#2013266080; set_priority(priority); > (i.e., running the scheduler in each raise() will still not > steal the processor away from the current task) >
First, any mucking around with priority at all is at best risky. Second, I still don't see what value is preserved by doing this. Just yield and go on.
>> - current task priority < another ready task - then the intention >> &#2013266080;&#2013266080; of priority is thwarted. >> >> - priorities are equal. Meh - flip a coin, possibly biased away from >> &#2013266080;&#2013266080; the current task. >> >> - Greater than - well, we're not gonna switch, are we? >> >> So I think this all sums to "it's blocking." >> >>> In the above, process() can proceed undisturbed (subject to the >>> ISR caveat mentioned above), monopolizing the processor for as long >>> as it takes.&#2013266080; 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.&#2013266080; To the task >>> that had done this process()ing, the raise_event() call will just >>> seem to take a longer time than usual! >> >> Right; so it's "fractionally" blocking. Like dude, that's >> totally cooperative multitasking :) The running thread did something to >> run the ready queue. > > I'd wager that most folks using cooperative multitasking DON'T expect > a task switch to occur at any time other than yield().&#2013266080; And, have > probably not coded to guard against these possibilities. >
I suspect we've all seen purely round-robin systems, which conform to that expectation. That basically means "no priority". But you have to yield some time. You are around the campfire, you Get the Stick, you can talk, you yield the stick.
>> Historically, this all goes back to the transition from "batch" to >> "multiuser" in the Dark Ages - it was necessary to synthesize an event >> to&#2013266080; switch. A time was as good as anything. >> >>> It's easy to see how a time-driven mechanism is added to such >>> a system:&#2013266080; you just treat the jiffy as a significant event >>> and let the scheduler reevaluate the run queue when it is >>> signaled.&#2013266080; I.e., every task in the run queue is effectively >>> waiting on the JIFFY_OCCURRED event. >> >> Yep. However, I'm&#2013266080; not prepared to call the absence of the jiffy >> event&#2013266080; preemptive. > > Yes you'll agree that the scheduler can run at times OTHER > than the jiffy?&#2013266080; And, the user shouldn't be surprised that his > task has lost control of the processor between two lines of code, > neither of which was a "yield()"? > >> In truth, it's kinda like a middle place between "cooperative big loop >> stuff" and a fully preemptive situation. > > Another misnomer is "big loop == cooperative". >
Indeed.
> The "big loop" serves the function of (crude, naive, simplistic) > scheduler.&#2013266080; It's presence is not required for a cooperative system. > E.g., yield() could call a function that saves the current PC/state > on the current stack, examines a list of TCBs on the run queue, > selects the most runnable, restores the stack from that TCB, > restores the state for that task and "returns" to the PC resident > on that stack. > > No timer.&#2013266080; No loop.&#2013266080; 100% cooperative. > > The earliest designs I worked on saved NO task state (besides PC), > supported different "task priorities" and didn't require any > special mechanisms to ensure the statements in a task() were > processed sequentially.&#2013266080; So: > > &#2013266080;&#2013266080;&#2013266080; while(FOREVER) { > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; task1(); > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; task2(); > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; task3(); > &#2013266080;&#2013266080;&#2013266080; } > > &#2013266080;&#2013266080;&#2013266080; task1() { > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; foo = 0; > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; yield(); > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; foo++; > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; yield(); > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; foo++; > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; yield(); > > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; if (2 != foo) { > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; panic(); > > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; <blah> > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; } > &#2013266080;&#2013266080;&#2013266080;&#2013266080; } > > would behave as you'd expect (i.e., no panic).&#2013266080; You can do this > on all sorts of super-tiny processors that don't seem like they'd > lend themselves to multitasking, otherwise. >
Exactly.
>>> (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. >> >> I really think of the goal here to chunk an operation into meaningful >> ... chunks, each of which is more or less "atomic", and yielding >> between them. > > If you look at many practical applications, you can see how > this almost naturally follows.&#2013266080; E.g., you update a FIFO > (head, tail, contents) and THEN do something that exposes > the scheduler -- instead of having to remember to lock the > scheduler out while you do SOME of the FIFO update, tinker > around with something unrelated, finish the balance of the > FIFO update and THEN unlock the scheduler. > > Paraphrasing the above: > &#2013266080;&#2013266080;&#2013266080; task1() { > &#2013266080;&#2013266080;&#2013266080; not_done: > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; if (data != available) > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; return; > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; grab_available_data(); > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; yield(); > > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; process_grabbed_data(); > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; yield(); > > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; if (data == complete) { > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; // act on the processed data > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; } else { > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; goto not_done; > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; } > > &#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080;&#2013266080; <blah> > &#2013266080;&#2013266080;&#2013266080;&#2013266080; } > > I.e., grab_available_data() likely involves talking to > a shared FIFO (the producer being some other process). > Note that there is no need for synchronization primitives > because grab_available_data() is written NOT to contain > any explicit yield()'s -- and the developer operates on the > assumption that he can do anything he wants without losing > control of the processor as long as he avoids yield()! > > Likewise, while this task moves on (during its next > activation) to process_grabbed_data(), the producer > can have been working on making more data available > (in the aforementioned FIFO). > > It's not hard to look at a "task" (job?) as consisting of > these incremental steps towards the desired solution. > The only contrivance is the presence of the "yield()" > statements; i.e., you could see how the code would > make sense "as is" with them elided... the series of > steps would likely remain the same! >
but as you say - an explicit "yield()" sort of seems hack-ey. We've all done it but it's a sign that improvement is possible.
>> I've never had that not work out for me. Goes back to things >> on DOS in state machines, headending on things like multiple >> serial ports. >> >>> This leads to more >>> readable code AND avoids the race/synchronization issues that >>> time-driven preemption brings about. >> >> Mmmmm.... I think you still have those when it comes to shared state. > > Only if you allow operations on parts of that state that SHOULD > be updated concurrently to be broken by the placement of a > yield() -- or, other system call (which could effectively bring > about a preemption, in the preemptive case). > >> That's more of something to prove out locally. I will say - I prefer to >> think in terms of "regulation", like a regulator clock releasing >> things, when I can more than "grab(); process() ; relinquish();" if I >> can. > > Isn't my above example exactly this?&#2013266080; With yield()'s interposed between > steps? >
I think so.
>>> The developer does have to >>> be aware that any OS call can result in a reschedule(), though! >> >> It's been my experience that any O/S call should be assumed >> to cause a running of the ready queue :) > > Should reading a character from a UART cause the scheduler to run? > (what if the UART doesn't have data pending?&#2013266080; Should the call cause > the system to spin -- effectively blocking ALL tasks?) >
What I am more familiar with is that the interrupt from a UART causes an ISR to run, which then changes state in a buffer and signals ( possibly thru a semaphore ) that the buffer-consumer task may now be eligible to run. I think of three primary paradigms: - The VxWorks-ish three layer ( ISR, middle and "userspace" ) - A Linux ioctl(..READ...). - fake multitasking where the ISR updates the buffer with interrupts off.
> Should posting a datagram cause the system to spin until the > network is ready to XMIT it?&#2013266080; Should the network stack be implmented > in an ISR? >
No and no.
> Where are the routines that one would consider "O/S calls" enumerated > (so I know if it's safe to call them without risk of a reschedule())? > Do all the debug() mechanisms exist within the O/S framework?&#2013266080; Or, > outside it? >
Those are open questions. It depends.
> This is why it's "safer" to assume that cooperative frees the > developer from thinking about losing the processor in all cases > other than an explicit yield(). >
Possibly. That depends on the perception of the balance between the explicit and the implicit. No, really - it's more like that.
> And, that the scheduler in the cooperative case need not be a > "super loop"; you may not be able to predict the successor task > to yours when you yield!&#2013266080; (but, you can be assured that nothing > will steal the processor away from you until you relinquish it!) > > And, why its safer for preemptive to require the developer to > behave as if any O/S call can cause preemption. >
Again, I think it's more complex than that. Because of experiences, I still think of "preemptive/cooperative" as being more like "does the jiffy ISR run the ready queue?" That's more concise to me. Whether ... nominally device drivers run the ready queue is a more nuanced decision, with a common answer being "oh yes."
> And, that the timer may or may not be tied to the scheduler. > Your system can work in the absence of a timer -- and, the > absence of "yield()"! > > Treat the domain of O/S characteristics as a multiaxis space > where each choice/implementation-option gives you another degree > of freedom.&#2013266080; It allows for a greater variety of approaches > without pidgeon-holing solutions into just a few naive stereotypes. >
Exactly.
> Exercise:&#2013266080; Try writing an application where the timer just provides > timing services but doesn't run the scheduler.&#2013266080; Or, where the timer > doesn't exist, at all!&#2013266080; The run-time dynamics of your solution will > change; but, the basic solution will likely remain the same. > > Likewise, try writing cooperative solutions where the processor can't > be stolen away *without* a yield().&#2013266080; And, solutions where ANY operation > that might affect another task's readiness could potentially result > in a reschedule.&#2013266080; And, solutions where there's no "superloop" but, > rather, some other sort of scheduler. > > Try writing with a single/shared stack.&#2013266080; Try writing with *no* saved > state. >
Yep.
> You'll be amused at how LITTLE you need to actually solve many > problems.&#2013266080; Then, start to wonder why you're "expecting so much"!&#2013266080; :>
Isn't that funny? We seem to be perfectly driven to get in our own way in so many cases. -- Les Cargill
On Mon, 6 Jan 2020 02:51:19 -0700, Don Y <blockedofcourse@foo.invalid>
wrote:

>On 1/6/2020 1:44 AM, upsidedown@downunder.com wrote: >> On Sun, 5 Jan 2020 17:08:56 -0700, Don Y <blockedofcourse@foo.invalid> >> wrote: >> >>> 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. >> >> What is a jiffy ? Is it the time between two clock interrupts as in >> Linux ? What is so special about timer interrupts vs. other interrupts >> e.g. UART interrupts ? > >A jiffy is nominally the basic unit of time in a particular system. >It need never be exposed to a developer (or user). It may (or may not!) >correspond to the period of the fastest timer interrupt used as a >timebase in a system.
Smells like a time sharing system, in which the quantum defines how much CPU time is given to each time share user before switching to next user.
>[There are certain contexts where it takes on very specific -- and >numerical -- meanings] > >There's nothing magical about the jiffy. But, it's typically >wired to an IRQ (directly or indirectly). With all the right >mechanisms in place for a preemptive system, the jiffy can just >raise an event (JIFFY_OCCURRED) and a very high priority "task" >*in* the kernel will be dispatched which will run the scheduler.
Unless you want to update a time of day time clock, what is the use of regular timer interrupts ? In some systems an I/O may arm a one shot clock interrupt waiting for the I/O or until a timeout occurs. If the I/O is completed in time, the receiver routine disables the timer request and the timer interrupt never occurs. The scheduler needs to be executed only when a "significant event" such as an interrupt or task going to wait for a significant event will occur, no need to run it for routine clock interrupts, unless a timeout has occurred.
>An event raised by a UART IRQ can be handled identically. The >task(s) that are waiting on the assertion of that event are >"immediately" run as the scheduler discovers them to be ready >(and, presumably, of sufficient "priority" to cause the currently >running task to be preempted).
In a typical RT system nearly all (and most of the time all) task are in some sort of wait state waiting for a hardware (or software) interrupt. Some time one or more tasks can become runnable due to some event and on a single processor system the one runnable task with highest priority (first in the runnable task list) is running (executing).
>E.g., you don't need a timer to have a preemptive system. >You could implement an "RS232 filter" with a pair of UARTs >each raising UARTx_READY events that cause UARTx_Task() to >be made ready -- instead of coding all of that in the ISRs >for the UARTs. Let the ISRs handle the timely actions -- like >pulling characters out of the receiver, twiddling RTS/CTS/DCD/DTR, >injecting flow control characters -- XON/XOFF -- in the Tx stream, >etc. Let the tasks handle the "filtering" activities without >burdening the ISRs. > >Repeat the analysis for a network packet being received, a >message being passed from one task/process to another, etc. > >As events can alter the state of the run queue -- by making >eligible to run those tasks that are presently BLOCKING, >awaiting specific events -- when raise_event is invoked, it is >common to run the scheduler to reexamine the run queue and make >any adjustments to the selection of "currently executing task".
Yes.
>As an "event" carries no real information (data) beyond the fact >that it *occurred*, it is typically a very lightweight mechanism. >There are typically very few of them supported by the OS -- often >defined by the number of bits in the native "word size" (this >allows a task to specify a *set* of events in which it may have >an interest -- as a bit-vector; any ONE will suffice). This >simplifies the work of deciding if ANY of the waiting task's >significant events have made it eligible to run.
In a more complicated systems each task could be waiting for a mask of events and if the system wide mask has one of the same mask (wait for logical OR) or until all (wait for logical AND) required bits are set. However, this still needs scanning the task list in priority order.
>[Note that events are transient; they aren't stored like "flags". >So, if an event happens and you're not watching for it, you never >*see* it!]
Depends on implementation.
>> Here is example how a very simple pre-emptive RT kernel worked: >> >> In the original version for a processor with only a few registers and >> when the hardware saved all registers on the stack before the >> interrupt service routine (ISR) was executed and restored after the >> return from interrupt instruction was executed. >> >> When the system was started in the main program, a subroutine call was >> executed for each task to be created. This subroutine allocated a >> local stack for the task as well as a 3 byte task control block >> consisting of 1 byte task state and 2 byte saved stack pointer. The >> task was started, which then performed a software interrupt storing >> original registers for that task on the local stack. > >This (storing present state on the task's stack) is a common approach. >It is also possible to store the register state *in* the TCB (a larger >structure being needed for that). But, these are just efficiency tradeoffs.
If you put the local stack in the TCB, you either have to use a fixed size stack for each task or use a linked list to access the next TCP. In the scheduler walking through a linked list is often less effective than selecting the next entry in an array on a small microprocessor.
>> After all task had been created in priority sequence, the main program >> entered an eternal loop (the null task) possibly containing a wait for >> interrupt instruction to reduce power consumption. >> >> The 3 byte task control blocks were in fixed priority order (as >> created) and adjacent locations in memory. >> >> When a task was running using its local stack and some kind of >> hardware interrupt occurred, the registers were saved on local stack >> by the hardware. The active stack pointer was then stored into the >> task specific saved SP in the task control block. The ISR was then > >Meaning you have to remember where the TCB (3 bytes, in your example) >is for the currently executing task.
Of course. It is updated each time there is a context switch.
>> executed using the local stack, potentially altering the runnability >> of some other dormant task. >> >> Before performing a return from interrupt the scheduler was executed. > >The problem with this is that the scheduler may end up being bulky >and take a nontrivial amount of time to make up its mind.
The RT kernel described above for 6809 was about 1-2 KB and even with a dozen tasks took 36 instructions (worst case) to find which the next task should be executing. Stack manipulation in task swathing required some additional instructions.
>Another approach is to "schedule" the scheduler to run at the COMPLETION >of the ISR. I.e., interpose the scheduler's invocation between the >"return-from-interrupt" and the actual "return to task that was interrupted".
I just tried to explain that the scheduler is executed after the ISR code but before executing the return from interrupt instruction either to the just interrupted task or to a separate task interrupted seconds or days earlier.
>> The scheduler checked the task state byte of each created task >> (requiring just 3 instructions/task). If no new higher priority task >> had become runnable, the scheduler performed a simple return from >> interrupt restoring the registers from the local stack and the >> suspended task was resumed. > >Deciding and picking can often be far more complicated actions. >And, the criteria used to make that selection are often not simple >(static?) priorities.
Why complicate things with dynamically changing priorities ? For avoiding priority inversion or improve user responsiveness ? But as I said, having separate lists is justifiable only with a large number of tasks. Try to avoid risk for priority inversion by avoiding complicated locks. Just use fixed priorities. With hundreds of tasks it would make sense to have a separate lists of runnable tasks in priority order. There is no need to check for non-runnable tasks. When a task becomes runnable, it is moved from the waiting list to runnable list. In a well behaving RT systems, there are only one or a small number of tasks in the runnable list.
>> However, if the ISR had made a higher priority task runnable, The >> scheduler would then load the stack pointer from the saved stack >> pointer from the new stack and a return from interrupt is performed, >> restoring the saved registers from the newly activated local stack and >> the activated task continued from where it was originally suspended. >> >> If a running task had no more work to do but wanted to wait for an >> interrupt or message from other task, it could execute a software >> interrupt, saving the registers on local stack and activate the >> scheduler. >> >> If no tasks were runnable, execution fell through into the null task >> at the end of the main program. >> >> With processors with more registers in which all registers weren't >> saved automatically upon each interrupt, the scheduler had to check if >> a task switch to a new task needs to be performed, the additional >> registers were pushed to the old stack and from the new stack >> additional registers were loaded before returning from interrupt. If >> no task switching was required, no additional register saves/restores >> were needed, just the hardware save/restore was automatically >> executed. > >A kernel can be even simpler! It all depends on how much you expect of it. > >Imagine an array of addresses and a pointer to an address in that array. >Each address points INTO a task. (i.e., initially, the addresses each >reference the first instruction of each task). The scheduler selects >one of these array elements (tasks!) for execution based on some criteria >(perhaps strictly sequential, perhaps some priority scheme or SET >of priorities, etc.). The last line of the scheduler effectively >jumps THROUGH the address stored in the array. As the stored address >represents the address of a statement in that particular task, >this effectively starts (or resumes!) the task at that instruction. > >When the task yields (easier case to describe than preemption), the >current PC replaces the address in that array. The next task to execute >is selected (i.e., the pointer into the array advances to the next >array element, in the case of a simple sequential "big loop" scheduler) >and the process repeats, as above. > >It's relatively easy to get the contents of the program counter that >needs to be saved -- just look at the return address for the >call to the YIELD routine (it's sitting right there on the stack!) > >This, of course, assumes you don't need to preserve any other state >as you transition from one task to another (remember, yield() happens >between statements!). And, that the stack penetration remains consistent >every time yield() is invoked! (cuz you can't rejigger the stack >back to the penetration level it had been at for the other tasks!) > >Imagine how you'd implement multitasking in a *tiny* PIC! > >[This last restriction proves to be of little consequence when >designing for small processors -- that often can't AFFORD a stack >per process and would be content to share the same stack for ALL >processes!]
I do not know about PICs but even primitive processors like 6502 with 256 byte stack pointer addressability range could support multiple stacks. With simple processors with a few registers a 32 bytes/task stack was more than enough.
>> Thus, a RT kernel can be really simple. > >The semantic issue becomes one of deciding whether or not the >implementation really provides RT services and guarantees.
What services ? The RMX-80 for 8080/8085 was quite adequate, the RMX-86 for 8086/8088 was bloatware :-). The RT kernel doesn't give any timeliness quarantees other than execution in priority order, it is up to the application programmer to make sure that the high priority tasks do not consume too much time.
Am 06.01.2020 um 01:08 schrieb Don Y:

> 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.
I think I have to disagree with that. Let's start with linguistics. To "preempt" means: to get in ahead of someone (or something) else. In the RT world, that something is a running task, and preemption happens when some other task gets to use the CPU before that task is done with it. I.e. a preemptive framework, pretty much by definition of the words, does pull the CPU out from under you, and that _will_ happen at, essentially, random times. If the running task can routinely (as opposed to exceptionally) avoid that happening to itself, that means it's essentially the other type of framework: a cooperative one. In other words: for the distinction of preemptive vs. cooperative multitasking to make any sense at all, it has to be about who routinely gets to decide whether task switching is allowed at any given time. If the decision normally is with individual tasks, that's cooperative. If it's centralized in the OS, that's preemptive. Now we in c.a.embedded don't usually get to make that distinction quite so cleanly of course, because for us, ISRs are a fact of life, and those are always preemptive. So purely cooperative multitasking is out. We only get to decide between largely cooperative systems with some preemptive task disturbing the "clean" picture, and almose purely preemptive system setups, with all the extra cost in terms of data exchange synchronization between tasks that entails.
> 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.
And still, when eventually you do lose it, the time when that happens is, for all practical intents and purposes, random. Because otherwise you wouldn't "lose" control, you'ld be "giving it up". In other words, in such a case the used RTOS framework may be preemptive, but you're not using it that way.