ID1191

Data Management inVehicle Control-Systems: 

Data Management in Vehicle Control-Systems Dag Nyström Mälardalen Real-Time Research Center Mälardalen University October 26 2005

Part I: 

Part I Background

A Vehicle Control-System: anno 1927: 

A Vehicle Control-System: anno 1927 The electrical system of the first Volvo, “Jakob”.

A Vehicle Control-System: anno 1927: 

A Vehicle Control-System: anno 1927

Vehicle Control-System: anno 2002: 

Vehicle Control-System: anno 2002 The electrical system of the Volvo XC90. A few km of wiring Dozens of computers Several computer networks Millions of lines of software

Information Growth: 

Information Growth In 5 years, vehicles will contain as much memory as a PC of today! Current practice with respect to data management will not be sufficient. Thus, data management at a higher level of abstraction is needed. Source: Audi

Vehicle Control-Systems: 

Vehicle Control-Systems Articulated hauler: Computer-system that controls the functionality of a vehicle Engine control Transmission control Braking control (i.e. ABS) Electronic control unit (ECU) Small box with a processor, memory and a control program Control is performed by Observing the environment Calculating behavior Actuating the result to vehicle

Vehicle Control-Systems: 

Vehicle Control-Systems Properties: Engine ECU Instrumental ECU Cabin ECU Safety critical Limited Resources 16 – 20Mhz CPU´s 64kb RAM 512kb Flash 32kb E2PROM Distributed CAN link Diagnostics link Real-time Critical control activities Hard real-time Non-critical management activities Soft real-time

Data in Vehicle Control-Systems: 

Data in Vehicle Control-Systems Engine Control Brake by Wire ABS Airbag Transmission Control Instrumentation Diagnostics Logging/ Statistics Added Value Features Current practice: Data is scatteredin different locations No uniform data access Consistency is upheld by application No possibility of data modeling

Data in Vehicle Control-Systems: 

Data in Vehicle Control-Systems Engine Control Brake by Wire ABS Airbag Transmission Control Instrumentation Diagnostics Logging/ Statistics Added Value Features Soft real-time Hard real-time Database Manage- Ment System (DBMS) S Q L D B P o i n t e r s Current practice: Future practice? Soft transactions Issued by manage- ment tasks or users Periodic, low freq- uency or event triggered Flexible Complex ~ 100’s of data elements Hard transactions Issued by control- and I/O-tasks Periodic, high frequency Static Simple ~ 1-3 data elements touched Data is centralized, central constraints possible Uniform data access Consistency is upheld by DBMS Data modeling/opt-imization, logical view

Why not using standard DBMSs?: 

Why not using standard DBMSs? A survey of… commercial embedded DBMSs experimental real-time DBMSs … showed that they are not suitable for use in vehicle control-systems since… Their real-time behavior is either lacking or not feasible. That the real-time DBMSs are not resource efficient enough.

Research Contributions: 

Research Contributions A case-study assessing current state of practice for data management in vehicle control-systems. (Paper A , joint effort with Linköping University) A high-level data management concept, denoted the COMET development suit (Paper B, joint effort with Linköping University) Data management concepts and mechanisms. Efficient data access (Paper C) Concurrency-control algorithms (Paper C & D) A data distribution mechanism (Paper E)

Data Management in Vehicle Control-Systems: 

Data Management in Vehicle Control-Systems Challenges: Efficiency and determinism for hard transactions Efficient access of individual data elements Flexibility and expressibility for soft transactions e.g. ad hoc queries Mixing hard and soft transactions Unacceptable blocking of hard transactions Starvation of soft transactions

Part II: 

Part II Results

Efficient Access (Paper C): 

Efficient Access (Paper C) Database Pointers: A method to manipulate data elements in a hard real-time database Deterministic Efficient Access requires a few sequential instructions Co-resides with the relational query processor ”Pointer-like” API Can be created during run-time Allow database reorganization during run-time

An Example Using Database Pointers: 

An Example Using Database Pointers Consider the following I/O task: Using a database pointer TASK OilTempReader(void){ int v; DbPointer *ptr; Bind(&ptr,”SELECT temperature WHERE subsystem=oil;”); while(1){ v=read_sensor(); Write(ptr,v); waitForNextPeriod(); } }

The Internal Structures – pessimistic concurrency approach: 

The Internal Structures – pessimistic concurrency approach ptr … Database Pointer Entries ptr … ptr … ptr … State lockInfo localVer … Soft Transactions State lockInfo localVer … …

Concurrency-Control: 

Concurrency-Control Concurrency-Control is used to resolve data conflicts among concurrently executing transactions Serialization: To order a set of concurrently executed transactions, such that it appears that they have been executed one after another. Concurrency-control algorithms enforce this by: using locks (semaphores) aborting/restarting transactions using multiple versions of data …

Pessimistic Concurrency-Control: 

Pessimistic Concurrency-Control Uses locks e.g. the 2-phase locking (2PL) algorithm transaction workflow: Obtain read- or write-locks on all data elements needed. Read and/or manipulate the ”owned” data elements At commit-time: release all locks In case of lock-conflict either block transaction, or abort some transaction Real-time version of 2PL is 2PL-High Priority (2PL-HP) Aborts low priority transaction in favor of high priority transactions. 2PL-HP is deadlock-free Problem: Long, low priority transactions are severely penalized!!

Versioning-Based Concurrency-Control: 

Versioning-Based Concurrency-Control Uses multiple versions of data elements. Two approaches: Dynamically create new versions on demand. Benefit: High level of concurrency Benefit: Unlimited number of concurrent transactions Drawback: Requires dynamic memory management Drawback: Unpredictable memory usage Statically create n versions of each data element Benefit: Efficient w.r.t. time Drawback: Bounding the number of concurrent transactions. (One version/transaction) Drawback: High memory usage

Our Approach…: 

Our Approach… …is to combine versioning and 2PL-HP to get a concurrency-control algorithm that: allow soft transactions to execute without blocking hard transactions being aborted by hard transactions do not add unpredictable or too much overhead Computational Memory consumption allow launching of soft ad hoc queries during run-time  The 2-Version Database Pointer Concurrency-Control Algorithm (2V-DBP)

2V-DBP: 

2V-DBP Engine Control Brake by Wire ABS Airbag Transmission Control Instrumentation Diagnostics Logging/ Statistics Added Value Features Soft real-time Hard real-time S Q L D B P o i n t e r s

2V-DBP Overview: 

2V-DBP Overview Consist of three parts: The transaction policy A policy that provide the desired behavior The versioning algorithm The mechanisms that enforces the policy Verified using the Uppaal model checker The data structures Used to store versions and transaction states

2V-DBP Transaction policy: 

2V-DBP Transaction policy Soft Transactions Uses a relational query language (e.g. SQL) Obey 2PL-HP Uses Locks Possible Soft-Soft transaction aborts No off-line assumptions i.e., ad hoc transactions can be launced at any time Hard Transactions Uses the database pointer concept Uses a 2-version scheme, no limits on number of trans. Currently only one data access/transaction is allowed Use HW support to enforce atomic behavior (IRQ disable) However, bounded and predictable.

2V-DBP Data Structures: 

2V-DBP Data Structures ptr … Database Pointer Entries ptr … ptr … ptr … dataPtr type lockInfo … Data Pointer State lockInfo localVer … Soft Transactions State lockInfo localVer … … dataPtr type update trans version

2V-DBP Versioning Algorithm: 

2V-DBP Versioning Algorithm Uses an algorithm to decide which copy to read from /write to. Require atomic execution Enforced using interrupt disable Not a big problem for embedded systems Example: Hard write transaction beginATOM(); if(DbP.trans->state!=NO_TRANS) version=NEW_VALUE; update=DIRTY; End if *(DbP.dataPtr)=NEW_VALUE; //Upd Database endATOM();

Serialization in 2V-DBP: 

Serialization in 2V-DBP 2V-DBP slightly relaxes transaction serialization Example:

Evaluation Setup: 

Evaluation Setup Database with 300 tuples with 4 data elements each 300 random database pointers Soft transactions Period 400ms, exec. time >400ms Randomly read-/write-lock up to 200 tuples Hard transactions Period 20 ms, reads/writes a random DbP System 350Mhz Pentium Asterix Real-Time Kernel Interrupt latency of 20μs

Hard Transaction Response-Times: 

Hard Transaction Response-Times 2PL-HP Results within three groups No interference during exec. ~5-8μs (~95% of transactions) Causing soft trans. to abort ~95 μs (~4% of transactions) Suffering from prio. Inversion ~180 μs (~0.1% of transactions) 2V-DBP Results within two groups No interference during exec. ~5μs (>99% of transactions) Suffered from OS latency ~25μs (~20 transactions) Latency actually occurred after transaction  not relevant

Soft Transaction Abortion-Ratios: 

Soft Transaction Abortion-Ratios The evaluation show that 2V-DBP significantly reduce the abortion ratio of soft transactions, compared to 2PL-HP Soft transactions aborted by both soft and hard transactions Soft transactions only aborted by other soft transactions.

Extending 2V-DBP (Paper D): 

Calculating Sensing Extending 2V-DBP (Paper D) Actuating Example: Engine control task Definition Snapshot: A consistent instant view (and control) of the environment. Not supported by 2V-DBP!!! time Solution: Introduce Snapshot transactions Access snapshot-data using database pointers Operate on snapshot sets Predefined (read- and write-set known a priori) 2V-DBP-SNAP

Data Distribution (Paper E): 

Data Distribution (Paper E) Data Distribution Off-line scheduled CAN Uses database pointers Periodic distribution Block-free database access Data assigned to CAN packets Service tools connected through CAN-bus Can priority Time

New Query Types for Service Tools: 

New Query Types for Service Tools Distributed ad hoc queries (diagnostics) Allow a tool to access data in the system Useful for diagnostics Subscription queries (monitoring) Allow a tool to periodically subscribe to any data element Can be turned on and off during run-time Substitution queries (stimulation e.g. test-bench) Allow a tool to take control of any data element (substitute the original producer of the data element) Can be turned on and off during run-time

Conclusions/Future work (Paper B): 

Conclusions/Future work (Paper B) Configuration tool Analysis tools WCET Resource utilization analysis Aspect analyser ECU ECU ECU ECU ECU ECU ECU COMET configuration COMET configuration COMET configuration The COMET Development Suit

Slide35: 

Features: Multi user data access A zero-maintenance run-time environment Transaction control and recovery Full SQL including procedures and triggers Standard interfaces (ODBC, .NET, C++, Java) Features: Worst case response time Sharing of data with soft real-time No unbounded blocking or unwanted restarts Intuitive API that operates on individual data elements in the database. Technology based on proven academic research

Thank you!: 

Thank you!