A Non-Preemptive Scheduling Algorithm for Soft Real-Time Systems

Description:

This article discusses a non-preemptive scheduling algorithm for soft real-time systems.

Creator(s):
Creation Date: April 10, 2006
Partner(s):
UNT College of Engineering
Collection(s):
UNT Scholarly Works
Usage:
Total Uses: 212
Past 30 days: 11
Yesterday: 2
Creator (Author):
Li, Wenming

University of North Texas

Creator (Author):
Kavi, Krishna M.

University of North Texas

Creator (Author):
Akl, Robert G.

University of North Texas

Publisher Info:
Publisher Name: Elsevier Science Ltd.
Place of Publication: [Amsterdam, Netherlands]
Date(s):
  • Creation: April 10, 2006
Description:

This article discusses a non-preemptive scheduling algorithm for soft real-time systems.

Degree:
Note:

Abstract: Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. The goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We present results comparing gEDF with other real-time algorithms including EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.

Physical Description:

18 p.

Language(s):
Subject(s):
Keyword(s): soft real-time systems | non-preemptive real-time scheduling | Earliest Deadline First | Shortest Job First | best-effort scheduling | group-EDF
Source: Computers and Electrical Engineering, 2006. Amsterdam: Elsevier Science Ltd., pp. 1-18
Partner:
UNT College of Engineering
Collection:
UNT Scholarly Works
Identifier:
  • ARK: ark:/67531/metadc30824
Resource Type: Article
Format: Text
Rights:
Access: Public
Citation:
Publication Title: Computers and Electrical Engineering
Volume: 33
Issue: 1
Page Start: 1
Page End: 18
Peer Reviewed: Yes