Periodic parallel task models, such as Directed Acyclic Graph (DAG), offer significant potential for modeling safety-critical real-time applications, but can introduce security vulnerabilities on multicore platforms. The deterministic schedules of periodic real-time tasks can be exploited through schedule-based side-channel attacks - causing missed deadlines or leaking sensitive information. Schedule randomization can address this vulnerability, yet existing work targets sequential tasks and lacks models that incorporate security for parallel workloads while meeting the real-time constraints. Furthermore, no widely accepted metric quantitatively measures the security gained from randomization against different attacker classes. This paper proposes Controlled DAG Randomization (CDR), a scheduler-oblivious framework that randomizes the schedule of periodic real-time DAG tasks while preserving hard deadline guarantees. Each DAG is transformed into an Augmented DAG (ADAG) via two mechanisms: dependency augmentation, which adds edges to constrain concurrency, and temporal augmentation, which inserts additional vertices/subtasks that introduce random delays. At runtime, two algorithms randomize the structure of each released instance of the DAG: one adds random precedence edges, and the other assigns randomized execution budgets to the augmented subtasks of the ADAG - both while maintaining schedulability. Two attacker-aware metrics, System Threat and Task Distribution Entropy, are proposed, targeting intrusive and observation-based attackers, respectively. Extensive simulations on single- and multi-task systems show significant vulnerability reductions. We also observe that increased resources do not always strengthen security and can diminish randomization effectiveness, highlighting the need for carefully designed schedules to realize real security benefits.

Heterogeneous multiprocessors can offer high performance at low energy expenditures. However, to be able to use them in hard real-time systems, timing guarantees need to be provided, and the main challenge is to determine the worst-case schedule length (also known as makespan) of an application. Previous works that estimate the makespan focus mainly on the independent-task application model or the related multiprocessor model that limits the applicability of the makespan. On the other hand, the directed acyclic graph (DAG) application model and the unrelated multiprocessor model are general and can cover most of today's platforms and applications. In this work, we propose a simple work-conserving scheduling method of the tasks in a DAG and two new approaches to finding the makespan. A set of representative OpenMP task-based parallel applications from the BOTS benchmark suite and synthetic DAGs are used to evaluate the proposed method. Based on the empirical results, the proposed approach calculates the makespan close to the exhaustive method and with low pessimism compared to a lower bound of the actual makespan calculation.

This paper presents a federated scheduling algorithm for implicit-deadline sporadic DAGs that execute on an unrelated heterogeneous multiprocessor platform. We consider a global work-conserving scheduler to execute a single DAG exclusively on a subset of the unrelated processors. Formal schedulability analysis to find the makespan of a DAG on its dedicated subset of the processors is proposed. The problem of determining each subset of dedicated unrelated processors for each DAG such that the DAG meets its deadline (i.e., designing the federated scheduling algorithm) is tackled by proposing a novel processors-to-task assignment heuristic using a new concept called processor value . Empirical evaluation is presented to show the effectiveness of our approach.

This paper presents federated scheduling algorithm, called MCFQ, for a set of parallel mixed-criticality tasks on multiprocessors. The main feature of MCFQ algorithm is that different alternatives to assign each high-utilization, high-critical task to the processors are computed. Given the different alternatives, we carefully select one alternative for each such task so that all the other tasks can be successfully assigned on the remaining processors. Such flexibility in choosing the right alternative has two benefits. First, it has higher likelihood to satisfy the total resource requirement of all the tasks while ensuring schedulability. Second, computational slack becomes available by intelligently selecting the alternative such that the total resource requirement of all the tasks is minimized. Such slack then can be used to improve the QoS of the system (i.e., never discard some low-critical tasks). Our experimental results using randomly-generated parallel mixed-critical tasksets show that MCFQ can schedule much higher number of tasksets and can improve the QoS of the system significantly in comparison to the state of the art.

This paper considers Dual Priority (DP) scheduling of constrained deadline sporadic tasks on uniprocessor. The initial fixed priority of each job of a task is promoted to a higher priority (called, promoted priority) after a fixed time interval (called, promotion point) relative to the release time of that job. DP scheduling alters the default preemptive behavior of traditional fixed priority (FP) scheduling to efficiently utilize the processor as close as possible to that of the optimal earliest deadline first (EDF) scheduler. In this paper, we address some of the main challenges of DP scheduling including derivation of a sufficient schedulability test, determination of promotion point of each task1. To the best of our knowledge, this test is the first schedulability test for DP scheduling applicable to constrained deadline sporadic tasks. The test is applicable for any given promotion points of the tasks and has pseudo-polynomial time complexity. We also propose two different heuristics to assign the promotion points, and experimental results show that the proposed test achieves performance very close to that of EDF scheduling.

We consider the scheduling of a real-time application that is modeled as a collection of parallel and recurrent tasks on a multicore platform. Each task is a directed-acyclic graph (DAG) having a set of subtasks (i.e., nodes) with precedence constraints (i.e., directed edges) and must complete the execution of all its subtasks by some specified deadline. Each task generates potentially infinite number of instances where the releases of consecutive instances are separated by some minimum inter-arrival time. Each DAG task and each subtask of that DAG task is assigned a fixed priority. A two-level preemptive global fixed-priority scheduling (GFP) policy is proposed: a task-level scheduler first determines the highest-priority ready task and a subtask-level schedulerthen selects its highest-priority subtask for execution. To our knowledge, no earlier work considers a two-level GFP scheduler to schedule recurrent DAG tasks on a multicore platform. We derive a schedulability test for our proposed two-level GFP scheduler. If this test is satisfied, then it is guaranteed that all the tasks will meet their deadlines under GFP. We show that our proposed test is not only theoretically better but also empirically performs much better than the state-of-the-art test in scheduling randomly generated parallel DAG task sets.

The traditional Vestal's model of Mixed-Criticality (MC) systems was recently extended to Imprecise Mixed-Critical task model (IMC) to guarantee some minimum level of (degraded) service to the low-critical tasks even after the system switches to the high-critical behavior. This paper extends the IMC task model by associating specific Quality-of-Service (QoS) values with the low-critical tasks and proposes a fluid-based scheduling algorithm, called MCFQ, for such task model. The MCFQ algorithm allows some low-critical tasks to provide full service even during the high-critical behavior so that the QoS of the overall system is increased. To the best of our knowledge MCFQ is the first algorithm for IMC task sets considering multiprocessor platform and QoS values. By extending the recently proposed MC-Fluid and MCF fluid-based multiprocessor scheduling algorithms for IMC task model, empirical results show that MCFQ algorithm can significantly improve the QoS of the system in comparison to that of both MC-Fluid and MCF. In addition, the schedulability performance of MCFQ is very close to the optimal MC-Fluid algorithm. Finally, we prove that the MCFQ algorithm has a speedup bound of 4/3, which is optimal for IMC tasks.

Multicore architectures can provide high predictable performance through parallel processing. Unfortunately, computing the makespan of parallel applications is overly pessimistic either due to load imbalance issues plaguing static scheduling methods or due to timing anomalies plaguing dynamic scheduling methods. This paper contributes with an anomaly-free dynamic scheduling method, called Lazy, which is non-preemptive and non-greedy in the sense that some ready tasks may not be dispatched for execution even if some processors are idle. Assuming parallel applications using contemporary taskbased parallel programming models, such as OpenMP, the general idea of Lazy is to avoid timing anomalies by assigning fixed priorities to the tasks and then dispatch selective highestpriority ready tasks for execution at each scheduling point. We formally prove that Lazy is timing-anomaly free. Unlike all the commonly-used dynamic schedulers like breadth-first and depth-first schedulers (e.g., CilkPlus) that rely on analytical approaches to determine an upper bound on the makespan of parallel application, a safe makespan of a parallel application is computed by simulating Lazy. Our experimental results show that the makespan computed by simulating Lazy is much tighter and scales better as demonstrated by four parallel benchmarks from a task-parallel benchmark suite in comparison to the state-of-the-art.

An algorithm (called FTM ) for scheduling of real-time sporadic tasks on a multicore platform is proposed. Each task has a deadline by which it must complete its non-erroneous execution. The FTM algorithm executes backups in order to recover from errors caused by non-permanent and permanent hardware faults. The worst-case schedulability analysis of FTM algorithm is presented considering an application-level error model, which is independent of the stochastic behavior of the underlying hardware-level fault model. Then, the stochastic behavior of hardware-level fault model is plugged in to the analysis to derive the probability of meeting all the deadlines. Such probabilistic guarantee is the level of assurance (i.e., reliability) regarding the correct functional and timing behaviors of the system. One of the salient features of FTM algorithm is that it executes some backups in active redundancy to exploit the parallel multicore architecture while other backups passively to avoid unnecessary execution of too many active backups. This paper also proposes a scheme to determine for each task the number of backups that should run in active redundancy in order to increase the probability of meeting all the deadlines. The effectiveness of the proposed approach is demonstrated using an example application.

The problem of estimating the makespan for parallel applications is overly pessimistic bounds either due to load imbalance issues plaguing static scheduling methods or due to timing anomalies plaguing dynamic scheduling methods for multicore architectures. While dynamic scheduling (where tasks are not pre-assigned) offers better utilization of the processors, it suffers from timing anomalies. This paper contributes with a new timing-anomaly-free dynamic scheduling algorithm, called the Out-of-(priority)-order Lazy (O-Lazy) that offers safe and tighter estimation of the makespan of parallel applications.

This paper proposes a new preemptive scheduling algorithm, called Fixed-Priority with Priority Promotion (FPP), for scheduling sporadic tasks on uni- and multiprocessor platform. In FPP scheduling, tasks are executed similar to traditional fixed-priority (FP) scheduling but the priority of some tasks may be promoted at fixed time interval (called, promotion point) relative to the release time of each job. A policy called Increase Priority at Deadline Difference (IPDD) to compute the promotion points and promoted priorities for each task is proposed. It is shown that when all tasks' priorities are governed under IPDD policy, then FPP scheduling essentially prioritizes jobs according to Earliest-Deadline-First (EDF) priority. It is known that inserting and removing jobs to and from the ready queue of traditional EDF scheduler is more complex and has higher overhead than that of FP scheduler. To avoid such problem in FPP scheduling, a simple data structure and efficient operations to insert and remove jobs to and from the ready queue are proposed. Finally, an effective scheme to reduce overhead due to priority promotion is proposed: if a task set is not schedulable using traditional FP scheduling, then promotion points are assigned only to those tasks that need them to meet the deadlines; otherwise, tasks are assigned fixed priorities without any priority promotion and executed same as traditional FP scheduling. Empirical investigation shows the effectiveness of the proposed scheme in reducing overhead on uniprocessor and in accepting larger number of task sets in comparison to that of using state-of-the-art global schedulability tests for multiprocessors.

Many previously proposed interface models for composability analysis of hierarchical scheduling are overhead-unaware, which is unsafe for real systems. This paper proposes an overhead-aware schedulability analysis to guarantee temporal partitioning among real-time applications/components hosted on a multicore platform. First, a new interface model and the method to generate an interface for a given component is proposed. Each interface has a tunable parameter d (degree) that can balance between abstraction and accuracy in capturing each component's task-level timing constraints. Second, the problem of constructing an overhead-aware system-level schedule of all the components is addressed. The system designer has the flexibility to select parameters (e.g., allocated processor bandwidth) for each component such that overhead (e.g., preemptions across partitions) is minimized. Third, a slack distribution algorithm to reduce various overhead is proposed and its effectiveness is evaluated using randomly generated interface sets and also using workload of a real space-borne application provided by RUAG Space Sweden AB.

In this paper we are concerned with the fundamental problem of reaching agreement among a set of distributed processes in presence of an unbounded number of communication failures. We present a probabilistic analysis of a family of synchronous consensus algorithms that aim to solve the 1-of-n selection problem. In this problem, a set of n nodes are to select one common value among a set of n proposed values. There are two possible outcomes of each node's selection process: it can decide either to select a value, or to abort. Agreement implies that all nodes select the same value, or all nodes decide to abort. We know from previous research that it is impossible to guarantee agreement if there is no upper bound on the number of communication failures that can occur. Our aim is to study how the probability of disagreement varies for different decision criteria. The decision criterion consists of the logical expressions that determine whether a process will select a value or decide to abort based on its view of the system state. In this paper we propose and analyse a moderately pessimistic decision criterion. We compared this decision criterion with an optimistic and a pessimistic decision criterion, which we have investigated in our previous work. Our results show that the moderately pessimistic decision criterion for most configurations has a lower maximum probability of disagreement compared with the two other decision criteria. Furthermore, it provides a compromise between the optimistic and the pessimistic approaches since it reduces the probability of disagreement without increasing excessively the probability of agreeing to abort.

The advent of multicore processors has attracted many safety-critical systems, e.g., automotive and avionics, to consider integrating multiple functionalities on a single, powerful computing platform. Such integration leads to host functionalities with different criticality levels on the same platform. The design of such ``mixed-criticality'' systems is often subject to certification from one or more certification authorities. Coming up with an effective scheduling policy and its analysis that can guarantee certification of the system at each criticality level, while maximizing the utilization of the processors, is the focus of the research presented in this paper. In this paper, the global, fixed-priority scheduling of a set of sporadic, mixed-criticality, tasks on multiprocessors is considered. A sufficient schedulability test based on response time analysis of the proposed algorithm is derived. One of the useful features of the proposed test is that it can be used for systems with more than two criticality levels. In addition, the test can be used to find ``effective'' fixed-priority ordering of the mixed-criticality tasks based on Audsley's approach.

In this paper, global fixed-priority multiprocessor scheduling of a set of sporadic real-time tasks is addressed. First, we propose a priority-assignment policy, called ISM-US, for implicit-deadline task systems. Policy ISM-US assigns slack monotonic priorities to a subset of the given task set and other tasks are assigned the highest fixed priority. We prove that the schedulability utilization bound for policy ISM-US is higher than the corresponding bound for any other existing schedulability test for implicit-deadline sporadic task systems. Second, we propose improvements to two state-of-the-art iterative schedulability tests for constrained-deadline sporadic task systems. Our improved schedulability tests, called HP-RTA-LC and HP-DA-LC, are based on a hybrid-priority assignment policy and are shown to dominate the two existing state-of-the-art tests, RTA-LC and DA-LC, respectively.

In this paper, we consider preemptive scheduling of a set of fixed-priority, sporadic tasks on multiprocessors from both real-time and fault-tolerant perspectives. We propose a fault-tolerant multiprocessor scheduling algorithm, called FTGS, exploiting time redundancy to tolerate both task errors and processor failures. The main contribution of this paper is the derivation of a feasibility test for our proposed FTGS algorithm. This feasibility test when satisfied guarantees that all the deadlines of the real-time tasks are met even in the presence of task errors and processor failures. The major strength of FTGS algorithm is the fault model it assumes; we consider a variety of software and hardware faults that may lead to task errors or processor failures. The novelty of our proposed feasibility test is that the resilience of resource constrained embedded real-time systems can be determined for different combinations of task errors and processor failures.

This paper addresses global Rate-Monotonic (RM) scheduling of implicit-deadline periodic real-time tasks on uniform multiprocessor platforms. In particular, we propose new schedulability conditions that include a set of easily computable task-set parameters for achieving better system utilization while meeting the deadlines of all the tasks. First, an individual sufficient schedulability condition is derived for each task. Then, the collection of schedulability conditions for the tasks are condensed to provide two different simple sufficient schedulability conditions for the entire task system - one for uniform multiprocessors, and one for unit-capacity multiprocessors, respectively. Finally, we show that our proposed simple rate-monotonic schedulability conditions for uniform and unit-capacity multiprocessors have higher worst-case system utilization than all other state-of-the-art simple schedulability conditions for global rate-monotonic scheduling of implicit-deadline tasks.

This paper proposes a fixed-priority partitioned scheduling algorithm for periodic tasks on multiprocessors. A new technique for assigning tasks to processors is developed and the schedulability of the algorithm is analyzed for worst-case performance. We prove that, if the workload (utilization) of a given task set is less than or equal to 55.2% of the total processing capacity on m processors, then all tasks meet their deadlines. During task assignment, the total work load is regulated to the processors in such a way that a subset of the processors are guaranteed to have an individual processor load of at least 55.2%. Due to such load regulation, our algorithm can be used efficiently as an admission controller for online task scheduling. And this online algorithm is scalable with increasing number of cores in chip multiprocessors. In addition, our scheduling algorithm possesses two properties that may be important for the system designer. The first one guarantees that if task priorities are fixed before task assignment they do not change during task assignment and execution, thereby facilitating debugging during development and maintenance of the system. The second property guarantees that at most m/2 tasks are split, thereby keeping the run-time overhead as caused by task splitting low.

In this paper, a necessary and sufficient (exact) feasibility test is proposed for fixed-priority scheduling of a periodic task set to tolerate multiple faults on uniprocessor. We consider a fault model such that multiple faults can occur in any task and at any time, even during recovery operations. The proposed test considers tolerating a maximum of f faults that can occur within any time interval equal to the largest relative deadline of the task set. The feasibility of the task set is checked based on the maximum workload requested by the higher-priority jobs within the released time and deadline of the job of each task that is released at the critical instant. The maximum workload is calculated using a novel technique to compose the execution time of the higher-priority jobs. To the best of our knowledge, no other work (assuming the same fault model as ours) has derived an exact feasibility test for periodic task sets having a lower time complexity than that of the test proposed in this paper.