mdh.sePublikationer
Ändra sökning
Avgränsa sökresultatet
1 - 27 av 27
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Aysan, Hüseyin
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Thekkilakattil, Abhilash
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Efficient Fault Tolerant Scheduling on Controller Area Network (CAN)2010Ingår i: Proceedings of the 15th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2010, Bilbao, Spain, 2010, s. Art.nr 5641318-Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.
    University of York, UK.
    Gettings, Oliver
    University of York, UK.
    Thekkilakattil, Abhilash
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    What is the Exact Speedup Factor for Fixed Priority Pre-emptive versus Fixed Priority Non-pre-emptive Scheduling?2015Ingår i: Proceedings of the 6th Real-Time Scheduling Open Problems Seminar (RTSOPS): held in conjunction with the 27th Euromicro Conference on Real-Time Systems (ECRTS), Lund, Sweden, 2015, s. 23-24Konferensbidrag (Refereegranskat)
  • 3.
    Davis, Rob
    et al.
    University of York, York, UK.
    Thekilakkattil, Abhilash
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Gettings, Oliver
    University of York, York, UK.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Chen, Jian-Jia
    Technische Universität, Dortmund, Germany..
    Exact Speedup Factors and Sub-Optimality for Non-Preemptive Scheduling2018Ingår i: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, s. 208-246Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.

  • 4.
    Davis, Rob
    et al.
    University of York, UK.
    Thekkilakattil, Abhilash
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Gettings, Oliver
    University of York, UK.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling2015Ingår i: Proceedings - Real-Time Systems Symposium, 2015, s. 96-106Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 5.
    Markovic, Filip
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Carlson, Jan
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Thekilakkattil, Abhilash
    Ericsson, Stockholm, Sweden.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Lisper, Björn
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Probabilistic Response Time Analysis for Fixed Preemption Point Selection2018Ingår i: 13th International Symposium on Industrial Embedded Systems SIES '18, 2018, artikel-id 8442099Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 6.
    Thekilakkattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Aysan, Hüseyin
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Optimizing the Fault Tolerance Capabilities of Distributed Real-Time Systems2009Ingår i: 14th International Conference on Emerging Technologies and Factory Automation, WiP, 2009Konferensbidrag (Refereegranskat)
    Abstract [en]

    Industrial real-time systems typically have to satisfy complex requirements, mapped to the task attributes, eventually guaranteed by a fixed priority scheduler in a distributed environment. These systems consist of a mix of hard and soft tasks with varying criticality, as well as associated fault tolerance requirements. Time redundancy techniques are often preferred in industrial applications and, hence, it is extremely important to devise resource efficient methodologies for scheduling real-time tasks under failure assumptions. In this paper, we propose a methodology to provide a priori guarantees in distributed real-time systems with redundancy requirements. We do so by identifying temporal feasibility windows for all task executions and re-executions, as well as allocating them on different processing nodes. We then use optimization theory to derive the optimal feasibility windows that maximize the utilization on each node, while avoiding overloads. Finally on each node, we use Integer Linear Programming (ILP) to derive fixed priority task attributes that guarantee the task executions within the derived feasibility windows, while keeping the associated costs minimized.

  • 7.
    Thekkilakattil, Abhilash
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Limited Preemptive Scheduling in Real-time Systems2016Doktorsavhandling, monografi (Övrigt vetenskapligt)
    Abstract [en]

    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.

  • 8.
    Thekkilakattil, Abhilash
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Resource Augmentation for Performance Guarantees in Embedded Real-time Systems2012Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    Real-time scheduling policies have been widely studied, with many known schedulability and feasibility analysis techniques for different task models, that have advanced the state-of-the-art. Most of these techniques are typically derived under the assumption of negligible runtime overheads which may not be realistic for modern embedded real-time systems, and hence potentially compromises the guarantees on their correct behaviors. This calls for methods to reason about the functioning of the system under the presence of such overheads as well as to predictably control them. Controlling these overheads may place additional performance demands, consequently requiring more resources such as faster processors. At the same time, the need for energy efficiency in these class of systems further complicates the problem and necessitates a holistic approach.

    In this thesis, we apply resource augmentation, viz., processor speed-up, to guarantee desired real-time properties even under the presence of runtime overheads. We specifically consider preemptions and faults that, at runtime, manifest as overheads in the system in various ways. Our aim is to provide specified non-preemption and fault tolerance feasibility guarantees in a real-time system. We first propose offline and online methods, that uses CPU frequency scaling, to control the number of preemptions in periodic and sporadic task systems, under a preemptive Fixed Priority Scheduling (FPS) policy. Furthermore, we derive the resource augmentation bound, specifically the upper-bound on the lowest processor speed, that guarantees the feasibility of a specified non-preemption behavior for any real-time task. We show that, for any task Ti , the resource augmentation bound that guarantees a non- reemptive execution for a specified duration Li , is given by 4Li/Dmin, where Dmin  is the shortest deadline in the task set. Consequently, we show that the upper-bound on the lowest processor speed that guarantees the feasibility of a non-preemptive schedule for the task set is 4Cmax/Dmin, where Cmax  is the largest execution time in the task set. We then propose a method to guarantee specified upper-bounds on the preemption related overheads in the schedule. We first translate the requirements of meeting specified upper-bounds on the preemption related overheads to a set of non-preemption requirements for the task set. The resource augmentation bound in conjunction with a sensitivity analysis is used to calculate the optimal processor speed that guarantees the derived non-preemption requirements, achieving the specified bounds on the preemption related costs. Finally, we derive the resource augmentation bound that guarantees the fault tolerance feasibility of a set of real-time tasks under an error burst of known length. We show that if the error burst length is no longer than half the shortest deadline in the task set, the resource augmentation bound that guarantees fault tolerance feasibility is 6. 

    Our contribution bounds the extra resources, specifically the required processor speed-up, that provides specified non-preemption and fault tolerance feasibility guarantees in a real-time system. It allows us to quantify the 'goodness' of non-preemptive scheduling, referred to as its sub-optimality, as compared to an optimal uni-processor scheduling algorithm, in terms of the required processor speed-up that guarantees a non-preemptive schedule for any uni-processor feasible task set. We intend to extend this work to provide non-preemption and fault tolerance feasibility guarantees in multi-processor systems.

  • 9.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Aysan, Hüseyin
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Towards a Contract-based Fault-tolerant Scheduling Framework for Distributed Real-time Systems2011Konferensbidrag (Refereegranskat)
    Abstract [en]

    The increasing complexity of real-time systems has lead to the adaptation of component based methods for their development which has a promising potential for faster and more cost effective development of complex real-time systems by facilitating reuse of the real-time components. This is enabled by the components' composition using contracts, which ensures 'correctness by construction'. Modern real-time systems typically consist of mixed criticality components, and scheduling them in a fault-tolerant as well as efficient way, on a distributed platform, is a challenging task. In this paper, we propose a contract-based approach to fault tolerant scheduling of mixed criticality real-time components on a distributed platform, by providing guarantees for the hard real-time components through offline negotiated contracts, as well as flexibility for the soft real-time components through online (re-)negotiated contracts. The proposed approach uses optimization techniques, that uses timing requirements and the recommendations of studies like Fault Hazard Analysis and Zonal Analysis, to provide the contractual parameters for the mixed-criticality components.

  • 10.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Baruah, Sanjoy
    University of North Carolina at Chapel Hill, USA.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    The Global Limited Preemptive Earliest Deadline First Feasibility of Sporadic Real-time Tasks2014Ingår i: Proceedings - Euromicro Conference on Real-Time Systems, 21 October 2014, 2014, s. 301-310Konferensbidrag (Refereegranskat)
    Abstract [en]

    The feasibility of preemptive and non-preemptivescheduling has been well investigated on uniprocessor and multiprocessor platforms under both Fixed Priority Scheduling(FPS) and Earliest Deadline First (EDF) paradigms. While feasibility of limited preemptive scheduling under FPS has been addressed on both uniprocssor and multiprocessor platforms,under EDF it has been investigated only on uniprocessors, and a similar analysis for multiprocessor platforms is still missing.In this paper, we introduce global Limited Preemptive Earliest Deadline First (g-LP-EDF) scheduling, and propose the associated feasibility analysis to complete the above described feasibility analysis spectrum. Specifically, we derive a sufficient condition that guarantees g-LP-EDF feasibility of sporadic real timetasks which directly provides a global Non-Preemptive Earliest Deadline First (g-NP-EDF) feasibility test. We then study the interplay between g-LP-EDF feasibility and processor speed, in order to quantify the sub-optimality of g-NP-EDF in terms of the minimum speed-up required to guarantee g-NP-EDF feasibility of all feasible tasksets. The results presented in this paper complement our previous results on uniprocessors, and provide a unified result on the sub-optimality of non-preemptive EDF on both uniprocessor and multiprocessor platforms.

  • 11.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Burns, Alan
    University of York, UK.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Birla Institute of Technology and Science, India.
    Mixed Criticality Systems: Beyond Transient Faults2015Ingår i: WMC 2015: Proceedings of the 3rd International Workshop on Mixed Criticality Systems, 2015Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 12.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Davis, Rob
    University of York, UK.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Birla Institute of Technology and Science, India.
    Bertogna, Marko
    University of Modena, Italy.
    Multiprocessor Fixed Priority Scheduling with Limited Preemptions2015Ingår i: ACM International Conference Proceeding Series, Volume 04-06, 2015, s. 13-22Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 13.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Bounding the effectiveness of temporal redundancy in fault-tolerant real-time scheduling under error bursts2014Ingår i: 19th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2014, 2014, s. Article number 7005170-Konferensbidrag (Refereegranskat)
    Abstract [en]

    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. 

  • 14.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Fault Tolerant Scheduling of Mixed Criticality Real-Time Tasks under Error Bursts2015Ingår i: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON INFORMATION AND COMMUNICATION TECHNOLOGIES, ICICT 2014, Kochi, India: Elsevier Procedia Computer Science , 2015, s. 1148-1155Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 15.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Preemption Control using CPU Frequency Scaling in Real-time Systems2011Ingår i: 18th INTERNATIONAL CONFERENCE ON CONTROL SYSTEMS AND COMPUTER SCIENCE, 2011, s. 88-95Konferensbidrag (Refereegranskat)
    Abstract [en]

    Controlling the preemption behavior in real-time systems can have beneficial impacts in multiple contexts as it can decrease the processor utilization, reduce the energy consumption or even enable the schedulability of the system. In this paper we study the preemption behavior of sporadic task systems scheduled using the Fixed Priority Scheduling (FPS) policy, and evaluate the feasibility of preemption control using CPU frequency scaling. We show that offline preemption control using CPU frequency scaling is difficult for sporadic task systems, and we propose an online heuristic algorithm, of linear complexity, to control the number of preemptions in a sporadic task system. Evaluation results show that online CPU frequency scaling is an attractive approach for preemption control in sporadic task systems.

  • 16.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Probabilistic Preemption Control using Frequency Scaling for Sporadic Real-time Tasks2012Ingår i: 7th IEEE International Symposium on IndustrialEmbedded Systems (SIES): Conference Proceedings, IEEE Computer Society, 2012, s. 158-165Konferensbidrag (Refereegranskat)
    Abstract [en]

    Preemption related costs are major sources of unpredictability in the task execution times in a real-time system. We examine the possibility of using CPU frequency scaling to control the preemption behavior of real-time sporadic tasks scheduled using a preemptive Fixed Priority Scheduling (FPS) policy. Our combined offline-online method provides probabilistic preemption control guarantees by making use of the release time probabilities of the sporadic tasks. The offline phase derives the probability related deviation from the minimum inter-arrival time of tasks. The online algorithm uses this information to calculate appropriate CPU frequencies that guarantees non-preemptive task executions while preserving the overall system schedulability. The online algorithm has a linear complexity and does not lead to significant implementation overheads. Our evaluations demonstrate the effectiveness of the method as well as the possibility of energy-preemption trade offs. Even though we have considered FPS, our method can easily be extended to dynamic priority scheduling schemes

  • 17.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Quantifying the Sub-Optimality of Non-Preemptive Real-time Scheduling2013Ingår i: Proceedings - Euromicro Conference on Real-Time Systems, 2013, 2013, s. 113-122Konferensbidrag (Övrigt vetenskapligt)
    Abstract [en]

    A number of preemptive real-time scheduling algorithms, such as Earliest Deadline First (EDF), are known to be optimal on uni-processor systems under specified assumptions. However, no uni-processor optimal algorithm exists under the non-preemptive scheduling paradigm. Hence preemptive schemes strictly dominate non-preemptive schemes with respect to uni-processor feasibility. However, the 'goodness' of non-preemptive schemes, compared to uni-processor optimal preemptive scheduling schemes such as EDF, which can also be referred to as its sub-optimality, has not been fully investigated yet. In this paper, we apply resource augmentation, specifically processor speed-up, to quantify the sub-optimality of non-preemptive scheduling with respect to EDF, and apply the results to guarantee user specified upper-bounds on the preemption related scheduling costs. In particular, we derive an upper bound on the minimum processor speed-up required to guarantee the non-preemptive feasibility of tasks that are deemed feasible under the preemptive EDF, and we prove that, in the cases where, for all tasks in the task set, the largest execution requirement is not greater than the shortest deadline, this bound is equal to 4. We also show how the proposed approach enables a system designer to choose an optimal processor, in order to, e.g., guarantee specified upper bounds on the preemption related overheads.

  • 18.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    The Limited-preemptive Feasibility of Real-time Tasks on Uniprocessors2015Ingår i: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 51, nr 3, s. 247-273Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.

  • 19.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Towards Preemption Control Using CPU Frequency Scaling in Sporadic Task Systems2011Ingår i: SIES 2011 - 6th IEEE International Symposium on Industrial Embedded Systems, Conference Proceedings, Vasteras, 2011, s. 35-38Konferensbidrag (Refereegranskat)
    Abstract [en]

    Preemptions in real-time systems scheduling typically lead to variations in task execution times, increase the temporal overhead required for various RTOS related operations and may even cause unschedulability.We examine the preemption behavior of sporadic tasks scheduled under the Fixed Priority Scheduling (FPS) policy, and evaluate the possibility of using CPU frequency scaling for preemption control. We propose an online heuristic-based algorithm, of linear complexity, to control the number of preemptions in a sporadic task system using CPU frequency scaling. Evaluation results show that CPU frequency scaling is an attractive option to control the preemption behavior of real-time sporadic task systems.

  • 20.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Using Processor Speed-up to Control Preemption Related Costs2013Rapport (Övrigt vetenskapligt)
  • 21.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Aysan, Huseyin
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Resource Augmentation for Fault-Tolerance Feasibility of Real-time Tasks under Error Bursts2012Ingår i: Proceedings of the 20th International Conference on Real-Time and Network Systems (RTNS 12), Association for Computing Machinery (ACM), 2012, s. 41-50Konferensbidrag (Refereegranskat)
    Abstract [en]

    Dependability is a vital system requirement, particularly in safety critical and mission critical real-time systems, due to the potentially catastrophic consequences of failures. In most critical applications different fault tolerance mechanisms using redundancy are employed to prevent possible failures. In the case of real-time systems the system designer must ensure that the task set is feasible even under faults, which we refer to as 'fault tolerance feasibility'. Due to cost considerations, often temporal redundancy has been prevalently used to meet this objective.

    In this paper we focus on guaranteeing fault-tolerance feasibility under error bursts on uni-processor systems by the usage of resource augmentation, specifically through processor speed-up. Firstly, we derive a processor demand bound based sufficient condition for a set of real-time tasks to be fault tolerance feasible under an assumption that no more than one error burst occurs during the hyper-period of the task set. Subsequently, we derive the necessary resource augmentation bounds (i.e., the processor speed-up), that guarantees the fault tolerance feasibility, if the sufficient test fails. Finally, we prove that, if the error burst length is no more than half the shortest relative deadline of the task set, the minimum processor speed-up required to guarantee fault tolerance feasibility is upper-bounded by 6.

  • 22.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dodig-Crnkovic, Gordana
    Chalmers Technical University and University of Gothenburg, Gothenburg, Sweden.
    Ethics Aspects Of Embedded And Cyber-Physical Systems2015Ingår i: 2015 IEEE 39th Annual Computer Software and Applications Conference (COMPSAC), 2015, s. 39-44Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 23.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Pillai, Anju
    Amrita School of Engineering, Amrita Vishwa Vidyapeetham, India .
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Preemption Control Using Frequency Scaling in Fixed Priority Scheduling2010Ingår i: Proceedings - IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2010, 2010, s. 281-288Konferensbidrag (Refereegranskat)
    Abstract [en]

    Controlling the number of preemptions in realtime systems is highly desirable in order to achieve an efficient system design in multiple contexts. For example, the delays due to context switches account for high preemption overheads which detrimentally impact the system schedulability. Preemption control can also be potentially used for the efficient control of critical section behaviors in multi-threaded applications. At the same time, modern processor architectures provide for the ability to selectively choose operating frequencies, primarily targeting energy efficiency as well as system performance. In this paper, we propose the use of CPUFrequency Scaling for controlling the preemptive behavior of real-time tasks. We present a framework for selectively eliminating preemptions, that does not require modifications to the task attributes or to the underlying scheduler. We evaluate the proposed approach by four different heuristics through extensive simulation studies. 

  • 24.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Pillai, Anju S
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik.
    Reducing the Number of Preemptions in Real-Time Systems Scheduling by CPU Frequency Scaling2010Ingår i: 18th International Conference on Real-Time and Network Systems, Toulouse, France, 2010Konferensbidrag (Refereegranskat)
    Abstract [en]

    Controlling the number of preemptions in real-time systems is highly desirable in order to achieve an efficient system design in multiple contexts. For example, the delays due to context switches account for high preemption overheads which detrimentally impact the system schedulability. Preemption avoidance can also be potentially used for the efficient control of critical section behaviors in multi-threaded applications. At the same time, modern processor architectures provide for the ability to selectively choose operating frequencies, primarily targeting energy efficiency as well as system performance. In this paper, we propose the use of CPU Frequency Scaling for controlling the preemptive behavior of real-time tasks. We present a framework for selectively eliminating preemptions, that does not require modifications to the task attributes or to the underlying scheduler. We evaluate the proposed approach by four different heuristics through extensive simulation studies.

  • 25.
    Thekkilakattil, Abhilash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Zhu, K.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Nie, Y.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, S.
    Birla Institute of Technology and Science, Goa, India.
    An empirical investigation of eager and lazy preemption approaches in global limited preemptive scheduling2016Ingår i: Lecture Notes in Computer Science, Springer, 2016, s. 163-178Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 26.
    Thekkilakattil, Abilsash
    et al.
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Dobrin, Radu
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Punnekkat, Sasikumar
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Mixed criticality scheduling in fault-tolerant distributed real-time systems2014Ingår i: International Conference on Embedded Systems, ICES 2014, 2014, s. 92-97Konferensbidrag (Refereegranskat)
    Abstract [en]

    Modern safety critical real-time systems are composed of tasks of mixed criticalities and the problem of scheduling them in a fault tolerant manner, on a distributed platform, is challenging. Fault tolerance is typically achieved by using redundancy techniques, most commonly in the form of temporal redundancy which involves executing an alternate task before the original deadline of the failed task. Additionally, studies like Zonal Hazard Analysis (ZHA) and Fault Hazard Analysis (FHA) may impose extra constraints on the re-executions, e.g., spatial separation of alternates, to improve reliability. In this paper, we present a method for scheduling mixed criticality real-time tasks on a distributed platform in a fault tolerant manner while taking into account the recommendations given by the reliability studies like ZHA and FHA. First, we use mathematical optimization to allocate tasks on the processors, and then derive fault tolerant and fault aware feasibility windows for the critical and non-critical tasks respectively. Finally, we derive scheduler specific task attributes like priorities for the fixed priority scheduler. Our method provides hard real-time fault tolerance guarantees for critical tasks while maximizing resource utilization for non-critical tasks.

  • 27.
    Ward, B. C.
    et al.
    University of North Carolina at Chapel Hill, United States.
    Thekkilakattil, Abhilash
    Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
    Anderson, J. H.
    University of North Carolina at Chapel Hill, United States.
    Optimizing preemption-overhead accounting in multiprocessor real-time systems2014Ingår i: ACM International Conference Proceeding Series, 2014, Vol. 8, s. 235-243Konferensbidrag (Refereegranskat)
    Abstract [en]

    There exist two general techniques to account for preemption-related overheads on multiprocessors. This paper presents a new preemption-related overhead-accounting technique, called analytical redistribution of preemption overheads (ARPO), which integrates the two previous techniques to minimize preemption-overhead-related utilization loss. ARPO is applicable under any job-level fixed priority (JLFP) preemptive scheduler, as well as some limited-preemption schedulers. ARPO is evaluated in a new experimentaldesign framework for overhead-aware schedulability studies that addresses unrealistic simplifying assumptions made in previous studies, and is shown to improve real-time schedulability.

1 - 27 av 27
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf