1. Introduction

The relentless developments in microelectronic technology enable processor manufacturers to fabricate more computational elements (cores) on a single chip to realize high performance and better reliability at low-cost. Such integrated systems are efficiently used in numerous safety-related industrial sectors (e.g., automotive, medical, aerospace, home electronics market, nuclear power station, etc.,) to fulfil the radically increased computing demands of safety-critical applications. A system is said to be safety-critical whose malfunction might lead to loss of human life or serious damage to property/environment. Most of the safety-critical domains are mixed-critical which consolidate various functionalities with different criticality levels (i.e., importance) on a common computational platform. The adoption of multicore processors for MCS will be driven by the increasing demand of computational power, development cost, and by SWaP (Space, Weight, and Power consumption) concerns.

An excellent example of MCS is the Unmanned Aerial Vehicles (UAV), generally known as pilotless aircrafts or drones [1]. Drone is a remotely operated airborne vehicle and finding applications in different private and public sectors ranging from military operations to traffic monitoring. It will have combat and surveillance abilities surpassing those of today’s piloted airplanes. UAV combines tasks of different criticalities and executes them on a common embedded platform. The workloads (i.e., tasks) of UAV can be characterized into three categories:

1. 1.

   Flight-critical tasks: High-level workloads that execute safety-related functionalities, such as flight control and trajectory computation to preserve the stability of aircraft, losing which a drone cannot be flown securely. The failures of these tasks can lead catastrophic consequences for the aircraft and hence need to be executed with the highest level of assurance.

2. 2.

   Mission-critical tasks: Low-level tasks, which are concerned with surveillance objectives such as tracking potential targets, navigation services, and parking assistance, losing which a drone is still considered safe. Malfunction on these tasks can result in minor service disruption in the system that is not catastrophic.

3. 3.

   Non-critical tasks: Tasks that execute the least important background activities. Task associated with vehicular entertainment, such as music streaming, is a good example of non-critical functionality that is least important for the specified mission.

Criticality is the degree of required protection against failure for a subsystem. It is called as Safety Integrity Levels (SIL) or Design Assurance Levels (DAL). These SILs reflect the required level of risk reduction in the engineering of a safety-related system and hence, influence all the phases of designing, implementing, testing, and certification processes. For example, in aeronautics standard DO-I78B, there are five SILs, characterized based on their level of jeopardizing produced by the failure of the task: catastrophic; hazardous; major; minor; no effect [2]. The task with higher criticality level indicates that a higher degree of guarantee is required for the correctness of system behaviour. For instance, in the control system of a UAV performing reconnaissance assignment, it is essential to assure the correctness of flight-critical activity such that the flight does not crash, than for mission-critical activities like sensing and transmitting images.

MCS often essential to be certified according to their criticality by a standard statutory third party, called as a Certification Authority (CA) (e.g., Federal Aviation Authority (FAA) in US and the European Aviation Safety Agency (EASA) in Europe for aerospace industry) [3]. Certification (i.e., conformity of assessment) is about guaranteeing different levels of the rigorous correctness of the system. To certify the correctness, CA mandates extremely rigorous and conservative assumptions regarding the run-time behaviour of the system, which are very unlikely to befall in reality. These authorities are not concerned about anything else apart from the safety of the aircraft. It is not incumbent on them whether the mission-critical functionalities are performed in time or not. Conversely, the entire system, comprising both the flight and mission-critical applications, must be authenticated by the system designers or other standard bodies, who generally use a considerably less rigorous standard than the one used by CAs.

Assimilating various operations on the same computational platform brings lots of upsides to the electronics market, enabling us to schedule more tasks hence maximizing the resource usage while reducing the SWaP requirements of the system. One of the major technical challenges in scheming MCS is formulating a scheduling criterion that exacerbates both the criticality and deadline (i.e., urgency) problems of the tasks while enabling certification. Moreover, it is essential to ensure sufficient separation and timeliness assurances for such MC workloads according to their safety and security levels. Any undesirable interference among these tasks must be prohibited to ensure the service guarantees of safety-related applications.

There is an extensive literature on scheduling MC tasks on both single-core and multicore systems. Unfortunately, traditional scheduling algorithms for MC tasks on multicore processors have at least one of the following crucial limitations that severely restrict the practical applicability of those algorithms:

1. (i)

   Traditional scheduling approaches assume that if any high-criticality task shows its critical behaviour (i.e., it overruns its corresponding nominal low-level Worst-case Execution Time (WCET)), all currently active and upcoming critical tasks in the same processor are likely to show high-criticality behaviour, which is often impractical. Our scheduling algorithm eradicates this dispute by taking the behaviour of every high-level workload into account and leads to improved performance and schedulability.

2. (ii)

   Existing approaches cannot completely adapt the dynamic nature of the applications: the workload can dynamically fluctuate among high- and low-level execution modes.

3. (iii)

   Conventional scheduling algorithms do not deliver a good real-time guarantee for the low-level workloads: since these are performed opportunistically with unbounded termination to assure the timing guarantees for critical workloads. This is undesirable because low-level workloads also need some level of timeliness guarantees (even though with lower-level assurances than the high-criticality tasks).

Motivated by previous investigations on MC scheduling, we develop a new hierarchical scheduling framework, called Clustered-PEDF (C-PEDF) to schedule MC sporadic task systems that overcome the limitations posed by existing scheduling algorithms. The contributions of this paper are four-fold:

• •

  We propose a Clustering-based partitioned MC scheduling strategy for implicit-deadline sporadic workloads on homogeneous (i.e., identical) multicore system, which imposes strong temporal separation between high-level workloads so they cannot influence each other and also provides better timeliness assurance for low-level workloads;

• •

  We devise a C-PEDF scheduling approach which exploits a bin-packing algorithm for effective resource utilization that explicitly accounts the demands of tasks based on their levels of confidence and an Enhanced dual-mode scheduling policy to schedule tasks within a core;

• •

  We develop a mathematical tool for schedulability analysis on multicore platforms under our C-PEDF scheduling approach. According to the schedulability constraints, we develop an evolutionary intelligence technique, namely MINLP model for task clustering, that can enhance the schedulability of the system;

• •

  We evaluate our C-PEDF algorithm extensively against some existing partitioned scheduling algorithms.

Our article is structured as follows: The following Section provides considerable relevant algorithms aiming to schedule MC tasks on single and multicore platforms. The MC sporadic task model is formally defined in Section 3. Our Clustered partitioning MC scheduling strategy upon a single-core processor is discussed in Section 4. We formulate and solve an MINLP model to identify the scheduling constraints in Section 5. Enhanced Dual-mode Scheduling Mechanism is explained in Section 6. Clustering-based partitioned MC scheduling on a multicore processor is described in Section 7. We discuss experimental results in Section 8. We briefly describe our future work in Section 9. Finally, Section 10 concludes this paper.

2. Related Work

Scheduling tasks at different criticality levels on a multicore computational platform is the subject of an emerging research field due to the proliferation of safety-related real-time applications. A large body of MC task scheduling algorithms has already been proposed on single-core and multicore platforms. Conventionally, scheduling algorithms are categorized into two main paradigms: (i) global scheduling (ii) partitioned scheduling.

In a partitioned approach, workloads are always mapped to same cores (processing elements) and task migration is not allowed. This type of scheduler exploits distinct queues for each core and each task is mapped to one particular core a priori, and will only be scheduled on that core. Partitioned algorithms are often a favorable choice for hard real-time applications since it delivers a simple and more predictable operation [4]. The major disadvantage of this approach is inefficient resource utilization owing to assignment problems that arise in the modeling of scheduling tasks to processing elements.

A global scheduler allows any task to execute on any core and migrates them across multiple executing cores. These approaches are often a better choice for soft real-time applications because the task-to-core mapping disputes that arise under partitioning approaches are mitigated if the limited delay is acceptable [5] [6]. A Global scheduler is most appropriate for workloads that are delivered based on the average execution time [7]. One key disadvantage of global scheduling is the interference across shared resources which make the WCET analysis more challenging.

The MC task scheduling problem was first identified and formalized by Vestal [8], in the scope of the static-priority preemptive scheduling. In his work, the schedulability is based on the WCET estimates of workloads of equal or greater priority. Vestal demonstrated that, from the viewpoint of low-criticality tasks, the WCET assigned for high-criticality tasks are unnecessarily pessimistic. Hence, the author suggested that schedulability tests for low-criticality workloads be dynamically adjusted to adapt less pessimistic WCET parameters for high-criticality workloads. This approach has been proved to be optimal by Dorin et al. [9]. Later, Baruah et al. extended Vestal’s algorithm [8] to allocate static priorities on a per-job basis (instead of task level). They introduced an algorithm, named OCBP (Own Criticality-based Priority), to address the asymmetric effects among various criticality levels by exploiting more global knowledge of the system [10]. Such a global knowledge is much more effective than simple scheduling constraints like urgency or importance, and OCBP significantly outperforms other policies like EDF and Criticality Monotonic (more critical tasks have greater priority).

To explore the exact intricacy of the MC scheduling algorithms [10], Baruah et al. presented [11] two necessary schedulability conditions, the Worst-Case- Reservations (WCR) and OCBP. This work was extended by Li and Baruah [12] using a static-job-priority scheduling policy based on the OCBP condition, as well as in some following works [11], [13], [3]. All of the above approaches have focused on a single-core processor, but of late efforts have shifted in the direction of multicore platforms.

To our knowledge, the MC task scheduling on multicore platforms was first proposed by Li and Baruah [14]. Later, Gu et al. [15] extended the work on uniprocessor MC scheduling [16] to multicore systems and presented two improvements for processor schedulability by exploiting criticality-cognizance policy. Mollison et al. developed a scheduling heuristic for MC tasks on multicore platforms, implementing various methods (i.e., Cyclic Executive, partitioned- EDF, global-EDF and global best effort) for five different criticalities and enabling temporal isolation between tasks through a bandwidth reservation server [17]. In this work, the more critical tasks are executed with high priorities and the less critical tasks can run in the residual slack time.

Pellizzoni et al. developed a reservations-based scheme to enable sufficient separation between tasks with different criticality levels. They proposed an architectural technique for facilitating such isolation despite to allow some required interferences (e.g., in the sharing of non-preemptible system resources) among applications of various criticalities [18]. Their objective is not on enhancing processor utilization, but on guaranteeing isolation. Anderson et al. introduced a two-level hierarchical approach with a bandwidth reservation server to ensure timing isolation between tasks [19]. They also analyzed the importance of slack re-distribution methods to reallocate residual computing capacity at higher criticality levels to lower criticality levels.

Kelly et al. studied the issues of schedulability that arise in the conventional partitioning approaches under static-priority scheduling on multicore systems. They proposed an SIL-based WCET for the tasks and a dispatching algorithm for mapping tasks to processor [20]. In order to explore both general and criticality mode change protocols, Burns surveyed the pessimistic assumptions of high criticality tasks in the higher criticality modes [21]. Petters et al. analyzed the significance of timing isolation of tasks for MCS and explored several problems in designing such systems in practice [22]. The disadvantage of the timing isolation method is that it operates on rigorously over-provisioning system resources, which may cause an adverse impact on the resource allocation cost and power performance of the system.

In contrast to these approaches, our scheduling algorithm can provide isolation between criticality levels from the perception of temporal correctness. The propagation of high-level execution behavior of a particular task is prohibited by enabling strong isolation between various clusters. In order to maximize the total schedulable utilization, our algorithm allows the system to transit back from high- to low-level execution mode as soon as all critical workloads show their low-level execution behavior.

3. System Model and Notation

In this section, we formally define the MCS task model and describe terms and notions used in this article. Since our eventual interest is in the scheduling of finite collections of recurrent (periodic or sporadic) MC tasks, we will consider the scheduling instance contains a finite set of sporadic tasks upon a homogeneous multicore platform. For simplicity, we confine our attention to a dual-criticality system. The high-critical tasks must finish their execution before their next release time. We relax the timeliness constraints for low-critical tasks in that some level of deadline misses are tolerated. In a dual-criticality task system, each sporadic task is defined as τ_i = (P_i, D_i, £_i, C_i¹, C_i²) with the following semantics:

• •

  i ∈ N⁺ is a unique index of task (i.e., 1 ≤ i ≤ n)

• •

  P_i ∊ R⁺ is the minimum inter-arrival time (period) of workload τ_i.

• •

  D_i ∈ R⁺ is the completion deadline of task τ_i. We consider an implicit-deadline sporadic task system in which each task τ_i has a deadline D_i equal to its period P_i. (i.e., ∀ τ_i ∈ τ, P_i = D_i), meaning that each task must be finished before its next release time.

• •

  £_i ∈ {1, 2} specifies the criticality of the task τ_i. Tasks with £←1 and £←2 designating low- and high-criticality level respectively.

• •

  C_i¹ ∈ N⁺ specifies the WCET of τ_i at the low-criticality level.

• •

  C_i² ∈ N⁺ specifies the WCET of τ_i at the high-criticality level.

Every high-criticality task τ_i² is represented by two WCET values: (i) more pessimistic, high-level WCET C_i² considered by CA; and (ii) a less pessimistic, low-level WCET C_i¹ expected by the system engineer. This is because the high-level WCET is extremely more pessimistic than low-level WCET (to ensure timeliness guarantee). Therefore, for each high-criticality task C_i² ≥ C_i¹. Each low-level task τ_i¹ is characterized by a single low-level WCET C_i¹. We also consider that the low-criticality tasks are enforced to suspend after C_i¹ time units of execution. Tasks are not permitted to migrate across cores after assignment as we consider partitioned scheduling policy. The notations used to describe the proposed scheduling mechanism are listed in Table 1.

Assume the first jobs of all the tasks have arrived at time zero. Task τ₁² is flight-critical which has criticality level 2 (higher-criticality level) and other two tasks τ₁¹ and τ₂¹ are only mission-critical with criticality level 1 (lower-criticality level). C_i¹ defines low-level WCET and C_i² defines the high-level WCET.

4. Clustering-based MC scheduling on single-core Processor

In order to impose strong isolation among high-level workloads and to decrease their service intervention with low-level workloads, each high-level workload τ_j² is scheduled with a group of low-level workloads and coalesces both in a distinct cluster. In our scheduling architecture, tasks within each cluster are scheduled under a budget-driven scheduling mechanism, and clusters are scheduled using EDF strategy.

4.2. Mode Transition Protocol

The basic idea of the runtime mechanism used in our scheduling strategy is the operation of mode transition protocol. The scheduling process within each cluster S_j is achieved in cycles; each cycle corresponds to a period of the executive task τ_j² (i.e., P (τ_j²)). Within each cycle, there can be three distinct behaviours. These three run-time behaviours seem to reveal three different operating modes, which are shown in Fig. 1.

1. (i)

   Low-criticality behaviour (L-Mode): The system starts it’s execution with this normal mode, where currently-active job (arrived, but not yet finished) of task τ_j² has not yet reached its respective C_i¹ and hence it is in L-Mode. The entire tasks in the cluster are executed to provide the low-level assurance.

2. (ii)

   Transition or switching behaviour (S-Mode): If any active job of τ_j² overruns it’s low-level WCET, then the system switches immediately to high-level execution behaviour during the active S-period. All the member tasks in the cluster are cancelled to provide the high-level assurance.

3. (iii)

   High-criticality behaviour (H-Mode): In this mode, an active job of τ_j² has either completed or executed beyond its C_i¹, so it is known whether the cluster is in L-Mode or H-Mode. If the executive task has really completed and the cluster has not yet depleted its reserved execution budget, any suspended member tasks will remain serviced; but, if they do not finish by the last S-period of every cycle (whereas another executive task arrives) or by their deadlines, whichever is earlier, they likely to be discarded. If the cluster is in H-Mode, the member tasks continue to be suspended. If at least one executive task overruns its corresponding high-level WCET C_i², then the scenario is called erroneous.

Fig. 1.

Mode transition strategy in a cluster

4.3. Three-mode Budget-driven Scheduling within a Cluster

We now provide the execution semantics of our mechanism, describing what happens during each cycle of the scheduling process. Consider the allocated execution budget of the cluster S_j is E_j and the number of execution replenishments in any P(τ_j²) is HI_j. As shown in Fig. 1, we assume that L-Mode lasts for aj S-periods, that is, the active job of τ_j² either changes to the H-Mode or has completed in (a_j +1)th S-periods. In every cycle, tasks are executed according to their predefined budget values, t_j, e1_i and e2_i (i.e., i = 1,2,3…n). The technique for estimating these constraints is explained in the next section.

L-Mode ([0, a_j] S-periods): In order to realize the low-level assurance, in each [0, a_j] S-periods, workloads are executed as: if there a “re any incomplete member tasks, the active job of τ_j² is performed first for a definite amount of time t_j ≥ 0 (as a maximum). As soon as this job finishes, member tasks are performed in a non-decreasing order of the task index, where all τ_i¹ is allotted with an execution budget of e1_i ≥ 0. If there are no incomplete member tasks, the active job of τ_j² is performed until it finishes its execution or the reserved execution time of the particular cluster is exhausted.

The pre-allocated budget parameters should hold the following conditions:

1. (i)

   The entire execution budget assigned to all workloads in the cluster should not overrun the reserved execution budget E_j of the cluster. Hence,

   (9)Ej≥tj+Σi=1ne1i

2. (ii)

   As the active job of the executive task exhibits its normal behaviour, the execution time allocated to τ_j² in this L-Mode should not overrun its low-level WCET, i.e.,

   (10)Cτj21≥aj×tj

S-Mode ([a_j, (a_j+1)] S-period): In order to realize the high-level assurance, the active job of τ_j² is performed first with an allocated execution time t_j. If this executive job finishes its execution, member tasks are executed until E_j is depleted (whereas some member jobs may be suspended). Else, the system will change from low- to high-level execution mode and will remain performed until it finishes or E_j is depleted.

As stated above, condition (9) should hold to guarantee the budget of t_j for executive task τ_j² and the budget e1_i for each member task τ_i¹. Furthermore, since the active job of τ_j² will change to the H-Mode if it cannot finish with t_j, the budget expected by τ_j² before the behaviour change should be greater than or equal to its corresponding low-level WCET. Hence,

(11)(aj+1)×tj≥Cτj21

H-Mode ([(a_j+1), HI_j] S-periods): In order to provide the high-level assurance, in each of the last (HI_j−a_j−1) S-periods, tasks are executed as follows: if the active job of τ_j² has not finished in the (HI_j−a_j−1) S-period, it will be performed until it finishes its execution or the received budget E_j is depleted. Else, member tasks are serviced by non-decreasing task index, where each τ_i¹ is assigned an execution time of e2_i ≥ 0. Since the entire budget E_j will be allotted to member tasks, we can assign more budget to each member. i.e.

(12)0≤e1i≤e2i

At the same time, the budget allotted to the entire low-level workloads should not overrun the reserved execution time of the cluster:

(13)Ej≥Σi=1n e2i

We now demonstrate our scheduling strategy using following example.

Example 2:

Consider the cluster comprised of three tasks in the Table 3. The base period of the cluster can be calculated as P_S1 = gcf (15, 10, 15) = 5. Assume the execution time allotted to S₁ is E₁ = 4.25 and other scheduling constraints are a₁=0, t₁=3, e1₁=1.25, e2₁=2.75, e1₂=0 and e2₂=1.5. Fig. 2 exemplifies the L-Mode behaviour of the executive task, whereas in Fig. 3 it shows its H-Mode behaviour. Each cycle covers HI_j = P(τ₁²) / P_S1 = 15 / 5 = 3 S-periods (i.e., 15ms) and involves only L-Mode and H-Mode (since a₁ = 0).

Fig. 2.

Scheduling of the task set under L-Mode.

Fig. 3.

Scheduling of the task set under H-Mode.

In figure 2, for the first S-period (i.e., [0, 5]), we can see the executive task τ₁² is first performed for t₁ = 3 and finishes its execution; then, the member task τ₁¹ is performed for the execution budget e1₁ = 1.25 (τ₂¹ is not performed at this interval since e1₂ = 0).

Since the cluster is in L-Mode, both member tasks τ₁¹ and τ₂¹ are performed in the second S-period ([5, 10]) and third S-period ([10, 15]) for e2₁ = 2.75 and e2₂ = 1.5 correspondingly. The second scheduling cycle ([15, 30]) works in the same way, but τ₁¹ completes before depleting its entire allotted budget in the time interval [25, 30].

In Fig. 3, τ₁² overruns its low-level WCET in the first cycle ([0, 15]), so the cluster is changed immediately to high-level execution behaviour, and all member tasks are cancelled (till τ₁² finishes). In the interval ([15, 30]), τ₁² continues in L-Mode, therefore τ₁¹ and τ₂¹ are performed normally, according to their allotted xecution time. In the first S-period of this second cycle, (i.e., [15, 20]), neither τ₁¹ nor τ₂¹ is performed. The reason is, the currently-active task τ₁¹ has been suspended at time 15ms when next τ₁² arrives, whereas the budget allotted to τ₂¹ is e1₂ = 0. It is important to note that only few member tasks violate their timing constraints: member tasks arrived in [0, 15] are discarded, but the entire member tasks arrived in [0, 15] are schedulable.

Let us consider a cluster S_j = {τ_j², τ₁¹, τ₂¹,..., τ_n¹}. Here, we first develop the MC schedulability constraints for S_j under our mode transition protocol with a pre-allocated execution time E_j and other constraints a_j, t_j, e1_i, e2_i (1 ≤ i ≤ n), where t_j ≥ 0, e1_i ≥ 0, e2_i ≥ 0 and a_j > 0. We then identify the sufficient schedulability condition for a cluster upon a single-core system. Lemma 1 gives the schedulability conditions for every member task τ_i¹.

Lemma 1:

All the member tasks τ_i¹ (1 ≤ i ≤ n) are guaranteed to be schedulable if and only if all the conditions (9) – (14) satisfy, where the condition (14) is given below:

(14)NiOL×e1i+(LOij−NiOL)×e2i≥Cτi11

where NiOL is the upper bound of S-periods in P(τ_i¹) that overlap with L-Mode and S-Mode of a scheduling cycle. It is calculated as follows:

(15)NiOL=⌊LOijHIj⌋×(aj+1)+min{LOij mod HIj,aj+1}

Example 3:

Let us use an example given in Table 4, with pre-allocated execution time E₁ = 1.5, a₁ = 1, e1₁ = 0 and e2₁ = 1.5 to exemplify the lemma 1. The estimated value of other scheduling parameters are P_S1 = 5, LO_i^j = 3, and HI_j = 5. The upper bound of the number of overlapping S-periods during is calculated as follows:

NiOL=⌊35⌋×(1+1)+min{3 mod 5 ,1+1}=2

Task	Given parameters				Calculated parameters
	£	Ci1	Ci2	Pi(τi)	Ui1(τi)	Ui2(τi)
τ12	2	3	7.5	25	0.12	0.3
τ11	1	1.5	-	15	0.10	-

Table 4.

An example cluster with task parameters

There are 2 overlapping S-periods for the first and fourth arrivals of τ₁¹, 1 for the second and third arrivals, and zero for the fifth arrival as illustrated in Fig. 4. Now, we can certify that all jobs of τ₁¹ can complete before their deadlines.

Fig. 4.

The number of overlapping S-periods

Lemma 2:

Each executive task τ_j² collects an execution budget of at least Cτj21 when it is in L-Mode and at least Cτj22 when it is in H-Mode by its deadline if the conditions(9), (11) and the following condition (16) satisfy:

(16)Cτj22≤aj×tj+(HIj−aj)×Ej

From lemma 1 and 2, we can drive theorem 2.

Theorem 2:

Suppose each cluster S_j = {τ_j², τ₁¹, τ₂¹, τ₃¹,…, τ_n¹} is assured to collect an execution budget of E_j in each of its periods. Then, the cluster is MC-schedulable with constraints E_j, a_j, t_j, e1_i, e2_i (1 ≤ i ≤ n) if all of the conditions (9) – (16) are met.

Let G_λ be the group of clusters scheduled on a core λ. Note that each cluster S_j ∈ G_λ is scheduled with other clusters in G_λ as a normal sporadic task with period P_Sj and budget E_j using EDF policy. The cumulative total processing capacity of the group of clusters is denoted by U_λ. According to the schedulable demand-bound functions of EDF [24], all clusters in G_λ are able to schedule if:

(17)Uλ=ΣSj∈GλEjPSj≤1

Hence, every cluster S_j is received an execution budget of E_j in each P_Sj if U_λ ≤1. From the above inequality (17) and Theorem 2, now we are ready to derive the sufficient condition and establish our main theorem for clusters schedulability.

Theorem 3:

Let G_λ be the group of clusters scheduled on the core Ψ_λ (based on any task clustering approach). If for all S_j = {τ_j², τ₁¹, τ₂¹, τ₃¹, τ₄¹,..., τ_n¹} in G_λ, there exist value E_j ∈ R⁺ and constraints a_j ∈ N (a_j < HI_j) and t_j, e1_i, e2_i ∈ R⁺ where 1 ≤ i ≤ n such that U_λ ≤1 and the conditions (9) – (16) are met, then every cluster mapped to the core λ are MC schedulable.

5. Mixed Integer Nonlinear Programming Model for Task Clustering

Fig. 5 illustrates a unified overview of our proposed mechanism. Consider a core Ψ_λ in which the set of tasks τ(Ψ_λ) = (τ₁²,…… τ_m², τ₁¹,…., τ_n¹) are scheduled. Each task has its own parameters P_i, D_i, £_i, C_i¹ and C_i². Our objective of the task clustering is to find (i) a group of the member tasks that will be clustered with executive task τ_j² (1 ≤ j ≤ m) into the cluster S_j; and (ii) for every cluster S_j, the values of the execution budget E_j and the other constraints a_j, t_j, e1_i, e2_i, P_Sj, LO_i^j and HI_j.

Fig. 5.

Overview of proposed mechanism

Here, we develop an MINLP model for clustering according to the schedulability constraints. Since the clusters are executed using EDF policy with periods P_Sj and a pre-allocated execution time E_j, the smaller utilization indicates better schedulability. Hence, the objective function of the MINLP problem is to minimize the overall utilization of the clusters so as to enhance their percentage of schedulable tasks. The parameters of the MINLP are identified from the MC schedulability constraints of the clusters. However, the MINLP is of NP-hard complexity and therefore computationally expensive to be solved every time in order to determine the optimal solution.

In order to allow a member task to exploit the overprovisioning of more than one executive task, we enable each τ_i¹ to present in multiple clusters – that is, every τ_i¹ can obtain pre-allocated execution time from multiple clusters and the τ_i¹ is performed whenever it is organized in a cluster. In the meantime, all the clusters are serviced serially on a common computing platform; τ_i¹ is not ever performed concurrently by more than one cluster. Therefore, if the reserved execution time that the low-level task is assured to collect from all of its clusters is at least C_i¹, then τ_i¹ is schedulable.

According to the above tenet, new variables (ej1_i, ej2_i) are used to specify the predefined execution times that τ_i¹ can collect from cluster S_j in each scheduling modes of S_j (rather than using an only one set of values (e1_i, e2_i)). These variables are also used to specify whether the member task has its place in the cluster S_j: if ej1_i = ej2_i = 0, then τ_i¹ does not belong to S_j, or else it does. According to the Theorem 3, the task set τ(Ψ_λ) is MC schedulable if all of the conditions (9) – (16) are satisfied for each cluster S_j. Hence, the scheduling parameters for each cluster S_j can be calculated by replacing e1_i with ej1_i, e2_i with ej2_i, N_i^OL with N_i,j^OL in the conditions and rewriting the condition (14) as

In order to decrease the processing intractability, rather than using the condition (9), we use Ej=tj+∑i=1nej1i. Now, we can summarize a complete MINLP formulation for our utilization minimization problem in Fig. 6. Putting together the objective function with the constraints, we define the MINLP model for our scheduling mechanism. According to the schedulability restraints, the MINLP model finds which tasks can be clustered to minimize the utilization. Given a set of mixed-critical workloads, if the overall cluster utilization derived from the formulated mathematical model is greater than 1, then this task set is considered to be not schedulable by the algorithm and will be precluded by the scheduler.

Fig. 6.

Scheduling constraints for MINLP formulation

Aiming to optimize the solution of the assignment, the MINLP problem is solved by a branch-and-bound solver, MINOTAUR (Mixed-Integer Nonconvex Optimization Toolbox: Algorithms, Underestimators, and Relaxations) [25, 26]. It is one of the best open-source solver toolkits which offer methods and data structures to study and solve complex MINLPs directly.

MINOTAUR provides a number of algorithms and advanced routines/libraries to find the solution of the complex MINLPs and can be directly called from several other codes like AMPL (A Mathematical Programming Language) scripts [27], FORTRAN or C++. In order to solve MINLP mathematical model, MINOTAUR exploits LP/NLP-based branch-and-bound (LP/NLP-BB) algorithm [28]. The non-negative parameters a_j, t_j, ej1_i, ej2_i and t_j indicates that the MINLP problem is convex, which guarantees that the solver provides an optimal result of the given mathematical model. The LP/NLP-BB solver is started by relaxing the linearization of the original MINLP problem and building a relaxed mixed-integer linear programming (MILP). The nonlinear constraint of an MINLP problem is represented by the following equation.

The MILP relaxation provides a close approximation to the original MINLP problem if we find the linear approximation about more points. On the other hand, the number of integrality constraints in the MILP problem increases with the number of linearization points and obviously reduces the speed of operation of MINOTAUR. To circumvent this issue, linearization limits obtained from a single point are included in the initial iteration. This initial estimate is considered as the initial solution of the relaxed nonlinear programming (NLP) [28]. Then, we take linearization for more points at which the constraints violated significantly. The LP/NLP-BB solver initiates by finding the solution for a linear programming (LP) relaxation and sets the incumbent value INC_V = ∞ [28]. The solver then generates a search tree to resolve very tight MILP relaxations. In each iteration, we exclude an LP subset from the list and resolve it. If the obtained result is more than the current INC_V, we reject this subset since it does not encompass any value superior than the INC_V. If the r result ẑ obtained from the linear programming subset has a fractional value, two additional subsets are created by subdividing (branching) the noninteger variable. Afterwards, these two newly created subsets are included in the list of unresolved subsets. If ẑ holds every integer constraints, then we inspect whether it holds the nonlinear constraints or not. If it is feasible, we have a new INC_V. Otherwise, we successively linearize one or more perturbed constraints about ẑ and continue. When there are no more remaining subsets left to resolve the algorithm will terminate.

In our problem formulation, the MINLP has m integer variables, 2mn+6m constraints, and m+2mn real variables, where m and n are the number of member and executive tasks, correspondingly. Note that depending upon the size of the input (the size of task set), the amount of variables and constraints associated with the problem is varied. In the worst case, the solver needs to solve an exponential amount of linear and nonlinear subsets. Nevertheless, in reality, MINOTAUR produces significantly higher quality solutions in much less time. The mathematical model shown in Fig. 6 can easily be reformed by accounting other kinds of constraints also – e.g., restrictions on cluster count that each member can fit, restrictions on the number of member tasks in each cluster, etc.

6. Enhanced Dual-mode Scheduling Algorithm

Unfortunately, the Three-mode budget-driven scheduling strategy introduces excessive overhead and unnecessary context switching when there are more member tasks in a cluster (refer Fig. 7). In order to evade this problem, we develop an Enhanced dual-mode (E-Mode) algorithm that schedules the member tasks using EDF policy with reduced switching overhead. Given a cluster S_j with allocated execution time E_j, a_j and t_j, the E-Mode mechanism operates as follows:

Fig. 7.

Three -mode Budget-driven schedule

Mode I ([0, (HI_j−1)] S-periods): For every S-period, if there are some incomplete member tasks in the cluster, the active job of τ_j² is performed first for a certain amount of time (up to t_j), and then the member tasks in the cluster are performed using EDF approach. Else, the active job of τ_j² is performed until it finishes or E_j exhausts.

Mode II (the last (HI_j − a_j) S-period): For every S-period, the job of τ_j² is performed first until it completes and then the incomplete member tasks in the cluster are performed using EDF strategy. If the active job of τ_j² is in H-Mode, the member tasks that cannot complete when their deadlines are met or another τ_j² arrives are discarded. In contrast to the Three-mode scheduling mechanism, our E-Mode strategy considers (a_j +1)th S-period and the last (HI_j − a_j) S-periods as a single mode. The rationale behind this is that under the Three-mode mechanism, different execution budgets (e1_i and e2_i) may be applied to each τ_i¹ in (a_j +1)th S-period and in (HI_j − a_j −1) S-periods, whereas under the E-Mode policy, member tasks are always executed using EDF approach.

Fig. 8.

Schedule using enhanced dual-mode

From Theorem 4, we can estimate the constraints for E-Mode mechanism by resolving the MINLP model formulated in Section 5. E-Mode can alleviate the switching overhead by dividing the number of low-level workloads as a main constraint. Furthermore, we can also provide a timing assurance for each τ_i¹ providing a restriction on the number of clusters in the system.

7. Clustering-based Partitioned MC scheduling on a Multicore Processor

We now briefly discuss our Clustering-based partitioning EDF algorithm for dispatching admitted workloads to multiple cores. Let us denote a processor Ψ with λ homogeneous cores as Ψ = {Ψ₁,….Ψ_j….,Ψ_λ}. Consider the group of tasks assigned to each core Ψ_j is represented by τ(Ψ_j). When the number of on-chip core increases, C-PEDF can satisfy the new requirements.

Our proposed approach targets to distribute the tasks among all cores while choosing an executive (member) task to allocate based on decreasing executive (member) task utilization. Consider τ² = {τ₁²,…,τ_n1²} be the group of executive tasks and τ¹ ={τ¹_n1+1……, τ¹_n} be the group of member tasks. The formal steps of C-PEDF for scheduling tasks with dual criticality levels are given in Algorithm 1.

C-PEDF starts by assigning τ(Ψ_j) to null and by ordering the given set of workloads. Executive tasks are arranged in descending order of their U_i²(τ), and tasks with equal U_i²(τ) are again arranged in decreasing order of U_i¹(τ). Member tasks are arranged in descending order of U_i¹(τ), and workloads with equal U_i¹(τ) are again arranged in ascending order of their inter-arrival time. The motivation behind this ordering is: for executive tasks with equal U_i²(τ), a task with a higher value of U_i¹(τ) typically has less overprovisioning; and for member tasks with equal U_i¹(τ), the workload with a lesser value of inter-arrival time will likely have a minimum utilization rate of overprovisioning, since P_Sj is selected as the gcf of the inter-arrival time of all the workloads.

Our C-PEDF then chooses the task (τ_s) with the highest utilization. Then, the algorithm selects an appropriate core Ψ_j for this workload, such that the cumulative utilization for selected workload in conjunction with the active workloads on this core is minimal; hence, it distributes the tasks across cores. If the cumulative cluster utilization on the chosen core Ψ_j does not go beyond one, τ_s is allocated to Ψ_j. Or else, the C-PEDF terminates with a failure report. If the workload is fruitfully assigned to a core, the C-PEDF reports “success”. According to the Theorem 4, the scheduling achieved by our C-PEDF always guarantees the real-time performance of the admitted tasks. The equally critical workloads on a core are directly scheduled under EDF policy.

Input: An MC task system with a group of executive tasks τ2 = {τ12,..., τn12} and group of member tasks τ1 ={τ1n1+1 ……, τ1n} to be scheduled on a processor Ψ with λ homogeneous cores.

Output: Real-time MC schedule

1: τ(Ψj)←0, for all j = 1,..., λ.

2: for i ← 1 to n1 ►for executive tasks

  a) Calculate the utilization Ui2(τ)

  b) Order task set in descending order of Ui2(τ)

  c) Order tasks with same Ui2(τ)value in descending order of Ui1(τ)

3: for i ← n1 to n ►for member tasks

  a) Calculate the utilization Ui1(τ)

  b) Order tasks in descending order of Ui1(τ)

  c) Order tasks with same Ui1(τ)value in ascending order of its inter-arrival time (Pi)

4: while τ2 != 0 and τ1 != 0 do ► Clustering

5:     τs ←NIL

6:   if τ1 != 0 then

7:     τs ← The first member task from τ1

8:   if τ2 !=0 then

9:     τs* ←The first executive task from τ2

10:     if τs = NIL ||

      τs!= NIL&& U1(τs)< U2(τs*) then

11:        τs←τs*

12: Remove τs from its group ► Bin-packing

13: Select a core Ψj ∈ Ψ that has a minimum cluster utilization for τ(Ψj) ∪ {τs}

14: if the cluster utilization for tasks

    τ(Ψj) ∪ {τs} ≤ 1 then

15:     τ(Ψj) ← τ(Ψj) ∪{τs}

16: else

17:   return FAILURE

18: return SUCCESS

8. Experiments and Results

We investigate and empirically assess the schedulability of C-PEDF by conducting extensive simulation experiments. To evaluate the effectiveness of our suggested scheme, we experimentally compare the performance of C-PEDF against the following partitioned MC scheduling approaches:

• •

  DC-RMS: a scheduling algorithm from [20] in which the workloads are ordered in descending order based on their level of importance and higher priorities are allocated to workloads with lower inter-arrival time (i.e., Decreasing Criticality-Rate Monotonic Scheduling);

• •

  DU-RMS: a scheduling algorithm from [20] in which the workloads are arranged in descending order based on their utilization and higher priorities are allocated to workloads with lower inter-arrival time (i.e., Decreasing Utilization-Rate Monotonic Scheduling);

• •

  DC-AOPA (Decreasing Criticality-Audsley’s Optimal Priority Assignment): an approach from [20] in which priorities are allocated in order, from lowest to highest. In each cycle, the algorithm finds an appropriate workload for the next priority level. If so, it gives that priority, then allocates the subsequent priorities to the other workloads in a similar way;

• •

  DU-AOPA (Decreasing Utilization – AOPA): an approach from [20] in which the tasks are scheduled according to their utilization and AOPA algorithm is used for priority allocation;

• •

  MC-PARTITION: EDF-based approach relies on Virtual Deadlines from [29];

• •

  EY-FF: an enhanced Ekberg and Yi (EY) algorithm [13] exploiting First-Fit (FF) packing policy from [15];

• •

  MPVD (Mixed-criticality Partitioning with Virtual Deadlines): a further extension of EY algorithm with the hybrid packing model from [15];

• •

  E-MPVD (Enhanced-MPVD): MPVD enhanced by the heavy low-criticality task cognizant assignment strategy in [15]; and

• •

  MPVD-OPT: E-MPVD further enhanced by the optimized virtual deadline tuning from [15].

We evaluate our proposed algorithm with the following objectives: (1) to evaluate the effectiveness of C-PEDF in terms of acceptance ratio (i.e. the fraction of the number of tasks that are deemed to be MC-schedulable by the algorithm to the total number of the tasks in the experiment); (2) to analyse how well C-PEDF can defend low-level tasks when an executive task exhibits its critical behaviour; (3) to examine the impact of probability of the generated workload exhibit high-level execution behaviour on Deadline Miss Ratios (DMR) of member tasks; and (4) to analyse the impact of overprovisioning in terms of schedulability on a single-core processor by enabling a member task to present in more than one clusters. The impact factor of member tasks is considered as a metric to evaluate the C-PEDF performance. We specify the impact factor of member tasks as the ratio of such workloads for which at least one job is discarded or violates its timing constraint since an executive task exhibits its critical behaviour. The ratio of low-level tasks that violate their timing constraints is called as DMR.

8.2. MC schedulability

In Fig. 9a – 9c, we depict the fraction of task sets successfully scheduled as a function of the normalized average utilization (load) of the various heuristics in 2- core, 4-core, and 8-core processors correspondingly. We first observe that as the load increases, the acceptance ratio decreases for all compared schemes. This is due to the fact that as the average utilization rises, there are more tasks in the platform that needs to be serviced. Therefore, there is a higher load on the processor, and as a result, more workloads violate their timing constraints.

Fig. 9(a).

MC schedulability for 2-Core systems

Fig. 9(b).

MC schedulability for 4-Core systems

Fig. 9(c).

MC schedulability for 8-Core systems

Consequently, we observe that schemes using AOPA provide better performance as compared to schemes using RMS policies. Therefore, these results prove that the choice of the priority allocation method plays a vital role to enhance schedulability. The results for 4- and 8-core processor reveal that the success ratio of EY-FF reduces as the core count increases. This is due to the uneven assignment of scheduling parameters in EY decreases the possibility of optimizing virtual deadline.

The graphs in Fig. 9c show the acceptance ratio against the system load under different scheduling algorithms on an 8-core processor. We observe that the algorithms MPVD, E-MPVD, and MPVD-OPT provide better performance as compared to EY-FF by distributing the workloads between cores. E-MPVD outperforms MPVD by allocating substantial low-level workloads to cores before high-level workloads, but the success ratio of these two approaches follow the same trend when the system comprises limited low-level tasks.

MPVD-OPT targets to increase the acceptance ratio by means of a virtual deadline optimizing technique, and its acceptance ratio is greater than MPVD and E-MPVD; however, these optimizing technique does not consider the low-level workloads, so it jeopardizes the acceptance ratio of the system. Therefore, the performance of MPVD-OPT is inferior to C-PEDF for all 2-core, 4-core and 8-core processor with higher average utilization. From the results, we can observe that many more tasks can be scheduled under C-PEDF with a given number of cores. The proposed algorithm constantly exhibits a substantial enhancement in the acceptance ratio and outperformed all state-of-art algorithms. Obviously, there is a wide performance gap among the schedulability of C-PEDF and those of other approaches. This is because, with an increase in the number of workloads, there are more opportunities for our C-PEDF to select suitable clusters for each member task.

8.3. Effect of H-Mode behavior on member tasks

In our study so far, we have fixed prob (τ_j²) = 50%. Next, we evaluate the impact factor of the member tasks for varying fractions of executive tasks to get into H-Mode. In Fig. 10, results are plotted for the fixed Uav*(τ)∈{0.65, 0.75, 0.85, 0.95} on a 4-core platform. We observe that only a certain ratio of member tasks is influenced and that this ratio increases with the ratio of executive tasks that show H-Mode behaviour. The reason is, with C-PEDF, the H-Mode behaviour of an executive task has an impact only on member tasks in the same cluster, but not in other clusters.

Fig. 10.

Impact factor of member tasks

We observe some important properties: (i) The relationship is not exactly linear since a group of low-level workloads are clustered with multiple executive tasks, and can thus be influenced by any one of these clusters. (ii) Once all the admitted workloads show H-Mode behaviour (i.e., prob(τ_j²) = 100%), there are still certain member tasks in the system that are not influenced. This is because the cores having only member tasks cannot be affected by the H-Mode behaviour of other clusters. (iii) As expected, the impact ratios are not affected by varying average utilization. This is due to the proportion of member tasks that are influenced hinges mainly on the clustering process and Prob(τ_j²).

8.4. Real-time performance of member tasks

The impact of H-Mode behaviour on the DMR of member tasks in a 4-core processor is plotted in Fig. 11. As expected, there is no task misses its deadline when prob(τ_j²) = 0: when the system is in L-Mode, the C-PEDF can guarantee that the system is schedulable. As the prob(τ_j²) increases, the DMR of the member task is also increased slowly; this is because that the H-Mode execution behaviour of a task can only influence other members within the cluster, but not tasks in other clusters. Furthermore, since the isolation among clusters allows the system to transit back to L-Mode when all executive tasks show L-Mode behaviour, the fraction of a deadline miss of the member tasks can be preserved small even for long-running applications.

Fig. 11.

Deadline miss ratio of member tasks.

It is evident that the DMR plots corresponding to various average processing capacities cross each other, that is, a cluster with a greater value of Uav*(τ) will have a smaller DMR than that of a cluster with a lesser value of Uav*(τ). This is anticipated because the DMR can become lesser as we generate more member tasks, which can be the case when Uav*(τ) rises. It is important to note that the other scheduling approaches reject the entire low-level workloads immediately an executive task shows H-Mode behaviour, so they provide no service assurance for member tasks in the H-Mode.

8.5. Impact of resource overprovisioning on schedulability

We continue to present the impact of resource overprovisioning on acceptance ratio. Fig. 12 shows the impact of allowing member tasks to exploit the overprovisioning of various executive tasks on the schedulability of the given task on a single-core system. Here, N ^m_cluster is the upper bound on the total number of clusters available for each member task.

Fig. 12.

Effect of overprovisioning on schedulability

As shown in Fig. 12, the acceptance ratio increases with N ^m_cluster. Furthermore, the success ratio gap tends to large as the load increases, which further specifies the usefulness of exploiting overprovisioning of executive tasks.

9. Future work

The additional research effort is required before our scheduling approach could be considered appropriate for real tasks. There are two potential directions of our future work: application studies and architecture improvements.

Application studies: We plan to apply our scheduling approach in LITMUS^RT (LInux Testbed for MUltiprocessor Scheduling in Real-Time systems) on an Intel® Xeon® Processor E7440 platform [30]. It is a 32-bit processor consists of 4 cores on a single chip operating at 2.40 GHz, with 16 MB L2 cache per processor and 4 GB of RAM. Each core can process 4 logical threads in parallel. The implementation of extensive measurements campaigns using this testbed will be intended for performance assessments that will give more constructive feedback on the pragmatism of our approach.

Architecture improvements: A substantial amount of improvements to our approach would increase the range of real-time tasks that can be supported on multicore systems. A leading example of this is efficient resource sharing across applications of different safety criticalities. An additional active field of interest is facilitating adaptivity, which is deemed to be an essential concern in future industrial safety-critical systems, which themselves must adapt different run-time operating conditions (environments) dynamically. For instance, in an unmanned aircraft, when previously-undetectable opponent radar stations are found, it might be beneficial to give rise to the share of computing resources of a pathfinding and route planning processes. On the other hand, if an unfriendly guided missile were to be spotted, in order for appropriate action or communication to be performed more quickly, the facility to enable a mode-switch (wherein a new set of tasks replaces those currently being scheduled) might be required. We would like to point out that even though our proposed approach considers a dual criticality system, it is likely to extend this approach to more than two levels. We intend to extend our algorithm to investigate the run-time overhead limitations of the proposed algorithm to obtain a global view of the gains of our approach. Finally, we plan to extend our scheduling strategy to execute multi-criticality tasks on a heterogeneous platform in a hierarchical manner.

10. Conclusions

We have proposed a Clustering-based partitioned EDF scheduling algorithm for scheduling dual-criticality tasks on a multicore platform. In our proposed C-PEDF algorithm, each high-level workload is coalesced in a cluster (to facilitate separation) along with a group of less critical tasks (to maximize schedulability of tasks while preserving the criticality assurance). Within each cluster, tasks are scheduled under Enhanced dual-mode scheduling policy to improve the service level of high-level tasks without jeopardizing the schedulability of low-level tasks. Clusters are scheduled under Earliest Deadline First (EDF) scheduling approach.

Our approach enforces strong temporal isolation between high-criticality tasks to alleviate all inter-task interferences, and it allows more lower-criticality workloads to satisfy their timing requirements. This is due to (i) the undesirable service intervention of high-level workloads on low-level workloads is considerably decreased; and (ii) low-level workloads are not continuously dropped, but rather received sufficient execution when the high-level workload in the same cluster exhibits its critical behaviour. We conduct a schedulability test for the proposed technique, and we demonstrate how workloads can be clustered by means of evolutionary intelligence technique, namely Mixed Integer Nonlinear Programming (MINLP) model. Extensive simulation results reveal that our algorithm significantly outperforms other approaches both in acceptance ratio and the impact factor of low-level tasks.