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
Subjects:	Earliest Deadline First (EDF) Group scheduling GutEDF Soft real time
Online Access:	http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/33154/1/Page%201-24.pdf http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/33154/2/Full%20text.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-unimap-33154
record_format	uketd_dc
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 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. Universiti Malaysia Perlis (UniMAP) 2013 Thesis en http://dspace.unimap.edu.my:80/dspace/handle/123456789/33154 http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/33154/1/Page%201-24.pdf a210cb129e2e6e37cc9814d69ba65315 http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/33154/2/Full%20text.pdf 45c811d22674b179c6894e1f9b90ab2c http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/33154/3/license.txt 8a4605be74aa9ea9d79846c1fba20a33 Earliest Deadline First (EDF) Group scheduling GutEDF Soft real time School of Computer and Communication Engineering
institution	Universiti Malaysia Perlis
collection	UniMAP Institutional Repository
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
granting_institution	Universiti Malaysia Perlis (UniMAP)
granting_department	School of Computer and Communication Engineering
url	http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/33154/1/Page%201-24.pdf http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/33154/2/Full%20text.pdf
_version_	1747836805601820672

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

Similar Items