mdh.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 61) Show all publications
Markovic, F., Carlson, J. & Dobrin, R. (2019). A Comparison of Partitioning Strategies for Fixed Points-based Limited Preemptive Scheduling. IEEE Transactions on Industrial Informatics, 15(2), 1070-1081
Open this publication in new window or tab >>A Comparison of Partitioning Strategies for Fixed Points-based Limited Preemptive Scheduling
2019 (English)In: IEEE Transactions on Industrial Informatics, ISSN 1551-3203, E-ISSN 1941-0050, Vol. 15, no 2, p. 1070-1081Article in journal (Refereed) Published
Abstract [en]

The increasing industrial demand for handling complex functionalities has influenced the design of hardware architectures for time critical embedded systems, during the past decade. Multi-core systems facilitate the inclusion of many complex functionalities, while, at the same time, inducing cache related overheads, as well as adding partitioning complexity to the overall system schedulability. One of the efficient paradigms for controlling and reducing the cache related costs in real-time systems is Limited Preemptive Scheduling (LPS), with its particular instance Fixed Preemption Points Scheduling (LP-FPPS), that has been shown to outperform other alternatives as well as has been supported by and investigated in the automotive domain. With respect to the partitioning constraints, Partitioned Scheduling has been widely used to pre-runtime allocate tasks to specific cores, resulting in a predictable cache-related preemption delays estimations. In this paper we propose to integrate LP-FPPS and Partitioned Scheduling on fixed-priority multicore real-time systems in order to increase the overall system schedulability.We define a new joint approach for task partitioning and preemption point selection, that is based on the computation of the maximum blocking tolerance upon each allocation, thus being able to quantify the schedulability of the taskset on each processor. Furthermore, we investigate partitioning strategies based on different heuristics, i.e. First Fit Decreasing and Worst Fit Decreasing, and priority and density taskset orderings. The evaluation performed on randomly generated tasksets shows that in the general case, no single partitioning strategy fully dominates the others. However, the evaluation results reveal that certain partitioning strategies perform significantly better with respect to the overall schedulability for specific taskset characteristics. The results also reveal that the proposed partitioning strategies outperform Fully Preemptive and Non-Preemptive partitioned scheduling in terms of successful partitioning.

Keywords
Real-Time Systems, Partitioned Scheduling, Limited Preemptive Scheduling, Fixed Preemption Points
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-39827 (URN)10.1109/TII.2018.2848879 (DOI)000458199000043 ()2-s2.0-85048607044 (Scopus ID)
Available from: 2018-06-14 Created: 2018-06-14 Last updated: 2019-02-28Bibliographically approved
Dobrin, R., Desai, N. & Punnekkat, S. (2019). On Fault-tolerant Scheduling of Time Sensitive Networks. In: 4th International Workshop on Security and Dependability of Critical Embedded Real-Time Systems CERTS 2019: . Paper presented at 4th International Workshop on Security and Dependability of Critical Embedded Real-Time Systems CERTS 2019, 09 Jul 2019, Stuttgart, Germany.
Open this publication in new window or tab >>On Fault-tolerant Scheduling of Time Sensitive Networks
2019 (English)In: 4th International Workshop on Security and Dependability of Critical Embedded Real-Time Systems CERTS 2019, 2019Conference paper, Published paper (Refereed)
Abstract [en]

Time sensitive networking (TSN) is gaining attention in industrial automation networks since it brings essential real-time capabilities at the data link layer. Though it can provide deterministic latency under error free conditions, TSN still largely depends on space redundancy for improved reliability.In many scenarios, time redundancy could be an adequate as well as cost efficient alternative. Time redundancy in turn will have implications due to the need for over-provisions needed for timeliness guarantees. In this paper, we discuss how to embed fault-tolerance capability into TSN schedules and describe our approach using a simple example.

Keywords
Time sensitive networks(TSN), Fault-tolerant schedule, Time redundancy
National Category
Engineering and Technology Computer Systems
Identifiers
urn:nbn:se:mdh:diva-43945 (URN)
Conference
4th International Workshop on Security and Dependability of Critical Embedded Real-Time Systems CERTS 2019, 09 Jul 2019, Stuttgart, Germany
Projects
FORA - Fog Computing for Robotics and Industrial Automation
Available from: 2019-06-20 Created: 2019-06-20 Last updated: 2019-06-20Bibliographically approved
Davis, R., Thekilakkattil, A., Gettings, O., Dobrin, R., Punnekkat, S. & Chen, J.-J. (2018). Exact Speedup Factors and Sub-Optimality for Non-Preemptive Scheduling. Real-time systems, 208-246
Open this publication in new window or tab >>Exact Speedup Factors and Sub-Optimality for Non-Preemptive Scheduling
Show others...
2018 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, p. 208-246Article in journal (Refereed) Published
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.

Keywords
real-time uniprocessor resource augmentation speedupfactor sub-optimality non-preemptive scheduling preemptive scheduling EDF xed priority
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-37337 (URN)10.1007/s11241-017-9294-3 (DOI)000419955500007 ()2-s2.0-85032335776 (Scopus ID)
Available from: 2017-11-28 Created: 2017-11-28 Last updated: 2018-01-26Bibliographically approved
Markovic, F., Carlson, J., Thekilakkattil, A., Dobrin, R. & Lisper, B. (2018). Probabilistic Response Time Analysis for Fixed Preemption Point Selection. In: 13th International Symposium on Industrial Embedded Systems SIES '18: . Paper presented at 13th International Symposium on Industrial Embedded Systems SIES '18, 06 Jun 2018, Graz, Austria. , Article ID 8442099.
Open this publication in new window or tab >>Probabilistic Response Time Analysis for Fixed Preemption Point Selection
Show others...
2018 (English)In: 13th International Symposium on Industrial Embedded Systems SIES '18, 2018, article id 8442099Conference paper, Published paper (Refereed)
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.

Keywords
Real-time systems, Limited Preemptive Scheduling, Fixed Preemption Points Scheduling, Probabilistic Response Time Analysis, Preemption Point Selection
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-39256 (URN)10.1109/SIES.2018.8442099 (DOI)2-s2.0-85053475648 (Scopus ID)9781538641552 (ISBN)
Conference
13th International Symposium on Industrial Embedded Systems SIES '18, 06 Jun 2018, Graz, Austria
Available from: 2018-05-23 Created: 2018-05-23 Last updated: 2018-09-27Bibliographically approved
Aravind, M., Wiklander, G., Palmheden, J. & Dobrin, R. (2017). An Event-Based Messaging Architecture for Vehicular Internet of Things (IoT) Platforms. In: Communications in Computer and Information Science, vol. 778: . Paper presented at 9th International Conference on Data-Driven Innovation, ICT Innovations 2017; Skopje; Macedonia; 18 September 2017 through 23 September 2017 (pp. 37-46). Springer Verlag
Open this publication in new window or tab >>An Event-Based Messaging Architecture for Vehicular Internet of Things (IoT) Platforms
2017 (English)In: Communications in Computer and Information Science, vol. 778, Springer Verlag , 2017, p. 37-46Conference paper, Published paper (Refereed)
Abstract [en]

Internet of Things (IoT) has revolutionized transportation systems by connecting vehicles consequently enabling their tracking, as well as monitoring of driver activities. Such an IoT platform requires a significant amount of data to be send from the on-board vehicle to the off-board servers, contributing to high network usage. The data can be send at regular intervals or in an event-based manner whenever relevant events occur. In interval-based approach, the data is send even if it is not relevant for reporting leading to a wastage of network resources, e.g., when the data does not change considerably compared to the previously sent value. In this paper, we investigate the possibility of using an event-based architecture to send data from the on-board system to the off-board system. The results show that our event-based architecture improves the accuracy of data available at the off-board system, by a careful selection of events. Moreover, we found that our event based architecture significantly decreases the frequency of sending messages, particularly during highway driving, leading to reduced average data transfer rates. Our results enable a customer to perform trade-offs between accuracy and data transfer rates. 

Place, publisher, year, edition, pages
Springer Verlag, 2017
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-36678 (URN)10.1007/978-3-319-67597-8_4 (DOI)2-s2.0-85029783908 (Scopus ID)9783319675961 (ISBN)
Conference
9th International Conference on Data-Driven Innovation, ICT Innovations 2017; Skopje; Macedonia; 18 September 2017 through 23 September 2017
Available from: 2017-10-06 Created: 2017-10-06 Last updated: 2018-01-03Bibliographically approved
Gutiérrez, M., Ademaj, A., Steiner, W., Dobrin, R. & Punnekkat, S. (2017). Self-Configuration of IEEE 802.1 TSN Networks. In: : . Paper presented at 22nd IEEE International Conference on Emerging Technologies And Factory Automation (ETFA, Limassol, CYPRUS, SEP 12-15, 2017. , Article ID F134116.
Open this publication in new window or tab >>Self-Configuration of IEEE 802.1 TSN Networks
Show others...
2017 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Configuration processes of real-time networks are costly both in terms of time and engineering effort and require the system to be shutdown during the reconfiguration phase thus resulting in significant down time as well. The convergence of IT/OT technologies is bringing a whole world of possibilities for the configuration and management of real-time networks for the automation industry. With software defined networking (SDN) features like the separation of the data and control plane and standards like IEEE 802.1 developed with the goal of adding deterministic capabilities to traditionally dynamic switched Ethernet networks, the plug and play paradigm is almost around the corner. In this paper, we go one step further and start looking into the self-configuration of real-time networks. To achieve that we propose to introduce a Configuration Agent in the network, an entity that continuously monitors the network to detect changes and automatically update the configuration to adapt to such changes while maintaining desired quality of service. We present here the complete framework for the Configuration Agent that will provide self-configuration capabilities to real-time networks. The proposed framework has IEEE 802.1 as its core, but also shows how the set of standards need to be extended in order to achieve the self-configuration requirements. Concretely we examine the role of existing communication protocols like NETCONF and OPC-UA and propose the essential ingredients (managed objects) for a YANG model for the learning aspects in the bridges, including different working modes.

Series
IEEE International Conference on Emerging Technologies and Factory Automation-ETFA
National Category
Embedded Systems
Identifiers
urn:nbn:se:mdh:diva-37100 (URN)10.1109/ETFA.2017.8247597 (DOI)000427812000032 ()2-s2.0-85044449708 (Scopus ID)9781509065059 (ISBN)
Conference
22nd IEEE International Conference on Emerging Technologies And Factory Automation (ETFA, Limassol, CYPRUS, SEP 12-15, 2017
Available from: 2017-10-19 Created: 2017-10-19 Last updated: 2019-06-25Bibliographically approved
Gutiérrez, M., Steiner, W., Dobrin, R. & Punnekkat, S. (2017). Synchronization quality of IEEE 802.1AS in large-scale industrial automation networks.. In: Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS: . Paper presented at 23rd IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2017, 18 April 2017 through 20 April 2017 (pp. 273-282). Institute of Electrical and Electronics Engineers Inc., Article ID 7939046.
Open this publication in new window or tab >>Synchronization quality of IEEE 802.1AS in large-scale industrial automation networks.
2017 (English)In: Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS, Institute of Electrical and Electronics Engineers Inc. , 2017, p. 273-282, article id 7939046Conference paper, Published paper (Refereed)
Abstract [en]

Industry 4.0 and Industrial Internet of Things projects work towards adoption of standard IT technologies for real-time control networks in industrial automation. For this the IEEE 802.1 Time-Sensitive Networking (TSN) Task Group has developed and continues to develop a set of standards. One of these standards is the IEEE 802.1AS clock synchronization protocol. IEEE 802.1AS can be used to enable time-triggered communication as well as to coordinate distributed actions in industrial networks. In this paper we study the synchronization quality of IEEE 802.1AS and we are interested in whether the clocks can be synchronized with sufficiently low error such that the protocol can be used for demanding industrial automation applications. In particular, we study the protocol behavior in large-scale networks while considering critical implementation details. We report analytical worst-case results as well as probabilistic results based on simulations, that show that implementation details such as the PHY jitter and the clock granularity have a big impact on the time synchronization precision. 

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc., 2017
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-36142 (URN)10.1109/RTAS.2017.10 (DOI)000411195100031 ()2-s2.0-85021821793 (Scopus ID)9781509052691 (ISBN)
Conference
23rd IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2017, 18 April 2017 through 20 April 2017
Available from: 2017-07-27 Created: 2017-07-27 Last updated: 2017-10-27Bibliographically approved
Markovic, F., Carlson, J. & Dobrin, R. (2017). Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling. In: OpenAccess Series in Informatics: . Paper presented at 17th International Workshop on Worst-Case Execution Time Analysis WCET 2017, 27 Jun 2017, Dubrovnik, Croatia (pp. 41-411). , 57
Open this publication in new window or tab >>Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling
2017 (English)In: OpenAccess Series in Informatics, 2017, Vol. 57, p. 41-411Conference paper, Published paper (Refereed)
Abstract [en]

Limited Preemptive Fixed Preemption Point scheduling (LP-FPP) has the ability to decrease and control the preemption-related overheads in the real-time task systems, compared to other limited or fully preemptive scheduling approaches. However, existing methods for computing the preemption overheads in LP-FPP systems rely on over-approximation of the evicting cache blocks (ECB) calculations, potentially leading to pessimistic schedulability analysis. In this paper, we propose a novel method for preemption cost calculation that exploits the benefits of the LP-FPP task model both at the scheduling and cache analysis level. The method identifies certain infeasible preemption combinations, based on analysis on the scheduling level, and combines it with cache analysis information into a constraint problem from which less pessimistic upper bounds on cache-related preemption delays (CRPD) can be derived. The evaluation results indicate that our proposed method has the potential to significantly reduce the upper bound on CRPD, by up to 50% in our experiments, compared to the existing over-approximating calculations of the eviction scenarios.

Keywords
Real-time systems, CRPD Analysis, WCET analysis, Limited Preemptive Scheduling, Fixed Preemption Point Approach
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-37013 (URN)10.4230/OASIcs.WCET.2017.4 (DOI)2-s2.0-85037724726 (Scopus ID)9783959770576 (ISBN)
Conference
17th International Workshop on Worst-Case Execution Time Analysis WCET 2017, 27 Jun 2017, Dubrovnik, Croatia
Available from: 2017-11-27 Created: 2017-11-27 Last updated: 2018-06-14Bibliographically approved
Thekkilakattil, A., Zhu, K., Nie, Y., Dobrin, R. & Punnekkat, S. (2016). An empirical investigation of eager and lazy preemption approaches in global limited preemptive scheduling. In: Lecture Notes in Computer Science: . Paper presented at 13 June 2016 through 17 June 2016 (pp. 163-178). Springer
Open this publication in new window or tab >>An empirical investigation of eager and lazy preemption approaches in global limited preemptive scheduling
Show others...
2016 (English)In: Lecture Notes in Computer Science, Springer, 2016, p. 163-178Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
Springer, 2016
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9695
Keywords
Multiprocessing systems, Real time systems, Response time (computer systems), Earliest deadline first, Empirical - comparisons, Empirical investigation, Fixed priority scheduling, Multi processor systems, Pre-emptive scheduler, Pre-emptive scheduling, Real - time scheduling, Scheduling
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:mdh:diva-32413 (URN)10.1007/978-3-319-39083-3_11 (DOI)000386324400011 ()2-s2.0-84977508721 (Scopus ID)9783319390826 (ISBN)
Conference
13 June 2016 through 17 June 2016
Available from: 2016-07-28 Created: 2016-07-28 Last updated: 2018-01-10Bibliographically approved
Shah, M. B., Husain, A. R., Aysan, H., Punnekkat, S., Dobrin, R. & Bender, F. A. (2016). Error Handling Algorithm and Probabilistic Analysis Under Fault for CAN-Based Steer-by-Wire System. IEEE Transactions on Industrial Informatics, 12(3), 1017-1034, Article ID 7435293.
Open this publication in new window or tab >>Error Handling Algorithm and Probabilistic Analysis Under Fault for CAN-Based Steer-by-Wire System
Show others...
2016 (English)In: IEEE Transactions on Industrial Informatics, ISSN 1551-3203, E-ISSN 1941-0050, Vol. 12, no 3, p. 1017-1034, article id 7435293Article in journal (Refereed) Published
Abstract [en]

This paper proposes an efficient way to handle fault in controller area network (CAN)-based networked control system (NCS). A fault in a bus line of CAN will induce a data error which will result in data dropout or time delay, and subsequently may lead to performance degradation or system instability. A strategy to handle fault occurrence in CAN bus is proposed to properly analyze the effect of the fault to CAN-based NCS performance. The fault occurrences are modeled based on fault interarrival time, fault bursts' duration, and Poisson law. Using fault and messages' attributes, response time analysis (RTA) is performed and the probability of control message missing its deadline is calculated. Utilizing the new error handling algorithm to replace the native error handling of CAN, the probability of a control message missing its deadline can be translated into the probability of data dropout for control message. This methodology is evaluated using steer-by-wire system of vehicle to analyze the effect of fault occurrences in CAN. It is found that the proposed error handling mechanism has resulted in better NCS performance and the range of data dropout probability for control message also could be obtained, which serves as crucial input for NCS controller design.

Keywords
Controller area network (CAN), data error handling, fault model, networked control system (NCS), probabilistic schedulability analysis, steer-by-wire (SbW) system, Algorithms, Control system analysis, Control system synthesis, Control systems, Data handling, Delay control systems, Errors, Networked control systems, Probability, Process control, System stability, Time delay, Wire, Controller area network, Data errors, Schedulability analysis, Steer-by-wire, Controllers
National Category
Computer Engineering
Identifiers
urn:nbn:se:mdh:diva-32382 (URN)10.1109/TII.2016.2543232 (DOI)000378530300013 ()2-s2.0-84976295515 (Scopus ID)
Available from: 2016-07-14 Created: 2016-07-14 Last updated: 2018-01-10Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-4157-3537

Search in DiVA

Show all publications