# On-Line Real-Time Service-Oriented Task Scheduling Using TUF

Authors: Shuo Liu; Gang Quan; Shangping Ren
Journal: ISRN Software Engineering
 (2012)

---

## Abstract

We present our approach to real-time
service-oriented scheduling problems with the objective of
maximizing the total system utility. Different from the traditional
utility accrual scheduling problems that each task is associated
with only a single time utility function (TUF), we associate two
different TUFs—a profit TUF and a penalty TUF—with each
task, to model the real-time services that not only need to reward
the early completions but also need to penalize the abortions or
deadline misses. The scheduling heuristics we proposed in this
paper judiciously accept, schedule, and abort real-time services
when necessary to maximize the accrued utility. Our extensive
experimental results show that our proposed algorithms can
significantly outperform the traditional scheduling algorithms
such as the Earliest Deadline First (EDF), the traditional utility
accrual (UA) scheduling algorithms, and an earlier scheduling
approach based on a similar model.


---

## Body

## 1. Introduction

With the proliferation of the Internet the opportunity has come to provide real-time services over the cloud infrastructure [1–3]. From media on-demand service by Netflix to online gaming by Nintendo, from Amazon’s e-commerce to Google’s free turn-by-turn direction service over the phone, all these indicate that we are entering a new era of real-time computing. These real-time services are usually built on Internet-based cloud infrastructure, not only because they need to be highly available, but also because they generally rely on large data sets that are most conveniently hosted in large data centers. According to O’Reilly [4], the entire Internet is becoming not only a platform, but also an operating system itself, and “the future belongs to services that respond in real time to information provided either by their users or by nonhuman sensors” [1].For real-time services, timeliness is a major criterion of judging real-time service-quality levels. Due to the high variability of the Internet, real-time service-oriented applications are more of soft real-time in nature. Guaranteeing hard deadlines for real-time services would be neither practical nor necessary in most scenarios. In this regard, besides pre-assigned deadlines, some other timing information that is closely related to quality of service (QoS) become important metrics when processing real-time service requests.To improve the real-time service performance, one approach is to employ the traditional UA approach [5, 6]. In [7], Jensen et al. first proposed to associate each task with a TUF, which indicates that the completion of a task will assign the system a certain value of utility, and the utility value varies with the time when the task is finished. Specifically, a TUF as shown in Figure 1(a) describes the value or utility accrued by a system at the time when a task is completed. Based on this model, there were extensive research results published on the topic of UA scheduling [8–12]. For example, in [8], the author proposed an algorithm, Generic Benefit Scheduling (GBS), based on TUF to schedule activities that subject to various time and mutual exclusive resource constraints. Utility density is implemented as the activity’s priority metric. While Jensen’s definition of TUF allows the semantics of soft timing constraints to be more precisely specified, all these variations of UA-aware scheduling algorithms imply that the aborted tasks neither increase nor decrease the accrued value or utility of the system.Time utility functions.
(a)(b)(c)We believe that, to further improve the performance of real-time services over the Internet, it is important to not only measure the profit when completing a task in time, but also account for the penalty when a task is aborted or discarded. In addition, the time at which a real-time service is aborted is also important. First, the more service requests are discarded and the longer a client waits fruitlessly, the lower the quality of service client receives. As a result, service providers have to pay higher cost, either in the form of monetary compensation or losing future service requests from unsatisfied clients. Second, before a task is aborted or discarded, it needs to consume system resources, including network bandwidth, storage space, and processing power, and thus can directly or indirectly affect the system performance. This is especially true if we assume real-time applications may be dissected and migrated across an entire cloud infrastructure [13, 14]. Therefore, if a real-time task is deemed to miss its deadline with no positive semantic profit, a better choice should be one that can detect it and discard it as soon as possible.A number of models [15–18] were proposed to account for the penalty when a real-time service request is discarded or misses its deadline. For example, Bartal et al. [15] studied the online scheduling problem when penalties have to be paid for rejected real-time tasks. Chun and Culler [16] and Irwin et al. [18] adopted an extended time utility function as shown in Figure 1(b). According to this model, a decay rate is associate with each real-time task, reflecting the increasing risk of completing the task late in the future. Therefore, when a real-time task is completed late, it earns a negative utility, indicating a penalty rather than the profit. These models, however, do not account for different penalties when aborting a real-time task at different times.In this paper, we study the real-time service scheduling problem based on a task model similar to the one proposed by Yu et al. [19]. Specifically, a task is associated with two different TUFs, as shown in Figure 1(c), a profit TUF (G(t)), and a penalty TUF (L(t)). The system takes a profit (determined by its profit TUF) if the task completes by its deadline and suffers a penalty (determined by its penalty TUF) if the task misses its deadline or is dropped before its completion. The penalty to abort a pending real-time service request can be the same or different from that of missing the deadline, which depends on the characteristics of the penalty TUF. Different from Yu’s model, we use a novel method to calculate task’s utility and use utility density to describe a task’s priority. The “critical time” for each task is more strict, and we add an admission step when there is a new task arrives since congested ready queue will decrease the system’s performance. It is a waste of system resources if tasks wait fruitlessly.We conduct analysis on how to optimize the accrual utility when scheduling a set of aperiodic real-time service requests. We first assume that the service requests are scheduled in a nonpreemptive manner. Two scheduling methods are presented. The first scheduling method is developed based on the concept of “opportunity cost” [20] from economics that can help evaluate the fulfillment of a real-time service request. The second method employs a more sophisticated but robust method to formulate the potential system profit by developing a speculated execution order for the ready tasks. We then extend our scheduling methods to deal with real-time services that may preempt each other. In addition to carefully choosing the ready task to run, our scheduling methods judiciously discard pending requests, abort task executions, cautiously preempt current running tasks, and therefore can achieve better performance. Our experimental results also show that the proposed algorithms can significantly outperform the traditional scheduling approaches such as the Earliest Deadline First (EDF), the traditional UA scheduling algorithm, that is, the Generic Utility Scheduling (GUS) [8], the Risk/Reward algorithm [18], and a previous scheduling approach based on a similar model, that is, the Profit Penalty-aware scheduling (PP-aware scheduling) [19].The rest of the paper is organized as follows. Section2 describes the models we used in the paper, formulates the problem formally, and then presents a motivation example. Sections 3 and 4 introduce our scheduling approaches in details. Experiment results are discussed in Section 5, and we make conclusions in Section 6.


## 2. Preliminary

In this section, we first introduce the task and architecture models considered in this paper. We then use an example to motivate our research.


### 2.1. Task Model and System Architecture

In this paper, we consider a single sequence of randomly arrived real-time tasksΓ={τ1,τ2,…,τn}, with τi defined using the following parameters:(i)
[Bi,Wi]: the best case execution time Bi and the worst case execution time Wi of τi;(ii)
Di: the relative deadline of τi;(iii)
fi(T): the probability density function for the execution time of τi;(iv)
Gi(t): the profit TUF, which represents the profit accrued when a task is completed at time t. We assume Gi(t) is a nonincreasing unimodal function before its deadline, that is, Gi(tp)≥Gi(tq) if  tp≤tq, and Gi(Di)=0.(v)
Li(t): the penalty TUF, which represents the penalty suffered when a task is discarded or aborted at time t. We assume that  Li(t) is a nondecreasing unimodal function before its deadline, that is, Li(tp)≤Li(tq) if tp≤tq, and a task is immediately discarded once it missed its deadline.Note that, even though the deadline of a task can be implicitly defined using appropriate profit and penalty TUFs, we opt to list the deadline explicitly as a parameter for ease of presentation. As shown above, a task is associated with both a profit function and a penalty function with function values varying with time. Therefore, while executing a task the system has a potential to gain profit, it also has a potential to encounter a penalty at a later time. The system performance is therefore evaluated by its total utility after penalty is deducted from profit.We assume an architecture for the service provider depicted in Figure2. Specifically, the service provider contains two computing components, that is, the manager host and the execution host, that can work concurrently. The manager host is in charge of accepting, scheduling, and aborting real-time service requests, and the execution host fulfills the selected service requests from the manager host. There may be one or more execution hosts for each service provider. We limit our research to one single execution host in this paper.Figure 2
The architecture for the service provider.With the task and architecture model introduced as above, our problem can be formally formulated as follows.Problem 1.
Given a task setΓ={τ1,τ2,…,τn} as described above, develop online scheduling methods such that the total accrued utility is maximized.


### 2.2. A Motivation Example

The problem defined in Problem1 is NP hard since a simpler version of this problem, that is, the total weighted completion time scheduling problem [21], is shown to be NP hard. To show that the commonly used scheduling policy such as the EDF or the traditional utility accrual approach such as the GUS [8] become ineffective to address this problem, consider the example shown in Figure 3.Figure 3
Three different schedules for two real-time tasksτ1 and τ2 arriving at the same time t=0.Assume that two real-time service requests arrive at the same time (t=0) with their characteristics shown in Figure 3. We assume that the actual processor time of each request is evenly distributed between the interval of its best case and worst case execution time. To make the example more concrete, we assume that the actual processing times for these two requests are 50 and 60, respectively.When EDF is applied,τ1 has a higher priority than τ2 and is executed first. It completes at  t=50 with profit of G1(50)=180-2×50=80. Then τ2 starts its execution. At  t=100, it misses its deadline and will incur more penalty if its execution continues. Therefore, the execution of τ2 is discarded at  t=100 with penalty of L2(100)=2×100=200. The total utility to process these two requests is therefore 80-200=-120.The GUS algorithm chooses the task with the largest expected profit density to execute first. Under our task model, the expected profit ofτ1 and τ2, that is, G¯(τ1) and G¯(τ2), can be calculated as(1)G¯(τ1)=∫2080(180-2t)×180-20dt=80,G¯(τ2)=∫20120(400-3t)×1120-20dt=190.Att=0, we have no knowledge of the actual execution time of τ1 and τ2, and a reasonable estimate would be the one using their expected values, that is, 50 and 70, respectively. As a result, τ2 is chosen to execute first since its expected profit density (expected profit divided by expected execution time) 190/70 is higher than that of τ1, that is, 80/50. It completes at t=60 with profit of G2(60)=400-3×60=220. Then τ1 starts its execution. At t=80, it misses its deadline and is aborted to prevent even higher loss. The total utility to process these two requests is therefore 220-80=140.An astute reader may immediately point out that, afterτ2 completes at t=60, it is less likely that τ1 can complete by its deadline, given that its best case execution time is 20. Therefore, τ1 should be immediately aborted at  t=60 with a total utility profit of 220-60=160. Note that, after τ2  is selected to execute first, its expected execution time would be 70. Given the expected execution time of τ1 being 50, it is more likely that τ1 will miss its deadline. Therefore, a better scheduling decision would discard it at t=0 with total profit of 220 in this case, as the third schedule shown in Figure 3.In our example, we can see that the EDF has the worst performance since it makes scheduling decisions solely based on tasks’ deadlines. The traditional utility accrual scheduling method takes the individual value function into consideration and therefore can achieve better performance. The problem, however, is that the traditional utility accrual scheduling approaches (such as GUS) fail to take the abortion or discard penalty and the timing for the abortion or discard penalty into consideration. Clearly, how to select the appropriate task to run so as to maximize the profit and how to discard real-time tasks as soon as possible in overloaded situations in order to control the penalty are vital for our research problem.


## 2.1. Task Model and System Architecture

In this paper, we consider a single sequence of randomly arrived real-time tasksΓ={τ1,τ2,…,τn}, with τi defined using the following parameters:(i)
[Bi,Wi]: the best case execution time Bi and the worst case execution time Wi of τi;(ii)
Di: the relative deadline of τi;(iii)
fi(T): the probability density function for the execution time of τi;(iv)
Gi(t): the profit TUF, which represents the profit accrued when a task is completed at time t. We assume Gi(t) is a nonincreasing unimodal function before its deadline, that is, Gi(tp)≥Gi(tq) if  tp≤tq, and Gi(Di)=0.(v)
Li(t): the penalty TUF, which represents the penalty suffered when a task is discarded or aborted at time t. We assume that  Li(t) is a nondecreasing unimodal function before its deadline, that is, Li(tp)≤Li(tq) if tp≤tq, and a task is immediately discarded once it missed its deadline.Note that, even though the deadline of a task can be implicitly defined using appropriate profit and penalty TUFs, we opt to list the deadline explicitly as a parameter for ease of presentation. As shown above, a task is associated with both a profit function and a penalty function with function values varying with time. Therefore, while executing a task the system has a potential to gain profit, it also has a potential to encounter a penalty at a later time. The system performance is therefore evaluated by its total utility after penalty is deducted from profit.We assume an architecture for the service provider depicted in Figure2. Specifically, the service provider contains two computing components, that is, the manager host and the execution host, that can work concurrently. The manager host is in charge of accepting, scheduling, and aborting real-time service requests, and the execution host fulfills the selected service requests from the manager host. There may be one or more execution hosts for each service provider. We limit our research to one single execution host in this paper.Figure 2
The architecture for the service provider.With the task and architecture model introduced as above, our problem can be formally formulated as follows.Problem 1.
Given a task setΓ={τ1,τ2,…,τn} as described above, develop online scheduling methods such that the total accrued utility is maximized.


## 2.2. A Motivation Example

The problem defined in Problem1 is NP hard since a simpler version of this problem, that is, the total weighted completion time scheduling problem [21], is shown to be NP hard. To show that the commonly used scheduling policy such as the EDF or the traditional utility accrual approach such as the GUS [8] become ineffective to address this problem, consider the example shown in Figure 3.Figure 3
Three different schedules for two real-time tasksτ1 and τ2 arriving at the same time t=0.Assume that two real-time service requests arrive at the same time (t=0) with their characteristics shown in Figure 3. We assume that the actual processor time of each request is evenly distributed between the interval of its best case and worst case execution time. To make the example more concrete, we assume that the actual processing times for these two requests are 50 and 60, respectively.When EDF is applied,τ1 has a higher priority than τ2 and is executed first. It completes at  t=50 with profit of G1(50)=180-2×50=80. Then τ2 starts its execution. At  t=100, it misses its deadline and will incur more penalty if its execution continues. Therefore, the execution of τ2 is discarded at  t=100 with penalty of L2(100)=2×100=200. The total utility to process these two requests is therefore 80-200=-120.The GUS algorithm chooses the task with the largest expected profit density to execute first. Under our task model, the expected profit ofτ1 and τ2, that is, G¯(τ1) and G¯(τ2), can be calculated as(1)G¯(τ1)=∫2080(180-2t)×180-20dt=80,G¯(τ2)=∫20120(400-3t)×1120-20dt=190.Att=0, we have no knowledge of the actual execution time of τ1 and τ2, and a reasonable estimate would be the one using their expected values, that is, 50 and 70, respectively. As a result, τ2 is chosen to execute first since its expected profit density (expected profit divided by expected execution time) 190/70 is higher than that of τ1, that is, 80/50. It completes at t=60 with profit of G2(60)=400-3×60=220. Then τ1 starts its execution. At t=80, it misses its deadline and is aborted to prevent even higher loss. The total utility to process these two requests is therefore 220-80=140.An astute reader may immediately point out that, afterτ2 completes at t=60, it is less likely that τ1 can complete by its deadline, given that its best case execution time is 20. Therefore, τ1 should be immediately aborted at  t=60 with a total utility profit of 220-60=160. Note that, after τ2  is selected to execute first, its expected execution time would be 70. Given the expected execution time of τ1 being 50, it is more likely that τ1 will miss its deadline. Therefore, a better scheduling decision would discard it at t=0 with total profit of 220 in this case, as the third schedule shown in Figure 3.In our example, we can see that the EDF has the worst performance since it makes scheduling decisions solely based on tasks’ deadlines. The traditional utility accrual scheduling method takes the individual value function into consideration and therefore can achieve better performance. The problem, however, is that the traditional utility accrual scheduling approaches (such as GUS) fail to take the abortion or discard penalty and the timing for the abortion or discard penalty into consideration. Clearly, how to select the appropriate task to run so as to maximize the profit and how to discard real-time tasks as soon as possible in overloaded situations in order to control the penalty are vital for our research problem.


## 3. Nonpreemptive Approach

In this section, we present our online nonpreemptive scheduling solutions to address the problem defined in the previous section. Since the execution of a task may gain positive profit or suffer penalty and thus degrade the overall computing performance, judicious decisions must be made with regard to executing a task, discarding or aborting a task, and when to discard or abort a task. In what follows, we present two metrics to measure the expected utility when executing a real-time task, and, based on which, we develop two scheduling algorithms.


### 3.1. The Opportunity Cost-Based Utility Metric

Our first utility metric is built upon the concept ofopportunity cost [20] in economics. In economics, the opportunity cost refers to the value associated with the next best available choice that one has to give up after making a choice. When scheduling a set of real-time tasks at t=T, let expected utility of running τi alone be Ui¯(T) and its opportunity cost be OCi¯(T). Then we can conveniently formulate the expected utility Ũ(τi,T) to run τi at t=T as(2)Ũ(τi,T)=Ui¯(T)-OCi¯(T).
The problem becomes how to calculate Ui¯(T) and OCi¯(T).Since the task execution time is not known a prior, we do not know if executing the task will lead to positive profit or loss. Given its probabilistic distribution, we can determine the expected profit and loss statistically. Given a taskτi with arrival time of ri, let its predicted starting time be T. Then the expected profit (Gi¯(T)) to execute τi can be represented as(3)Gi¯(T)=∫0∞Gi(t+(T-ri))fi(t∣t+T<D)dt=∫BiDiGi(t+(T-ri))fi(t)dt.
Similarly, the expected loss (Li¯(T)) to execute τi can be represented as(4)Li¯(T)=Li(D)P(t+T>D)=Li(D)∫Di-(T-ri)Wifi(t)dt.
Therefore, the expected utility Ui¯(T) can be represented as(5)Ui¯(T)=Gi¯(T)-Li¯(T).
When Ui¯(T)>0, it means that the probability to obtain positive profit is no smaller than that to incur a loss if we choose to execute τi  at  t=T. Since Gi¯(T) is a monotonic decreasing function of T, and Li¯(T) is a monotonic increasing function of T, Ui¯(T) must be a monotonic decreasing function of T.Note that even though two tasks may have the same expected utility, they may have different expected execution times. We define a parameterρi to capture the expected utility density for task τi as follows:(6)ρ¯i(T)=Ui¯(T)Ci¯,
where Ci¯ is the expected execution time of task τi. There exists a t0 such that(7)ρ¯i(t0)=0.
The time t=t0 is called the critical point. Apparently, when t>t0, it is more likely that it will incur a loss rather than a profit if we choose to execute τi. We can further relax  (7) by imposing a threshold (δ), that is,(8)ρ¯i(t0)≥δ.
We call δ as the utility density threshold.We next introduce how to formulate the opportunity cost when choosing to run taskτi at t=T. The original concept of “opportunity cost” is the value for the next best available choice. It is hard to identify the “next best choice” since the exact reason we need the opportunity cost is to set up the preference order when choosing tasks to run. In our metric, the opportunity cost is calculated as the decay of expected utilities by other tasks. Specifically, let the expected utility of τj at t=T  be  Uj¯. Then if we choose τi to execute at t=T and after its completion, the expected utility of τj is reduced to Uj¯(T+Ci¯), where Ci¯ is the expected execution time of τi. Provided that we can remove the task timely when its expected utility is less than zero, we thus define the opportunity cost to run τi at t=T, that is, OCi¯(T)  as(9)OCi¯(T)=1n-1∑j=1,j≠inmax⁡((Uj¯-Uj¯(T+Ci¯)),0).With bothUi¯(T) and  OCi¯(T) formulated, we are now ready to introduce our scheduling algorithm. Our nonpreemptive scheduling algorithm works at scheduling points that include the arrival of a new task, the completion of the current task, and the critical point of the current task. The detailed algorithm is described in Algorithm 1.Algorithm 1:The scheduling algorithm based on opportunity cost.
1:Input: Let {τ1,τ2,…,τk} be the accepted tasks in theready queue, and letCi¯ be the expected execution time ofτi. Let current time be t and let τ0 be the task currentlybeing executed, expected execution time ofτ0 is C0¯. Letthe expected utility density threshold beδ.2:3:if  A new task, that is, τp arrives then4:  Acceptτp if  ρ¯p(C¯0)>δ;5:  Rejectτp if ρ¯p(C¯0)≤δ;6:  Removeτj in the ready queue end if ρ¯j(C¯0)≤δ;7:end if8:9:Ifτ0 is completed then10:  Chooseτi with the largest system utility density, that is,ρ̃i(t)=maxkρ̃k(t).11:  Removeτj in the ready queue if ρ¯j(C¯i)<δ;12:end if13:14:Ift = the critical time of τ0  then15:  Abortτ0 immediately;16:  Chooseτi with the largest system utility density, that is,ρ̃i(t)=maxkρ̃k(t).17:  Removeτj in the ready queue if ρ¯j(C¯i)<δ;18:end ifWhen a new job arrives, its expected utility density is calculated based on (2), (5), and (9). If its expected utility density is larger than the pre-set threshold, it is accepted and is rejected otherwise. When the current running task completes, the task in the ready queue with the highest expected system utility density is chosen to be executed. When the time reaches the critical point of the current running task, it implies that it will mostly likely incur utility density less than the threshold and is thus worthless of continuous execution. In that case, the task is immediately discarded, and a new task will be chosen to execute. At every scheduling point, the expected utility density of the tasks in the ready queue is checked. Since the expected utility density decreases monotonically with time, the task with expected utility density less than the threshold is aborted. The complexity of Algorithm 1 comes from the calculation of the expected system utility values for the task set, with the complexity of O(n2), where n is the number of tasks in the ready queue.


### 3.2. The Speculation-Based Utility Metric

From (3), (4), and (5), we can clearly see that the expected utility of running a task depends heavily on variable T, that is, the time when the task can start. If we can know the execution order and thus the expected starting time for tasks in the ready queue, we will be able to quantify the expected utility density of each task more accurately. In this section, we develop our second utility metric based on a speculated execution order of the tasks in the ready queue.The general idea to generate the speculated execution order is as follows. We first calculate the expected utility density for each task in the ready queue based on the expected finishing time of the current running task. Then the task with the largest one is assumed to be the first task that will be executed after the current task is finished. Based on this assumption, we then calculate the expected utility densities for the rest of the tasks in the ready queue and select the next task. This process continues until all tasks in the ready queue are put in the order. While completed, we essentially generate a speculated execution order for the tasks in the ready queue and, at the same time, calculate the corresponding expected utility density for each task. The detailed algorithm is described in Algorithm2.Algorithm 2:Generating the speculated execution order and the expected utility for task in the ready queue.
1:Input: Let Γ={τ1,τ2,…,τk} be the accepted tasks in theready queue, and letri, Ci¯ represent the arrival time andexpected execution time ofτi. Let the current time be t2:Output: The new list Γ′={τ1′,τ2′,…,τk′} with the speculatedexecution order and their corresponding expectedutility densityρ̂j′ for  τj′,1≤j≤k.3:If A task τ0 is being executed then4:T=r0+C0¯;5:else6:T=t;7:end if8:WhileΓ is not empty do9:For Each task i in Γ  do10:  Calculateρ¯i(T) based on  (3), (4), (5), and(6);11:end for12:  Selectτj with the highest ρ¯j(T);13:  Addτj to the end of Γ′;14:ρ̂j=ρj¯(T);15:T=T+Cj¯;16:  Removeτj from Γ;17:end whileThe scheduling algorithm based on our speculated utility metric is very similar to Algorithm1 and is thus omitted. The only difference is that the speculation-expected utility, rather than the opportunity cost-based utility, for each task in the ready queue is calculated at each scheduling point, including the arrival of a new task, the completion of the current task, and the critical point of the current task.The complexity of the scheduling algorithm mainly comes from Algorithm2. It is not difficult to see that the complexity of Algorithm 2 is O(n2) with n the number of tasks in the ready queue.


## 3.1. The Opportunity Cost-Based Utility Metric

Our first utility metric is built upon the concept ofopportunity cost [20] in economics. In economics, the opportunity cost refers to the value associated with the next best available choice that one has to give up after making a choice. When scheduling a set of real-time tasks at t=T, let expected utility of running τi alone be Ui¯(T) and its opportunity cost be OCi¯(T). Then we can conveniently formulate the expected utility Ũ(τi,T) to run τi at t=T as(2)Ũ(τi,T)=Ui¯(T)-OCi¯(T).
The problem becomes how to calculate Ui¯(T) and OCi¯(T).Since the task execution time is not known a prior, we do not know if executing the task will lead to positive profit or loss. Given its probabilistic distribution, we can determine the expected profit and loss statistically. Given a taskτi with arrival time of ri, let its predicted starting time be T. Then the expected profit (Gi¯(T)) to execute τi can be represented as(3)Gi¯(T)=∫0∞Gi(t+(T-ri))fi(t∣t+T<D)dt=∫BiDiGi(t+(T-ri))fi(t)dt.
Similarly, the expected loss (Li¯(T)) to execute τi can be represented as(4)Li¯(T)=Li(D)P(t+T>D)=Li(D)∫Di-(T-ri)Wifi(t)dt.
Therefore, the expected utility Ui¯(T) can be represented as(5)Ui¯(T)=Gi¯(T)-Li¯(T).
When Ui¯(T)>0, it means that the probability to obtain positive profit is no smaller than that to incur a loss if we choose to execute τi  at  t=T. Since Gi¯(T) is a monotonic decreasing function of T, and Li¯(T) is a monotonic increasing function of T, Ui¯(T) must be a monotonic decreasing function of T.Note that even though two tasks may have the same expected utility, they may have different expected execution times. We define a parameterρi to capture the expected utility density for task τi as follows:(6)ρ¯i(T)=Ui¯(T)Ci¯,
where Ci¯ is the expected execution time of task τi. There exists a t0 such that(7)ρ¯i(t0)=0.
The time t=t0 is called the critical point. Apparently, when t>t0, it is more likely that it will incur a loss rather than a profit if we choose to execute τi. We can further relax  (7) by imposing a threshold (δ), that is,(8)ρ¯i(t0)≥δ.
We call δ as the utility density threshold.We next introduce how to formulate the opportunity cost when choosing to run taskτi at t=T. The original concept of “opportunity cost” is the value for the next best available choice. It is hard to identify the “next best choice” since the exact reason we need the opportunity cost is to set up the preference order when choosing tasks to run. In our metric, the opportunity cost is calculated as the decay of expected utilities by other tasks. Specifically, let the expected utility of τj at t=T  be  Uj¯. Then if we choose τi to execute at t=T and after its completion, the expected utility of τj is reduced to Uj¯(T+Ci¯), where Ci¯ is the expected execution time of τi. Provided that we can remove the task timely when its expected utility is less than zero, we thus define the opportunity cost to run τi at t=T, that is, OCi¯(T)  as(9)OCi¯(T)=1n-1∑j=1,j≠inmax⁡((Uj¯-Uj¯(T+Ci¯)),0).With bothUi¯(T) and  OCi¯(T) formulated, we are now ready to introduce our scheduling algorithm. Our nonpreemptive scheduling algorithm works at scheduling points that include the arrival of a new task, the completion of the current task, and the critical point of the current task. The detailed algorithm is described in Algorithm 1.Algorithm 1:The scheduling algorithm based on opportunity cost.
1:Input: Let {τ1,τ2,…,τk} be the accepted tasks in theready queue, and letCi¯ be the expected execution time ofτi. Let current time be t and let τ0 be the task currentlybeing executed, expected execution time ofτ0 is C0¯. Letthe expected utility density threshold beδ.2:3:if  A new task, that is, τp arrives then4:  Acceptτp if  ρ¯p(C¯0)>δ;5:  Rejectτp if ρ¯p(C¯0)≤δ;6:  Removeτj in the ready queue end if ρ¯j(C¯0)≤δ;7:end if8:9:Ifτ0 is completed then10:  Chooseτi with the largest system utility density, that is,ρ̃i(t)=maxkρ̃k(t).11:  Removeτj in the ready queue if ρ¯j(C¯i)<δ;12:end if13:14:Ift = the critical time of τ0  then15:  Abortτ0 immediately;16:  Chooseτi with the largest system utility density, that is,ρ̃i(t)=maxkρ̃k(t).17:  Removeτj in the ready queue if ρ¯j(C¯i)<δ;18:end ifWhen a new job arrives, its expected utility density is calculated based on (2), (5), and (9). If its expected utility density is larger than the pre-set threshold, it is accepted and is rejected otherwise. When the current running task completes, the task in the ready queue with the highest expected system utility density is chosen to be executed. When the time reaches the critical point of the current running task, it implies that it will mostly likely incur utility density less than the threshold and is thus worthless of continuous execution. In that case, the task is immediately discarded, and a new task will be chosen to execute. At every scheduling point, the expected utility density of the tasks in the ready queue is checked. Since the expected utility density decreases monotonically with time, the task with expected utility density less than the threshold is aborted. The complexity of Algorithm 1 comes from the calculation of the expected system utility values for the task set, with the complexity of O(n2), where n is the number of tasks in the ready queue.


## 3.2. The Speculation-Based Utility Metric

From (3), (4), and (5), we can clearly see that the expected utility of running a task depends heavily on variable T, that is, the time when the task can start. If we can know the execution order and thus the expected starting time for tasks in the ready queue, we will be able to quantify the expected utility density of each task more accurately. In this section, we develop our second utility metric based on a speculated execution order of the tasks in the ready queue.The general idea to generate the speculated execution order is as follows. We first calculate the expected utility density for each task in the ready queue based on the expected finishing time of the current running task. Then the task with the largest one is assumed to be the first task that will be executed after the current task is finished. Based on this assumption, we then calculate the expected utility densities for the rest of the tasks in the ready queue and select the next task. This process continues until all tasks in the ready queue are put in the order. While completed, we essentially generate a speculated execution order for the tasks in the ready queue and, at the same time, calculate the corresponding expected utility density for each task. The detailed algorithm is described in Algorithm2.Algorithm 2:Generating the speculated execution order and the expected utility for task in the ready queue.
1:Input: Let Γ={τ1,τ2,…,τk} be the accepted tasks in theready queue, and letri, Ci¯ represent the arrival time andexpected execution time ofτi. Let the current time be t2:Output: The new list Γ′={τ1′,τ2′,…,τk′} with the speculatedexecution order and their corresponding expectedutility densityρ̂j′ for  τj′,1≤j≤k.3:If A task τ0 is being executed then4:T=r0+C0¯;5:else6:T=t;7:end if8:WhileΓ is not empty do9:For Each task i in Γ  do10:  Calculateρ¯i(T) based on  (3), (4), (5), and(6);11:end for12:  Selectτj with the highest ρ¯j(T);13:  Addτj to the end of Γ′;14:ρ̂j=ρj¯(T);15:T=T+Cj¯;16:  Removeτj from Γ;17:end whileThe scheduling algorithm based on our speculated utility metric is very similar to Algorithm1 and is thus omitted. The only difference is that the speculation-expected utility, rather than the opportunity cost-based utility, for each task in the ready queue is calculated at each scheduling point, including the arrival of a new task, the completion of the current task, and the critical point of the current task.The complexity of the scheduling algorithm mainly comes from Algorithm2. It is not difficult to see that the complexity of Algorithm 2 is O(n2) with n the number of tasks in the ready queue.


## 4. Preemptive Approaches

In the previous section, we introduce two methods to quantify the potential system utility when scheduling a set of real-time requestsnonpreemptively. Since a preemptive real-time scheduling technique tends to be more responsive for a higher priority request and can achieve higher schedulability and throughput than its nonpreemptive counterpart, we are interested in studying how to schedule a real-time task set preemptively to maximize the total accrued system utility.When employing the preemptive scheduling method to schedule real-time tasks with the goal of maximizing the accrued utility, a critical issue is to determine when the preemption should occur. An intuitive approach is to define the priority of a task based on its expected utility density (6). Nevertheless, such an unconstrained preemptive scheduling may or may not improve the system performance, in terms of accrued system utility, when compared to a nonpreemptive one.Consider the two examples in Figure4. Figure 4(a) shows two tasks scheduled both preemptively (based on the expected utility density) and nonpreemptively. The parameters for both tasks are listed in the figure. In preemptive method, task τ1 arrives and starts its execution at arrival time t=0. At time t=1 task τ2 arrives. Note that, at t=1, we have ρ1(t)=1.3 and ρ2(t)=1.6. Therefore, τ2 comes with a higher expected utility density and preempts τ1. Task τ1 continues its execution after task τ2 completes. The total utility in this method is 12. In the corresponding nonpreemptive method, task τ2 misses its deadline, and the total utility in this method is 3. This example shows that, by processing the higher “priority” job first, the preemption helps increase the total utility of the system.Preemptive versus nonpreemptive scheduling two real-time requests to maximize the accrued system utility.
(a)
Preemptive scheduling is better than the nonpreemptive scheduling(b)
Nonpreemptive scheduling is better than the preemptive schedulingNow let us consider the example in Figure4(b). For the two tasks in Figure 4(b), at time t=1, we have ρ1(t)=1.6 and ρ2(t)=2.3. Therefore, τ2 has a higher priority than τ1. When these two tasks are scheduled in the preemptive manner, task τ1 misses its deadline, and the total utility is 3. Both two tasks can meet their deadlines when they are scheduled in the nonpreemptive manner with a total utility of 12.This example illustrates that unconstrained preemption does not always help improve the accrued utility. Note that since the profit and penalty TUFs of each task vary with time, its “priority” also varies with time. In this case, all tasks in the ready queue need to be checked for priority at every time instance. Hence, a perfect preemptive scheduling would be impractical due to its prohibit computational cost, even if it is theoretically possible. In addition, a large number of unconstrained preemptions disrupts task executions, makes them less likely to complete before their deadlines, and leaves alone the large overhead coming with the preemptions. Our empirical studies also showed that unconstrained preemptive scheduling can potentially degrade the performance than the corresponding nonpreemptive scheduling. To this end, we want to limit the scenarios of when the preemption can occur to improve the performance of the preemptive scheduling.To constrain the preemptions, we first limit the time instances that at when preemptions can occur. Instead of letting a higher priority task always preempts a lower priority task, we allow that such a preemption can only happen when a new task comes or at a regular checking point, which we callpreemption checking point. Let the last preemption occurs at time t=T0. A task can be preempted at t=T only if new tasks arrive at t=T or(10)(T-T0)mod⁡Lint⁡=0,
where Lint is the length of the preemption checking point interval.At apreemption checking point, the higher priority task does not necessarily always preempt the one with lower priority if the potential gain to execute the high priority task is not significantly higher than the gain achieved by continuously executing the current running task. We define a parameter called preemption threshold for this purpose. Let the current running task τ0’s conditional expected accrued utility density be ρ̂0(τ0,t) at time t, and preempting task τp’s expected accrued utility density be ρp¯. Task τp preempts τ0 only when the following equation is satisfied:(11)ρp¯(τp)-ρ0̂(τ0,t)>ζ,
where ζ is the preemption threshold.To further constrain preemptions, we do not allow the current task be preempted if it can complete by its deadline even it requires its worst case execution time. Preempting such tasks can delay the completion of these tasks, and potentially turn the profit into penalty if these tasks miss their deadlines. This constraint is illustrated by (12).(12)Sτ0+WEτ0≤Dτ0,
where Sτ0 is the starting time of current running task τ0. WEτ0 means the worst case execution time of τ0. Dτ0 represents τ0’s deadline.We summarize our preemption rules and present the preemptive scheduling algorithm in Algorithm3.Algorithm 3:Preemption checking.
1:input: Let τ0 be the task currently being executed, andτp be the task wants to preempt τ0, current time be t,ρ0̂(τ0,t) be the conditional expected utility density of τ0at timet, ρp¯(Cp¯) be the expected utility density of τp,Cp¯ and C0¯ are the expected execution time of τp and τ0,respectively;2:3:When a new task arrives or it is the preemption checkingpoint4:Ifρp¯(Cp¯)-ρ0̂(τ0,t)>ζthen5:  Check what isτ0’s worst case finish time;6:IfSτ0+WEτ0≤Dτ0then7:   Preemption not allowed;8:else9:   Preemption allowed;10:end if11:end ifFrom Algorithm3, when a preemption checking point is reached or when a new task arrives, scheduler first compares the preempting task’s expected utility density ρp¯(Cp¯) with the current running task’s conditional expected utility density ρ0̂(τ0,t). If the preempting task’s expected utility density exceeds the current running task’s conditional expected utility density by a preemption threshold, then the scheduler further checks if the current running task can complete its execution in its worst case or not. If the current running task can be completed even in its worst case, no preemption is allowed in order to protect the current running task, since this current running task will absolutely contribute positive utility to the system. Otherwise, the preemption may postpone the current running task and result in a penalty because of missing its deadline.


## 5. Experiments

In this section, we use experiments to investigate the performance of our proposed algorithms. The following six representative scheduling approaches were implemented and compared:(i)
EDF: the execution order of tasks are determined based on the EDF scheduling policy;(ii)
GUS [8]: the execution order of tasks is determined by the expected utility density, or the accrued utility per unit time;(iii)
PP: this is a previous approach developed based on a metric calledRisk Factor [19]. It adopts similar system models as those used in this paper;(iv)
RR: the risk/reward approach described in [18]. This is a utility accrual approach that allows the utility value to be negative (e.g., similar to Figure 1(b));(v)
PPOC: this is the scheduling approach (i.e., Algorithm1) built upon the utility metric that is developed based on the opportunity cost;(vi)
PPS: this is the scheduling approach built upon the speculated utility-based metric as discussed in Section3.2.


### 5.1. Experiment Setup

The test cases in our experiments were randomly generated. Specifically, each taskτ=([B,W],f(T),G(t),L(t),D) was randomly generated as below.(i)
B, W, and D were randomly generated such that they are uniformly distributed within interval of [1,10], [30,50], and [40,50], respectively.(ii)
The execution time of a task is assumed to be evenly distributed between interval of[B,W], that is, f(t)=1/(W-B).(iii)
G and  L were assumed to be linear functions, that is, G(t)=ag(-t+D) in the range of [0,D] and L(t)=alt. The gradient for G(t) and L(t), that is, ag and al were randomly picked from the interval of [4,10] and [1,5], respectively.(iv)
Task release times follow the Poisson distribution withμ=1.(v)
Preemption check interval lengthLint is set to be 1.(vi)
Preemption thresholdζ is set to be 0.(vii)
The utility density thresholdδ is set to 0.We conducted several different groups of experiments to study and compare the performance of different approaches under different conditions. The results are reported as follows.


### 5.2. Overall Performance Comparison

We first constructed 5 groups of experiments to study the overall performance of our proposed nonpreemptive scheduling algorithms. Each group has 1000 task sets, each of which consists of 20 tasks. The six different nonpreemptive scheduling algorithms were applied to the same task sets. The overall utility, the total profit, and the total penalty by each scheduling approach were collected and plotted in Figures5(a), 5(b), and 5(c), respectively. For ease of presentation, the experimental results are normalized to that by PPS.The comparison of total utility, profit, and penalty by different nonpreemptive scheduling approaches.
(a)
Total utility(b)
Total profit(c)
Total penaltyFigure5(a) clearly shows that both PPOC and PPS can significantly outperform the other scheduling approaches. It is not surprising that, from Figure 5(c), we can see that the penalty-conscious approaches, that is, PP, PPOC, and PPS, are more effective to control the penalty than the other three, that is, EDF, GUS, and RR. PPOC and PPS are particular effective in penalty control. It is interesting to note from Figures 5(b) and 5(c)  that, while the profits obtained by PPOC and PPS are comparable or even inferior to the other approaches, the penalties are dramatically decreased. This is because tasks that would potentially lead to high penalty are declined or discarded at early stages of their execution. As a result, the overall utilities are significantly higher than other approaches. As shown in Figure 5(a), with more elaborate scheduling algorithms to formulate the expected utility more accurately, and thus to make more appropriate decisions in task acceptation, abortion, and discard, PPOC improve upon PP by more than 70%, and PPS improve upon PP by more than 120% on average.When comparing PPOC nonpreemptive and PPS nonpreemptive, we can see from Figure5(a) that PPS is slightly better than PPOC. We can tell that the speculation-based utility metric predominant the opportunity cost metric in the control of penalty. The speculation order plays the major role in predicting the high risk of penalty.


### 5.3. Arrival Burst Impacts

We next studied the performance of our nonpreemptive scheduling methods under different burst conditions. In this experiment, we set the number of tasks to 20 and varied the expected number of occurrences within a unit interval,μ, from 1 to 5. By changing μ, we essentially changed the interval length between task arrivals. Figure 6 shows the results of the 1000 task sets’ total utility with different values of μ achieved by the nonpreemptive scheduling algorithms.Figure 6
The total utility with differentμ from nonpreemptive scheduling algorithms.Whenμ increases from 1 to 5, the number of task that comes within the same length of interval decreases, so the ready queue becomes less crowded and the overall workload reduces. The reduction in workload also helps lower down the deadline miss rate. More tasks can contribute positive profits instead of negative penalties to the system. Therefore, the total accrued utility is improved. From Figure 6, we can see that all the methods have a better performance as μ increases, and PPS and PPOC significantly outperform the other approaches.


### 5.4. Utility Density Threshold Effect

We further studied the impacts of the utility density thresholdδ on the scheduling performance. As indicated in Section 3, the threshold δ plays an important role in task admission, abortion, and execution. The larger the threshold, the smaller the number of tasks can be accepted and executed, and the smaller the penalty the system will suffer. To study this impact, we conducted another set of experiments. We generated task sets as before but changed the threshold from −30 to 30, with an interval of 5. The total utilities were collected and shown in Figure 7. It shows the effects on the 1000 task sets’ total utilities at various threshold values.Figure 7
The total utility varies with the threshold.It is interesting to see that the highest utility does not always occur at the point when the threshold equals zero. With the help from the figure, we can tell that the highest utility seldom occurs at the point with the lowest or the highest threshold value. The lower the threshold, the more tasks can be accepted to the system and get executed. This helps to improve the value of potential total profit. However, having more tasks accepted into a ready queue may potentially increase the potential penalty cost as many jobs can not meet their deadlines. On the contrary, using a higher threshold helps control the potential penalty but may limit the potential total profit that can be obtained. As a result, the total utility is a tradeoff between the two as shown in Figure7. From Figure 7 we can see the significant impact that the different threshold values may have on the overall performance. How to choose an appropriate threshold value for a specific task set to strike the balance between the profit and penalty and hence achieve the optimal accrued utility is an interesting problem and needs further study.


### 5.5. Effects of Preemption-Checking Interval LengthLint and Preemption Threshold ζ

In order to design a proper preemptive approach, we studied the preemption effects that come from variablesLint and ζ. We want to avoid aggressive preemptions. In Algorithm 3, when there is a high-priority task that wants to preempt the current running task, our scheduler first tries to protect the current running task and guarantee the current running task to finish execution without being preempted. The first constraint we added on preemptions is the preemption checking interval. In Figure 8, the result shows the effect of Lint. Even though there are bumps in the figure, it demonstrates a major trend that the smaller the preemption checking interval, the higher the system utility.Figure 8
Preemption checking interval effect withλ=1, task number = 20 each group, and ζ = 0.A preemption thresholdζ is another preemption constraint. Its effect is reflected by Figure 9. An optimal preemption threshold for a special task set can be hard to find. As shown in this figure, similar to the utility density threshold (δ) effect, the optimal value is seldom achieved at the two extremes. For this particular data set we tested, the best preemption threshold value ζ is around 2.Figure 9
Preemption threshold effect withλ=1, task number = 20, and Lint = 1.High preemption number does not mean better performance. Besides overheads generated by preemptions, potential penalties caused by preemptions may also be large. A set of carefully designed preemption rules can significantly improve the preemption performance. Results are shown in the next subsection.


### 5.6. Preemption versus Nonpreemption

Finally we compare our nonpreemptive and preemptive scheduling approaches. Figure10 shows comparisons in details between nonpreemptive and preemptive scheduling approaches with the same task sets. It illustrates that PPS has the highest system utility, followed by the preemptive approach, then PPOC obtains the lowest system utility among these three approaches. Even though from Figure 10(b) we can tell that preemptive approach achieves the highest profit among them, it does not have a good control on penalty as PPS does. This results in a lower system utility in the preemptive approach than that in PPS. Nevertheless, Figure 10(b) illustrates the value of constrained preemptions for increasing system-accrued utility, since our preemptive scheduler always selects high-priority tasks to run at proper time.Comparison between PPS nonpreemptive and preemptive scheduling under the burstiness effect.
(a)
Comparison of total utility(b)
Comparison of total profit(c)
Comparison of total penaltyFigure11 highlights the importance of preemption constraints. Some improper preemption instances postpone the running task’s natural execution, in which a task may meets its deadline constraint without being preempted. In addition, it is hard to predict the future condition of the postponed task. Preemptions may help maximize the accrued system utility since the scheduler always runs high-priority tasks first, whereas whether to allow preemptions happen needs prudential measures. The observation from Figure 11 is that by applying constraints on preemptions, we successfully improve the performance of the preemptive scheduling approach.Figure 11
Comparison between constrained preemption approach and unconstrained preemption approach.


## 5.1. Experiment Setup

The test cases in our experiments were randomly generated. Specifically, each taskτ=([B,W],f(T),G(t),L(t),D) was randomly generated as below.(i)
B, W, and D were randomly generated such that they are uniformly distributed within interval of [1,10], [30,50], and [40,50], respectively.(ii)
The execution time of a task is assumed to be evenly distributed between interval of[B,W], that is, f(t)=1/(W-B).(iii)
G and  L were assumed to be linear functions, that is, G(t)=ag(-t+D) in the range of [0,D] and L(t)=alt. The gradient for G(t) and L(t), that is, ag and al were randomly picked from the interval of [4,10] and [1,5], respectively.(iv)
Task release times follow the Poisson distribution withμ=1.(v)
Preemption check interval lengthLint is set to be 1.(vi)
Preemption thresholdζ is set to be 0.(vii)
The utility density thresholdδ is set to 0.We conducted several different groups of experiments to study and compare the performance of different approaches under different conditions. The results are reported as follows.


## 5.2. Overall Performance Comparison

We first constructed 5 groups of experiments to study the overall performance of our proposed nonpreemptive scheduling algorithms. Each group has 1000 task sets, each of which consists of 20 tasks. The six different nonpreemptive scheduling algorithms were applied to the same task sets. The overall utility, the total profit, and the total penalty by each scheduling approach were collected and plotted in Figures5(a), 5(b), and 5(c), respectively. For ease of presentation, the experimental results are normalized to that by PPS.The comparison of total utility, profit, and penalty by different nonpreemptive scheduling approaches.
(a)
Total utility(b)
Total profit(c)
Total penaltyFigure5(a) clearly shows that both PPOC and PPS can significantly outperform the other scheduling approaches. It is not surprising that, from Figure 5(c), we can see that the penalty-conscious approaches, that is, PP, PPOC, and PPS, are more effective to control the penalty than the other three, that is, EDF, GUS, and RR. PPOC and PPS are particular effective in penalty control. It is interesting to note from Figures 5(b) and 5(c)  that, while the profits obtained by PPOC and PPS are comparable or even inferior to the other approaches, the penalties are dramatically decreased. This is because tasks that would potentially lead to high penalty are declined or discarded at early stages of their execution. As a result, the overall utilities are significantly higher than other approaches. As shown in Figure 5(a), with more elaborate scheduling algorithms to formulate the expected utility more accurately, and thus to make more appropriate decisions in task acceptation, abortion, and discard, PPOC improve upon PP by more than 70%, and PPS improve upon PP by more than 120% on average.When comparing PPOC nonpreemptive and PPS nonpreemptive, we can see from Figure5(a) that PPS is slightly better than PPOC. We can tell that the speculation-based utility metric predominant the opportunity cost metric in the control of penalty. The speculation order plays the major role in predicting the high risk of penalty.


## 5.3. Arrival Burst Impacts

We next studied the performance of our nonpreemptive scheduling methods under different burst conditions. In this experiment, we set the number of tasks to 20 and varied the expected number of occurrences within a unit interval,μ, from 1 to 5. By changing μ, we essentially changed the interval length between task arrivals. Figure 6 shows the results of the 1000 task sets’ total utility with different values of μ achieved by the nonpreemptive scheduling algorithms.Figure 6
The total utility with differentμ from nonpreemptive scheduling algorithms.Whenμ increases from 1 to 5, the number of task that comes within the same length of interval decreases, so the ready queue becomes less crowded and the overall workload reduces. The reduction in workload also helps lower down the deadline miss rate. More tasks can contribute positive profits instead of negative penalties to the system. Therefore, the total accrued utility is improved. From Figure 6, we can see that all the methods have a better performance as μ increases, and PPS and PPOC significantly outperform the other approaches.


## 5.4. Utility Density Threshold Effect

We further studied the impacts of the utility density thresholdδ on the scheduling performance. As indicated in Section 3, the threshold δ plays an important role in task admission, abortion, and execution. The larger the threshold, the smaller the number of tasks can be accepted and executed, and the smaller the penalty the system will suffer. To study this impact, we conducted another set of experiments. We generated task sets as before but changed the threshold from −30 to 30, with an interval of 5. The total utilities were collected and shown in Figure 7. It shows the effects on the 1000 task sets’ total utilities at various threshold values.Figure 7
The total utility varies with the threshold.It is interesting to see that the highest utility does not always occur at the point when the threshold equals zero. With the help from the figure, we can tell that the highest utility seldom occurs at the point with the lowest or the highest threshold value. The lower the threshold, the more tasks can be accepted to the system and get executed. This helps to improve the value of potential total profit. However, having more tasks accepted into a ready queue may potentially increase the potential penalty cost as many jobs can not meet their deadlines. On the contrary, using a higher threshold helps control the potential penalty but may limit the potential total profit that can be obtained. As a result, the total utility is a tradeoff between the two as shown in Figure7. From Figure 7 we can see the significant impact that the different threshold values may have on the overall performance. How to choose an appropriate threshold value for a specific task set to strike the balance between the profit and penalty and hence achieve the optimal accrued utility is an interesting problem and needs further study.


## 5.5. Effects of Preemption-Checking Interval LengthLint and Preemption Threshold ζ

In order to design a proper preemptive approach, we studied the preemption effects that come from variablesLint and ζ. We want to avoid aggressive preemptions. In Algorithm 3, when there is a high-priority task that wants to preempt the current running task, our scheduler first tries to protect the current running task and guarantee the current running task to finish execution without being preempted. The first constraint we added on preemptions is the preemption checking interval. In Figure 8, the result shows the effect of Lint. Even though there are bumps in the figure, it demonstrates a major trend that the smaller the preemption checking interval, the higher the system utility.Figure 8
Preemption checking interval effect withλ=1, task number = 20 each group, and ζ = 0.A preemption thresholdζ is another preemption constraint. Its effect is reflected by Figure 9. An optimal preemption threshold for a special task set can be hard to find. As shown in this figure, similar to the utility density threshold (δ) effect, the optimal value is seldom achieved at the two extremes. For this particular data set we tested, the best preemption threshold value ζ is around 2.Figure 9
Preemption threshold effect withλ=1, task number = 20, and Lint = 1.High preemption number does not mean better performance. Besides overheads generated by preemptions, potential penalties caused by preemptions may also be large. A set of carefully designed preemption rules can significantly improve the preemption performance. Results are shown in the next subsection.


## 5.6. Preemption versus Nonpreemption

Finally we compare our nonpreemptive and preemptive scheduling approaches. Figure10 shows comparisons in details between nonpreemptive and preemptive scheduling approaches with the same task sets. It illustrates that PPS has the highest system utility, followed by the preemptive approach, then PPOC obtains the lowest system utility among these three approaches. Even though from Figure 10(b) we can tell that preemptive approach achieves the highest profit among them, it does not have a good control on penalty as PPS does. This results in a lower system utility in the preemptive approach than that in PPS. Nevertheless, Figure 10(b) illustrates the value of constrained preemptions for increasing system-accrued utility, since our preemptive scheduler always selects high-priority tasks to run at proper time.Comparison between PPS nonpreemptive and preemptive scheduling under the burstiness effect.
(a)
Comparison of total utility(b)
Comparison of total profit(c)
Comparison of total penaltyFigure11 highlights the importance of preemption constraints. Some improper preemption instances postpone the running task’s natural execution, in which a task may meets its deadline constraint without being preempted. In addition, it is hard to predict the future condition of the postponed task. Preemptions may help maximize the accrued system utility since the scheduler always runs high-priority tasks first, whereas whether to allow preemptions happen needs prudential measures. The observation from Figure 11 is that by applying constraints on preemptions, we successfully improve the performance of the preemptive scheduling approach.Figure 11
Comparison between constrained preemption approach and unconstrained preemption approach.


## 6. Conclusions

The popularity of Internet has grown enormously, which has presented a great opportunity for providing real-time services over Internet. Considering the tremendously large scale of the Internet infrastructure, it is necessary that not only the profit but also the cost of real-time task executions should be taken into consideration during the resource management process. Our experimental results clearly show that the traditional utility accrued approaches become ineffective.In this paper, we first present two novel nonpreemptive utility accrued scheduling approaches upon a metric developed according to theopportunity cost concept and a speculation-based metric for expected utility, respectively. Then, a constrained preemptive approach is proposed. Our scheduling algorithms carefully choose highly profitable tasks to execute and aggressively remove tasks that potentially lead to large penalty. Our extensive experimental results clearly show that our proposed algorithms can significantly outperform the traditional EDF approach, the traditional utility accrued approaches, and an earlier heuristic approach based on a similar profit and penalty aware task model.



---

*Source: 681985-2012-07-01.xml*