Mohamed Marouf
email: mohamed.marouf@inria.fr

Yves Sorel
email: yves.sorel@inria.fr

Scheduling non-preemptive hard real-time tasks with strict periods

Keywords: Hard real-time systems, Non-preemptive, Strict periods, scheduling heuristic

Non-preemptive real-time scheduling and the corresponding schedulability analyses have received considerable less attention in the research community, compared to preemptive real-time scheduling. However, nonpreemptive scheduling is widely used in industry, especially in the case of hard real-time systems where missing deadlines leads to catastrophic situations and where resources must not be wasted. In many industries such as avionics tasks may have strict periods, i.e. the start times of their executions must be separated by a fixed period. Indeed, this strict periodicity is generally required by sensors and actuators which may have accurate periods.

In this paper we consider separately the case where tasks have harmonic periods and the case where tasks have non-harmonic periods. Thus, the general case becomes a combination of both cases. In the harmonic case we give schedulability conditions to verify that a set of tasks is schedulable. In the non-harmonic case, in order to prove that a set of tasks is schedulable we propose local schedulability conditions that we apply iteratively to each task of the set in order to verify that this current task, added to a sub-set of tasks already scheduled, leads to a schedulable set of tasks.

Introduction

We consider hard real-time systems running on a uniprocessor platform where it is mandatory that all the tasks complete their executions before their deadlines. After the pioneering work of Liu and Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], a lot of works has been done in the area of hard real-time scheduling to analyze and predict the schedulability of a preemptive task set under different scheduling policies and several task models. Note that all these works assume that the cost of scheduler and particularly the cost of the preemption is approximated in the WCETs (Worst Case Execution Time) of the tasks. Although preemptive scheduling is more efficient than non-preemptive scheduling, this latter is im-portant for various reasons. Non-preemptive scheduling algorithms are easier to implement than preemptive algorithms, and can exhibit lower overhead at run-time. Preemption destroys program locality and affects the cache behavior, making the execution times more difficult to characterize and predict [START_REF] Ramaprasad | Tightening the bounds on feasible preemption points[END_REF][START_REF] Ramaprasad | Bounding worst-case response time for tasks with non-preemptive regions[END_REF]. The overhead of preemptive scheduling algorithms is more difficult to characterize and predict than that of non-preemptive scheduling algorithms. Since the scheduling overhead is often neglected in scheduling models, a non-preemptive scheduler will be closer to the model than a preemptive scheduler. In the former case, the cost of the scheduler itself could be taken into account in schedulability conditions. Contrary to non-preemptive scheduling, preemptive scheduling must guarantee the exclusive access to the shared resources and data. In automatic control applications, the input-output delay and jitter are minimized for all tasks when using a non-preemptive scheduling discipline, since there is no cost due to preemption which increases this delay [START_REF] Buttazzo | Comparative assessment and evaluation of jitter control methods[END_REF]. This simplifies the techniques for delay compensation in the control design. In many practical real-time scheduling problems involving I/O scheduling, the properties of the hardware and software either make preemption impossible of prohibitively expensive [START_REF] Jeffay | On non-preemptive scheduling of period and sporadic tasks[END_REF]. For these reasons, designers often use non-preemptive approaches even if the numerous theoretical results of the preemptive approach do not extend easily to the non-preemptive approach [START_REF] Balarin | Scheduling for embedded real-time systems[END_REF].

In hard real-time systems some sensors and actuators must have accurate periods. In order to produce (resp. receive) data at the right period, the corresponding real-time tasks must have strict periods. Strict period means that if the task τ i has the period

T i then S k i = S 1 i + (k • T i ) [7]
, where S 1 i and S k i are respectively the start time of the first and the (k) th repetitions of the task τ i , these repetitions are called jobs. On the other hand, these sensor and actuator tasks always cooperate with other tasks which may themselves have strict or non strict periods.

In this paper, in order to simplify the problem, we assume that all the periods are strict rather than a combination of strict and non strict periods.

In order to schedule a set of non-preemptive tasks with strict periods, it is enough to study the behaviors of these tasks for a time interval equal to the LCM (Least Common Multiple), called the hyper-period [START_REF] Korst | Periodic multiprocessor scheduling[END_REF].

This paper is organized as follows: in section 2 we present the related work and the strict periodic tasks model. Section 3 is devoted to the schedulability analysis for harmonic tasks. In section 4 we present the schedulability analysis for non-harmonic tasks, which is the general case of strict periodic tasks. Finally, section 5 presents a conclusion and further work.

2 Related work and tasks model

Related work

Preemption related problems have received considerable attention in the real-time community. For example there exist a lot of uniprocessor schedulability conditions for popular algorithms like RM and EDF [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. Unfortunately, these schedulability conditions become, at best, necessary conditions [START_REF] George | Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling[END_REF] in the non-preemptive case. However, non-preemption related problems must not be ignored since their resolutions may have great advantages in term of schedulability as pointed out previously. On the other hand, these problems are NP-Hard in the strong sense as Jeffay, Stanat and Martel [START_REF] Jeffay | On non-preemptive scheduling of period and sporadic tasks[END_REF] showed. Baruah and Chakraborty [START_REF] Baruah | Schedulability analysis of non-preemptive recurring real-time tasks[END_REF] analyzed the schedulability of the nonpreemptive recurring task model and showed that there exists polynomial time approximation algorithms for both preemptive and non-preemptive scheduling. Buttazzo and Cervin [START_REF] Buttazzo | Comparative assessment and evaluation of jitter control methods[END_REF] used the non-preemptive task model to reduce jitter. A comprehensive schedulability analysis of nonpreemptive systems was performed by George, Rivierre, and Spuri [START_REF] George | Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling[END_REF]. The main difference between these works and the works proposed in this paper lies in the type of periods we consider, i.e. strict periods. We remind the reader that usually periods are such that the difference between the start times of two task instances may vary whereas it is a constant in our case.

There are some works in the case of non-preemptive tasks with strict periods. Al Sheikh and al. study the partition scheduling on an IMA (Integrated Modular Avionics) platform where the avionic functions are strictly periodic. They gave an exact algorithm with excessive computation time, based on a linear programming formulation, to solve the problem. Korst and al. proved in [START_REF] Jan | Periodic multiprocessor scheduling[END_REF] a necessary and sufficient schedulability condition for two tasks, which becomes a sufficient condition for more than two tasks as proved by Kermia in [START_REF] Kermia | Schedulability analysis for non-preemptive tasks under strict periodicity constraints[END_REF]. However, as mentioned in [START_REF] Marouf | Schedulability conditions for non-preemptive hard real-time tasks with strict period[END_REF], this later condition is very restrictive. In [START_REF] Eisenbrand | Scheduling periodic tasks in a hard real-time environment[END_REF] Eisenbrand and al. proposed scheduling algorithms in the case of harmonic and non-harmonic tasks.

In this paper we first propose global schedulability conditions in the case of harmonic periods, whereas other works use local schedulability conditions, i.e. where a set of tasks is already scheduled and a new task is added to this set. In the general case of combination harmonic and non-harmonic periods, our proposed schedulability condi-tions are less restrictive than those proposed in the previous works which reject a lot of schedulable tasks.

Strict periodic tasks model

We consider real-time systems of non-preemptive tasks with strict periods. We assume that every task has a deadline equal to its period. A non-preemptive task τ i denoted by τ i (C i , T i , S 1 i ) with the strict period T i is characterized by:

• a first start time S 1 i .

• a strict period T i such as the start time of the k th instance of task τ i is given by

S k i = S 1 i + (k • T i ),
• a deadline D i equal to the period,

• a WCET (worst case execution time)

C i ≤ T i .
Afterwards, when the first start time is not given a task τ i is denoted by τ i (C i , T i ).

Figure 1 shows an example of task with a strict period. We assume that periods and WCETs are multiple of a unit of time, i.e. they are integers representing some cycles of the processor clock. If a task τ i with execution time C i is said to start at time unit t, it starts at the beginning of time unit t and completes at the end of time unit t + C i -1. Reciprocally, a time interval [t 1 , t 2 ] denotes a set of consecutive time units, given by {t 1 , t 1 + 1, ..., t 2 }.

T i C i S i 1 t T i S i 2 S i 3 C i

Scheduling harmonic tasks

Let consider a set of harmonic tasks Γ n = {τ i (C i , T i ), i = 1, ..., n}. Without any loss of generality we consider that Γ n is ordered according to the increasing values of the tasks periods, i.e. T i ≤ T j for i < j.

The schedulability analysis of harmonic tasks is a particular case of our study, in fact the GCD (Greatest Common Divisor) of all the tasks period is equal to the smallest task period T 1 and their hyper-period which is the LCM of of all the tasks period is equal to the greatest tasks period T n . We can distinguish between the three following cases:

1. all tasks have distinct periods: ∀i = j, T i = T j , 2. some tasks have the same periods: ∃i = j, T i = T j , (a) tasks with the same periods have the same WCETs, (b) tasks with the same periods have different WCETs.

The study of harmonic tasks is based on a bin tree [START_REF] Eisenbrand | Scheduling periodic tasks in a hard real-time environment[END_REF], where each bin has a size equal to the smallest period T 1 . The initial bin contains a free slot of size equal to T 1 -C 1 . At the i th iteration of the scheduling process, each parent bin has Ti Ti-1 children bins, and the final children bins number is equal to Ti Ti-1

• Ti-1 Ti-2 ••• T2 T1 = Ti T1 .
To schedule the candidate task τ i (C i , T i ), a local schedulability condition must be satisfied, i.e. there exist at least one children bin (among the Ti T1 children bins) containing a free slot of size bigger or equal to C i (figure 2).

1 1 1 ( , ) CT   2 2 2 ( , ) CT   3 3 3 ( , ) CT   3 1 2  T T 2 2 3  T T Figure 2:
Bin tree for scheduling harmonic tasks

Case of all tasks with distinct periods

Theorem (1) gives a necessary and sufficient schedulability condition for the first case.

Theorem 1 Let Γ n = {τ i (C i , T i ), i = 1, ..., n} be a set of harmonic tasks such as ∀i = j, T i = T j . Γ n is schedu- lable if and only if ∀i = 2..n, C 1 + C i ≤ T 1 (1)

Proof

We have

∀i = j, T i = T j ⇔ ∀i = 2..n, T i-1 < T i ⇔ ∀i = 2..n, Ti Ti-1 ≥ 2
Thus, each parent bin of the bin tree (figure 2) has at least two children bins.

To prove the sufficiency of the condition (1), let assume that ∀i = 2..n, C 1 + C i ≤ T 1 , we have to prove that Γ n is schedulable. We first schedule the task τ 1 (C 1 , T 1 ) and consequently obtain a free slot of size T 1 -C 1 . This parent bin has at least 2 children which contain the same free slot of size T 1 -C 1 . As T 2 ≤ T 1 -C 1 , we can schedule τ 2 in one of these children bins and thus it remains at least one child bin with a free slot of size T 1 -C 1 . This later bin will have at least 2 children which contain the same free slot of size T 1 -C 1 . As T 3 ≤ T 1 -C 1 , we can schedule τ 3 in one of these children bins and thus it remains at least one child bin with a free slot of size T 1 -C 1 . We proceed similarly until τ n .

To prove the necessity of the condition (1), we have by hypothesis a set of harmonic tasks Γ n = {τ i (C i , T i ), i = 1, ..., n} is schedulable, we have to prove that ∀i = 2..n, C 1 + C i ≤ T 1 . We first schedule the task τ 1 (C 1 , T 1 ) and consequently obtain a free slot of size T 1 -C 1 . This parent bin has at least 2 children which contain the same free slot of size T 1 -C 1 . To schedule τ 2 we must have

C 2 ≤ T 1 -C 1 .
After scheduling τ 2 we have at least one remaining bin with a free slot of size T 1 -C 1 , which is the largest free slots size among the children bins. This later bin will have at least 2 children bin which contain the same free slot of size T 1 -C 1 , thus to schedule τ 3 we must have C 3 ≤ T 1 -C 1 . We proceed similarly until τ n , and finally we have ∀i = 2..n,

C i ≤ T 1 -C 1 which gives ∀i = 2..n, C 1 + C i ≤ T 1 . ⊡ 3.

Case of some tasks with same periods

We first study the case where some tasks have the same periods and the same WCETs. Let consider a set of tasks

Γ n = {τ i,j (C i,j , T i,j ), i = 1..n, j = 1..m i } where C i,j = C i and T i,j = T i for j = 1..m i and ∀i = 2..n, T i = T i-1 .
Γ n contains m i tasks with the same period T i and the same WCET C i . The following theorem gives a local sufficient schedulability condition for this set of tasks.

Theorem 2 A set of harmonic tasks Γ n = {τ i,j (C i,j , T i,j ), i = 1..n, j = 1..m i } where C i,j = C i and T i,j = T i for j = 1..m i and ∀i = 2..n,

T i = T i-1 is schedulable if a n ≥ 0 and ∀i = 1..n -1, a i > 0 (2)
where

a 1 = T 1 -m 1 • C 1 T 1 and
a i = a i-1 • T i T i-1 -     m i T1-m1•C1 Ci     , i = 2..n Proof Let consider a set of tasks Γ n = {τ i,j (C i,j , T i,j ), i = 1..n, j = 1..m i } where C i,j = C i and T i,j = T i for j = 1..m i and ∀i = 2..n, T i = T i-1 . The m 1 tasks τ 1,j are schedulable if T 1 > m 1 • C 1 .
Thus, the first bin that we call the initial bin, contains one free slot of size equal to T 1 -m 1 •C 1 . Let a i be the number of bins with a free slot of size equal to T 1m 1 • C 1 .

For i = 1, the number of initial bin is equal to 1, and thus a 1 = 1.

For i = 2, a children bin can contain T1-m1•C1 C2 tasks τ 2,j , so l 2 children bins can contain the m 2 tasks τ 2,j where

l 2 =     m 2 T1-m1•C1 Ci     .
Thus, the number of available children bins identical to the initial bin is equal to

a 2 = T 2 T 1 -     m 2 T1-m1•C1 C2    
If a 2 > 0 then we have at least one children bin identical to the initial bin.

For i = 3, we have a 2 bins identical to the initial bin which have a 2 • T3 T2 children bin identical to the initial bin, so l 3 children bins can contain the m 3 tasks τ 3,j where

l 3 =     m 3 T1-m1•C1 C3     .
Thus, the number of available bins identical to the initial bin is equal to

a 3 = a 2 • T 3 T 2 -     m 3 T1-m1•C1 C2    
If a 3 > 0 than we have at least one children bin identical to the initial bin.

For i = k, we assume that a k-1 > 0. we have a k-1 bins identical to the initial bin which have a k-1

• T k T k-1
children bin identical to the initial bin, so l k children bins can contain the m k tasks τ k,j where

l k =     m k T1-m1•C1 C k     .
Thus, the number of available bins identical to the initial bin is equal to

a k = a k-1 • T k T k-1 -     m k T1-m1•C1 C k    
In order to schedule the m k+1 tasks τ k+1,j , we shall have at least one available bin identical to the initial bin, and thus a k > 0 Finally, for i = n, a n can be equal to 0 because τ n,j are the last tasks so we do not need any available bins to schedule other tasks, and thus a n ≥ 0.

⊡

The following theorem gives a global schedulability condition based on the condition (2).

Theorem 3 A set of harmonic tasks Γ n = {τ i,j (C i,j , T i,j ), i = 1..n, j = 1..m i } where C i,j = C i and T i,j = T i for j = 1..m i and ∀i = 2..n,

T i = T i-1 is schedulable if T n T 1 - n i=2 T n T i-1     m i T1-m1•C1 Ci     > 0 (3) with T 1 -m 1 • C 1 > 0. Proof Let consider α i = Ti Ti-1 and β i = m k T 1 -m 1 •C 1 C i for i = 2..n. Thus a i = α i • a i-1 -β i .
As α i > 0 and β i > 0 we have

a n > 0 ⇒ α n • a n-1 -β n > 0 ⇒ α n • a n-1 > β n ⇒ α n • a n-1 > 0 ⇒ a n-1 > 0 (4) so (a n > 0) ⇒ (a n-1 > 0) ⇒ ... ⇒ (a 2 > 0) ⇒ (a 1 > 0) then ∀i = 1..n, a i > 0 ⇔ a n > 0 a n = α n ...α 2 • a 1 -α n ...α 3 • β 2 -... -α n • β n-1 -β n = a 1 n i=2 α i - n i=2 β i n j=i α i as a 1 = 1 and b i=a α i = T a T a-1 • T a+1 T a ... T b-1 T b-2 • T b T b-1 = T b T a-1 then a n = T n T 1 - n i=2 T n T i-1 β i a n = T n T 1 - n i=2 T n T i-1     m i T1-m1•C1 Ci     Finally, a n > 0 ⇔ ∀i = 1..n, a i > 0 ⇔ condition (3)

⊡

In the general case of harmonic tasks where some tasks may have the same periods but different WCETs, we have the following corollary which is an extension of the theorem 3.

Corollary 1 A set of harmonic tasks Γ n = {τ i,j (C i,j , T i,j ), i = 1..n, j = 1..m i } where ∀j = 1..m i , T i,j = T i and ∀i = j, T i = T j is schedulable if

T n T 1 - n i=2 T n T i-1     m i T1-m1•C1 Ci     > 0 (5)
where

T 1 -m 1 • C 1 > 0 and C i = max j=1..mi C i .

Scheduling non-harmonic tasks

In this section we study the schedulability of a set of tasks in the general case where periods are not necessarily harmonic. Korst and al. proved in [START_REF] Jan | Periodic multiprocessor scheduling[END_REF] that two tasks τ 1 (C 1 , T 1 ) and τ 2 (C 2 , T 2 ) are schedulable if and only if:

C 1 + C 2 ≤ GCD(T 1 , T 2 ). (6)
It has been proved in [START_REF] Kermia | Schedulability analysis for non-preemptive tasks under strict periodicity constraints[END_REF][START_REF] Marouf | Schedulability conditions for non-preemptive hard real-time tasks with strict period[END_REF] that the necessary and sufficient schedulability condition (6) becomes a sufficient condition in the case of more than two tasks, thus a set of tasks

Γ = {τ i (C i , T i ), i = 1..n} is schedulable if: n i=1 C i ≤ GCD(∀i, T i ). (7)
We distinguish in our study the three following cases:

1. Tc g even number 2. Tc g odd number 3. general case where g is the GCD of all the periods tasks, and T c is the period of the candidate task as explained in section 4.1.

We distinguish three cases: Tc g even and odd numbers and the general case which is a combination of these two cases. In this case, in order to prove that a set of tasks is schedulable we propose local schedulability conditions that we apply iteratively to each task of the set in order to verify that this current task, added to a sub-set of tasks already scheduled, leads to a schedulable set of tasks.

Scheduling strategy

We consider a set of n tasks Γ n = {τ i (C i , T i ), i = 1..n} and a subset Γ ′ of Γ n containing the tasks that satisfies the schedulability condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF]. We call g the GCD of the periods T i of all the tasks τ i belonging to Γ ′ . Γ ′′ = Γ n \Γ ′ is the complementary set of Γ ′ in Γ n such as ∀τ i ∈ Γ ′′ , the tasks of Γ ′ ∪ {τ i } do not satisfy the condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF]. In order to verify if a set of tasks Γ n is schedulable, we first build the set of tasks Γ ′ then the scheduling process operates iteratively as follows: for each task τ c of Γ ′′ , called candidate task, we apply a local schedulability condition presented below, to the set of tasks Γ ′′ ∪ {τ c }. If this condition is satisfied then the schedulable set of tasks is Γ ′ ∪ {τ c } else the schedulable tasks set is Γ ′ . Finally, we obtain the subset of schedulable tasks

Γ ′ ∪ Γ ′′ s ⊆ Γ ′′ .
In this section, all the theorems are based on the computation of these free slots that we call periodic free slots.

Definition 1 We call a periodic free slot φ(C, T ) a free slot of size C ≤ T which is indefinitely repeated with a period T .

The following example illustrates the free periodic slots after scheduling three tasks. Example Let consider the set of tasks Γ 3 = {τ 1 (1, 3), τ 2 [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Balarin | Scheduling for embedded real-time systems[END_REF], τ 3 (1, 9)} to be scheduled.

As 7) is satisfied and thus Γ 3 is schedulable as shown in the figure 3.

C 1 + C 2 + C 2 = 3 ≤ GCD(T 1 , T 2 , T 3 ) = 3, the condition (
As we can see, there is one periodic free slot φ 1 (1, 6) and two periodic free slots φ 2,3 [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] George | Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling[END_REF]. Here we give a schedulability condition when ( Tc g ) is an odd number, i.e. ∃k ∈ N * , T c = (2

1 1  2 1  3 1  4 1  5 1  1 2  2 2  3 2  1 3  2 3  6 1  7 1  4 2  3 3  0 3 6 9 12 15 18 1 1  2 1  3 1  1 2  1 3  2 2
• k + 1) • g. Theorem 4 Let Γ n = {τ i (C i , T i ), i = 1, ...,
n} be a set of tasks scheduled according to the condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF]. A candidate task τ c is schedulable if ∃τ i ∈ Γ n such as

C c ≤ C i • δ (T c mod(T i )) (8)
where mod is the modulo function and δ is the Kronecker symbol:

δ(i) = 1 if i = 0 0 otherwise The condition (8) is equivalent to C c ≤ C i and T c mod(T i ) = 0. Proof Let Γ n = {τ i (C i , T i ), i = 1, ...,
n} be a set of tasks scheduled according to the condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF]:

n i=1 C i ≤ GCD(∀i, T i ).
Each instance τ k i is executed in the time interval

I k i = [kT i + S 1 i , kT i + S 1 i + C i [
Let n i = Ti g , then

I k i = [(kn i )g + S 1 i , (kn i )g + S 1 i + C i [
Thus, in each time interval [mg, (m + 1)g[ of length g, an instance τ k i can be executed in the time interval

[mg + S 1 i , mg + S 1 i + C i [⊂ [mg, (m + 1)g[. So if we schedule the first instances of the tasks τ i into the time interval [0, g[ such as: S 1 1 = 0, S 1 i = (i-1)
k=1 C k , then there will be no overlaps between the tasks τ i ∈ Γ n . This is a short proof of the sufficiency of the condition 7.

Now let consider a task τ i such as

τ 1 i is executed into the time interval [0, g[: 0 ≤ S 1 i < g -C i .
The second instance of this task will be executed after ( Ti g ) time intervals of length g. Thus, it will leave ( Ti g -1) unused (free) time intervals

[mg + S 1 i , mg + S 1 i + C i [. Let φ(C i , T i ) be a periodic free slot with start times S φ = S 1 i + mg, 1 ≤ m ≤ ( Ti g -1)
. These periodic free slots do not overlap the instances τ k i because they have the same period T i .

To schedule the task τ c into φ we must guarantee that C c ≤ C i and the period T c is multiple of the period of φ T i , thus T c mod(T i ) = 0.

⊡ Theorem 5 Let Γ n = {τ i (C i , T i ), i = 1, ...,
n} be a set of tasks scheduled according to the condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF], and τ c a candidate task which satisfies the condition [START_REF] Korst | Periodic multiprocessor scheduling[END_REF]. τ c can be scheduled N c times with the initial start times S 1 c given by

     N c = Tc Ti ( Ti g -1) Ci Cc S 1 c = S 1 i + k • g + l • T i + m • C c (9) with              1 ≤ k ≤ Ti g -1 0 ≤ l ≤ Tc Ti -1 0 ≤ m ≤ Ci Cc -1

Proof

As shown in the previous proof, the instances τ k c are scheduled into periodic free slots φ(C i , T i ), thus one free slot can contain

N ′ c = C i C c instances τ k c
, and the possible start times of these instances are given by

S ′1 c = S 1 i + m • C c
where 0 ≤ m ≤ Ci Cc -1. As there are ( Ti g -1) free slots in [0, T i [, thus

N ′′ c = ( T i g -1)N ′ c = ( T i g -1) C i C c
These free slots are separated by a time interval g, thus

S ′′1 c = S ′1 c + k • g = S 1 i + k • g + m • C c with 1 ≤ k ≤ Ti g -1.
The τ k c is now scheduled on a time interval T i . If Tc Ti > 1 then there are Tc Ti time intervals of length T i where we can also schedule the instances τ k c . Thus

N c = T c T i N ′′ c = T c T i ( T i g -1) C i C c
and the initial start times are given by

S 1 c = S ′′1 c + l • T i = S 1 i + k • g + l • T i + m • C c with 0 ≤ l ≤ Tc Ti -1. ⊡ 4.
3 Case of Tc g even number

Here we give a schedulability condition and the corresponding initial start times, when ( Tc g ) is even number, i.e. ∃k ∈ N, T c = 2 • k • g. This case is a little different from the previous one.

Theorem 6 Let Γ n = {τ i (C i , T i ), i = 1, ..., n} be a set of tasks scheduled according to the condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF]. A candidate task τ c is schedulable if ∃τ i ∈ Γ n such as

C c ≤ C i • δ (T c mod(2g) + T i mod(2g)) (10)
The condition ( 10) is equivalent to C c ≤ C i and T c mod(2g) = T i mod(2g) = 0. Proof Let Γ n = {τ i (C i , T i ), i = 1, ..., n} be a set of tasks scheduled according to the condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF]. Let τ i be a task of Γ n such as T i mod(2g) = 0, and τ c the candidate task. Let n i = Ti 2g . The start times of the free slots of τ i are given by:

S k = S 1 i + kg
where 1 ≤ k ≤ Ti g -1, which can be written as

S k φ ∈ {S 1 i + (2k + 1) • g, ∀k ≥ 0}∪ {S 1 i + 2k • g, ∀k ≥ 1, k mod(n i ) = 0} The first interval I 1 = {S 1 i + (2k + 1) • g, ∀k ≥ 0} describes a periodic free slot φ(C i , 2g) with a start time S φ = S 1 i + g . However, I 2 = {S 1 i + 2k • g, ∀k ≥ 1, k mod(n i ) = 0}
can not contain one periodic free slot because its periodicity is broken for k mod(n i ) = 0, thus we have ( Ti 2g -1) periodic free slots φ(C i , T i )

with the start times

S φ = S 1 i + (2k)g, k = 1..( T i 2g -1) Thus τ c is schedulable if C c ≤ C i and T c multiple of T i or 2g. As T i is multiple of 2g, then τ c is schedulable if C c ≤ C i and T c multiple of 2g. ⊡ Theorem 7 Let Γ n = {τ i (C i , T i ), i = 1, ...,
n} be a set of tasks scheduled according to the condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF], and τ c a candidate task which satisfies the condition [START_REF] Baruah | Schedulability analysis of non-preemptive recurring real-time tasks[END_REF]. τ c can be scheduled N c times with the initial start times S 1 c given by if T c mod (T i ) = 0:

N c = Tc Ti ( Ti g -1) Ci Cc S 1 c = S 1 i + k • g + l • T i + m • C c (11) with              1 ≤ k ≤ Ti g -1 0 ≤ l ≤ Tc Ti -1 0 ≤ m ≤ Ci Cc -1 if T c mod (T i ) = 0 and T c mod (2g) = 0: N c = Tc 2g Ci Cc S 1 c = S 1 i + (2k + 1) • g + m • C c (12) with      0 ≤ k ≤ Tc 2g -1 0 ≤ m ≤ Ci Cc -1

Proof

For T c mod (T i ) = 0, the proof is similar to the one of theorem 5.

For T c mod (T i ) = 0 and T c mod (2g) = 0: As we have seen in the proof of theorem 6, a scheduled task τ i generates one periodic free slot φ(C i , 2g) and ( Ti 2g -1) periodic free slot φ(C i , T i ).

As T c mod(T i ) = 0, we can not use φ(C i , T i ) to schedule the instances τ k c . However, we can use φ(C i , 2g):

φ(C i , 2g) generates N ′ c = T c 2g periodic free slot φ(C i , ( Tc 2g )2g) = φ(C i , T c ).
We have seen that the start time of φ(C i , 2g) is S φ = S 1 i + g, thus the start times of φ(C i , T c ) are given by

S ′ φ = S 1 i + (2k + 1)g, 0 ≤ k ≤ T c 2g - 1
Into each free slot of φ(C i , T c ) we can schedule Ci Cc tasks τ c , thus the number of schedulable tasks τ c is equal to

N c = N ′ c C i C c = T c 2g C i C c
and the initial start times of τ c are given by

S 1 c = S ′1 c + m • C c = S 1 i + (2k + 1) • g + m • C c , 0 ≤ m ≤ T c 2g - 1

General case

The following theorem is a combination of the theorem 4 and theorem 6.

Theorem 8 Let Γ n = {τ i (C i , T i ), i = 1, ..., n} be a set of tasks that satisfy the condition [START_REF] Cucu | Schedulability condition for systems with precedence and periodicity constraints without preemption[END_REF]. Let τ c be the task to be scheduled. τ c is schedulable if: Thus the task τ 3 is schedulable.

C c ≤ n i=1 C i • δ [T c mod(T i ) • (T c mod(2g) + T i mod(2g))] . (13
As T 3 mod(T 2 ) = 6 = 0, then according to the condition [START_REF] Eisenbrand | Scheduling periodic tasks in a hard real-time environment[END_REF] we have

Conclusion and further work

In this paper we presented a schedulability analysis in the case of non-preemptive tasks with strict periods. We started by studying schedulability analysis for harmonic tasks and gave a schedulability condition for different cases. For non-harmonic tasks we gave a local schedulability condition which assumes that a set of task is already scheduled and a new task is to be scheduled. We also gave the scheduling conditions for each case and illustrate them by an example.

An interesting problem will be to study the scheduling analysis for strict periodic tasks onto multiprocessor platforms.

Figure 1 :

 1 Figure 1: Model for non-preemptive task with a strict period

 2 3 Figure 3 :

 33 Figure 3: Scheduling diagram and periodic free slots

  ) whith T i > g.ExampleLet consider a set of six tasks Γ = {τ 1 (2, 9), τ 2[START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Kermia | Schedulability analysis for non-preemptive tasks under strict periodicity constraints[END_REF], τ 3 (1, 18), τ 4 (1, 27)}.As g = GCD(9, 12) = 3 and C 1 + C 2 = 3, the condition (7) is satisfied:C 1 + C 2 ≤ GCD(T 1 , T 2 ). However, it is not satisfied neither by {τ 1 , τ 2 , τ 3 } nor by {τ 1 , τ 3 , τ 4 }:C 1 + C 2 + C 3 = 4 ≤ GCD(T 1 , T 2 , T 3 ) = 3 and C 1 + C 2 + C 4 = 4 ≤ GCD(T 1 , T 2 , T 4 ) = 3 So Γ ′ = {τ 1 (2, 9), τ 2 (1, 12)} and Γ ′′ = {τ 3 (1, 18), τ 4 (1, 27)}.Let S 1 1 = 0 and S 1 2 = 2. For τ c = τ 3 , the condition[START_REF] Baruah | Schedulability analysis of non-preemptive recurring real-time tasks[END_REF] is satisfied by τ 2 and τ c : C c = 1 and C 2 • δ (T c mod(2g) + T 2 mod(2g)) = 1 • δ (18mod(6) + 12mod(6)) = 1.

N 3 1 )N 4

 314 • g + m • C c = 2 + 3(2k + 1) = 6k + 5[START_REF] Eisenbrand | Scheduling periodic tasks in a hard real-time environment[END_REF] with 0 ≤ k ≤ ( T3 2g -1 = 2) τ 3 is scheduled with S 1 3 = 2 + 3(1) = 5, and we consider two periodic free slots φ(1, 18) with the start times S φ ∈ {11, 17}For τ c = τ 4 , the condition (8) is satisfied by τ 1 and τ c :C c = 1 and C 1 • δ (T c mod(T 1 )) = 2 • δ (27mod(9)) = 2.Thus, the task τ 4 is schedulable.According to the condition(9), we have 6, 7, 12, 13, 15, 16, 21, 22, 24, 25}. Let S 1 4 = 3 and we consider 11 periodic free slots φ(1, 27) with the start times S φ ∈ {4, 6, 7, 12, 13, 15, 16, 21, 22, 24, 25}.


Mohamed Marouf
email: mohamed.marouf@inria.fr

Laurent George
email: laurent.george@inria.fr

Yves Sorel
email: yves.sorel@inria.fr

Schedulability analysis for a combination of non-preemptive strict periodic tasks and preemptive sporadic tasks

come

Introduction

We consider the problem of scheduling nonpreemptive strict periodic tasks combined with preemptive sporadic tasks.

Strict periodic tasks are typically in charge of sensor/actuator or feedback control functions. The freshness of the information they use and/or the reactivity of the system are constrained. Indeed, for such tasks it is important to control their jitters (the difference between the worst case and the minimum response times) to ensure the system's stability [START_REF] Marti | Jitter compensation for real-time control systems[END_REF][START_REF] Lincoln | Jitter compensation in digital control systems[END_REF][START_REF] Behnam | Real-time control design for flexible scheduling using jitter margin[END_REF][START_REF] Balbastre | Minimum deadline calculation for periodic real-time tasks in dynamic priority systems[END_REF].

We consider the Fixed Priority (FP) scheduling. We assume that all non-preemptive strict periodic tasks have the same highest fixed priority, whereas preemptive sporadic tasks have lower (distinct) fixed priority than strict periodic tasks. Afterwards, for the sake of clarity, we shall use the term "strict periodic tasks" for "non-preemptive strict periodic tasks", and "sporadic tasks" for "preemptive sporadic tasks".

In section 2, we first recall related work for strict periodic and sporadic tasks scheduling, and for fault-tolerant scheduling, then, we give the non-preemptive strict periodic task model. In section 3, we recall a necessary and sufficient schedulability condition for non-preemptive strict periodic tasks, and investigate the transient and permanent phases for such tasks. In section 4 we show how to determine the worst case scenario for a sporadic task where its Worst Case Response Time (WCRT) can be obtained, in the presence of strict periodic tasks. We prove that these release times belong only to the permanent phase of strict periodic tasks, and thus that the schedulability analysis for sporadic tasks can be restricted to the permanent phase. For preemptive sporadic tasks, we extend the classical necessary and sufficient schedulability condition based on the worst case response time computation [START_REF] Joseph | Finding response times in a real-time system[END_REF] to take into account non-preemptive strict periodic tasks. Finally, in section 5, we consider faulttolerance in the particular case where each primary strict periodic task has an alternate sporadic task which is released when its primary task fails.

Related work

Preemptive scheduling has received considerable attention in the real-time community. However, we can notice that non-preemptive scheduling has received less attention from the real-time community.

Yet, non-preemptive scheduling problems should not be ignored since their resolutions may have great advantages in terms of schedulability. On the other hand, these problems are NP-Hard in the strong sense as Jeffay, Stanat and Martel [START_REF] Jeffay | On nonpreemptive scheduling of period and sporadic tasks[END_REF] showed.

Baruah and Chakraborty [START_REF] Baruah | Schedulability analysis of non-preemptive recurring real-time tasks[END_REF] analyzed the schedulability of the non-preemptive recurring task model and showed that there exists polynomial time approximation algorithms for both preemptive and non-preemptive scheduling. Buttazzo and Cervin [START_REF] Buttazzo | Comparative assessment and evaluation of jitter control methods[END_REF] used the nonpreemptive task model to reduce the jitter of the tasks. A comprehensive schedulability analysis of non-preemptive systems was performed by George, Rivierre, and Spuri in [START_REF] George | Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling[END_REF]. The main difference between these works and the works proposed in this paper lies in the type of periods we consider for strict periodic tasks, i.e. strict periods. In the classical periodic model, the difference between the start times of two tasks jobs may vary whereas it must be a constant for strict periodic tasks.

Korst et al. proved in [START_REF] Korst | Periodic multiprocessor scheduling[END_REF] a necessary and sufficient schedulability condition for two tasks which can be generalized for more than two tasks. In [START_REF] Eisenbrand | The periodic maintenance problem[END_REF] Eisenbrand et al. proposed scheduling algorithms in the case of harmonic and non-harmonic strict periodic tasks. We proposed in [START_REF] Marouf | Schedulability conditions for non-preemptive hard real-time tasks with strict period[END_REF][START_REF] Marouf | Scheduling non-preemptive hard real-time tasks with strict periods[END_REF] a schedulability analysis for such tasks.

Software fault-tolerance has been considered through the primary/alternate task models. When a primary task cannot meet its deadline, an alternate task is run. The alternate task can be the same task (the task is re-executed). In [START_REF] Burns | Feasibility analysis of fault-tolerant real-time task sets[END_REF], Burns et al. give a feasibility condition for sporadic tasks in the case of fixed priority scheduling. Faults are assumed to be detected at the completion time of the tasks. A task can only affect one task at a time. An alternate task is run to re-execute the faulty task. In [START_REF] Ghosh | Faulttolerant rate-monotonic scheduling[END_REF], Ghosh et al. consider a recovery mechanism to re-execute faulty tasks. They propose to use the available slack time to reexecute a faulty task in the case of RM scheduling. In [START_REF] Han | A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults[END_REF], Han et al. consider software faults for primary tasks in the case of periodic tasks scheduled with RM. Primary tasks are more complex functions whose correctness is deemed more difficult to check.

Systems models

A non-preemptive strict periodic task τ i is denoted τ i (S 0 i , C i , D i , T i ), where:

• S 0 i is the first release time of τ i • C i the WCET (Worst Case Execution Time) of τ i • D i is the relative deadline of τ i • T i is the strict period of τ i .
The start time of the k th job of a strict periodic task τ i is given by S k i = S 0 i + k • T i . Figure 1 shows an example of a strict periodic task.

T i C i S i 0 T i S i 1 S i 2 C i D i D i Figure 1. Model for non-preemptive strict periodic task τ i (S 0 i , C i , D i , T i )
A preemptive sporadic task is non-concrete, i.e. its first release time can be chosen arbitrarily. A preemptive sporadic task τ i is therefore denoted (w.r.t. the strict periodic task model) τ i (C i , D i , T i ). T i is the minimum interarrival time between two successive jobs of τ i . We consider the case D i ≤ T i for sporadic tasks.

The scheduling used in this paper is Fixed Priority (FP) scheduling. Tasks in Γ S have the same highest priority while all tasks in Γ N S have distinct lower priority tasks. Furthermore, we assume that task parameters are integers multiple of the tick time.

3 Scheduling strict periodic tasks

Necessary and sufficient schedulability condition

For the sake of clarity, we use this notification g i,j for the gcd (Greatest Common Divisor) of two periods T i , T j : g i,j = gcd(T i , T j ).

Korst et al. gave in [START_REF] Korst | Scheduling periodic tasks[END_REF] a necessary and sufficient schedulability condition for a task set. It consists of applying a necessary and sufficient condition valid for only two tasks to all possible pairs of tasks.

Theorem 1 A task set Γ S = {τ i (S 0 i , C i , D i , T i ), i = 1,
n} is schedulable if and only if for all pairs of tasks (τ i , τ j ) satisfy the condition

C i ≤ (S 0 j -S 0 i )mod g i,j ≤ g i,j -C j (1)
Now we characterize the transient and the permanent phases of the schedule considering only strict periodic tasks.

Transient and permanent phases

The transient phase Φ = [0, φ[ ends at a time φ ≥ 0, which is the smallest time such that the release times obtained in any time interval [φ + kL, φ + (k + 1)L[, k ∈ N * , relatively to φ + kL, are the same as those obtained in the time interval [φ, φ + L[, relatively to φ. By definition, L is the length of the permanent phase.

The following theorem gives the time interval corresponding to transient phase obtained for the schedule of strict periodic tasks.

Theorem 2 We consider a schedule of strict periodic tasks. The transient phase Φ of this schedule is the time interval given by: Φ = [0, φ[, where

φ = M ax(0, M ax i=1..n S 0 i + C i -T i ) (2)
Proof φ is the smallest integer such as the first permanent phase

[φ, φ + L] contains ( L Ti ) jobs of each task τ i . Thus the ( L Ti -1) th job of τ ( L T i
-1) i must end its execution before (φ + L), thus

S 0 i + ( L T i -1)T i + C i ≤ φ + L thus φ ≥ S 0 i + C i -T i . (3)
Furthermore, for any task τ i , its relative start time according to φ must be equal to its relative start time according to φ + L.

The relative start time according to φ is given by

S 0 i + φ -s i T i T i -φ.
The relative start time according to φ + L is given by

S 0 i + (L + φ) -s i T i T i -(L + φ) = S 0 i + φ -s i T i T i + L -L -φ = S 0 i + φ -s i T i T i -φ.
These two relative start times are thus equal. As φ is the smallest integer which satisfies condition

(3) then φ = M ax i=1,...,n (0, s i + C i -T i ).

Combining strict periodic and sporadic tasks

In this section, we study the schedulability of a combination of strict periodic and sporadic tasks. We assume that a set of non-preemptive strict periodic tasks have already been scheduled with the highest priority, and a set of preemptive sporadic tasks is to be scheduled with lower (but different) priorities.

We use the following notations:

• Γ S (resp. Γ N S ) denotes the task set corresponding to strict periodic (respectively sporadic) tasks.

• hp N S (i) denotes the set of tasks in Γ N S having higher priority than a task τ i in Γ N S .

Schedulability analysis for sporadic tasks

In order to study the schedulability of sporadic tasks when tasks with strict periods have been scheduled, we have to determine the critical instants for a sporadic tasks where the WCRT can be reached.

It has been proved in [START_REF] Joseph | Finding response times in a real-time system[END_REF] that a critical instant occurs when the release time of a sporadic task is equal to the release time of all higher priority tasks. As strict periodic tasks have all higher priority than all the sporadic tasks, we define the set of critical instants Ψ which contains all the start times of the strict periodic jobs in the transient and the permanent phases: [0, φ + L[.

To consider tasks with strict periods, we have to study all cases of release times in Ψ and compute the WCRT of a sporadic task τ i when its first release time corresponds to the release time of a strict periodic task. For a sporadic task τ i , this results in first releasing, at the release time of a strict periodic task in Ψ all higher priority sporadic tasks than τ i at the same time. However, rather than testing all the release times of strict periodic tasks in Ψ, some release times are useless and will be thus removed from Ψ according to lemma 1.

Lemma 1 Consider a sequence of consecutive executions of strict periodic tasks with no slack between the executions. Then only the release time of the first strict periodic task in the sequence should be considered for the computation of worst case response time of a sporadic task.

Proof

Consider a sequence seq of consecutive executions of strict periodic tasks corresponding to a subset of tasks in Γ S . Let 0 be the time origin corresponding to the release time of the first strict periodic tasks in the sequence seq. As sporadic tasks have smaller priority than strict periodic tasks, a sporadic task released at time t i ≥ 0 can start its execution only when all strict periodic tasks in seq are completed and will terminate at the same time for any release time t i belonging to [0, duration(seq)], where duration(seq) is the sum of the execution times of all strict periodic tasks in seq. The response time of a sporadic task is therefore maximum when a sporadic task is released at time 0. Hence the lemma.

Thus, if ∃S k i , S l j ∈ Ψ such as S k i -S l j = C j , then S k i is removed from Ψ.
Finally, we limit the release times in Ψ only to the release times of strict periodic tasks in the permanent phase according to lemma 2.

Lemma 2 In the set Ψ, only the release times which belong to the permanent phase of strict periodic tasks should be considered to study the WCRT of sporadic tasks.

Proof

For strict periodic tasks, the time interval [L, φ + L[ in the permanent phase contains the release time pattern corresponding to all the release times of the transient phase [0, φ[. The transient phase may contain less jobs than in the permanent phase. Thus, jobs of the permanent phase are more critical than those of the transient phase for sporadic tasks.

The following theorem gives the computational requirements at time t for a sporadic task τ i released at time S ∈ Ψ.

Theorem 3 Consider a strict periodic task set Γ S and a sporadic task set hp N S (i) already scheduled. Let τ i be a sporadic task released at time S ∈ Ψ. The sum of the computational requirements at time t (w.r.t time S) are given by

W i (t) = C i + τj ∈hp N S (i) t T j C j + τj ∈Γ S t -s j T j C j (4
) where s j is the relative start time S k j according to a release time S given by

s j = S 0 j + S -S 0 j T j T j -S (5)

Proof

Consider that a sporadic task τ i is first released at time S ∈ Ψ. The sum of the computational requirements at time t (w.r.t time S) W i (t) is the sum of the following computational requirements:

1. one execution of τ i starting at time S: C i ;

2. all strict periodic tasks (all with higher priority than τ i ):

τj ∈Γ S t -s j T j C j ;
3. all sporadic tasks with higher priority than τ i :

τj ∈hp N S (i) t T j C j .
The following theorem gives a schedulability necessary and sufficient for set of sporadic task.

Theorem 4 Consider a strict periodic task set Γ S already scheduled. A sporadic task set Γ N S is schedulable if and only if

∀τ i ∈ Γ N S : R i ≤ D i ( 6
)
where R i is the WCRT of τ i ∈ Γ N S , which is the solution of R i = W (R i ) computed by iteration.

Proof

The proof is identical to the one given in [START_REF] Joseph | Finding response times in a real-time system[END_REF] which states that the Worst Case Response Time of any task should be less than or equal to its deadline.

Example

We use the Rate-Monotonic algorithm to schedule the following tasks. Consider the strict periodic task set Γ S = {τ 1 (0, 1, 4, 4), τ 2 (1, 1, 6, 6), τ 3 (2, 1, 12, 12)}, and the sporadic task set Γ N S = {τ 4 (2, 6, 8), τ 5 [START_REF] Baruah | Schedulability analysis of non-preemptive recurring real-time tasks[END_REF][START_REF] Korst | Scheduling periodic tasks[END_REF][START_REF] Korst | Scheduling periodic tasks[END_REF]} to be scheduled.

For (τ 1 , τ 2 ), g 1,2 = 2 and condition (1) is satisfied:

1 ≤ (1 -0)mod2 ≤ 2 -1 =⇒ 1 ≤ 1 ≤ 1.
For (τ 1 , τ 3 ), g 1,3 = 4 and condition (1) is satisfied:

1 ≤ (2 -0)mod4 ≤ 4 -1 =⇒ 1 ≤ 2 ≤ 3.
For (τ 2 , τ 3 ), g 2,3 = 6 and condition (1) is satisfied:

1 ≤ (2 -1)mod6 ≤ 6 -1 =⇒ 1 ≤ 1 ≤ 5.
Thus, Γ S is schedulable. According to theorem 2, the schedule of Γ S has no transient phase. The permanent phase starts at time 0 and has a length L = lcm(T 1 , T 2 , T 3 ) = 12, thus Ψ = {0, 1, 2, 4, 7, 8} corresponding to the release times of tasks Γ S in the time interval [0, L[. After pruning the release times of strict periodic tasks according to lemma 1 we have: Ψ = {0, 4, 7}.

From theorem 3 we have:

W 4 (t) = 2 + t -

Extension to fault-tolerance

We consider a task set of non-preemptive strict periodic tasks (control tasks, sensors/actuators tasks, etc.) and preemptive sporadic tasks (asynchronous events outside the embedded computer, etc.). For reliable systems, we proposed to use an alternate sporadic tasks for the primary strict periodic tasks, in such a way that when a primary non-preemptive strict periodic task fails, an alternate preemptive sporadic task is released. We suppose that faults occurs during the execution of primary tasks, and alternate tasks must meet the absolute deadlines of their primary task.

In this section we consider that sporadic tasks are composed of alternate tasks and independent sporadic tasks.

Primary strict periodic tasks have higher priority than alternate tasks that have higher priority than sporadic tasks. Both sporadic task sets are scheduled using RM or DM algorithms.

Figure 3 shows a primary task with three faults occurring: during the execution of the first job, during the execution of the third job and at the beginning of the execution of the forth job.

Figure 3. A primary strict periodic task with its alternate sporadic tasks

The worst case which minimizes the relative deadline of an alternate job is obtained when the fault of its primary job occurs at the end of its execution. As shown in figure 3, the minimal relative deadline D min and minimal inter-arrival time T min are obtained when a fault occurs at the the end of execution of a job and the next fault occurs at the release time of the next job. In that case we have:

D min = D i -C i and T min = T i -C i .
For this reason we consider that for each primary task τ i (S 0 i , C i , D i , T i the alternate task, denoted τ i,a has an execution time C i,a ≤ D i -C i , a relative deadline D i,a = D i -C i , and a minimal inter-arrival time

(T i -C i ). It is given by τ i (S 0 i,a , C i,a , (D i -C i ), (T i -C i )), with S 0 i ≤ S 0 i,a ≤ S 0 i + C i .

Schedulability analysis for alternate tasks

In this section we study the schedulability of a combination of primary strict periodic tasks and their alternate sporadic tasks.

We use the following notations:

• Γ S (resp. Γ N S a ) denotes the task set corresponding to primary strict periodic (resp. alternate sporadic) tasks.

• hp N S a (i) denotes the set of tasks in Γ N S a having higher priority than a task τ i,a in Γ N S .

In order to consider the worst case response time for an alternate task, we consider that all its primary jobs fails at the end of their executions, which mean that each primary job is entirely executed before releasing the alternate job. Thus, the critical instants for each alternate task τ i,a are obtained for t = S k i + C i , where S k i belongs to the permanent phase. Thus, the critical instants of each alternate task τ i,a is given by

Ψ i = {S k i + C i , φ ≤ S k i < φ + L}.
In order to compute the worst case response time of an alternate job τ k i,a , we introduce the following theorem which gives the computational requirements at time t for an alternate task τ i,a released at time S ∈ Ψ i .

Theorem 5 Let τ i,a be an alternate task of a primary task τ i . τ i,a is released at time S ∈ Ψ i . Let Γ S be a set of primary strict periodic tasks already scheduled. Let hp N S a (i) be a set of alternate tasks having higher priorities than τ i,a already scheduled. The sum of the computational requirements at time t ≥ 0 (w.r.t time S) are given by

W i,a (t) = C i,a + τj ∈Γ S t-sj Tj C j + τj ∈hp N S a (i) t-sj Tj C j,a + τj ∈hp N S a (i) max [0, (R i,a (S + s j -T j ) + (s j -T j ))] (7
) where s j is the relative start time S k j of τ i according to a release time S given by

s j = S 0 j + S -S 0 j T j T j -S (8)
Proof Consider the alternate task τ i,a released at time S ∈ Ψ i . The sum of the computational requirements at time t ≥ 0 (w.r.t time S) W i,a (t) is the sum of the following computational requirements:

1. one execution of τ i,a released at time S: C i ;

2. strict periodic tasks (all with higher priority than τ i,a ):

τj ∈Γ S t -s j T j C j ;
3. alternate tasks with higher priorities than τ i,a :

τj ∈hp N S a (i) t -s j T j C j,a
4. the sum of the additional computational requirements of alternate jobs of hp N S a executed before time S and which have not finished their executions yet before time S. Let τ k j,a be the last job of τ j,a executed before time S. The start time of this job is (S + S j -T j ). Its response time calculated according to theorem 4 at its start time is R i,a (S + S j -T j ). Thus, the additional computational requirements is given by: R i,a (S + S j -T j ) -(S -(S + s j -T j ) = R i,a (S + S j -T j ) + (s j -T j ).

If this job finishes its execution before time S then the additional computational requirements is equal to zero. Thus for each task τ j,a ∈ hp N S a (i), additional computational requirements is equal to:

max [0, (R i,a (S + s j -T j ) + s j -T j )] .
The sum of all the additional computational requirements is equal to:

τj ∈hp N S a (i) max [0, (R i,a (S + s j -T j ) + s j -T j )] .
5.2 Schedulability analysis for alternate and sporadic tasks After scheduling primary and alternates tasks, we focus now on scheduling sporadic tasks which have the lowest priorities. The following theorem gives the computational requirements at time t for a sporadic task τ i released at time S ∈ Ψ.

Theorem 6 Let τ i be a sporadic task released at time S ∈ Ψ. Let Γ S (resp. Γ N S a ) be the task set corresponding to primary strict periodic (resp. alternate sporadic) tasks already scheduled. The sum of the computational requirements at time t ≥ 0 (w.r.t time S) are given by

W i (t) = C i + τj ∈Γ S t -s j T j C j + τj ∈Γ N S a t -s j T j C j,a + τj ∈hp N S (i) t T j C j + τj ∈Γ N S a max [0, (R i (S + s j -T j ) + s j -T j )] (9)
where s j is the relative start time S k j of τ i according to a release time S given by

s j = S 0 j + S -S 0 j T j T j -S (10)

Proof

Let us consider the sporadic task τ i (C i , D i , T i ) released at time S ∈ Ψ i . The sum of the computational requirements at time t ≥ 0 (w.r.t time S) W i (t) is the sum of the following computational requirements:

1. one execution of τ i,a released at time S: C i ;

2. primary tasks of Γ S :

τj ∈Γ S t -s j T j C j ;
3. alternate tasks of Γ N S a :

τj ∈Γ N S a t -s j T j C j,a
4. the sum of the additional computational requirements of all alternate jobs of Γ N S a executed before time S and which have not finished their executions yet at time S: τj ∈Γ N S a max [0, (R i (S + s j -T j ) + s j -T j )] ; 5. sporadic tasks with higher priorities than τ i released at time S:

τj ∈hp N S (i) t T j C j .

Example

Consider the following task sets to be scheduled: primary task set Γ S = {τ 1 (0, 4, 9, 12), τ 2 (4, 2, 13, 18)}, alternate task set Γ N S a = {τ 1,a [START_REF] Burns | Feasibility analysis of fault-tolerant real-time task sets[END_REF][START_REF] Buttazzo | Comparative assessment and evaluation of jitter control methods[END_REF][START_REF] Korst | Scheduling periodic tasks[END_REF], τ 2,a (2, 11, 18)} and sporadic task set Γ N S = {τ 3 (4, 36, 36)}.

For (τ 1 , τ 2 ), g 1,2 = 6 and condition (1) is satisfied:

4 ≤ (4 -0)mod6 ≤ 6 -2 =⇒ 4 ≤ 5 ≤ 5.
Thus, Γ S is schedulable. According to theorem 2, the schedule of Γ S has no transient phase, thus the permanent phase stars at time 0 and has a length L = LCM (T 1 , T 2 ) = 36. The release times of τ 1 in the permanent phase are Ψ 1 = {0, 12, 24}, thus Ψ 1 = {4, 16, 28}. The release times of τ 2 in the permanent phase are

Ψ 2 = {4, 22} thus Ψ 2 = {6, 24}.
The critical instants of Γ S are: Ψ = Ψ 1 ∪ Ψ 2 = {0, 4, 12, 22, 24}. After pruning the release times of strict periodic tasks according to lemma 1 we have: Ψ = {0, 12, 22}.

For τ 1,a we have:

W 1,a (t) = 4 + t -s 1 T 1 C 1 + t -s 2 T 2 C 2 = 4 + t -s 1 12 4 + t -s 2 18 2.
The response times R As R 1,a ≤ (D 1,a = 6), τ 1,a is schedulable.

For τ 2,a we have: As R 2,a ≤ (D 2,a = 10), τ 2,a is schedulable.

W 2,a (t) = 2+ t -s 1 T 1 C 1 + t -s 2 T 2 C 2 + t -s 1,a T 1,a C 1,a +max [0, (R 1,a (S + s 1,a -T 1,a ) + s 1,a -T 1,a )] = 2 + t -
For τ 3 we have:

W 3 (t) = 2 + t -s 1 T 1 C 1 + t -s 2 T 2 C 2 + t -s 1,a T 1,a C 1,a + t -s 2,a T 2,a C 2,a + α + β with α = max [0, (R 1,a (S + s 1,a -12) + s 1,a - 12
)] and β = max [0, (R 2,a (S + s 2,a -18) + s 2,a -18)] .

After calculating R 1,a and R 2,a for S = 6 and S = 24 we obtained: Thus, we have:

W 3 = 2+ t -s 1 12 4+ t -s 2 18 2+ t -s 1,a 12 4+ t -s 2,a 18 2
The response times R 3 of τ 3 are given by: As R 3 ≤ (D 3 = 36), τ 3 is schedulable.

S s1 s2
Figure 4 shows the scheduling diagram of primary, alternate and sporadic tasks within a permanent phase in the worst case failures occurrences. The first job of τ 1,a and τ 3 and the second job of τ 2,a meet their respective deadlines. Figure 5 shows the scheduling diagram of primary, alternate and sporadic tasks within a permanent phase in the case of arbitrary faillures occurrences. All tasks responses times are less than their respective deadlines. For instance, the first job of τ 1,a starts its execution before its primary job finishes its execution, and thus its response time is less than its deadline. In this paper we have considered the problem of scheduling, with fixed priorities, strict periodic tasks in conjunction with sporadic tasks. Strict periodic tasks have the highest priority. We first present a necessary and sufficient schedulability condition valid for strict periodic tasks. This results in defining the first release times of strict periodic tasks preserving the strict periodicity constraints. Then, we show that the schedule of strict periodic tasks can have a transient and a permanent phase. We characterize the duration on both phases and show that we only need to consider the permanent phase for the schedulability of sporadic tasks. The release time of sporadic tasks can be chosen arbitrarily. We show that a worst case response time analysis can be used for sporadic tasks. The worst case response time of a sporadic task is obtained by releasing all sporadic tasks synchronously, at the release time of a strict periodic tasks in the permanent phase. We also show how to prune the times to consider (corresponding to the release times of strict periodic tasks) in the permanent phase. We give the schedulability condition for sporadic tasks based on the worst case response time computation of the tasks. Finally, we extend these results to the case where some of the sporadic tasks are alternate tasks to primary periodic tasks for fault-tolerance, and we give the corresponding worst case response time calculation.

  

Figure 2 .

 2 Figure 2. Scheduling diagram of strict periodic and sporadic tasks

Figure 4 .

 4 Figure 4. Scheduling diagram within a permanent phase in the worst case faillures occurrences

Figure 5 .

 5 Figure 5. Scheduling diagram within a permanent phase in the case of arbitrary failures occurrences

  According to theorem 4, the response times of τ 4 and τ 5 for the release times in S ∈ Ψ are given by: As R 4 ≤ D 4 and R 5 ≤ D 5 , τ 4 and τ 5 are schedulable as shown in figure2.

										4	s 1	+	t -s 2 6	+	t -s 3 12	,
	and
	W 5 (t) = 2 +	t 8	2 +	t -s 1 4	+	t -s 2 6	+	t -s 3 12	.
										S s1 s2 s3	R4 R5
										0	0	1	2	6	12
										4	0	3	4	3	7
										7	1	0	7	4	9
		1	(	0	, 1 ,	4	,	4	)
					, 1 , 1 (	6	,	6	)
			2
		(	2	12 , 1 ,	12 ,	)
	3
					(	2	,	6	8 ,	)
					4
					(	) 12 , 12 , 2

  1,a of τ 1,a are given by:

	S	s1 s2	R1,a(S)
	4	8	0	6
	16	8	6	4
	28	8	12	4


Mohamed Marouf

Laurent George

Yves Sorel

Schedulability analysis for a combination of preemptive strict periodic tasks and sporadic tasks

Introduction

We consider the problem of scheduling tasks with strict periods combined with sporadic tasks. Both types of task have fixed priorities and are preemptive. For a task with a strict period, the difference between its starting time and its release time must be identical for every job. Tasks with strict periods are typically in charge of controlling the activities of a system (sensor/actuator, feedback control, ect.). The freshness of the information they use and/or the reactivity of the system are constrained. Indeed, for control tasks, it might be important to control their jitters (the difference between the worst case and the minimum response time) to ensure the stability of the control loop. In this paper, we consider for controlled tasks, the solution satisfying property 1 that minimizes the jitter of tasks with strict periods.

Property 1 For any task with strict period, (i) the start time of any job of the task must be equal to its release time and (ii) the Worst Case Response Time (WCRT) of the task must be equal to its Worst Case Execution Time (WCET).

In this paper, we provide a sufficient schedulability condition for the schedulability of tasks with strict periods. We show how to define their first release times such that property 1 is met (based on paper [START_REF] Marouf | Schedulability conditions for non-preemptive hard real-time tasks with strict period[END_REF]). Tasks with strict periods have the same fixed priority, the highest one. Sporadic tasks all have a lower priority than any task with a strict period. We show in this paper how to define the worst case scenario for the schedulability of sporadic tasks in the presence of tasks with strict periods. Then we propose a schedulability condition for sporadic tasks based on the worst case response time computation.

Scheduling tasks with strict periods

A task τ i (C i , T i , D i ) with the strict period T i is characterized by (i) a first start time S 1 i , (ii) a strict period T i equal to the deadline D i such as the start time of the k th job of task τ i is given by

S k i = S 1 i + (k • T i ), and (iii) a WCET C i ≤ T i . It has been proved in [2] that a set of tasks Γ is schedulable (sufficient condition) if n i=1 C i ≤ g ( 1
)
where g is the gcd of the periods. The start time of each task is given by

S 1 = 0, S i = i-1 j=1 C j , i ≥ 2 (2)
In [START_REF] Marouf | Schedulability conditions for non-preemptive hard real-time tasks with strict period[END_REF] we gave a local schedulability condition when a set of tasks Γ do not satisfy condition [START_REF] Marouf | Schedulability conditions for non-preemptive hard real-time tasks with strict period[END_REF]. In order to prove that Γ is schedulable, we first schedule a sub-set of tasks according to condition [START_REF] Marouf | Schedulability conditions for non-preemptive hard real-time tasks with strict period[END_REF]. Then, for each remaining (candidate) task, we apply the following local schedulability condition iteratively, such that this candidate task, added to a sub-set of tasks already scheduled, leads to a schedulable set of tasks. A candidate tasks τ c (C c , T c , D c ) is thus schedulable if

C c ≤ C i • δ [T c mod(T i ) • (T c mod(2g) + T i mod(2g))] (3)
where mod is the modulo function and δ is the Kronecker symbol: δ(i) = 1 if i = 0 0 otherwise The start times of a candidate task τ c are given by

If (T c mod(T i ) = 0) then S 1 c = S 1 i + kg, 1 ≤ k ≤ Tc T i -1 If (T i mod(2g) = T c mod(2g) = 0) then S 1 c = S 1 i + (2k + 1)g, 0 ≤ k ≤ Tc 2g -1 (4)
Theorem 1 The scheduling of strict periodic tasks in the time interval [kL, (k + 1)L], k ∈ N * , with start times satisfying equations ( 2) or (4), is identical to the scheduling obtained in the time interval [0, L]. L is the LCM (Least Common Multiple) of all the tasks periods.

Proof According to the conditions (2, 4), 0 ≤ S 1 i < T i . The k th start time of a task τ i is given by S k i = S 1 i + kT i . From the definition of S k i , k ≤ 1, a task released at time S k i ends at time S k i + C i . Thus, the scheduling of tasks in the time interval [kL, (k + 1)L], k ∈ N * , is identical to the scheduling obtained in the time interval [0, L], .

⊡

We define the set Ψ which contains all the start times of the strict periodic jobs on a time interval [0, L[. Thus, Ψ = {S 1 i + k • T i , k = 0..( L T i -1), i = 1..n}.

Scheduling sporadic tasks

A sporadic task τ i (C i , T i , D i ) is defined by its WCET C i , its minimum inter-arrival time T i and its relative deadline D i ≤ T i . In order to study the schedulability of sporadic tasks when tasks with strict periods have already been scheduled, we have to determine the critical instants for a sporadic job τ j i . A critical instant is defined as the instant where a job will have the largest response time if its release time r j i is set to it. It has been proved in [START_REF] Joseph | Finding response times in a real-time system[END_REF] that a critical instant occurs when the release time of a sporadic job is equal to the release time of a highest priority job. For all sporadic tasks, this results in first releasing all tasks with priority higher than τ i at the same time as the first release time of τ i . To consider tasks with strict periods, we have to study all cases of release times S i ∈ Ψ following the scenario defined in section 2. However, rather than testing all the start times of Ψ, some start times are useless and will be thus pruned from Ψ according to the following lemma.

Lemma 2 For a sequence of consecutive executions of strict periodic jobs, only the first release times in the sequence should be considered.

* {Mohamed.Marouf, Laurent.George, Yves.Sorel}@inria.fr. INRIA Paris-Rocquencourt, Domaine de Voluceau BP 105, 78153 Le Chesnay Cedex, France.

Thus, if ∃S k i , S l j ∈ Ψ such that S k i -S l j = C j , S k i is removed from Ψ. Consider Ψ the release times of tasks with strict periods obtained applying equations [START_REF] Kermia | Schedulability Analysis for Non-Preemptive Tasks under Strict Periodicity Constraints[END_REF]4). Consider that task τ i is first released at time S ∈ Ψ. W i (t) denotes the sum of the computational requirements at time t (w.r.t time S) of all the tasks with higher priority, plus one execution of τ i starting from time S. It is given by

where s j is the relative start time S k j according to a release time S of τ i . s j is given by

The WCRT of τ i is the solution of r i = W (r i ) computed by iteration [START_REF] Joseph | Finding response times in a real-time system[END_REF].

Example

We use the Rate-Monotonic algorithm to schedule the following tasks. Let us consider three tasks with strict periods: τ 1 (1, 4, 4), τ 2 (1, 6, 6) and τ 3 [START_REF] Marouf | Schedulability conditions for non-preemptive hard real-time tasks with strict period[END_REF]12,12). τ 1 and τ 2 satisfy condition (1) and are schedulable with S 1 1 = 0, S 1 2 = 1. τ 3 and τ 1 satisfy condition (3), thus τ 1 is schedulable with S 1 3 = 6. L = LCM (T 1 , T 2 , T 3 ) = 12 thus Ψ = {0, 1, 4, 6, 7, 8}. After eliminating the successive jobs according to lemma 2, Ψ = {0, 4, 6}. Let τ 4 (2, 6, 8), τ 5 (2, 12, 12) be sporadic tasks to be scheduled. We have:

As r 4 ≤ D 4 and r 5 ≤ D 5 , τ 4 and τ 5 are schedulable, as shown in figure 1.