Roberto Medina

Etienne Borde

Laurent Pautet

Scheduling Multi-Periodic Mixed-Criticality DAGs on Multi-Core Architectures

Thanks to Mixed-Criticality (MC) scheduling, high and low-criticality tasks can share the same execution platform, improving considerably the usage of computation resources. Even if the execution platform is shared with low-criticality tasks, deadlines of high-criticality tasks must be respected. This is usually enforced thanks to operational modes of the system: if necessary, a high-criticality execution mode allocates more time to high-criticality tasks at the expense of low-criticality tasks' execution. Nonetheless, most MC scheduling policies in the literature have only considered independent task sets. For safety-critical real-time systems, this is a strong limitation: models used to describe reactive safety-critical software often consider dependencies among tasks or jobs.

In this paper, we define a meta-heuristic to schedule multiprocessor systems composed of multi-periodic Directed Acyclic Graphs of MC tasks. This meta-heuristic computes the scheduling of the system in the high-criticality mode first. The computation of the low-criticality scheduling respects a condition on highcriticality tasks' jobs, ensuring that high-criticality tasks never miss their deadlines. Two implementations of this meta-heuristic are presented. In high-criticality mode, high-criticality tasks are scheduled as late as possible. Then two global scheduling tables are produced, one per criticality mode. Experimental results demonstrate our method outperforms approaches of the literature in terms of acceptance rate for randomly generated systems.

I. INTRODUCTION

With the adoption of multi-core architectures in safetycritical real-time systems, more and more functionalities share a common execution platform. In practice, due to safety requirements, only functionalities with the same level of criticality should share resources. This constraint limits the deployment of functionalities on multi-core architectures, leading to a potential waste of computation power.

To solve this problem, the Mixed-Criticality (MC) model [START_REF] Vestal | Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance[END_REF] has proposed an approach to execute high and low-criticality tasks in a single platform. Thanks to operational modes, MC systems are capable of executing tasks with different criticalities in the same architecture. When the system is in a nominal mode: tasks are executed with an "optimistic" timing budget (e.g. a WCET estimated by the system designer). At the same time, MC systems are also capable of limiting lowcriticality tasks' execution in favor of high-criticality tasks to ensure safety of the system. When a Timing Failure Event (TFE) is detected, (i.e. a task did not complete its execution within its low-criticality timing budget) the system switches to a high-criticality mode and high criticality tasks are executed with a "pessimistic" timing budget (e.g. a WCET enforced by a certification authority).

Many contributions to schedule these type of systems with real-time constraints (i.e. respecting deadlines in all operational modes) have been proposed in the literature [START_REF] Burns | Mixed criticality systems-a review[END_REF]. However, most scheduling policies assume independent task sets: no synchronization (e.g. lock-based communication, precedence constraints) among tasks is considered by the schedulers. This assumption is very restrictive: methods used to develop reactive safety-critical systems often model such systems as data-flow graphs. Some examples of widely used tools that follow graph representations for their systems are SCADE from Esterel Technologies1 and Simulink from MathWorks 2 . In practice, tasks have data dependencies and can only start their execution when all their predecessors have completed their execution. Such precedence constraints are usually modelled with Directed Acyclic Graphs (DAGs) of tasks. Cyclic dependencies among multi-periodic tasks can be resolved thanks to deterministic periodic-delayed communications like the one presented in [START_REF] Cadoret | Deterministic implementation of periodic-delayed communications and experimentation in aadl[END_REF].

In this paper, we aim at addressing this problem: how to efficiently schedule multi-periodic DAGs of MC tasks on multicore architectures? Efficiency here refers to the capacity to find a feasible scheduler on a given number of cores.

Scheduling DAGs on multi-core architectures is a difficult problem [START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF] that becomes even more difficult when considering MC tasks. Precedence constraints, combined with the extension of timing budgets, induce a cascade effect propagating potential time drifts to dependent tasks. As a consequence, special care must be taken to ensure schedulability in both modes, but also in case of a mode switch : when a TFE occurs, enough processing time must be available for the remaining tasks to be executed in high-criticality mode.

To tackle this problem, we present in this paper a sufficient property to guarantee correct switches from low (LO)criticality mode to high (HI)-criticality mode in a multi-core MC system with multi-periodic DAGs. Building on this property, we propose MH-MCDAG, a meta-heuristic to produce MC-correct schedules (as formally defined in [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF]). We also provide an efficient implementation of MH-MCDAG, called G-ALAP-LLF. Based on Global-Least Laxity First (G-LLF), G-ALAP-LLF executes HI-criticality tasks as late as possible, giving more flexibility for the execution of LO-criticality tasks. Last but not least, we provide an evaluation framework to generate randomly configured multi-periodic MC-DAGs. Experimental results we provide show that our scheduling strategy has a promising acceptance rate when scheduling randomly generated systems. We also provide evidence that our method outperforms existing approaches of the literature [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF].

To the best of our knowledge, the problem we address in this paper has received very few contributions so far (i.e. [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF], [START_REF] Li | Mixedcriticality federated scheduling for parallel real-time tasks[END_REF] and [START_REF] Pathan | Improving the schedulability and quality of service for federated scheduling of parallel mixed-criticality tasks on multiprocessors[END_REF]). MH-MCDAG, the meta-heuristic we propose, paves the way for new contributions on this topic. In addition, our evaluation framework could be reused and extended to evaluate future contributions on this topic.

The remainder of this paper is organized as follows. Our task model is presented in Section II. In Section III, we define and prove a sufficient condition to guarantee correct mode switches in the MC scheduling of our task model. We also present MH-MCDAG, our meta-heuristic to schedule DAGs of MC tasks. In Section IV we present G-ALAP-LLF, an efficient implementation of MH-MCDAG, based on G-LLF. We also describe how to adapt it to define an implementation based on Global-Earliest Deadline First (G-EDF). Our experimental results are given in Section V. In Section VI we present related works, to finally conclude in Section VII.

II. DUAL-CRITICALITY MULTI-PERIODIC MC-DAG MODEL

We present in this section the notations of the system model we consider throughout our contribution. A motivating example representing an Unmanned Aerial Vehicle (UAV) for field exploration is also presented in this section.

A. Notations

We define a MC system (MCS) S = (G, Π), as a set G of Mixed-Criticality DAGs (MC-DAGs) and an architecture Π with m identical processors. We consider dual-criticality systems: the system has two execution modes HI and LO. We adopt the discard approach [START_REF] Baruah | Scheduling real-time mixedcriticality jobs[END_REF], i.e. if a TFE occurs, LOcriticality tasks are no longer executed and HI-criticality tasks have an extended timing budget.

A MC-DAG G j ∈ G, is defined as follows:

• T j ∈ N and D j ∈ N are respectively the period and deadline of the DAG G j . Without loss of generality, we consider implicit deadlines (i.e. D j = T j ) for the remainder of this paper. • V j is the set of vertices of G j . Each vertex τ i ∈ V j is a MC task, characterized by two WCET parameters C i (LO) and C i (HI). Each task is also characterized with a criticality level χ i ∈ {HI, LO}. LO-criticality tasks have a C i (HI) = 0, since we adopt the discard approach. In addition, note that a task τ i ∈ V j has the same period (T j ) and deadline (D j ) as its DAG G j . • E j ∈ (V j × V j ) is the set of edges between vertices. If (τ i , τ j ) ∈ E j , then task τ i must finish its execution before task τ j can begin. A vertex is ready to be executed as soon as all of its predecessors have been executed. We define succ(τ i ) (resp. pred(τ i )) the set of successors (resp. predecessors) of a task. The predecessors of a HIcriticality task cannot contain a LO-criticality task: for safety reasons, a HI-criticality task cannot depend on the execution of a LO-criticality task. If a mode switch occurs, the LOcriticality task might never be executed and the precedence constraints would never be satisfied.

Task jobs refer to the activations of a periodic tasks of a given DAG. j i,k denotes k-th job of a task τ i . A task job is said to be released at time instant r i,k = k × T j and has to complete its execution before d i,k = (k + 1) × D j : the release time (respectively deadline) of a task job is also the release time (resp. deadline) of a DAG job. We define the utilization rate for a MC-DAG (G j ) in the execution mode χ: U χ (G j ) = τi∈Gj C i (χ)/T j . For a system S with multiperiodic MC-DAGs, the utilization rate of S in mode χ is given by: U χ (S) = Gj ∈S U χ (G j ). To have a schedulable system, we know that the condition m ≥ U χ (S) must be satisfied in HI and LO-criticality modes.

B. Motivating Example: Unmanned Aerial Vehicle

In the remainder of this paper we describe our contribution using a motivating example of an UAV for field exploration. Its graphical representation is presented in Fig. 1.

The UAV is composed of two MC-DAGs: the first one takes care of the Flight Control System (FCS), noted G F CS , the representation is extracted from the services presented in [START_REF] Siebert | Mobile 3d mapping for surveying earthwork projects using an unmanned aerial vehicle (uav) system[END_REF]. The second MC-DAG represents a scientific workflow used for image processing [START_REF] Bharathi | Characterization of scientific workflows[END_REF], noted G M ontage . Vertices in gray represent HI-criticality tasks, while white vertices are LO-criticality tasks. Vertices are annotated with their timing budgets: a single value is given for LO-criticality tasks since they are not executed in the HI-criticality mode. Full edges represent data dependencies between tasks, while dashed edges represent where data is coming from/being sent to. The idea behind this motivating example is to demonstrate that the FCS could be executed next to an image processing workflow on a tri-core architecture, the lower bound of required processors ( U max{HI,LO} (S) = 3).

This motivating example is interesting for several reasons. First, embedded systems like UAVs have limited processing power due to energy consumption and weight constraints. Deploying a large number of distinct processors has an important impact in terms of energy required to power the architecture and lift the vehicle from the ground. Yet, nowadays, an UAV like the one illustrated in Fig. 1 would include two distinct processors: one for the FCS and another for the image processing. By incorporating a multi-core architecture we gain in energy consumption and weight. Second, the HI-criticality mode of the FCS ensures the safety of the UAV by keeping it on the air. At last, by having HI-criticality tasks in the image processing MC-DAG, we are capable of delivering a degraded version of its application.

III. MC-CORRECT SCHEDULING

An MC-correct scheduling for DAGs was defined in [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF]: executes beyond its C i (HI) then all the vertices that are designated as being of HI-criticality complete execution by their deadlines.

Definition 1. A MC-correct
Condition LO-Mode in Definition 1 ensures the schedulability in LO mode: as long as LO tasks execute within their C i (LO) (i.e. no TFE occurs), a MC-correct scheduling satisfies task deadlines and precedence constraints. Condition HI-Mode in Definition 1 states that when HI-criticality vertices need to execute until their C i (HI) (i.e. when a TFE occurs), a MC-correct scheduling satisfies deadlines and precedence constraints of HI tasks.

In this section, we present and prove a sufficient condition that guarantees Condition HI-Mode of MC-correct scheduling. Building on this result, we define a meta-heuristic for MC-correct scheduling of DAGs.

A. Safe mode transition, a sufficient property

For each task τ i executing in mode χ, we define the function ψ χ i as follows:

ψ χ i (t 1 , t 2 ) = t2 s=t1 δ χ i (s). (1)
where

δ χ i (s) = 1 if τ i is
ψ LO i (r i,k , t) < C i (LO) ⇒ ψ LO i (r i,k , t) ≥ ψ HI i (r i,k , t). (2)
Safe Trans. Prop. states that, while the k-th activation of HI task τ i has not been fully allocated in LO mode, the budget allocated to this job in LO mode must be greater than the one allocated to it in HI mode. Intuitively, this guarantees that whenever a TFE occurs, the final budget allocated to the job of τ i is at least equal to its WCET in HI mode.

Definition 3. A correct schedule in a given mode χ, is a schedule that respects the deadline and precedence constraints on all task jobs of the MCS considering their C i (χ).

We propose the following sufficient condition to ensure Condition HI-Mode of MC-correct scheduling : the scheduling of tasks is correct in HI mode and Safe Trans. Prop. is enforced in LO mode (Definition 3). This result is formalized in Theorem 1 and proved in the remainder of this subsection.

Theorem 1. To ensure Condition HI-Mode of MC-correct scheduling (Definition 1), it is sufficient to define a correct schedule in HI mode and from this, define a correct schedule in LO mode respecting Safe Trans. Prop.

Proof. Assume a TFE occurs at time t, and consider the job j i,k of any HI task τ i . At time t, j i,k has been executed for

ψ LO i (r i,k , t) (see Eq. 1). Case 1. If ψ LO i (r i,k , t) = C i (LO)
, j i,k has completed its execution at time t. τ i was completely executed in LO mode, and met its deadline. Indeed, the scheduling in LO mode is correct and ensures that all tasks meet their deadlines if they all execute within their C i (LO).

Case 2. If ψ LO i (r i,k , t) < C i (LO), as a TFE occurs, the scheduling strategy triggers the HI mode. Basically, it stops the LO-criticality scheduling to start the HI-criticality one at time instant t. The WCET of j i,k is also updated to C i (HI). At time instant t, job j i,k in LO mode has already been executed for ψ LO i (r i,k , t). At the time instant t, when the TFE occurs, the job j i,k has C i (HI) -ψ HI i (r i,k , t) of execution time available to complete its execution in HI mode. We want to know if the allocated budget is large enough to respect the deadline d i,k after the mode switch.

We define B i,k (t) as the budget allocated to job j i,k in LO mode in time interval [r i,k , t], plus the budget allocated to it in HI mode in time interval [t, d i,k ] (remember that t is the time the TFE occurred). More formally,

B i,k (t) = ψ LO i (r i,k , t) + ψ HI i (t, d i,k ) Since C i (HI) = ψ HI i (r i,k , t) + ψ HI i (t, d i,k
), we have:

B i,k (t) = ψ LO i (r i,k , t) + C i (HI) -ψ HI i (r i,k , t)
Enforcing Safe Trans. Prop. in LO mode, we know that

ψ LO i (r i,k , t) ≥ ψ HI i (r i,k , t). Therefore: B i,k (t) ≥ ψ HI i (r i,k , t) + C i (HI) -ψ HI i (r i,k , t) ≥ C i (HI).
ψ LO i (r i,k , t) < C i (LO).
We conclude that the budget allocated to job j i,k when a TFE occurs, is large enough to complete its execution within its HI-criticality WCET.

To better understand the proof, Fig. 2 illustrates the behavior of the scheduling strategy respecting Safe Trans. Prop. and being schedulable in LO and HI modes. The red rectangles represent the available computation time for a job j i,k when a TFE occurs. It is clear from the figure that this computation time is large enough for the job to complete its execution within its C i (HI).

B. Meta-heuristic for multi-periodic MC-DAG scheduling

In this subsection we define MH-MCDAG, a meta-heuristic to schedule multiprocessor systems executing multi-periodic MC-DAGs. The meta-heuristic computes two time-triggered (TT) scheduling tables [START_REF] Kopetz | The time-triggered model of computation[END_REF], S LO and S HI , one for each criticality mode. These tables are computed off-line to ease the calculus of Eq. 1 (i.e. ψ χ i (t 1 , t 2 )). In order to enforce Safe Trans. Prop., we have to schedule HI-criticality tasks in LO mode by taking into account how these tasks are scheduled in HI mode. The first step calclates the schedule of the system in HI mode by applying a suitable scheduling algorithm offline, G-EDF for instance [START_REF] Li | Outstanding paper award: Analysis of global edf for parallel tasks[END_REF]. If the schedule is correct in HI mode, we then compute the schedule in LO mode (the same scheduling algorithm can be used again) but we enforce Safe Trans. Prop. to guarantee Condition HI-Mode of MCcorrectness (Definition 1). If the resulting schedule is correct in LO mode, Condition LO-Mode of MC-correctness is also satisfied and therefore the schedule is MC-correct. Thanks to the TT scheduling tables, when a TFE occurs, the mode switch to the HI-criticality mode just consists in changing scheduling tables from S LO to S HI . Note that, for safety reasons, reactive and safety-critical systems like the UAV illustrated in Fig. 1 are often scheduled with TT tables. Definition 4. MH-MCDAG Meta-heuristic for multi-periodic MC-DAG scheduling 1) Compute the scheduling table in HI mode and check its correctness.

2) Compute the scheduling table in LO mode, enforcing

Safe Trans. Prop. Check correctness of the schedule in LO mode.

To the best of our knowledge, [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF], [START_REF] Li | Mixedcriticality federated scheduling for parallel real-time tasks[END_REF] and [START_REF] Pathan | Improving the schedulability and quality of service for federated scheduling of parallel mixed-criticality tasks on multiprocessors[END_REF] are the only works considering multi-periodic MC-DAGs. These approaches, called federated scheduling, create clusters (i.e. set of cores) in the multi-core architecture and allocate an exclusive cluster to each heavy DAG (i.e. a MC-DAG with a utilization greater than 1, Definition 2 of [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF]). A heuristic to schedule heavy DAGs on their clusters is then applied. The remaining DAGs, with an utilization rate inferior to 1, are allocated to the remaining cores scheduled as a set of independent tasks: all tasks of a DAG are executed sequentially and are considered to be part of a single bigger task. These bigger tasks are then scheduled using existing methods for independent MC tasks [START_REF] Burns | Mixed criticality systems-a review[END_REF].

As a matter of fact, the federated approach presented in [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF] fits in our meta-heuristic: it first schedules tasks in HI mode with a non-preemptive List Scheduling (LS), and checks its correctness. Then tasks are scheduled in LO mode with a Preemptive LS. The HI-criticality jobs in LO mode have the priority ordering they had in HI mode and all HI-criticality jobs have a higher priority than LO-criticality jobs. Thus, HIcriticality jobs always execute earlier in LO mode than in HI mode and Safe Trans. Prop. is implicitly verified.

In this section, we have proposed a meta-heuristic to schedule multi-periodic MC DAGs. This approach requires a scheduling algorithm for periodic tasks and task precedences as well as the enforcement of a specific condition to guarantee a safe switch from LO mode to HI mode. In the next section, we propose to instanciate this meta-heuristic with a specific scheduling algorithm in order to optimise the acceptance ratio.

IV. G-ALAP-LLF, AN ALAP INSTANCE OF MH-MCDAG

Like we mentioned in the previous section, the federated approach [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF] fits the definition of MH-MCDAG. However, while this approach has the benefit of being quite simple, it leads to poor resource usage: for example, if a system is composed of a heavy DAG with a utilization rate of 3.1 and a DAG with a utilization of 0.2, 5 cores will be needed (a cluster of 4 cores for the heavy DAG and 1 core for the other DAG), while we can expect to find a MC-correct schedule on 4 cores. For this reason, we aim at defining more efficient scheduling methods in terms of usage of multi-core architectures.

In this section, we present G-ALAP-LLF, an implementation of MH-MCDAG, which aims at optimizing the acceptance rate for MCS. This implementation is based on G-LLF, and we explain in this section how it can be adapted to an implementation of MH-MCDAGbased on G-EDF. As opposed to the federated techniques [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF], [START_REF] Li | Mixedcriticality federated scheduling for parallel real-time tasks[END_REF], [START_REF] Pathan | Improving the schedulability and quality of service for federated scheduling of parallel mixed-criticality tasks on multiprocessors[END_REF], we adopt a global scheduling approach.

A. Motivation and overview

To design an efficient scheduling strategy for multiprocessor MCS composed of multi-periodic MC-DAGs, we instantiate the meta-heuristic described in the previous section.

In order to have a good acceptance rate for the implementation of MH-MCDAG, we have to:

1) Adapt an efficient scheduling algorithm, in terms of acceptance rate, for periodic tasks with precedence constraints. The scheduling policy is used off-line to obtain the scheduling tables. The scheduling policy is applied to each of the criticality modes; 2) Enforce Safe Trans. Prop. without reducing the exploration space of the possible schedules in LO mode; for instance not limiting ourselves to schedules where HIcriticality jobs have priority over all LO-criticality jobs.

In our implementation, we consider a global scheduling algorithm for each operational mode. In general, to adapt a scheduling algorithm to fit in our meta-heuristic, the algorithm needs to be applied off-line in order to obtain scheduling tables. It also needs to be compatible with the enforcement of Safe Trans. Prop., i.e. we need to be capable of counting time slots allocated to tasks' jobs in each operational mode. G-LLF and G-EDF are global algorithms respecting these conditions.

To ease the computation of the LO scheduling table, we want to ease the enforcement of Safe Trans. Prop. To do so, ψ HI i (r i,k , t) should be kept minimal as long as ψ LO i (r i,k , t) < C i (LO). In other words, HI-criticality tasks in HI mode should be scheduled as late as possible (ALAP) and not as soon as possible (ASAP). This gives a good scheduling flexibility for HI-criticality tasks in LO mode and as a consequence, a good scheduling flexibility for LO-criticality tasks in LO mode.

To obtain such a behavior on HI-criticality tasks in HI mode (i.e. the HI-criticality task is ready to be executed but waits until the last possible instant to be allocated) we perform a common transformation in task graph theory [START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF] on our MCS. To schedule the HI mode task set with a ALAP strategy, we produce the dual task graph and schedule this new task set with an ASAP strategy. This transformation consists in substituting ALAP deadlines (resp. arrival times) as ASAP arrival times (resp. deadlines) and inverting the precedence constraints on all MC-DAGs.

In order to compute scheduling tables in each mode using G-LLF, we have to define a laxity formula in the context of tasks with precedence constraints. Let us first consider the common concept in task graph theory, the critical path. The critical path (CP χ i ) of a vertex τ i in mode χ is the longest path, considering the C i (χ) of vertices, to reach an exit vertex (i.e. a vertex with no successors). Let now define the laxity of task τ i , at time instant t, in the criticality mode χ as follows:

L χ i,k (t) = d i,k -t -(CP χ i + R χ i,k ) (3)
d i,k is the deadline of the job j i,k . R χ i,k is the remaining exe- cution time of the job j i,k , i.e. R χ i,k = C i (χ) -ψ χ i (r i,k , t -1)
. A similar approach is used to compute scheduling tables using G-EDF. We define the priority for each task job P i,k as follows, where d i is the relative deadline for the job j i,k :

P χ i,k = d i -CP χ i . (4)
For space limitation reasons, we only develop the G-LLF version in the remainder of the paper. Theoretically, this version is expected to dominate the G-EDF version in terms of acceptance rate [START_REF] Lee | Zero-laxity based real-time multiprocessor scheduling[END_REF]. Here, theoretically means that preemption and migration costs are ignored.

R list ← R list ∪ {τ i | pred(τ i ) = ∅} 7:
end for for all cores c ∈ Π do 14:

τ i ← head of R list not being allocated 15:

S HI [t][c] ← τ i Allocate task τ i 16:
R

HI i ← R HI i - 1 17:
end for 18:

R list ← R list ∪ {succ(τ i ) | ∀τ j ∈ pred(succ(τ i )), R HI j = 0} 19: R list ← R list \ {τ i ∈ R list | R HI i = 0} 20:
for all G j ∈ G do Reactivation of G j 21:

if t + 1 mod T j = 0 then 22:

∀τ i ∈ G j , R HI i ← C i (HI) 23: R list ← R list ∪ {τ i ∈ G j | pred(τ i ) =

B. Computation of the HI scheduling table

The first step to obtain a HI scheduling table consists in transforming the MCS S into its dual S , as illustrated on Fig. 3 for our UAV use-case. Only HI-criticality tasks are represented with their respective timing budget C i (HI). A scheduling table is computed on S using G-LLF. We then obtain the scheduling table of S by reversing the table obtained for S (i.e. we perform a horizontal flip). The algorithm used to compute the S HI table is presented by Alg. 1. This algorithm uses a ready list of jobs and orders its element based on their laxity computed as described in Formula 3.

The ready list is initialized (lines 3-7 in Alg. 1) with source vertices (i.e. vertices with no entry edges) of S : Altitude Ctrl, Data Acq and Concat in Fig. 3. We then proceed to allocate tasks at each time slot until we reach the hyper-period (H = 20 for S ). For each time slot t, we call the function SORTHI that considers the results of Eq. 3 to sort the list (l. 9). Once the tasks have been ordered, the function VER-IFYCONSTRAINTS is called. This function checks if obtaining a feasible schedule is still possible. Constraints that need to be respected are: (i) vertices do not have negative laxities, (ii) no more than m vertices have zero laxities, and (iii) the sum of remaining times for all jobs needs to be inferior to the number of available slots remaining in the table.

In order to obtain another implementation of MH-MCDAG, we just need to redefine SORTHI and VERIFYCONSTRAINTS. For a G-EDF based implementation, SORTHI uses Formula 4 and VERIFYCONSTRAINTS only checks that jobs' deadlines are respected since there are no laxities.

After performing the sorting in the list and checking that the scheduling tables are still obtainable, the heuristic grabs the m-first ready jobs of the list and allocates the tasks to the multi-core architecture (l. [START_REF] Lee | Zero-laxity based real-time multiprocessor scheduling[END_REF][START_REF] Kopetz | Event-triggered versus time-triggered real-time systems[END_REF][START_REF] Cordeiro | Random graph generation for scheduling simulations[END_REF][START_REF] Bini | Measuring the performance of schedulability tests[END_REF][START_REF] Davis | Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF]. Once the allocation for this timeslot has been performed, the ready list can be updated in two ways: (i) new jobs can become ready to execute because their precedence constraints are satisfied (l. 18) and (ii) jobs that finished their execution are removed from the list (l. [START_REF] Abrishami | Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds[END_REF].

We illustrate the algorithm on our motivating example. At time slot 0, for example, L

C. Computation of the LO scheduling table

The algorithm used to compute the S LO table is presented by Alg. 2. It is very similar to the algorithm used to schedule the dual system S . The main difference relies on the fact that for all timeslots t < H do 8:

SORTLO(R list , t)

9:
if VERIFYCONSTRAINTS(R list , t) = ⊥ then for all cores c ∈ Π do 13:

τ i ← head of R list not being allocated 14:

S LO [t][c] ← τ i Allocate task τ i 15: R LO i ← R LO i - 1 16:
end for 17:

R list ← R list ∪ {succ(τ i ) | ∀τ j ∈ pred(succ(τ i )), R LO j = 0} 18: R list ← R list \ {τ i ∈ R list | R LO i = 0} 19:
for all G j ∈ G do Reactivation of G j 20:

if t + 1 mod T j = 0 then 21:

∀τ i ∈ G j , R LO i ← C i (LO) 22: R list ← R list ∪ {τ i ∈ G j | pred(τ i ) = ∅} 23:
end if

24:

end for 25:

end for 26:

return S LO scheduling table 27: end function Safe Trans. Prop. must be ensured to follow the definition of our meta-heuristic (Definition 4).

To respect Safe Trans. Prop. during the computation of our scheduling table, we define SORTLO, the sorting function for jobs in the LO-criticality mode. It defines the following priority ordering: 1) HI-criticality tasks that would invalidate Safe Trans.

Prop. if they are not allocated at time slot t, are considered as tasks with zero laxity.

2) The rest of ready tasks are sorted according to their laxity (Formula 3). Once the sorting is obtained for the ready list, like for the HI-criticality mode, we call the VERIFYCONSTRAINTS function to check if a feasible schedule can be obtained, constraints are the same than in the HI-criticality mode. To obtain the G-EDF implementation we just need to redefine SORTLO to consider Formula 4 when HI-criticality tasks do not risk to invalidate Safe Trans. Prop. VERIFYCONSTRAINTS is also adapted to check if deadlines are respected.

We illustrate the computation of the S LO applied to system of Fig. 1. At time slot 0, we have the following laxities:

L LO GP S (0) = 2 -0 -2 = 0, L LO Receiver (0) = 2 -0 -2 = 0, L LO Cap1 (0) = 9 -0 -4 = 5 and L LO Cap2 (0) = 9 -0 -4 = 5.
Tasks of G F CS have the lowest laxity and they are allocated first. The third processor is shared by tasks Cap1 and Cap2 until time slot 2, when GP S and Receiver have completed their execution. The algorithm continues to allocate tasks in function of their laxities until slot 17. At this time slot, tasks Altitude Ctrl, T rans Grd, T rans F leet and T rans are in the ready list. However, Altitude Ctrl in the HI scheduling table is allocated at this time slot and this job has not started to be allocated. The application of SORTLO puts Altitude at the beginning of the list.

The final scheduling table is presented in Fig 5 . As we can see, our scheduling strategy respects the deadline of the system in both modes, and satisfies Safe Trans. Prop. during the computation of the LO scheduling table. The computed scheduling tables are therefore considered as MC-correct in a tri-core architecture (the minimal number of cores required to schedule the system).

Fig. 5: LO scheduling table D. Analysis of G-ALAP-LLF

In this subsection, we explain the expected advantages of G-ALAP-LLF over the federated approach [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF]. Fig. 6 illustrates the scheduling tables obtained by the federated approach [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF]. As we can see, this approach requires five cores to find a feasible schedule in the LO mode, whereas we found a MCcorrect one using three cores.

First, in G-ALAP-LLF, MC-DAGs are scheduled using a global algorithm in both LO and HI modes. To use a different algorithm, like G-EDF, the only necessary change is to modify the functions SORTHI, SORTLO and VERIFYCONSTRAINTS of Algorithm 1 and 2 in order to use Formula 3 (G-LLF) or 4 (G-EDF). The fact that our scheduling is global, is one of the two major reasons for obtaining a better resource utilization. Fig. 6: LO scheduling table produced by the federated approach [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF] Indeed, the G-ALAP-LLF method can schedule any task on any core whereas the federated approach clusterizes cores for heavy DAGs and execute light DAGs as sequential tasks. The second major source of optimization comes from the computation of the HI scheduling table. Scheduling HI-criticality tasks in HI mode ALAP preserves the possibility to allocate LO-criticality tasks on more timeslots. More formally the ψ HI i (r i;k , t) of G-ALAP-LLF has higher chances to increase at a later point t, as opposed to the ψ HI i (r i;k , t) of the federated approach, which schedules HI-criticality tasks ASAP.

Nonetheless, an advantage of the federated approach over ours, is that if tasks complete their execution before their C i (χ), their successors can start their execution sooner. This is possible thanks to the priority ordering that was computed. Our approach, on the other hand, executes the system in a TT fashion. As demonstrated in [START_REF] Kopetz | Event-triggered versus time-triggered real-time systems[END_REF], if the TT approach is much more predictable, it offers a less efficient resource utilization compared to the event-triggered approach. In addition, the federated approach will generate less preemptions and migrations than G-ALAP-LLF.

V. EXPERIMENTAL RESULTS

In this section we present our experimental results. The objective is to evaluate the performance of G-ALAP-LLF. We proceed to this evaluation by (i) generating random sets of MC-DAGs and (ii) measuring the ratio of systems for which our method finds a MC-correct schedule.

Following this method, we also compare G-ALAP-LLF to the federated scheduling [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF]. To our knowledge, it is the only contribution that considers a task model similar to ours, composed of (i) MC tasks, (ii) precedence constraints, and (iii) multiple deadlines for DAGs. The approaches of [START_REF] Li | Mixedcriticality federated scheduling for parallel real-time tasks[END_REF], [START_REF] Pathan | Improving the schedulability and quality of service for federated scheduling of parallel mixed-criticality tasks on multiprocessors[END_REF] have very restrictive MC-DAGs were all vertices belong to the same criticality level and thus, do not correspond to the type of applications we consider.

A. Experimental setup -MC-DAG Framework

For our experiments, we implemented the G-ALAP-LLF algorithm in an open-sourced framework 3 . In addition, since works in [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF] have only presented theoretical results, we also implemented the federated approach. Last but not least, we developed a MCS generator in order to produce many MCS with random properties. Thanks to these tools, we generated a set of MCSs and measured the ratio for which each scheduling method finds a MC-correct schedule.

The random generation needs to be unbiased and uniformly cover the possible timing configurations of MCS. To design this random generation, we first integrated existing methods to generate DAGs with unbiased topologies [START_REF] Cordeiro | Random graph generation for scheduling simulations[END_REF]. This is an important aspect, since certain DAG-shapes tend to be more schedulable than others. The distribution of execution time for tasks is not controlled by this DAG generation approach. Yet, the utilization of the system is the most important factor used to perform benchmarks on real-time scheduling techniques. To overcome this limitation, we have integrated existing methods achieving a uniform distribution of utilizations for tasks [START_REF] Bini | Measuring the performance of schedulability tests[END_REF], [START_REF] Davis | Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF].

Parameters for the generation of MCS are as follows: • U : Utilization of the system in both criticality modes. • |G|: Fixed number of MC-DAGs per system. • |V j |: Fixed number of vertices per MC-DAG, i.e. all MC-DAGs have the same number of vertices. • ρ: Ratio of HI criticality tasks. • f : Reduction factor for the utilization of HI tasks in LO mode.

• e: Probability to have an edge between two vertices.

Once these parameters are set, we first distribute uniformly the utilization of the system to each MC-DAG. We use the uniform distribution described in [START_REF] Bini | Measuring the performance of schedulability tests[END_REF] to assign a utilization for each MC-DAG. The period/deadline for each MC-DAG is then assigned randomly: this period is chosen from a predefined list of numbers in order to avoid prime numbers 4 (which are also avoided in the industrial context). With the assignment of the period and the utilization of the MC-DAG, we can distribute the utilization to tasks of the DAG. We use UUnifastdiscard [START_REF] Davis | Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF] in this case. As opposed to the utilization that can be given to DAGs, a vertex cannot have a utilization greater than 1 since it is a sequential task (parallel execution for a vertex is not possible). UUnifast-discard is therefore an apropriate method. The utilization available for LO-criticality tasks is given by the difference between the utilization of HI tasks in HI mode and the utilization of HI tasks in LO mode, the difference being controlled by parameter f .

Once the utilization of the system is distributed among MC-DAGs and the utilization of MC-DAGs is distributed among tasks, we start the generation of the topology for the MC-DAGs. We start by creating the HI-criticality vertices. These vertices are connected following the probability e given by the user and without creating cycles among vertices. After the HI-criticality tasks have been created, we create the LOcriticality tasks. Again vertices are connected following the probability e chosen by the user and without creating cycles. The higher the probability e, the more dense is the resulting graph: vertices have more precedence constraints to satisfy, making the scheduling of the system more difficult.

The benchmarks we perform to assess statistically G-ALAP-LLF compared to the federated approach [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF] follow these two steps: first, we generate a large number of random MCSs. Second, we measure the percentage of systems for which G- 4 Possible periods: {100, 120, 150, 180, 200, 220, 250, 300, 400, 500}.

ALAP-LLF and the federated approach find feasible schedules.

B. Acceptance rate

In the remainder of this section, we present and analyze our experimental results. The objective of these experiments is to evaluate the performance of our method in terms of acceptance rate, measured as the percentage of MCS for which our heuristic finds a MC-correct schedule.

Experimental parameters: We control the parameters of the MCS generator so as to measure their influence on the performance of our method. We expect the following parameters to make the scheduling problem more difficult: (i) the density of the graphs, (ii) the utilization of the system, (iii) the utilization per task of the system, (iv) the number of MC-DAGs. Our experiments aim at measuring the effect of these parameters on G-ALAP-LLF's performance.

Our experimental results are presented in Fig. 7. The xaxis of the plots is the normalized utilization of the system (U norm = U (S)/m), and the y-axis is the acceptance rate. For each point of the graphs, we tested 1000 randomly configured MCS. In our experiments, the ratio of HI tasks is set to ρ = 50% and reduction factor of HI tasks utilization in LO mode is set to f = 2. In addition, we generate MC-DAGs with three configurations in terms of number of tasks |V j | per MC-DAG: MC-DAGs are composed of 10, 20 and 50 tasks in each configuration. This setup allows us to see how the two scheduling approaches perform when a large number of tasks is considered (up to 200 when considering 4 MC-DAGs).

Influence of the number of vertices: Fig. 7a presents the results obtained with an edge probability e = 20%, two MC-DAGs (|G| = 2), and an architecture of four cores (m = 4). Note that a MC-DAG with e = 20% is already dense enough to represent industrial systems with their usual precedence constraints. This first experiment provides promising results: G-ALAP-LLF found MC-correct schedules for over 50% of systems with a utilization up to 70%. For the federated approach the utilization of the system needs to be below 55% to schedule over 50% of MCS. We also notice that, for G-ALAP-LLF, the acceptance rate increases with the number of tasks per MC-DAG (e.g. G-ALAP-50 is above G-ALAP-20). This is due to the fact that for a given system utilization and an increasing number of tasks, the uniform distribution tends to give less utilization to each task: tasks become smaller and therefore easier to schedule with G-ALAP-LLF. We can also notice that the performance of the federated approach is less sensitive to the number of tasks per DAG, which was expected since the federated approach first assigns DAGs to clusters of cores, and then schedules heavy DAGs on their clusters.

Influence of the number of MC-DAGs: To confirm these observations, we also increased the number of MC-DAGs. As a consequence, tasks become smaller but they are also scheduled with more heterogeneous periods. Fig. 7b provides the results obtained with four MC-DAGs (instead of two in the previous configuration). As we can see, the performances tend to improve for both methods, which tends to demonstrate that (i) the utilization per DAG has a strong influence on the Fig. 7: Comparison between our scheduling strategy and the federated approach [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF] performance of the federated approach, and (ii) the utilization per task has a strong influence on performance of the G-ALAP method. Conversely, the number of MC-DAGs and thus the heterogeneity of periods seems to have a lower influence.

Influence of the number of cores: Keeping this last configuration, we increase the utilization per task by increasing the number of cores: we consider an architecture of eight cores (m = 8). Experimental results are reported in Fig. 7c. As expected, the scheduling problem is more difficult (the utilization per DAG and per task increases with respect to the previous configuration) and the measured performance is degraded. However, we remark that the measured performance is lower than for the initial configuration (Fig. 7a) whereas the utilization per DAG and per task is similar. This is due to the link between two parameters of our experimental setup: when increasing the number of tasks, we increase the number of edges as well. However, the number of potential edges grows quadratically with the number of tasks.

Going from results reported in Fig. 7a to those reported in 7b, the number of tasks increases linearly but the number of edges grows quadratically. Yet, the performances improve because the utilization per DAG and per task becomes smaller. Going from results reported in Fig. 7a to those reported in Fig. 7c, the utilization per DAG and per task remains the same, but the number of edges grows fast. As a consequence, the performance is degraded.

As a conclusion of these first experiments, we can see that the following parameters have a strong influence on the performances of both methods: the utilization of the system and the density of the graphs. In addition, the utilization per tasks influences the performance of the G-ALAP-LLF method while the utilization per DAG influences the performance of the federated approach.

Influence of the probability to have an edge between two vertices: In Fig. 7d, Fig. 7e, and Fig. 7f, we report the results using the same configurations as before, except for the edge probability: in these configurations, e = 40%. These results confirm our previous conclusions: the density of the graph has a strong impact on the performance of the method, as well as the system utilization. Besides, the G-ALAP-LLF method continues to outperform the federated approach. However, with these configurations, we can make the following observations. First, the number of tasks per DAG has less influence on the performance of G-ALAP-LLF than in the previous experiments (e.g. G-ALAP-50 and G-ALAP-10 get closer). This reduction is however less visible in Fig. 7e where the number of tasks is important and the utilization per task is small. In other configurations, the utilization per task is too high to compensate the difficulty to schedule DAGs with such a density (e = 40%). Second, the gap of performances obtained with each method gets smaller (e.g. G-ALAP-10 and FED-10 get closer). This tends to show that the configurations considered push our method towards its limits: scheduling problems considered are very hard, which was expected since graphs generated with e = 40% are very dense. Still, with a high number of tasks and a low utilization per tasks, our results are very good: G-ALAP-50 on Fig. 7e exhibits an acceptance rate above 70% for a system utilization of 90%.

Other values were tested for the parameters of our experiments: number of MC-DAGs, cores, tasks, reduction factor and HI-tasks ratio. All these tests showed a general tendency: G-ALAP-LLF it is capable of scheduling more systems compared to FEDMCDAG [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF]. However, we acknowledge that this result remains valid only if we do not account for preemption and migration costs. Indeed, a well-known weakness of laxity based algorithms is that they increase the number of preemptions and migrations. Nevertheless, in these experiments, it would have been difficult to define the timing overhead of preemptions or migrations. In future works we plan to evaluate an implementation of our meta-heuristic, MH-MCDAG, with another scheduling criteria than tasks laxity.

In conclusion, G-ALAP-LLF shows very good performance in terms of acceptance rate, even when comparing the results obtained with G-ALAP-LLF to results obtained on MC scheduling for independent task sets. Indeed, when U norm = 0.8, G-EDF-VD applied on independent tasks has an acceptance rate of 80% [START_REF] Li | Outstanding paper award: Global mixed-criticality scheduling on multiprocessors[END_REF], while our approach reaches 70% on dependent tasks with e = 20% and |G| = 4. We expect to have a lesser schedulability rate but the difference is acceptable considering the utilization of the system and the fact that we have precedence constraints.

VI. RELATED WORKS

In this paper, we propose a multi-core scheduling heuristic for real-time systems using the mixed-criticality model. Our heuristic leverages a common limitation regarding MC scheduling [START_REF] Burns | Mixed criticality systems-a review[END_REF]: most contributions only consider independent task sets. In our case, we considered applications modeled thanks to DAGs in order to represent data dependencies: a common practice for real-time systems. In the following section we present some relevant related works from the different scientific communities mentioned.

The only contributions considering MC tasks and multiple DAGs are [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF], [START_REF] Li | Mixedcriticality federated scheduling for parallel real-time tasks[END_REF] and [START_REF] Pathan | Improving the schedulability and quality of service for federated scheduling of parallel mixed-criticality tasks on multiprocessors[END_REF] which compute federated schedulers. The closest task model to ours is the one presented in [START_REF] Baruah | The federated scheduling of systems of mixed-criticality sporadic dag tasks[END_REF] and as demonstrated in previous sections, our scheduling approach outperforms their method in terms of number of cores required to schedule a system and in schedulability when the number of cores is fixed. In [START_REF] Li | Mixedcriticality federated scheduling for parallel real-time tasks[END_REF], [START_REF] Pathan | Improving the schedulability and quality of service for federated scheduling of parallel mixed-criticality tasks on multiprocessors[END_REF], the task model is very restrictive: each DAG belongs to a criticality level, i.e. all tasks of the DAG have the same criticality HI or LO. The approach calculates virtual deadlines for HI-criticality DAGs in order to respect mode switches. Nonetheless, our experimental results showed that a global approach tends to schedule more systems in a given number of cores.

Real-time scheduling for multiple DAGs has seen recent interesting contributions in the cloud computing domain. Workflows of tasks often in the form of DAGs are distributed into heterogeneous computing clusters. While the execution platforms are different than simple multi-core architectures, some heuristics take into account deadlines for DAGs. In [START_REF] Abrishami | Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds[END_REF] the authors propose a deadline distribution and planning algorithm that aims to minimize the execution time of a workflow. In [START_REF] Wang | Maximize Throughput Scheduling and Cost-Fairness Optimization for Multiple DAGs with Deadline Constraint[END_REF], the authors calculate an urgency factor for each vertex of the DAG by taking into account the execution charge of its successors and the deadline of the DAG. An extension to the Heterogeneous Execution Time First heuristic is presented in [START_REF] Xie | Mixed real-time scheduling of multiple DAGs-based applications on heterogeneous multi-core processors[END_REF], in which priorities are assigned to tasks in order to satisfy as many deadlines as possible. While these works consider deadlines for multiple DAGs, the execution budgets for each vertex cannot change during the execution of the system and no mode switches need to be ensured.

The construction of TT scheduling tables for MC systems has been studied in [START_REF] Theis | Schedule table generation for timetriggered mixed criticality systems[END_REF]: scheduling tables are constructed by exploring the solution space. This exploration is guided by a leeway parameter allowing the detection of unfeasible schedules to perform backtracking when needed. Nonetheless the approach presented was only tested for mono-processors and our experimentations with Constrained programing considering data-dependencies between tasks and multi-core architecture were not capable of scaling for randomly generated systems. An online mechanism to incorporate MC aspects into TT tables is presented in [START_REF] Theis | Mixed criticality scheduling in time-triggered legacy systems[END_REF]. It relies on the fact that a scheduling table already exists for the LO-criticality mode and tries to use remaining time slots of the table to handle mode transitions and timing extensions for HI-criticality table. Since our approach computes two compatible scheduling tables, we do not rely on time slots that remained unused in the LOcriticality mode.

VII. CONCLUSION

In this paper, we have presented four contributions. First, we have defined a sufficient property to guarantee correct switches from LO mode to HI mode in a multi-core Mixed-Criticality scheduling for multi-periodic DAGs. Second, based on this property, we have defined and proved MH-MCDAG, a meta-heuristic produce MC-correct schedules for multiperiodic MC-DAGs. The computation of these schedules is performed off-line to ease the enforcement of the safe transition property. Third, we have defined and evaluated G-ALAP-LLF, an instantiation of MH-MCDAG, based on a global scheduling for multi-core execution platforms. Our experimental results have demonstrated that G-ALAP-LLF exhibits very good performances (in terms of acceptance rate) compared to the state-of-the-art. We also have explained how G-ALAP-LLF can be adapted to obtain an implementation of MH-MCDAG based on G-EDF. At last, we proposed an experimental platform to generate multi-periodic MC-DAGs with random configurations. This platform can be used to evaluate MC scheduling methods in terms of acceptance rate.

In the future we plan to extend MH-MCDAG to support an arbitrary number of criticality levels by applying our 2-levels approach by induction. We also plan to study the number of preemptions and migrations produced by G-ALAP-LLF and to use/evaluate other global algorithms entailing fewer preemptions and migrations. Indeed, solutions based on LLF scheduling are known to generate a lot of preemptions and migrations.

Fig. 1 :

 1 Fig. 1: UAV system S with two MC-DAGs: a Flight control system F CS and an image processing workload M ontage.

  schedule is one which guarantees 1) Condition LO-Mode: If no vertex of any MC-DAG in G executes beyond its C i (LO) then all the vertices complete execution by the deadlines; and 2) Condition HI-Mode: If no vertex of any MC-DAG in G

Fig. 2 :

 2 Fig.2: Illustration of case 2: ψ LO i (r i,k , t) < C i (LO). We conclude that the budget allocated to job j i,k when a TFE occurs, is large enough to complete its execution within its HI-criticality WCET.To better understand the proof, Fig.2illustrates the behavior of the scheduling strategy respecting Safe Trans. Prop. and being schedulable in LO and HI modes. The red rectangles represent the available computation time for a job j i,k when a TFE occurs. It is clear from the figure that this computation time is large enough for the job to complete its execution within its C i (HI).

P F CS = 10 P 3 Fig. 3 :

 1033 Fig. 3: Transformation of S to its dual S Algorithm 1 Computation of the HI scheduling table 1: function CALCSHI(S: MCS to schedule) 2:

  HI Altitude (0) = 3 -0 -3 = 0, L HI Data (0) = 3 -0 -3 = 0 and L HI Concat (0) = 13 -0 -4 = 9. They are the only three ready tasks until time slot 3, so Altitude Ctrl and Data Acq are fully allocated. At time slot 3, Altitude Ctrl and Data Acq have finished their executions, activating the F light Ctrl task. At time slot 4, the Concat task finishes its execution, activating Dif f 1 and Dif f 2. We have enough cores to execute all active tasks until time slot 7. At time slot 7, the Receiver and GP S tasks from the F CS become active, as well as the Cap1 and Cap2 tasks from the M ontage MC-DAG. We have the following laxities L HI Receiver (7) = 10 -7 -3 = 0, L HI GP S (7) = 10 -7 -3 = 0, L HI Cap1 (7) = 20 -7 -4 = 9 and L HI Cap2 (7) = 20 -7 -4 = 9. Receiver, GP S are going to run since they have the lower laxities. The tie is broken arbitrarily for Cap2 and Cap1, so Cap2 will execute first. MC-DAGs can have new activations during the computation of the tables: if the slot considered corresponds to the period of a MC-DAGs, its sources are added to the list once again and all R HI i are reset to C i (HI) (l. 20-25). At time slot 10, MC-DAG G F CS starts a new execution since it is executed twice during the hyper-period. The final HI scheduling table is presented in Fig 4a. Tasks belonging to G F CS are illustrated in blue, while tasks belonging to G M ontage are illustrated in orange. The last step (l. 27) performs the horizontal flip on the the scheduling table as illustrated in Fig 4b.

Fig. 4 :R

 4 Fig. 4: HI schedulingtable inversion Algorithm 2 Computation of the LO scheduling table 1: function CALCSLO(S: MCS to schedule) 2:

111

  e = 20%, |G| = 2 and m = 4e = 20%, |G| = 4 and m = 4e = 20%, |G| = 4 and m = 8. 0.3 0.4 0.5 0.6 0.7 0.8 0Utilization (U norm ) Acceptance rate (%) (d) e = 40%, |G| = 2 and m = 4. 0.3 0.4 0.5 0.6 0.7 0.8 0Utilization (U norm ) (e) e = 40%, |G| = 4 and m = 4. 0.3 0.4 0.5 0.6 0.7 0.8 0Utilization (U norm ) (f) e = 40%, |G| = 4 and m = 8.

  running at time s in mode χ, 0 otherwise . This function defines the execution time allocated to task τ i in mode χ from time t 1 to time t 2 .

	Definition 2. Safe Transition Property

  ∅}

	24:	end if
	25:	end for
	26:	end for
	27:	Reverse the scheduling table S HI
	28:	return S HI scheduling table
	29: end function

SCADE -http://www.esterel-technologies.com/products/scade-suite/

Simulink -https://www.mathworks.com/products/simulink.html

MC-DAG Framework -https://github.com/robertoxmed/MC-DAG

ACKNOWLEDGMENT

This research work has been funded by the academic and research chair Engineering of Complex Systems and the Smart, Safe and Secure Platform (S3P) project.


Discrete traits, inbreeding and family burials during the

Natufian: an overview.


Ulrich W Weber
email: uli.weber@eawag.ch

Peter G Cook

Matthias S Brennwald

Rolf Kipfer

Thomas C Stieglitz

A Novel Approach to Quantify Air-Water Gas Exchange in Shallow Surface Waters Using High-Resolution Time Series of Dissolved Atmospheric Gases

Keywords:

Gas exchange across the air-water interface is a key process determining the release of greenhouse gases from surface waters, and a fundamental component of gas dynamics 1 in aquatic systems. In order to experimentally quantify the gas transfer velocity in a wide range of aquatic settings, a novel method is presented based on recently developed techniques for the in situ, near-continuous measurement of dissolved (noble) gases with a eld-portable mass spectrometer.

Variations in observed dissolved gas concentrations are damped and lagged with respect to equilibrium concentrations, being the result of (a) temperature (and thus solubility) variations, (b) water depth and (c) the specic gas transfer velocity (k i ).

The method ts a model to the measured gas concentrations to derive the gas transfer velocity from the amplitude and the phase lag between observed and equilibrium concentrations. With the current experimental setup, the method is most sensitive to gas transfer velocities of 0.1 -8 m/h

Introduction

Gas exchange across the air-water interface is a key process coupling atmospheric and aquatic gas cycles. Accurate knowledge of gas exchange rates , expressed by the gas transfer velocity is required to determine mass balances of dissolved gases in aquatic systems, which can in turn be used to estimate uxes between groundwater reservoirs and surface water 1,2 :::

13 . Sur- face water bodies can be sources or sinks for gases: 4,5 whereas release of methane and carbon dioxide from water bodies is an important source of greenhouse gases to the atmosphere, the reverse ux of oxygen and nitrogen from atmosphere to water is an important factor in water quality and ecosystem functioning.

6

The gas transfer velocity for open ocean conditions is well parametrized in its dependence on wind speed.

7 Furthermore, numerous empirical relationships are available for rivers where 2 gas exchange is primarily a function of turbulent mixing due to water ow. [START_REF] Khadka | Synoptic estimates of diuse groundwater seepage to a spring-fed karst river at high spatial resolution using an automated radon measurement technique[END_REF] In contrast, for shallow open water surfaces like shallow lakes and, importantly, the coastal zone of oceans : , : a parametrization is currently not available that fully takes into account the physical processes driving gas exchange, which dier signicantly from those in the open ocean or rivers. In these systems, the inuence of other environmental parameters, e.g. rain, 9,10 current veloc- ity or bottom roughness, on near surface turbulence increases due to the decreased wind fetch and lower water depth, 11 which fundamentally impact ::: and ::::: this ::::::::::::::: fundamentally ::::::::: impacts air/water partitioning.

A commonly used method for estimating the transfer velocity at specic sites over short time scales consists of injecting trace gases (e. g. the 3 He/SF 6 dual tracer technique [START_REF] Ho | Inuence of current velocity and wind speed on air-water gas exchange in a mangrove estuary[END_REF][START_REF] Watson | Airsea gas exchange in rough and stormy seas measured by a dual-tracer technique[END_REF] ) and monitoring their rate of removal by air-water gas exchange [START_REF] Hall | Use of argon to measure gas exchange in turbulent mountain streams[END_REF] . These methods are subject to a number of experimental challenges and limitations, :::: and :::::::::::: monitoring :::::: trace :::::::::::: gases 1114 .

::::::::

Besides :::::: being :::::::::::::::: experimentally ::::::::::::::::::: demanding 11 and :::::::::::: sometimes :::::: being :::::::: subject ::: to :::::::::::::::: environmental ::::::::::

regulation :: (e.g. the identication of the exact geometry of the tracer patch 11 . Additionally, injection of gas tracers in surface water contaminates the site and future use of those gases as natural groundwater tracers may become :::::: SF 6 ), :::::: trace :::: gas ::::::::: injection ::::: may :::::::::::::: contaminate :::: the ::::

sites ::::: and :::::::: render ::::::: future ::::::::::::: experiments : impossible.

15 Further, the use of articial tracers (e.g. SF 6 ) is becoming increasingly regulated.

Recently, :: in ::::::: studies : primarily targeting the estimation of residence times of water within catchments, it was noted that diurnal variations in water temperature in rivers produced periodically varying concentrations of dissolved gases, which were damped and lagged to the respective atmospheric equilibrium concentration :: in :::::::::::: comparison ::::: with ::::::::::::: atmospheric :::::::::::: equilibrium :::::::::::::::

concentrations.

15

Variations of the gas concentrations are a function of the temperature variation, the temperature-dependence of gas solubility in water, and the gas transfer velocity. In principle, synchronous measurement of time series of temperature and concentrations of dissolved gases therefore allows the gas transfer velocity to be estimated. In the aforementioned study The objective of this study is to :::::::: combine ::::: the :::::::::: approach ::: to :::::::::: calculate :::: gas :::::::::: exchange :::::: rates :::::::

15 with :::::: those :::::: novel :::::::::::::: measurement :::::::::::: techniques. :::::::::: Further, ::: we ::::: aim :: to : establish the environmental conditions for which gas transfer velocities can be derived using the diurnal gas dynamics (DGD). Our data make a strong case that measurements of changes in gas concentrations over time can indeed be used to determine the gas transfer velocity, and to identify temporal variations in gas transfer velocity in response to changing environmental conditions. The introduced DGD method is applicable in rivers, in shallow lakes and lagoons, where well-mixed water conditions prevail, and avoids the injection of articial tracers.

:::

We ::::: rst ::::::::: calculate :::: the :::::::::::: sensitivity :::: and ::::::::::: resolution ::: of :::: the :::::::::: presented ::::::::: method :: in :: a :::::::::::: theoretical ::::::::

setting. : The performance and the experimental requirements of the suggested method are :::

are ::::: then : demonstrated in a controlled experiment and in the large, shallow La Palme lagoon at the Mediterranean Sea in southern France.

Theory

The gas ux of species i between air and water is caused by a disequilibrium of aquatic and atmospheric gas concentrations:

F i = k i • ∆C i = k i • (C w,i -C eq,i ), (1)
with F i being the gas ux, C w,i the concentration in the water, and C eq,i the concentration in air saturated water, :::: and : k i is the gas transfer velocity, which reects the rate of exchange. This basic relation : , ::::: even ::::::::: though :::: not :::::::::::: accounting ::: for :::::::::::::::::: bubble-mediated ::::: gas ::::::: uxes, : is used to determine uxes at regional-to-global scales.

7

If the water is well mixed, the ux can also be written as

F i = dC w,i dt • h, (2)
with h being the water depth of the exchanging water mass (`mixed layer'). Equating 1 and

2 yields dC w,i dt = k i h • (C w,i -C eq,i )
.

(3)

The equilibrium gas concentrations depend on the temperature (T w ) and the salinity (S) of the water and the partial pressure of the gasi, and is :::: each ::::: gas, ::::: and :::: are : determined by Henry's law,

20

C eq,i = p i H i (T w , S) .

(

) 4
The Henry's coecient (H i ) is specic to each gas species.

2123 p i is the partial pressure of species i in the atmosphere and is given by p i = (p atm -e s (T w ))v i , with p atm the local total atmospheric pressure, e s (T w ) the water vapor pressure, and v i the volume fraction of gas i in dry air.

20

Diurnal variation in C eq,i for the dierent gases is largely a function of the temperature dependence of their solubilities ::

20 . The magnitude of the diurnal variation in C eq,i for the noble gases will therefore be greatest for Xe and Kr, less for Ar and least for He and Ne.

The temperature dependence of the solubility of N 2 is similar to that of Ar.

To convert the transfer velocity derived from one gas species to another commonly the respective Schmidt numbers are used. The Schmidt number is dened as the ratio of kinematic viscosity of water, divided by the diusion coecient of the gas in water. The transfer velocities (k 1,2 ) of gas 1 and 2 are linked to each other via their Schmidt numbers (Sc 1,2 ) in

k 1 k 2 = Sc 1 Sc 2 -n , (5)
where n ::::::::::::: theoretically ranges from 1/2 < n < 2/3, theoretically ::

24 . However, it :

n : decreases rapidly to 1/2 for ::::

with : the onset of waves 24 (free surface condition). The ratio of (Sc 1 /Sc 2 )

is approximately constant with temperature.

25

While concentration gradients for reactive gases can also occur due to biogeochemical reactions, i.e. photosynthetic production in the case of O 2 and production by denitrication in the case of N 2 , the concentrations of the (atmospheric) noble gases are only controlled by physical processes, specically ::::::::::: radioactive :::::: decay ::::: and : air-water gas-exchange.

Method Modeling

An ordinary dierential equation solver is used to derive the results for the expected in-situ concentrations (C w,i ) by solving Eq. 3. The mean of the rst ten measured C w,i of a time series is used as the initial gas concentration.

The parameters for the equilibrium concentrations (C eq,i ) (cf. Eq. 4) and the water depth are given by the local environmental system, so that the transfer velocity (k i ) and C w,i remain as the only free parameters.

The model is t to the measured concentrations by varying k i . The t is optimized by minimizing the sum of squared errors (SSE) between the measured and modeled concentrations of the respective gas species.

The uncertainty of the best-t gas exchange rate k * i (95 % condence interval) was determined from the scatter of the observed concentrations relative to the best-t model curves.

26

The measured gas concentrations time series of the eld study were ltered with a Savitzky-

Experimental Method

The concentrations of dissolved N 2 , 40

Ar and 84 Kr in the water were analyzed with a portable `miniRUEDI' mass spectrometer 16 (Gasometrix GmbH) using the gas-equilibrium membrane-inlet mass spectrometry method (GE-MIMS).

20

During the experiments a submersible pump was used to continuously sample the water through a membrane contactor module (Liqui-Cel G542), in which the gases equilibrate between the water and a small gas headspace according to Henry's law. The partial pressures of N 2 , 40

Ar and 84

Kr in the headspace were quantied from the mass spectrometer readings by peak-height comparison relative to analyses of ambient air, which was used as calibration standard.

16 The analytical sequence was set to a continuously repeating cycle consisting of one air-standard analysis block, followed by three water sample analysis blocks, followed by one ambient air sample analysis block to assess the analytical performance ::

16 . Each of these analysis blocks were 8 min long.

The partial pressures observed in the headspaces of the membrane modules were converted to dissolved gas concentrations using the gas-specic Henry's law coecients at the temperature of the water in the membrane modules. The partial pressures obtained from the ambient-air samples were used to estimate the analytical uncertainties of the dissolved-gas concentrations as 1 % for N 2 , 2.5 % for Ar and 4 % for Kr.

In the controlled experiment and the eld study at La Palme lagoon, in-situ water temperature, salinity and atmospheric pressure were recorded by sensors every 10 min in order to calculate C eq,i using Eq. 4.

Controlled Experiment

A concept test of the DGD method to determine gas transfer velocities was conducted outside the Swiss Federal Institute of Aquatic Science and Technology (Eawag) in Dübendorf, Switzerland. For that purpose, a small tank (height = 15 cm, length = 60 cm, width = 40 cm) with a black shell was used. The small volume (0.036 m 3 ) and the black color of the tank caused a large temperature increase of the water in response to sun irradiation and a rapid decline in water temperature as air temperature dropped at night.

The water in the tub was circulated through the membrane module, where the gases equilibrate for measurement. The forced circulation caused an increase in turbulence in the water, producing a well mixed water body. This turbulence is assumed to be constant over time, as the pumping rate was kept constant. The development of (breaking) waves was heavily suppressed by the walls and the small surface area of the tank.

Field Study at La Palme Lagoon

The DGD method was further applied during a eld campaign in June 2017 at La Palme lagoon on the French coastline of the Mediterranean Sea. The shallow lagoon has a surface area of approximately 5 km 2 , a mean depth of 0.6 m and a maximum depth of 1.8 m. 1 The water level was not inuenced by tides, as there was no direct hydraulic connection of the lagoon to the sea.

The small depth of the lagoon ensures the water heats up quickly in response to solar irradiation and loses heat quickly at night, which leads to large diurnal temperature variations. The lagoon is regularly exposed to strong north-westerly winds, which cause waves of a maximum amplitude of about 0.4 m. 1 Inow of groundwater occurs in the northern section of the lagoon.

1 Recirculation of water between the lagoon and the pore space of shallow sed- iments is considerable 1,30 . This :::

and :::::: ows :::::: vary ::::: with ::: up ::: to :::: an :::::: order :: of :::::::::::::::: magnitude 1,30 . :::::: Such water exchange might inuence the concentrations of some of the gases. 31 He, for example, is known to be :::::::::::: Particularly, :::: He ::::::: being : enriched in the pore water of sediments by in-situ production or groundwater input :::::: might ::: be :::::::: subject ::: to ::::::::::: variations ::: in :::: the :::::::: mixing :: of :::: the ::::::: water :::::::

masses. Further, can O 2 be signicantly consumed by the sediments. However, Ar and Kr are not aected by sediment/water exchange.

32

The gas measurements were carried out near the center of the lagoon. Water was pumped 55 m from the sampling point at a water depth of 1 m to the onshore GE-MIMS system by a submersible pump through a hard plastic tube (polyamide tubing; 66 m in length).

Mechanical lters and regular cleaning of the membrane contactors kept the ow rates high to guarantee reliable gas measurements. The travel time of the water through the hoses was estimated to be approximately 5 min which is negligibly small in comparison to the diurnal variation.

Results and Discussion

Resolution and Sensitivity

The DGD method allows determination of gas exchange rates only within a certain range of k/h values. Here we discuss the upper and lower limits of the determination of the transfer velocity using the DGD approach, and elaborate on the constraining parameters.

We have run the model several times in a theoretical setting to determine the sensitivity and resolution of the method. For that purpose a synthetic sinusoidal variation in the precision ::: of ::::: the :::: gas ::::::::::::::::: measurements. ::::: We ::::::: dene ::::: two :::::::::::: quantities :::::::::: necessary :::: to ::: be :::::::::: resolved ::

by ::::: the :::::::::::::: measurement ::::::: setup. ::::::: (D i ) :: is ::::: the ::::::::::: maximum ::::::::::: dierence ::::::::: between :::: the :::::::::: expected ::::::: water :::::::::::::: concentration :::: and :::: the :::::::::::: equilibrium ::::::::::::::: concentration ::::::::::: normalized ::: to :::: the :::::: mean :::::::::::: equilibrium :::::::::::::: concentration ::

of :::: one ::::::::: period, ::::::::::::::::::::::::::

D i = max(|C w,i (t)-C eq,i (t)|)
C eq,i . ::::: We ::::::: dene ::::: (A i ) ::: as :::: the :::::::::::: amplitude ::: of :::: the :::::::::: expected ::::::::::::::

concentration :::::::::::: normalized :: to :::: the :::::: mean :::::::::::: equilibrium ::::::::::::::: concentration :: of :::: the ::::: time :::::: series :::::::::::::::::::::::::::

A i = max(C w,i (t))-min(C w,i (t) C eq,i
For very low k/h, C w,i approaches a constant value. The :::::

water : concentrations will be approximately equal to the equilibrium concentration at the daily mean water temperature.

In this case, the experimental setup is not sensitive to changes in k/h. The lower limit of resolution of k/h is shown in Fig. 1 for Ar and for the ve dierent values of diurnal water temperature variation. We dene this lower limit as the point at which the relative diurnal variation due to temperature (max(C w ) -min(C w ). ::

In ::::: this ::::: case, :::: the :::::::::::::: experimental ::::::: setup :: is :::

not :::::::::: sensitive ::: to ::::::::: changes ::: in :::: k/h ::: as :::: the :::::::::::: amplitude, ::::: A Ar :: (yellow, right y-axisin Fig. 1) :

), ::::: due ::

to ::::::::::::: temperature : becomes less than the analytical precision of the gas measurements (red line in Fig. 1; for Ar) . This :: of :::: the ::::: gas ::::::::::::::: measurements : . :::::: The : limit is higher for lower diurnal temperature dierences as the concentration gradients are smaller. For a water temperature amplitude of 10 • C the lower limit is approximately 0.07 d -1 for Ar, 0.05 d -1 for N 2 and 0.1 d -1 for Kr. The smaller the temperature amplitude of the daily forcing the higher the minimum of k/h that can be reliably determined.

For high k/h, the gas concentrations in surface water rapidly approaches C eq,i : , ::::: such ::::: that :::

the ::::::::::: dierence ::::::::: between ::::: C w,i ::::: and ::::: C eq,i ::::: gets :::::: small. Any further increase in k/h will not produce detectable changes :::::::: between :::: the :::::::::: expected :::: and :::: the :::::::::::: equilibrium ::::::::::::::: concentration, leaving the method insensitive for large k/h. Fig. 1 shows the relative dierence between equilibrium and in-situ concentrations for Ar as function of diurnal water temperature variation (∆C eq/InSitu ,

:::: D Ar :: (blue, left y-axis). The upper limit of the method is the point at which the dierence between the gas concentration in water ::::::::: expected ::::::::::::::: concentration and the equilibrium concentration becomes smaller than the analytical precision. :::: The ::::::: upper :::::: limit ::: of :::: the ::::::::: method ::: is, :::::::::: therefore, :::::::: reached :: if ::::: D Ar ::: is :::::::: smaller ::::: than :::: the ::::::::::: analytical :::::::::: precision. : For a diurnal temperature change of 10 • C, the upper limit of k/h that can be reliably measured is approximately 4 d -1

for Ar, 9 d -1 for N 2 and 2 d -1 for Kr. The smaller the temperature amplitude the lower the maximum of k/h that can be reliably determined.

The range of k/h values that can be reliably determined by Ar is therefore approximately 0.07 -4 d -1 for a diurnal temperature variation of 10 • C. For an assumed water The ability to resolve dierences in gas transfer velocity therefore depends on the magnitude of diurnal water temperature variation, on the water depth, on the temperature dependence of the solubility in water and on the measurement precision. The latter two factors are specic to each gas species.

In summary, the range of gas transfer velocities that can be determined by the DGD method falls well in the range of gas transfer velocities that are typically encountered in natural waters (average for lakes and reservoirs 1.0 m/d; global average 5.7 m/d). 33

Controlled Experiment

The results of the equilibrium, the observed and the modeled gas concentrations for N 2 , Ar and Kr in the controlled experiment are shown in Fig. A Ar ) :: (yellow, right y-axis) both normalized to the mean equilibrium concentration for Ar, shown for dierent water temperature amplitudes. High k/h results in a small dierence between the expected and equilibrium concentrations : , ::::::: hence, :::::: small ::::: D Ar .

Where this dierence :::: D Ar : is less than the experimental precision (that for Ar is indicated by the red horizontal line), C eq,i and C w,i cannot be reliably dierentiated, determining the upper limit on the k/h range. At low k/h the expected diurnal concentration amplitude : , ::::: A Ar , is less than the experimental precision. This, therefore, denes the lower limit for k/h determination. The range for ∆T = 10 • C (grey area and black circles) is approximately 0.07 -4 d -1 for Ar with a ::: an : experimental uncertainty of 2.5 %.

same as the expected value of 0.95 from Eq. 5 (Schmidt numbers for fresh water at T = 20 • C: Sc Ar = 552, Sc N 2 = 612, Sc Kr = 625 7 ). For Kr the derived solution of the transfer velocity matches with that scaled from Ar with the Schmidt number ratio (k SC,Kr = 0.27 m/d) within its 2σ condence interval. k SC,Kr also ts the data well given the scattering of the data (Fig. 2). Due to the lower experimental precision the error of the estimated gas transfer velocity is larger for Kr than for Ar and N 2 .

To illustrate the ability of the DGD method to reproduce C w,i , model results for N 2 and Ar are shown for 0.5 • k * i and 1.5 • k * i . This exercise makes the case that the uncertainty of the estimated transfer velocities for N 2 and Ar is signicantly better than ±50 %, and mostly falls in the range between 5 -20 %, depending also on the length of the measured time series.

The controlled experiment demonstrates the potential of the dierent gases to trace gas exchange processes. Due to their low solubility and high atmospheric abundance, N 2 and Ar are particularly powerful tracers for gas exchange. The analytical noise in Kr leads to a large uncertainty in deriving the respective transfer velocity. Ar has a signal-to-noise ratio that is only slightly higher than that of N 2 . These dierences between gases are fully explained by the abundance and the analytical performance of the applied GE-MIMS method to determine gas concentrations.

16

In summary, we interpret the controlled experiment as a proof of concept of the DGD method, especially for the lower gas transfer velocities commonly reported for inland waters and coastal zones.

Field Study at La Palme Lagoon The model reproduces the observed data for N 2 remarkably well. Ar concentrations are also reproduced correctly for a large period of the time series. However, in the morning of the second day we observed a decrease in Ar concentrations which we do not capture ::: are ::::: not :::::::::: captured : by our simple model. The low concentration may relate to a specic (but unidentied) event or process which aect the Ar but not the N 2 concentration. Such deviation between the measured and the modeled concentration shows how valuable time series of gas measurements over several days are, as they inform on additional processes that aect atmospheric gases in aquatic systems besides atmospheric exchange. However, we have no appropriate explanation for the observed deviation between the measured and predicted Ar concentration.

For N 2 two periods with dierent response dynamics of the in-situ concentrations to the diurnal heating can be observed (indicated with dierent colors in Fig. 3). For the rst period which lasts approximately for the rst two and a half days the observed N 2 concentrations are highly damped relative to the atmospheric equilibrium concentrations. For the second period the dampening of the measured to the equilibrium concentrations is much smaller.

:::::::: Further, ::::: the :::::: phase :::: lag :::::::::: decreases :::::: from :::: the ::::: rst ::: to :::: the :::::::: second :::::::: period. : Consequently, for the two periods very diering transfer velocities prevail. For the rst period: k * N 2 = 1.6±0.2 m/d.

For the second period: k * N 2 = 7.1±0.6 m/d. Leaving the described discrepancy on the second day out for Ar, globally, the same behavior can be found in the Ar time series.

The measurement position within the lagoon is rather sheltered against wind (fetch of approximately 50 m). Thus, during wind-calm conditions waves rapidly dissipate. During the rst period wind speeds were low (mean wind speed u 10 = 2.9 m/s; u 10 : measured wind speed scaled to ten meters above the water surface 34 ), while during the second period wind speeds more than three times higher were observed (u 10 = 10.2 m/s). This change :::: was : also found in the transfer velocity : , :::: and : demonstrates the ability of the method to resolve dierent weather conditions on time scales of hours to days.

Discussion

The controlled and the La Palme lagoon experiments demonstrate the capability of the DGD method to quantify temporally changing gas exchange rates at specic locations and on relative short time scales. The presented method allows the quantication of the transfer velocity over the wide range of approximately 0.1 -8 m/d ::::::::::::: 0.05 -9 m/d ::::: (for :::: N 2 ), which covers the typically observed range of gas transfer for surface waters. The quantiable range in k/h depends on the magnitude of the diurnal water temperature variation, the water depth, the temperature dependence of the gas solubility in water and on the measurement precision.

The selection of gases being used as tracers by our method depends on the environmental processes the respective gases are undergoing and on the experimental setup. The noble gases He, Ne, Ar, Kr, Xe and Rn are best suited due to their inert behavior, whereas the gases O 2 and N 2 are subject to biochemical reactions. However, the noble gases He and Rn, in contrast to Ar, Kr and Xe, are released from the sediments by radioactive decay and their concentrations, therefore, depend on e.g. groundwater inow and circulation of water between surface water and sediments.

From a technical perspective of the noble gases, currently only He, Ar and Kr can be analyzed quasi-continuously, whereas in-situ measurements of ::::::::::::: measurement ::::::::::: capability :::: for Ne and Xe using our GE-MIMS instrument remains to be developed. On-going improvements of the experimental performance of (GE)-MIMS systems might increase the number of gases that can be used to analyze air/water partitioning and, thus, greatly expand the determinable range (and the accuracy) of k/h values.

Our experiments show that N 2 and Ar are most sensitive to gas transfer velocities under eld conditions given the available technology. N 2 yields the widest k/h range as it has the best signal-to-noise ratio. However, N 2 is potentially non-conservative due to biogeochemical processes, such as denitrication.

The DGD method works best for large daily temperature changes in the water; a minimum ::::::::::

preferably :: a : water temperature variation of 10 • C should prevail :::::::: prevails : to get reliable re-sults for the :::: and :: to :::::: cover :: a ::::::::: relevant :::::: range ::: of : gas transfer velocities. The method is therefore most suitable for water depths of ::::: Such ::::: high ::::::::::: variations :::: are :::::: more :::::: likely :: to :::: be :::::: found ::: in :::::::: shallow :::::::

waters ::::: with ::::::: depths : less than a few meters. Deeper water is less likely to show strong diurnal temperature variations, and is also : , :::::::::::::: furthermore, ::::::: deeper ::::::: water :: is : unlikely to be vertically well mixed as assumed in our model. The DGD method can be used to quantify temporal variations in transfer velocities, which can then be linked to environmental drivers of air-water exchange, such as wind or river-ow-driven turbulence. For instance, measuring k i over a few days with varying wind speeds could be used to derive relationships between transfer velocity and wind speed in shallow environments. It may also be possible to determine the inuence of parameters (e.g. precipitation) on near surface turbulence that are less frequently incorporated into the estimation of the gas transfer velocity.

The mass spectrometer used in this study can cycle through multiple inlets on a time scales of minutes, which allows automated analysis at several locations simultaneously. This allows coverage of dierent geographic conditions at sites, that may be more complex than the open ocean. Hence, site-specic parametrizations can be derived on several orders of areal extents.

As the DGD method does not rely on the application of any articial tracer, there is no contamination of the environment. With additionally determined quantities e.g. tidal inuences, groundwater intrusion or deep water mixing a more complete description of a study site is possible.

Alternative approaches for measuring air-water gas exchange are more labor intensive and

  water temperature simulate the diurnal heating and cooling. This pre-set temperature cycle has a mean temperature value of 15 • C, a peak-to-peak amplitude of 2 • C, 6 • C, 10 • C, 16 • C or 20 • C and a 24 h period. C eq,i were calculated for a constant atmospheric pressure of 1013.15 hP a. The expected :::::: water : concentrations C w,i are modeled for a k/h-range of 0 -10 h -1 . C w,i and C eq,i are then compared to each other and evaluated in the light of the experimental precision of the gas measurements. :::::::::::0 -10 d -1 . :This synthetic data exercise allows ::::: allow : us to derive upper and lower bounds for the determination of the gas transfer velocities :: by :::::::::::: comparing ::: the :::::::::::: parameters ::: to :::: the :::::::::::::: experimental :::::::::

  depth :::::::: Results :::: for :::::: water :::::::: depths :: of 0.2 m the range of gas transfer velocity that can be reliably determined is approximately 0.015 -1.6 m/d ::: and ::::::: 0.6 m :::: are ::: of :::::::::::::::: 0.01 -0.8 m/d ::::: and :::::::::::::::: 0.04 -2.4 m/d, :::::::::::: respectively.

2 .Figure 1 :

 21 Figure 1: The maximal concentration dierence between expected concentration in water and equilibrium concentration ( ::::: D Ar ) :: (blue, left y-axis) and the expected diurnal amplitude of ::: the : water concentration ( ::::

Fig. 3

 3 Fig.3shows the results of the equilibrium, the observed and the modeled gas concentrations of the La Palme lagoon. The diurnal temperature variation was up to 10 • C, signicantly

Figure 2 :

 2 Figure 2: The equilibrium, the observed and the modeled concentrations for N 2 , Ar and Kr and the water temperature for the controlled experiment and the respective transfer velocities (k i ). The model ts the gas concentrations well. The derived gas exchange rates k * are: k * N 2 = 0.27 m/d, k * Ar = 0.29 m/d, k * Kr = 0.39 m/d. To illustrate the sensitivity of the DGD method, transfer velocities 50 % larger and smaller than k * i are shown for N 2 and Ar. For Kr the result expected of the transfer velocity scaled from Ar with the Schmidt numbers is additionally shown (k SC for Kr).

Figure 3 :

 3 Figure 3: The equilibrium, the observed and the modeled concentrations for N 2 and Ar and the water temperature series of the water in La Palme Lagoon. The derivation of the transfer velocity for N 2 with the DGD method is split into two periods. The rst 2.5 days (green) result in a transfer velocity of k * N 2 = 1.6 ± 0.2 m/d, while the second 2.5 days (orange) result in k * N 2 = 7.1 ± 0.6 m/d. Those phases are characterized by very dierent wind regimes with u 10 = 2.9 m/s for the rst and u 10 = 10.2 m/s for the second phase.

  ::::::::::::: Additionally, :::::: local ::::::::::: conditions :::: can :::::::::: inuence :::: the :::::::: diurnal ::::::::::::: temperature ::::::: cycles, ::::::::::: including :::::: solar ::::::::::: radiation, ::::::: water :::::::::: residence :::::: time ::::: and ::::: heat ::::::::::::: absorption.::::::These :::::::: impact :::: the ::::::::::::: applicability ::: of ::::: this ::::::::: method. ::: In ::::::: rivers, :::: for :::::::::: example, ::::::: where :::: the ::::::::: method :: is :::::::::: applicable ::: in ::::::::::::: principle 15 , :::: this :::::::::::::: temperature ::::::::::::: requirement :: is :::::::::: currently ::::: the :::::::: limiting ::::::: factor ::::: and ::::: could :::: be ::::: rare :: to :::::: nd. :::::::: Again, ::::::::::::::: improvements :: in :::: gas :::::::::::::::: measurements :::::::: expand :::: the :::::::::: locations ::::: that :::: can ::: be ::::::::: covered. :

Acknowledgements

We gratefully thank Aladin Andrisoa, Anne Brennwald, Marine David, Alexandra Lightfoot and Valenti Rodellas for conducting the eld measurements with us. :::::::::::::: Furthermore, ::: we ::::::: thank ::::: three ::::::::::::: anonymous :::::::::: reviewers ::: for :::::: their ::::::::::::: constructive :::::::::::: comments. : This research is a contribution to the ANR @RAction chair medLOC (ANR-14-ACHN-0007-01, T. Stieglitz) and Labex OT-Med (ANR-11-LABEX-0061, part of the Investissements d'Avenir program through the A/MIDEX project ANR-11-IDEX-0001-02), funded by the French National Research Agency (ANR). PC acknowledges support from IMéRA (Institute of Advanced Studies), Aix-Marseille Université (Labex RFIEA and ANR Investissements d'avenir).