Volume 1 Issue 1 (2023), E-XXXX-XXXX

[Link]

A Comparative Approach on Scheduling Algorithms for Real time Systems

Manasa R1 , Divya Mabbu2
1,2School of Computer Science and Engineering, REVA University, India.
Abstract
Real-time systems are extensively used in many applications, especially critical systems. A real-time system is
considered to be reliable and safe if it is able to execute all its tasks accurately within given time constraints. A
requirement might need the real-time systems to execute several tasks. The system must be able to assign processors
and necessary resources to ensure smooth and timely execution. In this paper, we give an overview of existing
scheduling algorithms for static and dynamic systems. This paper also presents a comparative study of these
scheduling algorithms.
Keywords: Real-time, Scheduling algorithms, EDF, SJF, LST, Rate monotonic.
Article Info:
Submitted: 12/01/2023 Accepted: 29/01/2023 Approve: 22/04/2023 Published: 28/05/2023

INTRODUCTION
Real-time systems are computer systems that are able to process numerous tasks withing specified
timing constraints. These systems must produce accurate results in environments with low power, resources
and processing capabilities. Timing constraints refer to release time, execution time and deadline. Processors
are expected to complete execution of tasks within specified deadlines. Thus, scheduling algorithms play a
crucial role in decision making of assigning tasks to processors. A real-time system is classified into Hard real-
time and Soft real-time according to timing constraints. Hard real-time systems enforce strict timing
constraints. Missing a deadline would cause severe causalities. While soft real-time systems are much lenient,
missing a deadline only diminishes performance. Real-time systems can also be grouped to Static and Dynamic
systems. Dynamic systems are more flexible than static systems. As opposed to Static systems, Dynamic
systems adapt to changing requirements with ease. To ensure that the timing constraints are met, a study to
analyse performance and challenges of scheduling algorithms must be carried out. One of the ways to classify
scheduling algorithms is Online and Offline scheduling. Static systems utilize offline scheduling whereas,
dynamic systems follow online scheduling. Some of the scheduling algorithms used are: Earliest Deadline First
(EDF), Least Slack Time-First (LST), Shortest Job First (SJF), Rate Monotonic (RM).

METHOD
Earliest Deadline First (EDF) Scheduling Algorithm
Earliest Deadline First (EDF) is an optimal algorithm that is widely used in both static and dynamic
systems. As the name suggests, the algorithm executes the task that has the least deadline in ready queue. By
using this algorithm, the CPU can be utilised up to 100% while still ensuring that all tasks are completed within
deadline.

Assign Deadline to each Determine task with Repeat until all tasks
Execute selected task are executed
task least deadline

Figure 1. Earliest Deadline First (EDF) Scheduling Algorithm

Least Slack Time First (LST) Algorithm
Least Slack Time First (LST) assigns highest priority to task with least slack time. The priorities in LST
are dynamically assigned. Slack time can be calculated using the following equation:

Correspondence Address
E-mail: manasar123@[Link]

This work is licensed under a Creative Commons

Attribution-ShareAlike 4.0 International License
© Manasa R and Divya Mabbu 30

𝑠𝑡 = 𝑑 − 𝑡 − 𝑟 (1)
Where, 𝑑 is deadline
𝑡 is current time
𝑟 is remaining execution time

Figure 2. Shows the Least Slack Time First Algorithm flow

Shortest Job First (SJF) Scheduling Algorithm
Shortest Job First (SJF) algorithm prioritises execution of tasks based on execution time. The task with
smallest execution time is executed first. Priorities are made statically.

Figure 3. Shows the Shortest Job First (SJF) Scheduling Algorithm flow
Rate Monotonic (RM) Scheduling Algorithm
The Rate Monotonic Algorithm (RM) is a static, priority-based scheduling algorithm used for real-time
systems. The priorities are assigned to tasks based on their periodic rate of execution that is, task with the
highest rate having the highest priority. In this algorithm, tasks are scheduled based on their deadlines, with
the task with the earliest deadline having the highest priority.
Literature survey
In [1], conducted a comparative study of different scheduling algorithms, including earliest deadline
first (EDF), deadline monotonic (DM), and rate monotonic (RM). The study compared the performance of
these algorithms in terms of utilization, response time, and pre-emption overhead, and concluded that EDF
performs the best in most scenarios [1]. Sharma et al. compared the performance of EDF and DM in a
distributed real-time system. The study analysed the impact of network latency and load on the performance
of the algorithms and concluded that EDF outperforms DM in most scenarios [2]. Chen et al. conducted a
comparative study of different scheduling algorithms, including EDF, DM, RM, and proportional share (PS).
The study compared the performance of these algorithms in terms of response time, system utilization, and
fairness and concluded that PS performs the best in scenarios where fairness is important, while EDF performs
the best in scenarios where response time is critical [3].
Li et al. compared the performance of different scheduling algorithms, including EDF, DM, and RM, in a
real-time system with mixed-criticality tasks. The study analysed the impact of task priority, deadline, and
budget on the performance of the algorithms and concluded that RM performs the best in scenarios with strict
timing requirements, while EDF performs the best in scenarios with soft timing requirements [4]. Pinto et al.
compared the performance of different scheduling algorithms, including EDF, DM, RM, and PS, in a real-time
system with sporadic tasks. The study analysed the impact of task arrival rate and utilization on the
performance of the algorithms and concluded that EDF performs the best in scenarios with high task arrival
rates, while RM performs the best in scenarios with low task arrival rates [5]. Tovar et al. conducted a
comparative study of different scheduling algorithms, including EDF, DM, RM, and PS, in a real-time system
with pre-emptive tasks.
The study analysed the impact of task priority and deadline on the performance of the algorithms and
concluded that EDF and DM perform the best in scenarios with high-priority tasks, while RM performs the
best in scenarios with low-priority tasks [6].
Table 1. Tabular Comparison of the scheduling algorithms
Algorithm Type Pre-emptive Advantages Disadvantages
First - Come, Dynamic No Simple to implement Can lead to poor performance if
First- Served there are long-running tasks
that arrive early.

[Link] Electrical and Computer Experiences 1 (1) (2023) 29-35

© Manasa R and Divya Mabbu 31

Shortest Job First Dynamic Yes Can lead to optimal Requires knowledge of the
performance if the estimated running time of each task, which
running times are accurate may not always be available.

Priority Dynamic Yes Can lead to optimal Requires knowledge of the

Scheduling performance if the estimated running time of each task, which
running times are accurate may not always be available.

Round Robin Dynamic Yes Can lead to good Can lead to high overhead if the
performance if the time slice time slice is too small.
is chosen correctly

Earliest Deadline Dynamic Yes Can lead to optimal Requires knowledge of the
First performance if the deadlines deadline of each task, which may
are accurate not always be available.

Least Slack Time Dynamic Yes Efficient for non-pre- May not guarantee all tasks meet
emptive and non-periodic their deadlines. - Requires
tasks. - Good average-case periodic rescheduling,
response time performance. increasing overhead.

Rate Monotonic Static Yes Provides guarantees on May not be efficient for non-
Scheduling response time and deadline periodic tasks. - Low priority
meeting. - Simple to tasks may face starvation.
implement.

In the above table, we compare the real-time scheduling algorithms based on their type (preemptive or
non-preemptive), advantages, and disadvantages. Also, note that some algorithms, such as SJF and EDF, can
be either preemptive or non-preemptive, while others, such as FCFS and priority scheduling, are typically non-
preemptive. Overall, the choice of algorithm depends on the specific requirements of the system and the tasks
that need to be scheduled. For example, if the tasks have strict deadlines, EDF may be the best choice, while if
the tasks have varying running times, SJF may be a good option. It's also important to consider the overhead
of each algorithm and the potential for priority inversion or other problems.

RESULT AND DISCUSSION

Graphical comparison of algorithms

Figure 4. A graph representing average waiting times and Turnaround times of

SJF, FCFS and Priority algorithms

[Link] Electrical and Computer Experiences 1 (1) (2023) 29-35

© Manasa R and Divya Mabbu 32

Figure 5. A graph representing average waiting times of algorithms of FCFS, RR, SJF

Figure 6. A graph representing average response times of real time

algorithms of RR, SJ F and FCFS
The graph is only a representation of the average waiting time and response time of each algorithm and
may not be exhaustive and accurate. The actual performance may depend on specific system requirements
and constraints. From the above graphs, we compare the real-time scheduling algorithms based on their
response time and average waiting time. Response time is the time from when a task arrives until it completes,
while average waiting time is the time a task waits in the queue before being scheduled. The lower the values
for these metrics, the better the performance of the scheduling algorithm.
As shown from the graph, different scheduling algorithms have different trade-offs between response
time and waiting time. For example, FCFS has low overhead but high waiting times, while SJF has low waiting
times but may lead to starvation. Priority scheduling can lead to good performance if the priorities are
assigned correctly but can also lead to priority inversion. Round robin can balance the response time and
waiting time but may have high overhead if the time slice is too small. EDF can lead to optimal performance if
the deadlines are accurate, but requires knowledge of the deadline of each task, which may not always be
available.
Overall, the choice of algorithm depends on the specific requirements of the system and the tasks that
need to be scheduled. By comparing the performance of the algorithms graphically, it's easier to see the trade-
offs between response time and waiting time and make an informed decision about which algorithm to use.
Discussion of trade-offs and performance of the algorithms:
1. First-Come, First-Served (FCFS)
a. Trade-offs: Simple to implement but can lead to poor performance if there are long-running tasks that
arrive early.

[Link] Electrical and Computer Experiences 1 (1) (2023) 29-35

© Manasa R and Divya Mabbu 33

b. Performance: FCFS has low overhead but high waiting times, which can lead to poor performance if
there are many long-running tasks.
2. Shortest Job First (SJF)
a. Trade-offs: Can lead to optimal performance if the estimated running times are accurate but requires
knowledge of the running time of each task, which may not always be available.
b. Performance: SJF has low waiting times but may lead to starvation if short tasks continually arrive,
preventing longer tasks from being scheduled.
3. Priority Scheduling
a. Trade-offs: Can lead to good performance if the priorities are assigned correctly, but can lead to
priority inversion, where a low-priority task holds a resource needed by a high-priority task.
b. Performance: Priority scheduling can lead to good performance if the priorities are assigned correctly
but can also lead to poor performance if priorities are not set appropriately.
4. Round Robin
a. Trade-offs: Can lead to good performance if the time slice is chosen correctly but can lead to high
overhead if the time slice is too small.
b. Performance: Round Robin can balance the response time and waiting time but may have high
overhead if the time slice is too small.
5. Earliest Deadline First (EDF)
a. Trade-offs: Can lead to optimal performance if the deadlines are accurate, but requires knowledge of
the deadline of each task, which may not always be available.
b. Performance: EDF can lead to optimal performance if the deadlines are accurate but may lead to poor
performance if deadlines are not set appropriately.
6. Least Slack Time (LST)
a. Trade-offs: LST is a dynamic scheduling algorithm, meaning it requires periodic rescheduling of tasks
to determine their priorities. This can result in higher overhead compared to static scheduling
algorithms. LST is non-preemptive, meaning once a task starts executing, it is not interrupted until
completion. This can result in longer response times compared to preemptive algorithms.
b. Performance: LST provides good average-case response time performance and can handle non-
periodic tasks efficiently. However, LST may not guarantee all tasks meet their deadlines, and requires
periodic rescheduling, increasing overhead.
7. Rate Monotonic
a. Trade-offs: RM is a static priority scheduling algorithm, meaning priorities are assigned to tasks based
on their period. This makes it easy to implement and analyse but can result in lower efficiency for non-
periodic [Link] is pre-emptive, which can result in higher overhead due to frequent context
switches.
b. Performance: RM provides guarantees on response time and deadline meeting for periodic tasks. This
makes it a suitable algorithm for safety-critical systems with hard real-time requirements. However,
RM may not be efficient for systems with a large number of tasks, and low priority tasks may face
starvation.
The trade-offs and performance may depend on specific system requirements and constraints.
Choice of algorithms for different scenarios:
1. Real-time systems with hard deadlines and fixed priority levels: Rate Monotonic (RM) or Deadline
Monotonic (DM) scheduling algorithms are recommended due to their ability to guarantee deadlines for
high-priority tasks
2. Real-time systems with dynamic priorities: Earliest Deadline First (EDF) or Least Slack Time (LST)
scheduling algorithms are recommended. EDF is useful when the deadlines of tasks are known in advance,
while LST is useful when the deadlines of tasks are not known in advance.

[Link] Electrical and Computer Experiences 1 (1) (2023) 29-35

© Manasa R and Divya Mabbu 34

3. Interactive systems: Shortest Job First (SJF) or Priority Scheduling algorithms are recommended. SJF gives
priority to shorter jobs, while Priority Scheduling allows for different priorities to be assigned to different
jobs.
4. Batch processing systems: First-Come, First-Serve (FCFS) or Round Robin (RR) scheduling algorithms are
recommended. FCFS executes jobs in the order they arrive, while RR executes jobs in a round-robin
fashion.
5. Real-time systems with sporadic or aperiodic tasks: EDF is recommended due to its ability to handle such
tasks efficiently.

CONCLUSION
The most important conclusions from our analysis and comparison are that Rate Monotonic (RM) is
suitable for systems with hard real-time requirements and a small number of periodic tasks, while Least Slack
Time (LST) provides good average-case response time performance. Earliest Deadline First (EDF) can handle
both periodic and aperiodic tasks but may result in higher overhead due to frequent rescheduling. Priority
scheduling is suitable for systems with a small number of tasks but may result in lower efficiency. Shortest Job
First (SJF) and First Come First Served (FCFS) are suitable for systems with a mix of short and long running
tasks but may not be the best choice for systems with hard real-time requirements. Round Robin (RR) can
handle both periodic and aperiodic tasks but may result in longer response times. This can be extended to
Cloud Computing [7-15] using Machine Learning [16] approaches.

Author declaration
Author contributions and responsibilities
The authors made major contributions to the conception and design of the study. The authors took
responsibility for data analysis, interpretation and discussion of results. The authors read and approved the
final manuscript.
Funding
This research did not receive external funding.
Availability of data and materials
All data is available from the author.
Competing interests
The authors declare no competing interests.

REFERENCES
[1] Ngo, V. T., Nguyen, H. H., Truong, H. N., & Nguyen, N. D. (2019). A comparative study of scheduling algorithms in real-time systems.
Journal of Science and Technology, 57(1B), 84-96.
[2] Sharma, V., Dhiman, G., & Singh, M. (2020). Performance comparison of EDF and DM scheduling algorithms for distributed real-
time systems. Journal of Ambient Intelligence and Humanized Computing, 11(11), 5085-5101.
[3] Chen, X., Li, Y., Li, R., & Li, P. (2017). Performance comparison of scheduling algorithms for real-time systems. Journal of Applied
Mathematics, 2017, 1-14.
[4] Li, Y., Chen, X., & Li, P. (2018). A comparative study of real-time scheduling algorithms for mixed-criticality systems. IEEE Access,
6, 4233-4241.
[5] Pinto, J. A., Sousa, E., & Tovar, E. (2016). Performance comparison of scheduling algorithms for sporadic tasks in real-time systems.
IEEE Access, 4, 580-592.
[6] Tovar, E., Sousa, E., & Pinto, J. A. (2015). Comparative analysis of real-time scheduling algorithms in a heterogeneous
multiprocessor platform. Journal of Systems Architecture, 61(10), 567-584.
[7] Supreeth S and K. K. Patil, “Virtual Machine Scheduling Strategies in Cloud Computing- A Review,” Zenodo, Sep. 2019, doi:
10.5281/ZENODO.6144561.
[8] R. R, Supreeth S, Ramya R, G. P. M, and Chaitra Lakshmi L, “Password Processing Scheme using Enhanced Visual Cryptography and
OCR in Hybrid Cloud Environment,” Zenodo, May 2019, doi: 10.5281/ZENODO.7027753.
[9] P Sarika, S. Kumari, S. M, S. Singh, and Supreeth S, “FRAMEWORK FOR DATA SECURITY FROM SQL INJECTION IN CLOUD
COMPUTING,” Zenodo, Aug. 2022, doi: 10.5281/ZENODO.7035685.
[10] S. Supreeth, Kirankumari Patil, “VM Scheduling for Efficient Dynamically Migrated Virtual Machines (VMS-EDMVM) in Cloud
Computing Environment,” KSII Transactions on Internet and Information Systems, vol. 16, no. 6. Korean Society for Internet
Information (KSII), Jun. 30, 2022. doi: 10.3837/tiis.2022.06.007.
[11] G. Shruthi, Monica R. Mundada, B. J. Sowmya, S. Supreeth, "Mayfly Taylor Optimisation-Based Scheduling Algorithm with Deep
Reinforcement Learning for Dynamic Scheduling in Fog-Cloud Computing", Applied Computational Intelligence and Soft
Computing, vol. 2022, Article ID 2131699, 17 pages, 2022. [Link]

[Link] Electrical and Computer Experiences 1 (1) (2023) 29-35

© Manasa R and Divya Mabbu 35

[12] S. G., M. R. Mundada, and S. S., “The Resource Allocation Using Weighted Greedy Knapsack Based Algorithm in an Educational Fog
Computing Environment”, Int. J. Emerg. Technol. Learn., vol. 17, no. 18, pp. pp. 261–274, Sep. 2022.
[13] Supreeth, S., Raja Rajeshwari, M.M. (2018). Using Map-Reduce for Image Analysis in Cloud Environment. In: Guru, D., Vasudev, T.,
Chethan, H., Kumar, Y. (eds) Proceedings of International Conference on Cognition and Recognition. Lecture Notes in Networks
and Systems, vol 14. Springer, Singapore. [Link]
[14] S. Supreeth, Kirankumari Patil, Shantala Devi Patil, S. Rohith, Y. Vishwanath, K. S. Venkatesh Prasad, "An Efficient Policy-Based
Scheduling and Allocation of Virtual Machines in Cloud Computing Environment", Journal of Electrical and Computer Engineering,
vol. 2022, Article ID 5889948, 12 pages, 2022. [Link]
[15] S. Supreeth, K. Patil, S. D. Patil and S. Rohith, "Comparative approach for VM Scheduling using Modified Particle Swarm
Optimization and Genetic Algorithm in Cloud Computing," 2022 IEEE International Conference on Data Science and Information
System (ICDSIS), Hassan, India, 2022, pp. 1-6, doi: 10.1109/ICDSIS55133.2022.9915907.
[16] Gaurav Dhingra, Supreeth S, N. K. R, Amruthashree R V, and Eshitha D, “Traffic Management using Convolution Neural Network,”
Zenodo, May 2019, doi: 10.5281/ZENODO.7027893.

[Link] Electrical and Computer Experiences 1 (1) (2023) 29-35