2

Uniprocessor Architecture Solutions

In this chapter, we will take a look at the problems and solutions in real-time scheduling for uniprocessor architectures.

In the first part, we present classical results from the state-of-the-art allowing us to design a real-time system (RTS). These results are based on the expression of feasibility conditions (FCs) that guarantee the compliance with temporal constraints associated with the execution of tasks on a system. We are foremost interested in the characterization of a scheduling problem leading to the definition of task models, temporal constraints and scheduling algorithms for an RTS. We focus on the periodic and sporadic task activation models. We will then look at the main state-of-the-art scheduling algorithms by specifying the contexts for which they are optimal. We will then study the worst-case scenarios as well as the FCs for temporal compliance in a preemptive, non-preemptive context for the scheduling policies based on task-level fixed priorities (FP), job-level fixed priorities (JFP) and dynamic priorities.

In the second part, we present sensibility analyses that allow us to determine the acceptable limit deviations of task parameters (worst-case execution time (WCET), periods and deadlines), which guarantee the schedulability of tasks. We study in particular the FP- and JFP-type schedulings (the case of Earliest Deadline First (EDF)).

2.1. Introduction

Scheduling theory has been widely studied over the past 40 years. Numerous results are available. They allow us to solve the problem of designing an RTS. The design allows us to verify, before its conception, that an RTS complies with timeliness properties associated with the execution of jobs originating from tasks. This design is based on a “worst-case” approach which allows us to guarantee that throughout the lifetime of a system, the tasks will respect their temporal constraints. The worst-case approach is distinguished from average analysis- and simulation-based approaches. Verifying that an RTS is consistent in worst-case allows us to guarantee the property of determinism: for each possible activation scenario, the tasks comply with their temporal constraints.

The methodology usually employed to solve a scheduling problem is the following:

– identify the class of the problem to solve (task model, with temporal constraints and with scheduling considered); – identify the possible activation scenarios of the tasks in the RTS; – identify, in the set of possible activation scenarios, the subset leading to the worst cases for the temporal constraint compliance of the tasks; – determine, for this subset, the associated FCs. An FC is a necessary, necessary and sufficient or simply sufficient test for guaranteeing the compliance of the tasks with the temporal constraint. – verify that the FCs are met for a given architecture.

The class of a real-time problem is defined by the scheduling model, the task model and the temporal constraint model employed. From the identification of the class of the problem to solve, we can identify the complexity of the problem to solve and deduce the existence of solutions for the problem.

We retrace in a first part the various task models, temporal constraints and schedulings defining the class of a problem. We describe the worst-case scenarios when no particular activation scenario is imposed (non-concrete case). We then study task-level fixed priority schedulings (FP), job-level fixed priority schedulings (JFP) for EDF and First In-First Out (FIFO) schedulers, and dynamic priority schedulings for Least Laxity First (LLF) and round robin (RR) schedulers, and the conditions for which these algorithms are optimal. The optimality property of a scheduling algorithm allows us to deduce the existence of a solution to the scheduling problem. We will then elaborate on the classical FCs for the FP and JFP schedulers.

Most FCs do not allow the deviation of task parameters defined in the specifications of a problem. It could be interesting to study the temporal robustness of FCs, allowing us to guarantee the compliance of the tasks with the temporal constraints, in case of the deviation of parameters of the tasks. This approach, called sensibility analysis, has the aim of studying the possibility of introducing more flexibility in the specifications in order to make the FCs more robust, in the design phase. Most state-of-the-art results consider sensibility analyses in which only a single parameter can evolve. We put ourselves in this context in this chapter. The reader interested in multidimensional sensibility analysis may refer to [RAC 06], in which a stochastic approach is proposed when taking into account the variation of several parameters.

This chapter is organized as follows. In section 2.2, we present the various models and concepts that allow us to classify the scheduling problem. We describe the task models, the temporal constraint models, the scheduling models as well as the notations and classical concepts of real-time scheduling. Section 2.3 presents the different state-of-the-art algorithms and specifies the conditions which make them optimal. Section 2.4 introduces the concept of busy period and defines the scenarios which lead to the compliance of temporal constraints of the tasks, for fixed-priority or dynamic scheduling policies. These worst-case scenarios are at the foundation of feasibility tests presented in section 2.5. We will then study the sensibility analyses proposed in the state-of-the-art in section 2.6. We consider the sensibility of WCETs, of periods and deadlines. Finally, we conclude the chapter.

2.2. Characterization of a scheduling problem

In this section, we recall a few classical concepts for the characterization of the class of the scheduling problem.

2.2.1. Task model

We consider a set τ = {τ1,..., τn} of n tasks. Various laws of arrival have been studied in the state-of-the-art. We distinguish between the following laws of arrival for a task τi:

– periodic arrival: the activation requests of the jobs of a task τi are periodic, with period Ti; – sporadic arrival: the activation requests of the jobs of a task τi have a minimal interarrival time greater than or equal to Ti; – aperiodic arrival: single activation request for the duration of the system. This model has been widely studied in presence of real-time periodic tasks. The aim is to allow aperiodic tasks with relative (flexible) temporal constraints in the presence of real-time periodic tasks [SPR 89, STR 95].

In this chapter, we will be looking at the periodic and sporadic laws of arrival.

The structural model of a task specifies the constraints associated with the structure of the tasks. We distinguish between:

– The local structure: - the sequence: an elementary task, composed of a sequential code; - the task with precedence constraints, composed of a set of sequential tasks in a relation of linear precedence or in a graph; - the task with resource constraints, for which a part of the code accesses a critical resource in mutual exclusion. The critical section is non-preemptive. – The distributed structure, composed of a set of tasks which are executed on several nodes interconnected by a communication network: - the tree, for which a task executed on a node triggers a set of processes on other nodes, forming a tree (for example multicast tree) without response from the latter ones; - the client/server (or request/response); - the graph defined by a set of dependency relations between the distributed tasks.

In this chapter, we will be looking at the task model without precedence or resource constraints. The reader interested in taking into account precedence constraints may refer to the task model called transaction, studied mainly in [RAH 12]. We will now introduce the various hypotheses possible in relation with the activation times of tasks:

– Concrete tasks: a scenario for the first activation times (offset) of the tasks is imposed. When the offsets can be chosen freely by the designer of the system, we refer to offset free systems. – Non-concrete tasks: we do not know the first activation times of the tasks beforehand.

Remark 2.1.– For the periodic law of arrival, considering a concrete task model means knowing the activation times of all the jobs of the tasks.

We will now introduce the notations specifying the WCET of a task (of sequential type) and the worst-case response time of a task:

– The WCET of a task τi is denoted by Ci. – This worst-case execution corresponds to the execution of the sole task without any preemption from the operating system. – Several approaches are possible to determine the WCET of a task [PUS 97]. Either by precise analysis of the machine code of the task and the material architecture on which the task is executed, or by benchmark on a real architecture, the value of Ci is more challenging to guarantee, it depends on the conditions of execution (memory,...