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.
- 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^{1}. 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
^{1}Dealing with End-to-End delay of an OP is beyond the scope of this work, we calculate it similarly to [71]
r1 | m r1r2 | r2 | m r2r3 | r | m r3r4 | r4 | m r4r5 | r5 | ||||||
3 | ||||||||||||||
Sensor | mr6 | _{r}_{7} mr7r8 | mr8r9 | actuator | ||||||||||
r6 | r 7 | r8 | r9 | |||||||||||
Sensor | actuator | |||||||||||||
Alloc | Alloc | Alloc | ||||||||||||
ECU2
Sensor
ECU1
Gateway |
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_{1}, . . . , 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 ω,ω^{−1} returns all the runnables inside an SWC. Runnables receive data via input ports P^{in}_{r}_{i} and send out the data via output ports P^{out}_{r}_{i}. P^{in}_{r}_{i} and P^{out}_{r}_{i} 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^{in}_{r}_{j} to the output port of r_{i},P^{out}_{r}_{i}. 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^{2}
χ: 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} = Σ_{∀}_{r}_{i}_{∈}_{ω}−1 C_{i}, T_{j} = min_{∀}_{r}_{i}_{∈}_{ω}−1 T_{i} and the deadline is
^{2}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_{∀}_{r}_{i}_{∈}_{ω}−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.
- 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 | ||||||||||
U_{i} | 0.19 | 0.186 | 0.16 | 0.1 | 0.165 | 0.15 | 0.4 | 0.4 | 0.42 | 0.32 | 0.32 | ||||||||||
Q_{i} | 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 ECU_{1} 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.
- 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
^{3}The number of OPs depends on the number of applications in the system ^{4}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.
- 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:
(
^{v}1 ^{=} ^{c}i,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} + ⌈ ^{v}^{k} ⌉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 = ⌈ ^{v}^{k} ⌉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}^{ECU}^{j} =P{c_{i,k} = h}. Since we know that c_{i,k} is time invariant, as U_{i}^{ECU}^{j} (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 _{=} _{MΠ}k−1 | |||||
where: | _{U}^{ECU}j _{(0)} _{.}_{ }_{..} _{U}^{ECU}j _{(0)} | 0 | 0 .. | ||
M = | _{U}^{iECU}j _{(1)} _{.} | _{..} _{U}^{iECU}j _{(1)} | _{U}^{ECU}j _{(0)} | 0 ..^{!} | |
i | i | i | |||
and | _{π}_{0}k | ||||
_{π}_{1}k | |||||
_{Π}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 = ⌈ ^{v}^{k} ⌉Ti, the
Q_{i}
probabilistic guarantee Qos(δ_{i}) can be easily computed as :
^{δ}i
^{Qos(δ}i^{) =} ^{D(}^{⌈}_{T}_{i} ^{⌉}^{Q}i^{)}
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}^{ECU}^{j} . 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:
^{L}i
N = _{∑ }U_{i}^{ECU}^{j} (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.
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
- 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.
- 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 | $ | ^{P}r | % | ! | 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 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}) | = (t_{0} + T_{i}) − | C_{i}(t_{r}) | |||||
U_{i} | − | U^{′} | U_{i} | − | U^{′} | ||
i | i |
C_{i}(t_{r})
^{i f d}^{i} ^{−} _{U}_{i} _{−U}_{i}′ ^{>} ^{t}^{r}
C_{i}(t_{r})
^{i f d}^{i} ^{−} _{U}_{i} _{−U}_{i}′ ^{≤} ^{t}^{r}
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_{0} + T_{i} to t_{0} + T^{′}_{i} where t_{0} is the release time of the current instance. At t_{r}, t_{0} ≤ t_{r} ≤ t_{0} + T_{i} ≤ t_{0} + 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
D | (sp ) = ΣD^{n}^{i} | (τ^{∗}), 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 t_{1} a
Fig. 5.8 Safe adaptation path overview.
reconfiguration task is triggered and safe adaptation path sp is released at t_{1} 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 sp_{i} can be cal-culated as follows:
- % !
DBF |
sp_{i} | (τ^{∗}, lgth(sp | )) = max 0, | lgth(sp_{i}) −D_{r}^{∗} | + 1 .C^{∗} | with : | |||
r | i | P_{r}^{∗} | r | ||||||
C^{∗} | = Σc^{n} | (τ^{∗}) | |||||||
r | j^{∗}=1 | r | |||||||
n | |||||||||
_{D}_{r}∗ | = Σd_{j}∗_{=1}(τ_{r}^{∗}) | ||||||||
_{lgth}_{(}_{sp}_{i}_{)}_{>}_{ D}∗ | |||||||||
r | |||||||||
and | D_{r}^{∗} = P_{r}^{∗}. |
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}_{∈}_{T}dbf(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:
∀ j : 1 ≤ j ≤ m : Σ_{j}(U_{j}(Λ_{χ} ( 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.
- 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
n reconfiguration actions ^{5} | { | r ^{∈} | i | def | { | 1 | 2 | n | }} | . The jobs of |
r | ||||||||||
, or so-called jobs i.e., | τ^{∗} | τ | , τ^{∗} = | j^{∗} | , j^{∗} | , .., j^{∗} |
τ^{∗}_{r} are separated by at least P^{∗}_{r} time units and each one has the maximum execution time C^{∗}_{r}
time units and must complete within D^{∗} | time units after its arrival. So, C^{∗} | def | (τ^{∗}) where | |||||||||||
= Σc^{n} | ||||||||||||||
{ | ∗ | } | r | r | j^{∗}=1 | r | ||||||||
1 | 2 | denotes the processing times of n reconfiguration actions of the reconfiguration | ||||||||||||
c_{j}∗ | , c_{j}∗ | , .., c_{j}_{n} | ||||||||||||
task τ_{r}^{∗} | ∗ | _{=1}(τ_{r}^{∗}) where | { | 1 | 2 | ∗ | } | |||||||
. and D_{r}^{∗} = Σd_{j}^{n} | d_{j}∗ | , d_{j}∗ | , .., d_{j}_{n} | denotes the execution durations or the |
deadlines of the reconfiguration actions in τ^{∗}_{r}. The utilization of the task τ^{∗}_{r} is defined as
^{5}The terms reconfiguration action and job are used interchangeably
+ U^{ECU}_{RQ}.
U^{ECU}_{RQ}
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.
- 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).
- 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.
- 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^{in}_{rj}) a connection is created between the output port of the SWC_{ri} and the input port of the SWC_{rj}
- unlink. disconnects a binding from the current architecture by using the same parameters as link
- 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)
- 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.
- Notations
The notation introduced here will be used throughout this chapter as well as the rest of the
manuscript.
Symbol | Description | |
r_{i} | i^{th}runnable | |
O_{i} | i^{th}operational chain | |
ECU_{j} | ||
U_{i} | (h) | Probability of job j has an execuion timeof h on ECU_{j} |
ECU_{j} | ||
C_{i} | The WCET of hard task on ECU_{j} | |
D_{i} | The deadline of hard task | |
δ _{i} | soft deadline | |
QoS(δ_{i}) | The probability of meeting the deadline δ_{i} | |
^{T}j | The period of soft and hard tasks | |
Q_{j} | The bandwidth server | |
Q_{j}/T_{j} | The utilisation of soft tasks | |
C_{j}/T_{j} | The utilisation of hard tasks | |
^{τ}i | i^{th}periodic task | |
τ_{r}^{∗} | reconfiguration (sporadic)task | |
C_{r}^{∗} | WCET of τ_{r}^{∗} | |
D_{r}^{∗} | relative deadline of τ_{r}^{∗} | |
P_{r}^{∗} | Period of τ_{r}^{∗} | |
ECU_{j} | ||
^{U}RQ | The utilization required for the reconfiguration | |
Table 5.2 Main notation used throughout this chapter
5.2 ASLA’s algorithms
- 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_{c}_{i} /T_{i} for soft, where EU_{c}_{i} 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.,
∑ | C_{j} | + | ∑ | Q_{j} | + U_{RQ}^{ECU}^{j} ≤ 1. | |
T | T | j | ||||
∀τ_{i}∈OP_{Hard}∩χ(τ_{i})=ECU_{j} | j | ∀τ_{i}∈OP_{Soft}∩χ(τ_{i})=ECU_{j} | ||||
ALGORITHM 1: O-TSMBA (Γ^{c}, ECUs)
- Γ^{c} = φ
- for i = 1….n do
- if SWC_{i} ∈/ Γ^{c} then
- Find a composite SWC_{j}; SWC_{j} ∈ Dep(SWC_{i})
[
5: Γ^{c}_{j} = Γ^{c}_{j} {SWC_{i}}
- else
- Γ^{c}_{n(Γ}c_{)} = {SWCi}
[
8: Γ^{c} = Γ^{c} Γ^{c}_{n+1(Γ}_{c}_{)}
- end if
- end for
- Sort Γ^{c} in descending order; start with Γ^{c} ∈ {OP_{hard} }and after Γ^{c} ∈ {OP_{so f t} }
- S ^{◦} = Initial Solution(Γ^{c}, ECUs)
- _{S} current _{=} _{S} best _{=} _{S} ◦
- Cost^{best} = CostFunction(S ^{◦})
- TabuList = φ
- for max_iter iterations do
- NS = Generate Neighborhood(S ^{current} )
- S ^{current} = Select Solution(NS)
- if CostFunction(S ^{current} ) < Cost^{best} then
- Cost^{best} = CostFunction(S ^{current} )
- _{S} best _{=} _{S} current
- end if
- TabuList = TabuList ^{[}S ^{current}
- end for
- 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}^{ECU}^{j} . 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,} ^{U}ECU_{i} ^{−1)} ^{×w}penalty
∀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).
- 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 τ_{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 t_{0} = 0 and the time to accommodate the new request (i.e., inserting a new task) t_{r} = 2, τ_{8}(15, 35) is compressed into τ_{8}(15, 70), thus using Definition 10, we have C_{i}(t_{r}) = 2 and U_{8} +U_{1} +U3 +U_{4} = (15/35) + (9/150) + (19/300) + (12/190) = 0.61. U_{new} = U_{8} −U_{8}^{′} = (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.
- 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.,τ_{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
- As soon as the add request is triggered
- for all SWC_{i} such that χ(SWC_{i}) ∈ ECUs do
- QoS_{best} = 0
- for all ECU_{j} ∈ ECUs do
5: | QoS_{i} = GetQoS(SWC_{i}); QoS_{currECU}_{j} = | ∑ | GetQoS(SWC_{k}) |
∀SWC_{k}:χ(SWC_{k})∈ECU_{j} |
- if QoS_{curr} > QoS_{best} then
- ECU_{target} = ECU_{j}; QoS_{best} = QoS_{curr}
- end if
- if Feasible Mapping then
- When (time2adapt = δ )
- load the SWC_{i}();
- link SWC_{i} to the correct interface();
- Change the network schedule();
- else if Ad just Qs Proportionally(SWC_{i}, ECU_{j}) then
- recomputeχ
else
ECUs ← ECUs + ECU_{new}
end
- end if
- U ndo Ad just Qs(ECU_{j})
- end for
- Add(SWC_{i}, ECU_{target})
- 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
^{QoS}currECU_{j}
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, 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
- As soon as the failure request is triggered (i.e a set of failed ECUs)
- for all SWC_{i} ∈ Γ^{c} such that χ(Γ^{c}, ECU_{faulty}) do
- QoS_{best} = 0
- get all the utilization of the Op mapped on ECU_{faulty}
- U_{i} = getUtilization(SWC_{i}); SWC_{i} ∈ Γ^{c}
- for all ECU_{j} ∈ ECUs; ECU_{j} ∈/ ECU_{faulty} do
- Find the best-fit ECUs(which is the one that gives the best QoS)
8: = _{∑} GetQoS(Γ_{k})
∀Γ_{k}:χ(Γ_{k})∈ECU_{j}
- if QoS_{curr} > QoS_{best} then
- ECU_{target} = ECU_{j}; QoS_{best} = QoS_{curr}
- end if
- Sorts Γ^{c}in descending order of their utilization, Γ^{c} with hard requirement first and after Soft.
- if Feasible Mapping then
- Migrate(Γ^{c}, ECU_{target})
- else if Picks the biggest Γ^{c}_{kso f t} ;Γ^{c}_{kso f t} ∈ ECU_{target}; Ad justQsProportionally(Γ^{c}, ECU_{j}) then
- recomputeχ
else
ECU s ← ECU s + ECU_{new}
end
- end if
- U ndoAd justQs(ECU_{j})
- end for
- 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