Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems Article Swipe

PDF

Jian-Jia Chen , Georg von der Brüggen , Niklas Ueter ·

YOU? · · 2018 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1802.10376

The sporadic task model is often used to analyze recurrent execution of identical tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of $3-1/M$ against any optimal scheduling algorithms, where $M$ is the number of identical processors, and prove that this bound is asymptotically tight.

Related Topics

Concepts

Computer science Scheduling (production processes) Task (project management) Distributed computing Mathematics Mathematical optimization Economics Management

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/1802.10376
PDF: https://arxiv.org/pdf/1802.10376
OA Status: green
Cited By: 2
References: 4
Related Works: 10
OpenAlex ID: https://openalex.org/W2787977648

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2787977648

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.1802.10376

Digital Object Identifier
Title: Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2018

Year of publication
Publication date: 2018-02-28

Full publication date if available
Authors: Jian-Jia Chen, Georg von der Brüggen, Niklas Ueter

List of authors in order
Landing page: https://arxiv.org/abs/1802.10376

Publisher landing page
PDF URL: https://arxiv.org/pdf/1802.10376

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/1802.10376

Direct OA link when available
Concepts: Computer science, Scheduling (production processes), Task (project management), Distributed computing, Mathematics, Mathematical optimization, Economics, Management

Top concepts (fields/topics) attached by OpenAlex
Cited by: 2

Total citation count in OpenAlex
Citations by year (recent): 2023: 1, 2022: 1

Per-year citation counts (last 5 years)
References (count): 4

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2787977648
doi	https://doi.org/10.48550/arxiv.1802.10376
ids.doi	https://doi.org/10.48550/arxiv.1802.10376
ids.mag	2787977648
ids.openalex	https://openalex.org/W2787977648
fwci
type	preprint
title	Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10933
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998000264167786
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1708
topics[0].subfield.display_name	Hardware and Architecture
topics[0].display_name	Real-Time Systems Scheduling
topics[1].id	https://openalex.org/T10772
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9955000281333923
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Distributed systems and fault tolerance
topics[2].id	https://openalex.org/T10904
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9865999817848206
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1708
topics[2].subfield.display_name	Hardware and Architecture
topics[2].display_name	Embedded Systems Design Techniques
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.617175817489624
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C206729178
concepts[1].level	2
concepts[1].score	0.5546483397483826
concepts[1].wikidata	https://www.wikidata.org/wiki/Q2271896
concepts[1].display_name	Scheduling (production processes)
concepts[2].id	https://openalex.org/C2780451532
concepts[2].level	2
concepts[2].score	0.49214500188827515
concepts[2].wikidata	https://www.wikidata.org/wiki/Q759676
concepts[2].display_name	Task (project management)
concepts[3].id	https://openalex.org/C120314980
concepts[3].level	1
concepts[3].score	0.3325779438018799
concepts[3].wikidata	https://www.wikidata.org/wiki/Q180634
concepts[3].display_name	Distributed computing
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.13379383087158203
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C126255220
concepts[5].level	1
concepts[5].score	0.12557339668273926
concepts[5].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[5].display_name	Mathematical optimization
concepts[6].id	https://openalex.org/C162324750
concepts[6].level	0
concepts[6].score	0.08031687140464783
concepts[6].wikidata	https://www.wikidata.org/wiki/Q8134
concepts[6].display_name	Economics
concepts[7].id	https://openalex.org/C187736073
concepts[7].level	1
concepts[7].score	0.0
concepts[7].wikidata	https://www.wikidata.org/wiki/Q2920921
concepts[7].display_name	Management
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.617175817489624
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/scheduling
keywords[1].score	0.5546483397483826
keywords[1].display_name	Scheduling (production processes)
keywords[2].id	https://openalex.org/keywords/task
keywords[2].score	0.49214500188827515
keywords[2].display_name	Task (project management)
keywords[3].id	https://openalex.org/keywords/distributed-computing
keywords[3].score	0.3325779438018799
keywords[3].display_name	Distributed computing
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.13379383087158203
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/mathematical-optimization
keywords[5].score	0.12557339668273926
keywords[5].display_name	Mathematical optimization
keywords[6].id	https://openalex.org/keywords/economics
keywords[6].score	0.08031687140464783
keywords[6].display_name	Economics
language	en
locations[0].id	pmh:oai:arXiv.org:1802.10376
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/1802.10376
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/1802.10376
locations[1].id	doi:10.48550/arxiv.1802.10376
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.1802.10376
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5000417436
authorships[0].author.orcid	https://orcid.org/0000-0001-8114-9760
authorships[0].author.display_name	Jian-Jia Chen
authorships[0].author_position	first
authorships[0].raw_author_name	Jian-Jia Chen
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5004024181
authorships[1].author.orcid	https://orcid.org/0000-0002-8137-3612
authorships[1].author.display_name	Georg von der Brüggen
authorships[1].author_position	middle
authorships[1].raw_author_name	Georg von der Brüggen
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5081007355
authorships[2].author.orcid	https://orcid.org/0000-0002-6722-4805
authorships[2].author.display_name	Niklas Ueter
authorships[2].author_position	last
authorships[2].raw_author_name	Niklas Ueter
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/1802.10376
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2018-03-06T00:00:00
display_name	Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10933
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998000264167786
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1708
primary_topic.subfield.display_name	Hardware and Architecture
primary_topic.display_name	Real-Time Systems Scheduling
related_works	https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2478288626, https://openalex.org/W4391913857, https://openalex.org/W2350741829
cited_by_count	2
counts_by_year[0].year	2023
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2022
counts_by_year[1].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:1802.10376
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/1802.10376
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/1802.10376
primary_location.id	pmh:oai:arXiv.org:1802.10376
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/1802.10376
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/1802.10376
publication_date	2018-02-28
publication_year	2018
referenced_works	https://openalex.org/W2231276398, https://openalex.org/W1828443364, https://openalex.org/W1976540538, https://openalex.org/W2531237237
referenced_works_count	4
abstract_inverted_index.A	17
abstract_inverted_index.a	75, 89, 112, 136
abstract_inverted_index.To	38
abstract_inverted_index.We	67, 128
abstract_inverted_index.an	21
abstract_inverted_index.be	46, 61, 115
abstract_inverted_index.in	14, 48
abstract_inverted_index.is	4, 148, 159
abstract_inverted_index.of	11, 24, 56, 91, 111, 122, 125, 139, 151
abstract_inverted_index.on	69, 74
abstract_inverted_index.to	7, 45, 50, 60
abstract_inverted_index.$M$	147
abstract_inverted_index.The	0
abstract_inverted_index.all	54, 57
abstract_inverted_index.and	87, 101, 154
abstract_inverted_index.any	81, 142
abstract_inverted_index.can	114
abstract_inverted_index.has	44, 135
abstract_inverted_index.job	65
abstract_inverted_index.the	33, 40, 64, 105, 108, 118, 123, 126, 149
abstract_inverted_index.(DM)	133
abstract_inverted_index.also	27
abstract_inverted_index.have	59
abstract_inverted_index.jobs	55, 124
abstract_inverted_index.sets	73
abstract_inverted_index.show	129
abstract_inverted_index.task	2, 19, 25, 72, 113
abstract_inverted_index.than	117
abstract_inverted_index.that	30, 130, 156
abstract_inverted_index.this	157
abstract_inverted_index.time	36, 99, 121
abstract_inverted_index.used	6
abstract_inverted_index.with	94
abstract_inverted_index.Under	104
abstract_inverted_index.bound	138, 158
abstract_inverted_index.focus	68
abstract_inverted_index.given	82
abstract_inverted_index.i.e.,	53
abstract_inverted_index.jobs,	29
abstract_inverted_index.model	3
abstract_inverted_index.often	5
abstract_inverted_index.prove	155
abstract_inverted_index.task.	127
abstract_inverted_index.tasks	13, 58
abstract_inverted_index.tests	93
abstract_inverted_index.their	98, 102
abstract_inverted_index.under	32, 80
abstract_inverted_index.where	146
abstract_inverted_index.arrive	31
abstract_inverted_index.before	63
abstract_inverted_index.called	28
abstract_inverted_index.ensure	39
abstract_inverted_index.global	83, 131
abstract_inverted_index.longer	116
abstract_inverted_index.number	150
abstract_inverted_index.series	90
abstract_inverted_index.system	41, 79
abstract_inverted_index.tight.	161
abstract_inverted_index.$3-1/M$	140
abstract_inverted_index.against	141
abstract_inverted_index.analyze	8
abstract_inverted_index.between	97
abstract_inverted_index.defines	20
abstract_inverted_index.minimum	34, 119
abstract_inverted_index.optimal	143
abstract_inverted_index.provide	88
abstract_inverted_index.safety,	42
abstract_inverted_index.speedup	137
abstract_inverted_index.addition	49
abstract_inverted_index.approach	86
abstract_inverted_index.deadline	110
abstract_inverted_index.finished	62
abstract_inverted_index.infinite	22
abstract_inverted_index.relative	109
abstract_inverted_index.sequence	23
abstract_inverted_index.setting,	107
abstract_inverted_index.sporadic	1, 18
abstract_inverted_index.systems.	16
abstract_inverted_index.accuracy.	103
abstract_inverted_index.analyzing	70
abstract_inverted_index.different	95
abstract_inverted_index.execution	10
abstract_inverted_index.identical	12, 152
abstract_inverted_index.real-time	15
abstract_inverted_index.recurrent	9
abstract_inverted_index.tradeoffs	96
abstract_inverted_index.complexity	100
abstract_inverted_index.deadlines.	66
abstract_inverted_index.functional	51
abstract_inverted_index.guaranteed	47
abstract_inverted_index.instances,	26
abstract_inverted_index.scheduling	85, 134, 144
abstract_inverted_index.timeliness	43
abstract_inverted_index.(identical)	77
abstract_inverted_index.algorithms,	145
abstract_inverted_index.constraint.	37
abstract_inverted_index.homogeneous	76
abstract_inverted_index.processors,	153
abstract_inverted_index.correctness,	52
abstract_inverted_index.inter-arrival	35, 120
abstract_inverted_index.asymptotically	160
abstract_inverted_index.fixed-priority	84
abstract_inverted_index.multiprocessor	78
abstract_inverted_index.schedulability	92
abstract_inverted_index.arbitrary-deadline	71, 106
abstract_inverted_index.deadline-monotonic	132
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
sustainable_development_goals[0].id	https://metadata.un.org/sdg/8
sustainable_development_goals[0].score	0.6000000238418579
sustainable_development_goals[0].display_name	Decent work and economic growth
citation_normalized_percentile