# Dynamic Soft Real-Time Scheduling with Preemption Threshold for Streaming Media

Authors: Wenle Wang; Yuan Wang; JiangYan Dai; Zhonghua Cao
Journal: International Journal of Digital Multimedia Broadcasting
 (2019)

---

## Abstract

Over the last decades, the advancements in networking technology and new multimedia devices have motivated the research on efficient video streaming mechanisms under wireless. We consider combing soft real-time video streaming scheduling with threshold to minimize the ineffective preemption. Based on the value density and urgency of soft real-time task, the dynamic scheduling with preemption threshold strategy (DSPT) is proposed in the paper. By analyzing the response time and preemption relationship of tasks, the preemption thresholds are assigned. Simulation results show that the DSPT strategy achieves improvements about success rate, delay time, and benefit of the system.


---

## Body

## 1. Introduction

With the advancements in networking technology and new multimedia devices, video streaming mechanisms under various network and devices have attracted more and more attention. Nowadays, multimedia communications over the internet especially wireless network are the necessarily part of modern life. Many researchers have studied on video streaming management over wireless, including video coding [1–4], network coding [5–8], and wireless communication [9–11]. In wireless networks, video streaming applications are almost the largest consumer of mobile wireless data, so scheduling video streaming in wireless networks is very important.Video streaming scheduling in wireless networks has been developed for recent years, such as given quality on service mechanisms [12–16] and real-time adaptive [17–19]. Many of video streaming scheduling studies are about hard real-time [20–22] that requires all the packets complete before the deadline; otherwise the packets will be considered invalid and dropped. However, for some actual video streaming media application, the packets of the transmission with delay can still bring a certain service and these packets can be forwarded and represented by soft real-time tasks. The soft real-time task model with value function is also applicable to video streaming with delay [23, 24]. For soft real-time scheduling, task executing under delay-constrained can bring goodput and benefit.Generally, real-time scheduling can be divided into preemptive scheduling and non-preemptive scheduling according to whether the task can preempt each other or not. In a dynamic network, the preemptive method is more applicable. However, arbitrary preemption between tasks will affect the scheduling performance. Therefore, considering the drawbacks of the two methods, a compromise approach is utilized to limit the arbitrary or invalid preemption by setting preemption threshold. Furthermore, the limited preemption scheduling strategy is a correct choice for improving the performance.Soft real-time task model is conducted for the video streaming under wireless. We propose a soft real-time threshold preemption scheduling strategy by combining value density and urgency for video streaming in the paper. Simulation results show that the strategy can improve the goodput, reduce the delay, and increase the benefit comparing with the EDF and LSF methods.In this paper, we only consider the CPU in the system scheduling and ignore the time caused by context switching. We study the video streaming transmission problem of gateway devices in wireless network at the specific level of packets of transport tiers.Organization. The structure of the paper is organized as follows: Section 2 describes the related work. Section 3 designs the structure of DSPT strategy. Section 4 defines the task model and problem analysis in detail. Section 5 is priority and preemption thresholds description. The details of scheduling based on preemption threshold are introduced in Section 6. The simulation setup and results are given in Section 7. Finally, the conclusions and future work are discussed.


## 2. Related Work

In wireless networks, the scheduling strategy should ensure high quality. For this purpose, lots of studies were proposed. The works in [1, 2] enabled high-quality HTTP streaming, in which video pre-encoded into segments that can only start to play if all the packet have received. However, much packet lost for video application in the above work. The literature [3] optimized the dynamic HTTP live streaming service by segment adaption. Some literatures proposed video streaming scheduling using video coding with network coding. For example, the literatures [5, 6] optimized video streaming by combining video coding and network coding for P2P network and distributed network, respectively. However, it might suffer from bandwidth inefficiencies because of unrecoverable packets. The work [7] proposed streaming scheduling for multiple server by Markov decision processes, but it had high computational complexity. In [9], the authors designed a crosslayer optimization scheme for dynamic wireless video streaming. However, these methods cannot contain the packet urgency for streaming control.With the emergence of various networks, the research on heterogeneous wireless networks had been motivated. The literatures [11, 19] studied the concurrent multipath transfer of the capacity-limited heterogeneous wireless platform. Another work [17] proposed a real-time adaptive video streaming deliver method over multiple wireless networks. In [23, 24], delay-constrained video transmission with multiple interface in heterogeneous network was proposed.Some researchers considered video streaming as hard real-time; that is, the streaming packet missing the deadline will be considered invalid. For example, the literature [20] proposed a feedback-based control approach under hard real-time workload to improve admission rate. In literatures [18, 21], the author studied in hard real-time video stream allocation to improve the utilization of video decoding. Nevertheless, most video streaming data meets the characteristics of soft real-time task, so delay-constrained of video is considered acceptable in applications.


## 3. DSPT Detail Design

We consider video streaming deliver over wireless networks as soft real-time scheduling. The streaming packet is expressed as task, and its quality and urgency are the metrics in scheduling. The task’s delay will affect the quality. Therefore, we introduced the value to measure the quality. Response time analysis (RTA) is used to test the schedulability of real-time task, and the preemption threshold-based scheduling approach is to reduce invalid preemption among tasks. The scheduling algorithm can effectively reduce the delay and improve the success rate and benefit. The flow diagram of DSPT strategy is shown in Figure1. In this paper, we assume that the value function Vi(t) of the soft real-time task Ti keeps unchanged in the interval [ai,di) and decreases linearly in the interval. While executing in the interval [di,cri), the task Ti is not allowed to be preempted in order to protect the execution of the task.Figure 1
The flow diagram of DSPT strategy.Contribution 1.
We construct the priority assignment function combining value density and urgency, improving the success and quality of task soft real-time scheduling.Contribution 2.
We propose the task scheduling strategy DSPT based on preemption threshold, which can obtain better performance.


## 4. Task Model and Analysis

Considering video streaming with delay-constrained under wireless, we conduct soft real-time task model in this section.


### 4.1. Soft Real-Time Task Model

We refer to a task as an aperiodic task model, and the task is soft real-time. This section provides the definitions of soft real-time task model used in the paper.Task T i: An aperiodic task Ti is defined as a triple Ti:={ai,eti,di,cri}, where ai,eti,di, and cri are the arrival time, the estimated execution time, the relative deadline, and the critical time of task Ti.Having executed time h t i: hti denotes that the task has been executing hti units at time t0.Required execution time r t i: rti denotes the remaining execution time of task Ti. Thus, it meets rti=eti-hti.Executable time l t i: lti is the executable time of the task Ti prior to its deadline di, where at the time t0(t0<di).Soft Executable time s l t i: When missed deadline di, task can continue to execute until cri. slti is the executable time prior to the critical time cri, that is, slti=cri-t0.Slack time s t i: The slack time sti denotes that the time unit after finish execution until deadline di, thus, sti=lti-rti. sti remains stable when the task Ti is in execution, and sti decreases when the task Ti is preempted. Once sti<0, the task Ti cannot finish before di.Delay Time d t i: The delay time dti denotes the finish time of task Ti after di. At the time t0(di<t0≤cri), it meets dti=t0-di.Priority p r i: pri is defined as the priority of task Ti. The larger pri’s value, the higher Ti’s priority.Threshold θ i: θi is the preemption threshold of task Ti, where θi≥pri.Value function V i ( t ): Vi(t) defines the value of the system for executing Ti at time t, where t∈[ai,cri). The task Ti ’s value will change when Ti keeps executing, and the function Vi(t) is dynamic. Vi(t) will be analyzed in detail in Section 4.Value density function V D i ( t ): VDi(t) is the ratio between Vi(t) and required execution time rti, that is, VDi(t)=Vi(t)/rti. Obviously, VDi(t) is growing with the decreasing of rti.


### 4.2. Value and Value Density Function of Soft Real-Time Task

According to assumption, the value functionVi(t) of the soft real-time task Ti at time t is defined as(1)Vit=Vit<dicri-tcri-di×Vidi≤t<criFrom (1), we can see that when t<di, Vi(t) is stable at Vi; however when di≤t<cri, Vi(t) is linearly diminishing until 0.Value density functionVDi(t) is denoted as(2)
V
D
i
t
=
V
i
r
t
i
t
<
d
i
c
r
i
-
t
c
r
i
-
d
i
×
V
i
r
t
i
d
i
≤
t
<
c
r
iWe can see that VDi(t) is not only concerned with Vi(t) but also related to rti. According to the definition, rti=eti-hti. As we known, when the task Ti is executing, rti decreases with the growing of the time t. And when the task Ti is blocked, the rti remains unchanged. The discussion of VDi(t) is as follows: (1)
t<di. Within this interval, VDi(t)=Vi/rti. When Ti is executing, VDi(t) grows with the decreasing of rti. While Ti is blocked, VDi(t) remains unchanged.(2)
di≤t<cri. In this interval, VDi(t) can be derived as follows: VDi(t)=Vi/rti×cri-t/cri-diFrom the above expression, the affect part of theVDi(t) is(3)cri-trtiBecause the task in scheduler can finish without any interference of any other task,cri-t/rti>1. In this case, if the task Ti keeps executing, the molecular part and the denominator part of (3) decrease at the same time. Further analysis is needed:
(1)
Att0 time, (3) is recorded as: cri-t0/rti. When task Ti has executed Δt from t0, (3) is formulated to cri-(t0+Δt)/rti-Δt. Because slti/rti>1, then cri-(t0+Δt)/rti-Δt>cri-t0/rti, where Δt>0. That is, when task Ti is executing, VDi(t) grows with the decreasing of rti.(2)
When the taskTi is blocked, the molecular part of (3) decreases with the growth of t, while the denominator rti is kept unchanged. Thus, (3) decreases with the growth of t. Therefore, Theorem 1 can be obtained.Theorem 1.
While the task keeps executing in the progress, it increases with timet.


### 4.3. Analysis of the Task’s Urgency

The more urgency of the task is, the sooner execution is required.Definition 2.
At anyt, the urgency Ugi(t) of task Ti is defined as Ugi(t)=1/esti.U g i ( t ) is affected by sti, the discussion is as follows:(1)
WhenTi remains in execution, sti does not change with the growing of the time t and then Ugi(t) remains unchanged.(2)
WhenTi is blocked, sti decreases with the growth of t, which makes Ugi(t) increase.


## 4.1. Soft Real-Time Task Model

We refer to a task as an aperiodic task model, and the task is soft real-time. This section provides the definitions of soft real-time task model used in the paper.Task T i: An aperiodic task Ti is defined as a triple Ti:={ai,eti,di,cri}, where ai,eti,di, and cri are the arrival time, the estimated execution time, the relative deadline, and the critical time of task Ti.Having executed time h t i: hti denotes that the task has been executing hti units at time t0.Required execution time r t i: rti denotes the remaining execution time of task Ti. Thus, it meets rti=eti-hti.Executable time l t i: lti is the executable time of the task Ti prior to its deadline di, where at the time t0(t0<di).Soft Executable time s l t i: When missed deadline di, task can continue to execute until cri. slti is the executable time prior to the critical time cri, that is, slti=cri-t0.Slack time s t i: The slack time sti denotes that the time unit after finish execution until deadline di, thus, sti=lti-rti. sti remains stable when the task Ti is in execution, and sti decreases when the task Ti is preempted. Once sti<0, the task Ti cannot finish before di.Delay Time d t i: The delay time dti denotes the finish time of task Ti after di. At the time t0(di<t0≤cri), it meets dti=t0-di.Priority p r i: pri is defined as the priority of task Ti. The larger pri’s value, the higher Ti’s priority.Threshold θ i: θi is the preemption threshold of task Ti, where θi≥pri.Value function V i ( t ): Vi(t) defines the value of the system for executing Ti at time t, where t∈[ai,cri). The task Ti ’s value will change when Ti keeps executing, and the function Vi(t) is dynamic. Vi(t) will be analyzed in detail in Section 4.Value density function V D i ( t ): VDi(t) is the ratio between Vi(t) and required execution time rti, that is, VDi(t)=Vi(t)/rti. Obviously, VDi(t) is growing with the decreasing of rti.


## 4.2. Value and Value Density Function of Soft Real-Time Task

According to assumption, the value functionVi(t) of the soft real-time task Ti at time t is defined as(1)Vit=Vit<dicri-tcri-di×Vidi≤t<criFrom (1), we can see that when t<di, Vi(t) is stable at Vi; however when di≤t<cri, Vi(t) is linearly diminishing until 0.Value density functionVDi(t) is denoted as(2)
V
D
i
t
=
V
i
r
t
i
t
<
d
i
c
r
i
-
t
c
r
i
-
d
i
×
V
i
r
t
i
d
i
≤
t
<
c
r
iWe can see that VDi(t) is not only concerned with Vi(t) but also related to rti. According to the definition, rti=eti-hti. As we known, when the task Ti is executing, rti decreases with the growing of the time t. And when the task Ti is blocked, the rti remains unchanged. The discussion of VDi(t) is as follows: (1)
t<di. Within this interval, VDi(t)=Vi/rti. When Ti is executing, VDi(t) grows with the decreasing of rti. While Ti is blocked, VDi(t) remains unchanged.(2)
di≤t<cri. In this interval, VDi(t) can be derived as follows: VDi(t)=Vi/rti×cri-t/cri-diFrom the above expression, the affect part of theVDi(t) is(3)cri-trtiBecause the task in scheduler can finish without any interference of any other task,cri-t/rti>1. In this case, if the task Ti keeps executing, the molecular part and the denominator part of (3) decrease at the same time. Further analysis is needed:
(1)
Att0 time, (3) is recorded as: cri-t0/rti. When task Ti has executed Δt from t0, (3) is formulated to cri-(t0+Δt)/rti-Δt. Because slti/rti>1, then cri-(t0+Δt)/rti-Δt>cri-t0/rti, where Δt>0. That is, when task Ti is executing, VDi(t) grows with the decreasing of rti.(2)
When the taskTi is blocked, the molecular part of (3) decreases with the growth of t, while the denominator rti is kept unchanged. Thus, (3) decreases with the growth of t. Therefore, Theorem 1 can be obtained.Theorem 1.
While the task keeps executing in the progress, it increases with timet.


## 4.3. Analysis of the Task’s Urgency

The more urgency of the task is, the sooner execution is required.Definition 2.
At anyt, the urgency Ugi(t) of task Ti is defined as Ugi(t)=1/esti.U g i ( t ) is affected by sti, the discussion is as follows:(1)
WhenTi remains in execution, sti does not change with the growing of the time t and then Ugi(t) remains unchanged.(2)
WhenTi is blocked, sti decreases with the growth of t, which makes Ugi(t) increase.


## 5. Priority and Preemption Thresholds for Soft Real-Time Tasks

Task scheduling is driven by priority, while task priority function combines value density with urgency.


### 5.1. The Construction of Task’s Priority Function

Considering the urgency and the benefits of task, task scheduling is based on priority. Only the completed task can gain value, so relative to the value density, the urgency is more important. In system scheduling, the first consideration is system success rate and then is value brought by tasks. It means that urgency is given much greater weight than value density in priority function. Therefore, we use exponential weighting to the urgency while using logarithmic weighting to the value density. The function of priority assignment can be rewritten to(4)pri=Ugit×ln1+VDitBased on the above analysis of value densityVDi(t) and urgency Ugi(t), we can conclude that(1)
WhenTi executes at interval [ai,di), pri satisfies(5)pri=1esti×ln⁡1+VirtiFurther analysis is needed:
(1)
According to Theorem1, when Ti keeps running, ln⁡[1+Vi/rti] increases. Because sti remain unchanged with time t growing. Therefore, (5) keeps increasing.(2)
OnceTi is preempted, 1/esti augments as time t grows, while ln⁡[1+Vi/rti] remain unchanged, then (5) keeps increasing. Based on above, pri increases as time t at interval [ai,di).(2)
WhenTi executes at [di,cri), its slack time is slti and satisfies(6)pri=1esti×ln1+cri-tcri-d×Virti
(1)
In the process of runningTi, with the growing of the time t, cri-t/cri-di×Vi/rti increases while slti remains unchanged and then (6) keeps increasing.(2)
WhenTi has been preempted, with the growing of time t, slti decreases and 1/eslti augments accordingly while cri-t/cri-di×Vi/rti reduces. Further discussion of Eq. (6) is needed. At moment t, slti=cri-t-rti<cri-di. After task Ti has been executed with Δt, there is pri(Δt)=1/ecri-t-rti-Δt×ln⁡[1+cri-t-Δt/cri-di×Vi/rti], where cri-t-rti-Δt>0. And 1/ecri-t-rti-Δt is exponential growth, in which growth rate is faster than ln[1+cri-t-Δt/cri-di×Vi/rti]’s logarithmic descent rate significantly. Therefore, pri(Δt) increases when Δt grows.


### 5.2. Preemption Threshold Selection for Task

The selection of preemption thresholds directly affects the scheduling algorithm. We select preemption threshold by analyzing the task’s response time.Definition 3.
TaskTi’s Effect Job Set is denoted as EJSi. During the execution of task Ti, all task of the sets can preempt Ti, which are defined as Effect Job Set (EJSi), satisfying EJSi=Tm∣(prim>prii∧(Dm>Ai)∧(Am<Di).
Response timeRti of task Ti contains two parts: estimated execution time eti and sum of the remaining execution time of the effect job sets EJSi:(7)Rti=eti+∑Tj∈EJSirtjBy analyzing the response time of Ti, its threshold θi can be obtained under the condition which can be scheduled. The procedure of preemption threshold selection is shown in Algorithm 1, where Tmax is the highest priority task.Algorithm 1:Compute θi.
1:  Calculateθi using (7); 2:θi=pri; 3:WHILE (Rti≤cri) DO 4:IF (θi>prmax) 5:    return not scheduled; 6:ELSE 7:IFTi is executing and sti<stmax 8:θi:=prmax; 9:      returnθi; 10:ELSE 11:     CalculateRti using (7) 12:END IF 13:END IF 14:END WHILE 15:   returnθiObviously, the computational complexity of Algorithm1 is O(n).


## 5.1. The Construction of Task’s Priority Function

Considering the urgency and the benefits of task, task scheduling is based on priority. Only the completed task can gain value, so relative to the value density, the urgency is more important. In system scheduling, the first consideration is system success rate and then is value brought by tasks. It means that urgency is given much greater weight than value density in priority function. Therefore, we use exponential weighting to the urgency while using logarithmic weighting to the value density. The function of priority assignment can be rewritten to(4)pri=Ugit×ln1+VDitBased on the above analysis of value densityVDi(t) and urgency Ugi(t), we can conclude that(1)
WhenTi executes at interval [ai,di), pri satisfies(5)pri=1esti×ln⁡1+VirtiFurther analysis is needed:
(1)
According to Theorem1, when Ti keeps running, ln⁡[1+Vi/rti] increases. Because sti remain unchanged with time t growing. Therefore, (5) keeps increasing.(2)
OnceTi is preempted, 1/esti augments as time t grows, while ln⁡[1+Vi/rti] remain unchanged, then (5) keeps increasing. Based on above, pri increases as time t at interval [ai,di).(2)
WhenTi executes at [di,cri), its slack time is slti and satisfies(6)pri=1esti×ln1+cri-tcri-d×Virti
(1)
In the process of runningTi, with the growing of the time t, cri-t/cri-di×Vi/rti increases while slti remains unchanged and then (6) keeps increasing.(2)
WhenTi has been preempted, with the growing of time t, slti decreases and 1/eslti augments accordingly while cri-t/cri-di×Vi/rti reduces. Further discussion of Eq. (6) is needed. At moment t, slti=cri-t-rti<cri-di. After task Ti has been executed with Δt, there is pri(Δt)=1/ecri-t-rti-Δt×ln⁡[1+cri-t-Δt/cri-di×Vi/rti], where cri-t-rti-Δt>0. And 1/ecri-t-rti-Δt is exponential growth, in which growth rate is faster than ln[1+cri-t-Δt/cri-di×Vi/rti]’s logarithmic descent rate significantly. Therefore, pri(Δt) increases when Δt grows.


## 5.2. Preemption Threshold Selection for Task

The selection of preemption thresholds directly affects the scheduling algorithm. We select preemption threshold by analyzing the task’s response time.Definition 3.
TaskTi’s Effect Job Set is denoted as EJSi. During the execution of task Ti, all task of the sets can preempt Ti, which are defined as Effect Job Set (EJSi), satisfying EJSi=Tm∣(prim>prii∧(Dm>Ai)∧(Am<Di).
Response timeRti of task Ti contains two parts: estimated execution time eti and sum of the remaining execution time of the effect job sets EJSi:(7)Rti=eti+∑Tj∈EJSirtjBy analyzing the response time of Ti, its threshold θi can be obtained under the condition which can be scheduled. The procedure of preemption threshold selection is shown in Algorithm 1, where Tmax is the highest priority task.Algorithm 1:Compute θi.
1:  Calculateθi using (7); 2:θi=pri; 3:WHILE (Rti≤cri) DO 4:IF (θi>prmax) 5:    return not scheduled; 6:ELSE 7:IFTi is executing and sti<stmax 8:θi:=prmax; 9:      returnθi; 10:ELSE 11:     CalculateRti using (7) 12:END IF 13:END IF 14:END WHILE 15:   returnθiObviously, the computational complexity of Algorithm1 is O(n).


## 6. Task Scheduling Strategy Based on Preemption Threshold

We propose a limited preemption scheduling strategy DSPT based on preemption threshold, which reduces the blocking time of the tasks by restricting preemption.Definition 4.
Sufficient and necessary conditions ofpri>θj is that task Ti can preempt task Tj.By Definition4, if task Ti preempts task Tj, there must be pri>prj.Theorem 5.
If taskTi and task Tj are not preempted, the following should be satisfied: (pri≤θj)∧(prj≤θi).Proof.
Supposing that there are two tasks,Tp and Tq, which do not preempt each other, ⌝((prp≤θq)∧(((prq≤θp))))⇒(prp>θq)∨(prq>θp) is satisfied.
There are two possible cases:(1)
Ifprp>θq, task Tp can preempt task Tq,(2)
Ifprq>θp, task Tp may be preempted by task Tq.
Obviously, tasksTp and Tq can preempt each other, in contradiction with Definition 4. Therefore, Theorem 5 can be proved.


### 6.1. Scheduling Algorithm Based On Preemption Threshold

The soft real-time dynamic task scheduling based on preemption threshold (DSPT) called Algorithm1 is to calculate the threshold and determines the scheduling queue dynamically as shown in Algorithm 2.Algorithm 2:Task scheduling.
θi: preemption threshold of Ti; pri: priority of Ti; Sj: ready tasks queue. 1≤j≤num, num is the number of tasks in the queue; Tarr: task just arriving; Texe: task in executing; Tmax: the highest priority task of Sj; 1:Tarr arrive; 2:IFnum=0; 3:Texe:=Tarr; 4:     EXECUTETexe; 5:ELSE 6:     Computeprarr using (7); 7:     FORi=1 to num DO 8:      Computepri using (5); 9:     Computeθi; 10:   SORT task inSj by prj Desc; 11:END IF 12:IFprarr>θmax 13:Texe:=Tarr; 14:IFTin in Sj can’t Finish 15:   ABORTTin; 16:ELSE 17:Texe:=Tmax; 18:   ADDTarr to Sj; 19:num++; 20:END IF 21:  EXECUTETexe; 22:END IF


### 6.2. Algorithm Complexity

There is only one loop in Algorithm2, that is, the 7th step is the loop of the length that is equal to the number of tasks in the ready queue. Thus, the computational complexity of the Algorithm 2 is O(n×m), and the computational complexity of the whole scheduling algorithm is O(n×m).


## 6.1. Scheduling Algorithm Based On Preemption Threshold

The soft real-time dynamic task scheduling based on preemption threshold (DSPT) called Algorithm1 is to calculate the threshold and determines the scheduling queue dynamically as shown in Algorithm 2.Algorithm 2:Task scheduling.
θi: preemption threshold of Ti; pri: priority of Ti; Sj: ready tasks queue. 1≤j≤num, num is the number of tasks in the queue; Tarr: task just arriving; Texe: task in executing; Tmax: the highest priority task of Sj; 1:Tarr arrive; 2:IFnum=0; 3:Texe:=Tarr; 4:     EXECUTETexe; 5:ELSE 6:     Computeprarr using (7); 7:     FORi=1 to num DO 8:      Computepri using (5); 9:     Computeθi; 10:   SORT task inSj by prj Desc; 11:END IF 12:IFprarr>θmax 13:Texe:=Tarr; 14:IFTin in Sj can’t Finish 15:   ABORTTin; 16:ELSE 17:Texe:=Tmax; 18:   ADDTarr to Sj; 19:num++; 20:END IF 21:  EXECUTETexe; 22:END IF


## 6.2. Algorithm Complexity

There is only one loop in Algorithm2, that is, the 7th step is the loop of the length that is equal to the number of tasks in the ready queue. Thus, the computational complexity of the Algorithm 2 is O(n×m), and the computational complexity of the whole scheduling algorithm is O(n×m).


## 7. Simulations and Analysis

### 7.1. Simulation Experiments

The experiment platform’s CPU is Intel dual-core 2.8 GHZ processor, and the memory is 8 GB. The operating system is Ubuntu Linux, and the source code is implemented by C language.In the experiment, we consider the aperiodic soft real-time task. Any taskTi’s arrival time ai obeys Poisson distribution (λ=4) and the estimated execution time eti is subject to [3.0,5.0] average distribution. Therefore, its relative deadline di is [1.2,1.5]×eti average distribution, its critical time cri is [1.2,1.5]×di, and its value Vi is randomly selected between [10,50].Performance indicators are included as follows:(1)
Systematic success rate (SSR):(8)SSR=NsNwhereNs denotes as the number of successful tasks and N represents the number of system overages.(2)
Average task latency rate ATDR:(9)ATDR=avg∑Ti∈TSelietiwhereTS denotes the successful task set and eli and eti denote execution latency and execution time of the success task Ti.(3)
Effective utilization Rate (EUR):(10)EUR=CTsCTwhereCTs denotes as the CPU time for successful tasks and CT represents the total CPU time in scheduling.(4)
Cumulative Value (CV):(11)CV=∑Ti∈TSViwhereTS denotes the successful task set and represents the value of the task Ti.


### 7.2. Performance Analysis

Under soft real-time environment, the preemptive threshold scheduling strategy is compared with Earliest Deadline First (EDF) method and Least Slack First (LSF) method, and the simulation results and performance are analyzed as follows.(1) Figure2 shows simulation results for SSR scheduled by DSPT, EDF and LSF. The task’s arrival interval is represented on the horizontal axis, and the vertical axis is SSR. When the arrival interval of the task is very short, the preemption among the tasks causes the SSR to be low. With the increasing of arrival interval, the preemption among tasks decreases and the SSR arguments. From Figure 2, SSR is sorted in descending order followed by DSPT, LSF, and EDF. This is due to the EDF algorithm chooses task with earliest deadline but not most urgent, which can lead to many tasks fail. While the LSF algorithm always chose the task with the shortest slack time dynamically, its unrestricted preemption causes the thrashing which can make lots of task fail. The DSPT can adapt to the system environment dynamically, and its preemption threshold can avoid the invalid preemption among tasks. (2) The simulation results of ATDR are shown in Figure 3, in which the ATDR is on the vertical axis and arrival interval is on the horizontal axis. It can be seen from Figure 3, the ATDR decreases since the arrival interval grows from 2.5, while ATDR is lower because the intervals among tasks are so short that many of these are dropped to 1.0. Moreover, EDF algorithm leads to the highest ATDR, while the DSPT method produces the lowest ATDR. Because the EDF algorithm always chooses the task with earliest deadline of slack time to execute, many tasks miss the deadline and delay. Relative to the EDF method, the LSF algorithm assigns the most urgency task to execute in time. But its unconstrained preemption may cause serious thrashing among tasks under system overload and this increases the ATDR. The DSPT approach chooses the most urgency task to execute, and limits the preemption among the tasks by the threshold, thereby reduces the delay of the task effectively.Figure 2
SSR results.Figure 3
ATDR results.(3) The simulation results for EUR scheduled by EDF, LSF, and DSPT are shown in Figure4, where the horizontal axis is task’s arrival interval and the vertical axis is EUR. The short arrival interval means intense preemption among tasks, which causes the EUR low. While the arrival interval becomes longer, there are EUR arguments as the tasks’ preemption decreases. From Figure 4, DSPT obtains the best EUR and EDF has the least EUR. Because the EDF algorithm always execute the task with earliest deadline, which causes more invalid CPU utilization than LSF along with the task failure. The DSPT using preemption threshold can improve the EUR through reducing invalid preemption of tasks.Figure 4
EUR results.(4) Figure5 plots the system’s CV as arrival interval grows. It can be seen from Figure 5, the CV increases when the arrival interval of tasks increases. DSPT obtains the highest CV, because it assigns higher executing priority of the task with high value density. The LSF method produces better CV than EDF method, because under the same system load, that more tasks finish augments CV obtained with the formal approach.Figure 5
CV results.


## 7.1. Simulation Experiments

The experiment platform’s CPU is Intel dual-core 2.8 GHZ processor, and the memory is 8 GB. The operating system is Ubuntu Linux, and the source code is implemented by C language.In the experiment, we consider the aperiodic soft real-time task. Any taskTi’s arrival time ai obeys Poisson distribution (λ=4) and the estimated execution time eti is subject to [3.0,5.0] average distribution. Therefore, its relative deadline di is [1.2,1.5]×eti average distribution, its critical time cri is [1.2,1.5]×di, and its value Vi is randomly selected between [10,50].Performance indicators are included as follows:(1)
Systematic success rate (SSR):(8)SSR=NsNwhereNs denotes as the number of successful tasks and N represents the number of system overages.(2)
Average task latency rate ATDR:(9)ATDR=avg∑Ti∈TSelietiwhereTS denotes the successful task set and eli and eti denote execution latency and execution time of the success task Ti.(3)
Effective utilization Rate (EUR):(10)EUR=CTsCTwhereCTs denotes as the CPU time for successful tasks and CT represents the total CPU time in scheduling.(4)
Cumulative Value (CV):(11)CV=∑Ti∈TSViwhereTS denotes the successful task set and represents the value of the task Ti.


## 7.2. Performance Analysis

Under soft real-time environment, the preemptive threshold scheduling strategy is compared with Earliest Deadline First (EDF) method and Least Slack First (LSF) method, and the simulation results and performance are analyzed as follows.(1) Figure2 shows simulation results for SSR scheduled by DSPT, EDF and LSF. The task’s arrival interval is represented on the horizontal axis, and the vertical axis is SSR. When the arrival interval of the task is very short, the preemption among the tasks causes the SSR to be low. With the increasing of arrival interval, the preemption among tasks decreases and the SSR arguments. From Figure 2, SSR is sorted in descending order followed by DSPT, LSF, and EDF. This is due to the EDF algorithm chooses task with earliest deadline but not most urgent, which can lead to many tasks fail. While the LSF algorithm always chose the task with the shortest slack time dynamically, its unrestricted preemption causes the thrashing which can make lots of task fail. The DSPT can adapt to the system environment dynamically, and its preemption threshold can avoid the invalid preemption among tasks. (2) The simulation results of ATDR are shown in Figure 3, in which the ATDR is on the vertical axis and arrival interval is on the horizontal axis. It can be seen from Figure 3, the ATDR decreases since the arrival interval grows from 2.5, while ATDR is lower because the intervals among tasks are so short that many of these are dropped to 1.0. Moreover, EDF algorithm leads to the highest ATDR, while the DSPT method produces the lowest ATDR. Because the EDF algorithm always chooses the task with earliest deadline of slack time to execute, many tasks miss the deadline and delay. Relative to the EDF method, the LSF algorithm assigns the most urgency task to execute in time. But its unconstrained preemption may cause serious thrashing among tasks under system overload and this increases the ATDR. The DSPT approach chooses the most urgency task to execute, and limits the preemption among the tasks by the threshold, thereby reduces the delay of the task effectively.Figure 2
SSR results.Figure 3
ATDR results.(3) The simulation results for EUR scheduled by EDF, LSF, and DSPT are shown in Figure4, where the horizontal axis is task’s arrival interval and the vertical axis is EUR. The short arrival interval means intense preemption among tasks, which causes the EUR low. While the arrival interval becomes longer, there are EUR arguments as the tasks’ preemption decreases. From Figure 4, DSPT obtains the best EUR and EDF has the least EUR. Because the EDF algorithm always execute the task with earliest deadline, which causes more invalid CPU utilization than LSF along with the task failure. The DSPT using preemption threshold can improve the EUR through reducing invalid preemption of tasks.Figure 4
EUR results.(4) Figure5 plots the system’s CV as arrival interval grows. It can be seen from Figure 5, the CV increases when the arrival interval of tasks increases. DSPT obtains the highest CV, because it assigns higher executing priority of the task with high value density. The LSF method produces better CV than EDF method, because under the same system load, that more tasks finish augments CV obtained with the formal approach.Figure 5
CV results.


## 8. Conclusions and Future Works

In this paper, we consider video streaming scheduling in wireless networks as soft real-time scheduling. The soft real-time task model has been constructed to express streaming packet and its quality, measure as value, and urgency metric are explored in scheduling. Response time analysis (RTA) approach has been used to test the task’s schedulability, and preemption threshold has been added to the schedule to release the invalid preemption. The scheduling schema DSPT can constrain the delay and improve the success ratio and benefit effectively.In future works, we want to apply our scheduling method to practical wireless networks, like 5G net, to test its practical effect. Moreover, the stream scheduling of mixed hard real-time and soft real-time characterizes are also a study work in the next step.



---

*Source: 5284968-2019-01-01.xml*