146 Chapters Priority-Driven Scheduling of Periodic Tasks In summary. Lemmas 6.7-.....-6.10 tell us that the busy interval we examine according to the general time-demand analysis method contains the most number of jobs in T, that can possibly execute in any level-jt,- busy interval. Moreover, the response time of each job in the examined busy interval is larger than the response time of the corresponding job executed in any level-717 busy interval. This is why if we find that none of the examined jobs completes late, we know that no job in 7} will. 6.7 SUFFICIENT SCHEDULABILITY CONDITIONS FOR THE RM AND DM ALGORITHMS When we know the periods and execution times of all'the tasks in an application system, we can use the schedulability test described in the last section to determine whether the system is schedulable according to the given fixed-priority algorithm. However, before we have completed the design of the application system, some of these parameters may not be known. In fact, the design process invariably involves the trading of these parameters against each other. We may want to vary the periods and execution times of some tasks within some range of values for which the system remains feasible in order to improve some aspects of the system. For this pur-pose, it is desirable to have a schedulability condition similar to the ones given by Theorems 6.1 and 6.2 for the EDF and the LST algorithms. These schedulability conditions give us a flexible design guideline for the choices of the periods and execution times of tasks. The schedulable utilizations presented in this section give us similar schedulability conditions for systems scheduled according to the RM or DM algorithms. An acceptance test based on such a schedulable utilization can decide whether to accept or reject a new periodic task in constant time. In contrast, the more accurate time-demand analysis test takes 0(nq„j) time; moreover, the accurate test is less robust because its result is sensitive to the values of periods and execution times. 6.7.1 Schedulable Utilization of the RM Algorithm for Tasks with Dt = />,• Specifically, the following theorem from [LiLa] gives us a schedulable utilization of the RM algorithm. We again focus on the case when the relative deadline of every task is equal to its period. For such systems, the RM and DM algorithms are identical. Theorem 6.11. A system of n independent, preemptable periodic tasks with relative deadlines equal to their respective periods can be feasibly scheduled on a processor according to the RM algorithm if its total utilization U is less than or equal to Urm(k) — n(21!" - 1) (6.10) Ul(M(n) is the schedulable utilization of the RM algorithm when Dt — pt for all 1 < k < n. Figure 6—14 shows its value as a function of the number n of tasks in the set. When n is equal to 2, U RM («) is equal to 0.828. It approaches In 2 (0.693), shown by the dashed line, for large n. Specifically, U (n) < UrmQ1) is a sufficient schedulability condition for any system of n independent, preemptable tasks that have relative deadlines equal to their respective periods to be schedulable rate-monotonically. (We use the notation U (n) in place of U in our subsequent discussion whenever we want to bring the number of tasks n to our attention.) As long as Section 6.7 Sufficient Schedulability Conditions for the RM and DM Algorithms 147 1.0 r URM(n") o.8 - 0.7 :___ 0.6-1----1-1-i_i.______i_i_i_____i 2 4 6 8 10 12 14 16 IS 20 n FIGURE 6-14 URi,(n) as a function n. \ i I the total utilization of such a system satisfies this condition, it will never miss any deadline. In particular, we can reach this-conclusion without considering the individual values of the phases, periods, and execution times. I As an example, we consider the system T of 5 tasks: (1.0, 0.25), (1.25, 0.1), (1.5, 0.3), ■ (1-75. 0.07), and (2.0, 0.1). Their utilizations are 0.25, 0.08, 0.2, 0.04, and 0.05. The total uti- ; lization is 0.62, which is less than 0.743, the value of UKM (5). Consequently, we can conclude J that we can feasibly schedule T rate-monotonically. Suppose that the system is later enhanced. • As a result, the tasks are modified, and the resultant tasks are (0.3, 1.3, 0.1), (1.0, 1.5, 0.3), (1.75, 0.1), (2.0, 0.1). and (7.0, 2.45). Since their total utilization is 0.737, which is still less than 0.743, we know for sure that the system remains schedulable. There is no need for us to do the more complex time-demand analysis to verify this fact. On the other hand, suppose ; that to make the above five-task system more modular, we divide the task with period 7.0 into j three smaller tasks with periods 5, 6, and 7, while keeping the total utilization of the system at i 0.737. We can no longer use this condition to assure ourselves that the system is schedulable j because URM(1) is 0.724 and the total utilization of the system exceeds this bound, j Since U(n) < URM(n) is not a necessary condition, a system of tasks may nevertheless \ be schedulable even when its total utilization exceeds the schedulable bound. For example, j the total utilization of the system with the four tasks (3, 1), (5, 1.5), (7, 1.25), and (9, 0.5) ; >s 0.85, which is larger than UKM(4) = 0.757. Earlier in Figure 6-9, we have shown by the • time-demand analysis method that this system is schedulable according to the RM algorithm, i ; *6.7.2 Proof of Theorem 6.11 : While the schedulable utilization of the EDF algorithm given by Theorem 6.1 is intuitively ; obvious, the schedulable utilization URM{n) given by Theorem 6.11 is not. We now present ; an informal proof of this theorem in order to gain some insight into why it is so. The proof first shows that the theorem is true for the special case where the longest period p„ is less than or equal to two times the shortest period p\. After the truth of the • theorem is established for this special case, we then show that the theorem remains true when Chapter 6 Priority-Driven Scheduling of Periodic Tasks this restriction is removed. As before, we assume that the priorities of all tasks are distinct. Here, this means that p\ < p2 < ■ ■ ■ < pn- Proof for the Case of p„ < 2p\. The proof for the case where p„ < 2p\ consists of the four steps that are described below. Their goal is to find the most difficult-to-schedule system of n tasks among all possible combinations of n tasks that are difiicult-to-schedule rate-monotonically. We say that a system is difficult to schedule if it is schedulable according to the RM algorithm, but it fully utilizes the processor for some interval of time so that any increase in the execution time or decrease in the period of some task will make the system unschedulable. The system sought here is the most difficult in the sense that its total utilization is the smallest among all difflcult-to-schedule n-task systems. The total utilization of this system is the schedulable utilization of the RM algorithm, and any system with a total utilization smaller than this value is surely schedulable. Each of the following steps leads us closer to this system and the value of its total utilization. Step 1: In the first step, we identify the phases of the tasks in the most difficult-to-schedule system. For this we rely on Theorem 6.5. You recall that according to that theorem, a job has its maximum possible response time if it is released at the same time as a job in every higher-priority task. The most difficult-to-schedule system must have one or more in-phase busy intervals. Therefore, in the search for this system, we only need to look for it among in-phase systems. Step 2: In the second step, we choose a relationship among the periods and execution times and hypothesize that the parameters of the most difficult-to-schedule system of n tasks are thus related. In the next step, we will verify that this hypothesis is true. Again from Theorem 6.5, we know that in making this choice, we can confine our attention to the first period of every task. To ensure that the system is schedulable, we only need to make sure that the first job of every task completes by the end of the first period of the task. Moreover, the parameters are such that the tasks keep the processor busy once some task begins execution, say at time 0. until at least pn, the end of the first period of the lowest priority task T„. The combination of n periods and execution times given by the pattern in Figure 6-15 meets these criteria. By construction, any system of n tasks whose execution times are related to their periods in this way is schedulable. It is easy to see that any increase in execution time of any task makes this system unschedulable. Hence systems whose parameters satisfy this relationship are difficult to schedule. Expressing analytically the dependencies of execution times on the periods of tasks that are given by Figure 6-15, we have (6.11a) Pk+\ - Pk fork = 1,2, 1 Since each of the other tasks execute twice from 0 to p„ the execution time of the lowest priority task T„ is n-1 e„ = p„ 2X> (6.11k) Step 3: We now show that the total utilization of any difficult-to-schedule n-task system whose execution times are not related to their periods according to Eq. (6.11) is larger than or equal to the total utilization of any system whose periods and execution times are thus Section 6.7 Sufficient Schedulability Conditions for the RM and DM Algorithms 149 To T, n-l PI 4>1 P3 Pn-l PI Pn FIGURE 6-15 Relationship among parameters of difficult-to-schedule tasks. related. Since we are looking for the difiicult-to-schedule system with the least total utilization, we need not consider any system whose parameters are not thus related. To do so. we construct new systems, whose parameters do not satisfy Eq. (6.11), from an original system whose parameters satisfy Eq. (6.11). There are two ways to do this. One way is by increasing the execution time of a higher-priority task from the value given by Eq. (6.11) by a small amount e > 0. Without loss of generality, let this task be TV In other words, in the new system, the execution time e'\ of T\ is equal to e\ = p2 - p\ + s — e\ + s For the new system to be schedulable, some other task must have a smaller execution time. From Figure 6-15, we see that the first job in every task can complete in time if we let the execution time of any other task be s units less than the value given by Eq. (6.11a). Suppose that we choose Tk, for some k / 1, to be this task and make its new execution time equal to e'k = ek-s The execution times of the tasks other than T{ and Tk are still given by Eq. (6.11). The new system still keeps the processor busy in the interval (0, p,,]. The difference between the total utilization U' of the new system and the total utilization U of the original system is U' -U Pi Pk P\ Pk s Pi s Pk 150 Chapter 6 Priority-Driven Scheduling of Periodic iasks Section 6.7 Sufficient Schedulabiiity Conditions for the RM and DM Algorithms 151 Since p\ < /?/,-. this difference is positive, and the total utilization of the new system is larger. (You may want to convince yourself that we would reach the same conclusion if in the construction of the new system, we make the execution time of some task other than T\ larger by s units and make the execution times of one or more tasks with priorities lower than this task smaller by a total of s units.) Another way to construct a new difficult-to-schedule system from the original one is to let the execution time of a higher-priority task be s units smaller than the value given by Eq. (6.11). Again, suppose that we choose T\ to he this task, that is, its new execution time is e'l = pi - P\ -e From Figure 6-15, we see that if we. do not increase the execution time of some other task, the processor will be idle for a total of 2s units of time in (0, p„\. To keep the processor busy throughout this interval and the system schedulable, we can increase the execution time of any of the other tasks by 2s units, that is, ek = ek + 2s for some k ^ 1. It is easy to see that with this increase accompanying the decrease in the execution time of T\, the first job of every task in the new system can still complete by its deadline and the processor never idles from 0 to p„. Comparing the total utilization U" of this new system with that of the original system, we find that 2s s U" -U =--- Pk Pi Since pk < 2p\ for all k j= 1, this difference is never negative. (Again, we could also divide the 2e units of time arbitrarily among the n — 1 lower-priority tasks and get a new system with a total utilization larger than or equal to U.) Step 4: As a result of step 3, we know that the parameters of the most difficult-to-schedule system of tasks must be related according to Eq. (6.11). To express the total utilization of a system whose parameters are given by Eq. (6.11) in terms of periods of the tasks in it, we substitute Eq. (6.11) into the sum XTt=i e>J'Pk and thus obtain 2 U(n) — c/2.1 +53,2 H-----'r q„Au-\) H---n (6.12) 12.1(73,2 ■ • - In,(h-1'1 where qk;, for k > is the ratio of the larger period pi- to the smaller period /?,, that is, Ik.i = Pk/Pi- In particular, the total utilization of any //-task system whose parameters are related according to Eq. (6.11) is a function of the // — 1 adjacent period ratios qi.+t.k for k = 1.2, ...,« - 1. This equation shows that U(n) is a symmetrical convex function of the adjacent period ratios, it has a unique minimum, and this minimum is the schedulable utilization UrmUi) of the RM algorithm. To find the minimum, we take the partial derivative of U(ii) with respect to each adjacent period ratio qk+i.k and set the derivative to 0. This gives us the following n — 1 equation: 2 ,--_-=0 qi.\q?.2 ■ ■ -qa+\).r, ■ ■ -<7».(»-i) for all k = 1, 2, .... n - 1. Solving these equations for Qk+i.k- we find that 1700 is at its minimum when all the u — i adjacent period ratios qu+\.k are equal to 2'-''". Their product qi.\qy.i... q„A„-\\ is the ration,, i of the largest period p„ to the smallest period p \. This ratio, being equal to 2<""1,/", satisfies the constraint that pn < 2p\. Substituting q<;+\.k = 21/" into the right-hand side of Eq. (6.12), we get the expression of U(«) given by Theorem 6.11. For more insight, let us look at the special case where n is equal to 3. The total utilization of any difficult-to-schedule system whose parameters are related according to Eq. (6.11) is given by i U(3) = q-> \+q^ +H--=--3 17(3) is a convex function off/2.1 and qy,. Its minimum value occurs at the point q2. \ — qxz — 2l;'-\ which is equal to 1.26. In other words, the periods of the tasks in the most difficult-to-schedule three-task system are such that />3 = \.26pn = 1.59pi. Generalization to Arbitrary Period Ratios. The ratio q„,\ = p,,/pi is the period ratio of the system. To complete the proof of Theorem 6.11, we must show that any //-task system whose total utilization is 110 greater than Urm(n) is schedulable rate-monotonically, not just systems whose period ratios are less than or equal to 2. We do so by showing that the following two facts are true. 1. Corresponding to every difficult-to-schedule n-task system whose period ratio is larger than 2 there is a difficult-to-schedule //-task system whose period ratio is less than or equal to 2. 2. The total utilization of the system with period ratio larger than 2 is larger than the total utilization of the corresponding system whose period ratio is less than or equal to 2. Therefore, the restriction of period ratio being equal to or less than 2, which we imposed earlier in steps 1-4, leads to no loss of generality. We show that fact 1 is true by construction. The construction starts with any difficult-to-schedule 7i-task system {7} = (/?,-, e;)} whose period ratio is larger than 2 and step-by-step transforms it into a system with a period ratio less than or equal to 2. Specifically, in each step, we find a task Tk whose period is such that lpk < p„ < (l + \)pk where / is an integer equal to or larger than 2; the transformation completes when no such task can be found. In this step, we modify only this task and the task T„ with the largest period p„. Tk is transformed into a new task whose period is equal to lpk and whose execution time is equal to ek. The period of the task with period p„ is unchanged, but its execution time is increased by (/ — ] )«U + u„) < 2pi Combining these two expressions, we have the following corollary. COROLLARY 6.12. n independent, precmptabic periodic tasks with relative deadlines equal to their respective periods are schedulable rate-monotonicaJly if their utilizations u\ . '.'2, - - ■, u„ satisfy the inequality (1 + «i)íl -I- u2) ■ - • (1 + ti„) < 2 if, IT) We denote the total utilization of the tasks whose utilizations satisfy the constraint Eq. (6.13) by C//>,w(;i|, h2,____ii„). As an example, we consider a system of two tasks Ti and T2. The schedulable utilization Urm{u\, «2) of the system is equal to 0.957, 0.899, 0.861, and 0.828, respectively, when the ratio u\/U of the utilization of Z'j to the total utilization of both tasks is equal to 0.05, 0.1, 0.25, and 0.5. The minimum of U(ui, ui) is at the point u\ = 0.5U (i.e., when «, = u2) and is 0.828, the Liu and Layland bound for n equal to 2. For arbitrary n, the inequality Eq. (6.13) becomes (1 +U(n)/si)" < 2 when the utilizations of all the tasks are equal. For this combination of utilizations, the inequality Eq. (6.13.) becomes the same as the Liu and Layland bound U(ii) < n(2,/" - 1). Schedulable Utilization of Subsets of Simply Periodic Tasks. We now consider a system of periodic tasks that are not simply periodic but can be partitioned into n,, subsets of simply periodic tasks. For example, we can partition the system T of tasks with periods 4, 7, 8, 14, 16, 28. 32. 56, and 64 into two subsets Z| and Z... Z| contains the tasks with period 4, 8, 16, 32, and 64; and Z2 contains tasks with periods 7, 14. 28, and 56. Let U(Zi) and U(Zn) denote the total utilization of the tasks in Zi and Z2, respectively. Kuo, et al. [KuMo91] have shown that if t/(Z,; + U(Z2) < 0.828 [i.e., URM{2)\. all these tasks are schedulable rate-monotonically. In contrast, if we were to treat the tasks separately, we would have to use the bound URM(9), which is only 0.712. The following theorem by Kuo, et al. [KuMo91] states this fact in general. theorem 6.13. If a system t of independent, preemptable periodic tasks, whose relative deadlines are equal to their respective periods, can be partitioned into;:/, disjoint