[MUSIC] Welcome to this module. If you recall from another lesson, we presented a schedulability test for checking the feasibility of a rate-monotonic schedule with periodic tasks. This test could only tell us if a set of tasks has a guaranteed feasibility incase the utilization of the system was below a so called Urm limit. Now in reality, schedules with a utilization between Urm and one can also be feasible. But we need more rigorous tests to evaluate this. And this is exactly what this lesson will be about. So for our next verification method, we want to rely on the same assumptions as in the Urm test, namely that we consider single processor systems, preemptive task and the RM scheduler. So to do this we further more need to consider tasks with response time equal or at most their period. And this is something we refer to as short response times and we need them to define a critical instance of a task as the time interval where the job in Ti is released, as the maximum response time of all the jobs ever released in Ti. If the job released at the critical instant meets the deadline then all the jobs in this task will also meet the deadline. Let's assume to have two tasks, T1 and T2. And the tasks are scheduled with the rate monotonic scheduler and the schedule is given. In this case the longest response time of T2 is 3. And this occurs at time 15 because T2 was interrupted by T1 and then again switched in at time 17. So the critical instant of T2 is therefore 15 because here is where we scheduled the longest T2 job. We denote the maximum response time of a job in a task Ti as Wi. And the response time Wi of a task Ti is equal to the smallest value of T that satisfies the following equation. The equation tells us that the worst response time W of a task i at time T is the execution time of the current running job ei plus the sum of the utilization of the already scheduled jobs k=1 to i-1. Which is described by t divided by the period of the kth job, rounded up to the closest integer and this is multiplied by the execution time of the kth job. So this should then be iterated from zero to pi for a task i. When we're able to determine the critical instant of a task, we can set up a schedulability test to test a system which has the following properties. The rate monotonic scheduler is used, pre-emptive tasks are used, a single processor is used, we have no phases or jitter in the tasks and a set of only periodic jobs. We then consider each task Ti in decreasing priority order. So we start by evaluating the task with the highest priority, which in a rate-monotonic system is the one with the shortest period. If the job is released at the critical instant this zero then the job of the task has a certain time demand. And time demand means how much time a task demands for completion. This time is then compared to the time of execution. And we use as said in the previously defined equation to determine the worse case response time. Concretely, we make the test by computing the time demand function, Wi(t). Then we check if Wi is less than t for all time steps equal to j multiplied by the period pk where j is given with the following equation. If this is true for all Ti then the system is feasible. And when implementing the feasibility test in a runtime system you must also consider the overhead added to the timeline. We can define this by looking at the complexity of the feasibility test. The complexity of time demand analysis is big O(nQ), where Q is the maximum period divided by the minimum period of all tasks. And to determine the response times, declaration must be solved. The first approximation is execution times ei of a task Ti. In other words w0 = ei and this gives Wi(w0) directly Wi(ei). And the algorithms is iterated through wj + 1 = Wi(wi) to account for all the tasks in the system scheduled one by one. In summary, the time demand analysis can tell us if a system with the rate-monotonic scheduler and periodic tasks is schedulable, even if the total utilization is between Urm and 1. So what is done here is that we measured a critical instant of a task which gives us the worst case execution of a task. The time the worst case execution required is compared to the time the system can provide before the deadline. In case all the tasks demand less time than what is provided then the system is feasible. Now, this have been highly theoretical but don't worry, because in other lessons we will take a practical example just to show how this method works in practice.