Julien David

We prove that the average complexity, for the uniform distribution on complete deterministic automata, of Moore's state minimization algorithm is O(n log log n), where n is the number of states in the input automata.

The Average Complexity of Moore's State Minimization Algorithm is O(n log log n) ⋆

Introduction

Due to their efficiency to represent regular languages and perform most of usual computations they involve, finite state automata are used in various fields such as linguistics, bioinformatics, program verification and data compression. A minimal automata is the smallest complete deterministic automata that can be associated to a regular language. Because this automaton is unique, up to isomorphism on the labels of the states, it is a canonical representation of a regular language and permits to test the equality between regular languages and equivalence between automata. Most state minimization algorithms compute the minimal automaton of a regular language taking a deterministic automaton as an input, by identifying the indistinguishable states. Moore proposed the first minimization algorithm [START_REF] Moore | Gedanken experiments on sequential machines[END_REF], which is based on the calculus of the Myhill-Nerode equivalence, by refinements of partitions of the set of states. There are at most n -2 such refinements, each of them requiring a linear running time: in the worst case, the complexity is quadratic. Though, in [START_REF] Bassino | On the average complexity of Moore's state minimization algorithm[END_REF], it is proved that the average complexity of the algorithm is bounded by O(n log n). Since this result does not rely on the underlying graph of the automaton, it holds for any probabilistic distribution on this graph. Also, the bound is tight for unary automata. Hopcroft's state minimization algorithm [START_REF] Hopcroft | An n log n algorithm for minimizing states in a finite automaton[END_REF] is the best known algorithm with an O(n log n) worst-case complexity. It also uses partition refinements to compute the minimal automaton, but its description is not deterministic, making its analysis complicated. Different proofs of its correctness were given [START_REF] Gries | Describing an algorithm by Hopcroft[END_REF][START_REF] Knuutila | Re-describing an algorithm by Hopcroft[END_REF] and several authors [START_REF] Berstel | On the complexity of Hopcroft's state minimization algorithm[END_REF][START_REF] Castiglione | On extremal cases of Hopcroft's algorithm[END_REF] proved the tightness of the upper bound of the complexity for different families of automata. In this paper, we prove that for the uniform distribution on complete deterministic automata, the average complexity of the algorithm due to Moore is O(n log log n). The article is organized as follows: after recalling the basics of automata minimization (Section 2), we introduce the tools we use for the average analysis (Subsections 2.3 to 2.5). Section 3 is dedicated to the average time complexity analysis of Moore's algorithm. Due to a lack of space, the proof of Lemma 6 is not fully detailed, but an idea of the proof is given. The paper closes with a discussion on Hopcroft's algorithm executions, which are faster than Moore's algorithm ones, for any input automaton and a conjecture on the average complexity of both algorithms, for various distributions on automata.

Preliminaries

Definitions and notations

A finite deterministic automaton A = (A, Q, •, q 0 , F ) is a quintuple where Q is a finite set of states, A is a finite set of letters called alphabet, the transition function • is a mapping from Q × A to Q, q 0 ∈ Q is the initial state and F ⊂ Q is the set of final states. An automaton is complete when its transition function is total. The transition function can be extended by morphism to all words of A * :

p • ε = p for any p ∈ Q and for any u, v ∈ A * , p • (uv) = (p • u) • v. A word u ∈ A *
is recognized by an automaton when p • u ∈ F . The set of all words recognized by A is denoted by L(A). We note A i the words of length i and A ≤i the word of length less or equal to i. An automaton is accessible when for any state p ∈ Q, there exists a word u ∈ A * such that q 0 • u = p.

A transition structure is an automaton where the set of final states is not specified. Given such a transition structure T = (A, Q, •, q 0 ) and a subset F of Q, we denote by (T , F ) the automaton (A, Q, •, q 0 , F ). For a given deterministic transition structure with n states there are exactly 2 n distinct deterministic automata that can be built from this transition structure. Each of them corresponds to a choice of set of final states.

In the following we only consider complete deterministic automata and complete deterministic transition structures, the accessibility is not guaranteed. Consequently these objects will most of the time just be called respectively automata or transition structures. The set Q of an n-state transition structure will be denoted by {1, . . . , n}. The set of automata and the set of transition structures with n states will respectively be denoted A n and T n . Also, since there are kn transitions and since for each transition, there are n possible arrival states, we have |T n | = n kn and |A n | = 2 n n kn (when |E| is the cardinal of the set E). The term 2 n comes from the choice of the set of final states. The military order on words, noted < mil , is defined as follows: ∀u, v ∈ A * , u < mil v if |u| < |v| or |u| = |v| and u is smaller than v in the lexicographical order. Let Cond be a Boolean condition, the Iverson bracket [[Cond]] is equal to 1 if the condition Cond is satisfied and 0 otherwise. For any non-negative integer i, two states p, q ∈ Q are i-equivalent, denoted by p ∼ i q, when for all words [START_REF] Nerode | Linear automaton transformation[END_REF]. This relation is said to be right invariant, meaning that for all u ∈ A * and all p, q ∈ Q, p ∼ q ⇒ p • u ∼ q • u. Proposition 1. Let A = (A, Q, •, q 0 , F ) be a deterministic automaton with n states. The following properties hold:

u ∈ A ≤i , [[p • u ∈ F ]] = [[q • u ∈ F ]]. Two states p and q are equivalent (noted p ∼ q) when for all u ∈ A * , [[p • u ∈ F ]] = [[q • u ∈ F ]]. This equivalence relation on Q is called Myhill-Nerode equivalence
(1) For all i ∈ N, ∼ i+1 is a partition refinement of ∼ i , that is, for all p, q ∈ Q, if p ∼ i+1 q then p ∼ i q. (2) For all i ∈ N and for all p, q ∈ Q, p ∼ i+1 q if and only if p ∼ i q and for all a ∈ A, p • a ∼ i q • a.

(3) If for some i ∈ N (i + 1)-equivalence is equal to i-equivalence then for every j ≥ i, j-equivalence is equal to Myhill-Nerode equivalence.

For any integer n ≥ 1 and any m ∈ N, we denote by A m n the set of automata with n states for which m is the smallest integer such that the m-equivalence ∼ m is equal to Myhill-Nerode equivalence. It is well known that m ≤ n -2.

Moore's State Minimization Algorithm

In this section we describe Moore's algorithm [START_REF] Moore | Gedanken experiments on sequential machines[END_REF] to compute the minimal automaton of a regular language represented by a deterministic automaton. It builds the partition of the set of states corresponding to Myhill-Nerode equivalence and mainly relies on properties (2) and (3) of Proposition 1: The partition π is initialized according to the 0-equivalence ∼ 0 , then at each iteration the partition corresponding to the (i + 1)-equivalence ∼ i+1 is computed from the one corresponding to the i-equivalence ∼ i using property [START_REF] Bassino | Enumeration and random generation of accessible automata[END_REF]. The algorithm halts when no new partition refinement is obtained, and the result is Myhill-Nerode equivalence according to property [START_REF] Berstel | On the complexity of Hopcroft's state minimization algorithm[END_REF]. The minimal automaton can then be computed from the resulting partition since it is the quotient automaton by Myhill-Nerode equivalence. According to Proposition 1, if an automaton is minimized in more than ℓ partition refinements, then there exists at least a pair of states p, q and a word u of length ℓ + 1, such that p ∼ ℓ q and p • u ≁ 0 q • u, that is to say at least two states are separated during the ℓ + 1-th partition refinement. In the remainder of this section we introduce the dependency tree and a modification of the dependency graph introduced in [START_REF] Bassino | On the average complexity of Moore's state minimization algorithm[END_REF]. Those tools will allow us to give an upper bound on the number of automata minimized in more than ℓ partition refinements, which is useful for the average complexity analysis.

The Dependency Tree

In the following, we introduce the dependency tree to model a set of transition structures. To begin with, we explain how a dependency tree R(p) can be obtained from a fixed transition structure τ and a fixed state p and then how this object will help to estimate the cardinal of a set of transition structures. For a

Algorithm 1: Moore's algorithm if F = ∅ then 1 return (A, {1}, * , 1, ∅) 2 if F = {1, . . . , n} then 3 return (A, {1}, * , 1, {1}) 4 forall p ∈ {1, . . . , n} do 5 π ′ [p] = [[p ∈ F ]] 6 π = undefined 7 while π = π ′ do 8 π = π ′ 9 compute π ′ from π 10 return the quotient of A by π 11
In this description of Moore's algorithm, * denotes the function such that 1 * a = 1 for all a ∈ A. Lines 1-4 correspond to the special cases where F = ∅ or F = Q. In the process, π ′ is the new partition and π the former one. Lines 5-6 is the initialization of π ′ to the partition of ∼0, π is initially undefined. Lines 8-10 are the main loop of the algorithm where the new partition is computed, using the second algorithm below. The number of iterations of Moore's algorithm is the number of times those lines are executed.

The computation of the new partition is done using the following property on associated equivalence relations:

p ∼i+1 q ⇔ ( p ∼i q p • a ∼i q • a ∀a ∈ A To each state p is associated a signa- ture s[p] such that p ∼i+1 q if and only if s[p] = s[q]
. The states are then sorted according to their signature, in order to compute the new partition. The use of a lexicographic sort provides a complexity of Θ(kn) for this part of the algorithm.

Algorithm 2:

Computing π ′ from π forall p ∈ {1, . . . , n} do 1 s[p] = (π[p], π[p • a1], . . . , π[p • a k ]) 2 compute the permutation σ that 3 sorts the states according to s[] i = 0 4 π ′ [σ(1)] = i 5 forall p ∈ {2, . . . , n} do 6 if s[p] = s[p -1] then i = i + 1 7 π ′ [σ(p)] = i 8 return π ′ 9
Fig. 1. Description of Moore's algorithm fixed transition structure with n states over a k-letter alphabet and a fixed state p, we define the function isnode mapping A * to {0, 1} as follows:

isnode(w) = 0 if ∃v ∈ A * such that p • w = p • v and v < mil w, 1 otherwise.
R(p) is a tree in which nodes and leaves of depth h are labelled by words of length h. It is built recursively, using a breadth-first traversal of the nodes of the tree starting from the node p. For each node of depth h labelled by w, and each letter a in the alphabet, we add a node labelled by wa at depth h + 1 if isnode(wa) is equal to 1, and a leaf otherwise. Figure 2 gives an example of a dependency tree. Note that this construction resembles the method used in [START_REF] Bassino | Enumeration and random generation of accessible automata[END_REF] to randomly generate accessible automata, except the authors use a depth-first traversal. It is easy to see that some dependency trees can be obtained from several fixed transition structures and states. In the remainder of the paper, we characterize sets of transition structures corresponding to particular dependency trees.

We introduce some notations associated to a dependency tree R(p): S h (p) denotes the set of all nodes of depth less or equal to h, L h (p) denotes the set of all the nodes at given depth h. Since every node in the tree is labelled by a word, we note w ∈ S h (p) or w ∈ L h (p) if w is a word labelling a node in those sets. We also define the set s h (p) of all the states that are reached from a state p by following a path labelled by a word of less or equal to h. For all the transition structures associated to a dependency tree R(p), we have

|s h (p)| = |S h (p)|.
Lemma 1. For any fixed state p, if a dependency tree R(p) contains f leaves at a depth less or equal to h, then the number of associated transition structures is bounded above by

|T n | |S h (p)| n f .
Proof. We recall that |T n | is equal to the product of the cardinals of the sets of possible arrival states, for each transition. Let wa be the label of a leaf at depth less than h. For every transition structure associated to the tree R(p), the transition labelled by a outgoing from the state p • w ends in a state p • v, with v ∈ S h (p). Therefore, the number of possible arrival states for this transition is bounded above by |S h (p)| instead of n. This is a rough upper bound but sufficient for the needs of the proof.

The T -Dependency graph

We introduce another model for sets of transition structures. For two fixed states p and q, two fixed x-tuples (x is a fixed integer) of non-empty words -→ u = (u 1 , . . . , u x ) and -→ v = (v 1 , . . . , v x ), two fixed sets ϕ p and ϕ q of pairs of words (w,w ′ ) such that w ′ < mil w, we define the set T n (p, q, ϕ p , ϕ q , -→ u , -→ v ) as follows:

T n (p, q, ϕ p , ϕ q , -→ u , -→ v ) = {τ ∈ T n |∀(w p , w ′ p ) ∈ ϕ p , p • w p = p • w ′ p , ∀(w q , w ′ q ) ∈ ϕ q , q • w q = q • w ′ q , ∀i ≤ x, p • u i = q • v i } We define the x-tuples of words -→ u ′ = (u ′ 1 , . . . , u ′ x )
and

-→ v ′ = (v ′ 1 , . . . , v ′ x ) and the x-tuples of letters -→ α ′ = (α ′ 1 , . . . , α ′ x )
and

-→ β ′ = (β ′ 1 , . . . , β ′ x ), such that for all i ≤ x we have u i = u ′ i α i and v i = v ′ i β i . From T n (p, q, ϕ p , ϕ q , - → u , -→ v ), one
can define the undirected graph G n (p, q, ϕ p , ϕ q , -→ u , -→ v ), called the T -dependency graph, as follows:

its vertices are pairs (r, a), with r ∈ Q and a ∈ A, that model transitions.

-There is an edge ((r, a),

(t, b)) in G n (p, q, ϕ p , ϕ q , -→ u , - → v ) if and only if for all τ ∈ T n (p, q, ϕ p , ϕ q , -→ u , -→ v ), r • a = t • b.
The T -dependancy graph G n (p, q, ϕ p , ϕ q , -→ u , -→ v ) satisfies the two following properties:

-For all i ≤ x, there exists an edge ((p

• u ′ i , α i ), (q • v ′ i , β i )).
-For all (w 1 , w 2 ) ∈ ϕ p (resp. (w 3 , w 4 ) ∈ ϕ q ), we have w 1 = w ′ 1 a 1 and w 2 = w ′ 2 a 2 with a 1 , a 2 ∈ A and such that there exists an edge ((p

•w ′ 1 , a 1 ), (p• w ′ 2 , a 2 )) (resp. ((q • w ′ 3 , a 3 ), (q • w ′ 3 , a 3 ))). Lemma 2. If G n (p, q, ϕ p , ϕ q , -→ u , -→ v ) contains
an acyclic subgraph induced by a subset of nodes with j edges, then:

|T n (p, q, ϕ p , ϕ q , -→ u , -→ v )| ≤ |T n | n j
Proof. Two transitions in the same connected components of G n (p, q, ϕ p , ϕ q ,--→ u , -→ v ) share the same arrival state. Hence if x is the number of connected components in the graph, then |T n (p, q, ϕ p , ϕ q , -→ u , -→ v )| ≤ n x . If G n (p, q, ϕ p , ϕ q , -→ u , -→ v ) contains an acyclic subgraph with exactly j edges, then there is at most knj connected components.

The F -Dependency Graph

In this subsection, we slightly modify the notion of dependency graph introduced in [START_REF] Bassino | On the average complexity of Moore's state minimization algorithm[END_REF]. Let τ be a fixed transition structure with n states and ℓ be an integer such that 1 ≤ ℓ < n. Let p, q be two states of τ such that p = q and u a word of length ℓ. We define F τ (p, q, u) as the set of sets of final states F for which in the automaton (τ, F ) the states p and q are separated by the word u. That is to say :

F τ (p, q, u) = {F ⊂ {1, . . . , n} | for all (τ, F ), p ∼ |u|-1 q, [[p • u ∈ F ]] = [[q • u ∈ F ]]}
From the set F τ (p, q, u) one can define the undirected graph G τ (p, q, u), called the F -dependency graph, as follows: its set of vertices is {1, . . . , n}, the set of states of τ ; -there is an edge (s, t) between two vertices s and t if and only if there exists a word w of length less than ℓ such that s = p • w and t = q • w and for all

F ∈ F τ (p, q, u), [[s ∈ F ]] = [[t ∈ F ]].
The F -dependency graph contains some information that is a basic ingredient of the proof: it is a convenient representation of necessary conditions for a set of final states to be in F τ (p, q, u), that is, for Moore's algorithm to require more than |u| iterations because of p, q and u. Figure 3 shows an example of a Fdependency graph.

Lemma 3. [1]

If G τ (p, q, u) contains an acyclic subgraph with at least i edges, then |F τ (p, q, u)| ≤ 2 n-i .

The notions of dependency graphs and dependency tree will be used in subsections 3.2 and 3.3 to obtain upper bounds on the cardinal of sets of automata with given properties and prove that their contribution to the average complexity is negligible.

Moore's Algorithm: average case analysis

In [START_REF] Bassino | On the average complexity of Moore's state minimization algorithm[END_REF], it is proved that the average complexity of Moore's state minimization algorithm is O(n log n). Since the result is obtained by studying only properties on the sets of final states of automata minimized in a given complexity, it holds for any distribution on the set of transition structures. In this paper, in order to improve the upper bound on the average complexity, we also have to study some properties of transition structures. Since the enumeration of accessible automata with given properties is an open problem, we focus our study on the uniform distribution over the set of complete deterministic automata.

Main Result and Decomposition of the Proof

The main result of this paper is the following.

Theorem 1 For any fixed integer k ≥ 2 and for the uniform distribution over the deterministic and complete automata with n states over a k-letter alphabet, the average complexity of Moore's state minimization algorithm is O(n log log n).

Recall that the number of partition refinements made by Moore's state minimization algorithm is smaller or equal to n -2 and that A i n is the set of automata of A n for which i is the smallest integer such that ∼ i is equal to Myhill-Nerode equivalence. The average number of partition refinements is given by:

N n = 1 |A n | n-2 i=0 (i + 1) × |A i n |
We define λ = ⌈log k log 2 n 3 + 2⌉, which will be used in the sequel. We gather the sets A i n , in order to obtain the following upper bound:

N n ≤ λ + 1 |A n | i≤λ |A i n | + (5 log 2 n + 1) |A n | 5 log 2 n i=λ+1 |A i n | + n -1 |A n | n-2 i=5 log 2 n+1 |A i n | S1 S2 S3
S1 is less than λ and equal to O(log log n).

In [START_REF] Bassino | On the average complexity of Moore's state minimization algorithm[END_REF], it is proved that

n-2 i=5 log 2 n+1 |A i n | ≤ |An| n .
Therefore we know that S3 is equal to O(1). Hence, in the following, we prove that:

S2 = (5 log 2 n + 1) |A n | 5 log 2 n i=λ+1 |A i n | = O(log log n) (1)
For any ℓ > 0, we define the set A n (p, q, ℓ) as the set of automata with n states, where the states p and q are separated during the ℓ-th partition refinement:

A n (p, q, ℓ) = {(τ, F ) ∈ A n | τ ⊂ T n , F ⊆ {1, . . . , n}, p ∼ ℓ-1 q, p ≁ ℓ q}
Remark 1. Note that if in the automaton (τ, F ), for all letter a ∈ A, p • a = q • a, then either p ≁ 0 q or p ∼ q. Therefore (τ, F ) / ∈ A n (p, q, ℓ) with ℓ > 0. Consequently, in the remainder of the proof, in all sets of transition structures where p and q are fixed, there exists a letter a such that p • a = q • a.

The following statement comes from the definition of the sets it involves:

i>λ A i n = p,q∈{1,...,n} A n (p, q, λ + 1)
Let τ be a transition structure, and p, q be two distinct states. Recalling that s h (p) is defined in Section 2.3, if A is a k-letter alphabet, and µ a positive integer, we define two properties associated to transition structures:

(1) largeT ree(τ, p, µ) is true if and only if

|s µ (p)| ≥ k µ -1. Note that this implies that |s µ-2 (p)| ≥ k µ-2 -1. (2) noIntersection(τ, p, q) is true if and only if s λ-2 (p) ∩ s λ-2 (q) = ∅.
For fixed states p and q, an automaton is in A n (p, q, λ + 1) if its associated transition structure is in one of the three distinct sets we are about to define:

-X n is the set of all transition structures τ such that:

• there exists a state r ∈ Q such that largeT ree(τ, r, λ) is f alse. Note that this set does not rely on the values of p and q.

-Y n (p, q) is the set of transition structures τ such that:

• for all state r ∈ Q, the property largeT ree(τ, r, λ) is true,

• for all words w ∈ A ≤2 , the property noIntersection(τ, p • w, q • w) is f alse. -α n (p, q) is the set of transition structures τ such that:

• for all state r ∈ Q, the property largeT ree(τ, r, λ) is true,

• there exists w ∈ A ≤2 such that noIntersection(τ, p • w, q • w) is true.

Transition

Structures with a Huge F -Dependency Graph Lemma 4. For any fixed transition structures τ ∈ α n (p, q), and a fixed word u of length λ+1, the following property holds: every F -dependency graph G τ (p, q, u) contains an acyclic subgraph with at least k λ-2 -1 edges.

Proof. Let G ′ be the subgraph G τ (p, q, u) defined as follows: there exists an edge (p•wv, q•wv) in G ′ , if and only if v labels a node in S λ-2 (p•w). G ′ contains exactly |s λ-2 (p • w)| edges, since for all v ∈ S λ-2 (p • w), the states p • wv are all pairwise distinct. Since largeT ree(τ, r, λ) is true for all state r ∈ Q, we have |s λ-2 (p•w)| ≥ k λ-2 -1. G ′ is acyclic: indeed, the property noIntersection(τ, p•w, q•w) indicates that the set of nodes connected to at least one edge forms a bipartite graph (the nodes of s λ-2 (p • w) on one side and the nodes of s λ-2 (q • w) on the other), where all the nodes of s λ-2 (p • w) are only connected to one edge.

Corollary 1. For λ = ⌈log k log 2 n 3 +2⌉, the number of automata in A n (p, q, λ+ 1) whose transition structures are in

α n (p, q) is O |T n | 2 n log n n 3 .
Proof. This follows directly from Lemmas 3 and 4 : for any distinct states p and q, any word u of length λ + 1 , and any fixed transition structure τ ∈ α n (p, q), we have

|F τ (p, q, u)| = O 2 n-log 2 n 3
For a fixed transition structure τ ∈ α n (p, q), since the number of words in A λ+1 is O(log n), the number of choices of sets of final states such that the automata are in A n (p, q, λ + 1) is bounded above by: Proof. For a fixed state r and a fixed integer µ ∈ {1, . . . , λ}, we define the sets X n (r, µ) of all transition structures τ for which µ is the smallest integer such that the property largeT ree(τ, r, µ) is false. We have :

X n = r∈{1,...,n}   µ∈{1,...,λ} X n (r, µ)  
For all transition structures in X n (r, µ), the dependency tree R(r) contains at least two leaves of depth less or equal to µ. Indeed, if R(r) contains at most one leaf of depth less than µ, then there exist k-1 letters a ∈ A such that R(r•a) does not contain any leaf of depth less than µ. Therefore we have

|S µ (p)| ≥ k µ -1.
We decompose the possible dependency trees R(r) into two different kinds:

1. All leaves are at level µ. Let k be the size of the alphabet and f the number of leaves, the number of trees of this kind is equal to

k µ f =2 k µ
f . 2. There exists exactly one leaf of depth h (with h < µ), and at least one of depth µ. The number of trees of this kind is at most

µ-1 h=1 k h k µ f =1 k µ f .
Using the upper bound of Lemma 1 on the number of transition structures counted by each tree, we obtain:

|X n (r, µ)| ≤ k µ f =2 k µ f |T n | |S µ (r)| n f + µ-1 h=1 k µ f =1 k h k µ f |T n | |S µ (r)| n f +1
Since µ ≤ λ, we have |S µ (r)| < k λ+1 and:

|X n (r, µ)| < |T n |   k λ f =2 k λ f k λ+1 n f + λk 2λ+1 n k λ f =1 k λ f k λ+1 n f   Since we have k λ f k λ+1 n f ≤ k 2λ+1 n f : |X n (r, µ)| < |T n |   k 4λ+2 n 2 ∞ f =0 k 2λ+1 n f + λk 4λ+2 n 2 ∞ f =0 k 2λ+1 n f   |X n (r, µ)| = O |T n | λk 4λ n 2 = O |T n | log 4 n 3 × log log n 3 n 2
Since this upper bound holds for any µ ∈ {1, . . . , λ} and any r ∈ Q, we obtain:

|X n | ≤   r∈{1,...,n} µ∈{1,...,λ} |X n (r, µ)|   = O |T n | log 4 n 3 × log 2 log n 3 n Lemma 6.
For any distinct states p and q, the number of transition structures in

Y n (p, q) is O |T n | log 6 n n 3 .
Proof. For any transition structure in Y n (p, q), for all words w ∈ A ≤2 , there exist two words u, v ∈ A ≤λ-2 such that p • wu = q • wv. We partition the set Y n (p, q) according to the leaves the dependency trees contain. Both trees do not contain a leaf of depth less or equal to λ : let E be the set of letters, such that for all a ∈ E, p • a = q • a. We define e = |E|. According to Remark 1, we have e < k. For all b ∈ A \ E and all c ∈ A, noIntersection(τ, p • bc, q • bc) is f alse. For -→ u and -→ v of size x = e + k(ke), such that for all 1 ≤ j ≤ e, we have u j = v j = a j with a j ∈ E and such that for all e < j ′ ≤ x, w ′ j is a prefix of u j ′ and v j ′ , where w ′ j is a word of the form bc. This subset is included in:

E A ∀a∈E, p•a=q•a - → u , - → v T n (p, q, ∅, ∅, - → u , -→ v )
There are 2 k -1 possible subsets E. There are less than k 2λ(x-e) possible choices for u i , v i ∈ A ≤λ , for e < i ≤ x. For all j, l ≤ x, j = l, since u j and u l (resp. v j and v l ) label nodes in R(p) (resp. R(q)), setting u j = u ′ j α j and u l = u ′ l α l , we have (p • u ′ j , α j ) = (p • u ′ l , α l ) and there is no path between (p • u ′ j , α j ) and (p • u ′ l , α l ) since if would imply that p • u j = p • u l and that either u j or u l labels a leaf. Therefore, G n (p, q, ∅, ∅, -→ u , -→ v ) contains an acyclic graph with x edges

((p • u ′ j , α j ), (q • v ′ j , β j )). Since x ≥ k + 1 (for e = k - 1
), using Lemma 2, we obtain the upper bound stated above. At least one tree contains a leaf of depth less or equal to λ : due to a lack of space, we will not describe this set. The idea is that, just like in the previous case, we are able to guarantee that a T -dependency graph always contains an acyclic subgraph with k + 1 edges and that there is O(log 2(k+1) n) possible graphs.

Concluding the proof

Recall that we want to prove Equation 1. We define X n , α n (p, q) and Y n (p, q) as the sets of automata whose transition structure are respectively in X n , α n (p, q) and Y n (p, q). We have:

Conclusion

In this paper, we obtained a new upper bound on the average complexity of Moore's state minimization algorithm, for the uniform distribution on complete deterministic automata. Also, it is possible to describe a set of Hopcroft's algorithm executions which, for any deterministic automata, compute the equivalence in less steps than Moore's algorithm (due to a lack of space, we are not giving the description of those executions in this paper). Hence, for the uniform distribution on complete deterministic automata with n states, there exists an execution of Hopcroft's algorithm whose average complexity is O(n log log n). This paper is a first step to prove the conjecture made in the conclusion of [START_REF] Bassino | On the average complexity of Moore's state minimization algorithm[END_REF]: for the uniform distribution on complete deterministic accessible automata, the average complexity of Moore algorithm is Θ(n log log n). To prove this conjecture is not an easy task, since it requires a better knowledge of the average size of the accessible part in a complete deterministic automaton, but also the average number of minimal automata amongst the complete deterministic and accessible. I would like to thank Phillipe Duchon for the fruitful discussion on upper bound of the cardinal of the set X n , but also Cyril Nicaud and Frederique Bassino for their advices and comments.

Fig. 2 .

 2 Fig.2. Let (a) be the fixed transition structure and 2 be the fixed state, (b) is the associated dependency tree R(2). We have S2(2) = {ε, a, b, aa, ab}, L2(2) = {aa, ab} and s2(2) = {2, 3, 4, 5, 6}.

Fig. 3 .

 3 abb

n log n n 3 3. 3 5 .

 335 u∈A λ+1 |F τ (p, q, u)| = O 2 Negligible Sets of Transition Structures Lemma The number of transition structure in X n is O |T n | log 5 n n .

2 n log 5 n n + n 2 |T n | × 2 n log n n 3 + |T n | 2 n log 6 n n 3 ≤ |A n | log 6 n n (5 log 2 n + 1 )

 2331 ,...,n}A n (p, q, λ + 1) ⊆ X n ∪   p,q∈{1,...,n} α n (p, q) ∪ Y n (p, q) log log n)Hence N n = O(log log n), this concludes the proof of the main theorem.

⋆ This work was completed with the support of the ANR project GAMMA number 07 -2 195422.


Frédéric Fauberteau
email: fauberte@univ-mlv.fr

Serge Midonnet
email: midonnet@univ-mlv.fr

Laurent George
email: lgeorge@ieee.org

Improvement of schedulability bound by task splitting in partitioning scheduling

We focus on the class of static-priority partitioning scheduling algorithm on multiprocessor. We are interested in improving the schedulability of these algorithms by splitting the tasks which cannot be successfully allocated on processors.

Context

Unless P = N P , no polynomial time algorithm exists to solve the MULTIPROCESSOR-TASK-PARTITIONING problem. Indeed, this problem can be transformed from BIN-PACKING problem which is NP-hard in the strong sense. Fortunately, there are several heuristics which solve BIN-PACKING problem and they may be adapted to produce partitioned schedulings. For instance, the algorithm FBB-FDD is based on First-Fit Decreasing [START_REF] Fisher | The partitioned scheduling of sporadic tasks according to static-priorities[END_REF] and the algorithm RM-DU-NFS is based on Next-Fit [START_REF] Andersson | Preemptive multiprocessor scheduling anomalies[END_REF].

We are interested in proposing a partitioning algorithm which is robust to task Worst Case Execution Time (WCET) overruns faults with the same objective as in [START_REF] Davis | Robust priority assignment for fixed priority real-time systems[END_REF]. This partitioning tends to maximize the capacity of the system to handle the WCET overruns by offering the maximum Allowance to each faulty task of the system. The Allowance of a task is the execution duration which can be added to its WCET such that all the deadlines in the system are met [START_REF] Bougueroua | Dealing with execution-overruns to improve the temporal robustness of realtime systems scheduled FP and EDF[END_REF].

We have shown in [START_REF] Fauberteau | A robust partitioned scheduling for real-time multiprocessor systems[END_REF] that the Worst-Fit heuristic offers good results in order to maximize the robustness of a partitioned system. Worst-Fit selects the least loaded processor (in terms of utilization) which can accept a task. Unfortunately, the performances of Worst-Fit in terms of schedulability are less efficient than those of the heuristics widely used in partitioning algorithms (First-Fit Decreasing/Best-Fit/Next-Fit). In order to improve the schedulability bound of Worst-Fit and potentially those of the other heuristics, we propose to split the tasks which cannot be allocated one a single processor. Contrary to the portioned scheduling approach proposed in [START_REF] Kato | Portioned static-priority scheduling on multiprocessors[END_REF] and [START_REF] Kato | Semi-partitioned fixed-priority scheduling on multiprocessors[END_REF], we don't migrate a job from a processor to another during its execution but we allocate jobs on different processors such that the migrations occur at job boundaries [START_REF] Baruah | Multiprocessor fixed-priority scheduling with restricted interprocessor migrations[END_REF].

Task splitting approach

Description. Let Π be a multiprocessor composed by m identical processors denoted by Π = {π 1 , . . . , π m }. Let τ be a set of tasks made of n periodic (or sporadic) real-time tasks denoted τ = {τ 1 , . . . , τ n }. Each task is characterized by its WCET, its deadline and its period (or minimum interarrival time). We consider a partitioning algorithm denoted A which allocates the tasks of τ on Π. A is designed as follows:

• τ is sorted according to a decreasing order policy (for instance Decreasing Utilization),

• a heuristic chooses the processor on which a given task should be allocated, • a schedulability test is used to decide whether the task can be allocated on the processor chosen by the heuristic. The resulting algorithm A produces a partition of τ on Π. If A fails to allocate the task τ i , the set of pending tasks {τ i , . . . , τ n } is unallocated.

In order to schedule these unallocated tasks, two approaches can be considered: portioned scheduling and scheduling at job boundaries (i.e. restricted migration). To illustrate the first one, we show in Figure 1 four tasks [START_REF] Davis | Robust priority assignment for fixed priority real-time systems[END_REF][START_REF] Bougueroua | Dealing with execution-overruns to improve the temporal robustness of realtime systems scheduled FP and EDF[END_REF], τ 3 [START_REF] Davis | Robust priority assignment for fixed priority real-time systems[END_REF][START_REF] Fauberteau | A robust partitioned scheduling for real-time multiprocessor systems[END_REF], τ 4 (3, 6)} scheduled on three processors. No partition can be found because u i + u j > 1, ∀i = j, i, j ∈ {1, 2, 3, 4} (u i = W CET period ). In this example, the tasks are allocated in decreasing utilization order and τ 4 is the last one. Therefore τ 4 is portioned and its jobs are scheduled on the three processors.

This approach can be difficult to implement because it is not easy to split a job in many parts. A job consists in pieces of code which can contain indivisible sections. Moreover, a large number of migrations occurs since a job can migrate several times. The second approach is attractive because the migrations are at job boundaries. Therefore no migration overhead are incurred if the consecutive jobs of a task don't share any data. We propose to plit a task in several k subtasks. Each subtask has the same WCET and deadline as its parent task but the subtasks are less frequently activated (their periods are multiplied). k -1 subtasks are unsynchronized with an offset to avoid the jobs overlaps. We represent in Figure 2 the same example as in Figure 1. For instance, the subtasks τ 1 1 (0, 2, 3, 9) on P 1 , τ 2 1 (3, 2, 3, 9) on P 3 and τ 3 1 (6, 2, 3, 9) on P 3 produce the same execution as τ 3 (2, 3) (where (w, x, y, z) is (offset, WCET, deadline, period)).

Open problem. We consider the case where a partitioning algorithm doesn't succeed to partition the set τ of tasks. Our aim is to build an algorithm which can split the pending tasks in subtasks such that a feasible partition of τ can be found. If no pending task can be split, already allocated tasks can be split until a feasible partition is found. The problem is to build an algorithm which finds a valid splitting scheme if such a scheme exists such that a feasible partition can be found.

Insights. We want to build an algorithm which splits the tasks such that the migration occurs at job boundaries. A first approach is to build a static-priority restricted migration scheduler. This scheduler allocates jobs of the tasks when they are activated on a ready processor according to a static-priority scheme. By logging the allocations made by this scheduler, we can build our splitting scheme. Notice that, this approach can be complex because it may require the consideration of an interval of study which can be exponential. Moreover, it is not obvious to decide on which processor a task must be activated to minimize the number of subtasks.


Damien Masson
email: masson@univ-mlv.fr

Serge Midonnet
email: midonnet@univ-mlv.fr

Slack Time Evaluation with RTSJ

We address in this paper the problem of jointly scheduling hard periodic tasks and soft aperiodic events using the Real-Time Specification for Java (RTSJ). We present the programming constraints of RTSJ and propose slack time evaluation and utilization algorithms which take these constraints into account. We evaluate these algorithms and compare their performances with the Background Scheduling (BS) through simulations.

INTRODUCTION

The need for more flexibility in real-time systems leads the community to address the problem of jointly scheduling hard periodic tasks and soft aperiodic events.

The easiest way to achieve this is to schedule all nonperiodic tasks at a lower priority (assuming that the tasks are scheduled using a preemptive fixed priority policy). This policy is known as the Background Servicing (BS).

In order to minimize the aperiodic tasks response times whilst guaranteeing the feasibility of the periodic tasks, the periodic task servers were introduced. A server is a periodic task, for which classical response time determination methods are applicable (with or without modifications). The server is in charge of servicing the non-periodic traffic with a limited capacity.

The Static Slack Stealer, an algorithm to compute the exact slack available at time t to execute aperiodic tasks at the highest priority, is proposed in [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF]. The optimality of this approach for maximizing the aperiodic tasks response times is demonstrated. Unfortunately, the time and memory complexities does not permit to use it.

We propose in this paper to start from RTSJ constraints to set up a slack time approximation algorithm. Then we discuss the slack time utilization issues with RTSJ.

We review in Section 2 the available mechanisms with RTSJ. Section 3 describes our approximate slack evaluation algorithm. Section 4 explicits RTSJ constraints to design slack time evaluation and utilization algorithms. Section

APERIODIC TASKS AND RTSJ

The RTSJ proposes two classes AsyncEvent and Async-EventHandler to model respectively an asynchronous event and its handler(s). The only way to include an handler in the feasibility process is to treat it as an independent task, and that implies to know at least its worst-case occurring frequency.

The RTSJ does not support any particular task server policy. We propose a solution in [START_REF] Masson | The design and implementation of real-time event-based applications with RTSJ[END_REF].

AVAILABLE SLACK EVALUATION

Our goal is to construct a slack time evaluation implementable with a minimal RTSJ compliant virtual machine.

The only instants in the system life time where we can easily operate are each periodic task instances begin and end.

We decompose the maximum available slack per task (S max i,t ) according to Equation 1 where W max i,t is the maximum possible work at priority i regardless of lower priority processes, and ci(t) is the effective hard real-time work we have to process at the instant t at the priority i.

S max i,t = W max i,t -ci(t) (1)
Then the available slack at time t at the highest priority is the minimum of the S max i,t .

Data initialization

Under hypothesis of a synchronous activation of all periodic hard real-time tasks at t0, we have:

8 > > < > > : W max 1,t 0 = d1 ∀i, W max i,t 0 = di - P ∀k∈HP (i) l T i T k m c k ∀i, ci(to) = ci (2)
where ci, di and Ti are respectively the cost, the deadline and the period of the periodic task τi. The data initialization has a time complexity in O(n 2 ), with n the periodic tasks number.

Dynamic operations

The data are function of time, so they potentially evolve at each clock tick. Between two dates t1 and t2, Wi is reduced by t2 -t1 for any task and ci(t) is reduced for any task executed during the interval. Eventually, these values can be increased for the tasks which complete between t1 and t2. However, we only need to update them at each periodic task instance begin and end and when an aperiodic event occurs.

1. End of periodic task τi. Let dt be the elapsed time since the last update of our data. Then, Wi is reduced by the elapsed time since the last update and increased by Ti minus the interference of tasks with higher priority. This interference, given by equation 3, has already be computed during the initialization phase.

Ii = X ∀k∈HP (i) ‰ Ti T k ı c k (3)
Ii is not the real interference at instant t, but the maximal interference. This bound is reach in the worst case scenario: the synchronous activation of all the tasks.

Moreover, for all tasks, W k is reduced by the elapsed time, and for all tasks with a lower priority than τi, W k is increased by ci. Finally, ci(t) is reset to ci.

8 > > < > > : ∀j, Wj,t = W j,t ′ -dt W max i,t ≥ Wi,t = max(W i,t ′ , 0) + Ti -Ii ∀j > i, Wj,t = W j,t ′ + ci ci(t) = ci (4) 2.
Beginning of periodic task τi.

The maximum available process time is reduced by dt at all priority level. Let j be the previous activity priority level. If j is in the hard real-time priority range (noted hrtp), then cj(t) is reduced by dt.

<

:

∀k, W k,t = W k,t ′ -dt if j ∈ hrtp, cj(t) = cj (t ′ ) -dt if Wi,t < ci(t), Wi,t = ci(t) (5)

Soft real-time aperiodic task τα arrival.

As for the previous cases, the maximum available process time is reduced by dt at all priority level as Wj if the previous activity priority, j, is in the hard realtime priority range. Then, the available slack at the highest priority is computed.

8 > < > : ∀k, W k,t = W k,t ′ -dt if j ∈ hrtp, cj (t) = cj (t ′ ) -dt S max i,t ≥ Si,t = min i∈hrpr Wi,t -ci(t) (6)

RTSJ CONSTRAINTS

Slack approximation

In order to act at the beginning and at the end of the periodic tasks instances, we overload the waitForNextPeriod() method of RealTimeThread. This method is called at the end of each periodic job and is blocking until the next job execution.

The slack stealer may be implemented as an AsyncEvent-Handler bound to a special AsyncEvent and with the maximal available priority.

The soft aperiodic events can be implemented with several AsyncEvent all bound to the AsyncEventHandler representing the slack stealer. In this way, we can call the slack stealer every time a soft aperiodic event is released and before and after each instance of hard periodic tasks.

Slack Utilization

With Java, it is impossible to resume a previously stopped thread. The RTSJ offers a mechanism to asynchronously interrupt a RT-thread, but it does not allow to resume it later. Moreover, in most implementation of RTJVM, the dynamic change of the priority is not supported.

Due to these limitations, we cannot begin the execution of a soft task at the highest priority if there is not enough slack to permit its completion.

When there is available slack, we schedule the execution of the first soft pending task with a cost lower or equal than the available slack at the highest priority. When there is no slack and no pending periodic task, we schedule in BS the first pending aperiodic task.

SIMULATIONS

We simulate the same real-time systems with the three following aperiodic policies: a BS, a slack stealing with an exact computation of the slack and one with our approximation of the slack.

Methodology

We measure the mean response time of soft tasks with different aperiodic and periodic loads.

First, we generate groups of ten periodic task sets with utilization levels of 30, 50, 70 and 90%. The results presented in this section are based on averages over a group of ten task sets. Then, we generate groups of ten aperiodic task sets with a range of utilization levels (plotted on the x-axis in the following graph). Our simulations end when all soft tasks have been served.

We experiment on a GPL home made event-based simulator.

Results

Our simulations show an improvement over a simple BS. However, we are nearer from a BS than from the same policy using an exact computation of the slack. Moreover, the higher the periodic charge is, the worst the results are.

CONCLUSIONS

In this paper, we address the problem of jointly scheduling hard periodic tasks and soft aperiodic events with RTSJ. We present the programming constraints of RTSJ and propose a simple slack time evaluation algorithm. We describe a possible implementation of this algorithm. We describe a RTSJ compliant slack utilization algorithm. We simulate this algorithm with an exact slack computation and with our approximation. If we obtain better results than a simple BS, these simulations point out that our approximation of the available slack is too large.


Damien Masson
email: damien.masson@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Userland Approximate Slack Stealer with Low Time Complexity

The aim of our work is to provide a mechanism to deal with soft real-time aperiodic traffic on top of a fixed priority scheduler, without any kind of modification on it. We want to reduce as most as possible the time and implementation complexities of this mechanism. Moreover, the overhead of the framework has to be completely integrated in the feasibility analysis process. We propose a naive but low cost slack time estimation algorithm and discuss the issue of its utilization at the user level. We validate our work by extensive simulations and illustrate its utility by an implementation on top of the Real-Time Specification for Java (RTSJ).

Introduction

The need for more flexibility in real-time systems leads the community to address the problem of jointly scheduling hard periodic tasks and soft aperiodic events.

A solution is to set up a mechanism which allows nonperiodic traffic to be served and analyzed without changing the feasibility conditions of a periodic task.

The easiest way to achieve this is to schedule all nonperiodic tasks at a lower priority (assuming that the tasks are scheduled using a preemptive fixed priority policy). This policy is known as the Background Servicing (BS). If it is very simple to implement, it does not offer satisfying response times for non-periodic tasks, especially if the periodic traffic is important.

Research turns on new scheduling approaches for minimizing the aperiodic tasks response times whilst guaranteeing the feasibility of the periodic tasks.

In this context, the periodic task servers were introduced by LEHOCZKY et al. in [START_REF] Lehoczky | Enhanced aperiodic responsiveness in hard real-time environments[END_REF]. A periodic task server is a periodic task, for which classical response time determination and admission control methods are applicable (with or without modifications). This particular task is in charge of servicing the non-periodic traffic with a limited capacity.

Several types of task server can be found in the literature. They differ by the way the capacity is managed. We can cite the Polling Server policy (PS), the Deferrable Server policy (DS), the Priority Exchange policy (PE) first described by LEHOCZKY et al. in [START_REF] Lehoczky | Enhanced aperiodic responsiveness in hard real-time environments[END_REF] and developed in [START_REF] Strosnider | The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments[END_REF][START_REF] Sprunt | Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm[END_REF] and the Sporadic Server policy (SS) presented in [START_REF] Sprunt | Aperiodic task scheduling for hard real-time systems[END_REF].

In [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF], LEHOCZKY and RAMOS-THUEL propose the Static Slack Stealer, an algorithm to compute the slack: the maximal amount of time available at instant t to execute aperiodic tasks at the highest priority without endangering the periodic tasks. They demonstrate the optimality of this approach in terms of maximizing the aperiodic tasks response times among non clairvoyant algorithms. Unfortunately, they also admit that its time and memory complexities are much too high for it to be usable.

In his PhD thesis work [START_REF] Davis | On Exploiting Spare Capacity in Hard Real-Time Systems[END_REF], DAVIS proposes a dynamic algorithm to compute the exact available slack time. Then he demonstrates that the complexity is too high for a real implementation and proposes two approximate slack time computation algorithms, one based on a static approximation, SASS, and the other which is dynamic, DASS. The dynamic approach presents the advantage to allow gain time 1to be assimilated in the slack and then transparently reallocated for aperiodic traffic.

All these contributions make the assumption that the developer has the hand on the scheduler, and are in substance enhanced scheduling mechanisms. Unfortunately, the scheduler is most of the time a part of the hardware or of the operating system. That is why we propose a framework based upon these algorithms, but adapted to be implemented in userland, on top of the scheduler.

In this paper, we describe and evaluate the slack stealer part of this framework. Our goal is to provide a slack stealer approach not only implementable on top of the system scheduler, but also with a very low overhead integrable in the feasibility analysis process.

To limit this overhead, we propose a very simple slack approximation algorithm of the slack which does not use scheduler or system specific data to perform. Moreover, we modify the way the slack is used in order to integrate the slack gesture cost in the worst case execution time of periodic tasks.

We formalize in Section 2 the task model and general notations. We describe in Section 3 the static and dynamic slack stealers, and the Dynamic Approximate Slack Stealer (DASS). We present our userland slack estimation in Section 4. Then its userland utilization in Section 5. Our simulations methodology is detailed in Section 6 and results are presented in Section 7. We propose to illustrate this work with an RTSJ implementation in Section 8.

Task Model and notations

We consider a process model of a mono processor system, Φ, made up of n periodic tasks, Π = {τ 1 , ..., τ n } scheduled with fixed priorities. Each τ i ∈ Π is a sequence of requests for execution characterized by the tuple τ i = (C i , T i , D i , P i), where C i is the worst case execution time of the request 2 ; T i is its period ; D i its relative deadline with D i ≤ T i and P i its priority, 3 being the highest. Tasks are ordered according to their priority, i.e. P 1 < P 2 < ... < P n . We do not consider blocking factor nor release jitter.

The system also has to serve an unbounded number p of aperiodic requests, Γ = {σ 1 , ..., σ p }. A request σ i ∈ Γ is characterized by a worst case execution time C i 2 .

The highest priority, 1, is reserved for the task T which implements our mechanism. When an aperiodic request is raised, T registers it in a queue. When slack becomes available, enqueued aperiodic tasks can be released by T with the priority 2. They are then scheduled by the system according to this priority.

Static and Dynamic Slack Stealing

The slack stealing technique was first introduced by LE-HOCZKY and RAMOS-THUEL in [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF]. It consists in determining how much computation time is available at the highest priority without jeopardizing the execution of the periodic tasks. Then this time can be used for aperiodic servicing. Since our mechanism is inspired by this technique, we review it in this section. 2 for brevity concern, we can denote it cost in this paper

Static Slack Stealing

This slack stealing algorithm is called static because the most significant computations are made off line. However, there is also a run-time phase.

Off line computations

The aim of this first step is to compute for each task a function which gives the task laxity at time t. The laxity of the task τ i at time t is the sum of aperiodic processing which can be process immediately in preference of τ i without compromising the respect of its deadline. These functions are noted A i (t). The function giving the aperiodic processing which can be processed at time t at the highest priority without compromise any deadline is noted A(t). The authors proved Equation 1 and gave an algorithm to compute the A i (t).

A(t) = min 1≤k≤n A k (t) (1)

On line algorithm

A(t) = min 1≤i≤n (A i (t) -I i ) -A (2)
At time t, the available laxity is given by Equation 2 where I i is the i-level inactivity and A the sum of the aperiodic processing time. These two values are maintained up to date each time the CPU begins a new activity.

The available laxity can only be increased when a hard periodic task ends. Hence, the laxity is only computed in two cases: if an aperiodic task is released when the aperiodic queue is empty and if a periodic task ends whilst the aperiodic queue is not empty.

Though this first algorithm is optimal (it provides the exact available time), it has time and memory complexities much too high and it is only applicable to simple systems, without synchronization constraints, resources sharing or sporadic hard real-time tasks. Moreover it can not be extended for gain time reclaiming. That is why DAVIS proposes a dynamic algorithm.

Dynamic Slack Stealing

This part of DAVIS thesis was first published with TIN-DELL and BURNS in [START_REF] Davis | Scheduling slack time in fixed priority pre-emptive systems[END_REF]. The first step to determine the available slack time is to compute for each task the maximum guaranteed slack, S max i (t), i.e. the maximum amount of slack time which may be stolen at priority level i, during the interval [t, t + d i (t)), whilst guaranteeing that task τ i meets its deadline. The value d i (t) denotes the remaining time before τ i next deadline.

The interval [t, t + d i (t)) is viewed as a succession of ilevel busy periods 3 and i-level idle periods 4 . Then, S max i (t) is the sum of the i-level idle period lengths. The author provides two equations, one to compute the end of a busy period starting at time t, one to compute the length of an idle period starting at time t. To determine S max i (t), the two equations are recursively applied until the next deadline is reached.

Then, if an aperiodic task is released at time t, let k be the priority of the running hard periodic task, the soft aperiodic task processing can proceed immediately in preference to task τ k for a duration of min This algorithm is not directly usable because of its time complexity. However, the slack computation can be replaced by a slack estimation. The algorithm is then no more optimal but can offer a significant improvement compared to other solutions. DAVIS proposes slack approximation mechanisms, but his algorithms are schedulers, with full knowledge of tasks and current execution parameters. Rather than adapting them, we prefer to set up a naive approximation based on data pieces easily available. Moreover, we want to keep a low computation complexity. Concerning the use of the computed slack, our algorithm is driven by our will to integrate the overhead in the feasibility analysis.

Dynamic Approximate Slack Stealer

Since S i (t) is the sum of the i-level idle period lengths in the interval [t, t + d i (t)), DAVIS proposes to estimate this quantity by computing a bound on the maximal interference the task τ i can suffer in this interval. A bound on this interference is given by the sum of the interferences from each task with a higher priority than τ i . Then Equation 3 gives the interference suffer by a task τ j from a task τ i in an interval [a, b].

I j i (a, b) = c i (t) + f i (a, b)C i + min(C i , (b -x i (a) -f i (a, b)T i ) 0 ) (3)
The function f i (a, b) returns the τ i instance number which can begins and completes in [a, b]. It is given by Equation 4.

f i (a, b) = b -x i (a) T i 0 (4)
The function x i (t) represents the first activation of τ i which follows t. Then the interference is composed by the remaining computation time needed to complete the current pending request, by a number of entire invocations given by f i (a, b), and by a last partial request.

A lower bound on the S i (t) value is given by the length of the interval minus the sum of the interferences from each task with a higher or equal priority than τ i . It is recapitulated by Equation 5.

S i (t) =   d i (t) -t - ∀j≤i I i j (t, d i (t))   0 (5)

Userland algorithm for slack time estimation

We decompose the maximum available slack per task (S max i (t)) into two different pieces of data: first W max i (t), the maximum possible work at priority i regardless of lower priority processes ; second c i (t), the effective hard real-time work we have to process at the instant t. The approximation is performed on the first term. To compute a bound on the available slack at time t at the highest priority, S(t), we then have to compute S i (t) for all priorities and take the minimum. This operation has an O(n) time complexity.

S max i (t) = W max i (t) -c i (t) S max t ≥ S t = min 1≤i≤n W i (t) -c i (t) (6)
So we have to keep up to date for each periodic task the two values W i (t) and c i (t).

Data initialization

Under hypothesis of a synchronous activation of all periodic hard real-time tasks at t 0 , we have:

W max 1 (t 0 ) = D 1 (7) ∀i, W max i (t 0 ) = D i - ∀k<i D i T k C k (8) ∀i, c i (t 0 ) = C i (9)
If we relax the synchronous activation hypothesis, the exact number of τ k activation between the first release of τ i and its first deadline, N b a , should be computed and equation 8 becomes:

∀i, W max i (t 0 ) = D i - ∀k<i N b a C k (10)
The data initialization has a time complexity in O(n 2 ), but can be completed before starting the system.

Dynamic operations

The values we want to keep up to date are function of time, so they potentially evolve at each clock tick. Between two dates t 1 and t 2 , if k is the priority level of the executing task, W max i is reduced by dt = (t 2 -t 1 ) for any task with a higher priority than k, and c i (t) is reduced for τ k . We approximate W max i by considering that it is reduced by dt for all tasks. We correct this pessimistic evaluation when a task τ k ends by adding its cost to W i for all task with a lesser priority than k. We will see in Section 5 that we only need to compute the slack when a task ends. So we just have to update the W i when a task completes and the c i at each context switches. If we do not consider systems with resource sharing, a context switch occurs only when a task begins and when a task ends.

1. End of periodic task τ k . Let dt be the elapsed time since t le the last periodic task ending, i.e. the last update of a W i . Then, W i is reduced by dt for all tasks and W k is increased by T k and reduced by the interference of higher priority tasks during the next period of τ k . We consider an upper bound on the maximal interference the task can suffer during one period. This bound, I * k , given by equation 11, can be computed during the initialization phase. A closer approximation technique is discussed in Section 4.3. Interference suffers by τ k before its next activation is already included in the approximation of W k .

I k ≤ I * k = ∀j<k T k T j C j (11)
Moreover, for all tasks with a smaller priority than τ k ,

W i is increased by C k . Finally, c k (t) is reset to C k . ∀i < k, W i (t) = W i (t le ) -dt ∀i > k, W i (t) = W i (t le ) -dt + C k i = k, W k (t) = W k (t le ) -dt + T k -I * k c k (t) = C k (12)
These operations are summarized in Equation 12. Their time complexity is O(n). We will see in Section 4.3 that the time complexity to obtain the interference is also O(n). This overhead can be a priori added to each periodic task cost since the operations are performed at the end of each instance.

2. Beginning of periodic task τ k .

As in the previous case, the maximum available process time is reduced by dt at each priority levels. However, since we do not need to accurate the

W i values qT τ τ T T i j i j i r u Tj v (k-1)T i Figure 1. Number of T i in T j
before the next task ending, we do not update these values in this case. Since the last update of data (end or begin of periodic request servicing), there is two possibilities. First, the scheduler can have served periodic traffic, say a τ j request. Then c j (t) is reduced by dt. The other possibility is that the system was idle or servicing a soft request. Then there is no need for data update.

If j = 0, c j (t) = c j (t) -dt ( 13
)
This operation is summarized in Equation 13. This time, the time complexity is O(1) and again, the induced overhead can be added to each periodic task cost.

Soft real-time aperiodic task τ α arrival.

When a soft real-time aperiodic task is released, it is enqueued. Utilization of the slack to serve enqueued aperiodic requests is the topic of Section 5.

Interference upper bound

Let τ i and τ j be two periodic hard real-time tasks with T i < T j . The priorities are assigned with a Rate Monotonic policy. We discuss in this section of I j i (t), the interference task τ j suffers from task τ i . More precisely, we give here a way to determine N a j i (t), the number of activations of task τ i during the current period of task τ j . We have the following properties:

I j i (t) ≤ N a j i (t).c i (14) I j (t) ≤ h∈hp(j) I j h (t) (15)
If we can find the N a j i (t) value in constant time, we can determine a bound for the total interference in O(n) time complexity.

Possible values for N a j

i (t) Let q and r be the quotient and the remainder in the euclidean division of T j by T i . We have T j = qT i + r. Then, for any activation of τ j , let u denotes the time before the next τ i activation, k the number of τ i activations before the next τ j activation and v be equal to T j -(k -1)T i -u. We have

T j = u + (k -1)T i + v, u < T i and v < T i .
Figure 1 resumes these notations.

Theorem 1. There is only two possible values for k, which are q + 1 and q.

Proof of k > q -1.

Suppose k ≤ q -1, k ≤ q -1 ⇒ k -1 ≤ q -2 ⇒ u + (k -1)T i + v < T i + (q -2)T i + T i because u < T i and v < T i .
Then, since we have u + (k -1)T i + v = T j , we get T j < qT i . This is in contradiction with T j = qT i + r, r ≥ 0.

Proof of k < q + 2. Suppose k ≥ q + 2, k ≥ q + 2 ⇒ k -1 ≥ q + 1 ⇒ u + (k -1)T i + v ≥ u + (q + 1)T i + v ⇒ T j ≥ (q + 1)T i , since u ≥ 0 and v ≥ 0.
This is in contradiction with T j = qT i + r, q ≥ 1 and r < T i .

In conclusion, determining the two possible values is a constant time complexity operation, and can be done offline before starting the system.

Determining the next interference

When a task τ j ends at time t, we want to find an upper bound on I i the interference it will suffer from tasks with higher priorities during its next activation. This interference is bounded by the sum of the interferences caused by each task with higher priority. Then the interference caused by task τ i is bounded by kC i , where k is the number of τ i activations during the τ j next period. We demonstrate that k can be equal to q or q + 1, where q is the quotient in the euclidean division of T j by T i .

In order to determine the correct value of k in this particular case, we first determine the value of u. At time t, let u be the difference between b and a, where a is the next T j activation date and b the first T i activation date that follow a. We have:

a = t T j T j b = a T i T i u = b -a
Now, we just have to compare u and r :

Theorem 2. u ≤ r ⇒ k = q + 1 (16) u > r ⇒ k = q (17)
Proof of Equation 16.

k = q + 1 ⇒ k -1 = q ⇒ u + (k -1)T i + v = qT i + u + v ⇒ u + v = r ⇒ u ≤ r since u ≥ 0 and v ≥ 0.
Proof of Equation 17.

k = q ⇒ u + (k -1)T i + v = (q -1)T i + u + v ⇒ u + v -T i = r ⇒ u > r since v < T i .
If we relax the assumption of the rate monotonic priorities assignment, we can have T j < T i . Than we have q = 0 and r = T j . That gives us:

u ≤ T j ⇒ k = 1 u > T j ⇒ k = 0 which is correct.
Choosing the correct value is then a constant time complexity operation. We are able to determine the N a j i (t) value with a O(1) time complexity and then the interference with a O(n) time complexity. Note that the complexity is the same for the exact computation of the interference used by DASS and given by Equation 3. However, the constant number of computations needed is smaller and we do not need any execution related data such as the remaining execution time needed to complete τ i .

Slack utilization in userland

In the slack stealer algorithms proposed by LEHOCZKY and RAMOS-THUEL and then by DAVIS, the slack at the highest priority is computed at the arrival of an aperiodic request, and the request is served in the limit of the slack. In DASS, S i (t) is computed each time a task with a higher or equal priority than τ i ends an execution, and assumed to have decreased by the elapsed time otherwise. Then the slack is computed in O(n) time complexity each time an aperiodic arrives. In our userland context, we oppose two objections to these models.

First, if we consider a request with a cost greater than the available slack, we have to start the service of the request, stop it when the slack is exhausted and then resume it later when more slack is available. This is not a problem if we are writing a scheduler, but becomes quite complex in userland. We can off course play with the priority of the task, but it supposes that the system allows dynamic changes of the priorities. So the first conclusion is that we must wait to have enough slack to schedule the request in one shot.

From that limitation cames the question of the queue policy. Not having enough slack to serve the first arrived aperiodic request does not mean that we not have enough to serve the second one. In our simulations, we test the following policies: first in first out, last in first out, lowest cost first and highest cost first.

The second objection is that we cannot compute the slack each time an aperiodic request arrives. Since the number and the arrival model of the aperiodic requests are unknown and the computation of the slack has an O(n) time complexity, the overhead of this approach cannot be bounded nor incorporated in the feasibility analysis process.

From this second objection cames the question of the best instant to begin a pending request. Several approaches are possible. Two remarks are that the slack can only grows up when a periodic task ends its execution and that in the worst case, after x time unit since the last growth, the slack has decreased by x.

The general conclusion is that we can compute in O(n) time complexity a close approximation of the slack at each periodic task ending, and assume at any other instant that the slack has just decreased by the amount of elapsed time unit. In this way, the slack estimation computation in O(n) can be included in the task costs, and the rough estimation perform each time an aperiodic request arrives is just limited to a constant time complexity, inducing a very low overhead. This overhead is not greater than the unavoidable cost of enqueuing (or rejecting) the aperiodic request.

The use of a slack estimation instead of an exact computation and the fact that we have to wait for having enough slack to complete a request before starting it raises a new issue. Some times, the algorithm can return a slack value of 0 time unit although the system is idle. Alternatively, there can exist some situations where the slack has often a non null but low value. In that sort of situations, our algorithm cannot begins the request while a simple BS could have been able to complete it. To limit the side effect of these situations on the average response time of the aperiodic requests, we test a policy we called "duplicate BS". It consists to duplicate all aperiodic requests. One copy is immediately scheduled with BS and the other copy is enqueued in our mechanism. The first of the two to end interrupts the other one.

We call this userland utilization of the slack associated with our minimal approximation of the available slack the Minimal Approximate Slack Stealer (M ASS) algorithm.

Simulations

The validation of the effectiveness of our slack estimation is the first purpose of our simulations. Despite the simplicity of our algorithm induced by the wanted low overhead, we expect results comparable to an exact slack computation based algorithm. The targeted performance metric is the mean response time of the aperiodic requests. To achieve this goal, we simulate the same systems with aperiodic tasks served according to our slack estimation and with the same aperiodic tasks (same release times and same costs) served according to the approximation of DASS and with an exact computation of the available slack.

The second expecting result is the validation of the userland exploitation of slack time. The only other available algorithm that does not need to customize the scheduler is the Background Scheduling (BS). So we compare our results with the BS. Moreover, in [START_REF] Masson | The design and implementation of real-time event-based applications with rtsj[END_REF] we proposed a framework for implementing task servers with RTSJ on top of the default scheduler. This framework permitted us to write a Polling server and a Deferrable Server, but with modifications on this two algorithms. We denote the modified algorithms MPS and MDS. We also compare our results with this ones to know how the slack stealing based approach performs comparing to server based ones.

Finally, we also want to determine the best queue policy through our simulations.

Methodology

We measure the mean response time of soft tasks with different aperiodic and periodic loads.

First, we generate groups of periodic task sets with utilization levels of 30, 50, 70 and 90%. The results presented in this section are averages over a group of ten task sets. For the same periodic utilization, we repeat generations over a wide range of periodic task set composition, from systems composed by 2 periodic tasks up to systems composed by 100 periodic tasks.

The periods are randomly generated with an exponential distribution in the range [40-2560] time units. Then the costs are randomly generated with an uniform distribution in the range [1-period] In order to test systems with deadlines less than periods, we randomly generate deadlines with an exponential distribution in the range [cost-period]. Priorities are assigned assuming a deadline monotonic policy.

Non feasible systems are rejected, the utilization is computed and systems with an utilization level differing by less than 1% from that required are kept.

For the polling server, we have to find the best period T s and capacity C s couple. We try to maximize the system load U composed by the periodic load U T and the server load U S .

U = U T + U S U = C i T i + C s T s
A feasible system load being bounded by 1, we have Equation 18.

C s T s ≤ 1 - C i T i (18)
To find a lower bound C min s of C s , we first set the period to 2560 (the maximal period). We then search the maximal value for C s in [START_REF] Bollella | The Real-Time Specification for Java[END_REF]16] in order to keep a feasible system. This maximal value is our lower bound on C s .

Then we seek the lower possible

T s value in [C min s /(1 - C i /T i ), 2560]. For each T s value tested, we try decreas- ing values of C s in [C min s , T s (1 -C i /T i )].
Note that it is possible to find a capacity lower than the maximal aperiodic tasks cost. In such cases, since we have to schedule the aperiodic tasks in one shot, we have no solution but to background scheduling the tasks with a cost greater than the server capacity.

For the deferrable server, the methodology is similar, except that since the server has a bandwidth preservation behavior, we do not try to minimize the period and we can search the maximal C s value in [START_REF] Bollella | The Real-Time Specification for Java[END_REF]2560].

Finally, we generate groups of ten aperiodic task sets with a range of utilization levels (plotted on the x-axis in the following graphs). Costs are randomly generated with an exponential distribution in the range [START_REF] Bollella | The Real-Time Specification for Java[END_REF][START_REF] Burns | On the Move to Meaningful Internet Systems 2003: Workshop on Java Technologies for Real-Time and Embedded Systems[END_REF][START_REF] Davis | Scheduling slack time in fixed priority pre-emptive systems[END_REF][START_REF] Davis | On Exploiting Spare Capacity in Hard Real-Time Systems[END_REF][START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF][START_REF] Lehoczky | Enhanced aperiodic responsiveness in hard real-time environments[END_REF][START_REF] Masson | The design and implementation of real-time event-based applications with rtsj[END_REF][START_REF] Sprunt | Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm[END_REF][START_REF] Sprunt | Aperiodic task scheduling for hard real-time systems[END_REF][START_REF] Strosnider | The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments[END_REF][11][12][13][14][15][16] and arrival times are generated with an uniform distribution in the range . Our simulations end when all soft tasks have been served.

Real-time Simulator

We develop a real-time event-based system simulator. This is a Java program which can simulate the execution of a real-time system and display a temporal diagram of the simulated execution.

This tool is distributed under the General Public License GNU (GPL), and can be found on the following web page: http://igm.univ-mlv.fr/ ˜masson/RTSS In order to evaluate our slack time evaluation, we add a PFP scheduler which schedules aperiodic tasks according to an exact slack computation and another according to our slack evaluation. The policies simulated take into account the restrictions due to the targeted userland implementation. Figures 2 to 9 present our simulations results. On these figures, ESS, DASS and M ASS refer to our slack stealer modified algorithm associated respectively with an exact computation of the available slack time, the slack time approximation given by DASS and our approximation of the available slack time. M P S and M DS designate the modified polling server and deferrable server we developed in a previous work. Finally BS designates the background scheduling associated with a F IF O queue policy and M BS a modified background server which cannot begins a task if a previously started task has not completed. The notation X&BS refers to the policy X with a BS duplication.

Figures 2 to 5 show the M ASS results for all periodic composition systems. We notice that our algorithm performs much better than BS for all policies if the periodic load is low (see Figure 2 and3). However, when the periodic load increases, the BS duplication became unavoidable. With the extreme 90% load (Figure 5), the non BSduplicated curves are not viewable on the same graph than the other and are completely out performed by the BS. The explications of this phenomena can be found in Section 5.

The second thing to note is that the queue policy which offers the best results is the LCF one. Due to space limitations and clarity purpose, we cannot put all our results in this paper, but this trend is confirmed by simulations on M P S, M DS, DASS and ESS. This is for sure amplified by the one shot execution limitation. The shorter a task is, the greater is the probability to have quickly enough slack to schedule it completely. Figures 6 to 9 present the results of the best queue policy for each algorithm (M P S, M DS, M ASS, DASS and ESS). For ESS, since the time complexity is dependant on the number of task, the results do not include systems composed of more than 40 periodic tasks. For all load conditions, servers bring real improvement comparing to BS. The M DS offers better performances than the M P S. Then, M ASS performs better than the servers, DASS better than M ASS and ESS better than DASS. For systems with periodic loads of 30% and 50%, results obtained with M ASS, DASS and ESS are quite similar. Considering the differences between the time complexities of these algorithms (constant, linear and pseudo polynomial), this is a very satisfying result. However M ASS performances degrade when periodic load increases. Nevertheless M ASS remains the best userland-implementable algorithm even for systems with a periodic load of 90%.

Example: RTSJ implementation

To illustrate the relevance of this work, we propose here an RTSJ [START_REF] Bollella | The Real-Time Specification for Java[END_REF] implementation of this slack stealer mechanism. Under RTSJ, it is possible theoretically to change the scheduler, but all the implementation of the specification rely on system scheduler. So if you want to use advance algorithms for jointly scheduling soft and hard real-time tasks in a portable application, you have to do it on top of the basic priority scheduler available by default.

Aperiodic Tasks and RTSJ

The RTSJ proposes two classes AsyncEvent and AsyncEventHandler to model respectively an asynchronous event and its handler(s). The only way to include an handler in the feasibility process is to treat it as an independent task, and that implies to know at least its worst-case occurring frequency.

The RTSJ does not support any particular task server policy. It also provides the so called "Processing Group Parameters" (PGP), which allows programmer to assign resources to a group of tasks. A PGP object is like a Release-Parameters which is shared between several tasks. More specifically, PGP has a cost field which defines a time budget for its associated task set. This budget is replenished periodically, since PGP has also a field period. This mechanism provides a way to set up a task server at a logical level. Unfortunately it does not take into account any server policy. Moreover, as pointed in [START_REF] Burns | On the Move to Meaningful Internet Systems 2003: Workshop on Java Technologies for Real-Time and Embedded Systems[END_REF], it is far too much permissive and it does not provide appropriate schedulability analysis techniques. Finally, since cost enforcement is an optional feature for an RTSJ-compliant virtual Java machine, PGP can have no effect at all. This is the case with the Timesys Reference Implementation of the specification (RI).

In next Section, we describe our previously published task server framework for RTSJ and we show how we can use it to write a slack stealer.

Slack Stealer Implementation with RTSJ

In [START_REF] Masson | The design and implementation of real-time event-based applications with rtsj[END_REF], we proposed an RTSJ extension to use task servers. Since we extend this framework to propose a slack stealer, we first describe it in this section.

Task Servers implementation

Our framework (Task Server Framework) is composed of six new classes: ServableAsyncEvent (SAE), ServableAsyncEventHandler (SAEH), Task-Server, PollingTaskServer, Deferrable-TaskServer and TaskServerParameters. To summarize the mechanism, when an SAE is fired, the servableEventReleased() methods of the bounded servers are called for each of its SAEHs. This method add the SAEH in the associated task server job queue. Depending of the subclass used, the server can be scheduled periodically or aperiodically to serve the aperiodic jobs in his queue. Several queue policies are possible. This allows developers to write different behaviors for different task server policies.

For example, we proposed a PollingTaskServer class which is implemented with a periodic real-time thread and a DeferrableTaskServer class with an asynchronous event handler bounded to a special event.

Slack Stealer is a Task Server

We can add a new class SlackStealerTaskServer to Figure 10. This class extends TaskServer. The slack stealer has to be wake up aperiodically: when an aperiodic task is released while the queue is empty, or when the slack time is increased while the queue is not empty.

The logic of the SlackStealerTaskServer class can be delegated to an AsyncEventHandler bounded to a special AsyncEvent. The method fire() of this event is called in the two situations described above.

This design was used for our deferrable server implementation and validated by execution experiments.

Conclusions

In this paper, we address the problem of jointly scheduling hard periodic tasks and soft aperiodic events when we cannot change the scheduler and when data relative to the current execution state are not accessible.

We briefly review aperiodic server algorithms. We describe the static and the dynamic exact slack computation algorithms, both theoretically optimal, and the Dynamic Approximate Slack Stealer. We present these algorithms limits in our userland context.

We then propose a simple algorithm to compute in linear time a bound on the available slack time. Since this algorithm operates only on periodic tasks beginning and ending, we show that the induced overhead can be included in these tasks worst case execution times.

The remaining side effect of our mechanism is a constant time operation to perform each time an aperiodic request occurs. This is unavoidable, even if the request is scheduled in background.

We simulate our slack stealer associated to an exact computation of the slack time and associated to our slack approximation. In order to limit the side effect of the approximation, we propose a duplication policy that simulations tend to validate. We compare our simulations with simulations on modified Polling and Deferrable servers we proposed in another publication [START_REF] Masson | The design and implementation of real-time event-based applications with rtsj[END_REF]. These modified server algorithms are also targeted for userland implementation. Our slack stealer is always the most efficient algorithm.

In our simulations, we test four aperiodic tasks queue policies and the most efficient one both for task servers and for slack stealers is the one which schedules in priority the aperiodic task with the lowest cost. This is a behavior amplified by the userland restriction: we have to schedule aperiodic tasks in one shot. Even with very high periodic loads (90%), our algorithm still brings improvements comparing with a BS.

To illustrate the aim of this work, we present an example of application: the implementation of portable task servers and slack stealers with the Real-Time Specification for Java.

We do not consider in this work systems where periodic task costs fluctuate. In such systems, a resource reservation has to be made for the worst case scenario. Each time a task completes earlier than in the worst case, gain time is generated. Even if we did not explain it in this paper, gain time can be integrated in the definition of the slack. Actually, this do not suppose any modification on our slack estimation, since it use dynamic pieces of data.

To continue this work, we will have to consider more complex systems, with resource sharing and precedence constraints. We also have to conduct experiments with real life executions in order to evaluate the exact cost of the BS duplication policy.

Figure 9 .

 9 Figure 2. MASS, 30% load

Figure 10 .

 10 Figure 10. Classes to implement the server policies

if a periodic task has a worst case execution time greater than its mean execution time, most of its executions generate reserved but unused time called gain time

periods where the processor is servicing priorities higher or equal to i

processor idle periods or periods where processor serves priorities lower than i