Timing and Schedulability Analysis of Real-Time Systems using Hidden Markov Models

In real-time systems functional requirements are coupled to timing requirements, a specified event needs to occur at the appropriate time. In order to ensure that timing requirements are fulfilled, there are two main approaches, static and measurement-based. The static approach relies on modeling the hardware and software and calculating upper bounds for the timing behavior. On the other hand, measurement-based approaches use timing data collected from the system to estimate the timing behavior. The usability of static and measurement-based approaches is limited in many modern systems due to the increased complexity of hardware and software architectures. Static approaches to timing and schedulability analysis are often infeasible due to their complexity. Measurement-based approaches require that design-time measurements are representative of the timing behavior at runtime, which is problematic to ensure in many cases. Designing systems that guarantee the timing requirements without excessive resource overprovisioning is a challenge. A Hidden Markov Model (HMM) describes a system where the behavior is state-dependent. In this thesis, we model the execution time distribution of a periodic task as an HMM where the states are associated with continuous emission distributions. By modeling the execution times in this manner with a limited number of parameters, a step is taken on the path toward tracking and controlling timing properties at runtime. We present a framework for parameter identification of an HMM with Gaussian emission distributions from timing traces, and validation of the identified models. In evaluated cases, the parameterized models are valid in relation to timing traces. For cases where design-time measurements are not representative of the system at runtime we present a method for the online adaptive update of the emission distributions of an HMM. Evaluation with synthetic data shows that the estimate tracks the ground truth distribution. A method for estimating the deadline miss probability for a task with execution times modeled by an HMM with Gaussian emission distributions, in a Constant Bandwidth Server (CBS) is proposed. The method is evaluated with simulation and for a synthetic task with a known Markov Chain structure running on real hardware.I realtidssystem är funktionella krav kopplade till tidskrav – en viss händelse måste inträffa vid rätt tid. För att försäkra sig om att tidskrav är uppfyllda finns två huvudsakliga metoder – statisk eller mätningsbaserad. En statisk analys baseras på modeller av hårdvara och mjukvara, och beräknar en övre gräns för tidsbeteendet. Mätningsbaserade analyser använder insamlat data från systemet för att uppskatta tidsbeteendet. Användbarheten av både statiska och mätningsbaserade metoder är begränsad i många moderna system eftersom komplexiteten hos hårdvara och mjukvara ökat. Statiska metoder är ofta omöjliga att genomföra på grund av komplexiteten. För mätningsbaserade metoder krävs att mätningarna som insamlats vid design är representativa för tidsbeteendet i drift, vilket är svårt att garantera i många fall. Att designa system som garanterar tidskraven utan överdriven resurstilldelning är en utmaning. En Hidden Markov Model (HMM) beskriver ett system med beteende som är tillståndsberoende. I denna avhandling modellerar vi exekveringstidens fördelning hos en periodisk task (uppgift) som en HMM där tillstånden är kopplade till kontinuerliga emissionsfördelningar. Genom att modellera exekveringstiderna på detta vis med ett begränsat antal parametrar, tar vi ett steg på vägen mot att följa och kontrollera tidsbeteendet i drift. Vi presenterar ett ramverk för parameteridentifiering för en HMM med Gaussiska emissionsfördelningar från tidsdata, och validering av de identifierade modellerna. De parametriserade modellerna är giltiga i relation till tidsdata i de fall som utvärderats. För fall när mätningar vid design inte är representativa för systemet i drift presenterar vi en metod för direkt adaptiv uppdatering av emissionsfördelningarna i en HMM. Utvärdering med syntetiska data visar att uppskattningen följer den sanna fördelningen. En metod föreslås för att uppskatta sannolikheten för att missa en deadline när exekveringstiden modelleras som en HMM med Gaussiska emissionsfördelningar hos en task i en Constant Bandwidth Server (CBS). Metoden utvärderas med simulering och med syntetiska program med känd Markov-struktur som körs på verklig hårdvara