Theoretical Foundations of Utility Accrual for Real-Time Systems

We consider a soft real-time system which can tolerate occasional deadline misses. We focus on one periodic real-time task $\tau$, which is serviced by a greedy processing component (GPC) [60] in a uniprocessor system.

The periodic soft real-time task $\tau$ is modeled by a tuple $(T,D,C)$, where $T>0$ is its period, $D>0$ is its relative deadline, and $C$ is a random variable that describes the execution time. The task $\tau$ releases an infinite number task instances, called jobs, where its $j$-th job is denoted by $J_j$. The first job is assumed to be released at time $0$. Hence, job $J_j$ is released at time $(j-1)T$ and its absolute deadline is $(j-1)T+D$.

We assume $C$ follows a discrete distribution; that is, $C$ has $h\ge 1$ distinct values each with a related probability. The probability that a random variable $X$ is equal to $x$ is denoted as $\mathbb{P}(X=x)$. The actual execution time of job $J_j$ is assumed to be one of the $h$ distinct values. Therefore, ${\sum }_{k=1}^h\mathbb{P}(C=e_k)=100\%$. The execution times of the soft real-time jobs are assumed independent and identically distributed (iid). Thus, their joint probability is equal to the product of their probabilities. The execution times of jobs $J_j,j\in \mathbb{N}=\{1,2,3,\mathrm{\dots }\}$ are described by the random variables $C_j,j\in \mathbb{N}$ which are independent copies of $C$.

The response time of a job, denoted as $R_j$ for job $J_j$, is defined as its finishing time minus its release time. We note that a job may be dismissed (aborted) by the system before its completion. For such cases, $R_j$ is denoted as ↯ for brevity. In this work, we consider discrete time, i.e., all the above values relevant to time are integers.

As we consider soft real-time systems, even after job $J_j$ misses its deadline at $(j-1)T+D$, it can be reasonable that the job is further executed, since, contrary to hard real-time tasks, a late result may still provide a certain utility to the system. To quantify the utility accrual of a job according to its response time, the task $\tau$ is associated with a time/utility function (TUF), denoted as $V$.

The TUF is a function that maps the response time of a job to a utility value. That is, $V:ℝ\cup \left\{\text{↯}\right\}\to ℝ$. We assume that the time utility function of the task $\tau$ is piecewise defined and that the domain is partitioned at two time points: at the deadline $D$ and at a termination time point $H\ge D$. We assume $V(t)$ is $1$ for any $0\le t\le D$ (i.e., the job meets its deadline and provides full utility), $V(t)$ is less than $1$ for any (i.e., the job misses its deadline but still provides some utility), and $V(t)$ is $\sigma \le 0$ if it finishes after $H$ or is dismissed (i.e., the job result is too late to be useful and the job gets a utility penalty). We assume $V(t)$ to be non-increasing with respect to $t$ for .

In summary, $V:ℝ\cup \left\{\text{↯}\right\}\to ℝ$,

We note that the domain of $V$ can be set to $\mathbb{N}\cup \left\{\text{↯}\right\}$, as all timing parameters are assumed to be integers. We choose to use the domain $ℝ\cup \left\{\text{↯}\right\}$, as this in many situations allows to more easily specify the utility function.

We do not assume any relationship of $D$ and $T$ (i.e., $\tau$ is an arbitrary-deadline task) and only make the non-trivial assumptions $V(H)\ge \sigma$ and $\sigma \le 0$. This model generalizes the existing hard, soft, and firm real-time models:

• $\mathrm{■}$

  For a hard real-time task that does not allow deadline misses, $H$ is set to $D$ and the penalty $\sigma$ is set to $-\mathrm{\infty }$. We note that this implies the necessity to meet all deadlines and is not studied in this paper.

• $\mathrm{■}$

  For a firm real-time task a job is considered not useful after its deadline miss; thus, $H$ is set to $D$ and the penalty $\sigma$ is set to $0$.

• $\mathrm{■}$

  For a soft real-time task, multiple scenarios (and their combinations) are applicable:

  • –

    If a job is only considered useful up to a certain point after its deadline miss, denoted in this paper by a relative dismiss point $\delta$, then $H$ can be set to $\delta$.

  • –

    If a job receives a penalty when it is not completed, $\sigma$ is set to the penalty (i.e., it has a negative utility).

Figure 1 illustrates some possible scenarios. A firm real-time task is shown in Figure 1(a). For soft real-time, between $D$ and $H$, $V(t)$ could be linear, concave, or step-wise decreasing, as shown in Figure 1(b), 1(c), and 1(d), respectively. A negative utility at $V(H)$ can be still more beneficial than dismissing a job, resulting in a penalty of $\sigma$, as shown in Figure 1(e).

The utility accrual for the case when $H$ is set to $D$ and the penalty $\sigma$ is set to $0$ is identical to $1$ minus the deadline miss rate. Literature results for the deadline miss rate can therefore be applied, e.g., [21, 1, 2, 41, 3, 55, 54, 16, 24, 27, 25, 26, 42, 43, 45, 44], which is not further discussed here. Instead, we focus on the analysis of the utility accrual and utilize it for the explorations of the configurations of the scheduler.

We note that our results do not depend on the concrete structure of the utility function – it is sufficient when the Markov chain representation can be constructed for the given utility function. We restrict to functions according to the specification in Eq. (4) for the simplicity of presentation. Further discussions can be found in Section 8.

We assume a soft real-time task $\tau$ that is served by a reservation server, a time division multiple access (TDMA), or alike. The jobs of $\tau$ are processed in a first-come-first-serve (FCFS) manner. As in Real-Time Calculus [62, 69, 68], we abstractly model this as a greedy processing component (GPC) [60].

We describe the supply provided by the GPC by specifying the supply in intervals of length $G$. This approach allows to easily specify relatively complex but recurrent supply patterns. Specifically, for $0\le t\le G$ and $j\in \mathbb{N}=\{1,2,3,\mathrm{\dots }\}$, let the supply function ${\beta }_j(t)$ be the amount of accumulative time, i.e., supply, the GPC provides in $[(j-1)G,(j-1)G+t)$. By definition, ${\beta }_j(0)=0$. Furthermore, ${\beta }_j(t)$ is a non-decreasing function.

We implicitly assume in this paper that ${\beta }_j(t)$ is deterministic and how to extend our analysis to systems with upper/lower bounds on ${\beta }_j(t)$ is discussed in Section 8. By reformulating ${\beta }_j$, let $\rho (t)$ be the supply the GPC provides in $[0,t)$. The accumulative service provided by the GPC starting from $(j-1)T$ to $(j-1)T+t$ is denoted as

Based on the above discussions, the interaction between the period of the soft real-time task and the accumulative service repeats periodically with a period of $LCM(T,G)$, i.e., the least common multiplier (LCM) of $T$ and $G$. Let $Q$ be $\frac{LCM(T,G)}{T}$. By definition $Q$ is a positive integer. That is, the interaction between the period of the soft real-time task and the accumulative service repeats after considering $Q$ jobs of $\tau$.

In the above TDMA example, the supply function is the same for each interval of length $G=5$. This approach can easily be extended to supply functions which are piecewise constructed. An example with two alternating supply functions (i.e., the supply in interval $1,3,5,\mathrm{\dots }$ is described by ${\beta }_1(t)$ and the supply in interval $2,4,6,\mathrm{\dots }$ is described by ${\beta }_2(t)$) can be found in Section 3.2 and the related Figure 2.

We assume that the scheduler $𝒜$ makes a decision on how to execute a job $J_j$ with the following properties:

• $\mathrm{■}$

  When a job $J_j$ arrives at time $(j-1)T$, the scheduler decides whether this job $J_j$ is admitted, i.e., placed in the ready queue. This decision is made based on only information that is known at time $(j-1)T$.

• $\mathrm{■}$

  The admission of $J_j$ is accompanied with a maximum waiting point ${\omega }_j$, where $J_j$ is dismissed if it does not start its execution before $(j-1)T+{\omega }_j$. We assume that this configuration of ${\omega }_j$ is decided when $J_j$ is admitted and that $0\le {\omega }_j\le H$.

• $\mathrm{■}$

  The admission of $J_j$ is accompanied with a relative dismiss point ${\delta }_j$, where $J_j$ is dismissed if it is not completed at an absolute dismiss point $(j-1)T+{\delta }_j$. We assume that this configuration of ${\delta }_j$ is decided either when $J_j$ is admitted or when $J_j$ starts its execution. For the rest of this paper, for simplicity, we assume that a job $J_j$ is always dismissed immediately if it has not yet been completed at time $(j-1)T+H$. Therefore, the response time of a job is either no more than $H$ or defined as ↯.

If a job is not admitted to the ready queue or is dismissed, its utility accrual is the penalty value $\sigma$. Without loss of generality, we assume that the first job $J_1$ is always admitted with a given relative dismiss point ${\delta }_1$.

Although the above assumptions may not hold for all schedulers, we believe that they provide a good coverage. For instance, the following scheduling approaches are covered.

We provide a general framework to construct Markov chains based the above properties of the schedulers. In case the target scheduler does not comply with these properties, a revision of the construction of the Markov chain in Section 5 is needed. We provide further discussions on this matter in Section 8.

Under a given scheduling policy $𝒜$, let $R(j)$ be a discrete random variable, indicating the response time of the $j$-th job $J_j$ of the real-time task $\tau$. By definition, $R(j)$ is in $ℝ\cup \left\{\text{↯}\right\}$. Hence, the utility accrual of the first $N\in \mathbb{N}$ jobs of task $\tau$ is a random variable that is determined by accumulating their corresponding time utility and dividing by $N$:

Note that not admitted or dismissed jobs contribute the penalty value $\sigma$ in Equation (9).

The utility accrual of task $\tau$ in the long run is ${\mathrm{UA}}_N$ when $N\to \mathrm{\infty }$. However, as ${\mathrm{UA}}_N$ is a random variable, it must be shown that ${\mathrm{UA}}_N$ converges towards a single value almost surely. Essentially, we need to answer the following fundamental questions:

Does ${\mathrm{UA}}_N$ actually converge to a single value? If yes, to which value?

In case ${\mathrm{UA}}_N$ converges to a constant value $\mathrm{UA}\in ℝ$ almost surely, then $\mathrm{UA}$ is denoted as the long-term utility accrual and satisfies

We now demonstrate why simulating the scheduling policy or conducting scheduling experiments in a long run may converge towards different values depending on initial conditions, based on the concrete example in Figure 2; thus, the utility accrual is not well-defined. Assume the following implementation of a scheduler based on Example 4:

• $\mathrm{■}$

  When a job $J_j$ arrives at $(j-1)T$, it is admitted unconditionally. Let $b_j$ be a Boolean variable indicating whether there is any unfinished job before $J_j$ is released for execution.

• $\mathrm{■}$

  The absolute dismiss point is then set dependent on the start time of the job $J_j$. Suppose that $J_j$ starts its execution at time $t$. The absolute dismiss point is set to $t+15$ if $b_j$ is false or $t+5$ if $b_j$ is true.

Assume we have two alternating supply functions ${\beta }_1,{\beta }_2:[0,5]\to ℝ$:

The intervals where supply is provided are depicted in gray in Figure 2.

The periodic task $\tau$ has the parameters $T=5$, $D=6$, and its execution time $C$ is described by $\mathbb{P}(C=3)=0.5$ and $\mathbb{P}(C=6)=0.5$. The utility function is

We now show that the long-term utility accrual is not well-defined for this concrete example. Specifically, we show that for the above example the system behavior depends on the execution time of the first job.

We depict the two possible schedules in Figure 2, where upwards arrows are job releases and the small gray boxes indicate the service for task $\tau$. The boxes labeled $J_i$ is the interval where $J_i$ can be executed. A box with blue dashed lines indicates a job where $V(t)$ is always $1$, a red box a job where $V(t)$ is always $0$, and a white box an unclear utility (either $0$ or $1$).

• $\mathrm{■}$

  For $C_1=6$, the schedule is depicted in Figure 2(a). $J_1$ finishes at time $11$ and $J_2$ starts executing at time $11$, setting its absolute dismiss point to $16$. Regardless whether $C_2$ is $3$ or $6$, $J_2$ is dismissed at time $16$. Thus, $J_3$ starts at time $16$ with an absolute dismiss point at $21$. At time $21$, $J_3$ either finishes its execution for $C_3=3$ or is dismissed for $C_3=6$. Each of the subsequent jobs $J_4,J_5,\mathrm{\dots }$ either has a response time of $11$ or is dismissed. That is, $R(j)=11$ or $R(j)=\text{↯}$ for $j\ge 2$. Thus, the utility accrual for every job and, therefore, also in the long run is $0$.

• $\mathrm{■}$

  For $C_1=3$, the schedule is depicted in Figure 2(b). $J_1$ finishes at time $6$ and $J_2$ starts at time $6$ with an absolute dismiss point of $11$. If $C_2$ is $3$, then $J_2$ finishes at time $11$ with utility $1$; otherwise $J_2$ is dismissed at time $11$ with utility $0$. Hence, the scheduler unconditionally starts the execution of $J_3$ at time $11$, with an absolute dismiss point of $16$. $J_3$ is always dismissed at time $16$. The scheduler repeats the above pattern for $J_4,J_5,\mathrm{\dots }$. In summary, we have the following cases:

  • –

    For $j=2,4,6,\mathrm{\dots }$, with probability $50\%$ each, (i) when $C_j$ is $3$ then $R(j)$ is $6$ and $V(R(j))=1$, and (ii) when $C_j$ is $6$ then $R(j)$ is ↯ and $V(R(j)=0$.

  • –

    For $j=3,5,7,\mathrm{\dots }$, $R(j)$ is ↯ and $V(R(j))=0$.

  Interestingly, in this example $R(2),R(4),R(6),\mathrm{\dots }$ are independent and identically distributed (i.i.d.) random variables for $C_1=3$.

  Hence, if $C_1=3$, we can calculate the utility accrual as:

  ${\mathrm{UA}}_N$

  $={\displaystyle \frac{1}{N}}{\displaystyle \sum _{j=1}^N}V(R(j))={\displaystyle \frac{1}{N}}\left(1+{\displaystyle \sum _{j=1}^{\lfloor \frac{N}{2}\rfloor }}V(R(2j))\right)={\displaystyle \frac{1}{N}}+{\displaystyle \frac{\lfloor \frac{N}{2}\rfloor }{N}}\cdot {\displaystyle \frac{{\sum }_{j=1}^{\lfloor \frac{N}{2}\rfloor }V(R(2j))}{\lfloor \frac{N}{2}\rfloor }}$

  For $N\to \mathrm{\infty }$, we get $\frac{1}{N}\to 0$ and $\frac{\lfloor \frac{N}{2}\rfloor }{N}\to 0.5$. Furthermore, since $V(R(2j))$ are i.i.d. random variables, we can apply the classical central limit theorem. That is, $\frac{{\sum }_{j=1}^{\lfloor \frac{N}{2}\rfloor }V(R(2j))}{\lfloor \frac{N}{2}\rfloor }$ converges to the expected value $𝔼[V(R(2j))]=0.5$ for $N\to \mathrm{\infty }$ almost surely. Hence, the long-term utility in that case is $0+0.5\cdot 0.5=0.25$.

Since the utility accrual converges towards two different values with a probability of $0.5$ each (dependent only on the execution behavior of the first job), the long-term utility accrual is undefined. By simulating the scheduling policy or conducting scheduling experiments, the utility accrual in the long run is either $0$ or $0.25$, each with $50\%$ probability. Hence, although each simulation or experiment returns a concrete value, these values do not represent the long run utility accrual.

We now show that the expected value of utility accrual is also different from the utility accrual in the long run. The expected utility accrual of the schedule can be expressed as:

We use the example in Section 3.2 to demonstrate that the expected utility accrual is not necessarily the same as the utility accrual in the long run. Recall that $\mathbb{P}(R(1)=11)=0.5$ and $\mathbb{P}(R(1)=6)=0.5$. Furthermore, when $R(1)$ is $11$ the conditional probabilities for $j=2,3,\mathrm{\dots }$ are

In addition, when $R(1)$ is $6$, the conditional probabilities for $j=2,4,\mathrm{\dots }$ are

and for $j=3,5,\mathrm{\dots }$ are

Hence, we get an expected value of

For $N\to \mathrm{\infty }$, we have $\frac{1}{N}\to 0$ and $\frac{\lfloor \frac{N}{2}\rfloor }{N}\to 0.5$. Therefore, ${lim}_{N\to \mathrm{\infty }}𝔼[{\mathrm{𝑈𝐴}}_N]=0.125$.

We have shown that the expected utility accrual is $0.125$, whilst the utility accrual in a long run is either $0.25$ or $0$, each with $50\%$ probability. We note that the definition of Eq. (16) should be used to derive the expected utility accrual of all possible realizations of $C_1,C_2,\mathrm{\dots },C_N$. However, our focus is the convergence of the utility accrual of any possible realizations of $C_1,C_2,\mathrm{\dots },C_N$ in the long run, which can differ from the expected utility accrual, as demonstrated here.

We first explain how to construct a Markov chain for the example used in Section 3.2. We also utilize this example to show that the non-existence of convergence can be observed directly by the constructed Markov chain. Recall the periodic soft real-time task $\tau$ has $T=5$ and $D=6$, and two realizations of $e_1=3$ and $e_2=6$, each with a $50\%$ probability. The supply functions are described in Eq. (11) and the time utility function is in Eq. (15). We also know that $Q$ is $2$.

As Figure 2 already illustrates parts of possible schedules, we utilize it to simplify the explanation, instead of applying the equivalent calculations of the remaining execution time using the equations stated in Section 5. Here, we do not need to utilize $I$, since the remaining values (i.e., $v$, $rem$, and $\xi$) already reveal sufficient information to determine the subsequent states. Thus, we always denote $I$ as $\mathrm{\varnothing }$.

We demonstrate how to utilize the internal state $I$ when the scheduling policy refers also to the number of pending jobs with a case study of a scheduler explained in Example 3, denoted as ${𝒜}_{num}$. Consider a periodic soft real-time task $\tau$ with $T=D=5$, and two possible execution times:

• $\mathrm{■}$

  $e_1=2$ and $e_2=6$, and

• $\mathrm{■}$

  $\mathbb{P}(C_j=e_1)=0.5$ and $\mathbb{P}(C_j=e_2)=0.5$, $\forall j\in \mathbb{N}$.

Suppose $\tau$ is served by the supply function in Example 1 and that the time utility function of $\tau$ is defined as follows:

The maximum number of the pending jobs is set to $2$. Consequently, when a job $J_n$ is released at time $t$, once the number of jobs in the ready queue at time $t$ (including one that has started executing but is not yet finished) has already reached this limit, $J_n$ is not admitted, and the utility accrual of $J_n$ is $\sigma$. The relative dismiss point is set to $\delta =15=3T$.

We use $I$ to monitor the number of pending jobs. That is, we store the number of jobs completing or being dismissed in each upcoming period $T$, and the aggregate of pending jobs is the sum of these list entries. More specifically, let $a_i(t)$ be the number of jobs completing or being dismissed in the interval $(t+i\cdot T,t+(i+1)\cdot T]$. Then, for a job being released at time $t+T$ the number of pending jobs can be calculated by $a_1(t)+a_2(t)$, because no preceding job is executed after $t+3T$ due to the dismiss point $\delta =3T$. Hence, it is sufficient to store $I=[a_1(t),a_2(t)]$ in a state that describes a job released at time $t$, since the subsequent job is admitted if and only if .

Due to space limitation, we only sketch the construction process with a focus on how to utilize the internal state $I$.