Flexible scheduling of hard real-time systems.
Neil Audsley · White Rose eTheses Online (University of Leeds, The University of Sheffield, University of York) · 1993
The design and implementation of increasingly complex hard real-time computer applications has been limited by the severe restrictions imposed by run-time support systems, in particular the scheduler.The restrictions arise from the assumptions required to afford 100% guarantees to processes with hard deadlines.This constrains the application to conform to the model required by the scheduler.For example, rate-monotonic scheduling, as originally proposed, restricts systems to periodic independent processes, with no shared resources.This thesis examines the trade-offs between the constraints required to enable offline feasibility analysis and the demand for increased fleidbility of the next generation of hard real-time systems.Initially, feasibility analysis is developed for a flexible process model.Tests are derived for static priority pre-emptive scheduling which relaxes the common restriction that the period of a periodic process must be equal to its deadline.One result of relaxing this constraint is that sporadic processes can be accommodated directly.The feasibility analysis is extended to permit processes that have their first execution offset from the 'initial start of system execution.This enables process sets with arbitrary precedence constraints to be expressed.An optimal priority assignment algorithm for processes that have offsets is given.Guaranteeing process deadlines using pessimistic estimations of processor and resource requirements implies that at run-time, an underutilisation of system resources will occur.An approach is proposed to identify this spare system capacity as soon as possible within the execution of a process.Conventionally, this spare capacity is used for the executions of processes without hard deadlines.This thesis presents an approach that enables spare capacity to be allocated to processes with hard deadlines so that system utility can be increased.This thesis contends that the adoption of such an approach imposes no real restrictions upon the application engineer, and greatly increases the flexibility of hard real-time systems, enabling many of the requirements of the next generation of hard real-time applications to be met.iv Chapter 1.