Due to advances in capacity, speed, and economics, NAND-based flash memory technology is increasingly integrated into all types of computing systems, ranging from enterprise servers to embedded devices. However, due to its unpredictable up-date behavior and time consuming garbage collection mechanism, NAND-based flash memory is difficult to integrate into hard-real-time embedded systems. In this thesis, I propose a performance model for flash memory garbage collection that can be used in conjunction with a number of different garbage collection strategies. I describe how to model the cost of reactive (lazy) garbage collection and compare it to that of more proactive schemes. I develop formulas to assess the schedulability of hard real- time periodic task sets under simplified memory consumption models. Results show that I prove the proactive schemes achieve the larger maximum schedulable utilization than the traditional garbage collection mechanism for hard real-time systems in flash memory.

Diss. Uppsala : Univ., 2002.

ABB SA Products designs and manufactures complex real-time systems. The real-time properties of the system are hard to measure and test especially in the long run, e.g.  monitoring a system for months out in the real environment. ABB have started developing their own tool called JobMon for monitoring timing requirements, but they needed to measure more properties than time and in a more dynamic way than JobMon is constructed today. The tool must be able to measure different kind of data and be able to be monitor as long as the system itself. This thesis first does a survey and evaluation on existing commercial tools and if there exists a tool that can be integrated to the system and fulfill all demands. Different trace recorders and system monitoring tools are presented with its properties and functions. The conclusion is that there is no such tool and the best solution is to design and develop a new tool. The result is SysMon, a dynamic generic framework for measuring any type of data within a real-time system. The main focus for measuring during this thesis is time measurements, but no limits or assumptions of data types are made, and during late steps of the development new types of measurements are integrated. SysMon can also handle limits for measurements and, if required, take pre-defined actions e.g. triggering a logging function and saving all information about the measurement that passed the limit. The new tool is integrated to the system and evaluated thoroughly. It is an important factor to not steal too much resource from the system itself, and therefore a measurement of the tool’s intrusiveness is evaluated. / ABB SA Products designar och konstruerar komplexa realtidssystem. Realtidsegenskaperna för systemen är svåra att mäta och testa, speciellt under långa tidsperioder, t.ex. under drift i dess riktiga miljö under månader av online tid. ABB SA Products har börjat utvecklat ett eget verktyg, JobMon, för att kunna övervaka och mäta egenskaper i form av tid. Men behovet är större än att endast mäta tid och alla möjliga slags data behöver övervakas och utvärderas. Det här examensarbetet gör först en undersökning och utvärdering av existerande kommersiella verktyg och om det redan finns ett verktyg som uppfyller alla krav. Olika tracerecorders och systemövervakningsverktyg är presenterade med dess egenskaper och funktioner. Slutsatsen är till sist att det inte finns något existerande verktyg och att den bästa lösningen är att utveckla ett nytt verktyg. Resultatet är SysMon, ett dynamisk generisk ramverk för att mäta vilken form av data som helst. Huvudfokus under examensarbetet är tidsmätningar, men inga antaganden om vilka datatyper som kan användas görs. Under den senare delen av examensarbetet implementeras också en ny typ av mätning i system ticks. SysMon kan också hantera gränser för mätningar och, om nödvändigt, exekvera fördefinierade funktioner, t.ex. trigga en loggning och spara nödvändig information om mätningen som överskred gränsen. Det nya verktyget blir integrerat i systemet och testat noggrant. Det är viktigt att verktyget inte tar för mycket resurser från det normala systemet och därför utförs även en utvärdering av hur resurskrävande verktyget är.

No description available.

Priority Assignment is one of the crucial problems in the scheduling of fixed-priority real-time systems, which requires both timely response and correctness of output under specified timing constraints. As the models and hardware platforms of real-time systems become increasingly more complex, it is necessary to consider various design metrics in addition to the system schedulability when we assign priorities to tasks. There has been a rich set of research studies on the priority assignment algorithms. However, there exist several limitations in the state-of-the-art: 1) the current research focuses on improving existing schedulability analyses but fails to integrate them with priority assignment algorithms which has better solution quality than heuristics; 2) the stochastic nature of task execution time in real operation and the properties of heterogeneous hardware platforms are not fully studied in the priority assignment process; and 3) design metrics other than response time are omitted in the priority assignment. In this dissertation, we seek to address the issues in the following aspects. First, instead of using existing schedulability analysis directly, we leverage the proposed concept of response time estimation range to build a novel priority assignment framework. It can quickly rule out infeasible priority assignments that share common attributes and be coupled with a more accurate schedulability analysis than Audsley's Optimal Priority Assignment (OPA) with much weaker compatibility conditions. The framework judiciously takes advantage of optimization techniques and heuristics under different task utilization to achieve better overall acceptance ratio of task system. Second, we consider the attributes of tasks, hardware platform (e.g., heterogeneous platform) and design metrics (e.g., reaction time and data age) of real applications in the process of priority assignment. Current studies assume worst case or certain distribution of tasks' execution times in their response time analysis. However, analysis based on these assumptions are pessimistic and overestimate the response times in some cases. We propose a more general model which does not assume any specific distribution of task execution time and analyze the response time by the convolution method. In addition, we propose stochastic heterogeneous Direct Acyclic Graph (DAG) model to take into account the randomness of execution and heterogeneous hardware platform in real operation. Third, we establish an optimization framework which takes other design metrics (e.g., reaction time, data age), in addition to response time in most studies, as objective and constraints in the optimization process. These design metrics can be important in real applications to guarantee satisfying performance of task system. We demonstrate the effectiveness of our proposed frameworks with several case studies, which have shown that our methods can achieve better system schedulability and/or better run-time. / Doctor of Philosophy / Real-time systems are crucial in control-centric applications, which require both the correctness and timely response of the output. Such systems have specified timing constraints which the outputs of the systems should meet. Failure to meet timing constraints will result in performance degradation or safety-related issues in extreme cases. Priority assignment is the process to assign priorities to tasks. In general case, tasks with higher priorities will execute ahead of tasks with lower priorities when computing resources are available. Priority assignment has an important role in scheduling, which determines the execution orders of the tasks. Current priority assignment algorithms come across several challenges: 1) existing analyses are directly integrated with heuristic method for priority assignment, which cannot guarantee the optimality of the solution; 2) the attributes of the hardware platform or the stochastic nature of task execution in real applications are not fully considered; 3) more design metrics need to be considered in addition to timely response of the system. In this dissertation, we aim to propose better solutions for the above issues. Experimental evaluation has shown that the proposed frameworks outperform existing priority assignment algorithms in terms of run-time and number of tasks that meet the timing constraints of the real-time systems.

Real-Time systems are defined not only by their logical correctness but also timeliness. Modern real-time systems, such as those controlling industrial plants or the flight controller on UAVs, are no longer isolated. The same computing resources are shared with a variety of other systems and software. Further, these systems are increasingly being connected and made available over the internet with the rise of Internet of Things and the need for automation. Many real-time systems contain sensitive code and data, which not only need to be kept confidential but also need protection against unauthorized access and modification. With the cheap availability of hardware supported Trusted Execution Environments (TEE) in modern day microprocessors, securing sensitive information has become easier and more robust. However, when applied to real-time systems, the overheads of using TEEs make scheduling untenable. However, this issue can be mitigated by judiciously utilizing TEEs and capturing TEE operation peculiarities to create better scheduling policies. This thesis provides a new task model and scheduling approach, Split-TEE task model and a scheduling approach ST-EDF. It also presents simulation results for 2 previously proposed approaches to scheduling TEEs, T-EDF and CT-RM. / Master of Science / Real-Time systems are computing systems that not only maintain the traditional purpose of any computer, i.e, to be logically correct, but also timeliness, i.e, guaranteeing an output in a given amount of time. While, traditionally, real-time systems were isolated to reduce interference which could affect the timeliness, modern real-time systems are being increasingly connected to the internet. Many real-time systems, especially those used for critical applications like industrial control or military equipment, contain sensitive code or data that must not be divulged to a third party or open to modification. In such cases, it is necessary to use methods to safeguard this information, regardless of the extra processing time/resource consumption (overheads) that it may add to the system. Modern hardware support Trusted Execution Environments (TEEs), a cheap, easy and robust mechanism to secure arbitrary pieces of code and data. To effectively use TEEs in a real-time system, the scheduling policy which decides which task to run at a given time instant, must be made aware of TEEs and must be modified to take as much advantage of TEE execution while mitigating the effect of its overheads on the timeliness guarantees of the system. This thesis presents an approach to schedule TEE augmented code and simulation results of two previously proposed approaches.

As embedded software and platforms become more complicated, many safety properties are left to simulation and testing. MRICDF is a formal polychronous language used to guarantee certain safety properties and alleviate the burden of software development and testing. We propose real-time extensions to MRICDF so that temporal properties of embedded systems can also be proven. We adapt the extended precedence encoding technique of Prelude and expand upon current schedulability analysis techniques for multi-periodic real-time systems. / Master of Science

In the world of real-time systems (RTS), security has often been overlooked in the design process. However, with the emergence of the Internet of Things and Cyber-Physical Systems, RTS are now frequently used in interconnected applications where data is shared regularly. Unfortunately, this increased connectivity has also led to a larger attack surface. As a result, it is crucial to redesign RTS to not only meet real-time requirements but also to be resilient to threats. To address this issue, we propose a new real-time security co-design task model, and an accompanying scheduling framework, where schedulability can be used to indicate whether both real-time and security requirements are met. Our algorithm is designed to be flexible, allowing different security mechanisms to be used along with real-time tasks. Specifically, we augment the frame-based task model by introducing an n-dimensional security matrix, which serves as a powerful tool to enable our approach. This matrix clearly indicates which defense mechanisms are available for each task in the system by storing the worst-case execution times of tasks. Then, we transform the problem of maximizing security, subject to schedulability, into a variant of the knapsack problem. To make this approach more practical, we implement a fully polynomial time approximation scheme (FPTAS) that reduces the time complexity of solving the knapsack problem from a pseudo-polynomial to a fully polynomial. We also experiment with a greedy-heuristic approach and compare the results of both algorithms. / Master of Science / Real-time systems are computer systems that need to respond to events in a timely manner. In the past, these systems were designed without much consideration for security. However, with the increasing use of interconnected devices and systems, it has become important to make sure that real-time systems are secure and protected against malicious attacks. To address this issue, we propose a new approach for designing real-time systems that prioritizes security from the very beginning. Our approach allows for different security tasks to be executed depending on the system's needs, and we use a two-dimensional security matrix to help with this. We also introduce a way to solve the security problem that is faster and more efficient than previous methods. Our experimental results show that our new approach significantly reduces the time and effort required to solve the security problem while still producing good results.

The increasing dependency of man on machines have led to increase computational load on systems. The increasing computational load can be handled to some extent by scaling up processor frequencies. However, this approach has hit a frequency and power wall and the increasing awareness towards green computing discourages this solution. This leads us to use multi-core architectures. Due to the same reason, real-time systems are also migrating from single-core towards multi-core systems. While multi-core systems provide scalable high computational power, they also expose real-time systems to several challenges. Most of these challenges hamper the key property of real-time systems, i.e., predictability. In this work, we address some challenges imposed by multi-core architectures on real-time systems. We propose and evaluate several scheduling algorithms and demonstrate improved predictability and performance over existing methods. A unifying them in all our algorithms is that we explicitly consider the effects of architectural factors on the scheduling and schedulablity of real-time programs. As a case study, we use Tilera's TilePro64 platform as an example multi-core platform and implement some of our algorithms on this platform. Through this case study, we derive several useful conclusions regarding performance, predictability and practical overheads on a multi-core architecture.

No description available.