Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Slack-based multiprocessor scheduling of aperiodic real-time tasks
Ansvarig organisation
2011 (Engelska)Ingår i: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 47, nr 6, s. 618-638Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We provide a constant time schedulability test and priority assignment algorithm for an on-line multiprocessor server handling aperiodic tasks. The so called Dhall's effect is avoided by dividing tasks in two priority classes based on their utilization: heavy and light. The improvement in this paper is due to assigning priority of light tasks based on slack-not on deadlines. We prove that if the load on the multiprocessor stays below (3 - √5)/2 ≈ 38.197%, the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. This is better than the current state-of-the-art algorithm where the priorities of light tasks are based on deadlines (the corresponding bound is in that case 35.425%). The bound (3 - √5)/ 2 can be improved if the number of processors m is known. There is a formula for the sharp bound Uthreshold(m) = 3m - 2 - √5m 2 - 8m + 4/2(m - 1), which converges to (3 - √5)/2 from above as m→∞. For m≥3, the bound is higher (i.e., better) than the corresponding sharp bound for the state-of-the-art algorithm where the priorities of light tasks are based on deadlines. A simulation study also indicates that when m>3 the best effort behavior of the priority assignment scheme suggested here is better than that of the traditional scheme where priorities are based on deadlines.

Ort, förlag, år, upplaga, sidor
Springer , 2011. Vol. 47, nr 6, s. 618-638
Nyckelord [en]
Aperiodic tasks, Global multiprocessor scheduling, Real-time scheduling, Slack-based priorities, Static priorities
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:bth-7377DOI: 10.1007/s11241-011-9134-9ISI: 000295793000004Lokalt ID: oai:bth.se:forskinfo414CF03F21E97B09C1257979003474CFOAI: oai:DiVA.org:bth-7377DiVA, id: diva2:834985
Tillgänglig från: 2012-09-18 Skapad: 2012-01-02 Senast uppdaterad: 2018-01-11Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Lundberg, Lars

Sök vidare i DiVA

Av författaren/redaktören
Lundberg, Lars
I samma tidskrift
Real-time systems
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 6 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf