# EDF-Adaptive: A New Semipartitioned Scheduling Algorithm for Multiprocessor Real-Time

Authors: Shujuan Huang; Tiansen Li; Zhihao Ma; Feng Xiao; Wenjuan Zhang
Journal: Journal of Sensors
 (2021)

---

## Abstract

Most of the multiprocessor real-time scheduling algorithms follow the partitioned approach, the global approach, or the semipartitioned approach which is a hybrid of the first two by allowing a small subset of tasks to migrate. EDF-fm (Earliest Deadline First-based Fixed and Migrating) and EDF-os (Earliest Deadline First-based Optimal Semipartitioned) are semipartitioned approaches and were proposed for soft real-time sporadic task systems. Despite their desirable property that migrations are boundary-limited such as they can only occur at job boundaries, EDF-fm and EDF-os are not always optimal and have higher tardiness and cost of overheads due to task migration. To address these issues, in this paper, we classify the systems into different types according to the utilization of their tasks and propose a new semipartitioned scheduling algorithm, earliest deadline first-adaptive, dubbed as EDF-adaptive. Our experiments show that EDF-adaptive can achieve better performance than EDF-fm and EDF-os, in terms of system utilization and tardiness overhead. It is also proved that EDF-adaptive is able to lessen the task migration overhead, by reducing the number of migrating jobs and the number of processors to which a task is migrated.


---

## Body

## 1. Introduction

The partitioned and global approaches are the classical scheduling algorithms for real-time multiprocessor systems. Because the former assigns tasks statically to processors and does not allow the tasks to migrate, it cannot achieve higher system utilization whereas the latter schedules tasks from a single run queue and the task hence can be migrated [1]. Although the global approach can attain higher system utilization but migrating tasks entails higher run-time overheads, especially in soft real-time (SRT) systems, many approaches have been proposed, based on these two algorithms [2–6] or the hybrid of the two [7–18]. Some approaches are aimed at reducing the switch context or preemption overheads and achieving higher system utilization [19–22].Semipartitioned scheduling extends the partitioned scheduling by allowing a (usually small) subset of tasks to migrate, and these tasks cannot be feasibly assigned to two or more processors by a partitioned scheduling algorithm [23–26]. This type of approach is different from the global ones as the former use push migrations which are planned before execution whereas the latter use pull migrations which are reactive in nature and more difficult to account for and implement efficiently.In this paper, we are particularly interested in two semipartitioned scheduling algorithms, EDF-fm [12] and EDF-os [13], because they are adaptive to SRT systems and allow a migrating task to migrate only between job boundaries, i.e., successive invocations. However, EDF-fm deals with per-task utilization restrictions according to the releasing sequence and cannot fully utilize the underlying hardware platform’s available capacity that makes it nonoptimal. These restrictions preclude any task utilization from exceeding half the capacity of a processor. EDF-fm has two phases as follows:
(1)
Offline assignment, where the tasks are assigned to the processors and meanwhile the tasks’ attributions of fixed or migrating are given(2)
Online execution, where the extended earliest-deadline-first (EDF) scheduling is used to execute fixed tasks and migrating tasks on each processor. Note that a fixed task, i.e., a nonmigrating task, is the task assigned to only one processor and a migrating task is the task assigned to two or more processors in the phase of offline assignmentLike EDF-fm, EDF-os also has two phases, and in the online execution phase, the migrating tasks are statically prioritized over fixed ones. This ensures migrating tasks never miss deadlines. However, in the assignment phase, EDF-os is very different from EDF-fm. It assigns tasks as fixed ones as many as possible using a worst decreasing bin-packing heuristic. All remanent tasks are assigned in decreasing utilization order, by considering each processor and remanent tasks in turn. This approach allows migrating tasks to execute on any number of processors, instead of just two. However, the preemption overheads will be increased.Though EDF-os increases the number of fixed tasks and reduces the number of migrating tasks, it may schedule a migrating task on three or more processors and thus the actual migrating times do not decrease. As a result, since the context switching overheads are also determined by the number of migrating jobs and the preemption times, EDF-os still has higher context switch overheads.In this paper, we propose a novel EDF-based approach that overcomes the limitations of EDF-fm and EDF-os by reducing the number of jobs that miss deadline and making a balance between the cost of overheads and system utilization. The approach partitions tasks and schedules them adaptively, according to their utilization; thus, we dub it as EDF-adaptive. Given a real-time multiprocessor system with periodic tasks, EDF-adaptive first divides the tasks into two sets: one with high utilization denoted asSH and the other with low utilization denoted as SL. EDF-adaptive then chooses tasks from SH and SL whose utilization sum to an integer is less than the number of processors. We call these tasks complimentary. This selection process is repeated until the sum of all integers equals to the number of processors. During the execution, EDF-adaptive separates the processors into different scheduling queues according to the integers and puts these tasks into the corresponding queue. Our experiments have demonstrated that, compared with EDF-fm and EDF-os, EDF-adaptive is able to achieve lower job switching overheads, and the lowest degree of splitting and migrating, while in the meantime maintaining competitiveness in terms of system utilization and slack task minimum tardiness.The remainder of this paper is organized as follows. Related works of semipartitioned algorithms are described in Section2. The system model, definitions, and theorems about different utilization systems and EDF-adaptive algorithm in detail are introduced in Section 3. Experimental evaluations are undertaken to demonstrate the effectiveness of the proposed algorithm in Section 4. Finally, concluding remarks are drawn in Section 5.


## 2. Related Work

As mentioned in the previous section, there are two typical categories of scheduling algorithms for a real-time multiprocessor system, i.e., the global and the partitioned. Since our proposed approach in this paper concerns more on the latter, here, we focus on our review on semipartitioned schedulers, both for hard real-time (HRT) and soft real-time (SRT) systems. The difference between them is that the tasks in HRT are not allowed to miss their deadlines whereas those in SRT are allowed.A variety of semipartitioned schedulers have been proposed for HRT that does not consider job boundary-limited. EDF-WM (Earliest Deadline First with Window constraint Migration) [14] assigns most tasks to processors, allowing some tasks to migrate between processors. But it is not only non-boundary-limited but also works by splitting tasks in a way guaranteeing no job misses a deadline while scheduling all jobs. When all processors share a single run queue, G-FL (Global Fair Lateness) [15] provides lateness bound for all tasks. For each job, G-FL uses a PP (Priority Point) that precedes its deadline. G-FL schedules each job based on the max-lateness bound which is minimized for any task system. C-FL (Clustered Fair Lateness) [16] defines the split factor of a task as the number of subjobs into which each of its jobs is split. By splitting job budgets to create subjobs with shorter periods and the worst-case execution times, such bounds can be reduced to near zero for implicit deadline sporadic task systems. Proposed for periodic task systems, EKG (Earliest Deadline First with task splitting and K processors in a Group) [17] is HRT-optimal when a configurable parameter is reduced in a way that increases preemption frequency.Because non-boundary-limited schedulers above mentioned allow jobs to migrate in any time, it will be expensive in practice if jobs maintain a much-cached state. Some semipartitioned algorithms have been proposed to support SRT systems under bounded deadline tardiness. EDF-fm was first proposed, requiring utilization constraints that render it nonoptimal. To overcome the constraints, EDF-os was proposed by scheduling migrating tasks on three or more processors. Since none of the other migration algorithms mentioned above are job-boundary-limited, we will compare our proposed approach with EDF-fm and EDF-os.


## 3. Task Model and Scheduling Algorithm

### 3.1. Task Model

Assume a sporadic system consists ofM processors and owns N>M tasks τ=τ1,τ2,⋯τN. These sporadic tasks are independent and to be scheduled upon a multiprocessor platform with M≥2 identical processors. In a sporadic task model, a sporadic task is a four-tuple τiri,ei,di,pi where ei, di, and pi are positive integer numbers and ri is a nonnegative integer number and it is characterized by a minimum interarrival time, also referred to as its period pi, a worst-case execution cost eipi, and a relative deadline di and a release time ri. Every task τi may be invoked zero or more times with two consecutive invocations separated by at least pi, time units. Each invocation of τi is referred to as a job of τi. The kth job of τi, where k≥1, is denoted as Ji,k. The release time of the job Ji,k is denoted as ri,k. Each job of τi is executed for at most ei, time units. The absolute deadline (or simply, deadline) of Ji,k, denoted as di,k, is the time at or before which Ji,k should complete execution. Each task is sequential and at any time may be executed on at most one processor.A periodic task system, in which every two consecutive jobs of every taskτi are separated by pi time units, is a special case of a sporadic task system. In this paper, we focus on the periodic task system and assume that di=pi holds for all τi and the first job of each task will be invoked or released at time zero. A task can then be represented using a two-tuple τiei,di. The lth processor is denoted as Pl, where 1≤l≤M. All tasks are synchronous and periodic and have the same initial release date. They are preemptive and independent. The overheads of other shared resources between tasks are not considered.


#### 3.1.1. Utilization System and Tasks

To facilitate the description of our proposed EDF-adaptive, we categorize the real-time system aforementioned according to its task utilization.Defineui=ei/di, where ui is the utilization of task τi. Then, we have the utilization for all tasks Uτ=∑τi∈τui.We define the real-time system as follows:(i)
Single full utilization system, ifUτ=1(ii)
All full utilization system, ifUτ=M(iii)
K full utilization system, if Uτ=K, where K is an integer. Under this scenario, the system may be either underloaded if M>K>1 or fully utilized if K=M. For the latter, it may be an all full utilization system K=M≥2 or a single full system K=M=1; overloaded utilization system, if Uτ>MFor the overloaded utilization system, we schedule the largest subsetτsub so that the total utilization of the tasks’ subset is very close to M. That is, M−∑i=1kui where ε∈0,1 is a minimum float number and k is the number of the tasks in the subset τsub.Each task is allocated a nonzero fraction, or share of one processor with the available utilization of 1.0. If there arek tasks being scheduled on the jth processor, the remanent utilization of this processor is
(1)Ujτ=1−∑i=1kui,where the fraction of the τi’s utilization scheduled on this processor pj, denoted as ui,j, is Ujτ. The total remanent utilization of this system is
(2)Uremτ=M−∑j=1MUjτ.We defineτi as a high utilization task if ui≥1/2, and a low utilization task otherwise. Define SH as a high utilization task set consisting of high utilization tasks, and SL as a low utilization task set consisting of low utilization tasks. We represent SH and SL as follows:
(3)SH=τi∣ui≥12,SL=τi∣ui<12.A high utilization system is defined as a system consisting of onlySH set.


#### 3.1.2. Theorems for EDF-Adaptive Utilization

Here, we define several new theorems for the EDF-adaptive algorithm. First, we propose a concept of complementary tasks.Definition 1.
Givenk periodic tasks τ1,τ2,⋯τk, k>1, we regard k tasks are complementary if ∑i=1kui=1. Then, we have the following lemma.Lemma 2.
Complementary periodic tasks can be scheduled on uniprocessor, and their total utilization is 1.According to the DD scheduling algorithm [18], this lemma can be easily proved.Given a time intervalΔ, CPU utilization UΔ=∑i=1kui, where k is a set of periodic tasks executed in Δ, and ui is the ratio of the execution time of τi task to Δ. Also, define the remanent utilization rate of a processor as βΔ=1−UΔ; then, the remaining time unit is
(4)spareΔ=βΔ×Δ=1−UΔ×Δ.LetT be the minimum common multiple of n tasks’ period. Given ∑i=1nui≤1 if n tasks can be scheduled in 0,T, then n tasks can be scheduled for the entire period of execution, according to [18]. This is because the corresponding scheduling method can be executed repeatedly in the future i∗T,i+1∗T, where i≥1.Lemma 3.
Givenn preemptive periodic tasks allocated to the jth processor, the available time unit of the ith periodic task τi=ei,di in 0,T is spare=T×1−∑k=1nuk, where T is the minimum common multiple of the period of n tasks and τi. Define x as the available average time unit allocated to each activation of τi, and l as the number of τk’ jobs allocated to this processor.We have(1)
A necessary and sufficient condition forτi to be assigned to the jth processor as a fixed task without tardiness in 0,T is x≥ei where l=T/di and x=spare/l(2)
Ifτi is to be assigned to the jth processor as a migrating task and ui,j is the fraction of the τi’ utilization is assigned to Pj, then l=T/di×ui,j/ui and x=spare/l. A sufficient condition for τi to be assigned to the jth processor as a migrating task without tardiness in 0,T is x≥eiProof.
For fixed tasks, firstly, we prove the necessary conditions under two scenarios.
One is for the first scheduled task, i.e.,n=1 and τ1e1,d1, where e1 is the execution time and d1 is the deadline or period. Obviously, this task is assigned to the processor as the fixed task. Given that the current spare time unit spare=T=d1 time units and only τ1 is allocated to this processor, we get
(5)x=spareT/d1=d1≥e1.
The other is whenn=k−1, and the remanent time unit is spare=T×1−∑i=1k−1ui, we need to decide if the kth task τkek,dk will be allocated to this processor as a fixed task. T time unit including τk tasks’ activation times is l=T/dk. Because the time units that must be executed in each activation time are ek and τk are scheduling on this processor with no tardiness, the remanent time unit spare must not be less than l×ek. Then, we get x=spare/l≥ek.
Secondly, we prove sufficient conditions. Whenn=k−1, the remanent time unit is spare=T×1−∑i=1k−1ui. Because T is the minimum common multiple of the period of n tasks and τi, T is dividable to dk. If the kth task τkek,dk is assigned to this processor as a fixed task, the activation times of τk, in 0;T, is l=T/dk and the available average time unit allocated to each activation is x=spare/l. The time units that must be executed in each period are ek. If x≥ek, there are enough time units for τk’s every activation with no tardiness.For migrating tasks, whenn=k−1, the remanent time unit is spare=T×1−∑i=1k−1ui; we need to decide if the kth task τkek,dk will be allocated to this processor as a migrating task. Let uk,j be the fraction of τk’s utilization. We can obtain the proportion of jobs allocated to this processor by uk,j/uk. The total activation time of τk in 0,T is T/dk, but there are at most T/dk×uk,j/uk jobs of τk allocated to this processor in 0,T. Let l be the number of jobs, l=T/dk×uk,j/uk. If x=spare/l≥ek, there are enough time units for τk’s jobs to be scheduled on this processor without any tardiness.According to Lemma3, given a task τi for a processor, we can decide whether it should be regarded as a fixed task or migrating task. If n−1 tasks are assigned as fixed task and for the nth task there always exists x<ei in 0,T, τn is then removed. If the system becomes an underloaded utilization system after the removal, we call τn is a probable slack task.Theorem 4.
A probable slack taskτiei,di can be delayed, and its minimum tardiness is
(6)Tardinessmin=ei×1M−∑i≠juj−1uj.Proof.
If a probable slack taskτi is removed, the system’s remanent utilization is M−∑i≠juj>0. To schedule this system, the task has to be delayed in the whole process, and we assume the minimum period after delay is dnew, which is also the delay deadline for the soft real-time task. The tardiness can be derived as
(7)Tardinessmin=dnew−di=ei×1M−∑i≠juj−di=ei×1M−∑i≠juj−1ui.


### 3.2. EDF-Adaptive Algorithm

Similar to EDF-fm and EDF-os, our EDF-adaptive also has two phases: offline task partitioning phase and task splitting execution phase.


#### 3.2.1. Task Partitioning Algorithm

To partition tasks, we first arrange them in utilization ascending order. FromSH and SL, we find all complementary task sets with their total utilization being K1≤K≤M. Subsequently, we dispatch K sets into the K processors’ scheduling queue. We assume that a center processor distributes new tasks to processors, and each processor sends a request and amends its own scheduling queue.Though the DD scheduling algorithm can be used for the tasks in one processor with its scheduling queue, there exist two issues. One is that the complementary task sets may not be unique. For example, given six tasks with utilization as0.1,0.3,0.4,0.5,0.7,0.9, we can divide them into two optional complementary tasks set: one is {0.1,0.4,0.5}, {0.7,0.3} and the other is {0.1,0.9}, {0.7,0.3}. EDF-adaptive always chooses the sets that include most tasks, unless the system species the priority of tasks. The other issue is to select the parameter ε so that all similar complementary tasks can be obtained. EDF-adaptive selects ε so that the total utilization is the nearest close to K.Algorithm1 presents the pseudocode to find complementary tasks set for K full utilization system. As shown in Algorithm 1, the overall approach is to find and add complementary tasks into Setcomp and then remove them from Q. When there are still tasks in Q or Ures is not 0 or j=i, Algorithm 1 recursively finds the complementary tasks set by adding ui and uj that is depending on the relationship between ui, uj, and Ures; there are several cases as follows:Algorithm 1: Find complementary tasks.
Input:i: the sequence number of the task with minimum utilizationj: the sequence number of the task with maximum utilizationUres: the remanent utilization and initial value is K when the system is K full utilization systemQ: the set of all tasks in the system with their utilization in descending orderOutput: Setcomp: the complementary task set.1: ifQ≠NULL and Ures≠0 and j≠i then2: ifui+uj==Ures then3:Setcomp⟵τi,τj;4:Ures=0;5:Q⟵deleteτi,τj;6: return 1;7: else8: ifui+uj<Ures then9:Setcomp⟵τi,τj10:Q⟵deleteτi,τj;11:Ures=Ures−ui−uj12:Findi+1;j−1,Ures,Q;13: else:14: ifui+uj>Ures then15: ifui==Ures then16:Setcomp⟵τi;17:Ures=0;18:Q⟵deleteτi;19: return 1;20: else21: ifuj==Ures then22:Setcomp⟵τj;23:Ures=0;24:Q⟵deleteτj;25: return 1;26: end if27: end if28: end if29: end if30: end if31:j=j−132: ifj≠i then.33:Findi,j−1,Ures,Q34: return 0;35: end if36: end ifIfui+uj==Ures, τi and τj belong to the complementary set.Ifui+uj>Ures, only one of them can be an element in the complementary set, depending on if ui==Ures or uj==Ures.Ifui+uj<Ures, τi and τj may or may not be the elements in the complementary set.If none of the conditions above is satisfied, the algorithm updates the sequence number (j=j−1) and continues to search.


#### 3.2.2. Task Splitting and Execution Algorithm

To achieve higher system utilization, we split tasks assigned toK processors according to their utilization.First, the tasks are arranged in descending order of utilization in the queue. The tasks with the highest utilization are assigned to thejth processors and then removed from the queue. If j≤K, calculate the remanent utilization of the jth processor Uj. If Uj>0, select the task which has the lowest utilization in the queue and calculate the split value by
(8)fi,j=Tdi×ui,jui,where fi,j is the number of jobs that τi will be scheduled on the jth processor in 0,T, according to Lemma 3. The task τi will be allocated to execute on the jth processor in time 0,T, i.e., the units of execution time units of τi on the jth processor. τi will be divided and assigned to other processors if its remanent execution time unit is not zero. If Uj≤0, it means that the jth processor has completed the assignment; if j>K, it indicates that the tasks of this group set have been allocated over, and it returns the corresponding processor with the allocated tasks. The pseudocode of the splitting approach is presented in Algorithm 2.Algorithm 2: Task splitting.
Input: Setcomp: a complementary utilization tasks set.T: a global time counter.Output: ProcessorSetN;K: the N tasks distribution results for the K processors the complementary task set.1: ifSetcomp≠NULL then2:Setcomp⟵τi,τj3: /∗Sort all the tasks in Setcomp according to its period in descending order;∗/4:i=1;5:j=1;6:Ui=1;7:Ui=ui;8: whilej≤K do:9: ifUi>Uj then.10:Ui=Ui−Uj;11:ui,j=Uj;12:Psetj⟵τi;13:fi,j⟵T/pi×ui,j/ui;14:ProcessorSeti,j⟵fi,j;15:j=j+1;16: else17:Uj=Uj−Ui;18:ui,j=Ui;19:Psetj⟵τi;20:Setcomp⟵deleteτi;21:fi,j⟵T/pi×ui,j/ui;22:ProcessorSeti,j⟵fi,j;23:i=i+124: ifUj==0 then25:j=j+1;26: end if27: end if28: end while29: end ifAs shown in Algorithm2, there are the following two scenarios:IfUi≥Uj, it means Uj cannot satisfy Ui. The τi’s utilization share on processor Pj is ui,j=Uj, and the remaining utilization of τi is Ui=Ui−Uj. The number of jobs that τi will be scheduled on the jth processor in 0,T is fi,j.IfUi<Uj, it means that Uj can satisfy Ui. The share of task τi assigned on processor Pj is ui,j=Uj. We calculate the number of jobs (fi,j) that τi will be scheduled on the jth processor in 0,T and record fi,j in the scheduling queue of processor Pj. Next, we update the remaining utilization of Pj, Uj=Uj−Ui, and remove the task τi from the complementary set before selecting the next task. If Uj=0, it means that the remaining utilization of the jth processor has been exhausted and the next processor must be selected.In the execution phase, all released jobs of the fixed tasks are scheduled online without migration. Different from EDF-os and EDF-fm that the priority of migration tasks is higher than that of fixed tasks at any time, in EDF-adaptive’s execution phase; the priority of migration tasks is only higher than that of fixed tasks with lower utilization. To compare the task splitting and scheduling of EDF-adaptive with EDF-fm and EDF-os, we use a task systemτ=9,10,7,12,3,4,2,3,3,5,1,2 as an example, since Uτ=4 is feasible on four processors. Because all task utilization but one exceed 0.5 and the other utilization is exactly 0.5, all the tasks belong to SH. The comparing results are shown in Figures 1–6.Figure 1
EDF-fm offline assigning tasks in 4 processors.Figure 2
EDF-fm online scheduling results in 22 time units.Figure 3
EDF-os offline assigning tasks in 4 processors.Figure 4
EDF-os online scheduling results in 22 time units.Figure 5
EDF-adaptive offline assigning tasks in 4 processors.Figure 6
EDF-adaptive online scheduling results in 22 time units.Figure1 illustrates the offline assignment phase of EDF-fm functions, where tasks are assigned to the processors as either fixed task or migrating one. We can see that EDF-fm has a simple assignment algorithm which dispatches tasks according to their order of coming. If the currently considered processor Pj has sufficient unallocated utilization, the currently considered task τi is assigned to it as a fixed task and ui,j=Ui; otherwise, τi exhausts the remaining unallocated utilization of Pj and receives from Pj+1 the rest of its allocation required. For example, τ2 is assigned to P1 and P2, and its utilization has been divided into two parts: u2,1=1/10 and u2,2=u2−u2,1=29/60; that means, τ2 is a migrating task.Figure2 is EDF-fm’s online execution phase that extends the earliest-deadline-first (EDF) scheduling to executed and migrating tasks. Specifically, each migrating task executes on two processors, and for each processor, at most two specific migrating tasks may execute upon it. Because the migrating tasks are prior to the fixed tasks for EDF-fm, the jobs of τ1 cannot meet any jobs’ deadline although it shares a 9/10 fraction of the processor P1 of which the remanent utilization is given the migrating task τ2. The jobs of τ1 and τ4 and τ6 miss the deadline, and their total tardiness is 44 time units. The migrating tasks are τ2, τ3, and τ5, and 9 time unit is unused. If the task’s utilization restriction of EDF-fm is violated, migrating tasks may miss deadlines, which invalidates the tardiness analysis.Figure3 is the offline assignment phase of EDF-os. All the tasks’ utilizations are assigned to the processors in decreasing order using a worst-t decreasing scheme rather than an arbitrary ordering. This phase tries to assign as many tasks as possible to be fixed; hence, the number of fixed tasks is as same as that of the processors at least. The remaining tasks are allocated nonzero shares from a succession of processors until the sum of its shares equals its utilization. Because the remaining tasks’ utilization is considered in decreasing order, each processor must contain at least one fixed task with its utilization that is at least that of any migrating task. It is possible that such a task receives a nonzero share on only one processor, in which it is a fixed task; otherwise, it is migrating. This procedure ensures that there are at most two migrating tasks with nonzero shares on any processors. However, a migrating task under EDF-os can have nonzero shares on more than two processors. We can see there are τ1, τ2, τ3, and τ4 four tasks’ utilization in decreasing order as fixed tasks and τ5 has nonzero shares on three processors. P3 contains one fixed task τ3 and two migrating tasks τ5 and τ6.Figure4 is EDF-os’s online execution phase. As in EDF-fm, migrating tasks are statically prioritized over fixed ones on any processor and each job executes on only one processor and fixed tasks are prioritized against each other using EDF. But if a processor has two migrating tasks τi and τi+1 assigned in this order, τi is statically prioritized over τi+1. This means a migrating task executes with the highest priority on any processor that is not its first processor. Note that the lowest-indexed processor to which a migrating task τi is assigned jobs is called τi’ first processor. For example, P2 is τ5’s first processor and P3 is τ5’s second processor, so τ5 has the highest priority on P3 and τ6 has higher priority than τ3.EDF-os has better solutions for decreasing the number of jobs missing deadline, and it distributes the fixed tasks at first according to the processors, as shown in Figures3 and 4. It can be seen that τ2 and τ3 in the EDF-fm have been scheduled as migrating tasks and assign them as the fixed tasks in the EDF-os, whereas the task τ5 is split and assigned into three processors. The splitting will introduce more preemption overhead in the third processor. The jobs of τ1 and τ3 miss the deadline, and the total tardiness is 15 time units.Figure5 is the offline assignment phase of EDF-adaptive. Algorithm 1 divides these 4 (i.e., K=4) full utilization systems into 2 full utilization subsystems that are 9,10,3,5,1,2 and 9,10,3,4,2,3. In each subsystem, the sum of tasks’ utilization is 2. Meanwhile, the processors are divided into two parts P1,P2 and P3,P4 according to the subsystems, respectively. In each subsystems, as many tasks with the maximum period as possible are assigned as fixed tasks. We can see that the tasks with the minimum period such as τ6 and τ4 are the migrating tasks in the two subsystems, respectively.Subsequently, according to Algorithm2, we obtain the number of scheduling jobs for each task on processors. The scheduling results for this instance of EDF-adaptive are shown in Figure 6. We also consider the bounded tardiness restriction, i.e., the job is migrated at its boundary. Unlike EDF-os and EDF-fm, EDF-adaptive does not statically prioritized migrating tasks over fixed tasks. Instead, it always preempts the fixed tasks with the lowest utilization in its subsystems. It can be seen in Figure 6 that only the jobs of τ2 miss the deadline and the total tardiness is 3 time units. The migrating tasks are τ4 and τ6, and only 1 time unit is unused. The context switch overhead is lower than that in EDF-os. With the statistic results depicted in Table 1, we can find that EDF-adaptive is prior to EDF-fm and EDF-os at the total tardiness but the context switch times are between the two. These figures also show us that EDF-os and EDF-adaptive need to increase the migrating times, preemptive times, and context switch times to meet more jobs’ deadlines.Table 1
Statistics for the example in 22 time units.
AlgorithmTardiness (time units)The number of migrating tasksUnused (time units)Context switch (time units)EDF-fm443915EDF-os153129EDF-adaptive32123


## 3.1. Task Model

Assume a sporadic system consists ofM processors and owns N>M tasks τ=τ1,τ2,⋯τN. These sporadic tasks are independent and to be scheduled upon a multiprocessor platform with M≥2 identical processors. In a sporadic task model, a sporadic task is a four-tuple τiri,ei,di,pi where ei, di, and pi are positive integer numbers and ri is a nonnegative integer number and it is characterized by a minimum interarrival time, also referred to as its period pi, a worst-case execution cost eipi, and a relative deadline di and a release time ri. Every task τi may be invoked zero or more times with two consecutive invocations separated by at least pi, time units. Each invocation of τi is referred to as a job of τi. The kth job of τi, where k≥1, is denoted as Ji,k. The release time of the job Ji,k is denoted as ri,k. Each job of τi is executed for at most ei, time units. The absolute deadline (or simply, deadline) of Ji,k, denoted as di,k, is the time at or before which Ji,k should complete execution. Each task is sequential and at any time may be executed on at most one processor.A periodic task system, in which every two consecutive jobs of every taskτi are separated by pi time units, is a special case of a sporadic task system. In this paper, we focus on the periodic task system and assume that di=pi holds for all τi and the first job of each task will be invoked or released at time zero. A task can then be represented using a two-tuple τiei,di. The lth processor is denoted as Pl, where 1≤l≤M. All tasks are synchronous and periodic and have the same initial release date. They are preemptive and independent. The overheads of other shared resources between tasks are not considered.


### 3.1.1. Utilization System and Tasks

To facilitate the description of our proposed EDF-adaptive, we categorize the real-time system aforementioned according to its task utilization.Defineui=ei/di, where ui is the utilization of task τi. Then, we have the utilization for all tasks Uτ=∑τi∈τui.We define the real-time system as follows:(i)
Single full utilization system, ifUτ=1(ii)
All full utilization system, ifUτ=M(iii)
K full utilization system, if Uτ=K, where K is an integer. Under this scenario, the system may be either underloaded if M>K>1 or fully utilized if K=M. For the latter, it may be an all full utilization system K=M≥2 or a single full system K=M=1; overloaded utilization system, if Uτ>MFor the overloaded utilization system, we schedule the largest subsetτsub so that the total utilization of the tasks’ subset is very close to M. That is, M−∑i=1kui where ε∈0,1 is a minimum float number and k is the number of the tasks in the subset τsub.Each task is allocated a nonzero fraction, or share of one processor with the available utilization of 1.0. If there arek tasks being scheduled on the jth processor, the remanent utilization of this processor is
(1)Ujτ=1−∑i=1kui,where the fraction of the τi’s utilization scheduled on this processor pj, denoted as ui,j, is Ujτ. The total remanent utilization of this system is
(2)Uremτ=M−∑j=1MUjτ.We defineτi as a high utilization task if ui≥1/2, and a low utilization task otherwise. Define SH as a high utilization task set consisting of high utilization tasks, and SL as a low utilization task set consisting of low utilization tasks. We represent SH and SL as follows:
(3)SH=τi∣ui≥12,SL=τi∣ui<12.A high utilization system is defined as a system consisting of onlySH set.


### 3.1.2. Theorems for EDF-Adaptive Utilization

Here, we define several new theorems for the EDF-adaptive algorithm. First, we propose a concept of complementary tasks.Definition 1.
Givenk periodic tasks τ1,τ2,⋯τk, k>1, we regard k tasks are complementary if ∑i=1kui=1. Then, we have the following lemma.Lemma 2.
Complementary periodic tasks can be scheduled on uniprocessor, and their total utilization is 1.According to the DD scheduling algorithm [18], this lemma can be easily proved.Given a time intervalΔ, CPU utilization UΔ=∑i=1kui, where k is a set of periodic tasks executed in Δ, and ui is the ratio of the execution time of τi task to Δ. Also, define the remanent utilization rate of a processor as βΔ=1−UΔ; then, the remaining time unit is
(4)spareΔ=βΔ×Δ=1−UΔ×Δ.LetT be the minimum common multiple of n tasks’ period. Given ∑i=1nui≤1 if n tasks can be scheduled in 0,T, then n tasks can be scheduled for the entire period of execution, according to [18]. This is because the corresponding scheduling method can be executed repeatedly in the future i∗T,i+1∗T, where i≥1.Lemma 3.
Givenn preemptive periodic tasks allocated to the jth processor, the available time unit of the ith periodic task τi=ei,di in 0,T is spare=T×1−∑k=1nuk, where T is the minimum common multiple of the period of n tasks and τi. Define x as the available average time unit allocated to each activation of τi, and l as the number of τk’ jobs allocated to this processor.We have(1)
A necessary and sufficient condition forτi to be assigned to the jth processor as a fixed task without tardiness in 0,T is x≥ei where l=T/di and x=spare/l(2)
Ifτi is to be assigned to the jth processor as a migrating task and ui,j is the fraction of the τi’ utilization is assigned to Pj, then l=T/di×ui,j/ui and x=spare/l. A sufficient condition for τi to be assigned to the jth processor as a migrating task without tardiness in 0,T is x≥eiProof.
For fixed tasks, firstly, we prove the necessary conditions under two scenarios.
One is for the first scheduled task, i.e.,n=1 and τ1e1,d1, where e1 is the execution time and d1 is the deadline or period. Obviously, this task is assigned to the processor as the fixed task. Given that the current spare time unit spare=T=d1 time units and only τ1 is allocated to this processor, we get
(5)x=spareT/d1=d1≥e1.
The other is whenn=k−1, and the remanent time unit is spare=T×1−∑i=1k−1ui, we need to decide if the kth task τkek,dk will be allocated to this processor as a fixed task. T time unit including τk tasks’ activation times is l=T/dk. Because the time units that must be executed in each activation time are ek and τk are scheduling on this processor with no tardiness, the remanent time unit spare must not be less than l×ek. Then, we get x=spare/l≥ek.
Secondly, we prove sufficient conditions. Whenn=k−1, the remanent time unit is spare=T×1−∑i=1k−1ui. Because T is the minimum common multiple of the period of n tasks and τi, T is dividable to dk. If the kth task τkek,dk is assigned to this processor as a fixed task, the activation times of τk, in 0;T, is l=T/dk and the available average time unit allocated to each activation is x=spare/l. The time units that must be executed in each period are ek. If x≥ek, there are enough time units for τk’s every activation with no tardiness.For migrating tasks, whenn=k−1, the remanent time unit is spare=T×1−∑i=1k−1ui; we need to decide if the kth task τkek,dk will be allocated to this processor as a migrating task. Let uk,j be the fraction of τk’s utilization. We can obtain the proportion of jobs allocated to this processor by uk,j/uk. The total activation time of τk in 0,T is T/dk, but there are at most T/dk×uk,j/uk jobs of τk allocated to this processor in 0,T. Let l be the number of jobs, l=T/dk×uk,j/uk. If x=spare/l≥ek, there are enough time units for τk’s jobs to be scheduled on this processor without any tardiness.According to Lemma3, given a task τi for a processor, we can decide whether it should be regarded as a fixed task or migrating task. If n−1 tasks are assigned as fixed task and for the nth task there always exists x<ei in 0,T, τn is then removed. If the system becomes an underloaded utilization system after the removal, we call τn is a probable slack task.Theorem 4.
A probable slack taskτiei,di can be delayed, and its minimum tardiness is
(6)Tardinessmin=ei×1M−∑i≠juj−1uj.Proof.
If a probable slack taskτi is removed, the system’s remanent utilization is M−∑i≠juj>0. To schedule this system, the task has to be delayed in the whole process, and we assume the minimum period after delay is dnew, which is also the delay deadline for the soft real-time task. The tardiness can be derived as
(7)Tardinessmin=dnew−di=ei×1M−∑i≠juj−di=ei×1M−∑i≠juj−1ui.


## 3.1.1. Utilization System and Tasks

To facilitate the description of our proposed EDF-adaptive, we categorize the real-time system aforementioned according to its task utilization.Defineui=ei/di, where ui is the utilization of task τi. Then, we have the utilization for all tasks Uτ=∑τi∈τui.We define the real-time system as follows:(i)
Single full utilization system, ifUτ=1(ii)
All full utilization system, ifUτ=M(iii)
K full utilization system, if Uτ=K, where K is an integer. Under this scenario, the system may be either underloaded if M>K>1 or fully utilized if K=M. For the latter, it may be an all full utilization system K=M≥2 or a single full system K=M=1; overloaded utilization system, if Uτ>MFor the overloaded utilization system, we schedule the largest subsetτsub so that the total utilization of the tasks’ subset is very close to M. That is, M−∑i=1kui where ε∈0,1 is a minimum float number and k is the number of the tasks in the subset τsub.Each task is allocated a nonzero fraction, or share of one processor with the available utilization of 1.0. If there arek tasks being scheduled on the jth processor, the remanent utilization of this processor is
(1)Ujτ=1−∑i=1kui,where the fraction of the τi’s utilization scheduled on this processor pj, denoted as ui,j, is Ujτ. The total remanent utilization of this system is
(2)Uremτ=M−∑j=1MUjτ.We defineτi as a high utilization task if ui≥1/2, and a low utilization task otherwise. Define SH as a high utilization task set consisting of high utilization tasks, and SL as a low utilization task set consisting of low utilization tasks. We represent SH and SL as follows:
(3)SH=τi∣ui≥12,SL=τi∣ui<12.A high utilization system is defined as a system consisting of onlySH set.


## 3.1.2. Theorems for EDF-Adaptive Utilization

Here, we define several new theorems for the EDF-adaptive algorithm. First, we propose a concept of complementary tasks.Definition 1.
Givenk periodic tasks τ1,τ2,⋯τk, k>1, we regard k tasks are complementary if ∑i=1kui=1. Then, we have the following lemma.Lemma 2.
Complementary periodic tasks can be scheduled on uniprocessor, and their total utilization is 1.According to the DD scheduling algorithm [18], this lemma can be easily proved.Given a time intervalΔ, CPU utilization UΔ=∑i=1kui, where k is a set of periodic tasks executed in Δ, and ui is the ratio of the execution time of τi task to Δ. Also, define the remanent utilization rate of a processor as βΔ=1−UΔ; then, the remaining time unit is
(4)spareΔ=βΔ×Δ=1−UΔ×Δ.LetT be the minimum common multiple of n tasks’ period. Given ∑i=1nui≤1 if n tasks can be scheduled in 0,T, then n tasks can be scheduled for the entire period of execution, according to [18]. This is because the corresponding scheduling method can be executed repeatedly in the future i∗T,i+1∗T, where i≥1.Lemma 3.
Givenn preemptive periodic tasks allocated to the jth processor, the available time unit of the ith periodic task τi=ei,di in 0,T is spare=T×1−∑k=1nuk, where T is the minimum common multiple of the period of n tasks and τi. Define x as the available average time unit allocated to each activation of τi, and l as the number of τk’ jobs allocated to this processor.We have(1)
A necessary and sufficient condition forτi to be assigned to the jth processor as a fixed task without tardiness in 0,T is x≥ei where l=T/di and x=spare/l(2)
Ifτi is to be assigned to the jth processor as a migrating task and ui,j is the fraction of the τi’ utilization is assigned to Pj, then l=T/di×ui,j/ui and x=spare/l. A sufficient condition for τi to be assigned to the jth processor as a migrating task without tardiness in 0,T is x≥eiProof.
For fixed tasks, firstly, we prove the necessary conditions under two scenarios.
One is for the first scheduled task, i.e.,n=1 and τ1e1,d1, where e1 is the execution time and d1 is the deadline or period. Obviously, this task is assigned to the processor as the fixed task. Given that the current spare time unit spare=T=d1 time units and only τ1 is allocated to this processor, we get
(5)x=spareT/d1=d1≥e1.
The other is whenn=k−1, and the remanent time unit is spare=T×1−∑i=1k−1ui, we need to decide if the kth task τkek,dk will be allocated to this processor as a fixed task. T time unit including τk tasks’ activation times is l=T/dk. Because the time units that must be executed in each activation time are ek and τk are scheduling on this processor with no tardiness, the remanent time unit spare must not be less than l×ek. Then, we get x=spare/l≥ek.
Secondly, we prove sufficient conditions. Whenn=k−1, the remanent time unit is spare=T×1−∑i=1k−1ui. Because T is the minimum common multiple of the period of n tasks and τi, T is dividable to dk. If the kth task τkek,dk is assigned to this processor as a fixed task, the activation times of τk, in 0;T, is l=T/dk and the available average time unit allocated to each activation is x=spare/l. The time units that must be executed in each period are ek. If x≥ek, there are enough time units for τk’s every activation with no tardiness.For migrating tasks, whenn=k−1, the remanent time unit is spare=T×1−∑i=1k−1ui; we need to decide if the kth task τkek,dk will be allocated to this processor as a migrating task. Let uk,j be the fraction of τk’s utilization. We can obtain the proportion of jobs allocated to this processor by uk,j/uk. The total activation time of τk in 0,T is T/dk, but there are at most T/dk×uk,j/uk jobs of τk allocated to this processor in 0,T. Let l be the number of jobs, l=T/dk×uk,j/uk. If x=spare/l≥ek, there are enough time units for τk’s jobs to be scheduled on this processor without any tardiness.According to Lemma3, given a task τi for a processor, we can decide whether it should be regarded as a fixed task or migrating task. If n−1 tasks are assigned as fixed task and for the nth task there always exists x<ei in 0,T, τn is then removed. If the system becomes an underloaded utilization system after the removal, we call τn is a probable slack task.Theorem 4.
A probable slack taskτiei,di can be delayed, and its minimum tardiness is
(6)Tardinessmin=ei×1M−∑i≠juj−1uj.Proof.
If a probable slack taskτi is removed, the system’s remanent utilization is M−∑i≠juj>0. To schedule this system, the task has to be delayed in the whole process, and we assume the minimum period after delay is dnew, which is also the delay deadline for the soft real-time task. The tardiness can be derived as
(7)Tardinessmin=dnew−di=ei×1M−∑i≠juj−di=ei×1M−∑i≠juj−1ui.


## 3.2. EDF-Adaptive Algorithm

Similar to EDF-fm and EDF-os, our EDF-adaptive also has two phases: offline task partitioning phase and task splitting execution phase.


### 3.2.1. Task Partitioning Algorithm

To partition tasks, we first arrange them in utilization ascending order. FromSH and SL, we find all complementary task sets with their total utilization being K1≤K≤M. Subsequently, we dispatch K sets into the K processors’ scheduling queue. We assume that a center processor distributes new tasks to processors, and each processor sends a request and amends its own scheduling queue.Though the DD scheduling algorithm can be used for the tasks in one processor with its scheduling queue, there exist two issues. One is that the complementary task sets may not be unique. For example, given six tasks with utilization as0.1,0.3,0.4,0.5,0.7,0.9, we can divide them into two optional complementary tasks set: one is {0.1,0.4,0.5}, {0.7,0.3} and the other is {0.1,0.9}, {0.7,0.3}. EDF-adaptive always chooses the sets that include most tasks, unless the system species the priority of tasks. The other issue is to select the parameter ε so that all similar complementary tasks can be obtained. EDF-adaptive selects ε so that the total utilization is the nearest close to K.Algorithm1 presents the pseudocode to find complementary tasks set for K full utilization system. As shown in Algorithm 1, the overall approach is to find and add complementary tasks into Setcomp and then remove them from Q. When there are still tasks in Q or Ures is not 0 or j=i, Algorithm 1 recursively finds the complementary tasks set by adding ui and uj that is depending on the relationship between ui, uj, and Ures; there are several cases as follows:Algorithm 1: Find complementary tasks.
Input:i: the sequence number of the task with minimum utilizationj: the sequence number of the task with maximum utilizationUres: the remanent utilization and initial value is K when the system is K full utilization systemQ: the set of all tasks in the system with their utilization in descending orderOutput: Setcomp: the complementary task set.1: ifQ≠NULL and Ures≠0 and j≠i then2: ifui+uj==Ures then3:Setcomp⟵τi,τj;4:Ures=0;5:Q⟵deleteτi,τj;6: return 1;7: else8: ifui+uj<Ures then9:Setcomp⟵τi,τj10:Q⟵deleteτi,τj;11:Ures=Ures−ui−uj12:Findi+1;j−1,Ures,Q;13: else:14: ifui+uj>Ures then15: ifui==Ures then16:Setcomp⟵τi;17:Ures=0;18:Q⟵deleteτi;19: return 1;20: else21: ifuj==Ures then22:Setcomp⟵τj;23:Ures=0;24:Q⟵deleteτj;25: return 1;26: end if27: end if28: end if29: end if30: end if31:j=j−132: ifj≠i then.33:Findi,j−1,Ures,Q34: return 0;35: end if36: end ifIfui+uj==Ures, τi and τj belong to the complementary set.Ifui+uj>Ures, only one of them can be an element in the complementary set, depending on if ui==Ures or uj==Ures.Ifui+uj<Ures, τi and τj may or may not be the elements in the complementary set.If none of the conditions above is satisfied, the algorithm updates the sequence number (j=j−1) and continues to search.


### 3.2.2. Task Splitting and Execution Algorithm

To achieve higher system utilization, we split tasks assigned toK processors according to their utilization.First, the tasks are arranged in descending order of utilization in the queue. The tasks with the highest utilization are assigned to thejth processors and then removed from the queue. If j≤K, calculate the remanent utilization of the jth processor Uj. If Uj>0, select the task which has the lowest utilization in the queue and calculate the split value by
(8)fi,j=Tdi×ui,jui,where fi,j is the number of jobs that τi will be scheduled on the jth processor in 0,T, according to Lemma 3. The task τi will be allocated to execute on the jth processor in time 0,T, i.e., the units of execution time units of τi on the jth processor. τi will be divided and assigned to other processors if its remanent execution time unit is not zero. If Uj≤0, it means that the jth processor has completed the assignment; if j>K, it indicates that the tasks of this group set have been allocated over, and it returns the corresponding processor with the allocated tasks. The pseudocode of the splitting approach is presented in Algorithm 2.Algorithm 2: Task splitting.
Input: Setcomp: a complementary utilization tasks set.T: a global time counter.Output: ProcessorSetN;K: the N tasks distribution results for the K processors the complementary task set.1: ifSetcomp≠NULL then2:Setcomp⟵τi,τj3: /∗Sort all the tasks in Setcomp according to its period in descending order;∗/4:i=1;5:j=1;6:Ui=1;7:Ui=ui;8: whilej≤K do:9: ifUi>Uj then.10:Ui=Ui−Uj;11:ui,j=Uj;12:Psetj⟵τi;13:fi,j⟵T/pi×ui,j/ui;14:ProcessorSeti,j⟵fi,j;15:j=j+1;16: else17:Uj=Uj−Ui;18:ui,j=Ui;19:Psetj⟵τi;20:Setcomp⟵deleteτi;21:fi,j⟵T/pi×ui,j/ui;22:ProcessorSeti,j⟵fi,j;23:i=i+124: ifUj==0 then25:j=j+1;26: end if27: end if28: end while29: end ifAs shown in Algorithm2, there are the following two scenarios:IfUi≥Uj, it means Uj cannot satisfy Ui. The τi’s utilization share on processor Pj is ui,j=Uj, and the remaining utilization of τi is Ui=Ui−Uj. The number of jobs that τi will be scheduled on the jth processor in 0,T is fi,j.IfUi<Uj, it means that Uj can satisfy Ui. The share of task τi assigned on processor Pj is ui,j=Uj. We calculate the number of jobs (fi,j) that τi will be scheduled on the jth processor in 0,T and record fi,j in the scheduling queue of processor Pj. Next, we update the remaining utilization of Pj, Uj=Uj−Ui, and remove the task τi from the complementary set before selecting the next task. If Uj=0, it means that the remaining utilization of the jth processor has been exhausted and the next processor must be selected.In the execution phase, all released jobs of the fixed tasks are scheduled online without migration. Different from EDF-os and EDF-fm that the priority of migration tasks is higher than that of fixed tasks at any time, in EDF-adaptive’s execution phase; the priority of migration tasks is only higher than that of fixed tasks with lower utilization. To compare the task splitting and scheduling of EDF-adaptive with EDF-fm and EDF-os, we use a task systemτ=9,10,7,12,3,4,2,3,3,5,1,2 as an example, since Uτ=4 is feasible on four processors. Because all task utilization but one exceed 0.5 and the other utilization is exactly 0.5, all the tasks belong to SH. The comparing results are shown in Figures 1–6.Figure 1
EDF-fm offline assigning tasks in 4 processors.Figure 2
EDF-fm online scheduling results in 22 time units.Figure 3
EDF-os offline assigning tasks in 4 processors.Figure 4
EDF-os online scheduling results in 22 time units.Figure 5
EDF-adaptive offline assigning tasks in 4 processors.Figure 6
EDF-adaptive online scheduling results in 22 time units.Figure1 illustrates the offline assignment phase of EDF-fm functions, where tasks are assigned to the processors as either fixed task or migrating one. We can see that EDF-fm has a simple assignment algorithm which dispatches tasks according to their order of coming. If the currently considered processor Pj has sufficient unallocated utilization, the currently considered task τi is assigned to it as a fixed task and ui,j=Ui; otherwise, τi exhausts the remaining unallocated utilization of Pj and receives from Pj+1 the rest of its allocation required. For example, τ2 is assigned to P1 and P2, and its utilization has been divided into two parts: u2,1=1/10 and u2,2=u2−u2,1=29/60; that means, τ2 is a migrating task.Figure2 is EDF-fm’s online execution phase that extends the earliest-deadline-first (EDF) scheduling to executed and migrating tasks. Specifically, each migrating task executes on two processors, and for each processor, at most two specific migrating tasks may execute upon it. Because the migrating tasks are prior to the fixed tasks for EDF-fm, the jobs of τ1 cannot meet any jobs’ deadline although it shares a 9/10 fraction of the processor P1 of which the remanent utilization is given the migrating task τ2. The jobs of τ1 and τ4 and τ6 miss the deadline, and their total tardiness is 44 time units. The migrating tasks are τ2, τ3, and τ5, and 9 time unit is unused. If the task’s utilization restriction of EDF-fm is violated, migrating tasks may miss deadlines, which invalidates the tardiness analysis.Figure3 is the offline assignment phase of EDF-os. All the tasks’ utilizations are assigned to the processors in decreasing order using a worst-t decreasing scheme rather than an arbitrary ordering. This phase tries to assign as many tasks as possible to be fixed; hence, the number of fixed tasks is as same as that of the processors at least. The remaining tasks are allocated nonzero shares from a succession of processors until the sum of its shares equals its utilization. Because the remaining tasks’ utilization is considered in decreasing order, each processor must contain at least one fixed task with its utilization that is at least that of any migrating task. It is possible that such a task receives a nonzero share on only one processor, in which it is a fixed task; otherwise, it is migrating. This procedure ensures that there are at most two migrating tasks with nonzero shares on any processors. However, a migrating task under EDF-os can have nonzero shares on more than two processors. We can see there are τ1, τ2, τ3, and τ4 four tasks’ utilization in decreasing order as fixed tasks and τ5 has nonzero shares on three processors. P3 contains one fixed task τ3 and two migrating tasks τ5 and τ6.Figure4 is EDF-os’s online execution phase. As in EDF-fm, migrating tasks are statically prioritized over fixed ones on any processor and each job executes on only one processor and fixed tasks are prioritized against each other using EDF. But if a processor has two migrating tasks τi and τi+1 assigned in this order, τi is statically prioritized over τi+1. This means a migrating task executes with the highest priority on any processor that is not its first processor. Note that the lowest-indexed processor to which a migrating task τi is assigned jobs is called τi’ first processor. For example, P2 is τ5’s first processor and P3 is τ5’s second processor, so τ5 has the highest priority on P3 and τ6 has higher priority than τ3.EDF-os has better solutions for decreasing the number of jobs missing deadline, and it distributes the fixed tasks at first according to the processors, as shown in Figures3 and 4. It can be seen that τ2 and τ3 in the EDF-fm have been scheduled as migrating tasks and assign them as the fixed tasks in the EDF-os, whereas the task τ5 is split and assigned into three processors. The splitting will introduce more preemption overhead in the third processor. The jobs of τ1 and τ3 miss the deadline, and the total tardiness is 15 time units.Figure5 is the offline assignment phase of EDF-adaptive. Algorithm 1 divides these 4 (i.e., K=4) full utilization systems into 2 full utilization subsystems that are 9,10,3,5,1,2 and 9,10,3,4,2,3. In each subsystem, the sum of tasks’ utilization is 2. Meanwhile, the processors are divided into two parts P1,P2 and P3,P4 according to the subsystems, respectively. In each subsystems, as many tasks with the maximum period as possible are assigned as fixed tasks. We can see that the tasks with the minimum period such as τ6 and τ4 are the migrating tasks in the two subsystems, respectively.Subsequently, according to Algorithm2, we obtain the number of scheduling jobs for each task on processors. The scheduling results for this instance of EDF-adaptive are shown in Figure 6. We also consider the bounded tardiness restriction, i.e., the job is migrated at its boundary. Unlike EDF-os and EDF-fm, EDF-adaptive does not statically prioritized migrating tasks over fixed tasks. Instead, it always preempts the fixed tasks with the lowest utilization in its subsystems. It can be seen in Figure 6 that only the jobs of τ2 miss the deadline and the total tardiness is 3 time units. The migrating tasks are τ4 and τ6, and only 1 time unit is unused. The context switch overhead is lower than that in EDF-os. With the statistic results depicted in Table 1, we can find that EDF-adaptive is prior to EDF-fm and EDF-os at the total tardiness but the context switch times are between the two. These figures also show us that EDF-os and EDF-adaptive need to increase the migrating times, preemptive times, and context switch times to meet more jobs’ deadlines.Table 1
Statistics for the example in 22 time units.
AlgorithmTardiness (time units)The number of migrating tasksUnused (time units)Context switch (time units)EDF-fm443915EDF-os153129EDF-adaptive32123


## 3.2.1. Task Partitioning Algorithm

To partition tasks, we first arrange them in utilization ascending order. FromSH and SL, we find all complementary task sets with their total utilization being K1≤K≤M. Subsequently, we dispatch K sets into the K processors’ scheduling queue. We assume that a center processor distributes new tasks to processors, and each processor sends a request and amends its own scheduling queue.Though the DD scheduling algorithm can be used for the tasks in one processor with its scheduling queue, there exist two issues. One is that the complementary task sets may not be unique. For example, given six tasks with utilization as0.1,0.3,0.4,0.5,0.7,0.9, we can divide them into two optional complementary tasks set: one is {0.1,0.4,0.5}, {0.7,0.3} and the other is {0.1,0.9}, {0.7,0.3}. EDF-adaptive always chooses the sets that include most tasks, unless the system species the priority of tasks. The other issue is to select the parameter ε so that all similar complementary tasks can be obtained. EDF-adaptive selects ε so that the total utilization is the nearest close to K.Algorithm1 presents the pseudocode to find complementary tasks set for K full utilization system. As shown in Algorithm 1, the overall approach is to find and add complementary tasks into Setcomp and then remove them from Q. When there are still tasks in Q or Ures is not 0 or j=i, Algorithm 1 recursively finds the complementary tasks set by adding ui and uj that is depending on the relationship between ui, uj, and Ures; there are several cases as follows:Algorithm 1: Find complementary tasks.
Input:i: the sequence number of the task with minimum utilizationj: the sequence number of the task with maximum utilizationUres: the remanent utilization and initial value is K when the system is K full utilization systemQ: the set of all tasks in the system with their utilization in descending orderOutput: Setcomp: the complementary task set.1: ifQ≠NULL and Ures≠0 and j≠i then2: ifui+uj==Ures then3:Setcomp⟵τi,τj;4:Ures=0;5:Q⟵deleteτi,τj;6: return 1;7: else8: ifui+uj<Ures then9:Setcomp⟵τi,τj10:Q⟵deleteτi,τj;11:Ures=Ures−ui−uj12:Findi+1;j−1,Ures,Q;13: else:14: ifui+uj>Ures then15: ifui==Ures then16:Setcomp⟵τi;17:Ures=0;18:Q⟵deleteτi;19: return 1;20: else21: ifuj==Ures then22:Setcomp⟵τj;23:Ures=0;24:Q⟵deleteτj;25: return 1;26: end if27: end if28: end if29: end if30: end if31:j=j−132: ifj≠i then.33:Findi,j−1,Ures,Q34: return 0;35: end if36: end ifIfui+uj==Ures, τi and τj belong to the complementary set.Ifui+uj>Ures, only one of them can be an element in the complementary set, depending on if ui==Ures or uj==Ures.Ifui+uj<Ures, τi and τj may or may not be the elements in the complementary set.If none of the conditions above is satisfied, the algorithm updates the sequence number (j=j−1) and continues to search.


## 3.2.2. Task Splitting and Execution Algorithm

To achieve higher system utilization, we split tasks assigned toK processors according to their utilization.First, the tasks are arranged in descending order of utilization in the queue. The tasks with the highest utilization are assigned to thejth processors and then removed from the queue. If j≤K, calculate the remanent utilization of the jth processor Uj. If Uj>0, select the task which has the lowest utilization in the queue and calculate the split value by
(8)fi,j=Tdi×ui,jui,where fi,j is the number of jobs that τi will be scheduled on the jth processor in 0,T, according to Lemma 3. The task τi will be allocated to execute on the jth processor in time 0,T, i.e., the units of execution time units of τi on the jth processor. τi will be divided and assigned to other processors if its remanent execution time unit is not zero. If Uj≤0, it means that the jth processor has completed the assignment; if j>K, it indicates that the tasks of this group set have been allocated over, and it returns the corresponding processor with the allocated tasks. The pseudocode of the splitting approach is presented in Algorithm 2.Algorithm 2: Task splitting.
Input: Setcomp: a complementary utilization tasks set.T: a global time counter.Output: ProcessorSetN;K: the N tasks distribution results for the K processors the complementary task set.1: ifSetcomp≠NULL then2:Setcomp⟵τi,τj3: /∗Sort all the tasks in Setcomp according to its period in descending order;∗/4:i=1;5:j=1;6:Ui=1;7:Ui=ui;8: whilej≤K do:9: ifUi>Uj then.10:Ui=Ui−Uj;11:ui,j=Uj;12:Psetj⟵τi;13:fi,j⟵T/pi×ui,j/ui;14:ProcessorSeti,j⟵fi,j;15:j=j+1;16: else17:Uj=Uj−Ui;18:ui,j=Ui;19:Psetj⟵τi;20:Setcomp⟵deleteτi;21:fi,j⟵T/pi×ui,j/ui;22:ProcessorSeti,j⟵fi,j;23:i=i+124: ifUj==0 then25:j=j+1;26: end if27: end if28: end while29: end ifAs shown in Algorithm2, there are the following two scenarios:IfUi≥Uj, it means Uj cannot satisfy Ui. The τi’s utilization share on processor Pj is ui,j=Uj, and the remaining utilization of τi is Ui=Ui−Uj. The number of jobs that τi will be scheduled on the jth processor in 0,T is fi,j.IfUi<Uj, it means that Uj can satisfy Ui. The share of task τi assigned on processor Pj is ui,j=Uj. We calculate the number of jobs (fi,j) that τi will be scheduled on the jth processor in 0,T and record fi,j in the scheduling queue of processor Pj. Next, we update the remaining utilization of Pj, Uj=Uj−Ui, and remove the task τi from the complementary set before selecting the next task. If Uj=0, it means that the remaining utilization of the jth processor has been exhausted and the next processor must be selected.In the execution phase, all released jobs of the fixed tasks are scheduled online without migration. Different from EDF-os and EDF-fm that the priority of migration tasks is higher than that of fixed tasks at any time, in EDF-adaptive’s execution phase; the priority of migration tasks is only higher than that of fixed tasks with lower utilization. To compare the task splitting and scheduling of EDF-adaptive with EDF-fm and EDF-os, we use a task systemτ=9,10,7,12,3,4,2,3,3,5,1,2 as an example, since Uτ=4 is feasible on four processors. Because all task utilization but one exceed 0.5 and the other utilization is exactly 0.5, all the tasks belong to SH. The comparing results are shown in Figures 1–6.Figure 1
EDF-fm offline assigning tasks in 4 processors.Figure 2
EDF-fm online scheduling results in 22 time units.Figure 3
EDF-os offline assigning tasks in 4 processors.Figure 4
EDF-os online scheduling results in 22 time units.Figure 5
EDF-adaptive offline assigning tasks in 4 processors.Figure 6
EDF-adaptive online scheduling results in 22 time units.Figure1 illustrates the offline assignment phase of EDF-fm functions, where tasks are assigned to the processors as either fixed task or migrating one. We can see that EDF-fm has a simple assignment algorithm which dispatches tasks according to their order of coming. If the currently considered processor Pj has sufficient unallocated utilization, the currently considered task τi is assigned to it as a fixed task and ui,j=Ui; otherwise, τi exhausts the remaining unallocated utilization of Pj and receives from Pj+1 the rest of its allocation required. For example, τ2 is assigned to P1 and P2, and its utilization has been divided into two parts: u2,1=1/10 and u2,2=u2−u2,1=29/60; that means, τ2 is a migrating task.Figure2 is EDF-fm’s online execution phase that extends the earliest-deadline-first (EDF) scheduling to executed and migrating tasks. Specifically, each migrating task executes on two processors, and for each processor, at most two specific migrating tasks may execute upon it. Because the migrating tasks are prior to the fixed tasks for EDF-fm, the jobs of τ1 cannot meet any jobs’ deadline although it shares a 9/10 fraction of the processor P1 of which the remanent utilization is given the migrating task τ2. The jobs of τ1 and τ4 and τ6 miss the deadline, and their total tardiness is 44 time units. The migrating tasks are τ2, τ3, and τ5, and 9 time unit is unused. If the task’s utilization restriction of EDF-fm is violated, migrating tasks may miss deadlines, which invalidates the tardiness analysis.Figure3 is the offline assignment phase of EDF-os. All the tasks’ utilizations are assigned to the processors in decreasing order using a worst-t decreasing scheme rather than an arbitrary ordering. This phase tries to assign as many tasks as possible to be fixed; hence, the number of fixed tasks is as same as that of the processors at least. The remaining tasks are allocated nonzero shares from a succession of processors until the sum of its shares equals its utilization. Because the remaining tasks’ utilization is considered in decreasing order, each processor must contain at least one fixed task with its utilization that is at least that of any migrating task. It is possible that such a task receives a nonzero share on only one processor, in which it is a fixed task; otherwise, it is migrating. This procedure ensures that there are at most two migrating tasks with nonzero shares on any processors. However, a migrating task under EDF-os can have nonzero shares on more than two processors. We can see there are τ1, τ2, τ3, and τ4 four tasks’ utilization in decreasing order as fixed tasks and τ5 has nonzero shares on three processors. P3 contains one fixed task τ3 and two migrating tasks τ5 and τ6.Figure4 is EDF-os’s online execution phase. As in EDF-fm, migrating tasks are statically prioritized over fixed ones on any processor and each job executes on only one processor and fixed tasks are prioritized against each other using EDF. But if a processor has two migrating tasks τi and τi+1 assigned in this order, τi is statically prioritized over τi+1. This means a migrating task executes with the highest priority on any processor that is not its first processor. Note that the lowest-indexed processor to which a migrating task τi is assigned jobs is called τi’ first processor. For example, P2 is τ5’s first processor and P3 is τ5’s second processor, so τ5 has the highest priority on P3 and τ6 has higher priority than τ3.EDF-os has better solutions for decreasing the number of jobs missing deadline, and it distributes the fixed tasks at first according to the processors, as shown in Figures3 and 4. It can be seen that τ2 and τ3 in the EDF-fm have been scheduled as migrating tasks and assign them as the fixed tasks in the EDF-os, whereas the task τ5 is split and assigned into three processors. The splitting will introduce more preemption overhead in the third processor. The jobs of τ1 and τ3 miss the deadline, and the total tardiness is 15 time units.Figure5 is the offline assignment phase of EDF-adaptive. Algorithm 1 divides these 4 (i.e., K=4) full utilization systems into 2 full utilization subsystems that are 9,10,3,5,1,2 and 9,10,3,4,2,3. In each subsystem, the sum of tasks’ utilization is 2. Meanwhile, the processors are divided into two parts P1,P2 and P3,P4 according to the subsystems, respectively. In each subsystems, as many tasks with the maximum period as possible are assigned as fixed tasks. We can see that the tasks with the minimum period such as τ6 and τ4 are the migrating tasks in the two subsystems, respectively.Subsequently, according to Algorithm2, we obtain the number of scheduling jobs for each task on processors. The scheduling results for this instance of EDF-adaptive are shown in Figure 6. We also consider the bounded tardiness restriction, i.e., the job is migrated at its boundary. Unlike EDF-os and EDF-fm, EDF-adaptive does not statically prioritized migrating tasks over fixed tasks. Instead, it always preempts the fixed tasks with the lowest utilization in its subsystems. It can be seen in Figure 6 that only the jobs of τ2 miss the deadline and the total tardiness is 3 time units. The migrating tasks are τ4 and τ6, and only 1 time unit is unused. The context switch overhead is lower than that in EDF-os. With the statistic results depicted in Table 1, we can find that EDF-adaptive is prior to EDF-fm and EDF-os at the total tardiness but the context switch times are between the two. These figures also show us that EDF-os and EDF-adaptive need to increase the migrating times, preemptive times, and context switch times to meet more jobs’ deadlines.Table 1
Statistics for the example in 22 time units.
AlgorithmTardiness (time units)The number of migrating tasksUnused (time units)Context switch (time units)EDF-fm443915EDF-os153129EDF-adaptive32123


## 4. Evaluation

In this section, we evaluate the performance of EDF-adaptive by generating task sets for the SRT system and compare it with EDF-fm and EDF-os against five criteria as follows:(1)
Average remanent utilization, which is the ratio of the sum of the unused time units of the processors to the total time units(2)
Average slack task minimum tardiness, according to Theorem4(3)
Average context switching overhead, which is the multiplication of the times of context switching jobs and the overhead of per job context switching(4)
Migrating degree, which is the ratio of the number of the migrating tasks to the total number of tasks(5)
Splitting degree, which is the ratio of the number of the tasks split and scheduled on more than three processors to the total number of tasks


### 4.1. Task Set Generation

We used an Intel (R) core (TM) 2 Quad Q8400 multiprocessors workstation with 4 processors shared on 4 MB L2 cache.In the experiment, we randomly generated 100 task sets, and each task set has generated 20 soft real-time periodic tasks with different utilization and period parameters randomly. From each task set, three types of task sets, overloaded, underloaded, and all full utilization, are selected. We run each type of task set 10 times to calculate the average value. These tasks come with implicit deadlines and are either inSH or in SL because the utilization of half of them is less than 0.5, and the other half is greater than or equal to 0.5. The worst-case execution time (WCET) of each task is determined by the product of its period and utilization so that WCET of all tasks will be less than the deadline (which is equal to the period).We set utilization caps in two sections,1,4 and 4,5. This cap is a range when the sum of all task utilization is given. We calculate the system utilization and get the probable slack task according to Lemma 3. Then, we add or delete the probable slack task until an overloaded system, all full utilization system, or underloaded system is obtained. That is to say, when a set of 20 tasks is generated, the probable slack tasks will be added or subtracted so that the sum of the utilization of all tasks is less than 4 (underloaded system), equal to 4 (all full utilization system), or in the range of 4,5 (overloaded system), respectively.


### 4.2. Results and Discussions

To evaluate the performance of EDF-adaptive, EDF-fm, and EDF-os, we ran100 times and obtained the average of each evaluation criterion. The results are shown in Figures 7–11. In each figure, the horizontal axis is the ratio of the number of tasks in SH to the number of tasks in SL, denoted as R. When the ratio increases, the system is moving from lower utilization to higher utilization.Figure 7
Average system remanent utilization.Figure 8
Average slack task minimum tardiness.Figure 9
Average switching jobs overhead.Figure 10
Migrating degree.Figure 11
Splitting degree.Average remanent utilization. It can be seen from Figure7 that for all algorithms, the remanent utilization increases with R, but it nearly stabilizes when R is greater than 1. Overall, EDF-adaptive and EDF-os get smaller remanent utilization than EDF-fm. This is because EDF-fm selects the tasks and executes them in releasing sequence while EDF-os sorts the utilization of the tasks with descending order first before execution, and EDF-adaptive chooses tasks to execute according to their utilization.Average minimum tardiness. Figure8 shows that EDF-adaptive and EDF-os have lower tardiness than EDF-fm because of their task selection, as it has been explained earlier. In fact, EDF-adaptive has the lowest tardiness because it can schedule the selective tasks that meet the full utilization system.Average job switching overhead. Obviously, as shown in Figure9, EDF-adaptive has lower overhead than EDF-os but has higher overhead than EDF-fm. Because EDF-adaptive and EDF-os are able to meet the jobs’ deadlines, they have to increase the preemptive and migrating times which will give rise to context switch overhead. Although EDF-fm gets the lowest switch jobs overhead, many jobs miss their deadlines as shown in Figure 7. While EDF-os needs to meet the jobs’ deadline and has no restrictions on task segmentation, some tasks may be partitioned into more than three processors that will introduce higher overhead than EDF-fm. EDF-adaptive partitions tasks to meet K full utilization rate in the nondescending order integer value. As a result, it can reduce the switching cost of EDF-os. Obviously, EDF-adaptive can achieve almost as the same as EDF-os on system utilization and get the lowest tardiness in these algorithms and reduce the switch jobs overhead.Migrating degree. Figure10 shows that EDF-adaptive has a much smaller migration degree (thus lower migrating overhead) than EDF-fm and EDF-os, because there will be no migration between the different partition of processors when the maximal K full utilization is achieved.Splitting degree. The higher the splitting degree, the more tasks have been scheduled on multiple processors. It can be seen in Figure11 that EDF-adaptive has performed much better than EDF-fm and EDF-os, in terms of preventing tasks from being split into multiple processors. Figure 11 also shows that EDF-os has the highest splitting degree. This is because EDF-os allows tasks to be assigned to more than 3 processors. This increases the partitioning of tasks. Based on the discussion above, we can conclude that EDF-adaptive is able to schedule more tasks in overloaded systems than EDF-fm and EDF-os. Because EDF-adaptive can selectively schedule from the task queue, it keeps the system running at full capacity as much as possible. For example, in an overloaded system, EDF-fm only schedules tasks in releasing sequence and EDF-os schedules tasks in descending order of utilization and then schedules migration tasks first, followed by fixed tasks. EDF-adaptive is to select appropriate tasks to schedule from SH and SL. For example, EDF-os schedules tasks with a utilization of 0.3 in order, while EDF-adaptive can schedule two tasks with a utilization of, say, 0.1 and 0.2. And in terms of job switching, task migration, and splitting, EDF-adaptive complexity analysis. Despite better performance, EDF-adaptive suffers a higher time complexity than EDF-fm and EDF-os.The time complexity of Algorithm1 is On2 because the worst case for searching and selecting process is the total number of tasks n in SH or SL. And it uses a recursive approach for finding complementary tasks, mainly based on the number of SH or SL. Algorithm 2 schedules tasks onto the processors, and the time complexity is Om, where m is the number of processors. Hence, the time complexity of EDF-adaptive is On2+m, while EDF-fm has the time complexity Onm and EDF-os has the time complexity On+nm. In our future work, we will investigate approaches to reduce the time complexity and simplify the process. One idea is to use hash functions to find the complementary tasks from SH and SL.


## 4.1. Task Set Generation

We used an Intel (R) core (TM) 2 Quad Q8400 multiprocessors workstation with 4 processors shared on 4 MB L2 cache.In the experiment, we randomly generated 100 task sets, and each task set has generated 20 soft real-time periodic tasks with different utilization and period parameters randomly. From each task set, three types of task sets, overloaded, underloaded, and all full utilization, are selected. We run each type of task set 10 times to calculate the average value. These tasks come with implicit deadlines and are either inSH or in SL because the utilization of half of them is less than 0.5, and the other half is greater than or equal to 0.5. The worst-case execution time (WCET) of each task is determined by the product of its period and utilization so that WCET of all tasks will be less than the deadline (which is equal to the period).We set utilization caps in two sections,1,4 and 4,5. This cap is a range when the sum of all task utilization is given. We calculate the system utilization and get the probable slack task according to Lemma 3. Then, we add or delete the probable slack task until an overloaded system, all full utilization system, or underloaded system is obtained. That is to say, when a set of 20 tasks is generated, the probable slack tasks will be added or subtracted so that the sum of the utilization of all tasks is less than 4 (underloaded system), equal to 4 (all full utilization system), or in the range of 4,5 (overloaded system), respectively.


## 4.2. Results and Discussions

To evaluate the performance of EDF-adaptive, EDF-fm, and EDF-os, we ran100 times and obtained the average of each evaluation criterion. The results are shown in Figures 7–11. In each figure, the horizontal axis is the ratio of the number of tasks in SH to the number of tasks in SL, denoted as R. When the ratio increases, the system is moving from lower utilization to higher utilization.Figure 7
Average system remanent utilization.Figure 8
Average slack task minimum tardiness.Figure 9
Average switching jobs overhead.Figure 10
Migrating degree.Figure 11
Splitting degree.Average remanent utilization. It can be seen from Figure7 that for all algorithms, the remanent utilization increases with R, but it nearly stabilizes when R is greater than 1. Overall, EDF-adaptive and EDF-os get smaller remanent utilization than EDF-fm. This is because EDF-fm selects the tasks and executes them in releasing sequence while EDF-os sorts the utilization of the tasks with descending order first before execution, and EDF-adaptive chooses tasks to execute according to their utilization.Average minimum tardiness. Figure8 shows that EDF-adaptive and EDF-os have lower tardiness than EDF-fm because of their task selection, as it has been explained earlier. In fact, EDF-adaptive has the lowest tardiness because it can schedule the selective tasks that meet the full utilization system.Average job switching overhead. Obviously, as shown in Figure9, EDF-adaptive has lower overhead than EDF-os but has higher overhead than EDF-fm. Because EDF-adaptive and EDF-os are able to meet the jobs’ deadlines, they have to increase the preemptive and migrating times which will give rise to context switch overhead. Although EDF-fm gets the lowest switch jobs overhead, many jobs miss their deadlines as shown in Figure 7. While EDF-os needs to meet the jobs’ deadline and has no restrictions on task segmentation, some tasks may be partitioned into more than three processors that will introduce higher overhead than EDF-fm. EDF-adaptive partitions tasks to meet K full utilization rate in the nondescending order integer value. As a result, it can reduce the switching cost of EDF-os. Obviously, EDF-adaptive can achieve almost as the same as EDF-os on system utilization and get the lowest tardiness in these algorithms and reduce the switch jobs overhead.Migrating degree. Figure10 shows that EDF-adaptive has a much smaller migration degree (thus lower migrating overhead) than EDF-fm and EDF-os, because there will be no migration between the different partition of processors when the maximal K full utilization is achieved.Splitting degree. The higher the splitting degree, the more tasks have been scheduled on multiple processors. It can be seen in Figure11 that EDF-adaptive has performed much better than EDF-fm and EDF-os, in terms of preventing tasks from being split into multiple processors. Figure 11 also shows that EDF-os has the highest splitting degree. This is because EDF-os allows tasks to be assigned to more than 3 processors. This increases the partitioning of tasks. Based on the discussion above, we can conclude that EDF-adaptive is able to schedule more tasks in overloaded systems than EDF-fm and EDF-os. Because EDF-adaptive can selectively schedule from the task queue, it keeps the system running at full capacity as much as possible. For example, in an overloaded system, EDF-fm only schedules tasks in releasing sequence and EDF-os schedules tasks in descending order of utilization and then schedules migration tasks first, followed by fixed tasks. EDF-adaptive is to select appropriate tasks to schedule from SH and SL. For example, EDF-os schedules tasks with a utilization of 0.3 in order, while EDF-adaptive can schedule two tasks with a utilization of, say, 0.1 and 0.2. And in terms of job switching, task migration, and splitting, EDF-adaptive complexity analysis. Despite better performance, EDF-adaptive suffers a higher time complexity than EDF-fm and EDF-os.The time complexity of Algorithm1 is On2 because the worst case for searching and selecting process is the total number of tasks n in SH or SL. And it uses a recursive approach for finding complementary tasks, mainly based on the number of SH or SL. Algorithm 2 schedules tasks onto the processors, and the time complexity is Om, where m is the number of processors. Hence, the time complexity of EDF-adaptive is On2+m, while EDF-fm has the time complexity Onm and EDF-os has the time complexity On+nm. In our future work, we will investigate approaches to reduce the time complexity and simplify the process. One idea is to use hash functions to find the complementary tasks from SH and SL.


## 5. Conclusions

In this paper, we have proposed the EDF-adaptive algorithm for the soft real-time multiprocessor systems, which can be divided into three types of system: underloaded utilization system, full utilization system, and overloaded utilization system. The algorithm can allocate task sets onto the processors to achieve better performance than EDF-os and EDF-fm in terms of the degree of task’s splitting and migrating. However, partition problems are generally Np hard and EDF-adaptive is not optimal because of its time complexity. In the future, we will try to apply EDF-adaptive for the heterogeneous systems and mixed-criticality systems, while investigating new approaches to reduce the time complexity.



---

*Source: 6377024-2021-12-13.xml*