mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct 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
Lock-Based Resource Sharing for Real-Time Multiprocessors
Mälardalen University, School of Innovation, Design and Engineering. (Complex Real-Time Systems)ORCID iD: 0000-0002-0474-2904
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Embedded systems are widely used in the industry and are typically resource constrained, i.e., resources such as processors, I/O devices, shared buffers or shared memory might be limited in the system. Hence, techniques that can enable an efficient usage of processor bandwidths in such systems are of great importance. Locked-based resource sharing protocols are proposed as a solution to overcome resource limitation by allowing the available resources in the system to be safely shared. In recent years, due to a dramatic enhancement in the functionality of systems, a shift from single-core processors to multi-core processors has become inevitable from an industrial perspective to tackle the raised challenges due to increased system complexity. However, the resource sharing protocols are not fully mature for multi-core processors. The two classical multi-core processor resource sharing protocols, spin-based and suspension-based protocols, although providing mutually exclusive access to resources, can introduce long blocking delays to tasks, which may be unacceptable for many industrial applications. In this thesis we enhance the performance of resource sharing protocols for partitioned scheduling, which is the de-facto scheduling standard for industrial real-time multi-core processor systems such as in AUTOSAR, in terms of timing and memory requirements.

 

A new scheduling approach uses a resource efficient hybrid approach combining both partitioned and global scheduling where the partitioned scheduling is used to schedule the major number of tasks in the system. In such a scheduling approach applications with critical task sets use partitioned scheduling to achieve higher level of predictability. Then the unused bandwidth on each core that is remained from partitioning is used to schedule less critical task sets using global scheduling to achieve higher system utilization. These scheduling schema however lacks a proper resource sharing protocol since the existing protocols designed for partitioned and global scheduling cannot be directly applied due to the complex hybrid structure of these scheduling frameworks. In this thesis we propose a resource sharing solution for such a complex structure. Further, we provide the blocking bounds incurred to tasks under the proposed protocols and enhance the schedulability analysis, which is an essential requirement for real-time systems, with the provided blocking bounds.

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2017.
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 247
National Category
Embedded Systems
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-37215ISBN: 978-91-7485-361-2 (print)OAI: oai:DiVA.org:mdh-37215DiVA: diva2:1154894
Public defence
2017-12-19, Kappa, Mälardalens högskola, Västerås, 13:30 (English)
Opponent
Supervisors
Available from: 2017-11-07 Created: 2017-11-06 Last updated: 2017-11-09Bibliographically approved
List of papers
1. Flexible spin-lock model for resource sharing in multiprocessor real-time systems
Open this publication in new window or tab >>Flexible spin-lock model for resource sharing in multiprocessor real-time systems
2014 (English)In: Proc. IEEE Int. Symp. Ind. Embedded Syst., SIES, 2014, 41-51 p.Conference paper, Published 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.

Series
Proceedings of the 9th IEEE International Symposium on Industrial Embedded Systems, SIES 2014
Keyword
Locks (fasteners), Real time systems, Access to resources, Better performance, Conventional approach, Global resources, Multi-processor platforms, Resource access, Resource locking, Resource sharing, Multiprocessing systems
National Category
Computer and Information Science
Identifiers
urn:nbn:se:mdh:diva-25907 (URN)10.1109/SIES.2014.6871185 (DOI)000345746200007 ()2-s2.0-84906688738 (Scopus ID)9781479940233 (ISBN)
Conference
9th IEEE International Symposium on Industrial Embedded Systems, SIES 2014, 18 June 2014 through 20 June 2014, Pisa
Available from: 2014-09-12 Created: 2014-09-12 Last updated: 2017-11-06Bibliographically approved
2. Per Processor Spin-Lock Priority for Partitioned Multiprocessor Real-Time Systems
Open this publication in new window or tab >>Per Processor Spin-Lock Priority for Partitioned Multiprocessor Real-Time Systems
(English)In: Leibniz Transactions on Embedded Systems, ISSN 2199-2002Article in journal (Other academic) Accepted
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.

National Category
Computer Science
Identifiers
urn:nbn:se:mdh:diva-37183 (URN)
Available from: 2017-11-02 Created: 2017-11-02 Last updated: 2017-11-06Bibliographically approved
3. An optimal spin-lock priority assignment algorithm for real-time multi-core systems
Open this publication in new window or tab >>An optimal spin-lock priority assignment algorithm for real-time multi-core systems
2017 (English)In: The 23th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA'17, 2017, 8046310Conference paper, Published 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.

National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-37055 (URN)10.1109/RTCSA.2017.8046310 (DOI)
Conference
The 23th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA'17, 16 Aug 2017, Hsinchu, Taiwan
Projects
PRESS - Predictable Embedded Software SystemsDPAC - Dependable Platforms for Autonomous systems and Control
Available from: 2017-11-02 Created: 2017-11-02 Last updated: 2017-11-16Bibliographically approved
4. Resource Sharing under Multiprocessor Semi-Partitioned Scheduling
Open this publication in new window or tab >>Resource Sharing under Multiprocessor Semi-Partitioned Scheduling
2012 (English)In: 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'12), 2012, 290-299 p.Conference paper, Published paper (Refereed)
Abstract [en]

Semi-partitioned scheduling has become the subject of recent interest for multiprocessors due to better utilization results, compared to conventional global and partitioned scheduling algorithms. Under semi-partitioned scheduling, a major group of tasks are assigned to fixed processors while a low number of tasks are allocated to more than one processor. Various task assigning techniques have recently been proposed in a semi-partitioned environment. However, a synchronization mechanism for resource sharing among tasks in semi-partitioned scheduling has not yet been investigated. In this paper we propose and evaluate two methods for handling resource sharing under semi-partitioned scheduling in multiprocessor platforms. The main challenge addressed in this paper is to serve the resource requests of tasks that are assigned to different processors.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-17295 (URN)10.1109/RTCSA.2012.25 (DOI)2-s2.0-84869032347 (Scopus ID)978-1-4673-3017-6 (ISBN)
Conference
Embedded and Real-Time Computing Systems and Applications (RTCSA), 2012 IEEE 18th International Conference, 19-22 Aug. 2012
Available from: 2012-12-20 Created: 2012-12-20 Last updated: 2017-11-06Bibliographically approved
5. Resource Sharing Under Global Scheduling with Partial Processor Bandwidth
Open this publication in new window or tab >>Resource Sharing Under Global Scheduling with Partial Processor Bandwidth
2015 (English)In: 2015 10th IEEE International Symposium on Industrial Embedded Systems, SIES 2015 - Proceedings, 2015, 195-206 p.Conference paper, Published 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.

National Category
Computer Engineering
Identifiers
urn:nbn:se:mdh:diva-28161 (URN)10.1109/SIES.2015.7185061 (DOI)000380569800027 ()2-s2.0-84959508561 (Scopus ID)9781467377119 (ISBN)
External cooperation:
Conference
10th IEEE International Symposium on Industrial Embedded Systems, SIES 2015; Siegen; Germany; 8 June 2015 through 10 June 2015
Projects
PRESS - Predictable Embedded Software Systems
Available from: 2015-06-12 Created: 2015-06-08 Last updated: 2017-11-06Bibliographically approved
6. Resource sharing in a hybrid partitioned/global scheduling framework for multiprocessors
Open this publication in new window or tab >>Resource sharing in a hybrid partitioned/global scheduling framework for multiprocessors
2015 (English)In: IEEE International Conference on Emerging Technologies and Factory Automation, ETFA, 2015Conference paper, Published 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.

Keyword
Job shop scheduling, Processor scheduling, Program processors, Protocols, Resource management, Servers, Synchronization, Embedded systems, Factory automation, Interactive computer systems, Multiprocessing systems, Network protocols, Optimization, Real time systems, Critical applications, Embedded real time systems, Resource reservations, Schedulability analysis, Scheduling frameworks, Synchronization protocols, Scheduling
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:mdh:diva-31602 (URN)10.1109/ETFA.2015.7301456 (DOI)000378564800057 ()2-s2.0-84952909303 (Scopus ID)9781467379298 (ISBN)
Conference
20th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2015, 8 September 2015 through 11 September 2015
Available from: 2016-05-23 Created: 2016-05-19 Last updated: 2017-11-06Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Afshar, Sara

Search in DiVA

By author/editor
Afshar, Sara
By organisation
School of Innovation, Design and Engineering
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 21 hits
CiteExportLink to record
Permanent link

Direct 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