Theoretical and Technical Aspects of ASLA Framework

Chapter 5

The ASLA approach: Theoretical study

Fig. 5.1 Dynamic task model in the dissertation overview

Traditionally, automotive systems have been designed to be unchanged at runtime in order to maintain the system predictability. However with the new trends in automotive industries and the emerging applications such as smart cars..etc, has proved that some flexibility can be provided to real-time systems mainly soft real-time systems. Dealing with runtime adaptation in real-time systems is a hard problem to solve due to the complex deployment and configuration issues involved in satisfying multiples requirements such as real-time timeliness and fault-tolerance. Effective deployment requires developing and evaluating a range of task allocation and recon-figuration algorithms that satisfy automotive system requirements while reducing resources usage. Therefore, we tackle in this chapter the problem of task mapping and reconfiguration (see Figure 5.1). This chapter makes two contributions to the study of runtime adaptation in automotive systems. First,it describes a novel task allocation algorithm for mapping runnables to ECUs. Second, it presents TSeRBA (Tabu Search Mapping and Bandwidth allocation) algorithm for task reconfiguration and bandwidth allocation.These two contributions are realized with ASLA, the framework we designed for task adaptation in AUTOSAR (chapter 4).

5.1 ASLA System Models and Assumptions

In this section, we will state our assumptions, the problem definition for our work on ASLA. We will describe ASLA’s system, fault and reconfiguration models.

1. ASLA’s system model

Applications in the automotive system use sensor information to obtain current system’s informaTion. For e.g., in Steer-by-Wire (SBW) applications [57], sensors are typically used to measure and obtain information about steering wheel movement. This information is then fed into the system to be processed. The controllers compute signals for steering movements with the information from sensors. The computed signals are then sent to the steering wheel actuator for the motors, which are handled periodically for timely handling of user operations and reactions to the environment. In order to reflect this nature, we define an “OPerational chain” OP, which is composed of periodically executing runnables generating data and events regularly that propa-gate through multiple runnables. An “OPerational chain” also has an end–to–end delay from the input to the output¹. Within an OP, runnables are classified into sensor/actuator runnables and other computational runnables. For instance, an actuator runnable controlling the steering wheel motors must run on the ECU connected to the motor in an SBW application. Every runnable generates data to be fed to other runnables, except actuator runnables which terminate the OP. Figure 5.2 shows an example of operational chains (with hard and soft real-time requirements) applied to E/E vehicle. Handling adaptations on demand with bounded time is a requirement for real-time systems. By handling adaptations within a specified timing boundary, time to adapt can be bounded, and the system can operate continuously. To limit time to adapt, authors of [110] classified software tasks into three classes: Hard Tasks, Soft Tasks, and Best-Effort Tasks. In our work, we apply the same classification to SWCs, where a runnable is a part of an SWC [aut]. In this work, we consider a system with two criticality levels: Hard and Soft Tasks. Considering multiple criticality levels is left as future work. An SWC with strict timing constraints, for which deadline misses lead to a catastrophic degradation of the system is classified as a Hard software Component (Hard SWC). An SWC which has flexible timing constraints. i.e., the deadline misses are tolerable is classified as (Soft Software Components(Soft SWC). The TSMBA (Tabu Search Mapping and Bandwidth Allocation) algorithm [93] provides a comprehensive solution that allocates Hard SWC, and Soft SWC to distributed heterogeneous architectures and performs processor bandwidth reservation for guaranteeing timing requirements even in the presence of faults. From dependability perspective, a single failure of a runnable within an OP will affect all its successors such that the overall OP requirement is violated. TSMBA cannot be used directly in systems with data dependencies. Therefore, we propose a new allocation algorithm based

¹Dealing with End-to-End delay of an OP is beyond the scope of this work, we calculate it similarly to [71]

ECU2

Sensor

ECU1

ECUn

Actuator

Fig. 5.2 An example of operational chains can be applicable to an E/E vehicle, where r represents a runnable, and m denotes a message between two runnables

on TSMBA, O-TSMBA (OPerational chain-TSMBA) which is a variant of TSMBA that takes dependencies among SWCs.

Then we add support for reconfiguration to O-TSMBA. We call this algorithm TSeRBA(Tabu Search Reconfiguration and bandwidth Allocation). TSeRBA has two properties that distin-guish it from TSMBA: (i) It supports dynamic SWCs allocation and reconfiguration within AUTOSAR, As we said in the previous chapters, currently, there is no support for doing this within AUTOSAR. In our work, we propose enhancements to the different layers of AUTOSAR (i.e., from the application down to the OS layer) to enable runtime adaptation and, therefore, provide support for TSeRBA, (ii) it considers dependencies among SWCs. In the next sections we describe the system model in detail.

5.1.1.1 Software architecture

We model an application as a set R of interacting runnables r_i ∈ R. R is composed of n runnables,r₁, . . . , r_n. Each runnable is part of an atomic SWC, sw_j, which may have several runnables. In order to represent a relationship between a runnable, r_i and the SWC, sw_j, we define a function ω such that ω(r_i) = sw_j when sw_j contains r_i. The function inverse of ω,ω⁻¹ returns all the runnables inside an SWC. Runnables receive data via input ports Pⁱⁿ_ri and send out the data via output ports P^out_ri. Pⁱⁿ_ri and P^out_ri are defined as a set of input, output ports of a runnable r_i, respectively. Runnables interact between each other via £, which is a set of links. An interaction between runnables is represented by a link l_i. Runnables exchange data through signals s_i on the links. We define Snd(s_i),Rcv(s_i) as a function returning the runnables that sends a data signal s_i

and function returning the runnables receiving a data signal s_i, respectively. In order to express the dependency relationship between the SWCs, we define a function Dep such that Dep(r_i) returns all the runnables that depend on r_i, in other words a runnable r_i dependent on a r_j, if there is a link l_i between both runnables and this link connects the input port of r_j,Pⁱⁿ_rj to the output port of r_i,P^out_ri. The set of SWCs are also given, Γ, for guaranteeing different timing requirements Γ is classified by a function RQ into two sets, so the function RQ: Γ → {Hard, So f t }, determines if a SWC is in hard or soft real-time subsets, respectively. The SWCs are allocated on a distributed heterogeneous architecture denoted by a set of ECUs. The allocation is denoted by the function²

χ: R→ECUs. This allocation is not yet known but would be decided by the Cost function described in Section 5.1.4. We assume that each runnable is represented by a periodic task [93] r_i, which releases a job every T_i units of time, where each job consumes at most C_i units of computation time and should be completed within a relative deadline D_i = T_i. Both runnables Soft and Hard are periodic and have a period T_i. A subset OP_i ⊂R contains runnables for the i^th operational chain out of total m operational chains. In certain cases, a runnable r_i can be an element of OP_i and also an element of OP_l, where i ̸= l. The relationship among the tasks in the i^th operational chain OP_i is represented by a directed graph G_i. In this graph, a node u denotes a runnable, r_i ∈ R, and an edge (u, v) of G_i indicates data flow from u to v; the edge

(u, v) has its own message, m_uv, which is generated by the node u and consumed by the node v in G_i. We assume that the allocation of each runnable, r_i, to the graph is given at design time. Certain runnables can only be mapped on certain ECUs. Let denote u(G_i, r_i) to be the node of

G_i allocated to the runnable, r_i. The u(G_i, r_i) value is ∅ if the runnable r_i is not an element of

OP_i. This function is also applicable to a SWC. An OP_i represented by a pair (T^OP_i, ∆) where

T^OP_i is the period of the application OP_i and ∆ is an end–to–end delay, which is defined as the worst-case delay between the release time of the first executed node in the graph G_i and the completion time of the last executed node in G_i. All runnables in OP_i have the same period T^OP_i.

So a runnable with hard real-time requirement r_i is characterized by its Worst Case Execution Time (WCET) C_i and a deadline D_i. For a hard runnable r_i, the WCET C^ECU_i^j is known for

each processing element ECU_j where r_i is considered for the allocation. Soft runnables are

characterized by the Probability Distribution Function (PDF) U^ECU_i^j of their execution times and a soft deadline δ_i. U^ECU_i^j (h) is the probability that the job J_i,k of r_i has an execution time of h

on the processing elements ECU_j. Each soft runnable (or task) must have An Expected Utility (EU) function EU_ci(r_i, ECU_j) for each ECU_j whose values is defined as the probability-weighted sum of possible values of the soft tasks’ execution time (i.e., c_i). The QoS of a soft runnable r_i is defined as the probability of meeting the deadline δ _i, i.e, QoS (δ_i) = P{f_i,k ≤ ar_i,k + δ_i},where f_i,k and ar_i,k are the finishing and arrival time of the k^th job of runnable r_i, respectively. An SWC sw_j is also characterized by a worst-case execution time C_j and a deadline D_j, however, it differs from runnables in the sense that it: C_j = Σ_∀ri∈ω−1 C_i, T_j = min_∀ri∈ω−1 T_i and the deadline is

²Allocating a runnable in the AUTOSAR implies that the corresponding SWC is also allocated. In other words, all runnables of a SWC should be assigned to one ECU

D _j = min_∀ri∈ω−1 D_i. Let U_i denote the utilization of an SWC sw_j with hard real-time requirement and it is defined as C_j/T_j. whereas an SWC sw_j with Soft real-time requirement its utilization is defined as Q_j/T_j. Throughout this dissertation, we restrict ourselves to implicit-deadline task systems.

5.1.1.2 Hardware architecture

We model the hardware architecture as an undirected graph G_h = (V_h, F_h). Nodes V_h represent a set of hardware resources and the edges F_h represent the communications links (or buses) between them. The hardware resources consist of a set of heterogeneous processing units (or ECUs), to which a runnable set R can be potentially mapped, run and delivered as part of SWCs. The ECUs are interconnected by a communication channel bus B on which messages m_ij are exchanged. We assume that we use a fault-tolerant network such as CAN [45] as the underlying in-vehicle network. Communicating SWCs allocated on different ECUs exchange messages on the communication channel. We assume that the network has an upper-bound on message delivery and is completely connected. This assumption is reasonable for automotive systems. Relaxing this assumption through the integration of our framework with the network level fault-tolerance techniques is an area of future work. Each ECU_i ∈ ECUs is composed of an EDF scheduler and a middleware implementing online tasks reconfiguration mechanism. The soft tasks are scheduled by the CBS server. The hard tasks and the CBS servers are scheduled using EDF. The temporal isolation between the hard and the soft real-time tasks is enforced by CBS, thus guaranteeing the schedulability of the hard tasks. The soft tasks τ_i are assigned to a CBS, characterized by the couple (Q_i, T_i) where Q_i (bandwidth server) represents a time that the soft task is allowed to use ECU every period T_i. The ECUs have access to a shared memory where the code of the tasks is stored. The system model is illustrated in Figure. 5.3.

Fig. 5.3 Soft real-time tasks are served by a CBS server, while hard real-time tasks are directly scheduled.

2. Problem statement

Based on the software and the hardware architecture presented above, we state the problem to solve as follows: given a set of ECUs and a system Configuration (consisting of a set of OPs with hard and soft real-time requirements) determine whether all tasks of every OP ³ will always meet all deadlines (both hard and soft constraints) under any possible adaptation sequences. However, there are many sub-problems that we need to consider in conjunction with the adaptation.

P1. Allocation problem. Can we find an optimal allocation schemes for each OP to maintain the schedulability analysis? By applying our global scheduling algorithm; we determine the mapping and the utilization such that the deadlines for all hard tasks are satisfied and the probability of meeting the deadline (i.e.,QoS ⁴) for the soft tasks is maximized.

P2. Adaptation problem. knowing a best allocation, can we guarantee all deadlines both (hard and soft) in the presence of the adaptation such as adding, deleting and migrating tasks? The objective of scheduling the runtime adaptation is to guarantee that a system is schedulable not only after the adaptation but also during the adaptation path. In the next we will give a simple example to show the difficultly of runtime adaptation.

Table 5.1 Example task set

Example 1.2 Consider a system configuration in Fig. 5.4 with a 3 ECUs, 4 hard tasks and 6 soft tasks. The task set parameters are reported in Table 5.1. Task parameters were chosen to keep the example simple and easily understandable; they should not be considered as real task cases. We assume that the allocation tasks to ECUs depicted in Fig. 5.4 has been already defined and it is so far the best solution (i.e., within which the deadline for hard tasks is satisfied and the QoS for soft tasks is maximized). The system configuration is schedulable under EDF in the absence of adaptation. Further, let us assume that during runtime, specifically at time t=9 an adaptation is triggered that updates the task τ₇ to τ^′₇; this adaptation will lead other tasks on ECU₁ to miss their deadlines at time t=12. This example illustrates that reconfiguring a task may cause deadline miss of other tasks on the system.

3. Fault model

This work focuses on a fail-stop model of failures, where tasks or ECUs can fail and the remainder of the system can continue executing. We assume that ASLA employs a failure

³The number of OPs depends on the number of applications in the system ⁴The QoS derivation is described in Section 5.1.4

Fig. 5.4 The missed deadline during the adaptation.

recovery policy[93], which consists of restoring the last non-faulty state of the failing task, i.e., to recover from faults. This state has to be saved in advance in the shared memory and will be restored if the task fails.

4. Cost function Calculation (i.e. QoS)

The schedulability analysis of a soft task τ_i (i.e., the probability of meeting its deadline δ_i; QoS(δ_i)) is calculated using the stochastic analysis method described in [70] ( see chapter 2). This QoS guarantee depends on both the PDFs and the bandwidth server Q_i. As we said previously in Section 5.1.1, for a given soft real-time task τ_i, The QoS r_i is defined as the probability of meeting the deadline δ _i, i.e., QoS (δ_i) = P{f_i,k ≤ ar_i,k + δ_i},where f_i,k and ar_i,k are the finishing and arrival time of the k^th job of runnable r_i, respectively. This QoS guarantee is calculated by by modeling the CBS server(serving the Soft tasks) as a queue [70]. The arriving job j_i,k are seen as tokens to be served by the server having the capacity Q_i (where is the capacity

of the server Q_i). As we had previously described, the PDF of the computation times of jobs of the tasks allocated on the ECU_j is defined to be U^ECU_i^j . In this model, U^ECU_i^j represents the PDF of the incoming requests for the queue: U^ECU_i^j (h) = P{c_i,k = h}, Probability that the arriving

job requires h units of computation time. The system is modeled with a queue where: a request of c_i,k units arrives every T_i. Since the server capacity is Q_i, at most Q_i can be served every T_i units of time. The system is described with a random process defined as follows:

(

^v1 ^= ci,1

v_k = max{0, v_k−1 −Q_i}+ c_i,k

The state variable v_k indicates the length of the queue (in time units) immediately after the job j_i,k having a computation time c_i,k arrives. It can be shown that the job j_i,k will finish before this time:

f_i,k = ar_i,k + ⌈ ^vk ⌉T_i

Q_i

Thus, the probability that the queue length is v_k immediately after a job arrives is a lower

bound to the probability that the job would finish before the deadline δi = ⌈ ^vk ⌉Ti.

Q_i

Let π_m^[k) = P{c_i,k = h} be the state probability of the process v_k. We already have the PDF of the request times of the arriving jobs, i.e., U_i^ECUj =P{c_i,k = h}. Since we know that c_i,k is time invariant, as U_i^ECUj (h)does not depend on i, k, the value of π_m^[k) can be calculated as follows:

π_m^(k) = P{v_k = m} = P{max{v_k−1 −Q_i, 0}+ c_k = m}

Finally the solution comes out to be:

Q_i

π_m^(k) = _∑(U_i(m) ×π_h^(k−1)) h=0

∞

+ _∑ (U_i(m −h + Q_i) ×π_h^(k−1))

h=Q_i+1

The detailed derivation can be seen in [70]. Using a matrix notation, one can solve for π_m^(k) using the following equation:

_Πk _= πk

2

_.

.

From the queuing model theory the condition for the que to be stable (i.e., the number of elements in the queue do not diverge to infinity) is presented as :

_P = meaninterarrivaltime _< 1 meanservicerate

In our case the stability condition is achieved when the mathematical expectation of the PDF of incoming requests is less than the server capacity, i.e., c_i,k < Q_i. If this condition is not satisfied, the difference between deadline f_i,k assigned by the server for the job J_i,k and

the job release time ar_i,k would increase indefinitely, thus the queue would overflow and the schedulability of the other tasks would slow down in unpredictable manner. For stable queue, a stationary solution of the Markov chain describing the queue can be found, i.e. there exists a solution Π such that Π = lim Π^i,k. Since the size of the matrices M and Π are infinite,

i,k→+∞

the calculation of an exact solution is computationally expensive. Thus the matrices can be truncated and an approximate solution can be found. However, by doing this we get inaccurate

(approximated) results, but the computation complexity is highly improved. the Matrix M is

′

truncated to an N ×N matrix M and the problem of finding the stationary solution becomes an eigenvector problem, i.e., one has to find Π^′ such that Π^′ = M^′Π^′ .

The resulting eigenvector Π^′ has to be normalized since the steady state probabilities must sum to one. This is done by dividing all the elements of the eigenvector by their combined sum. More formally:

• Π^′

•                 ∑_N Π^′

The resulting stationary solution is in fact — a PDF of the stochastic variable v. In our case, we would like to compute the CDF as it describes the system completely. We can recall that the CDF of a stochastic variable expresses the probability that the variable is less than or equal to a given value. The CDF D(v) of the given stochastic variable v can be easily computed as

v

D(v) = _∑ π_m.

m=0

Since we know that the deadline δ is related to the length of the queue as δi = ⌈ ^vk ⌉Ti, the

Q_i

probabilistic guarantee Qos(δ_i) can be easily computed as :

^δi

^Qos(δi^{) = D(⌈}_Ti ^⌉Qi⁾

The quality of solution depends a lot on the truncation point N. Essentially, by setting a truncation point on a state probability vector, the state space is reduced. Thus, it would be a good idea to set the truncation point such that, only the states which are impossible to reach are removed. In this case, the elements in the state probability vector Πrepresents the probability of the queue having a certain length. By setting the truncation point at the point representing the maximum possible length of the queue, we can have a safe assumption. The maximum possible length of the queue can be calculated by considering the PDF of the incoming requests and having a certain upper limit on the total number of jobs.

Lets assume that the total number of jobs are: JOBS. The probability distribution function of incoming jobs is given as U_i^ECUj . The PDF is finite and lets say it has a length of L_i. The server

capacity is given as Q_i.

The worse case scenario in this case would be observed when all the jobs having request times greater than the server capacity would arrive one after another. Thus, the maximum possible queue size can be calculated as:

^Li

N = _∑ U_i^ECUj (h) ×h ×JOBS

h=Q_i+1

This value N can be a safe truncation point. We have used this in our implementation to truncate and then solve the markov chain for a stationary solution, our proposed algorithm will decide on the appropriate Q values that minimize the cost function, thus maximizing the total QoS.

5.1.4.1 Cost function calculation – A numerical example

We considered a periodic task having a period of 8 and distributed computation times as shown in Figure. 5.5. The Q value for this example is 4 and the deadline δ is 6.

Fig. 5.5 PDF of the computation times.

′

This matrix M is then raised to higher powers until the desired accuracy level is reached. The accuracy is measured by calculating the quadratic distance between the elements of the first and the last column. We have set this accuracy level as 10⁻⁴⁰. Figure. 5.6 shows the measured

′

error values for different values of power. For this particular case, M is raised to 19, since the measured error for higher powers is less than the fixed accuracy level. The error measured at iteration 19 is 1.3693056903764797E-41.

One of the columns is then extracted and the CDF is generated. Then Qos(6) is calculated. It comes out to be 0.53. This is multiplied with its weight to give the final value of the cost

′

Fig. 5.6 Error in calculation of stationary solution vs number of iterations (power to which M is raised).

Fig. 5.7 Probability to satisfy a certain deadline,Qos(δ_i).

function. The plot for QoS(δ_i) can be seen in Figure. 5.7

5. Assumptions

We adopt the following assumptions:

Assumption 1 . The network is a fault-tolerant network, it has an upper-bound on message delivery and is completely connected. This assumption is reasonable for automotive systems. Relaxing this assumption through the integration of our framework with the network level fault-tolerance techniques is an area of future work.

Assumption 2 . For the sake of simplicity, we consider that each task contains one runnable.

6. Definitions

We first introduce some definitions:

Definition 9 (Demand-Bound Function) A demand-bound function dbf(τ_r, L) gives an upper bound on the maximum possible execution demand of task τ_r in any time interval of length L where, dbf is calculated as the total amount of required execution requirements of all jobs of τ_r with their whole scheduling windows within the time interval, dbf can be calculated as follows.

Definition 10 (Time2adapt) time2adapt denoted δ is defined as the time instant relative to the release time of τ^∗_r within which job of τ^∗_r should be reconfigured. During this time the task’s period is prolonged at runtime in order to accommodate the new request for reconfiguration. This operation is called task compression in which the period of task is prolonged from T_i to

T^′_i so the utilization of the task is reduced to U_i = C_i/T^′_i which gives some room to insert a new task i.e., the freed utilization U_i −U^′_i. if a task τ_i is compressed at t_r, then:

d_i −

δ =

t_r

C_i(t_r)

^{i f di −} _Ui −Ui′ ^> tr

C_i(t_r)

^{i f di −} _Ui −Ui′ ^≤ tr

where d_i is the deadline of the current instance of the task τ_i. C_i(t_r) is the new computation time of τ_r which is executed with the new period T^′_i and t_r is the time to accommodate the new requests during which the deadline of the instance is delayed from t₀ + T_i to t₀ + T^′_i where t₀ is the release time of the current instance. At t_r, t₀ ≤ t_r ≤ t₀ + T_i ≤ t₀ + T^′_i.

Definition 11 (Safe adaptation path) A safe adaptation path sp comprises an ordered series of reconfiguration actions that modify the structure and the behavior of the system configuration (i.e., OP); sp has the following parameters sp = (lgth, τ_r, D, nbr, Dep)— The length of the safe

adaptation path lgth(sp_i) which varies depending on the reconfiguration type i.e., the number of reconfiguration actions within the path nbr, with nbr ≥ 1 .Dep function (see section 5.1.1.1) of the affected SWCs is used to determine which reconfiguration actions need to be grouped in sp to reach a target system configuration. The global deadline of sp is equal to the sum of all the reconfiguration actions deadlines,D where

Example 1.1 (Safe adaptation path) Consider a system with a set of mixed tasks hard and soft, both tasks are schedulable under EDF without reconfiguration. However, at time t₁ a

Fig. 5.8 Safe adaptation path overview.

reconfiguration task is triggered and safe adaptation path sp is released at t₁ from a source configuration (S) to a target configuration (T): while this adaptation does not change any task parameter of (τ₁), it extends the period of (τ₂) and introduces a new task as illustrated in Fig 5.8. With our approach, we want to determine whether or not a mixed task set (τ) is schedulable in the presence of a runtime adaptation. The actual execution behavior during a sp depends on online information, such as the time instant when the current adaptation trigger is released, and the release and execution patterns. Since our system is adaptive and evolve at runtime it is able to monitor and keep track of the information which are required for the schedulability analysis.

In chapter 2, we have shown how Baruah et al. [23] computes the total resource demand of sporadic tasks under EDF scheduling over an interval [L) i.e. DBF (see equation 5.1). By using the concept of DBF introduced in Definition 9, it is possible to formalize, bound and ensure the schedulability analysis of our safe adaptation path sp as follows:

Definition 12 (Demand-Bound Function for Safe Adaptation Path) DBF for sp_i can be cal-culated as follows:

• %  !

Definition 13 (Feasible Safe Adaptation Path) Let sp be a safe adaptation path. sp is feasi-ble (i.e., schedulable) if and only if Σ_τ∗_r∈Tdbf(T, L) ≤ L for some positive interval L, where

L = lgth(sp).

Definition 14 (Feasible Mapping) Let (Γ, ECU) denote a system with heterogeneous ECU, with

|Γ| = n and |ECU| = m. Let χ : Γ → ECU denote a mapping from the tasks of Γ to the ECUs in ECU. Let Λ_χ( j) denote the set of all tasks hard and soft mapped onto ECU_j by the mapping

def

χ : Λ_χ( j) = {i|χ(i) = j}. χ is a feasible mapping if and only if it satisfies the following condition:

Definition 15 (Feasible Adaptation) The adaptation is said to be feasible if (i) if the mapping is feasible and (ii) the safe adaptation path is feasible too.

7. ASLA’s reconfiguration model

The reconfiguration in our case is a sporadic task τ^∗_r has the following four timing properties:

(C^∗_r, D^∗_r, P^∗_r, time2adapt)—a worst case execution time C^∗_r, a relative deadline D^∗_r, a minimum inter-arrival time P^∗_r and the time instant in which jobs of τ^∗_r are executed time2adapt, which is used as the necessary bounded time in which we execute the reconfiguration and the system need not to be stopped. This time is mainly based on the work of [55], in which authors studied what is the best time to introduce new tasks into an EDF-scheduled system. τ^∗_r comprising

τ^∗_r are separated by at least P^∗_r time units and each one has the maximum execution time C^∗_r

deadlines of the reconfiguration actions in τ^∗_r. The utilization of the task τ^∗_r is defined as

⁵The terms reconfiguration action and job are used interchangeably

def _∗ ∗

= C_r /P_r which is the additional utilization while a task is being reconfigured i.e., the

required resources for reconfiguring a task on the ECUs within the remaining time after triggering

reconfiguration. Whereas the task system utilization is equal to ΣU_others

The reconfiguration task has a global view on the tasks running on the different ECUs. An adaptation transforms a current system configuration to a new system configuration by applying reconfiguration actions on the respective configurations. ASLA uses the following six reconfiguration actions: add, migrate,replace, link,unlink and remove.

1. add. adds a new component SWC_new to the current architecture by taking its used and provided ports, constraints and implementation. As the SWC_new is a stateful this action initializes the execution state with default values.(See Algorithm 2).

2. replace.The replacement can be classified into two categories given the required need. 2.1 upgrade–changes the behavior of an existing component with an improved version, the SWC will have the same interface, WCET, communication pattern temporal behavior, but has an improved internal behavior (runnables). 2.2 update– which implies adding a new functionality. The new functionality needs to be stored first in memory and as well as its communication pattern and the new version of runnables that will communicate with the new added functionality. The update is more difficult than the upgrade.

3. link. creates a binding from a provided port of a SWC to a used port of another SWC.i.e., link(SWC_ri, SWC_rj, P^out_ri, Pⁱⁿ_rj) a connection is created between the output port of the SWC_ri and the input port of the SWC_rj

4. unlink. disconnects a binding from the current architecture by using the same parameters as link

5. migrate. The SWC is moved from its current location (ECUs) to a new location, we consider a migration as a special case of SWC replacement in which the version of the component doesn’t change (See Algorithm 3)

6. remove. removes an existing component from the current architecture by taking the name of the component.This action first removes the SWC execution state and then the respective SWC is deleted.

8. Notations

The notation introduced here will be used throughout this chapter as well as the rest of the

manuscript.

Table 5.2 Main notation used throughout this chapter

5.2 ASLA’s algorithms

1. ASLA’s tasks allocation algorithm

ASLA’s mapping manager uses Algorithm 1 to deploy tasks on ECUs. O-TSMBA uses the application description (initial system configuration file-AUTOSAR XML file) as an input. This algorithm is executed whenever there is a need to compute a new deployment of tasks on ECUs. O-TSMBA produces the following outputs: (1) The mapping, that is where each of the tasks should be mapped to, and (2) The utilization, that is how much processor utilization we should allocate to these soft tasks, processor utilization for hard tasks is fixed. So that the deadlines for all the hard tasks are satisfied, even when there are faults and the probability of meeting the deadlines for the soft tasks is maximized. In order to handle tasks dependencies, our algorithm tries to allocate all corresponding SWCs of an OP as a single SWC (or task) when possible, Else, it splits these consolidated SWCs when necessary. O-TSMBA starts by combining SWCs as part of the same OPs (whether it is an application with soft or hard real-time requirements) ( Lines 1– 12). The OPs with hard real-time requirements are considered before the OPs with soft real-time requirements and the combined SWCs are ordered on decreasing order of their utilization (total utilization of OP) C_i/T_i for hard and EU_ci /T_i for soft, where EU_ci represents the Expected Utility of each ECU (Line 13).

A Tabu search algorithm takes the application (i.e., the set of OPs) and the ECUs as input and produces a solution “S” consisting of the allocation χ for all the tasks and a set of bandwidth values Q for all the tasks with soft real-time requirements. (Take note that we assume that a runnable is represented by a task and runnables to tasks mapping exists before O-TSMBA is used similarly to AUTOSAR). Once having the OPs with their timing requirements and the architecture, we will have an initial solution in which the tasks are mapped such that their utilization is evenly distributed among the ECUs (for the soft tasks we consider the Average utilization AET/T_i.). The bandwidth for the soft tasks is allocated to a value equal to their AET

(Line 14).

This initial solution can either be schedulable or not. A schedulable solution is the one that satisfies Liu & Layland utilization test for EDF [75], to determine if the task set combined of hard tasks and CBS servers is schedulable (see Definition 6) i.e.,

ALGORITHM 1: O-TSMBA (Γ^c, ECUs)

1. Γ^c = φ
2. for i = 1….n do
3. if SWC_i ∈/ Γ^c then
4. Find a composite SWC_j; SWC_j ∈ Dep(SWC_i)

[

5: Γ^c_j = Γ^c_j {SWC_i}

6. else
7. Γ^c_n(Γc₎ = {SWCi}

[

8: Γ^c = Γ^c Γ^c_n+1(Γc)

9. end if
10. end for

11. Sort Γ^c in descending order; start with Γ^c ∈ {OP_hard }and after Γ^c ∈ {OP_{so f t} }
12. S ^◦ = Initial Solution(Γ^c, ECUs)
13.        _S current _= S best _= S ◦
14. Cost^best = CostFunction(S ^◦)
15. TabuList = φ
16. for max_iter iterations do

17. NS = Generate Neighborhood(S ^current )

18. S ^current = Select Solution(NS)
19. if CostFunction(S ^current ) < Cost^best then
20. Cost^best = CostFunction(S ^current )
21. _S best _= S current
22. end if

23. TabuList = TabuList ^[S ^current
24. end for
25. return S ^best

The total utilization which needs to be bounded by 1 is the sum of utilization of: the hard tasks, soft tasks and the reconfiguration task. For hard tasks it is simply, (C_i/T_i) where C_i is the execution time including the reconfiguration overhead, for soft tasks it is Q_j/T_j, and for the reconfiguration task, the utilization is the worst-case utilization needed to reconfigure tasks

U_RQ^ECUj . The neighborhood of the current solution is generated using design transformation (moves) that changes the current system implementation (Line 19). The neighborhood can be very large, thus we consider a limited number of neighboring solutions, called candidate set. Similarly to the original TSMBA. Two moves are considered in the mapping algorithm

(i) Mapping move (Mm) and (ii) Bandwidth Moves (BM). In (i) the mapping for the tasks is changed by selecting randomly a set of consolidated SWCs from a randomly selected ECU, tries to allocate them as a single SWC and allocate them to another ECU also selected randomly. The cost for doing this operation is given to O-TSMBA to evaluate the solution. In (ii) BM, the bandwidth of tasks is changed also by selecting randomly consolidated SWCs with soft real-time requirements from randomly selected ECUs. In O-TSMBA algorithm all the visited solutions are maintained by the tabu search in a TabuList to avoid revisiting them again (Line 17). All the solutions that have been already visited are marked as Tabu and are put in TabuList, this list is updated in (Line 25). The non-tabu solution with the minimum cost is chosen and exploration continues. The selected solutions (Line 20) are the ones which minimize the following cost function:

• ^max(0, UECU_i ^−1) ×wpenalty

∀ECU_i∈ECUs

(5.3)

+ _∑ (1 −QoS(r_i)) ×w_i(r_i, ECU_j)

∀r_i:R(r_i)=So f t

where w_penalty corresponds to a very large penalty added to the cost of a solution in case of hard real-time tasks are not scheduled (in other words the utilization of the ECU’s processor is greater than one). In case the hard tasks are schedulable the first is 0 and the second term of the cost function is the maximization of the QoS of the soft tasks. Different weights w_i(r_i, ECU_j) can be assigned to the soft task. These weights represent how important is to satisfy the QoS of a given task when being mapped on ECU_j. Similarly to TSMBA, our algorithm iterates the procedure until a bound number of iteration max_iter is reached which is given by the designer (Line 18).

2. ASLA’s task adaptation algorithm–The Case for adding a new tasks

As we said in chapter 4 section 4.3, the RM is a sporadic task that gets triggered upon the reception of an adaptation triggers (requests for adding new tasks, requests for migrating failed tasks/and or failed ECUs, replacement of tasks with an improved version and removing tasks). ASLA’s reconfiguration manager uses Algorithm 2 for adding a new application at runtime

(i.e., TSeRBA). TSeRBA uses the following inputs: (1) a solution schedulable and tagged optimized obtained from mapping manager using O-TSMBA algorithm and (2) the adaptation triggers from the monitor (in this case: request for adding a new application). The output of TSeRBA is a new system configuration which needs to be schedulable. To deal with the current reconfiguration, the algorithm starts by finding the target ECU to hold the new application (Line 3– 8). So it maintains an ordered list of ECU candidates, and the one which gives the best QoS is selected as the target ECU. This QoS is the probability of meeting the deadline for soft tasks and it depends on the allocated bandwidth Q_i [11], then if the mapping is still feasible (Line 10) and the time2adapt is reached, the new task is simply added in the target ECU (Lines 11, 12, 13 and 20) (see Definition 10). Thus, the RM loads, instantiates and connects a new component safely without affecting other components, changes the network schedule, and dynamically finds and binds to the correct interface as no SWC knows how to use this new component and the network schedule has to be reorganized to accommodate the communication pattern of this component (Lines 12, 13 and 14). If the RM cannot analyze and schedule this new component i.e., the mapping is not feasible (see Definition. 14) (Line 15), in that case the bandwidth Q associated with soft tasks on that ECU is decreased in proportion do their expectations, and then the new task can be mapped on the ECU. A completely new resource is added to hold the new task if the mapping is not feasible even when we adjust the bandwidth (Line 16). For our example task system described in section 5.1.2, upon the receipt of an adaptation trigger to add new task to the system; TSeRBA tries to find the best target ECU to hold this new task (as shown in Figure 5.9). ECU2 is selected as a candidate for adding this new task since it gives the best QoS. Furthermore, in Figure 5.9, the compressed task τ_i(C_i, T_i) is τ₈(15, 35) since it is the only hard task on ECU2. The only new task in Fig 5.9 is τ_new(1, 4), while the other unchanged tasks are: τ₁(9, 150), τ₃(12, 190) and τ₄(19, 300). Suppose the release time of the current instance t₀ = 0 and the time to accommodate the new request (i.e., inserting a new task) t_r = 2, τ₈(15, 35) is compressed into τ₈(15, 70), thus using Definition 10, we have C_i(t_r) = 2 and U₈ +U₁ +U3 +U₄ = (15/35) + (9/150) + (19/300) + (12/190) = 0.61. U_new = U₈ −U₈^′ = (15/35) −(15/70) = 1/5. From [55] and according to Definition 10, we get time2adapt = 35 −2/(1/5) = 25 > t_r.It is shown in the Figure 5.9 that no deadline is missed.

3. ASLA’s task adaptation algorithm–The Case for migrating tasks

Similarly to Algorithm 2. ASLA’s reconfiguration manager uses Algorithm 3 to migrate tasks between ECUs. In this case, TSeRBA tries to find first the target ECU (Line 3– 11) to hold the failed tasks on ECU3 (i.e.,τ₅, τ₆, τ₁₀) (as shown in Figure 5.10). ECU1 is determined an infeasible solution since the combined utilization on ECU1 would exceed 100% if τ₁₀ were allocated on ECU1 already hosting τ₂, τ₇, τ₉ and τ₁₀ (0.32 + 0.32 + 0.4 + 0.186 = 1.23) (Line 14). TSeRBA tries to decrease the server bandwidth of the soft tasks allocated on ECU1,

ALGORITHM 2: TSeRBA for adding a new SWC

1. As soon as the add request is triggered

2. for all SWC_i such that χ(SWC_i) ∈ ECUs do
3. QoS_best = 0
4. for all ECU_j ∈ ECUs do

6. if QoS_curr > QoS_best then
7. ECU_target = ECU_j; QoS_best = QoS_curr
8. end if

9. if Feasible Mapping then

10. When (time2adapt = δ )

11. load the SWC_i();
12. link SWC_i to the correct interface();
13. Change the network schedule();

14. else if Ad just Qs Proportionally(SWC_i, ECU_j) then

15. recomputeχ

else

ECUs ← ECUs + ECU_new

end

16. end if

17. U ndo Ad just Qs(ECU_j)
18. end for

19. Add(SWC_i, ECU_target)
20. end for

Fig. 5.9 New tasks insertion example.

however again no schedulable task set on ECU1 is found (Line 15) and ECU1 is eliminated as a choice to host the failed tasks.

The set of candidate ECUs is updated (Line 5) and TSeRBA is attempted again and selects ECU2 as the target migration node. Since the total processor utilization available for the soft tasks on ECU2 if τ₁₀ is migrated on it is equal to 1 −(0.49 + 0.32) = 0.26. Therefore, the utilization

Fig. 5.10 Tasks migration example.

desired by τ₁₀ can be made available by decreasing the bandwidth of the soft tasks on ECU2 in proportion to their expected utilities EUs. The values of EU for the allocated soft tasks (i.e.,

τ₁, τ₃, τ₄) on ECU2 are: 28, 29 and 31, respectively. For instance, the available utilization and the changed bandwidth for τ₁ is computed as follows: U_τ1 = (28/(28 + 29 + 31)) ∗0.26 = 0.09, Q^new_τ1 = 0.09 ∗150 = 12. In the same way we compute U_τi and Q^new_τi with i ∈ {3, 4}.Note that if the task to migrate cannot be allocated to any of ECU1 or ECU2, thereby an additional ECU is required (Line 17).

ALGORITHM 3: TSeRBA for migrating SWCs

1. As soon as the failure request is triggered (i.e a set of failed ECUs)

2. for all SWC_i ∈ Γ^c such that χ(Γ^c, ECU_faulty) do
3. QoS_best = 0
4. get all the utilization of the Op mapped on ECU_faulty
5. U_i = getUtilization(SWC_i); SWC_i ∈ Γ^c
6. for all ECU_j ∈ ECUs; ECU_j ∈/ ECU_faulty do

7. Find the best-fit ECUs(which is the one that gives the best QoS)

8: = _∑ GetQoS(Γ_k)

∀Γ_k:χ(Γ_k)∈ECU_j

9. if QoS_curr > QoS_best then
10. ECU_target = ECU_j; QoS_best = QoS_curr
11. end if

12. Sorts Γ^cin descending order of their utilization, Γ^c with hard requirement first and after Soft.
13. if Feasible Mapping then
14. Migrate(Γ^c, ECU_target)

15. else if Picks the biggest Γ^c_{kso f t} ;Γ^c_{kso f t} ∈ ECU_target; Ad justQsProportionally(Γ^c, ECU_j) then
16. recomputeχ

else

ECU s ← ECU s + ECU_new

end

17. end if

18. U ndoAd justQs(ECU_j)

19. end for

20. end for

5.3 Summary

In this Chapter, we have considered the theoretical and the technical aspect of ASLA framework described in Chapter 4. More specifically, we have formalized and solved the problem faced when tackling runtime adaptation in automotive real-time systems. We have shown how the runtime support to AUTOSAR is realized by TSeRBA algorithm “Tabu Search Reconfiguration and Bandwidth Allocation” as it allows the dynamic allocation of Software components(SWCs) with both Hard and Soft real-time constraints as well as supports the insertion, the deletion and the migration of SWCs at runtime. In the next Chapter,the theoretical resul