GitHub

Weakly Hard Systems

RealTimeScheduling provides basic support for weakly hard constraints.

Warning

Support for weakly hard systems is still a work in progress, and the API is still very incomplete. For now, we mainly support the constraints themselves, as well as comparisons between them.

Constraints that are logically equivalent compare as equal, even if they are represented differently.

julia> MeetAny(1, 1) == MeetRow(3, 5) == MissRow(0) == HardRealTime()
true

julia> MeetRow(0, 0) == MeetAny(0, 0) == BestEffort()
true

julia> MeetRow(4, 5) == MeetRow(2, 5)
false

Testing whether a BitVector satisfies a WeaklyHardConstraint is supported.

julia> BitVector([0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1]) ⊢ MeetRow(2, 5)
true

julia> BitVector([0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1]) ⊢ MeetRow(2, 5)
false
RealTimeScheduling.WeaklyHardConstraint — Type

Abstract parent type of all weakly hard constraints

The concrete subtypes of this, and many of the methods defined on them, are due to Bernat, Burns, and Llamosí, "Weakly Hard Real-Time Systems," IEEE Trans. Computers, Vol. 50, No. 4, April 2001.

source
RealTimeScheduling.MeetAny — Type
MeetAny{T}(meet::T, window::T)

Weakly hard constraint specifying that a task meets meet deadlines in any window of size window. Must satisfy 0 <= meet <= window.

source
RealTimeScheduling.MissAny — Function
MissAny([T=Int, ]miss, window)

Construct a MeetAny{T} constraint that allows at most miss deadlines to be missed in any window of size window.

While constraints of this sort are often expressed as a different type in the literature, they are equivalent to MeetAny, so using a single type simplifies any code using weakly hard constraints.

source
RealTimeScheduling.MeetRow — Type
MeetRow{T}(meet::T, window::T)

Weakly hard constraint specifying that a task meets meet deadlines in a row in any window of size window. Must satisfy 0 <= meet <= window.

source
RealTimeScheduling.MissRow — Type
MissRow{T}(miss::T)

Weakly hard constraint specifying that a task misses at most miss deadlines in a row. Must satisfy 0 <= miss.

source
RealTimeScheduling.satisfies — Function
satisfies(bv::BitVector, c::WeaklyHardConstraint)
⊢(bv::BitVector, c::WeaklyHardConstraint)

Check that the BitVector bv satisfies the weakly hard constraint given by c.

source
RealTimeScheduling.:⊢ — Function
satisfies(bv::BitVector, c::WeaklyHardConstraint)
⊢(bv::BitVector, c::WeaklyHardConstraint)

Check that the BitVector bv satisfies the weakly hard constraint given by c.

source
RealTimeScheduling.:⊬ — Function
⊬(bv::BitVector, c::WeaklyHardConstraint)

Check that the BitVector bv does not satisfy the weakly hard constraint given by c.

source

Sampling from Weakly Hard Constraints

A weakly hard constraint can be viewed as a sample space of bit strings, with 0 representing a deadline miss, and 1 representing a deadline hit. A finite length must be provided to generate such a string. For now, we only support uniform sampling from MissRow and MeetAny constraints.

Unfortunately, the requirement of specifying a string length precludes the easiest use of the Random.rand API. However, the precomputation required is non-negligible, so it would be a good idea to first create a sampler anyway.

RealTimeScheduling.SamplerUniformMissRow — Type
SamplerUniformMissRow(constraint::MissRow, H::Int64)

Pre-compute data for uniformly sampling BitVector objects from a MissRow constraint. The sampled vectors will have length H.

The algorithm used is due to Bernardi, Olivier, and Omer Giménez, "A linear algorithm for the random sampling from regular languages." Algorithmica 62.1 (2012): 130-145.

Examples

julia> sp = SamplerUniformMissRow(MissRow(3), 10);

julia> rand(sp)
10-element BitVector:
1
1
0
1
1
0
1
0
0
1
source
RealTimeScheduling.SamplerUniformMeetAny — Type
SamplerUniformMeetAny(constraint::MeetAny, H::Int64)

Pre-compute data for uniformly sampling BitVector objects from a MeetAny constraint. The sampled vectors will have length H.

The algorithm used is the recursive RGA due to Bernardi, Olivier, and Omer Giménez, "A linear algorithm for the random sampling from regular languages." Algorithmica 62.1 (2012): 130-145.

Examples

julia> sp = SamplerUniformMeetAny(MeetAny(1, 3), 10);

julia> rand(sp)
10-element BitVector:
1
1
0
1
1
0
1
0
0
1
source