EmbeddedRelated.com
Forums
The 2024 Embedded Online Conference

Common name for a "Task Loop"

Started by Tim Wescott June 24, 2016
On Sat, 25 Jun 2016 14:36:58 -0700, Don Y wrote:

> On 6/25/2016 1:43 PM, Tim Wescott wrote: > >> task. In mine, it just needs to finish up whatever task it's on and >> then the highest-priority task automatically gets executed. > > And it gets *exclusive* use of the processor while it is executing! > So, anything of lower priority starves. Your scheduling algorithm is > "highest priority first".
Whoa! No S**t! Just like the well-known and successful real-time design rules say! Dayum -- a method that does what it should. What a concept.
> Few systems are this cut and dry. In practice, you want to give more > resources to "more important" tasks -- and still let other tasks > continue to run. You don't want a big loop of "try this, then try that" > but, rather, to be able to code "this" and "that" in isolation and then > tie them back together (because they all must work in a single > environment).
Well, that would be why the higher-priority tasks only run when they're _ready_.
> In a foreground-background approach, the interrupt system takes priority > over the background. And, within the interrupt system, > the interrupt having the highest priority can preempt those of lower > priorities -- allowing them to resume when it has completed. > > Extending those priorities to the background in any meaningful way > distributes the scheduling mechanisms among the tasks. > I.e., if highest_priority gets half way through and then needs to *wait* > for something else, it needs to mark itself as "not ready" > and hope that someone will mark it as ready when that something else > happens. And, that whichever executing task happens to finish up (along > with any "higher priority" tasks) so that the if-tree will transfer > control to it.
Well, yes -- did you happen to know that the sky is blue and that water is wet, or do you need to have that pointed out?
> How do you deal with two tasks of equal priority? One has to come first > in your scheme as they can't share a priority level (because one "if" > precedes the other). > > If I have to flash the display and "blink" a noise maker, do I have to > put those activities in the same task? Why can't they coexist alongside > each other at equal "priorities" so BOTH can happen without one starving > the other?
You seem to be confusing assigned priority with how important something is to the programmer. If it's a hard-real-time system and you have a fast enough processor, you can just arbitrarily assign "equal priority" tasks as being adjacent to each other in order and it'll work. If you _don't_ have a fast-enough processor then nothing will work.
> The scheme I illustrated shows everything as "the same priority" > but with differing degrees of "importance". Or, alternatively, > with differing resource requirements to achieve similar levels of > performance. > > Should servicing UART0 have priority over UART1 (note I'm not talking > about ISRs but, rather, the handlers that the ISR's feed and are fed > by). I.e., if I allow two clients to connect to a device using two > different UARTs on the device, should I give preference to traffic from > one over the other? Is one, somehow, more "important" than the other?
That depends on so many different system-wide considerations that the question is practically meaningless. If it's really a real-time system, see my answer above. If you want some sort of graceful degradation in the face of processor overload, then yes, you need to do something different.
> Where do you put the task that manages system timers? (or, do you > require each individual task to examine a hardware counter-timer and do > their own timekeeping?) > > Where does the keyboard fit into your priority scheme? If too low, then > keys get dropped. If too high, then the operator's actions can > jeopardize some other aspect of the application (maybe the UARTs drop > characters because you're busy debouncing keys?) > > And, of course, if power fails, THAT should be noticed ASAP. But, will > the power fail task have to assume responsibility for doing all the > housekeeping as the system goes down? The priorities that would apply > may be exactly the opposite of what they were when the system was > running normally (and the system doesn't even know, yet, that it will no > longer be running normally!). > > When you pick (somewhat arbitrary) priorities, you invariably end up > having to juggle them. Then, refactor because the assignment doesn't > work in all operating conditions (e.g., power fail). In practical > systems, this results in a flattening of priorities -- which means > SHARING the processor concurrently.
In PRACTICAL systems that have well-defined deadlines, then the priorities are obvious, and ignoring them leads to a system that for all PRACTICAL purposes is useless. Yes, things may be different in a power- down situation, but that's such an extreme example that it's probably best handled entirely in an NMI.
>> This still depends on the low-priority stuff being broken into bits >> short enough that they never get in the way of the high-priority stuff. >> To me, >> this situation is the big advantage of an RTOS -- if you have stuff to >> do on very dissimilar time scales, you can just write the damned slow >> stuff without having to think hard about breaking it into bite-sized >> chunks. > > But then you incur the costs of a formal scheduler -- not an ad hoc loop > of code. How will task_lowest() ever have any guarantees of meeting its > requirements? You've cast the scheduling decisions in concrete, at > compile time.
How will task_lowest() ever have any guarantees of meeting it's requirements? Oh, garsh -- maybe because some guy on the team who's called an "engineer" knows that engineering means "applied science and math", and has _justified his pay_ by applying the science of processor speed and resource requirements to the math of rate-monotonic scheduling or one of the other well-known scheduling algorithms to make sure? Where did you learn your TRADE????
>>> When I use this sort of approach, my code looks like: >>> >>> ... // do something ... // do something else ... // do still >>> more yield() >>> ... // do some other stuff ... // do some more other stuff ... >>> // >>> do still more other stuff yield() >>> ... >> >> When you have no RTOS you have a yield() function call??? How? > > All yield() has to do is save the state of the current task and advance > to the next task in the "queue". In the big loop example, > the "queue" is fixed. > > task() { > ... > ... // do something ... // do something else ... // do still more > yield() > ... // do some other stuff ... // do some more other stuff ... // > do still more other stuff yield() > ... > } > > imagine if yield() was: > save current state (whatever that may be and however you want to > save it) > discard top stack frame (i.e., the frame that invoked yield()) > ret (i.e., return FROM task() to whatever invoked it!) > > The magic you're failing to see is you can fudge the preamble to task() > (and all task's) to effectively be: > restore state (whatever it was and however it was saved) > jump thru saved PC to the location after most recent yield() > > This is what a simple scheduler would do "in one "reschedule()" > routine. But, a scheduler would have to examine a queue of "ready" > tasks to select the next to execute. Here, the loop has made it clear > which will be the next task to execute. > > Which will *always* be the next to execute! > > [In an ASM environment, yield can be a couple of opcodes!]
So, you don't want to implement the useful part of a scheduler, but you do want to implement the esoteric and prone-to-bugs part. Well, it's different, I suppose. I can only assume from how you think the world should work that you simply do not work on products that need to have tasks of markedly different time-scales working at the same time. Because your approach would crash and burn immediately on most of the stuff that I work on. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
On Sat, 25 Jun 2016 14:45:36 -0700, Don Y wrote:

> On 6/25/2016 1:50 PM, Tim Wescott wrote: >> On Sat, 25 Jun 2016 08:27:54 -0700, Don Y wrote: >> >>> On 6/25/2016 4:00 AM, upsidedown@downunder.com wrote: >>>> On Sat, 25 Jun 2016 01:07:41 -0700, Don Y >>>> <blockedofcourse@foo.invalid> >>>> wrote: >>>> >>>>> On 6/25/2016 12:52 AM, upsidedown@downunder.com wrote: >>>>>> On Fri, 24 Jun 2016 17:03:07 -0700, Don Y >>>>>> <blockedofcourse@foo.invalid> wrote: >>>>>> >>>>>>> On 6/24/2016 4:31 PM, Tim Wescott wrote: >>>>>>>> I don't think your "prioritization" scheme really works, though >>>>>>>> -- if a high-priority task happens to miss it's cue right before >>>>>>>> the loop iterates then all the low- and mid-priority tasks get >>>>>>>> executed before the high-priority stuff. >>>>>>> >>>>>>> Priority is a misnomer. It's a "relatively short word" that >>>>>>> suggests "larger quantum". The "low_latency" task (list) tries to >>>>>>> address those tasks that need to "wake up more often". >>>>>> >>>>>> What does quantum has to do with priority in a real time >>>>>> environment ? >>>>> >>>>> Who mentioned "real-time"? >>>>> "... I'm _not_ using an RTOS..." >>>> >>>> You started by priorities, which usually implies some (soft) real >>>> time functionality. >>> >>> "I've used (*really* slim!) multitasking executives that used >>> the >>> ----------------------------------^^^^^^^^^^^^^^^^^^^^^^^ >>> loop as a general framework for "scheduling" tasks -- but >>> allowed voluntary rescheduling directives to be invoked by the >>> individual "function calls" invoked from that loop: >>> >>> Multitasking does not imply Real-Time. Likewise, Real-Time does not >>> imply Multitasking. >>> >>> "Priorities" just says some things are more important than others >>> (acknowledging the fact that there are only so many resources >>> available in a given implementation). Or, are you deciding that a >>> "time sharing" >>> system is a "real-time" system? >>> >>> (UN*X has "priorities" in its scheduler; is *it* "real-time"?) >>> >>>> A real time application doesn't necessary need an RTOS. A task loop >>>> like >>> >>> And, a real-time application need not consist of more than one task! >>> I.e., real-time does not imply multitasking. MTOS != RTOS. >>> >>>> A task loop and an RTOS are not really that much different. The task >>>> loop and non-preemptive RTOS can store the context in local static >>>> variables, while the pre-emptive RTOS stores the context into a >>>> process specific stacks. >>> >>> A task loop and an *MTOS* are functionally equivalent. An RTOS is a >>> different beast, entirely. >> >> I think you are confused in your terminology. A real-time operating >> system is a handy way to implement multitasking in a way that can meet >> real-time constraints. So while not all multitasking operating systems >> are real-time, all real-time operating systems are multitasking. > > No. A real-time operating system does not imply multitasking. > And, multitasking does not imply real-time. > > I can make a single-threaded application that draws on services offered > by an RTOS to achieve particular timeliness goals. > > I can make a multithreaded application that draws on services offered by > an MTOS to achieve the illusion of parallelism. > >> And, a task loop can be made real-time reasonably easily, as long as >> you're willing to live with writing every bit of code to the >> requirements of the shortest real-time deadline. > > Then it's not an RTOS (or an MTOS), is it? If it's an *OS*, please > identify the services that it is providing for you? > > Welcome to the days of "program loaders" (predating OS's)
OK. I'm done talking to Don Y. For _anyone else_ -- just find some reputable source and double-check what this guy is saying before you believe it. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
On Friday, June 24, 2016 at 12:37:16 PM UTC-6, Tim Wescott wrote:
> ... So -- is there a common Google-able term for this?
Kludge? OK, OK, I've done it too...
On 6/25/2016 3:25 PM, Tim Wescott wrote:
> I can only assume from how you think the world should work that you > simply do not work on products that need to have tasks of markedly > different time-scales working at the same time. Because your approach > would crash and burn immediately on most of the stuff that I work on.
You seem to have selective amnesia. Here's what I said when introducing my version of the "big loop": "I've used (*really* slim!) multitasking executives that used the loop as a general framework for 'scheduling' tasks -- but allowed voluntary rescheduling directives to be invoked by the individual 'function calls' invoked from that loop: " Yet, from that, you CONCLUDE that I "simply do not work on products that need to have tasks of markedly different time-scales working at the same time." I guess I fail to see the logic in that conclusion. And, the fact that *this* approach "would crash and burn immediately on most of the stuff that I work on" is equally useless to draw conclusions of the types of projects that *I* have applied it to. Here's the "Job list" (main loop) from a product I designed with this approach ~35 years ago: Jobs: Debugger // interactive debugger, when present Timekeeping // Timer service PowerMonitor // AC, battery backup and line frequency clock Display // Display and Indicator update Keypad // keypad scanning Barcode // Barcode decoding Sensor // sensor array scanning Operator // Console operator user interface FSM Diagnostic // Diagnostic Mode user interface FSM Supervisor // Supervisor Mode user interface FSM Port0 // Port0 comm channel user dialog Port1 // Port1 comm channel user dialog ret // done The Debugger task lets a developer plug a proprietary piece of hardware into the running (production!) system to examine and control the system at all levels (i.e., live patches to memory, stepping individual tasks, altering register contents). Most of the time, it's just refreshing the display on *that* device and polling for keystrokes. When it encounters one, it implements the command associated with it altering the device's operation in "real time". After deployment, it's dead code (and can be elided) Timekeeping updates the system timers made available to any task that needs them. So, no need to watch a hardware counter/timer to determine elapsed time, delays, etc. "Wait 3 seconds" and your code will block for 3 seconds, "Test KeystrokeTimeout" and your code will check to see if the "KeystrokeTimeout" has expired. PowerMonitor monitors the AC "line frequency clock" (essentially the 50/60Hz mains) so the unit can adjust sampling intervals and display refresh to frequency lock to the mains voltage. It also provides an indication of absence of primary power. And, whether that is due to the user manually flipping the power switch "off" *or* a power outage. The device can then either shutdown as "intended" or alert the user (via the "Operator" interface task) that he's now working on borrowed time -- perhaps wise to unload the database stored in system RAM, now. And, eventually, bring about an orderly shutdown when the battery actually is ready to fail. Or, alerting the user when power returns! At the same time, it informs the timekeeping software that the "stable" AC mains line frequency reference is no longer available and the most recent "crystal calibration" must be used to create synthetic time. So, the timescales are 50/60hz as well as the fractional hour the device can run on battery. The Display task ensures the display is updated synchronous with the AC mains (so you don't see a beating in the display) as well as ensuring the "content update" is synchronized with the "scan line refresh" to eliminate visual artifacts. It implements features like "blink" (in-phase and out-of-phase), "reverse", etc. so you can say: DisplayCenteredMessage: // copy pointer to message into "message" Send to Video // select device and wait to obtain lock SetAttributes(NORMAL+REPLACEMENT+FORWARD+SHOWIT+SOLID+INPHASE) CarriageReturn // leftmost column in line 0 Call(SkipOverLeadIn) // skip leading whitepace SetAttributes(NORMAL+REPLACEMENT+BACKWARD+SHOWIT+SOLID+INPHASE) ClearToEol // clear all LEADING whitespace! // display cursor now at LEFTMOST column Call(SkipOverLeadIn) // skip leading whitepace SetAttributes(NORMAL+REPLACEMENT+FORWARD+SHOWIT+SOLID+INPHASE) CarriageReturn // leftmost column in line 0 Print(message) // show error message ClearToEol // clear all TRAILING whitespace! Done // release the lock on the device SystemError: EnableAttribute(FLASH) "System Error" DisableAttribute(FLASH) " Detected!" End Initializing: "Initializing..." End FailedToInit: "Unable to Initialize" End SensorShorted: "Sensor Shorted" End The audio annunciator (handled as part of the Display "job") emits tones. So, you can say: Send To Audio // select device and wait to acquire lock Print(DropOfBlood) // "play" the annunciator Quit // end of output -- but retain lock on device ... // do other stuff while annunciator is playing Send To Audio // select device, already have the lock! Flush // block until output queue is empty Done // release the lock on the device DropOfBlood: Rate 150*60 Beats per Minute // underlying timebase Flush // ensure any previously queued are done Gather // queue data, don't play, yet // default glissando so it sounds "fluid"! Play C_Natural(4) for 3 Beats Play D_Natural(4) for 2 Beats Play E_Natural(4) for 1 Beats Play F_Natural(4) for 1 Beats Play G_Natural(4) for 1 Beats Play A_Natural(4) for 1 Beats Play B_Natural(4) for 1 Beats Play C_Natural(5) for 1 Beats Play D_Natural(5) for 1 Beats Play E_Natural(5) for 1 Beats Play F_Natural(5) for 1 Beats Play G_Natural(5) for 1 Beats Play A_Natural(5) for 1 Beats Play B_Natural(5) for 1 Beats Release // release queued data for playing End So, the timescales there are 1/150ths of seconds. The Keypad task scans the key matrix and debounces keys providing rollover etc. It feeds "events" to the Operator FSM in much the same way that the AC line monitor fed POWER_FAIL, POWER_OFF, POWER_RESTORE and BATTERY_FAIL events. The Barcode task continually monitors for the user's presentation of a barcoded label to the device. The user protocol doesn't require the operator to inform the device of his desire to do so; that would be an inefficient use of the operator's time! Instead, the operator can swipe a barcode at ANY time. The barcode hardware consists of a photodetector feeding an edge triggered interrupt pin, through an XOR. The other input of the XOR allows the ISR to indicate that it is looking for the black-to-white edge (of a bar) or the white-to-black edge (of a space) as the times between them are the "data". The ISR simply stores the contents of a freerunning counter along with another value (from the same counter) that effectively tells how long *ago* the edge occurred. I.e., the barcode *handler* will be able to adjust the observed counter value to reflect this interrupt latency to yield the *actual* time between successive "edges". At 100 ips, a minimal bar/space of 0.007" can pass the detector (i.e., time between edges) in 70 microseconds. Even smaller if you allow for ink spread (which causes space shrinking). You'll see an entire set of ~100 transitions in a bit less than a second -- an "entire code". I.e., the ISR is *really* fast cuz it has to catch each edge and reprogram the XOR for the NEXT edge. All this on a 1980-vintage machine processing 1.5M 8b opcodes per second. The Barcode task implements the "handler" -- that retrieves the raw data from the circular buffer managed by the ISR as it arrives (and taking note if it is ever too sluggish revisiting the buffer before it overflows!), does the latency compensation and then begins the analysis of the actual bar/space widths to create a code -- which it then verifies as legitimate or not. If the ratios of bar/space widths don't fit a defined pattern, the "oldest" bar and accompanying space are discarded and the process repeats -- until a set of bar/space widths consistent with a "legitimate character encoding" are discovered. Then, the bars and spaces that follow are analyzed to (hopefully) arrive at another "valid character". Once *a* character is available, we hesitate to discard anything until we know if that character -- and any that might follow -- are representative of a valid label (which might be "followed" by crud). ;Validity ::= Valid_ID | Alpha_ID | Null_ID ; ;Valid_ID ::= NumericID ;Alpha_ID ::= AlphaID ;Null_ID ::= NullID Wildcard NumericID for Validity is keyed with Valid_ID Wildcard AlphaID for Validity is keyed with Alpha_ID Wildcard NullID for Validity is keyed with Null_ID ;IDVals ::= NumericID | AlphaID | NullID ; ;NumericID ::= PADDING DIGIT DIGITS ;AlphaID ::= PADDING ALPHAPART NUMERICPART ;NullID ::= PADDING Grammar for NumericID is <<PADDING,DIGIT,DIGITS>> Grammar for AlphaID is <<PADDING,ALPHAPART,NUMERICPART>> Grammar for NullID is <<PADDING>> Wildcard PADDING for IDVals is keyed with 'p' Wildcard DIGIT for IDVals is keyed with '#' Wildcard DIGIT? for IDVals is keyed with 'e' Wildcard DIGITS for IDVals is keyed with 'd' Wildcard ALPHAPART for IDVals is keyed with 'a' Wildcard NUMERICPART for IDVals is keyed with 'n' ;PADDING ::= ASCNUL PADDING | '' ;DIGITS ::= DIGIT DIGITS | '' ;DIGIT? ::= DIGIT | '' etc. I.e., a grammar for what constitutes a "valid" label in terms of "recognized characters" -- so the handler can reject any PROCESSED data that might LOOK like (and may even *be*!) a set of legal characters but that doesn't ACTUALLY satisfy the criteria for a label. Once *a* code/label has been read, it has to note if another VALID label is encountered within a "half inch" of the end of the previous label (of course, it can't measure distances, only *times* -- what's a half inch at the scan rate that is apparent from the bar/space times in the data already recognized?). If the start code of the next label is compatible with the end code of the previous, seamlessly glue these labels together AS IF they had been a single, continuous label. Up to three labels can be concatenated like this *in* the Barcode handler so the rest of the system is unaware of this capability (the adjoining start and end codes are elided when the label's contents are reported to the application) When valid, it signals a BARCODE_AVAILABLE event to the Operator FSM task. Which can then interpret the event as applicable to the current user context (is a barcode valid at this stage in the protocol? is *this* barcode valid, here?) So, times from 70 microseconds through a second or more to ensure the label has completely passed the scanner (can't control how fast the user moves his arm!) The Sensor task scans an array of 60 RC oscillators at a rate that is frequency locked to the AC mains with the same sort of interrupt latency compensation that was applied to the barcode detector. In addition to noting the current frequency of each oscillator, it also has to detect an "open" cap (the caps are formed from large, widely spaced plates that allow changes in frequency to be used to detect the presence of 10 microliter blood samples placed between any pair; if a plate breaks off, that detector is obviously unreliable), a shorted cap (if the user bridges the gap between the plates with something of "relatively" low impedance the sensor is unreliable) or a disconnected sensor assembly. These data are signaled to the Operator FSM as well so the FSM knows what the operator has done in his "interaction" with the sensor array. So, you're sampling at some multiple of AC mains clock periods (the sampling interval changes based on what the Operator FSM is expecting from the sensor; faster intervals for reduced resolution, etc. A user typically pipettes samples (or reagents!) at a few second interval -- sort of like tapping on a keyboard. The Operator FSM task is a giant state machine that processes events and conditions sourced from other tasks. It steers the user interaction accordingly. Events can be sourced at varying timescales: as often as a user presses a key or scans a barcode, as often as he pipettes blood samples into the array, as often as the power fails/recovers, etc. It runs forever (as do all of these other jobs) The Diagnostic and Supervisor FSM's are other operating modes for the device. Typically, only one of these three modes are engaged at a time. Splitting them into three FSM's allows them to operate concurrently as well as reducing the complexity of the "user interface" FSM. Port0 and Port1 are handlers that service the two UARTs. Each talks to a respective UART ISR to retrieve incoming data and status (from software FIFO's with overflow protection -- this predates UARTs with big internal buffers). They also implement the hardware handshaking and character "pacing" (so the ISR's can remain lean -- just read the data and status registers... don't bother with the handshaking in the foreground!). As such, they deal with "character times" -- too sluggish and the remote device can be overrun *or* overrun the local device. Additionally, they feed two instances of the same state machine that implements the interface language specification by which external devices can query and control the device and the data that it maintains. The system is resilient enough that you can take a barcode label and rub it vigorously back and forth over the detector -- keeping in mind that each black/white transition triggers an interrupt -- and not crash the device *or* corrupt its execution. And, when you get tired of waving the barcode labels in front of the detector, the system will respond with the *correctly* decoded barcode -- despite the overload that it experienced. Of course, it *has* to be -- else you'll report the wrong diagnosis for some patient! What "priorities" would you like me to assign to these tasks? Maybe force the user to press a "Read A Barcode" key so the barcode task can be made ready? Then, once it has seen a barcode (or, perhaps, timed out?), it can make itself NOT ready until manually called upon, again? Maybe the Port0 servicing should only run when the user isn't busy interacting with the device? And, Port1 should wait until Port0 is no longer active? Maybe ignore the power subsystem while the user is in the middle of a sampling cycle and only worry about power availability BETWEEN those cycles? (e.g., POLL it?). Unless, of course, he takes too long and we have to abort his action lest we starve the power monitor task. And, we can just use a higher quality crystal oscillator instead of calibrating it against the (reliable) AC mains. And, only check the line frequency each time we power up (hey, if it's 50Hz, it's gonna stay 50Hz, right?). If the line frequency drifts, we can always live with a low frequency "beat" in the display. And, errors in the sensor array, right? As I said elsewhere, everything ends up running at essentially the same "priority" -- because everything CAN happen at the same time! Those activities that have truly tight timeliness constraints move into the foreground. And, ONLY do what they absolutely *must* while there. E.g., the barcode ISR doesn't waste foreground time computing the "time since the previous edge"; the UART ISR's don't waste time twiddling with handshaking/pacing features; etc. And, the *background* routines aren't piggish, either! They do enough to have justify their invocation "this time around the loop" but not too much that they delay the other tasks (who are ALL "ready"). So, the barcode handler quickly tries to empty any "edge times" from the barcode ISR's FIFO -- and converting them to widths. This allows 4 bytes of FIFO data to be reduced to a two byte "width" -- in the *handler's* "width FIFO". So, the ISR FIFO can stay small and still accommodate the amount of activity likely to be encountered BEFORE THE HANDLER COMES AROUND, AGAIN, to empty it. Likewise, the higher layers in the barcode handler try to aggressively discard "widths" that are incompatible with "valid character codes". Again, trying to keep as much space available in the *width* FIFO so there is always room for the raw "edge" data from the ISR FIFO. And, even higher layers try to invalidate individual characters as being incompatible with a valid *label* format -- again, so some widths can be removed from the width FIFO. And, ultimately, concatenated labels that fail to satisfy the criteria for a "glued together" label can be discarded. Always keeping the door open to harvest as much data from the ISR as possible. Because a FIFO overrun (anywhere) wedges the label in question. And, that means the user has to rescan the label (this is not a Good Thing).
On 6/25/2016 3:28 PM, Tim Wescott wrote:
> On Sat, 25 Jun 2016 14:45:36 -0700, Don Y wrote: > >> On 6/25/2016 1:50 PM, Tim Wescott wrote: >>> On Sat, 25 Jun 2016 08:27:54 -0700, Don Y wrote: >>> >>>> On 6/25/2016 4:00 AM, upsidedown@downunder.com wrote: >>>>> On Sat, 25 Jun 2016 01:07:41 -0700, Don Y >>>>> <blockedofcourse@foo.invalid> >>>>> wrote: >>>>> >>>>>> On 6/25/2016 12:52 AM, upsidedown@downunder.com wrote: >>>>>>> On Fri, 24 Jun 2016 17:03:07 -0700, Don Y >>>>>>> <blockedofcourse@foo.invalid> wrote: >>>>>>> >>>>>>>> On 6/24/2016 4:31 PM, Tim Wescott wrote: >>>>>>>>> I don't think your "prioritization" scheme really works, though >>>>>>>>> -- if a high-priority task happens to miss it's cue right before >>>>>>>>> the loop iterates then all the low- and mid-priority tasks get >>>>>>>>> executed before the high-priority stuff. >>>>>>>> >>>>>>>> Priority is a misnomer. It's a "relatively short word" that >>>>>>>> suggests "larger quantum". The "low_latency" task (list) tries to >>>>>>>> address those tasks that need to "wake up more often". >>>>>>> >>>>>>> What does quantum has to do with priority in a real time >>>>>>> environment ? >>>>>> >>>>>> Who mentioned "real-time"? >>>>>> "... I'm _not_ using an RTOS..." >>>>> >>>>> You started by priorities, which usually implies some (soft) real >>>>> time functionality. >>>> >>>> "I've used (*really* slim!) multitasking executives that used >>>> the >>>> ----------------------------------^^^^^^^^^^^^^^^^^^^^^^^ >>>> loop as a general framework for "scheduling" tasks -- but >>>> allowed voluntary rescheduling directives to be invoked by the >>>> individual "function calls" invoked from that loop: >>>> >>>> Multitasking does not imply Real-Time. Likewise, Real-Time does not >>>> imply Multitasking. >>>> >>>> "Priorities" just says some things are more important than others >>>> (acknowledging the fact that there are only so many resources >>>> available in a given implementation). Or, are you deciding that a >>>> "time sharing" >>>> system is a "real-time" system? >>>> >>>> (UN*X has "priorities" in its scheduler; is *it* "real-time"?) >>>> >>>>> A real time application doesn't necessary need an RTOS. A task loop >>>>> like >>>> >>>> And, a real-time application need not consist of more than one task! >>>> I.e., real-time does not imply multitasking. MTOS != RTOS. >>>> >>>>> A task loop and an RTOS are not really that much different. The task >>>>> loop and non-preemptive RTOS can store the context in local static >>>>> variables, while the pre-emptive RTOS stores the context into a >>>>> process specific stacks. >>>> >>>> A task loop and an *MTOS* are functionally equivalent. An RTOS is a >>>> different beast, entirely. >>> >>> I think you are confused in your terminology. A real-time operating >>> system is a handy way to implement multitasking in a way that can meet >>> real-time constraints. So while not all multitasking operating systems >>> are real-time, all real-time operating systems are multitasking. >> >> No. A real-time operating system does not imply multitasking. >> And, multitasking does not imply real-time. >> >> I can make a single-threaded application that draws on services offered >> by an RTOS to achieve particular timeliness goals. >> >> I can make a multithreaded application that draws on services offered by >> an MTOS to achieve the illusion of parallelism. >> >>> And, a task loop can be made real-time reasonably easily, as long as >>> you're willing to live with writing every bit of code to the >>> requirements of the shortest real-time deadline. >> >> Then it's not an RTOS (or an MTOS), is it? If it's an *OS*, please >> identify the services that it is providing for you? >> >> Welcome to the days of "program loaders" (predating OS's) > > OK. I'm done talking to Don Y.
Great. Remain ignorant.
> For _anyone else_ -- just find some reputable source and double-check > what this guy is saying before you believe it.
Yes, ask Tim for references to where he gets *his* ideas, as well! Well, let's see what the "experts" have said (the following excerpts from my "first session" teaching plan, I've just cut and pasted from my notes so apologies for typos): <https://en.wikipedia.org/wiki/Real-time_operating_system> "A real-time operating system (RTOS) is an operating system (OS) intended to serve real-time application process data as it comes in, typically without buffering delays. Processing time requirements (including any OS delay) are measured in tenths of seconds or shorter." Ah, so that deep space probe's deadline regarding when it needs to initiate that course correction near Jupiter isn't real-time -- it's had MONTHS to think about it and prepare the hardware for that critical burn... <https://en.wikipedia.org/wiki/Real-time_computing#Criteria_for_real-time_computing> "In the context of multitasking systems the scheduling policy is normally priority driven (pre-emptive schedulers). Other scheduling algorithms include earliest deadline first, which, ignoring the overhead of context switching, is sufficient for system loads of less than 100%. New overlay scheduling systems, such as an adaptive partition scheduler assist in managing large systems with a mixture of hard real-time and non real-time applications. I.e., *multitasking* is a separate issue from "real-time" But, that's Wikipedia -- who knows the pedigree of the author (*anyone* can create/edit a web page) Deitel, _Operating Systems (2nd)_, (c) 1990, p 5 "Real-time systems are characterized by supplying immediate response." Really? How do you quantify "immediate"? If I run the processor at double the clock rate, does that make it *more* real-time -- because the response is more immediate? "Real-time systems are often heavily underutilized -- it is far more important for such systems to be available when needed and to respond quickly than it is for them to be busy a large portion of the time. This fact helps explain their relatively high costs" Interesting definition. But, useless. Foster, _Real Time Programming Neglected Topics_ (c) 1981? never even *defines* "real time" (note the absence of the hyphen). This despite claiming to have taught the course "Real Time Programming" at least twice at UMass. Instead, he spends ~200 pp describing hardware interfaces, control theory, the sampling theorem, etc. Selic et al. _Real-Time Object-Oriented Modeling_, (c) 1994, p 16 "There is no universally accepted definition of what constitutes a real-time system. Systems commonly referred to as real-time span the range from small embedded microcontrollers that drive the operation of a microwave oven to very large systems such as global computer communication networks. A common misconception, even among some computer professionals, is that real-time by necessity implies microsecond response times that impose low-level assembly language programming. While this characterizes one category of real-time systems, it is by no means universal. "The ROOM modeling language was devices to model systems that have a certain set of characteristics... [paraphrasing] Timeliness Dynamic internal structure Reactiveness Concurrency Distribution" I.e., they won't even put forth a formal definition -- despite the fact that they've written 500pp on a modeling technique expressly *for* real-time systems! Hmmmm... Madnick&Donovan _Operating Systems_, (c) 1974, p 511 "A real-time system's scheduling policy must make the system capable of handling large amounts of data; it must be able to analyze or handle data faster than they come in and must also respond to time events" I guess that (large amounts of data) rules out the microwave oven that Selic considered a classic example of one type of real-time system. Tanenbaum, _Distributed Operating Systems_, (c) 1995, p 223 "What is a Real-Time System?" "In contrast, *real-time programs* (and systems) interact with the external world in a way that involves time. When a stimulus appears, the system must respond to it in a certaqin way and before a certain deadline. If it delivers the correct answer, but after the deadline, the system is regarded as having failed. /When/ the answer is produced is as important as /which/ answer is produced." So, a payroll system is NOT a real-time system -- because folks NEVER are willing to abandon the pay owed to them; there is always "value" to a result, even long after the 5PM Friday "deadline". Ah, but later he clarifies "soft" and "hard": "*Soft real-time* means that missing an occasional deadline is all right. ... In contrast, even a single missed deadline in a *hard real-time* system is unacceptable, as this might lead to loss of life or an environmental catastrophe. He then tries to hedge: "In practice, there are also intermediate systems where missing a deadline means you have to kill off the current activity, but the consequence is not fatal." What name is applied to these "intermediate systems" -- firm? squishy? Is "loss of life" what makes things "hard"? He also allows systems to have hard and soft subsystems -- without giving such systems a hard/soft designation. [I'll try to find references that claim *any* HRT makes a system *hard*! And, others that claim any SRT makes it soft! I know I have examples of both!] "Real-time systems are frequently programmed as a collection of short tasks (processes or threads), each with a well-defined function and a well-bounded executation time" I.e., there exist RT systems that do NOT use a *collection* of short tasks (single tasking -- no need for multitasking capabilities!). Zarrella, _Operating Systems Concepts and Principles_, (c) 1979, p 9 "Real Time Operating System" "Some operating systems must cater to events as they happen in *real time*. These systems usually have very tight constraints on the time it takes the system to react to a stimulus. In general, real-time systems must /guarantee/ this time requirement. I.e., no tolerance for anything other than (Tanenbaum's) HARD real-time, by this definition. "Usually, real time systems have an execution time margin (of 20% or more) built in for emergencies, but during normal operation this is wasted time." Gee, I didn't realize there was a 20% target for my "laxity"! "Thus, real time operating systems often have requirements to perform very low-priority operations whenever the higher-priority real time programs are not executing" "This type of operating system is often designed as *foreground/background*, where real time programs operate in the foreground with very high priority, while the background programs operate one at a time (in a batch-like manner) only when the foreground is not executing. "Multiprogramming Operating System" "Just as real time operating systems utilize a foreground/background organization to make more efficient use of computer systems, a *multiprogramming* operating system permits multiple programs to share computer processing power. Essentially, this is done by permitting a single program to execute until it stops to wait for an I/O device, operator input or some other event. When this occurs, the operating system saves all necessary information about the program in order to allow it to complete execution at some later time. The system then selects another program to run... Hint: multiprogramming == multitasking. Note how it is defined ORTHOGONAL to "real time"! Savitzky, _Real-Time Microprocessor Systems_, (c) 1985, p 4 "Real-Time" "The term /real-time/ covers a wide range of computer (and other) systems, but all share the common feature that results of some kind are demanded by deadlines imposed by the 'real' world outside the system. The range of time scales is immense, from microseconds (as in a digital signal processor) to years (in an airline reservation system or a seismic data logger). "Two Kinds of Real Time" No, not the two kinds that you *think*! :> "'Real-time' is used to describe two very different kinds of systems. The older usage, now fading, applied to such things as airline reservation systems and message switching centers. These systems were considered 'real-time' because there was an operator sitting at a terminal waiting for a response. These systems are now more commonly called /interactive/. Another older term for them was /on-line/." "The other kind of real-time system was once, before the advent of the minicomputer and microprocessor, less common; the situation is now reversed. This is the /process-control/ system in which the computer is directing or monitoring some ongoing physical process." I guess anything else is just not real-time! And, the idea of HRT vs SRT isn't even mentioned! Nor, the consequences of missing deadlines, etc. He then adds sections for: Polling Loop Event Driven Foreground/Background Multi-Processor Multitasking Again, multitasking is not *implied* in "real-time". Stankovic, "Misconceptions about Real-Time Computing: A Serious Problem for Next-Generation Systems", _IEEE Computer_ (c) 1988 "In real-time computing the correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced." This is the standard definition. But, what results do NOT depend on the time at which they are produced? Know many programs that run just for the sake of running?? Isn't there a point at which ALL results are "worthless"? How long are you willing to wait for that paycheck?? He presents common misconceptions: "There is no science in real-time system design" Yeah, just pick priorities until the code *seems* to work... Test the hell out of it and proclaim it "complete". "Advances in supercomputer hardware will take care of real-time requirements" Just buy a faster PC! "Real-time computing is equivalent to fast computing" If your deadline is in 6 microseconds, its "more real" than if its in 6 months! (e.g., reading a byte off a tape vs. making a course correction as a deep space probe approaches Jupiter; hint: you can always rewind the tape and try again!) "Real-time programming is assembly coding, priority interrupt programming and device driver writing" "Real-time-systems research is performance engineering" "The problems in real-time-system design have all been solved in other areas of computer science or operations research" "It is not meaningful to talk about guaranteeing real-time performance, because we cannot guarantee that the hardware will not fail and the software is bug free or that the actual operating conditions will not violate the specified design limits" "Real-time systems function in a static environment" I've not even begun to address the numerous on-line resources and the flaws and inconsistencies in their "presentations". Everyone *thinks* they know what "real-time" is and what constitutes an RTOS vs. an MTOS. And, if you look hard enough, you can probably find something that will back up any ideas you might have on the subject. But, that doesn't make them correct! Yes, by all means, *do* "find some reputable source and double-check what this guy is saying before you believe it". I gladly present all of this to the folks in my upcoming "class" so *they* can see my comments aren't based on something I picked up while standing at the water cooler! And, systematically poke holes in each of these "definitions". Perhaps *you* have a better set of references? Where did YOU learn your trade?
On 6/25/2016 11:52 AM, upsidedown@downunder.com wrote:
> On Sat, 25 Jun 2016 09:41:46 -0700, Don Y > <blockedofcourse@foo.invalid> wrote: > >> On 6/25/2016 8:27 AM, Simon Clubley wrote: >>> On 2016-06-24, Paul Rubin <no.email@nospam.invalid> wrote: >>>> Tim Wescott <seemywebsite@myfooter.really> writes: >>>>> So, this is the third time in a month or so that I've needed to tell >>>>> someone "use a task loop" -- but I'm not sure if I can say "just Google >>>>> it". >>>> >>>> I'd call that a polling loop, since it polls each task to see if it's >>>> ready. But I don't know if that's a standard term. >>> >>> Until I read your reply, this was _exactly_ what I was going to say. >>> >>> It _is_ a polling loop (or polling architecture if you want to >>> distinguish it from an interrupt architecture.) >> >> No. Why does any "polling" have to occur? Why can't every task be >> treated as active/ready? Why can't it coexist with an active foreground? >> >> How do you address task_N's whose ready conditions can't be simply >> externalized as "task_N_ready"? (Or, are you ONLY addressing implementations >> where this is the case -- ignoring any other sort of implementation that >> can ALSO exploit a "big loop"?) > > In the 1970's this was implemented with the event flag register > concept. > > On a 16 bit machine a global 16 bit event flag register was used and > each task had a wait for event flag mask. The scheduler performed an > AND operation between the global event flag register and the task wait > mask. If the result was non-zero, the task executed. Very light weight > scheduling if the number if the event flags fit into one machine word > and not horribly inefficient, even if you had to test a few machine > words :-) > > This concept could be used on a task loop as well.
There are some 8051 "OS's" that use this approach (very limited number of tasks) It means <something> has to actively detect the various conditions that might "make ready" a particular task. And, to potentially do it every time that set of conditions proves to be true. If you are interfacing something in the foreground (scarce time resources) to something in the background (e.g., "characters available in the UART receive FIFO"), then that's another action that must be taken in that foreground. Many MTOS's have support for events (some latching, others self-clearing). It's a relatively cheap way of passing (very little) information. E.g., "I have detected a 60Hz mains zero crossing". So, a background task can poll this -- or, in a preemptive scheduler, be automatically unblocked when it occurs -- and know that the "event" happened. However, there is limited utility. E.g., a UART might want to signal that it has some data in the receive ISR's FIFO. Or, that the receive FIFO has been OVERRUN (potentially very different reactions to these events). Or, that the transmit ISR has emptied its FIFO and is preparing to shut down the transmitter. Or, that a BREAK has been detected (unless you can encode them in-line AND they have no associated immediacy) OTOH, if a task can sit and watch for whatever it considers important (assuming you aren't using an OS), then it can implement whatever tests *it* deems appropriate -- now, and a potentially different set, later. E.g., I discussed one of my early barcode readers in another post. The ISR buffers "transition times" (edges) in a FIFO. The background extracts these. Should the background handler lock the FIFO (disable interrupts) to extract *one* edge? Or, should it possibly wait for 2 (white-to-black at the leading ede of a "bar" followed by white-to-black at the end of the "bar")? I.e., processing just a bar or just a space isn't of any help as a "character code" consists of a multiple of such bars/spaces. If the FIFO is *that* empty, maybe we shouldn't bother trying to extract anything, yet? Let some other task use the time that we would otherwise spend doing that! (and, avoid interfering with the ISR itself -- by leaving interrupts enabled!) You can usually arrange to leave some data in a "convenient" form so that it can easily be tested and acted upon. So, a waiting task can simply load the data, make a test and either return to sleep (relinquish the CPU) *or* wake up and act on it. The "testing" is done in the "background" -- where time isn't as scarce as it is in the foreground! And, what do you do in cases where the/all tasks are *always* ready (in a global sense)? I.e., I might be waiting for an incoming character from a UART, now -- and a timer to expire later -- followed by space in the same UART's transmit FIFO some time after that! Do these have to be three different tasks because they rely on three different "readiness" criteria? Do you have to keep the tasks in lock sync with the "producers" that are detecting the conditions that are assigned to each flag *now*?
On Sat, 25 Jun 2016 14:45:36 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:

> >> And, a task loop can be made real-time reasonably easily, as long as >> you're willing to live with writing every bit of code to the requirements >> of the shortest real-time deadline. > >Then it's not an RTOS (or an MTOS), is it? If it's an *OS*, please identify >the services that it is providing for you?
Send Message / Wait For Message can be easily implemented in a task loop by manipulating task_N_ready. No need to implement Create Process, since it is hardcoded into the task loop :-)
>Welcome to the days of "program loaders" (predating OS's)
You can make a successful RTOS with Create Process, Send Massager and Wait for Message services, the rest is syntactic sugar. Many companies involved in the 1970/80s 8 bitter embedded market had in house RTOS kernels that were quite simple. When Intel announced the RMS-80 (for 8080) it looked like a bloatware. Later on RMX-86 for 8086/88 was real bloatware :-).
On Sun, 26 Jun 2016 01:04:42 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:

>On 6/25/2016 11:52 AM, upsidedown@downunder.com wrote: >> On Sat, 25 Jun 2016 09:41:46 -0700, Don Y >> <blockedofcourse@foo.invalid> wrote: >> >>> On 6/25/2016 8:27 AM, Simon Clubley wrote: >>>> On 2016-06-24, Paul Rubin <no.email@nospam.invalid> wrote: >>>>> Tim Wescott <seemywebsite@myfooter.really> writes: >>>>>> So, this is the third time in a month or so that I've needed to tell >>>>>> someone "use a task loop" -- but I'm not sure if I can say "just Google >>>>>> it". >>>>> >>>>> I'd call that a polling loop, since it polls each task to see if it's >>>>> ready. But I don't know if that's a standard term. >>>> >>>> Until I read your reply, this was _exactly_ what I was going to say. >>>> >>>> It _is_ a polling loop (or polling architecture if you want to >>>> distinguish it from an interrupt architecture.) >>> >>> No. Why does any "polling" have to occur? Why can't every task be >>> treated as active/ready? Why can't it coexist with an active foreground? >>> >>> How do you address task_N's whose ready conditions can't be simply >>> externalized as "task_N_ready"? (Or, are you ONLY addressing implementations >>> where this is the case -- ignoring any other sort of implementation that >>> can ALSO exploit a "big loop"?) >> >> In the 1970's this was implemented with the event flag register >> concept. >> >> On a 16 bit machine a global 16 bit event flag register was used and >> each task had a wait for event flag mask. The scheduler performed an >> AND operation between the global event flag register and the task wait >> mask. If the result was non-zero, the task executed. Very light weight >> scheduling if the number if the event flags fit into one machine word >> and not horribly inefficient, even if you had to test a few machine >> words :-) >> >> This concept could be used on a task loop as well. > >There are some 8051 "OS's" that use this approach (very limited >number of tasks)
On RSX-11M (PDP11) had a 16 bit global event flag register. On RSX-11M+ had 16 bit group global event flag registers for each (up to 256) user groups.
>It means <something> has to actively detect the various conditions >that might "make ready" a particular task. And, to potentially do >it every time that set of conditions proves to be true.
The process that generates an event will set the appropriate event flag register bit. No problem.
>If you are interfacing something in the foreground (scarce time >resources) to something in the background (e.g., "characters >available in the UART receive FIFO"), then that's another >action that must be taken in that foreground. > >Many MTOS's have support for events (some latching, others >self-clearing). It's a relatively cheap way of passing (very >little) information. > >E.g., "I have detected a 60Hz mains zero crossing". So, a >background task can poll this -- or, in a preemptive scheduler, >be automatically unblocked when it occurs -- and know that >the "event" happened. > >However, there is limited utility. > >E.g., a UART might want to signal that it has some data in the >receive ISR's FIFO. Or, that the receive FIFO has been OVERRUN >(potentially very different reactions to these events). Or, >that the transmit ISR has emptied its FIFO and is preparing to >shut down the transmitter. Or, that a BREAK has been detected >(unless you can encode them in-line AND they have no associated >immediacy) > >OTOH, if a task can sit and watch for whatever it considers >important (assuming you aren't using an OS), then it can >implement whatever tests *it* deems appropriate -- now, and >a potentially different set, later. > >E.g., I discussed one of my early barcode readers in another >post. The ISR buffers "transition times" (edges) in a FIFO. >The background extracts these. Should the background handler >lock the FIFO (disable interrupts) to extract *one* edge? >Or, should it possibly wait for 2 (white-to-black at the leading >ede of a "bar" followed by white-to-black at the end of the "bar")? >I.e., processing just a bar or just a space isn't of any help >as a "character code" consists of a multiple of such bars/spaces. > >If the FIFO is *that* empty, maybe we shouldn't bother trying to >extract anything, yet? Let some other task use the time that >we would otherwise spend doing that! (and, avoid interfering >with the ISR itself -- by leaving interrupts enabled!) > >You can usually arrange to leave some data in a "convenient" form >so that it can easily be tested and acted upon. So, a waiting >task can simply load the data, make a test and either return to >sleep (relinquish the CPU) *or* wake up and act on it. The >"testing" is done in the "background" -- where time isn't as >scarce as it is in the foreground! > >And, what do you do in cases where the/all tasks are *always* >ready (in a global sense)? I.e., I might be waiting for an >incoming character from a UART, now -- and a timer to expire >later -- followed by space in the same UART's transmit FIFO >some time after that! Do these have to be three different >tasks because they rely on three different "readiness" criteria? >Do you have to keep the tasks in lock sync with the "producers" >that are detecting the conditions that are assigned to each >flag *now*?
On RSX-11 you posted an read/write QIO request and defined an event flag (typically #5 for terminal I/O), the OS then set this event flag when something happened on the serial line, such as received a character, had a framing error etc. The task waiting for the event flag then determined what was the cause of the recent flag setting.
On 6/26/2016 3:46 AM, upsidedown@downunder.com wrote:

>> It means <something> has to actively detect the various conditions >> that might "make ready" a particular task. And, to potentially do >> it every time that set of conditions proves to be true. > > The process that generates an event will set the appropriate event > flag register bit. No problem.
It means the signaling needs of one task have to be implemented by another. If the signaled task decides it wants to respond to a different set of conditions, then the signaling task has to be modified to detect those, instead of the original set. This can be a design-time change ("I'd rather only be notified of Rx FIFO activity") *or* a run-time change ("NOW, I'd like to be notified of *any* FIFO activity").
>> And, what do you do in cases where the/all tasks are *always* >> ready (in a global sense)? I.e., I might be waiting for an >> incoming character from a UART, now -- and a timer to expire >> later -- followed by space in the same UART's transmit FIFO >> some time after that! Do these have to be three different >> tasks because they rely on three different "readiness" criteria? >> Do you have to keep the tasks in lock sync with the "producers" >> that are detecting the conditions that are assigned to each >> flag *now*? > > On RSX-11 you posted an read/write QIO request and defined an event > flag (typically #5 for terminal I/O), the OS then set this event flag > when something happened on the serial line, such as received a > character, had a framing error etc. The task waiting for the event > flag then determined what was the cause of the recent flag setting.
So, the signaled task has to wake up to decide if it really *wants* to be awakened.
On Sun, 26 Jun 2016 05:11:32 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:

>> On RSX-11 you posted an read/write QIO request and defined an event >> flag (typically #5 for terminal I/O), the OS then set this event flag >> when something happened on the serial line, such as received a >> character, had a framing error etc. The task waiting for the event >> flag then determined what was the cause of the recent flag setting. > >So, the signaled task has to wake up to decide if it really >*wants* to be awakened.
You must be trolling. If I post a read/write channel, the expected result would be byte received or byte sent. However, if the result is different, such as timeout, framing error, parity error etc. it is as important to receive a notification of such events. It is much more convenient to have a channel specific event flag than having to search for the reason from a multiline serial card status registers.

The 2024 Embedded Online Conference