Essay Writing Service

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)

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 output1. 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

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

r1 r1r2 r2 r2r3 r r3r4 r4 r4r5 r5
Sensor mr6 r7     mr7r8 mr8r9 actuator
r6 7 r8 r9
Sensor actuator
Alloc Alloc Alloc







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. Software architecture

We model an application as a set R of interacting runnables ri ∈ R. R is composed of n runnables,r1, . . . , rn. Each runnable is part of an atomic SWC, swj, which may have several runnables. In order to represent a relationship between a runnable, ri and the SWC, swj, we define a function ω such that ω(ri) = swj when swj contains ri. The function inverse of ω,ω−1 returns all the runnables inside an SWC. Runnables receive data via input ports Pinri and send out the data via output ports Poutri. Pinri and Poutri are defined as a set of input, output ports of a runnable ri, respectively. Runnables interact between each other via £, which is a set of links. An interaction between runnables is represented by a link li. Runnables exchange data through signals si on the links. We define Snd(si),Rcv(si) as a function returning the runnables that sends a data signal si

and function returning the runnables receiving a data signal si, respectively. In order to express the dependency relationship between the SWCs, we define a function Dep such that Dep(ri) returns all the runnables that depend on ri, in other words a runnable ri dependent on a rj, if there is a link li between both runnables and this link connects the input port of rj,Pinrj to the output port of ri,Poutri. 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 function2

χ: 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] ri, which releases a job every Ti units of time, where each job consumes at most Ci units of computation time and should be completed within a relative deadline Di = Ti. Both runnables Soft and Hard are periodic and have a period Ti. A subset OPi ⊂R contains runnables for the ith operational chain out of total m operational chains. In certain cases, a runnable ri can be an element of OPi and also an element of OPl, where i ̸= l. The relationship among the tasks in the ith operational chain OPi is represented by a directed graph Gi. In this graph, a node u denotes a runnable, ri ∈ R, and an edge (u, v) of Gi indicates data flow from u to v; the edge

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

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

OPi. This function is also applicable to a SWC. An OPi represented by a pair (TOPi, ∆) where

TOPi is the period of the application OPi 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 Gi and the completion time of the last executed node in Gi. All runnables in OPi have the same period TOPi.

So a runnable with hard real-time requirement ri is characterized by its Worst Case Execution Time (WCET) Ci and a deadline Di. For a hard runnable ri, the WCET CECUij is known for

each processing element ECUj where ri is considered for the allocation. Soft runnables are

characterized by the Probability Distribution Function (PDF) UECUij of their execution times and a soft deadline δi. UECUij (h) is the probability that the job Ji,k of ri has an execution time of h

on the processing elements ECUj. Each soft runnable (or task) must have An Expected Utility (EU) function EUci(ri, ECUj) for each ECUj whose values is defined as the probability-weighted sum of possible values of the soft tasks’ execution time (i.e., ci). The QoS of a soft runnable ri is defined as the probability of meeting the deadline δ i, i.e, QoS (δi) = P{fi,k ≤ ari,k + δi},where fi,k and ari,k are the finishing and arrival time of the kth job of runnable ri, respectively. An SWC swj is also characterized by a worst-case execution time Cj and a deadline Dj, however, it differs from runnables in the sense that it: Cj = Σriω−1 Ci, Tj = minriω−1 Ti and the deadline is

2Allocating 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

j = minriω−1 Di. Let Ui denote the utilization of an SWC swj with hard real-time requirement and it is defined as Cj/Tj. whereas an SWC swj with Soft real-time requirement its utilization is defined as Qj/Tj. Throughout this dissertation, we restrict ourselves to implicit-deadline task systems. Hardware architecture

We model the hardware architecture as an undirected graph Gh = (Vh, Fh). Nodes Vh represent a set of hardware resources and the edges Fh 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 mij 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 ECUi ∈ 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 (Qi, Ti) where Qi (bandwidth server) represents a time that the soft task is allowed to use ECU every period Ti. 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.

  1. 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 3 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 4) 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.

Task τ 1 2 3 4 5 6 7 7 8 9 10
Ui 0.19 0.186 0.16 0.1 0.165 0.15 0.4 0.4 0.42 0.32 0.32
Qi 29 29 31 31 33 35

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 τ7 to τ7; this adaptation will lead other tasks on ECU1 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.

  1. 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

3The number of OPs depends on the number of applications in the system 4The 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.

  1. 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 Qi. As we said previously in Section 5.1.1, for a given soft real-time task τi, The QoS ri is defined as the probability of meeting the deadline δ i, i.e., QoS (δi) = P{fi,k ≤ ari,k + δi},where fi,k and ari,k are the finishing and arrival time of the kth job of runnable ri, respectively. This QoS guarantee is calculated by by modeling the CBS server(serving the Soft tasks) as a queue [70]. The arriving job ji,k are seen as tokens to be served by the server having the capacity Qi (where is the capacity

of the server Qi). As we had previously described, the PDF of the computation times of jobs of the tasks allocated on the ECUj is defined to be UECUij . In this model, UECUij represents the PDF of the incoming requests for the queue: UECUij (h) = P{ci,k = h}, Probability that the arriving

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


v= ci,1

vk = max{0, vk−1 −Qi}+ ci,k

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

fi,k = ari,k + ⌈ vk ⌉Ti


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

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


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

πm(k) = P{vk = m} = P{max{vk−1 −Qi, 0}+ ck = m}

Finally the solution comes out to be:


πm(k) = (Ui(m) ×πh(k−1)) h=0

 (Ui(m −h + Qi) ×πh(k−1))


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

Π= k−1
where: UECU(0)  .  ..  UECU(0) 0 0  ..
M = UiECU(1)  . ..  UiECU(1) UECU(0) 0  ..!
i i i
and π0k

Π= πk




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., ci,k < Qi. If this condition is not satisfied, the difference between deadline fi,k assigned by the server for the job Ji,k and

the job release time ari,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,


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


D(v) =  πm.


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


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


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 UiECUj . The PDF is finite and lets say it has a length of Li. The server

capacity is given as Qi.

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:


N = ∑ UiECUj (h) ×h ×JOBS


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. 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.

The worst case length of the queue (for 100 jobs) came out to be 67. Thus this was set as the
truncation point for calculation of the M matrix. The dimensions of M are fixed at 67×67. The
M matrix results as follows:

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−40. 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

  1. 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.

  1. 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.

r $ Pr % ! r
def L D r (5.1)
dbf(τ , L) = max  0, + 1  .C

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 Ti to

Ti so the utilization of the task is reduced to Ui = Ci/Ti which gives some room to insert a new task i.e., the freed utilization Ui −Ui. if a task τi is compressed at tr, then:

di −

δ =


Ci(tr) = (t0 + Ti) − Ci(tr)
Ui U Ui U
i i


i f di  Ui −Ui′ > tr


i f di  Ui −Ui′  tr

where di is the deadline of the current instance of the task τi. Ci(tr) is the new computation time of τr which is executed with the new period Ti and tr is the time to accommodate the new requests during which the deadline of the instance is delayed from t0 + Ti to t0 + Ti where t0 is the release time of the current instance. At tr, t0 ≤ tr ≤ t0 + Ti ≤ t0 + Ti.

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(spi) 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 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

D (sp ) = ΣDni ), with lgth(sp ) > D (sp )
max def max   i
i j=1 r i

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 t1 a

Fig. 5.8 Safe adaptation path overview.

reconfiguration task is triggered and safe adaptation path sp is released at t1 from a source configuration (S) to a target configuration (T): while this adaptation does not change any task parameter of (τ1), it extends the period of (τ2) 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 spi can be cal-culated as follows:

  • %  !


spi , lgth(sp )) = max  0, lgth(spi) −Dr + 1  .C with :
r i Pr r
C = Σcn )
r j=1 r
Dr = Σdj=1r)
lgth(spi)> D
and Dr = Pr.

Definition 13 (Feasible Safe Adaptation Path) Let sp be a safe adaptation path. sp is feasi-ble (i.e., schedulable) if and only if ΣτrTdbf(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 ECUj by the mapping


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

∀ j : 1 ≤ j ≤ m : Σj(Ujχ ( j)) ≤ 1) (5.2)

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.

  1. ASLA’s reconfiguration model

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

(Cr, Dr, Pr, time2adapt)—a worst case execution time Cr, a relative deadline Dr, a minimum inter-arrival time Pr 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

n reconfiguration actions 5 { i def { 1 2 n }} . The jobs of
, or so-called jobs i.e., τ τ , τ = j , j , .., j

τr are separated by at least Pr time units and each one has the maximum execution time Cr

time units and must complete within D time units after its arrival. So, C def ) where
= Σcn
{ } r r j=1 r
1 2 denotes the processing times of n reconfiguration actions of the reconfiguration
cj , cj , .., cjn
task τr =1r) where { 1 2 }
. and Dr = Σdjn dj , dj , .., djn denotes the execution durations or the

deadlines of the reconfiguration actions in τr. The utilization of the task τr is defined as

5The terms reconfiguration action and job are used interchangeably




= Cr /Pr 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 ΣUothers

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 SWCnew to the current architecture by taking its used and provided ports, constraints and implementation. As the SWCnew is a stateful this action initializes the execution state with default values.(See Algorithm 2).
  1. 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.
  1. link. creates a binding from a provided port of a SWC to a used port of another SWC.i.e., link(SWCri, SWCrj, Poutri, Pinrj) a connection is created between the output port of the SWCri and the input port of the SWCrj
  1. unlink. disconnects a binding from the current architecture by using the same parameters as link
  1. 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)
  1. 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.
  1. Notations

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


Symbol Description
ri ithrunnable
Oi ithoperational chain
Ui (h) Probability of job j has an execuion timeof h on ECUj
Ci The WCET of hard task on ECUj
Di The deadline of hard task
δ i soft deadline
QoS(δi) The probability of meeting the deadline δi
Tj The period of soft and hard tasks
Qj The bandwidth server
Qj/Tj The utilisation of soft tasks
Cj/Tj The utilisation of hard tasks
τi ithperiodic task
τr reconfiguration (sporadic)task
Cr WCET of τr
Dr relative deadline of τr
Pr Period of τr
URQ The utilization required for the reconfiguration

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 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) Ci/Ti for hard and EUci /Ti for soft, where EUci 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/Ti.). 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.,

Cj + Qj + URQECUj ≤ 1.
T T j
∀τi∈OPHard∩χ(τi)=ECUj j ∀τi∈OPSoft∩χ(τi)=ECUj


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


5: Γcj = Γcj {SWCi}

  1. else
  2. Γcn(Γc) = {SWCi}


8: Γc = Γc Γcn+1(Γc)

  1. end if
  2. end for
  1. Sort Γc in descending order; start with Γc ∈ {OPhard }and after Γc ∈ {OPso f t }
  2.  = Initial Solution(Γc, ECUs)
  3.        S current = S best = S ◦
  4. Costbest = CostFunction(S )
  5. TabuList = φ
  6. for max_iter iterations do
  1. NS = Generate Neighborhood(S current )
  1. current = Select Solution(NS)
  2. if CostFunction(S current ) < Costbest then
  3. Costbest = CostFunction(S current )
  4. S best = S current
  5. end if
  1. TabuList = TabuList [current
  2. end for
  3. 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, (Ci/Ti) where Ci is the execution time including the reconfiguration overhead, for soft tasks it is Qj/Tj, and for the reconfiguration task, the utilization is the worst-case utilization needed to reconfigure tasks

URQECUj . 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, UECUi −1) ×wpenalty



 (1 −QoS(ri)) ×wi(ri, ECUj)

∀ri:R(ri)=So f t

where wpenalty 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 wi(ri, ECUj) 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 ECUj. Similarly to TSMBA, our algorithm iterates the procedure until a bound number of iteration maxiter is reached which is given by the designer (Line 18).

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

As we said in chapter 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 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 Qi [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 111213 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 1213 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(Ci, Ti) is τ8(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: τ1(9, 150), τ3(12, 190) and τ4(19, 300). Suppose the release time of the current instance t0 = 0 and the time to accommodate the new request (i.e., inserting a new task) tr = 2, τ8(15, 35) is compressed into τ8(15, 70), thus using Definition 10, we have Ci(tr) = 2 and U8 +U1 +U3 +U4 = (15/35) + (9/150) + (19/300) + (12/190) = 0.61. Unew = U8 −U8 = (15/35) −(15/70) = 1/5. From [55] and according to Definition 10, we get time2adapt = 35 −2/(1/5) = 25 > tr.It is shown in the Figure 5.9 that no deadline is missed.

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

Similarly to Algorithm 2. ASLA’s reconfiguration manager uses Algorithm 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.,τ5, τ6, τ10) (as shown in Figure 5.10). ECU1 is determined an infeasible solution since the combined utilization on ECU1 would exceed 100% if τ10 were allocated on ECU1 already hosting τ2, τ7, τ9 and τ10 (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
  1. for all SWCi such that χ(SWCi) ∈ ECUs do
  2. QoSbest = 0
  3. for all ECUj ∈ ECUs do
5: QoSi = GetQoS(SWCi); QoScurrECUj = GetQoS(SWCk)
  1. if QoScurr > QoSbest then
  2. ECUtarget = ECUj; QoSbest = QoScurr
  3. end if
  1. if Feasible Mapping then
  1. When (time2adapt = δ )
  1. load the SWCi();
  2. link SWCi to the correct interface();
  3. Change the network schedule();
  1. else if Ad just Qs Proportionally(SWCi, ECUj) then
  1. recomputeχ


ECUs ← ECUs + ECUnew


  1. end if
  1. U ndo Ad just Qs(ECUj)
  2. end for
  1. Add(SWCi, ECUtarget)
  2. 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 τ10 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 τ10 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.,

τ1, τ3, τ4) on ECU2 are: 28, 29 and 31, respectively. For instance, the available utilization and the changed bandwidth for τ1 is computed as follows: Uτ1 = (28/(28 + 29 + 31)) ∗0.26 = 0.09, Qnewτ1 = 0.09 ∗150 = 12. In the same way we compute Uτi and Qnewτ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)
  1. for all SWCi ∈ Γc such that χ(Γc, ECUfaulty) do
  2. QoSbest = 0
  3. get all the utilization of the Op mapped on ECUfaulty
  4. Ui = getUtilization(SWCi); SWCi ∈ Γc
  5. for all ECUj ∈ ECUs; ECUj ∈/ ECUfaulty do
  1. Find the best-fit ECUs(which is the one that gives the best QoS)

8: =  GetQoS(Γk)


  1. if QoScurr > QoSbest then
  2. ECUtarget = ECUj; QoSbest = QoScurr
  3. end if
  1. Sorts Γcin descending order of their utilization, Γc with hard requirement first and after Soft.
  2. if Feasible Mapping then
  3. Migrate(Γc, ECUtarget)
  1. else if Picks the biggest Γckso f t ;Γckso f t ∈ ECUtarget; Ad justQsProportionally(Γc, ECUj) then
  2. recomputeχ


ECU s ← ECU s + ECUnew


  1. end if
  1. U ndoAd justQs(ECUj)
  1. end for
  1. 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

EssayHub’s Community of Professional Tutors & Editors
Tutoring Service, EssayHub
Professional Essay Writers for Hire
Essay Writing Service, EssayPro
Professional Custom
Professional Custom Essay Writing Services
In need of qualified essay help online or professional assistance with your research paper?
Browsing the web for a reliable custom writing service to give you a hand with college assignment?
Out of time and require quick and moreover effective support with your term paper or dissertation?