A New Strategy for Improving the Effectiveness of Resource Reclaiming Algorithms in Multiprocessor Real-Time Systems

Indranil Gupta, G. Manimaran, C. Siva Ram Murthy

Research output: Contribution to journalArticle

Abstract

The scheduling of tasks in multiprocessor real-time systems has attracted the attention of many researchers in the recent past. Tasks in such systems have deadlines to be met, and most real-time scheduling algorithms use worst case computation times to schedule these tasks. Many resources will be left unused if the tasks are dispatched purely based on the schedule produced by these scheduling algorithms, since most of the tasks will take less time to execute than their respective worst case computation times. Resource reclaiming refers to the problem of reclaiming the resources left unused by a real-time task when it takes less time to execute than its worst case computation time. Several resource reclaiming algorithms such as Basic, Early Start, and RV algorithms have been proposed in the recent past. But these pay very little attention to the strategy by which the scheduler can better utilize the benefits of reclaimed resources. In this paper, we propose an esti- mation strategy which can be used along with a particular class of resource reclaiming algorithms (such as Early Start and RV algorithms) by which the scheduler can estimate the minimum time by which any scheduled but unexecuted task will start or finish early, based solely on the start and finish times of tasks that have started or finished execution. We then propose an approach by which dynamic scheduling strategies, which append or reschedule new tasks into the schedules, can use this estimation strategy to achieve better schedulability. Extensive simulation studies are carried out to investigate the effectiveness of this estimation strategy versus its cost.

Original languageEnglish (US)
Pages (from-to)113-133
Number of pages21
JournalJournal of Parallel and Distributed Computing
Volume60
Issue number1
DOIs
StatePublished - Jan 2000
Externally publishedYes

    Fingerprint

Keywords

  • Dynamic scheduling
  • Multiprocessor real-time systems
  • Precedence constraints
  • Resource constraints
  • Resource reclaiming

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this