View in EDS

Exact speedup factors for linear-time schedulability tests for fixed-priority preemptive and non-preemptive scheduling.

Saved in:
Bibliographic Details
Title: Exact speedup factors for linear-time schedulability tests for fixed-priority preemptive and non-preemptive scheduling.
Authors: von der Brüggen, Georg1, Jian-Jia Chen1 jian-jia.chen@cs.uni-dortmund.de, Davis, Robert I.2,3, Wen-Hung Huang1
Source: Information Processing Letters. Jan2017, Vol. 117, p1-5. 5p.
Subjects: Algorithms, Scheduling, Time management, High performance processors, Linear time invariant systems
Abstract: In this paper, we investigate the quality of several linear-time schedulability tests for preemptive and non-preemptive fixed-priority scheduling of uniprocessor systems. The metric used to assess the quality of these tests is the resource augmentation bound commonly known as the processor speedup factor. The speedup factor of a schedulability test corresponds to the smallest factor by which the processing speed of a uniprocessor needs to be increased such that any task set that is feasible under an optimal preemptive (non-preemptive) work-conserving scheduling algorithm is guaranteed to be schedulable with preemptive (non-preemptive) fixed priority scheduling if this scheduling test is used, assuming an appropriate priority assignment. We show the surprising result that the exact speedup factors for Deadline Monotonic (DM) priority assignment combined with sufficient linear-time schedulability tests for implicit-, constrained-, and arbitrary-deadline task sets are the same as those obtained for optimal priority assignment policies combined with exact schedulability tests. Thus in terms of the speedup-factors required, there is no penalty in using DM priority assignment and simple linear schedulability tests. [ABSTRACT FROM AUTHOR]
Copyright of Information Processing Letters is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 118288768
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Exact speedup factors for linear-time schedulability tests for fixed-priority preemptive and non-preemptive scheduling.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22von+der+Brüggen%2C+Georg%22">von der Brüggen, Georg</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Jian-Jia+Chen%22">Jian-Jia Chen</searchLink><relatesTo>1</relatesTo><i> jian-jia.chen@cs.uni-dortmund.de</i><br /><searchLink fieldCode="AR" term="%22Davis%2C+Robert+I%2E%22">Davis, Robert I.</searchLink><relatesTo>2,3</relatesTo><br /><searchLink fieldCode="AR" term="%22Wen-Hung+Huang%22">Wen-Hung Huang</searchLink><relatesTo>1</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Information+Processing+Letters%22">Information Processing Letters</searchLink>. Jan2017, Vol. 117, p1-5. 5p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Scheduling%22">Scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Time+management%22">Time management</searchLink><br /><searchLink fieldCode="DE" term="%22High+performance+processors%22">High performance processors</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+time+invariant+systems%22">Linear time invariant systems</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In this paper, we investigate the quality of several linear-time schedulability tests for preemptive and non-preemptive fixed-priority scheduling of uniprocessor systems. The metric used to assess the quality of these tests is the resource augmentation bound commonly known as the processor speedup factor. The speedup factor of a schedulability test corresponds to the smallest factor by which the processing speed of a uniprocessor needs to be increased such that any task set that is feasible under an optimal preemptive (non-preemptive) work-conserving scheduling algorithm is guaranteed to be schedulable with preemptive (non-preemptive) fixed priority scheduling if this scheduling test is used, assuming an appropriate priority assignment. We show the surprising result that the exact speedup factors for Deadline Monotonic (DM) priority assignment combined with sufficient linear-time schedulability tests for implicit-, constrained-, and arbitrary-deadline task sets are the same as those obtained for optimal priority assignment policies combined with exact schedulability tests. Thus in terms of the speedup-factors required, there is no penalty in using DM priority assignment and simple linear schedulability tests. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Information Processing Letters is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=118288768
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ipl.2016.08.001
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 5
        StartPage: 1
    Subjects:
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Scheduling
        Type: general
      – SubjectFull: Time management
        Type: general
      – SubjectFull: High performance processors
        Type: general
      – SubjectFull: Linear time invariant systems
        Type: general
    Titles:
      – TitleFull: Exact speedup factors for linear-time schedulability tests for fixed-priority preemptive and non-preemptive scheduling.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: von der Brüggen, Georg
      – PersonEntity:
          Name:
            NameFull: Jian-Jia Chen
      – PersonEntity:
          Name:
            NameFull: Davis, Robert I.
      – PersonEntity:
          Name:
            NameFull: Wen-Hung Huang
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: Jan2017
              Type: published
              Y: 2017
          Identifiers:
            – Type: issn-print
              Value: 00200190
          Numbering:
            – Type: volume
              Value: 117
          Titles:
            – TitleFull: Information Processing Letters
              Type: main
ResultId 1