Hello. What we want to talk about now is when not to use EDF, when it has no advantage, and when, in fact, it may introduce new challenges. First of all, address when it has no particular advantage, and that's fairly straightforward. When we have harmonic services, as we've seen already, we can achieve 100 percent utility with fixed priorities like rate monotonic. Here's a reminder of that example, for one, where we have harmonic services, and you see what basically happens is that, we have the same schedule for EDF as we have for rate monotonic. There's no particular advantage to computation of urgency, so we're computing this time to deadline, which can be expensive. It requires us constantly determining the time until the deadline each time there's a request for service, for each service that's requested and added it to the ready queue. In fact, on every single change to the ready queue, we need to recompute all these urgencies just like we do when we're doing this by hand analysis. That's tedious, as you know, it's error-prone, it's much more difficult than simply having a fixed set of priorities and dispatching from a priority queue the highest priority at any point in time, which is very simple. They achieve the same result. The question is, what does it buy you? The same can be said for LLF, but we'll address that later. That's the first observation is it makes no sense to use EDF when you have harmonic services. The next observation is, what about in overloads? There's three classic objections to EDF. The one we already covered is that TTD can be expensive. It's higher overhead than fixed priority. That's one of the classic objections, and in some occasions where there are harmonic, not only is it higher overhead, it's higher overhead with no particular advantage. But there are, of course, as we saw in previous examples, cases where services aren't harmonic and they're either above the LUB, or at 100 percent but not at harmonic where EDF does do well. If there's no advantage, then the higher overhead is just a burden. The next objections are maybe a little bit more serious. The second one is what we call domino failure, and this is well documented in many of the papers that I've made optional reading, and we discussed it as a concept in Course 1 in this series. The domino failure can be seen whenever you start to get ties in your urgency, there's a possibility of a domino failure coming up. But actually, the other problem is it's not always 100 percent clear that ties indicate a failure. The third objection we're going to see is called the no warning issue with EDF. What happens is, when we have an overload, first of all, we should point out that in RM, it's very clear what happens, the overload results in the lowest priority services not meeting their deadlines. The higher priority services, as long as they aren't overloaded with respect to each other, which they're not here, we only have 75 percent utility if we look at these two, they should be okay, and S3 should be the one that can't make it because it's the one that pushes this over not only the LUB, but over 100 percent utility. RM has a really nice failure mode there. By comparison, EDF has this domino failure mode. What we mean by that is, as we start to get ties, we could just randomly choose one of the winner. We had a tie here, but we had a clear winner was S1, so that's not as interesting. But here we had a tie, and there's no clear winner, so we could choose S3, and that would lead to eventually S1 missing its deadline, this case here. We could choose S3 again, but then in a future tie, we could choose S1. This is one of the three factorial options, and that would lead to case B. We could also make a selection where we choose essentially S2 on the first tie, and then after that we choose S1, and that would lead to this final case. It creates this domino cascading looking failure potential. That of course, is not ideal. I actually have a simple solution that I use, which is, whenever there is a tie, I always favor the highest priority service. That tends to force failures that are more like rate monotonic. It helps. But it's still not clear that in all scenarios, you're going to be able to exactly predict who's going to fail and who's not. There's some more complicated examples where you can still have one of the highest frequency services fail in EDF, even if you use my method of always choosing the highest frequency in the case of ties. Ties unfortunately, don't perfectly predict miss deadlines. They're perhaps indicative of upcoming deadline issues, like we have here. We've got three services with the tie of two, and we've got three periods ending into time windows. That's, as a human, we can see that and we can say that that's trouble. But it's difficult to check in a simple manner, when this would be true. We don't have anything like a negative value for our heuristic or anything like that. We've got this domino failure mode or this mode where any one of our three services could fail depending upon the scenario. We don't know which of the three. In fact, it can basically go between the three depending on how we handle ties in general with EDF. There's no warning. If there was a warning, perhaps we could drop one of the services to force the failure mode into a specific, more deterministic kind of failure mode. But we just don't have that with EDF. Actually, that has been one of the motivations for least lacks the first, also known as least slack first, which we're going to talk about as well. Take a look at this. You may also want to look at more complicated examples with overload, so to convince yourself that it's difficult to know what's going to happen. Here's a much more complicated one, where with rate-monotonic it's always S3 that misses. But unfortunately with EDF, we can have S1, have a miss here, early on with S3 making its deadline on the first major period. S1 missing, and then S3 missing and so on and so forth. Then we get all sorts of ties, which again, like we said, can lead to all sorts of potential randomness in terms of which service is going to fail. We can try to minimize that by having some clear policy for how to handle ties. But you can see that wouldn't have helped us over here in that. We didn't even have any ties and we had S1 fail. That's a significant downside to EDF. Again, the three main reasons that EDF has objections, because otherwise it's optimal and we've seen that it has lots of advantages, is just the higher overhead of time to deadline to compute that. The domino failure mode and the no warning feature of the heuristic. On that note, we'll leave you to think about when you would use EDF. My suggestion is to limit use to soft real-time. There are different positions on that. One of the optional papers you can read is by [inaudible] who suggests that deadline driven is a better policy, because it's adaptive and other reasons, many other reasons. But one of the things that you would want to be careful about and want to address is this failure mode and this no warning issue in overload scenarios. When you're with dynamic priorities where you're running either low or zero margin, this is much more possible that you're going to have at least a transient overload that you might have to recover from. That's the reason that I would be careful with it compared to rate monotonic. Thank you very much.
