University of Illinois Urbana-Champaign

The delay composition theorem on pipeline systems with non-preemptive priority varying scheduling algorithms

Lu, Yi

Content Files
LU-THESIS-2015.pdf

Permalink

https://hdl.handle.net/2142/78658

Description

Title
The delay composition theorem on pipeline systems with non-preemptive priority varying scheduling algorithms
Author(s)
Lu, Yi
Issue Date
2015-04-23
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2015-07-22T22:33:49Z
Keyword(s)
  • real-time scheduling
  • pipeline systems
Abstract
The delay composition theorem, by taking into account the fact that pipeline systems allow concurrent execution, expresses the upper-bounded delay of a real-time task as the sum of two summations, where the first one is linear to the number of stages of the system, and the second one is linear to the number of tasks running on the system. The schedulability analysis based on delay composition theorem performs better than traditional analysis techniques. In this paper we break one assumption that has been hold by previous works on delay composition theorem, namely each task has the same relative priority across all stages. We extend the theorem to pipeline systems running non-preemptive scheduling algorithm which may assign different relative priorities to a task on different stages.
Graduation Semester
2015-5
Type of Resource
text
Permalink
http://hdl.handle.net/2142/78658
Copyright and License Information
Copyright 2015 Yi Lu

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science