Cover Image

A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate

The evergreen Earliest Deadline First algorithm is an excellent dynamic real time job scheduler under normal System Load. However, its’ performance in terms of deadline meeting rate is simply undeterministic under overload condition. This thesis presents a new algorithm in scheduling Soft Real Time...

Full description

Saved in:
Bibliographic Details
Main Author: Zahereel Ishwar, Abdul Khalib
Format: Thesis
Language:English
Published: Universiti Malaysia Perlis (UniMAP) 2014
Subjects:
Earliest Deadline First (EDF)
Group scheduling
GutEDF
Soft real time
Online Access:http://dspace.unimap.edu.my:80/dspace/handle/123456789/33154
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.unimap-33154
record_format dspace
spelling my.unimap-331542014-03-27T03:23:10Z A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate Zahereel Ishwar, Abdul Khalib Earliest Deadline First (EDF) Group scheduling GutEDF Soft real time The evergreen Earliest Deadline First algorithm is an excellent dynamic real time job scheduler under normal System Load. However, its’ performance in terms of deadline meeting rate is simply undeterministic under overload condition. This thesis presents a new algorithm in scheduling Soft Real Time Jobs by means of Dynamic Non Preemptive scheme, which is capable of maintaining excellent deadline meeting rate during normal System Load, while producing much better deadline meeting rate during overload. In a soft real time system it is critical that an algorithm is capable of maintaining acceptable performance during overload, because soft real time tolerates some level of missing deadline at the benefit of efficiency in its own parameter of interest. Many other works has been done to cater the issue of undeterministic behavior of Earliest Deadline First during overload. However, most of them uses preemptive scheme, requires overload detection and tailored to specific application. The proposed algorithm, which group jobs using purely dynamic parameters in its grouping formula is by itself novel. Next, the jobs in the group are schedule by another novel approach which is identical to shortest job first, but comes with a minimum of two extra benefits. To analyze the performance of the developed algorithm and compares it to other algorithms, a non preemptive, non resource constraint soft real time simulation model is developed on the OMNeT++ discrete event simulator. The Real Time Scheduling Simulator is rather moderate in size but is serve the simulation purpose. The Real Time Scheduling simulation model is then validated based on its specification. As for verification, the simulation model is tested against known cases to ensure correctness of operation and results achieved is found to be identical to theory. The analysis of the algorithm has been conducted by means of excessive simulation approach, where each simulation runs has been repeated with different seeds. The performance of the algorithms has been experimented with combinations of parameters which compose of Relative Deadline Size, Deadline Tolerance and Execution Time. Simulations results shows that, the developed algorithm, named gutEDF always achieved much better performance in terms deadline meeting rate compared to Earliest Deadline First and its immediate predecessor known as Group Earliest Deadline First, under different combinations of input parameters. Not only that, the algorithm is also evaluated in terms of Average Response Time, which is a Soft Real Time performance parameter for some application and results collected shows that gutEDF always achieved much better Average Response Time. 2014-03-27T03:23:09Z 2014-03-27T03:23:09Z 2013 Thesis http://dspace.unimap.edu.my:80/dspace/handle/123456789/33154 en Universiti Malaysia Perlis (UniMAP) School of Computer and Communication Engineering
institution Universiti Malaysia Perlis
building UniMAP Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Malaysia Perlis
content_source UniMAP Library Digital Repository
url_provider http://dspace.unimap.edu.my/
language English
topic Earliest Deadline First (EDF)
Group scheduling
GutEDF
Soft real time
spellingShingle Earliest Deadline First (EDF)
Group scheduling
GutEDF
Soft real time
Zahereel Ishwar, Abdul Khalib
A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate
description The evergreen Earliest Deadline First algorithm is an excellent dynamic real time job scheduler under normal System Load. However, its’ performance in terms of deadline meeting rate is simply undeterministic under overload condition. This thesis presents a new algorithm in scheduling Soft Real Time Jobs by means of Dynamic Non Preemptive scheme, which is capable of maintaining excellent deadline meeting rate during normal System Load, while producing much better deadline meeting rate during overload. In a soft real time system it is critical that an algorithm is capable of maintaining acceptable performance during overload, because soft real time tolerates some level of missing deadline at the benefit of efficiency in its own parameter of interest. Many other works has been done to cater the issue of undeterministic behavior of Earliest Deadline First during overload. However, most of them uses preemptive scheme, requires overload detection and tailored to specific application. The proposed algorithm, which group jobs using purely dynamic parameters in its grouping formula is by itself novel. Next, the jobs in the group are schedule by another novel approach which is identical to shortest job first, but comes with a minimum of two extra benefits. To analyze the performance of the developed algorithm and compares it to other algorithms, a non preemptive, non resource constraint soft real time simulation model is developed on the OMNeT++ discrete event simulator. The Real Time Scheduling Simulator is rather moderate in size but is serve the simulation purpose. The Real Time Scheduling simulation model is then validated based on its specification. As for verification, the simulation model is tested against known cases to ensure correctness of operation and results achieved is found to be identical to theory. The analysis of the algorithm has been conducted by means of excessive simulation approach, where each simulation runs has been repeated with different seeds. The performance of the algorithms has been experimented with combinations of parameters which compose of Relative Deadline Size, Deadline Tolerance and Execution Time. Simulations results shows that, the developed algorithm, named gutEDF always achieved much better performance in terms deadline meeting rate compared to Earliest Deadline First and its immediate predecessor known as Group Earliest Deadline First, under different combinations of input parameters. Not only that, the algorithm is also evaluated in terms of Average Response Time, which is a Soft Real Time performance parameter for some application and results collected shows that gutEDF always achieved much better Average Response Time.
format Thesis
author Zahereel Ishwar, Abdul Khalib
author_facet Zahereel Ishwar, Abdul Khalib
author_sort Zahereel Ishwar, Abdul Khalib
title A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate
title_short A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate
title_full A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate
title_fullStr A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate
title_full_unstemmed A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate
title_sort dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate
publisher Universiti Malaysia Perlis (UniMAP)
publishDate 2014
url http://dspace.unimap.edu.my:80/dspace/handle/123456789/33154
_version_ 1643797083664154624
score 13.222552

Similar Items