Task Systems
For interesting schedulability problems, a set of tasks needs to be contained within a task system. RealTimeScheduling provides such a type, which is a fairly thin wrapper around a standard Vector.
RealTimeScheduling.AbstractRealTimeTaskSystem — TypeAbstract parent type of all real-time task system types
RealTimeScheduling.TaskSystem — TypeTaskSystem{T} <: AbstractRealTimeTaskSystemA concrete real-time task system, holding a Vector of tasks of type T.
Generating Task Systems
Task systems can be generated at random using common algorithms from the real-time literature. This is useful for conducting schedulability studies.
RealTimeScheduling.randtasksystem — Functionrandtasksystem([tasktype=PeriodicImplicitTask{Float64}], U::Real,
utilization_dist::Univariate, period_dist::Univariate)Generate a random TaskSystem with utilization at most U. Tasks are drawn one at a time with utilizations drawn from utilization_dist, and periods from period_dist. The task system is returned once the next task generated would cause its utilization to exceed U.
Testing Properties of Task Systems
As with individual tasks, it can be useful to check if all tasks in a task system are implicit or constrained deadline.
RealTimeScheduling.implicit_deadline — Methodimplicit_deadline(T::AbstractRealTimeTaskSystem)Test whether all real-time tasks in T are implicit deadline.
RealTimeScheduling.constrained_deadline — Methodconstrained_deadline(T::AbstractRealTimeTaskSystem)Test whether all real-time tasks in T are constrained deadline.
It's just as easy to compute the utilization or density of a task system, as well as its hyperperiod.
RealTimeScheduling.utilization — Methodutilization(T::AbstractRealTimeTaskSystem)Return the sum utilization of all tasks in T.
RealTimeScheduling.density — Methoddensity(T::AbstractRealTimeTaskSystem)Return the sum density of all tasks in T.
RealTimeScheduling.min_utilization — Methodmin_utilization(T::AbstractRealTimeTaskSystem)Return the sum min_utilization of all tasks in T.
RealTimeScheduling.min_density — Methodmin_density(T::AbstractRealTimeTaskSystem)Return the sum min_density of all tasks in T.
RealTimeScheduling.hyperperiod — Methodhyperperiod(T::AbstractRealTimeTaskSystem)Return the hyperperiod, or least common multiple of the task periods, of T.
Additionally, it's often a sensible check to verify that a task system is feasible before doing other tests on it.
RealTimeScheduling.feasible — Methodfeasible(T::AbstractRealTimeTaskSystem, m::Integer=1)Test whether the real-time task system T is feasible on m processors, i.e. its density is at most m.
Task Priority
For fixed-priority (FP) scheduling, RealTimeScheduling uses an implicit model of task priority, whereby the index of a task in a given TaskSystem is its priority. Lower indices are considered higher priority, as is usually the case in the literature.
We provide two functions to sort a TaskSystem in order of increasing period and relative deadline.
RealTimeScheduling.rate_monotonic! — Functionrate_monotonic!(T::AbstractRealTimeTaskSystem)Sort the task system T from lowest to highest period.
RealTimeScheduling.deadline_monotonic! — Functiondeadline_monotonic!(T::AbstractRealTimeTaskSystem)Sort the task system T from lowest to highest period.
Time-Demand Analysis
Many schedulability tests make use of time-demand analysis (TDA). To support this, the common demand bound function (DBF) and request bound function (RBF) are implemented for task systems.
RealTimeScheduling.demand_bound — Methoddemand_bound(T::AbstractRealTimeTaskSystem, t)Compute Baruah's demand bound function (DBF) for task system T.
RealTimeScheduling.request_bound — Methodrequest_bound(T::AbstractRealTimeTaskSystem, t)Compute the request bound function (RBF) for task system T.
Using the RBF, the package provides an implementation of TDA for uniprocessor fixed-priority task systems.
RealTimeScheduling.schedulable_fixed_priority — Functionschedulable_fixed_priority(T)Check if the AbstractRealTimeTaskSystem T is schedulable by a fixed priority scheduler, with tasks prioritized by index (low to high).
Examples
Lehoczky's counterexample to use of traditional TDA when deadlines exceed periods:
julia> ts = TaskSystem([PeriodicTask(70, 70, 26), PeriodicTask(100, 118, 62)]);
julia> schedulable_fixed_priority(ts)
trueShortening the deadline of task 2 makes the system unschedulable:
julia> ts[2] = PeriodicTask(100, 116, 62);
julia> schedulable_fixed_priority(ts)
false