Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks

In this model, recurrent processes are represented as sporadic tasks ${\tau }_i=(C_i,D_i,T_i)$. Each task has three defining characteristics: worst-case execution requirement (WCET) $C_i$, relative deadline $D_i$, and period (minimum inter-arrival duration) $T_i$. The sporadic task ${\tau }_i$ generates a series of jobs, with inter-arrival times of at least $T_i$. Each job must be completed within a scheduling window, which starts at the job’s release time and ends $D_i$ time units later, and the job’s execution time is limited to $C_i$ units. A sporadic task system $\mathrm{\Gamma }$ is made up of multiple independent sporadic tasks. We assume without loss of generality that tasks are indexed in non-decreasing relative deadline order (i.e., if then $D_i\le D_j$).

The limited-preemption sporadic task model, as introduced by Baruah et al. [4], adds to the task specification ${\tau }_i=(C_i,D_i,T_i,{\beta }_i)$ a chunk-size parameter ${\beta }_i$ in addition to the regular parameters $C_i$, $D_i$, and $T_i$. This parameter ${\beta }_i$ indicates that each job of task ${\tau }_i$ may need to execute non-preemptively for up to ${\beta }_i$ time units.

To schedule tasks in the limited-preemption sporadic task model, the limited-preemption EDF scheduling algorithm was proposed [4, 9]. Like its preemptive counterpart, the limited-preemption EDF algorithm prioritizes jobs based on their (absolute) deadlines. If a job of task ${\tau }_i$ with remaining execution time $e$ is executing and a new job with an earlier deadline arrives, then ${\tau }_i$’s job may execute for an additional $\min (e,{\beta }_i)$ time units before incurring a preemption.

Baruah and Bertogna [4, 9] showed that a task system is not schedulable under the limited-preemption EDF model if and only if either of the following conditions are true:

or

Noting that ${\text{dbf}}_i(L)=0$ when , we combine and invert the two conditions, giving a necessary and sufficient condition for successfully scheduling a limited-preemption sporadic task system $\mathrm{\Gamma }$ upon a single preemptive processor using the limited-preemption EDF algorithm:

Unlike the exact test for preemptive uniprocessor EDF-schedulability (Equation 2), Equation 6 contains an additional term on the left-hand side of the inequality that accounts for blocking due to later-deadline (and hence lower-priority) jobs. Specifically, the ${\max }_{{\tau }_i|D_i>L}{\beta }_i$ term is a blocking term that captures the potential delay caused by lower-priority jobs that were already executing at the start of the interval, for a duration of up to their chunk size. Since we assume that all tasks have non-negative execution time, this blocking term is always non-negative.

In this extension to the prior work in [3], we use a continuous-time representation of the blocking term in Equation 6. The prior work used a discrete-time representation, ${\max }_{{\tau }_i|D_i>L}{\beta }_i-1$, which requires both task periods and execution times to be represented as integers. This introduces several challenges. First, it is more difficult to reason about the effect of inserting preemption points; blocking times (chunk sizes) must also be represented as integers, but the number of “chunks” might not evenly divide the execution time. Second, there is a tradeoff when choosing the precision at which to represent execution time units. If the unit of time is coarse, then the execution time of each phase and its corresponding startup/teardown time must be rounded up. If the unit of time is very short – such as a single processor tick – to achieve higher precision, then the testing set grows rapidly as the representations of the task periods become larger. By using continuous time, this extension removes these limitations, and modifies the expression to allow execution times to take any non-negative real value.

Based on this observation, the Processor Demand Analysis (PDA) algorithm has been extended to apply to limited-preemption systems as well [4]. The extension is straightforward: Equation 6 replaces Equation 2 in the algorithm, and the algorithm proceeds as usual.

However, we note that Expression 6 cannot hold true for values of $L$ of the form

where $D_{\min }={\min }_i\{D_i\}$, suggesting incorrectly that a set of tasks is not EDF schedulable if any task has non-zero blocking time. In the next section of this extension, we present a corrected condition that addresses this issue, which we then apply to scheduling of MPS tasks in Section 4.

As discussed in the prior section, in [4, 9], Baruah and Bertogna claimed as a necessary and sufficient condition for scheduling a limited-preemption sporadic task system upon a single preemptive processor using EDF that

where ${\beta }_i$ is the blocking due to limited preemption induced by task ${\tau }_i$.

From the definition of the demand bound function ${\text{dbf}}_i(L)$ in Equation 1, we observe that ${\text{dbf}}_i(L)=0$ for . Then for (i.e., for all tasks ${\tau }_i$), the above condition requires $L\ge {\max }_{{\tau }_i|D_i>L}\{{\beta }_i\}$; as we are already considering the case that , this can be simplified to $L\ge {\max }_{{\tau }_i}\{{\beta }_i\}$.

This implies that for values of $L$ such that , the above condition cannot hold true if $L$ does not also exceed ${\beta }_i$ for all tasks ${\tau }_i$. More simply, the condition cannot hold true for values of $L$ of the form shown in Expression 7. Because processor demand analysis requires that the condition hold true for all values of $L\ge 0$, this would deem any set of limited-preemption tasks with non-zero blocking time to be unschedulable by EDF.

As this is obviously not true – i.e., there are limited-preemption task sets that are schedulable by EDF, we now set out to correct the above condition. We do so by pointing out a subtlety to the proof in [4] of the condition in Expression 6.

That proof constructs the blocking time condition by defining a minimal unschedulable set of jobs for which $t_a$ represents the earliest arrival time of those jobs and $t_f$ is the time at which the first deadline miss occurs. Additionally, for each job ${\tau }_i$, it defines $q_i$ as representing an upper bound on the time for which ${\tau }_i$ can execute non-preemptively. In this system, there is exactly one job with a deadline after $t_f$; we let ${\tau }_j$ be the task that generates this job. If $t_1$ is the time at which that job begins to execute non-preemptively and $t_2$ is when it stops executing, then [4, Equation 4] states that

As $q_j$ is a bound on the non-preemptive execution time, the proof in [4] then claims that $t_2-t_1\le q_j$. We observe that since $t_2\le t_f$, it also follows that $t_2-t_1\le t_f-t_1$. We can therefore combine these inequalities to make the statement that $t_2-t_1\le \min (q_j,t_f-t_1)$. In light of this, we modify the rest of the proof in [4]. Now, it follows that

We then replace the expression $t_f-t_1$ with a time $L$. Since , it follows that ; the dbf of ${\tau }_j$ will therefore be zero at $L$ and we can rewrite the condition as:

This condition checks whether some task ${\tau }_j$ causes excessive blocking at times ; to determine if the system is schedulable, we can therefore test whether the following condition holds for any task ${\tau }_i$ at any time $L\ge 0$, considering blocking times from just those tasks for which :

Then when , the dbf for each task is $0$, so the condition will always be satisfied. Furthermore, when $L\ge D_{\min }$, ${\sum }_i\text{dbf}(L_i)>0$, and so the condition cannot be satisfied when $\min (L,{\max }_i{\beta }_i)\ge L$. We can therefore begin the testing set of our implementation at $D_{\min }$, and only check the blocking time when determining whether the condition is violated.

We have a task system $\mathrm{\Gamma }$ comprising $N$ independent recurrent tasks ${\tau }_1,{\tau }_2,\mathrm{\dots },{\tau }_N$, to be scheduled upon a single preemptive processor. The task ${\tau }_i$ is characterized by a period/inter-arrival separation parameter $T_i$ and a relative deadline $D_i\le T_i$ . The body of the task – the work that must be executed each time the task is invoked – comprises $n_i$ phases, denoted $v_{i,1},v_{i,2},\mathrm{\dots },v_{i,n_i}$, that must execute in sequence upon each job release of the task:

As previously discussed, we assume that successive phases are required to execute using different security mechanisms (i.e., $v_{i,j}$ and $v_{i,j+1}$ execute using different security mechanisms for all $j$, ). Let $c(v_{i,j})$ denote the WCET of phase $v_{i,j}$, and $q(v_{i,j})$ denote the sum of the startup cost and the teardown cost associated with the security mechanism within which phase $v_{i,j}$ is to execute. The aggregate WCET of all phases of this task during its execution is thus given by the following expression

However, suppose that during some execution of task ${\tau }_i$ the $j$’th phase is preempted $k_j$ times for each $j$, $1\le j\le n_i$; as discussed above (Equation 10), the cumulative WCET of all phases of this task during this execution is then given by the expression

The figure below depicts a 2-phase job, denoted by $v_{i,1}$ and $v_{i,2}$, which is preempted once in the first phase and twice in the second phase. The shaded region denotes the startup and teardown costs for each phase of the job.

Given a task system $\mathrm{\Gamma }$ comprising multiple independent MPS tasks to be scheduled upon a single preemptive processor, we will first execute a schedulability analysis algorithm to determine whether this system is schedulable, i.e., whether we can guarantee to schedule it to always meet all deadlines, despite the costs incurred by startup/teardown. This schedulability analysis algorithm essentially constructs a limited-preemption task $\widehat{{\tau }_i}$ corresponding to each task ${\tau }_i$, and determines whether the resulting limited-preemption task system can be scheduled by the limited-preemption EDF scheduling algorithm [4, 9] to always meet all deadlines. If so, then during run-time the original task system is scheduled using the limited-preemption EDF scheduling algorithm, with chunk-sizes as determined for the corresponding constructed limited-preemption tasks. We point out that if a chunk-size ${\beta }_i$ is determined for the limited-preemption task $\widehat{{\tau }_i}$, then the $j$’th phase of ${\tau }_i$’s jobs will execute in no more than $\lceil c(v_{i,j})/({\beta }_i-q(v_{i,j}))\rceil$ contiguous time-intervals (i.e., it would experience at most $(\lceil c(v_{i,j})/({\beta }_i-q(v_{i,j}))\rceil -1)$ preemptions); equivalently, the cumulative WCET of all the phases of each of task ${\tau }_i$’s jobs will be no more than

We now describe our schedulability test. As discussed above, our approach is to construct for each task ${\tau }_i$ a corresponding limited-preemption task $\widehat{{\tau }_i}$. This limited-preemption task is assigned the same relative deadline parameter value (i.e., $D_i$) and the same period parameter value (i.e., $T_i$) as ${\tau }_i$; its WCET $\widehat{C_i}$ and its chunk-size parameter ${\beta }_i$ are computed as described below, and in pseudo-code form in Algorithm 1.

We introduce integer variables $\text{cnt}(v_{i,j})$ for each $i$, $1\le i\le n$, and for each $j$, $1\le j\le n_i$, to denote the maximum number of contiguous time-intervals in which the $j$’th phase of ${\tau }_i$ may need to execute. Then $\widehat{C_i}$, the WCET of each job of task $\widehat{{\tau }_i}$, can be written as

where the second term within the summation represents the maximum preemption overhead (the startup cost plus the teardown cost) that is incurred by the $j$’th phase of task ${\tau }_i$.

It remains to specify the values we will assign to the $\text{cnt}(v_{i,j})$ variables. We will start out assuming that each phase of each task ${\tau }_i$ executes non-preemptively – i.e., in one contiguous time-interval. We do this by initially assigning each $\text{cnt}(v_{i,j})$ the value $1$; we will describe below how the $\text{cnt}(v_{i,j})$ values are updated if enforcing such non-preemptive execution may cause deadlines to be missed. With each $\text{cnt}(v_{i,j})$ assigned the value $1$, it is evident that the largest duration for which task ${\tau }_i$ will execute non-preemptively is equal to ${\max }_{j=1}^{n_i}\left\{c(v_{i,j})+q(v_{i,j})\right\}$; we initialize the chunk-size parameters – the ${\beta }_i$ values – accordingly: for each task ${\tau }_i$,

In this manner, we have instantiated the parameters for one limited-preemption task $\widehat{{\tau }_i}$ corresponding to each task $\tau \in \mathrm{\Gamma }$. We must now check whether the limited-preemption task system $\widehat{\mathrm{\Gamma }}=\{\widehat{{\tau }_1},\widehat{{\tau }_2},\mathrm{\dots },\widehat{{\tau }_N}\}$ so obtained is schedulable using the limited-preemption EDF scheduling algorithm [4, 9]. We do so by checking whether Equation 9 holds for values of $t$ in the testing set $𝒯(\widehat{\mathrm{\Gamma }})$, considered in increasing order; we motivate this ordering below in (5). First, we split $𝒯(\widehat{\mathrm{\Gamma }})$ into two sets, $𝒯{(\widehat{\mathrm{\Gamma }})}_1$ containing all values up to and including $D_{\max }\equiv {\max }_{{\tau }_i}{D}_i$, and $𝒯{(\widehat{\mathrm{\Gamma }})}_2$ containing all values thereafter. Then, we initialize $t_d$ to denote the smallest value in $𝒯{(\widehat{\mathrm{\Gamma }})}_1$, and perform the following steps.

1. 1.

   If Equation 9 is satisfied for $t_d$, we set $t_d$ to be the next-smallest value in $𝒯{(\widehat{\mathrm{\Gamma }})}_1$, and repeat this step.

2. 2.

   If Equation 9 is violated for $t_d$ and the first term in the LHS of Equation 9 is $>t_d$, then we conclude that the system is not schedulable and return.

   Suppose, however, that a violation of Equation 9 occurs due to the blocking term in Equation 9. That is, the first term in the LHS of Equation 9 is $\le t_d$ when Equation 9 is instantiated with $t\leftarrow t_d$, but the sum of the first and second terms exceeds $t_d$. For this to happen, it must be the case that some ${\widehat{\tau }}_i$ with $D_i>t_d$ is blocking ‘too much;’ we must reduce the amount of blocking each such task can cause (i.e., reduce its ${\beta }_i$ parameter). Below, we describe how to do so.

3. 3.

   Let $\mathrm{\Delta }(t_d)$ denote the amount of blocking that can be tolerated at $t_d$ without causing a deadline miss:

   $$\mathrm{\Delta }(t_d)\stackrel{\text{def}}{=}{t}_d-\sum _{\widehat{{\tau }_k}\in \widehat{\mathrm{\Gamma }}}\text{dbf}(\widehat{{\tau }_k},t_d)$$

   (13)

   As discussed above, each $\widehat{{\tau }_i}$ with $D_i>t_d$ must ensure that its blocking term, ${\beta }_i$, is no greater than $\mathrm{\Delta }(t_d)$. For each such task with ${\beta }_i$ currently greater than $\mathrm{\Delta }(t_d)$, we may need to increase $\text{cnt}(v_{i,j})$, the number of contiguous time-intervals in which its $j$’th phase may execute for each of its phases $v_{i,1},v_{i,2},\mathrm{\dots },v_{i,n_i}$, in the following manner:

   $$\text{cnt}(v_{i,j})\leftarrow \underset{\kappa \in \mathbb{N}}{\min }\text{such that}\frac{c(v_{i,j})}{\kappa }+q(v_{i,j})\le \mathrm{\Delta }(t_d)$$

   (14)

   That is, we reduce blocking in order to satisfy Equation 9 for $t_d$ by potentially increasing the number of preemptions (and thereby incurring additional teardown/startup overhead). In prior work [3], we assumed that tasks had integer execution times and hence used ${\beta }_i-1$ as the blocking term; here, we use continuous time and therefore do not subtract a time segment.

4. 4.

   Such additional overhead must be accounted for; this requires that $\widehat{C_i}$, the WCET parameter of the limited-preemption task $\widehat{{\tau }_i}$, must be updated (i.e., potentially increased) by recomputing it using Equation 11 (reproduced below):

   $$\widehat{C_i}\leftarrow \sum _{j=1}^{n_i}\left(c(v_{i,j})+\text{cnt}(v_{i,j})\times q(v_{i,j})\right)$$

   (Notice that since some of the $\text{cnt}(v_{i,j})$ values may have increased, the value of $\widehat{C_i}$ may also increase.)

5. 5.

   Recall that we have been checking the validity of Equation 9 for values of $t_d$ in $𝒯{(\widehat{\mathrm{\Gamma }})}_1$, the partial testing set of $\mathrm{\Gamma }$, considered in increasing order. Since we are currently considering $t_d$, we have therefore already validated that Equation 9 previously held for values of in the testing set. The crucial observation now is that the increase in the value of $\widehat{C_i}$ for any $i$ with $D_i>t_d$ does not invalidate Equation 9 for any , because the increased $\widehat{C_i}$ values only contribute to the cumulative demand (the first term in the LHS of Equation 9) for values of $t\ge t_d$. Hence, we do not need to go back and re-validate Equation 9 for values of $t$ smaller than $t_d$.

6. 6.

   Having thus modified the $\text{cnt}(v_{i,j})$ variables (as in Equation 14) in order to ensure that Equation 9 is satisfied by $\widehat{\mathrm{\Gamma }}$ for $t_d$, we update the value of $t_d$ to the next-smallest value in $𝒯{(\widehat{\mathrm{\Gamma }})}_1$, and return to Step 1 above.

7. 7.

   Once $t_d$ reaches $D_{\max }$, there are no remaining tasks with $D_i>t_d$, and so we are done updating the cnt variables. At this point, we check if the total utilization of the system, ${\sum }_{i=1}^n\frac{WCET({\tau }_i)}{T_i}>1$. If it is, the system cannot be scheduled.

8. 8.

   For an implicit-deadline system with $U\le 1$, we prove in Lemma 2 that the slack will never be at any later time. Therefore, we know that the system is schedulable and can return immediately.

9. 9.

   For a constrained-deadline system, we check the slack at each remaining point $t_d$ in the testing set $𝒯{(\widehat{\mathrm{\Gamma }})}_2$ up to and including the testing set’s upper bound, described by Expression 3. If the slack is found to be , the system is unschedulable, and we return immediately. Otherwise, is system is deemed to be schedulable.

We now provide a more formal description of the conditional MPS sporadic task model. Each task ${\tau }_i$ is characterized by a 3-tuple $(G_i,D_i,T_i)$ where $D_i$ and $T_i$ are the relative deadline and period, and $G_i$ is a DAG: $G_i=(V_i,E_i)$ with $E_i⊊V_i\times V_i$. Each vertex $v_{i,j}\in V_i$ represents a phase of computation, which must execute using a specified security mechanism. The interpretation of each edge $(v_{i,j},v_{i,k})\in E$ depends upon the outdegree (i.e., the number of outgoing edges) of vertex $v_{i,j}$:

1. 1.

   If this outdegree $=1$, then the edge denotes a precedence constraint: vertex $v_{i,k}$ may only begin to execute after vertex $v_{i,j}$ has completed execution.

2. 2.

   If this outdegree is $\ge 2$, then all the outgoing edges from $v_{i,j}$ collectively denote the choices available upon the execution of a conditional construct: after $v_{i,j}$ completes execution, exactly one of the vertices $v_{i,k}$ for which $(v_{i,j},v_{i,k})\in E$ becomes eligible to start executing. It is not known beforehand which one this may be, and different ones may become eligible upon different invocations of the task.

A WCET function $c:V_i\to \mathbb{N}$ is specified, with $c(v_{i,j})$ denoting the WCET of node $v_{i,j}\in V_i$. An overhead function $q:V_i\to \mathbb{N}$ is specified, with $q(v_{i,j})$ denoting the startup/teardown cost associated with the security mechanism using which vertex $v_{i,j}$ is to execute.

In the original model presented in [3], a simplifying assumption was made that teardown and setup costs are always incurred when transitioning between any two jobs, regardless of whether they use the same or different security mechanisms. This assumption was conservative, as it did not account for cases where both jobs use the same security mechanism, in which case the teardown and setup costs would not actually be incurred.

A subtle issue arises when dealing with conditional code, which was not present in the consideration of linear workflows in Section 4. Specifically, during the execution of conditional code, it is not known at compile time which branch will be taken at runtime, and different invocations may take different paths. In hard real-time systems, it is necessary to ensure that tasks meet their deadlines under all possible runtime conditions. Thus, during pre-runtime schedulability analysis, a conservative approach is adopted, assuming that each invocation of the task follows the “longest” path – the one with the maximum cumulative execution requirement.

Standard algorithms are known for identifying the longest path through a DAG that have running time linear in the representation of the DAG. Under limited-preemption scheduling, however, identifying the path through the DAG that has maximum cumulative execution requirement is not entirely straightforward. Let us consider again the example DAG of Figure 1.

• $\mathrm{■}$

  If the chunk size ${\beta }_i$ for this task were $\ge 7$, then both branches can be executed non-preemptively. The upper branch incurs a cost of $5+2=\mathrm{𝟕}$ while for the lower branch the cost is $3+3=\mathrm{𝟔}$; therefore, the upper branch is the computationally more expensive one.

• $\mathrm{■}$

  Now suppose ${\beta }_i=4$. Then the upper branch may need to execute in $\lceil 5/(4-2)\rceil$ or 3 contiguous pieces, for a cumulative cost of $5+3\times 2=\mathrm{𝟏𝟏}$. The lower branch may need to execute in $\lceil 3/(4-3)\rceil$ or 3 contiguous pieces, for a cumulative cost of $3+3\times 3=\mathrm{𝟏𝟐}$, and is hence the more expensive branch.

This example illustrates that the computationally most expensive path through a DAG that represents conditional execution depends upon the value of the chunk size parameter (the ${\beta }_i$ parameter of the task). As we saw in Section 4, the approach to scheduling MPS sporadic tasks has been to convert each task to a limited-preemption sporadic task. The procedure for doing so (Algorithm 1) repeatedly changes the values of the ${\beta }_i$ parameters of the tasks. As we adapt the techniques of Section 4 to schedulability analysis of conditional MPS tasks, it is important to note that the necessary improvements to handle conditional execution, including the correct analysis of teardown and setup costs, have already been addressed in a separate extension paper [38]. In that work, the unnecessary conservatism in the assumption that teardown and setup costs are always incurred during transitions between jobs, regardless of whether they use the same security mechanism is eliminated. This refinement leads to a more precise schedulability analysis, ensuring that only the relevant overheads are considered and optimizing the overall analysis of conditional MPS tasks. Thus, while this paper focuses on the linear task model and its optimization, the more accurate treatment of conditional execution is fully covered in [38].

The evaluation was conducted using a C++ simulation. All tests were performed on a a server with two Intel Xeon Gold 6130 (Skylake) processors running at 2.1 GHz, and with 64GB of memory. Multiple task sets were evaluated in parallel; each task set was given a single thread on which to run. We evaluate task sets for many parameter variations, including the task count, number of phases per task, utilization, and task periods. In some cases, the number of phases per task is fixed; where it is not fixed, we select the number of phases for each task following a uniform distribution in the given range. Task periods are selected either from a uniform distribution within the period range specified for each test or, where specified below, a log-uniform distribution. For each combination of fixed parameters, we generate 1000 random task systems. For each system, we use the UUniFast algorithm [12], first to assign a total utilization $\frac{C_i}{T_i}$ to each task and then to distribute the task’s total allotted time $C_i$ between the execution times $c_{(v_{i,j})}$ and startup/teardown overhead $q_{(v_{i,j}})$ for each of its phases. We note that compared to the prior work in [3] that this paper extends, we have adjusted this distribution to be more consistent and to be independent of the number of phases in the task. We then evaluate each task set against three algorithms: chains, the algorithm presented in section 4, phase NP, in which there is a static preemption point between each phase but no additional preemption points can be inserted, and fully NP, in which the entire task runs as a single non-preemptive chunk.

We evaluate both implicit-deadline and constrained-deadline task systems. In an implicit-deadline system, $D_i=T_i$ for each task. In a constrained-deadline system, we choose a random value for each $D_i$ that is uniformly distributed between the task’s execution time and its period $T_i$. For implicit-deadline systems, we evaluate $U$ at increments of $0.1$ in $[0,1]$. We note that, compared to the prior version of this work in [3], the improvement to the testing set described in Section 4 allows us to evaluate these systems in a reasonable amount of time even for large numbers of tasks; to understand the impact of this optimization, we also test the exponential set presented in the original version on systems with 8 tasks or fewer and compare their execution times. For constrained-deadline systems, the testing set is bounded by a term that is determined in part by a factor $\frac{1}{1-U}$; as $U\to 1$, the testing set size becomes very large and becomes infeasible to evaluate. We therefore limit our evaluation of constrained-deadline systems to utilizations in $[0,0.9]$.

The implementation of the algorithm in our prior work [3] could only evaluate sets of a few tasks in a reasonable amount of time. In this work, we rewrite the original Python-based simulation using C++, and correct an implementation issue with the original construction of the hyperperiod-bounded testing set. These changes lead to significant performance improvements on their own. In Figure 7 we randomly generate and test 50 task sets with either 3 or 4 tasks each; the original implementation is compared to the rewritten one, which is configured to test points in the full, exponentially-sized testing set. For sets of 3 tasks, the median execution time improves by approximately $70\times$ and the mean execution time improves by around $250\times$. For sets of 4 tasks, the median improves by around $150\times$ and the mean execution time by more than $3500\times$. These improvements enable testing larger task sets, as shown in the following sections.

In this work, we also introduce an optimization for implicit-deadline task systems that allows us to avoid testing timepoints past $D_{\max }$. In Figure 9, we analyze the impact of this optimization. Using the full, exponential testing set from the prior work, our implementation is able to test tasksets with 6 tasks in only a few seconds, but the time needed still scales exponentially with the number of tasks; past eight tasks per set, the analysis once again takes an unreasonable amount of time to run. Using the optimization for implicit-deadline systems, evaluating schedulability is orders of magnitude faster, and the evaluation times also become more consistent for each taskset. This optimization allows us to determine the schedulability ratio for systems of up to 20 tasks, the results of which are displayed in Figure 3. As the time needed to determine schedulability now scales much more slowly with respect to the number of tasks, we believe that evaluating even larger task sets is also possible.

In Figure 9, we evaluate the performance of determining schedulability of constrained-deadline task sets using the pseudo-polynomial bound on the testing set identified in [7]. Compared to the full hyperperiod testing set, running the evaluation with this testing set is much faster. However, we note that it is still slower than the optimized implicit-deadline bound from Figure 9. Moreover, the distribution of execution times exhibits high variability. Perhaps most importantly, our evaluation is on task sets where $U=0.9$, at which the pseudo-polynomial bound is still reasonably small. As shown in Figure 10, when $U\to 1$, the size of the pseudo-polynomial set approaches the hyperperiod set, and it becomes increasingly less feasible to iterate over the entire testing set.