https://www.mdu.se/

Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive Earliest Deadline First (EDF-P). In this paper, we investigate the sub-optimality of xed priority non-preemptive scheduling. Speci cally, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulablability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive xed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.

Preemption point selection has a significant impact on the schedulability of Real-Time tasks under the Fixed Preemption Point approach in Limited Preemptive Scheduling. Many real time systems can occasionally tolerate deadline misses as long as their occurrence does not exceed a specified probabilistic threshold. However, the existing approaches for preemption point selection are inappropriate for such systems, as they are mainly aiming to provide hard guarantees, considering worst case (upper bounded) preemption overheads. Additionally, the worst case preemption overheads typically occur with very low probabilities. In this paper, we propose a novel preemption point selection approach, and an associated probabilistic response time analysis, considering preemption related overheads modelled as probabilistic distributions. The method is suitable for providing solutions in systems that can occasionally tolerate deadline misses and can be interesting in the context of mixed criticality systems. Our method is able to find solutions, in terms of preemption point selections, in all cases where the existing approaches do. Moreover, it provides preemption point selections for additional tasksets that guarantees the overall taskset schedulability with a certain probability. The evaluation results show an improvement with respect to increasing the number of tasksets for which a preemption point selection is possible compared to existing, upper-bound based, selection approaches. The results show that the deadline miss probabilities of the tasksets and associated preemption point selections are considerably low.

Global limited preemptive real-time scheduling in multiprocessor systems using Fixed Preemption Points (FPP) brings in an additional challenge with respect to the choice of the task to be preempted in order to maximize schedulability. Two principal choices with respect to the preemption approach exist (1) the scheduler waits for the lowest priority job to become preemptible, (2) the scheduler preempts the first job, among the lower priority ones, that becomes preemptible. We refer to the former as the Lazy Preemption Approach (LPA) and the latter as the Eager Preemption Approach (EPA). Each of these choice has a different effect on the actual number of preemptions in the schedule, that in turn determine the runtime overheads. In this paper, we perform an empirical comparison of the run-time preemptive behavior of Global Preemptive Scheduling and Global Limited Preemptive Scheduling with EPA and LPA, under both Earliest Deadline First (EDF) and Fixed Priority Scheduling (FPS) paradigms. Our experiments reveal interesting observations some of which are counterintuitive. We then analyse the counter-intuitive observations and identify the associated reasons. The observations presented facilitate the choice of appropriate strategies when using limited preemptive schedulers on multiprocessor systems.

Preemptive and non-preemptive scheduling paradigms typically introduce undesirable side effects when scheduling real-time tasks, mainly in the form of preemption overheads and blocking, that potentially compromise timeliness guarantees. The high preemption overheads in preemptive real-time scheduling may imply high resource utilization, often requiring significant over-provisioning, e.g., pessimistic Worst Case Execution Time (WCET) approximations. Non-preemptive scheduling, on the other hand, can be infeasible even for tasksets with very low utilization, due to the blocking on higher priority tasks, e.g., when one or more tasks have WCETs greater than the shortest deadline. Limited preemptive scheduling facilitates the reduction of both preemption related overheads as well as blocking by deferring preemptions to favorable locations in the task code.

In this thesis, we investigate the feasibility of limited preemptive scheduling of real-time tasks on uniprocessor and multiprocessor platforms. We derive schedulability tests for global limited preemptive scheduling under both Earliest Deadline First (EDF) and Fixed Priority Scheduling (FPS) paradigms. The tests are derived in the context of two major mechanisms for enforcing limited preemptions, viz., defer preemption for a specified duration (i.e., Floating Non-Preemptive Regions) and defer preemption to the next specified location in the task code (i.e., Fixed Preemption Points). Moreover, two major preemption approaches are considered, viz., wait for the lowest priority job to become preemptable (i.e., a Lazy Preemption Approach (LPA)) and preempt the first executing lower priority job that becomes preemptable (i.e., an Eager Preemption Approach (EPA)). Evaluations using synthetically generated tasksets indicate that adopting an eager preemption approach is beneficial in terms of schedulability in the context of global FPS. Further evaluations simulating different global limited preemptive scheduling algorithms expose runtime anomalies with respect to the observed number of preemptions, indicating that limited preemptive scheduling may not necessarily reduce the number of preemptions in multiprocessor systems. We then theoretically quantify the sub-optimality (the worst-case performance) of limited preemptive scheduling on uniprocessor and multiprocessor platforms using resource augmentation, e.g., processor speed-up factors to achieve optimality. Finally, we propose a sensitivity analysis based methodology to control the preemptive behavior of real-time tasks using processor speed-up, in order to satisfy multiple preemption behavior related constraints. The results presented in this thesis facilitate the analysis of limited preemptively scheduled real-time tasks on uniprocessor and multiprocessor platforms.

The growing complexity of software employed in the cyber-physical domain is calling for a thorough study of both its functional and extra-functional properties. Ethical aspects are among important extra-functional properties, that cover the whole life cycle with different stages from design, development, deployment/production to use of cyber physical systems. One of the ethical challenges involved is the question of identifying the responsibilities of each stakeholder associated with the development and use of a cyber-physical system. This challenge is made even more pressing by the introduction of autonomous increasingly intelligent systems that can perform functionalities without human intervention, because of the lack of experience, best practices and policies for such technology. In this article, we provide a framework for responsibility attribution based on the amount of autonomy and automation involved in AI based cyber-physical systems. Our approach enables traceability of anomalous behaviors back to the responsible agents, be they human or software, allowing us to identify and separate the "responsibility" of the decision-making software from human responsibility. This provides us with a framework to accommodate the ethical "responsibility" of the software for AI based cyber-physical systems that will be deployed in the future, underscoring the role of ethics as an important extra-functional property. Finally, this systematic approach makes apparent the need for rigorous communication protocols between different actors associated with the development and operation of cyber-physical systems that further identifies the ethical challenges involved in the form of group responsibilities.

Dependability is an important requirement in hard real-time applications due to the potentially catastrophic consequences of failures. In these systems, fault tolerance mechanisms like temporal redundancy are adopted to improve reliability. Most of these types of systems are increasingly moving towards integrating critical and non-critical functionalities on the same platform to, e.g., better utilize resources and further reduce cost, and are commonly deployed in environments where errors typically occur in the form of bursts e.g., due to Electro Magnetic Interference (EMI). Consequently, in mixed criticality real-time systems, the designer must guarantee that critical tasks are feasible even under the presence of the error burst, while ensuring the feasibility of the non-critical tasks that are not affected by the burst. We refer to this as {em Fault Tolerance feasibility} (FT-feasibility) of mixed-criticality real-time systems. In this paper, we build on the well established results on Earliest Deadline First (EDF) scheduling, to derive a sufficient test that determines the FT-feasibility of a set of mixed criticality real-time tasks under the assumption that the inter-arrival time between two consecutive error bursts is at least equal to the hyper-period of the taskset.

Adopting mixed-criticality architectures enable safe sharing of computational resources between tasks of different criticalities consequently leading to reduced Size, Weight and Power (SWaP) requirements. A majority of the research in mixed-criticality systems focuses on scheduling tasks whose Worst Case Execution Times (WCETs) are certified to varying levels of assurances. If any given task overruns its WCET, the system switches to a higher criticality and all the lower criticality tasks are discarded to make time for the execution of higher criticality tasks. Task execution time overruns are transient faults that are typically tolerated by simply executing an alternate task before the original deadline, or, by discarding the failed task to prevent it from interfering with higher criticality tasks. However, permanent faults such as processor failures can render the system to be useless, many times leading to unsafe states. In this paper we present a taxonomy of fault tolerance techniques to tolerate permanent faults, as well as map it to real-time mixed-criticality requirements based on the extend of fault coverage that in turn influences the associated assurance.

Challenges associated with allowing preemptions and migrations are compounded in multicore systems, particularly under global scheduling policies, because of the potentially high overheads. For example, multiple levels of cache greatly increase preemption and migration related overheads as well as the difficulty involved in accurately accounting for them, leading to substantially inflated worst-case execution times. Preemption and migrations related overheads can be significantly reduced, both in number and in size, by using fixed preemption points in the tasks' code; thus dividing each task into a series of non-preemptive regions. This leads to an additional consideration in the scheduling policy. When a high priority task is released and all of the processors are executing non-preemptive regions of lower priority tasks, then there is a choice to be made in terms of how to manage the next preemption. With an eager approach the first lower priority task to reach a preemption point is preempted even if it is not the lowest priority running task. Alternatively, with a lazy approach, preemption is delayed until the lowest priority currently running task reaches its next preemption point. In this paper, we show that under global fixed priority scheduling with eager preemptions each task suffers from at most a single priority inversion each time it resumes execution. Building on this observation, we derive a new response time based schedulability test for tasks with fixed preemption points. Experimental evaluations show that global fixed priority scheduling with eager preemptions is significantly more effective than with lazy preemption using link based scheduling in terms of task set schedulability.

Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive Earliest Deadline First (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulablability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP), which since it matches a recently published upper bound gives the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, i.e., there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive upper and lower bounds on the speed-up factor required to guarantee FP-P feasibility of any FP-NP feasible task set. Empirical evidence suggests that the lower bound may be tight, and hence equate to the exact speed-up factor in this case.

The preemptive scheduling paradigm is known to strictly dominate the non-preemptive scheduling paradigm with respect to feasibility. On the other hand, preemptively scheduling real-time tasks on uniprocessors, unlike non-preemptive scheduling, may lead to unschedulability due to, e.g., preemption related overheads. The limited-preemptive scheduling paradigm, which is a generalization of preemptive and non-preemptive paradigms, has, however, the potential to reduce the preemption related overheads while enabling high processor utilization. In this paper, we focus on the characterization of the effects of increasing the computational resources on the limited-preemptive feasibility of real-time tasks in order to quantify the sub-optimality of limited-preemptive scheduling. Specifically, we first derive the required processor speed-up bound that guarantees limited-preemptive feasibility of any uniprocessor feasible taskset. Secondly, we demonstrate the applicability of the results in the context of controlling preemption related overheads while minimizing the required processor speed-up. In particular, we identify the preemptive behavior that minimizes preemption-related overheads, as well as derive the optimal processor speed associated with it. Finally, we examine the consequences of having more processors on limited-preemptive feasibility and derive the bound on the number of processors that guarantees a specified limited-preemptive behavior for any uniprocessor feasible real-time taskset. This paper essentially bridges the preemptive and non-preemptive real-time scheduling paradigms by providing significant theoretical results building on the limitedpreemptive scheduling paradigm, as well as provides analytical inputs to developers in order to perform various trade-offs, e.g., code refactoring, to control the preemptive behavior of real-time tasks.