LSTF: A new scheduling policy for complex real-time tasks in multiple processor systems

Bo Chao Cheng; Alexander D. Stoyenko; Thomas J. Marlowe; Sanjoy K. Baruah

doi:10.1016/S0005-1098(96)00245-2

LSTF: A new scheduling policy for complex real-time tasks in multiple processor systems

Bo Chao Cheng
, Alexander D. Stoyenko
, Thomas J. Marlowe
, Sanjoy K. Baruah

Department of Computer Science & Engineering

Research output: Contribution to journal › Article › peer-review

16 Scopus citations

Abstract

We propose a new algorithm, least space-time first (LSTF), for dealing with the general complex-task-multiple-processor model. The results of the proof and simulation shown that LSTF outperforms other established heuristic algorithms (such as earliest-deadline-first) in the sense that it minimizes the maximum tardiness of a set of tasks. LSTF can gracefully incorporate some realistic overhead assumptions, such as context switch.

Original language	English
Pages (from-to)	921-926
Number of pages	6
Journal	Automatica
Volume	33
Issue number	5
DOIs	https://doi.org/10.1016/S0005-1098(96)00245-2
State	Published - May 1997

Keywords

Graphs
Parallel processors
Performance analysis
Real-time tasks
Scheduling algorithms

Access to Document

10.1016/S0005-1098(96)00245-2

Cite this

@article{f9d3e8f3525743dba89aeebc1fcc9ddb,

title = "LSTF: A new scheduling policy for complex real-time tasks in multiple processor systems",

abstract = "We propose a new algorithm, least space-time first (LSTF), for dealing with the general complex-task-multiple-processor model. The results of the proof and simulation shown that LSTF outperforms other established heuristic algorithms (such as earliest-deadline-first) in the sense that it minimizes the maximum tardiness of a set of tasks. LSTF can gracefully incorporate some realistic overhead assumptions, such as context switch.",

keywords = "Graphs, Parallel processors, Performance analysis, Real-time tasks, Scheduling algorithms",

author = "Cheng, \{Bo Chao\} and Stoyenko, \{Alexander D.\} and Marlowe, \{Thomas J.\} and Baruah, \{Sanjoy K.\}",

year = "1997",

month = may,

doi = "10.1016/S0005-1098(96)00245-2",

language = "English",

volume = "33",

pages = "921--926",

journal = "Automatica",

issn = "0005-1098",

number = "5",

}

TY - JOUR

T1 - LSTF

T2 - A new scheduling policy for complex real-time tasks in multiple processor systems

AU - Cheng, Bo Chao

AU - Stoyenko, Alexander D.

AU - Marlowe, Thomas J.

AU - Baruah, Sanjoy K.

PY - 1997/5

Y1 - 1997/5

N2 - We propose a new algorithm, least space-time first (LSTF), for dealing with the general complex-task-multiple-processor model. The results of the proof and simulation shown that LSTF outperforms other established heuristic algorithms (such as earliest-deadline-first) in the sense that it minimizes the maximum tardiness of a set of tasks. LSTF can gracefully incorporate some realistic overhead assumptions, such as context switch.

AB - We propose a new algorithm, least space-time first (LSTF), for dealing with the general complex-task-multiple-processor model. The results of the proof and simulation shown that LSTF outperforms other established heuristic algorithms (such as earliest-deadline-first) in the sense that it minimizes the maximum tardiness of a set of tasks. LSTF can gracefully incorporate some realistic overhead assumptions, such as context switch.

KW - Graphs

KW - Parallel processors

KW - Performance analysis

KW - Real-time tasks

KW - Scheduling algorithms

UR - https://www.scopus.com/pages/publications/0031130974

U2 - 10.1016/S0005-1098(96)00245-2

DO - 10.1016/S0005-1098(96)00245-2

M3 - Article

AN - SCOPUS:0031130974

SN - 0005-1098

VL - 33

SP - 921

EP - 926

JO - Automatica

JF - Automatica

IS - 5

ER -

LSTF: A new scheduling policy for complex real-time tasks in multiple processor systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this