mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Resource Sharing in Real-Time Systems on Multiprocessors
Mälardalen University, School of Innovation, Design and Engineering.
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In recent years multiprocessor architectures have become mainstream, and multi-core processors are found in products ranging from small portable cell phones to large computer servers. In parallel, research on real-time systems has mainly focused on traditional single-core processors. Hence, in order for real-time systems to fully leverage on the extra capacity offered by new multi-core processors, new design techniques, scheduling approaches, and real-time analysis methods have to be developed.

In the multi-core and multiprocessor domain there are mainly two scheduling approaches, global and partitioned scheduling. Under global scheduling each task can execute on any processor at any time while under partitioned scheduling tasks are statically allocated to processors and migration of tasks among processors is not allowed. Besides simplicity and efficiency of partitioned scheduling protocols, existing scheduling and synchronization techniques developed for single-core processor platforms can more easily be extended to partitioned scheduling. This also simplifies migration of existing systems to multi-cores. An important issue related to partitioned scheduling is the distribution of tasks among the processors, which is a bin-packing problem.

In this thesis we propose a blocking-aware partitioning heuristic algorithm to distribute tasks onto the processors of a multi-core architecture. The objective of the proposed algorithm is to decrease the blocking overhead of tasks, which reduces the total utilization and has the potential to reduce the number of required processors.

In industrial embedded software systems, large and complex systems are usually divided into several components (applications) each of which is developed independently without knowledge of each other, and potentially in parallel. However, the applications may share mutually exclusive resources when they co-execute on a multi-core platform which introduce a challenge for the techniques needed to ensure predictability. In this thesis we have proposed a new synchronization protocol for handling mutually exclusive resources shared among real-time applications on a multi-core platform. The schedulability analysis of each application is performed in isolation and parallel and the requirements of each application with respect to the resources it may share are included in an interface. The protocol did not originally consider any priorities among the applications. We have proposed an additional version of the protocol which grants access to resources based on priorities assigned to the applications. We have also proposed an optimal priority assignment algorithm to assign unique priorities to the applications sharing resources. Our evaluations confirm that the protocol together with the priority assignment algorithm outperforms existing alternatives in most cases.

In the proposed synchronization protocol each application is assumed to be allocated on one dedicated core. However, in this thesis we have further extended the synchronization protocol to be applicable for applications allocated on multiple dedicated cores of a multi-core platform. Furthermore, we have shown how to efficiently calculate the resource hold times of resources for applications. The resource hold time of a resource for an application is the maximum duration of time that the application may lock the resource whenever it requests the resource. Finally, the thesis discusses and proposes directions for future work.

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2012.
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 124
National Category
Engineering and Technology
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-14497ISBN: 978-91-7485-063-5 (print)OAI: oai:DiVA.org:mdh-14497DiVA: diva2:516904
Public defence
2012-05-25, Gamma, Mälardalens högskola, Västerås, 14:00 (English)
Opponent
Supervisors
Available from: 2012-04-20 Created: 2012-04-20 Last updated: 2012-05-07Bibliographically approved
List of papers
1. Partitioning Real-Time Systems on Multiprocessors with Shared Resources
Open this publication in new window or tab >>Partitioning Real-Time Systems on Multiprocessors with Shared Resources
2010 (English)In: Lecture Notes in Computer Science, vol. 6490, Springer, 2010, 253-269 p.Chapter in book (Refereed)
Abstract [en]

There are two main approaches to task scheduling on multiprocessor/multi-core platforms; 1) global scheduling, under which migration of tasks among processors is allowed, and 2) partitioned scheduling under which tasks are allocated onto processors and task migration is not allowed. Under global scheduling a higher utilization bound can be achieved, but in practice the overheads of migrating tasks is high. On the other hand under partitioned scheduling, besides simplicity and efficiency, existing scheduling and synchronization methods developed for uniprocessor platforms can more easily be extended to partitioned scheduling. However the partitioned scheduling protocols suffer from the problem of partitioning tasks among processors/cores which is a bin-packing problem. Therefore, several heuristic algorithms have been developed for partitioning a task set on multiprocessor platforms. However, these algorithms typically assume independent tasks while in practice real-time systems often contain tasks that share resources and hence may block each other.

In this paper we propose a blocking-aware partitioning algorithm which allocates a task~set onto processors in a way that the overall amount of blocking times of tasks are decreased. The algorithm reduces the total utilization which, in turn, has the potential to decrease the total number of required processors (cores). In this paper we evaluate our algorithm and compare it with an existing similar algorithm. The comparison criteria includes both number of schedulable systems as well as processor reduction performance.

Place, publisher, year, edition, pages
Springer, 2010
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6490
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-9592 (URN)10.1007/978-3-642-17653-1_20 (DOI)2-s2.0-78650872347 (Scopus ID)978-364217652-4 (ISBN)
Note

14th International Conference on Principles of Distributed Systems, OPODIS 2010; Tozeur;14 December 2010 through 17 December 2010

Available from: 2010-05-17 Created: 2010-05-17 Last updated: 2016-05-17Bibliographically approved
2. Independently-Developed Real-Time Systems on Multi-Cores with Shared Resources
Open this publication in new window or tab >>Independently-Developed Real-Time Systems on Multi-Cores with Shared Resources
2011 (English)In: 23rd EUROMICRO Conference on Real-Time Systems (ECRTS'11), Porto, Portugal, 2011, 251-261 p.Conference paper, (Refereed)
Abstract [en]

In this paper we propose a synchronization protocol for resource sharing among independently-developed real-time systems on multi-coreplatforms. The systems may use different scheduling policies and they may have their own local priority settings. Each system is allocated on a dedicated processor (core). In the proposed synchronization protocol, each system is abstracted by an interface which abstracts the information needed for supporting global resources. The protocol facilitates the composability of various real-time systems with different scheduling and priority settings on a multi-core platform. We have performed experimental evaluations and compared the performance of our proposed protocol (MSOS) against the two existing synchronization protocols MPCP and FMLP. The results show that the new synchronization protocol enables composability without any significant loss of performance. In fact, in most cases the new protocol performs better than at least one of the other two synchronization protocols. Hence, we believe that the proposed protocol is a viable solution for synchronization among independently-developedreal-time systems executing on a multi-core platform.

Place, publisher, year, edition, pages
Porto, Portugal: , 2011
National Category
Computer and Information Science
Identifiers
urn:nbn:se:mdh:diva-13735 (URN)10.1109/ECRTS.2011.31 (DOI)000323257300023 ()2-s2.0-80053001354 (Scopus ID)978-076954442-7 (ISBN)
Conference
23rd Euromicro Conference on Real-Time Systems, ECRTS 2011;Porto;5 July 2011through8 July 2011
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2013-12-03Bibliographically approved
3. Resource Sharing among Prioritized Real-Time Applications on Multiprocessors
Open this publication in new window or tab >>Resource Sharing among Prioritized Real-Time Applications on Multiprocessors
2012 (English)Report (Other academic)
Abstract [en]

MSOS (Multiprocessors Synchronization protocol for real-time Open Systems) is a synchronization protocol for handling resource sharing among independently-developed real-time applications (components) on multi-core platforms.MSOS does not consider any priority setting among applications.To handle resource sharing based on the priority of applications, in this paper we propose a new protocol that allows for resource sharing among prioritized real-time applications on a multi-core platform. We propose an optimal priority assignment algorithm which assigns unique priorities to the applications based on information in their interfaces. We have performed experimental evaluations to compare the proposed protocol (called MSOS-Priority) to the existing MSOS as well as to the current state of the art locking protocols under multiprocessor partitioned scheduling, i.e., MPCP, MSRP, FMLP and OMLP. The evaluations show that MSOS-Priority mostly performs significantly better than alternative approaches.

Publisher
12 p.
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-14494 (URN)
Available from: 2012-04-20 Created: 2012-04-20 Last updated: 2013-12-03Bibliographically approved
4. Resource Sharing among Real-Time Components under Multiprocessor Clustered Scheduling
Open this publication in new window or tab >>Resource Sharing among Real-Time Components under Multiprocessor Clustered Scheduling
2013 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 49, no 5, 580-613 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we propose a general synchronization protocol for resource sharing among independently-developed real-time applications (components) on multi-core platforms. This protocol is a generalization of a previously proposed synchronization protocol (MSOS). In our proposed protocol, each component is statically allocated on a dedicated subset of processors (called cluster). A component has its own internal scheduler by which its tasks are scheduled. In this paper we focus on multiprocessor global fixed-priority preemptive scheduling algorithms to be used to schedule the tasks inside each component. Sharing the local resources is handled by the Priority Inheritance Protocol (PIP). For sharing the global resources (inter-component resource sharing) we have studied usage of FIFO and Round-Robin queues for access the resources across the components and usage of FIFO and prioritized queues inside the components. We have derived schedulability analysis for the different queue handling alternatives and compared their performance by using experimental evaluations. Finally, we have shown that the integration phase can be formulated in the form of a nonlinear integer programming problem where solution techniques in this domain can be used to minimize the total number of processors required to guarantee the schedulability of all components. As a proof of concept we have only provided the formulation for FIFO queues.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-14493 (URN)10.1007/s11241-013-9180-6 (DOI)000321960800002 ()2-s2.0-84880324623 (Scopus ID)
Available from: 2012-04-20 Created: 2012-04-20 Last updated: 2016-01-18Bibliographically approved
5. Resource Hold Times under Multiprocessor Static-Priority Global Scheduling
Open this publication in new window or tab >>Resource Hold Times under Multiprocessor Static-Priority Global Scheduling
2011 (English)In: 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'11), IEEE Computer Society, 2011, 197-206 p.Conference paper, (Refereed)
Abstract [en]

Recently there has been a lot of interest in coexisting of multiple independently-developed real-time applications on a shared open platform. On the other hand, emerging of multi-core platforms and the performance and possibilities they offer has attracted a lot of attention in multiprocessor real-time analysis, protocols and techniques. Co-executing independently- developedreal-time applications on a shared multiprocessor system, where each application executes on a dedicated sub set of processors, requires to overcome the problem of handling mutually exclusive shared resources among those applications. To handle resource sharing, it is important to determine the Resource Hold Time (RHT), i.e., the maximum duration of time that an application locks a shared resource. In this paper, we study resource hold times under multiprocessor static-priority global scheduling. We present how to compute RHT's for each resource in an application. We also show how to decrease the RHT's without compromising the schedulability of the application. We show that decreasing all RHT's for all shared resources is a multiobjective optimization problem and there can exist multiple Paretooptimal solutions.

Place, publisher, year, edition, pages
IEEE Computer Society, 2011
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-13618 (URN)10.1109/RTCSA.2011.34 (DOI)2-s2.0-84855558902 (Scopus ID)978-076954502-8 (ISBN)
Conference
17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011;Toyama;28 August 2011through31 August 2011
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2013-12-03Bibliographically approved

Open Access in DiVA

fulltext(861 kB)3008 downloads
File information
File name FULLTEXT02.pdfFile size 861 kBChecksum SHA-512
ffe8cef957037f7cf1fe16a025c6afeb0cac185c441d3e2c8331934a011ea361bf720f16d7f68dbde88c9d8f09a4254f3e6bc7a66994ebb0111e6edc579932de
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nemati, Farhang
By organisation
School of Innovation, Design and Engineering
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 3008 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 732 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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