Project Summary

This paper is about introducing a new scheduling

technique in a real-time system which is

defined based on the paper as the computation not only depends on producing a

correct output, but the output is also delivered within a deadline. The

identified problem for proposing such technique is because both EDF and LLF

have many contexts switching and the probability

of overhead occurrence causing degraded performance of the system. The proposed technique is a dynamic

scheduling algorithm that combines both

the EDF and LSF algorithms to reduce the problems that had been identified

before.

Background

Earliest Deadline First (EDF) work by giving

priorities based on the smallest deadline where it will then have the highest

probability. This scheduling algorithm was introduced by Liu and Layland in

1973 while Least Laxity First (LLF) and Maximum Urgency First (MUF) was

introduced by David B. Stewart and Pradeep K. Khosla where for LLF work by

selecting task with the minimum laxity to execute and MUF is a combination of

fixed and dynamic priority scheduling where each task is given an urgency. All

the algorithms have its own problems based on the finding of this paper. The

problems have then initiated the idea to

resolve the problems of the discussed algorithms. However, the proposed work is

only focused on comparing itself with only two dynamic algorithms which are the EDF and LLF. The identified problems

for EDF are high average waiting time, many contexts switching, does not let

tasks be executed with their minimal time and leads to the occurrence of overhead. The LLF on the other

hand facing the same problem with the EDF which has many context switches

occurred when two processes have similar laxities. This paper is a

collaboration with different universities from a different country which is from the country of Ethiopia and India.

Three of the authors are from Ethiopia and only one of them are from India. The

collaborated universities are between the Debre Markos University, Adama

Science and Technology University and St Mary’s College of Engineering and

Technology from India.

Process

The process of making this research a success is by

undergoing a simulation of the proposed algorithm with the previously developed

dynamic scheduling algorithms. It was simulated based on the parameters of

arrival time, execution, and relative

deadline while the schedulability of the proposed system was compared with the

schedulability of EDF where it considered many metrics like average waiting

time of the task, context switching,

system overhead and optimality. The three main parameters on the dataset

preparation of this paper have it own

rules which the first one is for the arrival time where each task is computed

using uniformly distributed random

integer number to make the computation easier. The range taken was from 1 to 30

as in real case more than one task will arrive at the same time and by doing

so, at least 20% of the total dataset will be ready at the same time. The second

rule is for the execution time where each task is computed using the same

technique with the arrival time rule but only ranging from 1 to 6 based on the

assumption of each task should have the maximum execution time of 6 units. It

is also stated in the rule that the execution time should be less than (deadline – arrival time) of each task. The third rule applies for the deadline where each task is determined by the logic that its deadline should be greater than

(arrival time + execution time) and

vice versa. Figure 1 is the proposed algorithm of this paper. It works by

determining the precise slack time and a deadline

of tasks where it will then give priority to the task and this algorithm is a

dynamic priority scheduling algorithm. It basically

works with the same concept of EDF except that it will also consider the

slack time of the tasks and let it continue to run the current task so that one

will not miss its deadline.

From the Table

1, have three algorithms has been used to test using same sample data. Firstly

by used scheduling with EDF, this paper found that sample data can be

scheduled, and the number of context switching and average waiting time can be

counted clearly. The second LLF

scheduling has been used and found that the result as same as EDF scheduler.

Lastly by used proposed algorithms scheduling, the result shows that the previous

proposed dynamic algorithms are less efficient

in term of context switching and average waiting time, which bottlenecks for

the system has overall performance.

Based on the finding in Table 2 and Figure 2, finding a show

that the number of context switching is high and very dynamic due to the Least

Slack First algorithms. But different to the proposed algorithms, it shows the number context switching is low and

mostly less than EDF and LST scheduler.

In Table 3 and Figure 3, if the number of context

switching is high than the average waiting time also become high except

switching is due to pre-empting the task have high

priority by the task having low slack time. In the finding, it shows that the

proposed algorithms have a low average waiting time than both EDF and LST

scheduling techniques.

In this finding also has mentioned on overhead performance, due to experiment that has been

done, it can say that proposed algorithms

have a low overhead than both EDF and

LST. In the proposed system the probability of tie to occur is (LST n EDF) where LST is laxity tie and EDF is deadline

tie, both want to execute at the same time.LST intersection EDF this is

because the proposed scheduler takes both slack and deadline into

consideration, so the scheduled will be confused to execute the task. This will show that, the

number of elements in (LST n EDF) less and equal to the element in individual

sets. Therefore, the proposed system is better in term of occurrence of

overhead. Based on all of the finding,

it can be concluded and prove that the real-time

dynamics scheduling algorithms are the

best and suit to the uni-processor system.

Recommendations for further

action

In future work to make

the best real-time

dynamics scheduling algorithms performance, this

can be recommended to combined some logic data such as slack and deadline into

multiprocessor and should use more logical and reasonable data.