# Performance Evaluation of New Joint EDF-RM Scheduling Algorithm for Real Time Distributed System

Authors: Rashmi Sharma; Nitin
Journal: Journal of Engineering
 (2014)

---

## Abstract

In Real Time System, the achievement of deadline is the main target of every scheduling algorithm. Earliest Deadline First (EDF), Rate Monotonic (RM), and least Laxity First are some renowned algorithms that work well in their own context. As we know, there is a very common problem Domino's effect in EDF that is generated due to overloading condition (EDF is not working well in overloading situation). Similarly, performance of RM is degraded in underloading condition. We can say that both algorithms are complements of each other. Deadline missing in both events happens because of their utilization bounding strategy. Therefore, in this paper we are proposing a new scheduling algorithm that carries through the drawback of both existing algorithms. Joint EDF-RM scheduling algorithm is implemented in global scheduler that permits task migration mechanism in between processors in the system. In order to check the improved behavior of proposed algorithm we perform simulation. Results are achieved and evaluated in terms of Success Ratio (SR), Average CPU Utilization (ECU), Failure Ratio (FR), and Maximum Tardiness parameters. In the end, the results are compared with the existing (EDF, RM, and D_R_EDF) algorithms. It has been shown that the proposed algorithm performs better during overloading condition as well in underloading condition.


---

## Body

## 1. Introduction and Motivation

Real Time Distributed System is a distributed system with real time properties. We can say that RTDS is a combination of RTS and distributed system (Figure1). Properties of real time tasks are applied on the distributed system or concept of a distributed system is implemented on RTS. The following is the first appearance of two main components of RTDS.Figure 1
Real time distributed system.


### 1.1. Real Time System (RTS)

RTS is a system in which execution of tasks has some time restrictions (deadline) [1–3]. Based on the execution of real time task RTS falls into the following categories.(i)
Hard RTS. Task execution by assigning deadline is restrictive. Missing deadline will produce incurable results for the entire system [4].
(ii)
Soft RTS. Although missing deadline is not enviable in RTS, but in soft RTS tasks could miss some deadline that will not affect the working of system [5].
(iii)
Firm RTS. If tasks complete their execution before the deadline, they gain more rewards [4, 6]. It is a special type of soft RTS.EDF, RM, and Least Laxity First are some basic scheduling algorithms that execute real time tasks on the basis of their deadline, interarrival period, tardiness, and so forth. Every scheduling algorithm is having some drawbacks, for example, EDF is not functioning well in overloading condition and RM in underloading condition [7, 8].


### 1.2. Distributed System (DS)

Distributed system is an arrangement of several processors/nodes followed by some interconnection topologies. The distribution of load to various processors increases the performance of the entire system. In DS, on the basis of nodes utilization load is balanced in between processors [9–11]. Task migration and duplication are two methodologies that help in balancing the processor load.(i)
Load Migration. In order to balance the load of DS task migration methodology relocates the victim task from one processor (source) to another processor (destination). This technique can be applied to dependent (DAG) as well as independent tasks [12, 13].
(ii)
Task Duplication. Task duplication method is given on the basis of computation to communication ratio (CCR) in between processors. This technique is mostly applicable on dependent tasks (DAG) in order to balance the load as well as minimize the execution cost of complete DAG [14, 15].Moreover, Tasks in a distributed system are assigned to processors by using the following schedulers (Figure2).(i)
Partitioned Scheduler. Tasks are mapped to processors deterministically for execution. Scheduler statically assigns tasks to processors and migration of task instance is prohibited here [16, 17].
(ii)
Global Scheduler. All tasks are kept in a global queue from where tasks to other processors will be assigned for the death penalty. This scheduler dynamically assigns tasks to nodes and allows task migration in between processors [17, 18]. Global scheduler is appealing in such systems where average as well as the worst case response time (WCRT) is important. In queuing theory, single queue scheduling generates healthier average response time as compared to queue per processing scheduler [17, 19]. Hence, in RTDS this scheduler is superior to partitioned scheduler.Distributed system scheduling.
(a)
(b)In this paper we have explained a new joint EDF-RM scheduling algorithm which behaves optimally in both circumstances (underloading as well as overloading). Here, the utilization bound of RM is used to boundary limit of the global queue instead of processorsρ
UB and tasks will be assigned to randomly selected processors. Moreover, for the execution of tasks the EDF scheduling is used on every processor. Our proposed algorithm is divided into the following two modules:(a)
real time job assignment in distributed system (using global scheduler);
(b)
real time task execution on allotted processors of distributed system (including task migration).Reason behind using RM utilization bound is to safeguard our system from overloading condition. Additionally, in order to deal dynamically with tasks the EDF scheduling algorithm is implemented. Load balancing in RTDS is availed by using the global scheduler because task migration is permissible in this scheduler.The remainder of the paper is organized as follows. Existing real time scheduling algorithms have been discussed in Section2. Section 3 explains the proposed joint EDF-RM scheduling algorithm. In Section 4, performances of EDF, RM, D_O_EDF, and D_R_EDF [8] along with proposed algorithm have been analyzed with simulation results. Finally, the conclusion is presented in Section 5.Before moving towards the next section, let us have a glance on the symbols that are utilized in the entire composition. Table1 demonstrates these symbols and their denotation.Table 1
Symbols and definitions.
Symbols
Definition
T
Task-set
τ
arrival
Task arrival time
τ
period
Interarrival period of task
τ
dline
Task deadline
τ
utilization
Per task utilization
τ
priority
Task priority
τ
p
,
a
Taska of p processor
ρ
utilization
Per processor utilization
ρ
UB
Processor upper bound
E
ρ
utilization
Efficient processor utilization
SR
Success Ratio
FR
Failure Ratio
MR
Migration ratio
A
_
preemption
Average number of preemptions
B
Q
Boundary limit of global task queue
TST
Total time of scheduling
tard
τ
i
Tardiness of given task


## 1.1. Real Time System (RTS)

RTS is a system in which execution of tasks has some time restrictions (deadline) [1–3]. Based on the execution of real time task RTS falls into the following categories.(i)
Hard RTS. Task execution by assigning deadline is restrictive. Missing deadline will produce incurable results for the entire system [4].
(ii)
Soft RTS. Although missing deadline is not enviable in RTS, but in soft RTS tasks could miss some deadline that will not affect the working of system [5].
(iii)
Firm RTS. If tasks complete their execution before the deadline, they gain more rewards [4, 6]. It is a special type of soft RTS.EDF, RM, and Least Laxity First are some basic scheduling algorithms that execute real time tasks on the basis of their deadline, interarrival period, tardiness, and so forth. Every scheduling algorithm is having some drawbacks, for example, EDF is not functioning well in overloading condition and RM in underloading condition [7, 8].


## 1.2. Distributed System (DS)

Distributed system is an arrangement of several processors/nodes followed by some interconnection topologies. The distribution of load to various processors increases the performance of the entire system. In DS, on the basis of nodes utilization load is balanced in between processors [9–11]. Task migration and duplication are two methodologies that help in balancing the processor load.(i)
Load Migration. In order to balance the load of DS task migration methodology relocates the victim task from one processor (source) to another processor (destination). This technique can be applied to dependent (DAG) as well as independent tasks [12, 13].
(ii)
Task Duplication. Task duplication method is given on the basis of computation to communication ratio (CCR) in between processors. This technique is mostly applicable on dependent tasks (DAG) in order to balance the load as well as minimize the execution cost of complete DAG [14, 15].Moreover, Tasks in a distributed system are assigned to processors by using the following schedulers (Figure2).(i)
Partitioned Scheduler. Tasks are mapped to processors deterministically for execution. Scheduler statically assigns tasks to processors and migration of task instance is prohibited here [16, 17].
(ii)
Global Scheduler. All tasks are kept in a global queue from where tasks to other processors will be assigned for the death penalty. This scheduler dynamically assigns tasks to nodes and allows task migration in between processors [17, 18]. Global scheduler is appealing in such systems where average as well as the worst case response time (WCRT) is important. In queuing theory, single queue scheduling generates healthier average response time as compared to queue per processing scheduler [17, 19]. Hence, in RTDS this scheduler is superior to partitioned scheduler.Distributed system scheduling.
(a)
(b)In this paper we have explained a new joint EDF-RM scheduling algorithm which behaves optimally in both circumstances (underloading as well as overloading). Here, the utilization bound of RM is used to boundary limit of the global queue instead of processorsρ
UB and tasks will be assigned to randomly selected processors. Moreover, for the execution of tasks the EDF scheduling is used on every processor. Our proposed algorithm is divided into the following two modules:(a)
real time job assignment in distributed system (using global scheduler);
(b)
real time task execution on allotted processors of distributed system (including task migration).Reason behind using RM utilization bound is to safeguard our system from overloading condition. Additionally, in order to deal dynamically with tasks the EDF scheduling algorithm is implemented. Load balancing in RTDS is availed by using the global scheduler because task migration is permissible in this scheduler.The remainder of the paper is organized as follows. Existing real time scheduling algorithms have been discussed in Section2. Section 3 explains the proposed joint EDF-RM scheduling algorithm. In Section 4, performances of EDF, RM, D_O_EDF, and D_R_EDF [8] along with proposed algorithm have been analyzed with simulation results. Finally, the conclusion is presented in Section 5.Before moving towards the next section, let us have a glance on the symbols that are utilized in the entire composition. Table1 demonstrates these symbols and their denotation.Table 1
Symbols and definitions.
Symbols
Definition
T
Task-set
τ
arrival
Task arrival time
τ
period
Interarrival period of task
τ
dline
Task deadline
τ
utilization
Per task utilization
τ
priority
Task priority
τ
p
,
a
Taska of p processor
ρ
utilization
Per processor utilization
ρ
UB
Processor upper bound
E
ρ
utilization
Efficient processor utilization
SR
Success Ratio
FR
Failure Ratio
MR
Migration ratio
A
_
preemption
Average number of preemptions
B
Q
Boundary limit of global task queue
TST
Total time of scheduling
tard
τ
i
Tardiness of given task


## 2. Preliminaries and Background

Before giving the elucidation of our proposed work we would like to enlighten scheduling algorithms associated with our work. This paper uses RM and EDF scheduling algorithms together and tries to resolve the downside of EDF (Domino’s effect) and RM as well. As we know that in distributed system load balancing is an important issue. Hence, proposed algorithm also amplifies the working capability in overloading or underloading situations. These above stated two situations (loading conditions) are checked by recalculations of per task/processor utilization.


### 2.1. Real Time Schedulers

Tasks having real time properties and scheduled on RTS are real time tasks. Scheduling is done by two types of scheduler modules.(i)
Dynamic Scheduler.Dynamic scheduler assigns priorities to tasks at run time. This scheduler reevaluates the information like priorities, resource availability after the arrival of current task. Due to the dynamism of tasks priority, already running tasks have to be preempted by the arrival of new task [20].
(ii)
Static Scheduler. Under this scheduler, priorities of tasks are predefined or we can say static. It cannot be altered by the arrival of new tasks. Priority of τ
m
>
τ
n, where m
<
n. Generally, this scheduler works on dependent tasks because communication cost in between tasks is reduced [20].Let us consider thatT is a set of n real time tasks T
=
{
τ
1
,
τ
2
,
τ
3
,
τ
4
,
τ
5
,
…
,
τ
n
} arriving on processor ρ. Hence,
(1)
τ
utilization
=
τ
wcet
τ
period
,
ρ
utilization
=
∑
i
=
1
n
τ
i
utilization
.RTS works with dynamic as well as static tasks. The EDF scheduling algorithm works well with dynamic and RM schedule static tasks efficiently. We are dealing with RTDS in this paper; therefore we consider the case of overloading in each case.


### 2.2. Earliest Deadline First Scheduling Algorithm

EDF is a dynamic scheduler that follows the principle: the nearer the deadline the higher the priority of task [21, 22]. It assigns priorities to tasks dynamically. Consider
(2)
τ
priority
∝
1
τ
dline
.Before assigning the priorities to the task, scheduler first checks the acceptance test by inspecting the utilization value of task as well as processor. Here task-setT is schedulable (3)
if
ρ
utilization
≤
1
.Let us consider the following examples that explain the behavior of EDF in overloading case in both single and multiple processors (distributed computing).


#### 2.2.1. Example of EDF in Uniprocessor

As we have mentioned in  Algorithm1 and Table 2 the arrival of new tasks preempts already running tasks. In Figure 3 the deadline of task τ
3 is shorter than the task τ
2 and therefore newly arrived task τ
3 preempts τ
2 task because τ
2 task has missed the deadline.Table 2
Arrival time, wcet, period, and deadline of tasksτ
1,   τ
2, and τ
3.
Tasks
Estimate arrival time
Computation time (wcet)
Period
Deadline
τ
utilization
=
τ
wcet
τ
period
τ
1
0
1
3
3
0.33
τ
2
1
2
5
5
0.4
τ
3
3
1.8
4
4
0.45Algorithm 1
EDF scheduling algorithm in uniprocessor
BEGIN
(1)If
τ
utilization
≤
1
(2)If
ρ
utilization
≤
1
(3)The task is schedulable and
(4)assign τ
priority of task on given   processor
(5)Else task is non-schedulable
END
EDF scheduling algorithm in distributed system
BEGIN
(1)If
τ
utilization
≤
1
(2)If
ρ
utilization
≤
1
(3)thentask is schedulable and assign τ
priority of task
on given processor
(4)Elsemigrate the task
(5)Else task is non-schedulable
ENDAlgorithm 2
RM scheduling algorithm in uniprocessor
BEGIN
(1)If
τ
utilization
≤
1
(2)If  ρ
UB
≤
n
(
2
1
/
n
-
1
)
(3)    task is schedulable and
assignτ
priority of task on given processor
(4)Else task is non-schedulable
END
RM scheduling algorithm in Distributed system
BEGIN
(1)If
τ
utilization
≤
1
(2)If  ρ
UB
≤
n
(
2
1
/
n
-
1
)
(3)thentask is schedulable and
assignτ
priority of task on given processor
(4)elsemigrate the task
(5)Else task is non-schedulable
ENDFigure 3
EDF scheduling on single processor.


#### 2.2.2. Example of EDF in Distributed System

In case of distributed system, overloaded processor can migrate the victim task to other processors (destination processor) [23].According to Table3 and Figure 4,  τ
utilization is 0.45 which qualifies the acceptance test of schedulability but due to task utilization ρ
utilization becomes 1.15 which is greater than 1. Due to the arrival of this third task ρ
1 becomes overloaded and future tasks will also miss their deadline. Therefore, by applying the migration terminology scheduler checks per processor utilization and migrate victim task to the processor having a time slot for its execution (ρ
utilization
<
1). In the above example ρ
2 has available time slot and its utilization is  also less than 1. In distributed system there is some migration cost α, that is, time taken by task to migrate from one processor (source) to another (destination).Table 3
Arrival time, wcet, period, deadline, and node for assignment of tasksτ
1,   τ
2,   τ
3,   τ
4,   τ
5, and τ
6.
Tasks
Arrival time
Computation time (wcet)
Period
Deadline
τ
utilization
=
τ
wcet
τ
period
Processor
τ
1
0
1
3
3
0.33
ρ
1
τ
2
1
2
5
5
0.4
ρ
1
τ
3
3
1.8
4
4
0.45
ρ
1
τ
4
5
3
6
6
0.5
ρ
2
τ
5
1
0.5
2
2
0.25
ρ
3
τ
6
2
2
4
4
0.5
ρ
3Figure 4
EDF scheduling algorithm in RTDS.


### 2.3. Rate Monotonic Scheduling Algorithm

RM scheduling algorithm comes under static scheduler (static priority) and follows the principle: the shorter the interarrival period the higher the priority of task [23, 24]:
(4)
τ
priority
∝
1
τ
period
.Before assigning the priorities to the task, scheduler first checks the acceptance test by inspecting the utilization value of task as well as processor. For this algorithmT task-set is schedulable on a given processor [25]
(5)
iff
ρ
UB
≤
n
(
2
1
/
n
-
1
)
,
where n is total number of tasks


#### 2.3.1. Example of RM in Uniprocessor

Now next is the implementation of RM scheduling algorithm on the data of Table2. In overloading condition neither EDF nor RM performs well [7].The upper bound of RM represents schedulability bound of the number of tasks, and asn increases, it decreases with n (number of jobs). While we compute ρ
UB for any number of tasks (as the number of processors increases towards infinity), the value of ρ
UB remains 0.6931472035974151. This means that
(6)
Lim
n
→
∞
⁡
n
(
2
n
-
1
)
=
ln
⁡
⁡
2
≈
0.693
,
τ
1
utilization
=
τ
wcet
τ
period
=
1
3
=
0.33
,
τ
2
utilization
=
0.4
,
τ
3
utilization
=
0.45
,
ρ
utilization
=
∑
i
=
1
2
τ
i
utilization
=
0.33
+
0.4
=
0.73
,
0
.
693
≤
ρ
utilization
≤
1 but after the arrival of 3rd task ρ
utilization becomes 1.15 which is greater than 1. Acceptance test of RM shows that any task-set is able to schedule through if ρ
utilization
≤
0.693, but not all tasks can be scheduled if 0.693
<
ρ
UB
≤
1 [7]. Therefore, we can say that all tasks may or may not be scheduled by RM.In addition, in case of RM, tasks having the least priority miss the deadline due to preemption of higher priority tasks in overloading case, since RM assigns priorities statically (priority of task will not change throughout the execution process) on the basis ofτ
period. In Figure 5 tasks priority is in order τ
1
>
τ
2
>
τ
3 and also according to Table 4 the execution of third task τ
3 is doubtful. Hence, each new arrival of τ
1 after every periodic cycle preempts task τ
2 or τ
3. Similarly task τ
2 preempts τ
3. Also the arrival of 3rd task exceeds ρ
utilization
>
1 and its priority is also third. As a result, τ
3 has missed its deadline. Therefore, we can say that tasks containing the east priority fail to meet the deadline in overloading situation.Table 4
Shows some values ofρ
UB on different number of tasks n.
Number of tasks(
n)
Tasks
τ
utilization
=
τ
wcet
τ
period
ρ
utilization
=
∑
n
=
1
3
τ
n
utilization
ρ
UB =
n
×
(
2
1
/
n
-
1
)
Comparison  ofρ
utilization with ρ
UB
Conclusion
1
τ
1
0.33
0.33
1.0
0.33
≤
1.0
τ
1 is schedulable
2
τ
2
0.4
0.43
0.8284
0.43
≤
0.82
τ
2 is schedulable
3
τ
3
0.45
0.88
0.7797
0.88
≥
0.77
τ
3 can be schedulableFigure 5
RM scheduling on single processor.


#### 2.3.2. Example of RM in Real Time Distributed System

As we have computed that arrival of 3rd task exceeds the range ofρ
utilization, therefore in ρ
1 task τ
3 is a victim task that initiates overloading situation in its source processor. Initially ρ
2 processor is idle and ρ
3
utilization is 0.75. Therefore, on the basis of utilization criteria ρ
2 becomes a destination processor for giving victim task and it will be executed on ρ
2 processor. After the arrival of migrated task τ
1,3 in ρ
2, its utilization becomes 0.45 and its priority is 1, but after the arrival of τ
4 task ρ
2
utilization becomes 0.95 which is again greater than 0.693. In our given example τ
period
=
τ
dline; therefore RM behaves like EDF but if τ
period
≠
τ
dline, then RM behaves different than EDF.


### 2.4. D_O_EDF and D_R_EDF Scheduling Algorithm

The main motive behind the derivation of these two scheduling algorithms is Domino’s effect problem of EDF that is created only in overloading condition. We keep in our mind that we should not let the processor shoot in such a way that causes Domino’s effect.The D_O_EDF scheduling algorithm assigns static priorities 0 and 1 to jobs (Figure6). Such static priorities will be used in overloading condition. In overloading condition, this scheduling algorithm discards those tasks that are expected to miss the deadline and their static priority is 0. On the other side, tasks with firm timing constraint and are expected to miss the deadline with static priority 1, are allowed to execute [8].Figure 6
Real time tasks frame format according to D_O_EDF scheduling algorithm.The D_R_EDF scheduling algorithm is an amalgamation of both dynamic and static scheduling algorithms, that is, EDF and RM (Figure7). As we know, EDF is working well in underloaded situation, but its performance reduces exponentially in overloading condition. Similarly, RM behaves normally in underloaded condition but performs well in overloaded situation. Hence, according to given algorithm initially processor uses EDF for task execution, but when tasks start missing deadline due to overloading condition, the scheduler switches towards RM algorithm. As tasks continuously meet the deadline, then it means that the system is in underloaded condition now and then scheduler again switches towards EDF algorithm [8].Figure 7
D_R_EDF scheduling algorithm flowchart.


## 2.1. Real Time Schedulers

Tasks having real time properties and scheduled on RTS are real time tasks. Scheduling is done by two types of scheduler modules.(i)
Dynamic Scheduler.Dynamic scheduler assigns priorities to tasks at run time. This scheduler reevaluates the information like priorities, resource availability after the arrival of current task. Due to the dynamism of tasks priority, already running tasks have to be preempted by the arrival of new task [20].
(ii)
Static Scheduler. Under this scheduler, priorities of tasks are predefined or we can say static. It cannot be altered by the arrival of new tasks. Priority of τ
m
>
τ
n, where m
<
n. Generally, this scheduler works on dependent tasks because communication cost in between tasks is reduced [20].Let us consider thatT is a set of n real time tasks T
=
{
τ
1
,
τ
2
,
τ
3
,
τ
4
,
τ
5
,
…
,
τ
n
} arriving on processor ρ. Hence,
(1)
τ
utilization
=
τ
wcet
τ
period
,
ρ
utilization
=
∑
i
=
1
n
τ
i
utilization
.RTS works with dynamic as well as static tasks. The EDF scheduling algorithm works well with dynamic and RM schedule static tasks efficiently. We are dealing with RTDS in this paper; therefore we consider the case of overloading in each case.


## 2.2. Earliest Deadline First Scheduling Algorithm

EDF is a dynamic scheduler that follows the principle: the nearer the deadline the higher the priority of task [21, 22]. It assigns priorities to tasks dynamically. Consider
(2)
τ
priority
∝
1
τ
dline
.Before assigning the priorities to the task, scheduler first checks the acceptance test by inspecting the utilization value of task as well as processor. Here task-setT is schedulable (3)
if
ρ
utilization
≤
1
.Let us consider the following examples that explain the behavior of EDF in overloading case in both single and multiple processors (distributed computing).


### 2.2.1. Example of EDF in Uniprocessor

As we have mentioned in  Algorithm1 and Table 2 the arrival of new tasks preempts already running tasks. In Figure 3 the deadline of task τ
3 is shorter than the task τ
2 and therefore newly arrived task τ
3 preempts τ
2 task because τ
2 task has missed the deadline.Table 2
Arrival time, wcet, period, and deadline of tasksτ
1,   τ
2, and τ
3.
Tasks
Estimate arrival time
Computation time (wcet)
Period
Deadline
τ
utilization
=
τ
wcet
τ
period
τ
1
0
1
3
3
0.33
τ
2
1
2
5
5
0.4
τ
3
3
1.8
4
4
0.45Algorithm 1
EDF scheduling algorithm in uniprocessor
BEGIN
(1)If
τ
utilization
≤
1
(2)If
ρ
utilization
≤
1
(3)The task is schedulable and
(4)assign τ
priority of task on given   processor
(5)Else task is non-schedulable
END
EDF scheduling algorithm in distributed system
BEGIN
(1)If
τ
utilization
≤
1
(2)If
ρ
utilization
≤
1
(3)thentask is schedulable and assign τ
priority of task
on given processor
(4)Elsemigrate the task
(5)Else task is non-schedulable
ENDAlgorithm 2
RM scheduling algorithm in uniprocessor
BEGIN
(1)If
τ
utilization
≤
1
(2)If  ρ
UB
≤
n
(
2
1
/
n
-
1
)
(3)    task is schedulable and
assignτ
priority of task on given processor
(4)Else task is non-schedulable
END
RM scheduling algorithm in Distributed system
BEGIN
(1)If
τ
utilization
≤
1
(2)If  ρ
UB
≤
n
(
2
1
/
n
-
1
)
(3)thentask is schedulable and
assignτ
priority of task on given processor
(4)elsemigrate the task
(5)Else task is non-schedulable
ENDFigure 3
EDF scheduling on single processor.


### 2.2.2. Example of EDF in Distributed System

In case of distributed system, overloaded processor can migrate the victim task to other processors (destination processor) [23].According to Table3 and Figure 4,  τ
utilization is 0.45 which qualifies the acceptance test of schedulability but due to task utilization ρ
utilization becomes 1.15 which is greater than 1. Due to the arrival of this third task ρ
1 becomes overloaded and future tasks will also miss their deadline. Therefore, by applying the migration terminology scheduler checks per processor utilization and migrate victim task to the processor having a time slot for its execution (ρ
utilization
<
1). In the above example ρ
2 has available time slot and its utilization is  also less than 1. In distributed system there is some migration cost α, that is, time taken by task to migrate from one processor (source) to another (destination).Table 3
Arrival time, wcet, period, deadline, and node for assignment of tasksτ
1,   τ
2,   τ
3,   τ
4,   τ
5, and τ
6.
Tasks
Arrival time
Computation time (wcet)
Period
Deadline
τ
utilization
=
τ
wcet
τ
period
Processor
τ
1
0
1
3
3
0.33
ρ
1
τ
2
1
2
5
5
0.4
ρ
1
τ
3
3
1.8
4
4
0.45
ρ
1
τ
4
5
3
6
6
0.5
ρ
2
τ
5
1
0.5
2
2
0.25
ρ
3
τ
6
2
2
4
4
0.5
ρ
3Figure 4
EDF scheduling algorithm in RTDS.


## 2.2.1. Example of EDF in Uniprocessor

As we have mentioned in  Algorithm1 and Table 2 the arrival of new tasks preempts already running tasks. In Figure 3 the deadline of task τ
3 is shorter than the task τ
2 and therefore newly arrived task τ
3 preempts τ
2 task because τ
2 task has missed the deadline.Table 2
Arrival time, wcet, period, and deadline of tasksτ
1,   τ
2, and τ
3.
Tasks
Estimate arrival time
Computation time (wcet)
Period
Deadline
τ
utilization
=
τ
wcet
τ
period
τ
1
0
1
3
3
0.33
τ
2
1
2
5
5
0.4
τ
3
3
1.8
4
4
0.45Algorithm 1
EDF scheduling algorithm in uniprocessor
BEGIN
(1)If
τ
utilization
≤
1
(2)If
ρ
utilization
≤
1
(3)The task is schedulable and
(4)assign τ
priority of task on given   processor
(5)Else task is non-schedulable
END
EDF scheduling algorithm in distributed system
BEGIN
(1)If
τ
utilization
≤
1
(2)If
ρ
utilization
≤
1
(3)thentask is schedulable and assign τ
priority of task
on given processor
(4)Elsemigrate the task
(5)Else task is non-schedulable
ENDAlgorithm 2
RM scheduling algorithm in uniprocessor
BEGIN
(1)If
τ
utilization
≤
1
(2)If  ρ
UB
≤
n
(
2
1
/
n
-
1
)
(3)    task is schedulable and
assignτ
priority of task on given processor
(4)Else task is non-schedulable
END
RM scheduling algorithm in Distributed system
BEGIN
(1)If
τ
utilization
≤
1
(2)If  ρ
UB
≤
n
(
2
1
/
n
-
1
)
(3)thentask is schedulable and
assignτ
priority of task on given processor
(4)elsemigrate the task
(5)Else task is non-schedulable
ENDFigure 3
EDF scheduling on single processor.


## 2.2.2. Example of EDF in Distributed System

In case of distributed system, overloaded processor can migrate the victim task to other processors (destination processor) [23].According to Table3 and Figure 4,  τ
utilization is 0.45 which qualifies the acceptance test of schedulability but due to task utilization ρ
utilization becomes 1.15 which is greater than 1. Due to the arrival of this third task ρ
1 becomes overloaded and future tasks will also miss their deadline. Therefore, by applying the migration terminology scheduler checks per processor utilization and migrate victim task to the processor having a time slot for its execution (ρ
utilization
<
1). In the above example ρ
2 has available time slot and its utilization is  also less than 1. In distributed system there is some migration cost α, that is, time taken by task to migrate from one processor (source) to another (destination).Table 3
Arrival time, wcet, period, deadline, and node for assignment of tasksτ
1,   τ
2,   τ
3,   τ
4,   τ
5, and τ
6.
Tasks
Arrival time
Computation time (wcet)
Period
Deadline
τ
utilization
=
τ
wcet
τ
period
Processor
τ
1
0
1
3
3
0.33
ρ
1
τ
2
1
2
5
5
0.4
ρ
1
τ
3
3
1.8
4
4
0.45
ρ
1
τ
4
5
3
6
6
0.5
ρ
2
τ
5
1
0.5
2
2
0.25
ρ
3
τ
6
2
2
4
4
0.5
ρ
3Figure 4
EDF scheduling algorithm in RTDS.


## 2.3. Rate Monotonic Scheduling Algorithm

RM scheduling algorithm comes under static scheduler (static priority) and follows the principle: the shorter the interarrival period the higher the priority of task [23, 24]:
(4)
τ
priority
∝
1
τ
period
.Before assigning the priorities to the task, scheduler first checks the acceptance test by inspecting the utilization value of task as well as processor. For this algorithmT task-set is schedulable on a given processor [25]
(5)
iff
ρ
UB
≤
n
(
2
1
/
n
-
1
)
,
where n is total number of tasks


### 2.3.1. Example of RM in Uniprocessor

Now next is the implementation of RM scheduling algorithm on the data of Table2. In overloading condition neither EDF nor RM performs well [7].The upper bound of RM represents schedulability bound of the number of tasks, and asn increases, it decreases with n (number of jobs). While we compute ρ
UB for any number of tasks (as the number of processors increases towards infinity), the value of ρ
UB remains 0.6931472035974151. This means that
(6)
Lim
n
→
∞
⁡
n
(
2
n
-
1
)
=
ln
⁡
⁡
2
≈
0.693
,
τ
1
utilization
=
τ
wcet
τ
period
=
1
3
=
0.33
,
τ
2
utilization
=
0.4
,
τ
3
utilization
=
0.45
,
ρ
utilization
=
∑
i
=
1
2
τ
i
utilization
=
0.33
+
0.4
=
0.73
,
0
.
693
≤
ρ
utilization
≤
1 but after the arrival of 3rd task ρ
utilization becomes 1.15 which is greater than 1. Acceptance test of RM shows that any task-set is able to schedule through if ρ
utilization
≤
0.693, but not all tasks can be scheduled if 0.693
<
ρ
UB
≤
1 [7]. Therefore, we can say that all tasks may or may not be scheduled by RM.In addition, in case of RM, tasks having the least priority miss the deadline due to preemption of higher priority tasks in overloading case, since RM assigns priorities statically (priority of task will not change throughout the execution process) on the basis ofτ
period. In Figure 5 tasks priority is in order τ
1
>
τ
2
>
τ
3 and also according to Table 4 the execution of third task τ
3 is doubtful. Hence, each new arrival of τ
1 after every periodic cycle preempts task τ
2 or τ
3. Similarly task τ
2 preempts τ
3. Also the arrival of 3rd task exceeds ρ
utilization
>
1 and its priority is also third. As a result, τ
3 has missed its deadline. Therefore, we can say that tasks containing the east priority fail to meet the deadline in overloading situation.Table 4
Shows some values ofρ
UB on different number of tasks n.
Number of tasks(
n)
Tasks
τ
utilization
=
τ
wcet
τ
period
ρ
utilization
=
∑
n
=
1
3
τ
n
utilization
ρ
UB =
n
×
(
2
1
/
n
-
1
)
Comparison  ofρ
utilization with ρ
UB
Conclusion
1
τ
1
0.33
0.33
1.0
0.33
≤
1.0
τ
1 is schedulable
2
τ
2
0.4
0.43
0.8284
0.43
≤
0.82
τ
2 is schedulable
3
τ
3
0.45
0.88
0.7797
0.88
≥
0.77
τ
3 can be schedulableFigure 5
RM scheduling on single processor.


### 2.3.2. Example of RM in Real Time Distributed System

As we have computed that arrival of 3rd task exceeds the range ofρ
utilization, therefore in ρ
1 task τ
3 is a victim task that initiates overloading situation in its source processor. Initially ρ
2 processor is idle and ρ
3
utilization is 0.75. Therefore, on the basis of utilization criteria ρ
2 becomes a destination processor for giving victim task and it will be executed on ρ
2 processor. After the arrival of migrated task τ
1,3 in ρ
2, its utilization becomes 0.45 and its priority is 1, but after the arrival of τ
4 task ρ
2
utilization becomes 0.95 which is again greater than 0.693. In our given example τ
period
=
τ
dline; therefore RM behaves like EDF but if τ
period
≠
τ
dline, then RM behaves different than EDF.


## 2.3.1. Example of RM in Uniprocessor

Now next is the implementation of RM scheduling algorithm on the data of Table2. In overloading condition neither EDF nor RM performs well [7].The upper bound of RM represents schedulability bound of the number of tasks, and asn increases, it decreases with n (number of jobs). While we compute ρ
UB for any number of tasks (as the number of processors increases towards infinity), the value of ρ
UB remains 0.6931472035974151. This means that
(6)
Lim
n
→
∞
⁡
n
(
2
n
-
1
)
=
ln
⁡
⁡
2
≈
0.693
,
τ
1
utilization
=
τ
wcet
τ
period
=
1
3
=
0.33
,
τ
2
utilization
=
0.4
,
τ
3
utilization
=
0.45
,
ρ
utilization
=
∑
i
=
1
2
τ
i
utilization
=
0.33
+
0.4
=
0.73
,
0
.
693
≤
ρ
utilization
≤
1 but after the arrival of 3rd task ρ
utilization becomes 1.15 which is greater than 1. Acceptance test of RM shows that any task-set is able to schedule through if ρ
utilization
≤
0.693, but not all tasks can be scheduled if 0.693
<
ρ
UB
≤
1 [7]. Therefore, we can say that all tasks may or may not be scheduled by RM.In addition, in case of RM, tasks having the least priority miss the deadline due to preemption of higher priority tasks in overloading case, since RM assigns priorities statically (priority of task will not change throughout the execution process) on the basis ofτ
period. In Figure 5 tasks priority is in order τ
1
>
τ
2
>
τ
3 and also according to Table 4 the execution of third task τ
3 is doubtful. Hence, each new arrival of τ
1 after every periodic cycle preempts task τ
2 or τ
3. Similarly task τ
2 preempts τ
3. Also the arrival of 3rd task exceeds ρ
utilization
>
1 and its priority is also third. As a result, τ
3 has missed its deadline. Therefore, we can say that tasks containing the east priority fail to meet the deadline in overloading situation.Table 4
Shows some values ofρ
UB on different number of tasks n.
Number of tasks(
n)
Tasks
τ
utilization
=
τ
wcet
τ
period
ρ
utilization
=
∑
n
=
1
3
τ
n
utilization
ρ
UB =
n
×
(
2
1
/
n
-
1
)
Comparison  ofρ
utilization with ρ
UB
Conclusion
1
τ
1
0.33
0.33
1.0
0.33
≤
1.0
τ
1 is schedulable
2
τ
2
0.4
0.43
0.8284
0.43
≤
0.82
τ
2 is schedulable
3
τ
3
0.45
0.88
0.7797
0.88
≥
0.77
τ
3 can be schedulableFigure 5
RM scheduling on single processor.


## 2.3.2. Example of RM in Real Time Distributed System

As we have computed that arrival of 3rd task exceeds the range ofρ
utilization, therefore in ρ
1 task τ
3 is a victim task that initiates overloading situation in its source processor. Initially ρ
2 processor is idle and ρ
3
utilization is 0.75. Therefore, on the basis of utilization criteria ρ
2 becomes a destination processor for giving victim task and it will be executed on ρ
2 processor. After the arrival of migrated task τ
1,3 in ρ
2, its utilization becomes 0.45 and its priority is 1, but after the arrival of τ
4 task ρ
2
utilization becomes 0.95 which is again greater than 0.693. In our given example τ
period
=
τ
dline; therefore RM behaves like EDF but if τ
period
≠
τ
dline, then RM behaves different than EDF.


## 2.4. D_O_EDF and D_R_EDF Scheduling Algorithm

The main motive behind the derivation of these two scheduling algorithms is Domino’s effect problem of EDF that is created only in overloading condition. We keep in our mind that we should not let the processor shoot in such a way that causes Domino’s effect.The D_O_EDF scheduling algorithm assigns static priorities 0 and 1 to jobs (Figure6). Such static priorities will be used in overloading condition. In overloading condition, this scheduling algorithm discards those tasks that are expected to miss the deadline and their static priority is 0. On the other side, tasks with firm timing constraint and are expected to miss the deadline with static priority 1, are allowed to execute [8].Figure 6
Real time tasks frame format according to D_O_EDF scheduling algorithm.The D_R_EDF scheduling algorithm is an amalgamation of both dynamic and static scheduling algorithms, that is, EDF and RM (Figure7). As we know, EDF is working well in underloaded situation, but its performance reduces exponentially in overloading condition. Similarly, RM behaves normally in underloaded condition but performs well in overloaded situation. Hence, according to given algorithm initially processor uses EDF for task execution, but when tasks start missing deadline due to overloading condition, the scheduler switches towards RM algorithm. As tasks continuously meet the deadline, then it means that the system is in underloaded condition now and then scheduler again switches towards EDF algorithm [8].Figure 7
D_R_EDF scheduling algorithm flowchart.


## 3. Proposed Joint EDF-RM Scheduling Algorithm

### 3.1. The Algorithm

This proposed algorithm is a combination of RM and EDF scheduling algorithms. As we knows in RM the upper bound of processor is computed byn
(
2
1
/
n
-
1
), where n is a number of tasks. In our proposed algorithm this upper bound of RM will be a boundary limit of global task queue B
Q of global scheduler. If cumulative utilization of tasks is less than or equal to B
Q will distribute towards randomly selected processors of the system for execution, otherwise that task will be discarded.The second scheduling algorithm EDF is working for the execution of assigned tasks on a particular processor. The positive side of using global scheduler is permitted to task migration in between processors. Figure9 explains the task migration methodology in between processors.


### 3.2. Joint EDF-RM Scheduling Algorithm

Proposed Joint EDF-RM scheduling algorithm is divided into following three modules:(1)
maintenance of global task queue
(2)
execution of assigned tasks on allotted processors
(3)
migration of tasks in between processors if needed (if overloading alarm generates).Following Algorithm3 explains all above-stated three modules.Algorithm 3:Joint EDF-RM scheduling algorithm.
Input: Random arrival of tasks with
τ
a
r
r
i
v
a
l
,
τ
w
c
e
t
,
τ
p
e
r
i
o
d
,
τ
d
l
i
n
e
Output: Number of tasks meet/miss the deadline along with another parameters
BEGIN
GlobalScheduler()
/
/ Global task Queue
(1)  The aperiodic // Periodic arrival of tasks with arrival time, wcet,
assigned deadline and period
(2)  tasku = wcet/Period;
(3)  UB=n*(Math.pow(2, 1.0/n)-1);
(4)IF  tasku<=UB
(5)    Generated task is schedulable
(6)    pselection(task)
(7)Else
(8)
The task is non-schedulable
pselection(task)
// Random Selection of Processors
(1)  Random Selection of Processor
(2)  PQueue(task)
;
PQueue(task)
// Processors local queue
(1)  Assign priorities to tasks on the basis of deadline
(2)  task
priority
∝
1
task
priority
(3)
TaskExecution(task)
TaskExecution(task)
// Task Execution by using EDF Scheduler
(1)If  tasku<=1
(2)     U= U+ tasku //Cumulative accumulation of task utilization
(3)If
(U<=.810)  //Processor utilization
(4)      The task is ready for execution
(5)Else
(6)    Task Migration (task, tasku)
Taskmigration(task, tasku)
// Task Migration on the basis of a processor
utilization factor
(1)  Sort all processor utilization
(2)  Assign task
to the processor having least a
utilization factor
(3)
PQueue(task);
END


### 3.3. Significance of the Above-Stated Proposed Algorithm

System assumed here is loosely coupled distributed system in which all processors share identical architecture (homogeneous RTDS). Threshold limit of each processor is fixed and in order to execute the tasks, the Earliest Deadline First (EDF) scheduling is employed by every processor. In given system all tasks are independent and theirτ
period
≥
τ
dline. Based on the priority of task, higher priority job can preempt the lower priority task. One central scheduler (global scheduler) is used that maintains the global task queue for the entire system. As we recognize that global scheduler allows task migration in between processors, therefore for every processor we have set one utilization threshold value that generates alarms for migration of task. This entire system deals with soft as well as firm real time tasks.In Figure8, there is a global scheduler that maintains a waiting task queue globally. In order to avoid the problem of overloading, limited amount of tasks arrives on the queue and its boundary limit is determined by using a RM scheduling algorithm. Tasks having τ
utilization
+
∑
i
=
1
n
-
1
τ
i
utilization
≤
i
×
(
2
1
/
i
-
1
) will be easily executable or if τ
utilization
+
∑
i
=
1
n
-
1
τ
i
utilization
≤
i
×
(
2
1
/
i
-
1
)
≤
1, then not all tasks will be executable.Figure 8
Architecture of proposed algorithm.Figure 9
Migration scenario in proposed algorithm.As the queue behaves on the basis of first in first out, tasks are randomly assigned to processors. Each processor executes tasks by using an EDF scheduling algorithm. Small change we have done in this existing algorithm is migration threshold limit. This migration threshold limit decides the migration of task from given processor. In Figure9  ρ
1 processor utilization is ρ
1
utilization
=
τ
i
utilization
+
τ
2
utilization
+
τ
3
utilizaion
+
τ
(
n
-
2
)
utilization
=
0.61
≤
0.810, And after the arrival of τ
n
-
1 processor utilization becomes ρ
1
utilization
+
τ
(
n
-
1
)
utilization
=
0.70
≤
0.810, but arrival of τ
n reaches utilization towards ρ
1
utilization
+
τ
(
n
)
utilization
≥
0.810
<
1. Arrival of further tasks will increase ρ
1
utilization by 1; after that, all tasks start missing deadline which causes a Domino effect. After migration threshold alarm, processor checks the utilization values of other processors. And then migrate the task to the processor having the least utilization. ρ
2 processor is a destination node given in Figure 9.Theorem 1.
If the upper bound of global task queue isn
×
(
2
1
/
n
-
1
), then overloading of processor is reduced.Proof.
Given set ofn aperiodic tasks τ
1
,
τ
2
,
τ
3
,
τ
4
,
…
,
τ
n arrives in a global task queue, whose periods and execution times are τ
1
period
,
τ
2
period
,
τ
3
period
,
τ
4
period
,
…
,
τ
n
period and τ
1
wcet
,
τ
2
wcet, τ
3
wcet
,
τ
4
wcet
,
…
,
τ
n
wcet, respectively. τ
1
utilization
,
τ
2
utilization
,
τ
3
utilization
,
τ
4
utilization
,
…
,
τ
n
utilization are per task utilization. We are considering here τ
deadline
≤
τ
period. There are 4 processors present in our RTDS with ρ
1
utilization, ρ
2
utilization, ρ
3
utilization, and ρ
4
utilization being their respective utilizations. Global scheduler randomly selects processors for the allocation of tasks but tasks, follow FCFS discipline for allocation.
We are taking three cases in order to proof given theorem
Case I. Global queue has infinite limit as the global queue is containing no acceptance test of task. Without checking its utilization, based on FCFS τ
1 task assigned to the randomly selected processor ρ
2 whose ρ
2
utilization
<
1, and after the assignment of τ
1, two conditions can occur:(7)
ρ
2
utilization
=
{
ρ
2
utilization
+
τ
1
utilization
,
if
τ
1
utilization
≤
1
,
ρ
2
utilization
,
otherwise
,
(8)
ρ
2
utilization
+
τ
1
utilization
=
{
schedule
τ
1
,
if
≤
1
,
miss
the
deadline
or
overload
,
otherwise
,
(9)
overload
=
{
migration
,
if
ρ
n
processor
<
1
,
wait
for
execution
,
otherwise
.
In this case there are more chances of overloading on every processor.
Case II.Boundary limit of global queue is 1, that is, ∑
i
=
1
n
τ
i
utilization
≤
1.
Here only those tasks are allowed to enter in a global task queue whoseτ
utilization
≤
1.
If tasks in a queue are waiting for an assignment and the arrival of new task increases the boundary limit by 1, then all upcoming tasks will not be allowed for admission:(10)
B
Q
=
{
allowed
for
execution
,
if
≤
1
,
Queue
is
full
,
otherwise
.
In this case (7) is satisfied only on 1st condition; that is,
(11)
ρ
utilization
=
ρ
utilization
+
τ
utilization
.
This case gives a guarantee of schedulability of every task. Equations (8) and (9) behave similar to 1st case. The limitation of the EDF scheduling algorithm is that if one task starts missing deadline, then upcoming tasks also miss deadline continuously (Domino’s effect).
Case III. Global queue has boundary limit n
×
(
2
1
/
n
-
1
).
Tasks having∑
i
=
1
n
τ
n
utilization
≤
n
×
(
2
1
/
n
-
1
) are allowed to execute on assigned processors. As we know the value of
(12)
n
×
(
2
1
/
n
-
1
)
=
{
1
,
for
n
=
1
,
<
1
,
for
n
tends
∞
.
According to RM scheduling, every task is schedulable if itsτ
utilization
≤
n
×
(
2
1
/
n
-
1
), but its execution is doubtful if it is in between n
×
(
2
1
/
n
-
1
) and 1. Therefore, here queue allows only those tasks for further execution whose τ
utilization
≤
n
×
(
2
1
/
n
-
1
). Consider
(13)
∑
i
=
1
n
τ
i
utilization
≤
n
×
(
2
1
/
n
-
1
)
∀
n
,
B
Q
=
{
allowed
for
execution
,
if
≤
n
×
(
2
1
/
n
-
1
)
,
tasks
are
non-schedulable
,
otherwise
.
After the allocation of tasks on the processor, it will execute tasks by using EDF:
(14)
ρ
utilization
=
{
schedule
tasks
,
if
≤
1
,
overloading
occur
,
if
>
1
.
But in 3rd case very rare tasks utilization reaches 1 but not beyond 1. Hence, we can say that if the upper bound of global task queue is n
×
(
2
1
/
n
-
1
), then overloading of processor is reduced.


## 3.1. The Algorithm

This proposed algorithm is a combination of RM and EDF scheduling algorithms. As we knows in RM the upper bound of processor is computed byn
(
2
1
/
n
-
1
), where n is a number of tasks. In our proposed algorithm this upper bound of RM will be a boundary limit of global task queue B
Q of global scheduler. If cumulative utilization of tasks is less than or equal to B
Q will distribute towards randomly selected processors of the system for execution, otherwise that task will be discarded.The second scheduling algorithm EDF is working for the execution of assigned tasks on a particular processor. The positive side of using global scheduler is permitted to task migration in between processors. Figure9 explains the task migration methodology in between processors.


## 3.2. Joint EDF-RM Scheduling Algorithm

Proposed Joint EDF-RM scheduling algorithm is divided into following three modules:(1)
maintenance of global task queue
(2)
execution of assigned tasks on allotted processors
(3)
migration of tasks in between processors if needed (if overloading alarm generates).Following Algorithm3 explains all above-stated three modules.Algorithm 3:Joint EDF-RM scheduling algorithm.
Input: Random arrival of tasks with
τ
a
r
r
i
v
a
l
,
τ
w
c
e
t
,
τ
p
e
r
i
o
d
,
τ
d
l
i
n
e
Output: Number of tasks meet/miss the deadline along with another parameters
BEGIN
GlobalScheduler()
/
/ Global task Queue
(1)  The aperiodic // Periodic arrival of tasks with arrival time, wcet,
assigned deadline and period
(2)  tasku = wcet/Period;
(3)  UB=n*(Math.pow(2, 1.0/n)-1);
(4)IF  tasku<=UB
(5)    Generated task is schedulable
(6)    pselection(task)
(7)Else
(8)
The task is non-schedulable
pselection(task)
// Random Selection of Processors
(1)  Random Selection of Processor
(2)  PQueue(task)
;
PQueue(task)
// Processors local queue
(1)  Assign priorities to tasks on the basis of deadline
(2)  task
priority
∝
1
task
priority
(3)
TaskExecution(task)
TaskExecution(task)
// Task Execution by using EDF Scheduler
(1)If  tasku<=1
(2)     U= U+ tasku //Cumulative accumulation of task utilization
(3)If
(U<=.810)  //Processor utilization
(4)      The task is ready for execution
(5)Else
(6)    Task Migration (task, tasku)
Taskmigration(task, tasku)
// Task Migration on the basis of a processor
utilization factor
(1)  Sort all processor utilization
(2)  Assign task
to the processor having least a
utilization factor
(3)
PQueue(task);
END


## 3.3. Significance of the Above-Stated Proposed Algorithm

System assumed here is loosely coupled distributed system in which all processors share identical architecture (homogeneous RTDS). Threshold limit of each processor is fixed and in order to execute the tasks, the Earliest Deadline First (EDF) scheduling is employed by every processor. In given system all tasks are independent and theirτ
period
≥
τ
dline. Based on the priority of task, higher priority job can preempt the lower priority task. One central scheduler (global scheduler) is used that maintains the global task queue for the entire system. As we recognize that global scheduler allows task migration in between processors, therefore for every processor we have set one utilization threshold value that generates alarms for migration of task. This entire system deals with soft as well as firm real time tasks.In Figure8, there is a global scheduler that maintains a waiting task queue globally. In order to avoid the problem of overloading, limited amount of tasks arrives on the queue and its boundary limit is determined by using a RM scheduling algorithm. Tasks having τ
utilization
+
∑
i
=
1
n
-
1
τ
i
utilization
≤
i
×
(
2
1
/
i
-
1
) will be easily executable or if τ
utilization
+
∑
i
=
1
n
-
1
τ
i
utilization
≤
i
×
(
2
1
/
i
-
1
)
≤
1, then not all tasks will be executable.Figure 8
Architecture of proposed algorithm.Figure 9
Migration scenario in proposed algorithm.As the queue behaves on the basis of first in first out, tasks are randomly assigned to processors. Each processor executes tasks by using an EDF scheduling algorithm. Small change we have done in this existing algorithm is migration threshold limit. This migration threshold limit decides the migration of task from given processor. In Figure9  ρ
1 processor utilization is ρ
1
utilization
=
τ
i
utilization
+
τ
2
utilization
+
τ
3
utilizaion
+
τ
(
n
-
2
)
utilization
=
0.61
≤
0.810, And after the arrival of τ
n
-
1 processor utilization becomes ρ
1
utilization
+
τ
(
n
-
1
)
utilization
=
0.70
≤
0.810, but arrival of τ
n reaches utilization towards ρ
1
utilization
+
τ
(
n
)
utilization
≥
0.810
<
1. Arrival of further tasks will increase ρ
1
utilization by 1; after that, all tasks start missing deadline which causes a Domino effect. After migration threshold alarm, processor checks the utilization values of other processors. And then migrate the task to the processor having the least utilization. ρ
2 processor is a destination node given in Figure 9.Theorem 1.
If the upper bound of global task queue isn
×
(
2
1
/
n
-
1
), then overloading of processor is reduced.Proof.
Given set ofn aperiodic tasks τ
1
,
τ
2
,
τ
3
,
τ
4
,
…
,
τ
n arrives in a global task queue, whose periods and execution times are τ
1
period
,
τ
2
period
,
τ
3
period
,
τ
4
period
,
…
,
τ
n
period and τ
1
wcet
,
τ
2
wcet, τ
3
wcet
,
τ
4
wcet
,
…
,
τ
n
wcet, respectively. τ
1
utilization
,
τ
2
utilization
,
τ
3
utilization
,
τ
4
utilization
,
…
,
τ
n
utilization are per task utilization. We are considering here τ
deadline
≤
τ
period. There are 4 processors present in our RTDS with ρ
1
utilization, ρ
2
utilization, ρ
3
utilization, and ρ
4
utilization being their respective utilizations. Global scheduler randomly selects processors for the allocation of tasks but tasks, follow FCFS discipline for allocation.
We are taking three cases in order to proof given theorem
Case I. Global queue has infinite limit as the global queue is containing no acceptance test of task. Without checking its utilization, based on FCFS τ
1 task assigned to the randomly selected processor ρ
2 whose ρ
2
utilization
<
1, and after the assignment of τ
1, two conditions can occur:(7)
ρ
2
utilization
=
{
ρ
2
utilization
+
τ
1
utilization
,
if
τ
1
utilization
≤
1
,
ρ
2
utilization
,
otherwise
,
(8)
ρ
2
utilization
+
τ
1
utilization
=
{
schedule
τ
1
,
if
≤
1
,
miss
the
deadline
or
overload
,
otherwise
,
(9)
overload
=
{
migration
,
if
ρ
n
processor
<
1
,
wait
for
execution
,
otherwise
.
In this case there are more chances of overloading on every processor.
Case II.Boundary limit of global queue is 1, that is, ∑
i
=
1
n
τ
i
utilization
≤
1.
Here only those tasks are allowed to enter in a global task queue whoseτ
utilization
≤
1.
If tasks in a queue are waiting for an assignment and the arrival of new task increases the boundary limit by 1, then all upcoming tasks will not be allowed for admission:(10)
B
Q
=
{
allowed
for
execution
,
if
≤
1
,
Queue
is
full
,
otherwise
.
In this case (7) is satisfied only on 1st condition; that is,
(11)
ρ
utilization
=
ρ
utilization
+
τ
utilization
.
This case gives a guarantee of schedulability of every task. Equations (8) and (9) behave similar to 1st case. The limitation of the EDF scheduling algorithm is that if one task starts missing deadline, then upcoming tasks also miss deadline continuously (Domino’s effect).
Case III. Global queue has boundary limit n
×
(
2
1
/
n
-
1
).
Tasks having∑
i
=
1
n
τ
n
utilization
≤
n
×
(
2
1
/
n
-
1
) are allowed to execute on assigned processors. As we know the value of
(12)
n
×
(
2
1
/
n
-
1
)
=
{
1
,
for
n
=
1
,
<
1
,
for
n
tends
∞
.
According to RM scheduling, every task is schedulable if itsτ
utilization
≤
n
×
(
2
1
/
n
-
1
), but its execution is doubtful if it is in between n
×
(
2
1
/
n
-
1
) and 1. Therefore, here queue allows only those tasks for further execution whose τ
utilization
≤
n
×
(
2
1
/
n
-
1
). Consider
(13)
∑
i
=
1
n
τ
i
utilization
≤
n
×
(
2
1
/
n
-
1
)
∀
n
,
B
Q
=
{
allowed
for
execution
,
if
≤
n
×
(
2
1
/
n
-
1
)
,
tasks
are
non-schedulable
,
otherwise
.
After the allocation of tasks on the processor, it will execute tasks by using EDF:
(14)
ρ
utilization
=
{
schedule
tasks
,
if
≤
1
,
overloading
occur
,
if
>
1
.
But in 3rd case very rare tasks utilization reaches 1 but not beyond 1. Hence, we can say that if the upper bound of global task queue is n
×
(
2
1
/
n
-
1
), then overloading of processor is reduced.


## 4. Performance Analysis and Simulation Results

In order to evaluate our proposed scheduling algorithm we have used Eclipse Java EE IDE. The operation of the proposed study is measured by calculating the Average CPU Utilization, Success Ratio, Failure Ratio, and Maximum Tardiness. The simulation is done with more than 26000 transactions on 10 processors of RTDS, but in simulation results we have mentioned transactions up to 2100. Before making the demonstration of calculating simulation results, let us discuss those parameters that determine the performance of joint EDF-RM scheduling algorithm with some existing algorithms (EDF, RM, D_O_EDF, and D_R_EDF).


### 4.1. Average CPU Utilization (A
ρ
utilization)

It is defined as(15)
A
ρ
utilization
=
∑
i
=
1
n
ρ
i
utilization
n
,
where the number of processors (ρ) varies from 1 to n.In Figure10, the CPU utilization in proposed joint EDF-RM scheduling algorithm is lesser than the other three algorithms. As (1) explains, processor utilization is dependent on particular tasks utilization and further tasks utilization is dependent on the worst case execution time (τ
wcet) and interarrival period (τ
period) of tasks as well. Additionally, the τ
wcet and τ
period are generated randomly in given simulation. Due to all these factors of real time tasks the Average CPU Utilization can vary from time to time. For example, in Figure 10   A
ρ
utilization of 8 processors for 300 tasks is 0.16338866 and on the other side for 10 processors it is 0.4004137. Similarly, In EDF A
ρ
utilization of 8 processors for 2100 tasks is 3.287974 whereas for 10 processors it is 3.0410550. Hence, the value of Average CPU Utilization is uncertain, but as compared to previous existing algorithm, proposed joint EDF-RM algorithm gives better A
ρ
utilization because of migration threshold limit of all processors along with the boundary limit of global task queue.Average CPU Utilization versus number of transactions on 8 and 10 processors.
(a)
(b)


### 4.2. Success Ratio (SR)

Consider(16)
SR
=
Successfully
scheduled
tasks
Total
number
of
tasks
arrival
.Meeting with the deadline is very imperative for all real time tasks; therefore we have computed success ratio that tells the percentage of successful implementation of tasks from total transactions.After simulating thousands of tasks, we find that EDF, RM and D_R_EDF scheduling algorithms’ Success ratio can vary however we sometimes find that our proposed algorithm has a higher Success Ratio than the existing algorithms (Figure11). Reason behind its best performance is a threshold value of task migration.Number of transactions versus Success Ratio on 3, 5, 8, and 10 Processors.
(a)
(b)
(c)
(d)


### 4.3. Failure Ratio (FR)

Consider(17)
FR
=
Tasks
miss
the
deadline
Total
number
of
tasks
arrival
.This parameter computes the other side of coin, that is, percentage of those tasks which are unable to meet the deadline. Missing deadline is also a big task in front of all algorithms (Figure12). Therefore, we also compute the Failure Ratio that tells us the occurrence of missing deadline.Number of transactions versus Failure Ratio on 3, 5, 8 and 10 processors.
(a)
(b)
(c)
(d)


### 4.4. Maximum Tardiness

As we know, tardiness is the lateness occurring in tasks execution; that is,(18)
tardiness
=
TST
-
τ
deadline
,
Max
⁡
Tardiness
=
max
⁡
⁡
(
tard
τ
i
)
,
where
i
∈
T
.While missing a deadline, we have computed the time after which task successfully executes. Figure13 explains that the proposed algorithm has Minimum Tardiness compared to existing algorithms.Number of transactions versus Maximum Tardiness on 8 and 10 processors.
(a)
(b)


## 4.1. Average CPU Utilization (A
ρ
utilization)

It is defined as(15)
A
ρ
utilization
=
∑
i
=
1
n
ρ
i
utilization
n
,
where the number of processors (ρ) varies from 1 to n.In Figure10, the CPU utilization in proposed joint EDF-RM scheduling algorithm is lesser than the other three algorithms. As (1) explains, processor utilization is dependent on particular tasks utilization and further tasks utilization is dependent on the worst case execution time (τ
wcet) and interarrival period (τ
period) of tasks as well. Additionally, the τ
wcet and τ
period are generated randomly in given simulation. Due to all these factors of real time tasks the Average CPU Utilization can vary from time to time. For example, in Figure 10   A
ρ
utilization of 8 processors for 300 tasks is 0.16338866 and on the other side for 10 processors it is 0.4004137. Similarly, In EDF A
ρ
utilization of 8 processors for 2100 tasks is 3.287974 whereas for 10 processors it is 3.0410550. Hence, the value of Average CPU Utilization is uncertain, but as compared to previous existing algorithm, proposed joint EDF-RM algorithm gives better A
ρ
utilization because of migration threshold limit of all processors along with the boundary limit of global task queue.Average CPU Utilization versus number of transactions on 8 and 10 processors.
(a)
(b)


## 4.2. Success Ratio (SR)

Consider(16)
SR
=
Successfully
scheduled
tasks
Total
number
of
tasks
arrival
.Meeting with the deadline is very imperative for all real time tasks; therefore we have computed success ratio that tells the percentage of successful implementation of tasks from total transactions.After simulating thousands of tasks, we find that EDF, RM and D_R_EDF scheduling algorithms’ Success ratio can vary however we sometimes find that our proposed algorithm has a higher Success Ratio than the existing algorithms (Figure11). Reason behind its best performance is a threshold value of task migration.Number of transactions versus Success Ratio on 3, 5, 8, and 10 Processors.
(a)
(b)
(c)
(d)


## 4.3. Failure Ratio (FR)

Consider(17)
FR
=
Tasks
miss
the
deadline
Total
number
of
tasks
arrival
.This parameter computes the other side of coin, that is, percentage of those tasks which are unable to meet the deadline. Missing deadline is also a big task in front of all algorithms (Figure12). Therefore, we also compute the Failure Ratio that tells us the occurrence of missing deadline.Number of transactions versus Failure Ratio on 3, 5, 8 and 10 processors.
(a)
(b)
(c)
(d)


## 4.4. Maximum Tardiness

As we know, tardiness is the lateness occurring in tasks execution; that is,(18)
tardiness
=
TST
-
τ
deadline
,
Max
⁡
Tardiness
=
max
⁡
⁡
(
tard
τ
i
)
,
where
i
∈
T
.While missing a deadline, we have computed the time after which task successfully executes. Figure13 explains that the proposed algorithm has Minimum Tardiness compared to existing algorithms.Number of transactions versus Maximum Tardiness on 8 and 10 processors.
(a)
(b)


## 5. Conclusion and Future Work

Proposed scheduling algorithm is the combination of EDF and RM scheduling algorithms that rise above the overloading problem of any processor. We have set the threshold limit 0.81 that generates alarm for the migration of upcoming tasks because overloading on task is restricted. We simulate this work for homogeneous system; in the future we will implement it on heterogeneous arrangement. One main problem occurs when running tasks are preempted by higher priority new tasks because running tasks miss the deadline. Hence, in future we will work on preemption technique of scheduling algorithms with fault tolerant techniques.



---

*Source: 485361-2014-01-22.xml*