Welcome to Nitin Joshi's Pages.
This page simply introduces the project to the visitors. The detailed implementation and technical report can be downloaded from
Abstract:
With the burgeoning demand of embedded systems with extensive time sensitive processing throughout the globe, the research communities from the computing industry are continuously raising the bars by introducing better and faster process scheduling algorithms.
In this paper we try to compare the performances of one of the best known traditional scheduling algorithms such as EDF, LLF with some of the most recent works in the field of multi-processor, non-preemptive scheduling algorithms like Algorithm C and Algorithm D.
Simulator designed and implemented by:
Nitin Joshi
Department of Computer Science
Lamar University
Beaumont, TX
Introduction:
In the study of real-time embedded systems, schedulability problem remains the most researched problem and over the course of several decades many pioneering researchers have presented scheduling algorithms such as EDF and LLF that changed the way scheduling analysis of task sets is done. These scheduling algorithms aim to provide optimal feasible schedules of task sets under various constraints. Despite such a radical increase in study of such algorithms, the schedulability analysis of non-preemptive tasks has received less attention in the real-time embedded research community.
There are many benefits of using non-preemptive tasks over preemptive tasks on multiprocessor platform. This is primarily because in non-preemptive scheduling the task instance runs until its computation time on the same processor where as in preemptive scheduling task migration creates a lot of computational overheads and makes prediction difficult [ACR2011].
In this paper we prove by simulated implementation that despite EDF with idle task being an optimal method for uniprocessor platform [GMR1995], EDF is no longer optimal for multiprocessor platform. We show this by providing a feasible schedule by algorithm C described in [ACGR2010] and Algorithm D [ACR2013] for all task sets for which EDF failed to provide a feasible schedule. The tabulated result in Section III shows the feasibility of task sets by different scheduling methods.
The aim of this paper is to show that although the scheduling problem is NP-complete, the Algorithms C and D were still able to find a feasible schedule for most single-instance, non-preemptive and independent task sets. In the next section we provide the implementation details for the simulation tool used for the analysis.
Authors and Contributors:
Ştefan Andrei
Lamar University
Department of Computer Science
Beaumont, TX, USA
Albert M.K. Cheng
University of Houston
Computer Science Department
Houston, TX, USA
Vlad Rǎdulescu
Cuza University of Iaşi
Department of Computer Science
Iaşi, Romania
Nitin Joshi
Lamar University
Department of Computer Science
Beaumont, TX, USA
Support or Contact
Having trouble with Pages? Check out the documentation at http://help.github.com/pages or contact support@github.com and we’ll help you sort it out.