Hello. We want to continue our discussion of rate monotonic theory advantages and pitfalls. I call them pitfalls because rather than disadvantages, we have work-arounds and solutions to deal with them. So there are things there if you're not careful, you could have a problem. But as long as you pay close attention to the methods of applying the theory, you should in fact be fine. So let's skip to slide 6. We finished up last time talking about whether we should use dynamic priorities instead of the fixed priority rate monotonic. The point we made was, well, rate monotonic is fixed priority z standard of practice. Today, basically, dynamic priorities are used for soft real-time systems and fixed priority is used more often for hard real-time mission critical systems. So if we stick with that, the Policy to Assign Priorities in RTOS or with SCHED_FIFO like we're doing for a Service Set is well-defined. The highest frequency gets the highest priority and it's simple. It stays that way while the services are running the entire time that they are on-line, right? So the entire time that we're providing mission-critical hard real-time service. If there's some sort of initialization time, then we consider the system to be off-line and not in a real-time mode. This can also be done by mode. So for example, the shuttle had ascent and entry modes as major modes. The real-time feasibility and safety can be analyzed independently in those modes, as long as the system can switch modes, perhaps going from an on-line to an off-line state temporarily back to a new on-line state. Normally, the off-line is analysis for a fixed set of services using worst-case analysis, using tools like cheddar or hand analysis, and we transition from off-line during boot or mode transition to on-line. Examples of this are things like autopilots, where you engage it and when the autopilot successfully engages its on-line, prior to that it's considered off-line. So the service set can't change. There's no dynamic admission in this standard approach. So on-line services admission is more sophisticated and we'll talk about potential uses of that before we're done here today with this segment. But to do that, we would have a feasibility test that actually runs to test the feasibility of new services as they are added to an on-line system. So the feasibility test itself would have to also be a service that would run somewhere, and we can talk about options for where that might run. Most real-time systems have static service sets. This is certainly safe state of practice or modes with different service sets that have been analyzed in advance statically. For example, the Spitzer Space Telescope, we had observing modes, you can have ready mode, safe mode, things like that, and you can apply the feasibility testing to each mode. So that's a straightforward approach to dealing with some level of adaptation even though you have fixed priorities. So something to consider before you decide to say go to dynamic priorities. Pessimistic assumptions associated with rate monotonic require resource margin safety. This is not a bad thing in engineering, right? Having margin and safety is something we always look for. The only time it can be considered not good is when you have more margin or more safety than is actually necessary. That's often in judgment call but you might determined that we're okay with having just 10 percent margin. Rate-monotonic may result in substantially more margin than that by failing this service set, which is feasible and therefore pushing you to have more margin than you might actually require. So that's a question. What do you actually want for safety? Well, you can do worst-case analysis and look at the actual slack time and compute the actual margin and then determine what's safe. So those would be scenarios where you're above the LUB but through worst-case analysis you determine the system is still feasible, then you just need to analyze over the LCM, figure out how much slack time you have, and determine if you have sufficient margin for safety. C equals WCET. This is fairly pessimistic. We really, for hard real-time mission critical systems need to take the worst case execution time. The longest path through the code that's executed least efficiently, that is really more than a, even a three sigma deviation. Something that's rarely going to happen. If we have something that's really soft real-time or more like firm. Real-time is what some people like to call it. [inaudible] we could tolerate a very occasional miss deadline and recover. Then we might take something that rather than worst case execution time, we might just take a worst case. Worst case has been observed over long-duration testing rather than fundamental architectural analysis that truly determines the worst worst case. But that's what we need if we really have hard real-time potential loss of life or property. The worst-case in our arrival rate is similar. We can do period transform to deal with period that can be shorter than the average or expected period. Frequency that can be higher than the average or the expected frequency and simply do period transform. The great thing about being pessimistic is this, just create slack. Slack can be used by best effort or soft real time services in a mixed hard-soft best effort service system. Another objection we looked at is the importance encoding requires period Transform. Well, that actually seems pretty reasonable as well, because if something is important, must not fail even though it's low frequency. We're simply pretending or assuming it has a higher frequency than it actually has. When it's actually requested the lower-frequency, we're just creating Slack, which once again can be used by soft real-time or best effort services. It's rare that that Slack goes to waste and it can't, as long as you have some other uses for it that are best effort or soft real-time. The critical instant assumes service requests may come all at once, which we always show in all of our worst-case analysis timing diagrams, certainly we can create a hard-coded schedule or some sort of specific sequencing for pipelines of services that reduces this worst case scenario for the critical instant. However, the critical instant, what I would point out about as it gives you a fantastic flexibility. In other words, it says that all services can simply be driven by real-world asynchronous events. If they all happened to occur at the same time, your schedule still going to work. It's much more flexible than any hard-coded schedule. I like to use sequencing, which is compromise between hard-code schedule, and the true worst-case critical instant. In other words, there might be services that can execute in specific rates driven by one source of events rather than n sources of events that are completely asynchronous. But that's a design judgment call that you need to make. It depends on what your sources of interrupts and event detection are really. The rate monotonic LUB is not exact that we know. It's based upon service periods that are not necessarily harmonic. To really understand this, we need to look at the LUB derivation and we do this in course 2. It's a reason to stick with us for Course 2 to fully understand that. That gives you a deeper understanding, really rate-monotonic theory and general worst-case analysis and why the LUB is not exact and what the fundamental concept is of harmony between services or lack of harmony between services and so forth. But the nice thing is LUB gives you this order n back of the envelope calculation that you could do quickly during the early phases of your design project or as an online dynamic admission, that's really quick, compared to order n-cubed, much quicker than order n cubed, and it can be used. What you can do instead is you can use the order n-cubed alternative completion test or scheduling point if you need to be exact. I have a couple options, more pitfalls. These two resources I found particularly useful when applying rate monotonic theory. This paper and then the practitioners handbook. Some more problems that are pointed out, our period is not constant. We talked about the fact that we can do period Transform. That just create Slack, which is really never a bad thing as long as it doesn't prevent you from actually succeeding as far as what as the services you must scheduled to be successful. The only problem that it really can't solve is truly A-periodic services. So things that have absolutely no period. It does well at handling sporadic services that are mostly periodic but have a frequency band that they operate in, in other words, high tidal, low-frequency, but there's some jitter within that frequency band. But truly A-periodic services requires more of a recovery strategy which we talked about in course 3 in this series. So C is not deterministic. Well, we talked about WCET, and worst worst case execution time. The fact that this is going to create slack or potential for occasional miss for firm or soft real-time. That can be addressed. These references talk about these scenarios. Rate monotonic does not encode importance. Again, we said, but let's use period transform. That's going to create slack for use by best effort or soft or firm real-time services, we've covered that already. Deadline not equal to period. This one's more interesting. If it's longer, we have overlapping requests for the same service. If it's shorter we have some padding in our response timeline that we can use to generate outputs or for our outputs to be transported across a network or something like that. If we need to account for I/O latency, we might want deadline less than period. In the case of deadline greater than period, this means that we have overlapping requests for the same service active at the same time. But we have this all the time and things like servers, web services. Many people make a request for the same service and there are multiple outstanding requests, a queue of outstanding requests, in fact. One solution that was presented early on, is what was initially thought of as new theory, deadline, monotonic policy, and feasibility test. But turns out it's really just a special case of rate monotonic. So what is it? Well, the reason I like to cover it's an alternative view on the same thing. That can be useful sometimes to help you understand. The policy first of all, rather than the shortest period gets the highest priority, the shortest deadline gets the highest priority. Be sure not to say earliest deadline because that implies dynamic priorities. So it's all about the requests frequency, or the frequency really associated with the deadline as a duration. So the deadline is shorter than the period. We have to adjust priorities for that, and we have to apply constraints that are appropriate for the deadline rather than period. So Neil and Alan Burns like this and said, "Well, we could have a new feasibility tests, and we can say for all services 1n. Let's look at the computational requirements or capacity over the deadline rather than the period and see if that plus the interference that occurs from higher-prior services is less than 100 percent." Remember, the higher priorities are going to be services that have a shorter deadline rather than a shorter period. That's just a simple modification. Well, the difficult part is the I_i as you might have guessed. So their first try was sum all the higher priority service occurrences, so this is the number of occurrences of higher priority services based on their deadline that occur over D_i. So this T_j is on the higher priority service periods. So remember priority is used to determine the request rate. Deadlines is going to determine the constraint for success or failure. Multiply that by their required CPU, and that's going to be the interference. That seems quite reasonable. It turns out that this ceiling term, D_i over T_j is a worst-case number of releases for S_j over S_i. So it over-accounts for interference, a problem very similar to the rate monotonic least upper bound. So they tried again, and they tried to account for partial interferences, whether a partial interference occurred or not. So either it occurred or didn't. Then when it did, when it was a partial interference, how long was the partial interference? Unfortunately, this was shown to still not be exact. It's order n squared, which is nice, but it's unfortunately, not exact. It's really not a significant improvement over the RM LUB. In fact, what I would recommend is just do worst-case analysis the way we always do. But look at deadlines that can be earlier, so they've got four, which is earlier than five here and look at deadlines that can be later 20 compared to 13 and simply do your analysis. Remember, the policy is slightly different. The priorities are assigned according to the shortest period. In this case, we haven't changed them enough that it changes the order of priorities between S1 and S4. We still have S1 higher than two higher than three, higher than four here, based on 2, 5, 7, 13. Here we have 2, 4, 7, 20. We really just need to adjust the constraint check in this scenario rather than adjusting the priorities, but we could do both, certainly. Then we'd go through the scheduling, basically a scheduling simulation with worst-case analysis as before, filling these in as we have many times before with rate-monotonic worst-case analysis. The big difference is that when we go to determine whether we have success or failure in DM than at down here compared to RM is that here you can see that our deadline is allowed to have this overlapping zone where two requests for the same service are active at the same time and the criteria for success on S4, which uses two units of time rather than having a miss right here, so this is the question. This would be a miss in rate-monotonic up here and over here. It's okay because we're going to extend that deadline out and say "This is okay." Okay in deadline monotonic, not okay in rate-monotonic, and it's just by comparing to a different constraint. You notice I've got a red arrow indicating the deadline interval and I've got a blue arrow indicating the period interval. They're always the same in rate-monotonic, but down here, they can be different. We've got this difference here. We just have to check the constraint with a new value. In the case of shorter, so we have S2 and its deadline is shorter than its period. Well, that just means this has to get done before this deadline rather than over here and it won't be re-requested still to the period interval occurs the request interval, but we have a constraint that's shorter than the request interval, and so we just have to meet that constraint. It's met here again, it's met here again, it's met here again, it's met again here again, quite readily. It's really that simple. It's just a variation on worst-case analysis for rate-monotonic theory. That's why it didn't really become a new theory. It's basically a fine tuning adjustment made rate-monotonic theory that allows T less than D or T greater than D. That works and it's useful and it's thing you'll find in the rate-monotonic practitioners handbook. Why not use EDF? Jump straight into it where we discussed some practical reasons and we said, it's state of practice to use rate-monotonic for hard real-time, dynamic priority EDF for soft real time. If that doesn't convince you, keep in mind that you'd get this nice simple approximation that can be used for online dynamic admission back at the envelope calculations. It's safe and it has margin and it will fail some things that are in fact feasible, but it's safe. It's nice to have simple rules to determine safety as well as feasibility. If you need exact, just use worst-case analysis as we've done and as we've seen. The question is, what are advantages and disadvantages of EDF? We won't go to them in gory detail now because it's a topic in course 2, but there's no problem with feasibility tests. There are well-known simple feasibility tests in EDF that we have to do over the hyperperiod which can be done. As long as we have a feasibility test, then we have something that we can definitely use. The harder problem is basically prio adjustment online. It's high or overhead for the scheduler. The scheduler basically has to adjust all the priorities for all services anytime there's a change in the ready queue. Anytime something completes execution or anytime something new enters the ready queue, it has to determine a new priority order for everything that's either executing or ready to execute. That has to occur and be updated basically as time passes and we have to unurgent their changes in the urgency. This laxity first is even more complicated. That's also a topic in Course 2. But it's not the feasibility test that is the problem, it's the prior adjustment online is one of the issues. Then the second thing is fail mode. We'd like that to be simple, easy to debug and understand. Because if we enter a failure mode, we have to have recovery, and recovery isn't a periodic type of service or processing. That's complicated and in rate monotonic, we always know everything higher or priority than the over-running service is going to continue to succeed. That's going to be based on frequency. If there's something that's more important, we just do period transform to make it higher-frequency. Everything at the overrun priority level and lower is going to fail. It's simple, so there's recovery modes that we'll talk about in actually Course 3 if they are needed. Those are the main two reasons that as a practitioner, I wouldn't jump into dynamic priorities, unless I have a soft real-time system. Then maybe it's okay to have a complicated failure mode in a little bit more overhead to get maximum scalability and efficient use of your processing infrastructure for something like providing streaming services for Netflix, or someone like that where, miss occasionally missing a deadline just means spinning hourglass for a few seconds and then you catch up for maybe a few customers out of your thousands or millions of customers. It's a soft real-time application by nature. A few final notes on dynamic admission that are interesting. Remember the LUB has an order and test that we can use for online dynamic admission. That's fairly low complexity. It also has an order and cube test that's exact. That's not bad for order and cubed and this is approximate but safe. We can use that for online admission testing. What I think is really interesting about this is that for offline analysis, we just transition from offline to online as we've discussed, the service set can't change, so that's a little rigid. But for online admissions services, we could use either one of these and make it a service on one of our processor cores or perhaps even have a dedicated co-processor that does this. The feasibility test must be run online to retest feasibility of new services before they go online and are essentially assigned a core. The feasibility tests either must be a service on a core or admitted by basically an offline tests that runs on dedicated hardware, a co-proc. We'll talk about this as we complete Course 1. This could be used for basically SMP load balancing with proper feasibility analysis, as services are assigned to cores for the first time or migrated between cores to keep all the processors at a mostly equal workload, balanced. For Migration of services, in essentially requires dynamic admission. That can be quite useful, and it might be helpful to have a low algorithmic complexity estimator for that. Thank you very much. That concludes and I think handles many of the objections by providing work arounds or solutions that are quite useful on rate monotonic theory that you can find more details on in things like the rate monotonic practitioners handbook. We will take a much more detailed look at the problem of secondary, tertiary resource needs in addition to the CPU, that have been essentially the secondary resource problem of shared memory has been solved with priority inheritance or priority ceiling protocol. But the work on rate monotonic theory continues and it's successful in its state of practice now. Thank you very much.
