https://www.mdu.se/

mdu.sePublications
Change search
Refine search result
12 1 - 50 of 78
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Afshar, Sara
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Bril, R. J.
    Technische Universiteit Eindhoven, Eindhoven, Netherlands .
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Flexible spin-lock model for resource sharing in multiprocessor real-time systems2014In: Proc. IEEE Int. Symp. Ind. Embedded Syst., SIES, 2014, p. 41-51Conference paper (Refereed)
    Abstract [en]

    Various approaches can be utilized upon resource locking for mutually exclusive resource access in multiprocessor platforms. So far two conventional approaches exist for dealing with tasks that are blocked on a global resource in a multi-processor platform. Either the blocked task performs a busy wait, i.e. spins, at the highest priority level until the resource is released, or it is suspended. Although both approaches provide mutually exclusive access to resources, they can introduce long blocking delays to tasks, which may be unacceptable for many industrial applications. In this paper, we propose a general spin-based model for resource sharing in multiprocessor platforms in which the priority of the blocked tasks during spinning can be selected arbitrarily. Moreover, we provide the analysis for two selected spin-lock priorities and we show by means of a general comparison as well as specific examples that these solutions may provide a better performance for higher priority tasks.

  • 2.
    Afshar, Sara
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Bril, Reinder J.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Resource sharing in a hybrid partitioned/global scheduling framework for multiprocessors2015In: IEEE International Conference on Emerging Technologies and Factory Automation, ETFA, 2015Conference paper (Refereed)
    Abstract [en]

    For resource-constrained embedded real-time systems, resource-efficient approaches are very important. Such an approach is presented in this paper, targeting systems where a critical application is partitioned on a multi-core platform and the remaining capacity on each core is provided to a noncritical application using resource reservation techniques. To exploit the potential parallelism of the non-critical application, global scheduling is used for its constituent tasks. Previously, we enabled intra-application resource sharing for such a framework, i.e. each application has its own dedicated set of resources. In this paper, we enable inter-application resource sharing, in particular between the critical application and the non-critical application. This effectively enables resource sharing in a hybrid partitioned/global scheduling framework on multiprocessors. For resource sharing, we use a spin-based synchronization protocol. We derive blocking bounds and extend existing schedulability analysis for such a system.

  • 3.
    Afshar, Sara
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Bril, Reinder J.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Technische Universiteit Eindhoven, Eindhoven, Netherlands.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Resource Sharing Under Global Scheduling with Partial Processor Bandwidth2015In: 2015 10th IEEE International Symposium on Industrial Embedded Systems, SIES 2015 - Proceedings, 2015, p. 195-206Conference paper (Refereed)
    Abstract [en]

    Resource efficient approaches are of great importance for resource constrained embedded systems. In this paper, we present an approach targeting systems where tasks of a critical application are partitioned on a multi-core platform and by using resource reservation techniques, the remaining bandwidth capacity on each core is utilized for one or a set of non-critical application(s). To provide a resource efficient solution and to exploit the potential parallelism of the extra applications on the multi-core processor, global scheduling is used to schedule the tasks of the non-critical applications. Recently a specific instantiation of such a system has been studied where tasks do not share resources other than the processor. In this paper, we enable semaphore-based resource sharing among tasks within critical and non-critical applications using a suspension-based synchronization protocol. Tasks of non-critical applications have partial access to the processor bandwidth. The paper provides the systems schedulability analysis where blocking due to resource sharing is bounded. Further, we perform experimental evaluations under balanced and unbalanced allocation of tasks of a critical application to cores.

  • 4.
    Afshar, Sara
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    J. Bril, Reinder
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Per Processor Spin-Lock Priority for Partitioned Multiprocessor Real-Time Systems2014Report (Other academic)
    Abstract [en]

    Two traditional approaches exist for a task that is blocked on a global resource; a task either performs a non-preemptive busy wait, i.e., spins, or suspends and releases the processor. Previously, we have shown that both approaches can be viewed as spinning either at the highest priority HP or at the lowest priority on the processor LP, respectively. Based on this view, previously we have generalized a task's blocking behavioral model, as spinning at any arbitrary priority level. In this paper, we focus on a particular class of spin-lock protocols from the introduced flexible spin-lock model where spinning is performed at a priority equal to or higher than the highest local ceiling of the global resources accessed on a processor referred to as CP spin-lock approach. In this paper, we assume that all tasks of a specific processor are spinning on the same priority level. Given this class and assumption, we show that there exists a spin-lock protocol in this range that dominates the classic spin-lock protocol which tasks spin on highest priority level (HP). However we show that this new approach is incomparable with the CP spin-lock approach. Moreover, we show that there may exist an intermediate spin-lock approach between the priority used by CP spin-lock approach and the new introduced spin-lock approach that can make a task set schedulable when those two cannot. We provide an extensive evaluation results comparing the HP, CP and the new proposed approach.

  • 5.
    Afshar, Sara
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    J. Bril, Reinder
    Technische Universiteit Eindhoven, Eindhoven, The Netherlands.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Per Processor Spin-Lock Priority for Partitioned Multiprocessor Real-Time Systems2017In: Leibniz Transactions on Embedded Systems, ISSN 2199-2002, no 2Article in journal (Other academic)
    Abstract [en]

    Two traditional approaches exist for a task that is blocked on a global resource; a task either performs a non-preemptive busy wait, i.e., spins, or suspends and releases the processor. Previously, we have shown that both approaches can be viewed as spinning either at the highest priority HP or at the lowest priority on the processor LP, respectively. Based on this view, previously we have generalized a task's blocking behavioral model, as spinning at any arbitrary priority level. In this paper, we focus on a particular class of spin-lock protocols from the introduced flexible spin-lock model where spinning is performed at a priority equal to or higher than the highest local ceiling of the global resources accessed on a processor referred to as CP spin-lock approach. In this paper, we assume that all tasks of a specific processor are spinning on the same priority level. Given this class and assumption, we show that there exists a spin-lock protocol in this range that dominates the classic spin-lock protocol which tasks spin on highest priority level (HP). However we show that this new approach is incomparable with the CP spin-lock approach. Moreover, we show that there may exist an intermediate spin-lock approach between the priority used by CP spin-lock approach and the new introduced spin-lock approach that can make a task set schedulable when those two cannot. We provide an extensive evaluation results comparing the HP, CP and the new proposed approach.

  • 6.
    Afshar, Sara
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Khalilzad, Nima
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Bril, Reinder J.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Universiteit Eindhoven, Eindhoven, Netherlands.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Intra-component Resource Sharing on a Virtual Multiprocessor Platform2016In: ACM SIGBED Review: Special Issue on 8th International Workshop on Compositional Theory and Technology for Real-Time Embedded Systems, 2016, p. 31-32Conference paper (Refereed)
    Abstract [en]

    Component-based software development facilitates the development process of large and complex software systems. By the advent of multiprocessors, the independently developed components can be integrated on a multi-core platform to achieve an efficient use of system hardware and a decrease in system power consumption and costs. In this paper, we consider a virtual multiprocessor platform where each component can be dynamically allocated to any set of processors of the platform with a maximum concurrency level. Global-EDF is used for intra-component scheduling. The existing analysis for such systems have assumed that tasks are independent. In this paper, we enable intra-component resource sharing for this platform. We investigate using a spin-based resource sharing protocol with the accompanying analysis that extends the existing analysis for independent tasks. We briefly illustrate and evaluate our initial results with an example.

  • 7.
    Afshar, Sara Zargari
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    J. Bril, Reinder
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Technische Universiteit Eindhoven, Eindhoven, Netherlands.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    An optimal spin-lock priority assignment algorithm for real-time multi-core systems2017In: The 23th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA'17, 2017, article id 8046310Conference paper (Refereed)
    Abstract [en]

    Support for exclusive access to shared (global) resources is instrumental in the context of embedded real-time multi-core systems, and mechanisms for achieving such access must be deterministic and efficient. There exist two traditional approaches for multiprocessors when a task requests a global resource that is locked by a task on a remote core: a spin-based approach, i.e. non-preemptive busy waiting for the resource to become available, and a suspension-based approach, i.e. the task relinquishes the processor. A suspension-based approach can be viewed as a spin-based approach where the lowest priority on a core is used during spinning, similar to a non-preemptive spin-based approach where the highest priority on a core is used. By taking such a view, we previously provided a general model for spinning, where any arbitrary priority can be used for spinning, i.e. from the lowest to the highest priority on a core. Targeting partitioned fixed-priority preemptive scheduled multiprocessors and spin-based approaches that use a fixed priority for spinning per core for all tasks, we aim at increasing the schedulability of multiprocessor systems by using the spin-lock priority per core as parameter. In this paper, we present (i) a generalization of the traditional worst-case response-time analysis for non-preemptive spin-based approaches addressing an arbitrary but fixed spin-lock priority per core, (ii) an optimal spin-lock priority assignment (OSPA) algorithm per core, i.e. an algorithm that will find a fixed spin-lock priority per core that will make the system schedulable, whenever such an assignment exists and, (iii) comparative evaluations of the OSPA algorithm with the spin-based and suspension-based approaches where OSPA showed up to 38% improvement compared to both approaches.

  • 8.
    Ashjaei, Mohammad
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Pedreiras, Paulo
    University of Aveiro, Portugal.
    Bril, Reinder J.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Almeida, Luis
    University of Porto, Portugal.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Reduced Buffering Solution for Multi-Hop HaRTES Switched Ethernet Networks2014In: The 20th IEEE International Conference on embedded and Real-Time Computing Systems and Applications RTCSA'14, 2014, p. Article number 6910504-Conference paper (Refereed)
    Abstract [en]

    In the context of switched Ethernet networks, multi-hop communication is essential as the networks in industrial applications comprise a high amount of nodes, that is far beyond the capability of a single switch. In this paper, we focus on multi-hop communication using HaRTES switches. The HaRTES switch is a modified Ethernet switch that provides real-time traffic scheduling, dynamic Quality-of-Service and temporal isolation between real-time and non-real-time traffic. Herein, we propose a method, called Reduced Buffering Scheme, to conduct the traffic through multiple HaRTES switches in a multi-hop HaRTES architecture. In order to enable the new scheduling method we propose to modify the HaRTES switch structure. Moreover, we develop a response time analysis for the new method. We also compare the proposed method with a method previously proposed, called Distributed Global Scheduling, based on their traffic response times. We show that, the new method forwards all types of traffic including the highest, the medium and the lowest priority, faster than the previous method in most of the cases. Furthermore, we show that the new method performs even better for larger networks compared with the previous one.

  • 9.
    Ashjaei, Mohammad
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Pedreiras, P.
    DETI/IT, University of Aveiro, Aveiro, Portugal .
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Bril, Reinder J.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Technische Universiteit Eindhoven (TU/e), Netherlands .
    Almeida, L.
    Technische Universiteit Eindhoven (TU/e), Netherlands .
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Response time analysis of multi-hop HaRTES Ethernet Switch networks2014In: IEEE Int. Workshop Factory Commun. Syst. Proc. WFCS, 2014Conference paper (Refereed)
    Abstract [en]

    In this paper we focus on micro-segmented switched-Ethernet networks with HaRTES switches. HaRTES switches provide synchronous and asynchronous real-time traffic scheduling, dynamic Quality-of-Service adaptation and transparent integration of real-time and non-real-time nodes. Herein we investigate the challenges of connecting multiple HaRTES switches in order to build multi-hop communication and we propose a method, named Distributed Global Scheduling, to handle the traffic forwarding in such an architecture while preserving the unique properties of the single HaRTES switch case. Moreover, we develop a response time analysis for the method. We also evaluate the level of pessimism embodied in the anal-ysis. Finally, we show the applicability of the proposed method in an industrial setting by applying it in an automotive case study.

  • 10.
    Ashjaei, Mohammad
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. MRTC Malardalen Univ, Vasteras, Sweden..
    Silva, Luis
    DETI IT Univ Aveiro, Aveiro, Portugal..
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. MRTC Malardalen Univ, Vasteras, Sweden..
    Pedreiras, Paulo
    DETI IT Univ Aveiro, Aveiro, Portugal..
    Bril, Reinder J.
    Tech Univ Eindhoven TU E, Eindhoven, Netherlands..
    Almeida, Luis
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. MRTC Malardalen Univ, Vasteras, Sweden.;IT DEEC Univ Porto, Oporto, Portugal..
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. MRTC Malardalen Univ, Vasteras, Sweden..
    Improved Message Forwarding for Multi-Hop HaRTES Real-Time Ethernet Networks2016In: Journal of Signal Processing Systems, ISSN 1939-8018, E-ISSN 1939-8115, Vol. 84, no 1, p. 47-67Article in journal (Refereed)
    Abstract [en]

    Nowadays, switched Ethernet networks are used in complex systems that encompass tens to hundreds of nodes and thousands of signals. Such scenarios require multi-switch architectures where communications frequently occur in multiple hops. In this paper we investigate techniques to allow efficient multi-hop communication using HaRTES switches. These are modified Ethernet switches that provide real-time traffic scheduling, dynamic bandwidth management and temporal isolation between real-time and non-real-time traffic. This paper addresses the problem of forwarding traffic in HaRTES networks. Two methods have been recently proposed, namely Distributed Global Scheduling (DGS) that buffers traffic between switches, and Reduced Buffering Scheme (RBS), that uses immediate forwarding. In this paper, we discuss the design and implementation of RBS within HaRTES and we carry out an experimental validation with a prototype implementation. Then, we carry out a comparison between RBS and DGS using worst-case response time analysis and simulation. The comparison clearly establishes the superiority of RBS concerning end-to-end response times. In fact, with sample message sets, we achieved reductions in end-to-end delay that were as high as 80 %.

  • 11.
    Balasubramanian, S. M. N.
    et al.
    Technische Universiteit Eindhoven, Eindhoven, Netherlands.
    Afshar, Sara
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Gai, P.
    Evidence Srl, Pisa, Italy.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    J. Bril, Reinder
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Practical challenges for FSLM2018In: Proceedings - 2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2018, Institute of Electrical and Electronics Engineers Inc. , 2018, p. 238-239, article id 8607257Conference paper (Refereed)
    Abstract [en]

    The flexible spin-lock model (FSLM) unifies suspension-based and spin-based resource access protocols for partitioned fixed-priority preemptive scheduling based real-time multi-core platforms. Recent work has been done in defining the protocol for FSLM, providing schedulability analysis, and investigating the practical consequences of the theoretical model. FSLM complies to the AUTOSAR standard for the automotive industry, and prototype implementations of FSLM in the OSEK/VDX-complaint Erika Enterprise Real-Time Operating System have been realized. In this paper, we briefly describe some practical challenges to improve efficiency and generality. 

  • 12.
    Balasubramanian, S.M.N
    et al.
    Technische Universiteit Eindhoven, Eindhoven, The Netherlands.
    Afshar, Sara Zargari
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Gai, Paolo
    Evidence Srl, Pisa, Italy.
    Bril, Reinder J.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Technische Universiteit Eindhoven, Eindhoven, The Netherlands.
    A dual shared stack for FSLM in Erika enterprise2017In: The 23rd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications - WiP Session RTCSA'17, 2017Conference paper (Refereed)
    Abstract [en]

    Recently, the flexible spin-lock model (FSLM) has been introduced, unifying spin-based and suspension-based resource sharing protocols for real-time multi-core platforms. Unlike the multiprocessor stack resource policy (MSRP), FSLM doesn’t allow tasks on a core to share a single stack, however. In this paper, we present a hypothesis claiming that for a restricted range of spin-lock priorities, FSLM requires only two stacks. We briefly describe our implementation of a dual stack for FSLM in the Erika Enterprise RTOS as instantiated on an Altera Nios II platform using 4 soft-core processors.

  • 13.
    Balasubramanian, S.M.N
    et al.
    Tech Univ Eindhoven, Eindhoven, Netherlands.
    Afshar, Sara Zargari
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Gai, Paolo
    Evidence Srl, Pisa, Italy.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    J. Bril, Reinder
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Tech Univ Eindhoven, Eindhoven, Netherlands.
    Incorporating implementation overheads in the analysis for the flexible spin-lock model2017In: IECON 2017 - 43RD ANNUAL CONFERENCE OF THE IEEE INDUSTRIAL ELECTRONICS SOCIETY, 2017, p. 411-8418Conference paper (Refereed)
    Abstract [en]

    The flexible spin-lock model (FSLM) unifies suspension-based and spin-based resource sharing protocols for partitioned fixed-priority preemptive scheduling based real-time multiprocessor platforms. Recent work has been done in defining the protocol for FSLM and providing a schedulability analysis without accounting for the implementation overheads. In this paper, we extend the analysis for FSLM with implementation overheads. Utilizing an initial implementation of FSLM in the OSEK/VDX-compliant Erika Enterprise RTOS on an Altera Nios II platform using 4 soft-core processors, we present an improved implementation. Given the design of the implementation, the overheads are characterized and incorporated in specific terms of the existing analysis. The paper also supplements the analysis with measurement results, enabling an analytical comparison of FSLM with the natively provided multiprocessor stack resource policy (MSRP), which may serve as a guideline for the choice of FSLM or MSRP for a specific application.

  • 14. Batsuuri, Tseesuren
    et al.
    Bril, Reinder J.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lukkien, Johan
    Model, analysis, and improvements for V2V communication based on 802.11p2012Conference paper (Refereed)
  • 15.
    Batsuuri, Tseesuren
    et al.
    Eindhoven University of Technology, Eindhoven, Netherlands .
    Bril, Reinder J.
    Eindhoven University of Technology, Eindhoven, Netherlands .
    Lukkien, Johan
    Eindhoven University of Technology, Eindhoven, Netherlands .
    Performance and Fairness in VANETs2011In: Digest of Technical Papers - IEEE International Conference on Consumer Electronics, 2011, p. 637-638Conference paper (Refereed)
  • 16.
    Becker, Matthias
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Khalilzad, Nima
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Bril, Reinder J.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Technische Universiteit Eindhoven, Eindhoven, Netherlands.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Extended support for limited preemption fixed priority scheduling for OSEK/AUTOSAR-compliant operating systems2015In: 2015 10th IEEE International Symposium on Industrial Embedded Systems, SIES 2015 - Proceedings, 2015, p. 207-217Conference paper (Refereed)
    Abstract [en]

    Fixed Priority Scheduling (FPS) is the de facto standard in industry and it is the scheduling algorithm used in OSEK/AUTOSAR. Applications in such systems are compositions of so called runnables, the functional entities of the system. Runnables are mapped to operating system tasks during system synthesis. In order to improve system performance it is proposed to execute runnables non-preemptively while varying the tasks threshold between runnables. This allows simpler resource access, can reduce the stack usage of the system, and improve the schedulability of the task sets. FPDS , as a special case of fixed-priority scheduling with deferred preemptions, executes subjobs non-preemptively and preemption points have preemption thresholds, providing exactly the proposed behavior. However OSEK/AUTOSAR-conform systems cannot execute such schedules. In this paper we present an approach allowing the execution of FPDS schedules. In our approach we exploit pseudo resources in order to implement FPDS . It is further shown that our optimal algorithm produces a minimum number of resource accesses. In addition, a simulation based evaluation is presented in which the number of resource accesses as well as the number of required pseudo-resources by the proposed algorithms are investigated. Finally, we report the overhead of resource access primitives using our measurements performed on an AUTOSARcompliant operating system.

  • 17.
    Behnam, Moris
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Bril, Reinder
    Eindhoven University of Technology, The Netherlands.
    Bounding the number of self-blocking occurrences of SIRAP2010In: Proceedings - Real-Time Systems Symposium, 2010, p. 61-72Conference paper (Refereed)
    Abstract [en]

    This paper presents a new schedulability analysis for hierarchically scheduled real-time systems executing on a single processor using SIRAP; a synchronization protocol for inter subsystem task synchronization. We show that it is possible to bound the number of self-blocking occurrences that should be taken into consideration in the schedulability analysis of subsystems. Correspondingly, we present two novel schedulability analysis approaches with proof of correctness for SIRAP. An evaluation suggests that this new schedulability analysis can decrease the analytical subsystem utilization significantly

  • 18.
    Behnam, Moris
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Bril, Reinder
    Eindhoven University of Technology, The Netherlands.
    Refining SIRAP with a Dedicated Resource Ceiling for Self-Blocking2009In: 9th ACM & IEEE International Conference on Embedded Software, 2009, p. 157-166Conference paper (Refereed)
  • 19.
    Behnam, Moris
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Bril, Reinder
    Eindhoven University of Technology, The Netherlands.
    Schedulability analysis of synchronization protocols based on overrun without payback for hierarchical scheduling frameworks revisited2010Report (Other academic)
    Abstract [en]

    In this paper, we show that both global as well as local schedulability analysis of synchronization protocols based on the stack resource protocol (SRP) and overrun without payback for hierarchical scheduling frameworks based on fixed-priority pre-emptive scheduling (FPPS) are pessimistic.We present improved global and local schedulability analysis,illustrate the improvements by means of examples, and show that the improved global analysis is both uniform and sustainable.We evaluate the improved global and local schedulabilityanalysis based on an extensive simulation study and comparethe results with the existing analysis.

  • 20.
    Behnam, Moris
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    J. Bril, Reinder
    Mälardalen University, School of Innovation, Design and Engineering.
    A new approach for global synchronization in hierarchical scheduled real-time systems2009In: Work-in-Progress (WiP) session of the 21st Euromicro Conference on Real-Time Systems (ECRTS'09), 2009Conference paper (Refereed)
  • 21.
    Behnam, Moris
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    J. Bril, Reinder
    Technische Universiteit Eindhoven.
    Improved SIRAP analysis for synchronization in hierarchical scheduled real-time systems2009In: Proceedings of 14th IEEE International Conference on Emerging Techonologies and Factory (ETFA'09), 2009Conference paper (Refereed)
    Abstract [en]

    We present our ongoing work on synchronization in hierarchical scheduled real-time systems, where tasks are scheduled using fixed-priority pre-emptive scheduling. In this paper, we show that the original local schedulability analysis of the synchronization protocol SIRAP is very pessimistic when tasks of a subsystem access many global shared resources. The analysis therefore suggests that a subsystem requires more CPU resources than necessary. A new way to perform the schedulability analysis is presented which can make the SIRAP protocol more efficient in terms of calculated CPU resource needs.

  • 22.
    Behnam, Moris
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    J. Bril, Reinder
    Technische Universiteit Eindhoven.
    Tighter Schedulability Analysis of Synchronization Protocols Based on Overrun Without Payback for Hierarchical Scheduling Frameworks2011In: 16th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS'11), Los Alamitos: IEEE Computer Society, 2011, p. 35-44Conference paper (Refereed)
  • 23.
    Behnam, Moris
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Shin, Insik
    Åsberg, Mikael
    Mälardalen University, School of Innovation, Design and Engineering.
    Bril, Reinder
    Technische Universiteit Eindhoven.
    Towards Hierarchical Scheduling in VxWorks2008In: OSPERT 2008, Proceedings of the Fourth International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, 2008, p. 63-72Conference paper (Refereed)
    Abstract [en]

    Over the years, we have worked on hierarchical schedulingframeworks from a theoretical point of view. In thispaper we present our initial results of the implementationof our hierarchical scheduling framework in a commercialoperating system VxWorks. The purpose of the implementationis twofold: (1) we would like to demonstrate feasibilityof its implementation in a commercial operating system,without having to modify the kernel source code, and (2) wewould like to present detailed figures of various key propertieswith respect to the overhead of the implementation.During the implementation of the hierarchical scheduler,we have also developed a number of simple task schedulers.We present details of the implementation of Rate-Monotonic(RM) and Earliest Deadline First (EDF) schedulers. Finally,we present the design of our hierarchical schedulingframework, and we discuss our current status in the project.

    Download full text (pdf)
    fulltext
  • 24.
    Behnam, Moris
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Åsberg, Mikael
    Mälardalen University, School of Innovation, Design and Engineering.
    Bril, Reinder
    Eindhoven University of Technology, The Netherlands.
    Overrun and Skipping in Hierarchically Scheduled Real-Time Systems2009In: 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2009, p. 519-526Conference paper (Refereed)
  • 25.
    Bergsma, Mark
    et al.
    Technische Universiteit Eindhoven.
    Holenderski, Mike J.
    Technische Universiteit Eindhoven.
    Bril, Reinder J.
    Technische Universiteit Eindhoven.
    Lukkien, Johan
    Technische Universiteit Eindhoven.
    Extending RTAI/Linux with Fixed-Priority Scheduling with Deferred Preemption2009In: 5th OSPERT OSPERT'09, 2009, p. 5-14Conference paper (Refereed)
  • 26.
    Bril, Reinder J.
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Technische Universiteit Eindhoven (TU/e), Netherlands.
    Altmeyer, Sebastian
    University of Amsterdam (UvA), The Netherlands.
    van den Heuvel, Martijn
    Technische Universiteit Eindhoven (TU/e), Netherlands.
    Davis, Rob
    University of York, UK.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Integrating Cache-Related Pre-emption Delays into Analysis of Fixed Priority Scheduling with Pre-emption Thresholds2015In: Proceedings - Real-Time Systems Symposium, 2015, Vol. January, p. 161-172Conference paper (Refereed)
    Abstract [en]

    Cache-related pre-emption delays (CRPD) have been integrated into the schedulability analysis of sporadic tasks with constrained deadlines for fixed-priority pre-emptive scheduling (FPPS). This paper generalizes that work by integrating CRPD into the schedulability analysis of tasks with arbitrary deadlines for fixed-priority pre-emption threshold scheduling (FPTS). The analysis is complemented by an optimal threshold assignment algorithm that minimizes CRPD. The paper includes a comparative evaluation of the schedulability ratios of FPPS and FPTS, for constrained-deadline tasks, taking CRPD into account.

  • 27.
    Bril, Reinder J.
    et al.
    Technische Universiteit, Eindhoven, The Netherlands.
    Lukkien, Johan
    Technische Universiteit, Eindhoven, The Netherlands.
    Mak, Rudolf H.
    Technische Universiteit, Eindhoven, The Netherlands.
    Best-case response times and jitter analysis of real-time tasks with arbitrary deadlines2013In: RTNS '13 Proceedings of the 21st International conference on Real-Time Networks and Systems, Sophia Antipolis, France, 2013, p. 193-202Conference paper (Refereed)
    Abstract [en]

    In this paper, we present and prove exact best-case response time and improved jitter analysis of real-time periodic tasks with activation jitter and arbitrary deadlines that are scheduled by means of fixed-priority pre-emptive scheduling. We illustrate the analysis by means of examples.

    Apart from having a value on its own whenever timing constraints include lower bounds on response times of a system to events, our novel analysis also allows for an improvement of existing end-to-end response time analysis in distributed systems, i.e. where the finalization of one task on a processor activates another task on another processor.

    Best-case and worst-case analysis for tasks with constrained deadlines have a dual nature. We present various witnesses of non-duality of best-case and worst-case analysis for tasks with arbitrary deadlines, illustrating that both our novel best-case analysis and its proof are not straightforward extensions of existing work.

  • 28.
    Bril, Reinder J.
    et al.
    Technische Universiteit Eindhoven, Netherlands .
    Lukkien, Johan
    Technische Universiteit Eindhoven, Netherlands .
    Verhaegh, Wim F.J.
    Philips Research Laboratories, Netherlands .
    Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption2009In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 42, no 1-3, p. 63-119Article in journal (Refereed)
    Abstract [en]

    Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority pre-emptive scheduling (FPPS), that obviates the need for non-trivial resource access protocols and reduces the cost of arbitrary preemptions. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is pessimistic and/or optimistic. The same problem also arises for fixed-priority non-pre-emptive scheduling (FPNS), being a special case of FPDS. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis is based on known concepts of critical instant and busy period for FPPS. To accommodate for our scheduling model for FPDS, we need to slightly modify existing definitions of these concepts. The analysis assumes a continuous scheduling model, which is based on a partitioning of the timeline in a set of non-empty, right semi-open intervals. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Hence, that instant, period, and response time cannot be assumed for any task, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks. These anomalies for the lowest priority task are an immediate consequence of the fact that only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks, illustrates the revised analysis for an advanced model for FPDS, where tasks are structured as flow graphs of subjobs rather than sequences, and shows that our analysis is sustainable.

  • 29.
    Bril, Reinder J.
    et al.
    Technische Universiteit Eindhoven, Netherlands .
    van den Heuvel, Martijn
    Technische Universiteit Eindhoven, Netherlands .
    Keskin, Ugur
    Technische Universiteit Eindhoven, Netherlands .
    Lukkien, Johan
    Generalized fixed-priority scheduling with limited preemptions2012In: Proceedings - Euromicro Conference on Real-Time Systems, 2012, 2012, p. 209-220Conference paper (Refereed)
    Abstract [en]

    Fixed-priority scheduling with deferred preemption(FPDS) and fixed-priority scheduling with preemption thresholds(FPTS) have been proposed in the literature as viable alternatives to fixed-priority preemptive scheduling (FPPS), that reduce memory requirements, reduce the cost of arbitrary preemptions, and may improve the feasibility of a task set even when preemption overheads are neglected. This paper aims at advancing the relative strength of limited preemptive schedulers by combining FPDS and FPTS. In particular, we present a refinement of FPDS with preemption thresholds for both jobs and sub-jobs, termed FPGS. We provide an exact schedulability analysis for FPGS, and show how to maximize the feasibility of a set of sporadic tasks under FPGS for given priorities, computation times, periods, and deadlines of tasks. We evaluate the effectiveness of FPGS by comparing the feasibility of task sets under FPGS with other fixed-priority scheduling algorithms by means of a simulation. Our experiments show that FPGS allows an increase of the number of task sets that are schedulable under fixed-priority scheduling.

  • 30.
    Bril, Reinder J.
    et al.
    Technische Universiteit, The Netherlands.
    van den Heuvel, Martijn
    Technische Universiteit, The Netherlands.
    Lukkien, Johan
    Technische Universiteit, The Netherlands.
    Improved feasibility of fixed-priority scheduling with deferred preemption using preemption thresholds for preemption points2013In: RTNS '13 Proceedings of the 21st International conference on Real-Time Networks and Systems, 2013, p. 255-264Conference paper (Refereed)
    Abstract [en]

    This paper aims at advancing the relative strength of limited-preemptive schedulers by improving the feasibility of a task set and simultaneously limiting, or even precluding, arbitrary preemptions. In particular, we present a refinement of existing limited-preemptive fixed-priority scheduling (FPS) schemes with preemption thresholds for preemption points next to preemption thresholds for sub-jobs, termed fixed-priority scheduling with varying preemption thresholds (FPVS). We derive exact schedulability analysis for FPVS and we develop algorithms to maximize the schedulability of a set of sporadic tasks for given priorities. Since FPVS generalizes existing FPS schemes, we apply our algorithms to those schemes to compare the ratio of schedulable systems. Our experiments show that FPVS can achieve the same schedulability ratio with limited-preemptive sub-jobs as with entirely non-preemptive sub-jobs.

  • 31.
    Bril, Reinder
    et al.
    Eindhoven University of Technology, The Netherlands.
    Keskin, Ugur
    Eindhoven University of Technology, The Netherlands.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Schedulability analysis of synchronization protocols based on overrun without payback for hierarchical scheduling frameworks revisited2009Conference paper (Refereed)
  • 32.
    Cao, Jingyue
    et al.
    Eindhoven University of Technology, Netherlands.
    Ashjaei, Seyed Mohammad Hossein
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Cuijpers, Pieter J.L.
    Eindhoven University of Technology, Netherlands.
    J. Bril, Reinder
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lukkien, Johan
    Eindhoven University of Technology, Netherlands.
    An Independent yet Efficient Analysis of Bandwidth Reservation for Credit-based Shaping in Ethernet TSN2018In: International Workshop on Factory Communication Systems WFCS'18, Imperia, Italy, 2018, p. 1-10Conference paper (Refereed)
    Abstract [en]

    Ethernet TSN is an upcoming communication standard for industrial distributed embedded systems with high demands on bandwidth and traffic delay. In this paper, we present and prove an improved analysis to determine bandwidth reservations for credit based shapers in a single Ethernet TSN switch. We compare this new analysis, which is based on eligible intervals, to the state-of-the-art bandwidth reservation analysis based on busy periods through experiments. Despite its low complexity and the independence of the knowledge of the interfering traffic, the results show an improvement of efficiency, i.e., a decrease of the required bandwidth, for the new analysis.

  • 33.
    Cranen, Sjoerd
    et al.
    Eindhoven University of Technology, Eindhoven, Netherlands .
    Bril, Reinder J.
    Eindhoven University of Technology, Eindhoven, Netherlands .
    Global schedulability analysis of a synchronization protocol based on replenishment-bounded overrun for compositional real-time systems2012In: 7th IEEE International Symposium on Industrial Embedded Systems, SIES 2012 - Conference Proceedings, 2012, p. 39-47Conference paper (Refereed)
    Abstract [en]

    Hierarchical scheduling frameworks (HSFs) provide means for composing complex real-time systems from well-defined independently developed and analyzed subsystems. To support shared logical resources requiring mutual exclusive access in two-level HSFs, overrun without payback has been proposed as a mechanism to prevent budget depletion during resource access arbitrated by the stack resource policy (SRP). The same mechanism can be applied to support scheduling techniques, such as fixed-priority scheduling with deferred preemption (FPDS), that aim at a reduction of the architecture-related preemption costs and may improve the feasibility of a system. Whereas the blocking times and overrun budgets for shared logical resources will typically be much smaller than the normal budget, these values may significantly increase for scheduling techniques such as FPDS. In this paper, we therefor consider replenishment-bounded overrun, i.e. the overrun ends upon a replenishment, because the normal budget becomes available again, which allows for larger overrun budgets. We show that the global schedulability analysis for this special kind of overrun has a number of anomalies: (i) the usual theorem for critical instant does not hold, (ii) maximal blocking does not necessarily lead to a maximal response time, and (iii) it is not sufficient to analyse a fixed amount of time (say, a number of hyperperiods). We present analysis for two subsystems.

  • 34.
    Hatvani, Leo
    et al.
    Technische Universiteit, The Netherlands.
    Afshar, Sara Zargari
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    J. Bril, Reinder
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Technische Universiteit, The Netherlands.
    Optimal Priority and Threshold Assignment for Fixed-priority Preemption Threshold Scheduling2018In: ACM SIGBED Review, E-ISSN 1551-3688, no 1, p. 43-49Article in journal (Refereed)
    Abstract [en]

    Fixed-priority preemption-threshold scheduling (FPTS) is a generalization of fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). Since FPPS and FPNS are incomparable in terms of potential schedulability, FPTS has the advantage that it can schedule any task set schedulable by FPPS or FPNS and some that are not schedulable by either. FPTS is based on the idea that each task is assigned a priority and a preemption threshold. While tasks are admitted into the system according to their priorities, they can only be preempted by tasks that have priority higher than the preemption threshold.

    This paper presents a new optimal priority and preemption threshold assignment (OPTA) algorithm for FPTS which in general outperforms the existing algorithms in terms of the size of the explored state-space and the total number of worst case response time calculations performed. The algorithm is based on back-tracking, i.e. it traverses the space of potential priorities and preemption thresholds, while pruning infeasible paths, and returns the first assignment deemed schedulable.

    We present the evaluation results where we compare the complexity of the new algorithm with the existing one. We show that the new algorithm significantly reduces the time needed to find a solution. Through a comparative evaluation, we show the improvements that can be achieved in terms of schedulability ratio by our OPTA compared to a deadline monotonic priority assignment.

  • 35.
    Hatvani, Leo
    et al.
    Technische Universiteit Eindhoven (TU/e), The Netherlands.
    Bril, Reinder J.
    Technische Universiteit Eindhoven (TU/e), The Netherlands.
    Minimizing stack usage for AUTOSAR/OSEK's restricted fixed-priority preemption threshold support2016In: 2016 11th IEEE Symposium on Industrial Embedded Systems (SIES 2016) SIES2016, Krakow, Poland, 2016Conference paper (Refereed)
    Abstract [en]

    Fixed priority preemption threshold scheduling (FPTS) may significantly improve the schedulability ratio of task sets compared to both fixed-priority pre-emptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). Moreover, FPTS reduces stack memory requirements compared to FPPS. Unfortunately, the scheduling policy defined by the standard automotive platform AUTOSAR/OSEK only supports a restricted version of FPTS. In earlier work, the consequences of these limitations have been investigated for the schedulability ratio of task sets on a uniprocessor platform. This paper considers the consequences for the stack memory requirements. To that end, it presents a preemption threshold assignment algorithm for minimizing stack usage under FPTS on an AUTOSAR/OSEK platform. The paper includes a comparative evaluation of the stack usage of FPTS without restrictions and FPTS as defined by AUTOSAR/OSEK.

  • 36.
    Hatvani, Leo
    et al.
    Technische Universiteit Eindhoven, Eindhoven, Netherlands .
    J. Bril, Reinder
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Technische Universiteit Eindhoven, Eindhoven, Netherlands .
    Altmeyer, Sebastian
    University of Amsterdam, Amsterdam, Netherlands .
    Schedulability using native non-preemptive groups on an AUTOSAR/OSEK platform with caches2017In: Proceedings of the 2017 Design, Automation and Test in Europe, DATE 2017, Institute of Electrical and Electronics Engineers (IEEE), 2017, p. 244-249Conference paper (Refereed)
    Abstract [en]

    Fixed-priority preemption threshold scheduling (FPTS) is a limited preemptive scheduling scheme that generalizes both fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). By increasing the priority of tasks as they start executing it reduces the set of tasks that can preempt any given task. A subset of FPTS task configurations can be implemented natively on any AUTOSAR/OSEK compatible platform by utilizing the platform's native implementation of non-preemptive task groups via so called internal resources. The limiting factor for this implementation is the number of internal resources that can be associated with any individual task. OSEK and consequently AUTOSAR limit this number to one internal resource per task. In this work, we investigate the impact of this limitation on the schedulability of task sets when cache related preemption delays are taken into account. We also consider the impact of this restriction on the stack size when the tasks are executed on a shared-stack system.

  • 37.
    Holenderski, Mike J.
    et al.
    Eindhoven University of Technology, Netherlands .
    Bril, Reinder J.
    Eindhoven University of Technology, Netherlands .
    Lukkien, Johan
    Eindhoven University of Technology, Netherlands .
    Grasp: Visualizing the Behavior of Hierarchical Multiprocessor Real-Time Systems2013In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 59, no 6, p. 307-314Article in journal (Refereed)
    Abstract [en]

    Trace visualization is a viable approach for gaining insight into the behavior of complex distributed realtime systems. Grasp is a versatile trace visualization toolset. Its flexible plugin infrastructure allows for easy extension with custom visualization and analysis techniques for automatic trace verification. This paper presents its visualization capabilities for hierarchical multiprocessor systems, including partitioned and global multiprocessor scheduling with migrating tasks and jobs, communication between jobs via shared memory and message passing, and hierarchical scheduling in combination with multiprocessor scheduling. For tracing distributed systems with asynchronous local clocks Grasp also supports the synchronization of traces from different processors during the visualization and analysis.

  • 38.
    Holenderski, Mike J.
    et al.
    Technische Universiteit Eindhoven, Netherlands .
    Bril, Reinder J.
    Technische Universiteit Eindhoven, Netherlands .
    Lukkien, Johan
    Technische Universiteit Eindhoven, Netherlands .
    Parallel-task scheduling on multiple resources2012In: Proceedings - Euromicro Conference on Real-Time Systems, 2012, 2012, p. 233-244Conference paper (Refereed)
    Abstract [en]

    This paper addresses the problem of scheduling periodic parallel tasks on a multi-resource platform, where tasks have real-time constraints. The goal is to exploit the inherent parallelism of a platform comprised of multiple heterogeneous resources. A resource model is proposed, which abstracts the key properties of any heterogeneous resource from a scheduling perspective. A new scheduling algorithm called PSRP is presented, which refines MSRP. The schedulability analysis for PSRP is presented. The benefits of PSRP are demonstrated by means of an example application showing that PSRP indeed exploits the available concurrency in heterogeneous real-time systems.

  • 39.
    Holenderski, Mike J.
    et al.
    Eindhoven University of Technology, Netherlands .
    Bril, Reinder J.
    Eindhoven University of Technology, Netherlands .
    Lukkien, Johan
    Eindhoven University of Technology, Netherlands .
    Reducing memory requirements in a multimedia streaming application2011In: Digest of Technical Papers - IEEE International Conference on Consumer Electronics, 2011, 2011, Vol. 57, no 1, p. 325-326Conference paper (Refereed)
    Abstract [en]

    This paper investigates memory management for real-time multimedia applications running on a resource-constrained platform. It is shown how a shared memory pool can reduce the total memory requirements of an application comprised of a data-driven chain of tasks with a time-driven head and tail and a bounded end-to-end latency. The general technique targeted at memory-constrained streaming systems is demonstrated with a video encoding example, showing memory savings of about 19%. 

  • 40.
    Holenderski, Mike J.
    et al.
    Eindhoven University of Technology, Netherlands .
    Bril, Reinder J.
    Eindhoven University of Technology, Netherlands .
    Lukkien, Johan
    Eindhoven University of Technology, Netherlands .
    Reducing memory requirements in a multimedia streaming application2011In: IEEE transactions on consumer electronics, ISSN 0098-3063, E-ISSN 1558-4127, Vol. 57, no 1, p. 145-152Article in journal (Refereed)
    Abstract [en]

    This paper investigates memory management for real-time multimedia applications running on resource-constrained electronic devices. The target applications are comprised of a data-driven task chain with a time-driven head and tail and a bounded end-to-end latency. The necessary buffer capacities along the task chain are derived. Subsequently it is shown how a shared memory pool can reduce the total memory requirements of the whole application. The impact of a shared memory pool is also evaluated in the context of scalable applications. The general technique targeted at memory-constrained streaming systems is demonstrated with a video encoding example, showing memory savings of about 19%.

  • 41.
    Holenderski, Mike J.
    et al.
    Eindhoven University of Technology, Netherlands .
    Bril, Reinder J.
    Eindhoven University of Technology, Netherlands .
    Lukkien, Johan
    Eindhoven University of Technology, Netherlands .
    Swift mode changes in memory constrained real-time systems2009Conference paper (Refereed)
    Abstract [en]

    A method for "preempting memory" is presented, where (parts of) the memory allocated to an active task may be reallocated to another task, without corrupting the state of the active task's job. The method is based on combining scalable components with Fixed-Priority Scheduling with Deferred Preemption (FPDS). Real-time systems composed of scalable components are investigated. A scalable component can operate in one of several modes, where each mode defines a certain trade off between the resource requirements and output quality. The focus of this paper is on memory constrained systems, with modes limited to memory requirements. During runtime the system may decide to reallocate the resources between the components, resulting in a mode change. The latency of a mode change should satisfy timing constraints expressed by upper bounds. A modeling framework is presented combining scalable components with FPDS. A quantitive analysis comparing Fixed-Priority Preemptive Scheduling (FPPS) and FPDS is provided, showing that FPDS sets a lower bound on the mode change latency. The analytical results are verified by simulation. The results for both FPPS and FPDS are applied to improve the existing latency bound for mode changes in the processor domain. The presented protocol is especially suited for pipelined applications, allowing to perform the mode change without the need to first clear the whole pipeline.

  • 42.
    Holenderski, Mike J.
    et al.
    Eindhoven University of Technology, Netherlands.
    Okwudire, Chidi G.U.
    Eindhoven University of Technology, Netherlands.
    Bril, Reinder J.
    Eindhoven University of Technology, Netherlands.
    Lukkien, Johan
    Eindhoven University of Technology, Netherlands.
    Memory Management for Multimedia Quality of Service in Resource Constrained Embedded Systems2010In: Proceedings of the 15th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2010, 2010Conference paper (Refereed)
    Abstract [en]

    In this paper, we consider multimedia Quality-of-Service (QoS) in resource constrained embedded systems, where scalable applications are structured as directed acyclic graphs of tasks, which communicate via shared buffers. Scalable multimedia applications allow to trade quality for resource usage during run-time. We present two QoS problems: (i) temporal dependencies between subchains of tasks due to a common predecessor, and (ii) mode change latency in applications. These problems are addressed through advanced memory management techniques. For the first problem, it is shown how additional access to the buffer, in particular the support for dropping selected frames, allows to guarantee the Quality of Service of the application during overload conditions, preventing congestion in one buffer to propagate across the whole application. For the latter problem, the approach of in-buffer scaling is applied to reduce the mode change latency in scalable multimedia processing applications, which can adapt their memory requirements during runtime according to a set of predefined modes. The latter approach is validated with simulation results.

  • 43.
    Huijbers, E. [Rico] A.M.
    et al.
    Eindhoven University of Technology, Netherlands .
    Ozcelebi, Tanir
    Eindhoven University of Technology, Netherlands .
    Bril, Reinder J.
    Eindhoven University of Technology, Netherlands .
    Complexity scalable motion estimation control for H.264/AVC2011In: Digest of Technical Papers - IEEE International Conference on Consumer Electronics, 2011, p. 49-50Conference paper (Refereed)
    Abstract [en]

    Guaranteeing real-time performance for video encoding on platforms with limited resources is becoming increasingly important for consumer electronics applications. In this paper, an extension of an H.264/AVC encoder with complexity scalable motion estimation (ME) control is presented. An upper bound on the complexity of encoding a single frame is achieved by restricting Sum of Absolute Differences (SAD) computations performed during ME and trading complexity allocation per frame for output quality. Allocation based on residual, i.e. SAD distortion of the final ME match before quantization, of the co-located macroblock in the previous frame outperforms other approaches in the literature in video quality.

  • 44.
    Inam, Rafia
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Sjödin, Mikael
    Mälardalen University, School of Innovation, Design and Engineering.
    Bril, Reinder J.
    Technische Universiteit Eindhoven (TU/e), Eindhoven, The Netherlands.
    Implementing Hierarchical Scheduling to support Multi-Mode System2012In: 7th IEEE International Symposium on Industrial Embedded Systems (SIES) June 20 – June 22, 2012 Karlsruhe, Germany, Conference Proceedings, Karlsruhe, Germany, 2012, p. 319-322Conference paper (Refereed)
    Abstract [en]

    Multi-mode embedded real-time systems exhibit a specific behavior for each mode and upon a mode-change request, the task-set and timing interfaces of the system need to be changed. Hierarchical Scheduling Framework (HSF) is a known technique to partition the CPU time into a number of hierarchically divided subsystems each consists of its own task set. We propose to implement a multi-mode system using a two-level HSF and provide a skeleton (framework)  for an adaptive HSFs supporting multi-modes. Upon a mode-change request, the timing interface of each subsystem is changed, thus making the hierarchical scheduling adaptive in nature. We address the main goals for the implementation and describe the initial design details of Multi-Mode Adaptive Hierarchical Scheduling Framework (MMAHSF) with the emphasis of doing minimal changes to the underlying kernel.

    Download full text (pdf)
    fulltext
  • 45.
    Inam, Rafia
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Sjödin, Mikael
    Mälardalen University, School of Innovation, Design and Engineering.
    J. Bril, Reinder
    TU/e, The Netherlands.
    Mode-Change Mechanisms support for Hierarchical FreeRTOS Implementation2013Conference paper (Refereed)
    Abstract [en]

    Multi-mode embedded real-time systems exhibit a specific behaviour for each mode, and upon a mode-change request the task-set and timing interfaces of the system need to be changed. This paper presents the implementation of a Multi- Mode Adaptive Hierarchical Scheduling Framework (MMAHSF) and provides a generic skeleton (framework) for a two-level adaptive hierarchical scheduling supporting multiple modes and multiple mode-change mechanisms on an open source real-time operating system (FreeRTOS). The MMAHSF enable applicationspecific implementations of mode-change protocols using a set of predefined mode-change mechanisms. The paper addresses different mode-change mechanisms at both global and local scheduling levels. It presents examples of mode-change protocols that are developed by composing together these mechanisms in multiple ways and provide the initial results of executing these protocols in the MMAHSF implementation on an AVR 32-bit board EVK1100.

  • 46.
    J. Bril, Reinder
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Tech Univ Eindhoven, Eindhoven, Netherlands.
    Altmeyer, Sebastian
    Univ Amsterdam, Amsterdam, Netherlands.
    van den Heuvel, Martijn M. H. P.
    Tech Univ Eindhoven, Eindhoven, Netherlands.
    Davis, Robert I.
    Univ York, York, N Yorkshire, England.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Fixed priority scheduling with pre-emption thresholds and cache-related pre-emption delays: integrated analysis and evaluation2017In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 53, no 4, p. 403-466Article in journal (Refereed)
    Abstract [en]

    Commercial off-the-shelf programmable platforms for real-time systems typically contain a cache to bridge the gap between the processor speed and main memory speed. Because cache-related pre-emption delays (CRPD) can have a significant influence on the computation times of tasks, CRPD have been integrated in the response time analysis for fixed-priority pre-emptive scheduling (FPPS). This paper presents CRPD aware response-time analysis of sporadic tasks with arbitrary deadlines for fixed-priority pre-emption threshold scheduling (FPTS), generalizing earlier work. The analysis is complemented by an optimal (pre-emption) threshold assignment algorithm, assuming the priorities of tasks are given. We further improve upon these results by presenting an algorithm that searches for a layout of tasks in memory that makes a task set schedulable. The paper includes an extensive comparative evaluation of the schedulability ratios of FPPS and FPTS, taking CRPD into account. The practical relevance of our work stems from FPTS support in AUTOSAR, a standardized development model for the automotive industry. [(This paper forms an extended version of Bril et al. (in Proceedings of 35th IEEE real-time systems symposium (RTSS), 2014). The main extensions are described in Sect. 1.2.].

  • 47. J. Bril, Reinder
    et al.
    Hassani, Hamid
    Eindhoven Univ Technol TU E, Eindhoven, Netherlands..
    Cuijpers, Pieter J. L.
    Eindhoven Univ Technol TU E, Eindhoven, Netherlands..
    Nelissen, Geoffrey
    Eindhoven Univ Technol TU E, Eindhoven, Netherlands..
    Cost of Robustness of independent WCRT analysis for CBS of Ethernet AVB using eligible intervals2023In: 2023 IEEE 19TH INTERNATIONAL CONFERENCE ON FACTORY COMMUNICATION SYSTEMS, WFCS / [ed] Golatowski, F Ragavan, SKV Facchinetti, T Wisniewski, L Porta, M Scanzio, S, IEEE, 2023, p. 229-232Conference paper (Refereed)
    Abstract [en]

    The existing worst-case response time (WCRT) analysis for individual priority classes under credit-based shaping (CBS) in Ethernet AVB based on so-called eligible intervals is both independent and tight. This WCRT analysis does not rely on any assumptions on interfering inter-priority streams other than those enforced by the Ethernet standard. A major advantage of this independent analysis is that CBS may be viewed as resource reservation, where allocated bandwidth is both guaranteed and enforced. Although independent analysis provides inter-priority class robustness, it comes at a cost of over-provisioning bandwidth. We illustrate this cost of inter-priority class robustness by means of an example that requires 7.8 times the amount of bandwidth reservation for a given set of streams compared to a different analysis that takes knowledge of interpriority streams into account.

  • 48.
    Keskin, U.
    et al.
    Technische Universiteit Eindhoven.
    Van Den Heuvel, M. M. H. P.
    Technische Universiteit Eindhoven.
    Bril, R. J.
    Technische Universiteit Eindhoven.
    Lukkien, J. J.
    Technische Universiteit Eindhoven.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    An engineering approach to synchronization based on overrun for compositional real-time systems2011In: SIES 2011 - 6th IEEE International Symposium on Industrial Embedded Systems, Conference Proceedings, 2011, p. 274-283Conference paper (Refereed)
    Abstract [en]

    Hierarchical scheduling frameworks (HSFs) provide means for composing complex real-time systems from well-defined independently developed and analyzed subsystems. To support shared logical resources requiring mutual exclusive access in two-level HSFs, overrun without payback has been proposed as a mechanism to prevent budget depletion during resource access arbitrated by the stack resource policy (SRP). In this paper, we revisit the global schedulability analysis of synchronization protocols based on SRP and overrun without payback for fixed-priority scheduled HSFs. We derive a new global schedulability analysis based on the observation that the overrun budget is merely meant to prevent budget depletion during global resource access. The deadline of a subsystem therefore only needs to hold for its normal budget rather than the sum of the normal and overrun budget. Our novel analysis is considerably simpler than an earlier, initially improved analysis, which improved both the original local and global schedulability analyses. We evaluate the new analysis based on an extensive simulation study and compare the results with the existing analysis. Our simplified analysis does not significantly affect schedulability compared to the initially improved analysis. It is therefore proposed as a preferable engineering approach to synchronization protocols for compositional real-time systems. We accordingly present the implementation of our improvement in an OSEK-compliant real-time operating system to sketch its applicability in today's industrial automotive standards. Both implementation and run-time overheads are discussed providing measured results1. © 2011 IEEE.

  • 49.
    Keskin, Ugur
    et al.
    Technische Universiteit Eindhoven.
    J. Bril, Reinder
    Technische Universiteit Eindhoven.
    Lukkien, Johan
    Technische Universiteit Eindhoven.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Improving the global schedulability analysis of overrun without payback2010In: Proceedings of the Work-In-Progress (WIP) session of the 22nd Euromicro Conference on Real-Time Systems (ECRTS'10) / [ed] Robert I. Davis, 2010Conference paper (Refereed)
    Abstract [en]

    Overrun without payback has been proposed asa mechanism for a stack resource policy (SRP) based synchronizationprotocol for hierarchical scheduling frameworks(HSFs). In this paper we reconsider the global schedulabilityanalysis of an HSF based on two-level fixed-priority preemptivescheduling (FPPS) using overrun without payback asa mechanism. Improved analysis is presented based on theobservation that there is no need to guarantee the overrunbudget before the end of the budget period, because thatadditional amount of resources is only meant to prevent depletionof a budget during global resource access. The resultingimprovement is illustrated by means of an example. Thepossibility to discard the remainder of an overrun budget upona replenishment is briefly considered as a further improvementand its potential is shown using the same example.

  • 50.
    Nemati, Farhang
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Behnam, Moris
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    J. Bril, Reinder
    Eindhoven University of Technology.
    Investigation of Implementing a Synchronization Protocol under Multiprocessors Hierarchical Scheduling2009In: Proceedings of the Work-In-Progress (WIP) session of 14th IEEE International Conference on Emerging Techonologies and Factory (ETFA'09), 2009Conference paper (Refereed)
    Abstract [en]

    In the multi-core and multiprocessor domain, there has been considerable work done on scheduling techniques assuming that real-time tasks are independent. In practice a typical real-time system usually share logical resources among tasks. However, synchronization in the multiprocessor area has not received enough attention. In this paper we investigate the possibilities of extending multiprocessor hierarchical scheduling to support an existing synchronization protocol (FMLP) in multiprocessor systems. We discuss problems regarding implementation of the synchronization protocol under the multiprocessor hierarchical scheduling.

12 1 - 50 of 78
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf