This thesis addresses the issues of data management in embedded systems’ software. The complexity of developing and maintaining software has increased over the years due to increased availability of resources, e.g., more powerful CPUs and larger memories, as more functionality can be accommodated using these resources.In this thesis, it is proposed that part of the increasing complexity can be addressed by using a real-time database since data management is one constituent of software in embedded systems. This thesis investigates which functionality a real-time database should have in order to be suitable for embedded software that control an external environment. We use an engine control software as a case study of an embedded system.The findings are that a real-time database should have support for keeping data items up-todate, providing snapshots of values, i.e., the values are derived from the same system state, and overload handling…
Contents
1 Introduction
1.1 Summary
1.2 Motivation
1.2.1 Software Development and Embedded Systems
1.2.2 Software Development and Engine Management Systems
1.2.3 Databases and Software Development
1.3 Goals
1.4 Contributions
1.5 Papers
1.6 Thesis Outline
2 Preliminaries
2.1 Real-Time System
2.1.1 Scheduling
2.1.2 Scheduling and Feasibility Tests
2.1.3 Precedence Constraints
2.1.4 Servers
2.2 Databases
2.2.1 Transactions
2.2.2 Consistency
2.3 Updating Algorithms
2.4 Linear Regression
2.5 Electronic Engine Control Unit
2.5.1 Data Model
2.6 Concurrency Control
2.6.1 Serializability
2.6.2 Concurrency Control Algorithms
2.7 Checksums and Cyclic Redundancy Checks
3 Problem Formulation
3.1 Software Development and Data Management
3.2 Notations and Assumptions
3.3 Problem Formulation
3.3.1 Computational Complexity of Maintaining Data Freshness
3.4 Wrap-Up
4 Data Freshness
4.1 Database System: DIESIS
4.1.1 Implementation of Database System
4.2 Data Freshness
4.2.1 Data Freshness in Time Domain
4.2.2 Data Freshness in Value Domain
4.2.3 Example of Data Freshness in Value Domain
4.3 Marking of Changed Data Items
4.3.1 Correctness of Determining Potentially Affected Data Items
4.4 On-Demand Updating Algorithms in Time Domain
4.5 On-Demand Updating Algorithms in Value-Domain
4.5.1 On-Demand Depth-First Traversal
4.5.2 Relevance Check: ODDFT_C
4.5.3 On-Demand Top-Bottom with relevance check
4.5.4 RADEx++ Settings
4.5.5 Performance Results
4.5.6 DIESIS in EECU
4.6 Wrap-Up
5 Multiversion Concurrency Control With Similarity
5.1 Multiversion Concurrency Control With Similarity
5.1.1 MVTO with Similarity
5.2 Implementation of MVTO-S
5.2.1 MVTO-SUV
5.2.2 MVTO-SUP
5.2.3 MVTO-SCRC
5.3 Single-version Concurrency Control With Similarity
5.4 Implementation Details of Concurrency Control
5.5 Performance Results of Snapshot Algorithms
5.5.1 Experiment 4a: Committed User Transactions
5.6 Wrap-Up
6 Analysis of CPU Utilization of On-Demand Updating
6.1 Specialized Task Model
6.2 Preliminaries
6.2.1 Workload and Schedulability Tests
6.3 Estimation of Mean Interarrival Times of On-Demand Updates
6.3.1 Time Domain using AVI
6.3.2 Value Domain
6.3.3 Estimation Formula Using Similarity
6.4 Evaluations using AVI
6.4.1 Simulator Setup
6.4.2 Performance Evaluations of Workload
6.4.3 Performance Evaluations of Estimations
6.5 Wrap-Up
7 Overload Control
7.1 Introduction
7.2 Extended Data and Transaction Model
7.2.1 Update Functions
7.3 Admission Control Updating Algorithm
7.4 Admission Control using ACUA
7.5 Analyzing CPU Utilization
7.6 Performance Evaluations
7.6.1 Evaluated Algorithms
7.6.2 Simulator Setup
7.6.3 Experiments
7.7 Wrap-Up
8 On-line Estimation of CPU Utilization
8.1 MTBI in a System with Arbitrary Number of Levels in G
8.1.1 Model
8.1.2 Analysis of Data Dependency Graphs
8.1.3 Multiple Regression
8.2 CPU Estimation Algorithm
8.3 Performance Results
8.4 Wrap-Up
9 Related Work
9.1 Updating Algorithms and Data Freshness
9.2 Concurrency Control
9.3 Admission Control
10 Conclusions and Future Work
10.1 Conclusions
10.2 Discussions
10.3 FutureWork
A Abbreviations and Notation
B On-Demand Updating Algorithms in Value-Domain
B.1 Updating Schemes
B.2 Binary marking of stale data items
B.3 Bottom-Up Traversal: Depth-First Approach
B.4 Bottom-Up Traversal: Breadth-First Approach
B.5 ODKB_C Updating AlgorithmWith Relevance Check
B.6 Top-Bottom Traversal: ODTBWith Relevance Check
B.7 Supporting Mechanisms and Algorithms
B.7.1 BeginTrans
B.7.2 ExecTrans
B.7.3 AssignPrio
B.8 Performance Results
B.8.1 Experiment 1b: Deriving Only Actuator User Transactions
B.8.2 Experiment 1c: Comparison of Using Binary Change Flag
or pa Time stamp
B.8.3 Experiment 1e: Effects of Blocking Factor
B.8.4 Experiment 2a: Consistency and Throughput With Relevance Check
B.8.5 Experiment 2b: Effects of Blocking Factors and Only
Deriving Actuator Transactions
C Multiversion Concurrency Control with Similarity
C.1 Performance Results
C.1.1 Simulator Setup
C.1.2 Experiment 4b: Memory Pool Size
C.1.3 Experiment 4c: Priority Levels
C.1.4 Experiment 4d: Overhead
C.1.5 Experiment 4e: Low Priority
C.1.6 Experiment 4f: Transient State
D Confidence Intervals 2
Author: Gustafsson, Thomas
Source: Linkoping University
Download URL 2: Visit Now