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
On Improving Resource Utilization in Distributed Real-Time Embedded Systems
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. (Complex Real-Time Embedded Systems)ORCID iD: 0000-0001-9736-8490
2014 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

In our modern life, embedded systems are playing an essential role. An embedded system is a computer system embedded into a certain device, in order to achieve computing functions. Beyond all doubt, as a validated system, the functional correctness must be guaranteed. However, for many embedded systems, timeliness also plays an important role in addition to the correctness of the functionalities. For example, in an automotive braking system, the braking function needs to be processed within a limited time duration in order to avoid accidents. Such systems are known as real-time embedded systems.

In these systems, there can be plenty of software programs (called tasks) sharing limited computing resources (e.g. processors, memories). If the system executes tasks in a random way, the whole system will become unpredictable. As a result, the system designers will not be able to verify if the system design can fulfill all the timing requirements or not. In other words, the system is not guaranteed to be safe. Therefore, system designers need to carefully implement algorithms to schedule all the tasks in a predictable manner. Regarding each scheduling algorithm, schedulability analyses are proposed which are used to check if the requirements can be satisfied.

Unfortunately, many real-time systems reserve too much computing resource for the sake of fulfilling timing requirements, without taking into account resource utilization. As a result, system resources cannot be efficiently utilized, which can cause significant resource waste in reality. Therefore, in this thesis, we aim to improve resource utilization in modern distributed real-time embedded systems. We try to tackle this problem from the following two aspects.

  1. Investigating tighter timing analyses. Due to the difficulty in performing precise mathematical schedulability analyses, most of the existing analyses include varying degrees of pessimism. In other words, the actual performance of the system can be much better than the predictions. If we can reduce the pessimism in schedulability analyses, we can then admit more workload into the system.
  2. Proposing new scheduling frameworks. It is difficult to find a scheduling algorithm which is suitable for all the situations. Therefore, we need different mechanisms to handle specific system characteristics in order to improve the resource utilization. 
Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2014.
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 190
National Category
Embedded Systems
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-26519ISBN: 978-91-7485-177-9 (print)OAI: oai:DiVA.org:mdh-26519DiVA: diva2:762429
Presentation
2014-12-18, Delta, Västerås, 13:30 (English)
Opponent
Supervisors
Projects
START
Available from: 2014-11-12 Created: 2014-11-11 Last updated: 2014-12-09Bibliographically approved
List of papers
1. An Adaptive Server-Based Scheduling Framework with Capacity Reclaiming and Borrowing
Open this publication in new window or tab >>An Adaptive Server-Based Scheduling Framework with Capacity Reclaiming and Borrowing
2014 (English)In: RTCSA 2014 - 20th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2014, Article number 6910548- p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we present a new reservation based scheduling framework for soft real-time systems using EDF algorithm (called CARB-EDF). This framework has the features of Capacity Adaptation, Reclaiming and Borrowing. This framework can simplify the initial configuration of the system, where the system designer does not need to provide any estimations of task execution times. We also present a Chebyshev’s inequality based predictor to estimate task execution times. A number of simulation-based experiments have been implemented. According to the results compared with some related works, our scheduling framework can provide a better performance with acceptable extra scheduling overhead. 

National Category
Embedded Systems
Identifiers
urn:nbn:se:mdh:diva-26516 (URN)10.1109/RTCSA.2014.6910548 (DOI)000352610400052 ()2-s2.0-84908627795 (Scopus ID)9781479939534 (ISBN)
Conference
20th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2014; Chongqing; China; 20 August 2014 through 22 August 2014
Available from: 2014-11-11 Created: 2014-11-11 Last updated: 2015-05-07Bibliographically approved
2. A Server-based Approach for Overrun Management in Multi-Core Real-Time Systems
Open this publication in new window or tab >>A Server-based Approach for Overrun Management in Multi-Core Real-Time Systems
2014 (English)Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents a server-based framework for task overrun management in multi-core real-time systems. Unlike most existing scheduling methods which usually assume a single upper bound of the Worst-Case Execution Time (WCET) for each task, our approach targets scenarios with task overruns. The main idea of our framework is to employ Synchronized Deferrable Servers (SDS) to deal with globally scheduled task overruns, while a partitioned scheduling approach is applied on regular task executions. Moreover, we provide a deterministic Worst- Case Response Time (WCRT) analysis focusing on hard timing constraints, along with a probabilistic analysis of Deadline Miss Ratio (DMR) for soft real-time applications. In the evaluation phase, we have implemented two types of experiments evaluating different timing constraints. 

National Category
Embedded Systems
Identifiers
urn:nbn:se:mdh:diva-26518 (URN)10.1109/ETFA.2014.7005114 (DOI)000360999100065 ()2-s2.0-84946690207 (Scopus ID)978-147994846-8 (ISBN)
Conference
The 19th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA'2014)
Projects
START
Available from: 2014-11-11 Created: 2014-11-11 Last updated: 2016-01-18Bibliographically approved
3. Schedulability analysis of GMF-modeled messages over controller area networks with mixed-queues
Open this publication in new window or tab >>Schedulability analysis of GMF-modeled messages over controller area networks with mixed-queues
2014 (English)In: IEEE Int. Workshop Factory Commun. Syst. Proc. WFCS, 2014, Article number 6837606- p.Conference paper, Published paper (Refereed)
Abstract [en]

The Controller Area Network (CAN) is widely utilized in many industrial real-time applications. As a real-time communication network, the predictability of timing behaviors is very important. Therefore, many works have been proposed regarding the schedulability analysis of CAN messages. Most of the existing analysis approaches are based on a traditional periodic message model. However, in some applications, the transmission of a message may follow a certain pattern instead of repeating the same transmission period by period. In these cases, applying the existing analysis methods may lead to quite pessimistic results. In order to tackle this problem, in this paper we apply the Generalized Multi-Frame (GMF) task model on CAN messages, where both priority-based and FIFO-based message queues are taken into account. We present a corresponding sufficient schedulability analysis. According to the experimental evaluations, our analysis can provide tighter results compared to the existing CAN message response time analysis in the context of GMF-modeled messages. 

Series
IEEE International Workshop on Factory Communication Systems - Proceedings, WFCS
National Category
Communication Systems
Identifiers
urn:nbn:se:mdh:diva-25720 (URN)10.1109/WFCS.2014.6837606 (DOI)000356767300031 ()2-s2.0-84904016213 (Scopus ID)9781479932351 (ISBN)
Conference
10th IEEE Workshop on Factory Communication Systems, WFCS 2014, 5 May 2014 through 7 May 2014, Toulouse
Available from: 2014-07-28 Created: 2014-07-25 Last updated: 2015-07-16Bibliographically approved
4. Applying the Peak Over Thresholds Method on Worst-Case Response Time Analysis of Complex Real-Time Systems
Open this publication in new window or tab >>Applying the Peak Over Thresholds Method on Worst-Case Response Time Analysis of Complex Real-Time Systems
2013 (English)In: 2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2013, 2013, 22-31 p.Conference paper, Published paper (Refereed)
Abstract [en]

The predictability of timing behavior is a very important performance issue of a real-time system. As the complexity of modern industrial systems increases, analyzing the timing behaviors of those systems becomes more and more challenging. Most of the existing analysis methods depend on static and detailed information of the systems under analysis. However, sometimes only partial information of a system can be available, or it may require too much effort on obtaining those details, making those analysis methods much less feasible. Moreover, those methods usually focus on some specific system models with unrealistic assumptions, consequently, applying those methods on a complex industrial real-time system may result in overly pessimistic results. Therefore, in this paper, we propose a statistical method to compute Worst-Case Response Times (WCRTs) of complex real-time systems regarding soft timing constraints, which can provide a higher general applicability with less required system information. Our approach employs a Peak Over Thresholds (POT) method, which is a branch of the Extreme Value Theory (EVT). For the evaluation, we have applied this approach on the analysis of message transmission latencies over Controller Area Networks (CAN).

National Category
Engineering and Technology Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:mdh:diva-21392 (URN)10.1109/RTCSA.2013.6732200 (DOI)2-s2.0-84899413647 (Scopus ID)978-1-4799-0850-9 (ISBN)
Conference
RTSCA 2013, The 19th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, August 19-21, 2013, Taipei, Taiwan
Projects
START - Stochastic Real-Time Analysis of Embedded Software Systems
Available from: 2013-09-16 Created: 2013-09-11 Last updated: 2015-01-09Bibliographically approved
5. An EVT-based Worst-Case Response Time Analysis of Complex Real-Time Systems
Open this publication in new window or tab >>An EVT-based Worst-Case Response Time Analysis of Complex Real-Time Systems
2013 (English)In: Proceedings of the 8th IEEE International Symposium on Industrial Embedded Systems, SIES 2013, 2013, 249-258 p.Conference paper, Published paper (Refereed)
Abstract [en]

In recent years, the complexity of real-time embedded systems has increased dramatically. For those modern real-time systems, the limitations of original static Response Time Analysis (RTA) become more and more conspicuous. Most static analysis methods not only require much detailed system information, but also only target to some specific system model with non-realistic assumptions. As a result, those methods may produce overly pessimistic results, making them unsuitable to be applied on a complex industrial system. The best system model may be the system itself. Therefore, statistical RTA, which can produce probabilistic analysis results based on samples provided by real systems or simulators, may become more expedient. Statistical RTA usually requires more relaxed assumptions and less system information than static RTA. In this paper, we present an Extreme Value Theory (EVT) based method to compute Worst-Case Response Time (WCRT) targeting complex real-time systems. In the evaluation phase, we have applied this method to the calculation of worst-case transmission delays of messages over Controller Area Network (CAN), and some comparisons with static RTA are also provided. According to the experimental results, as the system complexity increases, our approach performs much more stable and less pessimistic.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-21384 (URN)10.1109/SIES.2013.6601498 (DOI)2-s2.0-84885405002 (Scopus ID)9781479906581 (ISBN)
Conference
8th IEEE International Symposium on Industrial Embedded Systems (SIES2013), Porto, Portugal June 19-21, 2013
Projects
START - Stochastic Real-Time Analysis of Embedded Software Systems
Available from: 2013-09-17 Created: 2013-09-11 Last updated: 2014-11-12Bibliographically approved

Open Access in DiVA

fulltext(637 kB)173 downloads
File information
File name FULLTEXT02.pdfFile size 637 kBChecksum SHA-512
bf7c4c4a54b8fa1fe06d62ce30306c90d1f871fb9a666f51f2534a34a93b18689f28a49beaf356d96780e6482d5b2e81ab6989469cdc76ada46c35ea5d3a1982
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Liu, Meng
By organisation
Embedded Systems
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 173 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 612 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