| 1. |
- Aysan, Hüseyin, et al.
(författare)
-
Efficient Fault Tolerant Scheduling on Controller Area Network (CAN)
- 2010
-
Ingår i: Proceedings of the 15th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2010. - Bilbao, Spain. ; , s. Art.nr 5641318-
-
Konferensbidrag (refereegranskat)abstract
- Dependable communication is becoming a critical factor due to the pervasive usage of networked embedded systems that increasingly interact with human lives in many real-time applications. Controller Area Network (CAN) has gained wider acceptance as a standard in a large number of industrial applications, mostly due to its efficient bandwidth utilization, ability to provide real-time guarantees, as well as its fault-tolerant capability. However, the native CAN fault-tolerant mechanism assumes that all messages transmitted on the bus are equally critical, which has an adverse impact on the message latencies, results in the inability to meet user defined reliability requirements, and, in some cases, even leads to violation of timing requirements. As the network potentially needs to cater to messages of multiple criticality levels (and hence varied redundancy requirements), scheduling them in an efficient fault-tolerant manner becomes an important research issue. We propose a methodology which enables the provision of appropriate guarantees in CAN scheduling of messages with mixed criticalities. The proposed approach involves definition of fault-tolerant feasibility windows of execution for critical messages, and off-line derivation of optimal message priorities that fulfill the user specified level of fault-tolerance.
|
|
| 2. |
- Davis, Rob, et al.
(författare)
-
Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling
- 2015
-
Ingår i: Proceedings - Real-Time Systems Symposium. - 9781467395076 ; , s. 96-106
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 3. |
|
|
| 4. |
- Thekkilakattil, Abhilash, et al.
(författare)
-
An empirical investigation of eager and lazy preemption approaches in global limited preemptive scheduling
- 2016
-
Ingår i: Lecture Notes in Computer Science. - Cham : Springer. - 9783319390826 ; , s. 163-178
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 5. |
- Thekkilakattil, Abhilash, et al.
(författare)
-
Bounding the effectiveness of temporal redundancy in fault-tolerant real-time scheduling under error bursts
- 2014
-
Ingår i: 19th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2014. - 9781479948468 ; , s. Article number 7005170-
-
Konferensbidrag (refereegranskat)abstract
- Reliability is a key requirement in many distributed real-time systems deployed in safety and mission critical applications, and temporal redundancy is a widely employed strategy towards guaranteeing it. The temporal redundancy approach is typically based on task re-executions in form of entire tasks, task alternates or, check-pointing blocks, and each of the re-execution strategies have different impacts on the Fault Tolerance feasibility (FT-feasibility) of the system, which is traditionally defined as the existence of a schedule that guarantees timeliness of all tasks under a specified fault hypothesis. In this paper, we propose the use of resource augmentation to quantify the FT-feasibility of real-time task sets and use it to derive limits on the effectiveness of temporal redundancy in fault-tolerant real-time scheduling under error bursts of bounded lengths. We derive the limits for the general case, and then show that for the specific case when the error burst length is no longer than half the shortest deadline, the lower limit on the effectiveness of temporal redundancy is given by the resource augmentation bound 2, while, the corresponding upper-limit is 6. Our proposed approach empowers a system designer to quantify the effectiveness of a particular implementation of temporal redundancy.
|
|
| 6. |
- Thekkilakattil, Abhilash, et al.
(författare)
-
Ethics Aspects of Embedded and Cyber-Physical Systems
- 2015
-
Ingår i: 39th IEEE Annual Computer Software and Applications Conference, COMPSAC 2015, Taichung, Taiwan, 1-5 July 2015. - : IEEE. - 0730-3157. - 9781467365635
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 7. |
- Thekkilakattil, Abhilash, et al.
(författare)
-
Fault Tolerant Scheduling of Mixed Criticality Real-Time Tasks under Error Bursts
- 2015
-
Ingår i: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON INFORMATION AND COMMUNICATION TECHNOLOGIES, ICICT 2014. - Kochi, India : Elsevier Procedia Computer Science. ; , s. 1148-1155
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 8. |
- Thekkilakattil, Abhilash
(författare)
-
Limited Preemptive Scheduling in Real-time Systems
- 2016
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 9. |
- Thekkilakattil, Abhilash, et al.
(författare)
-
Mixed Criticality Systems : Beyond Transient Faults
- 2015
-
Ingår i: WMC 2015.
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 10. |
- Thekkilakattil, Abhilash, et al.
(författare)
-
Multiprocessor Fixed Priority Scheduling with Limited Preemptions
- 2015
-
Ingår i: ACM International Conference Proceeding Series, Volume 04-06. - New York, NY, USA : ACM. - 9781450335911 ; , s. 13-22
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
