# A Smart Semipartitioned Real-Time Scheduling Strategy for Mixed-Criticality Systems in 6G-Based Edge Computing

Authors: Wenle Wang; Chengying Mao; Shuai Zhao; Yuanlong Cao; Yugen Yi; Shaolong Chen; Qinghua Liu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

With the rapid growth of 6G communication and smart sensor technology, the Internet of Things (IoT) has attracted much attention now. In the 6G-based IoT applications on the multiprocessor platform, the partitioned scheduling has been widely applied. However, these partitioned scheduling approaches could cause system resource waste and uneven workload among processors. In this paper, a smart semipartitioned scheduling strategy (SSPS) was proposed for mixed-criticality systems (MCS) in 6G-based edge computing. Besides tasks’ acceptance rate and weighted schedulability, QoS is considered in SSPS to improve the service quality of the system. The SSPS allocates tasks into each processor, and some tasks can migrate to other processors as soon as possible. By comparing with the several existing algorithms, the experimental results show that the SSPS achieves the best in the schedulability and QoS of the system.


---

## Body

## 1. Introduction

Nowadays, with the 6G wireless communication networks and various smart sensors widely applied, the IoT applications grow rapidly in a wide range of areas, including industrial robot, driverless car, and edge computing [1–5]. Especially, edge computing, a new application paradigm, is growing popular with 6G technology’s development. For these systems in 6G-based edge computing, various sensors and mobile devices with different importance or criticality levels are integrated into a single computation platform for less space and energy. Criticality is designed for assurance needed against system failure [6]. Generally, criticality can be divided into several levels, such as low and high criticality. For example, in automotive systems, the tasks brought by steering and braking sensor are safety-related high, while the tasks of multimedia players, used for infotainment, are low-criticality (LO-criticality) tasks. These systems that have components with more than one distinct criticality level are mixed-criticality systems (MCS) [7], which are the special kind of 6G-based application with multiple criticality. The task scheduling is a fundamental issue in MCS, to reconcile the conflicting requirements for resource usage. The proper task is scheduled so that all high-criticality (HI-criticality) tasks’ execution is guaranteed which is a major challenge of MCS. Because the reliability verification and the mixed criticality exist simultaneously in MCS, the traditional real-time scheduling algorithms cannot be directly adopted [8, 9].With the prompt of computing requirements, the platforms of MCS are migrating from a single processor to multiprocessor hardware. MCS scheduling on multiprocessors can be mainly divided into global scheduling [10–12] and partitioned scheduling [13–17]. Fully global scheduling, because of task migration globally, has an overhead of the context switching and associated caches, while purely partitioned scheduling, in which some processors are too busy and others are too idle because of forbidden migration, causes waste of system resources [18]. Following this, the researchers mixed the above two scheduling methods and proposed the semipartitioned scheduling strategy [19–21]. The semipartitioned algorithms apply two-phase allocations for the different system criticality modes. During a phase of criticality mode update, the executing low-criticality (LO-criticality) tasks (jobs) will be aborted and new ones can be executed on a different processor, and thus, these jobs’ deadlines are met to achieve better schedulability of system.However, in most existing MCS semipartitioned scheduling algorithms, when the system criticality mode switches intoHI-criticality from LO-criticality, the LO-criticality tasks are directly discarded to ensure HI-criticality tasks’ completion [22–24], which seem too negative. Firstly, LO-criticality levels are not noncritical, and dropping the executing LO-criticality tasks may damage the system’s acceptance rate. During the scheduling process, the processors could be so idle that they can be assigned to perform LO-criticality tasks and thereby improving system utilization and task acceptance [25, 26].Furthermore, acceptance rate and utilization rate are the main schedulability concerning parameters in MCS, to ensure theHI-criticality tasks’ completion. However, for tasks with the identical criticality, they can have different influences to MCS in actual applications, where some tasks are more significant or have higher quality of service (QoS) to a certain extent. To describe the QoS property of task, a notion, for example, value [27, 28], is usually used. The higher the value, the better the quality brought by task. And calculative value brought by finished tasks is recorded as TV to respect the whole tasks’ QoS under scheduling algorithm [29, 30].


### 1.1. Organization

The paper’s structure is listed as follows: the related work is described in Section2. Section 3 describes the paper’s overall framework. Section 4 defines the proposed MCS model and notation in detail. We analyze the schedulability of tasks in MCS in Section 5. Section 6 designs the task priority assignment. The detail of the proposed scheduling algorithm SSPS is introduced in Section 7. The simulation experiment setup and results are presented in Section 8. Finally, in Section 9, we summarize the conclusion and future work.


## 1.1. Organization

The paper’s structure is listed as follows: the related work is described in Section2. Section 3 describes the paper’s overall framework. Section 4 defines the proposed MCS model and notation in detail. We analyze the schedulability of tasks in MCS in Section 5. Section 6 designs the task priority assignment. The detail of the proposed scheduling algorithm SSPS is introduced in Section 7. The simulation experiment setup and results are presented in Section 8. Finally, in Section 9, we summarize the conclusion and future work.


## 2. Related Work

In recent years, with the 6G network’s development, related IoT applications are widely applied and researched [1–3]. Especially, 6G-based edge computing is growing popular with 6G wireless communication developing rapidly [4, 5]. And the scheduling issue of these applications on multiprocessors, such as systems with multiple criticalities, has become prominent [6–12]. We review the related work as follows.The review of the literature [13–17] shows that the partitioned scheduling approach can achieve better schedulability than the global scheduling approach. By partitioned scheduling method, the task sets are firstly allocated to each processor, and then, they are executed according to the single-processor scheduling algorithm. The optimal partitioning of task sets on multiprocessors is a NP-hard problem, and the researchers mainly use heuristic partitioned algorithms to obtain suboptimal solutions. For the MCS on the identical multiprocessor platform, a fixed partitioned scheduling algorithm was firstly proposed in [14], and the impact of different task set sorting as well as a heuristic division on the system performance has been investigated. It showed that decreasing criticality (DC) can gain better schedulability than decreasing utilization (DU). In implicit-deadline sporadic MCS, a partitioned scheduling algorithm MC-PARTITION based on DC was proposed, which can get a better speedup bound. Since the task criticality level may change, the tasks are fixed via the Best-Fit Decreasing (BFD) of continuous criticality and utilization and improved resource utilization [15]. However, the pure partitioned scheduling algorithm may reduce the utilization of the entire system because of the migration forbidden between processors [16, 17].These above reasons lead to the emergence of a semipartitioned scheduling strategy. In this scheduling, most tasks are assigned to the fixed processor and some tasks can be scheduled to different processors globally [18–20]. And for the MCS, a series of semipartitioned scheduling algorithms have been proposed. Santy et al. designed a heuristic scheduling strategy, combining reserved, semipartitioned, and periodic conversion, which reduces the migration overhead and obtain better performance [21].In the original Vestal model,LO-criticality jobs sometimes are treated the same as noncritical jobs that will be not guaranteed in HI-criticality system mode, which ensures the completion requirements of HI-criticality tasks. Nevertheless, from the engineering perspective, LO-criticality task is not an NO-criticality task; it cannot be dropped easily [22–26]. Su and Zhu firstly focus on the LO-criticality tasks dropped in mixed critical scheduling and discuss the feasibility of restarting LO-criticality tasks from a multimodal perspective [22]. Burns and Baruah constructed an elastic mixed critical task model, which enables more frequent execution of LO-criticality tasks set through elastic processing [23]. And Baruah et al. [24] introduced an additional less pessimistic WCET for LO-criticality jobs to guarantee service regardless of the executions of HI-criticality jobs. The works in [25] follow the MC-Fluid framework to address the corresponding scheduler to handle LO-criticality service, having a good speedup factor.Some researchers agree that real-time task has importance or quality, which should be treated as a factor to improve the quality of service (QoS) of system or application [27, 28]. In these papers above, a notion, namely, value, is given to respect the quality of a task, as a basis of the scheduling algorithm. Moreover, the value density (value of a time unit) and urgency of a task are considered comprehensively into dynamic scheduling algorithm and improved the real-time application performance [29, 30].


## 3. Overall Framework

We consider the scheduling on mixed-criticality systems (MCS) under a multiprocessor platform, in 6G-based edge computing environment. Firstly, the schedulability analysis based on response time is used to obtain schedulable tasks. Then, these tasks are sorted by priority assigned by criticality, value, and deadline. The tasks are divided to processor by first fit (FF) in the priority of descending order. The smart semipartitioned scheduling strategy (SSPS) is proposed, in which some tasks can be migrated to other processors as needed. During the scheduling, the slack time collection is working to execute more task’s job. The overall framework of the SSPS is shown in Figure1.Figure 1
The overall framework of SSPS.


### 3.1. Our Contributions

For the mixed-criticality systems (MCS) in 6G-based edge computing of homogeneous multiprocessors, the timing and service quality of the system tasks are taken into consideration, and a smart semipartitioned scheduling strategy (SSPS) is proposed in the paper. Besides, when the system mode switches fromLO-criticality to HI-criticality, a mechanism that facilitates LO-criticality tasks (jobs) is designed in SSPS, to improve both the schedulability and the QoS.


## 3.1. Our Contributions

For the mixed-criticality systems (MCS) in 6G-based edge computing of homogeneous multiprocessors, the timing and service quality of the system tasks are taken into consideration, and a smart semipartitioned scheduling strategy (SSPS) is proposed in the paper. Besides, when the system mode switches fromLO-criticality to HI-criticality, a mechanism that facilitates LO-criticality tasks (jobs) is designed in SSPS, to improve both the schedulability and the QoS.


## 4. System Model and Notation

### 4.1. System Model and Notation

Here, a mixed-criticality system (MCS)S=T,P is defined as below, a task set T comprised of n independent and periodic tasks τ1,τ2,⋯,τn and n processor set P with m identical processors p1,p2,⋯,pm.Meanwhile, the dual MCS model is adopted in this paper, which runs in either aHI-criticality mode or a LO-criticality mode.Definition 1.
MCS tasks. The task of MC model can be characterized by a 5-tuple of parameters:τi=ζi,Ci,Di,Ti,Vi, where
(1)
ζi∈LO,HI denotes the criticality of task τi, where LO<HI. A task with HI-criticality is subject to be certified, whereas a LO-criticality task does not need to be certified(2)
Cil denotes the task τi’s worst-case execution time (WCET) in criticality mode l, where l∈LO,HI. CiHI and CiLO denote the WCET of task τi at HI-criticality mode and LO-criticality mode, respectively. It meets the constraint CiLO<CiHI(3)
Di∈R+ is the relative deadline of task τi(4)
Ti∈R+ is the period of task τi(5)
Vil specifies the value of task τi in criticality mode l, where l∈LO,HI. ViLO and ViHI respect the value of task τi at LO-criticality mode and HI-criticality mode, respectively, and it meets ViLO<ViHIEach taskτi in MCS can give rise to potentially infinite sequence of jobs.Definition 2.
MCS jobs. Each jobJij released by task τi can be described by a 4-tuple of parameters: Jij=aij,eij,dij,fij, where
(1)
aij∈R+ is the release time of job Jij(2)
eij∈R+ is the estimated execution time of Jij, with the constraint eij≤Ci(3)
dij∈R+ denotes the absolute deadline of Jij, satisfying dij=aij+Di(4)
fij∈R+ denotes the finish time of job Jij. If Jij succeed, it should be the constraint fij≤dijThe system starts in theLO-criticality mode and remains in this mode as long as all jobs finished their execution.If any job does not complete its execution within itsLO-criticality execution time CiLO, the system criticality mode will arise and HI-criticality tasks are executed with CiHI.


### 4.2. Assumptions of the Model

In the MCS model, theLO-criticality does not mean noncriticality, and these tasks should be executed to the extent possible.Assumption 3.
If MCS switches intoHI-criticality mode from LO-criticality mode, some of the LO-criticality tasks (and jobs) will be not dropped directly and allowed to be scheduled later.Assumption 4.
Tasks are independent of each other; they only share a processor, but not any other resource, such as bandwidth or memory.


## 4.1. System Model and Notation

Here, a mixed-criticality system (MCS)S=T,P is defined as below, a task set T comprised of n independent and periodic tasks τ1,τ2,⋯,τn and n processor set P with m identical processors p1,p2,⋯,pm.Meanwhile, the dual MCS model is adopted in this paper, which runs in either aHI-criticality mode or a LO-criticality mode.Definition 1.
MCS tasks. The task of MC model can be characterized by a 5-tuple of parameters:τi=ζi,Ci,Di,Ti,Vi, where
(1)
ζi∈LO,HI denotes the criticality of task τi, where LO<HI. A task with HI-criticality is subject to be certified, whereas a LO-criticality task does not need to be certified(2)
Cil denotes the task τi’s worst-case execution time (WCET) in criticality mode l, where l∈LO,HI. CiHI and CiLO denote the WCET of task τi at HI-criticality mode and LO-criticality mode, respectively. It meets the constraint CiLO<CiHI(3)
Di∈R+ is the relative deadline of task τi(4)
Ti∈R+ is the period of task τi(5)
Vil specifies the value of task τi in criticality mode l, where l∈LO,HI. ViLO and ViHI respect the value of task τi at LO-criticality mode and HI-criticality mode, respectively, and it meets ViLO<ViHIEach taskτi in MCS can give rise to potentially infinite sequence of jobs.Definition 2.
MCS jobs. Each jobJij released by task τi can be described by a 4-tuple of parameters: Jij=aij,eij,dij,fij, where
(1)
aij∈R+ is the release time of job Jij(2)
eij∈R+ is the estimated execution time of Jij, with the constraint eij≤Ci(3)
dij∈R+ denotes the absolute deadline of Jij, satisfying dij=aij+Di(4)
fij∈R+ denotes the finish time of job Jij. If Jij succeed, it should be the constraint fij≤dijThe system starts in theLO-criticality mode and remains in this mode as long as all jobs finished their execution.If any job does not complete its execution within itsLO-criticality execution time CiLO, the system criticality mode will arise and HI-criticality tasks are executed with CiHI.


## 4.2. Assumptions of the Model

In the MCS model, theLO-criticality does not mean noncriticality, and these tasks should be executed to the extent possible.Assumption 3.
If MCS switches intoHI-criticality mode from LO-criticality mode, some of the LO-criticality tasks (and jobs) will be not dropped directly and allowed to be scheduled later.Assumption 4.
Tasks are independent of each other; they only share a processor, but not any other resource, such as bandwidth or memory.


## 5. Schedulability Analysis

In this section, we will investigate the schedulability by analyzing the response time of the job.For jobJij, released by task τi, its response time Rij is denoted by Rij=fij−aij. Task τi’s response time is denoted as Ri, which equals to the value of the maximum response time of all jobs released by τi.We test the schedulability of the jobJij by comparing the response time Rij with the task τi’s deadline Di. If Rij≤Di, Jij can be scheduled; otherwise, it cannot be scheduled.The jobJij’s response time includes two parts: its estimated execution time eij and interference time Ii caused by higher priority tasks.When a taskτi is allocated to a processor, assuming a job Jij, released by τi at aij, Jij waits other higher priority jobs’ completion until bij, its finish time is fij, and its deadline is dij. The execution constraint is illustrated by Figure 2.Figure 2
Execution diagram ofJij.Supposetraise is the time when the system mode is raised from LO-criticality to HI-criticality. When traise∈aij,fij, discussion about Rij is as follows:
(1)
Iftraise∈aij,bij, it means that the system has been raised to HI-criticality mode before the job Jij starts
(a)
The system initials atLO-criticality mode during the interval aij,traise. And the job Jij executes in LO-criticality mode; the interference time can be calculated as
(1)Ii1=∑τi∈hpitraiseTj×CjLO,where hpi indicates the tasks with higher priority than task τi.(b)
In the intervaltraise,bij, the system is raised to HI-criticality mode. Then, the job Jij executes at HI-criticality mode; the interference time is defined as
(2)Ii2=∑τi∈hpi∪hcifij−traiseTj×CjHI,where hci indicates the tasks with higher criticality than task τi.(2)
Whentraise∈bij,fij, it means that the system critical mode is improved during the execution of the job Jij(a)
In the intervalbij,traise, the job Jij executes in LO-criticality mode; the interference time equals to Ii1 of Equation (1)(b)
In the intervaltraise,bij, the job Jij executes in HI-criticality mode; the interference time equals to Ii2 of Equation (2)In summary, the response time ofJij can be expressed as
(3)Rij=eij+Ii1+Ii2.Based on Equation (3), the task τi’s response time Ri, which can be determined by the jobs released by τi, selects the maximum response time of its job and satisfies Ri=maxJijRij.According to the discussion above, the pseudocode of the schedulability analysis algorithm can be described as Algorithm1. In this algorithm, the inputs include two pieces of information: the undivided task set T and unallocated processors P. The output is the partitioned task queue of the processors. At first, each processor is not allocated any task (lines 1–3). Then, sort the tasks T according to its priority in order (line 4). After this, the algorithm allocates the tasks to processors (lines 5-15). At last, return the partitioned result (line 16). For each task τi in the queue (line 5, the outer for), starting from the first, the algorithm tries to allocate τi to a processor pj to execute (line 6, the inner for). If τi can finish, insert it to the processor pj’s ready queue and allocate it to the next task (lines 7-10).In Algorithm1, it contains two-layer loops, where the outer-layer loop (lines 1, 5) can be evaluated in constant time On and the inner-layer loop (line 7)’s complexity is also constant level Om. The step of calculate Ri in line 6, between the outer-layer loop (line 5) and the inner-layer loop (line7), in which complexity is On. Consequently, Algorithm 1’s run time complexity is On∗m.


## 6. Priority Assignment of Task

In general, the priority of a task is the basis of schedule. This section mainly considers the criticality level and the value of task and proposes the priority assignment strategy.


### 6.1. Criticality and Value

According to Definition1, HI-criticality task τi’s value Vi is related to the criticality ζi, satisfying ViHI>ViLO.Algorithm 1: Schedulablity analysis.
Inputs:Task set to be partitionedT = τ1,...,τn;Processors set to be allocatedP=p1,⋯,pm.Outputs:PT =Que_Ready_p1,...,Que_Ready_pm./∗where Que_Ready_pi is the tasks ready queue on pi.∗/1:for each pj in Pdo2: SetQue_Ready_pj = {};3:end for4: SortedT according to priority in descending5:for each τi in Tdo6: CalculateRi by Eq. (3);7:for each pj in P by descending order do8:ifRi ≤ Dithen9:   Addτi into Que_Ready_pj;10:break;11:end if12:end for13:end for14:returnPT;In the existing strategies, theLO-criticality level tasks will be dropped out when the system criticality mode upgrades. Total value (TV) of the system can be expressed as TV=∑τi∈TViLO+∑τi∈THIViHI, where THI⊂T is the HI-criticality task set, ∑τi∈TViLO is the system total value in LO-criticality system mode, and ∑τi∈THIViHI is the system total value in HI-criticality mode.To compare the two values inHI-criticality mode and LO-criticality separately, ViHI and ViLO, let ViHI=CF×ViLO, where CF is criticality factor of task, which satisfies CF>1. ΔTV indicates the total value difference between in HI-criticality mode and in LO-criticality mode.
(4)ΔTV=∑τi∈THIViHI−∑τi∈TViLO=∑τi∈THICF×ViLO−∑τi∈TViLO=∑τi∈THICF−1×ViLO−∑τi∈TLOViLO.In Equation (4), ∑τi∈THICF−1×ViLO indicates the value difference of HI-criticality tasks in HI-criticality mode and in LO-criticality mode, and ∑τi∈TLOViLO represents the values obtained by the LO-criticality tasks.IfΔTV>0, it means that the TV increases as system criticality mode upgrades. In other words, the value difference of HI-criticality tasks in different criticality modes is larger than the LO-criticality tasks’ values at this time.IfΔTV≤0, it means the TV does not rise when the system criticality mode switches from LO-criticality to HI-criticality.


### 6.2. Assignment of Task’s Priority

In MCS, the task’s priority should reflect its attributes, including criticality level, value, and deadline. When constructing the priority assignment functionPri, we consider the importance of these factors.
(1)
AllHI-criticality tasks should be executed firstly(2)
Next, tasks with high value are prioritized in the same criticality levelIn different system criticality modes, for a taskτi, its priority is recorded as Pril:
(5)Pril=eCildi×lnVil,where Cil and Vil vary as the system critical mode l changes. And l satisfies l∈LO,HI.Theorem 5.
For the taskτi, it satisfies PriHI>PriLO.Proof.
In dual MCS withHI-criticality and LO-criticality, there are CiHI>CiLO and ViHI>ViLO. Therefore, PriHI>PriLO.Lemma 6.
When the system is inHI-criticality mode, for each HI-criticality taskτi and LO-criticality taskτj, it satisfies PriHI>PriLO.


## 6.1. Criticality and Value

According to Definition1, HI-criticality task τi’s value Vi is related to the criticality ζi, satisfying ViHI>ViLO.Algorithm 1: Schedulablity analysis.
Inputs:Task set to be partitionedT = τ1,...,τn;Processors set to be allocatedP=p1,⋯,pm.Outputs:PT =Que_Ready_p1,...,Que_Ready_pm./∗where Que_Ready_pi is the tasks ready queue on pi.∗/1:for each pj in Pdo2: SetQue_Ready_pj = {};3:end for4: SortedT according to priority in descending5:for each τi in Tdo6: CalculateRi by Eq. (3);7:for each pj in P by descending order do8:ifRi ≤ Dithen9:   Addτi into Que_Ready_pj;10:break;11:end if12:end for13:end for14:returnPT;In the existing strategies, theLO-criticality level tasks will be dropped out when the system criticality mode upgrades. Total value (TV) of the system can be expressed as TV=∑τi∈TViLO+∑τi∈THIViHI, where THI⊂T is the HI-criticality task set, ∑τi∈TViLO is the system total value in LO-criticality system mode, and ∑τi∈THIViHI is the system total value in HI-criticality mode.To compare the two values inHI-criticality mode and LO-criticality separately, ViHI and ViLO, let ViHI=CF×ViLO, where CF is criticality factor of task, which satisfies CF>1. ΔTV indicates the total value difference between in HI-criticality mode and in LO-criticality mode.
(4)ΔTV=∑τi∈THIViHI−∑τi∈TViLO=∑τi∈THICF×ViLO−∑τi∈TViLO=∑τi∈THICF−1×ViLO−∑τi∈TLOViLO.In Equation (4), ∑τi∈THICF−1×ViLO indicates the value difference of HI-criticality tasks in HI-criticality mode and in LO-criticality mode, and ∑τi∈TLOViLO represents the values obtained by the LO-criticality tasks.IfΔTV>0, it means that the TV increases as system criticality mode upgrades. In other words, the value difference of HI-criticality tasks in different criticality modes is larger than the LO-criticality tasks’ values at this time.IfΔTV≤0, it means the TV does not rise when the system criticality mode switches from LO-criticality to HI-criticality.


## 6.2. Assignment of Task’s Priority

In MCS, the task’s priority should reflect its attributes, including criticality level, value, and deadline. When constructing the priority assignment functionPri, we consider the importance of these factors.
(1)
AllHI-criticality tasks should be executed firstly(2)
Next, tasks with high value are prioritized in the same criticality levelIn different system criticality modes, for a taskτi, its priority is recorded as Pril:
(5)Pril=eCildi×lnVil,where Cil and Vil vary as the system critical mode l changes. And l satisfies l∈LO,HI.Theorem 5.
For the taskτi, it satisfies PriHI>PriLO.Proof.
In dual MCS withHI-criticality and LO-criticality, there are CiHI>CiLO and ViHI>ViLO. Therefore, PriHI>PriLO.Lemma 6.
When the system is inHI-criticality mode, for each HI-criticality taskτi and LO-criticality taskτj, it satisfies PriHI>PriLO.


## 7. Scheduling Algorithm

For the MCS under a homogeneous multiprocessor platform, we propose a smart semipartitioned scheduling strategy (SSPS).


### 7.1. Smart Semipartitioned Scheduling Strategy (SSPS)

SSPS includes both the processes of partitioned scheduling and global scheduling; the details are as follows:(1)
Task order. All the tasks ofT are sorted in a descending order according to their priorities calculated by Equation (5)(2)
Processors allocation. Each sorted task is allocated to processors by First-Fit Decreasing (FFD) method(3)
Schedulability test. The task subset’s schedulability is tested by Algorithm1(4)
Task execution. This process includes executing jobs released by the task and collecting the processors’ idle time forLO-criticality tasks’ execution
(a)
Tasks allocated in each processor execute by priority, and these tasks do not migrate. During this process, the slack times of each processor are collected and stored in the queueQue¯Slack(b)
When the system criticality mode upgrades, all unfinishedLO-criticality jobs are sorted and managed globally and then assign their execution times in Que¯Slack. At the high mode, we allow the execution of LO-criticality tasks but do not allow them to preempt HI-criticality tasks; i.e., the HI-criticality tasks will not incur any interference from the ones with a LO-criticality levelHere, the queueQue¯Slack is used to store feasible slack fragment sf. Each sf is represented in the form of q,d, where q is the length of time and d is the end time of sf. The algorithm of slack time collection is shown as Algorithm 2.In Algorithm2, the inputs include two pieces of information, including the given executing job Jexej and slack fragment sfi of processor pi. The output of the algorithm is the idle time queue Que¯Slack. At first, the condition of collect processor slack time is that the job Jexej can finish until its deadline dexej (line 1). And if the input sfi is null, insert into queue Que¯Slack (lines 2-6). Otherwise, discuss the values of Jexej executing time eexej=q and the sfi’s length q, the former should be not larger than the latter to ensure Jexej’s execution. If the two are equal, then remove the sfi from Que¯Slack (lines 9-10), and if eexej is less than q, q’s remaining time after completing Jexej is update to Que¯Slack (lines 11-14). At last, return Que¯Slack (line 17).Algorithm 2: Slack time collection.
Inputs:Executing jobJexej;Slack fragmentsfi.Output:The queue for collect idle timeQue_Slack.1:ifJexej finish at t0(t0<dexej) then2:ifsfi = null then3:q = (Cexe-eexej);4:d=dexej;5:sfi⇐q,d;6:  Insertsfi into Que_Slack;7:else8:  Getq,d from sfi;9:ifeexej=qthen10:   Removesfi from Que_Slack;11:else ifeexej<qthen12:    Setq=q−eexej;13:    Updatesfi to Que_Slack;14:end if15:end if16:end if17:returnQue_Slack;Example 1.
A task set including 5 tasks is shown in Table1 and is divided into two homogeneous processors.Table 1
A task set of 5 tasks.
CiLOCiHIζiDiViLOViHIτ145HI82050τ224HI82040τ322LO63535τ445LO32020τ545LO51010The system is inLO-criticality mode at the initial time, and if the task set is presorted using the DU method, the sequence of system tasks is τ1, τ3, τ4, τ2, and τ5. In accordance with the FFD strategy, tasks τ1 and τ3 are divided into processor p1, while tasks τ2, τ4, and τ5 are divided into processor p2. In this case, two processors meet the conditions. In LO-criticality system mode, the resource utilization of p1 is 83.3%, and the corresponding resource utilization of p2 is 78.3%. When the system mode upgrades to a HI-criticality mode, all LO-criticality tasks τ3, τ4, and τ5 are discarded. In this case, processor p1 obtains a resource utilization of 62.5% and the resource utilization of processor p2 is 50%.The existing scheduling algorithms, such as MC-PARTITION, drop out allLO-criticality tasks directly in HI-criticality system mode, even if there is some idle time on the processor at some moment. In order to improve the acceptance rate of the task and the utilization of the processor, the cutoff period and value attribute of the task can be considered comprehensively, and the LO-criticality task is dispatched globally by using the idle time of the processor when the system mode switches from LO-criticality into HI-criticality. A hyperperiod execution (here, 24 time units) for the task set of Example 1 is shown in Figure 3, in which the task set is presorted according to the priority function of Equation (5), with the same result as the DU method.Figure 3
Execution of the task set in Example1.After the system critical mode upgrades, we perform global scheduling forLO-criticality tasks τ3, τ4, and τ5 on the premise of ensuring HI-criticality tasks τ1 and τ2 and allocate idle time on processors p1 and p2 dynamically. This method can achieve high acceptance ratio and improve the utilizations of both processors to 91.7% (11/12).


### 7.2. Analysis of SSPS

In the smart semipartitioned scheduling strategy (SSPS), the task’s schedulability is analyzed by Algorithm1; tasks allocated by first fit (FF) are assigned priority by Equation (4). The queue Que¯Slack is used to collect slack time by Algorithm 2, and the LO-criticality jobs are collected to the queue Que¯Low. The system selects the segment in Que¯Slack to execute the job in Que¯Low. Meanwhile, the queue Que¯Ready is used to store prepared tasks. And the pseudocode of SSPS is shown in Algorithm 3 as follows.Algorithm 3: SSPS.
Inputs:T=τ1,τ2,⋯,τn;P=p1,p2,⋯,pm;Que¯Low,Que¯Slack=null;Que¯Ready=T;Sys¯Mode=LO;NST,NT=0.Output:Acceptance Ratio.1:PT= schedulability analysis(Que¯Ready,P)/∗PT=Que_Ready_p1,⋯,Que_Ready_pm, whereQue¯Ready¯p1 is the tasks allocated to p1∗/2:ifPT≠nullthen3:for each Que¯Ready¯pm in PTdo4:  Get the top elementJexem out of Que¯Ready¯pm;5:NT++;6:Rexem>CexeLOthen7:ifJexem is HI-criticality and Sys¯Mode=LOthen8:   Abort all Jobs ofLO-criticality in PT;9:   InsertLO-criticality jobs into Que¯Low asPrp¯LO in descending order;10:Sys¯Mode=HI;11:  ExecuteJexem in HI-criticality;12:NST++;13:else14:   AbortJexem;15:continue;16end if17:else18:  ExecuteJexem;19:NST++;20:  Que_Slack= slack time collection(Jexem, null);21:continue;22:end if23:ifSys¯Mode=HIthen24:for each sfs from Que¯Slackdo25:   Get the top elementJexej out of Que¯Low;26:ifeexej≤qsthen27:   ExecuteJexej;28:NST++,NT++;29:   Que_Slack= slack time collection(Jexej, sfs);30:else31:continue;32:end if33:end for34:end if35:end for36: returnNST/NT;37:end ifIn Algorithm3 mentioned above, the inputs include seven parameters: the task set T, the processor set P, the queue for LO-criticality jobs, the queue storing processor’s idle time, the queue for ready tasks, the initial system mode (Sys¯Mode=LO), the total successful jobs’ number NST and the total job number NT. The output of Algorithm 3 is the acceptance ratio which equals NST/NT. At first, analyze all tasks of T and allocate to a ready queue Que¯Ready¯pm of each processor pm (line 1). Then, for the queue Que¯Ready¯pm, get the task Jexem and compare its response time Rexem to CexeLO (lines 2-4). If Jexem cannot finish its completion (Rexem>CexeLO), then discuss if Jexem is a HI-criticality job and Sys¯Mode=LO; the system mode switches to HO-criticality from LO-criticality according the MCS definition; abort LO-criticality tasks in ready queue of each process, insert LO-criticality jobs into the queue Que¯Low, and execute the Jexem (lines 5–10); if Jexem is a LO-criticality job, then abort it and continue (lines 11-14). Otherwise, Jexem can finish, execute it, and collect the slack time of its completion (lines 15-19).During the scheduling inHO-criticality system mode, the processor of executing LO-criticality uses idle time of each processor (lines 20-30). For each slack fragment sfs in queue Que¯Slack, the top job Jexem of Que¯Low is chosen to execute. It is necessary to compare eexem to qs, the length of sfs. If the former is not less than the letter, then complete Jexem and collect the slack time of its completion (lines 22-25).Algorithm3 calls Algorithm 1 (line 1) that contains a two-layer loop. And its another two-layer loop in algorithm, where the outer-layer loop is in lines 3-31 of Om, and the inner-layer loop (lines 21-29) can be evaluated in constant time of On. Therefore, the time complexity of the Algorithm 3 is in the pseudopolynomial order.For the SSPS algorithm, it is necessary to discuss the system valueVi.
(1)
InLO-criticality system mode, the system total value of the T is ∑τi∈TViLO.(2)
InHI-criticality system mode, the total value contains two parts: the value obtained by the HI-criticality task ∑τi∈THIViHI, where THI⊂T, and the value obtained by the finished LO-criticality task set, named as TLO′, ∑τi∈TLO′ViLO.The total valueTVSSPS can be described as
(6)TVSSPS=∑τi∈TViLO+∑τi∈THIViHI+∑τi∈TLO′ViLO.According to Equation (6) about the TV of the classic strategies, TVSSPS≥TV obviously.To discuss theTVSSPS changed with system criticality mode, let ΔTVVSSPS indicate the total value difference between in HI-criticality mode and in LO-criticality mode. If ΔTVSSPS>0, it indicates that the TVSSPS in HI-criticality mode is bigger; conversely, it means that the TVSSPS in HI-criticality mode is smaller.
(7)ΔTVSSPS=∑τi∈THIViHI+∑τi∈TLO′ViLO−∑τi∈TViLO=∑τi∈THICF×ViLO+∑τi∈TLO′ViLO−∑τi∈TViLO=∑τi∈THICF−1×ViLO−∑τi∈T−THI−TLO′ViLO,where CF=ViHI/ViLO is the criticality factor of task, and CF>1.In Equation (7), ∑τi∈THICF−1×ViLO is the obtained value of HI-criticality task difference in HI-criticality mode and in LO-criticality mode. ∑τi∈T−THI−TLO′ViLO is the value obtained by the dropped LO-criticality tasks.


## 7.1. Smart Semipartitioned Scheduling Strategy (SSPS)

SSPS includes both the processes of partitioned scheduling and global scheduling; the details are as follows:(1)
Task order. All the tasks ofT are sorted in a descending order according to their priorities calculated by Equation (5)(2)
Processors allocation. Each sorted task is allocated to processors by First-Fit Decreasing (FFD) method(3)
Schedulability test. The task subset’s schedulability is tested by Algorithm1(4)
Task execution. This process includes executing jobs released by the task and collecting the processors’ idle time forLO-criticality tasks’ execution
(a)
Tasks allocated in each processor execute by priority, and these tasks do not migrate. During this process, the slack times of each processor are collected and stored in the queueQue¯Slack(b)
When the system criticality mode upgrades, all unfinishedLO-criticality jobs are sorted and managed globally and then assign their execution times in Que¯Slack. At the high mode, we allow the execution of LO-criticality tasks but do not allow them to preempt HI-criticality tasks; i.e., the HI-criticality tasks will not incur any interference from the ones with a LO-criticality levelHere, the queueQue¯Slack is used to store feasible slack fragment sf. Each sf is represented in the form of q,d, where q is the length of time and d is the end time of sf. The algorithm of slack time collection is shown as Algorithm 2.In Algorithm2, the inputs include two pieces of information, including the given executing job Jexej and slack fragment sfi of processor pi. The output of the algorithm is the idle time queue Que¯Slack. At first, the condition of collect processor slack time is that the job Jexej can finish until its deadline dexej (line 1). And if the input sfi is null, insert into queue Que¯Slack (lines 2-6). Otherwise, discuss the values of Jexej executing time eexej=q and the sfi’s length q, the former should be not larger than the latter to ensure Jexej’s execution. If the two are equal, then remove the sfi from Que¯Slack (lines 9-10), and if eexej is less than q, q’s remaining time after completing Jexej is update to Que¯Slack (lines 11-14). At last, return Que¯Slack (line 17).Algorithm 2: Slack time collection.
Inputs:Executing jobJexej;Slack fragmentsfi.Output:The queue for collect idle timeQue_Slack.1:ifJexej finish at t0(t0<dexej) then2:ifsfi = null then3:q = (Cexe-eexej);4:d=dexej;5:sfi⇐q,d;6:  Insertsfi into Que_Slack;7:else8:  Getq,d from sfi;9:ifeexej=qthen10:   Removesfi from Que_Slack;11:else ifeexej<qthen12:    Setq=q−eexej;13:    Updatesfi to Que_Slack;14:end if15:end if16:end if17:returnQue_Slack;Example 1.
A task set including 5 tasks is shown in Table1 and is divided into two homogeneous processors.Table 1
A task set of 5 tasks.
CiLOCiHIζiDiViLOViHIτ145HI82050τ224HI82040τ322LO63535τ445LO32020τ545LO51010The system is inLO-criticality mode at the initial time, and if the task set is presorted using the DU method, the sequence of system tasks is τ1, τ3, τ4, τ2, and τ5. In accordance with the FFD strategy, tasks τ1 and τ3 are divided into processor p1, while tasks τ2, τ4, and τ5 are divided into processor p2. In this case, two processors meet the conditions. In LO-criticality system mode, the resource utilization of p1 is 83.3%, and the corresponding resource utilization of p2 is 78.3%. When the system mode upgrades to a HI-criticality mode, all LO-criticality tasks τ3, τ4, and τ5 are discarded. In this case, processor p1 obtains a resource utilization of 62.5% and the resource utilization of processor p2 is 50%.The existing scheduling algorithms, such as MC-PARTITION, drop out allLO-criticality tasks directly in HI-criticality system mode, even if there is some idle time on the processor at some moment. In order to improve the acceptance rate of the task and the utilization of the processor, the cutoff period and value attribute of the task can be considered comprehensively, and the LO-criticality task is dispatched globally by using the idle time of the processor when the system mode switches from LO-criticality into HI-criticality. A hyperperiod execution (here, 24 time units) for the task set of Example 1 is shown in Figure 3, in which the task set is presorted according to the priority function of Equation (5), with the same result as the DU method.Figure 3
Execution of the task set in Example1.After the system critical mode upgrades, we perform global scheduling forLO-criticality tasks τ3, τ4, and τ5 on the premise of ensuring HI-criticality tasks τ1 and τ2 and allocate idle time on processors p1 and p2 dynamically. This method can achieve high acceptance ratio and improve the utilizations of both processors to 91.7% (11/12).


## 7.2. Analysis of SSPS

In the smart semipartitioned scheduling strategy (SSPS), the task’s schedulability is analyzed by Algorithm1; tasks allocated by first fit (FF) are assigned priority by Equation (4). The queue Que¯Slack is used to collect slack time by Algorithm 2, and the LO-criticality jobs are collected to the queue Que¯Low. The system selects the segment in Que¯Slack to execute the job in Que¯Low. Meanwhile, the queue Que¯Ready is used to store prepared tasks. And the pseudocode of SSPS is shown in Algorithm 3 as follows.Algorithm 3: SSPS.
Inputs:T=τ1,τ2,⋯,τn;P=p1,p2,⋯,pm;Que¯Low,Que¯Slack=null;Que¯Ready=T;Sys¯Mode=LO;NST,NT=0.Output:Acceptance Ratio.1:PT= schedulability analysis(Que¯Ready,P)/∗PT=Que_Ready_p1,⋯,Que_Ready_pm, whereQue¯Ready¯p1 is the tasks allocated to p1∗/2:ifPT≠nullthen3:for each Que¯Ready¯pm in PTdo4:  Get the top elementJexem out of Que¯Ready¯pm;5:NT++;6:Rexem>CexeLOthen7:ifJexem is HI-criticality and Sys¯Mode=LOthen8:   Abort all Jobs ofLO-criticality in PT;9:   InsertLO-criticality jobs into Que¯Low asPrp¯LO in descending order;10:Sys¯Mode=HI;11:  ExecuteJexem in HI-criticality;12:NST++;13:else14:   AbortJexem;15:continue;16end if17:else18:  ExecuteJexem;19:NST++;20:  Que_Slack= slack time collection(Jexem, null);21:continue;22:end if23:ifSys¯Mode=HIthen24:for each sfs from Que¯Slackdo25:   Get the top elementJexej out of Que¯Low;26:ifeexej≤qsthen27:   ExecuteJexej;28:NST++,NT++;29:   Que_Slack= slack time collection(Jexej, sfs);30:else31:continue;32:end if33:end for34:end if35:end for36: returnNST/NT;37:end ifIn Algorithm3 mentioned above, the inputs include seven parameters: the task set T, the processor set P, the queue for LO-criticality jobs, the queue storing processor’s idle time, the queue for ready tasks, the initial system mode (Sys¯Mode=LO), the total successful jobs’ number NST and the total job number NT. The output of Algorithm 3 is the acceptance ratio which equals NST/NT. At first, analyze all tasks of T and allocate to a ready queue Que¯Ready¯pm of each processor pm (line 1). Then, for the queue Que¯Ready¯pm, get the task Jexem and compare its response time Rexem to CexeLO (lines 2-4). If Jexem cannot finish its completion (Rexem>CexeLO), then discuss if Jexem is a HI-criticality job and Sys¯Mode=LO; the system mode switches to HO-criticality from LO-criticality according the MCS definition; abort LO-criticality tasks in ready queue of each process, insert LO-criticality jobs into the queue Que¯Low, and execute the Jexem (lines 5–10); if Jexem is a LO-criticality job, then abort it and continue (lines 11-14). Otherwise, Jexem can finish, execute it, and collect the slack time of its completion (lines 15-19).During the scheduling inHO-criticality system mode, the processor of executing LO-criticality uses idle time of each processor (lines 20-30). For each slack fragment sfs in queue Que¯Slack, the top job Jexem of Que¯Low is chosen to execute. It is necessary to compare eexem to qs, the length of sfs. If the former is not less than the letter, then complete Jexem and collect the slack time of its completion (lines 22-25).Algorithm3 calls Algorithm 1 (line 1) that contains a two-layer loop. And its another two-layer loop in algorithm, where the outer-layer loop is in lines 3-31 of Om, and the inner-layer loop (lines 21-29) can be evaluated in constant time of On. Therefore, the time complexity of the Algorithm 3 is in the pseudopolynomial order.For the SSPS algorithm, it is necessary to discuss the system valueVi.
(1)
InLO-criticality system mode, the system total value of the T is ∑τi∈TViLO.(2)
InHI-criticality system mode, the total value contains two parts: the value obtained by the HI-criticality task ∑τi∈THIViHI, where THI⊂T, and the value obtained by the finished LO-criticality task set, named as TLO′, ∑τi∈TLO′ViLO.The total valueTVSSPS can be described as
(6)TVSSPS=∑τi∈TViLO+∑τi∈THIViHI+∑τi∈TLO′ViLO.According to Equation (6) about the TV of the classic strategies, TVSSPS≥TV obviously.To discuss theTVSSPS changed with system criticality mode, let ΔTVVSSPS indicate the total value difference between in HI-criticality mode and in LO-criticality mode. If ΔTVSSPS>0, it indicates that the TVSSPS in HI-criticality mode is bigger; conversely, it means that the TVSSPS in HI-criticality mode is smaller.
(7)ΔTVSSPS=∑τi∈THIViHI+∑τi∈TLO′ViLO−∑τi∈TViLO=∑τi∈THICF×ViLO+∑τi∈TLO′ViLO−∑τi∈TViLO=∑τi∈THICF−1×ViLO−∑τi∈T−THI−TLO′ViLO,where CF=ViHI/ViLO is the criticality factor of task, and CF>1.In Equation (7), ∑τi∈THICF−1×ViLO is the obtained value of HI-criticality task difference in HI-criticality mode and in LO-criticality mode. ∑τi∈T−THI−TLO′ViLO is the value obtained by the dropped LO-criticality tasks.


## 8. Simulations and Analysis

### 8.1. Simulation Experiments

The simulation experiments are performed to test the scheduling algorithm SSPS. All experiments were run on a PC with a 3.40 GHz 4 identical processor and 8 GB memory. In the simulation, we compared SSPS to the existing partition scheduling algorithms, DC-RM [13] and MC-PARTITION [14], which are the classic and representative algorithms in the research community of MCS partition scheduling. Based on these two algorithms, there are lots of derived algorithms for other real-time application scenarios [16–19]. The task set parameters of the experiments were randomly generated as follows:
(1)
The utilization of each taskUiLO was in the range [0.025, 0.975] and was generated by the Uunifast-Discard algorithm(2)
The proportion of high-critical tasks to task setT HTP, which directly affects the execution of LO-criticality tasks and then affects the performance of our SSPS strategy, was 0.5 by default. And the criticality factor CF=CiHI/CiLO was set to 1.5, according to Definition 1 where CF>1(3)
Each taskτi’s LO-criticality execution time CiLO is randomly generated in the range from 1 to 10 in accordance with uniform distribution. And, τi’s execution time of HI-criticalityCiHI satisfies CiHI=CF×CiLO(4)
The taskτi’s relative deadline Di satisfies: Di=CiLO/UiLO, and τi’s period Ti is Ti=Di(5)
The taskτi’s value of LO-criticalityViLO was generated randomly between 10 and 50, and its HI-criticalityViHI was set to ViHI=5×CF×ViLOThe performance indicators include acceptance ratio (AR), weighted schedulability (WS), and total values (TV).(1)
AR=NST/NT, where NST is the number of successful tasks and NT is the number of system taskset. The AR shows the proportion of successful tasks to total task set(2)
WS=∑ibi×UiLO/∑iUiLO, where bi∈0,1. The WS indicates the total utilization of each task(3)
TV=∑τi∈STVi, where ST is the successful tasks. The TV represents the QoS of whole successful tasksIn order to measure the average number of job migrations, 100 trials of simulations with different tasks are conducted in the experiment.


### 8.2. Acceptance Ratio Analysis

The AR changes as tasks’ different LO-critical utilizationUiLO scheduled by MC-PARTITION, DC-RM, and SSPS are demonstrated in Figure 4. It can be seen that all algorithms’ AR decrease significantly as the UiLO grows from 0.3 to 1.0. And the DC-RM algorithm has the least AR and the SSPS algorithm obtains the best AR. When the UiLO is below 0.5, SSPS is close to MC-PARTITION and DC-RM in AR. But as UiLO becomes larger than 0.6, the SSPS begins to outperform the other two algorithms, because in HI-criticality mode, SSPS executes the LO-criticality tasks selectively, improving the AR of the whole system, while the other two algorithms discard LO-criticality tasks directly, which leads to a sharp descending in AR.Figure 4
Results of AR with the change ofUiLO.It is illustrated that the AR varies in different high-critical task proportionHTP in Figure 5, when UiLO is set to 0.6 and the HTP grows from 0.3 to 1.0. As shown by the result, with the HTP increases, the additional HI-criticality tasks require more executing time; thus, all algorithms’s AR continues to decline. When the HTP is less than 0.5, all algorithms’ AR is close because the competition of tasks’ execution is not intense in LO-criticality system mode. As the HTP grows larger than 0.6, the intense competition among tasks reduces the AR, in which some task cannot finish its execution and the system mode arises to HI-criticality.Figure 5
Results of AR as HTP changes.Once the system mode upgrades toHI-criticality, the task’s Ci becomes large. Compared to the MC-PARTITION and DC-RM, the SSPS algorithm achieves a more stable and higher AR, because the former two algorithms drop the LO-criticality tasks directly. When the system mode switches from LO-criticality to HI-criticality, the SSPS algorithm executes some LO-criticality jobs in an idle time of the processor and gradually decreases as HTP increases.


### 8.3. Schedulability Analysis

It is shown that the weighted schedulability WS is declining withUiLO arguments, where HTP is set to 0.5 (see Figure 6). Compared to MC-PARTITION and DC-RM algorithms, the SSPS gets higher and more stable in WS through schedule the LO-criticality task in HI-criticality system mode. In the beginning, the WS obtained by all algorithms is falling steadily. When HTP becomes larger than 0.6, MC-PARTITION and DC-RM accelerate degradation in WS due to the more execution time required by increased HI-criticality tasks and the discarded of LO-criticality tasks directly in HI-criticality system mode.Figure 6
Results of WS with the change ofUiLO.That weighted schedulability WS results change as HTP grows is plotted in Figure7, where UiLO=0.5. The HTP is represented on the horizontal axis, and the vertical axis is WS. We can see that WS is gradually declining as HTP arguments. Because with the number of HI-criticality tasks increasing, the system resources they need are increased. When the HTP is below 0.3, SSPS is almost identical to MC-PARTITION and DC-RM algorithms that get a steady decline in WS. With the HTP becoming larger and the system criticality level arising, the execution time of the HI-criticality task becomes longer, which can intensify competition among tasks and reduces the system schedulability. The SSPS can obtain better WS than the other two methods, because SSPS in HI-criticality mode can take advantage of slack time produced by HI-criticality task, to execute the selected LO-criticality task globally.Figure 7
Results of WS with the change of HTP.


### 8.4. Total Value Analysis

The simulation results for total value TV changed with LO-critical system utilizationUiLO’s growth are shown in Figure 8, where the horizontal axis is UiLO and the vertical axis is TV. As shown in Figure 8, all algorithms’ TV decrease as the UiLO increases from 0.3 to 0.9. Compared to the other two algorithms, the MAPPS has a significant advantage over the other two in TV, which gradually decreases as the UiLO grows. Because only the SSPS chooses the task with high urgency and high value, thereby obtaining better TV and improving the performance of the system.Figure 8
Results of TV with the change of HTP.Figure9 plots the TV with the change of HTP. It shows that the total value TV presents the fluctuation of first up then down as HTP grows from 0.1 to 0.9. In the beginning, the growing number of HI-criticality tasks can take a larger value. But with HTP increasing, the HI-criticality task’s longer executing time reduces the WS of the system, as shown in Figure 9, which brings the TV decreasing. And SSPS can obtain the best TV due to its choice of high urgency and high-value tasks.Figure 9
Results of TV with the change of HTP.


## 8.1. Simulation Experiments

The simulation experiments are performed to test the scheduling algorithm SSPS. All experiments were run on a PC with a 3.40 GHz 4 identical processor and 8 GB memory. In the simulation, we compared SSPS to the existing partition scheduling algorithms, DC-RM [13] and MC-PARTITION [14], which are the classic and representative algorithms in the research community of MCS partition scheduling. Based on these two algorithms, there are lots of derived algorithms for other real-time application scenarios [16–19]. The task set parameters of the experiments were randomly generated as follows:
(1)
The utilization of each taskUiLO was in the range [0.025, 0.975] and was generated by the Uunifast-Discard algorithm(2)
The proportion of high-critical tasks to task setT HTP, which directly affects the execution of LO-criticality tasks and then affects the performance of our SSPS strategy, was 0.5 by default. And the criticality factor CF=CiHI/CiLO was set to 1.5, according to Definition 1 where CF>1(3)
Each taskτi’s LO-criticality execution time CiLO is randomly generated in the range from 1 to 10 in accordance with uniform distribution. And, τi’s execution time of HI-criticalityCiHI satisfies CiHI=CF×CiLO(4)
The taskτi’s relative deadline Di satisfies: Di=CiLO/UiLO, and τi’s period Ti is Ti=Di(5)
The taskτi’s value of LO-criticalityViLO was generated randomly between 10 and 50, and its HI-criticalityViHI was set to ViHI=5×CF×ViLOThe performance indicators include acceptance ratio (AR), weighted schedulability (WS), and total values (TV).(1)
AR=NST/NT, where NST is the number of successful tasks and NT is the number of system taskset. The AR shows the proportion of successful tasks to total task set(2)
WS=∑ibi×UiLO/∑iUiLO, where bi∈0,1. The WS indicates the total utilization of each task(3)
TV=∑τi∈STVi, where ST is the successful tasks. The TV represents the QoS of whole successful tasksIn order to measure the average number of job migrations, 100 trials of simulations with different tasks are conducted in the experiment.


## 8.2. Acceptance Ratio Analysis

The AR changes as tasks’ different LO-critical utilizationUiLO scheduled by MC-PARTITION, DC-RM, and SSPS are demonstrated in Figure 4. It can be seen that all algorithms’ AR decrease significantly as the UiLO grows from 0.3 to 1.0. And the DC-RM algorithm has the least AR and the SSPS algorithm obtains the best AR. When the UiLO is below 0.5, SSPS is close to MC-PARTITION and DC-RM in AR. But as UiLO becomes larger than 0.6, the SSPS begins to outperform the other two algorithms, because in HI-criticality mode, SSPS executes the LO-criticality tasks selectively, improving the AR of the whole system, while the other two algorithms discard LO-criticality tasks directly, which leads to a sharp descending in AR.Figure 4
Results of AR with the change ofUiLO.It is illustrated that the AR varies in different high-critical task proportionHTP in Figure 5, when UiLO is set to 0.6 and the HTP grows from 0.3 to 1.0. As shown by the result, with the HTP increases, the additional HI-criticality tasks require more executing time; thus, all algorithms’s AR continues to decline. When the HTP is less than 0.5, all algorithms’ AR is close because the competition of tasks’ execution is not intense in LO-criticality system mode. As the HTP grows larger than 0.6, the intense competition among tasks reduces the AR, in which some task cannot finish its execution and the system mode arises to HI-criticality.Figure 5
Results of AR as HTP changes.Once the system mode upgrades toHI-criticality, the task’s Ci becomes large. Compared to the MC-PARTITION and DC-RM, the SSPS algorithm achieves a more stable and higher AR, because the former two algorithms drop the LO-criticality tasks directly. When the system mode switches from LO-criticality to HI-criticality, the SSPS algorithm executes some LO-criticality jobs in an idle time of the processor and gradually decreases as HTP increases.


## 8.3. Schedulability Analysis

It is shown that the weighted schedulability WS is declining withUiLO arguments, where HTP is set to 0.5 (see Figure 6). Compared to MC-PARTITION and DC-RM algorithms, the SSPS gets higher and more stable in WS through schedule the LO-criticality task in HI-criticality system mode. In the beginning, the WS obtained by all algorithms is falling steadily. When HTP becomes larger than 0.6, MC-PARTITION and DC-RM accelerate degradation in WS due to the more execution time required by increased HI-criticality tasks and the discarded of LO-criticality tasks directly in HI-criticality system mode.Figure 6
Results of WS with the change ofUiLO.That weighted schedulability WS results change as HTP grows is plotted in Figure7, where UiLO=0.5. The HTP is represented on the horizontal axis, and the vertical axis is WS. We can see that WS is gradually declining as HTP arguments. Because with the number of HI-criticality tasks increasing, the system resources they need are increased. When the HTP is below 0.3, SSPS is almost identical to MC-PARTITION and DC-RM algorithms that get a steady decline in WS. With the HTP becoming larger and the system criticality level arising, the execution time of the HI-criticality task becomes longer, which can intensify competition among tasks and reduces the system schedulability. The SSPS can obtain better WS than the other two methods, because SSPS in HI-criticality mode can take advantage of slack time produced by HI-criticality task, to execute the selected LO-criticality task globally.Figure 7
Results of WS with the change of HTP.


## 8.4. Total Value Analysis

The simulation results for total value TV changed with LO-critical system utilizationUiLO’s growth are shown in Figure 8, where the horizontal axis is UiLO and the vertical axis is TV. As shown in Figure 8, all algorithms’ TV decrease as the UiLO increases from 0.3 to 0.9. Compared to the other two algorithms, the MAPPS has a significant advantage over the other two in TV, which gradually decreases as the UiLO grows. Because only the SSPS chooses the task with high urgency and high value, thereby obtaining better TV and improving the performance of the system.Figure 8
Results of TV with the change of HTP.Figure9 plots the TV with the change of HTP. It shows that the total value TV presents the fluctuation of first up then down as HTP grows from 0.1 to 0.9. In the beginning, the growing number of HI-criticality tasks can take a larger value. But with HTP increasing, the HI-criticality task’s longer executing time reduces the WS of the system, as shown in Figure 9, which brings the TV decreasing. And SSPS can obtain the best TV due to its choice of high urgency and high-value tasks.Figure 9
Results of TV with the change of HTP.


## 9. Conclusions and Future Works

In recent years, with the increasing popularity of 6G wireless communication technology, mixed-criticality systems (MCS) in 6G-based edge computing have been grown quickly in application scenarios. Meanwhile, with the multiprocessors’ development widely applied, including homogeneous, the relative MCS scheduling technique is necessary to research. In this paper, a smart semipartitioned scheduling algorithm (SSPS) was designed on MCS in the homogeneous multiprocessors. Firstly, we analyze the task’s schedulability based on the response time and allocate the processors. Then, a task’s priority assignment function with multiple attributes, including criticality, urgency, and the total value, is constructed. Besides, a scheduling algorithm titled by SSPS has been proposed with the schedulability analysis algorithm and the priority assignment above. In the SSPS, we allocate the tasks inLO-criticality mode, while in HI-criticality mode, the SSPS not only finish the HI-criticality tasks but also choose the LO-criticality tasks to execute under the utilization of the processor’s slack time globally. The experimental results illustrate that the SSPS could achieve the best performance among the existing algorithms.However, there are still some limitations of the SSPS algorithm. In practical 6G-based edge computing applications, the task real-time scheduling is often related to the sharing of limited resources. With the heterogeneous multiprocessors’ development, heterogeneous will be more the case for the 6G-based real-time applications. We will explore the scheduling and resource sharing issues of edge computing of heterogeneous multiprocessors based on the SSPS algorithm. Besides, in other complex real-time applications, like parallel industry systems and smart industrial networks [31–33], it needs to consider several factors in data transmission and task scheduling; we are also planning to investigate these issues. Moreover, we notice that modern IoT devices are increasingly being equipped with multiple network interfaces; our future work will consider to apply the proposed SSPS algorithm to optimize the promising multipath parallel data transmission methods [34, 35] for the multihomed IoT environment.



---

*Source: 6663199-2021-03-23.xml*