Browse

A Safe Stochastic Analysis with Relaxed Limitations on the Periodic Task Model

DC Field Value Language
dc.contributor.authorKim, Kanghee-
dc.contributor.authorLee, Chang-Gun-
dc.date.accessioned2009-10-05T10:27:35Z-
dc.date.available2009-10-05T10:27:35Z-
dc.date.issued2009-05-
dc.identifier.citationIEEE transactions on computers, 58(5):634-647, 2009.en
dc.identifier.issn0018-9340-
dc.identifier.urihttps://hdl.handle.net/10371/10148-
dc.description.abstractThis paper proposes a safe stochastic analysis for fixed-priority scheduling, which is applicable to a broader spectrum of periodic tasks than the ones analyzable by any of the existing techniques. The proposed analysis can find a safe upper-bound of deadline miss probability for periodic tasks with 1) arbitrary execution time distributions, 2) varying interrelease times with the period as the minimum, and 3) the maximum utilization factor U^{max} that can be greater than 1. One challenge for this is that the release times of tasks are not known a priori because we are not limiting the interrelease times of each task to a constant, i.e., the period. In such a situation, the relative phases of task instances at run time can be arbitrary. Thus, we need to consider all possible phase combinations among jobs to find the worst case deadline miss probability, which is not tractable. To handle this difficulty, we first derive the worst case phase combination for harmonic task sets. Then, we present a safe way to transform a nonharmonic task set to a harmonic task set such that the deadline miss probabilities obtained with the worst case phase combination for the transformed harmonic task set are guaranteed to be worse than those for the original nonharmonic task set with all possible phase combinations. Therefore, the worst case deadline miss probabilities of the transformed harmonic tasks can be used as safe upper-bounds of deadline miss probabilities of the original nonharmonic tasks. Through experiments, we show that the safe upper-bound computed by the proposed analysis is tight enough for practical uses.en
dc.language.isoenen
dc.publisherIEEE Computer Societyen
dc.subjectStochastic Analysisen
dc.subjectPeriodic Task Modelen
dc.titleA Safe Stochastic Analysis with Relaxed Limitations on the Periodic Task Modelen
dc.typeArticleen
dc.contributor.AlternativeAuthor김강희-
dc.contributor.AlternativeAuthor이창건-
dc.identifier.doi10.1109/TC.2008.208-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Computer Science and Engineering (컴퓨터공학부)Journal Papers (저널논문_컴퓨터공학부)
Files in This Item:
There are no files associated with this item.
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse