Header menu link for other important links
X
Dynamic scheduling of parallelizable tasks and resource reclaiming in real-time multiprocessor systems
Published in IEEE, Piscataway, NJ, United States
1997
Pages: 206 - 211
Abstract
Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met despite the presence of faults. In this paper, we propose a new dynamic non-preemptive scheduling algorithm for a relatively new task model called parallelizable task model where real-time tasks can be executed concurrently on multiple processors. We use this parallelism in tasks to meet their deadlines and thus obtain better processor utilization compared to non-parallelizable task scheduling algorithms. We assume that tasks are aperiodic. Further, each task is characterized by its deadline, resource requirements, and worst case computation time on p processors, where p is the degree of task parallelization. To study the effectiveness of our algorithm, we have conducted extensive simulation studies and compared its performance with the myopic scheduling algorithm. We found that the success ratio offered by our algorithm is always higher than the myopic algorithm for a wide variety of task parameters. Also, we propose a resource reclaiming algorithm to reclaim resources from parallelizable real-time tasks when their actual computation times are less than their worst case computation times. Our parallelizable task scheduling together with its associated reclaiming offers the best guarantee ratio compared to the other algorithmic combinations.
About the journal
JournalData powered by TypesetProceedings of the International Conference on High Performance Computing, HiPC
PublisherData powered by TypesetIEEE, Piscataway, NJ, United States
Open AccessNo
Concepts (10)
  •  related image
    Computational complexity
  •  related image
    Computer architecture
  •  related image
    Parallel algorithms
  •  related image
    Real time systems
  •  related image
    Response time (computer systems)
  •  related image
    Storage allocation (computer)
  •  related image
    Dynamic scheduling
  •  related image
    PARALLELIZABLE REAL TIME TASKS
  •  related image
    RESOURCE RECLAIMING
  •  related image
    Multiprocessing systems