On the complexity of fixed-priority scheduling of periodic, real-time tasks

DOI10.1016/0166-5316(82)90024-4zbMath0496.90046OpenAlexW2064207294WikidataQ56171480 ScholiaQ56171480MaRDI QIDQ3960458

Joseph Y.-T. Leung, Jennifer Whitehead

Publication date: 1982

Published in: Performance Evaluation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-5316(82)90024-4

zbMATH Keywords

computational complexityNP-completenessNP- hardnessmultiprocessors systemoptimal fixed-priority scheduling algorithmperiodic real-time tasks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items (57)

Periodic assignment and graph colouring ⋮ Schedulers for larger classes of pinwheel instances ⋮ Minimal schedulability interval for real-time systems of periodic tasks with offsets ⋮ On fixed priority scheduling, offsets and co-prime task periods ⋮ Flexible hard real-time scheduling for deliberative AI systems ⋮ Robust priority assignment for messages on Controller Area network (CAN) ⋮ Optimal priority assignment in the presence of blocking ⋮ DESH: Overhead reduction algorithms for deferrable scheduling ⋮ Optimal \((D - J)\)-monotonic priority assignment ⋮ Choosing task periods to minimise system utilisation in time triggered systems ⋮ Exact speedup factors for linear-time schedulability tests for fixed-priority preemptive and non-preemptive scheduling ⋮ Maintaining the feasibility of hard real-time systems with a reduced number of priority levels ⋮ A new sufficient schedulability analysis for hybrid scheduling ⋮ Dynamic real-time scheduling of firm periodic tasks with hard and soft aperiodic tasks ⋮ Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms ⋮ The partitioned dynamic-priority scheduling of sporadic task systems ⋮ Feasibility interval for the transactional event handlers of P-FRP ⋮ A new algorithm for scheduling periodic, real-time tasks ⋮ Nonpreemptive scheduling of periodic tasks in uni- and multiprocessor systems ⋮ An engineering process for the verification of real-time systems ⋮ SCT-based priority-free conditionally-preemptive scheduling of modular real-time systems with exact task execution time ⋮ Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems ⋮ Lowest priority first based feasibility analysis of real-time systems ⋮ An efficient implementation of a VNS heuristic for the weighted fair sequences problem ⋮ Exact speedup factors and sub-optimality for non-preemptive scheduling ⋮ A note on preemptive scheduling of periodic, real-time tasks ⋮ Resource access control for dynamic priority distributed real-time systems ⋮ Efficient computation of response time bounds for preemptive uniprocessor deadline monotonic scheduling ⋮ Maintaining data temporal consistency in distributed real-time systems ⋮ Energy-aware real-time task scheduling for heterogeneous multiprocessors with particle swarm optimization algorithm ⋮ Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound ⋮ Power efficient rate monotonic scheduling for multi-core systems ⋮ Task partitioning and priority assignment for distributed hard real-time systems ⋮ Multiprocessor real-time scheduling with arbitrary processor affinities: from practice to theory ⋮ Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms ⋮ Graph-based models for real-time workload: a survey ⋮ Feasibility problems for recurring tasks on one processor ⋮ Laxity dynamics and LLF schedulability analysis on multiprocessor platforms ⋮ Interference-aware fixed-priority schedulability analysis on multiprocessors ⋮ Fault-tolerant and real-time scheduling for mixed-criticality systems ⋮ Non-migratory feasibility and migratory schedulability analysis of multiprocessor real-time systems ⋮ Analysis and optimisation of hierarchically scheduled multiprocessor embedded systems ⋮ Feasibility analysis under fixed priority scheduling with limited preemptions ⋮ Vehicle minimization for periodic deliveries ⋮ Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible ⋮ Unnamed Item ⋮ Improved multiprocessor global schedulability analysis ⋮ Dynamic voltage scaling under EDF revisited ⋮ Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems ⋮ Rate-monotonic scheduling for hard-real-time systems ⋮ Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling ⋮ On earliest deadline first scheduling for temporal consistency maintenance ⋮ Exact Response Time Scheduling Analysis of Accumulatively Monotonic Multiframe Real Time Tasks ⋮ Rate monotonic scheduling in hard real-time systems ⋮ On priority assignment in fixed priority scheduling ⋮ Global control of robotic highway safety markers: a real-time solution ⋮ Response time analysis for fixed priority real-time systems with energy-harvesting

This page was built for publication: On the complexity of fixed-priority scheduling of periodic, real-time tasks