Vincenzo Bonifaci
email: vincenzo.bonifaci@iasi.cnr.it

Björn

D ' Gianlorenzo
email: gianlorenzo.dangelo@gssi.infn.it

Angelo

Alberto Marchetti-Spaccamela
email: alberto@dis.uniroma1.it

Multiprocessor Real-Time Scheduling with Hierarchical Processor Affinities

Many multiprocessor real-time operating systems offer the possibility to restrict the migrations of any task to a specified subset of processors by setting affinity masks. A notion of "strong arbitrary processor affinity scheduling" (strong APA scheduling) has been proposed; this notion avoids schedulability losses due to overly simple implementations of processor affinities.

Due to potential overheads, strong APA has not been implemented so far in a real-time operating system. We show that, in the special but highly relevant case of hierarchical processor affinities (HPA), strong APA scheduling can be implemented with a vastly improved runtime complexity. In particular, we present a strong HPA scheduler with a runtime complexity of O(m) per task arrival and O(log n+m 2 ) per task departure, where m is the number of processors and n is the number of tasks, thus improving on the previous bounds of O(m 2 ) and O(mn). The improved runtime algorithms allowed us to implement support for strong hierarchical processor affinities in LITMUS RT . We benchmarked this implementation on a 24-core platform and observed nonnegligible, but still viable runtime overheads.

Additionally, in the case of a bilevel affinity hierarchy and when job priorities are based on deadlines, we argue that the performance of our strong HPA scheduler, HPA-EDF, can be related to system optimality in the following way: any collection of jobs that is schedulable (under any policy) on m unit-speed processors subject to hierarchical affinity constraints is correctly scheduled by HPA-EDF on m processors of speed 2.415.

I. INTRODUCTION

Most modern multiprocessor real-time operating systems offer the possibility to restrict task migration with affinity masks, which specify on a per-task basis on which processors a task may be scheduled. The usefulness of processor affinities in several contexts such as application performance, fault tolerance or security is well-documented [START_REF] Alfieri | Apparatus and method for improved CPU affinity in a multiprocessor system[END_REF][START_REF] Foong | An in-depth analysis of the impact of processor affinity on network performance[END_REF][START_REF] Foong | Architectural characterization of processor affinity in network processing[END_REF][START_REF] Jang | Miami: Multi-core aware processor affinity for TCP/IP over multiple network interfaces[END_REF][START_REF] Markatos | Using processor affinity in loop scheduling on shared-memory multiprocessors[END_REF][START_REF] Salehi | The effectiveness of affinity-based scheduling in multiprocessor network protocol processing (extended version)[END_REF].

More recently, the problem of scheduling real-time workloads with arbitrary processor affinities (APAs) has been considered [START_REF] Baruah | Multiprocessor feasibility analysis of recurrent task systems with specified processor affinities[END_REF][START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF][START_REF] Gujarati | Schedulability analysis of the Linux push and pull scheduler with arbitrary processor affinities[END_REF][START_REF] Gujarati | Multiprocessor real-time scheduling with arbitrary processor affinities: from practice to theory[END_REF]. To avoid schedulability losses due to overly simple implementations of such processor affinities, two notions of scheduling with arbitrary processor affinities, weak and strong APA scheduling, have been identified in prior work [START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF]. Commonly used schedulers, such as Linux's push-and-pull scheduler, implement only weak APA scheduling. However, it has been demonstrated that strong APA scheduling provides improved schedulability, and that it can be realized by leveraging the concept of task shifting, i.e., by allowing higher-priority This paper has passed an Artifact Evaluation process. For additional details, please refer to http://ecrts.org/artifactevaluation. tasks to be moved among processors in order to make room for lower-priority tasks that are limited by affinity constraints.

Previous work has shown that strong APA scheduling can be implemented with a runtime cost of O(m 2 ) per task arrival and O(mn) per task departure, where m is the number of processors and n is the number of tasks [START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF]. The second bound could be large when there many tasks. We remark that it might be difficult to improve these bounds in general, due to the combinatorial structure of the underlying matching problem.

However, we observe that in many practical scenarios affinity masks are not at all arbitrary; rather, they often follow a hierarchical structure, since affinity masks commonly mirror the underlying hardware topology. For example, some particular cache-sensitive, high-frequency tasks may be partitioned to a specific processor to ensure L1-cache affinity, whereas other tasks may be restricted to a subset of cores that share an L3 cache, while others yet may be assigned a global affinity mask to optimize their average-case response times.

We formalize this notion of hierarchical affinities by requiring that affinity masks follow a laminar set structure, that is, given any two affinity masks α and β, either α is a subset of β, or vice versa, or the two sets of processors are disjoint. This definition reflects the tree-like structure of the memory hierarchy.

Our results. We show that for such hierarchical processor affinities (HPAs), strong scheduling can be implemented with a vastly improved runtime complexity. In particular, we present a strong HPA scheduler with a runtime complexity of O(m) per task arrival and O(log n + m 2 ) per task departure, where m is the number of processors and n is the number of tasks, thus improving on the previous bounds of O(m 2 ) and O(mn), respectively, whenever n > m (Section III).

Additionally, in the case of a bilevel affinity hierarchy and when job priorities are based on deadlines, we argue that the performance of our strong HPA scheduler, HPA-EDF, can be related to system optimality in the following way: any collection of jobs that is schedulable (under any policy) on m unit-speed processors with the given affinity constraints, is correctly scheduled by HPA-EDF on m processors of speed 2.415 (Section IV).

Finally, we experimentally validate our approach by implementing a version of our strong HPA scheduler in LITMUS RT [START_REF] Litmus Rt | The Linux testbed for multiprocessor scheduling in real-time systems[END_REF][START_REF] Brandenburg | Scheduling and Locking in Multiprocessor Real-Time Operating Systems[END_REF][START_REF] Calandrino | LITMUS RT : A testbed for empirically comparing real-time multiprocessor schedulers[END_REF], a real-time extension of the Linux kernel (Section V). To the best of our knowledge, this is the first implementation of a strong HPA scheduler in a real OS; the experiments confirm that, although the overheads are non-negligible, the proposed scheduling approach is viable in practice.

Related work. Real-time scheduling algorithms are typically classified based on the degree of migrations allowed: unrestricted migrations, no migrations, or hybrid approaches with an intermediate degree of migration. Global scheduling algorithms allow unrestricted migration of tasks across (possibly) all processors, while partitioned scheduling algorithms do not allow migration at all [START_REF] Davis | A survey of hard real-time scheduling for multiprocessor systems[END_REF]. Proposed hybrid scheduling algorithms include clustered scheduling (see, for example, [START_REF] Baruah | Schedulability analysis of multiprocessor sporadic task systems[END_REF][START_REF] Calandrino | A hybrid real-time scheduling approach for large-scale multicore platforms[END_REF]), semipartitioned scheduling (see, for example, [START_REF] Anderson | An EDF-based scheduling algorithm for multiprocessor soft real-time systems[END_REF][START_REF] Bado | A semipartitioned approach for parallel real-time scheduling[END_REF][START_REF] Burns | Partitioned EDF scheduling for multiprocessors using a c=d task splitting scheme[END_REF][START_REF] Kato | Semi-partitioned scheduling of sporadic task systems on multiprocessors[END_REF]) and restricted-migration scheduling (see, for example, [START_REF] Anderson | An EDF-based scheduling algorithm for multiprocessor soft real-time systems[END_REF][START_REF] Dorin | Semipartitioned hard real-time scheduling with restricted migrations upon identical multiprocessor platforms[END_REF][START_REF] Nikolic | Priority assignment and application mapping for many-cores using a limited migrative model[END_REF]). It is well-known that partitioning incurs lower runtime overheads, but produces schedules that may be unnecessarily constrained; global scheduling, vice versa, entails higher runtime costs that should be properly taken into account.

A simple but important observation is that APA and HPA scheduling simultaneously generalize global, clustered, and partitioned scheduling, since they allow to confine each task's migrations to a specified set of processors. An APA/HPA taskset can thus be modeled as a global, clustered, or partitioned taskset with an appropriate processor affinity assignment [START_REF] Baruah | Multiprocessor feasibility analysis of recurrent task systems with specified processor affinities[END_REF][START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF][START_REF] Gujarati | Schedulability analysis of the Linux push and pull scheduler with arbitrary processor affinities[END_REF][START_REF] Gujarati | Multiprocessor real-time scheduling with arbitrary processor affinities: from practice to theory[END_REF].

Semi-partitioned scheduling relaxes partitioned scheduling by allowing a small number of jobs to migrate, thereby improving schedulability [START_REF] Anderson | An EDF-based scheduling algorithm for multiprocessor soft real-time systems[END_REF][START_REF] Bado | A semipartitioned approach for parallel real-time scheduling[END_REF][START_REF] Burns | Partitioned EDF scheduling for multiprocessors using a c=d task splitting scheme[END_REF][START_REF] Kato | Semi-partitioned scheduling of sporadic task systems on multiprocessors[END_REF]. Such tasks are called migratory, in contrast to fixed tasks that do not migrate. One difference with APA/HPA scheduling is that, in the latter models, if and when a task migrates is determined dynamically "on the fly", as under global scheduling, whereas semi-partitioned schedulers usually restrict tasks to migrate at pre-determined points in time (with regard to a job's release time) to pre-determined processors.

Clustered scheduling is another proposal that aims to alleviate limitations of partitioned and global algorithms: tasks are statically assigned to clusters of cores (like in partitioning), but are globally scheduled within each cluster [START_REF] Baruah | Schedulability analysis of multiprocessor sporadic task systems[END_REF][START_REF] Calandrino | A hybrid real-time scheduling approach for large-scale multicore platforms[END_REF]. Clusters are disjoint and typically defined to mirror the boundaries of shared caches at a specific level in the memory hierarchy (e.g., L2 or L3). The hierarchical processor affinity model considered in this work can be interpreted as a multilevel generalization of clustered scheduling, allowing nested cluster structures.

In restricted-migration scheduling, migrations are allowed only at job boundaries [START_REF] Anderson | An EDF-based scheduling algorithm for multiprocessor soft real-time systems[END_REF][START_REF] Dorin | Semipartitioned hard real-time scheduling with restricted migrations upon identical multiprocessor platforms[END_REF][START_REF] Nikolic | Priority assignment and application mapping for many-cores using a limited migrative model[END_REF]. This limits when a job may migrate, whereas APA and HPA scheduling (like global, clustered, and semi-partitioned scheduling) primarily specify where a job may migrate to. Note, however, that both global and semi-partitioned scheduling can be combined with restrictedmigration scheduling, and similar approaches could also be explored in the case of APA/HPA scheduling.

Finally, if one ignores the recurrent nature of tasks, HPA scheduling is similar to a non-real-time scheduling problem in which a set of non-recurrent jobs is to be scheduled on a set of restricted machines with nested affinity structure [START_REF] Muratore | Parallel machine scheduling with nested job assignment restrictions[END_REF]. The latter problem has recently been generalized to heterogeneous platforms [START_REF] Bonifaci | Hierarchical and semi-partitioned machine scheduling[END_REF], but to the best of our knowledge it has never been studied in the context of recurrent real-time task models.

II. SYSTEM MODEL AND NOTATION

We are given a set of n sporadic tasks τ = {T 1 , T 2 , . . . , T n } to be scheduled on a set of m processors π = {Π 1 , Π 2 , . . .,Π m }. Each task T i = (c i , d i , p i ) is characterized by a worst-case execution time c i , a relative deadline d i , and a minimum interarrival time or period p i . We assume that c i , d i , and p i are integers and that the tasks have constrained deadlines, that is, d i ≤ p i . The extension of the sporadic task model considered here (proposed in [START_REF] Baruah | Multiprocessor feasibility analysis of recurrent task systems with specified processor affinities[END_REF][START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF][START_REF] Gujarati | Schedulability analysis of the Linux push and pull scheduler with arbitrary processor affinities[END_REF]) associates with each task T i ∈ τ a processor affinity mask α(T i ) ⊆ π that is the set of processors on which the jobs of T i are allowed to be scheduled. We abbreviate α(T i ) as α i . We assume that the family of affinity masks is hierarchical (or laminar), that is, for each i, k = 1, . . . , n, either

α i ⊆ α k or α k ⊆ α i or α i ∩ α k = ∅.
The level of an affinity mask α is the number of distinct affinity masks β such that β ⊆ α. The height h of a task system is the maximum level among all the affinity masks of the task system. Note that h ≤ m since the affinity masks of a task system form a laminar family; moreover, by standard combinatorial arguments [START_REF] Schrijver | Combinatorial Optimization -Polyhedra and Efficiency[END_REF]Theorem 3.5], there are at most 2m distinct affinity masks.

Priority assignment policies used in real-time scheduling can be classified as task-level fixed priority (FP), job-level fixed priority (JLFP), or job-level dynamic priority (JLDP). Our model applies to both FP and JLFP scheduling. In the case of FP policies, we denote by φ i the priority of T i . In the case of JLFP policies, we denote by φ i (at any time) the priority of the unique pending job of T i (at that time); note that if T i has no pending job, we will never consider φ i .

Let τ (t) be the set of ready tasks at time t. We represent the scheduler state at time t by a bipartite graph G(t) = (τ (t) ∪ π, E(t)), where arc (T i , Π j ) belongs to E(t) iff Π j ∈ α i . Hence, finding a valid allocation of tasks in τ (t) to processors π is equivalent to finding a matching χ(t) in G(t).

However, not all matchings are equally desirable; in particular, one would like to maximize the number of non-idle processors while mantaining the specified priority ordering, without causing affinity violations. Note that in some cases, a processor may have to idle even though tasks are waiting. Two notions have been proposed to formalize how a correct scheduler should behave in this context by Cerqueira et al. [START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF].

Definition II.1 (Weak Invariant). At any time t, for each ready task T b not matched by χ(t) and for each Π j ∈ α b , there exists a task T i such that (T i , Π j ) ∈ χ(t) and φ i ≥ φ b .

As discussed in [START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF], the above requirement does not consider possible task shiftings that could improve schedulability without violating the affinity constraints. To take shiftings into account, a stronger definition is required based on alternating paths in the graph G(t). Given a task T b not matched to any processor by χ(t), an alternating path (T b = T 0 , Π j1 , T 1 , . . . , Π j k , T k ), k ≥ 0, from T b to task T k is a path in G(t) where (T q , Π jq ) ∈ χ(t) and (T q-1 , Π jq ) ∈ E(t), for each q = 1, . . . , k. A processor Π j is reachable from T b according to χ(t) if there exists an alternating path from T b to a task T such that Π j ∈ α . Let R b (t) denote the set of processors reachable from task T b in G(t) with respect to the matching χ(t).

Definition II.2 (Strong Invariant). At any time t, for each ready task T b not matched according to χ(t) and for each Π ∈ R b (t), there exists a task T i such that (T i , Π ) ∈ χ(t) and φ i ≥ φ b .

We will need Hall's Theorem [START_REF] Hall | On representatives of subsets[END_REF], a classical result on the existence of matchings in bipartite graphs.

III. SCHEDULING WITH HIERARCHICAL AFFINITIES

In this section we describe an algorithm for scheduling task sets with hierarchical affinities. First we give a conceptual description of the algorithm (Section III-A), then we prove that the assignment produced by the algorithm satisfies the strong APA invariant (Section III-B), and finally we show how to implement the algorithm in an efficient way (Section III-C).

A. Admission algorithm and feasibility

The algorithm is conceptually divided into two phases. In the first phase, we select a set τ of tasks in τ (t) that will be scheduled at time t. Tasks in τ are selected in such a way that there exists an assignment of tasks in τ to processors in π that respects the affinity masks and satisfies the strong APA invariant. In the second phase we find a feasible assignment of tasks in τ to processors in π according to their affinity masks.

The first phase of the algorithm selects the tasks in τ in a bottom-up order, i.e., from those with the smallest affinity masks to those with the largest one. At the beginning τ = τ (t). For each T i ∈ τ , let MARK[i] be a boolean variable that is false if and only if T i ∈ τ (t) and the affinity mask α i have not been analyzed by the algorithm. Let α i be a minimal affinity mask that has not been analyzed by the algorithm, that is MARK[i] = true and there is no task T k in τ (t) such that α k ⊂ α i and MARK[k] = false. The algorithm iteratively applies the following procedure until all affinity masks of tasks in τ (t) have been analyzed, that is until MARK

[k] = true for all T k ∈ τ (note that MARK[k] = true for each T k ∈ τ \ τ (t)):
1) Remove from τ all the tasks τ k that do not belong to the |α i | highest-priority tasks among those with affinity mask

α k ⊆ α i ; 2) Set MARK[k] to true, for each k such that α k = α i .
The pseudocode of the first phase is reported in Algorithm 1. For each i = 1, 2, . . . , n, let S i be the set of tasks with an affinity mask α k ⊆ α i that are in τ at the end of the algorithm, that is

S i = {T k ∈ τ : α k ⊆ α i }.
The next lemma shows that there exists an assignment of tasks in τ to processors in π that satisfies their affinity masks.

Lemma III.1. At the end of Algorithm 1 there exists a matching in G(t) of all the tasks in τ to processors in π. Proof. For any set S ⊆ τ of tasks, let Γ(S) be the set of neighbors of S in the bipartite graph G(t) defined previously. We claim that

τ ← τ (t); 2 MARK[i] ← false for each i = 1, . . . , n : T i ∈ τ (t); 3 MARK[i] ← true for each i = 1, . . . , n : T i ∈ τ (t); 4 while ∃i : ¬MARK[i] do 5 let i : ¬MARK[i] and ∀k(α k ⊂ α i ∨ MARK[k]); 6 S ← {T k ∈ τ : α k ⊆ α i };
|Γ(S i )| ≥ |S i | for every T i ∈ τ . (1)
S ⊆ τ , Γ(S) = ∪ Tj ∈S Γ({T j }) = ∪ Tj ∈S α j . In particular, Γ(S i ) ⊆ α i . On the other hand, when T i ∈ τ , α i ⊆ Γ(S i ) because T i ∈ S i . So, for T i ∈ τ , Γ(S i ) = α i .
We now claim that |Γ(S)| ≥ |S| for any S ⊆ τ . To prove this, we leverage the hierarchical structure of the affinity masks. Indeed, consider any S ⊆ τ . As we already argued, Γ(S) = ∪ Ti∈S α i . The latter set is the union of all the affinity masks of tasks in S. We can always rewrite such a union as α 1 ∪. . .∪α q , where all the αs are pairwise nonintersecting; for any T i , we call the α s containing α i the representative of T i . Thus,

Γ(S) = α 1 ∪ . . . ∪ α q = Γ(S 1 ) ∪ . . . ∪ Γ(S q ),
where again the sets on the right hand side are pairwise nonintersecting. We can now bound

|Γ(S)| = |Γ(S 1 )| + . . . + Γ(S q ) ≥ |S 1 | + . . . + S q ≥ S 1 ∪ . . . ∪ S q ≥ |S| ,
where the first inequality is due to (1), and the third inequality follows from the fact that the affinity mask of each task in S is covered by its representative, that is, S ⊆ S 1 ∪ . . . ∪ S q .

Theorem II.1, with X = τ , Y = π, guarantees the existence of a valid allocation of tasks in τ to the processors in π.

B. Assignment algorithm and strong APA invariant

Once the set of admitted tasks τ has been determined, Algorithm 2 constructs the assignment guaranteed to exist by Lemma III.1 in bottom-up order, that is, it assigns the tasks in S i to any unused processor in α i , assuming that, for each α k ⊂ α i , all the tasks in S k have already been assigned.

We denote by χ(t) the matching produced by Algorithm 2 in G(t). The set of matched tasks in χ(t) is τ . For each task T i ∈ τ (t)\τ we denote by R i (t) the set of reachable processors Algorithm 2: (Conceptual) Assignment algorithm.

1 ASSIGN[i] ← false for each i = 1, . . . , n : T i ∈ τ ; 2 ASSIGN[i] ← true for each i = 1, . . . , n : T i ∈ τ ; 3 while ∃i : ¬ASSIGN[i] do 4 let i : ¬ASSIGN[i] and ∀k(α k ⊂ α i ∨ ASSIGN[k]); 5 assign T i to any unused processor in α i ; 6 ASSIGN[i] ← true;
from T i according to χ(t). For each T i ∈ τ (t) \ τ , let α i be the inclusion-wise minimal affinity mask that satisfies the following properties:

1) α i ⊆ α i ; 2) processors in α i are matched with jobs T j such that α j ⊆ α i , that is, there are no edges (T j , Π k ) in χ(t) such that α j ⊆ α i and Π k ∈ α i . (In other words, α i is the smallest affinity mask containing α i such that all processors in α i are assigned tasks that have masks contained in α i .)

Lemma III.2. For each task T i ∈ τ (t) \ τ , R i (t) = α i .
Proof. We first show (i) that there are no alternating paths from T i to any Π j ∈ π\α i and then (ii) that there exists an alternating path from T i to any Π j ∈ α i . If there exists an alternating path from T i to some Π j ∈ π \ α i , then in such a path there exists a sequence (Π k , T , Π j ), for some Π k ∈ α i and T ∈ τ (t). By the definition of an alternating path, Π j ∈ α and hence α ⊆ α i , a contradiction to Condition 2 in the definition of α i . This proves statement (i). To prove statement (ii), let us assume that there exists a processor Π j ∈ α i that is not reachable from T i . For each task T k such that α k = α i , there exists an edge (T k , Π j ) in G(t). It follows that all such tasks (if any) are not reachable from T i , that is, for each processor Π ∈ α i and for each task T k such that α k = α i there is no edge (T k , Π ) in χ(t). This contradicts the assumption that α i was minimal, since the maximal set α i such that α i ⊂ α i and α i ⊆ α i would also satisfy the Conditions 1 and 2 in the definition α i , while being strictly contained in α i .

Theorem III.3. The matching produced by Algorithm 2 satisfies the Strong Invariant.

Proof. By Lemma III.2, it remains to be shown that, (i) for each task T i ∈ τ (t) \ τ and for each task T k matched to a processor in α i , φ k > φ i , and (ii) for each task

T i ∈ τ (t) \ τ no processor in α i is idle.
Let us consider a sequence of q iterations of Algorithm 1 and the corresponding affinity masks α i0 , α i1 , . . . , α iq-1 considered by these iterations, where:

• α ij denotes the affinity mask considered in iteration i j , for j = 0, 1, . . . , q -1; • i 0 is the the iteration where T i is removed from τ (i.e.

α i0 ⊇ α i ); • α ij-1 ⊂ α ij , for j = 1, 2, . . . , q -1;
• for each task T such that α = α ij-1 , S changes at iteration i j (i.e., there exists a task T r such that α r ⊆ α ij-1

that was not removed from τ in iteration i j-1 and that is removed in iteration i j ); and • α iq-1 = α i . To prove statement (i), we show by induction on iteration i j that, for each task T k such that α k ⊆ α ij that is not removed from τ at the end of iteration i j , it holds that φ k > φ i .

At iteration i 0 , i.e., when T i is removed from τ , the claim holds since, by the algorithm, T i is removed from τ as all the |α i0 | tasks in {T k : α k ⊆ α i0 } ∩ τ that are not removed have a higher priority than that of T i .

Assume that the inductive claim holds for iteration i j-1 . Since for each task T such that α = α ij-1 , S changes at iteration i j , there exists a task T r such that α r ⊆ α ij-1 that was not removed from τ at iteration i j-1 and that is removed at iteration i j . By induction, φ r > φ i and, moreover, since T r is removed at the end of iteration i j , for each task T k such that α k ⊆ α ij that is not removed from τ at the end of iteration i j , it holds that φ k > φ r . Therefore, φ k > φ i .

To prove statement (ii), we show by induction that for each α ij , no processor in α ij is idle. The basis of the induction is that when T i is removed from τ , there are |α i | tasks in τ that can only be scheduled on processors in α i ; this follows from the fact that Algorithm 1 does not remove the |α i | highest priority tasks, but removes at least one task (namely, T i ). Similarly, in subsequent steps, the algorithm does not remove the |α ij | highest priority tasks, but removes at least one task (namely, the task that caused S to change).

C. Runtime scheduling algorithm

Since the algorithm as described in the previous section has a substantial time complexity (proportional to mn or worse), in this section we discuss an efficient implementation of the same algorithm. The idea is to dynamically update the data structures that maintain the assignment of the tasks to the processors, instead of recomputing them from scratch at each task arrival or departure. To this end, we make use of strict Fibonacci heaps and doubly linked lists. A strict Fibonacci heap [START_REF] Brodal | Strict Fibonacci heaps[END_REF] for task arrival and task departure, respectively. For n > m, this improves over the APA algorithm from [START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF] that requires O(m 2 ) time for task arrival and O(mn) for task departure [START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF].

We assume without loss of generality that for any pair of consecutive time slots t and t + 1, the sets τ (t) and τ (t + 1) differ by one task T i , that is τ (t + 1) \ τ (t) = {T i } in the case of task arrival and τ (t) \ τ (t + 1) = {T i } in the case of task departure. We denote by τ (t) the set of tasks admitted to be scheduled by Algorithm 1 at time t, and by S k (t) the sets S k of tasks in τ (t) with affinity mask β ⊆ α k computed by Algorithm 1 at time t, for each k = 1, 2, . . . , n.

For our algorithms, we use the following data structures:

• for each affinity mask β, s[β] is a doubly linked list that contains tasks that are scheduled on processors in β, where, for each T i in s[β], α i ⊆ β; and • for each affinity mask β, b[β] is a strict Fibonacci heap that contains tasks that are backlogged, i.e., not scheduled, where, for each T i in b[β], α i = β. At time t, for each k = 1, 2, . . . , n, we assume that: all tasks in S k (t) are scheduled according to their affinity masks, s[α k ] contains all the tasks in S k (t) (i.e. s[α k ] = S k (t)), and b[α k ] contains all the tasks in τ (t) \ τ (t) with affinity mask α k .

1) Task Arrival: As in Section III-A, we divide the computation into two phases. In the first phase, we compute the set τ (t + 1) of tasks that are admitted to be scheduled at time t + 1. In the second phase we assign the tasks in τ (t + 1) to processors in π according to their affinity masks.

Let us assume that a new task T i arrives at time t + 1, that is, τ (t + 1) \ τ (t) = {T i }. In this case, the sets of tasks admitted to be scheduled by Algorithm 1 at time t and t + 1 differ by at most one task, that is either τ (t + 1) = τ (t) ∪ {T i }, or τ (t + 1) = (τ (t) \ {T r }) ∪ {T i }, for some task T r . To identify the potential task T r to be removed from τ , we look for an affinity mask β such that

α i ⊆ β, |s[β]| = |β|, (2)
β is minimal inclusion-wise.
If such an affinity mask exists, then τ (t + 1) = (τ (t) \ {T r }) ∪ {T i } and β is the affinity mask containing all the processors reachable from T i in the schedule at time t (i.e., it is equal to α i , see Section III-B). In fact, all the processors in β are used and for any affinity mask γ such that α i ⊆ γ and γ ⊂ β there exists a task T x , with γ ⊂ α x , that is scheduled in a processor in γ, while for all the tasks T y scheduled in processors of β, it holds that α y ⊆ β. If there exists an affinity mask β satisfying condition (2), then we check whether φ r < φ i , where T r is the task having lowest priority among those in s[β]. In the affirmative case, we remove T r from s[γ], for each γ such that α r ⊆ γ, insert T r in b[α r ], and insert T i in s[γ], for each γ such that α i ⊆ γ, otherwise we simply insert

T i into b[α i ]. If |s[β]| < |β|,
for all β such that α i ⊆ β, then there are enough processors in α i to schedule also T i , i.e. τ (t+1) = τ (t)∪{T i }. In this case, T i is added to s[γ], for each γ such that α i ⊆ γ.

Algorithm 3 presents the pseudocode of the runtime admission algorithm. First we initialize β to α i at line 2. Then, we look for an affinity mask β satisfying condition (2) at lines 3-5. We insert T i in s[γ], for each γ such that α i ⊆ γ at lines 6-7 (note that T i can be possibly removed from such heaps later). If |s[β]| = |β|+1 after the insertion of T i , then |s[β]| = |β| before the insertion (i.e., there was no idle processor in β). In this case we must remove a task T r . We look for T r with the operation FindMin() in s[β] at line 9. This operation returns the task with the minimum priority among those in s[β] (including T i ) and requires O(m) time. Finally, we remove T r from s[γ], for each γ such that α i ⊆ γ, and insert T r in b[α r ] at lines 10-12. We return τ (t + 1), which is equal to s[π] after the update process. To assign the tasks in τ (t+1) to suitable processors according to their affinity masks, we use, for each affinity mask β, a linked list L[β] that contains the unused processors in β. Each linked list supports the following operations:

• add(Π i ): add element Π i to the list; • first(): returns the value of the first element in the list;

• increase(): erases the first element of the list and shift the second element to become the first element; • concatenate(L 1 , L 2 , . . . , L l ): concatenates the lists L 1 , L 2 , . . . , L l and outputs the concatenated list. By using an implementation that maintains a pointer to the first and the last elements of the list, the first three operations require O(1) time, while the third operation requires O(l) time, where l is the number of lists to be concatenated.

We assume that each task is associated with its level and that each affinity mask α is associated with all the maximal affinity masks β such that β ⊂ α. This information can be computed offline as it does not depend on the currently present tasks. The algorithm assigns the tasks to processors level by level, starting from tasks with level-1 affinity masks. First of all we create the list L(α) for each α at level-1. W.l.o.g. we can assume that the union of the affinity masks at level-1 is equal to π and therefore that the level-1 lists jointly contain all the processors in π. Note that if there are processors that are not contained in any level-1 affinity mask, we can define dummy affinity masks containing such processors, with no associated task.

Let us consider the assignment of tasks that have an affinity mask at level l, assuming that all tasks with an affinity mask of a level lower than l have been assigned to suitable processors. In particular, for each level-l affinity mask α, we assume that there exists a list L[α] that contains the processors in α that have not yet been assigned to any task with affinity masks of a level lower than l. For each task T i k with a level-l affinity mask, we assign

T i k to L[α i k ].

first() and invoke L[α i k ].increase().

Eventually L[α i k ] contains all the processors in α i k that have not yet been assigned to any task with affinity masks of a level less than or equal to l. When all such tasks have been assigned, we create the lists L[α], for each level-(l + 1) affinity mask α, by concatenating all level-l lists L(β) such that β ⊂ α.

Algorithm 13 shows the pseudocode of the runtime assignment algorithm. At line 1, we create lists L(α) for each α at level 1. To assign the tasks to processors level by level, we sort the tasks in τ (t + 1) in order of increasing levels of their affinities (line 2). Let T i1 , T i2 , . . . , T i |τ | be the sorted tasks, for each k = 1, 2, . . . , |τ |, we assign T i k to L[α i k ].first() and remove from L[α i k ] the processor to which T i k is assigned (lines 5-6). After processing the last task T i k of a level , we concatenate the lists at level to create the lists at level , where is the level of task T i k+1 (lines 8-13). Specifically, line 8 checks whether T i k is not the last job in the list and is not the highest level h. In that case, if = (note that in this case can be greater than or equal to + 1), for each l = + 1, . . . , , the lists at level l -1 are concatenated to obtain lists at level l. Eventually we obtain the lists at level . Since the affinity masks are laminar, each affinity mask is concatenated at most once by the algorithm. Therefore, this operation requires time that is proportional to the number of distinct affinity masks in the task system. Algorithm 4: (Runtime) Assignment algorithm 1 Initialize L(α) for each level-1 affinity mask α; 2 Sort τ in increasing order according to tasks' levels; 3 Let T i1 , T i2 , . . . , T i τ be the sorted tasks;

4 foreach k = 1, 2, . . . , τ do 5 Assign T i k to L[α i k ].first(); 6 L[α i k ].increase(); 7 Let be the level of T i k ; 8 if k < |τ | ∧ < h then 9
Let be the level of T i k+1 ; Lines 8-13 concatenate the lists at level l to obtain the lists at level l + 1. Each list corresponds to a distinct affinity mask and hence this step requires an overall time that is proportional to the number of distinct affinity masks. Since the largest affinity mask is π and |π| = m, the number of distinct affinity masks in the system is at most 2m (see Theorem 3.5 in [START_REF] Schrijver | Combinatorial Optimization -Polyhedra and Efficiency[END_REF]); therefore, this step requires overall O(m) time.

2) Task completion: The algorithm for task completion first removes the completed task T i from s[γ], for each γ such that α i ⊆ γ. Then, for each distinct affinity mask β, it invokes the algorithm for handling task arrivals by using the highestpriority task T in b[β] as the new task. In the case that T is eventually scheduled, it is removed from b[α ]. The pseudocode of the algorithm is given in Algorithm 5. Note that line 12 of Algorithm 3 must be modified in order to check whether task T r is already present in b[α r ]; this can be done in O(1) time.

IV. BILEVEL AND CLUSTERED SCHEDULING

In this section, we consider a restricted scenario in which the hierarchy of affinity masks has only two levels. Namely, we assume that the task set τ is partitioned into M + 1 sets τ 0 , τ 1 , . . . , τ M and the set of processors is partitioned into M sets π 1 , π 2 , . . . , π M such that:

• τ = τ 0 ∪ τ 1 ∪ . . . ∪ τ M and τ i ∩ τ j = ∅, for each i = j, • π = π 1 ∪ π 2 ∪ . . . ∪ π M and π i ∩ π j = ∅, for each i = j, • for each T i ∈ τ 0 , α i = π, • for each i = 1, 2, . . . , M and T k ∈ τ i , α k = π i .
In other words, the affinity mask of each task T k is:

α k = π i if T k ∈ τ i , for some i > 0, π if T k ∈ τ 0 .
Table I illustrates the considered affinity masks, where an entry in row i and column k of the table is 1 if tasks in τ i can be scheduled on processors in π k , and 0 otherwise. This scenario models the following practically relevant cases:

TABLE I AFFINITY MASKS FOR BILEVEL OR CLUSTERED SCHEDULING π 1 π 2 • • • π M τ 0 1 1 • • • 1 τ 1 1 0 • • • 0 τ 2 0 1 • • • 0 . . . . . . . . . . . . . . . τ M 0 0 • • • 1
• bilevel scheduling, in which each task is either globally scheduled, or assigned to a specific processor, or • clustered scheduling, in which each task is either globally scheduled, or assigned to a cluster of processors. For each i = 1, 2, . . . , M , we denote |π i | as m i . Moreover, we define m max = max M i=1 {m i } and m 0 = m. We denote by J any possible collection of jobs generated by τ . For each job j = (R j , C j , D j ) in J, we let R j , C j , and D j denote the release time, the execution time requirement, and the absolute deadline of j, respectively. If T i is the task that generated job j, then C j = c i and D j = R j + d i . Given a time instant t, a job is available at time t if it has been released before or at t and has not signaled its completion. Since we are considering constrained deadline tasks, at any time t, there exists at most one available job for each task.

We will analyze the previously described algorithm in the special case where each job's priority is given by its absolute deadline; we therefore call it Hierarchical Processor Affinities -Earliest Deadline First (HPA-EDF).

A. Idealized schedule

Given a job collection J generated by τ that is feasible on m unit speed processors under affinity mask constraints α, the following idealized algorithm, A ∞ , is able to schedule J on a platform of infinitely many speed-(2 -1/m max ) processors π ∪ {Π m+1 , Π m+2 , . . .}, where the additional processors can only schedule tasks in τ 0 :

1) for each i = 1, 2, . . . , M , schedule the jobs of tasks in τ i on processors in π i by using (global) EDF; and 2) allocate one processor Π k , k > m, to each job of tasks in τ 0 and schedule all such jobs as early as possible. Let us denote by S ∞ the corresponding idealized schedule. To simplify the notation, we denote (2 -1/m max ) as s .

Lemma IV.1. At any point in time, at least as much total work has been processed in S ∞ as in any schedule which is feasible upon platform π with unit-speed processors and subject to the affinity mask constraints α.

Proof. By construction, at any point in time, S ∞ processed at least as much of each job generated by tasks in τ 0 as any feasible schedule. If we assume that, for some i ∈ {1, 2, . . . , M }, schedule S ∞ with speed s = 2 -1/m max ≥ 2 -1/m i provides less service to jobs of τ i than some feasible schedule, then we obtain a contradiction with the fact that any global work-conserving schedule on m i speed-(2 -1/m i ) processors processes at least as much work as any unit-speed schedule on m i processors [START_REF] Phillips | Optimal timecritical scheduling via resource augmentation[END_REF]Lemma 2.6].

B. Speedup bound for HPA-EDF

We analyze HPA-EDF on m processors of speed s, for a suitable s ≥ s to be determined later. By considering sufficiently small time slots, an equivalent description of the algorithm repeats the following procedure at each time slot:

1) consider the list of available jobs; 2) for each i = 1, 2, . . . , M , remove from the list all jobs of tasks in τ i but the m i with the earliest deadlines; 3) sort the remaining jobs in order of non-decreasing absolute deadlines; 4) consider the first m jobs in the obtained list, and a) for each i = 1, 2, . . . , M , schedule the job of a task in τ i (if any) onto an empty processor in π i ; b) schedule the remaining jobs (of τ 0 ) onto the empty processors.

Lemma IV.2. Consider a collection J of jobs generated by τ and let s ≥ s . Then at least one of the following holds: 1) All jobs in J are completed within their deadline under HPA-EDF on m processors of speed s, or 2) J is not feasible under the speed-s schedule S ∞ , or 3) there exists an interval I such that any feasible schedule for J must finish more than sm -2(m -1) ss s+s |I| units of work within I.

Proof. Suppose that the first two conditions do not hold, that is, J is feasible under the idealized schedule S ∞ with speed-s processors, but under HPA-EDF with speed s there is a job j = (R j , C j , D j ) that fails to meet its deadline. We aim to show that the third condition must then be satisfied. Let us assume that j has been generated by a task T in τ f , f ≥ 0. We assume w.l.o.g. that J is minimal, in the sense that there are no jobs with a deadline greater than D j .

Let us define t * as the latest time instant such that:

• t * ≤ R j , and

• at time t * , for any available job, HPA-EDF with speed s has processed at least as much of that job as A ∞ with speed s . Time t * exists because t * = 0 satisfies the above conditions. Let I = [t * , D j ]. We partition I into the following intervals:

• X k ⊆ [t * , R j ]: these are the intervals that occur before R j such that all the processors are busy under HPA-EDF scheduling; • Y k ⊆ [t * , R j ]: these are the intervals that occur before R j such that at least one processor is empty under HPA-EDF scheduling;

• Z k ⊆ [R j , D j ]: if f > 0,
these are the intervals that occur after R j such that, under HPA-EDF scheduling, at least one processor in π f is busy only with jobs from τ f for the entire interval and at least one processor in π is empty; otherwise, they are the intervals that occur after R j such that at least one processor is empty under HPA-EDF scheduling; and

• W k ⊆ [R j , D j ]: if f > 0,
these are the intervals that occur after R j such that all the processors are busy under HPA-EDF scheduling.

Note that, if f > 0, then the union of intervals Z k and W k is equal to [R j , D j ]. In fact, if at some time instant all processors in π f schedule a job in τ 0 , then all processors in π must be busy, otherwise a job in τ 0 scheduled in π f can be moved to an empty processor. Due to space constraints, the proofs of the following facts are given in an extended technical report [START_REF] Bonifaci | Multiprocessor real-time scheduling with hierarchical processor affinities[END_REF].

Fact IV.3. During each interval Y k , there are no available jobs in τ 0 that are not scheduled.

It follows that, if t * < R j , the first interval after t * is of type

X k . Hence the interval [t * , R j ] is composed of a sequence of intervals X 0 , Y 0 , X 1 , Y 1 , . . . Fact IV.4.
For each interval Y k , there exists a processor which is busy for the entire interval Y k under HPA-EDF scheduling.

We denote by X, Y , W , and Z the total length of intervals X k , Y k , W k , and Z k , respectively; we also group the sets X k and Y k into sequences X and Ȳ as follows.

1) Let Ȳ0 be the maximal sequence of consecutive intervals {Y 0 , Y 1 , . . . , Y x } such that the same processor is busy in Y k and in Y k+1 for k = 0, 1, . . . , x -1 and let X0 be the corresponding sequence {X 0 , X 1 , . . . , X x }. 2) We remove X0 and Ȳ0 from {X k } and {Y k }, respectively, and define X and Ȳ , > 0, by repeating the above procedure until {X k } and {Y k } become empty.

Let us denote by | X | and | Ȳ | the cumulative length of intervals in X and Ȳ , respectively.

Fact IV.5. s| Ȳ | ≤ s | X | + | Ȳ | .
By summing over all , we obtain sY ≤ s (X + Y ). Let a f ∈ {1, 2, . . . , m f } be the number of processors in π f that are busy in the entire sequence of intervals {Z k } only with jobs of τ f . Fact IV.6. If a f < m f , then sZ < s (W + Z).

Fact IV.7. If a f = m f , then sZ < s (|I| -Y ).
By the definitions of X and W , all processors are busy in such intervals, and hence HPA-EDF executes sm(X + W ) units of work. By Fact IV.4, for each interval Y k , there exists a processor which is busy for the entire interval Y k under HPA-EDF scheduling and then HPA-EDF executes at least sY units of work. Finally, for each interval Z k , there exists at least one processor in π f that is busy for the entire interval and then, HPA-EDF executes at least sZ units of work. Overall, in the interval I, HPA-EDF executes at least sm(X + W ) + s(Y + Z) units of work. The following cases may arise.

1) If a f < m f , then by Facts IV.5 and IV.6 it follows that: [START_REF] Litmus Rt | The Linux testbed for multiprocessor scheduling in real-time systems[END_REF], then we have two subcases. a) If X + W ≤ b|I|, Facts IV.5 and IV.7 imply that: , then sm -2(m -1) ss s+s |I| = m|I|. By Lemma IV.2, it follows that HPA-EDF correctly schedules J with speed s.

sm(X + W ) + s(Y + Z) = sm(|I| -Y -Z) + sY + sZ = sm|I| -sY (m -1) -sZ(m -1) > sm|I| -s (X + Y )(m -1) -s (W + Z)(m -1) = (sm -s (m -1)) |I|. 2) If a f = m f , let b ∈ [0,
sm(X + W ) + s(Y + Z) = sm|I| -(m -1)(sY + sZ) > sm|I| -s (m -1)(X + Y + |I| -Y ) ≥ sm|I| -s (m -1)(b + 1)|I|. b) If X + W > b|I|, then sm(X + W ) + s(Y + Z) = sm(X + W ) + s(|I| -X -W ) > sb(m -1)|I| + s|I|.
Since s ≤ 2, then s ≤ 3 2 -2 m + √ (4-3m) 2 +8m 2 2m < 3.562; if m max = 1, i.e. |π i | = 1 for each i > 0, then s = 1 and s = 1 -1 m + √ 2m 2 -2m+1 m ≤ 1 + √ 2 -1 m < 2.415. V.

IMPLEMENTATION AND EVALUATION

From the point of view of an RTOS developer, it is not obvious that the runtime algorithm presented in Section III-C lends itself to implementation in a real OS. To investigate the algorithm's viability in practice and to explore implementation choices, we implemented a prototype in LITMUS RT [START_REF] Litmus Rt | The Linux testbed for multiprocessor scheduling in real-time systems[END_REF][START_REF] Brandenburg | Scheduling and Locking in Multiprocessor Real-Time Operating Systems[END_REF][START_REF] Calandrino | LITMUS RT : A testbed for empirically comparing real-time multiprocessor schedulers[END_REF], a real-time extension of the Linux kernel, and conducted overhead measurements on a 24-core Intel Xeon platform.

A. Maintaining processor locality

One needed practical tweak pertains to Algorithm 13, which maps scheduled tasks to processors without any consideration for processor locality: in line 5 of Algorithm 13, each task is assigned simply to the first available processor, irrespective of where the task was scheduled previously. As a result, tasks may incur superfluous migrations. In practice, task migrations are costly, both due to the required OS and processor state updates (runqueue management, context switches, etc.) and due to the potential loss of cache affinity. Migrations should thus be avoided to the extent possible.

Fortunately, Algorithm 13 can be augmented to re-assign tasks to the last-used processor, provided this is possible without violating the strong APA invariant. Suppose we maintain for each processor a link to the list element used to enqueue it in the list L[•] (lines 1 and 13 in Algorithm 13), and for each task a link to the last-used processor. It is then possible to change line 5 of Algorithm 13 as follows: first check whether T i k 's last-used processor is still available (i.e., enqueued in L[α i k ]), and if so, remove the processor from the list and re-assign T i k to it. Assuming L[•] is realized as a doubly-linked list, this additional check and re-assignment can be carried out in O(1) time, thus preserving the overall complexity.

However, even with this modification, Algorithm 13 is still oblivious as to when a task used a processor last, which can be problematic if multiple tasks arrive that previously executed on the same processor (at different times). We hence instead implemented Algorithm 6, which favors later-scheduled tasks.

Algorithm 6 first initializes an array of task pointers to record each task's preferred processor (lines 6-10), resolving conflicts based on where and when a task was last scheduled (denoted as T i .last cpu and T i .last t, respectively). In the second step, each task is assigned to its preferred processor (lines 13-14), unless the processor was claimed by a more-recently scheduled task. If a task's locality cannot be maintained, the algorithm first attempts to assign it to an unclaimed processor (lines [START_REF] Cerqueira | Scaling global scheduling with message passing[END_REF][START_REF] Cormen | Introduction to Algorithms[END_REF], to avoid interfering with the preferences of other tasks. Finally, if this is not possible, any remaining unassigned processor in α i k may be used (lines [START_REF] Davis | A survey of hard real-time scheduling for multiprocessor systems[END_REF][START_REF] Dorin | Semipartitioned hard real-time scheduling with restricted migrations upon identical multiprocessor platforms[END_REF].

Algorithm 6 uses sets instead of lists to keep track of both unallocated and reserved processors. While this choice increases the algorithm's time complexity, it can be implemented more efficiently in practice because the number of processors is typically a small constant, which allows sets of processors to be represented as word-sized bitmaps that support (effectively) constant-time operations.

B. Implementation in LITMUS RT

We implemented a prototype fixed-priority scheduler based on Algorithms 3, 5, and 6 in LITMUS RT version 2015.1 [START_REF] Litmus Rt | The Linux testbed for multiprocessor scheduling in real-time systems[END_REF][START_REF] Brandenburg | Scheduling and Locking in Multiprocessor Real-Time Operating Systems[END_REF][START_REF] Calandrino | LITMUS RT : A testbed for empirically comparing real-time multiprocessor schedulers[END_REF], which in turn is based on Linux 4.1.

To allow the scheduler to scale to large multicore platforms, we adopted a design based on message passing [START_REF] Cerqueira | Scaling global scheduling with message passing[END_REF] in which the system is split into a single dedicated system management (or service) processor (DSP), which handles all interrupts and makes all scheduling decisions, and the remaining application processors (AP), which actually execute the real-time workload.

The DSP is notified of job arrivals by local interrupts and of job departures by APs via an efficient wait-free message queue.

Algorithm 6: Locality-aware assignment algorithm 1 Let available denote the set of all processors; 2 Let reserved denote an initially empty set of processors; 3 Let pref denote an array of task pointers of length m; 4 Sort τ in increasing order according to tasks' levels; 5 Let T i1 , T i2 , . . . , T i |τ | be the sorted tasks; In response, the DSP makes a scheduling decision (according to Algorithms 3, 5, and 6) and assigns each AP a job to execute.

6 foreach k = 1, 2, . . . , |τ | do 7 Let T x = pref [T i k .last cpu]; 8 if T x = NIL ∨ T x .last t < T i k .last t then 9 pref [T i k .last cpu] ← T i k ; 10 add T i k .last cpu to reserved ; 11 foreach k = 1, 2, . . . , |τ | do 12 Let valid = available ∩ α i k ; 13 if T i k .last cpu ∈ valid ∧ pref [T i k .last cpu] = T i k then 14 re-assign T i k to processor T i k .last
Each AP runs a simple, policy-free dispatcher that simply context-switches to the currently assigned job (if any) or executes non-real-time background work (if no job is assigned). Whenever the DSP changes an AP's assignment, it sends an inter-processor interrupt (IPI) to invoke the AP's dispatcher.

Cerqueira et al. [START_REF] Cerqueira | Scaling global scheduling with message passing[END_REF] pioneered this scheduler design for global schedulers and showed it to scale much better (in terms of worst-case overheads) than Linux's native push-and-pull scheduler (which enforces the weak APA invariant); we hence use Cerqueira et al.'s global scheduler as our baseline.

While we refer to Cerqueira et al. [START_REF] Cerqueira | Scaling global scheduling with message passing[END_REF] for an in-depth discussion of the approach's advantages and disadvantages, two aspects are of particular relevance: since only the DSP makes scheduling decisions, there is no need to explicitly synchronize access to scheduler data structures (i.e., the per-affinity lists of scheduled tasks and queues of backlogged jobs), and all scheduler data structures remain cache-local to the DSP.

Finally, instead of a strict Fibonacci heap as assumed in Algorithms 3 and 5, we used an array of linked lists (one per priority level) with an associated bitmap to indicate nonempty queues, which is the standard approach for implementing fixed-priority schedulers. Given that RTOSs typically implement only a limited number of distinct priority levels (e.g., 512 in LITMUS RT ), this enables (effectively) O(1) queue operations with much lower constant factors than strict Fibonacci heaps.

To the best of our knowledge, this is the first implementation of a strong APA scheduler in a real OS.

C. Experimental Evaluation

While some extra overhead can be expected-compared to the global baseline, an APA scheduler must consider additional constraints at runtime, which does not come for free-it is difficult to anticipate the magnitude of such additional costs, which could range from negligible to crippling. To investigate the system's overheads in a practical setting, we ran the baseline and the proposed schedulers on an Intel Xeon E7-8857 platform using two sockets with twelve cores each. Each core has private L1 and L2 caches (32 KiB and 256 KiB, respectively), and shares an L3 cache (30 MiB) local to its socket.

We generated 100 task sets with Emberson et al.'s task set generator [START_REF] Emberson | Techniques for the synthesis of multiprocessor tasksets[END_REF], each with a total utilization of either 75% or 85%, periods in the range [1ms, 1000ms] drawn from a log-uniform distribution, and a number of tasks ranging from 2m = 48 to 10m = 240 in steps of 2m. We considered three levels of affinities: global (i.e., all APs), socket-local (i.e., all APs sharing an L3 cache), or partitioned (i.e., just a single AP, which ensures L2 affinity). For each task, we selected uniformly at random a level (i.e., global, socket-local, or partitioned), and in the latter two cases then selected uniformly at random a socket or partition, respectively. Each task set was guaranteed to be feasible [START_REF] Baruah | Multiprocessor feasibility analysis of recurrent task systems with specified processor affinities[END_REF], and each c i parameter was ensured to exceed 500µs to filter impractically small parameters. Finally, we assigned all tasks rate-monotonic priorities.

Each task set was executed under both schedulers for 60 seconds each. Overheads were collected with the Feather-Trace instrumentation toolkit [START_REF] Brandenburg | Feather Trace: A light-weight event tracing toolkit[END_REF] included in LITMUS RT . In total, we recorded more than 34 GiB of trace data containing more than 700,000,000 valid overhead samples.

We focus here on the high-level scheduling overheads incurred on the DSP (i.e., Algorithms 3, 5, and 6) and the low-level dispatcher overheads incurred on the APs (i.e., dispatcher invocation and context-switching costs), as these two overhead sources exhibit the most telling differences, and omit a discussion of other system overheads due to space constraints. The relevant observed overhead data is summarized in Fig. 1. 99th perc. 95th perc. median average Because the memory hierarchy and the general design of commodity x86 platforms is decidedly not real-time friendly, the maximum overheads are affected by spurious outliers that exceed average and median overheads by a factor of 20x to 50x. Since such rare, but extreme outliers affect both the baseline and the HPA scheduler, they obscure a meaningful comparison.

Hence, we instead report 99.9 th percentile overheads, which are not obscured by outliers, and which we anyway consider to be more relevant for the "firm" real-time systems that can be expected to be deployed on commodity multicore platforms in the foreseeable future. For additional context, we also report 99 th percentile, 95 th percentile, median, and average overheads, which may be more relevant to soft real-time systems.

As expected, the results show the APA scheduler to incur higher overheads. In particular, the 99.9 th percentile DSP overhead increased from 5.79µs to 10.62µs, and this increase is reflected also in the median and average DSP overhead. However, while this is a substantial increase, it is important to note that these overheads are still within the range of a few microseconds, which is likely acceptable for tasks with a period in the range of a few to a few hundred milliseconds.

Interestingly, our data indicates that APs also experience increased dispatcher overheads, which may be surprising at first given that, under both schedulers, the AP dispatcher simply enacts the DSP's assignments. We attribute this increase in costs to a difference in how tasks migrate: whereas under global scheduling tasks migrate typically only after having been backlogged for some time, strong APA scheduling sometimes requires shifting migrations [START_REF] Gujarati | Schedulability analysis of the Linux push and pull scheduler with arbitrary processor affinities[END_REF], where a task that is scheduled on one processor must continue its execution immediately on another processor. Such migrations are more costly as they require careful coordination among the involved processors.

Overall, our prototype implementation shows the proposed scheduler to be practical: while overheads are indeed higher, they remain in a feasible range. Whether or not the capability to impose APAs is worth the extra costs is ultimately a design tradeoff that is best assessed in an application-specific context.

VI. CONCLUSION

We have studied hierarchical (i.e., laminar) affinity masks in the context of strong APA scheduling. For this important special case, which arises naturally in practice if affinity masks mirror a system's hardware topology, we have devised a new scheduler that is substantially more efficient (whenever n > m) than the best-known general-case strong APA scheduler [START_REF] Cerqueira | Linux's processor affinity API, refined: Shifting real-time tasks towards higher schedulability[END_REF]: our scheduler improves the per-arrival cost from O(m 2 ) to O(m), and the per-departure cost from O(mn) to O(log n + m 2 ).

In combination with EDF and assuming bilevel or clustered affinities, we have related our scheduler to an optimal system in the following way: any collection of jobs that is schedulable (under any policy) on m unit-speed processors subject to hierarchical affinity constraints is correctly scheduled by our scheduler on m processors of speed 2.415.

Finally, we have shown the proposed scheduler to be practically viable with a fixed-priority prototype implementation in an actual RTOS, namely LITMUS RT , and overhead measurements on a 24-core Intel Xeon platform.

Theorem II. 1 (

 1 Hall's Theorem). A bipartite graph G = (X ∪ Y, E) has a complete matching from X to Y if and only if |Γ(S)| ≥ |S| holds for every S ⊆ X, where Γ(S) = {y ∈ Y | (x, y) ∈ E for some x ∈ S}.

Algorithm 1 :

 1 (Conceptual) Admission algorithm.

1

 1

7 sort S by priority; 8 let 9 τ

 789 D be the |S| -|α i | lowest priority tasks in S; ← τ \ D; 10 MARK[k] ← true, ∀k : α k = α i ;

  is a heap that supports the Insert and FindMax operations in O(1) computational time, and the Delete operation in O(log N ) time, where N is the number of elements in the heap. A doubly linked list, with an auxiliary vector of pointers to each element, supports the Insert and Delete operations in O(1) time, and the FindMin operation in O(N ) time [17, Chapter 10.2]. The running time of our implementation is O(m) and O(log n+m 2 )

Theorem III. 4 . 5 β

 45 Algorithm 3 has time complexity O(m). Proof. The loops at lines 3-5 and 6-7 perform at most O(h) iterations. Since each Insert operation requires O(1) time, each iteration requires O(1) time. The loop at lines 10-11 performs at most O(h) iterations that require an overall O(h) time since each Delete operation requires O(1) time. The FindMin operation at line 9 requires O(m) time. Any other operation requires O(1) time. Algorithm 3: (Runtime) Admission procedure at task arrival 1 Let T i be the new task; 2 β ← α i ; 3 while |s[β]| < |β| ∧ β = π do 4 Let γ be the minimal affinity mask such that β ⊂ γ; ← γ; 6 foreach γ : α i ⊆ γ do 7 s[γ].Insert(T i ); 8 if |s[β]| = |β| + 1 then 9 T r ← s[β].FindMin(); 10 foreach γ : α r ⊆ γ do 11 s[γ].Delete(T r ); 12 b[α r ].Insert(T r ); 13 τ ← s[π];

10 if = then 11 foreach

 11 l = + 1, . . . , do 12 foreach level-l affinity mask α do 13 Concatenate lists L(β) such that β ⊂ α and the level of β is l -1, and assign the concatenation to L(α); Theorem III.5. Algorithm 13 has time complexity O(m). Proof. Line 1 requires O(m) time since it invokes m times the add operation. By using the counting-sort algorithm to sort the tasks in τ (t + 1), line 2 requires O(m) time [17, Chapter 8.1].

Algorithm 5 : 5 T 6

 556 (Runtime) Scheduling algorithm for task completion 1 Let T i be the completed task; 2 foreach γ : α i ⊆ γ do 3 s[γ].Delete(T i ); 4 foreach distinct affinity mask β do ← b[β].FindMax(); Run task arrival procedure by using T as new task; 7 Let T be the scheduled task, if any; 8 b[α ].Delete(T ); Theorem III.6. Algorithm 5 has time complexity O(log n+m 2 ). Proof. Lines 2-3 require O(h) = O(m) time. Lines 5 and 6 require O(1) and O(m) time, respectively. Since they are invoked O(m) times (as the number of distinct affinity masks is O(m)), they require an overall O(m 2 ) time. Line 8 requires O(log n) time.

  The first obtained lower bound decreases with b, while the second one increases with b. It follows that, for the value of b for which they are equal, we obtain the maximum lower bound for any value of b. The value of b for which the two lower bounds are equal is b = s-s s+s and the obtained lower bound is sm -2(m -1) ss s+s |I|. Since s ≥ s , the lower bound given in case 1 is always greater than that given in case 2. This proves the statement of the lemma. In fact, since HPA-EDF executes more than sm -2(m -1) ss s+s |I| units of work, by the definition of I, A ∞ with speed s executes at least the same amount of work during I. By Lemma IV.1, any feasible schedule of J cannot process more than A ∞ with speed s before I and hence it must execute more than sm -2(m -1) ss s+s |I| units of work within I.Theorem IV.8. Any collection of jobs J generated by τ that is feasible on m unit-speed processors under affinity mask constraints α is schedulable by HPA-EDF on m processors with speed s < 3.562, and speed s < 2.415 if m max = 1.Proof. Since J is feasible on m unit speed processors under affinity mask constraints α, then at any interval I a feasible schedule can execute at most m|I| units of work. If s = s +1 2m(s +1)) 2 +4s m 2 2m

Fig. 1 .

 1 Fig. 1. Measured DSP and AP dispatcher overheads (in microseconds) under the global baseline scheduler and the proposed HPA scheduler.

  cpu and remove T i k .last cpu from available; i k to any processor in valid \ reserved and remove the processor from available;

	15	else
	16	if valid \ reserved = ∅ then
	18	else
	19	assign T i k to any processor in valid and
		remove the processor from available;

17

assign T

ACKNOWLEDGMENTS

Work partially supported by project C26A15TXCF of Sapienza University of Rome. The authors also acknowledge Schloss Dagstuhl Seminar 16081 "Scheduling".