Suppose we have several active tasks with equal priorities. So, one task runs for one timer tick, then the next task runs for another timer tick, so on. Scheduler goes in a round robin manner.
At some moment, a higher priority task is activated. We execute this task, and then we have to return back to the round robin scheduling of the lower priority tasks.
Here is a problem: which of the lower priority tasks should be scheduled after the interruption of the round robin loop?
The best solution would be start at the same place where the round robin was preempted by higher priority task. But what if one round robin was preempted by another round robin at higher priority? Remember all positions for all possible cases? Doesn't look feasible.
The easiest would be restart round robin from task[0]. But, if round robin gets preempted before making a full turn, the tasks at the end of the list will never get executed.
We can restart round robin from random task in the loop. This is simple enough; however I am wondering if there is more elegant or efficient solution.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
Typically, you keep a list of "tasks" (lets not argue terms) at each priority level. The scheduler picks the first "ready" task on the highest "non empty" queue of tasks.
I.e., if tasks A, B, C and D are at priority 5 (assume higher numbers == higher priority) and no tasks are "ready" at any higher priority, then the READY[5] queue looks like: {A, B, C, D} (for example).
After A exhausts its timeslice (or yields it for whatever purpose), the READY[5] queue looks like {B, C, D, A}. And, assuming no higher priority tasks become ready, B will become the active task.
When B is preempted (by something that causes the scheduler to run, again), the scheduler examines the READY[] queues again. If it finds something in a higher priority queue (e.g., READY[9] = {X, Y, Z} -- perhaps these three tasks became ready at the same instant... maybe all waiting on an event that B signaled!), then it selects the first of the tasks from *that* queue to become the active task.
The tasks in READY[9] will share the processor until:
- a task in a higher priority queue becomes active, or
- all READY[9] tasks sleep/die (for whatever reasons) During this time, *none* of the READY[5] tasks will run.
How you deal with the fraction of a timeslice that B "lost" when it was initially preempted is up to you.
Instead of having *a* "time remaining in this slice" that is system wide, I have this value maintained in the READY[] queue (you don't need it in each task as, by definition, if another task in my queue is running, then
*I* have exhausted my time slice!) for each priority level.
So, when B eventually regains control of the processor (becomes the "active task"), whatever time remaining in its slice is given to it.
I.e., you treat the actions of any higher priority tasks AS IF they were interrupts -- the time they "consume" is invisible to the executing tasks at the priority that was preempted. (this model also makes it easy to think about how the OS *should* work)
Traditionally, the interrupted task is resumed from the point at which it was interrupted. This works fine if there is one task per priority level.
However, the moment you have multiple time sensitive tasks of equal priority you really need to time slice and, if any of those tasks are time sensitive, you may have to perform deadline scheduling - which can get *very* complicated.
Priority, fairness and run-to-completion are incompatible. You can have any two, but not all three. With prioritization, time slicing is required (but not sufficient) to implement (any kind of) fairness. [If you don't believe that, I can refer you to OS textbooks and research papers. OS internals are one of my "hobbies". 8-]
I'm not sure what you mean by "feasible".
You don't have to remember much beyond what an interrupted task was doing - it's register context - and information needed for scheduling: priority, trigger events, time stamps, etc. Deadline scheduling needs a shitload of scheduling data, but no RTOS I am aware of actually does deadline scheduling.
If you have a simple run-to-completion model, then you only need one register context per priority level. If you are time slicing, you need one per task. The other information is needed per task.
Then you've implemented time slicing ... only with arbitrarily long slices: to task completion or to next priority change.
Nope ... only more complex solutions for more complex problems.
Thanks, I see now. And for each list you remember who is the next to go. This certainly works; however it requires maintaining lists and updating them in the situations like temporary elevation of priority. Lots of overhead. I hoped to find a light weight solution.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
Yes. You need *some* way on sorting out the "ready" tasks from those that are "not ready" (disabled, blocking, etc.). One way is to thread them onto a "ready list".
If you have just one list, though, they you have to keep it sorted by priority *and* inserting another task into this list is no longer a constant time operation (unless you keep pointers to where each "group of tasks at a given priority" begin -- i.e., a list of lists).
Which begs the question: are you really looking for an RTOS or just an MTOS? E.g., an RTOS makes extra guarantees that an MTOS need not. Many so-called RTOS's are really "fast-ish MTOS's".
Often, MTOS's fail to be pedantic about invoking the scheduler every time it *should* and, instead, leave preemption to "selective conditions" -- sometimes, little more than the jiffy! Still others blindly call "reschedule()" each time there *might* be a need. Coming up with efficient ways of knowing when you can skip the reschedule() without impacting the system requires a bit more "art".
Yes. You also have to deal with cases where the "readymost" task at a given priority (i.e., head of it's READY[] queue) is moved to another priority level -- what do you do with the balance of its (previously preempted) time slice?
And, there are different criteria that can be used besides round robin/fixed priority to determine scheduling. In my multimedia RTOS, this is a pluggable module and allows me to change scheduling criteria at run-time based on the nature of the tasks active at any given time (RR, RM, EDF, etc.). The problem (for the system designer) is that you often have a mixture of tasks with different and competing scheduling algorithms. :<
Look at the nature of your tasks. Think about what *could* happen if any one of them became "starved" (completely or partially). Would some *other* aspect of the system throttle its competitors such that it would eventually regain processor share? (e.g., in a producer-consumer relationship, either party eventually ends up *needing* the other and, in the absence of that "other", effectively stops competing).
You also need to track any resources the "task" (again, lets not pick nits on terms) owns. E.g., if it has taken a lock, it *still* holds the lock even while preempted! And, of course, other "physical resources" (memory).
Look at MARTE and ERIKA. There may be others (as well as some that aren't "commercially available"). The problem is defining how generic you want that "deadline scheduling" to be.
Without preemption, you only need one register context per processor!
Isn't that what makes it fun?? (pity the folks who can't wake up to find something gnawing at their "creative center" each day :> )
I have the best of both worlds: RTOS with MTOS capability. In addition to the scheduling by priority, it allows for the round robin time-slicing of the tasks with equal priority.
Here is a cheap solution: restart round-robin time slicing from a random position in the corresponding list. Although it is not exactly fair, it works very nicely and avoids several problems.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
Well, RTOS *tends* to be a superset of MTOS -- it's an MTOS that gives temporal guarantees on its services (an MTOS just tries to share a processor using "some set of criteria")
But then you can't make any RT *guarantees* -- since you (your tasks) can't know "definitively" what resources they will have made available to them (?) There is something inherently non-deterministic built into the scheduler!
[in hindsight, should have crossposted all this to comp.realtime -- even though its a wasteland]
The deadlines are guaranteed for RT tasks, corresponding to their priority. Besides, I have a bunch of soft-RT and non-RT tasks which run by time slicing. It is very convenient to have all that under the same framework and same API.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
I'm going to get all pedantic, and probably start a flame war thereby.
A tasking kernel that doesn't use constant-time operations (like inserting tasks into the ready list) can still be real-time. "Real time" -- as I've seen it defined -- doesn't mean "consistent", "Real time" means "has bounded maximum times for operations".
So a task switcher that has an unpredictable task switch time can still be real time _if_ that unpredictable switch time has an upper bound.
Granted, the unpredictability makes verification by testing exceedingly difficult, because how do you know if you're loading the thing all the way?
Your comment about "doesn't always call the scheduler" also doesn't (if you're pedantic) necessarily violate "real time-ness", although it certainly does -- in spades! -- make it fiendishly difficult to test quality in.
IMHO there are few "real time" systems that are are actually correctly tested or analyzed to verify that they are really meeting real time criteria. For that matter, IMHO, there are a lot fewer systems that are really, truly "hard" real time than we like to think -- because if there were, there would be a lot fewer systems that actually worked!
--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com
Yes. Or, "deterministic". The problem is, if you don't carefully choose *how* you implement things, those bounds can be very loose -- so loose, that the guarantees are impractical for the needs of your application.
E.g., like spec-ing components with -50% +500% tolerances; if you look at the worst case with that +500%, you realize "circuit won't work".
So, one common approach is to use constant time operations (or, at least, O(N) algorithms) where the user can more readily "feel" the cost -- as "N" is typically visible.
Note the non-believers who complained of my use of dynamic memory allocation in RT systems. :>
Yes. See above. OTOH, if that scheduler examines *every* task in the system -- even those known to be "not READY" -- then its performance will be abysmal. It won't allow those tasks to meet their RT deadlines because its guarantees aren't worth crap. "Yeah, we'll get around to doing it *sometime*..."
If you don't always call the scheduler when you *should*, then you are violating the criteria that your scheduler is STATED to use. E.g., what if the jiffy didn't call the scheduler? Then, your time-slicing wouldn't truly be working (you can still have a preemptive OS without timeslicing).
You can, for example, have very long time slices in an RT system and still manage to meet very *short* deadlines.
*IF* you correctly call the scheduler each time something which can cause preemption happens! (i.e., instead of hoping the jiffy comes along and runs it *for* you!).
So, if B signals an event that makes A ready *and* A has a priority higher than B, then the scheduler *should* be run coincident with B's signal(). Otherwise, you are
*hoping* the jiffy comes along (or B yields the processor) "fast enough" so that A *can* be started.
If B's signal() does *not* cause the scheduler to run, then your RTOS is broken. It's as if the "interrupt" (that the event's signal() is analagous to) has not been recognized.
Consider, B can do something *knowing* it will make A ready. And, since this is a preemptive system, it can *expect* to be preempted and A *will* now perform some activity!
So, B could be doing something like sucking up bytes from a serial stream. It can signal "stream-received" KNOWING that A will now process the stream (because it KNOWS that A is "ready"). B can then proceed AS IF A had processed the stream *without* having to wait around for the next jiffy, etc. to cause the reschedule.
MTOS's that don't call the scheduler reliably each time they
*should* force A and B to add another interlock: B signals A that the stream is ready; then A signals B that it has seen B's signal and has, indeed, processed the stream -- so B can now proceed on the *knowledge* that this has happened.
OTOH, if you reliably invoke the scheduler and the system designer *knows* that A is READY (perhaps it was A who spawned the B task and is now waiting on B's signal), then B can do something as heavy handed as:
KNOWING THAT IT WILL ALWAYS WORK AS INTENDED! If you think about this, you can see how easy it is for pathological behaviors to manifest in systems that
*aren't* pedantic about invoking their schedulers. They misbehave and the "fix" is to add more explicit interlocks -- duplicating functionality that the OS is *supposed* to provide.
Many RTOS's give the user no way of checking whether deadlines are being met. And, no way of recovering if a deadline is
*missed*.
Actually, the problem I see more of is people treating SRT problems AS IF they were HRT and, as a result, making their implementations more brittle *or* over-resourced (blech! what a mangled word!).
There *are* a lot of HRT applications out there. E.g., conveyor belts where failing to process the item before it "falls off" is an obvious "failure".
But, too often, a lot of cruft that doesn't belong in the HRT part of the loop gets stuck there due to poor engineering. Analagous to heavy handed use of "disable interrupts" instead of smarter synchronization between ISR and "consumer".
[gee, and I didn't even get a chance to light my flamethrower :< ]
True. But "loose" and "not there" are two entirely different things. In the case of an RTOS, the only requirement to be "real time" is that the tolerance be specified as -100% to 0% of "spec".
But then, when was the last time you saw an RTOS that gives you an up-front and realistic clock-tick count for a rescheduling?
And that's certainly far better than something that varies wildly, to be sure.
I dimly recall being one of the complainers -- but I wasn't complaining about timing.
I don't know about that. Abysmal performance, yes -- but if it's abysmal _and_ predictable, is it that bad?
-- argument snipped --
I think I misunderstood what you meant. Yes, the kernel should always call the scheduler when it "should", and it should be clear in the documentation when that is.
I could see (since real-time programs always have not-so-real-time elements) that it would be nice for every OS call to have a "force a reschedule NOW dammit" version and a "reschedule this when you get around to it" version. I could also see this being a nightmare in the hands of the wrong developer (or set thereof).
Although it is often easy to build that into one's code when it is important. What's worse, in my view, is that even if you do go and instrument your code to make sure deadlines are being met, you have no way of knowing from testing if those deadlines will _still_ be met if you add a task, or if the rescheduling time increases for high priority tasks as the number of tasks in the ready queue increases, etc.
That's a different view of what I was getting at. What you said, plus when they get done and the system "works" (with totally inadequate testing), they tell themselves "I know how to do HRT systems! I'll go do some more!!"
I see a lot of control loop software designed with an absolute paranoia about getting each and every sample into the controller in a timely manner -- yet most control loops that can stand real-world noise and plant variations can stand to miss the occasional sample (with heavy emphasis on the "occasional"). If the code and control rule are designed right, the dropouts can be even more often than just "occasional"*, leading to even more tolerance to timing. So as real-time systems go, this falls into the "soft" real time category -- yet folks will sacrifice everything to treat it as hard real time**.
And bytes falling into the bit bucket instead of going into a queue, etc.
Yup. I think the most common case I see is when you _could_ split a task into a "hard real time" part and a "soft real time" part, or a "really, really fast real time" part and a "much slower real time" part. E.g. pulling bytes off a comm port, shoving them into a queue, and parsing the messages out of them. Pulling them off and shoving them into a queue is often so time critical and easy that you just do it in an ISR, and either schedule the parser when a flag comes through or on every byte, but only run the parser when the _really_ important stuff*** is done.
I'm intentionally not defining "occasional" here, because it depends on the system. One in five may be occasional for system A, but one in
500 may be too damn often for system B -- it depends.
** Or they'll throw any pretense of timeliness to the winds, and _really_ screw things up, but that's an issue for another post.
*** like, anything I wrote :-).
--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com
It does not take much belief to see the usefulness of dynamic memory allocation, just some (not very high) complexity of the task at hand :-) .
I believe most people put too much into task switch timing for real time. While it has to be kept in sane limits, it is rarely if ever the system limiting factor. Interrupt latency is.
Vladimirs original question was about fairness of lower priority tasks. How I have implemented it in DPS (around 1994 and nearly unchanged since because of no necessity) can be looked up. I have yet to see a scheme which could rival this one (which I have likely reinvented, by 1994 all that stuff had all been long beaten to death; but reinventing the obvious is often the fastest way :-) ).
Yes. But, what ends up happening, is you end up spec-ing a system that has far more capability than you need "typically" just to handle the "worst case" -- because the system (OS) wasn't designed using algorithms that are more "tightly bounded".
Very few *publish* those criteria. And, they rarely publish metrics in a form that you can "scale" to your hardware. E.g., when I write drivers in ASM, I specify execution times parameterized to include the speed of the CODE and DATA memory accesses (wait states, etc.). These tend top be the "hardest" RT portions of an application (e.g., guaranteeing you can empty a UART before an overrun, for exxample).
By far, the *best* way (IME) to design RT systems is to trim as much as you can out of the HRT "stuff". Then, put detectors in that *truly* HRT part that can tell you (at run time) when you have missed a hard deadline (e.g., building on the UART example: "when you have a buffer overrun"). Finally, make the SRT portions of the application smart enough to know how to *sensibly* deal with that missed deadline (since many RT systems are an infinite loop of *one* RT "application")
Well, it's easier to *live* with. Not necessarily easier to design the OS that way! :> (i.e., I burden the OS so the application can have greater freedom)
it depends on the resource budget you have available. If you are resource constrained, then this sort of thing can make a really dreadful product ("No, we can't double the speed of the processor just to accommodate your crappy coding style!").
If you can get by with sloppy/abysmal algorithms, then why bother refining them? OTOH, why not refine them and make the product less expensive for that level of performance? (there is a point beyond which you can't save any money on your DM)
I have a simple rule: if something happens that can change the readiness of *any* task, then there is a possibility that the currently executing task may change. Now, that doesn't mean you have to call the scheduler each time something changes the readiness of a task! You can be *smart* about it -- or naive.
E.g., you can use peephole optimizations to decide when you
*don't* have to call the scheduler. E.g., if I make a task ready by invoking some part of the API, that routine can examine *that* task directly and decide if it makes any sense to reschedule.
So, if I do something that makes a task at priority 5 ready but *I* am executing at priority 7, then I *know* that any call to the scheduler is going to decide, "No, there is a priority 7 task ready to run so this priority 5 task is still 'ready but waiting'" -- why bother calling the scheduler since it will just burn more CPU cycles to come to the same conclusion??
(i.e., these little optimizations can make a big impact on an RTOS's responsiveness and efficiency).
The smarts should lie within the API itself. I.e., if you call on the RTOS to do something for you and that something has side-effects that could affect the readiness of other tasks, then the RTOS should implicitly do the reschedule for you. It's like "arming an interrupt" -- you *expect* the IRQ to be asserted thereafter. IF YOUR CODE CAN'T HANDLE THE IMMEDIATE POSSIBILITY OF AN IRQ PREEMPTING IT (sorry for the caps), then you *explicitly* disable interrupts -- and this is very obvious in your code (along with a comment explaining same).
If your RTOS doesn't invoke the scheduler, then, sooner or later, luck will have the jiffy come along immediately after whatever you did that caused "that other" task to be ready and "you" *will* be preempted, possibly unprepared! (i.e., your code has to be prepared to be preempted the instant it does "whatever" to make that other task "ready".
*Hoping* that you aren't preempted is wishful thinking that invites bugs)
If you don't want to be preempted, then lock the scheduler before you make that other task "ready". Or, restructure your code so that you *can* be preempted once you make it "ready".
(sorry, too many words for a simple concept?)
Correct. Though there are some scheduling algorithms that allow you to "predict" schedulability based on an analysis of the frequencies with which your tasks are invoked and their processing times, etc.
And, when they get reports of (unreproducible!!!!!!!) crashes, they just shrug as they have no way of understanding where the "brittle point" in their implementation was located. So, they ignore the bug report ("If I can't reproduce it, how do you expect me to *fix* it??" "Well, if you had designed the system so that it couldn't fail that way, then you wouldn't *have* to reproduce it!")
Exactly. Inertia is your friend. I.e., you can look at things "after the fact" and still decide if "more control" (correction) is needed. If that last event "looked right" post factum, then who cares if you "missed its deadline"?
And, chances are, if *this* event looks OK, then the one you just *missed* probably was OK (or, at least not TERRIBLY BAD!), too. (of course, this depends on the process you are controlling).
Because HRT is much easier to wrap your mind around! :>
Look at X, make decision Y, then forget all about this and repeat.
One of the industries I worked in the customer questioned if the addition of the control loop didn't, in fact, make matters *worse*. I.e., because there is some normal variation in all processes. If you acted on every event, how do you know you aren't reacting to *noise*. Hence the rise of technologies like SPC which deliberately go *outside* the control loop.
Yes. Ask yourself, "How important were those bytes?" Did I actually lose any information? Or, do the bytes coming in *now* give me the same -- or BETTER? -- information?
E.g., I have a standard way of writing UART handlers. Feed a FIFO of some configurable size, etc. In some systems, each entry is two bytes -- character plus error flags. In others, just one (and sometimes some inband signalling to represent notable error conditions).
You *must* deal with buffer (software FIFO) overruns as there is almost always some set of circumstances that can cause them to happen. When this happens, I insert a marker into the data stream saying, in effect, "some stuff is missing, here". And, if the next character comes in before the overrun has been cleared (by some number of characters being "consumed"), I don't have to do anything as "some stuff" is now "some stuff plus one more".
So, when the application starts pulling in the data stream,
*it* decides how critical "some stuff missing" will be. E.g., if it happens in the middle of a "message", then the message is unreliable -- wait for the next "message boundary" to resynchronize to the data stream. You have no way of knowing how *much* data is missing (I don't report that -- a gap is a gap is a gap) but you know that any time you *don;t* have this indicator, then NOTHING was missed in the data stream.
Exactly. This is the *art* of RT design.
E.g., When I write a barcode handler, I have a very lean ISR (invoked by a black-to-white or white-to-black transition on a photodiode) that just grabs the value of a freerunning timer and stuffs it into a queue. [It also grabs another timer that tells me how long ago the "edge" happened before the ISR actually had a chance to respond] Then, it sets up the hardware to look for the "other" edge (WB vs BW) and quits.
A harvester thread continually examines the FIFO trying to pull out timestamps as fast (on average) as they are coming in. From adjacent pairs of timestamps, it computes "bar/space durations/widths" and feeds another FIFO. The goal of this first thread is to keep the ISR's FIFO "available" to the ISR at all times. Without burdening the ISR with trying to compute "bar widths" (dealing with the variable ISR latency, counter wraps, etc.).
The "bar widths" FIFO is examined by another thread that tries to find things that "can't be" valid bars -- too wide, too narrow, etc. It's goal is to keep this bar widths FIFO available for the harvester thread (by removing any cruft ASAP!)
Each stage adds complexity to the algorithm. But, it keeps the algorithm very robust. Remember, we're not "just" decoding bars/spaces! :> (anymore than debouncing a keyboard should use a significant portion of an application's resources)
The point of all the complexity is to decouple the HRT aspects (catching black-to-white and white-to-black transitions on the "video") from the SRT aspects (figuring out what, if any, barcode is represented by those transitions -- and, adding meaning to it). It allows these "softer" tasks to run while gathering "transitions" (because you never know when a barcode will be encountered) instead of deferring them until your "transition buffer" is full...
Yes. And, how you respond can vary. E.g., you might be able to run "forever" missing one in ten. Yet, missing three in a row might leave your process too "vulnerable" to operating "uncontrolled". I.e., you don't get to *see* that you are out of control until it is "too late".
"We can just use a P4 running Windows/Linux/whatever... And, if that doesn't work, next year's model will be 60% faster so
Most RTOSes (though not all) define a "task" as something that is lighter weight than the traditional notion of an OS process. I've seen everything from register context threads to VMM separated processes referred to as "tasks".
Things like memory typically aren't considered for scheduling, although they could be. Many desktop/server OSes have a 2 level scheduler: a primary that schedules register context threads and a secondary that schedules processes (deciding whether the threads in a process are included in the set scheduled by the primary. This kind of separation was needed back in the days of swapping when it was a big deal to restart a non-resident process. Demand paging has all but eliminated memory as a factor for scheduling.
I couldn't find a link to ERIKA, just to some projects that claim to use it. MaRTE's EDF scheduling appears to be slightly more predictable than Ada's, but Ada's task scheduler isn't particularly sophisticated to begin with
In a real deadline scheduling system, when a task pends on an event the scheduler needs to know:
- the actual deadline. This can take 2 forms: a maximum delay before scheduling a run-to-completion task, or for a time sliced task the time required to compute the response and the maximum cutoff time for producing the response. - whether the deadline is "hard" or "soft". It is an error to miss a "hard" deadline. A "soft" deadline is a best effort response. - how to deal with a deadline which is missed: e.g., ignore it, restart the task, resume the task, etc. - the priority of the task - any ad hoc. other things the scheduler needs to know
A deadline scheduler has to guarantee that all "hard" deadlines are met (for suitable hardware) and make best effort at meeting all the "soft" deadlines. In a time slicing system the scheduler has to decide which ready tasks can safely be delayed another quantum in order to pick one to run.
As I said before, I know of no available RTOS that actually implements deadline scheduling. It isn't simple, it is a global minimization function on all the simultaneous time and resource constraints ... and nobody does it. Nobody ever did it except maybe as a research project. At best, RTOSes provide priority preemption and a promise of maximum scheduling delay. If the application fits the predictability model that this presents, that's fine - but it doesn't work for all applications.
Sophisticated scheduling algorithm is no cheap to compute. While optimizing the order of the tasks, it consumes the CPU resources by itself. So, there is not much that could be gained compared to the simplistic solutions like ratemonotonic; why bother?
In practice, there are few realtime tasks and many tasks that can wait; the OS should not add the unnecessary overhead to every task. In the other words, if you need this particular task to be realtime, you should take care of it, not OS.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
Most use the term *thread* to reference "lightweight process". :>
I use "thread" to describe active objects while "process" is a (passive) container for resources (including threads).
A "task" can be some abstract concept pertaining to a "job to be done" (I have used the term "job" in the past, as well).
Since all of these terms are nonstandard (a classic UNIX process is single threaded, more modern Eunices support multithreaded processes, "process control" divorces the term from this context entirely, etc.), I always add the caveat to avoid nit picking -- and, alert the reader that his idea of task/ process/thread/etc. may not coincide with the one being loosely used, here.
I added memory as it was an example of a *resource* that needs to be "remembered" just like other parts of the "task's" state. Your comment:
"You don't have to remember much beyond what an interrupted task was doing - it's register context - and information needed for scheduling: priority, trigger events, time stamps, etc."
enumerated the sorts of things that have to be "remembered" in a task's state. "It's register context", "what it was doing" "[scheduling information]", etc. I was contending that there are lots of *other* things that have to be "remembered" for the task (i.e., everything that fits in the [process] container that I alluded to).
Doesn't have to be sophisticated -- just predictable. :>
The scheduler doesn't have to "guarantee" that these are met. That's the job of the system designer. E.g., it you try to schedule for 110% utilization, the scheduler *will* fail.
Some systems *can't* meet their deadlines 100% of the time. This is especially true for systems with asynchronous processing needs (event driven).
If you are designing a system that operates in steady state all the time, then scheduling is much more predictable. E.g., RMA is a win, here -- though with much lower processor utilization guarantees.
EDF is rather easy to implement and, in those systems where "tasks" (in my "abstract" role) are in harmonious accord with each other (e.g., you never exceed 100% utilization even on the short term), can be quite effective.
You're trying to describe something that "can't work" -- with unconstrained task requirements. E.g., I have three "tasks" each needing 100 time units to complete and each must be completed within 110 time units. "Coincidence" has caused them to be started (asynchronous events!) at the same instant. No scheduling algorithm "works" in overload.
OTOH, EDF *will* schedule all three of them properly IN THE PRESENCE OF OTHER COMPETING TASKS *if* they never exceed 100% utilization. (this is a relatively simple exercise to do in your head -- and doesn't require lots of analysis. It's analagous to a family getting ready for work/school in the morning: "Who needs to be OUT THE DOOR
*first*? OK, *he* gets first crack at the bathroom (shared resource). Once he's done (his deadline is met), "Who needs to be out the door first?", again. I.e., if you don't have to be "out the door" until afternoon, then you just aren't going to be using the bathroom in the morning! :>
As long as the work to be done *can* be done in the time available, EDF will make it happen. If it *can't* (i.e., the system is overloaded) then you're trying to have the scheduler decide who *should* break and who *shouldn't*.
Hmmm... you are aware of every RTOS in every product released? :> Surely you are just commenting on commercial offerings?
E.g., I rely on CoW semantics in my distributed memory system. I don't think many (any) commercial RTOS's support this -- yet, clearly *someone* has "done it" (me! :> ).
And, if the system is overloaded, how is this "better"/worse?
Rate Monotonic doesn't guarantee the same levels of processor utilization. It is only really useful with static priorities. I.e., devices with fixed workloads that can be analyzed at design time, etc. If you can get by with this, then why use anything more complicated?
I have one MTOS that deals with things "brute force" -- context switches are *almost* free... so, I invoke the scheduler VERY often (e.g., more than 1KHz). Everything can run at essentially the same "priority" and still be guaranteed timely service (though you have to keep everything "short and sweet" because your timeslice *will* be very short!). I write code in that environment very differently than I do in "fleshier" ones -- e.g., I may literally spin on a condition variable instead of having the OS add support for an event notification.
The trouble comes when you have to deal with more and varied "tasks". Or, with asynchronous activations. Things that cant easily be sorted out "on paper" ahead of time (though with reservations, some of this can be alleviated).
The OS is there to make the developer's job *easier* by managing resources for him. If your OS is getting in the way, then get a better OS! :>
You can always devolve to the "run everything time critical in an ISR and leave the rest in the background..." :-(
This is where I started. In the addition to described, in my first MTOS the tasks could call scheduler if they have nothing to do; so they don't have to consume the entire time slice. So, the scheduler loop was spinning through all tasks with the variable rate (from =10ms to ~10us per full revolution). If none of the tasks had anything to do, I put the system to sleep till an interrupt.
This approach is very simple. It is also free from priority resource deadlock problems, as every task gets time slice anyway.
I am already three major versions past that first round robin thingy :-) Round robin is supported as well as event driven priority scheduling.
Things that
If you make a fool to pray God, he will break his forehead.
I thought for a while about complete unification of interrupts and tasks. I.e. having them under the same abstraction. Unfortunately, that implies a lot of OS overhead.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
Yes. You can even craft executives that save *no* "task" state (other than PC) -- but that puts other constraints on the way you write your application.
Well, you can still have deadlock. You just don't have "priority inversion" as everything is "flat".
Hmmm... I guess i don't understand the reference :<
I treat the "application layer" AS IF it was just N layers of ISRs competing and coexisting. E.g., I try to design APIs so there aren't arbitrary "can't be called from an ISR" restrictions. Sometimes this affects the types of objects that can be supported (as you need to keep the interfaces "light").
The problem I always see with traditional "priority based" scheduling is there are no hard and fast rules for assigning priorities. Instead, folks tend to discover belatedly that the structure of their system is "wrong" and try to *make* it work by tweeking priorities. And, this turns into a "tipping canoe" exercise -- you move one way and the canoe starts to tip... so you move the other way and it tips a different way, etc. I.e., there is no "engineering" involved in picking the priority levels.
It's always amusing to see folks evaluate the *number* of priority levels supported in an OS AS IF "more is better". (Then 50,000 levels has *got* to be better than *20*!)
IME, an MTOS gives its biggest bang for buck by helping you decompose an application into independant "tasks" (using the meaning: "jobs") so you can focus on one at a time without having to juggle all of them at once. Beyond that, its a question of how much you want to migrate application requirements into the OS's domain instead of the application;s.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.