Mitra Nasri

Emmanuel Grolleau
email: grolleau@ensma.fr

On the Existence of a Cyclic Schedule for Non-Preemptive Periodic Tasks with Release Offset

I. INTRODUCTION

Non-preemptive scheduling reduces both runtime and design time overhead since it avoids context switches, preserves cache affinity, and simplifies the use of shared resources. As a result, it increases the accuracy of worst-case execution time (WCET) estimation and improves system predictability. Many safety critical systems use table driven scheduling in which tasks are dispatched according to a schedule stored in a table. This table contains a cyclic schedule that needs to be repeated during the lifetime of the system. Since the table must be kept in memory, a smaller table is preferable particularly for embedded systems with limited memory. For example, the Atmel UC3A0512 microcontroller, which is used in mission critical space applications [START_REF] Ruiz | GNAT Pro for On-board Mission-Critical Space Applications[END_REF], has 64 KiB of internal SRAM, 512 KiB of internal flash memory, and is clocked at 12 MHz. Similarly, an Arm Cortex-M3 has 4 KiB RAM, 16 KiB flash, and clock speed 24 MHz. With such limited resources, non-preemptive execution becomes the natural way of executing real-time tasks in these systems [START_REF] Nasri | Offline Equivalence: A Non-Preemptive Scheduling Technique for Resource-Constrained Embedded Real-Time Systems[END_REF].

In a non-preemptive scheduling table, the number of entries is analogous with the number of instances of the tasks (a.k.a jobs) in a cyclic schedule. It is known that in a synchronous periodic task set with constrained deadlines, the schedule becomes cyclic after H units of time where H is the least-common-multiple (LCM) of periods [START_REF] Leung | A note on preemptive scheduling of periodic, real-time tasks[END_REF] for any feasible schedule. However, many systems use release offsets for their tasks in order to enforce particular properties such as avoiding the critical instant, or enforcing precedence constraints. In that case, a cyclic schedule may not be found in the first hyperperiod, which then increases the size of scheduling table. In our work, we are interested in the length of a cyclic schedule since many embedded systems have limited amount of memory to store the table.

Choquet-Geniet et al. [START_REF] Choquet-Geniet | Minimal schedulability interval for real-time systems of periodic tasks with offsets[END_REF] have shown that any preemptive periodic task set with independent tasks and constrained deadlines that is feasible in a work-conserving schedule, satisfies the following conditions (we call it after the authors' names Choquet Grolleau Conditions (CGC)):

(i) it becomes cyclic after time t start ∈ [0, O max + H] where O max is the largest release offset, (ii) the length of cycle is H, (iii) the cycle is the first window of length H in the schedule having a slack exactly equal to (1 -U ) • H, where U is the task set utilization, (iv) there is no deadline miss from time 0 to the end of the cycle. (v) every job appearing in the cycle starts and ends in the cycle.

Goossens et al. [START_REF] Goossens | Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms[END_REF] have extended [START_REF] Choquet-Geniet | Minimal schedulability interval for real-time systems of periodic tasks with offsets[END_REF] and derived an upper bound on the length of the cycle for any feasible schedule (work-conserving or not, uni or multiprocessor). However, this upper bound is a function of task's periods, deadlines, and release offsets and may become exponential with respect to H.

In this work, we study the existence of a cyclic schedule for non-preemptive tasks when they are scheduled by non-workconserving scheduling algorithms. In the remainder of the paper we consider a set of non-preemptive periodic tasks denoted by τ = {τ 1 , τ 2 , . . . , τ n }, where each task τ i is identified by its execution time C i , its period T i , its deadline D i ≤ T i , and its release offset O i . We denote the least-common-multiple (LCM) of the periods by H and utilization of the task set by U = n i=1 C i /T i . Moreover, it is assumed that the system has a dispatcher to dispatch the jobs one after another according to the start times stored in the table, hence, the schedulability of the task set will not be affected by runtime release jitters or execution time variations.

In Sec. II, by an example we show that there exists online non-work-conserving scheduling algorithms that create a cycle with length 2H (i.e., they violate condition (ii) of CGC). We also show that it is possible to modify our example schedule such that it satisfies condition (ii) of CGC although it will no longer be consistent with the scheduling algorithm. In Sec. III, we formally introduce the open problems.

II. MOTIVATING EXAMPLES

Precautious-RM is one of the recently introduced online non-work-conserving scheduling algorithms for non-preemptive periodic tasks [START_REF] Nasri | A new approach for limited preemptive scheduling in systems with preemption overhead[END_REF]. It priorities the tasks according to the rate monotonic (RM) policy, however, before scheduling a task such as τ i at time t, Precautious-RM verifies the following condition: . In other words, it schedules a low priority task only if it will not cause a deadline miss for the next job of τ 1 . If Precautious-RM is used to create a non-preemptive schedule for the following task set, the resulting schedule will have a cycle with length 2H as it is shown in Fig. 1.

t + C i ≤ r next 1 + D 1 -C 1 ,
As it can be seen in Fig. 1-(a), Precautious-RM has inserted an idle-time from time 8 to 11 because if τ 2 was executed at 8, it would have caused a deadline miss for the second job of τ 1 . Even though the length of cycle is 2H in Fig. 1-(a), the total amount of slack is 4 which is equal to (1 -U ) • 2H. In Fig. 1-(b), an optimal schedule has been presented that schedules the task set in a cycle with length H. This schedule satisfies all CGC.

III. OPEN PROBLEMS

The first open problem is about the existence of a task set for which none of the feasible schedules satisfies CGC. The existence of such task set implies that memory required for storing an offline table of a set of non-preemptive tasks with release offsets might become unbounded or unreasonably large. Moreover, Since the problem of scheduling a set of non-preemptive periodic tasks is known to be strongly NP-Hard (see Jeffay et al. [START_REF] Jeffay | On non-preemptive scheduling of period and sporadic tasks[END_REF]), not knowing the existence of a cycle with a limited length will only make the situation worse. It means that in order to find a schedule, a large number of jobs must be considered (if a cycle exists).

Problem 1. Find a feasible task set τ for which there does not exist a cyclic schedule or the length of cycle is larger than H.

If there exists a task set that matches with Problem 1, then the next question is how to find a cyclic schedule such that the number of cycles is minimized. Otherwise, if there is no such task set, then we will be interested to find the CGC-compatible schedule. Next we define these two follow-up problems.

Problem 2. Given a feasible non-preemptive task set τ , find a schedule S that has the smallest cycle length and satisfies condition (iv) of CGC. Problem 3. Given a feasible non-preemptive task set τ , find a schedule S that satisfies CGC.

It is worth noting that we still do not know whether an answer to Problem 2 satisfies condition (i) of CGC or not. This answer will most probably satisfy condition (iii) because that is the notion of reaching to an equilibrium state.

where r next 1 is

 1 the expected release

Fig. 1 .

 1 Fig. 1. A task set with 4 tasks scheduled by (a) Precautious-RM [6] and (b) an optimal schedule. In this task set C 1 = 2, C 2 = 14, C 3 = 6, C 4 = 2, T 1 = 10, T 2 = T 3 = T 4 = 30, O 1 = O 2 = O 4 = 1, and O 3 = 0. Here, H is 30 and U = 28 30 .

ACKNOWLEDGMENT

This work is supported by a fellowship from Alexander von Humboldt Foundation. The authors would like to thank Schloss Dagstuhl for seminar number 17131 that helped this work to happen.


Alexis Akinyemi

Noé Cazin

Clémence Brun

Laurène Houtin

Attitude measurement with emoji, a large scale study on French youngsters

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.